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

______________________________________________________________________________________________________________

中 南 大 学

《计算机网络》实验报告

学生姓名
学 号
专业班级
指导教师 桂劲松
学 院 信息科学与工程学院
完成时间 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];//已经确定最短路径的节点的集合
cout<<"请输入起始节点:";
cin>>v0;
cout<<endl;

for(int cnt=0;cnt<vexnum;cnt++){//进行主要的循环之前的初始化
visit[cnt]=FALSE;
RL[cnt]=arcs[v0][cnt];

if(RL[cnt]<INFINITY){
R[cnt][0]=v0;
R[cnt][1]=cnt;
}
} //for
RL[v0]=0;//源节点的标志
visit[v0]=TRUE; //初始化已经找到最短路径的点集合

for(int i=1;i<vexnum;i++){//dijkstra算法的主要循环
int min=INFINITY;
int v=v0;
for(int j=0;j<vexnum;j++)
if(!visit[j])
if(RL[j]<min){
v=j;
min=RL[j];
}
visit[v]=TRUE; //离v0顶点最近的v加入到s集
for(int k=0;k<vexnum;k++)//更新当前最短路径及距离
if(!visit[k]&&(min+arcs[v][k]<RL[k])){
//modify shortest r[j] and RL[j]
RL[k]=min+arcs[v][k];
updateRouteLen(R[k],R[v],k,vexnum);
}//if
}//for
delete[] visit;
visit=NULL;
}//Dijkstra
完成核心算法后，对于每个路由器运行一次Dijkstra算法就可以计算出该路由到其他各个路由的最短路径。
四、实验过程及结果
本实验用6个节点进行模拟，首先输入节点个数，再依次输入节点的标识符和到邻居节点的标识符和距离。以end为结束符。
运行结果如下：
请输入路由节点总个数：
6
请输入路由节点标识符：
a
请输入节点：a 的邻居节点的标识符及其到邻居节点的距离：
b
8
请输入节点：a 的邻居节点的标识符及其到邻居节点的距离：
f
3
请输入节点：a 的邻居节点的标识符及其到邻居节点的距离：
end
请输入路由节点标识符：
b
请输入节点：b 的邻居节点的标识符及其到邻居节点的距离：
a
8
请输入节点：b 的邻居节点的标识符及其到邻居节点的距离：
c
3
请输入节点：b 的邻居节点的标识符及其到邻居节点的距离：
f
5
请输入节点：b 的邻居节点的标识符及其到邻居节点的距离：
d
2
请输入节点：b 的邻居节点的标识符及其到邻居节点的距离：
e
4
请输入节点：b 的邻居节点的标识符及其到邻居节点的距离：
end
请输入路由节点标识符：
c
请输入节点：c 的邻居节点的标识符及其到邻居节点的距离：
b
3
请输入节点：c 的邻居节点的标识符及其到邻居节点的距离：
d
10
请输入节点：c 的邻居节点的标识符及其到邻居节点的距离：
end
请输入路由节点标识符：
d
请输入节点：d 的邻居节点的标识符及其到邻居节点的距离：
c
10
请输入节点：d 的邻居节点的标识符及其到邻居节点的距离：
b
2
请输入节点：d 的邻居节点的标识符及其到邻居节点的距离：
e
6
请输入节点：d 的邻居节点的标识符及其到邻居节点的距离：
end
请输入路由节点标识符：
e
请输入节点：e 的邻居节点的标识符及其到邻居节点的距离：
b
4
请输入节点：e 的邻居节点的标识符及其到邻居节点的距离：
d
6
请输入节点：e 的邻居节点的标识符及其到邻居节点的距离：
f
4
请输入节点：e 的邻居节点的标识符及其到邻居节点的距离：
end
请输入路由节点标识符：
f
请输入节点：f 的邻居节点的标识符及其到邻居节点的距离：
a
3
请输入节点：f 的邻居节点的标识符及其到邻居节点的距离：
b
5
请输入节点：f 的邻居节点的标识符及其到邻居节点的距离：
e
4
请输入节点：f 的邻居节点的标识符及其到邻居节点的距离：
End
路由表结果

五、实验心得
本次实验，主要的就是一个著名算法的运用，当然通过本次实验我对链路路由算法也有了进一步的认识与了解。
从这次的实验中我不但学会了一个新的算法，进一步锻炼了我的编程能力而且我也对路由相关内容有了更深刻的了解。
六、附录：源代码
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.distance>distance)
dn.distance = distance;
}else{
DistanceNode 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.distance>distance)
dn.distance = distance;
}else{
DistanceNode 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(DistanceNode src,DistanceNode dst){
dst.distance = src.distance;
dst.dst = src.dst;
dst.path = src.path;
}

public void print(){
System.out.println(key+"的邻居节点：");
neighbour.print();
System.out.println("老路由表：");
old.print();
System.out.println("新路由表：");
current.print();
}
}

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！

精品资料