# Computer Networks - Final Notes
```
[final exam]
It's up on 1/09, Thursday, starting 10:20am. There'll be no lecture on 1/08. Use the time wisely preparing the exam.
An additional room is again reserved to ensure the desk space won't be cramped. Same, Team #1-8 will sit in BL-212 and Team #9-16 in BL-215.
The exam scope is: ch3: 3.5-3.7; ch4, ch5, ch6:6.1-6.4.3, 6.6-6.7, ch7:7.1-7.2.
- Polly
```
## Chapter 3: Transport Layer
### TCP: connection-oriented transport
#### Advantages
1. Reliable: in order byte stream, without msg boundaries
2. Pipelined: **TCP congestion** and **flow control** set window size
3. Full duplex data: bi-directional flow in same connection
4. 有handshaking, 有flow control => sender不會弄爆receiver
#### Structures
1. **TCP sequence number**: 一個segment裡面的第一個byte的byte編號
2. **Acknowledgements**: 就直接是對面傳過來的，他下一個期待收到的byte的sequence number，使用cumulative ACKs
##### Example
| Host A (正傳到編號42) | Host B (正傳到編號79) |
| ---------------------------- | ---------------------------- |
| Send Seq42, Ack79, SeqLen=10 | Receive |
| Receive | Send Seq79, Ack52, SeqLen=20 |
| Send Seq52, Ack99 | Receive |
#### Timing Issue
##### Round Trip Time (RTT) and Timeout
1. Timeout要比RTT大，才不會造成沒必要的重傳，但是RTT不固定
2. Timeout設太大會導致效率低落，都在等lost segment就飽了
=> 需要estimate RTT
##### SampleRTT
直接測segment傳出去到ACK傳回來的時間，sample多次算平均 => Exponential weighted moving average
$$ EstimatedRTT = (1-\alpha)*EstimatedRTT + \alpha*SampleRTT$$
$\alpha = 0.125$ 讓過去的影響沒那麼大
##### Savety Margin: DevRTT
除了用estimated rRTT之外，還是要加上一個安全範圍
DevRTT: deviation of estimating SampleRTT from EstimatedRTT
$$DevRTT = (1 - \beta)*DevRTT + \beta* |SampleRTT-EstimatedRTT|$$
$\beta = 0.25$
`TimeoutInterval = EstimatedRTT + 4*DevRTT`
#### TCP Reliable Data Transfer
##### Sender side
1. Create segment with segment # (byte number of first byte in byte stream)
2. Start Timer!
1. with expire time = `TimeoutInterval`
2. 想成之後timer會是為了oldest unacked segment
3. Timeout!
1. retransmit unack segment and restart timer
4. Ack comes!
1. segment be ACKed & update SendBase
2. (re)start timer for unacked segments | stop timer when there is no unacked segments
3. cumulative ACK => 只要有傳回新的ACK就不需要舊的ACK => 如果ACK傳回來lost了不緊張，只要receiver又有傳更新的ACK就代表他其實有收到
##### Receiver side
1. 收到in-order segments: delay 500ms 如果沒有下一個segment就傳ACK; 如果收到下一個就立刻傳ACK
2. 收到out-of-order segments: 立刻傳duplicate ACK
3. 收到的segment 可以fill the gap: 立刻傳ACK
##### TCP fast retransmit
為了不要等太久才retransmit lost packets，如果收到很多duplicate ACK那就代表中間有lost segment
=> 收連續三個duplicate ACK就直接resend unack segment (with smallest seq #) 不管timeout不timeout
##### TCP flow control
讓sender知道receiver的狀況
**rwnd** (Receive Window Size) 藏在TCP header裡，實際上是free buffer space
sender會限制in-flight data不能超過rwnd
##### TCP 3-way handshaking
=> SYN => SYNACK => ACK
- 艾莉絲: Client
- 包柏: Server
```sequence
Note left of 艾莉絲: 艾莉絲initial seq 編號x,
艾莉絲->包柏: Send SYNbit=1, Seq=x, SeqLen=1
Note right of 包柏: 包柏initial seq 編號y, 回應SYNACK
包柏-->艾莉絲: Send SYNbit=1, ACKbit=1, Seq=y, Ack=x+1, SeqLen=1
Note left of 艾莉絲: 艾莉絲回應ACK
艾莉絲->包柏: Send ACKbit=1, Seq=x+1, Ack=y+1
```
| Client A (initial seq 編號x) | Host B (initial seq 編號y) |
| ------------------------------- | ------------------------------------------------- |
| Send SYNbit=1, Seq=x, SeqLen=1 | Receive |
| Receive | Send SYNbit=1, ACKbit=1, Seq=y, Ack=x+1, SeqLen=1 |
| Send ACKbit=1, Seq=x+1, Ack=y+1 | Receive |
```flow
st=>start: closed
e=>end: Estab
listen=>operation: listen
SYNsent=>operation: SYNsent
SYNrcvd=>operation: SYNrcvd
op2=>operation: 啦啦啦
cond=>condition: Connect();
st->cond
cond(no)->listen->SYNrcvd->e
cond(yes)->SYNsent->e
```
##### TCP: closing a connection
```sequence
Note left of 艾莉絲: 艾莉絲close(), 之後不send但能receive
艾莉絲->包柏: FINbit=1, Seq=x, SeqLen=1
Note right of 包柏: 包柏回應ACK, 還是可以send
包柏-->艾莉絲: ACKbit=1, Ack=x+1
包柏-->艾莉絲: FINbit=1, Seq=y
Note right of 包柏: 包柏不能再send
Note left of 艾莉絲: 艾莉絲還是可以回應ACK
艾莉絲->包柏: ACKbit=1, Ack=y+1
```
#### Congestion Control
Flow control: 一個人用太多
Congestion control: 太多人一起用
=> lost packets & long delays
##### Scenarios
1. 兩connection共用link capacity = R，兩人都用R/2時，delay $\rightarrow \infty$
2. Retransmission
1. Application Layer用量不多，但Transportation Layer有retransmit，提升用量
2. 如果router buffer 滿了，packet被drop，傳的人不會知道，就一直retransmit
3. 還沒傳到但timeout了又重傳duplicate packets
3. 不同path有overlap的話互相干擾，明明是好的path卻因為別人而爛掉
##### Approach
1. Additive increase: 每次一收到newACK就cwnd += MSS (maximum segment size; packet) ，直到loss
2. Multiplicative decrease: 一有loss就cwnd /= 2
##### Details
- Send Rate $\approx \frac{cwnd}{RTT}$ bytes/sec
- Slow start (cwnd=1 MSS)
- 但每次RTT exponentially increase(cwnd *=2)，直到threshold，效果同每收到一個ack，cwnd就加1
- threshold = timeout前一刻的cwnd/2
- Loss:
- 如果是timeout: 直接cwnd=1 MSS
- 如果是3 duplicate ACKs:
- TCP Reno: cwnd /= 2
- TCP Tahoe: cwnd = 1 MSS
<table>
<thead>
<tr>
<th>Scale</th>
<th>per RTT</th>
<th>per ACK</th>
</tr>
</thead>
<tbody>
<tr>
<td>Slow start - increase</td>
<td>cwnd *= 2</td>
<td>cwnd += 1 MSS</td>
</tr>
<tr>
<td>Slow start - decrease by 3 duACK</td>
<td colspan=2>cwnd = cwnd/2</td>
</tr>
<tr>
<td>Slow start - decrease by timeout</td>
<td colspan=2>cwnd = 1 MSS</td>
</tr>
<tr>
<td>Cong Avoid - increase</td>
<td>cwnd += 1 MSS</td>
<td>cwnd += 1 MSS * (1 MSS/cwnd)</td>
</tr>
<tr>
<td>Cong Avoid - decrease by 3 duACK</td>
<td colspan=2>cwnd = cwnd/2</td>
</tr>
<tr>
<td>Cong Avoid - decrease by timeout</td>
<td colspan=2>cwnd = 1 MSS</td>
</tr>
</tbody>
</table>
- Average Throughput是3/4 W (W是會爆掉的window size)
- $$Throughput = \frac{1.22*MSS}{RTT \sqrt{L}}$$
#### TCP Fairness
很fair
## Chapter 4: Network Layer - The Data Plane
- Data plane: router 內運作
- Control plane: router間運作
Comparison:
- Transport layer: between two processes
- Network layer: between two host
### Longest Prefix Matching
Too simple
### Head-of-the-Line (HOL) blocking
進switch fabric前需要排隊，排後面的人被blocking
#### Buffering
Buffer size = RTT * link capacity R / √N
### Scheduling
- Priority scheduling
- Round Robin scheduling
- Weighted Fair Queuing (WFQ)
### IP: Internet Protocol
- TTL: time to live
- For traceroute
- 避免陷入無窮迴圈cycle
- Fragmentation, reassembly
- 原packet: length=4000(header=20; data=3980), fragflag=0
- Frag1: length=1500(header=20; data=1480), fragflag=1, offset=0
- Frag1: length=1500(header=20; data=1480), fragflag=1, offset=185 (offset單位8 bytes)
- Frag1: length=1040(header=20; data=1020), fragflag=0, offset=370
### Subnets
- IP address: subnet part(high order)/host part(lower order)
- one interface to router
- physically reach without router (可用switch)
### IP addressing: CIDR(Classless InterDomain Routing)
how to get one?
- Hardcoded in /etc/rc/config
- DHCP: Dynamic Host Configuration Protocol **是用UDP喔**～～～～
- 也會傳給你router ip address供你upload
- DHCP Router的addresses由ISP給予，ISP的addresses則由ICANN分配給予
```sequence
Host->DHCP server: Broadcasts "DHCP discover"
DHCP server-->Host: DHCP offer
Note right of DHCP server: 以上optional
Host->DHCP server: DHCP request
DHCP server-->Host: DHCP ack with address
Note left of Host: Get IP Address!
```
### NAT: network address translation
對外使用same single source NAT IP address，對內使用local network IP
#### Advantages
1. ISP不需要知道所有device的ip一樣可以傳data
2. 換ISP時不會動到local network
3. Security plus: 外面看不到裡面
#### Implementation
1. Outgoing datagrams: replace 任何內網ip to NAT ip address 但要是 new port number，之後都用這個port number去傳data
2. Remember 上面的轉換（translation pair）
3. Incomming datagram: replace NAT IP address and new port number to inet ip (with translatoin pair)
16-bits port number => 65535 simultaneous connections!
#### Controversial
1. NAT 是 network layer 但卻碰了application layer 的port number
2. ipv6已經解決address不夠用的問題
3. 因為不是end2end，害P2P的application不能直接用fake ip連線
4. NAT內的人無法當server被外界連線 => NAT traversal problem
#### Solutions to NAT traversal problem
1. 先幫server config好固定的port
2. 使用Universal Plug and Play (**UPnP**) Internet Gateway Device (**IGD**) Protocol => 自己去學最不會變的mapping
3. 用relaying: 先都連到第三方機器當中繼站（skype就是）
### IPv6
- 32-bits不夠了 => 加碼到128-bits
- 不用checksum了
- ICMPv6
- 遇到IPv4 router怎辦，包進IPv4 packet偽裝 => tunneling
### General Forwarding and SDN
match+action:
- Router: longest ip prefix+forward to link
- Switch: MAC address+forward or flood
- Firewall: IP address&TCP/UDP port+permit or deny
- NAT: IP address and port+rewrite IP address and port
| | Traditional | General (SDN OpenFlow) |
| ------------------ | ----------------------------------------- | ---------------------------------- |
| Control Plane | Central server | every router |
| Data Plane - match | destination address | any comb of pkt header |
| - action | Forwarding -> output interface statistics | any forward drop modify statistics |
## Chapter 5: Network Layer - The Control Plane
### Routing Protocols
Determine paths that are 1. Least cost 2. Fast 3. Least congested
#### Link State - Dijkstra's algorithm: O(nlogn)
缺點oscillision
```
c(x, y) = link cost of (x, y). // 查表
D(v) = path cost from source to v. // 直接查link (是neighbor)
p(v) = 前任from source to v
N' = 已知least cost nodes
更新：N' = {u}
for v in N:
D(v) = c(u, v) if v in u.neighbors else D(v) = +inf
while N' != N:
find w with minimum cost D(w)
for v in w.neighbors:
D(v) = min(D(v), D(w)+c(w, v))
```
#### Distance Vector - Bellman-Ford algorithm:
By the equation:
let:
$$
d_x(y) := \text{cost of least-cost path from x to y}
$$
then:
$$
d_x(y) = min_v \{c(x, y)+d_v(y)\}
$$
and:
$$
\text{distance vector } D_x(y) = [d_x(y): \text{for y} \in N]
$$
Node x 有什麼：
- link cost to 所有鄰居: $$c(x, v) \text{ for v in x.neighbors}$$
- 自己的DV: $D_x$ ; 鄰居的DV: $$D_v \text{ for v in x.neighbors}$$
Online 運作 Key idea:
- 如果一有變動，自己要把自己的DV送給鄰居
- 拿到鄰居的DV後要更新自己的DV
$$
D_x(y) \leftarrow min_v \{c(x, y)+d_v(y)\} \text{ for y} \in N
$$
##### Bad News travels slow - count to infinity problem
昔日的short link光榮揮之不去 => "good" link makes more iterations to be "flashed out"
##### Poisoned reverse
Link cost上漲時直接把DV中的$d_z(x)$值更新成$\infty$，大家就不會走這條，讓他再被min更新一次
### Scalable Routing in intra/inter-AS (autonomous systems)
forwarding table configured by intra- and inter-AS routing algorithm
#### Inter-AS routing
知道其他AS可以reach哪裡
#### BGP (Border Gateway Protocol)
- eBGP: 從鄰居拿到subnet reachability資訊 (用TCP)
- iBGP: 把reachability資訊傳給自己subnet裡面的別人
- "path" vector protocol: 除了傳Distance vector，還要傳Full Path
- 如果沒傳Full Path: 1. 可能有Loop 2. 可能count to infinity
- Hot potato routing => 選 cost 小的
- Policy dominate over performance
gateway router may learn about multiple paths to destination:
- AS1 gateway router 1c learns path *AS2,AS3,X* from 2a
- AS1 gateway router 1c learns path *AS3,X* from 3a
- Based on policy, AS1 gateway router 1c chooses path *AS3,X, and advertises path within AS1* *via iBGP*
#### Intra-AS routing a.k.a interior gateway protocols (IGP)
- RIP: Routing Information Protocol (distance vector)
- OSPF: Open Shortest Path First (link state) 跟 IS-IS routing protocol差不多
- IGRP: Interior Gateway Routing Protocol (none knows how it works)
#### OSPF (Open Shortest Path First)
- 一直算Dijkstra然後把table flood到整個AS裡面
- 所有OSPF msg 都要經過authenticated => security
- Same cost的path都可以走 => 不像DV
- 可以看每一條link的多種ToS => type of service 1. best effort 2. Stored 2. realized
- Uni/multi-cast support
- Hierarchical OSPF
### Sotfware defined networking (SDN)
Centralized Routing & General Forwarding
Traditionally, link weight is the only control "knobs" of traffic. 例如想要split traffic沿著兩條path，但因為沒有equal cost所以會違反shortest path，行不通。=> 用OpenFlow
Network Operating System, interact with routers, brains of control.
OpenFlow負責用Dijkstra算flow table，然後install回去各個router
### ICMP: Internet Control message protocol
traceroute就是用UDP send, 用ICMP return
## Chapter 6: The Link Layer and LANs
- Link Layer => 可以是Host to router的Link，也可以是Router to router的Link
- 不用IP address 而是 MAC address used in frame headers
- Link layer implemented in network interface card (NIC)
### Error Detection
- Two-dimension bit parity
- Cyclic Redundancy Check
### CRC
Data: D; Choose r+1 bits G as generator
找到CRC bits R (r-bits)使得 <D, R> 可被 G 用XOR整除
找法：把$D*2^r$ 除以 G 餘數就是R
### Multiple Access Links
- point-to-point: Ethernet, PPP for dial-up
- Broadcast: HFC, 802.11 wireless LAN, satelite => collision
#### MAC Protocol: taxonomy
1. Channel patition
2. Random access (and recover from collision)
1. slotted ALOHA
2. ALOHA
3. CSMA, CSMA/CD, CSMA/CA
3. Taking turns
### TDMA: time division multiple access
time division with idle slot possible
### FDMA: frequency division multiple access
Same
### Slotted ALOHA
大家有對齊好slot，若collision 發生則以機率p在next slot重傳直到成功，成功機率$Np(1-p)^{N-1}$
p = 1/N 是最佳解，此時使用效率是 $1/e = 37\% \text{ as } N \rightarrow \infty$
### Pure (Unslotted) ALOHA
$t_0$送的frame會跟$[t_0-1, t_0+1]$內送的frame collision
成功機率$Np(1-p)^{N-1} \cdot (1-p)^{N-1}$ = $Np(1-p)^{2(N-1)} \rightarrow \frac{1}{2e} = 0.18 \text{ as } N \rightarrow \infty$
比樓上更慘
### CSMA (Carrier Sense Multiple Access)
傳前先聽，但因為延遲，還是會collision
<img src="https://i.imgur.com/ELUmsTs.png" alt="image-20200108194336924" style="zoom:20%;" />
### CSMA/CD (Carrier Sense Multiple Access/Collision Detection)
一發現collision就收掉信號，節省時間，進入binary (exponential) backoff
<img src="https://i.imgur.com/KeFWClf.png" alt="image-20200108194414633" style="zoom:20%;" />
Choose K at random from $\{0, 1, 2, ..., 2^m-1\}$ and waits $K \cdot 512$ bit times
$$
\text{Efficiency} = \frac{1}{1+5t_{prop}/t_{trans}} \rightarrow 1 \\ \text{as } t_{prop} \rightarrow 0 \text{ and } t_{trans} \rightarrow 1 \\
\text{where } t_{prop} = \text{max prop time between two nodes}\\
t_{trans} = \text{time to transfer a frame}
$$
### Taking turns
best of both worlds!
#### polling
master邀請slave輪流送
#### token passing
輪流傳token，傳到的用
### ARP: Address Resolution Protocol
Mapping `<IP address; MAC address; TTL>`
LAN (Local Area Network)
## Chapter 7: Wireless
### SNR: signal-to-noise ratio
越大越好
**BER: Bit Error Rate**
SNR v.s. BER 的 trade-off
Increase power => 同時可以increase SNR and decrease BER
### Code Division Multiple Access (CDMA)
- Encode: convolution
- Decode: inner product / slot length
Sign in with Wallet
Connect another wallet