This time I really understood congestion control
In computer networks, we hear the term congestion control over and over again. So what exactly is network congestion? What are the congestion control methods? After reading this article, I hope you can have a general understanding.
Concept of network congestion
First quote a section of Baidu Encyclopedia for network congestion explanation:
Network congestion refers to the degradation of network transmission performance due to limited resources of storage and forwarding nodes when too many packets are being transmitted in a packet-switched network. When a network becomes congested, there is data loss, increased latency, decreased throughput, and even “congestion collapse” in severe cases. Generally, network congestion occurs when the network performance deteriorates due to excessive load. The figure below shows how the network throughput changes with increasing input load with or without congestion control intervention.
From the above description, we can probably get the following information:
- Network congestion is often caused by requests for resources that exceed the capacity of store-and-forward nodes.
- Network congestion may cause data loss, increased latency, and decreased throughput.
- If congestion occurs and is not controlled, the entire network situation may deteriorate, or even the network throughput will be reduced to 0.
- Network congestion is closely related to the current network load.
Congestion control algorithm
Before describing congestion control algorithms, I would like to introduce the following differences between congestion control algorithms and flow control algorithms.
Similarities and differences
The biggest difference between flow control and congestion control is that they target different objects and solve different problems.
First, for flow control, it targets two hosts that are communicating. Through the dynamic changes of the sliding window to ensure that both sides can accept ability and the ability to send to match (receiver to inform the sender’s own cache size, from then on, control the sender send window size, so as to achieve the purpose of flow control, the receiver control sender), and unapt appear out of the cache, active packet loss. (PS: [Key points] 1. End-to-end communication. 2. Sliding Windows)
Congestion control is a global problem, because partial network congestion may cause data exchange congestion on the entire network and result in the breakdown of the entire network. You can only restart the network to solve the problem. This problem occurs because the storage and forwarding node cannot process other storage and forwarding requests because the demand for resources on the local network exceeds the processing capability of the node. As a result, other requests are resended due to timeout. As a result, more data may be injected into the network and the network may break down. Thus, congestion control involves all hosts, routers, and all the factors associated with reducing network performance. The object of congestion control is the sender, and it does not concern the size of the cache on both sides of the communication. The maximum number of packets sent by a source data stream in an RTT.
So that’s the difference between flow control and congestion control. Next, we need to introduce the following two parameters:
- Congestion window CWND
- Slow start threshold SSTHresh
The sender needs to maintain a state variable called congestion window CWND, whose value depends on the degree of network congestion and changes dynamically with the degree of network congestion. Maintenance principle of congestion window: If no congestion occurs on the network, the congestion window will increase continuously (the specific increase depends on SSthresh). But as soon as the network becomes congested, this window shrinks. The criteria for determining network occurrence are as follows: Timeout packet (if the packet is not received in time, it needs to be retransmitted timeout).
Upper limit of sender window = Min [RWND, CWND] (PS: RWND is the size of the receiving window)
Ssthresh is also a state variable to maintain when doing congestion control:
- When CWND < ssTHRESH, the slow start algorithm *** is used
- When CWND >= SSTHRESH, use congestion avoidance algorithm ***
Slow start
When the host starts to send data, if all data is injected into the network at a time, the network may be blocked. This is because at the beginning of the data transmission, the sender does not know the actual load of the network. Therefore, the best approach in this scenario is to first detect the current network conditions, and then try to increase the congestion window as appropriate. For example, when we are marching in battle, we usually do not choose to send large troops directly into an unfamiliar area. But will first send part of the scouts to reconnaissance, according to the feedback of the scouts, in the army slowly in batches into the. Generally, the congestion window CWND is set to a maximum packet segment (MSS) value at the beginning of the packet segment sending. Each time a new message segment is acknowledged, a maximum of one MSS value is added to the congestion window.
As can be seen from the figure above, the congestion window CWND doubles after each transmission round (power of 2 increases). The round trip time (RTT) of a packet is referred to here, but it is referred to here to emphasize that the whole process of transmission is to send all the data in the CWND and receive an acknowledgement of the last byte sent (representing that all the data sent before has been acknowledged). However, in order to prevent network congestion caused by excessive increase of congestion window, it needs to be restricted by ssthRESH state variable. That is, when CWND > SSTHRESH, congestion avoidance algorithm is used and slow start algorithm is disabled.
Congestion avoidance
Congestion avoidance algorithm is designed to slow down the increase of congestion window and control data injection. The congestion window CWND of the sender is increased by 1 for each transfer round instead of doubling. In this way, the CWND of the congestion window will grow slowly in accordance with the linear law.
With the slow start and congestion avoidance algorithms introduced, let’s look at how they work together: If the sender determines that the network is congested either in the slow start phase or in the congestion avoidance phase, ssTHRESH is set to half of the CWND of the current congestion phase, and the CWND of the congestion window is reset to 1. Execute a slow start algorithm. The goal is to quickly reduce the amount of data sent to the network by the host so that the congested router has enough time to process its own heap load.
The fast retransmission
Fast retransmission requires the receiver to respond immediately when it receives an out-of-order message, rather than waiting until it sends its own data to piggy-back acknowledgement (to prevent timeouts!!). . According to the fast retransmission algorithm, as long as the sender receives three consecutive repeated ACKS for the same data packet, it should immediately retransmit the packet segment that the other party has not received, without waiting until the REtransmission timer (RTO) times out (sometimes not due to network reasons). —-PS: The main reason for using fast retransmission is that the sender does not have timeout retransmission for individual packets lost due to non-network reasons. The sender can detect them early and retransmit them immediately, so that the network will not be mistaken for congestion. The fast retransmission algorithm can increase the throughput of the network by 20%.
Fast recovery
In the fast retransmission algorithm, once the sender receives three duplicate ACKS, it knows that only individual data packets are now lost. Therefore, the fast recovery algorithm is used instead of the slow start algorithm (packets are lost because an ACK reply is received, not because of network congestion). The process of fast recovery algorithm is as follows:
- The sender reduced the slow start threshold SSthRESH and the congestion window CWND by half.
- Execute congestion avoidance algorithm.
The following example shows the four algorithms used in the congestion avoidance process. I hope you can understand them carefully:
The above is the summary of TCP congestion control knowledge, I hope to help you.