BSFQ: bin sort fair queueing
Proceedings - IEEE INFOCOM - Tập 3 - Trang 1640-1649 vol.3
Tóm tắt
Existing packet schedulers that provide fair sharing of an output link can be divided into two classes: sorted priority and frame-based. Sorted priority methods provide excellent approximation for weighted fair queueing (WFQ) while frame-based methods are more computationally efficient. We present a new packet scheduling algorithm called bin sort fair queueing (BSFQ) that combines the strengths of both type of schedulers. As a result, BSFQ is highly scalable and can provide very good approximation for WFQ. We prove that BSFQ can provide end-to-end delay and fairness guarantees to conformant flows. BSFQ also has a built-in buffer management function that can protect packets of conformant flows from nonconformant traffic. The performance of BSFQ and its ability to detect nonconformant flows are studied using simulations and compared to those of the deficit round robin method.
Từ khóa
#Scheduling algorithm #Delay #Round robin #Processor scheduling #Traffic control #Quality of service #Web and internet services #Clocks #Mathematics #Computer scienceTài liệu tham khảo
rachev, 1991, Probability metrics and the stability of stochastic models, Wiley Series in Probability and Mathematical Statistics
10.1109/INFCOM.2001.916649
10.1109/90.477714
goyal, 0, Determining end-to-end delay bounds in heterogeneous networks, Proc 5th Intl Workshop on Network and Operating System Support for Digital Audio and Video Durham New Hampshire April 18-21 1995, 287
zhang, 1996, WF2Q: Worst-case fair weighted fair queueing, IEEE INFOCOM 1996, 120
10.1109/90.234856
kleinrock, 1975, Queueing Systems Volume 1 Theory
matsufuru, 1999, Efficient fair queueing for ATM networks using uniform round robin, IEEE Infocom 1999 New York March
10.1109/INFCOM.1994.337677
10.1145/103720.103721
10.1109/90.664265
10.1109/5.469298
10.1109/90.502236
10.1145/259380.259482