# Reliable Transmission - Sliding Window Algorithm

[TOC]

## 想法：允許同時有多個「在途」的封包

Stop and Wait 一次只能傳一個封包，在收到 ACK 前，不能傳下一個封包。也就是「一次只能有一個封包正在傳送的路上」。而 sliding window 則是「一次傳送一批封包」：


## 滑動視窗演算法


### 封包有遞增編號

首先，每一個封包依照傳送次序，會有一個唯一的編號。這個編號是嚴格遞增的數值。為了方便，這邊就用連續的正整數來作為編號。實際上也可以是資料的 offset 之類的數值。

### 起始：連續發送 n 個封包

在傳送開始時，發送方會一口氣傳送 $n$ 個封包。傳送完之後，等待這個「區間」內的封包的 ACK。這個 $n$ 稱為 SWS (*Sliding Window Size*)。更精確地說，這個 SWS 指得是最多能有幾個「在途」的封包。

### 發送方滑動：收到編號最小的 k 個封包的 ACK 時

對於發送方來說，若它等到了「SWS 區間內編號最小的那 $k$ 個封包」的 ACK ，那麼這個大小為 $n$ 的視窗就可以往右移動 $k$。「移動」的意思是發送方可以繼續往下傳送 $k$ 個封包。這個「滑動」的過程一直持續，到發送方送完所有封包為止。

舉例來說，上面的例子收到了最小的 4 號封包的 ACK，所以這個 $k$ 就是 $1$。因為收到了最小的 1 個封包，所以視窗往右移動 1，也就是接著傳送編號 11 的封包。

### 接收方滑動：收到編號最小的 k 個封包時

對於接收方，每當它收到「RWS 區間內最小 $k$ 個封包」時，它就會把自己的視窗滑動 $k$。以這個例子來看，對於接收方來說，它收到了編號最小的 $k=1$ 個封包，因此整個滑動視窗的區間就往右移動 1，改為接收編號 5 ~ 11 的封包，

## Sliding Window 的一些參數


### SeqNum --- 封包的編號

每一個封包的唯一編號。這個編號是嚴格遞增的數值。

### SWS --- 有幾個在途的封包

這個意思是最多能允許有多少個「還沒有收到 ACK」的封包？

### LAR --- 上一個收到的 ACK

*Last ACK Received* 的縮寫。顧名思義，就是最後一個收到的 ACK 的 SeqNum。因為 SeqNum 嚴格遞增，所以這個數值其實也是「所有收到的 SeqNum 中，最大的那個」。

### LFS --- 上一個傳送的封包

*Last Frame Sent* 的縮寫。和上述狀況類似，利用 SeqNum 的遞增性來找。

## 參數的設計考量

### 觀察：SWS 的上限受 SeqNum 限制

相異的序列號數目跟 SWS 必須滿足 ~~Shannon's Sampling Theorem~~ ：

$$
\cdot \text{SWS} < \frac {N_{\text{SeqNum}} + 1}{2}
$$

否則碰到延遲的 ACK 時，就沒辦法知道它是新封包的 ACK，或者只是遲到的 ACK


上面的 6H 與 6I 講在討論這件事。

### 觀察：決定 RWS 跟 SWS

SWS 是受到網路頻寬決定的，因為一次就只能送那麼多封包而不掉東西。而 RWS 則比較有彈性。就算 RWS 設為 1，這個滑動視窗演算法也可以運作，這時候接收方永遠在等下一個相鄰的封包，也就是只接收「按照順序到達」的那些封包。儘管這樣可能會導致發送方不斷地重送「下一個封包以外」的其他封包，而較大的 RWS 可以避免這個問題。

另外要注意的是，雖然較大的 RWS 可能可以避免上述問題，但這個效益最大只能到 RWS=SWS 時。因為如果網路的頻寬一次僅能容許同時傳送 SWS 個封包，那 RWS 再大，一次還是最多只能有 SWS 個封包在途中傳送。

## 課程影片

### 第 6C 講區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 3

{%youtube vgQWajf9gkU %}

### 第 6DE 講區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 4 5

{%youtube GbrFuDkz4P4 %}

### 第 6H 講 區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 8

{%youtube 64v6Twt9S60 %}

### 第 6I 講 區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 9 10

{%youtube i9VQiZgqdLI %}

### 第 6G 講 區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 7 (10:00 ~ FIN)

{%youtube mxVN2LKIQuM %}

### Hands-on TCP Analysis: Packets, Sequences & Fun (SF17EU)

{%youtube R3nuuZiIbgU %}