Load balancing and routing on the hypercube and related networks

TitleLoad balancing and routing on the hypercube and related networks
Publication TypeJournal Articles
Year of Publication1992
AuthorsJaJa JF, Ryu K W
JournalJournal of Parallel and Distributed Computing
Volume14
Issue4
Pagination431 - 435
Date Published1992/04//
ISBN Number0743-7315
Abstract

Several results related to the load balancing problem on the hypercube, the shuffle-exchange, the cube-connected cycles, and the butterfly are shown. Implications of these results for routing algorithms are also discussed. Our results include the following: •⊎ Efficient load balancing algorithms are found for the hypercube, the shuffle-exchange, the cube-connected cycles, and the butterfly.

⊎ Load balancing is shown to require more time on a p-processor shuffle-exchange, cube-connected cycle or butterfly than on a p-processor weak hypercube.

⊎ Routing n packets on a p-processor hypercube can be done optimally whenever n = p1+1/k, for any fixed k > 0.

URLhttp://www.sciencedirect.com/science/article/pii/074373159290081W
DOI10.1016/0743-7315(92)90081-W