The increase of the instability of networks due to Quasi-Static link capacities
| Autor: | Koukopoulos, D., Mavronicolas, Marios, Spirakis, Paul G. |
|---|---|
| Přispěvatelé: | Spirakis, Paul G. [0000-0001-5396-3749] |
| Rok vydání: | 2007 |
| Předmět: |
Greedy protocols
Queueing theory General Computer Science Packet networks Network stability Node (networking) Integer programming Topology Stability (probability) Instability Theoretical Computer Science Graph theory Combinatorics Adversarial Quasi-Static Queuing Theory Queueing networks Adversarial Queuing Theory Communications protocol Link (knot theory) Queue Computer networks Computer Science(all) Mathematics Numerical stability |
| Zdroj: | Theoretical Computer Science Theor.Comput.Sci. |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2007.04.008 |
| Popis: | In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, where each link capacity may take on only two possible (integer) values, namely 1 and C > 1 under a (w, ρ)-adversary. We obtain the following results: •Allowing such dynamic changes to the link capacities of a network with just ten nodes that uses the LIS (Longest-in-System) protocol for contention-resolution results in instability at rates ρ > sqrt(2) - 1 and for large enough values of C.•The combination of dynamically changing link capacities with compositions of contention-resolution protocols on network queues suffices for similar instability bounds: The composition of LIS with any of SIS (Shortest-in-System), NTS (Nearest-to-Source), and FTG (Furthest-to-Go) protocols is unstable at rates ρ > sqrt(2) - 1 for large enough values of C.•The instability bound of the network subgraphs that are forbidden for stability is affected by the dynamic changes to the link capacities: we present improved instability bounds for all the directed subgraphs that were known to be forbidden for stability on networks running a certain greedy protocol. © 2007 Elsevier Ltd. All rights reserved. 381 1-3 44 56 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect