实验一：距离矢量路由算法
1实验目的
通过编程模拟距离矢量路由算法，了解距离矢量路由算法是如何工作的。
2实验内容
编程实现距离矢量路由算法的路由表交换过程，并显示出每轮交换过后路由表的各路由变化情况，得到各最佳路线。
3实验原理
网络层的主要功能是将分组从远端机器经选定的路由送到目的端机器。路由选择算法和它们使用的数据结构是网络层设计的一个主要区域。负责确定所收到分组应传送的外出路线。
距离矢量路由算法的工作原理：每个路由器维护一张表（即一个矢量），表中列出了当前已知的到每个目标的最佳距离，以及所使用的线路。通过在邻居之间相互交换信息，路由器不断地更新它们内部的表。
在距离矢量路由算法中，每个路由器维护了一张路由表，它以子网中的每个路由器为索引，并且每个路由器对应一个表项。
该表项包含两部分：为了到达该目标路由器而首先使用的输出线路，以及到达该目标路由器的时间估计值或距离估计值。
距离矢量路由算法在理论中可以工作，但在实践中有一个严重的缺陷：虽然它总是能够达到正确的答案，但是它收敛到正确答案的速度非常慢，尤其是，它对于好消息的反应非常快，但是对于坏消息的反应非常迟缓。
4实验步骤
4.1编写程序
程序的C语言源代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include "stdio.h" #include "stdlib.h" //atoi的头文件 //#include "alloc.h" #define ROUTNUM 7 //定义路由的个数为7个 typedef struct { int dis; //存延迟大小 int from; //存下一跳的路由 }RoutNode; RoutNode data[ROUTNUM][ROUTNUM]; //路由表，能存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; } else printf("\n路由表初始:\n"); InitData(pfile); fclose(pfile); for (i = 0; i<ROUTNUM; i++) { printf("%c||", i + 65); for (j = 0; j < ROUTNUM; j++) if (data[i][j].dis > 0) printf("<%c %d> ", j + 65, data[i][j].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; } else { int cur = start; int total = 0; if (data[start][end].dis < 0) { 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; } } void InitData(FILE *pfile) { char num[10]; 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 == ',') /*读完一个数字*/ { num[i] = '\0'; //赋值为空 data[m][n].dis = atoi(num);//atoi将字符变成数字，将路由权值给data[][].dis data[m][n].from = -1; //直接相连下一跳全都赋值为-1 i = 0; break; } /*end of if*/ else if ((c >= '0' && c <= '9') || c == '-') /*如果读到数字或符号.本题路由权值只能0到9*/ { num[i++] = 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 (data[i][j].dis < 0) //如果无路径 printf(" -"); else if(data[i][j].dis>=10) printf(" %d", data[i][j].dis); else printf(" %d", data[i][j].dis); if (data[i][j].from < 0) //如果未经过其它节点 所以直接相连的路由下一跳为-1 printf(" - "); else printf(" %c ", data[i][j].from + 65); //输出下一跳路由 } printf("\n"); } } void Communication(int recv, int send) //相连的两路由recv和send交换数据计算一次得到暂时最短距离 { int i; for (i = 0; i < ROUTNUM; i++) { if (data[send][i].dis > 0) //如果send节点到i号节点有路线 { if (data[recv][i].dis < 0) //如果recv到i号节点无路径 { data[recv][i].dis = data[send][i].dis + data[recv][send].dis; //第一种recv不予i相连，recv到不与他相连的i的延迟 data[recv][i].from = send; //下一跳为send } else if (data[recv][i].dis > data[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 } } } } void Exchange() //实现所有相连的两路由进行数据交换并计算最短数值 { int i, j; for (i = 0; i < ROUTNUM; i++) { for (j = 0; j < ROUTNUM; j++) { if (data[i][j].dis > 0) //如果两个节点之间有路径 { Communication(j, i); //将i号节点的路由表发送给j号节点 } } } } |
4.2设计思路
程序先定义了一个路由表——RoutNode data[ROUTNUM][ROUTNUM]，路由表的初始信息存储在文件中，程序运行是先调用函数InitData(FILE* pfile)从文件中读取路由表的初始信息，然后输出初始路由表的信息，Communication(int recv, int send)函数主要是向邻近节点发送自己的路由表信息，Exchange()函数则根据新路由表信息更新自己的路由表。当所有的路由表节点都更新一遍后，整个路由表更新完毕。
5实验结果分析
5.1运行部分结果如下图所示：
A到D的路径
C到G的路径
5.2结果分析
路由表初始信息从txt文件读取，完成路由表初始化，然后根据距离向量路由算法完成路由表的更新操作，得到各路由情况，最后任意输入两个路由表接点，则可得出两接点之间的最短路径。
6实验心得体会
距离矢量路由算法作为常见的动态算法，通过该实验加深了对网络层距离矢量路由算法的理解，明白了路由表之间如何交换，同时也提高了动手操作能力。
1实验目的
模拟实现数据链路层后退n帧协议（协议五）。
2实验内容
要求理解链路层后退n帧协议原理，编程动态实现数据链路层后退n帧协议。
3实验原理
数据链路层除了下次该交给网络层的下一帧外，拒绝接收其它任何帧。
后退N协议一方面因连续发送数据帧而提高了效率，但另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传（仅因这些数据帧之前有一个数据帧出了错），这种做法又使传送效率降低。由此可见，若传输信道的传输质量很差，因而误码率较大时，连续传送协议不一定优于停止-等待协议。此协议中的发送窗口的大小大于1，接收窗口大小为1。
4实验步骤
4.1编写程序
程序C语言源代码如下（Turbo c下实现）：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 |
include "stdio.h" #include "string.h" #include "time.h" #include "conio.h" #include "graphics.h" #define N_BACKE 2 #define LEN sizeof(struct Frame) int randm(int, int); int t; int g_seq = 1; int g_pos = 0; struct Frame { int err; //出错标志 int out; //发送标志 int seq; int clock; int ack; int count; //传输次数 struct Frame *next; }*sd, *re; typedef struct Frame Fra; void Insert(Fra **, Fra *); void init() //初始化就绪、阻塞、完成队列 { sd = NULL; re = NULL; } void delay(int a) //时间延迟函数，用于实现数据帧的动态变化 { clock_t start = clock(); //系统时间函数 while (clock() - a * CLK_TCK <= start); } void Creat() //创建数据帧 { Fra *p = (Fra *)malloc(LEN); p->count = 0; p->out = 0; //已经发送标志 p->seq = g_seq; //帧序号 p->clock = N_BACKE; //最大后退次数 p->ack = 0; //接受确认 if (p->seq % t == 0) p->err = 1; //出错标志 else p->err = 0; p->next = NULL; Insert(&sd, p); g_seq++; } void Insert(Fra **v, Fra *p) //将数据帧插入到V队列中 { Fra *q; q = *v; if (*v == NULL) { q = p; *v = q; } else { while (q->next != NULL) q = q->next; q->next = p; } } void send(Fra *p) //发送数据帧 { char str[10]; p->out = 1; if (p->err == 0) //发送未出错 { p->ack = 1; setfillstyle(1, 4); //设置填充模式，用4号颜色—红表示正确发送 setcolor(1); circle(50 + 25 * p->seq, 150, 10); //*画圆圈表示数据帧 floodfill(50 + 25 * p->seq, 150, 1); setcolor(2); itoa(p->seq, str, 10); outtextxy(45 + 25 * p->seq, 146, str); //显示帧的编号 if (p->count > 0) { setfillstyle(1, 5); setcolor(1); circle(50 + 25 * p->seq, 300, 10); floodfill(50 + 25 * p->seq, 300, 1); setcolor(2); itoa(p->seq, str, 10); outtextxy(45 + 25 * p->seq, 296, str); } } else //发送出错 { setfillstyle(1, 7); //用7号颜色表示错误的发送 setcolor(1); circle(50 + 25 * p->seq, 150, 10); floodfill(50 + 25 * p->seq, 150, 1); setcolor(4); itoa(p->seq, str, 10); outtextxy(45 + 25* p->seq, 146, str); if (p->count > 0) { setfillstyle(1, 5); setcolor(1); circle(50 + 25 * p->seq, 300, 10); floodfill(50 + 25 * p->seq, 300, 1); setcolor(2); itoa(p->seq, str, 10); outtextxy(45 + 25 * p->seq, 296, str); } } p->count++; } void back_send(Fra **v) //检查超时未确认的帧 { char str[10]; int pos; Fra *p; p = *v; while (p != NULL) { if (p->ack == 0 && p->clock == 0) //超时未发，取得该帧标号 { g_pos = p->seq; break; } else if (p->out == 1) p->clock -= 1; p = p->next; } } Fra *search(Fra **v, int num) //查找未确认帧对应的指针 { Fra *p; p = *v; while (p != NULL) { if (p->seq == num) return p; else p = p->next; } } int randm(int x, int y) //随机数函数 { int k; k = rand() % (x - y) + x; return k; } print(Fra **v) //在屏幕上显示帧序列 { int size; char str[10]; void *buff; Fra *p; p = *v; while (p != NULL) { setfillstyle(1, 7); setcolor(1); circle(50 + 25 * p->seq, 300, 10); floodfill(50 + 25 * p->seq, 300, 1); setcolor(4); itoa(p->seq, str, 10); outtextxy(45 + 25 * p->seq, 296, str); p = p->next; } size = imagesize(65, 290, 85, 310); buff = malloc(size); getimage(65, 290, 85, 310, buff); p = *v; while (!kbhit()) { putimage(40 + 25 * p->seq, 140, buff, COPY_PUT); delay(1); send(p); back_send(&sd); if (g_pos != 0) { p = (*search)(&sd, g_pos); if (p->seq % t == 0) p->err = 0; } else p = p->next; delay(1); g_pos = 0; } } void main() { int i, j; int driver = DETECT, mode; initgraph(&driver, &mode, ""); cleardevice(); srand((unsigned)time(NULL)); t = randm(5,7); for (i = 0; i < 20; i++) { Creat(); } print(&sd); getch(); } |
4.2设计思路
本程序首先用Creat()函数创建了若干的数据帧，创建完毕后调用send(Fra *p)函数依次发送创建好的若干个数据帧，同时每发送一个帧就检查前面发送的帧是否有超时未被确认的，此功能由函数back_send(Fra **v)来完成。若发现有超时未发则返回超时帧的序列号seq，同时根据seq调用超时帧查找函数*search(Fra **v, int num)找到该帧位置，从该位置起全部从发后面的帧，即后退N帧协议。
5实验结果分析
5.1运行结果如下图所示
5.2结果分析
根据后退N帧协议，当第5号帧发生错误时，第5、6、7帧全部重传（时间间隔为2个周期）。
6实验心得体会
通过该实验对协议五如何运行有了了解，即数据链路层除了下次该交给网络层的下一帧外，拒绝接收其它任何帧。同时也对其他滑动窗口协议有了更深的掌握，实验达到预期目的。
文章评论