# 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
- **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


#### Closing TCP Connection

### 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`**

#### 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
- **ATM**: Asynchronous Transfer Mode
**CBR**: Constant Bit Rate, **VBR**: Variable BR
**ABR**: Average BR, **UBR**: Unspecified BR

### Router
#### Architecture

#### Input Ports
- **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
- 
- **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
- **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**
- **Round Robin (RR) scheduling**
- **Weighted Fair Queuing (WFQ)** (generally RR)

### IP: Internet Protocol
#### IP Datagram Format

#### Fragmentation & Reassembly
- **MTU**: max transfer size

### 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):
- **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
- **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**


### 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**
- **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)*
- 
- 
- 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**

#### 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)**
- **ONOS**

### 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**)