Chương 4: Thực hiện mô phỏng
CHƯƠNG 3
ĐỊNH TUYẾN TRONG MẠNG IP/WDM
3.1. Giới thiệu chương
Trong mạng IP/WDM, người sử dụng liên lạc với nhau qua các kênh thông tin
quang được gọi là các lightpath. Lightpath là một đường đi của tín hiệu ánh sáng từ
nguồn đến đích dưới dạng quang thông qua các kết nối trung gian. Một lightpath có
thể kéo dài qua nhiều tuyến truyền dẫn để cung cấp một kết nối chuyển mạch giữa
hai node mà có thể chứa một luồng lưu lượng lớn giữa chúng.
Khi các lightpath thực hiện việc mang thông tin từ một node nguồn đến một
node đích nào đó thì nó cần được định tuyến. Định tuyến cho lightpath là vấn đề hết
sức quan trọng và xảy ra thường xuyên trong mạng.
Chương này sẽ nói rõ về việc định tuyến trong mạng IP/WDM.
3.2. Các giao thức định tuyến IP
3.2.1. Khái niệm: Định tuyến IP là quá trình chuyển lưu lượng người dùng từ nguồn
đến đích. Trong mạng, bộ định tuyến (router) là thiết bị dùng để định tuyến cho lưu
lượng. Router cần dựa vào bảng định tuyến để tìm ra tuyến đường chuyển gói tin đi.
Bảng định tuyến thường gồm ba thành phần chính là kiểu giao thức mạng, địa
chỉ mạng đích và giao diện gói ra.
3.2.2. Chức năng:
- Đóng gói và phân tán các thông tin trạng thái lưu lượng người dùng và mạng.
Gồm vị trí hiện tại và các yêu cầu dịch vụ người dùng, các dịch vụ được cung cấp
và tài nguyên sẵn có trong mạng.
- Tạo ra và lựa chọn các đường thích hợp dựa trên các thông tin trạng thái của người
dùng và mạng. Con đường thích hợp là con đường thoả được tất cả các yêu cầu giữa
người dùng và mạng.
- Chuyển tiếp lưu lượng người dùng trên các con đường đã chọn, lưu lượng có thể
được chuyển tiếp theo hướng kết nối hay không kết nối.
3.2.3. Phân loại định tuyến
Có nhiều cách phân loại định tuyến, có thể đưa ra một số loại định tuyến sau:
Chương 4: Thực hiện mô phỏng

định của nhà quản lý mạng.
+ Trong định tuyến tĩnh, các tuyến được thiết lập thủ công, mỗi khi mạng có sự cố
hoặc cấu hình mạng thay đổi thì quản trị mạng phải thiết lập lại tuyến mới. Hiện
nay hầu hết các nước trên thế giới đều sử dụng định tuyến thay thế,
phương pháp này được mô tả như hình 3.2. Trước tiên tổng đài sẽ chọn hướng ưu
tiên 1 để định tuyến cuộc gọi, nếu không định tuyến được trên hướng này thì sẽ
chọn đến hướng có mức ưu tiên thấp hơn và quá trình cứ thế được tiếp tục.
Chương 4: Thực hiện mô phỏng
Hình 3.2: phương pháp chọn Router thay thế
b. Định tuyến động: Định tuyến động lựa chọn tuyến dựa trên thông tin trạng thái
hiện thời của mạng. Thông tin trạng thái có thể đo hoặc dự đoán và tuyến đường có
thể thay đổi khi topo mạng thay đổi hoặc lưu lượng mạng thay đổi. Định tuyến động
thể hiện tính linh hoạt và dễ dàng mở rộng mạng.
* Ưu điểm của định tuyến động :
Hình 3.3: có thể tự thay thế tuyến hỏng bằng các tuyến khác
Định tuyến động lựa chọn tuyến dựa trên thông tin trạng thái hiện thời của mạng.
Thông tin trạng thái có thể đo hoặc dự đoán và tuyến đường có thể thay đổi khi topo
Chương 4: Thực hiện mô phỏng
mạng hoặc lưu lượng mạng thay đổi. Thông tin định tuyến cập nhật vào trong các
bảng định tuyến của các node mạng trực tuyến, và đáp ứng tính thời gian thực nhằm
tránh tắc nghẽn cũng như tối ưu hiệu năng mạng. Ưu điểm lớn nhất của định tuyến
động là nó có thể thiết lập tuyến đường tới tất cả các thiết bị trong mạng, tự động
thay đổi tuyến đường khi cấu hình mạng thay đổi. Nó rất thích hợp cho:
. Thêm thiết bị và địa chỉ mới vào mạng.
. Loại bỏ thiết bị và địa chỉ khỏi mạng.
Các giao thức định tuyến động cũng có thể chuyển lưu lượng từ cùng một phiên làm
việc qua nhiều đường đi khác nhau trong mạng để có hiệu suất cao hơn. Tính chất
này được gọi là chia sẻ tải (load sharing).
- Nhược điểm của định tuyến động :
Trong mạng phức hợp sử dụng định tuyến động, một mạng có thể bị tái tạo lại cấu

+ Để cho phép sự phát triển và làm cho các mạng tại các đơn vị dễ quản lý, OSPF
cho phép phân chia các mạng và các bộ định tuyến thành các tập hợp con ( khu
vực). Mỗi khu vực là riêng biệt, cấu hình cũng được che dấu với các khu vực khác,
như vậy tính mềm dẻo của mạng sẽ được tăng lên.
+ Giao thức OSPF xác định rằng tất cả những trao đổi giữa các bộ định tuyến có thể
được xác minh. OSPF cho phép có những mô hình khác nhau, và thậm chí cho phép
một khu vực được quyền chọn một mô hình riêng biệt với mô hình khác.
+ OSPF cho phép các mạng đa truy xuất có một cổng được chỉ định, để gửi đi các
bản tin trạng thái liên kết, đại diện cho tất cả các bộ định tuyến đấu vào mạng này.
+ Để cho phép độ ổn định tối đa, OSPF cho phép người quản lý mô tả cấu hình
mạng ảo tách biệt với mạng vật lý.
+ OSPF cho phép bộ định tuyến trao đổi thông tin định tuyến học được từ bên
ngoài. Định dạng của bản tin cho phép phân biệt được thông tin học từ mạng ngoài
hoặc từ nội bộ mạng.
OFPS dùng định tuyến trạng thái liên kết nên dùng metric dựa trên băng thông và
thuật toán Dijkstra để xây dựng bảng định tuyến. OFPS được dùng để định tuyến
Chương 4: Thực hiện mô phỏng
trong một vùng hay giữa nhiều vùng. OSPF có độ hội tụ nhanh và được đặc tả chi
tiết trong RFC 2328.
Hình 3.4: sử dụng OSPF nội vùng và liên vùng
* Giao thức định tuyến EIGRP :
The Enhanced Interior Gateway Routing Protocol (EIGRP) được phát triển từ
IGRP. Kết quả của sự phát triển này xuất phát từ những thay đổi bên trong hệ thống
mạng, nhằm đáp ứng được yêu cầu của người sử dụng và đặc biệt là sự mở rộng
ngày một lớn của các liên mạng.
EIGRP có khả năng kết hợp được cả hai phương pháp định tuyến tĩnh và động cùng
hoạt động đan xen, hay nói cách khác EIGRP sử dụng phương pháp định tuyến lai
cân bằng (Balanced Hybrid Routing Protocol). Bên cạnh thuật toán Bellman Ford
EIGRP.
Còn sử dụng thêm thuật toán cập nhật khuếch tán Diffusing-Update-

lihgtpath (DLE-Dynamic Lightpath Establishment), ta xem xét lưu lượng mạng là
động. Các yêu cầu kết nối xuất hiện một cách ngẫu nhiên tùy theo nhu cầu liên lạc
giữa các nút mạng. Các kết nối này được yêu cầu tồn tại trong một khoảng thời
Chương 4: Thực hiện mô phỏng
gian cũng ngẫu nhiên. Vì thế các lightpath không chỉ được thiết lập động mà còn
phải được giải phóng động.
Việc định tuyến và gán bước sóng phụ thuộc vào trạng thái của mạng ở thời
điểm yêu cầu kết nối xảy ra. Mỗi khi có yêu cầu kết nối xuất hiện,các thuật toán D-
RWA phải thực hiện để xem xét liệu tài nguyên mạng có đủ để đáp ứng yêu cầu có
hay không. Nếu có thể thì thực hiện quá trình định tuyến và gán bước sóng tại các
nút trung gian cần thiết để thiết lập lightpath. Còn nếu một yêu càu kết nối không
được đáp ứng do thiếu tài nguyên thì xem như bị nghẽn.
Khi quá trình liên lạc kết thúc,kết nối được giải phóng và vì vậy,bước sóng đã
sử dụng có thể được sử dụng lại cho một kết nối khác. Như vậy ta thấy định tuyến
động tận dụng bước sóng tốt hơn. Về mặt kinh tế,điều này sẽ đem kại lợi nhuận
nhiều hơn cho các nhà kinh doanh mạng, gián tiếp giảm chi phí cho câc thuê bao.
Bài toán D-RWA có thể được khái quát như sau:
Đặc điểm:
- Các yêu cầu kết nối xuất hiện ngẫu nhiên và tồn tại trong một khoảng thời
gian nào đó.
- Việc định tuyến và gán bước sóng phụ thuộc vào trạng thái mạng hiện tại và
phải được thực hiện mỗi khi có yêu cầu kết nối xuất hiện.
Mục tiêu:
- Tận dụng hiểu quả tài nguyên mạng để cực đại hóa xác xuất thiết lập thành
công lightpath hay tối thiểu hóa số yêu cầu bi nghẽn.
Vì nhu cầu phải đáp ứng nhanh với sự thay đổi của mạng, các giải thuật D-
RWA dòi hỏi phải đơn giản, độ phức tạp tính toán càng nhỏ càng tốt. Việc kết hợp
giữa định tuyến và gan bươc sóng là rất khó để giải quyết cùng một lúc. Do đó,
thông thường bài toán D-RWA cũng được chia thành 2 bài toán riêng lẽ: bài toán
định tuyến và bài toán gán bước sóng.

giữa i và j không có liên tiếp trực tiếp thì xem như
ij
W
vô cùng lớn
a
ij
λ
là số lượng
bước sóng rỗi trên liên kết tại thời tập hợp các thông tin về trạng thái liên kết
T
ij
λ
là
tổng số bước sóng có trên liên kết.
Hàm trọng số dựa trên chặng (HW-Hop-basd Weight):
Trong hàm này,
ij
w 1=
. Có nghĩa là các đường được chọn hoàn toàn dựa
trên số lượng chặng (hop) nhỏ nhất. Đường ngắn nhất sẽ là đường có số chặng nhỏ
nhất. Bằng trực quan, ta có thể nhận xét là khi có ít chặng hơn thì khả năng tim
được một bước sóng chung cho tất cả các liên kết trung gian là lớn hơn.
Hàm trọng số dựa trên chặng cách (DW-Distance-based Weight):
ij ij
w d=
với
ij
d
là khoảng cách vật lý giữa hai nút i và j.
ij


a
ij
1
λ
có nghĩa như độ cản trở của một liên kết khi thiết lập một yêu cầu kết nối, càng
có nhiều bước sóng rỗi trên liên kết thì độ cản trở càng thấp,tức khả năng thiết lập
kết nối trên liên kết càng cao. Do đó,
a
ij
1
(1 )
λ
−
là khả năng chấp nhận yêu cầu kết
nối của một liên kết.Vì ta mong muốn cực đại hóa tính sẵn có hoặc độ tin cậy của
Chương 4: Thực hiện mô phỏng
toàn bộ đường dẫn nên cần phải cực đại hóa các giá trị này của các liên kết trung
gian. Do bản chất của thuật toán Dijkstra là ưu tiên cho đường đi nào đó có Trọng
số nhỏ hơn nên hàm trọng lượng phải là phủ định âm của hàm log. Hàm trọng số
này phụ thuộc vào bước sóng rỗi trên liên kết nên có phụ thuộc vào trạng thái
mạng.
Hàm trọng số dựa trên số bước sóng sẵn có và số chặng (HAW – Hop count and
Available wave lengths-based Weight):
a
ij
1
(1 )
ij
w

ta quan niệm rằng số chặng hay số bước sóng sẵn có là quan trọng hơn mà có các
giá trị
α
và
β
phù hợp.
Hàm dựa trên tổng số bước sóng và số bước sóng sẵn có (TAW-Total wavelengths
and Available warelength-based Weight):

log(1 (1 ) )
1
a
a
ij
ij
T
ij
ij
w
χ
λ
λ
− − −


=





λ
−Ρ
. Do đó khi một đường dẫn có
Chương 4: Thực hiện mô phỏng
nhiều liên kết,ta mong muốn cực đại hóa các giá trị
a
ij
(1 )
λ
−Ρ
Của tất cả các liên kết
thuộc đường dẫn đó. Do thuật toán Dijkstra chọn lựa đường đi tối ưu theo trọng số
tăng dần,nên hàm trọng số phải là phủ định âm của hàm log,nghĩa là tối ưu hóa giá
trị này.
Hàm trọng số dựa trên số chặng, tổng số bước sóng và số bước sóng sẵn có
(HTAW-Hop count and Total warelengths and Available warelengths warelengths-
based Weight):

log(1 (1 ) )
a
a
ij
ij
T
ij
ij
w
χ
λ
α β

Sau đây, ta sẽ xét một ví dụ để thấy sự lựa chọn hàm trọng số sẽ dẫn đến các kết
quả định tuyến theo đường đẫn ngắn nhất khác nhau. Xét một tôpô được cho trên
hình 3.6. Giả sử mỗi cạnh của tôpô được gán một nhãn gồm ba tham số (
ij
d
,
a
ij
λ
,
T
ij
λ
)
tương ứng với độ trễ trên liên kết (i,j), số bước sóng sẵn có (rỗi) trên liên kết tổn số
bước sóng trên liên kết.
Chương 4: Thực hiện mô phỏng

Hình 3.6 tôpô mạng sử dụng trong định tuyến với các hàm trọngsố khác nhau
Ta cần xác định đường đi từ nút A đến nút D. Bảng 3.2 cho thấy các đường đi
có thể từ nút A đến nút D và giá trị chi phí trên mỗi đường đi được tính bởi các
hàm trọng số khác nhau. giá trị
α
và
β
được giả sử bằng 1.
Bảng 3.2: Chi phí đường đi khác nhau tính theo cá hàm trọng số khác nhau.
Đường đi Chi phi ứng với các hàm trọng số
HW DW AW HAW TAW HTAW
A-B-C-D 3 30 0.375 3.375 0.181 3.181

sẽ chọn một bước sóng giống nhau dẫn đến một hoặc nhiều kết nối bị nghẽn.
Ví dụ 3.2
Chương 4: Thực hiện mô phỏng
Giả sử ta có 5 nút với 4 liên kết.Mỗi liên kết có thể có 3 bước sóng.
1 2 3 4 5
Giả sử các yêu cầu lightpath là như sau:
{1,3}, {1,2}, {4,5}, {3,5}, {2,4}, {3,4}
Kí hiệu: a b c d e f
Các bước sóng được gán theo giải thuật First-Fit như hình 3.4

Hình 3.7: các bước sóng được gắn bởi giải thuật First-Fit
3.3.2. Warelength Reservation (WR) trong IP/WDM
* Phương pháp DIR:
Trong phương pháp này, đầu tiên nút nguồn bởi gói PROGE về phía nút đích.
Gói PROGE sẽ thu nhập các thông tin về trạng thái bước sóng tại các nút trung gian
mà nó đi qua. Khi nút đích nhận được gói PROGE, nó sẽ có được tất cả thông tin
về việc sử dụng bước sóng tại các liên kết trung gian. Dựa trên các thông tin này,
nút đích thực hiện giải thuật toán gán bước sóng và quyết định chọn một bước sóng
để dành trước. Sau đó nó gởi gói RESV trở ngược về phía nút nguồn. Khi nút
nguồn nhận được gói RESV thì đồng nghĩa với việc lightpath đã được thiết lập
xong, nút nguồn bắt đầu quá trình truyền dữ liệu. Khi kết thúc việc truyền dữ liệu,
nút nguồn cũng đợi một khoảng thời gian timeout trước khi quyết gởi gói REL để
giải phóng lightpath.
Chương 4: Thực hiện mô phỏng
Tuy nhiên quá trình dành trước bước sóng không phải lúc nào cũng thành công.
Với phương pháp này, có thể có ba tình huống thất bại.
Tình huống thất bại thứ nhất, khi gói PROBE đi qua một nút trung gian, nếu tại
nút đó không còn bước sóng nào rãnh thì nút dó sẽ loại bỏ gói PROBE và gửi gói
NACK về báo cho nút nguồn biết quá trình thiết lập đã bị thất bại. Khi này nút
nguồn có thể sử dụng một đường thay thế và truyền lại gói PROBE trên đường mới

CHƯƠNG 4
THỰC HIỆN MÔ PHỎNG
4.1. Giới thiệu chương
Chương 4: Thực hiện mô phỏng
Định tuyến là công việc hết sức quan trọng trong mạng quang WDM, nó thực
hiện tìm đường cho lightpath mang lưu lượng thông tin từ nguồn đến đích với mục
đích tối ưu mạng. Trong chương này, dựa trên phần mềm Visual C++, em mô
phỏng phần định tuyến cho các lightpath với hàm mục tiêu chúng ta có thể tuỳ chọn
như chi phí, độ trễ, lượng lưu lượng… qua các tuyến từ nguồn đến đích. Thuật toán
sử dụng để thực hiện định tuyến là thuật toán Dijkstra.
Các trọng số trên các tuyến không chỉ là độ dài đường đi của tuyến mà tuỳ theo
một tiêu chí nào đó của mạng như chi phí tuyến, độ trễ, băng thông, lưu lượng
thông tin Nếu lấy theo tiêu chí là chi phí thấp nhất thì trọng số trên các tuyến
(cạnh) là chí phí của tuyến đó.
4.2. Giới thiệu về ngôn ngữ Visual C++
Visual C++ là ngôn ngữ lập trình dựa trên nền tảng cơ bản của C++, đó là lập
trình hướng đối tượng. Nếu các bạn đã lập trình trên C++ thì việc xây dựng các ứng
dụng trên Visual C++ rất thuận lợi.
Khi thực hiện lập trình C/C++, để tạo các giao diện phức tạp, trình bày đẹp hoàn
toàn không đơn giản. Nhưng đối với Visual C++ thì việc đó khá đơn giản. Bạn chỉ
cần sử dụng các điều khiển hay xây dựng một menu đưa vào ứng dụng của mình mà
các mã lệnh cần viết không quá dài dòng và phức tạp như trong C/C++.
Trong chương trình mô phỏng của em có thể sử dụng bất kì ngôn ngữ lập trình
nào. Em chọn ngôn ngữ Visual C++ do khả năng của nó tạo giao diện dễ dàng hơn
C/C++.
4.3. Lưu đồ thuật toán
Giả sử bộ định tuyến mô phỏng tìm đường đi với đường đi ngắn nhất qua các
tuyến giữa node nguồn và node đích. Các trọng số trên các cạnh là độ dài của tuyến
thông tin từ node này đến node kia.
Bắt

Chương 4: Thực hiện mô phỏng
Thuật toán sẽ thực hiện tìm đỉnh u trong tập hợp Q mà có giá trị d[u] nhỏ nhất.
Đỉnh này được loại ra khỏi Q và được đưa vào tập S. Tập S chứa một bảng các đỉnh
tạo thành một trong những đường đi ngắn nhất từ s đến node nguồn t nào đó.
Chương 4: Thực hiện mô phỏng
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G]
3 d[v] := infinity // Gán các giá trị ban đầu
4 previous[v] := undefined
5 d[s] := 0 // Khoảng cách từ s đến s bằng 0
6 S := empty set // Thiết lập S là tập hợp rỗng
7 Q := V[G] // Tập Q chứa tất cả các node của đồ thị
8 while Q is not an empty set
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[u] + w(u,v) < d[v]
13 d[v] := d[u] + w(u,v)
14 previous[v] := u
4.4. Kết quả mô phỏng
Thuật toán Dijkstra tìm đường đi ngắn nhất từ node nguồn đến node đích được
thực hiện như sau:
1.Click vào biểu tượng ”THEM NODE” để lấy node ra như sau:
2.Click vào biểu tượng “THEM CANH” để nối các cạnh lại với nhau.
Chương 4: Thực hiện mô phỏng
3.Click vào biểu tượng “DUONG NGAN NHAT” thực hiện tìm đường ngắn nhất
giữa hai cặp node bất kì.

Chương 4: Thực hiện mô phỏng