DocumentCode
2454953
Title
Randomized single-target hot-potato routing
Author
Aroya, I.B. ; Newman, Ilan ; Schuster, Assaf
Author_Institution
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
fYear
1995
fDate
4-6 Jan 1995
Firstpage
20
Lastpage
29
Abstract
We present randomized hot-potato routing algorithms on d-dimensional meshes and on the n-dimensional hypercube. The algorithms are designed for routing many packets to a single destination, or a relatively small number of destinations. The important feature, which was not obtained previously, is that the algorithms utilize the higher in-degree of the nodes and are asymptotically optimal
Keywords
hypercube networks; network routing; parallel algorithms; randomised algorithms; d-dimensional meshes; n-dimensional hypercube; randomized single-target hot-potato routing; Algorithm design and analysis; Buffer storage; Communication networks; Delay; High speed optical techniques; Hypercubes; Optical buffering; Parallel machines; Routing; Sorting;
fLanguage
English
Publisher
ieee
Conference_Titel
Theory of Computing and Systems, 1995. Proceedings., Third Israel Symposium on the
Conference_Location
Tel Aviv
Print_ISBN
0-8186-6915-2
Type
conf
DOI
10.1109/ISTCS.1995.377050
Filename
377050
Link To Document