滑動(dòng)窗口算法原理.doc

1. 滑動(dòng)窗口算法 -滑動(dòng)窗口算法工作過(guò)程如下。首先，發(fā)送方為每1幀賦一個(gè)序號(hào)（sequence number），記作S e q N u m ?，F(xiàn)在，讓我們忽略S e q N u m是由有限大小的頭部字段實(shí)現(xiàn)的事實(shí)，而假設(shè)它能無(wú)限增大。發(fā)送方維護(hù)3個(gè)變量：發(fā)送窗口大?。╯end window size），記作S W S ，給出發(fā)送方能夠發(fā) 送但未確認(rèn)的幀數(shù)的上界； L A R 表示最近收到的確認(rèn)幀（ last acknowledgement re c e i v e d）的序號(hào)；L F S 表示最近發(fā)送的幀（last frame sent）的序號(hào)，發(fā)送方還維持如下的不變式：LAR-LFRRWS 當(dāng)一個(gè)確認(rèn)到達(dá)時(shí)，發(fā)送方向右移動(dòng)L A R，從而允許發(fā)送方發(fā)送另一幀。同時(shí)，發(fā)送方為所發(fā)的每個(gè)幀設(shè)置一個(gè)定時(shí)器，如果定時(shí)器在A C K到達(dá)之前超時(shí)，則重發(fā)此幀。注意：發(fā)送方必須存儲(chǔ)最多S W S個(gè)幀，因?yàn)樵谒鼈兊玫酱_認(rèn)之前必須準(zhǔn)備重發(fā)。接收方維護(hù)下面3個(gè)變量：接收窗口大?。╮eceive window size），記為RW S，給出接收方所能接收的無(wú)序幀數(shù)目的上界； L A F表示可接收幀（l a rgest acceptable frame）的序號(hào)；L F R表示最近收到的幀（last frame re c e i v e d）的序號(hào)。接收方也維持如下不變式：LFS-LARSWS 當(dāng)一個(gè)具有順序號(hào)S e q N u m的幀到達(dá)時(shí)，接收方采取如下行動(dòng)：如果S e q N u mL F R或S e q N u m L A F，那么幀不在接收窗口內(nèi)，于是被丟棄；如果L F RSe q N u mL A F，那么幀在接收窗口內(nèi)，于是被接收?，F(xiàn)在接收方需要決定是否發(fā)送一個(gè)A C K。設(shè)S e q N u m To A C K表示未被確認(rèn)幀的最大序號(hào)，則序號(hào)小于或等于S e q N u m To A c k的幀都已收到。即使已經(jīng)收到更高序號(hào)的分組，接收方仍確認(rèn)S e q N u m To A c k的接收。這種確認(rèn)被稱(chēng)為是累積的（c u m u l a t i v e）。然后它設(shè)置L F R = S e q N u m To A c k，并調(diào)整L A F = L F R + RW S。例如，假設(shè)L F R= 5（即，上次接收方發(fā)送的A C K是為了確認(rèn)順序號(hào)5的），并且RWS = 4。這意味著L A F = 9。如果幀7和8到達(dá)，則存儲(chǔ)它們，因?yàn)樗鼈冊(cè)诮邮沾翱趦?nèi)。然而并不需要發(fā)送A C K，因?yàn)閹?還沒(méi)有到達(dá)。幀7和8被稱(chēng)為是錯(cuò)序到達(dá)的。（從技術(shù)上講，接收方可以在幀7和8到達(dá)時(shí)重發(fā)幀5的A C K。）如果幀6當(dāng)時(shí)到達(dá)了（或許它在第一次丟失后又重發(fā)從而晚到，或許它只是被延遲了），接收方確認(rèn)幀8，L F R置為8，L A F置為1 2。如果實(shí)際上幀6丟失了，則出現(xiàn)發(fā)送方超時(shí)，重發(fā)幀6。我們看到，當(dāng)發(fā)生超時(shí)時(shí)，傳輸數(shù)據(jù)量減少，這是因?yàn)榘l(fā)送方在幀6確認(rèn)之前不能向前移動(dòng)窗口。這意味著分組丟失時(shí)，此方案將不再保證管道滿(mǎn)載。注意：分組丟失時(shí)間越長(zhǎng)，這個(gè)問(wèn)題越嚴(yán)重。注意，在這個(gè)例子中，接收方可以在幀7剛一到達(dá)時(shí)就為幀6發(fā)送一個(gè)認(rèn)幀N A K（negative acknowl edgment）。然而，由于發(fā)送方的超時(shí)機(jī)制足以發(fā)現(xiàn)這種情況，發(fā)送N A K反而為發(fā)送方增加了復(fù)雜性，因此不必這樣做。正如我們已提到的，當(dāng)幀7和8到達(dá)時(shí)為幀5發(fā)送一個(gè)額外的A C K是合理的；在某些情況下，發(fā)送方可以使用重復(fù)的A C K作為一個(gè)幀丟失的線索。這兩種方法都允許早期的分組丟失檢測(cè)，有助于改進(jìn)性能。關(guān)于這個(gè)方案的另一個(gè)變種是使用選擇確認(rèn)（selective acknowledgements）。即，接收方能夠準(zhǔn)確地確認(rèn)那些已收到的幀，而不只是確認(rèn)按順序收到最高序號(hào)的幀。因此，在上例中，接收方能夠確認(rèn)幀7、8的接收。如果給發(fā)送方更多的信息，就能使其較容易地保持管道滿(mǎn)載，但增加了實(shí)現(xiàn)的復(fù)雜性。發(fā)送窗口大小是根據(jù)一段給定時(shí)間內(nèi)鏈路上有多少待確認(rèn)的幀來(lái)選擇的；對(duì)于一個(gè)給定的延遲與帶寬的乘積，S W S是容易計(jì)算的。另一方面，接收方可以將RW S設(shè)置為任何想要的值。通常的兩種設(shè)置是：RW S= 1，表示接收方不存儲(chǔ)任何錯(cuò)序到達(dá)的幀； RW S=S W S，表示接收方能夠緩存發(fā)送方傳輸?shù)娜魏螏Ｓ捎阱e(cuò)序到達(dá)的幀的數(shù)目不可能超過(guò)S W S個(gè)，所以設(shè)置RWS S W S沒(méi)有意義。2. 有限順序號(hào)和滑動(dòng)窗口 -現(xiàn)在我們?cè)賮?lái)討論算法中做過(guò)的一個(gè)簡(jiǎn)化，即假設(shè)序號(hào)是可以無(wú)限增大的。當(dāng)然，實(shí)際上是在一個(gè)有限的頭部字段中說(shuō)明一個(gè)幀的序號(hào)。例如，一個(gè)3比特字段意味著有8個(gè)可用序號(hào)0 7。因此序號(hào)必須可重用，或者說(shuō)序號(hào)能回繞。這就帶來(lái)了一個(gè)問(wèn)題：要能夠區(qū)別同一序號(hào)的不同次發(fā)送實(shí)例，這意味著可用序號(hào)的數(shù)目必須大于所允許的待確認(rèn)幀的數(shù)目。例如，停止等待算法允許一次有1個(gè)待確認(rèn)幀，并有2個(gè)不同的序號(hào)。假設(shè)序號(hào)空間中的序號(hào)數(shù)比待確認(rèn)的幀數(shù)大1，即S W S M A a x S e q N u m -1 ，其中M a x Seq N u m 是可用序號(hào)數(shù)。這就夠了嗎？答案取決于RW S 。如果RW S = 1，那么MaxSeqNumSWS+1是足夠了。如果RW S等于S W S，那么有一個(gè)只比發(fā)送窗口尺寸大1的M a x S e q N u m是不夠的。為看清這一點(diǎn)，考慮有8個(gè)序號(hào)0 7的情況，并且S W S = RW S = 7。假設(shè)發(fā)送方傳輸幀0 6，并且接收方成功接收，但A C K丟失。接收方現(xiàn)在希望接收幀7，0 5，但發(fā)送方超時(shí)，然后發(fā)送幀0 6。不幸的是，接收方期待的是第二次的幀0 5，得到的卻是第一次的幀0 5。這正是我們想避免的情況。結(jié)果是，當(dāng)RW S = S W S時(shí)，發(fā)送窗口的大小不能大于可用序號(hào)數(shù)的一半，或更準(zhǔn)確地說(shuō)，SWS h d r）轉(zhuǎn)化為能夠安全放在消息前面的字節(jié)串（ h b u f）。該例程（未給出）必須將頭部中的每一個(gè)整數(shù)字段轉(zhuǎn)化為網(wǎng)絡(luò)字節(jié)順序，并且去掉編譯程序加入C語(yǔ)言結(jié)構(gòu)中的任意填充。7 . 1節(jié)將詳細(xì)討論字節(jié)順序的問(wèn)題，但現(xiàn)在，假設(shè)該例程將多字整數(shù)中最高有效位放在最高地址字節(jié)就足夠了。這個(gè)例程的另一個(gè)復(fù)雜性是使用s e m Wa i t 和s e n dW i n d o w N o t F u l l 信號(hào)量。S e n dWi n d o w N o t F u l l被初始化為發(fā)送方滑動(dòng)窗口的大小S W S（未給出這一初始化）。發(fā)送方每傳輸一幀， s e m Wa i t操作將這個(gè)數(shù)減1，如果減小到0，則阻塞發(fā)送方進(jìn)程。每收到一個(gè)A C K，在d e l i v e r S W P中調(diào)用s e m S i g n a l操作（見(jiàn)下面）將此數(shù)加1，從而激活正在等待的發(fā)送方進(jìn)程。 在繼續(xù)介紹S W P的接收方之前，需要調(diào)整一個(gè)看上去不一致的地方。一方面，我們說(shuō)過(guò)，高層協(xié)議通過(guò)調(diào)用s e n d操作來(lái)請(qǐng)求低層協(xié)議的服務(wù)，所以我們就希望通過(guò)S W P發(fā)送消息的協(xié)議能夠調(diào)用s e n d（S W P, p a c k e t）。另一方面，用來(lái)實(shí)現(xiàn)S W P的發(fā)送操作的過(guò)程叫做s e n d S W P，并且它的第一個(gè)參數(shù)是一個(gè)狀態(tài)變量（ S w p S t a t e）。結(jié)果怎樣呢？答案是，操作系統(tǒng)提供了粘結(jié)代碼將對(duì)s e n d的一般調(diào)用轉(zhuǎn)化為對(duì)s e n d S W P的特定協(xié)議調(diào)用的粘結(jié)代碼。這個(gè)粘結(jié)代碼將s e n d的第一個(gè)參數(shù)（協(xié)議變量S W P）映射為一個(gè)指向s e n d S W P的函數(shù)指針和一個(gè)指向S W P工作時(shí)所需的協(xié)議狀態(tài)的指針。我們之所以通過(guò)一般函數(shù)調(diào)用使高層協(xié)議間接調(diào)用特定協(xié)議函數(shù)，是因?yàn)槲覀兿胂拗聘邔訁f(xié)議中對(duì)低層協(xié)議編碼的信息量。這使得將來(lái)能夠比較容易地改變協(xié)議圖的配置?，F(xiàn)在來(lái)看d e l i v e r操作的S W P的特定協(xié)議實(shí)現(xiàn)，它在過(guò)程d e l i v e r S W P中實(shí)現(xiàn)。這個(gè)例程實(shí)際上處理兩種不同類(lèi)型的輸入消息：本結(jié)點(diǎn)已發(fā)出幀的A C K和到達(dá)這個(gè)結(jié)點(diǎn)的數(shù)據(jù)幀。在某種意義上，這個(gè)例程的ACK部分是與send SWP中所給算法的發(fā)送方相對(duì)應(yīng)的。通過(guò)檢驗(yàn)頭部的F l a g s字段可以確定輸入的消息是ACK還是一個(gè)數(shù)據(jù)幀。注意，這種特殊的實(shí)現(xiàn)不支持?jǐn)?shù)據(jù)幀中捎帶A C K。當(dāng)輸入幀是一個(gè)ACK時(shí)，delive rSWP僅僅在發(fā)送隊(duì)列（send Q）中找到與此ACK相應(yīng)的位置（slot），取消超時(shí)事件，并且釋放保存在那一位置的幀。由于A C K可能是累積的，所以這項(xiàng)工作實(shí)際上是在一個(gè)循環(huán)中進(jìn)行的。對(duì)于這種情況值得注意的另一個(gè)問(wèn)題是子例程swp In Wind o w的調(diào)用。這個(gè)子例程在下面給出，它確保被確認(rèn)幀的序號(hào)是在發(fā)送方當(dāng)前希望收到的A C K的范圍之內(nèi)。當(dāng)輸入幀包含數(shù)據(jù)時(shí)， d e l i v e r S W P首先調(diào)用m s g S t r i p H d r和l o a d _ s w p _ h d r以便從幀中提取頭部。例程l o a d _ s w p _ h d r對(duì)應(yīng)著前面討論的s t o r e _ s w p _ h d r，它將一個(gè)字節(jié)串轉(zhuǎn)化為容納S W P頭部的C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)。然后d e l i v e r S W P調(diào)用s w p I n Wi n d o w以確保幀序號(hào)在期望的序號(hào)范圍內(nèi)。如果是這樣，例程在已收到的連續(xù)的幀的集合上循環(huán)，并通過(guò)調(diào)用d e l i v e r H L P例程將它們傳給上層協(xié)議。它也要向發(fā)送方發(fā)送累積的A C K，但卻是通過(guò)在接收隊(duì)列上循環(huán)來(lái)實(shí)現(xiàn)的（它沒(méi)有使用本節(jié)前面給出的s e q N u m To A c k變量）。 最后，s w p I n Window 是一個(gè)簡(jiǎn)單的子例程，它檢查一個(gè)給定的序號(hào)是否落在某個(gè)最大和最小順序號(hào)之間。 4. 幀順序和流量控制 -滑動(dòng)窗口協(xié)議可能是計(jì)算機(jī)網(wǎng)絡(luò)中最著名的算法。然而，關(guān)于該算法易產(chǎn)生混淆的是，它可以有三個(gè)不同的功能，第一個(gè)功能是本節(jié)的重點(diǎn)，即在不可靠鏈路上可靠地傳輸幀。（一般來(lái)說(shuō)，該算法被用于在一個(gè)不可靠的網(wǎng)絡(luò)上可靠地傳輸消息。）這是該算法的核心功能。滑動(dòng)窗口算法的第二個(gè)功能是用于保持幀的傳輸順序。這在接收方比較容易實(shí)現(xiàn)，因?yàn)槊總€(gè)幀有一個(gè)序號(hào)，接收方要保證已經(jīng)向上層協(xié)議傳遞了所有序號(hào)比當(dāng)前幀小的幀，才向上傳送該當(dāng)前幀。即，接收方緩存了（即沒(méi)有傳送）錯(cuò)序的幀。本節(jié)描述的滑動(dòng)窗口算法確實(shí)保持了幀的順序，盡管我們可以想象一個(gè)變異，即接收方?jīng)]有等待更早傳送的幀都到達(dá)就將幀傳給下一個(gè)協(xié)議。我們可以提出的一個(gè)問(wèn)題是：我們是否確實(shí)需要滑動(dòng)窗口協(xié)議來(lái)保持幀的順序，或者，這樣的功能在鏈路層是否是不必要的。不幸的是，我們還沒(méi)有看到足夠多的網(wǎng)絡(luò)體系結(jié)構(gòu)來(lái)回答這個(gè)問(wèn)題我們首先需要理解的是，點(diǎn)到點(diǎn)鏈路序列如何由交換機(jī)連接而形成一條端到端的路徑?；瑒?dòng)窗口算法的第三個(gè)功能是，它有時(shí)支持流量控制（f l o w c o n t ro l），它是一種接收方能夠控制發(fā)送方使其降低速度的反饋機(jī)制。這種機(jī)制用于抑制發(fā)送方發(fā)送速度過(guò)快，即抑制傳輸比接收方所能處理的更多的數(shù)據(jù)。這通常通過(guò)擴(kuò)展滑動(dòng)窗口協(xié)議完成，使接收方不僅確認(rèn)收到的幀，而且通知發(fā)送方它還可接收多少幀。可接收的幀數(shù)對(duì)應(yīng)著接收方空閑的緩沖區(qū)數(shù)。在按序傳遞的情況下，在將流量控制并入滑動(dòng)窗口協(xié)議之前，我們應(yīng)該確信流量控制在鏈路層是必要的。尚