《计算机通信网 》第3章 数据链路层

1、2012 SPLENG,第3章 数据链路层,3.1 数据链路层概述 3.2 成帧与帧定界 3.3 差错检测与校正方法 3.4 差错与流量控制协议 3.5 协议描述与验证 3.6 数据链路层协议案例,2012 SPLENG,3.1 数据链路层概述,链路层模型,本地连接,传输系统,G.703,G.703,远程连接,物理层,网络层,链路层,链路层,网络层,链路层,链路层,网络层,传输系统提供透明的bit 传输,2012 SPLENG,3.1 数据链路层概述,DL面临的环境,网络层,数据链路层,物理层,SAP,SAP,SAP,SAP,网络层,数据链路层,物理层,分组,帧,装入,分组,取出,101011

2、01,10101101,帧,发送方,接收方,信道有噪声，bits可能出错,可能装入太快 取出跟不上,2012 SPLENG,3.1 数据链路层概述,链路层模型,链路层,网络层,物理层,010101,比特传输,传输信号,Packet,物理层 实现了把比特传输转换成信号传输、进入信道。 网络层 需要把一个个分组送到对方网络层 链路层 组织一个个分组，用比特传输实现逐个分组的传输和接收,2012 SPLENG,3.1 数据链路层概述,链路层的基本任务,物理层,Asynchronous,Block,Synchronous,DU,Framing(帧同步) 发送：转换成特定的bit传输形式，将Frame送

3、出 接收：界定每个frame的位置，取出frame,DU,Error Control(差错控制) 发送：组织DU (frame)，方便对方检查错误 接收：检测DU是否出错，DU出错的处理,Link Control(链路控制) 双方通过配合，实现： 链路的使用规则，流量控制、汇聚分发等,DU,Service(服务) 为上面的实体提供分组传输服务,2012 SPLENG,3.1 数据链路层概述,链路层任务模型,framing,Error Control,Data Link Control,framing,Error Control,Data Link Control,Physical Layer,

4、Data Link Layer,Network Layer,DU,DU,Frame,约定成帧方式,约定出错处理手段,约定控制方法,可用的通信功能,DU,2012 SPLENG,3.1 数据链路层概述,链路层效率定义 链路层 有效数据率 r = ni/T （ni：第i帧bit数，T：测量总时间） 物理层 信道的速率 R b/s 链路层效率： = r/R （ 1）,链路层,链路层,2012 SPLENG,Link Layer Services,三种服务的示意图,有确认面向连接,无确认无连接,Frame,ack,有确认无连接,Frame,ack,连接确认,连接请求,Frame,Frame,ack,拆

5、除确认,拆除请求,B方,A方,2012 SPLENG,Link Layer Services,三种可能的服务 无确认的无连接服务 无需对方许可，直接向对方发送Frame，对方不需要反馈确认信息 优点：不受等待确认的拖累；缺点：frame传输可靠性不高 信道效率：不等待确认，可提高信道效率，但传输出错降低信道效率 协议考虑：PDU中含源/目的地址 有确认的无连接服务 无需对方许可，直接向对方发送Frame，需要对方反馈确认信息 优点：通过重传增加了可靠性；缺点：受等待应答的拖累 保持发送和确认间的正确对应关系所采取的措施会大大降低信道使用效率 协议考虑：PDU编号，PDU中含源/目的地址、单帧确

6、认，差错检测与重传 有确认的面向连接服务 需事先与对方沟通，双方建立起一套复杂的发送、确认机制来实现恢复差错、排除重复、维持顺序的可靠通信 适合于有大量Frame传输的场合 协议考虑：PDU编号、确认、差错控制（丢弃错帧和重复帧，请求重发错帧）,2012 SPLENG,3.2 成帧Framing,成帧(或帧同步)：就是确定帧的界限（起与止） 通俗理解： 发送方：在帧的前后各加入事先商定好的标记 接收方：在bits中寻找标记来识别帧的起与止 需要特别考虑： 若数据与帧的起止标记相同时，发送方必须采取措施 否则可能会引起接收方的误断 成帧方法： 字符计数法 字符填充首尾界定法 位填充首尾界定法 物

7、理层编码违例法,11010110100101101100111101 11100101010111000101010010 11010101011011010100100100 .,2012 SPLENG,成帧,不同传输方式下的帧同步 同步传输方式(Sync,连续bit流) 连续的bit流传递离散的Frame 每个Frame都成为连续bit流中的一段，接收方识别并取出Frame 异步传输方式(Async,异步字节序列) 每个Frame转换为异步字节序列传送，接收方收集字节序列，还原Frame 数据块传输方式(Block) 每个Frame形成一个数据块传送。,2012 SPLENG,Sync信道

8、的帧同步技术,连续的bit流由若干Frame和它们间的空闲bit组成 注意：frame中或空闲的bit都只有两种取值：0或1 关键问题：如何正确识别和提取bit流中的Frame部分？ 思路：假设空闲bit用某种特殊的bit模式(pattern)构成，而Frame中不会出现该pattern，则接收方就能够正确设别和提取Frame 但: 应该允许Frame包含任意数据，就肯定包含了这种Pattern。 若能对Frame中出现的Pattern用某种变换方式消除，接收方提取出Frame后，再通过反变换，恢复原来的Frame，该假设成立,Frame,Frame,Frame,Frame,反变换,变换,Fr

9、ame,连续bit流,空闲,空闲,空闲,特殊pattern,2012 SPLENG,Sync信道的帧同步技术,发送,开始,扫描Frame,发现 Pattern,Pattern变换,扫描结束,发送Frame,否,是,结束,否,是,接收,开始,否,检测pattern,发现,存储数据,否,检测pattern,发现,复原Frame,是,继续,是,结束,是,Frame开始,Frame结束,否,Pattern选择 -易于变换 -易于检测 -易于反变换,2012 SPLENG,Sync信道的帧同步技术,位填充首尾定界法 （0比特插入/删除技术) Pattern=01111110称为定界标志F (Flag)

10、Frame内F的变换和反变换(利用F中连续6个1的性质) 变换： Frame中如果出现连续5个1时，插入一个0 提取 从第一次出现非F开始，到重新出现F时的所有bit 反变换 Frame中出现连续5个1时，删除后面的1个0 采用01111110的特点： 变换与发送合一：发送连续5个1，加发一个0 接收与复原合一：连续接收5个1，下一bit若是0则直接去掉，否则，应该出现的就是01111110结束该帧,2012 SPLENG,位填充首尾定界法,发送：在帧体部分出现连续5个1，无条件地插入一个0 接收：在帧体中扫描连续5个1，无条件去掉后面的0,01111110,0010101111011111,

11、01111110,101011111,11110010,0,0,成帧,0010101111011111,101011111,11110010,0,0,2012 SPLENG,位填充首尾定界法,位填充 (实现示意图),01111110011111101001111010110101010111111010101110101110111111001111110,帧提取,01101010,移位寄存器,F检测结果,帧体,帧体,“0”bit 删除,0bit插入,控制,接收,发送控制,数据,2012 SPLENG,位填充首尾定界法,软件模拟 int Send(char *pF, int Len) int

12、i,j,c,msk, sn; sn = 0; for(i=0;iLen;i+) / 循环帧的字节长度 msk = 1; for(j=0;j8;j+) / 8bit c = pFi / 回送发送总bit数 ,假定函数Xmitb(c)：向信道发送c (1bit),2012 SPLENG,Async信道的帧同步技术,描述 以字节(8bit)为单位的传输方式 逐字节传输实现Frame传输 帧同步讨论 Frame间留有足够的时间间隔，以区分各个Frame 对Frame传输能力有较大的影响 Frame间的时间间隔不够大，帧与帧区分易出错 两种典型帧同步技术 字节计数法 字符填充首尾定界法,PSTN,201

13、2 SPLENG,成帧字符计数法,也可称为字节计数法 假设一个字符由8位二进制数表示 基本思想 在帧头的第1个字节指明帧内的字节数 问题 字节计数值可能在传输中出错（被篡改） 简单、不可靠,11101010 00101110 01010101 010111010 10101011,发送,错,00000010,00000110,00000011,00000110,2012 SPLENG,字符填充首尾定界法,思想 与同步方式的位填充类似，不同的是以字节为单位 方法：“定界字符” 在帧体的前后都用某个特定的字节加以“定界” 帧体中也可能出现该定界字符，通过变换消除 接收时提取Frame后，通过反变换

14、复原 局限性：数据的长度总是以字符或其倍数为单位 定界字符: F(Flag) = 01111110,第1帧,第2帧,2012 SPLENG,字符填充首尾定界法,将F变换为某个其它字节(x)存在问题： 帧体中其它字节也可能出现x，反变换xF时就出错 Frame体中定界字符的变换方法 一字节到两字节的变换,变换后帧体中不出现F 帧体中的F和x都需要变换：Fxy; xxz y和z是另外选取的两个字符，对y、z不再需要变换 分析 若帧体中出现xy 变换：xy(xz)y ；反变换：xzyxy,正确复原 可以验证：对帧体中出现F,x,y,z的任意顺序的组合，只对其中的所有F和x进行变换，反变换时都能正确复

15、原,2012 SPLENG,字符填充首尾定界法,处理帧体内的特殊字符 (RFC1662，异步PPP) F=01111110 (7e),定界字符 x=01111101 (7d),称为转义字符 y=01011110 (5e) z=01011101 (5d),帧体,帧体填充后,发送,XmitB(F),B=F？,结束,否,是,B=Framei+,XmitB(B),B=x？,XmitB(x) XmitB(y),XmitB(x) XmitB(z),否,是,iLen,是,XmitB(F),否,XmitB：发送字节 XrcvB：接收字节,2012 SPLENG,练习,分两组：一组成帧，一组提取帧 分别用位填充

16、法、计数法、字符填充法进行练习 F=01111110，x、y、z可自行定义 可自定义若干帧来完成该练习 思考 字符填充法中，仅用F和x是否能够实现，如能实现，给出实现方法，如不能实现，请说明不能实现的理由,帧1：1001 1111 1110 0000 0101 1101 0100 0010 0110 0011 帧2：1101 1011 0000 0000 0110 0111 帧3：1100 0101 1111 1111 1101 0010 1101 1111,2012 SPLENG,字符填充首尾定界法,教材PP.159,2012 SPLENG,块传输信道的帧同步技术,当用电缆或无线直接通信(不

17、经过传输系统)时，最简洁的通信方式是块传输方式，每个块就是一个Frame 块传输方式 每个Frame都带有前导bit序列(preamble)和后续bit序列(postamble),以确保Frame的头和尾能正确检测和接收 因此需要确定： Preamble结束和Frame开始的比特位置 Frame结束和postamble开始的bit位置 同步技术 违例编码法：利用信息bit的码型特性，用非正常码型来进行界定位置,preamble,postamble,2012 SPLENG,块传输信道的帧同步技术,例1：曼切斯特编码(1b/2b, 10M以太网) Block = 010101JKFramebody

18、KJ010101 例2：4b/5b编码(100M以太网) 4bit数据映射成5bit码组 000011110, 000101001, , 111111101 空闲11111, 定界符111000, 定界符210001 Block = 010101定界符1FrameBody定界符2 010101 例3：8b/10b编码(1000M以太网) 8bit数据映射成10bit码组 从1024个码组中只需选取256个来代表8bit的各个值 剩余1024-256个码组可作为控制、定界等多种功能,0 =,1 =,违例,2012 SPLENG,块传输信道的帧同步技术校验和法,利用ATM信元固定、且长度较短(53

19、字节)的特性 信元前4字节是头部，第5字节是校验和，使用循环冗余校验 设40位寄存器，计算校验和 正确则可能发现了一个信元 不正确则移一位，再次计算，直到得到一个信元,成帧,1001101000101011111101000110110001111011100,信元头,信元体,信元头,信元体,2012 SPLENG,3.2 成帧讨论与理解,帧定界正确，请问帧一定无错吗？ 一个帧定界出错，请问 用字符计数法，后续的帧也不能正确识别吗？为什么？ 用字符填充法和位填充法，情况又如何？ 位填充法比字符填充法有哪些优越性？,2012 SPLENG,Framing小结,不同的成帧技术以适应信道的不同传输体

20、制 需求： 接收方易于提取、出错时对后续帧的提取影响小 较高的信道利用率、较简单的实现 位填充、字符计数、字符填充、违例编码、校验和 与其它功能的关系 实现的是信道上传输和接收帧的功能，不涉及帧的内容 链路层其它功能直接对帧的处理，不受传输体制影响,framing,framing,差错处理、链路功能,差错处理、链路功能,2012 SPLENG,3.3 差错检测与纠正,信道传输过程中 (误码：10; 01) 随机干扰：随机错 (均匀性) 突发干扰：突发错 (一定的突发长度) 出错处理 检错：验证是否出现了误码 纠错：找到误码的位置，纠正之,0111111001111110100111101011

21、0101010111111010101110101110111111001111110,01111110011011101001111110110101010110111010101110101111111111001111110,Bit错可能造成： 帧体错帧错误 定界错帧错误、帧丢失、多余帧 信道异常(多于6个1)信道失序,原码,出错后,2012 SPLENG,3.3 差错检测与纠正,如何理解数据传输中的差错？ 一位错就等于全帧错 关于误码率Pb与误帧率Pe 假设 帧长度为N比特，误码率为Pb（设每比特出错独立） 则 比特正确率为：1- Pb N比特正确率为 （1- Pb）N 帧出错率（误帧

22、率） （一帧中至少一位错）为 Pe= 1-（1- Pb）N NPb （帧出错的概率与帧成近似成正比）,2012 SPLENG,3.3 差错检测与纠正,差错控制，意味着： 首先检测出差错 然后是纠正差错 检测差错 采用冗余编码技术进行差错检验编码 纠错码：不仅能检测差错，且能知道错在哪儿 检错码：只能检测差错，但不知错在哪 纠正差错 前向纠错FEC（Forward Error Correction） 用纠错码，收方检错并自动纠错 自动请求重发ARQ （ Automatic Request for Repeat） 用检错码，收方检错通知发方重发恢复差错 计算机网络中常采用,2012 SPLENG,

23、3.3 差错检测与纠正,假设 待传数据为m位 为检测差错，所需要的冗余位（校验位）为r位 则 传输码长度n=m+r 通常采用纠错码或检错码，即： 按某种算法计算出校验位 然后将m位数据和r位校验码形成传输码 接收方根据相同的算法重新计算校验位，判断是否出错,2012 SPLENG,3.3 差错检测与纠正,一种直观简单的纠错方法 每个bit重传三次：1111; 0000 如果3bit中有1bit错, 我们可以纠正过来 101、110、011 111 1 001、010、100 000 0 如果3bit中有2bit或3bit全错，则无法纠正了 101 111 ? 000 ? 无法知道是1bit还是

24、2bit错 将每个bit重传2n+1次，n越大，纠错能力越强(传输效率越低) 不管n如何取，我们仍不知道是否真的纠正了错误，只能认为增大了纠正错误的概率,2012 SPLENG,3.3.1 纠错码海明码,海明距离 （Hamming Distance）教材P162163 两个等长码对应位不同的个数，称作这两个码的海明距离 例：0001111和0001100的海明距离为2 某种编码的任意两个有效编码之间的距离称为该编码的海明距离 结论1：检出d个错误的检错码，海明距离至少为d1 结论2：纠正d个错误的纠错码，海明距离至少为2d1 海明码是一种能纠正一位错的纠错码,2012 SPLENG,3.3.1

25、 纠错码海明码,假设 数据为m位 则纠正一位错的校验码 r 满足 m+r+12r （证明：P163） 例如：m=3，3+r+12r r=3 则海明码码长= m+r=6位 海明码的编码为r与m的混排方式，规则为： 检验位r的序号为2的整次幂1，2，4，8， 信息位m的序号为2的非整次幂，3，5，6，7. r1r2m3r4m5m6,2012 SPLENG,3.3.1 纠错码海明码,假设数据为011，该如何确定海明编码？ 编码应为：r1r2m3r4m5m6 现已知：m3 m5 m6 = 0 1 1 关键是确定r1、r2和r4 r的计算方法 首先找出哪些与 r1、r2和r4相关的数据位 将数据位数拆成

26、2的整次幂相加 如3=1+2 m3与r1和r2相关 然后将与某r相关的数据位模2加(异或），结果为该r值 与r1相关的数据位：m3、m5 则r1=01=1 与r2相关的数据位：m3、m6 则r2=01=1 与 r4相关的数据位：m5、m6 则r4=11=0 得出：011的海明编码为110011,2012 SPLENG,3.3.1 纠错码海明码,已知：011的海明编码为110011（ r1r2m3r4m5m6） 假设：编码在传输中出了一位错 110011 错成 110010 接收方的纠错规则 首先：对于每个ri，将ri和与之相关的数据位进行依次异或 结果为1，则记录Ai=i（i为r的序号） 结果

27、为0，则记录Ai=0 然后累加，计算Ai的值，结果等于几就是该对应位出错 最后，将出错位取反进行纠错 计算过程 r1m3 m5=101=0 则 A1=0 r2m3 m6=100=1 则 A2=2 r4m5 m6=010=1 则 A4=4 出错位： Ai=A1+A2+A4=6 纠错： 110010 110011 （差错位取反）,2012 SPLENG,3.3.2 差错检测,采用冗余编码技术进行差错检验编码 基本思想 发送方：将待发数据按照某种规则加上一定的冗余位后，进行传输， 接收方：对收到的数据进行判断，是否符合原规则，若符合则无错，不符合则出错。,C(x) = R(x) 无错 C (x)R(

28、x) 出错,2012 SPLENG,3.3.2 差错检测检错码,奇偶校验码 循环冗余码CRC 校验和编码,2012 SPLENG,3.3.2 差错检测奇偶校验码,增加冗余位使信息码中的“1”的个数为奇数或偶数的编码 奇校验：“1”的个数为奇数 偶校验：“1”的个数为偶数 具体实现：信息位逐位进行模2加（异或运算） a1a2a3a4a5 结果为0，偶校验时 校验位为0，奇校验时，校验位为1 结果为1， 偶校验时 校验位为1，奇校验时，校验位为0 例 信息字段 奇校验码 偶校验码 011001 011001 0 011001 1 出错为： 001001 0 001001 1 重新计算校验和： 1,

29、0,2012 SPLENG,纠正突发错,数据组织成矩阵，按行编写奇偶效验码 发送时按列发送 出现突发错误时，可按行纠正,10010111101010 00101101001001 10100100001010 01001001000010 11101011010101 10101001000010 00010101111100,0 0 1 0 1 1 1,2012 SPLENG,3.3.2 差错检测循环冗余码,循环冗余码（CRC: Cyclic Redundancy Code）教材p165167 对任意m位二进制流，补充r个0 用规定的r+1位除数进行求余计算，得到r位效验码 数据与r位效验码

30、组成传输码组 发送出去,1011010,11000101,0000000,1011010,1,1,0,1,1,0,0,m位数据,r位CRC,1010110,模2加,2012 SPLENG,3.3.2 差错检测循环冗余码,CRC校验 对收到的完整的数据帧用发送方相同的r+1位除数进行求余计算 余数为0则无错,10110101010110 11000101 11100000 11000101 01001011 00000000 10010110 11000101 10100111 11000101 11000101 11000101 00000000 00000000 0000000,110001

31、01,10110101010110,2012 SPLENG,3.3.2 差错检测循环冗余码,基于任何一个二进制位串组成的代码，都可以与系数只为0和1的多项式建立一一对应的关系。 一个K位的数据可以看成是从xK-1x0次系数为0和1的多项式 x4 x3 x2 x1 x0 数据： 1 1 0 1 1 多项式 x4 + x3 + x + 1,2012 SPLENG,3.3.2 差错检测循环冗余码,1）基本思想： 设：数据m位，对应多项式M（x），校验码为r位，对应多项式R(x) 给定：生成多项式G（x），阶数为r，r+1位，高位和低位系数为1 发送方：将M（x）通过G（x）计算出带校验和的传输多项式

32、T（x） 接收方：将收到的带校验和的多项式T （x）除以G（x），如有余数，出错，能除尽，无错 2）校验码与传输多项式的计算 STEP 1 在m位数据之后加上 r个0，数据位变成m+r位，对应多项式x r M（x） STEP 2 计算校验码多项式：x r M（x）/ G（x）(对应二进制位串模2除)，余数为校验码，对应多项式为R（x） STEP 3 计算传输多项式：T（x）= x r M（x）+ R（x），对应系数位串为传输数据,2012 SPLENG,3.3.2 差错检测循环冗余码,示例：数据： 110110 G（x）= x4 + x+ 1 对应位串 10011 （除数） 在数据后加4个0

33、形成 1101100000 被除数， 求余数,2012 SPLENG,3.3.2 差错检测冗余循环码,值得注意： 多项式变为码字时，首位对应最高次，中间的“0”不能丢掉 在计算中涉及的“+”和“-”均为模2运算（加、减结果一样，异或运算，相同为0，相异为1） 模2除商1的原则：只要被除数的首位为1，且位数与除数相同则商1，如上例中红色双向箭头处（被除数为10000，除数为10011）,2012 SPLENG,3.3.2 差错检测冗余循环码,CRC码的检错性能（r个校验位比特） 所有单个错 所有2bit错 所有长度小于或等于r个bit 的突发错 长度为r+1个比特的突发错，漏检率为：1/2 r-

34、1 长度大于r+1比特的突发错，漏检率为：1/2 r 校验和的计算一般都用硬件实现，有参考电路，也可用软件实现。硬件计算时是边发边计算，故通常校验和在帧尾。 常用的CRC多项式： CRC-8 = x8+x2+x + 1 CRC-12 = x12+x11+x3+x2+x + 1 CRC-16 = x16+x15+x2 + 1 CRC-CCITT = X16 + x12 + x5 + 1 CRC-32,2012 SPLENG,3.3.2 差错检测校验和,校验和 Checksum C语言：for(i=0;iN;i+) Sum +=Wi； 基本思想： 按一定大小进行累加 累加结果产生进位，将进位累加到

35、结果中 最终累加结果取反，获得校验和,ca 73 0c 1e,数据（16进制）,ca 72 22 01,计算16位校验和,ca 73 0c 1e ,d6 91,d6 91 ca 72 ,1 a1 03,1 a1 03 22 01 ,1 c3 04,checksum c3 04 1 3c fa,校验后的数据：,ca 73 0c 1e ca 72 22 01 3c fa,校验 1 c3 04 3c fa 1 fffe 0,2012 SPLENG,Error Control 小结,检错算法 CRC，二进制异或除法，除数选择重要 CheckSum，模65536加法，软件实现 帧末尾附加了r-bit检错

36、码 (也称校验码) 检错能力 r越大，检错能力越强 存在坏帧漏检的概率 应用 发现并丢弃传输中出现的坏帧，保证继续处理的帧基本上是正确的,Frame,校验码,2012 SPLENG,作业4,1、请写出通常采用的成帧方法及各种成帧法的特点。假设帧标记符出错，请问哪种成帧方法将不能检测到后续所有的帧？为什么？ 2、如果待传数据为 1111111000111111，假设采用“位填充法”成帧，请写出帧内容。 3、假设待传数据为 100101，（1）计算校验位r的位数；（2）计算出传输该数据的海明码（要求步骤） 4、假设待传数据为100101，采用CRC编码，假设生成多项式为G（X）=X4+1，计算出校

37、验多项式R（X）。,2012 SPLENG,3.4 差错与流量控制协议,在计算机网络中，差错控制方式通常采用 自动请求重发（ARQ ） ARQ基本思想： 采用检错码进行检错 丢弃出错的帧 请求重传出错的帧 对帧进行确认 典型的ARQ协议 停等协议 回退N协议 选择性重传协议,ARQ是一种保证PDU可靠传输的技术 可用于各层协议中，不仅仅限于数据链路层 例如： X.25网络的网络层、数据链路层 TCP/IP网络中的传送层,2012 SPLENG,3.4 差错与流量控制协议,3.4.1 停等协议 3.4.2 连续发送的滑动窗口协议的概念 3.4.3 回退N协议 3.4.4 选择性重传协议 3.4.

38、4 双向传输时的确认 3.4.4 流量控制,2012 SPLENG,3.4.1停等协议,停等协议：stop and wait protocol 基本思想： 每发送一个帧（PDU），停下来等确认（应答） 收到肯定应答，发送下一个新帧（PDU） 收到否定应答，重发上次的帧,数据链路层的 PDU也称为帧 后续讨论中帧 和PDU等同,2012 SPLENG,3.4.1停等协议,协议需要考虑以下情况 帧丢失，将导致： 接收方收不到PDU 发送方收不到应答（ACK或NAK） 应答丢失，将导致： 发送方收不到应答（ACK或NAK） 解决办法：设置定时器T，超时重发,2012 SPLENG,3.4.1停等协议

39、,还有问题要解决： 连续丢失问题 重发后仍收不到应答或接收方仍收不到PDU，一直重发下去？ 解决办法：设置重发次数Nmax 重复收帧问题 ACK丢失，重发PDU，接收方收到重复帧而不知道 措施：为PDU编号（0 1即可区别）,2012 SPLENG,3.4.1停等协议,还有问题要解决： 过早超时问题 重发定时器T在应答到达发送方之前就超时 导致接收方正确收到PDU，而发送方仍然重发 如果过早超时，且ACK无编号，则 出现发送PDU出错 措施：对应答编号 请同学自己分析以下情况： 过早超时，但PDU和ACK都编号时， 停等协议将如何工作？,2012 SPLENG,数据帧编号,DU,DU,N,校验

40、,T,DU,DU,N,校验,T,If(N=Vr) Vr+;,N=Vs Vs+;,对DU顺序编号,DU顺序提交上层,发送变量Vs实现对DU的顺序编号,接收变量Vr控制DU的顺序提交,DU,N,校验,T,N=帧序号,0,1,2,T=帧类型，DATA，ACK，,TQ,(待发送队列),记为Fm(N),Fm(N),2012 SPLENG,数据封装实现(扩),用skbBuff实现,MAC实体,IP实体,DataLen,DataPos,pPDU,OnSend(pPDU) skbPush(pPDU,sizeof(FmHdr); pHdr = skbGetDataPtr(pPDU); pHdrType= Sen

41、d(pPDU) to lower,Struct skbBuff *pPDU; Struct FmHdr pHdr;,Deliver(pHdrType, pPDU); skbPop(pPDU,sizeof(FmHdr); Do some recv things(pHdr) pHdr = skbGetDataPtr(pPDU); OnRecv(pPDU) From lower,MAC实体,DataLen,DataPos,skbPush(pPDU,len),len,skbGetDataPtr(pPDU),SAP,SAP,2012 SPLENG,数据帧编号(扩),typedef struct FmHd

42、r U8 Type; / Frame Type U8 seqN; / Frame number FmHdr；,#define FM_DATA 1 #define FM_ACK 2 int Vs = 0; int Vr = 0；,OnSendReq(SKB *pSkb) FmHdr *pF; skbPush(pSkb, sizeof(FmHdr); pF = (FmHdr*)skbGetDataPtr(pSkb); pF-Type = FM_DATA; pF-seqN = Vs+; EnQue(TQ, pSkb); ,OnFmInd(SKB *pSkb) FmHdr *pF; pF = (FmH

43、dr*)skbGetDataPtr(pSkb); skbPop(pSkb, sizeof(FmHdr); if(pF-seqN = Vr) NetRx(pSkb); Vr+; else skbFree(pSkb); ,2012 SPLENG,超时重传,TQ,取出一帧发送,送入重传队列,Timer,StartTimer,等待应答,RTQ,StopTimer,应答到,取出一帧发送,TimeOut,StartTimer,重传队列,2012 SPLENG,WaitACK() int Retry=0； while(1) event = WaitEvent(); / 无事件时，阻塞软件执行 switch(

44、event) case T0: pSkb=GetEntry(RTQ);/ 从队列中获得但不取出 SendFrame(pSkb); StartTimer(T0); Retry+; if (ReTry = MaxTry) return -1; break; case ACK: pSkb = DeQue(RTQ); skbFree(pSkb); StopTimer(T0); return 0; break; ,超时重传（扩）,int SendTask() int continue = 1; while (continue) pSkb=DeQue(TQ); SendFrame(pSkb); EnQue

45、(RTQ,pSkb); StartTimer(T0); if( WaitACK() 0) continue = 0; return -1; ,2012 SPLENG,3.4.1停等协议,效率讨论 设PDU长度为L(bit)，信道速率为B(bit/s)，PDU发送时延为t(s)，传播延时为(s) 则：t=L/B 无差错传送一个PDU的平均时延为：T=t+2（忽略应答发送时延，忽略接收处理时延） 实际通信能力 CC=L/T=L/（L/B+2）（位/秒） 信道的利用率 CR=CC/B=1/（1+2B/L）,2,t,如果考虑出错重传，则效率更低,2012 SPLENG,Stop-Wait：效率,主要结

46、论 当= 2/t 越大，信道效率越低 CR=CC/B=1/（1+ ) 信道越长， 越大 信道速率越高， 越大 协议存在传输速率上限 传输速率： CC=L/T=L/（L/B+2） 当B时，CCL/(2 ),2012 SPLENG,3.4.1停等协议,一卫星信道，信道传输速率50Kbps，传播时延为500ms，数据PDU长度为1000bit。采用停等协议，计算协议的最大通信能力CC（实际的最大通信速率）及信道利用率CR。（忽略应答发送时延和处理时延） 最大通信能力应为每次都正确收发时的能力(无重发） CC=L/T=L/（L/B+2） =1000/（1000/50000+2*0.5）=980（bit

47、/s） CR=CC/B=980/50000=1.96% 假设将信道传输速率提高到5000kbps（100倍） CC=998 通信能力仅提高18b/s CR=0.0001996=0.01996% 信道利用率降低近100倍 结论：停等协议不适合长距离（高传播时延）信道,2012 SPLENG,3.4.1停等协议,实际应用案例 如：在无线局域网的链路层使用 无连接方式 单帧确认 接收到正确帧，发送ACK 接收到错误帧，简单丢弃，不发送应答 发送方超时重发PDU,2012 SPLENG,3.4.1停等协议 小结,发送方 每次发送一个PDU，等待应答 收到ACK，继续发下一个PDU 收到NAK，重发PD

48、U 对PDU编号 PDU（0），PDU（1），以免收方重复收PDU 规定最大应答等待时间，超时重发，以免无限等待（死锁） 规定最大重发次数，超次数退出报高层，以免无限次重发（死锁） 接收方 收到PDU触发确认 收到正确的PDU，发送ACK 收到错误的PDU，发送NAK(或不动作) 可对ACK/NAK编号，避免错误应答配对 丢弃重复帧，错误帧 规定最大接收等待时间，超时退出并上报高层 注意： 发送方必须设置缓冲区存放未收到ACK的PDU，以备重发,2012 SPLENG,3.4.2 连续发送的滑动窗口协议的概念,引入 改进停等协议在等待应答时对资源的浪费 在应答信号未到来之前，利用等待应答的时间

49、，连续传送多个PDU 这样使信道处于“忙”状态，提高长延时信道的通信能力 假设可最多连续发送的帧为Ws个，则称发送窗口为Ws 若接收方可最多连续接收并存储的PDU为Wr个，则接收窗口为Wr 典型的发送窗口大于1的滑动窗口协议有 回退n帧协议 选择性重传协议 停等协议是一个特例：Ws=Wr=1,2012 SPLENG,3.4.2 连续发送的滑动窗口协议的概念,几个基本概念 关于PDU的编号 假设：用N位二进制表示PDU的编号 则：PDU的编号为0，1. 2N-1 循环使用 例如用2位二进制表示编号，则PDU编号为0、1、2、3 关于应答编号及含义 通常有两种理解 理解1：ACK（K），对PDU（

50、k）的肯定应答，希望下一帧接收PDU（K+1） 理解2：ACK（K），对PDU（k-1）的肯定应答，希望下一帧接收PDU（K） 只要收/发双方协商好，任选一种均可 本课件选用第二种方式,2012 SPLENG,注意发送窗口的移动 如果应答速度够快，发方可以一直连续发送 窗口的滑动 发送窗口：在收到窗口内数据的确认时滑动到该帧的下一帧 接收窗口：向上层递交一个DU，就向后移动窗口,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,3.4.3 连续发送的滑动窗口协议（动画）,0,1,2,3,4,5,6,7,8,0,1,2

51、,3,4,5,6,7,8,0,1,2,3,4,5,sender,ACK1,ACK4,receiver,ACK6,ACK8,ACK1,超时,ACK6,2012 SPLENG,确认帧编号(超前应答)扩,Fm(i),ACK(i+1),Fm(i),ACK(i+1),x,ACK(i+1): Fm(i)已收到，期望接收Fm(i+1),DU,Vr+;,发送 ACK(N=Vr),接收Fm(k),K=Vr,递交上层,丢弃Fm(k),序号正确的Fm(k), Vr+后应答ACK(Vr) 序号错误的Fm(k), Vr不变,应答ACK(Vr),Vr,OnRcvFm(pSkb) pF = (FmHdr*)skbGetDa

52、taPtr(pSkb); skbPop(Skb,sizeof(FmHdr); if(pF-seqN = Vr) NetRx(pSkb); Vr+; / for next frame else skbFree(pSkb); SendACK(Vr); ,2012 SPLENG,3.4.3 回退n帧协议（Go back n）,是一个发送窗口为Ws，接收窗口为1的滑动窗口协议 教材. 基本思想 发送方 一次可连续发送多个PDU 始终维持未应答的PDU个数某一个值（发送窗口大小） 超时重发窗口未被确认的所有PDU（回退n） 接收方 一个一个地按序收PDU 序号及内容正确的PDU，数据上交上层 出错的PD

53、U及后续（非期望）的PDU全部丢弃。 要求： 发送缓冲区为Ws个 接收缓冲区为1,2012 SPLENG,3.4.3 回退n帧协议（Go back n）,发送窗口滑动举例 假设；用3位二进制对PDU编号，发送窗口 Ws=4 PDU编号为0、17循环使用 假设：已连续发送了03号PDU，等应答 则： 窗口内的PDU为0-3号 如收到ACK（2），则 将窗口底部移到2，窗口顶部向前移，保持窗口大小为Ws=4，此时新窗口内的PDU为2、3、4、5,2012 SPLENG,3.4.3 回退n帧协议（Go back n）,假设PDU编号为3位二进制数，Ws=4 每帧确认，ACK（K）表示希望收下一个PD

54、U（K）,5,6,0,1,2,4,5,6,丢弃,ACK（3） 收到PDU（2） 下一个收 PDU（3）,2012 SPLENG,3.4.3 回退n帧协议（Go back n）,协议运行原理 发送方 窗口尺寸：1Ws2N-1，最多连续发送窗口中的Ws个PDU 窗口滑动：收到期望的Ack(k)：窗口底部移到 PDU（k），窗口顶部向前移动，始终保持窗口里有Ws个PDU未确认 窗口滑动后，发送新进入窗口的PDU 超时重发： 超过T未收到期望的Ack，重发窗口中的PDU(回退整个窗口) 超次数失败：超过最大重发次数Nmax仍无正确应答,2012 SPLENG,3.4.3 回退n帧协议（Go back

55、n）,协议运行原理 接收方 窗口尺寸：Wr=1 按序接收：按照PDU编号依序接收，出错、乱序PDU一律丢弃 确认含义：Ack(k)表示对k-1及以前各编号的PDU的确认，同时期望接收第k号PDU 确认策略： 按序到达的PDU可立即确认，也可延迟确认(收到多帧后一起确认)，但出错或乱序的PDU，确认Ack(k)（期望接收k号PDU）或不应答,2012 SPLENG,3.4.3 回退n帧协议（Go back n）,如果Ws2N，会出现什么情况？（协议会失败！） 假设：N=2，则PDU为0-3号（4个）循环使用,重复，无法分辨,ACK（0） 希望下一个收 PDU（0）,Ws=4，协议失败,2012

56、SPLENG,3.4.3 回退n帧协议,Select the go back Number N 发送PDUi时，继续发送后续的PDU，直到“预期”收到ACKi+1的时刻为止 可持续发送N个PDU：PDUi . PDUi+N-1 发送序号超前应答序号N,2,t,2012 SPLENG,3.4.4 选择性重传协议（selective repeat）,发送窗口为Ws，接收窗口为Wr的滑动窗口协议 教材.3 基本思想 改进回退n帧协议由于一个PDU错，需重传后续多个PDU的问题 发送方 对应一个发送窗口，可连续发送窗口内的多个PDU，并保持未被确认的PDU个数为窗口值 只重发接收方指定序号的PDU或超

57、时的PDU 接收方 也对应一个接收窗口，接收序号落在窗口内的PDU，存储出错的后续PDU及乱序的PDU 窗口外PDU一律丢弃，指定需重发的PDU，排序并按序上交数据 要求： 发送缓冲区为Ws个 接收缓冲区为Wr个,2012 SPLENG,3.4.4选择性重传协议,除正常的应答ACK（K）外，增加一个否定应答NAK（K），两者含义不同： ACK（K）：表示收方已正确收到K-1及以前所有的PDU，希望下一个接收K号PDU，K号及后续的PDU一定还未收到 NAK（K）：表示第K号PDU出错或丢失，但K号前的所有PDU收到，希望重发第K号PDU，还隐含K号以后的后续PDU可能已收到，只等PDU（K）的到来，重新排序后便可按序上交,2012 SPLENG,3.4.4选择性重传协议,协议运行原理 发送方 窗口尺寸：1Ws2N/2，最多连续发送窗口中的Ws个PDU 窗口滑动：与回退n帧协议相同 选择重发：收到NAK（K），重发PDU（K） 超时重发：超过T未收到期望的ACK，重发当前超时未应答的PDU 超次数失败：超过最大重发次数Nmax仍无正确应答，报告上层