Queuing Concepts

Most people already understand many of the concepts behind queuing. First, this section explains the basics and defines a few terms. Afterward, some of the IOS-specific details are covered.

IOS stores packets in memory while processing the packet. When a router has completed all the required work except actually sending the packet, if the outgoing interface is currently busy, the routerjust keeps the packet in memory waiting on the interface to become available. To manage the set of packets sitting around in memory waiting to exit an interface, IOS creates a queue. A queue just organizes the packets waiting to exit an interface; the queue itself is nothing more than a series of pointers to the memory buffers that hold the individual packets that are waiting to exit the interface.

The most basic queuing scheme uses a single queue, with first-in, first-out (FIFO) scheduling. What does that mean? Well, when the IOS decides to take the next packet from the queue, of those packets still in the queue, it takes the one that arrived earlier than all the other packets in the queue. Figure 4-1 shows a router, with an interface using a single FIFO queue.

Figure 4-1 Single FIFO Queue

4 X 1500

Byte Rackets^ Is there room in the queue?

4 X 1500

Byte Rackets^ Is there room in the queue?

Although a single FIFO queue seems to provide no QoS features at all, it actually does affect drop, delay, and jitter. Because there is only one queue, the router need not classify traffic to place it into different queues. Because there is only one queue, the router need not worry about how to decide from which queue it should take the next packet—there is only one choice. And because this single queue uses FIFO logic, the router need not reorder the packets inside the queue.

However, the size of the output queue affects delay, jitter, and loss. Because the queue has a finite size, it may fill. If it fills, and another packet needs to be added to the queue, tail drop would cause the packet to be dropped. One solution to the drops would be to lengthen the queue, which decreases the likelihood of tail drop. With a longer queue, however, the average delay increases, because packets may be enqueued behind a larger number of other packets. In most cases when the average delay increases, the average jitter increases as well. The following list summarizes the key concepts regarding queue length:

• With a longer queue length, the chance of tail drop decreases as compared with a shorter queue, but the average delay increases, with the average jitter typically increasing as well.

• With a shorter queue length, the chance of tail drop increases as compared with a longer queue, but the average delay decreases, with the average jitter typically decreasing as well.

• If the congestion is sustained such that the offered load of bytes trying to exit an interface exceeds the interface speed for long periods, drops will be just as likely whether the queue is short or long.

To appreciate most queuing concepts, you need to consider a queuing system with at least two queues. Consider Figure 4-2, which illustrates two FIFO output queues.

Figure 4-2 Dual FIFO Output Queues

4 X 1500 Byte Packets

Into which queue should I place each packet? -►

Is there room in the queue?

Output Queue^ 1

Output Queue^ 2

From which queue do Iw take the next packet?

©Should I reorder packet inside a single queue?

Figure 4-2 illustrates the questions that are answered by the queuing tool. Step 1, the classification step, works like classification and marking tools, except the resulting action is to place a packet in a queue, as opposed to marking a packet. So, at step 1, the packet header is examined, and depending on the matched values, the packet is placed into the appropriate queue. Before placing the packet in the queue, the router must make sure that space is available, as shown in step 2 in Figure 4-2. If no space is available, the packet is dropped. Inside each queue, the packets can be reordered (step 3): in this example, however, each queue uses FIFO logic inside each queue, so the packets would never be reordered inside the queue. Finally, the queuing system must choose to take the next packet for transmission from either Queue 1 or Queue 2 (step 4). The scheduler makes the decision at step 4.

Although the classification portion of each queuing tool is relatively obvious, consider two related points when thinking about classification by a queuing tool. First, with a QoS strategy that causes classification and marking to occur near the ingress edge of the network, the queuing tool may enqueue packets that have already been marked. So, the queuing tool can classify based on these marked fields, which was the whole point in marking them in the first place! Second, for each category of traffic for which you want to provide different queuing treatment, you need a different queue. For instance, you may want to classify traffic into six classes for queuing, so each class can get different treatment in a different queue. If the queuing tool only supports four different queues, you may need to consider a different queuing tool to support your QoS policy.

Inside each queue, the queuing methods use FIFO Queuing. The interesting logic for queuing occurs after the packets have been enqueued, when the router decides from which queue to take the next packet. Queue scheduling describes the process of the device, in this case a router, choosing which queue to service next. This process is also called a service algorithm, or a queue service algorithm. The scheduler may reserve amounts of bandwidth, or a percentage of link bandwidth, for a particular queue. The scheduler may always service one queue first, which means the packets in that queue will experience very low delay and jitter.

For the exams, you need to know what each queuing tool's scheduler accomplishes; for some tools, however, you also need to know the internals of how the scheduler actually works.

NOTE Cisco leads the industry in making details about their products public (being the first large networking vendor to publish bug reports, for instance). However, Cisco must also protect their intellectual assets. So, for some of the newer queuing tools, Cisco has not yet published every detail about how the scheduling algorithm works. For some of the older queuing tools, the details are published. Frankly, the details of how the scheduling code works inside IOS might be interesting, but it is not really necessary for a deep understanding of what a queuing tool does. For the QoS exams, you need to know what each queuing tool's scheduler accomplishes; for some tools, however, you also need to know the internals of how the scheduler actually works. When necessary, this book gives you plenty of details about the internal scheduling algorithms to help prepare you for the exams.

A final comment about the core concepts of queuing: The size of each packet does not affect the length of the queue, or how many packets it can hold. A queue of length 10 holds ten 1500-byte packets as easily as it holds ten 64-byte packets. Queues actually do not hold the packets themselves, but instead just hold pointers to the packets, whose contents are held in buffers.

Table 4-2 summarizes the key concepts of queuing. This table is used to compare the various queuing tools in the "Queuing Tools" section of this chapter.

Table 4-2 Key Concepts When Comparing Queuing Tools

Table 4-2 summarizes the key concepts of queuing. This table is used to compare the various queuing tools in the "Queuing Tools" section of this chapter.

Table 4-2 Key Concepts When Comparing Queuing Tools

Feature

Definition

Characteristic Affected

Classification

The capability to examine packets to determine into which queue the packet should be placed. Many options are available.

None

Drop policy

When the queue has been determined, the drop policy defines the rules by which the router chooses to drop the packet. Tail drop, modified tail drop, WRED (Weighted Random Early Detect), and FRED (Flow-Based Random Early Detect) are the main options.

Loss

Scheduling inside a single queue

Inside a single queue, packets can be reordered. In most cases, however, FIFO logic is used for packets inside each queue.

Bandwidth, delay, jitter, and loss

Scheduling between different queues

The logic that defines how queuing chooses the next packet to take from the output queues and place it in the TX Queue (Transmit Queue).

Bandwidth, delay, jitter, and loss

Maximum number of queues

The maximum number of different queues the queuing tools support, which in turn implies the maximum number of traffic classifications that can be treated differently by the queuing method.

None

Maximum queue length

The maximum number of packets in a single queue.

Loss, delay

Advance SEO Techniques

Advance SEO Techniques

Turbocharge Your Traffic And Profits On Auto-Pilot. Would you like to watch visitors flood into your websites by the 1,000s, without expensive advertising or promotions? The fact is, there ARE people with websites doing exactly that right now. How is that possible, you ask? The answer is Advanced SEO Techniques.

Get My Free Ebook


Post a comment