HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN LONG BÌNH
MỘT SỐ THUẬT TOÁN ĐỊNH TUYẾN VÀ GÁN BƯỚC
SÓNG TRONG MẠNG CHUYỂN MẠCH BURST

CHUYÊN NGÀNH : KỸ THUẬT VIỄN THÔNG
MÃ SỐ: 60.52.02.08

8 TÓM TẮT LUẬN VĂN THẠC SỸ
HÀ NỘI - NĂM 2013

1
MỞ ĐẦU
Công nghệ chuyển mạch burst quang (Optical Burst Switching – OBS) là
một giải pháp hữu hiệu cho phép truyền tải lưu lượng trong mạng quang WDM
hiện nay cũng như mạng toàn quang trong tương lai. 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 giữa các burst được truyền
trong mạng dẫn đến mất burst dữ liệ
u.
Một giải pháp có tính đột phá đang được thầy giáo, PGS. TS Bùi Trung Hiếu
cùng với nhóm nghiên cứu đề xuất có khả năng loại bỏ hoàn toàn các tranh chấp
bước sóng truyền tải và mất burst trong mạng quang chính là sử dụng giao thức
báo hiệu xoay vòng (CSP- Circle Signalling Protocol) để truyền tải các burst qua
mạng OBS.
Vấn đề đặt ra là làm thế nào để truyền các burst trong mạng một cách tối ưu
để tận dụng được tối đa các tài nguyên vốn có của m
ạng. Vì vậy việc định tuyến và
gán bước sóng cho các burst là một chức năng quan trọng trong các mạng chuyển
mạch burst quang (OBS Networks). Qua nghiên cứu, tìm hiểu cùng với sự hướng
dẫn của thầy giáo, trong luận văn này tôi thực hiện nghiên cứu một số thuật toán
định tuyến và gán bước sóng cho các burst quang trong các topo mạng điển hình
của mạng chuyển mạch burst quang và xin phép được đưa ra giải pháp định tuyến
và gán bước sóng đồng thời trong mạng OBS s
ử dụng giao thức báo hiệu CSP.
Cấu trúc của luận văn gồm 3 chương:
Chương 1: Tổng quan về mạng chuyển mạch burst quang
Chương này trình bày những khái niệm và vấn đề cơ bản về kỹ thuật chuyển
mạch burst quang, bao gồm khái niệm chuyển mạch burst quang, cấu trúc của
mạng chuyển mạch burst quang, các vấn đề về lập/ tách burst, nguyên lý truyền tải
burst quang trong mạng OBS.

1.1. Các khái niệm về chuyển mạch burst quang
1.1.1. Chuyển mạch burst
Chuyển mạch burst quang được thiết kế hướng tới một sự cân bằng giữa
công nghệ chuyển mạch kênh và chuyển mạch gói quang. Trong một mạng OBS
thì burst là phần tử nhỏ nhất của mạng. Một burst dữ liệu là một tổ hợp gồm nhiều
gói IP, được chuyển mạch qua mạng OBS một cách hoàn toàn bằng tín hiệu quang
(mạng OBS toàn quang). Các header của burst còn
được gọi là các gói điều khiển
của burst (CP- Control Packet) được truyền đi trước khi thực hiện truyền burst đó
để các nút thực hiện cấu hình chuyển mạch dọc theo tuyến cần truyền. Các gói điều
khiển burst được truyền ở kênh truyền riêng biệt (kênh điều khiển) với các kênh
truyền burst (kênh dữ liệu). Gói điều khiển burst được truyền đi trước khi truyền
burst một khoả
ng thời gian gọi là T
Offset
, khoảng thời gian này cho phép CP được
xử lý và các thiết bị chuyển mạch được thiết lập trước khi burst dữ liệu đến được
các nút trung gian trong tuyến truyền dẫn. Do đó, không cần các bộ đệm điện tử
hay bộ đệm quang tại các nút trung gian trong khi gói điều khiển đang được xử lý.
Gói điều khiển cũng có thể định rõ khoảng thời gian truyền burst để cho các nút
trung gian biết được để
các nút đó có thể tái cấu hình bộ chuyển mạch của chúng
cho burst đến tiếp theo.
Bằng việc đặt trước tài nguyên trong mạng chỉ trong một khoảng thời gian
đã được xác định rõ ràng sẽ tốt hơn việc đặt trước tài nguyên trong một khoảng
thời gian không xác định hay việc chiếm dụng tài nguyên toàn phần (trong chuyền
mạch kênh). Lúc này tài nguyên mạng có thể được sử dụng, cấp phát hiệu quả hơn
và việc ghép kênh sẽ
được thực hiện ở một mức cao hơn.
1.1.2. Thiết lập burst

burst đến, thời gian tới của burst đó hoặc cả hai để thực hiện công việc
đặt trước
hiệu quả tài nguyên mạng (tuyến đường, bước sóng,…) bên trong mạng lõi của
mạng OBS.
1.2. Một số cấu trúc của mạng chuyển mạch burst quang
1.2.1. Cấu trúc cơ bản của một mạng OBS
Một mạng OBS cơ bản bao gồm nhiều nút chuyển mạch burst quang gồm
các nút biên (hay còn được gọi là các nút “rìa”) và các nút lõi, được liên kết với
nhau thông qua các kết nối sợi quang (fiber link). Mỗi một liên kết sợi quang có
khả
năng cung cấp nhiều kênh đa bước sóng (WDM chanel) sử dụng kỹ thuật ghép
kênh phân chia theo bước sóng (WDM Tenology). Trong các kênh đa bước sóng
đó sẽ có 01 kênh bước sóng (kênh điều khiển) được sử dụng để truyền các gói điều
khiển burst (CP- Control Packet) và còn lại là các kênh truyền burst (kênh dữ liệu).
Nhờ có sự tách bạch riêng rẽ giữa các kênh dữ liệu và kênh điều khiển nên việc
truyền dữ liệu giữa các nút bên trong mạng lõi chỉ đơn gi
ản là việc chuyển mạch
các burst dẫn đến tốc độ truyền dẫn của mạng OBS sẽ đáp ứng được yêu cầu của
mạng thế hệ sau NGN hay mạng internet tốc độ cao. Hình 1.3 dưới đây minh họa
cho cấu trúc cơ bản của một mạng OBS.
Trong cấu trúc cơ bản của mạng OBS ta có thể thấy rằng mỗi một nút có thể
nhận được cả hai loại l
ưu lượng bao gồm lưu lượng đầu vào (các gói dữ liệu mới
đến cần được thiết lập thành burst) và các lưu lượng chuyển tiếp (các burst đến).
Vì vậy một số nút trong mạng OBS có thể phải có cả hai chức năng là một nút biên
(chứa bộ định tuyến biên – edge router) và là một nút lõi (chứa bộ định tuyến lõi –
core router). Những nút như vậy được gọi là những “nút lai” (hybrid node). 5

thông tin trạng thái của mạ
ng qua kênh điều khiển chung này để đưa ra những
quyết định hợp lý. Sau khi có những quyết định các nút này lại gửi các gói điều
Mạng
khác
Mạng OBS
Mạng
Khách hàng
N
út biên
N
út lõi
Kỹ thuật
báo hiệu 6
khiển burst của mình lên kênh điều khiển chung và cập nhật cho tất cả các nút
trong mạng được biết về việc chiếm giữ tài nguyên của mình.
1.3. Nguyên tắc hoạt động cơ bản của mạng OBS
Các đặc điểm cơ bản khác của một mạng OBS như sau:
Báo hiệu ngoài băng (Out-of-band Signalling): Các gói điều khiển burst
được truyền đi trên một kênh điều khiển riêng biệt vớ
i kênh truyền các burst đó, tại
mỗi nút mà nó đi qua được thực hiện chuyển đổi O/E, xử lý gói điều khiển và
chuyển đổi E/O rồi lại được gửi đi đến nút tiếp theo trên đường truyền.
Tính trong suốt dữ liệu (Data transparency): Dữ liệu được truyền đi hoàn
toàn trong suốt với các nút trung gian trong mạng OBS (hay có thể nói đối với các
nút lõi trong mạng OBS chỉ thực hiện việc chuyển mạch toàn quang
đối với các

7
CHƯƠNG 2- CÁC GIAO THỨC BÁO HIỆU TRONG MẠNG
CHUYỂN MẠCH BURST QUANG
2.1. Nguyên lý báo hiệu trong mạng OBS
2.1.1. Các phương pháp đặt trước tài nguyên trong mạng OBS
Nguyên tắc chính của việc báo hiệu trong mạng OBS đó chính là việc xác
định làm thế nào để các bộ chuyển mạch OXC biết được phải chuyển mạch các
burst quang trong mạng OBS hay có thể nói là các bộ điều khiển chuyển mạch phải
có được tài nguyên của mạng (tuyến đường, bước sóng truyền dẫn) để phục vụ cho
công việc truyền một burst từ
đầu vào đến đầu ra của mạng OBS. Do vậy để có
được điều này thì các bộ điều khiển chuyển mạch SCU phải thực hiện đặt trước tài
nguyên mạng cho mỗi một cuộc truyền tín hiệu trong mạng và các giao thức đặt
trước tài nguyên [21] phải đáp ứng được việc xác định, vận hành và bảo trì các cơ
sở dữ liệu về tình trạng tài nguyên mạng.
Về cơ b
ản thì có thể chia ra 03 phương pháp đặt trước tài nguyên trong
mạng OBS đó là: Không đặt trước tài nguyên [22], đặt trước một chiều hay còn gọi
là phương pháp đặt trước TAG (tell and go) [23] và đặt trước hai chiều hay còn gọi
là phương pháp đặt trước TAW (tell and wait) [23]. Ngoài ra còn có một số
phương pháp báo hiệu biến thể của phương pháp TAW đó là báo hiệu “khởi động
tại nút trung gian” INI (Intermediate Node Initiated) [24] và báo hiệu “gói điều
khiển kép” DCP (Dual Control Packet) [25]. Tuy nhiên hiện nay có rất nhiều nhà
nghiên cứu chỉ quan tâm
đến hai phương pháp đó là TAG và TAW vì vậy trong đồ
án này cũng chỉ đề cập đến hai phương pháp này.
Từ khi mô hình mạng OBS được đề xuất bởi Yoo, Jeong và Qiao trong [6-8]

ứng cần để dùng. Cách
thứ nhất được gọi là “đặt trước ngay lập tức” cách còn lại được gọi là “đặt trước
trễ”.
2.1.3. Tương quan giữa phương pháp đặt trước tài nguyên “điền ô trống” và
“không điền ô trống”
Khi sử dụng phương pháp đặt trước tài nguyên trễ, một giao thức được gọi là
có khả năng triển khai việc “điền ô trống” nếu nó có thể xắ
p xếp để tận dụng được
tài nguyên trên kênh truyền cho việc truyền một burst tương thích qua không gian
trống trên kênh truyền dữ liệu mà đã được đặt trước tài nguyên cho một burst khác
trước đó. Như ta đã đề cập ở phần trên, JET là một trong các giao thức có thể triển
khai việc “điền ô trống” này, trong đó JET sẽ nỗ lực thực hiện điền ô trống bằng
cách truy xuất đến cơ
sở dữ liệu tại SCU (hay SE) tại từng nút trung gian, cố gắng
tìm ra khoảng thời gian thích hợp trong bất kỳ kênh dữ liệu nào phục vụ cho Burst
cần truyền.
Như hình 2.6 và hình 2.7, ta có thể thấy rõ cùng một trường hợp xắp sếp lịch
truyền burst cho 02 burst (burst 1 và burst 2) cố gắng sử dụng cùng một tài nguyên
đầu ra trong một nút. Đối với mỗi burst thì các gói điều khiển tương ứng CP1 và
CP2 được xử lý và CP1 đến trướ
c CP2. Vì T
Offset
của burst 2 nhỏ hơn burst 1 do
vậy mà burst 2 sẽ đến nút trước khi burst 1 đến nút đó.
Nhưng ở trường hợp 1 không sử dụng giao thức có điền ô trống thì burst thứ
2 vẫn bị loại bất chấp tài nguyên của kênh lúc này vẫn có thể đáp ứng được cho nó
(ta có thể thấy rằng trên hình vẽ kênh lúc này là “rỗi” có nghĩa là có khả năng đáp
ứng được cho việc truyền burst 2) bởi vì khi CP1 được xử lý thì tài nguyên kênh
truyề
n lúc này đã được đặt ngay lập tức (như đã mô tả trên hình 2.4). Còn nếu ở

là một giao thức báo hiệu “định trước trễ” nhưng lại không có khả năng “điền ô
trống”. Thời gian “horizon” ở đây được xác định là thời điểm sớm nh
ất mà kênh
truyền được xác định là rỗi. Vì Horizon không sử dụng điền ô trống nên nó không
thể tận dụng được khoảng tài nguyên rỗi khi nó đã xử lý gói điều khiển CP của một
burst mặc dù từ khi xử lý xong đến khi quyết định cấu hình bộ OXC thì thời điểm
đó kênh dữ liệu vẫn có khả năng truyền được một burst thích hợp khác (như được
mô tả trong hình 2.6) do vậy giao thứ
c Horizon không được ưa chuộng như giao
thức JET.
Thời điểm
đến của CP1
Thời điểm
đến của CP2
Thời điểm đến
của burst 2
Thời điểm đến
của burst 1
Khoảng rỗi
rỗi
rỗi
Kênh
điều khiển
Kên
h
dữ liệ
u
Thời điểm
đến của CP1
Thời điểm

một số
đặc tính sau đây: Cho phép triển khai QoS, Hỗ trợ Multicast, Cho phép
chuyển mạch nhãn và Cho phép những kết nối ổn định (các đường dẫn quang ổn
định).
Trong giao thức JumpStart thì tại nút biên nguồn sẽ triển khai một bản tin
báo hiệu tới nút lõi trung gian đầu tiên vào trong khi burst đang đợi để được truyền
đi. Nếu nút đầu vào có thể chuyển burst đó đi thì nó sẽ gửi lại cho nút biên một bản
tin xác nhận (ACK) và chuyển tiếp gói điều khiể
n burst tới các nút lõi trong mạng.
Ngược lại nếu nút đầu vào không thể chuyển burst đó đi thì nó cũng gửi lại một
bản tin không xác nhận (NAK) tới nút biên và burst đó bị “rớt”

2.2.5. Giao thức JIT
+

Giao thức JIT
+
được đề xuất năm 2003 bởi Teng và Rouskas [30], giao thức
này cải thiện hơn giao thức JIT như sau: Một kênh dữ liệu được đặt trước cho một
burst nếu thời gian tới của burst đó xảy ra sau mức “giới hạn thời gian” (time
horizon) của kênh dữ liệu đó và nếu kênh dữ liệu đó có thể đặt trước tối đa một
phần tài nguyên khác. Điều này có nghĩa là giao thức JIT
+
không cố gắng thực hiện
phương pháp điền ô trống mà nó cố gắng cải thiện hiệu năng của giao thức JIT đó
là cho phép tối đa đặt trước hai tài nguyên mạng đồng thời (đặt trước tài nguyên
cho 02 burst) với điều kiện không có tranh chấp burst và tài nguyên mạng sẵn có
cho 02 burst vào thời điểm thiết lập kênh truyền.
2.2.6. Giao thức E-JIT
Giao thức E-JIT hay còn gọi là giao thức JIT “nâng cao” được giới thiệu bởi

đến mất burst truyền dẫn qua mạng.
2.3. Giới thiệu giao thức báo hiệu xoay vòng CSP
Gần đây đã xuất hiện một giao thức điều khiển không tranh chấp cho mạng
OBS được gọi là giao thức báo hiệu xoay vòng CSP (Cycle Signalling Protocol) do
PGS. TS Bùi Trung Hiếu và các cộng sự đề xuất, đã giải quyết được vấn đề tranh
chấp bước sóng truyền tải và mất burst một cách hoàn toàn bằng cách truyền một
gói tin điều khiển burst BCP (Burst Controlling Packet) theo vòng và đăng ký
trước bước sóng truyền burst trong mạng.
2.3.1. Phương pháp truyền bản tin
điều khiển BCP
Như ta biết mạng truyền tải OBS có thể được xây dựng theo nhiều cấu hình
khác nhau, ta xét trên một mạng thỏa mãn điều kiện là trong mạng tạo được ít nhất
một vòng truyền dẫn khép kín đi qua tất cả các nút mạng và chỉ qua mỗi nút mạng
một lần (việc tạo ra một vòng như vậy có thể sử dụng thuật toán người đi du lịch –
Travel Agent Algorithm). Vòng này được s
ử dụng để truyền BCP và các thông tin
báo hiệu khác, tạm gọi là vòng báo hiệu SR (Signalling Ring). Điển hình các mạng
có thể thỏa mãn điều kiện này là các mạng có cấu hình vòng (ring) hoặc mắt lưới
(mesh). Mô hình mạng sử dụng CSP được chỉ ra trên hình 2.12 dưới đây. 12
, thời gian phát BCP (T
T-BCP
), thời gian thu BCP (T
R-BCP
)
không thay đổi thì thơi gian truyền BCP trên vòng báo hiệu không thay đổi và
được gọi là chu kỳ báo hiệu T
T =
∑∑
==
−−−
+++
N
n
N
n
tnAnBCPpAnBCPRAnBCPT
TTTT
11
///
)( (2.3)
Thực tế thời gian phát, thời gian thu, thời gian xử lý BCP của các nút mạng
không hoàn toàn ổn định như nhau trong các vòng truyền BCP vì vậy chu kỳ T
thực tế sẽ thay đổi. Trong một mạng đang hoạt động thì chu kỳ T có thể được thay
bằng thời gian báo hiệu một vòng, xác định theo thời gian thực tại mỗi nút mạng:
T
i/An
= t
Ts-BCP(i+1)/An
– t

BCP
i
BCP
i
t
TsBCPi/An
T
tn
T
R-BCP
T
p
T
T-BCP
BCP
i
BCP
i
BCP
i
BCP
i+1
T
t
TsBCP(i+1)/An 13
2.3.2. Cấu trúc gói tin điều khiển BCP
Tác giả của giao thức CSP đề xuất một cấu trúc thông tin mới cho BCP,

Nút mạng định tuyến truyền burst ngay sau khi nhận BCP. Khi đã xác định
được tuyến và bước sóng truyền các burst, nút mạng đăng ký thông tin truyền burst
vào BCP trước khi phát BCP đến nút tiếp theo. Những burst không có bước sóng
rỗi hoặc tuyến rỗi để truyền, nút sẽ lưu trữ trong bộ đệm burst và định tuyến truyền
chúng ở lận nhận BCP ti
ếp theo.
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 2.1 dưới đây chỉ ra một cách hiển
OH
BCI
Khác
Cờ

Thông tin về
burst và
thông tin sử
dụng bước sóng
Loại L
BCP
… Sửa lỗi Chèn
Đánh dấu
L
B
k
t
sAs
Đánh dấu

…
L
Ib
(
k+1
)
B
(
k+1
)

λ
w
P
B
(
k+1
)
A
s
A
d

Tuyến
t
sAm
…

t
sAd

i
-…- A
n
P
B1λ1
… t
Sa1
…t
sAn
… t
San

… … … … … … … …
B
kλ1
L
Buλ1
A
1
-…- A
N
P
Bkλ1
t
Sa1
t
sAn
t
San


… t
sAn
… t
San

Thông tin trong bảng được sắp xếp theo trật tự trừ trái qua phải và từ trên
xuống dưới. Thông tin trong bảng cho thấy, bước sóng λ
1
đang được sử dụng để
truyền k burst là
B
1λ1
,…, B
1λk
. Burst B
1λ1
có độ dài L
B1λ1
, chỉ số ưu tiên P
B1λ1
,
truyền trên tuyến (A
i
-…A
k
), bit đầu tiên của burst được phát đi từ nút nguồn A
i
ở
thời điểm t
Sa1

tới chất lượng của mạng đó và điều này cũng không ngoại lệ với mạng OBS.
Thông thường một bài toán về định tuyến và gán bước sóng trong mạng OBS được
chia thành hai phần là bài toán
định tuyến và bài toán gán bước sóng, tuy được chia
thành hai phần riêng như vậy nhưng chúng lại ràng buộc chặt chẽ với nhau do tính
chất “ánh sáng liên tục” trên một đường dẫn quang bên trong mạng OBS, có nghĩa
là trên một đường dẫn quang nhất định chỉ tồn tại một bước sóng tương ứng với
một kênh dữ liệu (tất nhiên trên một đường dẫn quang tồn tại nhiều hơn 2 bước
sóng vẫn có thể xảy ra khi t
ại nút mạng có bộ chuyển đổi bước sóng). Do vậy công
việc định tuyến trong mạng OBS khác với công việc định tuyến trong các mạng
khác (mạng IP, mạng ATM,…) vì còn phải quan tâm tới tài nguyên bước sóng.
3.1.1. Định tuyến trong mạng OBS
Trong mạng OBS thì bài toán định tuyến bị ràng buộc bởi hai điều kiện đặc
biệt sau đây: thứ nhất là OBS thực hiện định tuyến tại nút đầu vào và thứ hai là
công tác định tuyến trong OBS không bi
ết rõ được lưu lượng trên tuyến đã thiết lập
(hay còn gọi là việc định tuyến “mù” tại nguồn), có nghĩa là nút đầu vào thực hiện
định tuyến cho các burst truyền từ đầu vào đến đầu ra mà không biết trước được
lưu lượng trên tuyến truyền dẫn này, không biết trước được tính liên tục bước sóng
trên tuyến. Do vậy, việc định tuyến OBS không được biết rõ về lưu lượng của
mạng nên đây cũng là một sự giới hạn đáng kể đối với mạng OBS.
Có thể phân loại việc định tuyến trong mạng OBS thành hai loại sau: định
tuyến mà tuyến truyền dẫn không thể thay đổi trong suốt quá trình truyền burst hay
có thể gọi là “định tuyến cố định” và định tuyến mà tuyến truyền dẫn có thể thay
đổi được trong quá trình truyền burst dữ liệu hay có thể gọi là “định tuyế
n linh
hoạt”.
3.1.2. Gán bước sóng trong mạng OBS
Gán bước sóng trong mạng OBS chính là việc lựa chọn một bước sóng để

pháp “điền ô trống” để đặt lịch truyền burst. Khác với gán bước sóng ngay lập tức,
nếu không có bước sóng rỗi thỏa mãn thì burst sẽ bị “rớt”, khi sử dụng lựa chọn
bước sóng theo phương pháp “đ
iền ô trống” tại nút biên nguồn, ngoài việc truy vấn
bước sóng rỗi tại thời điểm xét thì còn có thể lựa chọn những “khoảng rỗi” của
bước sóng đã được đặt lịch truyền burst (lúc này burst dữ liệu được đệm tại bộ đệm
điện tử). Hình 3.2 dưới đây sẽ minh họa cho việc lựa chọn bước sóng theo phương
pháp “điền ô trống”.

Hình 3.2: Các khoảng “bận, rỗi” của các bước sóng tại đầu ra nút biên nguồn
λ
1
λ
2
λ
w
t
t
t
“khoảng bận”, phục vụ truyền burst
“khoảng rỗi”
t
0
t

hoặc cấu trúc mạng mesh có ch
ứa vòng hai hướng với số nút trong vòng là số chẵn,
thì khi sử dụng DA sẽ lựa chọn nhiều đường dẫn đi qua một số liên kết trong mạng
hơn số liên kết còn lại, có nghĩa là trên một số liên kết trong mạng sẽ thường xuyên
phải chịu tải nhiều hơn một số liên kết còn lại trong mạng.

3.2.2 Thuật toán “định tuyến linh hoạt”
Thuật toán “định tuyến linh hoạt” sẽ là một chiến lược thay thế tốt hơn trong
mạng OBS khi các thuật toán “định tuyến cố định” gặp phải sự cố trên, khi nó giải
quyết được các vấn đề về tranh chấp burst và giảm thiểu khả năng mất burst. Sau
đây là thuật toán “định tuyến linh hoạt” dựa trên nguyên tắc của chiến lược định
tuy
ến lệch hướng [40] gọi là thuật toán định tuyến “Nút kế cận thỏa mãn tiếp theo”
(NAN Algorithm – Next Available Neighbour Algorithm).
Hình 3.5 dưới đây miêu tả hoạt động của chiến lược định tuyến lệch trong
một mạng OBS. Khi nút 2 và nút 3 cùng lúc truyền một burst tới nút 6 mà đều sử
dụng chung liên kết 5-6, do vậy liên kết 5-6 phải chịu sự tranh chấp của 2 burst 18
này. Thay vì phải đánh rớt một trong hai burst (burst nào có mức ưu tiên thấp hơn)
thì tại nút 5 sẽ cố gắng thực hiện làm “lệch hướng” (hay chuyển tuyến) cho một
trong hai burst tới nút 4 rồi tiếp tục gửi tới nút 6.

Hình 3.5: Sơ đồ miêu tả định tuyến lệch trong mạng OBS, là nền tảng trong hoạt động của
thuật toán định tuyến NAN [40]
3.3. Định tuyến và gán bước sóng đồng thời với giao thức CSP
3.3.1. Bài toán định tuyến và gán bước sóng đồng thời trong mô hình mạng OBS
cấu hình mesh sử dụng giao thức báo hiệu xoay vòng CSP.
Như đã giới thiệu tại phần 2.3, chương 2 về giao thức báo hiệu xoay vòng

tiên và thông tin sử dụng bước sóng của B
k
như bước sóng sử dụng truyền B
k
,
tuyến truyền dẫn, thời gian burst B
k
đến mỗi nút trong tuyến,…
Với yêu cầu như vậy, nếu ta sử dụng những thuật toán định tuyến tìm đường
ngắn nhất (như DA, EDA) hay thuật toán NAN và các thuật toán gán bước sóng đã
trình bày ở trên thì vẫn tồn tại khả năng xảy ra tranh chấp burst do vậy thông tin
cập nhật vào BCP sẽ không đạt được yêu cầu của giao thức CSP là giao thức
không tranh chấp tài nguyên truyền burst. Do vậy giải pháp đặt ra đó là tại nút A
i

sẽ thực hiện định tuyến và gán bước sóng đồng thời, có nghĩa là A
i
sẽ truy vấn toàn
bộ thông tin có liên quan đến việc truyền burst từ A
i
đến A
j
bao gồm thông tin về 19
toàn bộ các tuyến nối từ A
i
đến A
j

BCP
= const) trên tất cả các
nút trong mạng. Tại nút 1 sẽ thực hiện truy vấn toàn bộ thông tin bên trong BCP có
liên quan đến việc truyền burst từ nút 1 đến nút 6 gồm toàn bộ các tuyến đường từ
nút 1 đến nút 6 và toàn bộ thông tin về các burst dữ liệu đã được xếp lịch truyền
λ
0

λ
0

λ
0

λ
0

λ
0
λ
0

λ
0
λ
0
λ
0

λ

đã được đăng ký trước trong BCI mà đi qua các liên kết nói trên. Hình 3.8 dưới
đây miêu tả các khoảng thời gian phục vụ truyền các burst trên từng nút, chỉ xét
các burst thuộc các tuyến đi qua nút đó đến nút kế tiếp trong khoảng thời gian một
chu kỳ truyền BCP đối với bước sóng λ
w
, ta có thể thấy được các khoảng trống hay
khoảng rỗi tại mỗi nút, trên mỗi liên kết đó, từ đó để tìm ra các khoảng trống tương
ứng trên cả tuyến. Từ các khoảng trống tìm được này ta sẽ so sánh với khoảng thời
gian chiếm dụng của burst cần dùng để quyết định có truyền được burst đó trong
các khoảng trống nói trên hay không. Hình 3.8: Minh họa thời gian chiếm dụng bước sóng λ
w
của các burst qua mỗi nút
trên các liên kết của tuyến truyền dẫn 1Æ2Æ3Æ6
t
0
t
t
t

f2#2-3
t
s3#2-3
t
s4#2-3
t
f4#2-3
t
s5#2-3
t
f5#2-3
t
s1#3-6
t
f1#3-6
t
f2#3-6
t
f3#3-6
t
s4#3-6
t
f4#3-6
Nút 6
tuyến 1-2-3-6
Nút 1
tuyến X-1-2-Y
t
s2#3-6
Khoảng thời gian burst

có hai khoảng trống tương ứng với hai khoảng thời gian tại nút 1 có thể sử dụng
được để truyền burst dữ liệu trên toàn tuyến trên mà thôi.
Như ta thấy trên hình 3.8, khi nút 1 phát đi các burst dữ li
ệu đến nút 2 trên
“liên kết 1” phải mất một khoảng thời gian Δt
1
thì bit đầu tiên của burst mới đến
được nút 2, thời gian này chính là thời gian truyền dẫn của sóng ánh sáng trên
đường truyền từ nút 1 đến nút 2. Tương tự như vậy thời gian truyền dẫn trên các
liên kết 2Æ3 và 3Æ6 lần lượt là Δt
2
, Δt3. Vì vậy phải thực hiện tính toán chính xác
các khoảng cách của các liên kết trong mạng để đưa ra các thông số thời gian trễ
cho từng liên kết (trong mạng thực tế, các tham số Δt
i
này có thể có được một cách
chính xác bằng cách đo cụ thể), từ đó điều kiện đầu của “bài toán cơ sở” sẽ chặt
chẽ và chính xác.
Sau khi ta đã có được các thông tin đầu vào của “bài toán cơ sở” như thời
gian trễ truyền dẫn trên các liên kết, thời gian phát và truyền các burst qua các nút
trên tuyến đã cho, vấn đề cần giải quyết bây giờ đó là làm sao để kết hợp được các
khoảng b
ận trên từng liên kết lại với nhau lại thành một “khoảng bận chung” cho
toàn tuyến từ đó sẽ tìm được những “khoảng rỗi chung” của tuyến. Như trên hình
3.8, giải pháp đưa ra đó là chuyển các mốc thời gian trên các nút trung gian về
cùng một mốc thời gian tại nút biên nguồn (nút 1) và rõ ràng việc dịch chuyển các
khoảng thời gian trên các nút trung gian về cùng một mốc thời gian tại nút 1 không
ảnh hưởng đến kết quả tìm khoảng trố
ng thích hợp cần truyền, lúc này thời gian
truyền dẫn trên các liên kết bằng không, từ đó ta có thể làm giảm được các điều

Hình 3.9: Minh họa việc xếp chồng các khoảng bận tại từng nút trên mỗi liên kết thuộc
tuyến 1Æ2Æ3Æ6 sau khi đã dịch trái thời gian các khoảng bận
Từ hình 3.9 ta có thể thấy được t
si#j-k
là thời điểm bit đầu tiên của burst dữ
liệu thứ i bắt đầu đi từ nút j tới nút k và t
fi#j-k
là thời điểm bit cuối cùng của burst dữ
liệu thứ i bắt đầu đi từ nút j tới nút k (các thông tin này có được từ BCI). Sau khi
các khoảng thời gian được dịch trái trên mỗi nút trung gian như hình 3.9.
Như đã nói ở trên, ta có thể dựa vào mối tương quan giữa các t
si#j-k
và t
fi#j-k

với nhau là có thể tìm ra được các khoảng trống trên toàn bộ tuyến hay nói cách
khác ta sẽ thực hiện xếp chồng các burst trên mỗi liên kết theo một hàng dọc để
tìm ra các khoảng bận chung trên toàn tuyến.
Ta có thể thấy được có tất cả 04 khoảng thời gian tương ứng với thời gian
chiếm dụng của 04 burst trên các liên kết qua các nút (burst 4 trên liên kết 1-2;
burst 5 trên liên kết 2-3; burst 4 và burst 5 trên liên kết 3-6) trùng lặp với nhau một
khoảng thời gian gây ra một khoảng bận chung trên toàn tuyế
n tương ứng với 04
burst đó. Khoảng bận chung này bắt đầu từ thời điểm bit đầu tiên của burst 5 - liên
kết 2-3 và kết thúc tại thời điểm bit cuối cùng của burst 5 - liên kết 3-6, đó là đoạn
[t
s5#2-3
; t
f5#3-6
] và ký hiệu là [τ

τ
sR1
τ
fR1
τ
sR2
τ
fR2
τ
fR3
τ
sR3
t
0
t
t-Δt
1-2
t
t
t
f1#1-2
t
s2#1-2
t
f2#1-2
t
s3#1-2
t
f3#1-2
t

t
f3#3-6
t
s4#3-6
t
f4#3-6
Nút 6
tuyến 1-2-3-6
Nút 1
tuyến X-1-2-Y
Khoảng thời gian burst
chiếm dụng bước sóng
Khoảng thời gian không thể nhận được
burst từ nút 1 trên tuyến 1Æ2Æ3Æ6

t
s1#1-2
t
s4#1-2
t
f1#2-3
t
f3#2-3
t
s3#3-6
t
s2#2-3
t
f2#2-3
t

; τ
fN3
]
Sau đây là các bước giải quyết tổng quát đối với “bài toán cơ sở” theo ví dụ
trên:
1. Phân tích tuyến A
m
Æ
A
n
Æ
A
o
Æ
…
Æ
A
v
Æ
A
w
thành các liên kết cấu tạo nên
tuyến này gồm các liên kết là: (A
m
-A
n
); (A
n
-A
o

+Δt
An-Ao
+…+Δt
Au-Av
. (Với Δt
j-k
là thời
gian truyền dẫn sóng ánh sáng từ nút j đến nút k)
4. Thực hiện xếp chồng các khoảng thời gian (t
si#j-k
; t
fi#j-k
) đã được dịch trái
như trên với nhau để tìm ra các khoảng thời gian bước sóng λ
w
bận trên
toàn tuyến từ đó có được các khoảng rỗi trên toàn tuyến.
Sau khi đã tìm được những khoảng trống thỏa mãn cho việc truyền burst dữ
liệu thì việc còn lại tại nút nguồn đó là kiểm tra thời điểm bắt đầu của khoảng trống
đó (τ
sP
) có thỏa mãn lớn hơn giá trị t
0
+ T
Offset
hay không. Bởi vì đối với bất kỳ
giao thức báo hiệu nào trong mạng OBS đều phải tuân thủ nguyên tắc gói điều
khiển burst phải được gửi đi tới nút đích qua các nút trung gian trước khi thực hiện
truyền burst dữ liệu một khoảng thời gian T
Offset

dụng giao thức CSP.
b. Giải quyết yêu cầu của “bài toán tổng quát” theo các bước sau: