Chapter3:TheDatalinkLayerQiuJinsongComputerDepartmentZhejiangUniversityjinsongqiu@DesignIssuesServiceInterfaceFramingErrorControlFlowControlFunctionsoftheDataLinkLayerProvideserviceinterfacetothenetworklayerDealingwithtransmissionerrorsRegulatingdataflowSlowreceiversnotswampedbyfastsendersRelationshipbetweenpacketsandframes.ServicesProvidedtoNetworkLayerUnacknowledgedConnectionlessServiceAcknowledgedConnectionlessServiceAcknowledgedConnection-orientedServiceVirtualCommuncaitonPlacementofDatalinkProtocolFramingCharacterCountStartingandendingcharacter,withcharacterstuffingStartingandendingflags,withbitstuffingPhysicallayercodingviolationsCharacterCountStartingandendingcharacter,withcharacterstuffingStartingandendingflags,withbitstuffingErrorControlErrorCorrectingErrorDetecting,WithRetransmissionDuplicateLostErrorCorrectingCodeSingleErrorBurstErrorHammingDistanceCodewordDectectdbitserror,needd+1distancecodingCorrectdbitserror,need2d+1distancecodingParityCheckHammingCode10001001Xor1011000100111000d=3Even:100011000Odd:100011001HammingCodeUseofaHammingcodetocorrectbursterrors.1

234567891011x1

x2d1x3d2d3d4x4d5d6d7D7(11=1+2+8)checkedbyx1,x2,x4Data:1001000x1

x21x3001x4000CyclicRedundancyCheck(CRC)Modulo2DivisionCheckRemainderPolynomialRepresentation543210||||||110101=x5+x4+x2+1110110010011=x11+x10+x8+x7+x4+x+111109810Modulo2DivisionCheckingatthereceiverCRC-12=x12+x11+x3+x2+x1+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1PopularGeneratorPolynomialsStop-and-Wait(Normal)DataACKACKDatanextDatafollowingABStop-and-Wait(DataError)DataNAKACKData(Retransmission)DatanextABStop-and-Wait(DataLost)DataACKData(Retransmission)DatanextABTimeOutStop-and-Wait(ACKLost)DataACKData(Retransmission)DatanextABTimeOutACKDiscardthisDataProtocolProgramingProtocolProgramingUnrestrictedSimplexProtocol

---SenderUnrestrictedSimplexProtocol

---ReceiverSimplexStop-and-WaitProtocol

---SenderSimplexStop-and-WaitProtocol

---ReceiverAutomaticRepeatRequest(ARQ)ARQProtocol---SenderARQProtocol---ReceiverUtlizationofStop-and-waitUtilization=Tframe－－－－－－－－－2Tprop+TframeTframeDataACKACKDatanextABTpropTprop=Distance--------------------SpeedofSignalTframe=Framesize---------------Bitrate=Tprop

/

TframeUtilization=1/(2a+1)UtilizationSampleSatelliteLink:PropagationDelaytprop=270msFrameSize=4000bitsDatarate=56kbpsTtframe=4/56=71ms a=tprop/tframe=270/71=3.8U=1/(2a+1)=0.12ShortLink(1km):tprop=5sFrameSize=4000bitsDatarate=10MbpsTtframe=4k/10M=400s a=tprop/tframe=5/400=0.012U=1/(2a+1)=0.98SlidingWindowProtocolsData1ACK1Data4ABData2Data3ACK2ACK3Data5Data6ACK4ACK5ACK6UtlizationofSliding-windowTframeTpropABData1Data…DataNDataDataDataUtilization=NTframe－－－－－－－－－2Tprop+TframeUtilization=N/(2a+1)1(ifN>(2a+1))SlidingWindowWindow=Setofsequencenumberstosend/receiveSenderwindowSenderwindowincreaseswhenackreceivedPacketsinsenderwindowmustbebufferedatSourceSenderwindowmaygrowinsomeprotocolsPiggybackingData1ABData2Data3ACK+DataDataACK1SlidingWindow(Transmitter)6012345677012345……FramesmaybetransmittedFramesalreadytransmittedLastFrameTransmittedWindowshrinksfromtrailingedgeasframesaresentWindowexpandsfromleadingedgeasacknowledgmentsarereceivedFrameSequenceNumberFrameSequenceNumber6012345677012345……SlidingWindow(Receiver)6012345677012345……FramesmaybereceivedFramesalreadyreceivedLastFrameacknowledgedWindowshrinksfromtrailingedgeasframesarereceivedWindowexpandsfromleadingedgeasacknowledgmentsaresentFrameSequenceNumberFrameSequenceNumberSlidingWindowExampleSlidingWindowProgramingof1BitSlidingWindowProtocolProgramingof1BitSlidingWindowProtocolProblemofProtocol4NormalScenarios(seq,ack,packetnumber)NotSimultaneouslyduplicatesendpacketGo-back-NARQ(DataError)Data1ACK1Data4ABData2Data3Discard2Discard3ResendData2ResendData3Discard4ACK2ACK31bufferTimeOutGo-Back-NARQWindowSizeofGo-Back-NReceiveWindowSize=1SendWindowSize<=MAX_SEQ(0…N)0123450ACK50123450ACK5TimeOutlostresendnewSendtoNetworklayerdiscardSelectiveRepeatARQWindowSizeofSelectiveRepeatARQSendWindowSize<=(MAX_SEQ+1)/2ReceiveWindowSize=SendWindowSizeReceiveBufferNumber=WindowSizeAckalllostInitwindowNewwindowTimeoutresendSend7packetsGet7packetsIsneworresend?HDLCBit-OrientedProtocolFamilySynchronousDataLinkControl(SDLC):IBMHigh-LevelDataLinkControl(HDLC):ISOLinkAccessProcedure-Balanced(LAPB):X.25LinkAccessProcedurefortheDchannel(LAPD):ISDNPoint-to-PointProtocol(PPP):InternetLogicalLinkControl(LLC):IEEEAdvancedDataCommunicationsControlProcedures(ADCCP):ANSIBitStuffingHDLCFrameFormatInformationFrameUnnumberedFrameSupervisoryFrameHDLCFramesInformationFrames:UserdataPiggybackedAcks:NextframeexpectedPoll/Final=Command/ResponseSupervisoryFrames:FlowanderrorcontrolGobackNandSelectiveRejectFinal

NomoredatatosendRecieveReady(RR)、RecieveNotReady(RNR)Reject(REJ)、SelectiveReject(SREJ)UnnumberedFrames:ControlDISConnect、FrameReject、UnumberedAckModesettingcommandsandresponses,…HDLCExampleRR,HDLCExample(cont)DataLinkLayerinInternetSLIPSeialLineIPProblemsNoErrorDetectionandCorrectionSupportOnlyIPEachSideMustKnowPeer’sIPAddressAdvanceNoDynamicallyAssignedDuringSetupNoAuthenticationNotAnApprovedInternetStandardPPPPoint-to-PointProtocolAuthenticationDuringConnectionTimeSupportMultipleNetworkProtocols(IP,IPX)ErrorDetectionDynamicallyAssignedIPAddressDuringSetupCharacter-OrientedProtocolLinkControlProtocolNetworkControlProtocolPPPStateSummaryFramingFlowControlErrorControlSlidingWindowGo-Back-NSelectiveRepeatProtocolProgramingHDLCPPPExercise5.Abitstring,0111101111101111110,needstobetransmittedatthedatalinklayer.Whatisthestringactuallytransmittedafterbitstuffing?6.Whenbitstuffingisused,isitpossiblefortheloss,insertion,ormodificationofasinglebittocauseanerrornotdetectedbythechecksum?Ifnot,whynot?Ifso,how?Doest