距离矢量路由算法(共7页).doc
精选优质文档-倾情为你奉上路由算法距离矢量路由算法的具体实现距离矢量路由算法的原理距离向量路由算法(Bellman-Ford Routing Algorithm)，作为距离向量协议的一个算法，如RIP, （RIP 跳 最大跳数16）BGP。使用这个算法的路由器必须掌握这个距离表，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。这个在算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量等等。概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路由器从它的相邻处收到更新信息时，它会将更新信息与本身的路由表相比较。如果该路由器比较出一条新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更新：将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距离。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。距离矢量路由算法在理论中可以工作，但在实践中有一个严重的缺陷：虽然它总是能够达到正确的答案，但是它收敛到正确答案的速度非常慢，尤其是，它对于好消息的反应非常快，但是对于坏消息的反应非常迟缓。程序源代码（c语言）#include "stdio.h"#include "stdlib.h" /atoi的头文件/#include "alloc.h"#define ROUTNUM 7 /定义路由的个数为7个typedef structint dis; /存延迟大小int from; /存下一跳的路由RoutNode;RoutNode dataROUTNUMROUTNUM;/*路由表，能存7行7列数据,数据为权值*/void InitData(FILE* pfile);/*从数据文件读取数据，初始化路由表*/void OutputRoutData();/*输出所有的路由表*/void Communication(int recv, int send);/*send点向recv点发送自己的路由表*/void Exchange();/*所有节点进行一次数据交换, 更新路由表*/void main()int start, 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; i<ROUTNUM; i+)printf("%c|", i + 65);for (j = 0; j < ROUTNUM; j+)if (dataij.dis > 0)printf("<%c %d> ", j + 65, dataij.dis);printf("n"); /显示各路由的路由表 for (i = 0; i < ROUTNUM; 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 | start < 0 | start > 6 | end < 0 | end > 6)printf("n输入错误，请按任意键退出n");getch();return;elseint cur = start;int total = 0;if (datastartend.dis < 0)printf("没有路由路径发现!n");getch();return; printf("%c->", cur + 65);while (datacurend.from >= 0) /起始点与终点不相连。0是Atotal += datacurdatacurend.from.dis; /total变成cur与下一跳的延迟printf("%c->", datacurend.from + 65);cur = datacurend.from; /起始路由变成下一跳 total += 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.即不是文件尾部且m<7循环.for (n = 0; !feof(pfile) && n < 7; n+)while (!feof(pfile)c = fgetc(pfile); /读取单个字节if (c = ',')/*读完一个数字*/numi = '0' /赋值为空datamn.dis = atoi(num);/atoi将字符变成数字，将路由权值给data.disdatamn.from = -1; /直接相连下一跳全都赋值为-1i = 0;break; /*end of if*/else if (c >= '0' && c <= '9') | c = '-') /*如果读到数字或符号.本题路由权值只能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 < 0)/如果无路径printf(" -");elseif(dataij.dis>=10)printf(" %d", dataij.dis);elseprintf(" %d", dataij.dis);if (dataij.from < 0)/如果未经过其它节点 所以直接相连的路由下一跳为-1printf(" - ");elseprintf(" %c ", dataij.from + 65); /输出下一跳路由 printf("n"); void Communication(int recv, int send) /相连的两路由recv和send交换数据计算一次得到暂时最短距离int i;for (i = 0; i < ROUTNUM; i+)if (datasendi.dis > 0)/如果send节点到i号节点有路线if (datarecvi.dis < 0)/如果recv到i号节点无路径 datarecvi.dis = datasendi.dis + datarecvsend.dis; /第一种recv不予i相连，recv到不与他相连的i的延迟datarecvi.from = send; /下一跳为sendelse if (datarecvi.dis > datasendi.dis + datarecvsend.dis)/第二种recv与i相连，且直接相连值大于间接到i的延迟/如果现有路径比新路径远datarecvi.dis = datasendi.dis + datarecvsend.dis; /将recv到i的延迟改为间接延迟的值datarecvi.from = send; /下一跳改为send void Exchange() /实现所有相连的两路由进行数据交换并计算最短数值int i, j;for (i = 0; i < ROUTNUM; i+)for (j = 0; j < ROUTNUM; j+)if (dataij.dis > 0)/如果两个节点之间有路径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)算法，容易产生路由环路和计数到无穷大的问题。因此它们必须结合一些防环机制。距离矢量路由算法中每一个路由器都存放着整个网络的节点信息，但当一个节点发生变化时，路由不一定能很快的收敛。导致网络效率下降。适用于小型网络。专心-专注-专业
