加油！偷博仔
今天遇見兩首顧城的詩

黑夜給了我黑色眼睛
我卻用它尋找光明
————《一代人》 1979年4月

在你的門前
我堆起一個雪人
代表笨拙的我
把你久等
你拿出一顆棒糖
一顆甜甜的心
埋進雪里
說這樣就會高興
雪人沒有笑
一直沒作聲
直到春天的驕陽
把它融化干凈
人在哪呢
心在哪呢
小小的淚潭邊
只有蜜蜂
————《雪人》1980年2月

好，沉靜了心情，正片開始，

可靠資料傳輸原理，

一、可靠資料傳輸（rdt）的原理

? rdt（reliable data transfer)）在應用層、傳輸層和資料鏈路層都很很重要
? 是網路Top 10問題之一重要
什么才叫可靠呢，傳輸的資料，原原本本交付，不出錯不重復不失序不丟失

Reliable&& unreliable channel

1.1可靠資料傳輸：問題描述

在這里插入圖片描述
中間兩個大方框就是rdt物體，
這四個函式，分別是接收方和發送方rdt與上層、下層的介面

1.2可靠資料傳輸：問題描述（續）

我們將：
? 漸增式地開發可靠資料傳輸協議（ rdt ）的發送方和接收方
? 只考慮單向資料傳輸
? 但控制資訊是雙向流動的！
? 雙向的資料傳輸問題實際上是2個單向資料傳輸問題的綜合
? 使用有限狀態機 (FSM) 來描述發送方和接收方

所謂漸增式：
就是先假定可靠傳輸的條件一一具備，然后逐個假定條件不可靠，rdt逐個針對該不可靠條件，實作哪些機制，

然后采用有限狀態機來描述狀態的改變，

下面一步一步升級rdt

2.1Rdt1.0：在可靠信道上的可靠資料傳輸

Rdt1.0描述：

? 下層的信道是完全可靠的
? 沒有位元出錯
? 沒有分組丟失
? 發送方和接收方的FSM
? 發送方將資料發送到下層信道
? 接收方從下層信道接收資料

發送方：上層來了data，封裝成packet、下發packet；
接收方：下層來了packet，解封裝，上交data

這就相當于，rdt啥也不干，啥事下屬都干好了，rdt~~只管抽煙喝酒燙頭~~ （只管來什么發什么，送什么收什么）

2.2Rdt2.0：具有位元差錯的信道

Rdt2.0描述：

? 下層信道可能會出錯：將分組中的位元翻轉
? 用校驗和來檢測位元差錯

? 問題：怎樣從差錯中恢復：
? 確認(ACK， acknowledgment)：接收方顯式地告訴發送方分組已被正確接收
? 否定確認( NAK，negative acknowledgment): 接收方顯式地告訴發送方分組發生了差錯

發送方收到NAK后，發送方重傳分組

? rdt2.0中的新機制：采用差錯控制編碼進行差錯檢測
? 發送方差錯控制編碼、快取
? 接收方使用編碼檢錯
? 接收方的反饋：控制報文（ACK，NAK）：接收方→發送方
? 發送方收到反饋相應的動作

rdt2.0：FSM描述

發送方，有兩個狀態，等待上層呼叫和等待ACK或NAK

發送方有一個副本，以便檢錯重傳
發送方在第一個狀態，等待上層呼叫，來了一個data，計算checksum，封裝成packet，下發，
于是轉換成第二個狀態，等待ack或nak ，

接收方，只有一個狀態，

如果收到的packet（rcvpkt），是corrupt（腐敗的，這里就是有誤的）的，那么feedback NAK（udt_send(NAK)）.
如果notcorrupt，就解封裝(extract())，上交data（deliver_data(data)），并且feedback ACK（udt_send(ACK)）

所以現在，聰明的，你看懂了這個有限狀態機的描述形式吧，
那，就自己觀摩下面2個FSM的描述吧

rdt2.0：沒有差錯時的操作

rdt2.0：有差錯時

2.3rdt2.0的致命缺陷！-> rdt2.1

如果ACK/NAK出錯？
? 發送方不知道接收方發生了什么事情！
? 發送方如何做？ ? 重傳？可能重復 ? 不重傳？可能死鎖(或出錯)
? 需要引入新的機制: 序號(Sequence Number)
處理重復：
? 發送方在每個分組中加入序號
? 如果ACK/NAK出錯，發送方重傳當前分組
? 接收方丟棄（不發給上層）重復分組

rdt2.1：發送方處理出錯的ACK/NAK
從虛線的位置開始看，
此時，上層來的data除了data，checksum封裝到packet中，還有序號，

rdt2.1：接收方處理出錯的ACK/NAK

rdt2.1：討論

發送方：
? 在分組中加入序列號
? 兩個序列號（0，1）就足夠了: 一次只發送一個未經確認的分組
? 必須檢測ACK/NAK是否出錯（需要EDC ）
? 狀態數變成了兩倍: 必須記住當前分組的序列號為0還是1
接收方：
? 必須檢測接收到的分組是否是重復的
? 狀態會指示希望接收到的分組的序號為0還是1
? 注意：接收方并不知道發送方是否正確收到了其ACK/NAK
? 沒有安排確認的確認也沒有確認的確認的確認，
? 具體解釋見下頁

rdt2.1的運行
一張圖，明了啦！

2.3rdt2.2：無NAK的協議

rdt2.2 description:

? 功能同rdt2.1，但只使用ACK(ack 要編號）
? 接收方對最后正確接收的分組發ACK，以替代NAK? 接收方必須顯式地包含被正確接收分組的序號
? 當收到重復的ACK（如：再次收到ack0）時，發送方與收到NAK采取相同的動作：
重傳當前分組
? 為后面的一次發送多個資料單位做一個準備
? 一次能夠發送多個
? 每一個的應答都有：ACK，NACK；麻煩
? 用前一個資料單位的ACK，代替本資料單位的NAK
? 確認資訊減少一半，協議處理簡單

用前一個序號ack代替當前nak

rdt2.2的運行

rdt2.2：發送方和接收方片斷

2.4rdt3.0：具有位元差錯和分組丟失的信道

新的假設：
下層信道可能會丟失分組（資料或ACK）(好比之前說的路由器佇列排滿了，新來的就被drop掉)

? 會死鎖
? 機制還不夠處理這種狀況：
? 檢驗和
? 序列號
? ACK
? 重傳

方法：（超時重傳）

發送方等待ACK一段合理的時間
(鏈路層的timeout時間確定的傳輸層timeout時間是適應式的；所謂適應式的，現在我還不懂…鄭老師又說會在TCP的timeout設定那里去講)
? 發送端超時重傳：如果到時沒有收到ACK->重傳
? 問題：如果分組（或ACK ）只是被延遲了：
? 重傳將會導致資料重復，但利用序列號已經可以處理這個問題
? 接收方必須指明被正確接收的序列號
? 需要一個倒計數定時器

rdt3.0 發送方

注意注意，rdt3.0加入了start_timer動作和timeout事件，
rdt3.0的運行

rdt3.0的性能：
? rdt3.0可以作業，但鏈路容量比較大的情況下，性能很差
? 鏈路容量比較大，一次發一個PDU 的不能夠充分利用鏈路的傳輸能力

就好像交通規則（協議）規定，寬敞的（信道容量大）高速公路上（鏈路），每次只允許跑一臺車（1bit），或者一個車隊（1packet），正常情況下跑完全程高速， ack確認，然后再讓下臺車或下個車隊上高速跑，就產生高速公路（鏈路）利用率極低的情況，

信道容納bit的個數： 信道延時/一個bit的傳輸時間
往返傳播延時30ms，分組傳輸延時0.008ms
當物理資源的利用率將近100%，那么瓶頸就在于物理鏈路的帶寬了

rdt3.0：停——等操作（rdt3.0也是一種 “停止等待協議”）

那為了提高利用率，讓寬敞的信道忙起來，就… （當然如果信道不寬，一次發一個也許才是）

2.4.1流水線（pipeline）(提高鏈路利用率)

流水線： 允許發送方在未得到對方確認的情況下一次發送多個分組

? 必須增加序號的范圍:用多個bit表示分組的序號
? 在發送方/接收方要有緩沖區 （緩沖技術，對抗發送/接收速度不匹配的情況）
- 發送方緩沖：未得到確認，可能需要重傳；
- 接收方快取：上層用戶取用資料的速率≠接收到的資料速率；接收到的資料可能亂序，排序交付（可靠）

在這里插入圖片描述

? 兩種通用的流水線協議：回退N步(GBN)和選擇重傳(SR)

2.4.2通用（為后文協議鋪墊）：滑動視窗(slide window)協議

? 發送緩沖區
? 形式：記憶體中的一個區域，落入緩沖區的分組可以發送
? 功能：用于存放已發送，但是沒有未經確認的分組
? 必要性：需要重發時可用
? 發送緩沖區的大小：
一次最多可以發送多少個未經確認的分組
? 停止等待協議=1 ? 流水線協議>1，合理的值，不能很大，鏈路利用率不能>100%
? 發送緩沖區中的分組
? 未發送的：落入發送緩沖區的分組，可以連續發送出去；
? 已發送、等待確認的：發送緩沖區的分組只有得到確認才能洗掉

2.4.3 發送視窗滑動程序-相對表示方法

? 采用相對移動方式表示，分組不動
? 可緩沖范圍移動，代表一段可以發送的權力

在這里插入圖片描述

let me explain:
淺藍色：分組已發送且已確認，
粉紅色：分組已發送且未確認，
白色：分組未發送，
·
圖中“真正滑動程序”， 綠色線條（發送緩沖區）不動，數字佇列（分組）移動
相對滑動表示，真正滑動的相對滑動，

? 發送視窗：發送緩沖區內容的一個范圍 ，是發送緩沖區的一個子集
? 那些已發送但是未經確認分組的序號構成的空間
? 發送視窗的最大值<=發送緩沖區的值
? 一開始：沒有發送任何一個分組
? 后沿=前沿
? 之間為發送視窗的尺寸=0
? 每發送一個分組，前沿前移一個單位

發送視窗的移動->前沿移動

圖中前沿左邊的箭頭，應該隨著深藍色向右同步移動

前沿左邊的箭頭最后移動到位置4，所以此時發送視窗尺寸=5

發送視窗的移動->后沿移動

再看一個生動的發送視窗圖

2.4.4 滑動視窗(slide window)協議——接收視窗

? 接收視窗 (receiving window)=接識訓沖區

只有收到的分組序號落入接收視窗內才允許接收
若序號在接收視窗之外，則丟棄；
? 接收視窗尺寸Wr=1，則只能順序接收；
? 接收視窗尺寸Wr>1 ，則可以亂序接收
（但提交給上層的分組，要按序）

除了丟棄2號分組，還要回饋一個按順序接收的最高序號的ack，比方說此時ack = 1，
看下圖：

滑動，不能失序