路由算法分類

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

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

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

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

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

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

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

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

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

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

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