1. 從“停等”到“流水線”為什么我們需要選擇重傳協(xié)議如果你寫過網絡編程或者調試過TCP連接大概率遇到過“丟包”和“重傳”這兩個詞。在數據鏈路層和傳輸層可靠傳輸是基石。最早的“停等協(xié)議”Stop-and-Wait簡單直接發(fā)一幀等一個確認ACK收到后再發(fā)下一幀。這就像兩個人用對講機你說一句“完畢”必須等對方回一句“收到”才能說下一句。在網絡質量尚可的局域網里這種方式勉強夠用。但一旦把場景放到廣域網或者帶寬稍高、延遲稍大的環(huán)境里停等協(xié)議的效率問題就暴露無遺。它的信道利用率低得可憐計算公式是U Td / (Td RTT Ta)其中Td是發(fā)送數據時間RTT是往返時延Ta是發(fā)送確認時間。在高速、高延遲的鏈路上Td可能很短但RTT很長導致大部分時間信道都在空等帶寬被白白浪費。這就像用萬噸巨輪一次只運一個集裝箱船跑得再快大部分時間也在等裝貨卸貨。于是“滑動窗口協(xié)議”登場了。它允許發(fā)送方在收到確認前連續(xù)發(fā)送多個數據幀將信道“管道化”極大地提高了利用率。滑動窗口協(xié)議主要有兩種回退N幀Go-Back-N, GBN和選擇重傳Selective Repeat, SR。GBN協(xié)議相對簡單發(fā)送方維護一個發(fā)送窗口按序發(fā)送接收方只按序接收一旦發(fā)現某幀出錯或丟失就丟棄該幀及之后所有幀發(fā)送方需要從出錯幀開始全部重傳。這就像流水線上一個零件裝錯了整條線都得停下來從這個零件開始全部返工。而選擇重傳協(xié)議SR則更加“精明”和“寬容”。它的核心思想是接收方可以緩存亂序到達但正確的幀只要求發(fā)送方重傳真正丟失或出錯的那一幀。這解決了GBN協(xié)議中“一個錯誤株連九族”的弊端在錯誤率較高的信道中比如早期的無線網絡、衛(wèi)星鏈路優(yōu)勢明顯。今天雖然TCP等高層協(xié)議有更復雜的擁塞控制但SR協(xié)議的思想——選擇性確認與重傳——依然是其重要組成部分。理解SR不僅是理解計算機網絡課本上的一個算法更是理解現代可靠傳輸協(xié)議設計哲學的一把鑰匙。2. SR協(xié)議的核心機制發(fā)送與接收窗口如何協(xié)同工作選擇重傳協(xié)議的精髓在于發(fā)送方和接收方窗口的獨立與協(xié)同。它們不再是GBN中那種強耦合的同步關系而是各自維護狀態(tài)通過確認機制進行松耦合的交互。2.1 發(fā)送方不只是個無情的發(fā)送機器發(fā)送方維護著三個關鍵的數據結構發(fā)送窗口Send Window, SWND 一個固定大小的、允許已發(fā)送但未被確認的幀的序號范圍。假設窗口大小為N序號從0開始那么在任何時刻發(fā)送方只能發(fā)送序號落在[send_base, send_base N - 1]這個區(qū)間內的幀。send_base指向最早已發(fā)送但未確認的幀。定時器Timer 在GBN中通常只有一個定時器用于最早的未確認幀。而在SR中每個已發(fā)送但未確認的幀都需要一個獨立的定時器。這是SR能實現“選擇性”重傳的關鍵。當某個幀的定時器超時發(fā)送方只重傳這一幀然后重啟該幀的定時器。確認狀態(tài)緩存 記錄哪些幀已被確認ACKed。通常用一個布爾數組或位圖來實現。發(fā)送方的動作可以分解為以下幾個驅動事件上層調用發(fā)送數據 檢查下一個要發(fā)送的序號next_seq_num是否在發(fā)送窗口內。如果在則封裝數據幀并發(fā)送啟動該幀的獨立定時器然后next_seq_num加一。如果不在則緩存數據或通知上層窗口已滿。收到ACK 這是最有趣的部分。SR協(xié)議允許接收方發(fā)送累計確認但更典型的是使用選擇性確認SACK。假設收到對序號n的ACK。如果n在發(fā)送窗口內即send_base n send_base N發(fā)送方會標記該幀為已確認。如果n恰好等于send_base即確認了窗口最左端的幀那么發(fā)送方會將send_base向右移動到當前窗口內最小未確認的序號。這相當于窗口向前“滑動”了。無論n是否等于send_base只要該幀被確認就停止該幀的定時器。定時器超時 當序號為n的幀定時器超時發(fā)送方僅重傳這一幀并重啟該幀的定時器。這是與GBN最本質的區(qū)別。這里有一個關鍵細節(jié)窗口大小N和序號空間大小必須滿足一定關系否則會造成歧義。我們稍后在“序號空間與窗口大小的約束”一節(jié)會詳細討論。2.2 接收方一個有序的緩存管理員接收方的邏輯比發(fā)送方更復雜一些因為它要處理亂序到達的幀。接收窗口Receive Window, RWND 同樣是一個固定大小為N的窗口期望接收的幀序號范圍是[rcv_base, rcv_base N - 1]。任何序號落在這個窗口內的幀都會被接收方處理窗口外的幀會被直接丟棄并可能引發(fā)一個ACK用于幫助發(fā)送方同步。緩存區(qū)Buffer 一個能容納至少N個幀的緩存區(qū)用于存放亂序到達但正確的幀。交付隊列 用于向上層按序交付數據。接收方的動作分解收到序號為n的幀情況A幀在接收窗口內且正確rcv_base n rcv_base N發(fā)送一個針對該幀的ACKACK n。如果該幀是新的之前沒緩存過則將其緩存。如果該幀恰好是期望的幀即n rcv_base接收方會檢查緩存從rcv_base開始連續(xù)地向上層交付所有已緩存的、按序的幀。每交付一幀rcv_base就加一接收窗口隨之向右滑動。這個過程會一直持續(xù)直到遇到第一個未緩存的序號為止。情況B幀在接收窗口內但出錯 直接丟棄。在SR中接收方通常不會發(fā)送否定確認NAK而是等待發(fā)送方該幀的定時器超時。當然有些SR變種會使用NAK來加速重傳。情況C幀在接收窗口左側n rcv_base 這說明接收方已經交付了該幀并且窗口已經滑過。此時接收方必須再發(fā)送一個ACK n。為什么因為發(fā)送方可能丟失了之前對這個幀的ACK這個重復的ACK能幫助發(fā)送方知道該幀已被正確接收從而避免不必要的重傳。情況D幀在接收窗口右側n rcv_base N 幀已超出接收方當前能處理的范疇直接丟棄。這通常意味著發(fā)送方和接收方窗口出現了不同步。接收方的設計體現了SR的智能它利用緩存容忍亂序通過按序交付保證上層語義并通過ACK機制包括對舊幀的重復ACK來積極協(xié)助發(fā)送方維護連接狀態(tài)。3. 關鍵問題深度剖析序號、窗口與定時器理解了基本流程我們來看幾個讓SR協(xié)議真正穩(wěn)定工作的關鍵設計點這些也是面試和實際理解中的高頻考點。3.1 序號空間與窗口大小的約束為什么N必須小于等于序號空間的一半這是一個經典的、必須搞清楚的約束條件。我們用一個反例來說明。假設序號空間很小只有0, 1, 2, 3即2比特模4運算而發(fā)送/接收窗口大小N 3?？紤]如下場景初始狀態(tài)發(fā)送方和接收方窗口都是[0, 1, 2]。發(fā)送方發(fā)送了幀0, 1, 2接收方都收到了并發(fā)送了ACK 0, ACK 1, ACK 2。但ACK 0和ACK 1在網絡中丟失了只有ACK 2到達。發(fā)送方收到ACK 2窗口滑動。現在發(fā)送窗口變?yōu)閇3, 0, 1]因為模4運算3之后是0。send_base現在是3不對這里有個關鍵send_base必須移動到最小的未確認幀。由于ACK 0和ACK 1丟失發(fā)送方認為幀0和幀1未確認所以send_base仍然是0窗口實際上無法滑動但為了繼續(xù)通信協(xié)議必須允許發(fā)送新數據。假設經過一段時間發(fā)送方超時重傳了幀0舊的幀0。此時接收方的窗口已經因為收到了0,1,2而滑動到了[3, 0, 1]。它現在期待的是幀3, 0, 1。當重傳的舊幀0到達時它的序號0正好落在接收方當前窗口[3, 0, 1]內接收方無法區(qū)分這個幀0是新的屬于下一個輪回還是舊的重傳。它會錯誤地將其作為新幀接收導致數據錯誤。問題的根源在于當窗口大小N等于或大于序號空間大小時窗口向前滑動后新舊兩個輪回的序號范圍會產生重疊接收方無法區(qū)分。因此必須保證發(fā)送窗口大小 接收窗口大小 序號空間大小。在SR中通常雙方窗口大小相等即N N 2^kk是序號比特數所以N 2^(k-1)。也就是說窗口最大不能超過序號范圍的一半。注意 這是理論上的要求。在實際協(xié)議如TCP中序號空間非常大32位窗口大小受其他因素如接收緩沖區(qū)限制通常不會觸及這個理論上限但這個原理是設計的基礎。3.2 獨立定時器 vs 單一定時器管理開銷與效率的權衡GBN使用單一定時器管理最早未確認的幀簡單但粗放。SR為每個未確認幀維護獨立定時器精細但復雜。實現開銷 獨立定時器意味著更多的數據結構如鏈表或優(yōu)先級隊列來管理超時事件和更頻繁的定時器操作啟動、停止、檢查。在幀數量很多時這是一個不可忽視的開銷。重傳精度與效率 這是獨立定時器帶來的最大好處。假設窗口內幀1丟失幀2, 3, 4…都正確到達。在GBN下幀1超時會導致2,3,4…全部被重傳浪費帶寬。在SR下只有幀1被重傳。接收方已經緩存了2,3,4…一旦收到重傳的幀1就可以立即向上交付一批數據時延更低。實戰(zhàn)心得 在實現SR協(xié)議仿真或理解其性能時定時器管理是核心。一種常見的優(yōu)化是使用一個“主定時器”配合時間戳。為每個發(fā)送的幀記錄其發(fā)送時間戳。主定時器周期性檢查所有未確認幀的時間戳將那些當前時間 - 發(fā)送時間 RTO的幀加入重傳隊列。這樣避免了大量操作系統(tǒng)定時器資源的使用。3.3 確認機制ACK、NAK與SACK肯定確認ACK SR協(xié)議主要依賴ACK。接收方每收到一個在窗口內的新幀就立即發(fā)送對該幀的ACK。這個ACK有兩個作用一是確認該幀收到二是作為接收方窗口狀態(tài)的隱式通告告訴發(fā)送方“我期待rcv_base的幀”。否定確認NAK 標準SR協(xié)議不一定需要NAK。沒有NAK丟包完全依靠發(fā)送方定時器超時來檢測這至少需要一個RTO的時間。加入NAK后接收方一旦檢測到序號間隙比如收到了幀0和幀2但沒收到幀1可以立即發(fā)送一個NAK 1通知發(fā)送方“幀1可能丟了快重傳”。這可以顯著減少丟包恢復時間特別是在錯誤率高的鏈路上。許多實際實現包括TCP的SACK選項都包含了類似NAK的機制。選擇性確認SACK 這是對基本ACK機制的強大增強。一個SACK報文可以同時確認多個不連續(xù)的數據塊。例如接收方收到了幀0, 1, 3, 4它可以發(fā)送一個ACK其中包含“SACK塊”指明已收到[0-1]和[3-4]。發(fā)送方據此能精確知道只有幀2丟失了無需等待超時就可以重傳幀2同時知道幀3和幀4無需重傳。TCP的SACK選項正是SR思想在傳輸層的直接體現。4. 與回退N幀GBN協(xié)議的對比與選型思考理解了SR再回頭看GBN就能更深刻地體會其設計取舍。我們可以從幾個維度對比特性維度回退N幀 (GBN)選擇重傳 (SR)接收方緩存不緩存亂序幀直接丟棄。緩存亂序但正確的幀。確認機制累計確認。ACK(n)表示n及之前所有幀已正確接收。獨立確認或選擇性確認(SACK)。每個幀或數據塊可被單獨確認。重傳策略超時后重傳所有已發(fā)送但未確認的幀從最早未確認幀開始。超時后僅重傳超時的那個幀。定時器一個用于最早的未確認幀。每個已發(fā)送未確認的幀都有一個獨立定時器或等效機制。接收窗口大小固定為1。通常大于1與發(fā)送窗口大小相等。優(yōu)點實現極其簡單接收方邏輯簡單定時器管理容易。在低錯誤率信道中效率尚可。帶寬利用率高尤其在高錯誤率、高帶寬延遲積BDP的信道中。只重傳錯誤幀避免不必要的重傳。缺點一個錯誤拖累全局。錯誤率高時大量正確幀被無辜重傳效率急劇下降。不適合衛(wèi)星、無線等鏈路。實現復雜。需要維護多個定時器、接收方需要緩存管理、序號空間要求更嚴格窗口序號空間/2。適用場景錯誤率極低的可靠有線鏈路如局域網或對實現復雜度有嚴格限制的嵌入式環(huán)境。錯誤率較高的鏈路無線網絡、早期衛(wèi)星通信、帶寬延遲積大的長肥管道。是現代可靠傳輸協(xié)議如TCP的基礎。選型思考 這本質上是一個“簡單性”與“效率”的權衡。在計算機早期處理能力和內存非常寶貴GBN的簡單性極具吸引力。但隨著硬件發(fā)展復雜度不再是首要瓶頸而網絡帶寬和延遲成為關鍵SR的效率優(yōu)勢就凸顯出來。TCP協(xié)議的設計就融合了這兩種思想默認使用累計確認類似GBN但通過SACK選項實現了選擇重傳的能力它使用單個重傳定時器但通過快速重傳收到3個重復ACK即觸發(fā)重傳機制部分實現了對單個丟包的選擇性響應。可以說TCP是一個混合體在實踐中根據網絡狀況動態(tài)調整策略。5. 實戰(zhàn)推演一個完整的SR協(xié)議工作流程與故障模擬讓我們通過一個具體的例子把SR協(xié)議的所有機制串起來。假設窗口大小N4序號空間80-7模8運算滿足N 8/2。初始狀態(tài)發(fā)送方send_base 0,next_seq_num 0, 窗口[0,1,2,3]。接收方rcv_base 0, 窗口[0,1,2,3]緩存空。步驟1正常發(fā)送與接收發(fā)送方發(fā)送幀0,1,2,3并為每個啟動獨立定時器。接收方按序收到幀0。發(fā)送ACK 0緩存幀0。發(fā)現rcv_base0已收到交付幀0給上層rcv_base變?yōu)?窗口滑動至[1,2,3,4]。接收方收到幀2亂序。發(fā)送ACK 2緩存幀2。rcv_base仍是1因為幀1沒到無法交付。接收方收到幀1。發(fā)送ACK 1緩存幀1。此時緩存中有幀1,2。檢查rcv_base1已收到于是連續(xù)交付幀1和幀2rcv_base變?yōu)?窗口滑動至[3,4,5,6]。接收方收到幀3。發(fā)送ACK 3緩存幀3。交付幀3rcv_base變?yōu)?窗口滑動至[4,5,6,7]。發(fā)送方陸續(xù)收到ACK 0,ACK 1,ACK 2,ACK 3。窗口滑動send_base變?yōu)?現在可以發(fā)送幀4,5,6,7。步驟2模擬幀丟失與選擇性重傳發(fā)送方發(fā)送幀4,5,6,7。假設幀5在網絡中丟失。幀4,6,7正確到達接收方。接收方收到幀4發(fā)送ACK 4交付rcv_base5窗口[5,6,7,0]模8。接收方收到幀6發(fā)送ACK 6緩存幀6因為期望的是幀5。接收方收到幀7發(fā)送ACK 7緩存幀7。發(fā)送方收到ACK 4ACK 6ACK 7。它知道幀4,6,7已收到停止它們的定時器。但幀5的ACK始終沒來。幀5的定時器超時。發(fā)送方僅重傳幀5并重啟幀5的定時器。接收方收到重傳的幀5。發(fā)送ACK 5。此時它發(fā)現rcv_base5已收到且緩存中有幀6,7。于是它連續(xù)交付幀5,6,7rcv_base變?yōu)?模8窗口滑動至[0,1,2,3]。發(fā)送方收到ACK 5停止幀5的定時器窗口可以繼續(xù)滑動。步驟3模擬ACK丟失與重復ACK接續(xù)步驟2后發(fā)送方發(fā)送新的一批幀0,1,2,3注意序號輪回。假設幀0的ACK丟失了。發(fā)送方幀0的定時器超時重傳幀0。此時接收方的窗口是[0,1,2,3]它收到了這個重傳的幀0。它無法判斷這是新的幀0還是舊的重傳。但根據SR規(guī)則它必須檢查這是否是重復幀。實現上接收方需要維護一個“已接收并確認”的最高序號信息。它發(fā)現幀0序號0小于當前的rcv_base此時rcv_base可能已經大于0因為收到了更新的幀或者它發(fā)現自己已經緩存過幀0。于是接收方再次發(fā)送一個ACK 0。發(fā)送方收到這個重復的ACK 0。它知道接收方已經收到了幀0可能是之前ACK丟了于是它可以安全地忽略這個重傳幀帶來的影響并確認幀0已收到。這避免了發(fā)送方錯誤地認為接收方沒收到幀0而陷入死循環(huán)。這個推演展示了SR協(xié)議如何處理亂序、丟包、ACK丟失等各種異常情況其核心在于緩存、獨立確認和重復ACK的巧妙運用。6. 從理論到實踐SR思想在現代網絡協(xié)議中的體現雖然教科書上的SR是一個數據鏈路層協(xié)議但其思想已經深深嵌入現代網絡協(xié)議棧尤其是在傳輸層。TCP協(xié)議中的SR元素選擇性確認SACK 如前所述這是最直接的體現。通過在TCP選項字段中攜帶SACK塊接收方可以告知發(fā)送方多個不連續(xù)的數據段已收到使發(fā)送方能進行選擇性重傳?？焖僦貍髋c快速恢復 當發(fā)送方連續(xù)收到3個對同一序號的重復ACKDup-ACK時它推斷該序號的數據段可能丟失于是不等超時立即重傳該數據段。這本質上是利用重復ACK作為一種隱式的、負面的選擇信號實現了類似SR的快速重傳。隨后的“快速恢復”算法調整擁塞窗口也體現了對單個丟包的選擇性處理而非GBN式的全面回退。亂序緩存與按序交付 TCP接收端有接收緩沖區(qū)可以緩存亂序到達的報文段等待缺失的報文段到達后再按序交付給應用層。這完全繼承了SR接收方的核心邏輯。QUIC協(xié)議中的強化 谷歌提出的QUIC基于UDP協(xié)議將SR思想更進一步。它在傳輸層原生支持了更細粒度的、基于數據流的可靠傳輸每個數據包都有獨立的包號重傳機制天然就是選擇性的避免了TCP中因序列號重用可能帶來的歧義問題在高速長連接下重傳效率更高。實戰(zhàn)心得與注意事項窗口大小的動態(tài)調整 在實際協(xié)議中如TCP窗口大小不是固定的而是動態(tài)變化的受限于接收方通告窗口rwnd和擁塞窗口cwnd。理解固定窗口的SR是基礎但更要明白在實際中窗口是流動的協(xié)議需要同時處理可靠傳輸和流量控制、擁塞控制。定時器管理的優(yōu)化 為每個數據包維護一個硬件定時器是不現實的。實際中TCP使用一個重傳定時器RTO但其超時時間是通過動態(tài)測量RTT來計算的。當需要重傳時它可能采用類似“批量重傳”或基于SACK信息精確重傳的策略。在你自己實現可靠UDP時可以采用一個時間輪或優(yōu)先隊列來管理多個虛擬定時器。應用場景選擇 如果你在設計一個內部系統(tǒng)的通信模塊網絡環(huán)境可控低錯誤率、低延遲那么實現一個簡單的GBN變種可能更省心。但如果你面對的是公網、移動網絡等不穩(wěn)定環(huán)境那么引入選擇性重傳哪怕是簡化版對提升性能至關重要。很多時候不必完全實現教科書式的SR可以取其精髓例如實現亂序緩存和按序交付但重傳策略可以簡化或者使用一個主定時器配合SACK信息來實現選擇性重傳。理解選擇重傳協(xié)議不僅僅是記住它的規(guī)則更是理解一種“在不可靠的媒介上實現可靠通信”的設計哲學通過增加接收端的復雜性緩存和智能選擇性確認來換取信道利用率的本質提升這是一種典型的以空間緩存和計算復雜度換取時間和效率的工程權衡。下次當你用Wireshark抓包看到TCP報文里的SACK選項時你就會會心一笑知道這正是數據鏈路層那個古老而精妙的選擇重傳思想在互聯(lián)網的血管中繼續(xù)跳動。