| Search the Collection|Browse Subjects|Services|Library Information|Community |News & Events | ||
|
||
|
|
|
|
|
|
|||||
|
||||||||
Type of Document Dissertation Author Dwekat, Zyad , Author's Email Address zyad@hotmail.com URN etd-06092009-171211 Title Practical Fair Queuing Schedulers: Simpli¯cation through Quantization Degree PhD Graduate Program Electrical Engineering Advisory Committee
Advisor Name Title Mladen Vouk Committee Chair George Rouskas Committee Co-Chair Michael Devetsikiotis Committee Member Mihail Sichitiu Committee Member Keywords
- packet scheduling
- networking
- qos
- algorithm
Date of Defense 2009-06-02 Availability unrestricted Abstract Many packet scheduling schemes have been proposed, but most of them sufferfrom one of two extremes. A scheduling scheme may have simple implementation with
low fairness qualities, or it may have good fairness qualities but high complexity. Our
goal in this research is to design a frame work of schedulers that has both the desired
qualities of fairness and simple implementation. We began our research by conducting a
survey of the scheduling techniques and associated analysis models proposed during the
last decade. Then, in the first part of this thesis we present a suite of packet fair queuing
schedulers with low complexity and good fairness and delay properties. Our designs employ
the concept of quantization by exploiting two widely-observed characteristics of the Internet,
namely that service providers offer some type of tiered service with a small number of
service levels, and that a small number of packet sizes dominate. Taken together, these two
observations permit us to design a good fair queuing algorithm in a manner that packet
sorting operations only need to consider a small, fixed number of packets, independent
of the number of flows, and hence can be performed in constant time. Specifically, the
scheduler we present is equivalent to WF2Q, with the additional advantage that the virtual
time function can be computed in O(1) time. Our tiered-service schedulers operate under
assumptions that are valid under a wide range of practical scenarios, and combine provable
good performance with amenability to hardware implementation in high-speed routers. In
the second part of this thesis, we use quantization of virtual time to design a novel packet scheduler called Worst-Case Bin Sort Queuing (WBSQ). WBSQ has constant complexity,
and can be utilized in a simple hardware implementation. The WBSQ scheduler uses two
methods of quantization. First, WBSQ exploits quantization of virtual time in a manner similar to the bin sorting idea in BSFQ [1] scheduler. In addition, WBSQ simplifies the
system virtual time implementation of WF2Q+ [2]. Worst-Case Bin Sort Queuing has good worst-case fairness and delay properties that are demonstrated through both analytical results and simulations.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access etd.pdf 417.25 Kb 00:01:55 00:00:59 00:00:52 00:00:26 00:00:02