AdvancedComputerNetworkLecture3:TheMediumAccessControlLayerYangQinDepartmentofComputerScienceShenzhenGraduateSchoolHarbinInstituteofTechnologyMediumAccessControlSublayerNetworkLayerLogicalLinkControlSublayerMediumAccessControlSublayerDataLinkLayerPhysicalLayer2022年4月5日星期二2MediumAccessControlSublayer(cont’d)

Mediumaccess(MAC)sublayerisnotimportantonpoint-to-pointlinks

TheMACsublayerisonlyusedinbroadcastorsharedchannelnetworks

Examples:Satellite,Ethernet,Cellular2022年4月5日星期二3Agenda

TheChannelAllocationProblem

MultipleAccessProtocols

EthernetLANTechnology

LANSwitching2022年4月5日星期二4TheChannelAllocationProblem5MediumSharingProblemsNodeNodeBusBus(a)(b)NodeCollisionBus2022年4月5日星期二6MediumSharingProblems

Problemstobesolved

Whichnodecansendthedata?

Willacollisionhappen?

Howtosuccessfullysendaframeevenacollisionmayhappens.2022年4月5日星期二7StaticAssignmentProtocols

Staticandpredeterminedallocationofchannelaccess:independentofuseractivity

Idleusersmaybeassignedtothechannel,inwhichcasechannelcapacityiswasted

Examples:TDMA,FDMA,WDMA2022年4月5日星期二8DynamicChannelAllocation

Allthedynamicchannelallocationmethodstobediscussedarebasedonfivekeyassumptions.

z

z

z

zStationModel.SingleChannelAssumption.CollisionAssumption.(a)ContinuousTime;(b)SlottedTime

z(a)CarrierSense;(b)NoCarrierSense2022年4月5日星期二9StationModel

ThemodelconsistsofNindependentstations(e.g.,computers,telephones,orpersonalcommunicators)

Eachstationhasaprogramoruserthatgeneratesframesfortransmission.

TheprobabilityofaframebeinggeneratedinanintervaloflengthΔtisλ.Δt,whereλisaconstant(thearrivalrateofnewframes).

Onceaframehasbeengenerated,thestationisblockedanddoesnothinguntiltheframehasbeensuccessfullytransmitted.2022年4月5日星期二10SingleChannelAssumption

Asinglechannelisavailableforallcommunication.

Allstationscantransmitonitandallcanreceivefromit.

Asfarasthehardwareisconcerned,allstationsareequivalent,althoughprotocolsoftwaremayassignprioritiestothem.2022年4月5日星期二11CollisionAssumption

Iftwoframesaretransmittedsimultaneously,theywillresultinacollision.

Allstationscandetectcollisions.

Acollidedframemustbetransmittedagainlater.Therearenoerrorsotherthanthosegeneratedbycollisions.2022年4月5日星期二12TimeAssumption

ContinuousTime.Frametransmissioncanbeginatanyinstant.Thereisnomasterclockdividingtimeintodiscreteintervals.

SlottedTime.Timeisdividedintodiscreteintervals(slots).Frametransmissionsalwaysbeginatthestartofaslot.Aslotmaycontain0,1,ormoreframes,correspondingtoanidleslot,asuccessfultransmission,oracollision,respectively.2022年4月5日星期二13CarrierSenseAssumption

CarrierSense.Stationscantellifthechannelisinusebeforetryingtouseit.Ifthechannelissensedasbusy,nostationwillattempttouseituntilitgoesidle.

NoCarrierSense.Stationscannotsensethechannelbeforetryingtouseit.Theyjustgoaheadandtransmit.Onlylatercantheydeterminewhetherthetransmissionwassuccessful.2022年4月5日星期二14DemandAssignmentProtocols

Allocatechannelcapacitytohostsonademandbasis(i.e.,onlytoactiveusers)

Requiresmethodsformeasuringthedemandforthechannel

Polling

Reservationschemes

TokenPassingScheme2022年4月5日星期二15DemandAssignmentProtocols--Polling

AcentralcontrollerinterrogateseachhostandallocateschannelcapacitytothosewhoneeditGoodforsystemswith:

ShortpropagationdelaySmallpollingmessagesNon-burstytraffic

TokenPassingScheme

Atokenalwayscirculatesaroundaringnet.AusergrabsatokentotransmitdataWilldiscussdetailslaterintheTokenRingLAN

2022年4月5日星期二16ContentionAccessProtocols

Singlechannelsharedbyalargenumberofhosts

Nocoordinationbetweenhosts

Controliscompletelydistributed

Examples:ALOHA,CSMA,CSMA/CD2022年4月5日星期二17ContentionAccess(cont’d)

Advantages:

Shortdelayforburstytraffic

Simple(duetodistributedcontrol)

Flexibletofluctuationsinthenumberofhosts

Fairness2022年4月5日星期二18ContentionAccess(cont’d)

Disadvantages:

Lowchannelefficiencywithalargenumberofhosts

Notgoodforcontinuoustraffic(e.g.,voice)

Cannotsupportprioritytraffic

Highvarianceintransmissiondelays2022年4月5日星期二19MultipleAccessProtocols20MultipleAccessProtocols

ALOHA

CarrierSenseMultipleAccessProtocols

Collision-FreeProtocols

Limited-ContentionProtocols

WirelessLANProtocols2022年4月5日星期二21PureALOHA2022年4月5日星期二22CollisionPeriodofPureALOHA2022年4月5日星期二23ThroughputofPureALOHA2022年4月5日星期二24ThroughputofPureALOHA2022年4月5日星期二25SlottedALOHA

Principle:dataarealwayssentatthebeginningofatimeslot.Ifacollisionoccurs,finishthecurrenttransmissionandretryafterarandomamountoftimeslots.

SlottedALOHAcutsthevulnerableperiodforpacketsfrom2ttot.

Thisdoublesthebestpossiblethroughputfrom18.4%to36.8%

How?

Timeisslotted.Packetsmustbetransmittedwithinaslot2022年4月5日星期二26TheSlottedALOHAAlgorithm1.Ifahosthasapackettotransmit,itwaitsuntilthebeginningofthenextslotbeforesending2.Listentothebroadcastandcheckifthepacketwasdestroyed3.Iftherewasacollision,waitarandomnumberofslotsandtrytosendagain2022年4月5日星期二27ThroughputofSlottedALOHA2022年4月5日星期二28CSMA

Wecouldachievebetterthroughputifwecouldlistentothechannelbeforetransmittingapacket

Thisway,wewouldstopavoidablecollisions.

Todothis,weneed“CarrierSenseMultipleAccess,”orCSMA,protocols2022年4月5日星期二29AssumptionswithCSMANetworks1.Constantlengthpackets2.Noerrors,exceptthosecausedbycollisions3.Nocaptureeffect4.Eachhostcansensethetransmissionsofallotherhosts5.Thepropagationdelayissmallcomparedtothetransmissiontime2022年4月5日星期二30CSMA(cont’d)

ThereareseveraltypesofCSMAprotocols:

1-PersistentCSMA

Non-PersistentCSMA

P-PersistentCSMA2022年4月5日星期二311-PersistentCSMA

Sensethechannel.

Ifbusy,keeplisteningtothechannelandtransmitimmediatelywhenthechannelbecomesidle.

Ifidle,transmitapacketimmediately.

Ifcollisionoccurs,

Waitarandomamountoftimeandstartoveragain.

Theprotocoliscalled1-persistentbecausethehosttransmitswithaprobabilityof1wheneveritfindsthechannelidle.2022年4月5日星期二32TheEffectofPropagationDelayonCSMApacketABcarriersense=idleTransmitapacketCollision2022年4月5日星期二33PropagationDelayandCSMA

Contention(vulnerable)periodinPureALOHA

twopackettransmissiontimes

ContentionperiodinSlottedALOHA

onepackettransmissiontime

ContentionperiodinCSMA

upto2xend-to-endpropagationdelayPerformanceofCSMA>PerformanceofSlottedALOHA>PerformanceofPureALOHA2022年4月5日星期二341-PersistentCSMA(cont’d)

Evenifprop.delayiszero,therewillbecollisions

Example:

IfstationsBandCbecomereadyinthemiddleofA’stransmission,BandCwillwaituntiltheendofA’stransmissionandthenbothwillbegintransmittedsimultaneously,resultinginacollision.

IfBandCwerenotsogreedy,therewouldbefewercollisions2022年4月5日星期二35Non-PersistentCSMA

Sensethechannel.

Ifbusy,waitarandomamountoftimeandsensethechannelagain

Ifidle,transmitapacketimmediately

Ifcollisionoccurs

waitarandomamountoftimeandstartalloveragain2022年4月5日星期二36Tradeoffbetween1-andNon-PersistentCSMA

IfBandCbecomereadyinthemiddleofA’stransmission,

1-Persistent:BandCcollide

Non-Persistent:BandCprobablydonotcollide

IfonlyBbecomesreadyinthemiddleofA’stransmission,

1-Persistent:BsucceedsassoonasAends

Non-Persistent:Bmayhavetowait2022年4月5日星期二37P-PersistentCSMA

Optimalstrategy:useP-PersistentCSMA

Assumechannelsareslotted

Oneslot=contentionperiod(i.e.,oneroundtrippropagationdelay)2022年4月5日星期二38P-PersistentCSMA(cont’d)1.Sensethechannel

Ifchannelisidle,transmitapacketwithprobabilityp

ifapacketwastransmitted,gotostep2

ifapacketwasnottransmitted,waitoneslotandgotostep1

Ifchannelisbusy,waitoneslotandgotostep1.2.Detectcollisions

Ifacollisionoccurs,waitarandomamountoftimeandgotostep12022年4月5日星期二39P-PersistentCSMA(cont’d)

Considerp-persistentCSMAwithp=0.5

Whenahostsensesanidlechannel,itwillonlysendapacketwith50%probability

Ifitdoesnotsend,ittriesagaininthenextslot.

Theaveragenumberoftriesis:8i1i=0Si(1-p)p=p2022年4月5日星期二40ComparisonofCSMAandALOHAProtocols(NumberofChannelContenders)2022年4月5日星期二41CSMA/CD

InCSMAprotocols

Iftwostationsbegintransmittingatthesametime,eachwilltransmititscompletepacket,thuswastingthechannelforanentirepackettime

InCSMA/CDprotocols

Thetransmissionisterminatedimmediatelyuponthedetectionofacollision

CD=CollisionDetect2022年4月5日星期二42CSMA/CD(cont’d)

Sensethechannel

Ifidle,transmitimmediately

Ifbusy,waituntilthechannelbecomesidle

Collisiondetection

Abortatransmissionimmediatelyifacollisionisdetected（中止傳輸）

Tryagainlaterafterwaitingarandomamountoftime2022年4月5日星期二43CSMA/CD(cont’d)CSMA/CDcanbeinoneofthreestates:contention,transmission,oridle.（競爭、傳輸、空閑）2022年4月5日星期二44CSMA/CD(cont’d)

Carriersense

reducesthenumberofcollisions

Collisiondetection

reducestheeffectofcollisions,makingthechannelreadytousesooner2022年4月5日星期二45CollisiondetectiontimeHowlongdoesittaketorealizetherehasbeenacollision?Worstcase:2xend-to-endprop.delaypacketAB2022年4月5日星期二46Collision-FreeProtocols:Thebasicbit-mapprotocol2022年4月5日星期二47Collision-FreeProtocols:Thebinarycountdownprotocol2022年4月5日星期二48Limited-ContentionProtocols2022年4月5日星期二49Limited-ContentionProtocols(cont’d)2022年4月5日星期二50Limited-ContentionProtocols(cont’d)2022年4月5日星期二51AdaptiveTreeWalkProtocol1234567StationDeepth-firstSearchStrategy2022年4月5日星期二52AdaptiveTreeWalkProtocol<cont.>

Contentionsstartatwhichlayer?

Assumethenumberofcurrentcontendersinthesystem(stationsreadytosendframes)isq(canbeestimatedbytrafficstatistics)Calculatetheoptimallayeri(i=0…m)tostartthecontention?Eachnodeinleveliincludes2-i.nstationswherenisthetotalstationsOptimalcontentionlevel:q.2-i=1i=log2q

11=20231/2=2-145671/4=2-22022年4月5日星期二53WirelessLANProtocolsAwirelessLAN.(a)Atransmitting.(b)Btransmitting.(a)Thehiddenstationproblem.(b)Theexposedstationproblem.2022年4月5日星期二54WirelessLANProtocols(2)

TheMACAprotocol.(a)AsendinganRTStoB.(b)BrespondingwithaCTStoA.2022年4月5日星期二55EthernetLANTechnology56IEEE802LANStandards2022年4月5日星期二57IEEE802LANStandards2022年4月5日星期二58Ethernet?EthernetCabling?ManchesterEncoding?TheEthernetMACSublayerProtocol?TheBinaryExponentialBackoffAlgorithm?EthernetPerformance?SwitchedEthernet?FastEthernet?GigabitEthernet?IEEE802.2:LogicalLinkControl?RetrospectiveonEthernet2022年4月5日星期二59EthernetCablingThemostcommonkindsofEthernetcabling.2022年4月5日星期二60EthernetCabling(2)ThreekindsofEthernetcabling.(a)10Base5,(b)10Base2,(c)10Base-T.2022年4月5日星期二61EthernetCabling(3)Cabletopologies.(a)Linear,(b)Spine,(c)Tree,(d)Segmented.2022年4月5日星期二62EthernetCabling(4)(a)Binaryencoding,(b)Manchesterencoding,(c)DifferentialManchesterencoding.2022年4月5日星期二63EthernetMACSublayerProtocolFrameformats.(a)DIXEthernet,(b)IEEE802.3.2022年4月5日星期二64EthernetMACSublayerProtocolCollisiondetectioncantakeaslongas2.2022年4月5日星期二65EthernetPerformanceEfficiencyofEthernetat10Mbpswith512-bitslottimes.2022年4月5日星期二66Binaryexponentialbackoff

Whenacollisionoccureachstationwaits0or1slotsbeforetryagain

Ingeneral,aftericollision,arandomnumberbetween0and2i-1ischosen.

Maximumis1023

After16collisions,thecontrollergiveupandreportsfailure.2022年4月5日星期二67EthernetImplementationHostSystemHostSystemBusSystemInterfaceEthernetControler（MAC）Encoder/DecoderManchester（PLS）AUIInterfaceTransceiver（MAU）Coax2022年4月5日星期二68SwitchedEthernetAsimpleexampleofswitchedEthernet.2022年4月5日星期二69FastEthernetTheoriginalfastEthernetcabling.2022年4月5日星期二70IEEE802.2:LogicalLinkControl(a)PositionofLLC.(b)Protocolformats.2022年4月5日星期二71AnEthernetSnifferLANSourceDestinationSnifferNodeNode2022年4月5日星期二72AFrameCapturedbySnifferDestinationSourceAddressAddressADDRHEX000002608C82242802608C0224200081F0F00010DA3A0E00FFEF1600000000006B1619010020FF534D422D000001000600000000000000300000000000000000081804009406070000402E3F00090001FFEE13000085000000EE0050CA3C0000FFAF1200060600006D1800000060EA3A0000FF000000010000086A0012FF2022年4月5日星期二73TokenBusLANNodeANodeBNodeCNodeANodeDtokenNodeBTokenBusLANTokenBusNodeCNodeENodeDNodeE2022年4月5日星期二74LANSwitching75DataLinkLayer