【導(dǎo)讀】網(wǎng)絡(luò)的重要網(wǎng)絡(luò)設(shè)備，因此對(duì)路由技術(shù)的不斷研究尤其重要。個(gè)好的路由算法可以減少網(wǎng)絡(luò)開(kāi)銷、提高網(wǎng)絡(luò)的可靠性。術(shù)，對(duì)鏈路狀態(tài)路由算法的模擬是一個(gè)有效的途徑。關(guān)知識(shí)并研作出鏈路狀態(tài)路由算法的模擬，這個(gè)模擬有助于更好更深層次地理解鏈路狀態(tài)路由。在內(nèi)容方面，這份論文分5個(gè)部分。第1部分緒論，簡(jiǎn)單介紹了網(wǎng)絡(luò)體系結(jié)構(gòu)的相關(guān)基礎(chǔ)知識(shí)。第3部分重點(diǎn)介紹鏈路狀態(tài)路由原理的五個(gè)過(guò)程。最后一個(gè)部分是總結(jié)與展望。路由器是連接各種不同網(wǎng)絡(luò)的核心設(shè)備，要保證各網(wǎng)絡(luò)用戶之間正常的相互通信路由技術(shù)至關(guān)重要。不同的路由算法有它的優(yōu)缺點(diǎn)，鏈路狀態(tài)路由算法有收斂快等優(yōu)點(diǎn)，因此無(wú)論是理論上還是應(yīng)用上，對(duì)鏈路狀態(tài)路由算法的研究對(duì)網(wǎng)絡(luò)通信有著重大的意義。目前，在實(shí)際網(wǎng)絡(luò)中，計(jì)算機(jī)及其。在統(tǒng)一開(kāi)放系統(tǒng)中，相鄰層次間稱為接口，在接口處由低層向高層提供服務(wù)。·傳輸層──為上層用戶提供端對(duì)端的透明優(yōu)化的數(shù)據(jù)傳輸服務(wù)；

　　

【正文】 ]。 表 對(duì)應(yīng)于 圖 (a)中 B 的報(bào)文緩沖區(qū) 源 序號(hào) 生存時(shí)間 A C F A C F 鏈路狀態(tài)報(bào)文 A 21 60 0 1 1 1 0 0 C 20 60 1 0 1 0 1 0 D 21 59 1 0 0 0 1 1 E 21 60 1 1 0 0 1 1 F 21 59 0 1 0 1 0 1 23 表 中，前面 3 個(gè) ACF 為“發(fā)送標(biāo)志位”，后面 3 個(gè)為“應(yīng)答標(biāo)志位”。 在表 中， A產(chǎn)生的鏈路 狀態(tài)報(bào)文可直接達(dá)到 B，而 B 必須將此報(bào)文再擴(kuò)散到 C 和 F，同時(shí) B必須向 A發(fā)送應(yīng)答報(bào)文，如表 。類似的， F 產(chǎn)生的鏈路 狀態(tài)報(bào)文到 B 后， B必須向 A和 C 進(jìn)行轉(zhuǎn)發(fā)，同時(shí) B 必須向 F 發(fā)送應(yīng)答報(bào)文，如表 第 5 行所示。 但是，對(duì)于表 中來(lái)自 E 的報(bào)文有所不同。假設(shè) B 兩次收到來(lái)自 E 的報(bào)文，一次經(jīng)過(guò) EAB，另一次經(jīng)過(guò) EFB。因此， B 只需將 E 產(chǎn)生的鏈路 狀態(tài)報(bào)文發(fā)往 C，但要向 A和 F 發(fā)送應(yīng)答報(bào)文。 如果重復(fù)報(bào)文在前一個(gè)報(bào)文未出緩沖區(qū)時(shí)到達(dá)，圖中標(biāo)志位就得進(jìn)行修改。例如在圖 (a)中，當(dāng) B 還未處理完 C產(chǎn)生的鏈路 狀態(tài)報(bào)文，又接收到一個(gè)從 F傳來(lái)的 C的鏈路 狀 態(tài)報(bào)文，此時(shí)應(yīng)將 C的標(biāo)志位由 101010改為 100011，表示要向 F 發(fā)送應(yīng)答報(bào)文 ，而不必將 C 的鏈路 狀態(tài)報(bào)文再發(fā)向 F。 計(jì)算新路由 由于網(wǎng)絡(luò)上的每個(gè)路由器都可以獲得所有其他路由器的 鏈路 狀態(tài)報(bào)文，因此每個(gè)路由器都可以構(gòu)造出網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖。此時(shí)路由器可以根據(jù) Dijkstra 算法計(jì)算出到所有目的結(jié)點(diǎn)的最短路徑，并把計(jì)算結(jié)果填到路由器的路由表中。這樣的過(guò)程隨著鏈路 狀態(tài)報(bào)文的更新而周期性地進(jìn)行。 小結(jié) 本章 介紹了鏈路狀態(tài)的原理，分別介紹了 5個(gè)過(guò)程： ① 發(fā)現(xiàn)鄰居結(jié)點(diǎn)； ② 測(cè)量到鄰居結(jié)點(diǎn)的線路開(kāi)銷； ③ 構(gòu)造鏈路 狀態(tài)路由報(bào)文； ④ 廣播鏈路 狀態(tài)報(bào)文； ⑤ 計(jì)算新路由。因此，鏈路狀態(tài)算法的模擬和實(shí)現(xiàn)是離不開(kāi)這五個(gè)過(guò)程的。 24 4 鏈路狀態(tài)路由算法模擬 不管是鏈路狀態(tài)算法還是距離向量算法，對(duì)它們進(jìn)行模擬分析是研究一個(gè)路由算法的重要手段。通過(guò)對(duì)一些常用的算法模擬分析，可以比較它們的優(yōu)劣，為路由算法的優(yōu)化工作奠定基礎(chǔ)。本文下面部分對(duì)鏈路狀態(tài)路由算法進(jìn)行模擬研究。 鏈路狀態(tài)路由算法可以用 5 個(gè)部分加以描述。每個(gè)路由器必須完成以下的工作： （ 1）發(fā)現(xiàn)它的鄰居節(jié)點(diǎn)，并知道其網(wǎng)絡(luò)地址。 （ 2）測(cè)量到各鄰居節(jié)點(diǎn)的延遲或者開(kāi)銷。 （ 3）構(gòu)造一個(gè)分組，分組 中包含所有它剛剛知道的信息。 （ 4）將這個(gè)分組發(fā)送給所有其他路由器。 （ 5）利用 Dijkstra 算法計(jì)算得到每個(gè)其它路由器的最短路徑。 鏈路狀態(tài)路由算法模擬 鏈路狀態(tài)路由算 法模擬是為了對(duì)鏈路狀態(tài)路由原理的更好理解而做的，下面是鏈路狀態(tài)路由算法的模擬過(guò)程 。 算法模擬的思想 這里主要是模擬鏈路狀態(tài)路由（ LSR）廣播鏈路狀態(tài)報(bào)文 (LSA)的過(guò)程，說(shuō)明了 LSR 過(guò)程中是通過(guò)向路由器所在的網(wǎng)絡(luò)中其他路由器廣播自己的信息（包括網(wǎng)絡(luò)狀態(tài)）以達(dá)到收斂，和距離向量算法不同，距離向量算法是路由器通過(guò) 不斷地向鄰居結(jié)點(diǎn)發(fā)送自己的信息得到更新，這樣的收斂比較慢，而且需要定時(shí)機(jī)制。 下面介紹一下大致的模擬過(guò)程。 算法模擬中有 5 個(gè)成網(wǎng)狀連接的路由器： Router Router Router Router Router5，每個(gè)路由器的信息以“路由器名， IP，小組名”為主。當(dāng)網(wǎng)絡(luò)中路由器啟動(dòng)時(shí)，先給出后面 4 個(gè)路由器的信息（ IP 和小組名）即 Router1的網(wǎng)絡(luò)環(huán)境，然后進(jìn)行 Router1 的環(huán)節(jié)控制。這個(gè)環(huán)節(jié)控制有 2個(gè)過(guò)程：首先，發(fā)現(xiàn)鄰居節(jié)點(diǎn)過(guò)程，建立 Router1 的小組信息，把有相同“小組名”的路由器作為“鄰 居節(jié)點(diǎn)”加入到一個(gè)小組。這里主要模擬鏈路狀態(tài)路由過(guò)程中路由器通過(guò)發(fā)送“ Hello”報(bào)文發(fā)現(xiàn)鄰居節(jié)點(diǎn)的過(guò)程。然后， Router1 測(cè)量出和各“鄰居節(jié)點(diǎn)”的距離并記錄下來(lái)，建立本地路由表， 獲得以上信息后再計(jì)算各路由器之間的最短路徑，最后 得到路由表信息。 算法模擬的方案 在算法模擬中采用數(shù)據(jù)流程圖這種半形式化的描述方式表達(dá)需求。它是一種功能模型，以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過(guò)程，只反映系統(tǒng)必須完成的邏輯功能。 25 圖 是 結(jié)構(gòu) 圖， 這個(gè)結(jié)構(gòu)分為 2 個(gè)部分： 1. “小組信息模塊”主要是設(shè)置網(wǎng)絡(luò) 環(huán)境， 設(shè)置“小組名”是為了后面把相同小組名的路由器作為鄰居節(jié)點(diǎn)加入到同一個(gè)小組，“小組成員數(shù)量”是限制鄰居節(jié)點(diǎn)的數(shù)量有選擇性地收發(fā)信息。 2. “環(huán)節(jié)控制模塊”主要通過(guò) Router1 的路由表信息更新來(lái)模擬鏈路狀態(tài)路由的過(guò)程： 通過(guò)廣播路由信息 發(fā)現(xiàn)鄰居節(jié)點(diǎn)并 顯示出來(lái)，然后測(cè)量和鄰居節(jié)點(diǎn)的距離 ，最后得到本地路由表和路由表。 圖 算法模擬的結(jié)構(gòu) 圖 算法模擬的關(guān)鍵問(wèn)題 鏈路狀態(tài)路由算法模擬能夠形象的模擬出鏈路狀態(tài)路由的報(bào)文廣播過(guò)程，而 這個(gè)過(guò)程是通過(guò)網(wǎng)絡(luò)中路由器的路由信息的變化體現(xiàn)出來(lái)的。 先說(shuō)明一下算法模擬的開(kāi)發(fā)工具和開(kāi)發(fā)環(huán)境： 開(kāi)發(fā)工具： Delphi 和 Microsoft Access 2021 開(kāi)發(fā)環(huán)境： Windows XP。Windows 2021。Windows 98 為了實(shí)現(xiàn)路由功能，要為每個(gè)路由器在數(shù)據(jù)庫(kù)中建立一個(gè)信息表（模擬的），具體如表 。 鏈路狀態(tài)路由模擬系統(tǒng) 小組信息模塊 環(huán)節(jié)控制模塊 設(shè)置小組名 設(shè)置成員數(shù)量 顯示鄰居節(jié)點(diǎn)情況 構(gòu)造本地路由表 構(gòu)造路由表 26 表 路由器信息表（ Infor） Router IP Team（小組名） 1 Angela 2 Angela 3 Angela 4 Angela 5 Angela 在鏈路狀態(tài)路由過(guò)程中，每個(gè)路由器都維持著同樣的數(shù)據(jù)庫(kù)以描述整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并以此數(shù)據(jù)庫(kù)來(lái)創(chuàng)建最短路徑樹(shù)并計(jì)算路由表。 在發(fā)現(xiàn)拓?fù)涓淖兒?，僅利用很少的路由流量就可以快速的重新計(jì)算出路徑 [17]。 在 算法 模擬中，路由表數(shù)據(jù)主要通過(guò)表 的形式存儲(chǔ)。 表 路由表數(shù)據(jù)的設(shè)計(jì)表 字段名稱 數(shù)據(jù)類型 說(shuō)明 目的 文本 網(wǎng)絡(luò)中可以到達(dá)的路由器名 下一站 文本 直連的路由器名 距離 文本 到下 一站的延遲 算法模擬的主窗口如圖 所示 。 圖 算法模擬主界面 27 下面就算法模擬的 4 個(gè)過(guò)程分別介紹。 1． 路由器啟動(dòng)，設(shè)置好網(wǎng)絡(luò)環(huán)境。 從圖 中可以知道，路由器的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是網(wǎng)狀的。單擊“小組情況”按扭彈出如圖 所示 的窗口。 小組情況包括了各路由器的 IP 和小組名，在這個(gè)模擬過(guò)程中要把具有相同小組名的路由器作為鄰居節(jié)點(diǎn)，然后顯示各鄰居節(jié)點(diǎn)的 IP 以確認(rèn)發(fā)現(xiàn)了鄰居節(jié)點(diǎn)。而且，因?yàn)楦髀酚善髦g是直連的，所以路由器和鄰居節(jié)點(diǎn)的距離都是 “ 1” 。 圖 的窗口可以設(shè)置 Router Router Router Router5的路由信息，這里提供了兩種設(shè)置方法，一種是直接調(diào)用數(shù)據(jù)庫(kù)初始化路由信息；另一種是手動(dòng)修改，即在 edit 框中輸入數(shù)據(jù)作為小組名。 圖 小組情況 第一種方法的實(shí)現(xiàn)代碼如下： procedure (Sender: TObject)。 begin //調(diào)用數(shù)據(jù)庫(kù) 39。Infor39。數(shù)據(jù) :=adoconnection1。 :=39。Infor39。 :=true。 。 //調(diào)用“ Infor”的 team 數(shù)據(jù) with adotable1 do begin :=inttostr(Node[2,2].team)。 :=inttostr(Node[3,2].team)。 :=inttostr(Node[4,2].team)。 :=inttostr(Node[5,2].team)。 28 end。 這里要說(shuō)明一下對(duì)于變量 Node 的定義： var type matrix=array[1..5,1..2]of integer。 //定義二維數(shù)組，用來(lái)存放小組信息 var router,team:matrix。 Type //定義路由結(jié)點(diǎn) TNode=record router:integer。 team:string。 end。 TNodes=Array[1..5,1..2]of TNode。 var Node:TNodes。 第二種方法是手動(dòng)設(shè)置 ，因此首先要清空所有信息，清空的具體代碼如下： procedure (Sender: TObject)。 begin //將殘留在 edit 中的信息清空 :=39。39。 :=39。39。 :=39。39。 :=39。39。 end。 清空信息后，就可以手動(dòng)輸入各“小組名”了。設(shè)置好“小組情況”完成“修改確認(rèn)”，實(shí)現(xiàn)這個(gè)過(guò)程的源代碼如下： procedure (Sender: TObject)。 begin //把設(shè)置的值寫入數(shù)據(jù)庫(kù)中。 。//把控件 ADOQuery 的 Name 屬性設(shè)置為“ aq1” 。 (39。insert into infor values(39。39。239。39。,39。39。39。39。,39。39。39。++39。39。39。)39。)。 。 。 。 (39。insert into infor values(39。39。339。39。,39。39。39。39。,39。39。39。++39。39。39。)39。)。 。 。 。 (39。insert into infor values(39。39。439。39。,39。39。39。39。,39。39。39。++39。39。39。)39。)。 。 29 。 。 (39。insert into infor values(39。39。539。39。,39。39。39。39。,39。39。39。++39。39。39。)39。)。 。 end。 2． 網(wǎng)絡(luò)中路由器 Router1 的鏈路報(bào)文環(huán)節(jié)控制過(guò)程。 環(huán)節(jié)控制包括以下幾個(gè)過(guò)程：（ 1）尋找鄰居節(jié)點(diǎn)，設(shè)置 Router1 的加入小組信息；（ 2）計(jì)算和鄰居節(jié)點(diǎn)的距離，通過(guò)廣播信息建立本地路由表。 網(wǎng)路中路由信息設(shè)置好后表示路由器正常啟動(dòng)了，這樣 Router1 的網(wǎng)絡(luò)環(huán)境都已經(jīng)設(shè)置好了，接著我們通過(guò) Router1 的“環(huán)節(jié)控制”來(lái)說(shuō)明鏈路狀態(tài)路由過(guò)程中路由信息的收發(fā)情況。 圖 中單擊“建立小組”按鈕彈出如圖 的窗口。這個(gè)窗口的功能主要是模擬“發(fā)現(xiàn)鄰居節(jié)點(diǎn)”的過(guò)程，而且小組成員的建立是以網(wǎng)絡(luò)中有和 Router1 相同小組名的路由器為一個(gè)小組的，小組成員的數(shù)量是可以選擇的，這個(gè)功能其實(shí)就是模擬鏈路狀態(tài)路由過(guò)程中不使用廣播的方式而使用多播的方式，這種方式可以減輕網(wǎng)絡(luò)負(fù)擔(dān)。 圖 Router1 信息 圖 中，選擇“成員數(shù)量”以確定一個(gè)小組的最多的成員數(shù)量，超過(guò)這個(gè)數(shù)量后就不再允許加入成員。信息設(shè)置好后，在下面顯示“成員的加入情況”。到這里，主要模擬了發(fā)現(xiàn)鄰居節(jié) 點(diǎn)過(guò)程。具體代碼如下： procedure (Sender: TObject)。 var i,j:integer。 str:string。 begin 30 。 。 (39。select distinct ip from infor where team=39。39。39。+trim()+39。39。39。39。)。 。//把 team 和 Router1 相同的路由器的 IP 存儲(chǔ)在 aq1. if =0 then begin showmessage(39。39。)。 end。 if =39。39。 then begin showmessage(39。選擇成員數(shù)量 39。)。 。 exit。 end。 i:=strtoint()。 showmessage(39。成員最多的數(shù)量為 39。+inttostr(i))。 for j:=1 to i do begin if not then begin str:=[0].AsString。 (str+39。 Joined the group39。)。 。 end。 end。 end。 到此，路由信息基本設(shè)置好了，回到主界面后，本地路由表信息已經(jīng)可以顯示出來(lái)了。以本地路由表為基礎(chǔ)，結(jié)合鏈路狀態(tài)路由算法原理，組織路由信息。建立小組 的過(guò)程是模擬網(wǎng)