A composite scheduling algorithm for programmable networks

In today´s Internet, packet processing may be accomplished in the routers within the data path. For efficient resource allocation in such routers, the packet scheduling schemes should consider multiple resources such as CPU and memory in addition to the bandwidth to improve overall performance. The dynamic nature of network load and the inherent unpredictability of processing times of data packets pose a significant challenge for CPU scheduling, which in turn also limits the application of well-known bandwidth scheduling algorithms. This paper presents a new composite scheduling algorithm called prediction-based composite fair queueing (PCFQ), which is designed to schedule both bandwidth and CPU resources adaptively, fairly, and efficiently among all the competing flows. PCFQ is the first scheduler to have the following properties: (1) a very new idea of combining both CPU and bandwidth scheduling functionalities under a single scheduling scheme that can provide better QoS guarantees to the data flows competing for both processing and bandwidth resources; and (2) a simple and adaptive online prediction scheme for the scheduling algorithm for reliably estimating the execution times of the incoming data packets. Through simulation and analysis we show that PCFQ can provide significantly better delay guarantees than those achievable through separate CPU and bandwidth schedulers.