19
TP CHÍ KHOA HC, ði hc Hu, S 65, 2011
MÔ HÌNH HÀNG ð"I PHÂN TÍCH %NH HƯ'NG C(A S) K*T H"P ð+NH
TUY*N L/CH HƯ0NG VÀ B3 ð/M FDL TRONG GI%I QUY*T T8C
NGH9N TRÊN MNG CHUY;N MCH CHÙM QUANG
ðng Thanh Chương
Trưng ði hc Khoa hc, ði hc Hu
TÓM T8T
Bài toán tc nghn trong mng chuy n mch chùm quang (OBS) ñư(c xem là bài toán
l-n c.n gi/i quyt. S1 tc nghn chùm trong mng OBS có th xu3t hi4n khi hai chùm quang d7
li4u t8 hai c9ng vào khác nhau c; gng ñi ra trên cùng m=t c9ng ra ti cùng m=t thi ñi m. Các
gi/i pháp cho vi4c x? lý tc nghn là: s? dCng ñưng trD quang (FDL); chuy n ñ9i bư-c sóng
và ñInh tuyn l4ch hư-ng. Tuy nhiên, nu ñInh tuyn l4ch hư-ng ñư(c s? dCng, các FDL c.n
thit ñư(c s? dCng ñ bù vào s1 thiu hCt thi gian offset do s1 tăng thêm ñ= dài ñưng ñi l4ch
hư-ng.
Vi4c phân tích ưu, như(c ñi m cOa mPi phương pháp, cũng như kt h(p chúng thưng
ñư(c th1c hi4n qua mô hình hàng ñ(i. Bài báo nhUm ñV xu3t m=t mô hình hàng ñ(i ñ phân tích
vi4c s? dCng kW thuXt ñInh tuyn l4ch hư-ng kt h(p v-i vi4c s? dCng FDL trong gi/i quyt bài
toán tc nghn ñ;i v-i mng OBS. Kt qu/ phân tích cho th3y có s1 c/i thi4n xác su3t tc nghn
so v-i các mô hình ñã ñV xu3t trư-c ñó.
1. Gi?i thiAu
Chuyn mch chùm quang (OBS) trong mng quang WDM ñưc ñ xu!t g"n
ñây ñã ñưc xem là công ngh) ñ"y trin v,ng ñ-i v.i mng Internet th0 h) sau, b4i vì
nó có nhiu li th0 h!p d9n như t-c ñ: nhanh và hi)u su!t băng thông cao hơn nhiu so
v.i chuyn mch kênh quang [1]. Ti nút biên cDa mng OBS, nhEng dE li)u vào
(chFng hn các luHng IP) có cùng ñích ñ0n (và cùng l.p dKch vL QoS) ñưc tNp hp
trong m:t chùm quang dE li)u (data burst), ñưc lNp lKch (scheduling) và ñưc g4i vào
bên trong mng OBS theo sau gói ñiu khin chùm quang (BCP) m:t khoOng thPi gian
offset. KhoOng thPi gian offset này ñưc tính toán sao cho gói ñiu khin có th kKp ñRt
trư.c và c!u hình các tài nguyên ti các nút mà chùm quang dE li)u sS ñi qua. BTng
cách ñó, mng OBS ñã loi bU ñưc yêu c"u c"n sV dLng các vùng ñ)m quang, m:t
trong nhEng hn ch0 mà công ngh) quang hi)n nay chưa th vưt qua ñưc. Ti các nút
lõi bên trong mng OBS, chùm quang ñơn giOn ñưc chuyn mch (forward) theo
hư.ng ñ0n nút ñích như ñã c!u hình. Khi ñ0n nút biên ra, các luHng IP sS ñưc khôi
phLc li tX chùm quang dE li)u này.
20
Do s[ bùng n\ t[ nhiên cDa mng dE li)u, t]c nghSn chùm có th xu!t hi)n khi
hai hoRc nhiu gói ñiu khin c- g]ng dành trư.c m:t kênh bư.c sóng ti cùng m:t thPi
ñim, tX ñó có th gây ra m!t chùm. Vì vNy, v!n ñ giOi quy0t t]c nghSn chùm là r!t
quan tr,ng trong vi)c giOm b.t xác xu!t m!t chùm toàn mng OBS [2]. T]c nghSn
chùm có th ñưc giOi quy0t bTng m:t vài phương pháp, như chuyn ñ\i bư.c sóng, sV
dLng vùng ñ)m dE li)u d[a trên ñưPng tr_ quang (FDL) hoRc ñKnh tuy0n l)ch hư.ng.
M:t phương pháp khác là phân ñon chùm, giOi quy0t t]c nghSn bTng cách chia các
chùm bK t]c nghSn thành các ph"n nhU hơn, g,i là các ñon, sao cho chb m:t vài ñon bK
rơi thay vì toàn b: chùm.
Trong phương pháp ñ"u tiên, chùm bK t]c nghSn ñưc g4i ñi trên bư.c sóng
khác thông qua b: chuyn ñ\i bư.c sóng. V.i phương pháp thc hai, chùm ñưc chuyn
ñ0n m:t ñưPng tr_ FDL, tX ñó có th làm tr_ chùm trong m:t vài ñơn vK thPi gian c-
ñKnh ñ tránh khUi t]c nghSn [4]. ð-i v.i phương pháp ñKnh tuy0n l)ch hư.ng, các
chùm bK t]c nghSn sS ñưc g4i t.i c\ng ra khác cDa nút và sau ñó ñưc ñKnh tuy0n trên
m:t tuy0n khác ññ0n ñích. ðKnh tuy0n l)ch hư.ng là m:t hư.ng giOi quy0t t]c nghSn
ñang thu hút nhiu s[ quan tâm trong mng OBS, b4i vì nó không c"n thêm chi phí v
các thành ph"n vNt lý và sV dLng min ph\ quang sgn có. Tuy nhiên, khi lưu lưng
mng tăng lên, ñKnh tuy0n l)ch hư.ng có th làm giOm hi)u su!t và tính \n ñKnh cDa
mng.
Nhiu phương pháp ñKnh tuy0n l)ch hư.ng ñã ñưc ñ xu!t, như ñKnh tuy0n l)ch
hư.ng sV dLng offset b\ sung và ñKnh tuy0n ñưPng ñi ng]n nh!t [4]. Trong phương
pháp ñKnh tuy0n l)ch hư.ng thông thưPng, chb m:t chùm ñưc chuyn ñi theo tuy0n
ng]n nh!t (tuy0n chính), còn chùm t]c nghSn sS ñưc ñKnh tuy0n l)ch hư.ng sang tuy0n
m.i (tuy0n l)ch hư.ng). Tuy nhiên, khi cO tuy0n l)ch hư.ng m.i cũng không sgn có thì
chùm ñó sS bK hDy.
MRc dù các k0t quO nghiên ccu ñã chcng minh rTng ñKnh tuy0n l)ch hư.ng có
th làm giOm ñáng k vi)c m!t chùm, tuy nhiên, nó cũng làm tăng ñ: tr_ ñ"ulcu-i b4i vì
l: trình l)ch hư.ng thưPng dài hơn l: trình ban ñ"u. Vì vNy, trong mng OBS, thưPng
k0t hp ñKnh tuy0n v.i các phương pháp khác (như truyn li, sV dLng FDL, chuyn ñ\i
bư.c sóng,…). ð phân tích và ñánh giá các lưc ñH ñKnh tuy0n l)ch hư.ng có k0t hp
v.i các phương pháp khác, mô hình lý thuy0t hàng ñi thưPng ñưc sV dLng ñ l[a
ch,n phương án t-i ưu. MLc tiêu cDa bài báo là nghiên ccu v!n ñcng dLng mô hình
hàng ñi Markov ñphân tích và ñánh giá các hư.ng giOi quy0t t]c nghSn trong mng
OBS d[a trên phương pháp chính là ñKnh tuy0n l)ch hư.ng, k0t hp v.i vi)c sV dLng
ñưPng tr_ quang FDL.
N:i dung ti0p theo cDa bài báo bao gHm: ph"n 2 gi.i thi)u mô hình hàng ñi ñ
phân tích ñKnh tuy0n l)ch hư.ng k0t hp v.i sV dLng b: ñ)m FDL; ph"n 3 phân tích k0t
quO v.i m:t s- mô hình khác; và cu-i cùng là ph"n k0t luNn.
21
2. Mô hình hàng ñHi phân tích kM thuNt lAch hư?ng v?i viAc sS dUng ñưVng trX
quang FDL
Mô hình mng OBS ñưc nghiên ccu 4 ñây (hình 1) sV dLng giao thcc báo hi)u
m:t chiu JET và giao thcc lNp lKch tài nguyên LAUC_VF [5]. Gói ñiu khin sS ñưc
g4i trên kênh bư.c sóng ñiu khin tách bi)t và ñưc xV lý (hoàn toàn trong min ñi)n
tV) ti các nút trung gian ñ dành trư.c tài nguyên bư.c sóng cho chùm. Sau khi gói
ñiu khin ñã ñRt trư.c bư.c sóng trên toàn tuy0n tX nguHn ñ0n ñích thì chùm sS ñưc
phát ñi. Vi)c phân tích mô hình mng hàng ñi áp dLng cho ñKnh tuy0n l)ch hư.ng xét
tX nút lõi D.
Hình 1. Mô hình mng OBS
Xét v.i trưPng hp truyn chùm dE li)u giEa cRp nút AlE (hình 1). ðRt H là s-
chRng (hop) tX nút A ñ0n nút E, δ là thPi gian xV lý t-i ña cDa gói ñiu khin ti m|i
chRng. T\ng thPi gian tr_ cDa gói ñiu khin d,c theo ñưPng ñi không l.n hơn giá trK }
= H*δ, vì vNy offset có giá trK t-i thiu là T=}. Trong hình 1, ñưPng ñi ban ñ"u giEa A
và E là AlBlClE. N0u T = 3*δ, chùm sS ñ0n nút E sau khi gói ñiu khin ñã ñưc xV lý.
N0u gói ñiu khin không thành công ñRt trư.c băng thông ti m:t s- chRng trư.c (ví
dL, ti chRng ClE), gói ñiu khin sS không th ñ0n nút E. H) quO là chùm ñ0n nút C sS
bK rơi. Trong trưPng hp này, ñKnh tuy0n l)ch hư.ng có th ñưc sV dLng ti nút bK t]c
nghSn. L: trình l)ch hư.ng giEa nút t]c nghSn C và nút ñích E là ClDlE, vì vNy chùm
sS ñưc ñKnh tuy0n li tX C qua D ñ0n E. Rõ ràng l: trình l)ch hư.ng dài hơn l: trình
ban ñ"u, vì vNy thPi gian offset ban ñ"u sS không ñD ñ có th xV lý vi)c ñRt trư.c tài
nguyên.
Xét trưPng hp chùm bK t]c nghSn ti C và ñưc l)ch hư.ng sang D ñ ñ0n ñích.
ðRt h là s- chRng ñưc thêm vào so v.i l: trình ban ñ"u ñ l)ch hư.ng. N0u offset ban
ñ"u là T = H*δ, và h>0 thì chùm ñưc l)ch hư.ng ñi qua H chRng cDa ñưPng ñi và ñ0n
22
D trư.c khi băng thông giEa D và E ñưc d[ trE. Vì vNy, ñ ngăn trưPng hp chùm bK
rơi, c"n cung c!p thêm m:t thPi gian offset b\ sung bTng h*δ. Trong thPi gian offset m4
r:ng ñó, gói ñiu khin có th ñRt trư.c băng thông trên ñưPng ñi D ñ0n E. Có m:t vài
phương pháp ñã ñưc ñ xu!t ñ giOi quy0t v!n ñ này [4], 4 ñây chúng tôi xem xét
phương pháp sV dLng các ñưPng tr_ quang FDL ti nút ti0p theo nút bK t]c nghSn (ví dL
nút D) ñ bù thêm khoOng thPi gian offset m4 r:ng này (bù s[ thi0u hLt thPi gian offset
do s[ tăng thêm cDa ñ: dài ñưPng ñi l)ch hư.ng) [5].
Trong bài báo này, mô hình ñưc ñxu!t trên cơ s4 cDa các mô hình ñã ñ nghK
trong [4, 5]. Trong ñó, ngoài vi)c sV dLng các FDL ñ bù thPi gian offset tăng thêm do
ñKnh tuy0n l)ch hư.ng, các chùm ñưc l)ch hư.ng cũng sS ñưc c!p phát trên các bư.c
sóng riêng ñ làm giOm t]c nghSn và cOi ti0n hi)u su!t mng. Ngoài ra, các FDL còn li
cũng ñưc sV dLng cho các chùm không l)ch hư.ng ñ làm tr_ chùm n0u có s[ tranh
ch!p bư.c sóng giEa chùm l)ch hư.ng và chùm không l)ch hư.ng.
M:t s- giO thi0t trong mô hình:
l Có ω bư.c sóng trên m|i k0t n-i si quang ra, tương cng m:t tNp Λ = {λ
1
, λ
2
,
… λ
ω
};
l ð: dài chùm ñưc phân b- theo hàm mũ v.i giá trK trung bình L = 1/ˆ; trong
ñó, các chùm ñu ñưc phLc vL v.i t-c ñ: trung bình ˆ.
l S- chRng m4 r:ng trung bình ñ-i v.i các chùm ñưc l)ch hư.ng là h;
l ThPi gian xV lý t-i ña ñ-i v.i gói ñiu khin ti m|i chRng là δ;
l S- FDL ti nút ñang xét là n; trong ñó n
d
FDL ñưc thi0t k0 dành cho các chùm
ñưc l)ch hư.ng trong giai ñon 1, và (n]n
d
) FDL còn li dành cho các chùm 4 giai
ñon 2.
l Có ω bư.c sóng trong b: ñ)m FDL, thPi gian offset m4 r:ng trung bình ñ-i v.i
các chùm l)ch hư.ng, bTng 1/ˆ
d
.δ; do ñó s- FDL /o ñ-i v.i các chùm ñưc l)ch hư.ng
là v
d
= n
d
.ω
l Mô hình ñơn giOn chb xét ti m:t c\ng ra cDa nút OBS v.i chb m:t k0t n-i ra, 4
ñó cO các chùm ñưc l)ch hư.ng và không l)ch hư.ng ñ0n ñu theo phân b- Poisson
v.i t-c ñ: trung bình l"n lưt là λ
d
và λ
f
;
l Lưu lưng ñ0n tương cng là A = a
1
+ a
2
, trong ñó, a
1
= λ
f
/d là lưu lưng tOi
vào chùm không l)ch hư.ng, và a
2
= λ
d
/ˆ là lưu lưng vào cDa chùm ñưc l)ch hư.ng.
l ð duy trì thPi gian offset vXa ñD giEa gói ñiu khin và chùm dE li)u ngay sau
l)ch hư.ng, m|i chùm l)ch hư.ng ñưc làm tr_ trong FDL trư.c khi nó ñưc phLc vL.
l ð: tr_ ñưc cung c!p b4i các FDL ít nh!t bTng thPi gian offset m4 r:ng ñưc
yêu c"u sao cho chùm dE li)u không ñ0n trư.c gói ñiu khin cDa nó. ThPi gian offset
m4 r:ng này có th ñưc tính toán bTng cách xét thêm s- chRng mà chùm phOi ñi qua
23
do l)ch hư.ng.
Mô hình ñưc ñ xu!t 4 ñây là mô hình hàng ñi Markovain M/M/c/c, gHm 3
giai ñon ti m:t nút OBS (hình 2). Giai ñon ñ"u tiên tương cng v.i các ñưPng tr_
quang FDL ñ cung c!p thPi gian offset m4 r:ng cho các chùm ñưc l)ch hư.ng. Giai
ñon thc 2 cng v.i k bư.c sóng (trong s- ω bư.c sóng) trên k0t n-i si quang ra ñưc
ưu tiên c!p phát chb cho các chùm ñưc l)ch hư.ng. Giai ñon thc 3 cng v.i s- bư.c
sóng còn li trên k0t n-i ra (ω]k) ñưc chia s‰ cho các chùm không l)ch hư.ng và các
chùm l)ch hư.ng không thành công tX giai ñon 2 và (n]n
d
).ω FDL “/o”. Ti giai ñon
này, các chùm ñưc l)ch hư.ng tX giai ñon 2 ñưc cho quyn ưu tiên cao hơn so v.i
các chùm không l)ch hư.ng. N0u t!t cO các bư.c sóng ñu bNn, các chùm (l)ch hư.ng
và không l)ch hư.ng) sS ñưc làm tr_ tm thPi b4i (n]n
d
) ñưPng tr FDL còn li.
Hình 2. Mô hình 3 giai ñon cOa node lõi OBS ñang xét
Giai ñon ñ"u tiên là mô hình h) th-ng hàng ñi M/M/v
d
/v
d
ñ-i v.i các chùm
ñưc l)ch hư.ng ñi vào n
d
FDL, trong ñó, D
i
, v.i i = 1, 2,…, v
d
, xác ñKnh FDL thc i
ñưc thi0t k0 cho các chùm l)ch hư.ng, v.i t-c ñ: phLc vL trung bình i
d
= 1/(δ.h), δ là
thPi gian xV lý t-i ña cDa gói ñiu khin ti m:t nút và h là s- chRng trung bình ñưc
c:ng thêm trên l: trình ñ0n ñích. Xác su!t t]c nghSn (PB
1
) ti giai ñon này có th ñưc
tính tX công thcc t\n th!t cDa Erlang (Erlang’s loss formula) [6]:
(
)
( )
∑
=
=
d
d
v
k
k
dd
d
v
dd
k
v
PB
0
1
!//
!//
λ
λ
(1)