Dynamic TCP acknowledgement and other stories about e/(e-1)

ABSTRACT

We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are well-known to be generalizations of the classical online ski rental problem, however, they appeared to be harder. In this paper, we demonstrate that a number of online algorithms which have optimal competitive ratios of e/(e-1), including these, are fundamentally no more complex than ski rental. Our results also suggest a clear paradigm for solving ski rental-like problems.

REFERENCES

• 1: Susanne Albers, Better bounds for online scheduling, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.130-139, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258566]
• 2: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 3: C. Chekuri , R. Motwani , B. Natarajan , C. Stien, Approximation techniques for average completion time scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Bo Chen , André van Vliet , Gerhard J. Woeginger, A lower bound for randomized on-line scheduling algorithms, Information Processing Letters, v.51 n.5, p.219-222, Sept. 12, 1994 [doi>10.1016/0020-0190(94)00110-3 ]
• 5: Daniel R. Dooly , Sally A. Goldman , Stephen D. Scott, TCP dynamic acknowledgment delay (extended abstract): theory and practice, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.389-398, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276792]
• 6: R. L. Graham. "Bounds for certain multiprocessor anomalies". Bell System Technical Journal, 45:1563-1581, 1966.
• 7: Rudolf Fleischer, On the Bahncard problem, Theoretical Computer Science, v.268 n.1, p.161-174, 10/06/2001 [doi>10.1016/S0304-3975(00)00266-8 ]
• 8: David R. Karger , Steven J. Phillips , Eric Torng, A better algorithm for an ancient scheduling problem, Journal of Algorithms, v.20 n.2, p.400-430, March 1996 [doi>10.1006/jagm.1996.0019 ]
• 9: Anna R. Karlin , Mark S. Manasse , Lyle A. McGeoch , Susan Owicki, Competitive randomized algorithms for non-uniform problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.301-309, January 22-24, 1990, San Francisco, California, United States
• 10: Anna R. Karlin, M. Manasse, L. Rudolph and D. Sleator "Competitive Snoopy Caching," Algorithmica, Special Issue on Parallel and Distributed Computing, Number 3, pp. 79-119, 1988.
• 11: John Noga. Private Communication.
• 12: John Noga and Steven S. Seiden. Private Communication.
• 13: Steven S. Seiden, A guessing game and randomized online algorithms, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.592-601, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335385]
• 14: Jiří Sgall, A lower bound for randomized on-line multiprocessor scheduling, Information Processing Letters, v.63 n.1, p.51-55, July 14, 1997 [doi>10.1016/S0020-0190(97)00093-8 ]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: TCP/IP

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

General Terms:
Algorithms, Measurement, Performance, Standardization, Theory, Verification