用于總線型拓撲結(jié)構(gòu),隨機訪問的每個發(fā)送站必須判斷是否有沖突發(fā)生,如果有則應(yīng)延遲一個隨機時間重發(fā)。
一、aloha介質(zhì)訪問方法
aloha網(wǎng):跨越四個小島的夏威夷大學(xué)的校園網(wǎng),第一個使用報文包、無線通信的廣播式網(wǎng)絡(luò)。
1.純 aloha
策略:完全隨機式,任意一個站點只要有數(shù)據(jù)要發(fā)送就將其送到網(wǎng)上,如果在整個發(fā)送過程中沒有其它站發(fā)送數(shù)據(jù),則發(fā)送成功;如果在開始發(fā)送時或在發(fā)送過程中有其它站發(fā)送數(shù)據(jù),就會產(chǎn)生沖突,于是等待一段隨機時間再重發(fā);若仍然沖突,則反復(fù)重發(fā)直到成功為止。
特點: 當負載增加(使用網(wǎng)絡(luò)傳送數(shù)據(jù)的站點增多,發(fā)送數(shù)據(jù)量大)時,沖突率會很高;
性能分析計算表明純aloha網(wǎng)通道利用率(單位時間內(nèi)成功傳送幀所占的時間)最大值為0.184。
2.時隙 aloha 改進:將信道以一幀的發(fā)送時間為單位劃分為時間片(slot),時間片長度為(需設(shè)立中心時鐘以便同步),要求每一幀只能在時間片開始時傳輸,若因完全重疊而產(chǎn)生沖突,則分別延遲隨機個數(shù)的時間片后重發(fā),直至發(fā)送成功,或因重發(fā)次數(shù)超過規(guī)定而放棄發(fā)送,向上級報告。
工作流程:
特點:減少因兩幀部分重疊引起的沖突,性能分析計算表明時隙aloha的最大信道利用率是純aloha的兩倍,即0.368。
二、csma 和 csma/cd 介質(zhì)訪問方法
1.載波監(jiān)聽多路訪問csma(carries multiple access)——是對aloha協(xié)議的一種改進協(xié)議
工作原理:“先聽后說”,每個站點在發(fā)送前監(jiān)聽信道上是否有其他站點正在發(fā)送數(shù)據(jù),如果信道忙就暫不發(fā)送,否則立即發(fā)送,減少了發(fā)生沖突的概率。
監(jiān)聽、發(fā)送策略:
三種不同的協(xié)議:——都不能避免沖突發(fā)生,只是沖突的概率不同,一旦有沖突
發(fā)生則要延遲隨機個時間片τ,再重復(fù)監(jiān)聽過程。
1—堅持型:連續(xù)監(jiān)聽,立即發(fā)送。(沖突概率高,但信道利用率也較高)
非堅持型:斷續(xù)監(jiān)聽,立即發(fā)送。(沖突概率相對減少,但信道利用率低)
p—非堅持型:連續(xù)監(jiān)聽,以概率p發(fā)送,以概率(1-p)延遲一個時間片發(fā)送。
2.載波監(jiān)聽多路訪問/沖突檢測(csma/cd)介質(zhì)訪問控制——是對csma的改進方案,增加了 “沖突檢測”的功能
工作原理:“邊發(fā)邊聽”,發(fā)送前連續(xù)監(jiān)聽,如果空閑立即發(fā)送;發(fā)送后繼續(xù)監(jiān)聽,檢測有無沖突發(fā)生,若檢測到?jīng)_突發(fā)生,則沖突各方立即停止發(fā)送,并發(fā)出一串固定格式的阻塞信號以強化沖突,然后退讓一段時間再重發(fā)。
實現(xiàn)沖突檢測的幾種方法:
通過硬件檢查因信號迭加引起的接收信號電平擺動變大是否超過某一閥值,來判斷是否有沖突發(fā)生;
通過檢查曼徹斯特編碼信號的每位中間有無過零點(零點是否偏移)來判斷是否發(fā)生沖突;
邊發(fā)邊收,將發(fā)送的信號與接收的信號相比較,若不一致則說明有沖突存在。
csma/cd流程圖:
一旦有沖突發(fā)生,需要多長時間來檢測沖突?
定理1:對基帶總線而言,最壞情況下用于檢測一個沖突的時間為任意兩個站點之間最大傳播時延的兩倍。
信號傳播時延tp :從一個站點開始發(fā)送數(shù)據(jù)幀到另一個站點開始接收數(shù)據(jù)幀所需要的時間。
信號傳播時延tp =兩站間的距離(m)/信號傳播速度(200m/s)
例:假設(shè)a、b兩站相距最遠,幀發(fā)送時間為1,a到b的傳播延遲為0.5,從下圖可見沖突檢測所需時間為傳播延遲的兩倍。
定理2:若不考慮中繼器的延遲,數(shù)據(jù)幀從一個站點開始發(fā)送到該數(shù)據(jù)幀被另一個站點全部接收所需的時間,等于數(shù)據(jù)傳輸時延與信號傳播時延之和。
數(shù)據(jù)傳輸時延:從一個站點開始發(fā)送數(shù)據(jù)幀到另一個站點全部接收數(shù)據(jù)幀所需要的時間。
數(shù)據(jù)傳輸時延=數(shù)據(jù)幀的長度(bit)/數(shù)據(jù)傳輸速度(bit/s)
定理3:為了確保發(fā)送站點能在傳輸時檢測到可能存在的沖突,數(shù)據(jù)幀的傳輸時延至少要兩倍于信號傳播時延,即數(shù)據(jù)傳輸時延≥2tp 。
最短數(shù)據(jù)幀長(bit)=2(任意兩站間的最大距離/信號傳播速度)數(shù)據(jù)速率bit/s
二進制指數(shù)退避算法:一種確定隨機延遲時間td的算法,當重復(fù)發(fā)生一次沖突,就使后退延遲加倍,即后退延遲按二進制指數(shù)增長的辦法。
td=r·tr 其中:tr為時間片,等于傳播延遲2倍;r是(0,2k-1)范圍內(nèi)的均勻分布的隨機數(shù);
k滿足: k=min(n,10) 這里n為重發(fā)次數(shù)。
算法:
第一次沖突產(chǎn)生后,每個站點等待0或l個位時間片;第二次沖突發(fā)生后,從0,l,2,3中取一隨機數(shù),該數(shù)即等待的時間片數(shù);依此類推,達到第10次沖突后,最大時間片個數(shù)固定為210-1=1023;16次沖突后,不再傳送,向計算機報告發(fā)送失敗,由高層恢復(fù)。
目的:減少再次沖突的次數(shù),需多延遲、多等待,與信道負載有關(guān)。