路由器查表過程模擬

1、課課程程設設計計報報告告課程名稱：課程名稱： 局域網(wǎng)技術 設計題目設計題目： 路由表查找過程模擬 系系 別：別： 計算機與信息工程學院 專專 業(yè)：業(yè)： 網(wǎng)絡工程 組組 別：別： 第一組 起止日期起止日期: 2012 年 6 月 11 日 2012 年 6 月 24 日指導教師指導教師: 計算機科學與技術系二計算機科學與技術系二一二年制一二年制課程設計任務書課程設計任務書課程設計題目路由表的查找模擬組長學號班級院部計算機與信息工程學院專業(yè)網(wǎng)絡工程組員 指導教師課程設計目的通過課程設計,加深對路由表的理解,掌握路由表查找的基本原理及功能,具有初步分析實際路由表的組成、構造，并具備準確查找路由表的能

2、力。課程設計所需環(huán)境Windows XP，VC+6.0課程設計任務要求本設計的目的是通過設計一個簡單的路由表查找過程的模擬來模擬實際網(wǎng)絡中路由變化的過程，以掌握這種有用的技術。要求通過距離矢量的 rip 協(xié)議和鏈路狀態(tài)的ospf 協(xié)議來分別實現(xiàn)路由表的查找過程。課程設計工作進度計劃序號起止日期工 作 內(nèi) 容分工情況12012.6.11開會分析討論，作工作分工史言負責對小組成員進行分工26.126.12作具體分析，查詢相關資料36.136.15編寫源代碼46.166.17對源程序進行調(diào)試56.186.22寫課程設計報告66.236.24與老師交流，完善報告，并打印教研室審核意見：教研室主任簽字：

3、 年 月 日目目 錄錄1 引言引言 .12 需求分析需求分析 .12.1 設計目的.12.2 設計主要內(nèi)容及要求.12.2.1 設計內(nèi)容 .12.2.2 設計要求.22.2.3 使用環(huán)境及語言 .23 概要設計概要設計 .23.1 基本功能描述.23.1.1 路由表的結構.23.1.2 路由表的作用.23.1.3 路由表中路由的來源.33.2 IP 路由選擇.33.2.1 通過 RIP(路由信息協(xié)議)來實現(xiàn)路由選擇 .33.2.2 通過 OSPF(開放最短路徑優(yōu)先)來實現(xiàn)路由選擇 .53.2.3 Dijkstra 算法.5詳細設計詳細設計 .64.1 各模塊的偽碼算法.64.1.1 RIP .

4、64.1.2 ospf .105 調(diào)試與結果說明調(diào)試與結果說明 .135.1.RIP的調(diào)試結果 .135.2.OSPF調(diào)試結果.14課程設計總結與體會課程設計總結與體會 .17致謝致謝 .17參考文獻參考文獻 .18附錄附錄 .18局域網(wǎng)技術課程設計1課程設計的主要內(nèi)容課程設計的主要內(nèi)容1 引言引言隨著計算機信息技術的發(fā)展，大規(guī)模的互聯(lián)網(wǎng)逐漸流行起來，也為路由器的發(fā)展提供了良好的基礎和平臺。作為不同網(wǎng)絡之間互相連接的樞紐，路由器系統(tǒng)構成了基于 TCP/IP 的國際互聯(lián)網(wǎng)絡 Internet 的主體脈絡。然而如何準確的發(fā)送并接受信息，則需要通過路由表的準確查找，路由表存儲著指向特定網(wǎng)絡地址的路徑

5、（在有些情況下，還記錄有路徑的路由度量值） 。通過路由表查找過程的設計與模擬可以更好的體現(xiàn)路由的選擇，幫助我們準確的理解路由的選擇過程。2 需求分析需求分析2.1 設計設計目的目的該程序主要是用來模擬路由器中路由查找的過程。當主機向目的網(wǎng)絡發(fā)送一個數(shù)據(jù)包時，對每一個 IP 包，當發(fā)送到一個網(wǎng)絡拓撲中的時候，可以分別使用 RIP 或 OSPF 協(xié)議，來決定數(shù)據(jù)包通過互聯(lián)網(wǎng)絡的路徑。通過模擬算法的實現(xiàn)，我們可以模擬一個簡單的路由查找過程，進而找出最優(yōu)路徑，實現(xiàn)路由的查找2.2 設計主要內(nèi)容及要求設計主要內(nèi)容及要求2.2.1 設計內(nèi)容設計內(nèi)容1rip：距離向量路由協(xié)議，距離向量路由協(xié)議的特征是它在進

6、行路由更新時，會發(fā)送路由表的全部或一部分給鄰居路由器（這臺鄰居路由器也必須運行 rip 協(xié)議） ，當路由信息通過這種方式擴散到整個自治系統(tǒng)時，每個路由器會根據(jù) Dijkstra 算法計算出到達每個網(wǎng)段的最優(yōu)路徑，rip 選擇到達某個網(wǎng)絡的最優(yōu)路徑根據(jù)跳數(shù)。數(shù)據(jù)包經(jīng)過一個路由器就是一跳。2 ospf：路由器的路由選擇是基于鏈路狀態(tài)，通過 Dijkastra 算法建立起來最短路徑樹，用該樹跟蹤系統(tǒng)中的每個目標的最短路徑。最后再通過計算域間路由、自治系統(tǒng)外部路由確定完整的路由表。與此同時，OSPF 動態(tài)監(jiān)視網(wǎng)絡狀態(tài)，一旦發(fā)生變化則迅速擴散達到對網(wǎng)絡拓撲的快速聚合，從而確定出新的網(wǎng)絡路由表。因此，需要

7、把自治系統(tǒng)劃分為多個域，每個域內(nèi)部維持本域一張唯一的拓撲結構圖，且各域根據(jù)自己的拓撲圖各自計算路由，域邊界路由器把各個域的內(nèi)部路由總結后在域間擴散。這樣，當網(wǎng)絡中的某條鏈路狀態(tài)發(fā)生變化時，此鏈路所在的域中的每個路由器重新計算本域路由表，而其它域中路由器只需修改其路由表中的相應條目而無須重新計算整個路由表，節(jié)省了計算路由表的時間。局域網(wǎng)技術課程設計22.2.2 設計要求設計要求任意兩個節(jié)點，分別在 rip 和 ospf 協(xié)議的前提條件下，根據(jù)相應的算法找出最優(yōu)路徑。在 rip 協(xié)議中，所有的路由都由跳數(shù)來描述，到達目的地的路由最大不超過 16 跳，且只保留唯一的一條路由，這就限制了 RIP 的服

8、務半徑，即其只適用于小型的簡單網(wǎng)絡。同時，運行 RIP 的路由器需要定期地（一般 30s）將自己的路由表廣播到網(wǎng)絡當中，達到對網(wǎng)絡拓撲的聚合，這樣不但聚合的速度慢而且極容易引起廣播風暴、累加到無窮、路由環(huán)致命等問題。為此，OSPF 應運而生。OSPF 是基于鏈路狀態(tài)的路由協(xié)議，它克服了 RIP 的許多缺陷：第一，OSPF 不再采用跳數(shù)的概念第二，OSPF 支持不同服務類型的不同代價，從而實現(xiàn)不同 QoS 的路由服務；第三，OSPF 路由器不再交換路由表，而是同步各路由器對網(wǎng)絡狀態(tài)的認識，即鏈路狀態(tài)數(shù)據(jù)庫，然后通過 Dijkstra 最短路徑算法計算出網(wǎng)絡中各目的地址的最優(yōu)路由。2.2.3 使用

9、環(huán)境及語言使用環(huán)境及語言編程環(huán)境：Microsoft Visual C+6.0編寫語言：C+語言3 概要設計概要設計3.1 基本功能描述基本功能描述3.1.1 路由表的結構路由表的結構標準的路由表表目是一個二維組（目的網(wǎng)絡地址，下一站地址） ，其中不攜帶子網(wǎng)信息，不能滿足子網(wǎng)尋徑。引入子網(wǎng)編址以后，路由表的每一表目中加入子網(wǎng)掩碼，于是路由表表目變?yōu)槿S組：子網(wǎng)掩碼、目的網(wǎng)絡地址、下一站地址。 表 1 路由表結構及使用表 1 路由表結構及使用目的地址掩碼下一跳地址255.25

10、5.255.0路由器依據(jù)路由表來為報文尋徑，路由表由路由協(xié)議建立和維護。路由協(xié)議的設計則是依據(jù)某種路由算法。 路由器提供了將異構網(wǎng)互聯(lián)的機制，實現(xiàn)將一個數(shù)據(jù)包從一個網(wǎng)絡發(fā)送到另一個網(wǎng)絡。路由就是指導 IP 數(shù)據(jù)包發(fā)送的路徑信息局域網(wǎng)技術課程設計33.1.2 路由表的作用路由表的作用路由器的主要工作就是為經(jīng)過路由器的每個數(shù)據(jù)幀尋找一條最佳傳輸路徑，并將該數(shù)據(jù)有效地傳送到目的站點。由此可見，選擇最佳路徑的策略即路由算法是路由器的關鍵所在。為了完成這項工作，在路由器中保存著各種傳輸路徑的相關數(shù)據(jù)路由表（Routing Table） ，供路由選擇時使用。打個比方，路由表就像我們平時使用

11、的地圖一樣，標識著各種路線，路由表中保存著子網(wǎng)的標志信息、網(wǎng)上路由器的個數(shù)和下一個路由器的名字等內(nèi)容。路由表可以是由系統(tǒng)管理員固定設置好的，也可以由系統(tǒng)動態(tài)修改，可以由路由器自動調(diào)整，也可以由主機控制。3.1.3 路由表中路由的來源路由表中路由的來源在路由表中有一個 Protocol 字段，指明了路由的來源，即路由是如何生成的。 鏈路層協(xié)議發(fā)現(xiàn)的路由（Direct）它的特點是開銷小，配置簡單，無需人工維護，只能發(fā)現(xiàn)本接口所屬網(wǎng)段拓撲的路由。 手工配置的靜態(tài)路由（Static）靜態(tài)路由是一種特殊的路由，它由管理員手工配置而成。通過靜態(tài)路由的配置可建立一個互通的網(wǎng)絡，但這種配置問題在于：當一個網(wǎng)絡

12、故障發(fā)生后，靜態(tài)路由不會自動修正，必須有管理員的介入。靜態(tài)路由無開銷，配置簡單，適合簡單拓撲結構的網(wǎng)絡。 動態(tài)路由協(xié)議發(fā)現(xiàn)的路由（RIP、OSPF 等）當網(wǎng)絡拓撲結構十分復雜時，手工配置靜態(tài)路由工作量大而且容易出現(xiàn)錯誤，這時就可用動態(tài)路由協(xié)議，動態(tài)（Dynamic）路由表是路由器根據(jù)網(wǎng)絡系統(tǒng)的運行情況而自動調(diào)整的路由表。路由器根據(jù)路由選擇協(xié)議（Routing Protocol）提供的功能，自動學習和記憶網(wǎng)絡運行情況，在需要時自動計算數(shù)據(jù)傳輸?shù)淖罴崖窂?。讓其自動發(fā)現(xiàn)和修改路由，無需人工維護，但動態(tài)路由協(xié)議開銷大，配置復雜。3.2 IP 路由選擇路由選擇路由器通常依靠所建立及維護的路由表來決定如何

13、轉(zhuǎn)發(fā)。路由表能力是指路由表內(nèi)所容納路由表項數(shù)量的極限。3.2.1 通過通過 RIP(路由信息協(xié)議路由信息協(xié)議)來實現(xiàn)路由選擇來實現(xiàn)路由選擇RIP（Routing information Protocol，路由信息協(xié)議）是應用較早、使用較普遍的內(nèi)部網(wǎng)關協(xié)議（Interior Gateway Protocol，IGP） ，適用于小型同類網(wǎng)絡的一個自治系統(tǒng)（AS）內(nèi)的路由信息的傳遞。RIP 協(xié)議是基于距離矢量算法（Distance Vector Algorithms，DVA）的。它使用“跳數(shù)”，即 metric 來衡量到達目標地址的路由距離。它是一個用于路由器和主機間交換路由信息的距離向量協(xié)議，目前

14、最新的版本為 v4，也就是 RIPv4。 1.RIP 的工作原理局域網(wǎng)技術課程設計4RIP 是一種距離矢量路由協(xié)議 RIP 使用跳數(shù)作為路由選擇的度量。當在進行路由選擇是，路由表會根據(jù)最小跳數(shù)來決定轉(zhuǎn)發(fā)的路徑 RIP 用“路程段數(shù)”（即“跳數(shù)”）作為網(wǎng)絡距離的尺度。每個路由器在給相鄰路由器發(fā)出路由信息時，都會給每個路徑加上內(nèi)部距離。在如圖 3-1 中，路由器 3 直接和網(wǎng)絡 C 相連。當它向路由器 2 通告網(wǎng)絡 的路徑時，它把跳數(shù)增加 1。與之相似，路由器 2 把跳數(shù)增加到“2”，且通告路徑給路由器1，則 Route1 和 Route0 與 Route2 所在網(wǎng)絡 172

15、.16.0.0 的距離分別是 1 跳、2 跳。圖 3-1 rip 的工作原理事例2.RIP 報文的格式對于 RIP 報文有兩種版本的格式，Version 1 和 Version 2。兩種報文稍有不同，如圖 3-2 所示： 命令 版本 路由選擇 地址族 路徑標簽 IP 地址 子網(wǎng)掩碼 下一個站點的 IP 地址 度量值 前 20 個字節(jié)的重復 命令 版本 全零 地址族 全零 IP 地址 全零 全零 度量值 前 20 個字節(jié)的重復 (a) Version 1 (b) Version 2 0 31 0 31 圖 3-2 rip 報文的兩種版本格式局域網(wǎng)技術課程設計5在一開始，所有路由器中的路由表只有路

16、由器所接入的網(wǎng)絡（共有兩個網(wǎng)絡）的情況?，F(xiàn)在的路由表增加了一列，這就是從該路由表到目的網(wǎng)絡上的路由器的“距離” 。在圖中“下一站路由器”項目中有符號“” ，表示直接交付。這是因為路由器和同一網(wǎng)絡上的主機可直接通信而不需要再經(jīng)過別的路由器進行轉(zhuǎn)發(fā)。同理，到目的網(wǎng)絡的距離也都是零，因為需要經(jīng)過的路由器數(shù)為零。圖中粗的空心箭頭表示路由表的更新，細的箭頭表示更新路由表要用到相鄰路由表傳送過來的信息。接著，各路由器都向其相鄰路由器廣播 RIP 報文，這實際上就是廣播路由表中的信息。假定路由器 R2 先收到了路由器 R1 和 R3 的路由信息，然后就更新自己的路由表。更新后的路由表再發(fā)送給路由器 R1 和

17、 R3。路由器 R1 和 R3 分別再進行更新。3.2.2 通過通過 OSPF(開放最短路徑優(yōu)先開放最短路徑優(yōu)先)來實現(xiàn)路由選擇來實現(xiàn)路由選擇OSPF 是一種分層次的路由協(xié)議，其層次中最大的實體是 AS（自治系統(tǒng)） ，即遵循共同路由策略管理下的一部分網(wǎng)絡實體。在每個 AS 中，將網(wǎng)絡劃分為不同的區(qū)域。每個區(qū)域都有自己特定的標識號。對于主干（backbone）區(qū)域，負責在區(qū)域之間分發(fā)鏈路狀態(tài)信息。這種分層次的網(wǎng)絡結構是根據(jù) OSPF 的實際提出來的。當網(wǎng)絡中自治系統(tǒng)非常大時，網(wǎng)絡拓撲數(shù)據(jù)庫的內(nèi)容就更多，所以如果不分層次的話，一方面容易造成數(shù)據(jù)庫溢出，另一方面當網(wǎng)絡中某一鏈路狀態(tài)發(fā)生變化時，會引起

18、整個網(wǎng)絡中每個節(jié)點都重新計算一遍自己的路由表，既浪費資源與時間，又會影響路由協(xié)議的性能（如聚合速度、穩(wěn)定性、靈活性等） 。因此，需要把自治系統(tǒng)劃分為多個域，每個域內(nèi)部維持本域一張唯一的拓撲結構圖，且各域根據(jù)自己的拓撲圖各自計算路由，域邊界路由器把各個域的內(nèi)部路由總結后在域間擴散。這樣，當網(wǎng)絡中的某條鏈路狀態(tài)發(fā)生變化時，此鏈路所在的域中的每個路由器重新計算本域路由表，而其它域中路由器只需修改其路由表中的相應條目而無須重新計算整個路由表，節(jié)省了計算路由表的時間。OSPF 的設計實現(xiàn)要涉及到指定路由器、備份指定路由器的選舉、協(xié)議包的接收、發(fā)送、泛洪機制、路由表計算等一系列問題。本文僅就 Dijkst

19、ra 算法與路由表的計算進行討論。3.2.3 Dijkstra 算法算法Dijkstra 算法是路由表計算的依據(jù)，通過 Dijkstra 算法可以得到有關網(wǎng)絡節(jié)點的最短路徑樹，然后由最短路徑優(yōu)先樹得到路由表。1.Dijkstra 算法的描述 初始化集合 E，使之只包含源節(jié)點 S，并初始化集合 R，使之包含所有其它節(jié)點。初始化路徑列 O，使其包含一段從 S 起始的路徑。這些路徑的長度值等于相應鏈路的量度值，并以遞增順序排列列表 O. 若列表 O 為空，或者 O 中第 1 個路徑長度為無窮大，則將 R 中所有剩余節(jié)點標注局域網(wǎng)技術課程設計6為不可達，并終止算法。 首先尋找列表 O 中的最短路徑 P

20、，從 O 中刪除 P.設 V 為 P 的最終節(jié)點。若 V 已在集合 E 中，繼續(xù)執(zhí)行步驟 2.否則，P 為通往 V 的最短路徑。將 V 從 R 移至 E. 建立一個與 P 相連并從 V 開始的所有鏈路構成的侯選路徑集合。這些路徑的長度是 P 的長度加上與 P 相連的長度。將這些新的鏈路插入有序表 O 中，并放置在其長度所對應的等級上。繼續(xù)執(zhí)行步驟 2.2.Dijkstra 算法舉例以路由器 A 為例，來說明最短路徑樹的建立過程：1）路由器 A 找到了路由器 B、C，將它們列入候選列表.（2）從候選列表中找出最小代價項 B，將 B 加入最短路徑樹并從候選列表中刪除。接著從 B 開始尋找，找到了

21、D，將其放入候選列表.（3）從列表中找出C，再由 C 又找到了 D.但此時 D 的代價為 4，所以不再加入候選列表。最后將 D 加入到最短路徑樹。此時候選列表為空，完成了最短路徑樹的計算。3.OSPF 路由表的計算與實現(xiàn)有關路由表的計算是 OSPF 的核心內(nèi)容，它是動態(tài)生成路由器內(nèi)核路由表的基礎。在路由表條目中，應包括有目標地址、目標地址類型、鏈路的代價、鏈路的存活時間、鏈路的類型以及下一跳等內(nèi)容。關于整個計算的過程，主要由以下五個步驟來完成保存當前路由表，當前存在的路由表為無效的，必須從頭開始重新建立路由表；域內(nèi)路由的計算，通過 Dijkstra 算法建立最短路徑樹，從而計算域內(nèi)路由；域間路

22、由的計算，通過檢查 Summary-LSA 來計算域間路由，若該路由器連到多個域，則只檢查主干域的 Summary-LSA；查看 Summary-LSA：在連到一個或多個傳輸域的域邊界路由器中，通過檢查該域內(nèi)的 Summary-LSA 來檢查是否有比第（2） （3）步更好的路徑；AS 外部路由的計算，通過查看 AS-External-LSA 來計算目的地在 AS 外的路由。通過以上步驟，OSPF 生成了路由表。但這里的路由表還不同于路由器中實現(xiàn)路由轉(zhuǎn)發(fā)功能時用到的內(nèi)核路由表，它只是 OSPF 本身的內(nèi)部路由表。因此，完成上述工作后，往往還要通過路由增強功能與內(nèi)核路由表交互，從而實現(xiàn)多種路由協(xié)議

23、的學習。OPSF 作為一種重要的內(nèi)部網(wǎng)關協(xié)協(xié)議的普遍應用，極大地增強了網(wǎng)絡的可擴展性和穩(wěn)定性，同時也反映出了動態(tài)路由協(xié)議的強大功能。詳細設計詳細設計4.1 各模塊的偽碼算法各模塊的偽碼算法4.1.1 RIP 1.定義存儲類型的三個類：(1)網(wǎng)段類，包含相鄰弧的信息（不用 route_f，用 next）,也可用于存儲文件讀入信息局域網(wǎng)技術課程設計7（用 route_f，不用 next） public:string net_id;string route_f;string route_n;Net_sec* next;(2)路由類相當于頭結點class Routepublic:string rout

24、e;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_file(ifstream& infile)打開文件函數(shù)。Route_net()類的構造函數(shù)用來表示網(wǎng)絡拓撲的鄰接狀況，bool judge(string str)函數(shù)判斷一個路由是否已為其添加了路由表，void Init_routes()初始化路由表，void show()顯示各路由表，void change(int i

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

26、change(int i);void update(int i);void UPDATE();bool neighbor(int i,int j);/j 和 i 相鄰嗎private:list li; /讀取信息存儲在這Route routeMAX; /存儲圖的信息，即各路由的鄰接表局域網(wǎng)技術課程設計8list routesMAX; /存儲各路由路由表list temp; /用于存儲處理后的臨時路由表string flectionMAX; /用于對應路由器與存儲序列標號int sum; /用于統(tǒng)計路由個數(shù);（2）構造函數(shù)Route_net:Route_net()ifstream infile;

27、istringstream strm;string a_line;Net_sec t1;open_file(infile);while(getline(infile,a_line)strm.str(a_line);_idt1.route_ft1.route_n;li.push_back(t1);strm.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.pu

28、sh_back(p);（5）顯示各路由表void Route_net:show()局域網(wǎng)技術課程設計9int 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;（6）對相鄰路由表 change 一下，距離加 1，下一跳變?yōu)樵撀酚擅講oid Route_net:change(int i)Contents co;temp.

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

30、!=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).diatance=(*it2).di

31、atance;(*it1).next_stop=(*it2).next_stop;if(count=0)routesi.push_back(*it2);count=0;局域網(wǎng)技術課程設計10（8）對所有路由進行更新路由表操作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 running.next)if(flectionj=p-route_n)return true

32、;return false;4.1.2 ospfOSPF 路由協(xié)議是基于鏈路狀態(tài)的一種路由協(xié)議，通過帶寬大小來決定路徑，帶寬大者優(yōu)先。1.包含的頭文件#include #include #include #include #include #include2.結構體定義（1）將每個路由器看成一個節(jié)點，用結構體 VEXTYPE 來定義。結構體內(nèi)包含變量時名字 name，ip 地址，路由器的序號 num。typedef struct /圖中頂點表示點，存放點名稱 char name30;char ip12;局域網(wǎng)技術課程設計11int num; VEXTYPE;（2）網(wǎng)絡拓撲圖用無向圖來表示，定義

33、一個無向圖的結構體 MGraph，包含 VEXTYPE 類型的數(shù)組變量，ADJTYPE 型的矩陣，int 型變量來記錄頂點數(shù)和邊數(shù)。 typedef struct VEXTYPE vexsMAXLEN; /頂點的信息 ADJTYPE arcsMAXLENMAXLEN; /鄰接矩陣 int vexnum,arcnum ; /頂點數(shù)和邊數(shù) MGraph; /無向圖3.建立無向網(wǎng)的鄰接矩陣結構MGraph InitGraph() /*建立無向網(wǎng)的鄰接矩陣結構*/ int i, j; MGraph G; G.vexnum =5; /存放頂點數(shù)G.arcnum =7; /存放邊點數(shù) for(i=0;iG

34、.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);strcpy(G.vexs3.ip,); strcpy(G.,r4);strcpy(G.vexs4.ip,192.168

35、.4.1); 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ù)局域網(wǎng)技術課程設計12輸出每個頂點的信息：void PutOutVex(MGraph *G)，輸出每條邊的信息：void PutOutArc(MGraph *G)，修改拓撲圖函數(shù)：voi

36、d Change(MGraph *G)，刪除某個頂點：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) coutv0; coutv1; if(v1G-vexnum) coutv1; for(v=0;vvexnum

37、;v+) / 初始化 final20,p2020,finalv=1 即已經(jīng)求得 v0 到 v 的最短路徑， /pvw=1 則是 w 從 v0 到 v 當前求得最短路徑上的頂點，Dv帶權長度 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; 局域網(wǎng)技術課程設計13 for(w=0;w

38、vexnum;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)試與結果說明調(diào)試與結果說明5.1.rip 的調(diào)試結果的調(diào)試結果當網(wǎng)絡拓撲中使用 rip 的時候，最短路徑的查找如圖 5-1 所示局域網(wǎng)技術課程設計14圖 5-1 rip 調(diào)試結果圖 5-1 rip 調(diào)試結果（續(xù)）5

39、.2.ospf 調(diào)試結果調(diào)試結果1.運行 ospf 的時候，首先會有個選擇菜單，按 0 時會輸出網(wǎng)絡拓撲中節(jié)點的信息，本實驗中有 5 個節(jié)點 r0、r1、r2、r3、r4。如圖 5-2 所示：圖 5-2 ospf 輸出頂點信息2.當按 1 的時候可以查看各個邊的信息，用無向圖中的權值來替代帶寬，圖中有 5 條鏈路分別為：（r0,r1）=130,（r1,r2）=80,（r1,r3）=110,（r2,r4）=50,(r3,r4)=75。如圖 5-3 所示：局域網(wǎng)技術課程設計15圖 5-3 ospf 輸出邊的信息3.當按 2 的時候可以更改節(jié)點間邊上權值及帶寬的信息如是更改(r1,r3)=78,調(diào)試

40、結果如圖 5-4 所示：圖 5-4 ospf 邊更改后信息4.當按 3 的時候顯示源節(jié)點到目的的最短路徑及,如 r0 到 r4,調(diào)試結果如圖 5-5 所示：局域網(wǎng)技術課程設計16圖 5-5 ospf 輸出最短路徑信息5.當按 4 的時候顯示刪除某個節(jié)點，如刪除 r4 后顯示的節(jié)點信息，調(diào)試結果如圖 5-6 所示：圖 5-6 ospf 刪除頂點后輸出信息6.當按 5 的時候顯示刪除某個邊，如刪除(r2，r3)后顯示的邊信息，調(diào)試結果如圖 5-7 所示：局域網(wǎng)技術課程設計17圖 5-7ospf 刪除邊后輸出信息7.當按 6 的時候顯示插入某個邊，如插入(r2,r3)后顯示的邊信息，調(diào)試結果如圖 5

41、-8 所示：圖 5-8 ospf 刪除邊后輸出信息課程設計總結與體會課程設計總結與體會本次課程設計主要是通過設計一個簡單的路由表查找過程的模擬來模擬實際網(wǎng)絡中路由變化的過程，以掌握這種有用的技術。要求通過距離矢量的 rip 協(xié)議和鏈路狀態(tài)的 ospf協(xié)議來分別實現(xiàn)路由表的查找過程。在使用 rip 和 ospf 協(xié)議的時候都是用到了數(shù)據(jù)結構中圖的鄰接矩陣的存儲，帶權無向網(wǎng)的建立及 Dijkstra 算法的使用。在使用 rip 協(xié)議的網(wǎng)絡拓撲中，程序是根據(jù)兩個節(jié)點中的跳數(shù)來計算最優(yōu)路徑的。在 ospf 協(xié)議的網(wǎng)絡拓撲中，是根據(jù)帶寬即圖中邊的權值來計算最優(yōu)路徑的。在課程設計報告的撰寫過程中，遇到了格

42、式，字體等的不正確在老師的指導下都一一解決。通過實驗使得小組各個成員對路由表的查找過程有了更清楚的認識和理解。在實驗過程中，通過對系統(tǒng)模擬算法的實現(xiàn)以及使用 rip 和 ospf 時的實現(xiàn)過程，加深對路由查找的局域網(wǎng)技術課程設計18了解。并在實驗中懂得無論多復雜的問題，都可以轉(zhuǎn)化為簡單的算法模擬實現(xiàn)，使之更形象更具體。總之，此次課程設計既讓該小組成員掌握了路由表查找過程原理，還提高了自身的動手能力和團隊合作能力。致謝致謝首先我們要感謝胡老師在這一學期里對我們的教育，他教會我們的知識對這次課程設計起到關鍵作用。在此我們這一小組對劉老師表示感謝！其次，我們還要感謝在設計中給予我們幫助的同學，最后還

43、要感謝我們的母校給予我們良好的的設計環(huán)境，良好的學習環(huán)境，以及優(yōu)秀的教師資源等等！在此我們該小組表示感謝！參考文獻參考文獻1胡學鋼.數(shù)據(jù)結構(C 語言版)M.北京:高等教育出版社,20082 嚴蔚敏,吳偉民.數(shù)據(jù)結構(C 語言版)M.北京:高等教育出版社,20033 謝希仁.計算機網(wǎng)絡M.北京:電子工業(yè)出版社,19994 陸姚遠.計算機網(wǎng)絡技術M.北京:高等教育出版社,2000附錄附錄Ospf:#include #include #include #include #include #include #define MAX 10000 #define MAXLEN 8 #define ADJT

44、YPE int typedef struct /圖中頂點表示點，存放點名稱 char name30;char ip12; int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /頂點的信息 ADJTYPE arcsMAXLENMAXLEN; /鄰接矩陣 int vexnum,arcnum ; /頂點數(shù)和邊數(shù) MGraph; /無向圖MGraph b; MGraph InitGraph()局域網(wǎng)技術課程設計19 /*建立無向網(wǎng)的鄰接矩陣結構*/ int i, j; MGraph G; G.vexnum =5; /存放頂點數(shù)G.arcnum =7

45、; /存放邊點數(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);strcpy(G.vexs3.ip,); strcpy(G.,r4);strcpy

46、(G.vexs4.ip,); /*strcpy(G.,超市 r5); strcpy(G.vexs5.ip,); strcpy(G.,綜合實驗樓 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.ar

47、cs13=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;局域網(wǎng)技術課程設計20void Menu() /輸出菜單 cout需要輸出頂點的信息請按 0n; cout需要邊的信息輸出請按 1n; cout需要

48、修改請按 2n; cout需要求出最短路徑請按 3n; cout需要刪除某個頂點請按 4n; cout需要刪除某條邊請按 5n; cout需要插入某條邊請按 6n; cout需要退出請按 7n; void PutOutVex(MGraph *G) /輸出每個頂點的信息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) c

49、out從 到 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; 局域網(wǎng)技術課程設計21 coutv1; if(v1G-vexnum) co

50、utv1; for(v=0;vvexnum;v+) / 初始化 final20,p2020,finalv=1 即已經(jīng)求得 v0 到 v 的最短路徑， /pvw=1 則是 w 從 v0 到 v 當前求得最短路徑上的頂點，Dv帶權長度 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;

51、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;局域網(wǎng)技術課程設計22 void DeleteVex(MGraph *G) /刪除某個頂點int row,col;int v0;coutv0;for(int i=v0;ivexnum;i+)G-vexsi

52、=G-vexsi+1;G-vexnum-;for(row=0;rowvexnum;row+)for(col=v0;colvexnum;col+)G-arcsrowcol=G-arcsrowcol+1;for(col=0;colvexnum;col+)for(row=v0;rowvexnum;row+)G-arcscolrow=G-arcscolrow+1;void DeleteArc(MGraph *G) /刪除某條邊 int v0,v1; coutv0v1; G-arcsv0v1=MAX; G-arcsv1v0=MAX;void InsertArc(MGraph *G) /插入某條邊 int

53、 v0,v1,l=0; coutv0v1; coutl; G-arcsv0v1=l; G-arcsv1v0=l;void main() /主函數(shù) int a; 局域網(wǎng)技術課程設計23 b=InitGraph(); Menu(); cina; while(a!=7) switch(a) case 0:PutOutVex(&b);Menu();break; case 1:PutOutArc(&b);Menu();break; case 2:Change(&b);Menu();break; case 3:Dijkstra(&b);Menu();break; case 4:DeleteVex(&b);

54、Menu();break; case 5:DeleteArc(&b);Menu();break; case 6:InsertArc(&b);Menu();break; case 7:exit(1);break; default:break; cina; Rip:/以下是模擬 RIP 協(xié)議實現(xiàn)的 C+代碼#include#include#include#include#includeusing namespace std;#define MAX 100 /最大路由數(shù)/*下面是存儲類型的三個類*/class Net_sec;/網(wǎng)段類/路由類相當于頭結點class Routepublic:strin

55、g route;Net_sec *next;/網(wǎng)段類，包含相鄰弧的信息（不用 route_f，用 next）,也可用于存儲文件讀入信息（用route_f，不用 next）局域網(wǎng)技術課程設計24class 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

56、_file(ifstream& infile);Route_net();/ 構造函數(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; /存儲圖的信息，即各路由的鄰接表list routesMAX; /存儲各路由路由表list temp; /用于存儲處理后的臨時路由表string

57、flectionMAX; /用于對應路由器與存儲序列標號int sum; /用于統(tǒng)計路由個數(shù);/打開文件函數(shù)void Route_net:open_file(ifstream& infile)string filename;coutfilename;局域網(wǎng)技術課程設計25infile.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.beg

58、in(),it2;int i=0;Net_sec *t2,*t3;for(;it1!=li.end();it1+)if(judge(*it1).route_f) flectioni=(*it1).route_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_s

59、ec();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;局域網(wǎng)技術課程設計26t3-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=(