距離矢量路由算法

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

2、相鄰處收到更新信息時(shí)，它會(huì)將更新信息與本身的路由表相比較。如果該路由器比較出一條新路由或是找到一條比當(dāng)前路由更好的路由時(shí)，它會(huì)對(duì)路由表進(jìn)行更新：將從該路由器到鄰居之間的向量距離與更新信息中的向量距離相加作為新路由的向量距離。在距離向量路由算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，路由器之間也將及時(shí)地相互通知有關(guān)變更信息。距離矢量路由算法在理論中可以工作，但在實(shí)踐中有一個(gè)嚴(yán)重的缺陷：雖然它總是能夠達(dá)到正確的答案，但是它收斂到正確答案的速度非常慢，尤其是，它對(duì)于好消息的反應(yīng)非?？欤菍?duì)于壞消息的反應(yīng)非常遲緩。程序源代碼（c語言）#include stdio

3、.h#include stdlib.h /atoi的頭文件/#include alloc.h#define ROUTNUM 7 /定義路由的個(gè)數(shù)為7個(gè)typedef structint dis; /存延遲大小int from; /存下一跳的路由RoutNode;RoutNode dataROUTNUMROUTNUM;/*路由表，能存7行7列數(shù)據(jù),數(shù)據(jù)為權(quán)值*/void InitData(FILE* pfile);/*從數(shù)據(jù)文件讀取數(shù)據(jù)，初始化路由表*/void OutputRoutData();/*輸出所有的路由表*/void Communication(int recv, int send)

4、;/*send點(diǎn)向recv點(diǎn)發(fā)送自己的路由表*/void Exchange();/*所有節(jié)點(diǎn)進(jìn)行一次數(shù)據(jù)交換, 更新路由表*/void main()int start, end, i, j;FILE *pfile;pfile = fopen(1.txt, r);if (pfile = NULL)printf(文件打開錯(cuò)誤，按任意鍵退出.n);getch();return;elseprintf(n路由表初始:n);InitData(pfile);fclose(pfile);for (i = 0; iROUTNUM; i+)printf(%c|, i + 65);for (j = 0; j 0)p

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

6、= end | start 6 | end 6)printf(n輸入錯(cuò)誤，請(qǐng)按任意鍵退出n);getch();return;elseint cur = start;int total = 0;if (datastartend.dis , cur + 65);while (datacurend.from = 0) /起始點(diǎn)與終點(diǎn)不相連。0是Atotal += datacurdatacurend.from.dis; /total變成cur與下一跳的延遲printf(%c-, datacurend.from + 65);cur = datacurend.from; /起始路由變成下一跳 total

7、+= 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); /文件指針從距0位置0距離開始讀取for (m = 0; !feof(pfile) & m 7; m+) /feof(pfile),文件尾返回1，不是返回0.即不是文件尾部且m7循環(huán).for (n = 0; !feof(pfile) & n = 0 & c = 9) | c = -)

8、/*如果讀到數(shù)字或符號(hào).本題路由權(quán)值只能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 = 0; i ROUTNUM; i+)printf(%c , i + 65);for (j = 0; j ROUTNUM; j+)if (dataij.dis =

9、10)printf( %d, dataij.dis);elseprintf( %d, dataij.dis);if (dataij.from 0)/如果未經(jīng)過其它節(jié)點(diǎn) 所以直接相連的路由下一跳為-1printf( - );elseprintf( %c , dataij.from + 65); /輸出下一跳路由 printf(n); void Communication(int recv, int send) /相連的兩路由recv和send交換數(shù)據(jù)計(jì)算一次得到暫時(shí)最短距離int i;for (i = 0; i 0)/如果send節(jié)點(diǎn)到i號(hào)節(jié)點(diǎn)有路線if (datarecvi.dis datas

10、endi.dis + datarecvsend.dis)/第二種recv與i相連，且直接相連值大于間接到i的延遲/如果現(xiàn)有路徑比新路徑遠(yuǎn)datarecvi.dis = datasendi.dis + datarecvsend.dis; /將recv到i的延遲改為間接延遲的值datarecvi.from = send; /下一跳改為send void Exchange() /實(shí)現(xiàn)所有相連的兩路由進(jìn)行數(shù)據(jù)交換并計(jì)算最短數(shù)值int i, j;for (i = 0; i ROUTNUM; i+)for (j = 0; j 0)/如果兩個(gè)節(jié)點(diǎn)之間有路徑Communication(j, i);/將i號(hào)節(jié)點(diǎn)

11、的路由表發(fā)送給j號(hào)節(jié)點(diǎn) /*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,數(shù)值代表權(quán)值（如延遲大小）0代表目的網(wǎng)絡(luò)到其本身-1代表無法直接相連 */網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)CDAGEFB93524581實(shí)驗(yàn)結(jié)果分析與綜述實(shí)驗(yàn)結(jié)果正確。起始點(diǎn)C下一跳為D到達(dá)E。其最短的距離為10.多次驗(yàn)證均正確。本實(shí)驗(yàn)的路由表由一個(gè)而為數(shù)組結(jié)構(gòu)體實(shí)現(xiàn)，數(shù)組名代表兩個(gè)相關(guān)路由，結(jié)構(gòu)體中存放延時(shí)和下一跳。路由表初始信息從文件讀取，根據(jù)距離向量路由算法系統(tǒng)自動(dòng)完成路由表的更新操作，最