距离矢量路由算法

1、路由算法 距离矢量路由算法的具体实现 距离矢量路由算法的原理 距离向量路由算法 （Bellman-Ford Routing Algorithm） ，作为距离向量协议的一个算法， 如 RIP, （RIP 跳 最大跳数 16 ）BGP 。使用这个算法的路由器必须掌握这个距离表，它告诉在网络 中每个节点的最远和最近距离。 在距离表中的这个信息是根据临近接点信息的改变而时时更 新的。这个在算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量等等。 概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路 由器。路由表中的每一条记录都包括目标逻辑地址、 相应的网络接口和该条路

2、由的向量距离。 当一个路由器从它的相邻处收到更新信息时， 它会将更新信息与本身的路由表相比较。 如果 该路由器比较出一条新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更 新：将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距 离。在距离向量路由算法中， 相邻路由器之间周期性地相互交换各自的路由表备份。 当网络 拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。 距离矢量路由算法在理论中可以工作， 但在实践中有一个严重的缺陷： 虽然它总是能够达到 正确的答案，但是它收敛到正确答案的速度非常慢，尤其是，它对于好消息的反应非常快， 但是对于坏消息的反

3、应非常迟缓。程序源代码（ c 语言）#include stdio.h#include stdlib.h /atoi 的头文件/#include alloc.h/定义路由的个数为 7 个/存延迟大小/存下一跳的路由#define ROUTNUM 7 typedef struct int dis;int from; RoutNode;RoutNode dataROUTNUMROUTNUM;/*路由表，能存 7行 7列数据,数据为权值 */void InitData(FILE* pfile);/*从数据文件读取数据，初始化路由表*/void OutputRoutData();/* 输出所有的路由表

4、*/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 =

5、0; iROUTNUM; i+) printf(%c|, i + 65);for (j = 0; j 0) printf( , j + 65, dataij.dis); printf(n);/循环 7 次（好像多余，改成一次得到同样结果）/ 显示各路由的路由表for (i = 0; i ROUTNUM; i+) Exchange();printf(n 路由表交换 :n);OutputRoutData();printf(输入起始路由节点数字 (d-%d)O代表A, 1代表B. :, 0, ROUTNUM - 1); scanf(%d, &start);printf(输入终点路由节点数字 (d-%

6、d)O代表A, 1代表B. : , 0, ROUTNUM - 1); scanf(%d, &end);if (start = end | start 6 | end 6)printf(n 输入错误，请按任意键退出 n); getch();return;elseint cur = start;int total = 0;if (datastartend.dis , cur + 65);while (datacurend.from = 0)/起始点与终点不相连。 0 是 Atotal += datacurdatacurend.from.dis;/total 变成 cur 与下一跳的延迟printf

7、(%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);/文件指针从距for (m = 0; !feof(pfile) & m 7; m+) 即不是文件尾部且 m7 循环.0 位置 0 距离开始读取/feof(p

8、file), 文件尾返回 1，不是返回 0.for (n = 0; !feof(pfile) & n = 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

9、= 0; i ROUTNUM; i+)printf(%c , i + 65);for (j = 0; j ROUTNUM; j+)if (dataij.dis =10) printf( %d, dataij.dis);else printf( %d, dataij.dis);if (dataij.from 0)/如果未经过其它节点所以直接相连的路由下一跳为-1printf( - );elseprintf( %c , dataij.from + 65);/输出下一跳路由 printf(n);void Communication(int recv, int send)/相连的两路由 recv禾口

10、send交换数据计算一次得到暂时最短距离int i;for (i = 0; i 0)/如果 send 节点到 i 号节点有路线if (datarecvi.dis datasendi.dis + datarecvsend.dis)/ 第二种 recv 与 i 相连，且直接相连值大于间接到 i 的延迟/如果现有路径比新路径远datarecvi.dis = datasendi.dis + datarecvsend.dis;/ 将 recv 到 i的延迟改为间接延迟的值datarecvi.from = send;/下一跳改为 send/实现所有相连的两路由进行数据交换并计/如果两个节点之间有路径/ 将

11、 i 号节点的路由表发送给 j 号节点void Exchange() 算最短数值 int i, j;for (i = 0; i ROUTNUM; i+)for (j = 0; j 0)Communication(j, i); /*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代表无法直接

12、相连*/网络拓扑结构实验结果c、D：亜离矢量算法 123Debugj ul ish i I iang.exe1n ii：C!ib;：E!F!G!路由表初始:骼由表交换:A2045107畅入起始路由垃点娄 腳入终点路由常点幾C-D-E总的路由距离=106B7B88 G54-56D10 G7A0-9B10D9-11B9B0111 G8E10D1010 G7一9- 11G10G0 -3一11B8E73-0代表A, V代表B.:2-代初，1?氏表B.J : 4CDEFG分析与综述实验结果正确。起始点 C下一跳为D到达E。其最短的距离为10多次验证均正确。本实验 的路由表由一个而为数组结构体实现， 数组名代表两个相关路由， 结构体中存放延时和下一 跳。路由表初始信息从文件读取， 根据距离向量路由算法系统自动完成路