Network Layer: Data Plane#

Overview#

Routing#

根據 forwarding table（決定你要往哪走） 的產生方式大致上分成兩種大類別

1. Traditional Routing Algorithm

• 用統一的 distributed algorithm，router 之間的 algorithm 互相溝通形成 forwarding table

2. Software-Defined Networking(SDN)

• 有一個 Romote controller 的 process 擁有所有 router 的資訊去做統一計算，然後分發給各個 router
• Controller 通常會在各個 data center 或是 server
• 每個 router 會有一個 agent 收集資料給 center

Service model#

• 對於 Internet 來說，他採用 best effort service model，所以並沒有保證任何東西
  • 不保證成功傳輸到 destination
  • 不保證 Timing, Order
  • 不保證 Bandwidth available to end-end-flow

Router#

Router Architecture#

• 具有 Link Layer 的各種 input/output 接口
• 有 switching fabric 來做各種網路控制
• Routing Processor 用來做 control plane 的各種功能以及計算

Input port#

• Line termination: Physical layer 看看是 wireless 還是 copper 或 fabric
• Data Link: Link layer
• Decentralized Switching:
  • 是一種 Match plus action
  • 對 Queuing Datagram 做 Destination-based 的 forwarding
  • 根據各種 header 去做 locally 的 forward

Destination-based forwarding#

• 通常會被 aggregate 成一個 range，不然會存太多東西

• 但有可能會產生一些問題，像是有其中一小段的 data 雖然被分配在 Interface 3 但他其實，但他的目的地應該是 router 1，這時候就可以用 longest prefix matching

對於這個 table

• 11001000 00010111 00010110 10100001 應該去 Link 0
• 11001000 00010111 00011000 10101010 雖然 Link 2 也 match 但應該去 Link 1

通常這個動作會在 Ternary content addressable meemory (TCAM) 裡面就完成

• CAM 可以意思是這個記憶體 present address
• TCAM 可以在一個 CLK 裡面把任意大小的 table 完全 matching 完畢

Switching fabrics#

• Switching Rate: Rate transfer from input to output，理想上所有 input size $N$ 的 data 要在

$$NR$$

的時間內完成傳輸

• 理想上是一種 non-blocking switch 但是在這種情況下通常會比較高成本
• 但通常都會是 blocking 的，所以我們必須要有 input port queuing

有以下這幾種 switching 方法，Interconnection Network 比較常見

• Switching via Memory
  • First generation Routers
  • 這種 switching 就是另一種普通 I/O 而已
  
  

  Switching fabrics 2

• Switching via Bus
  • 從 input 輸入後，經由 bus connection 不經過 memory 直接前往 output
  • 限制就變成 bus 的頻寬
  
  

  Switching fabrics 3

• Switching via Interconnection Network
  • 本來是設計給 multiprocessor 用的一種傳輸方法
  • 通常不會用上面的形式，而是用 multi-stage 的形式
  
  

  Switching fabrics 4

  • $8 \times 8$ 的設計但只需要 4 個中繼點就好了
  • 我們通常會想用 parellel 的形式去做傳送，可以讓速度大幅增加
  
  

  Switching fabrics 5

  • 上圖是 Cisco CRS router
    • 通常有 8 個 switching plane，每個 switching plane 都 是用 3-stage interconnection 來達到平行化

Input Port Queue#

• 是一種 Head-of-the-Line (HOL) blocking: 整個 Queue 的第一個 datagram block 導致的 blocking

• 左圖有兩個 input port 裡的 datagram 同時想競爭一個 output port，在 system 決定誰優先後，第二個人會被 block 住，右圖中的綠色 datagram 因為 head 被 block 所以自己也得等待就是一種 HOL blocking

Output Port Queue#

Output port 結構大致與 input 完全相反

• output port queue 發生的原因是在 switch fabric 中平行傳輸的 datagram 到這裡被只剩下一個 Data Link 可以傳輸離開

$$\underset{\text{Input rate (parellel)}}{NR} > \underset{\text{Output rate}}{R}$$

因此必定需要 buffering，queueing (delay) and loss 就會發生在 output port buffer overflow

• 對於一個 capacity 為 $C$, $N$ flow 的 link 來說 buufer 大小應該要是

$$\text{Buffer Size} = \frac{\text{RTT}\cdot C}{\sqrt{N}}$$

太大的 Buffer 可能導致 RTT 過長，傳輸效率減低

• Buffer managament 大致分為
  • Drop Policy
    • Tail drop: 最新 arrive 的 packet 會被 drop 掉
    • Priority: 根據 priortity 做 drop
  • Marking
    • ESN, RED 等 congestion signal，會被標記在 IP header 上
• Packet Scheduling 要決定誰先執行
  • FCFS: first come first serve
  
  

  Output Port Queue 2

  • 就是種最基本的 FIFO 結構
  • Priority
  
  

  Output Port Queue 3

  • 會根據 ISP 的 Priority 去做分配，如果 packet prioty 高就會被存在 high priority queue
  
  

  Output Port Queue 4

  • 雖然 packet 2 比 packet 3 還早到，但他們在 packet 1 處理完成的時候都已經進入 queue，所以會優先執行 high priority 的
  • Round Robin (RR) scheduling
  
  

  Output Port Queue 5

  • 一樣分成多個 queue，但這次執行順序是輪流，每個 queue equally 的輪流執行
  • Weighted Fair Queuing (WFQ)
  
  

  Output Port Queue 6

  • 更 Generalize 的 Robin Round
  • 除了原始的輪流執行，會分配給每個 Queue 一個 weight $w_i$，i-th queue 分配到的時間就是

$$\text{Cycle time} \times \frac{w_i}{\sum_j w_j}$$

IP#

以下是當代的 IP header 架構

• Version: IP protocol version: IPv4, IPv6
• Type of service:
  • diffserv: 哪種類型的 congestion
  • ECN: Congestion Control 中使用 router 控制時討論過
• Time-to-live: TTL, remaining max hops
  • Checksum, TTL 都是 per-router 重新計算的數字，非常耗資源，所以才會有改良的 IPv6
• Data 就是 TCP or UDP 的 payload
• 大約 20 byte 是 IP header

Fragment, Reassemble#

• 一個 link 會有 Maximum Transfer Size(MTU)，當你發現傳過來的資料已經超過 MTU 的大小就要做 Fragment

• -20 byte 的 header 會有 1480 byte，offset 用 page 算，所以

$$\text{offset} = \frac{1480}{8} = 185$$

• 資料會多 40 byte，因為從一個 IP header 變成三個 IP header

• 最後根據這些 datagram 做 reassemble

IP addressing#

在現代網路架構中，32-bit identifier 會對應一個 router interface

• 一般電腦會有兩種 interface
  • Wireless
  • Ether net
• IP address 會把一組 interface 做 associate（先跳過 Link layer 的 implement）

• 我們會把 IP address 分成 subnet part 跟 host part
  • subnet part: 同一個 subnet 內有共同的 high order bit
  • host part: 剩下自己的 low order bit

Subnets#

• subnet 中，我有 devices 可以互相連結，不需要使用 router

• 我們使用 CIRD (Classless InterDomain Routing) protocol 作為 subnet 的協議，format 是

$$\texttt{a.b.c.d/x}$$

• $\texttt{a, b, c, d}$ 是四個 0~255 的 address
• $\texttt{x}$ 則是 # bits in subnet portion
• $\boxed{\texttt{200.23.16.0/23}}$ 為例

$$\underset{\text{subnet part}}{\underbrace{\texttt{11001000 00010111 0001000}}}\underset{\text{host part}}{\underbrace{\texttt{0 00000000}}}$$

DHCP#

• Dynamic Host Configuration Protocol，是這些裝置 ip 配置的方法
  • allow reuse of ip address
  • 可以 dynamic allow adding in the network
• 有以下的動作，大略流程是先找到自己 subnet 裡面的 DHCP 然後由 DHCP server 提供 IP address
  • host broadcasts DHCP discover msg [optional]
  • DHCP server responds with DHCP offer msg [optional]
  • host requests IP address: DHCP request msg
  • DHCP server sends address: DHCP ack msg

• 通常是在 port 67 listen to DHCP server, server 用 port 68 listen to client

Hierarchical addressing#

假設 ISP 有 $\texttt{200.23.16.0/20}$ 這個 block，那他可以把自己的 subnet 分成 8 個 blocks 分別是 $\texttt{200.23.16.0/23} \to \texttt{200.23.30.0/23}$

在 normal 情況下我們可以把 routing 存起來，告訴 internet 把 $\texttt{200.23.16.0/20}$ 全都傳給我

如果我想把其中某個 $\texttt{200.23.18.0/23}$ 轉存到另一個 ISP 身上，我們會 DHCP server 加上 or $\texttt{200.23.18.0/23}$ 的訊息

• 當有 Internet msg income 的時候 longest prefix 就派上用場了，因為必須要 longest prefix 才是正確要送的，會送往 ISPs-R-Us 而不是 Fly-By-Night-ISP

Assigned Names and Numbers) 索取，ICANN 同時也管理所有 DNS 的 policy

NAT#

全稱 Network Address Translation，為了解決「虛擬 IP」的問題，實體 IP 數量有限

• Port Number: 可以作為 application 對應的 process 的參照，但 NAT 這裏把 port number 拿來解決 address transformation（通常不跟慣用 application port number 重疊）
  • port number 總共有 16 bit 可以支援 $2^{16}$ 個 address
• NAT 讓 local 的一群 host 共用同一個 public 的 IPv4 address，內部再去細分，減輕 ISP 壓力
  • 外部是搜尋不到 10.0.0.1 這個 address 的
  • NAT 會把虛擬 IP，根據裡面的對應表，換成他真實的實體 IP

• 也可以增加安全性，因為內部看不到實體 IP
• NAT 會做到以下幾件事
  • 對於 outgoing datagrams 做 IP replace
  • remember 對應關係 in NAT translation table
  • 對於 incoming datagrams 做 IP replace

IPv6#

由於 IPv4 的資源 32-bits 已經被用完，因此要開發新的規格

• 加速 forwarding
• 在 best effort 的基礎上增加一些 QoS 控管
• 不允許 datagram 的 fragmentation，會 refuse，由 upper layer 做這件事。

IPv6 format#

1. 可以做 priority 的分類在 traffic class 裡面（但在 IPv6 裡面並沒有量化）
2. flow label 讓同一個 connection 前後 packet 處理得更一致，讓速度增快
3. next header
4. 刪除了 checksum 的部分，教給 upper layer

Tunneling#

IPv4 到 IPv6 之間的轉換不是一件簡單的事，因為要 globally 的達成這件事不簡單，因此採用了 Tunneling 的技巧

• IPv6 的 packet 只要在前面加上一個 IPv4 header 就可以送出去了

• border router 要可以做到 6 to 4 或是 4 to 6 的轉換，這樣就可以傳輸出去
  • border 會把 source 跟 destination 都改成 border 的 router

Forwarding#

一個基礎的 flow table 會有 match column 跟 action column，在 SDN 裡面 Header Fields 代表一個 flow，通常會做到四個動作

• Match: 看看他的 Pattern 對應到哪個 row
• Actions: 常見有
  • Forward：轉發到某個實體連接埠 (Port)。
  • Drop：丟棄封包（這就是防火牆的功能）。
  • Modify：修改封包內容（例如修改 IP 或 MAC，這就是 NAT 的功能）。
  • Send to Controller：這點最重要。如果交換機不知道怎麼辦，就把封包丟給中央的「控制器」(Controller) 決定，這就是 SDN 的精隨。
• Priority: 在兩個 pattern 都 match 的時候要做 priotrity judge
• Counters: Bytes, packet 數量，用來監測

---

Back to the content

NTU Computer Networking

2025 Fall

← Back to the content

---