Shulou(Shulou.com)06/01 Report--

How to understand TCP congestion control algorithm, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

  recently spent some time learning the TCP/IP protocol, the first reason is that my long-term knowledge of TCP/IP is limited to three handshakes and four breakups, so I want to know more about it. In addition, many designs at the TCP/IP and Linux system levels can be used in middleware system architectures, such as TCP congestion control algorithms can also be used in response time to limit the flow of middleware. On a deeper level, basic knowledge and rationale technologies such as TCP/IP are tested for a long time and are the crystallization of the wisdom of our predecessors, which can give you a lot of inspiration and help.

There will be some abbreviations in the   text, because of the space problem, it is impossible to explain all of them. If you don't understand what it means, please search for it yourself and be a person who actively seeks knowledge.

There are two important control algorithms in   TCP protocol, one is flow control, the other is congestion control.

  TCP protocol controls the flow by sliding the window, which controls the sending speed of the sender so that the receiver can receive and process it in time. Congestion control acts on the overall network, it is to prevent too many packets from being sent to the network, to avoid excessive network load and network congestion.

  congestion algorithm needs to master its state machine and four algorithms. There are five states of congestion control state machine, which are Open,Disorder,CWR,Recovery and Loss. The four algorithms are slow start, congestion avoidance, algorithm when congestion occurs and fast recovery.

Congestion Control State Machine

Like TCP,   has its own state machine for congestion control algorithms. When the sender receives an ACK, the Linux TCP determines its next behavior through the state machine, whether it should reduce the cwnd size of the congestion window, or keep the cwnd unchanged, or continue to increase the cwnd. If not handled properly, it may result in packet loss or timeout.

1 Open statu

The   Open state is the default state of the congestion control state machine. In this state, when the ACK arrives, the sender adjusts the congestion window according to the slow start or congestion avoidance algorithm according to whether the congestion window cwnd (Congestion Window) is less than or greater than the slow start threshold ssthresh (slow start threshold).

2 Disorder statu

  when the sender detects DACK (repeat acknowledgement) or SACK (selective acknowledgment), the state machine transitions to Disorder state. In this state, the sender follows the principle of in-flight packet conservation, that is, a new packet is sent only after an old packet leaves the network, that is, after the sender receives the ACK of the old packet, a new packet will be sent.

3 CWR statu

When the   sender receives a display congestion notification, it does not immediately reduce the congestion window cwnd, but reduces one segment for every two ACK received until the window size is halved. When cwnd is decreasing and there are no retransmitted packets in the network, this state is called CWR (Congestion Window Reduced) state. The CWR state can be transformed into a Recovery or Loss state.

4 Recovery statu

  enters this state when the sender receives enough (recommended three) DACK (repeat acknowledgements). In this state, the congestion window cnwd reduces one segment (segment) for every two ACK received until the cwnd is equal to the slow start threshold ssthresh, which is half the size of the cwnd when it first enters the Recover state. The   sender maintains the Recovery state until all the data segments being sent are successfully confirmed when entering the Recovery state, and then the sender returns to the Open state, and the retransmission timeout may interrupt the Recovery state and enter the Loss state.

5 Loss statu

  when a RTO (retransmission timeout) expires, the sender enters the Loss state. All the data being sent is marked as lost, the congestion window cwnd is set to a segment (segment), and the sender increases the congestion window cwnd again with the slow start algorithm.

The difference between   Loss and Recovery state is that in Loss state, the congestion window increases after the sender is set to one segment, while in Recovery state, the congestion window can only be reduced. The Loss state cannot be interrupted by other states, so the sender can return to the Open state only after all the data being transmitted at the beginning of the Loss has been successfully confirmed.

Four algorithms

  congestion control mainly includes four algorithms: 1) slow start, 2) congestion avoidance, 3) congestion occurrence, 4) fast recovery. These four algorithms were not developed in one day. The development of these four algorithms has gone through a lot of time, and they are still being optimized today.

Slow Hot start algorithm-Slow Start

  's so-called slow start, that is, the TCP connection has just been established, speed up bit by bit, to test the bearing capacity of the network, so as not to directly disturb the order of the network channel.

  slow start algorithm:

1) initialize the cwnd size of the congestion window at the beginning of the connection, indicating that a MSS-sized data can be passed. 2) whenever an ACK,cwnd size plus one is received, it increases linearly. 3) whenever a round-trip delay time RTT (Round-Trip Time) is passed, the cwnd size doubles directly, multiplied by 2, and increases exponentially. 4) there is also a ssthresh (slow start threshold), which is an upper limit. When cwnd > = ssthresh, it will enter the "congestion avoidance algorithm" (we will talk about this algorithm later).

Congestion avoidance algorithm-Congestion Avoidance

  as mentioned earlier, when the congestion window size cwnd is greater than or equal to the slow start threshold ssthresh, it enters the congestion avoidance algorithm. The algorithm is as follows:

1) if an ACK is received, then cwnd = cwnd + 1 / cwnd 2) whenever a round-trip delay time has elapsed, the RTT,cwnd size is increased by one.

After the   has passed the slow start threshold, the congestion avoidance algorithm can avoid window congestion caused by window growth too fast, but slowly increase the adjustment to the optimal value of the network.

Algorithm in congestion state

  generally speaking, TCP congestion control defaults to the idea that network packet loss is caused by network congestion, so general TCP congestion control algorithms take packet loss as a signal that the network enters a congested state. There are two ways to determine packet loss, one is timeout retransmission RTO [Retransmission Timeout] timeout, and the other is receiving three repeat acknowledgement ACK.

  timeout retransmission is an important mechanism for TCP protocol to ensure data reliability. Its principle is to start a timer after sending a data. If you do not get the ACK message to send the Datagram within a certain period of time, the data will be re-sent until it is sent successfully.

  but if the sender receives more than 3 duplicate ACK,TCP, it realizes that the data has been lost and needs to be retransmitted. This mechanism does not need to wait until the retransmission timer expires, so it is called fast retransmission, and after fast retransmission, it does not use slow start algorithm, but congestion avoidance algorithm, so this is also called fast recovery algorithm.

  timeout retransmits RTO [Retransmission Timeout] timeout, TCP retransmits the packet. TCP thinks the situation is bad and the reaction is strong:

Due to packet loss, the slow start threshold ssthresh is set to half of the current cwnd, that is, ssthresh = cwnd / 2.

Cwnd resets to 1

Enter the slow start process

The earliest TCP Tahoe algorithm of   uses the above processing method, but because everything starts all over again as soon as the packet is lost, the cwnd is reset to 1, which is not conducive to the stable transmission of network data.

  so the TCP Reno algorithm is optimized. When three repeat acknowledgement ACK are received, TCP enables fast retransmission of Fast Retransmit algorithm instead of waiting for RTO timeout to retransmit:

The cwnd size has shrunk to half of its current size

Ssthresh is set to the reduced cwnd size

Then go to the fast recovery algorithm Fast Recovery.

Fast recovery algorithm-Fast Recovery

  TCP Tahoe is an early algorithm, so there is no fast recovery algorithm, while the Reno algorithm does. Before entering the fast recovery, cwnd and ssthresh have been changed to half of the original cwnd. The logic of the fast recovery algorithm is as follows:

Cwnd = cwnd + 3 * MSS, plus 3 * MSS is due to the receipt of 3 duplicate ACK.

Retransmits the packet specified by DACKs.

If you receive another DACKs, the size of the cwnd increases by one.

If a new ACK is received indicating that the retransmitted packet is successful, exit the fast recovery algorithm. Set cwnd to ssthresh and enter the congestion avoidance algorithm.

  as shown in the figure, the fifth packet is lost, which causes the receiver to receive three repeat ACK, that is, ACK5. So set the ssthresh to half of the cwnd at that time, that is, 6 stroke 2 = 3 menagercwnd set to 3 + 3 = 6. Then retransmit the fifth packet. When a new ACK, ACK11, is received, it exits the fast recovery phase, resets cwnd to the current ssthresh, which is 3, and then enters the congestion avoidance algorithm phase.

  this article briefly describes some mechanisms of TCP congestion control, but these congestion controls still have many defects and need to be optimized, and the industry is constantly introducing new congestion control algorithms, such as Google's BBR.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.