Cluster Fault-Tolerant Routing in Star Graphs Qian-Ping Gu and Shietung Peng Department of Computer Software, The University of Aizu, Aizu-Wakamatsu, Fukushima, 965-8580 Japan Fault-tolerant routing is a key issue in computer/ communication networks. We say a network (graph) can tolerate l faulty nodes for a routing problem if after removing at most l arbitrary faulty nodes from the graph the routing paths exist for the routing problem. However, the bound l is usually a worst-case measure and it is of great interest to find the routing paths when more than l faulty nodes exist. Cluster fault-tolerant (CFT) routing was proposed as an approach for this purpose. In the CFT routing, we reduce the number of “faults” that a routing problem has to deal with using subgraphs to cover the faulty nodes. In particular, we consider the number and the size (diameter) of faulty subgraphs rather than the number of faulty nodes that a graph can tolerate. In this paper, we show that a subgraph of diameter 2 can be viewed as a single “fault” for the following routing problems in the star graph: Given a source node s and t target nodes t1 , . . . , tk , find k node-disjoint paths from s to ti (1 ≤ i ≤ k), and given k node pairs (s1 , t1 ), . . . , (sk , tk ), find k node-disjoint paths si → ti (1 ≤ i ≤ k). Since a subgraph of diameter 2 of the n-dimensional star graph Gn may have n nodes, the above result implies that the number of faulty nodes that Gn can tolerate is n times larger than the worst-case measure if the faulty nodes can be covered by certain subgraphs. We also give algorithms which find the paths for the two routing problems. © 2000 John Wiley & Sons, Inc. Keywords: interconnection network; fault-tolerant routing; node-disjoint paths 1. INTRODUCTION With the rapid progress in VLSI and optic fiber technologies, the size of computer and communication networks has increased tremendously. As a result, faulttolerant routing has become one of the central issues in the study of the networks [3, 4, 15, 16]. For a specific routing problem, we say a graph can tolerate I faulty nodes if after deleting at most l arbitrary nodes from the graph the required routing paths exist for the routing problem. However, the bound l is usually the Received March 24, 1998; accepted May 25, 1999 Correspondence to: Q.-P. Gu; e-mail {qian/s-peng}@u-aizu.ac.jp Contract grant sponsor: Ministry of Education, Science, Sports and Culture of Japan c 2000 John Wiley & Sons, Inc. NETWORKS, Vol. 35(1), 83–90 2000 worst-case measure that is unlikely to happen in practice. What are the sufficient conditions that guarantee the existence of the routing paths when more than l faulty nodes exist? Several approaches such as forbidden set [7, 20, 27] and cluster fault-tolerant (CFT) routing [12, 13] have been developed for answering the above question. Here, a cluster in a graph is a connected subgraph. It has been observed that for several fundamental routing problems in the interconnection networks with regular structures like hypercubes, star graphs, and so on if multiple faulty nodes can be covered by a cluster of small diameter then those faulty nodes can be viewed as a single “fault” rather than as several arbitrary ones. On the other hand, nodes of a network often “fail” in a clusterlike manner. For example, one of the most important operations in a network is to establish routing paths without disturbing the existing ones. One approach for the above problem is to find the new paths by viewing the nodes in the existing paths as faults. The faulty nodes in each path make a connected subgraph. Another example is that a fault in the physical implementation of the network may fail several logical nodes of the network. Those faulty nodes are usually in a clusterlike manner as well. Motivated by the above observation, CFT routing has been proposed to reduce the number of faults that the routing algorithm has to deal with, using clusters to cover the faulty nodes. In the CFT routing, we consider the number and the size (diameter) of faulty clusters that a graph can tolerate for certain routing problems. Efficient interconnection networks are critical for large-scale parallel/distributed computing systems because the communication between the processors is a prime bottleneck in such systems. The hypercube is one of the most versatile and efficient networks for such systems and has been adopted several times in practice. The star graph is an attractive alternative to the hypercube. Like the hypercube, the star graph holds many attractive features including complete symmetric topology, a simple and optimal routing algorithm that routes messages between nodes along a shortest path, the recursive decomposition structure, and the maximal fault tolerance through the multitude of paths between nodes. In addition, with regard to the important properties of node de- CCC 0028-3045/00/010083-08 gree and diameter, the star graph is shown to be markedly superior. A number of efficient algorithms on the star graph, which exploit its versatility, have been reported [1, 2, 5, 6, 8, 9]. Further efforts for fault-tolerant routing problems in the star graph have also been made by several researchers [5, 6, 11, 12, 14, 17, 19, 25]. In particular, it was previously known that for the most fundamental routing problem of finding a nonfaulty path between a source node s and a target node t (node-to-node routing) in the star graph a faulty cluster of diameter 2 can be viewed as a single “fault” [12]. In this paper, we extend the above result to the following two routing problems. We use disjoint paths for node-disjoint paths in what follows: 1. Given a node s and a set of nodes T = {t1 , . . . , tk }, find k disjoint paths s → ti , 1 ≤ i ≤ k (node-to-set routing). 2. Given k node pairs (s1 , t1 ), . . . , (sk , tk ), find k disjoint paths si → ti , 1 ≤ i ≤ k (k-pairwise routing). The node-to-set and the k-pairwise routing problems arise naturally from the study of routing, reliability, randomized routing (such as Rabin’s Information Dispersal Algorithm), fault tolerance, and other communication protocols (such as the byzantin algorithm and anycast) in parallel architecture and distributed computer networks [16, 23, 24]. The k-pairwise routing problem is also a classical problem in graph theory. For the node-toset routing problem, from Menger’s theorem, k disjoint paths exist in the n-dimensional star graph Gn [which is (n − 1)-connected] if k ≤ n − 1 [23]. This implies that Gn can tolerate (n − 1) − k arbitrary faulty nodes for the node-to-set routing problem. The k-pairwise routing problem has been investigated in both mathematical terms and interconnection network studies [6, 13, 18, 21, 22, 26, 28]. Whether a graph G(V, E) has k disjoint paths si → ti (1 ≤ i ≤ k) for k ≤ 2 can be verified in Poly(|V|) time [26]. However, for k ≥ 3, the existence of the k paths for the problem on an arbitrary graph is NP-complete [18] (also see [10], p. 217). A necessary condition for any graph to have the k paths is that it is (2k − 1)-connected [28]. Dietzfelbinger et al. [6] proved that for k ≤ d(n − 1)/2e the k disjoint paths exist in Gn . From this, Gn can tolerate n − 2k arbitrary faulty nodes for the k-pairwise routing problem. We prove in this paper that a faulty cluster of diameter 2 can be viewed as a single fault in the above routing problems. Especially, we show that Gn can tolerate as many as (n−1)−k and n−2k faulty clusters of diameter 2 for the node-to-set and the k-pairwise routing problems, respectively. Since a cluster of diameter 2 in Gn has as many as n nodes, the above results imply that Gn can tolerate as many as n(n−1−k) and n(n−2k) faulty nodes for the node-to-set and the k-pairwise routing problems, respectively, if the faulty nodes can be covered by certain clusters. These are in contrast to the worst-case measures 84 NETWORKS–2000 of (n − 1) − k and n − 2k arbitrary faulty nodes. We also give algorithms for finding the paths for the routing problems. In particular, we show an algorithm which, given at most (n − 1) − k faulty clusters of diameter at most two, constructs k nonfaulty disjoint paths of length at most d(Gn ) + 9 for the node-to-set routing problem in O(|F| + kn) time, where d(Gn ) = b[3(n − 1)]/2c is the diameter of Gn and |F| is the total number of nodes in faulty clusters. For the k-pairwise routing problem, we show an O(|F|+kn) time algorithm which, given at most n − 2k faulty clusters of diameter at most 2, constructs k nonfaulty disjoint paths of length at most d(Gn ) + 8. The rest of this paper is organized as follows: In Section 2, we give the preliminaries. The node-to-set and the k-pairwise CFT routing problems are discussed in Sections 3 and 4, respectively. The final section concludes the paper. 2. PRELIMINARIES A path in a graph is a sequence of edges of the form (s1 , s2 )(s2 , s3 ) . . . (sk−1 , sk ). The length of a path is the number of edges in the path. We sometimes denote the path from s1 to sk by s1 → sk . For a path P = (s1 , s2 )(s2 , s3 ) . . . (sk−1 , sk ), P is also used to denote the set of nodes {s1 , . . . , sk } that appear in path P if no confusion arises. Paths P and Q are disjoint if P∩Q = . Two paths P and Q that share a common end node s are disjoint if P ∩ Q = {s}. For two nodes s and t in a graph G, d(s, t) denotes the distance between s and t, that is, the length of the shortest path connecting s and t. The diameter of G is d(G) = max{d(s, t)|s, t ∈ G}. The eccentricity of s ∈ G is e(s) = max{d(s, t)|t ∈ G} and the radius of G is r(G) = min{e(s)|s ∈ G}. A node c ∈ G is a center node of G if e(c) = r(G). Notice that a graph may have multiple center nodes. A cluster C of G is a connected subgraph of G. C is used to express the cluster and the set of nodes in the cluster as well if no confusion arises. A cluster C is called faulty if all nodes in C are faulty. Given a set F of faulty clusters, d(F) = max{d(C)|C ∈ F} and F = ∪C∈F C denotes the set of all nodes of the clusters in F. For a routing problem in a graph G, a triple (m, d, l) is called a features number of G if for any set F of faulty clusters with |F| ≤ m, d(F) ≤ d, and |F| ≤ l, the required routing paths exist. A features number (m, d, l) is called an optimum features number (OCFT number) for a routing problem, if for any (m, d, l) < (m0 , d0 , l0 ), (m0 , d0 , l0 ) is not a features number for the problem.1 For a graph G and a triple (m, d, l) with l = m × max{|CkC ⊆ G, d(C) = d}, the triple will be denoted by only two parameters (m, d). A pair (m, d) is an OCFT number if (m, d) is a features number and for any (m0 , d0 ) with (m, d) < (m0 , d0 ), (m0 , d0 ) is not a features number. It has been known that (n − 2, 2) is an OCFT number of Gn for the node-to-node routing problem [12]. In this paper, we show that (n−1−k, 2) and (n−2k, 2) are OCFT numbers of Gn for the node-to-set and the k-pairwise routing problems, respectively. The n-dimensional star graph Gn is an undirected graph Gn . The nodes of Gn are in a one-to-one correspondence with the permutations [p1 , p2 , . . . , pn ] of the set hni = {1, 2, . . . , n}. Two nodes of Gn are connected by an edge if and only if the permutation of one node can be obtained from the other by interchanging the first symbol p1 with the ith symbol pi , 2 ≤ i ≤ n. This interchange of the symbols in position 1 with position i is called a transposition. For node s = [p1 , p2 , . . . , pn ], s(i) denotes the node [pi , p2 , . . . pi−1 , p1 , pi+1 , . . . , pn ], obtained by transposition i on s. Similarly, s(i1 , i2 , . . . , ik ) denotes the node obtained after performing k transpositions [s(1) = s(i,i) = s]. Figure 1 gives the G4 . Gn has uniform node degree n − 1 and diameter d(Gn ) = b[3(n − 1)]/2c. Gn is node and edgesymmetric and (n − 1)-connected. The star graph has a highly recursive structure. Gn is made of n copies of Gn−1 . Partition the nodes of Gn into n mutually disjoint subsets Sn (k), 1 ≤ k ≤ n, where Sn (k) = {[p1 , p2 , . . . , pn−1 , k]|pj ∈ hni\{k} for j ≠ n, pj ≠ p1 for j ≠ l}. Then, for each k, the induced subgraph of the set Sn (k) is an (n − 1)-dimensional star graph, denoted as Gn (k). For a node s = [p1 , p2 , . . . , pn−1 , k] ∈ Gn (k), we have s(n) ∈ Gn (p1 ). We call node s a port to Gn (p1 ). Each node s ∈ Gn (k) is a port to exactly one substar Gn (p1 ). The set of nodes Cn (k, l) = {s|s ∈ Gn (k) and s(n) ∈ Gn (l)} is called the port-set of Gn (k) to Gn (l). Clearly, the nodes in Gn (k) can be partitioned into n − 1 portsets Cn (k, l), l ∈ hni\{k}, with |Cn (k, l)| = (n − 2)! and Cn (k, l) ∩ Cn (k, m) = for l ≠ m. For s = [p1 , p2 , . . . , pn ] ∈ Gn (pn ), s ∈ Cn (pn , p1 ), and its neighbor nodes, s(i) = [pi , p2 , . . . , pi−1 , p1 , pi+1 , . . . , pn ] ∈ Cn (pn , pi ), i ∈ hni\{l, n}. For a cluster C of Gn with d(C) = 2 or d(C) = 0, C has a unique center node. If d(C) = 1, then both the two nodes of C are center nodes. We take an arbitrary node as the center in this case. Notice that the nodes of a cluster of diameter at most 2 appear in at most two substars of Gn . For example, let c = [p1 , . . . , pn ] be the center of the cluster C = {c, c(i) , 2 ≤ i ≤ n}. The nodes of C appear in two substars of Gn , with c and c(i) , 2 ≤ i ≤ n − 1, in Gn (pn ), and c(n) in Gn (p1 ). For simplicity, we use cluster for faulty cluster of diameter at most 2 unless otherwise stated in what follows. We assume that each node of Gn can be identified in O(1) time. The following properties of Gn have been proved in [12] and will play key roles in this paper: FIG. 1. The 4-dimensional star graph G4 . Lemma 1. There is no odd length cycle or no cycle of length 4 in Gn . Lemma 2. For any nodes s = [p1 , p2 , . . . , pn ] in Gn and any k ∈ hni\{p1 , pn }, there are n − 1 disjoint paths of length at most 3 that connect s to n − 1 distinct nodes in Gn (k). Assume that pj = k for some j with 2 ≤ j ≤ n − 1. Then, the n − 1 disjoint paths are s → s(i) → s(i,j) → s(i,j,n) ∈ Gn (k) if i ≠ j(pi ≠ k) Pi : s → s(i) → s(i,n) ∈ Gn (k) if i = j(pi = k) for 2 ≤ i ≤ n − 1 and Pn : s → s(n) → s(n,j) → s(n,j,n) ∈ Gn (k). Path Pn passes through substar Gn (p1 ), whereas the other n − 2 paths go directly from Gn (pn ) to Gn (k). Example. Let s = [2, 3, 4, 1, 6, 5] and k = 4. Then, the five paths are (see Fig. 2) P2 : s → s(2) = [3, 2, 4, 1, 6, 5] → s(2,3) = [4, 2, 3, 1, 6, 5] → s(2,3,6) = [5, 2, 3, 1, 6, 4], P3 : s → s(3) = [4, 3, 2, 1, 6, 5] → s(3,6) = [5, 3, 2, 1, 6, 4], P4 : s → s(4) = [1, 3, 4, 2, 6, 5] → s(4,3) = [4, 3, 1, 2, 6, 5] → s(4,3,6) = [5, 3, 1, 2, 6, 4], P5 : s → s(5) = [6, 3, 4, 1, 2, 5] → s(5,3) = [4, 3, 6, 1, 2, 5] → s(5,3,6) = [5, 3, 6, 1, 2, 4], and P6 : s → s(6) = [5, 3, 4, 1, 6, 2] → s(6,3) = [4, 3, 5, 1, 6, 2] → s(6,3,6) = [2, 3, 5, 1, 6, 4]. NETWORKS–2000 85 that d(s(i) , s(j,n) ) > 2(2 ≤ i ≤ n, 2 ≤ j ≤ n − 1, and i ≠ j) and d(s(i,n) , s(j,n) > 2(2 ≤ i, j ≤ n − 1 and i ≠ j). For a / C (Lemma cluster C with s ∈ / C, if s(i) ∈ C, then s(j) ∈ 1). Therefore, a cluster C ∈ F can block at most one of the above n − 1 paths s → gpi (1 ≤ i ≤ n − 1) and at least k of the n − 1 paths are nonfaulty. Assume that (n − 1) − r(r ≥ k) of the n − 1 paths are blocked by clusters (r of the n − 1 paths are nonfaulty). Let C be a cluster with the center c. If C blocks a path s → gpi , then c is either in Gn (pn ) or in Gn (pi ). Therefore, at most |F| − (n − 1 − r) ≤ r − k faulty clusters may have their centers in the r substars Gn (pj ) with nonfaulty path s → gpj . Thus, the lemma holds. The indices li (1 ≤ i ≤ k) of the k destination substars shall be decided in finding k nonfaulty disjoint paths ti → hli ∈ Gn (li ). FIG. 2. Five disjoint paths of the example. Lemma 3. Given s = [p1 , . . . , pn ], k ∈ hni\{p1 , pn }, and a cluster C with the center c ∈ Gn (k) and s ∈ C, C can block at most one of the above n − 1 paths. Lemma 4. Given a set F of faulty nodes with |F| ≤ n−2, and nonfaulty nodes s and t in Gn , a nonfaulty path of length at most d(Gn ) + 3 can be found in O(n) time. Lemma 5. Given a set F of clusters with |F| ≤ n − 2 and d(F) ≤ 2, and nonfaulty nodes s and t in Gn , a nonfaulty path of length at most d(Gn ) + 8 can be found in O(|F| + n) time. 3. NODE-TO-SET CFT ROUTING To find the nonfaulty disjoint paths for the node-toset routing problem, we make use of the recursive structure of the star graph. As stated in the previous section, Gn consists of n copies of substars of dimension n − 1. Our idea is to reduce the node-to-set routing problem in Gn to k node-to-node routing problems in k substars, one subproblem per substar. To realize the idea, we need to find k destination substars Gn (li ), k nonfaulty disjoint paths s → gli ∈ Gn (li ), and k nonfaulty disjoint paths ti → hli ∈ Gn (li ). Roughly speaking, we choose substars which do not contain node s or any center of clusters as destination substars. We first prove that destination substars Gn (li ) and paths s → gli can be found. Lemma 6. Given F with |F| ≤ n−1−k and d(F) ≤ 2, and a nonfaulty node s in Gn , we can find k substars Gn (l) which do not contain s or any center of clusters, and k nonfaulty disjoint paths s → gl ∈ Gn (l) of length at most 2. Proof. For s = [p1 , p2 , . . . , pn ], its neighbor node s(i) (2 ≤ i ≤ n − 1) is a port to the substar Gn (pi ), and path s → s(i) → s(i,n) = gpi ∈ Gn (pi ) has length 2. Path s → s(n) = gp1 ∈ Gn (p1 ) has length 1. It is easy to check 86 NETWORKS–2000 Lemma 7. Given F with |F| ≤ n − 1 − k and d(F) ≤ 2, nonfaulty nodes T = {t1 , . . . , tk } in Gn , and k destination substars Gn (l) given in Lemma 6, we can assign the k substars to the k nodes ti as Gn (li )(1 ≤ i ≤ k) and find k nonfaulty disjoint paths ti → hli ∈ Gn (li ) of length at most 3. Proof. For each destination substar Gn (l), if Gn (l) contains a node ti , then assign Gn (l) to ti as Gn (li ) (hli = ti ) and mark Gn (l) used. For each unused Gn (l), if Gn (l) (n) contains ti for an unassigned ti then assign Gn (l) to ti (n) as Gn (li ) (hli = ti ) and mark Gn (l) used. Since Gn (li ) has no center of clusters, any faulty node in Gn (li ) is c(n) , where c is the center of a cluster. From the fact that (n) ti is nonfaulty, ti is nonfaulty. Assume that t1 , . . . , ta have not been assigned destination substars. Assign each ti (1 ≤ i ≤ a) an arbitrary unused Gn (l) as Gn (li ). Since (n) / Gn (li ) and ti ∈ / Gn (li ), from Lemma 2, we can find ti ∈ n − 1 disjoint paths of length at most 3 from ti to n − 1 distinct nodes in Gn (li ). We find one of the n − 1 paths that does not have any faulty node or any node in the paths tj → hlj (j ≠ i) as ti → hli ∈ Gn (li ). If tj → hlj is of length 3, then hlj does not block any of the n − 1 paths of Lemma 2 for ti . Therefore, we can view each of the paths tj → hlj as a cluster when we find the path ti → hli . This implies that there are |F|+|T|−1 ≤ n−2 clusters when we connect ti to hli . Notice that Gn (li ) does (n) not have any tj or tj . This and the choice of Gn (li ) imply that Gn (li ) has no center of clusters. From Lemma 3, the paths ti → hli (1 ≤ i ≤ a) can be found. Now, we show the algorithm for the node-to-set routing problem. Assume that F = {C1 , . . . , Cr }(r ≤ (n − 1) − k) and Ci has center ci . Without loss of generality, (n) we may assume that ci ∈ Ci for all Ci ∈ F. We also assume that k ≤ n−2. For the case of k = n−1, |F| = and the paths for the node-to-set routing problem can be found by the previous work [14]. The algorithm is given on the next page: Step 1. For each substar Gn (j)(1 ≤ j ≤ n), compute xj = (n) (n) |Gn (j)∩{c1 , . . . , cr , c1 , . . . , cr }| and yj = |Gn (j)∩T|. If there are k destination substars Gn (li ) with xli +yli ≤ n − 2, then Step 2; otherwise, Step 3. Step 2. Find the k nonfaulty disjoint paths s → gli ∈ Gn (li ) as in Lemma 6. Find the k nonfaulty disjoint paths ti → hli ∈ Gn (li ) as in Lemma 7. Connect gli and hli in Gn (li ). Step 3. There are exactly k destination substars and one substar Gn (m) has xm + ym = n − 1]. For s = [p1 , . . . , pn ] ∈ Gn (pn ), use Gn (pn ) to replace Gn (m) as the destination substar. Find the nonfaulty path tj → hpn ∈ Gn (pn ) of length at most 2 and the k − 1 nonfaulty disjoint paths ti → hli ∈ Gn (li ) (i ≠ j) as in Lemma 7. Find the k−1 nonfaulty disjoint paths s → gli ∈ Gn (li ) (i ≠ j) as in Lemma 6. Mark the intermediate node of each path s → gli ∈ Gn (li ) (i ≠ j) of length 2 faulty. Connect gli and hli in Gn (li ) (i ≠ j), and connect s and hpn in Gn (pn ). In Step 1, xj is the number of clusters C with C ∩ Gn (j) ≠ and yj is the number of nodes of T in Gn (j). (n) Since ci and ci are in different substars, for every j ∈ hni, xj ≤ (n − 1) − k and xj + yj ≤ n − 1. Lemma 6 guarantees that there are at least k destination substars. If xli + yli ≤ n − 2, then Gn (li ) [which is (n − 1)-dimensional] has at most max{xli + yli − 1, xli } ≤ n − 3 clusters and, thus, gli and hli can be connected in Gn (li ) (Lemma 5). Therefore, if there are k destination substars Gn (li ) with xli + yli ≤ n − 2, then Step 2 solves the problem. If Step 3 is executed, then the following is true: r = (n − 1) − k; there are exactly k destination substars in Gn and one destination substar Gn (m) has xm + ym = n − 1; the centers ci (1 ≤ i ≤ r) of clusters are distributed in the other (n − 1) − k substars which do not contain s with one center per substar, and the (n − 1) − k nodes (n) of ci and k nodes of T are in the same substar Gn (m) which does not contain s or any center of clusters. Since xm + ym = n − 1, we may not be able to connect gm and hm in Gn (m). Let s = [p1 , . . . , pn ] ∈ Gn (pn ). Then, Gn (pn ) has no faulty node [otherwise, Gn (pn ) has at least one center of a cluster, implying that we can find kGn (li ) with xli + yli ≤ n − 2]. We use Gn (pn ) to replace Gn (m) as the destination substar. Since the faulty node in Gn (m) is c(n) , where c is the center of some cluster, the port-set Cn (m, pn ) has no faulty node. From this, a node tj can be connected to hpn in Gn (pn ) by a nonfaulty path of length at most 2. Mark the intermediate node of each path s → gli ∈ Gn (li ) (i ≠ j) of length 2 faulty. Since k ≤ n − 2, there are at most n − 3 faulty nodes in Gn (pn ). Hence, s and hpn can be connected in Gn (pn ) (Lemma 4). Theorem 8. For 2 ≤ k ≤ n − 1, given F with |F| ≤ (n − 1) − k and d(F) ≤ 2, and nonfaulty nodes s and T = {t1 , . . . , tk } in Gn , k nonfaulty disjoint paths s → ti of length at most d(Gn ) + 9 can be found in O(|F| + kn) time. Proof. The above algorithm finds the k paths s → gli → hli → ti (1 ≤ i ≤ k). For Gn (li ) which contains at most one node of T, any fault in Gn (li ) is a single faulty node. Therefore, by Lemma 4, gli and hli can be connected by a nonfaulty path of length at most d(Gn−1 ) + 3 in Gn (li ). If Gn (li ) has at least two nodes of T, then one node ti is assigned to Gn (li ) and the other nodes of T are connected to the destination substars other than Gn (li ). In this case, Gn (li ) may have some clusters. By Lemma 5, gli and hli can be connected by a nonfaulty path of length at most d(Gn−1 ) + 8 in Gn (li ). The total length of the paths s → ti is at most max{d(Gn−1 ) + 2 + 3 + 3, d(Gn−1 ) + 2 + 8} ≤ d(Gn ) + 9. It takes O(|F|) time to find the centers of clusters and O(kn) time to find k destination substars Gn (li ) by checking the last digits of center nodes of faulty clusters. Finding paths ti → hji takes O(kn) time. Connecting gli and hli in Gn (li ) takes O(|Fli | + n) time, where |Fli | is the number of faulty nodes in Gn (li ). Since Gn (li ) has originally at most O(n) faulty nodes and connecting nodes tj to hlj (j ≠ i) generates at most O(n) new faulty nodes, it takes O(n) time to find one gli → hli . Thus, the time complexity of connecting s to T is O(|F| + kn). Theorem 8 shows that (n − 1 − k, 2) is a features number of Gn for the node-to-set routing problem. We prove that (n − 1 − k, 2) is an OCFT number as well. Theorem 9. (n − 1 − k, 2) is an OCFT number of Gn for the node-to-set routing problem. Proof. To show the theorem, we need to prove that for any (m, d) with (n − 1 − k, 2) < (m, d), (m, d) is not a features number. Let s = [p1 , . . . , pn ] and F = {{[pi , . . . , pi−1 , p1 , pi+1 , . . . , pn ]}|2 ≤ i ≤ n−k+1}. Then, |F| = n − k and d(F) = 0 < 2. Obviously, s has only k − 1 nonfaulty neighbors. It is impossible to find k nonfaulty disjoint paths s → ti , 1 ≤ i ≤ k. Thus, (n−k, 2) is not a features number of Gn for the node-to-set routing problem. Similarly, we can show that (n − 1 − k, 3) is not a features number as well. 4. k -PAIRWISE CFT ROUTING Similar to the algorithm for the node-to-set routing problem, we reduce the k-pairwise routing problem in Gn into k node-to-node routing problems in k substars of dimension n − 1. To do so, we first find k destination substars Gn (li ) and then find 2k nonfaulty disjoint paths si → gli ∈ Gn (li ) and ti → hli ∈ Gn (li ). However, there are more constraints on destination substars for the kNETWORKS–2000 87 pairwise routing problem than those for the node-to-set routing problem. When we connect a node pair (si , ti ) in the destination substar Gn (li ), we want that Gn (li ) does not have any center of clusters or any node of sj and tj for j ≠ i. Lemma 10. Given F with F ≤ n − 2k and d(F) ≤ 2, and 2 ≤ k ≤ d(n − 1)/2e pairs of nonfaulty nodes (s1 , t1 ), . . . , (sk , tk ) in Gn , we can find k destination substars Gn (l), such that each Gn (l) does not contain any center of clusters, and if a Gn (l) has a node of si and ti , then the Gn (l) does not contain any node of sj and tj for j ≠ i. Proof. From |F| ≤ n − 2k, there are at least 2k substars which do not have any center of clusters. We call these 2k substars candidates. Let Vp = {(s1 , t1 ), . . . , (sk , tk )} and VG be the set of the 2k candidates. Construct a bipartite graph between Vp and VG . There is an edge between (si , ti ) and a candidate, if and only if at least one node si or ti appears in that candidate. Therefore, there are at most 2k edges in the bipartite graph. Assume that there are r0 nodes of degree 0, r1 nodes of degree 1, and r2 nodes of degree at least 2 in VG . We chose the nodes of degree at most 1 as the destination substars. Each node u of degree 1 in VG is assigned as the destination substar to the node pair (si , ti ) which is adjacent to u in the bipartite graph. After this, we have k − r1 unassigned node pairs and r0 destination substars. Since r1 + 2r2 ≤ 2k, r2 ≤ k. From r0 + r1 + r2 = 2k, r0 ≥ k − r1 . Thus, the lemma holds. Lemma 11. Given F with F ≤ n − 2k and d(F) ≤ 2, 2 ≤ k ≤ d(n − 1)/2e pairs of nonfaulty nodes (s1 , t1 ), . . . , (sk , tk ) in Gn , and k destination substars Gn (l) given in Lemma 10, we can assign the k substars to the k node pairs (si , ti ) as Gn (li )(1 ≤ i ≤ k) and find 2k nonfaulty disjoint paths si → gli ∈ Gn (li ) and ti → hli ∈ Gn (li ) of length at most 3. Proof. We first notice that the path si → gli should not contain any faulty node or any node in the paths sj → glj and tj → hlj for j ≠ i. However, it does not matter if paths si → gli and ti → hli have a common node. For each destination substar Gn (l), if Gn (l) con- FIG. 3. The case that glj blocks the path Pn for si . 88 NETWORKS–2000 tains si or ti for some unassigned pair (si , ti ), then assign Gn (l) to (si , ti ) as Gn (li ) and mark Gn (l) used. For each (n) unused destination substar Gn (l), if Gn (l) contains si or (n) ti for an unassigned pair (si , ti ), then assign Gn (l) to (si , ti ) as Gn (li ) and mark Gn (l) used. Since Gn (li ) has no center of clusters, any faulty node in Gn (li ) is c(n) , where c is the center of some cluster. From the fact that si (ti ) (n) (n) is nonfaulty, si ∈ Gn (li ) (ti ∈ Gn (li )) is nonfaulty. After this, for each unassigned (si , ti ), assign an arbitrary unused Gn (l) to (si , ti ) as Gn (li ). For si with si ∈ Gn (li ) (n) / Gn (li ), we find n − 1 disjoint paths P2 , . . . , Pn and si ∈ of length at most 3 from si to n − 1 distinct nodes in Gn (li ) by Lemma 2. We find one of the n − 1 paths that does not have any faulty node or any node in the paths sj → glj and tj → hlj (j ≠ i) as si → gli ∈ Gn (li ). In finding the path si → gli , we can view the paths sj → glj and tj → hlj (j ≠ i) as clusters due to the following reason: If sj → glj has length at most 2, then sj → glj can be viewed as a cluster. Assume that sj → glj has length 3. Obviously, glj does not block any of the n − 2 paths P2 , . . . , Pn−1 for si . Also, if glj is a node of the paths P2 , . . . , Pn−1 for sj , then glj does not block any paths P2 , . . . , Pn for si . However, if glj is a node of Pn for sj , then glj may block the path Pn for si . If this happens, then it must be the case that an intermediate node of sj → glj blocks the same path Pn as well (see Fig. 3). Therefore, we can neglect the blocking effect of glj and view sj → glj as a cluster. Thus, there are |F|+2(k−1) ≤ n−2 clusters when we connect si to gli . From Lemma 3, the path si → gli can be found. Similarly, the path ti → hli can be found. Lemmas 10 and 11 imply an algorithm for the kpairwise routing problem: Find the k destination substars Gn (li ); find the 2k nonfaulty disjoint paths si → gli ∈ Gn (li ) and ti → hli ∈ Gn (li ); and connect gli and hli in Gn (li ). Theorem 12. Given F with F ≤ n − 2k and d(F) ≤ 2, and 2 ≤ k ≤ d(n − 1)/2e pairs of nonfaulty nodes (s1 , t1 ), . . . , (sk , tk ) in Gn , k nonfaulty disjoint paths si → ti , 1 ≤ i ≤ k, of length at most d(Gn ) + 8 can be found in O(|F| + kn) time. Proof. From Lemmas 10 and 11, we can find k destination substars Gn (li ), each of which has at most n − 2k ≤ n − 4 faulty nodes and 2k nonfaulty disjoint paths si → gli ∈ Gn (li ) and ti → hli ∈ Gn (li ). From Lemma 4, gli and hli can be connected by a nonfaulty path of length at most d(Gn−1 ) + 3 in Gn (li ). Therefore, the length of si → ti is at most d(Gn−1 ) + 3 + 3 + 3 ≤ d(Gn ) + 8. It takes O(|F|) time to find the centers of clusters, O(n) time to find 2k candidates by checking the last digits of center nodes of clusters, and O(kn) time to find the k destination substars and paths si → gli and ti → hji . Connecting gli and hli in Gn (li ) takes O(n) time. Thus, the time complexity for connecting si and ti , 1 ≤ i ≤ k, is O(|F| + kn). Theorem 12 shows that (n−2k, 2) is a features number of Gn for the k-pairwise routing problem. We prove that (n − 2k, 2) is an OCFT number. Theorem 13. (n − 2k, 2) is an OCFT number of Gn for the k-pairwise routing problem. Proof. To prove (n − 2k, 2) is an OCFT number, we need to show that for any (m, d) with (n − 2k, 2) < (m, d), (m, d) is not a features number. Let (m, d) = (n − 2k + 1, 2). For the node s, let F = {{s(i) }|2 ≤ i ≤ n − 2(k − 1)}. Then, |F| ≤ n − 2k + 1 and d(F) ≤ 2, but Gn \F becomes a (2k − 2)-connected graph. A necessary condition of a graph to have k disjoint paths for the k-pairwise routing problem is that the graph is (2k − 1)connected [28]. Therefore, (n−2k+1, 2) is not a features number for the k-pairwise routing problem. By a similar argument, we can show that (n − 2k, 3) is not a features number as well. 5. CONCLUDING REMARKS In this paper, we discussed the node-to-set and the k-pairwise routing problems in star graphs. We proved that a faulty cluster of diameter at most 2 can be treated as a single fault in the n-dimensional star graph Gn for the two routing problems. This shows that Gn has very attractive fault-tolerant properties. We also presented algorithms for the node-to-set and the k-pairwise routing problems in Gn . Our algorithms run in optimal time and the lengths of the found routing paths are the diameter of Gn plus small constants. It is interesting to study CFT routing problems in star graphs for d(F) > 2. Investigating CFT routing properties and designing efficient CFT routing algorithms for other interconnection networks are certainly worth further research attention. Acknowledgments The authors are grateful to the anonymous reviewers for their constructive comments. Notes 1. The partial order ≤ is defined as (m, d, l) ≤ (m0 , d0 , l0 ) if m ≤ m0 , d ≤ d0 , and l ≤ l0 . (m, d, l) < (m0 , d0 , l0 ) if (m, d, l) ≤ (m0 , d0 , l0 ) and (m, d, l) ≠ (m0 , d0 , l0 ). REFERENCES [1] S.B. Akers and B. Krishnamurthy, A group theoretic model for symmetric interconnection networks, IEEE Trans Comput 38 (1989), 555–566. [2] S.G. Akl and K. Qiu, Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry, Networks 23 (1993), 215–225. [3] J.C. Bermond, Interconnection networks, Discr Appl Math [Special issue (edited)] (1992). [4] J.C. Bermond, N. Homobono, and C. Peyrat, Large fault-tolerant interconnection networks, Graphs Combin 5 (1989). [5] K. Day and A. Tripathi, A comparative study of topological properties of hypercubes and star graphs, IEEE Trans Parallel Distrib Syst 5 (1994), 31–38. [6] M. Dietzfelbinger, S. Madhavapeddy, and I.H. Sudborough, “Three disjoint path paradigms in star networks,” Proc IEEE Symp Parallel and Distributed Processing, 1991, pp. 400–406. [7] A.H. Esfahanian, Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans Comput 38 (1989), 1586–1591. [8] F. Fragopoulou and S.G. Akl, A parallel algorithm for computing fourier transforms on the star graph, IEEE Trans Parallel Distrib Syst 5 (1994), 100–106. [9] F. Fragopoulou and S.G. Akl, Optimal communication algorithms on star graphs using spanning tree constructions, J Parallel Distrib Comput 24 (1995), 55–71. [10] M.R. Garey and D.S. Johnson, Computers and intractability, A guide to the theory of NP-completeness, Freeman, New York, 1979. [11] Q. Gu and S. Peng, Efficient algorithms for disjoint paths in star graphs, Proc 6th Transputer/Occam Int Conf, 1994, pp. 53–65. [12] Q. Gu and S. Peng, Node-to-node cluster fault tolerant routing in star graphs, Inf Process Lett 56 (1995), 29–35. [13] Q. Gu and S. Peng, k-pairwise cluster fault tolerant routing in hypercubes, IEEE Trans Comput 46 (1997), 1042–1049. [14] Q. Gu and S. Peng, Node-to-set disjoint paths problem in star graphs, Inf Process Lett 62 (1997), 201–207. [15] D.F. Hsu, Interconnection networks and algorithms, Networks (special issue) 23(4) (1993). [16] D.F. Hsu, On container with width and length in graphs, groups, and networks, IEICE Trans Fundam Elect Inf Comput Sci E77-A(4) (1994), 668–680. [17] Z. Jovanovic and J. Misic, Fault tolerance of the star graph interconnection network, Inf Process Lett 49 (1994), 145– 150. [18] R.M. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975), 45–68. [19] S. Latifi, On the fault-diameter of the star graph, Inf Process Lett 46 (1993), 143–150. [20] S. Latifi, M. Hedge, and M. Naraghi-Pour, Conditional connectivity measures for large multi-processor systems, IEEE Trans Comput 43 (1994), 218–222. [21] J.F. Lynch, The equivalence of theorem proving and the interconnection problem, ACM SIGDA Newsl 5 (1975), 3. [22] S. Madhavapeddy and I.H. Sudborough, “A topological property of hypercubes: Node disjoint paths.” Proc 2nd IEEE Symp on Parallel and Distributed Processing, 1990, pp. 532–539. NETWORKS–2000 89 [23] J. McHugh, Algorithmic graph theory, Prentice-Hall, Englewood Cliffs, NJ, 1990. [24] M.A. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, J ACM 36 (1989), 335– 348. [25] Y. Rouskov and P.K. Srimani, Fault diameter of star graphs, Inf Process Lett 48 (1993), 234–251. 90 NETWORKS–2000 [26] Y. Shiloach, The two paths problem is polynomial, Technical Report STAN-CS-78-654, Stanford University, 1978. [27] S.B. Tien and C.S. Raghavendra, Algorithms and bounds for shortest paths and diameter in faulty hypercubes, IEEE Trans Parallel Distrib Syst 4 (1993), 713–718. [28] M. Watkin, On the existence of certain disjoint arcs in graphs, Duke Math J (1968).

1/--страниц