---
# System prepended metadata

title: IETF 0110

---

# IETF 0110

---

[TOC]

---

- https://www.cnblogs.com/unnling/p/14470833.html#3-%E4%BC%A0%E8%BE%93%E5%B1%82
- https://sls.weco.net/node/10675
- https://drive.google.com/drive/u/1/folders/1mheQ-3KEk0AViXMWOmNoj8sFwgiop3y8

---


## Chapter 3

### Pipelined protocols
#### Go-Back-N
- **Sender**
    - N unacked pkt in pipeline
    - Timer for oldest unacked
- **Receiver**
    - sends *cumulative ack*

#### Selective Repeat
- **Sender**
    - N unacked pkt in pipeline
    - Timer for each unacked
    - Data from above
        - if next available seq # in window, send pkt
- **Receiver**
    - sends *individual ack*
- **Seq# & Window Size**
    - More safe: Seq# * 2 >= window size


### TCP
#### Overview
- Point-to-point
- Reliable, in-order byte stream
- Pipelined
- Full duplex data
- Connection-oriented
- Flow controlled

#### TCP Segment Structure
![](https://i.imgur.com/tn7Fch1.png =450x)
- **Seq#**: First byte in segment's data
- **ACK#**: Seq# of next expected byte, Cumulative

#### TCP Timeout
- **SampleRTT**: Real RTT (ignore retransmission)
- **EstimatedRTT**: **`e = (1-a)*e + a*s`** (exponential)
- **DevRTT**: **`d = (1-b)*d + b*|s-e|`** (safety margin)
- **TimoutInterval**: **`t = e + 4*d`**

#### TCP Fast Retransmission
- **If** receive 3 ACKs for same data
- **Then** resend unacked segment with smallest seq#

#### TCP Flow Control
- **Receiver controls sender**
- Receiver advertise **`rwnd`**: Free buffer space


### TCP Connection Management
#### Establishing TCP Connection
- **3-way handshake** better than 2-way handshake

![](https://i.imgur.com/EuOZX4k.png =450x)

#### Closing TCP Connection
![](https://i.imgur.com/4WbjAOJ.png =450x)


### TCP Congestion Control
#### Overview
- "Too many sources sending too much data too fast for **network** to handle"
- **Cost of congestion**
    - More retrans for given goodput
    - Unneeded retrans
    - Upstream trans capcity wasted due to pkt dropped

#### AIMD
- **AIMD** (additive increase / multiplicative decrease)
    - **Additive inc**: **`cwnd += 1 MSS`** each RTT
    - **Multiplicative dec**: **`cwnd *= 0.5`** each loss
- **Rate**: **`rate = cwnd / RTT`** (roughly)

#### Slow Start
- **Init**: **`cwnd = 1 MSS`**
- **Each RTT**: **`cwnd *= 2`**

#### TCP Tahoe
- A **congestion** method
- **Timeout or 3 same ACKs**: **`ssthresh = cwnd / 2`**, **`cwnd = 1 MSS`**
![](https://i.loli.net/2021/03/02/vUxVfd4kqZwlacS.png =500x)

#### TCP Fairness
- **Fairness & UDP**
    - No congestion control
    - Constant rate
    - Tolerate pkt loss
- **Fairness & parallel TCP connections**
    - Parallel connections

#### ECN
- **Explicit Congestion Notification**
- **Network-assisted** congestion control
- Two bits in IP header (**ToS field**) marked by network router to indicate congestion


## Chapter 4

### Network-Layer Overview
#### Functions
- **Forwarding**:
    - Move packets from router input to appropriate router output
- **Routing**:
    - Determine route taken by packets from source to destination

#### Planes
- **Data Plane**: *(forwarding)*
    - Local, per-router function
- **Control Plane**: *(Routing)*
    - Network-wide logic
    - **Traditional routing algorithms** in each routers
    - **SDN** (Software-defined networking) in remote servers

#### Service Models
![](https://i.imgur.com/bHQczk4.png =450x)
- **ATM**: Asynchronous Transfer Mode
    **CBR**: Constant Bit Rate, **VBR**: Variable BR
    **ABR**: Average BR, **UBR**: Unspecified BR


### Router
#### Architecture
![](https://i.imgur.com/4yMaXmR.png =450x)

#### Input Ports
![](https://i.imgur.com/Y9clPqi.png =400x)
- **Decapsulation**
    - **Physical** -> **Data Link** -> **Network**
- **Decentralized switching**
    - **Destination-based forwarding**
        - Based only on **dest IP address** *(traditional)*
    - **Generalized forwarding**
        - Based on any set of **header field values**
- **Longest Prefix matching**
    - IP address
    - **TCAMs** (Ternary content addressable memories)
        - **Content addressable**: get address in 1 clock

#### Switching Fabrics
- ![](https://i.imgur.com/vBQNBhi.png =400x)
- **Bus contention**: switching speed limited by bus bandwidth
- **Input Port Queuing**
    - Delay & loss due to **input buffer overflow**
    - **HOL** (Head-of-the-Line) Blocking:
        - Many pkts want to go to same port
- **Output Port Queuing**
    - Delay & loss due to **output buffer overflow**

#### Output Ports
![](https://i.imgur.com/DXEzjXi.png =400x)
- **Encapsulation**
    - **Network** -> **Data Link** -> **Physical**
- Datagram (packets) can be **lost due to congestion, lack of buffers**
- **Priority scheduling**: who gets best performance, network neutrality

#### Scheduling
- **FIFO (first in first out) Scheduling**
- **Priority Scheduling**
    ![](https://i.imgur.com/CTspG4F.png =220x)![](https://i.imgur.com/wnNE2R9.png =220x)
- **Round Robin (RR) scheduling**
- **Weighted Fair Queuing (WFQ)** (generally RR)
    ![](https://i.imgur.com/6fbaF1O.png =250x)

### IP: Internet Protocol
#### IP Datagram Format
![](https://i.imgur.com/YI3bmBZ.png =450x)

#### Fragmentation & Reassembly
- **MTU**: max transfer size
![](https://i.imgur.com/rcqKEnC.png =280x)


### Network Address Translation
- **Subnet**:
    - Device interfaces with **same subnet part of IP address**
    - Can physically reach each other **without intervening router**
- **CIDR** (Classless InterDomain Routing):
    ![](https://i.imgur.com/tULz1Ye.png =250x)
- **How Host Get IP Address?**
    - Hard-coded
    - DHCP

#### DHCP
- **DHCP** (Dynamic Host Configuration Protocol)
- **Client-Server Steps**:
    - [S＜C] **"DHCP discover"** msg *(Optional)*
    - [S＞C] **"DHCP offer"** msg *(Optional)*
    - [S＜C] **"DHCP request"** msg
    - [S＞C] **"DHCP ack"** msg
- **DHCP Server Return More Info**:
    - Address of **first-hop router** for client
    - Name and IP address of **DNS sever**
    - **Network mask**

#### ICANN
- **ICANN** (Internet Corporation for Assigned Names and Numbers)
- **Abilities**:
    - Allocates addresses
    - Manages DNS
    - Assigns domain names, resolves disputes
- **An ISP can get block of addresses**

#### NAT
- **NAT** (Network Address Translation)
- **NAT Router Must ...**:
    - **Replace** outgoing datagrams data fields
    - **Remember** in NAT translation table)
    - **Replace back** outgoing datagrams data fields
- **Controversial**:
    - Change ports which **not in Network layer**
    - Address shortage should be solved by **IPv6**
    - Violates end-to-end argument (i.e. **P2P app**)
    - **NAT traversal**: client wants to connect to server behind NAT?


### IPv6
#### IPv6 Datagram Format
![](https://i.imgur.com/qPxX5mB.png =300x)
- **Fixed-length 40 bytes header**
- **No fragmentation** allowed
- **Priority**: Priority among datagrams in flow
- **Flow Label**: Datagrams in same flow
- **Next Header**: Upper layer protocol for data
- **No checksum**
- **Options**: outside of header, indicated by "**Next Field**"
- ICMP -> **ICMPv6**
    - Additional msg types: **“Packet Too Big”**
    - Multicast group management functions

#### TRansition from IPv4 to IPv6
- **Tunneling**:
    - **IPv6 datagram** carried as payload in **IPv4 datagram** among **IPv4 routers**

![](https://i.imgur.com/1ruihg2.png =400x)


### Generalized Forwarding and SDN
#### OpenFlow Data Plane Abstraction
- Each route contains a **flow table**
- **Flow**: Defined by header fields
- **Generalized Forwarding**: Simple packet-handling rules
    - **Pattern**: Match packet
    - **Actions**: Do for matched packet
    - **Priority**: Disambiguate overlapping patterns
    - **Contents**: #Bytes and #packets
- **Flow Table Entry**:
    - **Rule**, **Action**, and **Stats**
    ![](https://i.imgur.com/X0KkrUs.png =400x)
    - **Destination=based Forwarding**
    - **Firewall**
    - **Match + Action**: Unifies different kinds of devices
- Forwarding tables & flow tables **computed in control plane**


## Chapter 5
### Routing Algorithm
#### Classification
- **Global**: **Link state** algorithm
    **Decentralized**: **Distance vector** algorithm
- **Static**: Router change slowly
    **Dynamic**: Router change quickly

#### Link State Algorithm
- **Dijsktra** Algorithm
    - **Priority queue** $Q$ for $v$ with $d[v]$ as key
    - While $Q$ is not empty
        - Extract $v$ with **min** $d[v]$ from $Q$
        - For each **adjacent relaxable vertex** in Q
            - **Relax**
            - **Change priority**
- **Complexity** (**n** nodes)
    - **O(n^2)**, more efficient version **O(nlogn)**
- **Oscillations** possible:
    - Support link **cost equals** amount of carried traffic
    - Current flow **all go to** the best path

#### Distance Vector algorithm
- **Bellman-Ford** equation *(dynamic programming)*
    - ![](https://i.imgur.com/SLMXaNK.png =230x)
    - ![](https://i.imgur.com/Jz5Vhtz.png =400x)
    - From time-to-time, each node **sends its own distance vector** estimate to neighbors
    - Generally, the estimate **Dx(y) converge to the actual least cost dx(y)**
- **Iterative** & **Asynchronous** & **Distributed**
- For **each Node**
    - **Wait** for change in local cost or msg from neighbor
    - **Recompute** estimates
    - **Notify** changed distance vector
- **Link cost change**
    - **Good news travels fast**
        **bad news travels slow**
        - Long path would not be spread out
    - **Poisoned reverse**
        - Set bad path to **infinite**

#### Comparison
- **Message Complexity**
    - **LS**: **O(nE)** msgs xsent
    - **DV**: between **neighbors** only
- **Speed of Convergence**
    - **LS**: **O(n^2)** time with **O(nE)** msgs
    - **DV**: varies: **loops**, **count-to-infinite** (routing loop)
- **Robustness**
    - Advertise **incorrect link/path cost**
    - **LS**: each node computes **only its own table**
    - **DV**: error **propagate thru network**


### Intra-AS Routing: OSPF
#### AS
- **AS**: Autonomous System
    - Aggregate routers into regions
- **Intra-AS Routing**
    - All routers in AS must run **same** intra-domain protocol
    - **IGP** (Interior gateway protocols)
        - **RIP** (Routing Information Protocol)
        - **OSPF** (Open Shortest Path First)
        - **IGRP** (Interior Gateway Routing Protocol)
- **Inter-AS routing**
    - Learn which dests are **reachable** through which AS
    - **Propagate reachability** in own AS

#### RIP ==TODO==

#### OSPF
- **OSPF** (Open Shortest Path First)
- **Link state** algorithm used
- Router floods **OSPF link-state advertisements** to all other routers in entire AS
- **IS-IS** protocol essentially same as OSPF
- **Security**: all OSPF msgs authenticated
- **Multiple same-cost** paths allowed
- **Multiple cost metrics** for different **ToS**
- Integrated uni- and **multi-cast** support
    - **Multicast OSPF** (MOSPF) uses same topology data base as OSPF
- **Hierarchical** OSPF
    - Two-Level Hierarchy: **local area** & **backbone**
    - **Area border routers**: summarize distances in own area
    - **Backbone routers**: run OSPF routing limiyed to backbone
    - **Boundary routers**: connect to other AS

### Inter-AS Routing: BGP
#### BGP
- **BGP**: Border Gateway Protocol
    - De facto inter-domain routing protocol
    - **Distance Vector** algorithm used
    - **eBGP**: Internal BGP
        - Obtain subnet reachability info 
    - **iBGP**: External BGP
        - Propagate reachability info
- **BGP Sessions**
    - Two BGP routers (“peers”) **exchange BGP msgs** over **semi-permanent TCP connection**

#### Path Attributes
- Two important:
    - **AS-PATH**: List of **ASes through which prefix** advertisement has passed
    - **NEXT-PATH**: Indicates **specific internal-AS router to next-hop** AS
- **Policy-based routing**
    - **Import policy** to accept/decline path
    - Determine **whether to advertise path** to other 
    - **Provider Networks**
        - **Dual-Homed**: attached to two provider networks
        - **Policy to enforce**: not to go through clients to go different provider networks

#### BGP Messages
- **OPEN**: opens TCP connection to remote BGP peer and authenticates sending BGP peer
- **UPDATE**: advertises new path (or withdraws old)
- **KEEPALIVE**: keeps connection alive in absence of UPDATES & ACKs OPEN request
- **NOTIFICATION**: reports errors in previous msg & close connection

#### Hot Potato Routing
- **Fast transfer through ASes** to other ASes
    - choose local gateway that has least intra-domain cost 

#### Inter and Intra
- **Inter-AS**: admin wants **control over** its net
    **Intra-AS**: **single admin**, so no policy decisions needed
- **Scale**: Use **hierarchical** routing saves table size, reduced update traffic
- **Inter-AS**: **policy** may dominate over performance
    **Intra-AS**: can focus on **performance**


### SDN
- **SDN**: Software Defined Networking
- **Logically centralized control plane**
    - Easier **management**
    - Table-based forwarding (OpenFlow API) allows **“programming” routers**
    - **Open** (non-proprietary) implementation of control plane
- **Traffic engineering: difficult traditional routing**

#### SDN Perspective
- **Data plane switches**
- **SDN controller (network OS)**
- **Network-control apps**
![](https://i.imgur.com/yJazPNu.png =450x)

#### OpenFlow
- Operates between controller, switch
- **TCP** used to exchange messages
    - Optional **encryption**
- **OpenFlow Msgs**
    - **controller-to-switch**
        - **features**
        - **configure**
        - **modify-stat**
        - **packet-out**
    - **asynchronous** (**switch-to-controller**)
        - **packet-in**
        - **flow-removed**
        - **port status**
    - **symmetric** (misc)

#### Other Controller
- **OpenDaylight (ODL)**
![](https://i.imgur.com/oMsmwlY.png =300x)
- **ONOS**
![](https://i.imgur.com/VJJjrmr.png =300x)


### ICMP
- **ICMP**: Internet Control Message Protocol
- Used by hosts & routers to communicate network-level information
- **Traceroute**
    - TTL in IP datagram segment


### SNMP
- Managed devices contain managed objects whose  data is gathered into a **Management Information Base** (**MIB**) 
![](https://i.imgur.com/1OFZl78.png =450x)
![](https://i.imgur.com/BvsMGmY.png =450x)
![](https://i.imgur.com/q5KjaH6.png =450x)


