第3章 数据链路层

1、第第3章章 数据链路层数据链路层 3.1 知识结构图知识结构图 数据链路层 差错控制流量控制介质访问控制 CRC校验滑动窗口 停止等待协议 退后N帧协议 选择重传协议 信道划分随机访问轮询访问 频分多路复用 时分多路复用 波分多路复用 码分多路复用 ALOHA CSMA CSMA/CA CSMA/CD 令牌传递协议 局域网 以太网无线局域网 802.3802.11 广域网 PPP HDLC 零比特填充 链路层设备 网桥 交换机 3.2 大纲要点归纳大纲要点归纳 1.组帧 零比特填充的基本原理 将需要传输的数据块看作比特序列，在数据块前和后各加入一个 特殊的比特序列（前文位模式和后文位模式，01

2、111110），表示数据 块的起始和结束，从而构成最终传输的帧。特殊比特序列如果在数据 块出现，就采用零比特填充法，即： 发送端：在发送端，当一串比特流尚未加上标志字段时，先扫描 整个帧，只要发现有5个连续的1，就立即填入一个0。显然，经过如 此处理后的数据，肯定不会出现连续6个1。 接收端：在接收一个帧时，先找到F字段确定帧的边界。接着再 对其中的比特流进行扫描。每当发现5个连续的1时，就将此后的一个 0删除，以还原最初的比特流。 l例1（2013年第37题） HDLC协议对01111100 01111110组帧后 对应的比特串为（ ）。 A.01111100 00111110 10 B.0

3、1111100 01111101 01111110 C.01111100 01111101 0 D.01111100 01111110 01111101 答案：A HDLC协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110 标识每一个帧的开 始和结束，因此帧数据中凡是出现了5个连续 的位“1”的时候，就会在输出的位流中填充 一个“0”。 2.检错编码 是在要发送的数据块上附加冗余位，使接收方知道有差错发生， 但不知道是怎么样的差错，然后向发送方请求重传，常用的是奇偶校 验码和CRC循环冗余校验码。 l在发送数据后附加一个校验位，校验位的取值使得包括数据和校 验位中的“1”的个数

4、分别为奇数/偶数。 l奇偶校验检错能力有限，只能校验出奇数个错但不能校验出偶数 个错。 l优点是简单、易实现，在位数不长的情况下常常采用。 CRC循环冗余校验码的基本原理：在发送端， 先把数据划分为组。假定每组k个比特。假设待传 送的一组数据M=101001（现在k=6）。在M后面 再添加供差错检测用的n位冗余码一起发送。用二 进制的模2运算（即加法不进位，减法不借位，这 是一种异或算法，也就是两个数值相同取0，两个 数值不同取1）进行2n乘M的运算，这相当于在 M后面添加n个0。得到的（k+n）位的数除以事先 选定好的长度为（n+1）位的除数P，得出商是Q， 余数R比除数P少1位，即R是n位

5、。 循环冗余校验 l码多项式 ln 位长度的位串 可以用n -1次码多项式表示： 例如，位串1010001的码多项式为: l数据后面附加上冗余码：k 位的信息码后面附加上r 位的冗余码: l由信息码生成冗余码 l用一个特定的r 次多项式G(x)去除 ，其余数为r-1次的码多 项式R(x)，对应的r 位的位串作为冗余码。G(x)称为生成多项式 (Generator Polynomial)。 l除法中使用模2减(无借位减，相当于作异或(XOR)运算)。 1210nn CCCC C 12 1210 nn nn C xCxCxC xC 64 1xx r C xx K xR x r x K x l由信息

6、码生成冗余码的过程： 信息码：1010001，对应的码多项式为 K(x)=x6+x4+1； 生成多项式：G(x)=x4+x2+x1+1(r=4)，对应 的位串为10111； X4K(x)：x4(x6+x4+1)=x10+x8+x4，对 应的位串为10100010000 R(x)为x4K(x)/G(x)的余数 生成冗余码示例 4位的余数1101作为冗余 码，其码多项式为 R(x)=x3+x2+1 l传输差错校验 l接收方将接收到的C(x)除以生成多项式G(x)，只要 余数不为零，则表明校验出传输差错，若余数为零， 则可以认为传输无误。 l常用的生成多项式 lCRC-8用于ATM信元头差错校验。

7、CRC-8=x8+x2+x+1 lCRC-16是HDLC规程中使用的。 CRC-16=x16+x15+x2+1 lCRC-32是IEEE802.3以太网中采用的。 3.滑动窗口协议 是一种基于多帧应答机制的通信协议，每一个要发送的帧都包含 一个序号，范围是从0到某个最大值，最大值通常是2n-1，n为帧序 号的长度，滑动窗口协议的要点是，在任何时刻发送进程要维护一组 帧序号，对应于一组已经发送但尚未被确认的帧，这些帧称为落在发 送窗口内；类似地，接收进程也要维护一组帧序号，对应于一组允许 接收的帧，这些帧称为落在接收窗口内。 可靠传输是采用确认和重传机制，接收站只处理包含在接收窗口 内的各个帧，

8、每当接收窗口中的n个帧全部处理完后，才发送应答帧， 应答帧的序号为n，表示前n-1个帧已经正确接收，下次希望接收的是 从n号开始的帧，也就是累积确认。 若帧序号采用3位二进制编码，由最大序号为Smax=23-1=7。对 于有序接收方式，发送窗口最大尺寸选为Smax；对于无序接收方式， 发送窗口最大尺寸至多是序号范围的一半。发送方管理超时控制的计 时器数应等于缓冲器数，而不是序号空间的大小。 发送方的滑动窗口 4.停止等待协议 是最简单的一种流量控制技术，它采用单工或半双工通信方式。 当发送方发送完一数据帧后，便等待接收方发回的反馈信号。若收到 的是肯定（ACK）信息，则接着发送下一帧；若收到的

9、是否定（NAK） 信息超时而没有收到反馈信号，则重发刚刚发过的数据帧。 5.后退N帧策略的基本原理 当接收方检测出失序的信息帧后，要求发送方重发最后一个正确 接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N个帧 后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息， 则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其 后的N帧。 回退-N ARQ接收窗口 回退-N ARQ传输 过程示例 l例2（2009年第35题） 数据链路层采用后退N帧（GBN）协议， 发送方已经发送了编号为07的帧。当计时器 超时时，若发送方只接收到0、2、3号帧的确 认，则发送方需要重发的帧数是（

10、 ）。 A.2 B.3 C.4 D.5 答案：C 连续ARQ协议中，接收方一般采用累积确 认的方式，即接收方对按序到达的最后一个分 组发送确认，题目中收到3的确认帧就代表编 号为0、1、2、3的帧已接收，而此时发送方未 收到1号帧的确认只能代表确认帧在返回的过 程中丢失了，而不代表1号帧未到达接收方。 因此需要重传的帧是编号为4、5、6、7的帧。 l例3（2012年第36题） 两台主机之间的数据链路层采用后退N帧 协议（GBN）传输数据，数据传输速率为 16kbps，单向传播时延为270ms，数据帧长 度范围是128512字节，接收方总是以与数据 帧等长的帧进行确认。为使信道利用率达到最 高，

11、帧序号的比特数至少为（ ）。 A.5 B.4 C.3 D.2 答案：B 两台主机之间的数据链路层采用后退N帧协议（GBN）传输 数据，其数据帧发送的过程是，主机甲连续发送了T个数据帧，主 机乙接收到第一个数据帧之后，以等长的长度发送确认帧。题目 中，数据传输速率为16kbps，即2KB/s。主机甲连续发送T个数据 帧的时间是T*M/(2KB/s)，其中，M为数据帧的长度。 信道利用率=信道发送的比特数/发送的总时延，如果想使信 道利用率达到最大，即在第一个确认帧回到主机甲时，主机甲需 要连续不停地发送数据帧。即在一个往返时延内，主机甲发送的 数据帧越多越好。根据上述条件列出计算公式： T*M/

12、(2KB/s)=0.27*2+2*（M/ 2KB/s ），得出：T=4。 6.选择重传ARQ协议 只是重传出现差错的那一帧。当接收端发现某帧出错后，将其后 面的正确的帧先接收下来，存放在一个缓冲区里，同时要求发送端重 传出差错的那一帧。接收端一旦接收到重传的新帧并确认后，与原已 存放在缓冲区的各帧一起按正确的顺序交付给上一层。选择重传ARQ 协议可避免重复传输那些已经正确接收到的数据帧，但代价是在接收 端必须设置具有一定容量的缓冲区。 7.信道划分介质访问控制 多路复用技术是使多路数据信号共同使用一条线路进行传输的技 术，使多个计算机或终端设备共享信道资源，提高信道的利用率。 （1）频分多路复

13、用（FDM） （2）时分多路复用（TDM） （3）波分复用（WDM） （4）码分多路复用（CDMA） l例4（2011年第35题） 数据链路层采用选择重传协议（SR）传 输数据，发送方已经发送了03号数据帧，现 已经收到1号帧的确认，而0,2号帧依次超时， 则此时需要重传的帧数是（ ）。 A.1 B.2 C.3 D.4 答案：B 8.载波监听多路访问/冲突检测（CSMA/CD） 以太网采用的协调方法是使用一种特殊的协议，即载波监听多点 接入/碰撞检测CSMA/CD。要点如下： （1）多点接入：许多计算机以多点接入的方式连接在一根总线上，是总 线型网络。 （2）载波监听：是指每一个站在发送数据之

14、前先要检测一下总线上是否 有其他计算机在发送数据；如果有，则暂时不要发送数据，以免发生 碰撞。 （3）碰撞检测：就是计算机边发送数据边检测信道上的信号电压大小， 由信号电压摆动值的大小来判断是否发生了碰撞。正常发送时，计算 机发送的数据都是使用曼彻斯特编码的信号；发生碰撞时，信号会产 生严重的失真。一旦发送碰撞，就立即停止发送。也称为冲突检测。 （4）为什么会发生碰撞：每个站点都是在监听到信道“空闲”时才发送 数据的，为什么还会发生碰撞？根本原因是因为电磁波在媒体上的传 输速度总是有限的。 电磁波在1km电缆上的传输时延约为5s。将总线上单程的端到 端传播延迟记为。A发送数据后，最迟要经过两倍

15、的总线端到端的 传输延迟（2）才知道自己发送的数据和其他站点发送的数据没有 发生碰撞。可见，在一个站在自己发送数据后的一小段时间是不确定 的，它取决于另一个发送数据的站到本站的距离。因此，以太网不能 保证在某一时间之内能将自己的数据帧成功地发送出去。这一特点称 为发送的不确定性。 （5）争用期：最先发送数据帧的站点，在发送数据帧后至多经过2就 可以知道该帧是否发生了碰撞。以太网的端到端往返时延2称为争 用期，又称为碰撞窗口。经过争用期这段时间还没有检测到碰撞，才 能肯定这次发送不会发生碰撞。 问题：当某站正在发送数据时，另外两个站有数据要发送。这两 个站进行载波监听，发现总线忙，于是就等待；当

16、它们发现总线变为 空闲时，就立即发送自己的数据。但这必然再次发送碰撞；经检测发 现了碰撞，就停止发送。然后再重新发送，这样下去，一直不 能发送成功。 （6）退避算法：就是让发生碰撞的站在停止发送数据后，不是立即再发 送数据，而是推迟（这叫做退避）一个随机事件，具体做法是： 确定基本退避时间，一般是取争用期2。 定义参数k，它等于重传次数，但k不超过10，即k=Min（重传次数， 10）。 从离散整数集合0,1,2,(2k-1)中随机地取出一个数，记为r。重传 所需的时间就是r倍的基本退避时间。 当重传达16次仍不能成功时，则丢弃该帧，并向高层报告。 以太网取51.2s为争用期的长度。对于10M

17、b/s以太网，在争用 期内可以发送512bit，即64字节。因此以太网规定了最短有效帧长为 64字节，凡长度小于64字节的帧都是由于冲突而异常终止的无效帧。 l例5（2013年第36题） 下列介质访问控制方法中，可能发生冲突 的是（ ）。 A.CDMA B.CSMA C.TDMA D.FDMA 答案：B l例6（2009年第37题） 在一个采用CSMA/CD协议的网络中，传输介质 是一根完整的电缆，传输速率为1Gbps，电缆中的信 号传播速度是200000km/s。若最小数据帧长度减少 800比特，则最远的两个站点之间的距离至少需要 （ ）。 A.增加160m B.增加80m C.减少160m

18、 D.减少80m 答案：D 考查考查CSMA/CDCSMA/CD协议的工作原理协议的工作原理 若最短帧长减少，而数据传输速率不变，则需要使冲突域的 最大距离变短来实现争用期的减少。 争用期是指网络中收发结点间的往返时延，经过争用期这段时 间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。即： 争用期=（2*S）/信号的传播速度 争用期也指数据没有发生碰撞的最长时间，即： 争用期=数据帧长度/数据帧传输速率 题中，最小数据帧长度减少800比特，假设需要减少的最小距 离为s，单位是m，则可以得到下式： 2*s/（2*108）=800/（1*109） 可得：s=80m，即最远的两个站点之间的距离最少

19、需要减少80m。 9.CSMA/CA协议 该协议支持两种操作，第一种中发送站在发送前监听信道，信道 忙则推迟发送直至发现信道空闲，一旦信道空闲立即发送帧，但在发 送的过程中并不检测冲突（因为可能无法检测），如果发生冲突，发 送站使用二进制指数退避算法等待一段时间，然后再试。第二种操作 中发送站向接收站发送一个RTS帧请求发送，接收站发送一个CTS帧 表示同意发送，然后发送站可以发送一个帧，并启动一个ACK计时器， 接收站正确接收后必须返回一个ACK帧进行确认，若发送站的ACK计 时器超时，则发送站重发。收到RTS或CTS的站都用NAV信号通知自 己的相关实体保持沉默，直至整个交换过程结束。保持

20、沉默的时间可 以根据RTS或CTS中给出的待发送帧或待接收帧的长度以及确认所需 要的时间估算出来。 l例7（2011年第36题） 下列选项中，对正确接收到的数据帧进行 确认的MAC协议时（ ）。 A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA 答案：D 10.局域网的基本概念与体系结构 局域网是将小区域内的各种通信设备互联在一起的通 信网络。从这个定义可引出局域网络的三个属性： （1）局域网络是一个通信网络，从协议层次的观点看，它 包含着下三层的功能，将连接到局域网的数据通信设备加 上高层协议和网络软件组成为计算机网络，称为计算机局 域网络。 （2）计算机局域网络中数据通信

21、设备是广义的，包括计算 机、终端和各种外围设备等。 （3）所指的小区域可以是一个建筑物内，一个校园或者大 至几十公里直径的一个区域。 局域网络的协议结构包括物理层、数据链路层和网 络层。由于局域网没有路由问题，一般不单独设置网络层， 把数据链路层分为介质访问控制子层（MAC）和数据链路 控制子层（LLC）。 LLC子层提供与媒体接入无关的链路控制，包括差错控制和流量控制， 提供面向连接和无连接的服务。 MAC子层的主要功能是成帧、寻址、实现MAC和差错检验等。但MAC子 层一般并不进行差错控制，提供不可靠的传输服务。 l例8（2012年第35题） 以太网的MAC提供的是（ ）。 A.无连接的不

22、可靠的服务 B.无连接的可靠服务 C.有连接的不可靠服务 D.有连接的可靠服务 答案：A 11.网桥的概念及其工作原理 网桥工作在数据链路层，它根据MAC帧的目的地址对收到的帧进 行转发。网桥具有过滤帧的功能。当网桥收到一个帧时，并不是向所 有的接口转发此帧，而是先检查此帧的目的MAC地址，然后再确定将 该帧转发到哪一个接口。 网桥的自学习：网桥收到一个帧后进行自学习。查找转发表中与 收到帧的源地址有无相互匹配的项目。若没有，就在转发表中增加一 个项目（源地址、进入的接口和事件）。若有，则把原有的项目进行 更新。 转发帧：查找转发表中与收到的帧的目的地址有无匹配的项目。 如没有，则通过所有其他

23、接口（但进入网桥的接口除外）进行转发。 如有，则按转发表中给出的接口进行转发。若转发表中给出的接口就 是该帧进入网桥的接口，则应丢弃这个帧（因此这时不需要经过网桥 进行转发）。 12.局域网交换机及其工作原理 局域网交换机实质上就是一个多接口的网桥，工作在数据链路层， 每个接口都直接与主机相连，并且一般都工作在全双工。 l例9（2009年第36题） 以太网交换机进行转发决策时使用的 PDU地址是（ ）。 A.目的物理地址 B.目的IP地址 C.源物理地址 D.源IP地址 答案：A PDU PDU协议数据单元协议数据单元 考查交换机的工作原理考查交换机的工作原理 交换机实质上是一个多端口网桥，工

24、作在数据链路 层，数据链路层使用物理地址进行转发，而转发通常都是 根据目的地址来决定出端口。在转发过程中，使用的是目 的地址来进行转发决策的，因此，PDU地址就是目的物理 地址。 l例10（2013年第38题） 对于100Mbps的以太网交换机，当输出端 口无排队，以直通交换方式转发一个以太网帧 （不包括前导码）时，引入的转发延迟至少是 （ ）。 A.0us B.0.48us C.5.12us D.121.44us 答案：B 直通交换方式是以太网交换机可以在各端 口间交换数据。它在输入端口检测到一个数据 包时，检查该包的包头，获取包的目的地址， 启动内部的动态查找表转换成相应的输出端口， 在输

25、入与输出交叉处接通，把数据包直通到相 应的端口，实现交换功能。通常情况下，直通 交换方式只检查数据包的包头即前14个字节， 由于不需要考虑前导码，只需要检查目的地址 的6B，所以最短的传输延迟是0.48us。 3.3 难点释疑难点释疑 1.网桥，中继器和交换机的区别 网桥与转发器不同，（1）网桥工作在数据链路层，而转发器工 作在物理层；（2）网桥不像转发器转发所有的帧，而是只转发未出 现差错，且目的站属于另一网络的帧或广播帧；（3）转发器转发一 帧时不用检测传输媒体，而网桥在转发一帧前必须执行CSMA/CD算法； （4）网桥和转发器都有扩展局域网的作用，但网桥还能提高局域网 的效率并连接不同M

26、AC子层和不同速率局域网的作用。 以太网交换机通常有几十个端口，而网桥一般只有24个端口； 它们都工作在数据链路层；网桥的端口一般连接到局域网，而以太网 的每个接口都直接与主机相连，交换机允许多对计算机同时通信。所 以实质上以太网交换机是一个多端口的网桥，连到交换机上的每台计 算机就像到网桥的一个局域网段上。网桥采用存储转发方式进行转发， 而以太网交换机还可采用直通方式转发。以太网交换机采用了专用的 交换机芯片，转发速度比网桥快。 2.CSMA/CA和CSMA/CD的差异 CSMA/CD中，当节点侦听到信道空闲时，立即就可以发送数据。 而在CSMA/CA中，当侦听到信道空闲时要推迟发送，尤其在

27、第2步中 要随机回退，这是为了减少冲突而采取的措施。考虑这样一种情形， 一个节点正在发送，而另外两个节点在侦听信道准备发送。当信道上 的发送一完成，两个等待的节点同时侦听到信道空闲。如果它们等待 DIFS后立即发送，则肯定发生冲突。由于CSMA/CA不检测冲突且发 生冲突的代价很高，为了减少这种冲突的发生，令节点在侦听到信道 忙后立即进入回退。如果它们刚好选择了不同的回退值，则当信道空 闲时会有一个节点发送。未发送的节点将冻结其计数值，并抑制发送 直至前一个节点发送完成。当然，如果两个节点选择了相同的回退值 或者是相互隐藏的，则仍有可能发生冲突，这时可从一个更大的范围 内选取回退值。 3.IE

28、EE802.3标准的MAC帧和Ethernet V2的MAC帧区别 不同点在第三字段。在Ethernet V2中该字段表示LLC的上层所使 用的协议类型，而在802.3标准中该字段表示长度/类型字段。这个字 段表示MAC帧的数据字段长度，或者等同于以太网V2的类型字段。 当长度/类型字段表示类型时，就与Ethernet V2的MAC帧一样。当表 示长度时，MAC帧就必须装入802.2标准所定义的LLC子层的LLC帧。 802.3的MAC帧的数据字段长度为461500字节，而DIX Ethernet V2 的固定为1500字节。IEEE802.3帧结构，各字段功能如下。 4. IEEE802.3的以太网标准 在这些标准中签名的数字表示传输速度，单位是“Mbps”，最后 的一个数字表示单段网线长度（基准单位是10m），Base表示“基带” 的意思，Broad代表“带宽”。 10Base-5使用粗同轴电缆，最大网段长度为500m，基带传输方法。 10Base-2使用细同轴电缆，最大网段长度为185m，基带传输方法。 10