In the interview, I was asked how the reliability of TCP is guaranteed?

We know that TCP is reliable. Our previous article explained data transmission after three handshakes and four waves. They are based on the sequence number mechanism and the confirmation response mechanism. If the reliability of this mechanism is to be guaranteed, some other assistance is needed. The reliability guarantees of TCP include: retransmission mechanism, sliding window, flow control, congestion control, etc.

1. Retransmission Mechanism

The reliability of TCP depends on the sequence number mechanism and the confirmation response mechanism. That is, when one end sends data to the other end, the other end will reply with an ACK packet to ensure that the data is sent successfully. In this process, two things may happen:

• One is that the data packet does not reach the receiving end because the data is lost or delayed;
• One is that the ACK packet did not reach the sender, also because of loss or delay.

In the former case, the data has not reached the receiving end, while in the latter case, the data has reached the receiving end, but the reply ACK packet is lost and has not reached the sending end.

TCP uses a retransmission mechanism to solve the problems of packet loss and repeated transmission. Retransmission in TCP includes timeout retransmission, fast retransmission, SACK and D-SACK.

1. Timeout retransmission

As the name implies, data will be resent if no reply is received within a certain period of time. It is difficult to determine the timeout retransmission time RTO here. This time is not appropriate if it is too large or too small. It should be slightly longer than the RTT time for a data packet to go back and forth. However, the RTT time for a data packet to go back and forth is not fixed and will be affected by network fluctuations. Therefore, the RTT time is calculated based on the weighted average of several round-trip times and the fluctuation range of the RTT, and the RTO is converted based on this through some coefficients.

2. Fast retransmit

Although there is timeout retransmission, it would be too slow to wait until some data packets actually time out before retransmitting them. Therefore, Linux also has a retransmission mechanism called fast retransmission.

The principle is: when the sender sends a data seq2, it fails to get an ack data packet returned. At this time, if several data seq3, seq4, seq5, and seq6 are sent successively, and the ack data packets received in the following times are ack2, ack2, ack2, ack2, it means that the receiving end has received the data before seq2, but seq2 has not been received yet. The fast retransmission mechanism is that if the sending end sends multiple data, but the sequence number of the reply packet of each data packet is the same, for example, in this example, the data packets returned by seq3, seq4, seq5, and seq6 are all ack2, and the 2 refers to the sequence number, indicating that the sequence number of the largest data missing from the receiving end is 2. The sending end should send seq2. If there are three consecutive ack2s, TCP will determine that seq2 needs to be resent. This situation can solve the problem of long waiting time for timeout retransmission, but the new problem is that the sending end does not know whether to resend seq2 or seq3, seq4, seq5, and seq6. Different versions of Linux have different implementations in this case.

3. sack

The above problem has been raised. How will Linux solve it later? Sack is introduced. The value of this field will be placed in the option field of the TCP header. In the case of the above example, the receiving end will reply with an ack and a sack each time it receives a request. The part between these two values ​​is the data currently missing from the receiving end, that is, ack<=x<sack. x is the missing part of the data. The sequence number of this part of the data starts with ack and ends with sack-1. In this way, the sending end can know which part of the data is missing from the receiving end, and the sending end only needs to resend the data.

4.d-sack

There is another situation where the data sent by the sender is delayed in the network but not lost. After the sender retransmits, the delayed data arrives again, which causes repeated transmission. In this case, the d-sack method is used. dsack is actually a way to use sack to process duplicate data. The receiving end still replies ack+sack, but sack indicates the sequence number of the current repeated data, and ack indicates the sequence number to be received, so that the sender can know that the data has been sent.

It is not difficult to find that the two modes can be distinguished by comparing the size of ack and sack. If ack is greater than sack, it means that the data is sent repeatedly. If ack is less than sack, it means that the data is missing.

2. Sliding Window

TCP uses a confirmation response mechanism to ensure reliability. In theory, the sender sends a piece of data to the receiver, and the receiver replies with a response data after receiving it. Only then will a conversation end, and then the sender will send the next piece of data.

This method is undoubtedly an extremely inefficient method, so in order to achieve reliability and efficiency, TCP introduces sliding windows and flow control

TCP introduced the concept of sliding window. The sliding window means that the receiving end and the sending end set aside a space for each socket. The data from the sending end can only be processed when the sliding window on the receiving end is free.

Principle: Each time the sender sends data to the receiver, the receiver returns a sliding window size, which indicates the maximum number of bytes that the receiver can accept. After receiving this sliding window size, the sender can send multiple data packets continuously as long as they are within the sliding window range.

The sender's sliding window has the following areas:

• Sent but no reply received yet
• Unsent Area

When the sent data is replied, the sliding window moves right.

The sliding window on the receiving end has the following areas:

• Received but not yet taken by the application
• Areas not yet received

If the received data is taken away by the application, the window moves right.

If the ACK of one of the data packets sent by the sender within the sliding window is lost, it does not necessarily need to be resent. The sender can determine whether the lost ACK packet needs to be resent through the next ACK. In other words, with the concept of sliding window, it is not necessarily necessary to resend the ACK reply packet when it is lost.

The window size of the sender is determined by the receiver.

3. Flow Control

The concept of sliding window allows multiple data packets to be sent at a time, solving the problem of low efficiency of processing only one data packet at a time. However, because the processing capacity of the receiving end is limited, the sending end cannot continuously send data to the receiving end. If the data flow is large and the receiving end cannot process it, it can only discard the data, so there must be a mechanism to control the data flow.

TCP's flow control is precisely based on the sliding window. The sliding window is sent to the sending end after confirmation by the receiving end. The sending end sends data according to the window size, which can ensure that the sent data can be received and processed at the receiving end.

However, TCP considers the following issues when implementing flow control based on sliding windows:

The sliding window is a space in the socket buffer. The buffer corresponding to the socket is not fixed, so if the buffer changes, it will have some impact on the synchronization of the sliding window. For example, the receiving end notifies the sending end that the window size is 100, but at this time the operating system reduces the socket buffer to 50. If the received data is greater than 50, the packet will be dropped and packet loss will occur.

There is another problem, the confused window problem. For example, because the receiving end processes slowly, the sliding window is 0 and the window is closed. After a period of time, there may be 50 bytes of free space in the window. At this time, the window = 50 will be notified to the sending end. After the sending end receives the window = 50, it will send 50 bytes of data. However, no matter how much data is sent, TCP will add a TCP header to the data packet, which has 20 bytes. At the same time, it also has an IP header, which is also 20 bytes, a total of 40 bytes, while the data sent is only 10 bytes, which is extremely low in cost performance. It also occupies bandwidth.

TCP has to consider the above problems when implementing flow control based on sliding windows. How does TCP solve it?

TCP does not allow reducing the buffer size and window size at the same time. If you need to reduce the buffer size, you must first reduce the window size and then reduce the buffer size after a period of time.

To solve the problem of confused windows, we must avoid the receiver from replying with a smaller window to the sender and avoid the sender from sending small data packets.

TCP stipulates that the receiving end must close the window (reply to the receiving end that the window is 0) when the window size is <min(mss, half of the buffer), so that the receiving end will not send a small window to the sending end.

The sender also needs to solve the problem of sending small data. The sender uses the Nagle algorithm to perform delay processing, that is, it can only send when one of the following two conditions is met:

• The window size is larger than mss or the data size is larger than mss
• Receive the ack of the previous data send reply

As long as one of the two conditions is met, the data can be sent. However, once this algorithm is enabled, some packets with very small data will not be sent in time, so it is necessary to consider carefully when enabling this algorithm.

TCP relies on the above mechanism to implement flow control. The specific process is that the receiving end will reply the window size to the sending end every time. When the receiving end is very busy, the window may become smaller to 0, and the sending end will be notified that the window is closed. At this time, the sending end will no longer send data to the receiving end. When the receiving end window becomes larger, it will actively reply to the sending end's window size.

However, this reply may be lost, then there will be a problem of waiting for each other, which can be understood as a deadlock. The solution of TCP is to define a clock, which is a timer. When a certain period of time passes and the receiving end has not notified the window, the sending end will send a probe message, usually once every 30-60 seconds, and sent three times (this may be different for different implementations and can be configured). If the window is replied, it will start sending data. If the replied window is still 0, the clock will be reset and the timing will be restarted. If the window is not opened in the end, the sender may send a RST packet to the server to terminate the connection.

4. Congestion Control

The sliding window and flow control ensure that when the receiving end is busy, the data will not be discarded because there is nowhere to put it.

However, the network is shared and may be very busy. If the network is congested, packet loss may occur. TCP will retransmit when it does not receive an ACK, making the network more congested and causing more data loss, which will make the entire network environment worse.

TCP proposed congestion control to solve the problem of data loss caused by network congestion.

Two concepts in congestion control mechanism: congestion window and congestion algorithm

First, let's look at what is considered congestion. TCP considers congestion as long as timeout retransmission occurs.

When TCP sends data, the size of the data sent is limited by the sliding window and congestion window, that is, the maximum amount of data that the sender can send is the minimum value of the congestion window and the sliding window.

Congestion Algorithm

(1) Slow start:

When the connection is just established, the sliding window and the congestion window are the same. Next, we assume that the initial values ​​of the sliding window and the congestion window are 100 bytes. The following descriptions are based on this assumption.

Slow start means that based on the initial value, the sender sends a 100-byte data packet to the receiver (the number of data packets is not considered here, the total number of bytes is used directly). When all acks are returned, the congestion window will be increased by 100. The next cycle is to add 200 to 200, and the next cycle is to add 800. The congestion window of this algorithm grows exponentially and very fast, so there must be a limit. This limit is called the congestion threshold value, which defaults to 65535 bytes. When the congestion window value reaches this value, it enters the congestion avoidance phase.

(2) Congestion avoidance:

When the congestion window value reaches the congestion threshold, it will enter the congestion avoidance phase. In this phase, for example, if the current congestion window value reaches 65535 bytes, if these 65535 bytes are sent out, when all acks are returned, 65535 bytes are added to the 65535 bytes, and then 65535 bytes are added again, and then 65535 bytes are added again. It is no longer an exponential growth, but a linear growth. To put it bluntly, the growth rate has slowed down. But even so, the congestion window value is in a growth state. So when will it end? The answer is when a timeout retransmission occurs.

(3) Congestion occurs:

When retransmission occurs, it means congestion has occurred. Congestion occurs because of retransmission. Retransmission is divided into timeout retransmission and fast retransmission. When timeout retransmission occurs, it means that the network is really bad. TCP sets the congestion threshold value to half of the congestion window value at this time, and sets the congestion window value to 1. Thus, it enters the slow start phase again. If fast retransmission occurs, it means that the network is not very bad. The congestion window value will be set to half of the congestion window value at this time, and the congestion threshold value will also be set to half of the congestion window value. If nothing is done at this time, it will enter the congestion avoidance phase. However, for this situation, TCP will enter the fast recovery algorithm.

(4) Quick recovery:

That is, add 3 to the current congestion threshold value to indicate the size of the congestion window. Then resend the failed data, add 1 after receiving the recovery, then send new data and enter the congestion avoidance phase.