Show simple item record

dc.contributor.authorKoukopoulos, D.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorSpirakis, Paul G.en
dc.creatorKoukopoulos, D.en
dc.creatorMavronicolas, Mariosen
dc.creatorSpirakis, Paul G.en
dc.description.abstractIn 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.en
dc.sourceJournal of Parallel and Distributed Computingen
dc.subjectNetwork protocolsen
dc.subjectInteger programmingen
dc.subjectGraph theoryen
dc.subjectPacket networksen
dc.subjectParallel processing systemsen
dc.subjectParallel computingen
dc.subjectQueueing networksen
dc.subjectAdversarial queuing theoryen
dc.subjectAdversarial queueing theoryen
dc.subjectDelay boundsen
dc.subjectDirected Acyclic Graphs (DAG)en
dc.subjectStability boundsen
dc.titlePerformance and stability bounds for dynamic networksen
dc.description.endingpage399 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.source.abbreviationJ.Parallel Distrib.Comput.en
dc.contributor.orcidSpirakis, Paul G. [0000-0001-5396-3749]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record