2011年軟件水平考試網(wǎng)絡(luò)工程師全面復(fù)習(xí)資料(14)
貳.局域網(wǎng)和城域網(wǎng)
一.CSMA/CD
1. CSMA/CD(帶沖突檢測(cè)的載波監(jiān)聽(tīng)多路訪問(wèn)控制)
CSMA/CD是一種常用爭(zhēng)用的方法來(lái)決定對(duì)媒體訪問(wèn)權(quán)的協(xié)議,這種爭(zhēng)用協(xié)議只適用于邏輯上屬于總線拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)。在總線網(wǎng)絡(luò)中,每個(gè)站點(diǎn)都能獨(dú)立地決定幀的發(fā)送,若兩個(gè)或多個(gè)站同時(shí)發(fā)送幀,就會(huì)產(chǎn)生沖突,導(dǎo)致所發(fā)送的幀都出錯(cuò)。因此,一個(gè)用戶發(fā)送信息成功與否,在很大程度上取決于監(jiān)測(cè)總線是否空閑的算法,以及當(dāng)兩個(gè)不同節(jié)點(diǎn)同時(shí)發(fā)送的分組發(fā)生沖突后所使用的中斷傳輸?shù)姆椒ā?偩€爭(zhēng)用技術(shù)可分為載波監(jiān)聽(tīng)多路訪問(wèn)CSMA和具有沖突檢測(cè)的載波監(jiān)聽(tīng)多路訪問(wèn)CSMA/CD兩大類。
2. 載波監(jiān)聽(tīng)多路訪問(wèn)CSMA
載波監(jiān)聽(tīng)多路訪問(wèn)CSMA的技術(shù),也稱做無(wú)聽(tīng)后說(shuō)LBT(Listem Before Talk)。要傳輸數(shù)據(jù)的站點(diǎn)首先對(duì)媒體上有無(wú)載波進(jìn)行監(jiān)聽(tīng),以確定是否有別的站點(diǎn)在傳輸數(shù)據(jù)。如果媒體空閑,該站點(diǎn)便可傳輸數(shù)據(jù);否則,該站點(diǎn)將避讓一段時(shí)間后再做嘗試。這就需要有一種退避算法來(lái)決定避讓的時(shí)間,常用的退避算法有非堅(jiān)持、1-堅(jiān)持、P-堅(jiān)持三種。
a、非堅(jiān)持算法
算法規(guī)則為:
⑴如果媒本是空閑的,則可以立即發(fā)送。
⑵如果媒體是忙的,則等待一個(gè)由概率分布決定的隨機(jī)重發(fā)延遲后,再重復(fù)前一步驟。
采用隨機(jī)的重發(fā)延遲時(shí)間可以減少?zèng)_突發(fā)生的可能性。非堅(jiān)持算法的缺點(diǎn)是:即使有幾個(gè)著眼點(diǎn)為都有數(shù)據(jù)要發(fā)送,但由于大家都在延遲等待過(guò)程中,致使媒體仍可能處于空閑狀態(tài),使用率降低。
b、1-堅(jiān)持算法
算法規(guī)則:
⑴如果媒體空閑的,則可以立即發(fā)送。
⑵如果媒體是忙的,則繼續(xù)監(jiān)聽(tīng),直至檢測(cè)到媒體是空閑,立即發(fā)送。
⑶如果有沖突(在一段時(shí)間內(nèi)未收到肯定的回復(fù)),則等待一隨機(jī)量的時(shí)間,重復(fù)步驟⑴~⑵。
這種算法的優(yōu)點(diǎn)是:只要媒體空閑,站點(diǎn)就立即可發(fā)送,避免了媒體利用率的損失;其缺點(diǎn)是:假若有兩個(gè)或兩個(gè)以上的站點(diǎn)有數(shù)據(jù)要發(fā)送,沖突就不可避免。
c、P-堅(jiān)持算法
算法規(guī)則:
⑴監(jiān)聽(tīng)總線,如果媒體是空閑的,則以P的概率發(fā)送,而以(1-P)的概率延遲一個(gè)時(shí)間單位。一個(gè)時(shí)間單位通常等于最大傳播時(shí)延的2倍。
⑵延遲一個(gè)時(shí)間單位后,再重復(fù)步驟⑴。
⑶如果媒體是忙的,繼續(xù)監(jiān)聽(tīng)直至媒體空閑并重復(fù)步驟⑴。
P-堅(jiān)持算法是一種既能像非堅(jiān)持算法那樣減少?zèng)_突,又能像1-堅(jiān)持算法那樣減少媒體空閑時(shí)間的折中方案。問(wèn)題在于如何選擇P的有值,這要考慮到避免重負(fù)載下系統(tǒng)處于的不穩(wěn)定狀態(tài)。假如媒體是忙時(shí),有N個(gè)站有數(shù)據(jù)等待發(fā)送,一旦當(dāng)前的發(fā)送完成時(shí),將要試圖傳輸?shù)恼镜目偲谕麛?shù)為NP。如果選擇P過(guò)大,使NP>1,表明有多個(gè)站點(diǎn)試圖發(fā)送,沖突就不可避免。最壞的情況是,隨著沖突概率的不斷增大,而使吞吐量降低到零。所以必須選擇適當(dāng)P值使NP<1。當(dāng)然P值選得過(guò)小,則媒體利用率又會(huì)大大降低。
3. 具有沖突檢測(cè)的載波監(jiān)聽(tīng)多路訪問(wèn)CSMA/CD
在CSMA中,由于信道傳播時(shí)延的存在,即使總線上兩個(gè)站點(diǎn)沒(méi)有監(jiān)聽(tīng)到載波信號(hào)而發(fā)送幀時(shí),仍可能會(huì)發(fā)生沖突。由于CSMA算法沒(méi)有沖突檢測(cè)功能,即使沖突已發(fā)和,仍然將已破壞的幀發(fā)送完,使總線的利用率降低。
一種CSMA的改進(jìn)方案是使發(fā)送站點(diǎn)傳輸過(guò)程中仍繼續(xù)監(jiān)聽(tīng)媒體,以檢測(cè)是否存在沖突。如果發(fā)生沖突,信道上可以檢測(cè)到超過(guò)發(fā)送站點(diǎn)本身發(fā)送的載波信號(hào)的幅度,由此判斷出沖突的存在。一于檢測(cè)到?jīng)_突,就立即停止發(fā)送,并向總線上發(fā)一串阻塞信號(hào),用以通知總線上其它各有關(guān)站點(diǎn)。這樣,通道容量就不致因白白傳送已受損的幀而浪費(fèi),可以提高總線的利用率。這種方案稱做載波監(jiān)聽(tīng)多路訪問(wèn)/沖突檢測(cè)協(xié)議,簡(jiǎn)寫(xiě)為CSMA/CD,這種協(xié)議已廣泛應(yīng)用于局域網(wǎng)中。
CSMA/CD的代價(jià)是用于檢測(cè)沖突所花費(fèi)的時(shí)間。對(duì)于基帶總線而言,最壞情況下用于檢測(cè)一個(gè)沖突的時(shí)間等于任意兩個(gè)站之間傳播時(shí)延的兩倍。從一個(gè)站點(diǎn)開(kāi)始發(fā)送數(shù)據(jù)到另一個(gè)站點(diǎn)開(kāi)始接收數(shù)據(jù),也即載波信號(hào)從一端傳播到另一端所需的時(shí)間,稱為信號(hào)傳播時(shí)延。信號(hào)傳播時(shí)延(μs)=兩站點(diǎn)的距離(m)/信號(hào)傳播速度(m/μs)。假定A、B兩個(gè)站點(diǎn)位于總線兩端,兩站點(diǎn)之間的最大傳播時(shí)延為tp。當(dāng)A站點(diǎn)發(fā)送數(shù)據(jù)后,經(jīng)過(guò)接近于最大傳播時(shí)延tp時(shí),B站點(diǎn)正好也發(fā)送數(shù)據(jù),此時(shí)沖突便發(fā)生。發(fā)生沖突后,B 站點(diǎn)立即可檢測(cè)到該沖突,而A站點(diǎn)需再經(jīng)過(guò)一份最大傳播時(shí)延tp后,才能檢測(cè)出沖突。也即最壞情況下,對(duì)于基帶CSMA/CD來(lái)說(shuō),檢測(cè)出一個(gè)沖突的時(shí)間等于任意兩個(gè)站之間最大傳播時(shí)延的兩倍(2tp)。
數(shù)據(jù)幀從一個(gè)站點(diǎn)開(kāi)始發(fā)送,到該數(shù)據(jù)幀發(fā)送完畢所需的時(shí)間和為數(shù)據(jù)傳輸時(shí)延;同理,數(shù)據(jù)傳輸時(shí)延也表示一個(gè)接收站點(diǎn)開(kāi)始接收數(shù)據(jù)幀,到該數(shù)據(jù)幀接收完畢所需的時(shí)間。數(shù)據(jù)傳輸時(shí)延(s)=數(shù)據(jù)幀長(zhǎng)度(bit)/數(shù)據(jù)傳輸速率(bps)。若不考慮中繼器引入的延遲,數(shù)據(jù)幀從一個(gè)站點(diǎn)開(kāi)始發(fā)送,到該數(shù)據(jù)幀被另一個(gè)站點(diǎn)全部接收所需的總時(shí)間,等于數(shù)據(jù)傳輸時(shí)延與信號(hào)傳播時(shí)延之和。
由于單向傳輸?shù)脑?,?duì)于寬帶總線而言,沖突檢測(cè)時(shí)間等于任意兩個(gè)站之間最大傳播時(shí)延的4倍。所以,
對(duì)于寬帶CSMA/CD來(lái)說(shuō),要求數(shù)據(jù)幀的傳輸時(shí)延至少4倍于傳播時(shí)延。
在CSMA/CD算法中,一旦檢測(cè)到?jīng)_突并發(fā)完阻塞信號(hào)后,為了降低再次沖突的概率,需要等待一個(gè)隨機(jī)時(shí)間,然后再使用CSMA方法試圖傳輸。為了保證這種退避操作維持穩(wěn)定采用了一種稱為二進(jìn)制指數(shù)退避和算法,其規(guī)則如下:
(1)對(duì)每個(gè)數(shù)據(jù)幀,當(dāng)?shù)谝淮伟l(fā)生沖突時(shí),設(shè)置一個(gè)參量L=2;
(2)退避間隔取1到L個(gè)時(shí)間片中的一個(gè)隨機(jī)數(shù),1個(gè)小時(shí)片等于兩站之間的最大傳播時(shí)延的兩倍;
(3)當(dāng)數(shù)據(jù)幀再次發(fā)生沖突,由將參量L加倍;
(4)設(shè)置一個(gè)最大重傳次數(shù),超過(guò)該次數(shù),則不再重傳,并報(bào)告出錯(cuò)。
二進(jìn)制指數(shù)退避算法是按后進(jìn)先出LIFO(List In First Out)的次序控制的,即未發(fā)生沖突或很少發(fā)生沖突的數(shù)據(jù)幀,具有優(yōu)先發(fā)送的概率;而發(fā)生過(guò)多次沖突的數(shù)據(jù)幀,發(fā)送成功的概率就更少。
IEEE 802.3就是采用二進(jìn)制指數(shù)退避和1-堅(jiān)持算法的CSMA/CD媒體訪問(wèn)控制方法。這種方法在低負(fù)荷時(shí),如媒體空閑時(shí),要發(fā)送數(shù)據(jù)幀的站點(diǎn)能立即發(fā)送;在重負(fù)荷時(shí),仍能保證系統(tǒng)的穩(wěn)定性。由于在媒體上傳播的信號(hào)會(huì)衰減,為確保能檢測(cè)出沖突信號(hào),CSMA/CD總線網(wǎng)限制一段無(wú)分支電纜的最大長(zhǎng)度為500米。
【編輯推薦】