Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Mạng máy tínhĐọc trong 13 phút

Định tuyến trạng thái liên kết (link-state) và thuật toán Dijkstra, từng bước một

Trong định tuyến trạng thái liên kết, trước hết mỗi bộ định tuyến thu thập bản đồ đầy đủ của mạng, rồi chạy thuật toán Dijkstra trên đó để tìm đường đi rẻ nhất đến mọi đích. Bài thi yêu cầu bạn điền bảng của nó bằng tay, nên bài hướng dẫn này làm trọn một bảng.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Mạng máy tính

Chương 5 · Các thuật toán định tuyến
Biên soạn từ

Kurose và Ross, Computer Networking: A Top-Down Approach, mục 5.1 và 5.2.1, đối chiếu với RFC 2328 (OSPF Version 2), giao thức trạng thái liên kết tiêu chuẩn. Mọi con số trong các bảng ví dụ đều đã được tính lại bằng mã.

Cách sử dụng

Hãy chép bảng ví dụ ra giấy rồi làm lại khi đã che trang đi. Câu hỏi về Dijkstra được chấm điểm trên bảng, nên hãy viết mọi hàng, không chỉ đáp án cuối.

Bức tranh chung: ai cũng có cùng một bản đồ#

Hãy hình dung sáu người bạn ở sáu thị trấn. Mỗi người nhận cùng một tấm bản đồ đường bộ in sẵn, cho thấy mọi con đường và thời gian đi hết bao nhiêu phút. Không ai phải hỏi đường. Mỗi người tự tìm đường nhanh nhất từ thị trấn của mình đến mọi thị trấn khác.

Đó là định tuyến trạng thái liên kết (link-state routing). Các thị trấn là bộ định tuyến, các con đường là liên kết, và số phút là chi phí liên kết. Trước tiên ai cũng có cùng một bản đồ đầy đủ. Sau đó mỗi bộ định tuyến tự tìm các tuyến tốt nhất của mình từ bản đồ đó.

Phương pháp mà mỗi người bạn dùng là thuật toán Dijkstra. Giống như gợn sóng trên mặt ao, nó chốt thị trấn gần nhất trước, rồi đến thị trấn gần nhì, cho đến khi mọi thị trấn đều được chốt.

Từ vựng, trước khi dùng đến#

Thuật ngữÝ nghĩa
Đồ thị (graph)Một tập hợp các nút (ở đây là bộ định tuyến) được nối bằng các cạnh (ở đây là liên kết). Viết là G = (N, E): N là tập hợp các nút và E là tập hợp các cạnh.
Chi phí liên kết, c(x, y)Một con số trên cạnh giữa nút x và nút y. Càng thấp càng tốt. Nó có thể biểu thị độ trễ, tiền bạc, hoặc 1 cho mỗi chặng. Nếu x và y không được nối với nhau, c(x, y) = ∞ (vô cực).
Hàng xóm (neighbor)Hai nút là hàng xóm nếu có một cạnh nối trực tiếp chúng.
Đường đi chi phí thấp nhấtĐường đi giữa hai nút mà các chi phí liên kết cộng lại cho tổng nhỏ nhất.
Quảng bá trạng thái liên kếtMỗi nút gửi chi phí các liên kết của chính nó đến mọi nút khác, nên cuối cùng tất cả các nút có cùng một bản đồ đầy đủ.
Nút nguồn (source)Nút đang chạy thuật toán, thường viết là u. Nó tìm các đường đi chi phí thấp nhất từ chính nó đến mọi nút khác.
D(v)Chi phí của đường đi rẻ nhất từ nút nguồn đến nút v tìm được cho đến lúc này, ở bước hiện tại.
p(v)Nút đứng trước (predecessor) của v: nút đứng ngay trước v trên đường đi rẻ nhất tìm được cho đến lúc này.
N′Đọc là “N prime”. Tập hợp các nút đã biết chắc đường đi chi phí thấp nhất. Nó bắt đầu chỉ với nút nguồn và thêm một nút ở mỗi bước.

Định tuyến như một bài toán đồ thị, và các loại thuật toán định tuyến#

Thuật toán định tuyến là phương pháp tìm những đường đi tốt qua mạng. Về bản chất, mọi thuật toán đều giải cùng một bài toán: tìm đường đi chi phí thấp nhất trong một đồ thị. Chi phí của một đường đi là tổng các chi phí liên kết dọc theo nó. Nếu mọi liên kết đều có chi phí 1, đường đi chi phí thấp nhất đơn giản là đường có ít chặng nhất.

Đây là mạng mà bài hướng dẫn này dùng. Nó có sáu bộ định tuyến (A, B, C, E, F và G) và chín liên kết. Không có bộ định tuyến D, nên chữ D chỉ luôn có nghĩa là một chi phí. Mọi chi phí đều như nhau theo cả hai chiều.

Liên kếtChi phíLiên kếtChi phí
A–B2C–G8
A–C1E–F3
B–C2E–G2
B–G5F–G6
C–E10

Ba cách phân loại một thuật toán định tuyến

Câu hỏiMột loạiLoại còn lại
Ai biết toàn bộ bản đồ?Tập trung (toàn cục): mỗi nút bắt đầu với bản đồ đầy đủ. Trạng thái liên kết thuộc loại này.Phân tán: mỗi nút chỉ biết các liên kết của riêng mình và trao đổi các ước lượng với hàng xóm. Vectơ khoảng cách thuộc loại này.
Các tuyến thay đổi thường xuyên đến mức nào?Tĩnh: các tuyến thay đổi chậm, thường do làm bằng tay.Động: các tuyến được tính lại khi lưu lượng hoặc hình dạng của mạng thay đổi.
Chi phí có theo lưu lượng không?Nhạy với tải: chi phí của một liên kết tăng lên khi nó bận.Không nhạy với tải: chi phí bỏ qua tải hiện tại. Các giao thức định tuyến chính của Internet ngày nay thuộc loại này.
Đừng nhầm lẫn các khái niệm này
“Tập trung” không có nghĩa là một máy tính làm hết mọi việc. Trong định tuyến trạng thái liên kết, mỗi bộ định tuyến tự chạy Dijkstra. Nó chỉ có nghĩa là mỗi bộ định tuyến bắt đầu với bản đồ đầy đủ.

Dijkstra cần toàn bộ bản đồ, nên các bộ định tuyến phải dựng nó trước. Mỗi bộ định tuyến chỉ biết các liên kết gắn với nó và chi phí của chúng. Nó gói danh sách đó vào một gói trạng thái liên kết (link-state packet) (còn gọi là thông báo trạng thái liên kết, LSA) và gửi đến mọi bộ định tuyến khác trong mạng. Mỗi bộ định tuyến chuyển tiếp các gói này cho hàng xóm của nó, quá trình này gọi là lan truyền tràn (flooding), cho đến khi mọi bộ định tuyến có một bản sao từ mọi bộ định tuyến khác.

Khi việc lan truyền tràn xong, mọi bộ định tuyến giữ một bản đồ giống hệt nhau. Sau đó mỗi bộ định tuyến chạy Dijkstra với chính nó làm nút nguồn. Vì các bản đồ khớp nhau, các đáp án của chúng ăn khớp với nhau.

Bạn sẽ gặp lại điều này ở đâu

OSPF (Open Shortest Path First), giao thức trạng thái liên kết tiêu chuẩn, hoạt động theo cách này. Nó có bài hướng dẫn riêng ở phần sau trong chương 5.

Thuật toán Dijkstra, giải đầy đủ#

Nút nguồn ở đây là A. Thuật toán có một bước khởi đầu và một vòng lặp.

Khởi đầu. N′ = {A}. Với mỗi nút v khác, đặt D(v) = c(A, v) nếu v là hàng xóm của A, và D(v) = ∞ nếu không. Đặt p(v) = A cho mỗi hàng xóm.

Vòng lặp, cho đến khi mọi nút đều nằm trong N′:

  1. Trong các nút chưa thuộc N′, chọn nút có D nhỏ nhất. Gọi nó là w. Thêm w vào N′. D(w) của nó giờ đã được chốt.
  2. Với mỗi hàng xóm v của w chưa thuộc N′, kiểm tra xem đi qua w có rẻ hơn không:

D(v) = min( D(v), D(w) + c(w, v) )

Nói bằng lời: giữ chi phí cũ, hoặc đi đến w rồi đi theo liên kết tới v, cái nào nhỏ hơn thì chọn. Nếu đi qua w thắng, thì đặt luôn p(v) = w.

Đây là toàn bộ lần chạy từ A. Mỗi ô cho thấy D(v), p(v). Ô trống nghĩa là nút đó đã nằm trong N′, nên giá trị của nó đã được chốt và không đổi nữa.

BướcN′D(B), p(B)D(C), p(C)D(E), p(E)D(F), p(F)D(G), p(G)
0{A}2, A1, A∞∞∞
1{A, C}2, A11, C∞9, C
2{A, C, B}11, C∞7, B
3{A, C, B, G}9, G13, G
4{A, C, B, G, E}12, E
5{A, C, B, G, E, F}

Mục in đậm trong mỗi hàng là D nhỏ nhất chưa được chốt: nút sẽ được thêm vào ở bước tiếp theo.

Ví dụ có lời giải
Bước 2, chi tiết. Sau bước 1, các nút chưa được chốt có D(B) = 2, D(E) = 11, D(F) = ∞ và D(G) = 9. Nhỏ nhất là B, nên B vào N′ với chi phí cuối cùng là 2. Hàng xóm chưa được chốt của B là G, nối bằng một liên kết có chi phí 5. Đi qua B tốn D(B) + c(B, G) = 2 + 5 = 7. Con số đó thắng 9 cũ (đi qua C), nên D(G) trở thành 7 và p(G) trở thành B. Các hàng xóm khác của B, là A và C, đã được chốt rồi.

Từ bảng đến bảng chuyển tiếp

Để đọc đường đi đến một nút bất kỳ, hãy lần ngược theo các nút đứng trước. Với F: p(F) = E, p(E) = G, p(G) = B, p(B) = A. Vậy đường đi là A → B → G → E → F, với chi phí 2 + 5 + 2 + 3 = 12. Làm như vậy cho mọi nút sẽ cho ra cây đường đi ngắn nhất: các liên kết A–B, A–C, B–G, E–G và E–F.

Một bộ định tuyến chỉ cần chặng đầu tiên của mỗi đường đi, vì bộ định tuyến kế tiếp tự đưa ra quyết định của nó. Vậy bảng chuyển tiếp của A là:

ĐíchĐường đi chi phí thấp nhấtChi phíGửi ra liên kết
BA → B2(A, B)
CA → C1(A, C)
EA → B → G → E9(A, B)
FA → B → G → E → F12(A, B)
GA → B → G7(A, B)
Đừng nhầm lẫn các khái niệm này
Một giá trị D chỉ được chốt khi nút của nó vào N′. D(G) là 9 sau bước 1 và giảm xuống 7 sau bước 2. Cũng hãy để ý rằng A đến E với chi phí 9 qua B và G, dù C có liên kết trực tiếp tới E: tuyến đó tốn 1 + 10 = 11. Rẻ nhất không phải lúc nào cũng là ít chặng nhất.

Cần bao nhiêu công việc, và vấn đề dao động#

Chi phí: O(n²)

Giả sử có n nút ngoài nút nguồn. Để tìm D nhỏ nhất, bước đầu xét cả n nút, bước kế tiếp xét n − 1 nút, và cứ thế xuống 1. Tổng cộng là n(n + 1) / 2. Con số đó tăng cỡ n², nên trường hợp xấu nhất được viết là O(n²), đọc là “bậc n bình phương”.

Ví dụ có lời giải

Trong mạng của chúng ta có 5 nút ngoài A, nên thuật toán xét tổng cộng 5 + 4 + 3 + 2 + 1 = 5 × 6 / 2 = 15 nút. Lưu các nút chưa được chốt trong một cấu trúc dữ liệu gọi là heap sẽ làm mỗi bước “tìm giá trị nhỏ nhất” nhanh hơn.

Vấn đề dao động

Rắc rối bắt đầu khi chi phí liên kết nhạy với tải, nghĩa là chi phí của một liên kết bằng lượng lưu lượng mà nó đang chở. Hãy hình dung hai tuyến từ S đến T: một tuyến trên và một tuyến dưới. S gửi 10 đơn vị lưu lượng.

  1. Cả hai tuyến lúc đầu đều trống, nên cả hai có chi phí 0, và thế hòa được phá theo hướng tuyến trên. Bây giờ tuyến trên có chi phí 10 và tuyến dưới có chi phí 0.
  2. Mọi bộ định tuyến chạy lại Dijkstra. Tuyến dưới rẻ hơn, nên toàn bộ lưu lượng chuyển sang đó. Bây giờ tuyến dưới có chi phí 10 và tuyến trên có chi phí 0.
  3. Mọi bộ định tuyến lại chạy lại Dijkstra, và toàn bộ lưu lượng quay về tuyến trên.

Các tuyến cứ lật qua lật lại và không bao giờ ổn định. Đó là dao động (oscillation). Một cách khắc phục là không cho chi phí phụ thuộc vào tải, dù sách giáo khoa bác bỏ cách này vì khi đó các bộ định tuyến không thể lái lưu lượng tránh chỗ tắc nghẽn. Cách tốt hơn là ngăn các bộ định tuyến cùng chạy lại một lúc, bằng cách để mỗi bộ gửi các gói trạng thái liên kết vào một thời điểm hơi ngẫu nhiên.

Một câu để mang vào phòng thi

Trong định tuyến trạng thái liên kết, mỗi bộ định tuyến gửi tràn chi phí các liên kết của chính nó để mọi bộ định tuyến chia sẻ một bản đồ đầy đủ, rồi mỗi bộ chạy Dijkstra từ chính nó, ở mỗi bước chốt nút chưa chốt rẻ nhất và cập nhật D(v) = min(D(v), D(w) + c(w, v)), việc này tốn O(n²) và cho ra một cây đường đi ngắn nhất mà các chặng đầu của nó trở thành bảng chuyển tiếp.

Luyện tập#

Hãy viết ra toàn bộ bảng Dijkstra bất cứ khi nào câu hỏi có liên quan đến nó. Các hàng trong bảng mới là chỗ ghi điểm.

  1. Hãy phân loại thuật toán Dijkstra khi dùng trong định tuyến trạng thái liên kết: tập trung hay phân tán? Sau đó nói rõ bộ định tuyến phải có thông tin gì trước khi có thể bắt đầu.
  2. Dùng mạng sáu bộ định tuyến trong bài hướng dẫn này, hãy chạy Dijkstra với G làm nút nguồn. Cho biết chi phí thấp nhất cuối cùng đến mọi nút khác và bảng chuyển tiếp của G (mỗi đích được gửi đến hàng xóm nào).
  3. Trong bảng ví dụ từ A, D(E) là 11 sau bước 1 và 9 sau bước 3. Nút nào gây ra thay đổi đó, và phép tính là gì?
  4. Chi phí của liên kết E–G tăng từ 2 lên 6, và A chạy lại Dijkstra. Chi phí thấp nhất mới của A đến E và đến F là bao nhiêu, và bây giờ A dùng liên kết nào để đến E?
  5. Một mạng có 21 bộ định tuyến. Dùng phiên bản đơn giản của Dijkstra, tổng cộng một bộ định tuyến xét bao nhiêu nút để tìm D nhỏ nhất trong cả lần chạy?
  6. Giải thích vì sao chi phí liên kết theo tải lưu lượng có thể làm các tuyến dao động, và nêu một cách khắc phục.

Lời giải#

Cách học tốt nhất

Hãy tìm dòng đầu tiên mà cách làm của bạn khác với lời giải, rồi làm lại bài từ dòng đó. Đừng chỉ đọc đáp án rồi gật đầu.

  1. Tập trung (toàn cục). Mỗi bộ định tuyến tự chạy nó, nhưng chỉ sau khi quảng bá trạng thái liên kết đã cho nó bản đồ đầy đủ: mọi liên kết và chi phí của chúng.
  2. A 7, B 5, C 7, E 2, F 5. Chuyển tiếp: A, B và C đi qua B; E và F đi qua E. Khởi đầu: D(B) = 5, D(C) = 8, D(E) = 2, D(F) = 6, D(A) = ∞. Chốt E (2): F cải thiện thành 2 + 3 = 5 qua E; C qua E sẽ là 12, tệ hơn 8. B và F giờ hòa nhau ở 5; thứ tự nào cũng cho cùng đáp án. Chốt B (5): A thành 5 + 2 = 7 qua B, và C cải thiện thành 5 + 2 = 7 qua B. Chốt F, A và C không cải thiện thêm gì. Các đường đi: G→B→A, G→B, G→B→C, G→E, G→E→F.
  3. Nút G, khi nó vào N′ ở bước 3. D(G) + c(G, E) = 7 + 2 = 9, con số này thắng 11 cũ (qua C, 1 + 10), nên D(E) trở thành 9 và p(E) trở thành G.
  4. E có chi phí 11, F có chi phí 13, và E được đến qua liên kết (A, C). Qua B và G, E bây giờ sẽ tốn 7 + 6 = 13, nên tuyến A → C → E với 1 + 10 = 11 thắng. F giờ tốt nhất là A → B → G → F với 2 + 5 + 6 = 13.
  5. 210. Có n = 20 nút ngoài nút nguồn, nên tổng là n(n + 1) / 2 = 20 × 21 / 2 = 210.
  6. Việc chuyển lưu lượng làm thay đổi chính các chi phí đã chọn tuyến. Mọi bộ định tuyến cùng chuyển sang đường rẻ hơn, khiến nó thành đường đắt, nên lần chạy sau tất cả lại chuyển về. Cách khắc phục: không cho chi phí liên kết phụ thuộc vào tải, hoặc cho các bộ định tuyến chạy (và gửi gói trạng thái liên kết) vào những thời điểm ngẫu nhiên để chúng không cùng chuyển một lúc (cách được ưa chuộng hơn).

Danh sách kiểm tra trước khi thi#

  • ☐  Tôi có thể mô tả một mạng như một đồ thị với chi phí liên kết c(x, y), và nói c(x, y) = ∞ có nghĩa là gì.
  • ☐  Tôi có thể xếp một thuật toán định tuyến theo ba cách phân loại: tập trung hay phân tán, tĩnh hay động, nhạy với tải hay không.
  • ☐  Tôi có thể giải thích cách quảng bá trạng thái liên kết giúp mọi bộ định tuyến có cùng một bản đồ.
  • ☐  Tôi có thể điền một bảng Dijkstra đầy đủ với N′, D(v) và p(v), mỗi bước một hàng.
  • ☐  Tôi có thể đọc các đường đi từ các nút đứng trước và biến chúng thành một bảng chuyển tiếp.
  • ☐  Tôi có thể nêu chi phí O(n²) và tính n(n + 1) / 2 cho một mạng cho trước.
  • ☐  Tôi có thể giải thích vấn đề dao động và một cách tránh nó.
Một quy tắc cuối cùng

Trong mỗi hàng của Dijkstra, làm hai việc theo thứ tự: trước tiên chốt nút chưa chốt có D nhỏ nhất, rồi chỉ cập nhật các hàng xóm chưa chốt của nó.

Câu hỏi thường gặp#

Định tuyến trạng thái liên kết là gì?

Mỗi bộ định tuyến gửi tràn chi phí các liên kết của chính nó đến mọi bộ định tuyến khác, nên ai cũng có bản đồ đầy đủ. Sau đó mỗi bộ định tuyến chạy một thuật toán tìm đường chi phí thấp nhất, thường là Dijkstra, xuất phát từ chính nó. OSPF là ví dụ tiêu chuẩn.

D(v), p(v) và N prime nghĩa là gì trong thuật toán Dijkstra?

D(v) là chi phí của đường đi rẻ nhất từ nút nguồn đến v tìm được cho đến lúc này. p(v) là nút đứng ngay trước v trên đường đó. N prime là tập hợp các nút đã có đường đi chi phí thấp nhất được chốt.

Độ phức tạp thời gian của thuật toán Dijkstra trong định tuyến trạng thái liên kết là bao nhiêu?

Ở dạng đơn giản, nó là O(n bình phương). Với n nút ngoài nút nguồn, để tìm mỗi giá trị nhỏ nhất nó xét n nút, rồi n trừ 1 nút, và cứ thế xuống 1 nút, tổng cộng là n(n + 1) / 2. Phiên bản dùng heap thì nhanh hơn.

Làm sao lấy bảng chuyển tiếp từ thuật toán Dijkstra?

Lần ngược theo các nút đứng trước từ mỗi đích để tìm đường đi chi phí thấp nhất của nó, rồi chỉ giữ lại chặng đầu tiên. Bảng chuyển tiếp ánh xạ mỗi đích tới liên kết hướng về hàng xóm ở chặng đầu đó.

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn mong chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có một bài hướng dẫn mới.

Tự kiểm tra về chủ đề này

Ứng dụng luyện tập mạng máy tính miễn phí có 10 câu hỏi về bài hướng dẫn này và 500 câu cho toàn bộ môn học, mỗi đáp án đều có giải thích. Dùng được khi không có mạng, không quảng cáo, không cần tài khoản.

Luyện tập chủ đề này →