Categories
最新消息

路由器你竟然是這樣的…


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

網路層概述

網路層是 OSI 參考模型的第三層,它位於傳輸層和鏈路層之間,網路層的主要目的是實現兩個端系統之間透明的數據傳輸。

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

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

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

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

  • 數據平面(data plane):負責轉發網路流量,如路由器交換機中的轉發表(我們後面會說)。
  • 控制平面(control plane):控制網路的行為,比如網路路徑的選擇。

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

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

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

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

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

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

路由器工作原理

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

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

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

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

輸入埠

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

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

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

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

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

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

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

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

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

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

如何實現呢?

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

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

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

路由匹配遵循 最長前綴原則(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) 的規則,就是說如果輪詢的過程中發現有空隊列,輸出埠不會等待分組,而是繼續輪詢下面的隊列。