WFQ Scheduling The Process

WFQ gives each flow a weighted percentage of link bandwidth. However, WFQ does not predefine queues like class-based queuing tools do, because WFQ dynamically classifies queues based on the flow details. And although WFQ ends up causing each flow to get some percentage of link bandwidth, the percentage changes, and changes rapidly, because flows come and go frequently. Because each flow may have different precedence values, the percentage of link bandwidth for each flow will change, and it will change very quickly, as each flow is added or removed. In short, WFQ simply could not be implemented by assigning a percentage of bandwidth, or a byte count, to each queue.

The WFQ scheduler is actually very simple. When the TX Queue/Ring frees a slot, WFQ can move one packet to the TX Queue/Ring, just like any other queuing tool. The WFQ scheduler takes the packet with the lowest sequence number (SN) among all the queues, and moves it to the TX Queue/Ring. The SN is assigned when the packet is placed into a queue, which is where the interesting part of WFQ scheduling takes place.

For perspective on the sequence of events, marking the SN, and serving the queues, examine Figure 4-13.

Figure 4-13 WFQ: Assigning Sequence Numbers and Servicing Queues

3) Maximum Number of Queues

4) Maximum Queue Length

5) Scheduling Inside Queue

Assign SN

1) Classification

Jc aao-n lie

H il le

Always on Combination Of:

- Source/destination IP Address

- Transport Protocol Type

- Source/Destination Port

SN = Previous_SN +weight*length

Weight Based on IP Precedence

2) Drop Decision

Dropped

Modified Tail Drop Based on Hold Queue and CDT

3) Maximum Number of Queues

4) Maximum Queue Length

5) Scheduling Inside Queue

Max 4096

Queues

Process: Take packet with lowest sequence number.

Result: Favors flows with lower byte volumes and larger precedence values.

>TX Queue/Ring

FIFO

WFQ calculates the SN before adding a packet to its associated queue. In fact, WFQ calculates the SN before making the drop decision, because the SN is part of the modified tail-drop logic. The WFQ scheduler considers both packet length and precedence when calculating the SN. The formula for calculating the SN for a packet is as follows:

Previous_SN + weight * new_packet_length

The formula considers the length of the new packet, the weight of the flow, and the previous SN. By considering the packet length, the SN calculation results in a higher number for larger packets, and a lower number for smaller packets. The formula considers the SN of the most recently enqueued packet in the queue for the new sequence number. By including the SN of the previous packet enqueued into that queue, the formula assigns a larger number for packets in queues that already have a larger number of packets enqueued.

The third component of the formula, the weight, is the most interesting part. We know from the basic scheduling algorithm that the lowest SN is taken next, and we know that WFQ wants to give more bandwidth to the higher-precedence flows. So, the weight values are inversely proportional to the precedence values. Table 4-5 lists the weight values used by WFQ before and after the release of 12.0(5)T/12.1.

Table 4-5 WFQ Weight Values, Before and After 12.0(5)T/12.1

Precedence

Before 12.0(5)T/12.1

After 12.0(5)T/12.1

0

409ó

32384

1

204B

16192

2

13ó5

10194

3

1024

8096

4

B19

6416

5

682

539l

ó

5B5

4626

l

512

4048

As seen in the table, the larger the precedence value, the lower the weight making the SN lower. An example certainly helps for a fuller understanding. Consider the example in Figure 4-14, which illustrates one existing flow and one new flow.

Figure 4-14 WFQ Sequence Number Assignment Example

Existing: Flow 1

Figure 4-14 WFQ Sequence Number Assignment Example

Weight for Precedence=0 is 32,384

Existing: Flow 1

Existing

Packet:

SN=1000

Weight for Precedence=0 is 32,384

New Flow: Flow 2

TX Ring

Last Packet in TX Ring: SN=100

New packet 2, Flow 2: Length 500, Precedence 0 \

When adding new packet 1 to the queue for Flow 1, WFQ just runs the formula against the length of the new packet (100) and the weight, adding the SN of the last packet in the queue to which the new packet will be added. For new flows, the same formula is used; because there are no other packets in the queue, however, the SN of the most recently sent packet, in this case 100, is used in the formula. In either case, WFQ assigns larger SN values for larger packets and for those with lower IP precedence.

A more detailed example can show some of the effects of the WFQ SN assignment algorithm and how it achieves its basic goals. Figure 4-15 shows a set of four flow queues, each with four packets of varying lengths. For the sake of discussion, assume that the SN of the previously sent packet is zero in this case. Each flow's first packet arrives at the same instant in time, and all packets for all flows arrive before any more packets can be taken from the WFQ queues.

Figure 4-15 WFQ Sequence Number Assignment Example 2

Flow 1

Figure 4-15 WFQ Sequence Number Assignment Example 2

Flow 1

SN=48,576,000

Flow 2

SN=129,536,000

Packet7 SN=97,152,000

Packet6 SN=65,536,000

Packet5 SN=32,384,000

Flow 3

Precedence 0

Packet12 SN=65,536,000

Packet11 SN=48,576,000

Packet10 SN=32,384,000

Packet9 SN=16,192,000

Flow 4

Precedence 0

Packet16 SN=12,954,600

Packet15 SN=9,715,200

Packet14 SN=6,553,600

Packet13 SN=3,238,400

In this example, each flow had four packets arrive, all with a precedence of zero. The packets in Flow 1 were all 1500 bytes in length; in Flow 2, the packets were 1000 bytes in length; in Flow 3, they were 500 bytes; and finally, in Flow 4, they were 100 bytes. With equal precedence values, the Flow 4 packets should get better service, because the packets are much smaller. In fact, all four of Flow 1's packets would be serviced before any of the packets in the other flows. Flow 3's packets are sent before most of the packets in Flow 1 and Flow 2. Thus, the goal of giving the lower-volume flows better service is accomplished, assuming the precedence values are equal.

NOTE For the record, the order the packets would exit the interface, assuming no other events occur, is 13 first, then 14, followed by 15, 16, 9, 5, 19, 1, 11, 6, 12, 2, 7, 8, 3, 4.

To see the effect of different precedence values, look at Figure 4-16, which lists the same basic scenario but with varying precedence values.

Figure 4-16 WFQ Sequence Number Assignment with Varying Precedence Values

Flow 1

Figure 4-16 WFQ Sequence Number Assignment with Varying Precedence Values

Flow 1

Precedence 3

Packet4 SN=48,576,000

Packet3 SN=36,432,000

SN=12,144,000

Flow 2

Precedence 5

Packet8 SN=21,588,000

Packet7 SN=16,191,000

Packet6 SN=10,694,000

Packet5 SN=5,397,000

Flow 3

Precedence 0

Packet12 SN=65,536,000

Packet11 SN=48,576,000

Packet10 SN=32,384,000

Packets SN=16,192,000

Flow 4

Precedence 0

Packet16 SN=12,954,600

Packet15 SN=9,715,200

Packet14 SN=6,553,600

Packet13 SN=3,238,400

The SNs for Flow 1 and Flow 2 improve dramatically with the higher precedence values of 3 and 5, respectively. Flow 4 still gets relatively good service, even at precedence 0. Two packets from Flow 2, and one from Flow 1, will be serviced before Flow 4's fourth packet (SN 12,954,600), which is an example of how the higher precedence value gives the packets in this flow slightly better service. So, the lower-volume, but lower-precedence flows will have some degradation in service relative to the higher-volume, but higher-precedence flows.

NOTE For the record, the order the packets would exit the interface, assuming no other events occur, is 13, 5, 14, 15, 6, 1, 16, 7, 9, 2, 8, 3, 4, 11, 12.

Finally, a router using WFQ can experience a phenomenon called too fair. With many flows, WFQ will give some bandwidth to every flow. In the previous example, what happens if 200 new flows begin? Each of those new flows will get a relatively low SN, because the SN of the most recently sent packet is used in the formula. The packets that are already in the existing queues will have to wait on all the new packets. In an effort to give each flow some of the link bandwidth, WFQ may actually not give some or most of the flows enough bandwidth for them to survive.

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