Show simple item record

dc.contributor.authorBusch, Costasen
dc.contributor.authorMagdon-Ismail, M.en
dc.contributor.authorMavronicolas, Mariosen
dc.creatorBusch, Costasen
dc.creatorMagdon-Ismail, M.en
dc.creatorMavronicolas, Mariosen
dc.description.abstractA packet-switching algorithm specifies the actions of the nodes in order to deliver packets in the network. A packet-switching algorithm is universal if it applies to any network topology and for any batch communication problem on the network. A long-standing open problem has concerned the existence of a universal packet-switching algorithm with near-optimal performance guarantees for the class of bufferless networks where the buffer size for packets in transit is zero. We give a positive answer to this question. In particular, we give a universal bufferless algorithm which is within a polylogarithmic factor from optimal for arbitrary batch problems: T = O (Τ* · log 3(n + N)), where T is the packet delivery time of our algorithm, Τ* is the optimal delivery time, n is the size of the network, and N is the number of packets. At the heart of our result is a new deterministic technique for constructing a universal bufferless algorithm by emulating a store-and-forward algorithm on a transformation of the network. The main idea is to replace packet buffering in the transformed network with packet circulation in regions of the original network. The cost of the emulation on the packet delivery time is proportional to the buffer sizes used by the storeand-forward algorithm. We obtain the advertised result by using a store-and-forward algorithm with logarithmic sized buffers. The resulting bufferless algorithm is constructive and can be implemented in a distributed way. © 2007 Society for Industrial and Applied Mathematics.en
dc.sourceSIAM Journal on Computingen
dc.subjectElectric network topologyen
dc.subjectNetwork topologiesen
dc.subjectPacket switchingen
dc.subjectBatch problemsen
dc.subjectBuffer sizesen
dc.subjectDeterministic bufferless emulationen
dc.subjectGraph decompositionen
dc.subjectOpen problemsen
dc.subjectOptimal performancesen
dc.subjectOptimal schedulingen
dc.subjectPoly-logarithmic factorsen
dc.subjectSwitching algorithmsen
dc.titleUniversal bufferless packet switchingen
dc.description.endingpage1162 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :2</p>en
dc.source.abbreviationSIAM J Computen
dc.contributor.orcidBusch, Costas [0000-0002-4381-4333]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record