Self-Configured Fair Queueing

Abstract

Many core-stateless mechanisms have been proposed to resolve the scalability problem in the core routers. However, they place considerable reliance on the edge routers or anterior core routers to mark correct flow information in corresponding packets. As a result, the condition of incorrect flow information may severely degrade the fairness among different flows. To achieve the robust fairness, an approximately core-stateless fair sharing mechanism, self-configured fair queuing (SCFQ) is proposed in this paper. This mechanism is mainly composed of two rate estimators; one estimator is used to estimate the arrival rate of the malicious flows that can be adopted to emend the incorrect flow information of the arrival packets. The other one is used to estimate the fair share rate. Computer Simulation is applied to compare the fairness of the SCFQ, core-stateless fair queuing (CSFQ), linear fair sharing estimation (LFSE), deficit round robin (DRR), and first in first out (FIFO). From the simulation results, the SCFQ is capable of supporting much better fairness than that of other compared mechanisms under a variety of traffic conditions. Also, the overhead of the SCFQ is low, so it is very suitable to be deployed in high-speed core routers.

Keywords

Self-configured robust core-stateless fairness scalability

Get full access to this article

View all access options for this article.

References

Braden, B. , Clark, D. , Crowcroft, J. , Davie, B. , Deering, S. , Estrin, D. , Floyd, S. , Jacobson, V. , Minshall, G. , Partridge, C. , Peterson, L. , Ramakri, K. , Shenker S. , Wroclawski J. , and Zhang, L. 1998. Recommendations on queue management and congestion avoidance in the Internet, IETF RFC 2309.

Mankin, A. , and Ramakrishnan K. 1991. Gateway congestion control survey, IETF RFC 1254.

Parekh, A. , and R. Gallager. 1993. A generalized processor sharing approach to flow control: the single node case. IEEE/ACM Transactions on Networking 1(3):344—57.

Hasegawa, G. , T. Matsuo , M. Murata , and H. Miyahara. 2000. Comparisons of packet scheduling algorithms for fair service among connections on the Internet. In Proceedings of IEEE INFOCOM, pp. 1253—62.

Shreedhar, M. , and G. Varghese. 1996. Efficient fair queuing using deficit round-robin. IEEE/ACM Transactions on Networking 4(3):375—85.

Hasegawa, G. , and M. Murata. 2001. Survey on fairness issues in TCP congestion control mechanisms. IEICE Transactions on Communications E84-B(6):1461—72.

Lin, D. , and R. Morris. Dynamics of random early detection. In Proceedings of ACM SIGCOMM, 1997, pp. 127—37.

Anjum, F.M. , and L. Tassiulas. 1999. Fair bandwidth sharing among adaptive and non-adaptive flows in the Internet. In Proceedings of IEEE INFOCOM, pp. 1412—20.

Stoica, I. , S. Shenker , and H. Zhang. 2003. Core-stateless fair queueing: a scalable architecture to approximate fair bandwidth allocations in high-speed networks. IEEE/ACM Transactions on Networking 11(1):33—46.

10.

Floyd, S. , and V. Jacobson. 1993. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking 1(4):397—413.

11.

Yang, J.P. , M.C. Liang , and Y.S. Chu. 2004. Linear fair sharing estimation. In Proceedings of WTC/ISS2004, pp. 10—15.

12.

Cao, Z. , Z. Wang , and E. Zegura. 2000. Rainbow fair queueing: fair bandwidth sharing without per-flow state. In Proceedings of IEEE INFOCOM, pp. 922—31.

13.

Kurimoto, T. , T. Shimizu , and R. Kawamura. 2001. Core-stateless RED algorithm for improving fairness in a best-effort network. IEICE Transactions on Communications E84-B(5):1413— 21.

14.

Pan, R. , B. Prabhakar , and K. Psounis. 2000. CHOKEs: a stateless active queue management scheme for approximating fair bandwidth allocation. In Proceedings of the IEEE INFOCOM, pp. 942—51.

15.

Stoica, I. , H. Zhang , and S. Shenker. 2002. Self-verifying CSFQ. In Proceedings of IEEE INFOCOM, pp. 21—30.

16.

Zheng, J. , M. Hu , and L. Zhao. 2005. Enhancing Internet robustness against malicious flows using active queue management. In Proceedings of ICESS, pp. 501—6.

17.

Chu, Y.S. , J.P. Yang , C.S. Wu , and M.C. Liang. 2002. Partial sharing and partial partitioning buffer management scheme for shared buffer packet switches. IEICE Transactions on Communications E85-B(1):79—88.

18.

Yang, J.P. 2004. Performance analysis of threshold-based selective drop mechanism for high performance packet switches. Performance Evaluation 89—103.

19.

Paxson, V. , and S. Floyd. 1994. Wide-area traffic: the failure of Poisson modeling. In Proceedings of ACM SIGCOMM, pp. 257— 68.

20.

Dill, S. , Kumar, R. , McCurley, K. , Rajagopalan, S. , Sivakumar, D. , and Tomkins, A. 2002. Self-similarity in the web, ACM Trans. Internet Technology, 2(3): 205—223.