【正文】 華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 1 基于 DV算法的路由器設(shè)計與實現(xiàn) 實驗報告 學(xué) 院 ： 姓 名： 日 期： 華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 2 一． 實驗?zāi)康? 1． 深入理解分布式路由選擇算法 ，以最簡單的 DV 算法來增強(qiáng)對路由算法的 認(rèn)識 2． 理解、掌握和利用距離向量算法 3． 所實現(xiàn)的路由器模擬 Inter 上的 IP 路由器。它能確定網(wǎng)絡(luò)的最短路由，并在這些利用上傳輸分組 二． DV 算法描述 距離矢量算法， 也稱為 BellmanFord shortest path algorithm， 每個路由器都定期 或拓?fù)浣Y(jié)構(gòu)突發(fā)變化時 與其相鄰的所有路由器交換路由表，據(jù)此更新它們自己的路由表 。 DV算法工作方式：每個路由器維護(hù)一張路由表，表中分為三個表項：目的地址，列出了當(dāng)前可達(dá)的目的網(wǎng)絡(luò)地址；到達(dá)目的地址下一跳，列出了下一跳的IP 地址；到達(dá)目的地址 的代價，以距離或跳數(shù)為表征。 路由表更新規(guī)則： 1． 發(fā)現(xiàn)了一條到達(dá)某目的的新路由，而該路由在原來的路由表中不存在（即發(fā)現(xiàn)了一條新路由），則在路由表中增加該路由 。 2． 發(fā)現(xiàn)了一條到達(dá)某目的的、距離 更短的新路由，則用該路由替換原有的路由 。 3． 到達(dá)某目的的一條路由，其后繼結(jié)點(diǎn)到達(dá)該目的地的距離發(fā)生了變化，則需要更新該路由的距離 。 在此實驗當(dāng)中，為了實現(xiàn)和模擬的方便， 剛開始初始化生成一個網(wǎng)絡(luò)連接圖的 二 維 數(shù) 組 （ 見 mainManager/ ， 初 始 化 的 二 維 數(shù) 組 是entity/）； 每個路由器類包括了路由器 ID,端口， routerTable 對象，還有兩個 HashMap(一個存儲為每一個相鄰路由器的計時器，一個存儲每一個相鄰路由器的上一次交流時間 )。路由表 采用 了兩個數(shù)組來實現(xiàn)，一個數(shù)組存儲到各個網(wǎng)絡(luò)的下一跳，一個數(shù)組存儲到各個網(wǎng)絡(luò)的跳數(shù)， 如下結(jié)構(gòu) ， 以路由器一為例，（路由表的默認(rèn)數(shù)組和兩個真是數(shù)組的顯示信息 ，其中下一跳是 0 表示不可達(dá)的下一跳，不是 0 如 2021 表示下一跳是 2021，在距離數(shù)組里，如果是 16 表示不可達(dá)，如果是 0，表示到本身路由，不是 0 或 16 表示可達(dá)且跳數(shù)為該數(shù)值 ） ，如下 圖 路由表 左邊方框中的 信息 所示 ： 華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 3 在路由表中， 只 登記 下一跳 而不是 完整路由 ，以 真實模擬路由器的 DV 算法處理。轉(zhuǎn)發(fā)分 組時， 嚴(yán)格按照路由表進(jìn)行轉(zhuǎn)發(fā)。 如上圖，路由器的連接信息在上面圖片的左部區(qū)域，右部區(qū)域分為兩部分（一個是路由器接到相鄰路由器發(fā)來的路由表的實時 我設(shè)置的是每 1 秒 更新 一次 信息，一個是發(fā)送或者轉(zhuǎn)發(fā)數(shù)據(jù)的顯示信息） 。 三． 實驗要求 1． 輸出 路由表 ： 在此實驗當(dāng)中為了實現(xiàn)方便，所有拓?fù)浣Y(jié)構(gòu)中的路由器都給以顯示（可達(dá)的，不可達(dá)的 16 以及自己的路由編號） ： 要求對這個連接圖的二維數(shù)組解析，進(jìn)行 DV 算法的模擬。 2． 發(fā)送分組 ： 每個數(shù)字代表一個數(shù)據(jù)分組發(fā)送請求 ； 數(shù)據(jù)分組發(fā)送到 數(shù)字代表的目的地 ； 如果目的結(jié)點(diǎn)不是鄰居結(jié)點(diǎn)，不能直接發(fā)送分組，而必須在路由的各個結(jié)點(diǎn)上沿路由轉(zhuǎn)發(fā)該分組 。 收到數(shù)據(jù)分組的結(jié)點(diǎn)必須輸出一行，顯示該分華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 4 組的目的 ， 在圖 1 中的右上角顯示了每一秒的路由表的更新情況， 每一個路由器都有三個轉(zhuǎn)發(fā)進(jìn)程，發(fā)送進(jìn)程和接收進(jìn)程。發(fā)送進(jìn)程每一秒都需要發(fā)送自己的路由表信息。 每一個路由器都給自己相鄰的路由器設(shè)置了一個計時器，如果 10 秒鐘沒有收到相鄰路由器的信息，就將下一跳設(shè)置成 0，距離設(shè)置成 16（表示不可達(dá)）。 否則重新開始計數(shù)。 2． 發(fā)送 數(shù)據(jù)： 數(shù)據(jù)分組 必須有數(shù)據(jù)，且在如圖 1 中的點(diǎn)擊提交按鈕 之前，必須在文本框中輸入正確的數(shù)據(jù)格式（傳送的目的路由和要傳送的數(shù)據(jù)之間必須要有“ ”號分割），如： 2021DDDDDDD，表示目的路由是 2021，傳送的數(shù)據(jù)是DDDDDDD。 例如： 路由器 2021 要向 2021 發(fā)送數(shù)據(jù)，則具體轉(zhuǎn)發(fā)過程如下： 在 RouterTablePacket 中有 Hops(初始值是 16，每過一跳， hops 減 1，當(dāng) hops是 1 的時候，就不再進(jìn)行轉(zhuǎn)發(fā)了，相當(dāng)于 TTL： Time to Live)屬性， 分組應(yīng)該在華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 5 Hops 規(guī)定的時間或步數(shù)內(nèi)到達(dá)目的 結(jié)點(diǎn)，否則丟棄之 。 分組經(jīng)過每個中間結(jié)點(diǎn)時，將其 TTL 減 1。若 TTL=1，丟棄，否則繼續(xù)轉(zhuǎn)發(fā) 。 3． 關(guān)于時間定時 ： 每個路由器每 1 秒鐘發(fā)出它們的路由表 ； 每個路由器根據(jù)收到的路由表更新它們自己的路由表 ；路由器必須具備檢測鄰居是否活動的能力， 如果路由器在 10 秒鐘沒有收到鄰居發(fā)來的更新，則認(rèn)為鄰居不可達(dá) 。 4．顯示活動的相鄰路由：用一個特定的表格來顯示與當(dāng)前路由相鄰的路由器的信息。 5． 關(guān)于拓?fù)浣Y(jié)構(gòu) ： 路由器必須具備路由器故障和恢復(fù)的能力 ； 這里假設(shè)鏈路不會出現(xiàn)故障，分組不會丟失和出錯 ；如果路由器在給定時間內(nèi) 未運(yùn)行，表示路由器故障， 如果重啟運(yùn)行，則認(rèn)為路由器故障恢復(fù) ； 當(dāng)然，假設(shè)通信是雙向的 。 四． 實驗用例 編程語言： java； 開發(fā)環(huán)境： 、 , 測試用例為 二維數(shù)組的維數(shù) 個（你可以隨便寫出一個對稱的二維數(shù)組，程序可以自己解析的，我用的都是活代碼） ，如下如所示我寫的一個拓?fù)鋱D的二維數(shù)組，如圖： 此實驗是模仿 DV 算法 ， 應(yīng)用 java 中的多線程來模擬多個路由器，并且實現(xiàn)路由器之間的路由表和數(shù)據(jù)的傳送。實驗中 路由表的數(shù)據(jù)結(jié)構(gòu) 相比真實的 DV算法 發(fā)生了變化 ，所以 程序 在實現(xiàn)過程當(dāng)中盡量的按照實驗所用的路由表結(jié)構(gòu)來完成功能， 但是這 不影響其主要思想的實現(xiàn)。 1．拓?fù)浣Y(jié)構(gòu)： 為了模擬路由表的更新， 首先是 先確立六 個 結(jié) 點(diǎn) 網(wǎng)絡(luò) 的 拓?fù)浣Y(jié)構(gòu)， 由于是應(yīng)用多線程來模擬各個路由器，所以 在實驗過程當(dāng)中 可以隨時掛起某個或多個路由器來模擬網(wǎng)絡(luò)拓?fù)涞淖兓?，之后仍然可以恢?fù)掛起的路由器。網(wǎng)絡(luò)的初始拓?fù)浣Y(jié)構(gòu)如 圖 2 所示 ： 華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 6 圖 2 此處，路由表的 端口號 和路由器號全是來自 entity/ 文件的整個程 序的全局變量，路由器初始值為 2021，而端口初始值為 5001，分別是數(shù)組初始化時的維數(shù) 個 。 在實驗實現(xiàn)過程當(dāng)中，通過路由器線程的掛起實現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化，之后會對相應(yīng)的更該重新畫出拓?fù)浣Y(jié)構(gòu)。 2．路由表初始化： 在程序的 mainManager/ 類中初始化了留個路由器，這六個路由器的每一個實現(xiàn)都是在 mainManager/ 類中， 。以上 圖 2 的初始化二維數(shù)組 中所規(guī)劃的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為標(biāo)準(zhǔn)，根據(jù)當(dāng)前所創(chuàng)建的路由器編號靜態(tài)初始化每 個路由器自己的路由表。 3．?dāng)?shù)據(jù)格式： 各個路由器實例之間通過 UDP 來交換路由表，路由器之間還需要進(jìn)行數(shù)據(jù)的傳輸。在此，需要定義所傳輸?shù)穆酚杀砗蛿?shù)據(jù)的結(jié)構(gòu)， 我是全部打成了數(shù)據(jù)包或者路由表包，具體結(jié)構(gòu)見 transportPacket/ （有sourceRouterId 和 routerTable 兩個屬性 ） ， transportPacket/（有sourceRouterId,destRouterId,byte[]data,hops=16 四個屬性） ，transportPacket/（ 有 type,routerTablePacket,sendDataPacket 三個屬性， TotalPacket 類定義了具體具體是傳輸?shù)陌鞘裁搭愋偷模? 三個類， 如果是傳輸路由表就用 RouterTablePacket 把路由表包裝后再用 TotalPacket 的sendRouterTable 類型來包裝，最后用 UDP 發(fā)送出去，如果是傳輸數(shù)據(jù)就用SendDataPacket 把要傳送的數(shù)據(jù)包裝后再用 TotalPacket 的 sendData 類型來包裝，最后用 UDP 發(fā)送出去，在目的路由器端對收到的數(shù)據(jù)進(jìn)行解封裝。 五．程序描述 端口號： 5001 2021 端口號： 2021 端口號： 5002 端口號： 5004 端口號： 5003 端口號： 2021 2021 2021 2021 2021 2021 華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 7 為完成所要求功能，程序首先實現(xiàn)了 二維數(shù)組維數(shù) 個路由器線程 ，每一個路由器線程下面又實現(xiàn)了 發(fā)送線程、接收線程和 轉(zhuǎn)發(fā) 數(shù)據(jù)線程 三個子線程；接收線程下面實現(xiàn)了 定時器子線程 。 建立一個工程，命名為 day1202_DV_new_hasTimer（名字可以隨便起 ，我是以前的習(xí)慣都加上了日期 ） ，在此工程下建立源程序文件，每個線程放在單獨(dú)的 java 源程序文件當(dāng)中。 該實驗還可以對其中一個路由器進(jìn)行掛起，別的路由器在 10 秒后如果 收不到這個路由器發(fā)來的路由表信息，就將其路由表中的與其對應(yīng)的相應(yīng)路由表的值進(jìn)行修改成不可達(dá)，逐漸通知到整個網(wǎng)絡(luò)。在這里有點(diǎn)不同于 DV 算法的是 ：DV算法是每個路由器為收到的路由表的每一個簡歷一個計時器，而該路由器簡化了這個設(shè)計，是僅僅為相鄰的路由器保留一個計時器，這樣不僅可以大大減少整個網(wǎng)絡(luò)的通信量，將計時器的信息保留在內(nèi)存而不是在路由表中，而且采用了hashMap 保存后在驗證是否聯(lián)通時， 從 hashMap 中取數(shù)據(jù) 方便 快捷 。 六、實驗結(jié)論 在實驗過程遇到了許多問題，一方面是編程語言的使用，另一方面是對路由算 法的理解程度。 三是計時器的用法， 尤其是計時器的用法想了將近 2 個小時，最后 通過不懈的調(diào)試與算法完善，程序基本實現(xiàn)所要求的功能，有能力模擬 DV算法。 DV 算法 的優(yōu)缺點(diǎn)： DV 算法簡單，容易實現(xiàn)，對于好消息傳播的速度快，但是對于壞消息則傳播速度慢。 華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 8 package entity。 /** * 常量類 * @author 郭金磊 *@since 20211220 */ public class Constant { /** * @return 返回路由 Id 的初試值 */ public static int getRouterIdBasic(){ return 2021。 } /** * @return 返回路由端口的初試值 */ public static int getPortBasic(){ return 5001。 } } package entity。 /** * 初始化的網(wǎng)絡(luò)拓?fù)鋱D * @author 郭金磊 *@since 20211220 */ public class NetMap { /** * @return 返回初始化的網(wǎng)絡(luò)圖 */ public int[][] getInitInterMap(){ int[][] initVecter=new int[][] 華北計算機(jī)系統(tǒng)工程研究所 — 若 @只如初見 9 {{0,1,16,16,1,16}, {1,0,1,16,16,16}, {16,1,0,1,1,16}, {16,16,1,0,16,1}, {1,16,1,16,0,16}, {16,16,16,1,16,0} }。 return initVecter。 } } package entity。 import 。 /** * 路 由 器 實 體 類 ， 包 含 routerId ， port ， RouterTable ，createTimerMapsForNeighbers， lastTimeMaps * @author 郭金磊 *@since 20211220 */ public class Router { /** * 產(chǎn)生全局唯一的序列化的實體 ID */ private static f