5th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness

Research Article

PMUF: a high-performance scheduling algorithm for DiffServ classes

  • @INPROCEEDINGS{10.4108/ICST.QSHINE2008.3962,
        author={Wang Binqiang and Chen Shuqiao},
        title={PMUF: a high-performance scheduling algorithm for DiffServ classes},
        proceedings={5th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness},
        publisher={ICST},
        proceedings_a={QSHINE},
        year={2010},
        month={5},
        keywords={},
        doi={10.4108/ICST.QSHINE2008.3962}
    }
    
  • Wang Binqiang
    Chen Shuqiao
    Year: 2010
    PMUF: a high-performance scheduling algorithm for DiffServ classes
    QSHINE
    ICST
    DOI: 10.4108/ICST.QSHINE2008.3962
Wang Binqiang1, Chen Shuqiao1
  • 1: National Digital Switch System Engineering & Technology R&D Center (NDSC)

Abstract

The differentiated services (DiffServ) model relies on the Per Hop Behavior (PHB) in each network device to treat packets differently based on packet headers™ 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. Moreover, PMUF exhibits better delay performance than existing maximal matching based DiffServ scheduling schemes especially under non-uniform traffic.