TCP connection establish

一般 package 傳輸為停止並等待協定(Stop-and-wait)有著通道使用率極低的問題。 GBN(Go-Back-N) 及 SR(Selective Repeat) 兩種協定避免了此問題。

效果上 SR > Go-Back-N > Stop-and-wait。

接下來分別對 GBN、SR、TCP 三者作說明：

GBN(Go-Back-N) 回溯 N

  • GBN 接收端無需暫存任何順序不正確的封包，因為 GBN 傳送端會重送所有未經確認的封包。
  • GBN 的單一封包錯誤，將導致需重送大量無需重送的封包，這是它的缺點之一。

GBN 傳送端重點

  • 累積式確認：收到來自接收端回傳序號 n 的 ACK，表示小於 n 的封包都已經正確收到。
  • 使用一個 Timer：綁定最早送出且未經確認的封包(Base)。
  • 逾時事件：Timeout 時，若還未收到最早送出封包所回傳的確認，則重送所有未經確認的封包 base ~ (nextseqnum - 1)。
  • 收到順序不正確的 ACK：不做任何事情。
  • 收到順序正確的 ACK：
    1. 將 base 設定為 ACK 的序號+1，造成窗格滑動，因此又稱 窗格滑動協定(Sliding-Window)。
    2. 若還有可用封包可傳送的請況下，則重新啟動Timer。
    3. 傳送新的封包。

情境舉例

設窗格大小為 3，且目前送出序號 0、1、2 封包，下個時間點收到 0 的 ACK 則窗格從原本的 [0、1、2] 滑動成 [1、2、3]， 然後送出序號 3 的封包。

GBN接收端重點

  • 收到正確順序的封包事件：回傳該封包序號的 ACK 給傳送端。
  • 收到錯誤順序的封包事件：回傳最後一次收到正確序號的 ACK 給傳送端。

SR(Selective Repeat) 選擇性重複

  • SR 傳送端只重送接收端未正確收到的封包，可能是遺失或毀損。
  • SR 會將脫序的封包暫存。
  • SR 的傳送端、接收端雙方的 window 位置 各自不同。
  • SR 窗格大小必須等於有限序號大小的一半。

為什麼窗格大小必須是序號大小的一半？

有限序號 0、1、2、3，窗格大小為 3，接收端收到 0、1、2，所以接收端的窗格觀點會從 [0、1、2]、3、0、1、2… 變成 0、1、2、[3、0、1]、2…。

此時假設接收端回傳給傳送端的 ACK 遺失時，將造成傳送端等待逾時，而重送第一批的 0、1、2 給接收端；這時候的接收端想 要的是第二批的 0、1 以及第一批的 3，會有錯亂的問題，要避免此問題發生，就必須讓窗格大小是序號的一半，往下看下一個例子。

同樣的情境，將窗格大小改為 2，接收端收到 0、1，接收端窗格觀點就會從 [0、1]、2、3、0、1、2…變成 0、1、[2、3]、0、1、2。 若回傳給傳送端的 ACK 遺失時，傳送端等待逾時會重送第一批的 0、1，這時候接收端就不會有前一個例子錯亂的問題。

SR傳送端重點

  • 逾時事件：每個封包都綁有 timer，當各個封包的 ACK 逾時未收到，則重送該封包。
  • 收到 ACK：
    1. 標記對應序號的封包為已確認。
    2. 若收到的 ACK 序號是 Base，則將 Base 移動到下個最小未經確認的封包上。
    3. 若窗格移動到了尚未傳送的封包上，則同時送出這些未被送出的可用封包。

對於第二點的範例

目前送出 0、1、2、3、4，已收到的 ACK 為1、2，因為序號 0 尚未收到 ACK，所以 base 會停留在 0，一旦之後收到 ACK 0，base會直接跳到 3，因為此時 0、1、2 都已經確認過了。

SR接收端重點

  • 接收到目前 window 內任一封包：
    1. 回傳收到的序號之 ACK 給傳送端。
    2. 若收到的序號不是 base，則將封包暫存。
    3. 若收到的序號是 base，將 base 與其後連續已收到的封包交由上層，並將 window 移動到最小預期收到的 位置上。例如：接收端窗格為 0、1、2、3、4，此時收到 1、2、3，將它們暫存起來，之後收到 0(base) ，則將 0、1、2、3 一次交給上層，並將 window 移動到4。
  • 收到 window 之前的封包事件：再傳一次收到的序號之 ACK 給傳送端，倘若不傳，傳送端的 window 將永遠無法移動。 (之所以收到 window 之前的封包，表示上一次回傳給傳送端的 ACK 可能遺失了， 使得傳送端等到 timeout 仍沒收到 ACK 才再發一次之前的封包過來。)
  • 收到其它封包的事件：忽略該封包。

TCP(Transmission Control Protocol)

  • TCP 傳送端只需要維護「最小已送出未經確認的封包之序號」及「下一個要傳送的封包之序號」
  • TCP 最多只重送一筆區段
  • TCP 之 ACK 與 GBN、SR 兩者的 ACK 不同，TCP 傳送端所發出的 ACK，表示期待下一次要收到的封包之序號， 而 GBN、SR 的 ACK 用來告知已經收到的封包之序號。
  • TCP 同 SR 會將脫序的封包暫存。
  • TCP 為累積式確認(也有某種 TCP 修正稱選擇性確認)。

TCP傳送端重點

  • 逾時事件：重送封包。
  • 收到重複三次 ACK(Duplicated Ack)：重送封包，又稱快速重送。因為接收端總是收到 非預期的封包，而連續回傳希望收到的封包之序號，此時傳送端就會立刻重送接收端所預期的封包 ，這將會在 timeout 前就送出。

TCP 接收端重點

  • 預期封包抵達事件：回傳下一次期望收到的封包序號 ACK。
  • 非預期封包抵達事件：暫存封包，送出期望收到的封包之序號 ACK。

比較 GBN、SR、TCP 的範例

假設 timeout 時間內足夠傳送5筆區段，包含回應的 ACK 被傳送端收到。 傳送端傳送給接收端的 5 個區段，當中有 2 個區段遺失，且最後接收端會收到所有的區段， 在上面兩個前提下，下列為 GBN、SR、TCP 三者傳送端、接收端的比較：

  • GBN
    • 傳送端：共送出9個區段(1、2、3、4、5)和補送的(2、3、4、5)
    • 接收端：回應8個ACK(1、1、1、1、2、3、4、5)
  • SR
    • 傳送端：共送出6個區段(1、2、3、4、5)和補送的(2)
    • 接收端：共回應5個ACK(1、3、4、5、2)
  • TCP
    • 傳送端：共送出6個區段(1、2、3、4、5)和快速重送的(2)
    • 接收端：共回應5個ACK(2、2、2、2、6)

附註

GBN、SR 觀點的 Window

window of SR and GBN

Base 表示最久未經確認的封包，nextseqnum 是窗格內最小未被傳送， 由上圖可定義出四種區段：

  • [0, base - 1] 區段：已傳輸，且已經過確認的區段。
  • [base, nextseqnum - 1] 區段：已傳輸，未經確認的區段。
  • [nextseqnum, base + n + 1] 區段：窗格內可使用但尚未送出的區段。
  • [base + n, ~] 區段：不在窗格內，也不可使用的區段。

GBN 傳送端觀點範例

假設以下號碼分別代表封包的狀態：

  1. 已傳送已收到確認
  2. 已傳送未收到確認
  3. 可使用尚未傳送
  4. 不可使用

111222333444 可推得：

  • 第一個 2 為 base。
  • 窗格範圍：222333，窗格大小為6。
  • GBN分隔明顯，window 內只有 2、3 且為連續。

SR傳送端觀點範例

假設以下號碼分別代表封包的狀態：

  1. 已傳送已收到確認
  2. 已傳送未收到確認
  3. 可使用尚未傳送
  4. 不可使用

111221121233344 可推得：

  • 第一個 2 為 base。
  • 窗格範圍：2211212333，窗格大小為 10。
  • SR 的 window 內交錯著 2、1。
  • 窗格範圍：從最小未經確認的封包~最大可用的送出封包。

SR接收端觀點範例

假設以下號碼分別代表封包的狀態：

  1. 已收到
  2. 預期卻未收到
  3. 未依序但已回傳ACK
  4. 窗格內仍未收到
  5. 不可使用

555677888999 可推得：

同前 SR 敘述 最小預期收到的位置， 因此窗格範圍為：677888，窗格大小為 6（與上一個傳送端沒有對應關係，不要混著看）。