一、路由表

所謂路由表，指的是路由器或者其他互聯網網絡設備上存儲的表，該表中存有到達特定網絡終端的路徑，在某些情況下，還有一些與這些路徑相關的度量。

二、常見路由表生成算法

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

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

（一）靜態路由算法

1.Dijkstra算法（最短路徑算法）

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標號的方式。注意該算法要求圖中不存在負權回路。

Dijkstra算法執行下列步驟：

1）路由器建立一張網絡圖，并且確定源節點和目的節點，在這個例子里我們設為V1和V2。然后路由器建立一個矩陣，稱為“鄰接矩陣”。在這個矩陣中，各矩陣元素表示權值。例如，[i, j]是節點Vi與Vj之間的鏈路權值。如果節點Vi與Vj之間沒有鏈路直接相連，它們的權值設為“無窮大”。

2）路由器為網路中的每一個節點建立一組狀態記錄。此記錄包括三個字段： 前序字段——表示當前節點之前的節點。
長度字段——表示從源節點到當前節點的權值之和。 標號字段——表示節點的狀態。每個節點都處于一個狀態模式：“永久”或“暫時”。

3）路由器初始化（所有節點的）狀態記錄集參數，將它們的長度設為“無窮大”，標號設為“暫時”。

4）路由器設置一個T節點。例如，如果設V1是源T節點，路由器將V1的標號更改為“永久”。當一個標號更改為“永久”后，它將不再改變。一個T節點僅僅是一個代理而已。

5）路由器更新與源T節點直接相連的所有暫時性節點的狀態記錄集。

6）路由器在所有的暫時性節點中選擇距離V1的權值最低的節點。這個節點將是新的T節點。

7）如果這個節點不是V2（目的節點），路由器則返回到步驟5。

8）如果節點是V2，路由器則向前回溯，將它的前序節點從狀態記錄集中提取出來，如此循環，直到提取到V1為止。這個節點列表便是從V1到V2的最佳路由。

2.擴散法

事先不需要任何網絡信息；路由器把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發送。 將來會有多個分組的副本到達目的地端，最先到達的，可能是走了“最優”的路徑 常見的擴散法是選擇性擴散算法。

（二）動態路由算法

1.距離向量路由算法

距離向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算法(Ford-FulkersonAlgorithm)，其被距離向量協議作為一個算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用這個算法的路由器必須掌握這個距離表(它是一個一維排列-“一個向量”)，它告訴在網絡中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網絡中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網絡中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為“成本”)。這個在那個算法中的度量公式是跳躍的次數，等待時間，流出數據包的數量，等等。在距離向量路由算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網絡拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。 其優點是算法簡單容易實現。缺點是慢收斂問題，路由器的路徑變化需要像波浪一樣從相鄰路由器傳播出去，過程緩慢。
每一個相鄰路由器發送過來的路由表都要經過以下步驟：

1）對地址為X的 路由器發過來的路由表，先修改此路由表中的所有項目：把”下一跳”字段中的地址改為X，并把所有”距離”字段都加1。
2）對修改后的路由表中的每一個項目，進行以下步驟：

（1）將X的路由表(修改過的)，與S的路由表的目的網絡進行對比。若在X中出現，在S中沒出現，則將X路由表中的這一條項目添加到S的路由表中。

（2）對于目的網絡在S和X路由表中都有的項目進行下面步驟 ：
（2.1）在S的路由表中，若下一跳地址是x，則直接用X路由表中這條項目替換S路由表中的項目。
（2.2）在S的路由表中，若下一跳地址不是x
，若X路由表項目中的距離d小于S路由表中的距離，則進行更新。
3）若3分鐘還沒有收到相鄰路由器的更新表，則把此相鄰路由器記為不可到達路由器，即把距離設置為16。

2.鏈路狀態最短路由優先算法SPF

1）發現鄰居結點，并學習它們的網絡地址；
2）測量到各鄰居節點的延遲或者開銷；
3）創建鏈路狀態分組；
4）使用擴散法發布鏈路狀態分組；
5）計算到每個其它路由器的最短路徑。
使用Dijkstra算法處理鏈路信息

四、路由收斂原理

路由收斂:指網絡的拓撲結構發生變化后，路由表重新建立到發送再到學習直至穩定，并通告網絡中所有相關路由器都得知該變化的過程。也就是網絡拓撲變化引起的通過重新計算路由而發現替代路由的行為。

通過路由收斂可以使路由域中所有路由器對當前的網絡結構和路由轉發達成一致的狀態。

收斂時間是指從網絡的拓撲結構發生變化到網絡中所有路由設備中路由表重新保持一致的狀態轉換過程。

觸發條件

1、路由器失效

2、連接失效

3、管理度量調整等

總結

以上是生活随笔為你收集整理的常见的路由选择算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。