北京科技大学计算机网络双语课课件第5章

5:DataLinkLayer,5-1,Chapter5LinkLayerandLANs,Anoteontheuseofthesepptslides:Weremakingtheseslidesfreelyavailabletoall(faculty,students,readers).TheyreinPowerPointformsoyoucanadd,modify,anddeleteslides(includingthisone)andslidecontenttosuityourneeds.Theyobviouslyrepresentalotofworkonourpart.Inreturnforuse,weonlyaskthefollowing:Ifyouusetheseslides(e.g.,inaclass)insubstantiallyunalteredform,thatyoumentiontheirsource(afterall,wedlikepeopletouseourbook!)Ifyoupostanyslidesinsubstantiallyunalteredformonawwwsite,thatyounotethattheyareadaptedfrom(orperhapsidenticalto)ourslides,andnoteourcopyrightofthismaterial.Thanksandenjoy!JFK/KWRAllmaterialcopyright1996-2007J.FKuroseandK.W.Ross,AllRightsReserved,ComputerNetworking:ATopDownApproach4thedition.JimKurose,KeithRossAddison-Wesley,July2007.,5:DataLinkLayer,5-2,Chapter5:TheDataLinkLayer,Ourgoals:understandprinciplesbehinddatalinklayerservices:errordetection,correctionsharingabroadcastchannel:multipleaccesslinklayeraddressingreliabledatatransfer,flowcontrol:done!instantiationandimplementationofvariouslinklayertechnologies,5:DataLinkLayer,5-3,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8Linkvirtualization:ATM,MPLS,5:DataLinkLayer,5-4,LinkLayer:Introduction,Someterminology:hostsandroutersarenodescommunicationchannelsthatconnectadjacentnodesalongcommunicationpatharelinkswiredlinkswirelesslinksLANslayer-2packetisaframe,encapsulatesdatagram,data-linklayerhasresponsibilityoftransferringdatagramfromonenodetoadjacentnodeoveralink,5:DataLinkLayer,5-5,Linklayer:context,datagramtransferredbydifferentlinkprotocolsoverdifferentlinks:e.g.,Ethernetonfirstlink,framerelayonintermediatelinks,802.11onlastlinkeachlinkprotocolprovidesdifferentservicese.g.,mayormaynotproviderdtoverlink,transportationanalogytripfromPrincetontoLausannelimo:PrincetontoJFKplane:JFKtoGenevatrain:GenevatoLausannetourist=datagramtransportsegment=communicationlinktransportationmode=linklayerprotocoltravelagent=routingalgorithm,5:DataLinkLayer,5-6,LinkLayerServices,framing,linkaccess:encapsulatedatagramintoframe,addingheader,trailerchannelaccessifsharedmedium“MAC”addressesusedinframeheaderstoidentifysource,destdifferentfromIPaddress!reliabledeliverybetweenadjacentnodeswelearnedhowtodothisalready(chapter3)!seldomusedonlowbit-errorlink(fiber,sometwistedpair)wirelesslinks:higherrorratesQ:whybothlink-levelandend-endreliability?,5:DataLinkLayer,5-7,LinkLayerServices(more),flowcontrol:pacingbetweenadjacentsendingandreceivingnodeserrordetection:errorscausedbysignalattenuation,noise.receiverdetectspresenceoferrors:signalssenderforretransmissionordropsframeerrorcorrection:receiveridentifiesandcorrectsbiterror(s)withoutresortingtoretransmissionhalf-duplexandfull-duplexwithhalfduplex,nodesatbothendsoflinkcantransmit,butnotatsametime,5:DataLinkLayer,5-8,Whereisthelinklayerimplemented?,ineachandeveryhostlinklayerimplementedin“adaptor”(akanetworkinterfacecardNIC)Ethernetcard,PCMCIcard,802.11cardimplementslink,physicallayerattachesintohostssystembusescombinationofhardware,software,firmware,controller,physicaltransmission,cpu,memory,hostbus(e.g.,PCI),networkadaptercard,hostschematic,5:DataLinkLayer,5-9,AdaptorsCommunicating,sendingside:encapsulatesdatagraminframeaddserrorcheckingbits,rdt,flowcontrol,etc.,receivingsidelooksforerrors,rdt,flowcontrol,etcextractsdatagram,passestoupperlayeratreceivingside,controller,controller,sendinghost,receivinghost,datagram,datagram,datagram,frame,5:DataLinkLayer,5-10,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8LinkVirtualization:ATM.MPLS,5:DataLinkLayer,5-11,ErrorDetection,EDC=ErrorDetectionandCorrectionbits(redundancy)D=Dataprotectedbyerrorchecking,mayincludeheaderfieldsErrordetectionnot100%reliable!protocolmaymisssomeerrors,butrarelylargerEDCfieldyieldsbetterdetectionandcorrection,otherwise,5:DataLinkLayer,5-12,ParityChecking,SingleBitParity:Detectsinglebiterrors,TwoDimensionalBitParity:Detectandcorrectsinglebiterrors,0,0,5: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),5:DataLinkLayer,5-14,Checksumming:CyclicRedundancyCheck,viewdatabits,D,asabinarynumberchooser+1bitpattern(generator),Ggoal:chooserCRCbits,R,suchthatexactlydivisiblebyG(modulo2)receiverknowsG,dividesbyG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitswidelyusedinpractice(802.11WiFi,ATM),5:DataLinkLayer,5-15,CRCExample,Want:D.2rXORR=nGequivalently:D.2r=nGXORRequivalently:ifwedivideD.2rbyG,wantremainderR,R=remainder,D.2rG,5:DataLinkLayer,5-16,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet,5.6Link-layerswitches5.7PPP5.8LinkVirtualization:ATM,MPLS,5: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),5:DataLinkLayer,5-18,MultipleAccessprotocols,singlesharedbroadcastchanneltwoormoresimultaneoustransmissionsbynodes:interferencecollisionifnodereceivestwoormoresignalsatthesametimemultipleaccessprotocoldistributedalgorithmthatdetermineshownodessharechannel,i.e.,determinewhennodecantransmitcommunicationaboutchannelsharingmustusechannelitself!noout-of-bandchannelforcoordination,5:DataLinkLayer,5-19,IdealMultipleAccessProtocol,BroadcastchannelofrateRbps1.whenonenodewantstotransmit,itcansendatrateR.2.whenMnodeswanttotransmit,eachcansendataveragerateR/M3.fullydecentralized:nospecialnodetocoordinatetransmissionsnosynchronizationofclocks,slots4.simple,5:DataLinkLayer,5-20,MACProtocols:ataxonomy,Threebroadclasses:ChannelPartitioningdividechannelintosmaller“pieces”(timeslots,frequency,code)allocatepiecetonodeforexclusiveuseRandomAccesschannelnotdivided,allowcollisions“recover”fromcollisions“Takingturns”nodestaketurns,butnodeswithmoretosendcantakelongerturns,5: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,5:DataLinkLayer,5-22,ChannelPartitioningMACprotocols:FDMA,FDMA:frequencydivisionmultipleaccesschannelspectrumdividedintofrequencybandseachstationassignedfixedfrequencybandunusedtransmissiontimeinfrequencybandsgoidleexample:6-stationLAN,1,3,4havepkt,frequencybands2,5,6idle,frequencybands,time,FDMcable,5:DataLinkLayer,5-23,RandomAccessProtocols,WhennodehaspackettosendtransmitatfullchanneldatarateR.noaprioricoordinationamongnodestwoormoretransmittingnodes“collision”,randomaccessMACprotocolspecifies:howtodetectcollisionshowtorecoverfromcollisions(e.g.,viadelayedretransmissions)ExamplesofrandomaccessMACprotocols:slottedALOHAALOHACSMA,CSMA/CD,CSMA/CA,5:DataLinkLayer,5-24,SlottedALOHA,Assumptions:allframessamesizetimedividedintoequalsizeslots(timetotransmit1frame)nodesstarttotransmitonlyslotbeginningnodesaresynchronizedif2ormorenodestransmitinslot,allnodesdetectcollision,Operation:whennodeobtainsfreshframe,transmitsinnextslotifnocollision:nodecansendnewframeinnextslotifcollision:noderetransmitsframeineachsubsequentslotwithprob.puntilsuccess,5:DataLinkLayer,5-25,SlottedALOHA,Prossingleactivenodecancontinuouslytransmitatfullrateofchannelhighlydecentralized:onlyslotsinnodesneedtobeinsyncsimple,Conscollisions,wastingslotsidleslotsnodesmaybeabletodetectcollisioninlessthantimetotransmitpacketclocksynchronization,5: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!,!,5:DataLinkLayer,5-27,Pure(unslotted)ALOHA,unslottedAloha:simpler,nosynchronizationwhenframefirstarrivestransmitimmediatelycollisionprobabilityincreases:framesentatt0collideswithotherframessentint0-1,t0+1,5: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!,5:DataLinkLayer,5-29,CSMA(CarrierSenseMultipleAccess),CSMA:listenbeforetransmit:Ifchannelsensedidle:transmitentireframeIfchannelsensedbusy,defertransmissionhumananalogy:dontinterruptothers!,5: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!,5:DataLinkLayer,5-57,CSMA/CDefficiency,Tprop=maxpropdelaybetween2nodesinLANttrans=timetotransmitmax-sizeframeefficiencygoesto1astpropgoesto0asttransgoestoinfinitybetterperformancethanALOHA:andsimple,cheap,decentralized!,5: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,5:DataLinkLayer,5-64,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,5:DataLinkLayer,5-65,Switch:self-learning,switchlearnswhichhostscanbereachedthroughwhichinterfaceswhenframereceived,switch“learns”locationofsender:incomingLANsegmentrecordssender/locationpairinswitchtable,A,A,B,B,C,C,1,2,3,4,5,6,Switchtable(initiallyempty),5:DataLinkLayer,5-66,Switch:framefiltering/forwarding,Whenframereceived:1.recordlinkassociatedwithsendinghost2.indexswitchtableusingMACdestaddress3.ifentryfoundfordestinationthenifdestonsegmentfromwhichframearrivedthendroptheframeelseforwardtheframeoninterfaceindicatedelseflood,forwardonallbuttheinterfaceonwhichtheframearrived,5:DataLinkLayer,5-67,Self-learning,forwarding:example,A,A,B,B,C,C,1,2,3,4,5,6,Switchtable(initiallyempty),framedestinationunknown:,flood,destinationAlocationknown:,selectivesend,5:DataLinkLayer,5-68,Interconnectingswitches,switchescanbeconnectedtogether,A,B,Q:sendingfromAtoF-howdoesS1knowtoforwardframedestinedtoFviaS4andS3?A:selflearning!(worksexactlythesameasinsingle-switchcase!),S1,C,5:DataLinkLayer,5-69,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,5:DataLinkLayer,5-70,Institutionalnetwork,toexternalnetwork,router,IPsubnet,mailserver,webserver,5:DataLinkLayer,5-71,Switchesvs.Routers,bothstore-and-forwarddevicesrouters:networklayerdevices(examinenetworklayerheaders)switchesarelinklayerdevicesroutersmaintainroutingtables,implementroutingalgorithmsswitchesmaintainswitchtables,implementfiltering,learningalgorithms,5:DataLinkLayer,5-72,Summarycomparison,5:DataLinkLayer,5-73,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet,5.6Hubsandswitches5.7PPP5.8LinkVirtualization:ATM,5:DataLinkLayer,5-74,PointtoPointDataLinkControl,onesender,onereceiver,onelink:easierthanbroadcastlink:noMediaAccessControlnoneedforexplicitMACaddressinge.g.,dialuplink,ISDNlinepopularpoint-to-pointDLCprotocols:PPP(point-to-pointprotocol)HDLC:Highleveldatalinkcontrol(Datalinkusedtobeconsidered“highlayer”inprotocolstack!,5:DataLinkLayer,5-75,PPPDesignRequirementsRFC1557,packetframing:encapsulationofnetwork-layerdatagramindatalinkframecarrynetworklayerdataofanynetworklayerprotocol(notjustIP)atsametimeabilitytodemultiplexupwardsbittransparency:mustcarryanybitpatterninthedatafielderrordetection(nocorrection)connectionliveness:detect,signallinkfailuretonetworklayernetworklayeraddressnegotiation:endpointcanlearn/configureeachothersnetworkaddress,5:DataLinkLayer,5-76,PPPnon-requirements,noerrorcorrection/recoverynoflowcontroloutoforderdeliveryOKnoneedtosupportmultipointlinks(e.g.,polling),Errorrecovery,flowcontrol,datare-orderingallrelegatedtohigherlayers!,5:DataLinkLayer,5-77,PPPDataFrame,Flag:delimiter(framing)Address:doesnothing(onlyoneoption)Control:doesnothing;inthefuturepossiblemultiplecontrolfieldsProtocol:upperlayerprotocoltowhichframedelivered(eg,PPP-LCP,IP,IPCP,etc),5:DataLinkLayer,5-78,PPPDataFrame,info:upperlayerdatabeingcarriedcheck:cyclicredundancycheckforerrordetection,5:DataLinkLayer,5-79,ByteStuffing,“datatransparency”requirement:datafieldmustbeallowedtoincludeflagpatternQ:isreceiveddataorflag?Sender:adds(“stuffs”)extrabyteaftereachdatabyteReceiver:two01111110bytesinarow:discardfirstbyte,continuedatareceptionsingle01111110:flagbyte,5:DataLinkLayer,5-80,ByteStuffing,flagbytepatternindatatosend,flagbytepatternplusstuffedbyteintransmitteddata,5:DataLinkLayer,5-81,PPPDataControlProtocol,Beforeexchangingnetwork-layerdata,datalinkpeersmustconfigurePPPlink(max.framelength,authentication)learn/configurenetworklayerinformationforIP:carryIPControlProtocol(IPCP)msgs(protocolfield:8021)toconfigure/learnIPaddress,5:DataLinkLayer,5-82,LinkLayer,5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet,5.6Hubsandswitches5.7PPP5.8LinkVirtualization:ATMandMPLS,5:DataLinkLayer,5-83,Virtualizationofnetworks,Virtualizationofresources:powerfulabstractioninsystemsengineering:computingexamples:virtualmemory,virtualdevicesVirtualmachines:e.g.,javaIBMVMosfrom1960s/70slayeringofabstractions:dontsweatthedetailsofthelowerlayer,onlydealwithlowerlayersabstractly,5:DataLinkLayer,5-84,TheInternet:virtualizingnetworks,1974:multipleunconnectednetsARPAnetdata-over-cablenetworkspacketsatellitenetwork(Aloha)packetradionetwork,differingin:addressingconventionspacketformatserrorrecoveryrouting,ARPAnet,satellitenet,AProtocolforPacketNetworkIntercommunication,V.Cerf,R.Kahn,IEEETransactionsonCommunications,May,1974,pp.637-648.,5:DataLinkLayer,5-85,TheInternet:virtualizingnetworks,ARPAnet,satellitenet,gateway,Gateway:“embedinternetworkpacketsinlocalpacketformatorextractthem”route(atinternetworklevel)tonextgateway,5:DataLinkLayer,5-86,Cerfbitsynchronization;bandwidthpartitions(TDM);severalspeeds:OC3=155.52Mbps;OC12=622.08Mbps;OC48=2.45Gbps,OC192=9.6GbpsTI/T3:transmissionframestructure(oldtelephonehierarchy):1.5Mbps/45Mbpsunstructured:justcells(busy/idle),5:DataLinkLayer,5-100,IP-Over-ATM,ClassicIPonly3“networks”(e.g.,LANsegments)MAC(802.3)andIPaddresses,IPoverATMreplace“network”(e.g.,LANsegment)withATMnetworkATMaddresses,IPaddresses,ATMnetwork,EthernetLANs,EthernetLANs,5:DataLinkLayer,5-101,IP-Over-ATM,5:DataLinkLayer,5-102,DatagramJourne