哈爾濱工業(yè)大學(xué)計算機(jī)網(wǎng)絡(luò)2HITLecture2

AdvancedComputerNetworkLecture2:TheDataLinkLayerYangQinDepartmentofComputerScienceShenzhenGraduateSchoolHarbinInstituteofTechnologyTheDataLinkLayera)Problems–Howtotransferdatacorrectlyonainstablelinkb)Node：Hostandrouterinthenetworkc)Link：Thechannelconnectstheadjacentnodesd)TheDATALINKLAYERprovidesaccesstothenetworkingmediaandphysicaltransmissionacrossthemedia,whichenablesthedatatolocateitsintendeddestination.e)Layer2protocolsdefinetheformatofdataexchangedonalink,anddefinetheactionofthetwonodesonthelinkTheDATALINKLAYERhandleserrornotification,networktopology,andflowcontrol.f)TheDataLinkLayerForeachlimitationinLayer1,Layer2hasasolution.a)Layer1cannotcommunicatewiththeupper-levellayers;Layer2doesthatwithLogicalLinkControl(LLC).Layer1cannotnameoridentifycomputers;Layer2usesanaddressing(ornaming)process.Layer1canonlydescribestreamsofbits;Layer2usesframingtoorganizeorgroupthebits.Layer1cannotdecidewhichcomputerwilltransmitbinarydatafromagroupthatarealltryingtotransmitatthesametime.Layer2usesasystemcalledMediaAccessControl(MAC).b)a)a)Layer2Communications

‘endtoend’and‘pointtopoint’–endtoendcommunications:?Datacommunicationsonapathbetweenthesourcenodeandthedestinationnode.Thepathpossiblycomprisesmultiplelinks–pointtopointcommunications:?Datacommunicationsonalinkconnectingtheadjacentnodes

Layer2concernsaboutpointtopointcommunications,notendtoendcommunicationsTransmissionMethodsinLayer2LANdatatransmissionsfallinto3classifications:

unicast--asinglepacketissentfromthesourcetoasingledestinationonanetwork單播

multicast--consistsofasingledatapacketthatissenttoaspecificsubsetofnodesonthenetwork.組播

broadcast--consistsofasingledatapacketthatistransmittedtoallnodesonthenetwork.廣播DataLinkLayerDesignIssues?ServicesProvidedtotheNetworkLayer提供服務(wù)給網(wǎng)絡(luò)層?Framing成幀?ErrorControl誤差控制?FlowControl流控制FunctionsoftheDataLinkLayer?????Provideserviceinterfacetothenetworklayer提供網(wǎng)絡(luò)層的服務(wù)接口Dealingwithtransmissionerrors處理傳輸誤差Regulatingdataflow?調(diào)節(jié)數(shù)據(jù)流SlowreceiversnotswampedbyfastsendersFunctionsoftheDataLinkLayer(2)Relationshipbetweenpacketsandframes.ServicesProvidedtoNetworkLayer(a)Virtualcommunication.(b)Actualcommunication.ServicesProvidedtoNetworkLayer(2)Placementofthedatalinkprotocol.Framing(1):charactercountmethodAcharacterstream.(a)Withouterrors.(b)Withoneerror.Trouble:countcanbegarbledbyatransmissionerror,thengetoutofsynchronization.Framing(2)(a)Aframedelimitedbyflagbytes:withspecialbytes.(b)Fourexamplesofbytesequencesbeforeandafterstuffing.Majordisadvantage:tiedto8-bitcharactersFraming(3)Bitstuffing(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataastheyarestoredinreceiver’smemoryafterdestuffing.ErrorDetectionandCorrection??Error-CorrectingCodesError-DetectingCodesErrorDetectiona)b)EDC=ErrorDetectionandCorrectionbits(redundancy)D=Dataprotectedbyerrorchecking,mayincludeheaderfieldsc)Errordetectionnot100%reliable!––protocolmaymisssomeerrors,butrarelylargerEDCfieldyieldsbetterdetectionandcorrectionParityChecking奇偶校驗a)Singlebitparity,detectonebiterrora)TwoDimensionalBitParity:b)DetectandcorrectsinglebiterrorsChecksumming:CyclicRedundancyChecka)b)c)viewdatabits,D,asabinarynumber循環(huán)冗余校驗chooser+1bitpattern(generator),Ggoal:chooserCRCbits,R,suchthat–––<D,R>exactlydivisiblebyG(modulo2)receiverknowsG,divides<D,R>byG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitsd)widelyusedinpractice(ATM,HDCL)CRCExampleWant:D.2rXORR=nGequivalently:D.2r=nGXORRequivalently:ifwedivideD.2rbyG,wantremainderRa)R=remainder[(D2r)/G]ElementaryDataLinkProtocols???AnUnrestrictedSimplexProtocolASimplexStop-and-WaitProtocolASimplexProtocolforaNoisyChannelProtocolDefinitionsContinuedSomedefinitionsneededintheprotocolstofollow.Thesearelocatedinthefileprotocol.h.ProtocolDefinitions(ctd.)Somedefinitionsneededintheprotocolstofollow.Thesearelocatedinthefileprotocol.h.UnrestrictedSimplexProtocolSimplexStop-and-WaitProtocolASimplexProtocolforaNoisyChannelApositiveacknowledgementwithretransmissionprotocol.ContinuedASimplexProtocolforaNoisyChannel(ctd.)Apositiveacknowledgementwithretransmissionprotocol.SlidingWindowProtocols???AOne-BitSlidingWindowProtocolAProtocolUsingGoBackNAProtocolUsingSelectiveRepeatSlidingWindowProtocols(2)Aslidingwindowofsize1,witha3-bitsequencenumber.(a)Initially.(b)Afterthefirstframehasbeensent.(c)Afterthefirstframehasbeenreceived.(d)Afterthefirstacknowledgementhasbeenreceived.AOne-BitSlidingWindowProtocolContinuedAOne-BitSlidingWindowProtocol(ctd.)AOne-BitSlidingWindowProtocol(2)Twoscenariosforprotocol4.(a)Normalcase.(b)Abnormalcase.Thenotationis(seq,ack,packetnumber).Anasteriskindicateswhereanetworklayeracceptsapacket.AProtocolUsingGoBackNPipelininganderrorrecovery.Effectonanerrorwhen(a)Receiver’swindowsizeis1.(b)Receiver’swindowsizeislarge.SlidingWindowProtocolUsingGoBackNContinuedSlidingWindowProtocolUsingGoBackNContinuedSlidingWindowProtocolUsingGoBackNContinuedSlidingWindowProtocolUsingGoBackNSlidingWindowProtocolUsingGoBackN(2)Simulationofmultipletimersinsoftware.ASlidingWindowProtocolUsingSelectiveRepeatContinuedASlidingWindowProtocolUsingSelectiveRepeat(2)ContinuedASlidingWindowProtocolUsingSelectiveRepeat(3)ContinuedASlidingWindowProtocolUsingSelectiveRepeat(4)ASlidingWindowProtocolUsingSelectiveRepeat(5)(a)Initialsituationwithawindowsizeseven.(b)Aftersevenframessentandreceived,butnotacknowledged.(c)Initialsituationwithawindowsizeoffour.(d)Afterfourframessentandreceived,butnotacknowledged.ConstrainsonWindows’Size?nbitssequencenumber?Thesizeofsendingwindow:W?Thesizeofreceivingwindow:W?Ws+Wsrr≤2nProtocolVerification?????FiniteStateMachinedModelsPetriNetModelsFiniteStateMachinedM