擁塞控制

擁塞的極端后果是死鎖。

死鎖是網(wǎng)絡(luò)中最容易發(fā)生的故障之一,即使在網(wǎng)絡(luò)負(fù)荷不很重時(shí)也會(huì)發(fā)生。死鎖發(fā)生時(shí),一組節(jié)點(diǎn)由于沒有空閑緩沖區(qū)而無(wú)法接收和轉(zhuǎn)發(fā)分組,節(jié)點(diǎn)之間相互等待,既不能接收分組也不能轉(zhuǎn)發(fā)分組,并一直保持這一僵局,嚴(yán)重時(shí)甚至導(dǎo)致整個(gè)網(wǎng)絡(luò)的癱瘓。此時(shí),只能靠人工干預(yù)來(lái)重新啟動(dòng)網(wǎng)絡(luò),解除死鎖。但重新啟動(dòng)后并未消除引起死鎖的隱患,所以可能再次發(fā)生死鎖。死鎖是由于控制技術(shù)方面的某些缺陷所引起的,起因通常難以捉摸、難以發(fā)現(xiàn),即使發(fā)現(xiàn),也常常不能立即修復(fù)。因此,在各層協(xié)議中都必須考慮如何避免死鎖的問(wèn)題。

存儲(chǔ)轉(zhuǎn)發(fā)死鎖及其防止

最常見的死鎖是發(fā)生在兩個(gè)節(jié)點(diǎn)之間的直接存儲(chǔ)轉(zhuǎn)發(fā)死鎖。例如,A節(jié)點(diǎn)的所有緩沖區(qū)裝滿了等待輸出到B節(jié)點(diǎn)的分組,而B節(jié)點(diǎn)的所有緩沖區(qū)也全部裝滿了等待輸出到A節(jié)點(diǎn)的分組;此時(shí),A節(jié)點(diǎn)不能從B節(jié)點(diǎn)接收分組,B節(jié)點(diǎn)也不能從A節(jié)點(diǎn)接收分組,從而造成兩節(jié)點(diǎn)間的死鎖。這種情況也可能發(fā)生在一組節(jié)點(diǎn)之間,例如,A節(jié)點(diǎn)企圖向B節(jié)點(diǎn)發(fā)送分組、B節(jié)點(diǎn)企圖向C節(jié)點(diǎn)發(fā)送分組、而C節(jié)點(diǎn)又企圖向A節(jié)點(diǎn)發(fā)送分組,但此時(shí)每個(gè)節(jié)點(diǎn)都無(wú)空閑緩沖區(qū)用于接收分組,這種情形稱做間接存儲(chǔ)轉(zhuǎn)發(fā)死鎖。當(dāng)一個(gè)節(jié)點(diǎn)處于死鎖狀態(tài)時(shí),所有與之相連的鏈路將被完全擁塞。

一種防止存儲(chǔ)轉(zhuǎn)發(fā)死鎖的方法是,每個(gè)節(jié)點(diǎn)設(shè)置M+1個(gè)緩沖區(qū),并以0到M編號(hào)。M為通信子網(wǎng)的直徑,即從任一源節(jié)點(diǎn)到任一目的節(jié)點(diǎn)間的最大鏈路段數(shù)。每個(gè)源節(jié)點(diǎn)僅當(dāng)其0號(hào)緩沖區(qū)空時(shí)才能接收源端系統(tǒng)來(lái)的分組,而此分組僅能轉(zhuǎn)發(fā)給1號(hào)緩沖區(qū)空閑的相鄰節(jié)點(diǎn),再由該節(jié)點(diǎn)將分組轉(zhuǎn)發(fā)給它的2號(hào)緩沖區(qū)空閑的相鄰節(jié)點(diǎn)……最后,該分組或者順利到達(dá)目的節(jié)點(diǎn)并被遞交給目的端系統(tǒng),或者到了某個(gè)節(jié)點(diǎn)編號(hào)為M的緩沖區(qū)中再也轉(zhuǎn)發(fā)不下去,此時(shí)一定發(fā)生了循環(huán),應(yīng)該將該分組丟棄。由于每個(gè)分組都是按照編號(hào)遞增規(guī)則分配緩沖區(qū),所以節(jié)點(diǎn)之間不會(huì)相互等待空閑緩沖區(qū)而發(fā)生死鎖現(xiàn)象。這種方法的不足之處在于,當(dāng)某節(jié)點(diǎn)雖然有空閑緩沖區(qū),但正巧沒有所需要的特定編號(hào)的緩沖區(qū)時(shí),分組仍要等待,從而造成了緩沖區(qū)和鏈路的浪費(fèi)。

另一種防止存儲(chǔ)轉(zhuǎn)發(fā)死鎖的方法是,使每個(gè)分組上都攜帶一個(gè)全局性的惟一的"時(shí)間戳",每個(gè)節(jié)點(diǎn)要為每條輸入鏈路保留一個(gè)特殊的接收緩沖區(qū),而其它緩沖區(qū)均可用于存放中轉(zhuǎn)分組。在每條輸出鏈路的隊(duì)列上分組按時(shí)間戳順序排隊(duì)。例如,節(jié)點(diǎn)A要將分組送到節(jié)點(diǎn)B,若B節(jié)點(diǎn)沒有空閑緩沖區(qū),但正巧有要送到A節(jié)點(diǎn)的分組,此時(shí)A、B節(jié)點(diǎn)可通過(guò)特殊的接收緩沖區(qū)交換分組;若B節(jié)點(diǎn)既沒有空閑緩沖區(qū),也沒有要送往A節(jié)點(diǎn)的分組,B節(jié)點(diǎn)只好強(qiáng)行將一個(gè)出路方向大致與A節(jié)點(diǎn)方向相同的分組與A節(jié)點(diǎn)互相交換分組,但此時(shí)A節(jié)點(diǎn)中的分組必須比B節(jié)點(diǎn)中的分組具有更早的時(shí)間戳,這樣才能保證子網(wǎng)中某個(gè)最早的分組不受阻擋地轉(zhuǎn)發(fā)到目的地。由此可見,每個(gè)分組最終總會(huì)成為最早的分組,并總能被一步一步地發(fā)送到目的節(jié)點(diǎn),從而避免了死鎖現(xiàn)象的發(fā)生。

重裝死鎖及其防止

死鎖中比較嚴(yán)重的情況是重裝死鎖。假設(shè)發(fā)給一個(gè)端系統(tǒng)的報(bào)文很長(zhǎng),被源節(jié)點(diǎn)拆成若干個(gè)分組發(fā)送,目的節(jié)點(diǎn)要將所有具有相同編號(hào)的分組重新裝配成報(bào)文遞交給目的端系統(tǒng),若目的節(jié)點(diǎn)用于重裝報(bào)文的緩沖區(qū)空間有限,而且它無(wú)法知道正在接收的報(bào)文究竟被拆成多少個(gè)分組,此時(shí),就可能發(fā)生嚴(yán)重的問(wèn)題:為了接收更多的分組,該目的節(jié)點(diǎn)用完了它的緩沖空間,但它又不能將尚未拼裝完整的報(bào)文遞送給目的端系統(tǒng),而鄰節(jié)點(diǎn)仍在不斷地向它傳送分組,但它卻無(wú)法接收。這樣,經(jīng)過(guò)多次嘗試后,鄰節(jié)點(diǎn)就會(huì)繞道從其它途徑再向該目的節(jié)點(diǎn)傳送分組,但該目的節(jié)點(diǎn)已被死鎖,其周邊區(qū)域也由此發(fā)生了擁塞。下面幾種方法可用以避免重裝死鎖的發(fā)生:

①允許目的節(jié)點(diǎn)將不完整的報(bào)文遞交給目的端系統(tǒng);

②一個(gè)不能完整重裝的報(bào)文能被檢測(cè)出來(lái),并要求發(fā)送該報(bào)文的源端系統(tǒng)重新傳送;

③為每個(gè)節(jié)點(diǎn)配備一個(gè)后備緩沖空間,用以暫存不完整的報(bào)文。

①、②兩種方法不能很滿意地解決重裝死鎖,因?yàn)樗鼈兪苟讼到y(tǒng)中的協(xié)議復(fù)雜化了。一般的設(shè)計(jì)中,網(wǎng)絡(luò)層應(yīng)該對(duì)端系統(tǒng)透明,也即端系統(tǒng)不該考慮諸如報(bào)文拆、裝之類的事。③方法雖然不涉及端系統(tǒng),但使每個(gè)節(jié)點(diǎn)增加了開銷。

網(wǎng)關(guān)的功能主要有以下幾個(gè)方面:1、具有協(xié)議轉(zhuǎn)換能力。網(wǎng)關(guān)具有從物理層到運(yùn)輸層，甚至應(yīng)用層各層協(xié)議轉(zhuǎn)換能力。當(dāng)然用于不同場(chǎng)合的網(wǎng)關(guān)，其協(xié)議轉(zhuǎn)換的能力可以不同，比如:有的只需要負(fù)責(zé)物理層到運(yùn)輸層的協(xié)議轉(zhuǎn)換，有的則需要完成物理層到應(yīng)用層的協(xié)議轉(zhuǎn)換。2、具有流量控制和擁塞控制的能力。對(duì)不同工作速率的網(wǎng)絡(luò)進(jìn)行互連時(shí)，需要有某種流量控制機(jī)構(gòu)來(lái)控制輸入到其他網(wǎng)絡(luò)上的信息流，網(wǎng)關(guān)常用的流量控制方式有:源站僅在得到允許時(shí)才進(jìn)行傳輸;強(qiáng)制源站減少它們向網(wǎng)絡(luò)提供的負(fù)荷;采用咨詢服務(wù)，這種咨詢服務(wù)告訴源站由于網(wǎng)絡(luò)擁塞或者其他異常情況，它所發(fā)送的分組已經(jīng)作廢。

3、具有在各個(gè)網(wǎng)絡(luò)之間可靠傳送信息的能力。為了提高互連的網(wǎng)絡(luò)的可靠性，常采用一下一些措施:防止分組在若干個(gè)網(wǎng)關(guān)中無(wú)限制的循環(huán);向源站或者其他網(wǎng)關(guān)發(fā)送錯(cuò)誤報(bào)告;對(duì)分組從源站到目的站之間的路徑進(jìn)行跟蹤;提供網(wǎng)間信息的重傳功能。4、具有路由選擇功能。5、具有將分組分段和組裝的能力。

網(wǎng)關(guān)的用途:網(wǎng)關(guān)可以用于以下幾種場(chǎng)合的異構(gòu)型網(wǎng)絡(luò)的互連。1、異構(gòu)型局域網(wǎng)互連?？梢岳镁W(wǎng)關(guān)將幾種完全不同的局域網(wǎng)互聯(lián)起來(lái)。2、局域網(wǎng)與WAN互連。局域網(wǎng)與WAN互連比較，至少其低3層協(xié)議不相同，因此它們屬于異構(gòu)型網(wǎng)絡(luò)，可以用網(wǎng)關(guān)實(shí)現(xiàn)互連。3、WAN與WAN互連。主要用于不同類型的WAN之間的互連。