链路状态路由算法

1、路由算法一链路状态路由算法的具体实现（1）链路状态路由算法的原理链路状态路由协议是目前使用最广的一类域内路由协议。它采用一种“拼 图”的设计策略，即每个路由器将它到其周围邻居的链路状态向全网的其他路由器 进行广播。这样，一个路由器收到从网络中其他路由器发送过来的路由信息后，它 对这些链路状态进行拼装，最终生成一个全网的拓扑视图，近而可以通过最短路径 算法来计算它到别的路由器的最短路径。运行链路状态路由协议的路由器，每台路 由器公在其接口的状态发生变化时，才将变化后的状态发送给其他所有路由器，每 台路由器都使用收到的信息重新计算前往每个网络的最佳路径，然后将这些信息存 储到自己的路由选择表中。链

2、路状态路由算法背后的思想非常简单，可以用5个基本步骤加以描述。1、发现他的邻接点，并知道其网络的地址。2、测量到各邻接点的延迟或开销。3、构造一个分组，分组中包含所有他刚刚收到的信息。4、将这个分组发送给其他的路由器。5、计算出到每一个其他路由器的最短路径。例如，每个路由器运行 Dijkstra算法就可以找从它到每一个其他路由器的最短路径。（2）程序源代码（C+语言，核心算法为迪杰斯特拉算法）#include #include #define routeTable routeTable.txtusing namespace std;const int MAX_NODES = 1024;/能接受

3、的最大路由数const int INFINITY = 100000;/权值int distMAX_NODESMAX_NODES;用于存放网络拓扑结构连接矩阵int static Vnums;/总的节点(路由)数void initDist()(初始化邻接矩阵for(int i = 0; i MAX_NODES; i +)for(int j = 0; j MAX_NODES; j +)distij = 0;void creatRouteMap(int Vnums)(创建网络拓扑结构的邻接矩阵，1.创建路由表函数for(int i = 0; i Vnums; i +)(cout 输入第 i 个节点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、的 节点t源节点struct state(/存放节点数据int predecessor;/父节点int length;/权值，存放最小权值bool lable;访问状态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;/源节点的权值改为0statet.lable = true;k = t;cout 最短

6、路径为： endl;do(/dowhile先是把所有最短路径连起来for(i = 0; i Vnums; i +)找到与永久标定节点直接相连的节点，并改变其权值(if( (distki != 0) & (statei.lable = false)(/与源节点直接相连并且不是同一个源节点k源节点if(statek.length + distki statei.length)(statei.predecessor = k; /记录节点 cout k ；statei.length = statek.length + distki; 路径长度总k = 0;min = INFINITY;for( i =

7、 0; i Vnums; i +)/找到与永久标定节点相邻的节点，并把与最小权值的相邻点改为永久标点(if(statei.lable = false) & (statei.length min) 找到与 永久标点相邻的节点(min = statei.length;k = i;statek.lable = true;/新的永久标点也变为访问过while(k!=s);新的永久标点是否为目的节点，不是继续循环cout s 最小距离二minn；void addRoute()(添加一个路由及结点信息2.增加路由char ch;do(cout 添加一个路由： endl;Vnums = Vnums + 1;

8、cout 输入第 Vnums - 1 个节点与第；for(int j = 0; j Vnums; j +)(cout j 个节点的权值： distVnums - 1j;/写入对应增加行的信息distjVnums - 1 = distVnums - 1j; /写入对应增加列的信息 cout 继续添加(y 或者 n) : ch; if(ch = n) break;while(ch = y); void deleteRoute()(/3.删除路由char ch; int delNum; do( cout 输入删除路由结点号： delNum; for(int j = 0; j Vnums; j +)

9、( distdelNum - 1j = 0;/对应行的信息distjdelNum - 1 = distdelNum - 1j; /对应列的信息 cout 继续删除(y 或者 n): ch;if(ch = n) break;while(ch = y);void changeRoute()(/4.修改路由int i,j;cout 输入要修改的结点1： i;cout 输入要修改的结点2： j;cout 输入修改的权值：disti-1j-1;void displayRouteInfo()/7.显示路由表信息cout * endl;cout 路由表信息： endl;cout;for(int j=0;jV

10、nums;j+)coutt(char)(j+65);/显示ABC.的对应数字为012.cout（目的节点）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:初始化权值矩阵initDist ();cout Vnums:do 主菜单界面cout 、/ /z=/z

11、 endl;cout t.创建路由表 endl;cout /z2.增加路由 endl:cout /z3.删除路由 endl:cout t /z4.修改路由 endl;cout t 5.找两个路由间的最短路径 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 输入目标节点和源节点： desNode;cin rouNode;dijkstra(desNode,rouNode,path); 求最短路径system(pause)；system(cls);break;case 6:routeTables.open(routeTable);if(routeTables=NUL

13、L)(cout 打开文件夹错误： 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;网络拓扑结构实验运行截图呕回

14、选择菜单句或者昨径路短最件的文息 表 由表表 由由由由路由由 路路路路个路路 建加除改两存一宙 创惨着显退12345678F目的节点 0 6 0 7 8 0E 5 0 1 0 003301007路由表信息: ABfl03B30C02D00E50F06请按任意键继续. .褥回选择菜单句或者nn径路短最件的文息信 表 由表表 由由由由路由由 路路路路个路路 建加除改两存雷 创端修有显退12345678选择操作输入目标节点和源节点：0备短路径为:3 - 3 - 2 - 2 - 4-1 -巨离=8请按任意键继续 分析与综述本实验用手动输入方式来代替路由之间的分组发送消息，并可以用增加，删 除，修改来模拟现实的情况。其核心是最短路径算法，本实验用的是的迪杰斯特拉 算法。3-3-2-2-4T-0表示算法的计算过程并不是实际的具体跳法。优点：