Optimization of generalized processor sharing using Interleaved Stratified Timer Wheels

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.