In the network communication, optimizing and managing queuing of packet flow is an important subject for network traffic management, quality of service (QoS), and resource allocation. A network device has a block of memory, called a buffer, which is used for a collection of packets waiting to be processed. Packets may arrive at queues in bursts from multiple devices, and a device may temporarily receive more packets than it can process. A waiting queue of packets therefore is formed in the buffer. If the device cannot catch up, buffers fill up and new incoming packets are dropped. This is called "tail drop." Many queuing methods and algorithms are introduced to solve these problems.
A queuing algorithm typically addresses the following questions:
- How are incoming packets placed into queues?
- What is the order and/or method use by the networking device to process its queues?
- What are the strategies for dealing with bursts of traffic and queues that overflow?
The following are a few popular queuing methods:
- First-In First-Out (FIFO) queuing - In this algorithm the first packet in the queue is processed first. When queues become full, congestion occurs and incoming packets are dropped. FIFO relies on end systems to control congestion via congestion control mechanisms.
- Priority queuing - This algorithm uses multiple queues and each queue has different levels of priority, with the highest priority queues being processed first. When congestion occurs, packets are dropped from lower-priority queues. The problem with this method is that lower-priority queues may not get serviced at all if high-priority traffic is excessive.
- Fair queuing - Under this model, multiple queues are allowed and a round-robin approach is used to service all queues in a fair way. This prevents any one source from overusing its share of network capacity. However packets are typically variable in length. If each queue is allowed to release one packet at a time, some queues will take more time – so it is not “fair”. A byte-oriented scheme is often used to equalize the queues. In addition, some queues may be more full than others and naturally need more service, but a strict, fair queuing scheme will only service each queue equally.
- Weighted Fair Queuing (WFQ) - This algorithm is a combination of priority queuing and fair queuing, which allows guaranteed bandwidth services for high priority traffic but the low priority traffic gets a fair share of bandwidth. Traffic may be prioritized according to packet markings, source and destination IP address fields, port numbers, and information in the ToS field. If high-priority queues are not in use, lower-priority traffic uses its queues. This prevents high-bandwidth traffic from grabbing an unfair share of resources.
- Class-Based Queuing (CBQ) - CBQ is a class-based algorithm that schedules packets according to traffic characteristics and guarantees a certain transmission rate. Incoming packets are classified on such variables as the DSCP (Differentiated Services Code Point) in the IP header, the IP addresses, applications, protocols, URL, or other information. Each class of traffic is assigned to a specific FIFO (First In First Out) queue, each of which is guaranteed some portion of the total bandwidth of the router. If a queue is not in use, the bandwidth is made available to other queues. CBQ is also a QoS scheme that identifies different types of traffic and queues the traffic according to predefined parameters.
Queuing Methods and Algorithms
Related Terms: Traffic Management, QoS, FIFO, Priority Queuing, Fair Queuing, Weighted Fair Queuing, Class-Based Queuing