路由

**路由**（**routing**）是任何網路中選取路徑的程式，在此 "程式" 是指一組在電腦中執行的程式。電腦網路由稱為節點的許多機器 (例如電腦) 以及連線至這些節點的路徑或連結所組成。網路中相互連接的兩個節點之間的通訊可以透過許多不同的路徑進行。路由是使用一些預定規則選取最佳路徑的程式。

設定與發展路由的原因是路由建立了網路通訊的效率。網路通訊失敗會導致使用者載入網站頁面需要長時間等待。因為無法處理大量使用者，它也可能會導致網站伺服器失敗。路由可以管理資料流量，來協助將網路故障降至最低，讓網路盡可能使用其容量而不會產生擁塞。

其目的是通過互聯的網路把資訊從源位址以有效率的方式傳輸到目的位址的活動。路由發生在 OSI 網路參考模型中的第三層即網路層。

路由引導分組轉送，經過一些中間的節點後，到它們最後的目的地。作成硬體的話，則稱為路由器。路由通常根據路由表 —— 一個儲存到各個目的地的最佳路徑的表 —— 來引導分組轉送。因此為了有效率的轉送分組，建立儲存在路由器記憶體內的路由表是非常重要的。

路由與橋接的不同，在於路由假設位址相似的節點距離相近。這使得路由表中的一項紀錄可以表示到一群位址的路徑。因此，在大型網路中，路由優於橋接，且路由已經成為網際網路上尋找路徑的最主要方法。

較小的網路通常可以手動設定路由表，但較大且擁有複雜拓撲的網路可能常常變化，若要手動建立路由表是不切實際的。儘管如此，大多數的公共交換電話網路（PSTN）仍然使用預先計算好的路由表，在直接連線的路徑斷線時才使用預備的路徑；見公共交換電話網路由。「動態路由」嘗試按照由路由協定所攜帶的資訊來自動建立路由表以解決這個問題，也讓網路能夠近自主地避免網路斷線或失敗。

動態路由目前主宰了整個網際網路。然而，設定路由協定常須要經驗與技術；目前的網路技術還沒有發展到能夠全自動地設定路由。

分組交換網路（例如網際網路）將資料分割成許多帶有完整目的地位址的分組，每個分組單獨轉送。而電路交換網路（例如公共交換電話網路）同樣使用路由來找到一條路徑，讓接下來的資料能夠抵達正確的目的地。

## 動態路由

若某個設定好的路徑無法使用時，現存的節點必須決定另一個傳送資料到目的地的路徑。他們通常使用以下兩種形式的路由協定來達成：距離向量演算法與連線狀態演算法。所有路由演算法幾乎都可以分類到這兩種演算法中。

### 距離向量演算法

**距離向量演算法**使用 Bellman-Ford 演算法。對於每一條網路上節點間的路徑，演算法指定一個「成本」給它們。節點會選擇一條總成本（經過路徑的所有成本總和）最低的路徑，用來把資料從節點甲送到節點乙。

此演算法非常的簡單。當某節點初次啟動時，將只知道它的鄰居節點（直接連接到該節點的節點）與到該節點的成本。（這些資訊、目的地列表、每個目的地的總成本，以及到某個目的地所必須經過的「下一個節點」，構成路由表，或稱距離表。）每個節點定時地將目前所知，到各個目的地的成本的資訊，送給每個鄰居節點。鄰居節點則檢查這些資訊，並跟目前所知的資訊做比較；如果到某個目的地的成本比目前所知的低，則將收到的資訊加入自己的路由表。經過一段時間後，網路上的所有節點將會了解到所有目的地的最佳「下一個節點」與最低的總成本。

當某個節點斷線時，每個將它當作某條路徑的「下一個節點」的節點會將該路由資訊捨棄，再建立新的路由表資訊。接著，他們將這些資訊告訴所有相鄰的節點，再找出到所有可抵達的目的地之新路徑。

### 連線狀態演算法

在**連線狀態演算法中**，每個節點擁有網路的圖譜（一個圖）。每個節點將自己可以連接到的其他節點資訊傳送到網路上所有的節點，而其他節點接著各自將這個資訊加入到圖譜中。每個路由器即可根據這個圖譜來決定從自己到其它節點的最佳路徑。

完成這個動作的演算法 ——Dijkstra 演算法 —— 建立另一種資料結構 —— 樹。節點產生的樹將自己視為根節點，且最後這棵樹將會包含了網路中所有其他的節點。一開始，此樹只有根節點（節點自己）。接著在樹中已有的節點的鄰居節點且不存在樹中的節點集合中，選取一個成本最低的節點加入此樹，直到所有節點都存入樹中為止。

這棵樹即用來建立路由表、提供最佳的「下一個節點」等，讓節點能跟網路中其它節點通訊。

### 路由演算法的比較

在小型網路中，距離向量路由協定十分簡單且有效率，且只需要一些管理。然而，它們的規模性不好，且
收斂性質也十分差，因此促進了較複雜但規模性較好的連線狀態路由協定的開發，以使用在較大型的網路。距離向量路由協定也有無限計數問題。

連線狀態路由協定的主要優點是在限制的時間內，對於連線改變（例如斷線）的反應較快。而且連線狀態路由協定在網路上所傳送的封包也比距離向量路由協定的封包小。距離向量路由協定必須傳送一個節點的整個路由表，但連線狀態路由協定的封包只需要傳輸該節點的鄰居節點資訊即可。因此，這些封包小到不會佔用可觀的網路資源。連線狀態路由協定的主要缺點則是比距離向量路由協定需要較多的儲存空間與較強的計算能力。

## 路由協定與可被繞送協定

有時路由協定與可被繞送協定常會令人混淆：

* **可被繞送協定**：任何一個提供足夠的網路層位址資訊讓封包可被從一個裝置轉送到另一個，而不需要知道來源到目的地的整條路徑的網路通訊協定。「可被繞送協定」定義了封包的格式與封包欄位的使用方式。封包通常從一個終端系統被遞送到另一個。IP 是一個可被繞送協定，而乙太網路是一個不可被繞送協定的例子。
* **路由協定**：在網路間交換**路由資訊**，讓路由器可動態建立路由表的通訊協定。傳統的 IP 路由十分簡單，因為它使用**下一個節點路由方法**，也就是路由器只需要考慮將封包送到哪一個「下一個節點」，而不需考慮到目的地的整條路徑。

雖然動態路由可能非常複雜，但它使得網際網路十分有彈性，且讓網際網路的規模自從採用 IP 以後成長了超過八個數量級。

**路由度量**（routing metric）包含了被路由演算法使用來決定哪一條路徑較另一條路徑好的所有數值。度量可能包括許多資訊，例如頻寬、延遲、經過節點數、路徑成本、負載、MTU、可靠性及傳輸成本等。路由表只儲存最佳的可能路徑，但連線狀態或拓撲資料庫可能儲存其他相關的資訊。

當路由器從不同的路由協定裡發現有多個能抵達相同目的地的不同路徑時，它們使用稱為**管理距離**（administrative distance）的特性來選擇最佳的路徑。管理距離定義了路由協定的可靠程度。每個路由協定按照管理距離值，由最可靠到最不可靠排列來區分優先順序。

依照路由器與其他自治系統的關係，有許多種類的路由協定：

* **Ad hoc 網路路由協定**出現在沒有或一點點基礎的網路。參見 Ad hoc 路由協定列表以獲得提議中的協定。
* **內部閘道協定**（**IGP**s）在單一的自治系統中交換路由資訊。常見的範例包括：
  * IGRP（Interior Gateway Routing Protocol）
  * EIGRP（Enhanced Interior Gateway Routing Protocol）
  * OSPF（Open Shortest Path First）
  * RIP（Routing Information Protocol）
  * IS-IS（Intermediate System to Intermediate System）
* **外部閘道協定**（**EGP**s）在不同的自治系統中交換路由資訊。EGP 包括：
  * EGP（原本用來連接網際網路骨幹的外部閘道協定，現在已不再使用）
  * BGP（Border Gateway Protocol：大約從 1995 年開始使用目前的版本，BGPv4）

## 註釋

## 參見

* 路由演算法
  * 階層式路由
  * 最短來迴路徑分離演算法
* 偏向路由
* 策略路由
* 蟲洞路由
* 適應性路由
* 特別的設計
  * CIDR
  * MPLS 路由
  * ATM 路由
  * 公共交換電話網路由
* 與封包轉送有關，但與路徑選擇無關的條目
  * 網路位址轉換（NAT）
  * IP 位址欺騙（安全問題）
* 數種尺度路由的數學複雜性
  * 路由 QoS
* 延展網路 路由模式
  * 基於關鍵值的轉送方法 (KBR)
  * 分散式物件定址及路由 (DOLR)
  * 群組任播及多播 (CAST)
  * 分散式雜湊表 (DHT)
* RPSL
* HSLS
* OSPF（一個連線狀態路由協定）
* 模糊邏輯路由
* 地理式路由

## 參考資料

* Kurose, James E. and Ross, Keith W. Computer Networking. Benjamin/Cummings. 2004. ISBN 978-0-321-22735-5.
* Doyle, Jeff. Routing TCP/IP, Volume I, Second Ed.. Cisco Press. 2005. ISBN 978-1-58705-202-6. Ciscopress ISBN 978-1-58705-202-6 （頁面存檔備份，存於網際網路檔案館）

## 外部連結

* （英文） Routing and Routed Protocols
* （英文） 路由 （頁面存檔備份，存於網際網路檔案館） 路由作業圖
* （英文） Router Troubleshooting Primer （頁面存檔備份，存於網際網路檔案館） 路由問題的除錯步驟
* （英文） Count-To-Infinity Problem （頁面存檔備份，存於網際網路檔案館）
* （英文） "Stability Features" （頁面存檔備份，存於網際網路檔案館） 一種避免 Count-To-Infinity 問題的方法