-
路由算法
鎖定
- 中文名
- 路由算法
- 外文名
- routingalgorithm
- 屬 性
- 計算機用語
路由算法簡介
路由算法是提高路由協議功能,儘量減少路由時所帶來開銷的算法。當實現路由算法的軟件必須運行在物理資源有限的計算機上時高效尤其重要。路由算法必須健壯,即在出現不正常或不可預見事件的情況下必須仍能正常處理,例如硬件故障、高負載和不正確的實現。因為路由器位於網絡的連接點,當它們失效時會產生重大的問題。最好的路由算法通常是那些經過了時間考驗,證實在各種網絡條件下都很穩定的算法。
此外路由算法必須能快速聚合,聚合是所有路由器對最佳路徑達成一致的過程。當某網絡事件使路徑斷掉或不可用時,路由器通過網絡分發路由更新信息,促使最佳路徑的重新計算,最終使所有路由器達成一致。聚合很慢的路由算法可能會產生路由環或網路中斷。
路由算法主要目的
路由器使用路由算法來找到到達目的地的最佳路由。當説“最佳路由”時,考慮的參數包括諸如跳躍數(分組數據包在網絡中從一個路由器或中間節點到另外的節點的行程)、延時以及分組數據包傳輸通信耗時。關於路由器如何收集網絡的結構信息以及對之進行分析來確定最佳路由,有兩種主要的路由算法:
總體式路由算法和分散式路由算法。採用分散式路由算法時,每個路由器只有與它直接相連的路由器的信息——而沒有網絡中的每個路由器的信息。這些算法也被稱為DV(距離向量)算法。採用總體式路由算法時,每個路由器都擁有網絡中所有其他路由器的全部信息以及網絡的流量狀態。這些算法也被稱為LS(鏈路狀態)算法。
路由算法設計目標
(1)最優化:指路由算法選擇最佳路徑的能力。根據metric的值和權值來計算。
(3)堅固性:路由算法處於非正常或不可預料的環境時,如硬件故障、負載過高或操作失誤時,都能正確運行。由於路由器分佈在網絡聯接點上,所以在它們出故障時會產生嚴重後果。最好的路由器算法通常能經受時間的考驗,並在各種網絡環境下被證實是可靠的。
(4)快速收斂:收斂是在最佳路徑的判斷上所有路由器達到一致的過程。當某個網絡事件引起路由可用或不可用時,路由器就發出更新信息。路由更新信息遍及整個網絡,引發重新計算最佳路徑,最終達到所有路由器一致公認的最佳路徑。收斂慢的路由算法會造成路徑循環或網絡中斷。
路由算法技術要素
路由算法區分要素
路由算法靜態與動態
靜態路由算法很難算得上是算法,只不過是開始路由前由網管建立的表映射。這些映射自身並不改變,除非網管去改動。使用靜態路由的算法較容易設計,在網絡通信可預測及簡單的網絡中工作得很好。由於靜態路由系統不能對網絡改變做出反映,通常被認為不適用於的大型、易變的網絡。九十年代主要的路由算法都是動態路由算法,通過分析收到的路由更新信息來適應網絡環境的改變。如果信息表示網絡發生了變化,路由軟件就重新計算路由併發出新的路由更新信息。這些信息滲入網絡,促使路由器重新計算並對路由表做相應的改變。動態路由算法可以在適當的地方以靜態路由作為補充。例如,最後可選路由(router of last resort),作為所有不可路由分組的去路,保證了所有的數據至少有方法處理。
路由算法單路徑與多路徑
路由算法平坦與分層
一些路由協議在平坦的空間裏運作,其它的則有路由的層次。在平坦的路由系統中,每個路由器與其它所有路由器是對等的;在分層次的路由系統中,一些路由器構成了路由主幹,數據從非主幹路由器流向主幹路由器,然後在主幹上傳輸直到它們到達目標所在區域,在這裏,它們從最後的主幹路由器通過一個或多個非主幹路由器到達終點。路由系統通常設計有邏輯節點組,稱為域、自治系統或區間。
分層路由的主要優點是它模擬了多數公司的結構,從而能很好地支持其通信。多數的網絡通信發生在小組中(域)。因為域內路由器只需要知道本域內的其它路由器,它們的路由算法可以簡化,根據所使用的路由算法,路由更新的通信量可以相應地減少。
路由算法主機與路由器
一些路由算法假定源結點來決定整個路徑,這通常稱為源路由。在源路由系統中,路由器只作為存貯轉發設備,無意識地把分組發向下一跳。其它路由算法假定主機對路徑一無所知,在這些算法中,路由器基於自己的計算決定通過網絡的路徑。前一種系統中,主機具有決定路由的智能,後者則為路由器具有此能力。
主機智能和路由器智能的折衷實際是最佳路由與額外開銷的平衡。主機智能系統通常能選擇更佳的路徑,因為它們在發送數據前探索了所有可能的路徑,然後基於特定系統對“優化”的定義來選擇最佳路徑。然而確定所有路徑的行為通常需要很多的探索通信量和很長的時間。
路由算法域內與域間
路由算法鏈接與距離
鏈接狀態算法(也叫做短路徑優先算法)把路由信息散佈到網絡的每個節點,不過每個路由器只發送路由表中描述其自己鏈接狀態的部分。距離向量算法(也叫做Bellman-Ford算法)中每個路由器發送路由表的全部或部分,但只發給其鄰居。也就是説,鏈接狀態算法到處發送較少的更新信息,而距離向量算法只向相鄰的路由器發送較多的更新信息。
由於鏈接狀態算法聚合得較快,它們相對於距離算法產生路由環的傾向較小。在另一方面,鏈接狀態算法需要更多的CPU和內存資源,因此鏈接狀態算法的實現和支持較昂貴。雖然有差異,這兩種算法類型在多數環境中都可以工作得很好。
路由算法度量標準
路由算法路徑長度
路徑長度是最常用的路由metric。一些路由協議允許網管給每個網絡鏈接人工賦以代價值,這種情況下,路由長度是所經過各個鏈接的代價總和。其它路由協議定義了跳數,即分組在從源到目的的路途中必須經過的網絡產品,如路由器的個數。
路由算法可靠性
可靠性,在路由算法中指網絡鏈接的可依賴性(通常以位誤率描述),有些網絡鏈接可能比其它的失效更多,網路失效後,一些網絡鏈接可能比其它的更易或更快修復。任何可靠性因素都可以在給可靠率賦值時計算在內,通常是由網管給網絡鏈接賦以metric值。
路由算法路由延遲
路由延遲指分組從源通過網絡到達目的所花時間。很多因素影響到延遲,包括中間的網絡鏈接的帶寬、經過的每個路由器的端口隊列、所有中間網絡鏈接的擁塞程度以及物理距離。因為延遲是多個重要變量的混合體,它是個比較常用且有效的metric。
路由算法帶寬
帶寬指鏈接可用的流通容量。在其它所有條件都相等時,10Mbps的以太網鏈接比64kbps的專線更可取。雖然帶寬是鏈接可獲得的最大吞吐量,但是通過具有較大帶寬的鏈接做路由不一定比經過較慢鏈接路由更好。例如,如果一條快速鏈路很忙,分組到達目的所花時間可能要更長。
路由算法負載
路由算法通信代價
通信代價是另一種重要的metric,尤其是有一些公司可能關心運作費用甚於關心性能。即使線路延遲可能較長,他們也寧願通過自己的線路發送數據而不採用昂貴的公用線路。
路由算法典型種類
路由算法LS算法
2、測量相鄰路由器的延時(或者其他重要的網絡參數,比如平均流量)。為做到這一點,路由器向整個網絡發送響應分組數據包。每個接收到數據包的路由器返回一個應答分組數據包。將路程往返時間除以2,路由器便可以計算出延時。(路程往返時間是網絡當前延遲的量度,通過一個分組數據包從遠程主機返回的時間來測量。)該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。
在這一步中,路由器選擇通往每一個節點的最佳路由。它們使用一個算法來實現這一點,如Dijkstra最短路徑算法。在這個算法中,一個路由器通過收集到的其他路由器的信息,建立一個網絡圖。這個圖描述網絡中的路由器的位置以及它們之間的鏈接關係。每個鏈接都有一個數字標註,稱為權值或成本。這個數字是延時和平均流量的函數,有時它僅僅表示節點間的躍點數。例如,如果一個節點與目的地之間有兩條鏈路,路由器將選擇權值最低的鏈路。
路由算法Dijkstra算法
Dijkstra算法執行下列步驟:1、路由器建立一張網絡圖,並且確定源節點和目的節點,在這個例子裏我們設為V1和V2。然後路由器建立一個矩陣,稱為“鄰接矩陣”。在這個矩陣中,各矩陣元素表示權值。例如,[i, j]是節點Vi與Vj之間的鏈路權值。如果節點Vi與Vj之間沒有鏈路直接相連,它們的權值設為“無窮大”。
長度字段——表示從源節點到當前節點的權值之和。
路由算法鏈路向量選路算法
路由算法距離向量算法
距離向量算法(也稱為Bellman-Ford算法)則要求每個路由器發送其路由表全部或部分信息,但僅發送到鄰近結點上。從本質上來説,鏈路狀態算法將少量更新信息發送至網絡各處,而距離向量算法發送大量更新信息至鄰接路由器。 ——由於鏈路狀態算法收斂更快,因此它在一定程度上比距離向量算法更不易產生路由循環。但另一方面,鏈路狀態算法要求比距離向量算法有更強的CPU能力和更多的內存空間,因此鏈路狀態算法將會在實現時顯得更昂貴一些。
路由算法分級路由
可以看到,在LS和DV算法中,每個路由器都需要保存其他路由器的一些信息。隨着網絡規模的擴大,網絡中的路由器也將增加。因此,路由表的規模也將增大,從而使路由器不能有效地處理網絡流量。使用分級路由可以解決這個問題。讓使用DV算法來查找節點間的最佳路由。
在下述情形中,網絡中的每個節點保存了一個有17個記錄的路由表。在分級路由中,路由器被分成很多組,稱為區域。每個路由器都只有自己所在區域路由器的信息,而沒有其他區域路由器的信息。所以在其路由表中,路由器只需要存儲其他每個區域的一條記錄。在這個例子中,我們將網絡分為5個區域。