【计算机网络课程教学课件】ch4.ppt

1、2020/6/15,ComputerNetworks-04,1/119,COMPUTERNETWORKSChapter04TheMediumAccessControlSublayer,ShoubaoYangTel:3601540syang1/syangSeptember2006,2020/6/15,ComputerNetworks-04,2/119,Chapter4TheMediumAccessControlSublayer,BroadcastnetworkandtheirprotocolsTheKeyIssueis:Howtodeterminewhogets

2、tousethechannelwhenthereiscompetitionforit?,2020/6/15,ComputerNetworks-04,3/119,Broadcastchannel,multi-accesschannel,orrandomaccesschannel:anumberofstationsthatsharethesame“wire.”Ifonestationsends,alltheothersgettohearit.Whatstheproblem:ifyouresharingachannel,thentwostationsmaydecidetostartframetran

3、smissionatthesametime.Framecollision,whichmeansrubbishonthewire.Solution:Allocatethechanneltooneofthecompetingstations.,Introduction,2020/6/15,ComputerNetworks-04,4/119,MAC:mediumaccesscontrol,todeterminewhogoesnextonamulti-accesschannelbelongtoasublayerofthedatalinklayer.OSIModelLANModel,WhatisMAC?

4、,2020/6/15,ComputerNetworks-04,5/119,4.1TheChannelAllocationProblem,4.1.1StaticChannelAllocationinLANsandWANsAllocatingasinglechannelamongmultiplecompetingusers,suchasFDMandTDM,eachuserisstaticallyallocatedthebandwidthortimeslots.Thereisnointerferencebetweenusers.BothFDMandTDMcannotworkwellwithburst

5、traffic.Dividingthesingleavailablechannelintostaticsubchannelisinherentlyinefficient.Whenusersarequiescent,thebandwidthissimplywasted.Poorperformance,shownbyPoissonarrivalandservicetime:T=1/(C-),whereTismeantimedelay,Cischannelcapacity,isarrivalrate,CisservicerateTFDM=1/(C/N(/N)=N/(C-)=NT,2020/6/15,

6、ComputerNetworks-04,6/119,4.1.2DynamicChannelAllocationinLANsusesacollision-freetechniqueathighloadtoprovidegoodchannelefficiency.,Fig.4-8Acquisitionprobabilityforasymmetriccontentionchannel,2020/6/15,ComputerNetworks-04,26/119,TheAdaptiveTreeWalkProtocol,Stationsarelocatedastheleavesofabinary-tree.

7、Protocolassignscontentionslotdynamicallytostationswhohasframetosend.Searchingalgorithmisdepth-firstfromtoptobottom.Ifacollisionoccurs,thesearchcontinuesrecursivelywiththenodesleftandrightchildren.Example:C,D,andGarereadyforcontention.TestforsyphilisduringWWII,2020/6/15,ComputerNetworks-04,27/119,Bit

8、slot0:collide,moveto2Bitslot1:collide,moveto4Bitslot2:nocollision,moveto5Bitslot3:collide,assignedtoCBitslot4:assignedtoD,moveto3Bitslot5:nocollision,assignedtoGSo,totally6bitslotsareneededforC,D,G.,TheAdaptiveTreeWalkProtocol,2020/6/15,ComputerNetworks-04,28/119,4.2.5WavelengthDivisionMultipleAcces

9、sProtocol(WDMA),Principle:ifyouhavealotofbandwidth,justdividethechannelintosub-channels,anddynamicallyallocatethesub-channels.Itisusedinfiberoptics.Eachstationgetstwochannels:onecontrolchannelforhandlingincomingrequests,onefortheactualdatatransfer.Eachchannelrepeatedlycarriesafixedseriesofslots.Thed

10、atachannelcontainsastatusslotcarryinginformationonfreeslotsinitscontrolchannel.,2020/6/15,ComputerNetworks-04,29/119,InordertocontactastationA,youfirstreaditsstatusslotfromthedatachanneltoseewhichcontrolslotisunused.Youthenputatransmissionrequestinafreecontrolslot.Ifthetransmissionrequestisaccepted,

11、youcansenddataonyourowndatachannelthatwillbepickedupbyA.Youputthedatainspecificslot,andtellAwhichslotthatis.Note:theresstillalotofcompetition.Iftwosenderssaythattheresdatainslot#4forstationA,oneoftheslotswillnotbereadAcanonlyreadfromonechannelatatime.,2020/6/15,ComputerNetworks-04,30/119,Fig.4-10.Wa

12、velengthdivisionmultipleaccess,2020/6/15,ComputerNetworks-04,31/119,4.2.6WirelessLANProtocols,Basicidea:Often,thereareanumberofbasestationsconnectedthroughguidedmedia.Abasestationcancommunicatewithamobilecomputer.Themobilecomputersuseradio/infraredsignalsforcommunication.Problem:Therecanbesubtleinte

13、rference,Fig.4-11.AwirelessLAN.(a)Atransmitting.(b)Btransmitting,2020/6/15,ComputerNetworks-04,32/119,Issue(a):HowcanCbepreventedfromtryingtotransmitsomethingtoB?InthatcaseitwillruinanyreceiptbyB(hiddenstationproblem).Issue(b):HowcanwetellCthatitisallowedtotransmittoD,becausethiswillnotinterferewith

14、thecommunicationfromBtoA?(exposedstationproblem).,HiddenStationotherwiseittransmitsimmediately.Iftwoormorestationssimultaneouslybegintransmittingonanidlecable,theywillcollide.Allcollidingstationsthenterminatetheirtransmission,waitarandomtime,andrepeatthewholeprocessalloveragain.ThehistoryofIEEE802.3

15、andEthernetEthernet:aspecificproductthatalmostimplement802.3specifications.,2020/6/15,ComputerNetworks-04,36/119,IEEE802Standards,The802workinggroups.Theimportantonesaremarkedwith*.Theonesmarkedwitharehibernating.Theonemarkedwithgaveup.,2020/6/15,ComputerNetworks-04,37/119,Ethernetstandsforanearimpl

16、ementationoftheIEEE802.3protocol.ItisCSMA/CDbased(sensethechannel,waituntilidle,andback-offwhenyoudetectacollision).Note:10Base-Tispopularasitcanmakeuseoftelephonelines,andiseasytomaintainwhenitcomestocablebreaks(cablesgotohubs).Allfourtypesarewidelyused.,4.3.1802.3Cabling,2020/6/15,ComputerNetworks

17、-04,38/119,Note:DifferentEthernetsusedifferentconnectionandcablingschemes:(a)10Base5,(b)10Base2,(c)10Base-TIn10Base-Fwecanapplydifferentschemes(linear,backbone,tree).Segmentednetworkswithrepeatersareusedtobuildlargelocalinternetworks.,2020/6/15,ComputerNetworks-04,39/119,4.3.2ManchesterEncoding,Prob

18、lem:Wecantjustsendstraightbinarycodesacrossthewire,becausestationscantdistinguisha0fromanidleline.Solution:useanencodingschemeinwhichavoltagetransitionoccursduringeverybittime(ManchesterEncoding):,2020/6/15,ComputerNetworks-04,40/119,4.3.3The802.3MACSublayerProtocol,802.3FrameLayoutPreamble:Seventim

19、es10101010isusedtosynchronizethereceiversclockwiththatofthesender.Start:Justadelimitertotellthattherealinfoisnowcoming.Address:Generally48-bitfields.Leftmostbitindicatesordinaryorgroupaddresses.Secondbitindicatesglobalorlocaladdress.Length:Rangesfrom0-1500.Framesshouldalwaysbeatleast64bytes.Padding:

20、yougotit.Checksum:Calculatedoverthedatafield.CRC-based.,2020/6/15,ComputerNetworks-04,41/119,ContentionSlotandBinaryExponentiationBack-offAlgorithm,Contentionslotmustbe2.Actually2=2(totalDTEdelay+totalRepeatersdelay+totalMAUdelay+propagationdelay)=51.2sfor10MEthernetor512bit-time,2020/6/15,ComputerN

21、etworks-04,42/119,Howcomestheminimumframesizeof64bytes?512bit-timeWhyweneedminimumsize?DetectingframecollisionDistinguishgoodframefromdamagedonesWhatisthenetworkspan?2500mIfwekeeptheminimumframesizeof64bytesforcompatibilityreason,whatisthecontentiontimefor100Mand1000MEthernet?5.12sfor100M,networkspa

22、nis204m0.512sfor1000M,networkspanis20m?1000MEthernetcontentiontimeis4.096s,remainthenetworkspan204m,Questions,2020/6/15,ComputerNetworks-04,43/119,Aftericollisions,arandomnumberbetween0and2i1ischosen,andthatnumberisskipped.After10collisionshavebeenreached,therandomizationintervalisfrozenatamaximumof

23、1023slots.After16collisions,thecontrollerthrowsinthetowelandreportsfailurebacktothecomputer.Ex:1stcollision,slotsselectedfrom0,1;2ndcollision,slotsselectedfrom0,1,2,3;3rdcollision,slotsselectedfrom0,1,7;10thcollision,slotsselectedfrom0,1,1023,4.3.4TheBinaryExponentiationBackoffAlgorithm,2020/6/15,Co

24、mputerNetworks-04,44/119,4.3.5EthernetPerformance,EfficiencyofEthernetat10Mbpswith512-bitslottimes.,2020/6/15,ComputerNetworks-04,45/119,4.3.6SwitchedEthernet,Problem:Asmorestationsareadded,trafficwillgoup,andsowillthepossibilityofcollisions,then,thenetworkwillsaturate.Solution:Dividethenetworkintos

25、eparatesub-LANsandconnectthemthroughahigh-speedswitch:,2020/6/15,ComputerNetworks-04,46/119,4.3.7FastEthernet,802.3u,Problem:FDDIisjustplainexpensive,soitsokayforbackbones,butnotforbasicLANsegments.Solution:UpgradeexistingbaseofLANs(i.e.Ethernets)insuchawaythattheinterfacesremainthesame,butthecapaci

26、tygoesup,thatisthe100MbpsEthernet.Dataformats,interfaces,andprotocolsareallthesame.Thatmeansthatwecanonlydropthebittimefrom100nsecto10nsec.Justtellingeveryonetoshortentheirwireswontreallydo.,2020/6/15,ComputerNetworks-04,47/119,FastEthernet,802.3u,Thesolutionistouseonlyhubs(10Base-T)andcombineitwith

27、switchingtechnology.(10Base-Tcanmakeuseoftelephonelines,andiseasytomaintainwhenitcomestocablebreaks.)So,thecablingturnsouttobeprettyimportant:,2020/6/15,ComputerNetworks-04,48/119,Illustration,T4uses4twistedpairs,onetothehub,onefromthehub,andtwoswitchabletocurrentdirection(half-duplex).Ratherthanbin

28、arysignaling,weuseternarysignaling:threetwistedpairsintherightdirectiongives33=27possiblesignals,whichcanencodestringsof4bits.Withasignalingspeedof25MHz,wethenget100Mbpsacrossthecategory3UTPwires.Note:Ifwethensubsequentlyaddframe-bufferingcapabilitiestothehub,combinethatwithahigh-speedbackplane,weca

29、nhavestationstransmitatthesametime.Thebufferingatthehubcanavoidalotofcollisions.,2020/6/15,ComputerNetworks-04,49/119,100Base-TX,100Base-TXissimplerbecausethewirescanhandle125MHz.Onlytwotwistedpairsperstationareused,onetoswitchandonefromit.Aschemecalled4B/5Bisused,whichistokenfromFDDI.Everygroupoffi

30、veclockperiods,eachcontainingoneoftwosignalvalues,yields32combinations.16ofthesecombinationsareusedtotransmitthefourbitgroups0000,0001,1111.Therest16areusedforcontrolpurposessuchasmarkingframesboundaries.Thecombinationsusedhavebeencarefullychosentoprovideenoughtransitionstomaintainclocksynchronizati

31、on.The100Base-TXsystemisfullduplex.,2020/6/15,ComputerNetworks-04,50/119,4.3.8GigabitEthernet,802.3z,BecauseFastEthernetmaynotalwaysbefastenough,wesimplymovethedecimalpointonepositionandgetGigabitEthernet:transferEthernetframesat1000Mbps.Note:Standardizationisalmostthere.GigabitEthernetpromisestobeo

32、neofthemostimportantsolutionforLANsandMANs,aswellaslong-haul(LH)connections.ItsEthernetalltheway.,2020/6/15,ComputerNetworks-04,51/119,SimplestGigabitEthernetConfiguration,Atwo-stationEthernet.Amulti-stationEthernet.,2020/6/15,ComputerNetworks-04,52/119,GigabitEthernetSpecifications(1),Twodifferentm

33、odesofoperationFull-duplexmode:allowstrafficinbothdirectionatthesametime,point-to-pointcommunication,nocontention,CSMA/CDisnotused.Half-duplexmode:connectedtoahub,collisionsarepossible,CSMA/CDisrequired,themaximumdistanceis100timesless,or25metersfor64-byteshortframe,tomaintaintheessentialpropertieso

34、fEthernet.TwofeaturestothestandardtoincreasetheradiusCarrierextension:tellsthehardwaretoadditsownpaddingafterthenormalframetoextendtheframeto512bytes,hasalineefficiencyof9%(46/512).Framebursting:allowsasendertotransmitaconcatenatedsequenceofmultipleframesinasingletransmission,ifthetotalburstislessth

35、an512bytes,thehardwarepadsitagain.,2020/6/15,ComputerNetworks-04,53/119,GigabitEthernetSpecifications(2),Encoding8B/10B:each8-bitbyteisencodedonthefiberas10bits,1024possibleoutputcodeword.1000Base-T:4twistedpairsareusedtoallow4symbolstobetransmittedinparallel,eachsymbolisencodedusingoneoffivevoltage

36、levelstoencode00,01,10,11,oraspecialvalueforcontrolpurposes.Thus,thereare2databitspertwistedpairor8databitsperclockcycle,runsat125MHz,allowing1-Gbpsoperation.FlowcontrolPAUSEframesareusedtotelltheotherendtopauseforsomeperiodoftime,inunitsoftheminimumframetime,whichis512ns,allowingforpausesaslongas33

37、.6ms.10GEthernet:IEEE802.3ae,2002,2020/6/15,ComputerNetworks-04,54/119,4.3.9IEEE802.2:LogicalLinkControl,LLCrunsontopofallthe802LANandMANprotocols,hidesthedifferencesbetweenthevariouskindsof802networksprovidingasingleformatandinterfacetothenetworklayer.Thisformat,interface,andprotocolareallcloselyba

38、sedonOSI.,2020/6/15,ComputerNetworks-04,55/119,IEEE802.2:LogicalLinkControl,TypicalLLCusageNetworklayerpassesapackettoLLCLLCaddsanLLCheader,containingsequenceandacknowledgenumbers,basedontheolderHDLCResultingstructureisinsertedintothepayloadfieldofan802.xframeandtransmitted.Receiverdoestheinversepro

39、cessLLCserviceoptionsUnreliabledatagramserviceAcknowledgeddatagramserviceReliableconnection-orientedservice,2020/6/15,ComputerNetworks-04,56/119,4.4WirelessLANs,4.4.1The802.11ProtocolStackPartofthe802.11protocolstack.,2020/6/15,ComputerNetworks-04,57/119,4.4.2The802.11PhysicalLayer,InfraredFHSS(Freq

40、uencyHoppingSpreadSpectrum)Uses79channels,each1-MHzwide,atthelowendofthe2.4-GHzISMbandDSSS(DirectSequenceSpreadSpectrum),restrictedto1or2Mbps802.11a,OFDM(OrthogonalFrequencyDivisionMultiplexing)54Mbpsinthewider5-GHzISMband802.11b,HR-DSSS(HighRateDirectSequenceSpreadSpectrum)11Mbpsinthe2.4-GHzISMband

41、802.11g,OFDM11Mbpsinthenarrow2.4-GHzISMband,intheory,canoperateatupto54Mbps,2020/6/15,ComputerNetworks-04,58/119,4.4.3The802.11MACSublayerProtocol(1),(a)Thehiddenstationproblem.(b)Theexposedstationproblem.,Twooperatemodes:DCF(DistributedCoordinationFunction)PCF(PointCoordinationFunction),2020/6/15,C

42、omputerNetworks-04,59/119,The802.11MACSublayerProtocol(2),TheuseofvirtualchannelsensingusingCSMA/CAforDCF.Aframeburst,2020/6/15,ComputerNetworks-04,60/119,The802.11MACSublayerProtocol(3),Interframespacingin802.11,2020/6/15,ComputerNetworks-04,61/119,4.4.4The802.11FrameStructure,The802.11dataframe.,2

43、020/6/15,ComputerNetworks-04,62/119,4.4.5802.11Services,DistributionServicesAssociationDisassociationReassociationDistributionIntegrationIntracellularServicesAuthenticationDeauthenticationPrivacyDataDelivery,2020/6/15,ComputerNetworks-04,63/119,4.5BroadbandWireless,Comparisonof802.11and802.16The802.

44、16ProtocolStackThe802.16PhysicalLayerThe802.16MACSublayerProtocolThe802.16FrameStructure,2020/6/15,ComputerNetworks-04,64/119,4.5.2The802.16ProtocolStack,The802.16ProtocolStackOperatesinthe10-to-66GHzrangeQPSK:50Mbpswith2bits/baudQAM-64,802.16a:150Mbpswith6bits/baudQAM-16,802.16b:100Mbpswith4bits/ba

45、ud,2020/6/15,ComputerNetworks-04,65/119,4.5.3The802.16PhysicalLayer,The802.16transmissionenvironment.,2020/6/15,ComputerNetworks-04,66/119,The802.16PhysicalLayer(2),Framesandtimeslotsfortimedivisionduplexing.FrameStructure(a)Agenericframe.(b)Abandwidthrequestframe.,2020/6/15,ComputerNetworks-04,67/1

46、19,The802.16MACSublayerProtocol,ServiceClassesConstantbitrateserviceReal-timevariablebitrateserviceNon-real-timevariablebitrateserviceBesteffortsservice,2020/6/15,ComputerNetworks-04,68/119,4.6Bluetooth,Essence:Bluetoothistoallowverydifferent(portableandfixed)deviceslocatedineachothersproximitytoexc

47、hangeinformation:Letverydifferentportabledevices(PDA,cellularphone,notebook)setupconnectionsReplacemanyoftheexistingcables(headset,keyboard,mouse,printer)Providebetterwirelessconnection(handsfreesolutions)ProvidewirelessaccesstoInternetentrypointsRelativelyhighbandwidth:1Mbit/second,2020/6/15,Comput

48、erNetworks-04,69/119,BluetoothProtocolStack,2020/6/15,ComputerNetworks-04,70/119,Radio:Operatesinunlicensedbandaround2.4GHzusingfrequencyhopping:Takedatasignalandmodulateitwithacarriersignalthatchangesfrequencyinhops.HopsforBluetooth:fixedat2402+kMHz=0,1,78Goodtominimizeinterferencefromotherdevices(

49、microwaveovens!)Baseband:Coreofthedatalinklayer.Determinestiming,framing,packets,andflowcontrol.Providessynchronousandasynchronousdatacommunication.,BluetoothProtocolStack,2020/6/15,ComputerNetworks-04,71/119,Linkmanager:Managesconnections,powermanagementLogicallinkcontrol:Multiplexingofhigher-level

50、protocols,segmentationandreassemblyoflargepackets,devicediscoveryAudio:Handlesstreamingforvoice-relatedapplicationsRFCOMM:EmulateserialcablebasedonGSMprotocolTCP/IP:ImplementationoftheTCP/IP(bridging,addressresolution,MTUdefinition,andmulticastingissuesApplication:WAPandIrDAinteroperabilityandallthe

51、funstuff,BluetoothProtocolStack,2020/6/15,ComputerNetworks-04,72/119,4.6.1BluetoothArchitecture,Thelinkmanagerhandlesanad-hocstructureknownasapiconet:Acollectionofdevicesthatcommunicate.Thecollectionissetupbyasinglemasterdevice,probingforotherdevicestojoinasslavesUptosevenslavescanbeactiveinthesamep

52、iconet;moreslavesmaybeina(lowpower)“parked”stateImportant:Apiconetisconstructedon-the-flyOverlappingpiconetsformascatternetAdevicecanparticipateinmultiple(overlapping)piconets,2020/6/15,ComputerNetworks-04,73/119,BluetoothArchitecture,Twopiconetscanbeconnectedtoformascatternet.,2020/6/15,ComputerNet

53、works-04,74/119,4.6.2BluetoothApplications,TheBluetoothprofiles.,2020/6/15,ComputerNetworks-04,75/119,4.6.3TheBluetoothProtocolStack,The802.15versionoftheBluetoothprotocolarchitecture.,2020/6/15,ComputerNetworks-04,76/119,4.6.5TheBluetoothFrameStructure,AtypicalBluetoothdataframe.,2020/6/15,Computer

54、Networks-04,77/119,BluetoothConnectionEstablishment,Sniff:ListenformessagesatfixedtimeintervalsHold:Nosupportforasynchronousdatatransfer;onlysynchronousdata(i.e.,voice).Allowsthemastertoperhapsattendotherpiconet.Park:Giveupeverythinguntilmasterwakesyouup.,2020/6/15,ComputerNetworks-04,78/119,Bluetoo

55、thFuture,Ingeneral:Thisisextremelypromisingtechnology:itmaybemorethanjustahype!Cordlesstelephony,unifyingthecellphonesandthecordlessphonesathomeIntercomforwirelesstwo-waycommunication(ahhh-thebabysitter)HeadsetsDial-upnetworking:letacomputerconnecttotheInternetbymeansofacellphoneFaxingusingmobilepho

56、nes,2020/6/15,ComputerNetworks-04,79/119,LANaccess:letabunchofBluetoothdevicessetupawirelessLANElectronicbusinesscardsFiletransferAutomaticsynchronizationbetweencomputersandotherdevicesCar(in-vehicle)communicationHigh-qualityaudio/videoGeographicalpositioning,BluetoothFuture,2020/6/15,ComputerNetwor

57、ks-04,80/119,IEEEStandard802.4:TokenBus,Problem:In802.3thereisapossibilitythatyoullneverbeabletotransmit:theremaybesimultaneoustransmissionefforts,waitingtimeincreaseswitheachfailedattempttostarttransmission(binaryexponentialbackoff).802.3isnotacceptableforreal-time,reliable,industrialsystems:Maketh

58、enetworkdeterministicbylogicallyorganizingthestationsinaring.Whenastationwantstotransmit,itrequiresaspecialcontrolframecalledatoken.,2020/6/15,ComputerNetworks-04,81/119,Thetokenishandedfromstationtostation.Physically,allstationsareconnectedtoasinglebus(aswithEthernet).WHY!?Physicallyabustopology,ne

59、tworkcontrolisinthehandofalogicalring.,IEEEStandard802.4:TokenBus,2020/6/15,ComputerNetworks-04,82/119,TokenBusFrameTheonlythingincommonwith802.3aretheaddresses(sigh.).Therealimportantdifferenceliesinthecontrolframes(Ethernetdoesnthavethose):Claimthetokenduringringinitialization.Allownewsenderstoenterthering.Recoverfromtokenloss.Resolvecontendingstationsforpositioninthering.Allowstationtoleavethering.,IEEEStandard802.4:TokenBus,2020/6/15,ComputerNetworks-04,83/119,Note:Stationsmaintaintheringinalogicalfashionithasnothingtodowiththeirphysica