-
距離矢量路由協議
鎖定
- 中文名
- 距離矢量路由協議
- 外文名
- distance-vector routing protocol
距離矢量路由協議簡介
距離向量路由協議（英語：distance-vector routing protocol），為路由協議中的兩大分類之一，這類協議採用距離向量（distance-vector，縮寫為DV）算法來決定報文交換的路徑。包括貝爾曼-福特算法，Ford–Fulkerson algorithm與DUAL FSM等算法，都被歸類於距離向量算法中。
距離矢量路由協議貝爾曼-福特算法
貝爾曼-福特算法（英語：Bellman–Ford algorithm），求解單源最短路徑問題的一種算法，由理查德·貝爾曼（Richard Bellman） 和萊斯特·福特創立的。有時候這種算法也被稱為 Moore-Bellman-Ford 算法，因為Edward F. Moore也為這個算法的發展做出了貢獻。它的原理是對圖進行
次鬆弛操作，得到所有可能的最短路徑。其優於迪科斯徹算法的方面是邊的權值可以為負數、實現簡單，缺點是時間複雜度過高，高達
。但算法可以進行若干種優化，提高了效率。
距離矢量路由協議算法
貝爾曼-福特算法與迪科斯徹算法類似，都以鬆弛操作為基礎，即估計的最短路徑值漸漸地被更加準確的值替代，直至得到最優解。在兩個算法中，計算時每個邊之間的估計距離值都比真實值大，並且被新找到路徑的最小長度替代。 然而，迪科斯徹算法以貪心法選取未被處理的具有最小權值的節點，然後對其的出邊進行鬆弛操作；而貝爾曼-福特算法簡單地對所有邊進行鬆弛操作，共
次，其中
是圖的點的數量。在重複地計算中，已計算得到正確的距離的邊的數量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特算法比迪科斯徹算法適用於更多種類的輸入。
距離矢量路由協議偽代碼表示
procedure BellmanFord(list vertices, list edges, vertex source) // 該實現讀入邊和節點的列表，並向兩個數組（distance和predecessor）中寫入最短路徑信息 // 步驟1：初始化圖 for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // 步驟2：重複對每一條邊進行鬆弛操作 for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // 步驟3：檢查負權環 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "圖包含了負權環"
距離矢量路由協議路由協議
路由協議（英語：Routing protocol）是一種指定數據包轉送方式的網上協議。Internet網絡的主要節點設備是路由器，路由器通過路由表來轉發接收到的數據。轉發策略可以是人工指定的（通過靜態路由、策略路由等方法）。在具有較小規模的網絡中，人工指定轉發策略沒有任何問題。但是在具有較大規模的網絡中（如跨國企業網絡、ISP網絡），如果通過人工指定轉發策略，將會給網絡管理員帶來巨大的工作量，並且在管理、維護路由表上也變得十分困難。為了解決這個問題，動態路由協議應運而生。動態路由協議可以讓路由器自動學習到其他路由器的網絡，並且網絡拓撲發生改變後自動更新路由表。網絡管理員只需要配置動態路由協議即可，相比人工指定轉發策略，工作量大大減少。
[1]
距離矢量路由協議路由信息協議
路由信息協議（英語：Routing Information Protocol，縮寫：RIP）是一種內部網關協議（IGP），為最早出現的距離向量路由協定。屬於網絡層，其主要應用於規模較小的、可靠性要求較低的網絡，可以通過不斷的交換信息讓路由器動態的適應網絡連接的變化，這些信息包括每個路由器可以到達哪些網絡，這些網絡有多遠等。
