HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
ĐÀO ĐỨC LONG THUẬT TOÁN ĐIỀN ĐẦY Ô TRỐNG VÀ ỨNG DỤNG
TRONG MẠNG OBSR
CHUYÊN NGÀNH : KỸ THUẬT VIỄN THÔNG
MÃ SỐ: 60.52.02.08
LUẬN VĂN THẠC SĨ KỸ THUẬT

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS BÙI TRUNG HIẾU

I


LỜI MỞ ĐẦU
Cùng với sự phát triển của xã hội, nhu cầu thông tin ngày càng tăng lên cả
về lưu lượng và chất lượng. Trước đây lưu lượng thoại chiếm phần lớn nhưng hiện
nay lưu lượng phi thoại đang dần thay thế và chiếm phần lớn. Cùng với sự ra đời
của nhiều loại hình dịch vụ mới yêu cầu về thời gian thực, QoS…Hiện nay lưu
lượ
ng viễn thông chủ yếu là lưu lượng IP. Do đó cần đưa ra các phương thức để hỗ
trợ việc truyền tải lưu lượng IP trên WDM. Chuyển mạch quang đóng vai trò quan
trọng trong việc truyển tải lưu lượng IP trên mạng quang. Nếu sử dụng chuyển
mạch điện tử thì các ưu điểm của thông tin quang như tốc độ sẽ bị hạn chế. Trong
điều kiện hiện nay thì chuyển mạch kênh quang đã được ứng dụng nhưng vẫn còn
nhiều hạn chế vốn có, còn chuyển mạch gói quang thì đang trong giai đoạn nghiên
cứu vì công nghệ hiện tại chưa thể đáp ứng được các yêu cầu của chuyển mạch
quang. Hiện tại chuyển mạch Burst quang được coi là một giải pháp hiệu quả trong
việc truyền tải lưu lượng IP trên mạng quang. Chuyển m
ạch Burst quang là sự kết
hợp các ưu điểm của chuyển mạch kênh quang và chuyển mạch gói quang. Tuy vậy,
một vấn đề quan trọng trong mạng OBS vẫn chưa được giải quyết triệt để, mà có lẽ
là cản trở chính trong triển khai mạng OBS vào thực tế, đó là xung đột (collision)
dẫn đến mất burst truyền qua mạng. Nhiều giải pháp giảm thiểu tranh chấp cũng đã
được đề xu
ất như sử dụng các đường dây trễ quang (FDL), chuyển đổi bước sóng
(WC), định tuyến lệch hướng (DR) nhưng cũng chỉ cho khả năng giảm hoặc
tránh một phần tranh chấp bước sóng truyền tải chứ không loại bỏ triệt để tranh
chấp và mất burst.
Một giải pháp đã được đề xuất và nghiên cứu có khả năng loại bỏ tranh

TỔNG QUAN
1.1 Giới thiệu sơ lược về mạng chuyển mạch burst quang OBS Hình 1. 1 Mô hình mạng chuyển mạch burst quang
1.2 Giới thiệu mạng OBS-R
Trong luận văn này, các giải pháp dành riêng cho mạng OBS cấu hình vòng
đã được đưa ra và đề xuất một vài cải tiến cho các giải pháp đó sẽ được trình bày.
Các giải pháp này cho phép loại bỏ tranh chấp bước sóng truyền tải và mất burst.

2



Hình 1. 2 Mô hình mạng và nút mạng OBS-R


Hình 1. 3 Nút mạng OBS-R
1.2.1 Báo hiệu cho mạng OBS-R
Trình bày về giao thức báo hiệu xoay vòng CSP.
1.2.2 Truyền tải qua mạng

3


1.3 Thuật toán đã được đề xuất cho mạng OBS-R
Giới thiệu một thuật toán đã được đưa ra cho mạng OBSR có tên gọi là thuật
toán “thợ may”. Việc lựa chọn bước sóng cho yêu cầu truyền áp dụng thuật toán
“thợ may” sẽ được thực hiện lần lượt theo các bước sau:


=L
n+k
; j=n HOẶC j+h=n+k)
BƯỚC 5: Tuyến rỗi có số đoạn nhỏ nhất:
λ
i
(L
j+h
)=0 & L
n+k
∩L
j+h
=L
n+k
; j=n HOẶC j+h=n+k; h=min)
BƯỚC 6: Bước sóng chứa tuyến rỗi có số đoạn sử dụng nhiều nhất:
λi(Lj+h)=0 & Ln+k∩Lj+h=Ln+k; j=n HOẶC j+h=n+k; h=min; ∑ λ
i
(s
x
)
max, x=1,2,…,N
BƯỚC 7: Chọn bước sóng có chỉ số nhỏ hơn; Đăng ký bước sóng; Lặp
lại bước 1 hoặc kết thúc.
BƯỚC 1: Tìm burst có tuyến yêu cầu dài nhất: L
n+k
;
4



MIỀN THỜI GIAN
Trong chương này, tôi giới thiệu một vài thuật toán đã được đề xuất cho
mạng OBS.
2.1 Giới thiệu các thuật toán lập lịch Burst
2.1.1 Một số thuật toán lập lịch Burst
Theo chính sách lập lịch được sử dụng có thể phân chia các thuật toán lập lịch
Burst như sau:
- Horizon hoặc Không điền đầy ô trống.
- Điền đầy ô trống.
Đại diện cho các thuật toán Horizon là: Kênh chưa được đăng ký thỏa mãn
đầu tiên - First Fit Unscheduled Channel (FFUC), Kênh chưa được đăng ký khả
dụng cuối cùng - Latest Available Unscheduled Channel (LAUC).
Đại diện cho các thuật toán điền đầy ô trống là: Kênh chưa được đăng ký có
khoảng trống th
ỏa mãn đầu tiên - First Fit Unscheduled Channel with Void Filling
(FFUC-VF), Kênh chưa được đăng ký có khoảng trống khả dụng cuối cùng - Latest
Available Unscheduled Channel with Void Filling (LAUC-VF) và Khoảng trống
nhỏ nhất - Minimum End Void (Min-EV).
6



Hình 2. 1 Minh họa cho các thuật toán lập lịch burst
Chúng ta định nghĩa kênh chưa được lập lịch và kênh trống như sau:
Kênh chưa được lập lịch: một kênh bước sóng được gọi là chưa được lập lịch tại
thời điểm t khi không có burst dữ liệu nào sử dụng kênh tại và sau thời điểm t.
Kênh trống: là kênh chưa được sử dụng suốt khoảng thời gian giữa hai burst dữ liệu
liên tiếp.
2.1.2 Thuật toán BFVF – Best Fit Void Filling
Trong phần này tôi đề xuất một thuật toán lập lịch mới, cố gắng tận dụng các

data channel: kênh dữ liệu được lựa chọn bằng thuật toán lập lịch burst
dữ liệu
THUẬT TOÁN BFVF
Đầu vào: start
b
, length
b
Đầu ra: data channel
Bước 1: Lựa chọn tất cả các kênh trống có thể đăng ký. Một kênh trống i được nói
là có thể đăng ký nếu start
b
> start
v
(i) và length
b
> length
v
(i)

. Nếu không có kênh
khoảng trống có thể đăng ký, đến bước 4.
Bước 2: Tính toán hệ số tận dụng kênh cho tất cả các kênh được tìm thấy ở bước 1.
8


Bước 3: Tìm một kênh j mà có hệ số tận dụng kênh lớn nhất được tìm ở bước 2.
Kênh đầu ra j là kênh cho dữ liệu. Kết thúc.
Bước 4: Đăng ký cho burst dữ liệu theo thuật toán LAUC. Kết thúc.
2.2 Cải tiến thuật toán điền đầy ô trống
Tôi đề xuất một sự kết hợp giữa hai thuật toán FFUC-VF và BFVF, tức là,

burst phải được thực hiện để đáp ứng các tiêu chí của mạng. Các tiêu chí này như là
burst được đặt sát liền kề với burst trước đó nhất, khoảng trống là nh
ỏ nhất thõa
mãn burst, hoặc khoảng trống sớm nhất cho burst truyền… Từ đó các thuật toán
9


FFUC-VF, LAUC-VF, hay BFVF đã được đưa ra. Trong luận văn này, tôi đề xuất
một sự kết hợp các thuật toán trên, dựa vào đó thực hiện khảo sát khả năng truyền
tải của mạng OBS-R.
Chương tiếp theo tôi thực hiện mô phỏng mạng chuyển mạch burst quang
cấu hình vòng OBS-R, kết quả thống kê thu được bước đầu giúp chúng ta đưa ra
được những đánh giá về khả năng truyền tải của m
ạng OBS-R sử dụng giao thức
báo hiệu CSP, và sử dụng thuật toán điền ô trống để định tuyến và lập lịch cho burst
dữ liệu.
λ
0

Truyền tải., λ
1
,…, λ
W

Hình 3. 1 Mô hình mạng mô phỏng
Khi mạng bắt đầu khởi tạo, bản tin BCP sẽ được nút 1 gửi đi lần đầu tiên, tất
cả các bước sóng đều rỗi. Trong một BCP có đầy đủ thông tin về các burst, tuyến và
thời gian sử dụng bước sóng truyền burst trong toàn mạng. Bảng 1 chỉ ra một cách
hiển thị thông tin đăng ký truyền burst trong BCP tại một nút mạng, trước khi BCP
này được phát đến nút tiếp theo trên vòng báo hiệu.
Bảng 1 Thông tin trong BCP tại một nút mạng
BƯỚC
SÓNG
BURSTS
THỜI ĐIỂM BIT ĐẦU CỦA
BURST ĐẾN
Mã L
B
(B) Tuyến P TT khác Nút A
1
… Nút A
n
… Nút A
N
11


-…-A
N
P
Bkλ1
… t
sA1
… t
sAn
t
sAN

… … … … …

λ
W

B
jλW
L
BjλW
A
N
-A
1
P
BjλW
… t
sA1
… … t
sAN

NỐI
NHIỆM VỤ

λ
1
A
(n-1)
- R
X
t
sAn/B1λ1
- t
fAn/B1λ1
Thu burst B
1λ1
… … …
A
(n-1)
- A
(n+1)
t
sAn/Bkλ1
- t
fAn/Bkλ1
Tạo đường truyền qua cho
B
kλ1

… … … …
λ

n
=20km ( n=1,…,8), B
r
=2,5Gbps, T
p
=100μs,
T
OS
=20μs. Đầu tiên, tôi cho L
B
=25kB và sau đó cho L
B
=50kB. Kết quả khảo sát
bằng mô phỏng như ở hình 3.3. Trên hình 3.3.a là đồ thị tỷ số các burst truyền được
trên các burst cần truyền phụ thuộc tải lưu lượng ρ .Trên hình 3.3.b, đường màu
xanh thể hiện số các burst trễ phải lưu đệm lại do không tìm được bước sóng rỗi
trong một lần xử lý BCP (một chu kỳ báo hiệu) phụ thuộc tải lưu lượng ρ; đường
màu đỏ thể
hiện số các burst mất trung bình trong một chu kỳ BCP phụ thuộc tải
lưu lượng ρ.
Cả hai, tỷ số các burst truyền được trên các burst cần truyền, số các burst trễ và số
các burst mất đều là giá trị trung bình thống kê trong thời gian quan sát R=200 chu
kỳ báo hiệu cho mỗi giá trị của tải lưu lượng ρ.



Hình 3. 2
T
burst
m

b
áo hiệu (b
)
n
truyền (a)
)
phụ thuộc
và số burs
t
tải
l
ưu lượ
n
t
trễ và số
n
g ρ. 


L
B
v
ớ
k
h
bu
bu

T
p
=100μs,
T
B
r
=2.5Gbp
s
ư
hình 3.4
.
u
yền phụ t
h
u
ng bình t
r
h
iện số
b
u
r
2, CSP-
O
T
OS
=10μs.
s
trong th
ờ

o
n
g bình tr
o
4

c
ác tham
s
t
ôi khảo s
á
n
sát là R
=
n

t
ỉ số giữ
a
.
Hình 3.4.
o
hiệu ph
ụ
o
ng mỗi c
h
s
ố N=6, l

ợ
m
àu xanh
t
lưu lượn
g
h
iệu phụ th
u

n=1,…,8)
,
b
ps, sau đ
ó
u
. Kết qu
ả
ợ
c trên cá
c
t
hể hiện s
ố
g
ρ, đườn
g
u
ộc tải lư
u

bá
n
h
l
ớ
n
h
h
i

ph
tr
x
ả
H
ình 3. 3 T
ỷ

.
5 Nhậ
n
 Tron
g
ậ
y loại bỏ
u
yền từ n
g
h
ưa có bư

số burst tr
u
trong m
ộ
n
xét, đá
n
g
mạng C
S
hoàn toà
n
g
uồn đến đ
í
ớ
c sóng v
à
h
u kỳ
b
áo
h
b
urst này c
ò
Với các
m
n
g lớn (thư

iá
S
P-OBS k
h
n
mất bur
s
í
ch theo t
u
à
tuyến rỗ
i
h
iệu sau.
N
ò
n bị trễ t
h
m
ạng nằm
t
ờng nhỏ h
ơ
ó
kích thư
ớ
a
n nhỏ hơ
n

s
t do tran
h
u
yến và th
ờ
i
thích hợ
p
N
hư vậy,
n
h
êm một
k
t
rong vùn
g
ơ
n 10ms),
ớ
c địa lý l
ớ
n
, truyền n
h
o
phép.
ấ
y, khi tải

g
k
hoảng th
ờ
g
địa lý (k
í
thời gian
t
ớ
n, có thể
h
iều hơn
m
lưu lượng
m
ột phần
l
á
o hiệu sa
u
thị 3.3.b
v
t
ruyền (a),
s
v
ào tải lưu l
ư
h

ầ
l
ưu lượng
u
, nhưng n
v
à 3.4.b)
v
s
ố burst tr
ễ

ư
ợng ρ
s
óng truyề
n
n
. Các bur
s
ề
n burst. N
h
l
ưu lại tro
n
n
dẫn và t
h
h

s
t sẽ đượ
c
h
ững burs
t
n
g bộ đệ
m
h
ời gian b
ù
m
ột chu k
ỳ
n
g bình v
à
p
hải là qu
á
ệ
u T thàn
h
c
hu kỳ
b
á
o
0

o

i

m

a

ờ

16


cũng chỉ xấp xỉ 10% tổng lưu lượng cần truyền (là tổng của lưu lượng mới phát sinh
và lưu lượng chờ từ vòng báo hiệu trước).
Trên hình 3.3.b, 3.4.b chỉ rõ số burst trễ (phải chờ đến chu kỳ báo hiệu sau) ở
tất cả các nút trong mạng. Khi lưu lượng tải nhỏ và trung bình, số burst trễ khá nhỏ.
Với ρ=1, chưa xảy ra hiện tượng mất burst, số burst trễ c
ũng chỉ nhỏ hơn 10, tương
đương với trung bình mỗi nút mạng có xấp xỉ một burst phải chờ. Điều này cho
thấy, dung lượng bộ đệm burst dành cho các burst trễ không lớn, hầu như không
làm tăng giá thành của thiết bị nút mạng.
Trên hình 3.3.a và 3.3.b, đồ thị ở 2 trường hợp L
b
= 25kB và L
b
= 50kB tách
nhau khi ρ>0.6. Điều này là do với cùng một giá trị tải lưu lượng ρ, khi độ dài burst
khác nhau thì số lượng burst khác nhau, dẫn đến số lần (hay tổng thời gian) phải xử
lý BCP tại các nút mạng là khác nhau. Ở trường hợp cụ thể này, với cùng một giá trị

thờ
i gian rỗi trên mỗi kênh bước sóng và đăng ký cho burst cần truyền tại nút. Kết
quả được đưa ra dưới dạng đồ thị trực quan phản ánh năng lực truyền tải của mạng
OBSR.
Cũng cần nói rõ thêm, thuật toán điền ô trống tôi sử dụng trong mô phỏng
chưa phải thuật toán tối ưu. Trong mạng OBS, định tuyến truyền burst yêu cầu bước
sóng rỗi trong các khoảng thời gian khác nhau mà burst đi qua trên từ
ng đoạn của
tuyến truyền burst. Ngoài ra, thời điểm phát burst còn phải chậm sau thời điểm phát
BCP một khoảng thời gian không nhỏ hơn thời gian bù trước (T
offset
). Những khác
biệt này dẫn đến rất khó áp dụng các thuật toán định tuyến đã được áp dụng trên các
mạng chuyển mạch khác cho mạng OBS và do vậy, cần phải có các thuật toán định
tuyến mới. Tìm kiếm thuật toán tối ưu cho chọn tuyến và khoảng rỗi của bước sóng
còn cần được nghiên cứu tiếp và là vấn đề còn để ngỏ. Khi có một thuật toán hợp lý
hơn, chắc chắn k
ết quả truyền tải qua mạng CSP-OBS sẽ còn tốt hơn. 18