第4章数据链路层.ppt
《第4章数据链路层.ppt》由会员分享,可在线阅读,更多相关《第4章数据链路层.ppt(99页珍藏版)》请在课桌文档上搜索。
1、数据链路层,数据链路层及其协议,链路与数据链路 链路就是一条无源的点到点的物理线路段,中间没有任何其他的交换节点。数据链路则是另一个概念。这是因为当需要在一条线路上传输数据时,除了必须有一条物理线路外,还必须有一些必要的规程来控制这些数据的传输。把实现这些规程的硬件和软件加到链路上,就构成了数据链路。,数据链路层要解决的问题如何在有差错的线路上,进行无差错传输。ISO关于数据链路层的定义数据链路层的目的是为了提供功能上和规程上的方法,以便建立、维护和释放网络实体间的数据链路。数据链路从数据发送点到数据接收点(点到点 point to point)所经过的传输途径。虚拟数据通路,实际数据通路,数
2、据链路层提供的服务,为网络层提供三种合理的服务无确认无连接服务,适用于误码率很低的线路,错误恢复留给高层;实时业务大部分局域网有确认无连接服务,适用于不可靠的信道,如无线网。有确认有连接服务,数据链路层的功能,数据链路层提供相邻设备间的无差错数据传输。它要完成如下功能:链路管理 帧同步 流量控制 差错控制 帧的透明传输 寻址 数据链路层协议 为实现数据链路控制功能而 制定的规程或协议。,数据链路层协议的类型,面向字符型数据链路层协议:BSC面向比特型数据链路层协议:HDLC,面向字符型数据链路层协议:BSC,以字符为控制传输信息的基本单元。常见的通信控制字符:格式字符:SOH(start of
3、 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 link escape)面向字符型BSC协议的帧格式,面向比特型数据链路层协议:HDLC,以比特作为传输控制信息的基本单元;数据帧与控制 帧格式相同;传输透明性好;连续发送,传输效率高。面向比特型HDLC协议的帧格式,将比特流分成离散的帧,并计
4、算每个帧的校验和。物理层以比特为单位进行数据传输,数据链路层以帧为单位进行数据传输。帧是具有一定长度和格式的信息块,一般由一些字段和标志组成。不同网络其帧格式或长度可以不同,但将比特流分成帧的方法基本相同。四种常用的方法为:字符计数法;带填充字符的首尾界符法;带填充位的首尾标志法;物理层编码违例法。把比特流分成帧,标定帧的起始和结束,以利于进行差错控制。在数据链路层,数据的传送单位是帧。数据一帧一帧地传送,就可以在出现差错时,将有差错的帧重传一次,而避免将所有数据重传,从而实现差错控制。,成帧(Framing),成帧方法:字符计数法(Fig.3-3)在帧头中用一个域来表示整个帧的字符个数缺点:
5、若计数出错,对本帧和后面的帧有影响。带字符填充的首尾字符定界法(Fig.3-4)起始字符 DLE STX,结束字符DLE ETX字符填充缺点:局限于8位字符和ASCII字符传送。带位填充的首尾标记定界法(Fig.3-5)帧的起始和结束都用一个特殊的位串“01111110”,称为标记(flag)“0”比特插入删除技术物理层编码违例法只适用于物理层编码有冗余的网络802 LAN:Manchester encoding or Differential Manchester encoding 用high-low pair/low-high pair表示1/0,high-high/low-low不表示数
6、据,可以用来做定界符。,采用0插入删除的方法来使得收发双发同步。,零比特插入/删除工作过程,流量控制,流量控制 数据链路层必须控制链路上的数据流量,保证发送与接收速度匹配,防止出现发送速度超过接收能力的现象,以免丢失数据。大多数流量控制方法的基本原理都是相同的,都需要启用反馈机制,使发方直接或是间接地获得收方指示的发送时机。在未得到允许前,禁止发出帧。如单工停等协议、滑动窗口协议等。发方的发送速率必须小于等于收方的接收速率,否则会浪费网络资源,增加网络负担。流量控制就是对发方的发送速率进行控制。基本流量控制方法基于反馈的流控制 接收方给发送方送回消息,告诉发送方它的状态 基于速率的流控制 限制
7、了发送方传输数据的速率,无需利用接收方的反馈信息,差错控制,差错控制一般方法:接收方给发送方一个反馈(响应)。比如自动重复请求(ARQ)出错情况帧(包括发送帧和响应帧)出错;帧(包括发送帧和响应帧)丢失通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。差错出现的特点:随机,连续突发(burst),差错控制方法,从差错控制的角度,对于传输的信号,利用检纠错基本原理进行编码来降低差错的发生,利用差错控制编码方法进行差错控制的常用方式主要有如下几种:自动请求重发(ARQ)方式 反馈校验方式 前向纠错(FEC)方式 混合纠错(HEC)方式,自动请求重发(ARQ)方式,发送端发
8、送出可以发现错误的码字,接收端译码若检测到错误,则主动向发送端发出请求,要求重发以便纠错。这种系统要求有反馈信道且发送端和接收端都有缓存器。,反馈校验方式,这种方式是发送端一边发送码字一边存贮发出的码字到缓冲区中。在接收端收到码字后,马上返回到发送端去与原发送码进行比较。如发现与发送码不同,就重发上一次的码字,直到发送端校验正确为止。这种方式进行差错控制的原理和设备都简单,但要求双向信道,且传输效率较低。,前向纠错(FEC)方式,发送端发出的码字是具有一定纠错能力的码字。在接收端译码后不仅可以发现错码,而且能够判断错码所在的位置并自动纠正。这种方法不需反馈信道,实时性好,传输效率较高,但纠错编
9、码方法和设备较复杂。,混合纠错(HEC)方式,实际应用中,可以结合使用ARQ方式和FEC方式。即在传输错码较少且接收端能纠正时,自动纠正错误;在错码较多、超出纠正能力但尚能检测时,采用自动请求重发方式,请求发送端重传,直到正确接收为止。该方式大大提高了通信的可靠性。,差错控制方法处理差错的两种基本策略使用纠错码:发送方在每个数据块中加入足够的冗余信息,使得接收方能够判断接收到的数据是否有错,并能纠正错误。使用检错码:发送方在每个数据块中加入足够的冗余信息,使得接收方能够判断接收到的数据是否有错,但不能判断哪里有错奇偶校验码 垂直奇(偶)校验 水平奇(偶)校验水平 垂直奇(偶)校验(方阵码)循环
10、冗余编码CRC:目前应用最广的检错码编码方法之一海明码:是一种纠错码。,纠错码,码字(codeword):一个帧包括m个数据位,r个校验位,n=m+r,则此n比特单元称为n位码字。海明距离(Hamming distance):两个码字之间不同的比特位数目。,例:0000000000 与0000011111的海明距离为5如果两个码字的海明距离为d,则需要d个单比特错就可以把一个码字转换成另一个码字;为了检查出d个错(单比特错),需要使用海明距离为 d+1 的编码;为了纠正d个错,需要使用海明距离为 2d+1 的编码;最简单的例子是奇偶校验,在数据后填加一个奇偶位(parity bit)例:使用偶
11、校验(“1”的个数为偶数)1011010110110101110110001101100010奇偶校验可以用来检查单个错误。,海明码,设计纠错码要求:m个信息位,r个校验位,纠正单比特错;利用 n=m+r,得到(m+r+1)2r 给定m,利用该式可以得出校正单比特误码的校验位数目的下界海明码码位从左边开始编号,从“1”开始;位号为2的幂的位是校验位,其余是信息位;每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数)。为看清数据位k对哪些校验位有影响,将k写成2的幂的和。例:11=1+2+8,海明码工作过程每个码字到来前,接收方计数器清零;接收方检查每个校验位k(k=1,2,4)的奇偶值是
12、否正确;若第 k 位奇偶值不对,计数器加 k;所有校验位检查完后,若计数器值为0,则码字有效;若计数器值为m,则第m位出错。若校验位1、2、8出错,则第11位变反。Fig.3-6使用海明码纠正突发错误可采用k个码字(n=m+r)组成 k n 矩阵,按列发送,接收方恢复成 k n 矩阵kr个校验位,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,使用纠错码传数据,效率低,适用于不可能重传的场合;大多数情况采用检错码加重传。循环冗余码(CRC码,多项式编码)110001,表示成多项式
13、 x5+x4+1生成多项式G(x)发方、收方事前商定;生成多项式的高位和低位必须为1生成多项式必须比传输信息对应的多项式短。CRC码基本思想校验和(checksum)加在帧尾,使带校验和的帧的多项式能被G(x)除尽;收方接收时,用G(x)去除它,若有余数,则传输出错。,检错码,循环码的编码,第一步若生成多项式G(x)的阶是r,将信息位左移r位,得xrM(x);第二步,作模2除法,求余数r(x);余数由下式获得:第三步,根据T(x)=xrM(x)+r(x),求出码字。,CRC的检错能力发送:T(x);接收:T(x)+E(x);余数(T(x)+E(x)/G(x)=0+余数(E(x)/G(x)若 余
14、数(E(x)/G(x)=0,则差错不能发现;否则,可以发现。,如果只有单比特错,即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)包括奇数个项,G(x)选(x+1)的倍数就能查出奇数个比特错;具有r个校验位的多项式能检查出所有长度 r 的突发性差错。长度为k的突发性连续差错(并不表示有k个单比特错)可表示为 xi(xk-1+1),若G(x)包括x0项
15、,且 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。,错误检测和纠正(8),四个多项式已成为国际标准CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1CRC-32硬件实现CRC校验。,CRC校验码的检错能力,CRC校验码能检查出全部单个错;CRC校验码能检查出全部离散的二位错;CRC校验码能检查出全部奇数个错;C
16、RC校验码能检查出全部长度小于或等于K位的突发错;CRC校验码能以1-(1/2)K-1的概率检查出长度为(K+1)位的突发错;如果K=16,则该CRC校验码能全部检查出小于或等于16 位的所有的突发差错,并能以1-(1/2)16-1=99.997的概率检查出长度为17位的突发错,漏检概率为0.003%;,基本的数据链路层协议,无约束单工协议(An Unrestricted Simplex Protocol)工作在理想情况,几个前提:单工传输发送方无休止工作(要发送的信息无限多)接收方无休止工作(缓冲区无限大)通信线路(信道)不损坏或丢失信息帧工作过程发送程序:取数据,构成帧,发送帧;接收程序:
17、等待,接收帧,送数据给高层Fig.3-9,单工停等协议(A Simplex Stop-and-Wait Protocol),增加约束条件:接收方不能无休止接收。解决办法:接收方每收到一个帧后,给发送方回送一个响应。工作过程发送程序:取数据,成帧,发送帧,等待响应帧;接收程序:等待,接收帧,送数据给高层,回送响应帧。Fig.3-10,有噪声信道的单工协议(A Simplex Protocol for a Noisy Channel),增加约束条件:信道(线路)有差错,信息帧可能损坏或丢失。解决办法:出错重传。带来的问题:什么时候重传 定时响应帧损坏怎么办(重复帧)发送帧头中放入序号为了使帧头精简
18、,序号取多少位 1位发方在发下一个帧之前等待一个肯定确认的协议叫做PAR(Positive Acknowledgement with Retransmission)或ARQ(Automatic Repeat reQuest),自动重复请求(ARQ),自动重复请求(ARQ)是应用最广泛的一种差错控制技术,包括:无错接收的PDU的肯定确认、对未确认PDU的自动重传和丢弃。接收方监测到数据中存在差错:发否认帧,立即启动重发;不理会,发送方超时重发,停止等待式ARQ,协议简单 效率低效率是多少?滑动窗口大小发送窗口大小SWS=1 接收窗口大小RWS=1,注意协议的漏洞由于确认帧中没有序号,超时时间不能
19、太短,否则协议失败。因此假设协议的发送和接收严格交替进行。Fig.3-11的实现是正确的,确认帧有序号,发送,接收,0,0,1,ACK,ACK,滑动窗口协议,单工 全双工捎带/载答(piggybacking):暂时延迟待发确认,以便附加在下一个待发数据帧的技术。优点:充分利用信道带宽,减少帧的数目意味着减少“帧到达”中断;带来的问题:复杂。本节的三个协议统称滑动窗口协议,都能在实际(非理想)环境下正常工作,区别仅在于效率、复杂性和对缓冲区的要求。,滑动窗口协议(2),滑动窗口协议(Sliding Window Protocol)工作原理:发送的信息帧都有一个序号,从0到某个最大值,0 2n-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据链

链接地址:https://www.desk33.com/p-740679.html