可靠數(shù)據(jù)傳輸原理

可靠數(shù)據(jù)傳輸原理的實(shí)現(xiàn)問(wèn)題不僅出現(xiàn)在運(yùn)輸層，也會(huì)出現(xiàn)在鏈路層和應(yīng)用層，如果要確定所有網(wǎng)絡(luò)中最為重要的“前十個(gè)”問(wèn)題排名的話，可靠數(shù)據(jù)傳輸原理將是名列榜首的候選者。

• 什么是可靠？不錯(cuò)、不丟、不亂
  下圖是可靠數(shù)據(jù)傳輸?shù)目蚣?。為上層?shí)體提供的服務(wù)抽象是：數(shù)據(jù)可以通過(guò)一條可靠的信道進(jìn)行傳輸。借助可靠信道，傳輸數(shù)據(jù)比特就不會(huì)受到損壞或丟失，而且所有的數(shù)據(jù)都是按照其發(fā)送順序進(jìn)行交付的。
  
  image

實(shí)現(xiàn)這種服務(wù)抽象是可靠數(shù)據(jù)傳輸協(xié)議的責(zé)任。由于可靠數(shù)據(jù)傳輸協(xié)議的下層可能是不可靠的，因此只是一項(xiàng)困難的任務(wù)。然而，就我們而言，我們可以將較低層直接視為不可靠的點(diǎn)對(duì)點(diǎn)信道。

• 本次的討論中漸進(jìn)地設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議的發(fā)送方和接收方
• 只考慮單向數(shù)據(jù)傳輸，但是控制信息能夠雙向流動(dòng)
• 利用狀態(tài)機(jī)（FSM）刻畫傳輸協(xié)議，F(xiàn)SM中的箭頭指示了協(xié)議從一個(gè)狀態(tài)變遷到另一個(gè)狀態(tài)。引起變遷的時(shí)間顯示在表示變遷的橫線上方，事件發(fā)生時(shí)所采取的工作顯示在橫線下方；

構(gòu)造可靠數(shù)據(jù)傳輸協(xié)議

rdt1.0:可靠信道上的可靠數(shù)據(jù)傳輸協(xié)議

• 底層信道完全可靠：不會(huì)發(fā)生錯(cuò)誤（bit error），不會(huì)丟失分組，并且不會(huì)亂序；
• 發(fā)送方和接收方的FSM獨(dú)立，不用進(jìn)行數(shù)據(jù)交換

發(fā)送方FSM

image

image

rdt2.0:產(chǎn)生位錯(cuò)誤的信道

• 傳輸?shù)倪^(guò)程中可能會(huì)產(chǎn)生位錯(cuò)誤（比特位翻轉(zhuǎn)）；
• 在該信道中僅有產(chǎn)生位錯(cuò)誤這一種情況

此時(shí)我們底層信道不可靠，可能產(chǎn)生位錯(cuò)誤，因此在接收方要判斷是否產(chǎn)生錯(cuò)誤，如果有錯(cuò)誤需要進(jìn)行恢復(fù)。在進(jìn)行的恢復(fù)的過(guò)程中僅有接收方是無(wú)法解決的。

• 辨別分組中是否有錯(cuò)誤：利用校驗(yàn)和檢測(cè)位錯(cuò)誤
• 如何從錯(cuò)誤中恢復(fù)？
  • 確認(rèn)機(jī)制（ACK）：接收方顯示的告知發(fā)送方分組已正確接收；
  • NAK：接收方顯示的告知發(fā)送方分組有錯(cuò)誤
  • 發(fā)送發(fā)收到NAK后，重傳分組

基于上述重傳機(jī)制的rdt協(xié)議稱為ARQ協(xié)議。因此通過(guò)與rdt1.0對(duì)比，rdt2.0中引入的新的機(jī)制主要有以下一些：

• 差錯(cuò)檢測(cè)
• 接收方反饋信息： ACK/NAK
• 重傳

下面是設(shè)計(jì)出的rdt2.0:FSM規(guī)約
發(fā)送方:

image

image

rdt2.1:發(fā)送方應(yīng)對(duì)ACK/NAK破壞

• rdt2.0存在缺陷：如果ACK/NAK消息發(fā)送錯(cuò)誤、被破壞：

  • 為ACK/NAK增加校驗(yàn)和，檢錯(cuò)并糾錯(cuò)：難度高；
  • 添加額外控制消息:額外控制信息可能壞掉；
  • 如果ACK/NAK壞掉，發(fā)送方重傳：不能簡(jiǎn)單重傳，可能產(chǎn)生重復(fù)分組

• 如何解決重復(fù)分組的問(wèn)題？

  • 序列號(hào)：發(fā)送方給每個(gè)分組增加序列號(hào)
  • 接收方丟棄重復(fù)分組

發(fā)送方：

image

接收方：

image

rdt2.2：無(wú)NAK消息協(xié)議

與rdt2.1的功能相同，但是只使用ACK
實(shí)現(xiàn)方案：

• 接收方通過(guò)ACK告知最后一個(gè)被正確接收的分組；
• 在ACK消息中顯示地加入被確認(rèn)分組的序列號(hào)
• 發(fā)送方在接收到重復(fù)ACK之后，采取與收到NAK消息相同的動(dòng)作：重傳當(dāng)前分組
  發(fā)送方：
  
  image
  
  接收方：
  
  image

rdt3.0: 信道既可能發(fā)生錯(cuò)誤，也可能丟失分組

方法：發(fā)送方等待"合理"的時(shí)間

• 如果沒(méi)有收到ACK,重傳
• 但是此時(shí)又會(huì)有新的問(wèn)題，合理的時(shí)間很確定，可能會(huì)有這樣的情況：如果分組或者ACK只是延遲，并沒(méi)有丟失。因此重傳就會(huì)引起重復(fù)的問(wèn)題，就需要之前的序列號(hào)的方案來(lái)解決。
  因此，在rdt3.0中我們需要增加定時(shí)器
  發(fā)送方：
  
  image
  
  此時(shí)對(duì)應(yīng)于下面的幾種情況：
  
  image

在這里插入圖片描述

流水線可靠數(shù)據(jù)傳輸協(xié)議

上面設(shè)計(jì)出來(lái)的rdt3.0雖然能夠正確的工作，但是性能很差。（關(guān)于性能具體的分析示例見(jiàn)《計(jì)算機(jī)網(wǎng)絡(luò)——自頂向下方法》第六版P145）此時(shí)設(shè)計(jì)的協(xié)議限制了物理資源的利用，因此協(xié)議必須要和硬件資源匹配，在計(jì)算機(jī)科學(xué)中稱為軟硬件協(xié)同設(shè)計(jì)。
解決性能問(wèn)題的一個(gè)簡(jiǎn)單方法就是不采用停等方式運(yùn)行，允許發(fā)送發(fā)發(fā)送多個(gè)分組無(wú)需等待確認(rèn)。如下圖所示，如果發(fā)送方可以在等待確認(rèn)之前就發(fā)送三個(gè)報(bào)文，其利用率基本上也會(huì)提高三倍。因?yàn)樵S多從發(fā)送方向接收方屬性的分組被看成是填充到一條流水線中，故這種技術(shù)也被稱為流水線。

image

• 必須增加序號(hào)范圍， 因?yàn)樵诿總€(gè)傳輸中的分組（不計(jì)算重傳的）必須有一個(gè)唯一的序號(hào)，而且也有許多在傳輸中未確認(rèn)的報(bào)文；
• 協(xié)議的發(fā)送方和接收方也許必須緩存多個(gè)分組。發(fā)送方最低限度應(yīng)當(dāng)能緩沖哪些已發(fā)送但是沒(méi)有確認(rèn)的分組，接收方或許也需要緩存哪些已經(jīng)已正確接收的分組；
• 所需的序號(hào)范圍和對(duì)緩沖的要求取決于數(shù)據(jù)傳輸協(xié)議如何處理丟失、損壞及延遲過(guò)大的分組

要想實(shí)現(xiàn)流水線機(jī)制，需要滑動(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é)議：回退N步(Go-Back-N, GBN）和選擇重傳（Select Repeat，SR)。