距离矢量路由算法

路由算法距离矢量路由算法的具体实现距离矢量路由算法的原理距离向量路由算法(Bellman-FordRoutingAlgorithm)，作为距离向量协议的一个算法，如RIP,（RIP跳最大跳数16）BGP。使用这个算法的路由器必须掌握这个距离表，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。这个在算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量等等。概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路由器从它的相邻处收到更新信息时，它会将更新信息与本身的路由表相比较。如果该路由器比较出一条新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更新：将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距离。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。距离矢量路由算法在理论中可以工作，但在实践中有一个严重的缺陷：虽然它总是能够达到正确的答案，但是它收敛到正确答案的速度非常慢，尤其是，它对于好消息的反应非常快，但是对于坏消息的反应非常迟缓。程序源代码（c语言）#includestdio.h#includestdlib.h//atoi的头文件//#includealloc.h#defineROUTNUM7//定义路由的个数为7个typedefstruct{intdis;//存延迟大小intfrom;//存下一跳的路由}RoutNode;RoutNodedata[ROUTNUM][ROUTNUM];/*路由表，能存7行7列数据,数据为权值*/voidInitData(FILE*pfile);/*从数据文件读取数据，初始化路由表*/voidOutputRoutData();/*输出所有的路由表*/voidCommunication(intrecv,intsend);/*send点向recv点发送自己的路由表*/voidExchange();/*所有节点进行一次数据交换,更新路由表*/voidmain(){intstart,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=0;iROUTNUM;i++){printf(%c||,i+65);for(j=0;jROUTNUM;j++)if(data[i][j].dis0)printf(%c%d,j+65,data[i][j].dis);printf(\n);}//显示各路由的路由表for(i=0;iROUTNUM;i++)//循环7次（好像多余，改成一次得到同样结果）{Exchange();}printf(\n路由表交换:\n);OutputRoutData();printf(输入起始路由节点数字(%d-%d)[0代表A，1代表B...]:,0,ROUTNUM-1);scanf(%d,&start);printf(输入终点路由节点数字(%d-%d)[0代表A，1代表B...]:,0,ROUTNUM-1);scanf(%d,&end);if(start==end||start0||start6||end0||end6){printf(\n输入错误，请按任意键退出\n);getch();return;}else{intcur=start;inttotal=0;if(data[start][end].dis0){printf(没有路由路径发现!\n);getch();return;}printf(%c-,cur+65);while(data[cur][end].from=0)//起始点与终点不相连。0是A{total+=data[cur][data[cur][end].from].dis;//total变成cur与下一跳的延迟printf(%c-,data[cur][end].from+65);cur=data[cur][end].from;//起始路由变成下一跳}total+=data[cur][end].dis;printf(%c\n总的路由距离=%d,end+65,total);getch();return;}}voidInitData(FILE*pfile){charnum[10];inti=0;charc;intm,n;fseek(pfile,0,0);//文件指针从距0位置0距离开始读取for(m=0;!feof(pfile)&&m7;m++)//feof(pfile),文件尾返回1，不是返回0.即不是文件尾部且m7循环.{for(n=0;!feof(pfile)&&n7;n++){while(!feof(pfile)){c=fgetc(pfile);//读取单个字节if(c==',')/*读完一个数字*/{num[i]='\0';//赋值为空data[m][n].dis=atoi(num);//atoi将字符变成数字，将路由权值给data[][].disdata[m][n].from=-1;//直接相连下一跳全都赋值为-1i=0;break;}/*endofif*/elseif((c='0'&&c='9')||c=='-')/*如果读到数字或符号.本题路由权值只能0到9*/{num[i++]=c;}/*endofelseif*/}/*endofwhile*/}/*endoffor(n=0*/}/*endoffor(m=0*/}voidOutputRoutData(){inti,j;printf();for(i=0;iROUTNUM;i++){printf(%c,i+65);}printf(\n);for(i=0;iROUTNUM;i++){printf(%c,i+65);for(j=0;jROUTNUM;j++){if(data[i][j].dis0)//如果无路径printf(-);elseif(data[i][j].dis=10)printf(%d,data[i][j].dis);elseprintf(%d,data[i][j].dis);if(data[i][j].from0)//如果未经过其它节点所以直接相连的路由下一跳为-1printf(-);elseprintf(%c,data[i][j].from+65);//输出下一跳路由}printf(\n);}}voidCommunication(intrecv,intsend)//相连的两路由recv和send交换数据计算一次得到暂时最短距离{inti;for(i=0;iROUTNUM;i++){if(data[send][i].dis0)//如果send节点到i号节点有路线{if(data[recv][i].dis0)//如果recv到i号节点无路径{data[recv][i].dis=data[send][i].dis+data[recv][send].dis;//第一种recv不予i相连，recv到不与他相连的i的延迟data[recv][i].from=send;//下一跳为send}elseif(data[recv][i].disdata[send][i].dis+data[recv][send].dis)//第二种recv与i相连，且直接相连值大于间接到i的延迟//如果现有路径比新路径远{data[recv][i].dis=data[send][i].dis+data[recv][send].dis;//将recv到i的延迟改为间接延迟的值data[recv][i].from=send;//下一跳改为send}}}}voidExchange()//实现所有相连的两路由进行数据交换并计算最短数值{inti,j;for(i=0;iROUTNUM;i++){for(j=0;jROUTNUM;j++){if(data[i][j].dis0)//如果两个节点之间有路径{Communication(j,i);//将i号节点的路由表发送给j号节点}}}}/*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,数值代表权值（如延迟大小）0代表目的网络到其本身-1代表无法直接相连*/网络拓扑结构实验结果CDAGEFB93524581分析与综述实验结果正确。起始点C下一跳为D到达E。其最短的距离为10.多次验证均正确。本实验的路由表由一个而为数组结构体实现，数组名代表两个相关路由，结构体中存放延时和下一跳。路由表初始信息从文件读取，根据距离向量路由算法系统自动完成路由表的更新操作，最后任意输入两个路由表接点，则可得出两接点之间的最短路径。所有距离矢量路由协议均使用Bellman-Ford(Ford-Fulkerson)算法，容易产生路由环路和计数到无穷大的问题。因此它们必须结合一些防环机制。距离矢量路由算法中每一个路由器都存放着整个网络的节点信息，但当一个节点发生变化时，路由不一定能很快的收敛。导致网络效率下降。适用于小型网络。