# 計算機網路 Ch03 - Transport Layer

###### tags: `計網`

[]()

## Principles of transport layer
* multiplexing, demultiplexing
* reliable data transfer
* flow control
* congestion control

## 3.1 transport-layer services
建立logical communication關係

送出: application layer -> messages -> segments(封包) -> network layer
接收: network layer -> segments -> messages -> application layer

### Transport vs. network layer

### TCP vs. UDP

* congestion control -> 壅塞處理(重點!!)
* flow control -> 流量控管
* connection setup

## 3.2 multiplexing and demultiplexing

* Multiplexing: 一次傳多個
* Demultiplexing: 區分不同的process

基本上host就是透過IP addresses 和 port numbers來分辨的

### UDP: Connectionless demux

### TCP: Connection-oriented demux
一個IP address對一個socket，修復容易

## 3.3 UDP: User Datagram Protocol
connectionless -> 不建立連線
each UDP segment handled independently of others -> 封包彼此獨立

優點:
* 延遲小

缺點:
* 封包遺失
* 不按照順序

使用協定:
* streaming multimedia apps (loss tolerant, rate sensitive)
* DNS: 傳送內容不大
* SNMP: 網路設備設定

### UDP segment header

UDP header size: 8 bytes
TCP header size: 20 bytes

### UDP checksum

比較算出來的checksum和封包中的checksum是否相等:
* 不相等: 一定錯
* 相等: 沒有發現錯，但不一定對，因為checksum只取檔案的一小部分，所以可能只是剛好沒找到錯誤而已。

## 3.4 principles of reliable data transfer
### Reliable data transfer
reliable data transfer protocol(rdt)：資料必須全對，deliver_data才會傳給應用層

### State
finite state machines (FSM)

類似正規語言中的DFS

### rdt1.0: reliable transfer over a reliable channel

underlying channel perfectly reliable -> 假設都不會錯
* no bit errors
* no loss of packets

### rdt2.0: channel with bit errors
checksum to detect bit errors

acknowledgements **(ACKs)**: receiver explicitly tells sender that pkt received OK -> 接收到正確的封包
negative acknowledgements **(NAKs)**: receiver explicitly tells sender that pkt had errors -> checksum有錯誤，保留封包並要求重傳


#### sender
接收ACK: 傳下一份封包，釋放Buffer
接收NAK: 封包重傳

#### receiver
checksum沒錯: 回傳ACK
checksum有錯: 回傳NAK，捨棄封包

正確的情況:

錯誤的情況:

#### stop-and-wait
- sender sends one packet, then waits for receiver response -> 一次只傳一個封包，確保封包的正確性。

### rdt2.1
- sequence number -> 封包序號，如果是重複的封包需省略。只需要1-bit(0, 1)。
- sender: 停在等待0或1的狀態。
- receiver: 停在等待0或1的狀態。



### rdt2.2: a NAK-free protocol
duplicate ACK at sender results in same action as NAK: retransmit current pkt -> 不需要NAK，利用重複的封包來取代NAK的作用。如果收到重複的封包，則重傳。


### rdt3.0: channels with errors and loss
多考慮到封包遺失的情況: sender加上timer機制，計數從送出封包到接收到NAK/ACK的時間，超過時間就直接重傳。
sender3.0和2.2架構差不多，只多了timer。receiver則沒變。




(d) 封包延遲時間超過timeout時間



### Pipelined protocols


一口氣送多個pkt。

- Go-back-N: 不連續的部分全部捨棄並重傳。
- Selective Repeat: 保留連續的封包，只針對錯誤的部分做重傳。

#### Go-back-N(GBN)


cumulative ACK -> 所有 seq number < n 的pkt都已經被ACK。



**window size <= seq number**

#### Selective Repeat(SR)

一個pkt獨立設置一個timer，timeout只需要重傳該封包就好。


問題: receiver認為0是下一個0的封包，以為3還沒傳。

**window size <= seq number/2**

## 3.5 connection-oriented transport: TCP
* 以byte為單位傳輸
* pipeLine: 一次傳好幾個封包
* 雙向溝通
* handshaking: 先建立連線
* flow controlled: 流量控管

### TCP segment structure


* sequence numbers: 傳輸端的第一個
* acknowledgement numbers: 接收端預計接收ACK的第一個



### TCP round trip time, timeout

#### SampleRTT: 預測合理的timeout時間

* timeout太短：多次寄送重複封包，浪費頻寬。
* timeout太長：封包遺失要等待很久才重傳，延遲變長。

因此，計算合理的RTT時間是很重要的一件事。


$$EstimatedRTT = (1- a)*EstimatedRTT + a*SampleRTT$$

a = 0.125

$$DevRTT = (1-b)*DevRTT + b*|SampleRTT-EstimatedRTT|$$

b = 0.25

$$TimeoutInterval = EstimatedRTT + 4*DevRTT$$

### reliable data transfer

#### sender events
* data rcvd from app: 只重傳一個封包
* timeout
* ack rcvd: 確認封包正確



sender或receiver端會記錄最大seq number，如果接收到的seq number小於最大的seq number，則視為重複封包。

就算ACK100遺失也沒關係，因為sender只要接收到ACK120就能確定100有成功送達。

#### TCP fast retransmit
detect lost segments via duplicate ACKs: 收到重複地確認訊息，視為遺失，並重傳。


收到三個重複的ACK，直接重傳，不管有沒有Timeout。

### TCP flow control


避免因為buffer空間不夠造成封包遺失。
在TCP header中的receive window欄位，receiver透過這個欄位傳送rwnd給sender。
receiver告知sender空閒的Buffer空間(rwnd)，還沒被ACK的封包大小必須 <= rwnd。

### Connection Management
避免序號重複。

### 2-way handshake


timeout導致重新發送連線請求，在結束連線後又再連線一次

### 3-way handshake


三次確認，序號是錯開的。


### closing a connection


FINbit = 1，關閉連線。
seq用來確認是否為同次連線，x和y不會相同。
等待兩倍週期，如果封包遺失還可以重傳。

## 3.6 principles of congestion control (壅塞控制)


 重傳後檔案反而更大

浪費頻寬


D遺失資料，浪費了圈起來兩個router的資源。

## 3.7 TCP congestion control

### 目標

* Efficiency: 效率，且不能降低網路使用率。
* Fairness: 公平性，所有的分到的頻寬要是一樣的。
* Distributeness: 分散性
* Convergence and stability: 收斂性，遇到雍塞時可以盡快收斂。穩定性，壅塞時對其他使用者影響不大。兩者互相矛盾。

### Sample Model


將所有的流量相加，如果大於可用頻寬，就發生壅塞。

### Linear Contral


efficiency line: 效率線，線以上的部分發生雍塞
fairness line: 公平線，點越接近線越公平

### congestion: 發生壅塞


efficiency和fairness兩個區塊重疊的部分為紅線。
**紅線：a~D~ = 0，b~D~ > 1 (通過原點，斜率大於1)**


efficiency和fairness兩個區塊重疊的部分為紅色區塊。
通常會挑垂直於efficiency的紅線。
**紅線：a~I~ > 0，b~I~ = 1 (與x軸交會於正向，斜率等於1)**

#### AIMD(Additive Increase & Multiplicative Decrease)

公式總整理


網路上的實際情況就是在underload和overload間來來回回，越來越接近fairness線。

### TCP流量控制


* 沒壅塞時...: cwnd一次上升一個RTT(線性上升)
* 雍塞時...: cwnd/2(倍數下降)

**線性上升，倍數下降 -> 符合AIMD**


$$LastByteSent - LastByteACKed <= cwnd$$

大於則無法送出封包。


可以用cwnd就算出傳送速率。

### TCP Slow Start


為了增加一開始的速度，每次成功接收到ACK訊息，**cwnd就變兩倍**。

### TCP Congestion Control Summary


* MSS：maximum segment size
* 當 cwnd < ssthresh 時，進入slow start狀態，cwnd = cwnd + 1 MSS，以指數成長。
* 當 cwnd >= ssthresh 時，進入congestion avoidance狀態，cwnd = cwnd + MSS*(MSS/cwnd)，以線性成長。
* 當接收三個重複ACK(fast retransmit)時，進入fast recovery狀態，ssthresh = cwnd/2，cwnd = ssthresh + 3 MSS。
* 當發生timeout時，回到slow start狀態，ssthresh = cwnd/2，cwnd = 1 MSS。
* fast recovery狀態下，收到重複ACK，則cwnd = cwnd + 1 MSS。


### TCP throughput


平均window大小為¾W

### TCP Fairness
總頻寬為R，每個人平均分到R/K。
AIMD即可解決。

不公平的情況: 和UDP競爭不利、一個host同時建立多個TCP連線。

### 補充: Explicit Congestion Notification (ECN)


交給Router做壅塞控制，並在header和ACK訊息中加上ECN欄位告訴source和destination有無發生雍塞。