计算机网络英文版课件：5-4 随机接入MAC协议

随机接入MAC协议MACProtocols:ataxonomyThreebroadclasses:ChannelPartitioningdividechannelintosmaller“pieces”(timeslots,frequency,code)allocatepiecetonodeforexclusiveuseRandomAccesschannelnotdivided,allowcollisions“recover”fromcollisions“Takingturns”nodestaketurns,butnodeswithmoretosendcantakelongerturnsRandomAccessProtocolsWhennodehaspackettosendtransmitatfullchanneldatarateR.noaprioricoordinationamongnodestwoormoretransmittingnodes➜“collision”,randomaccessMACprotocolspecifies:howtodetectcollisionshowtorecoverfromcollisions(e.g.,viadelayedretransmissions)ExamplesofrandomaccessMACprotocols:slottedALOHAALOHACSMA,CSMA/CD,CSMA/CASlottedALOHAAssumptions:allframessamesizetimedividedintoequalsizeslots(timetotransmit1frame)nodesstarttotransmitonlyslotbeginningnodesaresynchronizedif2ormorenodestransmitinslot,allnodesdetectcollisionOperation:whennodeobtainsfreshframe,transmitsinnextslotifnocollision:nodecansendnewframeinnextslotifcollision:noderetransmitsframeineachsubsequentslotwithprob.puntilsuccessSlottedALOHAProssingleactivenodecancontinuouslytransmitatfullrateofchannelhighlydecentralized:onlyslotsinnodesneedtobeinsyncsimpleConscollisions,wastingslotsidleslotsnodesmaybeabletodetectcollisioninlessthantimetotransmitpacketclocksynchronizationSlottedAlohaefficiencysuppose:Nnodeswithmanyframestosend,eachtransmitsinslotwithprobabilitypprobthatgivennodehassuccessinaslot=p(1-p)N-1probthatanynodehasasuccess=Np(1-p)N-1maxefficiency:findp*thatmaximizes

Np(1-p)N-1formanynodes,takelimitofNp*(1-p*)N-1asNgoestoinfinity,gives:Maxefficiency=1/e=.37Efficiency:long-run

fractionofsuccessfulslots

(manynodes,allwithmanyframestosend)Atbest:

channelusedforusefultransmissions37%oftime!!Pure(unslotted)ALOHAunslottedAloha:simpler,nosynchronizationwhenframefirstarrivestransmitimmediatelycollisionprobabilityincreases:framesentatt0collideswithotherframessentin[t0-1,t0+1]PureAlohaefficiencyP(successbygivennode)=P(nodetransmits).P(noothernodetransmitsin[p0-1,p0].P(noothernodetransmitsin[p0-1,p0]=p.(1-p)N-1.(1-p)N-1=p.(1-p)2(N-1)

…choosingoptimumpandthenlettingn->infty...

=1/(2e)=.18

evenworsethanslottedAloha!PureALOHAThroughputversusofferedtrafficforALOHAsystems.CSMA(CarrierSenseMultipleAccess)CSMA:listenbeforetransmit:Ifchannelsensedidle:transmitentireframeIfchannelsensedbusy,defertransmissionhumananalogy:don’tinterruptothers!CSMAcollisionscollisionscanstilloccur:propagationdelaymeanstwonodesmaynotheareachother’stransmissioncollision:entirepackettransmissiontimewastednote:roleofdistance&propagationdelayindeterminingcollisionprobabilityNonpersistentCSMAIfmediumisidle,transmit;otherwise,goto2Ifmediumisbusy,waitamountoftimedrawnfromprobabilitydistribution(retransmissiondelay)andrepeat1

RandomdelaysreducesprobabilityofcollisionsConsidertwostationsbecomereadytotransmitatsametimeWhileanothertransmissionisinprogressIfbothstationsdelaysametimebeforeretrying,bothwillattempttotransmitatsametimeCapacityiswastedbecausemediumwillremainidlefollowingendoftransmissionEvenifoneormorestationswaitingNonpersistentstationsdeferential1-persistentCSMAToavoididlechanneltime,1-persistentprotocolusedStationwishingtotransmitlistensandobeysfollowing:

Ifmediumidle,transmit;otherwise,gotostep2Ifmediumbusy,listenuntilidle;thentransmitimmediately1-persistentstationsselfishIftwoormorestationswaiting,collisionguaranteedGetssortedoutaftercollisionP-persistentCSMACompromisethatattemptstoreducecollisionsLikenonpersistentAndreduceidletimeLike1-persistentRules:Ifmediumidle,transmitwithprobabilityp,anddelayonetimeunitwithprobability(1–p)TimeunittypicallymaximumpropagationdelayIfmediumbusy,listenuntilidleandrepeatstep1Iftransmissionisdelayedonetimeunit,repeatstep1Whatisaneffectivevalueofp?PersistentandNonpersistentCSMAComparisonofthechannelutilizationversusloadforvariousrandomaccessprotocols.CSMA/CD(CollisionDetection)CSMA/CD:carriersensing,deferralasinCSMAcollisionsdetectedwithinshorttimecollidingtransmissionsaborted,reducingchannelwastagecollisiondetection:easyinwiredLANs:measuresignalstrengths,comparetransmitted,receivedsignalsdifficultinwirelessLANs:receivedsignalstrengthoverwhelmedbylocaltransmissionstrengthhumananalogy:thepoliteconversationalistCSMA/CDcollisiondetectionCSMA/CD(CollisionDetection)WithCSMA,collisionoccupiesmediumfordurationoftr