[[357649]]

前面我們學習了運輸層如何為客戶端和服務器輸送數(shù)據(jù)的，提供進程端到端的通信。那么下面我們將學習網(wǎng)絡層實際上是怎樣實現(xiàn)主機到主機的通信服務的。幾乎每個端系統(tǒng)都有網(wǎng)絡層這一部分。所以，網(wǎng)絡層必然是很復雜的。下面我將花費大量篇幅來介紹一下計算機網(wǎng)絡層的知識。

網(wǎng)絡層概述

網(wǎng)絡層是 OSI 參考模型的第三層，它位于傳輸層和鏈路層之間，網(wǎng)絡層的主要目的是實現(xiàn)兩個端系統(tǒng)之間透明的數(shù)據(jù)傳輸。

網(wǎng)絡層的作用從表面看上去非常簡單，即將分組從一臺主機移動到另外一臺主機。為了實現(xiàn)這個功能，網(wǎng)絡層需要兩種功能

• 轉(zhuǎn)發(fā)：因為在互聯(lián)網(wǎng)中有很多路由器的存在，而路由器是構(gòu)成互聯(lián)網(wǎng)的根本，路由器最重要的一個功能就是分組轉(zhuǎn)發(fā)，當一個分組到達某路由器的一條輸入鏈路時，該路由器會將分組移動到適當?shù)妮敵鲦溌?。轉(zhuǎn)發(fā)是在數(shù)據(jù)平面中實現(xiàn)的唯一功能。
• 在網(wǎng)絡中存在兩種平面的選擇
• 數(shù)據(jù)平面(data plane)：負責轉(zhuǎn)發(fā)網(wǎng)絡流量，如路由器交換機中的轉(zhuǎn)發(fā)表(我們后面會說)。
• 控制平面(control plane)：控制網(wǎng)絡的行為，比如網(wǎng)絡路徑的選擇。
• 路由選擇：當分組由發(fā)送方流向接收方時，網(wǎng)絡層必須選擇這些分組的路徑。計算這些路徑選擇的算法被稱為 路由選擇算法(routing algorithm)。

也就是說，轉(zhuǎn)發(fā)是指將分組從一個輸入鏈路轉(zhuǎn)移到適當輸出鏈路接口的路由器本地動作。而路由選擇是指確定分組從源到目的地所定位的路徑的選擇。我們后面會經(jīng)常提到轉(zhuǎn)發(fā)和路由選擇這兩個名詞。

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

每臺路由器都有一個關鍵的概念就是 轉(zhuǎn)發(fā)表(forwarding table)。路由器通過檢查數(shù)據(jù)包標頭中字段的值，來定位轉(zhuǎn)發(fā)表中的項來實現(xiàn)轉(zhuǎn)發(fā)。標頭中的值即對應著轉(zhuǎn)發(fā)表中的值，這個值指出了分組將被轉(zhuǎn)發(fā)的路由器輸出鏈路。如下圖所示

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

路由器工作原理

下面是一個路由器體系結(jié)構(gòu)圖，路由器主要是由 4 個組件構(gòu)成的

• 輸入端口：輸入端口(input port)有很多功能。線路終端功能和數(shù)據(jù)鏈路處理功能，這兩個功能實現(xiàn)了路由器的單個輸入鏈路相關聯(lián)的物理層和數(shù)據(jù)鏈路層。輸入端口查找/轉(zhuǎn)發(fā)功能對路由器的交換功能來說至關重要，由路由器的交換結(jié)構(gòu)來決定輸出端口，具體來講應該是查詢轉(zhuǎn)發(fā)表來確定的。
• 交換結(jié)構(gòu)：交換結(jié)構(gòu)(Switching fabric)就是將路由器的輸入端口連接到它的輸出端口。這種交換結(jié)構(gòu)相當于是路由器內(nèi)部的網(wǎng)絡。
• 輸出端口：輸出端口(Output ports) 通過交換結(jié)構(gòu)轉(zhuǎn)發(fā)分組，并通過物理層和數(shù)據(jù)鏈路層的功能傳輸分組，因此，輸出端口作為輸入端口執(zhí)行反向數(shù)據(jù)鏈接和物理層功能。
• 路由選擇處理器：路由選擇處理器(Routing processor) 在路由器內(nèi)執(zhí)行路由協(xié)議，維護路由表并執(zhí)行網(wǎng)絡管理功能。

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

輸入端口

上面介紹了輸入端口有很多功能，包括線路終端、數(shù)據(jù)處理、查找轉(zhuǎn)發(fā)，其實這些功能在輸入端口的內(nèi)部有相應的模塊，輸入端口的內(nèi)部實現(xiàn)如下圖所示

每個輸入端口中都有一個路由處理器維護的路由表的副本，根據(jù)路由處理器進行更新。這個路由表的副本能 夠使每個輸入端口進行切換，而無需經(jīng)過路由處理器統(tǒng)一處理。這是一種分散式的切換，這種方式避免了路 由選擇器統(tǒng)一處理造成轉(zhuǎn)發(fā)瓶頸。

在輸入端口處理能力有限的路由器中，輸入端口不會進行交換功能，而是由路由處理器統(tǒng)一處理，然后根據(jù) 路由表查找并將數(shù)據(jù)包轉(zhuǎn)發(fā)到相應的輸出端口。

一般這種路由器不是單獨的路由器，而是工作站或者服務器充當?shù)穆酚桑@種路由器內(nèi)部中，路由處理器其實就是 CPU，而輸入端口其實只是網(wǎng)卡。

輸入端口會根據(jù)轉(zhuǎn)發(fā)表定位輸出端口，然后再會進行分組轉(zhuǎn)發(fā)，那么現(xiàn)在就有一個問題，是不是每一個分組都有自己的一條鏈路呢?如果分組數(shù)量非常大，到達億級的話，也會有億個輸出端口路徑嗎?

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

下面是三個輸入端口對應了轉(zhuǎn)發(fā)表中的三個輸出鏈路的示例

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

如何實現(xiàn)呢?

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

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

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

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

一旦通過查找功能確定了分組的輸出端口后，那么該分組就會進入交換結(jié)構(gòu)。在進入交換結(jié)構(gòu)時，如果交換結(jié)構(gòu)正在被使用，就會阻塞新到的分組，等到交換結(jié)構(gòu)調(diào)度新的分組。

交換結(jié)構(gòu)

交換結(jié)構(gòu)是路由器的核心功能，通過交換功能把分組從輸入端口轉(zhuǎn)發(fā)至輸出端口，這就是交換結(jié)構(gòu)的主要功能。交換結(jié)構(gòu)有多種形式，主要分為 通過內(nèi)存交換、通過總線交換、通過互聯(lián)網(wǎng)絡進行交換，下面我們分開來探討一下。

經(jīng)過內(nèi)存交換：最開始的傳統(tǒng)計算機就是使用內(nèi)存交換的，在輸入端口和輸出端口之間是通過 CPU 進行的。輸入端口和輸出端口的功能就好像傳統(tǒng)操作系統(tǒng)中的 I/O 設備一樣。當一個分組到達輸入端口時，這個端口會首先以中斷 的方式向路由選擇器發(fā)出信號，將分組從輸入端口拷貝到內(nèi)存中。然后，路由選擇處理器從分組首部中提取目標地址，在轉(zhuǎn)發(fā)表中找出適當?shù)妮敵龆丝谶M行轉(zhuǎn)發(fā)，同時將分組復制到輸出端口的緩存中。

這里需要注意一點，如果內(nèi)存帶寬以每秒讀取或者寫入 B 個數(shù)據(jù)包，那么總的交換機吞吐量(數(shù)據(jù)包從輸入端口到輸出端口的總速率) 必須小于 B/2。

經(jīng)過總線交換：在這種處理方式中，總線經(jīng)由輸入端口直接將分組傳送到輸出端口，中間不需要路由選擇器的干預?？偩€的工作流程如下：輸入端口給分組分配一個標簽，然后分組經(jīng)由總線發(fā)送給所有的輸出端口，每個輸出端口都會判斷標簽中的端口和自己的是否匹配，如果匹配的話，那么這個輸出端口就會把標簽拆掉，這個標簽只用于交換機內(nèi)部跨越總線。如果同時有 多個 分組到達路由器的話，那么只有一個分組能夠被處理，其他分組需要再進入交換結(jié)構(gòu)前等待。

經(jīng)過互聯(lián)網(wǎng)絡交換：克服單一、共享式總線帶寬限制的一種方法是使用一個更復雜的互聯(lián)網(wǎng)絡。如下圖所示

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

輸出端口處理

如下圖所示，輸出端口處理取出已經(jīng)存放在輸出端口內(nèi)存中的分組并將其發(fā)送到輸出鏈路上。包括選擇和去除排隊的分組進行傳輸，執(zhí)行所需的鏈路層和物理層的功能。

在輸入端口中有等待進入交換的排隊隊列，而在輸出端口中有等待轉(zhuǎn)發(fā)的排隊隊列，排隊的位置和程度取決于流量負載、交換結(jié)構(gòu)的相對頻率和線路速率。

隨著隊列的不斷增加，會導致路由器的緩存空間被耗盡，進而使沒有內(nèi)存可以存儲溢出的隊列，致使分組出現(xiàn)丟包(packet loss)，這就是我們說的在網(wǎng)絡中丟包或者被路由器丟棄。

何時出現(xiàn)排隊

下面我們通過輸入端口的排隊隊列和輸出端口的排隊隊列來介紹一下可能出現(xiàn)的排隊情況。

輸入隊列

如果交換結(jié)構(gòu)的處理速度沒有輸入隊列到達的速度快，在這種情況下，輸入端口將會出現(xiàn)排隊情況，到達交換結(jié)構(gòu)前的分組會加入輸入端口隊列中，以等待通過交換結(jié)構(gòu)傳送到輸出端口。

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

• 使用網(wǎng)絡互聯(lián)的交換方式;
• 假定所有鏈路的速度相同;
• 在鏈路中一個分組由輸入端口交換到輸出端口所花的時間相同，從任意一個輸入端口傳送到給定的輸出端口;
• 分組按照 FCFS 的方式，只要輸出端口不同，就可以進行并行傳送。但是如果位于任意兩個輸入端口中的分組是發(fā)往同一個目的地的，那么其中的一個分組將被阻塞，而且必須在輸入隊列中等待，因為交換結(jié)構(gòu)一次只能傳輸一個到指定端口。

如下圖所示

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

輸出隊列

我們下面討論輸出隊列中出現(xiàn)等待的情況。假設交換速率要比輸入/輸出的傳輸速率快很多，而且有 N 個輸入分組的目的地是轉(zhuǎn)發(fā)至相同的輸出端口。在這種情況下，在向輸出鏈路發(fā)送分組的過程中，將會有 N 個新分組到達傳輸端口。因為輸出端口在一個單位時間內(nèi)只能傳輸一個分組，那么這 N 個分組將會等待。然而在等待 N 個分組被處理的過程中，同時又有 N 個分組到達，所以 ，分組隊列能夠在輸出端口形成。這種情況下最終會因為分組數(shù)量變的足夠大，從而耗盡 輸出端口的可用內(nèi)存。

如果沒有足夠的內(nèi)存來緩存分組的話，就必須考慮其他的方式，主要有兩種：一種是丟失分組，采用 棄尾(drop-tail) 的方法;一種是刪除一個或多個已經(jīng)排隊的分組，從而來為新的分組騰出空間。

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

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

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

等上一個分組被轉(zhuǎn)發(fā)完成后，輸出端口就會選擇在剩下的分組中根據(jù) 分組調(diào)度(packet scheduleer) 選擇一個分組來進行傳輸，我們下面就會聊到分組傳輸。

分組調(diào)度

現(xiàn)在我們來討論一下分組調(diào)度次序的問題，即排隊的分組如何經(jīng)輸出鏈路傳輸?shù)膯栴}。我們生活中有無數(shù)排隊的例子，但是我們生活中一般的排隊算法都是 先來先服務(FCFS)，也是先進先出(FIFO)。

先進先出

先進先出就映射為數(shù)據(jù)結(jié)構(gòu)中的隊列，只不過它現(xiàn)在是鏈路調(diào)度規(guī)則的排隊模型。

FIFO 調(diào)度規(guī)則按照分組到達輸出鏈路隊列的相同次序來選擇分組，先到達隊列的分組將先會被轉(zhuǎn)發(fā)。在這種抽象模型中，如果隊列已滿，那么棄尾的分組將是隊列末尾的后面一個。

優(yōu)先級排隊

優(yōu)先級排隊是先進先出排隊的改良版本，到達輸出鏈路的分組被分類放入輸出隊列中的優(yōu)先權(quán)類，如下圖所示

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

循環(huán)加權(quán)公平排隊

在循環(huán)加權(quán)公平規(guī)則(round robin queuing discipline) 下，分組像使用優(yōu)先級那樣被分類。然而，在類之間卻不存在嚴格的服務優(yōu)先權(quán)。循環(huán)調(diào)度器在這些類之間循環(huán)輪流提供服務。如下圖所示

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

這是一種所謂的保持工作排隊(work-conserving queuing) 的規(guī)則，就是說如果輪詢的過程中發(fā)現(xiàn)有空隊列，輸出端口不會等待分組，而是繼續(xù)輪詢下面的隊列。

本文轉(zhuǎn)載自微信公眾號「 程序員cxuan」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系 程序員cxuan公眾號。