_3.5 _________信道分配策略

3.5信道分配策略,3.5.1爭(zhēng)用協(xié)議,在第二章中已介紹了靜態(tài)分配策略中的頻分、同步時(shí)分、波分與碼分多路復(fù)用，本章介紹動(dòng)態(tài)分配策略中的爭(zhēng)用與控制訪問(wèn)。最早采用爭(zhēng)用協(xié)議的計(jì)算機(jī)網(wǎng)絡(luò)是美國(guó)夏威夷大學(xué)的ALOHA網(wǎng)，該網(wǎng)通過(guò)無(wú)線信道將各分校的遠(yuǎn)程終端接到本部的主機(jī)上。,1.純ALOHA(PureALOHA),基本思想任何用戶有數(shù)據(jù)發(fā)送就可以發(fā)送；每個(gè)用戶通過(guò)監(jiān)聽(tīng)信道獲知數(shù)據(jù)傳輸是否成功；當(dāng)發(fā)現(xiàn)數(shù)據(jù)傳輸失敗后，各自等待一段隨機(jī)時(shí)間，再重新發(fā)送。,純ALOHA方式中，數(shù)據(jù)可在任意時(shí)刻發(fā)送。,純ALOHA沖突重發(fā),2.時(shí)隙ALOHA系統(tǒng)(SlottedALOHA，或S-ALOHA),基本思想：將時(shí)間分成時(shí)間片(即時(shí)隙T0，slot)，每個(gè)時(shí)間片可以用來(lái)發(fā)送一個(gè)幀；用戶有數(shù)據(jù)要發(fā)送時(shí)，必須等到下一個(gè)時(shí)間片開(kāi)始才能發(fā)送。,時(shí)隙ALOHA工作原理,每一個(gè)幀在到達(dá)后，一般都要在緩沖區(qū)中等待一段時(shí)間(該時(shí)間小于T0),然后在下一時(shí)間片開(kāi)始時(shí)才能發(fā)送出去。,PureALOHAvs.SlottedALOHA,吞吐量S：一幀所占時(shí)間段t內(nèi)成功發(fā)送的平均幀數(shù)網(wǎng)絡(luò)負(fù)載G：時(shí)間段t內(nèi)總共發(fā)出的平均幀數(shù),3.載波監(jiān)聽(tīng)多重訪問(wèn)協(xié)議（CarrierSenseMultipleAccessProtocol,CSMA),1-堅(jiān)持CSMA非堅(jiān)持CSMAP-堅(jiān)持CSMA,即所謂“先聽(tīng)后說(shuō)”。希望傳輸?shù)恼臼紫葘?duì)信道進(jìn)行監(jiān)聽(tīng)以確定是否有別的站在傳輸。若信道空閑，該站可以傳輸，否則，該站將按一定算法退避一段時(shí)間后再試。這可以分為：,1-堅(jiān)持CSMA,當(dāng)一個(gè)站要發(fā)送數(shù)據(jù)時(shí)，執(zhí)行如下步驟：(1)監(jiān)聽(tīng)信道，若信道空閑就發(fā)送；(2)若信道忙則繼續(xù)堅(jiān)持監(jiān)聽(tīng)，直至檢測(cè)到信道空閑后就立即(以概率1)發(fā)送；(3)若有沖突，則隨機(jī)等待一段時(shí)間，重復(fù)步驟(1)。優(yōu)點(diǎn)：只要信道空閑，數(shù)據(jù)就立即得到發(fā)送；缺點(diǎn)：若有兩個(gè)或兩個(gè)以上的站點(diǎn)等發(fā)送，沖突就不可避免。,1-堅(jiān)持CSMA（續(xù)）,非堅(jiān)持CSMA,當(dāng)一個(gè)站要發(fā)送數(shù)據(jù)時(shí)，執(zhí)行如下步驟：(1)監(jiān)聽(tīng)信道，若信道空閑就發(fā)送；(2)若信道忙則放棄(不堅(jiān)持)監(jiān)聽(tīng)，隨機(jī)等待一段時(shí)間，重復(fù)步驟（1）；優(yōu)點(diǎn)：采用隨機(jī)的重發(fā)延遲時(shí)間可減少?zèng)_突可能性；缺點(diǎn)：即使有幾個(gè)站有數(shù)據(jù)要傳送，信道仍然可能處于空閑狀態(tài)，信道利用率較低。,非堅(jiān)持CSMA（續(xù)）,p-堅(jiān)持CSMA,當(dāng)一個(gè)站要發(fā)送數(shù)據(jù)時(shí)，執(zhí)行如下步驟：(1)監(jiān)聽(tīng)信道，若信道空閑就以概率p發(fā)送數(shù)據(jù)，以概率1-p延遲至下一個(gè)時(shí)間片；(2)若信道忙則繼續(xù)堅(jiān)持監(jiān)聽(tīng)，直至下一個(gè)時(shí)間片；(3)至下一個(gè)時(shí)間片后重復(fù)步驟(1)。問(wèn)題：如何選擇p的有效值？設(shè)任一時(shí)刻平均有N個(gè)站有數(shù)據(jù)等待發(fā)送，則一旦當(dāng)前的數(shù)據(jù)發(fā)送完畢，在下一個(gè)時(shí)間片里平均有Np個(gè)站發(fā)送數(shù)據(jù)。若p過(guò)大，使Np1，表明有多個(gè)站試圖發(fā)送，沖突不可避免，所以應(yīng)使Np1；若p過(guò)小，信道利用率會(huì)大大降低。,p-堅(jiān)持CSMA（續(xù)）,Non-persistent，1-，P-Persistent,幾種隨機(jī)訪問(wèn)協(xié)議的性能比較,帶有沖突檢測(cè)的CSMA（CSMA/CD）,ALOHA,CSMA,CSMA/CD,增加“發(fā)送前先監(jiān)聽(tīng)，忙時(shí)則不發(fā)”,改進(jìn),改進(jìn),1-堅(jiān)持CSMA增加“一旦檢測(cè)到?jīng)_突，立即停止發(fā)送”,ALOHA、S-ALOHA,1-堅(jiān)持CSMA、非堅(jiān)持CSMA、p-堅(jiān)持CSMA,Ethernet,CSMA/CD工作的三個(gè)周期,傳輸周期(Transmissionperiod)競(jìng)爭(zhēng)周期(Contentionperiod)空閑周期(Idleperiod),CSMA/CD中競(jìng)爭(zhēng)時(shí)間片長(zhǎng)度？,競(jìng)爭(zhēng)時(shí)間片長(zhǎng)度取為網(wǎng)絡(luò)中最大傳輸時(shí)延的2倍。也即站點(diǎn)開(kāi)始發(fā)送后最多經(jīng)2時(shí)間就能確認(rèn)傳輸是否成功。,CSMA/CD檢測(cè)沖突時(shí)間,站點(diǎn)開(kāi)始發(fā)送后最多經(jīng)2時(shí)間就能確認(rèn)傳輸是否成功一來(lái)一回的時(shí)延定出了以太網(wǎng)的最大直徑，也即沖突域3.最大直徑時(shí)，一來(lái)一回的時(shí)延512位時(shí)間（對(duì)所有以太網(wǎng)）,CSMA/CD檢測(cè)沖突時(shí)間,上述情況下，檢測(cè)沖突的時(shí)間等于總線上最遠(yuǎn)兩個(gè)站點(diǎn)之間端到端延遲時(shí)間的兩倍（即一來(lái)一回時(shí)延2）。這種CSMA/CD沖突檢測(cè)，對(duì)發(fā)送站所發(fā)送的數(shù)據(jù)幀長(zhǎng)度有一定要求，以太幀長(zhǎng)度的最小值不能小于512位，即64字節(jié)(如所發(fā)送的信息不足時(shí)，可加以填充)。這是因?yàn)镃SMA/CD要求發(fā)送站一邊發(fā)送數(shù)據(jù)，一邊進(jìn)行沖突檢測(cè)，若檢測(cè)到?jīng)_突則立即中止發(fā)送，然后推遲一段時(shí)間，再發(fā)送。如果所發(fā)送的幀長(zhǎng)度太短，發(fā)送站還沒(méi)來(lái)得及將發(fā)送與接收數(shù)據(jù)進(jìn)行比較(即檢測(cè)沖突)就已經(jīng)發(fā)送完了。,CSMA/CD檢測(cè)沖突時(shí)間,等待的隨機(jī)時(shí)間，用截?cái)嗟亩M(jìn)制指數(shù)退避算法。隨機(jī)時(shí)間的基本單位：為競(jìng)爭(zhēng)時(shí)間片的長(zhǎng)度2端到端的傳播時(shí)延(即最遠(yuǎn)兩個(gè)站之間的傳播時(shí)延),檢測(cè)到?jīng)_突后，退避等待的隨機(jī)時(shí)間？,算法規(guī)則如下：設(shè)1個(gè)時(shí)間片等于兩站之間的最大傳播時(shí)延的兩倍（2）；(1)當(dāng)?shù)谝淮伟l(fā)生沖突時(shí)，設(shè)置沖突計(jì)數(shù)k=1，(2)退避等待一個(gè)隨機(jī)時(shí)間，取值為n個(gè)時(shí)間片;n為0,1,2,.,2k-1中的一個(gè)隨機(jī)數(shù)(3)當(dāng)再發(fā)送幀時(shí)若又發(fā)生沖突，則k=k+1,但若k加到10后便不再增加,仍維持k=10,即k=min重發(fā)次數(shù)，10,轉(zhuǎn)(2)；(4)設(shè)置一個(gè)最大重發(fā)次數(shù)16，超過(guò)該次數(shù)，則不再重傳，并報(bào)告出錯(cuò)。,CSMA/CD小結(jié),工作原理：監(jiān)聽(tīng)到信道空閑,就立即發(fā)送數(shù)據(jù)，且邊發(fā)送邊監(jiān)聽(tīng)(2時(shí)間內(nèi)),若監(jiān)聽(tīng)到?jīng)_突，沖突方立即停止發(fā)送，并發(fā)送Jam干擾信號(hào)串強(qiáng)化沖突，通知全網(wǎng)站點(diǎn)，使信道很快空閑，從而提高效率。1-堅(jiān)持CSMA,再加上CD(沖突檢測(cè))。沖突檢測(cè)方法：（1）比較接收到的信號(hào)電壓的大小（2）檢測(cè)曼徹斯特編碼的過(guò)零點(diǎn)（3）比較接收到的信號(hào)與剛發(fā)出的信號(hào)退避算法：為截?cái)嗟亩M(jìn)制指數(shù)退避算法，來(lái)決定重發(fā)時(shí)延：從0,1,2,.,2k-1中隨機(jī)取一個(gè)數(shù)r，重發(fā)時(shí)延=r(2)，其中k=min重發(fā)次數(shù)，10,3.5.2無(wú)沖突協(xié)議,特點(diǎn)：數(shù)據(jù)發(fā)送無(wú)沖突方法：(1)預(yù)約；(2)輪轉(zhuǎn)預(yù)約例：比特映像介質(zhì)訪問(wèn)控制協(xié)議小時(shí)間片輪換優(yōu)先權(quán)介質(zhì)訪問(wèn)控制協(xié)議二進(jìn)制地址相加輪轉(zhuǎn)例：選擇輪詢TokenPassing,預(yù)約法1,基本思想-各站在預(yù)約幀中對(duì)應(yīng)位預(yù)約，之后有預(yù)約的站依序發(fā)送,預(yù)約法2,基本思想-某個(gè)站在預(yù)約之后可以立即發(fā)送，降低了每個(gè)站的平均等待時(shí)間,預(yù)約法3,基本思想-從高位到低位，各站將二進(jìn)制地址相或，相或結(jié)果為1、本站地址為0者退出預(yù)約過(guò)程,輪轉(zhuǎn)法1：選擇,輪轉(zhuǎn)法2：輪詢,輪轉(zhuǎn)法3：Token-Passing,TokenPassing流程,3.5.3有限爭(zhēng)用協(xié)議,結(jié)合爭(zhēng)用協(xié)議和無(wú)沖突協(xié)議的長(zhǎng)處在輕負(fù)載時(shí)獲得較好的延遲特性在重負(fù)載時(shí)獲得較高的信道利用率