链路状态路由算法.doc

路由算法一 链路状态路由算法的具体实现（1）链路状态路由算法的原理链路状态路由协议是目前使用最广的一类域内路由协议。它采用一种“拼图”的设计策略，即每个路由器将它到其周围邻居的链路状态向全网的其他路由器进行广播。这样，一个路由器收到从网络中其他路由器发送过来的路由信息后，它对这些链路状态进行拼装，最终生成一个全网的拓扑视图，近而可以通过最短路径算法来计算它到别的路由器的最短路径。运行链路状态路由协议的路由器, 每台路由器公在其接口的状态发生变化时，才将变化后的状态发送给其他所有路由器，每台路由器都使用收到的信息重新计算前往每个网络的最佳路径，然后将这些信息存储到自己的路由选择表中。链路状态路由算法背后的思想非常简单，可以用5个基本步骤加以描述。1、发现他的邻接点，并知道其网络的地址。2、测量到各邻接点的延迟或开销。3、构造一个分组，分组中包含所有他刚刚收到的信息。4、将这个分组发送给其他的路由器。5、计算出到每一个其他路由器的最短路径。例如，每个路由器运行Dijkstra算法就可以找从它到每一个其他路由器的最短路径。（2）程序源代码（c+语言，核心算法为迪杰斯特拉算法）#include #include #define routeTable routeTable.txtusing namespace std;const int MAX_NODES = 1024; /能接受的最大路由数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 ; 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目的节点 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; /=100000 p-lable = false;statet.length = 0; /源节点的权值改为0statet.lable = true;k = t;cout 最短路径为： 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 = 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; 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 +) 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;jVnums;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 t = endl;cout t 1.创建路由表 endl;cout t 2.增加路由 endl;cout t 3.删除路由 endl;cout t 4.修改路由 endl;cout t 5.找两个路由间的最短路径 endl;cout t 6.保存路由表到文件 endl;cout t 7.显示路由表信息 endl;cout t 8.退出 endl;cout t = endl;/cout 输入路由总节点数： Vnums;cout 选择操作(1-8)： change;switch(change) case 1: creatRouteMap(Vnums); system(pause); system(cls);break;case 2:addRoute(); system(pause); 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=NULL) 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;（3）网络拓扑结构ABEFDC32378516（4）实验运行截图（5）分析与综述本实验用手动输入方式来代替路由之间的分组发送消息，并可以用增加，删除，修改来模拟现实的情况。其核心是最短路径算法，本实验用的是的迪杰斯特拉算法。3-3-2-2-4-1-0表示算法的计算过程并不是实际的具体跳法。优点：比距