MEDIUM-ACCESS CONTROL SUB LAYER.ppt

Many algorithms for allocating a multiple access channel are known

1. MEDIUM-ACCESS CONTROL
SUB LAYER

2. •Networkscanbedividedintotwocategories:
•Thoseusingpoint-to-pointconnectionsandthoseusing
broadcastchannels
•Inaface-to-facemeeting,chaosisavoidedbyexternalmeans,
forexample,atameeting,peopleraisetheirhandstorequest
permissiontospeak
•Whenonlyasinglechannelisavailable,determiningwho
shouldgonextismuchharder
•Manyprotocolsforsolvingtheproblemareknownandform
thecontentsofthischapter.
•Intheliterature,broadcastchannelsaresometimesreferred
toasmultiaccesschannelsorrandomaccesschannels

3. •Theprotocolsusedtodeterminewhogoesnextonamultiaccesschannel
belongtoasublayerofthedatalinklayercalledtheMAC(MediumAccess
Control)sublayer.
•Manyalgorithmsforallocatingamultipleaccesschannelareknown
•ALOHA
–PureALOHA
–SlottedALOHA
•CarrierSenseMultipleAccessProtocols
–PersistentandNonpersistentCSMA
–CSMAwithCollisionDetection
–Collision-FreeProtocols
•ABit-MapProtocol
•BinaryCountdown
•Limited-ContentionProtocols
•TheAdaptiveTreeWalkProtocol
•WavelengthDivisionMultipleAccessProtocols
•WirelessLANProtocols
•MACAandMACAW
–

4. ALOHA
•Inthe1970s,NormanAbramsonandhiscolleagues-
UniversityofHawaii-newandelegantmethodtosolvethe
channelallocationproblem
•AlthoughAbramson'swork,calledtheALOHAsystem,ground-
basedradiobroadcasting,thebasicideaisapplicabletoany
systeminwhichuncoordinatedusersarecompetingforthe
useofasinglesharedchannel.
•ALOHA-pureandslotted-Theydifferwithrespecttowhether
timeisdividedintodiscreteslotsintowhichallframesmust
fit
•PureALOHA-PureALOHAdoesnotrequireglobaltime
synchronization
•SlottedALOHA-slottedALOHAdoes

5. •ALOHAsystemissimple:transmitdatatobesent-collisions-
collidingframeswillbedamaged
•WithaLAN,thefeedbackisimmediate
•Systemsinwhichmultipleusersshareacommonchannelina
waythatcanleadtoconflictsarewidelyknownascontention
systems

8. Slotted ALOHA
•In1972,Robertspublishedamethodfor
doublingthecapacityofanALOHAsystem
•IncontrasttoAbramson'spureALOHA,a
computerisnotpermittedtosendwhenever
acarriagereturnistyped
•Instead,itisrequiredtowaitforthebeginning
ofthenextslot

9. Carrier Sense Multiple Access
Protocols
•WithslottedALOHAthebestchannelutilizationthatcanbe
achievedis1/e
•(estandsforcollisions)
•Thesenetworkscanachieveamuchbetterutilizationthan1/e
•Inthissectionwewilldiscusssomeprotocolsforimproving
performance
•Protocolsinwhichstationslistenforacarrier(i.e.,a
transmission)andactaccordinglyarecalledcarriersense
protocols

10. Persistent and Nonpersistent CSMA
•Thefirstcarriersenseprotocol-1-persistentCSMA
•Whenastationhasdatatosend,listenstothechannel,if
anyoneelseistransmittingatthatmoment
•Ifthechannelisbusy,thestationwaitsuntilitbecomesidle
•Whenthestationdetectsanidlechannel,ittransmitsaframe
•Ifacollisionoccurs,thestationwaitsarandomamountof
timeandstartsalloveragain
•Theprotocoliscalled1-persistentbecausethestation
transmitswithaprobabilityof1whenitfindsthechannelidle
•AsecondcarriersenseprotocolisnonpersistentCSMA

11. Nonpersistent CSMA
•Beforesending,astationsensesthechannel
•Ifnooneelseissending,thestationbeginsdoingsoitself
•However,ifthechannelisalreadyinuse,thestationdoesnot
continuallysenseitforthepurposeofseizingitimmediately
upondetectingtheendoftheprevioustransmission
•Instead,itwaitsarandomperiodoftimeandthenrepeatsthe
algorithm
•Consequently,thisalgorithmleadstobetterchannel
utilizationbutlongerdelaysthan1-persistentCSMA
•Thelastprotocolisp-persistent-Whenastationbecomes
readytosend,itsensesthechannel
•Ifitisidle,ittransmitswithaprobabilityp
•If that slot is also idle, it either transmits or defers again, with
probabilities p and q. This process is repeated until either the
frame has been transmitted

12. Comparison of the channel utilization versus load for
various random access protocols

13. CSMA with Collision Detection
•PersistentandnonpersistentCSMAprotocolsare
clearlyanimprovementoverALOHA
•Quicklyterminatingdamagedframessavestimeand
bandwidth.Thisprotocol,knownasCSMA/CD(CSMA
withCollisionDetection)
•CSMA/CDcanbeinoneofthreestates:contention,
transmission,oridle

14. Collision-Free Protocols
•AlthoughcollisionsdonotoccurwithCSMA/CDonceastationhas
unambiguouslycapturedthechannel,theycanstilloccurduringthe
contentionperiod
•CSMA/CDisnotuniversallyapplicable
•Inthissection,wewillexaminesomeprotocolsthatresolvethe
contentionforthechannelwithoutanycollisionsatall,notevenduring
thecontentionperiod

15. A Bit-Map Protocol
•Inourfirstcollision-freeprotocol,thebasicbit-map
method,eachcontentionperiodconsistsofexactlyN
slots
•Ifstation0hasaframetosend,ittransmitsa1bit
duringthezerothslot
•Nootherstationisallowedtotransmitduringthis
slot

16. •Nslotshavepassedby,eachstationhascompleteknowledgeofwhich
stationswishtotransmit
•Protocolslikethisinwhichthedesiretotransmitisbroadcastbeforethe
actualtransmissionarecalledreservationprotocols

17. Binary Countdown
•A problem with the basic bit-map protocol is that the
overhead is 1 bit per station, so it does not scale well
to networks with thousands of stations
•All addresses are assumed to be the same length
•The bits in each address position from different
stations are BOOLEAN ORed together
•We will call this protocol binary countdown

18. •Example:stationsC,H,D,A,G,B,E,Fhavepriorities7,6,5,4,
3,2,1,and0,respectively,thenasuccessfultransmissionbyD
putsitattheendofthelist,givingapriorityorderofC,H,A,
G,B,E,F,D
•Thus,Cremainsvirtualstation7,butAmovesupfrom4to5
andDdropsfrom5to0
•StationDwillnowonlybeabletoacquirethechannelifno
otherstationwantsit
•Binarycountdownisanexampleofasimple,elegant,and
efficientprotocolthatiswaitingtoberediscovered

19. Limited-Contention Protocols
•Twobasicstrategiesforchannelacquisitioninacable
network:
•contention,asinCSMA,andcollision-freemethods
•Eachstrategycanberatedastohowwellitdoeswithrespect
tothetwoimportantperformancemeasures
•delayatlowloadandchannelefficiencyathighload
•Itwouldbeniceifwecouldcombinethebestpropertiesofthe
contentionandcollision-freeprotocols
•Arrivingatanewprotocolthatusedcontentionatlowloadto
providelowdelay,butusedacollision-freetechniqueathigh
loadtoprovidegoodchannelefficiency
•Suchprotocols,whichwewillcalllimited-contentionprotocols

20. The Adaptive Tree Walk Protocol
•Simplewayofperformingthenecessaryassignmentistousethe
algorithmdevisedbytheU.S.Armyfortestingsoldiersforsyphilisduring
WorldWarII(Dorfman,1943)
•thestationsastheleavesofabinarytree,asillustratedinFig
•Inthefirstcontentionslotfollowingasuccessfulframetransmission,slot
0,allstationsarepermittedtotrytoacquirethechannel
•Ifoneofthemdoesso,fine.Ifthereisacollision,thenduringslot1only
thosestationsfallingundernode2inthetreemaycompete
•Ifoneofthemacquiresthechannel,theslotfollowingtheframeis
reservedforthosestationsundernode3
•If,ontheotherhand,twoormorestationsundernode2wanttotransmit,
therewillbeacollisionduringslot1,inwhichcaseitisnode4'sturn
duringslot2

22. •Ifacollisionoccursduringslot0,theentire
treeissearched,depthfirst,tolocateallready
stations
•Eachbitslotisassociatedwithsomeparticular
nodeinthetree
•Ifacollisionoccurs,thesearchcontinues
recursivelywiththenode'sleftandright
children
•Ifabitslotisidleorifonlyonestation
transmitsinit,thesearchingofitsnodecan
stopbecauseallreadystationshavebeen
located

23. Wavelength Division Multiple
Access Protocols
•A different approach to channel allocation is
to divide the channel into subchannels using
FDM, TDM, or both, and dynamically allocate
them as needed
•Schemes like this are commonly used on fiber
optic LANs to permit different conversations
to use different wavelengths (i.e., frequencies)
at the same time.

24. •Toallowmultipletransmissionsatthesame
time,thespectrumisdividedintochannels
(wavelengthbands)
•Eachstationisassignedtwochannels
•Anarrowchannelisprovidedasacontrol
channeltosignalthestation,andawide
channelisprovidedsothestationcanoutput
dataframes.

25. Wavelength division multiple
access.

26. Wireless LAN Protocols
•Toachievetruemobility,notebookcomputersneedtouse
radio(orinfrared)signalsforcommunication
•Asystemofnotebookcomputersthatcommunicatebyradio
canberegardedasawirelessLAN
•TheseLANshavesomewhatdifferentpropertiesthan
conventionalLANsandrequirespecialMACsublayer
protocols.
•AcommonconfigurationforawirelessLANisanoffice
buildingwithbasestations(alsocalledaccesspoints)
strategicallyplacedaroundthebuilding
•Allthebasestationsarewiredtogetherusingcopperorfiber

27. •Forourpurposes,itdoesnotmatterwhicharebasestations
andwhicharenotebooks
•TheradiorangeissuchthatAandBarewithineachother's
rangeandcanpotentiallyinterferewithoneanother
•CcanalsopotentiallyinterferewithbothBandD,butnot
withA

28. •IfCdoesstarttransmitting,itwillinterfereatB,wipingout
theframefromA
•Theproblemofastationnotbeingabletodetectapotential
competitorforthemediumbecausethecompetitoristoofar
awayiscalledthehiddenstationproblem.

29. MACA and MACAW
•AnearlyprotocoldesignedforwirelessLANsis
MACA(MultipleAccesswithCollision
Avoidance)(Karn,1990)
•Thebasicideabehinditisforthesenderto
stimulatethereceiverintooutputtingashort
frame,sostationsnearbycandetectthis
transmissionandavoidtransmittingforthe
durationoftheupcoming(large)dataframe

31. •LetusnowconsiderhowAsendsaframetoB.Astartsby
sendinganRTS(RequestToSend)frametoB,asshowninFig.
4-12(a).
•Thisshortframe(30bytes)containsthelengthofthedata
framethatwilleventuallyfollow.
•ThenBreplieswithaCTS(CleartoSend)frame,asshownin
Fig.4-12(b).
•TheCTSframecontainsthedatalength(copiedfromtheRTS
frame).
•UponreceiptoftheCTSframe,Abeginstransmission.

32. •Bharghavanetal.(1994)finetunedMACAto
improveitsperformanceandrenamedtheir
newprotocolMACAW(MACAforWireless)
•Lostframeswerenotretransmitteduntilthe
transportlayernoticedtheirabsence,much
later
•Theysolvedthisproblembyintroducingan
ACKframeaftereachsuccessfuldataframe
•Thischangeimprovesthefairnessofthe
protocol

33. Ethernet