擁塞控制

網路的吞吐量與通信子網負荷(即通信子網中正在傳輸的分組數)有著密切的關係。當通信子網負荷比較小時，網路的吞吐量(分組數/秒)隨網路負荷(每個節點中分組的平均數)的增加而線性增加。當網路負荷增加到某一值后，若網路吞吐量反而下降，則表徵網路中出現了擁塞現象。在一個出現擁塞現象的網路中，到達某個節點的分組將會遇到無緩衝區可用的情況，從而使這些分組不得不由前一節點重傳，或者需要由源節點或源端系統重傳。當擁塞比較嚴重時，通信子網中相當多的傳輸能力和節點緩衝器都用於這種無謂的重傳，從而使通信子網的有效吞吐量下降。由此引起惡性循環，使通信子網的局部甚至全部處於死鎖狀態，最終導致網路有效吞吐量接近為零。

（1）多條流入線路有分組到達，並需要同一輸出線路，此時，如果路由器沒有足夠的內存來存放所有這些分組，那麼有的分組就會丟失。

（2）路由器的慢帶處理器的緣故，以至於難以完成必要的處理工作，如緩衝區排隊、更新路由表等。

（1）在傳輸層可採用：重傳策略、亂序緩存策略、確認策略、流控制策略和確定超時策略。

（2）在網路層可採用：子網內部的虛電路與數據報策略、分組排隊和服務策略、分組丟棄策略、路由演演算法和分組生存管理。

（3）在數據鏈路層可採用：重傳策略、亂序緩存策略、確認策略和流控制策略。

該法用於虛電路分組交換網中。在建立虛電路時，讓呼叫請求分組途經的節點為虛電路預先分配一個或多個數據緩衝區。若某個節點緩衝器已被佔滿，則呼叫請求分組另擇路由,或者返回一個"忙"信號給呼叫者。這樣，通過途經的各節點為每條虛電路開設的永久性緩衝區(直到虛電路拆除),就總能有空間來接納並轉送經過的分組。此時的分組交換跟電路交換很相似。當節點收到一個分組並將它轉發出去之後，該節點向發送節點返回一個確認信息。該確認一方面表示接收節點已正確收到分組，另一方面告訴發送節點，該節點已空出緩衝區以備接收下一個分組。上面是"停一等"協議下的情況，若節點之間的協議允許多個未處理的分組存在，則為了完全消除擁塞的可能性，每個節點要為每條虛電路保留等價於窗口大小數量的緩衝區。這種方法不管有沒有通信量，都有可觀的資源(線路容量或存儲空間)被某個連接佔有，因此網路資源的有效利用率不高。這種控制方法主要用於要求高帶寬和低延遲的場合，例如傳送數字化語音信息的虛電路。

該法不必預先保留緩衝區,當緩衝區佔滿時，將到來的分組丟棄。若通信子網提供的是數據報服務,則用分組丟棄法來防止擁塞發生不會引起大的影響。但若通信子網提供的是虛電路服務,則必須在某處保存被丟棄分組的備份，以便擁塞解決后能重新傳送。有兩種解決被丟棄分組重發的方法，一種是讓發送被丟棄分組的節點超時，並重新發送分組直至分組被收到；另一種是讓發送被丟棄分組的節點在嘗試一定次數後放棄發送，並迫使數據源節點超時而重新開始發送。但是不加分辨地隨意丟棄分組也不妥，因為一個包含確認信息的分組可以釋放節點的緩衝區，若因節點元空餘緩衝區來接收含確認信息的分組，這便使節點緩衝區失去了一次釋放的機會。解決這個問題的方法可以為每條輸入鏈路永久地保留一塊緩衝區，以用於接納並檢測所有進入的分組，對於捎帶確認信息的分組，在利用了所捎帶的確認釋放緩衝區后，再將該分組丟棄或將該捎帶好消息的分組保存在剛空出的緩衝區中。

這種方法在通信子網中設置適當數量的稱做"許可證"的特殊信息，一部分許可證在通信子網開始工作前預先以某種策略分配給各個源節點,另一部分則在子網開始工作后在網中四處環遊。當源節點要發送來自源端系統的分組時，它必須首先擁有許可證，並且每發送一個分組註銷一張許可證。目的節點方則每收到一個分組並將其遞交給目的端系統后，便生成一張許可證。這樣便可確保子網中分組數不會超過許可證的數量，從而防止了擁塞的發生。

擁塞的極端後果是死鎖。

死鎖是網路中最容易發生的故障之一，即使在網路負荷不很重時也會發生。死鎖發生時，一組節點由於沒有空閑緩衝區而無法接收和轉發分組，節點之間相互等待，既不能接收分組也不能轉發分組，並一直保持這一僵局，嚴重時甚至導致整個網路的癱瘓。此時，只能靠人工干預來重新啟動網路，解除死鎖。但重新啟動后並未消除引起死鎖的隱患，所以可能再次發生死鎖。死鎖是由於控制技術方面的某些缺陷所引起的，起因通常難以捉摸、難以發現，即使發現，也常常不能立即修復。因此，在各層協議中都必須考慮如何避免死鎖的問題。

最常見的死鎖是發生在兩個節點之間的直接存儲轉發死鎖。例如,A節點的所有緩衝區裝滿了等待輸出到B節點的分組，而B節點的所有緩衝區也全部裝滿了等待輸出到A節點的分組；此時,A節點不能從B節點接收分組,B節點也不能從A節點接收分組，從而造成兩節點間的死鎖。這種情況也可能發生在一組節點之間，例如,A節點企圖向B節點發送分組、B節點企圖向C節點發送分組、而C節點又企圖向A節點發送分組，但此時每個節點都無空閑緩衝區用於接收分組，這種情形稱做間接存儲轉發死鎖。當一個節點處於死鎖狀態時，所有與之相連的鏈路將被完全擁塞。

一種防止存儲轉發死鎖的方法是，每個節點設置M+1個緩衝區，並以0到M編號。M為通信子網的直徑，即從任一源節點到任一目的節點間的最大鏈路段數。每個源節點僅當其0號緩衝區空時才能接收源端系統來的分組，而此分組僅能轉發給1號緩衝區空閑的相鄰節點，再由該節點將分組轉發給它的2號緩衝區空閑的相鄰節點……最後，該分組或者順利到達目的節點並被遞交給目的端系統，或者到了某個節點編號為M的緩衝區中再也轉發不下去，此時一定發生了循環，應該將該分組丟棄。由於每個分組都是按照編號遞增規則分配緩衝區，所以節點之間不會相互等待空閑緩衝區而發生死鎖現象。這種方法的不足之處在於，當某節點雖然有空閑緩衝區，但正巧沒有所需要的特定編號的緩衝區時，分組仍要等待，從而造成了緩衝區和鏈路的浪費。

另一種防止存儲轉發死鎖的方法是，使每個分組上都攜帶一個全局性的惟一的"時間戳",每個節點要為每條輸入鏈路保留一個特殊的接收緩衝區，而其它緩衝區均可用於存放中轉分組。在每條輸出鏈路的隊列上分組按時間戳順序排隊。例如，節點A要將分組送到節點B,若B節點沒有空閑緩衝區，但正巧有要送到A節點的分組，此時A、B節點可通過特殊的接收緩衝區交換分組；若B節點既沒有空閑緩衝區，也沒有要送往A節點的分組,B節點只好強行將一個出路方向大致與A節點方向相同的分組與A節點互相交換分組，但此時A節點中的分組必須比B節點中的分組具有更早的時間戳，這樣才能保證子網中某個最早的分組不受阻擋地轉發到目的地。由此可見，每個分組最終總會成為最早的分組，並總能被一步一步地發送到目的節點，從而避免了死鎖現象的發生。

死鎖中比較嚴重的情況是重裝死鎖。假設發給一個端系統的報文很長，被源節點拆成若干個分組發送，目的節點要將所有具有相同編號的分組重新裝配成報文遞交給目的端系統，若目的節點用於重裝報文的緩衝區空間有限，而且它無法知道正在接收的報文究竟被拆成多少個分組，此時，就可能發生嚴重的問題：為了接收更多的分組，該目的節點用完了它的緩衝空間，但它又不能將尚未拼裝完整的報文遞送給目的端系統，而鄰節點仍在不斷地向它傳送分組，但它卻無法接收。這樣，經過多次嘗試后，鄰節點就會繞道從其它途徑再向該目的節點傳送分組，但該目的節點已被死鎖，其周邊區域也由此發生了擁塞。下面幾種方法可用以避免重裝死鎖的發生:

①允許目的節點將不完整的報文遞交給目的端系統;

②一個不能完整重裝的報文能被檢測出來，並要求發送該報文的源端系統重新傳送;

③為每個節點配備一個後備緩衝空間，用以暫存不完整的報文。

①、②兩種方法不能很滿意地解決重裝死鎖，因為它們使端系統中的協議複雜化了。一般的設計中,網路層應該對端系統透明，也即端系統不該考慮諸如報文拆、裝之類的事。③方法雖然不涉及端系統，但使每個節點增加了開銷。

端到端擁塞控制的IETF標準關注的方面包括集中在特定的協議（例如TCP協議[RFC2581],可靠的多點傳送協議[RFC2357])；終端節點和路由器之間的擁塞信息(例如明確的擁塞通告[RFC2481])交換的句法和語義；不同服務的服務質量的期望值。端到端的擁塞控制的作用也在一個關於“Internet中的隊列管理和避免擁塞的建議”[參見RFC2309]的RFC報告中進行了討論。RFC2309提出了在路由器中活躍的隊列管理機制的配置和對路由器機制設計的延續來處理對擁塞通告無回應的流。我們能夠輕鬆地從RFC2309中借用一些端到端的擁塞控制的概括性的討論。

與上面提到的RFCs資料相比，本文檔對擁塞控制的原理進行更一般性的討論。Internet成功的一個關鍵因素就是TCP協議的避免擁塞機制。當前TCP協議在Internet中仍然是佔主導地位的傳輸協議，但它不是適用於任何地方，有越來越多的應用由於某種原因沒有選擇使用TCP協議。通信不僅包括多點傳送通信，而且包括單點傳送通信，諸如不需要可靠性的流化的多媒體，以及包括象DNS(DomainNameServer域名伺服器)或路由信息的通信，它們帶有被認為對網路運行至關重要的簡訊息。許多通信並不使用任何形式的預留帶寬或端到端擁塞控制。為了保持最優傳輸量，端到端的擁塞控制的繼續使用對保持Internet的穩定至關重要。

本文檔也討論IETF在新的擁塞控制協議標準化中的一般作用。對於區別性服務和集成性服務的擁塞控制的討論在本文檔中不涉及。集成性或區別性服務能夠保證端到端的網路帶寬，所以不需要端到端的擁塞控制機制。

確定擁塞窗口的大小的過程：在剛建立連接時，將擁塞窗口的大小初始化為該連接所需的最大連接數據段的長度值，併發送一個最大長度的數據段（當然必須是接收窗口允許的）。如果在定時器超時前得到確認，將擁塞窗口的大小增加一個數據段的位元組數，併發送兩個數據段，如果每個數據段在定時器超時前都得到確認，就再在原基礎上增加一倍，即為4個數據段的大小，如此反覆，每次都在前一次的基礎上加倍。當定時器超時或達到發送窗口設定值，停止擁塞窗口尺寸的增加。這種反覆稱為慢速啟動，所有的TCP協議都支持這種方法。

擁塞控制不僅是網路穩定、高效運行的關鍵，同時又是實現各種服務質量的基礎和前提。實際的網路是一個不斷發展的系統，網路擁塞控制研究也是一個非常困難、有挑戰性的研究領域。對網路擁塞控制的研究仍有許多工作要做，進一步的工作包括：

1、擁塞控制基於端主機的控制策略和路由器的隊列管理策略存在相互影響、相互作用的關係，如何在網路模型描述的基礎上，從控制系統的角度將兩者結合起來，設計出最優的擁塞控制策略，是網路擁塞控制研究的一個方向。

2、主動隊列管理技術通過丟包積極響應擁塞，來達到擁塞避免和緩解的目的，是網路擁塞控制最重要的手段。如何實現AQM高級策略，引入新的人工智慧演演算法和遺傳演演算法與模糊邏輯的綜合應用是目前研究的一個熱點問題。

3、以往的工作主要採用局部線性化方法，缺乏對系統全局動力學的理論分析。此外，在多種源端擁塞控制策略和路由器避免策略並存時，如何分析整個網路的穩定性，如何分析各種不確定因素對穩定性的影響等，也是需要認真考慮的問題。

4、CP/IP 擁塞控制的設計和實現面臨著眾多的折中，不可能有一種設計和實現在所有環境中都是“最好的”。現有的擁塞控制思路、方法和技術在多目標的不同環境中面臨著挑戰，它們還有許多要改進的地方。

5、目前已經有越來越多的移動用戶通過無線系統接入網際網路，由於無線通信固有的特點，使得擁塞控制機制的研究更加困難，極具挑戰。