direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

All publications

Competitive analysis of call admission algorithms that allow delay
Zitatschlüssel FMSST-CACAAD-95
Autor Feldmann, Anja and Maggs, Bruce and Sgall, Jiri and Sleator, Daniel and Tomkins, Andrew
Jahr 1995
Notiz No. CMU-CS-95-102
Institution Carnegie Mellon University
Zusammenfassung This paper presents an analysis of 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 call admission algorithm decides whether to accept a 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, 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 Θ(log n)-competitive with respect to makespan on n-node trees for arbitrary durations and bandwidth, a proof that on an n-node tree no algorithm can be better than Ω(loglog n / logloglog n)-competitive with respect to makespan, and a proof that no algorithm can be better than Ω(log n)-competitive with respect to call-admission and data-admission ratio on a linear array, if each request can be delayed for at most some constant times its (known) duration.
Typ der Publikation Technical Report
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe