Kỹ thuật truyền số liệu : Tìm đường trong mạng chuyển mạch part 4

• Bellman-Ford– Việc tính toán cho node n phải biết các thông tin về chi phí liên kết của các node kề của n và chi phí tổng cộng từ node s đến các node kề của node n [i.e., Lh(j)] – Mỗi node cần lưu trữ tập các chi phí và các đường đi tương ứng
Nội dung trích xuất từ tài liệu:
Kỹ thuật truyền số liệu : Tìm đường trong mạng chuyển mạch part 4dce Giải thuật Bellman-Ford 2008 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 31dce Bài tập 2008 • Tìm đường ngắn nhất từ node 1 – Theo giải thuật Dijkstra – Theo giải thuật Bellman-Ford 4 1 2 3 3 6 1 2 1 2 3 4 5 3 4 3 1 5 7 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 32dce Bài tập 2008 • Tìm đường ngắn nhất từ node A – Theo giải thuật Dijkstra – Theo giải thuật Bellman-Ford 1 1 E A B 2 1 2 5 2 G C 3 1 F D 2 1 4 1 1 H K J Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 33dce Dijkstra vs. Bellman-Ford 2008 • Bellman-Ford – Việc tính toán cho node n phải biết các thông tin về chi phí liên kết của các node kề của n và chi phí tổng cộng từ node s đến các node kề của node n [i.e., Lh(j)] – Mỗi node cần lưu trữ tập các chi phí và các đường đi tương ứng đến các node khác – Có thể trao đổi thông tin với các node kề trực tiếp – Có thể cập nhật thông tin về chi phí và đường đi dựa trên các thông tin trao đổi với các node kề và các thông tin về chi phí liên kết • Dijkstra – Mỗi node cần biết topology toàn bộ mạng – Phải biết chi phí liên kết của tất cả các liên kết trong mạng – Phải trao đổi thông tin với tất cả các node khác trong mạng Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 34dce Đánh giá 2008 • Phụ thuộc vào thời gian xử lý của các giải thuật • Phụ thuộc vào lượng thông tin yêu cầu từ các node khác • Phụ thuộc vào việc hiện thực • Cùng hội tụ về một lời giải dưới điều kiện topology tĩnh và chi phí không thay đổi • Nếu chi phí liên kết thay đổi, các giải thuật sẽ tính lại để theo kịp sự thay đổi • Nếu chi phí liên kết thay đổi theo lưu thông, lưu thông lại thay đổi theo đường đi được chọn – Phản hồi – Có thể rơi vào trạng thái không ổn định Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 35dce ARPANET – Tìm đường 2008 • Thế hệ đầu tiên – 1969 – Distributed adaptive – Dùng thời gian trễ ước tính làm tiêu chuẩn để đánh giá hiệu quả – Dùng giải thuật tìm đường Bellman-Ford – Các node trao đổi thông tin (các vector thời gian trễ) với các node kề – Cập nhật bảng tìm đường dựa trên thông tin đến – Không quan tâm đến tốc độ đường truyền, chỉ quan tâm chiều dài hàng đợi tại các node – Chiều dài hàng đợi không phải là cách đo chính xác của thời gian trễ – Đáp ứng chậm với nghẽn mạch Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 36dce ARPANET – Tìm đường 2008 • Thế hệ thứ 2 – 1979 – Dùng thời gian trễ làm tiêu chuẩn đánh giá hiệu quả – Thời gian trễ được đo trực tiếp – Dù ...