哈尔滨工业大学计算机网络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提供服务给网络层•Framing成帧•ErrorControl误差控制•FlowControl流控制FunctionsoftheDataLinkLayer•••••Provideserviceinterfacetothenetworklayer提供网络层的服务接口Dealingwithtransmissionerrors处理传输误差Regulatingdataflow•调节数据流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循环冗余校验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