Parallel routing in regular networks with faults

Abstract With the continuous increasing the scale of networks, routing in networks with faulty processors has become inevitable. Motivated by parallel routing in networks with faults, we investigate the fault-tolerant maximally local connectivity of regular networks. A network G is f-fault-tolerant maximally local-connected if each pair of nodes x and y of G − F are connected by m i n { d G − F ( x ) , d G − F ( y ) } parallel (node-disjoint) paths for any node subset F of G with | F | ≤ f , where d G − F ( x ) and d G − F ( y ) are the degrees of x and y in G − F , respectively. In this paper, we give a sufficient condition for regular networks to be f -fault-tolerant maximally local-connected. Furthermore, we apply this result on some well-known networks. In addition, several known results about other interconnection networks are straight consequence of our result.