1、中南大学计算机网络实验报告中 南 大 学计算机网络实验报告学生姓名 学 号 专业班级 指导教师 桂劲松 学 院 信息科学与工程学院 完成时间 2011年月 模拟路由算法的实现一、实验内容1.模拟距离向量路由算法的路由表交换过程，演示每轮交换后路由表的变化。2实现链路状态路由算法中的最短路径算法。二、实验目的及要求本实验是计算机网络课程的实践性锻炼环节。通过实验,帮助学生更好地掌握网络通信协议的实现技术，锻炼学生应用高级编程语言完成通信编程的能力，使学生加深对网络协议本质的理解，巩固课堂所学的理论知识。要求实验者利用路由选择算法模拟软件提供的通信功能，模拟链路状态路由选择算法的初始化、路由信息扩
2、散过程和路由计算方法;掌握链路状态算法的路由信息扩散过程;掌握链路状态算法的路由计算方法。三、实验原理编程语言： JA编程工具: MEclips实验实现方式：单机模拟实现核心方法:dijktra算法计算最短路径分析：布置好各个模拟路由，以及路由的路程权值如何获取。接着就是核心算法的实现,如何计算任意两个路由之间的最短路径问题。用到的是dijktra算法。ijktra算法按照从给定起点到图中顶点的距离，顺序求出最短的路径，首先，它求出从起点到最接近起点的顶点之间的最短路径,然后求出第二近的,一次类推,推而广之,再第i次迭代开始之前，算法已经确定了-1条连接起点和离起点最近顶点之间的最短路径。这些
3、顶点、起点和从起点到顶点的路径上的边，构成了给定图的一颗子树Ti,因为所有边的权值都是非负数,可以从与T的顶点相邻的顶点中找到下一个和起点最接近的顶点。和Ti的顶点相邻的顶点的集合称为“边缘顶点”,以他们为候选对象，Diktra算法可以从中选出一个最接近起点的顶点。为了确定第I个最接近的顶点，对于每一个边缘顶点u,该算法求出它到最近的树中顶点v的距离以及从起点到v得最短路径长度dv的和，再从中选出具有最小和的顶点。此次实验主要是运用路由算法来处理路由当中的一些问题，利用jkstra算法处理最短路径的问题，在实验中这点已经得到了充分地体现。下面是该算法的流程图：核心算法代码如下。其中每个顶点用一
4、个类来封装含有两个属性,一个是路由编号,一个是到某个路由的最短路径初始值为无限大。vod jkstr( * arcs,int* ,itL,itvexum）/迪杰斯特拉算法 int v0; /定义源节点 boo * visit=new bool vexnum;/已经确定最短路径的节点的集合 outv；couendl; fo(int cnt=0;nvexum;cnt+)/进行主要的循环之前的初始化 visitcnt=FALS; Rcnt=arcsvct； f(RLctINFINIY) Rnt0=0;cnt1t; /forRL0=0;/源节点的标志 vsitv0=TRUE; 初始化已经找到最短路径的
5、点集合 for( i=1;vxnum;i+）/ijsta算法的主要循环 int min=INFNITY; int v=0； fo(int =0；jvexum;+） if(!vst) （Rjmin） vj; mi=RLj; viiv=TRUE； /离v0顶点最近的v加入到s集 or(in k=0;kdstance) dn.disace istanc; elseistancede dn1= ths; whle(！null) dn = n.next; DstanceNode od = ne DistaneNoe()； noeistance = itan; nod.dst = key; nod.pat
6、h =path; d1.ex = node; = nll; publc voidprint() DstnceNodedn hs; Sstem.out.prntln(目地节点:+n.ds+ 距离:dn.istane+线路:n.path);whie(dn.next!=ul)dn= dn.ne; St.outrintln（目地节点:dn.t 距离:+dn.sance线路:+d.pah); packagedstvetr;/* *描述两个路由节点之间关系的类* */uli class DistncNod /publc RouteNe sr;/源节点/pblicDstanceode(RotNo src）
7、/tis.src =r;/ pbli Sring dst;/目标节点public in dtac；两者之间的距离 pubic Srin ath；/经过的第一个路径节点,即线路 publi istaceNod ne;/下一个节点public DistanceNde() publc Disaneode(Strig dt,int istce,Strin path) this.dt = ds;this.ditane =itnce; thspa path; /* * 根据节点标识符,得到路由节点到指定节点的距离 *param key 指定节点标识符 * rtur如果找到,则返回这个关系类节点，否则返回u
8、ll。 * int */ publi DistnceNde fndod(Stringey) DsancNode s；wie（d！nul） if(dn.s.equals(key) rtun dn; dn d.ex; etun null; /* * 根据ke向链表中修改或增加一个节点,如果存在t.equal(key)的点并且他的dstce大于要插入的distne,则更改其distane,否则向链表末尾插入新节点 par e *pramdstanc para ah * oi */pulioid adNode(Sting ke,it ditane，Sing ath)DistanceNd dn = fn
9、Node(ey); if(nll!)/如果找到了节点 if(dn.ditacedtce) n.diste= isae; lse istaneNode n1 = th; hil(d1.next!ull) 1 = dn.ext; Distncode de n Ditncede(）; nod.ditane = stac；oe.st= key;no.pth = th; dnnex = node; nodeet ul; blicoid print() DistanceNde dn tis; Systemout.prinn(目地节点：+dn.dst+ 距离：+.isnce+线路:n.pt); whil(n
10、.next！=ull) = d.nxt； System.otritln(目地节点:+dndst+距离:dn.distance+ 线路:+d.pth）； pkagestvert;/* 路由的唯一标识符类 */pubc cass otey Srng ky;/路由节点的唯一标识符 Ruteey next;/路由表中的下一个路由节点 publicRoteKey（) public Routeey（Strg ke) ti.key = ey; ulic voidrit（) otKy rk=tis; Sys.out.rin（kkey | ); ile（rknext!=null) k = rk.nxt; Sys
11、emout.prin(rk.key+ | ）; package dstvert；/* 路由节点 */pubic class oueNoe isacNe ld;/老路由表DisanceNode current;/新路由表 RoeKey eighour;/存储邻居节点的链表头结点 Sg ey； /跟新路由表 lic oid updateuet() saveCurent();/路由表变化前保存当前的路由表Rutede b;/邻居节点 RuteKey rk=nihbour; wile(ul!rk)/ Sytemutprintln（-+r.ky-）; b = DistVerctor.map.get（rk
12、.key)；/由节点标记符得到路由节点 /tm.ut.prinl(-nbke-); DisanceNode d= nb.l；/得到邻居节点的老路由表 /排除自己在内,避免重新计算自己到邻居节点 i(dn.t.equals(ky) Sstem.ou.rint(-+dn.d-）; dn n.e; intdistTnb0; (n!ul) disTob cunt.fidode(nb.ky).istance；/到邻居节点的距离 while（null!=n) /排除自己在内，避免重新计算自己到邻居节点 if(dn.st.equals(key)） ytem.out.rintln（-+dn.st-); dn
13、= d.next; els /修改新路由表， /如果当前节点到dn的距离小于当前节点到邻居节点nb+nb到dn的距离,则修改路由表 /如果不存在当前节点到d的路径，则在路由表最后新添加该路径 cr.adNode（dn.st, dndiane+distTonb,n.ky); dn dnnex; rk = ;/指向下一个邻居节点 * * 将当前表保存为旧表* *vid */ puic vid aveCrren() DiaNode nod = current; DistancNde oode eDisanNode（）;copy(node,onod);/得到cnde的备份 ld oode;whil(c
14、nodenex！=null) onenex = nw DistacNode(); co(cndent,onod.next）; node =cnonex; onode =onode.nt； pli vod cop(Disaeod src,istanceNodd) dst.istance= rcditae; ds.d=src.dt;dst.pat src.path; puic void rint（) Sytem.out.printn(ky+的邻居节点：); ihbou.rint();Systemo.pintln(老路由表:)； old.prn(); System.ot.pintln(新路由表:);crrentprnt(）;
