Optimization of generalized processor sharing using Interleaved Stratified Timer Wheels
Sangam Kumar Chaturvedi · 2011
Packet scheduling algorithms are the main center of attraction in packet switched network. Multiple researches are proposed on to provide fairness and protection to the packet flow through a router, A General Processor Sharing (GPS) has been used as a conceptual scheduler with many desirable properties, GPS supports guaranteed service traffic and to provide best-effort service traffic. A novel data structure called Interleaved Stratified Timer Wheels (ISTW) is introduced. This design enables the construction of a set of novel packet schedulers with effectively constant complexity, constant fairness and delay characteristics in all relevant dimensions. The ISTW data structure is used as a compact and efficient priority queue that enables the virtual traffic shaping necessary for achieving these characteristics. ISTW parallelization of the GPS is done.