Rate this post

Định tuyến Link state là một kỹ thuật trong đó mỗi bộ định tuyến chia sẻ kiến thức về vùng lân cận của nó với mọi bộ định tuyến khác trong mạng internet.

Các bài viết liên quan:

Ba chìa khóa để hiểu thuật toán Định tuyến Link state:

Kiến thức về vùng lân cận: Thay vì gửi bảng định tuyến của nó, một bộ định tuyến chỉ gửi thông tin về vùng lân cận của nó. Một bộ định tuyến phát thông tin nhận dạng và chi phí của các liên kết được gắn trực tiếp đến các bộ định tuyến khác.
Ngập lụt: Mỗi bộ định tuyến gửi thông tin đến mọi bộ định tuyến khác trên mạng internet ngoại trừ các bộ định tuyến hàng xóm của nó. Quá trình này được gọi là Lũ lụt. Mỗi bộ định tuyến nhận được gói tin sẽ gửi các bản sao đến tất cả các bộ định tuyến lân cận của nó. Cuối cùng, mỗi bộ định tuyến đều nhận được một bản sao của cùng một thông tin.
Chia sẻ thông tin: Một bộ định tuyến chỉ gửi thông tin đến mọi bộ định tuyến khác khi có sự thay đổi trong thông tin.

Tóm tắt nội dung

Định tuyến Link state có hai giai đoạn:

Reliable Flooding

Trạng thái ban đầu: Mỗi nút biết chi phí của các nút lân cận của nó.
Trạng thái cuối cùng: Mỗi nút biết toàn bộ đồ thị.

Tính toán đường đi

Mỗi nút sử dụng thuật toán Dijkstra trên đồ thị để tính toán các tuyến đường tối ưu đến tất cả các nút.

Thuật toán định tuyến Link state còn được gọi là thuật toán Dijkstra, được sử dụng để tìm đường đi ngắn nhất từ một nút đến mọi nút khác trong mạng.
Thuật toán Dijkstra là một phép lặp và nó có đặc tính là sau lần lặp ^thứ k của thuật toán, các đường dẫn có chi phí thấp nhất được biết đến nhiều cho k nút đích.

Hãy mô tả một số ký hiệu:

c (i, j): Chi phí liên kết từ nút i đến nút j. Nếu các nút i và j không liên kết trực tiếp thì c (i, j) = ∞.
D (v): Nó xác định chi phí của đường dẫn từ mã nguồn đến đích v có chi phí thấp nhất hiện tại.
P (v): Nó xác định nút trước đó (hàng xóm của v) cùng với đường dẫn chi phí thấp nhất hiện tại từ nguồn đến v.
N: Là tổng số nút có sẵn trong mạng.

Thuật toán

Khởi tạo 
N = {A} // A là một nút gốc .
cho tất cả các nút v
nếu v liền kề với A
thì D (v) = c (A, v)
else D (v) = infinity
vòng lặp
tìm w không thuộc N sao cho D (w) là cực tiểu.
Thêm w vào N
Cập nhật D (v) cho tất cả v liền kề với w và không thuộc N:
D (v) = min (D (v), D (w) + c (w, v))
Cho đến khi tất cả các nút trong N

Trong thuật toán trên, một bước khởi tạo được theo sau bởi vòng lặp. Số lần vòng lặp được thực hiện bằng tổng số nút có sẵn trong mạng.

Hãy hiểu qua một ví dụ:

Trong hình trên, đỉnh nguồn là A.

Bước 1:

Bước đầu tiên là bước khởi tạo. Con đường có chi phí thấp nhất được biết đến hiện tại từ A đến các láng giềng trực tiếp của nó, B, C, D lần lượt là 2,5,1. Chi phí từ A đến B được đặt thành 2, từ A đến D được đặt thành 1 và từ A đến C được đặt thành 5. Chi phí từ A đến E và F được đặt thành vô cùng vì chúng không liên kết trực tiếp với A.

Bươc	n	D (B), P (B)	D (C), P (C)	D (D), P (D)	D (E), P (E)	D (F), P (F)
1	A	2, A	5, A	1, A	∞	∞

Bước 2:

Trong bảng trên, chúng ta quan sát thấy đỉnh D chứa đường đi ít chi phí nhất trong bước 1. Do đó, nó được thêm vào N. Bây giờ, chúng ta cần xác định một đường đi có chi phí thấp nhất qua đỉnh D.

a) Tính đường đi ngắn nhất từ A đến B

v = B, w = D
D (B) = min (D (B), D (D) + c (D, B))
=min( 2 , 1 + 2 )>
=min( 2 , 3 )
Giá trị nhỏ nhất là 2 . Do đó, đường đi ngắn nhất hiện nay từ A đến B là 2 .

b) Tính đường đi ngắn nhất từ A đến C

v = C, w = D
D (B) = min (D (C), D (D) + c (D, C))
=min( 5 , 1 + 3 )
=min( 5 , 4 )
Giá trị nhỏ nhất là 4 . Do đó, con đường ngắn nhất hiện tại từ A đến C là 4. </p>

c) Tính đường đi ngắn nhất từ A đến E

v = E, w = D
D (B) = min (D (E), D (D) + c (D, E))
=min(∞, 1 + 1 )
=min(∞, 2 )
Giá trị nhỏ nhất là 2 . Do đó, đường đi ngắn nhất hiện tại từ A đến E là 2 .

Lưu ý: Đỉnh D không có liên kết trực tiếp với đỉnh E. Do đó, giá trị của D (F) là vô cùng.

Bươc	n	D (B), P (B)	D (C), P (C)	D (D), P (D)	D (E), P (E)	D (F), P (F)
1	A	2, A	5, A	1, A	∞	∞
2	AD	2, A	4, D		2, D	∞

Bước 3:

Trong bảng trên, chúng ta quan sát thấy rằng cả E và B đều có đường dẫn chi phí nhỏ nhất trong bước 2. Hãy xem xét đỉnh E. Bây giờ, chúng ta xác định đường đi có chi phí thấp nhất của các đỉnh còn lại qua E.

a) Tính đường đi ngắn nhất từ A đến B.

v = B, w = E
D (B) = min (D (B), D (E) + c (E, B))
=min( 2 , 2 + ∞)
=min( 2 , ∞)
Giá trị nhỏ nhất là 2 . Do đó, đường đi ngắn nhất hiện nay từ A đến B là 2 .

b) Tính đường đi ngắn nhất từ A đến C.

v = C, w = E
D (B) = min (D (C), D (E) + c (E, C))
=min( 4 , 2 + 1 )
=min( 4 , 3 )
Giá trị nhỏ nhất là 3 . Do đó, đường đi ngắn nhất hiện nay từ A đến C là 3 .

c) Tính đường đi ngắn nhất từ A đến F.

v = F, w = E
D (B) = min (D (F), D (E) + c (E, F))
=min(∞, 2 + 2 )
=min(∞, 4 )
Giá trị nhỏ nhất là 4 . Do đó, đường đi ngắn nhất hiện nay từ A đến F là 4 .

Bươc	n	D (B), P (B)	D (C), P (C)	D (D), P (D)	D (E), P (E)	D (F), P (F)
1	A	2, A	5, A	1, A	∞	∞
2	AD	2, A	4, D		2, D	∞
3	ADE	2, A	3, E			4, E

Bước 4:

Trong bảng trên, chúng ta quan sát thấy đỉnh B có đường đi nhỏ nhất ở bước 3. Do đó, nó được thêm vào N. Bây giờ, chúng ta xác định đường đi có chi phí nhỏ nhất của các đỉnh còn lại qua B.

a) Tính đường đi ngắn nhất từ A đến C.

v = C, w = B
D (B) = min (D (C), D (B) + c (B, C))
=min( 3 , 2 + 3 )
=min( 3 , 5 )
Giá trị nhỏ nhất là 3 . Do đó, đường đi ngắn nhất hiện nay từ A đến C là 3 .

b) Tính đường đi ngắn nhất từ A đến F.

v = F, w = B
D (B) = min (D (F), D (B) + c (B, F))
=min( 4 , ∞)
=min( 4 , ∞)
Giá trị nhỏ nhất là 4 . Do đó, đường đi ngắn nhất hiện nay từ A đến F là 4 .

Bươc	n	D (B), P (B)	D (C), P (C)	D (D), P (D)	D (E), P (E)	D (F), P (F)
1	A	2, A	5, A	1, A	∞	∞
2	AD	2, A	4, D		2, D	∞
3	ADE	2, A	3, E			4, E
4	ADEB		3, E			4, E

Bước 5:

Trong bảng trên, chúng ta quan sát thấy đỉnh C có đường đi nhỏ nhất ở bước 4. Do đó, nó được thêm vào N. Bây giờ, chúng ta xác định đường đi có chi phí nhỏ nhất của các đỉnh còn lại qua C.

a) Tính đường đi ngắn nhất từ A đến F.

v = F, w = C
D (B) = min (D (F), D (C) + c (C, F))
=min( 4 , 3 + 5 )
=min( 4 , 8 )
Giá trị nhỏ nhất là 4 . Do đó, đường đi ngắn nhất hiện nay từ A đến F là 4 .

Bươc	n	D (B), P (B)	D (C), P (C)	D (D), P (D)	D (E), P (E)	D (F), P (F)
1	A	2, A	5, A	1, A	∞	∞
2	AD	2, A	4, D		2, D	∞
3	ADE	2, A	3, E			4, E
4	ADEB		3, E			4, E
5	ADEBC					4, E

Bảng cuối cùng:

Bươc	n	D (B), P (B)	D (C), P (C)	D (D), P (D)	D (E), P (E)	D (F), P (F)
1	A	2, A	5, A	1, A	∞	∞
2	AD	2, A	4, D		2, D	∞
3	ADE	2, A	3, E			4, E
4	ADEB		3, E			4, E
5	ADEBC					4, E
6	ADEBCF

Nhược điểm:

Lưu lượng truy cập đông đúc được tạo trong định tuyến ở trạng thái Đường do ngập lụt. Ngập lụt có thể gây ra vòng lặp vô hạn, vấn đề này có thể được giải quyết bằng cách sử dụng trường Thời gian rời khỏi

Computer network, Network và security

Định tuyến Link state vector