北郵課件計算機(jī)網(wǎng)絡(luò)ch3-datalink

Chapter3TheDataLinkLayerDatalinkLayerDataLinkLayerDesignIssuesServicesProvidedtotheNetworkLayerFramingErrorControl&FlowControlErrorDetectionandCorrectionErrorCorrectingCode(ECC)ErrorDetectingCodeElementaryDataLinkProtocolsSlidingWindowProtocolsOne-BitSlidingWindowProtocolProtocolUsingGoBackNUsingSelectiveRepeatPerformanceofSlidingWindowProtocolsExampleDataLinkProtocolsHDLCSLIPPPP3.1DataLinkLayerDesignIssuesDataLinkLayerDesignIssuesGoalsStudythealgorithmsforachievingreliable,efficientcommunicationbetweentwoadjacentmachinesAdjacent:twomachinesareconnectedbyacommunicationchannelthatactslikeawire,bitsaredeliveredinexactlythesameorderinwhichtheyaresentDataLinkLayerDesignIssuesServicesProvidedtotheNetworkLayerFramingErrorControlFlowControlServicesProvidedtotheNetworkLayerFunctionsoftheDataLinkLayerProvideserviceinterfacetothenetworklayerDealingwithtransmissionerrorsRegulatingdataflowSlowreceiversnotswampedbyfastsendersFunctionsoftheDataLinkLayer(2)Relationshipbetweenpacketsandframes.ServicesProvidedtoNetworkLayer(a)Virtualcommunication.(b)Actualcommunication.ServicesProvidedtoNetworkLayerUnacknowledgedconnectionlessservice.

MostLANsuseunacknowledgedconnectionlessservice

Acknowledgedconnectionlessservice.

Thisserviceisusefuloverunreliablechannels,suchaswirelesssystemsAcknowledgedconnection-orientedserviceTimerSequencenumberConnectionestablishmentPlacementofthedatalinkprotocolFramingFramingAsequenceofbitsissentfromnodeAtonodeBoverapoint-to-pointlink,NodeBmustrecognizeexactlywhatsetofbitsconstitutesaframeCharacterCountAcharacterstream.(a)Withouterrors.(b)Withoneerror.Charactercount(字符記數(shù)):Usesafieldintheheadertospecifythenumberofcharactersintheframe(DEC:DDCMP)ByteStuffing

(a)Aframedelimitedbyflagbytes.(b)Fourexamplesofbytesequencesbeforeandafterstuffing.Flagbyteswithbytestuffing(字符添充):Havingeachframestartandendwithspecialbytes(BISYNC,PPP)BitStuffing

(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataastheyarestoredinreceiver’smemoryafterdestuffing.Startingandendingflags,withbitstuffing(比特添充):Eachframebeginsandendswithaspecialbitpattern,01111110.Wheneverthesender'sdatalinklayerencountersfiveconsecutive1sinthedata,itautomaticallystuffsa0bitintotheoutgoingbitstream(Example:HDLC)ExamplewithPossibleErrors(BitStuffing)

PhysicalLayerCodingViolationsPhysicallayercodingviolations:物理層編碼違例法(IEEE:802.3)

例如：編碼方案：時鐘周期內(nèi)電壓高變低表示1，低變高表示0，時鐘周期內(nèi)電壓恒高或恒低，不表示數(shù)據(jù)，可用做定界符Manchester差分ManchesterHomework1,2,3,4,5ErrorControl&FlowControlErrorControlMakesureallframesaredeliveredtothedestinationandintheproperorderProvidethesenderwithsomefeedbackaboutwhatishappeningattheotherendofthelineHardwaretroublesmaycauseaframetovanishcompletelyframeorACKislost,thetimerwillgooff,...Managingtimersandsequencenumberssoastoensurethateachframeispassedtothedestinationexactlyonce,nomoreandnolessFlowControlTwoapproachesarecommonlyused

Feedback-basedflowcontrol,thereceiversendsbackinformationtothesender,givingitpermissionortellingthesenderhowthereceiverisdoingRate-basedflowcontrol,limitstherateatwhichsendersmaytransmitdata3.2ErrorDetectionandCorrectionErrorCorrectingCode(ECC)Single-bitError&BurstErrorSingle-biterror,onlyonebithaschangedAbursterrormeansthat2ormorebitshavechanged.HammingDistanceHammingdistance:Thenumberofbitpositionsinwhichtwocodewordsdiffer(10001001and10110001,Hammingdistance=3)Todetectterrors,needadistancet+1codeTocorrectterrors,needadistance2t+1codeECC:error-correctingcodesFEC:forwarderrorcorrectionExampleofanError-CorrectingCodeConsideracodewithonlyfourvalidcodewords:,1111100000,1111111111Thiscodehasadistance5,whichmeansthatitcancorrect2errors.Ifthecodewordarrives,thereceiverknowsthattheoriginalmusthavebeenIfatripleerrorchangesinto,theerrorwillnotbecorrectedproperlyTheNumberofCheckBitsFindoutthenumberofcheckbitsneededtocorrectsingleerrorCodingm:messagebitsr:checkbitsn:codewordlength(n=m+r)2mlegalmessagesEachlegalmessagehasnillegalcodewordsatadistance1fromit,need(n+1)2mcodewords(n+1)2m

≤2n

(m+r+1)≤2r Example:m=7,r≥4Thebitsofthecodewordarenumbered,startwith1atleftend,bit2toitsimmediateright,andsoon.CheckbitsThebitsthatarepowersof2(1,2,4,8,16...)arecheckbitsEachcheckbitforcestheparityofsomecollectionofbits,includingitself,tobeeven(orodd).DatabitsTherest(3,5,6,...)arefilledupwiththemdatabitsHammingCodeMessage:‘H’(7-bitASCII100,1000)DataBits:3,5,6,7,9,10,114Checkbits,Bit1,2,4,8(evenparity)BitNumber:1

234567891011Codeword:00110010000發(fā)送前編碼：

3=1+2，5=1+4，6=2+4，7=1+2+49=1+8，10=2+8，11=1+2+8接收者糾錯：

b1⊕b3⊕b5⊕b6⊕b7⊕b9⊕b10⊕b11=0(k=1)

b2⊕b3⊕b5⊕b6⊕b7⊕b9⊕b10⊕b11=0(k=2)

b4⊕b3⊕b5⊕b6⊕b7⊕b9⊕b10⊕b11=0(k=4)

b8⊕b3⊕b5⊕b6⊕b7⊕b9⊕b10⊕b11=0(k=8)ExampleofHammingCodeHammingcode:CorrectbursterrorsUseofaHammingcodetocorrectbursterrors.其他前向糾錯碼（FEC）廣泛用于無線鏈路，提高信道信噪比BCH碼Bose，Ray-Chaudhuri，Hocquenhem里德-所羅門碼(里所碼)Reed-solomoncodes,RScodes戈帕碼Goppacodes卷積碼與塊編碼不同，卷積碼可以連續(xù)地生成冗余位擦除碼(ErasureCorrection)原始數(shù)據(jù)分成k塊，編碼后的編碼數(shù)據(jù)n片從n片中的任意k片都可以恢復(fù)原先的k塊數(shù)據(jù)k<n≤2k,常見n=2k例如：k=3,n=6a00x0+a01x1+a02x2=y0a10x0+a11x1+a12x2=y1a20x0+a21x1+a22x2=y2a30x0+a31x1+a32x2=y3a40x0+a41x1+a42x2=y4a50x0+a51x1+a52x2=y5(x0,x1,x2)為原始數(shù)據(jù)，(y0,y1,y2,y3,y4,y5)為編碼后數(shù)據(jù)只需得到y(tǒng)0-y5的任三個(包括它們的行號)就可還原x0-x2精心設(shè)計系數(shù)矩陣A(非齊次線性方程問題，矩陣的秩)Homework9,11ErrorDetectingCodeErrorCorrecting&DetectingOnchannelsthatarereliable,suchasfiber,itischeapertouseanerrordetectingcodeandjustretransmittheoccasionalblockfoundtobefaultyOnchannelssuchaswirelesslinksthatmakemanyerrors,itisbettertoaddenoughredundancytoeachblockforthereceivertobeabletofigureoutwhattheoriginalblockwasExample(single-biterror)BitErrorRateBER=10-6,1Block=1000bits,Data=1MbitsTheoverheadErrordetection+retransmission:2001bitsHammingcode:10,000bitsErrorDetectingCodes

Odd&EvenParityOdd&Evenparity單個奇偶校驗(yàn)位性能可檢出奇數(shù)個位翻轉(zhuǎn)錯誤不能檢出偶數(shù)個位翻轉(zhuǎn)錯誤OddParityEvenParityEvenParityCheckOdd&EvenParityCoding(rcheckbits)Eachblockisregardedasak×rmatrixAparitybiteverycolumn,affixedtothematrixasthelastrowThematrixisthentransmittedonerowatatimePerformanceCandetectasingleburstoflength≤rCatchallerrorsconsistingofanoddnumberofinvertedbitsAburstoflength>rIfblockisgarbledbyalongburst，theprobabilityofbeingacceptedis2-r

1001000101010011101000010101011011001100111011011000100010011110PolynomialCodeAlsoknownasCRC(CyclicRedundancyCheck)FCS(FrameCheckSequence)M(x):Treatingbitstringsasrepresentationsofpolynomialswithcoefficientsof0and1Ak-bitframeisregardedasthecoefficientlistforapolynomialwithkterms,rangingfromxk-1tox0:110001=>x5+x4+x0Polynomialarithmeticisdonemodulo2,additionandsubtractionareidenticaltoXORG(x):GeneratorpolynomialSender:ComputingtheChecksumThealgorithmforcomputingthechecksum:Appendrzerobitstothelow-orderendoftheframeDividethebitstringcorrespondingtoG(x)T(x):SubtracttheremainderfromthebitstringExampleofCRCCalculationCalculationofthepolynomialcodechecksum.Receiver:VerifytheChecksumIfatransmissionerroroccurs,sothatinsteadofthebitstringforT(x)arriving,T(x)+E(x)arrives.Thereceivercomputes[T(x)+E(x)]/G(x).T(x)/G(x)is0,sotheresultisE(x)/G(x)ThoseerrorsthathappentocorrespondtopolynomialscontainingG(x)asafactorwillslipby;allothererrorswillbecaught.ThePowerofCRCrcheckbitswilldetectallbursterrorsoflength≤rTwoisolatedsingle-biterrorsaredetectedE(x)=xi+xj,=xj(xi-j+1).wherei>jChooseG(x):G(x)doesnotdividexk+1foranykuptomaximumframelengthForexample,x15+x14+1willnotdividexk+1foranyvalueofkbelow32,768(4096bytes)Catchallerrorsconsistingofanoddnumberofinvertedbits:bymakingx+1afactorofG(x)IfE(x)hasanoddnumberoftermsandisdivisiblebyx+1.E(x)=(x+1)Q(x),E(1)=(1+1)Q(1)=0.E(x)hasanoddnumberofterms,E(1)=1Otherbursterrors(length>r)Theprobabilityofabadframebeenacceptedis2-rGeneratorPolynomialCertainpolynomialshaveeinternationalstandardsCRC-16x16+x15+x2+1CRC-CCITT(HDLC)x16+x12+x5+1CRC-32(IEEE802)x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1CRC-64TheCalculationofCRC5(Hardware)TheCalculationofCRC5(Hardware)HardwareAsimpleshiftregistercircuitcanbeconstructedtocomputeandverifythechecksums生成多項式G(x)=x5+x4+x2+1(110101)初始時移位寄存器C0~C4清0信息位10比特發(fā)送之后，斷開A接通B,發(fā)送5比特校驗(yàn)和，并順便清0寄存器C0~C4為下次發(fā)送做好準(zhǔn)備C4C3C2C1C0I(Input)Initial000001111Step1101011110Step2111111101Step3111100010Step4010011000Step5100101010Step6100010001Step7000101011Step8100011110Step9101110101Step1001110TheCalculationofCRC5(Hardware)手工計算CRC4：速算表生成多項式x4+x+1手工計算CRC4：利用速算表TheCalculationofCRC(Software)

staticunsignedshortcrctab[256]={0x0000,0x1189,0x2312,0x329b,0x4624,0x57ad,0x6536,0x74bf,0x8c48,0x9dc1,0xaf5a,0xbed3,0xca6c,0xdbe5,……0xd49d,0xc514,0xb1ab,0xa022,0x92b9,0x8330,0x7bc7,0x6a4e,0x58d5,0x495c,0x3de3,0x2c6a,0x1ef1,0x0f78};unsignedshortcrc16(unsigned

shortcrc,unsignedchar*p,intlen){

while(len--)crc=(crc>>8)^crctab[(crc^*p++)&0xff];

returncrc;}其他哈希函數(shù)及應(yīng)用哈希函數(shù)CRC算法為一個數(shù)據(jù)段計算出一個長度固定的哈希值。哈希算法的哈希值位數(shù)越多，校驗(yàn)?zāi)芰υ綇?qiáng)，64位以上的哈希函數(shù)常用于安全領(lǐng)域，實(shí)現(xiàn)電子簽名的功能，防止數(shù)據(jù)被惡意修改在計算性能上的特點(diǎn)：便于32位計算機(jī)高效率的軟件實(shí)現(xiàn)MessageDigest5(MD5)：128bitsSecureHashAlgorithm1(SHA-1)：160bits哈希函數(shù)的其他應(yīng)用(用來比較兩段數(shù)據(jù)是否相同)哈希值不同，數(shù)據(jù)必不同；哈希值相同，數(shù)據(jù)不同的概率很低（弱哈希函數(shù)和強(qiáng)哈希函數(shù)）用CRC32比較兩臺計算機(jī)上的數(shù)據(jù)是否相同，例如：Cisco的OSPF鏈路狀態(tài)數(shù)據(jù)庫Bittorent,eMulemd5sum增量拷貝rsync（同時利用弱哈希函數(shù)和強(qiáng)哈希函數(shù)）Homework14,15,163.3ElementaryDataLinkProtocolsElementaryDataLinkProtocolsAnUnrestrictedSimplexProtocolASimplexStop-and-WaitProtocolASimplexProtocolforaNoisyChannelProtocolDefinitionsElementaryDataLinkProtocolsSomeoftheassumptionsPhysicallayer,datalinklayer,andnetworklayerareindependentprocessesMachineAwantstosendalongstreamofdatatomachineB,usingareliable,connection-orientedserviceMachinesdonotcrashLibraryprocedureswait_for_eventsfrom_network_layer/to_network_layerto_physical_layer/from_physical_layertimeroperationsenable_network_layer/disable_network_layersequencenumberoperationProtocolDefinitionsSomedefinitionsneededintheprotocolstofollow.Thesearelocatedinthefileprotocol.h.Protocol1:UtopiaUnrestricted

Simplex

ProtocolProtocol2:Stop-and-WaitProtocolforaError-freeChannelSimplexStop-and-WaitProtocolProtocol3:ASimplexProtocolforaNoisyChannelProblemsSendDATAandthenwaitforACK……Case1:ProtocolfailedonreceiverThenetworklayeronAgivespacket1toitsdatalinklayer.ThepacketiscorrectlyreceivedatBandpassedtothenetworklayer.BsendsanACKtoATheACKgetslostcompletelyThedatalinklayeronAeventuallytimesout.NothavingreceivedACK,resendstheframeTheduplicateframealsoarrivesB,...Case2:ProtocolfailedonSenderAdelayedACKSequenceNumberDistinguishanewframefromaretransmissionPutasequencenumberintheheaderofeachframeWhatistheminimumnumberofbitsneededforthesequencenumber?（停等協(xié)議）鏈路層：1比特，編號空間大小為2傳輸層：1比特編號空間太小，需要較大的編號空間。如：TFTP（16比特編號）seq_nr=0從網(wǎng)絡(luò)層獲取一個分組放入buffer發(fā)送buffer中的數(shù)據(jù)(seq_nr)，新啟動定時器label1:wait_for_event()switch(event){case收到了壞幀(校驗(yàn)和錯):

重發(fā)緩沖在buffer里的數(shù)據(jù)(seq_nr)，重新啟動定時器case定時器超時：重發(fā)緩沖在buffer里的數(shù)據(jù)(seq_nr)，新啟動定時器case收到校驗(yàn)和正確的幀：

if（ack序號正確）{

關(guān)閉舊定時器

inc(seq_nr)從網(wǎng)絡(luò)層獲取下一個分組放入buffer

發(fā)送buffer中的數(shù)據(jù)(seq_nr)，新啟動定時器

}else

重發(fā)緩沖在buffer里的數(shù)據(jù)(seq_nr)，重新啟動定時器}gotolabel1Senderseq_nr=0從網(wǎng)絡(luò)層獲取一個分組放入bufferlabel1:發(fā)送buffer中的數(shù)據(jù)(seq_nr)，新啟動定時器wait_for_event()switch(event){case收到了壞幀(校驗(yàn)和錯)://重發(fā)緩沖在buffer里的數(shù)據(jù)(seq_nr)，重新啟動定時器case定時器超時：

//重發(fā)緩沖在buffer里的數(shù)據(jù)(seq_nr)，新啟動定時器case收到校驗(yàn)和正確的幀：

if（ack序號正確）{

關(guān)閉舊定時器

inc(seq_nr)從網(wǎng)絡(luò)層獲取下一個分組放入buffer//發(fā)送buffer中的數(shù)據(jù)(seq_nr)，新啟動定時器

}else//重發(fā)緩沖在buffer里的數(shù)據(jù)(seq_nr)，重新啟動定時器}gotolabel1SenderSenderframe_expected=0while(true){wait_for_event()switch(event){case壞幀：

do_nothingcase收到校驗(yàn)和正確的數(shù)據(jù)幀:if(序號==frame_expected){向網(wǎng)絡(luò)層上交分組

回送ACK(序號為frame_expected)inc(frame_expected)}else{回送ACK(序號為dec(frame_expected))}}}Receiverframe_expected=0while(true){wait_for_event()switch(event){case壞幀：

do_nothingcase收到校驗(yàn)和正確的數(shù)據(jù)幀:if(序號==frame_expected){向網(wǎng)絡(luò)層上交分組inc(frame_expected)

}回送ACK(序號為dec(frame_expected))}}ReceiverReceiverApositiveacknowledgementwithretransmissionprotocol.(PAR)TimerTimeoutIfthetimeoutintervalissettooshort,thesenderwilltransmitunnecessaryframes.Whiletheseextraframeswillnotaffectthecorrectnessoftheprotocol,theywillhurtperformance3.4SlidingWindowProtocolsPiggybackingForfull-duplexdatatransmissionUsetwoseparatecommunicationchannelsanduseeachoneforsimplexdatatrafficUsethesamecircuitfordatainbothdirectionsPiggybackingWhenadataframearrives,insteadofimmediatelysendingaseparatecontrolframe,thereceiverrestrainsitselfandwaitsuntilthenetworklayerpassesitthenextpacketACKisattachedtotheoutgoingdataframe(usingtheackfieldintheframeheader)Sendingwindow&ReceivingwindowSendingwindowUsewindowtocontrolnumberofoutstandingframesAtanyinstantoftime,thesendermaintainsasetofsequencenumberscorrespondingtooutstandingframes.TheseframesaresaidtofallwithinthesendingwindowMaximumofSendingWindowSizeReceivingwindowReceiveralsomaintainsareceivingwindowcorrespondingtothesetofframesitispermittedtoacceptSlidingWindowProtocolsAOne-BitSlidingWindowProtocolAProtocolUsingGoBackNAProtocolUsingSelectiveRepeatOne-BitSlidingWindowProtocolSlidingWindowofSize1Aslidingwindowofsize1,witha3-bitsequencenumber.(a)Initially.(b)Afterthefirstframehasbeensent.(c)Afterthefirstframehasbeenreceived.(d)Afterthefirstacknowledgementhasbeenreceived.Protocol4:One-BitSlidingWindow發(fā)送窗口最大值1One-BitSlidingWindowProtocol(1)/*兩端都執(zhí)行相同的程序protocol4()*//*雙向均有無窮盡數(shù)據(jù)發(fā)向?qū)Ψ?/One-BitSlidingWindowProtocol(2)TwoScenariosforProtocol4Twoscenariosforprotocol4.Thenotationis(seq,ack,packet)Anasteriskindicateswhereanetworklayeracceptsapacket(a)Normalcase.(b)Abnormalcase.ProblemConsidera50-kbpssatellitechannelwitha520-msecround-trippropagationdelay,send1000-bitframest=0:senderstartssendingt=20msec:theframehasbeencompletelysentt=270msec:framefullyarrivedatthereceivert=520msec:ACKarrivedbackatthesender,underthebestofcircumstances(nowaitinginthereceiverandashortacknowledgementframe).ConclusionSenderwasblockedduring500/520or96%ofthetime.only4%oftheavailablebandwidthwasusedLineUtilization

ProtocolUsingGoBackNPipelining&ErrorRecoveryPipelininganderrorrecovery.Effectonanerrorwhen(a)Receiver’swindowsizeis1.(b)Receiver’swindowsizeislarge.AboutACKBA012ACK0ACK2ACK1BA012ACK2GoBackNBasedonslidingwindowUsewindowtocontrolnumberofoutstandingframesIfReceiverdetectserror,discardthatframeandallfutureframesuntilerrorframereceivedcorrectly(silent)Transmittermust

gobackandretransmitthatframeandallsubsequentframesDamagedFrameIfDataFrameisDamagedReceiverdetectserrorinframeiReceiverdiscardthatframei

andallsubsequentWhentimeout,transmitterretransmitsframeiandallsubsequentIfACKFrameisDamagedReceivergetsframei

andsendacknowledgementACK(i)whichislostAcknowledgementsarecumulative,sonextACK(i+n)mayarrivebeforetransmittertimesoutonframeiIftransmittertimesout,retransmitsframeiandallsubsequentMaximumofSendingWindowSizeProblemThesendersendsframes0through7.ACKforframe7comesbacktothesender.Thesendersendsanothereightframes,againwithsequencenumbers0through7.Didalleightframesbelongingtothesecondbatcharrivesuccessfully,ordidalleightgetlost?

原則發(fā)送方發(fā)完窗口內(nèi)所有幀，接收方正確接收到所有發(fā)送來的幀，接收窗口向前推移。此時(未回送ACK)，必須保證發(fā)送窗口與接收窗口在序號上不重疊(考慮所有ACK丟失的情況:發(fā)送窗口不滑動，接收窗口最大滑動)。Protocol5:Go-Back-NProtocol發(fā)送窗口最大值7函數(shù)between

判斷序號b是否落在窗口(a,b)內(nèi)判斷：a到c不回繞c>a(b位于a~c之間)判斷：a到c回繞a>c(b位于a~7,或者0~c-1)-Protocol5改進(jìn)和效率設(shè)置ACK幀和ACK定時器發(fā)送數(shù)據(jù)量并非一個源源不斷的分組流無法及時搭載ACK時，發(fā)送短的ACK幀(不含數(shù)據(jù)信息)用于回送ACK的定時器操作start_ack_timer和stop_ack_timer,數(shù)據(jù)重傳所用定時器操作(與上述兩個操作有區(qū)別)start_timer與stop_timerACK定時器時限的設(shè)計NAK幀:激發(fā)重傳不需等到超時協(xié)議參數(shù)與線路利用率超時定時器時限的設(shè)計（考慮線路往返時間延遲，ACK定時器時限，對方物理層發(fā)送排隊時延）滑動窗口即MAX_SEQ大小TimerQueueinSoftwareSimulationofmultipletimersinsoftware.UsingSelectiveRepeatSelectiveRepeatAlsocalledselectiveRejectOnlyrejectedframesareretransmittedSubsequentframesareacceptedbythereceiverandbufferedMinimizesretransmissionReceivermustmaintainlargeenoughbufferMorecomplexWindowSizeofSelectiveRepeat

(a)Initialsituationwithawindowsizeseven.(b)Aftersevenframessentandreceived,butnotacknowledged.(c)Initialsituationwithawindowsizeoffour.(d)Afterfourframessentandreceived,butnotacknowledgedSequenceNumber,BuffersThemaximumwindowsizeshouldbeatmosthalftherangeofthesequencenumbersHowmanybuffersmustthereceiverhave?Thenumberofbuffersneededisequaltothewindowsize,nottotherangeofsequencenumbersSendWindow&ReceiveWindows

Ws+Wr<=2n Ws>=Wr

ACKTimerACKtimerAfteranin-sequencedataframearrives,anauxiliarytimerisstartedbystart_ack_timer.Ifnoreversetraffichaspresentedbeforethistimerexpires,aseparateACKframeissentNAKWheneverthereceiverhasreasontosuspectthatanerrorhasoccurred,itsendsNAKframebacktothesenderNAKframeisarequestforretransmissionTherearetwocaseswhenthereceivershouldbesuspiciousAdamagedframehasarrivedAframeotherthantheexpectedonearrivedAvoidmakingmultiplerequestsforretransmissionofthesameframeReceiverkeepstrackofwhetheraNAKhasalreadybeensentforagivenframeProtocol6:SelectiveRepeat發(fā)送窗口最大4，接收窗口最大4ContinuedContinuedContinued-3.5PerformanceofSlidingWindowProtocolsPerformanceStop-and-waitwithouterrorPerformanceStop-and-waitwithouterrorPerformanceStop-and-waitwitherrorPerformanceSlidewindowwithouterrorHomework172026,27,28,29,30,31,323.6ExampleDataLinkProtocolsExampleDataLinkProtocolsHDLC–High-LevelDataLinkControlTheDataLinkLayerintheInternetSLIP(SerialLineIP)PPP(Point-to-PointProtocol)HDLC(High-LevelDataLinkControl)HistoryIBMSDLCSynchronousDataLinkControlANSIADCCPAdvancedDataCommunicationControlProcedureISOHDLCHigh-levelDataLinkControlCCITT(ITU-T)LAPBLAP(LinkAccessProcedure)LAPB(LinkAccessProcedure–Balancedmode)LAPD(IDSND-Channel)HDLCStationTypesPrimarystationControlsoperationoflinkFramesissuedarecalledcommandsMaintainsseparatelogicallinktoeachsecondarystationSecondarystationUndercontrolofprimarystationFramesissuedcalledresponsesCombinedstationMayissuecommandsandresponsesHDLCLinkConfigurationsUnbalancedOneprimaryandoneormoresecondarystationsSupportsfull-duplexandhalf-duplexBalancedTwocombinedstationsSupportsfull-duplexandhalf-duplexHDLCFrameformatFrameformatforbit-orientedprotocols.HDLCFramesControlfieldof(a)Aninformationframe.(I)(b)Asupervisoryframe.(RR/RNR/REJ/SREJ)(c)Anunnumberedframe.(SABM,UA,DISC,FRMR)FirstoneortwobitsofcontrolfiledidentifyframetypeI-frameIfthefirstbitofthecontrolfieldis0,thismeanstheframeisanI-frame.3-bitN(S)1-bitP/F3-bitN(R)S-frameControlFieldIfthefirst2bitsofthecontrolfieldare10,thismeanstheframeisanS-frame.CodeRR,RNR,REJ,SREJ(3-bitN(R))將ACK幀分兩類(RR/RNR),將NAK幀分兩類(REJ/SREJ),why?U-frameCodingU-frame建立連接SABM/SABME/SNRM/SNRME（應(yīng)答UA)斷開連接DISC（應(yīng)答UA)FRMR幀（FrameReject)indicatethataframewithacorrectchecksumbutimpossiblesemanticsarrivedUI幀(UnnumberedInformation)無編號數(shù)據(jù)幀，可以含有較長的數(shù)據(jù)域可用UI幀在鏈路層兩端提供“無連接-不可靠”數(shù)據(jù)傳輸P/FBitUsedependsoncontext

UnbalancedconfigurationPoll:InvitetheterminaltosenddataFinal:Alltheframessentbytheterminal,exceptthefinalone,havetheP/Fbitsetto0.Thefinaloneis1BalancedconfigurationCommand(Pbit):P=1tosolicit(poll)responsefrompeerResponse(Fbit):F=1indicatesresponsetosolicitingcommand

ForcetheothermachinetosendaSupervisoryframeimmediatelyratherthanwaitingforreversetrafficontowhichtopiggybackthewindowinformationACKFrame:RR&RNRRR:ReceiverReadyACKframeusedtoindicatetheN(R)frameexpectedThisframeisusedwhenthereisnoreversetraffictouseforpiggybackingRNR:ReceiverNotReadyItacknowledgesallframesuptobutnotincludingN(R),justasRRdoes,butittellsthesendertostopsending(Flowcontrol)NAKFrame:REJ&SREJREJ:RejectIndicatethatatransmissionerrorhasbeendetectedTheN(R)

fieldindicatesthefirstframeinsequencenotreceivedcorrectly(i.e.,theframetoberetransmitted)Thesenderisrequiredtoretransmitalloutstandingframesstartingat

N(R)

SREJ:SelectiveRejectCallsforretransmissionofonlytheframespecifiedbyN(R)Ifareceiverwishestobufferout-of-sequenceframesforpotentialfutureuse,itcanforcetheretransmissionofanyspecificframeusingSREJHDLCOperationExchangeofinformation,supervisoryandunnumberedframesInformation-datatobetransmittedtouserFlowanderrorcontrolpiggybackedoninformationframesSupervisory-ARQwhenpiggybacknotusedUnnumbered-supplementarylinkcontrolThreephrasesInitializationDatatransferDisconnectExampleofHDLCOperationExampleofHDLCOperationSLIP(SerialLineIP)SLIP–SerialLineInternetProtocolRFC1055Framing:Ch