鏈路狀態(tài)路由算法

1、路由算法一鏈路狀態(tài)路由算法的具體實(shí)現(xiàn)（1）鏈路狀態(tài)路由算法的原理鏈路狀態(tài)路由協(xié)議是目前使用最廣的一類域內(nèi)路由協(xié)議。它采用一種“拼 圖”的設(shè)計(jì)策略，即每個(gè)路由器將它到其周圍鄰居的鏈路狀態(tài)向全網(wǎng)的其他路由器 進(jìn)行廣播。這樣，一個(gè)路由器收到從網(wǎng)絡(luò)中其他路由器發(fā)送過來的路由信息后，它 對(duì)這些鏈路狀態(tài)進(jìn)行拼裝，最終生成一個(gè)全網(wǎng)的拓?fù)湟晥D，近而可以通過最短路徑 算法來計(jì)算它到別的路由器的最短路徑。運(yùn)行鏈路狀態(tài)路由協(xié)議的路由器，每臺(tái)路 由器公在其接口的狀態(tài)發(fā)生變化時(shí)，才將變化后的狀態(tài)發(fā)送給其他所有路由器，每 臺(tái)路由器都使用收到的信息重新計(jì)算前往每個(gè)網(wǎng)絡(luò)的最佳路徑，然后將這些信息存 儲(chǔ)到自己的路由選擇表中。鏈

2、路狀態(tài)路由算法背后的思想非常簡單，可以用5個(gè)基本步驟加以描述。1、發(fā)現(xiàn)他的鄰接點(diǎn)，并知道其網(wǎng)絡(luò)的地址。2、測量到各鄰接點(diǎn)的延遲或開銷。3、構(gòu)造一個(gè)分組，分組中包含所有他剛剛收到的信息。4、將這個(gè)分組發(fā)送給其他的路由器。5、計(jì)算出到每一個(gè)其他路由器的最短路徑。例如，每個(gè)路由器運(yùn)行 Dijkstra算法就可以找從它到每一個(gè)其他路由器的最短路徑。（2）程序源代碼（C+語言，核心算法為迪杰斯特拉算法）#include #include #define routeTable routeTable.txtusing namespace std;const int MAX_NODES = 1024;/能接受

3、的最大路由數(shù)const int INFINITY = 100000;/權(quán)值int distMAX_NODESMAX_NODES;用于存放網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)連接矩陣int static Vnums;/總的節(jié)點(diǎn)(路由)數(shù)void initDist()(初始化鄰接矩陣for(int i = 0; i MAX_NODES; i +)for(int j = 0; j MAX_NODES; j +)distij = 0;void creatRouteMap(int Vnums)(創(chuàng)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鄰接矩陣，1.創(chuàng)建路由表函數(shù)for(int i = 0; i Vnums; i +)(cout 輸入第 i 個(gè)節(jié)點(diǎn)n

4、”;for(int j = 0; j Vnums; j +)(cout 的第 j distij;void saveRoute(ofstream& routeTables)( /6.保存路由信息routeTables 路由鄰接矩陣為：；routeTables n;routeTables *;routeTables n;for(int i = 0; i Vnums; i +)(for(int j = 0; j Vnums; j +)(routeTablesdistijt;routeTables n;void dijkstra(int s, int t, int path) /迪杰斯特拉算法 s 目

5、的 節(jié)點(diǎn)t源節(jié)點(diǎn)struct state(/存放節(jié)點(diǎn)數(shù)據(jù)int predecessor;/父節(jié)點(diǎn)int length;/權(quán)值，存放最小權(quán)值bool lable;訪問狀態(tài)false未被訪問過，true訪問過stateMAX_NODES;int i,k,min,print;struct state *p;for(p = &state0; p predecessor = -1;/類似存下一跳p-length = INFINITY; /=100000p-lable = false;statet.length = 0;/源節(jié)點(diǎn)的權(quán)值改為0statet.lable = true;k = t;cout 最短

6、路徑為： endl;do(/dowhile先是把所有最短路徑連起來for(i = 0; i Vnums; i +)找到與永久標(biāo)定節(jié)點(diǎn)直接相連的節(jié)點(diǎn)，并改變其權(quán)值(if( (distki != 0) & (statei.lable = false)(/與源節(jié)點(diǎn)直接相連并且不是同一個(gè)源節(jié)點(diǎn)k源節(jié)點(diǎn)if(statek.length + distki statei.length)(statei.predecessor = k; /記錄節(jié)點(diǎn) cout k ；statei.length = statek.length + distki; 路徑長度總k = 0;min = INFINITY;for( i =

7、 0; i Vnums; i +)/找到與永久標(biāo)定節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，并把與最小權(quán)值的相鄰點(diǎn)改為永久標(biāo)點(diǎn)(if(statei.lable = false) & (statei.length min) 找到與 永久標(biāo)點(diǎn)相鄰的節(jié)點(diǎn)(min = statei.length;k = i;statek.lable = true;/新的永久標(biāo)點(diǎn)也變?yōu)樵L問過while(k!=s);新的永久標(biāo)點(diǎn)是否為目的節(jié)點(diǎn)，不是繼續(xù)循環(huán)cout s 最小距離二minn；void addRoute()(添加一個(gè)路由及結(jié)點(diǎn)信息2.增加路由char ch;do(cout 添加一個(gè)路由： endl;Vnums = Vnums + 1;

8、cout 輸入第 Vnums - 1 個(gè)節(jié)點(diǎn)與第；for(int j = 0; j Vnums; j +)(cout j 個(gè)節(jié)點(diǎn)的權(quán)值： distVnums - 1j;/寫入對(duì)應(yīng)增加行的信息distjVnums - 1 = distVnums - 1j; /寫入對(duì)應(yīng)增加列的信息 cout 繼續(xù)添加(y 或者 n) : ch; if(ch = n) break;while(ch = y); void deleteRoute()(/3.刪除路由char ch; int delNum; do( cout 輸入刪除路由結(jié)點(diǎn)號(hào)： delNum; for(int j = 0; j Vnums; j +)

9、( distdelNum - 1j = 0;/對(duì)應(yīng)行的信息distjdelNum - 1 = distdelNum - 1j; /對(duì)應(yīng)列的信息 cout 繼續(xù)刪除(y 或者 n): ch;if(ch = n) break;while(ch = y);void changeRoute()(/4.修改路由int i,j;cout 輸入要修改的結(jié)點(diǎn)1： i;cout 輸入要修改的結(jié)點(diǎn)2： j;cout 輸入修改的權(quán)值：disti-1j-1;void displayRouteInfo()/7.顯示路由表信息cout * endl;cout 路由表信息： endl;cout;for(int j=0;jV

10、nums;j+)coutt(char)(j+65);/顯示ABC.的對(duì)應(yīng)數(shù)字為012.cout（目的節(jié)點(diǎn)）n”;for(int i = 0; i Vnums; i +) (int c=i+65;cout(char)ct;for(int j = 0; j Vnums; j +)(cout distij t;cout n;int main()(int desNode,rouNode;int pathMAX_NODES;int change;char ch;ofstream routeTables:初始化權(quán)值矩陣initDist ();cout Vnums:do 主菜單界面cout 、/ /z=/z

11、 endl;cout t.創(chuàng)建路由表 endl;cout /z2.增加路由 endl:cout /z3.刪除路由 endl:cout t /z4.修改路由 endl;cout t 5.找兩個(gè)路由間的最短路徑 endl;cout t 6.保存路由表到文件 endl;cout /z7.顯示路由表信息 endl:cout Vnums;cout 選擇操作(1-8) ： change;switch(change)(case 1: creatRouteMap(Vnums); system(pause)； system(cls);break;case 2:addRoute(); system(pause)；

12、 system(cls); break;case 3: deleteRoute(); system(pause)； system(cls); break;case 4:changeRoute(); system(pause)； system(cls);break;case 5: cout 輸入目標(biāo)節(jié)點(diǎn)和源節(jié)點(diǎn)： desNode;cin rouNode;dijkstra(desNode,rouNode,path); 求最短路徑system(pause)；system(cls);break;case 6:routeTables.open(routeTable);if(routeTables=NUL

13、L)(cout 打開文件夾錯(cuò)誤： endl;getchar();exit(0);保存文件saveRoute(routeTables);routeTables.close();system(cls);break;case 7: displayRouteInfo();system(pause)；system(cls)； break;case 8: return 0;default: system(cls); break;cout 返回選擇菜單(y或者n): ch;if(ch = n) break;while(ch = y);system(pause)；return 0;網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)實(shí)驗(yàn)運(yùn)行截圖嘔回

14、選擇菜單句或者昨徑路短最件的文息 表 由表表 由由由由路由由 路路路路個(gè)路路 建加除改兩存一宙 創(chuàng)慘著顯退12345678F目的節(jié)點(diǎn) 0 6 0 7 8 0E 5 0 1 0 003301007路由表信息: ABfl03B30C02D00E50F06請(qǐng)按任意鍵繼續(xù). .褥回選擇菜單句或者nn徑路短最件的文息信 表 由表表 由由由由路由由 路路路路個(gè)路路 建加除改兩存雷 創(chuàng)端修有顯退12345678選擇操作輸入目標(biāo)節(jié)點(diǎn)和源節(jié)點(diǎn)：0備短路徑為:3 - 3 - 2 - 2 - 4-1 -巨離=8請(qǐng)按任意鍵繼續(xù) 分析與綜述本實(shí)驗(yàn)用手動(dòng)輸入方式來代替路由之間的分組發(fā)送消息，并可以用增加，刪 除，修改來模擬現(xiàn)實(shí)的情況。其核心是最短路徑算法，本實(shí)驗(yàn)用的是的迪杰斯特拉 算法。3-3-2-2-4T-0表示算法的計(jì)算過程并不是實(shí)際的具體跳法。優(yōu)點(diǎn)：