滑動(dòng)窗口算法

概述
滑動(dòng)窗口實(shí)現(xiàn)了TCP流控制。首先明確滑動(dòng)窗口的范疇：TCP是雙工的協(xié)議，會(huì)話的雙方都可以同時(shí)接收和發(fā)送數(shù)據(jù)。TCP會(huì)話的雙方都各自維護(hù)一個(gè)發(fā)送窗口和一個(gè)接收窗口。各自的接收窗口大小取決于應(yīng)用、系統(tǒng)、硬件的限制（TCP傳輸速率不能大于應(yīng)用的數(shù)據(jù)處理速率）。各自的發(fā)送窗口則要求取決于對端通告的接收窗口，要求相同。

滑動(dòng)窗口解決的是流量控制的的問題，就是如果接收端和發(fā)送端對數(shù)據(jù)包的處理速度不同，如何讓雙方達(dá)成一致。接收端的緩存?zhèn)鬏敂?shù)據(jù)給應(yīng)用層，但這個(gè)過程不一定是即時(shí)的，如果發(fā)送速度太快，會(huì)出現(xiàn)接收端數(shù)據(jù)overflow，流量控制解決的是這個(gè)問題。

窗口的概念
發(fā)送方的發(fā)送緩存內(nèi)的數(shù)據(jù)都可以被分為4類:

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

其中類型2和3都屬于發(fā)送窗口。

接收方的緩存數(shù)據(jù)分為3類：

1. 已接收
2. 未接收但準(zhǔn)備接收
3. 未接收而且不準(zhǔn)備接收

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

窗口大小代表了設(shè)備一次能從對端處理多少數(shù)據(jù)，之后再傳給應(yīng)用層。緩存?zhèn)鹘o應(yīng)用層的數(shù)據(jù)不能是亂序的，窗口機(jī)制保證了這一點(diǎn)?，F(xiàn)實(shí)中，應(yīng)用層可能無法立刻從緩存中讀取數(shù)據(jù)。

滑動(dòng)機(jī)制
發(fā)送窗口只有收到發(fā)送窗口內(nèi)字節(jié)的ACK確認(rèn)，才會(huì)移動(dòng)發(fā)送窗口的左邊界。

接收窗口只有在前面所有的段都確認(rèn)的情況下才會(huì)移動(dòng)左邊界。當(dāng)在前面還有字節(jié)未接收但收到后面字節(jié)的情況下，窗口不會(huì)移動(dòng)，并不對后續(xù)字節(jié)確認(rèn)。以此確保對端會(huì)對這些數(shù)據(jù)重傳。

遵循快速重傳、累計(jì)確認(rèn)、選擇確認(rèn)等規(guī)則。

發(fā)送方發(fā)的window size = 8192;就是接收端最多發(fā)送8192字節(jié)，這個(gè)8192一般就是發(fā)送方接收緩存的大小。

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

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

發(fā)送方?jīng)]有收到接收方發(fā)回的ACK，就不能向右滑動(dòng)。假設(shè)發(fā)送方向接收方發(fā)了ABCD就滑動(dòng)，只要對方?jīng)]收到A，就不能滑動(dòng)，那么就會(huì)出現(xiàn)二者不同步的局面。

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

窗口大小不能大于序號空間大小的一半。目的是為了不讓兩個(gè)窗口出現(xiàn)交迭，比如總大小為7，窗口大小都為4，接收窗口應(yīng)當(dāng)滑動(dòng)4，但只剩3個(gè)序號，導(dǎo)致兩個(gè)窗口相互迭代。

有一種情況沒出現(xiàn)：發(fā)送方發(fā)ABCD，接收方都收到然后向右滑動(dòng)，但回復(fù)的ACK包全丟了。發(fā)送方未收到任何ACK， timeout后會(huì)重發(fā)ABCD，此時(shí)的接收方按累計(jì)確認(rèn)的原則，收到ABCD后只會(huì)重發(fā)D的ACK，發(fā)送方收到后向右滑動(dòng)。

對比滑動(dòng)窗口和擁塞窗口
滑動(dòng)窗口是控制接收以及同步數(shù)據(jù)范圍的，通知發(fā)送端目前接收的數(shù)據(jù)范圍，用于流量控制，接收端使用。擁塞窗口是控制發(fā)送速率的，避免發(fā)的過多，發(fā)送端使用。因?yàn)閠cp是全雙工，所以兩邊都有滑動(dòng)窗口。
兩個(gè)窗口的維護(hù)是獨(dú)立的，滑動(dòng)窗口主要由接收方反饋緩存情況來維護(hù)，擁塞窗口主要由發(fā)送方的擁塞控制算法檢測出的網(wǎng)絡(luò)擁塞程度來決定的。

擁塞窗口控制sender向connection傳輸數(shù)據(jù)的速率，使這個(gè)速率為網(wǎng)絡(luò)擁堵狀況的函數(shù)。

找到一個(gè)經(jīng)典的問題：

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

比如

數(shù)組為：1，2，3，4

最大值為：3+4=7

數(shù)組為：-1，4，7，-3，8，5，-2，6

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

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

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

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

運(yùn)用滑動(dòng)窗口思路，遍歷時(shí)不嵌套循環(huán)計(jì)算所有值；外層遍歷相當(dāng)于窗口向右滑動(dòng)，每次減去失效值加上最新值，即為當(dāng)前窗口的和，然后再比較。

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

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

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