计算机网络理论教学资料 chapter5z

DataLinkLayer5-1ComputerNetworking:ATopDownApproach

5thedition.

JimKurose,KeithRoss

Addison-Wesley,April2009.

ComputerNetworksDr.GuifengZheng(郑贵锋)gfzheng@DataLinkLayer5-2Chapter5:TheDataLinkLayerOurgoals:

understandprinciplesbehinddatalinklayerservices:errordetection,correctionsharingabroadcastchannel:multipleaccesslinklayeraddressingreliabledatatransfer,flowcontrol:done!instantiationandimplementationofvariouslinklayertechnologiesDataLinkLayer5-3LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9AdayinthelifeofawebrequestDataLinkLayer5-4LinkLayer:IntroductionTerminology:hostsandroutersarenodescommunicationchannelsthatconnectadjacentnodesalongcommunicationpatharelinkswiredlinkswirelesslinksLANslayer-2packetisaframe,

encapsulatesdatagramdata-linklayerhasresponsibilityoftransferringdatagramfromonenodetophysicallyadjacentnodeoveralinkDataLinkLayer5-5Linklayer:contextdatagramtransferredbydifferentlinkprotocolsoverdifferentlinks:e.g.,Ethernetonfirstlink,framerelayonintermediatelinks,802.11onlastlinkeachlinkprotocolprovidesdifferentservicese.g.,mayormaynotproviderdtoverlinktransportationanalogytripfromPrincetontoLausannelimo:PrincetontoJFKplane:JFKtoGenevatrain:GenevatoLausannetourist=datagramtransportsegment=communicationlinktransportationmode=linklayerprotocoltravelagent=routingalgorithmDataLinkLayer5-6LinkLayerServicesframing,linkaccess:

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

pacingbetweenadjacentsendingandreceivingnodeserrordetection:

errorscausedbysignalattenuation,noise.receiverdetectspresenceoferrors:signalssenderforretransmissionordropsframeerrorcorrection:

receiveridentifiesandcorrectsbiterror(s)withoutresortingtoretransmissionhalf-duplexandfull-duplexwithhalfduplex,nodesatbothendsoflinkcantransmit,butnotatsametimeDataLinkLayer5-8Whereisthelinklayerimplemented?ineachandeveryhostlinklayerimplementedin“adaptor”(akanetworkinterfacecardNIC)Ethernetcard,PCMCIcard,802.11cardimplementslink,physicallayerattachesintohost’ssystembusescombinationofhardware,software,firmwarecontrollerphysicaltransmissioncpumemoryhostbus(e.g.,PCI)networkadaptercardhostschematicapplicationtransportnetworklinklinkphysicalDataLinkLayer5-9AdaptorsCommunicatingsendingside:encapsulatesdatagraminframeaddserrorcheckingbits,rdt,flowcontrol,etc.receivingsidelooksforerrors,rdt,flowcontrol,etcextractsdatagram,passestoupperlayeratreceivingsidecontrollercontrollersendinghostreceivinghostdatagramdatagramdatagramframeDataLinkLayer5-10LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection

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

Errordetectionnot100%reliable!protocolmaymisssomeerrors,butrarelylargerEDCfieldyieldsbetterdetectionandcorrectionotherwiseDataLinkLayer5-12ParityCheckingSingleBitParity:DetectsinglebiterrorsTwoDimensionalBitParity:Detectandcorrectsinglebiterrors00DataLinkLayer5-13Internetchecksum(review)Sender:treatsegmentcontentsassequenceof16-bitintegerschecksum:addition(1’scomplementsum)ofsegmentcontentssenderputschecksumvalueintoUDPchecksumfieldReceiver:computechecksumofreceivedsegmentcheckifcomputedchecksumequalschecksumfieldvalue:NO-errordetectedYES-noerrordetected.Butmaybeerrorsnonetheless?

Goal:detect“errors”(e.g.,flippedbits)intransmittedpacket(note:usedattransportlayeronly)DataLinkLayer5-14Checksumming: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)DataLinkLayer5-15CRCExampleWant:D.2rXORR=nGequivalently:D.2r=nGXORRequivalently:

ifwedivideD.2rbyG,wantremainderRR=remainder[]D.2rGDataLinkLayer5-16LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9AdayinthelifeofawebrequestDataLinkLayer5-17MultipleAccessLinksandProtocolsTwotypesof“links”:point-to-pointPPPfordial-upaccesspoint-to-pointlinkbetweenEthernetswitchandhostbroadcast(sharedwireormedium)old-fashionedEthernetupstreamHFC802.11wirelessLANsharedwire(e.g.,cabledEthernet)sharedRF(e.g.,802.11WiFi)sharedRF(satellite)humansatacocktailparty(sharedair,acoustical)DataLinkLayer5-18MultipleAccessprotocolssinglesharedbroadcastchanneltwoormoresimultaneoustransmissionsbynodes:interferencecollisionifnodereceivestwoormoresignalsatthesametimemultipleaccessprotocoldistributedalgorithmthatdetermineshownodessharechannel,i.e.,determinewhennodecantransmitcommunicationaboutchannelsharingmustusechannelitself!noout-of-bandchannelforcoordinationDataLinkLayer5-19IdealMultipleAccessProtocolBroadcastchannelofrateRbps1.whenonenodewantstotransmit,itcansendatrateR.2.whenMnodeswanttotransmit,eachcansendataveragerateR/M3.fullydecentralized:nospecialnodetocoordinatetransmissionsnosynchronizationofclocks,slots4.simpleDataLinkLayer5-20MACProtocols:ataxonomyThreebroadclasses:ChannelPartitioningdividechannelintosmaller“pieces”(timeslots,frequency,code)allocatepiecetonodeforexclusiveuseRandomAccesschannelnotdivided,allowcollisions“recover”fromcollisions“Takingturns”nodestaketurns,butnodeswithmoretosendcantakelongerturnsDataLinkLayer5-21ChannelPartitioningMACprotocols:TDMATDMA:timedivisionmultipleaccess

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

channelspectrumdividedintofrequencybandseachstationassignedfixedfrequencybandunusedtransmissiontimeinfrequencybandsgoidleexample:6-stationLAN,1,3,4havepkt,frequencybands2,5,6idlefrequencybandstimeFDMcableDataLinkLayer5-23RandomAccessProtocolsWhennodehaspackettosendtransmitatfullchanneldatarateR.noaprioricoordinationamongnodestwoormoretransmittingnodes➜“collision”,randomaccessMACprotocolspecifies:howtodetectcollisionshowtorecoverfromcollisions(e.g.,viadelayedretransmissions)ExamplesofrandomaccessMACprotocols:slottedALOHAALOHACSMA,CSMA/CD,CSMA/CADataLinkLayer5-24SlottedALOHAAssumptions:allframessamesizetimedividedintoequalsizeslots(timetotransmit1frame)nodesstarttotransmitonlyslotbeginningnodesaresynchronizedif2ormorenodestransmitinslot,allnodesdetectcollisionOperation:whennodeobtainsfreshframe,transmitsinnextslotifnocollision:nodecansendnewframeinnextslotifcollision:noderetransmitsframeineachsubsequentslotwithprob.puntilsuccessDataLinkLayer5-25SlottedALOHAProssingleactivenodecancontinuouslytransmitatfullrateofchannelhighlydecentralized:onlyslotsinnodesneedtobeinsyncsimpleConscollisions,wastingslotsidleslotsnodesmaybeabletodetectcollisioninlessthantimetotransmitpacketclocksynchronizationDataLinkLayer5-26SlottedAlohaefficiencysuppose:Nnodeswithmanyframestosend,eachtransmitsinslotwithprobabilitypprobthatgivennodehassuccessinaslot=p(1-p)N-1probthatanynodehasasuccess=Np(1-p)N-1maxefficiency: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!!DataLinkLayer5-27Pure(unslotted)ALOHAunslottedAloha:simpler,nosynchronizationwhenframefirstarrivestransmitimmediatelycollisionprobabilityincreases:framesentatt0collideswithotherframessentin[t0-1,t0+1]DataLinkLayer5-28PureAlohaefficiencyP(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)

…choosingoptimumpandthenlettingn->infty...

=1/(2e)=.18

evenworsethanslottedAloha!DataLinkLayer5-29CSMA(CarrierSenseMultipleAccess)CSMA:listenbeforetransmit:Ifchannelsensedidle:transmitentireframeIfchannelsensedbusy,defertransmission

humananalogy:don’tinterruptothers!DataLinkLayer5-30CSMAcollisionscollisionscanstilloccur:propagationdelaymeanstwonodesmaynotheareachother’stransmissioncollision:entirepackettransmissiontimewastedspatiallayoutofnodesnote:roleofdistance&propagationdelayindeterminingcollisionprobabilityDataLinkLayer5-31CSMA/CD(CollisionDetection)CSMA/CD:carriersensing,deferralasinCSMAcollisionsdetectedwithinshorttimecollidingtransmissionsaborted,reducingchannelwastagecollisiondetection:

easyinwiredLANs:measuresignalstrengths,comparetransmitted,receivedsignalsdifficultinwirelessLANs:receivedsignalstrengthoverwhelmedbylocaltransmissionstrengthhumananalogy:thepoliteconversationalistDataLinkLayer5-32CSMA/CDcollisiondetectionDataLinkLayer5-33“TakingTurns”MACprotocolschannelpartitioningMACprotocols:sharechannelefficientlyandfairlyathighloadinefficientatlowload:delayinchannelaccess,1/Nbandwidthallocatedevenifonly1activenode!randomaccessMACprotocolsefficientatlowload:singlenodecanfullyutilizechannelhighload:collisionoverhead“takingturns”protocolslookforbestofbothworlds!DataLinkLayer5-34“TakingTurns”MACprotocolsPolling:

masternode“invites”slavenodestotransmitinturntypicallyusedwith“dumb”slavedevicesconcerns:pollingoverheadlatencysinglepointoffailure(master)masterslavespolldatadataDataLinkLayer5-35“TakingTurns”MACprotocolsTokenpassing:controltokenpassedfromonenodetonextsequentially.tokenmessageconcerns:tokenoverheadlatencysinglepointoffailure(token)

Tdata(nothingtosend)TDataLinkLayer5-36SummaryofMACprotocolschannelpartitioning,bytime,frequencyorcodeTimeDivision,FrequencyDivisionrandomaccess(dynamic),ALOHA,S-ALOHA,CSMA,CSMA/CDcarriersensing:easyinsometechnologies(wire),hardinothers(wireless)CSMA/CDusedinEthernetCSMA/CAusedin802.11takingturnspollingfromcentralsite,tokenpassingBluetooth,FDDI,IBMTokenRingDataLinkLayer5-37LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9AdayinthelifeofawebrequestDataLinkLayer5-38MACAddressesandARP32-bitIPaddress:network-layeraddressusedtogetdatagramtodestinationIPsubnetMAC(orLANorphysicalorEthernet)address:

function:

getframefromoneinterfacetoanotherphysically-connectedinterface(samenetwork)48bitMACaddress(formostLANs)burnedinNICROM,alsosometimessoftwaresettableDataLinkLayer5-39LANAddressesandARPEachadapteronLANhasuniqueLANaddressBroadcastaddress=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-53LAN(wiredorwireless)DataLinkLayer5-40LANAddress(more)MACaddressallocationadministeredbyIEEEmanufacturerbuysportionofMACaddressspace(toassureuniqueness)analogy:(a)MACaddress:likeSocialSecurityNumber(b)IPaddress:likepostaladdressMACflataddress➜portabilitycanmoveLANcardfromoneLANtoanotherIPhierarchicaladdressNOTportableaddressdependsonIPsubnettowhichnodeisattachedDataLinkLayer5-41ARP: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-53LAN3848DataLinkLayer5-42ARPprotocol: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”:nodescreatetheirARPtableswithoutinterventionfromnetadministratorDataLinkLayer5-43walkthrough:senddatagramfromAtoBviaR.focusonaddressing-atbothIP(datagram)andMAClayer(frame)assumeAknowsB’sIPaddressassumeAknowsB’sMACaddress(how?)assumeAknowsIPaddressoffirsthoprouter,R(how?)assumeAknowsMACaddressoffirsthoprouterinterface(how?)Addressing:routingtoanotherLANR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D121174-29-9C-E8-FF-55A2249-BD-D2-C7-56-2A2188-B2-2F-54-1A-0FBDataLinkLayer5-44Addressing:routingtoanotherLANR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D121174-29-9C-E8-FF-55AIPEthPhyIPsrc:11IPdest:22AcreatesIPdatagramwithIPsourceA,destinationBAcreateslink-layerframewithR'sMACaddressasdest,framecontainsA-to-BIPdatagramMACsrc:74-29-9C-E8-FF-55MACdest:E6-E9-00-17-BB-4B2249-BD-D2-C7-56-2A2188-B2-2F-54-1A-0FBDataLinkLayer5-45Addressing:routingtoanotherLANR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D121174-29-9C-E8-FF-55AIPEthPhyframesentfromAtoRIPsrc:11IPdest:22MACsrc:74-29-9C-E8-FF-55MACdest:E6-E9-00-17-BB-4BIPEthPhyframereceivedatR,datagramremoved,passeduptoIP2249-BD-D2-C7-56-2A2188-B2-2F-54-1A-0FBDataLinkLayer5-46Addressing:routingtoanotherLANR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D121174-29-9C-E8-FF-552249-BD-D2-C7-56-2A2188-B2-2F-54-1A-0FBAIPsrc:11IPdest:22RforwardsdatagramwithIPsourceA,destinationBRcreateslink-layerframewithB'sMACaddressasdest,framecontainsA-to-BIPdatagramMACsrc:1A-23-F9-CD-06-9BMACdest:49-BD-D2-C7-56-2AIPEthPhyIPEthPhyDataLinkLayer5-47Addressing:routingtoanotherLANR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D121174-29-9C-E8-FF-552249-BD-D2-C7-56-2A2188-B2-2F-54-1A-0FBARforwardsdatagramwithIPsourceA,destinationBRcreateslink-layerframewithB'sMACaddressasdest,framecontainsA-to-BIPdatagramIPsrc:11IPdest:22MACsrc:1A-23-F9-CD-06-9BMACdest:49-BD-D2-C7-56-2AIPEthPhyIPEthPhyDataLinkLayer5-48Addressing:routingtoanotherLANR1A-23-F9-CD-06-9B2010E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D121174-29-9C-E8-FF-552249-BD-D2-C7-56-2A2188-B2-2F-54-1A-0FBARforwardsdatagramwithIPsourceA,destinationBRcreateslink-layerframewithB'sMACaddressasdest,framecontainsA-to-BIPdatagramIPsrc:11IPdest:22MACsrc:1A-23-F9-CD-06-9BMACdest:49-BD-D2-C7-56-2AIPEthPhyDataLinkLayer5-49LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-LayerAddressing5.5Ethernet5.6Link-layerswitches5.7PPP5.8Linkvirtualization:MPLS5.9AdayinthelifeofawebrequestDataLinkLayer5-50Ethernet“dominant”wiredLANtechnology:cheap$20forNICfirstwidelyusedLANtechnologysimpler,cheaperthantokenLANsandATMkeptupwithspeedrace:10Mbps–10GbpsMetcalfe’sEthernetsketchDataLinkLayer5-51Startopologybustopologypopularthroughmid90sallnodesinsamecollisiondomain(cancollidewitheachother)today:startopologyprevails盛行activeswitchincentereach“spoke”runsa(separate)Ethernetprotocol(nodesdonotcollidewitheachother)switchbus:coaxialcable同轴电缆starDataLinkLayer5-52EthernetFrameStructureSendingadapterencapsulatesIPdatagram(orothernetworklayerprotocolpacket)inEthernetframePreamble前导:

7byteswithpattern10101010followedbyonebytewithpattern10101011usedtosynchronizereceiver,senderclockratesDataLinkLayer5-53EthernetFrameStructure(more)Addresses:6bytesifadapterreceivesframewithmatchingdestinationaddress,orwithbroadcastaddress(e.g.ARPpacket),itpassesdatainframetonetworklayerprotocolotherwise,adapterdiscardsframeType:indicateshigherlayerprotocol(mostlyIPbutotherspossible,e.g.,NovellIPX,AppleTalk)CRC:checkedatreceiver,iferrorisdetected,frameisdroppedDataLinkLayer5-54Ethernet:Unreliable,connectionlessconnectionless:NohandshakingbetweensendingandreceivingNICsunreliable:receivingNICdoesn’tsendacksornackstosendingNICstreamofdatagramspassedtonetworklayercanhavegaps(missingdatagrams)gapswillbefilledifappisusingTCPotherwise,appwillseegapsEthernet’sMACprotocol:unslottedCSMA/CDDataLinkLayer5-55EthernetCSMA/CDalgorithm1.NICreceivesdatagramfromnetworklayer,createsframe2.IfNICsenseschannelidle,startsframetransmissionIfNICsenseschannelbusy,waitsuntilchannelidle,thentransmits3.IfNICtransmitsentireframewithoutdetectinganothertransmission,NICisdonewithframe!4.IfNICdetectsanothertransmissionwhiletransmitting,abortsandsendsjamsignal5.Afteraborting,NICentersexponentialbackoff指数补偿:aftermthcollision,NICchoosesKatrandomfrom

{0,1,2,…,2m-1}.NICwaitsK·512bittimes,returnstoStep2

DataLinkLayer5-56Ethernet’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}See/interactwithJavaappletonAWLWebsite:highlyrecommended!/aw_kurose_network_5/111/28536/7305312.cw/index.htmlDataLinkLayer5-57CSMA/CDefficiencytprop=maxpropdelaybetween2nodesinLANttrans=timetotransmitmax-sizeframeefficiencygoesto1astpropgoesto0asttransgoestoinfinitybetterperformancethanALOHA:andsimple,cheap,decentralized!DataLinkLayer5-58802.3EthernetStandards:Link&PhysicalLayersmanydifferentEthernetstandardscommonMACprotocolandframeformatdifferentspeeds:2Mbps,10Mbps,100Mbps,1Gbps,10Gbpsdifferentphysicallayermedia:fiber,cableapplicationtransportnetworklinkphysicalMACprotocolandframeformat100BASE-TX100BASE-T4100BASE-FX100BASE-T2100BASE-SX100BASE-BXfiberphysicallayercopper(twisterpair)physicallayerDataLinkLayer5-59Manchesterencodingusedin10BaseTeachbithasatransitionallowsclocksinsendingandreceivingnodestosynchronizetoeachothernoneedforacentralized,globalclockamongnodes!Hey,thisisphysical-layerstuff!originaldataXORclock=Manchestervalue 0 0 0

0 1 1

1 0 1

1 1 0DataLinkLayer5-60DataLinkLayer5-61LinkLayer5.1Introductionandservices5.2Errordetectionandcorrection5.3Multipleaccessprotocols5.4Link-layerAddressing5.5Ethernet5.6Link-layerswitches,LANs,VLANs5.7PPP5.8Linkvirtualization:MPLS5.9AdayinthelifeofawebrequestDataLinkLayer5-62Hubs…physical-layer(“dumb”)repeaters:bitscominginonelinkgooutallotherlinksatsamerateallnodesconnectedtohubcancollidewithoneanothernoframebufferingnoCSMA/CDathub:hostNICsdetectcollisionstwistedpairhubDataLinkLayer5-63Switchlink-layerdevice:smarterthanhubs,takeactiverolestore,forwardEthernetframesexamineincomingframe’sMACaddress,selectivelyforwardframetoone-or-moreoutgoinglinkswhenframeistobeforwardedonsegment,usesCSMA/CDtoaccesssegmenttransparenthostsareunawareofpresenceofswitchesplug-and-play,self-learningswitchesdonotneedtobeconfiguredDataLinkLayer5-64Switch:allowsmultiplesimultaneoustransmissionshostshavededicated,directconnectiontoswitchswitchesbufferpacketsEthernetprotocolusedoneachincominglink,butnocollisions;fullduplexeachlinkisitsowncollisiondomainswitching:

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

123456DataLinkLayer5-65SwitchTableQ: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)

123456DataLinkLayer5-66Switch:self-learningswitch

learnswhichhostscanbereachedthroughwhichinterfaceswhenframereceived,switch“learns”locationofsender:incomingLANsegmentrecordssender/locationpairinswitchtableAA’BB’CC’123456AA’Source:ADest:A’MACaddrinterfaceTTLSwitchtable(initiallyempty)A160DataLinkLayer5-67Switch:framefiltering/forwardingWhenframereceived:

1.recordlinkassociatedwithsendinghost2.indexswitchtableusingMACdestaddress3.if

entryfoundfordestination

then{

if

destonsegmentfromwhichframearrived

thendroptheframe

elseforwardtheframeoninterfaceindicated

}

elseflood

forwardonallbuttheinterfaceonwhichtheframearrivedDataLinkLayer5-68Self-learning,forwarding:exampleAA’BB’CC’123456AA’Source:ADest:A’MACaddrinterfaceTTLSwitchtable(initiallyempty)A160AA’AA’AA’AA’AA’framedestinationunknown:floodA’AdestinationAlocationknown:A’460selectivesendDataLinkLayer5-69InterconnectingswitchesswitchescanbeconnectedtogetherABQ:sendingfromAtoG-howdoesS1knowtoforwardframedestinedtoGviaS4andS3?A:selflearning!(worksexactlythesameasinsingle-switchcase!)S1CDEFS2S4S3HIGDataLinkLayer5-70Self-learningmulti-switchexampleSupposeCsendsframetoI,IrespondstoCQ:showswitchtablesandpacketforwardinginS1,S2,S3,S4

ABS1CDEFS2S4S3HIG12DataLinkLayer5-71InstitutionalnetworktoexternalnetworkrouterIPsubnetmailserverwebserverDataLinkLayer5-72Switchesvs.Routersbothstore-and-forwarddevicesrouters:network-layerdevices(examinenetwork-layerheaders)switchesarelink-layerdevices(examinelink-layerheaders)routersmaintainroutingtables,implementroutingalgorithmsswitchesmaintainswitchtables,implementfiltering,learningalgorithms

applicationtransportnetworklinkphysicalnetworklinkphysicallinkphysicalswitchdatagramapplicationtransportnetworklinkphysicalframeframeframedatagramDataLinkLayer5-73VLANs:motivationWhathappensif:CSusermovesofficetoEE,butwantsconnecttoCSswitch?singlebroadcastdomain:alllayer-2broadcasttraffic(ARP,DHCP)crossesentireLAN(security/privacy,efficiencyissues)eachlowestlevelswitchhasonlyfewportsinuseComputerScienceElectricalEngineeringComputerEngineeringWhat’swrongwiththispicture?DataLinkLayer5-74VLANsPort-basedVLAN:switchportsgrouped(byswitchmanagementsoftware)sothatsinglephysicalswitch……Switch(es)supportingVLANcapabilitiescanbeconfiguredtodefinemultiplevirtualLANSoversinglephysicalLANinfrastructure.VirtualLocalAreaNetwork189161027…ElectricalEngineering(VLANports1-8)ComputerScience(VLANports9-15)15…ElectricalEngineering(VLANports1-8)ComputerScience(VLANports9-16)…operatesasmultiplevirtualswitchesDataLinkLayer5-75Port-basedVLAN189161027…ElectricalEngineering(VLANports1-8)ComputerScience(VLANports9-15)15…traf