Định tuyến sống, đường ngắn nhất khi mạng đổi
Đị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, tuyến tự tìm đường vòng khác và tổng chi phí luôn tăng, không phải "thường tăng": tuyến cũ đã là rẻ nhất, nên bỏ đi một mắt của nó thì mọi lựa chọn còn lại đều đắt hơ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í).
Mở bài, tuyến rẻ nhất từ A tới F là A → C → B → D → E → F với tổng 13, chứ không phải
đường trông thẳng hơn là A → B → D → F vốn tốn 15. Đây là chỗ trực giác hình học hay đánh lừa:
vị trí node trên màn hình không mang chi phí nào cả.
Hãy thử cắt lần lượt từng dây trong chín dây. Năm dây nằm trên tuyến vàng, cắt dây nào cũng đẩy
chi phí lên 14 hoặc 15. Bốn dây còn lại nằm ngoài tuyến, và cắt cả bốn đều
không đổi một đơn vị nào, vì tuyến rẻ nhất vốn không đi qua chúng. Đó là một cách nhìn khác về chữ "ngắn nhất":
thuật toán chỉ phụ thuộc vào phần đồ thị mà nó thật sự dùng tới.
Có thể xảy ra chuyện hai tuyến rẻ ngang nhau. Cuộn chuột hạ trọng số dây A-B xuống 3 thì
A → B → D → E → F và A → C → B → D → E → F cùng tốn 13, mà sim chỉ tô vàng được một.
Nó tô cái nào là do luật phá hoà: thuật toán chỉ thay cha khi tìm được đường rẻ hơn hẳn, nên
nó giữ đường tìm thấy trước, ở đây là A → B. Đổi luật thành "rẻ hơn hoặc bằng" sẽ cho tuyến kia,
và tổng chi phí vẫn là 13. Bài toán đường đi ngắn nhất chỉ định nghĩa duy nhất cái chi phí,
không định nghĩa duy nhất cái tuyế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.
- 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?
- 2Con số d= trên một node có nghĩa là gì?
- 3Vì sao kéo một node không làm tuyến đổi?