哈工大計(jì)算機(jī)網(wǎng)絡(luò)傳輸層詳解之：流水線機(jī)制與滑動窗口協(xié)議

• 哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議詳解之：可靠數(shù)據(jù)傳輸?shù)幕驹?/li>
• 哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議詳解之：TCP協(xié)議
• 哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議詳解之：擁塞控制原理剖析

在上一節(jié)中我們逐步分析了可靠傳輸協(xié)議的設(shè)計(jì)過程，最后講到rdt3.0的設(shè)計(jì)和實(shí)現(xiàn)機(jī)制。但是rdt3.0為了實(shí)現(xiàn)可靠性，犧牲了很大一部分性能，其中最主要的原因就在于停止等待協(xié)議，在發(fā)送完數(shù)據(jù)后，發(fā)送端需要等待至少RTT后才能收到ACK，期間什么都不能做。

因此，我們需要設(shè)計(jì)方案來解決這個(gè)問題，這就是本節(jié)所講述的內(nèi)容。

流水線機(jī)制：提高資源利用率

在之前的停止等待協(xié)議中，發(fā)送端每發(fā)送一個(gè)數(shù)據(jù)包，都會等待至少RTT的時(shí)間?，F(xiàn)在采用流水線機(jī)制，每一次發(fā)送端多發(fā)送幾個(gè)數(shù)據(jù)包，比如上圖中的發(fā)送3個(gè)數(shù)據(jù)包。即每次發(fā)送端發(fā)完3個(gè)數(shù)據(jù)包后，再執(zhí)行停止等待協(xié)議，此時(shí)的發(fā)送方利用率（發(fā)送方發(fā)送時(shí)間百分比）就相當(dāng)于原先的3倍。

流水線協(xié)議

現(xiàn)在利用流水線機(jī)制，允許發(fā)送方在發(fā)送完數(shù)據(jù)包后，不用立即停止等待，而是可以在發(fā)送多個(gè)數(shù)據(jù)包后，再執(zhí)行停止等待協(xié)議，等待每個(gè)數(shù)據(jù)包的ACK反饋。

允許發(fā)送方在收到ACK之前連續(xù)發(fā)送多個(gè)分組

• 需要更大的序列號范圍，只有原先的0和1顯然是不夠了
• 發(fā)送方和/或接收方需要更大的存儲空間以緩存分組。原來的接收方只需要一個(gè)分組的存儲空間，但是現(xiàn)在需要多個(gè)分組的緩存空間。

左邊就是只有一個(gè)數(shù)據(jù)包發(fā)送的過程。右圖就是流水線機(jī)制下，多個(gè)數(shù)據(jù)包的發(fā)送和接收。

滑動窗口協(xié)議

窗口：用來管理那些發(fā)送端已經(jīng)發(fā)出，但還未來得及確認(rèn)的數(shù)據(jù)包。

• 允許使用的序列號范圍（每個(gè)數(shù)據(jù)包都對于一個(gè)序列號，因此滑動窗口中是已發(fā)送的數(shù)據(jù)包，也就表示使用的序列號范圍）
• 窗口尺寸為N：最多有N個(gè)等待確認(rèn)的消息。N也表示發(fā)送端一次允許發(fā)送的最大數(shù)據(jù)包個(gè)數(shù)。

滑動窗口：隨著協(xié)議的運(yùn)行，窗口在序列號空間內(nèi)向前滑動

滑動窗口協(xié)議：GBN、SR

如上圖所示，窗口左邊表示的是已經(jīng)發(fā)送，且已經(jīng)得到ACK確認(rèn)的數(shù)據(jù)分組。 黃色部分表示已經(jīng)發(fā)送，帶還沒確認(rèn)的數(shù)據(jù)分組。藍(lán)色則表示還可以使用的序列號范圍（最大為N，藍(lán)色表示接下來發(fā)送可以使用的序列號范圍）。當(dāng)藍(lán)色部分用完后，就必須等待窗口內(nèi)的數(shù)據(jù)包得到ACK確認(rèn)后，窗口繼續(xù)右移，來發(fā)送加下來的序列號數(shù)據(jù)包。

接下來，我們分別對GBN和SR兩種滑動窗口協(xié)議進(jìn)行介紹，介紹其實(shí)現(xiàn)原理和區(qū)別，便于我們理解滑動窗口協(xié)議的改進(jìn)。

滑動窗口協(xié)議：Go-Back-N協(xié)議（GBN）

發(fā)送方

• 分組頭部包含k-bit序列號
• 窗口尺寸為N，最多允許N個(gè)分組未確認(rèn)。

如上所述，窗口左邊的綠色部分表示已經(jīng)獲得ACK確認(rèn)的數(shù)據(jù)分組。黃色的表示已經(jīng)發(fā)送，但未ACK確認(rèn)的分組，藍(lán)色部分表示繼續(xù)發(fā)送分組可使用的序列號范圍，比如此時(shí)如果需要再發(fā)送一個(gè)數(shù)據(jù)分組，使用的序列號就是圖中nextseqnum對于的序列號值。最右邊的白色是還不能使用的序列號，需要等待窗口滑動右移才能到達(dá)。

累計(jì)確認(rèn)機(jī)制

對于GBN協(xié)議來說，發(fā)送端對于ACK的確認(rèn)采用的是累計(jì)確認(rèn)的方式。

• ACK（n）：表示確認(rèn)到序列號n（包含n）的分組均已被正確接收。即n-1、n-2,…往前的分組都已經(jīng)被正確接收了。
• 為傳輸中的分組設(shè)置計(jì)數(shù)器（timer）
• 超時(shí)(timeout)時(shí)間：重傳序列號大于等于n，還未收到ACK的所有分組。

GBN發(fā)送方的有限狀態(tài)機(jī)示例如下圖所示：

• if(nextseqnum < base+N)表示如果下一個(gè)序列號小于窗口的最大范圍，說明還可以繼續(xù)發(fā)送數(shù)據(jù)包，則取nextseqnum的序列號來構(gòu)造數(shù)據(jù)包并發(fā)送。同時(shí)，如果在窗口的最左側(cè)時(shí)，啟動當(dāng)前窗口內(nèi)流水線發(fā)送數(shù)據(jù)包的定時(shí)器?？梢钥吹剑麄€(gè)窗口內(nèi)發(fā)送數(shù)據(jù)包時(shí)，只會有一個(gè)定時(shí)器。
• refuse_data：如果窗口內(nèi)的序列號已經(jīng)用光了，也就是發(fā)送的數(shù)據(jù)包序列號達(dá)到了窗口的最大值。此時(shí)，發(fā)送方再需要發(fā)送數(shù)據(jù)包時(shí)，會被拒絕refuse。
• timeout：如果觸發(fā)了timeout超時(shí)，則會從窗口最左側(cè)的數(shù)據(jù)包開始，逐個(gè)重發(fā)，知道窗口最右端。
• rdt_rcg && notcorrupt：由于是累計(jì)確認(rèn)，在收到ACK（n）后，表示認(rèn)到序列號n（包含n）的分組均已被正確接收，此時(shí)起始偏移base會更新為所收到的確認(rèn)號ACK(n)的值+1（n+1）。這里，也就是窗口滑動的原理過程了。

GBN接收方的有限狀態(tài)機(jī)示例如下圖所示：

ACK機(jī)制：發(fā)送擁有最高序列號的、已被正確接收的分組的ACK（累計(jì)重傳機(jī)制）

• 可能產(chǎn)生重復(fù)ACK
• 只需要記住唯一的expectedseqnum。因?yàn)榱魉€機(jī)制可能會使到達(dá)接收方的數(shù)據(jù)包序列號亂序，此時(shí)接收方只需記住期待接收的最大序列號即可，比如期待序列號為5，此時(shí)收到了一個(gè)序列號為7的數(shù)據(jù)包，此時(shí)GBN會直接丟棄掉這些已經(jīng)收到的但不是當(dāng)前期望的分組序號。丟棄完后，還是需要做ACK的，所以重新確認(rèn)序列號最大的按序到達(dá)的分組。比如上述例子的，收到序列號7，期望5，應(yīng)該確認(rèn)的是序列號4，因?yàn)?之前的都已經(jīng)收到了。

亂序到達(dá)的分組：

• 直接丟棄—>接收方?jīng)]有緩存
• 重新確認(rèn)序列號最大的、按序到達(dá)的分組

GBN示例

假定窗口的大小是4，所以在發(fā)送方可以發(fā)送pkt0、pkt1、pkt2、pkt3，發(fā)送完pkt3后達(dá)到了窗口的最大序列號，因此發(fā)送端開始停止等待ACK反饋。

前兩個(gè)pkt0、pkt1都正確到達(dá)了分組，pkt2在發(fā)送過程中丟失了，而pkt3也正確到達(dá)了接收端。在接收端接收到pkt0、pkt1之后，接收端期望的序列號expectedseqnum應(yīng)該為2，而此時(shí)pkt3分組到達(dá)了接收端，但不是接收端期望的序列號。按照上面的分析我們知道，此時(shí)接收端會丟棄序列號3對應(yīng)的分組，然后發(fā)送一個(gè)ACK1的返回（因?yàn)槠谕蛄刑柺?，所以發(fā)送ACK1表示序列號2前面的數(shù)據(jù)分組都收到了）。

但是這個(gè)ACK1在返回時(shí)也不幸丟失了。由于pkt1的分組和該分組的ACK1的反饋被成功接收到了，此時(shí)發(fā)送端的窗口就可以向右移動兩位，有了序列號來發(fā)送pkt4、pkt5。

在發(fā)送完pkt4、pkt5之后，由于pkt2的ACK一直沒有收到，所以發(fā)送端觸發(fā)了timeout超時(shí)，又由于上一次接收到的最大ACK確認(rèn)序列號為1，即序列號為1和1之前的都已經(jīng)確認(rèn)了，所以發(fā)送方會重發(fā)序列號為1之后的分組，即上圖中的pkt2、pkt3、pkt4、pkt5。對于接收方收到的重復(fù)分組，會根據(jù)序列號進(jìn)行去重，所以不怕分組重復(fù)。

練習(xí)題： 數(shù)據(jù)鏈路層采用后退N幀（GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號為0~7的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，若發(fā)送方只收到0，2，3號幀的確認(rèn)，則發(fā)送方下需要重發(fā)的幀數(shù)是多少？分別是哪幾個(gè)幀？

解： 根據(jù)GBN協(xié)議工作原理，GBN協(xié)議的確認(rèn)是累計(jì)確認(rèn)，由于發(fā)送端已經(jīng)得到的最大ACK確認(rèn)序列號為3，表示序列號3和之前的分組都已經(jīng)確認(rèn)（即使ACK1的確認(rèn)序列號可能在反饋途中丟失了）。因此，發(fā)送方需要重新下發(fā)的幀數(shù)是4個(gè)，依次分別是4、5、6、7號幀。

滑動窗口協(xié)議：Selective Repeat協(xié)議（SR）

GBN有什么缺陷？

通過上面的介紹也能發(fā)現(xiàn)，GBN一個(gè)比較明顯的缺陷就是，當(dāng)需要重傳時(shí)，可能一次會重傳很多個(gè)分組，比如當(dāng)某個(gè)序列號n的分組丟失時(shí)，發(fā)送端會重傳序列號n和n之后到窗口右側(cè)最大序列號之間的數(shù)據(jù)分組。 這會導(dǎo)致網(wǎng)絡(luò)中充斥著很多這些不必要的重復(fù)分組，造成網(wǎng)絡(luò)擁塞，性能變差。所以一個(gè)顯然的改進(jìn)就是，我們不使用累計(jì)確認(rèn)機(jī)制，而是對每個(gè)分組單個(gè)確認(rèn)，同時(shí)不丟棄那些亂序的分組，接收端緩存起來。

SR協(xié)議

接收方

• 接收方對每個(gè)分組單獨(dú)進(jìn)行確認(rèn)。只要這個(gè)分組到達(dá)，就會返回一個(gè)ACK確認(rèn)。這點(diǎn)跟GBN的不同在于，GBN的確認(rèn)是累計(jì)確認(rèn)，在確認(rèn)時(shí)會有一個(gè)期望序列號expectedseqnum，對于接收端接收到的分組序號不是期望序號的，是直接丟棄不返回ACK的。只有在是期望序號時(shí)，才返回對應(yīng)序號的ACK，并便是這個(gè)序號之前的分組都正確收到了，這是上面GBN采用的ACK累計(jì)確認(rèn)機(jī)制。
• 接收方設(shè)置緩存機(jī)制，緩存亂序到達(dá)的分組。 因?yàn)楝F(xiàn)在分組是亂序到達(dá)的，還不是一個(gè)完整的數(shù)據(jù)報(bào)文，所以不能直接向上交付，需要先緩存起來。
• 接收方也有一個(gè)窗口

發(fā)送方

• 發(fā)送方只重傳那些沒收到ACK的分組。
• 發(fā)送方為每個(gè)分組設(shè)置單獨(dú)的定時(shí)器。
• 發(fā)送窗口：包含N個(gè)連續(xù)的序列號，限制已發(fā)送且未確認(rèn)的分組。

SR協(xié)議中發(fā)送方和接收方的窗口如下所示：

圖（b）表示的是接收方的窗口。接收方的窗口大小也是N，窗口前面是那些已經(jīng)按序到達(dá)成功交付的數(shù)據(jù)分組。窗口里的灰色部分表示接收方期望收到的，但是還沒收到的分組序號。紅色的則表示那些亂序到達(dá)的分組，這些亂序到達(dá)的分組，此時(shí)接收方會緩存起來，并返回ACK。藍(lán)色的部分表示接收方可以接收的序列號范圍。

從上兩個(gè)圖可以發(fā)現(xiàn)，在SR協(xié)議中，發(fā)送方和接收方的窗口不是同步的，發(fā)送方的窗口可能是滯后于接收端的（因?yàn)榭赡苣承┮寻l(fā)送的分組還沒收到ACK）。

SR協(xié)議的整體邏輯如下所示：

• 對于發(fā)送方來說，如果窗口內(nèi)收到了序列號為N的ACK，且該序列號是窗口中最小序列號的還沒被ACK確認(rèn)的序列號，則此時(shí)該分組確認(rèn)后，窗口會向右滑動到下一個(gè)還沒確認(rèn)ACK的序列號最小的分組位置。
• 對于接收方來說，如果接收到的分組序列號是在接收窗口序列號范圍內(nèi)的，會對該分組返回ACK，如果這個(gè)分組是亂序到達(dá)的，則緩存起來。如果是按序到達(dá)的，則跟其它按序到達(dá)的分組拼接起來，并且如果這個(gè)分組序號是接收端窗口中的未接收的最小序號，則窗口向右移動到下一個(gè)還未接收的最小序號位置。
• 如果接收端接收到的分組序號不在接收端窗口范圍內(nèi)，同樣要發(fā)送ACK。因?yàn)檫@種情況可能是之前返回的ACK丟失了，發(fā)送端觸發(fā)了超時(shí)操作重傳了分組，因此這種情況仍然要重新發(fā)ACK。

SR協(xié)議示例

1. 上圖中，發(fā)送方連續(xù)發(fā)送pkt0~pkt3的數(shù)據(jù)分組，首先接收方接收接收到pkt0，向上層交付，并返回ACK0，同時(shí)窗口右移。pkt1同理。但是pkt2在發(fā)送過程中丟失了，接收方接收端亂序到達(dá)的pkt3。因此SR協(xié)議的獨(dú)立確認(rèn)機(jī)制，此時(shí)接收方會返回對pkt3的確認(rèn)ACK。
2. 當(dāng)發(fā)送方收到pkt0、pkt1的確認(rèn)ACK后，同樣的，窗口會右移，繼續(xù)發(fā)送數(shù)據(jù)pkt4、pkt5。由于pkt2的ACK一直沒有返回，因此發(fā)送方的窗口最左側(cè)移動到序號2的位置就不動了。
3. 在這個(gè)過程中，接收方會接收到發(fā)送方窗口右移后的pkt4、pkt5的數(shù)據(jù)分組，由于SR協(xié)議有緩存機(jī)制，因此會對亂序到達(dá)的分組緩存起來，并返回對應(yīng)序號的確認(rèn)ACK。但此時(shí)，由于窗口中序列號最小的pkt2還未接收到，所以接收端窗口不會右移。
4. 終于，發(fā)送端pkt2分組的定時(shí)器超時(shí)了，觸發(fā)重傳。
5. 等到pkt2到達(dá)接收端后，由于這個(gè)序號是窗口內(nèi)最小未到達(dá)的序號，并且其他序號的分組都已經(jīng)收到了，此時(shí)接收方會將窗口內(nèi)的分組一起交付給上層。同時(shí)窗口會右移到下一個(gè)未接收的最小序列號的位置，也就是pkt6的位置，如上右圖最下邊所示。
6. 對于發(fā)送端來說，第二次對于pkt2分組的確認(rèn)ACK被正確收到了，那么窗口也會右移到下一個(gè)最小未確認(rèn)ACK的序號所在的位置，也就是pkt6的位置。

SR困境

上圖給出了a、b兩種場景，圖中窗口大小是3，序列號只包括0、1、2、3四個(gè)序列號，循環(huán)使用。思考接收方能區(qū)分開上面兩種不同的場景嗎？

• 在（a）場景中，接收方對pkt0、1、2的ACK都丟失了，在超時(shí)后，發(fā)送端會重發(fā)pkt0
• 在（b）場景中，接收方在收到ack0、1確認(rèn)后，窗口右移，并繼續(xù)發(fā)送后面的pkt3、pkt0，而這時(shí)pkt3的分組丟失了。
• 兩種場景的共性在于，接收端的窗口位置一樣，而且在某一時(shí)刻，接收端都接收到了一個(gè)pkt0的分組。

那么，在（a）場景中發(fā)送方重發(fā)分組0，接收方收到后會如何處理？

從上帝視角我們直到，這兩種場景是不一樣的，（a）場景中的pkt0是重傳，而（b）場景下的分組是正常的數(shù)據(jù)分組。但是接收端并不能區(qū)分這兩種場景，就有可能導(dǎo)致錯(cuò)誤。比如在（a）場景下，接收端可能以為這次收到的pkt0是正常的數(shù)據(jù)分組進(jìn)行了接收，并按序向上交付。但此時(shí)，這個(gè)分組并不是正確按序到達(dá)的分組，就會導(dǎo)致上層數(shù)據(jù)解析錯(cuò)誤。

之所以會導(dǎo)致上述的問題，顯而易見，是由于我們的序號太少，而窗口尺寸相對序號又比較大。因此在SR協(xié)議中，需要考慮序號個(gè)數(shù)與窗口大小之間的關(guān)系。

序列號個(gè)數(shù)與窗口尺寸需滿足什么關(guān)系？

Ns+Nr <= 2k

上式中k表示序列號的位數(shù)，Ns表示發(fā)送方窗口尺寸，Nr表示接收方窗口尺寸。文章來源地址http://www.zghlxwxcb.cn/news/detail-497447.html

到了這里，關(guān)于哈工大計(jì)算機(jī)網(wǎng)絡(luò)傳輸層詳解之：流水線機(jī)制與滑動窗口協(xié)議的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！