ch33讲数据链路层讲义(打印版)

1第三章数据链路层(6学时)本章概述:数据链路层主要内容为:两台相邻机器之间实现可靠、有效的通信而涉及到的一些算法。所谓相邻，意思是指两台机器通过一条通信信道连接起来，这里的通信信道在概念上就像一条线(比如同轴电缆、电话线或者点到点的无线信道)。一条信道像一条线,这也暗示了它的一个本质特性,即在一条信道上递交的数据位的顺序与发送的顺序完全相同。相邻机器的通信并不简单,影响因素有:通信线路的偶尔错误,通信线路的数据传输率有限,传输延迟等.所以协议必须考虑这些因素的影响.数据链路层的任务是将物理层提供的原始位流转换成可供网络层使用的帧流。数据链路层用到了各种成帧的方法，包括字符计数法、字节填充法和位填充法。数据链路协议可以提供错误控制能力，以便重传损环的或者丢失的帧。为了避免快速的发送方淹没一个慢速的接收方,数据链路协议还要提供流控制功能。滑动窗口机制是—种被广泛使用的技术，它可以方便地将错误控制和流控制结合在一起来考虑。滑动窗口协议可以按照发送方的窗口大小和接收方的窗口大小来进行分类。当两个窗口的大小都是l的时候，滑动窗口协议变成了停—等协议。当发送方的窗口大于1(例如，为了避免发送方由于长的传输延迟而阻塞线路)的时候，接收方可以有两种实现办法：除了下一个顺序帧以外其他的帧都丢弃；或者将所有乱序的帧都缓存起来，一直到需要这些帧的时候。3.1数据链路层设计要点数链层基本功能:向网络层提供一个定义良好的服务接口;处理传输错误;调节数据流,防止淹死接收方.图3.1分组和帧之间的关系3.1.1为网络层提供服务图3.2(a)虚拟通信过程;(b)实际通信过程2图3.3数据链路层协议的位置3.1.2成帧1．字符计数法在帧头中用一个域来表示整个帧的字符个数缺点：若计数出错，对本帧和后面的帧有影响图3.4一个字符流(a)无差错(b)有一个差错2．带字符填充的首尾字符定界法缺点：局限于8位字符和ASCII字符传送。图3.5(a)有标志字节作为分界的帧;(b)字节填充前后的4个字节序列例子33．带位填充的首尾标记定界法-帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag)-“0”比特插入删除技术图3.6位填充(a)原始数据;(b)线路上的数据;(c)删除填充之后存储在接收方存储器中的数据4．物理层编码违例法802LAN：曼彻斯特编码或差分曼彻斯特编码用high-lowpair/low-highpair表示1/0，high-high/low-low不表示数据，可以用来做定界符。注意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。3.1.3错误控制帧完全丢失一般方法：接收方给发送方一个反馈（响应）。接收方反馈接收情况信息确认:肯定性确认否定性确认出错情况-帧（包括发送帧和响应帧）出错；-帧（包括发送帧和响应帧）丢失计数器(计时用)-收到重复帧帧编号通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。3.1.4流控制淹没问题,两种流控制策略:基于反馈的流控制和基于速率的流控制(第5章讲)3.2错误检测和纠正差错出现的特点(错误分为两种)：随机的,单个位,孤立的错误，连续突发（burst）一次连续许多位错误更难以纠正处理差错的两种基本策略-使用纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。-使用检错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错。纠错码(error-correctingcode),技术上又称为前向纠错(forwarderrorcorrection)(适用于低可靠性信道—无线链路,在数据块中加入足够冗余信息,减少重传,因重传也可能是错误的)-码字（codeword）：一个帧包括m个数据位，r个校验位，n=m+r，则此n比特单元4称为n位码字。-海明距离（Hammingdistance）：两个码字之间不同的比特位数目。例：0000000000与0000011111的海明距离为5如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字；为了检查出d个错（单比特错），需要使用海明距离为d+1的编码；为了纠正d个错，需要使用海明距离为2d+1的编码。最简单的例子是奇偶校验，在数据后填加一个奇偶位-例：使用偶校验（“1”的个数为偶数）10110101——10110101110110001——101100010-奇偶校验可以用来检查奇数个错误。设计纠错码-要求：m个报文位，r个校验位，纠正单比特错；-对2m个合法报文中任何一个，有n=m+r个与其距离为1的非法码字，因此每个合法的报文都要求n+1个位模式,专门供它使用.由于总共只有2n个位模式,所以有：(n+1)2m2n-利用n=m+r，得到(m+r+1)2r。给定m，利用该式可以得出校正单比特误码的校验位数目的下界.例如,m=8,则r=4.海明码-码位从左边开始编号，从“1”开始；-位号为2的幂的位是校验位，其余是信息位；-每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。-为看清数据位k对哪些校验位有影响，将k写成2的幂的和。例：11=1+2+8海明码工作过程-每个码字到来前，接收方计数器清零；-接收方检查每个校验位k(k=1,2,4…)的奇偶值是否正确；-若第k位奇偶值不对，计数器加k；-所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为m，则第m位出错。例：若校验位1、2、8出错，则第11位变反。使用海明码纠正突发错误-可采用k个码字（n=m+r）组成kn矩阵，按列发送，接收方恢复成kn矩阵-kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错。5图3.7利用海明码来纠正突发性错误例题:习题3-9练习:3-10,3-11假设使用海明码来传输16位的报文.请问,需要多少个检查位才能确保接收方可以检测并纠正单个位错误?对于报文1101,0011,0011,0101,请给出所传输的位模式.假设在海明码中使用了偶数位.解:m=16,根据公式(m+r+1)2r得r5,即至少需要5个检查位.(1,2,4,8,16)1101,0011,0011,01011=13=1+22=25=1+44=47=1+2+47=1+2+411=1+2+88=812=4+811=1+2+815=1+2+4+812=4+817=1+1614=2+4+819=1+2+1616=1621=1+4+160110,1011,0011,0011,1010,1(答案错误)0111,1011,0011,0011,1010,1(正确)检错码(error-detectingcode)(适用于高可靠性信道—光纤)使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。循环冗余码（CRC码，多项式编码）循环冗余校验码CyclicRedundancyCheck-110001，表示成多项式x5+x4+1生成多项式G(x)GeneratorPolynomial-发方、收方事前商定；-生成多项式的高位和低位必须为16-生成多项式必须比传输信息对应的多项式短。CRC码基本思想-校验和（checksum）加在帧尾，使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出错。校验和计算算法-设G(x)为r阶，在帧的末尾加r个0，使帧为m+r位，相应多项式为xrM(x)；-按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串；-按模2减法从对应于xrM(x)的位串中减去余数(等于或小于r位)，结果就是要传送的带校验和的多项式T(x)。图3.8多项式编码校验和的计算过程CRC的检错能力-发送：T(x)；接收：T(x)+E(x),E(x)0,E(x)中的每一个”1”位都对应于有一位变反了；-余数((T(x)+E(x))/G(x))=0+余数(E(x)/G(x))7-若余数(E(x)/G(x))=0，则差错不能发现；否则，可以发现。CRC检错能力的几种情况分析-如果只有单比特错，即E(x)=xi，而G(x)中至少有两项，余数(E(x)/G(x))0，所以可以查出单比特错；-如果发生两个孤立单比特错，即E(x)=xi+xj=xj(xi-j+1)，假定G(x)不能被x整除，那么能够发现两个比特错的充分条件是：xk+1不能被G(x)整除(ki-j)；-如果有奇数个比特错，即E(x)包括奇数个项，因为在模2系统中,没有一个奇数项多项式包含x+1作为因子,所以G(x)选(x+1)的倍数就能查出奇数个比特错；-具有r个校验位的多项式能检查出所有长度r的突发性差错。长度为k的突发性连续差错可表示为xi(xk-1+…+1)，若G(x)包括x0项，且k-1小于G(x)的阶，则余数(E(x)/G(x))0;-如果突发差错长度为r+1，当且仅当突发差错和G(x)一样时，余数(E(x)/G(x))=0，概率为1/2r-1;-长度大于r+1的突发差错或几个较短的突发差错发生后，坏帧被接收的概率为1/2r。四个多项式已成为国际标准-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+x5+x4+x2+x1+1IEEE802使用CRC-32硬件实现CRC校验-网卡NIC（NetworkInterfaceCard）练习:3-1483.3基本数据链路层协议一个无限制的单工协议工作在理想情况，几个前提：-单工传输-发送方无休止工作（要发送的信息无限多）-接收方无休止工作（缓冲区无限大）-通信线路（信道）不损坏或丢失信息帧工作过程-发送程序:取数据，构成帧，发送帧；-接收程序：等待，接收帧，送数据给高层一个单工的停-等协议增加约束条件：接收方不能无休止接收。解决办法：接收方每收到一个帧后，给发送方回送一个响应。工作过程-发送程序：取数据，成帧，发送帧，等待响应帧-接收程序：等待，接收帧，送数据给高层，回送响应帧。物理层数据链路层网络层运输层应用层物理层网络层运输层应用层数据链路层Node1Node29有噪声信道的单工协议增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。解决办法：出错重传。带来的问题：-什么时候重传——定时-响应帧损坏怎么办（重复帧）——发送帧头中放入序号-为了使帧头精简，序号取多少位——1位发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（PositiveAcknowledgementwithRetransmission）或ARQ（AutomaticRepeatreQuest）工作过程物理层数据链路层网络层运输层应用层物理层网络层运输层应用层数据链路层Node1Node2103.4滑动窗口协议单工——全双工捎带/载答（piggybacking）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。-优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断；-带来的问题：复杂。本节的三个协议统称滑动窗口协议，都能在实际（非理想）环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求。滑动窗口协议（SlidingWindowProtocol）工作原理-发送的信息帧都有一个序号，从0到某个最大值，0~2n-1，一般用n个二进制位表示；-发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大小可变；-发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1；-接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧；-接收窗