Performance and stability bounds for dynamic networks

Author

Koukopoulos, Dimitrios ; Mavronicolas, Marios ; Spirakis, Paul

Author_Institution

Comput. Technol. Inst., Patras, Greece

fYear

2004

fDate

10-12 May 2004

Firstpage

239

Lastpage

246

Abstract

In this work, we study the impact of dynamically changing link capacities on the delay bounds of LIS (longest-in-system) and SIS (shortest-in-system) protocols on specific networks (that can be modelled as directed acyclic graphs - DAGs) and stability bounds of greedy contention-resolution protocols running on arbitrary networks under the adversarial queueing theory. Especially, we consider the model of dynamic capacities, where each link capacity may take on integer values from [1,C] with C > 1, under a (w,p)-adversary.

Keywords

computer networks; delays; directed graphs; packet switching; protocols; queueing theory; stability; delay bounds; directed acyclic graphs; dynamic networks; dynamically changing link capacities; greedy contention-resolution protocols; integer values; longest-in-system protocols; performance; queueing theory; shortest-in-system protocols; specific networks; stability bounds; Collaborative work; Computer networks; Computer science; Contracts; Delay; Protocols; Queueing analysis; Stability; Stochastic processes; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on

ISSN

1087-4089

Print_ISBN

0-7695-2135-5

Type

conf

DOI

10.1109/ISPAN.2004.1300487

Filename

1300487