---
robots: index, follow
tags: NCTU, CS, 共筆, 網路
description: 交大資工課程學習筆記
lang: zh-tw
dir: ltr
breaks: true
disqus: calee
GA: UA-100433652-1
---
計算機網路 -- 趙禧綠
===

## Introduction
- Telecom (Tele Communication)
- Datacom (Data Communication)

- Course Taken
- Computer network
- Cellular network
- Cloud computing
- Programming
- Final Projects
- Theory
- Algo. DataStruct.
- Graph
- Control Theory: TCP, load-sensitive routing
- Queueing theory: 了解、分析網路狀況 (太複雜時無法分析)
- Optimization
- Game Theory
- Information Theory: 可以算出 network properties
- Goals
- Overview
- state-of-the-art
- conduct research
- Logistics
- [e-mail]
- TextBook
- **[Data and Computer Communication](https://abmpk.files.wordpress.com/2013/04/data-and-computer-comm-8e-william-stallings.pdf)**
- [Computer Network: a system approach](http://cs.mvnu.edu/twiki/pub/Main/JimSkon/Computer_Networks_A_Systems_Approach.pdf)
- paper / RFC
- Syllabus
- Internet arch. & proto.
- Underlay
- Wireless
- Datacenter
- SDN & NFV
- Cloud RANs / 5G / WiGig
- Overlay
- Application
- Web, streaming, p2p, distribution
- Edge computing
- Miscellaneous (Misc.)

### Architecture
一旦網路架構定好了，當需要改變時，是很麻煩的 => 一開始設計好架構是很重要的
- Network
- Best-effort (最小架構，剩下的 host 端處理 ex. tcp)
- lost, corrupted, out-of-order
- Host
- everything else
- 5G
- Broadband communications
- Massive IoT
- URLLC (高可靠，低延遲)
- => 不是 best-effort
- Congestion Control
- 需有現在網路狀況
- 要 low lagicy 就不一定是最短路徑，而是可能需要 ECMP
- what rate to use for each flow?
- 最好還是分散式架構
- 交換資訊越少越好
- [TCP Congestion Control](https://witestlab.poly.edu/blog/tcp-congestion-control-in-lossy-wireless-networks/)
- Why TCP 不會壅塞在 host 端？
- 3 way handsharking 時就會告知 host 的資源
- 網路如何傳送?
- 電訊號、電磁波
- 大、小 功率？
- 大: 遠、干擾、2.4GHz
- 小: 進、5GHz、低延遲、高速
- => 5G 取 功率小
- 低延遲、高速
- 高密度佈建 (0.001/m^2)
- **UDN** small cell (ultra dense network)
- small buffer (單顆不會有太多人連線) => cheap

How to Read a Paper

## Foundation of Computer Networks
- 網路需要
- Application Programmer
- Network Designer
- Network Provider
- 連線
- Term.
- Scale
- Link
- Nodes
- Point-to-Point (PPPoE)
- Multiple access (Switch、Hub、Bus、...)
- Packet / Circuit Switched (因為 multiple access 要處理何時誰傳 or 如何同時傳)
- store-and-forward
- cut through
- 不將封包全部收進來，看到 header 後就動作了
- S.A.F.
- 將封包全部收進來，才開始檢查 header 後動作
- Resource
- link & node
- shared link
- Multiplexing
- De-multiplexing
- DM (division Multiplexing)
- FDM
- TDM
- CDM
- Statistical Multiplexing
- Flow: 點到點
- Resource Allocation: FIFO, Round-Robin, QoS
- Congested
- 加 buffer => 延遲
- 好的 tcp congestion 會檢查 buffer 中，只有佔 queue 太多的 source 才會丟 window ack，只有送最多的 source 才需要降封包送出數，流量佔不多的其實不需要降流量
- Reliability
- hide error
- bits / packets lost
- failures
- delay
- out-of-order
- eavesdrop (竊聽)
- 軟體：加密
- 通訊：跳頻 (frequency hopping) (HSSS, DSSS)
- Protocols
- Spec.: prose, pseudo-code, **state transition diagram**
- Interoperable(互操作)
- IETF(Internet Engineering Task Force): 訂定 RFC 的組織 (免費)
- Performance
[參考](https://blog.gtwang.org/web-development/network-lantency-and-bandwidth/)
- Bandwidth
- 每單位時間內，可以傳送的資訊量
- bandwidth (Hz)
- Latency
- propagation delay + transmit delay + queueing delay
- propagation delay: 網路線上電子訊號跑的速度有關
- transmit delay: 網路卡將資料傳送到網路線上 (正比於資料大小)
- queueing delay: 經過 switch / router 中 queue 的時間
- delay * bandwidth
- 
- jitter
- vedio 或 voice
- [抖動、時基誤差](https://zh.wikipedia.org/wiki/%E6%8A%96%E5%8A%A8)，穩定度的量化
- 若 jitter 高，聽到的聲音可能會不穩，vedio 了化可以用 buffer 來處理，電話了化可能無解
- 因為有了 buffer 所以現在 paper 比較少出現這種

## Connected in LAN
沒有 routing
- 分散式 media access control (避免訊號碰撞)
- control frame
- framing (data 內部要塞什麼)
- Link Capacity
- Shannon-Hartley Theorem: $C = B * log_2(1+S/N)$
- B：bandwidth
- S：signal
- N：noice
- capacity 代表是理論值
- Links
- medium
- frequency
- 影響 S (接收訊號)
- F 高 => B 會增加 => 可是受干擾的影響大 => 距離要大
- encoding: 把 binary 資訊放到 signal 上
- Modulation: 調變 (MAC 層)
- 一個 signal 可以傳送多個 data 意義
- 可以改變 振幅、相位、頻率、...
- ex. 將振幅切成四個等級，一個振幅可以代表不只一個訊息
- ex. BPSK, QPSK, 16QAM, [others](https://www.radio-electronics.com/info/rf-technology-design/quadrature-amplitude-modulation-qam/8qam-16qam-32qam-64qam-128qam-256qam.php)
- encoding
- NRZ (none-return-to-zero)
- 
- 中間才是 0
- 問題：
- 電腦不同不：當出現一連串的 0 或 1 時，A 電腦可能以為是 3 個 0，B 電腦可能以為是 4 個 0
- 機械漂移：因為電壓是相對的，所以其實 baseline 是用平均算出來的 => 當收到的資訊愈多，baseline 就會漂移
- NRZI (Non Return to Zero Inverted)
- 0 電壓不改變
- 1 電壓改變
- Manchester
- 只有中間有改變
- 0 低到高電壓
- 1 高到低電壓
- 目前使用最普遍的
- 
- 4B/5B encoding
- 根據 spec. 若有連續 n 個 0/1，用其他 encode 代表之
- no more than one leading 0(zero) and no more than two trailing 0’s
- No pair of 5-bit codes results in more than three consecutive 0’s
- 有 table 可以參考
- Framing
- byte 為單位
- BYSINC、PPP、DDCMP
- bit 為單位
- HDLC
- Error
- Detection
- kind
- CRC (Cyclic Redundancy Check) => 用晶片做
- Checksum (IP) => 軟體作
- Correction
- Re-send
- Reliable
- 要確保可靠傳輸
- ARQ (Automatic Repeat Request)
- kind
- stop and wait
- ACK / NAK
- timer (timeout) (seq number)
- go back N
- 一次送多個
- sliding window
- 第 n 個錯了話，從第 n 個開始全部重送
- 對 receiver 的 buff 好作，不需要紀錄送錯的 packet 以及之後的 packet
- select repeat
- 第 n 個錯了，只重送第 n 個
- receiver 的 buff 要記住對的 packet 與位置
- seq no 要多長？
- stop & wait 只要 0 與 1，有交錯就是正確執行，有連續就是 seq 有問題
- $SWS < (MaxSeqNum + 1)/2$
- Flow Control
- 在 ack 裡回復 window 要開多大
- if connection 多 => window 要減小 => 把 buffer 平均分攤
- 監聽 channel busy
- 1-persistent protocol
- 聽到 channel 空的就直接送
- ethernet 使用
- 碰撞機率高 but 因為 ethernet 有辦法煞車 (可以邊送邊聽) (CSMACD)
- wifi 因為無法煞車 => 不能使用 (CSMACA)
- 適合較少用戶之網路(較激進的使用)
- non-persistent
- 若 channel 使用中，就不監聽 => 停一個隨機的數字後，再一次監聽
- 適合高使用率網路
- p-persistent
- p 的機率送，1-p 的機率不送，p 以網路的狀況決定
- p 不好預測 (也許可以用 AI 處理)
- [543 規則](http://netgames123.blogspot.com/2007/11/543.html)
- 5 個網域
- 4 個 repeater: 太多雜訊會提高
- 3 個電腦群體
- TXOP
- transmition oppotunity
- 時間單位
- 每次搶到 channel 有這麼長的時間可以使用
- 原本只有一個 frame/ack 就要重新搶 channel，現在因為 throughput 變大了，所以開始允許使用多一些時間，利用 TXOP 來決定可以使用多久
- ip / mac 都有 unicast / multicast / broadcast
- Wireless
- 要做調變 (用 震幅/角度/... 來放入不同資訊)
- broadband 寬頻通訊
- header 一定是用最慢的速度傳輸 (電磁波角度)
- payload 會比 header 快很多 => packet aggregation: 將 payload 結合起來，讓 payload 很常，避免每次傳一個 frame 都要浪費時間在傳 header
- Wireles
- FHSS
- DSSS

## L3 Internetworking
- virtual circute
- ATM Switch
- MPLS
- VCI / VPI
- 打 lable 代替看 L2 mac address
- 需要先建立虛擬路徑，只有 local 知道
- 先建立 local forwarding rule，多一個路徑建立時間 but 跑的時候比較快
- circute switch 的概念
- 不收的時候會 tear down
- 早點資源釋出
- tear down 後，memory 已經沒有資料了，因此無法回復前一個 switch 說我丟包了
- Source Routing
- 看 source
- ex. PBR
- static vs loose
- switch vs bridge
- switch: learning switch protocal
- bridge: flooding
- Reduntency
- 
- TOS 只放 n 選 1
- 
- fragment
- 
- Router 只做 fragment 不做 reassemble
- 但是，如果要求重送，因為可能 H8 重要第二個 frame，可是 H5 送的時候明明只有一個 frame，無從知道 frame 2 是誰，所以後來實作時，都是先要求 MTU 多少，在統一用這個 MTU 來送資料
- 如果 rerouting 時，path MTU 要重要求 (Maximum transmission unit)
- Class
- A 1/2
- B 1/4
- C 1/8
- D 群播 (multicast)：指定 multicast ip
- E 保留 / 實驗
- CIDR: 沒有 class 概念

## End-to-end protocols
...

### TCP
- 希望實現可靠的通訊
- Connection establish
- Resend
- relay on ACK / timeout / mss 塞滿
- Connection termination
- Flow control
- 希望 sender 不要 overrun (不要送超過對方的 buffer -> 掉封包)
- slow start
- reciver 透過 windows size 告知 sender 我的 buffer size 多少
- Timer
- 如何設定 resend 的 timeout 長度
RTO(Retransmission Time Out)
- 需要比 *來回* 時間還長
- 太小: 其實有收到，但是重傳了
- 太大: 很晚才重傳
- 設定方法:
- Average Round-Trip Time (ARTT)
- TCP 內包含 reciver 回 ACK 時的系統時間
- sender 可以知道 *來回時間*
- 用此來預測下一個 ARTT
- $ARTT(k+1) = \frac{K}{K+1} ARTT(K) + \frac1{K+1} RTT(K+1)$
- RTT: 此次 來回時間
- [RFC 793](https://tools.ietf.org/html/rfc793)
- Smoothed RTT
- 原方法每次的比重都一樣
- 應該越近的比重越重
- $SRTT(k+1) = \alpha * SRTT(k)+(1-\alpha) * RTT(k+1)$
- SRTT 可以表示現在的網路狀況，那 timeout 時間應該要比他大，但是要大多少呢？
- $RTO=SRTT + \Delta$
- 原來以為 $\Delta$ 可以是參數 => 發現也要隨著網路狀況而改變
- $RTO(k+1)=min(UBound, max(LBound,\beta*SRTT(k+1))$
- 造成 RTT 大改變的原因
- data transmission time
- queuing time (Router)
- reciver 的 waiting time (reciver 會想包裝一定的資訊量再重傳)
- 另外一種 RTO 的算法
- Jacobson’s Algorithm (RFC 2988)
- 利用 error 來調整
- Standard RoundTrip Time
- Standatd
- 如果封包沒有回來 (掉包 or 前面的還沒回來而已)
- 把現在的 RTO 變兩倍 (binary exponential backoff)
- 凡重送後成功的封包得到的間隔時間不算入 RTT 中
- 因為其實也有可能是第一次就成功的，只是真的送的很久，TCP 無法分辨是第一個的 ack 還是重送的 ack
- Karn's algorithm
- 由於無法分別在Re-transmit後，回來的ACK是原ACK還是Re-transmit後之ACK
故選擇不將其納入RTO之計算中
- 在重傳過程結束後，後面進行的成功傳送才納入計算
- K+1成功重傳 回傳ACK(K+2)
- K+2成功傳送 回傳ACK(K+3)
- 此參數才可納入RTO計算

- tcp congestion control
- 看網路壅塞狀況
- TCP 是第四層，網路狀況是二、三層，對 TCP 其實不好偵測
- IP 曾有些東西也許可以幫忙，but 可能比較沒有效率
- ICMP Source Quench message: Router 可以透過 ICMP 叫某些 sender 不要送
- sender 不一定會聽
- RSVP may help but not widely implemented
- 作法
- slow start (RFC 2581)
探索(probe)網路最大能力
- Basic:
- awnd = allowed window in **segments**
awnd = min[credit, cwnd] (擇小的)
- cwnd = congestion window in **segaments**
當每個新的connection成功收到ACK，則新增一connection
直到loss
- 指數成長
- credit = amount of unused credit granted in most recent ACkK in **segments** (= window/segment size)
- 一直往上漲，但是不能無限上綱 => 在 flow control 的 limit 停止
- 同樣 flow control 也要停止在 congestion control
- Congestion avoidance
- dynamic windows sizing on congestion
- 基本上是用 congestion windows 來處理 (單位: segments) (TCP 是用 byte 為單位，單位不同)
- 
與slow start不同於，他會將爆掉發生的cwnd數除二
設為下個循環的thershold
到thershold時從指數轉為線性成長
- Fast Retransmition
- 加速 Slow start
- 當 segment 丟掉後，會要重傳，可是如果又收到 duplicate 的 ack，就知道網路不是壅塞，而是掉包
- 這時候掉下來的 cwnd 不應該回到 1 重測
- Fast recovery
- 因為知道是掉包，而不是壅塞
- 收到 n duplicate ACK 後
- ssthresh = cwnd / 2 畢竟還是有緩慢
- cwnd = ssthresh + n
- 確定進到下一個 windows 時，(掉包的重傳正確後)，回到原來的 TCP 機制 cwnd = ssthresh
- TCP 版本
- TCP Tahoe
- slow start
- congestion avoidance
- timeout
- TCP Reno
- slow start
- fast retransmission
- fast recovery
- TCP Vegas
- 看packet delay
- accurate RTT
- New retransmission mechanism
- Modified slow start
- 看其他 RTT

## RTP
### RTP
Real Time Transport Protocol
- 不綁定 IP
- TCP 不適合用在 real time **distributed**: 同一個內容，收件者有多人，ex. 多人視訊
- TCP 對 real time 不友善，UDP 沒有時間資訊
- RFC 1889, 3550
- Require
- 需要知道 payload 格式、payload ID
- 跟 application 綁定
- seq number
- time stamp
- 如果要有 QoS，需要有 RSVP、[MPLS](https://zh.wikipedia.org/wiki/%E5%A4%9A%E5%8D%8F%E8%AE%AE%E6%A0%87%E7%AD%BE%E4%BA%A4%E6%8D%A2)... (預留頻寬)
- 
- RTCP
- RTP 是 data plane
- RTCP 是 control plane
- 週期性的
-