? ? ? ? 在本章中，包含網絡層的控制平面組件。控制平面作為一種網絡范圍的邏輯，不僅控制沿著從源主機到目的主機的端到端路徑間的路由器如何轉發數據報，而且控制網絡層組件和服務如何配置和管理。5.2節，傳統的計算圖中最低開銷路徑的路由選擇算法。5.3和5.4節，因特網路由選擇協議 OSPF 和 BGP 的基礎。OSPF 是一種運行在單一 ISP 的網絡中的路由選擇算法，BGP 是一種在因特網中用于互聯所有網絡的路由選擇算法，常被稱為因特網的“ 粘合劑 ”。
? ? ? ? 5.5 節，SDN 控制器，軟件定義網絡（SDN）在數據平面和控制平面之間做了明確分割，在一臺分離的“ 控制器 ”服務中實現了控制z平面功能，該控制器服務于他所控制的路由器的轉發組件完全分開并遠離。 5.6 和 5.7節，涉及管理 IP 網絡的某些具體細節：ICMP（互聯網控制報文協議）和 SNMP（簡單網絡管理協議）。
5.1 概述
????????通過回顧圖 4-2 和圖 4-3 ，迅速建立起學習網絡控制平面的環境。在這里，轉發表（在基于目的地轉發的場景中）和流表（在通用轉發的場景中）是鏈接網絡層的數據平面和控制平面的首要元素。我們知道這些表定義了一臺路由器的本地數據平面轉發行為。看到在通用轉發的場景下，所采取的動作（4.4.2 節）不僅包括轉發一個分組到達路由器的每個輸出端口，而且能夠丟棄一個分組 、復制一個分組和/或重寫第 2 ,3 或 4 層分組首部字段。
? ? ? ? ?本章中，學習這些轉發表和流表是如何計算、維護和安裝的。在 4.1 節的網絡層概述中，學習路完成這些工作有兩種可能的方法。
? ? ? ? ?①?每路由器控制 。圖 5-1 顯示了在每臺路由器中運行一種路由選擇算法的情況，每臺路由器中都包含轉發和路由選擇功能。每臺路由器有一個路由選擇組件，用于與其他路由器中的路由選擇組件通信，以計算其轉發表的值。這種每路由器控制的方法在因特網中已經使用了幾十年。將在 5.3 節和 5.4 節中學習的 OSPF 和 BGP 協議都是基于這種每路由器的方法進行控制的。
? ? ? ? ② 邏輯集中式控制。圖 5-2 顯示了邏輯集中式控制器計算并分發轉發表以供每臺路由器使用的情況。如在 4.4 節中所見，通用的" 匹配加動作 "抽象允許執行傳統的 IP 轉發以及其他功能（負載共享、防火墻功能和 NAT）的豐富集合，而這些功能先前是在單獨的中間盒中實現的。?
? ? ? ? 該控制器經一種定義良好的協議與每臺路由器中的一個控制代理（CA）進行交互，以配置和管理該路由器的轉發表。CA 一般具有最少的功能，其任務是與控制器通信并且按控制器命令行事。與圖 5-1 中的路由選擇算法不同，這些 CA 既不能直接相互交互，也不能主動參與計算轉發表。這是每路由器控制和邏輯集中式控制之間的關鍵差異。
?
? ? ? ? ?邏輯集中式控制意味著就像路由選擇控制服務位于單一的集中服務點那樣獲取它們，即使該服務處于容錯和性能擴展的原因，可能經由多個服務器實現。正如 5.5 節所見，SDN 采用了邏輯集中式控制器的概念，而這種方法在生產部署中得到越來越多的應用。
?5.2 路由選擇算法
????????路由選擇算法 (routing algorithm) ，其目的是從發送方到接收方的過程中確定一條通過路由器網絡的好的路徑（等價于路由）。通常， 一條好路徑指具有最低開銷的路徑。然而我們將看到，實踐中現實世界還關心諸如策略之類的問題（例如，有一個規則是" 屬于組織Y 的路由器X 不應轉發任何來源于組織 Z 所屬網絡的分組")。我們注意到無論網絡控制平面采用每路由器控制方法，還是采用邏輯集中式控制方法，必定總是存在一條定義良好的一連串路由器，使得分組從發送主機到接收主機跨越網絡"旅行" 。
?????????可以用圖來形式化描述路由選擇問題。圖( graph ) G = (N, E) 是一個 N 個節點和 E 條邊的集合，其中每條邊是取自 N的 一對節點。在網絡層路由選擇的環境中，圖中的節點表示路由器，這是做出分組轉發決定的點；連接這些節點的邊表示這些路由器之間的物理鏈路。這樣一個計算機網絡的圖抽象顯示在圖 5-3。
?
?????????如圖 5-3 所示，一條邊還有一個值表示它的開銷。通常，一條邊的開銷可反映出對應鏈路的物理長度（例如一條越洋鏈路的開銷可能比一條短途陸地鏈路的開銷高） ，它的鏈路速度，或與該鏈路相關的金錢上的開銷。為了我們的目的，只將這些鏈路開銷看成是給定的，而不必操心這些值是如何確定的。對于 E 中的任一條邊（x，y），用 c(x，y) 表示節點 x 和 節點 y 間邊的開銷。如果節點對（x，y）不屬于 E，則置 c(x，y)=∞。此外，這里考慮的都是無向圖（圖的邊沒有方向），因此邊（x，y）與邊（y，x）是相同的并且 c(x，y) = c(y，x)。然而，學習的算法能夠很容易擴展到在每個方向有不同開銷的有向鏈路組合。同時，如果（x，y）屬于 E，節點 y 也被稱為節點 x 的鄰居。
?????????在圖抽象中為各條邊指派了開銷后，路由選擇算法的天然目標是找出從源到目的地間的最低開銷路徑。為了使問題更為精確，回想在圖 G= (N, E) 中的一條路徑 (path)是一個節點序列(x1，x2，…，xp) ，這樣每一個對 (x1 ，x2 ), (x2，x3) ,…, (xp-1,xp）是 E中的邊。路徑（x1,x2 …,xp）的開銷只是沿著路徑所有邊的開銷的總和，即c(x1，x2) + c( x2，x3) +… +C(xp-1,xp）。給定任何兩個節點 x 和 y ，通常在這兩個節點之間有許多條路徑，每條路徑都有一個開銷。這些路徑中的一條或多條是最低開銷路徑。最低開銷路徑問題是清楚的：找出源和目的地之間具有最低開銷的一條路。例如，在圖5-3中，源節點 u 和目的節點 w 之間的最低開銷路徑是（u,x,y,w），具有的路徑開銷是3。注意到若在圖中的所有邊具有相同的開銷，則最低開銷路徑也就是最短路徑，即在源和目的地之間的具有最少鏈路數量的路徑。
?????????路由選擇算法的一種分類方式是根據該算法是集中式還是分散式來劃分。
? ? ? ? ① 集中式路由選擇算法用完整的、全局性的網絡知識計算出從源到目的地之間的最低開銷路徑。也就是說，該算法以所有節點之間的連通性及所有鏈路的開銷為輸入。這就要求該算法在真正開始計算以前，要以某種方式獲得這些信息。計算本身可在某個場點（例如，圖 5-2 中所示的邏輯集中式控制器）進行，或在每臺路由器的路由選擇組件中重復進行(例如在圖 5- 1?中) 然而，這里的主要區別在于，集中式算法具有關于連通性和鏈路開銷方面的完整信息。具有全局狀態信息的算法常被稱作鏈路狀態 (Link State , LS) 算法，因為該算法必須知道網絡中每條鏈路的開銷。我們將在 5.2.1 節中學習 LS 算法。
? ? ? ? ② 在分散式路由選擇算法 (deeentralized routing algorithm) 中，路由器以迭代、分布式的方式計算出最低開銷路徑。沒有節點擁有關于所有網絡鏈路開銷的完整信息。相反，每個節點僅有與其直接相連鏈路的開銷知識即可開始工作。然后，通過迭代計算過程以及與相鄰節點的信息交換，一個節點逐漸計算出到達某目的節點或一組目的節點的最低開銷路徑。我們將在后面的 5.2.2 節學習一個稱為距離向量( Distance-Vector, DV) 算法的分散式路由選擇算法。之所以叫作 DV 算法，是因為每個節點維護到網絡中所有其他節點的開銷(距離)估計的向量。 這種分散式算法，通過相鄰路由器之間的交互式報文交換，也許更為天然地適合那些路由器直接交互的控制平面，就像在圖 5-1 中那樣。
? ? ? ? ?路由選擇算法的第二種廣義分類方式是根據算法是靜態的還是動態的進行分類。在靜態路由選擇算法（static routing algorithm) 中，路由隨時間的變化非常緩慢，通常是人工進行調整（如人為手工編輯一條鏈路開銷）。動態路由選擇算法 (dynamic routi algorithm)隨著網絡流量負載或拓撲發生變化而改變路由選擇路徑。一個動態算法可周期性地運行或直接響應拓撲或鏈路開銷的變化而運行。雖然動態算法易于對網絡的變化做出反應，但也更容易受諸如路由選擇循環、路由振蕩之類問題的影響。
?????????路由選擇算法的第三種分類方式是根據它是負載敏感的還是負載遲鈍的進行劃分。在負載敏感算法（load -sensitive algorithm) 中，鏈路開銷會動態地變化以反映出底層鏈路的當前擁塞水平。如果當前擁塞的一條鏈路與高開銷相聯系，則路由選擇算法趨向于繞開該擁塞鏈路來選擇路由。當今的因特網路由選擇算法(如 RIPOSPF BGP) 都是負載遲鈍的( 10ad -insensitive) ，因為某條鏈路的開銷不明確地反映其當前(或最近)的擁塞水平。
5.2.1 鏈路狀態路由選擇算法
????????前面講過， 在鏈路狀態算法中，網絡拓撲和所有的鏈路開銷都是已知的，也就是說可用作 LS 算法的輸入。實踐中這是通過讓每個節點向網絡中所有其他節點廣播鏈路狀態分組來完成的，其中每個鏈路狀態分組包含它所連接的鏈路的標識和開銷。在實踐中（例如使用因特網的 OSPF 路由選擇協議，討論見 5.3 節) ，這經常由鏈路狀態廣播（link state broadcast）算法來完成。節點廣播的結果是所有節點都具有該網絡的統一、完整的視圖。于是每個節點都能夠像其他節點一樣，運行 LS 算法并計算出相同的最低開銷路徑集合。
? ? ? ? 下面給出的鏈路狀態路由選擇算法叫做 Dijkstra 算法。一個密切相關的算法是 prim 算法。Dijkstra 算法計算從某節點（源節點 稱之為 u）到網絡中所有其他節點的最低開銷路徑。Dijkstra 是迭代算法，其性質是經算法的第 k 次迭代后，可知道到 k 個目的節點的最低開銷路徑，在到所有目的節點的最低開銷路徑中，著 k 條路徑具有 k 個最低開銷。定義下列符號。
????????舉一個例子，考慮圖 5-3 中的網絡，計算從 u 到所有可能目的地的最低開銷路徑算法的計算過程以表格方式總結于表5-1 中，表中的每一行給出了迭代結束時該算法的變量的值。詳細地考慮前幾個步驟。?
? ? ? ? ①?在初始化步驟，從 u 到與其直接相連的鄰居v 、x、w 的當前已知最低開銷路徑分別初始化為 2,1,5。特別值得注意的是，到 w 的開銷被設為 5（盡管我們很快就會看見確實存在一條開銷更小的路徑），因為這是從 u 到 w 的直接（一跳）鏈路開銷。到 y 與 z的開銷被設為無窮大，因為它們不直接與 u 連接。
? ? ? ? ② 在第一次迭代中，觀察那些還未加到集合 N' 中的節點，并且找出在前一次迭代結束時具有最低開銷的節點。那個節點便是 x ，其開銷是 1，因此 x 被加到集合 N'。于是 LS 算法中的第 12 行中的程序被執行，以更新所有節點 v 的 D(v)，產生表 5-1 中第 2 行( 步驟 )所示的結果。到 v 的路徑開銷未變。經過節點 x 到 w（在初始化結束時其開銷為 5）的路徑開銷被發現為 4。因此這條具有更低開銷的路徑被選中，且沿從 u 開始的最短路徑上 w' 的前一節點被設為 x。類似地，到 y (經過 x）的開銷被計算為 2，且該表也被相應地更新。
? ? ? ? ③??在第二次迭代時，節點 v 與 y 被發現具有最低開銷路徑 (2) ，并且我們任意改變次序將 y 加到集合 N' 中，使得 N' 中含有 u,x 和 y。到仍不在 N' 中的其余節點（即節點 v w 和 z）的開銷通過 LS 算法中的第 12 行進行更新，產生如表 5-1 中第 3 行所示的結果。
? ? ? ? ④ 如此等等。
????????當 LS 算法終止時，對于每個節點，我們都得到從源節點沿著它的最低開銷路徑的前一節點。對于每個前一節點，我們又有它的前一節點，以此方式我們可以構建從源節點到所有目的節點的完整路徑。通過對每個目的節點存放從 u 到目的地的最低開銷路徑上的下一跳節點，在一個節點（如節點 u）中的轉發表能夠根據此信息而構建。圖 5-4 顯示了對于圖 5-3 中的網絡產生的最低開銷路徑和 u 中的轉發表。
?
? ? ? ? 該算法的計算復雜性是什么？即給定 n 個節點（不算源節點），在最壞情況下要經過多少次計算，才能找到從源節點到所有目的節點的最低開銷路徑？在第一次迭代中，我們需要搜索所有的 n 個節點以確定出不在 N' 中且具有最低開銷的節點 w。 在第二次迭代時，我們需要檢查 n-1 個節點以確定最低開銷。第三次對 n-2 個節點迭代，依次類推。總之，我們在所有迭代中需要搜尋的節點總數為 n(n+1 )/2 ，因此我們說前面實現的鏈路狀態，算法在最差情況下復雜性 O(n^2)。(該算法的一種更復雜的實現是使用一種稱為堆的數據結構，能用對數時間而不是線性時間得到第 9 行的最小值，因而減少其復雜性）。
????????在完成 LS 算法的討論之前，考慮一下可能出現的問題。圖 5-5 顯示了一個簡單的網絡拓撲，圖中的鏈路開銷等于鏈路上承載的負載，例如反映要歷經的時延。在該例中，鏈路開銷是非對稱的，即僅當在鏈路 (u，v) 兩個方向所承載的負載相同時 c(u，v) 和?c(v，u) 才相等。在該例中，節點 z 產生發往 w 的一個單元的流量，節點 x 也產生發往w 的一個單元的流量，并且節點 y 也產生發往 w 的一個數量為 e 的流量。初始路由選擇情況如圖 5-5a 所示，其鏈路開銷對應于承載的流量。
? ? ? ? 當 LS 算法再次運行時，節點 y 確定（基于圖 5-5a 所示的鏈路開銷）順時針到 w 的路徑開銷為 1，而逆時針到 w 的路徑開銷（一直使用的）是 1+e。因此，y 到 w 的最低開銷路徑現在是順時針的。類似的，x 確定其到 w 的新的最低開銷路徑也是順時針的，產生如圖 5-5b 中所示的開銷。當 LS 算法下次運行時，節點 x、y 和 z 都檢測到一條至 w 的逆時針方向零開銷路徑，他們都將其流量引導到逆時針方向的路由上。下次 LS 算法運行時，x、y和 z 都將其流量引導到順時針方向的路由上。
????????如何才能防止這樣的振蕩（它不只是出現在鏈路狀態算法中，而且也可能出現在任何使用擁塞或基于時延的鏈路測度的算法中）。一種解決方案可能強制鏈路開銷不依賴于所承載的流量，但那是一種不可接受的解決方案，因為路由選擇的目標之一就是要避開高度擁塞（如高時延）的鏈路。另一種解決方案就是確保并非所有的路由器都同時運行 LS 算法。這似乎是一個更合理的方案，因為我們希望即使路由器以相同周期運行 LS 算法，在每個節點上算法執行的時機也將是不同的。有趣的是，研究人員近來已注意到了因特網上的路由器能在它們之間進行自同步。 這就是說，即使它們初始時以同一周期但在不同時刻執行算法，算法執行時機最終會在路由器上變為同步并保持之 。避免這種自同步的一種方法是，讓每臺路由器發送鏈路通告的時間隨機化。?
5.2.2 距離向量路由選擇算法
?????????距離向量（Distance-Vector DV）算法是一種迭代的、異步的和分布式的算法，而 LS 算法是一種使用全局信息的算法。說它是分布式的，是因為每個節點都要從一個或者多個直接相連鄰居接收某些信息，執行計算，然后將其計算結果分發給鄰居。說他是迭代的，是因為此過程一直要持續到鄰居之間無更多信息要交換為止。(有趣的是，此算法是自我終止的，即沒有計算應該停止的信號，它就停止了）。說它是異步的，是因為它不要求所有節點相互之間步伐一致地操作。我們將看到一個異步的、迭代的、自我終止的、分布式的算法。
? ? ? ? ?給出 DV 算法之前，討論存在于最低開銷路徑的開銷之間的一種重要關系。令 dx(y)是從節點 x 到 y 的最低開銷路徑的開銷。則該最低開銷于 Bellman-Ford 方程相關，即
?????????檢查在圖5-3 中的源節點 u 和目的節點 z。源節點有 3 個鄰居：v、x 和 w。通過遍歷該圖中的各條路徑，容易看出 dv(z)=5 dx(z)=3 dw(z)=3。連通開銷 c(u，v)=2、c(u，x)=1 c(u，w)=5 帶入方程。得出 du(z)=min{2+5，5+3，1+3}=4。顯然是正確的。
?????????在該 DV 算法中，當節點 x 發現它的直接相連的鏈路開銷變化或從某個鄰居接收到一個距離向量的更新時，它就更新其距離向量估計值。但是為了一個給定的目的地 y 而更新它的轉發表，節點 x 真正需要知道的不是到 y 的最短路徑距離，而是沿著最短路徑到下一跳路由器鄰居節點 v*(y) 。如你可能期望的那樣，下一跳路由器 v*(y) 是在 DV 算法第14 行中取得最小值的鄰居 v 。(如果有多個取得最小值的鄰居 v*(y) 能夠是其中任何一個有最小值的鄰居。)因此，對于每個目的地 y，在第 13 -14 行中，節點 x 也決定v*(y) 并更新它對目的地 y 的轉發表。
?????????前面講過 LS 算法是一種全局算法，在于它要求每個節點在運行 Dìjkstra 算法之前，首先獲得該網絡的完整信息。DV 算法是分布式的，它不使用這樣的全局信息。實際上，節點具有的唯一信息是它到直接相連鄰居的鏈路開銷和它從這些鄰居接收到的信息。每個節點等待來自任何鄰居的更新(第 10 -11 行) ，當接收到一個更新時計算它的新距離向量(第 14 行)并向它的鄰居分布其新距離向量(第 16 -17 行)。在實踐中許多類似 DV 的算法被用于多種路由選擇協議中，包括因特網的 RIP 和 BGP、ISO IDRP等。
? ? ? ? 圖 5-6?舉例說明了 DV 算法的運行，應用場合是該圖頂部有三個節點的簡單網絡。算法的運行以同步的方式顯示出來，其中所有節點同時從其鄰居接收報文，計算其新距離向量，如果距離向量發生了變化則通知其鄰居。學習完這個例子后，你應當確信該算法以異步方式也能正確運行，異步方式中可在任意時刻出現節點計算與更新的產生/接收。?
????????該圖最左邊一列顯示了這 3 個節點各自的初始路由選擇表( routlng table)。例如，位于左上角的表是節點 x 的初始路由選擇表。在一張特定的路由選擇表中，每行是一個距離向量一一特別是每個節點的路由選擇表包括了它的距離向量和它的每個鄰居的距離向量。因此，在節點 x 的初始路由選擇表中的第一行 Dx=[Dx(x)，Dx(y)，Dx(z)]=[0,2,7]。在該表的第二和第三行是分別從節點 y 和 z 收到的距離向量。因為在初始化時節點 x 還沒有從節點 y 和z 收到任何東西，所以第二行和第三行的表項被初始化為無窮大。
? ? ? ? 初始化后，每個節點向它的兩個鄰居發送其距離向量。圖 5-6 中用從表的第一列到表的第二列的箭頭說明了情況。例如，節點 x 向兩個節點 y 和 z 發送了它的距離向量 Dx=[0，2，7]。在接收到更新后，每個節點重新計算它自己的距離向量。例如，節點 x 計算?
????????第二列因此為每個節點顯示了節點的新距離向量連同剛從它的鄰居接收到的距離向量。注意到，例如節點 x 到節點 z 的最低開銷估計 Dx(z) 已經從 7 變成 3 了。還應注意到，對于節點 x，節點 y 在該 DV 算法的第 14 行中取得了最小值；因此在該算法的這個階段，在節點 x 得到了 v*(y)=y 和 v*(z)=y。
????????在節點重新計算它們的距離向量之后，它們再次向其鄰居發送它們的更新距離向量（如果它們已經改變的話）。圖 5-6 中由從表第二列到表第三列的箭頭說明了這一情況。注意到僅有節點 x 和節點 z 發送了更新：節點 y 的距離向量沒有發生變化，因此節點 y 沒有發送更新。在接收到這些更新后，這些節點則重新計算它們的距離向量并更新它們的路由選擇表，這些顯示在第三列中。
?????????從鄰居接收更新距離向量、重新計算路由選擇表項和通知鄰居到目的地的最低開銷路徑的開銷已經變化的過程繼續下去，直到無更新報文發送為止。在這個時候，因為無更新報文發送，將不會出現進一步的路由選擇表計算，該算法將進入靜止狀態，即所有的節點將執行 DV 算法的第 10 -11 行中的等待。該算法停留在靜止狀態，直到一條鏈路開銷發生改變，如下面所討論的那樣。
1. 距離向量算法：鏈路開銷改變與鏈路故障
?????????當一個運行 DV 算法的節點檢測到從它自己到鄰居的鏈路開銷發生變化時(第 10 --11 行) ，它就更新其距離向量（第13-14 行) ，并且如果最低開銷路徑的開銷發生了變化，向鄰居通知其新的距離向量（第16-17行）。圖 5-7a 圖示了從 y 到 x 的鏈路開銷從 4 變為 1 的情況。我們在此只關注 y 與 z 到目的地 x 的距離表中的有關表項。該 DV 算法導致下列事件序列的出現：
?? ?① 在 t0 時刻，y 檢測到鏈路開銷變化(開銷從 4 變為 1) ，更新其距離向量，并通知其鄰居這個變化，因為最低開銷路徑的開銷已改變。
?? ?② 在 t1 時刻，收到來自 y 的更新報文并更新了其距離表。它計算出到 x 的新最低開銷（從開銷 5 減為開銷 2），它向其鄰居發送了它的新距離向量。
?? ?③ 在 t2時刻，y 收到來自 z 的更新并更新其距離表。y 的最低開銷未變，因此 y 不發送任何報文給 z。該算法進入靜止狀態。
? ? ? ? 因此，對于該 DV 算法只需要兩次迭代就到達了靜止狀態。在 x 與 y 之間開銷減少的好消息通過網絡得到了迅速傳播。
? ? ? ? 現在考慮一下某鏈路開銷增加的情況。假設 x 與 y 之間的鏈路開銷從 4 增加到 60，如圖 5-7b
????????該過程將要繼續多久呢？你應認識到該循環將持續 44 次迭代(在 y 與 z 之間交換報文) ，即直到 z 最終算出它經由 y 的路徑開銷大于 50 為止。此時 z 將(最終)確定它到的最低開銷路徑是經過它到 x 的直接連接。y 將經由 z 路由選擇到 x 。關于鏈路開銷增加的壞消息的確傳播得很慢！如果鏈路開銷 c(y,x) 從 4 變為 10000 且開銷 c(z x) 為 9999時將發生什么樣的現象呢？由于這種情況，我們所見的問題有時被稱為無窮計數( count-to-infinity)問題。
2. 距離向量算法：增加毒性逆轉
????????剛才描述的特定循環的場景可以通過使用一種稱為毒性逆轉 (poisoned reverse) 的技術而加以避免。其思想較為簡單：如果 z 通過 y 路由選擇到目的地 x，則 z 將通告 y，它(即 z) 到 x 的距離是無窮大，也就是 z 將向 y 通告 Dz(x)=∞（即使 z 實際上知道Dz (x) =?5）。只要 z 經 y 路由選擇到 x，z 就持續地向 y 講述這個善意的小謊言。因為 y 相信 z 沒有到 x 的路徑，故只要 z 繼續經 y 路由選擇到 x（并這樣去撒謊），y 將永遠不會試圖經由 z 路由選擇到 x。
?? ?現在看一下毒性逆轉如何解決我們前面在圖 5-7b 中遇到的特定環路問題。作為毒性逆轉的結果，y 的距離表指示了 Dz(x)=∞。當(x，y) 鏈路的開銷在 t0 時刻從 4 變為60 更新其表，雖然開銷高達 60 ，仍繼續直接路由選擇到 x，并將到 x 的新開銷通知z，即 Dy(x) =60。z在 t1 時刻收到更新后，便立即將其到 x 的路由切換到經過開銷為 50的直接 (z x) 鏈路 肉為這是一條新的到壞的最低開銷路徑，且因為路徑不再經過 y，z?就在 t2 時刻通知 y 現在 Dz(x) = 50。在收到來自 z 的更新后，y 便用 Dy(x) =51 更新其距離表.另外，因為 z 此時位于 y到 x 的最低開銷路徑上，所以 y 通過在 t3 時刻通知 z 其 Dy(x)=∞(即使 y 實際上知道 Dy(x) = 51）毒化從 z 到 x 壞的逆向路徑。
?????????毒性逆轉解決了一般的無窮計數問題嗎？沒有。你應認識到涉及 3 個或更多節點（而不只是兩個直接相連的鄰居節點）的環路將無法用毒性逆轉技術檢測到。
3. LS 與 DV 路由選擇算法的比較
?????????DV 和 LS 算法采用互補的方法來解決路由選擇計算問題。在 DV 算法中，每個節點僅與它的直接相連的鄰居交談，但它為其鄰居提供了從它自己到網絡中（它所知道的）所有其他節點的最低開銷估計。LS 算法需要全局信息。因此，當在每臺路由器中實現時，例如像在圖 4-2 和圖 5-1 中那樣，每個節點（經廣播）與所有其他節點通信，但僅告訴它們與它直接相連鏈路的開銷。通過快速比較它們各自的屬性來總結所學的鏈路狀態與距離向量算法。記住 N 是節點(路由器)的集合，而 E 是邊(鏈路)的集合。
? ? ? ? ?① 報文復雜性。LS 算法要求每個節點都知道網絡中每條鏈路的開銷。這就要求要發送 O（|N||E|）個報文。而且無論何時一條鏈路的開銷改變時，必須向所有節點發送新的鏈路開銷。DV 算法要求在每次迭代時，在兩個直接相連鄰居之間交換報文。我們已經看到，算法收斂所需時間依賴于許多因素。當鏈路開銷改變時， DV 算法僅當在新的鏈路開銷導致與該鏈路相連節點的最低開銷路徑發生改變時，才傳播已改變的鏈路開銷。
? ? ? ? ② 收斂速度。LS 算法的實現是一個要求?O(|N||E|)個報文的 O(|N|^2)算法。DV 算法收斂較慢，且在收斂時會遇到路由選擇環路。DV 算法還會遭遇無窮計數問題。
? ? ? ? ③??健壯性。如果一臺路由器發生故障、行為錯亂或收到蓄意破壞時情況會怎樣呢？對于 LS 算法，路由器能夠向其連接的鏈路（而不是其他鏈路）廣播不正確的開銷。作為 LS 廣播的一部分，一個節點也可損壞或丟棄它收到的任何 LS 廣播分組。但是一個 LS 節點僅計算自己的轉發表；其他節點也自行執行類似的計算。這就意味著LS 算法下，路由計算在某種程度上是分離的，提供了一定程度的健壯性。DV算法下，一個節點可向任意或所有目的節點通告其不正確的最低開銷路徑。（在1997 年， 一個小 ISP 的一臺有故障的路由器的確向美國的主干路由器提供了錯誤的路由選擇信息。這引起了其他路由器將大量流量引向該故障路由器，并導致因特網的大部分中斷連接達數小時）一般地，我們會注意到每次迭代時，在 DV 算法中一個節點的計算會傳遞給它的鄰居，然后在下次迭代時再間接地傳遞給鄰居的鄰居。在此情況下， DV 算法中一個不正確的節點計算值會擴散到整個網絡。
? ? ? ? 總之，兩個算法沒有一個是明顯的贏家，它們的確都在因特網中得到了應用。?
5.3 因特網中自治系統內部的路由選擇：OSPF
? ? ? ? 在目前為止的算法研究中，將網絡只看作一個互聯路由器的集合。從所有路由器執行相同的路由選擇算法以計算穿越整個網絡的路由選擇路徑的意義上說，一臺路由器很難同另一臺路由器區別開來。?在實踐中，該模型和這種一組執行同樣路徑選擇算法的同質路由器集合的觀點有一點簡單化。以下兩個重要原因：
? ? ? ? ① 規模。隨著路由器數目變得很大，涉及路由選擇信息的通信、計算和存儲的開銷將高得不可實現。當今的因特網由數億臺主機組成。在這些主機中存儲的路由選擇信息顯然需要巨大容量的內存。在所有路由器之間廣播連通性和鏈路開銷更新所要求的負擔將是巨大的！在如此大量的路由器中迭代的距離向量算法將肯定永遠無法收斂！顯然，必須采取一些措施以減少像因特網這種大型網絡中的路由計算的復雜性。
? ? ? ? ?② 管理自治。如在1.3 節描述的那樣，因特網是 ISP 的網絡，其中每個 ISP 都有它自己的路由器網絡。 ISP 通常希望按自己的意愿運行路由器（如在自己的網絡中運行它所選擇的某種路由選擇算法），或對外部隱藏其網絡的內部組織面貌。在理想情況下，一個組織應當能夠按自己的愿望運行和管理其網絡，還要能將其網絡與其他外部網絡連接起來。
?????????這兩個問題都可以通過將路由器組織進自治系統 (Autonomous System, AS) 來解決，其中每個 AS 由一組通常處在相同管理控制下的路由器組成，通常在一個 ISP 中的路由器以及互聯它們的鏈路構成一個 AS。然而，某些 ISP 將它們的網絡劃分為多個 AS 。特別是，某些一級 ISP 在其整個網絡中使用一個龐大的 AS，而其他 ISP 則將它們的 ISP 拆分為數十個互聯的 AS。一個自治系統由其全局唯一 AS號?(ASN) 所標識。就像 IP地址那樣， AS 號由 ICANN 區域注冊機構所分配
? ? ? ? ?在相同 AS 中的路由器都運行相同的路由選擇算法并且有彼此的信息。在一個自治系統內運行的路由選擇算法叫做自治系統內部路由選擇協議。
開放最短路優先（OSPF）
? ? ? ? OSPF 路由選擇及其關系密切的協議 IS-IS 都被廣泛用于因特網的 AS 內部路由選擇。
? ? ? ? OSPF 是一種鏈路狀態協議，它使用洪泛鏈路狀態信息和 Dijkstra 最低開銷路徑算法。使用 OSPF，一臺路由器構建了一幅關于整個自治系統的完整拓撲圖(即一幅圖)。于是，每臺路由器在本地運行 Dijkstra 的最短路徑算法，以確定一個以自身為根節點到所有子網的最短路徑樹。各條鏈路開銷是由網絡管理員配置的(參見"實踐原則：設置 OSPF 鏈路權值"）。管理員也許會選擇將所有鏈路開銷設為 1，因而實現了最少跳數路由選擇，或者可能會選擇將鏈路權值按與鏈路容量成反比來設置，從而不鼓勵流量使用低帶寬鏈路。OSPF 不強制使用設置鏈路權值的策略，而是提供了一種機制(協議) ，為給定鏈路權值集合確定最低開銷路徑的路由選擇 。
?????????使用 OSPF 時，路由器向自治系統內所有其他路由器廣播路由選擇信息，而不僅僅是向其相鄰路由器廣播。每當一條鏈路的狀態發生變化時（如開銷的變化或連接/中斷狀態的變化) ，路由器就會廣播鏈路狀態信息。即使鏈路狀態未發生變化，它也要周期性地(至少每隔 30 min 一次)廣播鏈路狀態。RFC 2328 中有這樣的說明:"鏈路狀態通告的這種周期性更新增加了鏈路狀態算法的健壯性"。OSPF 通告包含在 OSPF 報文中，該 OSPF報文直接由 IP 承載，對 OSPF 其上層協議的值為 89。因此 OSPF 協議必須自己實現諸如可靠報文傳輸、鏈路狀態廣播等功能。OSPF 協議還要檢查鏈路正在運行(通過向相連的鄰居發送 HELLO 報文) ，并允許 OSPF 路由器獲得相鄰路由器的網絡范圍鏈路狀態的數據庫。
?
)
