Dynamic adaptive windows for high speed data networks: theory and simulations

ABSTRACT

Recent results on the asymptotically optimal design of sliding windows for virtual circuits in high speed, geographically dispersed data networks in a stationary environment are exploited here in the synthesis of algorithms for adapting windows in realistic, non-stationary environments. The algorithms proposed here require each virtual circuit's source to measure the round trip response times of its packets and to use these measurements to dynamically adjust its window. Our design philosophy is quasi-stationary: we first obtain, for a complete range of parameterized stationary conditions, the relation, called the “design equation”, that exists between the window and the mean response time in asymptotically optimal designs; the adaptation algorithm is simply an iterative algorithm for tracking the root of the design equation as conditions change in a non-stationary environment. A report is given of extensive simulations of networks with data rates of 45 Mbps and propagation delays of up to 47 msecs. The simulations generally confirm that the realizations of the adaptive algorithms give stable, efficient performance and are close to theoretical expectations when these exist.

REFERENCES

• 1: M. Reiser, "A queueing-network analysis of computer communication networks with window ttow control," IEEE Trans. Comm., COM-27, 1979. pp. 11#-1209.
• 2: Mischa Schwartz, Telecommunication networks: protocols, modeling and analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 4: D. Bertsekas and R. Gallager, Data Ne#ork..~, Prentice Hall, Englewood Cliffs, NJ, 1987.
• 5: $. P. Morgan, "Window flow control on a trunked byte-stream virtual circuit," IEEE Trans. Commun., COM-36, July 1988, pp. 816-825.
• 6: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 7: P. Karn , C. Partridge, Improving round-trip time estimates in reliable transport protocols, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.2-7, August 11-13, 1987, Stowe, Vermont, United States
• 8: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer, Symposium proceedings on Communications architectures and protocols, p.303-313, August 16-18, 1988, Stanford, California, United States
• 9: R. Jain. "A delay-based approach for congestion avoidance in interconnected heterogeneous computer networks," Report DEC-TR-556, 1988, Digital Equipment Corp.
• 10: D. Mitra. "Optimal design of windows for high speed data networks," Prec. IEEE INFOCOM'90, IEEE Computer Society Press, 1990, pp. 1156-1163. This paper reports partial results fa'om "Optimal design of congestion control for high speed data networks," AT&T Bell Laboratories report, 1989, submitted for publication.
• 11: R. Jain , K. K. Ramakrishnan , D.-M. Chiu, Congestion avoidance in computer networks with a connectionless network layer, Innovations in Internetworking, Artech House, Inc., Norwood, MA, 1988
• 12: L. Zhang, A New Architecture for Packet Switching Network Protocols, MIT Ph.D. thesis, Laboratory for Computer Science, Cambridge, Mass., 02139.
• 13: A. E. Eckberg, D. T. Luan and D. M. Lucantoni, "Bandwidth management: a congestion control strategy for broadband packet networks: characterizing the thtoughput-bursdness filter," Prec. 1TC Specialist Seminar, Adelaide., 1989, paper no. 4.4.
• 14: J. McKerma, D. Mitra and K. G. Ramakrishnan, "A class of closed Markovian queueing networks: integral representations, asymptotic expansions and generalizations," Bell System Tech. L, 60, 1981, pp. 599-641.
• 15: J. McKenna , Debasis Mitra, Asymptotic Expansions and Integral Representations of Moments of Queue Lengths in Closed Markovian Networks, Journal of the ACM (JACM), v.31 n.2, p.346-360, April 1984 [doi>10.1145/62.322432]
• 16: D. Mitra and K. G. Ramakrishnan, "A numerical investigation on the optimal design of congestion controls for high speed data networks," Prec. ICCC. New Delhi, 1990.
• 17: A. Giessler, J. Hanle, A. Konig and E. Pade, "Free buffer allocation- an investigation by simulation," Comput. Networks, 2, 1978.
• 18: L. Kleinrock. "'On detemdnistic rules for probabilisdc problems in computer communications," Proc. ICC, vol. 3, June 1979.
• 19: D. Mitra and I. Mitrani, "Asymptotic optimality of the go-back-n protocol in high speed data networks with small buffers," Prec. Fourth International Conf. on Data Communications Systems and Their Performance, IHP, Barcelona, June 1990, pp. 17-31.
• 20: K. G. Ramakrishnan and D. Mi{ra, "PANACEA: An integrated set of tools for performance analysis," in Modelling Techniques and Tools for Computer Evaluations, F,d. R. Puigjanet and D. Potier, Plenum Press. N.Y. 1988.
• 21: J.B. Seery, "Customizing PANACEMSimulation," internal AT&T Bell Laboratories memorandum.
• 22: D. Mitra and J. B. Seery, "Dynamic Adaptive Windows for High Speed Data Networks: Theory and Simulations," AT&T Bell Laboratories report, April 1990, submitted for publication.

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; Network communications

General Terms:
Algorithms, Design, Theory