An adaptive timeout algorithm for retransmission across a packet switching network

ABSTRACT

This paper presents and analyses a simple algorithm for setting an adaptive timeout value at a source Host for end-to-end retransmission on a packet-switched connection. The algorithm allows the recipient Host to acknowledge arriving data in either original transmission order or out-of-order. The time out at the source Host is determined from current estimates - using exponentially weighted moving averages - of the mean and variance of successive acknowledgement delays. We show that when these delays are random variables forming certain stationary or non-stationary stochastic processes, the ensuing timeout gives a near-minimum retransmission delay, subject to some specified limit on the amount of unnecessary retransmission. This property is illustrated for a simulated sequence of acknowledgement delays obtained from loop delay measurements.

REFERENCES

• 1: "A Generalised Test Harness for Network Protocols" - N.P. Alfano, M.Sc Thesis and Indra Note 1482, Dept. of Computer Science, University College London, October 1983.
• 2: "TIME SERIES ANALYSIS forecasting and control - Revised Edition" - G.E.P. Box and G.M. Jenkins, publisher Holden-Day, 1976.
• 3: "A Protocol for Packet Network Inter-communication" - V.G. Cerf, R.E. Kahn, IEEE Trans. on Comm. Vol. COM-22 No.5, May 1974, pp.637-648.
• 4: "Datapac Network Overview" - W.W. Clipsham, F.E. Glave, M.L. Narraway, ICCC Toronto 1976, pp.131-135.
• 5: "Prediction by Exponentially Weighted Moving Averages and Related Methods" - D.R. Cox, Journal of the Royal Statistical Soc. Series B, Vol.23, 1961, pp.414-422.
• 6: "The Theory of Stochastic Processes" - D.R. Cox, H.D. Miller, publisher Methuen, 1965.
• 7: "Connection Flow Control is a Wide Area Packet Switching Network" - S.W. Edge, Ph.D Thesis and TR 88, Dept. of Computer Science, University College London, September 1983.
• 8: "Analysis of an Adaptive Timeout Algorithm" - S.W. Edge, Indra Note 1523, Dept. of Computer Science, University College London, January 1984.
• 9: "An Introduction to Probability Theory and Its Applications - Volume 2, 1st Edition" -W. Feller, published by Wiley, 1966.
• 10: "Performance Evaluations in CYCLADES" - M. Gien, J.L. Grange, ICCC September 1978, Kyoto, Japan, pp. 23-32.
• 11: Information processing systems-open systems interconnection-transport protocol specification, ACM SIGCOMM Computer Communication Review, v.12 n.3&4, p.24-67, July/October 1982 [doi>10.1145/1015601.1015603]
• 12: "Queueing Systems Volume 2" - L. Kleinrock, publisher John Wiley, 1976.
• 13: "Optimal Properties of Exponentially Weighted Forecasts" - J.F. Muth, Journal of the American Stat. Assoc. Vol.55, 1960, pp.299-306.
• 14: "DOD Standard Transmission Control Protocol" - J. Postel, IEN 129, Info. Sciences Institute, Univ. of S. Cal., January 1980.
• 15: "Routing in TYMNET" - A. Rajaraman, Eurocomp 78, Wembley, England, May 1978, publisher Online Ltd. Uxbridge, England, pp.9-21.
• 16: "Interprocess Communication Protocols for Computer Networks" - C.A. Sunshine, Tech. Report 105 (Ph.D Thesis), Digital Systems Laboratory, Stanford University, December 1975.
• 17: "A Study in the Analysis of Stationary Time Series - 2nd edition" - H. Wold, publisher Almqvist & Wiksell (Stockholm), 1954.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Design