Bài giảng Linkstate Routing Protocols - Âu Bửu Long

Nội dung text: Bài giảng Linkstate Routing Protocols - Âu Bửu Long

1. ThS Âu Bửu Long Mạng máy tính nâng cao-V1 1
2. 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ề
3. 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.
4. 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)
5. 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
6. 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
7. Thuật toán Dijkstra’s LSR
   Xét topo mạng sau: 6 2 A B C 5 1 2 2 G 2 4 D E F 1 Link state database: A B C D E F G B 6 A 6 B 6 A 2 B 1 C 2 C 5 D 2 C 2 F 2 E 2 D 2 E 4 F 1 E 1 G 5 F 4 G 1
8. Thuật toán Dijkstra’s LSR
   Kh ởi t ạo đường đi cho node C: ◦ Đầ u tiên, thêm (C,0,0) vào PATH C (0)
9. 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) F G B
10. Thuật toán Dijkstra’s LSR
    Thêm F vào PATH ◦ Thêm G và E vào TENT C (0) (2) (5) (2) F G B (3) (6) G E
11. Thuật toán Dijkstra’s LSR
    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) F G B (3) (6) G E
12. Thuật toán Dijkstra’s LSR
    Thêm B vào PATH ◦ Thêm A và E vào TENT C (0) (2) (2) F B (3) (6) (3) (8) G A E E
13. Thuật toán Dijkstra’s LSR
    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) F B (3) (6) (3) (8) G A E E
14. Thuật toán Dijkstra’s LSR
    Thêm E vào PATH ◦ Thêm D vào TENT C (0) (2) (2) F B (3) (3) (8) G A E (5) D
15. Thuật toán Dijkstra’s LSR
    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) F B (3) (3) (8) G A E (5) D
16. Thuật toán Dijkstra’s LSR
    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) F B (3) (3) (8) G A E (5) D (7) A
17. Thuật toán Dijkstra’s LSR
    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) F B (3) (3) G E (5) D (7) A
18. Thuật toán Dijkstra’s LSR
    Kết thúc vì t ất c ả các đường trong TENT đã thêm vào PATH C (0) (2) (2) F B (3) (3) G E (5) D (7) A
19. Thuật toán Dijkstra’s LSR
    Tạo ra database forward: Forwarding Database C (0) Destination Port (2) (2) C C F B FF (3) (3) G GF E BB (5) EB D DB (7) A AB