Deterministic many-to-many hot potato routing

Allan Borodin; Yuval Rabani; Baruch Schieber

doi:10.1109/71.595575

Deterministic many-to-many hot potato routing

Allan Borodin, Yuval Rabani, Baruch Schieber

Research output: Contribution to journal › Article › peer-review

24 Scopus citations

Abstract

We consider algorithms for many-to-many hot potato routing. In hot potato (deflection) routing, a packet cannot be buffered, and is therefore always moving until it reaches its destination. We give optimal and nearly optimal deterministic algorithms for many-to-many packet routing in commonly occurring networks such as the hypercube, meshes, and tori of various dimensions and sizes, trees, and hypercubic networks such as the butterfly. All these algorithms are analyzed using a charging scheme that may be applicable to other algorithms as well. Moreover, all bounds hold in a dynamic setting in which packets can be injected at arbitrary times.

Original language	English (US)
Pages (from-to)	587-596
Number of pages	10
Journal	IEEE Transactions on Parallel and Distributed Systems
Volume	8
Issue number	6
DOIs	https://doi.org/10.1109/71.595575
State	Published - 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Signal Processing
Hardware and Architecture
Computational Theory and Mathematics

Keywords

Deflection routing
Hypercube
Many-to-many routing
Mesh
Routing

Access to Document

10.1109/71.595575

Cite this

@article{1dbb7d765b8d4e809c394a3e92c5255a,

title = "Deterministic many-to-many hot potato routing",

abstract = "We consider algorithms for many-to-many hot potato routing. In hot potato (deflection) routing, a packet cannot be buffered, and is therefore always moving until it reaches its destination. We give optimal and nearly optimal deterministic algorithms for many-to-many packet routing in commonly occurring networks such as the hypercube, meshes, and tori of various dimensions and sizes, trees, and hypercubic networks such as the butterfly. All these algorithms are analyzed using a charging scheme that may be applicable to other algorithms as well. Moreover, all bounds hold in a dynamic setting in which packets can be injected at arbitrary times.",

keywords = "Deflection routing, Hypercube, Many-to-many routing, Mesh, Routing",

author = "Allan Borodin and Yuval Rabani and Baruch Schieber",

note = "Funding Information: This work was done while Allan Borodin was visiting the Departments of Computer Science at the Hebrew University, Jerusalem, and The Weizmann Institute of Science, Rehovot, Israel; and while Yuval Rabani was at the Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, supported by U.S. ARPA/Army contract DABT63-93-C-0038, and at the Department of Computer Science, University of Toronto, Toronto, Canada. Dr. Rabani{\textquoteright}s work at the Technion was supported by a David and Ruth Moskowitz academic lecturer award and by a grant from the fund for the promotion of sponsored research at the Technion.",

year = "1997",

doi = "10.1109/71.595575",

language = "English (US)",

volume = "8",

pages = "587--596",

journal = "IEEE Transactions on Parallel and Distributed Systems",

issn = "1045-9219",

publisher = "IEEE Computer Society",

number = "6",

}

TY - JOUR

T1 - Deterministic many-to-many hot potato routing

AU - Borodin, Allan

AU - Rabani, Yuval

AU - Schieber, Baruch

N1 - Funding Information: This work was done while Allan Borodin was visiting the Departments of Computer Science at the Hebrew University, Jerusalem, and The Weizmann Institute of Science, Rehovot, Israel; and while Yuval Rabani was at the Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, supported by U.S. ARPA/Army contract DABT63-93-C-0038, and at the Department of Computer Science, University of Toronto, Toronto, Canada. Dr. Rabani’s work at the Technion was supported by a David and Ruth Moskowitz academic lecturer award and by a grant from the fund for the promotion of sponsored research at the Technion.

PY - 1997

Y1 - 1997

N2 - We consider algorithms for many-to-many hot potato routing. In hot potato (deflection) routing, a packet cannot be buffered, and is therefore always moving until it reaches its destination. We give optimal and nearly optimal deterministic algorithms for many-to-many packet routing in commonly occurring networks such as the hypercube, meshes, and tori of various dimensions and sizes, trees, and hypercubic networks such as the butterfly. All these algorithms are analyzed using a charging scheme that may be applicable to other algorithms as well. Moreover, all bounds hold in a dynamic setting in which packets can be injected at arbitrary times.

AB - We consider algorithms for many-to-many hot potato routing. In hot potato (deflection) routing, a packet cannot be buffered, and is therefore always moving until it reaches its destination. We give optimal and nearly optimal deterministic algorithms for many-to-many packet routing in commonly occurring networks such as the hypercube, meshes, and tori of various dimensions and sizes, trees, and hypercubic networks such as the butterfly. All these algorithms are analyzed using a charging scheme that may be applicable to other algorithms as well. Moreover, all bounds hold in a dynamic setting in which packets can be injected at arbitrary times.

KW - Deflection routing

KW - Hypercube

KW - Many-to-many routing

KW - Mesh

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=0031166958&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031166958&partnerID=8YFLogxK

U2 - 10.1109/71.595575

DO - 10.1109/71.595575

M3 - Article

AN - SCOPUS:0031166958

SN - 1045-9219

VL - 8

SP - 587

EP - 596

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 6

ER -

Deterministic many-to-many hot potato routing

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this