路由表是指路由器或者其他網際網路網路設備上存儲的一張路由信息表，該表中存有到達特定網路終端的路徑，在某些情況下，還有一些與這些路徑相關的度量。下一節點路由選擇表是指在路由表中選擇下一個節點，一般路由選擇算法有關。
基本介紹
- 中文名：下一節點路由選擇表
- 外文名：Next node routing table
- 學科：計算機
- 定義：路由表中選擇下一個節點
- 有關術語：路由表
- 領域：計算機網路
簡介,IP路由,路由查找,軟體路由查找算法,硬體路由查找算法,路由表,路由算法,
簡介
下一節點路由選擇表即在路由表中選擇下一個路由節點。下一節點路由選擇表與計算機網路中很多因素都有關，例如節點可達性、節點所屬路由域、傳輸代價、路由算法等。
IP路由
IP協定的路由功能是由路由器實現的的，當路由器接收到一個報文，它抽出報文中的目的地址，然後，從目的地址中找出目的地的網路號查找路由選擇表尋找與目的地址中網路相匹配的項。每個路由選擇表項包含了用來轉發報文的接口信息，也就是到目的地路徑中的下一個路由器的地址。路由器的第二個工作，是維持路由選擇表。這些表是由網路管理者創建的，或通過與其它路由器交換路由信息創建。當一個路由器初始引導時，它只知道與它直接相連的接口，如果網路中的路由器正在運行路由選擇協定，當路由器知道與它相鄰接的路由器相連的網路時，新的路由表表項將被創建每個路由選擇表表項都被標識一個字元，該字元表示路由信息的源端。
路由查找
整個路由過程中，查表算法的優劣直接影響了當前和未來網際網路網路的整體性能。當前，網際網路的規模、鏈路速度、頻寬、流量等都呈指數級增長 ，這對路由器中IP路由查找算法對大容量路由表處理的適應性以及報文轉發查表的能力提出了更高要求。路由器是構成網際網路的中間節點，其轉發性能決定了網際網路的整體性能。因此，IP路由查找操作已經成為了當前路由器轉發性能的瓶頸之一 。其實路由查找問題本身很簡單，但由於其對性能要求很高，因此有很大的難度。通常評價IP路由查表算法的標準主要有高速查找、記憶體需求小、更新時間短、實現的靈活性強、能夠處理真實的大容量路由表以及預處理時間短等。IP 路由查找方案可以分為以下幾類：（1）基於精確匹配的改進方案：這種方案一般效率不高，為了找到最佳結果，一般需要log2N步（N 為路由表項的數目）；（2）層次方案：這是普遍採用的一種查找方案，在 BSD核心中得到實現 。它最壞情況下的複雜度為O（W），而且需要 32或 128 次（分別對應IPv4 和IPv6）存儲訪問，效率也不高；（3）硬體實現:這種方法需要昂貴的內容定址存儲器，而且擴展性不好；（4）基於協定的解決方案：現在的IP交換和標記交換技術就屬於這種方式；這種方案也無法完全避免搜尋，特別是邊界路由器仍然需要執行繁重的路由決策。
軟體路由查找算法
軟體路由查找算法主要有基於二分支的算法，基於多分支的算法，還有前綴維度上的二分搜尋算法 、最差性能受限的近似最優路由查找算法 、多路前綴值範圍搜尋樹算法等。基於二分法的算法有Redix Rrie、Patricia、Multiway 和Multicolumn等。這些算法的基本思想是根據前綴值的二進制位構建二叉樹，在檢索時用目標地址作為索引，在二叉樹中遍歷；當找到一個匹配的前綴時，將其作為到目前為止所發現的最長前綴，繼續搜尋更長的匹配前綴，直到再沒有分支可以搜尋時，搜尋結束，此時所記錄的最長前綴就是所要尋找的最長前綴匹配。在基於多分支的算法二叉樹算法中，每個搜尋步驟能夠將第一步開始的整個232搜尋空間減少一半，而多叉樹可以令每個搜尋步驟減少更多的搜尋空間。此類算法的典型有 LC Trie樹算法 、受控前綴擴展算法 。可變分支數目的多分支Trie樹結構，其搜尋過程與二叉樹類似，只是由一位比較變成了多位比較以決定下一步搜尋的子樹。Srinivasan對分支數目和層次數目的選取做了詳細的分析，並提出了多分支樹的一般結構，所有基於Trie樹的算法都可以看作是該一般結構的特例或變形。此外他還提出了前綴擴展技術，以耗費更多記憶體為代價來避免最長前綴匹配所帶來的回溯問題。其它軟體算法有前綴維度上的二分搜尋算法 、最差性能受限的近似最優路由查找算法 、多路前綴值範圍搜尋樹算法等。這些算法並不是對整個 前綴地址空間進行搜尋，因此對於地址寬度的敏感性較低。前者的搜尋時間複雜度是O(log2w)，而後兩個算法的搜尋時間複雜度與地址寬度無關。因此，這幾個算法能夠用於 IPv6的路由查找。
硬體路由查找算法
硬體路由查找算法有24-8 DIR算法、基於TCAM（三值 TCAM）的算法。24-8 DIR算法實際是一種用硬體實現的多分支前綴擴展算法。該算法基於對於前綴長度分布的統計數據長度大於24的前綴非常少，因此該算法將所有前綴全部展開為24位前綴。所以，它 只 有 兩級：第一級224個分支，若有第二級節點，則該第一級節點有28個二級子節點。在一般情況下只需一次訪存即可找到目標路由，而對於長度大於24的前綴則最多只需要進行兩次訪存。因此，這是一種“以存儲器速度進行路由查找”的算法，也是典型的用空間換時間的算法。
路由表
在計算機網路中，路由表（routing table）或稱路由擇域信息庫（RIB, Routing Information Base），是一個存儲在路由器或者聯網計算機中的電子表格（檔案）或類資料庫。路由表存儲著指向特定網路地址的路徑（在有些情況下，還記錄有路徑的路由度量值）。路由表中含有網路周邊的拓撲信息。路由表建立的主要目標是為了實現路由協定和靜態路由選擇。在現代路由器構造中，路由表不直接參與數據包的傳輸，而是用於生成一個小型指向表，這個指向表僅僅包含由路由算法選擇的數據包傳輸優先路徑，這個表格通常為了最佳化硬體存儲和查找而被壓縮或提前編譯。本文將忽略這個執行的詳細情況而選擇整個路徑選擇/傳輸信息子系統作為路由表來說明。
在路徑選擇的過程中，主機和路由器的決策是由一個叫路由表的路徑資料庫輔助決定的。路由表在路由器內部。根據路由協定，主機也可以擁有用於選擇最佳路徑的路由表。主機路由表是網際網路協定中可選的，像已經過時了的IPX協定。各種路由表：網路路由：一個在網路中有特定網路ID的路由（路徑）主機路由：一個有特定網路地址（網路ID和主機ID）的路由。主機路由允許智慧型化的路由選擇。主機路由通常用於創建用於控制和最佳化特定網路通信的定製路由。默認路由：一個當別的路由在路由表中未被找到的時候使用的路由。如果一個路由器或終端系統（如裝有Microsoft Windows和Linux的個人電腦），找不到到達目的地的路由時就會使用默認路由。
路由算法
路由算法，又名選路算法，可以根據多個特性來加以區分。算法的目的是找到一條從源路由器到目的路由器的“好”路徑（即具有最低費用的路徑）。算法設計者的特定目標影響了該路由協定的操作；具體來說存在著多種路由算法，每種算法對網路和路由器資源的影響都不同；由於路由算法使用多種度量標準（metric），從而影響到最佳路徑的計算。路由算法通常具有下列設計目標的一個或多個：最佳化、簡單、低耗、健壯、穩定、快速聚合、靈活性。（1）最最佳化：指路由算法選擇最佳路徑的能力。根據metric的值和權值來計算。（2）簡潔性：算法設計必須簡潔。路由協定在網路中必須高效地提供其功能，儘量減少軟體和套用的開銷。這在當實現路由算法的軟體必須運行在物理資源有限的計算機上時尤其重要。（3）堅固性：路由算法處於非正常或不可預料的環境時，如硬體故障、負載過高或操作失誤時，都能正確運行。由於路由器分布在網路聯接點上，所以在它們出故障時會產生嚴重後果。最好的路由器算法通常能經受時間的考驗，並在各種網路環境下被證實是可靠的。（4）快速收斂：收斂是在最佳路徑的判斷上所有路由器達到一致的過程。當某個網路事件引起路由可用或不可用時，路由器就發出更新信息。路由更新信息遍及整個網路，引發重新計算最佳路徑，最終達到所有路由器一致公認的最佳路徑。收斂慢的路由算法會造成路徑循環或網路中斷。（5）靈活性：路由算法要求可以快速、準確地適應各種網路環境。例如，某個網段發生故障，路由算法要能很快發現故障，並為使用該網段的所有路由選擇另一條最佳路徑。
