路由表建立的算法

一、路由表

    在計算機網絡中，路由表或稱路由擇域信息庫（RIB）是一個存儲在路由器或者聯網計算機中的電子表格（文件）或類數據庫。路由表存儲著指向特定網絡地址的路徑（在有些情況下，還記錄有路徑的路由度量值）。路由表中含有網絡周邊的拓撲信息。路由表建立的主要目標是為了實現路由協議和靜態路由選擇。

    在現代路由器構造中，路由表不直接參與數據包的傳輸，而是用于生成一個小型指向表，這個指向表僅僅包含由路由算法選擇的數據包傳輸優先路徑，這個表格通常為了優化硬件存儲和查找而被壓縮或提前編譯。

二、路由算法簡介

    路由算法是提高路由協議功能，盡量減少路由時所帶來開銷的算法。當實現路由算法的軟件必須運行在物理資源有限的計算機上時高效尤其重要。路由算法必須健壯，即在出現不正常或不可預見事件的情況下必須仍能正常處理，例如硬件故障、高負載和不正確的實現。因為路由器位于網絡的連接點，當它們失效時會產生重大的問題。最好的路由算法通常是那些經過了時間考驗，證實在各種網絡條件下都很穩定的算法。

    此外路由算法必須能快速聚合，聚合是所有路由器對最佳路徑達成一致的過程。當某網絡事件使路徑斷掉或不可用時，路由器通過網絡分發路由更新信息，促使最佳路徑的重新計算，最終使所有路由器達成一致。聚合很慢的路由算法可能會產生路由環或網路中斷。

三、路由算法的目標特點

    路由算法通常具有下列目標特點的一個或多個：優化、簡單、低耗、健壯、穩定、快速聚合、靈活性。

   （1）最優化：指路由算法選擇最佳路徑的能力。根據metric的值和權值來計算。

   （2）簡潔性：算法設計必須簡潔。路由協議在網絡中必須高效地提供其功能，盡量減少軟件和應用的開銷。這在當實現路由算法的軟件必須運行在物理資源有限的計算機上時尤其重要。

   （3）堅固性：路由算法處于非正常或不可預料的環境時，如硬件故障、負載過高或操作失誤時，都能正確運行。由于路由器分布在網絡聯接點上，所以在它們出故障時會產生嚴重后果。最好的路由器算法通常能經受時間的考驗，并在各種網絡環境下被證實是可靠的。

   （4）快速收斂：收斂是在最佳路徑的判斷上所有路由器達到一致的過程。當某個網絡事件引起路由可用或不可用時，路由器就發出更新信息。路由更新信息遍及整個網絡，引發重新計算最佳路徑，最終達到所有路由器一致公認的最佳路徑。收斂慢的路由算法會造成路徑循環或網絡中斷。

   （5）靈活性：路由算法要求可以快速、準確地適應各種網絡環境。例如，某個網段發生故障，路由算法要能很快發現故障，并為使用該網段的所有路由選擇另一條最佳路徑。

四、路由算法分類

    路由器使用路由算法來找到到達目的地的最佳路由。當說“最佳路由”時，考慮的參數包括諸如跳躍數（分組數據包在網絡中從一個路由器或中間節點到另外的節點的行程）、延時以及分組數據包傳輸通信耗時。

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

   （1）分布式路由選擇。每個路由器只有與它直接相連的路由器的信息——而沒有網絡中的每個路由器的信息。這些算法也被稱為DV（距離向量）算法。

   （2）集中式路由選擇。每個路由器都擁有網絡中所有其他路由器的全部信息以及網絡的流量狀態。這些算法也被稱為LS（鏈路狀態）算法。

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

五、距離向量算法

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

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

六、鏈路狀態算法

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

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

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

    鏈路-狀態路由選擇算法要求每個節點都知道到它的每個鄰居的時延。測量這種時延的最直接的方法是在它們之間的鏈路上發送一個特殊的ECHO響應報文，并且要求對方收到后立即再將其發送回來。將測量得到的來回時間除以2，即可得到一個比較合理的估計。為了得到更準確的結果，可以將測試重復多次，取平均值。

    ⑶ 建立鏈路-狀態報文

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

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

    ⑷ 分發鏈路-狀態報文

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

    ⑸ 計算新路由

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

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