Luận án Giải quyết bài toán định tuyến đảm bảo băng thông, độ trễ

 BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
CAO THÁI PHƯƠNG THANH 
GIẢI QUYẾT BÀI TOÁN ĐỊNH TUYẾN 
ĐẢM BẢO BĂNG THÔNG, ĐỘ TRỄ 
LUẬN ÁN TIẾN SĨ KỸ THUẬT 
HÀ NỘI – 2017 
BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
CAO THÁI PHƯƠNG THANH 
GIẢI QUYẾT BÀI TOÁN ĐỊNH TUYẾN 
ĐẢM BẢO BĂNG THÔNG, ĐỘ TRỄ 
Chuyên ngành: Hệ thống thông tin 
Mã số: 62.48.01.04 
LUẬN ÁN TIẾN SĨ KỸ THUẬT 
 NGƯỜI HƯỚNG DẪN KHOA HỌC: 
1. PGS. TS. TRẦN CÔNG HÙNG 
2. PGS. TS. HÀ HẢI NAM 
HÀ NỘI – 2017 
iLỜI CAM ĐOAN
Nghiên cứu sinh cam đoan nội dung luận án này là kết quả nghiên cứu của bản thân
dưới sự hướng dẫn của PGS. TS. Trần Công Hùng và PGS.TS. Hà Hải Nam. Các kết
quả và số liệu trình bày trong luận án là trung thực, một phần đã được công bố trong
các công trình của nghiên cứu sinh và chưa được công bố trong công trình khoa học
của tác giả khác. Tất cả tham khảo từ những nghiên cứu liên quan đều được nêu rõ
trong danh mục tài liệu tham khảo ở phần sau của luận án.
Người cam đoan
Cao Thái Phương Thanh
ii
LỜI CẢM ƠN
Để hoàn thành được luận án này, đầu tiên, nghiên cứu sinh chân thành cảm ơn sự
hướng dẫn khoa học và tận tình giúp đỡ của Thầy giáo, PGS. TS. Trần Công Hùng
và PGS. TS. Hà Hải Nam. Nghiên cứu sinh trân trọng cảm ơn Ban Giám đốc Học
viện Công nghệ Bưu chính Viễn thông, Hội đồng Tiến sĩ, Khoa Quốc tế và Đào tạo
Sau Đại học đã tạo điều kiện thuận lợi cho nghiên cứu sinh thực hiện và hoàn thành
chương trình nghiên cứu. Xin cảm ơn các Thầy, Cô đã đọc và đóng góp ý kiến cho
luận án.
Nghiên cứu sinh chân thành cảm ơn Ban Giám hiệu trường Đại học Sài Gòn và
Ban Tổ chức Thành ủy Thành phố Hồ Chí Minh đã tạo điều kiện công tác thuận lợi
và hỗ trợ kinh phí để nghiên cứu sinh tham gia và hoàn thành khóa đào tạo.
Cuối cùng, nghiên cứu sinh bày tỏ lòng biết ơn sâu sắc và muôn vàn tình yêu đến
ba, mẹ, vợ, con, những người thân, những người bạn đã luôn bên cạnh, động viên và
ủng hộ nghiên cứu sinh trong suốt thời gian qua.
Nghiên cứu sinh
Cao Thái Phương Thanh
iii
MỤC LỤC
Lời cam đoan i
Lời cảm ơn ii
Danh mục các chữ viết tắt, các kí hiệu vi
Danh mục các bảng ix
Danh mục các hình xi
MỞ ĐẦU 1
NỘI DUNG 6
Chương 1. TỔNG QUAN VỀ ĐỊNH TUYẾN ĐẢM BẢO CHẤT LƯỢNG
DỊCH VỤ 6
1.1 CHẤT LƯỢNG DỊCH VỤ . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . 6
1.2 ĐỊNH TUYẾN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Phân loại . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Một số hướng nghiên cứu phổ biến . . . . . . . . . . . . . . 10
1.3 ĐỊNH TUYẾN ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ . . . . . . . 11
1.4 KẾT CHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Chương 2. BÀI TOÁNĐỊNHTUYẾNUNICASTĐẢMBẢOBĂNGTHÔNG
VÀ ĐẢM BẢO BĂNG THÔNG, ĐỘ TRỄ 13
2.1 ĐỊNH NGHĨA BÀI TOÁN . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Phát biểu bài toán và kí hiệu sử dụng . . . . . . . . . . . . . 13
2.1.2 Điều kiện thực hiện bài toán định tuyến và các giả sử . . . . 15
2.1.3 Các độ đo đánh giá hiệu quả thuật toán định tuyến . . . . . . 18
2.2 CÁC THUẬT TOÁN ĐỊNH TUYẾN ĐẢM BẢO BĂNG THÔNG
LIÊN QUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
iv
2.2.1 Nhóm thuật toán lựa chọn đường đi dựa trên thông số từng
liên kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Nhóm thuật toán lựa chọn đường đi hạn chế ảnh hưởng . . . 21
2.2.3 Nhóm thuật toán áp dụng máy học . . . . . . . . . . . . . . 25
2.3 CÁC THUẬT TOÁNĐỊNH TUYẾNĐẢMBẢOBĂNGTHÔNGVÀ
ĐỘ TRỄ LIÊN QUAN . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Thuật toán LDA . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2 Thuật toán MDWCRA . . . . . . . . . . . . . . . . . . . . 28
2.3.3 Thuật toán MDMF . . . . . . . . . . . . . . . . . . . . . . 30
2.4 KHẢO SÁT THUẬT TOÁN ĐỊNH TUYẾN BẰNG MÔ PHỎNG . 31
2.4.1 Mô phỏng thuật toán định tuyến đảm bảo băng thông bằng ns2 31
2.4.2 Chương trình mô phỏng thuật toán định tuyến trên .NET Frame-
work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.3 Sơ đồ mạng và bộ yêu cầu định tuyến thử nghiệm . . . . . . 35
2.4.4 So sánh, đánh giá thuật toán định tuyến bằng mô phỏng . . . 38
2.5 KẾT CHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Chương 3. THUẬT TOÁN ĐỊNH TUYẾN ĐẢM BẢO BĂNG THÔNG 40
3.1 BGHT: THUẬT TOÁN ĐỊNH TUYẾN ĐẢM BẢO BĂNG THÔNG
SỬ DỤNG THỜI GIAN GIỮ BĂNG THÔNG . . . . . . . . . . . . 40
3.1.1 Thuật toán đề xuất BGHT . . . . . . . . . . . . . . . . . . 40
3.1.2 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.3 Phân tích hoạt động . . . . . . . . . . . . . . . . . . . . . . 45
3.2 TEARD: THUẬTTOÁNĐỊNHTUYẾNĐẢMBẢOBĂNGTHÔNG
SỬ DỤNG DỮ LIỆU ĐỊNH TUYẾN . . . . . . . . . . . . . . . . . 46
3.2.1 Thuật toán đề xuất TEARD . . . . . . . . . . . . . . . . . . 46
3.2.2 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.3 Phân tích hoạt động . . . . . . . . . . . . . . . . . . . . . . 51
3.3 KẾT QUẢ MÔ PHỎNG . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.1 Kết quả khi thay đổi tham số yêu cầu thử nghiệm . . . . . . 54
Đặc điểm kết quả thử nghiệm . . . . . . . . . . . . . . . . . 54
Thay đổi băng thông yêu cầu . . . . . . . . . . . . . . . . . 57
Thay đổi số cặp nguồn đích . . . . . . . . . . . . . . . . . . 61
v3.3.2 Kết quả trên số lượng lớn bộ yêu cầu định tuyến . . . . . . . 64
Kịch bản định tuyến tĩnh . . . . . . . . . . . . . . . . . . . 65
Kịch bản định tuyến động, điều kiện tải bình thường . . . . . 68
Kịch bản định tuyến động, điều kiện tải cao . . . . . . . . . 71
3.3.3 Kết quả khi thay đổi tham số thuật toán đề xuất . . . . . . . 74
3.4 KẾT CHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Chương 4. THUẬT TOÁN ĐỊNH TUYẾN ĐẢM BẢO BĂNG THÔNG VÀ
ĐỘ TRỄ 78
4.1 HRABDC: THUẬT TOÁN ĐỊNH TUYẾN HEURISTIC ĐẢM BẢO
BĂNG THÔNG VÀ ĐỘ TRỄ . . . . . . . . . . . . . . . . . . . . . 78
4.1.1 Thuật toán đề xuất HRABDC . . . . . . . . . . . . . . . . . 78
4.1.2 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 80
4.1.3 Phân tích hoạt động . . . . . . . . . . . . . . . . . . . . . . 84
4.2 TĂNG CƯỜNG KHẢ NĂNG TÌM ĐƯỜNG ĐI CÓ TRỌNG SỐ
NHỎ CHO DIJKSTRA HEURISTIC . . . . . . . . . . . . . . . . . 86
4.2.1 Cải tiến thuật toán tìm đường Dijkstra heuristic . . . . . . . 86
4.2.2 Thuật toán định tuyến eHRABDC . . . . . . . . . . . . . . 88
4.3 KẾT QUẢ MÔ PHỎNG . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.1 Thử nghiệm thuật toán định tuyến . . . . . . . . . . . . . . 90
Kết quả mô phỏng trên sơ đồ MIRA . . . . . . . . . . . . . 90
Kết quả mô phỏng trên sơ đồ CESNET . . . . . . . . . . . . 93
Kết quả mô phỏng trên sơ đồ ANSNET . . . . . . . . . . . 96
4.3.2 Thử nghiệm phương pháp tính trọng số và tìm đường đi . . . 99
4.4 KẾT CHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
KẾT LUẬN VÀ KIẾN NGHỊ 105
Danh mục các công trình đã công bố của nghiên cứu sinh 107
Tài liệu tham khảo 109
PHỤ LỤC 116
vi
DANHMỤC CÁC CHỮ VIẾT TẮT
BCRA Bandwidth Constrained Routing Al-
gorithm
Tên một thuật toán định tuyến
BGHT Bandwidth Guaranteed routing algo-
rithm using Holding Time
Tên một thuật toán định tuyến
BGMRA Bandwidth Guaranteed MPLS Rout-
ing Algorithm
Tên một thuật toán định tuyến
CSPF Constrained Shortest Path First Tên một thuật toán định tuyến
DiffServ Differentiated Services Tên một mô hình đảm bảo chất lượng
dịch vụ
DORA Dynamic Online Routing Algorithm Tên một thuật toán định tuyến
eHRABDC enhanced Heuristic Routing Algo-
rithm with Bandwidth Delay Con-
straints
Tên một thuật toán định tuyến
HRABDC Heuristic Routing Algorithm with
Bandwidth Delay Constraints
Tên một thuật toán định tuyến
IGRP Interior Gateway Routing Protocol Tên một giao thức định tuyến
IntServ Integrated Services Tên một mô hình đảm bảo chất lượng
dịch vụ
IP Internet Protocol Tên một giao thức mạng máy tính
LDA Least Delay Algorithm Tên một thuật toán định tuyến
M-MDWCRA Modified Maximum Delay Weighted
Capacity Routing Algorithm
Tên một thuật toán định tuyến
MDMF Minimum Delay and Maximum Flow Tên một thuật toán định tuyến
MDWCRA Maximum Delay Weighted Capacity
Routing Algorithm
Tên một thuật toán định tuyến
MHA Minimum Hop Algorithm Tên một thuật toán định tuyến
MIRA Minimum Interference Routing Algo-
rithm
Tên một thuật toán định tuyến
MPLS Multi Protocol Label Switching Tên một kĩ thuật mạng máy tính
vii
MPLS TE Multi Protocol Label Switching Traf-
fic Engineering
Tên một kĩ thuật mạng máy tính
OC Optical Carrier Mức truyền dẫn cáp quang
OSI Open Systems Interconnection Tên một mô hình mạng máy tính
POOA Paths Optimal Ordering Algorithm Tên một thuật toán định tuyến
QoS Quality Of Service Khái niệm chất lượng dịch vụ trong
mạng máy tính
RIP Routing Information Protocol Tên một giao thức định tuyến
RRATE Random Race based Algorithm for
Traffic Engineering
Tên một thuật toán định tuyến
RSVP Resource Reservation Protocol Tên một giao thức mạng máy tính
TEARD Traffic Engineering routing algorithm
using Routing Data
Tên một giao thức định tuyến
viii
DANHMỤC CÁC KÍ HIỆU
SLYC Số lượng yêu cầu
TC Tỉ lệ chấp nhận yêu cầu định tuyến
TT Thời gian tính toán định tuyến trung bình
ĐT Độ lệch chuẩn tải liên kết
b(l) Băng thông còn lại của liên kết l
c(l) Dung lượng băng thông của liên kết l
d(l) Độ trễ của liên kết l
w(l) Trọng số của liên kết l
G(N,L) Đồ thị biểu diễn sơ đồ mạng
N Tập hợp k nút mạng
L Tập hợp m liên kết
SD Tập hợp các cặp nút nguồn đích sd
r(s,d,b) Yêu cầu định tuyến từ s đến d với lượng băng thông b cần đảm bảo
r(s,d,β ,δ ) Yêu cầu định tuyến từ s đến d với lượng băng thông β và độ trễ δ cần đảm bảo
psd Một đường đi từ s đến d
pr(s,d,b) Đường đi psd thỏa yêu cầu r(s,d,b)
pr(s,d,β ,δ ) Đường đi psd thỏa yêu cầu r(s,d,β ,δ )
P(sd) Tập hợp tất cả đường đi từ s đến d
ix
DANHMỤC CÁC BẢNG
2.1 Kí hiệu được sử dụng trong bài toán . . . . . . . . . . . . . . . . . 15
2.2 Các bước tổng quát thuật toán định tuyến đảm bảo băng thông . . . 27
3.1 Thuật toán BGHT . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Thuật toán TEARD . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Độ phức tạp của thuật toán định tuyến đảm bảo băng thông . . . . . 52
3.4 Kết quả định tuyến tĩnh, sơ đồ CESNET với băng thông yêu cầu thay
đổi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5 Kết quả trung bình 300 bộ yêu cầu định tuyến tĩnh . . . . . . . . . . 65
3.6 Kết quả trung bình 300 bộ yêu cầu định tuyến động, điều kiện tải thường 69
3.7 Kết quả trung bình 300 bộ yêu cầu định tuyến động, điều kiện tải cao 72
3.8 Kết quả một thử nghiệm định tuyến tĩnh, sơ đồ CESNET, sau 1000
yêu cầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.9 Kết quả một thử nghiệm định tuyến động, điều kiện tải cao, sơ đồ
ANSNET, sau 5000 yêu cầu . . . . . . . . . . . . . . . . . . . . . . 76
4.1 Thuật toán HRABDC . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.2 Độ phức tạp của thuật toán định tuyến đảm bảo băng thông và độ trễ 85
4.3 Thuật toán eHRABDC . . . . . . . . . . . . . . . . . . . . . . . . 89
4.4 Kết quả trung bình thử nghiệm trên sơ đồ MIRA . . . . . . . . . . . 90
4.5 Kết quả trung bình thử nghiệm trên sơ đồ CESNET . . . . . . . . . 94
4.6 Kết quả trung bình thử nghiệm trên sơ đồ ANSNET . . . . . . . . . 97
xDANHMỤC CÁC HÌNH
2.1 Ví dụ mô hình hóa bài toán định tuyến đảm bảo băng thông [27] . . 15
2.2 Mô hình MPLS TE thực hiện bài toán định tuyến đảm bảo băng thông 17
2.3 Mô hình MPLS TE với máy chủ định tuyến [63] . . . . . . . . . . . 18
2.4 Giá trị trọng số liên kết MIRA cho yêu cầu r1(1,5,1) . . . . . . . . 22
2.5 Ví dụ trọng số khác nhau của thuật toán MIRA và NewMIRA . . . . 23
2.6 Mô hình mô phỏng thuật toán định tuyến . . . . . . . . . . . . . . . 32
2.7 Mô hình định tuyến đảm bảo băng thông với MNS 2.1 và QOSPF
trong ns2 [63] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.8 Các thành phần của chương trình mô phỏng thuật toán định tuyến . . 34
2.9 Mô hình định thời gian trong việc xử lý và kết thúc yêu cầu . . . . . 35
2.10 Sơ đồ mạng thử nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 36
2.11 Một ví dụ biểu đồ so sánh độ đo các thuật toán từ [11] . . . . . . . . 39
3.1 Ví dụ định tuyến liên quan đến thời gian giữ băng thông . . . . . . . 41
3.2 Kết quả ví dụ minh họa thuật toán BGHT . . . . . . . . . . . . . . 45
3.3 Ví dụ minh họa thuật toán TEARD . . . . . . . . . . . . . . . . . . 49
3.4 Kết quả ví dụ minh họa thuật toán TEARD . . . . . . . . . . . . . . 51
3.5 Kết quả định tuyến động, điều kiện tải thường, sơ đồ MIRA . . . . . 55
3.6 Kết quả định tuyến động, điều kiện tải cao, sơ đồ ANSNET với băng
thông yêu cầu thay đổi . . . . . . . . . . . . . . . . . . . . . . . . 59
3.7 Kết quả định tuyến tĩnh, sơ đồ CESNET với số cặp nguồn đích thay đổi 62
3.8 Kết quả trung bình 100 bộ yêu cầu định tuyến tĩnh, sơ đồ MIRA . . 67
3.9 Kết quả trung bình 100 bộ yêu cầu định tuyến động, điều kiện tải
thường, sơ đồ CESNET . . . . . . . . . . . . . . . . . . . . . . . . 70
3.10 Kết quả trung bình 100 bộ yêu cầu định tuyến động, điều kiện tải cao,
sơ đồ ANSNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1 Kết quả ví dụ minh họa thuật toán HRABDC . . . . . . . . . . . . . 83
4.2 Kết quả ví dụ minh họa Dijkstra mở rộng . . . . . . . . . . . . . . . 85
4.3 Ví dụ Dijkstra heuristic cải tiến . . . . . . . . . . . . . . . . . . . . 88
xi
4.4 So sánh tỉ lệ chấp nhận yêu cầu của thử nghiệm định tuyến động, điều
kiện tải cao, sơ đồ MIRA . . . . . . . . . . . . . . . . . . . . . . . 91
4.5 So sánh thời gian tính toán định tuyến trung bình của thử nghiệm định
tuyến tĩnh, sơ đồ MIRA . . . . . . . . . . . . . . . . . . . . . . . . 92
4.6 So sánh độ lệch chuẩn tải liên kết của thử nghiệm định tuyến động,
điều kiện tải thường, sơ đồ MIRA . . . . . . . . . . . . . . . . . . . 93
4.7 So sánh tỉ lệ chấp nhận yêu cầu của thử nghiệm định tuyến động, điều
kiện tải thường, sơ đồ CESNET . . . . . . . . . . . . . . . . . . . . 95
4.8 So sánh thời gian tính toán định tuyến trung bình của thử nghiệm định
tuyến động, điều kiện tải cao, sơ đồ CESNET . . . . . . . . . . . . 95
4.9 So sánh độ lệch chuẩn tải liên kết của thử nghiệm định tuyến tĩnh, sơ
đồ CESNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.10 So sánh tỉ lệ chấp nhận yêu cầu của thử nghiệm định tuyến tĩnh, sơ đồ
ANSNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.11 So sánh thời gian tính toán định tuyến trung bình của thử nghiệm định
tuyến động, điều kiện tải thường, sơ đồ ANSNET . . . . . . . . . . 98
4.12 Một kết quả thử nghiệm kết hợp phương pháp tính trọng số và tì ... rk (CESNET), Czech Republic, pp. 3–18.
[46] Ogier R., Rutenburg V., Shacham N. (1993), “Distributed algorithms for comput-
ing shortest pairs of disjoint paths”, IEEE Transactions on Information Theory
39(2), pp. 443–455.
[47] Oommen B. J., Misra S., Granmo O.-C. (2007), “Routing Bandwidth-Guaranteed
Paths in MPLS Traffic Engineering: A Multiple Race Track Learning Ap-
proach”, IEEE Transactions on Computers 56(7), pp. 959–976.
113
[48] Pant R., Sanguankotchakorn T. (2010), “A heuristic approach for bandwidth con-
straint path selection in MPLS based networks”, International Conference on
Electrical Engineering/Electronics Computer Telecommunications and Infor-
mation Technology, ECTI-CON 2010, Thailand, pp. 909–913.
[49] Porwal M. K., Yadav A., Charhate S. (2008), “Traffic Analysis of MPLS and Non
MPLS Network including MPLS Signaling Protocols and Traffic Distribution
in OSPF and MPLS”, First International Conference on Emerging Trends in
Engineering and Technology, ICETET 08, IEEE, pp. 187–192.
[50] Pushpavalli M., Natarajan A. M. (2012), “Quality of Service in Mobile Adhoc
Networks using Two Bandwidth Estimation Method in Optimized Link State
Routing protocol”, International Journal of Computer Science and Network
Security 12(1), pp. 98–105.
[51] Qadir J., Ali A., Yau K. L. A., Sathiaseelan A., Crowcroft J. (2015), Exploiting
the power of multiplicity: a holistic survey of network-layer multipath, ArXiv
e-prints.
[52] Rocha M., Sousa P., Cortez P., Rio M. (2011), “Quality of Service constrained
routing optimization using Evolutionary Computation”, Applied Soft Comput-
ing 11(1), pp. 356–364.
[53] Rutgers C. L. H. (2005), An Introduction to IGRP, CISCO Technology white pa-
per, CISCO.
[54] Sahoo S. P., Kabat M. R., Sahoo A. K. (2011), “Tabu Search Algorithm for Core
Selection in Multicast Routing”, International Conference on Communication
Systems and Network Technologies, CSNT 2011, IEEE, USA, pp. 17–21.
[55] Sang-Woon Jeon, Kyomin Jung, Hyunseok Chang (2014), “Fully Distributed Al-
gorithms for Minimum Delay Routing Under Heavy Traffic”, IEEE Transac-
tions on Mobile Computing 13(5), pp. 1048–1060.
[56] Scoglio C., Anjali T., Cavalcante de Oliveira J., Akyildiz I., Uhl G. (2004), “TEAM:
a traffic engineering automated manager for diffserv-based MPLS networks”,
IEEE Communications Magazine 42(10), pp. 134–145.
[57] Singh A., Mittal G. (2000), QoS and Traffic Engineering: MPLS, DiffServ and
Constraint Based Routing, BSc thesis, Indian Institute of Technology, India.
114
[58] Smit H., Li T. (2004), Intermediate System to Intermediate System (IS-IS) Exten-
sions for Traffic Engineering (TE), RFC 3784, IETF.
[59] Soorki M. N., Rostami H. (2014), “Label switched protocol routing with guaran-
teed bandwidth and end to end path delay in {MPLS} networks”, Journal of
Network and Computer Applications 42, pp. 21–38.
[60] Stiliadis D., Varma A. (1998), “Latency-rate Servers: A General Model for Analy-
sis of Traffic Scheduling Algorithms”, IEEE/ACM Transactions on Networking
6(5), pp. 611–624.
[61] TanenbaumA. S. (2011),Computer networks, 5th ed, Pearson Prentice Hall, Boston.
[62] Tran C. H., Le Q. C., Tran T. T. M. (2010), “A study on Any transport over
MPLS (AToM)”, The 12th International Conference on Advanced Communi-
cation Technology, ICACT 2010, IEEE, Korea, pp. 64–70.
[63] Tran C. H., Nguyen H. T., Nguyen D. T., Jung H. W., Kim T. I., Kim S. H., Yang
W. J. (2007), “Advanced Routing Algorithms and Load Balancing on MPLS”,
The 9th International Conference on Advanced Communication Technology,
ICACT 2007, IEEE, Korea, pp. 1886–1891.
[64] Turky A. A., Mitschele-Thiel A. (2009), “MPLS Online Routing Optimization
Using Prediction”, Network Control and Optimization, Springer Berlin Heidel-
berg, Berlin, Heidelberg, pp. 45–52.
[65] Wang B., Su X., Chen C. (2002), “A new bandwidth guaranteed routing algorithm
for MPLS traffic engineering”, International Conference on Communications,
ICC 2002, IEEE, USA, pp. 1001–1005.
[66] Wang N., Ho K., Pavlou G., Howarth M. (2008), “An overview of routing op-
timization for internet traffic engineering”, IEEE Communications Surveys &
Tutorials 10(1), pp. 36–56.
[67] Wang Z., Crowcroft J. (1995), “Bandwidth-delay based routing algorithms”,Global
Telecommunications Conference, GLOBECOM 1995, IEEE, Singapore, pp. 2129–
2133.
[68] Wang Z., Crowcroft J. (1996), “Quality-of-service routing for supporting multime-
dia applications”, IEEE Journal on Selected Areas in Communications 14(7),
pp. 1228–1234.
115
[69] Wisniewski L., Schumacher M., Jasperneite J., Diedrich C. (2014), “Linear time,
possibly disjoint path search approach for ethernet based industrial automation
networks”, Emerging Technology and Factory Automation, ETFA 2014, IEEE,
Spain, pp. 1–9.
[70] Wroclawski J. (1997), The Use of RSVP with IETF Integrated Services, RFC 2210,
IETF.
[71] Xu Y. (2011), Metaheuristic Approaches for QoS Multicast Routing Problems,
PhD thesis, University of Nottingham, Nottingham, UK.
[72] Xu Y., Qu R. (2012), “A hybrid scatter search meta-heuristic for delay-constrained
multicast routing problems”, Applied Intelligence 36(1), pp. 229–241.
[73] Xuan L., Ying L. (2008), “L-MMIRA: LightMulticast Minimal Interference Rout-
ing Module in MPLS Network”, Seventh International Conference on Network-
ing, ICN 2008, IEEE, Mexico, pp. 421–426.
[74] Yang Y., Muppala J., Chanson S. (2001), “Quality of service routing algorithms
for bandwidth-delay constrained applications”, Ninth International Conference
on Network Protocols, ICNP 2001, IEEE, USA, pp. 62–70.
[75] Yang Y., Zhang L., Muppala J. K., Chanson S. T. (2003), “Bandwidth–delay con-
strained routing algorithms”, Computer Networks 42(4), pp. 503–520.
[76] Yen J. Y. (1971), “Finding the K Shortest Loopless Paths in a Network”,Manage-
ment Science 17(11), pp. 712–716.
[77] Younis O., Fahmy S. (2003), “Constraint-based routing in the internet: Basic prin-
ciples and recent research”, Communications Surveys Tutorials, IEEE 5(1),
pp. 2–13.
[78] Zahary A., Ayesh A. (2010), “An analytical review for multipath routing in Mobile
Ad Hoc Networks”, International Journal of Ad Hoc and Ubiquitous Comput-
ing 5(2), p. 69.
[79] Zhang L., Cai L.-b., Li M., Wang F.-h. (2009), “A method for least-cost QoS
multicast routing based on genetic simulated annealing algorithm”, Computer
Communications 32(1), pp. 105–110.
116
PHỤ LỤC A. CHƯƠNG TRÌNH MÔ PHỎNG ĐỊNH TUYẾN
ĐẢM BẢO BĂNG THÔNG, ĐỘ TRỄ
A.1 Thiết kế chương trình mô phỏng trên .NET Framework
Chức năng của chương trình mô phỏng thuật toán định tuyến bao gồm:
• Đọc vào sơ đồ mạng và bộ dữ liệu định tuyến được lưu dưới dạng tập tin văn bản.
• Thực hiện định tuyến cho mỗi yêu cầu bằng các thuật toán định tuyến được cài
đặt thành các lớp đối tượng.
• Xuất ra kết quả định tuyến cũng như kết quả thống kê của mỗi bộ yêu cầu dưới
dạng tập tin phân cách giá trị bằng dấu phẩy (.csv).
• Chạy tự động kết hợp nhiều bộ yêu cầu với nhiều thuật toán định tuyến.
Hình A.1 trình bày sơ đồ lớp chính của chương trình mô phỏng.
Network Component là thành phần mô phỏng sơ đồ mạng, có ba lớp đối tượng:
• Lớp Topology thể hiện sơ đồ mạng. Mỗi đối tượng Topology có một danh sách
nút mạng (kiểu lớp Node), một danh sách liên kết (kiểu lớp Link), và một tập hợp
các cặp nút nguồn đích.
• Lớp Node thể hiện nút mạng, mỗi nút có chứa một danh sách liên kết xuất phát
từ chính nó.
• Lớp Link thể hiện liên kết, có các thuộc tính như dung lượng, băng thông còn
lại, nút đầu, nút cuối.
Routing Component là thành phần cài đặt thuật toán với hai thành phần con:
• Common Algorithms gồm các lớp cài đặt thuật toán dùng chung như thuật toán
tìm đường đi có trọng số nhỏ nhất Dijkstra, thuật toán tính luồng cực đại Fork-
Fulkerson [15], thuật toán Yen tìm k đường đi ngắn nhất [76]...
• Routing Algorithms gồm các lớp cài đặt thuật toán định tuyến liên quan như
MHA, MIRA, RRATE, MDMF... và các thuật toán của nghiên cứu sinh đề xuất
BGHT, TEARD, HRABDC (sẽ được trình bày chi tiết ở chương sau).
Simulator Component là thành phần thực hiện mô phỏng, có các lớp đối tượng:
• Lớp Request thể hiện yêu cầu định tuyến với các thông tin nút nguồn, nút đích,
băng thông yêu cầu, thời điểm đến của yêu cầu, thời gian giữ băng thông. Đối
với bài toán đảm bảo băng thông và độ trễ thì có thêm độ trễ yêu cầu.
• Lớp Response mô phỏng kết quả đáp ứng yêu cầu. Mỗi đối tượng Response
117
Hình A.1: Sơ đồ lớp chính của chương trình mô phỏng
118
tương ứng với một đối tượng Request, chứa thông tin đường đi tìm được, thời
gian xử lý của thuật toán, thời điểm kết thúc (để giải phóng tài nguyên mạng).
• Lớp Ticker và giao diện ITickerListener thực hiện cơ chế bộ định thời gian của
chương trình mô phỏng, trong đó mỗi lần hàm callback Ticker::OnTimedEvent
được gọi thì tính là đã qua một đơn vị thời gian mô phỏng.
• Lớp RequestDispatcher chứa bộ yêu cầu định tuyến và thực thi giao diện ITick-
erListener để gửi yêu cầu đến thuật toán định tuyến dựa trên thời điểm đến của
yêu cầu.
• Lớp ReponseManager chứa bộ kết quả ứng với những yêu cầu đã xử lý, thực thi
giao diện ITickerListener để giải phóng băng thông dựa trên thời điểm kết thúc
yêu cầu định tuyến.
• Lớp Simulator chứa các hàm chương trình để thực hiện quá trình mô phỏng.
• Lớp Configuration dùng để đọc thông tin cấu hình được lưu dưới dạng tập tin
XML.
Cuối cùng, thành phần Statistics gồm lớp Log để ghi vết quá trình thử nghiệm, và
lớp Statistics dựa trên kết quả ReponseManager::ResponseForStatistics để thống kê
tỉ lệ chấp nhận yêu cầu, thời gian tính toán trung bình, độ lệch chuẩn tải liên kết và
xuất kết quả thống kê thành tập tin csv.
Hình A.2 và hình A.3 lần lượt trình bày sơ đồ thiết kế tuần tự của việc xử lý yêu
cầu định tuyến và kết thúc yêu cầu.
119
Hình A.2: Sơ đồ tuần tự chức năng gửi yêu cầu đến thuật toán định tuyến
Hình A.3: Sơ đồ tuần tự chức năng kết thúc yêu cầu
120
A.2 Một số màn hình kết quả thử nghiệm
Xét ví dụ hình A.4, sơ đồ mạng có 11 nút, 2 cặp nguồn - đích, thử nghiệm với2
yêu cầu định tuyến r1 = (0,4,1) và r2 = (5,8,1). Thuật toán MHA chọn đường đi
ngắn nhất cho yêu cầu r1: pr1 = (0,6,7,4) nên yêu cầu thứ hai không thể đáp ứng vì
liên kết (6− 7) không còn đủ băng thông. Trong khi thuật toán MIRA chọn đường
đi cho r1 là pr1 = (0,1,2,3,4) nên tiếp tục đáp ứng được yêu cầu r2 với đường đi
pr2 = (5,6,7,8). Hình A.5 thể hiện quá trình thử nghiệm trên ns2, trong khi hình A.6
thể hiện cùng một kết quả trên chương trình mô phỏng .NET Framework.
Hình A.4: Ví dụ thử nghiệm thuật toán định tuyến
121
(a) Kết quả thuật toán định tuyến MHA
(b) Kết quả thuật toán định tuyến MIRA
Hình A.5: Thử nghiệm trên ns2
122
(a) Kết quả thuật toán định tuyến MHA
(b) Kết quả thuật toán định tuyến MIRA
Hình A.6: Thử nghiệm chương trình mô phỏng trên .NET Framework
123
PHỤ LỤC B. VÍ DỤ MINH HỌA TỪNG BƯỚC CÁC PHƯƠNG
PHÁP TÌM ĐƯỜNG TRONG BÀI TOÁN ĐỊNH TUYẾN ĐẢM
BẢO BĂNG THÔNG VÀ ĐỘ TRỄ
B.1 Dijkstra mở rộng và Dijkstra heuristic
Ví dụ từng bước thực hiện của hai phương pháp tìm đường Dijkstra mở rộng và
Dijkstra heuristic trên cùng một hệ thống mạng.
(a) Sơ đồ mạng
(b) Bỏ liên kết không đảm bảo băng thông và tính trọng số
Hình B.1: Sơ đồ mạng được sử dụng làm ví dụ
124
(a) Giá trị khởi tạo Dijkstra mở rộng. Thông tin trên mỗi liên kết (trọng số, độ trễ)
(b) Xét mục có w nhỏ nhất en00, cập nhật hai mục en
1
1 và en
2
1. (Mục en
2
1 lưu vết đường đi từ 0
đến 2, có độ trễ bằng 1 và trọng số bằng 2)
125
(c) Xét mục có w nhỏ nhất kế tiếp en01, cập nhật hai mục en
1
2 và en
2
2
(d) Tương tự xét en02, cập nhật en
1
3 và en
2
3
126
(e) Xét en03, không cập nhật mục nào vì không thỏa điều kiện độ trễ
(f) Xét en11 (w nhỏ nhất kế tiếp), cập nhật en
3
3
127
(g) Xét en12, không cập nhật mục nào ở nút liền kề 3 vì không thỏa điều kiện độ trễ. Xét en
1
3
có kết quả tương tự
(h) Xét w nhỏ nhất kế tiếp en21, cập nhật mục en
3
2 và en
4
3
128
(i) Tiếp tục xét en22, cập nhật en
3
3 vì trọng số nhỏ hơn giá trị đã lưu. Không cập nhật mục ở
nút 4 vì không thỏa điều kiện độ trễ
(j) Xét en23, không cập nhật mục nào vì không thỏa điều kiện độ trễ
129
(k) Xét w nhỏ nhất kế tiếp en32, cập nhật en
5
3
(l) Xét en33, không cập nhật mục nào vì không thỏa điều kiện độ trễ
130
(m) Xét en43, không cập nhật mục nào vì không thỏa điều kiện độ trễ
(n) Xét en53, không cập nhật mục nào vì không có liên kết từ nút 5
131
(o) Xét en10, không cập nhật mục nào vì không thỏa điều kiện trọng số. Kết quả tương tự khi
xét các mục có w= ∞ khác
(p) Thuật toán kết thúc khi duyệt hết 24 mục, tìm được đường đi pri = (0,2,3,5)
Hình B.2: Kết quả từng bước của Dijkstra mở rộng cho ví dụ B.1
132
(a) Khởi tạo Dijkstra heuristic. Thông tin trên mỗi liên kết là (trọng số, độ trễ)
(b) Xét mục có w nhỏ nhất en0 (tại nút 0), cập nhật mục en2. Mục en1 không được cập nhật
vì không thỏa điều kiện độ trễ
(c) Xét mục w nhỏ nhất tiếp theo en2, cập nhật mục en3. Mục en4 không được cập nhật vì
không thỏa điều kiện độ trễ
133
(d) Xét mục tiếp theo en3, cập nhật mục en5
(e) Xét tiếp các mục en5, en1, en4, không có mục nào được cập nhật vì không thỏa điều kiện
trọng số. Thuật toán kết thúc khi duyệt hết nút, tìm được đường đi pri = (0,2,3,5)
.Hình B.3: Kết quả từng bước của Dijkstra heuristic cho ví dụ B.1
B.2 Dijkstra heuristic và Dijkstra heuristic cải tiến
Hình B.4 ví dụ một trường hợp Disjktra heuristic không tìm được đường đi nhỏ
nhất; sau đó hình B.5 thể hiện kết quả áp dụng Dijkstra heuristic cải tiến để tìm được
đường đi có trọng số nhỏ hơn.
134
(a) Khởi tạo Dijkstra heuristic, đã bỏ các liên kết không đảm bảo băng thông. Thông tin trên
mỗi liên kết là (trọng số, băng thông). Yêu cầu định tuyến ri(0,5,1,4)
(b) Xét mục w nhỏ nhất en0, cập nhật en1, en2
(c) Xét mục w nhỏ nhất kế tiếp en1, cập nhật en3
135
(d) Xét mục w nhỏ nhất kế tiếp en2, vì không thỏa điều kiện trọng số (w3 < w2+w(l23)) nên
không cập nhật en3, dẫn đến sẽ không tìm được đường đi trọng số nhỏ nhất
(e) Xét mục w nhỏ nhất kế tiếp en3, cập nhật en5. en4 không được cập nhật vì không thỏa điều
kiện độ trễ
136
(f) Tiếp tục xét en5 (w= 7) và en4 (w= ∞), không cập nhật mục nào. Thuật toán kết thúc với
đường đi tìm được p1 = (0,1,3,5) (trong khi đường p2 = (0,2,3,4,5) có trọng số nhỏ hơn).
Hình B.4: Ví dụ Dijkstra heuristic không tìm được đường đi trọng số nhỏ nhất
(a) Bỏ liên kết trọng số lớn nhất l35 từ đường đi p1 = (0,1,3,5) đã tìm được. Tiếp tục thực
hiện Dijkstra heuristic trên sơ đồ mạng còn lại
137
(b) Kết quả Dijkstra heuristic tìm được đường đi p2 = (0,2,3,4,5)
(c) Bỏ liên kết trọng số lớn nhất l23 từ đường đi p2 = (0,2,3,4,5) tìm được. Tiếp tục thực hiện
Dijkstra heuristic và không tìm được đường đi thỏa điều kiện độ trễ. Quá trình tìm đường kết
thúc và lựa chọn đường đi có trọng số nhỏ hơn p2 = (0,2,3,4,5).
Hình B.5: Áp dụng Dijkstra heuristic cải tiến tiếp theo ví dụ hình B.4