《第6章数据链路层概要》由会员分享,可在线阅读,更多相关《第6章数据链路层概要(71页珍藏版)》请在金锄头文库上搜索。
1、1,第6章 数据链路层,6.1 数据链路层的基本概念 6.2 差错控制 6.3 流量控制 6.4 数据链路规程示例,2,第一节 数据链路层的基本概念,6.1.1 差错产生与差错控制 6.1.2 数据链路控制 6.1.3 数据链路层向网络层提供的服务,3,6.1.1 差错产生与差错控制,传输线路是由传输介质与设备组成的。原始的物理传输线路是指没有采用高层差错控制的基本的物理传输介质与设备。 当数据从信源出发,经过通信信道时,由于通信信道总是有一定的噪声存在,在到达信宿时,接收信号是数据信号与噪声的叠加。在接收端,接收电路在取样时判断信号电平。如果噪声对信号叠加的结果在电平判决时出现错误,就会引起
2、传输数据的错误。,4,通信信道的噪声分为两类: 热噪声和冲击噪声,热噪声是由传输介质导体的电子热运动产生的。热噪声的特点是:时刻存在,幅度较小,强度与频率无关,但频谱很宽,是一类随机的噪声。由热噪声引起的差错是一类随机差错。 冲击噪声是由外界电磁干扰引起的。与热噪声相比,冲击噪声幅度较大,是引起传输差错的主要原因。冲击噪声持续时间与数据传输中每比特的发送时间(T)相比,可能较长,因而冲击噪声引起的相邻多个数据位出错呈突发性。冲击噪声引起的传输差错为突发差错。引起突发差错的位长称为突发长度。在通信过程中产生的传输差错,是由随机差错与突发差错共同构成的。,5,误码率,描述物理传输线路上传输数据信号
3、出现差错多少的参数为误码率。 误码率是指二进制比特在数据传输过程中被传错的概率,它在数值上近似等于被传错的比特数和传输的二进制比特总数的比值。在实际的物理线路的传输过程中,人们需要进行大量测试,求出各种信道的平均误码率,或者给出某些特殊情况下的平均误码率。 因为计算机网络的平均误码率要求低于10-6,所以普通电话线路如不采取差错控制技术,是不能满足计算机网络的通信要求的。,6,6.1.2 数据链路控制,数据链路控制的主要功能有以下几点: (1)链路管理 (2)帧同步 (3)流量控制 (4)差错控制 (5)透明传输 (6)寻址,7,6.1.3 数据链路层向网络层提供的服务,面向连接确认服务(ac
4、knowledged connection-oriented service); 无连接确认服务(acknowledged connectionless service); 无连接不确认服务(unacknowledged connectionless service)。,8,第二节:差错控制,6.2.1 差错控制方法 6.2.2 奇偶校验法 6.2.3 循环冗余校验(Cyclic Redundancy Cheek,CRC) 6.2.4 海明码,9,6.2.1 差错控制方法,差错控制概念: 所谓差错控制是指在进行数据通信时,如何发现所传送的信息是否有错,以及发现错误时如何处理。,10,自动请求重
5、发(ARQ): 发送端发送能检测差错的抗干扰码,如奇偶校验码、循环冗余校验码(CRC)等。接收端检验传输中有无差错产生,并把检验结果通过反馈信道送回到发送端,发送端根据反馈消息把接收端认为有错的消息再次发送,直到接收端判定无错为止。 特点: 检错码所需加入的冗余码元较少; 只能检测出错码是在哪些接收码之中,但不能确定错码的准确位置; 这种方式只能用在双向通信系统中; 为了重发,必须有存储器; 在信道条件恶劣时需多次重发,接收端收到正确信息要经过较长的延时时间,因此这种方式在数据的实时性要求很高的场合就不能用。,11,向前纠错(FEC) 在发送端发送能够纠错的抗干扰编码,如海明码。接收端收到这些
6、码后,通过纠错译码器,不仅能发现错误,而且能自动地纠正传输中的错误。 特点: 接收端能够准确地确定错码的位置, 不存在重发延时,所以实时性强。 适用于单工信道且不可能要求重发的场合。 缺点是附加信息量大、传输效率低、解码设备较复杂。,12,奇偶校验法,校验方法: 在奇偶校验时,要在每一个字符上增加一个附加位,使该字符中“1”的个数为奇数或偶数。如在奇校验时,如果该字符位串中“1”的个数为奇数,则增加的附加位置“0”,否则置“1”,使该字符位串中“1”的个数为奇数。偶校验的附加位要保证字符位串中的“1”为偶数个。 奇偶校验并不是一种十分安全可靠的检错方法,如果有偶数个数据位在传输中同时出错,接收
7、端将无法检测出差错,所以其检错概率为50。 通常偶校验常用于异步传输或低速传输,而奇校验常用于同步传输。,13,循环冗余校验,校验方法: 将所传输的数据除以一个预先设定的除数,所得的余数作为冗余比特,附加在要发送数据的末尾,被称为循环冗余校验码(CRC码),这样,实际传输的数据就能够被预先设定的除数整除。当整个数据传送到接收方后,接收方就利用同一个除数去除接收到的数据,如果余数为0,即表明数据传输正确,否则即意味着数据传输出现了差错。,14,循环冗余校验,计算方法: 在数据的末尾加上n个0,n等于除数的位数减1。 采用二进制除法规则,计算加长的数据除以预先设定的除数,得到的余数即为循环冗余校验
8、码。 将循环冗余校验码替换数据末尾的n个0,即得出整个传输的数据。,15,例如,如果除数为10011,写出数据1011010的循环冗余码,例如,如果除数为10011,写出数据1011010的循环冗余码 因为除数为10011,所以 N=4, 1011010 0000,16,循环冗余校验,CRC校验码为相除的余数, 即 1111 实际发送的比特串则为:10110101111,17,循环冗余校验,实际上,循环冗余校验的数学基础是多项式除法。从数学角度看,任何数都可以表示成多项式的形式,因此二进制序列也可以表示成多项式形式。例如,1011010 就可表示成: 126 + 025 + 124 + 123
9、 + 022 + 121 + 020 即 26+24+23+2 基于上述理论,所传输的数据即可表示成一个信息多项式m(x),而除数多项式即被称为生成多项式g(x)。循环冗余校验码就是扩充n个0后的m(x)除以g(x)的余数。,18,循环冗余校验,CRC标准: CRC-12 = x12+x11+x3+x2+1 CRC-16 = x16+x15+x2+1 CRC-ITU-T = x16+x12+x5+1 CRC-32 = x32+x25+x23+x22+x16+x12+X11+x10+x8+x7+x5+x4+x2+x+1,19,理论上,自动纠正每一个二进制代码的传输差错是可以做到的。但纠错码比检错
10、码复杂得多,而且需要更多的冗余位。用于多位或突发差错纠错的位数太大的,以致大部分情况下,将使编码效率低到不可接受的程度。为此,大部分纠错码只限于处理1位、2位或3位差错。 在数据通信中,最常用的纠错码是所谓“海明码” (Hamming Code),是贝尔实验室的科学家R.W.Hamming 于1950年提出的,主要用来纠正1位差错。,4.海明码,20,1位差错的纠错 Single-bit Error Correction,奇偶校验可以检测出1位差错的情况,方法是加上一个冗余的奇校验位或偶校验位。纠错则需确定其中哪位有差错。 如果要确定一个ASCII字符(7位)中的某位差错,此时需要区别8种情况
11、:没差错,第1位错,第2位错,第7位错。于是,需要3个冗余位来表示8种不同的状态(000 -111)。 实际上,3位冗余是不够的。因为,冗余位本身也可能出现差错!,21,纠错码 Error Correction,22,冗余位,如何计算m位数据纠错时所需的冗余位数 r 呢? 此时数据传输的总位数是m+r,且要求 r必须能够至少表示 m+r+1 种状态。其中,一种状态表示无差错,m+r 种状态分别表示在 m+r 位每个位置上发生的差错。 由于r 位二进制数可以表示2r种不同的状态,所以,2r必须大于或等于 m+r+1。 2 r m+r+1 如果m=7(ASCII代码),则能满足上式的最小 r 值是
12、4。因为: 24 7+4+1,23,数据位数 m 与冗余位数 r 的关系,下表为一些可能的 m 值及其对应的 r 值。,24,纠错原理,冗余位的定位 海明码可用于任何长度的数据块,并利用了上面讨论的数据位数和冗余位数的关系。例如,一个7位ASCII码要求4个冗余位,它们可以附加在数据位的后面,亦可散布在数据位之中。下图中,各冗余位处于第1、2、4、8位(2的n次方处),分别用r1,r2,r4,r8表示。,25,确定冗余位的位置,在海明码中,每一个r位都是一组数据位的奇偶校验码。用于计算7数据位4个r值(奇偶校验码)的方案是: r1 : 第 1,3,5,7,9,11 位 r2 : 第 2,3,6
13、,7,10,11 位 r3 : 第 4,5,6,7 位 r4 : 第 8,9,10,11 位,26,r1和r2值的计算,27,r4和r8值的计算,28,纠错码的计算,为了搞清楚这种技术后面的窍门,不妨看看每一数位的位置号(用二进制表示)。r1位使用的是所有位置号右侧为1开头的数位。r2使用的是所有位置号第2位为1的数位,以此类推。,29,示例:各r位值的计算,假设使用偶校验。,30,检错与纠错,如果数据发送后,接收端收到的海明码为: 10010100101, 请问接收是否正确?如不正确,如何纠错?,31,假设上述数据发送后,接收端收到的:10010100101 (第7位差错)。 此时接收端取出
14、接收结果,并使用与发送端相同的方法计算出一组新的奇偶校验码。然后将这些奇偶校验码按r的顺序(r8,r4,r2,r1)组成一个二进制数。本例中,组成的二进制数是0111(十进制数7),这就是准确的差错位置。 一旦找出差错位,接收端即可将该位的值反转,以纠正差错。,检错与纠错,1,32,海明码,基本思想: 在数据中加入足够多的冗余位(满足2r=m+r+1),将这些冗余位分别放置在2的幂的位置上,每个冗余位都是一组比特的奇偶校验位。,33,海明码,例如所传输的数据为 1011010,构成海明码的过程如下: (1)对于7位的数据,24 7+4+1,即取r=4个冗余位。海明码共11位。 (2)将这4个比
15、特,分别放置在第1,2,4,8位上,记为 r1,r2,r4,r8。 (3) r1为位置的二进制表示的最低位是1的各位的校验,r2为位置的二进制表示的次低位是1的各位的校验,r4 、r8依此类推。即:r1为第1,3,5,7,9,11位的偶校验。r2为第2,3,6,7,10,11位的偶校验。r4为第4,5,6,7位的偶校验。r8为第8,9,10,11位的偶校验。即:,34,海明码,数据: 1 0 1 1 0 1 0 d7 d6 d5 d4 d3 d2 d1 位置: 11 10 9 8 7 6 5 4 3 2 1 海明码:1 0 1 0 1 0 1 0 0 0 0 d7 d6 d5 r8 d4 d3
16、 d2 r4 d1 r2 r1,35,第三节 流量控制,6.6.1 非受限协议 6.6.2 停等协议 6.6.3 滑动窗口协议,36,6.6.1 非受限协议,非受限协议是最简单的流量控制协议,其基本思路是:发送方只要有信息要发送,就可以不受限制地发送数据帧;并假定接收方有足够大的缓存区,可以缓存发送方发送的数据帧,或假定接收方的处理速度足够快,快到可以完全来得及处理发送方发送的数据。 非受限协议不检测帧是否损坏、丢失,不控制发送数量;即没有任何限制。这种协议适用于高质量的网络传输信道,几乎没有错误发生的情况;或者传输信息不重要,即使发生个别信息的丢失也没有太大影响阶情况。就如同我们生活中邮寄平信,一般都是不重要的内容,并且信任邮局能够安全将信送达。,37,6.6.2停等协议,停等协议的基本思想是:发送方每发送完一个数据帧,都要等待接收方的确认帧到来后,再发送下一帧:接收方每接收到一个数据帧后,都要向发送方发送一个正确接收到数据帧的确认帧