High-performance packet scheduling to provide relative delay differentiation in future high-speed networks

Due to significant advances in interconnection networks and optical technologies, line rate for future high-speed networks can upgrade to terabits per second (Tb/s). Reduction of computational overhead and decrease of packet queueing delay are two critical issues in the design of a packet scheduler for efficiently delivering relative differentiated services over such high-speed networks. In this paper, we propose a new packet scheduler called multi-level dynamic deficit round-robin (MLDDRR). MLDDRR considers packet size and priority at the same time in making scheduling decision. Thus, MLDDRR can deliver relatively small delays not only for traffic of high priority but also for short packets of each class. Because MLDDRR acts like the shortest job first scheduler, MLDDRR can reduce average queueing delay for each class and also provide a better service for real-time applications with a large amount of short packets. MLDDRR also exploits concurrency and pipelining approach to speedup scheduling decision. Furthermore, MLDDRR can protect the traffic of the highest priority from serious performance degradation due to bursts of low priority traffic or high link utilization, and simultaneously prevent the traffic of the lowest priority from starvation. MLDDRR allows network operators to simply change the level of delay differentiation by adjusting parameters. Complexity analysis and extensive simulation results are presented and illustrate that MLDDRR is a high-performance packet scheduler and suitable for being deployed in future high-speed networks to provide relative delay differentiated service.