Implementation and Performance Analysis of a Packet Scheduler on a Programmable Network Processor

Abstract — The problem of achieving fairness in the allocation of the bandwidth resource on a link shared by multiple flows of traffic has been extensively researched over the last decade. However, as these flows traverse a computer network, they share many different kinds of resources such as links, processor cycles, buffers and battery power, a critical resource in mobile devices. The ultimate goal should hence be overall fairness in the allocation of multiple resources rather than a single specific resource such as link bandwidth. In our earlier work we have presented a novel scheduler called Prediction-based Composite Fair Queueing (PCFQ), which jointly allocates the fair share of the link bandwidth as well as processing resource to all competing flows. Our scheme also uses a simple and adaptive online prediction scheme for reliably estimating the execution times of the incoming data packets. We have demonstrated via simulation experiments that PCFQ can provide much improved Quality of Service (QoS) guarantees as compared to separate bandwidth and processor schedulers. With the rapid increase in the capacity of transmission links, the ease with which a scheduler can be imple-mented in real hardware systems gains paramount importance. In this paper we concentrate on the design and implementation of the PCFQ scheduler in a programmable router. We demonstrate that our scheduler can be easily implemented on an off-the-shelf network processor such as the Intel IXP 2400 board. We also validate our design by carrying out extensive experiments and demonstrate the improved performance achieved by the PCFQ scheduler. The experimental results from the IXP2400 implementation highlight the effectiveness and high performance of this algorithm in a real world system. I