流水線可靠資料傳輸協定
如上篇文章所述所述的rdt3.0協定是一個功能正确的協定，但是因為它是停止等待協定，是以它的的性能并不高。它對信道的使用率十分低，為解決這個問題的簡單方法便是：不使用停等方式運作，允許發送方發送多個分組而無需等待确認。
采用流水線技術對可靠資料傳輸也産生了一些影響：
- 必須增加序号範圍，因為每個輸送中的分組（不計重傳的）必須有一個唯一的序号，而且也許有多個在輸送中未被确認的封包。
- 協定的發送方和接收方兩端也許必須緩存多個分組。
- 所需序号範圍和對緩沖的要求取決于資料傳輸協定如何處理丢失、損壞及延時過大的分組。解決流水線差錯恢複的兩種基本辦法是： 回退N步（Go-Back-N,GBN） 和 選擇重傳（Selective Repeat,SR） 。
回退N步（GBN）
在GBN協定中，允許發送發發送多個分組（當有多個分組可用時）而不需要等待确認，但是它受限于流水線中為确認分組數不能超過某個最大允許數N。可操作此處的GBN Java小程式檢視GBN運作過程。
下圖（來自《計算機網絡 自定向下方法》）顯示了發送方看到的GBN協定的序号範圍。
base代表最早的未确認的分組，nextseqnum代表最小的未使用的序号（即下一個待發分組序号）。
序号範圍可以分成四段，[0,base-1]段内的序号對應于已經發送并被确認的分組，[base,nextseqnum-1]代表已被發送但未被确認的分組，[nextseqnum,base+N-1]段内的序号能用于那些即将要被發送的分組，最後大于等于base+N的序号是不能被使用的
那些已被發送但還未被确認的分組的許可序号範圍可以被看成是一個在序号範圍長度為N的視窗。
随着協定的進行，搞視窗序号空間向前滑動。是以，N常被稱為視窗長度（window size）,GBN協定也被稱為
滑動視窗協定（sliding-window protocol）在此我們限定的視窗長度N，而不是讓分組數為無限大是有兩個原因①流量控制②TCP擁塞控制
如果分組序号字段的比特數為k,那麼序号範圍就是[0,2k-1],在一個有限的序号範圍内，所有涉及序号的運算必須使用模2k運算。 GBN發送方必須響應三種類型的事件：
- 上層的調用 當上層調用分組發送時，發送方首先檢查發送視窗是否已滿，即是否含有N個已發送但是未被确認的分組。如果視窗未滿，則産生一個分組并将其發送，并更新相應變量。如果視窗已滿，發送方隻需将資料傳回給上層，隐式訓示上層該視窗已滿。然後上層可能過一會兒在試試。在實際實作中，發送方可能會緩存這些資料，或者使用同步機制允許上層在僅當視窗不滿是才調用分組發送。
- 收到一個ACK 在GBN協定中，對序号為n的分組采用 累積确認(cumulative acknowledgment) 方式，表明接收方已正确接收到序号為n的以前且包括n在内的所有分組。
- 逾時事件
協定的名字“回退N步”源于出現丢失和時延過長的分組時發送方的行為。
發送方采用一個定時器，可作為最早發送但未被确認的分組的定時器。如果收到一個ACK，但是仍有已發送但是未被确認的分組，定時器被重新啟動。如果沒有已發送但是未被确認的分組，該定時器被終止。
如果一個序号為n的分組被正确接收并且是按序的，接收方為分組n發送一個ACK，并将該分組的資料部分交給上層。其他情況，發送方丢棄該分組，并未最近按序接收的分組重新發送ACK。
接收方丢棄所有失序分組。分組n丢失，發送發會重傳分組n以及分組n後面的分組，接收方不必緩存失序分組後面的分組。接收方需要維護下一個按序接收的分組序号。
下圖為視窗長度為4的GBN協定運作情況。
選擇重傳
GBN也存在着一些性能問題，單個的分組出現差錯就會引起GBN重傳大量不必要重傳的分組。在信道差錯率很高時，流水線可能會被不必要重傳的分組所充斥。可操作此處SR Java小程式檢視SR運作流程。
SR協定通過讓發送方僅重傳那些它懷疑在接受方出錯（丢失或受損）的分組而避免不必要的重傳。
下圖（來自《計算機網絡 自定向下方法》）顯示了SR協定中發送方和接收方的序号範圍。
在SR協定中發送方和接收方所采取得動作可見下文描述。
- 從上層接收到資料 從上層接收到資料後，SR發送方檢查下一個可用于該分組的序号。如果該序号位于發送方的視窗内，則将資料打包并發送；否則就像再GBN中一樣，要麼将資料換粗，要麼傳回給上層以便以後傳輸。
- 逾時 定時器在此用來防止丢失分組。但是，SR中每個分組都要有自己的邏輯定時器。
- 收到ACK
如果收到ACK,倘若該分組序号在視窗内，SR發送方就将那個被确認的分組标記為已接收。
如果該分組的序号等于send_base，則視窗基序号向前移動到具有最小序号的未被确認分組處。
如果視窗移動了并且有序号落在視窗内的未發送分組，則發送這些分組。
SR接收方将确認一個正确接收的分組而不管其是否按序。失序的分組将被緩存，知道所有丢失分組皆被收到為止，這時才将一批分組按序傳遞給上層。
- 序号在[rcv_base,rcv_base+N-1]内的分組被正确接收
在此情況下，收到的分組落在接收方的視窗内，一個選擇ACK被回送給發送方。
如果該分組以前沒有被接收到過在，則緩存該分組。
如果該分組的序号等于基序号，則該分組以及以前緩存的序号連續的分組傳遞給上層。
然後，接收視窗按向前移動分組的編号向上傳遞這些分組。
- 序号在[rcv_base-N,rcv_base-1]内的分組被正确收到
在此情況下，必須産生一個ACK,即使該分組時接收方以前已确認的分組。
要意識到這是非常重要的，假設接收方以前就接收了send_base分組，現在接收到重傳的不回送ACK，那麼發送方視窗就永遠也不會向前滑動！
- 其他情況，忽略該分組
SR協定中發送方視窗和接收方視窗并不總是一緻的。這會引出關于序号範圍的一個問題。
在有限的序号範圍的實作裡，如果SR接收方視窗太大并且發送方和接收方視窗間的不同步，便會造成發送方這邊
新分組序号與舊分組序号重複使用。導緻無法辨析該序号代表的是一個新分組還是舊分組。
SR的視窗長度應限制在小于等于序号空間大小的一半。 小結一下可靠資料傳輸機制中使用到的技術:檢驗和、定時器、序号、确認、否定确認、視窗/流水線
此文為《計算機網絡 自頂向下方法》學習筆記2
每天進步一點點，不要停止前進的腳步~