滑動窗口算法

概述
滑動窗口實現了TCP流控制。首先明確滑動窗口的范疇：TCP是雙工的協議，會話的雙方都可以同時接收和發送數據。TCP會話的雙方都各自維護一個發送窗口和一個接收窗口。各自的接收窗口大小取決于應用、系統、硬件的限制（TCP傳輸速率不能大于應用的數據處理速率）。各自的發送窗口則要求取決于對端通告的接收窗口，要求相同。

滑動窗口解決的是流量控制的的問題，就是如果接收端和發送端對數據包的處理速度不同，如何讓雙方達成一致。接收端的緩存傳輸數據給應用層，但這個過程不一定是即時的，如果發送速度太快，會出現接收端數據overflow，流量控制解決的是這個問題。

窗口的概念
發送方的發送緩存內的數據都可以被分為4類:

1. 已發送，已收到ACK
2. 已發送，未收到ACK
3. 未發送，但允許發送
4. 未發送，但不允許發送

其中類型2和3都屬于發送窗口。

接收方的緩存數據分為3類：

1. 已接收
2. 未接收但準備接收
3. 未接收而且不準備接收

其中類型2屬于接收窗口。

窗口大小代表了設備一次能從對端處理多少數據，之后再傳給應用層。緩存傳給應用層的數據不能是亂序的，窗口機制保證了這一點。現實中，應用層可能無法立刻從緩存中讀取數據。

滑動機制
發送窗口只有收到發送窗口內字節的ACK確認，才會移動發送窗口的左邊界。

接收窗口只有在前面所有的段都確認的情況下才會移動左邊界。當在前面還有字節未接收但收到后面字節的情況下，窗口不會移動，并不對后續字節確認。以此確保對端會對這些數據重傳。

遵循快速重傳、累計確認、選擇確認等規則。

發送方發的window size = 8192;就是接收端最多發送8192字節，這個8192一般就是發送方接收緩存的大小。

從上面的過程中，我們可以得到以下結論：

1. TCP連接是通過數據包和ACK實現的，我們作為第三者可以看到雙方發包的過程，但接受者在收到之前不知道發送方發的是什么，同樣的，發送方在收到ACK前也不知道對方是否成功接收。

發送方沒有收到接收方發回的ACK，就不能向右滑動。假設發送方向接收方發了ABCD就滑動，只要對方沒收到A，就不能滑動，那么就會出現二者不同步的局面。

滑動窗口提高了信道利用率，TCP是發送報文段為單位的，假如每發一個報文就要等ACK，那么對于大數據包，等待時間就太長了。只要發送的報文在滑動窗口里面，不用等每個ACK回來就可以向右滑動。本例中，開始接收端空著AB，只有CD，此時不能滑動；之后接收到EF和H，直接向右滑動2位，不必等G到位。

窗口大小不能大于序號空間大小的一半。目的是為了不讓兩個窗口出現交迭，比如總大小為7，窗口大小都為4，接收窗口應當滑動4，但只剩3個序號，導致兩個窗口相互迭代。

有一種情況沒出現：發送方發ABCD，接收方都收到然后向右滑動，但回復的ACK包全丟了。發送方未收到任何ACK， timeout后會重發ABCD，此時的接收方按累計確認的原則，收到ABCD后只會重發D的ACK，發送方收到后向右滑動。

對比滑動窗口和擁塞窗口
滑動窗口是控制接收以及同步數據范圍的，通知發送端目前接收的數據范圍，用于流量控制，接收端使用。擁塞窗口是控制發送速率的，避免發的過多，發送端使用。因為tcp是全雙工，所以兩邊都有滑動窗口。
兩個窗口的維護是獨立的，滑動窗口主要由接收方反饋緩存情況來維護，擁塞窗口主要由發送方的擁塞控制算法檢測出的網絡擁塞程度來決定的。

擁塞窗口控制sender向connection傳輸數據的速率，使這個速率為網絡擁堵狀況的函數。

找到一個經典的問題：

（一）給定一組大小為n的整數數組，計算長度為k的子數組和的最大值。

比如

數組為：1，2，3，4

最大值為：3+4=7

數組為：-1，4，7，-3，8，5，-2，6

最大值為：7-3+8=12

想到最簡單思路，那就遍歷所有子數組唄，求和然后比較。

    int index = 0;// 記錄最大子數組第1個元素的索引，目前是0
    int maxSum = 0;// 記錄最大子數組和，目前是從左開始第1個子數組
    for (int i = 0; i < k; i++) {
        maxSum += array[i];
    }

    for (int i = 1; i <= array.length - k; i++) {// 遍歷所有子數組，求和并比較
        int curSum = 0;
        for (int j=0; j < k; j++) {// 計算當前子數組和
            curSum += array[i + j];
        }
        if (curSum > maxSum) {// 如果大于最大和，則記錄
            maxSum = curSum;
            index = i;
        }
    }

運用滑動窗口思路，遍歷時不嵌套循環計算所有值；外層遍歷相當于窗口向右滑動，每次減去失效值加上最新值，即為當前窗口的和，然后再比較。

復制代碼
int index = 0;// 記錄最大子數組第1個元素的索引，目前是0
int maxSum = 0;// 記錄最大子數組和，目前是從左開始第1個子數組
for (int i = 0; i < k; i++) {
maxSum += array[i];
}

    int curWindowSum = maxSum;
    for (int i = 1; i <= array.length - k; i++) {// 從下個元素開始，即窗口向右滑動
        curWindowSum = curWindowSum - array[i - 1] + array[k + i - 1];// 減去失效值，加上最新值
        if (curWindowSum > maxSum) {// 如果大于最大和，則記錄
            maxSum = curWindowSum;
            index = i;
        }
    }

復制代碼
可以看到代碼差不多，只不過在計算求和時，采取了滑動窗口技術(思路)，通過一減一加求和，消除了內部的循環。
注：這里為了突出語義，將變量名curSum改為curWindowSum