<p>Zhu, Kai. <b>Statistical Delay Bounds Oriented Packet Scheduling Algorithms inHigh Speed Networks.</b> (Under the direction of Prof. Yannis Viniotis)<P>We first present a strategic analysis of end-to-end delay bounds and identify heuristics for scheduler design, then propose three new schedulers that are targeted at statistical delay bounds: Deadline-curve basedEarliest Deadline First (DC-EDF), Adaptive Quasi-Earliest Deadline First (AQE)and General Dynamic Guaranteed Rate Queueing (GDGRQ).<P>Under DC-EDF, local deadlines are assigned as strict time-shifted versions ofsource packet arrival times. This is quite different from the well-known RC-EDF(Rate-controlled EDF), which deploys traffic shaping at each switching node. Weshow that even without traffic shapers, DC-EDF provides not only end-to-enddelay bounds, but also a schedulable region as large as that of RC-EDF. DC-EDFis self-adaptive in local delay bound assignments. This property makes DC-EDFsuitable as the scheduler at intermediate switching nodes along a flow's route.<P>AQE is an enhancement of EDF with intelligence of adaptive scheduling. Under AQEpercentile delay bounds are the delay QoS metric. AQE behaves like EDF whenbandwidth is sufficient. When bandwidth becomes deficient, however, AQE onlyschedules a subset of flows which currently have relatively worse performance;other flows are completely blocked and will be unblocked only when bandwidthbecomes sufficient again. Essentially, AQE enforces shaping on packet delaydistributions. AQE is most suited for scheduling at the last switching nodealong a flow's route. The combination of DC-EDF and AQE provides a good solutiontowards statistical end-to-end delay bounds.<P>GDGQR is designed for networks with fixed packet sizes. It is a subclass of thewell-known Guaranteed Rate (GR) schedulers, thus can guarantee minimum rates toflows. The GR property of GDGRQ is retained through a sophisticated datastructure called cell transmission table. The unique feature of GDGRQ is that itallows controllable adaptive strategy of excess bandwidth distribution, which isrealized by short-term rate adjustment according to queue measurement. GDGRQ isa framework for designing schedulers that can both provide (possibly large)deterministic delay bounds and allow statistical delay bounds.<P>
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-20000911-100735 |
| Date | 21 September 2000 |
| Creators | Zhu, Kai |
| Contributors | Yannis Viniotis, Harry Perros, George N. Rouskas, Bibhuti B. Bhattacharrya |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-20000911-100735 |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.002 seconds