距離向量路由與計數到無窮

解同一道謎題的兩種辦法

在上一篇你看到了連結狀態路由如何運作：每台路由器把自己的本地鏈成本廣播（flood）給所有人，於是每一台最後都握有一份完整的網路圖副本，然後私下跑 Dijkstra 演算法算出最短路徑。這像是一個讀書會，每個人都分享自己的筆記，然後每個學生再各自把整張考卷解完。距離向量路由採取的是完全相反的立場，而它有多激進，值得停下來想一想。

一台距離向量路由器從未看過地圖。它只知道兩件事：連到它緊鄰鄰居的那些鏈的成本，以及那些鄰居告訴它的內容。從這點碎片出發，每台路由器保有一張小表，也就是它的距離向量，每個目的地存一個數字：我對抵達那裡的成本的最佳猜測。它並不知道路徑，只知道成本，以及該把封包交給哪個鄰居。然後，它週期性地把自己整個向量告訴鄰居、也聽鄰居的，整場對話就只有這樣。謎題跟之前一樣——在網路上找出最低成本路徑——但這裡沒有任何人握有答案；答案是從閒話裡浮現出來的。

Bellman-Ford 的點子：去問你的鄰居

底下的引擎是 Bellman-Ford 方程式，而把它直白講出來，幾乎是顯而易見的。假設我想知道抵達某個遙遠目的地 D 的最低成本。我看不到整條路線，但我可以在本地推理：對任何一個鄰居 N，有一條候選路線就是「我連到 N 的鏈成本，加上 N 自己宣稱的抵達 D 的最低成本」。我抵達 D 的最佳成本，就只是把這種候選在我所有鄰居上取最小值。用話講：抵達 D 最便宜的方式，就是先走一步到我最好的那個鄰居，再走他們抵達 D 最便宜的方式。

Bellman-Ford, the neighbour's-eye view

  cost_x(D) = min over each neighbour N of [ c(x, N) + cost_N(D) ]

  c(x, N)      = cost of my own link to neighbour N  (I know this)
  cost_N(D)    = N's advertised cheapest cost to D   (N told me this)

Example, router X reaching D, with two neighbours A and B:
  link X->A costs 1,  A advertises cost 4 to D   =>  candidate 1 + 4 = 5
  link X->B costs 2,  B advertises cost 2 to D   =>  candidate 2 + 2 = 4
  cost_x(D) = min(5, 4) = 4,  next hop = B

整個演算法就一行：拿每個鄰居宣稱的抵達 D 的成本，加上抵達那個鄰居的成本，留下最小的。勝出的鄰居就成為下一跳。

現在把這套當成一個活生生、在整張網路上跑的過程。每台路由器一開始只知道自己的直連鏈，其他一切都是無窮大。它對鄰居最新的向量套用 Bellman-Ford，而只要自己的向量變了，就把新的向量廣告給鄰居。鄰居重算、也許跟著變、再廣告出去，更新就像消息在一座小鎮裡傳開那樣一圈圈往外漣漪。在沒出任何差錯的情況下，這會安定下來——每台路由器的向量都不再變動——而它已經收斂到真正的最低成本路徑，過程中卻沒有任何一台路由器看過地圖。那種安靜的、分散式的收斂，是真的很美。

好消息傳得快，壞消息傳得慢

這就是優雅破功的地方。距離向量有一個出了名的不對稱：好消息（某條鏈變便宜了，或冒出一條新捷徑）傳得很快，但壞消息（某條鏈或某個目的地消失了）可能傳得慢得叫人難受，而在最糟的情況下，它會引爆計數到無窮問題。根本原因在於：一台路由器相信鄰居，卻不知道鄰居為什麼會相信他們所相信的東西。鄰居說到 D 的成本是 4，你就信了，從沒懷疑過那個鄰居通往 D 的路線其實可能繞回經過你。

想像三台路由器排成一列：A 透過 B 抵達目的地 D，C 也透過 B 抵達 D。所以 A 認為「D 成本 2，走 B」，C 也認為「D 成本 2，走 B」。現在 B 直通 D 的那條鏈斷了。B 察覺 D 沒了，把它的成本設為無窮大。但在 B 還來不及告訴任何人之前，A 先插嘴丟出它的舊廣告：「我可以用成本 2 抵達 D！」B 相信了 A（它根本不知道 A 的路線一開始就是繞經 B 的），開心地推論「那我就透過 A 抵達 D，成本 3。」B 廣告 3，C 更新成 4，A 接著看到 B 現在是 3、就把自己抬高到 4，於是兩台就這樣一來一回地往上彈——5、6、7——慢慢地朝無窮大數過去，全都在追一個已經不存在的目的地。這就是慢動作播放的路由迴圈。

部分解藥：在源頭給謊言下毒

如果這個病是「一台路由器把某條路線廣告回它所依賴的那個鄰居」，那麼顯而易見的藥方就是別這麼做。這就是水平分割：如果我透過鄰居 B 抵達 D，我就完全不告訴 B 我能抵達 D。我絕不把一條路線往我當初學到它的方向廣告回去。在那個三路由器的故事裡，A 就只會對 B 在 D 這件事上保持沉默，於是 B 永遠不會聽到那個誘人的假「成本 2」，也就永遠不會開始往上爬。

稍微強一點的變體是帶毒性反轉的水平分割（poison reverse）：A 不只是保持沉默，而是主動告訴 B「我到 D 的成本是無窮大」，給這條路線下毒，讓 B 根本不可能被誘惑。這兩招都有幫助，真實的協定也都會用。但這裡有個誠實而重要的提醒：它們是部分解藥，不是保證。水平分割能可靠地殺掉兩台路由器的迴圈，但一個牽涉到三台以上路由器繞成一圈的迴圈，仍然可能計數到無窮，因為那個謊言會繞著迴圈走遠路、而不是直接折回來。距離向量在壞消息上的慢收斂，是一個真實的、殘留的弱點，不是一個你能完全補起來的 bug。

路由器開機時只知道連到每個直接相連鄰居的成本；其他每個目的地都從無窮大開始。
它週期性地把自己整個距離向量送給每個鄰居（並且在自己的向量一變動時也立刻送出）。
收到某鄰居的向量時，它套用 Bellman-Ford：對每個目的地，拿該鄰居廣告的成本加上連到它的鏈成本，並留下最小值。
在廣告出去之前，它套用水平分割（並可選地加上毒性反轉），好讓它絕不把一條路線往它所依賴的鄰居那邊餵回去。
如果它的向量變了，就再廣告一次；這個漣漪持續下去，直到每個向量都不再變動——網路就收斂了。

哪一個贏？都不贏，而這正是重點

我們很容易宣布連結狀態獲勝，因為距離向量有計數到無窮的毛病。忍住別這麼做。每種設計付的代價不同。連結狀態要求每台路由器把更新廣播（flood）給整個區域、並儲存完整的地圖，這耗費的記憶體與廣播流量會隨網路規模成長；它的好處是快速、無迴圈的收斂。距離向量則省得令人讚嘆——一台路由器永遠只跟鄰居講話、每個目的地只存一個數字——但它付出的代價是失效時的慢收斂，以及計數到無窮的風險。

這些不只是教科書上的好奇之物；它們直接對應到你接下來要認識的兩個真實內部閘道協定。RIP 是距離向量、簡單而受限，以那個跳數 16 當作無窮大。OSPF 是連結狀態、較重但可擴展，是大型網路內部真正在跑的東西。甚至還有第三個家族建立在距離向量的點子之上，叫做路徑向量，它廣告的是整條路徑、而不只是一個成本，於是一台路由器能看出並拒絕任何繞回經過自己的路線——這正是那個把整個網際網路綁在一起的協定避開計數到無窮的辦法——但那屬於後面講跨網域路由的一段。

退一步看，這一段的形狀就清楚了。兩個演算法攻的是同一道圖論問題，都算出最低成本路徑，也都餵養同一張卑微的轉送表——那張資料平面逐封包查閱的表。它們只是對「誰知道什麼」意見不合。連結狀態說：知道一切、各自算；距離向量說：知道你的鄰居、一起算。下一篇就拿這兩個點子，給你看它們穿上真實協定外衣的樣子——RIP 與 OSPF——今天就在真正的網路裡跑著。