Layer structure of De Bruijn and Kautz digraphs: an application to deflection routing
Abstract
In the main part of this paper we present polynomial expressions for the cardinalities of some sets of interest of the nice distance-layer structure of the well-known De Bruijn and Kautz digraphs. More precisely, given a vertex $v$, let $S_{i}^\star(v)$ be the set of vertices at distance $i$ from $v$. We show that $|S_{i}^\star(v)|=d^i-a_{i-1}d^{i-1}-\cdots -a_{1} d-a_{0}$, where $d$ is the degree of the digraph and the coefficients $a_{k}\in\{0,1\}$ are explicitly calculated. Analogously, let $w$ be a vertex adjacent from $v$ such that $S_{i}^\star(v)\cap S_j^{\ast}(w)\neq \emptyset$ for some $j$. We prove that $\big |S_{i}^\star(v) \cap S_j^{\ast}(w) \big |=d^i-b_{i-1}d^{i-1}-\ldots -b_{1} d-b_{0},$ where the coefficients $b_{t}\in\{0,1\}$ are determined from the coefficients $a_k$ of the polynomial expression of $|S_{i}^\star(v)|$. An application to deflection routing in De Bruijn and Kautz networks serves as motivation for our study. It is worth-mentioning that our analysis can be extended to other families of digraphs on alphabet or to general iterated line digraphs.
Full text
UPCommons
Po al del coneixemen obe de la UPC
h p://upcommons.upc.edu/e-p in s
Aques a és una còpia de la e sió
au ho ’s inal d a
d'un a icle
publica a la e is a [
Elec onic no es in disc e e ma hema ics
].
URL d'aques documen a UPCommons E-p in s:
h p://hdl.handle.ne /2117/103040
A icle publica /
Published pape
:
Fàb ega, J., Ma í-Fa é, J., Muñoz, X. Laye s uc u e o De B uijn
and Kau z dig aphs: an applica ion o de lec ion ou ing. "Elec onic
no es in disc e e ma hema ics", 17 Oc ub e 2016, ol. 54, p. 157-
162. Doi: 10.1016/j.endm.2016.09.028
Laye s uc u e o De B uijn and Kau z
dig aphs. An applica ion o de lec ion ou ing
J. F`ab ega 1,2J. Ma ´ı-Fa ´e 1,3X. Mu˜noz 1,4
Depa amen de Ma em`a iques
Uni e si a Poli `ecnica de Ca alunya
Ba celona, Spain
Abs ac
In he main pa o his pape we p esen polynomial exp essions o he ca dinali ies
o some se s o in e es o he nice dis ance-laye s uc u e o he well-known De
B uijn and Kau z dig aphs. Mo e p ecisely, gi en a e ex , le S⋆
i( ) be he se o
e ices a dis ance i om . We show ha |S⋆
i( )|=di−ai−1di−1−···−a1d−a0,
whe e dis he deg ee o he dig aph and he coe icien s ak∈ {0,1}a e explici ly
calcula ed. Analogously, le wbe a e ex adjacen om such ha S⋆
i( )∩S∗
j(w)6=
∅ o some j. We p o e ha |S⋆
i( )∩S∗
j(w)|=di−bi−1di−1−...−b1d−b0,whe e
he coe icien s b ∈ {0,1}a e de e mined om he coe icien s ako he polynomial
exp ession o |S⋆
i( )|. An applica ion o de lec ion ou ing in De B uijn and Kau z
ne wo ks se es as mo i a ion o ou s udy. I is wo h-men ioning ha ou analysis
can be ex ended o o he amilies o dig aphs on alphabe o o gene al i e a ed line
dig aphs.
Keywo ds: De B uijn and Kau z dig aphs, Gene al i e a ed line dig aphs,
De lec ion ou ing.
© <2016>. This manusc ip e sion is made a ailable unde he CC-BY-NC-
ND 4.0 license h p://c ea i ecommons.o g/licenses/by-nc-nd/4.0/
1 Mo i a ion
De lec ion ou ing [1] is a ou ing scheme o bu e less ne wo ks based on he
idea ha i a packe canno be sen h ough a ce ain link due o conges ion,
i is de lec ed h ough any o he a ailable link (ins ead o being bu e ed in
he node queue) and will be e ou ed o des ina ion om he node a which
he packe a i es. The e iciency o his p o ocol depends on he decision
c i e ia used o de lec packe s when he e exis s a collision as well as on he
ne wo k opology. This kind o ou ing is nowadays in e es ing in he con ex
o op ical ne wo ks [7,8] because i is no possible o bu e da a wi hou op ical
o elec ical con e sion.
In [5] an analy ical model o e alua ing he pe o mance o de lec ion
ou ing schemes unde di e en de lec ion c i e ia based on Ma ko chains is
p oposed. A Ma ko chain is de ined wi h s a es 0,1,...,D,co esponding o
he possible dis ances ha a packe may be o i s des ina ion, whe e Ds ands
o he diame e o he ne wo k. The ansi ion p obabili ies in he Ma ko
chain depend on he de lec ion c i e ia as well as on he ne wo k opology.
I he ne wo k opologies unde conside a ion co espond o dig aphs on
alphabe [4] o , mo e gene ally, o some amilies o i e a ed line dig aphs [6],
a ca e ul s udy o he e ex laye s uc u e can be pe o med, allowing us o
o mula e explici exp essions o he de lec ion p obabili ies. In his pape
we conside he case o De B uijn and Kau z dig aphs B(d, D) and K(d, D)
[2] as models o he ne wo k opology. In pa icula , we a e in e es ed in he
compu a ion o he ollowing wo p obabili ies, which appea in he Ma ko
chain desc ibed in [5]:
•Inpu p obabili y Pin(i): Gi en a uni o m andom e ex , le Pin(i) be he
p obabili y ha ano he uni o mly andom choosed e ex w,w6= , is a
dis ance i om .
•De lec ion p obabili y Pd(i, j): I a packe is de lec ed when i is isi ing a
e ex a dis ance i o he des ina ion e ex z,Pd(i, j) is he p obabili y
ha he new dis ance o za e he de lec ion has occu ed is j.
In his pape we p esen a con enien cha ac e iza ion o he laye s uc u e
1Resea ch suppo ed by he Minis e io de Econom´ıa y Compe i i idad (Spain) unde
p ojec MTM2014- 60127-P, and by he Ca alan Resea ch Council unde p ojec 2014-
SGR-1147.
2Email: [email p o ec ed]
3Email: [email p o ec ed]
4Email: [email p o ec ed]
o De B uijn and Kau z dig aphs (Sec ion 3) ha is used o compu e he gi en
p obabili ies (Sec ion 4). Because o he lack o space we omi p oo s which
a e echnical and edious as well as algo i hmic aspec s ha will be p esen ed
in a ull pape .
2 Laye s uc u e o B(d, D)and K(d, D)
We will use he well-known sequence ep esen a ion o he e ices o B(d, D)
and K(d, D). Each e ex o B(d, D) co esponds o a sequence = 1 2··· D,
whe e each elemen kbelongs o an alphabe Ao dsymbols, and e ex
is adjacen o he d e ices w= 2··· D D+1, D+1 ∈A. Analogously,
each e ex o K(d, D) co esponds o a sequence = 1 2··· D, whe e now
k6= k+1, 1 ≤k < D, and he base alphabe Ahas d+ 1 symbols, d≥2.
Ve ex is adjacen o he d e ices w= 2··· D D+1, D+1 ∈A, D+1 6= D.
The dig aphs B(d, D) and K(d, D) a e d- egula and ha e diame e D.
In o de o desc ibe he laye s uc u e o he e ex se Vo hese di-
g aphs in a way con enien o compu e inpu and de lec ion p obabili ies
in he co esponding ne wo ks we in oduce he ollowing de ini ions. Gi en
∈V, le Si( ) be he se o e ices o which he e exis s a walk om
o leng h i,i≥0, and le S⋆
i( ) be he se o e ices a dis ance i om ,
0≤i≤D. Mo eo e , o 0 ≤k≤ile Sk,i( ) = Sk( ) i Sk( )⊂Si( ) and
Sk( )6⊂ Sj( )⊂Si( ) o k < j < i, and le Sk,i( ) = ∅o he wise. The nex
esul ollows easily.
P oposi ion 2.1 Le ∈V. Then
(i) |Si( )|=di o 0≤i≤D.
(ii) I G=B(d, D)and i≥D, hen Si( ) = V.
(iii) I G=K(d, D)and i≥D+ 1, hen Si( ) = V.
(i ) I k≤i < D, hen ei he Sk( )⊂Si( ′)o Sk( )∩Si( ′) = ∅. Mo eo e ,
Sk( )⊂Si( ′)i and only i k+1 = ′
i+1, k+2 = ′
i+2, . . . , D+k−i= ′
D.
The ollowing p oposi ion p o ides a desc ip ion o he laye s S⋆
i( ) and a
polynomial exp ession o i s ca dinali y.
P oposi ion 2.2 I ∈V, hen
(i) S⋆
i( ) = Si( ) i−1
[
k=0
Sk,i( ).
(ii) |S⋆
i( )|=di−ai−1di−1− · · · − a1d−a0, whe e ak∈ {0,1}and ak= 1 i
and only i Sk,i( )6=∅.
In a simila way, we can gi e a p ecise polynomial desc ip ion o |S⋆
i( )∩
S∗
j(w)|when wis a e ex adjacen om .
P oposi ion 2.3 Le wbe a e ex adjacen om such ha S⋆
i( )∩S∗
j(w)6=
∅ o some j,i≤j < D. Then |S⋆
i( )∩S∗
j(w)|=di−bi−1di−1−...−b1d−b0,
whe e he coe icien s b ∈ {0,1}a e de e mined om he coe icien s ako he
polynomial exp ession o |S⋆
i( )|. Mo e p ecisely,
(i) I ai−1= 1, hen bk=ak o all k.
(ii) I ai−1= 0 and ei he Si−1,j(w) = ∅o ∅ 6=Si−1,j (w)6⊂ Si( ), hen
bk=ak o all k.
(iii) I ai−1= 0 and ∅ 6=Si−1,j(w)⊂Si( ), hen bi−1= 1, and o k < i −1
we ha e: bk= 0 i ak= 0,bk= 0 i ak= 1 and Sk( )⊂Si−1,j(w), o
bk= 1 i ak= 1 and Sk( )6⊂ Si−1,j(w).
3 Inpu and de lec ion p obabili ies
In his sec ion we use P oposi ions 2.2 and 2.3 o compu e he inpu and
de lec ion p obabili ies in B(d, D) and K(d, D) ne wo ks.
Le V=V1∪ · · · ∪ Vlbe he pa i ion induced by he equi alence ela ion
de ined by = 1 2. . . D∼ ′= ′
1 ′
2. . . ′
Di and only i he e exis s a
pe mu a ion σo he symbol alphabe Asuch ha σ( k) = ′
k, 1 ≤k≤D.
The classes V co espond o he di e en sequence s uc u es o he e ices.
P oposi ion 3.1
(i) |V |is easily compu ed om dand he numbe so dis inc symbols in
he sequence ep esen a ion o ∈ V .
(ii) I nsis he numbe o e ex classes V such ha |V |=ms, hen nsdoes
no depend on dand i can be compu ed ecu si ely using he equali y
Psnsms=n.
(iii) I , ′∈ V hen |S⋆
i( )|=|S⋆
i( ′)|.
Gi en a e ex selec ed a andom (uni o mly) om V, le Pin(i) be he
(inpu ) p obabili y ha a uni o mly andom selec ed e ex om V { }is
a dis ance i om . We ha e Pin(i) = P Pin(i| ∈ V )P( ∈ V ), whe e
Pin(i| ∈ V ) = |S⋆
i( )|/n −1 and P( ∈ V ) = |V |/n. In his way we ob ain
he ollowing esul .
Theo em 3.2 The inpu p obabili y Pin(i)can be exp essed as
Pin(i) = 1
n(n−1)
l
X
=1
|V |di−a( ,i)
i−1di−1− · · · − a( ,i)
1d−a( ,0)
0
whe e a( ,i)
k∈ {0,1}. I ∈ V , hen a( ,i)
k= 1 i and only i Sk,i( )6=∅.
No ice ha Pin(i| ∈ V ) = Θ 1/dD−iindependen ly o he e ex class
V , and, hence, Pin(i) = Θ 1/dD−i.
I a packe is de lec ed when i is isi ing a e ex a dis ance i o he
des ina ion e ex z, he p obabili y Pd(i, j) ha he new dis ance o za e a
de lec ion has occu ed is jcan also be calcula ed as Pd(i, j) = P Pd(i, j | ∈
V )P( ∈ V ), whe e Pd(i, j | ∈ V ) = (1/(d−1))|S⋆
i( )∩S⋆
j(w)|/|S⋆
i( )|.
Finally we ha e:
Theo em 3.3 The de lec ion p obabili ies Pd(i, j),1≤i≤j < D, a e gi en
by
Pd(i, j) = 1
n(d−1)
l
X
=1
c( ,i,j)|V |p( ,i,j)
whe e
p( ,i,j)=di−b( ,i,j)
i−1di−1− · · · − b( ,i,j)
1d−b( ,i,j)
0
di−a( ,i)
i−1di−1− · · · − a( ,i)
1d−a( ,i)
0
and a( ,i)
k, b( ,i,j)
k, c( ,i,j)∈ {0,1}. Mo eo e , le ∈ V and le wbe he e ex
adjacen o m gi en by w= 2··· D i+(D−j). Then
(i) c( ,i,j)= 0 i and only i Si( )⊂S ,j(w) o some ,i≤ < j.
(ii) a( ,i)
k= 1 i and only i Sk,i( )6=∅and b( ,i,j)
kis de e mined om a( ,i)
k.
4 Final ema ks
The p obabili ies gi en in Theo ems 3.2 and 3.3 can be used o calcula e he
e iciency o de lec ion ou ing in De B uijn and Kau z ne wo ks by means o
he Ma ko model men ioned in Sec ion 2.1, which can be ound in [5].
We emphasize ha ou analysis o he laye s uc u e o he dig aph and
he e iciency o de lec ion ou ing in he co esponding ne wo k opology can
be ex ended o o he amilies o dig aphs on alphabe o o gene al i e a ed
line dig aphs such ha , o ins ance, gene alized De B uijn cycles [3].
Re e ences
[1] Ba an, P., On dis ibu ed communica ions ne wo ks, IEEE T ans. Comm. Sys.
12 (1964), 1–9.
[2] Be mond, J.C., and Pey a , C., De B uijn and Kau z ne wo ks: A compe i o
o he hype cube?, In: And e, F., Ve jus, J.P. (eds): Hype cube and Dis ibu ed
Compu e s, No h-Holland, Ams e dam (1989), 279–294.
[3] G´omez, J., Pad ´o, C., and Pe ennes, S., La ge Gene alized Cycles, Disc e e
Appl. Ma h. 89 (1998), 107–123.
[4] G´omez, J., Fiol, M. A., and Yeb a, J. L. A., G aphs on alphabe s as models o
la ge in e connec ion ne wo ks, Disc e e Appl. Ma h. 37/38 (1992), 227–243.
[5] F`ab ega, J., and Mu˜noz, X., A s udy o ne wo k capaci y unde de lec ion
ou ing schemes, Eu o-Pa 2003 Pa allel P ocessing, LNCS 2790 (2003), 989–
994,
[6] Fiol, M.A., Yeb a, J.L.A., and Aleg e, I., Line dig aph i e a ions and he (d, k)
dig aph p oblem, IEEE T ans. Compu . C-33 (1984), 400–403.
[7] Hae i, S., and T ajko ic, L., In elligen de lec ion ou ing in bu e -less ne wo ks,
IEEE T ansac ions on Cybe ne ics, 45 (2) (2015), 316–327.
[8] Zheng, X., Hu, Y., Luo, D., and Wu, X., S udy o De lec ion Rou ing om an
In o ma ion- heo e ic Pe spec i e, In e na ional Jou nal o Fu u e Gene a ion
Communica ion and Ne wo king, 8(1) (2015), 227–236.