Queuing (Linktionary term)

Site home page
(news and notices)

Get alerts when Linktionary is updated

Book updates and addendums

Get info about the Encyclopedia of Networking and Telecommunicatons, 3rd edition (2001)

Download the electronic version of the Encyclopedia of Networking, 2nd edition (1996). It's free!

Contribute to this site

Electronic licensing info

Queuing

Note: Many topics at this site are reduced versions of the text in "The Encyclopedia of Networking and Telecommunications." Search results will not be as extensive as a search of the book's CD-ROM.

You are familiar with queues as lines of people waiting to buy tickets or to talk to a service representative on the phone. A queue is also a collection of objects waiting to be processed, one at a time. In the networking environment, packets are queued up into the memory buffers of network devices like routers and switches. Packets in a queue are usually arranged in first-in, first-out order, but various techniques may be used to prioritize packets or ensure that all packets are handled fairly, rather than allowing one source to grab more than its share of resources.

Note that a buffer is a physical block of memory, while a queue is a collection of packets waiting in buffers for processing. Queuing algorithms determine how queues are processed. A different type of queuing is message queuing. See "Middleware and Messaging."

Packets may arrive at queues in bursts from multiple devices, and a device may temporarily receive more packets than it can process. Buffers hold packets until a device can catch up. If the device cannot catch up, buffers fill up and new incoming packets are dropped. This is called "tail drop."

Queue management schemes alleviate congestion. One technique drops packets when necessary or appropriate. So-called "stale" packets (voice or video packets that will arrive too late to be used) may also be dropped to free up space in a queue with the assumption that the receiver will drop them anyway. Scheduling algorithms determine which packet to send next in order to manage and prioritize the allocation of bandwidth among the flows.

Queue management is a part of packet classification and QoS schemes, in which flows are identified and classified, and then placed in queues that provide appropriate service levels. RFC 1633 (Integrated Services in the Internet Architecture: An Overview, June 1994) describes the router functions that provide "traffic control" functions. The most important for this discussion is the packet scheduler, which uses queues to forward different packet streams. Other components include the classifier, which identifies and maps packets into queues. Packets of the same class are put into the same queues, where they receive the same treatment by the packet scheduler.

Multiple access networks such as intranets and the Internet are referred to as "networks of queues." In a point-to-point link, the receiver monitors its own queues and signals the sender when it is sending too fast. In packet-switched networks with many senders transmitting at any time, it is impossible to predict traffic levels. Some parts of the network may become more congested than others. The solution is to place queues throughout the network to absorb bursts from one or more senders.

Queuing Methods

This section explains basic queuing techniques. The following questions could be asked about queues when trying to understand how a particular system works:

How are incoming packets placed into queues?

What is the order and/or method in which the networking device services its queues?

What are the strategies for dealing with bursts of traffic and queues that overflow?

There are several queuing methods, including FIFO (first-in, first out), priority queuing, and fair queuing. FIFO is common in all the queuing schemes, as it describes the basic method in which packets flow through queues. You can imagine queues as supermarket checkout lanes. Each lane uses FIFO queuing, but cashiers may change the order to reduce congestion (e.g., pull shoppers from busy lanes into less busy lanes). Shoppers with membership cards, cash, or a small number of items may be pulled into an express lane (prioritization).

FIFO queuing This is the basic first-in, first-out queuing technique in which the first packet in the queue is the first packet that is processed. 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 technique uses multiple queues, but queues are serviced with different levels of priority, with the highest priority queues being serviced first. Figure Q-2 illustrates Cisco's priority queuing scheme. When congestion occurs, packets are dropped from lower-priority queues. The only problem with this method is that lower-priority queues may not get serviced at all if high-priority traffic is excessive. Packets are classified and placed into queues according to information in the packets. For example, Cisco routers can be programmed to prioritize traffic for a particular port into high-, medium-, or low-priority queues. Priority schemes may be abused by users or applications that mark packets with priorities that are not allowed. Admission control functions can monitor this. See "Admission Control."

Fair queuing This method helps solve the problem where some queues may not get serviced because high-priority queues are being serviced. 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. Problems can occur when packets are variable in length and each queue is allowed to release one packet at a time. Some queues will take more time. A byte-oriented scheme may be 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 service each queue equally.

WFQ (weighted fair queuing) This can be seen as a combination of priority queuing and fair queuing. All queues are serviced so that none are starved, but some queues are serviced more than others. A weight is applied to queues to give some queues higher priority. For example, one queue may get half the available bandwidth and other queues will get an allocation of the remaining bandwidth. Traffic may be prioritized according to packet markings, source and destination IP address fields, port numbers, and information in the ToS field. WFQ weights traffic so that low-bandwidth traffic gets a fair level of priority. 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. WFQ is Cisco's "premier queuing technique" according to the Cisco QoS paper listed on related entries page. A unique feature is that it moves real-time interactive traffic to the front of queues and fairly shares the remaining bandwidth among other flows.

CBQ (class-based queuing) CBQ is a class-based algorithm that schedules packets in queues and guarantees a certain transmission rate. If a queue is not in use, the bandwidth is made available to other queues. A CBQ-compliant device looks deep in packets to classify packets according to addresses, application type, protocol, URL, or other information. CBQ is more than a queuing scheme. It is also a QoS scheme that identifies different types of traffic and queues the traffic according to predefined parameters.

Queue Behavior

A good document on queue management is RFC 2309 (Recommendations on Queue Management and Congestion Avoidance in the Internet, April 1998). It describes methods for improving and preserving Internet performance, including queue management. Important points are outlined here:

Buffering is meant to absorb data bursts and transmit them during the slow period that follows (assuming that occurs).

Queue "lockout" occurs when a sender is allowed to monopolize queue space and prevents other connections from getting room in the queue. The sender may be bursting, or sending large packets.

The variable length of packets in IP networks (up to 1,500 bytes) makes queue management difficult, and thus QoS is difficult. It is impossible to accurately estimate delay with variable packet sizes.

Congestion avoidance mechanisms that operate in TCP hosts can reduce network congestion. These work at the edge of the network. Routers use active queue management techniques to avoid congestion problems. Packets are dropped in anticipation of full queues so that senders slow down. This is appropriate, but maintaining queues in a nonfull state is also not efficient, and "translates to a recommendation that low end-to-end delay is more important than high throughput."

Temporary bursts should be allowed. Acting to reduce temporary bursts by dropping packets may be an unnecessary waste of bandwidth.

The bigger the queue, the less likely that packets will be dropped off the end of the queue (tail drop). However, large queues can lead to delay problems (a packet may be held when it should be dropped to indicate congestion). Queues should reflect the size of bursts that need to be absorbed. Applications that are affected by delay and jitter, such as voice, need small queues. Non-real-time traffic such as electronic mail, file transfers, and backups benefit from large queues.

Two queue disciplines can be used in place of tail drop. "Random drop on full" drops randomly selected packets. "Drop front on full" drops packets at the front of queues. Dropping on the front is used to more quickly notify a sender of congestion. Consider a case where a sender has filled a queue and tail drop occurs. The receiver will continue to receive packets and not know that congestion is occurring until it notices the dropped packet. Dropping at the front tells the receiver right away to signal congestion (by failing to acknowledge).

Active queue management is the process of dropping packets before buffers overflow. A mechanism called RED (random early detection) detects when a queue is about to overflow by monitoring several threshold levels. When a level is exceeded, packets are dropped "probabilistically" in an attempt to scale back a sender. RED and some variations of RED are discussed under "Congestion Control Mechanisms."

Packet bursts are unavoidable. Dropping packets from temporary bursts is not helpful since it will cause the sender to slow down when it may not need to. Keeping average queue size small helps active queue management provide greater capacity to absorb naturally occurring bursts without dropping packets.

Small queues reduce delay, which is essential for real-time traffic.

Without active queue management, the number of dropped packets increases. TCP hosts steadily increase their transmission rates. If a host reaches a high rate just as the buffer fills, many packets will be dropped. It is best to slow a host down if this situation occurs.

Since basic queue management does not provide per-flow state (tracking flows of packets with the same IP source/destination address and port), scheduling methods such as fair queuing, CBQ, and other packet-scheduling methods are needed to fairly allocate bandwidth among flows. Scheduling algorithms and queue management should be seen as complementary, not as replacements for each other.

Traffic-shaping algorithms control queues in a way that smoothes out the flow of packets into networks by hosts or at routers. For example, a host may use what is called a leaky bucket at the network interface. The bucket is basically a regulated queue. An application may produce an uneven flow of packets that burst or trickle into the bucket, but the bucket has an imaginary hole in the bottom through which only a certain number of packets can exit in a steady stream. A token bucket takes this concept further by allowing a queue to save up permission to send bursts of packets at a later time. A typical algorithm is that for every second of time, a token is saved. If a packet is sent, one of these tokens is destroyed. If no packets are being sent, tokens start to accumulate, which can be used later to burst packets.

UDP may be used by applications that do not need TCP's guaranteed services. UDP does not acknowledge receipt of packets to the sender; therefore, it does not support congestion controls based on dropping packets. When queues fill, UDP will keep sending. Rate controllers can help, as discussed under "Congestion Control Mechanisms."

As mentioned, TCP congestion control mechanisms and active queue management schemes such as RED are discussed under "Congestion Control Mechanisms." Going beyond congestion control mechanisms, there are QoS techniques such as Int-Serv (Integrated Services) and RSVP (Resource Reservation Protocol). See "QoS (Quality of Service)" for an overview and references to related sections.