Article

QoS into the Network: Router Queuing

Gilbert Held

In this third article of a series focused upon Quality of Service (QoS), I focus on the manner by which traffic can be differentiated as it flows into a wide area network. “Quality of Service”, the first article in the series (Sys Admin, September 2000), focused on obtaining an overview of QoS and various methods that could be used to differentiate types of traffic. The second article, “Layer 2 Quality of Service”, (Sys Admin, October 2000) examined QoS by focusing on the data link layer and discussing the role of the IEEE d802.1p standard in a switch-based LAN environment. In that article, I noted that eight levels of priority could be specified that enable switches to place frames into predefined queues based upon the priority tag inserted into the frame. I also noted that because 802.1p tagging occurs within an extended layer 2 frame, priority tagging is lost at router boundaries. Due to this, 802.1p is a LAN QoS mechanism, and the differentiation of traffic as data flows into and through a layer 3 network requires different traffic differentiation mechanisms. This third article primarily illustrates two methods used to provide a quality of service to traffic as it enters a wide area network. These methods include the configuration of router queues and the use of the Type of Service (ToS) byte within the IP header. A recent revision to the use of the ToS byte, which enables the byte to be used as the Differentiated Services (DiffServ) byte, will be the focus of a later article.

Router Queues

Any discussion of router queuing methods requires a frame of reference. Because Cisco Systems has approximately 70 percent of the router market, I will describe and discuss output queuing algorithms supported by Cisco routers under their Internetwork Operating system (IOS) software. IOS currently supports four different queuing algorithms -- first in, first out (FIFO), priority queuing, custom queuing, and weighted fair queuing. As you might expect, there are certain advantages and disadvantages associated with each queuing method.

FIFO

The first, simplest, and the default queuing method for interfaces operating above 2 Mbps is FIFO. The term FIFO is descriptive of both the manner by which accountants can compute the cost of goods sold, and the flow of data when there is no method available to differentiate traffic. Figure 1 illustrates FIFO queuing. As indicated, packets are forwarded out of a router's interface in the order in which they arrive.

The key advantage of FIFO is that it requires the least amount of router resources. However, the simplistic nature of FIFO queuing is also its key disadvantage. Because packets are output to the interface in their order of arrival, it is not possible to prioritize traffic or to prevent an application or user from monopolizing available bandwidth. To appreciate how FIFO queuing can result in latency problems for latency-intolerant applications, examine an evolving IP application -- the use of a voice gateway to digitize voice conversations for their transmission over an IP network.

Figure 1 shows a voice gateway transmitting relatively short packets on an Ethernet LAN, while a station on a Token-Ring network performs a file transfer operation. Assuming that the first packet from the file transfer reaches the router ahead of the first digitized voice packet, then the relatively lengthy file transfer packet precedes the relatively short digitized voice packet in the queue. Because the reconstruction of digitized voice cannot tolerate any significant delay, such as that associated with the insertion of a lengthy packet between two digitized voice packets, the dataflow in Figure 1 illustrates the necessity for queuing methods that employ multiple queues. By placing traffic into different queues based upon various criteria, and using a priority scheme to extract data from those queues, we can differentiate traffic and prioritize data flow, thereby providing a QoS capability as data flows into a WAN.

Priority Queuing

A second type of queuing supported by Cisco routers is referred to as priority queuing. Under priority queuing traffic can be directed into up to four queues -- high, medium, normal, and low. Traffic in the highest priority queue is serviced prior to traffic in lower priority queues. This means that through priority queuing, you can configure a router to place traffic that is relatively intolerant to delay into an appropriate queue that favors its extraction onto a WAN.

In a Cisco router environment, there are several methods available for both identifying traffic to be prioritized, and for placing identified traffic into appropriate queues. While it is possible to use the IOS priority-list command by itself to assign traffic to predefined queues, you can also associate an access list with a priority list to take advantage of the considerable flexibility of access lists in filtering data.

To illustrate priority queuing and some of the limitations of this queuing technique, look at the previous example (Figure 1). That example has a file transfer and voice gateway's digitized voice packets flowing into a router, with both data sources destined to locales beyond the router, resulting in a requirement for each type of traffic to flow over a common WAN link. If priority queuing is enabled, the use of the queues might be configured so that file transfer packets are directed into the low-priority queue, while digitized voice packets are directed into the high-priority queue. Figure 2 shows an example of this packet direction based upon priority queuing. Voice gateway-generated packets are directed into the high-priority queue and file transfer packets flow into the low-priority queue.

The assignment of traffic to priority queues is accomplished through the use of the priority-list command. That command can be used by itself or in conjunction with an access-list command to direct traffic to applicable queues. When used alone, the format of the priority-list command is as follows:

priority-list list-number protocol protocol-name
[high|medium|normal|low] keyword keyword-value

Here the “list-number” is in the range 1 to 10 and identifies the priority list created by a user. The “protocol-name” identifies the protocol type, such as ip, ipx, and similar layer 3 protocols. Next, select one of the four priority queue levels. This is followed by a keyword that can further define the protocol by specifying a transport protocol carried by the network protocol, such as tcp or udp when IP is the network protocol. You can also specify a TCP or UDP port number to denote a service or use such arguments as Gt and lt with a number to initiate queuing based on packet length.

A second version of the priority-list command can be used to reference an access list. That version of the command has the following format:

priority-list list-number protocol protocol-name \
  {high|medium|normal|low} list list number

When using the second version of the priority-list command, the list-number variable references an extended access-list number.

Because digitized voice is transported via UDP without the use of a standardized port, assume that Figure 2 shows the use of UDP port 3210. Since ftp uses TCP port 21, the priority-list statements in a Cisco router environment required to configure priority queuing for the two data sources are:

priority-list 1 protocol ip low tcp 21 priority-list 1 protocol ip high udp 3210

To effect the filtering of traffic into applicable ports, use a priority group command that assigns the specified priority list to the router WAN interface. Assuming the IP address of the serial port connected to the WAN is 198.78.46.1, the applicable set of commands is:

interface serial 0
ip address 198.78.46.1 255.255.255.0
priority-group 1
!
priority-list 1 protocol ip low tcp 21
priority-list 1 protocol ip high udp 3210

Although only two types of traffic were assigned to queues, note that any traffic that does not match the priority list entries is, by default, placed in the normal queue. If you want to use access lists to differentiate traffic, you can associate separate access lists to a common priority list. An example of this is:

interface serial 0
 ip address 198.78.46.1 255.255.255.0
 priority-group 1
!
access-list 100 permit tcp any any eq 3210
access-list 101 permit udp any any eq 21
priority-list 1 protocol ip low tcp 100
priority-list 1 protocol ip high udp 101
!

One of the disadvantages of priority queuing is that it's possible to starve certain applications from access to an interface, such as the WAN shown in Figure 2. The reason for this is that any time there are packets in the high-priority queue, they will be extracted first. Therefore, if the voice gateway is heavily utilized and generates a sustained, heavy flow of traffic to the router, it is possible to exclude the servicing of traffic entering other queues. In this situation, the other queues could fill to capacity, resulting in packets to those queues being dropped. This could result in the retransmission of packets until a threshold is reached that would terminate the application. Perhaps because of the limitation of priority queuing, Cisco added support for two additional queuing methods to its router platforms. One of those methods is custom queuing.

Custom Queuing

Custom queuing provides a mechanism to allocate the bandwidth of a transmission facility based upon specifying a byte count in a series of queue-list commands. By defining the number of bytes to be extracted from a queue before having the router process the next queue, you obtain the ability to indirectly allocate bandwidth. For example, assume you want to allocate 60 percent of the bandwidth of the WAN connection previously shown in Figure 2 to the voice application, 30 percent to file transfers, and the remaining 10 percent to all other traffic. In a Cisco IOS command environment, you would use the queue-list command to classify traffic as well as assign the byte counts to specify the maximum quantity of data to be extracted from each queue prior to the next queue's being serviced.

There are two versions of the queue-list command you would use. One version establishes queuing priority based upon the protocol type, while the second version designates the byte size serviced per queue. The format of the queue-list command used to establish queuing priority is:

queue-list list number protocol protocol-name \
   queue-number keyword keyword-value

The first four entries in the queue-list command function in the same manner as the first four entries in the priority-list command. The fifth entry, “queue-number”, is an integer between 1 and 16 and represents the number of the queue. The “keyword” and “keyword-values” function in the same manner as their counterparts in the priority-list command. The second version of the queue-list command you would use is the queue-list-byte-count command. The format of this command is:

queue-list list-number queue queue-number \ byte-count byte-count-number

In this version of the queue-list command, the “list-number” and “queue-number” continue as identifiers for the number of the queue list and number of the queue, respectively. The important change is the addition of the keyword “byte-count”, which is followed by the “byte-count-number”, the latter specifying the normal lower boundary concerning the number of bytes that can be extracted from a queue during an extraction cycle. The queue extraction process proceeds in a round-robin order, and up to 16 distinct queues can be specified under custom queuing. Once you use the queue and queue-list-byte-count commands, you then use the custom-queue-list command to associate the queue list with an interface.

For the example shown in Figure 2, our custom queuing entries, assuming the same serial port and IP address, would be:

interface serial 0
ip address 198.78.46.1 255.255.255.0
 custom-queue-list 1
!
queue-list 1 protocol ip 1 udp 3210
queue-list 1 protocol ip 2 tcp 21
queue-list 1 default 3
queue-list 1 queue 1 byte count 3000
queue-list 1 queue 2 byte count 1500
queue-list 1 queue 3 byte count 500

In this example, custom queuing was configured to accept 3000 bytes from the UDP queue, 1500 bytes from the ftp queue, and 500 bytes from the default queue. Note that this allocates the percentage of available bandwidth as 60, 30, and 10 percent to queues 1, 2, and 3, respectively. Also note that during the round-robin queue extraction process, if there are fewer than the defined number of bytes in a queue, the other queues can use the extra bandwidth. That use will continue until the number of bytes in the queue equals or exceeds the specified byte count for the queue.

Although the byte count plays a significant role in the allocation of bandwidth when custom queuing is used, you need to carefully consider the length of each frame to obtain the desired allocation. This is due to the manner by which TCP operates, as well as how queuing extraction works. Concerning the former, if you are using a TCP application where the window size for a protocol is set to 1, then that protocol will not transmit another frame into the queue until the transmitting station receives an acknowledgment. This means that if your byte count for the queue was set to 1500 and the frame size is 512 bytes, then only about one-third of the expected bandwidth will be obtained, since 512 bytes will be extracted from the queue. Entire frames are extracted, regardless of the byte count value for a queue. This means that if you set the byte count to 512, but the frame size of the protocol assigned to the queue is 1024 bytes, then each time the queue is serviced, 1024 bytes will be extracted. This would therefore double the bandwidth used by this protocol each time there was a frame in an applicable queue when the round-robin process selected the queue. Therefore, you must carefully consider each protocol's frame size when determining the byte count to be assigned to a queue. Although custom queuing can prevent the potential starvation of lower priority queues, the actual allocation of bandwidth may not actually reach your desired metric.

Another limitation of custom queuing is the fact that processing byte counts for up to 16 queues uses more processing power than the previously described queuing methods. Perhaps because they recognized the first problem, Cisco provided another method that can be used to achieve a level of fairness in allocating bandwidth. That method is referred to as weighted fair queuing.

Weighted Fair Queuing

Weighted fair queuing (WFQ) is an automated method to obtain a level of fairness in allocating bandwidth. Under WFQ, all traffic is monitored and conversations are subdivided into two categories -- those requiring large amounts of bandwidth, and those requiring relatively small amounts of bandwidth. This subdivision results in packets queued by flow, with a flow based upon packets having the same source IP address, destination IP address, source TCP or UDP port, or destination TCP or UDP port. The goal of WFQ is to ensure that low-bandwidth conversations receive preferential treatment in gaining access to an interface, while permitting the large bandwidth conversations to use the remaining bandwidth in proportion to their weights.

Under WFQ, response times for interactive query-response and the egress of small digitized voice packets can be improved when they are sharing access to a WAN with such high-bandwidth applications as HTTP and ftp. For example, without WFQ, a query to a corporate Web server residing on a LAN behind a router could result in a large sequence of lengthy HTTP packets flowing onto the WAN link that precede a short digitized voice packet in the interface's FIFO queue. This would cause the digitized voice packet to wait for placement onto the WAN that could induce an unacceptable amount of delay that would adversely effect the ability to reconstruct a portion of the conversation being delayed.

When WFQ is enabled, the digitized voice frame is automatically identified and scheduled for transmission between HTTP frames, which would considerably reduce its egress time onto the WAN. A second advantage of WFQ is that it requires no configuration commands. It is simply enabled by the use of the following interface command:

fair-queue

Under WFQ, traffic from high-priority queues are always forwarded when there is an absence of low-priority traffic. Because WFQ makes efficient use of available bandwidth for high-priority traffic and is enabled with a minimal configuration effort, it is the default queuing mode on most serial interfaces configured to operate at or below the E1 data rate of 2.048 Mbps.

Although WFQ does not require any configuration commands, the fair-queue command has three options that can be used to tailor its operation. To better understand those options, see Figure 3 for the basic manner by which traffic is classified under WFQ.

Note in Figure 3 that the WFQ classifier automatically classifies frames by protocol, source and destination address, session layer protocol and source/destination port, IP Precedence value in the Service Type byte, and RSVP flow. The latter is a mnemonic for Resource ReSerVation Protocol, which represents a standard for allocating bandwidth across IP networks and will be described in a later article.

Concerning configurable options in the fair-queue command, they include the congestive discard threshold, number of dynamic queues available to hold distinct conversations, and the number of queues that can be reserved by RSVP. The congestive discard threshold specifies how many packets may be queued in each flow's queue. The default is 64 and that value can be adjusted in powers of 2, from 2 through 4096 (216). The dynamic queue value controls the maximum number of conversations a router will monitor. The default value is 256. The reservable-queues option defines the number of queues RSVP can reserve. The default value is 0; however, enabling RSVP on your router automatically results in WFQ reserving 1000 queues for RSVP.

Although WFQ is a good queuing method when you have a mixture of data, in its present incarnation, it cannot tell the difference between a 64-byte telnet packet and a 64-byte packet transporting digitized voice. WFQ treats both equally ahead of longer packets transporting files, which may not be your preference. In addition to a lack of control, WFQ consumes more router resources, which may or may not be a problem depending upon the level of utilization of your router.

Another type of WFQ is Class-Based WFQ (CB-WFQ). Class-based weighted fair queuing allows users to create traffic classes and to assign weights to each class. CB-WFQ represents a powerful tool for backbone network connections within a layer 3 network. I won't go into detail about CB-WFQ, since I am focusing on QoS.

The ToS Byte

Within the 20-byte IP header is an 8-bit byte commonly referred to as the Type of Service (ToS) field. The function of this byte is to denote the importance of the datagram, as well as the datagram's requirements with respect to delay, throughput, and reliability.

Figure 4 illustrates the format of the ToS byte. Note that the first three bit positions can be used to assign a precedence to a datagram. Although eight levels of precedence are available, the highest two values are normally reserved for internal network utilization, allowing the ToS byte to provide a mechanism for partitioning traffic in up to six classes of service.

The setting of a precedence value is normally a function of an application. Although the original intention of the ToS byte was to provide a mechanism for specifying precedence and the reliability, throughput, delay, and cost requirements of a datagram, like many good intentions, its use never approached its goal. In fact, a popular joke is that by default IP traffic is unreliable, slow, and costly, which may explain why applications did not turn on any of the relevant ToS bits. However, if you obtain an application that can be configured to turn on an applicable precedence bit, you can use a Cisco extended IP access list with a priority-list command to associate traffic into a predefined queue.

While Cisco and other router manufacturers provide a mechanism for traffic differentiation based upon the setting of the ToS precedence bits, it will probably be a warm day in Antarctica before its use becomes popular. Recognizing the low level of utilization of the ToS byte, the Internet Engineering Task Force worked on a series of RFCs that redefined the use of that byte. Under the revision, the byte is used to provide differentiated service (DiffServ) information to routers, and its use will be the topic of conversation when I continue the discussion of QoS at the entry into the networks in the next article in this series.

About the Author

Gilbert Held is an award-winning author and lecturer. Gil is the author of over 40 books and 250 technical articles and has represented the United States at technical conferences in Moscow and Jerusalem. Some of Gil's recent titles include Voice and Data Internetworking and Cisco Router Performance, both published by McGraw Hill. Gil can be reached via email at gil_held@yahoo.com.