Implementation of expedited forwarding using dynamic hop counts based absolute priority scheduling

As the scalability of implementation of expedited forwarding per hop behavior (EF PHB) becomes a crucial problem in DiffServ framework, the simple FIFO packet scheduling algorithms have been attracting more attention recently. However, the worst end-to-end delay of the FIFO algorithm is proportional to the maximum hop counts of flows. In our study, the hop counts based relative or absolute priority scheduling (HBRP/HBAP) algorithms have been proposed to balance the difference of end-to-end delay of flows that traverse paths of different hop counts, which decrease the worst end-to-end delay bound of the whole domain and improve the maximum allowable network utilization level accordingly. It is too simple for the HBAP algorithm to improve the delay performance perfectly and it is too complex for the HBRP to deploy. In this paper, we propose new dynamic hop counts based absolute priority scheduling algorithms (DHBAP) with similar delay performance to the HRBP while the computational complexity DHBAP is decreased to O(1). The performances of the DHBAP are compared with those of FIFO, HBAP and HBRP algorithms by theoretic analyses and simulation experiments.