動態路由算法

靜態路由算法不能根據網路流量和拓撲結構的變化來調整自身的路由表，也就不能找出最佳路由，動態路由算法則是節點的路由選擇要依靠網路當前的狀態信息來決定。這種策略能較好地適應網路流量、拓撲結構的變化，有利於改善網路的性能。但由於算法複雜，會增加網路的負擔。

基本介紹

• 中文名：動態路由算法
• 外文名：Dynamic routing algorithm
• 決定方式：依靠網路當前的狀態信息來決定
• 方法分類：分為3種

基本信息

動態路由算法

靜態路由算法不能根據網路流量和拓撲結構的變化來調整自身的路由表，也就不能找出最佳路由，動態路由算法則是節點的路由選擇要依靠網路當前的狀態信息來決定。這種策略能較好地適應網路流量、拓撲結構的變化，有利於改善網路的性能。但由於算法複雜，會增加網路的負擔。實用的三種路由策略是：

（1）分散式路由選擇。基本算法有距離向量算法和鏈路狀態算法；

（2）集中式路由選擇。由網路控制中心（Network Control Center，NCC）負責全網狀態信息的收集、路由計算及最佳路由的實現。最簡單的方法是將最新路由定期傳送到網路中各節點上去。

（3）混合式動態路由選擇。將分布路由選擇與集中路由選擇、以及其它路由選擇方法混合使用。

下面主要介紹分散式路由選擇的兩種算法。

1．距離向量路由選擇算法(Distance Vector Routing)

各節點周期性地向所有相鄰節點傳送路由刷新報文，報文由一組(V，D)有序數據對組成，V表示該節點可以到達的節點，D表示到達該節點的距離(跳數)。收到路由刷新報文的節點重新計算和修改它的路由表。

距離向量路由算法具有簡單，易於實現的優點。但它不適用於路由劇烈變化的或大型的網路環境。因為某個節點的路由變化像波動一樣從相鄰節點傳播出去，其過程是非常緩慢的，稱之為“慢收斂”。因此，在距離向量路由選擇算法的路由刷新過程中，可能會出現路由不一致問題。距離向量路由選擇算法的另一個缺陷是它需要大量的信息交換，但很多都可能是與當前路由刷新無關的。

2．鏈路狀態路由選擇

鏈路-狀態路由選擇算法的基本思想很簡單，可以分成以下五個部分敘述：

⑴ 每個節點必須找出它的所有鄰居

其他信息

當一個節點啟動後，通過在每一條點到點的鏈路上傳送一個特殊的HELLO報文，並通過鏈路另一端的節點傳送一個應答報文告訴它自己是誰。

⑵ 每個節點測量到它的每個鄰居的時延或其他參數

鏈路-狀態路由選擇算法要求每個節點都知道到它的每個鄰居的時延。

測量這種時延的最直接的方法是在它們之間的鏈路上傳送一個特殊的ECHO回響報文，並且要求對方收到後立即再將其傳送回來。將測量得到的來回時間除以2，即可得到一個比較合理的估計。為了得到更準確的結果，可以將測試重複多次，取平均值。

⑶ 建立鏈路-狀態報文

收集齊了用於交換的信息後，下一步就為每一個節點建立一個包含所有數據的報文。報文以傳送者的標識符開始，隨後為順序號以及它的所有鄰居的列表。對於每一個鄰居，給出到此鄰居的時延。

建立鏈路-狀態報文很容易，困難是決定何時建立它們。一種可行的方法是每隔一段規律的時間間隔周期性地建立它們。另一種可行的方法是當節點檢測到了某些重要事件的發生時建立它們。例如，一條鏈路或一個鄰居崩潰或恢復時，建立它們。

⑷ 分發鏈路-狀態報文

基本的分發算法是使用順序號的洪泛法。這種分發算法由於循環使用順序號、某個節點曾經崩潰或某個順序號曾經被誤用過等原因，可能會使不同的節點使用不同版本的拓撲結構，這將導致不穩定、循環、到達不了目的機器及其他問題。為了防止這類錯誤的發生，需要在每個報文中包含一個年齡域，年齡每秒減1，當年齡減到0時，丟棄此報文。

⑸ 計算新路由

一旦一個節點收集齊了所有來自於其他節點的鏈路-狀態報文，它就可以據此構造完整的網路拓撲結構圖，然後使用Dijkstra算法在本地構造到所有可能的目的地的最短通路。

鏈路-狀態路由選擇算法具有各節點獨立計算最短通路、能夠快速適應網路變化、交換的路由信息少等優點，但相對於距離向量路由選擇算法，它較複雜、難以實現。