Mô hình hàng đợi phân tích ảnh hưởng định tuyến lệch hướng và bộ đệm FDL giải quyết tắc nghẽn mạng chuyển mạch chùm quang: Báo cáo nghiên cứu khoa học

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.

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.

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

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 Λ = {λ

, λ

… λ

};

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

FDL ñưc thi0t k0 dành cho các chùm

ñưc l)ch hư.ng trong giai ñon 1, và (n]n

) 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/ˆ

.δ; do ñó s- FDL /o ñ-i v.i các chùm ñưc l)ch hư.ng

là v

= n

.ω

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à λ

và λ

;

l Lưu lưng ñ0n tương cng là A = a

+ a

, trong ñó, a

= λ

/d là lưu lưng tOi

vào chùm không l)ch hư.ng, và a

= λ

/ˆ 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

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

).ω 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

) ñư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

ñ-i v.i các chùm

ñưc l)ch hư.ng ñi vào n

FDL, trong ñó, D

, v.i i = 1, 2,…, v

, 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

= 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

) 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]:

(

)

( )

∑

!//

λ

(1)

Báo cáo nghiên cứu khoa học: "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ướng và bộ đệm FDL trong giải quyết tắc nghẽn trên mạng chuyển mạch chùm quang"

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi