Định tuyến sống, đường ngắn nhất khi mạng đổi

DijkstraĐường đi ngắn nhấtTương tác thật

Định tuyến sống

Bạn sửa mạng, thuật toán tính lại. Đường đi ngắn nhất không phải một hình vẽ chết, nó phản ứng với mọi thay đổi.

Ở các bài trước, bạn xem thuật toán tìm kiếm mở rộng frontier từng bước trên một đồ thị cố định. Đó là cách nhìn từ bên trong thuật toán. Bài này đổi góc: giữ nguyên đồ thị nhưng để bạn cầm quyền sửa nó, còn thuật toán thì phải chạy theo. Đây đúng là cách một router thật hành xử khi một sợi cáp đứt: nó không diễn lại một hoạt cảnh dựng sẵn, nó tính lại tuyến.

Bài toán: chọn đường rẻ nhất trên đồ thị có trọng số

Mỗi node là một điểm trong mạng, mỗi cạnh có một trọng số là chi phí đi qua nó (độ trễ, số chặng, giá thuê đường). Ta muốn đi từ nguồn tới đích sao cho tổng chi phí nhỏ nhất. Với đồ thị có trọng số không âm, Dijkstra trả lời bài toán này: nó giữ cho mỗi node một con số d là chi phí rẻ nhất đã biết để tới node đó từ nguồn, rồi lặp đi lặp lại việc chọn node có d nhỏ nhất mà chưa xử lý, và cập nhật các hàng xóm của nó. Khi dừng, d của đích chính là chi phí tối ưu, và lần theo con trỏ cha ta dựng lại được tuyến.

Thử ngay: sửa mạng và xem tuyến đổi

Đây không phải một GIF. Mỗi thao tác bên dưới đổi một con số thật và buộc Dijkstra chạy lại:

• Nhấp vào một dây để cắt liên kết đó, như thể cáp bị đứt. Nếu dây vàng (tuyến hiện tại) bị cắt, hãy để ý tuyến tự tìm đường vòng khác, và tổng chi phí thường tăng lên.
• Cuộn chuột trên một dây để tăng hoặc giảm trọng số. Làm một đường trở nên đắt đỏ và xem thuật toán bỏ nó để chọn lối rẻ hơn.
• Đổi nguồn hoặc đích ở hai ô chọn phía trên.
• Kéo node chỉ để sắp lại cho dễ nhìn, thao tác này không đổi kết quả (vị trí không phải chi phí).

Định tuyến sống · Dijkstra tính lại theo bạn

TừABCDEFĐếnABCDEF

Chi phí: 13 · A → C → B → D → E → F

Nhấp một dây để cắt/nối (mô phỏng đứt cáp) · cuộn chuột trên dây để tăng/giảm trọng số · kéo node để sắp lại cho dễ nhìn. Mỗi thay đổi đều khiến engine chạy lại Dijkstra — số d= trên mỗi node là khoảng cách ngắn nhất từ nguồn.

Con số d= trên mỗi node là chi phí rẻ nhất từ nguồn tới node đó. Node nào hiện ∞ nghĩa là sau khi bạn cắt vài dây, không còn đường nào tới được nó nữa. Nhấn Chạy gói để một gói tin chạy dọc đúng tuyến vừa tính, không phải một đường cố định.

Vì sao đây là "tính lại thật" chứ không phải phát lại

Điểm mấu chốt của một minh họa tốt là: khi bạn đổi đầu vào, hệ phải tính lại đầu ra bằng chính thuật toán, chứ không tua lại một hoạt cảnh đã quay sẵn. Ở đây trọng số, trạng thái đứt cáp, nguồn và đích đều là dữ liệu, và mỗi lần chúng đổi thì hàm Dijkstra chạy lại từ đầu rồi vẽ lại. Nếu một nút bấm không làm con số nào đổi, nút đó là nút giả và không nên tồn tại.

Nối với router thật

Trong một router, phần vừa mô phỏng chính là mặt phẳng điều khiển: giao thức như OSPF thu thập topology rồi chạy Dijkstra để tìm đường ngắn nhất, kết quả nạp vào bảng định tuyến. Khi một liên kết chết, giao thức phát hiện, cập nhật topology, và chạy lại thuật toán y như lúc bạn nhấp cắt một dây. Còn việc bê từng gói tin đi theo bảng đó ở tốc độ phần cứng là mặt phẳng dữ liệu, một câu chuyện khác về tốc độ chứ không phải về việc chọn đường.

Kiểm tra nhanh0/3 đúngchưa trả lời

1. 1Khi bạn cắt đúng liên kết đang nằm trên tuyến vàng, điều gì xảy ra?
2. 2Con số d= trên một node có nghĩa là gì?
3. 3Vì sao kéo một node không làm tuyến đổi?