Warp control: a dynamically stable congestion protocol and its analysis

ABSTRACT

This paper presents a distributed, end-to-end congestion control protocol for use in high-traffic packet switched networks. The network is represented as a stochastic single-server queue, with arrival rates being the control variables. A time-stamp based measure of network state called warp is defined, and it is shown to be an estimator of network utilization. Congestion is modeled explicitly using unimodal load-service rate functions, and its monotonicity property is exploited to yield characterizations of stability and optimality. A protocol based on "perfect" information is analyzed, whose prowess is then shown to be emulated by one which only uses locally computable, delayed information. The main effect of a unimodal load-service function is to induce a division of the phase space into stable and unstable regions, the optimal operating point being its "boundary." Protocols are devised for dealing with each regime separately, rate adjustment protocol being the control that guides the system to the optimal operating point. Proactive rate protocol and reactive rate protocol deal with the issue of the optimal operating point being near to the unstable zone. Protocols for handling fairness and structural perturbation augment the basic suite. The analysis is supported by simulations showing the global dynamical properties of the system.

REFERENCES

• 1: Ludwig Arnold. Stochastic Differential Equations: Theory and Applications. John Wiley & Sons, 1974.
• 2: K. Bala, I. Cidon, and K. Sohraby. Congestion control for high speed packet switched networks, in Proc. IEEE INFOCOM '90, pages 520-526, 1990.
• 3: Jean-Chrysostome Bolot , A. Udaya Shankar, Analysis of a fluid approximation to flow control dynamics, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.2398-2407, May 1992, Florence, Italy
• 4: 1%. Dighe, C. J. May, and G. Ramamurthy. Congestion avoidance strategies in broadband packet networks. In Proc. IEEE INFOCOM '91, pages 295-303, 1991.
• 5: Kerry W. Fendick , Manoel A. Rodrigues , Alan Weiss, Analysis of a rate-based control strategy with delayed feedback, Conference proceedings on Communications architectures & protocols, p.136-148, August 17-20, 1992, Baltimore, Maryland, United States
• 6: M. Gerla and L. Kleinrock. Flow control: a comparative survey. IEEE Trans. Commun., COM- 28:553-574, 1980.
• 7: Z. Haas and J. Winters. Congestion control by adaptive admission. In Proc. IEEE INFOCOM '91, pages 560-569, 1991.
• 8: Jack K. Hale. Functional Differential Equations. Springer-Verlag, 1971.
• 9: A. Heddaya, K. Park, and H. Sinha. Using warp to control network contention in mermera. Submitted to HiC$S 'gd, 1993.
• 10: A. Hordijk and F. Spieksma. Constrained admission control to a queueing system. Adv. Appl. Prob., 21:409-431, 1989.
• 11: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 12: F. P. Kelly. The optimization of queueing and loss networks. In O. J. Boxma and R. Syski, editors, Queueing Theory and its Applications. North- Holland, 1988.
• 13: Srinivasan Keshav, A control-theoretic approach to flow control, Proceedings of the conference on Communications architecture & protocols, p.3-15, September 03-06, 1991, Zurich, Switzerland
• 14: Hiroshi Kobayashi , Mario Gerla, Optimal routing in closed queuing networks, ACM Transactions on Computer Systems (TOCS), v.1 n.4, p.294-310, Nov. 1983 [doi>10.1145/357377.357381]
• 15: D. Mitra , J. B. Seery, Dynamic adaptive windows for high speed data networks: theory and simulations, Proceedings of the ACM symposium on Communications architectures & protocols, p.30-40, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 16: S-E A. Mohammed. Stochastic functional differorbital equations, volume 99 of Research Notes in Mathematics. Pitman Advanced Publishing Program, 1984.
• 17: Amarnath Mukherjee , John C. Strikwerda, Analysis of dynamic congestion control protocols: a Fokker-Planck approximation, Proceedings of the conference on Communications architecture & protocols, p.159-169, September 03-06, 1991, Zurich, Switzerland
• 18: G. F. Newell. Applications of Queueing Theory. Chapman and Hall, 2nd edition, 1982.
• 19: J. Robinson , Dan Friedman , Martha Steenstrup, Congestion control in BBN packet-switched networks, ACM SIGCOMM Computer Communication Review, v.20 n.1, p.76-90, Jan. 1990 [doi>10.1145/86587.86592]
• 20: S. Shenker, A theoretical analysis of feedback flow control, Proceedings of the ACM symposium on Communications architectures & protocols, p.156-165, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 21: Y. T. Wang , B. Sengupta, Performance analysis of a feedback congestion control policy under non-negligible propagation delay, Proceedings of the conference on Communications architecture & protocols, p.149-157, September 03-06, 1991, Zurich, Switzerland

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

General Terms:
Design, Measurement, Performance