research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitlePerformance and stability bounds for dynamic networks
Bibtex cite IDRACTI-RU1-2007-108
Year published 2007
Month April
Volume 67
Number 4
Pages 386-399
Keywords Parallel computing; Networks; Delay bounds; Stability bounds; Adversarial queueing theory
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,ñ)-adversary. We show that the packet delay on DAGs for LIS is upper bounded by O(iwñC) and lower bounded by Ù(iwñC) where i is the level of a node in a DAG (the length of the longest path leading to node v when nodes are ordered by the topological order induced by the graph). In a similar way, we show that the performance of SIS on DAGs is lower bounded by Ù(iwñC), while the existence of a polynomial upper bound for packet delay on DAGs when SIS is used for contention–resolution remains an open problem. We prove that every queueing network running a greedy contention–resolution protocol is stable for a rate not exceeding a particular stability threshold, depending on C and the length of the longest path in the network.
Koukopoulos, Dimitrios
Mavronicolas, Marios
Spirakis, Paul
getPDF.pdf (main file)
Publication ID334