Bài tiểu luận: Thuật toán vector khoảng cách

Chia sẻ: Pham Van Thanh Thanh | Ngày: | Loại File: PPT | Số trang:14

Thêm vào BST

Báo xấu

304
lượt xem 54
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tiểu luận: Thuật toán vector khoảng cách

LOGO www.themegallery.com . Bài tiểu luận: Thuật toán vector khoảng cách Nhóm 2 :
. nội dung Đặc điểm Ví dụ Ưu và nhược điểm www.themegallery.com
. 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. www.themegallery.com
. 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 www.themegallery.com
Khoảng cách đến nút A B C D E F G Khởi đầu, mỗi nút đặt giá trị 1 cho Thông tin được đường kết nối đến các nút láng lưu tại các nút giềng kề nó, ∞ cho các đường nối đến tất cả các nút còn lại A 0 1 1 ∞ 1 1 ∞ 1 0 1 B ∞ ∞ ∞ ∞ C 1 1 0 1 ∞ ∞ ∞ D ∞ ∞ 1 0 ∞ ∞ 1 E 1 ∞ ∞ ∞ 0 ∞ ∞ F 1 ∞ ∞ ∞ ∞ 0 1 G ∞ ∞ ∞ 1 ∞ 1 0 www.themegallery.com
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 Đích (Destination) Trọng số (Cost) Nút kế tiếp (Next 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 Hop) ra để đến một nút nào đó. B 1 B C 1 C D ∞ - Bước kế tiếp trong giải thuật vạch E 1 E đường Distance-Vector là: F 1 F Mỗi nút sẽ gởi một thông điệp đến các G ∞ - Đích (Cost) Nút kế tiếp láng giềng liền kề nó, trong thông điệp đó (Destination) (Next Hop) chứa danh sách các khoảng cách mà cá B 1 B nhân nút tính được C 1 C VD nút F bảo nút A rằng F có thể đi đến D 2 C nút G với chi phí là 1; A cũng biết được E 1 E rằng nó có thể đến F với chi phí là 1, vì thế F 1 F A cộng các chi phí lại thành chi phí đi đến G 2 F G là 2 thông qua F www.themegallery.com
Thông tin được lưu tại Khoảng cách đến nút các nút A B C D E F G A 0 1 1 2 1 1 2 Nếu không có sự thay đổi về hình trạng mạng nào, chỉ cần vài B 1 0 1 2 2 2 3 cuộc trao đổi thông tin vạch đường giữa các nút trong mạng thì mọi nút C 1 1 0 1 2 2 2 đều có được thông tin vạch đường hoàn hảo. 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 www.themegallery.com
. Ví dụ 2 www.themegallery.com
Ư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ễ www.themegallery.com
LOGO www.themegallery.com Your Company Slogan
www.themegallery.com
www.themegallery.com
www.themegallery.com
www.themegallery.com