計算機網(wǎng)絡(luò)網(wǎng)絡(luò)層路由算法.ppt

1、1、路由算法是網(wǎng)絡(luò)層軟件的一部分，它負責(zé)將接收的包發(fā)送到哪個線路。 路由算法應(yīng)當(dāng)具有正確性、單純性、魯棒性、穩(wěn)定性、公平性、最佳性的特性。 路由算法不需要所有主機都停止所有工作，而且必須能夠處理拓撲和通信的各種變化。 2、路由算法可分為兩類。 不自適應(yīng)-不根據(jù)當(dāng)前測量或估計的通信量和拓撲調(diào)整路由決策。 使用的路由預(yù)先離線計算，在網(wǎng)絡(luò)啟動時下載到路由器上。 自適應(yīng)-根據(jù)拓撲、通信量的變化修改路由。 另外，3，3，5.2.1優(yōu)化原則優(yōu)化路徑通常，在路由器j處于從路由器I到k的優(yōu)化路徑上的情況下，從j到k的優(yōu)化路徑也必須遵循相同路徑。 集約樹：b，a，c，d，e，g，f，h，I，j，路由器b的集約樹

2、，4，5.2.2最短路徑算法，基本的想法：網(wǎng)絡(luò)圖的各節(jié)點表示路由器，各邊表示通信線路或鏈路，選擇某路由器間的路徑最短路徑：測量方法：跳躍數(shù)，以公里為單位的距離。 標(biāo)準(zhǔn)測試包的平均延遲。 Dijksstra算法、5、6、5.2.3溢流算法、溢流：將入境的各包發(fā)送到除該包到達的線路以外的各出境線路。 缺點：產(chǎn)生大量重復(fù)數(shù)據(jù)包。 對策： (1)設(shè)置跳躍計數(shù)器(2)跟蹤包。 優(yōu)點：確保分組轉(zhuǎn)發(fā)到每個網(wǎng)絡(luò)內(nèi)的節(jié)點的洪水路徑的魯棒性非常好，即使大量的路由器被碎片化，也可以找到分組到達目的地的路徑。 7、距離向量路由算法、工作原理：各路由器保存表，在表中指示與到每個目的地路由器的已知最短“距離”對應(yīng)的輸出線

3、路，通過與相鄰路由器交換距離信息來更新表。 “距離”:到目的地路由器的跳數(shù)、估計的延遲時間、路由隊列的分組估計總數(shù)等的值。 然后，使用延遲作為距離測量，并且假定路由器知道到每一鄰站的延遲。 每個路由器向每個鄰近站發(fā)送一個表，每隔t秒記錄到每個目標(biāo)站的延遲，并從鄰近站接收類似的表。8、發(fā)現(xiàn)交換距離信息更新路由表的示例，9、無限計算問題、10、鏈路狀態(tài)路由算法、以及鄰居，并且知道為每個鄰居節(jié)點設(shè)置其網(wǎng)絡(luò)地址的距離或成本測量。 把剛才知道的所有鏈接數(shù)據(jù)包匯總成一個。 將此包發(fā)射到所有其它路由器，且從其它路由器接收包。 計算到其他路由器的最短路徑。 11、鄰居在各點線路上發(fā)送特殊問候包，并發(fā)現(xiàn)線路另一

4、側(cè)的路由器返回指示自己是誰的響應(yīng)。 如果兩個或多個路由器通過一個廣播鏈路連接：12，設(shè)置的鏈路成本與帶寬成反比的鏈路延遲是成本的一部分。 方法：通過線路向另一側(cè)發(fā)送特殊的ECHO分組，請求對方立即返回，測量往返時間除以2，從而通過發(fā)送路由器可以獲得合理的延遲估計。 構(gòu)建鏈路狀態(tài)包的內(nèi)容：發(fā)件人的標(biāo)識符，然后是序列號和年齡，鄰居列表。 制作時間：周期性，重要的事情發(fā)生的時候。、13、鏈路狀態(tài)分組、示例性網(wǎng)絡(luò)、14，分發(fā)鏈路狀態(tài)分組(1)溢流法：每個分組包括一個序列號，以控制溢流的規(guī)模，序列號在每個分組中逐個增加，并且路由器看它當(dāng)新鏈路狀態(tài)分組到達時，路由器檢查該分組是否已經(jīng)出現(xiàn)在上述觀察列表中，

5、如果該分組是新的分組則被轉(zhuǎn)發(fā)，并且如果分組重復(fù)或舊的話將其丟棄。 (2)改進方法：當(dāng)數(shù)據(jù)包淹沒在其他路由器上時，不立即排隊，而是先進入保留區(qū)域。 在轉(zhuǎn)發(fā)它之前，另一個鏈路狀態(tài)分組到達來自相同的源路由器，并與它們的號碼比較以確定轉(zhuǎn)發(fā)哪一個。15、路由器b的狀態(tài)數(shù)據(jù)包緩沖器、特殊情況：即使有一個重復(fù)的包到達，原始的包仍在緩沖器中。 此時標(biāo)志位的變化。 一旦c的副本從f到達，標(biāo)志位就計算100011 .新的路由：使用Dijikstra算法。 鏈路狀態(tài)路由算法的優(yōu)點：沒有慢收斂問題。16、5.2.6分層路由、原理：將路由器劃分成區(qū)域，每個路由器知道如何將包路由到它所在區(qū)域內(nèi)的目的地地址，但它不知道其他

6、區(qū)域的內(nèi)部結(jié)構(gòu)。 一旦不同的網(wǎng)絡(luò)相互連接，則網(wǎng)絡(luò)當(dāng)然被視為獨立的區(qū)域，一個網(wǎng)絡(luò)的路由器不知道其他路由器的拓撲。 在大規(guī)模的網(wǎng)絡(luò)中，二級階層可能不夠，一般將地區(qū)組織為集群，集群組織為地區(qū)，地區(qū)組織為分組。17、1A完全表、1A層次表、區(qū)域1、區(qū)域5、區(qū)域4、區(qū)域3、區(qū)域2、二級層次示例、18、優(yōu)點：隨著區(qū)域數(shù)與每個區(qū)域的路由器數(shù)的比率的增加，節(jié)省的空間也增加。 缺點：傳球的長度變長了。 科學(xué)上可知，對于包含n個路由器的網(wǎng)絡(luò)，最合適的層數(shù)是lnN，各路由器所需的路由器的條目是elnN個。 當(dāng)然，基于分層的路徑長的實際增長非常小。 另外，將19、廣播路由、同時向所有目的地地址發(fā)送一個分組稱為廣播擴頻

7、方法。 多目標(biāo)路由：每個數(shù)據(jù)包含一組目標(biāo)地址，并且通過路由器沿宿樹生成樹擴展到目標(biāo)選擇根的目標(biāo)分布式反向路徑轉(zhuǎn)發(fā)，20，20 根據(jù)該路徑是否是用于向廣播源發(fā)送分組的路徑，該路徑傳送到所有其它路徑，否則丟棄該路徑。 反向路徑傳輸?shù)膬?yōu)點：有效且容易實現(xiàn)。21、組播路由、定義：向明確定義的組發(fā)送消息稱為組播。 在組的分布密集的情況下，通過修剪廣播生成樹，可以從樹種中減少與組成員不相通的鏈路。 修剪的結(jié)果得到了有效的組播生成樹。 修剪(b )最左邊路由器的一個生成樹. (c )分組1的一個多播樹. (d )分組2的一個多播樹. (a )網(wǎng)絡(luò)實例修剪從各路徑的末端開始，朝向根，刪除不屬于相應(yīng)組的路由器。

8、 在距離向量路由協(xié)議距離向量路由算法中，反向的路徑被轉(zhuǎn)發(fā)。 如果路由器不感興趣某一組，且該路由器沒有連接于接收多播消息的其他路由器，則向它發(fā)送一個保持信息以防止向其發(fā)送消息的鄰居發(fā)送該組消息的路由器的主機屬于該組這樣，最終修剪一棵樹。 缺點：構(gòu)建樹的存儲需要很多空間。 24，5.2.9廣播路由，廣播：數(shù)據(jù)包被傳遞給最近的組成員。 您可以使用距離向量和鏈路狀態(tài)路由算法來生成新的選播路由.假設(shè)您需要選擇包為組1的成員。 將組地址“1”而不是獨立地址分配給組成員，距離向量路由按常規(guī)方式發(fā)送包，節(jié)點僅選擇到目的地1的最短路徑。 25、組1的選播路徑、路由協(xié)議看到了拓撲、1、1、26、5.2.10移動主

9、機路徑、互聯(lián)網(wǎng)和蜂窩移動路徑的基本想法是移動主機現(xiàn)在在那里故障自己。 以移動主機的名義行動，并且一旦知道移動主機的位置，就可以將分組轉(zhuǎn)發(fā)給移動主機。 27、首先，移動主機獲取本地網(wǎng)絡(luò)地址(也稱為轉(zhuǎn)交地址)，通知歸屬代理其位置，并向歸屬代理發(fā)送帶有轉(zhuǎn)交地址的注冊消息。 然后發(fā)送者使用其永久地址將包發(fā)送到移動主機，該包通過網(wǎng)絡(luò)路由到其歸屬地址。 因為移動主機已經(jīng)離開了家，所以家庭地址用新的標(biāo)頭包或封裝包，然后將捆綁的結(jié)果轉(zhuǎn)發(fā)給轉(zhuǎn)交地址的機制稱為隧道。 封裝的分組到達轉(zhuǎn)交地址，移動主機對其解包以檢索來自發(fā)信方的分組，并且移動主機將響應(yīng)信號直接發(fā)送給發(fā)送方。 發(fā)送者可利用當(dāng)前的轉(zhuǎn)交地址來直接將后續(xù)包發(fā)

10、送給移動主機。 28、移動用戶路由轉(zhuǎn)發(fā)過程：發(fā)件人， 將包發(fā)送到第二歸屬地址，第一注冊轉(zhuǎn)交地址、第三隧道至轉(zhuǎn)交地址、歸屬代理、移動主機、第四回復(fù)發(fā)送者、第五隧道至轉(zhuǎn)交地址、第29隧道、ad hoc網(wǎng)絡(luò)、移動ad hoc網(wǎng)絡(luò)按需向量路由算法是一種相對向量路由算法?？紤]到節(jié)點帶寬有限，電池壽命短，它適合于移動環(huán)境中的工作。 30、AODV路由算法、路徑發(fā)現(xiàn)、(a ) rangeofasbroadcast.(b ) afterbanddhavereceivedasbroadcast.(c ) afterc，f andhavereceivedasbroadca h andihavereceivedasbroadcast.shadednodesarenewrecipients.arrowssshowposibleereverseroutes .31，pathmaintenance，各節(jié)點定期進行HELLO 如果沒有應(yīng)答，消息廣播者就知道附近的人已經(jīng)失效，或者離開接收范圍，所以和