什么是數據通信的擁塞控制

擁塞現象是指到達通信子網中某一部分的分組數量過多,使得該部分網絡來不及處理,以致引起這部分乃至整個網絡性能下降的現象,嚴重時甚至會導致網絡通信業務陷入停頓,即出現死鎖現象。這種現象跟公路網中經常所見的交通擁擠一樣,當節假日公路網中車輛大量增加時,各種走向的車流相互干擾,使每輛車到達目的地的時間都相對增加(即延遲增加),甚至有時在某段公路上車輛因堵塞而無法開動(即發生局部死鎖)。

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

1.擁塞控制方法

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

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

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

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

(1)存儲轉發死鎖及其防止。最常見的死鎖是發生在兩個節點之間的直接存儲轉發死鎖。例如,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節點中的分組具有更早的時間戳,這樣才能保證子網中某個最早的分組不受阻擋地轉發到目的地。由此可見,每個分組最終總會成為最早的分組,并總能被一步一步地發送到目的節點,從而避免了死鎖現象的發生。

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

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

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

③為每個節點配備一個后備緩沖空間,用以暫存不完整的報文。

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