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ƯỚ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
Đặng Thanh Chương
Trường Đại học Khoa học, Đại học Huế
TÓM TẮT
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. Sự tắc nghẽn chùm trong mạng OBS có thể xuất hiện khi hai chùm quang dữ
liệu từ hai cổng vào khác nhau cố gắng đi ra trên cùng một cổng ra tại cùng một thời điểm. Các
giải pháp cho việc xử lý tắc nghẽn là: sử dụng đường trễ quang (FDL); chuyển đổi bước sóng
và định tuyến lệch hướng. Tuy nhiên, nếu định tuyến lệch hướng được sử dụng, các FDL cần
thiết được sử dụng để bù vào sự thiếu hụt thời gian offset do sự tăng thêm độ dài đường đi lệch
hướng.
Việc phân tích ưu, nhược điểm của mỗi phương pháp, cũng như kết hợp chúng thường
được thực hiện qua mô hình hàng đợi. Bài báo nhằm đề xuất một mô hình hàng đợi để phân tích
việc sử dụng kỹ thuật định tuyến lệch hướng kết hợp với việc sử dụng 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 thấy có sự cải thiện xác suất tắc nghẽn
so với các mô hình đã đề xuất trước đó.

1. Giới thiệu
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 thế hệ sau, bởi vì
nó có nhiều lợi thế hấp dẫn 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 của mạng OBS, những dữ liệu vào
(chẳng hạn các luồng IP) có cùng ñích ñến (và cùng lớp dịch vụ QoS) ñược tập hợp
trong một chùm quang dữ liệu (data burst), ñược lập lịch (scheduling) và ñược gởi vào

Nhiều phương pháp ñịnh tuyến lệch hướng ñã ñược ñề xuất, như ñịnh tuyến lệch
hướng sử dụng offset bổ sung và ñịnh tuyến ñường ñi ngắn nhất [4]. Trong phương
pháp ñịnh tuyến lệch hướng thông thường, chỉ một chùm ñược chuyển ñi theo tuyến
ngắn nhất (tuyến chính), còn chùm tắc nghẽn sẽ ñược ñịnh tuyến lệch hướng sang tuyến
mới (tuyến lệch hướng). Tuy nhiên, khi cả tuyến lệch hướng mới cũng không sẵn có thì
chùm ñó sẽ bị hủy.
Mặc dù các kết quả nghiên cứu ñã chứng minh rằng ñịnh tuyến lệch hướng có
thể làm giảm ñáng kể việc mất chùm, tuy nhiên, nó cũng làm tăng ñộ trễ ñầu-cuối bởi vì
lộ trình lệch hướng thường dài hơn lộ trình ban ñầu. Vì vậy, trong mạng OBS, thường
kết hợp ñịnh tuyến với các phương pháp khác (như truyền lại, sử dụng FDL, chuyển ñổi
bước sóng,…). ðể phân tích và ñánh giá các lược ñồ ñịnh tuyến lệch hướng có kết hợp
với các phương pháp khác, mô hình lý thuyết hàng ñợi thường ñược sử dụng ñể lựa
chọn phương án tối ưu. Mục tiêu của bài báo là nghiên cứu vấn ñề ứng dụng mô hình
hàng ñợi Markov ñể phân tích và ñánh giá các hướng giải quyết tắc nghẽn trong mạng
OBS dựa trên phương pháp chính là ñịnh tuyến lệch hướng, kết hợp với việc sử dụng
ñường trễ quang FDL.
Nội dung tiếp theo của bài báo bao gồm: phần 2 giới thiệu mô hình hàng ñợi ñể
phân tích ñịnh tuyến lệch hướng kết hợp với sử dụng bộ ñệm FDL; phần 3 phân tích kết
quả với một số mô hình khác; và cuối cùng là phần kết luận. 21
2. Mô hình hàng ñợi phân tích kỹ thuật lệch hướng với việc sử dụng ñường trễ
quang FDL
Mô hình mạng OBS ñược nghiên cứu ở ñây (hình 1) sử dụng giao thức báo hiệu
một chiều JET và giao thức lập lịch tài nguyên LAUC_VF [5]. Gói ñiều khiển sẽ ñược
gởi trên kênh bước sóng ñiều khiển tách biệt và ñược xử lý (hoàn toàn trong miền ñiện
tử) 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 ñã ñặt trước bước sóng trên toàn tuyến từ nguồn ñến ñích thì chùm sẽ ñược
phát ñi. Việc phân tích mô hình mạng hàng ñợi áp dụng cho ñịnh tuyến lệch hướng xét

ñịnh tuyến lệch hướng, các chùm ñược lệch hướng cũng sẽ ñược cấp phát trên các bước
sóng riêng ñể làm giảm tắc nghẽn và cải tiến hiệu suất mạng. Ngoài ra, các FDL còn lại
cũng ñược sử dụng cho các chùm không lệch hướng ñể làm trễ chùm nếu có sự tranh
chấp bước sóng giữa chùm lệch hướng và chùm không lệch hướng.
Một số giả thiết trong mô hình:
- Có ω bước sóng trên mỗi kết nối sợi quang ra, tương ứng một tập Λ = {λ
1
, λ
2
,
… λ
ω
};
- ðộ dài chùm ñược phân bố theo hàm mũ với giá trị trung bình L = 1/µ; trong
ñó, các chùm ñều ñược phục vụ với tốc ñộ trung bình µ.
- Số chặng mở rộng trung bình ñối với các chùm ñược lệch hướng là h;
- Thời gian xử lý tối ña ñối với gói ñiều khiển tại mỗi chặng là δ;
- Số FDL tại nút ñang xét là n; trong ñó n
d
FDL ñược thiết kế 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 ở giai
ñoạn 2.
- Có ω bước sóng trong bộ ñệm FDL, thời gian offset mở rộng trung bình ñối với
các chùm lệch hướng, bằng 1/µ
d
.δ; do ñó số FDL ảo ñối với các chùm ñược lệch hướng
là v
d


23
do lệch hướng.
Mô hình ñược ñề xuất ở ñây là mô hình hàng ñợi Markovain M/M/c/c, gồm 3
giai ñoạn tại một nút OBS (hình 2). Giai ñoạn ñầu tiên tương ứng với các ñường trễ
quang FDL ñể cung cấp thời gian offset mở rộng cho các chùm ñược lệch hướng. Giai
ñoạn thứ 2 ứng với k bước sóng (trong số ω bước sóng) trên kết nối sợi quang ra ñược
ưu tiên cấp phát chỉ cho các chùm ñược lệch hướng. Giai ñoạn thứ 3 ứng với số bước
sóng còn lại trên kết 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 từ 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 từ 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. Nếu tất cả các bước sóng ñều bận, các chùm (lệch hướng
và không lệch hướng) sẽ ñược làm trễ tạm thời bởi (n-n
d
) ñường trể FDL còn lại.

Hình 2. Mô hình 3 giai đoạn của 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

!//
µλ
µλ

(1) 24
Theo ñặc tính của mô hình Markovian, thời ñiểm lệch hướng có phân bố giống
phân bố của thời ñiểm ñến (nếu không bị giới hạn vào khả năng hệ thống, tức là mô
hình M/M/c/∞). Vì vậy, luồng lệch hướng ra từ giai ñoạn ñầu tiên cũng tuân theo phân
bố Poisson với tốc ñộ trung bình
0
d
λ
như sau:
(
)
1
0
1 PB
dd
−=
λλ

(2)
Tại giai ñoạn thứ 2, có k bước sóng trên kết nối sợi quang ra ñược cấp phát riêng
cho các chùm lệch hướng. Giai ñoạn này ứng với mô hình mất M/M/k/k trong ñó xác
suất PB
2

:
0
2
1
.
dd
PB
λλ
=

(4)

1
d
γ

1
d
γ

f
γ

1
d
γ

1
d
γ

d
γ

1
d
γ

f
γ

f
γ

f
γ

f
γ

f
γ

f
γ

f
γ

f
γ

sóng khi có sự tranh chấp bước sóng giữa 2 chùm này. Khi ñó, lưu lượng không lệch
hướng sẽ sử dụng các FDL ñể làm trễ chúng. Khác với [4], FDL ñược chúng tôi ñề xuất
trong giai ñoạn này dành cho cả chùm lệch hướng và không lệch hướng.
Giai ñoạn thứ 3 ứng với mô hình lưu lượng multi-dimensional [6]. Giả thiết rằng
các chùm không lệch hướng và lệch hướng ñến vẫn theo quá trình Poisson với tốc ñộ
trung bình là
f
λ
và
1
d
λ
. Lược ñồ chuyển trạng thái trong giai ñoạn 3 ñược chỉ ra trong
hình 3. Mỗi trạng thái trong mô hình ở giai ñoạn 3 ở trên ứng với cặp (i,j); 0 ≤ i ≤ ω-k +
(n–n
d
).ω, 0 ≤ j ≤ ω-k + (n–n
d
).ω tương ứng là số chùm không lệch hướng và lệch hướng.
Số trạng thái trong chuỗi Markov ñược tính như sau:
(
)
(
)
(
)
2
1)()(22
+
−

++−−
+++++=+++
jijijidjifijdf
jiji
µπµππλπλπµλλ

(6)
ở đây, 0 ≤ i ≤ (ω – k) + (n-n
d
).ω - 1, 0 ≤ j ≤ (ω – k) + (n-n
d
).ω -1, 0 ≤ i +j ≤ (ω – k) +
(n-n
d
).ω -1
và
1,
1
,1
)(
−−
+=+
jidjifij
ji
πλπλµπ

(7)
ở đây, 0 ≤ i ≤ (ω – k) + (n-n
d
).ω, j ≤ ω – k + (n-n

i
a
ji
ij
=

(8)
Trong ñó,
00
π
ñược tính như sau:
1
23
)(
0
1
)(
0
00
!!
−
−+−
=
+−
=







26
∑
+−
=
−+−
−+−
=
q
q
k
i
q
ik
i
x
ik
a
i
a
PB
νω
νω
π
νω
)(
0
00
)(
23

3
323
3
a
PBa
PB
d
=

(11)
ở ñây,
a
3
= a
1
+ a
23
, là tổng lưu lượng ñến ở giai ñoạn 3.
Xác xuất tắc nghẽn chùm trung bình (
PB
) ñối với mô hình 3 giai ñoạn ở trên
ñược tính theo [4]-[6] và từ (11), cho kết quả cuối cùng như sau:
[
]
A
PBPBPBPBaPBa
PB
dnd
3211231
)1(

32112
)1(
−
+
=

3. Phân tích kết quả

Hình 4. Xác suất tắc nghẽn với chùm lệch hướng vs. lưu lượng β (Erl), đối với k=0,2,4 27
Phân tích kết quả thu ñược ñối với xác suất tắc nghẽn chùm lệch hướng (
PB
d
)
như là một hàm của lưu lượng vào ñược chuẩn hóa trên bước sóng β=A/ω, khi a
1
=0.7A,
a
2
=0.3A, L=1/µ=48µs, h=1, δ=0.1L, 1/µ
d
=0.2L, n =2, n
d
=1, W=16, k=0, 2, 4 (tương
ứng là
PB
d0
, PB

d_pevac
của mô hình ñược ñề xuất bởi Pevac [5], trong
ñó, các bộ ñệm FDL ñược sử dụng chỉ cho các chùm lệch hướng ở giai ñoạn 1 ñể bù
thời gian offset tăng thêm do lệch hướng. Kết quả cho thấy có sự cải tiến ñáng kể về xác
suất tắc nghẽn chùm khi lược ñồ ñề xuất ñược thực hiện.
4. Kết luận
Trong bài báo này, chúng tôi ñã phân tích ảnh hưởng của ñịnh tuyến lệch hướng
(có sự kết hợp với các FDL) trong mạng OBS bằng mô hình mạng hàng ñợi Markov.
Trong kỹ thuật ñinh tuyến lệch hướng, các FDL thường ñược sử dụng ñể bổ sung thời
gian offset do lộ trình lệch hướng thường dài hơn lộ trình ban ñầu. Bài báo ñã ñề xuất
một mô hình ñược cải tiến từ một số mô hình trước ñó. Kết quả phân tích cho thấy mô
hình ñược ñề xuất cho xác suất tắc nghẽn với các chùm lệch hướng là tối ưu hơn. Tuy
nhiên, mô hình chưa xem xét vấn ñề số lượng tối ưu FDL ñược sử dụng tại một nút.
Thêm vào ñó, chi phí trang bị FDL cũng cần phải ñặt ra. ðây ñược xem là hướng mở
cho các nghiên cứu tiếp theo của chúng tôi. 28
TÀI LIỆU THAM KHẢO
[1]. Y. Chen, C. Qiao, and X. Yu, Optical Burst switching: a new area in optical networking
research, IEEE Network, vol. 18, no. 3, (2004), 16–23.
[2]. Son-Hong Ngo, Xiaohong Jiang, and Susumu Horiguchi, Hybrid Deflection and
Retransmission Routing Schemes for OBS Networks, Workshop on High Performance
Switching and Routing, 2006.
[3]. T. Venkatesh, C. Siva Ram Murthy, An Analytical Approach to Optical Burst Switched
Networks, Springer ISBN 978-1-4419-1509-2, Chennai, India, August 2009.
[4]. Hsu C. F., Liu T. L., Huang N. F., Performance analysis of deflection routing in optical
burst-switched networks, Proceedings of IEEE INFOCOM, (2002), 846–852.
[5]. R.Bojovc, D.Pevac, I. Petrovic, An Approach to Resolving Contention in an Optical
Burst Switched WDM Network, ISSN 1392 – 1215- ELECTRONICS AND

Keywords: Blocking probability, OBS network, Deflection routing, FDL.