中南大学计算机网络实验报告

中 南 大 学计算机网络实验报告学生姓名 学 号 专业班级 指导教师 桂劲松 学 院 信息科学与工程学院 完成时间 2011年1月 模拟路由算法的实现一、实验内容1.模拟距离向量路由算法的路由表交换过程，演示每轮交换后路由表的变化。2.实现链路状态路由算法中的最短路径算法。二、实验目的及要求本实验是计算机网络课程的实践性锻炼环节。通过实验，帮助学生更好地掌握网络通信协议的实现技术，锻炼学生应用高级编程语言完成通信编程的能力，使学生加深对网络协议本质的理解，巩固课堂所学的理论知识。要求实验者利用路由选择算法模拟软件提供的通信功能，模拟链路状态路由选择算法的初始化、路由信息扩散过程和路由计算方法；掌握链路状态算法的路由信息扩散过程；掌握链路状态算法的路由计算方法。三、实验原理编程语言： JAVA编程工具： MyEclipse实验实现方式：单机模拟实现核心方法：dijkstra算法计算最短路径分析：布置好各个模拟路由，以及路由的路程权值如何获取。接着就是核心算法的实现，如何计算任意两个路由之间的最短路径问题。用到的是dijkstra算法。Dijkstra算法按照从给定起点到图中顶点的距离，顺序求出最短的路径，首先，它求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的，一次类推，推而广之，再第i次迭代开始之前，算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。这些顶点、起点和从起点到顶点的路径上的边，构成了给定图的一颗子树Ti，因为所有边的权值都是非负数，可以从与Ti的顶点相邻的顶点中找到下一个和起点最接近的顶点。和Ti的顶点相邻的顶点的集合称为“边缘顶点”，以他们为候选对象，Dijkstra算法可以从中选出一个最接近起点的顶点。为了确定第I个最接近的顶点，对于每一个边缘顶点u，该算法求出它到最近的树中顶点v的距离以及从起点到v得最短路径长度dv的和，再从中选出具有最小和的顶点。开始输入各个路由边的权值并计算运行输出各个路由表信息。各个路由分别运行一次dijkstra算法结 束删除路由或继续测试？此次实验主要是运用路由算法来处理路由当中的一些问题，利用Dijkstra算法处理最短路径的问题，在实验中这点已经得到了充分地体现。下面是该算法的流程图：核心算法代码如下。其中每个顶点用一个类来封装含有两个属性，一个是路由编号，一个是到某个路由的最短路径初始值为无限大。void Dijkstra(int * arcs,int * R,int RL,int vexnum)/迪杰斯特拉算法int v0; /定义源节点 bool * visit=new bool vexnum;/已经确定最短路径的节点的集合 coutv0;coutendl;for(int cnt=0;cntvexnum;cnt+)/进行主要的循环之前的初始化 visitcnt=FALSE;RLcnt=arcsv0cnt;if(RLcntINFINITY)Rcnt0=v0;Rcnt1=cnt; /forRLv0=0;/源节点的标志 visitv0=TRUE; /初始化已经找到最短路径的点集合 for(int i=1;ivexnum;i+)/dijkstra算法的主要循环 int min=INFINITY;int v=v0;for(int j=0;jvexnum;j+)if(!visitj)if(RLjmin)v=j;min=RLj; visitv=TRUE; /离v0顶点最近的v加入到s集for(int k=0;kvexnum;k+)/更新当前最短路径及距离if(!visitk&(min+arcsvkdistance)dn.distance = distance;elseDistanceNode dn1 = this;while(dn1.next!=null)dn1 = dn1.next;DistanceNode node = new DistanceNode();node.distance = distance;node.dst = key;node.path = path;dn1.next = node;node.next = null;public void print()DistanceNode dn = this;System.out.println(目地节点：+dn.dst+ 距离：+dn.distance+ 线路：+dn.path);while(dn.next!=null)dn = dn.next;System.out.println(目地节点：+dn.dst+ 距离：+dn.distance+ 线路：+dn.path);package dstverctor;/* * 描述两个路由节点之间关系的类 * */public class DistanceNode /public RouteNode src;/源节点/public DistanceNode(RouteNode src)/this.src = src;/public String dst;/目标节点public int distance;/两者之间的距离public String path;/经过的第一个路径节点，即线路public DistanceNode next;/下一个节点public DistanceNode()public DistanceNode(String dst,int distance,String path)this.dst = dst;this.distance = distance;this.path = path;/* * 根据节点标识符，得到路由节点到指定节点的距离 * param key 指定节点标识符 * return 如果找到，则返回这个关系类节点，否则返回null。 * int */public DistanceNode findNode(String key)DistanceNode dn = this;while(dn!=null)if(dn.dst.equals(key)return dn;dn = dn.next;return null;/* * 根据key向链表中修改或增加一个节点，如果存在dst.equal(key)的点并且他的distance大于要插入的distance，则更改其distance，否则向链表末尾插入新节点 * param key * param distance * param path * void */public void addNode(String key,int distance,String path)DistanceNode dn = findNode(key);if(null!=dn)/如果找到了节点if(dn.distancedistance)dn.distance = distance;elseDistanceNode dn1 = this;while(dn1.next!=null)dn1 = dn1.next;DistanceNode node = new DistanceNode();node.distance = distance;node.dst = key;node.path = path;dn1.next = node;node.next = null;public void print()DistanceNode dn = this;System.out.println(目地节点：+dn.dst+ 距离：+dn.distance+ 线路：+dn.path);while(dn.next!=null)dn = dn.next;System.out.println(目地节点：+dn.dst+ 距离：+dn.distance+ 线路：+dn.path);package dstverctor;/* * 路由的唯一标识符类 * */public class RouteKey String key;/路由节点的唯一标识符RouteKey next;/路由表中的下一个路由节点public RouteKey()public RouteKey(String key)this.key = key;public void print()RouteKey rk = this;System.out.print(rk.key+ | );while(rk.next!=null)rk = rk.next;System.out.print(rk.key+ | );package dstverctor;/* * 路由节点 */public class RouteNode DistanceNode old;/老路由表DistanceNode current;/新路由表RouteKey neighbour;/存储邻居节点的链表头结点String key;/跟新路由表public void updateCurrent()saveCurrent();/路由表变化前保存当前的路由表RouteNode nb;/邻居节点RouteKey rk=neighbour;while(null!=rk)/System.out.println(-+rk.key+-);nb = DistVerctor.map.get(rk.key);/由节点标记符得到路由节点/System.out.println(-+nb.key+-);DistanceNode dn= nb.old;/得到邻居节点的老路由表/排除自己在内，避免重新计算自己到邻居节点if(dn.dst.equals(key)System.out.println(-+dn.dst+-);dn = dn.next;int distTonb=0;if(dn!=null) distTonb = current.findNode(nb.key).distance;/到邻居节点的距离while(null!=dn)/排除自己在内，避免重新计算自己到邻居节点if(dn.dst.equals(key)System.out.println(-+dn.dst+-);dn = dn.next;else/修改新路由表，/如果当前节点到dn的距离小于当前节点到邻居节点nb+nb到dn的距离，则修改路由表/如果不存在当前节点到dn的路径，则在路由表最后新添加该路径current.addNode(dn.dst, dn.distance+distTonb, nb.key);dn = dn.next;rk = rk.next;/指向下一个邻居节点/* * 将当前表保存为旧表 * * void */public void saveCurrent()DistanceNode cnode = current;DistanceNode onode = new DistanceNode();copy(cnode,onode);/得到cnode的备份 old = onode;while(cnode.next!=null)onode.next = new DistanceNode();copy(cnode.next,onode.next);cnode =cnode.next;onode =onode.next;public void copy(D