Practical Fair Queuing Schedulers: Simplification through Quantization

packet scheduling;networking;qos;algorithm

Dwekat, Zyad ; Mladen Vouk, Committee Chair,George Rouskas, Committee Co-Chair,Mihail Sichitiu, Committee Member,Michael Devetsikiotis, Committee Member,Dwekat, Zyad ; Mladen Vouk ; Committee Chair ; George Rouskas ; Committee Co-Chair ; Mihail Sichitiu ; Committee Member ; Michael Devetsikiotis ; Committee Member

University:North Carolina State University

关键词: packet scheduling;    networking;    qos;    algorithm;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/4470/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

Many packet scheduling schemes have been proposed, but most of them sufferfrom one of two extremes. A scheduling scheme may have simple implementation withlow fairness qualities, or it may have good fairness qualities but high complexity. Ourgoal in this research is to design a frame work of schedulers that has both the desiredqualities of fairness and simple implementation. We began our research by conducting asurvey of the scheduling techniques and associated analysis models proposed during thelast decade. Then, in the first part of this thesis we present a suite of packet fair queuingschedulers with low complexity and good fairness and delay properties. Our designs employthe 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 ofservice levels, and that a small number of packet sizes dominate. Taken together, these twoobservations permit us to design a good fair queuing algorithm in a manner that packetsorting operations only need to consider a small, fixed number of packets, independentof the number of flows, and hence can be performed in constant time. Specifically, thescheduler we present is equivalent to WF2Q, with the additional advantage that the virtualtime function can be computed in O(1) time. Our tiered-service schedulers operate underassumptions that are valid under a wide range of practical scenarios, and combine provablegood performance with amenability to hardware implementation in high-speed routers. Inthe 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 twomethods 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 thesystem 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.