Thuật toán gồm các bước sau: Mỗi nút tính khoảng cách giữa nó và tất cả các nút khác trong hệ thống tự chủ và lưu trữ thông tin này trong một bảng. Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận. Khi một nút nhận được các bảng thông tin từ các nút lân cận, nó tính các tuyến đường ngắn nhất tới tất cả các nút khác và cập nhật bảng thông tin của chính mình. | Bài tiểu luận: Thuật toán vector khoảng cách Nhóm 2 : nội dung Ví dụ Ưu và nhược điểm Đặc điểm 1. Đặc điểm của thuật toán vector khoảng cách Thuật toán gồm các bước sau: 1. Mỗi nút tính khoảng cách giữa nó và tất cả các nút khác trong hệ thống tự chủ và lưu trữ thông tin này trong một bảng 2. Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận. 3. Khi một nút nhận được các bảng thông tin từ các nút lân cận, nó tính các tuyến đường ngắn nhất tới tất cả các nút khác và cập nhật bảng thông tin của chính mình. [ 2. Ví dụ Mỗi nút thiết lập một mảng một chiều (vector) chứa khoảng cách từ nó đến tất cả các nút còn lại và sau đó phát vector này đến tất cả các nút lân cận của nó. Giả thiết Mỗi nút phải biết được trọng số của các đường nối từ nó đến tất cả các nút láng giềng Một kết nối bị đứt sẽ được gán cho giá trị vô cùng Khởi đầu, mỗi nút đặt giá trị 1 cho đường kết nối đến các nút láng giềng kề nó, cho các đường nối đến tất cả các nút còn lại Thông tin được lưu tại các nút Khoảng cách đến nút A B C D E F G A 0 1 1 ∞ 1 1 ∞ B 1 0 1 ∞ ∞ ∞ ∞ C 1 1 0 1 ∞ ∞ ∞ D ∞ ∞ 1 0 ∞ ∞ 1 E 1 ∞ ∞ ∞ 0 ∞ ∞ F 1 ∞ ∞ ∞ ∞ 0 1 G ∞ ∞ ∞ 1 ∞ 1 0 Lúc đầu A tin rằng nó có thể tìm đến B qua một bước nhảy (hop) và rằng nó không thể đi đến D được. Bảng vạch đường lưu tại A thể hiện những gì mà A có được, ngoài ra còn lưu thêm nút kế tiếp mà A cần phải đi ra để đến một nút nào đó. Đích (Destination) Trọng số (Cost) Nút kế tiếp (Next Hop) B 1 B C 1 C D ∞ - E 1 E F 1 F G ∞ - Đích (Destination) (Cost) Nút kế tiếp (Next Hop) B 1 B C 1 C D 2 C E 1 E F 1 F G 2 F Bước kế tiếp trong giải thuật vạch đường Distance-Vector là: Mỗi nút sẽ gởi một thông điệp đến các láng giềng liền kề nó, trong thông điệp đó chứa danh sách các khoảng cách mà cá nhân nút tính được VD nút F bảo nút A rằng F có thể đi đến nút G với chi phí là 1; A cũng biết được rằng nó có thể đến F với chi phí là 1, vì thế A cộng các chi phí lại thành chi phí đi đến G là 2 thông qua F Thông tin được lưu tại các nút Khoảng cách đến nút A B C D E F G A 0 1 1 2 1 1 2 B 1 0 1 2 2 2 3 C 1 1 0 1 2 2 2 D 2 2 1 0 3 2 1 E 1 2 2 3 0 2 3 F 1 2 2 2 2 0 1 G 2 3 2 1 3 1 0 Nếu không có sự thay đổi về hình trạng mạng nào, chỉ cần vài cuộc trao đổi thông tin vạch đường giữa các nút trong mạng thì mọi nút đều có được thông tin vạch đường hoàn hảo. Ví dụ 2 Ưu và nhược điểm Ưu điểm : + Cấu hình đơn giản + Cho phép tất cả các nút đạt được thông tin vạch đường + Xác định đướng đi nhanh chóng, chính xác + Khả năng tránh được các nối kết bị tắt nghẽn tạm thời Nhược điểm - Tăng thời gian trễ Your Company Slogan Thank You !
