高级计算机网络课件Chapter5_4th_ed_June_13_2007

5:DataLinkLayer5-1Chapter5LinkLayerandLANsAnoteontheuseofthesepptslides:We’remakingtheseslidesfreelyavailabletoall(faculty,students,readers).They’reinPowerPointformsoyoucanadd,modify,anddeleteslides(includingthisone)andslidecontenttosuityourneeds.Theyobviouslyrepresentalotofworkonourpart.Inreturnforuse,weonlyaskthefollowing:Ifyouusetheseslides(e.g.,inaclass)insubstantiallyunalteredform,thatyoumentiontheirsource(afterall,we’dlikepeopletouseourbook!)Ifyoupostanyslidesinsubstantiallyunalteredformona(orperhapsidenticalto)ourslides,andnoteourcopyrightofthismaterial.Thanksandenjoy!JFK/KWRAllmaterialcopyright1996-2007J.FKuroseandK.W.Ross,AllRightsReservedComputerNetworking:ATopDownApproach4thedition.JimKurose,KeithRossAddison-Wesley,July2007.5:DataLinkLayer5-2Chapter5:TheDataLinkLayerOurgoals:understandprinciplesbehinddatalinklayerservices:errordetection,correctionsharingabroadcastchannel:multipleaccesslinklayeraddressingreliabledatatransfer,flowcontrol:done!instantiationandimplementationofvariouslinklayertechnologies5:DataLinkLayer5-3LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8Linkvirtualization:ATM,MPLS5:DataLinkLayer5-4LinkLayer:IntroductionSometerminology:hostsandroutersarenodescommunicationchannelsthatconnectadjacentnodesalongcommunicationpatharelinkswiredlinkswirelesslinksLANslayer-2packetisaframe,encapsulatesdatagramdata-linklayerhasresponsibilityoftransferringdatagramfromonenodetoadjacentnodeoveralink5:DataLinkLayer5-5Linklayer:contextdatagramtransferredbydifferentlinkprotocolsoverdifferentlinks:e.g.,Ethernetonfirstlink,framerelayonintermediatelinks,802.11onlastlinkeachlinkprotocolprovidesdifferentservicese.g.,mayormaynotproviderdtoverlinktransportationanalogytripfromPrincetontoLausannelimo:PrincetontoJFKplane:JFKtoGenevatrain:GenevatoLausannetourist=datagramtransportsegment=communicationlinktransportationmode=linklayerprotocoltravelagent=routingalgorithm5:DataLinkLayer5-6LinkLayerServicesframing,linkaccess:encapsulatedatagramintoframe,addingheader,trailerchannelaccessifsharedmedium“MAC”addressesusedinframeheaderstoidentifysource,dest•differentfromIPaddress!reliabledeliverybetweenadjacentnodeswelearnedhowtodothisalready(chapter3)!seldomusedonlowbit-errorlink(fiber,sometwistedpair)wirelesslinks:higherrorrates•Q:whybothlink-levelandend-endreliability?5:DataLinkLayer5-7LinkLayerServices(more)flowcontrol:pacingbetweenadjacentsendingandreceivingnodeserrordetection:errorscausedbysignalattenuation,noise.receiverdetectspresenceoferrors:•signalssenderforretransmissionordropsframeerrorcorrection:receiveridentifiesandcorrectsbiterror(s)withoutresortingtoretransmissionhalf-duplexandfull-duplexwithhalfduplex,nodesatbothendsoflinkcantransmit,butnotatsametime5:DataLinkLayer5-8Whereisthelinklayerimplemented?ineachandeveryhostlinklayerimplementedin“adaptor”(akanetworkinterfacecardNIC)Ethernetcard,PCMCIcard,802.11cardimplementslink,physicallayerattachesintohost’ssystembusescombinationofhardware,software,firmwarecontrollerphysicaltransmissioncpumemoryhostbus(e.g.,PCI)networkadaptercardhostschematicapplicationtransportnetworklinklinkphysical5:DataLinkLayer5-9AdaptorsCommunicatingsendingside:encapsulatesdatagraminframeaddserrorcheckingbits,rdt,flowcontrol,etc.receivingsidelooksforerrors,rdt,flowcontrol,etcextractsdatagram,passestoupperlayeratreceivingsidecontrollercontrollersendinghostreceivinghostdatagramdatagramdatagramframe5:DataLinkLayer5-10LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8LinkVirtualization:ATM.MPLS5:DataLinkLayer5-11ErrorDetectionEDC=ErrorDetectionandCorrectionbits(redundancy)D=Dataprotectedbyerrorchecking,mayincludeheaderfields•Errordetectionnot100%reliable!•protocolmaymisssomeerrors,butrarely•largerEDCfieldyieldsbetterdetectionandcorrectionotherwise5:DataLinkLayer5-12ParityCheckingSingleBitParity:DetectsinglebiterrorsTwoDimensionalBitParity:Detectandcorrectsinglebiterrors005:DataLinkLayer5-13Internetchecksum(review)Sender:treatsegmentcontentsassequenceof16-bitintegerschecksum:addition(1’scomplementsum)ofsegmentcontentssenderputschecksumvalueintoUDPchecksumfieldReceiver:computechecksumofreceivedsegmentcheckifcomputedchecksumequalschecksumfieldvalue:NO-errordetectedYES-noerrordetected.Butmaybeerrorsnonetheless?Goal:detect“errors”(e.g.,flippedbits)intransmittedpacket(note:usedattransportlayeronly)5:DataLinkLayer5-14Checksumming:CyclicRedundancyCheckviewdatabits,D,asabinarynumberchooser+1bitpattern(generator),Ggoal:chooserCRCbits,R,suchthatD,RexactlydivisiblebyG(modulo2)receiverknowsG,dividesD,RbyG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitswidelyusedinpractice(802.11WiFi,ATM)5:DataLinkLayer5-15CRCExampleWant:D.2rXORR=nGequivalently:D.2r=