ThS Âu Bửu Long
1
Mạng máy tính nâng cao-V1
Link State Routing Link State Routing
(cid:1) Dựa trên thuật
toán Dijkstra để tìm
đường đi ngắn nhất.
(cid:1) Mỗi router lưu trữ thông tin về toàn bộ
topo của mạng ◦ Gồm danh sách các router và đường kết ◦ Gồm danh sách các router và đường kết
nối giữa các router liền kề
Link State Routing Link State Routing
(cid:1) Mỗi router tạo ra gói “link state packet” (LSP) chứa địa chỉ mạng và khoảng cách đến các router kề với nó. ◦ LSP sẽ được gởi đế đến tất cả các router để
cập nhật các mẫu tin định tuyến của chúng. cập nhật các mẫu tin định tuyến của chúng.
◦ Khi router nhận LSP từ tất cả các router, nó sẽ dùng các thông tin này để quyết định đường đi.
Link State Packets Link State Packets
(cid:1) LSPs được tạo ra và gởi khi:
◦ Định kỳ. ◦ Có node mới kết nối vào router. ◦ Chi phí kết nối thay đổi. ◦ Chi phí kết nối thay đổi. ◦ Mất kết nối giữa các node (link failure). ◦ Node nào đó bị fail (node failure)
Link State Packets Link State Packets
(cid:1) LSP chứa các thông tin:
◦ Thông tin về node/mạng lân cận ◦ Thông tin về chi phí kết nối
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR
(cid:1) Đầu tiên, PATH chỉ chứa node gốc (Router
hiện tại)
(cid:1) Ứng với mỗi node N trong PATH: ◦ Với mỗi node kề M của node N:
(cid:2) Nếu M không nằm trong TENT, Thêm M vào TENT (cid:2) Nếu M không nằm trong TENT, Thêm M vào TENT (cid:2) Nếu M nằm trong TENT, và chi phí đường đi mới thấp
hơn chi phí node M trong TENT, thay thế M bởi thông tin ứng với đường qua N
(cid:2) Nếu M nằm trong TENT và chi phí mới cao hơn chi phí
đã tính thì bỏ qua.
(cid:2) Tính đường đi ngắn nhất trong TENT
(cid:2) Nếu đường đi ngắn hơn đường đã lưu trong PATH thì cập
nhật lại PATH
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Xét topo mạng sau:
6 2
A B C 5
2 1 2 G
2 2 4 4 1 D E F
Link state database:
A B 6
B A 6
C B 6
D A 2
E B 1
F C 2
G C 5
D 2
C 2
F
2
E 2
D 2
E 4
F
1
E 1
G 5
F
4
G 1
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Khởi tạo đường đi cho node C: ◦ Đầu tiên, thêm (C,0,0) vào PATH
C (0)
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Ứng với LSP của C
◦ Thêm F, G, và B vào TENT
C (0)
(2) (2) (2) (2) (5) (5) F B G
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Thêm F vào PATH
◦ Thêm G và E vào TENT
C (0)
(2) (2) (2) (2) (5) (5) F B G
(3) (6) G E
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) G xuất hiện trong TENT 2 lần, lưu đường
tốt nhất ◦ Hướng mới đến G tốt hơn (3 < 5)
C (0)
(2) (2) (2) (2) (5) (5) F B G
(3) (6) G E
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Thêm B vào PATH
◦ Thêm A và E vào TENT
C (0)
(2) (2) (2) (2) F B
(3) (6) (3) (8) G A E E
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) E xuất hiện 2 lần, chọn hướng tốt nhất.
◦ Đường đến E mới tốt hơn (3 < 6)
C (0)
(2) (2) (2) (2) F B
(3) (6) (3) (8) G A E E
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Thêm E vào PATH ◦ Thêm D vào TENT
C (0)
(2) (2) (2) (2) F B
(3) (8) (3) G A E
(5)
D
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Thêm G vào PATH
◦ Tất cả các thành phần trong LSP của G đã tồn
tại trong TENT
C (0)
(2) (2) (2) (2) F B
(3) (8) (3) G A E
(5)
D
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Thêm D vào PATH
◦ Thêm đường mới đến A vì tốt hơn đường có sẵn
C (0)
(2) (2) (2) (2) F B
(3) (3) (8) G A E
(5)
D
(7) A
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Thêm A vào PATH
◦ Tất cả các thành phần trong LSP của G đã tồn
tại trong TENT
C (0)
(2) (2) (2) (2) F B
(3) (3) G E
(5)
D
(7) A
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Kết thúc vì tất cả các đường trong TENT
đã thêm vào PATH
C (0)
(2) (2) (2) (2) F B
(3) (3) G E
(5)
D
(7) A
Thuật toán Dijkstra’s LSR Thuật toán Dijkstra’s LSR (cid:1) Tạo ra database forward:
Forwarding Database
C (0)
Destination Port
C C
C C
F
F
(2) (2) (2) (2) F B
G
F
B
B
(3) (3) G E
E
B
(5)
D
B
D
A
B
(7) A
