On the Scalable Fairness and Efficient Active Queue Management of RED

Abstract

Internet routers generally see packets from a fast flow more often than a slow flow. This suggests that network fairness may be improved without per-flow information. In this paper, we propose a scheme using Most Recently Used List (MRUL)-a list storing statistics of limited active flows that sorted in most recently seen first mode-to improve the fairness of RED. Based on the list, our proposed scheme jointly considers the identification and punish of the fast and unresponsive fast flows, and the protection of slow flows. Its performance improvements are demonstrated with extensive simulations. Different from the previous proposals, the complexity of our proposed scheme is proportional to the size of the MRUL list but not coupled with the queue buffer size or the number of active flows, so it is scalable and suitable for various routers. In addition, another issue we address in this paper is queue management in RED. Specifically, we replace the linear packet dropping function in RED by a judicially designed nonlinear quadratic function, while original RED remains unchanged. We call this new scheme Nonlinear RED, or NLRED. The underlying idea is that, with the proposed nonlinear packet dropping function, packet dropping becomes gentler than RED at light traffic load but more aggressive at heavy load. As a result, at light traffic load, NLRED encourages the router to operate in a range of average queue sizes rather than a fixed one. When the load is heavy and the average queue size approaches the pre-determined maximum threshold (i.e. the queue size may soon get out of control), NLRED allows more aggressive packet dropping to back off from it. Simulations demonstrate that NLRED achieves a higher and more stable throughput than RED and REM. Since NLRED is fully compatible with RED, we can easily upgrade/replace the existing RED implementations by NLRED.

Share and Cite:

H. WANG, X. LIN, K. ZHOU, N. XIE and H. LI, "On the Scalable Fairness and Efficient Active Queue Management of RED," International Journal of Communications, Network and System Sciences, Vol. 2 No. 1, 2009, pp. 73-83. doi: 10.4236/ijcns.2009.21009.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] F. Ren, C. Lin, and X. Huang, “TCC: A two-category classifier for AQM routers supporting TCP flows,” IEEE Communications Letters, Vol. 9, pp. 471-473, 2005.
[2] R. T. Morris, “Scalable TCP congestion control,” Ph. D thesis, Harvard University, 1999.
[3] C. V. Hollot, V. Misra, D. Towsley, et al., “Analysis and design of controllers for AQM routers supporting TCP flows,” IEEE Transactions on Automatic Control, Vol. 47, pp. 945-959, 2002.
[4] M. Nabeshima and K. Yata, “Performance improvement of active queue management with per-flow scheduling,” IEEE Proceedings-Communications, Vol. 152, pp. 797-803, 2005.
[5] Smitha and A. L. N. Reddy, “LRU-RED: An active queue management scheme to contain high bandwidth flows at congested routers,” in Proceedings of IEEE Global Telecommunications Conference 2001 (GLOBECOM ’01), San Antonio, TX, USA, Vol. 1, pp. 2311-2315, November 25-29, 2001.
[6] C. Brandauer, G. Iannaccone, C. Diot, et al., “Comparison of tail drop and active queue management performance for bulk-data and web-like Internet traffic,” in Proceedings of Sixth IEEE Symposium on Computers and Communications 2001, (ISCC ’01), Hammamet, Tunisia, pp. 122-129, July 3-5, 2001.
[7] T. J. Ott, T. V. Lakshman, and L. H. Wong, “SRED: Stabilized RED,” in Proceedings of Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’99), New York, USA, Vol. 3, pp. 1346-1355, March 21-25, 1999.
[8] F. M. Anjum and L. Tassiulas, “Fair bandwidth sharing among adaptive and non-adaptive flows in the Internet,” in Proceedings of Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’99), New York, NY, USA, Vol. 3, pp. 1412-1420, March 21-25, 1999.
[9] D. Lin and R. Morris, “Dynamics of random early detection,” in Proceedings of ACM SIGCOMM ’97, Cannes, France, pp. 127-137, September 14-18, 1997.
[10] R. Mahajan, S. Floyd, and D. Wetherall, “Controlling high-bandwidth flows at the congested router,” in Proceedings of Ninth International Conference on Network Protocols, pp. 192-201, 2001.
[11] M. Christiansen, K. Jeffay, D. Ott, et al., “Tuning RED for web traffic,” in Proceedings of ACM SIGCOMM 2000, Stockholm, Sweden, pp. 139-150, August 28-September 1, 2000.
[12] F. Ren, C. Lin, and X. Huang, “TCC: A two-category classifier for AQM routers supporting TCP flows,” IEEE Communications Letters, Vol. 9, pp. 471-473, 2005.
[13] L. Zhang, S. Shenker, and D. D. Clark, “Observations on the dynamics of a congestion control algorithm: the effects of two-way traffic,” in Proceedings of ACM SIGCOMM ’91, the Conference on Communications Architecture & Protocols, Vol. 1, pp. 133-147, Zurich, Switzerland, September 03- 06, 1991.
[14] S. Floyd, J. Mahdavi, M. Mathis, et al., “An extension to the selective acknowledgement (SACK) option for TCP,” in RFC 2883, 2000.
[15] K. Xu and N. Ansari, “Stability and fairness of rate estimation based AIAD congestion control in TCP,” IEEE Communications Letters, Vol. 9, pp. 378-380, 2005.
[16] T. J. Ott, T. V. Lakshman, and L. H. Wong, “SRED: Stabilized RED,” in Proceedings of Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, (INFOCOM’99), New York, NY, USA, Vol. 3, pp. 1346-1355, March 21-25, 1999.
[17] B. Braden, D. Clark, J. Crowcroft, et al., “Recommendations on queue management and congestion avoidance in the Internet,” in RFC2309, April 1998.
[18] V. Misra, W. B. Gong, and D. Towsley, “Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED,” ACM SIGCOMM Computer Communication Review, Vol. 30, pp. 151-160, 2000.
[19] B. Zheng and M. Atiquzzaman, “DSRED: An active queue management scheme for next generation networks,” in Proceedings of 25th Annual IEEE Conference on Local Computer Networks (LCN’00), Tampa, FL, USA, Vol. 1, pp. 242-251, November 8-10, 2000.
[20] S. Athuraliya, S. H. Low, V. H. Li, et al., “REM: Active queue management,” IEEE Network, Vol. 15, pp. 48-53, 2001.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.