Premium
A competitive analysis for retransmission timeout
Author(s) -
Dolev Shlomi,
Kate Michael,
Welch Jennifer L.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199908)34:1<73::aid-net8>3.0.co;2-3
Subject(s) - timeout , retransmission , network packet , computer science , competitive analysis , algorithm , context (archaeology) , line (geometry) , computer network , real time computing , mathematics , upper and lower bounds , mathematical analysis , paleontology , geometry , biology
Protocols that provide reliable communication on top of a network that can lose packets rely on periodically retransmitting packets. The choice of retransmission timeout critically affects system performance. This paper presents a first step toward a theoretical study of the choice of retransmission timeout, based on competitive analysis. In general, competitive analysis compares the performance of an on‐line algorithm to the performance of an optimal off‐line algorithm, which has access to more information. In this context, the job of an algorithm is to choose the retransmission timeout interval; an off‐line algorithm knows the exact message delays, whereas an on‐line algorithm knows only upper and lower bounds on the delays. The performance measure of interest is the expected value of a linear combination of the number of packets used and the amount of time elapsed. An on‐line algorithm for choosing the retransmission timeout is presented that is optimal with respect to the difference between its performance and that of an optimal off‐line algorithm. The algorithm is also analyzed with respect to the ratio of its performance and that of an optimal off‐line algorithm. © 1999 John Wiley & Sons, Inc. Networks 34: 73–80, 1999