1、中南大學計算機網絡實驗報告中南大學計算機網絡實驗報告學生姓名學號專業班級指導教師桂勁松學院信息科學與工程學院完成時間2011年1月模擬路由算法的實現一、實驗內容.模擬距離向量路由算法的路由表交換過程，演示每輪交換后路由表的變化。.實現鏈路狀態路由算法中的最短路徑算法。二、實驗目的及要求本實驗是計算機網絡課程的實踐性鍛煉環節。通過實驗，幫助學生更好地掌握網絡通信協議的實現技術，鍛煉學生應用高級編程語言完成通信編程的能力，使學生加深對網絡協議本質的理解，鞏固課堂所學的理論知識。要求實驗者利用路由選擇算法模擬軟件提供的通信功能，模擬鏈路狀態路由選擇算法的初始化、路由信息擴散過程和路由計算方法；掌握鏈

2、路狀態算法的路由信息擴散過程；掌握鏈路狀態算法的路由計算方法。三、實驗原理編程語言：JAVA編程工具：MyEclipse實驗實現方式：單機模擬實現核心方法：dijkstra算法計算最短路徑分析：布置好各個模擬路由，以及路由的路程權值如何獲取。接著就是核心算法的實現，如何計算任意兩個路由之間的最短路徑問題。用到的是dijkstra算法。Dijkstra算法按照從給定起點到圖中頂點的距離，順序求出最短的路徑，首先，它求出從起點到最接近起點的頂點之間的最短路徑，然后求出第二近的，一次類推，推而廣之，再第i次迭代開始之前，算法已經確定了i-1條連接起點和離起點最近頂點之間的最短路徑。這些頂點、起點和從

3、起點到頂點的路徑上的邊，構成了給定圖的一顆子樹Ti,因為所有邊的權值都是非負數，可以從與Ti的頂點相鄰的頂點中找到下一個和起點最接近的頂點。和Ti的頂點相鄰的頂點的集合稱為“邊緣頂點”，以他們為候選對象，Dijkstra算法可以從中選出一個最接近起點的頂點。為了確定第I個最接近的頂點，對于每一個邊緣頂點u,該算法求出它到最近的樹中頂點v的距離以及從起點到v得最短路徑長度dv的和，再從中選出具有最小和Dijkstra的頂點。此次實驗主要是運用路由算法來處理路由當中的一些問題，利用算法處理最短路徑的問題，在實驗中這點已經得到了充分地體現。下面是該算法的流程圖:核心算法代碼如下。其中每個頂點用一個類

4、來封裝含有兩個屬性，一個是路由編號，一個是到某個路由的最短路徑初始值為無限大。voidDijkstra(int*arcs,int*R口,intRL,intvexnum)/迪杰斯特拉算法intv0;定義源節點bool*visit=newboolvexnum;/已經確定最短路徑的節點的集合coutv0;coutendl;for(intcnt=0;cntvexnum;cnt+)進行主要的循環之前的初始化visitcnt=FALSE;RLcnt=arcsv0cnt;if(RLcntINFINITY)Rcnt0=v0;Rcnt1=cnt；/forRLv0=0;/源節點的標志visitv0=TRUE;初始

5、化已經找到最短路徑的點集合for(inti=1;ivexnum;i+)dijkstra算法的主要循環intmin=INFINITY;intv=v0;for(intj=0;jvexnum;j+)if(!visitj)if(RLjmin)v=j；min=RLj;visitv=TRUE;/離v0頂點最近的v加入到s集for(intk=0;kvexnum;k+)更新當前最短路徑及距離if(!visitk&(min+arcsvkdistance)dn.distance=distance;elseDistanceNodedn1=this;while(dn1.next!=null)dn1=dn1.next;

6、DistanceNodenode=newDistanceNode。;node.distance=distance;node.dst=key;node.path=path;dn1.next=node;node.next=null;publicvoidprint()DistanceNodedn=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.

7、path);packagedstverctor;/*描述兩個路由節點之間關系的類*/publicclassDistanceNode/publicRouteNodesrc;/W節點/publicDistanceNode(RouteNodesrc)/this.src=src;/publicStringdst;目標節點publicintdistance;/兩者之間的距離publicStringpath;/經過的第一個路徑節點，即線路publicDistanceNodenext;/T一個節點publicDistanceNode()publicDistanceNode(Stringdst,intdist

8、ance,Stringpath)this.dst=dst;this.distance=distance;this.path=path;)/*根據節點標識符，得到路由節點到指定節點的距離paramkey指定節點標識符null oreturn如果找到，則返回這個關系類節點，否則返回int/publicDistanceNodefindNode(Stringkey)DistanceNodedn=this;while(dn!=null)if(dn.dst.equals(key)returndn;)dn=dn.next;returnnull;/*根據key向鏈表中修改或增加一個節點，如果存在dst.equ

9、al(key)的點并且他的distance大于要插入的distance,則更改其distance,否則向鏈表末尾插入新節點paramkeyparamdistanceparampathvoid*/publicvoidaddNode(Stringkey,intdistance,Stringpath)DistanceNodedn=findNode(key);if(null!=dn)如果找到了節點if(dn.distancedistance)dn.distance=distance;elseDistanceNodedn1=this;while(dn1.next!=null)dn1=dn1.next;D

10、istanceNodenode=newDistanceNode。;node.distance=distance;node.dst=key;node.path=path;dn1.next=node;node.next=null;publicvoidprint()DistanceNodedn=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.p

11、ath);packagedstverctor;/*路由的唯一標識符類*/publicclassRouteKeyStringkey;/路由節點的唯一標識符RouteKeynext;/路由表中的下一個路由節點publicRouteKey()publicRouteKey(Stringkey)this.key=key;publicvoidprint()RouteKeyrk=this;System.out.print(rk.key+|);while(rk.next!=null)rk=rk.next;System.out.print(rk.key+|);packagedstverctor;/*路由節點/p

12、ublicclassRouteNodeDistanceNodeold;/總路由表DistanceNodecurrent;/新路由表RouteKeyneighbour;/#儲鄰居節點的鏈表頭結點Stringkey;/跟新路由表publicvoidupdateCurrent()saveCurrent();/I各由表變化前保存當前的路由表RouteNodenb;/鄢居節點 TOC o 1-5 h z RouteKeyrk=neighbour;while(null!=rk)/System.out.println(+rk.key+);nb=DistVerctor.map.get(rk.key);由節點標

13、記符得到路由節占八、/System.out.println(+nb.key+);DistanceNodedn=nb.old;/得到鄰居節點的老路由表/排除自己在內，避免重新計算自己到鄰居節點if(dn.dst.equals(key)System.out.println(+dn.dst+);dn=dn.next;intdistTonb=0;if(dn!=null)distTonb=current.findNode(nb.key).distance;/i猿口居節點的距離while(null!=dn)/排除自己在內，避免重新計算自己到鄰居節點if(dn.dst.equals(key)System.o

14、ut.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/publicvoidsaveCurrent()DistanceNodecnode=current;DistanceNodeonode=newDistanceNode();copy(cnode,onode);/得至Ucnode的備份old=onode;while(cnode.next!=null)onode.next=newDistanceNode();copy(cnode.next,onode.next);cnode=cnode.next;onode=onode.next;publicvoidcopy(DistanceNo