数据链路层

链路层要解决的问题是单段链路的数据传输，物理层解决的是数字信号与电气信号之间的相互转换。

在这一层中，我们把所有接入数据链路层的实体看作结点，包括主机，路由器，交换机和Wifi接入点；将相邻结点间的通信信道为链路；

数据通过给定链路时，传输结点需要将数据封装成帧(framing)，送入链路中，数据链路层提供的服务包括

  • 成帧；
  • 链路接入：介质访问控制(Medium Access Control, MAC)协议规定了帧在链路上传输的规则；
  • 可靠交付：链路层上的可靠交付服务也是依靠确认和重传取得的；
  • 差错检测和纠正：通常使用硬件实现；
  • 流量控制：在邻接的发送节点和接收节点间的同步调节；
  • 对半双工和全双工的实现：半双工是指一个结点不能同时同时传输和接收，全双工是指结点可以同时传输和接收；

注意：分组经过不同的链路可能采取不同的协议；每个链路协议提供不同的服务；链路层不一定要具有全部的这些功能服务。

适配器

一般链路层实在网络适配器(NIC)上实现的；不同的适配器对应不同的协议；部分链路层协议实在运行在软件上实现的，通常在软件和硬件交接的地方；

常见的适配器有Ethernet卡，PCMCIA卡， 802.11卡；

上图通信过程涉及链路层和物理层，其中

  • 发送方封装分组成帧，增加检测位，可靠传输，流量控制；
  • 接收方检测差错，可靠交付，流量控制，提取分组，并传给接收节点；

差错检测和纠错

差错检测和纠错的核心技术是冗余，通常会增加设计差错检测和纠错(error-detection and correction, EDC)比特；

接收方检测和纠错的能力称为前向纠错(forward error correction, FEC);常用于音频等设备；

image-20250612062350063

注意，错误检测并非完全可靠；越大的EDC域能提供更大的纠错检错能力，但需要tradeoff；

一种比较简单的技术为奇偶校验(parity);

  • 一维奇偶校验通过增加一位冗余，只有一半的概率检测到错误；
  • 二维偶数奇偶校验能检测和纠正单个位的错误,检测任意组合的两个错误

image-20250612062737221

另一种常见的技术为Internet校验和(checksum)，多见于传输层；

但是最广泛为基于循环冗余检测(cyclic redundancy check, CRC)的编码技术；

  • 接收方和发送方协商一个生成多项式(generator)，长度为;
  • 发送方在末尾添加冗余多项式,长度为;
  • 每个CRC标准能够检测少于r+1位的突发错误和任意的奇数个比特错误；

这意味所有连续r比特或更少比特差错可以检测，长度大于r+1比特差错能以概率检测到；

的确定等价于

image-20250612063757393

多路访问协议

网络链路分成两种具体类型

  • 点对点链路(point-to-point link)：由链路一对发送方和接收方组成，包括点对点协议(point-to-point, PPP)，HDLC或者在以太网交换机和主机间的链路；
  • 广播链路(broadcast link)：让多个发送和接收结点连接到相同的单一的共享的广播信道；比如传统以太网或者802.11局域网；

多路访问控制协议(multiple access protocol)提出了在共享广播信道中结点传输的规范；

  • 当两个或多个结点同时传输时，我们认为信道发生了碰撞(collide);
  • 某一时刻仅有一个结点发送数据才认为可以成功发送信息；
  • 碰撞发生时，没有任何结点可以有效获得传输帧；

该协议内置一个分布式算法，决定各个节点如何共享信道；共享信道负责数据传输和算法的控制信息传输，理想的效果为：

  • 当只有一个结点活跃时，活跃结点吞吐量为bps；
  • 当存在个活跃节点时，每个结点吞吐量接近为bps;

有三类常见的实现方式

  • 信道划分：把信道划分为小片；给节点分配专用的小片，
  • 随机访问：不划分信道，允许冲突，能从冲突中恢复，对应一类随机访问协议；
  • 轮流：通过集中调整共享访问避免冲突；是信号划分和随机访问的tradeoff；

信道划分协议

频分多路访问(frequency division multiple access, FDMA)

  • 对应频分多路复用，信道被分成不同频段；
  • 每个站点分配一个固定的频段，未被使用的频段空闲；

时分多路访问(time division multiple access, TDMA)

  • 对应比如时分多路复用，轮流访问信道；
  • 在每个循环中，每个站点得到一个固定长度的时隙，时隙长度通常为数据服务单元的发送时间，未被使用的时隙空闲

码分多路访问(Code Division Multiple Access, CDMA)

  • 每个节点分配一个唯一的编码，每个节点用它唯一的编码来对它发送的数据进行编码；
  • 允许多个节点“共存” ，信号可叠加，即可以同时传输数据而无冲突 ；

这些协议在即使在高负载情况下依旧能保证信道公平；但是在低负载下效率较低，后果是延迟访问，因为只存在一个活跃结点就只分配了的带宽；

随机访问协议

非时隙ALOHA是简单的协议，无需同步，帧一到达就立即传输；

假设在发送的帧和其他帧没有冲突，则概率为

这个概率过低了；

在时隙ALOHA中，假设所有帧大小相同，每个时间划分为传输一帧的时隙，每个结点必须在一个时隙开始才能传送，结点需要同步机制，每个结点知道从何时隙从何开始，也能检测到彼此的冲突；

  • 当结点发送新帧时，需要等待下一个时隙传送；
  • 若没有冲突，则可以在下一个时隙发送新帧；
  • 若有冲突，则以概率重传该帧；

其优点为单个活跃结点可以持续满速率传送帧，且高度分散，只需要时隙的同步，简单；

其缺点为冲突可能浪费时隙，以及空间时隙什么也没做，只有在传输数据包时结点才能感受到冲突；

此方案的效率为

载波侦听多路访问(Carrier Sense Multiple Access, CSMA)是一类更礼让的协议

载波侦听(carrier sensing)指结点在传输前先听信道，若忙则延迟传送，若闲则传送整个帧；

  • 仍然可能发生冲突，因为传播延迟导致两个结点没有侦听到其他节点的传送；

一类具有碰撞检测(collision detection)：当一个传输结点正在传输时同时侦听信道，若检测另一个结点正在传输干扰帧，则停止传输，随机等待一段时间；实现的协议是CSMA/CD;

等待的时间选择原则一般是二进制指数后退(binary exponential backoff)算法

这类协议在低负载情况下效率高，单个节点可以获得整个信道；但是高负载时，冲突开销大；

一般CSMA/CD协议用于以太网，而CSMA/CA协议用于无线网络；

轮流协议

轮流协议(taking-turns protocol)分为轮询协议(polling protocol)和令牌传递协议(token-passing protocol);

  • 轮询协议要求指定主结点，主节点轮询其他结点，邀请它们从信道传输数据，虽然消除了碰撞和空时隙的问题，但是带来了轮询开销时延，而且一旦主结点失效，整个网络也失效了；
  • 令牌传输协议设计了一个控制令牌，从一个结点传递到下一个结点，当且仅当当前令牌持有结点有帧发送时，才会持有令牌；同样也存在令牌开销，时延和令牌失效的风险；