循环冗余码CRC课件.ppt

1、*Network Center(NC)of Qinghai Normal University CRC码算法码算法设G(x)为 r 阶，在帧的末尾加 r 个0，使帧为m+r位，相应多项式为xrM(x)；按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串；按模2减法从对应于xrM(x)的位串中减去余数（等于或小于r位），结果就是要传送的带校验和的多项式T(x)。*Network Center(NC)of Qinghai Normal University CRC的检错能力的检错能力发送：T(x)；接收：T(x)+E(x)；余数(T(x)+E(x)/G(x)=0+余数(E(x)/G(x)

2、若 余数(E(x)/G(x)=0，则差错不能发现；否则，可以发现。四个多项式已成为国际标准CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1CRC-32 硬件实现CRC校验。*Network Center(NC)of Qinghai Normal University101000110100000110101110101110101011011101111010111101011010111111011010110110011010111001011010101110n信息位串1010001101，K(x)x9+x

3、7+x3+x2+1n生成多项式110101，G(x)x5+x4+x2+1CRC计算例程*Network Center(NC)of Qinghai Normal UniversityCRC检测方法的特点 相比于奇偶校验法，CRC校验码的检错能力很强，而奇偶校验法实现简单，检错能力低，一般只适合于通信要求较低环境；CRC校验码除了能查出离散错外，还能检查出突发错，主要包括：所有单个错；全部离散的二位错；全部奇数个错；全部长度小于或等于K位的突发错（K是生成多项式的最高幂）；*Network Center(NC)of Qinghai Normal University检验和(checksum)算法|

4、检验字段初值置0；|待检验的数据拆分成一个个与检验字段等长的分片，不足部分补0以满足长度要求；|将所有分片逐位取反，并连续累加逐位取反，并连续累加，丢弃最高进位；|计算结果置入检验字段；|填充的0仅参与计算，不参与传输；|检验字段自身不参与计算；|接收段执行相同的过程，并将计算结果和传输过来的检验和进行比较以决定数据是否出现差错；|适用于高层的字节型协议，如适用于高层的字节型协议，如IP、TCP、UDP等等；|常见分片长度：常见分片长度：8位、位、16位和位和32位。位。*Network Center(NC)of Qinghai Normal University检验和算法举例 待传输数据为：

5、10010100,01110110,1100 计算过程(10010100)+(01110110)=11110100 11110100+(11000000)=00110011 带检验和的传输数据是 10010100,01110110,1100 00110011*Network Center(NC)of Qinghai Normal University数据链路层通信模型数据链路层通信模型帧AP1缓存发送方AP2缓存接收方数据链路高层数据链路主机A主机B层*Network Center(NC)of Qinghai Normal University数据链路层控制机制数据链路层功能：通过该层协议的作

6、用，在一条不太可靠的通讯链路上实现可靠的数据传输；数据链路：在数据链路层，通讯的对等实体之间的数据传输通道，包括物理链路和必要的传输控制规程；理想的数据链路基于以下两个假设：不管发方以多快的速率发送数据，收方总能够来得及接收、处理并上交。也就是说收方有足够的接收缓存区和处理速度；链路是理想的传输通道，传输的任何数据既不会出现差错也不会丢失；*Network Center(NC)of Qinghai Normal University数据链路层控制机制 流量控制：保证发送数据在如何情况下都不会“淹没”收方接收缓存区，而且还应使传输达到理想的吞吐率，由收方控制发方的数据流量是计算机网络中流量控制的

7、一个基本思路；一个重要的方法是滑动窗口机制。差错控制：使得链路传输出现差错时等到补救。主要有两种差错发生，帧丢失和帧损坏。基本方式是确定重发机制（反馈重发纠错）数据链路层控制机制*Network Center(NC)of Qinghai Normal University4.5 滑动窗口机制机制：在发送方和接收方分别设置发送窗口和接收窗口，在数据传输过程中受控的向前滑动，从而控制传输过程。发送窗口：对发方进行流量控制，其大小WT指明在收到对方ACK之前发方最多可以发送多少个数据帧，落在窗口内的帧可以连续发送。接收窗口：控制哪些数据帧可以接收，只有到达的数据帧的序号落在接收窗口内时才可以被接收，

8、否则将被丢弃。当收方收到一个有序且无差错的帧后，接收窗口想起滑动，准备接收下一帧，并向发方发送一个确认（ACK）。为了提高效率收方可以采用累积确认或捎带确认。*Network Center(NC)of Qinghai Normal University发送方的滑动窗口作用设发送序号用3个比特编码，WT5*Network Center(NC)of Qinghai Normal University4.6 停等协议 差错控制的基本方式是确认重发机制，即反馈重发纠错，收方对收到的数据予以某种形式的反馈信息，发方根据反馈信息对出错的帧进行重发。一般基于以下措施：差错发现确认ACK累积确认负确认（NAK

9、）超时重发 确认重发机制又称为自动请求重发（ARQ），根据确认重发方式不同，分为停等ARQ、回退-N ARQ、选择重传ARQ。*Network Center(NC)of Qinghai Normal University停等ARQ 停等ARQ机制：在发方发出一个数据帧后停下来不再发送，等待收方ACK到达后再发送下一帧。（实际使用滑动窗口技术，发送窗口WT=1，接收窗口也是1）处理的差错问题：收方收到发来的数据帧，但检测出帧有差错；发方发出的数据帧丢失，收方不可能发出ACK；收方收到数据帧，但ACK丢失；（重复帧处理，对数据帧和确认帧边上序号，对于停等ARQ，用0和1交替编号。发方正确收到0/1

10、号数据帧，发回ACK1/ACK0，确认序号表明期待收到的下一个序号）*Network Center(NC)of Qinghai Normal University在无差错的正常情况下，停等ARQ把流量控制在每往返时间一个数据帧的水平，一个往返时间为：TDATA+TACK+2+TPRO链路利用率=TDATA/(TDATA+TACK+2+TPRO)TDATA/(TDATA+2)=1/(1+2)=/TDATA=链路比特长度/帧比特长度出错差错而重传情况下，停等ARQ引起的重传时间等于超时重传的定时时间TOUT解决链路利用率低的办法：回退-N ARQ和选择重传ARQ停等ARQ的效率分析*Network

11、 Center(NC)of Qinghai Normal University回退-N ARQ使用滑动窗口机制，WT1,WR=1,发方在每收到一个ACK之前不用等待，可以连续发送窗口内的多个帧，如果这时收到ACK，还可以则调整发方窗口，继续发送后续的帧；（连续ARQ）对于发送的每一帧设置超时定时器，发方发出一个帧后启动该定时器。若因帧效验错误、帧丢失、ACK丢失使定时器超时后还没有收到ACK，发方则要重复此帧，而且还必须重发此帧后面所有的已发帧;（回退-N ARQ）收方每收到一次失序的数据帧时都重发上次发送过的ACK，这可弥补上次已发送的确认帧的丢失；*Network Center(NC)of

12、 Qinghai Normal University回退-N ARQ*Network Center(NC)of Qinghai Normal University选择重传ARQ 接收窗口WR1,这样可以接收和保存正确到达的失序帧 出现传输差错时只重传出错的帧，后续的正确到达的帧不再重传，提高了信道的利用率 WT=WR=2n/2*Network Center(NC)of Qinghai Normal University4.5 停等协议前面介绍了帧边界的划分办法和检查帧是否错误的方法，如果帧在传输过程中出现错误，发送方就要重发错误帧，如何控制帧重发？简单停等协议 带流量控制的停等协议 带差错控制

13、的停等协议*Network Center(NC)of Qinghai Normal University简单停等协议假设：通信线路（信道）不损坏或丢失信息帧。发送数据的速率低于接受数据的速率理想传输协议、单工传输工作过程 发送程序:取数据，构成帧，发送帧；接收程序：等待，接收帧，送数据给高层。*Network Center(NC)of Qinghai Normal University带流量控制的停等协议无差错单工停等协议增加约束条件：接收方不能无休止接收。例如：缓冲区数量有限，接受速率比发送速率低等。解决办法：接收方每收到一个帧后，给发送方回送一个响应。接收方每收到一个帧后，给发送方回送一个

14、响应。工作过程发送程序：取数据，成帧，发送帧，等待响应帧；接收程序：等待，接收帧，送数据给高层，回送响应帧。*Network Center(NC)of Qinghai Normal University带差错控制的停等协议增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。使用正向应答正向应答+重发机制重发机制来解决差错的控制问题。使用超时重发计时器解决数据帧、确认帧丢失问题。为判断重复帧重复帧，必须在数据帧附加上不同的发送序号，数据序号采用循环序号循环序号机制。协议效率低协议效率低*Network Center(NC)of Qinghai Normal University数据帧差错情况

15、时间送主机BA(a)正常情况DATA0DATA1ACKACK送主机BA(b)数据帧出错DATA0DATA0NAKACK送主机出错BA(c)数据帧丢失DATA0DATA0ACK送主机丢失重传超时BA(d)确认帧丢失DATA0DATA0ACK重传超时ACK丢失送主机丢弃*Network Center(NC)of Qinghai Normal University有噪声信道单工停等协议流程图从网络层取数，成帧从网络层取数，成帧发送帧发送帧帧到否帧到否应答到否应答到否超时否超时否重复重复正确否正确否接收帧，送网络层接收帧，送网络层发应答发应答发送帧发送帧应答帧应答帧YNYNYNNY定时器定时器丢弃丢弃

16、丢弃丢弃NY注：P127*Network Center(NC)of Qinghai Normal University数据帧间时序关系BADATAACKDATA传播时延tp 传播时延tp 处理时延处理时延tpr 确认帧发送时间ta tpr 时间连续成功发送数据帧之间的最小时间间隔tT 数据帧发送时间tf 重传时间tout*Network Center(NC)of Qinghai Normal University停等协议的效率分析 重传时间 两个发送成功的数据帧间最小时间间隔 正确传送一个数据帧所需的平均时间:tavtT(1一个帧的平均重传次数)1(1)(1)niavTTTittpip ttp

17、*Network Center(NC)of Qinghai Normal University停等协议的效率分析（续）每秒成功发送的最大帧数就是链路的最大吞吐量max，显然：max1/tav(1-p)/tT。在发送方，设数据帧的实际到达率为（即每秒到达个帧），则不应超过最大吞吐量max，即(1-p)/tT，用时间tf进行规一化，得出规一化的吞吐量为：tf (1-p)/1，其中参数是tT的规一化时间：tT/tf 1。当重传时间小于发送时间时，1，此时的规一化吞吐量 (1-p)。针对单工协议效率低，引入连续ARQ和选择重传ARQ。*Network Center(NC)of Qinghai Norm

18、al University4.6 连续ARQ协议 1、工作原理连续停等协议是指不需要等前面帧的应答收到就可连续连续停等协议是指不需要等前面帧的应答收到就可连续不断的发下面的帧。不断的发下面的帧。1）全部重发流水线协议）全部重发流水线协议当一帧出错时，需重发出错帧之后的所有帧；接收方的缓冲区数量只需要一个。2）选择重发流水线协议）选择重发流水线协议当一帧出错时，只重发出错帧；接收方的缓冲区数量足够多。*Network Center(NC)of Qinghai Normal UniversityDATA0ACK1ACK1确认DATA0DATA1ACK2确认DATA1ACK2DATA2?DATA3D

19、ATA4DATA5重传时间tout ACK2DATA3乱序，丢弃，重传ACK2ACK2ACK2DATA4乱序，丢弃，重传ACK2DATA5乱序，丢弃，重传ACK2重传DATA2重传DATA3重传DATA4重传DATA5ACK3ACK4ACK5DATA6ACK3确认DATA2ACK4确认DATA3ACK5确认DATA4递交主机递交主机.连续ARQ协议的工作原理*Network Center(NC)of Qinghai Normal University滑动窗口协议 滑动窗口协议是对连续停等协议的改进，它能够控制已发送但未确认的数据帧的个数（滑动窗口的大小）。1.数据帧序号：0 2n-1；2.发送

20、窗口窗口尺寸：允许连续发送未应答的帧的个数数据允许发送的条件：上界下界 WR，WR=1 WT 2n-1 选择性重传 WT=WR WR 2n-1*Network Center(NC)of Qinghai Normal University4.8 HDLC协议面向比特的链路层协议面向比特的链路层协议IBM的SNA使用的数据链路协议SDLC（Synchronous Data Link Control protocol）；ISO修改SDLC，提出HDLC（High-level Data Link Control）；CCITT修改HDLC，提出LAP（Link Access Procedure）作为X.

21、25网络接口标准的一部分，后来改为LAPB。面向字符的链路层协议面向字符的链路层协议ISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM）IBM的二进制同步通信规程（BSC）DEC的数字数据通信报文协议（DDCMP）PPP Point-to-Point Protocol，Internet的协议。的协议。*Network Center(NC)of Qinghai Normal University4.8 HDLC HDLC广泛应用于X.25（是 ITU-T 为广域网 WAN 通信所建议的一种数据分组交换网络协议）及其他许多协议中。HDLC 是面向比特的同步通信协议，主要为全双工点对

22、点操作提供完整的数据透明度。HDLC LAPB 是一种高效协议，为确保流量控制、差错监测和恢复它要求额外开销最小。如果数据在两个方向上（全双工）相互传输，数据帧本身就会传送所需的信息从而确保数据完整性。HDLC 是 X.25 栈的一部分。*Network Center(NC)of Qinghai Normal University 数据站（简称站 station），由计算机和终端组成，负责发送和接收帧。HDLC涉及三种类型的站：主站（主站（primary stationprimary station）：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等

23、）；次站（次站（secondary stationsecondary station）：主要功能是接收命令，发送响应，配合主站完成链路的控制；组合站（组合站（combined stationcombined station）：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制。在一条公共通信链路上的在一条公共通信链路上的一个主战和一个次站一个主战和一个次站或多个站或多个站之间交换数据，这是之间交换数据，这是HDLC使用的典型链路结构。使用的典型链路结构。HDLC数据站种类*Network Center(NC)of Qinghai Normal UniversityHDLC的链路

24、配置 非平衡配置：用于点对点链路和多点链路，链路上的站点分为主站和从站；平衡配置：用于点对点链路，链路两端的站点平等；*Network Center(NC)of Qinghai Normal UniversityHDLC 操作模式正规响应模式正规响应模式 NRM（Normal Response Mode）适用于非平衡构型。只有当主站向次站发出探询后，次站才能获得传输帧的许可。异步响应模式异步响应模式 ARM（Asynchronous Response Mode）适用于非平衡构型。次站可以随时传输帧，不必等待主站的探询。异步平衡模式异步平衡模式 ABM（Asynchronous Balanced

25、 Mode）适用于通信双方都是组合站的平衡构型，双方具有同等能力。*Network Center(NC)of Qinghai Normal UniversityHDLC 的帧结构（1）定界符定界符8bit 01111110，采用0比特填充 地址域（地址域（Address）8bit 非平衡配置，写入从站地址，用来区分终端；平衡配置，写入应答站地址，全1表示广播地址，全0无效；*Network Center(NC)of Qinghai Normal UniversityHDLC 的帧结构（2）控制域控制域（Control）8b：用作序号、确认和其它目的 数据域（数据域（Data）任意信息，任意长度

26、（上层协议SDU有上限，比如标准的TCP/IP分组是576字节。减去分组中固定为40字节大小的地址信息及其它信息，最多还包含512字节的数据。）校验和（校验和（Checksum）CRC校验 生成多项式：CRC-CCITT=x16+x12+x5+1*Network Center(NC)of Qinghai Normal UniversityHDLC 的帧类型 信息帧（Information）：完成信息传送。监控帧（Supervisory）：差错控制和流量控制。无序号帧（Unnumbered）：链路控制管理。*Network Center(NC)of Qinghai Normal Universi

27、ty4.9 因特网数据链路接入控制 点到点通信的两种主要情形：点到点通信的两种主要情形：路由器到路由器 通过modem拨号上网，连到路由器或接入服务器*Network Center(NC)of Qinghai Normal UniversitySLIP串行线路网际协议 SLIP Serial Line IP 1984年，Rick Adams提出，RFC1055，发送原始IP包，用一个标记字节（0 xC0）来定界，采用字符填充技术；新版本提供TCP和IP头压缩技术，RFC 1144 存在的问题不提供差错校验只支持IPIP地址不能动态分配不提供身份认证多种版本并存，互连困难*Network Cen

28、ter(NC)of Qinghai Normal UniversityPPP 点到点协议点到点协议 PPP Point-to-Point Protocol 面向字符的链路协议 RFC 1661，RFC 1662，RFC 1663 与SLIP相比，PPP有很大的提高，提供差错校验、支持多种协议、允许动态分配IP地址、支持认证等。以帧为单位发送，而不是原始以帧为单位发送，而不是原始IP包包；链路控制协议链路控制协议LCP（Link Control Protocol）可使用多种物理层服务：modem，SDH/SONET等 网络控制协议网络控制协议NCP（Network Control Protoco

29、l）可支持多种网络层协议*Network Center(NC)of Qinghai Normal University标记域：标记域：0111111001111110，字符填充；，字符填充；地址域：地址域：1111111111111111控制域：缺省值为控制域：缺省值为0000001100000011，表示无序号帧，缺省情况下，表示无序号帧，缺省情况下，PPPPPP不不提供使用序号和确认的可靠传输；但是在不可靠线路上，也可使提供使用序号和确认的可靠传输；但是在不可靠线路上，也可使用有序号的可靠传输。用有序号的可靠传输。协议域：指示净负荷中是何种包，比如协议域：指示净负荷中是何种包，比如IPIP

30、，IPXIPX等。缺省大小为等。缺省大小为2 2个字节。个字节。净负荷域：变长，缺省为净负荷域：变长，缺省为15001500字节；字节；校验和域：校验和域：2 2或或4 4个字节个字节PPP帧*Network Center(NC)of Qinghai Normal UniversityPPP通信过程 为了建立点对点链路通信，PPP 链路的每一端，必须首先发送 LCP 包以便设定和测试数据链路。在链路建立之后，LCP 可选设备才可以被认证。然后，PPP 必须发送 NCP 包以便选择和设定一个或更多的网络层协议。一旦每个被选择的网络层协议都被设定好了，来自每个网络层协议的数据报就能在链路上发送了。

31、链路将保持通信设定不变，直到外在的 LCP 和 NCP 关闭链路，或者是发生一些外部事件的时候（如休止状态的定时器期满或者网络管理员干涉）。*Network Center(NC)of Qinghai Normal UniversityPPP工作状态迁移*Network Center(NC)of Qinghai Normal University本章作业 有人认为：每一帧的结束处是一个标志字节，而下一个帧的有人认为：每一帧的结束处是一个标志字节，而下一个帧的开始处又是另外一个标志字节，这种方法非常浪费空间。用开始处又是另外一个标志字节，这种方法非常浪费空间。用一个标志字节就可以完成同样的任务，这

32、样就可以节省一个一个标志字节就可以完成同样的任务，这样就可以节省一个字节。你同意这种观点吗？字节。你同意这种观点吗？位串位串01110111110011111101需要在数据链路层上被发送，请需要在数据链路层上被发送，请问：经过位填充后实际被发送出去的什么？问：经过位填充后实际被发送出去的什么？奇偶检验的一个改进是按奇偶检验的一个改进是按n行、每行行、每行k位来传输数据，并且在位来传输数据，并且在每行和每列上加上奇偶位。其中右下角是一个检查它所在行每行和每列上加上奇偶位。其中右下角是一个检查它所在行和列的奇偶位。这种方案能够检测出所有的单个、和列的奇偶位。这种方案能够检测出所有的单个、2位和三

33、位位和三位错吗？错吗？利用利用CRC方法来传输位流方法来传输位流10011101，假设生成多项市是，请，假设生成多项市是，请给出实际被传输的位串。如果在传输过程中左边第三位发生给出实际被传输的位串。如果在传输过程中左边第三位发生错误。试证明：该错误可以在接收方被检测出来。错误。试证明：该错误可以在接收方被检测出来。数据链路层协议几乎总是将检错码放在尾部，而不是头部，数据链路层协议几乎总是将检错码放在尾部，而不是头部，请问这是什么原因？请问这是什么原因？试描述滑动窗口是如何实施流量控制的？试描述滑动窗口是如何实施流量控制的？假设有一个滑动窗口协议使用多位作为数据帧序列号，使得假设有一个滑动窗口协

34、议使用多位作为数据帧序列号，使得在接收方能够分辨出预期新发来的帧编号和那些重发的旧的在接收方能够分辨出预期新发来的帧编号和那些重发的旧的帧编号。那么，帧编号。那么，4个窗口边界及窗口大小必须保持什么样的关个窗口边界及窗口大小必须保持什么样的关系？系？一个信道的位速率为一个信道的位速率为4kbps，传输延迟为，传输延迟为20ms。请问帧的大。请问帧的大小在什么范围内，停等协议才可以获得至少小在什么范围内，停等协议才可以获得至少50%的传输效率？的传输效率？Network Center(NC)of Qinghai Normal Univrsity*精品课件精品课件！Network Center(N

35、C)of Qinghai Normal Univrsity*精品课件精品课件！*Network Center(NC)of Qinghai Normal University本章作业（续）一条一条3000公里长的公里长的T1干线被用来传输干线被用来传输64字节的帧，通信字节的帧，通信的两端使用了连续的两端使用了连续ARQ协议。如果信号传播速度为协议。如果信号传播速度为6s/公里，则序列号应该设置为多少位？公里，则序列号应该设置为多少位？利用地球同步卫星在一个利用地球同步卫星在一个1Mbps的信道上发送的信道上发送1000b的帧，的帧，该信道离开地球的传播延迟为该信道离开地球的传播延迟为270ms

36、。确认信息总是被捎。确认信息总是被捎带在数据帧上。头部非常短，使用带在数据帧上。头部非常短，使用3b序列号。在下面的协序列号。在下面的协议中，最大可获得的信道利用率是多少？（议中，最大可获得的信道利用率是多少？（a）停等协议；）停等协议；（b）连续）连续ARQ协议；（协议；（c）选择重传）选择重传ARQ协议。协议。使用一个使用一个64Kbps的无差错卫星信道发送的无差错卫星信道发送512字节的数据字节的数据帧，而在另外一个方向上返回的确认帧长度很短（可忽略帧，而在另外一个方向上返回的确认帧长度很短（可忽略不计）。对于窗口大小为不计）。对于窗口大小为1、7、15和和100的最大吞吐率是的最大吞吐

37、率是多少？多少？一条一条100公里长的电缆以公里长的电缆以T1速率传输数据，假设在电缆中速率传输数据，假设在电缆中的信号传播速度是光速的的信号传播速度是光速的2/3，试问：在该电缆中最多可，试问：在该电缆中最多可以填充多少个数据位？以填充多少个数据位？SLIP协议有哪些不足？协议有哪些不足？PPP基本上是以基本上是以HDLC为基础的，为基础的，HDLC使用了位填充技使用了位填充技术来防止负荷数据中偶尔出现标志字节，以避免引起混淆。术来防止负荷数据中偶尔出现标志字节，以避免引起混淆。请说明为什么请说明为什么PPP协议却使用了字节填充技术？协议却使用了字节填充技术？简述简述PPP协议的信道状态迁移过程？协议的信道状态迁移过程？