CS-534: Packet Switch Architecture
Spring 2003		 Department of Computer Science
© University of Crete, Greece

7.3   Round Robin Scheduling

[Up: Table of Contents]
[Prev: 7.2 Strict (Static) Priorities]
[Next: 7.4 Weighted Round Robin (WFQ)]

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.
Refer to exercise 11.2 for more details on this scheme.

[Up: Table of Contents]
[Prev: 7.2 Strict (Static) Priorities]
[Next: 7.4 Weighted Round Robin (WFQ)]
Up to the Home Page of CS-534
 		 © copyright University of Crete, Greece.
Last updated: 6 June 2003, by M. Katevenis.