close

Вход

Забыли?

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

?

269

код для вставкиСкачать
Mean Eccentricities of de Bruijn Networks
Jean-Claude Bermond, 1 Zhen Liu, 2 Michel Syska 1
1
SLOOP, Joint Project 13S-CNRS/UNSA/INRIA, 2004 Route des Lucioles, BP 93, F-06902
Sophia-Antipolis, France
2
2004 Route des Lucioles, BP 93, F-06902 Sophia-Antipolis, France
Received 6 August 1993; accepted 28 February 1997
Abstract: Given a graph G Å (V, E), we define eV ( X ), the mean eccentricity of a vertex X, as the average
distance from X to all the other vertices of the graph. The computation of this parameter appears to be
nontrivial in the case of the de Bruijn networks. In this paper, we consider upper and lower bounds for
eV ( X ). For the directed de Bruijn network, we provide tight bounds as well as the extremal vertices which
reach these bounds. These bounds are expressed as the diameter minus some constants. In the case
of undirected networks, the computation turns out to be more difficult. We provide lower and upper
bounds which differ from the diameter by some small constants. We conjecture that the vertices of the
form arrra have the largest mean eccentricity. Numerical computations indicate that the conjecture
holds for binary de Bruijn networks with diameters up to 18. We also provide a simple recursive scheme
for the computation of the asymptotic mean eccentricity of the vertices arrra. Finally, we prove that
the asymptotic difference, when the diameter goes to infinity, between the mean eccentricities of an
arbitrary vertex and that of arrra is smaller than a small constant tending to zero with the degree. A
byproduct of our analysis is that in both directed and undirected de Bruijn networks most of the vertices
are at distance near from the diameter and that all of the mean eccentricities (and therefore the average
distance) tend to the diameter when the degree goes to infinity. q 1997 John Wiley & Sons, Inc. Networks
30: 187–203, 1997
Keywords: interconnection network; de Bruijn network; distances; mean eccentricities; bounds
1. INTRODUCTION AND NOTATION
Graphs are widely used in the design and analysis of
computer networks. A vertex in the graph denotes a node
or processor in the corresponding network, and an edge
denotes a communication link between two nodes. If a
network is unidirectional, i.e., the communication links
in the network are unidirectional, a digraph (i.e., directed
graph) is used, whereas for a bidirectional network, an
undirected graph (or simply, graph) is used.
Let G Å (V, E) be a (strongly) connected graph (or
digraph), where V denotes the set of vertices, and E, the
set of edges (or arcs for digraphs). We will denote by N
Å ÉV É the number of vertices in G.
The vertex X is a neighbor of the vertex Y if (X, Y )
√ E or (Y, X ) √ E. The degree of a vertex is the number
of its neighbors. The degree of a graph is the maximum
degree of the vertices. In case of a digraph, we can distinguish the predecessors and successors of vertex X, which
correspond to the neighbors Y which satisfy (Y, X ) √ E
and (X, Y ) √ E, respectively. The number of arcs entering (respectively, going out from) a vertex X is called the
q 1997 John Wiley & Sons, Inc.
CCC 0028-3045/97/030187-17
187
/ 8U16$$0780
08-19-97 19:15:05
netwas
W: Networks
780
188
BERMOND, LIU, AND SYSKA
Fig. 1. Example of a de Bruijn digraph B(2, 3).
in-degree (respectively, out-degree) of X. The in-degree
(respectively, out-degree) of a graph is the maximum indegree (respectively, out-degree) of the vertices.
A path (respectively, a dipath) between two vertices
X and Y (respectively, from X to Y ) in a graph (respectively, a digraph) G is a sequence of vertices {X Å X1 ,
X2 , . . . , Xk Å Y } such that two consecutive vertices in
the sequence are joined by an edge (respectively, an arc).
The length of a path is the number of edges on this path.
The length of a shortest path (respectively, dipath) between X and Y (from X to Y ) is called the distance and
is denoted by d(X, Y ). Note that in the case of digraphs
it is not a classical distance as d(X, Y ) might be different
from d(Y, X ). The diameter of a graph is the maximum
distance in the graph.
The de Bruijn digraph (respectively, graph), denoted
by B(d, D) [respectively, UB(d, D)], has N Å d D vertices with diameter D and in-degree or out-degree d (respectively, degree 2d). The vertices correspond to the
words of length D over an alphabet of d symbols. The
arcs (or edges) correspond to the shift operations: Given
a word X Å x1rrrxD on an alphabet A of d letters, where
xi √ A, i Å 1, 2, . . . , D, and given l √ A, the operation
• x1rrrxD r x2rrrxDl is called a left shift;
• x1rrrxD r l x1rrrxD01 is called a right shift.
In the de Bruijn digraph B(d, D), the successors are
obtained by left-shift operations, whereas in the de Bruijn
graph UB(d, D), the neighbors are obtained by either
left- or right-shift operations. An example of a de Bruijn
digraph is given in Figure 1. The corresponding undirected de Bruijn graph is obtained by transforming arcs
to edges (i.e., removing the directions of the arcs) and
removing the redundant edges (i.e., those with multiple
occurrences in the graph or those linking the same vertices). The multiprocessor system which can be modeled
by a de Bruijn graph is called a de Bruijn network.
The reader can see that in B(d, D) each vertex has
in-degree and out-degree d and there are Nd arcs, whereas
/ 8U16$$0780
08-19-97 19:15:05
in UB(d, D), there exist N 0 d 2 vertices of degree 2d,
d 2 0 d vertices of degree 2d 0 1, and d vertices of degree
2d 0 2.
These networks have been discovered by many authors
and are named after de Bruijn [8]. They are sometimes
also called Good graphs [10].
De Bruijn networks present many attractive features.
In particular, they are among the best-known networks
for a given degree and diameter [see the survey [2] for
more details on this problem known as the (d, D) or
( D, D) graph problem]. They have good vulnerability
properties, being able to tolerate up to d 0 1 faults in the
directed case and 2d 0 3 in the undirected case, while
the diameter can still be left small (see [3]). They are
adequate for various applications as one can embed in
them linear arrays, rings, and complete binary trees. They
can also emulate without loss of time shuffle-exchange or
hypercubes for the class of ascend–descend algorithms.
De Bruijn networks have also many other interesting
properties like easy greedy routing. This greedy algorithm
is a simple D-step routing which consists of unidirectional
shifts or ‘‘bit-erosion’’ of the destination address; namely,
in order to go from X Å x1rrrxD to Y Å y1rrryD , we
apply D left shifts (and also right shifts in the undirected
case), introducing successively the letters y1 , y2 , . . . , yD ,
corresponding to the dipath
x1rrrxD r x2rrrxD y1 r x3rrrxD y1 y2 r
rrrr y1rrryD .
We refer the reader to one of the two recent surveys
concerning de Bruijn networks written by Bermond and
Peyrat [5] and Samatham and Pradhan [14] or to the
recent book of Leighton [11].
In this paper, we analyze the mean eccentricity of these
graphs. The eccentricity of a vertex X is defined [7]
as the distance to the farthest node from this vertex:
e(X ) Å max{d(X, Y ) : Y √ V }. We define the mean
eccentricity of a vertex X, denoted eV ( X ), as the average
distance from X to all the others vertices:
eV (X ) Å
1
N01
∑
d(X, Y ).
(1)
Y √ V0 {X }
The computation of this parameter appears to be nontrivial in the case of the de Bruijn networks. In this paper,
we consider the upper and lower bounds of eV ( X ).
In Section 2, we analyze the directed de Bruijn networks. We provide the tight bounds as well as the extremal vertices which reach these bounds. These bounds are
expressed as the diameter minus some constants.
In Section 3, we analyze the undirected networks. The
computation turns out to be more difficult. We provide
netwas
W: Networks
780
189
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
lower and upper bounds which differ from the diameter
by some small constants. We conjecture that the vertices
of the form arrra have the largest mean eccentricity.
Numerical computations indicate that the conjecture holds
for binary de Bruijn networks with diameters up to 18.
We will show that the asymptotic difference, when the
diameter goes to infinity, between the mean eccentricities
of an arbitrary vertex and that of arrra is smaller than
0.22. We also provide a simple recursive scheme for the
computation of the asymptotic mean eccentricity of the
vertices arrra.
A byproduct of our analysis is that in both directed
and undirected de Bruijn networks most of the vertices
are at distance near from the diameter and that all of the
mean eccentricities (and therefore the average distance)
tend to the diameter when the degree goes to infinity.
Our results also imply that optimal routing algorithms
are in most of the cases not advantageous due to their
overheads. Instead, one can use the simple D-step routing
algorithm as described above.
The following formulas will be extensively used in
this paper:
p
d p/ 1 0 1
.
∑d Å
d01
kÅ0
k
(2)
of a (di)graph G rooted at vertex X a spanning tree of G
with root X such that the (di)path in the tree from X to
any vertex is a shortest (di)path in G. It can be obtained,
e.g., using the ‘‘breadth first’’ search algorithm. Observe
that for any given G and X this tree is not unique. However, the vertices at level l of a shortest path tree of G
rooted at vertex X are exactly all the vertices that are at
distance l from X in G. Therefore, the weights of the
shortest path trees rooted at vertex X are identical. The
mean eccentricity of a vertex is, in fact, the weight of a
shortest path tree rooted at this vertex divided by N 0 1.
Let lk (X ) be the width, i.e., the number of vertices, at
level k in the shortest path trees rooted at vertex X. Then,
D
eV (X ) Å
1
∑ krlk (X ).
N 0 1 kÅ1
(4)
We first look at the minimal mean eccentricity. We
will need the following for the comparison result.
Lemma 2.1. Let n be a positive integer, and m1 , . . . ,
mn , positive real numbers such that
n
p
∑ kd k0 1
kÅ1
(p / 1)d p
d p/ 1 0 1
Å
0
d01
(d 0 1) 2
Å
pd p/ 1 0 (p / 1)d p / 1
.
(d 0 1) 2
1 ° n ° D 0 1,
∑ mk ° N 0 1.
kÅ1
(3)
If for all 1 ° k ° n, lk (X ) ° mk , then
n
eV (X ) ¢ n / 1 0
2. DIRECTED CASE
In the case of a digraph B(d, D), it is well known (see,
e.g., Fiol et al. [9]) that there is a unique shortest dipath
from a given vertex X Å x1rrrxD to a vertex Y
Å y1rrryD . To find the distance d(X, Y ) and the shortest
dipath, one has to find the smallest i such that xi/1rrrxD
Å y1rrryD0i . The distance is then i, and the shortest path
is obtained by doing the left shifts introducing successively yD/10i , . . . , yD . This fact allows one to compute
easily d(X, Y ) and so eV ( X ) for any X. But, unfortunately,
that does not give a closed formula.
In this section, we provide upper and lower bounds of
the mean eccentricities of B(d, D) and show that these
bounds are reached.
Our analysis will need some notions on trees (or, more
precisely, the outtrees). The level of a vertex in a tree is
the distance from the root to the vertex, where by convention, the root is at level 0. The weight of a tree is the sum
of the levels of all vertices. We call a shortest path tree
/ 8U16$$0780
08-19-97 19:15:05
1
( ∑ (n / 1 0 k)mk ).
N 0 1 kÅ1
(5)
Proof. Let mn/1 Å N 0 1 0 ( nkÅ1 mk , and mi Å 0 for
all n / 1 õ i ° D. It then follows that
D
D
kÅ1
kÅ1
N 0 1 Å ∑ lk (X ) Å ∑ mk
and that for all 2 ° i ° D
D
D
i0 1
kÅi
kÅ1
kÅ1
∑ lk (X ) Å ∑ lk (X ) 0 ∑ lk (X )
¢
Thus, according to (4),
netwas
W: Networks
780
D
i0 1
D
kÅ1
kÅ1
kÅi
∑ mk 0 ∑ mk Å ∑ mk .
190
BERMOND, LIU, AND SYSKA
D
eV (X ) Å
1
∑ krlk (X )
N 0 1 kÅ1
Å
1
∑ ∑ lk (X )
N 0 1 iÅ1 kÅi
¢
1
∑ ∑ mk
N 0 1 iÅ1 kÅi
Å
1
∑ kmk
N 0 1 kÅ1
Å
1
( ∑ kmk / (n / 1)(N 0 1 0 ∑ mk ))
N 0 1 kÅ1
kÅ1
D
D
D
D
D
n
n
n
Ån/10
1
( ∑ (n / 1 0 k)mk ).
N 0 1 kÅ1
j
Proposition 2.1. For any d ¢ 2 and D ¢ 2, and for all
X Å x1rrrxD √ B(d, D),
eV (X ) ¢ D 0
d
d
D
/
r
.
2
(d 0 1)
d01 N01
(6)
Moreover, the equality holds if and only if xi x xD for
all i Å 1, . . . , D 0 1.
Proof. The minimal mean eccentricity corresponds to
the shortest path tree with the minimal weight, which,
owing to Lemma 2.1, requires that as many as possible
vertices should be put in the smallest levels. Since B(d,
D) has out-degree d, a vertex has at most d vertices at
distance 1, and so d 2 vertices at distance 2, . . . , and d k
vertices at distance k. Therefore, in the shortest path trees,
there are at most d k vertices at level k, k Å 1, 2, . . . ,
D 0 1. As 1 / d / d 2 /rrr/ d D01 Å (d D 0 1)/(d 0 1)
we have still at least x Å d D 0 [(d D 0 1)/(d 0 1)]
vertices which are at level D. Figure 2 illustrates such a
tree for the case d Å 2.
Therefore, we can apply Lemma 2.1 with n Å D 0 1
and mk Å d k for 1 ° k ° D 0 1:
D0 1
eV (X ) ¢ D 0
Å D0
Å D0
1
( ∑ (D 0 k)d k )
N 0 1 kÅ1
S
D
D
D/ 1
d 0 d Dd
1
d
0d
D
0
/
N01
d 0 1 d 0 1 (d 0 1) 2
D
We now look at the upper bound of the mean eccentricities. We will need the following property of the shortest
path tree with the maximal weight. An example is given
for the case d Å 2 (Fig. 3).
D
D
kÅi
kÅi
∑ lk ° ∑ d k0 1 (d 0 1) ∀i, 1 ° i ° D,
Assume now the vertex X Å x1rrrxD is such that xi
x xD for all i Å 1, . . . , D 0 1. We want to show the
equality in (6). Indeed, for all 1 ° k ° D 0 1, the
08-19-97 19:15:05
vertices at distance k from x1rrrxD are of the form
xk/1rrrxD y1rrryk , where y1rrryk are arbitrary letters
of the alphabet A. For all 1 ° j õ k , the vertices
at distance j from x1rrrxD are of the form
xj /1rrrxD0k/jrrrxDz1rrrzj , where z1rrrzj are arbitrary
letters of the alphabet A. Since xD0k/j x xD , none of the
vertices xk/1rrrxD y1rrryk are at distance j õ k. Thus,
the width of the shortest path tree of X at level k, 1 ° k
° D 0 1, is d k , so that the equality in (6) holds.
Assume now that for some vertex X Å x1rrrxD the
equality in (6) holds. Then, necessarily, the width of its
shortest path tree at level D 0 1 is d D0 1 , so that all the
vertices at level D 0 1 which have the form xD y1rrryD01
should not already be at levels k Å 0, . . . , D 0 2, where
y1rrryD01 are arbitrary letters of the alphabet A. Thus,
for all k Å 0, . . . , D 0 2, we should have xk/1 x xD ,
which completes the proof.
j
Lemma 2.2. An outtree of out-degree d with d D vertices
and D levels is such that
d
d
D
/
r
.
2
(d 0 1)
d01 N01
/ 8U16$$0780
Fig. 2. Shortest path tree with the minimal weight.
where lk is the number of vertices at distance k from the
root.
Proof. Suppose that the lemma is not true and let i 0
D
D
be the largest i ¢ 1 such that ( kÅi
lk ú ( kÅi
d k01 (d 0 1).
netwas
W: Networks
780
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
D
Then, li0 ú d i001 (d 0 1), which, in turn, as the out-degree
is d, implies li001 ú d i002 (d 0 1), which further implies
that li002 ú d i003 (d 0 1), and so on. Therefore,
D
D
D
∑ ∑ lk (X ) ° ∑ ∑ d k0 1 (d 0 1)
iÅ1 kÅi
iÅ1 kÅi
D
Å (d 0 1)
Å (D / 1)d D 0
D
D
which, together with the fact that ( kÅi
l ¢ 1 / ( kÅi
d k01 (d
0 k
0
0 1), imply that
Å Dd D 0
D
kÅ1
kÅ1
∑ lk ¢ i 0 / ∑ d k01 (d 0 1) Å i 0 / d D 0 1 ¢ d D .
eV (X ) ° D 0
1
D
/
.
d01 N01
We now show that
1
D
/
.
eV (X ) ° D 0
d01 N01
(7)
Moreover, the inequality becomes equality if and only if
X Å arrra, where a √ A.
Proof. Note first that
D
N01
/ D.
d01
Therefore,
Proposition 2.2. For any d ¢ 2 and D ¢ 2, and for all
X √ B(d, D),
D
d D/ 1 0 1
d01
dD 0 1
d01
Å D(N 0 1) 0
This contradicts the fact that the tree has d D vertices. (Note
that the root which is at level 0 is not included in the above
summation.)
j
eV (X ) Å
∑ kd k0 1
kÅ1
li ¢ d i01 (d 0 1) / 1, 1 ° i ° i 0 0 1,
D
191
D
1
1
∑ krlk (X ) Å
∑ ∑ lk (X ).
N 0 1 kÅ1
N 0 1 iÅ1 kÅi
It follows from Lemma 2.2 that
eV (X ) Å D 0
1
D
/
d01 N01
if and only if X Å arrra. First, the vertices at distance
k from arrra are of the form a1rrraD , with a1 Årrr
Å aD0k Å a, aD0k/1 Å aV where aV x a and aD0k/2 , . . . ,
aD can be any letter of the alphabet A. None of these
vertices are at distance j õ k. Their number is d k0 1 (d
0 1), so that all the inequalities in the above derivation
of the proof become equalities. Second, by Lemma 2.2,
a necessary condition for eV ( X ) to reach the bound is
that l1 Å d 0 1. Only the the vertices arrra have this
property.
j
The following properties are immediate consequences:
Corollary 2.1. For any d ¢ 2 and D ¢ 2, and for all
X √ B(d, D),
D0
d
d
D
/
r
(d 0 1) 2 d 0 1 N 0 1
1
D
° eV (X ) ° D 0
/
.
d01 N01
(8)
In particular, when d Å 2,
D02/
Fig. 3. Shortest path tree with the maximal weight.
/ 8U16$$0780
08-19-97 19:15:05
netwas
2D
D
° eV (X ) ° D 0 1 /
.
N01
N01
W: Networks
780
(9)
192
BERMOND, LIU, AND SYSKA
Applying R to the vertex X Å x1rrrxD yields vertex
arrrra1 x1rrrxD0r , which corresponds to the path
Corollary 2.2.
lim eV (X ) Å D,
D ¢ 2.
dr`
x1rrrxD r a1 x1rrrxD01 r a2a1 x1rrrxD02 r
1
° lim inf (D 0 eV (X ))
d01
Dr`
rrrr arrrra1 x1rrrxD0r .
° lim sup (D 0 eV (X )) °
Dr`
d
,
(d 0 1) 2
d ¢ 2.
Our results indicate that the upper and the lower
bounds of the mean eccentricities are both close to the
diameter. This is especially true when the degree of the
de Bruijn network is large. In [12], a linear (in time
and in space with respect to the diameter) algorithm was
proposed for the optimal routing of directed de Bruijn
networks. However, even if we use D shifts to route instead of the optimal routing, the global communication
delay of the network should not be affected too much.
The routing scheme in D steps corresponds to a simple
‘‘bit-erosion’’ of the destination address, a very simple
routing function that could be implemented with only a
very few VLSI components on chip.
3. UNDIRECTED CASE
We now consider the mean eccentricities of UB(d, D).
It turns out that the computation of bounds is much more
difficult. This is partially due to the facts that the shortest
paths are, in general, not unique and that the determination of the distances between the vertices is more complicated.
In what follows, we will first study some properties of
the shortest paths in undirected de Bruijn networks. We
then derive the lower and upper bounds, respectively.
3.1. Characterization of the Shortest Paths
Since the neighborhood in UB(d, D) can be defined by
the left- and right-shift operations, a path can be described
by a sequence of corresponding shifts. The length of a
path connecting X to Y is equal to the cardinality of this
sequence of shifts. Formally, let L be the operation consisting of a sequence of l left shifts, introducing a suffix
B Å b1 , . . . , bl with É LÉ Å l, and let R be the operation
consisting in a sequence of r right shifts, introducing a
prefix A Å arrrra1 with É RÉ Å r. Then, applying L to
a vertex X Å x1rrrxD yields vertex xl/1rrrxDb1rrrbl ,
which corresponds to the path
In general, any path of the de Bruijn graph can be denoted
by L1 R1 L2 R2rrrLn Rn with É Li É Å li and É Ri É Å ri ,
meaning that we successively apply L1 , then R1 , then L2 ,
and so on. The length of the path is equal to l1 / r1 / l2
/ r2 /rrr ln / rn . Note that one can have l1 Å 0 or rn
Å 0.
We will use the following results established by Bond
[6, p. 92] and Peyrat [13, annexe 3.2]. For the sake of
completeness, we give a slightly simpler proof. We will
also give a more precise property pertaining to the shortest
paths from vertices arrra (cf. Proposition 3.2 below).
Lemma 3.1. If a path of the form LRL * is a shortest
path, where l ú 0, r ú 0, l * ú 0, then l / l * ° r.
Similarly, if a path of the form RLR * is a shortest path,
where r ú 0, l ú 0, r * ú 0, then r / r * ° l.
Proof. We consider the shortest paths of the form
LRL *. The case of RLR * is analogous. We first prove that
l õ r and l * õ r.
Given a path of the form LRL * from X Å x1rrrxD to Y,
suppose that l ¢ r; then after the application of L to X, we
reach vertex xl/1rrrxDb1rrrbl . The application of R leads
to the vertex arrrra1 xl/1rrrxDb1rrrbl0r . The first shift
of L * leads to the vertex ar01rrra1 xl/1rrrxDb1rrrbl0rb.
But the vertex ar 01rrra1 xl/1rrrxDb1rrrbl0rb could
have been reached by a shorter path L1 R1 with l1 Å l and
r1 Å r 0 1 (L1 introduces the word b1rrrbl0rbrrrand
R1 the word ar 01rrra1 ). Therefore, LRL * is not a shortest
path.
Thus, we have necessarily l õ r, and by symmetry (in
considering the reverse path from Y to X, which is also
a shortest path), l * õ r.
Now, the vertices obtained by LRL * are of the form
ar 0l =rrra1 xl/1rrrxD0 (r 0l ) b1rrrbl = ,
where a1rrrar 0l = and b1rrrbl = are arbitrary letters. These
vertices can also be obtained via the sequence of shifts
R1 L1 R2 with
r1 Å r 0 l, l1 Å r,
x1rrrxD r x2rrrxDb1 r x3rrrxDb1b2 r
rrr r xl/1rrrxDb1rrrbl .
/ 8U16$$0780
08-19-97 19:15:05
r 2 Å r 0 l *.
As LRL * is a shortest path, we have
netwas
W: Networks
780
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
r1 / l1 / r2 Å 3r 0 l 0 l * ¢ l / r / l *,
which implies that l / l * ° r.
193
At level k, 1 ° k ° D 0 1, we have three kinds of
vertices:
j
Proposition 3.1. A shortest path of UB(d, D) is made
of the concatenation of at most three directed paths, i.e.,
the shortest path is of the form LRL * or RLR *, where the
cardinalities of these shift sequences can be zero.
Proof. Suppose that a shortest path from X to Y is
made of more than three directed paths, then a part of
this shortest path is either L1 R1 L2 R2 or R1 L1 R2 L2 , with
l1 ú 0, r1 ú 0, l2 ú 0, and r2 ú 0. Let us assume that it
is the first case. It then follows that L1 R1 L2 R2 is a shortest
path, and so are L1 R1 L2 and R1 L2 R2 . By Lemma 3.1, we
j
get l2 õ r1 and r1 õ l2 , which is a contradiction.
(a) Those obtained with a directed path containing only
left (respectively, right) shifts. Their number is at
most 2Ak , with
Ak Å d k ,
1 ° k ° D 0 1.
(11)
(b) Those obtained with the concatenation of two directed paths corresponding to a sequence of LR (respectively, RL) shifts with l ú 0, r ú 0 and l / r
Å k, where l Å É LÉ and r Å É RÉ.
Consider the vertices obtained with a path LR. They
are of the form
H
Proposition 3.2. A shortest path between a vertex X and
the vertex arrra is of the form LR (with 0 ° r õ l) or
RL (with 0 ° l õ r).
Proof. Without loss of generality, suppose that the
path between arrra and X is of the form LRL *. Suppose
that l ° r, which is, in particular, the case if l * ú 0 by
Lemma 3.1. The vertex reached after the operation LR is
arrrra1arrra, which could have been reached directly
by the path R which is shorter.
j
arrrra1 xl/1rrrxDb1rrr bl0r , if l ¢ r;
arrrra1 xl/1rrrxD0 (r 0l )
if l õ r,
where arrrra2 and b1rrrbl0r are arbitrary letters
and a1 x xl . Indeed, if a1 Å xl , these vertices would
have been reached with a path L1 R1 with l1 Å l 0 1
and r1 Å r 0 1 and so are already at level k 0 2.
Thus, there are at most (d 0 1)d m0 1 vertices reached
by such paths, where m Å max(l, r).
Hence, for fixed k, 2 ° k ° D 0 1, the number of
vertices reached by the concatenation of two directed
paths is at most 2Bk , with
3.2. Lower Bound
We now consider the lower bound of the mean eccentricity for general UB(d, D).
k0 1
Bk Å ∑ (d 0 1)d max ( l , k0l ) 01
Proposition 3.3. For any D ¢ 2 and any X √ UB(d,
D),
9
D 0 3 0 ú D 0 4.2,
8
eV (X ) ¢
lÅ1
k0 1
lÅ k / 2
d Å 2;
8
D 0 1 0 ú D 0 1.9,
9
d Å 3;
25
D010
ú D 0 1.4,
72
d Å 4;
0 (d 0 1)d  k / 2 011 {k mod2Å0 }
Å 2d
0 2d
where  x denotes the smallest integer greater than
or equal to x, and 1 { l } is the indicator function.
Therefore,
Proof. Consider the shortest path tree rooted at X
Å x1rrrxD . As in the case of directed de Bruijn networks,
the more vertices that are at the first levels of the shortest
path tree, the smaller is the mean eccentricity (cf. Lemma
2.1). We will use the fact that the shortest paths are made
of the concatenation of at most three directed paths to
obtain upper bounds of the widths of the first levels in
the shortest path tree.
08-19-97 19:15:05
(12)
 k / 2 01
0 (d 0 1)d  k / 2 011 {k mod2Å0 } ,
2(d / 1)
¢ D 0 0.9, d ¢ 5.
d(d 0 1) 2
/ 8U16$$0780
k0 1
(10)
2
D0
∑ d l0 1 )
Å 2(d 0 1)(
Bk ° 2d k0 1 ,
2 ° k ° D 0 1.
(13)
(c) Those obtained with the concatenation of three directed paths corresponding to a sequence of LRL *
(respectively, RLR * ) shifts. Consider the path LRL *.
We have l ú 0, r ú 0, l * ú 0, and l / r / l * Å k,
where l Å É LÉ, r Å É RÉ and l * Å É L *É. According
netwas
W: Networks
780
194
BERMOND, LIU, AND SYSKA
to Lemma 3.1, l / l * ° r, so that k ¢ 4.
Consider the vertices obtained with a path LRL *.
They are of the form
lk (X ) ° 2Ak / 2Bk1 {k¢2 } / 2Ck1 {k¢4 }
õ 2(d k / 2d k0 1 / d k0 2 ) Å mk ,
(17)
1 ° k ° D 0 1,
ar 0l =rrra2a1 xl/1rrrxD0 (r 0l ) b1b2rrrbl = ,
where ar 0l =rrra2 and b2rrrbl = are arbitrary letters
and a1 x xl , b1 x xD0 (r 0l ) /1 (otherwise, these vertices
are already at a preceding level). Thus, there are at
most (d 0 1) 2 d r 0 2 vertices reached by such paths.
Hence, for fixed k, 4 ° k ° D 0 1, the number
of vertices reached by the concatenation of three directed paths is at most 2Ck , with
where lk (X ) is the width of level k in the shortest path
trees rooted at vertex X.
Let nd be the greatest integer n such that for all
D¢2
n
∑ mk ° N 0 1.
(18)
kÅ1
Note that N Å d D and
Ck Å
k0 2
k0r 0 1
∑ (d 0 1) 2 d r 0 2 .
∑ mk Å
r Å k / 2
lÅ1
kÅ1
∑
n
Hence, it is readily checked that
A simple calculation yields
k0 2
D 0 4, d Å 2;
∑ (k 0 r 0 1)(d 0 1) 2 d r 0 2
Ck Å
2(d / 1) 2 n
(d 0 1).
d(d 0 1)
nd ¢
r Å k / 2
D 0 2, d Å 3, 4;
(19)
k0 2
∑ d r02
Å (k 0 1)(d 0 1) 2
D 0 1, d ¢ 5.
r Å k / 2
(d 0 1) 2
d
0
Å (k 0 1)(d 0 1)(d
1
d
F
S
k
2
0
0
k0 3
k0 2
∑ rd r 0 1
r Å k / 2
0 d  k / 2 02 )
(14)
In fact, we have equality in (19) as soon as D ¢ 7 for
d Å 2, D ¢ 4 for d Å 4, and any D ¢ 2 for other values
of d.
Applying now Lemma 2.1 implies that
(k 0 2)d k0 1 0 (k 0 1)d k0 2
Å d k0 2 0
D
0 1 d  k / 2 /
k
2
k
2
n
eV (X ) ¢ nd / 1 0
G
d  k / 2 01
Å nd / 1 0
d
1
( ∑ (nd / 1 0 k)mk )
N 0 1 kÅ1
S
d nd 0 1
2(d / 1) 2
(nd / 1)
D
d 01
d(d 0 1)
d  k / 2 01
/
S
k
2
0
D
0 1 d  k / 2 02 ,
Å nd / 1 0
where  x  denotes the integer part of x. Hence,
Ck ° d k0 2 .
Therefore,
(15)
eV (X ) ¢ nd / 1 0
(16)
08-19-97 19:15:05
2(d / 1) 2 d nd/ 1
r
.
d(d 0 1) 2 d D
(20)
It is now a simple calculation from (19) and (20) to
obtain relation (10).
j
It follows from relations (11), (13), and (15) that
/ 8U16$$0780
D
2(d / 1) 2 d nd/ 1 0 (nd / 1)d / nd
r
.
dD 0 1
d(d 0 1) 2
For 1 ° k ° D 0 1, let
mk Å 2(d k / 2d k0 1 / d k0 2 ) Å 2(d / 1) 2 d k0 2 .
(nd / 1)d nd
d nd/ 1 0 1
/
d(d 0 1)
d(d 0 1) 2
Observe that for small values of d and D closer lower
netwas
W: Networks
780
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
bounds can be obtained using the exact values of Ak , Bk ,
and Ck [see (11), (12), and (14)] in
mk Å 2Ak / 2Bk1 {k¢2 } / 2Ck1 {k¢4 } .
Note also that for X Å arrra the lower bounds of
Proposition 3.3 can be improved. Indeed, in that case, it
follows from Proposition 3.2 that there exist only two
kinds of vertices: type (a) with Ak Å d k and type (b) with
Bk ° d k0 1 (as l ú r in the paths LR). Hence, we can do
the computation with mk Å 2(d / 1)d k0 1 . This gives
=
2(d / 1) d n d/ 1
eV (arrra) ¢ n *d / 1 0
r
,
(d 0 1) 2 d D
(21)
195
putations for the case of small diameters. In Table I, we
provide the numerical results of the mean eccentricities
in the binary de Bruijn network UB(2, D). In particular,
we present, for diameter D Å 2, 3, . . . , 18, the average
(taken over all vertices) of the mean eccentricities, the
maximal and the minimal weights of the shortest path
trees, as well as the vertices which exhibit these weights.
While the minimal weights are reached by different
vertices, the maximal weights are obtained by the vertices
0rrr0 and 1rrr1 in all our experimentation. This leads
us to the following conjecture:
Conjecture. For any d ¢ 2 and D ¢ 2, the vertices
arrra, where a is a letter of A, have the maximal mean
eccentricity in UB(d, D).
where
D 0 3, d Å 2;
n *d ¢
D 0 2, d Å 3;
(22)
D 0 1, d ¢ 4.
As a simple corollary of Proposition 3.3, we obtain
the asymptotic mean eccentricity when d goes to infinity.
Corollary 3.1. For any D ¢ 2 and any X √ UB(d, D),
lim eV (X ) Å D.
dr`
The above property shows that all the mean eccentricities are close to the diameter when the degree of the de
Bruijn network is large. Therefore, in this case, we can
simply use D shifts to route instead of the sophisticated
optimal routing of the shortest path [12]. The global communication delay would even be decreased due to the
simplicity of the routing algorithm.
This conjecture is numerically verified for the binary
de Bruijn network UB(2, D) with diameters up to 18.
However, we were unable to prove it for the general case.
Unlike the case of de Bruijn digraphs where we got closed
form formulas for the mean eccentricities of some extremal vertices, in the undirected de Bruijn graphs, we were
not even able to obtain a closed formula for the mean
eccentricity of the probably simplest vertices arrra.
Numerical computation (see Table II) indicates that
the widths in the shortest path trees of UB(2, D) rooted
at arrra are quite regular. It is possible to prove that
for any 1 ° k ° D/2 the width at level k of the shortest
path trees of UB(2, D), denoted lk (2, D), can be expressed as
lk (2, D)
2 k / 2 k0 2 / 2 k0 3 /rrr
/ 2 2 p / 2 2 p0 2 Å 2 k / 2 k0 1
0 2 2 p / 2 2 p0 2 ,
Å
3.3. Upper Bound
1
D
/
.
d01 N01
(23)
This bound is not tight. In the remainder of the paper,
we will study upper bounds in more detail.
To obtain some intuition, we start with numerical com-
/ 8U16$$0780
2 /2
k0 2
/2
k0 3
k Å 3p;
/rrr
/ 2 2 p Å 2 k / 2 k0 1 0 2 2 p ,
It is clear that the mean eccentricity of any vertex X in
the undirected de Bruijn network UB(d, D) is smaller
than the mean eccentricity of the same vertex in the directed de Bruijn network B(d, D). Therefore, Proposition
2.2 still holds for undirected de Bruijn network UB(d,
D), i.e., for any d ¢ 2 and D ¢ 2 and for all X √ UB(d,
D),
eV (X ) ° D 0
k
08-19-97 19:15:05
k Å 3p / 1;
2 k / 2 k0 2 / 2 k0 3 /rrr
/ 2 2 p/ 1 Å 2 k / 2 k0 1 0 2 2 p/ 1 ,
k Å 3p / 2.
Unfortunately, it is nontrivial to characterize lk (2, D) for
k ú D/2. These numbers are not so regular as to yield
simple recursive equations. It seems that for any fixed
diameter the widths are unimodal with the maximum at
D 0 1. It also seems that lD/10k (2, D / 1) ° 2lD0k (2,
D) for k Å 0, 1, 2, and lD/10k (2, D / 1) ¢ 2lD0k (2, D)
for k ¢ 3.
In what follows, we will first consider the asymptotic
value of eV (arrra) when D tends to infinity. More precisely, we will prove that the limit of
netwas
W: Networks
780
196
BERMOND, LIU, AND SYSKA
TABLE I. Mean eccentricities of UB(2, D)
D
Maximum eV (X)
vertex arrra
Average eV (X)
Minimum eV (X)
Vertices
2
1.1667
1.3333
1.0000
01
10
3
1.6429
2.0000
1.4286
4
2.1417
2.6667
1.8667
001, 011
110, 100
0011
1100
5
2.7540
3.4516
2.5484
00011, 00111
11100, 11000
6
3.4534
4.2698
3.2063
001011
110100
7
4.2148
5.1654
3.9685
0001011, 0010111
1110100, 1101000
8
5.0280
6.0706
4.08078
00010111
11101000
9
5.8844
7.0098
5.6888
001111010, 010111100
110000101, 101000011
10
6.7737
7.9589
6.5689
0010111100, 0011110100
1101000011, 1100001011
11
7.6886
8.9253
7.4934
00101111100, 00111110100
11010000011, 11000001011
12
8.6232
9.8960
8.4308
001101011100, 001110101100
110010100011, 110001010011
13
9.5733
10.8764
9.3770
0011010111100, 0011110101100
1100101000011, 1100001010011
14
10.5351
11.8594
10.3377
00101111110100
11010000001011
15
11.5063
12.8473
11.3107
001011111101100, 001101111110100
110100000010011, 110010000001011
16
12.4844
13.8372
12.2936
0010111111101100, 0011011111110100
1101000000010011, 1100100000001011
17
13.4678
14.8297
13.2790
00101101111110100, 00101111110110100
11010010000001011, 11010000001001011
18
14.4554
15.8233
14.2669
001011111010100011, 001110101000001011
110100000101011100, 110001010111110100
def
D(X ) Å D 0 eV (X )
exists when X Å arrra, and we will provide a numerical
recursive scheme for its computation. We will also establish an upper bound [better than (23)] for arbitrary X.
As a consequence of these two results, we show that for
any fixed degree (2d) the asymptotic difference between
eV ( X ) and eV (arrra) when the diameter goes to infinity
is smaller than 0.22.
/ 8U16$$0780
08-19-97 19:15:05
Let X √ UB(d, D) and 0 ° h ° D. Define Eh (X ) to
be the set of vertices that are at distance no greater than
D 0 h from X:
Eh (X ) Å {Y É d(X, Y ) ° D 0 h}.
By definition, E0 (X ) contains all the vertices of UB(d,
D) and ED (X ) is a singleton. Let eh (X ) Å É Eh (X )É/N
be the proportion of vertices that are at distance no
netwas
W: Networks
780
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
197
TABLE II. Widths in the shortest path trees of UB(2, D) rooted at arrra
lk(2, D)
k
UB(2, 18)
UB(2, 19)
UB(2, 20)
UB(2, 21)
UB(2, 22)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
4
9
20
40
84
176
352
720
1469
2926
5865
11648
22444
41559
68474
79558
26793
2
4
9
20
40
84
176
352
720
1471
2936
5911
11846
23268
45081
83382
136638
158954
53393
2
4
9
20
40
84
176
352
720
1472
2941
5934
11945
23680
46764
90549
166578
273450
317504
106351
2
4
9
20
40
84
176
352
720
1472
2943
5944
11991
23878
47588
93976
180959
333665
547235
633746
212347
2
4
9
20
40
84
176
352
720
1472
2944
5949
12014
23977
48000
95660
187888
362679
668397
1093347
1266714
423855
greater than D 0 h from X. Then, e0 (X ) Å 1 and eD (X )
Å 1/N.
Lemma 3.2. For any d ¢ 2, D ¢ 2, and any X √ UB(d,
D),
Ph ,k Å {X É X Å UAV, A Å arrra,
D0 1
D01
N
eV (X ) Å D /
0
∑ eh (X ).
N 0 1 N 0 1 hÅ1
We will first consider the vertices arrra. For simplicity of notation, we arbitrarily fix a letter a √ A and denote
Eh å Eh (arrra), and eh å eh (arrra).
Let
(24)
Proof. For any 0 ° h ° D 0 1, the set of vertices
that are exactly at distance D 0 h from X is Eh (X ) 0
Eh/1 (X ). Since Eh/1 (X ) ⊆ Eh (X ), we obtain that the
number of vertices that are at distance D 0 h from X is
Neh (X ) 0 Neh/1 (X ). Therefore,
É AÉ Å k / h, ÉUÉ Å k},
Sh ,k Å {X É X Å UAV, A Å arrra,
É AÉ Å k / h, ÉV É Å k}.
Lemma 3.3. For any 0 ° h ° D,
Eh Å
D0 1
1
eV (X ) Å
∑ (D 0 h)N(eh (X ) 0 eh/1 (X ))
N 0 1 hÅ0
N
N01
S
0 e2 (X ) 0rrr0 eD (X ))
D0 1
D0
1
0 ∑ eh (X )
N
hÅ1
D
D0 1
Å D/
D01
N
0
∑ eh (X ).
N 0 1 N 0 1 hÅ1
/ 8U16$$0780
08-19-97 19:15:05
Eh ,k ,
where Eh ,k Å Ph ,k < Sh ,k .
N
Å
(De0 (X ) 0 e1 (X )
N01
Å
<
0°k°  ( D0h ) / 2 
j
Proof. Let X be a vertex in Ph ,k , where 0 ° k ° (D
0 h)/2. Then, X Å UAV, with A Å arrra, É AÉ Å k
/ h and ÉUÉ Å k. Thus, X can be reached from arrra
by first D 0 (k / h) left shifts applied to arrra introducing the suffix V V *, where V * is an arbitrary word with
length k, and then k right shifts introducing prefix U. The
length of the corresponding path is D 0 (k / h) / k
Å D 0 h. Hence, X √ Eh . Similarly, we can show that
if X √ Sh ,k , then X √ Eh . Therefore,
netwas
W: Networks
780
198
BERMOND, LIU, AND SYSKA
Eh fl
<
0°k°  ( D0h ) / 2 
Eh ,k .
(25)
 ( D0h ) / 2 
eh Å
 ( D0h ) / 2 
∑
∑
eh ,k °
kÅ0
Suppose now that X is a vertex in Eh . Then, by Proposition 3.2, there exists a path (not necessarily a shortest
one) between arrra and X of the type LR or RL with r
/ l ° D 0 h, where r Å É RÉ, l Å É LÉ. Without loss of
generality, suppose that this path is of the form LR. Thus,
X can be written as X Å UAV, with U Å arrrra1 ,
A Å arrra, V Å b1rrrbl0r , where l ¢ r (cf. Proposition
3.2, where the equality holds when l Å r Å 0). It then
follows that
<
Eh ,k .
D0 1
p
q
hÅ1
hÅ1 kÅ0
p
hÅ1
kÅq/1
p
 ( D0h ) / 2 
hÅ1
kÅq/1
q
∑ ∑ eh ,k / ∑
°
j Å0
.
N
hÅ1 kÅ0
p
Å (∑
 ( D0h ) / 2 
∑ eh ,k ) / 2
F
G
On the other hand, it is easy to see that
D0 1
∑ eh ¢ ∑
D0 1  ( D0h ) / 2 
∑
hÅ1
hÅ1
kÅ0
p
q
eh ,k ¢ ∑ ∑ eh ,k;
hÅ1 kÅ0
j
`
∑
eh ,k .
(28)
`
lim D(arrra) Å ∑ ∑ eh ,k °
hÅ1 kÅ0
2d
. (32)
(d 0 1) 2
Proof. Let p Å q Å  D/3  in (29), and let D go to
1
` readily implies that the limit of ( D0
hÅ1 eh exists when
D r ` and that
`
`
lim ∑ eh Å ∑ ∑ eh ,k .
Lemma 3.4. For any fixed d ¢ 2 and any p, q °  D/
3,
Dr` hÅ1
hÅ1 kÅ0
Applying Lemma 3.2 entails that
D0 1
∑ ∑ eh ,k ° ∑ eh
`
hÅ1
q
∑ eh ,k ) / 2
hÅ1 kÅ0
S
d 0q / d 10 p
(d 0 1) 2
D
(29)
Dr`
hÅ1 kÅ0
.
Using again inequality (30) yields
`
`
`
`
∑ ∑ eh ,k ° 2 ∑ ∑ d 0h0k Å
É Ph ,kÉ
Å 2d 0h0k ,
N
hÅ1 kÅ0
(30)
0 ° k, h ° D,
hÅ1 kÅ0
The proof is thus completed.
2d
.
(d 0 1) 2
j
2k / h ° D,
A recursive scheme will be provided after for the computation of limDr` D(arrra). The convergence of the
which implies that
/ 8U16$$0780
`
lim D(arrra) Å ∑ ∑ eh ,k .
Proof. Note first that
eh ,k ° 2
2d 10 h
hÅp/1 d 0 1
d 0q / d 10 p
.
(d 0 1) 2
D0 1
p
`
hÅ1 kÅq/1
q
kÅ0
° (∑
2d 10 h
hÅp/1 d 0 1
`
hÅ1 kÅ0
(27)
It then follows that
hÅ1 kÅ0
D0 1
2d 0h0k / ∑
∑ ∑ eh ,k / ∑ ∑ 2d 0h0k / ∑
°
Dr`
q
hÅp/1
Proposition 3.4. For any fixed d ¢ 2,
k0 1
p
eh ,k / ∑ eh
∑
`
q
D0 1
∑
hence, the result.
É Eh ,k 0 < Eh ,jÉ
eh Å
 ( D0h ) / 2 
p
∑ eh Å ∑ ∑ eh ,k / ∑
p
For h ¢ 1 and k ¢ 0, let
(31)
Thus, for any p, q °  D/3  ,
Combining relations (25) and (26) readily implies the
assertion of the lemma.
j
eh ,k Å
2d 10 h
Å
.
d01
0h0k
kÅ0
hÅ1 kÅ0
(26)
∑ 2d
°
Let A * be the prefix of A with size r / h. Then, X can
be written as X Å UA *V * so that X √ Ph ,r . Since ÉV *É
Å D 0 r 0 (r / h) ¢ ÉV É ¢ 0, we get that r ° (D
0 h)/2. Therefore,
0°k°  ( D0h ) / 2 
kÅ0
`
É AÉ Å D 0 r 0 (l 0 r) ¢ D 0 (D 0 h) / r Å r / h.
Eh ⊆
2d 0h0k
08-19-97 19:15:05
netwas
W: Networks
780
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
series ( `hÅ1 ( `kÅ0 eh ,k is very fast. Good precisions are
obtained with computations stopped at quite small indices
h, k. Indeed, Lemma 3.4 and Proposition 3.4 imply that
for any n ¢ 1
n
n
∑ ∑ eh ,k ° lim D(arrra)
hÅ1 kÅ0
x1rrrxk/1 Ak/1/hV, where x1 , . . . , xk/1 are arbitrary letters, Ai is a word of length i with letter a, and V is
an arbitrary word. The words in Ph ,k are of the form
x1rrrxk Ak/hV *. Therefore, the words in Ph ,k/1 0 Ph ,k are
of the form x1rrrxkaV Ak/1/hV, where aV is an arbitrary
letter in A 0 {a}. Thus, hh ,k Å d 0 ( k/h/ 1 ) (d 0 1)/d. j
Dr`
n
n
2(d / 1) 0n
õ ( ∑ ∑ eh ,k ) /
d .
(d 0 1) 2
hÅ1 kÅ0
(33)
Lemma 3.6. For all h ¢ 1 and k ¢ 0 such that 2k / 2
/ h ° D,
gh ,k/1 Å gh ,k / dh ,k .
In view of the above results, we see that the computation of limit of D(arrra) can be carried out on the values
of eh ,k for small h and k. We derive below a recursive
computational scheme for eh ,k . This will be based on
counting the proportion of words (of length D over the
alphabet A ) fulfilling some conditions. This approach and
some of the ideas can be found in [1].
Let C be a condition on the words of length D over
A. Let CV be the opposite condition of C. Two conditions,
C1 and C2 , are said to be independent if they concern
disjoint subgroups of letters of the word. Let p(C) denote
the proportion of words satisfying a condition C.
We recall the following basic computation rules which
will be used in the remainder of the paper:
• The proportion of words satisfying CV is 1 0 p(C), i.e.,
p(CV ) Å 1 0 p(C).
• If C1 and C2 are independent, then the proportion of
words satisfying both C1 and C2 is p(C1 )p(C2 ), i.e.,
p(C1 , C2 ) Å p(C1 )p(C2 ).
For h ¢ 1 and k ¢ 0, let
hh ,k Å
j Å0
N
j Å0
k
j Å0
N
k
j Å0
j Å0
j Å0
k
É Sh ,k/1 0 < Sh ,jÉ
å
j Å0
N
.
For k Å 01, hh ,01 Å dh ,01 Å É Ph ,0É/N Å d 0h . For k
° 01, gh ,k Å 0. It is also clear that gh ,0 Å d 0h .
Lemma 3.5. For all h ¢ 1 and k ¢ 0 such that 2k / 2
/ h ° D,
hh ,k Å (d 0 1)d 0 ( k/h/ 2 ) .
dh ,k Å (1 0 gh ,  ( k0h ) / 2  ) hh ,k ,
k ¢ 01;
(36)
Å (1 0 gh ,  ( k0h ) / 2  )(d 0 1)d 0 ( k/h/ 2 ) ,
k ¢ 0. (37)
Proof. As seen in the proof of Lemma 3.5, the words
in Ph ,k/1 0 Ph ,k are of the form x1rrrxkaV Ak/1/hV, where
aV is an arbitrary letter in A 0 {a}. It then follows that
these words will not appear in Ph ,j for all j such that j
õ k and 2 j / h ú k. Therefore,
k
Ph ,k/1 0 Ph ,k Å Ph ,k/1 0
<
j Å  ( k0h ) / 2  /1
k
 ( k0h ) / 2 
j Å0
j Å0
Ph ,j ,
(38)
Ph ,j .
(39)
(34)
08-19-97 19:15:05
<
It is easily verified that the conditions for words to be in
( k0h ) / 2 
Ph ,j are independent (the
Ph ,k/1 0 Ph ,k and in < j Å0
former is on xk/1rrrx2k/2/h of word X Å x1rrrxD ,
whereas the latter is on x1rrrxk ). Therefore, relation (39)
implies relation (36) according to the basic computation
rule. Relation (37) follows from those of (34) and (36).
j
Proposition 3.5. For all h ¢ 1 and k ¢ 0 such that 2k
/ h ° D/2,
eh ,k Å (2 0 gh ,k01 0 gh ,k ) dh ,k01 ,
k ¢ 0;
(40)
eh ,k Å (2 0 gh ,k01 0 gh ,k )(1 0 gh ,  ( k0h01 ) / 2  )
1 (d 0 1)d 0 ( k/h/ 1 ) ,
Proof. The words in Ph ,k/1 are of the form
/ 8U16$$0780
j
Lemma 3.7. For all h ¢ 1 and k ¢ 01 such that 2k
/ 2 / h ° D,
Ph ,k/1 0 < Ph ,j Å Ph ,k/1 0 Ph ,k 0
,
N
É Ph ,k/1 0 < Ph ,jÉ
dh ,k Å
k
which, in turn, implies that
É < Sh ,jÉ
å
k/ 1
É < Ph ,jÉ Å É < Ph ,jÉ / É Ph ,k/1 0 < Ph ,jÉ.
k
É < Ph ,jÉ
(35)
Proof. The assertion comes from the fact that
É Ph ,k/1 0 Ph ,kÉ
É Sh ,k/1 0 Sh ,kÉ
å
,
N
N
k
gh ,k Å
199
netwas
W: Networks
780
k ¢ 1.
(41)
200
BERMOND, LIU, AND SYSKA
TABLE III. D(arrra) in UB(2, D)
kÅ0
eh,k
kÅ1
kÅ2
kÅ3
kÅ4
kÅ5
(5kÅ1 eh,k
hÅ1
0.75000
0.10938
0.02246
0.01050
0.00381
0.00188
0.89802
hÅ2
0.43750
0.08984
0.04110
0.01524
0.00752
0.00342
0.59552
hÅ3
0.23438
0.05371
0.02612
0.01288
0.00560
0.00279
0.33547
hÅ4
0.12109
0.029053
0.01434
0.00713
0.00355
0.00166
0.17683
hÅ5
0.06152
0.01508
0.00750
0.00373
0.00186
0.00093
0.09062
hÅ6
0.03101
0.00768
0.00383
0.00191
0.00095
0.00048
0.04585
(
1.63550
0.30473
0.11624
0.05140
0.02330
0.01116
2.14232
1.66667
0.31250
0.11914
0.05235
0.02388
0.01146
2.18600
6
kÅ1
eh,k
êk
Under the assumption that 2k / h ° D/2, the conditions
1
k0 1
for words to be in Ph ,k 0 < k0
j Å0 Ph ,j and in < j Å0 Sh ,j are
independent (the former is on the left-half part of the
word, whereas the latter is on the right-half part of the
word). Therefore,
Proof.
k0 1
É Ph ,k < Sh ,k 0 < Eh ,jÉ
j Å0
eh ,k Å
N
k0 1
k0 1
É Ph ,k 0 < Eh ,jÉ
Å
j Å0
j Å0
N
k0 1
k0 1
j Å0
j Å0
j Å0
Similarly,
N
k0 1
k
É Sh ,k 0 < Sh ,j 0 < Ph ,jÉ
j Å0
j Å0
N
N
j Å0
.
h
eh
(hiÅ1 ei
1
2
3
4
5
6
7
8
9
10
11
12
13
:
30
:
60
0.8997111342
0.5988445366
0.3381424180
0.1784738644
0.0915215694
0.0463216922
0.0232996659
0.0116843542
0.0058507839
0.0029275407
0.0014643071
0.0007322877
0.0003661774
0.899711134
1.498555671
1.836698089
2.015171953
2.106693523
2.153015215
2.176314881
2.187999235
2.193850019
2.196777560
2.198241867
2.198974155
2.199340332
:
2.199706529
:
2.199706532
017
0.260 1 10
j Å0
Å dh ,k01 (1 0 gh ,k ).
Hence, relation (40) holds. Relation (41) follows from
j
(36) and (40).
TABLE IV. D(arrra) in UB(2, D)
0.0000000027
k
k0 1
É Sh ,k 0 < Sh ,j 0 < Ph ,jÉ
/
Å dh ,k01 (1 0 gh ,k01 ).
N
É Ph ,k 0 < Ph ,j 0 < Sh ,jÉ
Å
k0 1
É Ph ,k 0 < Ph ,j 0 < Sh ,jÉ
j Å0
/
N
k0 1
É Sh ,k 0 Ph ,k 0 < Eh ,jÉ
Lemmas 3.5, 3.6, and 3.7 and Proposition 3.5 enable
us to compute recursively eh ,k . In Table III, we indicate
the values of eh ,k in the case d Å 2 for 1 ° h ° 6 and 0
° k ° 5. This gives already a lower bound of 2.14 for
D(arrra). In fact, we have computed all the eh ,k for d
Å 2, h ° 30 and k ° 85. Results for eh are given in Table
IV. The values are given with 10 digits but we have
computed them with infinity precision. Recall that by
having the values of eh we obtain the number of vertices
at distance exactly D 0 h. For instance, we have 1 0 e1
á 10.03% of vertices at distance D from (arrra) in the
case d Å 2. This table shows that most of the vertices
are at distance D 0 h with h small.
Finally, let us note that one can get closed form formulas for êk where
`
eP k Å ∑ eh ,k .
hÅ1
/ 8U16$$0780
08-19-97 19:15:05
netwas
W: Networks
780
(42)
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
We give below this formulas for 0 ° k ° 6:
eP 0 Å
2d / 1
d2 0 1
eP 1 Å
2d 2 0 2d / 1
d4
6
eP 2 Å
5
We now turn back to upper bounds for arbitrary vertex
X. Let us consider an arbitrarily fixed vertex X Å
x1rrrxD . Let
Ph ,k (X ) Å {Z ÉZ Å UXh ,kV, Xh ,k
Å xD0h0k/1 xD0h0k/2rrrxD , ÉUÉ Å k},
4
3
2
2d 0 4d / 4d / d 0 3d / 1
d9
Sh ,k (X ) Å {Z ÉZ Å UX
eP 4 Å d 022 (2d 17 0 4d 16 / 2d 15 / 4d 14 0 4d 13 / d 12
0 2d
0d
9
7
6
/ 7d 0 6d 0 d / 5d
Lemma 3.8. For any 0 ° h ° D,
eP 5 Å d 028 (2d 22 0 4d 21 / 2d 20 / 4d 19 0 6d 18 / 4d 17
/ d 16 0 6d 15 / d 14 / 8d 13 0 2d 12 0 10d 11
/ 11d 10 0 2d 9 0 3d 8 0 d 6 / 2d 5 0 d 2 / 2d 0 1)
eP 6 Å d
( 01 / 2d / 8d
4
5
10
2
0 d / 2d
6
0 2d / 6d 0 3d / 5d
18
24
s
h ,k
5
Eh (X ) fl
0 4d 4 / 2d 3 0 d 2 / 2d 0 1)
034
V, X
Eh ,k (X ) Å Ph ,k (X ) < Sh ,k (X ).
0 3d 6 / 2d 5 0 d 4 0 2d 3 / d 2 / 2d 0 1)
10
s
h ,k
Å x1 x2rrrxh/k , ÉV É Å k},
eP 3 Å d 016 (2d 12 0 4d 11 / 4d 10 0 2d 9 / d 8 / 2d 7
11
201
/ 3d
<
0°k°  ( D0h ) / 2 
Eh ,k (X ).
Proof. The proof is analogous to the first part of the
proof of Lemma 3.3 and is thus omitted.
j
Proposition 3.7. For any fixed d ¢ 2 and D ¢ 2,
20
D0 1
∑ eh (X ) ú u(d) 0 22d 0D / 4 ,
8
/ d 0 2d 7 0 3d 12
(44)
hÅ1
0 2d 9 0 2d 16 0 8d 11 0 2d 15 0 2d 14 / 8d 13
0 4d 19 / 2d 17 0 4d 21 / 2d 25 0 4d 26 / 2d 27 ).
In Table III, we also provided exact values of êk for d
Å 2. Again, we note that using only ( 6kÅ0 êk gives a very
good estimation of D(arrra).
Indeed, it follows from Lemma 3.4 and Proposition
3.4 that for any q ¢ 0
where
u(d) Å
2d / 1
2d 0 1
1
/ 3
0
d2 0 1
d 0 (d 0 1) 2 d 3 / 1
2d 6 0 d 5 / 2d 4 0 d 3 / d 2 / d 0 1
Å 7
.
d 0 2d 6 / 3d 5 0 2d 4 0 d 3 / 3d 2 0 3d / 1
(45)
(43)
Proof. The proof is technical and involved so that we
omit it here. The interested reader can find the detailed
proof in the technical report [4].
j
The following proposition gives values of limD r`
D(arrra) for d ° 7. There, again, we give only truncated values with five decimals. The values given in parentheses are approximation using ( 6kÅ0 êk .
As a corollary of Lemma 3.2 and Proposition 3.7, we
obtain
q
q
∑ eP k ° lim D(arrra) õ ( ∑ eP k ) /
kÅ0
Dr`
kÅ0
2d 0q
.
(d 0 1) 2
Proposition 3.6. In the de Bruijn network UB(d, D),
2.19970 d Å 2 (2.19151)
1.09605 d Å 3 (1.09556)
lim D(arrra) Å
Dr`
0.72359 d Å 4
(0.72353)
0.53752 d Å 5
(0.53751)
0.42652 d Å 6 (0.42652)
Corollary 3.2. For any d ¢ 2, D ¢ 2, and any X
√ UB(d, D),
eV (X ) õ D 0 u(d) / 22d 0D / 4
1
/
r(D 0 1 0 u(d) / 22d 0D / 4 ),
N01
where u( d) is defined in (45).
0.35304 d Å 7 (0.35303).
/ 8U16$$0780
08-19-97 19:15:05
Proof. It follows from (24) and (44) that
netwas
W: Networks
780
(46)
202
BERMOND, LIU, AND SYSKA
D0 1
eV (X ) Å D 0 ∑ eh (X )
hÅ1
D0 1
/
1
r(D 0 1 0 ∑ eh (X ))
N01
hÅ1
õ D 0 u(d) / 22d 0D / 4
1
r(D 0 1 0 u(d) / 22d 0D / 4 ).
N01
/
j
As a consequence of Proposition 3.4 and the above
corollary, we obtain
Proposition 3.8. For any fixed d ¢ 2,
`
`
lim sup (eV (X ) 0 eV (arrra)) õ ( ∑ ∑ eh ,k ) 0 u(d),
Dr`
hÅ1 kÅ0
where u( d) is defined in (45).
Proof. It follows from Proposition 3.4 that
lim sup (eV (X ) 0 eV (arrra))
We thank the anonymous referees for their helpful remarks.
M. S. was supported by INRIA while visiting the Simon Fraser
University, BC, Canada.
Dr`
Å lim D(arrra) 0 lim inf D(X )
Dr`
`
¢ (∑
bounds as well as the extremal vertices which reach these
bounds. For the undirected de Bruijn network, we have
provided lower and upper bounds which differ from the
diameter by some small constants. We conjecture that
the vertices of the form arrra have the largest mean
eccentricity. This conjecture has been verified by numerical computations for binary de Bruijn networks with diameters up to 18. We have shown that the asymptotic
difference, when the diameter goes to infinity, between
the mean eccentricities of an arbitrary vertex and that of
arrra is a small constant tending to zero with the degree.
We have also provided a simple recursive scheme for the
computation of the asymptotic mean eccentricity of the
vertices arrra.
We have proved that in both directed and undirected
de Bruijn networks all the mean eccentricities tend to the
diameter when the degree goes to infinity. This implies
that when the degree is large, the simple routing algorithm
which consists of doing left shifts all the time or right
shifts all the time is more efficient than are optimal routing
algorithms. In general, the gain of applying optimal routing algorithms is quite limited, even without considering
their overheads.
Dr`
`
∑ eh ,k ) 0 u(d),
hÅ1 kÅ0
REFERENCES
where the inequality comes from (46).
j
[1]
Numerical results for small d are given below:
[2]
Proposition 3.9.
0.2155 d Å 2
[3]
0.0393 d Å 3
lim sup (eV (X ) 0 eV (arrra)) õ
Dr`
0.0117 d Å 4
[4]
0.0045 d Å 5
0.0021 d Å 6
0.0011 d Å 7.
[5]
4. CONCLUSIONS
[6]
In this paper, we have provided upper and lower bounds
of the mean eccentricities of the de Bruijn networks. For
the directed de Bruijn network, we have presented tight
[7]
/ 8U16$$0780
08-19-97 19:15:05
netwas
J.-C. Bermond, J. Bond, W. Fernandez de la Vega, S.
Rudich, and M. Santha, The radius of graphs on alphabets. Graph Combin. (1988), preprint.
J.-C. Bermond, C. Delorme, and J.-J. Quisquater, Strategies for interconnection networks: Some methods from
graph theory. JPDC 3 (1986) 433–449.
J.-C. Bermond, N. Homobono, and C. Peyrat, Large
fault-tolerant interconnection networks. Graph Combin.
5 (1989) 107–123.
J.-C. Bermond, Z. Liu, and M. Syska, Mean eccentricities of de Bruijn networks. Rapport de recherche INRIA,
No. 2114, 1993. Research Report of I3S, Université de
Nice Sophia Antipolis, No. 94-02 (1994).
J.-C. Bermond and C. Peyrat, De Bruijn and Kautz networks: A competitor for the hypercube? Hypercube and
Distributed Computers (J. P. Verjus and F. André, Eds.
North-Holland (1989) 279–294.
I. Bond, Constructions de grands réseaux d’interconnexion. PhD Thesis, Université de Paris-Sud, Centre d’Orsay (1984).
F. Buckley and F. Harary, Distance in Graphs. AddisonWesley, Redwood City, CA (1990).
W: Networks
780
MEAN ECCENTRICITIES OF DE BRUIJN NETWORKS
[8]
N. G. de Bruijn, A combinatorial problem. Koninklijke
Nederlands Akademie van Wetenschappen Proceedings
49-2 (1946) 758–764.
[9] M. A. Fiol, J. L. A. Yebra, and I. Alegre de Miquel,
Line digraph iterations and the (d, k) digraph problem.
IEEE Trans. Comput. C-33(5) (1984) 400–403.
[10] S. W. Golomb, Shift Register Sequences. Holden-Day,
San Francisco, CA (1967).
[11] F. T. Leighton, Introduction to Parallel Algorithms and
Architectures: Arrays, Trees, Hypercubes. Morgan
Kaufmann, San Mateo, CA (1992).
/ 8U16$$0780
08-19-97 19:15:05
[12]
203
Z. Liu, Optimal routing in the De Bruijn networks. Proceedings of the Tenth International Conference on Distributed Computing Systems, Paris, France (May 1990)
537–544.
[13] C. Peyrat, Vulnérabilité dans les grand réseaux d’interconnexion. PhD thesis, Université de Paris-Sud, Centre
d’Orsay (1984).
[14] M. R. Samatham and D. K. Pradhan, The de Bruijn
multiprocessor network: A versatile parallel processing
and sorting network for VLSI. IEEE Trans. Comput.
38(4) (1989) 567–581.
netwas
W: Networks
780
Документ
Категория
Без категории
Просмотров
3
Размер файла
192 Кб
Теги
269
1/--страниц
Пожаловаться на содержимое документа