Linear Recursive Networks and Their Applications in Distributed Systems.
AbstractWe present a new class of interconnection topologies called the Linear Recursive Networks (LRNs) and examine their possible applications in distributed systems. Each LRN is characterized by a recursive pattern of interconnection which can be specified by simple parameters. Basic properties such as node degree, diameter, and the performance of routing algorithms for all LRNs are then collectively analyzed in terms of these parameters. By choosing appropriate values for the parameters, our results can assist a network designer in selecting a topology with required routing performance and cost of interconnection. A subclass of LRNs, called Congruent LRNs (CLRNs), is also identified here and shown to possess desirable properties for more tightly coupled systems. It is shown that the CLRNs include existing networks such as hypercube and generalized Fibonacci cubes. These results suggest that the linear recursive networks potentially have applications in interconnecting distributed systems.
INTRODUCTION
HEN designing the network topology of a distributed
system, one attempts to satisfy as much as possible
certain basic requirements such as routing efficiency,
minimal cost of links, maximal concurrency, fault tolerance,
and scalability (see, e.g., [1], [4], [14], [10]). It often appears
that some of these requirements dictate conflicting approaches
which can only be resolved by ad hoc methods
and exhaustive simulations [4], [14].
The complexity of the network designer's task can be reduced
if the network topology assumes a certain degree of
regularity. 1 Among other benefits, the simplicity of the
naming and addressing conventions of such network tends
to facilitate efficient routing and reduce software cost. For
example, various topologies such as meshes, rings, trees,
and combinations of several topologies [14] have been proposed
and useful results have been obtained. However,
there are relatively few existing results that quantitatively
relate these individual networks. As such, it is rather difficult
to choose a network topology to fulfill the different
requirements. One objective of this paper, therefore, is to
alleviate the difficulty of choice by contributing a new family
of network topologies that span from loosely connected
to densely connected topologies. As will be seen, these
network topologies satisfy many of the basic requirements
mentioned earlier.
We will present the Linear Recursive Networks which include
the hypercube [11] and the Generalized Fibonacci
cubes [7], [8] as special cases. Each member of these networks
will be parameterized by a generator (call it A) and a
dimension n. Properties of the class of networks are then
analyzed and performance of the algorithms is determined
in terms of A and n. The main advantages of this approach
include:
. Since the cost, performance, and reliability of a fairly
large class of networks are expressed in terms of the
same parameters (viz. A and n), one analysis economically
applies to all the networks.
. The parameters provide a quantitative link between
individual networks; the results can also be applied to
yield a network with a prescribed connection cost,
routing performance, and degree of fault tolerance.
Each n-dimensional Linear Recursive Network (or LRN for
short) is generally associated with a linear recurrence of the
are nonnegative integers and a k # 0. In the recurrence, the
subscript n corresponds to the dimension of the network
(which itself is symbolized by the notation X n ), while the
parameter a i signifies the number of occurrences of a lower
dimension network X n-i (i.e., the (n - i)-dimensional net-
work) within the n-dimensional network. For instance, the
recursion would correspond to the binary n-cube,
because each n-dimensional hypercube consists of two
copies of (n - 1)-dimensional hypercube. Similarly, the Fibonacci
cube [8], [7] can be characterized by the recursion
because an n-dimensional network consists
of a copy of (n -1)-dimensional network and a copy of
(n - 2)-dimensional network. With any recursive network,
the boundary conditions determine the actual number of
nodes in the network, and different boundary conditions
give rise to (minor) variations of network topologies. How-
ever, the more significant properties (such as diameter,
. W.-J. Hsu and A. Das are with the Division of Software Systems, School of
Applied Science, Nanyang Technological University, Singapore.
E-mail: hsu@ntu.edu.sg.
. M.J. Chung is with the Department of Computer Science, Michigan State
University, East Lansing, MI 48824.
Manuscript received 24 May 1994.
For information on obtaining reprints of this article, please send e-mail to:
transtpds@computer.org, and reference IEEECS Log Number 100868.0.
1. By regularity in the network topology, we will mean recursiveness in
the underlying graph. The term will have a more definite and quantitative
meaning later when the graph is defined.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 6, JUNE 1997
J:\PRODUCTION\TPDS\2-INPROD\100868.0\100868_1.DOC regularpaper97.dot JT 19,968 04/01/97 11:58 AM 2 / 8
bisection width, and scalability, etc.) are determined by the
recursion.
Let N denote the number of nodes in the network. The
following are some of the basic properties of the LRNs and
their possible applications to network designs:
1) The degree of each node in an LRN is bounded by a
logarithmic function of N. The total number of links
(edges) is bounded by O(N log N). The multiplier is a
constant characteristic of the generator A.
2) The diameter of such a network is bounded above by
O(log N). This implies that two arbitrary nodes in an
LRN can communicate by going over no more than
O(log N) intermediate nodes. A Point-To-Point communication
(i.e., Send or Receive, cf. Section 4) of a
message of L units can be achieved in no more than O
(Max {log N, L}) time steps.
An LRN embeds a spanning rooted tree with a depth
of O(log N), which implies that each broadcasting operation
can be done with at most O(log N) set-up
steps. A Single-node Broadcast operation can be done
in O(Max {log N, L}) time steps, where L denotes the
length of a broadcast message. The same tree can also
be used to perform multicasting simply and efficiently.
A subclass of the LRNs called the Congruent LRNs is
of particular interest. Specifically, there are Q(log N)
node-disjoint (hence, edge-disjoint) paths between
any pair of nodes in a CLRN. This property implies
that in such a network two nodes can communicate
by using alternative or concurrent routes. As a result,
the communication can be done even more reliably
and efficiently. The CLRNs also form a hierarchy in
terms of graph-containment relations: A CLRN is generally
a subgraph of many other CLRNS. This property
implies that a network based on the CLRN is scalable.
Therefore, the basic requirements of interconnection topologies
(in terms of routing efficiency, minimal cost, fault-
tolerance, and scalability) can be accommodated by considering
the Linear Recursive Networks.
Apart from the intuitive (but informal) derivation based
on the recurrence relations, LRNs can also be conveniently
(and formally) derived from the hypercube. The set of
nodes in an n-dimensional hypercube corresponds exactly
with the set of n-bit binary codes (call it 0 1
< A n

Clearly, a
subset of 0 1
< A n
* also corresponds to a subgraph of the hy-
percube. But what subgraphs possess the desirable properties
mentioned in the preceding paragraph? A critical step
in our scheme, therefore, is to find a systematic way to generate
bit strings.
It turns out that the theory of formal languages (see, e.g.,
[6]) can be applied to precisely describe the LRNs. The following
is an outline of the key developments:
Associated with an (arbitrary) string A, define a set of
strings of length n which are used to label the nodes
of G n (A), the n-dimensional LRN associated with A.
The edges of G n (A) are determined by the Hamming
distance between the node labels.
We will show that G n (A) can be recursively decomposed
(partitioned) into disjoint subgraphs such that
each subgraph is also G k (A) for some k < n. Moreover,
this decomposition can be easily derived from the
generating string A.
We then identify a subclass of LRNs (called the Congruent
LRNs, or CLRNs) that have strong regularity.
Applications of the LRNs are then presented.
The remainder of the paper is organized as follows.
Section 2 lists the notations that will be used throughout
the paper. Then LRNs are defined formally. Section 3 presents
some basic properties of the LRNs including the number
of nodes, number of edges, degrees, distance between
two nodes, diameter, recurrence in the network structure,
and so on. Section 4 presents the applications of the LRNs
to basic data routing functions such as point-to-point
send/receive, multicasting, and broadcasting/gathering.
Section 5 briefly summarizes the results.
A finite set of symbols is called an alphabet. We will confine
ourselves to the binary alphabet Thus, a symbol
will also be called a bit. A string is a finite sequence of sym-
bols. The null string, denoted by l, is a string of length zero.
A language is a collection of strings. The set of binary strings
of length n will be denoted by - *
be two strings. The
following notations will be used throughout the paper.
. We let A the string obtained by appending
A with B, i.e., A . Note that
l
. For a language L, we let A o L denote the set {A
. A k denotes the string obtained by repeating a symbol
A k times.
. Let S [i] denote the string obtained from complementing
the string S at the ith bit.
. We denote the number of 1-bits in A by the symbol
Weight(A).
. If to denote the Hamming
distance between A and B, i.e., the number of bits
where the two strings differ.
Let A denote a given string. In the following paragraphs,
we will generate a language L n (A) to label the vertices of the
target network G n (A).
First, expand the string A with a 1-bit at either end to
avoid trivial recursions. Let A A a a a a A
denote the resulting string. Let be the sequence
of positions in A + that contain the 1-bit. That is,
a a a
K and a other values of i. A
seed is a string obtained by complementing the last bit of a
prefix of A + that ends in one. That is, for each i OE J, a seed A
is defined as A
seed strings.
HSU ET AL.: LINEAR RECURSIVE NETWORKS AND THEIR APPLICATIONS IN DISTRIBUTED SYSTEMS 3
J:\PRODUCTION\TPDS\2-INPROD\100868.0\100868_1.DOC regularpaper97.dot JT 19,968 04/01/97 11:58 AM 3 / 8
EXAMPLE 1. Let
1010001, the 1-bit po-
and the seed strings are
. Notice that each
seed string A j matches the prefix of A j +1
except at the
last bit.
The following lemma will be needed to guarantee the
existence of certain nodes (e.g., node 0 n in an arbitrary
n-dimensional LRN).
2.1. Let the seed strings A A A
, , K be as defined in
the preceding paragraph. Then
PROOF. The lemma follows directly from the definition of A j .+
Now we are ready to define L n (A).
DEFINITION 1. The language L n (A) (called node labels) is defined
recursively as follows:
For
2. Let 10101. The seed strings are
Recall that if L is a language, A
0100, 0101, 1000, 1001, 1010}.
Now the Linear Recursive Networks can be formally
defined.
DEFINITION 2. Let A denote a given string, n be a nonnegative
integer, and the language L n (A) be as defined previously.
Each instance of G n (A) will be referred to as a Linear
Recursive Network, or LRN for short. The string A is
said to be a generator of G n (A). The parameter n is said to
be the dimension of the network. The set
will be referred to as the family of LRNs generated
by A, and the set as the Class of LRNs.
We have restricted ourselves to the binary alphabet.
However, it can be readily seen that the same concepts extend
to arbitrary alphabets [9].
EXAMPLE 3. Fig. 1 shows G i (A) for A
The nodes of G (A) are labeled by the strings in L i (A).
Fig. 1. Linear Recursive Networks generated by A
4 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 6, JUNE 1997
J:\PRODUCTION\TPDS\2-INPROD\100868.0\100868_1.DOC regularpaper97.dot JT 19,968 04/01/97 11:58 AM 4 / 8
It can be seen that G 5 # G 4 # G 3 # G 0 , where G # H
denotes that H is a subgraph of G.
EXAMPLE 4. The generalized Fibonacci cubes in [8], [7] are
LRNs with generators of the form:
It can be shown that the hypercubes of
any dimension can be generated by 1 k for
they are special cases of the generalized Fibonacci
cubes [8], and, hence, they are also LRNs.
Let (A) be as defined in the preceding section.
Since both the vertices and edges of the networks are based
on the strings in L n (A), the properties of the network clearly
are determined by the language. For example, because of
the recursive construction of L n (A), an LRN of higher dimension
generally contains other LRNs of lower dimen-
sions. In Fig. 1, for instance, G 5 contains one copy of G 4 , one
In fact, the recursive decomposition can be
inferred from the string A 10101. This property will be
further investigated here. Let # denote the "isomorphic"
relations between graphs, i.e., iff the two graphs are
identical up to the renaming of the nodes. The following
lemma formally states this important topological property
[3]. As before, let
denote the list of 1-bits in the augmented string A + .
LEMMA 3.1 (Decomposition Lemma). Let G n (A) be an LRN, the
indices be defined as before. Then, for all n #
can be decomposed into a set of m subgraphs
, such that
PROOF. The lemma can be established in two steps:
Since the set of vertices
and, by definition, L A A L A
should be clear that each language A L A
induces a subgraph g i of G n (A) and g G A
# .
Hence, two strings that are prefixed by A j k
and A j ,
respectively, cannot be equal. Therefore, for k # l,
A L A A L A
In other words,
the subgraphs induced by these two subsets must
be disjoint, i.e.,
COROLLARY 3.2. Let G denote an LRN.
Then, for all n # |A|, the number of nodes iV n (A)i observes
the recurrence relation: iV n
the n-dimensional hypercube defined
by
LEMMA 3.3. Let B n and G n (A) denote the hypercube and LRN,
respectively. Then G
PROOF. The lemma follows immediately by noting that
both interconnection topologies are based on the
same Hamming distance between the nodes, and
By Lemma 3.3, the total number of nodes in G n (A) cannot
exceed 2 n . The following theorem states a more precise result
about the combinatorial aspects of an LRN.
THEOREM 3.4. Let G n (A) be an arbitrary LRN of dimension n as
defined
1) The number of nodes N in G n (A) is given by Q d A
where d A denotes a constant characteristic of the generating
string A. For all A OE S* of finite length, 1 < d A < 2.
2) The degree of each node in G n (A) is bounded by n.
The number of edges is bounded by O(N log N).
PROOF. By Corollary 3.2, iV (A)i. It is not difficult
to verify (by induction on n) that N A
for
some 1 < d A - 2. In other words,
For the upper bound of node degrees, it suffices to
note that
1) each node is labeled by a bit string B of length n,
and
2) at most one neighbor is obtained by complementing
a bit in B.
Therefore, each node has no more than n edges.
By Statements 1 and 2, the total number of edges is
no more than n -
It can be shown that for any binary string A and any integer
# 0, the LRN G n (A) is connected. The following
Theorem 3.6 shows a slightly stronger result by giving a
bound on the maximum distance between two vertices. The
following lemma is in order.
LEMMA 3.5. Let G denote an LRN.
denote the string that consists of n consecutive
0s. Then 0
is the rightmost 1-bit in B. Then B b b b
PROOF. (

Appendix

THEOREM 3.6. Let D(x, y) denote the distance between two nodes
x and y in G n (A), an LRN. Then D(x,
PROOF. Lemma 3.5 shows that the node 0 n is in G n for all
LRNs. We will show that the node 0 n is reachable
from any other nodes in G n . Let
Lemma 3.5, complementing the rightmost 1-bit in x
will get another node x- OE G n . Apply the same procedure
to x- and so on. Eventually this will lead us to 0 n .
HSU ET AL.: LINEAR RECURSIVE NETWORKS AND THEIR APPLICATIONS IN DISTRIBUTED SYSTEMS 5
J:\PRODUCTION\TPDS\2-INPROD\100868.0\100868_1.DOC regularpaper97.dot JT 19,968 04/01/97 11:58 AM 5 / 8
This shows a path P 1 of length Weight(x) from x to 0 n
Apply the same procedure to node y to obtain a second
path P 2 from y to 0 n . The result follows immediately
by connecting P 1 and P 2 .
In the following, we identify an infinite subset of LRNs
(called the Congruent LRNs) that always have multiple
edge-disjoint paths between two arbitrary nodes. Inciden-
tally, the generalized Fibonacci cubes described in [7], [8] (and
hence hypercubes) are all CLRNs.
3.1 Congruent LRNs: Recursive Networks with
Strong Connectivity
Again, let be the set of nonzero positions in
the augmented string A
DEFINITION 3. An LRN G n (A) is said to be a Congruent LRN,
or CLRN for short, iff j is a constant for all 1 - i < m.
The LRNs shown in Fig. 1 are examples of Congruent
LRNs. It can be seen that G 5 contains a copy of G 4 and a
copy of G 2 . Since G 4 also contains a copy of G 2 , G 5 contains
two copies of G 2 . Note that there are edges connecting these
two copies of G 2 in G 5 . This important property of the
CLRNs distinguishes themselves from the other LRNs and
makes them more robust structures in terms of the number
of independent paths (i.e., the paths are node-disjoint or
edge-disjoint [5], [2]) between a pair of nodes. The following
lemma lists additional properties of the Congruent
LRNs.
LEMMA 3.7. Let G n (A) be an arbitrary CLRN and
can be decomposed
into a set of m subgraphs m such that
(Recursive Decomposition) g G A
and
(Self-Similarity) For each g , where 1 < i - m, there is a
subgraph g k,i of g k for all 1 - k < i such that g k,i # g .
(Edge between Corresponding Nodes) For each node
there exists a unique node v k OE
PROOF. (

Appendix

B).
Because of the regularity in the generator, the CLRNs
have stronger connectivities as shown below.
LEMMA 3.8. Let N denote the number of nodes in an n-dimensional
CLRN G n (A). Then
1) The node degrees of G n (A) is no more than n. The total
number of edges is bounded exactly by Q(N log N).
2) The distance between two nodes x and y is equal to the
Hamming distance H(x, y). The diameter of G n (A) is
bounded above by n.
There exist Q(log N) node-disjoint paths between any
two nodes.
PROOF. (

Appendix

C).
The diameter of a network, which determines the maximum
delay in the setup time for a communication between two
nodes, is the maximum distance between any pair of nodes
in the network. Let N denote the number of nodes in the
network. By Theorem 3.6, the diameter of an LRN is
bounded above by O(log N). The number of links on a node
is often a concern in implementation. By Theorem 3.6, each
node is connected to O(log N) other nodes. As can be seen,
both the number of nodes and the density of interconnections
are scalable and can be linked to the cost and performance
requirements. We will further consider the applications
of LRNs to the following data communication tasks:
Point-To-Point Send/Receive and Broadcast/Gather.
4.1 Point-to-Point Communications
A Single-node Send is the sending of a message from a source
node to a destination node. The Single-node Receive operation
is the receiving from a node, essentially the reverse of the
send operation. Together they will be referred to as PTP
(Point-To-Point) Communications. For the performance
analysis, by the multiport model we will mean that all incident
links of a given node can be used simultaneously to
transmit data. The uniport model is more restrictive, allowing
at most one active incident link at a time. We will assume
that each intermediate node takes one unit time to
receive, setup, and forward a unit-length message.
The constructive proof in Theorem 3.6 provides a primitive
algorithm for the point-to-point communications. The
following lemma states a more general result.
THEOREM 4.1. Let N denote the total number of nodes in an LRN.
A Point-To-Point communication (i.e., a Single-node Send
and Single-node Receive operation) of a message of L
units can be achieved in no more than O(Max {log N, L})
time steps under the uniport model. With the Congruent
LRNs, the Point-To-Point operation can be done
O Max N L
log , log
time under the multiport model.
PROOF. It is readily seen that an algorithm for either Send or
Receive can be adapted for the other, and it suffices to
consider the Send operation.
First, consider the uniport model. To route a message
of L units, the data is sent in a pipelined fashion:
in Step j, each node i on the path sends the unit-length
data received at Step j - 1. By Theorem 3.6, it takes at
most O(log N) time steps for the first unit of data to
arrive at the destination and L - 1 more time steps for
the last unit to reach the destination. Hence, the total
is bounded by O(Max {log N, L}) time steps.
Now consider the CLRNs. Under the multiport
model, the L units can be split up and sent concurrently
by using the node-disjoint paths. By Lemma 3.8, there
are Q(log N) such paths. The result follows.
With the CLRNs, since there are multiple node-disjoint
paths between any two nodes, the communication can be
done more efficiently and reliably. Specifically, because of
the independent paths, up to O(log N) failures on any link
or node (except the source and the destination nodes) can
be tolerated without disrupting the data communication.
Now we show that the throughput of the PTP traffic on
the CLRN is lower bounded by W(N) under uniform loading.
6 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 6, JUNE 1997
J:\PRODUCTION\TPDS\2-INPROD\100868.0\100868_1.DOC regularpaper97.dot JT 19,968 04/01/97 11:58 AM 6 / 8
The diameter of an LRN is bounded by O(log N). Therefore,
the expected number of hops between two randomly selected
users is also given by E[number of
N). In other words, under uniform loading, the link
efficiency
number of hops
W log .
Since the total number of links is in the order of Q(N log N),
the network throughput is in the order of W(N). By using a
similar analysis, it can be shown that the network through-put
of a general LRN is at least W N
log
4 9 .
The following discusses Broadcasting and Gathering,
which are many-to-one and one-to-many operations, respectively

4.2 Data Broadcasting and Gathering
To Single-node Broadcast is to send a message from a source
node to all the other nodes in the network. The Gathering
operation is the reverse, i.e., receiving from the other nodes.
Again, because of the apparent symmetry, we will concentrate
on the broadcast algorithm.
We will show that each LRN embeds a spanning tree
which can be applied to efficiently perform the broadcasting
operation. For this purpose, a spanning tree in the hypercube
is considered. A binomial tree of dimension n, denoted
BT n , is a tree obtained from two copies of BT n-1 by
making the root of one of the trees a child of the root of the
other tree. As the basis of the recursive definition, BT 0 consists
of a single node.
LEMMA 4.3. Let G n (A) be an LRN. For all n # 0 and A OE S*,
there exists a spanning tree T of G n (A) rooted at node 0 n
such that
2) the height of T is bounded by n.
PROOF. By Theorem 3.6, G n (A) is connected, so a spanning
tree exists trivially. It remains to show that there is a
spanning tree T such that T - BT n . Recall that a spanning
tree of G n (A) must contain all the vertices in
define T to be the subgraph of BT n induced
by the set V n (A). We now show that T is connected
and, therefore, it is a tree (and hence a spanning tree
of G n (A)).
Assume for contradiction that T is not connected.
In other words, there exists a tree edge <x, y> in
such that the parent x oe T, while the child y OE T. In
Fig. 2), a parent (here, x) is obtained by complementing
the rightmost 1-bit of a child (y here).
Now, by Lemma 3.5, the same property applies to the
nodes in V n . Therefore, if y OE T, then its parent x OE T.
A contradiction.
Since BT n has a height of n, the height of T cannot
exceed n.
We have the following theorem:
THEOREM 4.4. Let N denote the number of nodes in an arbitrary
LRN. Let L denote the length of a data item. A Single-node
Broadcast operation can be done in O(Max {log N, L}) time
steps under the uniport model. The Single-node Gathering
operation can be done in similar time. With the CLRNs,
both operations can be done in O Max N L
log , log
time
under the multiport model.
PROOF. The broadcasting can be performed in two steps,
which have the same time complexity:
1) Send the broadcast message from the source to the
node 0 n . By Theorem 4.1 (Point-To-Point Commu-
nication), this step can be done in O(Max {log N, L})
time steps under the uniport model and, with
CLRNs, in O Max N L
log , log
time by using the
multiports concurrently.
Initiate the broadcast by using the subtree of the
binomial tree embedded in the underlying graph.
By Lemma 4.2, this step can be done in O(Max
{log N, L}) time steps under the uniport model and,
with CLRNs, in O Max N L
log , log
steps under
the multiport model.
The conclusion follows.


We have presented a new class of parameterized networks,
namely, the Linear Recursive Networks, and analyzed the
entire class in terms of the routing efficiency, reliability, and
cost issues. We have demonstrated that each member of
this fairly large class of network topologies exhibits a
structural recurrence that can assist in the performance
evaluation. We also demonstrated that the point-to-point
send/receive, multicasting, and broadcasting/gathering
can be done rather efficiently on all LRNs. We feel that
these results suggest that the Linear Recursive Networks
may find applications in large-scale distributed systems.
Therefore, further investigation of the new topologies is
deserved.
Fig. 2. A binomial tree with node labels.
HSU ET AL.: LINEAR RECURSIVE NETWORKS AND THEIR APPLICATIONS IN DISTRIBUTED SYSTEMS 7
J:\PRODUCTION\TPDS\2-INPROD\100868.0\100868_1.DOC regularpaper97.dot JT 19,968 04/01/97 11:58 AM 7 / 8






A
PROOF OF LEMMA 3.5. Statement 1 can be proved by induction
on n. Two key steps are:
Recall that (A). It is straightforward to
verify that 0 i OE (induction basis).
consider the subset A L A
j1= by Lemma 2.1 and 0 1n j
by induction hypothesis, so A L A
Statement (2) can be proved in a similar fashion.



PROOF OF LEMMA 3.7. By Lemma 3.1, Statement 1 is valid for
all LRNs, of which CLRNs are subsets.
Statements 2 and 3 can be verified together. Let j , j k
OE J and 1 - k < i. The key is to show that for each node
x
there is a unique counterpart y g
such that (x, y k,i In other words, for
each x A L A
there exists a unique y A
Assume that x A S
that X [r] denotes the string obtained by complementing
the rth bit (from left) of X. Let y A S
It should be clear that H(x, y k,i
We need further prove that y A L A
By assumption, j
which may be rewritten as
1. By simple induction,
Also, as a simple extension of Lemma 2.1, A j
A A A L A
c
Therefore,
y A S
A A S A L A
A L A A L A
c
We conclude that the claim is true.



PROOF OF LEMMA 3.8. Without loss of generality, let n denote
a sufficiently large integer. By definition of the language
can be decomposed into
segments: c 1
equal to some seed A y . There are two cases when we
can modify one bit of the segments to obtain a neighbor
of C.
. In this case, by Lemma 2.1, there is at least
one 1-bit in the segment. As a simple extension to
Lemma 3.5, complementing any 1-bit in each c
will obtain a legitimate code in V j y
. Therefore, each
1-bit in c i corresponds to a neighbor.
. In this case, complementing the 0-bit in
such c i may not obtain a valid code. However,
when there are consecutively j 2 such segments,
then the first 0-bit can be complemented to obtain a
valid code (which, by Lemma 2.1, is equal to A j 2
We will consider these segments as forming a
single component.
For the following discussion, call a segment or component
nontrivial if it can be modified to obtain a valid
code (by either complementing a 1- or 0-bit). There are
at least u
nontrivial segments/components
in C. In other words, there are at least u neighbors of
the node C in V n (A). It should be clear that
Q(log N). Statement 1 follows trivially.
For Statement 2, let S and T denote two nodes in
denote the difference vector of S and T,
obtained by exclusive-ORing S and T. The following
construction is meant to show a path between S and T:
Complement every 1-bit in S that is also a 1-bit in C.
Let the result be denoted by S-.
Complement every 1-bit in T that is also a 1-bit in C.
Let the result be denoted by T-.
It is easy to verify the following facts from the construction

From the above, Statement 2 follows.
For the construction of disjoint paths, note that two
different sequences in complementing the bits correspond
to two different paths. To obtain node-disjoint
paths, the following standard strategy can be applied:
For the first path, modify the first nontrivial component
(by changing either the suitable 1-bit or 0-bit),
then modify the second component, and so on. In
general, for the ith path, modify the ith component
first, followed by modifying the (i
and so on for the remaining components in a cyclic
fashion.

ACKNOWLEDGMENTS

Wen-Jing Hsu would like to dedicate this paper to the
memory of his father.



--R

Data Networks.
Graph Theory with Application to Engineering and Computer Science
"Recursive Formula for the Calculation of Point- to-Point Congestion,"
"On the Topological Design of Distributed Computer Networks,"
Graph Theory.
Introduction to Automata Theory
"Fibonacci Cubes: A New Class of Interconnection Topologies for Parallel Processing,"
"Generalized Fibonacci Cubes,"
"Linear Recursive Graphs and Their Applications in Network Topological Design and Data Routing,"
Distributed Computing: Network Reliabil- ity
Hypercube Algorithms (With Applications to Image Processing and Pattern Recognition).
"On Reliability Evaluation by Network Decompo- sition,"
"Network Reliability and the Factoring Theorem,"
The Art and Science of Network Design.
--TR

--CTR
Peter K. K. Loh , H. Schrder , W. J. Hsu, Fault-tolerant routing on complete Josephus Cubes, Australian Computer Science Communications, v.23 n.4, p.95-104, January 2001
Peter K. K. Loh , Wen Jing Hsu, The Josephus cube: analysis of routing and fault tolerance, Journal of Parallel and Distributed Computing, v.65 n.1, p.58-64, January 2005
Peter K. K. Loh , W. J. Hsu, Fault-tolerant routing for complete Josephus cubes, Parallel Computing, v.30 n.9-10, p.1151-1167, September/October 2004
Peter K. K. Loh , W. J. Hsu, Fault-tolerance of Complete Josephus Cubes, Journal of Systems Architecture: the EUROMICRO Journal, v.49 n.1-2, p.1-21, July
Yuzhong Sun , Paul Y. S. Cheung , Xiaola Lin, Recursive Cube of Rings: A New Topology for Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.275-286, March 2000
Masaru Takesue, The psi-cube: a bus-based cube-type clustering network for high-performance on-chip systems, Parallel Computing, v.32 n.11-12, p.852-869, December, 2006
Wong Han Min , Bharadwaj Veeravalli , Gerassimos Barlas, Design and performance evaluation of load distribution strategies for multiple divisible loads on heterogeneous linear daisy chain networks, Journal of Parallel and Distributed Computing, v.65 n.12, p.1558-1577, December 2005
Jingnan Yao , Bharadwaj Veeravalli, Design and Performance Analysis of Divisible Load Scheduling Strategies on Arbitrary Graphs, Cluster Computing, v.7 n.2, p.191-207, April 2004
hypercube;self-similar networks;fibonacci cube;routing algorithms;recursive networks;design and analysis of interconnection topologies