计算机网络英文版课件：slide 03 The Data Link Layer

TheDataLinkLayerContentsFunctionofthedatalinklayer:Toconverttherawbitstreamofferedbythephysicallayerintoastreamofframesforusebythenetworklayertotransferdatafromthenetworklayeronthesourcemachinetothenetworklayeronthedestinationmachine.FramingErrorControlFlowControlProtocolVerification:protocolmodeling,andcorrectnessExampleDataLinkProtocolsDataLinkLayerDesignIssuesThedatalinklayerhasanumberofspecificfunctionsitcancarryout.Thesefunctionsinclude:Providingawell-definedserviceinterfacetothenetworklayer.DealingwithtransmissionerrorsRegulatingtheflowofdatasothatslowreceiversarenotswampedbyfastsenders.Toachievereliable,efficientcommunicationbetweentwoadjacentmachinesatthedatalinklayerFrame,andframemanagementFunctionsoftheDataLinkLayerRelationshipbetweenpacketsandframes.ServicesProvidedtoNetworkLayer(a)Virtualcommunication.(b)Actualcommunication.Thedatalinklayercanbedesignedtooffervariousservices.Theactualservicesofferedcanvaryfromsystemtosystem.ThreereasonablepossibilitiesthatarecommonlyprovidedareUnacknowledgedconnectionlessservice.AcknowledgedconnectionlessserviceAcknowledgedconnection-orientedserviceServicesProvidedtoNetworkLayerServicesProvidedtoNetworkLayerPlacementofthedatalinkprotocol.FramingAcharacterstream.(a)Withouterrors.(b)Withoneerror.Framing(2)(a)Aframedelimitedbyflagbytes.(b)Fourexamplesofbytesequencesbeforeandafterstuffing.Framing(3)Bitstuffing(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataastheyarestoredinreceiver’smemoryafterdestuffing.Strategs:Error-CorrectingCodesError-DetectingCodesCodeword:Ann-bitunitcontainingdataandcheckbitsisoftenreferredtoasann-bitcodewordHammingDistance:ThenumberofbitpositionsinwhichtwocodewordsdifferIftwocodewordsareaHammingdistancedapart,itwillrequiredsingle-biterrorstoconvertoneintotheotherErrorDetectionandCorrection100010011011000100111000ErrorDetectionandCorrectionTodetectderrors,youneedadistance

d+1codebecausewithsuchacodethereisnowaythatdsingle-biterrorscanchangeavalidcodewordintoanothervalidcodewordTocorrectderrors,youneedadistance

2d+1codebecausethatwaythelegalcodewordsaresofarapartthatevenwithdchanges,theoriginalcodewordisstillcloserthananyothercodeword,soitcanbeuniquelydetermined.Todesignacodewithmmessagebitsandrcheckbitsthatwillallowallsingleerrorstobecorrected,wemusthave(n+1)2m

≤2n,wheren=m+r.Error-CorrectingCodesUseofaHammingcodetocorrectbursterrors.Error-DetectingCodesCalculationofthepolynomialcodechecksum.ElementaryDataLinkProtocolsAnUnrestrictedSimplexProtocolASimplexStop-and-WaitProtocolASimplexProtocolforaNoisyChannelProtocolDefinitionsContinuedSomedefinitionsneededintheprotocolstofollow.Thesearelocatedinthefileprotocol.h.Protocol

Definitions

(ctd.)Somedefinitionsneededintheprotocolstofollow.Thesearelocatedinthefileprotocol.h.Unrestricted

Simplex

ProtocolSimplexStop-and-WaitProtocolASimplexProtocolforaNoisyChannelApositiveacknowledgementwithretransmissionprotocol.ContinuedASimplexProtocolforaNoisyChannel(ctd.)Apositiveacknowledgementwithretransmissionprotocol.SlidingWindowProtocolsAOne-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.SlidingWindowProtocolUsingGoBackNContinuedSlidingWindowProtocolUsingGoBackNContinuedSlidingWindowProtocolUsingGoBackNContinuedSlidingWindowProtocolUsingGoBackNSlidingWindowProtocolUsingGoBackNSimulationofmultipletimersinsoftware.ASlidingWindowProtocolUsingSelectiveRepeatContinuedContinuedASlidingWindowProtocolUsingSelectiveRepeat(2)ASlidingWindowProtocolUsingSelectiveRepeat(3)ContinuedASlidingWindowProtocolUsingSelectiveRepeat(4)ASlidingWindowProtocolUsingSelectiveRepeat(5)(a)Initialsituationwithawindowsizeseven.(b)Aftersevenframessentandreceived,butnotacknowledged.(c)Initialsituationwithawindowsizeoffour.(d)Afterfourframessentandreceived,butnotacknowledged.Allsevenframesarrivecorrectly,sothereceiveracknowledgesthemandadvancesitswindowtoallowreceiptof7,0,1,2,3,4,or5,asshowninFig.(b).

ButtheACKmessagesarelost.

Thesendereventuallytimesoutandretransmitsframe0.Thereceiversendsapiggybackedacknowledgementforframe6,since0through6havebeenreceived.Thesenderishappytolearnthatallitstransmittedframesdidactuallyarrivecorrectly,soitadvancesitswindowandimmediatelysendsframes7,0,1,2,3,4,and5.ExampleDataLinkProtocolsHDLC–High-LevelDataLinkControlTheDataLinkLayerintheInternetHigh-LevelDataLinkControlFrameformatforbit-orientedprotocols.High-LevelDataLinkControl(2)Controlfieldof(a)Aninformationframe.(b)Asupervisoryframe.(c)Anunnumberedframe.TheDataLinkLayerintheInternetAhomepersonalcomputeractingasaninternethost.PPP–PointtoPointProtocolPPPprovidesthreefeatures:Aframingmethodthatunambiguouslydelineatestheendofoneframeandthestartofthenextone.TheframeformatalsohandleserrordetectionAlinkcontrolprotocolforbringinglinesup,testingthem,negotiatingoptions,andbringingthemdownagaingracefullywhentheyarenolongerneeded.ThisprotocoliscalledLCP(LinkControlProtocol).Itsupportssynchronousandasynchronouscircuitsandbyte-orientedandbit-orientedencodings.Awaytonegotiatenetwork-layeroptionsinawaythatisindependentofthenetworklayerprotocoltobeused.ThemethodchosenistohaveadifferentNCP(NetworkControlProtocol)foreachnetworklayersupported.PPP–PointtoPointProtocolThePPPfullframeformatforunnumberedmodeoperation.ProtocolVerificationFiniteS