路由算法分類(lèi)

1、路由算法及分類(lèi)路由算法及分類(lèi)：1、非自適應(yīng)算法，靜態(tài)路由算法 不能根據(jù)網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)的變化更新路由表，使用靜態(tài)路由表，也稱(chēng)為固定式路由選擇算法。 特點(diǎn)：簡(jiǎn)單，開(kāi)銷(xiāo)少；靈活性差。 2、自適應(yīng)算法，動(dòng)態(tài)路由算法 可根據(jù)網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)的變化更新路由表。 特點(diǎn)：開(kāi)銷(xiāo)大；健壯性和靈活性好。 3、最優(yōu)化原則（optimality principle） 如果路由器 J 在路由器 I 到 K 的最優(yōu)路由上，那么從 J 到 K 的最優(yōu)路由會(huì)落在同一路由上。 4、匯集樹(shù)（sink tree） 從所有的源結(jié)點(diǎn)到一個(gè)給定的目的結(jié)點(diǎn)的最優(yōu)路由的集合形成了一個(gè)以目的結(jié)點(diǎn)為根的樹(shù)，稱(chēng)為匯集樹(shù)； 路由算法的目的是找出

2、并使用匯集樹(shù)。 幾種典型的路由選擇算法：1、最短路徑路由算法（Shortest Path Routing） 1）基本思想 構(gòu)建子網(wǎng)的拓?fù)鋱D，圖中的每個(gè)結(jié)點(diǎn)代表一個(gè)路由器，每條弧代表一條通信線路。為了選擇兩個(gè)路由器間的路由，算法在圖中找出最短路徑。 2）測(cè)量路徑長(zhǎng)度的方法 結(jié)點(diǎn)數(shù)量 地理距離 傳輸延遲 距離、信道帶寬等參數(shù)的加權(quán)函數(shù) 3）Dijkstra算法 每個(gè)結(jié)點(diǎn)用從源結(jié)點(diǎn)沿已知最佳路徑到本結(jié)點(diǎn)的距離來(lái)標(biāo)注，標(biāo)注分為臨時(shí)性標(biāo)注和永久性標(biāo)注； 初始時(shí)，所有結(jié)點(diǎn)都為臨時(shí)性標(biāo)注，標(biāo)注為無(wú)窮大； 將源結(jié)點(diǎn)標(biāo)注為0，且為永久性標(biāo)注，并令其為工作結(jié)點(diǎn)； 檢查與工作結(jié)點(diǎn)相鄰的臨時(shí)性結(jié)點(diǎn)，若該結(jié)點(diǎn)到工作結(jié)點(diǎn)

3、的距離與工作結(jié)點(diǎn)的標(biāo)注之和小于該結(jié)點(diǎn)的標(biāo)注，則用新計(jì)算得到的和重新標(biāo)注該結(jié)點(diǎn)； 在整個(gè)圖中查找具有最小值的臨時(shí)性標(biāo)注結(jié)點(diǎn)，將其變?yōu)橛谰眯越Y(jié)點(diǎn)，并成為下一輪檢查的工作結(jié)點(diǎn)； 重復(fù)第四、五步，直到目的結(jié)點(diǎn)成為工作結(jié)點(diǎn)；2、洪泛及選擇洪泛算法 1） 洪泛算法（Flooding） 屬于靜態(tài)路由算法 a)基本思想 把收到的每一個(gè)包，向除了該包到來(lái)的線路外的所有輸出線路發(fā)送。 b)主要問(wèn)題 洪泛要產(chǎn)生大量重復(fù)包。 c)解決措施 每個(gè)包頭包含站點(diǎn)計(jì)數(shù)器，每經(jīng)過(guò)一站計(jì)數(shù)器減1，為0時(shí)則丟棄該包； 記錄包經(jīng)過(guò)的路徑 2）選擇性洪泛算法（selective flooding） 洪泛法的一種改進(jìn)。將進(jìn)來(lái)的每個(gè)包僅發(fā)

4、送到與正確方向接近的線路上。 3）應(yīng)用情況 路由器和線路的資源過(guò)于浪費(fèi)，實(shí)際很少直接采用； 具有極好的健壯性，可用于軍事應(yīng)用； 作為衡量標(biāo)準(zhǔn)評(píng)價(jià)其它路由算法。 3、基于流量的路由算法（Flow-Based Routing） 屬于靜態(tài)路由算法 1）基本思想 既考慮拓?fù)浣Y(jié)構(gòu)，又兼顧網(wǎng)絡(luò)負(fù)荷； 前提：每對(duì)結(jié)點(diǎn)間平均數(shù)據(jù)流是相對(duì)穩(wěn)定和可預(yù)測(cè)的； 根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均包延遲，因此路由選擇問(wèn)題歸結(jié)為找產(chǎn)生網(wǎng)絡(luò)最小延遲的路由選擇算法。 提前離線（off-line）計(jì)算 2）需要預(yù)知的信息 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)； 通信量矩陣Fij； 線路帶寬矩陣Cij； 3）路由算法（可能是臨時(shí)的） 1/m = 800

5、 bits 根據(jù)排隊(duì)論，平均延遲 T = 1/ (mC - l) 4、距離向量路由算法（Distance Vector Routing） 屬于動(dòng)態(tài)路由算法，也稱(chēng)Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP協(xié)議采用。 1）基本思想 每個(gè)路由器維護(hù)一張表，表中給出了到每個(gè)目的地的已知最佳距離和線路，并通過(guò)與相鄰路由器交換距離信息來(lái)更新表； 以子網(wǎng)中其它路由器為表的索引，表項(xiàng)包括兩部分：到達(dá)目的結(jié)點(diǎn)的最佳輸出線路，和到達(dá)目的結(jié)點(diǎn)所需時(shí)間或距離； 每隔一段時(shí)間，路由器向所有鄰居結(jié)點(diǎn)發(fā)送它到每個(gè)目的結(jié)點(diǎn)的距離表，同時(shí)它也接收每個(gè)鄰居結(jié)點(diǎn)發(fā)來(lái)的距離表

6、； 鄰居結(jié)點(diǎn)X發(fā)來(lái)的表中，X到路由器i的距離為Xi，本路由器到X的距離為m，則路由器經(jīng)過(guò)X到i的距離為Xi + m。根據(jù)不同鄰居發(fā)來(lái)的信息，計(jì)算Xi + m，并取最小值，更新本路由器的路由表； 注意：本路由器中的老路由表在計(jì)算中不被使用 2）無(wú)限計(jì)算問(wèn)題 算法的缺陷：對(duì)好消息反應(yīng)迅速，對(duì)壞消息反應(yīng)遲鈍； 3）水平分裂算法 工作過(guò)程與距離向量算法相同，區(qū)別在于到X的距離不向真正通向X的鄰居結(jié)點(diǎn)報(bào)告，使得壞消息傳播的也快。 雖然廣泛使用，但有時(shí)候會(huì)失敗。 5、鏈路狀態(tài)路由算法 （Link State Routing） 1）距離向量路由算法的主要問(wèn)題 選擇路由時(shí)，沒(méi)有考慮線路帶寬； 路由收斂速度慢。

7、 2）鏈路狀態(tài)路由算法 發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址； 路由器啟動(dòng)后，通過(guò)發(fā)送HELLO包發(fā)現(xiàn)鄰居結(jié)點(diǎn)； 兩個(gè)或多個(gè)路由器連在一個(gè)LAN時(shí)，引入人工結(jié)點(diǎn)； 測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或開(kāi)銷(xiāo)； 一種直接的方法是：發(fā)送一個(gè)要對(duì)方立即響應(yīng)的ECHO包，來(lái)回時(shí)間除以2即為延遲。 將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)包； 包以發(fā)送方的標(biāo)識(shí)符開(kāi)頭，后面是序號(hào)、年齡和一個(gè)鄰居結(jié)點(diǎn)列表； 列表中對(duì)應(yīng)每個(gè)鄰居結(jié)點(diǎn)，都有發(fā)送方到它們的延遲或開(kāi)銷(xiāo)； Fig. 5-15 鏈路狀態(tài)包定期創(chuàng)建或發(fā)生重大事件時(shí)創(chuàng)建。 將這個(gè)包發(fā)送給所有其它路由器； 3）基本思想 洪泛鏈路狀態(tài)包，為控制洪泛，每個(gè)包包含一個(gè)序號(hào)，每次發(fā)送新包時(shí)加

8、1。路由器記錄信息對(duì)（源路由器，序號(hào)），當(dāng)一個(gè)鏈路狀態(tài)包到達(dá)時(shí)，若是新的，則分發(fā)；若是重復(fù)的，則丟棄；若序號(hào)比路由器記錄中的最大序號(hào)小，則認(rèn)為過(guò)時(shí)而丟棄； 4）改進(jìn) 序號(hào)循環(huán)使用會(huì)混淆，解決辦法：使用32位序號(hào)； 路由器崩潰后，序號(hào)重置； 鏈路狀態(tài)包到達(dá)后，延遲一段時(shí)間，并與其它已到達(dá)的來(lái)自同一路由器的鏈路狀態(tài)包比較序號(hào)，丟棄重復(fù)包，保留新包； 鏈路狀態(tài)包需要應(yīng)答； 計(jì)算到每個(gè)其它路由器的最短路徑。 根據(jù)Dijkstra算法計(jì)算最短路徑； 5）實(shí)用協(xié)議 OSPF IS-IS 從E發(fā)來(lái)的鏈路狀態(tài)包有兩個(gè)，一個(gè)經(jīng)過(guò)EAB，另一個(gè)經(jīng)過(guò)EFB； 從D發(fā)來(lái)的鏈路狀態(tài)包有兩個(gè)，一個(gè)經(jīng)過(guò)DCB，另一個(gè)經(jīng)過(guò)D

9、FB； 6、分層路由（Hierarchical Routing） 1）網(wǎng)絡(luò)規(guī)模增長(zhǎng)帶來(lái)的問(wèn)題 路由器中的路由表增大； 路由器為選擇路由而占用的內(nèi)存、CPU時(shí)間和網(wǎng)絡(luò)帶寬增大。 2）分層路由 分而治之的思想； 根據(jù)需要，將路由器分成區(qū)域（regions）、聚類(lèi)（clusters）、區(qū)（zones）和組（groups） Fig. 5-17，路由表由17項(xiàng)減為7項(xiàng)。 3）分層路由帶來(lái)的問(wèn)題 路由表中的路由不一定是最優(yōu)路由。 7、移動(dòng)主機(jī)的路由 1）需要解決的問(wèn)題 為了能夠?qū)?shù)據(jù)包轉(zhuǎn)發(fā)給移動(dòng)主機(jī)，網(wǎng)絡(luò)必須首先要找到移動(dòng)的主機(jī)。 2）網(wǎng)絡(luò)結(jié)構(gòu)示意圖 3）一些基本概念 移動(dòng)用戶（mobile users）

10、：包括位置發(fā)生變化，通過(guò)固定方式或移動(dòng)方式與網(wǎng)絡(luò)連接的兩類(lèi)用戶； 家鄉(xiāng)位置（home location）：所有用戶都有一個(gè)永久的家鄉(xiāng)位置，用一個(gè)地址來(lái)標(biāo)識(shí)； 外部代理（foreign agent）：每個(gè)區(qū)域（一個(gè)LAN或一個(gè)wireless cell）有一個(gè)或多個(gè)外部代理，它們記錄正在訪問(wèn)該區(qū)域的移動(dòng)用戶； 家鄉(xiāng)代理（home agent）：每個(gè)區(qū)域有一個(gè)家鄉(xiāng)代理，負(fù)責(zé)記錄家鄉(xiāng)在該區(qū)域，但是目前正在訪問(wèn)其它區(qū)域的用戶。 移動(dòng)用戶進(jìn)入一個(gè)新區(qū)域時(shí)，必須首先向外部代理注冊(cè) 外部代理定期廣播聲明自己的存在和地址的包，新到達(dá)的移動(dòng)主機(jī)接收該信息；若移動(dòng)用戶未能收到該信息，則移動(dòng)主機(jī)廣播包，詢(xún)問(wèn)外部代理

11、的地址； 移動(dòng)主機(jī)向外部代理注冊(cè)，告知其家鄉(xiāng)地址、目前的數(shù)據(jù)鏈路層地址和一些安全信息； 外部代理與移動(dòng)主機(jī)的家鄉(xiāng)代理聯(lián)系，告知移動(dòng)主機(jī)的目前位置、自己的網(wǎng)絡(luò)地址和一些安全信息； 家鄉(xiāng)代理檢查安全信息，通過(guò)，則給外部代理確認(rèn)； 外部代理收到確認(rèn)后，在登記表中加入一項(xiàng)，并通知移動(dòng)主機(jī)注冊(cè)成功 4）移動(dòng)用戶的路由轉(zhuǎn)發(fā)過(guò)程 當(dāng)一個(gè)包發(fā)給移動(dòng)用戶時(shí)，首先被轉(zhuǎn)發(fā)到用戶的家鄉(xiāng)局域網(wǎng)； 該包到達(dá)用戶的家鄉(xiāng)局域網(wǎng)后，被家鄉(xiāng)代理接收，家鄉(xiāng)代理查詢(xún)移動(dòng)用戶的新位置和與其對(duì)應(yīng)的外部代理的地址； 家鄉(xiāng)代理采用隧道技術(shù)，將收到的包作為凈荷封裝到一個(gè)新包中，發(fā)給外部代理； 家鄉(xiāng)代理告訴發(fā)送方，發(fā)給移動(dòng)用戶的后續(xù)包作為凈荷封裝成包直接發(fā)給外部代理； 外部代理收到包后，將凈荷作為數(shù)據(jù)鏈路幀發(fā)給移動(dòng)用戶；8、廣播路由（Broadcast Routing） 廣播（broadcasting）：同時(shí)發(fā)送一個(gè)包給所有目的地。 1）實(shí)現(xiàn)廣播路由的方法 通過(guò)多個(gè)點(diǎn)到點(diǎn)通信實(shí)現(xiàn)，缺點(diǎn)：浪費(fèi)帶寬，源主機(jī)需要知道所有目的地； 洪泛（flooding）方式，缺點(diǎn)：浪費(fèi)帶寬 多目的地路由（multidestination routing） 每個(gè)包包括一個(gè)目的地列表或一個(gè)目的地位圖； 路由器根據(jù)目的地做路由選擇，在相應(yīng)輸出線路