roman10
1. Why Active Queue Management (AQM) Mechanism
Network bandwidth is shared by users. Users want to get as much bandwidth as possible. However, there’s always limited bandwidth. When the bandwidth cannot satisfy what everyone is trying to get, congestion might occur. That’s why there’re congestion avoidance algorithms implemented in TCP at the users’ end.
But we cannot simply rely on end hosts to avoid congestion. Although TCP is designed to avoid congestion, hackers might change TCP implementation to grasp more bandwidth than other users; And how about UDP? Although TCP takes most of the Internet traffic, UDP senders can send lots of traffic which congest the network. Therefore, gateway/routers are identified as the most appropriate place to detect and avoid congestion, and allocate bandwidth fairly.
There’re two types of algorithms have been studied related to congestion control at gateways: queue management algorithms and scheduling algorithms. Scheduling algorithms work by scheduling which packet from which flow is going to be processed by the gateway. In this way, it allocates bandwidth among flows. On the other hand, queue management algorithms manage the flows by managing the buffer at the gateway.
2. Drop Tail
Drop Tail is a simple active queuing management (AQM) algorithm used in many routers. It doesn’t differentiate traffic from different sources. As long as the queue is filled up, it will drop subsequent packets arrived. In other words, drop the tail of sequence of packets.
Drop Tail is simple and easy to implement, however, it suffers from a couple of drawbacks.
● It doesn’t distribute buffer space fairly. Because Drop Tail doesn’t differentiate traffic from different sources, sources with higher traffic volume will take more buffer space.
● If multiple TCP connections exist in the system and a buffer overflow will cause TCP global synchronization, which reduce the network throughput and utility significantly.
3. Random Early Detection (RED)
Random Early Detection or Random Early Drop (RED) is another AQM. It monitors the average queue size and take actions on packet (either drop or mark) based on statistical probabilities.
RED is designed with the following goals,
● Provide connection avoidance by controlling the average queue size
● Avoid TCP global synchronization
● Avoid bias against bursty traffic
● Maintain an upper bound on average queue size even the transport-layer protocols doesn’t cooperate.
In order to achieve the goals, RED operates in three regions. When the average queue size lower than th_min, all packets are accepted; when the average queue size is between th_min and th_max, RED drops or marks a packet by a probability, which is calculated based on the average queue size, and the number of packets transmitted since the last dropped/marked packet in this flow; When average queue size goes beyond th_max, all packets will be dropped/marked.
In this way, RED monitors the average queue size to detect congestion, drops/marks the packet randomly to avoid global synchronization, and allows fluctuations in the actual queue size to accommodate bursty traffic and transient congestion. In case the transport-layer protocol doesn’t cooperate, RED can be configured to drop packets to maintain an upper bound.
Below is a figure illustrates how RED works in detail,
Figure 1. How RED Works
References
1. Floyd, S. and Jacobson, V. 1993. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking.
If you enjoyed this article, please consider sharing it!
