Set-to-Set Disjoint-Path Routing in Metacube

摘要

In this paper, we propose an efficient algorithm that finds disjoint paths for set-to-set disjoint-paths routing in metacube. Metacube is a cluster-based, hypercube-like interconnection network that can connect a huge number of nodes with small amount of links per node. An metacube MC$(k,m)$ has $2^{2^km+k}$ nodes and $m+k$ links per node. For an MC$(k,m)$ and two sets of nodes $S$ and $T$ of size $m+k$, the algorithm finds $m+k$ disjoint paths, $node {s}_irightarrow node {t}_j,~1leq i,j leq m+k, node{s}_iin S, node{t}_jin T$, in $O((m+k)(2^km)log (m+k))$ time. The length of the paths is at most $(m+1)2^k+(2k+1)(lceil lg (m+k)rceil +lfloor lg 2(m+k)rfloor +1)$ if ($k=2$ and $mgeq 3$) or ($k=3$ and $mgeq 2)$ or ($k>3$). In other cases, the length of the paths is at most $(k+1)(m2^k+m+k)$.