Reliable Transmission - Sliding Window Algorithm

• Reliable Transmission - Sliding Window Algorithm
  • 想法：允許同時有多個「在途」的封包
  • 滑動視窗演算法
    • 封包有遞增編號
    • 起始：連續發送 n 個封包
    • 發送方滑動：收到編號最小的 k 個封包的 ACK 時
    • 接收方滑動：收到編號最小的 k 個封包時
  • Sliding Window 的一些參數
    • SeqNum –- 封包的編號
    • SWS –- 有幾個在途的封包
    • LAR –- 上一個收到的 ACK
    • LFS –- 上一個傳送的封包
  • 參數的設計考量
    • 觀察：SWS 的上限受 SeqNum 限制
    • 觀察：決定 RWS 跟 SWS
  • 課程影片
    • 第 6C 講區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 3
    • 第 6DE 講區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 4 5
    • 第 6H 講 區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 8
    • 第 6I 講 區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 9 10
    • 第 6G 講 區域網路可靠傳輸技術 －－ 滑動視窗技術 L06 7 (10:00 ~ FIN)
    • Hands-on TCP Analysis: Packets, Sequences & Fun (SF17EU)

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

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

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

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

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

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

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