# 【計算機網路筆記】1.4 Delay, Loss, and Throughput in Packet-Switched Networks

[TOC]

Hello Guys, I'm LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, **8**th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。

## 1.4.1 Overview of Delay in Packet-Switched Networks（封包交換網路中的延遲概述）

該節核心概念：解釋封包從源頭（Source）經過一系列路由器（Routers）到達目的地（Destination）的過程中，為什麼會發生延遲（Delay），以及這些延遲是由哪些部分組成的。

一個封包在單一節點所經歷的**延遲總和**定義為四個主要部分的累加：

1. 節點處理延遲（Nodal Processing Delay）
2. 佇列延遲（Queuing Delay）
3. 傳輸延遲（Transmission Delay）
4. 傳播延遲（Propagation Delay）

### 處理延遲（Processing Delay）

處理延遲：封包到達路由器時發生的第一個延遲。

- 成因：路由器需要檢查封包的標頭（Header）來決定導向哪一個輸出連結（Outbound link），同時檢查封包在傳輸過程中是否發生了位元級別的錯誤（Bit-level errors）。
- 耗時：在高速路由器中，這個過程通常非常快，大約在微秒（microseconds）或更短的數量級。
- 處理完畢後，路由器會將封包導向通往下一站的佇列（Queue）。

### 佇列延遲（Queuing Delay）

佇列延遲：封包在路由器內部等待傳輸的時間。

- 成因：當封包被導向輸出連結時，如果有其他封包正在傳輸，或者有其他封包排在前面，新到達的封包就必須在緩衝區（Buffer）中排隊等待。
- 耗時：此為不可預測的延遲，如果網路擁塞（Congestion）程度高，延遲會很長；如果佇列是空的，延遲則為零。
- 延遲範圍：通常在微秒到毫秒（milliseconds）之間。

### 傳輸延遲（Transmission Delay）

傳輸延遲：將封包的所有位元（Bits）推送上連結所需的時間。

- 定義：假設封包長度為 $L$ 位元，連結傳輸速率為 $R$ 位元／秒（bps），傳輸延遲就是 $\frac{L}{R}$。
- 概念：由於是將封包從路由器推送到連結上所需的時間，只跟**封包長度**和**傳輸速率**有關，與兩點之間的距離無關。
- 延遲範圍：通常在微秒到毫秒之間。

### 傳播延遲（Propagation Delay）

傳播延遲：位元進入連結後，傳送到下一個節點所需的時間。

- 定義：假設兩台路由器之間的距離為 $d$ ，傳播速度為 $s$ ，則傳播延遲就是 $\frac{d}{s}$ 。
- 物理限制：傳播速度取決於物理介質（如光纖、銅線），速度大約在 $2 \times 10^8$ 到 $3 \times 10^8$ $\frac{m}{s}$ （公尺／秒）之間（接近光速）。
- 延遲範圍：在廣域網路中，通常是毫秒等級。

### 傳輸延遲 vs 傳播延遲

這兩個名詞只差一個字（以中文來講），但卻很容易搞混，除了這個差異之外，在兩者性質上也很容易會搞混。

- 傳輸延遲（Transmission Delay）：是路由器將封包「推」出去的時間，取決於封包長度和連結頻寬。
- 傳播延遲（Propagation Delay）：是訊號在介質上「跑」的時間，取決於距離。

書中用車隊跟收費站來比喻，如下：

- 情境：有 10 輛車組成的車隊（整個車隊是封包）要通過收費站（路由器），前往高速公路（連結），而每輛車（單一的車輛是位元）都需要時間繳費。
- 傳輸延遲：收費站處理完這 10 輛車並讓它們全部開上高速公路所需的時間，假設收費站每 12 秒處理一輛車，10 輛車就需要 2 分鐘。這就是將整個「封包」推上連結的時間。
- 傳播延遲：車輛從一個收費站開到下一個收費站所需的時間，假設距離 100 公里，車速 100 km/hr，那這段時間就是 1 小時。
- 總時間：從車隊第一輛車抵達第一個收費站，到最後一輛車離開第二個收費站，總共需要：傳輸延遲 + 傳播延遲，也就是 62 分鐘。


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 68, Figure 1.17)

### 公式總結

節點總延遲（ $d_\text{nodal}$ ）可以表示為以下四個延遲的總和：$$d_\text{nodal} = d_\text{proc} + d_\text{queue} + d_\text{trans} + d_\text{prop}$$

各項延遲的權重變化：

- $d_\text{prop}$ （傳播）：在校園網路上可能只有幾微秒，但在衛星連線中可能是主要延遲幾百毫秒。
- $d_\text{trans}$ （傳輸）：在高速連結上可能很小，但在低速撥接網路傳輸大封包時延遲會很顯著。
- $d_\text{proc}$（處理）：通常很小，但會影響路由器的最大吞吐量（Throughput, 亦可稱產出率、流通量）。

:::info
註：在電腦網路中，吞吐量（Throughput）是指在特定時間內，資料成功從傳送端到達接收端的實際速率。常用單位為 bps（Bits per second）、Mbps 或 Gbps。
:::

## 1.4.2 Queuing Delay and Packet Loss（佇列延遲與封包遺失）

為何要把佇列延遲拆開來特別說明？因為它是最複雜且最有趣的，加上不是固定的延遲，而是隨著網路狀態動態變化的。

### 佇列延遲的特性

- 變動性：與處理、傳輸或傳播延遲不同，佇列延遲對每個封包來說可能都不同。
- 例如：如果 10 個封包同時到達一個空佇列，第一個傳輸的封包完全沒有佇列延遲，而最後一個封包則需要等待前 9 個封包傳輸完畢，延遲會很長。
- 統計描述：因為這種隨機性，通常用統計資料來描述它，例如
- 平均佇列延遲
- 佇列延遲的變異數
- 延遲超過特定數值的機率。

### 佇列延遲的指標：流量強度（Traffic Intensity）

要判斷佇列延遲的大小，最關鍵的指標就是流量強度，如何計算流量強度？有三個參數要先知道：

1. $a$ ：封包到達佇列的平均速率（單位：封包/秒，pkt/sec）。
2. $L$ ：封包的長度（單位：位元，bits），假設所有封包長度相同。
3. $R$ ：連結的傳輸速率（單位：位元/秒，bits/sec），即封包被推送到連結上的速度。

流量強度公式：

假設封包到達的平均速率是 $a$ ，每個封包有 $L$ 位元，則位元到達佇列的平均速率為 $La$ 位元／秒。

最後假設該佇列是無限大，可存放無窮多個位元。

流量強度的定義就是 $\frac{La}{R}$ 這個比值。

### 流量強度的三種情況分析

1. 流量強度 $> 1$（$\frac{La}{R} > 1$）
- 狀況：位元到達佇列的速度超過了位元從佇列輸出的速度。
- 結果：佇列長度將無限增長，佇列延遲會趨近於無限大。
- 黃金法則：在流量工程中，設計系統時必須確保流量強度不大於 1。
2. 流量強度 $\le 1$（$\frac{La}{R} \le 1$）
- 即使平均速率不超過傳輸能力，到達的模式也很重要，大概有兩種模式：
- 封包是**週期性**地、一個接一個均勻到達（如每 $\frac{L}{R}$ 秒到達一個），則佇列永遠是空的，延遲為 0。
- 封包是**爆發性**地（Burst）到達的（如每 $N\frac{L}{R}$ 秒同時到達 $N$ 個），那這群封包中的第一個沒有延遲，但第 $n$ 個封包就必須等待前 $n−1$ 個封包傳輸，導致平均延遲顯著增加。
3. 流量強度 $\le 1$（$\frac{La}{R} \le 1$），但隨機到達（Random Arrivals）
- 現實中，封包的到達是隨機的。
- 見下圖（Figure 1.18）的曲線圖，橫軸是流量強度（$La/R$），縱軸是平均佇列延遲。
- 當流量強度接近 0 時：延遲接近 0。
- 當流量強度接近 1 時：延遲會指數級急劇上升。
- 比喻：就像高速公路，如果交通量已經很大（接近容量上限），這時只要多一點點車流，就會導致嚴重的回堵（延遲激增）。


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 70, Figure 1.18)

### 封包遺失（Packet Loss）

前面的討論假設佇列可以無限長，屬於理論範疇，但在現實世界中的資源是有限的。

- 有限容量：路由器的佇列（Queue），也就是物理上的緩衝區容量是有限的。
- 封包遺失（Packet Loss）：當流量強度持續接近或超過 $1$ ，佇列會被填滿，如果一個新封包到達時發現佇列已滿，路由器不能繼續存它，只能將其丟棄（Drop），此為封包遺失。
- 後果：從終端系統的角度來看，這個封包傳進網路後就消失了，通常會導致應用層或傳輸層（如 TCP）進行重傳（Retransmission）的動作。

## 1.4.3 End-to-End Delay（端到端延遲）

前兩節專注的是單一路由器的節點延遲（Nodal Delay），該節放大視角探討封包從源頭主機（Source）出發，經過網路路徑，最終到達目的主機（Destination）的總延遲。

### 理論模型：累積的延遲

假設源頭主機和目的主機之間有 $N−1$ 個路由器（也就是有 $N$ 條連結），且網路目前沒有擁塞（忽略佇列延遲），那端到端延遲可以簡單地視為路徑上每個節點延遲的總和。

也就是： $$d_\text{end-end} = N(d_\text{proc} + d_\text{trans} + d_\text{prop})$$

- $N$ ：連結數量。
- $d_\text{trans}$ ：傳輸延遲（ $\frac{L}{R}$ ），即把封包推上連結的時間。
- $d_\text{proc}$ ：處理延遲。
- $d_\text{prop}$ ：傳播延遲。

該公式說明了總延遲是路徑上每一個節點（路由器和主機）的處理、傳輸和傳播延遲的累加。

### 實務測量工具：Traceroute

實際上如何測量網路上兩點之間的延遲？用 Traceroute。

#### Traceroute 的運作原理

為了測量到目的地的路徑和延遲，Traceroute 採取了一種聰明的策略：

1. 發送**特殊封包**：源頭主機向目的地發送一系列特殊的封包，可想像這些封包被標記為 $1$ 到 $N$。
2. 路由器的反應：
- 當路徑上的第 $N$ 個路由器收到標記為 $N$ 的封包時，它不會將封包繼續轉發給下一個路由器。
- 相反地，它會向源頭主機發送一個回傳訊息，並告訴源頭它的**名稱**跟**位址**。
3. 記錄時間：源頭主機記錄從「**發送封包**」到「**收到回傳訊息**」所經過的時間，這就是該路由器的**往返時間**（Round-Trip Time, RTT）。
4. 終點反應：當最後一個封包（標記為 $N$）到達真正的目的地主機時，目的地主機也會回傳一個訊息給源頭。

透過這種方式，源頭主機可以拼湊出封包經過的所有路由器清單，以及到達每個路由器的往返延遲。

#### Traceroute 範例

從美國麻薩諸塞大學到法國索邦大學的兩端主機做 Traceroute 測試，其輸出結果如下：


Data From：Computer Networking: A Top-Down Approach (8th ed., p. 72)

由左到右的欄位是這樣的：

| 欄位 | 意義 | 觀察重點 |
| -------- | -------- | -------- |
| 路由器編號 | 路徑上的第幾個節點 | 從 1 開始遞增。 |
| 路由器名稱 | 該節點的身份 | 如 `gw-vlan-2451.cs.umass.edu` |
| 路由器位址 | 該節點的身份 | 如 `(128.119.245.1)` |
| RTT（3 次測試） | 往返延遲時間（毫秒） | Traceroute 通常會對每個節點測三次。 |

關鍵觀察點：

1. 延遲的波動：可發現同一路由器的三次 RTT 數據不同（如 1.899 ms, 3.266 ms, 3.280 ms），此因為網路中的佇列延遲（Queuing Delay）是隨機變化的。
2. 後面路由器延遲較短：
- 有時看到第 $N+1$ 個路由器的 RTT 比第 $N$ 個還短，如：路由器 12 的延遲比路由器 11 還小。
- 因為網路擁塞狀況隨時在變化，測量第 11 號路由器時可能剛好遇到網路塞車，而測量第 12 號時網路比較順暢。
3. 星號（`*`）：如果源頭主機在一段時間內沒有收到回傳訊息，Traceroute 會顯示星號，通常代表封包遺失（Packet Loss）或者是該路由器設定為不回應此類探測。
4. 地理距離影響：
- 路由器 7 到路由器 8 的延遲突然大增（從約 7 ms 跳到 77 ms）。
- 因為封包正在跨越大西洋海底光纜，物理距離導致傳播延遲（$d_\text{prop}$）顯著增加。

### 其他類型的延遲

除了網路核心延遲之外，還有其他發生在端系統（End System）的延遲：

- 端系統處理延遲：若想在共享媒介（如 WiFi 或 Cable）上傳輸，可能需要等待媒介空閒，這是端系統的一種延遲。（要跟其他端系統共用就會這樣）
- 媒體封包化延遲（Media Packetization Delay）：在 VoIP（Voice over Internet Protocol，網路語音協議）應用中很常見，發送方需要先將語音編碼並填滿一個封包才能發送，該「**填滿封包所需的時間**」即為封包化延遲。

## 1.4.4 Throughput in Computer Networks（電腦網路中的吞吐量）

註：吞吐量亦稱流通量、產出率（量）等等。

除了前面討論過的延遲（Delay）和丟包（Packet Loss），吞吐量（Throughput）也是衡量網路效能的另一個關鍵指標。

如果延遲是關於「多快到達」，那吞吐量就是有關於網路「能傳送多少資料」。

### 什麼是吞吐量？

假設主機 A 要傳送一個大檔案給主機 B：

- 瞬時吞吐量（Instantaneous throughput）：等同於在任何給定的瞬間，主機 B 接收檔案的**速率**（以 bits/sec 為單位）。
- 平均吞吐量（Average throughput）：如果檔案大小為 $F$ 位元，主機 B 接收完整個檔案花費了 $T$ 秒，則平均吞吐量為 $\frac{F}{T}$（bits/sec）。

#### 為什麼吞吐量很重要？

對於某些應用（如網路電話、視訊會議），需要持續且穩定的吞吐量（高於某個門檻，e.g. 網路電話 > 24 kbps、即時影像應用 > 256 kbps）。

對於其他應用（如檔案下載），通常只希望吞吐量越高越好，以縮短等待時間。

### 瓶頸連結（Bottleneck Link）

假設伺服器（Server）透過一條速率為 $R_s$ 的連結連接到路由器，而路由器再透過一條速率為 $R_c$ 的連結連接到客戶端（Client），中間沒有其他干擾流量。

- 若 $R_s < R_c$ ：伺服器傳送資料的速度比客戶端接收的速度慢，此時，資料會順暢地流過路由器，吞吐量受限於 $R_s$ 。
- 若 $R_s > R_c$ ：伺服器灌入資料的速度比路由器轉發給客戶端的速度快，路由器無法及時轉發，資料會堆積在路由器緩衝區（這是我們不樂見的情形），此時，吞吐量受限於 $R_c$ 。


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 74, Figure 1.19)

對於這個簡單的雙連結網路，端到端吞吐量是 $min\{R_c, R_s\}$ ，當中傳輸速率最低的連結，就被稱為該路徑的瓶頸連結（Bottleneck Link）。

擴展一下思路，若有 $N$ 條連結（見 Figure 1.19 的 b.），速率分別是 $R_1, R_2, \cdots, R_N$ ，那吞吐量就是 $min\{R_1, R_2, \cdots, R_N\}$

### 現實網路中的吞吐量限制

- 網際網路核心：通常被過度配置（Over-provisioned），擁有極高速的傳輸速率，很少成為瓶頸。
- 存取網路（Access Network）：通常是限制吞吐量的關鍵。
- 如果伺服器的上傳頻寬是 2 Mbps，而你的下載頻寬是 1 Mbps，即便中間網路再快，你的下載速度最高也只有 1 Mbps。
- 反之，如果你有 100 Mbps 的光纖，但伺服器只有 2 Mbps 的上傳能力，你的下載速度就會被限制在 2 Mbps。

結論：在現今的網際網路中，吞吐量的限制因素通常在於存取網路（也就是家中或伺服器連接到網路的那一段）。

### 干擾流量的影響（Intervening Traffic）

假設有個共享連結情境：有 10 個伺服器和 10 個客戶端同時在進行檔案下載，他們都通過網際網路核心中的一條共同連結，該連結的速率為 $R$ 。

如果這條共同連結 $R$ 非常大（例如比所有存取連結的總和還大），它就不會是瓶頸，吞吐量仍取決於各自的存取速率 $min\{R_s, R_c\}$ 。

但如果 $R$ 不夠大（例如 $R$ 跟 $R_s, R_c$ 差不多），這條連結就會成為新的瓶頸。

在這情境的最終結果：假設這條連結公平地將頻寬分給這 10 個客戶端下載任務，每個客戶端下載獲得的吞吐量將只有 $\frac{R}{10}$。

這說明吞吐量不僅取決於路徑上的連結傳輸速率，也取決於當前的網路流量負載（Intervening traffic），也可稱其為介入的資料流量。


Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 76, Figure 1.20)

## 總整理

### 封包交換網路中的延遲

封包從來源端到目的端，沿途經過多個路由器，每一個節點都會產生延遲，單一節點的總延遲（$d_\text{nodal}$）由四個部分組成：$$d_\text{nodal} = d_\text{proc} + d_\text{queue} + d_\text{trans} + d_\text{prop}$$

**四種延遲一覽**：

1. 處理延遲（Processing Delay）
路由器檢查封包標頭、錯誤檢查的時間，通常極短（微秒等級）。
2. 佇列延遲（Queuing Delay）
封包在緩衝區等待傳輸的時間，最不穩定、最難預測，與網路擁塞高度相關。
3. 傳輸延遲（Transmission Delay）
將封包所有位元推送到連結上的時間，為 $$\frac{L}{R}$$
只與封包大小與頻寬有關，與距離無關。
4. 傳播延遲（Propagation Delay）
訊號（位元）在實體媒介中傳遞的時間，為 $$\frac{d}{s}$$
只與距離與物理介質有關。

**傳輸延遲跟傳播延遲的差異**：

- 傳輸延遲＝「推資料上線要多久」
- 傳播延遲＝「訊號在路上跑多久」

### 佇列延遲與封包遺失

#### 流量強度（Traffic Intensity）

衡量佇列延遲大小的指標： $$\text{Traffic Intensity} = \frac{La}{R}$$

- $a$ ：封包到達速率。
- $L$ ：封包大小。
- $R$ ：連結速率。

**三種典型情況**：

- $\frac{La}{R} > 1$
到達速度 > 傳輸能力 → 佇列無限成長 → 延遲趨近無限。
- $\frac{La}{R} \le 1$，但爆發式到達
平均可行，但仍會產生顯著佇列延遲。
- $\frac{La}{R} \to 1$，隨機到達（現實狀況）
平均佇列延遲會指數型暴增，類似高速公路快滿時的塞車現象。

#### 封包遺失（Packet Loss）

- 實際佇列容量有限。
- 佇列滿時，新封包會被丟棄。
- 上層（如 TCP）需重傳，進一步加劇擁塞。

### 端到端延遲（End-to-End Delay）

理論模型（忽略佇列），若有 N 條連結：$$d_\text{end-end} = N(d_\text{proc} + d_\text{trans} + d_\text{prop})$$

本質上是沿途每個節點延遲的累加。

#### Traceroute

- 利用逐步限制封包存活次數（TTL, Time To Live）的方式。（第 $N$ 個路由器收到標記為 $N$ 的封包不會繼續傳，而是會回傳名稱跟位址回去）
- 量測每一跳的 RTT（往返時間）。
- 可觀察：
- 延遲波動（佇列延遲隨機）
- 封包遺失（星號）
- 長距離連線造成的傳播延遲暴增（如跨洋光纜）

#### 其他延遲來源

- 端系統等待媒介（如 WiFi 共用）
- 多媒體封包化延遲（如 VoIP 需先填滿封包）

### 吞吐量（Throughput）

定義：

- 瞬時吞吐量：某一瞬間的接收速率
- 平均吞吐量：如果檔案大小為 $F$ 位元，主機 B 接收完整個檔案花費了 $T$ 秒，則平均吞吐量為 $$\frac{F}{T}$$

延遲注意的是「多久到」，吞吐量則注意「能送多少」。

### 瓶頸連結（Bottleneck Link）

端到端吞吐量 = 路徑上最慢的那條連結 $min\{R_1, R_2, \cdots, R_N\}$

現實上：

- 網際網路核心：通常不構成瓶頸。
- 存取網路（家用網路、伺服器端）：最常成為限制因素。

### 干擾流量的影響（Intervening Traffic）

- 多條資料流共享同一連結時。
- 即使個別連線很快，共用連結仍可能成為瓶頸。
- 頻寬若公平分配，吞吐量會被平均瓜分（如 $\frac{R}{10}$）。