Time Optimal Node-to-Set Disjoint Paths Routing in Hypercubes

摘要

Due to their simplicity, hypercubes are a popular topology for the interconnection network of massively parallel systems. One critical issue when dealing with such parallel systems is routing: data transmission is at the center of any operation or computation. Additionally, as the number of processors inside modern supercomputers is huge, and continuously growing, fault tolerance ought to be addressed. Hence, for a routing algorithm to generating node-disjoint paths is of high interest as it maximises the probability of establishing a fault-free path in a faulty environment. Also importantly, generating disjoint paths allows for time-efficient data transmission; transfers are able to be realised in parallel as two paths are ensured to share no common resource. In an n-dimensional hypercube, given a source node and k(k≤n) destination nodes, Rabin described an algorithm finding k node-disjoint paths between the source node and the destination nodes of optimal lengths (at most n + 1) in O(k~3 + kn) time. We describe in this paper a smart improvement to this algorithm to reduce its time complexity from O(k~3 + kn) to O(kn) which is time optimal.