Chương 4:
PHÂN TÍCH CÁC GIẢT THUẬT TÌM ĐƯỜNG
Giải thuật giá trị bé nhất:
Thực tế các mạch chuyển mạch gói(PSN) sự quyết định đường của nó dựa trên một sô" dạng phân loại giá trị tôi thiểu. Nếu sự phân loại theo giá trị các
hops là ít nhất, mỗi đường có giá trị 1. Điển hình hơn, giá trị mỗi đường tương xứng dung lượng mỗi đường, tương xứng tức thời (current load) trên đường
đi, hoặc một sô" tổ hợp. Trong một sô" trường hợp, sự đánh giá các giá trị đó không bao gồm giải thuật giá trị bé nhât.Với điều đó có thể nói đơn giản:
Cho một mạng các Node nôi với nhau bằng những đường hai chiều, mỗi đường đó có giá trị tổng hợp chung cho mỗi hướng. Ta định nghĩa giá trị
của một đường (path) giữa hai Node là tổng giá trị của những đường nó đi qua. Cho mỗi cặp Node tìm thây một con đường giá trị bé nhất. Hầu hết các giải
thuật giá trị bé nhất được sử dụng trong PSN đều dựa trên hai giải thuật Dijkstra và Bellman Ford.
1. Giải thuật Dijkstra:
Giải thuật Dijkstra có thể phát biểu như sau: Để tìm con đường ngắn nhâ"t từ Node nguồn cho trước đến tất cả các Node khác bằng cách phát triển thêm
vào độ dài của đường. Quá trình thực hiện giải thuật như sau: Với mức k con đường ngắn nhất đến k Node, đến Node nguồn đã cho, qua m Node, ở
mức(k+l).
Giải thuật được định nghĩa như sau:
N = sô" lượng Node trong mạng, s = Node nguồn.
M = sô" lượng Node hợp nhất cho giải thuật (kết hợp cho giải thuật).
Dij = Giá trị đường từ Node i tới Node j.
->dij = 0
dij = co nếu Node không nôi trực tiếp.
Dn = Giá trị nhỏ nhất từ Node s đến Node n lúc xác lập giải thuật.
Giải thuật có 3 bưđc và lập lại cho đến khi M = N.
1. Gán D(s) = 0; giả sử T là tập hợp các đỉnh.
2. Nếu s không thuộc T, ngưng. (D(s) là chiều dài đường đi ngắn nhất từ s đến z).
3. Chọn V thuộc T sao cho D(v) có giá trị nhỏ nhất.
T = T-{v}
4. Với mỗi X thuộc T kề với V, gán:
D(x) = min{D(x), D(v) +w(v,x)}.
Đến bước 2.
Trong chương trình ta dùng:
Đôi tượng Cpoint pBegin để khởi tạo điểm nguồn của đường đi.
Đôi tượng Cpoint pEnd để khởi tạo điểm đích của đường đi.

Ta dùng giải thuật Dijkstra để tìm đường ngắn nhất nôi A với các đỉnh khác.
© o
A B
c D E F G H
D D D
L 0 2oo 4 00 1 6 00
V AA F A A F A
© o
Ớ bước thứ nhất, ta lập được bảng như sau:
A B C D E F G H
D D
L 0 2 o o 0 3 0 0 Q O 0 0 Q O
V A A A A A A A
(0) o o
0
o
o
Chọn được đỉnh F đặt vào D và ta có bảng sau:
Cứ tiếp tục như trên ta lần lược có các bảng như sau:
A B C D E F G H
D
D D D
L
0 2 4 4 4
1 6 O 0
V
A B F B A
F A
o
A B C D E F G H

V
A B F B A
F c
Giải thuật kết thúc và bảng lập được sau cùng cho ta con đường ngắn nhất nôi từ đỉnh A đến các đĩnh khác.
Ví dụ đường đi ngắn nhất nối từ đỉnh A đến H là ABCH và chiều dài đường ngắn nhất này là 5.
2. Giải thuật BELLMANFORD:
Giải thuật Bellman Ford có thể phát biểu: Tìm con đường đi ngắn nhất từ Node (nguồn) đã cho X đến Node bắt buộc, con đường gồm một đoạn đường, rồi
tìm đoạn đường ngắn nhất giữa hai đoạn đường nôi và tiếp tục cho đến hết. Giải thuật được thực hiện như sau:
• S:Node nguồn.
• dij: Giá trị đường từ i đến j.
• dij = 0.
• Dij = 00 cho Node không nôi trực tiếp.
• D(h): Giá trị của con đường ngắn nhất từ Node s đến Node n, dưới sự bắt buộc không quá h đường nối.
A B C D E F G H
D D D D D D
L
0 2 4 4 4 1
6 5
V
A B F B A
F c
• h: sô" cực đại đường nôi trong đường nối trong đường nối tại thời điểm tức thời đổi về giá trị.
Giải thuật có các bước sau, và chúng lập lại cho đến khi không có sự thay đổi về giá trị.
Bước 1: Bắt đầu:
D„
(0)
= 00 cho tất cả n ^ s.
Bước 2: Thực hiện kế tiếp với h > 0.
D
n

cho giải thuật phân tán. Mỗi Node cần toàn bộ topologie về mạng, có nghĩa là nó cần biết giá trị đường nôi của tất cả các đường trong mạng. Như vậy
với giải thuật này, thông tin cần trao đổi với tất cả các nốt, phức tạp hơn cho việc Routing phân tán.
3. Giải Thuật SHORTEST PATH ROUTING:
Trong giải thuật này chúng ta có một trọng đồ kết nôi vô hướng có trọng sô" của các Node. Với mỗi kết nôi trực tiếp giữa hai Node có một giá trị
được coi là chi phí hay là khoảng cách cần thiết để đi từ Node này đê" Node kia.
Giải thuật có các bước sau:
a) cho Node nguồn là Node cô" định và cho nó làm việc, hay là Node hiện hành.
Bellman- Ford (đỉnh nguồn =1)
h D
2
(h>
Path D
3
(h)
Path D
4
(h)
Path D
5
(h)
Path D
ỏ
(h)
Path
0
oo oo
00 00 00
1
2 1-2 5 1-3 1 1-4
00 00

d[iỊ[jì = 1 nếu có đường nôi trực tiếp từ i đến j. d[i][j] = 00 nếu
không có đường nôi trực tiếp từ i đến j.
Tổng quát các bước lặp để tính đường đi ngắn nhất như sau:
for(k = 0; k< n; k++)
for(i = 0; i< n ; i++)
for(j = 0; j< n ; j++)
if(d[i][k]+d[k][j]<d[i][j])
í
d[i][j]=d[i][k] + d[k][j]; p[i]
[j] = k;
}
Tại bước lập thứ k, giá trị d[i][k] + d[k][j] được gán cho d[i][j] được thỏa mản một
trong hai trường hợp sau đây:
1. Tồn tại đường đi từ i đến k và đường đi từ k đến j nhưng không tồn tại đường đi từ i
đến j qua các đỉnh trung gian thuộc tập hợp Vk-i(D[i,j] = 0).
2. Tồn tại đường đi từ đỉnh i đến đỉnh k, đường đi từ k đến j và đường đi từ i đến j qua
các đỉnh trung gian tập hợp VK-1 nhưng d[i][j] > d[i][k] + d[k][j] ( nguyên lý tôi ưu).
• Sơ đồ biểu diễn:
k
0
j
• Sơ đồ khôi của giải thuật Floyd như sau:
ỉ
i = 1
j = l
k= l
Ví dụ: Xét đồ thị
1
7
4

4
thực hiện tổng cộng của giải thuật Dijkstra tỉ lệ với n * ((E +n) * log(n)) = (E * n + n
2
) &* log(n). Nếu đồ thị đầy(E« n
2
) ta nên sử dụng giải thuật Dijkstra,
nếu đồ thị không đầy (E xấp xỉ với n
2
) thì ta nên sử dụng giải thuật Floyd.
Tuy nhiên với giải thuật Floyd ta thấy việc tìm đường đi ngắn nhất nó thực hiện một cách nhanh. Và nó cho ta con đường ngắn nhất giữa mọi cặp đỉnh
trong đồ thị.
Giải thuáỊ Floyd có thể áp dụng cho đồ thị vô hướng cũng như đồ thị có hướng: ta chỉ cần thay đổi cạnh vô hướng bằng một cạnh vô hương. Tuy nhiên
trong trường hợp này các phần tử trên đường chéo của ma trận cần đặt bằng không.
5. Giải thuật FLOODING routing( tìm đường động):
Giải thuật này chỉ ra đường đi ngắn nhất từ đỉnh X đến đỉnh y. Kết hợp cả ba phương pháp Deapth First Search, Breadth First Search và xét giá trị đường
đi là tối thiểu.
Một kỹ thuật tìm đường đơn giản khác là Flooding. Giải thuật này không yêu cầu bất cứ thông tin nào của mạng và nó làm việc như sau: Gói gửi từ Node
nguồn đến mọi Node lân cận. Ớ tại mỗi Node, gói vừa mới đến lại chuyển đi trên mọi đường ra ngoài ngoại trừ đường nó mới đến. Và cứ tiếp tục như vậy
cho các Node kế tiếp cho đến khi nào Node đích nhận được thông tin của Node nguồn.
Rõ ràng rằng như vậy không có gì mất để dừng sự truyền liên tục cá gói. Sô" thứ tự các gói trong khi chạy chỉ do một nguồn cung cấp không bị hạn chế.
Để đề phòng điều đó, ở mỗi Node nhớ lại nhận lại gói chuẩn bị truyền. Khi copy thứ hai đến nó sẽ bị loại bỏ. Một kỹ thuật đơn giản là thêm bộ đếm bước
cho mỗi gói.
Bộ đếm có thể ban đầu đặt ở giá trị cực đại nào đó, như là tham sô" của mạng. Mỗi điểm gói qua Node nó được giảm đi 1. Khi bộ đêm đạt đến giá trị 0, gói
sẽ bị loại bỏ.
Minh họa giải thuật flooding ( với n = 3):
cần có một sô" nhận dạng thông nhất (những Node nguồn, sô" thứ tự hoặc sô" vc ). Như vậy Node 6 biết loại bỏ tất cả mà chỉ lây copy đầu tiên.
Tóm lại, gói sẽ được truyền từ Node 1 đến Node 6. Bước thứ nhất 3 bản sao của gói được tạo ra. Bưđc thứ hai của cả 3 gói, tổng cộng là 9 gói được tạo ra.
Một trong những gói được tạo ra đến Node 6. Nó được giữ lại và không truyền tiếp nữa. Tuy nhiên các gói còn lại phát ra 22 bản sao mới cho bước 3 và
cũng là bước cuô"i. Sau bước thứ 3 tất cả các gói bị bỏ, bản 6 nhận được tổng cộng 4 bản sao của gói. Với Flooding ta có thể tìm được đường đi ngắn nhất
giữa các điểm bâ"t kỳ trong mạng, giữa các đôi tượng chuyển động trong mạng, và đạt được mức tôi ưu. Flooding có hai điều cần chú ý:

ưu. Tuy nhiên thứ tự duyệt các đỉnh bị ảnh hưởng bởi việc thay đổi cấu trúc dữ liệu. Các đỉnh của đồ thị trong giải thuật Breadth First Search (tìm kiếm
ưu tiên bề rộng) Được chia thành 3 nhóm:
Các đỉnh đã duyệt là các đỉnh được lấy ra khỏi hàng.
Những đỉnh đang xét là những đỉng trong hàng.
Các đình chưa được xét đến là những đĩnh chưa được duyệt và không có trong hàng.
Sự bất của phương pháp tìm kiếm theo chiều rộng khi đích cần tìm phân bô" rải rác trên tất cả các mức, trong trường hợp này nó phải huy động hết khả
năng tìm tới đích.
8.Giải thuật DISTANCE VECTOR ROUTING:
Mỗi router gửi một bản tìm đường của mạng được nhìn một cách bao quát và qua đó các protocol xác định được thông tin tìm đường, cộng một bước
nhảy
(hop) vào đường đi (để giải thích sự hiện diện của mình đúng), và thông qua việc truy cập thông tin đến router kế tiếp trên đường. Bản chất của
Ditance vector routing protocol là sử dụng tầng thông tin từ các người kế cận chúng. Ditance vector routing protocols chọn lựa đường đi tốt nhất dựa
trên một phép đo met (metric). sử dụng metric là dựa trên sự khác nhau của các protocols hiện tại.
Mặt hạn chế của Ditance vector routing protocol là khi các router gửi những thông tin mới nhất, chúng sẽ gửi toàn bộ bản tìm đường. Đổ gửi thông tin
cập nhật, cập nhật thông tin mới nhất được truyền đi thường xuyên và ấn định thời gian.
Mỗi IMP có một bản tìm đường là danh sách các phần tử. Mỗi phần tử đại diện cho các router khác trong hệ thống và chứa hai phần:
• Khoảng cách cần thuyết lớn nhất để đi IMP đó.
• Đường ra tương ứng khoảng cách đó.
sau thời gian T mỗi IMP sẽ gửi bản tìm đường củab nó cho các IMP kế cận và nhận về bản tương tự. Dựa trên đó tìm ra được bảng tìm đường mới.
Ví dụ : Cho hệ thông supnet
Ngõ vào từ A, I, H, K và bảng tìm đường mơi cho J.
Trong giải thuật này nảy sinh ra hai vấn đề: Count- to-infinity.
Split horizon
• Lưu đồ của giải thuật DISTANCE VECTOR ROUTING :
t = 0
Xác định NETWORK và các router muôn hướng tc i
TO A I H K
New
estimated delay
from J

JH
(delay IS 12)
JK
(delay IS 6)
New routing table for J
Lập bảng tìm đường bao gồm:
• Khoảng cách cần thiết ngắn nhất để đến các
Node
• Đường ra tương ứng khoảng cách đó.
8. Giải thuật LINK-STATE ROUTING:
Trái với Distance-vector routing protocol là Link state routing protocols, một router tính toán một cây”tree” của các ngõ vào network mà nó chính là gốc.
những routers chỉ bao gồm đường dẫntôt nhất nhận được cho metric đến những Nodes(router) khác. Khi một router nhận thấy thay đổi trong
trạng thái liên kết trực tiếp của nó( như một liên kết được thiết lập hay mất đi), router sắp sép sự thay đổi đến tất cả các routers khác thông qua
một sử lý(process) gọi là flooding. Flooding truy cập cơ sở dữ liệu của mỗi router bổi vì nó chỉ gửi trạng thái thay đổi thông tin(vì lý do có tên
trạng thái liên kết).
Tổng quát những gói flooding thì rất nhỏ và hiếm khi được gửi. Chúng góp phần rất ít đến toàn bộ mạng giao thông truyền thông tin, trừ khi
trường hợp thay đổi đường đi một cách thường xuyên.
Giải thuật này đưa ra giải quyết hai vấn đề: Count-to-infinity và băng thông(được xét đến như thành phần của chi phí để cguyển packet).
Có 5 bước thực hiện thuật toán:
• phát hiện các Node láng giềng và lưu lại địa chỉ mạng của chúng.
• Tính toán chi phí đến mỗi Node láng giềng các router gửi các echopacket đến các Node lân cận.(để đưa lưu lượng đường truyền vào trong
chi phí . Ta cần tính thời gian delay của đường truyền từ lúcechopacket đưa vào hàng đợi thay vì tính từ khi gửi đi).
• Tạo ra các packet chứa tất cả các thông tin vừa có được gồm có:
Tên Node.
Sô" sequence.
Tham sô" Age.
Danh sách các router lân cận và chi phí của chúng.
• gửi các packet đến tất cả các router khác, thời điểm gửi: Định kì theo thời gian T.
Gửi theo yêu cầu.
Gửi khi lân cận thay đổi.