距離向量路由算法

定義

距離向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算法(Ford-Fulkerson Algorithm)，其被距離向量協定作為一個算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用這個算法的路由器必須掌握這個距離表(它是一個一維排列-“一個向量”)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為“成本”)。這個在那個算法中的度量公式是跳躍的次數， 等待時間，流出數據包的數量，等等。
在距離向量路由算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。

路由表的建立和更新

如上圖，有三個路由器，A，B和C。路由器A的兩個網路接口E0和S0
分別連線在 10.1.0.0和10.2.0.0網段上；路由器B的兩個網路接口S0和S1
分別連線在 10.2.0.0和10.3.0.0網段上；路由器C的兩個網路接口S0和E0
分別連線在 10.3.0.0和10.4.0.0網段上；
如上圖中各路由表的前兩行所示，通過路由表的網路接口到與之直接相連的網
絡的網路連線，其向量距離設定為0。這即是最初的路由表。
當路由器B和A以及B和C之間相互交換路由信息後，它們會更新各自的路由表。
例如，路由器B通過網路連線埠S1收到路由器C的路由信息（10.3.0.0,S0,0）和(10.4.0.0,E0,0)後，在自己的路由表中增加一條(10.4.0.0,S1,1)路由信息。該信息表示：通過路由器B的網路接
口S1可以訪問到10.4.0.0網段，其向量距離為1,該向量距離是在路由器C的基礎上加1獲得的。
同樣道理，路由器B還會產生一條(10.1.0.0,S0,1)路由，這條路由是通過網路連線埠S0從路由器A
獲得的。如此反覆，直到最終收斂，形成圖中所示的路由表。
概括地說，距離向量算法要求每一個路由器把它的整個路由表傳送給與它直接連線的其它路由
器。路由表中的每一條記錄都包括目標邏輯地址、相應的網路接口和該條路由的向量距離。當一個路
由器從它的相鄰處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條
新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的
向量距離與更新信息中的向量距離相加作為新路由的向量距離。

參與運算信息

目的地址：在算法的IP實現中，這指的是主機或的IP 地址。 下一跳地址：到信宿的路由中的第一個路由器。 接口：用於到下一跳物理。 metric值：一個數，指明本路由器到信宿的開銷。 定時器：路由項最後一次被修改的時間。 路由標記：區分路由為內部路由協定的路由還是外部路由協定的路由的標記。

運算

路由器間交換的最重要的信息是修改報文，參加路由維護計畫的路由器傳送當前存在於實體的描述路由庫的路由修改報文。僅通過相鄰路由器間交換路由信息是可以維護整個系統的最佳路由的，這在接下來的討論中會逐步得到證明。 距離向量算法總是基於一個這樣的事實：路由庫中的路由已是目前通過報文交換而得到的最佳路由。同時，報文交換僅限於相鄰的實體間，也就是說，實體共享同一個。當然，要定義路由是最佳的，就必須有衡量的辦法，這就用到前面所說的“metric”。RIP簡單的中，通常用可行路由所經的路由器數簡單地計算metric值。在複雜的中，metric一般代表該路由傳輸報的延遲或其它傳送開銷。 令D代表從實體i到實體j的最佳路由的metric值，d（i，j）代表從i直接到j的開銷，因為開銷是可加的，算法中最佳路由如此獲取表示： D（i，i）=0， 對所有的i D（i，j）=MIN[d（i，j）+D（k，j）， 當i不等於k時 實體i從相鄰路由器k收到k到j的開銷的估計D，i將D（i，j）加上i到k的開銷估計d（i，j），i比較從所有相鄰路由器得到的數值，取得最小數，就得到了它到j的最佳路由。