SRC Technical Note 2000-001

Variations on a Theme by Chuck Thacker: Hypercube Routing with Limited Interconnections

Andrei Broder, Mark Manasse, Jim Saxe

In a recent talk at SRC, Chuck Thacker (Microsoft Corporation) described a routing scheme for a small hypercube network. In this note we explore some generalizations of Chuck's ideas and offer a routing scheme in arbitrary dimensional hypercubes. We also provide a lower-bound counterexample to fault-tolerance.

Back to the SRC Technical Notes main page.

• Hypertext (HTML) -- 24 Kbytes