An adaptive timeout algorithm for retransmission across a packet switching network

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.