路由器查表过程模拟Word格式.docx
《路由器查表过程模拟Word格式.docx》由会员分享，可在线阅读，更多相关《路由器查表过程模拟Word格式.docx（45页珍藏版）》请在冰点文库上搜索。
1
2012.6.11
开会分析讨论，作工作分工
史言负责对小组成员进行分工
2
6.12~6.12
作具体分析，查询相关资料
3
6.13~6.15
编写源代码
4
6.16~6.17
对源程序进行调试
5
6.18~6.22
写课程设计报告
6
6.23~~6.24
与老师交流，完善报告，并打印
教研室审核意见：
教研室主任签字：
年月日
课程设计任务书
课程设计的主要内容
1引言
随着计算机信息技术的发展，大规模的互联网逐渐流行起来，也为路由器的发展提供了良好的基础和平台。
作为不同网络之间互相连接的枢纽，路由器系统构成了基于TCP/IP的国际互联网络Internet的主体脉络。
然而如何准确的发送并接受信息，则需要通过路由表的准确查找，路由表存储着指向特定网络地址的路径（在有些情况下，还记录有路径的路由度量值）。
通过路由表查找过程的设计与模拟可以更好的体现路由的选择，帮助我们准确的理解路由的选择过程。
2需求分析
2.1设计目的
该程序主要是用来模拟路由器中路由查找的过程。
当主机向目的网络发送一个数据包时，对每一个IP包，当发送到一个网络拓扑中的时候，可以分别使用RIP或OSPF协议，来决定数据包通过互联网络的路径。
通过模拟算法的实现，我们可以模拟一个简单的路由查找过程，进而找出最优路径，实现路由的查找
2.2设计主要内容及要求
2.2.1设计内容
1．rip：
距离向量路由协议，距离向量路由协议的特征是它在进行路由更新时，会发送路由表的全部或一部分给邻居路由器（这台邻居路由器也必须运行rip协议），当路由信息通过这种方式扩散到整个自治系统时，每个路由器会根据Dijkstra算法计算出到达每个网段的最优路径，rip选择到达某个网络的最优路径根据跳数。
数据包经过一个路由器就是一跳。
2．ospf：
路由器的路由选择是基于链路状态，通过Dijkastra算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。
最后再通过计算域间路由、自治系统外部路由确定完整的路由表。
与此同时，OSPF动态监视网络状态，一旦发生变化则迅速扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由表。
因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。
这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表，而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。
2.2.2设计要求
任意两个节点，分别在rip和ospf协议的前提条件下，根据相应的算法找出最优路径。
在rip协议中，所有的路由都由跳数来描述，到达目的地的路由最大不超过16跳，且只保留唯一的一条路由，这就限制了RIP的服务半径，即其只适用于小型的简单网络。
同时，运行RIP的路由器需要定期地（一般30s）将自己的路由表广播到网络当中，达到对网络拓扑的聚合，这样不但聚合的速度慢而且极容易引起广播风暴、累加到无穷、路由环致命等问题。
为此，OSPF应运而生。
OSPF是基于链路状态的路由协议，它克服了RIP的许多缺陷：
第一，OSPF不再采用跳数的概念 第二，OSPF支持不同服务类型的不同代价，从而实现不同QoS的路由服务；
第三，OSPF路由器不再交换路由表，而是同步各路由器对网络状态的认识，即链路状态数据库，然后通过Dijkstra最短路径算法计算出网络中各目的地址的最优路由。
2.2.3使用环境及语言
编程环境：
MicrosoftVisualC++6.0
编写语言：
C++语言
3概要设计
3.1基本功能描述
3.1.1路由表的结构
标准的路由表表目是一个二维组（目的网络地址，下一站地址），其中不携带子网信息，不能满足子网寻径。
引入子网编址以后，路由表的每一表目中加入子网掩码，于是路由表表目变为三维组：
子网掩码、目的网络地址、下一站地址。
表1路由表结构及使用
目的地址
掩码
下一跳地址
0.0.0.0
10.0.0.1
100.0.0.0
255.255.255.0
20.0.0.1
200.0.0.0
30.0.0.1
路由器依据路由表来为报文寻径，路由表由路由协议建立和维护。
路由协议的设计则是依据某种路由算法。
路由器提供了将异构网互联的机制，实现将一个数据包从一个网
络发送到另一个网络。
路由就是指导IP数据包发送的路径信息
3.1.2路由表的作用
路由器的主要工作就是为经过路由器的每个数据帧寻找一条最佳传输路径，并将该数据有效地传送到目的站点。
由此可见，选择最佳路径的策略即路由算法是路由器的关键所在。
为了完成这项工作，在路由器中保存着各种传输路径的相关数据——路由表（RoutingTable），供路由选择时使用。
打个比方，路由表就像我们平时使用的地图一样，标识着各种路线，路由表中保存着子网的标志信息、网上路由器的个数和下一个路由器的名字等内容。
路由表可以是由系统管理员固定设置好的，也可以由系统动态修改，可以由路由器自动调整，也可以由主机控制。
3.1.3路由表中路由的来源
在路由表中有一个Protocol字段，指明了路由的来源，即路由是如何生成的。
链路层协议发现的路由（Direct）它的特点是开销小，配置简单，无需人工维护，只能发现本接口所属网段拓扑的路由。
手工配置的静态路由（Static）静态路由是一种特殊的路由，它由管理员手工配置而成。
通过静态路由的配置可建立一个互通的网络，但这种配置问题在于：
当一个网络故障发生后，静态路由不会自动修正，必须有管理员的介入。
静态路由无开销，配置简单，适合简单拓扑结构的网络。
动态路由协议发现的路由（RIP、OSPF等）当网络拓扑结构十分复杂时，手工配置静态路由工作量大而且容易出现错误，这时就可用动态路由协议， 动态（Dynamic）路由表是路由器根据网络系统的运行情况而自动调整的路由表。
路由器根据路由选择协议（RoutingProtocol）提供的功能，自动学习和记忆网络运行情况，在需要时自动计算数据传输的最佳路径。
让其自动发现和修改路由，无需人工维护，但动态路由协议开销大，配置复杂。
3.2IP路由选择
路由器通常依靠所建立及维护的路由表来决定如何转发。
路由表能力是指路由表内所容纳路由表项数量的极限。
3.2.1通过RIP（路由信息协议）来实现路由选择
RIP（RoutinginformationProtocol，路由信息协议）是应用较早、使用较普遍的内部网关协议（InteriorGatewayProtocol，IGP），适用于小型同类网络的一个自治系统（AS）内的路由信息的传递。
RIP协议是基于距离矢量算法（DistanceVectorAlgorithms，DVA）的。
它使用“跳数”，即metric来衡量到达目标地址的路由距离。
它是一个用于路由器和主机间交换路由信息的距离向量协议，目前最新的版本为v4，也就是RIPv4。
1.RIP的工作原理
RIP是一种距离矢量路由协议RIP使用跳数作为路由选择的度量。
当在进行路由选择是，路由表会根据最小跳数来决定转发的路径RIP用“路程段数”（即“跳数”）作为网络距离的尺度。
每个路由器在给相邻路由器发出路由信息时，都会给每个路径加上内部距离。
在如图3-1中，路由器3直接和网络C相连。
当它向路由器2通告网络142.10.0.0的路径时，它把跳数增加1。
与之相似，路由器2把跳数增加到“2”，且通告路径给路由器1，则Route1和Route0与Route2所在网络172.16.0.0的距离分别是1跳、2跳。
图3-1rip的工作原理事例
2.RIP报文的格式
对于RIP报文有两种版本的格式，Version1和Version2。
两种报文稍有不同，如图3-2所示：
图3-2rip报文的两种版本格式
在一开始，所有路由器中的路由表只有路由器所接入的网络（共有两个网络）的情况。
现在的路由表增加了一列，这就是从该路由表到目的网络上的路由器的“距离”。
在图中“下一站路由器”项目中有符号“－”，表示直接交付。
这是因为路由器和同一网络上的主机可直接通信而不需要再经过别的路由器进行转发。
同理，到目的网络的距离也都是零，因为需要经过的路由器数为零。
图中粗的空心箭头表示路由表的更新，细的箭头表示更新路由表要用到相邻路由表传送过来的信息。
接着，各路由器都向其相邻路由器广播RIP报文，这实际上就是广播路由表中的信息。
假定路由器R2先收到了路由器R1和R3的路由信息，然后就更新自己的路由表。
更新后的路由表再发送给路由器R1和R3。
路由器R1和R3分别再进行更新。
3.2.2通过OSPF（开放最短路径优先）来实现路由选择
OSPF是一种分层次的路由协议，其层次中最大的实体是AS（自治系统），即遵循共同路由策略管理下的一部分网络实体。
在每个AS中，将网络划分为不同的区域。
每个区域都有自己特定的标识号。
对于主干（backbone）区域，负责在区域之间分发链路状态信息。
这种分层次的网络结构是根据OSPF的实际提出来的。
当网络中自治系统非常大时，网络拓扑数据库的内容就更多，所以如果不分层次的话，一方面容易造成数据库溢出，另一方面当网络中某一链路状态发生变化时，会引起整个网络中每个节点都重新计算一遍自己的路由表，既浪费资源与时间，又会影响路由协议的性能（如聚合速度、稳定性、灵活性等）。
OSPF的设计实现要涉及到指定路由器、备份指定路由器的选举、协议包的接收、发送、泛洪机制、路由表计算等一系列问题。
本文仅就Dijkstra算法与路由表的计算进行讨论。
3.2.3Dijkstra算法
Dijkstra算法是路由表计算的依据，通过Dijkstra算法可以得到有关网络节点的最短路径树，然后由最短路径优先树得到路由表。
1.Dijkstra算法的描述
初始化集合E，使之只包含源节点S，并初始化集合R，使之包含所有其它节点。
初始化路径列O，使其包含一段从S起始的路径。
这些路径的长度值等于相应链路的量度值，并以递增顺序排列列表O.
若列表O为空，或者O中第1个路径长度为无穷大，则将R中所有剩余节点标注为不可达，并终止算法。
首先寻找列表O中的最短路径P，从O中删除P.设V为P的最终节点。
若V已在集合E中，继续执行步骤2.否则，P为通往V的最短路径。
将V从R移至E.
建立一个与P相连并从V开始的所有链路构成的侯选路径集合。
这些路径的长度是P的长度加上与P相连的长度。
将这些新的链路插入有序表O中，并放置在其长度所对应的等级上。
继续执行步骤2.
2.Dijkstra算法举例
以路由器A为例，来说明最短路径树的建立过程：
1）路由器A找到了路由器B、C，将它们列入候选列表.
（2）从候选列表中找出最小代价项B，将B加入最短路径树并从候选列表中删除。
接着从B开始寻找，找到了D，将其放入候选列表.（3）从列表中找出C，再由C又找到了D.但此时D的代价为4，所以不再加入候选列表。
最后将D加入到最短路径树。
此时候选列表为空，完成了最短路径树的计算。
3.OSPF路由表的计算与实现
有关路由表的计算是OSPF的核心内容，它是动态生成路由器内核路由表的基础。
在路由表条目中，应包括有目标地址、目标地址类型、链路的代价、链路的存活时间、链路的类型以及下一跳等内容。
关于整个计算的过程，主要由以下五个步骤来完成
保存当前路由表，当前存在的路由表为无效的，必须从头开始重新建立路由表；
域内路由的计算，通过Dijkstra算法建立最短路径树，从而计算域内路由；
域间路由的计算，通过检查Summary-LSA来计算域间路由，若该路由器连到多个域，则只检查主干域的Summary-LSA；
查看Summary-LSA：
在连到一个或多个传输域的域边界路由器中，通过检查该域内的Summary-LSA来检查是否有比第
（2）（3）步更好的路径；
AS外部路由的计算，通过查看AS-External-LSA来计算目的地在AS外的路由。
通过以上步骤，OSPF生成了路由表。
但这里的路由表还不同于路由器中实现路由转发功能时用到的内核路由表，它只是OSPF本身的内部路由表。
因此，完成上述工作后，往往还要通过路由增强功能与内核路由表交互，从而实现多种路由协议的学习。
OPSF作为一种重要的内部网关协协议的普遍应用，极大地增强了网络的可扩展性和稳定性，同时也反映出了动态路由协议的强大功能。
⒋详细设计
4.1各模块的伪码算法
4.1.1RIP
1.定义存储类型的三个类：
（1）网段类，包含相邻弧的信息（不用route_f，用next）,也可用于存储文件读入信息（用route_f，不用next）
public:
stringnet_id;
stringroute_f;
stringroute_n;
Net_sec*next;
};
（2）路由类相当于头结点
classRoute{
stringroute;
Net_sec*next;
classNet_sec{
（3）路由表内容类
classContents{
intdiatance;
stringnext_stop;
2.路由表和网段类
在路由表网段类中定义了多个函数。
voidopen_file（ifstream&
infile）打开文件函数。
Route_net（）类的构造函数用来表示网络拓扑的邻接状况，booljudge（stringstr）函数判断一个路由是否已为其添加了路由表，voidInit_routes（）初始化路由表，voidshow（）显示各路由表，voidchange（inti）对相邻路由表change一下，距离加1，下一跳变为该路由名字，voidupdate（inti）对一个路由进行更新操作，voidUPDATE（）对所有路由进行更新路由表操作，boolneighbor（inti,intj）判断两路由是否相邻。
在类中还定义了一些私有的成员变量。
（1）Route_net类的伪码段：
classRoute_net{
voidopen_file（ifstream&
infile）;
Route_net（）;
//构造函数
booljudge（stringstr）;
voidInit_routes（）;
voidshow（）;
voidchange（inti）;
voidupdate（inti）;
voidUPDATE（）;
boolneighbor（inti,intj）;
//j和i相邻吗
private:
list<
Net_sec>
li;
//读取信息存储在这
Routeroute[MAX];
//存储图的信息，即各路由的邻接表
Contents>
routes[MAX];
//存储各路由路由表
temp;
//用于存储处理后的临时路由表
stringflection[MAX];
//用于对应路由器与存储序列标号
intsum;
//用于统计路由个数
（2）构造函数
Route_net:
:
Route_net（）{
ifstreaminfile;
istringstreamstrm;
stringa_line;
Net_sect1;
open_file（infile）;
while（getline（infile,a_line））{
strm.str（a_line）;
strm>
>
_id>
t1.route_f>
t1.route_n;
li.push_back（t1）;
strm.clear（）;
}
（3）判断一个路由是否已为其添加了路由表
boolRoute_net:
judge（stringstr）{
inti=0;
while（flection[i]!
="
"
&
i<
MAX）{
i++;
if（str==flection[i]）
returnfalse;
}
returntrue;
}
（4）初始化各路由表
voidRoute_net:
Init_routes（）{
Net_sec*t;
Contentsp;
for（;
route[i].next!
=NULL;
i++）
for（t=route[i].next;
t!
t=t->
next）{
p.diatance=1;
_id=t->
net_id;
p.next_stop="
直接交付"
;
routes[i].push_back（p）;
}
（5）显示各路由表
show（）{
iteratorp;
sum;
i++）{
cout<
<
Thisisthetableof"
flection[i]<
endl;
for（p=routes[i].begin（）;
p!
=routes[i].end（）;
p++）
cout<
（*p）.net_id<
"
（*p）.diatance
<
（*p）.next_stop<
（6）对相邻路由表change一下，距离加1，下一跳变为该路由名字
change（inti）{
Contentsco;
temp.erase（temp.begin（）,temp.end（））;
iteratorp=routes[i].begin（）;
p++）{
co.diatance=（*p）.diatance+1;
_id=（*p）.net_id;
co.next_stop=flection[i];
temp.push_back（co）;
（7）对一个路由进行更新操作
update（inti）{
intcount=0;
list<
iteratorit1=routes[i].begin（）;
iteratorit2=temp.begin（）;
it2!
=temp.end（）;
it2++）{
for（it1=routes[i].begin（）;
it1!
it1++）{
if（（*it1）.net_id==（*it2）.net_id）{
count++;
if（（（*it1）.next_stop）==（（*it2）.next_stop））{
（*it1）.diatance=（*it2）.diatance;
（*it1）.next_stop=（*it2）.next_stop;
}
if（（（*it1）.next_stop!
=（*it2）.next_stop）&
（（*it1）.diatance>
（*it2）.diatance））{
（*it1）.diatance=（*it2）.diatance;
（*it1）.next_stop=（*it2）.next_stop;
}
if（count==0）
routes[i].push_back（*it2）;
count=0;
（8）对所有路由进行更新路由表操作
UPDATE（）{
intj=0,i=0,I;
for（I=0;
I<
I++）{
for（j=0;
j<
j++）{
for（i=0;
if（neighbor（j,i））{
change（i）;
update（j）;
Thisisthe"
I+1<
running......."
（9）判断两路由是否相邻
neighbor（inti,intj）{
Net_sec*p=route[i].next;
p=p->
next）
if（flection[j]==p->
route_n）
returntrue;
returnfalse;
4.1.2ospf
OSPF路由协议是基于链路状态的一种路由协议，通过带宽大小来决定路径，带宽大者优先。
1.包含的头文件
#include<
stdio.h>
iostream.h>
#include<
stdlib.h>
conio.h>
malloc.h>
string.h>
2.结构体定义
（1）将每个路由器看成一个节点，用结构体VEXTYPE来定义。
结构体内包含变量时名字name，ip地址，路由器的序号num。
typedefstruct//图中顶点表示点，存放点名称
{
charname[30];
charip[12];
升级会员 