搜索
华北计算机系统工程研究所—若@只如初见1基于DV算法的路由器设计与实现实验报告学院：姓名：日期：华北计算机系统工程研究所—若@只如初见2一．实验目的1．深入理解分布式路由选择算法，以最简单的DV算法来增强对路由算法的认识2．理解、掌握和利用距离向量算法3．所实现的路由器模拟Internet上的IP路由器。它能确定网络的最短路由，并在这些利用上传输分组二．DV算法描述距离矢量算法，也称为Bellman-Fordshortestpathalgorithm，每个路由器都定期或拓扑结构突发变化时与其相邻的所有路由器交换路由表，据此更新它们自己的路由表。DV算法工作方式：每个路由器维护一张路由表，表中分为三个表项：目的地址，列出了当前可达的目的网络地址；到达目的地址下一跳，列出了下一跳的IP地址；到达目的地址的代价，以距离或跳数为表征。路由表更新规则：1．发现了一条到达某目的的新路由，而该路由在原来的路由表中不存在（即发现了一条新路由），则在路由表中增加该路由。2．发现了一条到达某目的的、距离更短的新路由，则用该路由替换原有的路由。3．到达某目的的一条路由，其后继结点到达该目的地的距离发生了变化，则需要更新该路由的距离。在此实验当中，为了实现和模拟的方便，刚开始初始化生成一个网络连接图的二维数组（见mainManager/RoutersInit.java，初始化的二维数组是entity/NetMap.java）；每个路由器类包括了路由器ID,端口，routerTable对象，还有两个HashMap(一个存储为每一个相邻路由器的计时器，一个存储每一个相邻路由器的上一次交流时间);路由表采用了两个数组来实现，一个数组存储到各个网络的下一跳，一个数组存储到各个网络的跳数，如下结构，以路由器一为例，（路由表的默认数组和两个真是数组的显示信息，其中下一跳是0表示不可达的下一跳，不是0如2004表示下一跳是2004，在距离数组里，如果是16表示不可达，如果是0，表示到本身路由，不是0或16表示可达且跳数为该数值），如下图路由表左边方框中的信息所示：华北计算机系统工程研究所—若@只如初见3在路由表中，只登记下一跳而不是完整路由，以真实模拟路由器的DV算法处理。转发分组时，严格按照路由表进行转发。如上图，路由器的连接信息在上面图片的左部区域，右部区域分为两部分（一个是路由器接到相邻路由器发来的路由表的实时-------我设置的是每1秒更新一次-------信息，一个是发送或者转发数据的显示信息）。三．实验要求1．输出路由表：在此实验当中为了实现方便，所有拓扑结构中的路由器都给以显示（可达的，不可达的16以及自己的路由编号）：要求对这个连接图的二维数组解析，进行DV算法的模拟。2．发送分组：每个数字代表一个数据分组发送请求；数据分组发送到数字代表的目的地；如果目的结点不是邻居结点，不能直接发送分组，而必须在路由的各个结点上沿路由转发该分组。收到数据分组的结点必须输出一行，显示该分华北计算机系统工程研究所—若@只如初见4组的目的，在图1中的右上角显示了每一秒的路由表的更新情况，每一个路由器都有三个转发进程，发送进程和接收进程。发送进程每一秒都需要发送自己的路由表信息。每一个路由器都给自己相邻的路由器设置了一个计时器，如果10秒钟没有收到相邻路由器的信息，就将下一跳设置成0，距离设置成16（表示不可达）。否则重新开始计数。2．发送数据：数据分组必须有数据，且在如图1中的点击提交按钮之前，必须在文本框中输入正确的数据格式（传送的目的路由和要传送的数据之间必须要有“#”号分割），如：2003#DDDDDDD，表示目的路由是2003，传送的数据是DDDDDDD。例如：路由器2006要向2001发送数据，则具体转发过程如下：在RouterTablePacket中有Hops(初始值是16，每过一跳，hops减1，当hops是1的时候，就不再进行转发了，相当于TTL：TimetoLive)属性，分组应该在华北计算机系统工程研究所—若@只如初见5Hops规定的时间或步数内到达目的结点，否则丢弃之。分组经过每个中间结点时，将其TTL减1。若TTL=1，丢弃，否则继续转发。3．关于时间定时：每个路由器每1秒钟发出它们的路由表；每个路由器根据收到的路由表更新它们自己的路由表；路由器必须具备检测邻居是否活动的能力，如果路由器在10秒钟没有收到邻居发来的更新，则认为邻居不可达。4．显示活动的相邻路由：用一个特定的表格来显示与当前路由相邻的路由器的信息。5．关于拓扑结构：路由器必须具备路由器故障和恢复的能力；这里假设链路不会出现故障，分组不会丢失和出错；如果路由器在给定时间内未运行，表示路由器故障，如果重启运行，则认为路由器故障恢复；当然，假设通信是双向的。四．实验用例编程语言：java；开发环境：jdk1.6.0_02、Myeclipse8.6,测试用例为二维数组的维数个（你可以随便写出一个对称的二维数组，程序可以自己解析的，我用的都是活代码），如下如所示我写的一个拓扑图的二维数组，如图：此实验是模仿DV算法，应用java中的多线程来模拟多个路由器，并且实现路由器之间的路由表和数据的传送。实验中路由表的数据结构相比真实的DV算法发生了变化，所以程序在实现过程当中尽量的按照实验所用的路由表结构来完成功能，但是这不影响其主要思想的实现。1．拓扑结构：为了模拟路由表的更新，首先是先确立六个结点网络的拓扑结构，由于是应用多线程来模拟各个路由器，所以在实验过程当中可以随时挂起某个或多个路由器来模拟网络拓扑的变化，之后仍然可以恢复挂起的路由器。网络的初始拓扑结构如图2所示：华北计算机系统工程研究所—若@只如初见6图2此处，路由表的端口号和路由器号全是来自entity/Constant.java文件的整个程序的全局变量，路由器初始值为2001，而端口初始值为5001，分别是数组初始化时的维数个。在实验实现过程当中，通过路由器线程的挂起实现网络拓扑结构的动态变化，之后会对相应的更该重新画出拓扑结构。2．路由表初始化：在程序的mainManager/RoutersInit.java类中初始化了留个路由器，这六个路由器的每一个实现都是在mainManager/RouterThread.java类中，。以上图2的初始化二维数组中所规划的网络拓扑结构为标准，根据当前所创建的路由器编号静态初始化每个路由器自己的路由表。3．数据格式：各个路由器实例之间通过UDP来交换路由表，路由器之间还需要进行数据的传输。在此，需要定义所传输的路由表和数据的结构，我是全部打成了数据包或者路由表包，具体结构见transportPacket/RouterTablePacket.java（有sourceRouterId和routerTable两个属性），transportPacket/SendDataPacket.java（有sourceRouterId,destRouterId,byte[]data,hops=16四个属性），transportPacket/TotalPacket.java（有type,routerTablePacket,sendDataPacket三个属性，TotalPacket类定义了具体具体是传输的包是什么类型的）三个类，如果是传输路由表就用RouterTablePacket把路由表包装后再用TotalPacket的sendRouterTable类型来包装，最后用UDP发送出去，如果是传输数据就用SendDataPacket把要传送的数据包装后再用TotalPacket的sendData类型来包装，最后用UDP发送出去，在目的路由器端对收到的数据进行解封装。五．程序描述端口号：50012002端口号：2005端口号：5002端口号：5004端口号：5003端口号：200620032001200520042006华北计算机系统工程研究所—若@只如初见7为完成所要求功能，程序首先实现了二维数组维数个路由器线程，每一个路由器线程下面又实现了发送线程、接收线程和转发数据线程三个子线程；接收线程下面实现了定时器子线程。建立一个工程，命名为day12-02_DV_new_hasTimer（名字可以随便起，我是以前的习惯都加上了日期），在此工程下建立源程序文件，每个线程放在单独的java源程序文件当中。该实验还可以对其中一个路由器进行挂起，别的路由器在10秒后如果收不到这个路由器发来的路由表信息，就将其路由表中的与其对应的相应路由表的值进行修改成不可达，逐渐通知到整个网络。在这里有点不同于DV算法的是：DV算法是每个路由器为收到的路由表的每一个简历一个计时器，而该路由器简化了这个设计，是仅仅为相邻的路由器保留一个计时器，这样不仅可以大大减少整个网络的通信量，将计时器的信息保留在内存而不是在路由表中，而且采用了hashMap保存后在验证是否联通时，从hashMap中取数据方便快捷。六、实验结论在实验过程遇到了许多问题，一方面是编程语言的使用，另一方面是对路由算法的理解程度。三是计时器的用法，尤其是计时器的用法想了将近2个小时，最后通过不懈的调试与算法完善，程序基本实现所要求的功能，有能力模拟DV算法。DV算法的优缺点：DV算法简单，容易实现，对于好消息传播的速度快，但是对于坏消息则传播速度慢。华北计算机系统工程研究所—若@只如初见8packageentity;/***常量类*@author郭金磊*@since20131220*/publicclassConstant{/***@return返回路由Id的初试值*/publicstaticintgetRouterIdBasic(){return2001;}/***@return返回路由端口的初试值*/publicstaticintgetPortBasic(){return5001;}}packageentity;/***初始化的网络拓扑图*@author郭金磊*@since20131220*/publicclassNetMap{/***@return返回初始化的网络图*/publicint[][]getInitInternetMap(){int[][]initVecter=newint[][]华北计算机系统工程研究所—若@只如初见9{{0,1,16,16,1,16},{1,0,1,16,16,16},{16,1,0,1,1,16},{16,16,1,0,16,1},{1,16,1,16,0,16},{16,16,16,1,16,0}};returninitVecter;}}packageentity;importjava.util.HashMap;/***路由器实体类，包含routerId，port，RouterTable，createTimerMapsForNeighbers，lastTimeMaps*@author郭金磊*@since20131220*/publicclassRouter{/***产生全局唯一的序列化的实体ID*/privatestaticfinallongserialVersionUID=-4112736218089137504L;/***路由ID*/privateintrouterId;/***路由端口*/privateintport;/**华北计算机系统工程研究所—若@只如初见10*路由表*/privateRouterTableRouterTable;/***存储计时器的Map*/privateHashMapInteger,TimeCountercreateTimerMapsForNeighbers=newHashMapInteger,TimeCounter();/***存储上一次该路由器收到某个路由器的路由表时间*/privateHashMapInteger,LonglastTimeMaps=newHashMapInteger,Long();/***默认的构造方法*/publicRouter(){super();}