Transcript highly resilient

Minimal Fault Diameter
for Highly Resilient
Product Networks
Khaled Day, Abdel-Elah Al-Ayyoub
IEEE Trans. On Parallel and Distributed Systems
2000 vol. 11, no 9
Speaker: Y-Chuang Chen
Abstract
Fault tolerance of Cartesian Product.
 A method for building containers (a set of nodedisjoint paths) between any two nodes of a
product network.
 Show the best achieve fault diameter.
 highly resilient and minimal fault diameter
=> Cartesian product =>
still highly resilient and minimal fault diameter

Some definitions

Node-connectivity, diameter, fault-diameter
Definition 1: Cartesian product

1.
2.
The Cartesian product G = G1G2 of two
graphs G1=(V1,E1) and G2=(V2,E2) is the
graph G=(V,E), where the set of nodes V
and the set of edges E are given by:
V = { x,y | xV1 and yV2 }, and
For u = xu,yu and v = xv,yv in V, (u,v)E
iff (xu,yv)E1 and yu=yv, or (yu,yv)E2 and
xu=xv.
Definition 2: container K



A container K between two nodes u and v
in a graph G is a set of node-disjoint paths
joining nodes u and v.
The width of K is the number of paths on K.
In a regular graph G, a container is of
maximum width if its width is equal to the
degree of G.
Lemma 1: some known results

1.
2.
3.
4.
Let u = xu,yu and v = xv,yv be two nodes
in G1G2. The following properties holds:
G1G2 is isomorphic to G2G1.
|G1G2| = |G1|  |G2|
D(G1G2) = D(G1) +D(G2).
 (G1G2)  (G1) + (G2).
Maximum-Width Containers in
Products Networks

They show how to construct a maximumwidth container between any two nodes in
G1 G2 .
Some notations




D(G): the diameter of a graph G.
L(K): the length of a longest path in the
container K.
l(K): the length of a shortest path in the
container K.
Df(G): fault diameter of G; the maximum
diameter of any subgraph of G obtained by
deleting less than (G) nodes from G.
Lemma 2. Container

Let u = xu,yu and v = xv,yv be two nodes
in G1G2 such xuxv and yuyv. If there is a
container K1 of width w1 between xu and xv
in G1 and a container K2 of width w2
between yu and yv in G2, then there is in
G1G2 a container K of width w1 + w2
between u and v. Furthermore, L(K) =
max{L(K1)+l(K2), l(K1)+L(K2)} and
l(K)=l(K1)+l(K2).
Lemma 3.


Let u = xu,yu and v = xv,yv be two nodes in
G1G2 such xuxv and yu=yv. If there is a container
K1 of width w1 between xu and xv in G1 and if
degG2(yu) = 2, then there is in G1G2 a container K
of width w1 + 2 between u= xu,yu and v= xv,yv.
Furthermore, L(K) = max{L(K1), l(K1)+2} and
l(K)=l(K1).
Notice that since G1G2 = G2G1, a similar result
holds for xu=xv and yuyv.
Theorem 1.

If G1 and G2 are regular each with a maximumwidth container between every pair of nodes, then
there exists a maximum-width container between
every pair of nodes in G1G2. Furthermore, if each
path in a G1 (resp. G2) container has length at
most L1 (resp. L2) and at least one path is of
length at most l1(resp. l2), then every path in
corresponding G1G2 container has length at most
max(l1+L2, L1+l2, l1+2, l2+2) and at least one path
has length l1+l2.
High Fault Resilience and Minimal
Fault Diameter


A number of interconnection networks are
known to have excellent fault diameter
(equal to diameter plus one).
Eg. Hypercube, star graph, k-ary n-cube,
cube-connected cycles, generalized
hypercubes.
High Fault Resilience and Minimal
Fault Diameter

Definition of highly resilient:
A regular graph G is highly resilient if
between any two nodes of G, there exists a
deg(G)-wide container such that every path
in the container is of length at most
D(G)+1 and at least one path is of length at
most D(G).
Some results


If G1 is regular, G2 is regular, (G1) =
deg(G1), and (G2) = deg(G2), then G1G2
is regular and (G1G2) = deg(G1G2).
The fault diameter Df(G) of any regular
connected graph G of diameter D(G)>2
and of node-connectivity (G) = deg(G)
satisfies Df(G)  D(G)+1.
Some results (cont.)


If G is regular and highly resilient, then (G)
= deg(G). If, in addition, D(G) > 2, then
Df(G) = D(G) +1. (By definition of highly
resilient)
If G1 and G2 are highly resilient regular
graphs, then G1G2 is highly resilient.
Theorem 2. Highly Resilience

If G1 and G2 are highly resilient regular
graphs such that D(G1) + D(G2) > 2, then
G1G2 is highly resilient and Df(G1G2) =
D(G1G2) + 1.
Corollary

If each of G1,G2,…,Gn is a hypercube, a kary n-cube, a star graph, a cube-connected
cycles, or a generalized hypercube, then
the product G1G2…Gn is highly resilience
and has minimal fault diameter provided
that D(G1) + D(G2) + … + D(Gn) > 2.