数据链路层 Data Link Layer

数据链路层设计要点

数据链路层属于计算机网络的底层。

物理层实现了比特流的传输，数据链路层在其基础上实现了帧 (frame) 的传输。

数据链路层传输的协议数据单元 (Protocol Data Unit, PDU) 是帧。数据链路层把网络层交下来的数据构成帧发送到链路上，以及把接收到的帧中的数据取出并上交给网络层。

数据链路层使用的信道类型

点对点信道

这种信道使用一对一的点对点通信方式。

广播信道

这种信道使用一对多的广播通信方式。广播信道上连接多个主机，必须采用专门的共享信道协议来协调数据发送。

数据链路层涉及的问题

成帧 (framing)

怎么组成帧、怎么使接收方识别帧

错差控制

帧在传输过程中出错的检测

流量控制及可靠传输

仅是数据链路层的选项

广播信道中的介质访问控制

如何使众多用户能够合理且方便地共享通信媒体资源

成帧方法

主要解决接收方如何识别帧的边界问题。常用的成帧方法有：

字符计数法

在帧头部字段中指明本帧的字节数，接收方通过该字段得知该接受多少字节。

字符填充的首尾定界法

定义专门的字符作为帧的起始/结束标志，并使用字符填充方式将标志字符与数据区分开来。

比特填充的首尾定界法

定义专门的比特序列作为帧的起始/结束标志，并使用比特填充方式将标志序列与数据区分开来。

物理编码违例法

使用无效的物理编码作为帧的起始/结束标志，供接收方识别。

错误检测和纠正

任何通信链路在传输数据时都有可能出错，一般用误码率 (Bit Error Rate, BER) 表示链路可靠性：

误码率 = 出错的比特数 / 传送的总比特数。

当误码率为 $10^{-10}$ ，表示平均每传送 $10^{10}$ 个比特就会出现一个比特出错。

检错编码 (Error detecting code)

可检测错误的编码，以重传处理。

由于信道的误码率通常都比较低，出错属于小概率事件，因此发现出错的时候只需重传即可，使用检错编码就更有性价比。

常用的检错编码方法有：

奇偶校验

简单累加和（校验和）

循环冗余校验 (Cyclic Redundancy Check, CRC)

发送方：把数据划分成组，设每组 k 个比特，在其后添加供差错检测用的 n 位冗余码，再将 (k+n) 比特一起发送。

接收方：对收到的 (k+n) 比特计算冗余码，结果为 0 表示传输正确，否则表示传输错误。

纠错编码 (Error correcting code)

可检测错误，并且纠正错误的编码。

这类编码看似很好，但实际应用的代价比较高，因为需要为了纠正错误腾出更多冗余比特，成本更高。

基本数据链路协议

基本数据链路协议有无限制的单工协议、单工停-等协议以及有噪声信道的单工协议。

无限制的单工协议

其假设前提有：

此协议未考虑接收方的处理速度，像是发送方发送的速度大于接收方的处理速度。

单向传输，即发送方向接收方传输数据，接收方不需要反向的传输数据。
理想信道，即通信是没有错误的。
发送方总有数据发送，并且接收方总能及时处理所收到的数据。

单工停-等协议 (stop-and-wait)

按照无限制的单工协议，如果接收方的处理速度不及发送方，则可能出现帧丢失的情况。因此就有了解决方法，增加流量控制 (Flow control) 机制，得到单工停-等协议。

虽然这个协议考虑了接收方的处理速度，但其未考虑传输出错的问题。

接收方每收到一帧，都向发送方返回一个应答帧。而发送方每发送一帧，都等待来自接收方的应答帧，之后才发送下一帧。

有噪声信道的单工协议

在有噪声信道中，帧在传输过程中是有可能出错的，此问题的解决方法为 ARQ 协议。

ARQ 协议的原理要点有：

校验和，使接收方能够检测帧是否出错
确认帧，使发送方知道帧已被正确接收
超时重发，发送方在规定时间内未收到确认帧，则重发帧
帧序号，保证接收方不会重复接收帧

协议设计时，需要考虑的三种情形：

数据帧被正确接收

接收方返回确认帧，发送方收到后继续发送下一帧。

数据帧出错或丢失

接收方未收到帧或校验出错丢失该帧，发送方等待确认帧超时后，重新发送数据帧。

确认帧出错或丢失

发送方未收到有效的确认帧，重发数据帧。接收方收到后，检测到帧序号重复，不上交该帧，仅返回确认帧。

滑动窗口协议

传输链路存在时延，ARQ 协议在同一时刻仅有一个帧在链路上传输，导致其对信道的利用率较低，特别是传输时延较长的时候。

利用率 $U = T_D~/~(T_D~+~RTT~+~T_A)$

$T_D$ ：发送数据帧的时间， $RTT$ ：往返时延 / 环路时延， $T_A$ ：发送应答帧的时间

滑动窗口协议原理

滑动窗口协议的基本思想是允许发送方连续发送多个帧，并通过滑动窗口实现流量控制。

发送方，发送窗内的序列号代表允许它发送的帧。窗口内最大的序列号成为窗口上边界、上沿或前沿。窗口内最小的序列号成为窗口下边界、下沿、后沿。每当从网络层得到一个数据包，将其组成帧发出后，发送窗口的上边界将 +1。发送窗口下边界的帧被接收方确认后，发送窗口的下边界将 +1。

接收方，接收窗口内的序列号代表可以接受的帧。收到的帧序列号等于窗口下边界时，将该帧上交网络层，并返回确认帧，同时整个窗口向前移动 1 个位置。如果收到帧序列号落在接收窗口之外，则将其丢弃。

后退N帧的滑动窗口协议

当某帧出错时，该帧之后的帧全部被丢弃，从出错帧开始重新发送。

选择性重传的滑动窗口协议

当某帧出错时，只选择性重发该帧，该帧之后发送的帧会先由接收方在数据链路层缓冲，收到重发的出错帧之后再上交给网络层。

ACKn 表示 n 及 n 之前的帧均已被正确接收

当接收方检测到出错帧时，会发送一个否定的确认帧 (Negative Acknowledgement, NAK)。这样的好处是，发送方可以尽快重发出错帧，不必等到超时。

点对点协议 PPP

PPP 全称为 Point-to-Point Protocol，是一种数据链路层协议，广泛应用于点到点链路的数据传输。

PPP 协议的特点

PPP 协议有三个组成部分，分别是：

将 IP 数据封装到串行链路的方法
用来建立、配置和测试数据链路连接的链路控制协议 Link Control Protocol LCP
一套网络控制协议 Network Control Protocol NCP

PPP 的帧格式

零比特填充

属于同步传输，如 SONET / SDH。

发送端：只要发现有 5 个连续 1，则立即填入一个 0。

接收端：对帧中的比特流进行扫描，每当发现 5 个连续 1 时，就把这 5 个连续 1 后的一个 0 删除。

字符填充

属于异步传输。

发送端：

信息字段（载荷）中的每一个 0x7E 转换成 0x7D, 0x5E。

信息字段中的每一个 0x7D 转换成 0x7D, 0x5D。

信息字段中的每一个 ASCII 码控制字符（小于 0x20 的字符）前面都加入 0x7D，且编码改变。如 0x03 转换成 0x7D, 0x23。

接收端：

在收到数据后进行与发送端字节填充相反的变换，即可正确恢复原来的信息。

PPP 协议的工作状态

鉴别状态中，若鉴别成功，则进入网络层协议 (Network-Layer Protocol)。否则进入链路终止状态 (Link Terminate)。

PPP支持两种身份认证协议，即：

口令鉴别协议 PAP (Password Authentication Protocol)

若使用 PAP，则需要发起通信的一方发送身份标识符和口令。

口令握手界别协议 CHAP (Challenge-Handshake Authentication Protocol)

若需要更好的安全性，则使用更加复杂的 CHAP。

介质访问控制 (Media Access Control, MAC)

广播信道可以进行一对多的通信，而局域网使用的就是广播信道。局域网是在 20 世纪 70 年代末发展起来的。局域网技术在计算机网络中占有非常重要的地位。

局域网的数据链路层

局域网最主要的特点是，网络为一个单位所拥有，且地理范围和站点数目均有限。

其优点有：

具有广播功能，从一个站点可以很方便的访问全网。局域网上的主机可共享连接在局域网上的各种硬件和软件资源。
便于系统的扩展和逐渐地演变，各设备的位置可灵活调整和改变。
提高了系统的可靠性、可用性和生存性。

局域网可按拓扑进行分类，其中有星形网、环形网及总线网。

由于局域网通常使用广播信道，可能会有多个主机同时访问信道。共享信道要着重考虑的问题是如何使众多用户能够合理且方便地共享通信媒体资源，因此就有了介质访问控制技术。其中有两种方法：

静态划分信道

有如频分复用、时分复用、波分复用以及码分复用。用户只要分配到了信道，就不会与其他用户发生冲突。但这种划分信道的方法代价较高，不适用于局域网。

动态介质访问控制 / 多点访问

其特点是信道并非在用户通信时固定分配给用户，分为以下两类：

随机访问

所有用户可随机发送信息。但如果有两个或更多的用户在同一时间发送信息，就会产生碰撞。因此，必须有解决碰撞的网络协议。经典的协议有：CSMA/CD、CSMA/CA等。

受控访问

用户不能随机发送信息，而必须服从一定的控制，局域网中使用较少。经典代表有：分散控制的令牌环局域网和集中控制的多点线路探询，或轮询。

CSMA/CD 协议

全称为载波监听多点访问/碰撞检测 Carrier Sense Multiple Access with Collision Detection，是一种随机访问协议，也是以太网的核心，非常重要。

其优点：

网络负载较低时，效率高。
硬软件实现简单、灵活。

其缺点：

网络负载较重时，碰撞发生的概率增大，网络效率较低。
由于存在多次冲突的可能，数据从发送方到接收方的时间没有保证，即实时性较差。

载波监听

发送前先听：结点在发送数据之前会先检测一下，总线上是否有其他结点正在发送数据。若有则暂时不发送数据，以免发生碰撞。

碰撞检测

由于线路的传播时延，单纯靠载波监听并不能完全避免碰撞。有发生碰撞时，两个或更多的信号在总线上相互叠加，会导致无法识别。

边发送边听：结点边发送数据边检测信道上是否发生了碰撞。

碰撞强化

发送方检测到碰撞后，立刻停止发送，并发送 32 或 48bit 的人为干扰信号 (jamming signal)，以便让所有用户都知道已经发生了碰撞。

碰撞退避

碰撞后，结点将等待一段时间，再重新开始载波检测和发送操作。为了避免退避后再次碰撞，冲突各方的等待时间就应该各不相同。因此，以太网采用了截断二进制指数退避算法 (truncated binary exponential backoff)。

截断二进制指数退避算法的特点有：

退避时间： $T=2\tau \times$ 倍数
倍数：在 $0,1,\dots,2^k - 1$ 中取随机数，其中 k = min(重传次数, 10)。
重传次数超过 16 后，则丢弃该帧，并向上层报告。

争用期

一个站点开始发送数据后，最多经过时间 $2\tau$ ，就可以知道是否发生了碰撞。如果经过争用期还没检测到碰撞，就可以肯定这次发送不会发生碰撞。

以太网争用期

以太网的端到端往返时延 $2\tau$ 称为争用期，或碰撞窗口。其争用期长度为 $51.2~\mu s$ 。

对于 10Mb/s 以太网，在争用期内可发送 512 bit，即 64 字节。因此在发送数据时，若前 64 字节未发生碰撞，就不会发生碰撞。根据此规定，以太网帧长 $\ge$ 64 字节，长度小于 64 字节的帧为无效帧。

局域网技术标准

IEEE802 标准将局域网的数据链路层分为两个子层，分别是：

逻辑链路控制子层 (Logic Link Control, LLC)

逻辑链路控制子层，是局域网中数据链路层的上层部分，用户的数据链路服务透过 LLC 子层为网络层提供统一的接口。在 LLC 子层下面是 MAC 子层。

介质访问控制子层 (Media Access Control, MAC)

介质访问控制子层，是局域网中数据链路层的下层部分，提供定址及媒体存取的控制方式，使得不同设备或网络上的结点可以在多点的网络上通讯，而不会互相冲突。

以太网

IEEE802 委员会的 802.3 工作组于 1983 年制定了第一个 IEEE 的以太网标准 IEEE802.3，数据率为 10Mb/s。DIX Ethernet V2 与 IEEE802.3 标准只有很小的差别，因此有很多人常把 802.3 局域网简称为以太网。但严格来说，以太网应该是指符合 DIX Ethernet V2 标准的局域网。

曼彻斯特 (Manchester) 编号

二进制基带数字信号通常是高、低电压交替出现的信号。当信号出现一长串连续的 0 或 1 时，接收端就无法从收到的比特流中取位同步信号。

曼彻斯特编码的编码方法就是把每一个码元分成两个相等的间隔，码元 1 是前一个间隔为低电压而后一个间隔为高电压。码元 0 则正好相反，从高电压转为低电压。这样保证每个比特的正中间都出现一次电压转换，接收端就可以利用这种电压的转换把位同步信号提取出来。

以太网物理层

最初的以太网为总线结构，采用 $50\Omega$ 同轴电缆，传输速率为 10Mbps。

其缺点是：

同轴电缆成本较高
总线上单点故障会导致全网瘫痪。网络中结点数较多时，可靠性较差，且维护困难。

后来发展为采用更便宜和灵活的非屏蔽双绞线，使用集线器 (HUB) 连接各个结点，物理上呈星形结构。集线器就很像一个多接口的转发器，工作在物理层。使用集线器的以太网在逻辑上仍然是一个总线网。这种技术称为 10BASE-T。

10：10Mbps，BASE：基带传输，T：双绞线 (Twisted pair)

以太网的 MAC 层

以太网采用 CSMA/CD 介质访问控制协议。所有的结点都会被分配一个按照 IEEE802.3 标准，且唯一的 MAC 地址。该地址为 48bit，高 24bit 为厂商标识符，低 24bit 由厂商自行分配，且必须保证每个网络接口具有全球唯一的 MAC 地址。

当一个结点发送数据时，由于以太网的总线结构，总线上的所有结点都能收到帧。因此就需要一个适配器 (Adapter) 在每收到一个帧的时，就检查帧中的目的 MAC 地址。如果是发往本站的帧则进行处理，否则丢弃。

发往本站的帧包括以下三种帧：

单播帧 / 一对一 (Unicast)

广播帧 / 一对全体 (Broadcast) — MAC 地址为全 1 就表示广播

组播 / 多播 / 一对多 (Multicast)

以太网的帧格式（5个字段）

每个帧在发送时，前面都会插入 8 个字节。其中前 7 个字节用于比特同步，后 1 字节为帧起始标志。由于以太网采用曼彻斯特编码，每个比特均有电平跳变，因此无电平跳变就表示总线空闲。

目的地址

6 字节，接收方的 MAC 地址。

源地址

6 字节，发送方的 MAC 地址。

类型

2 字节，标明上层协议类型，例如 0x0800 表示 IP 包。

数据

网络层数据报，长度为 46 ~ 1500 字节。最小为 46 字节是由以太网有效帧的最小长度 64 字节，扣除目的地址、源地址、类型及 FCS 计算出来的，即 64 - 6 - 6 - 2 - 4 = 46 字节。

帧校验序列 (Frame Checksum, FCS)

4 字节，帧校验序列，采用 CRC 校验。

快速以太网 (Faster Ethernet)

其标准为 IEEE802.3u，传输速率为 100Mb/s，其使用 8 芯非屏蔽双绞线中的 4 条芯，其中 2 条用以发送，2 条用以接收。这使其可在全双工方式下工作而无冲突发生，因此 CSMA/CD 协议对全双工方式工作的快速以太网就不起作用了。

其使用的 MAC 帧格式仍然是 IEEE802.3 标准规定的帧格式，最短的帧长也保持不变。由于传输速率有所提升，争用期有所缩短，导致一个网段的最大电缆长度减小至 100m。

快速以太网的物理层标准有：

100BASE-TX

使用媒体为铜缆，网段的最大电缆长度为 100m，特点是使用 2 对 UTP 5 类线或屏蔽双绞线 STP。

100BASE-T4

使用媒体为铜缆，网段的最大电缆长度为 100m，特点是使用 4 对 UTP 3 类线或 5 类线。

100BASE-FX

使用媒体为光缆，网段的最大电缆长度为 2000m，特点是两根光纤，发送与接收个一根。

千兆以太网 / 吉比特以太网 (Gigabit Ethernet)

其标准为 IEEE802.3z，传输速率为 1Gb/s，其迅速占领市场，成为以太网的主流产品。

吉比特以太网的标准 IEEE802.3z 有以下几个特点：

允许在 1Gb/s 下以全双工和半双工两种方式工作。
仍使用 IEEE802.3 协议规定的帧格式。
在半双工方式下使用 CSMA/CD 协议，全双工方式则不使用。
支持自适应，与 10BASE-T 和 100BASE-T 技术向后兼容。

吉比特以太网的物理层标准有：

1000BASE-SX

使用媒体为光缆，网段的最大电缆长度为 550m，特点是采用多摸光纤。

1000BASE-LX

使用媒体为光缆，网段的最大电缆长度为 5000m，特点是采用单模光纤及多摸光纤。

1000BASE-CX

使用媒体为铜缆，网段的最大电缆长度为 25m，特点是使用 2 对屏蔽双绞线电缆 STP。

1000BASE-T

使用媒体为铜缆，网段的最大电缆长度为 100m，特点是使用 4 对 UTP 5 类线。

万兆以太网 / 10 吉比特以太网 (10Gbps Ethernet)

其标准为 IEEE802.3ae，传输速率为 10Gb/s，只使用光纤传输。

其使用的 MAC 帧格式仍然是 IEEE802.3 标准规定的帧格式，并保留了 802.3 标准规定的以太网最小帧长与最大帧长。由于万兆以太网仅工作在全双工方式，不存在争用问题，也就不使用 CSMA/CD 协议。因此其传输距离大大提高，不再受限于争用期。

局域网互连

在物理层扩展局域网

使用中继器 (repeater) 或集线器 (HUB)，可实现局域网在物理层的互连。

中继器和集线器都工作在网络的物理层。

其优点是，可以方便地实现网络的扩展，并且成本较低。

而缺点则是，碰撞域增大，碰撞发生概率增大，可能会影响网络性能。

在数据链路层扩展局域网

使用网桥 (bridge) ，可实现局域网在数据链路层的互连。

网桥工作在网路的数据链路层。

网桥的基本工作原理是根据 MAC 帧的目的地址对收到的帧进行转发，即其具有过滤帧的功能。当收到一个帧时，会先检查帧的目的 MAC 地址，确定将该帧转发到哪一个接口，而非向所有的接口转发。

转发表是由交换机根据自学习算法建立的。

其优点是，可过滤通信量、增大吞吐量，因为各网段都是独立的碰撞域。同时，其扩大了物理范围，可互连不同物理层、不同 MAC 子层和不同速率的局域网，提高了可靠性。

其缺点是，其存储转发的方式增加了时延，并且在 MAC 子层并没有流量控制功能。因此网桥只适用于用户数不太多和通信量不太大的局域网，因为若某个站点频繁发送广播帧（MAC 地址全为 1 的帧）时，就会产生网络拥塞，即广播风暴。

多接口网桥 — 交换机 Switch

早期称为交换式集线器 (switching hub)，通常有十几道几十个网络接口，每个接口可连接主机或其他交换机。其内部工作原理为网桥，每一个网络接口被视为一个网段，因此交换机是一个多接口网桥。其按照自学习算法建立转发表，原理是若从 A 出发的帧从接口 x 进入到某网桥，则从这个接口出发沿相反方向一定可以把一个帧传送到 A。

由于每一个网络接口被视为一个网段，并且每个接口都独享宽带，因此可以大幅提高网络性能。集线器则由所有接口共享传输介质的带宽。

交换机的自学习过程

交换机初始时转发表为空，通过自学习逐步建立。

交换机在收到一个帧后，会先进行自学习，检查帧中源地址在交换表中是否存在。若不存在，则在交换表中添加一项，记录源地址和进入交换机的接口。

然后转发帧，根据收到的帧中的目的地址在交换表中查找。若找到，则对应的接口为转发接口。若找不到，则向除进入接口外的所有接口转发，再根据目的地址返回的应答帧进行相应记录。

透明网桥还使用生成树算法 (spanning tree)

其用途是，当多个局域网互连形成环路时，避免帧无休止转发。所使用的方法为建立生成树，即互连在一起的网桥彼此通信后，能找出网络拓扑的一个子集。在该子集中，整个连通的网络不存在回路，即在任何两个站之间只有一条路径。

但考虑到网络拓扑的动态变化，生成树必须定期更新。

虚拟局域网 Virtual LAN

虚拟局域网，是在现有局域网的基础上，通过将网络站点分组，构成若干个逻辑上独立的虚拟局域网。其用途是，便于管理、控制广播风暴以及安全性等。

帧不会在两个虚拟局域网之间自动转发，包括广播帧。这样，虚拟局域网限制了接收广播信息的计算机数，使得网络不会因为传播过多的广播信息而引起性能恶化。

IEEE 批准了 802.3ac 标准，定义了以太网的帧格式的扩展，以便支持虚拟局域网。虚拟局域网允许在以太网的帧格式中插入一个 4 字节的标识符，称为 VLAN 标记 (tag)，用来指明发送该帧的计算机术语哪一个虚拟局域网。而插入 VLAN 标记得出的帧，就称为 802.1Q 帧。