# 無線網路筆記
## Chapter 3
### Principles of reliable data transfer
* 目標:想要在Transport layer達成reliable的傳輸
* 主要針對rdt_send()和rdt_rcv()設計，用以達到reliable的傳輸
### rdt1.0
* 假設無error bit跟packet loss
### rdt2.0
* 假設會有error bit，所以增加了check sum來進行檢查是否傳對
* 新增ACK&NAK，接收端回傳ACK代表傳對，回傳NAK代表有錯誤
* 傳送端在傳送之後會在Wait for ACK or NAK的狀態，若接收到NAK則會重傳，直到接收到ACK才會回到Wait for call的狀態
### rdt2.1
* 為了解決rdt2.0無法確認ACK/NAK有沒有傳錯，所以當傳送端無法辨識接收端的ACK/NAK時會重傳資料，但這樣有可能導致接收端取得重複的資料
* 為了避免接收端取得重複的資料，在封包新增了"Sequence Number"來檢查是否重複，因為採用stop and wait所以Sequence Number只需要0和1就夠了，若有重複接收端則會丟棄封包
#### sender
#### receiver
### rdt2.2 A NAK-free protocal
* 基本上跟rdt2.1一樣但不再用NAK了，只用ACK
* ACK新增number
### rdt3.0
* 假設有error bit跟packet loss的情況
* 假如packet loss的話，因為傳送端採用stop and wait沒有接收到ACK，所以會卡住
* 因此傳送端新增"Count Donw Timer"，在時間內要接收到回覆，若Time out就會重傳，用以解決上述問題
* 若check sum檢查錯誤不會重傳，等待time out時間到再重傳，避免多次重傳
#### no loss
#### packet loss
#### ACK loss
* 不收封包但還是要回覆ACK給傳送端
#### Premature timeout
* 不收封包但還是要回覆ACK給傳送端

### Performance of rdt3.0
* 傳資料的時間佔總傳輸的比例

### Pipeline protocal
* 為了改善stop and wait的效率問題
* 一次送出好幾個封包
* Sequence number遞增
* 傳送端跟接收端都有buffer
#### stop and wait V.S. Pipeline
#### Performance of using pipeline

### Pipeline protocal "Go-Back-N" sliding window protocal
* k-bits的sqeunce number在封包裡
* 但window最大只能用到2^k-1 bits
* Cumulative ACK:ACK(n)代表n之前的資料都確定有傳輸成功，所以沒收到ACK(n-1)也沒差
* 若在window最前面的資料time out，則會重傳所有資料，這也是此協定叫Go-Back-N的原因

### FSM of Go-Back-N

#### sender

#### receiver
* 按照順序進來的才會收

#### example

### Pipeline protocal "Selective Repeat"
* 收到的封包個別回傳ACK，並且暫存在Buffer裡，等封包都補齊才會傳到應用層
* 傳送端只需要重傳錯誤的封包就好
* 每個封包都有自己的timer
* 傳送端與接收端都有一個相同大小的window最大為2^(k-1)

#### sender and receiver

#### example

#### Selective repeat:dilemma
* 可能重複接收相同的資料
* 將window size切成兩半就可以解決序號重疊的問題，這也是為甚麼window size最大只能為2^(k-1)

### TCP segment structure

#### TCP sequence# and ACKs

#### TCP RTT and Timeout
* Timeout的時間太長或太短都不好，但在設定合適的Timeout之前我們必須先知道RTT，所以採用統計的結果，也就是"SampleRTT"來當作合適的RTT
* 但因為想要讓SampleRTT平滑一點，所以用以下公式來平滑SampleRTT會計算出"EstimatedRTT"
* 可是我們不能直接把EstimatedRTT當作Timeout的時間，要加上一個"safety margin"(4個標準差)
* 通常將EstimatedRTT+4 * DevRTT(標準差)當作Timeout

#### TCP sender events

#### TCP retransmission scenarios
##### lost ACK
##### premature timeout
##### Cumulative ACK
* Cumulative ACK的作用，所以前面的ACK lost也沒關係

#### Fast retransmission
* 如果接收端連續收到三個重複的ACK的話會直接重傳，不需要等到timeout

#### TCP flow control
* 計算buffer剩餘的空間也就是"RecWindow"，傳送端最多只能傳送跟RecWindow一樣大的資料

#### Connection Management
* 連線建立
1. Client端傳送SYN為1的封包做為連線請求
2. Server端接收SYN並回覆一個SYNACK
3. Client端接收SYNACK並回覆ACK
* 連線中斷
1. Client端發送FIN標頭為1的封包
2. Server端接收到FIN回傳ACK，此時就完成關閉了，再傳送一個FIN告訴client端已經完成關閉了
3. Client啟動一個count down timer，並回傳ACK，timer結束後就會關閉連線
* TCP life cicle
#### Causes/costs of congestion
1. 完美的情況，沒有loss
2. 當有loss的時候input就包含重傳所以output的資料一定小於input
3. premature的情況，資料重傳>>
.
* 網路壅塞的例子

#### TCP Congestion control
1. AIMD(Additive Increase Multiplicative Decrease)
* AI線性增加，每次加1
* MD如果發生loss event(接收三個重複的的ACK或Timeout)就減半或減至1
2. Slow start
* 剛建立連線TCP的initial transmission rate太低了
* 因此讓傳輸速度已指數的速度上升，每次傳輸cwnd就double，直到第一次event loss之後cwnd有兩種情況
1. 若為3-duplicate-ACKs會減半，並改用線性增長
2. 若為Timeout會直接變回1MSS，再繼續用指數增長，直到到達threshold後改用線性增長
3. Threshold的值為發生loss event前一瞬間的cwnd的一半
* 小於Threshold -> slow start 指數增加
* 大於Threshold -> congestion-avoidance 線性增加

#### TCP throughput

#### TCP fairness
* 發生event loss的時候，彼此傳輸的頻寬大小會越來越靠近

## Chapter 4

### Network layer
* 網路層的目的將傳輸層的Segement從傳送端傳到接收端
* 將傳輸層的Segement包裝成datagram(packet)
* 確認沒問題去除網路層標頭再傳送到傳輸層
* 路由器:檢查packet的標頭，決定要傳輸到哪裡

#### Key Network-Layer Functions
* Forwarding (Data plane): 將packet從input傳送到恰當的output (轉機)
* Routing (Control plane): 決定封包從起點到目的走的路徑 (行程安排)
* 傳統的Routing algorithms
* Software-defined networking: 由遠端的控制中心來決定路由的路徑

#### Data plane
* Local
#### Ｃontrol plane
* Network-wide logic

### Router Architecture Overview
* 執行路由演算法
* RIP
* OSPF
* BGP
* Forwarding
### Input port function
* Line termination: 實體網路線
* Data lin processing: 解封裝處理標頭
* 網路層 Decentralized switching (分散式交換):
* 根據封包的目的地，查看forwarding table尋找合適的輸出
* Destination-based forwarding: forward based only on destination IP address (traditional)
* Generalized forwarding: decision is not based on the destination address.

### Switching fabrics
* Memory
* Cross bar
* Bus

#### Switching Via Memory
* 將封包複製到memory
* 記憶體的頻寬會限制處理的速度

#### Switching Via Bus
* 從輸入的memory到輸出的memory
* 透過一個Bus來交換
* Bus contention: 交換的速度被Bus的頻寬限制

#### Switching via interconnection network
* 為了解決Bus競爭頻寬的問題
* Banyan network: 切成很多小的block，競爭就變少了
* Advanced design: 把Datagram切成比較小的cell

### Output ports
* Buffer: 當輸出的速度小於輸入的速度就會產生queueing，可能導致packet lost.
* Scheduling: 決定packet誰先誰後的規格

### Queueing
* Queueing delay
* Packet loss
#### Output queueing

#### Input queueing
* 線路傳輸的速度比資料進來的速度還慢的時候會產生queueing
* Head of the line blocking: 前面的datagram卡住後面的datagram移動

### Scheduling mechanisms
* Scheduling: 選擇要傳送的packet
* FIFO scheduling: send in order
* 當Queue滿了有以下discard policy
* tail drop: 丟掉來進來的packet
* priority: 根據優先度來決定drop的packet
* random: 隨機丟棄
### Scheduling policies
#### Priority scheduling
* sent priority最高的packet
* 有很多class，每個class的priority都不一樣
#### Round Robin (RR) scheduling
* 有很多class輪流sent
### Weighted Fair Queuing
* 每個cycle都會計算權重，根據權重來決定sent哪個packet

### IP datagram format
* IP protocol version: 4bits, ipv4,ipv6
* Header length:表示封包有幾列，以下範圍為5
* Type of service
* Length:表示整個datagram的長度
* For fragmentation and reassembly
* 16-bit ID: 表示封包序號
* flag: 3bits
* fragment-offset: 13bits
* Time to live: 每經過一個hop就會減1
* Upper layer: 看採用上層的什麼協定UDP or TCP
* Check sum
* Source IP
* Destination IP

### IP fragmentation, reassembly
* 因為link有Maximum Transmission Unit，所以要將一個比較大的封包切成幾個比較小的封包，最後再送達目的地之前重組
* 16-bit ID用來辨別是不是同個packet的fragmentation
* 每個封包都有20Byte的標頭
* offset必須為8的倍數

### IP addressing: introduction
* IP address: 32bits的辨別碼，就像地址一樣
* Router有很多interface，每個interfaces有不同的ip address
* 分成部分，8bits為一部分

#### Subnet
* subnet part of ip會一樣
* 不需要Router也可以互相溝通

#### CIDR(Classless InterDomain Routing)
* 23代表被用來當作subnet part的bit數

### DHCP: Dynamic Host Configuration Protocol
* IP由DHCP server來分配給host
* DHCP步驟
1. DHCP discover: Host用廣播來搜尋DHCP server
2. DHCP offer: DHCP server提供可用的ip給Host
3. DHCP request: 向網路發送一個DHCP Request廣播封包，告訴所有DHCP伺服器它將指定接受那一台伺服器提供的IP位址。
4. DHCP ack: 當DHCP伺服器接收到客戶端的DHCP Request之後，會客戶端發出一個DHCK Ack回應，以確認IP租約的正式生效。
* 其他DHCP也可以分配的資訊
* Default Gate way
* 子網路遮罩
* DNS server
### Hierarchical addressing
* 子網路切割
* 可以分給更多機構使用
* 更靈活使用
* 下面的情況要傳給200.23.18.0/23的這段 (Longest prefix matching)
* ICANN:網路ip分配的機構
* 分配address
* 管理DNS
* Assign domain
### NAT (Network Address Translation)
* 內部的ip都會轉成一個對外的ip
* Motivation:
* 節省ip的使用量
* 提升安全性
* Implementation
1. outgoing datagrams:將 source(IP, port#) to NAT(IP, port#)
2. remember:用一個translation table紀錄，外部傳進來的時候才知道要傳給內部哪個Host
3. incoming datagrams:NAT(IP, port#)查表找source(IP, port#)

### IPv6
* 為了解決IPv4不夠用的問題
* 固定長度為40Byte = 4+4+16+16
* 不能切割packet
#### IPv6 Header
* Version: 4bits, IPv4 or IPv6
* Priority: 8bits,決定packet服務的優先權
* Flow label: 用來辨別相同的datagrams
* Payload len: Data的長度
* Next header: TCP or UDP
* Hop limit: Time to live，每經過一個路由會-1
* Source address: 128bits = 16Byte
* Destination address: 128bits = 16Byte
* Change from IPv4
* Checksum: 被移除了，處理速度會變快
* Options: 被移除了，如果真的需要會記錄在Next Header
* ICMPv6: 新版本的ICMP
#### Transition from IPv4 to IPv6
* no “flag days” -> IPv4 不能就這樣直接不見，設備成本很高
* 利用Tunneling來進行IPv4跟IPv6的溝通
* 把IPv6包裝成IPv4的封包

### Generalized Forwarding and SDN
* flow table 由logically centralized routing controller 生成

#### OpenFlow data plane abstraction
* flow 定義在標頭
* generalized forwarding: 簡易的封包處理規則
* Pattern: 用來match封包裡的資訊
* Action for matched packet
* Drop
* Forward
* Modify
* Send to controller
* Priority: Pattern重疊時，利用優先度決定
* Counters: #bytes and #packets

#### OpenFlow abstraction
* Router
* match: longest destination IP prefix
* action: forward out a link
* Switch
* match: 目的地Mac位址
* action: forward or flood(?)
* Firewall
* match: IP address 跟 port
* action: 允許或阻斷
* NAT
* match: IP addess跟port
* action: 內部的ip跟port轉換成對外的ip跟port
#### Examples
* Flow Table Entries
* Destination-based forwarding
* Firewall
* Switch forwarding