Elsevier

Automatica

Volume 41, Issue 7, July 2005, Pages 1255-1262
Automatica

Brief paper
A general stability criterion for congestion control with diverse communication delays

https://doi.org/10.1016/j.automatica.2005.02.007Get rights and content

Abstract

A unified duality model is proposed for describing the current Internet congestion control algorithms. Based on this model, the problem of the local asymptotic stability of the congestion control with heterogeneous propagation delays is formulated and solved. A general stability criterion is proved by using the stability theory for quasi-polynomials.

Introduction

Congestion control algorithms for the Internet generally can be classified into two types: primal algorithm and dual algorithm (Kelly et al., 1998, Low and Lapsley, 1999). Roughly speaking, the primal algorithm has a dynamical law for adjusting source rate and a static law for generating link price, and conversely, the dual algorithm has a dynamical law for adjusting link price and a static law for generating source rate. It has been shown recently that these two kinds of algorithms properly describe currently used congestion avoidance protocols for TCP rate control at sources and active queue management (AQM) at links (Low et al., 2002, Kelly, 2003, Low and Srikant, 2003).

Both primal and dual algorithms have their own advantages and shortcomings. For example, the primal algorithm allows general utility functions, and hence arbitrary fairness in rate allocation, but gives up tight control on utilization; whereas the dual algorithm can achieve very high utilization but is restricted to a specific class of utility functions (Low & Srikant, 2003). A natural idea for improving the currently used congestion algorithms is to add slow-timescale dynamics at links (for primal algorithm) or at sources (for dual algorithm) in order to achieve both high utilization and arbitrary fairness (Low and Srikant, 2003, Alpcan and Basar, 2002, Wen and Arcak, 2004). This new kind of algorithm is now referred to as the primal–dual algorithm. A duality model was recently proposed by Low (2003) for describing the primal–dual algorithm.

The stability of congestion control is a very important topic and has drawn much attention from researchers. In particular, the problem of the local asymptotic stability under communication delays was firstly studied in Johari and Tan (2001), where they investigated the effect of propagation delays on the stability of the primal algorithm. They gave a nice decomposition of the transfer function matrix of the feedback congestion control system into a product of a diagonal and a Hermitian matrix, and used this to derive some sufficient conditions for the local stability of networks with the same round-trip delays for different TCP connections. For a more general case of networks with heterogeneous round-trip delays, they proposed a conjecture on the local stability of the algorithm. Their conjecture provides an elegant stability criterion which suggests that network stability can be guaranteed by simple, decentralized conditions on end sources and links, i.e., each end system needs knowledge only of its own round-trip delay. Later on, a weaker version of the continuous-time analogue of the conjecture was proved by Massoulie (2002). Vinnicombe (2000) proposed an elegant lemma which relates the eigenloci of the product of a Hermitian matrix and a diagonal matrix to a product of the spectral radius of the Hermitian matrix and the convex hull of the entries of the diagonal matrix. With the help of this lemma and the generalized Nyquist criterion (Desoer & Yang, 1980), Vinnicombe (2000) illustrated the correctness of the continuous-time analogue of the conjecture of Johari and Tan by a graphic method. However, such a graphic method cannot be directly applied to other congestion control algorithms such as primal–dual algorithms (Liu, Başar, & Srikant, 2003), REM algorithm (Athuraliya, Low, Li, & Yin, 2001) because the stability property of a convex combination of two systems is not always guaranteed by its two vertices. By using the clockwise property (Tesi, Vicino, & Zappa, 1992) of Nyquist plots of delayed systems, the original version of Johari and Tan's conjecture in the discrete-time form was completely proved and generalized by Tian and Yang (2004). Then, Tian (2005) and Tian and Chen (2004) analyzed the REM algorithm and the primal–dual algorithm respectively, and found that the clockwise property plus some other nice geometric properties of the dynamics of congestion control algorithms in a certain frequency interval is the prerequisite of the existence of decentralized stability conditions.

The existing papers in the literature on Internet congestion control analyze stability for specific algorithms. To establish some general stability criterion which is independent of specific forms of congestion control algorithms, in this paper we discuss the stability problem for a general duality model. This model unifies different congestion control algorithms discussed in the literature. As a matter of fact, this model can be regarded as a generalization of the duality model proposed by Low (2003). Compared to Low's model, it allows the introduction of internal variables both in link dynamics and in source dynamics while Low's model introduces internal variables only in link dynamics. The key tool for proving our general stability criterion is the notion of the convex direction in the space of stable quasi-polynomials. Using a frequency-domain condition for convex directions (Kharitonov & Zhabko, 1994) and the Vinnicombe's lemma (Vinnicombe, 2000), we develop a methodology to bound the spectrum of the transfer function of the congestion control system inside some region in the complex plane, which does not enclose the point (-1,j0). Then, from the generalized Nyquist criterion of stability, we obtain a rigorous proof of the general stability criterion for networks with diverse round-trip communication delays.

The paper is organized as follows. In Section 2, we present our unified duality model for congestion control. Then we derive the linearized model and give the formulation of the stability problem under communication delays. Section 3 describes the main result—stability criterion for the general primal–dual algorithm in the presence of heterogeneous round-trip delays. The proof of the main result with some preliminary results needed in the proof are collected in Section 4. The conclusion is given in Section 5.

Section snippets

A unified duality model

Consider a communication network with a set of L links shared by a set of S sources. For each lL¯={1,,L}, the index set of sources using link l is denoted by SlS¯={1,,S}. For each iS¯, the index set of links used by source i is denoted by LiL¯. The sets Sl,lL¯, define an L×S routing matrix R={Rli}, whereRli=1ifiSl,0otherwise.

For each link l, we have:

  • aggregate rate of all sources which use link l, denoted by yl (in packet per second);

  • price pl, used to indicate the link congestion.

The

Stability criterion

Denote by GiM the gain margin of stability of the round-trip transfer-function Wi(s)e-Tis, where Wi(s) is defined by (27) and Ti is defined by (30). Actually, GiM for Wi(s)e-Tis is defined byGiM=1/|Wi(jωc(i))|,where ωc(i)>0 is the minimal frequency that satisfies the following equation:Im[Wi(jω)e-jωTi]=0.Note that the Nyquist plot of GiMWi(jω)ejωTi crosses the real axis at (-1,j0) when ω=ωc(i). So we will call GiMWi(s)e-Tisthe normalized round-trip transfer function with delay.

Write GiMWi(s) asG

Convex directions for stable quasi-polynomials

To prove our main result, we need to review the notion of convex directions for stable quasi-polynomials. A quasi-polynomial is an entire function of the formf(s)=p0(s)eτ0s+p1(s)eτ1s++pm(s)eτms=i=0mk=0nakiskeτis,where pi(s), i=0,1,,m, are polynomials with coefficients aikR and τ0<τ1<<τm are real numbers representing delays.

For n0,m>0 and any real vector [τ0,τ1,,τm] with ordered components τ0<τ1<<τm, let Qnm,τ(R) denote the set of all quasi-polynomials defined by (51) with coefficients

Conclusion

In this paper, a unified duality model is proposed for describing the current Internet congestion control algorithms. Based on this model, the problem of the local asymptotic stability of the congestion control with heterogeneous propagation delays is formulated and solved. A general stability criterion is proved by using the stability theory for quasi-polynomials. Finally, we note that the method developed in this paper can be easily extended to discrete-time models for congestion control.

Acknowledgements

The author would like to thank the National Natural Science Foundation of China for Distinguished Young Scholars (under Grant 60425308) and the Doctoral Research Foundation of the Educational Ministry of China (under Grant 20040286004) for financial supports for this work.

Yu-Ping Tian received the bachelor degree from Tsinghua University, Beijing, China, in 1986, Ph.D. degree from Moscow Power Institute, Moscow, USSR, in 1991, and Sc.D. degree from Taganrog State Radio-Engineering University, Taganrog, Russia, in 1996. All his degrees are in Electrical Engineering. Since 1992, he has been with Southeast University, Nanjing, China, and now he is a Professor in the Department of Automatic Control. In 1998 and 2001, he worked as a Senior Visiting Scholar in the

References (19)

  • A. Tesi et al.

    Clockwise property of the Nyquist plot with implications for absolute stability

    Automatica

    (1992)
  • Y.-P. Tian et al.

    Stability of the Internet congestion control with diverse delays

    Automatica

    (2004)
  • Alpcan, T., & Basar, T. (2002). A game-theoretic framework for networking flow control in general topology networks....
  • S. Athuraliya et al.

    Rem: Active queue management

    IEEE Networks

    (2001)
  • C.A. Desoer et al.

    On the generalized Nyquist stability criterion

    IEEE Transactions on Automatic Control

    (1980)
  • R. Johari et al.

    End-to-end congestion control for the internet: Delays and stability

    IEEE/ACM Transactions on Networking

    (2001)
  • Kelly, F. P. (2003). Fairness and stability of end-to-end congestion control for the Internet, 2003. Available:...
  • F.P. Kelly et al.

    Rate control for communication networks: Shadow prices, proportional fairness, and stability

    Journal of Operational Research Society

    (1998)
  • V.L. Kharitonov et al.

    Robust stability of time-delayed systems

    IEEE Transactions on Automatic Control

    (1994)
There are more references available in the full text version of this article.

Cited by (28)

  • Design of robust H∞ fault detection filter for uncertain time-delay systems using canonical form approach

    2016, Journal of the Franklin Institute
    Citation Excerpt :

    Driven by these issues fault detection for dynamical systems has grabbed the attention of researchers and has become an active area of research [2–7]. Time delay very often occurs in various dynamical systems, such as electric, hydraulic and pneumatic networks, long transmission lines, and chemical processes (see [8–11]). Systems like rolling steel mills, conveyor belts and some population models [12,13] possess delays.

  • A family of multi-path congestion control algorithms with global stability and delay robustness

    2014, Automatica
    Citation Excerpt :

    To tackle the case of an arbitrary network with heterogeneous delays, the first consideration is the generalized Nyquist criterion, by which local stability can be obtained through linearized analysis of such systems around the equilibrium point. See the references on this technique and its applications to congestion control (Desoer & Yang, 1980; Han et al., 2006; Kelly, 2003; Kelly & Voice, 2005; Paganini, Doyle, & Low, 2001; Paganini, Wang, Doyle, & Low, 2005; Srikant, 2004; Tian, 2005; Tian & Yang, 2004; Vinnicombe, 2002; Voice, 2007). A significant open challenge is to verify whether the designing criteria derived from such linearized analysis can guarantee the global stability.

  • Hopf bifurcation analysis in a fluid flow model of Internet congestion control algorithm

    2009, Nonlinear Analysis: Real World Applications
    Citation Excerpt :

    Using some discrete-time models, researchers have shown that TCP/RED systems develop chaotic dynamics with variability in RED parameters [8–12]. The local and global stability of the congestion control algorithm with or without communication delays have been studied in [13–25]. Meanwhile, Hopf bifurcation analysis of Internet congestion control systems has also drawn much attention from researchers.

  • Necessary and sufficient conditions for Hopf bifurcation in exponential RED algorithm with communication delay

    2008, Nonlinear Analysis: Real World Applications
    Citation Excerpt :

    Thus, the qualitative analysis of the dynamical behaviors is a necessary step for the practical design and application of AQM schema. Recently, the stability of AQM schema with or without delays has been widely studied by many researchers, and various interesting results have been reported [15,8,26,11,19,3,1,22–24,28,18,2,6,30,13,12]. The primal algorithm for TCP rate control and the dual algorithm for AQM schema have been proven globally asymptotically stable in the absence of delay [15].

  • Stability and Hopf bifurcation analysis in a novel congestion control model with communication delay

    2008, Nonlinear Analysis: Real World Applications
    Citation Excerpt :

    The local asymptotic stability with communication delays was studied by linearizing the model around the equilibrium in [10–12,18,6,15,7]. To establish some general stability criteria, which are independent of specific forms of congestion control algorithms, Tian proposed a unified quality model and proved the local asymptotic stability of the congestion control with heterogeneous delays in [19,21]. Based on the clockwise property of parameterized curves and the general Nyquist criterion, Tian derived the sufficient conditions for local asymptotic stability of the second-order congestion control algorithm [20].

View all citing articles on Scopus

Yu-Ping Tian received the bachelor degree from Tsinghua University, Beijing, China, in 1986, Ph.D. degree from Moscow Power Institute, Moscow, USSR, in 1991, and Sc.D. degree from Taganrog State Radio-Engineering University, Taganrog, Russia, in 1996. All his degrees are in Electrical Engineering. Since 1992, he has been with Southeast University, Nanjing, China, and now he is a Professor in the Department of Automatic Control. In 1998 and 2001, he worked as a Senior Visiting Scholar in the Faculty of Informatics and Communication at Central Queensland University, Australia. In 2002 he worked as a Hwa-Ying Visiting Scholar in the Department of Electrical Engineering and Computer Sciences, University of California at Berkeley. He won the Guan Zhao Zhi Paper Award at the Chinese Control Conference in 1995 and the Best Theory Paper Award at the Third World Congress on Intelligent Control and Automation in 2000. He is the recipient of the Chang Jiang Professorship awarded by the Education Ministry of China and the Distinguished Young Scholar Award of the National Natural Science Foundation of China. His research interests include robust and adaptive control, chaos control and synchronization, analysis and control of communication networks.

This paper was not presented at any IFAC meeting. This paper was recommended for publication in the revised form by Associate Editor I. Paschalidis under the direction of Editor I. Petersen.

View full text