close

Вход

Забыли?

вход по аккаунту

?

197

код для вставкиСкачать
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).
Документ
Категория
Без категории
Просмотров
4
Размер файла
150 Кб
Теги
197
1/--страниц
Пожаловаться на содержимое документа