RANDOMIZED SINGLE-TARGET HOT-POTATO ROUTING

Authors
BENAROYA I NEWMAN I SCHUSTER A
Citation
I. Benaroya et al., RANDOMIZED SINGLE-TARGET HOT-POTATO ROUTING, Journal of algorithms, 23(1), 1997, pp. 101-120
Citations number
29
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
23
Issue
1
Year of publication
1997
Pages
101 - 120
Database
ISI
SICI code
0196-6774(1997)23:1<101:RSHR>2.0.ZU;2-2
Abstract
We present randomized hot-potato routing algorithms on d-dimensional m eshes and on the n-dimensional hypercube. The algorithms are designed for routing many packets to a single destination, or a relatively smal l number of destinations. The important feature, which was not obtaine d previously, is that the algorithms utilize the higher in-degree of t he nodes and are asymptotically optimal. (C) 1997 Academic Press.