Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
1
Luận văn
Thuật toán đường
đi ngắn nhất và
rộng nhất WSP

Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
2
Mục Lục
I. Đảm bảo chất lượng dịch vụ định tuyến ........................................................ 3
1.1. Giới thiệu: ................................................................................................. 3
1.2 Kỹ thuật lưu lượng và định tuyến ràng buộc cơ sở ............................... 4
1.3 Các mục tiêu của đảm bảo chất lượng dịch vụ định tuyến .................... 4
1.4 Vị trí của đảm bảo chất lượng dịch vụ định tuyến trong hệ thống mạng
chất lượng dịch vụ........................................................................................... 5
1.4.1 Dịch vụ phân biệt và đảm bảo chất lượng dịch vụ định tuyến ............ 5
1.4.2 MPLS và đảm bảo chất lượng dịch vụ định tuyến ............................... 6
1.4.3 Đảm bảo chất lượng dịch vụ định tuyến với sự dành riêng tài
nguyên. ............................................................................................................. 7
1.4.4 Đảm bảo chất lượng dịch vụ định tuyến với điều khiển tải ............... 9
II.Thuật toán định tuyến .................................................................................... 10
2.1 Lời giới thiệu .......................................................................................... 10
2.2 Ghi chú ..................................................................................................... 10
2.3 Số đo: ....................................................................................................... 10
2.4 Các vấn đề về định tuyến: ...................................................................... 11
2.4.1 Các vấn đề định tuyến số đo đơn ....................................................... 11
2.4.2 các vấn đề định tuyến với một số số đo ............................................. 13
Thuật toán ...................................................................................................... 21
Thuật toán Iwata. ........................................................................................... 23
H-MCOP ......................................................................................................... 25
A* Prune ......................................................................................................... 26
Thuật toán đảm bảo băng thông 1 (WSP). ....................................................... 28
-SWP ............................................................................................................... 28
SDP ................................................................................................................. 28
Thuật toán đảm bảo băng thông 5 (dynamic alternative path)..................... 30
2.6.2 Tóm tắt những thuật toán với ràng buộc băng thông: ........................ 31
2.7 Ràng buộc trễ đầu cuối........................................................................... 32
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
3
I. Đảm bảo chất lượng dịch vụ định tuyến
1.1. Giới thiệu:
OSPF và các giao thức định tuyến động khác luôn luôn đóng gói tin chuyển tiếp
tới đường đi ngắn nhất. Nếu đường đi ngắn nhất không có đủ tài nguyên để đạt
được các yêu cầu. Dịch vụ hợp nhất được hỗ trợ để dự trữ các tài nguyên cho
lưu lượng, nhưng không thể tạo nguồn dự trữ nếu không có đủ tài nguyên dọc
theo đường dẫn tới điểm khởi đầu. Dịch vụ phân biệt cũng được sử dụng với
khả năng tốt nhất để cung cấp dịch vụ yêu cầu là chưa được xác định. Phần bị
mất mát trên hệ thống mạng sẽ có một kỹ thuật có thể tìm thấy đường dẫn, nếu
nó tồn tại, có được yêu cầu tài nguyên khả dụng. Trong trường hợp đó nó có
thể được sử dụng kỹ thuật Dịch vụ phân biệt hay Dịch vụ hợp nhất một cách có
hiệu quả.
Đảm bảo chất lượng dịch vụ định tuyến là lược đồ định tuyến mà những sự cân
nhắc về chất lượng của dịch vụ yêu cầu của một lưu lượng khi đưa ra các quyết
định định tuyến. Tương phản với định tuyến tìm đường ngắn nhất truyền thống,
cái chỉ xem xét việc tính bước truyền, Đảm bảo chất lượng dịch vụ định tuyến
được thiết kế để tìm kiếm những đường đi khả thi mà đáp ứng được nhiều sức
ép. Đảm bảo chất lượng dịch vụ định tuyến là một lược đồ định tuyến, dưới mỗi
tài nguyên có giá trị trên mạng cũng như yêu cầu đảm bảo chất lượng dịch vụ
định tuyến của các lưu lượng. “ Crawley et al.
Phần này giới thiệu các khái niệm cơ bản về kỹ thuật lưu lượng và định tuyến
ràng buộc cơ sở. Sau đó các mục đích của đảm bảo chất lượng dịch vụ định
tuyến sẽ được giới thiệu. Phần còn lại sẽ thảo luận về vị trí của đảm bảo chất
lượng dịch vụ định tuyến trong mạng chất lượng dịch vụ các kỹ thuật có liên
quan đến chất lượng dịch vụ khác.
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
4
1.2 Kỹ thuật lưu lượng và định tuyến ràng buộc cơ sở
Định tuyến đường đi ngắn nhất dẫn đường đến sự phân phối lưu lượng không
đồng đều. Điều này có thể do sự tắc nghẽn ở một số đường đi của mạng ngay cả
khi lưu lượng tải là không mạnh mẽ một cách đặc biệt. Trong khi lược đồ chất
lượng dịch vụ cố gắng để cung cấp dịch vụ tốt hơn dưới sự tắc nghẽn cho các
lưu lượng với các yêu cầu chất lượng dịch vụ, nó thậm chí còn đáng được mong
muốn hơn để tránh các tình huống này. Kỹ thuật lưu lượng được xử lý có chuẩn
bị làm sao để các lưu lượng chảy qua mạng, để tắc nghẽn do sự không đồng đều
trong việc sử dụng mạng có thể tránh được.
Ràng buộc cơ sở định tuyến tiến đến đảm bảo chất lượng dịch vụ định tuyến,
Mặc dù các điều khoản đôi khi được sử dụng hầu như có thể đuợc thay thế cho
nhau, định tuyến ràng buộc cơ sở chính xác là một điều khoản chung hơn, có
thể kết hợp với đảm bảo chất lượng dịch vụ định tuyến và chính sách định
tuyến. Nó kéo dài đến các lược đồ đảm bảo chất lượng dịch vụ định tuyến xét
bởi thực tế, hơn nữa các yêu cầu chất lượng dịch vụ, các ràng buộc khác như
chính sách mạng cũng như các ứng dụng của mạng chống lại các tình huống tải
không đồng dều.
1.3 Các mục tiêu của đảm bảo chất lượng dịch vụ định tuyến
Đảm bảo chất lượng dịch vụ định tuyến sử dụng thông tin về trạng thái mạng và
tài nguyên có giá trị cũng như các yêu cầu chất lượng dịch vụ cả lưu lượng để ra
các quyết định định tuyến. Các mục đích gồm 3 phần:
Sự quyết định động của các đường đi khả thi. Mục đích này có nghĩa là tìm
một đường đi khả thi cho dòng thông tin trong câu hỏi mà có thể cung cấp hoặc
ít nhất là cơ hội tốt để cung cấp các yêu cầu chất lượng dịch vụ của dòng thông
tin.
Tối ưu tài nguyên sử dụng. Chất lượng dịch vụ cơ sở định tuyến có thể được
sử dụng để giúp cho việc cân bằng tải của mạng bởi ứng dụng có hiệu quả của
các tài nguyên, và do đó tăng tổng số thông lượng của mạng.
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
5
Sự giảm hiệu năng uyển chuyển. Trong các tình huống quá tải đảm bảo chất
lượng dịch vụ định tuyến có thể cung cấp thông lượng tốt hơn trong mạng hơn
bất cứ lược đồ định tuyến trạng thái vô tình, và giảm hiệu năng uyển chuyển
hơn nữa.
1.4 Vị trí của đảm bảo chất lượng dịch vụ định tuyến trong hệ thống
mạng chất lượng dịch vụ.
Phần này thảo luận về các mối quan hệ giữa đảm bảo chất lượng dịch vụ định
tuyến và kỹ thuật có liên quan đến chất lượng dịch vụ. Vị trí có liên quan của
các thành phần khác nhau trong khuôn khổ chất lượng dịch vụ được thể hiện
trong bảng sau:
Lớp ứng dụng
Lớp giao vận
Dịch vụ hợp nhất/RSVP , Dịch vụ
phân biệt
Lớp mạng
Constraint Based Routing
Lớp liên kết
MPLS
1.4.1 Dịch vụ phân biệt và đảm bảo chất lượng dịch vụ định tuyến
Thông thường, lược đồ Dịch vụ phân biệt được tách riêng một cách cố ý từ
định tuyến IP, bởi vậy tất cả lưu lượng giữa một cặp nguồn – đích có đi theo
cùng một đường cho dù nó thuộc về lớp dịch vụ nào đó, và Dịch vụ phân biệt tự
nó không có tác dụng trong các quyết định chọn đường. Điều này có nghĩa là
vùng Dịch vụ phân biệt dễ bị tắc nghẽn.
Trường hợp sự tập hợp của lưu lượng tối ưu trong mạng lõi có thể là do sự tắc
nghẽn. Điều này không phải là một vấn đề khi lưu lượng từ bộ định tuyến biên
tập hợp lại ở nhân của bộ định tuyến, từ đó đường dẫn từ bộ định tuyến nhân