| Competitive Analysis of Call Admission Algorithms that Allow Delay (1995) | |||||||||||||||
Abstract | |||||||||||||||
| This paper presents an analysis of several on-line algorithms, called call admission algorithms, for processing requests for connections in distributed networks. Each request comes with a source, a destination, and a bandwidth requirement. The call admission algorithm decides whether to accept the request, and if so, when to schedule it and which path the connection should use through the network. The duration of the request is unknown to the algorithm when the request is made. We analyze the performance of the algorithms on simple networks such as linear arrays, trees, networks with small separators, and meshes. We use three measures to quantify their performance: network utilization (makespan), call-admission ratio, and data-admission ratio. Our results include proofs that greedy algorithms are \Theta(log n)-competitive with respect to makespan on n-node trees and O(log 2 n)- competitive on n 2 -node meshes for requests with arbitrary durations and bandwidth requirements, a proo... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||