Queuing Mechanisms Objectives

Case Study

• The WFQ system can hold a maximum of ten packets (hold-queue limit).
• Early dropping (of aggressive flows) should start when there are eight packets (congestive discard threshold) in the WFQ system.

Case Study: Interface Congestion

• Absolute maximum (HQO=10) exceeded; new packet is the last in the TDM system and is dropped

Case Study: Interface Congestion

• Absolute maximum exceeded (HQO=10); new packet is not the last in the TDM system, so last packet is dropped

Case Study: Flow Congestion

• CDT exceeded (CDT=8); new packet would be the last in the TDM system and is dropped

Case Study: Flow Congestion

• CDT exceeded (CDT=8); new packet would not be the last, and packet is enqueued

Drop Mechanism Within WFQ: Exception

• Exception: A packet classified into an empty subqueue is never dropped.
• The packet precedence has no effect on the dropping scheme.

WFQ Scheduling

• Each packet is tagged with its finish time in a virtual TDM system.
• The scheduler selects the packets with the earliest finish time tag (thus, the packet that leaves the virtual TDM the earliest).
• Reference: “On the Efficient Implementation of Fair Queuing," Keshav, Berkeley, 1994

Fair Queuing Finish Time Calculation

• FT(B2)=350+300

• B2[300]

• FT(A3)=120+10

• A3[10]

• FT(A2)=100+20

• A2[20]

• FT(B1)=50+300

• B1[300]

• A1[100]

• FT(A1)=0+100

• T

• 100

• 70

• 60

• 50

• 0

• B2

• B1

• A3

• A2

• A1

• Thus the resulting scheduling is:

• If Flow F active, then FT(Pk+1) = FT(Pk) + Size(Pk+1) otherwise FT(P0) = Now + Size(P0)