TELKOM
NIKA
, Vol. 11, No. 4, April 2013, pp. 1813
~18
2
1
ISSN: 2302-4
046
1813
Re
cei
v
ed
Jan
uary 3, 2013;
Re
vised Feb
r
uar
y 8, 2013;
Acce
pted Fe
brua
ry 20, 20
13
Dynamic Routing and Resource Assignment Algorithm
in Sloted Optical Networks
Bishen
g Qu
an*
1
, Hui Li
2
, Zichun Le
3
1,2,
3
Colle
ge of Scienc
e, Z
heji
ang U
n
ivers
i
t
y
of
T
e
c
hnol
og
y,
288 Li
uh
e Roa
d
, Hangz
ho
u, Chin
a, 31
002
3
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: qbs@zj
u
t.ed
u
.cn
A
b
st
r
a
ct
All-optic
al
w
a
vele
ngth divis
i
o
n
multi
p
l
e
xin
g
net
w
o
rks are
the
most
pro
m
i
s
ing c
a
n
d
id
ate
for th
e
next gen
erati
o
n w
i
deba
nd b
a
ckbo
ne n
e
tw
orks. T
o
impr
ov
e the uti
l
i
z
a
t
ion of w
a
vele
ngth, time divi
si
o
n
mu
ltipl
e
xi
ng te
chno
logy is
int
r
oduc
ed. T
he
routin
g, w
a
vel
ength
and ti
me
-slots assi
gn
me
nt prob
le
m
w
a
s
studie
d
in s
u
c
h
time-sp
a
ce
sw
itched netw
o
rks.
T
w
o new
dyna
mic a
l
gorith
m
s w
e
re
prop
osed w
h
ic
h
distrib
u
te slots
of the sess
ion
requ
est on
mul
t
iple
di
ffere
nt w
a
vel
engt
hs of s
i
ngl
e fib
e
r se
p
a
rately
bas
ed
on
fixed alter
nate
routin
g an
d ad
aptive
ro
utin
g policy. Esp
e
cia
lly in L
L
R-MW
L
B
algor
ith
m
, ne
tw
ork link w
e
ight
s
adj
ust adaptiv
ely w
i
th the availa
bl
e time slots of
each lin
k and lo
ad ba
l
anci
ng strateg
y
is adopte
d
. T
h
e
effectiveness
of
the prop
os
ed alg
o
rith
ms is
de
monstr
ate
d
by
si
mu
latio
n
s a
nd r
e
sults
show
the
b
e
tte
r
perfor
m
a
n
ce.
Ke
y
w
ords
:
W
D
M-T
DM netw
o
rk, RW
T
A
algorith
m
, loa
d
ba
lanci
n
g
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Wavele
ngth-division mult
iplexing (WDM) [1] in
optical net
works is a
preferred
techn
o
logy to exploit the enorm
o
u
s
band
width of
optical fibe
r and it offers
the cap
ability of
building ve
ry large
wide
-a
re
a netwo
rks
wi
th throug
hput
s of the order of gigabits p
e
r sec fo
r ea
ch
node [2,
3]. In traditio
nal
WDM net
works,
whe
n
a
n
e
w
se
ssi
on
reque
st a
rrive
s, a lig
htpath
is
establi
s
h
ed b
e
twee
n the source a
nd th
e de
sti
nation whi
c
h
o
c
cupi
es
the whol
e band
width
of one
wavele
ngth.
Ho
wever,
wit
h
the
ra
pid
progre
s
s i
n
o
p
tical t
r
an
smi
ssi
on te
chn
o
log
y
, the ba
ndwi
d
th
of a single
wa
velength ha
s
rea
c
he
d 40G
bps
whi
c
h fa
r exceed
s the
cap
a
city req
u
i
reme
nt of most
appli
c
ation
s
reque
st. For e
x
ample, HDT
V
works
well
with only 20M
bps.
As wavel
engt
hs a
r
e
key re
sou
r
ces i
n
WDM net
wo
rks, it’s importa
n
t
to better util
ize the
huge
ban
dwi
d
th pe
r wave
length. In o
r
der to
in
cre
a
s
e the
utiliza
t
ion of fiber
band
width, T
D
M
(Time
Divisio
n
Multiplexin
g
) technol
og
y is
introdu
ced into WDM netwo
rks
[4] and su
ch
a
netwo
rk is
called
WDM-T
D
M network
or
WDM
gro
o
m
i
ng netwo
rk
whi
c
h fu
rt
her
divide
s the
band
width of
each
wavel
ength into fixed-len
g
th
time-slots. In
this way, more tha
n
one
su
ccessful co
nne
ction req
uest ar
e
cap
able
of sha
r
i
ng o
ne
wavel
ength
and
bl
ocking
proba
bility
will de
cre
a
se
. WDM-TDM
networks ca
n be cla
s
sifi
e
d
into two types-(i
) dedi
cated-wavele
n
g
th
TDM net
wo
rks and
(ii)
sha
r
ed
-waveleng
th TDM net
works [5]. In the forme
r
, entire wavelengt
h
are de
dicate
d to conn
ecti
on req
u
e
s
ts
betwe
en
spe
c
ific source
-d
estinatio
n pai
rs. Conne
ctio
n
requ
est
s
bet
wee
n
oth
e
r source
-de
s
tina
tion pai
rs
ca
nnot u
s
e
the
s
e
dedi
cate
d
re
so
urce
s a
nd
swit
chin
g is n
o
t perfo
rme
d
in the time
do
main at th
e in
termedi
ate n
ode
s alo
ng th
e ro
uting
pat
h.
In the later, ti
me-slots
withi
n
a wavelen
g
t
h, ra
ther tha
n
the enti
r
e
wavele
ngth,
are
dedi
cated
to
spe
c
ific source-de
s
tinatio
n pai
rs. V
a
ri
ous ot
he
r conne
ction
re
que
sts ca
n sha
r
e
th
e same
wavele
ngth o
n
a lin
k by u
s
ing
different
time-sl
o
ts fo
r information
transmissio
n. The b
and
wi
dth
available in
su
ch n
e
two
r
ks is
used m
o
re effi
ciently than in n
e
tworks which
dedi
cate e
n
t
ire
wavele
ngth
s
betwe
en
spe
c
ific
so
urce
-d
estinatio
n pai
rs. In thi
s
p
aper,
we
onl
y con
s
ide
r
t
he
sha
r
ed
-wavel
ength TDM n
e
tworks.
In WDM
-
T
D
M optical n
e
tworks, the granula
r
it
y of band
width allo
cation i
s
in term
s of
time-sl
o
ts instead of the entire wavel
e
n
g
th band
widt
h. Hence, time-sl
o
ts a
ssi
g
n
ment ha
s to be
determi
ned fo
r a conne
ctio
n req
u
e
s
t, in addition to th
e route a
nd
wavelength. It is called routi
ng,
wavele
ngth
and time-slot
s
assig
n
men
t
(RWTA
)
problem. Like
the routing
and wavelen
g
th
assignm
ent (RWA
) proble
m
, RWTA p
r
o
b
lem can be
cla
ssifie
d
as
static o
r
dyna
mic [6] acco
rding
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 1813 – 1
821
1814
to the traffic model
s. In the former, all
the
traffic req
uest
s
are
kn
own a
d
van
c
e
and the RWTA
deci
s
io
n i
s
m
ade
offline. In
the late
r, the
pro
b
le
m
is to
determine
ro
utes, a
s
sign
wavele
ngth
a
n
d
time-s
lots
for
a s
e
t
of dynamic
tr
affi
c re
q
uest give
n th
e cu
rrent
state of time-slot
allocation in t
he
netwo
rk. T
h
e
dynamic ve
rsion i
s
well a
c
cord
ant wi
th
the most p
r
a
c
tical
data
se
rvice
s
in
WDM-
TDM opti
c
al
netwo
rks.
For dyn
a
mi
c RWTA p
r
o
b
lem, de
sig
n
i
ng a
good
and a
p
p
r
op
ri
ate dynami
c
RWT
A
algorith
m
i
s
critically im
port
ant to imp
r
ov
e the
network perfo
rma
n
ce
. The
de
sign
obje
c
tive of t
h
e
algorithm is t
o
minimize the blocki
ng
probab
ility while maximizi
ng the
bandwidth utilization.
Whe
n
de
sign
ing the algo
rithm, two pri
n
cipl
es mu
st
be abide
d by which cal
l
ed
wa
vele
ng
th
contin
uity co
nstrai
nt
and
t
i
m
e
-slot co
ntinuity
con
s
trai
nt
. For wavel
ength continu
i
ty constraint, a
con
n
e
c
tion
b
e
twee
n two
endp
oints ca
n be
only
se
tup on
on
e
wavele
ngth,
and
wavel
e
n
g
th
conve
r
si
on i
s
not allowed
at the intermediat
e n
o
d
e
s al
ong the
routing
path
.
For time-sl
o
t
contin
uity co
nstrai
nt, slot
interchan
gin
g
is n
o
t allo
wed
at the i
n
terme
d
iate
node
s al
ong
the
routing p
a
th.
In this paper,
we will
concentrate on the
RW
TA problem. The netwo
rk manager
runs the
RWTA algo
ri
thm to esta
blish a lig
htpath fo
r session
requ
est
s
. If a lightpath can n
o
t be
establi
s
h
ed, the req
u
e
s
t is blocked o
r
reje
cte
d
. Com
pare
d
to the RWTA probl
em, the RWA
probl
em ha
s been well ad
dre
s
sed in wavelength
-
ro
u
t
ed (WR) opt
ical networks. Referen
c
e [
7
]
comp
re
hen
si
vely
reviewe
d
the pro
p
o
s
ed RWA app
ro
a
c
he
s. De
spite
of
that, some re
sea
r
ches
have be
en
co
ndu
cted in th
e are
a
of find
ing effi
cie
n
t a
l
gorithm
s for
RWTA proble
m
. In 2002, B
o
Wen a
nd Kri
s
hn
a M. Sivalingam first
pre
s
ent
e
d
RWTA con
c
ep
t and pro
p
o
s
ed a sch
e
me
to
divide RWT
A
proble
m
into three
su
b pro
b
lem
s
whi
c
h a
r
e routing p
r
obl
em, wavele
n
g
th
assignm
ent probl
em and
slots allo
cat
i
on pro
b
lem
[6]. Then they improved
the sch
eme
for
routing
probl
em in m
u
ltip
le fiber
optical
networks
and p
r
o
p
o
s
e
d
two
wavel
ength a
nd
sl
ot
assignm
ent p
o
licie
s [8]. In the same ye
ar, seve
ral a
daptive routin
g and re
so
urce
s assig
n
m
ent
algorith
m
s
were di
scu
s
se
d [9] which u
s
ed multi path
s
for o
ne
se
ssion
req
u
e
s
t. These alg
o
rit
h
ms
above all are based on mul
t
i fibers
optical netwo
rks. In [10], t
he authors re
port a
dynamic
RWTA
algorithm wit
h
compl
e
te switchi
ng capability in
time d
o
main. But for recent WDM-T
D
M networks
the routing n
ode
s without
wavelength
conve
r
ters
a
nd time slots interch
ang
ers may be more
appli
c
able. I
n
literatu
r
e [
11, 12], dyn
a
mic
RWTA
schem
es h
a
ve bee
n p
r
opo
sed fo
r
ring
netwo
rks, tho
ugh the
r
e i
s
need to
re
se
arch the
RWTA probl
em i
n
the me
sh
WDM-T
D
M o
p
tical
netwo
rks. Re
feren
c
e [13]
has p
r
op
osed
dy
namic Mo
st-u
sed Ba
se
d (MUB
) and
enhan
ce
d MUB
(EMUB)
algo
rithms to a
d
d
r
ess
RWTA issue in
me
sh
WDM
-
T
D
M
optical n
e
two
r
k, but a
s
sign
ed
slots a
r
e only
distribute
d
o
n
one si
ngle
wavele
ngth.
Different fro
m
the objecti
ve of minimizing
the blocki
ng
probability ab
ove, reference [14]
has proposed
a RWTA re
assi
gnment algorit
h
m
with the purp
o
se of maxim
i
zing the time
of first blocki
ng.
In this pa
per,
we p
r
op
osed
two ne
w dyn
a
m
ic RWTA
al
gorithm
s to m
i
nimize th
e bl
ocking
prob
ability. Base
d on m
e
sh
WDM-T
D
M optical
ne
tworks with
singl
e fiber
and a
b
ide
d
by
wavele
ngth a
nd time-slot continuity con
s
traint,
the
s
e
two algorith
m
s ado
pt mu
ltiple wavelen
g
th
distrib
u
ted sl
ot assi
gnme
n
t
policy. In th
e fist al
gorith
m
, fixed alternate routin
g policy is u
s
e
d
.
We
calle
d it as M
U
MD
(Mo
s
t Used
ba
sed a
n
d
Multi-wa
vel
ength
Distri
b
u
ted ba
sed
)
algorith
m
. In the
se
con
d
alg
o
ri
thms, lea
s
t lo
aded
(me
a
n
s
most avail
a
b
l
e slot
s)
routi
ng poli
c
y is
u
s
ed
and
assi
gns
slots
with l
o
ad bal
an
cing
. We
calle
d
it as L
L
R-MWLB
(Le
a
s
t Loa
ded
Route
d
, Mult
iple
Wavele
ngth
s
distrib
u
ted
with Loa
d Balan
c
ing
b
a
sed) al
gorith
m
. The exp
e
rime
ntal re
sults
sho
w
e
d
that the two algo
rithms outp
e
rf
orm the exist
i
ng algo
rithm
s
―
RA
ND
O
M
, FIRST-FI
T,
EMUB in terms of blocking probability. And
LLR-M
WLB algorithm
has
the best
performance.
2. Definition
s
In this secti
on, network
model a
nd t
r
affic mo
del
are d
e
fined.
We al
so
gi
ve some
mathemati
c
d
e
finitions.
2.1. Net
w
o
r
k
Model
The net
wo
rk
topology i
s
repr
e
s
e
n
ted a
s
an
undi
re
cted graph
G (V, E)
, con
s
isting of
|V|=
n
no
de
s
and
|E|=
m
li
nks inte
rcon
nectin
g
the
n
ode
s. We
co
nsid
er
a
sing
le fiber n
e
twork
con
s
i
s
ting of
|W|
wavele
ngt
hs where
W= {w
1
, w
2
, …w
|W
|
}
. Each
wa
velength is di
vided into fixed-
length T
D
M f
r
ame
s
com
p
ose
d
of a
fixed n
u
mbe
r
o
f
time slot
s
whi
c
h
are
de
noted
by
T= {t
1
,
t
2
,…t
|T|
}
and
|T|
represen
ts the nu
mbe
r
of time
slots
of ea
ch
wa
velength
cap
a
city. Whe
n
a
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Dynam
ic Routing and Resource Assignm
ent Algor
ithm
in Sloted O
p
tical...(Bisheng Quan)
1815
se
ssi
on a
rriv
e
s, on
e route
will be
sele
cted and
so
m
e
slot
s
will b
e
assig
ned f
o
r the
se
ssio
n to
establi
s
h a lig
htpath. If enough re
so
urce
s we
re
not av
ailable, the session i
s
blo
c
ked.
2.2. Traffic M
odel
Several traffi
c mod
e
ls
ha
ve been
con
s
ide
r
ed fo
r the RWA pro
b
lem. Typical
l
y, three
types of session req
u
e
s
ts are ap
plied
whi
c
h are
static traffic, dynamic traffic and increme
n
tal
traffic. All session requ
est
s
are kn
own in
advance fo
r s
t
atic
traffic
.
For inc
r
emental traffic
model
,
the sessio
n reque
sts arriv
e
sequ
entially, and
esta
blished li
ghtpath
will remai
n
s i
ndefinitely in
the
netwo
rk. Fo
r
dynamic traffic mod
e
l, the se
ssi
on a
rriv
e
s at a rand
o
m
time and l
a
sts fo
r a fini
te
rand
om time.
In our alg
o
rit
h
m, we
con
s
i
der the dyn
a
m
ic ra
ndo
m traffic mod
e
l. A conn
ectio
n
requ
est
r
i
is rep
r
e
s
ente
d
by a tu
ple
)
,
,
,
,
(
i
i
i
i
i
D
t
d
s
, where
V
s
i
is the
source,
V
d
i
is the
destin
a
tion,
t
i
is
the arriving time,
∆
i
is th
e hol
ding
tim
e
an
d
D
i
i
s
re
quire
d b
and
width represent
ed
as the num
be
r of time-sl
o
ts. We use the
assu
mptio
n
s
followe
d for the dynami
c
traffic model:
(i). Se
ssi
on
reque
sts arriv
e
a
c
cordi
ng
to the
P
o
ssi
on
pr
oc
es
s
w
i
th
th
e r
a
te
λ
. The
holdin
g
time of each
se
ssi
on req
u
e
s
t obeys a
neg
ative exponenti
a
l distrib
u
tion
with a mean
1/
μ
.
The holdi
ng time is ind
epe
ndent of ea
ch other a
nd the arrival time. The netwo
rk lo
ad is d
e
fined
as
λ
/
μ
(erla
n
g
)
.
(ii). Th
e requi
red
ban
dwi
d
th of ea
ch
se
ssi
on i
s
u
n
ifo
r
mly ra
ndo
m
distrib
u
ted i
n
[
1, |T|
],
so we co
nsi
d
er multi-rate session.
(iii). If lightpath can not
be establi
s
hed fo
r a
session, the
se
ssi
on i
s
blocked and
discarded fro
m
the netwo
rk.
2.3. Mathem
atic De
finitio
n
s
Similar to
the
RWA
proble
m
, app
roa
c
h
e
s
to
ad
dre
s
s RWTA
p
r
obl
e
m
can be cla
ssifie
d
in
to two
categ
o
rie
s
: combi
ned a
p
p
r
oa
ches and
di
sj
oint app
ro
aches.
Di
sjoint
app
roa
c
h
e
s are
popul
ar i
n
the
literatu
r
e
s
. Usually
disjoi
nt app
roa
c
h
e
s
are to
divide
the
RWTA
pro
b
lem into
thre
e
sub
p
ro
blem
s:
routin
g
sub
p
r
oble
m
, wave
length
assi
gn
ment subp
ro
b
l
em an
d time
slot a
s
signm
e
n
t
sub
p
ro
blem.
For
ro
uting sub
p
ro
blem, we
choo
se
K
shorte
st routing poli
c
y and network wei
ghts
cha
nge
ada
p
t
ively with th
e total n
u
mb
er of
ava
ilabl
e time-slot
s
on the
links.
To detail
the
link
weig
ht functio
n
, we state th
e followin
g
mathematic d
e
scription
s
.
Define
)
,
,
(
t
w
l
S
as t
he
state of t
he
slot
t
in
wavele
ngth
w
on link
l
.
1
)
,
,
(
t
w
l
S
mean
s slot is
available an
d
0
)
,
,
(
t
w
l
S
means
slot is occu
pied.
Define
)
,
,
(
t
w
p
S
as th
e combi
ned
state of
the
slot
t
i
n
wav
e
length
w
al
ong
path
p
.
1
)
,
,
(
t
w
p
S
mean
s slot
i
s
avail
able
a
nd
0
)
,
,
(
t
w
p
S
mean
s sl
ot is
occu
pie
d
.
)
,
,
(
t
w
p
S
is
given by Equation (1
).
)
,
,
(
)
,
,
(
)
,
,
(
)
,
,
(
|
|
2
1
t
w
l
S
t
w
l
S
t
w
l
S
t
w
p
S
p
(1)
Define
t
t
w
l
S
w
l
C
)
,
,
(
)
,
(
as th
e total num
be
r of the avail
a
ble sl
ots fo
r
wavele
ngth
w
on lin
k
l
.
Define
t
t
w
p
S
w
p
C
)
,
,
(
)
,
(
as the total nu
mber of th
e available
slots for
wavele
ngth
w
along path
p
.
The link
weig
ht function is
given by Equation (2
):
w
w
l
C
W
T
l
C
)
,
(
|
|
|
|
)
(
(2)
Whe
r
e
|T|
de
notes th
e nu
mber of time
-slots fo
r ea
ch wavele
ngth
and |W| de
n
o
tes the
numbe
r of wa
velength
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 1813 – 1
821
1816
The choi
ce o
f
weight fun
c
tion makes a
signifi
cant di
fference in th
e cal
c
ulatio
n
of the
optimal path.
These links with
more available time-slots
alwa
ys
have more probability to be
sele
cted i
n
to
the ro
ute. T
hus th
e n
e
w se
ssi
on
req
uest ten
d
s to
avoid the
b
u
sie
r
lin
ks. As a
result, the load of the whol
e netwo
rk i
s
balan
ce
d and
the proba
bility of blockin
g
decrea
s
e
s
.
3. Rese
arch
Metho
d
In this pa
pe
r, two dyn
a
m
ic
RWTA
algorith
m
s
called M
U
M
D
and L
L
R-M
W
LB a
r
e
prop
osed, which h
a
ve th
e sam
e
idea
that time
slots may be
distrib
u
ted o
n
multiple dif
f
erent
wavele
ngth
s
.
3.1. MUMD
Algorithm.
In the M
U
MD algo
rithm, we choo
se th
e
fi
xed alterna
t
e routin
g for routin
g
sub
p
r
oble
m
.
For wavelen
g
th assignm
ent subp
ro
b
l
em, the
algorithm may select m
u
ltiple different
wavele
ngth
s
based on m
o
st used ap
proa
ch. And
slots m
a
y also be di
stri
b
u
ted on diffe
rent
wavele
ngth
s
based on mo
st use
d
app
ro
ach.
The p
s
eud
o-cod
e
of MUMD algo
rith
m is
sh
own
in Figure 1
,
mainly including the
f
o
llowin
g
st
ep
s:
Figure 1. Pse
udo Code of
MUM
D
Algori
t
hm
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Dynam
ic Routing and Resource Assignm
ent Algor
ithm
in Sloted O
p
tical...(Bisheng Quan)
1817
Step one: Select the
rou
t
e. Che
ck th
e rout
e from
the first ava
ilable route
of the
K
alternate
rout
es
set. If
C (
p
i
, w)
≥
n
, ch
oose
p
i
as
p
and
go to
the
next ste
p
. O
r
the
sessio
n
is
blocke
d.
Step two: L
o
o
k
for the
avail
able
wavele
n
g
th of
p
. If
C(p,w
)
>
0
, put
w
to the
set
W
and so
rt
set
W
a
c
cord
ing to
UR
_W
i
n
d
e
scendin
g
o
r
de
r wh
ere
UR
_W
de
n
o
tes
th
e
us
e-
ra
te
o
f
wavelengths
. If
set
W
i
s
empty, the se
ssi
on i
s
blocke
d.
setW
represe
n
ts the avai
lable
wavelengths
s
e
t.
Step three:
Assign
wa
velength an
d time-sl
o
t. Choo
se wavelength from
set
W
seq
uentially. Add the available slot
s to
set
T
and
sort
set
T
in descen
ding o
r
de
r acco
rding t
o
UR
_T
wh
ere
UR_T
denote the use
-rat
e
of time-slot
s
. If th
e number of availa
ble slots i
s
more
than
n
,
s
e
lec
t
the firs
t
n
sl
ot
s
in
set
T
a
nd a
s
signm
e
n
t ha
s be
en f
i
nish
ed. Oth
e
r
wi
se,
cho
o
se all
the slots in
se
t
T
and go to next wavelen
g
th in
set
W
.
Step four: If the numb
e
r of assigne
d
slots i
s
le
ss than
n
after che
c
ked t
he entire
wavele
ngth in
set
W
, the se
ssi
on is bl
ocked. Otherwise, light
path is succe
s
sfully establi
s
h
ed.
3.2. LLR-M
WLB Algori
th
m
The p
s
e
udo
-cod
e of L
L
R-MWLB
algo
rithm is sh
own
in Figu
re
2. a
nd Fig
u
re
3.
Figure 2
sho
w
s the
p
s
eu
do-co
de
of ro
uting
p
o
licy a
nd
Fi
gure
3
sho
w
s the
p
s
eu
do-cod
e
of
the
assignm
ent p
o
licy of wavel
ength an
d slo
t
s.
The followi
ng step
s can
be ab
stra
cted
:
Step one:
Update all li
nk weig
hts of t
he net
wo
rk
a
c
cordi
ng to t
he form
ula
1
. Find
K
alternate rout
es set
P=
{
p
1
,
p
2
, …,
p
K
} based o
n
the
K
sh
orte
st routing
policy and so
rt th
em
ascen
d
ingly b
y
C(p
i
)
w
h
er
e
l
i
l
C
p
C
)
(
)
(
denotes the
total weight o
f
path
p
i
.
Step two: Decide the ro
ute
.
From
the first available route of set
P
, where cu
rre
n
t
route is
p
i
,
se
ar
ch
setW
b
a
sed
on
the
wavele
ngt
h continuity
constraint. Th
e
n
sea
r
ch avai
lable tim
e
-slo
ts
set
s
in
set
W
and calculate
the amount
of t
he total available sl
ots
in
set
W
whi
c
h is
T
p
. If
T
p
≥
D
,
cho
o
s
e
p
i
as
p and
go
to t
he next
step.
Or a
nalyze th
e next route i
n
set
P
until fi
nd an
availa
b
l
e
route. If no available route i
n
P
, the sessi
on is blo
c
ked.
Figure 2. Pse
udo-co
de of Routin
g Policy for LLR-M
WLB Algorith
m
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 1813 – 1
821
1818
Figure 3. Pse
udo-co
de of
Slots Assi
gn
ment Policy for LL
R-M
W
L
B
Algorithm
Step three: Assi
gn wavele
ngths a
nd time slots
combi
nedly. Path
p
has be
en sel
e
cted in
step two. Available
wav
e
length
set
set
W
and
a
v
ailable time
-slot
s
set
{se
t
T
i
}
have b
e
en
cal
c
ulate
d
. No
w ran
k
setW
de
scen
dingly by the amount o
f
available slots a
nd d
e
lete
wavele
ngth
s
with
zero
ava
ilable slots. Define
m=
|s
e
t
W
|
which de
n
o
tes th
e amo
unt of availa
b
l
e
wavele
ngth
s
in path
p
. Then
{setT
i
}
wh
er
e
i=1~m
deno
tes the availa
ble time-slots set and d
e
fin
e
D
i
wh
ere
i=
1~m
as available slots fo
r ea
ch availa
ble
wavele
ngth. (i) If
T
p
= D
, assign all availa
ble
slot
s
in
set
W
for the
s
e
ss
ion reques
t; (ii) If
T
p
>D
and
T
p
≤α
D
, wh
ere
α
i
s
a
co
nst
a
nt, assig
n
th
e
firs
t D
s
l
ots
in
{setT
i
}
to the sessio
n reque
st; (iii) If
T
p
>
α
D
, define
]
[
1
'
1
D
D
where
β
is a
constant, and [•] calculates a in
teger not more than the num
ber
filli
ng in the
br
ackets. Choose
D
s
l
ots in the firs
t wavelength of
set
W
for the
se
ssi
on i
f
D
D
'
1
; Or
c
h
oose
'
1
D
s
l
ots
in the
firs
t
wavele
ngth of
set
W
f
o
r
the se
ssion
and a
s
sign
slots f
r
om th
e next wave
length in
set
W
seq
uentially. In this ca
se, the se
ssion i
s
blocke
d if
'
1
2
D
D
D
m
i
i
.
Step four: Up
date the network
state
s
an
d wait a ne
w se
ssi
on re
qu
est.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Dynam
ic Routing and Resource Assignm
ent Algor
ithm
in Sloted O
p
tical...(Bisheng Quan)
1819
3.3. An Exa
m
ple for the
Proposed
Algorithms
Give a netwo
rk
with 5 no
d
e
s an
d 6 lin
ks. Give 3 session
req
u
e
s
ts from nod
e 1
to node
5: Sessio
n
A need
s 2 slot
s, session B need
s 3 sl
ots
and se
ssion
C need
s 4 sl
ots. The se
ssions
arrive
d at nod
e 1 seq
uentia
lly. Given an
assumptio
n
o
f
|W|
=
2
,
|T|
=
4
,
K=
1
.
Figure 4 sho
w
s th
e re
sult
of slots a
s
si
gnment
by M
U
MD
algo
rith
m. It shows that, the
same
route (1, 3, 5) is sel
e
cted fo
r all three
se
ssi
on
s and
se
ssi
on
C is blo
c
ked.
Figure 5 sh
o
w
s the result of routing a
nd sl
ot
s assi
gnment by L
L
R-MWLB algorithm. It
sho
w
s that, t
he
same
rout
e (1,
3, 5
)
i
s
sele
cted
for
session
s
A
an
d B an
d
rout
e (1,
2, 4, 5
)
for
se
ssi
on C b
e
c
au
se of the
variable lin
k
weig
ht.
Figure 4. An Example of MUMD Alg
o
rith
m
Figure 5. An Example of LLR-MWLB Algorithm
4. Results a
nd Analy
s
is
Simulation
s have bee
n p
e
rform
ed o
n
NSFNET
with 14-node
s
and 21
-lin
ks.
And we
assume
that i
n
the n
e
two
r
k each lin
k i
s
consi
s
ti
ng
of a
pair
of an
op
posite
one
-way fiber a
n
d
h
a
s
t
he sa
me
ca
pacit
y
.
I
n
t
h
e
simul
a
t
i
on
s,
se
ssi
on
r
e
qu
e
s
ts
ar
r
i
ve
a
t
th
e
n
e
tw
or
k
a
c
c
o
r
d
ing to
Poisson
pro
c
ess with
rate
λ
and th
e h
o
lding time
of
a sessio
n is expone
ntiall
y distrib
u
ted
with
mean
1/
μ
. And
K
-sh
o
rte
s
t path algo
rith
m is used to cal
c
ulate alte
rnate path
s
,
whe
r
e
K
is 2.
4.1. Optimal Combination of
α
and
β
We have p
e
rformed a
sim
u
lation to find the optimal
combin
ation
of
α
and
β
. Figure
6
sho
w
s the bl
ocking p
r
ob
a
b
ility under th
e ca
se of |
W|
=16 a
nd
|T|
=16, and net
w
ork l
oad i
s
10
0 in
erlan
g
s. We find the be
st perform
an
ce while
α
= 2 an
d
β
= 1
.
4.2. Perform
ance o
f
Algo
rithms
We
evaluate
the pe
rform
ances
of M
U
MD a
n
d L
L
R-MWLB alg
o
rithm in terms of the
overall average blocking
probability which i
s
de
fined as a
ratio of the number
of blocked
se
ssi
on
s t
o
t
he n
u
mbe
r
of
t
o
t
a
l ar
riv
e
d
se
ssi
on
s. We
com
p
a
r
e
our algo
rithm
s
with RANDO
M
,
FIRST-FIT, EMUB algo
rith
m.
Figure 7
plot
s the
averag
e blo
cki
ng
probability un
d
e
r the
case
of
|W|
=1
6 an
d
|T|
=16.
Simulation re
sults
sh
ow th
at the MUM
D
and LL
R-M
W
LB poli
c
ie
s perfo
r
m mu
ch better tha
n
th
e
other th
re
e p
o
licie
s a
nd th
e later ha
s th
e be
st pe
rformance that i
n
crea
se
s by
1 to 3
orders of
magnitud
e
. T
w
o
re
ason
s
contribute
to t
he g
ood
resul
t
s. First,
K
-sh
o
rtest
alterna
t
e ro
uting
poli
cy
based o
n
ad
aptive link
weights te
nd
s
to con
d
u
c
e t
hat se
ssion
s
are
route
d
to
those
path
with
more availabl
e
time-slots. Thus se
ssion
load
s
w
ill b
e
well-pro
p
o
r
tionally dist
rib
u
ted in the li
nks
of the network and a n
e
w
se
ssi
on will h
a
ve more
cha
n
ce to be tra
n
s
ferred
su
cce
ssfully. Seco
nd,
slots in multip
le different wavelength
s
are assi
gn
ed to
the sessio
n and the a
ssi
g
n
ing alg
o
rith
m is
adaptive
with
the rem
a
ind
e
r resou
r
ce
s
of the network
. The
r
efo
r
e,
the ca
pa
city of wavele
ngt
hs i
s
fully utilized, which tends to
leave more avail
a
ble wavelengt
hs and slot
s to accept the
sub
s
e
que
nt session requ
e
s
ts.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 1813 – 1
821
1820
Figure 6. Optimal Com
b
ina
t
ion of
α
and
β
Figure 7. The Blocking Probability Versus the
Network Loa
d (In erla
ng
s)
Figure 8. The Blocking Probability Versus the
Numb
er of Wavelength
Figure 9. The Blocking Probability Versus the
Numb
er of Ti
me-slots p
e
r
Wavele
ngth
The sim
u
lati
on also pe
rform
s
the im
pact of
|W|
on the network bl
ocking probability.
Figure 8
shows the blocki
ng probab
ility of the four RWTA algori
thms versus |W
|, when the
netwo
rk l
oad
is fixed at 12
0 and
|T|
is 1
6
. The re
sult
s sh
ow th
at with the incre
a
sin
g
of
|W
|, the
blockin
g
pe
rf
orma
nce of
both five alg
o
rithm
s
is
en
han
ced. T
h
is is b
e
cau
s
e
the ca
pa
city of
netwo
rk enl
arges with
the increa
sing
of
|W|
. Cle
a
rly,
our alg
o
rith
ms p
e
rfo
r
m
much
bette
r t
han
other alg
o
rith
ms and L
L
R-MWLB alg
o
rit
h
m doe
s the best.
The imp
a
ct
of
|T|
on the network blocki
ng probability is shown in Figure 9.
When
netwo
rk lo
ad
is fixed at 12
0 and
|W|
is 1
6
, the blockin
g
perfo
rman
ce is slig
htly improve
d
with
the
increa
sing
of
|T|
. As the rate of sessio
ns is u
n
iformly
random
di
strib
u
ted in [1,
|T|
], the avera
g
e
rate of
se
ssio
ns in
crea
se
s
whe
n
|T|
in
creases. So
th
e pe
rform
a
n
c
e is
not o
b
viously im
prov
ed.
Clea
rly, our a
l
gorithm
s al
so perfo
rm the
best.
5. Conclusio
n
TDM te
chn
o
l
ogy is con
s
i
dere
d
to imp
r
ov
e the
wav
e
length
cap
a
c
ity utilizatio
n of All
-
optical
WDM
networks. In this pap
er, we st
udy the routing,
wavele
ngth
and time-slot
s
assignm
ent p
r
oble
m
in such time-spa
ce
swit
ch
e
d
net
works. Two n
e
w dyna
mic a
l
gorithm
s call
ed
MUM
D
an
d LLR-M
WLB are pro
p
o
s
ed
whi
c
h ca
n distrib
u
te slot
s
of
the se
ssion re
que
st
on
multiple diffe
rent
wavele
n
g
ths. In M
U
MD al
gorith
m
, fixed altern
ate ro
uting p
o
licy is u
s
ed.
In
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Dynam
ic Routing and Resource Assignm
ent Algor
ithm
in Sloted O
p
tical...(Bisheng Quan)
1821
LLR-M
WLB a
l
gorithm, net
work lin
k
wei
ghts vary a
d
a
p
tively with the numb
e
r of
available
slot
s on
the link an
d this poli
c
y dist
ribute
s
slot
s
of the se
ssio
n requ
est o
n
multiple different wavele
ng
ths
adaptively wi
th the remai
nder resou
r
ce of t
he network. Simula
tion results sho
w
that the
perfo
rman
ce
s of ou
r al
gori
t
hms a
r
e
mu
ch
bette
r th
a
n
RA
NDOM,
FIRST-FIT, E
M
UB al
gorith
m
and LL
R-MWLB performs t
he be
st.
Ackn
o
w
l
e
dg
ements
This
wo
rk
wa
s finan
cially
sup
porte
d by
Nation
al Natural S
c
ien
c
e
Found
ation o
f
Chin
a
(611
720
81),
Zhejia
ng P
r
ovinci
al
Nat
u
ral S
c
ien
c
e
Foun
dation
of China
(Y111
092
3
and
Y11110
24
).
Referen
ces
[1]
Gree P E, Jr.
Optica
l Net
w
or
king
Up
date.
I
EEE Jour
nal on Selected
Areas in Comm
unications
. 19
96
;
14(5): 76
4-7
7
9
.
[2]
Ramas
w
a
m
i R,
Sivaraj
an KN.
Optical
Networks: A Practical Perspective
. Los
Altos: Morgan
Kaufman
n
Pub
lishers. 1
998.
[3]
Optimizatio
n
o
f
point-to-p
o
i
n
t transmissi
on
and
inv
e
stig
ation
of o
p
tic
a
l time-
doma
i
n multi
p
le
xe
d
(OT
D
M) routing for all-optic
a
l net
w
orks
at si
ngl
e c
han
nel
data
rates
of 1
60Gb/s
and
hi
ghter
.
Europ
e
a
n
Com
m
ission
un
der t
he IST
-
2000-2
876
5 pro
j
ect F
ASHIN: Ultrafa
st S
w
itch
in
g in
High-S
p
e
e
d
OT
DM Net
w
or
ks. 2003.
[4]
Nen F
u
Hu
ang
, Guan Hsiun
g
Lia
w
, Ch
uan
P
w
u W
a
ng. A Novel Al
lo
ptica
l
T
r
ansport Net
w
ork
w
i
t
h
T
i
me-shared W
a
vele
ngth C
han
nels.
IEEE Journal on S
e
lected
Areas
in Comm
unic
ations
. 20
00
;
18(1
0
): 186
3–1
875.
[5]
Yates J, Lacey
J, Everitt D.
Blocki
ng
in
Multiw
avel
engt
h T
D
M N
e
tw
orks. Procee
din
g
s of th
e
4t
h
Internatio
na
l
C
onfere
n
ce on T
e
leco
mmuni
c
a
tion, Syste
m
,
Mode
lin
g a
n
d
Analys
is
. Nas
h
vill
e. 1
9
9
6
:
535-
541.
[6]
Bo W
en, KM Sivali
ngam.
Routi
ng, W
a
vele
ngth a
nd
T
i
me-S
lot Ass
i
gn
ment in T
i
me D
i
visi
o
n
Multipl
e
xe
d W
a
vel
engt
h-Ro
uted Optical W
D
M Netw
orks
. P
r
oc. IEEE INFOCOM. Ne
w
Y
o
rk. 2002; 3
:
144
2-14
50.
[7]
H Z
hang, JP Jue, B Mukherj
ee. A Revie
w
of
Routin
g an
d
W
a
velen
g
th Assignm
ent App
r
oach
e
s fo
r
W
a
vele
ngth R
outed Optic
a
l
W
D
M Net
w
o
r
k
s
.
Optical Netw
orks Maga
z
i
ne
.
2000; 1(1): 4
7
-
60.
[8]
W
en B, She
n
a
i
R, Siva
li
nga
m K. Routi
ng,
W
a
vele
ngth
an
d T
i
me-Slot A
ssignm
ent for
W
a
vele
ngth-
routed Optica
l W
D
M/T
D
M Netw
o
r
ks.
Journ
a
l
of Lightw
a
ve T
e
chn
o
l
. 20
05; 23(9): 25
98-
26
09.
[9]
Pei
y
u
an Le
e, Yongta
o
Go
ng,
W
a
n
y
i
Gu. Ad
aptive
Ro
utin
g
and
Res
ourc
e
Assign
ment i
n
W
D
M-T
DM
Networks with
Multi-rate Sessions
. Proce
edi
ngs of SPIE. Belli
ng
ham. 20
0
5
; 5626: 5
93-6
01.
[10]
Vish
w
a
nn
ath A
,
Lian
g W
.
On-line
Routi
ng
i
n
WDM-T
DM
S
w
itc
h
e
d
Optic
a
l Mesh
Net
w
orks.
Photon
Netw
ork Commu
n
ic
ation.
2
0
05; 12(1
1
): 287
-299.
[11]
W Yang, SA P
a
redes,
T
r
evor J Hall. A Study
of Fast Flex
ible Band
w
i
dth
Assignm
ent Methods and
their Bl
ocki
ng
Proba
bil
i
ties fo
r Metro Ag
ile
All-optic
al
Rin
g
Net
w
orks.
IEE
E
Internati
ona
l
Confer
enc
e
on Co
mmunic
a
tions.
Glasgo
w. 2007; 24-
28: 241
8-24
23.
[12]
W
Yang, T
r
evor J Hall.
Dist
r
ibute
d
Dyna
mic Routi
ng, W
a
vel
engt
h and
T
i
mesl
ot assi
gn
me
nt for
Bandw
idth
o
n
De
ma
nd i
n
A
g
ile
all-
optic
al N
e
tw
orks
. 2006
Can
adi
an
Co
nferenc
e o
n
El
e
c
trical a
n
d
Computer Engineer
ing (CCECE
06). Ottaw
a
. 2006: 136-
139.
[13]
Peng
Xi
an
g, Ron
g
W
ang.
Stud
y
on D
y
n
a
mic Ro
uting,
W
a
velen
g
th and times
l
ot Assignm
e
n
t
Algorit
hm i
n
WDM-T
D
M Optical
Net
w
o
r
k
s
.
Journ
a
l of Electron
ics
& Information
T
e
chno
logy
. (In
chin
ese). 20
09
; 31(3): 679-6
8
3
.
[14]
P Rajal
a
kshm
i
, A Jhunjhu
n
w
ala. Ro
uting
W
a
ve
le
ngth a
nd T
i
me-slot Reassi
gnm
ent
Algorithms for
T
D
M based Optical W
D
M Netw
o
r
ks.
Co
mp
uter Co
mmu
n
icat
ions
. 20
07; 30(
18): 349
1–
349
7.
Evaluation Warning : The document was created with Spire.PDF for Python.