[[357649]]

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

網(wǎng)絡(luò)層概述

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

網(wǎng)絡(luò)層的作用從表面看上去非常簡(jiǎn)單，即將分組從一臺(tái)主機(jī)移動(dòng)到另外一臺(tái)主機(jī)。為了實(shí)現(xiàn)這個(gè)功能，網(wǎng)絡(luò)層需要兩種功能

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

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

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

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

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

路由器工作原理

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

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

上面只是這幾個(gè)組件的簡(jiǎn)單介紹，其實(shí)這幾個(gè)組件的組成并不像描述的那樣簡(jiǎn)單，下面我們就來(lái)深入聊一聊這幾個(gè)組件。

輸入端口

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

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

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

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

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

v我們的潛意識(shí)中顯然不是的，來(lái)看下面一個(gè)例子。

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

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

如何實(shí)現(xiàn)呢?

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

如果存在一個(gè)匹配項(xiàng)，那么就會(huì)轉(zhuǎn)發(fā)到對(duì)應(yīng)的鏈路上，可能不好理解，我舉個(gè)例子來(lái)說(shuō)吧。

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

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

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

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

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

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

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

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

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

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

輸出端口處理

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

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

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

何時(shí)出現(xiàn)排隊(duì)

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

輸入隊(duì)列

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

為了描述清楚輸入隊(duì)列，我們假設(shè)以下情況：

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

如下圖所示

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

輸出隊(duì)列

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

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

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

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

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

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

分組調(diào)度

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

先進(jìn)先出

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

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

優(yōu)先級(jí)排隊(duì)

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

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

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

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

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

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

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