计算机网络理论教学资料chapter5-z

DataLinkLayer,5-1,ComputerNetworking:ATopDownApproach5thedition.JimKurose,KeithRossAddison-Wesley,April2009.,ComputerNetworks,Dr.GuifengZheng(郑贵锋)gfzheng,DataLinkLayer,5-2,Chapter5:TheDataLinkLayer,Ourgoals:understandprinciplesbehinddatalinklayerservices:errordetection,correctionsharingabroadcastchannel:multipleaccesslinklayeraddressingreliabledatatransfer,flowcontrol:done!instantiationandimplementationofvariouslinklayertechnologies,DataLinkLayer,5-3,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9Adayinthelifeofawebrequest,DataLinkLayer,5-4,LinkLayer:Introduction,Terminology:hostsandroutersarenodescommunicationchannelsthatconnectadjacentnodesalongcommunicationpatharelinkswiredlinkswirelesslinksLANslayer-2packetisaframe,encapsulatesdatagram,data-linklayerhasresponsibilityoftransferringdatagramfromonenodetophysicallyadjacentnodeoveralink,DataLinkLayer,5-5,Linklayer:context,datagramtransferredbydifferentlinkprotocolsoverdifferentlinks:e.g.,Ethernetonfirstlink,framerelayonintermediatelinks,802.11onlastlinkeachlinkprotocolprovidesdifferentservicese.g.,mayormaynotproviderdtoverlink,transportationanalogytripfromPrincetontoLausannelimo:PrincetontoJFKplane:JFKtoGenevatrain:GenevatoLausannetourist=datagramtransportsegment=communicationlinktransportationmode=linklayerprotocoltravelagent=routingalgorithm,DataLinkLayer,5-6,LinkLayerServices,framing,linkaccess:encapsulatedatagramintoframe,addingheader,trailerchannelaccessifsharedmedium“MAC”addressesusedinframeheaderstoidentifysource,destdifferentfromIPaddress!reliabledeliverybetweenadjacentnodeswelearnedhowtodothisalready(chapter3)!seldomusedonlowbit-errorlink(fiber,sometwistedpair)wirelesslinks:higherrorratesQ:whybothlink-levelandend-endreliability?,DataLinkLayer,5-7,LinkLayerServices(more),flowcontrol:pacingbetweenadjacentsendingandreceivingnodeserrordetection:errorscausedbysignalattenuation,noise.receiverdetectspresenceoferrors:signalssenderforretransmissionordropsframeerrorcorrection:receiveridentifiesandcorrectsbiterror(s)withoutresortingtoretransmissionhalf-duplexandfull-duplexwithhalfduplex,nodesatbothendsoflinkcantransmit,butnotatsametime,DataLinkLayer,5-8,Whereisthelinklayerimplemented?,ineachandeveryhostlinklayerimplementedin“adaptor”(akanetworkinterfacecardNIC)Ethernetcard,PCMCIcard,802.11cardimplementslink,physicallayerattachesintohostssystembusescombinationofhardware,software,firmware,controller,physicaltransmission,cpu,memory,hostbus(e.g.,PCI),networkadaptercard,hostschematic,DataLinkLayer,5-9,AdaptorsCommunicating,sendingside:encapsulatesdatagraminframeaddserrorcheckingbits,rdt,flowcontrol,etc.,receivingsidelooksforerrors,rdt,flowcontrol,etcextractsdatagram,passestoupperlayeratreceivingside,controller,controller,sendinghost,receivinghost,datagram,datagram,datagram,frame,DataLinkLayer,5-10,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9Adayinthelifeofawebrequest,DataLinkLayer,5-11,ErrorDetection,EDC=ErrorDetectionandCorrectionbits(redundancy)D=Dataprotectedbyerrorchecking,mayincludeheaderfieldsErrordetectionnot100%reliable!protocolmaymisssomeerrors,butrarelylargerEDCfieldyieldsbetterdetectionandcorrection,otherwise,DataLinkLayer,5-12,ParityChecking,SingleBitParity:Detectsinglebiterrors,TwoDimensionalBitParity:Detectandcorrectsinglebiterrors,0,0,DataLinkLayer,5-13,Internetchecksum(review),Sender:treatsegmentcontentsassequenceof16-bitintegerschecksum:addition(1scomplementsum)ofsegmentcontentssenderputschecksumvalueintoUDPchecksumfield,Receiver:computechecksumofreceivedsegmentcheckifcomputedchecksumequalschecksumfieldvalue:NO-errordetectedYES-noerrordetected.Butmaybeerrorsnonetheless?,Goal:detect“errors”(e.g.,flippedbits)intransmittedpacket(note:usedattransportlayeronly),DataLinkLayer,5-14,Checksumming:CyclicRedundancyCheck,viewdatabits,D,asabinarynumberchooser+1bitpattern(generator),Ggoal:chooserCRCbits,R,suchthatexactlydivisiblebyG(modulo2)receiverknowsG,dividesbyG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitswidelyusedinpractice(Ethernet,802.11WiFi,ATM),DataLinkLayer,5-15,CRCExample,Want:D.2rXORR=nGequivalently:D.2r=nGXORRequivalently:ifwedivideD.2rbyG,wantremainderR,R=remainder,D.2rG,DataLinkLayer,5-16,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9Adayinthelifeofawebrequest,DataLinkLayer,5-17,MultipleAccessLinksandProtocols,Twotypesof“links”:point-to-pointPPPfordial-upaccesspoint-to-pointlinkbetweenEthernetswitchandhostbroadcast(sharedwireormedium)old-fashionedEthernetupstreamHFC802.11wirelessLAN,sharedwire(e.g.,cabledEthernet),sharedRF(e.g.,802.11WiFi),sharedRF(satellite),humansatacocktailparty(sharedair,acoustical),DataLinkLayer,5-18,MultipleAccessprotocols,singlesharedbroadcastchanneltwoormoresimultaneoustransmissionsbynodes:interferencecollisionifnodereceivestwoormoresignalsatthesametimemultipleaccessprotocoldistributedalgorithmthatdetermineshownodessharechannel,i.e.,determinewhennodecantransmitcommunicationaboutchannelsharingmustusechannelitself!noout-of-bandchannelforcoordination,DataLinkLayer,5-19,IdealMultipleAccessProtocol,BroadcastchannelofrateRbps1.whenonenodewantstotransmit,itcansendatrateR.2.whenMnodeswanttotransmit,eachcansendataveragerateR/M3.fullydecentralized:nospecialnodetocoordinatetransmissionsnosynchronizationofclocks,slots4.simple,DataLinkLayer,5-20,MACProtocols:ataxonomy,Threebroadclasses:ChannelPartitioningdividechannelintosmaller“pieces”(timeslots,frequency,code)allocatepiecetonodeforexclusiveuseRandomAccesschannelnotdivided,allowcollisions“recover”fromcollisions“Takingturns”nodestaketurns,butnodeswithmoretosendcantakelongerturns,DataLinkLayer,5-21,ChannelPartitioningMACprotocols:TDMA,TDMA:timedivisionmultipleaccessaccesstochannelinroundseachstationgetsfixedlengthslot(length=pkttranstime)ineachroundunusedslotsgoidleexample:6-stationLAN,1,3,4havepkt,slots2,5,6idle,1,3,4,1,3,4,6-slotframe,DataLinkLayer,5-22,ChannelPartitioningMACprotocols:FDMA,FDMA:frequencydivisionmultipleaccesschannelspectrumdividedintofrequencybandseachstationassignedfixedfrequencybandunusedtransmissiontimeinfrequencybandsgoidleexample:6-stationLAN,1,3,4havepkt,frequencybands2,5,6idle,frequencybands,time,FDMcable,DataLinkLayer,5-23,RandomAccessProtocols,WhennodehaspackettosendtransmitatfullchanneldatarateR.noaprioricoordinationamongnodestwoormoretransmittingnodes“collision”,randomaccessMACprotocolspecifies:howtodetectcollisionshowtorecoverfromcollisions(e.g.,viadelayedretransmissions)ExamplesofrandomaccessMACprotocols:slottedALOHAALOHACSMA,CSMA/CD,CSMA/CA,DataLinkLayer,5-24,SlottedALOHA,Assumptions:allframessamesizetimedividedintoequalsizeslots(timetotransmit1frame)nodesstarttotransmitonlyslotbeginningnodesaresynchronizedif2ormorenodestransmitinslot,allnodesdetectcollision,Operation:whennodeobtainsfreshframe,transmitsinnextslotifnocollision:nodecansendnewframeinnextslotifcollision:noderetransmitsframeineachsubsequentslotwithprob.puntilsuccess,DataLinkLayer,5-25,SlottedALOHA,Prossingleactivenodecancontinuouslytransmitatfullrateofchannelhighlydecentralized:onlyslotsinnodesneedtobeinsyncsimple,Conscollisions,wastingslotsidleslotsnodesmaybeabletodetectcollisioninlessthantimetotransmitpacketclocksynchronization,DataLinkLayer,5-26,SlottedAlohaefficiency,suppose:Nnodeswithmanyframestosend,eachtransmitsinslotwithprobabilitypprobthatgivennodehassuccessinaslot=p(1-p)N-1probthatanynodehasasuccess=Np(1-p)N-1,maxefficiency:findp*thatmaximizesNp(1-p)N-1formanynodes,takelimitofNp*(1-p*)N-1asNgoestoinfinity,gives:Maxefficiency=1/e=.37,Efficiency:long-runfractionofsuccessfulslots(manynodes,allwithmanyframestosend),Atbest:channelusedforusefultransmissions37%oftime!,!,DataLinkLayer,5-27,Pure(unslotted)ALOHA,unslottedAloha:simpler,nosynchronizationwhenframefirstarrivestransmitimmediatelycollisionprobabilityincreases:framesentatt0collideswithotherframessentint0-1,t0+1,DataLinkLayer,5-28,PureAlohaefficiency,P(successbygivennode)=P(nodetransmits).P(noothernodetransmitsinp0-1,p0.P(noothernodetransmitsinp0-1,p0=p.(1-p)N-1.(1-p)N-1=p.(1-p)2(N-1)choosingoptimumpandthenlettingn-infty.=1/(2e)=.18,evenworsethanslottedAloha!,DataLinkLayer,5-29,CSMA(CarrierSenseMultipleAccess),CSMA:listenbeforetransmit:Ifchannelsensedidle:transmitentireframeIfchannelsensedbusy,defertransmissionhumananalogy:dontinterruptothers!,DataLinkLayer,5-30,CSMAcollisions,collisionscanstilloccur:propagationdelaymeanstwonodesmaynotheareachotherstransmission,collision:entirepackettransmissiontimewasted,spatiallayoutofnodes,note:roleofdistance48bitsBittime:.1microsecfor10MbpsEthernet;forK=1023,waittimeisabout50msec,ExponentialBackoff:Goal:adaptretransmissionattemptstoestimatedcurrentloadheavyload:randomwaitwillbelongerfirstcollision:chooseKfrom0,1;delayisK512bittransmissiontimesaftersecondcollision:chooseKfrom0,1,2,3aftertencollisions,chooseKfrom0,1,2,3,4,1023,See/interactwithJavaappletonAWLWebsite:highlyrecommended!,DataLinkLayer,5-57,CSMA/CDefficiency,tprop=maxpropdelaybetween2nodesinLANttrans=timetotransmitmax-sizeframeefficiencygoesto1astpropgoesto0asttransgoestoinfinitybetterperformancethanALOHA:andsimple,cheap,decentralized!,DataLinkLayer,5-58,802.3EthernetStandards:Linkfullduplexeachlinkisitsowncollisiondomainswitching:A-to-AandB-to-Bsimultaneously,withoutcollisionsnotpossiblewithdumbhub,A,A,B,B,C,C,switchwithsixinterfaces(1,2,3,4,5,6),1,2,3,4,5,6,DataLinkLayer,5-65,SwitchTable,Q:howdoesswitchknowthatAreachableviainterface4,Breachableviainterface5?A:eachswitchhasaswitchtable,eachentry:(MACaddressofhost,interfacetoreachhost,timestamp)lookslikearoutingtable!Q:howareentriescreated,maintainedinswitchtable?somethinglikearoutingprotocol?,A,A,B,B,C,C,switchwithsixinterfaces(1,2,3,4,5,6),1,2,3,4,5,6,DataLinkLayer,5-66,Switch:self-learning,switchlearnswhichhostscanbereachedthroughwhichinterfaceswhenframereceived,switch“learns”locationofsender:incomingLANsegmentrecordssender/locationpairinswitchtable,A,A,B,B,C,C,1,2,3,4,5,6,Switchtable(initiallyempty),DataLinkLayer,5-67,Switch:framefiltering/forwarding,Whenframereceived:1.recordlinkassociatedwithsendinghost2.indexswitchtableusingMACdestaddress3.ifentryfoundfordestinationthenifdestonsegmentfromwhichframearrivedthendroptheframeelseforwardtheframeoninterfaceindicatedelseflood,forwardonallbuttheinterfaceonwhichtheframearrived,DataLinkLayer,5-68,Self-learning,forwarding:example,A,A,B,B,C,C,1,2,3,4,5,6,Switchtable(initiallyempty),framedestinationunknown:,flood,destinationAlocationknown:,selectivesend,DataLinkLayer,5-69,Interconnectingswitches,switchescanbeconnectedtogether,A,B,Q:sendingfromAtoG-howdoesS1knowtoforwardframedestinedtoGviaS4andS3?A:selflearning!(worksexactlythesameasinsingle-switchcase!),S1,C,DataLinkLayer,5-70,Self-learningmulti-switchexample,SupposeCsendsframetoI,IrespondstoC,Q:showswitchtablesandpacketforwardinginS1,S2,S3,S4,A,B,S1,C,D,E,F,S2,S4,S3,H,I,G,1,2,DataLinkLayer,5-71,Institutionalnetwork,toexternalnetwork,router,IPsubnet,mailserver,webserver,DataLinkLayer,5-72,Switchesvs.Routers,bothstore-and-forwarddevicesrouters:network-layerdevices(examinenetwork-layerheaders)switchesarelink-layerdevices(examinelink-layerheaders)routersmaintainroutingtables,implementroutingalgorithmsswitchesmaintainswitchtables,implementfiltering,learningalgorithms,applicationtransportnetworklinkphysical,switch,applicationtransportnetworklinkphysical,DataLinkLayer,5-73,VLANs:motivation,Whathappensif:CSusermovesofficetoEE,butwantsconnecttoCSswitch?singlebroadcastdomain:alllayer-2broadcasttraffic(ARP,DHCP)crossesentireLAN(security/privacy,efficiencyissues)eachlowestlevelswitchhasonlyfewportsinuse,ComputerScience,ElectricalEngineering,ComputerEngineering,Whatswrongwiththispicture?,DataLinkLayer,5-74,VLANs,Port-basedVLAN:switchportsgrouped(byswitchmanagementsoftware)sothatsinglephysicalswitch,Switch(es)supportingVLANcapabilitiescanbeconfiguredtodefinemultiplevirtualLANSoversinglephysicalLANinfrastructure.,VirtualLocalAreaNetwork,1,8,9,16,10,2,7,ElectricalEngineering(VLANports1-8),ComputerScience(VLANports9-15),15,ElectricalEngineering(VLANports1-8),ComputerScience(VLANports9-16),operatesasmultiplevirtualswitches,DataLinkLayer,5-75,Port-basedVLAN,1,8,9,16,10,2,7,ElectricalEngineering(VLANports1-8),ComputerScience(VLANports9-15),15,trafficisolation:framesto/fromports1-8canonlyreachports1-8canalsodefineVLANbasedonMACaddressesofendpoints,ratherthanswitchport,dynamicmembership:portscanbedynamicallyassignedamongVLANs,router,DataLinkLayer,5-76,VLANSspanningmultipleswitches,trunkport:carriesframesbetweenVLANSdefinedovermultiplephysicalswitchesframesforwardedwithinVLANbetweenswitchescantbevanilla802.1frames(mustcarryVLANIDinfo)802.1qprotocoladds/removedadditionalheaderfieldsforframesforwardedbetweentrunkports,1,8,9,10,2,7,ElectricalEngineering(VLANports1-8),ComputerScience(VLANports9-15),15,2,7,3,Ports2,3,5belongtoEEVLANPorts4,6,7,8belongtoCSVLAN,5,4,6,8,DataLinkLayer,5-77,2-byteTagProtocolIdentifier(value:81-00),TagControlInformation(12bitVLANIDfield,3bitpriorityfieldlikeIPTOS),RecomputedCRC,802.1QVLANframeformat,802.1frame,802.1Qframe,DataLinkLayer,5-78,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9Adayinthelifeofawebrequest,DataLinkLayer,5-79,PointtoPointDataLinkControl,onesender,onereceiver,onelink:easierthanbroadcastlink:noMediaAccessControlnoneedforexplicitMACaddressinge.g.,dialuplink,ISDNlinepopularpoint-to-pointDLCprotocols:PPP(point-to-pointprotocol)HDLC:Highleveldatalinkcontrol(Datalinkusedtobeconsidered“highlayer”inprotocolstack!,DataLinkLayer,5-80,PPPDesignRequirementsRFC1557,packetframing:encapsulationofnetwork-layerdatagramindatalinkframecarrynetworklayerdataofanynetworklayerprotocol(notjustIP)atsametimeabilitytodemultiplexupwardsbittransparency:mustcarryanybitpatterninthedatafielderrordetection(nocorrection)connectionliveness:detect,signallinkfailuretonetworklayernetworklayeraddressnegotiation:endpointcanlearn/configureeachothersnetworkaddress,DataLinkLayer,5-81,PPPnon-requirements,noerrorcorrection/recoverynoflowcontroloutoforderdeliveryOKnoneedtosupportmultipointlinks(e.g.,polling),Errorrecovery,flowcontrol,datare-orderingallrelegatedtohigherlayers!,DataLinkLayer,5-82,PPPDataFrame,Flag:delimiter(framing)Address:doesnothing(onlyoneoption)Control:doesnothing;inthefuturepossiblemultiplecontrolfieldsProtocol:upperlayerprotocoltowhichframedelivered(e.g.,PPP-LCP,IP,IPCP,etc),DataLinkLayer,5-83,PPPDataFrame,info:upperlayerdatabeingcarriedcheck:cyclicredundancycheckforerrordetection,DataLinkLayer,5-84,ByteStuffing,“datatransparency”requirement:datafieldmustbeallowedtoincludeflagpatternQ:isreceiveddataorflag?Sender:adds(“stuffs”)extrabyteaftereachdatabyteReceiver:two01111110bytesinarow:discardfirstbyte,continuedatareceptionsingle01111110:flagbyte,DataLinkLayer,5-85,ByteStuffing,flagbytepatternindatatosend,flagbytepatternplusstuffedbyteintransmitteddata,DataLinkLayer,5-86,PPPDataControlProtocol,Beforeexchangingnetwork-layerdata,datalinkpeersmustconfigurePPPlink(max.framelength,authentication)learn/configurenetworklayerinformationforIP:carryIPControlProtocol(IPCP)msgs(protocolfield:8021)toconfigure/learnIPaddress,DataLinkLayer,5-87,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9Adayinthelifeofawebrequest,DataLinkLayer,5-88,Virtualizationofnetworks,Virtualizationofresources:powerfulabstractioninsystemsengineering:computingexamples:virtualmemory,virtualdevicesVirtualmachines:e.g.,javaIBMVMosfrom1960s/70slayeringofabstractions:dontsweatthedetailsofthelowerlayer,onlydealwithlowerlayersabstractly,DataLinkLayer,5-89,TheInternet:virtualizingnetworks,1974:multipleunconnectednetsARPAnetdata-over-cablenetworkspacketsatellitenetwork(Aloha)packetradionetwork,differingin:addressingconventionspacketformatserrorrecoveryrouting,ARPAnet,satellitenet,AProtocolforPacketNetworkIntercommunication,V.Cerf,R.Kahn,IEEETransactionsonCommunications,May,1974,pp.637-648.,DataLinkLayer,5-90,TheInternet:virtualizingnetworks,ARPAnet,satellitenet,gateway,Gateway:“embedinternetworkpacketsinlocalpacketformatorextractthem”route(atinternetworklevel)tonextgateway,DataLinkLayer,5-91,Cerf&KahnsInternetworkArchitecture,Whatisvirtualized?twolayersofaddressing:internetworkandlocalnetworknewlayer(IP)makeseverythinghomogeneousatinternetworklayerunderlyinglocalnetworktechnologycablesatellite56Ktelephonemodemtoday:ATM,MPLS“invisible”atinternetworklayer.LookslikealinklayertechnologytoIP!,DataLinkLayer,5-92,ATMandMPLS,ATM,MPLSseparatenetworksintheirownrightdifferentservicemodels,addressing,routingfromInternetviewedbyInternetaslogicallinkconnectingIProutersjustlikedialuplinkisreallypartofseparatenetwork(telephonenetwork)ATM,MPLS:oftechnicalinterestintheirownright,DataLinkLayer,5-93,AsynchronousTransferMode:ATM,1990s/00standardforhigh-speed(155Mbpsto622Mbpsandhigher)BroadbandIntegratedServiceDigitalNetworkarchitectureGoal:integrated,end-endtransportofcarryvoice,video,datam