# 数据链路层的设计要点

数据链路层的设计要点 (Design Issues) 包括：

1. 如何将数据封装成帧 (framing)
2. 如何进行差错控制 (error control), 即检测并纠正错误的数据。
3. 如何处理发方和收方的数据传输速率不匹配问题，即流量控制 (flow control).

# 向网络层提供的服务

数据链路层向网络层提供虚拟通信服务，最终通过物理层实现数据通信。提供的服务包括：

1. 无确认、无连接的服务 (Unacknowledged connectionless service): 不需要对发送的帧进行确认，也不需要提前建立逻辑链接。其适用于固有可靠性较高的网络，例如以太网 (Ethernet).
2. 有确认、无连接的服务 (Acknowledged connectionless service): 不需要提前建立逻辑链接，但发送的每一个帧都需要单独确认。其适用于不可靠的信道，例如 IEEE 802.11(WiFi).
3. 有确认、有连接的服务 (Unacknowledged connection-oriented service): 既需要进行帧确认，又需要提前进行逻辑链接。发送数据的过程包括三个阶段：建立连接 (establish the connection), 传输数据 (transfer data), 解除连接 (release the connection). 每一个发送的数据帧需要编号，这样可以确认每帧恰被接收一次，且依照正确的顺序被接收。其适用于长距离、不可靠的信道，例如卫星信道和长距离电话线路。

# 封装成帧

封装成帧过程需要解决两个问题:

• 帧的边界 (boundary) 确定
• 帧的透明传输

在以上两个任务的驱动下，产生了以下四种封装成帧的方法：

1. 字节计数法 (Byte count): 在帧头部采用一个字段表明帧内字节数 (含自身)。当一个帧头部出现差错后，其后的帧可能全部出现差错，且纠错困难，很少使用。
2. 字节填充的标志字节法 (Flag bytes with byte stuffing): 定义一个标志字节 (Flag byte) 表示帧的开始和结束。如果在传输的数据中出现标志字节，则加入一个转义符 (Escape Byte, ESC) 进行表示。即数据中的 FLAG 表示为 ESC FLAG , 数据中的 ESC 表示为 ESC ESC . 该方法在 PPP 协议中使用。
3. 比特填充的标志比特法 (Flag bits with bit stuffing): 帧长度的最小单位为比特而非字节。帧开始和结束的标志为一个比特串: 01111110 即 0x7E. 为实现透明传输，发送端将传输数据中的任 5 个连续的 1 后都插入 1 个 0. 接收端将 5 个连续的 1 后的第一个 0 删去。若出现 6 个连续的 1, 则认为达到了帧的末尾。其在 HDLC 协议中使用。
4. 物理层编码违例法 (Physical layer coding violations): 该做法没有实现完全的透明传输，而是将常规数据中不常用的比特组合作为标志位。因此其称之为 “违例” 法。其不十分常用。

# 差错控制

差错控制 (error control) 需要解决的问题是：如何确定所有的帧都被接收端按正确的顺序全部接收了。否则，其可能出现的错误包括：帧丢失、帧重复和帧失序。

应对以上方式采用的策略包括：

• 计时器 (timers) 和重传 (retransmission): 用来检测帧是否在信道上丢失。
• 顺序编号 (Sequence Numbers for each frame): 用来检测帧是否丢失，并检测帧的接收顺序是否出现问题。

# 可靠通信的实现

根据以上的策略，我们可以在不可靠的信道上实现可靠通信。其传输步骤如下：

1. 发送端发送数据帧$M_1$ 并启用计时器.
2. 接收端接收$M_1$ 后进行确认.
3. 若发送端未收到$M_1$ 的确认信号，则在一定时间后重传$M_1$, 即超时重传。 此过程称为确认丢失。
4. 若发送端在重新发送$M_1$ 后收到了此前的$M_1$ 的确认信号，则不再考虑。此过程称为确认迟到。

以上的可靠传输协议称为自动重传请求 (Automatic Repeat reQuest, ARQ).

# 流量控制

当发送方发送的数据远超接收方可以接收的数目时，接收方会出现帧丢失等情况。此时需要进行流量控制。流量控制有两种最基本的策略：

• 基于反馈的流量控制 (feedback-based flow control)
• 基于速率的流量控制 (rate-based flow control)

# 错误检测和纠正

当信道受到干扰等以外情况发生时，帧中的数据可能出现一位或数位的错误。对于这种情况，我们采用错误检测和错误纠正的方式予以应对。

其中，错误检测 (Error Detection) 即检查传输过程中是否发生错误。是一般采用的方法。其技术主要包括

• 奇偶校验 (parity)
• 校验和 (checksums)
• 循环冗余检验 (cyclic redundancy checks, CRC)

错误纠正 (Error Correction) 不仅要求检查传输过程中是否发生错误，还要求将错误进行纠正。此种方式传输效率低，使用相对较少。其技术主要包括

• 海明码 (Hamming codes)
• 二进制卷积码 (binary convolutional codes)
• 里德所罗门码 (Reed-Solomon codes)
• 低密度奇偶校验码 (low-density parity check codes)

下面，我们主要介绍校验和技术和循环冗余检验技术。

# 校验和技术 (checksum)

校验和技术在诸多互联网协议中有应用，包括 IP 协议，TCP 协议和 UDP 协议等。广义的校验和技术即将信息分段求和，根据和进行校验。我们在这里给出因特网 16 位校验和技术 (Internet checksum) 的具体过程。

1. 信息分段：将信息每 16 位分成一段
2. 从左至右相邻两段求和
3. 若出现进位，则抹去进位并在和上加一，并返回 2.
4. 完成求和后，将最终的 16 位和各位求反，得到校验和

接收方按同样规则进行部分和求和，若最终得到的结果为 0xFFFF , 则说明传输无误。

# 循环冗余检验 (CRC)

循环冗余检验 (Cyclic Redundancy Check, CRC) 也称多项式编码 (polynomial code), 是最常用、最有效的错误检验方式。其具体方式如下：

假设传输的帧长度是 $m$, 则将其看作一个系数为模 $2$ 意义下的$m-1$ 次多项式 $M(x)$. 发送方和接收方预先商定一个生成多项式 (generated polynomial) $G(x)$. 设 $r:=\deg G(x)$ 是 $G(x)$ 的次数，则发送方计算 $x^r M(x)$ 模 $G(x)$ 得到的余式 $R(x)$, 则最终发出的帧为

$$T(x):= x^rM(x)+R(x)$$

由于多项式系数是定义在模 $2$ 意义下的，因此 $G(x)|T(x)$. 若接收方接受到的 $T(x)$ 可被 $G(x)$ 整除，则认为 $T(x)$ 传输成功，删去其后 $r$ 位即得到真实数据 $M(x)$. 数据传输出现差错的情况复杂，可以参考课本 (section 3.2.2)。

另外需要注意实现的细节，由于是模 $2$ 意义下的多项式，因此求余式多次取异或即可。

# 流量控制

流量控制很难独自出现，常伴随差错控制出现。

# 数据链路层的基本协议

# 理想单工协议

在数据链路层中，最理想的协议为理想单工协议 (Utopian Simplex Protocol). 其要求

1. Data are transmitted in one direction only (数据单向传输);
2. Both the transmitting and receiving network layers are always ready (信息发送方和接收方总是处于等待状态);
3. Processing time can be ignored (信号处理时间可以被忽略);
4. Infinite buffer space is available (缓存空间无限大);
5. The communication channel between the data link layers never damages or loses frames (通信信道不会损坏或丢失帧).

因此只需要考虑封装成帧环节。发送方每完成一个帧的封装，就发送一个帧。接收方亦持续处于等待接收状态。

下面是一个简单的实现：

/* Protocol 1 (Utopia) provides for data transmission in one direction only,

  from sender to receiver. The communication channel is assumed to be error

  free and the receiver is assumed to be able to process all the input

  infinitely quickly. Consequently, the sender just sits in a loop pumping

  data out onto the line as fast as it can. */I

typedef enum {frame_arrival} event_type;

#include "protocol.h"

void sender1(void) {

  frame s;

  packet buffer;

  while (true) {

    from_network_layer(&buffer);

    s.info = buffer;

    to__physical_layer(&s);

  }

}

void receiver1(void) {

  frame r;

  event_type event;

  while (true) {

    wait_for_event(&event);

    from_physical_layer(&r);

    to_network_layer(&r.info);

  }

}

# 无噪信道上的单工停等协议

在理想单工协议中去掉缓冲区无限大的条件，即接收方可能来不及处理发送方发出的数据。这时候显然理想单工协议中的假设 2 , 假设 3 亦不再成立。这时，就得到了无噪信道上的单工停等协议 (Simplex Stop-and-Wait Protocol for an Error-Free Channel). 其包括以下两个基本假设：

1. Data are transmitted in one direction only (数据单向传输);
2. The communication channel between the data link layers never damages or loses frames (通信信道不会损坏或丢失帧).

这时的解决方案是让接收方向发方提供反馈 (feedback). 发送方每发出一帧，待接收方确认后继续发送下一帧。这样的协议称为停等协议.

下面是停等协议的一个简单实现：

/* Protocol 2 (Stop-and-wait) also provides for a one-directional flow of data

  from sender to receiver. The communication channel is once again assumed to

  be error free, as in protocol 1. However, this time the receiver has only a

  finite buffer capacity and a finite processing speed, so the protocol must

  explicitly prevent the sender from flooding the receiver with data faster

  than it can be handled. */

typedef enum {frame_arrival} event_type;

#include "protocol.h"

void sender2 (void){

  frame s;

  packet buffer;

  event_type event;

  while (true) {

    from_network_layer(&buffer);

    s.info = buffer;

    to_physical_layer(&s);

    wait_for_event (&event);

  }

}

void receiver2(void){

  framer s;

  event_type event;

  while (true){

    wait_for_event(&event);

    from_physical_layer(&r);

    to_network_layer(&r.info);

    to_physical_layer(&s);

  }

}

# 有噪信道中的单工停等协议

将无噪信道上的单工停等协议进一步现实化，我们假设帧在信道中的传输可能出错或丢失。这样就得到了有噪信道中的单工停等协议 (Simplex Stop-and-Wait Protocol for a Noisy Channel) 对应的情况。此时可能存在如下三种问题：

1. 帧错误
2. 帧丢失
3. 确认帧丢失

# 滑动窗口协议

滑动窗口协议是停等协议的延伸，其可以实现流量控制与可靠传输 (结合重传)。

• 单帧滑动窗口与停等协议
• 多帧滑动窗口与后退 $N$ 帧协议 (Go-Back-N protocol, GBN)
• 多帧滑动窗口与选择重传协议 (Selective Repeat)

# 数据链路协议实例

# 协议三要素

协议的三要素为：

1. 语法 (Syntax): 数据格式和控制信息
2. 语义 (Semantics): 收到信息时采取的特殊操作
3. 同步 (Synchronization): 又称时序，是网络上对等实体间发送和接受信息的顺序

# HDLC 协议

向高层提供面向连接的可靠的服务机制 (connection-oriented reliable service)。

station 分类:

1. 主站 (Primary):
2. 从站 (Secondary):
3. 混合站 (Combined):

主站和从站形成非对等的链路。主站控制全部操作。混合站之间形成对等的链路。

# HDLC 协议的帧结构

# HDLC 协议中的帧分类

HDLC 协议中的帧可以分为三类：

• 信息帧 (information)
• 监控帧 (supervisory)
• 无序号帧 (unnumbered)

# PPP 协议

PPP 协议全称点对点协议 (Point-to-Point Protocol, PPP). 是数据链路层上两对等节点间数据包传输的封装协议。

# PPP 协议的组成

PPP 协议主要由三部分组成：

• 链路控制协议 (Link Control Protocol, LCP)
• 网络控制协议 (Network Control Protocol, NCP)
• 成帧方法 (framing method)

# PPP 协议的帧格式

PPP 协议的帧格式如下表所示：

# DSL 协议

# MAC 子层

IEEE 802 委员会将数据链路层划分为下述两个子层：

• 介质访问控制子层 (medium access control sublayer, MAC), 解决信道资源分配问题。
• 逻辑链路控制子层 (Logic Link Control sublayer, LLC).

其中，PPP 仅需要 MAC, broadcast 需要 LLC 和 MAC.

# 信道分配策略

信道分配策略可以分为两类：静态信道分配策略和动态信道分配策略。

静态信道分配策略包括频分复用、时分复用、波分复用、码分复用等复用策略。大多被物理层采用。在数据链路层，大多使用的策略是动态分配策略。

动态信道分配策略可以分为随机接入策略和控制接入策略两大类。

# 随机接入策略

随机接入策略 (Random-access protocols). 站间公平，不存在优先权。包括

• ALOHA:
  • Pure ALOHA: 任何用户可以随时发送数据，效率低下。吞吐量$S = Ge^{-2G}$. $S_{\max} = 18.4\%$.
  • Slotted ALOHA: 固定帧的发送时间。吞吐量$S = Ge^{-G}$. $S_{\max} = 36.8\%$. 缺点是节点发送数据过于随机。
• 载波侦听多路访问协议 (Carrier Sense Multiple Access Protocols, CSMA):
  • 1-persistent CSMA (1 - 持续 CSMA)
  • nonpersistent CSMA (非持续 CSMA)
  • p-persistent CSMA (p - 持续 CSMA)
  • CSMA with Collision Detection, CSMA/CD (带冲突检测的 CSMA)
  • CSMA with Collision Avoidance, CSMA/CA

Questions of CSMA:

• When can the station access medium?
• What can the station do if the medium is busy?
• How can the station determine the success or failure?
• What can station do if there is a conflict?

# 控制接入

# ALOHA

# CSMA

# 1-persistent CSMA

1-persistent CSMA 的机制如下：

• When a station has data to send, it first listens to the channel.
• If the channel is idle, the station transmit its data immediately.
• If the channel is busy, the station just waits until it becomes idle, and then transmits the frame.
• If a collision occurs, the station waits a random amount of time and starts all over again.

# nonpersistent CSMA

nonpersistent CSMA 的机制如下：

• A station senses the channel when it wants to send a frame.
• If the channel is idle, the station transmit it
  immediately.
• If the channel is busy, the station does not
  continually sense it and waits a random period of time and starts listening again.

非持续 CSMA 信道传输效率更高了，因为其在信道空闲时永远选择等待一段随机时间再进行发送。这样冲突的概率会降低，从而提高信道利用率。然而，伴随信道利用率提高的代价是传输时延增大。

# p-persistent CSMA

前面的 1-persistent CSMA 和 nonpersistent CSMA 都是 p-persistent CSMA 的特例。其在信道空闲时，选择以概率$p$ 发送帧，而以$1-p$ 概率推迟到下个时隙进行。

# CSMA/CD

带冲突检测 CSMA(CSMA with Collision Detection, CSMA/CD) 是经典以太网的基础。

# CSMA/CA

带冲突避免的 CSMA(CSMA with Collision Avoidance, CSMA/CA) 多用于无线局域网。

# Reference

这是一篇介绍 access protocol 的文章: Multiple access protocol: ALOHA, CSMA, CSMA/CA and CSMA/CD.

# 以太网

以太网 (Ethernet) 是一种局域网标准，对应 IEEE 标准为 IEEE 802.3.

按速度划分为：

• 标准以太网 (Classic Ethernet)
• 高速以太网 (High Speed Ethernet), 又称交换式以太网 (Switched Ethernet), 速度高于 10Mbps. 进一步可以分为以下几类：
  • Fast Ethernet: 100Mbps
  • Gigabit Ethernet: 1000Mbps
  • 10 Gigabit Ethernet: 10000Mbps

# 以太网帧格式

以太网帧格式分为 DIX 格式和 IEEE 802.3 格式。其中 DIX 格式最早提出，更加常用。

两种帧格式如下 (长度单位为字节)：

• DIX:

  前导码 (Preamble)	目标地址	源地址	类型 (区分 DIX 与 802.3)	数据	填充 (padding)	校验和
  8	6	6	2	0~1500	0~46	4

• IEEE 802.3:

  前导码 (Preamble)	目标地址	源地址	长度	数据	填充 (padding)	校验和
  8	6	6	2	0~1500	0~46	4

填充位需要保证数据与填充的长度之和不小于 46 Bytes. 因此，一个以太网帧的最小长度为 64 Bytes, 最大长度为 1518 Bytes.

# 二进制指数后退算法

第 $i$ 次冲突后，从后续 $0\sim 2^i-1$ 个时间槽中任意选择一个再次发送的算法称为二进制指数后退算法 (binary exponential back-off).

# 以太网性能

$$a = \frac{\tau}{T_0} = \frac{\tau c}{L}$$

其中 $\tau$ 为传播时延 (propagation time), $T_0$ 为发送时延 (sending time), $L$ 为帧长度 (frame length), $c$ 为数据传输率 (data rate). $a$ 越小，信道利用率越高。

# 交换式以太网

# 集线器

单节点发送数据，其余节点接收数据。发送数据采用 CSMA/CD 协议。

# 快速以太网

# WLAN

WLAN 即无线局域网 (Wireless LANs), 遵循 IEEE 802.11 标准。

主要研究其物理层和数据链路层的技术变化与特点。

# 体系结构

WLAN 协议的体系结构是有基础设施 (infrastructure mode) 的体系结构。其将客户端 (Client) 与接入节点 (Access Point, AP) 相连。Client 间的通信均需要借助 AP 进行转接。

基本服务集合 (Basic Service Set, BSS) 是一个 AP 所服务的 Client 组成的集合。

分布式系统 (Distributed System) 是用来连接不同 AP 的系统。其将多个 BSS 连接起来，称为扩展的服务集 (Extended Service Set, ESS).

# Ad-Hoc 模式

除前述有基础设施的模式之外，802.11 该提供了一种无基础设施的模式，称为自组织的网络 (Ad-Hoc)，即网络中各终端相互连接形成组网，是无基础设施 (infrastructureless mode) 的体系结构。其多用于军事及救灾环境中。

# 隐藏终端和暴露终端

隐藏终端和暴露终端是无线信号传输中特有的问题，其主要原因是不同信号站的无线信号传输范围不同，因而不能像有线信号一样可以互相听到对方。

# 帧分类

• 管理帧 (Management Frame): 用来进行节点的协调
• 控制帧 (Control Frame): 对帧信息进行确认，不携带数据字段，例如 RTS, CTS 及 ACK
• 数据帧 (Data Frame)