Show simple item record

dc.contributor.authorKoukopoulos, D.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorNikoletseas, Sotiris E.en
dc.contributor.authorSpirakis, Paul G.en
dc.creatorKoukopoulos, D.en
dc.creatorMavronicolas, Mariosen
dc.creatorNikoletseas, Sotiris E.en
dc.creatorSpirakis, Paul G.en
dc.description.abstractA 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.en
dc.sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en
dc.subjectGraph theoryen
dc.subjectComplex networksen
dc.subjectComputational complexityen
dc.subjectStructural parameteren
dc.subjectNetwork structuresen
dc.subjectEconomic and social effectsen
dc.subjectQueueing networksen
dc.subjectQueueing theoryen
dc.subjectAdversarial queueing theoriesen
dc.subjectAnalysis of stabilityen
dc.subjectEdge disjoint pathsen
dc.subjectForbidden subgraphsen
dc.subjectStability and instabilityen
dc.subjectStability thresholdsen
dc.titleThe impact of network structure on the stability of greedy protocolsen
dc.description.endingpage263 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.source.abbreviationLect. Notes Comput. Sci.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