«计算机网络»笔记：第4章 MAC 子层

介质访问控制（Medium Access Control）解决信道分配问题，高效利用信道。

4.1 信道分配问题

广播式：总线上收到包的站点看地址是否是自己，是则接收。

点对点式：通过一系列点到点的链路连接成网络。

共享信道的方式：

频分复用（FDM）
- CATV
时分复用（TDM）
- 同步（STDM）
- 异步（ATDM）
  - 随机访问（自治）
  - 受控访问
    - 中心化控制：轮询（Polling）
    - 分布式控制：令牌环（Token Ring）

TDMA：时分复用访问，每个设备分配等长的时间。

Little’s Law：$T = \dfrac{1}{\mu-\lambda}$

$\lambda$：单位时间到达数

$\mu$：单位时间服务数

$T$：平均等待时间

详见排队论。

对于一个信道，$\lambda$ 就是帧到达率，$T$ 是平均时延，假设通道带宽是 $C$，通道数量是 $N$，定义 $1/\mu$ 是平均帧长，则平均服务率是 $1/T_{\text{trans}} = 1/((1/\mu)/C)=\mu C$ 有：

$$ T_{FDM} = \frac{1}{\mu C/N - \lambda/N} = NT $$

这种静态分配，会导致带宽不足或者延迟过大，因此只能采用动态分配技术。

4.2 多路访问协议

$S$：吞吐量（Throughput）：$T_0$ 内成功发送的数量。

$G$：网络负载：$T_0$内收到的帧数。

$S = G P$，$P$ 是成功率。

ALOHA

采用总线式的结构。发送之后等待 ACK，没有收到 ACK 就重传。

基于反馈

易冲突期：$2T_0$

最大吞吐量：$18.4%$

时隙 ALOHA

需要一个统一的时钟
规定在时隙开始时发送

载波监听多路访问（CSMA）

载波监听：发送之前先检查信道是否空闲。

检查空闲
- 空闲，则以一定概率发送
- 忙，则等待
超时重传

易冲突期：等于传播时延 $t$。

nonpersistent CSMA：如果忙，则等待随机时间

persistent CSMA：即使忙，也等待一空闲就发送

1-persistent：空闲时发送概率为1
p-persistent：空闲时发送概率为 $p$。高负载时信道利用率更高。

4.3 以太网

CSMA/CD（with Collision Detection）

发送时检测冲突，一旦发现冲突就停止发送。
发送冲突时，发送 jam 强化信号
半双工系统
以太网基础

状态：

发送期
争用期
空闲期

时隙是 $2\tau$。

冲突检测：

边发送边检测
冲突：收到了非自己发送的数据
冲突时停止发送，并发送 jam

退避时间：二进制指数退避算法

等待随机时间。重发时间指数加倍，最多N次，N次失败abort。

性能：如果发送时延远大于发送时延，那么效率更好。（如局域网）

IEEE 802

物理层
MAC 层
- 发：增加地址和校验字段成帧
- 收：地址识别和校验
LLC （逻辑链路控制）层
- 基于 HDLC

不同的局域网，MAC 不同，LLC 相同。

802.3：CSMA/CD

802.11：Wireless

网卡：提供 LLC, MAC 和物理层功能，有唯一 MAC 地址。

10base5

收发器：冲突检测、载波监听，jam 信号发送。

10Base2

收发器放在网卡，使用 T 接头连接电缆。

10BaseT

双绞线连接，没有共享电缆，共享集线器。

通过双绞线连接到集线器，RJ-45 结构，收发各一对，差分传输。

直连线：用于连接不同类别设备，两端接线方式一一对应。（568B）

交叉线：连接同类设备，一端 568B，一端 568A。

中继器（Repeater）：对信号放大和整型。最大四个中继器于一个局域网。已经过时。

集线器（Hub）：将一个端口广播到其它端口。

终端电阻：避免反射干扰

广播链路：通过地址比对来决定接受与否。两个帧之间间隔一定时间，用于发送和接收模式的转换。

1-persistent CSMA/CD

监听空闲
1. 空闲超过 IFG，发送
2. 忙则监听
边发送边检测冲突
1. 如果冲突则 jam 通知大家
2. 退避（backoff）

帧结构：

Preamble：前导码，8bytes，1010…1011，用于时钟同步

Address：MAC 地址 48 bits

Type: 协议类型，如 IP，ARP

Length：Data+Pad 的长度

Data+Pad：最大 1500bytes，最小 46bytes

Checksum：CRC32

MAC 地址：前三字节是制造商，后三字节是厂商分配地址。广播地址：FF-FF-FF-FF-FF-FF。

第一字节最后一个字节的最后一个 bit = 1 是多播，0 是单播。

最小帧长度是 64 bytes，保证一个原站点能知道自己引起的冲突（发送时间超过回环时间$2\tau$）。

_	_
时隙	51.2 us
帧间隔	9.6 us
尝试上限	16
回避上线	10
Jam 大小	32bits
最大帧长	1518Bytes
最小帧长	64 Bytes
地址长	48 bits

性能

通道效率

$$ e = \dfrac{P}{P+2\tau/A} $$

p：发送概率

P：帧传输时间

A：发送成功概率，即1/A是发送成功的站点数

$P+2\tau/A$：重传开销

$$ e = (1+2BL/AcF)^{-1} $$

F：帧长

B：带宽

L：线缆长

c：光速

优化措施：

使用交换机，可以同时有多路数据传输，并提高安全性

100BaseT4

一对专门发送
一对专门接收
另外两对动态调整
半双工

编码：

不使用曼彻斯特编码，使用 8B/6T

100BASE-TX

一对收
一对发
全双工

编码：4B/5B

快速以太网只能用星星拓扑

803.3u：允许协商使用 10/100M, 全双工和半双工。自动配置。

交换机：全双工不是用 CSMA/CD

802.3z：快 100 倍

最小帧长问题的解决

载波扩展：扩展到 512B
帧突发：一次发送多个短帧

流控标准：802.3x

繁忙时回发暂停帧（type = 0x8808）

10GBps：802.3a

4.4 无冲突协议

轮询

HDLC，集中式控制。如果

令牌传递

令牌沿着环传输，拿到令牌才能发送。类似打麻将。

4.5 无线局域网络

隐蔽站问题：

隐蔽终端：左图，A 想要发送给 B，但是不知道 B 已经在收了，以为信道空闲，结果导致 B 接受失败。

暴露终端：A 无法发送给 C，以为会发送失败。

解决方法：

PCF 点协调功能：通过信标（beacon）将站点登陆进来

DCF 分布协调功能：使用握手机制

MACA（带冲突避免的多路访问）

SRC: RTS（请求发送）
DST: CTS（允许发送）
发送数据
完毕，ACK

RTS 可以发送给 SRC 范围内的所有站点，起到提醒作用。

CTS 可以发送给 DST 范围内的所有站点。从而周围站点知道他忙，这样避免了隐蔽站问题。

冲突处理：

使用二进制指数退避（类似 CSMA/CD）

例子：

B 范围内有 A, C。B->A: RTS. A: CTS. B: 保持安静，被禁止发送。

IEEE 802.11 WiFi

CSMA/CA

显式 ACK
指数退避
CA：冲突避免（可选）

DIFS：DCF 帧间隔

SIFS：短帧间隔

发送方：

如果空闲，等 DIFS
如果忙，启动退避计时器
1. 超时发送
2. 超时没收到 ACK，加倍，重复

接收方：

收到之后，等 SIFS 事件后，回 ACK

以太网是冲突后退避
CSMA/CA 是提前退避，避免冲突
通过 ACK 判断冲突

解决隐蔽站**：NAV（网络分配向量）**

NAV 是一个时间段，表示保持静默，不发送任何信息。

如上图，A 发出 RTS，C 首先收到，但是一看不是叫自己，所以就保持静默（NAV），之后 B 收到，发现是自己，就开始接收，接受完 ACK。D 也是保持静默。

802.11：这不能解决暴露站的问题，只能解决隐蔽站问题。

MACA：同时解决了暴露站和隐蔽站问题。

分段突发：假设一帧发送成功率是 $p$，则 $S = (1-p)^n$，短帧出错概率低。将长帧剪短提高成功率。

PCF（集中协调方法）：中心化控制，基站集中轮询

帧间隔：

DIFS: time waiting before frame transmission SIFS: time waiting before ACK transmission AIFS1 (Arbitration InterFrame Space): time waiting before sending high-priority traffic 高优先级仲裁 AIFS4: time waiting before sending low-priority traffic：低优先级仲裁 EIFS: time waiting before retransmission：重传等待

TXOP：传输机会机制：发送快的会被发送慢的拉后腿，所以采用按需分配，TDM 划分，使得快的站点发送更多。

帧格式：

不使用 TXOP，每个站点发送帧长相同
使用 TXOP，每个站点的发送时间相同

IEEE 802.16 WiMax

IEEE 802.15 Bluetooth

十米范围内，取代电缆，如蓝牙耳机，键盘等。使用主从模式，从站发送请求，主站允许。

4.5 数据链路层交换

Bridges from 802.x to 802.y

网桥：在数据链路层实现互联的设备。可以连接几个冲突域，降低负载。

还可以实现不同类型网络的互连（协议转换）

面临的问题：

帧格式不同
数据率不同
最大帧长不同
加密方式不同
延迟增加
没有流控，缓冲溢出
广播风暴

Learning Bridges and LAN Switches

混杂模式-会接收相关的所有帧

根据内置的转发表进行转发/丢弃等操作。

转发表的工作：

开始时是空的
根据源地址知道端口和站点的对应关系（逆向学习）
查表，如果端口一样，则丢弃
端口不同，则转发

Spanning Tree Bridges

Summary of connection devices

层	设备
应用层	应用网关
传输层	传输网关
网络层	路由器
数据链路层	网桥和交换机
物理层	中继器和集线器

虚拟局域网

提高安全
避免广播风暴
低开销（软件实现）

VLAN ID：标识站点属于哪个局域网。

每个端口分配一个 VLAN ID
每个 MAC 地址分配一个 VLAN ID