计算机网路（第四版）英文课件chp3

*1TheDataLinkLayer

(数据链路层)Chapter323.1DataLinkLayerDesignIssuesServicesProvidedtotheNetworkLayer〔为网络层提供的效劳〕Framing〔帧〕ErrorControl〔过失控制〕FlowControl〔流量控制〕33.1.1ServicesprovidedtothenetworklayerUnacknowledgedconnectionlessservice〔无确认的无连接效劳〕Acknowledgedconnectionlessservice〔有确认的无连接效劳〕Acknowledgedconnection-orientedservice〔有确认的面向连接的效劳〕4FunctionsoftheDataLinkLayerProvideserviceinterfacetothenetworklayerDealingwithtransmissionerrorsRegulatingdataflowSlowreceiversnotswampedbyfastsenders5FunctionsoftheDataLinkLayer(2)Relationshipbetweenpacketsandframes.6ServicesProvidedtoNetworkLayer(a)Virtualcommunication.(b)Actualcommunication.7ServicesProvidedtoNetworkLayer(2)Placementofthedatalinkprotocol.8数据链路层的简单模型局域网广域网主机

H1主机

H2路由器

R1路由器

R2路由器

R3网局域网主机

H1

向

H2

发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动9数据链路层的简单模型(续〕局域网广域网主机

H1主机

H2路由器

R1路由器

R2路由器

R3网局域网主机

H1

向

H2

发送数据H1H2仅从数据链路层观察帧的流动链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3103.1.2FramingFramingmethod(成帧的方法):3〔1〕charactercount〔字符计数法〕-[seefig3-3]〔2〕Startingandendingcharacter,withcharacterstuffing〔带字符填充的首尾界符法〕-[seefig3-4]Frameflags:DLESTX(StartText),DLEETX(EndText)DLEindata(betweenflags):DLE-->DLEDLE,sothat:DLEETX-->DLEDLEETX 〔3〕Startingandendingflags,withbitstuffing〔带位填充的首尾界符法〕.-〔01111110〕-[seefig3-5]Physicallayercodingviolation〔1->高-低电平对，0->低-高电平对〕11Framing(2)Acharacterstream.(a)Withouterrors.(b)Withoneerror.12Framing(3)(a)Aframedelimitedbyflagbytes.(b)Fourexamplesofbytesequencesbeforeandafterstuffing.13Framing(4)Bitstuffing(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataastheyarestoredinreceiver’smemoryafterdestuffing.143.1DATALINKLAYERDESIGNISSUES3.1.3ErrorControl〔过失控制〕ErrordetectionErrorcorrectionRepeateddataframeLostframeTimer3.1.4FlowControl〔流量控制〕Tosolvetheproblemthatasenderwantstotransmitframesfasterthanthereceivercanacceptthem.Feedback-basedflowcontrolRate-basedflowcontrol153.2ErrorDetectionandCorrectionError-CorrectingCodes〔纠错码〕codeword〔码字〕Hammingdistance(10001001,10110001=>00111000,3)paritybit纠正d比特错需距离为2d+1比特的编码Error-DetectingCodes〔检错码〕polynomialcode〔cyclicredundancycode，CRCcode〕检测d比特错需距离为d+1比特的编码163.2.1Error-CorrectingCodes(*)UseofaHammingcodetocorrectbursterrors.173.2.2Error-DetectingCodesCalculationofthepolynomialcodechecksum多项式编码〔循环冗余码，CRC码〕生成多项式G(x)计算校验和的算法：-[seepage197]CRC-12=x12+x11+x3+x2+x1+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1结论：具有r检测位的多项式能够检测所有长度<=r的突发错误长度大于r+1的错误逃脱的概率为1/2r.DataCRC除法器余数0,acceptNot0,refuseDataCRCData00…0除法器CRCn位n+1位余数n位ReceiverSenderCRC产生器和校验器将一个n位的0串追加到数据单元,n的值为预先约定的除数位数减1，即除数为n+1位。用除数去除组成的新数，除的方法是二进制除法，所得的余数即为CRC。将由第二步得出n位的CRC替换数据单元末尾追加的n个0。数据单元的数据局部先到达接收方，然后是CRC到达。接收方将这些都看作是一个字串并用找出CRC余数所用的同一个除数去除这个字串。如果到达的字串没有过失，那么CRC校验器产生的余数为0，数据单元通过。如果在传送的过程中字串发生改变，相除的结果就产生一个非0的余数，数据单元就不能通过。20

1101010110

←

Q

商

除数

P→

←

2nM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数循环冗余检验的原理说明213.3ElementaryDataLinkProtocolsAnUnrestrictedSimplexProtocol〔一种无限制的单工协议〕ASimplexStop-and-WaitProtocol〔一种单工的停-等协议〕ASimplexProtocolforaNoisyChannel〔有噪声信道的单工协议〕进程(process)、分组(packet)和帧(frame)wait_for_event(&event),3events:frame_arrival:Receivedcorrectframecksum_err:Receivedframewithchecksumerrortimeout:Timeoutwhenwaitingacknowledgement AnUnrestrictedProtocolAsimplexStop-and-WaitProtocol Premise：ErrorfreeandtrafficsimplexSender： 〔1〕Getdataframefromhost； 〔2〕sendtobufferofdatalink； 〔3〕forwardthedataframe； 〔4〕waiting； 〔5〕Acknowledgefromreceiver,getnewdataframefromhost,thengotostep〔2〕。 Receiver： 〔1〕Waiting； 〔2〕getthedataframefromsender,putitintoreceivingbuffer; 〔3〕transferdataframetohost； 〔4〕sendamessagetosender,tellitthedataframehasbeenforwardedtothehost 〔5〕gotostep(1)。

AsimplexprotocolforaNoisyChannel

Apositivestop-and-waitprotocol sender： 〔1〕getdataframefromhosttobuffer。 〔2〕V(S)←0。 {发送状态变量初始化} 〔3〕N(S)←V(S)； {将发送状态变量的数值写入发送序号} 〔4〕senditonitsway。 〔5〕initializetimer。 {选择适当的超时重传时间tout} 〔6〕waiting {等待以下3个事件中最先出现的一个} 〔7〕ifgettheACK，then： getanewframefromthehost； V(S)←[1V(S)]； {更新发送状态变量，变为下一个序号} gotostep(3)。 〔8〕ifgettheNAK，thengotostep(4)。 {重传数据帧} 〔9〕iftimeout，thengotostep(4)。 {重传数据帧} receiver： 〔1〕V(R)←0。{接收状态变量初始化，其数值等于欲接收的数据帧的发送序号} 〔2〕waiting。 〔3〕ifframearrives,thenchsum-error当收到一个数据帧，就检查有无产生传输过失(如用CRC)。 ifnomistake，continue； otherwisegotostep(8)。 〔4〕ifN(S)=V(R)，thencontinue；{收到发送序号正确的数据帧} otherwiselosttheframe，gotostep(7)。 〔5〕Passthedatetothehost。 〔6〕V(R)←[1V(R)]。{更新接收状态变量，准备接收下一个数据帧} 〔7〕sendaACKtosender，gotostep(2)。 〔8〕sendaNAKtosender，gotostep(2)。32333.4SlidingWindowProtocols

〔滑动窗口协议〕Bidirectionaltransmission,piggybacking〔捎带〕,betteruseofavailablebandwidthslidewindowsendingwindow:asetofsequencenumberscorrespondingtoframeitispermittedtosendforsenderreceivingwindow:correspondingtothesetofframeswhichispermittedtoacceptforreceiver34SlidingWindowProtocols(2)AOne-BitSlidingWindowProtocolAProtocolUsingGoBackN〔后退n帧〕AProtocolUsingSelectiveRepeat〔选择性重传〕35SlidingWindowProtocols(3)Aslidingwindowofsize1,witha3-bitsequencenumber.(a)Initially.(b)Afterthefirstframehasbeensent.(c)Afterthefirstframehasbeenreceived.(d)Afterthefirstacknowledgementhasbeenreceived.3637AOne-BitSlidingWindowProtocol(2)

Twoscenariosforprotocol4.(a)Normalcase.(b)Abnormalcase.Thenotationis(seq,ack,packetnumber).Anasterisk(*)indicateswhereanetworklayeracceptsapacket.38393.4.2AProtocolUsingGoBackNPipelininganderrorrecovery.Effectonanerrorwhen(a)Receiver’swindowsizeis1.(b)Receiver’swindowsizeislarge.40回退n〔gobackn〕41SlidingWindowProtocolUsingGoBackN(2)接收窗口大小为W=1抛弃所有后续的帧最多允许有MAX_SEQ帧未被确认Stop-and-waitisnotfitfulforchannelwhichhaslonground-tripdelay,e.g.Satellitechannel,270msBidirectionaltransmission,noisychannel,Discardrestrictedcondition:networklayerofsenderhasunlimiteddatatotransmitsizeofreceivingwindow=1,receiverdiscardsallsubsequentframesafteradamagedorlostdataframe.42SlidingWindowProtocolUsingGoBackN(3)MAX_SEQ+1distinctsequencenumbers(0,1,2,...MAX_SEQ),nomorethanMAX_SEQunacknowledgedframes,thesenderwindow<=MAX_SEQ.Why?ConsiderthefollowingscenariowithMAX_SEQ=7(asenderwindowofsizeeight):Thesendersendsframes0through7.Apiggybackedacknowledgementforframe7eventuallycomesbacktothesender.Thesendersendsanothereightframes,againwithsequencenumbers0through7.AlleightframesbelongingtothesecondbatchgetlostAlleightframesbelongingtothesecondbatcharrivesuccessfully.Anotherpiggybackedacknowledgementforframe7comein,ambiguitywillarisetosender:Alleightframesbelongingtothesecondbatchgetlost,ack=7Alleightframesbelongingtothesecondbatcharrivesuccessfully,ack=743SlidingWindowProtocolUsingGoBackN(4)AProtocolUsingGoBackn(whenthesizeofsenderwindow=7,noambiguity:Thesendersendsframes0through6Apiggybackedacknowledgementforframe6eventuallycomesbacktothesenderThesendersendsanother7frames:7,0,1,2,3,4,5,Frame7,0,1,2,3,4,5belongingtothesecondbatchgetlostFrame7,0,1,2,3,4,5belongingtothesecondbatcharriveAnotherpiggybackedacknowledgementcomesin,noambiguityFrame7,0,1,2,3,4,5

belongingtothesecondbatchgetlost,ack=6Frame7,0,1,2,3,4,5belongingtothesecondbatcharrive,ack=5theproblem:Sinceasendermayhavetoretransmitalltheunacknowledgedframesatafuturetime,itmusthangontoalltransmittedframesuntilitknowsforsurethattheyhavebeenacceptedbythereceiver.Noacknowledgedframeswithoutdata.44SlidingWindowProtocolUsingGoBackN(9)Simulationofmultipletimersinsoftware.453.4.3ASlidingWindowProtocolUsingSelectiveRepeat允许接收后续的帧〔接收窗口>1〕窗口大小为W<=(MAX_SEQ+1)/2所需缓冲器的数量=W所需计时器的数量=W否认性确认帧-NAK思考题46选择重传〔selectiverepeat〕47ASlidingWindowProtocolUsingSelectiveRepeat(6)(a)Initialsituationwithawindowsizeseven.(b)Aftersevenframessentandreceived,butnotacknowledged.(c)Initialsituationwithawindowsizeoffour.(d)Afterfourframessentandreceived,butnotacknowledged.482023/1/1249Performance：性能比较Stop-and-wait慢只在特定情形有用Slidingwindow快高速网络必须2023/1/1250性能比较的图示2023/1/1251滑动窗口协议的重要性同时发送增加了网络吞吐量流控制如何加速？ Tw=min(B,TGW〕 whereB：硬件带宽TW：滑动窗口协议吞吐量TG：停走协议吞吐量W：窗口大小523.6ExampleDataLinkProtocolsHDLC–High-LevelDataLinkControl〔高级数据链路控制〕TheDataLinkLayerintheInternet〔因特网中的数据链路层〕533.6.2TheDataLinkLayerintheInternetAhomepersonalcomputeractingasaninternethost.54用户拨号入网的示意图路由器调制解调器调制解调器因特网效劳提供者(ISP)用户家庭拨号线使用TCP/IP的

PPP连接使用TCP/IP的客户进程路由选择进程至因特网…PC机55PPP协议1992年制订了PPP协议。经过1993年和1994年的修订，现在的PPP协议已成为因特网的正式标准[RFC1661]。PPP协议有三个组成局部一个将IP数据报封装到串行链路的方法。链路控制协议LCP(LinkControlProtocol)。网络控制协议NCP(NetworkControlProtocol)。56PPP协议的帧格式PPP的帧格式和HDLC的相似。标志字段F仍为0x7E〔符号“0x〞表示后面的字符是用十六进制表示。十六进制的7E的二进制表示是01111110〕。地址字段A只置为0xFF。地址字段实际上并不起作用。控制字段C通常置为0x03。PPP是面向字节的，所有的PPP帧的长度都是整数字节。57PPP协议的帧格式PPP有一个2个字节的协议字段。当协议字段为0x0021时，PPP帧的信息字段就是IP数据报。假设为0xC021,那么信息字段是PPP链路控制数据。假设为0x8021，那么表示这是网络控制数据。IP数据报1211字节12不超过1500字节PPP帧先发送7EFF03FACFCSF7E协议信息部分首部尾部58PPP—PointtoPointProtocol

〔点到点协议〕(2)Support：errordetection、multipleprotocols(IP,IPX,AppleTalk,XNS,...),allowsIPaddressto