计算机网络技术(3)课件(PPT 79页)

1、第三章 数据链路层协议及技术成帧 差错检测与差错控制 链路层协议第1页，共79页。3.1 数据链路层基本概念链路：一条无源的点到点的物理线路段数据链路：链路规程（控制数据传输）。一条物理连接加上为实现数据可靠传输所配置的硬件和相关的通信协议）数据链路层的作用：通过一些数据链路层协议（链路控制规程），在不太可靠的物理链路上实现可靠的数据传输第2页，共79页。数据链路层功能和提供的服务数据链路层的协议数据单元PDU:帧任务是将网络层的数据组合成帧，加上一定的校验，然后交物理层用某种信号表示二进制数据位送到目的计算机，并通过目的计算机的物理层和数据链路层送到网络层，为网络层提供了一条可靠的数据链路提

2、供服务（通过有无连接，有无确认区分）：无确认无连接服务例如：局域网1）共享信道无需连接2）传输出错或丢失由上层恢复3）信道比较好，数据传输的误码率比较低无确认并非不可靠，其可靠性由上层负责第3页，共79页。有确认无连接：使用前不建立连接，但每帧传输必须得到确认适合信号传播时延比较大，线路状态不一定很可靠的情况例如：无线通信：建立连接降低了利用率(540ms)；误码率相对高，需确认）：用于不可靠的通道传输；有确认有连接（电话，大多数广域网的通信子网的DLL）第4页，共79页。数据链路层可靠传输保证直接相连的两台主机的可靠性传输1）将传输的数据组合成同一的格式：帧2）数据校验和反馈重发机制3）流量

3、控制第5页，共79页。3.2 成帧（framing)帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错导致前一个帧丢失，也必须能识别下一个帧(错误发生之后重新同步)。成帧方法：字符计数法带字符填充的首尾字符定界法带位填充的首尾标记定界法物理层编码违例法第6页，共79页。3.2.1 字符计数法帧头中用一个字节来表示整个帧的字符个数若计数出错，对本帧和后面的帧有影响。（错误没有办法恢复）第7页，共79页。3.2.2 带字符填充的首尾字符定界法比如以ASCII字符DLE和STX作为帧的头部，DLE和ETX作为帧的尾部（DLE=10H,STX=02H,ETX=03H）（DLE:data lin

4、k escape表转义字符，STX:start of text,ETX:end of text)技术：如何避免字符数据可能与帧的头尾标志相同？ 发送方在数据中遇到DLE时，自动在其前后插入一个DLE 接收方在数据中遇到单个DLE时，可确定帧界，遇到2个 DLE时，自动删除一个DLE第8页，共79页。3.2.2 带字符填充的首尾字符定界法用途：帧同步用于面向字符型协议，比如PPP，IBM的二进制同步通信协议BSC不足：依靠字节模式，但不是所有的字符编码都是采用8位模式，unicode采用16位编码，如何允许任意长度的字符编码的帧同步技术呢？第9页，共79页。3.2.3 带位填充的首尾字符定界法帧

5、的起始和结束都用一个特殊的位串“01111110”，称为标记（flag）如果由于干扰，一个帧标志没有正确接收，则继续扫描接收串，一旦扫描到，表示新的一帧的开始，具有再同步能力“0”比特插入删除技术（透明传输）：发送方5个“1”后插入“0”,接收方删除第5个“1”后的“0”第10页，共79页。3.2.4 物理层编码违例法Manchester encoding or Differential Manchester encoding 用high-low pair/low-high pair 表示1/0，high-high/low-low不表示数据，可以用来做定界符。令牌环网中使用编码违例格式第11页

6、，共79页。3.3 差错产生与差错控制方法3.3.1 为什么要设计数据链路层在原始物理传输线路上传输数据信号是有差错的；设计数据链路层的主要目的： 将有差错的物理线路改进成无差错的数据链路； 方法 差错检测 差错控制（重发和编序号） 流量控制（滑动窗口协议）作用：改善数据传输质量，向网络层提供高质量的服务。第12页，共79页。差错产生的原因和差错类型传输差错 通过通信信道后接收的数据与发送数据 不一致的现象;差错控制 检查是否出现差错以及如何纠正差错；通信信道的噪声分为两类：热噪声（传输介质导体的电子热运动形成）和冲击噪声（外界电磁干扰形成）；由热噪声引起的差错是随机差错，或随机错，一般出错数

7、据位不相邻 ；冲击噪声引起的差错是突发差错，或突发错，一般会引起相邻多个数据位出错 ；引起突发差错的位长称为突发长度；在通信过程中产生的传输差错，是由随机差错与突发差错共同构成的。第13页，共79页。差错评价指标及差错控制方法评价指标：误码率：错传的码元数与所传输码元总数之比误比特率：错传的比特数与所传输总比特数之比。在二进制码元时，误比特流误码率差错控制基本方式：反馈纠错：在接收端能发现差错，但不能确定错码的位置，通过反馈信息请求发送端重发，直到接收端肯定确认为止。适合双工通信和非实时通信系统前向纠错：在接收端不但能发现错码，还能确定错码位置，并纠正错码。适合单工通信和实时通信系统混合纠错：

8、少量差错在接收端自动纠正，超出自纠正能力，通过反馈请求重发第14页，共79页。误码控制基本原理为了能判断传送的信息数据是否有误，在传送时增加必要的附加判断数据，在不发生误码的情况之下，附加判断数据是完全多余的，但如果发生误码，即可利用信息数据与附加数据之间的特定关系来实现检错和纠错为了使数据码有一定的检错和纠错能力，应当按一定的规则在数据码的基础上增加一些冗余码第15页，共79页。码字的检错与纠错能力码字（n位）数据码（m位）冗余码（r位）海明距离：两个码字之间对应码元位的不同码元的个数。比如：与，有3位不同，海明距离3码字编码的海明距离：对于一种码字编码，在这个码字集合中，可得到所有任意两个

9、码字的海明距离，其中最小的海明距离称为该码字编码的海明距离d第16页，共79页。检错编码和纠错编码使用3位二进制来对8个码字进行编码不能检测出错使用4位二进制来对8个码字进行编码能检测奇数位出错，但不能纠错海明距离（码距）为3及以上，才能够进行纠错第17页，共79页。码距与纠错检错位的关系一般情况下，冗余位越多，检错纠错能力越强，但相应编码效率也随之降低了L-1=C+D L为码距，D为可以检测出的错误位数，C为可以纠正的错误位数，并且有DC。第18页，共79页。常用检错码和纠错码检错码：校验和奇偶校验码循环冗余编码CRC目前应用最广的检错码编码方法之一纠错码：海明码第19页，共79页。3.3.

10、1 校验和算法简单，容易实现，但检错率不高将发送的数据看成是二进制整数序列，并划分成一段段规定的长度（8bbit,16bit,32bit）计算他们的和，若校验和大于规定的长度，则将进位加到最后的校验和中。将校验和和数据一起发送。在接收端，重新计算校验和与原校验和比较。比如传输“HELLO WORLD.”以16bit为例4865H+6C6CH+6F20H+776FH+726CH+642EH+进位71FCH第20页，共79页。3.3.2 奇偶检验通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法.例：发送端发送ASCII码，在传输的过程中由于干扰，接收端接收的是。那么系统能不能知道出现出

11、错了呢？如果发送端发送的是ASCII码数据奇校验位，即，那么接收端接收的是，那么系统能不能知道出错了呢？若接收到的数据是，那么系统如何判断？第21页，共79页。3.3.3 循环冗余码CRC码特点：实现容易，检错能力强，广泛使用。常结合反馈重发法来保证信息的可靠传输。码字组成：编码和解码的计算采用二进制比特序列多项式二进制比特序列多项式第22页，共79页。例：若数据码110011，可以表示为：M(X)=X5+X4+X+1生成多项式G(X):G(X)被通信双方事先共同选定使用：发送端：通过G(X)生成校验码接收端：通过G(X)校验接收的码字 对于多项式的运算：采用模2计算（加法不进，减法不借位）；

12、加减法是一样的模2计算即是异或运算第23页，共79页。发送端：1、生成校验码R(X):把要发送的数据码去除G(X)，所得的余数值T(X)就是循环冗余码2、发送 ：实际上，把CRC校验码R(X)附加到数据码M(X)的后面，然后发送传输接收端：第24页，共79页。CRC举例数据码M(X)=110011,利用生成多项式G(X)=X4+X3+1,求CRC校验码为多少？第25页，共79页。流行的生成多项式有：CRC-12 G（x）= x12+x11+x3+x2+x+1CRC-16 G（x）= x16+x15+x2+1CRC-CCITT G（x）= x16+x12+x5+1CRC-32 G（x）= x32

13、+x26+x23+x22+x16+x12+x11+ x10 +x8+x7+x5+x4 + x2+x+1检测能力： 所有单个错、奇数个错和离散的二位错 所有长度r位的突发差错CRC实现：硬件：采用多段移位寄存器或异或门组成CRC校验电路来实现软件：通过快速的CRC检验软件来实现第26页，共79页。3.4 差错控制和流量控制数据链路协议主要考虑的问题：1、避免所传送的数据可能出现差错和丢失2、使发方发送数据的速率适应收方的接收能力第27页，共79页。理想化的数据传输假设1：所传送的数据既不会出现差错和也不会丢失（不考虑差错控制问题）假设2：接收端的数据接收速率足够快，有能力接收发送端的数据发送率（

14、不考虑流量控制问题）在理想化的条件下，数据链路层不需要：1、差错控制协议2、流量控制协议 就可保证数据的正确传输第28页，共79页。3.4.1 最简单流量控制的停止等待协议保留假设1，去掉假设2。考虑流量控制问题流量控制协议使发送端发送数据的速率适应接收端的接收能力最简单流量控制协议（发送方和接收方各有一个帧的缓冲空间）发送节点：1、从数据链路层的发送缓存中取一个数据帧2、发送这个数据帧3、等待4、若收到由接收端的应答信息，转1接收节点：1、等待2、接收由发送端发来的数据帧3、将其存入数据链路层的接收缓存4、发送应答信息，表示数据帧已接收，转到1第29页，共79页。3.4.2实用的停止等待协议

15、ARQ去掉假设1，去掉假设2考虑差错控制问题差错控制协议考虑流量控制问题流量控制协议初步协议：1、发送端发送数据帧后，等待接收端的应答帧2、接收端收到数据帧后，通过CRC校验，如果无差错，回送一个确认帧ACK，否则，回送一个否认帧NAK3、发送端收到应答帧，如果是ACK，发送下一数据帧，如果是NAK，重发数据帧 协议有什么缺陷呢？第30页，共79页。死锁现象缺陷1：数据帧丢失当出现帧丢失时，发送端永远等待下去，如何解决？解决方法：发送端设立一个超时计时器，发送完一个数据帧时，就启动它，如果在规定时间内得不到应答帧，判定为超时，重传数据tout称为重传时间第31页，共79页。重复帧差错缺陷2：应

16、答帧丢失，产生重复帧若应答帧丢失，按照超时重发方法，接收端将接收到重复帧，如何解决？解决方法：给每个数据帧附加不同的发送序号Ns,如果接收端收到相同序号的数据帧，则丢弃，并回送一个ACK发送序号需要多少位？对于ARQ协议，发送序号有1和0即可（只需1bit)，每发一个新的数据帧，发送序号和上次发送不一样第32页，共79页。停止等待协议的信道利用率单程传输时延Td,数据帧发送时间Tf,数据传输率C，数据帧长度L，信道利用率Cr(总时间等待时间)/传输一帧的总时间忽略应答帧长度和处理时间： Cr=Tf/(Tf+2Td)=1/(1+2TdC/L)第33页，共79页。卫星信道传输速率50kbps,往返

17、传输延迟500ms，若传1000bit的帧，使用停止等待协议，则传输一个帧所需时间为： 发送时间信息信道延迟确认信道延迟1000bit/50kbps+250ms+250ms=520ms 信道利用率20/520约为4%一般情况：信道速率b比特/秒，帧长度L比特，往返传输延迟R秒，则信道利用率为 （L/b）/（L/b+R）=l/(l+Rb/L) 结论：传输延迟大（R)、信道带宽高、帧短时 信道利用率低第34页，共79页。3.4.3 连续ARQ目的：提高信道利用率方法：发送端发送完一个数据帧后，不停下来等待应答帧，而是连续再发送数据帧，当收到否认帧NAK时，再控制重发实现要求： 数据帧需附加发送序号

18、信息。否认帧附加出错的数据帧发送序号常用协议 回退N帧ARQ协议 选择重发ARQ协议第35页，共79页。回退N帧ARQ协议方式1：反馈否认帧NAK（含出错的数据帧发送序号）。再从出错的数据帧开始重传要求：发送端要求有一个能存储N个数据帧的缓冲区，接收端只需能存储一个数据帧的缓冲（接收端的数据链路层协议要求将分组按次序递交给网络层）第36页，共79页。方式2：不反馈否认帧NAK。发送端采用超时机制。发送端每发送一个数据帧就启动该帧计时器，当收到确认帧后，计时器复位；如果知道超时还没有收到确认帧，则重发该数据帧及后续的帧第37页，共79页。选择重传ARQ协议回退N帧协议，当信道误码率较高时，对损坏

19、帧和非损坏帧的重传非常的多，浪费带宽目的：进一步提高信道利用率方法：只重传出现差错的数据帧或者超时的数据帧要求：在接收端要设置具有相当容量的缓存空间第38页，共79页。选择重发ARQ协议工作原理示意图多个数据帧出错情况第39页，共79页。3.5 滑动窗口协议对于连续ARQ协议，采用了发送端不等待确认帧返回就可以连续发送帧，存在问题：1、当未被确认的数据帧数目太多时，只要有一帧出错，就有很多数据帧需要重传，增大了开销2、为了对发送出去的大量未被确认的数据帧进行编号，每个数据帧的发送需要也要占用较多的比特数，又增大了开销滑动窗口协议：对发送端已发送出去但未被确认的帧的数目加以限制，在发送端和接收端

20、分别设置发送窗口和接收窗口第40页，共79页。3.5.1发送窗口（发送端）目的：对发送端进行流量控制发送窗口大小Ws：在还没有收到应答帧的情况下，发送端最多可以连续发送数据帧的个数发送序号：一般采用n位bit进行编号，若n=3，则编号为（07）第41页，共79页。发送端只能连续发送窗口内的数据帧每收到一个确认帧后，发送窗口的前后沿顺时针旋转一个号，并可以发送一个新的数据帧若未应答帧的数目等于发送窗口大小时，便停止发送新的数据帧第42页，共79页。3.5.2 接收窗口（接收端）目的：用来控制可以接收哪些数据帧而不可以接收哪些帧接收窗口Wr:只有当收到的数据帧的发送序号落入接收窗口内，才允许将该数

21、据帧收下，否则，丢弃若Wr1，意味着只能按顺序接收数据帧若Wr较大，有可能会出现数据帧的失序第43页，共79页。应答帧丢失情况 第44页，共79页。应答帧被“篡改”情况：ACK-NAK 第45页，共79页。应答帧被“篡改”情况：NAK-ACK 第46页，共79页。3.5.3 重叠问题在接收前后，接收窗口范围内的有效序号出现重叠第47页，共79页。避免重叠问题为了避免重叠问题，接收窗口大小Wr=2n/2第48页，共79页。发送窗口的最大尺寸值发送窗口大小Wr=2Td+Tf时：Cr约为100当Ws*Tf1,接收窗口Wr=1 2、选择重发连续ARQ协议 发送窗口Ws1,接收窗口Wr1,且Wr=Ws第

22、54页，共79页。3.6 数据链路层协议(广域网) 按所传输信息的基本单位分：面向字符(BSC,ARPA,DLC，PPP， DDCMP)面向比特（HDLC,SDLC,ADCCP,LAPB,)发展IBM：最早数据链路层协议SDLC（synchronous data link control同步数据链路控制）协议美国国家标准协会ANSI对其作了修改成为高级数据通信控制规程ADCCPISO将其修改成高级数据链路控制HDLCCCITT在HDLC基础上修改，作为链路访问规程LAP，后来又修改为LAPB作为X.25网的第二层协议IEEE将SDLC修改成LAN的LLC子层标准称为IEEE802.2 所有面向

23、位的协议基本原理相同，相互之间只是实现方法不同第55页，共79页。高级数据链路控制HDLC协议的目的是提供一种通信准则，满足计算机、终端之间数据通信以及计算机通信子网节点间的数据通信。适用范围：计算机计算机、计算机终端、终端终端三种类型的通信站：主站：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）次站：主要功能是接收命令，发送响应，配合主站完成链路的控制复合站：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制第56页，共79页。3.6.1 HDLC的链路构型非平衡配置（主从配置）主站控制整个链路工作，主站发出的帧叫命令；从站发出

24、的帧叫响应。适合把智能和半智能的终端连接到计算机第57页，共79页。HDLC的链路构型平衡配置复合站具有主站和从站的功能。地位平等。适合于计算机和计算机之间的连接不支持多点平衡配置第58页，共79页。3.6.2 HDLC的基本操作模式正常响应模式NRM适合于非平衡构型。只有当从站得到主站的许可（主站向从站发出探询）后，从站才能发起一次一帧或多帧数据的传输响应异步响应模式ARM适用于点点式非平衡构型。从站不必等待主站的许可，就可发起一次传输。但主站和从站的地位不变异步平衡模式ABM适合于复合站的平衡构型。双方具有同等能力，任何一个复合站可随时传输帧第59页，共79页。3.6.3 HDLC的帧的类

25、型信息帧（I帧）用来传输用户数据监控帧（S帧）用来传输控制信息（如流量和差错控制信息）无序号帧（U帧）用来传输网络管理信息第60页，共79页。HDLC的帧结构帧标志（flag） 定界符为7EH（零比特填充法）地址域（address）1)使用不平衡方式传送数据时（采用NRM和ARM），地址字段总是写入从站的地址；2)使用平衡方式时（采用ABM），地址字段总是写入应答站的地址。3)有效地址为254个（通常为8位，可扩展到16位） 全1的8位地址表示广播（所有次站接收） 全0的8位地址是无效地址数据域：任意比特串或字符串（有上限）I帧和U帧第61页，共79页。HDLC的帧结构校验和（checksum

26、） 循环冗余校验CRC，生成多项式，为透明传输插入的“0”不在校验范围内第62页，共79页。HDLC帧的控制域控制域：标识帧的类型和功能，使对方站执行特定的操作，是HDLC的关键字段，许多重要功能由此字段实现第63页，共79页。HDLC帧的控制域(信息帧)N(s)-发送序号 表示当前发送的信息帧的序号，使用滑动窗口技术，3位序号N（r）-接收序号（确认序号） 约定：表示本站期望收到的帧的发送序号，而不是最后一个已收到的帧序号它具有捎带确认功能第64页，共79页。 第65页，共79页。HDLC帧的控制域监控帧(48bit) 第66页，共79页。HDLC进行询问示例：从站数据主站 第67页，共79

27、页。HDLC进行询问示例：主站数据从站 第68页，共79页。HDLC帧的控制域无序号帧 第69页，共79页。 第70页，共79页。3.7 因特网的数据链路层因特网模型1：因特网中的网络互联（路由器之间是通过点到点来进行连接的）因特网模型2：因特网中家庭用户入网：用户通过拨号与ISP连接后，采用点到点方式连接第71页，共79页。第72页，共79页。因特网的点对点协议PPP1992年，PPP：point-to-point protocol，RFC1661、RFC1662、RFC1663 1）PPP协议可以在同一条链路上同时支持多种网络层协议（IP,IPX)2）PPP协议能够在多种不同类型的链路上传输,并且对每中类型的点对点链路设置了最大传输单元MTU)支持远程分配地址)支持验证3）PPP协议不提供纠错，只进行检错，无序号，无流量控制，所以是不可靠的传输协议4）不支持多点传输，只支持全双工链路第73页，共79页。3.7.1 PPP协议的三个组成部分PPP提供了串行点对点链路上传输数据报的方法，包含了以下几个部分：1、封装方法一个将IP数据报封到串行链路的方法。PPP既支持异步