Subsections in the current document:

• 7.1 introduction, Conservation Law, Scheduler Composition
• 7.2 Strict (Static) Priority Scheduling
• 7.3 Round Robin Scheduling
• 7.4 Weighted Round Robin Scheduling

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

7.2 Strict (Static) Priority Scheduling

7.3 Round Robin Scheduling

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

[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.