第 5 讲 数据链路层(1) 1/31.

Presentation on theme: "第 5 讲 数据链路层(1) 1/31."— Presentation transcript:

1 第 5 讲 数据链路层(1) 1/31

2 知识回顾 物理层的功能 数据通信模型 信道复用技术 数字传输系统 宽带接入技术 2/31

3 本讲内容及教学目标 理解数据链路层的功能。 掌握帧、链路等相关概念。 掌握帧定界的方法。 理解数据链路层的三个基本问题。
掌握差错检测－CRC的计算方法。 理解透明传输问题。 3/31

4 数据链路层的服务 数据链路层最基本的服务是将源计算机网络层来的数据可靠的传输到相邻节点的目标计算机的网络层。它为网络层提供以下服务：
无确认、无连接的服务 源端可以不需要建立连接就向目的端发送独立的数据帧，而目的端也不需要对收到的帧进行确认。以太网采用此服务。 有确认、无连接的服务 源端可以不需要建立连接就向目的端发送独立的数据帧，但目的端需要对收到的帧进行确认。 面向连接的服务 源端与目的端在通信前要先建立连接，然后在此连接上互相传输数据帧，每一个帧都被编号，数据链路层保证传送的帧被对方收到，且只收到一次，双方通信完毕后拆除连接。电话网络采用。 4/31

5 数据链路层的主要功能 为达到上述目的，数据链路层必须具备一系列相应的功能，主要有：如何将数据组合成数据块；如何控制帧在物理信道上的传输，包括如何处理传输差错，如何调节发送速率以使之与接收方相匹配；在两个网路实体之间提供数据链路通路的建立、维持和释放管理。 具体如下： 链路管理 帧定界 流量控制 差错控制 将数据和控制信息区分开 透明传输 寻址 5/31

6 数据链路层的基本概念 在数据链路层中将这种数据块称为帧，帧是数据链路层的传送单位。
链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分。 数据链路(data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。 一般的适配器都包括了数据链路层和物理层这两层的功能。 6/31

7 Functions of the Data Link Layer (2)
Relationship between packets and frames. 7/31

8 Services Provided to Network Layer
(a) Virtual communication. (b) Actual communication. 8/31

9 数据链路层 数据链路层使用的信道主要有以下两种类型： 点对点信道。这种信道使用一对一的点对点通信方式。
广播信道。这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发 9/31

10 数据链路层的简单模型 主机 H1 向 H2 发送数据 从层次上来看数据的流动 路由器 R1 路由器 R3 主机 H1 路由器 R2
电话网 局域网 广域网 局域网 链路层 应用层 运输层 网络层 物理层 R1 R2 R3 H1 H2 从层次上来看数据的流动 10/31

11 数据链路层的简单模型——cont. 主机 H1 向 H2 发送数据 仅从数据链路层观察帧的流动 路由器 R1 路由器 R3 主机 H1
电话网 局域网 广域网 局域网 仅从数据链路层观察帧的流动 H1 H2 应用层 应用层 R1 R2 R3 运输层 运输层 网络层 网络层 网络层 网络层 网络层 链路层 链路层 链路层 链路层 链路层 物理层 物理层 物理层 物理层 物理层 11/31

12 数据链路层 数据链路层像个数字管道。 常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。
早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。 结点 帧 12/31

13 成帧（帧同步） 为了向网络层提供服务，数据链路层必须使用物理层提供的服务。
物理层, 是以比特流进行传输的，这种比特流并不保证在数据传输过程中没有错误，接收到的位数量可能少于、等于或者多于发送的位数量。而且它们还可能有不同的值，这时数据链路层为了能实现数据有效的差错控制，就采用了一种“帧”的数据块进行传输。分段传输。 采用帧格式传输，就必须有相应的帧同步技术，这就是数据链路层的“成帧”（也称为“帧同步”）功能。 13/31

14 成帧（帧同步）（续） 采用帧传输方式的好处是
在发现有数据传送错误时，只需将有差错的帧再次传送，而不需要将全部数据的比特流进行重传，这就在传送效率上将大大提高。 但同时也带来了两方面的问题：（1）如何识别帧的开始与结束；（2）在夹杂着重传的数据帧中，接收方在接收到重传的数据帧时是识别成新的数据帧，还是识别成已传帧的重传帧呢？这就要靠数据链路层的各种“帧同步”技术来识别了。 “帧同步”技术既可使接收方能从以上并不是完全有序的比特流中准确地区分出每一帧的开始和结束，同时还可识别重传帧。 14/31

15 数据链路层传送的是帧 结点 A 结点 B 网络层 IP 数据报 IP 数据报 装入 取出 数据 链路层 帧 帧 物理层 链路 (a)
1010… …0110 1010… …0110 链路 (a) 结点 A 结点 B 发送 接收 数据 链路层 帧 帧 链路 (b) 15/31

16 封装成帧 封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。
首部和尾部的一个重要作用就是进行帧定界。 IP 数据报 帧开始 帧结束 帧首部 帧的数据部分 帧尾部 开始 发送  MTU 数据链路层的帧长 16/31

17 用控制字符进行帧定界的方法举例 帧开始符 帧结束符 SOH 装在帧中的数据部分 EOT 帧 发送在前 17/31

18 透明传输方法 出现了“EOT” 完整的帧 发送 在前 数据部分 被接收端 误认为是一个帧 被接收端当作无效帧而丢弃 SOH EOT EOT
18/31

19 解决透明传输问题 发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。
字节填充(byte stuffing)或字符填充(character stuffing)——接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。 如果转义字符也出现在数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。 “透明传输”是指可以让无论是哪种比特组合的数据，都可以在数据链路上进行有效传输。这就需要在所传数据中的比特组合恰巧与某一个控制信息完全一样时，能采取相应的技术措施，使接收方不会将这样的数据误认为是某种控制信息。以保证数据链路层的传输是透明的。 19/31

20 用字节填充法解决透明传输的问题 帧开始符 帧结束符 原始数据 字节填充 字节填充 字节填充 字节填充 经过字节填充后发送的数据 发送 在前
SOH EOT SOH ESC SOH EOT 字节填充 字节填充 字节填充 字节填充 SOH ESC EOT ESC SOH ESC ESC ESC SOH EOT 经过字节填充后发送的数据 发送 在前 20/31

21 差错检测 在传输过程中可能会产生比特差错：1 可能会变成 0 而 0 也可能变成 1。
在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。 误码率与信噪比有很大的关系。 为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。 在数据通信过程可能会因物理链路性能和网络通信环境等因素，难免会出现一些传送错误，但为了确保数据通信的准确，又必须使得这些错误发生的机率尽可能低。这一功能也是在数据链路层实现的，就是它的“差错控制”功能。 21/31

22 差错检测与校正 信号在任何信道上传输都存在着传输差错，这些差错由多种物理现象引起，解决差错问题的方法有两种：
一种是在要发送的数据中加入一定的冗余位，使接收方能知道数据是否出错，但不知道是哪里出错，这种编码方法叫差错检测码，或简称检错码。如CRC 另一种是在要发送的数据中加入足够多的冗余位，使接收方能纠正出错的位，这种编码方法叫差错校正码，或简称纠错码。如海明码。 22/31

23 纠错码－海明码 定义：一帧由m个数据位（即报文）和r个冗余位（即校验位）组成，设总长度为n（n=m+r)，此长度为n的单元常称为n位码字。
定义：两个码字不同的位的数目称为海明距离 例如， 与 它们的海明距离为3。 对于n位码字的集合，只有2m个码字是有效的，在任意两个有效码字间找出具有最小海明距离的两个码字，该海明距离便定义为全部码字的海明距离。 一种编码的检错和纠错能力取决于编码后码字的海明距离的大小。 为了检测出d个比特的错，需要使用距离为d+1的编码。 例如：数据后加奇偶校验位，编码后的海明距离为2，能检测1比特错。 为了纠正d个比特的错，必须用距离为2d+1的编码。 例如有4个有效码字：它们是 ， ， ， ，海明距离为5，能纠正2比特错。 23/31

24 纠正单比特错的校验位下界 设计一种编码，它有m个信息位和r个校验位，当r满足什么条件时，能纠正所有单比特错？
对2m个有效码字的任何一个而言，有n个与该码字距离为1的无效码字，所以2m个有效码字每一个都对应有n+1个各不相同的位图，n位码字的总的位图是2n个。 （n+1）2m<=2n，n=m+r代入 （m+r+1）2m<=2 m+r 2r>=n+1 纠正单比特误码的校验位下界 24/31

25 海明编码 海明在1950年提出一种编码来纠正单比特错的编码。
该编码是将码字内的位从左到右依次编号，编号为2的幂的位是校验位（如第1，2，4，8…），其余为信息位。 每个校验位的取值应使得包括自己在内的一些集合服从规定的奇偶性。 集合的选取如下： 对编号为K的信息位来说，K可以分解成2的幂的和，如编号为11，11=1+2+8，即第11位由1，2，8校验位校验，它同时属于1，2，8所在的集合。 25/31

26 改进的奇偶校验 对数据位组成一个L位宽，K位高的长方形距阵来发送，然后对每一列单独计算奇偶位，并附在最后一行作为冗余位。 L列 检错率：
1.该方法可以检测长度为L的突发性错误，但不能检测长度为L+1的突发性错误。 2.假设L列中任意一列检测出错的概率为1/2，那么，整个数据块的错判率为（1/2）L 。 X X X X X X……X …… R R R R R R.….R奇偶位 K行 该方法用在ICMP报头检验中。 26/31

27 海明编码举例 上例中，m=7，r=4，n=11，显然24>=11+1，采用偶校验 能纠正单比特错！ 3=1+2，5=1+4
6=2+4，7=1+2+4 9=1+8，10=2+8 11=1+2+8 能纠正单比特错！ 在接收方，如果校验位1不满足偶校验，而其他校验位都满足，则第1位出错，… 校验位：1（3，5，7，9，11） 2 （3，6，7，10，11） 4 （5，6，7） 8 （9，10，11） 27/31

28 检错码 在实际通信中使用纠错码好还是检错码好呢？ 例题 在多数通信中采用检错编码，但在单工信道中需要纠错编码。
假设一个信道误码率是10-6，且出错是孤立产生的（即只有单比特错），数据块长度为1000比特，如果采用纠错编码，需要10个校验位（210>1011），传送1M数据需要10000个校验位；如果采用检错编码，每个数据块只需一个奇偶校验位，传送1M数据只需1000个校验位和一个重传的数据1001位，共需要2001比特。 在多数通信中采用检错编码，但在单工信道中需要纠错编码。 28/31

29 多项式编码（循环冗余码CRC） CRC（Cyclic Redundancy Check) CRC编码的一般操作
给定一个m比特的帧或报文，发送方生成r比特的序列（也称为帧检验序列FCS，Frame Check Series），形成（m+r）的码字，该码字能被某个事先确定的数整除。接收方用相同的数去除收到的帧，如果无余数，则认为数据帧无差错。 多项式表示：即将k比特的数据用k项多项式表示，它的各项为X k-1…X0，它的系数为数据中对应位的0或1。 例如：110001可表示成X5+X4+1 29/31

30 循环冗余检验的原理 在数据链路层传送的帧中，广泛使用了循环冗余检验码 CRC 的检错技术。
在发送端，先把数据划分为组。假定每组 k 个比特。 假设待传送的一组数据 M = （现在 k = 6）。我们在 M 的后面再添加供差错检测用的 n 位冗余码一起发送。 30/31

31 冗余码的计算 用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。
得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 少1 位，即 R 是 n 位。 31/31

32 冗余码的计算举例 现在 k = 6, M = 101001。 设 n = 3, 除数 P = 1101，
被除数是 2nM = 。 模 2 运算的结果是：商 Q = ， 余数 R = 001。 把余数 R 作为冗余码添加在数据 M 的后面发送出去。发送的数据是：2nM + R 即： ，共 (k + n) 位。 32/31

33 循环冗余检验的原理说明 除数 P → 110101 101000110100000 ← 2nM 被除数 33/31
← Q 商 除数 P → ← 2nM 被除数 110101 111011 111010 111110 101100 110010 01110 ← R 余数 33/31

34 接收端对收到的每一帧进行 CRC 检验 (1) 若得出的余数 R = 0，则判定这个帧没有差错，就接受(accept)。
但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。 只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。 34/31

35 帧检验序列 FCS 在数据后面添加上的冗余码称为帧检验序列 FCS (Frame Check Sequence)。
循环冗余检验 CRC 和帧检验序列 FCS并不等同。 CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。 FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。 35/31

36 应当注意 仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。
“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。 也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。 要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。 36/31

37 常用的多项式国际标准 CRC-12=X12+X11+X3+X2+X+1 CRC-16= X16 +X15 +X2 +1
CRC-CCITT= X16 +X15 +X5 +1 CRC-32=X32+X26+X23 +X22 +X16 +X12 +X11 +X10 +X8 +X7 +X5 +X4 +X2+X+1 37/31

38 本讲小结 数据链路层的功能 帧定界 差错检测 循环冗余检验码（纠错码） 海明码（检错码） 38/31

39 作业 上交作业 P105, 3-01,3-02,3-04,3-05,3-07 39/31