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

1、计算机网络技术，第3章流量控制和差错控制，南开大学通信工程系，计算机网络技术-韩，1，第3章流量控制和差错控制，3.1流量控制3.2差错校验编码原理3.3差错校验编码3.4差错控制3.5差错控制方法，计算机网络技术-韩，2，计算机网络技术-韩，3，3.1流量控制，3.1.1停候流量控制方法3.1.2滑动窗口流量控制方法3.1.3其他流量控制方法，4， 流量控制的概念，确保发送实体发送的数据不会超过接收实体接收数据的能力，防止缓冲区溢出，传输时间，将所有位发送到介质所需的时间，沿链路传输一位所需的时间，3.1.1停-等流量控制方法，计算机网络技术-韩，5。 在源实体发送帧之后，目的实体返回确认，

2、即源实体在发送下一帧之前必须等待确认。目的站可能不发送确认来终止流传输。它适用于发送少量长帧、等待效率低、等待效率低的链路。传输时间与总时间的比率。链接位长度b，计算机网络技术-韩，6，7，参数与帧长度和链接长度的关系。如果帧长是L，当帧长L固定时，它越大，就越大，表示速率越高或距离越远。1，表示在发送一个帧之后，第一个比特还没有到达另一方，也就是说，一个帧占用少于一个链路。8、停止等待链路利用率公式。线路利用率u(等待效率):传输时间与总时间的比率参考：总传输效率，9，停止等待链路的利用率示例1，光纤链路：1 Gbps，200米，帧长度：8000位，计算利用率。传播速率为200，000 km

3、/s的链路位长度为b=r * d/v=1gbps * 200m/200，000 km/s=1000位=b/l=1000/8000=0.125 U=1/(12)=1/(10.25)=1微秒传播延迟需要8 1(帧)1(确认)=10微秒，U=8/10=80%，10，停止的利用率传播速率为300，000 km/s的链路比特长度为b=240，000比特=b/l=240，000/8000=30u=1/(1 2)=1/(1 60)=1.62%的传播延迟240毫秒，发送一帧的总时间为8.2毫秒* 240(循环延迟)=滑动窗口方法允许发送方在确认之前连续发送多个数据帧。计算机网络技术-韩易刚，11，12，滑动窗

4、口流控制，允许接收器一次发送多个帧，并有一个长度为W帧的缓冲区，无需等待任何确认。发射机可以发送窗口大小为w的帧，每个帧由序列号标识。要接收的下一帧的序列号范围与字段长度(k)相关。帧的序列号是模2k。最大窗口大小为2k -1，13，滑动窗口示例，窗口大小为7，3.1.3。其他流量控制方法，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错误类型，单比特

5、错误突发错误，计算机网络技术-韩，16，11 隔离，仅改变一个比特不影响相邻比特的白噪声随机误差，独立误差，18，突发误差，突发误差是指一系列几乎连续发生的误差脉冲噪声，而信号衰落在无线传输中对高数据速率有较大影响。 19.突发错误的定义，突发长度b中的第一位和最后一位连续的b位是错误的，并且中间的任何位串也具有错误长度=给定值x IEEE定义：两个相邻错误位之间的正确位数小于指定的标准。给定值x，3.2.2，校验码的分类，1。检错码和纠错码。分组码和卷积码。线性码和非线性码，4。系统码和非系统码，计算机网络技术-韩，20，3.2.3，编码的纠错和检测能力，汉明距离，两个码字之间具有不同对应比

6、特的码距数，以及码距的法律代码字如果代码字符合编码规则，则称其为法律代码字。非法码字，计算机网络技术韩，21，22，编码的检错能力，码距D与编码的检错纠错能力的关系如下：1 .如果D1，只要错误位数不超过e 1，就可以检测出E1错误；2.如果d 2t 1，只要错误数量不超过t，就可以纠正t个错误；3.如果d e t 1 (e t)，只要错误的数量不超过E，就可以纠正T错误，同时检测E错误。23、码距与编码纠错和检测能力的关系。1.如果D1，只要错误位数不超过e，就可以检测出e个错误；24，编码距离与编码纠错和检测能力的关系，2。如果d 2t 1，只要错误位数不超过T，就可以纠正T错误；25、码

7、距与编码纠错和检测能力的关系。3.如果d e t 1 (e t ),只要错误数字不超过e，就可以纠正t错误，同时检测e错误。计算机网络技术-韩，26，3.3差错校验编码，3.3.1奇偶校验码，3.3.2平方矩阵校验码，3.3.4循环冗余校验码，3.3.5海明码，3.3.1奇偶校验码，增加奇偶校验奇偶校验到字符：在整个字符中有偶数个奇数：水平冗余校验：奇偶校验在数据块中每个字符的相应位上执行。28，3.3.3校验和，根据二进制加法将数据块中的每个字符码相加，29，3.3.4循环冗余校验码循环冗余校验，将数据除以一个预先指定的数，并将余数作为奇偶校验位，30，循环冗余校验，预先指定个数的数据k位称

8、为生成多项式n-k 1位除法模2除数n-k位，一般称为帧校验序列FCS俗称帧，31，32，循环冗余校验编码算法， K位数据左移n-k位，低位用0填充，然后n-k 1位生成多项式用于模2除法，得到的n-k位余数为FCS。33，CRC码的实现方法，三种等价方式：模2运算数据和生成多项式都用0和1的字符串表示。多项式数据和生成多项式以多项式形式表示。数字逻辑由异或门和移位寄存器实现。34，通过模2运算计算循环冗余码，D(x)=1001001，G(x)=x3 x2 1。35，循环冗余码计算示例2，D(x)=x6 x4 x3 1，G(x)=x4 x3 1，查找循环冗余码。即，信息比特是1011001，而

9、G(x)是11001，即，r=n-k=4，那么X4d(x)=X10874(对应的代码是1011001000)，并且通过模2除法来寻找余数R(x)的过程如下：1101010 11001 101111 T: N比特帧P: N-K 1比特生成器多项式，37当循环冗余码的任何一位有错误时，余数在被生成多项式模2除后不应为0。当错误发生在不同的位时，余数应该不同。继续用模2除余数，并使余数循环。为了检测单个错误，我们应该包括多个非零项来检测双错误，一个三重因子来检测奇数错误，因子(x 1)，38，生成多项式标准，CRC-12=x12 X11 x3 x2 x1 CRC-16=x16 x15 x2 1 CR

10、C-CCITT=x16 x12 x51 CRC-32=x32 x26 x23 x22 x16 x12 X11 X10 x8x x7x x4x x2 x1，39，CRC码的错误检测能力，CRC码生成的错误检测能力16 双错误和奇数错误，16位内2 100%突发错误，17位(1-2-15)的3 99.997%突发错误，18位以上(1-2-16)的4 99.998%突发错误，40，循环冗余校验电路，循环冗余校验-。 41、循环冗余校验计算程序，/循环冗余校验计算，x是要加到循环冗余校验中的字节。/用于循环冗余校验计算的CCITT多项式：16x12x51无效更新循环冗余校验(x)无符号字符x；exte

11、rn无符号int crcaccum/循环冗余校验结果，2字节无符号移位器，标志；对于(移位器=0 x80移位器；移位器=1)标志=(循环冗余校验累加/异或多项式，3.3.5汉明码，汉明不等式，计算机网络技术-韩，42，汉明码规则，(1)汉明码2i-1位置的校验数据位的下标(2)等于参与校验该位的所有奇偶校验位的下标之和，一般采用偶校验方法，计算机网络技术-韩，43，计算机网络技术-韩，44，3.4差错控制，3.4.1差错控制方法概述3.4.2反馈重传纠错方法3.4.3前向纠错方法(FEC) 3.4.4混合纠错(HEC) 3.4.5其它差错控制方法反馈重传纠错()，前向纠错(FEC)，混合纠错(

12、HEC)，计算机网络技术-韩，45，差错控制方法，计算机网络技术-韩，46，3 最常用的错误控制技术，技术机制，错误检测，肯定应答，拒绝重传和超时后重传，计算机网络技术-韩，47，48，类型，停止并等待(停止并等待)返回到N(返回-N ARQ(选择性拒绝ARQ (SRQ)，3.4.3前向纠错(FEC)，发送方发送的纠错码适用于单工模式，计算机网络技术-韩一刚，49，3.4.4混合纠错(HEC)， 集成反馈重传纠错和前向纠错方法，如自动柜员机的循环冗余校验和纠错，计算机网络技术-韩，50，3.4.5其他错误控制方法，计算机网络技术-韩，51，计算机网络技术-韩，52，3.5错误控制方法，3.5.

13、1停止等待3.5.2返回到3.5.3选择拒绝，3.5.1停止等待，源站发送一帧并等待确认确认，53，54 停止等待ARQ传输效率，56，停止等待ARQ的优点和缺点，简单和低效率参考：面向字符的数据链路控制程序BSC二进制同步通信基本控制程序ISO 1747-75，3.5.2返回ARQ N，基于滑动窗口流控制的无确认连续发送的最大帧数取决于没有错误时的窗口大小。 如果通过返回肯定的确认检测到错误，发送拒绝的目的站丢弃该帧和随后接收的帧，直到正确接收到带有错误的帧，并且源站必须重传错误的帧和所有随后发送的帧，57，58，返回到ARQ的错误控制，返回到2 ARQ的连续工作系统，3.5.3选择拒绝ARQ，也称为选择性重传， 只有接收到拒绝的帧后面的帧被接收器接收，并且存储在缓冲器中的重传帧的数量被减少到最小。 接收器必须保持足够大的缓冲区。发送方需要有更复杂的逻辑来发送乱序帧。59，60，选择拒绝ARQ图，选择帧2中的重传帧2，61，选择停止窗口大小的ARQ，并将最大窗口大小设置为1，62。窗口大小的选择返回到北ARQ。如果序列号字段的长度是k比特k=3，并且序列号0、1和7接收RR1，发送1、2、7和0，然后接收RR1，我不知道它是当前帧0还是在前一帧