第4章数据链路层.ppt

《第4章数据链路层.ppt》由会员分享，可在线阅读，更多相关《第4章数据链路层.ppt（99页珍藏版）》请在优知文库上搜索。

1、数据链路层数据链路层及其协议n链路与数据链路链路与数据链路 链路就是一条无源的点到点的物理线路段，中间没有任何其他的交换节点。数据链路则是另一个概念。这是因为当需要在一条线路上传输数据时，除了必须有一条物理线路外，还必须有一些必要的规程来控制这些数据的传输。把实现这些规程的硬件和软件加到链路上，就构成了数据链路。数据链路层要解决的问题q如何在有差错的线路上，进行无差错传输。ISO关于数据链路层的定义q数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。数据链路q从数据发送点到数据接收点（点到点 point to point）所经过的传输途径。n虚拟数据通路

2、，实际数据通路数据链路层提供的服务 n为网络层提供三种合理的服务q无确认无连接服务，适用于n误码率很低的线路，错误恢复留给高层；n实时业务n大部分局域网q有确认无连接服务，适用于不可靠的信道，如无线网。q有确认有连接服务数据链路层的功能数据链路层的功能数据链路层提供相邻设备间的无差错数据传输。它要完成如下功能：q链路管理链路管理 q帧同步帧同步 q流量控制流量控制 q差错控制差错控制 q帧的透明传输帧的透明传输 q寻址寻址 数据链路层协议数据链路层协议 为实现数据链路控制功能而为实现数据链路控制功能而 制定的规程或协议。制定的规程或协议。数据链路层协议的类型数据链路层协议的类型n面向字符型数据

3、链路层协议：BSCn面向比特型数据链路层协议：HDLC面向字符型数据链路层协议：BSC以字符为控制传输信息的基本单元。常见的通信控制字符：以字符为控制传输信息的基本单元。常见的通信控制字符：格式字符：格式字符：SOH（start of heading）STX（start of text）ETB（end of transmission block）ETX（end of text）控制字符：控制字符：ACK（acknowledge）NAK（negative acknowledge）ENQ（enquire）EOT（end of transmission）SYN（synchrous）DLE（data

4、link escape）面向字符型面向字符型BSC协议的协议的帧帧格式格式SYNSYNSOH报头STX正文ETB/ETXBCC报文开始同步字符用户定义报头结束分组结束报文结束校验字段正文字段面向比特型数据链路层协议：HDLCn以比特作为传输控制信息的基本单元；以比特作为传输控制信息的基本单元；n数据帧与控制数据帧与控制 帧格式相同；帧格式相同；n传输透明性好；传输透明性好；n连续发送，传输效率高。连续发送，传输效率高。n面向比特型面向比特型HDLC协议的协议的帧帧格式格式标志字段F(8位)地址字段A(8/16位)控制字段C(8/16位)信息字段I(长度可变)帧校验字段FCS(16/32位)标志

5、字段F(8位)n将比特流分成离散的帧，并计算每个帧的校验和。n物理层以比特为单位进行数据传输，数据链路层以帧为单位进行数据传输。n帧是具有一定长度和格式的信息块，一般由一些字段和标志组成。不同网络其帧格式或长度可以不同，但将比特流分成帧的方法基本相同。四种常用的方法为：字符计数法；带填充字符的首尾界符法；带填充位的首尾标志法；物理层编码违例法。n把比特流分成帧，标定帧的起始和结束，以利于进行差错控制。在数据链路层，数据的传送单位是帧。数据一帧一帧地传送，就可以在出现差错时，将有差错的帧重传一次，而避免将所有数据重传，从而实现差错控制。成帧（Framing）n成帧方法：q字符计数法（Fig.3-

6、3）n在帧头中用一个域来表示整个帧的字符个数n缺点：若计数出错，对本帧和后面的帧有影响。q带字符填充的首尾字符定界法（Fig.3-4）n起始字符 DLE STX，结束字符DLE ETXn字符填充n缺点：局限于8位字符和ASCII字符传送。q带位填充的首尾标记定界法（Fig.3-5）n帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag)n“0”比特插入删除技术q物理层编码违例法n只适用于物理层编码有冗余的网络n802 LAN：Manchester encoding or Differential Manchester encoding 用high-low pair/low-

7、high pair表示1/0，high-high/low-low不表示数据，可以用来做定界符。采用0插入删除的方法来使得收发双发同步。零比特插入/删除工作过程流量控制n流量控制q 数据链路层必须控制链路上的数据流量，保证发送与接收速度匹配，防止出现发送速度超过接收能力的现象，以免丢失数据。大多数流量控制方法的基本原理都是相同的，都需要启用反馈机制，使发方直接或是间接地获得收方指示的发送时机。在未得到允许前，禁止发出帧。如单工停等协议、滑动窗口协议等。q发方的发送速率必须小于等于收方的接收速率，否则会浪费网络资源，增加网络负担。流量控制就是对发方的发送速率进行控制。n基本流量控制方法p基于反馈的

8、流控制 接收方给发送方送回消息,告诉发送方它的状态p 基于速率的流控制 限制了发送方传输数据的速率,无需利用接收方的反馈信息差错控制n差错控制q一般方法：接收方给发送方一个反馈（响应）。比如自动重复请求（ARQ）q出错情况n帧（包括发送帧和响应帧）出错；n帧（包括发送帧和响应帧）丢失q通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。n差错出现的特点：随机，连续突发（burst）差错控制方法差错控制方法 从差错控制的角度，对于传输的信号，利用检纠错基本原理进行编码来降低差错的发生，利用差错控制编码方法进行差错控制的常用方式主要有如下几种：n 自动请求重发（ARQ）方式

9、n 反馈校验方式n 前向纠错（FEC）方式n 混合纠错（HEC）方式自动请求重发（自动请求重发（ARQARQ）方式）方式 发送端发送出可以发现错误的码字，接收端译码若检测到错误，则主动向发送端发出请求，要求重发以便纠错。这种系统要求有反馈信道且发送端和接收端都有缓存器。反馈校验方式 这种方式是发送端一边发送码字一边存贮发出的码字到缓冲区中。在接收端收到码字后，马上返回到发送端去与原发送码进行比较。如发现与发送码不同，就重发上一次的码字，直到发送端校验正确为止。这种方式进行差错控制的原理和设备都简单，但要求双向信道，且传输效率较低。前向纠错（FEC）方式 发送端发出的码字是具有一定纠错能力的码字

10、。在接收端译码后不仅可以发现错码，而且能够判断错码所在的位置并自动纠正。这种方法不需反馈信道，实时性好，传输效率较高，但纠错编码方法和设备较复杂。混合纠错（HEC）方式 实际应用中，可以结合使用ARQ方式和FEC方式。即在传输错码较少且接收端能纠正时，自动纠正错误；在错码较多、超出纠正能力但尚能检测时，采用自动请求重发方式，请求发送端重传，直到正确接收为止。该方式大大提高了通信的可靠性。n差错控制方法q处理差错的两种基本策略n使用纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。n使用检错码：发送方在每个数据块中加入足够的冗余信息，使得接收方

11、能够判断接收到的数据是否有错，但不能判断哪里有错奇偶校验码奇偶校验码 垂直奇（偶）校验垂直奇（偶）校验 水平奇（偶）校验水平水平奇（偶）校验水平 垂直奇（偶）校验（方阵码）垂直奇（偶）校验（方阵码）循环冗余编码循环冗余编码CRC：目前应用最广的检错码编码方目前应用最广的检错码编码方法之一法之一海明码：是一种纠错码。海明码：是一种纠错码。纠错码纠错码码字码字（codeword）：一个帧包括m个数据位，r个校验位，n=m+r，则此n比特单元称为n位码字。n海明距离海明距离（Hamming distance）：两个码字之间不同的比特位数目。q例：0000000000 与0000011111的海明距离

12、为5q如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字；q为了检查出d个错（单比特错），需要使用海明距离为 d+1 的编码；q为了纠正d个错，需要使用海明距离为 2d+1 的编码；n最简单的例子是奇偶校验，在数据后填加一个奇偶位（parity bit）q例：使用偶校验（“1”的个数为偶数）1011010110110101110110001101100010q奇偶校验可以用来检查单个错误。海明码n设计纠错码q要求：m个信息位，r个校验位，纠正单比特错；利用 n=m+r，得到(m+r+1)2r 给定m，利用该式可以得出校正单比特误码的校验位数目的下界n海明码q码位从左

13、边开始编号，从“1”开始；q位号为2的幂的位是校验位，其余是信息位；q每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。q为看清数据位k对哪些校验位有影响，将k写成2的幂的和。例：11=1+2+8n海明码工作过程q每个码字到来前，接收方计数器清零；q接收方检查每个校验位k(k=1,2,4)的奇偶值是否正确；q若第 k 位奇偶值不对，计数器加 k；q所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为m，则第m位出错。q若校验位1、2、8出错，则第11位变反。qFig.3-6n使用海明码纠正突发错误q可采用k个码字（n=m+r）组成 k n 矩阵，按列发送，接收方恢复成 k n

14、 矩阵qkr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错。1 2 3 4 5 6 7 8 9 10 11 1 1 1 1 1 2 2 2 2 2 4 4 4 8 8 8使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。n循环冗余码（CRC码，多项式编码）q110001，表示成多项式 x5+x4+1n生成多项式G(x)q发方、收方事前商定；q生成多项式的高位和低位必须为1q生成多项式必须比传输信息对应的多项式短。nCRC码基本思想q校验和（checksum）加在帧尾，使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出

15、错。检错码循环码的编码 n第一步若生成多项式G(x)的阶是r,将信息位左移r位，得xrM(x)；n第二步，作模2除法，求余数r(x)；余数由下式获得：n第三步，根据T(x)=xrM(x)+r(x)，求出码字。)()()()(xrxQxGxMxrnCRC的检错能力q发送：T(x)；接收：T(x)+E(x)；q余数(T(x)+E(x)/G(x)=0+余数(E(x)/G(x)q若 余数(E(x)/G(x)=0，则差错不能发现；否则，可以发现。q如果只有单比特错，即E(x)=xi，而G(x)中至少有两项，余数(E(x)/G(x)0，所以可以查出单比特错；q如果发生两个孤立单比特错，即E(x)=xi+x

16、j=xj(xi-j+1)，假定G(x)不能被x整除，那么能够发现两个比特错的充分条件是：xk+1不能被G(x)整除(k i-j)；q如果有奇数个比特错，即E(x)包括奇数个项，G(x)选(x+1)的倍数就能查出奇数个比特错；q具有r个校验位的多项式能检查出所有长度 r 的突发性差错。长度为k的突发性连续差错（并不表示有k个单比特错）可表示为 xi(xk-1+1)，若G(x)包括x0项，且 k-1小于G(x)的阶，则 余数(E(x)/G(x)0;q如果突发差错长度为 r+1，当且仅当突发差错和G(x)一样时，余数(E(x)/G(x)=0，概率为1/2r-1;q长度大于 r+1的突发差错或几个较短的突发差错发生后，坏帧被接收的概率为 1/2r。错误检测和纠正（8）n四个多项式已成为国际标准qCRC-12=x12+x11+x3+x2+x+1qCRC-16=x16+x15+x2+1qCRC-CCITT=x16+x12+x5+1qCRC-32n硬件实现CRC校验。CRC校验码的检错能力nCRC校验码能检查出全部单个错；校验码能检查出全部单个错；nCRC校验码能检查出全部离散的二位错；校验码能检查