第 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 $$

image-20210608201740652

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

4.2 多路访问协议

$S$:吞吐量(Throughput):$T_0$ 内成功发送的数量。

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

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

ALOHA

image-20210608202531336

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

  • 基于反馈

易冲突期:$2T_0$

最大吞吐量:$18.4%$

时隙 ALOHA

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

载波监听多路访问(CSMA)

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

  • 检查空闲

    • 空闲,则以一定概率发送
    • 忙,则等待
  • 超时重传

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

nonpersistent CSMA:如果忙,则等待随机时间

persistent CSMA:即使忙,也等待一空闲就发送

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

image-20210608205456532

4.3 以太网

CSMA/CD(with Collision Detection)

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

状态:

  • 发送期

  • 争用期

  • 空闲期

时隙是 $2\tau$。

冲突检测:

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

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

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

性能:如果发送时延远大于发送时延,那么效率更好。(如局域网)

IEEE 802

  • 物理层

  • MAC 层

    • 发:增加地址和校验字段成帧
    • 收:地址识别和校验
  • LLC (逻辑链路控制)层

    • 基于 HDLC

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

image-20210608214848555

802.3:CSMA/CD

802.11:Wireless

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

10base5

  • 收发器:冲突检测、载波监听,jam 信号发送。

10Base2

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

10BaseT

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

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

直连线:用于连接不同类别设备,两端接线方式一一对应。(568B)

交叉线:连接同类设备,一端 568B,一端 568A。

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

集线器(Hub):将一个端口广播到其它端口。

image-20210608231702678

终端电阻:避免反射干扰

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

1-persistent CSMA/CD

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

image-20210608232126754

帧结构:

image-20210608232217837

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 无线局域网络

隐蔽站问题:

image-20210608211324900

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

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

解决方法:

PCF 点协调功能:通过信标(beacon)将站点登陆进来

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

MACA(带冲突避免的多路访问)

  1. SRC: RTS(请求发送)
  2. DST: CTS(允许发送)
  3. 发送数据
  4. 完毕,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:短帧间隔

发送方:

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

接收方:

  • 收到之后,等 SIFS 事件后,回 ACK

image-20210609000835599

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

解决隐蔽站**:NAV(网络分配向量)**

image-20210609001226966

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 划分,使得快的站点发送更多。

帧格式:

image-20210609002309715

  • 不使用 TXOP,每个站点发送帧长相同

  • 使用 TXOP,每个站点的发送时间相同

IEEE 802.16 WiMax

IEEE 802.15 Bluetooth

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

4.5 数据链路层交换

Bridges from 802.x to 802.y

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

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

面临的问题:

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

Learning Bridges and LAN Switches

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

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

转发表的工作:

  1. 开始时是空的
  2. 根据源地址知道端口和站点的对应关系(逆向学习)
  3. 查表,如果端口一样,则丢弃
  4. 端口不同,则转发

Spanning Tree Bridges

Summary of connection devices

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

虚拟局域网

  • 提高安全
  • 避免广播风暴
  • 低开销(软件实现)

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

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