CS-534: Packet Switch Architecture
Fall 2001
Department of Computer Science
© copyright: University of Crete, Greece

7. Output Scheduling for QoS

Subsections in the current document:

Reading: read Chapter 9, on "Scheduling", from the book: S. Keshav: "An Engineering Approach to Computer Networking", Addison Wesley, 1997, ISBN 0-201-63442-2.

7.1 introduction, Conservation Law, Scheduler Composition

Scheduling: introduction

Conservation Law

Conceptual Stages of Scheduling

Composite Schedulers: Aggregation and Hierarchy

7.2 Strict (Static) Priority Scheduling

Strict (Static) Priority Scheduling

Starvation Issue with strict (static) priorities

7.3 Round Robin Scheduling

Round Robin Scheduling

Circular Linked List of Eligible Flow ID's
Comments: Let us call "uncongested" flows the flows whose bottleneck is not this network link --their bottleneck may be their source (end-to-end flow control), or it may be another network link (either a link upstream of this link, or a downstream link but with hop-by-hop flow control). Uncongested flows ususally have (almost) empty queues, because these queues are served (emptied) more frequently that they are filled. Newly arriving cells or packets will usually be inserted into empty queues, causing the flow to re-become elligible. Then, the queue will be served before a second cell or packet arrives in it, causing the queue to re-become empty and the flow to become inelligible.

Insertions (b) penalize the uncongested ("well behaved") flows by causing them to undergo the worst-case delay, while this yields no appreciable gain for the congested flows: congested flows undergo a very long delay anyway --what matters for these latter flows is throughput, not delay. Insertions (c) offer only a 50% (average) improvement over (b) for uncongested flows.

An alternative is to use insertions (a) when we have verified that the flow is uncongested, else use insertions (b) (or (c)?) when it looks like the flow is congested. To verify that the flow is well behaved (uncongested), we need to maintain per-flow last-service timestamps. When a formerly-inelligible flow becomes elligible again, we look at the difference of the current time minus the last-service time of the flow; if this difference is larger than the average "circular scan" time, then the flow is (currently) uncongested, else it is (currently) congested on this link. The "circular scan" time is the time it takes our server to go once around the circular list of eligible flows. We need a "fixed pointer" into the list to compute this: every time the server passes over this "marked" flow, we read that flow's last-service timestamp, and see how much time has elapsed since then.

7.4 Weighted Round Robin Scheduling

Weighted Round Robin Service Schedules

Priority Queue: (quite) smooth WRR scheduling

Real or Virtual Time?

Where to Reinsert a Flow that becomes Eligible?

Beware: multiple low-rate flows may create large jitter for high-rate flows

Leaky Bucket implemented using Priority Queue
[Correction: the "max" should be "min" in the equation at the middle of this transparency]

Read the pages on Weighted Round-Robin Schedulers of the Computer Architecture and VLSI Systems Lab of ICS-FORTH.

For Calendar Queues, the primary reference is: R. Brown: "Calendar Queues: a Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem", Communications of the ACM, vol. 31, no. 10, Oct. 1988, pp. 1220-1227.

Up to the Home Page of CS-534
© 2001 copyright: University of Crete, Greece.
Last updated: 29 Nov. 2001, by M. Katevenis.