Node-to-Set Cluster Fault Tolerant Routing in Star Networks

Abstract

Consider the following node-to-set routing problem in the n-dimensional star graph Gn：given a node s and a set of nodes T={t1,…, tk}, 2 ＜k＜n-1, find k node-disjoint paths s → ti, 1≦ I ≦ k. From Menger’s theorem, it is known that Gn, can totlerat at most (n-1)-k arbitrary faulty nodes for node-to-set routing problem. In this paper, we prove that Gn can tolerate as many as (n-1)-k arbitrary faulty clusters of diameter at most 2, where the faulty cluster is a connected subgraph of Gn such that all its nodes are faulty. This result implies that Gn can tolerate as many as n(n-1-k) faulty nodes for node-to-set routing if the faulty nodes can be covered by (n-1)-k subgraphs of diameter at most 2. We also show an algorithm which, in the presence of up to (n-1)-k faulty clusters of diameter at most 2, finds the k routing paths of length at most d(Gn) +9 for node-to-set routing in O(│F▕+kn) time, where d(Gn)=[3(n-1)/2] is the diameter of Gn and │F▕ is the total number of faulty nodes in faulty clusters.