Active Queue Management

Active queue management is an intelligent packet drop technique in side the NIC buffers, before the queue associated with that particular interface is full. It is an alternative to other methods such as using a tail drop queue, which waits until the queue is completely filled, and then the packet dropping starts.

Active queue management solves issues of bufferbloat and TCP global syncronization.

Bufferbloat

Bufferbloat is high latency caused due to queueing/buffering of packets. As the queue gets full, the buffering time increases, hence it is beneficial to drop packets to prevent the queue from getting full. This will eventually notify the sender to reduce the sending rate.

TCP Global Syncronization

When a packet burst in a single flow causes packets from all flows to be dropped is called TCP Global Syncronization. A flow refers to a flow of packets from a particular source to destination. The issue here is that even packets from perfectly steady flows may be dropped due to a burst in packets from another flow. An example is as follows, consider flows A, B and C. The queue is currently full, and all flows transmit packets at steady rates. But, say that now flow B experiences a sudden burst in packets. As a result, the queue overflows and packets from flows A, B and C have to be dropped. A and C are penalized due to B.

Another problem which might arise is when the sender reduces its sending rate for a certain amount of time, and then tries to find out if the network is no longer congested by increasing the rate again subject to a ramp-up. Almost all the senders will use the same time delay before increasing their rates. When these delays expire, at the same time, all the senders will send additional packets, the router queue will again overflow, more packets will be dropped, the senders will all back off for a fixed delay. This situation will occur repeatedly and leads to inefficient use of bandwith.

AQM Algorithms

RED (Random early detection)

Random Early Detection, or RED, is an active queue management algorithm for routers suited for congestion avoidance. In contrast to traditional queue management algorithms, which drop packets only when the buffer is full, the RED algorithm drops arriving packets probabilistically. The probability of drop increases as the estimated average queue size grows. RED responds to a time-averaged queue length, not an instantaneous one.

REDAlgorithm()  

  avg ← average queue size

  while packetsarrive

  	if(minth <= avg AND avg < maxth)

  		Compute pa  with probability pb

  		drop the arriving packet

  	else if  (maxth < avg)

  		drop the arriving packet

  	endif

end REDAlgorithm

RED algorithm contains two main sub algorithms (parts):

1. For computing the average queue size that determines the degree of burstiness that will be allowed in the routers queue.

2. For calculating the packet- dropping probability that determines how frequently the router drops packets, given the current level of congestion.

There exist variants of RED like Weighted RED, Adaptive RED etc.

CoDel

The theory behind CoDel is based on observations of packet behavior in packet-switched networks under the influence of data buffers. CoDel was developed as an attempt to address the problem of bufferbloat.

CoDel is a simple algorithm with no parameters. Thus, it overcomes the problem of RED.

Algorithm:

	100ms dropping interval set
	Queuing delay is calculated for each packet. (Dequeue time - Enqueue time)
	Lowest delay is maintained
	If lowest delay is greater than 5ms 
		drop last packet
		dropping interval is set to 100/root(2)
	Else
		dropping interval reset to 100	 

• Dropping Intervals are set as - 100 , 100/root(2) , 100/root(3) , 100/root(4) ... where 2,3,4,5... signify the number of packets dropped

PIE

PIE also aims to keep the benefits of RED: including easy implementation and scalability to high speeds. Similar to RED, PIE randomly drops an incoming packet at the onset of the congestion. The congestion detection, however, is based on the queueing latency instead of the queue length like RED. Furthermore, PIE also uses the derivative of the queuing latency to help determine congestion levels and an appropriate response.

PIE is comprised of three simple basic components:

• random dropping at enqueueing
• periodic drop probability update
• latency calculation

When a packet arrives, a random decision is made regarding whether to drop the packet. The drop probability is updated periodically based on how far the current latency is away from the target and whether the queuing latency is currently trending up or down. The queueing latency can be obtained using direct measurements or using estimations calculated from the queue length and the dequeue rate.

    Random Drop
         /               --------------
 -------/  -------------->    | | | | | -------------->
        /|\                   | | | | |
         |               --------------
         |             Queue Buffer   \
         |                     |       \
         |                     |queue   \
         |                     |length   \
         |                     |          \
         |                    \|/         \/
         |          -----------------    -------------------
         |          |     Drop      |    |                 |
         -----<-----|  Probability  |<---| Latency         |
                    |  Calculation  |    | Calculation     |
                    -----------------    -------------------



                  Figure 1. The PIE Structure