一、路由表

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

二、常見路由表生成算法

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

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

（一）靜態路由算法

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的最佳路由。