Per-flow Queue Scheduling with Pipelined Counting Priority Index

For advanced per-flow service disciplines at high-speed network links, it is essential to maintain priority queues in sorted order. The scalable priority queue implementation requires managing a large number of queues at ever increasing line speeds. In this paper, we propose novel solutions to the management of priority queues using a previously proposed pipelined Counting Priority Index (pCPI) structure. We consider applications in which hundreds of thousands of priority queues may need to be maintained at line rate at each line card. We provide solutions to two specific problems: the mapping of packet departure times into a priority index, and the locating of the priority queue that contains the packet for a given departure time. We show that the pCPI structure can be effectively implemented for scheduling packets that are maintained in a large number of priority queues.