- 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.
- Back to other
- Back to my home page