On the Invariant Many-One Packet Routing in Multi-Link Binary Hypercubes

摘要

The paper considers the necessity conditions for the existence of many-one destination graphs in multi-link hypercubes. It is shown that many-one modular destination graphs for minimum routing exist for dimensions five and six in the two-link hypercube, and also for dimension seven in the three-link hypercube. The combination of two many-one modular graphs forms a new modular graph for invariant oblivious permutation routing. As a result, modular destination graphs for minimum permutation routing in two-link hypercubes exist for dimensions 9, 10, 11, and 12. In three-link hypercubes such graphs exist for dimensions 13 and 14. An advantage of this approach is that (for any source-destination pair of an arbitrary permutation) two distinct packets can be simultaneously transmitted within a network cycle of n routing steps in the n-dimensional hypercube.