计算机网络第四章--介质访问控制层

每日一言

The root of all evil is the kotatsu. – Chiaki Shinichi
from Nodame Cantabile

介质访问控制(MAC, Media Access Control)是数据链路层的重要组成部分，负责协调多个设备共享同一传输介质的访问权限。

主要应用领域：

• 局域网(LAN)
  • 以太网
  • 无线局域网
• 广域网(WAN)
  • 卫星通信
  • 蜂窝移动网络

这样具有广播(Broadcast)功能，从一个站点可很方便地访问全网的网络环境。

Channel allocation problem 信道分配

Static Channel Allocation 静态信道分配

Multiplexing 复用技术：

• Time Division Multiplexing 时分复用
• Frequency Division Multiplexing 频分复用

M/M/1排队系统模型

M 到达过程

• 数据帧到达时间间隔服从指数分布(单位时间内到达帧个数服从泊松分布)
• 平均到达率：$: \lambda \text{ 帧/秒}$

M 服务过程

• 传输一帧所需的时间服从指数分布
• 帧的长度服从指数分布平均长度为 1/μ 位/帧。
• 信道容量为C位/秒
• 信道的平均服务率为 μC 帧/秒(即 容量 / 平均帧长 = 位/秒 / (位/帧) = 帧/秒)。

1 (服务台数量):

• 指系统中只有一个服务台，也就是一条信道。

None of the static channel allocation methods work well with bursty traffic(突发流量)

Dynamic Channel Allocation 动态信道分配(重！！)

• Random multiple access 随机多路访问
• Controlled multiple access 受控多路访问

五个动态分配信道的假设

A1 : Station Model 站点模型

• N independent stations, generates frames for transmission
• The probability of a frame being generated in an interval(时间间隔) of length t is $: \lambda t$
  • $\lambda$是一个常数(constant),代表单个站点生成新帧的到达率(arrival rate)
• 阻塞(blocked)机制：
  • Once a frame has been generateed, the station is blocked.
  • 在阻塞状态下，该站点不会再生成任何新的帧
  • 直到它之前生成帧被成功发送，阻塞结束

A2：Single Channel 单一信道

• 单一共享信道：A single channel is available for all communication
• 广播特性：All station can transmit on it and all can receive from it
• 站点等效性：All stations are equivalent
  • 实际运行的协议软件 (protocol software) 可能会给不同的站点分配优先级 (assign priorities)。

A3：Collision Assumption 冲突假设

• If two frames are transmitted simultaneously(同时), they overlap(重叠) in time and the resulting signal is garbled(混乱).
• All stations can detect collisions 所有的站点都可以检测到冲突
• A collided frame(冲突的帧) must be transmitted again(重传) later

A4：Continuous Time(连续时间) & Slotted Time(分槽时间)

连续时间：一帧可以在任何时间开始传输

分槽时间：Time is divided into discrete(离散的) intervals(时间区间)

• frame transmissions always begin at the start of a slot(时间槽的开始)
• 一个槽中可以传输0，1，多个帧
  • 0帧：空闲(idle)
  • 1帧：一次成功发送(a successful transmission)
  • 多帧：一次冲突(a collision)

A5：Carrier Sence(载波侦听)

Station can tell if the channel is in use before trying to use it. If busy, no station will attempt to use it until it gose idle(空闲). 即使用信道前会侦听信道是否空闲。

No Carrier Sense: Station cannot sense the channel before trying to use it. They just go ahead(直接进行) and transmit. Only later can they determine whether the transmission was successful.

Multiple access procotols

Contention 争夺

ALOHA

• Stations transmit a frame arbitrarily(任意的)
• After the station has sent its frame to the central computer, the computer rebroadcasts(重播) the frame.
• If collision occurs, wait a random amont of time and sends it again

Collision reason: two station send frame simultaneously(同时)

Perfermance Analysis

脆弱期(易冲突期) Vulnerable period：

发送一帧的数据，则有两t的时间都不能发送其他数据，如果发送，就会产生冲突。

基本概念(basis)：

假设：

• 帧时：假设所有帧长一致，帧时(可以理解为传输时延)为T
• 帧的产生服从泊松分布

相关参数：

• 吞吐量(Throughput S)：每帧时内成功传输的平均帧数，取值范围在0到1之间。
• 网络负载(Network load G)：是每帧时内的平均帧数，且G大约等于S，具体指时间T内所有Station 发送的帧的平均值
• 成功传输概率(Probability $P_0$)：表示成功传输的概率，吞吐量S、网络负载G和成功传输概率$P_0$满足公式$S = G \times P_0$

根据公式最终可以推导得出：

$$
P_0 =e^{-\lambda(2T)} = e^{-2G}
$$

$$
S = G \times P_0 = G e^{-2G}
$$

最中在G=0.5时得到最大值：$$

Slotted(分槽的) ALOHA

把时间划分为离散的时间间隔，每个间隔对应一帧。这要求每个用户都必须知晓时隙边界，即需要进行同步（synchronization ）。同步方式是一个特殊的站在每个时间槽起始时发送一个脉冲信号来界定时间槽边界。

时间槽的长度为T，易冲突期也为T。

$$
P_0 =e^{-\lambda(T)} = e^{-G}
$$

$$
S = G \times P_0 = G e^{-G}
$$

当G = 1 时，取到最大值：$ S = \frac{1}{e} \approx 0.368 $

CSMA(Carrier Sence Multiple Access)载波侦听多路

Station listens for a carrier before sending

• 1-persistent CSMA(1坚持)
  • If the channel is busy, waits until it becomes idle, then transmits frame immediately.(立即)
  • If a collision occurs, waits for a random amount of time and start all over again.
• Nonpersistent CSMA(非坚持)
  • If the channel is busy, waits for a random amount of time and sense channel again
• P-persistent CSMA (slotted channel)
  • If the channel is busy, waits to the next slot
  • If idle, transmits frame with probility of p, with a probility of q = 1-p it defers to the next slot. 如果信道空闲，有概率p直接发送到当前槽，概率1-p 发送到下一时间槽
  • Repeated until either the frame has been transmitted or another station has begun transmitting
  • If there had been a collision, waits a random time and starts again.

CSMA Collision

csma 还会产生冲突的原因：

1. 同时传送
2. 传播延迟 ： τ

CSMA with Collision Detection (CSMA/CD)

原则：

Station aborts(中断) the transmission as soon as it detects a collision, it saves time and bandwith.

如何检测冲突：

• 要求：发送的帧不能太短，至少要有一个冲突窗口(竞争期2τ)

当一个帧传输了2τ的时间还没有监听到冲突，则竞争成功。

CSMA/CD : Channel state

• Transmission period：传输周期，一个站点使用信道，其他站点禁止使用
• Contention period：竞争周期，所有站点都有权尝试使用信道，争用时间槽
• Idle period：空闲周期，所有的站点都不使用信道

Wireless LAN Protocols

无线网的传输与接收：

• 无线网的传输范围有固定的大小
• 在某些无线网中，并非所有站点都处于彼此的覆盖范围
• 干扰发生在接收端而非发送端

Hidden station problem 隐藏站问题

• 当A正在向B传输信号时
• C 无法感知到传输信号，所以C也可能同时向B传输答案
• 此时在B处发生冲突

Exposed station problem 暴露站问题

• 当B在向A发送数据时
• C感知到了信号，所以错误的认为无法向D发送信号

Solutions

PCF (Point Coordination Function) 点协调功能

采用轮询(Polling)机制：

• 由一个基站控制其范围内的所有活动
• 基站周期性(periodically)的广播一个信标帧(Beacon Frame)
• 信标帧包含系统参数，邀请新站点注册轮询服务。
• 一旦站点注册完成，就能有效保证获得一定比例(fraction)的带宽(bandwidth)。

DCF(Distributed Coordination Function) 分布协调功能

• Station use a handshake to determine which one can send
• MACA(Multiple Access with Collision Avoidance ) 冲突避免的多路访问
• CSMA/CA(CSMA with Collision Avoidance) 冲突避免的CSMA

MACA

• RTS发送请求帧：源节点向目的结点发送RTS(Request to Send)
• CTS允许发送帧：目的结点收到RTS后，回复允许发送(Clear to Send)
• 数据传输：源节点收到CTS后，开始传输数据
• 确认帧(ACK)：目的结点接收数据后，回复确认ACK帧

• A向B发送RTS帧，听到RTS帧的C,E结点会在接下来足够长的时间内保持沉默。
• B向A发送CTS帧，听到CTS的结点D,E会在后续数据传输期间保持静默。

Collision-Free Protocols

Basic bit-map protocol 基本位图协议

• 每个竞争期由 N 个时隙（位）组成，每个站点占用一个时隙 。
• 若站点有帧要发送，就在其对应的时隙中填入‘1’来进行预留，属于预留协议 。

Token Ring 令牌环

Binary countdown protocol 二进制倒计数协议

• 给每个站点编序号，每个站的序号长度相同
• 竞争期：有数据发送的站从高序号到低序号排队，高站点先发
• 特点：高序号站优先

Ethernet

Ethernet Cabling 以太网布线

10Base5:Thick Ethernet (粗以太网)

• InterFace board 网卡：负责数据帧的处理，将数据组装成特定格式的帧并进行收发，处理校验和以保障数据准确性；管理接收和发送缓冲区，实现与主机的直接内存传输，提升数据传输效率。
• Transceiver(接收器)：具备载波检测和冲突检测能力，能判断信道是否空闲，并在数据传输时检测冲突。一旦检测到冲突，会发出特殊无效信号通知其他收发器，使整个网络能及时响应并处理冲突 。

10Base2:Thin Ethernet(细以太网)

10BaseT

• 完全没有共享电缆
• 集线器Hub：
  • Station is connected to Hub by a deficated(专有的) cable
  • 媒体信号的再生

从此以太网的拓扑就从总线型变为星型，而以太网也就在局域网中占据了统治地位

Hub 集线器

集线器是一种多端口中继器(repeater) 。中继器的作用是对传输介质上的信号进行放大和整形，以延长信号传输距离，而集线器拥有多个端口，可连接多个设备。

• Providing a star connection physically implements a bus topology logically
• 星型的逻辑结构和总线的逻辑结构
• 支持10Mbps or 100Mbps
• 一个网段中最多配置3个集线器，否则可能影响网络性能

Ethernet MAC frame 以太网MAC帧格式

以太网常用的帧格式有两种：

a)：DIX Ethernet 普遍使用的帧格式

b)：IEEE 802.3规定的帧格式

两种帧格式相互兼容

• Preamble(前导码)：8字节，用于同步时钟
• Destination address(目的地址)：6字节，48 bits，目的地址的Mac地址
• Source address(源地址)：6字节，48 bits，发送方的Mac地址
• Type(类型)：2字节，用于标识用于封装数据字段的上层协议类型，如0x0800表示IP协议
• Length(长度)：2字节，用于表示数据字段的长度
• Data(数据)：0到1500字节，承载上层传递下来的数据
• pad(填充)：0-46字节，当数据长度小于64字节时，用于填充使得帧总长超过64bytes
• Check sum(校验和)：4字节用于存储校验和，错误的帧直接丢弃
• SoF：帧开始的界定符，表示后面的信息就是Mac帧

所以Preamble的8字节并不算Mac帧的内容

Frame Length

Max Frame Length

• 1518 Bytes(1500字节数据帧+18字节用于封装，不考虑Preamble码)

Min Frame Length

• 有效的最小帧长为64btyes (46+18)
• 这是为了满足传输延时大于2τ = 51.2 μs

$$
10Mbps \times 51.2 μs = 512 bits
$$

$$
512bits = 64 bytes
$$

Ethernet CSMA/CD :Binary Exponential Backoff(二进制指数退避)

当侦听到冲突时，以太网采取二进制指数退避机制进行避让，其流程如下：

• 从 $0, 1, 3, \cdots, 2^k - 1$ 中随机选取一个数 r 。其中 k 取尝试次数和 10 中的较小值 ，即$k=min[\text{number of attempt},10]$
• $重传时间 = r /times 基本重传时间$
• $基本重传时间 = 2\tau = 51.2μs$

Ethernet Performance

涉及参数

• Frame length（帧长） ：用 F 表示。
• Bandwidth（带宽） ：用 B 表示 。
• Cable length（电缆长度） ：用 L 表示 。
• Speed of signal propagation（信号传播速度） ：用 c 表示 。
• 传送一帧平均时间 ：用 P 表示，(P = F/B) 。
• 某个站获得信道的概率 ：用 A 表示 ，$2\tau$为时间槽 。

• 给定帧长的情况下，增加带宽B或距离L会降低网络效率
• 电缆越长，τ越大，任何两个站之间的最大电缆距离会影响性能

Switched Ethernet 交换式以太网

Switch 交换机

工作在数据链路层，检查MAC帧的目的地址对收到的帧进行转发。

Fast Ethernet: IEEE 802.3u

• 兼容旧规则
• 将比特时间从100ns缩短到10ns，带宽从10mbps提升到100mbps
• 电缆的最大长度降低到10分之一

比特时间：发送1bit需要的时间

100Base-T4

• 3类非屏蔽双绞线
• 工作在半双工模式(Half duplex)
• Manchester encoding is not used 不使用曼彻斯特码

100Base-TX

• 5类屏蔽双绞线
• 全双工(full duplex)
• 采用4B/5B编码
• 100bps速率

Hub 对比Switch

Hub:

• Incoming lines are logically connected, forming a single collision domain
• 工作方式契合经典以太网

Switch:

• Incoming frame is buffered and passed to the destination
• 对于 100Base - FX 线缆，由于其长度过长，不适合使用冲突检测算法（如 CSMA/CD ），所以必须连接到交换机上 。交换机能够更好地处理长距离传输带来的问题，保障网络正常运行 。

Gigabit(千兆) Ethernet:IEEE 802.3z

• 比起之前10倍块
• 向后兼容
  • 帧格式不变
  • 最大帧长不变
  • 最小帧长不变

在使用Switch时（全双工），不需要CSMA/CD，半双工工作模式需要CSMA\CD。

Hub:Half-duplex Mode

由于在半双工模式下，集线器连接的设备之间可能发生数据冲突 ，所以需要使用 CSMA/CD协议来检测和处理冲突 。但是由于高速带宽下，最小帧长度不变时，发送时延将变的非常小，导致网络半径被限制在25米。

Solution：

• Carrier extension (载波扩展)：
  • Add a padding after the normal frame to extend the frame to 512 bytes
  • 发送硬件添加填充，接收硬件去除填充 。通过增加帧长，在一定程度上缓解了因网络距离短带来的问题 。
• Frame bursting(帧突发)：
  • Allows a sender to transmit a concatenated(连接的) sequence of multiple frames in a single transmission
  • 允许发送方在一次传输中发送多个帧的串联序列 。这种方式可以提高数据传输效率，同时使网络半径能够保持在 200 米 ，扩大了网络覆盖范围 。

10Gbps Ethernet

• Support only full-duplex (Not using CSMA/CD 不再支持多路访问控制协议)
• Preserve(保留) the 802.3 Ethernet frame format at mac interface
• Preserve the minimum and maximum frame size of the current 802.3 standard
• 64B/66B code

Summary Ethernet

• 重要：
  • 1-persistent CSMA/CD,binary exponential backoff
  • MAC address : 48bits
  • Frame size : 64-1518B
  • Repeater(中继器)、Hub(集线器)、and Switch(交换机)：layers,collision domain,forwarding table of switch.

Wireless LAN

IEEE 802.11

architecture

常见的802.11标准：

• 802.11b
• 802.11a
• 802.11g
• 802.11n

都使用CSMA/CA 避免冲突

CSMA/CA

发送机制：

• If sense channel idle for DIFS(帧间间隔) then transmit entire frame
• 如果检测到通道繁忙，则先等待传输结束，然后开始随机后退
  • 先随机后退0~15个时间槽，每当检测到一个空闲时间槽计数器就减一，当有帧传输时则挂起后退过程，当计数器减为零时发送帧。

接收返回机制：

• If the frame gets through, destination sends a short ACK
• Lack of an ACK is inferred(推断) to indicate(表明) a collision or other error, doubles the backoff period and tries again.

DIFS

所有站点完成发送后，必须等待一段很短的时间才能发送下一帧。这段时间统称为帧间间隙。(IFS)

• DIFS：Dcf InterFrame Spacing
  • Regular data frames
• SIFS：Shot InterFrame Spacing
  • ACK frame
  • Other control frame sequences like RTS and CTS
  • a brust of fragments

Channel Sensing

• Physical sensing 物理监听

  • Checks the medium to see if there is a valid signal

• Virtual sensing 虚拟监听、

  • 每个站点通过跟踪NAV(Network Allocation Vector)来逻辑上记录信道的使用情况
  • NAV：每个帧都携带一个NAV，用于表示携带本帧所属的通信将占用信道的时间（包含返回ACK的时间）。

带NAV的CSMA/CA只能解决隐藏站问题

802.11 reliability 可靠性

1. 降低传输速率：通过降低传输速率来提升可靠性
2. 短帧突发：(a fragment butst)
   • 将大数据拆分成小的数据片段，这样做是因为短帧出错概率低，小片段在传输中更不易受噪声、干扰等影响而损坏。
   • 每个分片都有单独的序列号，校验和，并且通过停等协议发送，确保每一帧被正确送达

802.11 Saving power

Beacon frames

• 接入点(AP)周期性的广播信标帧，向设备通告接入点的存在
• 客户端设备发送给接入点的帧中通知是否进入省电模式
• 客户端进入省电模式后，AP会缓存该客户端的流量
• 客户端后续会向AP发送轮询消息(poll message),询问是否有缓存数据

APSD(Automatic Power Save Deliver) 自动省电交付

AP会缓存帧，当客户端向AP发送帧之后，AP紧接着就将缓存的帧发送给该客户端。

Mac Layer Frames 帧格式

802.2：Logical Link Control (LLC)

LLC运行在802.3以及其他802协议之上。

• Hides differences between the various kinds of 802 networks by providing a single format and interface to the network layer

提供三种服务：

• Unreliable datagram service
• Acknowledge datagram service
  • Error-controlled
• Reliable connection-oriented service
  • Error-controlled
  • flow-controlled

LLC位于MAC层和Network layer 之间

Datalink layer switching 局域网互联

Bridge 网桥

Bridges are used to interconnect LANs at data link layer.

Bridge 交换原理

网桥内部维护着一张MAC地址表，记录不同MAC地址对应的端口信息，通过查找这个表，确定将帧转发到那个端口所连接的局域网。

Bridge from 802.x to 802.y

当两个端口中连接的局域网使用不同的协议时，Bridge还负责协议转换：

Learning Bridge 学习网桥

理想的网桥是透明(Transparent):

• 即插即用，无需任何配置
• 网络中的站点无需感知网桥的存在与否

工作模式：

• Accepting every frame transmitted on all the LANs to which it is attached
• 接受连接到的所有局域网上传输的每一个帧。
• Station stable(MAC地址表)
  • Lists each possible destination and tell which output line (LAN) it belongs on

Station table

Backward Learning 后向学习：即如果有帧传来，通过记录传来帧的mac地址以及它所在端口。

网桥的三种处理过程：

• forwarding 转发
• filtering 过滤
• flooding 泛洪

flooding

将收到的数据向其余所有的端口进行发送，除了源端口

两种目的地址的帧需要泛洪：

1. 广播帧：目的地址为FF-FF-FF-FF-FF-FF
2. 未知单播帧：目的地址不在MAC地址转发表中的单播数据帧

forwarding

目的局域网与源局域网不同，则将帧转发到对应端口。

Filtering

目的局域网和源局域网是一个，则忽略。

Dynamic topologies 动态拓扑

网络的拓扑结构可能发生改变，设备或者网桥可能会开机或关机。

Solution

• 记录到达时间：每当在哈希表中建立一个表项时，会记录对应帧的到达时间。这有助于跟踪设备最近一次发送帧的时间。
• 定期扫描删除旧表项：Periodically（周期性地） scan the hash table and purges(清理) all entries more than a few minutes old

Loops in the Topology 环路

扑环路会导致广播风暴（大量广播帧在网络中不断循环，占用带宽）、帧重复（同一帧被多次接收处理）等问题，严重影响网络性能，甚至使网络瘫痪。

Spanning Tree Bridges 生成树网桥

• 根桥选择：选择ID最低的网桥作为桥根
• 每个网桥记录到根桥的最短路径，若存在多条最短路径，则选择经过ID最低的网桥的路径
• 关闭不属于最短路径的端口

Bridge vs Switch

处理方式：

• 网桥：帧处理由软件(software)完成。
• 交换机：地址识别和帧转发由硬件(hardware)实现

数据处理能力：

• 每次只能分析和转发一帧
• 具备多条并行数据路径(multiple parallel data paths)，可同时处理多个帧

转发操作：

• 网桥：采用存储转发(store-and-forward)
• 交换机：使用直通(cut-through)操作

VLAN:Virtual LAN 虚拟局域网

VLAN 实现了逻辑拓扑和物理拓扑的分离。

实现方法：

• Lable each port with a “color” ,and prohibit multicast(多播) and broadcast(广播) across colors
• Prohibit packets from traveling to destinations on different VLANs

基于支持VLAN-aware 的网桥或交换机实现

VLAN ID

In the switches, configuration tables tell which VLANs are accessible via which ports.在交换机中，配置表（configuration tables）用于指明通过哪些端口（ports）可以访问哪些 VLAN 。

VLAN ID 的选取方法：

• Every port is assigned a VLAN ID
• Every MAC address is assigned a VLAN ID
• Every layer 3 protocol or IP address assigned a VLAN ID