Study On Dynamics Of Internet Congestion Control Algorithms

With the rapid development of the technique of communication networks, especially the Internet, and the increase of the requirement for networks, it becomes more and more crucial to provide congestion control and avoidance algorithms and to analyze the dynamics of these algorithms. From the point of view of the control theory, Internet can be considered as a dynamic nonlinear feedback system with communication delays, whose internal state is decided by the TCP congestion avoidance algorithms at sources and the active queue management (AQM) schemes at link nodes. By choosing Kelly's primal algorithm and REM scheme as investigation representations, this dissertation has studied thoroughly TCP algorithms and AQM schemes of Internet network. Based on the general Nyquist criterion and Lyapunov method in the control theory, the stability of the Internet congestion control algorithms (ICCA) is analyzed. In addition, by applying the Hopf bifurcation theorem and the normal form theory, the dynamics of the time-delayed congestion control system have been investigated when the stability conditions of the algorithms are broken. The main contributions of the research work presented in this dissertation are as follows:1. The locally asymptotical stability of a class of Internet congestion control algorithms, namely Kelly's primal algorithm, with communication delays, is studied. Based on the clockwise property of parameterized curves and the general Nyquist criterion of stability, the features of the frequency function of the delay-differential equation in discrete time system are analyzed. A conjecture on the stability of the ICCA with heterogeneous delays is proved, and a more general stability criterion is also presented. The new criterion preserves the elegancy of the conjecture being decentralized and locally implemented: each end system needs knowledge only of its own round-trip delay, but enlarges the stability region of control gains and admissible communication delays.2. The global asymptotical stability of the delayed Kelly's primal algorithm with a single link accessed by a single source is studied. Based on the Lyapunov-Razumikhin theorem of the delay-differential equation and Barbalat Lemma, a criterion of the global stability is established by applying the Lyapunov direct method. Compared withthose existed conclusions, the new theorem presents a definite upper bound for the delay, and enlarges the permitting delay to ensure the global asymptotical stability.3. The dynamics of Kelly's primal algorithm is investigated when the stability conditions are broken. By choosing the communication delay as a bifurcation parameter, the Hopf bifurcation of Kelly's primal algorithm with a single link and a single source is discussed. Formulas to determine the stability of bifurcating periodic solutions are obtained by applying the center manifold theorem and the normal form theory. These conclusions can explain perfectly the role of the delay in Internet and the sensitivity of the network parameter in the practical network.4. A class of Internet AQM schemes, namely REM (Random Exponential Marking) algorithm, with communication delays, is studied. REM algorithm, by decoupling the equilibrium value of congestion measure and that of performance measure, achieves high utilization with low loss and delay at equilibrium. Since REM algorithm with communication delays is a retarded multivariable feedback system, the stability of such an algorithm is an open difficult problem. By studying the frequency properties of the second-order delayed differential equation, a criterion on the local asymptotical stability at the equilibrium point of the REM algorithm with heterogeneous delays is obtained. This provides a solid theoretic foundation for designing the network parameters of REM algorithm.5. The bifurcation of the REM algorithm with communication delay is researched. By choosing the delay constant as a bifurcation parameter, it is proved that REM algorithm exhibits Hopf bifurcation. Formulas for determining the direction of the Hopf bifurcation and the stability of bifurcating periodic solutions are presented by applying the center manifold theorem and the normal form theory. These results show that the communication delay is one of the important factors to affect Internet capability, and the quality of service of Internet can be improved by choosing efficient control methods.