Time-shift scheduling: fair scheduling of flows in high speed networks
- 24 December 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We present a scheduling protocol, called time-shift scheduling, to forward data packets from multiple input flows to a single output channel. Each input flow is guaranteed a predetermined forwarding rate and an upper bound on packet delay. The protocol is an improvement over existing protocols because it satisfies the properties of low delay, fairness, and efficiency, while existing protocols fail to satisfy at least one of these properties. In time-shift scheduling, each flow is assigned an increasing timestamp, and the packet chosen for transmission is taken from the flow with the least timestamp. The protocol features the novel technique of time shifting, in which the scheduler's real-time clock is adjusted to prevent flow timestamps from increasing faster than the real-time clock. This bounds the difference between any pair of flow timestamps, thus ensuring the fair scheduling of flows.Keywords
This publication has 17 references indexed in Scilit:
- Flow theory: Verification of rate-reservation protocolsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A self-clocked fair queueing scheme for broadband applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Rate controlled servers for very high-speed networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Flow theoryIEEE/ACM Transactions on Networking, 1997
- An upper bound delay for the virtual-clock service disciplineIEEE/ACM Transactions on Networking, 1995
- Protocol verification made simple: a tutorialComputer Networks and ISDN Systems, 1993
- A control-theoretic approach to flow controlPublished by Association for Computing Machinery (ACM) ,1991
- MPEGCommunications of the ACM, 1991
- A calculus for network delay. I. Network elements in isolationIEEE Transactions on Information Theory, 1991
- A stop-and-go queueing framework for congestion managementACM SIGCOMM Computer Communication Review, 1990