iT邦幫忙

0

企業資料通訊Week7 (2) | rdt(reliable data transfer)[下]

rdt3.0

rdt3.0 開始考慮到packet loss的情形,它怎麼解決呢?
https://ithelp.ithome.com.tw/upload/images/20211109/20135414VMc7T2V3Y3.png
喔喔~原來是採用"倒數計時"的方式,sender每送一個封包就會設定一個timer,如果超過時間還沒收到receiver的回饋,sender就會重傳該封包。如果receiver有回饋,但可能因為網路太慢使得ACK遲到sender會如何?sender還是重傳啊!於是receiver就會收到重複的封包,不過沒關係,有sequence number就可以辨認哪個是重複的封包。

注意這裡,rdt3.0的重傳機制只綁定在timer身上,可以看紅色圈起來的地方(圖中描述ACK壞掉或是ACK編號錯誤)
https://ithelp.ithome.com.tw/upload/images/20211109/20135414VnnpNQdanj.png
這裡也是rdt2.2與rdt3.0另外一個差別,這個意思是回饋如果是錯的sender也不重傳、不停止倒數,直等到timerout才重傳(rdt2.2收到錯誤的回饋就會重傳)。

幾種狀況

下圖分別為正常情況與sender packet loss
https://ithelp.ithome.com.tw/upload/images/20211109/20135414eJKFQcJVtF.png
sender 等到timerout 重傳

而這是ACK中途loss
https://ithelp.ithome.com.tw/upload/images/20211109/20135414axZRB91iAL.png
sender 等到timerout 重傳,receiver收到重複的封包,於是再傳一次ACK。

這是回饋晚到的情形,比較複雜一點,這會導致雙方的時間不一致,所以會多送幾次封包與ACK
https://ithelp.ithome.com.tw/upload/images/20211109/20135414IleeQN5a46.png

rdt3.0性能

它也是採用 stop and wait 的方式,中間在等回饋的時候sender除了倒數計時之外都沒做事。
https://ithelp.ithome.com.tw/upload/images/20211109/20135414MljiDk0Oqn.png
注:1RTT 大約等於 兩個propagation delay(sender發出封包的最後一個bit到sender收到ACK的時間);L/R 是 transmition delay
注意receiver要等到收到最後一個packet的bit才會發出ACK。

假設RTT是30,sender完整發出一個封包是0.008所以一個回合sender使用效率只有0.008/30.008,使用率很差。
怎麼改良呢?請繼續看~

Pipelined protocols

所以我們又想到一個方法,如果一次可以送很多封包就不用花時間等那麼多次了!
使用"in flight"(在途,就是還未被確認的packet)的概念。
有兩個特色:

  • 它有一個未被確認封包的上限 N (WindowSize)
  • 有buffering(緩衝)機制
    Pipelined protocols 主要分兩類:(1)go-back-N (2)selective repeat
    如果在理想的狀態下,它的使用效率可達100%,因為可以一邊傳一邊收。

https://ithelp.ithome.com.tw/upload/images/20211109/20135414fPJVMqG0pK.png

1.go-back-N (GBN)

下圖的框框是一個WindowSize
https://ithelp.ithome.com.tw/upload/images/20211109/20135414bm2OS9oorF.png
每一根長長的代表一個segment(請容我叫它封包QUQ)

  • 綠色的是送出且被checked部分
  • 黃色的是已經送出但還沒被checked部分
  • 框框內藍色的是還沒被送出,但還可以再送的空間
  • 白色的是還不能送的,因為go-back-N對於未確認的封包有WindowSize的上限

名詞解釋:

  • send_base:最老的未被確認封包
  • nextseqnum:下一個準備要傳的封包

go-back-N 特色

  • timer: 這go-back-N的 timer 會設定在send_base上面,並等待receiver 送 ACK(n)。
  • cumulative ACK: 甚麼是ACK(n)?
    舉個例子,如果ACK(7)就代表第七個封包以下(包含)都沒問題,所以這也稱**“cumulative
    ACK”**!
  • timeout的處理:sender會從send_base直到最後的未確認封包都重送,如果Window是滿的就會重送N個封包(最糟的狀況),這也是為甚麼它叫go-back-N。
  • 如果中間有缺失:舉例,8號封包不見了,但是sender送的9、10、11都是正常的,receiver還是只會一直送ACK(7)。
    之後window滿的就不能送、卡在那裏等timeout,從8號封包到 8+N-1號封包都會重送。

流程

sender方
https://ithelp.ithome.com.tw/upload/images/20211109/20135414mIJICvxbHh.png
注:

  • 收到ACK(N),window就會往右移,直到base=N+1
  • nexthttps://ithelp.ithome.com.tw/upload/images/20211109/20135414mzfD1QiJiG.pngseqnum>=base+N 代表window已經滿了,sender就不會再接收上層傳下來的封包

receiver方
https://ithelp.ithome.com.tw/upload/images/20211109/2013541483gJ4yUQeP.png

看下圖,2號封包loss,receiver一直痴痴地等著二號封包,非二號封包就丟掉,然後等到timeout,整個window的封包都重傳了!
https://ithelp.ithome.com.tw/upload/images/20211109/20135414vOXso7xY8z.png

你會不會覺得 go-back-N 有一種「一顆老鼠屎,壞了一鍋粥」的感覺?

2.Selective repeat

不同於 go-back-N,Selective repeat 每一個送出的封包都有綁定timer,為甚麼它要這麼做?
是的,當其中一個封包有缺失就只要送該封包就好。
https://ithelp.ithome.com.tw/upload/images/20211109/20135414wQBBz9BfeX.png

這裡要注意,Selective repeat 的receiver有window buffer,而 go-back-N 只有sender 有 window buffer
https://ithelp.ithome.com.tw/upload/images/20211109/20135414BzPFfePDsP.png

https://ithelp.ithome.com.tw/upload/images/20211109/20135414qnnAwel55z.png
雖然Selective repeat可以少重送封包,但要多設timer,資源消耗也不少。
所以兩種方法各有利弊。

這裡就簡單介紹完 reliable data transfer ,考試加油!!

思考:

  • 為甚麼需要可靠傳書協定(rdt)?
  • Selective repeat 與 go-back-N 的差別?
  • rdt2.0 與 rdt2.1 差別?
  • 拿幾張A4紙,學到多少還記得?一邊講一邊寫出來吧!

尚未有邦友留言

立即登入留言