可靠數據傳輸對於應用層、傳輸層、鏈路層都很重要,是網絡領域的Top10問題。
對於傳輸層來說,由於相鄰的網絡層是不可靠的,所以要在傳輸層實現可靠數據傳輸(rdt)就比較複雜。
那麼我們來了,究竟怎樣才是可靠?

我們將討論一下幾個方面的內容
信道的(不可靠)特性
可靠數據傳輸的需求
Rdt 1.0
Rdt 2.0, rdt 2.1, rdt 2.2
Rdt 3.0
流水線與滑動窗口協議
GBN
SR

什麼是可靠?

  • 不錯
    就是傳輸的數據包沒有錯誤
  • 不丟
    傳輸的數據包不丟失
  • 不亂
    傳輸的數據包順序要保持正確

image.png

為了更好的說明,我們採取漸進式的設計可靠數據傳輸的發送方和接收方。

我們考慮第一個版本的可靠數據傳輸

Rdt 1.0: 可靠信道上的可靠數據傳輸

假設
底層信道完全可靠

  • 不會發生錯誤(bit error)
  • 不會丟棄分組
    顯然有了這個假設的話,發送方和接收方只要能正確接收數據就可以了,所以他們是相互獨立的,因為發過來的數據保證一定是正確的。

Rdt 2.0: 產生位錯誤的信道

我們假設底層信道可能翻轉分組中的位(bit)

首先如何判斷錯誤,我們可以利用校驗和來判斷是否發生位錯誤
那麼發現了錯誤,我們該如何處理呢?
第一種思路當然是糾正錯誤,但是這樣實現的難度和代價都比較大,在計算機網絡中,我們一般都會採取第二種思路
第二種思路就是直接重傳,如果我們發現了錯誤,很自然,那我們就重傳一次,直到接受方收到正確的分組。
還有一個問題就是假設接收方發現了錯誤,如果告知發送方已經發生了錯誤呢?
其實處理起來也很簡單,就是向接收方發送一個信號,代表出現錯誤,如果沒錯誤就發送一個信號,表示沒錯誤。

如何從錯誤中恢復?

  • 確認機制(Acknowledgements, ACK): 接收方顯式地告知發送方分組已正確接收
  • NAK:接收方顯式地告知發送方分組有錯誤
  • 發送方收到NAK后,重傳分組
  • 基於這種重傳機制的rdt協議稱為ARQ(Automatic Repeat reQuest)協議

Rdt 2.0中引入的新機制

  • 差錯檢測
  • 接收方反饋控制消息: ACK/NAK
  • 重傳

下面兩個圖分別模擬了有錯誤和無錯誤場景:
無錯誤場景


image.png

有錯誤場景


image.png

Rdt 2.1: 發送方, 應對ACK/NAK破壞

我們看rdt2.0有什麼問題,我們知道確認信號也需要通過信道傳播,那麼如果ack,nck的信號發生了錯誤呢?發送方應該怎麼處理?
顯然發生了錯誤,我們就應該重傳
但是這裏,又有一個問題,接收方怎麼知道發送方這次新傳過來的是新的報文段還是因為ack出錯而重傳的報文段呢?顯然我們需要區分,上一個報文段和當前的報文段,我們給報文段編寫好序號就可以了,而且只需要0,1兩個序號,一個表示上次的報文段,一個表示新接受的。
這樣接收方如果收到0,就知道這次不是新的報文段,可能是上次ack出錯了,發送方無法確認,就重傳了上次的報文段,所以接收方需要丟掉這個報文段,然後再次傳一次ack確認信號,如果收到的是序號為1的報文段,則接收方直接接受就可以了。


image.png

Rdt 2.1 vs. Rdt 2.0

發送方:

  • 為每個分組增加了序列號
  • 兩個序列號(0, 1)就夠用,為什麼?
  • 需校驗ACK/NAK消息是否發生錯誤
  • 狀態數量翻倍
  • 狀態必須“記住”“當前”的分組序列號
    接收方:
  • 需判斷分組是否是重複
  • 當前所處狀態提供了期望收到分組的序列號
  • 注意:接收方無法知道ACK/NAK是否被發送方正確收到

Rdt 2.2: 無NAK消息協議

我們考慮一下我們真的需要兩個確認信號ack和nck么?
 與rdt 2.1功能相同,但是只使用ACK
如何實現?
 接收方通過ACK告知最後一個被正確接收的分組
 在ACK消息中顯式地加入被確認分組的序列號
 發送方收到重複ACK之後,採取與收到NAK消息相同的動作
 重傳當前分組


image.png

Rdt 3.0

到rdt2.2為止,我們基本解決了“不錯”的要求,即報文和確認信息在信道上發生了錯誤的話,我們都可以很好的解決,解決的方法其實就是重傳
那麼我們接下來就該解決不丟的問題。
如果信道既可能發生錯誤,也可能丟失分組,怎麼辦?
“校驗和 + 序列號 + ACK + 重傳”夠用嗎?
顯然是不夠用的’
我們假設這時候ack不是錯誤而是直接丟了,那麼發送方就會無限制的等着接收方的ack,同時接收方也會無限制的等着發送方的新報文。
這樣就陷入了類似死鎖的機制,如果不加以處理,那麼網絡就卡死在這裏了。
那麼我們該如何處理呢?
方法:發送方等待“合理”時間
 如果沒收到ACK,重傳
 如果分組或ACK只是延遲而不是丟了

  • 重傳會產生重複,序列號機制能夠處理
  • 接收方需在ACK中顯式告知所確認的分組

 需要定時器


image.png

image.png

rdt3.0效率

Rdt 3.0能夠正確工作,但性能很差
示例:1Gbps鏈路,15ms端到端傳播延遲,1KB分組


image.png

 發送方利用率:發送方發送時間百分比


image.png

 在1Gbps鏈路上每30毫秒才發送一個分組33KB/sec
 網絡協議限制了物理資源的利用

這樣低效率的原因是,我們採取的是停-等操作
就是說發送方發了一個數據包,就停下來了,直到得到來自接收方的確認才發送第二個,這樣就造成了很多的空餘時間都在空閑等待。

流水線機制與滑動窗口協議

為了改進停等機制所造成的效率低下,我們可以採用流水線的機制,一次發送多條報文段,充分利用空閑的時間


image.png

允許發送方在收到ACK之前連續發送多個分組
 更大的序列號範圍
 發送方和/或接收方需要更大的存儲空間以緩存分組


image.png

進一步的,我們採用滑動窗口協議,顧名思義,就是發送給定窗口大小的報文數,隨着報文被接收確認,同時窗口可以動態的向前滑動


image.png

滑動窗口協議: Sliding-window protocol
窗口
 允許使用的序列號範圍
 窗口尺寸為N:最多有N個等待確認的消息
滑動窗口
 隨着協議的運行,窗口在序列號空間內向前滑動
滑動窗口協議:GBN, SR

Go-Back-N(GBN)協議


image.png

如圖所示,窗口大小N,最多允許N個分組未確認。
ACK(n): 確認到序列號n(包含n)的分組均已被正確接收
 可能收到重複ACK
為沒收到確認的分組設置計時器(timer)
超時Timeout(n)事件: 重傳序列號大於等於n,還未收到ACK的所有分組
ACK機制: 發送擁有最高序列號的、已被正確接收的分組的ACK
 可能產生重複ACK
 只需要記住唯一的expectedseqnum
接收方是沒有緩存的,所以接收方對於亂序到達的分組直接丟棄,並且重新發送目前為止接收到的分組中序列號最大的按序到達的分組


image.png

簡單的習題:
 數據鏈路層採用後退N幀(GBN)協議,發送方已經發送了編號為
0~7的幀。當計時器超時時,若發送方只收到0、2、3號幀的確認
,則發送方需要重發的幀數是多少?分別是那幾個幀?
 解:根據GBN協議工作原理,GBN協議的確認是累積確認,所以
此時發送端需要重發的幀數是4個,依次分別是4、5、6、7號幀

Selective Repeat協議

GBN有什麼缺陷?
由於GBN接收方沒有緩存,對於非按序的分組直接丟棄,就會造成很多到達的分組由於順序亂了,卻白髮了,需要再次重新發送。
顯然為了提高效率,我們可以在接收方設置緩存,對於未按序達到的分組,先存起來,而不是直接丟棄。
這就是選擇重複協議的思想
接收方對每個分組單獨進行確認
 設置緩存機制,緩存亂序到達的分組
發送方只重傳那些沒收到ACK的分組
 為每個分組設置定時器
發送方窗口
 N個連續的序列號
 限制已發送且未確認的分組


image.png

image.png

從圖中我們可以看到,接收方是動態移動滑動窗口的,只有當窗口部分前面的全部正確接受並確認了,才向前移動。

可靠數據傳輸原理與協議回顧

信道的(不可靠)特性
可靠數據傳輸的需求
Rdt 1.0
Rdt 2.0, rdt 2.1, rdt 2.2
Rdt 3.0
流水線與滑動窗口協議
GBN
SR