Drop Tail and Red Queue Management with Small Buffers: Stability and HOPF Bifurcation

Ganesh Patil; Sally McClean; Gaurav Raina

Drop Tail and Red Queue Management with Small Buffers: Stability and HOPF Bifurcation

Ganesh Patil, Sally McClean, Gaurav Raina

Research output: Contribution to journal › Article › peer-review

Abstract

There are many factors that are important in the design of queue management schemes for routers in the Internet: for example, queuing delay, link utilization, packet loss, energy consumption and the impact of router buffer size. By considering a fluid model for the congestion avoidance phase of Additive Increase Multiplicative Decrease (AIMD) TCP, in a small buffer regime, we argue that stability should also be a desirable feature for network performance. The queue management schemes we study are Drop Tail and Random Early Detection (RED). For Drop Tail, the analytical arguments are based on local stability and bifurcation theory. As the buffer size acts as a bifurcation parameter, variations in it can readily lead to the emergence of limit cycles. We then present NS2 simulations to study the effect of changing buffer size on queue dynamics, utilization, window size and packet loss for three different flow scenarios. The simulations corroborate the analysis which highlights that performance is coupled with the notion of stability. Our work suggests that, in a small buffer regime, a simple Drop Tail queue management serves to enhance stability and appears preferable to the much studied RED scheme.

Original language	English
Pages (from-to)	339-344
Journal	ICTACT Journal on Communication Technology
Volume	2
Issue number	2
Publication status	Published (in print/issue) - Jun 2011

Bibliographical note

Reference text: [1] G. Appenzeller, “Sizing Router Buffers”, Ph.D. diss., Department of Computer Science, Stanford Univ, 2004.
[2] B. Braden, et al., “Recommendations on queue management and congestion avoidance in the Internet”, RFC 2309, IETF, 1998.
[3] S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance”, IEEE/ACM Trans. on Networking, Vol.1, No. 4, pp. 397–413, 1993.
[4] Ganesh, N. O’Connell, and D. Wischik, “Big Queues,”
Lecture Notes in Mathematics, Springer, 2004.
[5] B.D. Hassard, N.D. Kazarinoff, and Y. Wan, “Theory and applications of Hopf bifurcation,” Cambridge: Cambridge University Press, 1981.
[6] P.G. Kulkarni, S.I. McClean, G.P. Parr, and M.M. Black, “Lightweight proactive queue management,” IEEE Trans. on Network and Service Management, Vol. 3, No. 2,
pp. 1-11, 2006.
[7] G. Raina, “Local bifurcation analysis of some dual congestion control algorithms,” IEEE Trans. on Automatic Control, Vol. 50, No. 8, pp. 1135–1146, 2005.
[8] G. Raina, D. Towsley, and D. Wischik, “Part II: Control theory for buffer sizing,” ACM SIGCOMM Trans. Computer Communication Review, Vol. 35, No. 3,
pp.79–82, 2005.
[9] G. Raina and D. Wischik, “Buffer sizes for large multiplexers: TCP queueing theory and instability analysis,” in Proc. of EuroNGI Conference on Next Generation Internet, 2005.
[10] K.K. Ramakrishnan, S. Floyd, and D. Black, “The addition of Explicit Congestion Notification (ECN) to IP,” RFC 3168, Proposed Standard, 2001.
[11] Ramamurthy, G.N. Rouskas and K. Sivalingam, Eds., “Next-Generation Internet: Architectures and Protocols,” New York: Cambridge University Press, 2011.
[12] Wischik and N. McKeown, “Part I: Buffer sizes for core routers,” ACM SIGCOMM Trans. Computer Communication Review, Vol. 35, No. 2, pp. 75–78, 2005.
[13] NS2, “The Network Simulator NS2 homepage.” Available at: http://www.isi.edu/nsnam/ns/. Accessed 1 April 2011.

Keywords

TCP
Queue Management
Small Buffers
Performance.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Cite this

@article{c8b6adf4e8c34ae2bb0c659cdb1deb46,

title = "Drop Tail and Red Queue Management with Small Buffers: Stability and HOPF Bifurcation",

abstract = "There are many factors that are important in the design of queue management schemes for routers in the Internet: for example, queuing delay, link utilization, packet loss, energy consumption and the impact of router buffer size. By considering a fluid model for the congestion avoidance phase of Additive Increase Multiplicative Decrease (AIMD) TCP, in a small buffer regime, we argue that stability should also be a desirable feature for network performance. The queue management schemes we study are Drop Tail and Random Early Detection (RED). For Drop Tail, the analytical arguments are based on local stability and bifurcation theory. As the buffer size acts as a bifurcation parameter, variations in it can readily lead to the emergence of limit cycles. We then present NS2 simulations to study the effect of changing buffer size on queue dynamics, utilization, window size and packet loss for three different flow scenarios. The simulations corroborate the analysis which highlights that performance is coupled with the notion of stability. Our work suggests that, in a small buffer regime, a simple Drop Tail queue management serves to enhance stability and appears preferable to the much studied RED scheme.",

keywords = "TCP, Queue Management, Small Buffers, Performance.",

author = "Ganesh Patil and Sally McClean and Gaurav Raina",

note = "Reference text: [1] G. Appenzeller, “Sizing Router Buffers”, Ph.D. diss., Department of Computer Science, Stanford Univ, 2004. [2] B. Braden, et al., “Recommendations on queue management and congestion avoidance in the Internet”, RFC 2309, IETF, 1998. [3] S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance”, IEEE/ACM Trans. on Networking, Vol.1, No. 4, pp. 397–413, 1993. [4] Ganesh, N. O{\textquoteright}Connell, and D. Wischik, “Big Queues,” Lecture Notes in Mathematics, Springer, 2004. [5] B.D. Hassard, N.D. Kazarinoff, and Y. Wan, “Theory and applications of Hopf bifurcation,” Cambridge: Cambridge University Press, 1981. [6] P.G. Kulkarni, S.I. McClean, G.P. Parr, and M.M. Black, “Lightweight proactive queue management,” IEEE Trans. on Network and Service Management, Vol. 3, No. 2, pp. 1-11, 2006. [7] G. Raina, “Local bifurcation analysis of some dual congestion control algorithms,” IEEE Trans. on Automatic Control, Vol. 50, No. 8, pp. 1135–1146, 2005. [8] G. Raina, D. Towsley, and D. Wischik, “Part II: Control theory for buffer sizing,” ACM SIGCOMM Trans. Computer Communication Review, Vol. 35, No. 3, pp.79–82, 2005. [9] G. Raina and D. Wischik, “Buffer sizes for large multiplexers: TCP queueing theory and instability analysis,” in Proc. of EuroNGI Conference on Next Generation Internet, 2005. [10] K.K. Ramakrishnan, S. Floyd, and D. Black, “The addition of Explicit Congestion Notification (ECN) to IP,” RFC 3168, Proposed Standard, 2001. [11] Ramamurthy, G.N. Rouskas and K. Sivalingam, Eds., “Next-Generation Internet: Architectures and Protocols,” New York: Cambridge University Press, 2011. [12] Wischik and N. McKeown, “Part I: Buffer sizes for core routers,” ACM SIGCOMM Trans. Computer Communication Review, Vol. 35, No. 2, pp. 75–78, 2005. [13] NS2, “The Network Simulator NS2 homepage.” Available at: http://www.isi.edu/nsnam/ns/. Accessed 1 April 2011.",

year = "2011",

month = jun,

language = "English",

volume = "2",

pages = "339--344",

journal = "ICTACT Journal on Communication Technology",

issn = "2229-6948",

publisher = "ICT Academy",

number = "2",

}

TY - JOUR

T1 - Drop Tail and Red Queue Management with Small Buffers: Stability and HOPF Bifurcation

AU - Patil, Ganesh

AU - McClean, Sally

AU - Raina, Gaurav

N1 - Reference text: [1] G. Appenzeller, “Sizing Router Buffers”, Ph.D. diss., Department of Computer Science, Stanford Univ, 2004. [2] B. Braden, et al., “Recommendations on queue management and congestion avoidance in the Internet”, RFC 2309, IETF, 1998. [3] S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance”, IEEE/ACM Trans. on Networking, Vol.1, No. 4, pp. 397–413, 1993. [4] Ganesh, N. O’Connell, and D. Wischik, “Big Queues,” Lecture Notes in Mathematics, Springer, 2004. [5] B.D. Hassard, N.D. Kazarinoff, and Y. Wan, “Theory and applications of Hopf bifurcation,” Cambridge: Cambridge University Press, 1981. [6] P.G. Kulkarni, S.I. McClean, G.P. Parr, and M.M. Black, “Lightweight proactive queue management,” IEEE Trans. on Network and Service Management, Vol. 3, No. 2, pp. 1-11, 2006. [7] G. Raina, “Local bifurcation analysis of some dual congestion control algorithms,” IEEE Trans. on Automatic Control, Vol. 50, No. 8, pp. 1135–1146, 2005. [8] G. Raina, D. Towsley, and D. Wischik, “Part II: Control theory for buffer sizing,” ACM SIGCOMM Trans. Computer Communication Review, Vol. 35, No. 3, pp.79–82, 2005. [9] G. Raina and D. Wischik, “Buffer sizes for large multiplexers: TCP queueing theory and instability analysis,” in Proc. of EuroNGI Conference on Next Generation Internet, 2005. [10] K.K. Ramakrishnan, S. Floyd, and D. Black, “The addition of Explicit Congestion Notification (ECN) to IP,” RFC 3168, Proposed Standard, 2001. [11] Ramamurthy, G.N. Rouskas and K. Sivalingam, Eds., “Next-Generation Internet: Architectures and Protocols,” New York: Cambridge University Press, 2011. [12] Wischik and N. McKeown, “Part I: Buffer sizes for core routers,” ACM SIGCOMM Trans. Computer Communication Review, Vol. 35, No. 2, pp. 75–78, 2005. [13] NS2, “The Network Simulator NS2 homepage.” Available at: http://www.isi.edu/nsnam/ns/. Accessed 1 April 2011.

PY - 2011/6

Y1 - 2011/6

N2 - There are many factors that are important in the design of queue management schemes for routers in the Internet: for example, queuing delay, link utilization, packet loss, energy consumption and the impact of router buffer size. By considering a fluid model for the congestion avoidance phase of Additive Increase Multiplicative Decrease (AIMD) TCP, in a small buffer regime, we argue that stability should also be a desirable feature for network performance. The queue management schemes we study are Drop Tail and Random Early Detection (RED). For Drop Tail, the analytical arguments are based on local stability and bifurcation theory. As the buffer size acts as a bifurcation parameter, variations in it can readily lead to the emergence of limit cycles. We then present NS2 simulations to study the effect of changing buffer size on queue dynamics, utilization, window size and packet loss for three different flow scenarios. The simulations corroborate the analysis which highlights that performance is coupled with the notion of stability. Our work suggests that, in a small buffer regime, a simple Drop Tail queue management serves to enhance stability and appears preferable to the much studied RED scheme.

AB - There are many factors that are important in the design of queue management schemes for routers in the Internet: for example, queuing delay, link utilization, packet loss, energy consumption and the impact of router buffer size. By considering a fluid model for the congestion avoidance phase of Additive Increase Multiplicative Decrease (AIMD) TCP, in a small buffer regime, we argue that stability should also be a desirable feature for network performance. The queue management schemes we study are Drop Tail and Random Early Detection (RED). For Drop Tail, the analytical arguments are based on local stability and bifurcation theory. As the buffer size acts as a bifurcation parameter, variations in it can readily lead to the emergence of limit cycles. We then present NS2 simulations to study the effect of changing buffer size on queue dynamics, utilization, window size and packet loss for three different flow scenarios. The simulations corroborate the analysis which highlights that performance is coupled with the notion of stability. Our work suggests that, in a small buffer regime, a simple Drop Tail queue management serves to enhance stability and appears preferable to the much studied RED scheme.

KW - TCP

KW - Queue Management

KW - Small Buffers

KW - Performance.

M3 - Article

SN - 2229-6948

VL - 2

SP - 339

EP - 344

JO - ICTACT Journal on Communication Technology

JF - ICTACT Journal on Communication Technology

IS - 2

ER -

Drop Tail and Red Queue Management with Small Buffers: Stability and HOPF Bifurcation

Abstract

Bibliographical note

Keywords

UN SDGs

Fingerprint

Cite this