Network congestion
lastmod 2018-08-17created 2017-01-262 edits
Congestion control refers to regulating the amount of traffic entering a telecommunications network so that the network does not become congested. For example, detecting excessive traffic and sending fewer packets can prevent congestion collapse.
TCP congestion control
TCP congestion control was introduced by Van Jacobson in the 1980s. In the Internet environment of that time, congestion collapse was a major problem. To send data quickly, each host sent the maximum number of packets it could within a given time, and congestion occurred at some routers, which could not process all the packets received within that time. When packets were not processed within the given time, hosts retransmitted them, so routers received even more packets and the congestion grew worse..
TCP congestion control works by having the sender determine the network's capacity. The sender knows how many packets it can safely send, and receives an ACK packet when a packet arrives successfully. That is, receiving an ACK packet tells the sender that a previously sent packet arrived, and once it receives an ACK it can safely send more new packets; this is why TCP congestion control is called self-clocking. Of course, knowing the network's capacity from the start is difficult. To make matters worse, network capacity changes from moment to moment. This means the sender must adjust its transmission rate according to network conditions.
Additive increase/multiplicative decrease
This method is called AIMD (Additive Increase/Multiplicative Decrease). It starts by sending one packet at a time, and if packets arrive without problems, it increases the window size (the number of packets sent per unit of time) by 1 as it transmits. If a packet transmission fails or a set time is exceeded, the sending rate is cut in half.
This method is fair. When several hosts using this method share a network, a host that joins later is at a disadvantage at first, but over time they converge to an equilibrium.
The problems are that it takes a long time at the start because it cannot use the network's high bandwidth, and it cannot detect in advance that the network is becoming congested. In other words, it reduces bandwidth only after the network has become congested.
Slow start
Additive increase/multiplicative decrease works efficiently around the network's capacity, but has the drawback that it takes too long to ramp up the transmission rate at the start. Slow Start, like additive increase/multiplicative decrease, starts by sending one packet at a time. However, if packets arrive without problems, it increases the window size by 1 for each ACK packet. That is, after one round the window size doubles. So unlike additive increase/multiplicative decrease, the transmission rate grows exponentially. Instead, when congestion occurs, the window size drops to 1. At first there is no information for estimating the network's capacity, but once congestion has occurred the capacity can be estimated to some degree, so the window size is increased exponentially as before up to half the window size at which congestion occurred, and after that it is increased gently by 1.
One might think it odd that a method which rapidly increases the window size exponentially at the start is called slow start. However, slow start should not be compared to linear increase, but to how TCP behaved when slow start was invented. Earlier TCP started by sending as many packets as it possibly could, whereas slow start instead starts the window size at 1 and increases it exponentially to probe the network's capacity.
This method is more efficient than additive increase/multiplicative decrease, but likewise, when congestion occurs, there is a large time gap while waiting for a timeout.
Fast retransmit
Fast Retransmit is a policy added to TCP congestion control. The receiver sends an ACK packet even when a packet that should have arrived first has not arrived and the next packet arrives instead. However, the ACK packet carries the sequence number of the packet following the last packet that arrived in order. So if one packet in the middle is lost, the sender receives ACK packets with duplicate sequence numbers, and as soon as it detects this it can retransmit the packet with the problematic sequence number. Fast retransmit retransmits after receiving 3 packets with duplicate sequence numbers. And since this indicates mild congestion, it detects congestion and reduces the window size.
Fast recovery
Fast Recovery is a method that, on congestion, halves the window size instead of reducing it to 1, and then increases it linearly. With fast recovery applied as well, after experiencing congestion once, it operates as pure additive increase/multiplicative decrease.
TCP Reno implements all three: slow start, fast retransmit, and fast recovery, and the Microsoft Windows operating system also works this way.
Congestion collapse in China
The 'congestion collapse' phenomenon disclosed by Nettention basically occurs when data packets are lost due to router problems during data transmission. It is a conflict that arises when UDP (user datagram protocol) and TCP (transmission control protocol) are used together. It happens because UDP, which aims to send a lot quickly even if data is lost, completely eats up the traffic of TCP, which sends data in order and adjusts its rate when data is lost. This is known to be a characteristic of the local network infrastructure itself, not a C/S or P2P problem.