Bài giảng Mạng máy tính - Chương 11: Linkstate Routing Protocols - Âu Bửu Long

ThS Âu Bửu Long 1Mạng máy tính nâng cao-V1 Link State Routing
Dựa trên thuật toán Dijkstra để tìm đường đi ngắn nhất.
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 nối giữa các router liền kề Link State Routing
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. ◦ 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
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. ◦ Mất kết nối giữa các node (link failure). ◦ Node nào đó bị fail (node failure) Link State Packets
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
Đầu tiên, PATH chỉ chứa node gốc (Router hiện tại)
Ứng với mỗi node N trong PATH: ◦ Với mỗi node kề M của node N:  Nếu M không nằm trong TENT, Thêm M vào TENT  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  Nếu M nằm trong TENT và chi phí mới cao hơn chi phí đã tính thì bỏ qua.  Tính đường đi ngắn nhất trong TENT  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
Xét topo mạng sau: A B C G2 6 2 4 2 1 2 5 D E F 1 Link state database: A B 6 D 2 B A 6 C 2 E 1 C B 6 F 2 G 5 D A 2 E 2 E B 1 D 2 F 4 F C 2 E 4 G 1 G C 5 F 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
Ứng với LSP của C ◦ Thêm F, G, và B vào TENT C (0) (2) (5) (2) Thuật toán Dijkstra’s LSR F G B
Thêm F vào PATH ◦ Thêm G và E vào TENT C (0) (2) (5) (2) Thuật toán Dijkstra’s LSR F G B G E (3) (6)
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) (5) (2) Thuật toán Dijkstra’s LSR F G B G E (3) (6)
Thêm B vào PATH ◦ Thêm A và E vào TENT C (0) (2) (2) Thuật toán Dijkstra’s LSR F B G E (3) (6) A E (3) (8)
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) Thuật toán Dijkstra’s LSR F B G E (3) (6) A E (3) (8)
Thêm E vào PATH ◦ Thêm D vào TENT C (0) (2) (2) Thuật toán Dijkstra’s LSR F B G (3) A E (3) (8) D (5)
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) Thuật toán Dijkstra’s LSR F B G (3) A E (3) (8) D (5)
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) Thuật toán Dijkstra’s LSR F B G (3) A E (3) (8) D (5) A (7)
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) Thuật toán Dijkstra’s LSR F B G (3) E (3) D (5) A (7)
Kết thúc vì tất cả các đường trong TENT đã thêm vào PATH C (0) (2) (2) Thuật toán Dijkstra’s LSR F B G (3) E (3) D (5) A (7)
Tạo ra database forward: C (0) (2) (2) Forwarding Database Destination Port C C Thuật toán Dijkstra’s LSR F B G (3) E (3) D (5) A (7) F F G F B B E B D B A B