点到点链路的滑动窗口协议
目錄
- 傳輸?shù)目煽啃?/li>
- ARQ算法一：停止—等待
- 算法
- 三種情形
- 分析
- ARQ算法二：滑動窗口
- 算法
- 發(fā)送方
- 接收方
- 例如
- 分析
- 序號的范圍
- 點到點傳輸
傳輸?shù)目煽啃?/h2>
??在通信過程中，幀的傳輸而可能出錯時，可以用像CRC這樣的差錯碼來檢測。但是雖然有些差錯碼功能很強，并且還能夠糾錯，但實際上由于開銷太大以至于無法處理網(wǎng)絡(luò)鏈路上發(fā)生的比特錯和成組差錯。即使使用糾錯碼，某些差錯因為過于嚴重仍需丟棄其對應(yīng)差錯幀，因此可靠的鏈路協(xié)議必須能以某種方式回復(fù)這些丟失的幀。
??通常使用兩種基本的機制——**確認（ackonwledegment）和超時（timeout）**的組合來實現(xiàn)差錯幀的重傳，這個策略叫做：自動請求重發(fā)（Automatic Repeat Request，簡稱ARQ）
- 確認：接收端發(fā)送確認信號ACK給發(fā)送端用以告知成功接收某一幀
- 超時：發(fā)送端長時間未收到確認信號，重傳該原始幀給接收端
?
?
ARQ算法一：停止—等待
算法
??stop-and-wait 算法是最簡單的ARQ算法，發(fā)送方傳輸一幀后，在傳輸下一幀前等待接受方發(fā)來的確認信號。如果在規(guī)定時間內(nèi)沒有接收到確認信號，則發(fā)送方超時，重傳原始幀。
?
三種情形
?分析
??在stop-and-wait 算法中，接受方的確認信號如果丟失或者遲到了，那么如上面后兩種情形一樣，發(fā)送方會超時并重傳原始幀，而接受方卻會誤以為收到的是下一幀。解決此問題的方法可以是給發(fā)送幀添加一個1比特的首部表示其序號，每一幀的序號在0、1間交替使用。
??stop-and-wait 算法的主要缺點是鏈路資源浪費。它允許發(fā)送方每次在鏈路上只有一個未確定幀，這可能遠遠低于鏈路容量。
?
?
ARQ算法二：滑動窗口
??考慮到stop-and-wait 算法的缺點，滑動窗口算法允許鏈路上同時傳輸?shù)膸瑪?shù)達到鏈路的容量上限，也就是說滑動窗口算法的發(fā)送端在接收到確認信號前可以發(fā)送不止一幀數(shù)據(jù)后才進入等待。
?
算法
發(fā)送方
發(fā)送方對每一幀賦予一個序號，記為SeqNum，并維護三個變量：
- LFS：最近發(fā)送的幀（last frame sent），即還未確認成功發(fā)送的幀中序號最大者
- LAR：最近收到的確認幀（last ackoneledgement received），即已確認成功發(fā)送的幀中序號最大者
- SWS：發(fā)送窗口大小（send window size），即鏈路容量允許的同時發(fā)送幀數(shù)上限
??發(fā)送窗口的大小是根據(jù)一段時間內(nèi)鏈路上有多少待傳輸?shù)膸瑏磉x擇的，可根據(jù)給定延遲帶寬積和幀的大小來計算得到。
??當確認到達時，發(fā)送方向右移動LAR，從而允許發(fā)送方發(fā)送另一幀。同時發(fā)送方為所發(fā)送的每個幀設(shè)置一個定時器用于檢測是否超時重傳，因此發(fā)送方必須緩存SWS個幀。
接收方
接受方記錄SeqNumToAck為當前已收到的連續(xù)序號幀中未回復(fù)ACK的最大序號，并維護三個變量：
- LAF：最大的可接收幀序號（largest accpetable frame）
- LFR：最后收到的幀序號（last frame received），是已經(jīng)發(fā)送過ACK的幀中最大序號
- RWS：接收窗口的大小（receive window size），即接受方所能接收的無序幀數(shù)上限
接收窗口RWS的大小可以設(shè)置為任意值，但通常有兩種：
當有新的數(shù)據(jù)幀發(fā)來時，接收方先做兩種處理：
??接受了新幀后，SeqNumToAck對應(yīng)移動，但應(yīng)明確一點：SeqNumToAck代表著接收到的連續(xù)序號的幀中序號最大者。如果序號不連續(xù)（序號低的幀有延遲或者丟失并待重傳），則SeqNumToAck暫時不會變化。
??一但當SeqNumToAck變化之后，接受方回傳一個SeqNumToAck對應(yīng)幀的ACK信號（而不是前面所有幀的），并賦值：LFR = SeqNumToAck，LAF = LFR + RWS。
例如
??LFR=5（即上次接受方發(fā)送的ACK是確認5號幀），并且RWS=4，意味著LFR=9。若7、8號幀到達，則被存入緩沖區(qū)，但SeqNumToAck不會變化，因為6號幀還沒到達。稱7和8號幀是錯序到達的。如果隨后6號幀到達了（延遲或者丟失后重傳來的），SeqNumToAck從5變成8，接收方回傳8號幀的ACK信號；如果6號幀一直不來，則出現(xiàn)發(fā)送方超時，引發(fā)重傳。
?
分析
??在上例中可以看到，當發(fā)生超時時，窗口的滑動就會停滯，傳輸數(shù)據(jù)量減少。這意味著當分組丟失時，此方案不再保證管道滿載，且分組丟失時間越長，這個問題越嚴重。
??同時在上例中，可以不只是確認按順序收到的最高序號的幀SeqNumToAck。就是說接收方在收到7、8號幀但是沒有6號幀時，不管SeqNumToAck有沒有變化，直接回傳7、8號幀的ACK信號來確認二者的接收，這樣能保證管道滿載，但是增加了實現(xiàn)的復(fù)雜性，這個機制叫做選擇確認。
?
序號的范圍
??由于幀首部的序號字段長度有限，不可能序號上限無窮大，因此幀的序號必須循環(huán)使用，這就帶來了一個問題：要保證同一時刻鏈路上一個序號唯一確認一個幀，要求可用序號數(shù)必須大于所允許的待確認幀的數(shù)量。例如上面stop-and-wait算法中允許一次有一個待確認幀，并有兩個不同序號。
對不同RWS，序號空間有不同要求：
??例如，有8個序號0~8，且RWS=SWS=7。假設(shè)發(fā)送方傳輸幀0~6，并且接收方成功接收，但是ACK丟失發(fā)送方?jīng)]收到，那么接收方期待收到幀7和下一輪的幀0~5，但是發(fā)送方因為沒收到ACK所以超時重傳本輪的幀0~6，也就是說此時必須把（本輪的0~6幀） 和 （幀7+下輪0~5幀）通過序號區(qū)分開來，否則就會誤識別。而這就要求序號必須要多于發(fā)送窗口大小的二倍。
?
點到點傳輸
??上面算法建立在“幀在傳輸過程過程中不重新排序”的假設(shè)基礎(chǔ)上，也就是點到點鏈路。如果是不同環(huán)境中的滑動窗口算法則需要設(shè)計其他規(guī)則。
總結(jié)
以上是生活随笔為你收集整理的点到点链路的滑动窗口协议的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【进程通信】Signal信号
- 下一篇： 波束管理 Beam Management