滑動窗口

滑動窗口（Sliding window）是一種流量控制技術。早期的網絡通信中，通信雙方不會考慮網絡的擁擠情況直接發送數據。由於大家不知道網絡擁塞狀況，同時發送數據，導致中間節點阻塞掉包，誰也發不了數據，所以就有了滑動窗口機制來解決此問題。參見滑動窗口如何根據網絡擁塞發送數據仿真視頻。圖片是一個滑動窗口的實例：

滑動窗口協議是用來改善吞吐量的一種技術，即容許發送方在接收任何應答之前傳送附加的包。接收方告訴發送方在某一時刻能送多少包（稱窗口尺寸）。

TCP中採用滑動窗口來進行傳輸控制，滑動窗口的大小意味着接收方還有多大的緩衝區可以用於接收數據。發送方可以通過滑動窗口的大小來確定應該發送多少字節的數據。當滑動窗口為0時，發送方一般不能再發送數據包，但有兩種情況除外，一種情況是可以發送緊急數據，例如，允許用户終止在遠端機上的運行進程。另一種情況是發送方可以發送一個1字節的數據報來通知接收方重新聲明它希望接收的下一字節及發送方的滑動窗口大小。

滑動窗口協議的基本原理就是在任意時刻，發送方都維持了一個連續的允許發送的幀的序號，稱為發送窗口；同時，接收方也維持了一個連續的允許接收的幀的序號，稱為接收窗口。發送窗口和接收窗口的序號的上下界不一定要一樣，甚至大小也可以不同。不同的滑動窗口協議窗口大小一般不同。發送方窗口內的序列號代表了那些已經被髮送，但是還沒有被確認的幀，或者是那些可以被髮送的幀。

下面舉例説明，假設發送窗口尺寸為2，接收窗口尺寸為1：

分析：①初始態，發送方沒有幀發出，發送窗口前後沿相重合。接收方0號窗口打開，等待接收0號幀；②發送方打開0號窗口，表示已發出0幀但尚未確認返回信息。此時接收窗口狀態不變；③發送方打開0、1號窗口，表示0、1號幀均在等待確認之列。至此，發送方打開的窗口數已達規定限度，在未收到新的確認返回幀之前，發送方將暫停發送新的數據幀。接收窗口此時狀態仍未變；④接收方已收到0號幀，0號窗口關閉，1號窗口打開，表示準備接收1號幀。此時發送窗口狀態不變；⑤發送方收到接收方發來的0號幀確認返回信息，關閉0號窗口，表示從重發表中刪除0號幀。此時接收窗口狀態仍不變；⑥發送方繼續發送2號幀，2號窗口打開，表示2號幀也納入待確認之列。至此，發送方打開的窗口又已達規定限度，在未收到新的確認返回幀之前，發送方將暫停發送新的數據幀，此時接收窗口狀態仍不變；⑦接收方已收到1號幀，1號窗口關閉，2號窗口打開，表示準備接收2號幀。此時發送窗口狀態不變；⑧發送方收到接收方發來的1號幀收畢的確認信息，關閉1號窗口，表示從重發表中刪除1號幀。此時接收窗口狀態仍不變。

若從滑動窗口的觀點來統一看待1比特滑動窗口、後退n及選擇重傳三種協議，它們的差別僅在於各自窗口尺寸的大小不同而已。1比特滑動窗口協議：發送窗口=1，接收窗口=1；後退n協議：發送窗口>1，接收窗口=1；選擇重傳協議：發送窗口>1，接收窗口>1。

當發送窗口和接收窗口的大小固定為1時，滑動窗口協議退化為停等協議（stop-and-wait）。該協議規定發送方每發送一幀後就要停下來，等待接收方已正確接收的確認（acknowledgement）返回後才能繼續發送下一幀。由於接收方需要判斷接收到的幀是新發的幀還是重新發送的幀，因此發送方要為每一個幀加一個序號。由於停等協議規定只有一幀完全發送成功後才能發送新的幀，因而只用一比特來編號就夠了。其發送方和接收方運行的流程圖如圖所示。 ^[1] 

由於停等協議要為每一個幀進行確認後才繼續發送下一幀，大大降低了信道利用率，因此又提出了後退n協議。後退n協議中，發送方在發完一個數據幀後，不停下來等待應答幀，而是連續發送若干個數據幀，即使在連續發送過程中收到了接收方發來的應答幀，也可以繼續發送。且發送方在每發送完一個數據幀時都要設置超時定時器。只要在所設置的超時時間內仍未收到確認幀，就要重發相應的數據幀。如：當發送方發送了N個幀後，若發現該N幀的前一個幀在計時器超時後仍未返回其確認信息，則該幀被判為出錯或丟失，此時發送方就不得不重新發送出錯幀及其後的N幀。

從這裏不難看出，後退n協議一方面因連續發送數據幀而提高了效率，但另一方面，在重傳時又必須把原來已正確傳送過的數據幀進行重傳（僅因這些數據幀之前有一個數據幀出了錯），這種做法又使傳送效率降低。由此可見，若傳輸信道的傳輸質量很差因而誤碼率較大時，連續測協議不一定優於停止等待協議。此協議中的發送窗口的大小為k，接收窗口仍是1。

在後退n協議中，接收方若發現錯誤幀就不再接收後續的幀，即使是正確到達的幀，這顯然是一種浪費。另一種效率更高的策略是當接收方發現某幀出錯後，其後繼續送來的正確的幀雖然不能立即遞交給接收方的高層，但接收方仍可收下來，存放在一個緩衝區中，同時要求發送方重新傳送出錯的那一幀。一旦收到重新傳來的幀後，就可以原已存於緩衝區中的其餘幀一併按正確的順序遞交高層。這種方法稱為選擇重發（SELECTICE REPEAT），其工作過程如圖所示。顯然，選擇重發減少了浪費，但要求接收方有足夠大的緩衝區空間。

滑動窗口功能：確認、差錯控制、流量控制。

如果過多的源同時以很快的速度發送大量的數據包，而此時接收方並沒有如此高的接收數據的能力，因此極易導致網絡的擁塞。所以，為了控制發送方的發送速度，防止發送方並考慮到受發送緩衝區大小的制約等，要求對發送方已發出但尚未經確認的幀的數目加以限制，同時使網絡的傳輸效率得到提高，滑動窗口協議應運而生，它使得發送方可以在未收到確認的情況下，同時發送多個數據分組，由此大大提升了網絡吞吐量。

在任何基於自動重發請求進行錯誤控制的通信協議中，接收方必須確認收到的數據包。 如果發送方在合理的時間內沒有收到確認，則重發數據。沒有聽到確認的發送方不知道接收方是否實際接收到分組（數據可能在傳輸中丟失或損壞）。 如果錯誤檢測顯示損壞，則數據包將被接收方忽略，並且不會發送確認。 因為網絡傳輸的時延，將有大量時間被用於等待確認，導致傳輸效率低下。 ^[2] 

通過限制在任何給定時間可以發送或接收的數據包的數量，滑動窗口協議允許使用固定大小的序列號傳送無限數量的數據包。發送方側的術語“窗口”表示接收方尚未確認的分組總數的邏輯邊界。接收方在每個確認包中通知發送器當前的最大接收緩衝區大小（窗口邊界）。 TCP報頭使用16位字段向發送方報告接收窗口大小。因此，可以使用的最大窗口是2^16 = 64千字節。在慢啓動模式下，發送器以低分組計數器開始，並且在從接收方接收到確認分組之後增加每個傳輸中的分組數量。對於接收的每個ACK分組，該窗口通過一個分組（邏輯地）滑動以傳送一個新分組。當達到窗口閾值時，發送器發送一個包，用於接收到的一個ACK分組（確認分組）。如果窗口限制為10個數據包，則在慢啓動模式下，發送器可以開始發送一個數據包，後跟兩個數據包（發送兩個數據包之前必須接收一個數據包），其次是三個數據包等等，直到10個數據包。但是在達到10個分組之後，進一步的傳輸被限制為一個接收到的一個分組發送的分組。在仿真中，看起來好像窗口對於接收到的每個ACK分組移動一個分組距離。在接收方側，窗口也會為接收到的每個數據包移動一個數據包。滑動窗口方法可以確保網絡上的交通擁堵得以避免。應用層仍將提供傳輸到TCP的數據，而不用擔心網絡流量擁塞問題，因為發送方和接收方的TCP實現分組緩衝區的滑動窗口。窗口大小可能根據網絡流量而動態變化。

發送方和接收方分別具有當前序列號nt和nr。它們各自還有一個窗口大小wt和wr。窗口大小可能會根據網絡流量的變化而有所不同，但是在更簡單的實現中它們是固定的。窗口大小必須大於零才能進行任何操作。

通常情況下，nt是要發送到下一個分組，即尚未發送的第一分組的序列號。同樣地，nr尚未收到的第一個分組的序列號。這兩個序列號會隨着時間逐漸增加。

接收方還可以跟蹤未接收到的最高序列號，變量ns比接收到的最高序列號還多一。對於僅接受數據包（wr = 1）的簡單接收方，這與nr相同，但如果wr> 1，則可以更大。注意區別：已經收到nr以下的所有數據包，沒有接收到ns以上的任何數據包，在nr和ns之間，已經收到一些數據包。

當接收方接收到一個數據包時，它會適當地更新其變量，並用新的nr發送確認。發送方跟蹤其收到的最高確認。發送方知道已經接收到但不包括na的所有分組，但是對於na和ns之間的分組是不確定的,即na≤nr≤ns。

並且序列號總是符合na≤nr≤nx≤nt≤na+wt的規則,證明如下：

na≤nr：發送器接收到的最高確認不能高於接收方確認的最高nr。

nr≤ns：完全接收的數據包的範圍不能超出部分接收的數據包的結尾。

ns≤nt：接收到的最高報文不能高於發送的最高報文。

nt≤na + wt：發送的最高數據包同時受到接收到的最高確認和發送窗口大小的限制。

每當發送方具有要發送的數據時，它可以在最新的確認na之前傳輸序列號高達wt數據包。也就是説，只要nt

在沒有通信錯誤的情況下，發送方很快就會收到所有發送的數據包的確認信息，這等於nt。如果在合理的延遲之後不會發生這種情況，則發送方必須在na和nt之間重傳數據包。

每次接收到一個編號為x的數據包時，接收方檢查它是否落入接收窗口，nr≤x nr，則存儲數據包直到接收到所有先前的數據包為止。如果x≥ns，後者更新為ns = x + 1。

如果數據包的序列號不在接收窗口內，則接收方將丟棄該數據包，並且不修改nr或ns。無論數據包是否被接受，接收方發送包含當前nr的確認。 （確認還可以包括關於nr或ns之間接收的附加數據包的信息，但這隻能幫助效率。）

請注意，沒有必要讓接收窗口wr大於發送窗口wt，因為不需要擔心接收到永遠不會發送的數據包;有用範圍為1≤wr≤wt。 ^[3] 

TCP的特點之一是提供體積可變的滑動窗口機制，支持端到端的流量控制。TCP的窗口以字節為單位進行調整，以適應接收方的處理能力。處理過程如下：

TCP連接階段，雙方協商窗口尺寸，同時接收方預留數據緩存區；

發送方根據協商的結果，發送符合窗口尺寸的數據字節流，並等待對方的確認；

發送方根據確認信息，改變窗口的尺寸，增加或者減少發送未得到確認的字節流中的字節數。調整過程包括：如果出現發送擁塞，發送窗口縮小為原來的一半，同時將超時重傳的時間間隔擴大一倍。

滑動窗口機制為端到端設備間的數據傳輸提供了可靠的流量控制機制。然而，它只能在源端設備和目的端設備起作用，當網絡中間設備（例如路由器等）發生擁塞時，滑動窗口機制將不起作用。

滑動窗口協議以基於分組的數據傳輸協議為特徵。因此該協議適用於對按順序傳送分組的可靠性要求較高的環境，例如在數據鏈路層（OSI模型）以及傳輸控制協議（TCP）中。

增強應答的鏈路層重傳，在長線傳輸中，因軟故障造成的消息傳輸錯誤佔據了絕大部分，對於這些問題的解決可以是系統的可靠性大大提高。這種機制，向通過實現簡單、檢突發錯誤能力高的CRC碼的校驗進行錯誤檢查，再由相應的滑動窗口協議實現重傳恢復 ^[2]  。