The Impact of Network Structure on the Stability of Greedy Protocols

Dimitrios Koukopoulos, Marios Mavronicolas, Sotiris E. Nikoletseas, Paul G. Spirakis

Abstract

A packet-switching network is stable if the number of packets in the network remains bounded at all times. A very natural question that arises in the context of stability and instability properties of such networks is how network structure precisely affects these properties. In this work, we embark on a systematic study of this question in the context of Adversarial Queueing Theory, which assumes that packets are adversarially injected into the network. We consider size, diameter, maximum vertex degree, minimum number of disjoint paths that cover all edges of the network, and network subgraphs as crucial structural parameters of the network, and we present a comprehensive collection of structural results, in the form of bounds on both stability and instability thresholds for various greedy protocols:
BibTeX
@inproceedings{koukopoulos2003impact,
  author = {Dimitrios Koukopoulos and Marios Mavronicolas and Sotiris E. Nikoletseas and Paul G. Spirakis},
  title = {{The Impact of Network Structure on the Stability of Greedy Protocols}},
  booktitle = {CIAC},
  year = {2003},
  doi = {10.1007/3-540-44849-7\_29},
}

Loading related content...

Figure