路由器查表課程設(shè)計(jì)報(bào)告

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

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

3、，最后打印實(shí)驗(yàn) 報(bào)告指導(dǎo)教師簽字：年月日系（教研室）審核意見(jiàn)：系（教研室）主任簽字：年月日目錄1 引言 12 需求分析 22.1 設(shè)計(jì)題目 22.2 設(shè)計(jì)目的 22.3 設(shè)計(jì)主要內(nèi)容及要求 22.3.1 設(shè)計(jì)內(nèi)容 22.3.2 設(shè)計(jì)要求 22.3.3 使用環(huán)境及語(yǔ)言 33 概要設(shè)計(jì) 33.1 基本功能描述 33.1.1 路由表的結(jié)構(gòu) 33.1.2 路由表的作用 43.1.3 路由表中路由的來(lái)源 43.2IP 路由選擇 43.2.1通過(guò)RIP （路由信息協(xié)議）來(lái)實(shí)現(xiàn)路由選擇 4322通過(guò)OSPF （開(kāi)放最短路徑優(yōu)先）來(lái)實(shí)現(xiàn)路由選擇 63.2.3 Dijkstra 算法 74 詳細(xì)設(shè)計(jì) 84.1

4、各模塊的偽碼算法 84.1.1RIP 84.1.2 OSPF 125調(diào)試與結(jié)果說(shuō)明 155.1 RIP 的調(diào)試結(jié)果 155.2 OSPF勺調(diào)試結(jié)果 166. 課程設(shè)計(jì)總結(jié)與體會(huì) 19參考文獻(xiàn) 19致謝 20附錄 211 引言隨著計(jì)算機(jī)信息技術(shù)的發(fā)展，大規(guī)模的互聯(lián)網(wǎng)逐漸流行起來(lái)，也為路由器的發(fā)展提供 了良好的基礎(chǔ)和平臺(tái)。作為不同網(wǎng)絡(luò)之間互相連接的樞紐，路由器系統(tǒng)構(gòu)成了基于 TCP/IP 的國(guó)際互聯(lián)網(wǎng)絡(luò) Internet 的主體脈絡(luò)。然而如何準(zhǔn)確的發(fā)送并接受信息，則需要通過(guò)路由 表的準(zhǔn)確查找，路由表存儲(chǔ)著指向特定網(wǎng)絡(luò)地址的路徑（在有些情況下，還記錄有路徑的 路由度量值）。通過(guò)路由表查找過(guò)程的設(shè)計(jì)與

5、模擬可以更好的體現(xiàn)路由的選擇，幫助我們準(zhǔn) 確的理解路由的選擇過(guò)程。2 需求分析2.1 設(shè)計(jì)題目路由器查表過(guò)程模擬2.2 設(shè)計(jì)目的該程序主要是用來(lái)模擬路由器中路由查找的過(guò)程。當(dāng)主機(jī)向目的網(wǎng)絡(luò)發(fā)送一個(gè)數(shù)據(jù)包時(shí)，對(duì)每一個(gè)IP包，當(dāng)發(fā)送到一個(gè)網(wǎng)絡(luò)拓?fù)渲械臅r(shí)候，可以分別使用RIP或OSPF協(xié)議，來(lái)決定數(shù)據(jù)包通過(guò)互聯(lián)網(wǎng)絡(luò)的路徑。通過(guò)模擬算法的實(shí)現(xiàn)，我們可以模擬一個(gè)簡(jiǎn)單的路由 查找過(guò)程，進(jìn)而找出最優(yōu)路徑，實(shí)現(xiàn)路由的查找。2.3 設(shè)計(jì)主要內(nèi)容及要求2.3.1 設(shè)計(jì)內(nèi)容1rip ：距離向量路由協(xié)議，距離向量路由協(xié)議的特征是它在進(jìn)行路由更新時(shí)，會(huì)發(fā) 送路由表的全部或一部分給鄰居路由器（這臺(tái)鄰居路由器也必須運(yùn)行ri

6、p 協(xié)議），當(dāng)路由信息通過(guò)這種方式擴(kuò)散到整個(gè)自治系統(tǒng)時(shí)，每個(gè)路由器會(huì)根據(jù) Dijkstra 算法計(jì)算出到達(dá)每個(gè) 網(wǎng)段的最優(yōu)路徑， rip 選擇到達(dá)某個(gè)網(wǎng)絡(luò)的最優(yōu)路徑根據(jù)跳數(shù)。數(shù)據(jù)包經(jīng)過(guò)一個(gè)路由器就是 一跳。2 ospf ：路由器的路由選擇是基于鏈路狀態(tài)，通過(guò) Dijkastra 算法建立起來(lái)最短路徑 樹(shù)，用該樹(shù)跟蹤系統(tǒng)中的每個(gè)目標(biāo)的最短路徑。最后再通過(guò)計(jì)算域間路由、自治系統(tǒng)外部 路由確定完整的路由表。與此同時(shí)，OSPF動(dòng)態(tài)監(jiān)視網(wǎng)絡(luò)狀態(tài)，一旦發(fā)生變化則迅速擴(kuò)散達(dá)到對(duì)網(wǎng)絡(luò)拓?fù)涞目焖倬酆?，從而確定出新的網(wǎng)絡(luò)路由表。因此，需要把自治系統(tǒng)劃分為 多個(gè)域，每個(gè)域內(nèi)部維持本域一張唯一的拓?fù)浣Y(jié)構(gòu)圖，且各域根據(jù)

7、自己的拓?fù)鋱D各自計(jì)算路由，域邊界路由器把各個(gè)域的內(nèi)部路由總結(jié)后在域間擴(kuò)散。這樣，當(dāng)網(wǎng)絡(luò)中的某條鏈路狀態(tài)發(fā)生變化時(shí)，此鏈路所在的域中的每個(gè)路由器重新計(jì)算本域路由表，而其它域中路由 器只需修改其路由表中的相應(yīng)條目而無(wú)須重新計(jì)算整個(gè)路由表，節(jié)省了計(jì)算路由表的時(shí)間。2.3.2 設(shè)計(jì)要求任意兩個(gè)節(jié)點(diǎn)，分別在 rip 和 ospf 協(xié)議的前提條件下，根據(jù)相應(yīng)的算法找出最優(yōu)路徑。 在 rip 協(xié)議中，所有的路由都由跳數(shù)來(lái)描述，到達(dá)目的地的路由最大不超過(guò) 16 跳，且只保 留唯一的一條路由，這就限制了 RIP 的服務(wù)半徑，即其只適用于小型的簡(jiǎn)單網(wǎng)絡(luò)。同時(shí)， 運(yùn)行RIP的路由器需要定期地（一般 30s）將自己的

8、路由表廣播到網(wǎng)絡(luò)當(dāng)中，達(dá)到對(duì)網(wǎng)絡(luò) 拓?fù)涞木酆希@樣不但聚合的速度慢而且極容易引起廣播風(fēng)暴、累加到無(wú)窮、路由環(huán)致命 等問(wèn)題。為此，OSPF應(yīng)運(yùn)而生。OSPF是基于鏈路狀態(tài)的路由協(xié)議，它克服了RIP的許多缺陷:第一， OSPF 不再采用跳數(shù)的概念 第二， OSPF 支持不同服務(wù)類型的不同代價(jià)，從而實(shí)現(xiàn) 不同QoS的路由服務(wù)；第三，OSPF路由器不再交換路由表，而是同步各路由器對(duì)網(wǎng)絡(luò)狀 態(tài)的認(rèn)識(shí)，即鏈路狀態(tài)數(shù)據(jù)庫(kù)，然后通過(guò) Dijkstra 最短路徑算法計(jì)算出網(wǎng)絡(luò)中各目的地址 的最優(yōu)路由。2.3.3 使用環(huán)境及語(yǔ)言編程環(huán)境: Microsoft Visual C+6.0編寫(xiě)語(yǔ)言: C+ 語(yǔ)言3 概要

9、設(shè)計(jì)3.1 基本功能描述3.1.1 路由表的結(jié)構(gòu)標(biāo)準(zhǔn)的路由表表目是一個(gè)二維組（目的網(wǎng)絡(luò)地址，下一站地址） ，其中不攜帶子網(wǎng)信息， 不能滿足子網(wǎng)尋徑。引入子網(wǎng)編址以后，路由表的每一表目中加入子網(wǎng)掩碼，于是路由表 表目變?yōu)槿S組:子網(wǎng)掩碼、目的網(wǎng)絡(luò)地址、下一站地址。表1路由表結(jié)構(gòu)及使用目的地址掩碼下一跳地址路由器依據(jù)路由表來(lái)為報(bào)文尋徑，路由表由路由協(xié)議建立和維護(hù)。路由協(xié)議的設(shè)計(jì)則 是依據(jù)某種路由算法。路由器提供了將異構(gòu)網(wǎng)互聯(lián)的機(jī)制，實(shí)現(xiàn)

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

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

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

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

14、路由器發(fā)出路由信息時(shí)，都會(huì)給每個(gè)路徑加上內(nèi)部距離。在如圖3-1中，路由器3直接和網(wǎng)絡(luò)C相連。當(dāng)它向路由器 2通告網(wǎng)絡(luò)的 路徑時(shí)，它把跳數(shù)增加 1。與之相似，路由器 2把跳數(shù)增加到“2；且通告路徑給路由器1,則Route1和RouteO與Route2所在網(wǎng)絡(luò)的距離分別是 1跳、2跳。172. 16.0 02.RIP報(bào)文的格式圖3-1 rip的工作原理事例對(duì)于RIP報(bào)文有兩種版本的格式，Version 1和Version 2。兩種報(bào)文稍有不同，如圖3-2所示:命令版本全零地址族全零IP地址全零全零度量值前20個(gè)字節(jié)的重復(fù)031(a) Version1命令版本

15、路由選擇地址族路徑標(biāo)簽IP地址子網(wǎng)掩碼下一個(gè)站點(diǎn)的IP地址度量值前20個(gè)字節(jié)的重復(fù)031MK. IB. lK.B. IMW. IMIK.(b) Version2圖3-2 rip報(bào)文的兩種版本格式在一開(kāi)始，所有路由器中的路由表只有路由器所接入的網(wǎng)絡(luò)（共有兩個(gè)網(wǎng)絡(luò)）的情況?，F(xiàn)在的路由表增加了一列，這就是從該路由表到目的網(wǎng)絡(luò)上的路由器的“距離”。在圖中“下一站路由器”項(xiàng)目中有符號(hào)“-”，表示直接交付。這是因?yàn)槁酚善骱屯痪W(wǎng)絡(luò)上的主 機(jī)可直接通信而不需要再經(jīng)過(guò)別的路由器進(jìn)行轉(zhuǎn)發(fā)。同理，到目的網(wǎng)絡(luò)的距離也都是零， 因?yàn)樾枰?jīng)過(guò)的路由器數(shù)為零。圖中粗的空心箭頭表示路由表的更新，細(xì)的箭頭表示更新 路由表要用

16、到相鄰路由表傳送過(guò)來(lái)的信息。接著，各路由器都向其相鄰路由器廣播RIP報(bào)文，這實(shí)際上就是廣播路由表中的信息。假定路由器R2先收到了路由器 R1和R3的路由信息，然后就更新自己的路由表。更 新后的路由表再發(fā)送給路由器 R1和R3。路由器R1和R3分別再進(jìn)行更新。3.2.2通過(guò)OSPF（開(kāi)放最短路徑優(yōu)先）來(lái)實(shí)現(xiàn)路由選擇OSPF是一種分層次的路由協(xié)議，其層次中最大的實(shí)體是AS （自治系統(tǒng)），即遵循共同路由策略管理下的一部分網(wǎng)絡(luò)實(shí)體。在每個(gè)AS中，將網(wǎng)絡(luò)劃分為不同的區(qū)域。每個(gè)區(qū)域都有自己特定的標(biāo)識(shí)號(hào)。對(duì)于主干（backb one）區(qū)域，負(fù)責(zé)在區(qū)域之間分發(fā)鏈路狀態(tài)信息。這種分層次的網(wǎng)絡(luò)結(jié)構(gòu)是根據(jù)OSPF的

17、實(shí)際提出來(lái)的。當(dāng)網(wǎng)絡(luò)中自治系統(tǒng)非常大時(shí)，網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)庫(kù)的內(nèi)容就更多，所以如果不分層次的話，一方面容易造成數(shù)據(jù)庫(kù)溢出，另 一方面當(dāng)網(wǎng)絡(luò)中某一鏈路狀態(tài)發(fā)生變化時(shí)，會(huì)引起整個(gè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都重新計(jì)算一遍自 己的路由表，既浪費(fèi)資源與時(shí)間，又會(huì)影響路由協(xié)議的性能（如聚合速度、穩(wěn)定性、靈活 性等）。因此，需要把自治系統(tǒng)劃分為多個(gè)域，每個(gè)域內(nèi)部維持本域一張唯一的拓?fù)浣Y(jié)構(gòu)圖， 且各域根據(jù)自己的拓?fù)鋱D各自計(jì)算路由，域邊界路由器把各個(gè)域的內(nèi)部路由總結(jié)后在域間 擴(kuò)散。這樣，當(dāng)網(wǎng)絡(luò)中的某條鏈路狀態(tài)發(fā)生變化時(shí)，此鏈路所在的域中的每個(gè)路由器重新 計(jì)算本域路由表，而其它域中路由器只需修改其路由表中的相應(yīng)條目而無(wú)須重新計(jì)算整

18、個(gè) 路由表，節(jié)省了計(jì)算路由表的時(shí)間。OSPF的設(shè)計(jì)實(shí)現(xiàn)要涉及到指定路由器、備份指定路由器的選舉、協(xié)議包的接收、發(fā) 送、泛洪機(jī)制、路由表計(jì)算等一系列問(wèn)題。本文僅就 Dijkstra 算法與路由表的計(jì)算進(jìn)行討 論。3.2.3 Dijkstra 算法Dijkstra 算法是路由表計(jì)算的依據(jù)，通過(guò) Dijkstra 算法可以得到有關(guān)網(wǎng)絡(luò)節(jié)點(diǎn)的最短路 徑樹(shù)，然后由最短路徑優(yōu)先樹(shù)得到路由表。1. Dijkstra 算法的描述 初始化集合E,使之只包含源節(jié)點(diǎn) S,并初始化集合R，使之包含所有其它節(jié)點(diǎn)。 初始化路徑列O,使其包含一段從 S起始的路徑。這些路徑的長(zhǎng)度值等于相應(yīng)鏈路的量度 值，并以遞增順序排列列表

19、 O. 若列表 O 為空，或者 O 中第 1 個(gè)路徑長(zhǎng)度為無(wú)窮大，則將 R 中所有剩余節(jié)點(diǎn)標(biāo)注 為不可達(dá)，并終止算法。 首先尋找列表 O中的最短路徑P,從O中刪除P設(shè)V為P的最終節(jié)點(diǎn)。若 V已在 集合E中，繼續(xù)執(zhí)行步驟 2否則，P為通往V的最短路徑。將 V從R移至E. 建立一個(gè)與 P 相連并從 V 開(kāi)始的所有鏈路構(gòu)成的侯選路徑集合。這些路徑的長(zhǎng)度 是P的長(zhǎng)度加上與P相連的長(zhǎng)度。將這些新的鏈路插入有序表O中，并放置在其長(zhǎng)度所對(duì)應(yīng)的等級(jí)上。繼續(xù)執(zhí)行步驟 2.2. Dijkstra 算法舉例以路由器 A 為例，來(lái)說(shuō)明最短路徑樹(shù)的建立過(guò)程： 1）路由器 A 找到了路由器 B、 C， 將它們列入候選列表

20、.（2）從候選列表中找出最小代價(jià)項(xiàng) B,將B加入最短路徑樹(shù)并從 候選列表中刪除。接著從 B開(kāi)始尋找，找到了 D，將其放入候選列表.（3）從列表中找出 C,再由C又找到了 D.但此時(shí)D的代價(jià)為4，所以不再加入候選列表。最后將 D加入到最 短路徑樹(shù)。此時(shí)候選列表為空，完成了最短路徑樹(shù)的計(jì)算。3.OSPF路由表的計(jì)算與實(shí)現(xiàn)有關(guān)路由表的計(jì)算是 OSPF的核心內(nèi)容，它是動(dòng)態(tài)生成路由器內(nèi)核路由表的基礎(chǔ)。在 路由表?xiàng)l目中，應(yīng)包括有目標(biāo)地址、目標(biāo)地址類型、鏈路的代價(jià)、鏈路的存活時(shí)間、鏈路 的類型以及下一跳等內(nèi)容。關(guān)于整個(gè)計(jì)算的過(guò)程，主要由以下五個(gè)步驟來(lái)完成保存當(dāng)前路由表，當(dāng)前存在的路由表為無(wú)效的，必須從頭開(kāi)始

21、重新建立路由表；域內(nèi)路由的計(jì)算，通過(guò) Dijkstra算法建立最短路徑樹(shù)，從而計(jì)算域內(nèi)路由；域間路由的計(jì)算，通過(guò)檢查Summary-LSA來(lái)計(jì)算域間路由，若該路由器連到多個(gè)域，則只檢查主干域的 Summary-LSA ；查看Summary-LSA :在連到一個(gè)或多個(gè)傳輸域的域邊界路由器中，通過(guò)檢查該域內(nèi) 的 Summary-LSA 來(lái)檢查是否有比第（ 2）（3）步更好的路徑；AS外部路由的計(jì)算，通過(guò)查看 AS-External-LSA來(lái)計(jì)算目的地在 AS外的路由。 通過(guò)以上步驟， OSPF 生成了路由表。但這里的路由表還不同于路由器中實(shí)現(xiàn)路由轉(zhuǎn) 發(fā)功能時(shí)用到的內(nèi)核路由表，它只是OSPF本身的內(nèi)

22、部路由表。因此，完成上述工作后，往往還要通過(guò)路由增強(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)定性，同時(shí) 也反映出了動(dòng)態(tài)路由協(xié)議的強(qiáng)大功能。4 詳細(xì)設(shè)計(jì)4.1 各模塊的偽碼算法4.1.1RIP1. 定義存儲(chǔ)類型的三個(gè)類:網(wǎng)段類，包含相鄰弧的信息（不用route_f，用next）也可用于存儲(chǔ)文件讀入信息（用 route_f，不用 next）public:string net_id;string route_f;string route_n;Net_sec* next;（2）路由類相當(dāng)于頭結(jié)點(diǎn)classRoute

23、public:string route;Net_sec *next;classNet_sec（3）路由表內(nèi)容類class Contentspublic:string net_id;int diatance;string next_stop;2. 路由表和網(wǎng)段類在路由表網(wǎng)段類中定義了多個(gè)函數(shù)。 void open_file(ifstream& infile) 打開(kāi)文件函數(shù)。Route_net()類的構(gòu)造函數(shù)用來(lái)表示網(wǎng)絡(luò)拓?fù)涞泥徑訝顩r，bool judge(string str)函數(shù)判斷一個(gè)路由是否已為其添加了路由表，void Init_routes()初始化路由表，void show()顯示各路

24、由表，void cha nge(i nt i)對(duì)相鄰路由表 change下，距離加1，下一跳變?yōu)樵撀酚擅?，voidupdate(int i)對(duì)一個(gè)路由進(jìn)行更新操作，void UPDATE。對(duì)所有路由進(jìn)行更新路由表操作，bool neighbor(int i,int j) 判斷兩路由是否相鄰。在類中還定義了一些私有的成員變量。(1) Route_net類的偽碼段： classRoute_net public:void open_file(ifstream& infile);Route_net();/ 構(gòu)造函數(shù)bool judge(string str);void Init_routes();v

25、oid show();void change(int i);void update(int i);void UPDATE();bool neighbor(int i,int j);/j 和 i 相鄰嗎private:list li; /讀取信息存儲(chǔ)在這Route routeMAX; /存儲(chǔ)圖的信息，即各路由的鄰接表list routesMAX;/存儲(chǔ)各路由路由表list temp; /用于存儲(chǔ)處理后的臨時(shí)路由表 string flectionMAX; /用于對(duì)應(yīng)路由器與存儲(chǔ)序列標(biāo)號(hào) int sum;/用于統(tǒng)計(jì)路由個(gè)數(shù);( 2)構(gòu)造函數(shù)Route_net:Route_net()ifstream

26、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); strm.clear();(3)判斷一個(gè)路由是否已為其添加了路由表bool Route_net:judge(string str)int i=0;while(flectioni!=&inext) p.diatance=1;_id=t -net_id;p.next_stop= 直

27、接交付 ;routesi.push_back(p);5) 顯示各路由表void Route_net:show()int i=0;list:iterator p;for(;isum;i+)coutThis is the table of flectioniendl;for(p=routesi.begin();p!=routesi.end();p+) cout(*p).net_id (*p).diatance (*p).next_stopendl;6) 對(duì)相鄰路由表 change 一下，距離加 1，下一跳變?yōu)樵撀酚擅?void Route_net:change(int i)Contents co

28、;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);7) 對(duì)一個(gè)路由進(jìn)行更新操作void Route_net:update(int i)int count=0;list:iterator it1=routesi.begin();list:iterator it2=temp.begin()

29、;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).diatance) (*it1).di

30、atance=(*it2).diatance;(*it1).next_stop=(*it2).next_stop; if(count=0)routesi.push_back(*it2);count=0;8) 對(duì)所有路由進(jìn)行更新路由表操作void Route_net:UPDA TE()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 running next)if(flectionj=p -route_n)r

31、eturn true; return false;4.1.2OSPFOSPF路由協(xié)議是基于鏈路狀態(tài)的一種路由協(xié)議，通過(guò)帶寬大小來(lái)決定路徑，帶寬大 者優(yōu)先。1. 包含的頭文件#include #include #include#include#include #include2. 結(jié)構(gòu)體定義（1） 將每個(gè)路由器看成一個(gè)節(jié)點(diǎn)，用結(jié)構(gòu)體VEXTYPE 來(lái)定義。結(jié)構(gòu)體內(nèi)包含變量時(shí)名 字 name， ip 地址，路由器的序號(hào) num。typedef struct/圖中頂點(diǎn)表示點(diǎn)，存放點(diǎn)名稱char name30;char ip12;int num;VEXTYPE;（2） 網(wǎng)絡(luò)拓?fù)鋱D用無(wú)向圖來(lái)表示，定義一

32、個(gè)無(wú)向圖的結(jié)構(gòu)體MGraph ，包含 VEXTYPE 類型的數(shù)組變量， ADJTYPE 型的矩陣， inttypedef structVEXTYPE vexsMAXLEN;ADJTYPE arcsMAXLENMAXLEN; int vexnum,arcnum ;MGraph;/無(wú)向圖3. 建立無(wú)向網(wǎng)的鄰接矩陣結(jié)構(gòu)MGraph InitGraph()int i, j;MGraph G;G.vexnum =5;G.arcnum =7; for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,r0);型變量來(lái)記錄頂點(diǎn)數(shù)和邊數(shù)。/頂點(diǎn)的信息/鄰

33、接矩陣 /頂點(diǎn)數(shù)和邊數(shù)/*建立無(wú)向網(wǎng)的鄰接矩陣結(jié)構(gòu) */存放頂點(diǎn)數(shù)/存放邊點(diǎn)數(shù)strcpy(G.vexs0.ip,);strcpy(G.,r1);strcpy(G.vexs1.ip,);strcpy(G.,r2);strcpy(G.vexs2.ip,);strcpy(G.,r3);strcpy(G.vexs3.ip,);strcpy(G.,r4);strcpy(G.vexs4.ip,);for(i=0;iG

34、.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ù)void void void輸出每個(gè)頂點(diǎn)的信息： void PutOutVex(MGraph *G) ，輸出每條邊的信息： PutOutArc(MGraph *G) ，修改拓?fù)鋱D函數(shù)： void Change(MGraph *G) ，

35、刪除某個(gè)頂點(diǎn)： DeleteVex(MGraph *G) ，刪除某條邊： void DeleteArc(MGraph *G) ，插入某條邊： 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)coutv0;coutv1;if(v1G -vexnum)coutv1;for(v=0;vvexnum;v+)/ 初始化 final20,p2020,finalv=

36、1 即已經(jīng)求得 v0 到 v 的最短路徑， /pvw=1 則是 w 從 v0 到 v 當(dāng)前求得最短路徑上的頂點(diǎn)， Dv 帶權(quán)長(zhǎng)度 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 -arcsvwarcsvw; for(x=

37、0;xvexnum;x+) pwx=pvx;pww=1; cout從vexsvO.name到的最短路徑長(zhǎng)度為: Dv1endl;cout 路徑為: ;for(int j=0;jvexnum;j+)if(pv1j=1)交交ab艾艾mlnb C罄.I 戀b氏 Inwlm he直血宜琶宜Hh$詈jberr曲阿 缶L靶ofOlrR0Hl_J詐 t hif1r rhnTlitfi： 1ifaR _H 0168*1x01r0ihw直R1M1192.B.V2.OfRO圖5-1 RIP調(diào)試結(jié)果Jhis.iifir-0.*1R4t l t ttL 1C f巨釋交

38、啊旦接交甘Jh*旨百 畝fl*llilaR2O1C耳吋 4吋好 tfiw-Mfi.直丙芯舊也直百R1 t t-1古H 1 a i n 29 213a dH 19 2R 33 2 km訝the宅鼻力丄 ofe Arh * IftuLe圖5-1 RIP調(diào)試結(jié)果（續(xù)）5.2 OSPF勺調(diào)試結(jié)果1運(yùn)行OSPF的時(shí)候，首先會(huì)有個(gè)選擇菜單，按0時(shí)會(huì)輸出網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)的信息，本實(shí)驗(yàn)中有5個(gè)節(jié)點(diǎn)r0、r1、r2、r3、r4。如圖5-2所示：3 4按fe: 急-#遣請(qǐng)段蕊 4i岀輕占.V晴 射鎬屢跖頂詛幻7 點(diǎn)總理亠牛圣至茂 頂信戰(zhàn)旳T-Vi 輸邊慘求膽便 要買(mǎi)雯薯要賈雯生4Bl圖5-2 OSPF俞出頂點(diǎn)信息2

39、當(dāng)按1的時(shí)候可以查看各個(gè)邊的信息，用無(wú)向圖中的權(quán)值來(lái)替代帶寬，圖中有5條鏈路分別為：（r0,r1）=130,（ r1,r2）=80,（r1,r3）=110,（ r2,r4）=50,（r3,r4）=75。如圖 5-3 所示圖5-3OSPF輸出邊的信息（r1,r3）=78,調(diào)試結(jié)果如圖5-3當(dāng)按2的時(shí)候可以更改節(jié)點(diǎn)間邊上權(quán)值及帶寬的信息如是更改4所示：十 匸r L】運(yùn)呂掃二司刃；短昭醫(yī)請(qǐng)孫丁 卜負(fù)曰.消:曲口 x圖5-4OSPF邊更改后的信息出旳喪二僚阻人!?-底f=1按 息請(qǐng) 信岀 兇輸IS信尊MS蕪1H 出囪熾出ftlalJ捕 E蟲(chóng)列tel 3 4 w SS6 息請(qǐng)請(qǐng)請(qǐng)按按 宿岀&取請(qǐng)請(qǐng) 套2

40、路叵邊邊？ 點(diǎn)息按想個(gè)按 頂信盲販某某善 的及出陳除入出 暑修求史要亜兀更要要要雯 西*誓ffift而請(qǐng)喻入結(jié)東頂點(diǎn)=基輸入源頂煜;-C:Paciiiea-ts and Sett iiigsXss522面、計(jì)算機(jī)同觀超設(shè)tfKS董畫(huà)圖5-5OSPF輸出最短路徑信息4當(dāng)按3的時(shí)候顯示源節(jié)點(diǎn)到目的的最短路徑及，如r0到r4,調(diào)試結(jié)果如圖5-5所示到理的曩短路徑長(zhǎng)度為：260徑為Z125當(dāng)按4的時(shí)候顯示刪除某個(gè)節(jié)點(diǎn)，如刪除 r4后顯示的節(jié)點(diǎn)信息，調(diào)試結(jié)果如圖5-6所示:mlalJ-1-總請(qǐng)請(qǐng) 宿岀任克請(qǐng)請(qǐng)W輸工銘預(yù)辿氈7 電鎭鰲.T*爭(zhēng)持 出射檢出除rh掃 rJil&-Efee基夢(mèng) klg堅(jiān)15誓I

41、s翦尊甌峭車(chē)尊IgMmaai歳層15W請(qǐng)校 別7f伎售職某某某僕 曼岀腳改出障I八出 輯零狂宴孌蔘圧宴STTrl 193UC6r2丄r3.1圖5-6 OSPF刪除頂點(diǎn)后輸出信息6當(dāng)按5的時(shí)候顯示刪除某個(gè)邊，如刪除 (r2，后顯示的邊信息，調(diào)試結(jié)果如圖5-7所示:sirs?-爭(zhēng)手0 1 1 1 z 3uzz必CD 7當(dāng)按6的時(shí)候顯示插入某個(gè)邊，如插入（r2,后顯示的邊信息，調(diào)試結(jié)果如圖5-8所示輸站 ”SS - - . .M- i 1 1 2 2 1 1 rpFflrr.! mumhr 1 s宦出fejct I 頂佶誦甲栗呆拯IF 出srj出 夏吁Me宣e吁尊 算U.冬亟章X壟號(hào)誼按L J 1

42、I sr.-f 町輸2略-T1邊辺？ 點(diǎn)息爲(wèi)枝 翟臺(tái)菜壬帶 出MS出吹ft入出 r口斜g資吁S口宴 凹丟翟AZ至U五瓷則胴G-60 3斤卡11C078272圖5-8 OSPF刪除邊后輸出信息6.課程設(shè)計(jì)總結(jié)與體會(huì)本次課程設(shè)計(jì)主要是通過(guò)設(shè)計(jì)一個(gè)簡(jiǎn)單的路由表查找過(guò)程的模擬來(lái)模擬實(shí)際網(wǎng)絡(luò)中路由變化的過(guò)程，以掌握這種有用的技術(shù)。要求通過(guò)距離矢量的rip協(xié)議和鏈路狀態(tài)的ospf協(xié)議來(lái)分別實(shí)現(xiàn)路由表的查找過(guò)程。在使用rip和ospf協(xié)議的時(shí)候都是用到了數(shù)據(jù)結(jié)構(gòu)中圖的鄰接矩陣的存儲(chǔ)，帶權(quán)無(wú)向網(wǎng)的建立及Dijkstra算法的使用。在使用 rip協(xié)議的網(wǎng)絡(luò)拓?fù)渲?，程序是根?jù)兩個(gè)節(jié)點(diǎn)中的跳數(shù)來(lái)計(jì)算最優(yōu)路徑的。在o

43、spf協(xié)議的網(wǎng)絡(luò)拓?fù)渲?，是根?jù)帶寬即圖中邊的權(quán)值來(lái)計(jì)算最優(yōu)路徑的。在課程設(shè)計(jì)報(bào)告的撰寫(xiě)過(guò)程中，遇到了格式， 字體等的不正確在老師的指導(dǎo)下都一一 一解決。通過(guò)實(shí)驗(yàn)使得小組各個(gè)成員對(duì)路由表的查找過(guò)程有了更清楚的認(rèn)識(shí)和理解。在實(shí)驗(yàn)過(guò)程中，通過(guò)對(duì)系統(tǒng)模擬算法的實(shí)現(xiàn)以及使用rip和ospf時(shí)的實(shí)現(xiàn)過(guò)程，加深對(duì)路由查找的了解。并在實(shí)驗(yàn)中懂得無(wú)論多復(fù)雜的問(wèn)題，都可以轉(zhuǎn)化為簡(jiǎn)單的算法模擬實(shí)現(xiàn)，使之更形 象更具體。總之，此次課程設(shè)計(jì)既讓該小組成員掌握了路由表查找過(guò)程原理，還提高了自 身的動(dòng)手能力和團(tuán)隊(duì)合作能力。參考文獻(xiàn)1 胡學(xué)鋼數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）M.北京:高等教育出版社，20082 嚴(yán)蔚敏 ,吳偉民 .數(shù)據(jù)結(jié)

44、構(gòu) （C 語(yǔ)言版 ）M. 北京 :高等教育出版社 ,20033 謝希仁 .計(jì)算機(jī)網(wǎng)絡(luò) M. 北京 :電子工業(yè)出版社 ,19994 陸姚遠(yuǎn) .計(jì)算機(jī)網(wǎng)絡(luò)技術(shù) M. 北京 :高等教育出版社 ,2000致謝首先我們要感謝張巧云老師在這次課程設(shè)計(jì)對(duì)我們的指導(dǎo)，張老師在我們遇到難題的 過(guò)程中給予我們幫助，致使我們的這次課程設(shè)計(jì)得以順利完成。在此我們這一小組對(duì)張老 師表示感謝！其次，我們還要感謝在設(shè)計(jì)中給予我們幫助的同學(xué)，他們的寶貴意見(jiàn)讓這次 課程設(shè)計(jì)更加完善。最后還要感謝我們的學(xué)校給予我們良好的的設(shè)計(jì)環(huán)境，良好的學(xué)習(xí)環(huán) 境，以及優(yōu)秀的教師資源等等！在此我們?cè)撔〗M表示感謝！附錄RIP/以下是模擬 RIP

45、協(xié)議實(shí)現(xiàn)的 C+ 代碼#include#include#include#include#includeusing namespacestd;#define MAX 100/最大路由數(shù)/*下面是存儲(chǔ)類型的三個(gè)類*/class Net_sec; 網(wǎng)段類/路由類相當(dāng)于頭結(jié)點(diǎn)class Routepublic:string route;Net_sec *next;/網(wǎng)段類，包含相鄰弧的信息（不用route_f,用next）也可用于存儲(chǔ)文件讀入信息（用route_f，不用 next） class Net_secpublic:string net_id;string route_f;string rout

46、e_n;Net_sec* next;/路由表內(nèi)容類class Contentspublic:string net_id;int diatance;string next_stop;/*上面是存儲(chǔ)類型的三個(gè)類*/ /路由表和網(wǎng)段類 class Route_net public: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; /讀取信息存儲(chǔ)在這Route routeMAX; /存儲(chǔ)圖的信息，即各路由的鄰接表 list routesMAX;/存儲(chǔ)各路由路由表list temp; / 用于存儲(chǔ)處理后的臨時(shí)路由表 string flectionMAX; /用于對(duì)應(yīng)路由器與存儲(chǔ)序列標(biāo)號(hào) int sum;/ 用于統(tǒng)計(jì)路由個(gè)數(shù);/打開(kāi)文件函數(shù)void Route_net:open_file(ifstream& infile)string filename;coutfilename;infile.o