《《计算机通信网》第3章数据链路层.pptx》由会员分享，可在线阅读，更多相关《《计算机通信网》第3章数据链路层.pptx（53页珍藏版）》请在三一办公上搜索。
1、第3章 数据链路层,3.1 数据链路层概述3.2 成帧与帧定界3.3 差错检测与校正方法3.4 差错与流量控制协议3.5 协议描述与验证3.6 数据链路层协议案例,3.1 数据链路层概述,链路层模型,本地连接,传输系统,G.703,G.703,远程连接,物理层,网络层,链路层,链路层,网络层,链路层,链路层,网络层,传输系统提供透明的bit 传输,3.1 数据链路层概述,DL面临的环境,网络层,数据链路层,物理层,SAP,SAP,SAP,SAP,网络层,数据链路层,物理层,分组,帧,装入,分组,取出,10101101,10101101,帧,发送方,接收方,信道有噪声，bits可能出错,可能装入
2、太快取出跟不上,3.1 数据链路层概述,链路层模型,链路层,网络层,物理层,010101,比特传输,传输信号,Packet,物理层实现了把比特传输转换成信号传输、进入信道。网络层需要把一个个分组送到对方网络层链路层组织一个个分组，用比特传输实现逐个分组的传输和接收,3.1 数据链路层概述,链路层的基本任务,物理层,Asynchronous,Block,Synchronous,DU,Framing(帧同步)发送：转换成特定的bit传输形式，将Frame送出接收：界定每个frame的位置，取出frame,DU,Error Control(差错控制)发送：组织DU(frame)，方便对方检查错误接收
3、：检测DU是否出错，DU出错的处理,Link Control(链路控制)双方通过配合，实现：链路的使用规则，流量控制、汇聚分发等,DU,Service(服务)为上面的实体提供分组传输服务,3.1 数据链路层概述,链路层任务模型,framing,ErrorControl,Data LinkControl,framing,ErrorControl,Data LinkControl,Physical Layer,Data Link Layer,Network Layer,DU,DU,Frame,约定成帧方式,约定出错处理手段,约定控制方法,可用的通信功能,DU,3.1 数据链路层概述,链路层效率定义
4、链路层有效数据率 r=ni/T（ni：第i帧bit数，T：测量总时间）物理层信道的速率 R b/s链路层效率：=r/R（1）,链路层,链路层,Link Layer Services,三种服务的示意图,有确认面向连接,无确认无连接,Frame,ack,有确认无连接,Frame,ack,连接确认,连接请求,Frame,Frame,ack,拆除确认,拆除请求,B方,A方,Link Layer Services,三种可能的服务无确认的无连接服务无需对方许可，直接向对方发送Frame，对方不需要反馈确认信息优点：不受等待确认的拖累；缺点：frame传输可靠性不高信道效率：不等待确认，可提高信道效率，但传
5、输出错降低信道效率协议考虑：PDU中含源/目的地址有确认的无连接服务无需对方许可，直接向对方发送Frame，需要对方反馈确认信息优点：通过重传增加了可靠性；缺点：受等待应答的拖累保持发送和确认间的正确对应关系所采取的措施会大大降低信道使用效率协议考虑：PDU编号，PDU中含源/目的地址、单帧确认，差错检测与重传有确认的面向连接服务需事先与对方沟通，双方建立起一套复杂的发送、确认机制来实现恢复差错、排除重复、维持顺序的可靠通信适合于有大量Frame传输的场合协议考虑：PDU编号、确认、差错控制（丢弃错帧和重复帧，请求重发错帧）,3.2 成帧Framing,成帧(或帧同步)：就是确定帧的界限（起与
6、止）通俗理解：发送方：在帧的前后各加入事先商定好的标记接收方：在bits中寻找标记来识别帧的起与止需要特别考虑：若数据与帧的起止标记相同时，发送方必须采取措施否则可能会引起接收方的误断成帧方法：字符计数法字符填充首尾界定法位填充首尾界定法物理层编码违例法,.,成帧,不同传输方式下的帧同步同步传输方式(Sync,连续bit流)连续的bit流传递离散的Frame每个Frame都成为连续bit流中的一段，接收方识别并取出Frame异步传输方式(Async,异步字节序列)每个Frame转换为异步字节序列传送，接收方收集字节序列，还原Frame数据块传输方式(Block)每个Frame形成一个数据块传送
7、。,Sync信道的帧同步技术,连续的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,反变换,变换,
8、Frame,连续bit流,空闲,空闲,空闲,特殊pattern,Sync信道的帧同步技术,发送,开始,扫描Frame,发现Pattern,Pattern变换,扫描结束,发送Frame,否,是,结束,否,是,接收,开始,否,检测pattern,发现,存储数据,否,检测pattern,发现,复原Frame,是,继续,是,结束,是,Frame开始,Frame结束,否,Pattern选择-易于变换-易于检测-易于反变换,Sync信道的帧同步技术,位填充首尾定界法（0比特插入/删除技术)Pattern=01111110称为定界标志F(Flag)Frame内F的变换和反变换(利用F中连续6个1的性质)变换
9、：Frame中如果出现连续5个1时，插入一个0提取从第一次出现非F开始，到重新出现F时的所有bit反变换Frame中出现连续5个1时，删除后面的1个0采用01111110的特点：变换与发送合一：发送连续5个1，加发一个0接收与复原合一：连续接收5个1，下一bit若是0则直接去掉，否则，应该出现的就是01111110结束该帧,位填充首尾定界法,发送：在帧体部分出现连续5个1，无条件地插入一个0 接收：在帧体中扫描连续5个1，无条件去掉后面的0,01111110,01111110,101011111,11110010,0,0,成帧,101011111,11110010,0,0,位填充首尾定界法,位
10、填充(实现示意图),01111110,帧提取,01101010,移位寄存器,F检测结果,帧体,帧体,“0”bit删除,0bit插入,控制,接收,发送控制,数据,位填充首尾定界法,软件模拟int Send(char*pF,int Len)int i,j,c,msk,sn,cnt;sn=0;for(i=0;iLen;i+)/循环帧的字节长度 msk=1;cnt=0;for(j=0;j8;j+)/8bit c=pFi/回送发送总bit数,假定函数Xmitb(c)：向信道发送c(1bit),Async信道的帧同步技术,描述以字节(8bit)为单位的传输方式逐字节传输实现Frame传输帧同步讨论Fram
11、e间留有足够的时间间隔，以区分各个Frame对Frame传输能力有较大的影响Frame间的时间间隔不够大，帧与帧区分易出错两种典型帧同步技术字节计数法字符填充首尾定界法,PSTN,成帧字符计数法,也可称为字节计数法假设一个字符由8位二进制数表示基本思想在帧头的第1个字节指明帧内的字节数问题字节计数值可能在传输中出错（被篡改）简单、不可靠,11101010 00101110 01010101 010111010 10101011,发送,错,00000010,00000110,00000011,00000110,字符填充首尾定界法,思想与同步方式的位填充类似，不同的是以字节为单位方法：“定界字符”
12、在帧体的前后都用某个特定的字节加以“定界”帧体中也可能出现该定界字符，通过变换消除接收时提取Frame后，通过反变换复原局限性：数据的长度总是以字符或其倍数为单位定界字符:F(Flag)=01111110,第1帧,第2帧,字符填充首尾定界法,将F变换为某个其它字节(x)存在问题：帧体中其它字节也可能出现x，反变换xF时就出错Frame体中定界字符的变换方法一字节到两字节的变换,变换后帧体中不出现F帧体中的F和x都需要变换：Fxy;xxzy和z是另外选取的两个字符，对y、z不再需要变换分析若帧体中出现xy变换：xy(xz)y；反变换：xzyxy,正确复原可以验证：对帧体中出现F,x,y,z的任意
13、顺序的组合，只对其中的所有F和x进行变换，反变换时都能正确复原,字符填充首尾定界法,处理帧体内的特殊字符(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：接收字节,练习,分两组：一组成帧，一组提取帧分别用位填充法、计数法、字
14、符填充法进行练习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,字符填充首尾定界法,教材PP.159,块传输信道的帧同步技术,当用电缆或无线直接通信(不经过传输系统)时，最简洁的通信方式是块传输方式，每个块就是一个Fram
15、e块传输方式每个Frame都带有前导bit序列(preamble)和后续bit序列(postamble),以确保Frame的头和尾能正确检测和接收因此需要确定：Preamble结束和Frame开始的比特位置Frame结束和postamble开始的bit位置同步技术违例编码法：利用信息bit的码型特性，用非正常码型来进行界定位置,preamble,postamble,块传输信道的帧同步技术,例1：曼切斯特编码(1b/2b,10M以太网)Block=010101JKFramebodyKJ010101例2：4b/5b编码(100M以太网)4bit数据映射成5bit码组000011110,000101
16、001,111111101空闲11111,定界符111000,定界符210001Block=010101定界符1FrameBody定界符2 010101例3：8b/10b编码(1000M以太网)8bit数据映射成10bit码组从1024个码组中只需选取256个来代表8bit的各个值剩余1024-256个码组可作为控制、定界等多种功能,0=,1=,违例,块传输信道的帧同步技术校验和法,利用ATM信元固定、且长度较短(53字节)的特性信元前4字节是头部，第5字节是校验和，使用循环冗余校验设40位寄存器，计算校验和正确则可能发现了一个信元不正确则移一位，再次计算，直到得到一个信元,成帧,100110
17、1000101011111101000110110001111011100,信元头,信元体,信元头,信元体,3.2 成帧讨论与理解,帧定界正确，请问帧一定无错吗？一个帧定界出错，请问用字符计数法，后续的帧也不能正确识别吗？为什么？用字符填充法和位填充法，情况又如何？位填充法比字符填充法有哪些优越性？,Framing小结,不同的成帧技术以适应信道的不同传输体制需求：接收方易于提取、出错时对后续帧的提取影响小较高的信道利用率、较简单的实现位填充、字符计数、字符填充、违例编码、校验和与其它功能的关系实现的是信道上传输和接收帧的功能，不涉及帧的内容链路层其它功能直接对帧的处理，不受传输体制影响,fra
18、ming,framing,差错处理、链路功能,差错处理、链路功能,3.3 差错检测与纠正,信道传输过程中(误码：10;01)随机干扰：随机错(均匀性)突发干扰：突发错(一定的突发长度)出错处理检错：验证是否出现了误码纠错：找到误码的位置，纠正之,01111110,0111111001101110100111111001111111001111110,Bit错可能造成：帧体错帧错误 定界错帧错误、帧丢失、多余帧 信道异常(多于6个1)信道失序,原码,出错后,3.3 差错检测与纠正,如何理解数据传输中的差错？一位错就等于全帧错关于误码率Pe与误帧率Pf假设帧长度为N比特，误码率为Pe（设每比特出错
19、独立）则比特正确率为：1-PeN比特正确率为（1-Pe）N帧出错率（误帧率）（一帧中至少一位错）为 Pf=1-（1-Pe）N NPe（帧出错的概率与帧成近似成正比）,3.3 差错检测与纠正,差错控制，意味着：首先检测出差错然后是纠正差错检测差错采用冗余编码技术进行差错检验编码纠错码：不仅能检测差错，且能知道错在哪儿检错码：只能检测差错，但不知错在哪纠正差错前向纠错FEC（Forward Error Correction）用纠错码，收方检错并自动纠错 自动请求重发ARQ（Automatic Request for Repeat）用检错码，收方检错通知发方重发恢复差错计算机网络中常采用,3.3 差
20、错检测与纠正,假设待传数据为m位为检测差错，所需要的冗余位（校验位）为r位则传输码长度n=m+r通常采用纠错码或检错码，即：按某种算法计算出校验位然后将m位数据和r位校验码形成传输码接收方根据相同的算法重新计算校验位，判断是否出错,3.3 差错检测与纠正,一种直观简单的纠错方法每个bit重传三次：1111;0000如果3bit中有1bit错,我们可以纠正过来101、110、011 111 1001、010、100 000 0如果3bit中有2bit或3bit全错，则无法纠正了101 111?000?无法知道是1bit还是2bit错将每个bit重传2n+1次，n越大，纠错能力越强(传输效率越低)
21、不管n如何取，我们仍不知道是否真的纠正了错误，只能认为增大了纠正错误的概率,3.3.1 纠错码海明码,海明距离（Hamming Distance）教材P162163两个等长码对应位不同的个数，称作这两个码的海明距离例：0001111和0001100的海明距离为2某种编码的任意两个有效编码之间的距离称为该编码的海明距离结论1：检出d个错误的检错码，海明距离至少为d1结论2：纠正d个错误的纠错码，海明距离至少为2d1 海明码是一种能纠正一位错的纠错码,3.3.1 纠错码海明码,假设数据为m位则纠正一位错的校验码 r 满足 m+r+12r（证明：P163）例如：m=3，3+r+12r r=3则海明码
22、码长=m+r=6位海明码的编码为r与m的混排方式，规则为：检验位r的序号为2的整次幂1，2，4，8，信息位m的序号为2的非整次幂，3，5，6，7.r1r2m3r4m5m6,3.3.1 纠错码海明码,假设数据为011，该如何确定海明编码？编码应为：r1r2m3r4m5m6现已知：m3 m5 m6=0 1 1关键是确定r1、r2和r4r的计算方法首先找出哪些与 r1、r2和r4相关的数据位将数据位数拆成2的整次幂相加如3=1+2 m3与r1和r2相关然后将与某r相关的数据位模2加(异或），结果为该r值与r1相关的数据位：m3、m5 则r1=01=1与r2相关的数据位：m3、m6 则r2=01=1与
23、 r4相关的数据位：m5、m6 则r4=11=0得出：011的海明编码为110011,3.3.1 纠错码海明码,已知：011的海明编码为110011（r1r2m3r4m5m6）假设：编码在传输中出了一位错 110011 错成 110010 接收方的纠错规则首先：对于每个ri，将ri和与之相关的数据位进行依次异或结果为1，则记录Ai=i（i为r的序号）结果为0，则记录Ai=0然后累加，计算Ai的值，结果等于几就是该对应位出错最后，将出错位取反进行纠错计算过程r1m3 m5=101=0 则 A1=0 r2m3 m6=100=1 则 A2=2 r4m5 m6=010=1 则 A4=4 出错位：Ai=
24、A1+A2+A4=6纠错：110010 110011（差错位取反）,3.3.2 差错检测,采用冗余编码技术进行差错检验编码基本思想发送方：将待发数据按照某种规则加上一定的冗余位后，进行传输，接收方：对收到的数据进行判断，是否符合原规则，若符合则无错，不符合则出错。,C(x)=R(x)无错C(x)R(x)出错,3.3.2 差错检测检错码,奇偶校验码循环冗余码CRC校验和编码,3.3.2 差错检测奇偶校验码,增加冗余位使信息码中的“1”的个数为奇数或偶数的编码奇校验：“1”的个数为奇数偶校验：“1”的个数为偶数具体实现：信息位逐位进行模2加（异或运算）a1a2a3a4a5 结果为0，偶校验时 校验
25、位为0，奇校验时，校验位为1结果为1，偶校验时 校验位为1，奇校验时，校验位为0例 信息字段 奇校验码 偶校验码 011001 011001 0 011001 1 出错为：001001 0 001001 1重新计算校验和：1,0,纠正突发错,数据组织成矩阵，按行编写奇偶效验码发送时按列发送出现突发错误时，可按行纠正,0010111,3.3.2 差错检测循环冗余码,循环冗余码（CRC:Cyclic Redundancy Code）教材p165167对任意m位二进制流，补充r个0用规定的r+1位除数进行求余计算，得到r位效验码数据与r位效验码组成传输码组发送出去,1011010,11000101,
26、0000000,1011010,1,1,0,1,1,0,0,m位数据,r位CRC,1010110,模2加,3.3.2 差错检测循环冗余码,CRC校验对收到的完整的数据帧用发送方相同的r+1位除数进行求余计算余数为0则无错,11000101 11100000 11000101 01001011 00000000 10010110 11000101 10100111 11000101 11000101 11000101 00000000 00000000 0000000,11000101,3.3.2 差错检测循环冗余码,基于任何一个二进制位串组成的代码，都可以与系数只为0和1的多项式建立一一对应的
27、关系。一个K位的数据可以看成是从xK-1x0次系数为0和1的多项式 x4 x3 x2 x1 x0 数据：1 1 0 1 1多项式 x4+x3+x+1,3.3.2 差错检测循环冗余码,1）基本思想：设：数据m位，对应多项式M（x），校验码为r位，对应多项式R(x)给定：生成多项式G（x），阶数为r，r+1位，高位和低位系数为1发送方：将M（x）通过G（x）计算出带校验和的传输多项式T（x）接收方：将收到的带校验和的多项式T（x）除以G（x），如有余数，出错，能除尽，无错2）校验码与传输多项式的计算STEP 1 在m位数据之后加上 r个0，数据位变成m+r位，对应多项式x r M（x）STEP 2
28、 计算校验码多项式：x r M（x）/G（x）(对应二进制位串模2除)，余数为校验码，对应多项式为R（x）STEP 3 计算传输多项式：T（x）=x r M（x）+R（x），对应系数位串为传输数据,3.3.2 差错检测循环冗余码,示例：数据：110110 G（x）=x4+x+1 对应位串 10011（除数）在数据后加4个0 形成 1101100000 被除数，求余数,3.3.2 差错检测冗余循环码,值得注意：多项式变为码字时，首位对应最高次，中间的“0”不能丢掉在计算中涉及的“+”和“-”均为模2运算（加、减结果一样，异或运算，相同为0，相异为1）模2除商1的原则：只要被除数的首位为1，且位数
29、与除数相同则商1，如上例中红色双向箭头处（被除数为10000，除数为10011）,3.3.2 差错检测冗余循环码,CRC码的检错性能（r个校验位比特）所有单个错所有2bit错所有长度小于或等于r个bit 的突发错长度为r+1个比特的突发错，漏检率为：1/2 r-1长度大于r+1比特的突发错，漏检率为：1/2 r校验码的计算一般都用硬件实现，有参考电路，也可用软件实现。硬件计算时是边发边计算，故通常校验码在帧尾。常用的CRC多项式：CRC-8=x8+x2+x+1CRC-12=x12+x11+x3+x2+x+1 CRC-16=x16+x15+x2+1,漏检概率为3/327674.6*10-5CRC
30、-CCITT=X16+x12+x5+1CRC-32,漏检概率为3/2147483648 7*10-10,3.3.2 差错检测校验和,校验和 ChecksumC语言：for(i=0;iN;i+)Sum+=Wi；基本思想：按一定大小进行累加累加结果产生进位，将进位累加到结果中最终累加结果取反，获得校验和,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 7
31、2 22 01 3c fa,校验 1 c3 04 3c fa 1 fffe 0,3.3.2 差错检测校验和,CheckSum算法描述将M(x)作连续多个16bit无符号整数看待(奇数字节长度帧尾部添加一个全0字节)，全部累加起来,结果分为两部分：16bit累加值，进位累加值，把进位值加到16比特累加值上后再取反，构成16 bit 的CheckSum,W0,W1,WN,+,M(x),16bit累加值,进位值,16bit累加值,进位值,+,Sum,Sum,CheckSum,Error Control 小结,检错算法CRC，二进制异或除法，除数选择重要CheckSum，模65536加法，软件实现帧末尾附加了r-bit检错码(也称校验码)检错能力r越大，检错能力越强存在坏帧漏检的概率应用发现并丢弃传输中出现的坏帧，保证继续处理的帧基本上是正确的,Frame,校验码,作业4,1、请写出通常采用的成帧方法及各种成帧法的特点。假设帧标记符出错，请问哪种成帧方法将不能检测到后续所有的帧？为什么？2、如果待传数据为，假设采用“位填充法”成帧，请写出帧内容。3、假设待传数据为 100101，（1）计算校验位r的位数；（2）计算出传输该数据的海明码（要求步骤）4、假设待传数据为100101，采用CRC编码，假设生成多项式为G（X）=X4+1，计算出校验多项式R（X）。,
