ALCOMFT-TR-03-136

Dimitrios Koukopoulos, Marios Mavronicolas and Paul Spirakis
Performance and Stability Bounds for Dynamic Networks
Patras and Cyprus. Work packages 2 and 4. December 2003.

Abstract: In this work, we study the impact of dynamically changing link capacities on the performance 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,\rho)-adversary. The stability of a greedy protocol guarantees that the number of packets in the network remains bounded at all times. However, it does not guarantee the existence of small bounds on the packet delay. We therefore show:

• The packet delays on DAGs for LIS is upper bounded by O(iw \rho C) where i is the length of the longest path leading to a node when nodes are ordered by the topological order induced by the DAG.

• Complementarily, the performance of LIS on DAGs is lower bounded by Omega(iw \rho C) through an involved combinatorial construction. Therefore, we show tight performance bounds for LIS on DAGs. In a similar way, we show that the performance of SIS on DAGs is lower bounded by Omega(iw \rho C).

• Any arbitrary network G (possibly cyclic) running a greedy protocol is stable for a rate not exceeding a particular stability threshold, depending on C and the length d( G) of the longest path in the network.

Postscript file: ALCOMFT-TR-03-136.ps.gz (222 kb).