本章研究的是在同一个局域网中，分组怎样从一台主机传送到另一个主机，但并不经过路由器转发。从整个互联网来看，局域网仍属于数据链路层的范围。

数据链路层

数据链路层使用的信道主要有以下两种类型：

• 点对点信道
• 广播信道

本章研究的是在同一个局域网中，分组怎样从一台主机传送到另一个主机，但并不经过路由器转发。从整个互联网来看，局域网仍属于数据链路层的范围。

本章重点内容：

• 数据链路层的点对点信道和广播信道的特点，以及这两种信道使用的协议（PPP协议以及CSMA/CD协议）的特点。
• 数据链路层的三个基本问题：封装成帧、透明传输和差错检测。
• 以太网MAC层的硬件地址。
• 适配器、转发器、集线器、网桥、以太网交换机的作用以及使用场合

链路层的三个基本问题

封装成帧

一个帧的帧长等于帧的数据部分长度加上帧首部和帧尾部的长度。首部和尾部的一个重要作用就是进行帧定界 （即确定帧的界限）。显然，为了提高帧的传输效率，应当使帧的数据部分长度尽可能地大于首部和尾部的长度。但是，每一种链路层协议都规定了所能传送的帧的数据部分长度上限——最大传送单元 MTU（Maximum Transfer Unit）。

透明传输

“在数据链路层透明传送数据”表示无论什么样的比特组合的数据，都能够按照原样没有差错地通过这个数据链路层。当数据部分出现控制字符字段就变得不透明了，故需要进行转义操作（前面插入转义字符 "ESC"），这种方法称为字节填充或者字符填充。

差错检测

一种差错（无比特差错）检测方式—— CRC 循环冗余校验码

对数据位 + 冗余校验码进行对 CRC 生成多项式进行模 2 除法运算。

当余数为 0 则判定没有差错向上层交付，否则丢弃。

点对点协议 PPP

PPP 协议应满足的需求

• 简单
• 封装成帧：必须规定特殊的字符作为帧定界符
• 透明性：采取有效措施处理数据中有与帧定界符一样的比特组合情况
• 多种网络层协议
• 多种类型链路
• 差错检测：丢弃有差错的帧
• 检测连接状态
• 最大传送单元 MTU：数据部分的最大长度

广播链路

静态信道划分协议：

• TDMA
• FDMA
• CDMA

频分复用与时分复用

码分复用

使用CDMA的每一个站被指派一个唯一的m bit码片序列 （chip sequence）。一个站如果要发送比特1，则发送它自己的m bit码片序列。如果要发送比特0，则发送该码片序列的二进制反码。例如，指派给S站的8bit码片序列是00011011。当S发送比特1时，它就发送序列00011011，而当S发送比特0时，就发送11100100。为了方便，我们按惯例将码片中的0写为–1，将1写为＋1。因此S站的码片序列是（–1–1–1＋1＋1–1＋1＋1）。

随机访问协议：

• ALOHA、时隙 ALOHA
• CSMA、CSMA/CD、CSMA/CA（无线网络，冲突避免）

ALOHA 与 时隙 ALOHA

纯 ALOHA：随机发送，冲突则重发

时隙 ALOHA：划分时间点，只有在时间点到才能随机发送，冲突则重发

载波监听 CSMA

• 非坚持 CSMA ：一旦监听到信道忙，则不再监听，而根据协议算法延迟一个时间段监听。
  • 时隙非坚持 CSMA ：只能在时隙开始时才能发送 帧。
• 坚持 CSMA
  • 1 坚持 CSMA ：传送数据时首先侦听信道，信道忙则一直等待空闲，若发生冲突，站点就等待一个随机长的时间。
  • p 坚持 CSMA ：传送数据时首先侦听信道，信道忙则一直等待空闲，以概率 p 发送数据，1 - p 概率延迟一段时间 $\tau$ (网络中最远的端到端时延)重新监听信道。若冲突则随机等待一个随机长的时间。

轮流协议：

• 轮询协议 < 主节点邀请 >
  • 轮询开销
  • 等待时间
  • 单点失效（主节点）
• 令牌传递协议
  • 令牌开销
  • 等待延迟
  • 单点故障

CSMA/CD 载波监听/冲突检测

争用期：$2\tau$ （这个值是当发送方信息即将到达接收方时，接收方以为信道空闲而发送数据到达发送方的时间）。

强化碰撞 💥：当碰撞发生后除了停止发送数据外，还要继续发送 32 比特或 48 比特的人为干扰信号。

二进制指数退避算法：当出现冲突时，等待 $randOf\{0, 1, ...,2^k-1\} \times 2\tau\ \ (k=\min\{\text{重传次数}\text{，}10\})$的时间，当重传达到 16 次仍不能成功时，则丢弃该帧并向上层报告。

MAC 地址

组成：

• 48 bits
• 前 24 bits 由 IEEE 分配管理——OUI 号
• 后 24 bits 由厂商自行分配

作用：在数据链路层标识每块网络适配器，使得能在广播信道上寻址目标节点。

协议

每台主机都维护着一个 ARP cache（记录<IP, MAC, TTL>）. 当 IP - MAC 映射不存在时将发起 ARP 广播请求。

以太网帧结构

MTU：帧最大数据长度，默认值为 1500

关于最小数据为 46 是争用期要求最小帧长 64 - 6 - 6 -2 （首部）- 4 （尾部）= 46。

链路层交换机工作原理

交换机选路原理：

将发送方的 <MAC, 接口, TTL> 填入表中；若接收方在表中则对应接口（本接口发往本接口则丢弃）发出，否则向除发送方接口以外所有接口转发。超时即删除记录。

交换机存在环路问题：

解决方案为支撑树算法，选取一个交换机为树根，以最短路径为依据找到树中的每一个节点。为了让支撑树能够反映网络拓扑的变化，每隔几秒钟每个交换机要广播其标识号和它所知道的交换机。⚠️ 互联局域网数目非常大时，支撑树算法可能花很多时间。

多种分组交换机比较

集线器：是一种硬件设备，只是将网络的覆盖距离简单地延长，而且距离有限。实现在物理层。

以太网交换机：既包括硬件又包括软件。维护交换表，实现MAC 地址过滤，具有自学习算法。具体实现在 MAC 层。

路由器：维护路由表，实现路由算法。

	集线器	路由器	交换机
流量隔离	无	有	有
即插即用	有	无	有
优化选路	无	有	无
直通交换	有	无	有

VLAN

VLAN （Vitual Local Area Network）：是指以软件方式实现逻辑工作组划分与管理的一种网络工作组组建技术。

特征：

• 局域网交换机是组建虚拟局域网的核心设备。

• 组成逻辑工作组的各结点不受物理位置的限制，换言之，同一逻辑工作组的成员不一定要连接在同一个物理网段上。

• 当一个结点从一个逻辑工作组转移到另一个逻辑工作组时，只需要通过软件设定，而不需要改变它在网络中的物理位置。