RIP协议的距离向量算法实现(c++)

原创 已于 2023-05-29 20:44:39 修改 · 8.2k 阅读 · 97 ·
CC 4.0 BY-SA版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
文章标签：

#算法 #c++ #开发语言

于 2019-06-09 13:36:17 首次发布

模拟路由表示意图

核心：

  • 新的直接进表
  • 下一跳不一样要短的
  • 下一跳一样要新的(哪怕更长)

(应用层的不是网络层的)

解释： eg:x收到相邻结点的路由表信息，则

(规定路由器直接相邻的网络距离为1)
1.先将下一跳全改为X
2.距离全部+1
3.
    3.1 新的直接进表：X路由表没有对应目的网络相同的路由信息
    3.2 下一跳相同要新的: X路由表有对应目的网络相同且下一跳相同的路由项，要新的路由项 (网络拓扑可能变化了，否则就不是坏消息传得慢了，而是压根发现不了坏消息(网络某链路坏了))
     3.3 下一跳不同要短的：X路由表有对应目的网络相同但下一跳不同的路由项，要距离短的

算法实现:

#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdio>
#include<unistd.h>
#include<sys/time.h>
using namespace std;

const int maxR=6;//最大路由器数量

//时间间隔辅助函数
typedef long long ll;
ll getNowTime(){//返回秒数
	struct timeval tv;
	struct timezone tz;
	gettimeofday(&tv,&tz);
	return tv.tv_sec;//零头的微秒忽略
}

//路由表项
struct RIP{
	char name;//本路由器名称
	int N;//到目的网络N
	int d;//距离d
	char X;//下一跳路由器
	ll time;//上次更新时间
	bool is_valid;//是否有效
	RIP(){is_valid=true;}
};

//发送的报文打包
vector<RIP> Send(vector<RIP> r,char c){
	for(int i=0;i<r.size();i++){
		r[i].d++;
		r[i].X=c;
		r[i].time=getNowTime();//时间也要更新
	}
	return r;
}

vector<RIP> rip[maxR];//路由表
char idToRname[]="ABCDEF";//int编号改为字母标号 0-A 1-B 2-C 3-D 4-E 5-F
vector<char> ve[maxR];//一个vector<RIP>包含多条记录是一个路由表 ve则可表示路由器分布图邻接表

//打印路由表
void printR(){
	vector<RIP> r;
	for(int i=0;i<maxR;i++){
		r=rip[i];
		cout<<"***********************路由表"<<idToRname[i]<<"************************\n";
		cout<<"到目的网络N\t\t距离d\t\t下一跳路由器X\n";
		for(int i=0;i<r.size();i++){
			cout<<r[i].N<<"\t\t\t"<<r[i].d<<"\t\t"<<r[i].X<<endl;
		}
	}
}

//用文件file的内容更新各个路由器
void init(char* file){
	fstream infile(file);
	if(!infile.is_open()) cout<<"未成功打开文件!"<<endl;
	int N;char name;RIP rp;
	infile>>N;
	for(int i=0;i<N;i++){//此处N和maxR设置得一样大 当然可小不可大
		infile>>name;//因为按顺序的所以不处理了
		rp.name=name;//处理下也行 不过一次处理一次就够了  冗余但安全性高了
		while(infile>>rp.N>>rp.d>>rp.X&&rp.N){
			rp.time=getNowTime();
			rip[i].push_back(rp);
		}
	}
	infile.close();
}

//用领接表初始化网络结构图
void initve(char* file){
	fstream infile(file);
	if(!infile.is_open()) cout<<"未成功打开文件!"<<endl;
	char v,v1;
	while(infile>>v){//第一个是当前结点 后面的都是当前结点的所有邻居 0表示结束
		while(infile>>v1&&v1!='0'){
			ve[v-'A'].push_back(v1);
		}
	}
	infile.close();
}

//打印图
void printG(){
	cout<<"**********************网络拓扑结构********************\n";
	for(int i=0;i<maxR;i++){
		cout<<char(i+'A')<<" ";
		for(int j=0;j<ve[i].size();j++){
			cout<<ve[i][j];
			if(j<ve[i].size()-1) cout<<" ";
		}
		cout<<endl;
	}
}

//路由表排序依据
bool cmp(RIP r1,RIP r2){
	return r1.N<r2.N;
}

//正式发送更新报文更新路由表了
bool update(){
	bool hasEdit=false;//本次更新有无修改
	vector<RIP> send;
	vector<RIP> rip1[maxR];
	for(int i=0;i<maxR;i++) rip1[i]=rip[i];//不一定赋值成功
	for(int i=0;i<maxR;i++){//遍历每个路由结点
		//rip里是本次更新前所有路由表的状态   rip1是更新过程中每个路由表的状态 
		//为了达到同时发送不产生连锁效应 故先备份新状态rip1 全部更新完毕再一次性协会rip

		//传旧的         i号结点传的
		send=Send(rip[i],i+'A');//向邻居发送的路由更新报文 i就是路由器编号 rip和ve的存储顺序一致

		for(int j=0;j<ve[i].size();j++){//遍历第i个路由器的所有邻居 目的就是更新邻居啊
			//本次给邻居ve[i][j] 一个字母 -'A'就是序号
			int lid=ve[i][j]-'A';
			for(int x=0;x<send.size();x++){//一条一条遍历发过来的更新报文 一条一条插入
				int k;
				//检查筛选时要筛选新的
				for(k=0;k<rip1[lid].size();k++){//遍历邻居路由表 查找更新报文的每一条
					//开始rip1是rip的备份 新的都写到rip1里    
					/*rip[lid]是第lid个路由表  rip[lid][k]是第lid个路由表的第k条记录*/
					if(send[x].N==rip1[lid][k].N){//有 判断逻辑:目的地址相同
						if(send[x].X==rip1[lid][k].X){//下一跳相同 要新的
							if(rip1[lid][k].d!=send[x].d){//N X d都相同  更新却无任何更改(仅仅改时间...)
								rip1[lid][k]=send[x];
								hasEdit=true;
							} 

						}else{//下一跳不同要短的
							if(send[x].d<rip1[lid][k].d){
								rip1[lid][k]=send[x];
								hasEdit=true;
							}
						}
						break;
					}
				}

				if(k==rip1[lid].size()){//没找到 是新的 直接加入
					rip1[lid].push_back(send[x]);
					hasEdit=true;
				}
			}			
		}
	}

	//一次更新完毕 才写回rip
	for(int i=0;i<maxR;i++) {
		rip[i]=rip1[i];//不一定赋值成功
		sort(rip[i].begin(),rip[i].end(),cmp);//按目的地址排序
	}
	return hasEdit;//返回本次有无更改
}

//检查有无长期未更新的路由表项
void check(){
	ll t1=getNowTime();
	for(int i=0;i<maxR;i++){
		for(int j=0;j<rip[i].size();j++){
			if(rip[i][j].is_valid&&(t1-rip[i][j].time)>180) rip[i][j].is_valid=false;//180s无更新 标记无效
			else if(!rip[i][j].is_valid&&(t1-rip[i][j].time)>120) rip[i].erase(rip[i].begin()+j);//无效后120s无更新 删除
		}
	}
}

int main(){
	// freopen("运行结果.txt","w",stdout);
	init("routes.txt");//用文件routes.txt初始化
	printR();
	initve("netGraphic.txt");//初始化网络拓扑图
	printG();
	int T=0,n=0;
	while(true){
		sleep(1);//每隔3秒更新路由表 为了演示运行结果方便不设置为30s秒了
		cout<<"\n------------------------第"<<++T<<"次更新------------------------\n";
		if(update()){//一次更新
			printR();//打印路由表
			n++;
		}else{
			cout<<"本次没有任何有价值的修改!说明前面"<<n<<"次修改后,每一个路由器都得到了全局路由信息!\n";
		}
		check();
	}
	return 0;
}

文件:

netGraphic.txt 网络拓扑图 0代表一行结束

A B D E 0
B A C 0
C B F 0
D A E F 0
E A D F 0
F C D E 0

routes.txt 各个路由表初始状态

6

A
1 1 -
2 1 -
3 1 -
0 0 0

B
3 1 -
4 1 -
0 0 0

C
4 1 -
6 1 -
0 0 0

D
2 1 -
5 1 -
0 0 0

E
1 1 -
5 1 -
0 0 0

F
5 1 -
6 1 -
0 0 0

#第一个数字N表示路由器个数
#N组，每组表示一个路由器表项 每个路由器表项中目的网络为0表示此路由器结束

3个文件要放在同一个文件夹下执行

运行结果:

***********************路由表A************************
到目的网络N		距离d		下一跳路由器X
1				1			-
2				1			-
3				1			-
***********************路由表B************************
到目的网络N		距离d		下一跳路由器X
3				1			-
4				1			-
***********************路由表C************************
到目的网络N		距离d		下一跳路由器X
4				1			-
6				1			-
***********************路由表D************************
到目的网络N		距离d		下一跳路由器X
2				1			-
5				1			-
***********************路由表E************************
到目的网络N		距离d		下一跳路由器X
1				1			-
5				1			-
***********************路由表F************************
到目的网络N		距离d		下一跳路由器X
5				1			-
6				1			-
**********************网络拓扑结构********************
A B D E
B A C
C B F
D A E F
E A D F
F C D E

------------------------第1次更新------------------------
***********************路由表A************************
到目的网络N		距离d		下一跳路由器X
1				1			-
2				1			-
3				1			-
4				2			B
5				2			D
***********************路由表B************************
到目的网络N		距离d		下一跳路由器X
1				2			A
2				2			A
3				1			-
4				1			-
6				2			C
***********************路由表C************************
到目的网络N		距离d		下一跳路由器X
3				2			B
4				1			-
5				2			F
6				1			-
***********************路由表D************************
到目的网络N		距离d		下一跳路由器X
1				2			A
2				1			-
3				2			A
5				1			-
6				2			F
***********************路由表E************************
到目的网络N		距离d		下一跳路由器X
1				1			-
2				2			A
3				2			A
5				1			-
6				2			F
***********************路由表F************************
到目的网络N		距离d		下一跳路由器X
1				2			E
2				2			D
4				2			C
5				1			-
6				1			-

------------------------第2次更新------------------------
***********************路由表A************************
到目的网络N		距离d		下一跳路由器X
1				1			-
2				1			-
3				1			-
4				2			B
5				2			D
6				3			B
***********************路由表B************************
到目的网络N		距离d		下一跳路由器X
1				2			A
2				2			A
3				1			-
4				1			-
5				3			A
6				2			C
***********************路由表C************************
到目的网络N		距离d		下一跳路由器X
1				3			B
2				3			B
3				2			B
4				1			-
5				2			F
6				1			-
***********************路由表D************************
到目的网络N		距离d		下一跳路由器X
1				2			A
2				1			-
3				2			A
4				3			A
5				1			-
6				2			F
***********************路由表E************************
到目的网络N		距离d		下一跳路由器X
1				1			-
2				2			A
3				2			A
4				3			A
5				1			-
6				2			F
***********************路由表F************************
到目的网络N		距离d		下一跳路由器X
1				2			E
2				2			D
3				3			C
4				2			C
5				1			-
6				1			-

------------------------第3次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

------------------------第4次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

------------------------第5次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

------------------------第6次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

------------------------第7次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

------------------------第8次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

------------------------第9次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

------------------------第10次更新------------------------
本次没有任何有价值的修改!说明前面2次修改后,每一个路由器都得到了全局路由信息!

【软考中级网络工程师】知识点之 RIP 协议
邓邓子的博客
08-03 1293
本文围绕软考中级网络工程师必备的 RIP 协议展开，先概述其作为基于距离矢量算法的内部网关协议，及应用场景与考试重要性。接着详解工作原理，包括算法、更新机制等，还介绍报文格式、版本差异。同时阐述计时器、防环机制、配置示例，分析优缺点。旨在助考生全面掌握 RIP 协议核心知识，应对考试及实际应用。
RIP协议的距离向量算法--C++
01-17 1566
RIP协议的距离向量算法--C++ #include#include#include#include#includeusing namespace std; //路由表中数据class Table{   public:string destination_id;int distance;string next_stop;}; //路由类class Route{        
RIP协议路由表调整算法的实现-c++编写
05-23
RIP协议路由表调整算法的实现__c++编写，作为一个课程设计做的，有需要的可以看下
路由表计算——RIP协议 距离向量算法
宋宋丶的博客
01-06 1万+
一、RIP简介 RIP(Routing Information Protocol,路由信息协议）是一种内部网关协议（IGP），是一种动态路由选择协议，用于自治系统（AS）内的路由信息的传递。RIP协议基于距离矢量算法（DistanceVectorAlgorithms），使用“跳数”(即metric)来衡量到达目标地址的路由距离。 二、距离向量算法 1.距离（跳数）问题 （1）从一个路由器到直接连接的路由器距离定义为1 （2）从一个路由器到另一个非直接相连的路由器距离定义为所经过路由器的个数加.
计算机网络路由算法
12-24
这是用C语言实现的代码，计算机网络距离矢量路由算法，可随机生成拓扑图，多次交换路由表。
内部网关协议RIP 距离向量算法
youthpasses的专栏
02-08 1181
网络拓扑结构： A、B、C、D为路由器，1、2、3、4、5为网络 采用邻接表 胡乱一写，代码相当冗余，也没对某些方法进行封装 #include "stdio.h" #include typedef struct RouNode { char router; struct RouNode *nextrou; } RouNode; void main() { //声明并
基于距离向量算法的rip协议的实现
05-02
尽管有这些局限，RIP仍然是学习路由协议和距离向量算法的良好起点，其简单性和清晰的原理有助于理解和实践网络路由的基本概念。在实际的大型网络中，通常会使用更先进的协议，如OSPF（Open Shortest Path First）或...
C++实现基于距离向量算法的RIP协议详解
基于距离向量算法的RIP协议实现是一个深入探讨网络协议和路由算法的经典主题。RIP（Routing Information Protocol）路由信息协议是一种使用距离向量算法的内部网关协议（IGP），它主要用于小型到中型的网络环境中。...
C++实现基于距离向量算法的RIP协议
在进行基于距离向量算法的RIP协议实现时，涉及到计算机网络的基础知识，主要包括： 1. 路由协议的分类：静态路由协议和动态路由协议。静态路由是通过手动配置进行路由选择的，而动态路由协议允许路由器自动交换信息...
基于距离向量算法的ｒｉｐ协议的实现
11-11
【标题】基于距离向量算法的ｒｉｐ协议的实现 在计算机网络中，路由协议是网络设备之间交换路由信息的基础，它使得数据能够在不同网络间有效地传输。RIP（Routing Information Protocol，路由信息协议）是一种广泛...
计算机网络课程设计报告-RIP协议路由表调整算法的实现.doc
03-27
总结，这个课程设计项目通过C++编程实现了RIP协议的关键部分，即路由表的调整和更新，帮助理解距离向量路由算法的工作原理。在实际网络环境中，理解并掌握这些基本路由协议对于网络管理员和IT专业人员来说是至关重要...
RIP协议编程
12-29
RIP协议编程 ，里面有路由表的转发，是基于距离向量算法的，挺不错的
C++实现的距离矢量路由算法
02-17
用C++来模拟网络中的距离矢量路由算法（即D-V算法）
c编写的RIP协议源程序
07-02
用C写的rip协议 这是其中的广播request程序片段： void RouteInit() { int i,optval=0,length,error; routeNum = 0; // init local socket address and ip address GetLocalIP(); // init route table items for(i = 0; i < MAX_NUM; i++) { SetRouteEntry(&routeTable[i].routeInfo,"0.0.0.0",0,0); routeTable[i].isvalid = 0; routeTable[i].timer = 0; routeTable[i].statue = 0; inet_aton("0,0,0,0",&routeTable[i].sourceIPAddr); } // init request packet SetRoutePacket(&reqPacket,REQUEST); SetRouteEntry(&reqPacket.routeEntry[0],"0.0.0.0",0,16); // init response packet SetRoutePacket(&resPacket,RESPONSE); recvSockAddr.sin_family = AF_INET; recvSockAddr.sin_port = htons(PORT); recvSockAddr.sin_addr.s_addr = htonl(INADDR_ANY); sendSockAddr.sin_family = AF_INET; sendSockAddr.sin_port = htons(PORT); // inet_aton("240.255.255.255",&sendSockAddr.sin_addr); sendSockAddr.sin_addr.s_addr = htonl(INADDR_ANY); EntryInit(); sock = socket(AF_INET,SOCK_DGRAM,0); if(sock<0) { printf("cannot create a socket!\n"); exit(1); } if(setsockopt(sock,SOL_SOCKET,SO_BROADCAST,&optval,sizeof(int)) != 0) { printf("cannot broadcast!\n"); close(sock); exit(1); } if(bind(sock,(struct sockaddr*)&recvSockAddr,sizeof(recvSockAddr))<0) { printf("cannot bind to port\n"); close(sock); exit(1); } length=sizeof recvSockAddr; getsockname(sock,(struct sockaddr*)&recvSockAddr,&length); printf("Port %d is opened. Listen for packet...\n",ntohs(recvSockAddr.sin_port)); FD_ZERO(&fdSet); FD_SET(sock,&fdSet); error = sendto(sock,&reqPacket,4+sizeof(struct ROUTE_ENTRY),0,(struct sockaddr*)(&sendSockAddr),sizeof(struct sockaddr)); if(error<0) { PrintEntry(&reqPacket.routeEntry[0]); printf("broadcast request packet failed! %d,%d,%d\n",error,sock,fdSet); } }
距离向量路由协议模拟程序（Java）
07-08
Java平台上的距离向量路由协议的模拟程序。提供给定的配置文件（ConfigA.txt，包含相邻路由的端口号和距离）时，自动计算出网络中到达各个路由的距离。当路由挂起或关闭时，其它路由可以检测到路由点的消失并重新计算距离
rip协议 java实现
06-20
在计算机网络实验课程结束后，老师要求熟悉rip协议的一些简单规则，并用代码实现
RIP协议及距离向量算法（详解）
热门推荐
zep
06-05 3万+
一、路由选择协议分类回顾 二、RIP协议 RIP是一种分布式的基于距离向量的路由选择协议，是因特网的协议标准，最大优点是简单。 RIP协议要求网络中每一个路由器都维护从它自己到其他每一个目的网络的唯一最佳距离记录（即一组距离）。距离：通常为“跳数”，即从源端口到目的端口所经过的路由器个数，经过一个路由器跳数+1。特别的，从一路由器到直接连接的网络距离为1。RIP允许一条路由最多只能包含15个路由器，因此距离为16表示网络不可达。 所以说，RIP协议只适用于小互联网。 三、RIP协议和谁交换？多久交换
RIP距离向量算法
suzathlan的博客
02-06 4807
基本概况 编辑 RIP协议采用距离向量算法，在实际使用中已经较少适用。在默认情况下，RIP使用一种非常简单的度量制度：距离就是通往目的站点所需经过的链路数，取值为1~15，数值16表示无穷大。RIP进程使用UDP的520端口来发送和接收RIP分组。RIP分组每隔30s以广播的形式发送一次，为了防止出现“广播风暴”，其后续的的分组将做随机延时后发送。在RIP中，如果一个路由在180s内未被刷，则相
计算机网络——RIP协议：距离向量算法
最新发布
Hacker_xingchen的博客
01-17 923
由于11＞7+1=8，此时R1经过R2到达目的网络20.0.0.0的路由距离变短了，因此R1要根据R2提供的数据，修改相应路由项的距离值为8(即7+1)。由于9=8+1，显然R1经过R2到达目的网络30.0.0.0，并不能得到更短的路由距离，因此R1无须进行更新操作，将保持该路由条目原来的参数。②如果R1的路由表中的某项路由记录比R2发送的对应项的距离值加1还要大，则R1在路由表中修改该项，距离值根据R2提供的值加1,否则——R1无须进行更新操作，将保持该R1路由表原来的参数。R1起始路由表如表1所示。
评论 8
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值