TELKOM
NIKA
, Vol.13, No
.1, March 2
0
1
5
, pp. 305~3
1
3
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i1.1262
305
Re
cei
v
ed Se
ptem
ber 28, 2014; Revi
se
d De
cem
ber
2, 2014; Acce
pted De
cem
b
er 29, 201
4
Topology Architecture and Routing Algorithms of
Octagon-Connected Torus Interconnection Network
You
y
ao Liu*, Lidong Xing, Xin Zhou
Schoo
l of Elect
r
onic En
gin
eer
i
ng, Xi’a
n Univ
e
r
sit
y
of Posts &
T
e
lecommu
nic
a
tions
，
Xi’a
n 7
101
21, Ch
ina
*Corres
p
o
ndi
n
g
author, em
ail
:
l
yya
o20
02@
xupt.edu.c
n
A
b
st
r
a
ct
T
w
o important
issues
in
the
d
e
sig
n
of
interc
onn
ectio
n
n
e
tw
orks for
massi
vely
para
lle
l c
o
mp
uters
are sca
lab
ility
and s
m
all
di
a
m
eter. A
new
interco
nnecti
on
netw
o
rk topo
l
ogy, cal
l
ed
oct
ago
n-con
necte
d
torus (OCT
), i
s
propos
ed. T
he OCT
netw
o
rk comb
in
es
the sma
ll di
a
m
et
er of
octagon
topol
ogy a
nd th
e
scala
bil
i
ty of torus top
o
lo
gy.
T
he OCT
net
w
o
rk has bet
t
e
r pro
perties,
such as s
m
all
dia
m
eter, reg
u
lar,
symmetry a
nd
the scal
abi
lity. T
he no
des
of the OCT
netw
o
r
k
ado
pt the
Jo
hnso
n
co
din
g
s
c
he
me w
h
ic
h c
a
n
mak
e
routi
ng
alg
o
rith
ms si
mple a
nd efficie
n
t. Both
unica
sting an
d broa
dcastin
g
routin
g alg
o
rith
ms a
r
e
desi
gne
d for the OCT
netw
o
rk, and it is base
d
on t
he Jo
hns
on cod
i
n
g
sche
m
e. A deta
i
l
ed
ana
lysis show
s
that the OCT
n
e
tw
ork is a bett
e
r interc
onn
ection
netw
o
rk in t
he pr
operti
es o
f
topolo
g
y an
d
the perfor
m
anc
e
of commu
n
ic
ati
on.
Ke
y
w
ords
:
tor
u
s, octago
n, intercon
nectio
n
n
e
tw
ork, Johnso
n
codi
ng, routi
n
g
al
gorith
m
s
1.
Introduc
ti
on
The la
rge
-
sc
ale mult
ip
ro
ce
ss
or
sy
st
e
m
wh
i
c
h
co
ntains th
ou
sand
s of p
r
o
c
e
s
sors
become
s
p
o
ssible
with th
e
develop
ment
of ha
rd
ware
techn
o
logie
s
,
especi
a
lly th
e improveme
n
t
of VLSI technology [1]-[3]
.
For exampl
e, ther
e exi
s
ts 716
8 comp
uting nod
es i
n
Tianh
e -1A
[4],
and the
num
ber
exce
ed
s
80,000 i
n
the
Fujitsu
su
pe
rcomp
u
ting
sy
stem [5]. In the comin
g
ye
ars,
new appli
c
ati
ons and algo
rithms will
pro
m
otes sin
g
le
chip
proce
ssor
core to h
a
v
e sam
e
num
ber
with
the 198
0s’ sup
e
rcom
puting syste
m
nod
e
[3
]. We
are
hea
d
ed for the ex
ascale
co
mp
uting
age a
nd
will
rea
c
h thi
s
ne
w e
r
a in
20
1
8
with
su
percomp
uting
sy
stem h
a
s 1 e
x
aFLOPS (1
0
18
FLOPS) [2],[3],[6].
In the exa
s
ca
le computin
g
age, multip
ro
ce
ssor
syste
m
will
ha
s hu
ndre
d
s of mill
ions of
pro
c
e
s
sor co
res. At th
e
same
time, i
n
terconn
ectio
n
net
works
have g
r
eat i
n
fluen
ce
on
the
perfo
rman
ce
of su
ch m
a
ssive system
a
nd al
so
d
e
termine the
com
putational
an
d sto
r
ag
e abil
i
ty
of the mass
ive parallel application in the fu
ture [2],[3],[6]. Thus
, in
order to improve the
comm
uni
cati
on effici
en
cy of parallel
co
mputation,
re
sea
r
che
r
s ha
ve bee
n en
g
aged
in the
study
of interconne
ction net
wo
rk with simpl
e
stru
ct
ure, lo
w deg
ree
of node, sh
ort
diameter, e
a
sy
routing
strate
gy and fine scala
b
ility [1],[7]-[14].
For a
la
rge scale syste
m
, the
topolo
g
y has a
maj
o
r
i
m
pact on
th
e perfo
rman
ce
and co
st
of the interco
nne
ction net
work. The to
pology of
Torus interco
nne
ction network has its sp
ecial
feature
s
su
ch
as regul
arity, sy
mmet
r
y, fault-toleran
c
e,
sho
r
t di
amete
r
, emb
edd
abil
i
ty and
so
on;
hence it is
well received am
ong researchers and practitioners
[2],[5],[7],[8],[11]-[17]. Bei
n
g
rega
rd
ed
as one
of th
e
mo
st impo
rtant and
att
r
active
types of typology
for
pa
ralleli
ng
comp
utationa
l netwo
rk, it h
a
s
been
impl
emented
in I
B
M BLUE
G
E
NE/Q net
wo
rk [1
5], 3D Cray
netwo
rk [16]
and
Fujitsu
T
o
fu net
wo
rk [5]. Ho
weve
r,
whe
n
d
ealing
with
a n
e
two
r
k which
cont
ain
s
millions, o
r
h
undred
s of b
illions of p
r
o
c
e
s
sor
co
res, the traditio
nal Torus
ne
twork would
not
suitabl
e fo
r th
e conn
ectio
n
of the futu
re
parall
e
l
syste
m
s fo
r it
s ove
r
ly lengt
hene
d dia
m
eter. A
s
i
s
requi
re
d that the parall
e
l progra
m
s shoul
d acco
mpli
sh
frequent co
mmuni
cation
within one
se
t of
node
s (lo
c
al
commu
nication), a num
ber of To
ru
s-ba
sed
HINs (hierarchi
cal
interconn
ect
i
on
netwo
rks) [1
6]-[22] a
r
e
p
u
t forward. A
m
ong
the
s
e
hiera
r
chi
c
al i
n
terconn
ectio
n
net
wo
rks, l
o
w-
level netwo
rks, con
s
istin
g
of computati
onal nod
es,
carry local
communi
catio
n
, and high-l
e
vel
netwo
rks, co
nsi
s
ting of cl
uster g
r
o
u
p
s
, are re
sp
on
si
ble for teleco
mmuni
cation.
As the diam
eter
of HINs is the product
of
the net
work
diameters of
every level, it
still turns
out to be relatively
large. In co
ntrast, the Toru
s embe
dde
d Hypercu
be
[1
2],[13] is the
combi
nation
of Toru
s network
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 305 – 3
1
3
306
and
Hype
rcu
be n
e
two
r
k a
nd its dia
m
et
er i
s
th
e
sum
of two
interco
nne
cted
one,
whi
c
h
gre
a
tly
cut
down the len
g
th of diameter of the whol
e netwo
rk.
Octag
on [23]
interconn
ecti
on network i
s
appl
i
ed to
on-chip
-n
etwork
by F. Karim and
other
re
se
archers. Its to
po
logica
l stru
cture po
ssesse
s cha
r
a
c
teri
st
ics of
regul
arity, symmetry,
and sh
ort dia
m
eter. In ord
e
r to further redu
ce t
he dia
m
eter of the Toru
s net
work and imp
r
ov
e its
fault-toleran
c
e, local co
mmuni
cation
perfo
rman
ce, the pape
r provid
es
a new type
of
interconn
ecti
on net
wo
rk,
the o
c
tag
on-con
n
e
c
ted
toru
s (oct
agon
-conn
ect
ed torus
，
OC
T
)
interconn
ecti
on network, based on the
incorpo
r
atio
n of Toru
s n
e
twork’ s
sca
l
ability and short
diamete
r
of
Octag
on to
p
o
logi
cal
stru
cture. O
C
T i
s
a symm
etri
cal and
re
gula
r
interco
nne
ction
netwo
rk
whi
c
h is ch
ara
c
te
rize
d by sho
r
t diameter, g
ood scal
ability and local
comm
uni
cati
on
perfo
rman
ce.
Network ext
ensi
on a
nd
routing al
gorit
hm could
be
easily
achie
v
ed if ado
pting
Joh
n
son codi
ng schem
e o
n
the node of
OCT top
o
log
y
.
Und
e
r conditi
ons of a giv
en topolo
g
y, the
perfo
rma
n
ce of inte
rconne
ction n
e
t
work is
determi
ned by the routing
algorithm [8],[24]. Ther
efore, the uni
casting an
d broadcasting
routi
n
g
algorith
m
s a
r
e desi
gne
d in
this article b
a
se
d on t
he structu
r
e of O
C
T interco
n
n
e
ction n
e
two
r
k.
2. Octag
on-Conn
ected T
o
rus Inter
c
o
nnec
t
ion Ne
tw
o
r
k
2.1. Prelimin
aries
Defini
tion 1.
Binary
unit-di
stan
ce cycli
c
cod
e
is
a bin
a
ry code
who
s
e e
a
ch two
adja
c
ent
cod
e
s h
a
ve one and only
one bit different(unit di
st
a
n
ce
cha
r
a
c
te
ristic), and the first co
de
and
the last one i
n
those
cod
e
s
have on
e a
nd onl
y one b
i
t different(cy
c
le characte
ri
stic).
Defini
tion 2.
Binary cod
e
represents
each numb
e
r
in the descendin
g
se
qu
ence of
integers {
n
-1,
n
-2,…,2, 1,0}
as a bina
ry string of len
g
th
m
=
2
/
n
by an orde
r. T
h
e
bin
a
ry cod
e
has the p
r
op
erties of defin
ition 1 and as follows: i) for 0<
k
<
m
,
Q
=
Z
m
-1
…
Z
k
O
k
-1
…
O
0
(
Z
i
stan
ds f
o
r
0,
O
j
stand
s for
1,
k
≤
i
≤
m-1
,
0
≤
j
≤
k-
1
) is
the code
of i
n
teger
k
; i
i
)
fo
r
k
>
m
,
Q
=
O
m
-1
…
O
k-
m
Z
k
-
m
-
1
…
Z
0
(
Z
i
stan
ds
fo
r 0,
O
j
st
and
s fo
r 1,
0
≤
i
≤
k
-
m-
1
,
k-
m
≤
j
≤
m-
1
) i
s
t
he
code
of integ
e
r
k
; iii) for
k
m
,
Q
=
O
m
-1
…
O
0
(
O
i
stand
s for
1,
0
≤
i
≤
m-
1
) is the code of i
n
teger
k
; iv) for
k
0,
Q
=
Z
m
-1
…
Z
0
(
Z
i
s
t
an
ds
for 0,
0
≤
i
≤
m-1
) is the
code
of integer
k
.
This bin
a
ry code is
calle
d Joh
n
son cod
e
.
Defini
tion 3.
Two no
de
s in
two-dim
e
n
s
i
onal(2D) plan
e are na
med
as adj
acen
cy, if and
only if there is differen
c
e b
e
twee
n their
cod
e
s, an
d o
n
ly one bit varies.
Defini
tion 4.
If two rando
m node
s in 2
D
plan
e are adja
c
ent, the
n
a (di
r
e
c
t) li
nk exist
s
betwe
en the
m
, accordi
ng
to the definition 3.
Defini
tion 5.
The 2
k
×2
m
2
D
T
o
ru
s
(
a
bbr
e
v
ia
te
as
T
(
k
,
m
)) interco
n
nectio
n
network i
s
a
netwo
rk to
pol
ogy whi
c
h h
a
s
followi
ng p
r
opertie
s
:1
) it con
s
i
s
ts of 2
k
×2
m
node
s and 8
k
×
m
direct
links. 2) The
node’
s hori
z
ontal ordi
nat
e can b
e
m
a
rked with
m
-bits
John
so
n cod
e
, and
the
vertical
coo
r
d
i
nate ca
n be
marked with
k
-bit
s Jo
hn
son co
de. Th
e vertical
co
ordin
a
te of n
ode
take a
s
hig
h
-orde
r
po
sitio
n
, and take the ho
rizontal
ordin
a
te a
s
low o
r
de
r, the
n
com
b
ine th
em
into a node
s codi
ng, thus
any node
s ca
n be identifie
d by binary coding of
k
+
m
bits. 3) The rule
of nod
es
cod
i
ng: if a
nd
o
n
ly if there i
s
o
n
e
and
o
n
ly one
bit
d
i
fference
bet
wee
n
two n
o
des
codi
ng in T (
k
,
m
), the nodes a
r
e a
d
ja
cent an
d that mean
s there
exists a dire
ct link bet
we
en
them.
Figure 1 i
s
a
diag
ram
sho
w
ing to
polo
g
i
c
al
st
ru
cture
of 4×6
2D T
o
ru
s inte
rcon
nectio
n
netwo
rk. Inte
rco
nne
ction
n
e
twork T
(
k
,
m
) sho
w
s g
o
od prope
rties, such as
①
node codi
ng in
each ro
w a
n
d
col
u
mn a
r
e bina
ry unit
distan
ce
cy
clic
co
de.
②
There are o
n
ly four adj
a
c
ent
node
s in a
n
y cod
ed no
de
whi
c
h can n
a
t
urally form
structu
r
e of T
o
ru
s (but
bidi
mensi
onal
gray
node d
o
e
s
n
o
t meet this prop
erty wh
e
n
the amount
of encodi
ng
bits is g
r
eate
r
than or eq
ua
l to
5).
③
Whe
n
k
or
m
increa
se o
ne
positi
on, the n
u
mb
er of
co
rre
sp
ondin
g
no
de
only increa
se
s 4
m
or 4
k
(the nu
mber of bidi
mensi
onal g
r
ay node is 2
k
×2
m
, therefore, when
k
or
m
increase one
positio
n,
the numbe
r of co
rre
sp
ondi
ng n
ode wo
uld
do
uble to
its ori
g
inal
amou
nt).
④
XO
Ring
any
two nod
es
co
ding, the sum
of the total n
u
mbe
r
of
1 in the result wh
ich al
so can
be reg
a
rded
as
the minimu
m
dista
n
ce bet
wee
n
the
s
e t
w
o
node
s.
⑤
Thi
s
n
e
twork po
sse
s
se
s
simple
ro
uting
mech
ani
sm o
f
Hypercube
-l
ike.
Defini
tion 6
.
Octa
gon i
n
terconn
ect
ne
twork i
s
a
n
e
twork to
pol
ogy whi
c
h
h
a
s th
e
followin
g
pro
pertie
s
: 1) it
con
s
i
s
ts of
8 nod
es
and
12 direct lin
ks. 2
)
Its
co
ordin
a
te can
be
identified by 4-bits
Jo
hn
so
n cod
e
. 3) Th
ere exi
s
ts
on
e dire
ct link b
e
twee
n two a
d
jacent nod
e
s
in
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Topology Architecture and
Routing Algorithm
s
of Octagon-Connect
ed To
rus .... (Youyao Liu)
307
interconn
ect netwo
rk whe
n
these
two coding
hav
e o
ne and only one bit difference or the e
a
ch
bit of the resu
lt of XOR is 1.
Figure 2 pre
s
ents the topo
logical stru
ct
ure of
interco
nne
ct netwo
rk Octa
gon, a
nd also
sho
w
s go
od
qualitie
s of
Octag
on. 1
)
In this n
e
two
r
k, a
n
y no
de
s
conn
ectivity is 3, a
nd i
t
s
diamete
r
i
s
2
.
Octa
gon
is
regul
arity, sy
mmetry;
me
a
n
whil
e it h
a
s
other go
od
q
ualities,
su
ch
as
sho
r
t diamet
er, low conn
ectivity and so on. 2)
The
r
e are 3 un
crossed lin
ks b
e
twee
n any two
node
s in O
c
tagon. At the same time, the length
of
these 3 lin
ks are 1,4,4 if
two node
s li
nk
dire
ctly, or it
woul
d be
2,3,3. T
herefore, this net
wo
rk
has
high fa
ult-toleran
c
e a
n
d
pa
ralleli
sm.
3)
Whe
n
the re
sult of the XOR of two n
ode
s’ cod
e
is one 1 or fou
r
1s, the nod
es are adjoin
ed.
Whe
n
the re
sult is two o
nes o
r
thre
e
ones, the di
stan
ce bet
we
en to node
s
is 2. Ho
wev
e
r,
Octag
on is la
ck of scal
abili
ty.
Most of pa
rall
el pro
g
ra
m communi
cate f
r
equ
ently in a
set of nod
es, the commu
nicatio
n
perfo
rman
ce
has
a maj
o
r i
m
pact
on the
efficien
cy of
parall
e
l p
r
og
ram, and th
e
prin
cipal fa
ct
or i
s
distan
ce
of in
tra-g
r
ou
p no
d
e
[8],[10]. Thus, LIU F A e
t
al. [10] puts
forwa
r
d
s
a
ki
nd of pa
ram
e
ter
whi
c
h
can
b
e
u
s
ed i
n
ev
aluating l
a
ye
red i
n
tercon
n
e
ction
netwo
rk,
whi
c
h m
e
ans the o
p
timal
grou
ping i
s
a
n
evaluation
method on la
yered
inte
rco
nne
ction net
work pe
rform
ance.
Defini
tion 7.
The distance of node group [10
],[11]: the distan
ce of node group
G
ca
n
be defin
ed
as the
maxi
mum di
stan
ce between
any two n
o
des
wh
en t
he
G
i
s
i
n
t
h
e
interconn
ecti
on network
N
.
Defini
tion 8
.
Optimal g
r
oupi
ng [10],
[
11]: for the
given po
sit
i
ve integer
λ
, the
interconn
ecti
on n
e
two
r
k
N
contai
ns multiple
g
r
o
u
p
s of
λ
no
de
s, un
der this ci
rcu
m
sta
n
ce, the
minimum di
stance gro
up is the
optimal group
whi
c
h contain
s
λ
n
ode
s
,
r
e
c
o
r
d
ed
a
s
G
λ
(
N
).
Defini
tion 9.
Group divisible
perform
ance [10],[11]: for the
given interconnec
t
ion
netwo
rk
N
1
a
nd
N
2
,
there exists
the distance of
G
λ
(
N
1
) le
ss th
an
or eq
ual to
the dista
n
ce
of
G
λ
(
N
2
) for a
n
y positive integer
λ
, then the gro
u
p
divisible p
e
rform
a
n
c
e
of interco
nne
ction
netwo
rk
N
1
is
sup
e
rio
r
to the interconn
ection netwo
rk
N
2
.
If the group divisible pe
rf
orma
nce of interconn
ectio
n
netwo
rk
N
1
is supe
rior to the
interconn
ecti
on net
work
N
2
, makin
g
u
s
e of the
co
ndition that communi
catio
n
co
st of a set of
comp
utationa
l co
de
s
G
λ
(
N
1) i
s
le
ss t
han th
e o
n
e
of
G
λ
(
N
2
)
, thus the
ne
twork
divisibl
e
perfo
rman
ce
can b
e
sh
owed its own sig
n
ifican
ce.
Within the l
i
mitations of
hard
w
a
r
e
resou
r
ces, i
n
ord
e
r to
improve
calcul
ated
perfo
rman
ce
of
the whol
e
parallel syst
em,
the
n
e
twork shoul
d o
c
cupy resou
r
ce
s a
s
l
e
ss
as
possibl
e, and
packin
g
de
n
s
ity can
eval
uate the h
a
rd
ware resource of intercon
nectio
n
net
work
[18].
Defini
tion 1
0
. The
pa
cki
ng
den
sity of int
e
rconn
ectio
n
netwo
rk is de
fined a
s
th
e
ratio of
the numbe
r o
f
nodes of a n
e
twork to the
prod
uct of net
work dia
m
ete
r
and de
gree
[18].
000
00
00
001
0
0011
0
0111
00110
00100
010
00
01
001
0
1011
0
1111
01110
01100
110
00
11
001
1
1011
1
1111
11110
11100
100
00
10
001
1
0011
1
0111
10110
10100
0000
0001
0011
0111
1111
1110
110
0
10
00
Figure 1. To
pology an
d n
ode codin
g
of T(
k
,
m
)
Figure 2
．
Topol
ogy
and nod
e co
ding
（
k
=2,
m
=3
）
of Octagon
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 305 – 3
1
3
308
2.2. Octag
o
n
-
Co
nnec
t
ed
Torus Inte
rc
onnec
t
ion Net
w
o
r
k
With 8
×
2
k
×2
m
nodes, th
e octa
gon
-co
nne
cted toru
s (O
CT
(
k
,
m
),
whe
r
e
k
,
m
are the
para
m
eters o
f
network sca
l
e) intercon
ne
ction net
work should b
e
constructe
d by integrating t
he
sho
r
t diamete
r
of Octag
on
and the scal
a
b
ility of Torus as followi
ng
ways:
1) Fi
rstly, ba
sed
on
defini
t
ion 6, ei
ght
node
s
ca
n fo
rm a
n
O
c
tag
on n
e
two
r
k.
There
will
be 2
k
×2
m
Octagon net
works in the e
nd
and ea
ch of
them is referred to as a sli
c
e.
2) Fo
rm 2
k
×2
m
slices
int
o
Toru
s net
work: e
n
code
2
k
×2
m
slice
s
by 4 bits of Joh
n
son
cod
e
and,
co
mplying with
the definition
5, conn
ec
t n
ode
s of sam
e
cod
e
s i
n
e
a
ch
slice to form
netwo
rk T
(
k
,
m
).
3)
En
co
de O
C
T (
k,
m
):
Code
of ea
ch
node
con
s
ist
s
of t
w
o
part
s
-A
t
and A
o .
A
o
(
J
oh
ns
o
n
cod
e
4
)
i
s
code
of no
de
in ea
ch
O
c
ta
gon
network.
A
t
(John
so
n
co
de
k
+
m
) i
s
cod
e
of
ea
ch
Octag
on area
, namely the cod
e
of node
in each T (
k
,
m
) network.
The top
o
logi
cal structu
r
e o
f
interconn
ect
i
on net
work
OCT
(
k,
m
)
is
as
s
h
ow
n
in
F
i
g
.
3
whe
r
e the
sol
i
d lines
rep
r
e
s
ent the O
c
ta
gon inte
rcon
nectio
n
network li
nk, the
dashed lin
es
are
the intercon
n
e
ction n
e
two
r
k T(
k
,
m
) link and the ci
rcl
e
s a
r
e no
de
of netwo
rk. T
he direct lin
ks
exist betwe
en
endpoint
s which ma
rks a
r
ound a
r
e the
same. Th
e scale of internet
work O
C
T(
k,
m
)
node
s ca
n b
e
expande
d to form intercon
ne
ction n
e
twork O
C
T
(
k,
m
+
1)
o
r
OC
T
(
k+
1,
m
) by
increa
sing
on
e bit on the
code-
m
or
k
,
whi
c
h e
nable
s
two li
ne
s or colum
n
s
(4
k
or
4
m
relev
a
nt
node
s ad
ded
) adde
d in ne
twork T(
k
,
m
) and 8×4
k
or
8
×
4
m
node
s
adde
d in net
work O
C
T
(
k
,
m
) .
In the o
r
igi
n
al net
work O
C
T(
k,
m
), the
r
e i
s
no
ch
a
nge
of the
n
e
twork conn
ection
s i
n
e
a
c
h
Octag
on a
r
e
a
and th
e con
nectivity of n
ode
s. In the i
n
terconn
ectio
n
network T
(
k
,
m+
1) or T(
k+
1,
m
) , exce
pt th
e no
de
s
con
n
e
cting
the
ad
ded
one
s,
th
e
r
e
rem
a
in
s n
o
chan
ge
of o
t
her
nod
es a
nd
con
n
e
c
tion
s. As the examp
l
e in Figure 3,
interc
o
nne
cti
on network O
C
T(2,3) is fo
rmed from eig
h
t
Octag
on area
s add
ed on th
e right sid
e
of network O
C
T(2,2
)
.
A1
A2
A3
A4
A5
A6
A7
A8
B1
B2
B3
B4
B5
B6
B7
B8
C1
C2
C3
C4
C5
C6
C7
C8
D1
D2
D3
D4
D5
D6
D7
D8
A1
A2
A3
A4
A5
A6
A7
A8
B1
B2
B3
B4
B5
B6
B7
B8
C1
C2
C3
C4
C5
C6
C7
C8
D1
D2
D3
D4
D5
D6
D7
D8
A1
E1
E2
E3
E
4
E5
E6
E7
E8
F1
F2
F
3
F4
F
5
F6
F7
F8
G1
G2
G3
G
4
G5
G
6
G7
G8
H1
H2
H3
H4
H
5
H6
H7
H8
E1
E2
E3
E
4
E5
E6
E7
E8
F1
F2
F
3
F4
F
5
F6
F7
F8
G
1
G2
G3
G
4
G5
G
6
G7
G8
H
1
H2
H3
H4
H
5
H6
H7
H8
Figure 3.Top
o
logi
cal struct
ure of O
C
T(k,
m)
（
k=
2, m=2
）
Theorem
. In interconn
ecti
on network O
C
T (
k
,
m
), with two node
s
A
(
A
m
+
k
+3
…
A
m
+
k
,
A
m
+
k
-
1
…
A
m
A
m
-1
…
A
1
A
0
),
B
(
B
m
+
k
+3
…
B
m
+
k
,
B
m
+
k
-1
…
B
m
B
m
-1
…
B
1
B
0
)
，
A
i
,
B
i
,
A
j
,
B
j
{0,1}
，
i
{4,…,
m
+
k
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Topology Architecture and
Routing Algorithm
s
of Octagon-Connect
ed To
rus .... (Youyao Liu)
309
+3 }
，
j
{
0
,
1,
2, 3}
，
the
distance
between A a
nd B will
be
d
(
A
,
B
)=
j
j
j
ij
j
j
i
i
j
j
j
ij
j
j
i
i
B
A
for
B
A
B
A
B
A
for
B
A
B
A
}
4
,
3
{
,
1
}
2
,
1
{
,
。
Proof.
Each
node
s co
din
g
in Octag
o
n
slice a
nd th
e node
s codi
ng in T (
k
,
m
) are
Joh
n
son
cod
e
. From th
e
constructio
n
p
r
oce
s
s of inte
rcon
ne
ction n
e
twork
OCT
(
k
,
m
), it can
be
see
n
that th
e
dista
n
ce b
e
twee
n a
n
y two no
de
s e
qua
ls the
di
stan
ce of the
two
node
s i
n
T
(
k
,
m
)
plus th
ose in
Octag
on. In
Octag
on
slice, t
here i
s
o
n
e
and
only o
ne bit differe
nce
between
any
two n
ode
s
or
the result of
XOR i
s
1, the
s
e t
w
o
nod
es are a
d
jacent,
that
is the
di
stan
ce
betwe
en
any two
no
de
s i
s
the
different bits of two no
de
s o
r
th
e same
bits
o
f
two n
ode
s
p
l
us
one; th
ere
is
one a
nd
only
one
bit difference bet
wee
n
two
nod
es i
n
T (
k
,
m
), th
e nod
es are
adja
c
ent, that
is
the di
stan
ce
of any two n
ode
s i
s
the
n
u
mbe
r
of
di
fferent
bits in
any two
no
de
s. Th
erefo
r
e,
thi
s
theore
m
is e
s
tablish
ed.
2.3. The Properties o
f
O
C
T (k, m)
Char
acter 1
. The
inte
rco
nne
ction
net
work of O
C
T (k, m
)
i
s
regul
ar on
e, and
the
con
n
e
c
tivity o
f
any node is
7.
Owin
g to ev
ery O
c
tago
n
belon
gs to
the re
gula
r
i
n
terconn
ectio
n
network, a
nd the
con
n
e
c
tivity of any nod
e is
3. Accordi
ng
to the
form
ation of the i
n
te
rco
nne
ction
n
e
twork
OCT
(
k,
m), taking
O
c
tago
n as a
node, a
s
the
result, th
is interconn
ectio
n
netwo
rk is interconne
cti
on
netwo
rk of
T(
k
,
m
),an
d
the
con
n
e
c
tivity of no
de i
s
4.T
h
u
s
, O
C
T(k,m
)
is th
e
reg
u
lar
interconn
ecti
on network, and the co
nne
ctivity of node is 3+4
=
7.
Char
acter 2.
The m
a
xim
u
m di
stan
ce
(the
diamet
er) bet
ween
any two
no
des the
interconn
ecti
on network of OCT (k,m) is
k
+
m
+2.
As the di
ame
t
er of inte
rco
nne
ction n
e
twork
of T (
k
,
m
) is the di
ameter
of 2
m
and
2k
node
ring
s, whi
c
h is
m
+
k
. According t
o
the pro
c
e
s
s formatio
n o
f
the interco
n
nectio
n
network
OCT
(
k
，
m
), takin
g
as a T
(
k
,
m
) as a n
ode, as the result, this int
e
rconn
ectio
n
network is t
he
Octag
on inte
rcon
ne
ction n
e
twork, an
d the diam
eter
i
s
2. Thu
s
, th
e diamete
r
of
internet i
s
th
e
combi
nation
of the diameter of Torus a
nd Octa
gon,
whi
c
h are
m
+
k+
2.
Char
acter 3
. The Symmetrical net
work o
f
OCT(
k,
m
) interco
nne
ction
network.
Acco
rdi
ng to t
he p
r
o
c
e
s
s fo
rmation
of the
OCT
(
k,
m
) interconn
ectio
n
netwo
rk, ta
ki
ng a
n
y
node m
a
rk in
this net
work as a i
n
itial p
o
int, that
is we ca
n come t
o
the same
concl
u
si
on fro
m
observing
ev
ery no
de.
Realizi
ng the
simplific
ation
of ro
uting
algorith
m
tha
t
is the
routi
n
g
algorith
m
and
the node po
sition is irrelev
ant.
Char
acter 4.
The link n
u
m
ber of the inte
rco
nne
ction n
e
twork of O
C
T(
k,
m
)
is
1
12×
k
×
m.
The lin
k
nu
mber of inte
rco
nne
ction
netwo
rk of
OCT
(
k
，
m
) i
s
the
combi
nation
with
2
k
×2
m
of
O
c
tago
n
lin
k numbe
r 12
and 8 2
k
×2
m
of Toru
s
2×2
k
×2
m,
that is 2
k
×2
m
×12
+
8×2
×
2
k
×2
m
=11
2
×
k
×
m.
Char
acter 5.
The bisectio
n
width of intercon
ne
ction n
e
twork of O
C
T(
k,
m
) is 24
×
k
×
m.
The inte
rcon
nectio
n
net
work bi
se
ction
width i
s
that
whe
n
the i
n
te
rco
nne
ction
n
e
twork i
s
divided into
two eq
ual
subnet
s, the
minimum lin
k numb
e
r m
u
st be d
e
lete
d. The bi
se
ct of
OCT
(
k,
m
) i
n
terconn
ectio
n
netwo
rk i
s
di
viding 2
k
×2
m
O
c
tagon
inte
rco
nne
ction
n
e
twork,
and
th
e
width is 6,thu
s
the bisectio
n width is 6
×
2
k
×2
m
=24
×
k
×
m.
For furth
e
r e
x
plain the go
od f
eature of the intercon
nectio
n
network, the T
abl
e 1 gives
the comp
ari
s
on three
kind
s of static net
works.
The
scalabilit
y of the inte
rco
nne
ction
netwo
rk is th
at netwo
rk topolo
g
y perf
o
rma
n
ce
maintain the
same, th
e ab
ility to expand the no
de
will influe
nce
the ro
utes
e
fficiency. In t
h
e
interconn
ecti
on network
of OCT (k,m
), the expan
sion of
n
e
t
w
ork
si
ze
an
d
the config
uration
informatio
n of the interco
n
n
e
ction n
ode
st
ay the same,
and have the
good expa
nsibility.
Table 1. Perf
orma
nce ch
aracteri
stics of th
ree
kind
s of static net
works [12],[13]
T
y
pe
of net
w
o
rk
Node Deg
r
ee
Number of
Links
Net
w
ork Diamete
r
Bisection Width
OCT
(
k
，
m
)
7
112×
k
×
m
k
+
m
+2
24×k×m
(2
k
,2
m
,3)-
OMM
H
7
112×
k
×
m
k
+
m
+3
16×k×m
T(2
k
,4
m
)
4
64×
k
×
m
2
k
+4
m
min{8
k,
6m }
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 305 – 3
1
3
310
The diam
ete
r
of the interconn
ectio
n
network d
e
termin
es th
e informatio
n might
experie
nce th
e num
be
r of t
he h
op. Th
e
node
de
gr
e
e
of intercon
ne
ction
network determine
s t
he
compl
e
xity of the hard
w
a
r
e. Since the
diameter
wil
l
get smalle
r of higher n
ode de
gre
e
, the
diamete
r
an
d nod
e mu
st take into
con
s
id
erat
io
n
for the ev
aluation
of the cost of
the
interconn
ecti
on net
work [
13],[18]. Accordin
g to
the
definition 1
0
and tabl
et 1
,
the packa
gi
ng
den
sity of three
inte
rco
nne
ction
net
work O
C
T(
k
,
m
), (2
k
,2
m
,3)- OMMH,
T(2
k
,4
m
) can
demon
strate in the figure
4. The high
er the packi
n
g
den
sity of a netwo
rk, the
smalle
r the
chip
area
req
u
ired
for its VLSI layout. The fig
u
re
sh
o
w
s th
at the OCT
(k, m) has th
e
highe
st pa
cki
ng
den
sity while
T(2
k
,4
m
) req
u
ire
s
the lowest pa
cki
ng d
ensity.
The id
eal th
rough
put of t
he inte
rconn
ection
net
work a
nd the
bi
se
ction
width
is di
re
ct
prop
ortio
n
[8],[14]. Thus,
we
can
dete
c
t from the
T
a
ble 1, the
wi
dth of halve
intercon
ne
ction
netwo
rk OCT
(
k
,
m
) bigg
er
than (2
k
,2
m
,3)- OMM
H
、
T(2
k
,4
m
), that is the ide
a
l throu
ghp
ut of
interconn
ecti
on network O
C
T(
k,
m
) is b
e
tter than (2
k
,2
m
,3)- OMM
H
、
T(
2
k
,4
m
). Meanwhile, the
interconn
ecti
on net
wo
rk
o
f
OCT
(
k,
m
) i
s
in the mi
ddl
e propo
rtion
wi
th the i
n
ternet pe
rform
a
nce,
and ha
s the b
e
tter band
wid
t
h expansi
b
ility.
Figure 4. Assembly de
nsit
y of
three kin
d
s of intern
etwork
From the
ch
ara
c
ter 1,2,3
,
4,5,
and rel
a
ting explan
ation of OCT(
k,
m
) interconne
ctio
n
network has t
he better
scal
ability.
Char
acter 6
.
Gro
up divi
sible prope
rty of interconn
e
c
tion n
e
two
r
k OCT
(
k,
m
) i
s
sup
e
rio
r
to (2
k
,2
m
,3)-OMMH and T
(
2
k
,4
m
).
Acco
rdi
ng to the con
s
tru
c
ti
on pro
c
e
s
s o
f
OCT(
k
,
m
) and the definit
ion 3
、
4
an
d 5
,
th
e
optimal group
distan
ce of OCT
(
k
，
m
), (
2
k
,2
m
,3)-OMMH , T(2
k
,4
m
) re
spe
c
tiv
e
ly
is
d
(
G
λ
(
T
or
us
))
=
2
(
1
) (1)
d
(
G
λ
(OMM
H)
) =
9
2
1
8
log
2
for
for
，
，
(2)
d
(
G
λ
(O
CT)
)
=
9
8
3
2
2
2
,
1
for
for
for
，
，
(3)
0
1
000
20
00
30
00
40
00
50
00
60
00
70
00
80
00
0
5
10
15
20
25
30
35
N
o
de
s
c
al
e
P
a
c
k
i
n
g
de
ns
i
t
y
OC
T
(
k
,
m
)
(2k
,
2m
,
3
)-
O
M
M
H
T(
2
k
,
4
m
)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Topology Architecture and
Routing Algorithm
s
of Octagon-Connect
ed To
rus .... (Youyao Liu)
311
From exp
r
e
s
sion (1)~(3),
the group d
i
vi
sible prope
rty of interne
t
work OCT(
k
，
m
) is
s
u
pe
r
i
or
to
(
2
k
,2
m
,3)-O
MMH and
T
(
2
k
,4
m
), whi
c
h
m
ean
s OCT
(
k
,
m
)
has better l
o
cal
comm
uni
cati
on ability.
With the i
n
crease of n
e
twork no
de
an
d the
in
crea
se
of proba
b
ility of node
or lin
ks
failure, the int
e
rconnection
network
should have the certain fault-
tol
e
rant
ability.
Because there
exists T
(
k
,
m
) and
Octa
g
on in O
C
T(
k,
m
) simultane
ously, the re
routing
of messag
e ca
n
be
achi
eved by simple u
pdati
ng the no-fa
ult tolerant
routing algo
rit
h
m whe
n
me
eting the sin
g
le
node a
nd lin
k failure. The failure of a
sin
g
le nod
e or li
nk in any no
n
-
so
urce n
ode
or de
stinatio
n
node ca
n
be
corre
c
ted by addin
g
two h
ops of
no
des and lin
ks in
bypass p
a
ths. When
source
node, de
stina
t
ion node a
n
d
error n
ode
or links a
r
e i
n
same
su
b-netwo
rk of T
(
k
,
m
), it can adds
one of hop
s in Octag
on to forwa
r
d me
ssag
e to the adjacent sub
-
n
e
twork of T(
k
,
m
), and adds
anothe
r h
op
can b
a
ck to th
e form
er
su
b-netwo
rk of T
(
k
,
m
). In the
same
way, wh
en
sou
r
ce n
o
de,
destin
a
tion n
ode a
nd e
rro
r node o
r
lin
ks are in
sam
e
sub
-
net
wo
rk
of Octag
on, it can
add
s on
e of
hop
s in T(
k
,
m
) to
forwa
r
d
message to the adjacent su
b
-
net
wo
rk
of Octago
n, and add
s an
other
hop can ba
ck to the former sub-network
of Octago
n.
The form
er a
nalysi
s
sh
ows that interco
nne
ction net
work O
C
T
(
k
,
m
) has good scalability,
well lo
cal co
mmuni
cation
perfo
rman
ce
and hig
h
fault-tolerant abilit
y.
3. Routing al
gorithms in OCT
Routin
g alg
o
rithm is
a
key
factor which
affects the e
fficiency
of th
e commu
nica
tion of
netwo
rk,
an
d this se
ction mainly
an
alyzes
th
e r
outin
g
algo
rithm
an
d pe
rforman
c
e of u
n
icast
a
nd
multicast.
3.1. Unicas
t Rou
t
ing Alg
o
rithm on O
C
T(k,m)
3.1.1. Unicas
t routing alg
o
rithm
Assu
ming
th
at No
de
A
(
A
m
+
k
+3
…
A
m
+
k
,
A
m
+
k
-1
…
A
m
A
m
-1
…
A
1
A
0
) se
nd the
data
to No
de
B
(
B
m
+
k
+3
…
B
m
+
k
,
B
m
+
k
-1
…
B
m
B
m
-1
…
B
1
B
0
), the Hamming
Dista
n
ce bet
wee
n
No
de A
and Node B
is
H
（
A
,
B
）
= Hammi
ng
（
A
⊕
B
）
,“
⊕
” m
e
a
n
s bit
w
ise X
O
R o
n
A an
d B and “Ha
mming” fu
nct
i
on
mean
s the
pl
us
com
putati
on of “1”
after XO
R on
A
and
B
. Fro
m
en
codin
g
method
on n
ode
T(
k
,
m
) & Oct
agon a
nd the
con
s
tru
c
tion
pro
c
e
ss
of OCT
(
k
,
m
), the sh
orte
st ro
ute of OCT
(
k
,
m
)
can b
e
se
en
as follo
ws.
①
If
A
and
B
are in a sa
me Octag
on,
as 2.2 has
mentione
d, their T(
k
,
m
) coding a
r
e
same, that is
when Hammi
ng
（
A
m
+
k
+3
…
A
m
A
m
-1
…
A
5
A
4
⊕
B
m
+
k
+3
…
B
m
B
m
-1
…
B
5
B
4
）
≡
0, the distan
ce
betwe
en
sou
r
ce n
ode A a
n
d
de
stination
B ia 1 or 2
o
n
ly routing i
n
A
o
=
A
3
…
A
0
，
B
o
=
B
3
…
B
0
of
Oc
tagon. If Hamming
（
A
3
…
A
0
⊕
B
3
…
B
0
）
=1
or 4, n
ode
A
sen
d
s messa
ge to
node
B
dire
ctly.
Otherwise,
A
o
should firstly compute the distan
ce
betwe
en
A
’s adja
c
ent nod
es
A
o
1
，
A
o
2
，
A
o
3
and
B
o
, and
sen
d
me
ssag
e to adja
c
e
n
t node
whi
c
h i
s
1 a
w
ay fro
m
destin
a
tion
node, a
nd th
en
to node
B
.
②
If A and B are in a sa
me T(
k
,
m
), as 2,2 ha
s me
ntioned,
their Octago
n co
ding are
same, that is Hammi
ng
（
A
3
…
A
0
⊕
B
3
…
B
0
）
≡
0 o
n
ly by routing
from no
de
A
t
=
A
m
+
k
+3
…
A
m
A
m
-
1
…
A
5
A
4
to
B
t
=
B
m
+
k
+3
…
B
m
B
m
-1
…
B
5
B
4
in T
(
k
,
m
). In netwo
rk T
(
k
,
m
), there onl
y a difference in
hori
z
ontal axi
s
and al
so in
ordinate of
adja
c
ent no
d
e
. The nod
e whi
c
h is left to node
A
t
is
A
l
=
A
m
+
k
+3
…
A
l
…
A
k
+1
A
k
4
A
A
k
-1
…
A
p
…
A
5
and
the n
ode
which
rig
h
t i
s
to
node
A
t
is
A
r
=
A
m
+
k
+3
…
A
l
…
A
k
+1
A
k
A
k
-2
…
A
p
…
A
5
A
4
1
k
A
,
the
nod
e which
i
s
on
t
he
no
de
A
t
is
A
u
=
k
A
S
m
+
k
+3
…
A
l
…
A
k
+1
A
k
-1
…
A
p
…
A
4,
the node which i
s
lower tha
n
the node
A
t
vertically is
A
d
=
A
m
+
k
+2
…
A
l
…
A
k
+1
A
k
3
k
m
A
A
k
-2
…
A
p
…
A
5
A
k
-1
，
the
n
the di
stan
ce bet
ween
th
e adja
c
e
n
t n
ode
of
A
t
and
B
t
is
H
l
= Hamming
（
A
l
⊕
B
t
）
,
H
r
= Hamming
（
A
r
⊕
B
t
）
,
H
u
= Hamming
（
A
u
⊕
B
t
）
,
H
d
=
Hammi
ng
（
A
d
⊕
B
t
）
. After
H
min
＝
min{
H
l
,
H
r
,
H
u
,
H
d
}
sendin
g
thi
s
data p
a
cket
to the
rela
tive
adja
c
ent no
d
e
of
H
min
and modifying
A
t
to the co
de of
that adjacent
code,
we ca
n com
puting t
h
e
res
u
lt of
H=
Hammi
ng
（
A
t
⊕
B
t
）
, if
H
≡
0 and
A
t
will be
a de
stination
node, oth
e
rwise the p
r
o
c
ess
will be re
peat
ed.
③
If A and B
are
not in
a
same O
c
tag
o
n
nor in a
sam
e
T(
k
,
m
), they are
any two
node
s,
then the
dat
a pa
cket
sh
ould
be
rout
ed firstly to
A’
(
A
m
+
k
-1
…
A
m
A
m
-1
…
B
3
B
2
B
1
B
0
) in a
s
a
me
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 305 – 3
1
3
312
Octag
on as t
he way in
①
,
A &
B are in a same T (
k
,
m
) and then routing data
packa
ge to the
destin
a
tion n
ode B in the T(
k
,
m
) as
the way in
②
.
3.1.2. Perfor
mance analy
s
is of algorithm
The
advanta
ge of
O
C
T(
k
,
m
) routin
g al
gorithm
is th
e ad
option
of
Jo
hn
son
Co
de in
T
(
k
,
m
), which makes the
Hammi
ng
（
A
⊕
B
）
of
any t
w
o
nod
es coding
be
com
e
the
minim
u
m
distan
ce
bet
wee
n
two
n
ode
s an
d thi
s
codin
g
al
so implie
s ro
uting info
rma
t
ion and
rel
a
tio
n
betwe
en t
w
o
adja
c
e
n
t co
des.
Thi
s
alg
o
rithm
ca
n g
e
t right
ro
uting result onl
y by savin
g
the
curre
n
t codi
n
g
and de
stin
ation co
ding
whe
n
tr
an
smi
tting data. Network O
c
tag
on also ado
p
t
s
Joh
n
son
co
di
ng, so th
e n
e
t
work
routin
g
will
be
sim
p
l
y
whe
n
XO
R re
sult i
s
a
1
or
ha
s
4
on
es,
whi
c
h mea
n
s the two node
s are a
d
ja
cen
t, and XOR result is 2 on
e
s
or thre
e on
es which m
a
kes
the nodal di
st
ance is 2.
Data
sho
u
ld
have twice
operation a
t
worst
acco
rding to
uni
cast ro
uting a
l
gorithm
OCT
(
k
,
m
), that mean
s it n
eed
s
k+
m
rou
nds’
com
m
un
ication
ope
rat
i
ons i
n
a sam
e
T(
k
,
m
) at the
worst, therefo
r
e, it needs
k+m
+
2 ro
und
s’
commu
ni
cation ope
ration
s at the worst.
If the algorithm
can
send
dat
a from
the
source
nod
e t
o
the d
e
stin
a
t
ion nod
e in
the
sho
r
test
way, this
kin
d
of
algorith
m
h
a
s high
commu
nicatio
n
effici
ency. A
ll
abo
ve uni
ca
st ro
uting al
gorith
m
s fo
rward d
a
ta
in a
sho
r
t
e
st
way
,
so
in t
h
e wo
r
s
t
ca
se,
t
he ro
uting p
a
th wo
uld n
o
t excee
d
the
n
e
twork
diame
t
er
k
+
m
+2, a
nd the com
m
uni
cation efficien
cy would be 1/
(
k
+
m
+2
).
3.2. Broad
c
a
s
ting Ro
utin
g Algorithm
on OCT
(
k,m)
3.2.1. Broad
cast ro
uting
algorithm
It is assume
d
that node A
sen
d
s d
a
ta to
all the other
node
s. No
de
A firstly send
s data to
all the node
s in the sam
e
Octag
on, and then
all
the node
s whi
c
h have receive
d
the dat
a
conve
r
sely se
nd the data to
all the node
s in their own
T(
k,
m
) with rec
u
rs
ive doubling method.
3.2.2. Perfor
mance analy
s
is of algorithm
Br
o
a
d
c
a
s
t
r
o
u
t
in
g
in
th
is
w
a
y, n
o
d
e
A s
e
nd
in
g
da
ta
to
a
ll th
e
no
d
e
s
in
th
e
O
c
ta
gon
need
s 2 ro
un
ds of com
m
u
n
icatio
n ope
rations, an
d then the data
broad
ca
sting
within T (
k,
m
)
need
s
m+k
round
s
of com
m
unication
s
operation
s
. T
herefo
r
e, th
e
radio
ne
ed
s
k+
m+
2
rou
n
d
s
of
comm
uni
cati
on ope
ration
s, and the com
m
unication ef
ficien
cy of algorithm is
1/
(
k+
m+
2
).
4. Conclusio
n
The inte
rcon
nectio
n
net
work To
ru
s a
n
d
the inte
rco
nne
ction n
e
twork
Octa
go
n are the
most impo
rta
n
t and the most attractive
interconn
ecti
on netwo
rk topolo
g
y. Therefore, this paper
combi
n
es the scalability of the
i
n
terconnection network Torus
wi
t
h
the short
diameter of the
interconn
ecti
on
n
e
two
r
k Octag
on
to
pre
s
ent
a si
mple scalabl
e
O
C
T(
k
,
m
) intercon
ne
ction
netwo
rk
stru
cture. T
h
is i
n
terconn
ectio
n
network
is a kin
d
of regula
r
symm
etrical
exten
s
ibl
e
interconn
ecti
on network with 7 node
s, can exp
and t
he network with the con
s
ta
nt node de
gree
and ma
ke
s t
he ro
uting al
gorithm
simp
le and
efficie
n
t adoptin
g John
son
Cod
e
. Analysis
a
n
d
experim
ent result
s
sho
w
t
he inte
rconn
ection
net
work h
a
s a
goo
d
co
mmuni
cati
on p
e
rfo
r
man
c
e
,
fault toleran
c
e and
scala
b
ility, and it is a kin
d
of in
terco
nne
ction
netwo
rk top
o
logy which i
s
suitabl
e for la
rge scal
e pa
rallel com
putin
g.
Ackn
o
w
l
e
dg
ements
This work
wa
s
sup
ported by the
Natio
nal
Scien
c
e
Fo
undatio
n of
Chi
n
a
(No.6
113
600
2
，
No.612
72
120), the Key
Proje
c
t of Chine
s
e Mini
st
ry of Educati
on (No.21
11
80),
the Natural Scien
c
e Fo
und
ation of Shaa
nx
i Province
of China (No.
2014
JM83
11
).
Referen
ces
[1]
Rinkl
e RA. D
e
sig
n
an
d Re
liab
ilit
y An
al
ys
is of
a Class
of Irregular
Faul
t-toler
ant Multistag
e
Interconnection Net
w
orks.
Internati
ona
l Jour
nal of
Co
mpute
r
Applic
ations
.
201
2; 39(8): 8-
14.
[2]
Liu N, Carot
h
ers C, Cope J
,
et al. Model
and Simu
latio
n
of Exasc
a
le
Communic
a
ti
on Net
w
o
r
ks.
Journ
a
l of Si
mulati
on
. 20
12; 6(4): 227
–2
36.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Topology Architecture and
Routing Algorithm
s
of Octagon-Connect
ed To
rus .... (Youyao Liu)
313
[3]
John S, Su
dip
D, John M. Exascal
e
Com
put
ing T
e
chno
log
y
C
hal
len
ges.
Lecture N
o
tes
in Co
mpute
r
Scienc
e
. 201
1; 6449: 1-2
5
.
[4]
Min X, Yuto
ng
L, Kefei W
,
e
t
al.
T
i
anhe-1A
Interconnecti
o
n
and Mess
ag
e-pass
i
ng S
e
rvices.
IE
EE
Micro
. 201
2; 32(1): 8-20.
[5]
Yuichiro A, T
o
mohiro I, Shin
ya H, et al.
T
he T
o
fu
Interconnect.
IEEE Micr
o
. 2012; 3
2
(1): 21-3
1
.
[6]
Roberto
G.
Towards sustainable
ex
ascale com
p
uting
.
18th IEEE/IF
IP VLSI S
y
ste
m
on C
h
i
p
Confer
ence (V
LSI-SoC). Mad
r
id. 201
0: 270
–
275.
[7]
Sona
l S. Bh
o
p
le, MA Ga
ik
w
a
d. D
e
si
gn
of Mesh
an
d
T
o
rus T
opologi
es for
Net
w
o
r
k-On-Ch
i
p
Appl
icatio
n.
Internati
ona
l Jour
nal of Rec
onf
i
g
urab
le an
d E
m
bed
de
d Systems
. 20
13; 2(2):
76-82.
[8]
Dally
W, T
o
w
l
es B.
Principl
e
s
and Practice
s of Interconn
ection N
e
tw
orks
. San F
r
ancis
co. Morgan
Kaufman
n
Pre
ss. 2004.
[9]
You
y
a
o
L, Ju
nga
ng
H, H
u
i
m
in D.
A
H
y
percu
be-b
a
se
d
Scal
abl
e Int
e
rcon
nectio
n
Net
w
ork
fo
r
Massively
P
a
rallel Computing.
Journa
l of Co
mp
uters
. 200
8;
3(10): 13-1
9
.
[10]
F
ang’
ai
L, Z
h
i
y
o
n
g
L,
Xian
g
z
hen
Q. A Pr
acti
cal
Interco
nnecti
on
Net
w
ork RP(k)
an
d
Its Routi
n
g
Algorit
hms.
Science i
n
Chi
na
Series: Infor
m
a
t
ion Scie
nces
. 200
2; 44(6): 46
1-47
3.
[11]
W
ang L, Che
n
Z
.
Research on Peterse
n
Graphs an
d
H
y
p
e
r-cub
es
Conn
ected Intercon
necti
on
Net
w
orks.
Lec
ture Notes in C
o
mputer Sci
e
n
c
e
. 2006; 4
186
: 495-50
1.
[12]
N Gop
a
lakr
ish
na K, M
Sathi
s
h K, Mruth
yu
nj
a
y
a
HS. T
o
rus Emb
edd
ed
H
y
perc
ube
Intercon
nectio
n
Net
w
ork: A Co
mparativ
e Stud
y.
Internati
o
n
a
l
Journa
l of
Co
mp
uter App
lica
t
ions.
201
0; 1(
4): 29-31.
[13]
Ahmed
L, Ho
n
g
ki S. A Sca
l
a
b
le Optic
a
l
H
y
percu
be
base
d
Interconn
ectio
n
Net
w
o
r
k for
Massivel
y
Parall
el C
o
mp
uting.
Applied Optics.
1994; 3
3
(11): 75
88-
75
98.
[14]
Jose D, Su
dh
akar Y, Lio
n
e
l
N.
Interconn
ection N
e
tw
orks: An Engi
n
eeri
ng Ap
pro
a
c
h
. Morgan
Kaufman
n
. 200
3.
[15]
Don
g
C,
No
el
AE, Phil
ip
H, e
t
al. T
he IBM B
l
ue
Gen
e
/q Int
e
rcon
nectio
n
N
e
t
w
o
r
k F
a
bric.
IEEE Micro
.
201
2; 32(1): 32
-43.
[16]
Steven LS, Gregor
y MT
.
T
h
e
Cray T
3
E Netw
ork: Adaptive
Rout
in
g in a
H
i
gh Perfor
manc
e 3D T
o
rus
.
5th An
nu
al
S
y
mposi
u
m H
i
gh
Performanc
e I
n
tercon
nects (
H
ot Interco
n
n
e
c
ts IV)
.
Stanfor
d U
n
ivers
i
t
y
.
199
6: 147-
156.
[17]
Erno S, Ari K,
T
i
mo DH.
Survey of Netw
ork-on-C
h
ip pr
op
o
s
als
. W
h
ite Pa
per, OCP-IP. 2008: 1-1
3
.
[18]
Mostafa A,T
u
rki F
A
.
T
opolo
g
ic
al Prop
erties
of Hierarc
hica
l
Intercon
necti
on
Net
w
orks: A R
e
vie
w
an
d
Comp
ariso
n
.
Journ
a
l of Electr
ical a
nd
Co
mputer Eng
i
n
eeri
n
g
. 201
1; 201
1: 1-12.
[19]
MM Hafizur
R, Yasush
i I, F
a
iz AF
, et al. S
y
mmetric
an
d
F
o
lde
d
T
o
ri C
onn
ected T
o
ru
s Net
w
ork.
Journ
a
l of Net
w
orks
. 2011; 6(1): 26-35.
[20]
Jain VK, Hor
i
guchi S. V
L
SI
Consi
der
atio
ns
for T
ESH: A Ne
w
Hi
erarch
i
c
al Interc
on
ne
ction
Net
w
ork
for 3-D Integrat
ion.
IEEE Trans on VLSI System
s
. 1
998; 6(
3
)
: 346-35
3.
[21]
Horiguchi S, Ooki T
.
Hierar
c
hical
3D-T
oru
s
Interconn
ecti
on Netw
ork
. Internati
o
n
a
l S
y
mp
osi
u
m on
Parall
el Arch
ite
c
tures, Algorith
m
s
and Net
w
o
r
ks.
T
e
xas, US
A. 2000: 50-
56
.
[22]
Latifah, Er
nas
tuti, Djati K.
Structural P
r
operti
es of
T
o
rus-Butterfl
y
Interconn
ecti
on N
e
t
w
ork.
Internatio
na
l Journ
a
l of
Co
mputer App
lic
ations
. 201
2; 46(
16): 31-3
5
.
[23]
F
a
ra
ydo
n
K, Anh N, Sujit D.
An Interconn
ect Architectur
e
for Net
w
o
r
ki
ng S
y
stems o
n
Chi
p
.
IEEE
Micro
. 200
2; 22(5): 36-4
5
.
[24]
T
ao H, Xin
g
mi
ng Z
,
T
ao Q. Improvin
g
Ne
g
a
tive
F
i
rst
Rou
t
ing A
l
gor
ithm
w
i
t
h
Loa
d E
q
u
a
lizati
o
n
o
f
Virtual
Ch
ann
e
l
in
No
C.
T
E
L
K
OMNIKA Ind
ones
ian
Jo
urn
a
l of E
l
ectric
al
Engi
ne
erin
g.
201
3;
11(
11):
646
0 – 64
67.
Evaluation Warning : The document was created with Spire.PDF for Python.