Does anyone know what TCP stands for? The P is likely for Protocol, and while many know the T stands for Transfer, it actually stands for Transmission. What about the C? It would be Control, right? If we look up the word Control, we find three main meanings, and contextually, the third meaning is probably what we want: to regulate a machine, equipment, or chemical reaction so that it operates appropriately for its purpose. This means that TCP has a specific purpose and implies that it appropriately controls certain actions. Now, we understand that control is important, but what exactly is being controlled? I'm Pedro from Group 6, and I’m here to explore that with you. I’ve prepared the presentation in the following order: first, we’ll briefly look at the purpose of TCP, and then we’ll explore the three methods of control one by one. So, why do we use TCP?

To understand the purpose, we need to briefly look at the OSI 7 layers. When communication devices first emerged, various protocols from different vendors were mixed together. This inevitably led to compatibility issues. To resolve this, the International Organization for Standardization (ISO) proposed a network standard model, known as the OSI 7 layers. The main purpose of this model is to prevent the fragmentation of communication standards by separating concerns at each layer. It was designed to facilitate maintenance and management by assigning roles and responsibilities at each layer, similar to object-oriented programming and MVC architecture. As a side note, my favorite layer is the Data Link layer. However, putting my preference aside, we will be focusing on TCP, so let's take a look at the Transport layer, which is described in RFC 1122.

The transport layer provides services for end-to-end communication. One of the protocols among them is called TCP. TCP offers reliability, reordering, and flow control between endpoints. Here, a difficult term has come up: what does reliability between endpoints actually mean? Reliability simply means that there is no damage or loss of data. When sender A requests receiver B to please modify this, we live in a world where it seems obvious that this will be delivered to B. However, in the self-operating network in between, more complex things happen than we might think. What happens? Data is ultimately made up of sequences of bits consisting of 0s and 1s, right?

How do we encode these bit streams well so that they can be converted into electrical or optical signals? Then, they are transmitted through the physical layer to a remote location. However, this physical layer truly exists in the physical world, so it is influenced by natural physical laws. For example, energy loss occurs due to channel resistance, and various encoded data are sent as composite signals made up of multiple sine waves. The components of these signals travel through the channel at different speeds. As a result, while we send these signals, the receiver may receive a distorted version of the signal. Therefore, control over this distortion is necessary. Additionally, various types of noise, commonly referred to as thermal noise or induced noise, can also mix in. Finally, since the network routes the data, the transmission paths for each packet may differ, so just because I sent a packet first...

We cannot guarantee that the recipient will receive the message first. Therefore, it might be good to remember that the reliability of the transmission channel cannot be guaranteed. From the perspective of how we can achieve reliable communication through such unreliable channels, the concept of RDT: Reliable Data Transfer arises. Fortunately, reliable data transfer is not solely the responsibility of the transport layer; it is shared between the data link layer, which is my favorite layer, and the transport layer. Both layers have similar but slightly different control technologies. The data link layer supports reliable communication to the next destination, while the transport layer, with the help of the data link layer, ensures reliable end-to-end transmission. Now, I have organized a few challenges that TCP needs to address, such as the possibility of packet loss.

The order may be reversed, and packets could completely disappear in a congested state, or the receiver may not be able to process them. There seem to be many such issues, so let's take a look at them one by one. First, we have TCP error control, which refers to how TCP handles cases where data is lost or incorrect data is received. To control errors, we must first be able to detect them. To clearly define an error, it can occur when the data sent by the sender is lost, when the acknowledgment (ACK) sent by the receiver is lost, or when the receiver receives a duplicate acknowledgment. TCP fundamentally responds to these error packets by retransmitting them. For example, if both the 0th packet and the 1st packet are received and acknowledged, but the 2nd packet is lost, from the sender's perspective, it might wonder, Why is the 3rd packet being sent without the 2nd packet?

Let's change it again. In this way, the sender can detect this and retransmit it. These things are referred to as Automatic Repeat Request, which introduces the concept of ARQ. To put it simply, if you want to implement ARQ easily, you can send the next data once you receive an acknowledgment that the previous data was received correctly. For example, Received 0, understood. Received? Understood. Received? Understood. Just looking at it, it seems very inconvenient, and you would want to refactor it, right? So, there are these drawbacks. Until the acknowledgment is received, the next transmission is blocked, making it very inefficient. To alleviate these issues, there are two methods available. Both methods share the basic concept of sending data in bundles and defining how to fix the lost packets. The first method I will explain is the Go-back-N method, where three packets are bundled and sent like this.

one packet has been lost. In this case, all packets from the lost one will be sent again. This method is inefficient because many packets are discarded in the event of an error. Next is the Selective Repeat method, which also sends three packets together but only requests the retransmission of the lost packet number four. Once it is resent, the receiver must store the correctly received data in a separate buffer and sort it by sequence, which leads to overhead as a disadvantage.

Next is flow control. The basic concept is based on regulating the amount of data transmitted between the sender and receiver. In general communication between two devices, when the data transfer speeds for input and output differ, a buffer is used to mitigate that difference. However, a buffer is ultimately a finite storage space. If the output speed on the communication side continues to be faster than the processing speed on the receiving side,

the buffer on the receiving end will become full, and any data transmitted afterward will be lost. This is where the sliding window flow control technique in TCP is explained. TCP itself is defined in RFC 793, and you can find the explanation of Flow Control in section 3.1. The window field in the TCP header is utilized, and rwnd (Receive Window) represents the upper limit of the amount of data that can be sent by the sender before receiving a response from the receiver. As a result, during the 3-Way Handshake, they check their buffer status to negotiate the size of rwnd, and ultimately, the window size used in that session is set to the smaller value of the two. 

Now, the window used in the sliding window can be divided into four main parts. The green part represents the data that I have already sent and confirmed as received. The yellow part indicates the data that has been transmitted but for which an acknowledgment has not yet been received. The blue part signifies the data that is still available but has not yet been transmitted, meaning it can be used in the future. The yellow and blue parts combined...

The window size is defined, and the gray area represents the range that exceeds the window, which means it cannot be transmitted yet. The part that has been transmitted but has not received an acknowledgment is called an In-Flight packet. Controlling the size of these In-Flight packets is the key to flow control. Now, I have outlined scenarios with an rwnd of 7. Since the window size is 7, the sender can transmit a maximum of 7 data packets without the receiver's acknowledgment. Therefore, from the sender's perspective, each time data is sent, the left pointer is incremented by one, and each time an acknowledgment is received, the right pointer is increased, creating the appearance of the window sliding to the right, which is why it is called a Sliding Window. I will examine the effectiveness of this flow control through a scenario where three transmissions are requested, leaving two windows remaining. When the acknowledgment is sent again, it will indicate, I currently have two slots remaining in the window.

Now, from the sender's perspective, if an additional request for four transmissions is made, it will not be sent immediately. Instead, when a buffer read delay occurs, it results in a situation where the sender thinks, I still haven't reduced my window size, causing the delay. Once the buffer is emptied and the window size is restored, only then does the actual transmission take place. This transmission delay allows the sender to control the flow so that the sender does not overflow the receiver's buffer while continuing to send data. It would be great if this were the end of the discussion, but unfortunately, it cannot be concluded here. You might wonder, If error control is completed and the buffer is fine, isn't that the end? Let's consider a scenario: A is transmitting data to C, and B is transmitting data to D. In this situation, the buffers of the routers along the paths are finite. Naturally, there will be moments when both transmissions traverse the same path. This moment implies that they will mutually affect each other's paths.

In other words, if too many packets are sent at once, it can lead to a situation where both hosts ultimately fail to transmit. If we represent such transmission volumes on a graph, it looks like this: R is the input/output link capacity, λ_out is the incoming data, and λ_in is the outgoing data. After a certain point in time, as we try to send more, the amount of incoming data decreases, and ultimately it converges to zero. This network congestion results in packet loss, where packets are dropped, and the time those packets occupied the link, along with the time spent buffering, are all resources. All those resources become wasted. Consequently, packet loss due to congestion can be considered to have a significant overhead. Even if packets are not dropped but result in a timeout, TCP responds with retransmission due to error control. Therefore, from the receiver's perspective, duplicate packets are received twice.

One will eventually be discarded, which will result in increased overhead. This is where congestion control comes into play. Congestion control can be described as a method of managing congestion from a more macro perspective. In comparison to flow control, which is simply a way to adjust the transmission speed between the sender and receiver, congestion control is about preventing congestion from the perspective of routers and the network. 

To elaborate, flow control is the method of adjusting the transmission speed using a window to prevent buffer overflow at the receiving end, while congestion control aims to prevent packet loss when network conditions are poor. Now, in order to control congestion, it is necessary to detect it, right? There are several methods for detection, one of which involves measuring throughput. If the throughput significantly drops at a specific point in time, this indicates that congestion has occurred.

It would be good to organize the terminology, especially since RTT will come up later, so it would be beneficial to understand it better. RTT stands for Round-Trip Time, which refers to the time it takes for a network request to travel from the starting point to the destination and back again. cwnd represents the size of the window, and MSS is a value that is generally fixed at 1460. 

Now, the throughput of TCP can be calculated as (cwnd * MSS) / RTT. If you recall the formula for speed, which is distance divided by time, it might be a bit easier to understand. So, by measuring the throughput every hour and comparing the best throughput with the current throughput, if I find that my current value is significantly lower, I can conclude that there is congestion. This is the method used by TCP Vegas. 

In other implementations, a timeout and three duplicate acknowledgments are used. A timeout can be considered the worst-case scenario where packets are completely lost.

When a duplicate acknowledgment is received, there is some loss, but from the recipient's perspective, the acknowledgment sent to me has arrived properly, so we can say that the network is in a somewhat acceptable condition. This method is somewhat special; it's called ECN (Explicit Congestion Notification), where the router intervenes and directly informs the sender. Here, we use the IP header flags and such, but due to time constraints, I'll skip over that. In the scenario, the router detects congestion in the middle and sets the CE field in the IP header. From the recipient's perspective, they set the ECE field in the TCP header and send it back. This operation is why ECN is considered an indirect notification method through intermediaries. Similarly, in TCP congestion control, a window is used, and the basic concept remains the same, where the position and size information of cwnd is altered. The position moves one step to the right each time an acknowledgment is received, using the sliding window algorithm.

The size of the window is adjusted based on various congestion control methods, and since TCP is ultimately an interface, several standards exist. There are multiple standard methods, so let's briefly review them. The actual window size uses the smaller value between the window size determined by congestion control and the window size determined by flow control. There are various standards, but they generally control congestion in two stages, excluding Fast Recovery. Starting from Slow Start, since I do not know the state of the network, the idea is to begin with a window size of 1 and gradually increase it. It starts from 1 and increases by 1 with each acknowledgment received. This allows for the transmission of packets equal to the window size during one RTT.

As a result, once a round of RTT is completed, the window size will double, right? So, we are using an exponentially increasing method. If we increase exponentially, just after ten rounds, it exceeds 1,000. Therefore, we need to consider when to stop this increase. This is referred to as the Slow Start Threshold (ssthresh), which is the threshold for ending the Slow Start phase. In the event of congestion, it is set to half of the current window size where congestion occurred, and the window size is drastically reduced to 1, effectively returning to the Slow Start point. When the current window size exceeds the threshold, it is judged that we have reached near the network capacity, and we gradually increase the window size. If we look closely at this gradual increase method, it involves increasing by one unit at a time, while the decrease is done sharply. The same applies when an acknowledgment is received.

The congestion window (cwnd) is increased, but now it is not increased by one each time. Instead, it is increased by 1 divided by the current window size, so that effectively, the window size only increases by one each round. When a timeout occurs and packets are lost, the MD process is performed to significantly reduce the window size. If we look at the graph in the upper right, we can get a better understanding of how this operates. In TCP, which employs this AIMD method, the graph takes on a sawtooth shape, so when measuring throughput, it is usually measured by multiplying by three-quarters. Lastly, there is the Fast Recovery stage. This can be seen as a response to the idea that AIMD is slow, questioning whether it is necessary to reduce the cwnd to one when the network is slightly better. A standard for determining less congestion would be needed. Earlier, there were mentions of timeouts and duplicate acknowledgments.

which situation is less congested? Right? A situation with duplicate acknowledgments is slightly better. If we think about the meaning of this in detail, it refers to a situation where packets sent from the sender to the receiver are lost, but the acknowledgment sent from the receiver back to the sender is successfully transmitted. Now, when such duplicate acknowledgments occur, the ssthresh value is set to half of the window size as before, but instead of reducing the window size to 1, we adjust the ssthresh value to ssthresh + 3, considering the meaning of these three duplicate acknowledgments. Additionally, when duplicate acknowledgments are received, the window size is increased by 1. Normally, left and right would move together as they slide, but since I am still blocked by packets for which I have not yet received acknowledgments, I need to send one more. Therefore, it is good to think of it as increasing that space. Ultimately, when congestion is resolved,

When a corresponding acknowledgment is received in sequence, the inflated window size is finally reduced. By setting the threshold value we configured earlier as the window size, after escaping the Fast Recovery phase, the overall window size becomes exactly half of the window size during congestion. I meticulously plotted the graph, and in the 14th round, I received three duplicate acknowledgments. The previous ssthresh was 8, so now ssthresh is set to 14 divided by 2, which equals 7. While cwnd is reduced to 1, it is then set to 7 + 3, resulting in 10. However, since it has not yet resolved, when I receive another duplicate acknowledgment, I increase the window size by 1, making cwnd equal to 10 + 1, which is 11. Finally, when congestion is resolved and I receive a new (correct) acknowledgment, I substitute this cwnd value into the ssthresh value of 7 that was just set.

The window size is set to 7, which is half of 14. Now, we need to compare the performance, right? We have Tahoe and Reno. TCP Tahoe does not apply Fast Recovery. If you look at the orange graph, you can see that congestion occurred at an RTT of 14, but the MD process was applied, reducing the window size to 1. After that, it went through Slow Start and increased exponentially, but after four rounds, at RTT 18, we can see that the throughput becomes the same as TCP Reno. On the other hand, as we just saw, in the case of Reno, congestion occurred at 14, but with Fast Recovery applied, we can see that it does not drop below this threshold value as long as there is no timeout, regardless of what happens. Finally, there is a TCP that adjusts the transmission rate using AIMD and still feels slow with Fast Recovery! This TCP suggests not to increase linearly but to increase it as a cubic function!

I brought the graph of y = x^3, and by utilizing the properties of odd functions, we use a method that increases the window size only slightly to avoid congestion, and then sharply increases it the moment the congestion is resolved. In this graph, you can think of the origin as the point in time when congestion previously occurred. The reason I brought this up is that it is currently adopted as the standard TCP in Linux. As a side note, it was developed by two Koreans and can be said to be the TCP still in use today. Thank you for your hard work.

[10분 테코톡] 페드로의 TCP 제어 기능

우아한형제들의 기술조직 이야기를 전하는 우아한테크입니다.

우아한형제들 https://www.woowahan.com/
우아한테크 Facebook https://www.facebook.com/woowahanTech
우아한형제들 기술블로그 https://techblog.woowahan.com