第三章 数据链路层

1. 概述

• 链路（Link）就是从一个节点到相邻节点的一段物理线路，而中间没有任何其他的交换节点。
• 数据链路（Data Link）是指把实现通信协议的软件加到链路上，就构成了数据链路。

• 数据链路层以帧为单位传输和处理数据。

  数据链路层使用的信道

• 点对点信道

• 广播信道

2. 数据链路层的三个重要问题：

2.1 封装成帧

（1）封装成帧是指数据链路层给上层交付的协议数据单元添加帧头和帧尾使之称为帧。

  - 帧头和帧尾中包含有重要的控制信息。

  - 帧头和帧尾的作用之一就是**帧定界**。在帧头和帧尾中，各包含有一个长度为1字节的标志字段，作用就是帧定界。
  - 注：并不是每一种数据链路层协议的帧都包含有帧定界标志。
  - 以MAC帧为例：以太网的数据链路层封装好MAC帧后，将其交付给物理层，物理层会在MAC帧前面添加８字节的前导码，然后再将比特流转换成电信号发送。

前同步码作用：使接收方的时钟同步。
（2）透明传输是指数据链路层对上层交付的传输数据没有任何限制，就好像数据链路层不存在一样。

  - 面向字节的物理链路使用字节填充（或称字符填充）的方法实现透明传输。
  - 面向比特的物理链路使用比特填充的方法实现透明传输。

（3）为了提高帧的传输效率，应当使帧的数据部分的长度尽可能大些。
（4）考虑到差错控制等多种因素，每一种数据链路层协议都规定了帧的数据部分的长度上限，即最大传输单元MTU（Maximum Transfer Unit）。

2.2 差错检测

（1）实际的通信链路都不是理想的，比特在传输的过程中可能会产生差错：1可能会变成0，而0也可能变成1。这称为比特差错或误码。
（2）在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BER（Bit Error Rate）。使用差错检测码来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一。

FCS：(Frame Check Sequence) 帧检验序列：其作用就是让接收方的数据链路层检查帧在传输过程中是否产生了误码。
（3）奇偶校验：

  - 在待发送的数据后面添加1位奇偶校验位，使整个数据（包含所添加的校验位在内）中“1”的个数为奇数（奇校验）或（偶校验）。
  - 如果有奇数个位发生误码，则奇偶性发生改变，可以检查处误码。
  - 如果有偶数个位发生误码，则奇偶性不发生变化，不能检查出误码（漏检）。
  - 因此，数据链路层一般不会采用这种检测方法。

（4）循环冗余校验CRC（Cyclic Redundancy Check）：这是一种具有很强检错能力的检错方法，漏检率极低。

  - 收发双方约定好一个生成多项式G(x)；
  - 发送方基于待发送的数据和生成多项式计算出差错检测码（冗余码），将其添加到待传输数据的后面一起传输；
  - 接收方通过生成多项式来计算收到的数据是否产生了误码；

  - 检错码只能检测出帧在传输过程中出现了差错，但并不能定位错误，因此无法纠正错误。
  - 要想纠正传输过程中的差错，可以使用冗余信息更多的纠错码进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用。
  - 循环冗余检验 CRC 有很好的检错能力（漏检率非常低），虽然计算比较复杂，但非常易于实现硬件扩展，因此被广泛应用于数据链路层。
  - 在计算机网络中，经常采用检错重传方式来纠正传输中的差错，或者仅仅是丢弃检测到差错的帧，这取决于数据链路层向起上层提供的是可靠传输服务还是不可靠传输服务。

2.3 可靠传输

（1）基本概念：

  - 使用差错检测技术（eg.循环冗余校验CRC），接收方的数据链路层就可以检测出帧在传输过程中是否产生了误码（比特错误）。
  - 数据链路层向上提供的服务类型
     - 不可靠传输服务：仅仅丢弃有误码的帧，其他什么也不做；
     - 可靠传输服务：想办法实现发送端发送什么，接收端就接收什么
  - 一般情况下，有线链路的误码率比较低，为了减小开销，并不要求数据链路层向上层提供可靠传输服务。即使出现了误码，可靠传输的问题交由上层处理。
  - 无线链路易受到干扰，误码率较高，因此要求数据链路层必须向上层提供可靠传输服务。

2.3.1 可靠传输的实现机制—-停止-等待协议(Stop-and-Wait)

• 停止等待协议信道利用率

• 当往返时延 RTT 远大于数据帧发送时延 Td 时(例如使用卫星链路)，信道利用率非常低。
• 若出现重传，则对于传送有用的数据信息来说，信道利用率还要低。
• 为了克服停止-等待协议信道利用率很低的缺点，就产生了另外两种协议，即后退 N 帧协议 GNB 和选择重传协议 SR。

• 停止-等待协议的信道利用率很低，若出现超时重传，则信道利用率更低
• 采用流水线传输可以提高信道利用率

2.3.2 可靠传输的实现机制—-回退N帧协议GNB（Go Back N）

为什么使用回退N帧协议？
在相同的时间内，使用停止-等待协议的发送方只能发送一个数据分组，而采用流水线传输的发送方，可以发送多个数据分组。

• 该协议在流水线传输的基础上，利用发送窗户来限制发送方可连续发送数据分组的个数。
• 工作原理：

• 例题：

2.3.3 可靠传输的实现机制—-选择重传协议 SR

• 回退N帧协议的接收窗口尺寸 Wr 只能等于1，因此接收方只能按序接收正确到达的数据分组。
• 一个数据分组的误码就会导致其后续多个数据分组不能被接收方按序接收而丢弃（尽管它们无乱序和误码）。这必然会造成发送方对这些数据库分组的超时重传，显然这是对痛惜资源的极大浪费。
• 为了进一步提高性能，可设法只重传出现误码的分组。因此，接收窗口的尺寸 Wr不用等于1（而应大于1），以便接收方先收下失序到达但无误码并且序号落在接收窗口内的那些数据分组，等到所缺分组收齐后再一并送交上层。这就是选择重传协议。
• 注意：选择重传协议为了使发送方仅重传出现差错的分组，接收方不能再采用累积确认，而需要对每个正确接收到的分组进行逐一确认。

选择重传协议的工作原理：

例题：

3. 点对点协议

• 点对点协议PPP（Pooint-to-Point Protocol）是目前使用最广泛的点对点数据链路层协议。

• PPP协议在点对点链路传输各种协议数据报提供了一个标准方法，主要由以下三部分构成：
  • 对各种协议数据报的封装方法（封装成帧）
  • 链路控制协议LCP 用于建立、配置以及测试数据链路的连接
  • 一套网络控制协议NCPs 其中的每一个协议支持不同的网络层协议

• 帧格式：

• 透明传输：PPP协议实现透明传输的方法取决于所使用的链路类型。
  • 如果是面向字节的异步链路，采用字节填充法—插入”转义字符”

• 如果是面向比特的同步链路，比特填充法—插入”比特0”

• 差错检测：能够对接收端收到的帧进行检测，并立即丢弃有差错的帧。

• 工作状态：
  • 当用户拨号接入 ISP 时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。
  • PC 机向路由器发送一系列的 LCP 分组（封装成多个 PPP 帧）。
  • 这些分组及其响应选择一些 PPP 参数，并进行网络层配置，NCP 给新接入的 PC 机
  • 分配一个临时的 IP 地址，使 PC 机成为因特网上的一个主机。
  • 通信完毕时，NCP 释放网络层连接，收回原来分配出去的 IP 地址。接着，LCP 释放数据链路层连接。最后释放的是物理层的连接。

4. 媒体接入控制

4.1 基本概念：

共享信道要着重考虑的一个问题就是如何协调多个发送和接受站点对同一个共享传输媒体的占用，即媒体接入控制MAC(Medium Access Control)。
媒体接入控制的分类：

4.2 信道复用：

• 复用(Multiplexing) 是通信技术中的一个重要概念。复用就是通过一条物理线路同时传输多路用户的信号。
• 当网络中传输媒体的传输容量大于多条单一信道的总通信量时，可利用复用技术在一条物理线路上建立多条通信信道来充分利用传输媒体的带宽。

4.3 常见的信道复用技术：

频分复用FDM、时分复用TDM、波分复用WDM、码分复用CDM

4.3.1 频分复用：

如图，将传输线路的资源划分为多个子频带，形成多个子信道，各子信道之间需要留出隔离频带，以免造成子信道间的干扰。当多路信号输入一个多路复用器时，这个复用器将每一路信号调制到不同频率的载波上。接收端由相应的分用器通过滤波将各路信号分开。将合成的复用信号恢复成原始的多路信号。

频分复用的所有用户同时占用不同的频带资源并进行通信。

4.3.2 时分复用：

时分复用技术将传输线路的资源按时隙轮流分配给不同的用户，每对用户只在所分配的时隙里使用线路传输数据。
时分复用技术将时间划分成了一段段等长的时分复用帧，每一个时分复用的用户在每一个时分复用帧中占用固定序号的时隙。

时分复用的所有用户在不同的时间占用同样的频带宽度。

4.3.3 波分复用：

波分复用其实就是光的频分复用。

4.3.4 码分复用：

• 码分复用CDM(Code Division Multiplexing)是一种共享信道的方法，人们更常用名词是码分多址CDMA（Code Division Multiple Access）。、
• 与FDM和TDM不同，CDM的每一个用户可以在同样的时间使用同样的频带进行通信。
• 由于各用户使用经过特殊挑选的不同码型，因此各用户之间不会造成干扰。
• 在CDMA中，每个比特时间再划分为m个短的间隔，称为码片（chip），通常m值为64或128，一般m=8
• 使用CDMA的每一个站被指派一个唯一的m bit码片序列(Chip Sequence).
  • 一个站如果要发送比特1，则发送它自己的m bit码片序列
  • 如果要发送0，则发送该码片序列的二进制反码

举例：

• 码片序列的挑选规则：

4.4 媒体接入控制—动态接入控制—随机接入

• 多址接入MA：多个站连接在一条总线上，竞争使用总线。
• 载波监听CS每一个站在发送帧之前要先检测一下总线上是否有其他站点在发送帧（”先听后说”）
  • 若检测到总线空闲96比特时间，则发送这个帧
  • 若检测到总线忙，则继续检测并等待总线转为空闲96比特时间，然后发送这个帧。

• 碰撞检测CD：每一个正在发送帧的站，边发送边检测碰撞（”边说边听”）

  • 一旦发现总线上出现碰撞，则立即停止发送，退避一段时间后再次发送

    5. 随机接入

• 总线局域网使用的协议：CSMA/CD协议—Carrier Sense Multiple Access/collision detection，带有冲突检测的载波侦听多路存取，是IEEE 802.3使用的一种媒体访问控制方法。

  • 以太网使用采用的协议是具有冲突检测的载波监听多点接入 CSMA/CD。协议的要点是：发送前先监听，边发送边监听，一旦发现总线上出现了故障，就立即停止发送。然后按照退避算法等待一段时间后再次发送。因此，每一个站在自己发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。以太网上各站点都平等的征用以太网信道。
• 无线局域网使用的协议：CSMA/CA协议

  CSMA/CD协议—争用期（碰撞窗口）

  

  CSMA/CD协议—最小帧长

  

  CSMA/CD协议—最大帧长

  

  CSMA/CD协议—截断二进制指数退避算法

  
  退避算法的示例：
  

CSMA/CD协议—信道利用率

CSMA/CD协议—帧发送流程图

CSMA/CD协议—帧接收流程图

例题：

CSMA/CA协议

载波监听多址接入/碰撞避免 CSMA/CA（Carrier Sense Multiple Access/Collision Avoidance）。
既然CSMA/CD协议已经成功地应用于使用广播信道的有线局域网，那么同样使用广播信道的无线局域网能不能也使用CSMA/CD协议呢？

• 在无线局域网中，仍然可以使用载波监听多址接入CSMA，即在发送帧之前先对传输媒体进行载波监听。若发现有其他站在发送帧，就推迟发送以免发生碰撞。
• 在无线局域网中，不能使用碰撞检测CD，原因如下：
  • 由于无线信道的传输条件特殊，其信号强度的动态范围非常大，无线网卡上接收到的信号强度往往会远小于发送信号的强度（可能相差百万倍）。如果要在无线网卡上实现碰撞检测CD，对硬件的要求非常高。
  • 即使能在硬件上实现无线局域网的碰撞检测功能，但由于无线电波传播的特殊性（存在隐蔽站问题），进行碰撞的意义也不大。

CSMA/CA协议的工作原理

虚拟载波监听机制能减少隐蔽站带来的碰撞问题的示例

6. 以太网的MAC层

• MAC地址：在局域网中，硬件地址又称为物理地址或MAC地址。

  MAC地址

• 使用点对点信道的数据链路层不需要使用地址

• 使用广播信道的数据链路层必须使用地址来区分主机

广播信道的数据链路层必须使用地址(MAC)

例题：

• 注意：MAC地址又称为硬件地址或物理地址。不要被 “物理” 二字误导认为物理地址属于物理层范畴，物理地址属于数据链路层范畴。

IEEE 802局域网的MAC地址格式

组织唯一标识符OUI

• 生产网络设备的厂商，需要向IEEE的注册管理机构申请一个或多个OUI

网络接口标识符

• 由获得OUI的厂商自行随意分配

EUI-48

• 48是这个MAC地址的位数

关于无效的 MAC 帧

• 数据字段的长度与长度字段的值不一致；
• 帧的长度不是整数个字节；
• 用收到的帧检验序列 FCS 查出有差错；
• 数据字段的长度不在 46 ~ 1500 字节之间。
• 有效的 MAC 帧长度为 64 ~ 1518 字节之间。

对于检查出的无效 MAC 帧就简单地丢弃。以太网不负责重传丢弃的帧。

IEEE 802局域网的MAC地址发送顺序

单播MAC地址举例

• 单播帧（一对一）：即收到的帧的MAC地址与本站的硬件地址相同。

主机B给主机C发送单播帧，主机B首先要构建该单播帧，在帧首部中的目的地址字段填入主机C的MAC地址，源地址字段填入自己的MAC地址，再加上帧首部的其他字段、数据载荷以及帧尾部，就构成了该单播帧。

• 主机B将该单播帧发送出去，主机A和C都会收到该单播帧
• 主机A的网卡发现该单播帧的目的MAC地址与自己的MAC地址不匹配，丢弃该帧
• 主机C的网卡发现该单播帧的目的MAC地址与自己的MAC地址匹配，接受该帧
• 并将该帧交给其上层处理

广播MAC地址举例

• 广播帧（一对全体）：即发送给本局域网上所有站点的帧

假设主机B要发送一个广播帧，主机B首先要构建该广播帧，在帧首部中的目的地址字段填入广播地址，也就是十六进制的全F，源地址字段填入自己的MAC地址，再加上帧首部中的其他字段、数据载荷以及帧尾部，就构成了该广播帧。

主机B将该广播帧发送出去，主机A和C都会收到该广播帧，发现该帧首部中的目的地址字段的内容是广播地址，就知道该帧是广播帧，主机A和主机C都接受该帧，并将该帧交给上层处理。

多播MAC地址举例

• 多播帧（一对多）：即发送给本局域网上一部分站点的帧

假设主机A要发送多播帧给该多播地址。将该多播地址的左起第一个字节写成8个比特，第一个字节的最低比特位是1，这就表明该地址是多播地址。
快速判断地址是不是多播地址，就是上图所示箭头所指的第十六进制数不能整除2（1,3,5,7,9,B,D,F），则该地址是多播地址

假设主机B，C和D支持多播，各用户给自己的主机配置多播组列表如下所示：

主机B属于两个多播组，主机C也属于两个多播组，而主机D不属于任何多播组。

主机A首先要构建该多播帧，在帧首部中的目的地址字段填入该多播地址，源地址点填入自己的MAC地址，再加上帧首部中的其他字段、数据载荷以及帧尾部，就构成了该多播帧。

• 主机A将该多播帧发送出去，主机B、C、D都会收到该多播帧。
• 主机B和C发现该多播帧的目的MAC地址在自己的多播组列表中，主机B和C都会接受该帧。
• 主机D发现该多播帧的目的MAC地址不在自己得多播组列表中，则丢弃该多播帧。

给主机配置多播组列表进行私有应用时，不得使用公有的标准多播地址。

7. 扩展的以太网

7.1 在物理层扩展以太网—集线器

概念：

• 传统以太网最初是使用粗同轴电缆，后来演进到使用比较便宜的细同轴电缆，最后发展为使用更便宜和更灵活的双绞线。
• 采用双绞线的以太网采用星形拓扑，在星形的中心则增加了一种可靠性非常高的设备，叫做集线器 (hub)。
• 集线器是也可以看做多口中继器，每个端口都可以成为一个中继器，中继器是对减弱的信号进行放大和发送的设备。
• 集线器的以太网在逻辑上仍是个总线网，需要使用CSMA/CD协议来协调各主机争用总线，只能工作在半双工模式，收发帧不能同时进行。

使用集线器扩展：将多个以太网段连成更大的、多级星形结构的以太网。

优点：

1. 使原来属于不同碰撞域的以太网上的计算机能够进行跨碰撞域的通信。
2. 扩大了以太网覆盖的地理范围。

缺点：

1. 碰撞域增大了，但总的吞吐量并未提高。
2. 如果不同的碰撞域使用不同的数据率，那么就不能用集线器将它们互连起来。

碰撞域

• 碰撞域（collision domain）又称为冲突域，是指网络中一个站点发出的帧会与其他站点发出的帧产生碰撞或冲突的那部分网络。

• 碰撞域越大，发生碰撞的概率越高。

  7.2 在数据链路层扩展以太网—交换机

  概念：

• 扩展以太网更常用的方法是在数据链路层进行。

• 早期使用网桥，现在使用以太网交换机。

网桥

• 网桥工作在数据链路层。
• 它根据 MAC 帧的目的地址对收到的帧进行转发和过滤。
• 当网桥收到一个帧时，并不是向所有的接口转发此帧，而是先检查此帧的目的MAC 地址，然后再确定将该帧转发到哪一个接口，或把它丢弃。

交换机

• 1990 年问世的交换式集线器 (switching hub) 可明显地提高以太网的性能。
• 交换式集线器常称为以太网交换机 (switch) 或第二层交换机 (L2 switch)，强调这种交换机工作在数据链路层。
• 以太网交换机实质上就是一个多接口的网桥

以太网交换机的特点：
以太网交换机实质上就是一个多接口的网桥，相互通信的主机都是独占传输媒体，无碰撞的传输数据。

7.3 集线器与交换机的区别

使用集线器互连而成的共享总线式以太网上的某个主机，要给另一个主机发送单播帧，该单播帧会通过共享总线传输到总线上的其他各个主机
使用交换机互连而成的交换式以太网上的某个主机，要给另一个主机发送单播帧，该单播帧进入交换机后，交换机会将该单播帧转发给目的主机，而不是网络中的其他各个主机
这个例子的前提条件是忽略ARP过程，并假设交换机的帧交换表已经学习或配置好了。

7.4 以太网交换机的交换方式

存储转发方式

• 把整个数据帧先缓存后再进行处理。

直通 (cut-through) 方式

• 接收数据帧的同时就立即按数据帧的目的 MAC 地址决定该帧的转发接口，因而提高了帧的转发速度。
• 缺点是它不检查差错就直接将帧转发出去，因此有可能也将一些无效帧转发给其他的站。

这个例子的前提条件是忽略ARP过程，并假设交换机的帧交换表已经学习或配置好了 。
对比集线器和交换机


多台主机同时给另一台主机发送单播帧

• 集线器以太网：会产生碰撞，遭遇碰撞的帧会传播到总线上的各主机
• 交换机以太网：会将它们缓存起来，然后逐个转发给目的主机，不会产生碰撞

这个例子的前提条件是忽略ARP过程，并假设交换机的帧交换表已经学习或配置好了。

集线器扩展以太网和交换机扩展以太网区别：
单播：

广播：

多个单播：


广播域（broadcast domain）：指这样一部分网络，其中任何一台设备发出的广播通信都能被该部分网络中的所有其他设备所接收。

8. 以太网交换机的自学习和转发帧的流程（重点）

8.1 概念

8.2 自学习和转发帧的例子

以下例子假设各主机知道网络中其他各主机的MAC地址（无需进行ARP）
A->B

1. A 先向 B 发送一帧。该帧从接口 1 进入到交换机
2. 交换机收到帧后，先查找（图中左边）交换表。没有查到应从哪个接口转发这个帧给 B
3. 交换机把这个帧的源地址 A 和接口 1 写入（图中左边）交换表中
4. 交换机向除接口 1 以外的所有的接口广播这个帧
5. 接口 4到接口 2，先查找（图中右边）交换表。没有查到应从哪个接口转发这个帧给 B
6. 交换机把这个帧的源地址 A 和接口 1 写入（图中右边）交换表中
7. 除B主机之外与该帧的目的地址不相符，将丢弃该帧
8. 主机B发现是给自己的帧，接受该帧

B -> A

1. B 向 A 发送一帧。该帧从接口 3 进入到交换机
2. 交换机收到帧后，先查找（图中左边）交换表。发现（图中左边）交换表中的 MAC 地址有 A，表明要发送给A的帧应从接口1转发出去。于是就把这个帧传送到接口 1 转发给 A。
3. 主机 A 发现目的地址是它，就接受该帧
4. 交换机把这个帧的源地址 B 和接口 3 写入（图中左边）交换表中

E -> A

1. E 向 A发送一帧
2. 交换机收到帧后，先查找（图中右边）交换表。发现（图中右边）交换表中的 MAC 地址有 A，表明要发送给A的帧应从接口2转发出去。于是就把这个帧传送到接口 2 转发给 接口 4。
3. 交换机把这个帧的源地址 E 和接口 3 写入（图中右边）交换表中
4. 接口 4 到 左边的交换机，先查找（图中左边）交换表。发现（图中左边）交换表中的 MAC 地址有 A，表明要发送给A的帧应从接口1转发出去。于是就把这个帧传送到接口 1 转发给 A。
5. 交换机把这个帧的源地址 E 和接口 4 写入（图中左边）交换表中
6. 主机 A 发现目的地址是它，就接受该帧

G -> A

主机 A、主机 G、交换机 1的接口 1就共享同一条总线（相当于总线式网络，可以想象成用集线器连接了）

1. 主机 G 发送给 主机 A 一个帧
2. 主机 A 和 交换机接口 1都能接收到
3. 主机 A 的网卡收到后，根据帧的目的MAC地址A，就知道是发送给自己的帧，就接受该帧
4. 交换机 1收到该帧后，首先进行登记工作
5. 然后交换机 1对该帧进行转发，该帧的MAC地址是A，在（图中左边）交换表查找MAC 地址有 A
6. MAC 地址为 A的接口号是1，但是该帧正是从接口 1 进入交换机的，交换机不会再从该接口 1 讲帧转发出去，因为这是没有必要，于是丢弃该帧

随着网络中各主机都发送了帧后，网络中的各交换机就可以学习到各主机的MAC地址，以及它们与自己各接口的对应关系

考虑到可能有时要在交换机的接口更换主机，或者主机要更换其网络适配器，这就需要更改交换表中的项目。为此，在交换表中每个项目都设有一定的有效时间。过期的项目就自动被删除。
以太网交换机的这种自学习方法使得以太网交换机能够即插即用，不必人工进行配置，因此非常方便。

8.3 小结

交换机自学习和转发帧的步骤归纳