信息通信网络概论英文课件：Chapter5-DataLinkLayer-1

Chapter5

Peer-to-PeerProtocols

andDataLinkLayerRequiredreading:Garcia3.9&5.1~5.5

Chapter5DataLinkLayer-LLCPartI:5.1ErrorDetectionandCorrection5.2ARQProtocolsandReliableDataTransferService5.3Sliding-windowFlowControlPartII:5.4Framing5.5HDLC5.6PPPH1sendtoH2Host

H1Host

H2Router

R1Router

R2Router

R3Peer-to-PeerProtocolsModelDataLinkApplicationtransportNetworkPhysicalDataLinkApplicationtransportNetworkPhysicalDataLinkNetworkPhysicalDataLinkNetworkPhysicalDataLinkNetworkPhysicalR1R2R3H1H2ActualPDUFlowRouter

R4Point-to-PointProtocolsH1sendtoH2Host

H1Host

H2Router

R1Router

R2Router

R3End-to-EndProtocolsDataLinkApplicationtransportNetworkPhysicalDataLinkApplicationtransportNetworkPhysicalDataLinkNetworkPhysicalDataLinkNetworkPhysicalDataLinkNetworkPhysicalR1R2R3H1H2ActualPDUFlowRouter

R4End-to-EndProtocolsEnd-to-EndtoVs.Hop-to-HopFunctionsoftheDataLinkLayerProvidingawell-definedserviceinterfacetothenetworklayerDealingwithtransmissionerrorsRegulatingdataflowsothatslowreceiversarenotswampedbyfastsenders最主要的作用是通过一些数据链路层协议(即链路控制规程),在不太可靠的物理链路上实现可靠的数据传输.ServicesofDataLinkLayerFraming,linkaccess:

encapsulatedatagramintoframe,addingheader,trailerchannelaccessifsharedmediumAddressing‘physicaladdresses’usedinframeheaderstoidentifysource,dest

differentfromIPaddress!Reliabledeliverybetweenadjacentnodesseldomusedonlowbiterrorlink(fiber,co-axialcableandsometwistedpair)Usedonwirelesslinks:higherrorrates,wherethegoalistoreduceerrorsthusavoidingend-to-endretransmissionsQ:whybothlink-levelandend-endreliability?DataLinkLayerServices(cont.)ErrorDetection:

receiverdetectspresenceoferrorsErrorCorrection:receiveridentifiesandcorrectsbiterror(s)withoutresortingtoretransmissionErrorControl:Acknowledgement-Receiversendsbacktosenderspecialcontrolframesbearingpositiveornegativeacknowledgementsabouttheincomingframestosignaliftheframearrivesproperly.Timer-Whensendertransmitsaframe,italsostartsatimer,whichissettoexpireafteranintervallongenoughfortheframetoreachthedestination,beprocessedthere,andhavetheacknowledgementpropagatebacktosender.Sequencing-Assignsequencenumberstooutgoingframes,sothatthereceivercandistinguishretransmissionsfromoriginals,avoidduplicates.DataLinkLayerServices(cont.)FlowControl:

pacingbetweenadjacentsendingandreceivingnodesHalf-duplexandfull-duplexwithhalfduplex,nodesatbothendsoflinkcantransmit,butnotatsametimeChapter5

Peer-to-PeerProtocols

andDataLinkLayerPartI:ErrorDetectionandCorrection5.1ErrorDetectionandCorrection§5.1.1ErrorDetectionandCorrection§5.1.2ParityChecks§5.1.3InternetChecksum§5.1.4CyclicRedundancyCheck

§5.1.1ErrorDetect&CorrectDigitaltransmissionsystemsintroduceerrors,BERrangesfrom10-3forwirelessto10-9foropticalfiberApplicationsrequirecertainreliabilitylevelDataapplicationsrequireerror-freetransferVoice&videoapplicationstoleratesomeerrorsErrorcontrolusedwhentransmissionsystemdoesnotmeetapplicationrequirementErrorcontrolensuresadatastreamistransmittedtoacertainlevelofaccuracydespiteerrorsTwobasicapproaches:(1)ErrorDetection+AutomaticRetransmissionRequest(ARQ)(2)ForwardErrorCorrection(FEC)ErrorDetection&Correction

--SystemAlltransmitteddatablocks(“codewords”)satisfyapatternIfreceivedblockdoesn’tsatisfypattern,itisinerrorCheckbits&ErrorDetectionErrorDetection&Correction--RedundancyChannelcoding1Error-CorrectingCodes2Error-DetectingCodes

RetransmissionARQ:AutomaticRepeatRequestFEC:ForwardErrorCorrection

Redundancycheck1010000000010101101110110100000000101011011101CheckingFunctionGeneratingFunctionAcceptRejectAllerrordetection/correctionmethodsarebasedonredundancySenderReceiverWhatisagoodcode?

Manychannelshavepreferenceforerrorpatternsthathavefewer#oferrorsTheseerrorpatternsmaptransmittedcodewordtonearbyn-tupleIfcodewordsclosetoeachotherthendetectionfailureswilloccurGoodcodesshouldmaximizeseparationbetweencodewordsWhatisagoodcode?HammingDistance--NumberofbitsthatdifferbetweentwocodesToreliablydetectad-biterror:HD≥d+1Toreliablycorrectad-biterror:HD≥2d+1ParityCheckSingleParityCheck:AppendanoverallparitychecktokinformationbitsInfoBits:b1,b2,b3,…,bkCheckBit:bk+1=b1+b2+b3+…+bk

modulo2Codeword:(b1,b2,b3,…,bk,,bk+1)Allcodewordshaveeven#of1sReceivercheckstoseeif#of1sisevenAllerrorpatternsthatchangeanodd#ofbitsaredetectableAlleven-numberedpatternsareundetectableParitybitusedinASCIIcodeExampleofSingleParityCodeInformation(7bits):(0,1,0,1,1,0,0)ParityBit:b8=0+1+0+1+1+0=1Codeword(8bits):(0,1,0,1,1,0,0,1)Ifsingleerrorinbit3:(0,1,1,1,1,0,0,1)#of1’s=5,oddErrordetectedIferrorsinbits3and5:(0,1,1,1,0,0,0,1)#of1’s=4,evenErrornotdetectedHowgoodisthesingleparity

checkcode?Redundancy:Singleparitycheckcodeadds1redundantbitperkinformationbits:overhead=1/(k+1)Coverage:allerrorpatternswithodd#oferrorscanbedetectedAnerrorpattenisabinary(k+1)-tuplewith1swhereerrorsoccurand0’selsewhereOf2k+1binary(k+1)-tuples,½areodd,so50%oferrorpatternscanbedetectedIsitpossibletodetectmoreerrorsifweaddmorecheckbits?Yes,withtherightcodesTypesofErrorsSingle-BitError:BurstError:(a)(b)RandomErrorVectorChannelModelthereare2npossibleerrorvectors–allerrorareequallylikelye.g.e=[00000000]ande=[11111111]areequallylikely50%oferrorvectorshaveaneven#of1s,50%oferrorvectorshaveanodd#of1sprobabilityoferrordetectionfailure=0.5notveryrealisticchannelmodel!!!RandomBitError

Channelbiterrorsatrandom,independentlyofeachother,andprobabilityoferrorinasingle-bittransmission

pbSingleparitycheckcodewithrandombiterrorsSingleparitycheckcodewithrandombiterrorsExampleApproximately,1inevery2000transmitted32-bitbitlongcodewordsiscorruptedwithanerrorpatternthatcannotbedetectedwithsingle-bitparitycheck.

§5.1.2Two-DimensionalParityCheck

MoreparitybitstoimprovecoverageArrangeinformationascolumnsAddsingleparitybittoeachcolumnAddafinal“parity”columnUsedinearlyerrorcontrolsystemsTwo-DimensionalParityCheck--Example10001010字符1b1b2b3b4b5b6b7check11001011字符211011010字符310101011字符410001010字符510001010字符611101010字符700100101checkTwo-DimensionalParityCheck--Example10001010Byte1b1b2b3b4b5b6b7check11011011Byte211011010Byte310101011Byte410100010Byte510001010Byte611101010Byte700100101CheckBytePerformacrossrowsandcolumnsCatchesall1-,2-,3-,andsome4-biterrorsCancorrectall1-biterrorsError-detectingcapabilityOtherErrorDetectionCodesManyapplicationsrequireverylowerrorrateNeedcodesthatdetectthevastmajorityoferrorsSingleparitycheckcodesdonotdetectenougherrorsTwo-dimensionalcodesrequiretoomanycheckbitsThefollowingerrordetectingcodesusedinpractice:InternetCheckSumsCRCPolynomialCodes§5.1.3InternetChecksumerrordetectionmethodusedbyIP,TCP,UDP!!!checksumcalculation:IP/TCP/UDPpacketisdividedinton-bitsectionsn-bitsectionsareaddedusing“1-scomplementarithmetic”–thesumisalson-bitslong!thesumiscomplementedtoproducechecksum(complementofanumberin1-sarithmeticisthenegativeofthenumber)advantages:relativelylittlepacketoverheadisrequiredeasy/fasttoimplementinsoftwaredisadvantages:weakprotectioncomparedtoCRC–e.g.willnotdetectmisorderedbytes/words!!!detectsallerrorsinvolvinganoddnumberofbitsandmosterrorsinvolvinganevennumberofbitsInternetChecksumSender:dataisdividedintoksectionseachnbitslongallsectionsareaddedusing1-scomplementtogetthesumthesumiscomplementedandbecomesthechecksumthechecksumissentwiththedataReceiver:dataisdividedintoksectionseachnbitslongallsectionsareaddedusing1-scomplementtogetthesumthesumiscomplementediftheresultiszero,thedataisaccepted,otherwiseitisrejectedChecksum--ExampleChecksum--ExampleChecksum--ExampleChecksum--ExampleUDPChecksum--Example1001100100010011→153.190000100001101000→8.1041010101100000011→171.30000111000001011→14.110000000000010001→0和170000000000001111→150000010000111111→10870000000000001101→130000000000001111→150000000000000000→0（检验和）0101010001000101→数据0101001101010100→数据0100100101001110→数据0100011100000000→数据和0（填充）1001011011101101→求和得出的结果0110100100010010→检验和153.19.8.104171.3.14.1112字节伪首部8字节UDP首部7字节数据填充按二进制反码运算求和将得出的结果求反码全0171510871315全0数据数据数据数据数据数据数据全0请注意：进行反码运算求和时，最高位有进位

2，这个

2

应当加到最低位。§5.1.4PolynomialCodes

PolynomialsinsteadofvectorsforcodewordsImplementedusingshift-registercircuitsAlsocalledcyclicredundancycheck(CRC)

codesMostdatacommunicationsstandardsusepolynomialcodesforerrordetectionPolynomialcodesalsobasisforpowerfulerror-correctionmethodsCyclicRedundancyCheckBinaryPolynomialArithmeticBinaryvectorsmaptopolynomials(ik-1

,ik-2

,…,i2,i1,i0)ik-1xk-1+ik-2xk-2+…+i2x2+i1x+i0Addition: (x7+x6+1)+(x6

+x5)=x7+x6

+x6+x5+1 =x7+(1+1)x6+x5+1 =x7+x5+1 since1+1=0mod2Multiplication: (x+1)(x2

+x+1)=x(x2+x+1)+1(x2+x+1) =(x3+x2+x)+(x2+x+1) =x3+1BinaryPolynomialDivision

1101010110

←

Q

商

除数

G→

110101101000110100000

←

2nM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

remainderPolynomialexample:Transmittedcodeword:

b=(101000110101110)Generatorpolynomial: g(x)=x5+x4+x2+1Information:(1010001101) i(x)=x9+x7+x3+x2+1Encoding: x5i(x)=x14+x12+x8+x7+x5PolynomialCodingCodehasbinarygeneratingpolynomialofdegreen–k

g(x)=xn-k+gn-k-1xn-k-1+…+g2x2+g1x+1

kinformationbitsdefinepolynomialofdegreek–1

i(x)=ik-1xk-1+ik-2xk-2+…+i2x2+i1x+i0Findremainderpolynomialofatmostdegreen–k–1

xn-ki(x)=q(x)g(x)+r(x)Definethecodewordpolynomialofdegreen–1ThePatterninPolynomialCodingAllcodewordssatisfythefollowingpa