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

12012SPLENG第3章数据链路层3.1数据链路层概述3.2成帧与帧定界3.3差错检测与校正方法3.4差错与流量控制协议3.5协议描述与验证3.6数据链路层协议案例22012SPLENG3.1数据链路层概述链路层模型本地连接传输系统G.703G.703远程连接物理层网络层链路层链路层网络层链路层链路层网络层传输系统提供透明的bit传输32012SPLENG3.1数据链路层概述DL面临的环境网络层数据链路层物理层SAPSAPSAPSAP网络层数据链路层物理层分组帧装入分组取出1010…11011010…1101帧发送方接收方信道有噪声，bits可能出错可能装入太快取出跟不上★42012SPLENG3.1数据链路层概述链路层模型链路层网络层物理层010101比特传输传输信号Packet物理层实现了把比特传输转换成信号传输、进入信道。网络层需要把一个个分组送到对方网络层链路层组织一个个分组，用比特传输实现逐个分组的传输和接收52012SPLENG3.1数据链路层概述链路层的基本任务物理层AsynchronousBlockSynchronousDUFraming(帧同步)发送：转换成特定的bit传输形式，将Frame送出接收：界定每个frame的位置，取出frameDUErrorControl(差错控制)发送：组织DU(frame)，方便对方检查错误接收：检测DU是否出错，DU出错的处理LinkControl(链路控制)双方通过配合，实现：链路的使用规则，流量控制、汇聚分发等DUService(服务)为上面的实体提供分组传输服务62012SPLENG3.1数据链路层概述链路层任务模型framingErrorControlDataLinkControlframingErrorControlDataLinkControlPhysicalLayerDataLinkLayerNetworkLayerDUDUFrame约定成帧方式约定出错处理手段约定控制方法可用的通信功能DU72012SPLENG3.1数据链路层概述链路层效率定义链路层有效数据率r=∑ni/T（ni：第i帧bit数，T：测量总时间）物理层信道的速率Rb/s链路层效率：η=r/R（η≤1）链路层链路层82012SPLENGLinkLayerServices三种服务的示意图有确认面向连接无确认无连接Frameack有确认无连接Frameack连接确认连接请求FrameFrameack拆除确认拆除请求B方A方92012SPLENGLinkLayerServices三种可能的服务无确认的无连接服务无需对方许可，直接向对方发送Frame，对方不需要反馈确认信息优点：不受等待确认的拖累；缺点：frame传输可靠性不高信道效率：不等待确认，可提高信道效率，但传输出错降低信道效率协议考虑：PDU中含源/目的地址有确认的无连接服务无需对方许可，直接向对方发送Frame，需要对方反馈确认信息优点：通过重传增加了可靠性；缺点：受等待应答的拖累保持发送和确认间的正确对应关系所采取的措施会大大降低信道使用效率协议考虑：PDU编号，PDU中含源/目的地址、单帧确认，差错检测与重传有确认的面向连接服务需事先与对方沟通，双方建立起一套复杂的发送、确认机制来实现恢复差错、排除重复、维持顺序的可靠通信适合于有大量Frame传输的场合协议考虑：PDU编号、确认、差错控制（丢弃错帧和重复帧，请求重发错帧）102012SPLENG3.2成帧Framing成帧(或帧同步)：就是确定帧的界限（起与止）通俗理解：发送方：在帧的前后各加入事先商定好的标记接收方：在bits中寻找标记来识别帧的起与止需要特别考虑：若数据与帧的起止标记相同时，发送方必须采取措施否则可能会引起接收方的误断成帧方法：字符计数法字符填充首尾界定法位填充首尾界定法物理层编码违例法110101101001011011001111011110010101011100010101001011010101011011010100100100…….如何分离出一个一个的帧？★112012SPLENG成帧不同传输方式下的帧同步同步传输方式(Sync,连续bit流)连续的bit流传递离散的Frame每个Frame都成为连续bit流中的一段，接收方识别并取出Frame异步传输方式(Async,异步字节序列)每个Frame转换为异步字节序列传送，接收方收集字节序列，还原Frame数据块传输方式(Block)每个Frame形成一个数据块传送。122012SPLENGSync信道的帧同步技术连续的bit流由若干Frame和它们间的空闲bit组成注意：frame中或空闲的bit都只有两种取值：0或1关键问题：如何正确识别和提取bit流中的Frame部分？思路：假设空闲bit用某种特殊的bit模式(pattern)构成，而Frame中不会出现该pattern，则接收方就能够正确设别和提取Frame但:应该允许Frame包含任意数据，就肯定包含了这种Pattern。若能对Frame中出现的Pattern用某种变换方式消除，接收方提取出Frame后，再通过反变换，恢复原来的Frame，该假设成立Frame’FrameFrame’Frame反变换变换Frame连续bit流空闲空闲空闲特殊pattern132012SPLENGSync信道的帧同步技术发送开始扫描Frame发现PatternPattern变换扫描结束发送Frame’否是结束否是接收开始否检测pattern发现存储数据否检测pattern发现复原Frame是继续是结束是Frame开始Frame结束否Pattern选择--易于变换--易于检测--易于反变换142012SPLENGSync信道的帧同步技术位填充首尾定界法（‘0’比特插入/删除技术)Pattern=‘01111110’称为定界标志F(Flag)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’结束该帧152012SPLENG位填充首尾定界法发送：在帧体部分出现连续5个1，无条件地插入一个0接收：在帧体中扫描连续5个1，无条件去掉后面的0011111100010101111011111011111101010111111111001000成帧00101011110111111010111111111001000162012SPLENG位填充首尾定界法位填充(实现示意图)…01111110011111101001111010110101010111111010101110101110111111001111110…帧提取…01101010…移位寄存器F检测结果帧体帧体“0”bit删除01111110‘0’bit插入控制接收发送控制数据172012SPLENG位填充首尾定界法软件模拟intSend(char*pF,intLen){inti,j,c,msk,sn;sn=0;for(i=0;iLen;i++){//循环帧的字节长度msk=1;for(j=0;j8;j++){//8bitc=pF[i]&msk?1:0;测试第jbitmsk=1;准备测试下一bitXmitb(c);sn++;if(c)cnt++;elsecnt=0;//计算连续1的个数if(cnt==5){Xmitb(0);cnt=0;sn++;}}}returnsn;//回送发送总bit数}假定函数Xmitb(c)：向信道发送c(1bit)182012SPLENGAsync信道的帧同步技术描述以字节(8bit)为单位的传输方式逐字节传输实现Frame传输帧同步讨论Frame间留有足够的时间间隔，以区分各个Frame对Frame传输能力有较大的影响Frame间的时间间隔不够大，帧与帧区分易出错两种典型帧同步技术字节计数法字符填充首尾定界法PSTN192012SPLENG成帧——字符计数法也可称为字节计数法假设一个字符由8位二进制数表示基本思想在帧头的第1个字节指明帧内的字节数问题字节计数值可能在传输中出错（被篡改）简单、不可靠11101010001011100101010101011101010101011发送DATA11101010001011100101010101011101010101011错00000010接收11101010001011100101010101011101010101011000001100000001100000110★202012SPLENG字符填充首尾定界法思想与同步方式的位填充类似，不同的是以字节为单位方法：“定界字符”在帧体的前后都用某个特定的字节加以“定界”帧体中也可能出现该定界字符，通过变换消除接收时提取Frame后，通过反变换复原局限性：数据的长度总是以字符或其倍数为单位定界字符:F(Flag)=01111110F14768x31452F684314F第1帧第2帧68431414768F31452212012SPLENG字符填充首尾定界法将F变换为某个其它字节(x)存在问题：帧体中其它字节也可能出现x，反变换xF时就出错Frame体中定界字符的变换方法一字节到两字节的变换,变换后帧体中不出现F帧体中的F和x都需要变换：Fxy;xxzy和z是另外选取的两个字符，对y、z不再需要变换分析若帧体中出现xy变换：xy(xz)y；反变换：xzyxy,正确复原可以验证：对帧体中出现F,x,y,z的任意顺序的组合，只对其中的所有F和x进行变换，反变换时都能正确复原222012SPLENG字符填充首尾定界法处理帧体内的特殊字符(RFC1662，异步PPP)F=01111110(7e),定界字符x=01111101(7d),称为转义字符y=01011110(5e)z=01011101(5d)帧体1476F43x5d52F1476x5e43x5d5d52F帧体填充后发送XmitB(F)B=F？结束否是B=Frame[i++]XmitB(B)B=x？XmitB(x)XmitB(y)XmitB(x)XmitB(z)否是iLen是XmitB(F)否XmitB：发送字节XrcvB：接收字节232012SPLENG练习分两组：一组成帧，一组提取帧分别用位填充法、计数法、字符填充法进行练习F=01111110，x、y、z可自行定义可自定义若干帧来完成该练习思考字符填充法中，仅用F和x是否能够实现，如能实现，给出实现方法，如不能实现，请说明不能实现的理由帧1：1001111111100000010111010100001001100011帧2：110110110000000001100111帧3：11000101111111111101001011011111242012SPLENG字符填充首尾定界法教材PP.159252012SPLENG块传输信道的帧同步技术当用电缆或无线直接通信(不经过传输系统)时，最简洁的通信方式是块传输方式，每个块就是一个Frame块传输方式每个Frame都带有前导bit序列(preamble)和后续bit序列(postamble),以确保Frame的头和尾能正确检测和接收因此需要确定：Preamble结束和Frame开始的比特位置Frame结束和postamble开始的bit位置同步技术违例编码法：利用信息