中南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)報(bào)告

1、中南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)報(bào)告中南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)報(bào)告學(xué)生姓名學(xué)號(hào)專業(yè)班級(jí)指導(dǎo)教師桂勁松學(xué)院信息科學(xué)與工程學(xué)院完成時(shí)間2011年1月模擬路由算法的實(shí)現(xiàn)一、實(shí)驗(yàn)內(nèi)容.模擬距離向量路由算法的路由表交換過(guò)程，演示每輪交換后路由表的變化。.實(shí)現(xiàn)鏈路狀態(tài)路由算法中的最短路徑算法。二、實(shí)驗(yàn)?zāi)康募耙蟊緦?shí)驗(yàn)是計(jì)算機(jī)網(wǎng)絡(luò)課程的實(shí)踐性鍛煉環(huán)節(jié)。通過(guò)實(shí)驗(yàn)，幫助學(xué)生更好地掌握網(wǎng)絡(luò)通信協(xié)議的實(shí)現(xiàn)技術(shù)，鍛煉學(xué)生應(yīng)用高級(jí)編程語(yǔ)言完成通信編程的能力，使學(xué)生加深對(duì)網(wǎng)絡(luò)協(xié)議本質(zhì)的理解，鞏固課堂所學(xué)的理論知識(shí)。要求實(shí)驗(yàn)者利用路由選擇算法模擬軟件提供的通信功能，模擬鏈路狀態(tài)路由選擇算法的初始化、路由信息擴(kuò)散過(guò)程和路由計(jì)算方法；掌握鏈

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

3、起點(diǎn)到頂點(diǎn)的路徑上的邊，構(gòu)成了給定圖的一顆子樹Ti,因?yàn)樗羞叺臋?quán)值都是非負(fù)數(shù)，可以從與Ti的頂點(diǎn)相鄰的頂點(diǎn)中找到下一個(gè)和起點(diǎn)最接近的頂點(diǎn)。和Ti的頂點(diǎn)相鄰的頂點(diǎn)的集合稱為“邊緣頂點(diǎn)”，以他們?yōu)楹蜻x對(duì)象，Dijkstra算法可以從中選出一個(gè)最接近起點(diǎn)的頂點(diǎn)。為了確定第I個(gè)最接近的頂點(diǎn)，對(duì)于每一個(gè)邊緣頂點(diǎn)u,該算法求出它到最近的樹中頂點(diǎn)v的距離以及從起點(diǎn)到v得最短路徑長(zhǎng)度dv的和，再?gòu)闹羞x出具有最小和Dijkstra的頂點(diǎn)。此次實(shí)驗(yàn)主要是運(yùn)用路由算法來(lái)處理路由當(dāng)中的一些問題，利用算法處理最短路徑的問題，在實(shí)驗(yàn)中這點(diǎn)已經(jīng)得到了充分地體現(xiàn)。下面是該算法的流程圖:核心算法代碼如下。其中每個(gè)頂點(diǎn)用一個(gè)類

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

5、化已經(jīng)找到最短路徑的點(diǎn)集合for(inti=1;ivexnum;i+)dijkstra算法的主要循環(huán)intmin=INFINITY;intv=v0;for(intj=0;jvexnum;j+)if(!visitj)if(RLjmin)v=j；min=RLj;visitv=TRUE;/離v0頂點(diǎn)最近的v加入到s集for(intk=0;kvexnum;k+)更新當(dāng)前最短路徑及距離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(目地節(jié)點(diǎn)：+dn.dst+距離：+dn.distance+”線路：+dn.path);while(dn.next!=null)dn=dn.next;System.out.println(目地節(jié)點(diǎn)：+dn.dst+”距離：+dn.distance+線路：+dn.

7、path);packagedstverctor;/*描述兩個(gè)路由節(jié)點(diǎn)之間關(guān)系的類*/publicclassDistanceNode/publicRouteNodesrc;/W節(jié)點(diǎn)/publicDistanceNode(RouteNodesrc)/this.src=src;/publicStringdst;目標(biāo)節(jié)點(diǎn)publicintdistance;/兩者之間的距離publicStringpath;/經(jīng)過(guò)的第一個(gè)路徑節(jié)點(diǎn)，即線路publicDistanceNodenext;/T一個(gè)節(jié)點(diǎn)publicDistanceNode()publicDistanceNode(Stringdst,intdist

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

9、al(key)的點(diǎn)并且他的distance大于要插入的distance,則更改其distance,否則向鏈表末尾插入新節(jié)點(diǎn)paramkeyparamdistanceparampathvoid*/publicvoidaddNode(Stringkey,intdistance,Stringpath)DistanceNodedn=findNode(key);if(null!=dn)如果找到了節(jié)點(diǎn)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(目地節(jié)點(diǎn)：+dn.dst+距離：+dn.distance+”線路：+dn.path);while(dn.next!=null)dn=dn.next;System.out.println(目地節(jié)點(diǎn)：+dn.dst+”距離:+dn.distance+線路：+dn.p

11、ath);packagedstverctor;/*路由的唯一標(biāo)識(shí)符類*/publicclassRouteKeyStringkey;/路由節(jié)點(diǎn)的唯一標(biāo)識(shí)符RouteKeynext;/路由表中的下一個(gè)路由節(jié)點(diǎn)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;/*路由節(jié)點(diǎn)/p

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

13、記符得到路由節(jié)占八、/System.out.println(+nb.key+);DistanceNodedn=nb.old;/得到鄰居節(jié)點(diǎn)的老路由表/排除自己在內(nèi)，避免重新計(jì)算自己到鄰居節(jié)點(diǎn)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猿口居節(jié)點(diǎn)的距離while(null!=dn)/排除自己在內(nèi)，避免重新計(jì)算自己到鄰居節(jié)點(diǎn)if(dn.dst.equals(key)System.o

14、ut.println(+dn.dst+-);dn=dn.next;else/修改新路由表，/如果當(dāng)前節(jié)點(diǎn)到dn的距離小于當(dāng)前節(jié)點(diǎn)到鄰居節(jié)點(diǎn)nb+nb到dn的距離，則修改路由表/如果不存在當(dāng)前節(jié)點(diǎn)到dn的路徑，則在路由表最后新添加該路徑current.addNode(dn.dst,dn.distance+distTonb,nb.key);dn=dn.next;rk=rk.next;指向下一個(gè)鄰居節(jié)點(diǎn)/*將當(dāng)前表保存為舊表*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