TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010

201
ĐỀ XUẤT PHƯƠNG PHÁP THIẾT KẾ TOPOLOGIC TRONG MẠNG IP
TRÊN NỀN WDM CÓ XEM XÉT YÊU CẦU LƯU LƯỢNG
VÀ SỐ CHẶNG VẬT LÝ
PROPOSAL OF DESIGN METHODS FOR LOGICAL TOPOLOGIES IN
NETWORKS OF IP OVER WDM IN CONSIDERATION OF BOTH THE TRAFFIC
DEMAND AND HOP COUNT OF PHYSICAL ROUTES
Nguyễn Quang Như Quỳnh, Nguyễn Văn Tuấn
Trường Đại học Bách khoa, Đại học Đà Nẵng TÓM TẮT
Những năm gần đây, nhiều phương pháp thiết kế tô pô lô gic trong mạng IP trên nền
WDM (IP/WDM) được nghiên cứu rộng rãi, trong đó thuật toán thiết kế topologic tìm kiếm
(HLDA) và thuật toán tối thiểu độ trễ (MLDA) được xem như là các thuật toán cơ bản sử dụng
mô hình xếp chồng trong mạng IP/WDM [1]. HLDA và MLDA thiết lập các đường quang giữa
các cặp node chỉ dựa trên yêu cầu lưu lượng giữa chúng. Trong bài báo này, chúng tôi đề xuất
hai thu
ật toán mới, thuật toán thiết kế topologic đơn chặng tự do (SHFLDA) và thuật toán thiết
kế topologic đơn chặng ràng buộc (SHCLDA) trong đó chúng thiết lập các đường quang giữa
các cặp node dựa trên cả yêu cầu lưu lượng và số lượng số chặng của đường đi nhỏ nhất
giữa chúng. SHFLDA cho lưu lượng cực đại thấp trên các đường quang sau khi được thiết lập
và SHCLDA cho độ trễ trung bình thấp. Chúng tôi tiến hành so sánh 4 thông số
giữa hai thuật
toán: tổng lưu lượng trên topologic, lưu lượng cực đại trên các đường quang sau khi được thiết
lập, tổng lưu lượng yêu cầu và phần trăm các bước sóng được sử dụng. Kết quả mô phỏng chỉ

khác nhau: đồng đẳng, tăng cường và xếp chồng. Chúng tôi xây dựng hai thuật toán,
mỗi thuật toán tạo một topologic bằng các đường quang (lightpath) như một mạng xếp
chồng lên mạng vật lý WDM, mỗi một đường quang mang lưu lượng IP giữa các node
trong kiến trúc mạng OCS. Như đã đề cập trong phần tóm tắt, hai thuật toán đề xuất
khác với hai thuật toán HLDA và MLDA về tiêu chí để quyết định cặp node nào được
chọn để xử lý trước. HLDA và MLDA không xem xét đến số chặng vật lý giữa các cặp
node, và chỉ xem xét đến lưu lượng giữa các cặp node [3]. Trái lại, hai thuật toán đề
xuất chọn cặp node để xử lý trước dựa trên cả số chặng vật lý giữa các cặp node và lưu
lượng giữa các cặp node đó. Hai thuật toán đề xuất đạt được độ trễ trung bình thấp, giải
quyết được vấn đề cân bằng tải nhờ vào cập nhật tích của yêu cầu lưu lượng và số chặng
vật lý nhỏ nhất giữa các cặp node sau khi đường quang giữa chúng được thiết lập. Giả
thiết rằng số bước sóng trên mỗi kết nối vật lý đều giống nhau.
2. Mô hình mạng
Thiết kế và định tuyến trên topologic này dựa trên các giả thiết cho thông số ngõ
vào như sau:
-Tô pô vật lý cho trước gồm các node có các bộ phát và thu bước sóng, chúng
kết nối với nhau bởi sợi quang. Giả sử số bước sóng là bằng nhau trên mỗi kết nối trực
tiếp và không có sự chuyển đổi bước sóng tại các node.
-Một node gồm có bộ định tuyến điện tử và bộ chuyển mạch quang như hình
1[4].
-Yêu cầu l
ưu lượng giữa các cặp node (i, j) đến theo tiến trình Poison và được
tính theo Gbps và giả thiết luôn có yêu cầu lưu lượng giữa các cặp node.
-Dung lượng truyền dẫn của mỗi bước sóng được thiết lập là 10Gbps.
-Dung lượng xử lý của các bộ định tuyến điện tử luôn lớn hơn lượng lưu lượng
đến tại bộ định tuyến đó.
Bộ tách bước sóng (Wavelength Demux) tách các bước sóng từ tín hiệu quang
sau
đó chúng được chuyển mạch đến đầu ra tương ứng bởi bộ non-blocking switch mà
không có sự chuyển đổi bước sóng. Các bước sóng này lại được ghép trở lại trên sợi


Hình 1. Mô hình kiến trúc của node[5]
N
Y
Y
Kết thúc
N

Tìm cặp node có giá trị lớn nhất trong ma trận F
Tìm đường đi vật lý ngắn nhất giữa cặp node đó .
Số bước sóng trên các liên kết vật lý đã sử dụng giảm đi
1 khi lightpath giữa cặp node này được thiết lập.
Tìm cặp node có giá trị lớn kế tiếp trong ma trận F và cập nhật ma trận F
Tính s
ố
chặng vật lý nhỏ nh
ấ
t của từng cặp node(i, j): hij
Tạo ma trận F: Fij=qij*hij
Các cặp node
đ
ư
ợ
cxét h

ij
=q
ij
* h
ij
. Thuật toán SHFLDA chọn cặp node (i, j) sao cho có giá trị F
ij
lớn nhất để
thiết lập đường quang và sử dụng độ trễ để xác định đường đi của nó. SHFLDA chọn
đường đi từ node i đến node j sao cho độ trễ giữa chúng là nhỏ nhất bằng thuật toán tìm
đường ngắn nhất Dijkstra.
Thuật toán đề xuất này được đặt tên là SHFLDA là thuật toán thiết kế topologic
đơn chặng vì nó thiết lập các đường quang đơn chặng, nghĩa là mỗi đường quang chỉ sử
dụng một bước sóng có sẵn trên liên kết vật lý mà nó đi qua, chữ F (Free) trong
SHFLDA ngụ ý việc bước sóng có sẵn được sử dụng trên mỗi liên kết vật lý khi có yêu
cầu thiết lập đường quang; điều này khác với thuật toán đề xuất thứ hai: SHCLDA được
trình bày như dưới đây.
3.2. Thuật toán SHCLDA

205
Thuật toán đề xuất thứ 2 được gọi là SHCLDA, trong đó C là “Constraint” nghĩa
là thiết lập các lightpath giữa các cặp node nối trực tiếp trước, và sau đó thiết lập các
lightpath giữa các cặp node còn lại tương tự như thuật toán SHFLDA.

4. Đánh giá kết quả
4.1. Mô hình mô phỏng và kết quả mô phỏng
Các thuật toán HLDA và MLDA không được so sánh với các thuật toán đề xuất
vì chúng không giống nhau về tiêu chí để quyết định cặp node nào được chọn để xử lý
trước.
Thực hiện thiết kế topologic với cùng các thông số ngõ vào sử dụng hai thuật
toán SHFLDA và SHCLDA, tiến hành so sánh bốn thông số được đánh số 1, 2, 3, và 4
c
ủa hai thuật toán thể hiện qua đồ thị hình cột như hình 5.
- Thông số 1: Tổng lưu lượng trên tô pô lô gic là tổng lưu lượng trên các đường
quang sau khi thiết lập.
- Thông số 2: Là tổng lưu lượng yêu cầu giữa các cặp node.
- Thông số 3: Lưu lượng cực đại của trên các đường quang được thiết lập.


4.2. Nhận xét
Ở hình 5(a) và 5(b), thuật toán SHFLDA hiệu quả hơn khi cho giá trị tổng lưu
lượng trên topologic thấp hơn so với thuật toán SHCLDA. Điều này được giải thích là
do số đường quang được thiết lập bởi SHFLDA để mang các lưu lượng có giá trị lớn
giữa các cặp node không có kết nối trực tiếp giữa chúng nhiều hơn bởi SHCLDA vì
SHFLDA ưu tiên chọn cặp node có giá trị Fij lớn nhất để xử lý trước. Trái lại SHCLDA
ưu tiên chọn các cặp node có kết nối vật lý trực tiếp đề xử lý trước. Trái lại, ở hình 5(c),
thuật toán SHFLDA ít hiệu quả hơn khi cho giá trị tổng lưu lượng trên topologic cao
hơn so với thuật toán SHCLDA vì do giới hạn số bước sóng trên mỗi liên kết và số yêu
(a) (b)
(c) (d)
Hình 5. So sánh bốn thông số của SHFLDA và SHCLA trong mạng gồm:
+ 4 node, 3 bước sóng trên mỗi kết nối vật lý
+ 9 node, 3 bước sóng trên mỗi kết nối vật lý
+ 14 node, 3 bước sóng trên mỗi kết nối vật lý
+ 14 node, 6 bước sóng trên mỗi kết nối vật lý
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010

207
cầu kết nối trong mạng tăng. Nhưng khi tăng số bước sóng trên mỗi kết nối vật lý lên 6

[3] Junichi Katou, Shin’ichi Arakawa, and Masayuki Murata, “A design method
of logical topology for IP over WDM networks with stable routing”, ONDM 2001,
February 2001.
[4] Yukinobu Fukushi ma, Shin’ichi Arakawa, Masayuki Murata and Hideo
Miyahara, “Design of Logical Topology for Minimizing the Number of Fiber
Amplifiers”, Osaka University, Osaka 560-8531 Japan, 2002.
[5] Yukinobu Fukushima, “Physical and Logical Design of Flexible and Scalable
Wavelength-Routed Networks”, Depart ment of Information Networking
Graduate School of Information Science and Technology Osaka University,
January 2006.