大二下计算机网络chapter5

5:DataLinkLayer5-1Chapter5

LinkLayerandLANsComputerNetworking:ATopDownApproach

4thedition.

JimKurose,KeithRoss

Addison-Wesley,July2007.

5:DataLinkLayer5-2LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5:DataLinkLayer5-3LinkLayer:IntroductionSometerminology:hostsandroutersarenodescommunicationchannelsthatconnectadjacentnodesalongcommunicationpatharelinkswiredlinkswirelesslinksLANslayer-2packetisaframe,

encapsulatesdatagramdata-linklayerhasresponsibilityoftransferringdatagramfromonenodetoadjacentnodeoveralink5:DataLinkLayer5-4LinkLayerServicesframing,linkaccess:

encapsulatedatagramintoframe,addingheader,trailerchannelaccessifsharedmedium“MAC”addressesusedinframeheaderstoidentifysource,destdifferentfromIPaddress!reliabledeliverybetweenadjacentnodeswelearnedhowtodothisalready(chapter3)!seldomusedonlowbit-errorlink(fiber,sometwistedpair)wirelesslinks:higherrorrates5:DataLinkLayer5-5LinkLayerServices(more)flowcontrol:

pacingbetweenadjacentsendingandreceivingnodeserrordetection:

errorscausedbysignalattenuation,noise.receiverdetectspresenceoferrors:errorcorrection:

receiveridentifiesandcorrectsbiterror(s)withoutresortingtoretransmissionhalf-duplexandfull-duplexwithhalfduplex,nodesatbothendsoflinkcantransmit,butnotatsametime5:DataLinkLayer5-6Whereisthelinklayerimplemented?ineachrouterandeveryhostlinklayerimplementedin“adaptor”(akanetworkinterfacecardNIC)e.g.Ethernetcardimplementslink,physicallayerattachesintohost’ssystembusescombinationofhardware,software,firmwarecontrollerphysicaltransmissioncpumemoryhostbus(e.g.,PCI)networkadaptercardhostschematicapplicationtransportnetworklinklinkphysical5:DataLinkLayer5-7AdaptorsCommunicatingsendingside:encapsulatesdatagraminframeaddserrorcheckingbits,rdt,flowcontrol,etc.receivingsidelooksforerrors,rdt,flowcontrol,etcextractsdatagram,passestoupperlayeratreceivingsidecontrollercontrollersendinghostreceivinghostdatagramdatagramdatagramframe5:DataLinkLayer5-8LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection

5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8LinkVirtualization:ATM.MPLS5:DataLinkLayer5-9ErrorDetectionEDC=ErrorDetectionandCorrectionbits(redundancy)D=Dataprotectedbyerrorchecking,mayincludeheaderfields

Errordetectionnot100%reliable!protocolmaymisssomeerrors,butrarelylargerEDCfieldyieldsbetterdetectionandcorrectionotherwise5:DataLinkLayer5-10Checksumming:CyclicRedundancyCheckviewdatabits,D,asabinarynumberchooser+1bitpattern(generator),G

goal:chooserCRCbits,R,suchthat<D,R>exactlydivisiblebyG(modulo2)receiverknowsG,divides<D,R>byG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitswidelyusedinpractice(802.11WiFi,ATM)5:DataLinkLayer5-11CRCExample5:DataLinkLayer5-12LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8LinkVirtualization:ATM,MPLS5:DataLinkLayer5-13MultipleAccessLinksandProtocolsTwotypesof“links”:point-to-pointPPPfordial-upaccesspoint-to-pointlinkbetweenEthernetswitchandhostbroadcast(sharedwireormedium)old-fashionedEthernetupstreamHFC802.11wirelessLANsharedwire(e.g.,cabledEthernet)sharedRF(e.g.,802.11WiFi)sharedRF(satellite)humansatacocktailparty(sharedair,acoustical)5:DataLinkLayer5-14MultipleAccessprotocolssinglesharedbroadcastchanneltwoormoresimultaneoustransmissionsbynodes:interferencecollisionifnodereceivestwoormoresignalsatthesametimemultipleaccessprotocoldistributedalgorithmthatdetermineshownodessharechannel,i.e.,determinewhennodecantransmit5:DataLinkLayer5-15MACProtocols:ataxonomyThreebroadclasses:ChannelPartitioningdividechannelintosmaller“pieces”(timeslots,frequency,code)allocatepiecetonodeforexclusiveuseRandomAccesschannelnotdivided,allowcollisions“recover”fromcollisions“Takingturns”nodestaketurns,butnodeswithmoretosendcantakelongerturns5:DataLinkLayer5-16ChannelPartitioningMACprotocols:TDMATDMA:timedivisionmultipleaccess

accesstochannelin"rounds"eachstationgetsfixedlengthslot(length=pkttranstime)ineachroundunusedslotsgoidleexample:6-stationLAN,1,3,4havepkt,slots2,5,6idle1341346-slotframe5:DataLinkLayer5-17ChannelPartitioningMACprotocols:FDMAFDMA:frequencydivisionmultipleaccess

channelspectrumdividedintofrequencybandseachstationassignedfixedfrequencybandunusedtransmissiontimeinfrequencybandsgoidleexample:6-stationLAN,1,3,4havepkt,frequencybands2,5,6idlefrequencybandstimeFDMcable5:DataLinkLayer5-18RandomAccessProtocolsWhennodehaspackettosendtransmitatfullchanneldatarateR.noaprioricoordinationamongnodestwoormoretransmittingnodes➜“collision”,randomaccessMACprotocolspecifies:howtodetectcollisionshowtorecoverfromcollisions(e.g.,viadelayedretransmissions)ExamplesofrandomaccessMACprotocols:ALOHAandslottedALOHACSMA,CSMA/CD,CSMA/CA5:DataLinkLayer5-19collisionscanstilloccur:propagationdelaymeanstwonodesmaynotheareachother’stransmissioncollision:entirepackettransmissiontimewastedspatiallayoutofnodesnote:roleofdistance&propagationdelayindeterminingcollisionprobabilityCSMA:listenbeforetransmit:Ifchannelsensedidle:transmitentireframeIfchannelsensedbusy,defertransmissionCSMA(CarrierSenseMultipleAccess)5:DataLinkLayer5-20CSMA/CD(CollisionDetection)CSMA/CD:carriersensing,deferralasinCSMAcollisionsdetectedwithinshorttimecollidingtransmissionsaborted,reducingchannelwastage

CSMA/CD先听再讲--载波监听边讲边听—进行检测检测冲突处理--发送站检测到冲突后立即停止帧的发送，并且发一个简短的堵塞信号(称强化冲突信号，Jammingsignal)，通知网上各站已经发生冲突，本站及网上所有站都等待一段随机分布的时间，然后再按CSMA/CD方式重发该帧。5:DataLinkLayer5-21LANtechnologiesDatalinklayersofar:services,errordetection/correction,multipleaccessNext:LANtechnologiesaddressingEthernetswitchesPPP5:DataLinkLayer5-22

OSI/RMLANNetworkLayerDataLinkLayerPhysicalLayerLLCMACPhysicalMostoftraditionalLANismedium-sharing(usingbroadcastchannel)Needsnotfunctionsofrouteselecting,soitonlyhasthefunctionsofthefirstandsecondlayersofOSIDatalinklayerisdividedintotwosub-layers:LLCandMAC.OSI/RM&LANMODEL(1)OSI/RM&LANMODEL(1)5:DataLinkLayer5-23MAC(MediaAccessControl):

respectiveoftransmissionmediumsandtopologies

Framing/disassemblingframeAddressingBiterrordetectingRealizingandmaintainMACprotocolOSI/RM&LANMODEL(2)

OSI/RMLANNetworkLayerDataLinkLayerPhysicalLayerLLCMACPhysical5:DataLinkLayer5-24LLC(LogicalLinkControl):

irrespectiveoftransmissionmediumsandtopologiesEstablishandreleaselogicconnectionofdatalinklayerProvideinterfacetoupperlayerAddsequencenumbertoframe,flowcontrol,errorcontrolOSI/RM&LANMODEL(3)

OSI/RMLANNetworkLayerDataLinkLayerPhysicalLayerLLCMACPhysical5:DataLinkLayer5-25LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8LinkVirtualization:ATM,MPLS5:DataLinkLayer5-26MACAddressesandARP32-bitIPaddress:network-layeraddressusedtogetdatagramtodestinationIPsubnetMAC(orLANorphysicalorEthernet)address:

function:

getframefromoneinterfacetoanotherphysically-connectedinterface(samenetwork)48bitMACaddress(formostLANs)burnedinNICROM,alsosometimessoftwaresettable5:DataLinkLayer5-27LANAddressesandARPEachadapteronLANhasuniqueLANaddressBroadcastaddress=FF-FF-FF-FF-FF-FF=adapter1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53

LAN(wiredorwireless)5:DataLinkLayer5-28LANAddress(more)MACaddressallocationadministeredbyIEEEmanufacturerbuysportionofMACaddressspace(toassureuniqueness)MACflataddresscanmoveLANcardfromoneLANtoanotherIPhierarchicaladdressNOTportableaddressdependsonIPsubnettowhichnodeisattached5:DataLinkLayer5-29ARP:AddressResolutionProtocolEachIPnode(host,router)onLANhasARPtableARPtable:IP/MACaddressmappingsforsomeLANnodes

<IPaddress;MACaddress;TTL>

TTL(TimeToLive):timeafterwhichaddressmappingwillbeforgotten(typically20min)Question:howtodetermineMACaddressofBknowingB’sIPaddress?1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53

LAN137.196.7.23137.196.7.78137.196.7.14137.196.7.885:DataLinkLayer5-30ARPprotocol:SameLAN(network)AwantstosenddatagramtoB,andB’sMACaddressnotinA’sARPtable.AbroadcastsARPquerypacket,containingB'sIPaddressdestMACaddress=FF-FF-FF-FF-FF-FFallmachinesonLANreceiveARPquery

BreceivesARPpacket,repliestoAwithits(B's)MACaddressframesenttoA’sMACaddress(unicast)Acaches(saves)IP-to-MACaddresspairinitsARPtableuntilinformationesold(timesout)ARPis“plug-and-play”:nodescreatetheirARPtableswithoutinterventionfromnetadministrator5:DataLinkLayer5-31Addressing:routingtoanotherLANR1A-23-F9-CD-06-9B222.222.222.220111.111.111.110E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D111.111.111.112111.111.111.111A74-29-9C-E8-FF-55222.222.222.22188-B2-2F-54-1A-0FB222.222.222.22249-BD-D2-C7-56-2Awalkthrough:senddatagramfromAtoBviaRassumeAknowsB’sIPaddresstwoARPtablesinrouterR,oneforeachIPnetwork(LAN)5:DataLinkLayer5-32AcreatesIPdatagramwithsourceA,destinationBAusesARPtogetR’sMACaddressfor111.111.111.110Acreateslink-layerframewithR'sMACaddressasdest,framecontainsA-to-BIPdatagramA’sNICsendsframeR’sNICreceivesframeRremovesIPdatagramfromEthernetframe,seesitsdestinedtoBRusesARPtogetB’sMACaddressRcreatesframecontainingA-to-BIPdatagramsendstoBR1A-23-F9-CD-06-9B222.222.222.220111.111.111.110E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D111.111.111.112111.111.111.111A74-29-9C-E8-FF-55222.222.222.22188-B2-2F-54-1A-0FB222.222.222.22249-BD-D2-C7-56-2AThisisareallyimportantexample–makesureyouunderstand!5:DataLinkLayer5-33LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8LinkVirtualization:ATMandMPLS5:DataLinkLayer5-34Startopologybustopologypopularthroughmid90sallnodesinsamecollisiondomain(cancollidewitheachother)today:startopologyprevailsactiveswitchincentereach“spoke”runsa(separate)Ethernetprotocol(nodesdonotcollidewitheachother)switchbus:coaxialcablestar5:DataLinkLayer5-35EthernetFrameStructureSendingadapterencapsulatesIPdatagram(orothernetworklayerprotocolpacket)inEthernetframePreamble:

7byteswithpattern10101010followedbyonebytewithpattern10101011usedtosynchronizereceiver,senderclockrates5:DataLinkLayer5-36EthernetFrameStructure(more)Addresses:6bytesifadapterreceivesframewithmatchingdestinationaddress,orwithbroadcastaddress(egARPpacket),itpassesdatainframetonetworklayerprotocolotherwise,adapterdiscardsframeType:indicateshigherlayerprotocol(mostlyIPbutotherspossible,e.g.,NovellIPX,AppleTalk)CRC:checkedatreceiver,iferrorisdetected,frameisdroppedData:46-1500byte5:DataLinkLayer5-37Ethernet:Unreliable,connectionlessconnectionless:NohandshakingbetweensendingandreceivingNICsunreliable:receivingNICdoesn’tsendacksornackstosendingNICstreamofdatagramspassedtonetworklayercanhavegaps(missingdatagrams)gapswillbefilledifappisusingTCPotherwise,appwillseegapsEthernet’sMACprotocol:unslottedCSMA/CD5:DataLinkLayer5-38EthernetCSMA/CDalgorithm1.NICreceivesdatagramfromnetworklayer,createsframe2.IfNICsenseschannelidle,startsframetransmissionIfNICsenseschannelbusy,waitsuntilchannelidle,thentransmits3.IfNICtransmitsentireframewithoutdetectinganothertransmission,NICisdonewithframe!4.IfNICdetectsanothertransmissionwhiletransmitting,abortsandsendsjamsignal5.Afteraborting,NICentersexponentialbackoff5:DataLinkLayer5-39Ethernet’sCSMA/CD(more)ExponentialBackoff:

Goal:adaptretransmissionattemptstoestimatedcurrentloadheavyload:randomwaitwillbelongeraftermthcollision,NICchoosesKatrandomfrom

{0,1,2,…,2m-1}.NICwaitsK·512bittimes,forexample:firstcollision:chooseKfrom{0,1};delayisK·512bittransmissiontimesaftersecondcollision:chooseKfrom{0,1,2,3}…aftertencollisions,chooseKfrom{0,1,2,3,4,…,1023}Aftersixteencollisions,abandonthetransmission.5:DataLinkLayer5-40LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5:DataLinkLayer5-41Hubs…physical-layer(“dumb”)repeaters:bitscominginonelinkgooutallotherlinksatsamerateallnodesconnectedtohubcancollidewithoneanothernoframebufferingnoCSMA/CDathub:hostNICsdetectcollisionstwistedpairhub5:DataLinkLayer5-42Switchlink-layerdevice:smarterthanhubs,takeactiverolestore,forwardEthernetframesexamineingframe’sMACaddress,selectivelyforwardframetoone-or-moreoutgoinglinkswhenframeistobeforwardedonsegment,usesCSMA/CDtoaccesssegmenttransparenthostsareunawareofpresenceofswitchesplug-and-play,self-learningswitchesdonotneedtobeconfigured5:DataLinkLayer5-43Switch:allowsmultiplesimultaneoustransmissionshostshavededicated,directconnectiontoswitchswitchesbufferpacketsEthernetprotocolusedoneachinglink,butnocollisions;fullduplexeachlinkisitsowncollisiondomainswitching:A-to-A’andB-to-B’simultaneously,withoutcollisionsnotpossiblewithdumbhubAA’BB’CC’switchwithsixinterfaces(1,2,3,4,5,6)

1234565:DataLinkLayer5-44SwitchTableQ:howdoesswitchknowthatA’reachableviainterface4,B’reachableviainterface5?A:eachswitchhasaswitchtable,eachentry:(MACaddressofhost,interfacetoreachhost,timestamp)lookslikearoutingtable!Q:howareentriescreated,maintainedinswitchtable?somethinglikearoutingprotocol?AA’BB’CC’switchwithsixinterfaces(1,2,3,4,5,6)

1234565:DataLinkLayer5-45Switch:self-learningswitchlearnswhichhostscanbereachedthroughwhichinterfaceswhenframereceived,switch“learns”locationofsender:ingLANsegmentrecordssender/locationpairinswitchtableAA’BB’CC’123456AA’Source:ADest:A’MACaddrinterfaceTTLSwitchtable(initiallyempty)A1605:DataLinkLayer5-46Switch:framefiltering/forwardingWhenframereceived:

1.recordlinkassociatedwithsendinghost2.indexswitchtableusingMACdestaddress3.ifentryfoundfordestination

then{ifdestonsegmentfromwhichframearrived

thendroptheframe

elseforwardtheframeoninterfaceindicated

}

elseflood

forwardonallbuttheinterfaceonwhichtheframearrived5:DataLinkLayer5-47Self-learning,forwarding:exampleAA’BB’CC’123456AA’Source:ADest:A’MACaddrinterfaceTTLSwitchtable(initiallyempty)A160AA’AA’AA’AA’AA’framedestinationunknown:floodA’AdestinationAlocationknown:A’460selectivesend5:DataLinkLayer5-48InstitutionalnetworktoexternalnetworkrouterIPsubnetmailserverwebserver5:DataLinkLayer5-49Switchesvs.Routersbothstore-and-forwarddevicesrouters:networklayerdevices(examinenetworklayerheaders)switchesarelinklayerdevicesroutersmaintainroutingtables,implementroutingalgorithmsswitchesmaintainswitchtables,implementfiltering,learningalgorithms

5:DataLinkLayer5-50Summarycomparison5:DataLinkLayer5-51LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet5.6Hubsandswitches5.7PPP5:DataLinkLayer5-52PointtoPointDataLinkControlonesender,onereceiver,onelink:easierthanbroadcastlink:noMediaAccessControlnoneedforexplicitMACaddressinge.g.,dialuplink,ISDNlinepopularpoint-to-pointDLCprotocols:PPP(point-to-pointprotocol)HDLC:Highleveldatalinkcontrol5:DataLinkLayer5-53PPPDesignRequirements[RFC1557]packetframing:encapsulationofnetwork-layerdatagramindatalinkframecarrynetworklayerdataofanynetworklayerprotocol(notjustIP)abilitytodemultiplexupwardsbittransparency:mustcarryanybitpatterninthedatafield