Kurose và Ross, Computer Networking: A Top-Down Approach, các mục 5.1 và 5.2.2, đối chiếu với RFC 2453 (RIP Version 2; RIP là Routing Information Protocol), một giao thức vectơ khoảng cách có đặc tả mô tả split horizon (không bao giờ quảng bá một tuyến ngược lại cho láng giềng mà nó được học từ đó) với poisoned reverse (thay vào đó quảng bá ngược lại là vô cực), và coi metric 16 là vô cực. Mọi chuỗi cập nhật bên dưới đều được mô phỏng bằng mã.
Hãy học phương trình và nói nó bằng lời. Sau đó làm lại các ví dụ ba bộ định tuyến trên giấy, mỗi cập nhật một dòng.
Hình dung: hỏi các láng giềng đường đi#
Hãy hình dung bạn ở một thị trấn không có bản đồ. Bạn biết mỗi con đường tới thị trấn bên cạnh mất bao lâu. Mỗi người bạn bên cạnh gửi bạn một danh sách: “Từ đây, tôi tới Z mất 9 phút, tới Y mất 4.”
Để tìm thời gian tốt nhất của chính bạn tới Z, bạn cộng con đường của bạn tới mỗi người bạn vào thời gian tới Z của người bạn đó, và giữ tổng nhỏ nhất. Sau đó bạn gửi danh sách mới của bạn cho các láng giềng của mình, và họ làm điều tương tự.
Đó là định tuyến vectơ khoảng cách. Không ai có toàn bộ bản đồ. Các đáp án lan ra từng láng giềng một cho đến khi mọi danh sách ngừng thay đổi.
Từ vựng, trước khi dùng đến#
| Thuật ngữ | Ý nghĩa |
|---|---|
| c(x, v) | Chi phí của liên kết trực tiếp từ nút x tới láng giềng v của nó. |
| dx(y) | Chi phí nhỏ nhất thực sự của một đường đi từ nút x tới nút y. |
| Dx(y) | Ước lượng hiện tại của nút x về chi phí nhỏ nhất đó. Nó có thể sai cho đến khi mạng ổn định. |
| Vectơ khoảng cách, Dx | Danh sách các ước lượng của nút x tới mọi đích: [Dx(y) cho mọi y]. |
| Chặng kế tiếp (next hop) | Láng giềng ở liên kết đầu tiên của đường đi tốt nhất. |
| Hội tụ (converge) | Ổn định: ước lượng của mọi nút ngừng thay đổi và bằng các chi phí nhỏ nhất thực sự. |
| Vòng lặp định tuyến (routing loop) | Hai hoặc nhiều bộ định tuyến, mỗi bộ chuyển tiếp gói tin cho một đích tới bộ kế tiếp theo vòng tròn, nên các gói tin cứ quay vòng. |
| Count-to-infinity | Sau khi một liên kết xấu đi, các bộ định tuyến tăng ước lượng của mình từng bước nhỏ, mỗi lần trao đổi một bước, thay vì nhảy thẳng tới đáp án đúng. |
| Poisoned reverse | Nếu x tới y qua láng giềng z, x báo cho z rằng khoảng cách của nó tới y là ∞. RIP gọi đây là “split horizon with poisoned reverse”. |
Phương trình Bellman-Ford#
Mọi thứ trong định tuyến vectơ khoảng cách đều đến từ một phương trình:
dx(y) = minv { c(x, v) + dv(y) }
Hãy đọc nó như sau: “chi phí rẻ nhất của tôi tới y là, trên mọi láng giềng v của tôi, giá trị nhỏ nhất của (liên kết của tôi tới v) cộng (chi phí rẻ nhất của v tới y)”.
Vì sao nó đúng? Mọi đường đi từ x tới y phải rời x qua một liên kết tới một láng giềng nào đó. Từ đó, điều tốt nhất có thể là chi phí nhỏ nhất của chính láng giềng đó. Láng giềng cho giá trị nhỏ nhất là chặng kế tiếp, được đưa vào bảng chuyển tiếp.
Ba bộ định tuyến, P, Q và R. Các liên kết có chi phí c(P, Q) = 3, c(Q, R) = 1 và c(P, R) = 21. Q biết chi phí của nó tới R là 1, và chi phí của R tới chính nó là 0. P tính chi phí của mình tới R:
DP(R) = min { c(P, Q) + DQ(R), c(P, R) + DR(R) } = min { 3 + 1, 21 + 0 } = 4.
Giá trị nhỏ nhất đến từ Q, nên bảng chuyển tiếp của P gửi lưu lượng cho R tới Q, không qua liên kết trực tiếp có chi phí 21.
Thuật toán chạy như thế nào#
Mỗi nút x giữ ba thứ: chi phí c(x, v) của mỗi liên kết của chính nó, vectơ khoảng cách của chính nó Dx, và vectơ khoảng cách mới nhất nó đã nghe từ mỗi láng giềng. Rồi nó lặp mãi mãi:
- Chờ cho đến khi một láng giềng gửi vectơ khoảng cách mới, hoặc một trong các chi phí liên kết của chính x thay đổi.
- Tính lại Dx(y) cho mọi đích y, dùng phương trình Bellman-Ford.
- Nếu có gì thay đổi, gửi vectơ mới tới mọi láng giềng.
Vậy thuật toán là phân tán: mỗi nút chỉ làm việc với những gì các láng giềng của nó cho biết. Nó lặp: nó lặp lại cho đến khi không còn gì thay đổi, rồi tự dừng. Nó bất đồng bộ: các nút không chạy đồng bộ từng nhịp.
| Bộ định tuyến | Trước mọi lần trao đổi | Sau một lần trao đổi |
|---|---|---|
| P | 0, 3, 21 | 0, 3, 4 |
| Q | 3, 0, 1 | 3, 0, 1 |
| R | 21, 1, 0 | 4, 1, 0 |
P hạ chi phí của nó tới R từ 21 xuống 4 (qua Q), và R hạ chi phí của nó tới P xuống 4 theo cách tương tự: min{1 + 3, 21 + 0} = 4. Lần trao đổi thứ hai không thay đổi gì: mạng đã hội tụ.
Khi chi phí một liên kết thay đổi: tin tốt và tin xấu#
Khi một trong các liên kết của chính một bộ định tuyến đổi chi phí, nó tính lại và báo cho các láng giềng nếu vectơ của nó thay đổi. Mọi thứ ổn định nhanh hay chậm tùy tin đó là tốt hay xấu. Chỉ theo dõi khoảng cách của mỗi bộ định tuyến tới P.
Tin tốt lan nhanh
Bắt đầu từ mạng đã hội tụ, nơi Q tới P với chi phí 3 (trực tiếp) và R tới P với chi phí 4 (qua Q). Giờ c(P, Q) giảm từ 3 xuống 1.
- Bước 0: Q tính lại: min{1 + 0, 1 + 4} = 1, trực tiếp. Q báo cho R.
- Bước 1: R tính lại: min{21 + 0, 1 + 1} = 2, qua Q. R báo cho Q.
- Bước 2: Q tính lại: vẫn là 1. Không có gì thay đổi, nên không gửi gì. Xong.
Tin xấu lan chậm
Lại bắt đầu từ mạng đã hội tụ. Giờ c(P, Q) vọt từ 3 lên 50. Đáp án đúng là R trực tiếp (21) và Q qua R (22). Đây là những gì xảy ra:
| Bước | Ai cập nhật | Phép tính | Khoảng cách mới tới P |
|---|---|---|---|
| 0 | Q | min{50 + 0, 1 + 4} | 5, qua R |
| 1 | R | min{21 + 0, 1 + 5} | 6, qua Q |
| 2 | Q | min{50 + 0, 1 + 6} | 7, qua R |
| 3 | R | min{21 + 0, 1 + 7} | 8, qua Q |
| … | … | mỗi bước cộng thêm 1 vào ước lượng của bộ định tuyến kia | … |
| 15 | R | min{21 + 0, 1 + 19} | 20, qua Q |
| 16 | Q | min{50 + 0, 1 + 20} | 21, qua R |
| 17 | R | min{21 + 0, 1 + 21} | 21, trực tiếp |
| 18 | Q | min{50 + 0, 1 + 21} | 22, qua R |
Rắc rối bắt đầu từ bước 0. Ước lượng cũ 4 của R là một đường qua Q, nhưng Q không thể biết điều đó. Vì vậy Q định tuyến qua R trong khi R định tuyến qua Q: một vòng lặp định tuyến, nơi một gói tin cho P nảy qua lại giữa chúng. Mỗi lần trao đổi chỉ tăng các ước lượng thêm 1, và cần 18 lần cập nhật trước khi vòng lặp bị phá (R chuyển sang liên kết trực tiếp của nó ở bước 17) và 19 trước khi mọi ước lượng đều đúng. Sự leo thang chậm này là vấn đề count-to-infinity. Nếu hoàn toàn không có liên kết P–R, các ước lượng sẽ tăng mãi mãi.
Poisoned reverse, và nó ngừng hiệu quả ở đâu#
Cách sửa cho vòng lặp hai bộ định tuyến rất đơn giản. Nếu R tới P qua Q, R báo cho Q: “khoảng cách của tôi tới P là ∞”. Lời nói dối đó ngăn Q định tuyến tới P qua R.
Hãy phát lại tin xấu với poisoned reverse. Trước khi thay đổi, R định tuyến tới P qua Q, nên R đã báo cho Q rằng khoảng cách của nó tới P là ∞.
- Bước 0: Q tính lại: min{50 + 0, 1 + ∞} = 50, trực tiếp. Q báo cho R.
- Bước 1: R tính lại: min{21 + 0, 1 + 50} = 21, trực tiếp. R không còn dùng Q, nên giờ nó nói cho Q sự thật: 21.
- Bước 2: Q tính lại: min{50 + 0, 1 + 21} = 22, qua R. Giờ Q làm độc tuyến ngược của nó về phía R. Xong.
Ba lần cập nhật thay vì 19, và không có vòng lặp.
Trạng thái liên kết so với vectơ khoảng cách#
Bài thi thường hỏi so sánh này.
| Trạng thái liên kết (Dijkstra) | Vectơ khoảng cách (Bellman-Ford) | |
|---|---|---|
| Mỗi bộ định tuyến biết gì | Toàn bộ bản đồ: mọi liên kết và chi phí của nó | Chỉ chi phí các liên kết của chính nó và các vectơ của láng giềng |
| Độ phức tạp thông điệp | Cao: O(nE) thông điệp cho n nút và E liên kết; mọi thay đổi chi phí phải đến được mọi nút | Thấp hơn: các thông điệp chỉ đi giữa các láng giềng, và chỉ khi một vectơ thay đổi |
| Tốc độ hội tụ | Tính toán O(n²) khi đã có bản đồ; có thể dao động với các chi phí dựa trên tải | Thay đổi; các vòng lặp định tuyến có thể hình thành trong lúc ổn định, và tin xấu gây ra count-to-infinity |
| Độ bền vững | Một bộ định tuyến hỏng chỉ có thể nói sai về các liên kết của chính nó, và mỗi bộ định tuyến tự tính bảng của mình | Một bộ định tuyến hỏng có thể quảng bá chi phí sai tới mọi đích, và lỗi lan ra |
| Ví dụ giao thức | OSPF (Open Shortest Path First) | RIP (Routing Information Protocol) |
Trong định tuyến vectơ khoảng cách, mỗi bộ định tuyến áp dụng Dx(y) = minv{c(x, v) + Dv(y)} cho các vectơ của láng giềng và truyền đi mọi thay đổi, nên nó phân tán, lặp và bất đồng bộ; tin tốt lan nhanh, tin xấu có thể đếm đến vô cực qua một vòng lặp định tuyến, và poisoned reverse chỉ sửa các vòng lặp hai bộ định tuyến.
Luyện tập#
Với mỗi lần cập nhật, hãy viết đầy đủ min{ } với một số hạng cho mỗi láng giềng trước khi chọn đáp án.
- Hãy viết phương trình Bellman-Ford và nói bằng lời ý nghĩa của từng phần.
- Bộ định tuyến M có ba láng giềng: c(M, J) = 2, c(M, K) = 7, c(M, L) = 4. Nó vừa nhận các vectơ sau (chi phí tới J, K, L, Z): J gửi (0, 5, 3, 6); K gửi (5, 0, 2, 1); L gửi (3, 2, 0, 3). Tính vectơ khoảng cách của M và chặng kế tiếp cho mỗi đích.
- Trong mạng ba bộ định tuyến (c(P, Q) = 3, c(Q, R) = 1, c(P, R) = 21), chi phí của P–Q giảm từ 3 xuống 2. Khoảng cách mới của Q và R tới P là bao nhiêu, và cần bao nhiêu lần cập nhật?
- Cùng mạng đó, với poisoned reverse được bật và chưa có gì thay đổi. R báo gì cho Q về khoảng cách của nó tới P, và Q báo gì cho R?
- Giả sử c(P, R) là 101 thay vì 21, poisoned reverse tắt, và c(P, Q) tăng từ 3 lên 500. Q và R kết thúc ở đâu, và mất khoảng bao lâu?
- Vì sao poisoned reverse không ngăn được một vòng lặp định tuyến qua ba bộ định tuyến?
- Nêu một ưu điểm của vectơ khoảng cách so với trạng thái liên kết, và một ưu điểm của trạng thái liên kết so với vectơ khoảng cách.
Lời giải#
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.
- dx(y) = minv{c(x, v) + dv(y)}. Chi phí nhỏ nhất từ x tới y được tìm bằng cách thử mọi láng giềng v: cộng chi phí liên kết của x tới v và chi phí nhỏ nhất của v tới y, và giữ tổng nhỏ nhất. Láng giềng v thắng là chặng kế tiếp.
- Tới J: 2 qua J. Tới K: 6 qua L. Tới L: 4 qua L. Tới Z: 7 qua L. K: min{2 + 5, 7 + 0, 4 + 2} = min{7, 7, 6} = 6, nên liên kết trực tiếp (7) thua. L: min{2 + 3, 7 + 2, 4 + 0} = 4. Z: min{2 + 6, 7 + 1, 4 + 3} = 7. J: min{2 + 0, 7 + 5, 4 + 3} = 2.
- Q: 2, trực tiếp. R: 3, qua Q. Hai lần cập nhật. Q: min{2 + 0, 1 + 4} = 2. R: min{21 + 0, 1 + 2} = 3. Sau đó Q tính lại ra 2 một lần nữa và không gửi gì.
- R báo cho Q ∞; Q báo cho R 3. R tới P qua Q, nên nó làm độc tuyến đó về phía Q. Q tới P trực tiếp, không qua R, nên nó báo cho R chi phí thật của mình.
- R kết thúc ở 101 trực tiếp và Q ở 102 qua R, sau 99 lần cập nhật. Các ước lượng tăng 1 mỗi lần cập nhật (5, 6, 7, …) cho đến khi liên kết trực tiếp 101 của R thắng việc đi qua Q.
- Mỗi bộ định tuyến chỉ làm độc chặng kế tiếp của chính nó. Giả sử Q định tuyến qua R, R qua S, và S qua Q. Q làm độc R, R làm độc S, và S làm độc Q. Nhưng mỗi bộ định tuyến vẫn nghe một chi phí hữu hạn, đã lỗi thời, từ chặng kế tiếp của chính nó, bộ định tuyến đứng trước nó trong vòng tròn (Q nghe một chi phí hữu hạn từ R, vì R định tuyến qua S, không phải Q), nên vòng lặp tự nuôi chính nó.
- Vectơ khoảng cách: ít thông điệp hơn, chỉ gửi giữa các láng giềng. Trạng thái liên kết: hội tụ nhanh hơn, bền vững hơn. Mỗi bộ định tuyến tự tính bảng của mình từ toàn bộ bản đồ, nên không có count-to-infinity và một bộ định tuyến hỏng không thể lan chi phí sai khắp nơi.
Danh sách kiểm tra trước khi thi#
- ☐ Tôi viết được phương trình Bellman-Ford và giải thích được từng ký hiệu trong đó.
- ☐ Tôi tính được vectơ khoảng cách mới và các chặng kế tiếp của một bộ định tuyến từ các vectơ của láng giềng.
- ☐ Tôi giải thích được phân tán, lặp và bất đồng bộ có nghĩa gì với thuật toán này.
- ☐ Tôi chỉ ra được vì sao tin tốt lan trong vài lần cập nhật còn tin xấu có thể đếm đến vô cực.
- ☐ Tôi áp dụng được poisoned reverse vào một ví dụ hai bộ định tuyến và nói được vì sao nó thất bại với các vòng lặp dài hơn.
- ☐ Tôi so sánh được trạng thái liên kết và vectơ khoảng cách về thông điệp, hội tụ và độ bền vững.
Trước khi tin ước lượng của một láng giềng trong một câu hỏi count-to-infinity, hãy hỏi: ước lượng đó có đi qua tôi không? Nếu có, đó chính là vòng lặp.
Câu hỏi thường gặp#
Phương trình Bellman-Ford là gì?
Nó nói rằng chi phí nhỏ nhất từ x tới y là giá trị nhỏ nhất, trên mọi láng giềng v của x, của chi phí liên kết từ x tới v cộng với chi phí nhỏ nhất của v tới y. Viết là d_x(y) = min over v of c(x, v) + d_v(y). Láng giềng cho giá trị nhỏ nhất là chặng kế tiếp (next hop).
Vấn đề count-to-infinity là gì?
Khi chi phí một liên kết tăng, các bộ định tuyến có thể tiếp tục tin ước lượng cũ của một láng giềng mà thực ra đi qua chính chúng. Chúng tạo thành một vòng lặp định tuyến và tăng ước lượng của mình từng bước nhỏ, mất nhiều vòng mới ổn định, hoặc không bao giờ ổn định nếu không có đường nào khác.
Poisoned reverse là gì?
Nếu bộ định tuyến x tới một đích qua láng giềng z, x báo cho z rằng khoảng cách của chính nó tới đích đó là vô cực. Điều này ngăn z định tuyến ngược qua x và phá vỡ các vòng lặp hai bộ định tuyến. Nó không ngăn được các vòng lặp có ba bộ định tuyến trở lên.
Định tuyến trạng thái liên kết và vectơ khoảng cách khác nhau thế nào?
Với trạng thái liên kết, mọi bộ định tuyến học toàn bộ bản đồ và tự chạy Dijkstra; nó cần nhiều thông điệp hơn nhưng lỗi chỉ ở phạm vi cục bộ. Với vectơ khoảng cách, các bộ định tuyến chỉ trao đổi ước lượng với láng giềng; nó cần ít thông điệp hơn nhưng có thể lặp vòng và đếm đến vô cực.
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 →