?ComputerNetworksv4?cs.sjtu2004-5-23

第4章介質(zhì)訪問子層

?信道分配問題

?多路訪問協(xié)議CSMA

?:?以太網(wǎng)

?數(shù)據(jù)鏈路層交換

/net330第4章MAC層1/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道分配問題

?信道的靜態(tài)分配

?信道的動態(tài)分配

/net330第4章MAC層2/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道的靜態(tài)分配

?頻分多路復(fù)用FDM

(FrequencyDivisionMultiplexing)

?時分多路復(fù)用TDM

(TimeDivisionMultiplexing)

?靜態(tài)分配的問題

＞延遲時間長

＞信道利用率低

/net330第4章MAC層3/186

?ComputerNetworksv4?cs.sjtu2004-5-23

排隊論模型

?模型假設(shè)

信道容量Cb/s

信道數(shù)據(jù)到達平均速率（服從泊松分布）九幀/秒

幀的長度平均值（服從指數(shù)分布）1/|LLbit/幀

平均延時T

?:?排隊模型網(wǎng)絡(luò)節(jié)點

隊列

報文到達速率九（幀/S）信道輸出速率J1C（幀/s）

/net330第4章MAC層4/186

?ComputerNetworksv4?cs.sjtu2004-5-23

生滅過程

?一個穩(wěn)定的生滅過程

如該過程穩(wěn)定，則解得：Pi=PoP1

入Po=UCPi①其中：p=V(pC)

1

Xp1+pCp1=Xp0+pCp2②則:Po=-P

則系統(tǒng)中的平均顧客數(shù)

Xp2+pCp2=Xp1+pCp3③

00

N=?Pi=

i=Q1一夕

/net330第4章MAC層5/186

?ComputerNetworksv4?cs.sjtu2004-5-23

Little定理

?在穩(wěn)定狀態(tài)下，存儲在網(wǎng)絡(luò)中的報文平均數(shù)，

等于報文的平均到達率乘以這些報文在網(wǎng)絡(luò)中

經(jīng)歷的平均時間

即：N=XT

pl-(2///C)

得：T=~^

/dC—2

在頻分多路復(fù)用條件下，每個信道的容量為C/N,每個信

道的報文到達率為九/N

所以：TFDM=NT即平均增加N倍

/net330第4章MAC層6/186

?ComputerNetworksv4?cs.sjtu2004-5-23

靜態(tài)FDM的性能

?頻段分成N段，平均延時增加N倍

?頻段分成N段，當(dāng)用戶數(shù)小于N時，不產(chǎn)

生爭用，但并非每個被分配的用戶每時

每刻都在通信，所以，信道的利用率較

低o且不能調(diào)整

時分多路復(fù)用TDM(Time-DivisionMultiplexing)

與FDM相似

/net330第4章MAC層7/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道分配問題

?:?信道的靜態(tài)分配

?:?信道的動態(tài)分配?

/net330第4章MAC層8/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道的動態(tài)分配

有關(guān)動態(tài)分配的五個假設(shè)：

?站模型(StationModel)

?單通道假設(shè)(SingleChannelAssumption)

?沖突假設(shè)(CollisionAssumption)

?時間假設(shè)：

>時間連續(xù)(ContinuousTime)

>時間分時隙(SlottedTime)

?偵聽假設(shè)

>載波偵聽(CarrierSense)

>非載波偵聽(noCarrierSense)

/net330第4章MAC層9/186

?ComputerNetworksv4?cs.sjtu2004-5-23

站模型

?由N個獨立的站（計算機、電話、個人通信設(shè)

備）組成

?每個站都可產(chǎn)生待發(fā)送的幀

在時間At內(nèi)，一幀生成的概率為九A3其中九是

常量（新幀到達速率）

載波偵聽（CarrierSense）

?一旦生成一幀，就等待發(fā)送，直到成功發(fā)送

各站都是相互獨立地、以固定速率產(chǎn)生數(shù)據(jù)幀，某站被

阻塞，則不會有新的幀產(chǎn)生，即每個站只有一個用戶

/net330第4章MAC層10/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道的動態(tài)分配

有關(guān)動態(tài)分配的五個假設(shè)：

?站模型(StationModel)

?單通道假設(shè)(SingleChannelAssumption)A

?沖突假設(shè)(CollisionAssumption)

?時間假設(shè)：

>時間連續(xù)(ContinuousTime)

>時間分時隙(SlottedTime)

?偵聽假設(shè)

>載波偵聽(CarrierSense)

>非載波偵聽(noCarrierSense)

/net330第4章MAC層11/186

?ComputerNetworksv4?cs.sjtu2004-5-23

單通道假設(shè)

?所有通信，包括發(fā)送和接收，都通過單

?通道進行

?所有的站都在該通道上發(fā)送或接收信息

。所有站都是平等的，各站沒有主從之分

任何時刻只允許一個站可以發(fā)送，都是通過爭用才能取

得發(fā)送權(quán)。（如有主從之分，則存在單點故障）

/net330第4章MAC層12/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道的動態(tài)分配

有關(guān)動態(tài)分配的五個假設(shè)：

?站模型(StationModel)

?單通道假設(shè)(SingleChannelAssumption)

沖突假設(shè)(CollisionAssumption)?

?時間假設(shè)：

>時間連續(xù)(ContinuousTime)

>時間分時隙(SlottedTime)

?偵聽假設(shè)

>載波偵聽(CarrierSense)

>非載波偵聽(noCarrierSense)

/net330第4章MAC層13/186

?ComputerNetworksv4?cs.sjtu2004-5-23

沖突假設(shè)

如兩幀同時發(fā)送，則發(fā)生沖突

?所有的站都能檢測到?jīng)_突

?:?沖突的幀必須重發(fā)，除了沖突引起的差

錯外，沒有其它差錯

由于每個站都是通過爭用才能取得發(fā)送權(quán)，所以沖

突是不可避免的，但也有采用某些競爭機制來消除

沖突（令牌網(wǎng)）

/net330第4章MAC層14/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道的動態(tài)分配

有關(guān)動態(tài)分配的五個假設(shè)：

?站模型(StationModel)

?單通道假設(shè)(SingleChannelAssumption)

?沖突假設(shè)(CollisionAssumption)

?時間假設(shè)：

>時間連續(xù)(ContinuousTime)

>時間分時隙(SlottedTime)

?偵聽假設(shè)

>載波偵聽(CarrierSense)

>非載波偵聽(noCarrierSense)

/net330第4章MAC層15/186

?ComputerNetworksv4?cs.sjtu2004-5-23

時間假設(shè)

?時間連續(xù)(ContinuousTime)：

幀的發(fā)送可在任意時刻

?時間分時隙(SlottedTime)：

時間被分為時隙，幀在時隙的開始處發(fā)

送，一個時隙中可發(fā)送0、1或多幀，幀

在空閑時隙中發(fā)送成功或發(fā)生沖突

把時間分片或不分片都是可能的，但任何一個系統(tǒng)都

只能選用一種方式

/net330第4章MAC層16/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道的動態(tài)分配

有關(guān)動態(tài)分配的五個假設(shè)：

?站模型(StationModel)

?單通道假設(shè)(SingleChannelAssumption)

?沖突假設(shè)(CollisionAssumption)

?時間假設(shè)：

>時間連續(xù)(ContinuousTime)

>時間分時隙(SlottedTime)

?偵聽假設(shè)

>載波偵聽(CarrierSense)

>非載波偵聽(noCarrierSense)

/net330第4章MAC層17/186

?ComputerNetworksv4?cs.sjtu2004-5-23

偵聽假設(shè)

載波偵聽(CarrierSense)：

所有的站在使用信道前，都可檢測到當(dāng)前

信道是否正被使用5如信道正忙,則等待

?非載波偵聽(noCarrierSense)：

所有的站在使用信道前，都不檢測當(dāng)前信

道是否正被使用，只是盲目發(fā)送

在局域網(wǎng)中，常采用載波偵聽；而在無線網(wǎng)中則不

采用載波偵聽

/net330第4章MAC層18/186

?ComputerNetworksv4?cs.sjtu2004-5-23

第4章介質(zhì)訪問子層

?信道分配問題

?多路訪問協(xié)議CSMAA

?以太網(wǎng)

?數(shù)據(jù)鏈路層交換

/net330第4章MAC層19/186

?ComputerNetworksv4?cs.sjtu2004-5-23

多路訪問協(xié)議CSMA

?純ALOHA------

?分隙ALOHA------D>

?載波偵聽多路訪問協(xié)虹

/net330第4章MAC層20/186

?ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA的原理

?如果時間以時隙(TimeSlot)計，每個時隙

的長度為一個標(biāo)準(zhǔn)長度的幀的發(fā)送時間t,則

在2t時間內(nèi)不能有新幀產(chǎn)生，否則沖突

t0t0+t"2tt0+3t時間h

V沖突危險區(qū)A

TnbmP253Fig.4-2陰影幀的沖突危險區(qū)

/net330第4章MAC層21/186

?ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA的原理（續(xù)）

任何一個站都可以在幀生成后立即

發(fā)送（可能沖突），并通過信號的

反饋，檢測信道，以確定發(fā)送是否

成功。如發(fā)送失敗，則經(jīng)隨機延時

后再發(fā)送

/net330第4章MAC層22/186

?ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA信道的效率

幀時(FrameTime)：發(fā)送一個標(biāo)準(zhǔn)長度

的幀所需的時間

設(shè)：無限多個用戶產(chǎn)生新幀的概率服從泊松分布

平均每個幀時產(chǎn)生S個新幀

則：當(dāng)S>1時，將每個幀都沖突

所以，吞吐率應(yīng)為0vSv1

除新幀外，凡沖突的幀也要重發(fā)

/net330第4章MAC層23/186

?ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA信道的效率（續(xù)）

設(shè)：其平均值為G幀/幀時，G中包括每個幀時內(nèi)

產(chǎn)生的新幀S和由于沖突而需重發(fā)的幀

當(dāng)輕負(fù)載（Svv1。0）時，幾乎無沖突，則G^S

當(dāng)重負(fù)載（S-1）時，沖突頻繁，則G>S

t0t0+tt0+2tt0+3t—時間

Y沖突危險區(qū)A

/net330第4章MAC層24/186

?ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA的吞吐率

設(shè)：在任一幀時內(nèi)生成k幀（包括新舊幀）

的概率服從泊松分布，為：心=0-6

則：生成。幀的概率為P。二e?

兩個幀時內(nèi)產(chǎn)生的平均幀數(shù)為2G

即：心等Po=&2G

由于S=GP。

所以S=Ge2G

/net330第4章MAC層25/186

?ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA的吞吐率（續(xù)）

對于：S=Ge2G

得：S5=&2G+G&2G(-2)并令其為0

e2G.2G&2G=o

2G=1

G=0.5時，S有最大值

S=1/(2e)

0.184

在純ALOHA中，其吞吐率最大為0?184

/net330第4章MAC層26/186

?ComputerNetworksv4?cs.sjtu2004-5-23

多路訪問協(xié)議

?純ALOHA

?分隙ALOHA

?載波偵聽多路訪問協(xié)議

/net330第4章MAC層27/186

?ComputerNetworksv4?cs.sjtu2004-5-23

分隙ALOHA的原理

在一個時隙內(nèi)只產(chǎn)生一個新

1

L

,1

幀，新幀不允許立即發(fā)送，I1

卜+何

將在下一個時隙的開始處

t0+t口2t

%+t時發(fā)送，不會發(fā)生沖突

時間

在一個時隙內(nèi)產(chǎn)生一個以上

新幀，在前一個時隙結(jié)束

%+t時發(fā)送，兩個以上的幀t°+att0+pt；;

t0+tt0+2t

同時發(fā)送，將發(fā)生沖突沖突危險區(qū)

/net330第4章MAC層28/186

?ComputerNetworksv4?cs.sjtu2004-5-23

分隙ALOHA的原理(續(xù))

?分隙ALOHA的時間以時隙(TimeSlot)為單位

?時隙的長度對應(yīng)一幀的傳輸時間，其起點由專

門的信號來標(biāo)志

?新幀的產(chǎn)生是隨機的，但分隙ALOHA不允許

隨機發(fā)送，凡幀的發(fā)送必須在時隙的起點，即

沖突危險區(qū)是原來的一半

沖突主要發(fā)生在時隙的起點，一旦發(fā)送成功，則不

會出現(xiàn)沖突。即生成新幀并等待發(fā)送的這一幀時

內(nèi)，是沖突危險區(qū)，為原來的一半

/net330第4章MAC層29/186

?ComputerNetworksv4?cs.sjtu2004-5-23

分隙ALOHA的吞吐率

?在一個時隙的起點沒有其它幀發(fā)送的概

G

率為：Po=e

G

所以：S=GP0=Ge'

?當(dāng)G=1時,吞吐量S為最大S標(biāo)0.36

/net330第4章MAC層30/186

ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA和分隙ALOHA的比較

?純ALOHA中，一旦產(chǎn)生新幀，就立即

發(fā)送，全然不顧是否有用戶正在發(fā)送，

所以發(fā)生沖突的可能伴隨著發(fā)送的整個

過程,

?分隙ALOHA中，規(guī)定發(fā)送行為必須在

時隙的開始，一旦在發(fā)送開始時沒有沖

突，則該幀將成功發(fā)送

/net330第4章MAC層31/186

?ComputerNetworksv4?cs.sjtu2004-5-23

純ALOHA和分隙ALOHA的比較（續(xù)）

S

為

每

幀

時

內(nèi)

的

吞

吐

率

TnbmP254Fig.4-3ALOHA系統(tǒng)中吞吐率和幀產(chǎn)生率之間的關(guān)系

/net330第4章MAC層32/186

?ComputerNetworksv4?cs.sjtu2004-5-23

多路訪問協(xié)議

?純ALOHA

?分隙ALOHA

。載波偵聽多路訪問協(xié)議?

/net330第4章MAC層33/186

?ComputerNetworksv4?cs.sjtu2004-5-23

載波偵聽多路訪問協(xié)議CSMA

?載波偵聽協(xié)議(CarrierSenseProtocol)

持續(xù)和非持續(xù)CSMA(CarrierSenseMultiple

Access,載波偵聽多路訪問)

>1-持續(xù)CSMAA

>非持續(xù)CSMA(NonpersistentCSMA)

>p-持續(xù)CSMA(p-persistentCSMA)

?CSMA協(xié)議的沖突和沖突檢測

/net330第4章MAC層34/186

?ComputerNetworksv4?cs.sjtu2004-5-23

1-持續(xù)CSMA

?每個站在發(fā)送前，先偵聽信道，如信

道正忙，則等待并持續(xù)偵聽，一旦信

道空閑，立即發(fā)送，即發(fā)送的概率為

1；如沖突，則延時一隨機時隙數(shù)后,

重新發(fā)送

/net330第4章MAC層35/186

?ComputerNetworksv4?cs.sjtu2004-5-23

載波偵聽多路訪問協(xié)議CSMA

?載波偵聽協(xié)議(CarrierSenseProtocol)

持續(xù)和非持續(xù)CSMA(CarrierSenseMultiple

Access,載波偵聽多路訪問)

>1-持續(xù)CSMA

>非持續(xù)CSMA(NonpersistentCSMA)?

>p-持續(xù)CSMA(p-persistentCSMA)

?CSMA協(xié)議的沖突和沖突檢測

/net330第4章MAC層36/186

?ComputerNetworksv4?cs.sjtu2004-5-23

非持續(xù)CSMA

(NonpersistentCSMA)

每個站在發(fā)送前，先偵聽信道，如

信道正忙，則不再繼續(xù)偵聽，而是

延時一隨機時隙數(shù)后，再偵聽信道

/net330第4章MAC層37/186

瞰?ComputerNetworksv4?cs.sjtu2004-5-23

“載波偵聽多路訪問協(xié)議CSMA

?載波偵聽協(xié)議(CarrierSenseProtocol)

持續(xù)和非持續(xù)CSMA(CarrierSenseMultiple

Access,載波偵聽多路訪問)

>1一持續(xù)CSMA

>非持續(xù)CSMA(NonpersistentCSMA)

>p-持續(xù)CSMA(p-persistentCSMA)

?CSMA協(xié)議的沖突和沖突檢測

/net330第4章MAC層38/186

?ComputerNetworksv4?cs.sjtu2004-5-23

p-持續(xù)CSMA

(p-persistentCSMA)

?用于分隙信道

?先偵聽信道，如信道正忙，則等到下

一時隙；如信道空閑，則以概率P發(fā)

送,而以概率q=(1?p)把本次發(fā)送延至

下一時隙，直至發(fā)送成功

/net330第4章MAC層39/186

?ComputerNetworksv4?cs.sjtu2004-5-23

載波偵聽多路訪問協(xié)議CSMA

:?載波偵聽協(xié)議(CarrierSenseProtocol)

持續(xù)和非持續(xù)CSMA(CarrierSenseMultiple

Access,載波偵聽多路訪問）

>1一持續(xù)CSMA

>非持續(xù)CSMA(NonpersistentCSMA)?

>p-持續(xù)CSMA(p-persistentCSMA)

?CSMA協(xié)議的沖突和沖突檢測A

/net330第4章MAC層40/186

?ComputerNetworksv4?cs.sjtu2004-5-23

?CSMA協(xié)議的沖突和沖突檢測

?帶沖突檢測的CSMA

?無沖突的多路訪問協(xié)議

?有限競爭協(xié)議

/net330第4章MAC層41/186

?ComputerNetworksv4?cs.sjtu2004-5-23

傳播時延對載波監(jiān)聽的影響

?但CSMA并不能完全解決沖突問題

如兩個或多個準(zhǔn)備發(fā)送的站都檢測到信

道空閑而同時發(fā)送將發(fā)生沖突

/net330第4章MAC層42/186

?ComputerNetworksv4?cs.sjtu2004-5-23

帶沖突檢測的CSMA

CSMA/CD

CarrierSenseMultipleAccess/CollisionDetection

帶沖突檢測的載波偵聽多路訪問

CSMA/CD的概^念模型：

It壹爭時隙J一旦沖突，則放

|°兄-7腺J棄并隨機延時

幀innn幀innnnrn幀i11幀i

V

Y人Y~V~)

傳輸周期競爭周期時間------->空閑周期

TnbmP258Fig.4-5CSMA心D有三種狀態(tài)：競爭、傳輸或空閑

/net330第4章MAC層43/186

?ComputerNetworksv4?cs.sjtu2004-5-23

CSMA/CD的要點

在一幀傳輸完成后的時刻％,想要發(fā)送的

站點都可以嘗試發(fā)送

?如兩個或多個站點同時發(fā)送則發(fā)生沖突

?判斷出沖突后，立即停止發(fā)送，并延時

一個隨機時隙數(shù)后，通常其中的一個站

點將發(fā)送成功

/net330第4章MAC層44/186

?ComputerNetworksv4?cs.sjtu2004-5-23

沖突的檢測

?信號電平法

基于基帶傳輸。兩個幀信號疊加后，電壓大一倍

過零點檢測法

用曼切斯特編碼時，零點在每比特的正中央。有干擾

時，則可能偏移

?自收發(fā)檢測法

在發(fā)送數(shù)據(jù)的同時也在接收，并逐比特比較

/net330第4章MAC層45/186

?ComputerNetworksv4?cs.sjtu2004-5-23

CSMA/CD發(fā)生沖突時

對信道占用時間的影響

AB

信

道

占

用

時

間

如一個站點發(fā)送后，經(jīng)2T后，沒有沖突，即發(fā)送成功

典型地，一公里長的同軸電纜，工。

/net330第4章MAC層46/186

?ComputerNetworksv4?cs.sjtu2004-5-23

?CSMA協(xié)議的沖突和沖突檢測

?帶沖突檢測的CSMA

?無沖突的多路訪問協(xié)議

?有限競爭協(xié)議

/net330第4章MAC層47/186

?ComputerNetworksv4?cs.sjtu2004-5-23

無沖突的協(xié)議

信道的爭用勢必發(fā)生沖突，沖突將降低信

道的利用率

。位圖協(xié)議?

?二進制倒計數(shù)法

/net330第4章MAC層48/186

?ComputerNetworksv4?cs.sjtu2004-5-23

位圖協(xié)議

。如有N個站點共享信道，編號為。?N?1,其競爭周期

將分為N個時隙，每個站點占有一個時隙，如某站準(zhǔn)

備發(fā)送，則可在屬于它的時隙內(nèi)填入1,一個競爭周期

后，則將按順序發(fā)送，不會產(chǎn)生沖突

8個爭用時隙8個爭用時隙

_________________人_________________

012345670123456701234567

I卜□卜川□FilIhl111110

TnbmP259Fig,4-6基本位圖協(xié)議

/net330第4章MAC層49/186

?ComputerNetworksv4?cs.sjtu2004-5-23

位圖協(xié)議的效率分析

?在低負(fù)荷條件下，如每幀的數(shù)據(jù)量的dbit,額

外比特數(shù)為N,則效率為d/(d+N)

在高負(fù)荷條件下，即所有的站都希望一幀接一

幀發(fā)送，位圖按平均分配給每一幀，一幀只占

一位，則效率為d/(d+1)

缺點：位圖協(xié)議無法考慮優(yōu)先級

/net330第4章MAC層50/186

?ComputerNetworksv4?cs.sjtu2004-5-23

無沖突的協(xié)議

信道的爭用勢必發(fā)生沖突，沖突將降低信

道的利用率

?:?位圖協(xié)議

?二進制倒計數(shù)法

/net330第4章MAC層51/186

?ComputerNetworksv4?cs.sjtu2004-5-23

二進制倒計數(shù)法

?需要一個仲裁機構(gòu)決定哪個站點發(fā)送

?:?把站號按相同長度的二進制數(shù)編號，需

要發(fā)送的站逐個按高位到低位在爭用周

期開始時發(fā)送，凡低序號的站點發(fā)現(xiàn)有

高序號站點也希望發(fā)送，則退出競爭，

即：高序號站點優(yōu)先

/net330第4章MAC層52/186

?ComputerNetworksv4?cs.sjtu2004-5-23

二進制倒計數(shù)法舉例

如有四個準(zhǔn)備發(fā)送的站的站號分別為0010(2#)、

0100(4#)、1001(9#)和1010(10#),當(dāng)爭用周期開

始后，分別將最高位送出，仲裁機構(gòu)作或運算結(jié)

果送回。2#和4#檢測到1,則知道有高序號的站

點也希望發(fā)送，則退出競爭，不再發(fā)送下一位，

9#和10#繼續(xù)送出次高位，仍不分高下，再繼

續(xù)，9#退出，最后10#得到幀的發(fā)送權(quán)

/net330第4章MAC層53/186

?ComputerNetworksv4?cs.sjtu2004-5-23

信道效率分析

?N個站的二進制編碼所需位數(shù)是logzN位

?:?信道的效率為：d/(d+log2N)

?如果規(guī)定每個幀的幀頭為發(fā)送地址，即

競爭的同時也在發(fā)送。則效率為100%

/net330第4章MAC層54/186

?ComputerNetworksv4?cs.sjtu2004-5-23

?CSMA協(xié)議的沖突和沖突檢測

?帶沖突檢測的CSMA

?無沖突的多路訪問協(xié)議

?有限競爭協(xié)議A

/net330第4章MAC層55/186

?ComputerNetworksv4?cs.sjtu2004-5-23

有限競爭協(xié)議

?有限競爭協(xié)議(LimitedContention

Protocol)即：在低負(fù)荷時使用競爭

法，在高負(fù)荷時，使用無沖突法

＞對稱競爭協(xié)議受，

＞適應(yīng)樹搜索協(xié)議

(AdaptiveTreeWalkProtocol)

/net330第4章MAC層56/186

?ComputerNetworksv4?cs.sjtu2004-5-23

對稱競爭協(xié)議

?對稱競爭協(xié)議的性能：

每個站申請使用信道的概率相同，都為P

設(shè)：有k個站參與信道競爭

每個站點在每個時隙中的發(fā)送概率為p

那么：某個給定時隙內(nèi)，站點成功獲得信道的概率為:

kp(1-p)k-1

/net330第4章MAC層57/186

?ComputerNetworksv4?cs.sjtu2004-5-23

當(dāng)pk=1時成功率最高

成

功

概

率

/net330第4章MAC層58/186

?ComputerNetworksv4?cs.sjtu2004-5-23

當(dāng)pk=1時成功率最高（續(xù)）

?k較小時，成功率較高；k.8時，成功

率為1/e

?當(dāng)站點數(shù)為2?4時，成功概率急劇下降

?當(dāng)站點數(shù)達5時，成功概率將逐漸接近1/e

k2345810oo

Pr[pk=1]0.50.4440.4220.4100.3930.3870.368

/net330第4章MAC層59/186

?ComputerNetworksv4?cs.sjtu2004-5-23

有限競爭協(xié)議

?有限競爭協(xié)議(LimitedContention

Protocol)即：在低負(fù)荷時使用競爭

法，在高負(fù)荷時，使用無沖突法

＞對稱競爭協(xié)議

＞適應(yīng)樹搜索協(xié)議

/net330第4章MAC層60/186

?ComputerNetworksv4?cs.sjtu2004-5-23

適應(yīng)樹搜索協(xié)議

適應(yīng)樹搜索協(xié)議(AdaptiveTreeWalkProtocol)

。在某一次成功傳輸后的第一個競爭時隙，所有希望

發(fā)送的站點都允許競爭，如果只有一個站點申請，

則獲得信道。否則在下一競爭時隙，只允許一半站

點參與競爭(遞歸)

即將所有站點構(gòu)成一棵完全二叉樹。對二叉樹作深

度優(yōu)先的搜索

/net330第4章MAC層61/186

?ComputerNetworksv4?cs.sjtu2004-5-23

8個站點的適應(yīng)樹搜索

?TnbmP264Fig.4-9包含8個站點的樹

/net330第4章MAC層62/186

((ComputerNetworksv4?cs.sjtu2004-5-23

8個站點的適應(yīng)樹搜索舉例

?如當(dāng)前有站點G、H請求獲得信道

＞在時隙0,因有兩個站點請求獲得信道，所以沖突

＞在時隙1,按深度優(yōu)先搜索節(jié)點2,但發(fā)現(xiàn)節(jié)點2所

屬的站點無信道請求

＞在時隙2,跳過節(jié)點3,搜索節(jié)點3下屬節(jié)點6,但發(fā)

現(xiàn)節(jié)點6所屬的站點也無信道請求

＞在時隙3,跳過節(jié)點7,搜索節(jié)點7下屬節(jié)點G,G獲

得信道

/net330第4章MAC層63/186

?ComputerNetworksv4?cs.sjtu2004-5-23

第4章介質(zhì)訪問子層

?信道分配問題

?多路訪問協(xié)議CSMA

?以太網(wǎng)A

?數(shù)據(jù)鏈路層交換

/net330第4章MAC層64/186

?ComputerNetworksv4?cs.sjtu2004-5-23

以太網(wǎng)

?以太網(wǎng)的電纜

?以太網(wǎng)MAC子層協(xié)議

?沖突后的避讓算法

?以太網(wǎng)的性能

?交換式以太網(wǎng)

?:?快速以太網(wǎng)

?千兆以太網(wǎng)

?IEEE802.2LLC

/net330第4章MAC層65/186

?ComputerNetworksv4?cs.sjtu2004-5-23