擁塞的極端后果是死鎖。死鎖是網(wǎng)絡中最容易發(fā)生的故障之一,即使在網(wǎng)絡負荷不很重時也會發(fā)生。死鎖發(fā)生時,一組節(jié)點由于沒有空閑緩沖區(qū)而無法接收和轉(zhuǎn)發(fā)分組,節(jié)點之間相互等待,既不能接收分組也不能轉(zhuǎn)發(fā)分組,并一直保持這一僵局,嚴重時甚至導致整個網(wǎng)絡的癱瘓。此時,只能靠人工干預來重新啟動網(wǎng)絡,解除死鎖。但重新啟動后并未消除引起死鎖的隱患,所以可能再次發(fā)生死鎖。死鎖是由于控制技術(shù)方面的某些缺陷所引起的,起因通常難以捉摸、難以發(fā)現(xiàn),即使發(fā)現(xiàn),也常常不能立即修復。因此,在各層協(xié)議中都必須考慮如何避免死鎖的問題。存儲轉(zhuǎn)發(fā)死鎖及其防止最常見的死鎖是發(fā)生在兩個節(jié)點之間的直接存儲轉(zhuǎn)發(fā)死鎖。
例如,A節(jié)點的所有緩沖區(qū)裝滿了等待輸出到B節(jié)點的分組,而B節(jié)點的所有緩沖區(qū)也全部裝滿了等待輸出到A節(jié)點的分組;此時,A節(jié)點不能從B節(jié)點接收分組,B節(jié)點也不能從A節(jié)點接收分組,從而造成兩節(jié)點間的死鎖。這種情況也可能發(fā)生在一組節(jié)點之間,例如,A節(jié)點企圖向B節(jié)點發(fā)送分組、B節(jié)點企圖向C節(jié)點發(fā)送分組、而C節(jié)點又企圖向A節(jié)點發(fā)送分組,但此時每個節(jié)點都無空閑緩沖區(qū)用于接收分組,這種情形稱做間接存儲轉(zhuǎn)發(fā)死鎖。當一個節(jié)點處于死鎖狀態(tài)時,所有與之相連的鏈路將被完全擁塞。一種防止存儲轉(zhuǎn)發(fā)死鎖的方法是,每個節(jié)點設置M+1個緩沖區(qū),并以0到M編號。M為通信子網(wǎng)的直徑,即從任一源節(jié)點到任一目的節(jié)點間的最大鏈路段數(shù)。每個源節(jié)點僅當其0號緩沖區(qū)空時才能接收源端系統(tǒng)來的分組,而此分組僅能轉(zhuǎn)發(fā)給1號緩沖區(qū)空閑的相鄰節(jié)點,再由該節(jié)點將分組轉(zhuǎn)發(fā)給它的2號緩沖區(qū)空閑的相鄰節(jié)點……最后,該分組或者順利到達目的節(jié)點并被遞交給目的端系統(tǒng),或者到了某個節(jié)點編號為M的緩沖區(qū)中再也轉(zhuǎn)發(fā)不下去,此時一定發(fā)生了循環(huán),應該將該分組丟棄。由于每個分組都是按照編號遞增規(guī)則分配緩沖區(qū),所以節(jié)點之間不會相互等待空閑緩沖區(qū)而發(fā)生死鎖現(xiàn)象。
這種方法的不足之處在于,當某節(jié)點雖然有空閑緩沖區(qū),但正巧沒有所需要的特定編號的緩沖區(qū)時,分組仍要等待,從而造成了緩沖區(qū)和鏈路的浪費。另一種防止存儲轉(zhuǎn)發(fā)死鎖的方法是,使每個分組上都攜帶一個全局性的惟一的"時間戳",每個節(jié)點要為每條輸入鏈路保留一個特殊的接收緩沖區(qū),而其它緩沖區(qū)均可用于存放中轉(zhuǎn)分組。在每條輸出鏈路的隊列上分組按時間戳順序排隊。例如,節(jié)點A要將分組送到節(jié)點B,若B節(jié)點沒有空閑緩沖區(qū),但正巧有要送到A節(jié)點的分組,此時A、B節(jié)點可通過特殊的接收緩沖區(qū)交換分組;若B節(jié)點既沒有空閑緩沖區(qū),也沒有要送往A節(jié)點的分組,B節(jié)點只好強行將一個出路方向大致與A節(jié)點方向相同的分組與A節(jié)點互相交換分組,但此時A節(jié)點中的分組必須比B節(jié)點中的分組具有更早的時間戳,這樣才能保證子網(wǎng)中某個最早的分組不受阻擋地轉(zhuǎn)發(fā)到目的地。由此可見,每個分組最終總會成為最早的分組,并總能被一步一步地發(fā)送到目的節(jié)點,從而避免了死鎖現(xiàn)象的發(fā)生。重裝死鎖及其防止死鎖中比較嚴重的情況是重裝死鎖。
假設發(fā)給一個端系統(tǒng)的報文很長,被源節(jié)點拆成若干個分組發(fā)送,目的節(jié)點要將所有具有相同編號的分組重新裝配成報文遞交給目的端系統(tǒng),若目的節(jié)點用于重裝報文的緩沖區(qū)空間有限,而且它無法知道正在接收的報文究竟被拆成多少個分組,此時,就可能發(fā)生嚴重的問題:為了接收更多的分組,該目的節(jié)點用完了它的緩沖空間,但它又不能將尚未拼裝完整的報文遞送給目的端系統(tǒng),而鄰節(jié)點仍在不斷地向它傳送分組,但它卻無法接收。這樣,經(jīng)過多次嘗試后,鄰節(jié)點就會繞道從其它途徑再向該目的節(jié)點傳送分組,但該目的節(jié)點已被死鎖,其周邊區(qū)域也由此發(fā)生了擁塞。下面幾種方法可用以避免重裝死鎖的發(fā)生:①允許目的節(jié)點將不完整的報文遞交給目的端系統(tǒng);②一個不能完整重裝的報文能被檢測出來,并要求發(fā)送該報文的源端系統(tǒng)重新傳送;③為每個節(jié)點配備一個后備緩沖空間,用以暫存不完整的報文。①、②兩種方法不能很滿意地解決重裝死鎖,因為它們使端系統(tǒng)中的協(xié)議復雜化了。一般的設計中,網(wǎng)絡層應該對端系統(tǒng)透明,也即端系統(tǒng)不該考慮諸如報文拆、裝之類的事。③方法雖然不涉及端系統(tǒng),但使每個節(jié)點增加了開銷。
下載文檔
