路線選擇

選擇路線是指選擇合適的路由選擇算法為分組通過通信子網選擇最適當的路徑（路線）。在網絡層，選擇路線最主要的目的使分組傳輸的代價最小，例如傳輸時間，分組丟失率等。常見選擇路線算法有距離矢量路由算法，鏈路狀態路由算法。

分組（packet）是在分組交換網絡中傳輸的的格式化數據數據單位。一個分組（packet）分成兩個部分，包括控制信息，也就是數據表頭，和數據本身，也就是酬載（payload），兩大部分構成。不同的網絡中，分組可能有很多形式，比如以位為單位的分組（用某個位表示控制信息），再如以太網中含有首部的多字節分組。我們可以將一個分組比作一封信，首部相當於信封，而分組的數據部分則相當於信的內容。當然，有時候一個大分組可以分成多個小分組，這個和信不同。

鏈路狀態算法的思想是要求網絡中所有參與鏈路狀態路由協議的路由器都掌握網絡的全部拓撲結構信息，並記錄在路由數據庫中。鏈路狀態算法中路由數據庫實質上是一個網絡結構的拓撲圖，該拓撲圖由一個節點的集合和一個邊的集合構成。在網絡拓撲圖，結點代表網絡中路由器，邊代表路由器之間的物理鏈路。在網絡拓撲結構圖，每一條鏈路上可以附加不同的屬性，例如鏈路的狀態、距離或費用等。如果沒一個路由器所保存的網絡拓撲結構圖都是一致的，那麼個路由器生成的路由表也是最佳的，不存在錯誤路由或循環路由。鏈路狀態選路算法的工作原理如下

（1）在參與鏈路狀態選路的路由器集合中，每個路由器都需要通過某種機制來了解自己所連接的鏈路及其狀態。

（2）各路由器都能夠將其所連接的鏈路的狀態信息通知給網絡中的所有其他路由器，這些鏈路信息包括鏈路狀態、費用以及鏈路兩端的路由器等。

（3）鏈路狀態信息的通過鏈路狀態分組（LSP）來向整個網絡發佈。一個LSP通常包含源路由器的標識符、相鄰路由器的標識符，以及而知之間鏈路的費用。每一個LSP都將被網絡中的所有的路由器接收，並用於建立網絡整體的統一拓撲數據庫。由於網絡中所有的路由器都發送LSP，經過一段時間以後，每一個路由器都保持了一張完整的網絡拓撲圖，再在這個拓撲圖上，利用最短通路算法（例如Dijkstra算法等），路由器就可以計算出從任何源點到任何目的地的最佳通路。

這樣，每一個路由器都能夠利用通路最短的原則建立一個以本路由器為根、分支到所有其他路由器的生成樹，依據這個生成樹就可以很容易地計算出本路由器的路由表 ^[1]  。

距離矢量路由算法是動態路由算法。它是這樣工作的：每個路由器維護一張矢量表，表中列出了當前已知的到 每個目標的最佳距離，以及所使用的線路。通過在鄰居之間相互交換信息，路由器不斷地更新它們內部的表。

距離矢量路由算法最常見的是Ford－Fulkerson算法。該算法的核心思想是使用標號的方法不斷尋找一個圖上的 可增廣路徑並且進行調整，直到找不到可增廣路徑為止。距離矢量路由算法號召每個路由器在每次更新時發送它 的整個路由表，但僅僅給它的鄰居。距離矢量路由算法傾向於路由循環，但比鏈路狀態路由算法計算更簡單。

算法描述如下：

給定帶杈有向圖G和源點s，求從s到G中任意頂點v的最短路徑，該算法通過在一個路由中重申跳數的個數九來尋 找一個最短路徑生成樹。

在距離矢量路由選擇算法中，每個路由器維持有一張子網中每一個以其他路由器為索引的路由選擇表，表中的 每一個項目都對應於子網中的每個路由器。此表項包括兩個部分，即希望使用的到目的地的輸出線路和估計到達 目的地所需時間或距離。用度量標準可為站點，估計的時間延遲（ms），該路出排隊的分組估計總數或類似的值。

假定路由器知道它到每個相鄰路由器的“距離”。如果度量標準為站點，其距離就為一個站點；如果度量標準是隊列長度，則路由器會簡單地檢查每個隊列；如果度量標準是延遲，路由器可以直接發送一個特別“響應”（ECHO）分組來測出延遲，接收者只對它加上時間標記後就儘快送回。

網絡擁塞（network congestion）是指在分組交換網絡中傳送分組的數目太多時，由於存儲轉發節點的資源有限而造成網絡傳輸性能下降的情況。

網絡擁塞是一種持續過載的網絡狀態，此時用户對網絡資源（包括鏈路帶寬、存儲空間和處理器處理能力等）的需求超過了固有的處理能力和容量。在Internet的體系結構中，擁塞的發生是其固有的屬性。