Dept. of Computer Science, University of Crete.
CS-534: Packet Switch Architecture

7. Output Scheduling for QoS

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

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 ]