A Set-to-Set Disjoint Paths Routing Algorithm in a Torus-Connected Cycles Network

摘要

Torus-Connected Cycles (TCC) have been recently proposed as interconnection network for massively parallel systems. In order to increase system dependability and inter-processor communication performance, disjoint paths routing is critical. In this paper, we focus on the set-to-set disjoint paths routing problem which consists in select mutually node-disjoint paths between two sets of nodes. As a pre-requisite, we first propose a time-optimal solution to the 3-set-to-set disjoint paths routing problem in a k-ary n-dimensional torus, including its empirical evaluation. Consequently, we can solve the set-to-set disjoint paths routing problem in a TCC(k, n) with paths of lengths at most kn~2 + 2n in 0(kn~2) time.