PMUF: A High-Performance Scheduling Algorithm for DiffServ Classes

The differentiated services (DiffServ) model relies on the per hop behavior (PHB) in each network device to treat packets differently based on packet headerspsila DSCP (DiffServ code point). For each DiffServ compliant router, the scheduling algorithm is critical in implementing PHBs, according to which packets are forwarded. In this paper, we propose the parallel maximum urgency first (PMUF) scheduling algorithm for combined input-crosspoint queued (CICQ) switches to support DiffServ classes. The proposed PMUF algorithm features in a distributed scheduling scheme which can be implemented on each input and each output independently and in parallel. It adopts a two-stage flow control mechanism based on periodic statistic to provide minimum bandwidth guarantees for EF and AF traffic, and uses a priority scheduling mechanism to provide lower delay for EF traffic. The time complexity of PMUF is only O(log N), hence is practical and scalable for high speed application. Simulation results show that PMUF provides minimum bandwidth guarantees for EF and AF traffic and fair bandwidth allocation for BE traffic. PMUF also exhibits better delay performance than existing maximal matching based DiffServ scheduling schemes especially under non-uniform traffic.