可靠數(shù)據(jù)傳輸對(duì)于應(yīng)用層往声、傳輸層、鏈路層都很重要若贮，是網(wǎng)絡(luò)領(lǐng)域的Top10問題省有。
對(duì)于傳輸層來說痒留，由于相鄰的網(wǎng)絡(luò)層是不可靠的，所以要在傳輸層實(shí)現(xiàn)可靠數(shù)據(jù)傳輸（rdt）就比較復(fù)雜蠢沿。
那么我們來了伸头，究竟怎樣才是可靠？

我們將討論一下幾個(gè)方面的內(nèi)容
?信道的(不可靠)特性
?可靠數(shù)據(jù)傳輸?shù)男枨?br> ?Rdt 1.0
?Rdt 2.0, rdt 2.1, rdt 2.2
?Rdt 3.0
?流水線與滑動(dòng)窗口協(xié)議
?GBN
?SR

什么是可靠舷蟀？

• 不錯(cuò)
  就是傳輸?shù)臄?shù)據(jù)包沒有錯(cuò)誤
• 不丟
  傳輸?shù)臄?shù)據(jù)包不丟失
• 不亂
  傳輸?shù)臄?shù)據(jù)包順序要保持正確

image.png

為了更好的說明恤磷，我們采取漸進(jìn)式的設(shè)計(jì)可靠數(shù)據(jù)傳輸?shù)陌l(fā)送方和接收方。

我們考慮第一個(gè)版本的可靠數(shù)據(jù)傳輸

Rdt 1.0: 可靠信道上的可靠數(shù)據(jù)傳輸

假設(shè)
** 底層信道完全可靠 **

• 不會(huì)發(fā)生錯(cuò)誤(bit error)
• 不會(huì)丟棄分組
  顯然有了這個(gè)假設(shè)的話野宜，發(fā)送方和接收方只要能正確接收數(shù)據(jù)就可以了扫步，所以他們是相互獨(dú)立的坐儿，因?yàn)榘l(fā)過來的數(shù)據(jù)保證一定是正確的抹镊。

Rdt 2.0: 產(chǎn)生位錯(cuò)誤的信道

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

首先如何判斷錯(cuò)誤，我們可以利用校驗(yàn)和來判斷是否發(fā)生位錯(cuò)誤
那么發(fā)現(xiàn)了錯(cuò)誤，我們?cè)撊绾翁幚砟兀?br> 第一種思路當(dāng)然是糾正錯(cuò)誤旬牲，但是這樣實(shí)現(xiàn)的難度和代價(jià)都比較大，在計(jì)算機(jī)網(wǎng)絡(luò)中搁吓，我們一般都會(huì)采取第二種思路
第二種思路就是直接重傳原茅，如果我們發(fā)現(xiàn)了錯(cuò)誤，很自然堕仔，那我們就重傳一次擂橘，直到接受方收到正確的分組。
還有一個(gè)問題就是假設(shè)接收方發(fā)現(xiàn)了錯(cuò)誤摩骨，如果告知發(fā)送方已經(jīng)發(fā)生了錯(cuò)誤呢通贞？
其實(shí)處理起來也很簡單，就是向接收方發(fā)送一個(gè)信號(hào)恼五，代表出現(xiàn)錯(cuò)誤昌罩，如果沒錯(cuò)誤就發(fā)送一個(gè)信號(hào)，表示沒錯(cuò)誤灾馒。

如何從錯(cuò)誤中恢復(fù)茎用？

• 確認(rèn)機(jī)制(Acknowledgements, ACK): 接收方顯式地告知發(fā)送方分組已正確接收
• NAK:接收方顯式地告知發(fā)送方分組有錯(cuò)誤
• 發(fā)送方收到NAK后，重傳分組
• 基于這種重傳機(jī)制的rdt協(xié)議稱為ARQ(Automatic Repeat reQuest)協(xié)議

Rdt 2.0中引入的新機(jī)制

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

下面兩個(gè)圖分別模擬了有錯(cuò)誤和無錯(cuò)誤場景：
無錯(cuò)誤場景

image.png

有錯(cuò)誤場景

image.png

Rdt 2.1: 發(fā)送方, 應(yīng)對(duì)ACK/NAK破壞

我們看rdt2.0有什么問題睬罗，我們知道確認(rèn)信號(hào)也需要通過信道傳播轨功，那么如果ack，nck的信號(hào)發(fā)生了錯(cuò)誤呢容达？發(fā)送方應(yīng)該怎么處理古涧？
顯然發(fā)生了錯(cuò)誤，我們就應(yīng)該重傳
但是這里花盐，又有一個(gè)問題羡滑，接收方怎么知道發(fā)送方這次新傳過來的是新的報(bào)文段還是因?yàn)閍ck出錯(cuò)而重傳的報(bào)文段呢圆米？顯然我們需要區(qū)分，上一個(gè)報(bào)文段和當(dāng)前的報(bào)文段啄栓，我們給報(bào)文段編寫好序號(hào)就可以了娄帖，而且只需要0，1兩個(gè)序號(hào)昙楚，一個(gè)表示上次的報(bào)文段近速，一個(gè)表示新接受的。
這樣接收方如果收到0堪旧，就知道這次不是新的報(bào)文段削葱，可能是上次ack出錯(cuò)了，發(fā)送方無法確認(rèn)淳梦，就重傳了上次的報(bào)文段析砸，所以接收方需要丟掉這個(gè)報(bào)文段，然后再次傳一次ack確認(rèn)信號(hào)爆袍，如果收到的是序號(hào)為1的報(bào)文段首繁，則接收方直接接受就可以了。

image.png

Rdt 2.1 vs. Rdt 2.0

發(fā)送方：

• 為每個(gè)分組增加了序列號(hào)
• 兩個(gè)序列號(hào)(0, 1)就夠用陨囊，為什么弦疮？
• 需校驗(yàn)ACK/NAK消息是否發(fā)生錯(cuò)誤
• 狀態(tài)數(shù)量翻倍
• 狀態(tài)必須“記住”“當(dāng)前”的分組序列號(hào)
  接收方:
• 需判斷分組是否是重復(fù)
• 當(dāng)前所處狀態(tài)提供了期望收到分組的序列號(hào)
• 注意：接收方無法知道ACK/NAK是否被發(fā)送方正確收到

Rdt 2.2: 無NAK消息協(xié)議

我們考慮一下我們真的需要兩個(gè)確認(rèn)信號(hào)ack和nck么？
? 與rdt 2.1功能相同蜘醋，但是只使用ACK
如何實(shí)現(xiàn)胁塞？
? 接收方通過ACK告知最后一個(gè)被正確接收的分組
? 在ACK消息中顯式地加入被確認(rèn)分組的序列號(hào)
? 發(fā)送方收到重復(fù)ACK之后，采取與收到NAK消息相同的動(dòng)作
? 重傳當(dāng)前分組

image.png

Rdt 3.0

到rdt2.2為止压语，我們基本解決了“不錯(cuò)”的要求啸罢，即報(bào)文和確認(rèn)信息在信道上發(fā)生了錯(cuò)誤的話，我們都可以很好的解決胎食，解決的方法其實(shí)就是重傳
那么我們接下來就該解決不丟的問題扰才。
如果信道既可能發(fā)生錯(cuò)誤，也可能丟失分組斥季，怎么辦训桶？
“校驗(yàn)和 + 序列號(hào) + ACK + 重傳”夠用嗎？
顯然是不夠用的’
我們假設(shè)這時(shí)候ack不是錯(cuò)誤而是直接丟了酣倾，那么發(fā)送方就會(huì)無限制的等著接收方的ack舵揭，同時(shí)接收方也會(huì)無限制的等著發(fā)送方的新報(bào)文。
這樣就陷入了類似死鎖的機(jī)制躁锡，如果不加以處理午绳，那么網(wǎng)絡(luò)就卡死在這里了。
那么我們?cè)撊绾翁幚砟兀?br> 方法：發(fā)送方等待“合理”時(shí)間
? 如果沒收到ACK映之，重傳
? 如果分組或ACK只是延遲而不是丟了

• 重傳會(huì)產(chǎn)生重復(fù)拦焚，序列號(hào)機(jī)制能夠處理
• 接收方需在ACK中顯式告知所確認(rèn)的分組

? 需要定時(shí)器

image.png

image.png

rdt3.0效率

?Rdt 3.0能夠正確工作蜡坊，但性能很差
?示例：1Gbps鏈路，15ms端到端傳播延遲赎败，1KB分組

image.png

? 發(fā)送方利用率：發(fā)送方發(fā)送時(shí)間百分比

image.png

? 在1Gbps鏈路上每30毫秒才發(fā)送一個(gè)分組?33KB/sec
? 網(wǎng)絡(luò)協(xié)議限制了物理資源的利用

這樣低效率的原因是秕衙，我們采取的是停-等操作
就是說發(fā)送方發(fā)了一個(gè)數(shù)據(jù)包，就停下來了僵刮，直到得到來自接收方的確認(rèn)才發(fā)送第二個(gè)据忘，這樣就造成了很多的空余時(shí)間都在空閑等待。

流水線機(jī)制與滑動(dòng)窗口協(xié)議

為了改進(jìn)停等機(jī)制所造成的效率低下搞糕，我們可以采用流水線的機(jī)制勇吊，一次發(fā)送多條報(bào)文段，充分利用空閑的時(shí)間

image.png

允許發(fā)送方在收到ACK之前連續(xù)發(fā)送多個(gè)分組
? 更大的序列號(hào)范圍
? 發(fā)送方和/或接收方需要更大的存儲(chǔ)空間以緩存分組

image.png

進(jìn)一步的窍仰，我們采用滑動(dòng)窗口協(xié)議汉规，顧名思義，就是發(fā)送給定窗口大小的報(bào)文數(shù)驹吮，隨著報(bào)文被接收確認(rèn)针史，同時(shí)窗口可以動(dòng)態(tài)的向前滑動(dòng)

image.png

?滑動(dòng)窗口協(xié)議: Sliding-window protocol
?窗口
? 允許使用的序列號(hào)范圍
? 窗口尺寸為N：最多有N個(gè)等待確認(rèn)的消息
?滑動(dòng)窗口
? 隨著協(xié)議的運(yùn)行，窗口在序列號(hào)空間內(nèi)向前滑動(dòng)
?滑動(dòng)窗口協(xié)議：GBN, SR

Go-Back-N(GBN)協(xié)議

image.png

如圖所示钥屈，窗口大小N,最多允許N個(gè)分組未確認(rèn)悟民。
ACK(n): 確認(rèn)到序列號(hào)n(包含n)的分組均已被正確接收
? 可能收到重復(fù)ACK
為沒收到確認(rèn)的分組設(shè)置計(jì)時(shí)器(timer)
?超時(shí)Timeout(n)事件: 重傳序列號(hào)大于等于n，還未收到ACK的所有分組
ACK機(jī)制: 發(fā)送擁有最高序列號(hào)的篷就、已被正確接收的分組的ACK
? 可能產(chǎn)生重復(fù)ACK
? 只需要記住唯一的expectedseqnum
接收方是沒有緩存的，所以接收方對(duì)于亂序到達(dá)的分組直接丟棄近忙，并且重新發(fā)送目前為止接收到的分組中序列號(hào)最大的按序到達(dá)的分組

image.png

簡單的習(xí)題：
? 數(shù)據(jù)鏈路層采用后退N幀（GBN）協(xié)議竭业，發(fā)送方已經(jīng)發(fā)送了編號(hào)為
0～7的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)及舍，若發(fā)送方只收到0未辆、2、3號(hào)幀的確認(rèn)
锯玛，則發(fā)送方需要重發(fā)的幀數(shù)是多少咐柜？分別是那幾個(gè)幀？
? 解：根據(jù)GBN協(xié)議工作原理攘残，GBN協(xié)議的確認(rèn)是累積確認(rèn)拙友，所以
此時(shí)發(fā)送端需要重發(fā)的幀數(shù)是4個(gè)，依次分別是4歼郭、5遗契、6、7號(hào)幀

Selective Repeat協(xié)議

GBN有什么缺陷病曾？
由于GBN接收方?jīng)]有緩存牍蜂，對(duì)于非按序的分組直接丟棄漾根，就會(huì)造成很多到達(dá)的分組由于順序亂了，卻白發(fā)了鲫竞，需要再次重新發(fā)送辐怕。
顯然為了提高效率，我們可以在接收方設(shè)置緩存从绘，對(duì)于未按序達(dá)到的分組秘蛇，先存起來，而不是直接丟棄顶考。
這就是選擇重復(fù)協(xié)議的思想
?接收方對(duì)每個(gè)分組單獨(dú)進(jìn)行確認(rèn)
? 設(shè)置緩存機(jī)制赁还，緩存亂序到達(dá)的分組
?發(fā)送方只重傳那些沒收到ACK的分組
? 為每個(gè)分組設(shè)置定時(shí)器
?發(fā)送方窗口
? N個(gè)連續(xù)的序列號(hào)
? 限制已發(fā)送且未確認(rèn)的分組

image.png

image.png

從圖中我們可以看到，接收方是動(dòng)態(tài)移動(dòng)滑動(dòng)窗口的驹沿，只有當(dāng)窗口部分前面的全部正確接受并確認(rèn)了艘策，才向前移動(dòng)。

可靠數(shù)據(jù)傳輸原理與協(xié)議回顧

?信道的(不可靠)特性
?可靠數(shù)據(jù)傳輸?shù)男枨?br> ?Rdt 1.0
?Rdt 2.0, rdt 2.1, rdt 2.2
?Rdt 3.0
?流水線與滑動(dòng)窗口協(xié)議
?GBN
?SR