3 数据链路层¶

3.1 基本概念¶

链路（Link）是指从一个节点到相邻节点的一段物理线路（有线或无线），而中间没有任何其他的交换节点。

数据链路（Data Link）是基于链路的。当在一条链路上传送数据时，除需要链路本身，还需要一些必要的通信协议来控制这些数据的传输，把实现这些协议的硬件和软件加到链路上，就构成了数据链路。

帧（Frame）是数据链路层对等实体之间在水平方向进行逻辑通信的协议数据单元PDU。

Note

数据链路层解决的是链路上数据的传输的问题

3.2 数据链路层面临的三个重要问题¶

3.2.1 封装成帧和透明传输¶

封装成帧是指数据链路层给上层交付下来的协议数据单元PDU添加一个首部和一个尾部，使之成为帧。其中帧的首部和尾部中包含有一些重要的控制信息。（不同协议下控制信息不一样）

接收方的数据链路层如何从物理层交付上来的比特流中提取出一个个的帧呢？在 PPP 帧的首部和尾部有帧定界标志来进行标识，但是有一些帧首部和尾部并不包含帧定界标志，比如说以太网 V2 的 MAC 帧，它是使用前导码来进行标识的

为了提高数据链路层传输帧的效率，应当使帧的数据载荷的长度尽可能地大于首部和尾部的长度。

考虑到对缓存空间的需求以及差错控制等诸多因素，每一种数据链路层协议都规定了帧的数据载荷的长度上限，即最大传送单元（Maximum Transfer Unit，MTU）。例如，以太网的MTU为1500个字节。

透明传输是指数据链路层对上层交付下来的协议数据单元PDU没有任何限制，就好像数据链路层不存在一样。

在上一部分不知道你有没有疑问，如果我指定了一个帧首尾部标识了帧的开始与结束，那么上一层传下来的数据中如果也包含了相同的字节，那么帧不就会提前被识别结束吗？所以在封装的时候要对原先数据进行一定加工

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

面向字节的物理链路

如果原先数据中包含 Flag，那么在之前加入转义字节，要表示转义字节，那么在转义字节前再加转义字节

面向比特的物理链路

3.2.2 差错检测¶

实际的通信链路都不是理想的，比特在传输过程中可能会产生差错（称为比特差错）

在一段时间内，传输错误的比特数量占所传输比特总数的比率称为误码率（Bit Error Rate，BER），使用差错检测技术来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一。负责差错检测的部分为 FCS

常用的一种校验方式如奇偶检验

奇校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为奇数。
偶校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为偶数。

奇偶校验一个很明显的缺点就是如果出现了偶数个位发生误码，那么就会出现漏检。

现在，最为广泛使用的差错检测技术为 循环冗余校验，其基本思想是

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

但是这些检测技术都只能检测出传输过程中出现了差错，但并不能定位错误，因此无法纠正错误。要想纠正传输中的差错，可以使用冗余信息更多的纠错码(例如海明码)进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用。

海明码

15位用四位作为校验位，从而可以定位哪一位出现了错误

3.2.3 可靠传输¶

使用差错检测技术（例如循环冗余校验CRC），接收方的数据链路层就可检测出帧在传输过程中是否产生了误码（比特差错），出现差错之后根据数据链路层向上提供的服务类型执行不同的操作

不可靠传输服务：仅仅丢弃有误码的帧，其他什么也不做；
可靠传输服务：通过某种机制实现发送方发送什么，接收方最终就能收到什么。

一般情况下，有线链路的误码率比较低。为了减小开销，并不要求数据链路层向其上层提供可靠传输服务。即使出现了误码，可靠传输的问题由其上层处理。

无线链路易受干扰，误码率比较高，因此要求数据链路层必须向其上层提供可靠传输服务。

当然，除了误码的问题之外，还有分组丢失，分组失序，分组重复会导致传输差错，这些都是数据链路层的上层出现的问题。针对可靠传输，介绍几个协议

停止-等待协议
回退N帧协议
选择重传协议

停止-等待协议的基本过程是发送方发送一个数据分组，然后接受方接受到数据之后进行差错检测，无误码则接受，向发送方发送确认分组，否则发送否认分组。

当然上述过程建立在数据不丢失的情况，当发生数据丢失时，情况会变得复杂。

如果发送方的数据出现了丢失，那么接收方收不到数据分组，就不会发送相应的 ACK 或 NAK。如果不采取措施，发送方就会一直处于等待接收方 ACK 或 NAK 的状态。为解决上述问题，发送方可在每发送完一个数据分组时就启动一个超时计时器（Timeout Timer）若到了超时计时器所设置的超时重传时间（Retransmission Time-Out，RTO），但发送方仍未收到接收方的 ACK 或 NAK，就重传之前已发送过的数据分组。

当 ACK 出现丢失的时候，那么发送方不知道上一个数据已经被接收方接受，那么超时之后就会重传相同数据，这页接收方就会重复得到数据，此时接收方会丢弃重复的数据分组。

还有一种情况就是 ACK 传回来的时候出现迟到，导致发送方重传相应数据，然后发送方接收到了迟到的 ACK，从而发送方发送下一组数据，那么发送方将无法识别下一次 ACK 是重传的数据还是下一组数据了。所以需要对 ACK 也要进行编号。

关于停止-等待协议的信道利用率，可以看到当 RTT 相对较大的情况下，信道利用率非常低，可以选择回退N帧（GBN）协议或选择重传（SR）协议。

Example

为解决 \(RTT>>T_D\) 导致信道利用率极低的情况，提出回退 N 帧协议。思想就是不传一个等一个，而是同时传很多个，传错了回退即可

在使用流水线传输方式时，发送方不能无限制地连续发送数据分组，否则可能会导致网络中的路由器或接收方来不及处理这些数据分组，进而导致数据分组的丢失，这实际上是对网络资源的浪费。

下面将阐述一下这个协议基本的工作流程：

采用n个比特给分组编序号，序号范围是 \(0\) ~ \((2^n−1)\)。本例假设采用3个比特给分组编序号，则序号范围是0~7。
发送方需要维护一个发送窗口 \(W_T\) ，在未收到接收方确认分组的情况下，发送方可将序号落入\(W_T\) 内的所有数据分组连续发送出去。
接收方需要维护一个接收窗口 \(W_R\)（只能是1），只有正确到达接收方（无误码）且序号落入\(W_R\) 内的数据分组才被接收方接收。

无差错的情况

这里 \(W_T\) 为 5，

然后接受方受到信息之后依次传出 ACK，\(W_R\) 向右移动

发送方接受到相应的 ACK, \(W_T\) 向右移动

当发送方发送多个帧后因超时未收到确认，就从第一个未被确认的帧开始，将其及之后的所有帧全部重传。

回退N帧协议的接收方采用累积确认方式：确认分组ACKn表明序号为n及之前的所有数据分组都已正确接收。

若\(W_T\)超过取值范围，例如 \(W_T\)= 8，会出现什么情况？

当数据块0超时了（ACK7还没到）打算重传，然后发现 \(W_R\) 已经在0了，那么就会继续接受，就无法分辨新旧数据分组了

例题1

例题2

回退 n 帧协议一个最大的问题就是一个数据块的错误需要同组后面所有数据块来买单。

选择重传协议允许接收方缓存失序到达的正确帧，发送方仅重传出错或丢失的帧，避免了GBN中“全部重传”的浪费，从而大幅提升信道利用率。

Example

3.3 点对点协议¶

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

点对点协议PPP主要有两种应用：用户接入（通过 PPPoE）和路由器间的广域网连接

下面是 PPP 的帧格式

标志（Flag）字段：PPP帧的定界符，取值为0x7E。
地址（Address）字段：取值为0xFF，预留（目前没有什么用）。
控制（Control）字段：取值为0x03，预留（目前没有什么作用）。
协议（Protocol）字段：其值用来指明帧的数据载荷应向上交付给哪个协议处理。
帧检验序列（Frame Check Sequence，FCS）字段：其值是使用循环冗余校验CRC计算出的检错码。

面向字节的异步链路使用字节填充来实现透明传输 [RFC1662]

数据载荷中出现的每一个 0x7E，减去 0x20（相当于异或0x20），然后在其前面插入转义字符0x7D。
数据载荷中出现的每一个 0x7D，则把每一个 0x7D 减去 0x20，然后在其前面插入转义字符 0x7D。
将数据载荷中出现的每一个ASCII码控制字符（即数值小于 0x20 的字符），加上 0x20（相当于异或 0x20，将其转换成非控制字符），然后在其前面插入转义字符 0x7D。

面向比特的同步链路使用零比特填充来实现透明传输

对帧的数据载荷进行扫描（一般由硬件完成），每出现5个连续的比特1，则在其后填充一个比特0。

上述阐述都是发送方的操作，对于接收方的操作，就只需要反着来做即可。

以用户主机拨号接入因特网服务提供者ISP的拨号服务器的过程为例阐述一下工作状态

3.4 共享式以太网¶

3.4.1 网络适配器¶

要将计算机连接到以太网，需要使用相应的网络适配器（Adapter），网络适配器一般简称为“网卡”。

在计算机内部，网卡与CPU之间的通信，一般是通过计算机主板上的I/O总线以并行传输方式进行。

网卡与外部以太网（局域网）之间的通信，一般是通过传输媒体（同轴电缆、双绞线电缆、光纤）以串行方式进行的。

网卡除要实现物理层和数据链路层功能，其另外一个重要功能就是要进行并行传输和串行传输的转换。由于网络的传输速率和计算机内部总线上的传输速率并不相同，因此在网卡的核心芯片中都会包含用于缓存数据的存储器。

在确保网卡硬件正确的情况下，为了使网卡正常工作，还必须要在计算机的操作系统中为网卡安装相应的设备驱动程序。驱动程序负责驱动网卡发送和接收帧。

3.4.2 MAC 地址¶

当多个主机连接在同一个广播信道上，要想实现两个主机之间的通信，则每个主机都必须有一个唯一的标识，即一个数据链路层地址。

在每个主机发送的帧的首部中，都携带有发送主机（源主机）和接收主机（目的主机）的数据链路层地址。由于这类地址是用于媒体接入控制（Medium Access Control，MAC）的，因此被称为MAC地址。

MAC地址一般被固化在网卡的电可擦可编程只读存储器 EEPROM 中，因此MAC地址也被称为硬件地址。有时也被称为物理地址。

一般情况下，普通用户计算机中往往会包含两块网卡：

一块是用于接入有线局域网的以太网卡
另一块是用于接入无线局域网的Wi-Fi网卡

每块网卡都有一个全球唯一的MAC地址。交换机和路由器往往具有更多的网络接口，所以会拥有更多的MAC地址。

Note

综上所述，严格来说，MAC地址是对网络上各接口的唯一标识，而不是对网络上各设备的唯一标识。

IEEE 802局域网的MAC地址格式

发送顺序是字节从第1字节到第6字节，然后字节内比特的发送顺序是 b0-b7

网卡从网络上每收到一个帧，就检查帧首部中的目的MAC地址，按以下情况处理：

如果目的MAC地址是广播地址（FF-FF-FF-FF-FF-FF），则接受该帧。
如果目的MAC地址与网卡上固化的全球单播MAC地址相同，则接受该帧。
如果目的MAC地址是网卡支持的多播地址，则接受该帧。
其余情况均丢弃该帧

混杂方式

网卡还可被设置为一种特殊的工作方式：混杂方式（Promiscuous Mode）。工作在混杂方式的网卡，只要收到共享媒体上传来的帧就会收下，而不管帧的目的MAC地址是什么。

对于网络维护和管理人员，这种方式可以监视和分析局域网上的流量，以便找出提高网络性能的具体措施

3.4.3 CSMA/CD协议¶

在以太网的发展初期，人们普遍认为“无源的电缆线比有源器件可靠”，因此将多个站点连接在一条总线上来构建共享总线以太网。

共享总线以太网具有天然的广播特性，即使总线上某个站点给另一个站点发送单播帧，表示帧的信号也会沿着总线传播到总线上的其他各站点。

当某个站点在总线上发送帧时，总线资源会被该站点独占。此时，如果总线上的其他站点也要在总线上发送帧，就会产生信号碰撞。

所以自然而然地引出了共享总线以太网的一个重要问题：如何协调总线上的各站点争用总线。

为了解决各站点争用总线的问题，共享总线以太网使用了一种专用协议 CSMA/CD，它是载波监听多址接入/碰撞检测（Carrier Sense Multiple Access Collision Detection）的英文缩写词。

载波监听检测到总线空闲，但总线并不一定空闲。存在传播延迟

使用 CSMA/CD 协议的共享总线以太网上的各站点，只是尽量避免碰撞并在出现碰撞时做出退避后重发的处理，但不能完全避免碰撞。

在使用 CSMA/CD 协议时，由于正在发送帧的站点必须“边发送帧边检测碰撞”，因此站点不可能同时进行发送和接收，也就是不可能进行全双工通信，而只能进行半双工通信（双向交替通信）。【注意这里只有在发送的时候才进行碰撞检测】

Warning

发送帧的站点一旦检测到碰撞，除了立即停止发送帧外，还要再继续发送32比特或48比特的人为干扰信号（Jamming Signal），以便有足够多的碰撞信号使所有站点都能检测出碰撞。

某个站点从发送帧开始，最长要经过多长时间，才能检测出自己发送的帧与其他站点发送的帧产生了碰撞？

只需要考虑最极端的情况，当一个信号从一端传到另一端，就当要传到的时候发生了碰撞，这时返回来才知道发生了碰撞。设以太网单程端到端传播时延 \(\tau\) ，那么最多经过时长 \(2τ\) 就可检测出所发送的帧是否遭遇了碰撞。因此，共享总线以太网的端到端往返时间 \(2τ\) 被称为争用期（Contention Period）或碰撞窗口（Collision Window）

Note

10Mb/s 共享总线以太网（传统以太网）规定：争用期 \(2τ\) 的值为 512 比特的发送时间，即 51.2 \(μs\) 。

共享总线以太网规定：总线长度不能超过2500m。

如果一个帧过短，那么在发送时延很短，就可能已经发送完了却与其他帧发生了碰撞，就会导致发送端并未检测到碰撞，从而就不会重发该帧了。

所以为了确保共享总线以太网上的每一个站点在发送完一个完整的帧之前，能够检测出是否产生了碰撞，帧的发送时延就不能少于共享总线以太网端到端的往返时间，即一个争用期 \(2τ\) 。也就是说最小的帧长为 512b，即 64B

当某个站点在发送帧时，如果帧的前 64B 没有遭遇碰撞，那么帧的后续部分也就不会遭遇碰撞。也就是说，如果遭遇碰撞，就一定是在帧的前 64B 之内。由于发送帧的站点边发送帧边检测碰撞，一旦检测到碰撞就立即中止帧的发送，此时已发送的数据量一定小于 64B。因此，接收站点收到长度小于 64B 的帧，就可判定这是一个遭遇了碰撞而异常中止的无效帧，将其丢弃即可。

为了防止帧过长导致长时间占用信道，帧的最大长度也做限制（1500B）

在使用CSMA/CD协议的共享总线以太网中，正在发送帧的站点一边发送帧一边检测碰撞，当检测到碰撞时就立即停止发送，退避一段随机时间后再重新发送。共享总线以太网中的各站点采用截断二进制指数退避（Truncated Binary Exponential Backoff）算法来选择退避的随机时间。

\[ 退避时间 = 2\tau \times 随机数 r \]

其中 \(r\) 从离散的整数集合\(\{0,1,…,(2^k−1)\}\)中随机选出一个数，\(k=\min⁡[重传次数，10]\)

如果连续多次发送碰撞，就表明可能有较多的站点参与竞争信道。但使用上述退避算法可使重传需要推迟的平均时间随重传次数而增大（即动态退避），因而减小产生碰撞的概率。

当重传达16次仍不能成功时，就表明同时打算发送帧的站点太多，以至于连续产生碰撞，此时应放弃重传并向高层报告。

下面探究共享式以太网的信道利用率，考虑以下理想情况：

总线一旦空闲就有某个站点立即发送帧
各站点发送帧都不会产生碰撞
发送一帧占用总线的时间为 \(T_0+τ\)，而帧本身的发送时间是 \(T_0\)

那么极限信道利用率为

\[ S_{max} = \frac{T_0}{T_0+\tau} = \frac{1}{1+\frac{\tau}{T_0}} = \frac{1}{1+\alpha} \]

所以想要提高极限信道利用率，就要让 \(\alpha\) 的值尽可能小，也就是说

共享总线以太网端到端的距离不应太长（让 \(\tau\) 减小）
帧的长度应尽量大（让 \(T_0\) 增加）

3.4.4 使用集线器的共享式以太网¶

事实上无源电缆线和大量机械接口的总线型以太网并不像人们想象的那么可靠，若总线上的某个机械连接点接触不良或断开，则整个网络通信就不稳定或彻底断网。

在使用细同轴电缆的共享总线以太网之后，以太网发展出来了一种使用大规模集成电路来替代总线、并且可靠性非常高的设备，叫作集线器（Hub）。

使用集线器的以太网虽然物理拓扑是星型的，但在逻辑上仍然是一个总线网。总线上的各站点共享总线资源，使用的还是 CSMA/CD 协议。【工作逻辑是相同的】
集线器只工作在物理层，它的每个接口仅简单地转发比特，并不进行碰撞检测。碰撞检测的任务由各站点中的网卡负责。
集线器一般都有少量的容错能力和网络管理功能。例如，若网络中某个站点的网卡出现了故障而不停地发送帧，集线器可以检测到这个问题，在内部断开与出故障网卡的连线，使整个以太网能正常工作

Note

IEEE于1990年制定了10BASE-T星型以太网的标准802.3i，这种以太网是局域网发展史上的一座非常重要的里程碑，它为以太网在局域网中的统治地位奠定了牢固的基础。【10 代表传输速率为 10Mb/s, BASE 代表采用基带信号进行传输，T 代表采用双绞线作为传输媒体，如果是 F 的话代表光纤】

3.4.5 在物理层扩展以太网¶

一方面是扩展站点与集线器之间的距离

共享总线以太网中两站点之间的距离不能太远，否则它们之间所传输的信号就会衰减到使CSMA/CD协议无法正常工作。

在早期广泛使用粗同轴电缆或细同轴电缆共享总线以太网时，为了提高网络的地理覆盖范围，常用的是工作在物理层的转发器。

随着使用双绞线和集线器的 10BASE-T 星型以太网成为以太网的主流类型，扩展网络覆盖范围就很少使用转发器了。限常使用光纤和一对光纤调制解调器来扩展站点与集线器之间的距离

另一方面是扩展共享式以太网的覆盖范围和站点数量

以太网集线器一般具有8~32个接口，如果要连接的站点数量超过了单个集线器能够提供的接口数量，就需要使用多个集线器，这样就可以连接成覆盖更大范围、连接更多站点的多级星型以太网。采用多个集线器连接而成的多级星型以太网，在扩展了网络覆盖范围和站点数量的同时，也带来了一些负面因素。【相当于形成树一样的结构】

在物理层扩展的共享式以太网仍然是一个碰撞域，不能连接太多的站点，否则可能会出现大量的碰撞，导致平均吞吐量太低。

3.4.6 在数据链路层扩展以太网¶

使用网桥在数据链路层扩展以太网，网桥工作在数据链路层，比集线器懂的更多

网桥可以识别帧的结构
网桥可以根据帧首部中的目的MAC地址和网桥自身的帧转发表来转发或丢弃所收到的帧。

网桥中很重要的一个部分就是转发表，用于连接两边的站点。

那么转发表又是如何建立的呢？

透明网桥（Transparent Bridge）通过自学习算法建立转发表。透明网桥中的“透明”，是指以太网中的各站点并不知道自己所发送的帧将会经过哪些网桥的转发，最终到达目的站点。也就是说，以太网中的各网桥对于各站点而言是看不见的。

整个自学习的过程如下

网桥收到帧后进行登记（即自学习），登记的内容为帧的源MAC地址和进入网桥的接口号。
网桥根据帧的目的MAC地址和网桥的转发表对帧进行转发，包含以下三种情况：
明确转发：网桥知道应当从哪个接口转发帧。
盲目转发：网桥不知道应当从哪个接口转发帧，只能将其通过除进入网桥的接口外的其他所有接口转发。
丢弃：网桥知道不应该转发该帧，将其丢弃。

Warning

如果网桥收到有误码的帧则直接丢弃。
如果网桥收到一个无误码的广播帧，则不用进行查表，而是直接从除接收该广播帧的接口的其他接口转发该广播帧。
转发表中的每条记录都有其有效时间，到期自动删除！这是因为各站点的MAC地址与网桥接口的对应关系并不是永久性的，例如某个站点更换了网卡，其MAC地址就会改变。

为了提高以太网的可靠性，有时需要在两个以太网之间使用多个透明网桥来提供冗余链路。但是增加冗余链路却给网络引入了环路，网络中广播帧将在环路中永久兜圈，造成广播帧充斥整个网络，网络资源被白白浪费，而网络中的主机之间无法正常通信！

为了避免广播帧在环路中永久兜圈，透明网桥使用生成树协议（Spanning Tree Protocol，STP），可以在增加冗余链路提高网络可靠性的同时，又避免环路带来的问题。

不管网桥之间连接成了怎样复杂的带环拓扑，网桥之间通过交互网桥协议单元（Bridge Protocol Data Unit，BPDU），找出原网络拓扑的一个连通子集（即生成树），在这个子集里整个连通的网络中不存在环路。

3.5 交换式以太网¶

网桥的接口数量很少，通常只有2~4个，一般只用来连接不同的网段。

交换式集线器（Switching Hub），实质上是具有多个接口的网桥，常称为以太网交换机（Switch）或二层交换机。

仅使用交换机（而不使用集线器）的以太网就是交换式以太网。

交换机的每个接口可以连接计算机，也可以连接集线器或另一个交换机。

当交换机的接口与计算机或交换机连接时，可以工作在全双工方式，并能在自身内部同时连通多对接口，使每一对相互通信的计算机都能像独占传输媒体那样，无碰撞地传输数据，这样就不需要使用CSMA/CD协议了。
当交换机的接口连接的是集线器时，该接口就只能使用CSMA/CD协议并只能工作在半双工方式。
现在的交换机和计算机中的网卡都能自动识别上述两种情况，并自动切换到相应的工作方式。