Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Luận văn
Thuật toán đường
đi ngắn nhất và
rộng nhất WSP

Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
1
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Mục Lục
M c L cụ ụ 2
I. m b o ch t l ng d ch v nh tuy nĐả ả ấ ượ ị ụđị ế 2
1.1. Gi i thi u:ớ ệ 2
1.2 K thu t l u l ng v nh tuy n r ng bu c c sỹ ậ ư ượ àđị ế à ộ ơ ở 3
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 .ấ ượ ị ụ 4
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ậ đị ế 9
2.1 L i gi i thi uờ ớ ệ 9
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ấ đềđị ế ớ ộ ố ốđ 12
Thu t toánậ 21
Thu t toán Iwata.ậ 23
H-MCOP 25

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
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.
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
3
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
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

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
được bởi Dịch vụ phân biệt. Đảm bảo chất lượng dịch vụ định tuyến có thể
được sử dụng để tránh tình huống này. Trong một vùng Dịch vụ phân biệt đảm
bảo chất lượng dịch vụ định tuyến được sử dụng để tìm kiếm các đường dẫn có
thể cung cấp các luồng lưu lượng và chống lại sự tắc nghẽn.
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
5
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Một vấn đề khác có thể xảy ra nếu lưu lượng tối ưu không được định tuyến một
cách tối ưu theo thứ tự ưu tiên cho lưu lượng, ưu tiên thấp khi khối lượng lớp
chi phí cao. Đảm bảo chất lượng dịch vụ định tuyến có thể được sử dụng cho
việc cân bằng tải vào khối Dịch vụ phân biệt, do vậy không chỉ lưu lượng tối ưu
mà còn cả lưu lượng lớp thấp hơn có được dịch vụ tốt hơn. Các giải thuật định
tuyến đặc biệt đã đề xuất để định tuyến lưu lượng ưu tiên cao trong một cách
mà xem xét hiệu năng của các lớp lưu lượng khác.
1.4.2 MPLS và đảm bảo chất lượng dịch vụ định tuyến
Từ khi MPLS được lược đồ chuyển tiếp và lược đồ đảm bảo chất lượng dịch vụ
định tuyến, chúng có thể được sử dụng cùng nhau cho các vấn đề về kỹ thuật
lưu lượng. Trong thực tế, MPLS có thể cung cấp thông tin chính xác hơn về lưu
lượng tải hơn là định tuyến IP truyền thống, bởi vậy cho phép đảm bảo chất
lượng dịch vụ định tuyến tính toán đường đi tốt hơn cho việc cài đặt các chyể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
thông báo lỗi sẽ được gửi tới bộ nhận. Nếu việc dành riêng thành công, băng
thông cần thiết và không gian đệm sẽ được xác định. Sau khi kết nối và dành
riêng được thiết lập nguồn gửi một cách định kỳ các thông tin đường đi để thiết
lập hay cập nhật trạng thái, và bộ nhận định kỳ gửi thông tin RESV để thiết lập
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
7
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
hay cập nhật trạng thái dự trữ. Không có thông tin cập nhật việc dành riêng sẽ
kết thúc. Nó được gọi là trạng thái – mềm ( soft-state).
Khi RSVP được sử dụng cùng với đảm bảo chất lượng dịch vụ định tuyến, các
thông tin về đường đi được định tuyến sử dụng đảm bảo chất lượng dịch vụ
định tuyến. Các thông tin RESV và dành riêng trên các tài nguyên sẽ không có
tác dụng bởi giao thức định tuyến. Nhờ có sự tự nhiên động của tiêu chuẩn chọn
đường đi chất lượng dịch vụ định tuyến có thể dễ dàng hơn trong định tuyến
đường đi ngắn nhất. Điều này cho phép băng thông hoặc số đo khác có thể thay
đổi nhanh hơn, để từ đó đường đi đang được chọn sẽ không còn là một với khả
năng tốt nhất để thực hiện dòng lưu lượng. Mỗi sự thay đổi bất ngờ ít khi xảy ra
trong định tuyến đường đi ngắn nhất, kể từ đó cấu hình mạng thường nhiều hơn
hay ít hơn.

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à
tổng dung lượng của đường dẫn i. Việc dành riêng được xác định chỉ nếu phân
số này, đưa ra băng thông cho phép trên đường dẫn nếu việc dành riêng được
chấp nhận, là lớn hơn 1 dự trữ trước, hay băng thông dành riêng. Đường dẫn
càng được sử dụng lâu hơn, thì băng thông dự trữ sẽ cao hơn.
II.Thuật toán định tuyến
2.1 Lời giới thiệu
Chương này thảo luận về chất lượng dịch vụ định tuyến và các thuật toán được
sử dụng để giải quyết chúng. Các vấn đề định tuyến sử dụng một hoặc hai số
đo, và sự phức tạp của chúng cũng sẽ được thảo luận. Chương này đưa ra các
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
9
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
giải pháp cho các vấn đề đơn giản và hướng tiếp cận đối với các vấn đề phức
tạp hơn. Các giải pháp này dựa vào thuật toán đường đi ngắn nhất, thuật toán
Dijkstra và thuật toán Bellman-Ford.
Phần 2.6 thảo luận về tình huống thông thường nhất, khi mà băng thông và
bước nhảy là các số đo.
Phần 2.7 giới thiệu một trường hợp đặc biệt: độ trễ ràng buộc đầu cuối. Nó có
một số đo đơn là chức năng phức tạp của 1 số phần tử.

10
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Tính lõm: if w(P) = min(w(u1, u2),w(u2, u3), ;w(ul¡1, ul)).
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.
2.4 Các vấn đề về định tuyến:
2.4.1 Các vấn đề định tuyến số đo đơn
Trong trường hợp đơn giản nhất, các yêu cầu QoS của lưu lượng được biểu thị
tốt nhất bằng 1 trong các số đo (giới thiệu trong phần 2.3). Vấn đề hoặc là tối
ưu hoặc là ràng buộc. Các số đo được chia thành ràng buộc tuyến và ràng buộc
liên kết. Tính lõm là ràng buộc liên kết vì số đo cho 1 đường đi phụ thuộc giá trị
đoạn nút cổ chai trên liên kết. Tính cộng và tính nhân là ràng buộc tuyến, vì số
đo cho 1 đường đi phụ thuộc vào toàn bộ giá trị của đường đi. Có 4 vấn đề với
số đo đơn.
*) Vấn đề 1: (định tuyến tối ưu liên kết)
Cho mạng G(N,A) và 1 tính nhân đơn w(a) cho mỗi đường liên kết aЄA. Tìm
đường đi P từ nút nguồn s đến nút đích t sao cho w(P) là rộng nhất.
Vấn đề định tuyến liên kết tối ưu có thể được giải quyết bằng thuật toán
Dijkstras và thuật toán Bellman-Ford đã được sửa đổi. Thuật toán Dijkstras
(xem phụ lục A) được chỉnh sửa bằng cách thay đổi các tiêu chuẩn về lựa chọn
nút tiếp theo được thêm vào là nút M để sao cho nút đó liên kết có băng thông
rộng nhất, còn trong thuật toán chuẩn của Dijstra
’
s nút tiếp theo được lựa chọn

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
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
12
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
đườ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.
Đã có nhiều nỗ lực nhằm đơn giản vấn đề này. Wang và Crowcroft đã đề xuất
ra một số đo hỗn hợp đơn là kết hợp của tất cả các số đo mong muốn. Họ kết
luận rằng nó được sử dụng chỉ như là một chỉ báo, chứ không chứa đựng tất cả
các thông tin cần thiết để quyết định đường đi nào có thể đáp ứng được các yêu
cầu chất lượng dịch vụ QoS. Tuy nhiên trong một số trường hợp, băng thông có
thể được sử dụng như một số đo đơn. Trong khi một kết nối có thể có nhiều yêu
cầu về QoS thì những yêu cầu này chủ yếu chuyển thành các yêu cầu về băng
thông. Guerin et al đề xuất ra một phương trình cho sự sắp xếp các ràng buộc
trễ trong ràng buộc băng thông.
Bảng 2.1 biểu diễn tổng hợp của 2 số đo từ 4 vấn đề đơn mô tả ở trên kết hợp 2
vấn đề tối ưu bị bỏ trống vì không hợp lí. Tất nhiên, vẫn kết hợp được 2 tối ưu,
nhưng phải đưa các vấn đề phức hợp về dạng 2 số đo đơn. Tối ưu thứ 2 chỉ
được sử dụng nếu có nhiều hơn một đường dẫn khả thi liên quan tới tối ưu thứ
nhất. Phương pháp này được sử dụng trong các thuật toán như wsp và swp (xem
phần 2.6)
Bảng 2.1 Sự phức tạp của việc kết hợp các số đo
-Sự cắt giảm:

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 cách cắt bớt mạng, thì vấn đề 6 đưa về dạng 2: vấn đề định tuyến liên kết
ràng buộc.
+ Vấn đề 7 (định tuyến liên kết ràng buộc, đường đi tối ưu)
Cho mạng G(N,A), số đo w
i
(a), i=1,2, trong đó w
1
là concave, với mỗi liên kết a
thuộc A, và một điều kiện ràng buộc C
1
. Tìm đường đi P từ điểm nguồn s đến
điểm đích t sao cho w
2
(P) nhỏ nhất, w
1
(P)≥C
1
.
Vấn đề định tuyến liên kết ràng buộc, đường đi tối ưu có thể được cắt bớt mạng

Cho mạng G(N,A), số đo w
i
(a); i=1,2 trong đó w
i
là tính nhân, với mỗi liên kết
a thuộc A và 1 điều kiện ràng buộc C
2
, tìm đường đi P từ điểm nguồn s đến
điểm đích t sao cho w
1
(P) lớn nhất, w
2
(P)≤C
2
.
Vấn đề này được giải quyết bằng cách sử dụng thuật toán đường đi ngắn nhất
đã được chỉnh sửa. Trên mạng, có m liên kết, các liên kết này có một số giá trị
là số đo liên kết tối ưu. Gọi k là biểu thị cho số lượng các gía trị khác nhau của
số đo. Rõ ràng k≤m vì một số liên kết có thể có những giá trị xác định. Các giá
trị này có thể được dùng như các giới hạn giả thấp hơn C
1
1
, C
1
2
, …, C
1
k
sao cho
các số đo liên kết ràng buộc được tối ưu. Điều này giúp đưa vấn đề 9 về dạng 8

1
k-2
sẽ lại tiếp tục được thêm vào cấu trúc liên kết. Việc
này sẽ tiếp diễn cho đến khi tìm được 1 đường đi khả thi, vấn đề này phức tạp
hơn các vấn đề từ 5 đến 8 nhưng vẫn có thể giải quyết được qua nhiều lần.
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
15
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Hai vấn đề phức tạp hơn còn tồn tại là MCP (vấn đề định tuyến ràng buộc đa
tuyến) và MCOP(vấn đề định tuyến đường đi ràng buộc, đường đi tối ưu hay
còn gọi là vấn đề tối ưu đa ràng buộc). Những số đo trong các vấn đề này không
phải là concave, bởi vậy đây là những vấn đề NP-complete chúng không thể
giải quyết qua nhiều lần, nếu sử dụng tập hợp các số đo này thì cần phải có
những cách giải quyết khác.
+ Vấn đề 10 (Định tuyến ràng buộc đa thức)
Cho mạng G(N,A), số đo additive w
i
, i=1,2, với mỗi đường 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 dẫn P từ điểm nguồn s đến điểm
đích t sao cho w
i
(P)≤ C
i
với tất cả các giá trị i.
Vấn đề định tuyến ràng buộc đa tuyến là NP - Complete. Vấn đề này được biết
đến rất nhiều, nó chỉ ra rằng: vấn đề số đo patition và additive dùng để chứng
minh NP-Complete bằng cách này hay cách khác, có thể đưa các vấn đề đa thức
nêu trên về các vấn đề số đo đơn để dùng các thuật toán đường đi ngắn nhất để

dung pha có thể giải quyết qua nhiều lần bằng thuật toán Bellman-Ford. Nó dựa
vào thực tế là trong một môi trường như vậy , bước nhảy chỉ là một thông số
nếu như ràng buộc dung pha có thể đạt yêu cầu. Bởi vậy có thể giải quyết vấn
đề này bằng cách giải quyết ràng buộc độ trễ, kiểm soát tính toán bước nhảy sao
cho đảm bảo các yêu cầu về độ dung. Nếu tất cả các số đo cho phép nhận các
giá trị nguyên trong giới hạn thì vấn đề cũng có thể được giải quyết qua nhiều
lần.
Ví dụ, bước nhảy vốn là một số đo có giá trị nguyên và được giới hạn bằng
đường kính của đồ thị.
2.5 Các hướng tiếp cận từ nghiệm suy đôi vớ i các vấn đề phức tạp NP-
Complete:
Như đã nói trong phần 2.4.2, sự phức tạp trong tính toán của các vấn đề MCP,
MCOP, vấn đề 10,11 là NP-Complete. Để giải quyết các vấn đề này, thì cần
tính gần đúng từ nghiệm suy nhiều lần. Các vấn đề được đưa về dạng đơn giản
để giải quyết bằng thuật toán đường đi ngắn nhất.
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
17
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Hình 2.1: Vấn đề định tuyến ràng buộc đa tuyến. Vùng khả thi với mỗi i, w
i
(P)≤
C
i
, được biểu thị bằng 1 hình chữ nhật góc dưới bên trái. Các chấm đen biểu thị
các tuyến.
Xem hình 2.1 mỗi đường đi P có một số giá trị cho mỗi số đo w
i
(P). Hình này
mô phỏng tình huống với hai ràng buộc. Các tuyến là các chấm đen trong đồ thị
theo giá trị của các số đo. Các phần tiếp theo xem lại một số phép tính gần đúng

2
’(a) với liên kết a thuộc A, điều kiện ràng
buộc C
1
và x. Tìm đường đi P từ điểm nguồn s đến điểm đích t, sao cho
w
1
(P)≤C và w
2
’(P)≤ x. Chen và Nahrstedt đã mở rộng thuật toán Dijkstra và
Bellman-Ford để giải quyết vấn đề này.
Mệnh đề 1: giải pháp cho vấn đề nghiệm suy gần đúng cũng là giải pháp cho
vấn đề gốc
Chứng minh: từ phương trình 2.2
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
18
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Suy ra
Đường đi P là giải pháp cho vấn đề đơn giản, phương trình
W
2
’(P)≤x (2.3) phải được đảm bảo
Có thể dễ thấy là P cũng là giải pháp cho vấn đề gốc
Do đó w
2
(P) ≤ C
2
Giải pháp cho vấn đề gốc là giải pháp cho vấn đề đơn giản.
Vd: Nếu đường đi P có 3 bước nhẩy với tải trọng liên kết 4,5 và 6, nó là giải
pháp cho vấn đề gốc khi C

2
,
C
2
) nên thử bằng cách khác. Còn nếu có giải pháp, thì cách nghiệm suy chính là
1 giải pháp.
+ Thuật toán Jaffe
Jaffe đề xuất hàm chiều dài đường đi không thuộc đường thẳng
f(P) = max{w
1
(P), C
1
} + max {w
2
(P), C
2
} (2.5)
Trong đó, giá trị nhỏ nhất đảm bảo giải quyết vấn đề MCP bằng cách tìm ra
tuyến khả thi nếu có. Tuy nhiên, nó không được giải quyết bằng thuật toán
đường đi ngắn nhất, vì hàm chiều dài này không thuộc đường thẳng. Bởi vậy
ông dùng 1 thuật toán tương tự sử dụng đường nối của các tải trọng:
W(u,v) = d
1
.w1(u,v) + d
2
.w
2
(u,v) (2.6)
Như vậy vấn đề trở thành: tải trọng hợp là 1 số đo và có thể giải quyết bằng
thuật toán đường đi ngắn nhất. Sau đó giải pháp là kiểm tra với điều kiện ràng

i
.
Hình 2.3 biểu diễn các đường cong của hàm tải trọng kết hợp thậm chí
nếu có 1 giải pháp khả thi, thì thuật toán cũng có thể không tìm ra nó, là trường
hợp bên phải.Nếu giải pháp mà thuật toán tìm ra không khả thi, thì ta có thể
bằng cách thay đổi giá trị của d
i
để tìm ra giải pháp khả thi. Nhưng vì các đường
cong tương đương thuộc đường thẳng, nên có thể xuất hiện tình huống là có giải
pháp khả thi nhưng không phải tìm được bằng bất cứ giá trị nào của d
i
.
Thuật toán
Thuật toán này thay vì sử dụng đường nối tải trọng, thì sử dụng hàm non-lineat
(làm cong các đường thẳng tương đương) để giải quyết vấn đề MCP
Tải trọng đường được nối là:
(2.7)
Khi q -> ∞ phương trình (2.7) sẽ biến đổi thành
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
21
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
(2.8)
Phương trình này đảm bảo tất cả các điều kiện ràng buộc được thoả mãn nếu
w(P)≤1.
Hình 2.3 không có tuyến nhưng đường cong đang tồn tại tương tự.
Giá trị q làm tăng thêm khả năng của thuật toán.
Hình 2.3 biểu diễn tình huống tương tự như hình 2.2. Số đo đã tìm
được chính xác đường khả thi.
Vấn đề trong (2.6) đó là số đo đó không phải là tính cộng, do vậy mà khi tính
toán tải trọng của đường đi. Kết quả là TAMCRA phải sử dụng thuật toán

nguồn đích t.Với những đường đi đó, tính tải trọng đường đi,và lựa chọn đường
đi P sao cho w(P) nhỏ nhất.Kiểm tra giải pháp đường đi P thoả mãn đk ràng
buộc w
i
≤ c
i
với mỗi I hay không.
Thuật toán Iwata.
Iwata đề xuất giải pháp trực tiếp đối với vấn đề MCP,thuật toán tìm ra đường đi
ngắn nhất ,hoặc các tuyến phụ thuộc vào 1 số đo và sau đó kiểm tra ràng buộc
có được đảm bảo không.Nếu không,nó tìm ra tuyến ngắn nhất với số đo khác và
kiểm tra lại các điều kiện ràng buộc.Vấn đề là các tuyến khả thi không cần phải
là ngắn nhất đối với bất kì số đo nào.Trong hình 2.4, tuyến khả thi là đường thứ
2 liên quan đến tải trọng 1.
+ Hướng nghiệm suy 4 (thuật toán IWATA)
Cho mạng G(N,A), số đo
Sinh Viên Vũ Công Sự Mã Sinh Viên A06255
23
Thuật toán đường đi ngắn nhất và rộng nhất SWP GVHD: Hoàng Trọng Minh
Hình (2.4) Quy trình tìm kiếm của thuật toán Iwata
w
i
(a), i=1,2 với mỗi liên kết a Є A, điều kiện ràng buộc C
i
, i=1,2. Tìm đường đi
P sao cho w
i
(P) nhỏ nhất với mỗi giá trị cụ thể i, hoặc một số đường đi nhẹ nhất
với w
i

buộc C
i
và tải trọng d
i
, i=1,2. Bước khởi đầu tính đường đi ngắn nhất từ điểm
nguồn u đến điểm đích t, ứng với mỗi số đo w
i
, và số đo tổng hợp tuyến tính
(2.5). Sử dụng kiểm tra ngẫu nhiên breadth-first tìm đường dẫn P từ điểm nguồn
s đến điểm đích t sao cho w
i
(P) ≤ C
i
với tất cả i. Để giảm việc tìm kiếm trong
không gian, Khi tìm được 1 điểm thì dùng thông tin khởi đầu kiểm tra xem có
thể tìm được đường đi khả thi thông qua điểm đó hay không. Nếu không có thì
loại bỏ nó.
H-MCOP
Thuật toán này được đề xuất bởi Korkmaz và Krunz để giải quyết vấn đề
MCOP. Nó trở về đường đi khả thi, cũng là làm nhỏ nhất hàm chi phí đã được
lựa chọn, dựa vào chi phí 1 đường liên kết C(u,v) ứng với mỗi đường liên kết là
một ràng buộc QoS w
i
(u,v) hoặc 1 số hàm chi phí tương tự. Trong bước đầu
tiên, thuật toán tính tuyến khả dụng từ một điểm u đến điểm đích t ứng với số
đo tổng hợp tuyến tính (2.5) thiết lập bước này trở lại tuyến khả thi với số đo
tổng hợp tuyến tính.
Sau đó, thuật toán sử dụng hàm chiều dài tuyến không thẳng của phương trình
(2.6) để tính toán các đường đi từ điểm nguồn đến điểm s. Nó phát hiện ra mỗi
điểm u dựa vào giá trị nhỏ nhất của hàm chiều dài tuyến không thẳng hàng. Với