Chapter4

TheMediumAccessControlSublayer

（介質訪問子成）

1

14:45:05

4TheMediumAccessControl

Sublayer

?Thecategoriesofnetworks（網絡分類）

-Point-to-pointconnections（點到點連接）

-Broadcastchannels（廣播信道）

?Broadcastchannels（廣播信道網絡），也稱:

-MultiaccessChannel（多路訪問信道）

-or:RandomAccessChannel（隨機訪問信道）

?MediumAccessControl（介質訪問控制，MAC）

-Thebottompartofthedatalinklayer

2

14:45:05

4.1TheChannelAllocationProblem

?4.1.1StaticChannelAllocationinLANsandMANs

（局域網和城域網中信道的靜態分配）

?4.4.2DynamicChannelAllocationinLANsandMANs

（局域網和城域網中信道的動態分配）

3

14:45:05

4.1.1StaticChannelAllocationin

LANsandMANs

?Defect：ifthespectrumiscutupintoNregions,andfewer

thanNusersarecurrentlyinterestedincommunicating,a

largepieceofvaluablespectrumwillbewasted

缺陷：無通信量時信道白白浪費

?TheperformanceofstaticFDMispoor

?Themeantimedelay：TFDM=NT

-N--numberofSub-ChannelafterFDM

-T--originalmeandelayofframebeforeFDM

?ThesameargumentsthatapplytoFDMalsoapplytoTDM

4

14:45:05

4.1.2DynamicChannelAllocationin

LANsandMANS

Fivekeyassumptions（5個關鍵假設）：

1.Stationmodel（站模型）

-Nindependentstations>theframebegenerated>waitingfortransmittaL

untiltheframehasbeensuccessfullytransmitted

2.Singlechannelmodel（單通道假設）

-Asinglechannelisavailableforallcommunication

3.Collisionassumption（沖突假設）

-Acollidedframemustbetransmittedagainlater

4a.Continuoustime（連續時間）

-Frametransmissioncanbeginatanyinstant.

4b.Slottedtime（時隙）

-Frametransmissionsalwaysbeginatthestartofaslot.Aslotmaycontain

0,1,ormoreframes

5a.Carriersense（載波偵聽）

-Stationscantellifthechannelisinusebeforetryingtouseit

5b.Nocarriersense（非載波偵聽）

-Onlylatercantheydeterminewhetherornotthetransmissionwas

successful5

14:45:05

?局域網和城域網中信道的動態分配

-5個關鍵假設：

1.站模型(stationmodel)

-N各站、產生待發幀、等待發送、直至成功發送

2.單通道假設(singlechannelmodel)

-所有通信都通過單個信道進行

3.沖突假設(collisionassumption)

-沖突、檢測到后等待重發

4a.連續時間(continuoustime)

-幀可在任何時候發送

4b.時隙(slottedtime)

-時間片、幀總在時隙開始時發送、一時隙內可發送0、1或

多幀

5a.載波偵聽(carriersense)

-使用前偵聽信道是否忙

5b.非載波偵聽(nocarriersense)

-使用前不檢測信道，事后才能確定傳送是否成功

14:45:05

4.2MULTIPLEACCESSPROTOCOLS

?4.2.1ALOHA(AdditiveLinkOn-LineHawaiisystem)

?4.2.2CarrierSenseMultipleAccessProtocols

?4.2.3Collision-FreeProtocols

?4.2.4Limited-ContentionProtocols

?4.2.5WavelengthDivisionMultipleAccessProtocols

?4.2.6WirelessLANProtocols

7

14:45:05

421ALOHA

?ALOHA(AdditiveLinkOn-LineHawaiisystem)

-PureALOHA

-SlottedALOHA

?PureALOHA-

-Thebasicidealetuserstransmitwhenevertheyhavedatato

besent.Assumed:Fixedframelengtho

基本思想：只要有待發數據，就讓他們發

-Aftercollision,waitingforrandomtime,thenretransmit

-Vulnerableperiodfortheshadedframe-

一Thethroughputofsystem:S=G*e-2G

?G-Load,totalgeneratedmeanframenumbers(oldandnew)per

frametime,每柳時內傳送的幀數

?S---successfullytransmittedframesperframetime,S<1

-ThemaximumthroughputoccursatG=0.5,withS=l/(2e),which

isabout0.184.

-Inotherwords,thebestwecanhopeforisachannelutilization

of188

i4:45：05Percent.

A[ZZ1[ZZ]

B[ZZ1

c[ZZ1[ZZl[ZZ]

D[^^1[ZZ][=1[=1

E[ZZ][ZZ]IZZ][ZZ1

Time-----------?

Fig4-1,InpureALOHA,framesaretransmittedatcompletelyarbitrary

times

Fig.4-2.Vulnerableperiodfortheshadedframe

14:45:05

4.2.1ALOHA

?SlottedALOHA

-hebasicidea：dividetimeupintodiscreteintervals,each

intervalcorrespondingtooneframe

基本思想：把時間分為離散的時間片(slot),每段對應一幀

一Theapproachrequirestheuserstoagreeofslot

boundaries.

-Dangerofcollisionreduceahalf

-Thethroughput:S=GeG

-SlottedALOHAatG=l,withathroughputs=l/eorabout

0.368,twicethatofpureALOHA.

一ThebestwecanhopeforusingslottedALOHAis37

percentoftheslots.

-Therelationbetweentheofferedtrafficandthe

i4：45：05throughputisshowninFigurd斗-3]

421ALOHA

①(

ul

一

一

l

n

d

J6Z

n

o

￡」

)

s

Fig.4-3.ThroughputversusofferedtrafficforALOHAsystems

11

14:45:05

4.2.2CarrierSenseMultipleAccessProtocols

(載波偵聽多路竊問協議)

?BasicIdea：detectwhatotherstationsaredoing,adapttheirbehavior

accordingly,achieveamuchbetterutilization

基本思想：檢測其它站點，調整自己的動作，大大提高利用率

?CarrierSenseProtocols:protocolsinwhichstationslistenforacarrier(i.e.,a

transmission)andactaccordingly

?PersistentandNonpersistentCSMA

-1-persistentCSMA

?listentothechannel,ifthechannelisbusy,thestationwaitsuntilit

becomesidle,thentransmitstheframe.Ifidle,thestationtransmitit

immediately.

?Ifacollisionoccurs,thestationwaitsarandomamountoftimeand

startsalloveragain.

-NonpersistentCSMA

?listening,ifthechannelisbusy,waitsarandomamountoftimeand

startslistening.Ifidle,thestationtransmititimmediately.

?BetterChannelutilizationthan1-persistentCSMA,butlongerdelays.

12

14:45:05

-p-persistentCSMA

?Appliestoslottedchannels

?listening,ifitisidleJttransmitswithaprobabilityp,and

deferswithaprobability1-p.IfbusyzContinuelistening.

?-[seefig4-4]

L00.01-persistentCSMA

o9NonpersistentCSMA

aE)s8

一0.1-persistentCSMA

二7

￡s

O6

E。

d0.5-persistent

」5『CSMA

6

<dD4

JsSlotted

n

ds3ALOHA

-C

n6s21-persistent

o"CSMA

.J1

￡/ALOHA

)Q

w

o

23456789

G(attemptsperpackettime'

Fig.4-4.Comparisonofthechannelutilizationversusload

forvariousrandomaccessprotocols

13

14:45:05

4.2.2CarrierSenseMultipleAccess

Protocols

?CSMAwithCollisionDetection(帶沖突檢測的CSMA)

一Improvement：aborttheirtransmissionsassoonastheydetect

acollision.

-CarrierSenseMultipleAccesswithCollisionDetection(CSMA/CD)

-Theconceptualmodel-

一Threestates：contentionztransmissionzoridle

-CSMA/CDisaimportantprotocol.Oneversionofit：IEEE

802.3(Ethernet),whichisaninternationalstandard.

14

14:45:05

（補充）

沖

突強化沖突

檢

測

放棄幀的發送

出口

14:45:05圖4/0CSMA/CD的流程圖

Contention

,oslots

TransmissionContentionIdle

periodperiodperiod

Time------?

Fig.4-5CSMA/CDcanbeinoneofthreestates:contention,

transmission,oridle.

16

14:45:05

4.2.3無沖突的協議

-位圖協議

-基本位圖法-

?競爭周期由N個時隙組成;

?站點j可以通過在時隙j內填入IBit,以聲明有一幀要發送

?然后按照聲明的順序發送數據

-特點：預定協議-發送之前，先聲明

-性能:

?效率=d/(N+d),N-每幀的開銷，d-數據量/幀

?高負荷下，效率=d/(d+l),(N=l)

17

14:45:05

4.2.3無沖突的協議

Bittime

-二進制倒計數法（*）

Stations0010Station1001

and0100seethisseesthis1

1andgiveupandgivesup

Fig.4-7.Thebinarycountdownprotocol.Adashindicatessilence.

18

14:45:05

4.2.4有限競爭協議

-競爭法（如CSMA）和無沖突法的結合

?低負荷時，采用競爭法，使時延較短

?重負荷時，采用無沖突法，使信道利用率較高

-對稱競爭信道獲取概率-

0.0---------------------------1---------------------------1---------------------------1---------------------------1--------------------------1——

0510152025

Numberofreadystations

Fig.4-8.Acquisitionprobabilityforasymmetriccontentionchannel.

19

14:45:05

4.2.4有限競爭協議

-適應樹搜索協議-

?二叉樹

?第一個競爭時隙(0)內，所有站點多可以嘗試獲取信道

?如有沖突，1時隙內，只允許節點2以下的站點參與競爭

20

14:45:05

4.2.5波分多路訪問協議(WDMA)

mtimeslots

forcontrol

Station*'

A'scontrolchannelis

—-煙忖IWI四豆T岡TT**-----usedbyotherstations

A------_一_

—?I~~i-ii""irsitocontactA

V

n+1timeslotsfordata

t---函xjIMxH|函x|IW沛-B'scontrolchannel

￡____UsedbyBto

--Bsdatachannel—transmj;data

C'scontrolchannel

c

-----?C'sdatachannel

-----D'scontrolchannel

D

-----?D'sdatachannel

Time

Fig.4-10.Wavelengthdivisionmultipleaccess.

21

14:45:05

4.2.5波分多路訪問協議(WDMA)

-信道分成子信道(TDM,FDM),動態地分配信道

?例如，fig4-10,光纖LAN

?每個站點分成2個子信道：窄-控制，寬-數據

-每個站點有2個發送端和2個接收端

?波長固定的接收端,用于偵聽本站點控制信道

?波長可調的發送端,用于向其他站點控制信道發送幀

?波長固定的發送端,用于輸出數據幀

?波長可調的接收端,用于選擇要偵聽的數據發送端

-DWDM(DenseWavelengthDivisionMultiplexing)

22

14:45:05

426WirelessLANProtocols

?Unlikecellulartelephonesystems,eachcellhasonlyone

channeLcoveringtheentireavailablebandwidth,usuallyits

bandwidthisll-54Mb/s

?Hiddenstationproblem-

-A->B,CwillnothearA,thusfalselyconcludethatCcan

transmit,collisionoccur.

?Exposedstationproblem-[seefig4-ll(b)]

-B->A,Cislistening,falselyconcludethatitmaynotsend

toD

Fig.4-11.AwirelessLAN.(a)Atransmitting.(b)Btransmitting.

23

14:45:05

WirelessLANProtocols(2)

?MultipleAccesswithCollisionAvoidance(MACA)-

-IEEE802.11

-Thebasicidea：thesenderstimulatethereceiver(RTS),

makeitsendaframe(CTS),allstationsnearbycandetect

thistransmission,avoidcollision.

Fig.4-12.TheMACAprotocol.(a)AsendinganRTStoB

(b)BrespondingwithatoA

14:45:05

?Conclusion(CSMA/CARule)：

-IfstationXreceivedRTS,butdidnotreceiveCTS,thenX

cantransmititsdataandwillnotinterferewithother

stations.。

一IfstationXhasnotreceivedRTS,butreceivedCTS,thenX

maynottransmititsdata.

-IfstationXhasreceivedbothRTSandCTS,thenXmay

nottransmititsdata.

?AlthoughtheuseofRTSandCTSwilldecreasetheefficiencyof

network,buttheinfluenceislittlebecausetheyareveryshort,

e.g,framelengthofRTSis30bytewhilethemaximallengthof

dataframeis2346bytes.

?MACAcannotpreventcollisionfromhappening.e.g,AandC

transmitRTStoBinthesametime,theirRTSframewillcollision.

?MACAW:tuneMACAtoimproveitsperformance.

-forireless

-introducinganACKaftereachsuccessfuldataframe,

avoidlosingtheframe

25

14:45:05

WLAN標準

?IEEE802.112.4GHz,1997

-1/2M

?IEEE802.lib2.4GHz,1999

-11M

?IEEE802.11a5GHz,1999

-54M

?IEEE802.11g2.4GHz,July2003

-11M/54M

?IEEE802.Hi(WLAN的802.lx)新一代WLAN安全標準

?IEEE802.lln橫跨MAC與PHY兩層的標準，預計:108Mbps,甚至320Mbps

26

14:45:05

4.3Ethernet

?EthernetCabling

?ManchesterEncoding

?TheEthernetMACSublayerProtocol

?TheBinaryExponentialBackoffAlgorithm

?EthernetPerformance

?SwitchedEthernet

?FastEthernet

?GigabitEthernet

?IEEE802.2:LogicalLinkControl

?RetrospectiveonEthernet

27

14:45:05

4.3.1EthernetCabling

?Fourtypesofcablingarecommonlyused:(Figure4-

13,14,15)

NameCableMax.seg.Nodes/seg.Advantages

10Base5Thickcoax500m100Originalcable;nowobsolete

10Base2Thincoax185m30Nohubneeded

10Base-TTwistedpair100m1024Cheapestsystem

10Base-FFiberoptics2000m1024Bestbetweenbuildings

Figure4-13.ThemostcommonkindsofEthernetcabling.

28

14:45:05

Controller

Te

Controller^d

Transeeiverowiosopaoiroo

+controlleroooooo

oooooo

Core

Hub

(a)(b)(c)

Figure4-14.ThreekindsofEthernetcabling.10Base5,10Base2,lOBase-T.

ABcD

C

Tap

DRepeater

Backbone

⑻(b)(d)

Figure4-15.Cabletopologies.)Tree,Segmented.

29

14:45:05

43.2ManchesterEncoding

?Problem:bit0-0volts,bit1-5volts,thenambiguitiesarise:

anidlesender(0volts)ora0bit(0volts).

?Method:using+1voltsfora1and-1voltsfora0,butthereis

stillaproblem:differentclockspeeds

?keyissue:tounambiguouslydeterminethestart,end,ormiddle

ofeachbitwithoutreferencetoanexternalclock.Twosuch

approaches:ManchesterencodinganddifferentialManchester

encoding.

?Manchesterencoding:Eachbitperiodisdividedintotwoequal

intervals(l一highduringthefirstintervalandlowinthesecond

one.0—justthereverse).

一Advantage:easyforthereceivertosynchronizewiththesender

一Disadvantage:twiceasmuchbandwidthasstraightbinary

encoding30

14:45:05

4.3.2ManchesterEncoding

?DifferentialManchesterencoding:1一absenceofat「ansition（EK變）at

thestartoftheinterval,0一presenceofatransitionatthestartofthe

interval

-Thedifferentialschemerequiresmorecomplexequipmentbutoffers

betternoiseimmunity

?AllEthernetsystemsuseManchesterencodingduetoitssimplicity

14:45:05encoding.

4.3.3TheEthernetMACSublayerProtocol

?OriginalDIXframestructure->eefig4T7(a)]

-Preambleocontainingbitpattern10101010

-high-orderbitofdestinatiSs:O-ordinary,1-

group

-minimumframelength:64bytes

?todistinguishvalidframesfromgarbage

?collisiondetection-[seefig4-18]

一CRCcheck

?twochangesIEEEmade:[seefig4-17(b)]

一Preambleof7bytes,lastbyteforaStartof

Frame(SOF)delimiter(7+1=8)

一tochangeTypefieldintoLengthfield

32

14:45:05

Bytes86620-15000-464

DestinationSourceCheck-

(a)PreambleTypeDataPad

addressaddresssum

ss

SDestinationSourceCheck-

(b)Preamble0LengthDataPad

Faddressaddresssum

Figure4-17.Frameformats.DIXEthernet,IEEE802.3.

PacketstartsPacketalmost

ABAB

attime0atBatT-G

(a)(b)

Noiseburstgets

backtoAat2T

AB

(c)Collisionat(d)

timeT

lisiondetectioncant1longas2r.

33

14:45:05

CSMA/CD協議

?最初的以太網是將許多計算機都連接到一根總線上。

當初認為這樣的連接方法既簡單又可靠，因為總線上

沒有有源器件。

匹配電阻（用來吸收總線上傳播的信號）匹配電阻

只有D接受

B發送的數據圜

D

不接受B向D不接受接受不接受

發送數據

34

14:45:05

兩個標準

?DIXEthernetV2是世界上第一個局域網產品

（以太網）的規約。

?IEEE的802.3標準。

?DIXEthernetV2標準與IEEE的802.3標準

只有很小的差別，因此可以將802.3局域網簡

稱為“以太網”。

?嚴格說來，“以太網”應當是指符合DIX

EthernetV2標準的局域網

35

14:45:05

為了通信的簡便

以太網采取了兩種重要的措施

?采用較為靈活的無連接的工作方式，即不必

先建立連接就可以直接發送數據。

?以太網對發送的數據幀不進行編號，也不要

求對方發回確認。

-這樣做的理由是局域網信道的質量很好,

信道質量產生差錯的概率是很小的。

36

14:45:05

以太網提供的服務

?以太網提供的服務是不可靠的交付，即盡最

大努力的交付。

?當目的站收到有差錯的數據幀時就丟棄此幀,

其他什么也不做。差錯的糾正由高層來決定。

?如果高層發現丟失了一些數據而進行重傳，

但以太網并不知道這是一個重傳的幀，而是

當作一個新的數據幀來發送。

37

14:45:05

載波監聽多點接入/碰撞檢測

(CSMA/CD)

?CSMA/CD表示CarrierSenseMultipleAccess

withCollisionDetectiono

?“多點接入”表示許多計算機以多點接入的方式連接

在一根總線上。

“載波監聽”是指每一個站在發送數據之前先要檢測

一下總線上是否有其他計算機在發送數據，如果有,

則暫時不要發送數據，以免發生碰撞。

?總線上并沒有什么“載波”因此，“載波監聽”就

是用電子技術檢測總線上有沒有其他計算機發送的數

據信號。

38

14:45:05

碰撞檢測

?“碰撞檢測”就是計算機邊發送數據邊檢測信

道上的信號電壓大小。

?當幾個站同時在總線上發送數據時，總線上的

信號電壓擺動值將會增大（互相疊加）。

?當一個站檢測到的信號電壓擺動值超過一定的

門限值時，就認為總線上至少有兩個站同時在

發送數據，表明產生了碰撞。

?所謂“碰撞”就是發生了沖突。因此“碰撞檢

測”也稱為“沖突檢測”。

39

14:45:05

檢測到碰撞后

?在發生碰撞時，總線上傳輸的信號產生了嚴

重的失真，無法從中恢復出有用的信息來。

?每一個正在發送數據的站，一旦發現總線上

出現了碰撞，就要立即停止發送，免得繼續

浪費網絡資源，然后等待一段隨機時間后再

次發送。

40

14:45:05

電磁波在總線上的

有限傳播速率的影響

?當某個站監聽到總線是空閑時，也可能總線并

非真正是空閑的。

?A向B發出的信息，要經過一定的時間后才能

傳送到Bo

?B若在A發送的信息到達B之前發送自己的

幀（因為這時B的載波監聽檢測不到A所發送

的信息），則必然要在某個時間和A發送的幀

發生碰撞。

?碰撞的結果是兩個幀都變得無用。

41

14:45:05

1km

B

t=0

t=T

單程端到端

f=2T-8傳播時延記為丁

42

14:45:05

1km

B

t=T

單程端到端

=2T-5傳播時延記為丁

t=0

檢測到

AB

信道空閑ET

發送數據一f二T—3

ABB檢測到信道空閑

發送數據

――3/2

發生碰撞

t=T

B檢測到發生碰撞

停止發送

14:45:05

重要特性

?使用CSMA/CD協議的以太網不能進行全雙工

通信而只能進行雙向交替通信（半雙工通信）。

?每個站在發送數據之后的一小段時間內，存在著

遭遇碰撞的可能性。

?這種發送的不確定性使整個以太網的平均通信量

遠小于以太網的最高數據率。

44

14:45:05

爭用期

?最先發送數據幀的站，在發送數據幀后至多經過

時間2T（兩倍的端到端往返時延）就可知道發

送的數據幀是否遭受了碰撞。

?以太網的端到端往返時延2工稱為爭用期，或碰

撞窗口。

?經過爭用期這段時間還沒有檢測到碰撞，才能肯

定這次發送不會發生碰撞。

45

14:45:05

二進制指數類型退避算法（truncated

binaryexponentialtype）

?發生碰撞的站在停止發送數據后，要推遲（退避）

一個隨機時間才能再發送數據。

-確定基本退避時間，一般是取為爭用期2TO

-定義重傳次數A,A<10,即

A=Min［重傳次數，10］

-從整數集合［0,1，…，（24-1）］中隨機地取出一個

數，記為ro重傳所需的時延就是r倍的基本退

避時間。

-當重傳達16次仍不能成功時即丟棄該幀，并向高

層報告

46

14:45:05

爭用期的長度

?以太網取51.2|is為爭用期的長度。

?對于10Mb/s以太網，在爭用期內可發送512

bit,即64字節。

?以太網在發送數據時，若前64字節沒有發生沖

突，則后續的數據就不會發生沖突。

47

14:45:05

最短有效幀長

?如果發生沖突，就一定是在發送的前64字節之內。

?由于一檢測到沖突就立即中止發送，這時已經發送出去

的數據一定小于64字節。

?以太網規定了最短有效幀長為64字節，凡長度小于

64字節的幀都是由于沖突而異常中止的無效幀。

48

14:45:05

強化碰撞

?當發送數據的站一旦發現發生了碰撞時，除了立

即停止發送數據外，還要再繼續發送若干比特的

人另干擾信石(jammingsignal),以便讓所有

用戶都知道現在已經發生了碰撞。

49

14:45:05

人為干擾信號,

A發送數據

B

_

-A

-

-

-

-

7Y5

H信

~道

^

"H占

用

-時

L間

B也能夠檢測到沖突，并立即停止發送數據幀，接

著就發送干擾信號。這里為了簡單起見，只畫出A

發送干擾信號的情況。

50

14:45:05

4.3.4TheBinaryExponential

BackoffAlgorithm

?delay=k*2x

?slottime(round-tripdelay):2T=51.2ILLS

?aftericollisions,arandomnumberkbetween0

and2L1ischosen.

?After10collisionshavebeenreached,the

randomizationintervalisfrozenatamaximumof

1023slots.After16collisions,thecontroller

throwsinthetowelandreportsfailurebacktothe

computer.

51

14:45:05

4.3以太網的MAC層

4.3.1MAC層的硬件地址

?在局域網中，硬件地址又稱為物理地址，或

MAC地址。

?802標準所說的“地址”嚴格地講應當是每一個

站的“名字”或標識符。

?但鑒于大家都早已習慣了將這種48bit的“名

字”稱為“地址”，所以本書也采用這種習慣用

法，盡管這種說法并不太嚴格。

52

14:45:05

第1字節第6字節

十六進制表示的EUI-48地址:AC-DE-48-00-00-80

二進制表示的EUL48地址：,

機構惟一標志符OUI擴展標志符不

K字節順序//第1第2第3第4第5第6\

■高位在前

最高位最最高位最低位

日生塵、皂

取元友達最后發送

字節順序第1第2第3第4第5第6

低位在前001101010111101100010010000000000000000000000001

低位最局位最低位最高位

七

取m無發送最后發送

53

14:45:05

網卡上的硬件地址

路由器由于同時連接到兩個網絡上,

因此它有兩塊網卡和兩個硬件地址。

54

14:45:05

網卡檢查MAC地址

?網卡從網絡上每收到一個MAC幀就首先用硬件

檢查MAC幀中的MAC地址.

-如果是發往本站的幀則收下，然后再進行其他的

處理。

-否則就將此幀丟棄，不再進行其他的處理。

?“發往本站的幀”包括以下三種幀：

-單播(unicast)幀(一對一)

-廣播(broadcast)幀(一對全體)

-多播(multicast)幀(一對多)

55

14:45:05

4.3.2兩種不同的MAC幀格

式

?常用的以太網MAC幀格式有兩種標準：

一DIXEthernetV2標準

-IEEE的