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

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

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

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

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

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

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

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

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

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

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