# 計算機網路: Ch4 Network Layer: Data Plane

建議在 [HackMD](https://hackmd.io/@Toast1001/B1ipsZGEkl) 上面查看效果會更好哦~

:::warning
**2023 考古題考點** :
- DHCP
- Nat
- Bacher-Banyan Network
- Queueing
:::

## Overview
- **Two key functions**:
- **Forwarding**: move packets from a router's input link to appropriate router output link
- **Routing**: determine route

- **Data Plane**:
- Local
- Use on **forwarding**
- **Control plan**:
- **Network-wide** logic
- Use on **routing**
- 2 control-plane approaches
- **Traditional routing algorithms**
- Implemented in routers
- Local view
- **Software-defined networking (SDN)**
- Implemented in remote servers
- Global view
- Remoted controller computes, install **forwarding tables in routers**

- **Network service model**:
- For **individual datagram**
- Guaranteed delivery
- Guaranteed delivery with less than 40 msec delay
- For **flow of datagrams**
- In-ordeer datagram delivery
- Guaranteed minimum bandwidth to flow
- Guaranteed stable **packet gap**
- **Best-effort service**
- No guarantees on:
- Successful datagram delivery to destination
- Timing or order of delivery
- **Bandwidth** available to end-end flow
- **Simplicity of mechanism**
- Allowed Internet to be widely deployed adopted
- Sufficient **provisioning of bandwidth** allows performance of real-time applications
- Replicated, application-layer distributed services
- Congestion control

## What's inside a router
### Router architecture overview

| Routing Processor | Switching fabric |
| -------- | -------- |
| Control plane | Data plane |
| **Software** | **Hardware** |
| Use to **Routing** | Use to **forwarding** |
| Operates in msec timeframe | Operates in nanosecond timeframe |


### Input port functions
- **Physical layer**:
- Bit-level reception
- Line termination
- **Link layer**:
- Ethernet
- **Decentralized switching**:
- Lookup forwarding queueing
- Usingheader field values, lookup output port uswing
- **Goal**: complete input port processing at **line speed**
- **Input port queueing**: if datagrams arrive faster than forwarding rate into switch fabric

### Switching fabrics
- Transfer packet from input link to appropriate output link
- **Switching rate**: rate at which packets can be transfer from inputs to outputs

#### 3 major types of switching fabrics
- **Memory**:
- Traditional computers wit switching under direct control of CPU
- Packet copied to system's memory
- Speed limited by memory bandwidth
- **2 bus crossing** per datagram

- **Bus**:
- Datagram from input port memory to output port memory via a **shared bus**
- **Bus connection**: switching speed limited by **bus bandwidth**
- Use **NFE processor** to replace passing CPU memory

- **Interconnection newwork (Crossbar)**:
- **Multistage switch**: $n\times n$ switch from **multiple stages** of smaller switches

- **Crossbar Switch Fabric**
- **Cisco CRS router**:
- Basic unit: 8 switching planes
- Each plane: 3-stage interconnection newwork
- Up to 100's Tbps swithcing capacity
- **Banyon Network**:
- **Basic element**:
- **Larger** input tag go down
- **Large Banyon Network**:
- It can change input port to appropriate output port
- Much greater likelihood of **collisions**

- **Trap Network**:
- 到相同desitned-port 的 packets，僅讓一個 packet 通過
- **Shuffle Network**:
- 讓排序最接近的packets，盡量分開，避免發生internal collisions
- e.g. 0 1 2 3 4 5 6 7 8 -> 0 5 1 6 2 7 3 8 4

- **Batcher Network**:
- Use for **sorting**
- Sorting can reduce collisions

- **Batcher-Banyan network**:

### Queueing
- **Input port queueing**:
- When switch fabric **slower** than input ports combined -> **queueing** may occur at input queues
- **Head-of-the-Line (HOL) blocking**:
- 前面塞車導致後面無法做 forwarding
- 可以透過調整順序解決
- **Output port queueing**:
- **Buffering** when arrival rate via switch exceeds output line speed
- Datagrams can be lost due to **congestion**, lack of buffer
- **Scheduling discipline**
- chooses among queued datagrams for transmission
- **Priority scheduling**

### Buffering
#### How to buffering
- **Recent recommendation**:
- $\frac{RTT\cdot C}{\sqrt{N}}$
- $C$: link capacity
- $N$: the number of flows
- Too much buffering can increase **delay**
- Particularly in home routers
- Long RTTs: poor performance for realtime apps
- **Delay-based congestion control**: keep bottleneck link just full enough but no fuller

#### Buffer management
- **Drop**:
- Which packet to add drop when buffers are full
- **Tail drop**: drop arriving packet
- **Priority drop**: drop on priority basis
- **Marking**:
- Which packets to mark to signal congestion
- ECN, RED

### Packet scheduling

| Methods | Priority | Cycle | Weighted | Queue |
| -------- | -------- | -------- | -----| ------ |
| **FCFS** | No | No | No |  |
| **Priority** | Yes | No | No |  |
| **RR** | Yes | Yes | No |  |
| **WFQ** | Yes | Yes | Yes |  |

#### First come, first served(FCFS)
Packets transmitted in order of arrival to output port

#### Priority
- Any header field can be used for classification
- High priority send first
- **FCFS** within **priority class**

#### Round robin(RR)
- Arriving traffic classified queue by class
- Server **cyclically**, repeatedly scans class queues
- Sending one complete packet from each class in turn

#### Weighted fait queueing(WFQ)
- Generalized **Round Robin**
- Each class $i$, has weight, $w_{i}$
- Weighted amount of service in each cycle = $\frac{w_{i}}{\Sigma _{j} w_{j}}$
- **Minimum bandwidth guarantee** (per-traffic-class)

## IP: the Internet Protocol
### Internet
- **Path-selection algorithms**:
- Routing protocols
- SDN controller
- **IP protocol**:
- Datagram format
- Addressing
- Packet handling conventions
- **ICMP protocol**:
- Error reporting
- Router "signaling"

### IP Datagram Format
- **Overhead**:
- 20 bytes of TCP
- 20 bytes of IP

### IP addressing
#### Introduction
- **IP address**: **32-bit** identifier associated with each host or router **interface**
- **Interface**: connection between host/router and physical link
- **Router**: multiple interfaces
- **Host**: 1 or 2 interfaces

#### Subnets
- **Definition**:
- Device interfaces that can physically reach each other **without paswsing through an intervening router**
- Each **isolated** network is called **subnet**
- **IP addresses structure**:
- **Subnet part**:
- High order bits
- Devices in same subnet have common subnet part
- **Host part**:
- Remaining low order bits

#### Classless InterDomain Routing(CIDR)
- Subnet portion of address of arbitrary length
- **Address format**:
- $a.b.c.d/x$
- $x$ is **the number of bits in subnet portion** of address

#### How to get IP address
- How does **a host get IP address** within its network(host part of address)?
- Hard-coded by **sysadmin** in config file
- **Dynamic Host Configuration Protocol(DHCP)**:
- Dynamically get address from as server
- **plug-and-play**
- Dynamic IP address is **not stable**
- How does a **network** get IP address for itself(network part of address)?
- Gets allocated portion of its provider ISP's address space

#### Dynamic Host Configuration Protocol(DHCP)
- **UDP** based
- **Goal**: host **dynamically** obtain IP address from **network server** when it join network
- Can **renew** its lease on addresses
- Support for **mobile users** who join/leave network
- Allows **reuse** of address
- **Secnario**:

- **Overview**:

    Arriving client->DHCP server: DHCP discover
    DHCP server-->Arriving client: DHCP offer
    Arriving client->DHCP server: DHCP request
    DHCP server-->Arriving client: DHCP ACK

- **DHCP discover**:
- Client **broadcast** packet to whole subnet
- Ask **DHCP server** of the subnet offer IP address
- **DHCP offer**:
- **DHCP server** send a **unused IP address** to client
- **DHCP request**:
- Client request to DHCP server that it got the IP address
- **DHCP ACK**:
- DHCP server talk to client that it can connect to network by the IP address

#### Hierarchical addressing
- **Goal**: allow **efficient advertisement** of routing information
- **More specific routes**
- **Organization 1** moves from Fly-By-Night-ISP to ISPs-R-Us
- ISPs-R-Us now advertises a **more specific route** to Organization 1

#### Internet Corporation for Assigned Names and Numbers(ICANN)
- **Goal**: let ISP get block of addresses
- Allocated IP addresses, through 5 **regional registries(RRs)**
- Manage **DNS root zone**, including **TLD** management
#### How to get IP address ?

| Asker | Method |
| -------- | -------- |
| **Host** | Use **DHCP** |
| **Network** | Allocated by **ISP** |
| **ISP** | Allocated by **ICANN** |

### Network address translation(NAT)
- All devices have:
- **Public IP address**: use for ouside world
- **Private IP address**: use in local network
- **Advantages**:
- Just **one** IP address needed from provider ISP for all devices
- Can change ISP without changing addreses of devices in local network
- **Security**:
- Devices inside local network **not directly addressable** by outside world

- **Implementation**:
- **Outgoing datagram**:
- Source IP address(LAN) -> NAT IP address(WAN)
- Source port number(LAN) -> New new port number(WAN)
- **NAT translation table**:
- **Remember** every (source IP address, port number) to (NAT IP address, new port number)
- **Incoming datagrams**:
- NAT IP address(WAN) -> Destination IP address(LAN)
- New port number(WAN) -> Destination port number(LAN)

### IPv6
#### Motivation
- **Initial motivation**: 32-bit IPv4 address space would be completely allocated
- **Additional motivation**:
- Speed processing and forwarding
- Enable different network-layer treatment of flows

#### IPv6 datagram format
- Compare with IPv4:

| Properties | IPv4 | IPv6 |
| -------- | -------- | -------- |
| **Addresses size** | **32-bit** | **128-bit** |
| **Checksum** | Yes | No |
| **Fragmentation** | Yes | No |
| **Reassembly** | Yes | No |
| **Options** | Yes | No |

#### Transition from IPv4 to IPv6
- Not all router can be upgraded simultaneously
- **Tunneling**:
- **IPv6** datagram carried as **payload** in **IPv4** datagram among IPv4 routers
- Packet within a packet


## Generalized Forwarding, SDN
### Match + action
- **Detination-based forwarding**: forward based on **destination IP address**
- **Generalized forwarding**:
- Many header fields can determine action
- Many action possible:
- Drop
- Copy
- Modify
- Log packet

### Flow table abstraction
- **Flow**: defined y header field values
- **Generalized forwarding**:
- **Match**: pattern values in packet header fields
- **Actions**: for matched packet
- Drop
- Forward
- Modify
- Matched
- Send matched packet to controller
- **Priority**: disambiguate overlapping patterns
- **Counters**: number bytes and number packets

### OpenFlow
- **Goal**: 允許用軟體的方式遠端操縱硬體

#### Flow table entries

#### Examples

#### Abstraction
- **Match + action**: abstraction unifies different kinds of devices

| Devices | Match | Action |
| -------- | -------- | -------- |
| **Router** | Longest destination **IP prefix** | Forward out a link |
| **Switch** | Destination **MAC address** | Forward or flood |
| **Firewall** | IP address, TCP/UDP port number | Permit or deny |
| **NAT** | IP address and port number | Rewrite address and port number |

## Middleboxes
- **Definition**: Any intermediary box performing functions **apart form normal, stadard function of an IP router** on the data path between a source host and destination host
- **Initially**: proprietary hardware solutions
- Move towards **whitebox hardware** implementing open API
- Move away from proprietary hardware solution
- **Programmable local actions** via match+action
- Move towards innovation/differentiation in software
- **Network functions virtualization(NFV)**:
- Programmable services services over white box **networking, computation, storage**
- **The IP hourglass**: