路由演算法 路由演算法可以根據多個特性來加以區分。首先，演算法設計者的特定目標影響了該路由協議的操作；其次，存在著多種路由演算法，每種演算法對網路和路由器資源的影響都不同；最後，路由演算法使用多種metric，影響到最佳路徑的計算。
由演算法－路由演算法的特性 1、設計目標
路由演算法通常具有下列設計目標的一個或多個：
最佳化
簡單、低耗
健壯、穩定
快速聚合
靈活性
最佳化指路由演算法選擇最佳路徑的能力，根據metric的值和權值來計算。例如有一種路由演算法可能使用跳數和延遲，但可能延遲的權值要大些。當然，路由協議必須嚴格定義計算metric的演算法。
路由演算法也可以設計得儘量簡單。換句話說，路由協議必須高效地提供其功能，儘量減少軟體和應用的開銷。當實現路由演算法的軟體必須執行在物理資源有限的計算機上時高效尤其重要。
路由演算法必須健壯，即在出現不正常或不可預見事件的情況下必須仍能正常處理，例如硬體故障、高負載和不正確的實現。因為路由器位於網路的連線點，當它們失效時會產生重大的問題。最好的路由演算法通常是那些經過了時間考驗，證實在各種網路條件下都很穩定的演算法。
此外，路由演算法必須能快速聚合，聚合是所有路由器對最佳路徑達成一致的過程。當某網路事件使路徑斷掉或不可用時，路由器透過網路分發路由更新資訊，促使最佳路徑的重新計算，最終使所有路由器達成一致。聚合很慢的路由演算法可能會產生路由環或網路中斷。
在下圖中的路由環中，某分組在時間t1到達路由器1，路由器1已經更新並知道到達目的的最佳路徑是以路由器2為下一跳，於是就把該分組轉發給路由器2。但是路由器2還沒有更新，它認為最佳的下一跳是路由器1，於是把該分組發回給路由器1，結果分組在兩個路由器間來回傳遞直到路由器2收到路由更新資訊或分組超過了生存期。
路由演算法還應該是靈活的，即它們應該迅速、準確地適應各種網路環境。例如，假定某網段斷掉了，當知道問題後，很多路由演算法對通常使用該網段的路徑將迅速選擇次佳的路徑。路由演算法可以設計得可適應網路頻寬、路由器佇列大小和網路延遲。
路由演算法的核心是路由選擇演算法，設計路由演算法時要考慮的技術要素有：
（1）選擇最短路由還是最佳路由；
（2）通訊子網是採用虛電路操作方式還是採用資料報的操作方式；
（3）採用分散式路由演算法還是採用集中式路由演算法；
（5）確定採用靜太路由還是動態路由。
2、演算法型別
各路由演算法的區別點包括：
靜態與動態
單路徑與多路徑
平坦與分層
主機智慧與路由器智慧
域內與域間
連結狀態與距離向量
(1)靜態與動態
靜態路由演算法很難算得上是演算法，只不過是開始路由前由網管建立的表對映。這些對映自身並不改變，除非網管去改動。使用靜態路由的演算法較容易設計，在網路通訊可預測及簡單的網路中工作得很好。
由於靜態路由系統不能對網路改變做出反映，通常被認為不適用於現在的大型、易變的網路。九十年代主要的路由演算法都是動態路由演算法，透過分析收到的路由更新資訊來適應網路環境的改變。如果資訊表示網路發生了變化，路由軟體就重新計算路由併發出新的路由更新資訊。這些資訊滲入網路，促使路由器重新計算並對路由表做相應的改變。
動態路由演算法可以在適當的地方以靜態路由作為補充。例如，最後可選路由（router of last resort），作為所有不可路由分組的去路，保證了所有的資料至少有方法處理。
(2)單路徑與多路徑
一些複雜的路由協議支援到同一目的的多條路徑。與單路徑演算法不同，這些多路徑演算法允許資料在多條線路上覆用。多路徑演算法的優點很明顯：它們可以提供更好的吞吐量和可靠性。
(3)平坦與分層
一些路由協議在平坦的空間裡運作，其它的則有路由的層次。在平坦的路由系統中，每個路由器與其它所有路由器是對等的；在分層次的路由系統中，一些路由器構成了路由主幹，資料從非主幹路由器流向主幹路由器，然後在主幹上傳輸直到它們到達目標所在區域，在這裡，它們從最後的主幹路由器透過一個或多個非主幹路由器到達終點。
路由系統通常設計有邏輯節點組，稱為域、自治系統或區間。在分層的系統中，一些路由器可以與其它域中的路由器通訊，其它的則只能與域內的路由器通訊。在很大的網路中，可能還存在其它級別，最高階的路由器構成了路由主幹。
分層路由的主要優點是它模擬了多數公司的結構，從而能很好地支援其通訊。多數的網路通訊發生在小組中（域）。因為域內路由器只需要知道本域內的其它路由器，它們的路由演算法可以簡化，根據所使用的路由演算法，路由更新的通訊量可以相應地減少。
(4)主機智慧與路由器智慧
一些路由演算法假定源結點來決定整個路徑，這通常稱為源路由。在源路由系統中，路由器只作為存貯轉發裝置，無意識地把分組發向下一跳。其它路由演算法假定主機對路徑一無所知，在這些演算法中，路由器基於自己的計算決定透過網路的路徑。前一種系統中，主機具有決定路由的智慧，後者則為路由器具有此能力。
主機智慧和路由器智慧的折衷實際是最佳路由與額外開銷的平衡。主機智慧系統通常能選擇更佳的路徑，因為它們在傳送資料前探索了所有可能的路徑，然後基於特定系統對“最佳化”的定義來選擇最佳路徑。然而確定所有路徑的行為通常需要很多的探索通訊量和很長的時間。
(5)域內與域間
一些路由演算法只在域內工作，其它的則既在域內也在域間工作。這兩種演算法的本質是不同的。其遵循的理由是最佳化的域內路由演算法沒有必要也成為最佳化的域間路由演算法。
(6)連結狀態與距離向量
連結狀態演算法（也叫做短路徑優先演算法）把路由資訊散佈到網路的每個節點，不過每個路由器只發送路由表中描述其自己連結狀態的部分。距離向量演算法（也叫做Bellman-Ford演算法）中每個路由器傳送路由表的全部或部分，但只發給其鄰居。也就是說，連結狀態演算法到處傳送較少的更新資訊，而距離向量演算法只向相鄰的路由器傳送較多的更新資訊。
由於連結狀態演算法聚合得較快，它們相對於距離演算法產生路由環的傾向較小。在另一方面，連結狀態演算法需要更多的CPU和記憶體資源，因此連結狀態演算法的實現和支援較昂貴。雖然有差異，這兩種演算法型別在多數環境中都可以工作得很好。
3、路由的metric
路由表中含有由交換軟體用以選擇最佳路徑的資訊。但是路由表是怎樣建立的呢？它們包含資訊的本質是什麼？路由演算法怎樣根據這些資訊決定哪條路徑更好呢？
路由演算法使用了許多不同的metric以確定最佳路徑。複雜的路由演算法可以基於多個metric選擇路由，並把它們結合成一個複合的metric。常用的metric如下：
路徑長度
可靠性
延遲
頻寬
負載
通訊代價
路徑長度是最常用的路由metric。一些路由協議允許網管給每個網路連結人工賦以代價值，這種情況下，路由長度是所經過各個連結的代價總和。其它路由協議定義了跳數，即分組在從源到目的的路途中必須經過的網路產品，如路由器的個數。
可靠性，在路由演算法中指網路連結的可依賴性（通常以位誤率描述），有些網路連結可能比其它的失效更多，網路失效後，一些網路連結可能比其它的更易或更快修復。任何可靠性因素都可以在給可靠率賦值時計算在內，通常是由網管給網路連結賦以metric值。
路由延遲指分組從源透過網路到達目的所花時間。很多因素影響到延遲，包括中間的網路連結的頻寬、經過的每個路由器的埠佇列、所有中間網路連結的擁塞程度以及物理距離。因為延遲是多個重要變數的混合體，它是個比較常用且有效的metric。
頻寬指連結可用的流通容量。在其它所有條件都相等時，10Mbps的乙太網連結比64kbps的專線更可取。雖然頻寬是連結可獲得的最大吞吐量，但是透過具有較大頻寬的連結做路由不一定比經過較慢連結路由更好。例如，如果一條快速鏈路很忙，分組到達目的所花時間可能要更長。
負載指網路資源，如路由器的繁忙程度。負載可以用很多方面計算，包括CPU使用情況和每秒處理分組數。持續地監視這些引數本身也是很耗費資源的。
通訊代價是另一種重要的metric，尤其是有一些公司可能關係運作費用甚於效能。即使線路延遲可能較長，他們也寧願透過自己的線路傳送資料而不採用昂貴的公用線路 [編輯本段]路由演算法－LS演算法 採用LS演算法時，每個路由器必須遵循以下步驟：
1、確認在物理上與之相連的路由器並獲得它們的IP地址。當一個路由器開始工作後，它首先向整個網路傳送一個“HELLO”分組資料包。每個接收到資料包的路由器都將返回一條訊息，其中包含它自身的IP地址。
2、測量相鄰路由器的延時（或者其他重要的網路引數，比如平均流量）。為做到這一點，路由器向整個網路傳送響應分組資料包。每個接收到資料包的路由器返回一個應答分組資料包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，透過一個分組資料包從遠端主機返回的時間來測量。）請注意，該時間包括了傳輸和處理兩部分的時間——也就是將分組資料包傳送到目的地的時間以及接收方處理分組資料包和應答的時間。
3、向網路中的其他路由器廣播自己的資訊，同時也接收其他路由器的資訊。在這一步中，所有的路由器共享它們的知識並且將自身的資訊廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網路的結構以及狀態。
4、使用一個合適的演算法，確定網路中兩個節點之間的最佳路由。在這一步中，路由器選擇通往每一個節點的最佳路由。它們使用一個演算法來實現這一點，如Dijkstra最短路徑演算法。在這個演算法中，一個路由器透過收集到的其他路由器的資訊，建立一個網路圖。這個圖描述網路中的路由器的位置以及它們之間的連結關係。每個連結都有一個數字標註，稱為權值或成本。這個數字是延時和平均流量的函式，有時它僅僅表示節點間的躍點數。例如，如果一個節點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。
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的最佳路由。
路由演算法 路由演算法可以根據多個特性來加以區分。首先，演算法設計者的特定目標影響了該路由協議的操作；其次，存在著多種路由演算法，每種演算法對網路和路由器資源的影響都不同；最後，路由演算法使用多種metric，影響到最佳路徑的計算。
由演算法－路由演算法的特性 1、設計目標
路由演算法通常具有下列設計目標的一個或多個：
最佳化
簡單、低耗
健壯、穩定
快速聚合
靈活性
最佳化指路由演算法選擇最佳路徑的能力，根據metric的值和權值來計算。例如有一種路由演算法可能使用跳數和延遲，但可能延遲的權值要大些。當然，路由協議必須嚴格定義計算metric的演算法。
路由演算法也可以設計得儘量簡單。換句話說，路由協議必須高效地提供其功能，儘量減少軟體和應用的開銷。當實現路由演算法的軟體必須執行在物理資源有限的計算機上時高效尤其重要。
路由演算法必須健壯，即在出現不正常或不可預見事件的情況下必須仍能正常處理，例如硬體故障、高負載和不正確的實現。因為路由器位於網路的連線點，當它們失效時會產生重大的問題。最好的路由演算法通常是那些經過了時間考驗，證實在各種網路條件下都很穩定的演算法。
此外，路由演算法必須能快速聚合，聚合是所有路由器對最佳路徑達成一致的過程。當某網路事件使路徑斷掉或不可用時，路由器透過網路分發路由更新資訊，促使最佳路徑的重新計算，最終使所有路由器達成一致。聚合很慢的路由演算法可能會產生路由環或網路中斷。
在下圖中的路由環中，某分組在時間t1到達路由器1，路由器1已經更新並知道到達目的的最佳路徑是以路由器2為下一跳，於是就把該分組轉發給路由器2。但是路由器2還沒有更新，它認為最佳的下一跳是路由器1，於是把該分組發回給路由器1，結果分組在兩個路由器間來回傳遞直到路由器2收到路由更新資訊或分組超過了生存期。
路由演算法還應該是靈活的，即它們應該迅速、準確地適應各種網路環境。例如，假定某網段斷掉了，當知道問題後，很多路由演算法對通常使用該網段的路徑將迅速選擇次佳的路徑。路由演算法可以設計得可適應網路頻寬、路由器佇列大小和網路延遲。
路由演算法的核心是路由選擇演算法，設計路由演算法時要考慮的技術要素有：
（1）選擇最短路由還是最佳路由；
（2）通訊子網是採用虛電路操作方式還是採用資料報的操作方式；
（3）採用分散式路由演算法還是採用集中式路由演算法；
（5）確定採用靜太路由還是動態路由。
2、演算法型別
各路由演算法的區別點包括：
靜態與動態
單路徑與多路徑
平坦與分層
主機智慧與路由器智慧
域內與域間
連結狀態與距離向量
(1)靜態與動態
靜態路由演算法很難算得上是演算法，只不過是開始路由前由網管建立的表對映。這些對映自身並不改變，除非網管去改動。使用靜態路由的演算法較容易設計，在網路通訊可預測及簡單的網路中工作得很好。
由於靜態路由系統不能對網路改變做出反映，通常被認為不適用於現在的大型、易變的網路。九十年代主要的路由演算法都是動態路由演算法，透過分析收到的路由更新資訊來適應網路環境的改變。如果資訊表示網路發生了變化，路由軟體就重新計算路由併發出新的路由更新資訊。這些資訊滲入網路，促使路由器重新計算並對路由表做相應的改變。
動態路由演算法可以在適當的地方以靜態路由作為補充。例如，最後可選路由（router of last resort），作為所有不可路由分組的去路，保證了所有的資料至少有方法處理。
(2)單路徑與多路徑
一些複雜的路由協議支援到同一目的的多條路徑。與單路徑演算法不同，這些多路徑演算法允許資料在多條線路上覆用。多路徑演算法的優點很明顯：它們可以提供更好的吞吐量和可靠性。
(3)平坦與分層
一些路由協議在平坦的空間裡運作，其它的則有路由的層次。在平坦的路由系統中，每個路由器與其它所有路由器是對等的；在分層次的路由系統中，一些路由器構成了路由主幹，資料從非主幹路由器流向主幹路由器，然後在主幹上傳輸直到它們到達目標所在區域，在這裡，它們從最後的主幹路由器透過一個或多個非主幹路由器到達終點。
路由系統通常設計有邏輯節點組，稱為域、自治系統或區間。在分層的系統中，一些路由器可以與其它域中的路由器通訊，其它的則只能與域內的路由器通訊。在很大的網路中，可能還存在其它級別，最高階的路由器構成了路由主幹。
分層路由的主要優點是它模擬了多數公司的結構，從而能很好地支援其通訊。多數的網路通訊發生在小組中（域）。因為域內路由器只需要知道本域內的其它路由器，它們的路由演算法可以簡化，根據所使用的路由演算法，路由更新的通訊量可以相應地減少。
(4)主機智慧與路由器智慧
一些路由演算法假定源結點來決定整個路徑，這通常稱為源路由。在源路由系統中，路由器只作為存貯轉發裝置，無意識地把分組發向下一跳。其它路由演算法假定主機對路徑一無所知，在這些演算法中，路由器基於自己的計算決定透過網路的路徑。前一種系統中，主機具有決定路由的智慧，後者則為路由器具有此能力。
主機智慧和路由器智慧的折衷實際是最佳路由與額外開銷的平衡。主機智慧系統通常能選擇更佳的路徑，因為它們在傳送資料前探索了所有可能的路徑，然後基於特定系統對“最佳化”的定義來選擇最佳路徑。然而確定所有路徑的行為通常需要很多的探索通訊量和很長的時間。
(5)域內與域間
一些路由演算法只在域內工作，其它的則既在域內也在域間工作。這兩種演算法的本質是不同的。其遵循的理由是最佳化的域內路由演算法沒有必要也成為最佳化的域間路由演算法。
(6)連結狀態與距離向量
連結狀態演算法（也叫做短路徑優先演算法）把路由資訊散佈到網路的每個節點，不過每個路由器只發送路由表中描述其自己連結狀態的部分。距離向量演算法（也叫做Bellman-Ford演算法）中每個路由器傳送路由表的全部或部分，但只發給其鄰居。也就是說，連結狀態演算法到處傳送較少的更新資訊，而距離向量演算法只向相鄰的路由器傳送較多的更新資訊。
由於連結狀態演算法聚合得較快，它們相對於距離演算法產生路由環的傾向較小。在另一方面，連結狀態演算法需要更多的CPU和記憶體資源，因此連結狀態演算法的實現和支援較昂貴。雖然有差異，這兩種演算法型別在多數環境中都可以工作得很好。
3、路由的metric
路由表中含有由交換軟體用以選擇最佳路徑的資訊。但是路由表是怎樣建立的呢？它們包含資訊的本質是什麼？路由演算法怎樣根據這些資訊決定哪條路徑更好呢？
路由演算法使用了許多不同的metric以確定最佳路徑。複雜的路由演算法可以基於多個metric選擇路由，並把它們結合成一個複合的metric。常用的metric如下：
路徑長度
可靠性
延遲
頻寬
負載
通訊代價
路徑長度是最常用的路由metric。一些路由協議允許網管給每個網路連結人工賦以代價值，這種情況下，路由長度是所經過各個連結的代價總和。其它路由協議定義了跳數，即分組在從源到目的的路途中必須經過的網路產品，如路由器的個數。
可靠性，在路由演算法中指網路連結的可依賴性（通常以位誤率描述），有些網路連結可能比其它的失效更多，網路失效後，一些網路連結可能比其它的更易或更快修復。任何可靠性因素都可以在給可靠率賦值時計算在內，通常是由網管給網路連結賦以metric值。
路由延遲指分組從源透過網路到達目的所花時間。很多因素影響到延遲，包括中間的網路連結的頻寬、經過的每個路由器的埠佇列、所有中間網路連結的擁塞程度以及物理距離。因為延遲是多個重要變數的混合體，它是個比較常用且有效的metric。
頻寬指連結可用的流通容量。在其它所有條件都相等時，10Mbps的乙太網連結比64kbps的專線更可取。雖然頻寬是連結可獲得的最大吞吐量，但是透過具有較大頻寬的連結做路由不一定比經過較慢連結路由更好。例如，如果一條快速鏈路很忙，分組到達目的所花時間可能要更長。
負載指網路資源，如路由器的繁忙程度。負載可以用很多方面計算，包括CPU使用情況和每秒處理分組數。持續地監視這些引數本身也是很耗費資源的。
通訊代價是另一種重要的metric，尤其是有一些公司可能關係運作費用甚於效能。即使線路延遲可能較長，他們也寧願透過自己的線路傳送資料而不採用昂貴的公用線路 [編輯本段]路由演算法－LS演算法 採用LS演算法時，每個路由器必須遵循以下步驟：
1、確認在物理上與之相連的路由器並獲得它們的IP地址。當一個路由器開始工作後，它首先向整個網路傳送一個“HELLO”分組資料包。每個接收到資料包的路由器都將返回一條訊息，其中包含它自身的IP地址。
2、測量相鄰路由器的延時（或者其他重要的網路引數，比如平均流量）。為做到這一點，路由器向整個網路傳送響應分組資料包。每個接收到資料包的路由器返回一個應答分組資料包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，透過一個分組資料包從遠端主機返回的時間來測量。）請注意，該時間包括了傳輸和處理兩部分的時間——也就是將分組資料包傳送到目的地的時間以及接收方處理分組資料包和應答的時間。
3、向網路中的其他路由器廣播自己的資訊，同時也接收其他路由器的資訊。在這一步中，所有的路由器共享它們的知識並且將自身的資訊廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網路的結構以及狀態。
4、使用一個合適的演算法，確定網路中兩個節點之間的最佳路由。在這一步中，路由器選擇通往每一個節點的最佳路由。它們使用一個演算法來實現這一點，如Dijkstra最短路徑演算法。在這個演算法中，一個路由器透過收集到的其他路由器的資訊，建立一個網路圖。這個圖描述網路中的路由器的位置以及它們之間的連結關係。每個連結都有一個數字標註，稱為權值或成本。這個數字是延時和平均流量的函式，有時它僅僅表示節點間的躍點數。例如，如果一個節點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。
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的最佳路由。