Performance and stability bounds for dynamic networks

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, ρ)-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. © 2007 Elsevier Inc. All rights reserved.