Performance and stability bounds for dynamic networks
Spirakis, Paul G.
SourceJournal of Parallel and Distributed Computing
Google Scholar check
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Andreou, Panayiotis G.; Zeinalipour-Yazdi, Constantinos D.; Samaras, George S.; Chrysanthis, Panos K. (2014)Wireless sensor networks enable users to monitor the physical world at an extremely high fidelity. In order to collect the data generated by these tiny-scale devices, the data management community has proposed the utilization ...
Savva, Giannis; Manousakis, Konstantinos; Ellinas, Georgios (2019)In this work, the concept of network coding (NC) is used in conjunction with the routing and spectrum allocation (RSA) problem to jointly provide security and protection in elastic optical networks (EONs). Specifically, ...
Morgan, Ethan; Skaathun, Britt; Nikolopoulos, Georgios K.; Paraskevis, Dimitrios; Williams, Leslie D.; Smyrnov, Pavlo; Friedman, Samuel R.; Schneider, John A. (2019)Individuals with recent/acute HIV-infection have an increased likelihood of disease transmission. To evaluate effectiveness of identifying recent infections, we compared networks of recently and long-term HIV-infected ...