_3.5 _________信道分配策略

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