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−iindependen 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.