Files and links (1)
PDFOpen Access (License Unspecified), Open Access
Dissertation
Design and analysis of fair, efficient and low-latency schedulers for high-speed packet-switched networks
Doctor of Philosophy (Ph.D.), Drexel University
May 2003
DOI:
https://doi.org/10.17918/etd-145
Abstract
A variety of emerging applications in education, medicine, business, and entertainment rely heavily on high-quality transmission of multimedia data over high speed networks. Packet scheduling algorithms in switches and routers play a critical role in the overall Quality of Service (QoS) strategy to ensure the performance required by such applications. Fair allocation of the link bandwidth among the traffic flows that share the link is an intuitively desirable property of packet schedulers. In addition, strict fairness can improve the isolation between users, help in countering certain kinds of denial-of-service attacks and offer a more predictable performance. Besides fairness, efficiency of implementation and low latency are among the most desirable properties of packet schedulers. The first part of this dissertation presents a novel scheduling discipline called Elastic Round Robin (ERR) which is simple, fair and efficient with a low latency bound. The perpacket work complexity of ERR is O(1). Our analysis also shows that, in comparison to all previously proposed scheduling disciplines of equivalent complexity, ERR has significantly better fairness properties as well as a lower latency bound. However, all frame-based schedulers including ERR suffer from high start-up latencies, burstiness in the output anddelayed correction of fairness. In the second part of this dissertation we propose a new scheduling discipline called Prioritized Elastic Round Robin (PERR) which overcomes the limitations associated with the round robin service order of ERR. The PERR scheduler achieves this by rearranging the sequence in which packets are transmitted in each round of the ERR scheduler. Our analysis reveals that PERR has a low work complexity which is independent of the number of flows. We also prove that PERR has better fairness and latency characteristics than other known schedulers of equivalent complexity. In addition to their obvious applications in Internet routers and switches, both the ERR and PERR schedulers also satisfy the unique requirements of wormhole switching, popular in interconnection networks of parallel systems. Finally, using real gateway traces and based on a new measure of instantaneous fairness borrowed from the field of economics, we present simulation results that demonstrate the improved fairness characteristics and latency bounds of the ERR and and PERR schedulers in comparison with other scheduling disciplines of equivalent efficiency.
Metrics
30 File views/ downloads
25 Record Views
Details
- Title
- Design and analysis of fair, efficient and low-latency schedulers for high-speed packet-switched networks
- Creators
- Salil S. Kanhere - DU
- Contributors
- Harish Sethu (Advisor) - Drexel University (1970-)
- Awarding Institution
- Drexel University
- Degree Awarded
- Doctor of Philosophy (Ph.D.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Resource Type
- Dissertation
- Language
- English
- Academic Unit
- College of Engineering (1970-2026); Electrical (and Computer) Engineering [Historical]; Drexel University
- Other Identifier
- 145; 991014632539004721