1、PAGE PAGE 56滁州學(xué)院課程設(shè)計報告課程名稱： 計算機(jī)網(wǎng)絡(luò) 設(shè)計題目： 路由表查找過程模擬 院 部： 計算機(jī)與信息工程學(xué)院 專 業(yè)： 網(wǎng)絡(luò)工程（無線傳感器網(wǎng)絡(luò)方向） 組 別： 第 二 組 起止日期: 2012年12月29日 2012年12月30日 指導(dǎo)教師: 張 老師 計算機(jī)與信息工程學(xué)院二一二年制課程設(shè)計題目路由器查表過程模擬組長曹學(xué)號2011211班級網(wǎng)工113班院部計算機(jī)與信息工程學(xué)院專業(yè)網(wǎng)絡(luò)工程（無線傳感器網(wǎng)絡(luò)方向）組員指導(dǎo)教師張課程設(shè)計目的通過課程設(shè)計,加深對路由表的理解,掌握路由表查找的基本原理及功能,具有初步分析實(shí)際路由表的組成、構(gòu)造，并具備準(zhǔn)確查找路由表的能力。課程設(shè)計

2、所需環(huán)境Windows XP，VC+6.0課程設(shè)計任務(wù)要求編程模擬路由器查找路由表的過程，用（目的地址 掩碼 下一跳）的IP路由表以及目的地址作為輸入，為目的地址查找路由表，找出正確的下一跳并輸出結(jié)果。課程設(shè)計工作進(jìn)度計劃序號起止日期工 作 內(nèi) 容分工情況12012.12.29分析討論，進(jìn)行相關(guān)的分工以及查閱相關(guān)的資料曹對組員進(jìn)行分工。每個組員查閱資料，摘取相關(guān)的信息22012.12.29編寫源代碼，對源程序進(jìn)行調(diào)試編寫源代碼，對程序代碼進(jìn)行調(diào)試32012.12.30撰寫課程設(shè)計報告。與老師進(jìn)行交流，對報告進(jìn)行相關(guān)的修改，并打印根據(jù)課程設(shè)計報告模板，組員在一起撰寫實(shí)驗(yàn)報告，并和老師在一起交流，

3、進(jìn)行報告的相關(guān)修改，最后打印實(shí)驗(yàn)報告指導(dǎo)教師簽字： 年 月 日系（教研室）審核意見：系（教研室）主任簽字： 年 月 日課程設(shè)計任務(wù)書目 錄 HYPERLINK l _Toc344987394 2.3.1 設(shè)計內(nèi)容 PAGEREF _Toc344987394 h 2 HYPERLINK l _Toc344987395 2.3.2設(shè)計要求 PAGEREF _Toc344987395 h 2 HYPERLINK l _Toc344987396 2.3.3使用環(huán)境及語言 PAGEREF _Toc344987396 h 3 HYPERLINK l _Toc344987399 3.1.1路由表的結(jié)構(gòu) PA

4、GEREF _Toc344987399 h 3 HYPERLINK l _Toc344987400 3.1.2路由表的作用 PAGEREF _Toc344987400 h 4 HYPERLINK l _Toc344987401 3.1.3路由表中路由的來源 PAGEREF _Toc344987401 h 4 HYPERLINK l _Toc344987403 3.2.1通過RIP（路由信息協(xié)議）來實(shí)現(xiàn)路由選擇 PAGEREF _Toc344987403 h 4 HYPERLINK l _Toc344987404 3.2.2通過OSPF（開放最短路徑優(yōu)先）來實(shí)現(xiàn)路由選擇 PAGEREF _Toc

5、344987404 h 6 HYPERLINK l _Toc344987405 3.2.3 Dijkstra算法 PAGEREF _Toc344987405 h 7 HYPERLINK l _Toc344987408 4.1.1RIP PAGEREF _Toc344987408 h 8 HYPERLINK l _Toc344987409 4.1.2 OSPF PAGEREF _Toc344987409 h 121引言隨著計算機(jī)信息技術(shù)的發(fā)展，大規(guī)模的互聯(lián)網(wǎng)逐漸流行起來，也為路由器的發(fā)展提供了良好的基礎(chǔ)和平臺。作為不同網(wǎng)絡(luò)之間互相連接的樞紐，路由器系統(tǒng)構(gòu)成了基于TCP/IP 的國際互聯(lián)網(wǎng)絡(luò)Int

6、ernet 的主體脈絡(luò)。然而如何準(zhǔn)確的發(fā)送并接受信息，則需要通過路由表的準(zhǔn)確查找，路由表存儲著指向特定網(wǎng)絡(luò)地址的路徑（在有些情況下，還記錄有路徑的路由度量值）。通過路由表查找過程的設(shè)計與模擬可以更好的體現(xiàn)路由的選擇，幫助我們準(zhǔn)確的理解路由的選擇過程。2需求分析2.1設(shè)計題目路由器查表過程模擬2.2設(shè)計目的該程序主要是用來模擬路由器中路由查找的過程。當(dāng)主機(jī)向目的網(wǎng)絡(luò)發(fā)送一個數(shù)據(jù)包時，對每一個IP包，當(dāng)發(fā)送到一個網(wǎng)絡(luò)拓?fù)渲械臅r候，可以分別使用RIP或OSPF協(xié)議，來決定數(shù)據(jù)包通過互聯(lián)網(wǎng)絡(luò)的路徑。通過模擬算法的實(shí)現(xiàn)，我們可以模擬一個簡單的路由查找過程，進(jìn)而找出最優(yōu)路徑，實(shí)現(xiàn)路由的查找。2.3設(shè)計主要

7、內(nèi)容及要求2.3.1 設(shè)計內(nèi)容1rip：距離向量路由協(xié)議，距離向量路由協(xié)議的特征是它在進(jìn)行路由更新時，會發(fā)送路由表的全部或一部分給鄰居路由器（這臺鄰居路由器也必須運(yùn)行rip協(xié)議），當(dāng)路由信息通過這種方式擴(kuò)散到整個自治系統(tǒng)時，每個路由器會根據(jù)Dijkstra算法計算出到達(dá)每個網(wǎng)段的最優(yōu)路徑，rip選擇到達(dá)某個網(wǎng)絡(luò)的最優(yōu)路徑根據(jù)跳數(shù)。數(shù)據(jù)包經(jīng)過一個路由器就是一跳。2 ospf：路由器的路由選擇是基于鏈路狀態(tài)，通過Dijkastra算法建立起來最短路徑樹，用該樹跟蹤系統(tǒng)中的每個目標(biāo)的最短路徑。最后再通過計算域間路由、自治系統(tǒng)外部路由確定完整的路由表。與此同時，OSPF動態(tài)監(jiān)視網(wǎng)絡(luò)狀態(tài)，一旦發(fā)生變化則

8、迅速擴(kuò)散達(dá)到對網(wǎng)絡(luò)拓?fù)涞目焖倬酆希瑥亩_定出新的網(wǎng)絡(luò)路由表。因此，需要把自治系統(tǒng)劃分為多個域，每個域內(nèi)部維持本域一張唯一的拓?fù)浣Y(jié)構(gòu)圖，且各域根據(jù)自己的拓?fù)鋱D各自計算路由，域邊界路由器把各個域的內(nèi)部路由總結(jié)后在域間擴(kuò)散。這樣，當(dāng)網(wǎng)絡(luò)中的某條鏈路狀態(tài)發(fā)生變化時，此鏈路所在的域中的每個路由器重新計算本域路由表，而其它域中路由器只需修改其路由表中的相應(yīng)條目而無須重新計算整個路由表，節(jié)省了計算路由表的時間。2.3.2設(shè)計要求任意兩個節(jié)點(diǎn)，分別在rip和ospf協(xié)議的前提條件下，根據(jù)相應(yīng)的算法找出最優(yōu)路徑。在rip協(xié)議中，所有的路由都由跳數(shù)來描述，到達(dá)目的地的路由最大不超過16跳，且只保留唯一的一條路由，

9、這就限制了RIP的服務(wù)半徑，即其只適用于小型的簡單網(wǎng)絡(luò)。同時，運(yùn)行RIP的路由器需要定期地（一般30s）將自己的路由表廣播到網(wǎng)絡(luò)當(dāng)中，達(dá)到對網(wǎng)絡(luò)拓?fù)涞木酆希@樣不但聚合的速度慢而且極容易引起廣播風(fēng)暴、累加到無窮、路由環(huán)致命等問題。為此，OSPF應(yīng)運(yùn)而生。OSPF是基于鏈路狀態(tài)的路由協(xié)議，它克服了RIP的許多缺陷：第一，OSPF不再采用跳數(shù)的概念第二，OSPF支持不同服務(wù)類型的不同代價，從而實(shí)現(xiàn)不同QoS的路由服務(wù)；第三，OSPF路由器不再 HYPERLINK /List_7.html t _blank 交換路由表，而是同步各路由器對網(wǎng)絡(luò)狀態(tài)的認(rèn)識，即鏈路狀態(tài)數(shù)據(jù)庫，然后通過Dijkstra最短

10、路徑算法計算出網(wǎng)絡(luò)中各目的地址的最優(yōu)路由。2.3.3使用環(huán)境及語言編程環(huán)境：Microsoft Visual C+6.0編寫語言：C+語言3概要設(shè)計3.1基本功能描述3.1.1路由表的結(jié)構(gòu)標(biāo)準(zhǔn)的路由表表目是一個二維組（目的網(wǎng)絡(luò)地址，下一站地址），其中不攜帶子網(wǎng)信息，不能滿足子網(wǎng)尋徑。引入子網(wǎng)編址以后，路由表的每一表目中加入子網(wǎng)掩碼，于是路由表表目變?yōu)槿S組：子網(wǎng)掩碼、目的網(wǎng)絡(luò)地址、下一站地址。表1 路由表結(jié)構(gòu)及使用目的地址掩碼下一跳地址路由器依據(jù)路由表來為報文尋徑，路由表由路由協(xié)議建立和維護(hù)。路由協(xié)議的設(shè)計則是依據(jù)某種路由算法。路由器提供了將異構(gòu)網(wǎng)互聯(lián)的機(jī)制，實(shí)現(xiàn)將一個數(shù)據(jù)包從一個網(wǎng)絡(luò)發(fā)送到另

11、一個網(wǎng)絡(luò)。路由就是指導(dǎo)IP數(shù)據(jù)包發(fā)送的路徑信息。3.1.2路由表的作用路由器的主要工作就是為經(jīng)過路由器的每個數(shù)據(jù)幀尋找一條最佳傳輸路徑，并將該數(shù)據(jù)有效地傳送到目的站點(diǎn)。由此可見，選擇最佳路徑的策略即路由算法是路由器的關(guān)鍵所在。為了完成這項(xiàng)工作，在路由器中保存著各種傳輸路徑的相關(guān)數(shù)據(jù)路由表（Routing Table），供路由選擇時使用。打個比方，路由表就像我們平時使用的地圖一樣，標(biāo)識著各種路線，路由表中保存著子網(wǎng)的標(biāo)志信息、網(wǎng)上路由器的個數(shù)和下一個路由器的名字等內(nèi)容。路由表可以是由系統(tǒng)管理員固定設(shè)置好的，也可以由系統(tǒng)動態(tài)修改，可以由路由器自動調(diào)整，也可以由主機(jī)控制。3.1.3路由表中路由的來源

12、在路由表中有一個Protocol字段，指明了路由的來源，即路由是如何生成的。 = 1 * GB2 鏈路層協(xié)議發(fā)現(xiàn)的路由（Direct）它的特點(diǎn)是開銷小，配置簡單，無需人工維護(hù)，只能發(fā)現(xiàn)本接口所屬網(wǎng)段拓?fù)涞穆酚伞?= 2 * GB2 手工配置的靜態(tài)路由（Static）靜態(tài)路由是一種特殊的路由，它由管理員手工配置而成。通過靜態(tài)路由的配置可建立一個互通的網(wǎng)絡(luò)，但這種配置問題在于：當(dāng)一個網(wǎng)絡(luò)故障發(fā)生后，靜態(tài)路由不會自動修正，必須有管理員的介入。靜態(tài)路由無開銷，配置簡單，適合簡單拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)。 = 3 * GB2 動態(tài)路由協(xié)議發(fā)現(xiàn)的路由（RIP、OSPF等）當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)十分復(fù)雜時，手工配置靜態(tài)路由工

13、作量大而且容易出現(xiàn)錯誤，這時就可用動態(tài)路由協(xié)議，動態(tài)（Dynamic）路由表是路由器根據(jù)網(wǎng)絡(luò)系統(tǒng)的運(yùn)行情況而自動調(diào)整的路由表。路由器根據(jù)路由選擇協(xié)議（Routing Protocol）提供的功能，自動學(xué)習(xí)和記憶網(wǎng)絡(luò)運(yùn)行情況，在需要時自動計算數(shù)據(jù)傳輸?shù)淖罴崖窂健Ｗ屍渥詣影l(fā)現(xiàn)和修改路由，無需人工維護(hù)，但動態(tài)路由協(xié)議開銷大，配置復(fù)雜。3.2IP路由選擇路由器通常依靠所建立及維護(hù)的路由表來決定如何轉(zhuǎn)發(fā)。路由表能力是指路由表內(nèi)所容納路由表項(xiàng)數(shù)量的極限。3.2.1通過RIP（路由信息協(xié)議）來實(shí)現(xiàn)路由選擇RIP（Routing information Protocol，路由信息協(xié)議）是應(yīng)用較早、使用較普遍的

14、內(nèi)部網(wǎng)關(guān)協(xié)議（Interior Gateway Protocol，IGP），適用于小型同類網(wǎng)絡(luò)的一個自治系統(tǒng)（AS）內(nèi)的路由信息的傳遞。RIP協(xié)議是基于距離矢量算法（Distance Vector Algorithms，DVA）的。它使用“跳數(shù)”，即metric來衡量到達(dá)目標(biāo)地址的路由距離。它是一個用于路由器和主機(jī)間交換路由信息的距離向量協(xié)議，目前最新的版本為v4，也就是RIPv4。 1.RIP的工作原理RIP是一種距離矢量路由協(xié)議RIP使用跳數(shù)作為路由選擇的度量。當(dāng)在進(jìn)行路由選擇是，路由表會根據(jù)最小跳數(shù)來決定轉(zhuǎn)發(fā)的路徑RIP用“路程段數(shù)”（即“跳數(shù)”）作為網(wǎng)絡(luò)距離的尺度。每個路由器在給相鄰路

15、由器發(fā)出路由信息時，都會給每個路徑加上內(nèi)部距離。在如圖3-1中，路由器3直接和網(wǎng)絡(luò)C相連。當(dāng)它向路由器2通告網(wǎng)絡(luò)的路徑時，它把跳數(shù)增加1。與之相似，路由器2把跳數(shù)增加到“2”，且通告路徑給路由器1，則Route1和Route0與Route2所在網(wǎng)絡(luò)的距離分別是1跳、2跳。圖3-1 rip的工作原理事例2.RIP報文的格式對于RIP報文有兩種版本的格式，Version 1和Version 2。兩種報文稍有不同，如圖3-2所示：圖3-2 rip報文的兩種版本格式在一開始，所有路由器中的路由表只有路由器所接入的網(wǎng)絡(luò)（共有兩個網(wǎng)絡(luò)）的情況。現(xiàn)在的路由表增加了一列，這就是從該路由表到目的網(wǎng)絡(luò)上的路由器的

16、“距離”。在圖中“下一站路由器”項(xiàng)目中有符號“”，表示直接交付。這是因?yàn)槁酚善骱屯痪W(wǎng)絡(luò)上的主機(jī)可直接通信而不需要再經(jīng)過別的路由器進(jìn)行轉(zhuǎn)發(fā)。同理，到目的網(wǎng)絡(luò)的距離也都是零，因?yàn)樾枰?jīng)過的路由器數(shù)為零。圖中粗的空心箭頭表示路由表的更新，細(xì)的箭頭表示更新路由表要用到相鄰路由表傳送過來的信息。接著，各路由器都向其相鄰路由器廣播RIP報文，這實(shí)際上就是廣播路由表中的信息。假定路由器R2先收到了路由器R1和R3的路由信息，然后就更新自己的路由表。更新后的路由表再發(fā)送給路由器R1和R3。路由器R1和R3分別再進(jìn)行更新。3.2.2通過OSPF（開放最短路徑優(yōu)先）來實(shí)現(xiàn)路由選擇OSPF是一種分層次的路由協(xié)議，

17、其層次中最大的實(shí)體是AS（自治系統(tǒng)），即遵循共同路由策略管理下的一部分網(wǎng)絡(luò)實(shí)體。在每個AS中，將網(wǎng)絡(luò)劃分為不同的區(qū)域。每個區(qū)域都有自己特定的標(biāo)識號。對于主干（backbone）區(qū)域，負(fù)責(zé)在區(qū)域之間分發(fā)鏈路狀態(tài)信息。這種分層次的網(wǎng)絡(luò)結(jié)構(gòu)是根據(jù)OSPF的實(shí)際提出來的。當(dāng)網(wǎng)絡(luò)中自治系統(tǒng)非常大時，網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)庫的內(nèi)容就更多，所以如果不分層次的話，一方面容易造成數(shù)據(jù)庫溢出，另一方面當(dāng)網(wǎng)絡(luò)中某一鏈路狀態(tài)發(fā)生變化時，會引起整個網(wǎng)絡(luò)中每個節(jié)點(diǎn)都重新計算一遍自己的路由表，既浪費(fèi)資源與時間，又會影響路由協(xié)議的性能（如聚合速度、穩(wěn)定性、靈活性等）。因此，需要把自治系統(tǒng)劃分為多個域，每個域內(nèi)部維持本域一張唯一的拓?fù)浣Y(jié)

18、構(gòu)圖，且各域根據(jù)自己的拓?fù)鋱D各自計算路由，域邊界路由器把各個域的內(nèi)部路由總結(jié)后在域間擴(kuò)散。這樣，當(dāng)網(wǎng)絡(luò)中的某條鏈路狀態(tài)發(fā)生變化時，此鏈路所在的域中的每個路由器重新計算本域路由表，而其它域中路由器只需修改其路由表中的相應(yīng)條目而無須重新計算整個路由表，節(jié)省了計算路由表的時間。OSPF的設(shè)計實(shí)現(xiàn)要涉及到指定路由器、備份指定路由器的選舉、協(xié)議包的接收、發(fā)送、泛洪機(jī)制、路由表計算等一系列問題。本文僅就Dijkstra算法與路由表的計算進(jìn)行討論。3.2.3 Dijkstra算法Dijkstra算法是路由表計算的依據(jù)，通過Dijkstra算法可以得到有關(guān)網(wǎng)絡(luò)節(jié)點(diǎn)的最短路徑樹，然后由最短路徑優(yōu)先樹得到路由表。

19、1.Dijkstra算法的描述 = 1 * GB2 初始化集合E，使之只包含源節(jié)點(diǎn)S，并初始化集合R，使之包含所有其它節(jié)點(diǎn)。初始化路徑列O，使其包含一段從S起始的路徑。這些路徑的長度值等于相應(yīng)鏈路的量度值，并以遞增順序排列列表O. = 2 * GB2 若列表O為空，或者O中第1個路徑長度為無窮大，則將R中所有剩余節(jié)點(diǎn)標(biāo)注為不可達(dá)，并終止算法。 = 3 * GB2 首先尋找列表O中的最短路徑P，從O中刪除P.設(shè)V為P的最終節(jié)點(diǎn)。若V已在集合E中，繼續(xù)執(zhí)行步驟2.否則，P為通往V的最短路徑。將V從R移至E. = 4 * GB2 建立一個與P相連并從V開始的所有鏈路構(gòu)成的侯選路徑集合。這些路徑的長度

20、是P的長度加上與P相連的長度。將這些新的鏈路插入有序表O中，并放置在其長度所對應(yīng)的等級上。繼續(xù)執(zhí)行步驟2.2.Dijkstra算法舉例以路由器A為例，來說明最短路徑樹的建立過程：1）路由器A找到了路由器B、C，將它們列入候選列表.（2）從候選列表中找出最小代價項(xiàng)B，將B加入最短路徑樹并從候選列表中刪除。接著從B開始尋找，找到了D，將其放入候選列表.（3）從列表中找出C，再由C又找到了D.但此時D的代價為4，所以不再加入候選列表。最后將D加入到最短路徑樹。此時候選列表為空，完成了最短路徑樹的計算。3.OSPF路由表的計算與實(shí)現(xiàn)有關(guān)路由表的計算是OSPF的核心內(nèi)容，它是動態(tài)生成路由器內(nèi)核路由表的基

21、礎(chǔ)。在路由表?xiàng)l目中，應(yīng)包括有目標(biāo)地址、目標(biāo)地址類型、鏈路的代價、鏈路的存活時間、鏈路的類型以及下一跳等內(nèi)容。關(guān)于整個計算的過程，主要由以下五個步驟來完成 = 1 * GB2 保存當(dāng)前路由表，當(dāng)前存在的路由表為無效的，必須從頭開始重新建立路由表； = 2 * GB2 域內(nèi)路由的計算，通過Dijkstra算法建立最短路徑樹，從而計算域內(nèi)路由； = 3 * GB2 域間路由的計算，通過檢查Summary-LSA來計算域間路由，若該路由器連到多個域，則只檢查主干域的Summary-LSA； = 4 * GB2 查看Summary-LSA：在連到一個或多個傳輸域的域邊界路由器中，通過檢查該域內(nèi)的Summ

22、ary-LSA來檢查是否有比第（2）（3）步更好的路徑； = 5 * GB2 AS外部路由的計算，通過查看AS-External-LSA來計算目的地在AS外的路由。通過以上步驟，OSPF生成了路由表。但這里的路由表還不同于路由器中實(shí)現(xiàn)路由轉(zhuǎn)發(fā)功能時用到的內(nèi)核路由表，它只是OSPF本身的內(nèi)部路由表。因此，完成上述工作后，往往還要通過路由增強(qiáng)功能與內(nèi)核路由表交互，從而實(shí)現(xiàn)多種路由協(xié)議的學(xué)習(xí)。OPSF作為一種重要的內(nèi)部網(wǎng)關(guān)協(xié)協(xié)議的普遍應(yīng)用，極大地增強(qiáng)了網(wǎng)絡(luò)的可擴(kuò)展性和穩(wěn)定性，同時也反映出了動態(tài)路由協(xié)議的強(qiáng)大功能。4詳細(xì)設(shè)計4.1各模塊的偽碼算法4.1.1RIP1.定義存儲類型的三個類：(1)網(wǎng)段類，

23、包含相鄰弧的信息（不用route_f，用next）,也可用于存儲文件讀入信息（用route_f，不用next） public:string net_id;string route_f;string route_n;Net_sec* next;(2)路由類相當(dāng)于頭結(jié)點(diǎn)class Routepublic:string route;Net_sec *next;class Net_sec(3)路由表內(nèi)容類class Contentspublic:string net_id;int diatance;string next_stop;2.路由表和網(wǎng)段類在路由表網(wǎng)段類中定義了多個函數(shù)。void open_

24、file(ifstream& infile)打開文件函數(shù)。Route_net()類的構(gòu)造函數(shù)用來表示網(wǎng)絡(luò)拓?fù)涞泥徑訝顩r，bool judge(string str)函數(shù)判斷一個路由是否已為其添加了路由表，void Init_routes()初始化路由表，void show()顯示各路由表，void change(int i) 對相鄰路由表change一下，距離加1，下一跳變?yōu)樵撀酚擅郑瑅oid update(int i) 對一個路由進(jìn)行更新操作，void UPDATE()對所有路由進(jìn)行更新路由表操作，bool neighbor(int i,int j) 判斷兩路由是否相鄰。在類中還定義了一些

25、私有的成員變量。（1）Route_net類的偽碼段：class Route_netpublic:void open_file(ifstream& infile);Route_net();/ 構(gòu)造函數(shù)bool judge(string str);void Init_routes();void show();void change(int i);void update(int i);void UPDATE();bool neighbor(int i,int j);/j和i相鄰嗎private:list li; /讀取信息存儲在這Route routeMAX; /存儲圖的信息，即各路由的鄰接表lis

26、t routesMAX; /存儲各路由路由表list temp; /用于存儲處理后的臨時路由表string flectionMAX; /用于對應(yīng)路由器與存儲序列標(biāo)號int sum; /用于統(tǒng)計路由個數(shù);（2）構(gòu)造函數(shù)Route_net:Route_net()ifstream infile;istringstream strm;string a_line;Net_sec t1;open_file(infile);while(getline(infile,a_line)strm.str(a_line);strm_idt1.route_ft1.route_n;li.push_back(t1);str

27、m.clear(); （3）判斷一個路由是否已為其添加了路由表bool Route_net:judge(string str)int i=0;while(flectioni!=&inext) p.diatance=1; _id=t-net_id; p.next_stop=直接交付; routesi.push_back(p);（5）顯示各路由表void Route_net:show()int i=0;list:iterator p;for(;isum;i+)cout This is the table of flectioniendl;for(p=routesi.begin();p!=route

28、si.end();p+)cout(*p).net_id (*p).diatance (*p).next_stopendl;（6）對相鄰路由表change一下，距離加1，下一跳變?yōu)樵撀酚擅講oid Route_net:change(int i)Contents co;temp.erase(temp.begin(),temp.end();list:iterator p=routesi.begin();for(;p!=routesi.end();p+)co.diatance=(*p).diatance+1;_id=(*p).net_id;co.next_stop=flectioni;temp.pu

29、sh_back(co);（7）對一個路由進(jìn)行更新操作void Route_net:update(int i)int count=0;list:iterator it1=routesi.begin();list:iterator it2=temp.begin();for(;it2!=temp.end();it2+)for(it1=routesi.begin();it1!=routesi.end();it1+) if(*it1).net_id=(*it2).net_id)count+;if(*it1).next_stop)=(*it2).next_stop) (*it1).diatance=(*i

30、t2).diatance; (*it1).next_stop=(*it2).next_stop;if(*it1).next_stop!=(*it2).next_stop)&(*it1).diatance(*it2).diatance) (*it1).diatance=(*it2).diatance; (*it1).next_stop=(*it2).next_stop; if(count=0) routesi.push_back(*it2); count=0;（8）對所有路由進(jìn)行更新路由表操作void Route_net:UPDATE()int j=0,i=0,I;for(I=0;Isum;I+

31、)for(j=0;jsum;j+)for(i=0;isum;i+)if(neighbor(j,i)change(i);update(j); coutThis is the I+1 runningnext)if(flectionj=p-route_n) return true;return false;4.1.2 OSPFOSPF路由協(xié)議是基于鏈路狀態(tài)的一種路由協(xié)議，通過帶寬大小來決定路徑，帶寬大者優(yōu)先。1.包含的頭文件#include #include #include #include #include #include2.結(jié)構(gòu)體定義（1）將每個路由器看成一個節(jié)點(diǎn)，用結(jié)構(gòu)體VEXTYPE來定

32、義。結(jié)構(gòu)體內(nèi)包含變量時名字name，ip地址，路由器的序號num。typedef struct /圖中頂點(diǎn)表示點(diǎn)，存放點(diǎn)名稱 char name30;char ip12;int num; VEXTYPE;（2）網(wǎng)絡(luò)拓?fù)鋱D用無向圖來表示，定義一個無向圖的結(jié)構(gòu)體MGraph，包含VEXTYPE類型的數(shù)組變量，ADJTYPE型的矩陣，int型變量來記錄頂點(diǎn)數(shù)和邊數(shù)。 typedef struct VEXTYPE vexsMAXLEN; /頂點(diǎn)的信息 ADJTYPE arcsMAXLENMAXLEN; /鄰接矩陣 int vexnum,arcnum ; /頂點(diǎn)數(shù)和邊數(shù) MGraph; /無向圖3.建立

33、無向網(wǎng)的鄰接矩陣結(jié)構(gòu)MGraph InitGraph() /*建立無向網(wǎng)的鄰接矩陣結(jié)構(gòu)*/ int i, j; MGraph G; G.vexnum =5; /存放頂點(diǎn)數(shù)G.arcnum =7; /存放邊點(diǎn)數(shù) for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,r0);strcpy(G.vexs0.ip,); strcpy(G.,r1);strcpy(G.vexs1.ip,); strcpy(G.,r2);strcpy(G.vexs2.ip,); strcpy(G.,r3)

34、;strcpy(G.vexs3.ip,); strcpy(G.,r4);strcpy(G.vexs4.ip,); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=MAX;G.arcs01=130;G.arcs12=80; G.arcs13=110; G.arcs34=75; G.arcs24=50; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij;return G;4.操作函數(shù)輸出每個頂點(diǎn)的信息：void PutOutVex(MGraph *

35、G)，輸出每條邊的信息：void PutOutArc(MGraph *G)，修改拓?fù)鋱D函數(shù)：void Change(MGraph *G)，刪除某個頂點(diǎn)：void DeleteVex(MGraph *G)，刪除某條邊：void DeleteArc(MGraph *G)，插入某條邊：void InsertArc(MGraph *G)。5.迪杰斯特拉算法求最短路徑void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路徑 int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; coutv0; if(v0G-vexnum) coutv

36、0; coutv1; if(v1G-vexnum) coutv1; for(v=0;vvexnum;v+) / 初始化final20,p2020,finalv=1即已經(jīng)求得v0到v的最短路徑， /pvw=1則是w從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)，Dv帶權(quán)長度 finalv=0; Dv=G-arcsv0v; for(w=0;wvexnum;w+) pvw=0; if(DvMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=MAX; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min

37、=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvwarcsvw; for(x=0;xvexnum;x+) pwx=pvx; pww=1; cout從到的最短路徑長度為：Dv1endl; cout路徑為：; for(int j=0;jvexnum;j+) if(pv1j=1) endl; 5調(diào)試與結(jié)果說明5.1 RIP的調(diào)試結(jié)果圖5-1 RIP調(diào)試結(jié)果圖5-1 RIP調(diào)試結(jié)果（續(xù)）5.2 OSPF的調(diào)試結(jié)果1.運(yùn)行OSPF的時候，首先會有個選擇菜單，按0時會

38、輸出網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)的信息，本實(shí)驗(yàn)中有5個節(jié)點(diǎn)r0、r1、r2、r3、r4。如圖5-2所示：圖5-2 OSPF輸出頂點(diǎn)信息2.當(dāng)按1的時候可以查看各個邊的信息，用無向圖中的權(quán)值來替代帶寬，圖中有5條鏈路分別為：（r0,r1）=130,（r1,r2）=80,（r1,r3）=110,（r2,r4）=50,(r3,r4)=75。如圖5-3所示圖5-3OSPF輸出邊的信息3.當(dāng)按2的時候可以更改節(jié)點(diǎn)間邊上權(quán)值及帶寬的信息如是更改(r1,r3)=78,調(diào)試結(jié)果如圖5-4所示：圖5-4OSPF邊更改后的信息4.當(dāng)按3的時候顯示源節(jié)點(diǎn)到目的的最短路徑及,如r0到r4,調(diào)試結(jié)果如圖5-5所示圖5-5OSPF輸出

39、最短路徑信息5.當(dāng)按4的時候顯示刪除某個節(jié)點(diǎn)，如刪除r4后顯示的節(jié)點(diǎn)信息，調(diào)試結(jié)果如圖5-6所示：圖5-6 OSPF刪除頂點(diǎn)后輸出信息6.當(dāng)按5的時候顯示刪除某個邊，如刪除(r2，r3)后顯示的邊信息，調(diào)試結(jié)果如圖5-7所示：圖5-7 OSPF刪除邊后輸出信息7.當(dāng)按6的時候顯示插入某個邊，如插入(r2,r3)后顯示的邊信息，調(diào)試結(jié)果如圖5-8所示圖5-8 OSPF刪除邊后輸出信息6.課程設(shè)計總結(jié)與體會本次課程設(shè)計主要是通過設(shè)計一個簡單的路由表查找過程的模擬來模擬實(shí)際網(wǎng)絡(luò)中路由變化的過程，以掌握這種有用的技術(shù)。要求通過距離矢量的rip協(xié)議和鏈路狀態(tài)的ospf協(xié)議來分別實(shí)現(xiàn)路由表的查找過程。在使

40、用rip和ospf協(xié)議的時候都是用到了數(shù)據(jù)結(jié)構(gòu)中圖的鄰接矩陣的存儲，帶權(quán)無向網(wǎng)的建立及Dijkstra算法的使用。在使用rip協(xié)議的網(wǎng)絡(luò)拓?fù)渲校绦蚴歉鶕?jù)兩個節(jié)點(diǎn)中的跳數(shù)來計算最優(yōu)路徑的。在ospf協(xié)議的網(wǎng)絡(luò)拓?fù)渲校歉鶕?jù)帶寬即圖中邊的權(quán)值來計算最優(yōu)路徑的。在課程設(shè)計報告的撰寫過程中，遇到了格式，字體等的不正確在老師的指導(dǎo)下都一一解決。通過實(shí)驗(yàn)使得小組各個成員對路由表的查找過程有了更清楚的認(rèn)識和理解。在實(shí)驗(yàn)過程中，通過對系統(tǒng)模擬算法的實(shí)現(xiàn)以及使用rip和ospf時的實(shí)現(xiàn)過程，加深對路由查找的了解。并在實(shí)驗(yàn)中懂得無論多復(fù)雜的問題，都可以轉(zhuǎn)化為簡單的算法模擬實(shí)現(xiàn)，使之更形象更具體。總之，此次課程設(shè)

41、計既讓該小組成員掌握了路由表查找過程原理，還提高了自身的動手能力和團(tuán)隊(duì)合作能力。參考文獻(xiàn)胡學(xué)鋼.數(shù)據(jù)結(jié)構(gòu)(C語言版)M.北京:高等教育出版社,20082 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)M.北京:高等教育出版社,20033 謝希仁.計算機(jī)網(wǎng)絡(luò)M.北京:電子工業(yè)出版社,19994 陸姚遠(yuǎn).計算機(jī)網(wǎng)絡(luò)技術(shù)M.北京:高等教育出版社,2000致謝首先我們要感謝張巧云老師在這次課程設(shè)計對我們的指導(dǎo)，張老師在我們遇到難題的過程中給予我們幫助，致使我們的這次課程設(shè)計得以順利完成。在此我們這一小組對張老師表示感謝！其次，我們還要感謝在設(shè)計中給予我們幫助的同學(xué)，他們的寶貴意見讓這次課程設(shè)計更加完善。最后還要

42、感謝我們的學(xué)校給予我們良好的的設(shè)計環(huán)境，良好的學(xué)習(xí)環(huán)境，以及優(yōu)秀的教師資源等等！在此我們該小組表示感謝！附錄RIP/以下是模擬RIP協(xié)議實(shí)現(xiàn)的C+代碼#include#include#include#include#includeusing namespace std;#define MAX 100 /最大路由數(shù)/*下面是存儲類型的三個類*/class Net_sec;/網(wǎng)段類/路由類相當(dāng)于頭結(jié)點(diǎn)class Routepublic:string route;Net_sec *next;/網(wǎng)段類，包含相鄰弧的信息（不用route_f，用next）,也可用于存儲文件讀入信息（用route_f，不用

43、next）class Net_sec public:string net_id;string route_f;string route_n;Net_sec* next;/路由表內(nèi)容類class Contentspublic:string net_id;int diatance;string next_stop;/*上面是存儲類型的三個類*/路由表和網(wǎng)段類class Route_netpublic:void open_file(ifstream& infile);Route_net();/ 構(gòu)造函數(shù)bool judge(string str);void Init_routes();void sh

44、ow();void change(int i);void update(int i);void UPDATE();bool neighbor(int i,int j);/j和i相鄰嗎private:list li; /讀取信息存儲在這Route routeMAX; /存儲圖的信息，即各路由的鄰接表list routesMAX; /存儲各路由路由表list temp; /用于存儲處理后的臨時路由表string flectionMAX; /用于對應(yīng)路由器與存儲序列標(biāo)號int sum; /用于統(tǒng)計路由個數(shù);/打開文件函數(shù)void Route_net:open_file(ifstream& infil

45、e)string filename;coutfilename;infile.open(filename+.txt).c_str();if(!infile) cerrfile open error!_idt1.route_ft1.route_n; li.push_back(t1); strm.clear(); /以上把文件內(nèi)容存入了類屬性li中l(wèi)ist:iterator it1=li.begin(),it2;int i=0;Net_sec *t2,*t3;for(;it1!=li.end();it1+) if(judge(*it1).route_f) flectioni=(*it1).route

46、_f; routei.route=flectioni; t3=t2=routei.next=new Net_sec(); for(it2=li.begin();it2!=li.end();it2+) if(flectioni=(*it2).route_f) t2-net_id=(*it2).net_id; t2-route_n=(*it2).route_n; t3=t2; t2-next=new Net_sec(); t2=t2-next; if(flectioni=(*it2).route_n) t2-net_id=(*it2).net_id; t2-route_n=(*it2).route

47、_f; t3=t2; t2-next=new Net_sec(); t2=t2-next; t3-next=NULL; i+;if(judge(*it1).route_n) flectioni=(*it1).route_n; routei.route=flectioni; t3=t2=routei.next=new Net_sec(); for(it2=li.begin();it2!=li.end();it2+) if(flectioni=(*it2).route_f) t2-net_id=(*it2).net_id; t2-route_n=(*it2).route_n; t3=t2; t2-

48、next=new Net_sec(); t2=t2-next;if(flectioni=(*it2).route_n)t2-net_id=(*it2).net_id; t2-route_n=(*it2).route_f; t3=t2; t2-next=new Net_sec(); t2=t2-next; t3-next=NULL;i+;sum=i;routei.next=NULL;/網(wǎng)絡(luò)拓?fù)鋱D的鄰接表表示法/判斷一個路由是否已為其添加了路由表bool Route_net:judge(string str)int i=0;while(flectioni!=&inext)p.diatance=1;

49、_id=t-net_id; p.next_stop=直接交付;routesi.push_back(p);/顯示各路由表void Route_net:show()int i=0;list:iterator p;for(;isum;i+)cout This is the table of flectioniendl;for(p=routesi.begin();p!=routesi.end();p+)cout(*p).net_id (*p).diatance (*p).next_stopendl; /對相鄰路由表change一下，距離加1，下一跳變?yōu)樵撀酚擅講oid Route_net:chang

50、e(int i)Contents co;temp.erase(temp.begin(),temp.end();list:iterator p=routesi.begin();for(;p!=routesi.end();p+)co.diatance=(*p).diatance+1;_id=(*p).net_id;co.next_stop=flectioni;temp.push_back(co);/對一個路由進(jìn)行更新操作void Route_net:update(int i)int count=0;list:iterator it1=routesi.begin();list:iterator it

51、2=temp.begin();for(;it2!=temp.end();it2+)for(it1=routesi.begin();it1!=routesi.end();it1+) if(*it1).net_id=(*it2).net_id) count+; if(*it1).next_stop)=(*it2).next_stop) (*it1).diatance=(*it2).diatance; (*it1).next_stop=(*it2).next_stop; if(*it1).next_stop!=(*it2).next_stop)&(*it1).diatance(*it2).diata

52、nce)(*it1).diatance=(*it2).diatance;(*it1).next_stop=(*it2).next_stop; if(count=0)routesi.push_back(*it2);count=0;/對所有路由進(jìn)行更新路由表操作void Route_net:UPDATE()int j=0,i=0,I;for(I=0;Isum;I+) for(j=0;jsum;j+) for(i=0;isum;i+)if(neighbor(j,i) change(i); update(j); coutThis is the I+1 runningnext)if(flectionj=

53、p-route_n)return true;return false;int main()Route_net route_net;route_net.Init_routes();route_net.show();route_net.UPDATE();route_net.show();return 0;/*運(yùn)行程序時要在當(dāng)前文件下創(chuàng)建一個txt文件用以輸入網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。舉例如下：文件名為net_route.txt存儲信息如下： R0 R1 R1 R2 R1 R3 R3 R4 R2 R4分別表示網(wǎng)段與連接此網(wǎng)段的兩個路由。運(yùn)行程序輸入.txt文件名：net_route即可完成功能。*/OSPF#i

54、nclude #include #include #include #include #include #define MAX 10000 #define MAXLEN 8 #define ADJTYPE int typedef struct /圖中頂點(diǎn)表示點(diǎn)，存放點(diǎn)名稱 char name30; char ip12; int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /頂點(diǎn)的信息 ADJTYPE arcsMAXLENMAXLEN; /鄰接矩陣 int vexnum,arcnum ; /頂點(diǎn)數(shù)和邊數(shù) MGraph; /無向圖MGraph

55、b; MGraph InitGraph() /*建立無向網(wǎng)的鄰接矩陣結(jié)構(gòu)*/ int i, j; MGraph G; G.vexnum =5; /存放頂點(diǎn)數(shù) G.arcnum =7; /存放邊點(diǎn)數(shù) for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,r0);strcpy(G.vexs0.ip,); strcpy(G.,r1);strcpy(G.vexs1.ip,); strcpy(G.,r2);strcpy(G.vexs2.ip,); strcpy(G.,r3);strcp

56、y(G.vexs3.ip,); strcpy(G.,r4);strcpy(G.vexs4.ip,); /*strcpy(G.,超市r5); strcpy(G.vexs5.ip,); strcpy(G.,綜合實(shí)驗(yàn)樓r6);strcpy(G.vexs6.ip,); strcpy(G.,校醫(yī)院r7);strcpy(G.vexs7.ip,); */ for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=MAX;G.arcs01=130;G.arcs12=80; G.arc

57、s13=110; G.arcs34=75; G.arcs24=50; /G.arcs34=120; /G.arcs23=265; /G.arcs35=85; /G.arcs36=400; /G.arcs46=350; /G.arcs56=120; /G.arcs47=200; /G.arcs67=150; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij;return G;void Menu() /輸出菜單 cout需要輸出頂點(diǎn)的信息請按0n; cout需要邊的信息輸出請按1n; cout需要修改請按2n; cout需要

58、求出最短路徑請按3n; cout需要刪除某個頂點(diǎn)請按4n; cout需要刪除某條邊請按5n; cout需要插入某條邊請按6n; cout需要退出請按7n; void PutOutVex(MGraph *G) /輸出每個頂點(diǎn)的信息int v; for(v=0;vvexnum;v+) coutvexsv.num vexsv.ipendl; void PutOutArc(MGraph *G) /輸出每條邊的信息for(int i=0;ivexnum;i+) for(int j=0;jvexnum;j+) if(G-arcsijMAX) cout從 到vexs

59、 arcsijendl; void Change(MGraph *G) /修改 int v0,v1,length; coutv0; cinv1; coutlength; G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路徑 int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; coutv0; if(v0G-vexnum) coutv0; coutv1; if(v1G-vexnum) coutv1; for(v=0;vvexnum;v+) / 初始化f

60、inal20,p2020,finalv=1即已經(jīng)求得v0到v的最短路徑， /pvw=1則是w從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)，Dv帶權(quán)長度 finalv=0; Dv=G-arcsv0v; for(w=0;wvexnum;w+) pvw=0; if(DvMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=MAX; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvwa