05数据链路层的功能与服务

1、课程负责人：甘课程负责人：甘卫民卫民链路与数据链路链路与数据链路数据链路层的功能与服务数据链路层的功能与服务(1) (1) 封装成帧封装成帧( (透明传输透明传输) )(2) (2) 可靠性的保障可靠性的保障(3) (3) 差错控制差错控制(4) (4) 流量控制流量控制 (5) (5) 链路管理链路管理习题习题重点：重点：了解数据链路层信道的类型；数据在链路层的流了解数据链路层信道的类型；数据在链路层的流动；动；熟悉数据链路层的功能与服务；熟悉数据链路层的功能与服务；难点：难点：掌握封装帧的原理、差错控制编码掌握封装帧的原理、差错控制编码( (奇偶校验码、奇偶校验码、crc)crc)；ip

2、数据报1010 0110帧取出数据链路层网络层链路结点 a结点 b物理层数据链路层结点 a结点 b帧发送帧接收数据链路ip 数据报1010 0110帧装入n常常在两个对等的数据链路层之间画出一个数字管道（数据链路），而在这条数字管道上传输的数据单位是帧。讨论讨论1 1：数据链路层中基本概念：数据链路层中基本概念5讨论讨论1 1：数据链路层中基本概念（续）：数据链路层中基本概念（续）n链路链路(link) 一条无源的点到点的物理线路段，中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分1.1 1.1 链路与数据链路链路与数据链路n数据链路数据链路(data link) 除了物理线路

3、外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。 数据链路=链路+协议实现 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。 一般的适配器都包括了数据链路层和物理层这两层的功能。 6数据链路层的简单模型数据链路层的简单模型局域网广域网主机 h1主机 h2路由器 r1路由器 r2路由器 r3电话网局域网主机 h1 向 h2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层r1r2r3h1h2从层次上来看数据的流动71.2 1.2 数据链路层的服务数据链路

4、层的服务n数据链路层实现在同一链路两端相邻设备之间帧的传输，为网络层提供数据包的搬运服务n要解决在易受到干扰的物理层的原始比特流传输的服务基础上，向网络层提供可靠的、无差错的、透明的、面向帧的传输服务。v点对点信道点对点信道 这种信道使用一对一的点对点通这种信道使用一对一的点对点通信方式。信方式。点对点信道abp 信道主要有以下两种类型：广播信道cbedan广播信道广播信道 这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送。不同的信道，服务使用的控制实现方法有所差异1.2 1.2 数据链路层的服务数据链路层的服

5、务( (续续) )9n要解决的几个基本问题要解决的几个基本问题 ？(1) (1) 封装成帧封装成帧( (透明传输透明传输) )(2) (2) 可靠性的保障可靠性的保障(3) (3) 差错控制差错控制(4) (4) 流量控制流量控制(5) (5) 链路管理链路管理 1.2 1.2 数据链路层的服务数据链路层的服务( (续续) )(1) 封装成帧封装成帧(透明传输透明传输)v封装成帧封装成帧(framing)(framing)就是在一段数据的前后分别添就是在一段数据的前后分别添加首部和尾部，构成了一个帧。确定帧的界限。加首部和尾部，构成了一个帧。确定帧的界限。v首部和尾部的一个重要作用就是进行首部

6、和尾部的一个重要作用就是进行帧定界帧定界。 ip 数据报 mtu数据链路层的帧长开始发送帧结束帧首部帧的数据部分帧尾部帧开始11四种成帧方法四种成帧方法: :(1) 封装成帧(续)n字节计数法(character count) n字符填充法(flag bytes with byte stuffing)n比特填充法(starting and ending flags, with bit stuffing)n违例编码法(physical layer coding violations)字符填充法用特殊的控制字符进行帧定界，以解决当传输错误时，重新接收方重新和发送方同步，找到帧的边界。n成帧原理帧开

7、始符（00000001）帧结束符（00000100）soh装在帧中的数据部分eot帧发送在前13待解决的问题：如何进行透明传输？待解决的问题：如何进行透明传输？soheot出现了“eot”被接收端当作无效帧而丢弃被接收端误认为是一个帧数据部分eot完整的帧发送在前n问题分析字符填充法(续)14解决透明传输问题解决透明传输问题v发送端的数据链路层在数据中出现控制字符发送端的数据链路层在数据中出现控制字符“sohsoh”或或“eoteot”的前面插入一个的前面插入一个转义字符转义字符“escesc”( (其十六进制其十六进制编码是编码是 1b1b，即，即00010000)00010000)。v接收

8、端的数据链路层在将数据送往网络层之前删除插入接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。的转义字符。v如果转义字符也出现数据当中，那么应在转义字符前面如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。时，就删除其中前面的一个。 解决方法：转义字符填充法sohsoheotsohescesc eotesc sohesc escesc soh原始数据eoteot经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符用字符填充法解决透明传输的

9、问题用字符填充法解决透明传输的问题 soh16n问题分析(续)优点：可以解决当错误发生时，重新同步帧的边界缺点：依赖于字符的编码方式(ascii)不是所有字符都采用ascii编码方式，如：unicode采用16位编码字符填充法(续)比特填充法(1) 封装成帧(续)n成帧原理通过在帧头和帧尾分别添加具有特殊比特流模式（01111110）的标识符，来标示帧的定界。帧头数据载荷信息帧尾0111111001111110原始数据帧的定界符帧的定界符发送在前18待解决的问题：如何进行透明传输？待解决的问题：如何进行透明传输？01111110出现了标识符被接收端误认为是一个帧数据部分完整的帧发送在前n问题分

10、析比特填充法(续)0111111001111110n发送端，只要在数据部分发现有 5 个连续 1，则立即填入一个 0。n接收端对帧中的比特流进行扫描。每当发现 5 个连续1时，就把这 5 个连续 1 后的一个 0 删除。解决透明传输问题解决方法：零比特填充法解决方法：零比特填充法原始数据部分a01111110b填充后的数据部分a011111010ba01111100ba011111000ba01111101ba011111001b20n问题分析(续)比特填充法优点：适应于任何数据形式的比特流的传输适应于任意编码方式的字符传输比特填充法应用举例： hdlc 、ppp比特填充法(续)n要解决的几个

11、基本问题要解决的几个基本问题 ？(1) (1) 封装成帧封装成帧( (透明传输透明传输) )(2) (2) 可靠性的保障可靠性的保障(3) (3) 差错控制差错控制(4) (4) 流量控制流量控制 (5) (5) 链路管理链路管理1.2 数据链路层的服务(续)22(2) 可靠性的保障ip 数据报1010 0110帧取出数据链路层网络层链路结点 a结点 b物理层ip 数据报1010 0110帧装入数据链路层要将网络层的数据报封装在帧中，实现透明传输。传输是否可靠？是否需要可靠保障？如何保障？23(2) 可靠性的保障(续)n三种类型的传输可靠性服务n不同的协议和系统中对数据链路层的传输可靠性服务的

12、定义是不同点。无确认无连接的服务无确认无连接的服务有确认无连接的服务有确认无连接的服务有确认面向连接的服务有确认面向连接的服务24无确认无连接的服务1. 源端和目的端的数据链路层在传输帧之前不需要建立逻辑上连接。（无连接）2. 每个帧在数据链路层协议的控制下从源端到目的端进行独立传输。（独立传输）3. 目的端收到帧后，不需要通过反馈信息告诉源端，该帧是否正确接收 （无确认）4. 帧在传输时如果因为噪音干扰而丢失，没有任何机制来检测帧丢失，也没有任何机制实施帧的重新传输。 （无重传）n 基本思想适应于质量较好、差错率降低的信道传输，将少许差错情况的检测交给高层协议实现。适应于实时性要求较高的场合

13、。如：音频的传输n 适应场合25有确认无连接的服务1. 源端和目的端的数据链路层在传输帧之前不需要建立逻辑上连接。（无连接）2. 每个帧在数据链路层协议的控制下从源端到目的端进行独立传输。（独立传输）3. 目的端收到帧后，需要通过反馈确认信息告诉源端数据链路层，该帧正确接收。（有确认）4. 发送方对每个传输的帧进行编码 （帧编号）5. 帧在传输时丢失，源端可以通过超时机制，重新传输丢失的帧。（超时重传）n 基本思想基本思想l 适应于信道质量较差的不可靠信道 如：无线信道n 适应场合适应场合26有确认面向连接的服务源端和目的端的数据链路层在传输帧之前需要首先建立逻辑上连接。（有连接）每个帧在数据

14、链路层协议的控制下，沿着建立好的链路，从源端到目的端进行独立传输。（独立传输）发送方对每个传输的帧进行编号，目的端收到帧后，需要通过反馈确认信息告诉源端数据链路层，相应编号的帧被正确接收；所有传输中的帧要求按序到达目的端，且只被正确接收一次.（有确认，帧编号）帧在传输时丢失，源端可以通过超时机制，重新传输丢失的帧。（超时重传）数据传输完毕，需要释放逻辑连接。（释放连接）n 基本思想基本思想适应于传输要求可靠性较高的场合n 适应场合适应场合27n要解决的几个基本问题要解决的几个基本问题 ？(1) (1) 封装成帧封装成帧( (透明传输透明传输) )(2) (2) 可靠性的保障可靠性的保障(3)

15、(3) 差错控制差错控制(4) (4) 流量控制流量控制 (5) (5) 链路管理链路管理1.2 数据链路层的服务(续)28n 误比特率与信噪比有很大的关系。n 在一段时间内，传输错误的比特占所传输比特 总数的比率称为误比特率 ber 。误比特率=传输错误的比特位总数实际传输的比特位总数n 因为物理层存在噪音干扰（随机噪音和突发噪音），在传输中的比特位可能会产生差错：1 可能会变成 0 而 0 也可能变成 1。(3) (3) 差错控制差错控制29n 为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错控制措施。(3)差错控制(续)检错纠错差错控制措施差错控制的基本思想n 发送方按

16、照一定算法为每一个传输的帧增加一定的冗余位（差错控制码、校验和字段、帧检验序列）n 接收方按照相同算法进行检查（重新计算该冗余位，并判断计算结果和实际接收的冗余位是否相等，相等表示检查结果正确，不相等表示检查结果错误）30(3)差错控制(续)差错检测(检错码)差错纠正(纠错码)接收，反馈确认信息检查正确检查错误帧丢失差错控制的基本思想差错控制的基本思想(续续)进行纠正，接收超时重传接收，反馈确认信息检查正确检查错误帧丢失丢弃，并反馈否定帧丢弃，超时重传超时重传差错检测(检错码)差错纠正(纠错码)差错控制的基本思想差错控制的基本思想(续续)(3)差错控制(续)应用于高可靠性的信道传输，如：光纤传

17、输应用于不可靠性的信道传输，如：无线传输arq,自动请求重传(automatic request for repeat)fec,前向纠错(forward error correction)32(3)差错控制(续)码字码字(codeword)的概念的概念k位r位n位码字（ n = k + r ）数据位冗余（校验）位1 0 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1 11 0 1 0 1编码效率:r=knkk+r=33常用的简单差错控制编码n奇偶校验码(parity checking code)n循环冗余码(crc)(3)差错控制(续)n正反码n海明码34通过增

18、加冗余位来使得码字中”1”的个数保持奇数或偶数的编码方法。垂直奇/偶校验码水平奇/偶校验码水平垂直奇/偶校验码奇偶校验码n 分类:n 思想:奇偶校验码35垂直奇/偶校验码n 思想：将整个发送的信息块分为定长为p位（一般p=7）的若干段（设为q段）,每段后面按“1”的个数为奇或偶数的规律加上一位奇偶位(冗余位)。36偶校验奇校验37例如例如: :要发送的信息是要发送的信息是1100101 0100011 1011011 01010101100101 0100011 1011011 010101011001010100011101101101010100 偶校验11 1 +采用偶校验方式,实际发送

19、:11001010 01000111 10110111 01010101发送顺序偶校验思想:添加1位使得每列中”1”的个数为偶数个38例如例如: :要发送的信息是要发送的信息是1100101 0100011 1011011 01010101100101 0100011 1011011 0101010采用奇校验方式,实际发送:11001011 01000110 10110110 01010100奇校验1 00 0 1100101010001110110110101010+发送顺序奇校验思想:添加1位使得每列中”1”的个数为奇数个39垂直奇垂直奇/ /偶校验码的特点偶校验码的特点: : 编码效率

20、r=p/(p+1) 只能检测每列奇数个错误,不能检测每列偶数个错误,检测效率50% 发送方可以边发送边生成冗余位,接收方可以边接收边检测40水平奇/偶校验码思想:添加1位使得每行中”1”的个数为奇/偶数个41例如例如: :要发送的信息是要发送的信息是1100101 0100011 1011011 01010101100101 0100011 1011011 01010101100101010001110110110101010+采用偶校验方式,实际发送:1100101 0100011 1011011 0101010 0110111发送顺序偶校验011011142水平奇水平奇/ /偶校验码的特点

21、偶校验码的特点: : 编码效率 r=q/(q+1) 只能检测每行奇数个错误,不能检测每行偶数个错误,检测效率50% 可以检测出突发长度p的错误,漏检率小于垂直奇/偶校验方式 发送方和接收方需要使用记忆寄存器43水平垂直奇/偶校验码思想:一般采用偶教验，同时在每行和每列上添加1位使得每行和每列中”1”的个数为偶数个44例如例如: :要发送的信息是要发送的信息是1100101 0100011 1011011 01010101100101 0100011 1011011 01010101100101010001110110110101010偶采用偶校验方式,实际发送:11001010 0100011

22、1 10110111 01010101 01101111发送顺序偶0 1 1 11011011145水平奇水平奇/ /偶校验码的特点偶校验码的特点: :编码效率 r=pq/(p+1)(q+1)只能检测每行和每列奇数个错误能检测出所有3位和3位以下的错误能检测出大多数偶数位错误可以检测出突发长度p+1的错误具有1位纠错能力,但也可能误纠发送方和接收方需要使用记忆寄存器46 任意一个由二进制位串组成的码串都可以唯一的和一个系数仅为0和1的多项式一一对应。n 算法理论思想基础假设二进制串： bm bm-1 bm-2 b2 b1 b0, 其中bi0，1m(x)=bmxm+bm-1xm-1+b2x2+b

23、1x+b0循环冗余码(crc)47例例1 1：m(x)=x8+x7+x4+x2+1110010101例例2 2：m(x)=x8+x6+x5+x4+x2+x10111011048 选择一个生成多项式g(x)g(x)=grxr+gr-1xr-1+g2x2+g1 x+g0 其中：gi0，1 进行多项式除法运算xrm(x)g(x)商多项式余多项式q(x)r(x)其中r(x)=ar-1xr-1+ ar-2xr-2+ +a1x+a0ai0，1循环冗余检验的原理循环冗余检验的原理 v 在数据链路层传送的帧中，广泛使用了循环冗余检验 crc 的检错技术。v 在发送端，先把数据划分为组。假定每组 k 个比特。

24、v 假设待传送的一组数据 m = 101001（现在 k = 6）。我们在 m 的后面再添加供差错检测用的 n 位冗余码一起发送。 冗余码的计算冗余码的计算 v 用二进制的模 2 运算进行 2n 乘 m 的运算，这相当于在 m 后面添加 n 个 0。v 得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 p，得出商是 q 而余数是 r，余数 r 比除数 p 少1 位，即 r 是 n 位。 冗余码的计算举例冗余码的计算举例 v现在 k = 6, m = 101001。v设 n = 3, 除数 p = 1101，v被除数是 2nm = 101001000。 v模 2 运

25、算的结果是：商商 q = 110101， 余数余数 r = 001。v把余数 r 作为冗余码冗余码添加在数据 m 的后面发送出去。发送的数据是：2nm + r 即：101001001，共 (k + n) 位。 循环冗余检验的原理说明循环冗余检验的原理说明 110101 q (商) p (除数) 1101 101001000 2nm (被除数) 1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 r (余数)，作为 fcs 53 crc练习练习1.假设发送方待发的信息比特为:1001101011,选择的生成多项式为g(x)=x4+x2+x+1,请问发送方实际发送的数据是什么?crc码?练习2.假设接收方接到如下比特流为:100011001011,校验时选择的生成多项式为g(x)=x5+x3+x+1,请问接收到的比特流是否正确?答案:10011010111111答案:有误,