《计算机网络基础》 第3章 流量控制和差错控制.ppt

1、计算机网络技术,第3章 流量控制和差错控制 南开大学通信工程系,计算机网络技术-韩毅刚,1,第3章 流量控制和差错控制,3.1 流量控制 3.2 差错校验编码原理 3.3 差错校验编码 3.4 差错控制 3.5 ARQ差错控制方法,计算机网络技术-韩毅刚,2,计算机网络技术-韩毅刚,3,3.1 流量控制,3.1.1 停-等流量控制方法 3.1.2 滑动窗口流量控制方法 3.1.3 其它流量控制方法,4,流量控制的概念,确保发送实体发送的数据不会超出接收实体接收数据能力 防止缓冲区溢出 传输时间 把所有比特发送到媒介所需要的时间 传播时间 一个比特沿链路传播所需要的时间 帧 链路,3.1.1 停

2、-等流量控制方法,计算机网络技术-韩毅刚,5,源实体传输一个帧 目的实体接收帧后，返回一个确认 源实体在发送下一帧之前必须等待ACK 目的站点可不发送 ACK以终止流量传输 适用于发送少量的但较长的帧,等待效率,链路的等待效率 传输时间占总时间的比例 链路比特长度B,计算机网络技术-韩毅刚,6,7,参数 与帧长、链路长度的关系,设帧长度为L，则 当帧长L固定时， 越大，B就越大 说明速率越高或距离越远 1，说明发送完一个帧后，第一位还未到达对方 即，一个帧占不满一条链路,8,停止等待链路的利用率公式,线路利用率U（等待效率）： 传输时间占总时间的比例 参考：总传输效率,9,停止等待链路的利用率

3、举例1,光纤链路：1 Gbps，200m，帧长8000比特，求其利用率. 传播速率20万公里/秒 链路比特长度B=R*d/V =1Gbps*200m/20万公里/秒 =1000比特 =B/L=1000/8000=0.125 U=1/(1+2 )=1/(1+0.25)=80% 传输一个帧8微秒，传播时延1微秒 总耗时8 + 1（帧）+ 1（ACK）=10微秒 U=8/10=80%,10,停止等待链路的利用率举例2,卫星链路：1 Mbps，36000km，帧长8000比特，求其利用率。 传播速率30万公里/秒 链路比特长度B=240 000比特 =B/L=240000/8000=30 U=1/(1

4、+2 )=1/(1+60)=1.62% 传播时延240ms，传输一个帧8ms 总耗时8 + 2*240(环路延迟）=488ms U=8/488=1.64%,3.1.2 滑动窗口流量控制,滑动窗口法允许发送方在等到确认以前，可以连续发送多个数据帧,计算机网络技术-韩毅刚,11,12,滑动窗口流量控制,允许一次传送多个帧 接收器有长度为W个帧的缓冲区 不等待任何 ACK的情况下，发送器可发送W个帧 窗口尺寸 每个帧通过序号来标识 ACK 中包含下一个希望接收到的帧的序号 序列号范围与字段长度 (k)有关 帧的序号以 2k 为模 最大窗口尺寸2k -1,13,滑动窗口例子,窗口尺寸为7,3.1.3

5、其它流量控制方法,1预约缓冲区法 2带宽限制法 3RTS/CTS硬件流量控制 4XON/XOFF流量控制协议 5定时延迟 6许可证法 7分组丢弃法 葡萄酒策略和牛奶策略,计算机网络技术-韩毅刚,14,计算机网络技术-韩毅刚,15,3.2 差错校验编码原理,3.2.1 差错类型 3.2.2 校验码的分类 3.2.3 编码的纠检错能力,3.2.1 差错类型,单比特错 突发错,计算机网络技术-韩毅刚,16,17,单比特错,孤立，只改变一个比特 不影响邻近的比特 白噪声 随机差错、独立差错,18,突发错,突发错是指几乎是连续发生的一串错 冲激噪声 无线传输中的信号衰落 对高数据速率影响更大,19,突发

6、错的定义,突发长度 B 连续 B 比特中的第一个和最后一个比特错，中间的任意一串比特也有错 长度 = 给定值x IEEE定义：两个相邻错误比特之间的正确比特数小于规定的标准。 给定值x,3.2.2 校验码的分类,1. 检错码和纠错码 2. 分组码和卷积码 3. 线性码和非线性码 4. 系统码和非系统码,计算机网络技术-韩毅刚,20,3.2.3 编码的纠检错能力,海明距离 两个码字之间对应位不同的个数 码距 某种编码的码距是全部码字中两两之间海明距离的最小值。 合法码字 如果一个码字符合编码规则，则称该码字是一个合法码字。 非法码字,计算机网络技术-韩毅刚,21,22,编码的纠检错能力,码距d与

7、编码的检错和纠错能力的关系是： 1. 若d e + 1，只要出错位数不超过e，则可检测出e个错误； 2. 若d 2t + 1，只要出错位数不超过t，则可纠正t个错误； 3. 若d e + t + 1 （e t），只要出错位数不超过e，则可纠正t个错误，同时检测出e个错误。,23,码距与编码纠检错能力的关系,1. 若d e + 1，只要出错位数不超过e，则可检测出e个错误；,24,码距与编码纠检错能力的关系,2. 若d 2t + 1，只要出错位数不超过t，则可纠正t个错误；,25,码距与编码纠检错能力的关系,3. 若d e + t + 1 （e t），只要出错位数不超过e，则可纠正t个错误，同时

8、检测出e个错误。,计算机网络技术-韩毅刚,26,3.3 差错校验编码,3.3.1 奇偶校验码 3.3.2 方阵校验码 3.3.3 校验和 3.3.4 CRC码 3.3.5 海明码,3.3.1奇偶检验码,在字符上附加奇偶检验位 偶检验：整个字符中有偶数个1 奇检验：整个字符中有奇数个1 如果有偶数位出错，检测不到,27,3.3.2方阵检验码,垂直冗余校验VRC：就是字符奇偶校验； 水平冗余校验LRC：就是对数据块中每个字符的对应位进行奇偶校验。,28,3.3.3 检查和,把数据块中的每一个字符代码都按二进制加法求和,29,3.3.4循环冗余校验码CRC,数据除以预先指定的一个数，余数作为校验位,

9、30,CRC,数据 k 位 预先指定的这个数称为生成多项式 n-k+1位 除法 模2除 余数 n-k位，一般称为帧校验序列FCS 校验码 n位，一般称为帧,31,32,CRC码的算法,将k位的数据左移n-k位，低位补0， 再用n-k+1位的生成多项式进行模2除， 所得的n-k位余数就是FCS。,33,CRC码的实现方法,三种等价方式： 模2运算 数据和生成多项式都用0、1串表示 多项式 数据和生成多项式都用多项式形式表示 数字逻辑 使用异或门和移位寄存器实现,34,CRC码的计算举例模2运算,D(x) = 1001001 ， G(x) = x3+x2+1 ，求CRC码。,35,CRC码的计算举

10、例2,D(x) = x6+x4 + x3 + 1， G(x) = x4+x3 + 1，求CRC码。,即信息位是1011001， G(x) 是11001，即r=n-k=4，则 x4D(x) = x10 + x8 + x7 + x4( 对应代码为10110010000） 其由模2除法求余数R(x)的过程如下： 1101010 11001 10110010000 11001 11110 11001 11110 11001 11100 11001 1010,36,CRC码算法的证明,D：k位数据。 T：n位的帧 P： n-k+1位的生成多项式,37,生成多项式的选择,a、生成多项式的最高位和最低位必须

11、为1。 b、当CRC码的任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做模2除，应使余数循环。 检测单错，要含一个以上的非零项 检测双错，要含一个三项因式 检测奇数错，要含因式(x+1),38,生成多项式标准,CRC-12 = x12 + x11 + x3 + x2 + x + 1 CRC-16 = x16 + x15 + x2 + 1 CRC-CCITT = x16 + x12 + x5 + 1 CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7

12、 + x5 + x4 + x2 + x + 1,39,CRC码的检错能力,16位生成多项式产生的CRC码的检错能力： 1 所有的单错、双错和奇数错 2 100%的16位以内的突发错 3 99.997%的17位的突发错(1-2-15) 4 99.998%的18位以上的突发错(1-2-16),40,CRC电路,CRC-CCITT = x16 + x12 + x5 + 1,41,CRC计算程序,/ CRC calculation，x is the byte to be added to CRC. / CCITT polynomial used for CRC calculation：16+x12+x

13、5+1 void updcrc（x） unsigned char x; extern unsigned int crcaccum; / CRC result，2 byte unsigned shifter，flag; for （shifter=0 x80; shifter; shifter=1） flag=（crcaccum / XOR polynomial ,3.3.5海明码,海明不等式,计算机网络技术-韩毅刚,42,海明码编码规则,（1）Pi在海明码的第2i-1位置 （2）被校验的数据位的下标等于所有参与校验该位的校验位的下标之和 一般采用偶校验方法。,计算机网络技术-韩毅刚,43,计算机

14、网络技术-韩毅刚,44,3.4 差错控制,3.4.1 差错控制方法概述 3.4.2 反馈重发纠错方式 3.4.3 前向纠错方式（FEC） 3.4.4 混合纠错（HEC） 3.4.5 其它差错控制方式,3.4.1差错控制方法概述,反馈重发纠错（ARQ） 前向纠错（FEC） 混合纠错（HEC）,计算机网络技术-韩毅刚,45,差错控制方法,计算机网络技术-韩毅刚,46,3.4.2 反馈重发纠错方式,Automatic repeat request（ARQ,自动重发请求） 最常用的差错控制技术 ARQ的技术机制 差错检测 肯定确认 超时后重传 否认并重传,计算机网络技术-韩毅刚,47,48,ARQ的类

15、型,停止等待ARQ （Stop and wait ARQ） 返回 N ARQ （Go-back-N ARQ） 选择拒绝 ARQ (Selective-reject ARQ) (选择重传，SRQ),3.4.3 前向纠错方式（FEC）,发送端发送纠错码 适用于单工方式,计算机网络技术-韩毅刚,49,3.4.4 混合纠错（HEC）,反馈重传纠错和前向纠错方式的综合 如ATM的CRC校验与纠错,计算机网络技术-韩毅刚,50,3.4.5 其它差错控制方式,计算机网络技术-韩毅刚,51,计算机网络技术-韩毅刚,52,3.5 ARQ差错控制方法,3.5.1 停止等待ARQ 3.5.2 返回N ARQ 3.5

16、.3 选择拒绝ARQ,3.5.1 停止等待ARQ,源站点传输一个帧 等待一个确认 ACK,53,54,停等ARQ-图,55,停等ARQ传输效率,56,停止等待 ARQ的优缺点,简单易行 效率低 参考：面向字符的数据链路控制规程 BSC Binary Synchronous Communication 基本型控制规程 ISO 1747-75,3.5.2返回 N ARQ,基于滑动窗口流量控制 连续发送 没有被收到确认的帧的最大数目取决于窗口大小 无差错时，返回肯定确认 检测到差错, 则发送一个否认 目的站点丢弃这个帧及后续收到的帧，直至有差错的帧被正确接收到 源站点必须重传错帧以及后续的所有已经传输过的帧,57,58,返回 N ARQ 的差错控制,返回 2 ARQ 连续工作系统,3.5.3 选择拒绝ARQ,也叫选择重传 只重传那些接收到否认的帧 后面的帧被接收器接收,并且保存在缓冲区里 重传帧的数目降低到最小 接收方必须维护足够大的缓冲区 发送方需要具有能够发送失序帧的更复杂的逻辑,59,60,选择拒绝 ARQ图,帧2错 选择重发帧2,61,窗口大小的选择停等ARQ,最大窗口尺寸设置为 1,62,窗口大小的选择返回N-ARQ,如果序号字段长度为k比特 k=3, 序号0，1，7 收到RR1，发送