電腦網路概論

tags: NCKU

Chapter 1 Introduction

常見縮寫

• ISP：網路服務供應商 Internet Service Provider (e.g. 中華電信)
• TCP：傳輸控制協定 Transmission Control Protocol
• UDP：使用者資料包協定 User Datagram Protocol

常見設備

數據機 (modem, modulator-demodulator)

是一個能將數位訊號調變到類比訊號進行傳輸，並解調收到的類比訊號為數位訊號的電子裝置。

路由器 (router)

提供路由與轉送兩種重要機制：

• 路由：決定封包於host到host之間的傳輸路徑的過程
• 轉送：將路由器輸入端的封包移送至適當的路由器輸出端

路由的工作在OSI網路模型的網路層

何謂協定 (Protocol)?

Protocol defines the format, order of messages sent and received among network entities, and actions taken on message transmission, receipt.

協定定義了網路實體之間發送和接收消息的格式、順序，以及對消息傳輸、接收所採取的動作。

協定是一種標準化的溝通規範，它描述了通訊系統中的通訊規則、數據格式、錯誤檢測和糾錯機制，以確保通訊雙方能正確地解讀和處理訊息。

TCP/IP Model 封裝名稱

• 傳輸層
  • TCP表頭+資料：TCP 區段 (TCP Segment)
  • UDP表頭+資料：UDP 資料包 (UDP Datagram)
• 網路層
  • IP表頭+資料：IP 資料包 (IP Datagram) 或 封包 (packet)
• 鏈結層
  • 鏈結層表頭+資料+(表尾)：訊框 (Frame)

封包傳輸

封包延時 Packet delay

$$d_{nodal}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$$

• $d_{nodal}$：節點總延時
• $d_{proc}$：節點處理延時
  • 檢查錯誤
  • 判斷輸出線路
  • 通常時間 < microsecs
• $d_{queue}$：排隊延時
  • 等待傳輸
• $d_{trans}$：傳輸延時，將封包推向線路的時間
  • $L$：封包長度 (bits)
  • $R$：傳輸速率(bits/sec)
  • $d_{trans}=L/R$
• $d_{prop}$：傳播延時，實體線路的傳播時間
  • $d$：實體線路長度
  • $r$：傳播速率
  • $d_{prop}=d/r$

封包排隊延時 Packet queueing delay

• $a$：平均封包到達速率
• $L$：封包長度 (bits)
• $R$：傳輸速度 (bit transmission rate)

traffic intensity

$$\frac{L\cdot a}{R}:\frac{\text{arrival rate of bits}}{\text{service rate of bits}}$$
當值大於0.7

$\Rightarrow$ high queueing delay

封包丟失 Packet loss

Chapter 2 Application Layer

常見縮寫

• TLD：Top-Level-Domain
• RTT：Round-Trip Time
  • 資料從發送端到接收端再返回發送端的時長

HTTP (HyperText Transfer Protocol)

• 使用TCP
• Port：80

運作流程：
    1. 客戶端初始化與伺服器的TCP連線 (80 port)
    2. 伺服端接受客戶端的TCP連線
    3. 兩端互相交換HTTP訊息
    4. 關閉TCP連線

版本差異

版本	差別
HTTP/1.0	1個物件、1個TCP連線，每個物件需要 2 RTT
HTTP/1.1	多個物件、1個TCP連線
HTTP/2.0
HTTP/3.0

DNS (Domain Name System)

• 使用兩者TCP或UDP傳輸
• Port：53
• 可同時發送多個請求
• 主機發送DNS請求時，會發送到 Local DNS server

DNS資源紀錄 Resource Record (RR)

格式：(name, value, type, ttl)
name：域名
ttl： Time to Live

Type	Description
A	將域名解析為 IPv4
AAAA	將域名解析為 IPv6
NS	指定該域名的DNS伺服器
CNAME	將域名解析為另一個域名(別名)
MX	指定郵件伺服器的地址
PTR	反向DNS查詢，將IP解析為域名

SMTP (Simple Mail Transfer Protocol)

• 使用TCP
• Port：25
• 用於傳輸郵件 (push)

IMAP (Internet Message Access Protocol)

• Port：143
• 一種郵件伺服器和郵件客戶端之間的協定
  

Chapter 3 Transport Layer

Principle of reliable data transfer (rdt)

version	assumption
rdt 1.0	reliable channel: no bits error, no loss of packets
rdt 2.0	channel with bit error，include ACKs、NAKs
rdt 2.1	handle corrupt on ACK/NAKs，include sequence number(0, 1)
rdt 2.2	NAK-free，add seq# to ACK
rdt 3.0	channel with errors and loss，include timeout

Principles of congestion control

Approaches

• End-end congestion control
  • 沒有明確的回應
  • 從丟失和延遲來推斷壅塞
  • TCP 使用的方法
• Network-assisted congestion control
  • 路由器會有明確的回應
  • 回覆壅塞的程度或明確指示傳送速率
  • TCP ENC, ATM, DECbit protocol

Transmission Control Protocol (TCP)

TCP round trip time (RTT), timeout

• 如何決定 TCP timeout 的值?
• SampleRTT
  • 測量將Segment送出到接收ACK的時間
  • 每次測量的值可能會差很多，所以要將先前的預測納入考慮，才能讓結果更 Smooth
• 使用 Exponential Weighted Moving Average (EWMA)
• EstimatedRTT
  • EstimatedRTT
    ${}_1$ =
    $(1-\alpha )$*EstimatedRTT
    ${}_0$ +
    $\alpha$*SampleRTT
    ${}_1$
  • $\alpha$ 通常為 0.125
• 將結果再加上安全邊界(safety margin)
• TimeoutInterval
  ${}_1$ = EstimatedRTT
  ${}_1$ + 4*DevRTT
  ${}_1$
  • DevRTT
    • Dev：Deviation 偏差
    • SampleRTT
      ${}_1$ 對 EstimatedRTT
      ${}_0$ 偏差的 EWMA
    • DevRTT
      ${}_1$ =
      $(1-\beta )$*DevRTT
      ${}_0$ +
      $\beta$*
      $|$SampleRTT
      ${}_1$ - EstimatedRTT
      ${}_0$
      $|$
    • $\beta$ 通常為 0.25

TCP Connection Management

建立連線
TCP 3-way handshake

關閉連線

TCP congestion control

• AIMD
• slow start
• CUBIC
• fairness

Network Layer Introduction

• 主要功能

  • forwarding：將輸入的封包導向至正確的輸出端
  • routing：決定封包從來源端到目的端的傳輸路徑

• Plane

  • Data plane
    • forwarding
    • local：per-router function
  • Control plane
    • routing
    • network-wide logic

Chapter 4 Network Layer - Data plane

• Router architecture
  • input ports
  • switching
  • output ports

• Internet Protocol (IP)
  • IP address (32 bits)
• Dynamic Host Configuration Prorocol (DHCP)
  • 取得IP位址

Input ports

• 功能
  • 使用 header fields value 和 forwarding table 找到 output port
• forwarding
  • destination-based forwarding (traditional)：僅透過目的IP來判斷
  • generalized forwarding：透過 header field value 來判斷

Longest Prefix matching

• 找相對應的前綴 (prefix)
• 若有多個，找對應最多的 (longest)

Swtiching fabrics

• 三種主要的形式
  • memory
  • bus
  • interconnecting network

Output ports

• Buffering
• Scheduling discipline

Packet scheduling

• FCFS (first come, first served)
• Priority queue
• Round Robin
• Weighted fair queueing (WFQ)

Internet Protocol (IP)

Chapter 5 Network Layer - Control plane

Chapter 6 Link Layer

Introduction

• 用 frame 封裝 datagram，加入表頭、表尾
• 負責傳輸 datagram 從一個節點到另一個物理上鄰接的節點
• 從發送端到目的端中間的節點間，可透過不同的方式傳輸
  • 例如：將 datagram 從 A 傳到 C
  • A 到 B 用 Ethernet 傳
  • B 到 C 用 WiFi 傳
• 使用 MAC位址 (Media Access Control Address) 來辨別來源端和目的端
• Link Layer 提供的服務有
  • framing：封裝資料包
  • 節點間可靠的傳輸
  • 流量控制 (flow control)
  • 錯誤偵測 (error detection)、錯誤糾正 (error correction)
  • 半雙工 (half-duplex)、全雙工 (full-duplex)
    • 差別在於兩端是否能同時互相傳輸資料
• Link Layer 被實作在網路介面卡(Network Interface Card, NIC)或晶片(chip)上

MAC address

• 48-bit, e.g. 1A-2F-BB-76-09-AD
• 前三碼：製造商、後三碼：流水號
• 印在網卡上

Error Detection, Correction

Error Detection

不是100%可靠

在傳送資料(D)的時候，以 bits 的方式來看，用演算法對原始資料做計算產生錯誤檢查碼(Error Detection Code, EDC)，再將EDC加在D的後面並送出。

送出的資料

–-D–-	EDC

接收到的資料

–-D'–-	EDC'

將接收到的資料，用同樣的方式對 D' 生成EDC，再去檢查是否和 EDC' 相同。

資訊冗餘 (information redundancy)
像上面的例子，在資料後面加上一些資訊，可用來檢測一致性和恢復損壞的資訊

奇偶校驗 (pairty checking)

checksum

就和前面的一樣

迴圈冗餘校驗 (Cyclic Redundancy Check, CRC)

可以把一組位元想像成是一個多項式
例如，

${111}_2$ 的多項式就是

$x^2+x+1$、

${101}_2$ 就是

$x^2+1$

假設原始資料

$M(x)$、鑰匙

$K(x)$ (

$n+1$階多項式)

計算

$$M(x)\cdot x^n=Q(x)\cdot K(x)-R(x)$$

$M(x)\cdot x^n$ 相當於將

$M$ 左移

$n$ 位

實際傳送的資料是

$M(x)\cdot x^n+R(x)$
接收端只要檢查收到的資料是否能被

$K(x)$整除，就能知道是否是正確的。

簡報上的表示法

D：data bits
G：bit pattern (key) (r+1 bits)
R：D*

$2^r$ / G 的餘數 (r bits)

傳送的資料：<D,R>=D*

$2^r$+R

接收端知道 G
就可以檢查接收到的資料<D,R>是否能被G整除
如果算出來有餘數的話：Error Detected!

Multi Access Protocol

多重存取協定

• channel partitioning MAC protocol
  • TDMA (time division)
  • FDMA (frequency division)
  • CDMA (code division)
• random access MAC protocol
  • ALOHA
  • Slotted ALOHA
  • CSMA
  • CSMA/CD
• "taking turns" protocol
  • polling
  • token-passing
  • Bluetooth

TDMA

FDMA

Pure ALOHA

Slotted ALOHA

假設

• 每個 frame 的大小都一樣
• 將時間分成好幾個 slot
• node 之間是同步的

當 node 接收到新的 frame，會在下一個 slot 進行傳送

• 沒有碰撞(沒有其他node用同一個slot)：
  • 送出
• 碰撞發生：
  • 在接下來的slot會有機率
    $p$ 的機會選擇送出，直到成功送出為止

效率

$N$ 個節點要送出多個 frame，機率

$p$

• 一個節點成功送出的機率：
  $p(1-p{)}^{N-1}$
• 任意一個節點成功送出的機率：
  $Np(1-p{)}^{N-1}$
• 最大效率：找出
  $p^{\ast }$ 使
  $Np(1-p{)}^{N-1}$ 最大
• 得到
  $p^{\ast }=1/e=0.37=37\mathrm{\%}$

Carrier Sense Multiple Access (CSMA)

CSMA/CD：CSMA with collision detection
CSMA/CA：CSMA with collision avoidance

Ethernet CSMD/CD algorithm

1. NIC 從網路層接收 datagram 加上 frame
2. NIC 感測 channel
   • 若 idle：馬上送出
   • 若 busy：等待直到 idle 再傳送
3. 若完整送出且沒有碰撞，Done!
4. 若在傳輸的過程中感測到碰撞：終止傳輸
5. 等待一段時間，回到第 2. 步
   • binary (exponential) backoff
     • 在經過
       $m$ 次碰撞後，NIC 會從
       $\{0,1,\dots ,2^m-1\}$ 裡面隨機選一個
       $K$，等待
       $K\cdot 512$ bit times
     • bit time：NIC 彈出 1 bit 所需的時間
       • Example：10 Mbit/s NIC
       • bit time = 1 / (10 * 10^6) s = 100 ns

Address Resolution Protocol (ARP)

位址解析協定

ARP table：存在於 LAN (Local Area Network) 的每一個節點中，用於 IP/MAC 之間的對照
<IP address; MAC address; TTL>

用廣播的方式傳送

ARP query

Destination MAC address：FF-FF-FF-FF-FF-FF
Ethernet frame (sent to FF-FF-FF-FF-FF-FF)

Source MAC: 71-65-F7-2B-08-53
Source IP: 137.196.7.23
Destination IP: 137.196.7.14

ARP response

Ethernet frame (sent to 71-65-F7-2B-08-53)

Target IP address: 137.196.7.14
Target MAC address: 58-23-D7-FA-20-B0

Ethernet

• Connectionless：no handshaking
• Unreliable：no ACK or NAK
• MAC protocol：CSMA/CD with binary backoff

Ethernet frame structure

…

Switch

• link-layer device
• store, forward Ethernet frames

Switch forwarding table

(MAC address of host, interface to reach host, time stamp)