最新中南大学计算机网络试验报告

1、精品文档中南大学计算机网络实验报告学生姓名学 号专业班级指导教师桂劲松学 院信息科学与工程学院完成时间2011年1月模拟路由算法的实现一、实验内容1. 模拟距离向量路由算法的路由表交换过程，演示每轮交换后路由表的变化。2. 实现链路状态路由算法中的最短路径算法。二、实验目的及要求本实验是计算机网络课程的实践性锻炼环节。 通过实验， 帮助学生更好地掌 握网络通信协议的实现技术，锻炼学生应用高级编程语言完成通信编程的能力， 使学生加深对网络协议本质的理解， 巩固课堂所学的理论知识。 要求实验者利用 路由选择算法模拟软件提供的通信功能，模拟链路状态路由选择算法的初始化、 路由信息扩散过程和路由计算方

2、法；掌握链路状态算法的路由信息扩散过程； 掌握链路状态算法的路由计算方法。三、实验原理编程语言： JAVA编程工具： MyEclipse实验实现方式：单机模拟实现核心方法： dijkstra 算法计算最短路径 分析：布置好各个模拟路由，以及路由的路程权值如何获取。接着就是核心算法的实现， 如何计算任意两个路由之间的最短路径问题。 用 到的是 dijkstra 算法。Dijkstra 算法按照从给定起点到图中顶点的距离，顺序求出最短的路径， 首先，它求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的， 一次类推，推而广之，再第i次迭代开始之前，算法已经确定了 i-1条连接起点 和离起点

3、最近顶点之间的最短路径。这些顶点、起点和从起点到顶点的路径上的边，构成了给定图的一颗子树Ti ，因为所有边的权值都是非负数，可以从与 Ti 的顶点相邻的顶点中找到下一 个和起点最接近的顶点。 和 Ti 的顶点相邻的顶点的集合称为 “边缘顶点”，以他们为候选对象，Dijkstra 算法可以从中选出一个最接近起点的顶点。为了确定第I个最接近的顶点，对于每一个边缘顶点 u,该算法求出它到最近的树中顶点 v的距离以及从起点到v得最短路径长度dv的和，再从中选出具有最小和的顶 点。此次实验主要是运用路由算法来处理路由当中的一些问题，利用Dijkstra算法处理最短路径的问题，在实验中这点已经得到了充分地

4、体现。下面是该算法核心算法代码如下。其中每个顶点用一个类来封装含有两个属性，一个是路由编号，一个是到某个路由的最短路径初始值为无限大。void Dijkstra(i nt * arcs,i nt * R,i nt RL,i nt vex nu m)/迪杰斯特拉算法in t v0;定义源节点bool * visit= new bool vex num;/已经确定最短路径的节点的集合cout v0;coute ndl;for(int cnt=0;cntvexnum;cnt+)/ 进行主要的循环之前的初始化 visitcnt=FALSE;RLcnt=arcsv0cnt;if(RLcntINFINIT

5、Y)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+arcsvkdistanee)dn.distane

6、e = distanee;elseDistaneeNode 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.distanc

7、e+ 线路： +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;/ 目标节点publi

8、c 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; /* 根据节点标识符，得到路由节点到指定节点的距离null。* param key 指定节点标识符* return 如果找到，则返回这个关系类节点

9、，否则返回* 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) 的点并且他的distanee大于要插入的distanee，则更改其distanee，否则向链表末尾插入新节点* param key* param distanee* param path* void*/publie

10、void addNode(String key,int distanee,String path)DistaneeNode dn = findNode(key);if(null!=dn)/ 如果找到了节点if(dn.distaneedistanee)dn.distanee = distanee;elseDistaneeNode dn1 = this;while(dn1.next!=null)dn1 = dn1.next;DistaneeNode node = new DistaneeNode();node.distanee = distanee;node.dst = key;node.path

11、 = 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 c

12、lass RouteKey Stri ng 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 RouteN

13、ode Dista nceNode old;/ 老路由表DistanceNode current;/ 新路由表RouteKey neighbour;/ 存储邻居节点的链表头结点 String key;/跟新路由表public void updateCurrent()saveCurre nt();路由表变化前保存当前的路由表RouteNode nb; 邻居节点RouteKey rk=neighbour;while(null!=rk)/ System.out.println(+rk.key+);nb = DistVerctor.map.get(rk.key);/ 由节点标记符得到路由节点/Syst

14、em.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.

15、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(Distanc