路由器你竟然是這樣的...

我把自己以往的文章匯總成為了 Github ，歡迎各位大佬 star
https://github.com/crisxuan/bestJavaer

前面我們學習了運輸層如何為客戶端和服務器輸送資料的，提供行程端到端的通信，那么下面我們將學習網路層實際上是怎樣實作主機到主機的通信服務的，幾乎每個端系統都有網路層這一部分，所以，網路層必然是很復雜的，下面我將花費大量篇幅來介紹一下計算機網路層的知識，

網路層概述

網路層是 OSI 參考模型的第三層，它位于傳輸層和鏈路層之間，網路層的主要目的是實作兩個端系統之間透明的資料傳輸，

網路層的作用從表面看上去非常簡單，即將分組從一臺主機移動到另外一臺主機，為了實作這個功能，網路層需要兩種功能

• 轉發：因為在互聯網中有很多路由器的存在，而路由器是構成互聯網的根本，路由器最重要的一個功能就是分組轉發，當一個分組到達某路由器的一條輸入鏈路時，該路由器會將分組移動到適當的輸出鏈路，轉發是在資料平面中實作的唯一功能，

在網路中存在兩種平面的選擇

• 資料平面(data plane)：負責轉發網路流量，如路由器交換機中的轉發表（我們后面會說），
• 控制平面(control plane)：控制網路的行為，比如網路路徑的選擇，

• 路由選擇：當分組由發送方流向接收方時，網路層必須選擇這些分組的路徑，計算這些路徑選擇的演算法被稱為 路由選擇演算法(routing algorithm)，

也就是說，轉發是指將分組從一個輸入鏈路轉移到適當輸出鏈路介面的路由器本地動作，而路由選擇是指確定分組從源到目的地所定位的路徑的選擇，我們后面會經常提到轉發和路由選擇這兩個名詞，

那么此處就有一個問題，路由器怎么知道有哪些路徑可以選擇呢？

每臺路由器都有一個關鍵的概念就是 轉發表(forwarding table)，路由器通過檢查資料包標頭中欄位的值，來定位轉發表中的項來實作轉發，標頭中的值即對應著轉發表中的值，這個值指出了分組將被轉發的路由器輸出鏈路，如下圖所示

上圖中有一個 1001 分組到達路由器后，首先會在轉發表中進行索引，然后由路由選擇演算法決定分組要走的路徑，每臺路由器都有兩種功能：轉發和路由選擇，下面我們就來聊一聊路由器的作業原理，

路由器作業原理

下面是一個路由器體系結構圖，路由器主要是由 4 個組件構成的

• 輸入埠：輸入埠(input port)有很多功能，線路終端功能和資料鏈路處理功能，這兩個功能實作了路由器的單個輸入鏈路相關聯的物理層和資料鏈路層，輸入埠查找/轉發功能對路由器的交換功能來說至關重要，由路由器的交換結構來決定輸出埠，具體來講應該是查詢轉發表來確定的，
• 交換結構：交換結構(Switching fabric)就是將路由器的輸入埠連接到它的輸出埠，這種交換結構相當于是路由器內部的網路，
• 輸出埠：輸出埠(Output ports) 通過交換結構轉發分組，并通過物理層和資料鏈路層的功能傳輸分組，因此，輸出埠作為輸入埠執行反向資料鏈接和物理層功能，
• 路由選擇處理器：路由選擇處理器(Routing processor) 在路由器內執行路由協議，維護路由表并執行網路管理功能，

上面只是這幾個組件的簡單介紹，其實這幾個組件的組成并不像描述的那樣簡單，下面我們就來深入聊一聊這幾個組件，

輸入埠

上面介紹了輸入埠有很多功能，包括線路終端、資料處理、查找轉發，其實這些功能在輸入埠的內部有相應的模塊，輸入埠的內部實作如下圖所示

每個輸入埠中都有一個路由處理器維護的路由表的副本，根據路由處理器進行更新，這個路由表的副本能 夠使每個輸入埠進行切換，而無需經過路由處理器統一處理，這是一種分散式的切換，這種方式避免了路 由選擇器統一處理造成轉發瓶頸，

在輸入埠處理能力有限的路由器中，輸入埠不會進行交換功能，而是由路由處理器統一處理，然后根據 路由表查找并將資料包轉發到相應的輸出埠，

一般這種路由器不是單獨的路由器，而是作業站或者服務器充當的路由，這種路由器內部中，路由處理器其實就是 CPU，而輸入埠其實只是網卡，

輸入埠會根據轉發表定位輸出埠，然后再會進行分組轉發，那么現在就有一個問題，是不是每一個分組都有自己的一條鏈路呢？如果分組數量非常大，到達億級的話，也會有億個輸出埠路徑嗎？

我們的潛意識中顯然不是的，來看下面一個例子，

下面是三個輸入埠對應了轉發表中的三個輸出鏈路的示例

可以看到，對于這個例子來說，路由器轉發表中不需要那么多條鏈路，只需要四條就夠，即對應輸出鏈路 0 1 2 3 ，也就是說，能夠使用 4 個轉發表就可以實作億級鏈路，

如何實作呢？

使用這種風格的轉發表，路由器分組的地址 前綴(prefix) 會與該表中的表項進行匹配，

如果存在一個匹配項，那么就會轉發到對應的鏈路上，可能不好理解，我舉個例子來說吧，

比如這時有一個分組是 11000011 10010101 00010000 0001100 到達，因為這個分組與 11000011 10010101 00010000 相匹配，所以路由器會轉發到 0 鏈路介面上，如果一個前綴不匹配上面三個輸出鏈路中的一種，那么路由器將向鏈路介面 3 進行轉發，

路由匹配遵循 最長前綴原則(longest prefix matching rule)，最長匹配原則故名思義就是如果有兩個匹配項一個長一個短的話，就匹配最長的，

一旦通過查找功能確定了分組的輸出埠后，那么該分組就會進入交換結構，在進入交換結構時，如果交換結構正在被使用，就會阻塞新到的分組，等到交換結構調度新的分組，

交換結構

交換結構是路由器的核心功能，通過交換功能把分組從輸入埠轉發至輸出埠，這就是交換結構的主要功能，交換結構有多種形式，主要分為 通過記憶體交換、通過總線交換、通過互聯網路進行交換，下面我們分開來探討一下，

• 經過記憶體交換：最開始的傳統計算機就是使用記憶體交換的，在輸入埠和輸出埠之間是通過 CPU 進行的，輸入埠和輸出埠的功能就好像傳統作業系統中的 I/O 設備一樣，當一個分組到達輸入埠時，這個埠會首先以中斷 的方式向路由選擇器發出信號，將分組從輸入埠拷貝到記憶體中，然后，路由選擇處理器從分組首部中提取目標地址，在轉發表中找出適當的輸出埠進行轉發，同時將分組復制到輸出埠的快取中，

這里需要注意一點，如果記憶體帶寬以每秒讀取或者寫入 B 個資料包，那么總的交換機吞吐量(資料包從輸入埠到輸出埠的總速率) 必須小于 B/2，

• 經過總線交換：在這種處理方式中，總線經由輸入埠直接將分組傳送到輸出埠，中間不需要路由選擇器的干預，總線的作業流程如下：輸入埠給分組分配一個標簽，然后分組經由總線發送給所有的輸出埠，每個輸出埠都會判斷標簽中的埠和自己的是否匹配，如果匹配的話，那么這個輸出埠就會把標簽拆掉，這個標簽只用于交換機內部跨越總線，如果同時有 多個 分組到達路由器的話，那么只有一個分組能夠被處理，其他分組需要再進入交換結構前等待，

• 經過互聯網路交換：客服單一、共享式總線帶寬限制的一種方法是使用一個更復雜的互聯網路，如下圖所示

每條垂直的的總線在交叉點與每條水平的總線交叉，交叉點通過交換結構控制器能夠在任何時候開啟和閉合，當分組到達輸入埠 A 時，如果需要轉發到埠 X，交換機控制器會閉合 A 到 X 交叉部分的交叉點，然后埠 A 在總線上進行分組轉發，這種網路互聯式的交換結構是 非阻塞的(non-blocking)的，也就是說 A -> X 的交叉點閉合不會影響 B -> Y 的鏈路，如果來自兩個不同輸入埠的兩個分組其目的地為相同的輸出埠的話，這種情況下只能有一個分組被交換，另外一個分組必須進行等待，

輸出埠處理

如下圖所示，輸出埠處理取出已經存放在輸出埠記憶體中的分組并將其發送到輸出鏈路上，包括選擇和去除排隊的分組進行傳輸，執行所需的鏈路層和物理層的功能，

在輸入埠中有等待進入交換的排隊佇列，而在輸出埠中有等待轉發的排隊佇列，排隊的位置和程度取決于流量負載、交換結構的相對頻率和線路速率，

隨著佇列的不斷增加，會導致路由器的快取空間被耗盡，進而使沒有記憶體可以存盤溢位的佇列，致使分組出現丟包(packet loss)，這就是我們說的在網路中丟包或者被路由器丟棄，

何時出現排隊

下面我們通過輸入埠的排隊佇列和輸出埠的排隊佇列來介紹一下可能出現的排隊情況，

輸入佇列

如果交換結構的處理速度沒有輸入佇列到達的速度快，在這種情況下，輸入埠將會出現排隊情況，到達交換結構前的分組會加入輸入埠佇列中，以等待通過交換結構傳送到輸出埠，

為了描述清楚輸入佇列，我們假設以下情況：

• 使用網路互聯的交換方式；
• 假定所有鏈路的速度相同；
• 在鏈路中一個分組由輸入埠交換到輸出埠所花的時間相同，從任意一個輸入埠傳送到給定的輸出埠；
• 分組按照 FCFS 的方式，只要輸出埠不同，就可以進行并行傳送，但是如果位于任意兩個輸入埠中的分組是發往同一個目的地的，那么其中的一個分組將被阻塞，而且必須在輸入佇列中俄等待，因為交換結構一次只能傳輸一個到指定埠，

如下圖所示

在 A 佇列中，輸入佇列中的兩個分組會發送至同一個目的地 X，假設在交換結構正要發送 A 中的分組，在這個時候，C 佇列中也有一個分組發送至 X，在這種情況下，C 中發送至 X 的分組將會等待，不僅如此，C 佇列中發送至 Y 輸出埠的分組也會等待，即時 Y 中沒有出現競爭的情況，這種現象叫做 線路前部阻塞(Head-Of-The-Line, HOL) ，

輸出佇列

我們下面討論輸出佇列中出現等待的情況，假設交換速率要比輸入/輸出的傳輸速率快很多，而且有 N 個輸入分組的目的地是轉發至相同的輸出埠，在這種情況下，在向輸出鏈路發送分組的程序中，將會有 N 個新分組到達傳輸埠，因為輸出埠在一個單位時間內只能傳輸一個分組，那么這 N 個分組將會等待，然而在等待 N 個分組被處理的程序中，同時又有 N 個分組到達，所以 ，分組佇列能夠在輸出埠形成，這種情況下最侄訓因為分組數量變的足夠大，從而耗盡 輸出埠的可用記憶體，

如果沒有足夠的記憶體來快取分組的話，就必須考慮其他的方式，主要有兩種：一種是丟失分組，采用 棄尾(drop-tail) 的方法；一種是洗掉一個或多個已經排隊的分組，從而來為新的分組騰出空間，

網路層的策略對 TCP 擁塞控制影響很大的就是路由器的分組丟棄策略，在最簡單的情況下，路由器的佇列通常都是按照 FCFS 的規則處理到來的分組，由于佇列長度總是有限的，因此當佇列已經滿了的時候，以后再到達的所有分組（如果能夠繼續排隊，這些分組都將排在佇列的尾部）將都被丟棄，這就叫做尾部丟棄策略，

通常情況下，在緩沖填滿之前將其丟棄是更好的策略，

如上圖所示，A B C 每個輸入埠都到達了一個分組，而且這個分組都是發往 X 的，同一時間只能處理一個分組，然后這時，又有兩個分組分別由 A B 發往 X，所以此時有 4 個分組在 X 中進行等待，

等上一個分組被轉發完成后，輸出埠就會選擇在剩下的分組中根據 分組調度(packet scheduleer) 選擇一個分組來進行傳輸，我們下面就會聊到分組傳輸，

分組調度

現在我們來討論一下分組調度次序的問題，即排隊的分組如何經輸出鏈路傳輸的問題，我們生活中有無數排隊的例子，但是我們生活中一般的排隊演算法都是 先來先服務(FCFS)，也是先進先出(FIFO)，

先進先出

先進先出就映射為資料結構中的佇列，只不過它現在是鏈路調度規則的排隊模型，

FIFO 調度規則按照分組到達輸出鏈路佇列的相同次序來選擇分組，先到達佇列的分組將先會被轉發，在這種抽象模型中，如果佇列已滿，那么棄尾的分組將是佇列末尾的后面一個，

優先級排隊

優先級排隊是先進先出排隊的改良版本，到達輸出鏈路的分組被分類放入輸出佇列中的優先權類，如下圖所示

通常情況下，每個優先級不同的分組有自己的優先級類，每個優先級類有自己的佇列，分組傳輸會首先從優先級高的佇列中進行，在同一類優先級的分組之間的選擇通常是以 FIFO 的方式完成，

回圈加權公平排隊

在回圈加權公平規則(round robin queuing discipline) 下，分組像使用優先級那樣被分類，然而，在類之間卻不存在嚴格的服務優先權，回圈調度器在這些類之間回圈輪流提供服務，如下圖所示

在回圈加權公平排隊中，類 1 的分組被傳輸，接著是類 2 的分組，最后是類 3 的分組，這算是一個回圈，然后接下來又重新開始，又從 1 -> 2 -> 3 這個順序進行輪詢，每個佇列也是一個先入先出的佇列，

這是一種所謂的保持作業排隊(work-conserving queuing) 的規則，就是說如果輪詢的程序中發現有空佇列，輸出埠不會等待分組，而是繼續輪詢下面的佇列，

另外，我自己肝了六本 PDF，微信搜索「程式員cxuan」關注公眾號后，在后臺回復 cxuan ，領取全部 PDF，這些 PDF 如下

六本 PDF 鏈接