The impact of network structure on the stability of greedy protocols
Ημερομηνία
2003Source
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Volume
2653Pages
251-263Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
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: - We present a novel, yet simple and natural, construction of a network parameterized by its size on which certain compositions of universally stable, greedy protocols are unstable for low rates. The closeness of the drop to 0.5 is proportional to the increase in size. - It is now natural to ask how unstable networks with small (constant) size be. We show that size of 22 suffices to drop the instability threshold for the FIFO protocol down to 0.704. This results is the current state-of-the-art trade-off between size and instability threshold. - The diameter, maximum vertex degree and minimum number of edge-disjoint paths play a significant role in an improved analysis of stability threshold for the FIFO protocol. The results of our analysis reveal that a calibration of these parameters may be a valuable asset for the design of networks with as high as possible stability threshold. - How much can network subgraphs that are forbidden for stability affect the instability threshold? Through improved combinatorial constructions of networks and executions, we improve the state-of-the-art instability threshold induced by certain known forbidden subgraphs on networks running a certain greedy protocol. © Springer-Verlag Berlin Heidelberg 2003.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
Using the Milliken Moment Method and dynamic simulation to evaluate vehicle stability and controllability
Hoffman, R. C.; Stein, J. L.; Louca, Loucas S.; Huh, K. (2008)The Milliken Moment Method (MMM) effectively organises kinematically constrained vehicle test results. The authors present a method for evaluating vehicle handling
-
Conference Object
Robust stabilizing scheme for uncertain systems controlled over limited capacity additive white Gaussian noise channels
Farhadi, A.; Charalambous, Charalambos D. (2008)In this paper we propose an encoding scheme and a stability scheme for reliable data reconstruction and robust stability of uncertain dynamical systems controlled over Additive White Gaussian Noise (AWGN) channels subject ...
-
Article
Stability and reliable data reconstruction of uncertain dynamic systems over finite capacity channels
Farhadi, A.; Charalambous, Charalambos D. (2010)In this paper we present an encoder, decoder and a stabilizing controller for reliable data reconstruction and robust stability of uncertain dynamic systems controlled over Additive White Gaussian Noise (AWGN) channels. ...