Load balancing and routing on the hypercube and related networks

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.