計(jì)算機(jī)網(wǎng)絡(luò)英文版課件：Chapter5 The Data Link Layer

Chapter5:TheDataLinkLayerOurgoals:

understandprinciplesbehinddatalinklayerservices:errordetection,correctionsharingabroadcastchannel:multipleaccesslinklayeraddressingreliabledatatransfer,flowcontrol:done!instantiationandimplementationofvariouslinklayertechnologies15:DataLinkLayerLinkLayer:IntroductionSometerminology:hostsandroutersarenodesLinks：

communicationchannelsthatconnectadjacentnodeswiredlinkswirelesslinksLANslayer-2packetisaframe,

encapsulatesdatagramdata-linklayerhasresponsibilityoftransferringdatagramfromonenodetoadjacentnodeoveralink25:DataLinkLayerLinklayer:contextdatagramtransferredbydifferentlinkprotocolsoverdifferentlinks:EthernetlinkPpplinkATMlinkframerelayFiberlink802.11link…eachlinkprotocolprovidesdifferentservicese.g.,mayormaynotproviderdtoverlink35:DataLinkLayerLinkLayerServicesframing,linkaccess:

encapsulatedatagramintoframe,addingheader,trailerchannelaccessifsharedmedium“MAC”addressesusedinframeheaderstoidentifysource,destdifferentfromIPaddress!reliabledeliverybetweenadjacentnodeswelearnedhowtodothisalready(chapter3)!seldomusedonlowbit-errorlink(fiber,sometwistedpair)wirelesslinks:higherrorratesQ:whybothlink-levelandend-endreliability?45:DataLinkLayerLinkLayerServices(more)flowcontrol:

pacingbetweenadjacentsendingandreceivingnodeserrordetection:

errorscausedbysignalattenuation,noise.receiverdetectspresenceoferrors:signalssenderforretransmissionordropsframeerrorcorrection:

receiveridentifiesandcorrectsbiterror(s)withoutresortingtoretransmissionhalf-duplexandfull-duplexwithhalfduplex,nodesatbothendsoflinkcantransmit,butnotatsametime55:DataLinkLayerWhereisthelinklayerimplemented?ineachandeveryhostlinklayerimplementedin“adapter”(akanetworkinterfacecardNIC)Ethernetcard,PCMCIcard,802.11cardimplementslink,physicallayerattachesintohost’ssystembusescombinationofhardware,software,firmwarecontrollerphysicaltransmissioncpumemoryhostbus(e.g.,PCI)networkadaptercardhostschematicapplicationtransportnetworklinklinkphysical65:DataLinkLayerAdaptersCommunicatingsendingside:encapsulatesdatagraminframeaddserrorcheckingbits,rdt,flowcontrol,etc.receivingsidelooksforerrors,rdt,flowcontrol,etcextractsdatagram,passestoupperlayeratreceivingsidecontrollercontrollersendinghostreceivinghostdatagramdatagramdatagramframe75:DataLinkLayerErrorDetectionEDC=ErrorDetectionandCorrectionbits(redundancy)D=Dataprotectedbyerrorchecking,mayincludeheaderfields

Errordetectionnot100%reliable!protocolmaymisssomeerrors,butrarelylargerEDCfieldyieldsbetterdetectionandcorrectionotherwise85:DataLinkLayerParityCheckingSingleBitParity:DetectsinglebiterrorsTwoDimensionalBitParity:Detectandcorrectsinglebiterrors0095:DataLinkLayerCRC:CyclicRedundancyCheckviewdatabits,D,asabinarynumberchooser+1bitpattern(generator),G

goal:chooserCRCbits,R,suchthat<D,R>exactlydivisiblebyG(modulo2)receiverknowsG,divides<D,R>byG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitswidelyusedinpractice(Ethernet,802.11WiFi,ATM)105:DataLinkLayerCRCExampleWant:D.2rXORR=nGequivalently:D.2r=nGXORRequivalently:

ifwedivideD.2rbyG,wantremainderRR=remainder[]D.2rG115:DataLinkLayerMultipleAccessLinksandProtocolsTypesof“l(fā)inks”:point-to-pointPPPfordial-upaccesspoint-to-pointlinkbetweenEthernetswitchandhostbroadcast(sharedwireormedium)old-fashionedEthernetupstreamHFC802.11wirelessLANSwitched

Ethernetsharedwire(e.g.,cabledEthernet)sharedRF(e.g.,802.11WiFi)sharedRF(satellite)humansatacocktailparty(sharedair,acoustical)125:DataLinkLayerMultipleAccessprotocolssinglesharedbroadcastchanneltwoormoresimultaneoustransmissionsbynodes:interferencecollisionifnodereceivestwoormoresignalsatthesametimemultipleaccessprotocolsDecentralizedcontroldistributedalgorithmthatdetermineshownodessharechannel,i.e.,determinewhennodecantransmitcommunicationaboutchannelsharingmustusechannelitself!noout-of-bandchannelforcoordinationCentralizedcontrolThereisacontroller135:DataLinkLayerIdealMultipleAccessProtocolBroadcastchannelofrateRbps1.whenonenodewantstotransmit,itcansendatrateR.2.whenMnodeswanttotransmit,eachcansendataveragerateR/M3.fullydecentralized:nospecialnodetocoordinatetransmissionsnosynchronizationofclocks,slots4.simple145:DataLinkLayerMACProtocols:ataxonomyThreebroadclasses:ChannelPartitioningdividechannelintosmaller“pieces”(timeslots,frequency,code)allocatepiecetonodeforexclusiveuseRandomAccesschannelnotdivided,allowcollisions“recover”fromcollisions“Takingturns”nodestaketurns,butnodeswithmoretosendcantakelongerturns155:DataLinkLayerChannelPartitioningMACprotocols:TDMATDMA:timedivisionmultipleaccess

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

channelspectrumdividedintofrequencybandseachstationassignedfixedfrequencybandunusedtransmissiontimeinfrequencybandsgoidleexample:6-stationLAN,1,3,4havepkt,frequencybands2,5,6idlefrequencybandstimeFDMcable175:DataLinkLayerRandomAccessProtocolsWhennodehaspackettosendtransmitatfullchanneldatarateR.noaprioricoordinationamongnodestwoormoretransmittingnodes?“collision”,randomaccessMACprotocolspecifies:howtodetectcollisionshowtorecoverfromcollisions(e.g.,viadelayedretransmissions)ExamplesofrandomaccessMACprotocols:slottedALOHAALOHACSMA,CSMA/CD,CSMA/CA185:DataLinkLayerSlottedALOHAAssumptions:allframessamesizetimedividedintoequalsizeslots(timetotransmit1frame)nodesstarttotransmitonlyslotbeginningnodesaresynchronizedif2ormorenodestransmitinslot,allnodesdetectcollisionOperation:whennodeobtainsfreshframe,transmitsinnextslotifnocollision:nodecansendnewframeinnextslotifcollision:noderetransmitsframeineachsubsequentslotwithprob.puntilsuccess195:DataLinkLayerSlottedALOHAProssingleactivenodecancontinuouslytransmitatfullrateofchannelhighlydecentralized:onlyslotsinnodesneedtobeinsyncsimpleConscollisions,wastingslotsidleslotsnodesmaybeabletodetectcollisioninlessthantimetotransmitpacketclocksynchronization205:DataLinkLayerSlottedAlohaefficiencysuppose:Nnodeswithmanyframestosend,eachtransmitsinslotwithprobabilitypprobthatgivennodehassuccessinaslot=p(1-p)N-1probthatanynodehasasuccess=Np(1-p)N-1

maxefficiency:findp*thatmaximizes

Np(1-p)N-1formanynodes,takelimitofNp*(1-p*)N-1asNgoestoinfinity,gives:Maxefficiency=1/e=.37Efficiency:long-run

fractionofsuccessfulslots

(manynodes,allwithmanyframestosend)Atbest:channelusedforusefultransmissions37%oftime!!215:DataLinkLayerPure(unslotted)ALOHAunslottedAloha:simpler,nosynchronizationwhenframefirstarrivestransmitimmediatelycollisionprobabilityincreases:framesentatt0collideswithotherframessentin[t0-1,t0+1]225:DataLinkLayerPureAlohaefficiencyP(successbygivennode)=P(nodetransmits).P(noothernodetransmitsin[p0-1,p0].P(noothernodetransmitsin[p0-1,p0]=p.(1-p)N-1.(1-p)N-1

=p.(1-p)2(N-1)

max(p)=1/(2e)=.18

evenworsethanslottedAloha!G=offeredload=Np0.51.01.52.00.10.20.30.4PureAlohaSlottedAlohaS=throughput=“goodput”(successrate)protocolconstrainseffectivechannelthroughput!235:DataLinkLayerCSMA(CarrierSenseMultipleAccess)CSMA:listenbeforetransmit:Ifchannelsensedidle:transmitentireframeIfchannelsensedbusy,defertransmission

humananalogy:don’tinterruptothers!245:DataLinkLayerCSMAcollisionscollisionscanstilloccur:propagationdelaymeanstwonodesmaynotheareachother’stransmissioncollision:entirepackettransmissiontimewastedspatiallayoutofnodesnote:roleofdistance&propagationdelayindeterminingcollisionprobability255:DataLinkLayerCSMA/CD(CollisionDetection)CSMA/CD:carriersensing,deferralasinCSMAcollisionsdetectedwithinshorttimecollidingtransmissionsaborted,reducingchannelwastagecollisiondetection:

easyinwiredLANs:measuresignalstrengths,comparetransmitted,receivedsignalsdifficultinwirelessLANs:receivedsignalstrengthoverwhelmedbylocaltransmissionstrength265:DataLinkLayerCSMA/CDcollisiondetection275:DataLinkLayer“TakingTurns”MACprotocolschannelpartitioningMACprotocols:sharechannelefficientlyandfairlyathighloadinefficientatlowload:delayinchannelaccess,1/Nbandwidthallocatedevenifonly1activenode!RandomaccessMACprotocolsefficientatlowload:singlenodecanfullyutilizechannelhighload:collisionoverhead“takingturns”protocolslookforbestofbothworlds!285:DataLinkLayer“TakingTurns”MACprotocolsPolling:

masternode“invites”slavenodestotransmitinturntypicallyusedwith“dumb”slavedevicesconcerns:pollingoverheadlatencysinglepointoffailure(master)masterslavespolldatadata295:DataLinkLayer“TakingTurns”MACprotocolsTokenpassing:controltokenpassedfromonenodetonextsequentially.tokenmessageconcerns:tokenoverheadlatencysinglepointoffailure(token)

Tdata(nothingtosend)T305:DataLinkLayer

SummaryofMACprotocolschannelpartitioning,bytime,frequencyorcodeTimeDivision,FrequencyDivisionrandomaccess(dynamic),ALOHA,S-ALOHA,CSMA,CSMA/CDCollisiondetection:easyinsometechnologies(wire),hardinothers(wireless)CSMA/CDusedinEthernetCSMA/CAusedin802.11takingturnspollingfromcentralsite,tokenpassingBluetooth,FDDI,IBMTokenRing315:DataLinkLayerMACAddressesandARP32-bitIPaddress:network-layeraddressusedtogetdatagramtodestinationIPsubnetMAC(orLANorphysicalorEthernet)address:

function:

getframefromoneinterfacetoanotherphysically-connectedinterface(samenetwork)48bitMACaddress(formostLANs)burnedinNICROM,alsosometimessoftwaresettable325:DataLinkLayerLANAddressesandARPEachadapteronLANhasuniqueLANaddressBroadcastaddress=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)335:DataLinkLayerLANAddress(more)MACaddressallocationadministeredbyIEEEmanufacturerbuysportionofMACaddressspace(toassureuniqueness)MACflataddress?portabilitycanmoveLANcardfromoneLANtoanotherIPhierarchicaladdressNOTportableaddressdependsonIPsubnettowhichnodeisattached345:DataLinkLayerARP: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

LAN3848AB355:DataLinkLayerARPprotocol: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-MACaddresspairinitsARPtableuntilinformationbecomesold(timesout)softstate:informationthattimesout(goesaway)unlessrefreshedARPis“plug-and-play”:nodescreatetheirARPtableswithoutinterventionfromnetadministrator365:DataLinkLayerAddressing:routingtoanotherLANR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D1211A74-29-9C-E8-FF-552188-B2-2F-54-1A-0FB2249-BD-D2-C7-56-2Awalkthrough:senddatagramfromAtoBviaRassumeAknowsB’sIPaddresstwoARPtablesinrouterR,oneforeachIPnetwork(LAN)375:DataLinkLayerAcreatesIPdatagramwithsourceA,destinationBAusesARPtogetR’sMACaddressfor10Acreateslink-layerframewithR'sMACaddressasdest,framecontainsA-to-BIPdatagramA’sNICsendsframeR’sNICreceivesframeRremovesIPdatagramfromEthernetframe,seesitsdestinedtoB,forwarditusingroutingtableRusesARPtogetB’sMACaddressRcreatesframecontainingA-to-BIPdatagramsendstoBR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D1211A74-29-9C-E8-FF-552188-B2-2F-54-1A-0FB2249-BD-D2-C7-56-2AThisisareallyimportantexample–makesureyouunderstand!385:DataLinkLayerEthernet“dominant”wiredLANtechnology:cheap$20forNICfirstwidelyusedLANtechnologysimpler,cheaperthantokenLANsandATMkeptupwithspeedrace:10Mbps–10Gbps

Metcalfe’sEthernetsketch395:DataLinkLayerStartopologybustopologypopularthroughmid90sallnodesinsamecollisiondomain(cancollidewitheachother)today:startopologyprevailsactiveswitchincentereach“spoke”runsa(separate)Ethernetprotocol(nodesdonotcollidewitheachother)switchbus:coaxialcablestar405:DataLinkLayerEthernetFrameStructureSendingadapterencapsulatesIPdatagram(orothernetworklayerprotocolpacket)inEthernetframePreamble:

7byteswithpattern10101010followedbyonebytewithpattern10101011usedtosynchronizereceiver,senderclockrates415:DataLinkLayerEthernetFrameStructure(more)Addresses:6bytesifadapterreceivesframewithmatchingdestinationaddress,orwithbroadcastaddress(egARPpacket),itpassesdatainframetonetworklayerprotocolotherwise,adapterdiscardsframeType:2B,indicateshigherlayerprotocol(mostlyIPbutotherspossible,e.g.,NovellIPX,AppleTalk)CRC:4B,checkedatreceiver,iferrorisdetected,frameisdroppedData:46B~1500B425:DataLinkLayer

ServicesmodelofEthernetConnectionless,unreliableservicesOnlyCRCcheck,nohandshaking,noretransmissionNoACKorNACKWhenaframefails,discarditandlefttheprocessingtouplayersEthernetusesbasebandtransmission,sendsadigitalsignaldirectlytothebroadcastchannelDifferentfromADSL,ModemManchesterencodingisused,fromuptodownrepresents1,fromdowntouprepresents0CRC+CSMA/CD435:DataLinkLayer

Ethernet:CSMA/CDalgorithmA:sensechannel,ifidlethen{ transmitandmonitorthechannel;Ifdetectanothertransmission//collisiondetection

then{abortandsendjamsignal;update#collisions;delayasrequiredbyexponentialbackoffalgorithm;gotoA}

else{donewiththeframe;setcollisionstozero}}else{waituntilongoingtransmissionisoverandgotoA}445:DataLinkLayerEthernet’sCSMA/CD(more)JamSignal:makesureallothertransmittersareawareofcollision;48bitsBittime:.1microsecfor10MbpsEthernet;

forK=1023,waittimeisabout50msec

ExponentialBackoff:

Goal:adaptretransmissionattemptstoestimatedcurrentloadheavyload:randomwaitwillbelongerfirstcollision:chooseKfrom{0,1};delayisK*512bittransmissiontimesaftersecondcollision:chooseKfrom{0,1,2,3}…aftertencollisions,chooseKfrom{0,1,2,3,4,…,1023}455:DataLinkLayerCSMA/CDefficiencyTprop=maxpropdelaybetween2nodesinLANttrans=timetotransmitmax-sizeframeefficiencygoesto1astpropgoesto0asttransgoestoinfinitybetterperformancethanALOHA:andsimple,cheap,decentralized!465:DataLinkLayer802.3EthernetStandards:Link&PhysicalLayersmanydifferentEthernetstandardscommonMACprotocolandframeformatdifferentspeeds:2Mbps,10Mbps,100Mbps,1Gbps,10Gbpsdifferentphysicallayermedia:fiber,cableapplicationtransportnetworklinkphysicalMACprotocolandframeformat100BASE-TX100BASE-T4100BASE-FX100BASE-T2100BASE-SX100BASE-BXfiberphysicallayercopper(twisterpair)physicallayer475:DataLinkLayerManchesterencodingusedin10BaseTeachbithasatransitionallowsclocksinsendingandreceivingnodestosynchronizetoeachothernoneedforacentralized,globalclockamongnodes!Hey,thisisphysical-layerstuff!485:DataLinkLayerHubs…physical-layer(“dumb”)repeaters:bitscominginonelinkgooutallotherlinksatsamerateallnodesconnectedtohubcancollidewithoneanothernoframebufferingnoCSMA/CDathub:hostNICsdetectcollisionstwistedpairhub495:DataLinkLayerSwitchlink-layerdevice:smarterthanhubs,takeactiverolestore,forwardEthernetframesexamineincomingframe’sMACaddress,selectivelyforwardframetoone-or-moreoutgoinglinkswhenframeistobeforwardedonsegment,usesCSMA/CDtoaccesssegmenttransparenthostsareunawareofpresenceofswitchesplug-and-play,self-learningswitchesdonotneedtobeconfigured505:DataLinkLayerSwitch:allowsmultiplesimultaneoustransmissionshostshavededicated,directconnectiontoswitchswitchesbufferpacketsEthernetprotocolusedoneachincominglink,butnocollisions;fullduplexeachlinkisitsowncollisiondomainswitching:

A-to-A’andB-to-B’simultaneously,withoutcollisionsnotpossiblewithdumbhubAA’BB’CC’switchwithsixinterfaces(1,2,3,4,5,6)

123456515:DataLinkLayerSwitchTableQ: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)

123456525:DataLinkLayerSwitch:self-learningswitch

learnswhichhostscanbereachedthroughwhichinterfaceswhenframereceived,switch“l(fā)earns”locationofsender:incomingLANsegmentrecordssender/locationpairinswitchtableAA’BB’CC’123456AA’Source:ADest:A’MACaddrinterfaceTTLSwitchtable(initiallyempty)A160535:DataLinkLayerSwitch:framefiltering/forwardingWhenframereceived:

1.recordlinkassociatedwithsendinghost2.indexswitchtableusingMACdestaddress3.ifentryfoundfordestination

then{ifdestonsegmentfromwhichframearrived

thendroptheframe

elseforwardtheframeoninterfaceindicated

}

elseflood

forwardonallbuttheinterfaceonwhichtheframearrived545:DataLinkLayer

BridgeSelf-learningAbridgehasself-learningabilityThebridgetableisbuiltautomatically,dynamicallyandautonomously—withoutanyinterventionfromtheadministratororconfigurationprotocolSelf-learningprocedure:ThebridgetableisinitiallyemptyWhenaframearrivesononeinterface,thebridgeforwardsittoallotherinterfaces.RemembertheLANaddress,inputinterfacenumberandtimestamp.Ifeverynodeeventuallysendsaframe,everynodewillgetrecordedinthetable:(address,interfaces,time)Whenaframearrivesandthedest.Addressisinthetable,forwardittoappropriateinterfaceIfnoframereceivedaftersometime,deletecorrespondingrecord555:DataLinkLayerSelf-learning,forwarding:AA’BB’CC’123456AA’Source:ADest:A’MACaddrinterfaceTTLSwitchtable(initiallyempty)A160AA’AA’AA’AA’AA’framedestinationunknown:floodA’AdestinationAlocationknown:A’460selectivesend565:DataLinkLayer

BridgeSelf-learning:exampleSupposeCsendsframetoDandDrepliesbackwithframetoCCsendsframe,bridgehasnoinfoaboutD,sofloodstobothLANs

bridgenotesthatCisonport1frameignoredonoriginalLANframereceivedbyD575:DataLinkLayerInterconnectingswitchesswitchescanbeconnectedtogetherABQ:sendingfromAtoG-howdoesS1knowtoforwardframedestinedtoGviaS4andS3?A:selflearning!(worksexactlythesameasinsingle-switchcase!)S1CDEFS2S4S3HIG585:DataLinkLayerSelf-learningmulti-switchexampleSupposeCsendsframetoI,IrespondstoCQ:showswitchtablesandpacketforwardinginS1,S2,S3,S4

ABS1CDEFS2S4S3HIG12595:DataLinkLayerInstitutionalnetworktoexternalnetworkrouterIPsubnetmailserverwebserver605:DataLinkLayerSwitchesvs.Routersbothstore-and-forwarddevicesrouters:networklayerdevices(examinenetworklayerheaders)switchesarelinklayerdevicesroutersmaintainroutingtables,implementroutingalgorithmsswitchesmaintainswitchtables,implementfiltering,learningalgorithms

615:DataLinkLayerVLANs:motivationWhathappensif:CSusermovesofficetoEE,butwantsconnecttoCSswitch?singlebroadcastdomain:alllayer-2broadcasttraffic(ARP,DHCP)crossesentireLAN(security/privacy,efficiencyissues)eachlowestlevelswitchhasonlyfewportsinuseComputerScienceElectricalEngineeringComputerEngineeringWhat’swrongwiththispicture?625:DataLinkLayerVLANsPort-basedVLAN:switchportsgrouped(byswitchmanagementsoftware)sothatsinglephysicalswitch……Switch(es)supportingVLANcapabilitiescanbeconfiguredtodefinemultiplevirtualLANSoversinglephysicalLANinfrastructure.VirtualLocalAreaNetwork189161027…ElectricalEngineering(VLANports1-8)ComputerScience(VLANports9-15)15…ElectricalEngineering(VLANports1-8)ComputerScience(VLANports9-16)…operatesasmultiplevirtualswitches635:DataLinkLayerPort-basedVLAN189161027…ElectricalEngineering(VLANports1-8)ComputerScience(VLANports9-15)15…trafficisolation:framesto/fromports1-8canonlyreachports1-8canalsodefineVLANbasedonMACaddressesofendpoints,ratherthanswitchportdynamicmembership:portscanbedynamicallyassignedamongVLANsrouterforwardingbetweenVLANS:doneviarouting(justaswithseparateswitches)inpracticevendorssellcombinedswitchesplusrouters645:DataLinkLayerVLANSspanningmultipleswitchestrunkport:carriesframesbetweenVLANSdefinedovermultiplephysicalswitchesframesforwardedwithinVLANbetweenswitchescan’tbevanilla802.1frames(mustcarryVLANIDinfo)802.1qprotocoladds/removedadditionalheaderfieldsforframesforwardedbetweentrunkports1891027…ElectricalEngineering(VLANports1-8)ComputerScience(VLANports9-15)15…273Ports2,3,5belongtoEEVLANPorts4,6,7,8belongtoCSVLAN5468161655:DataLinkLayerType2-byteTagProtocolIdentifier(value:81-00)TagControlInformation(12bitVLANIDfield,3bitpriorityfieldlikeIPTOS)

RecomputedCRC

802.1QVLANframeformat802.1frame802.1Qframe665:DataLinkLayerPointtoPointDataLinkControlonesender,onereceiver,onelink:easierthanbroadcastlink:noMediaAccessControlnoneedforexplicitMACaddressinge.g.,dialuplink,ISDNlinepopularpoint-to-pointDLCprotocols:PPP(point-to-pointprotocol)HDLC:Highleveldatalinkcontrol(Datalinkusedtobeconsidered“highlayer”inprotocolstack!675:DataLinkLayerPPPDesignRequirements[RFC1557]packetframing:encapsulationofnetwork-layerdatagramindatalinkframecarrynetworklayerdataofanynetworklayerprotocol(notjustIP)atsametimeabilitytodemultiplexupwardsbittransparency:mustcarryanybitpatterninthedatafielderrordetection(nocorrection)connectionliveness:detect,signallinkfailuretonetworklayernetworklayeraddressnegotiation:endpointcanlearn/configureeachother’snetworkaddress685:DataLinkLayerPPPnon-requirementsnoerrorcorrection/recoverynoflowcontroloutoforderdeliveryOKnoneedtosupportmultipointlinks(e.g.,polling)Errorrecovery,flowcontrol,datare-orderingallrelegatedtohigherlayers!695:DataLinkLayerPPPDataFrameFlag:delimiter(framing)Address:doesnothing(onlyoneoption)Control:doesnothing;inthefuturepossiblemultiplecontrolfieldsProtocol:upperlayerprotocoltowhichframedelivered(eg,PPP-LCP,IP,IPCP,etc)705:DataLinkLayerPPPDataFrameinfo:upperlayerdatabeingcarriedcheck:cyclicredundancycheckforerrordetection715:DataLinkLayerByteStuffing

“datatransparency”requirement:datafieldmustbeallowedtoincludeflagpattern<01111110>Q:isreceived<01111110>dataorflag?Sender:adds(“stuffs”)extra<01111110>byteaftereach<01111110>databyteReceiver:

two01111110bytesinarow:discardfirstbyte,continuedatareceptionsingle01111110:flagbyte725:DataLinkLayerByteStuffingflagbytepatternindatatosendflagbytepatternplusstuffedbyteintransmitteddata735:DataLinkLayerPPPDataControlProtocolBeforeexchangingnetwork-layerdata,datalinkpeersmustconfigurePPPlink(max.framelength,authentication)learn/configurenetwork

layerinformationforIP:carryIPControlProtocol(IPCP)msgs(protocolfield:8021)toconfigure/learnIPaddress745:DataLinkLayerVirtualizationofnetworksVirtualizationofresources:powerfulabstractioninsystemsengineering:computingexamples:virtualmemory,virtualdevicesVirtualmachines:e.g.,javaIBMVMosfrom1960’s/70’slayeringofabstractions:don’tsweatthedetailsofthelowerlayer,onlydealwithlowerlayersabstractly755:DataLinkLayerTheInternet:virtualizingnetw