1、路由算法 距離矢量路由算法的具體實現 距離矢量路由算法的原理 距離向量路由算法 （Bellman-Ford Routing Algorithm） ，作為距離向量協議的一個算法， 如 RIP, （RIP 跳 最大跳數 16 ）BGP 。使用這個算法的路由器必須掌握這個距離表，它告訴在網絡 中每個節點的最遠和最近距離。 在距離表中的這個信息是根據臨近接點信息的改變而時時更 新的。這個在算法中的度量公式是跳躍的次數，等待時間，流出數據包的數量等等。 概括地說，距離向量算法要求每一個路由器把它的整個路由表發送給與它直接連接的其它路 由器。路由表中的每一條記錄都包括目標邏輯地址、 相應的網絡接口和該條路

2、由的向量距離。 當一個路由器從它的相鄰處收到更新信息時， 它會將更新信息與本身的路由表相比較。 如果 該路由器比較出一條新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更 新：將從該路由器到鄰居之間的向量距離與更新信息中的向量距離相加作為新路由的向量距 離。在距離向量路由算法中， 相鄰路由器之間周期性地相互交換各自的路由表備份。 當網絡 拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。 距離矢量路由算法在理論中可以工作， 但在實踐中有一個嚴重的缺陷： 雖然它總是能夠達到 正確的答案，但是它收斂到正確答案的速度非常慢，尤其是，它對于好消息的反應非?？?， 但是對于壞消息的反

3、應非常遲緩。程序源代碼（ c 語言）#include stdio.h#include stdlib.h /atoi 的頭文件/#include alloc.h/定義路由的個數為 7 個/存延遲大小/存下一跳的路由#define ROUTNUM 7 typedef struct int dis;int from; RoutNode;RoutNode dataROUTNUMROUTNUM;/*路由表，能存 7行 7列數據,數據為權值 */void InitData(FILE* pfile);/*從數據文件讀取數據，初始化路由表*/void OutputRoutData();/* 輸出所有的路由表

4、*/void Communication(int recv, int send);/*send 點向 recv 點發送自己的路由表 */void Exchange(); /* 所有節點進行一次數據交換 , 更新路由表 */void main()int start, end, i, j;FILE *pfile;pfile = fopen(1.txt, r);if (pfile = NULL)printf( 文件打開錯誤，按任意鍵退出 .n); getch();return;elseprintf(n 路由表初始 :n);InitData(pfile);fclose(pfile);for (i =

5、0; iROUTNUM; i+) printf(%c|, i + 65);for (j = 0; j 0) printf( , j + 65, dataij.dis); printf(n);/循環 7 次（好像多余，改成一次得到同樣結果）/ 顯示各路由的路由表for (i = 0; i ROUTNUM; i+) Exchange();printf(n 路由表交換 :n);OutputRoutData();printf(輸入起始路由節點數字 (d-%d)O代表A, 1代表B. :, 0, ROUTNUM - 1); scanf(%d, &start);printf(輸入終點路由節點數字 (d-%

6、d)O代表A, 1代表B. : , 0, ROUTNUM - 1); scanf(%d, &end);if (start = end | start 6 | end 6)printf(n 輸入錯誤，請按任意鍵退出 n); getch();return;elseint cur = start;int total = 0;if (datastartend.dis , cur + 65);while (datacurend.from = 0)/起始點與終點不相連。 0 是 Atotal += datacurdatacurend.from.dis;/total 變成 cur 與下一跳的延遲printf

7、(%c-, datacurend.from + 65);cur = datacurend.from;/起始路由變成下一跳total += datacurend.dis;printf(%cn 總的路由距離 = %d, end + 65, total);getch();return;void InitData(FILE *pfile)char num10;int i = 0;char c;int m, n;fseek(pfile, 0, 0);/文件指針從距for (m = 0; !feof(pfile) & m 7; m+) 即不是文件尾部且 m7 循環.0 位置 0 距離開始讀取/feof(p

8、file), 文件尾返回 1，不是返回 0.for (n = 0; !feof(pfile) & n = 0 & c = 9) | c = -) /* 如果讀到數字或符號 .本題路由權 值只能 0 到 9*/numi+ = c; /*end of else if*/ /*end of while*/ /*end of for (n = 0*/ /*end of for (m = 0*/ void OutputRoutData()int i, j;printf( );for (i = 0; i ROUTNUM; i+)printf( %c , i + 65); printf(n);for (i

9、= 0; i ROUTNUM; i+)printf(%c , i + 65);for (j = 0; j ROUTNUM; j+)if (dataij.dis =10) printf( %d, dataij.dis);else printf( %d, dataij.dis);if (dataij.from 0)/如果未經過其它節點所以直接相連的路由下一跳為-1printf( - );elseprintf( %c , dataij.from + 65);/輸出下一跳路由 printf(n);void Communication(int recv, int send)/相連的兩路由 recv禾口

10、send交換數據計算一次得到暫時最短距離int i;for (i = 0; i 0)/如果 send 節點到 i 號節點有路線if (datarecvi.dis datasendi.dis + datarecvsend.dis)/ 第二種 recv 與 i 相連，且直接相連值大于間接到 i 的延遲/如果現有路徑比新路徑遠datarecvi.dis = datasendi.dis + datarecvsend.dis;/ 將 recv 到 i的延遲改為間接延遲的值datarecvi.from = send;/下一跳改為 send/實現所有相連的兩路由進行數據交換并計/如果兩個節點之間有路徑/ 將

11、 i 號節點的路由表發送給 j 號節點void Exchange() 算最短數值 int i, j;for (i = 0; i ROUTNUM; i+)for (j = 0; j 0)Communication(j, i); /*1.text 中存者路由信息0, 2,-1,-1, 8,-1, 5,2, 0,4, 5,-1,-1,-1,-1,4, 0,-1,-1, 9,-1,-1, 5,-1, 0,1,-1,-1,8,-1,-1,1, 0,-1, 7,-1,-1, 9,-1,-1, 0, 3,5,-1,-1,-1, 7, 3, 0,數值代表權值（如延遲大?。?代表目的網絡到其本身-1代表無法直接

12、相連*/網絡拓撲結構實驗結果c、D：亜離矢量算法 123Debugj ul ish i I iang.exe1n ii：C!ib;：E!F!G!路由表初始:骼由表交換:A2045107暢入起始路由垃點婁 腳入終點路由常點幾C-D-E總的路由距離=106B7B88 G54-56D10 G7A0-9B10D9-11B9B0111 G8E10D1010 G7一9- 11G10G0 -3一11B8E73-0代表A, V代表B.:2-代初，1?氏表B.J : 4CDEFG分析與綜述實驗結果正確。起始點 C下一跳為D到達E。其最短的距離為10多次驗證均正確。本實驗 的路由表由一個而為數組結構體實現， 數組名代表兩個相關路由， 結構體中存放延時和下一 跳。路由表初始信息從文件讀取， 根據距離向量路由算法系統自動完成路