計算機網路概論GBN、SR、TCP比較

Posted by JSON on September 12, 2013

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:
    • 將base設定為ACK序號+1,造成窗格滑動,因此又稱窗格滑動協定(Sliding-Window)
    • 若還有可用封包可傳送的請況下,重新啟動Timer
    • 傳送新的封包

情境:

窗格大小為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尚未確認,所以base會停留在0,一旦之後收到 ACK0,base會直接跳到,因為此時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可能遺失了, 使得傳送端等到timeout都沒收到ACK才再發一次之前的封包過來,所以再傳一次收到的序號之ACK給傳送端 ,倘若不傳,傳送端的window將無法移動。
  • 收到其它封包的事件:忽略該封包

TCP(Transmission Control Protocol)

  • TCP傳送端只需要維護「最小已送出未經確認的封包之序號」及「下一個要傳送的封包之序號」
  • TCP最多只重送一筆區段
  • TCP之ACK與GBN、SR的ACK不同,TCP傳送端所發出的ACK,表示期待下一次要收到的封包之序號, 而GBN、SR是用來確認已經收到的封包之序號。
  • 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(與上一個傳送端沒有對應關係,不要混著看)