A Shortest-Path Routing Algorithm in Bicubes

Recently, an explosive increase of demand on space- and time-consuming computation makes the research activities of massively parallel systems enthusiastic. Because in a massively parallel system a huge number of processors cooperate to process tasks by communicating among others, it forms an interconnection network, which is a network that interconnects the processors. By replacing a processor and a link with a vertex and an edge, respectively, many problems regarding communication and/or routing in interconnection networks are reducible to the problems in the graph theory. There have been many topologies proposed for interconnection networks of the massively parallel systems. The hypercube is the most popular topology and many variants were proposed so far. The bicube is a such topology, which can connect the same number of vertices with the same number degree as the hypercube while its diameter is almost half of that of the hypercube keeping the vertex-symmetric property. Therefore, we focus on the bicube and propose a shortest-path routing algorithm. We give a proof of correctness of the algorithm and demonstrate its execution.