2. Problem Description
An increase in exchanging data and sharing computing resources over the Internet can lead to severe congestion problems. As a result, gateways such as routers drop packets when their storage is full.
TCP handles the congestion problem through the timeout and retransmission methods. Assuming packages have gone missing and retransmitting them can result in overflooding the network and a congestion collapse.
Therefore, we need a congestion control algorithm that can manage these problems.
3. What Does TCP DUP ACK Mean?
In the previous congestion control algorithms, a packet is considered non-received as soon as its timer expires.
Is there another way to find out if the packet is lost? The answer is: yes, by sending a duplicate acknowledgment packet.
A duplicate acknowledgment packet is a packet the receiver sends to the network to inform the sender that it has accepted a new out-of-order segment. So, the packet with the sequence number mentioned in the duplicate acknowledgment is the non-received packet.
The non-received packet is either lost or rearranged in sequence by the network. A network router can rearrange segments. For example, the router can send large segments before smaller ones.
Both the fast retransmit and fast recovery algorithms (used in congestion control) use duplicate acknowledgment packets.
3.1. Fast Retransmit
The fast retransmit algorithm watches out for duplicate acknowledgment packets, so it can send the lost packet without waiting for the timer to expire. Hence, this advances the recovery of the missing segment.
When a duplicate acknowledgment arrives at the sender, the sender first assumes there was a packet re-ordering. Furthermore, the sender assumes the packet will arrive soon at the receiver’s side. After that, the sender concludes that the packet is most likely lost once it receives the third duplicate acknowledgment. Consequently, the sender will send the lost packet again.
3.2. Fast Recovery
Fast recovery is an improvement of the slow start algorithm. The slow start algorithm came along to prevent congestion at routers. In brief, the sender only sends an extra packet to the network after receiving an acknowledgment. The maximum allowed number of packets it can send (window) increases exponentially when it receives an acknowledgment. Moreover, the slow start algorithm runs at the start of traffic transmission and after congestion. On the other hand, fast recovery tries to keep the data flow and not abruptly decrease the window size.
The fast retransmit takes place upon the receipt of the third acknowledgment packet. So, a slow start is no longer called after the third acknowledgment. Fast recovery is called instead.
3.3. Fast Retransmit With Fast Recovery Algorithm
The fast-retransmit and the fast-recovery methods can work together to improve the network throughput during congestion:
The congestion window () is the amount of data the sender can send into the network before receiving an acknowledgment. In addition, is the slow start threshold. It determines whether the slow start or the congestion avoidance algorithm is used and sets a ceiling to the slow start.
The if-statement checks whether the duplication acknowledgment received is the third duplicate acknowledgment and sets the and values accordingly.
Otherwise, the nested if-statement checks if the currently received acknowledgment packet is a duplicate acknowledgment. If so, the value changes, and a new segment is sent to the network. If not, is set to , and the node moves to the congestion avoidance state. The congestion avoidance state aims to minimize traffic by setting by .
Let’s work out an example based on an article on fast retransmitting and recovery.
First, we assume that socket initialization and the three-way handshake have already happened. Additionally, the TCP connection has begun a slow start, and the congestion window is 5000 bytes.
Now, the client decides to send 3K bytes of data. The data is split into six TCP segments. Five TCP segments reach the network router successfully. The segment with sequence number 223012 drops off due to network congestion:
Afterward, the network router sends the segment with sequence number 222500 to the receiver. The receiver accepts it and sends it to the higher layer. Then, the network router sends the segment with sequence number 223564 to the receiver.
The receiver realizes that this is an out-of-sequence segment and buffers it. Also, the receiver sends an acknowledgment packet for the lost segment 223012. It keeps sending the same acknowledgment packet after receiving each remaining segment from the sender:
The router forwards the acknowledgment packets to the sender. Consequently, the sender considers the second acknowledgment packet with sequence number 223012 a duplicate acknowledgment. Then, the sender moves to the fast retransmit state and waits for further acknowledgment packets with the same sequence number.
After some time, the sender receives the third duplicate acknowledgment packet. It concludes that packet 223012 has gone missing. Therefore, the sender changes the value to half the window size and sends the lost packet again:
The sender’s window size is set to . Subsequently, the window size increased by one after each received acknowledgment packet. Following this, the sender receives an acknowledgment for all the segments in the receiver’s buffer.
At this point, the sender sets the window size to and moves to the congestion avoidance state.
In this article, we described the congestion problem in networks and various congestion control algorithms. Then, we explained how a duplicate acknowledgment packet is a signal that there could be a lost packet.
A lost packet is an indicator of congestion. So, congestion control algorithms rely on the detection of such packets.