The impact of network structure on the stability of greedy protocols
Nikoletseas, Sotiris E.
Spirakis, Paul G.
SourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Google Scholar check
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
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
Koukopoulos, D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2002)A distinguishing feature of today’s large-scale platforms for distributed computation and communication, such as the Internet, is their heterogeneity, predominantly manifested by the fact that a wide variety of communication ...
Lestas, Marios; Ioannou, Petros A.; Pitsillides, Andreas; Hadjipollas, George (2017)A number of congestion control schemes which adopt the max-min fairness criterion and do not require maintenance of per flow states within the network have been proposed in the literature. The establishment of global ...