Chapter12MultipleAccessCopyright?TheMcGraw-HillCompanies,Inc.Permissionrequiredforreproductionordisplay.1Figure12.1Datalinklayerdividedintotwofunctionality-orientedsublayers2Figure12.2Taxonomyofmultiple-accessprotocolsdiscussedinthischapter312-1RANDOMACCESSInrandomaccessorcontentionmethods,nostationissuperiortoanotherstationandnoneisassignedthecontroloveranother.Nostationpermits,ordoesnotpermit,anotherstationtosend.Ateachinstance,astationthathasdatatosendusesaproceduredefinedbytheprotocoltomakeadecisiononwhetherornottosend.ALOHA

CarrierSenseMultipleAccessCarrierSenseMultipleAccesswithCollisionDetectionCarrierSenseMultipleAccesswithCollisionAvoidanceTopicsdiscussedinthissection:4Figure12.3FramesinapureALOHAnetwork5Figure12.4ProcedureforpureALOHAprotocol6ThestationsonawirelessALOHAnetworkareamaximumof600kmapart.Ifweassumethatsignalspropagateat3×108m/s,wefind

Tp=(600×105)/(3×108)=2ms.

NowwecanfindthevalueofTBfordifferentvaluesof

K.a.ForK=1,therangeis{0,1}.Thestationneedsto|

generatearandomnumberwithavalueof0or1.This

meansthatTBiseither0ms(0×2)or2ms(1×2),

basedontheoutcomeoftherandomvariable.Example12.17b.ForK=2,therangeis{0,1,2,3}.ThismeansthatTB

canbe0,2,4,or6ms,basedontheoutcomeofthe

randomvariable.c.ForK=3,therangeis{0,1,2,3,4,5,6,7}.This

meansthatTBcanbe0,2,4,...,14ms,basedonthe

outcomeoftherandomvariable.d.WeneedtomentionthatifK>10,itisnormallysetto

10.Example12.1(continued)8Figure12.5VulnerabletimeforpureALOHAprotocol9ApureALOHAnetworktransmits200-bitframesonasharedchannelof200kbps.Whatistherequirementtomakethisframecollision-free?Example12.2SolutionAverageframetransmissiontimeTfris200bits/200kbpsor1ms.Thevulnerabletimeis2×1ms=2ms.Thismeansnostationshouldsendlaterthan1msbeforethisstationstartstransmissionandnostationshouldstartsendingduringtheone1-msperiodthatthisstationissending.10ThethroughputforpureALOHAis

S=G×e?2G.ThemaximumthroughputSmax=0.184whenG=(1/2).Note11ApureALOHAnetworktransmits200-bitframesonasharedchannelof200kbps.Whatisthethroughputifthesystem(allstationstogether)producesa.1000framespersecondb.500framespersecondc.250framespersecond.Example12.3SolutionTheframetransmissiontimeis200/200kbpsor1ms.a.Ifthesystemcreates1000framespersecond,thisis1

framepermillisecond.Theloadis1.Inthiscase

S=G×e?2GorS=0.135(13.5percent).Thismeans

thatthethroughputis1000×0.135=135frames.Only

135framesoutof1000willprobablysurvive.12Example12.3(continued)b.Ifthesystemcreates500framespersecond,thisis

(1/2)framepermillisecond.Theloadis(1/2).Inthis

caseS=G×e?2GorS=0.184(18.4percent).This

meansthatthethroughputis500×0.184=92andthat

only92framesoutof500willprobablysurvive.Note

thatthisisthemaximumthroughputcase,

percentagewise.c.Ifthesystemcreates250framespersecond,thisis(1/4)

framepermillisecond.Theloadis(1/4).Inthiscase

S=G×e?2GorS=0.152(15.2percent).Thismeans

thatthethroughputis250×0.152=38.Only38

framesoutof250willprobablysurvive.13Figure12.6FramesinaslottedALOHAnetwork14ThethroughputforslottedALOHAis

S=G×e?G.Themaximumthroughput

Smax=0.368whenG=1.Note15Figure12.7VulnerabletimeforslottedALOHAprotocol16AslottedALOHAnetworktransmits200-bitframesonasharedchannelof200kbps.Whatisthethroughputifthesystem(allstationstogether)producesa.1000framespersecondb.500framespersecondc.250framespersecond.Example12.4SolutionTheframetransmissiontimeis200/200kbpsor1ms.a.Ifthesystemcreates1000framespersecond,thisis1

framepermillisecond.Theloadis1.Inthiscase

S=G×e?GorS=0.368(36.8percent).Thismeans

thatthethroughputis1000×0.0368=368frames.

Only386framesoutof1000willprobablysurvive.17Example12.4(continued)b.Ifthesystemcreates500framespersecond,thisis

(1/2)framepermillisecond.Theloadis(1/2).Inthis

caseS=G×e?GorS=0.303(30.3percent).This

meansthatthethroughputis500×0.0303=151.

Only151framesoutof500willprobablysurvive.c.Ifthesystemcreates250framespersecond,thisis(1/4)

framepermillisecond.Theloadis(1/4).Inthiscase

S=G×e?GorS=0.195(19.5percent).Thismeans

thatthethroughputis250×0.195=49.Only49

framesoutof250willprobablysurvive.18Figure12.8Space/timemodelofthecollisioninCSMA19Figure12.9VulnerabletimeinCSMA20Figure12.10Behaviorofthreepersistencemethods21Figure12.11Flowdiagramforthreepersistencemethods22Figure12.12CollisionofthefirstbitinCSMA/CD23Figure12.13CollisionandabortioninCSMA/CD24AnetworkusingCSMA/CDhasabandwidthof10Mbps.Ifthemaximumpropagationtime(includingthedelaysinthedevicesandignoringthetimeneededtosendajammingsignal,asweseelater)is25.6μs,whatistheminimumsizeoftheframe?Example12.5SolutionTheframetransmissiontimeisTfr=2×Tp=51.2μs.Thismeans,intheworstcase,astationneedstotransmitforaperiodof51.2μstodetectthecollision.Theminimumsizeoftheframeis10Mbps×51.2μs=512bitsor64bytes.ThisisactuallytheminimumsizeoftheframeforStandardEthernet.25Figure12.14FlowdiagramfortheCSMA/CD26Figure12.15Energylevelduringtransmission,idleness,orcollision27Figure12.16TiminginCSMA/CA28InCSMA/CA,theIFScanalsobeusedtodefinethepriorityofastationoraframe.Note29InCSMA/CA,ifthestationfindsthechannelbusy,itdoesnotrestartthetimerofthecontentionwindow;itstopsthetimerandrestartsitwhenthechannelbecomesidle.Note30Figure12.17FlowdiagramforCSMA/CA3112-2CONTROLLEDACCESSIncontrolledaccess,thestationsconsultoneanothertofindwhichstationhastherighttosend.Astationcannotsendunlessithasbeenauthorizedbyotherstations.Wediscussthreepopularcontrolled-accessmethods.Reservation

Polling

TokenPassingTopicsdiscussedinthissection:32Figure12.18Reservationaccessmethod33Figure12.19Selectandpollfunctionsinpollingaccessmethod34Figure12.20Logicalringandphysicaltopologyintoken-passingaccessmethod3512-3CHANNELIZATIONChannelizationisamultiple-accessmethodinwhichtheavailablebandwidthofalinkissharedintime,frequency,orthroughcode,betweendifferentstations.Inthissection,wediscussthreechannelizationprotocols.Frequency-DivisionMultipleAccess(FDMA)

Time-DivisionMultipleAccess(TDMA)Code-DivisionMultipleAccess(CDMA)Topicsdiscussedinthissection:36WeseetheapplicationofallthesemethodsinChapter16when

wediscusscellularphonesystems.Note37Figure12.21Frequency-divisionmultipleaccess(FDMA)38InFDMA,theavailablebandwidth

ofthecommonchannelisdividedintobandsthatareseparatedbyguardbands.Note39Figure12.22Time-divisionmultipleaccess(TDMA)40InTDMA,thebandwidthisjustonechannelthatistimesharedbetweendifferentstations.Note41InCDMA,onechannelcarriesalltransmissionssimultaneously.Note42Figure12.23Simpleideaofcommunicationwithcode43Figure12.24Chipsequences44Figure12.25DatarepresentationinCDMA45Figure12.26SharingchannelinCDMA46Figure12.27DigitalsignalcreatedbyfourstationsinCDMA47Figure12.28DecodingofthecompositesignalforoneinCDMA48Figure12.29GeneralruleandexamplesofcreatingWalshtables49ThenumberofsequencesinaWalshtableneedstobeN=2m.Note50Findthechipsforanetworkwitha.Twostationsb.FourstationsExample12.6SolutionWecanusetherowsofW2andW4inFigure12.29:a.Foratwo-stationnetwork,wehave

[+1+1]and[+1?1].b