Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
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.
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
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
2
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
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
này tới định tuyến nhân tiếp theo sẽ nhanh hơn là các đường dẫn từ bộ định
tuyến lõi đến bộ định tuyến biên. Mặc dù vậy nếu lưu lượng giữa các nhân của
bộ định tuyến trong cùng một bộ định tuyến lõi, đường dẫn mà bộ định tuyến
dẫn lưu lượng tiến đến có thể không đủ nhanh. Vấn đề này không thể giải quyết
chuyển mạch nhãn để chống lại sự tắc nghẽn.
Dựa trên thông tin về lưu lượng liên kết, cấu hình mạng và các tài nguyên, đảm
bảo chất lượng dịch vụ định tuyến tính toán đường đi rõ ràng cho mỗi lưu lượng
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
4
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
liên kết. Các đường rõ ràng ở đây là một sự chỉ rõ chuyển mạch nhãn, đường đi
chuyển mạch nhãn, thoả mãn các yêu cầu của lưu lượng liên kết. Theo lộ trình
định tuyến, MPLS xác lập việc sử dụng giao thức phân phối nhãn của đường đi
chuyển mạch nhãn. Nó không tạo ra sự khác biệt nào so với MPLS cho dù các
tuyến được tính toán với quy tắc tự động, cho phép băng thông có thể, nhưng
các yêu cầu chất lượng dịch vụ của các dòng lưu lượng là không được xem xét.
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.
Sự dành riêng tài nguyên và đảm bảo chất lượng dịch vụ định tuyến là các kỹ
thuật độc lập nhưng bổ sung cho nhau. Đảm bảo chất lượng dịch vụ định tuyến
có thể tìm thấy đường đi khả thi cho các dòng lưu lượng cần đến sự đảm bảo
chất lượng dịch vụ nhưng không thể đảm bảo rằng đường đi sẽ khả thi trong
thời gian còn lại của dòng lưu lượng. Phương thức dành riêng tài nguyên có thể
được sử dụng để xác định tài nguyên yêu cầu theo đường đi đã chọn.
RSVP (Resouce ReSerVation Protocol)
Giao thức thường được đề nghị trong các tài liệu liên quan đến đảm bảo chất
lượng dịch vụ định tuyến và dành riêng tài nguyên là giao thức lưu trữ tài
nguyên. Nó được định hướng bộ nhận, có nghĩa là bộ nhận của dòng dữ liệu
chịu trách nhiệm khởi tạo việc dành riêng tài nguyên. Khi nút nguồn khởi tạo
một dòng, nó gửi một thông tin đường đi đến nút đích xác nhận các kí tự của
dòng cho các tài nguyên được yêu cầu. Điểm trung gian theo thông tin đường đi
đến giao thức định tuyến trong câu hỏi. Sau khi nhận thông tin đường đi PATH,
điểm đích sẽ gửi lại một thông tin RESV để thực hiện việc dành riêng. Các
điểm trung gian quyết định từng phần một cho dù chúng có thể thực hiện yêu
cầu hay không. Nếu một trong các phần này thoát khỏi phần dành riêng, một
Việc chốt đảm bảo cho bất cứ giao thức lưu trữ tài nguyên nào truy vấn đảm
bảo chất lượng dịch vụ định tuyến cho cùng dòng lưu lưọng, nó quay trở lại
đường đi đã chốt thay vì việc tính toán đảm bảo chất lượng dịch vụ định tuyến
đường đi hiện tại tốt nhất.
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
6
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Các đường nhận chốt trong khi xử lý thông tin đường đi. Chúng không được
chốt khi: Hết thời hạn gửi thông báo hay một PATHEAR được gửi. Tham số
của thông tin đường đi bị thay đổi. Phát hiện thấy lỗi.
1.4.4 Đảm bảo chất lượng dịch vụ định tuyến với điều khiển tải
Một trong những mục đích của đảm bảo chất lượng dịch vụ định tuyến là ứng
dụng mạng tốt hơn. Điều này hơi mâu thuẫn với mục đích chính là tìm kiếm
luân phiên đường đi để thực hiện các yêu cầu chất lượng dịch vụ của dòng lưu
lượng. Khi lưu lượng lớn được tải với chỉ những đường dẫn có thể cung cấp sự
đảm bảo chất lượng dịch vụ yêu cầu có thể lâu, đường đi ngắn nhất lưu lượng
được định tuyến dọc theo đường đi luân phiên, một sự phân phối của dòng lưu
lượng đến sự tắc nghẽn của mạng điều khiển đến có nhiều dòng lưu lượng hơn
bị khoá trong tương lai. Điều này gợi đến việc sử dụng điều khiển tải cấp độ cao
hơn để đảm bảo đường đi được chọn không được sử dụng nhiều của tài nguyên
mạng mà tổng thông lượng giảm xuống. Cho mỗi đường dẫn đến phân số tuân
theo đã được tính toán, khi có một sự cố gắng dành riêng:
trong đó B
avaiable i
là thông lượng cho phép trên đường dẫn i nơi mà tài nguyên
được cố gắng để dự trữ, b
requested
là thông lượng yêu cầu của dòng và b
capacity i
là
2
,…,u
i
) và w(P) là tải trọng cho toàn bộ
đường đi.
2.3 Số đo:
Để có thể tìm ra đường đi khả thi mà thoả mãn được yêu cầu chất lượng của lưu
lượng thì phải có một số số đo phù hợp nhằm đo được các yêu cầu. Các số đo
phải được lựa chọn sao cho các yêu cầu có thể được biểu thị bằng một số đo,
hoặc tổng hợp của nhiều số đo thích hợp. Khi các số đo định nghĩa được các
dạng của chất lượng dịch vụ đảm bảo, thì mạng có thể được hỗ trợ. Nếu nó
không thể được sắp xếp trong sự kết hợp của các số đo thì không yêu cầu nào
được hỗ trợ. Các số đo thường được sử dụng trong định tuyến QoS và định
tuyến ràng buộc được chia thành 3 loại, cũng được gọi là các quy tắc cấu tạo
của số đo.
Số đo bao gồm:
Tính cộng: if w(P) = w(u1; u2) + w(u2; u3) + : : : + w(ul¡1; ul)
Tính nhân: if w(P) = w(u1; u2) . w(u2; u3) ………….. w(ul¡1; ul)
Tính lõm: if w(P) = min(w(u1, u2),w(u2, u3),......;w(ul¡1, ul)).
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
8
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Tính cộng bao gồm độ trễ, trễ pha, chi phí và số bước nhảy. Độ tin cậy [(1-tỉ lệ
mất)], là tính nhân, trong khi đó, băng thông, đơn vị được sử dụng nhiều nhất là
tính nhân. Tính cộng bằng cách thay thế các tải trọng liên kết w
i
và ràng buộc c.
Bằng các thuật toán logw
i
và logC.
yêu cầu. Một cách khác là cắt bớt cấu trúc liên kết bằng cách xoá bỏ những liên
kết có băng thông < C, và sau đó tìm ra đường đi ngắn nhất trên cấu trúc liên
kết đã được cắt bớt đó. Từ đó định tuyến liên kết ràng buộc tìm ra được đường
đi thoả mãn được yêu cầu chất lượng dịch vụ cho số đo liên kết ràng buộc.
(không cần thiết phải tối ưu). Ví dụ là tìm ra đường đi có băng thông theo yêu
cầu.
Vấn đề 3 (định tuyến đường đi tối ưu) cho mạng G(N,A) và một tính cộng
đơn w(a) với mỗi liên kết aЄA, tìm đường đi P từ điểm nguồn s tới điểm đích t
sao cho w(P) nhỏ nhất.
vấn đề định tuyến đường đi tối ưu có thể được giải quyết trực tiếp bằng thuật
toán Dijstra hoặc thuật toán Bellman-Ford. Định tuyến đường đi tối ưu tìm ra
đường đi tốt nhất cho một s ố đo đường đi ràng buộc. Một vấn đề điển hình có
thề tìm được đường đi với số bước nhảy ít nhất, tổng chi phí thấp nhất hoặc độ
trễ nhỏ nhất tất cả các giá trị đó là các số đo đường đi ràng buộc vì chúng là
additive.
Vấn đề 4 (định tuyến đường đi ràng buộc) cho mạng G(N,A) và một số đo
additive đơn w(a) với mỗi liên aЄA, v à điều kiện ràng buộc C tìm đường đi P
từ điểm nguồn s tới điểm đích t sao cho w(P)≤C
Vấn đề định tuyến đường đi ràng buộc có thể được giải quyết trực tiếp bằng
thuật toán Dijstra hoặc thuật toán bellman-Ford. Định tuyến đường đi ràng buộc
tìm ra đường đi với độ trễ và chi phí thấp hơn mức yêu cầu.
cả bốn vấn đề nêu trên đều là phức tạp đa thức. Xem phụ lục B.
2.4.2 các vấn đề định tuyến với một số số đo
Thường thì một số tập hợp của nhiều số đo là cần thiết để mô tả các yêu cầu của
dich vụ. Tuy nhiên một số tập hợp tính toán quá phức tạp nên chúng không thực
dụng. Bất kỳ sự kết hợp nào của hai hoặc nhiều hơn số đo, hoặc là tính cộng
hoặc là tính nhân, là NP-complete. Các tập hợp duy nhất cho phép tính toán
đường đi với độ phức tạp đa thức là những tập hợp của số đo tính nhân như
băng thông với các số đo khác, thông dụng nhất là độ trễ hoặc số bước nhảy.
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
Cho mạng G(N,A), số đot ính nhân w
i
(a), i = 1,2; Với mỗi liên kết a thuộc A và
điều kiện ràng buộc C
1
. Tìm đường đi từ điểm nguồn s đến điểm đích t sao cho
w
2
(P) lớn nhất, trong khi w
1
(P)≥ C
1
.
Vấn đề này có thể đưa về dạng 1: vấn đề định tuyến liên kết tối ưu bằng cách
cắt bớt mạng, xoá bỏ tất cả các liên kết mà ràng buộc w1(P) ≥C1 không được đáp
ứng. Sự phức tạp của quá trình cắt bỏ cấu trúc liên kết tỉ lệ với m- số lượng các
liên kết trong mạng, bởi vậy vấn đề liên kết ràng buộc, liên kết tối ưu là thuộc
sự phức tạp đa thức.
+ Vấn đề 6 (định tuyến ràng buộc đa liên kết)
Cho mạng G(N,A), số đo concave w
i
(a), i=1,2; Với mỗi liên kết a thuộc A và điều
kiện ràng buộc C
i
, i=1,2. Tìm đường đi P từ điểm nguồn s đến điểm đích t sao
cho w
i
(P)≥ C
1
với tất cả các giá trị i. Cũng giống vấn đề 5 là đưa về dạng 1 bằng
i
(P) ≥C
1
, w
2
(P)≤ C
2
.
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
12
Copyright: Tài liệu đại học ©