• Competitive analysis of call admission algorithms that allow delay. A. Feldmann, B. M. Maggs, J. Sgall, D. D. Sleator, and A. Tomkins.

  This paper analyzes several simple on-line algorithms for processing requests for connections in distributed networks. These algorithms are called call admission algorithms. Each request comes with a source, a destination, and a bandwidth requirement. The duration of the request may or may not be known when the request is made. The call admission algorithm either schedules the request to begin immediately, schedules it to begin after some delay, or rejects it. We analyze the performance of the algorithms on simple networks such as linear arrays, trees, and networks with small separators. We use three measures to quantify their performance: makespan, maximum response time, and data-admission ratio. Our results include a proof that greedy algorithms are Theta(log N)-competitive with respect to makespan on N-node trees, and a proof that no algorithm is better than Omega(log N)-competitive with respect to data-admission ratio on a linear array, if each request can be delayed for at most some constant times its (known) duration.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page