[ Up to the Home Page of CS-534 ]
© copyright University of Crete, Greece.
Dept. of Computer Science, University of Crete.
CS-534: Packet Switch Architecture

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

Conceptual Stages of Scheduling

Conservation Law

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


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

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 ]
© copyright University of Crete, Greece.
Last updated: May 2000, by M. Katevenis.