Congestion Management: Queuing Algorithms

There are many different types of queuing algorithms, though not all may be suitable in modern networks that can carry many different media types.

FIFO – First In, First Out

The first packet to be placed on an output interface is the first packet that will leave that interface. All traffic belongs to the same class in first in, first out queuing.

RR – Round Robin

Queues are serviced in sequence one after the other, each queue will process one packet only. There are no queue starvation with round robin since every queue gets an opportunity to send a packet at every round. No queue has a priority over others, and if the packet sizes from all queues are around the same in length, bandwidth is shared equally. There is no mechanism to prioritise traffic in round robin.

WRR – Weighted Round Robin

Weighted round robin can provide prioritisation to the round robin queuing algorithm. It allows a weight to be assigned to a queue, and based on that weight the queue gets a proportionate share of the interface bandwidth that may be more or less than the other queues

CQ – Custom Queuing

Custom Queuing is Ciscos implementation of the weighted round robin algorithm. It creates a set of 16 queues with a round robin scheduler with first in first out on each queue.

Each queue can be customised with a portion of the link bandwidth for each selected traffic type. If there is a portion of the reserved link bandwidth unused, other queues can utilise that unused bandwidth. Custom queuing can suffer from long delays, and suffers from foundational issues of first in first out.

PQ – Priority Queuing

Priority queuing creates four queues assigned to different priorities, high, medium, normal, and low. There is first in, first out queuing within each queue. The high-priority queue always gets served first, and lower priority queues are served once the higher priority queues are empty.

If a packet arrives at any time during a lower priority queue being serviced, it is stopped and the higher priority queue is cleared before resuming any lower priority queue.

If a higher priority queue is always being serviced, the lower priority queues can suffer from starvation.

WFG – Weighted Fair Queuing

The weighted fair queuing algorithm divides the interface bandwidth by the number of flows, weighted using IP Precedence, to allocate bandwidth fairly among all flows. The WFG method provides good service for high priority real time flows, but it can not provide a fixed bandwidth guarantee for a particular flow.

CBQFG – Class-based Weighted Fair Queuing

One of the two algorithms recommended for modern networks. Class based weighted fair queuing allows up to 256 queues to be created, serving a certain traffic class. The queue is serviced dependant on the bandwidth that has been assigned to that class. Weighted fair queuing functionality is extended to support these user-defined traffic classes.

Packet classification is done in this queuing algorithm by looking at traffic descriptors such as quality of service markings, protocols, access control lists and input interfaces.

Once a flow has been classified by its traffic descriptors, it can be assigned specific amount of bandwidth, weight, a queue limit and a maximum packet limit.

The bandwidth that is assigned to a class is a minimum amount of bandwidth that will be provided to that class during periods of congestion on the interface.

The queue limit for the class is the maximum number of packets allowed to be buffered in that class queue.

If the queue reaches the configured packet limit, excess packets will be dropped.

There is no guarantee to low latency using this algorithm, so is not suitable for real time flows such as audio and video calls.

LLQ – Low Latency Queuing

Low latency queuing is the other recommended algorithm for modern networks, and combines class-based weighted fair queuing with priority queuing. It makes up for the disadvantage CBQFG faces with real time traffic by guaranteeing a lower latency and bandwidth

Traffic assigned to the strict-priority queue is serviced up to its assigned bandwidth before other CBWFG queues are serviced.

Real time traffic must be assigned to the strict-priority queue in order for packets to move quickly.

There can be multiple classes defined for servicing real time traffic with separate bandwidth guarantees on each, but there is a single priority queue that combines all of these classes together to be serviced first.

If there is a traffic class not utilising its bandwidth assigned, it can be used by other classes.

If there is congestion on the link, real time traffic that goes beyond its assigned bandwidth will be policed to ensure that non-priority traffic is not starved. The policing rate must be specified as a fixed amount of bandwidth or as a percentage of interface bandwidth




Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.