4 The Medium Access Control Sublayer¶
说明
本文档正在更新中……
说明
本文档仅涉及部分内容，仅可用于复习重点知识
在广播信道中，由于多个设备共享同一介质，一个根本性的问题随之产生：当多个设备都想同时发送数据时，如何协调和仲裁，以决定哪个设备可以使用信道？这就是所谓的竞争问题。如果不加以控制，会导致数据冲突，使得所有发送都失败
为了解决这个关键问题，引入了 MAC（medium access control，介质访问控制）子层。它是数据链路层的一部分，专门负责制定规则和协议，以决定在广播信道上谁下一个发送
1 The Channel Allocation Problem¶
- static channel allocation
以 FDMA 为例，它预先将总带宽划分成固定数量的、互不重叠的子频带，并永久或长期地分配给每个用户。这种方式实现简单，能避免用户间的干扰
但是缺乏灵活性，效率低下。当用户数量动态变化或流量具有突发性时，问题尤为突出。突发性流量意味着用户可能在短时间内需要高速传输，然后长时间静默；资源浪费。分配给静止用户的信道在空闲时无法被其他需要的用户使用，导致宝贵的带宽资源被浪费。这在数据通信这种典型的高突发性场景中效率极低
- dynamic channel allocation
不进行固定的预先分配，而是按需动态地将信道分配给有数据要发送的用户
通过 statistical multiplexing（统计复用）来共享信道。它利用了这样一个统计事实：并非所有用户都会在同一时刻需要全速传输。因此，系统可以为大量用户服务，而无需为每个用户预留专用带宽，从而显著提高了信道利用率
1.1 Static Channel Allocation¶
为了分析静态信道分配性能不佳的原因，我们将借助一些简单的排队论计算
1.1.1 Preliminary Queueing Theory¶
容量 \(C\)：指系统（在这里可以理解为共享信道）能够处理工作的最大速率（例如，总带宽或总数据处理速率）
平均需求速率 \(R\)：指所有用户对系统提出工作需求的平均速率（例如，所有用户平均的数据发送速率之和）
- \(R < C\)：系统容量在平均水平上足以满足需求。这是系统能够稳定工作的必要条件
- \(R > C\)：系统容量长期不足，会导致持续的拥塞、数据丢失和极长的延迟，即系统饱和
但即使满足 \(R > C\)，系统仍然会面临问题（如延迟、排队）。这是因为流量是随机和突发的，而不是平滑恒定的
排队（从而导致延迟）的产生源于两个固有的随机性：
- the arrival time：数据包（或用户发送请求）到达的时间点是不可预测的
- the service time：每个数据包所需的传输时间（或服务量）也是随机的（例如，数据包大小可变）
queueing theory 的本质是研究到达过程和服务过程的随机特性，以及这些随机性如何导致排队现象
将系统抽象为一个排队设施，用户或数据包抽象为顾客 \(C_n\)，定义了 3 个关键变量来数学化地描述每个顾客
- \(\tau_n\)：arrival time。顾客到达队列的时刻
- \(t_n\)：inter-arrival time。连续两个顾客 \(C_{n-1}\) \(C_n\) 到达的时间间隔
- \(x_n\)：service time。为顾客提供服务所需花费的时间
整个排队系统的行为是由两个随机变量序列 \(\lbrace t_n\rbrace\) \(\lbrace x_n\rbrace\) 共同驱动的。为了简化模型以便于理论分析，假设所有这些随机变量是相互独立的
将具体的序列抽象为两个通用随机变量：
- \(\tilde{t}\)：代表任意一个到达间隔时间的分布
- \(\tilde{x}\)：代表任意一个服务时间的分布
每个随机变量都关联着一个 probability distribution function（概率分布函数，PDF）
- \(A(t) = P[\tilde{t} \leqslant t]\)
- \(B(x) = P[\tilde{x} \leqslant x]\)
相关的 probability density function（概率密度函数，pdf）为
- \(a(t) = \dfrac{d A(t)}{d t}\)
- \(b(t) = \dfrac{dB(x)}{dx}\)
与这些随机变量相关的一些重要 moments（矩）为：
- mean inter-arrival time：\(E[\tilde{t}] = \dfrac{1}{\lambda}\)
- mean service time：\(E[\tilde{x}] = \dfrac{1}{\mu}\)
那么 \(\lambda\) 就是平均到达速率，\(\mu\) 就是平均服务速率
排队论的研究按复杂度和假设条件分为三个层次：
- elementary queueing theory：通常基于最强的简化假设
- intermediate queueing theory：放松一些假设，考虑更一般的分布
- advanced queueing theory：处理非常复杂或特殊的模型
不同层次理论之间的根本区别在于对到达间隔时间分布 \(a(t)\) 和服务时间分布 \(b(x)\) 所做的假设不同
Kendall 记号：简洁、明确地指代和研究不同类型的排队系统。\(A/B/m\)
- \(A\)：代表到达间隔时间的概率分布类型
- \(B\)：代表服务时间的概率分布类型
- \(m\)：代表系统中并行服务台（或服务员、信道）的数量。这是一个整数
\(A\) \(B\) 从以下符号集合中取值，这些符号指代它们所对应的分布：
- \(M\)：指数分布
- \(Er\)：r 阶埃尔朗分布
- \(Hr\)：r 阶超指数分布
- \(D\)：确定性分布
- \(G\)：一般分布
最简单的模式则是 \(M/M/1\)
对于 \(G/G/1\)，定义利用率因子 \(\rho = \lambda \bar{x} = \dfrac{R}{C}\)，表示单个服务台处于繁忙状态的时间比例。例如 \(\rho = 0.8\) 意味着服务器有 80% 的时间在工作，20% 的时间空闲
对于 \(G/G/m\)，\(\rho = \dfrac{\lambda \bar{x}}{m} = \dfrac{R}{C}\)，表示每个服务台的平均利用率或系统中繁忙服务台的期望比例。例如，\(m=3, \rho=0.9\)，则平均来看，约有 \(3 \times 0.9 = 2.7\) 个服务台处于繁忙状态，或者说 90% 的服务台在工作
为了使系统稳定（即队列不会无限增长），必须满足：\(\rho < 1\)
the average time in system \(T = \bar{x} + W\)，\(W\) 是平均等待时间（顾客在队列中等待服务所花费的时间）
\(W\) 反映了共享资源所带来的代价。正是因为资源（如信道、服务器）不是独占的，而是与其他用户（顾客）共享，才产生了排队和等待现象
little's result：\(\bar{N} = \lambda T\)，\(\bar{N}\) 表示系统中的平均顾客总数（包括正在接受服务的和正在排队等待的）
average queue size \(\bar{N}_q = \lambda W\)
因此，\(\bar{N} = \bar{N}_q + m\rho\)
也就是平均客户数 = 正在接受服务的平均客户数 + 正在等待的平均客户数
当一个系统有 \(k\) 个顾客时，定义此时的状态为 \(E_k\)，状态概率 \(P_k(t) = P[N(t) = k]\) 表示在特定时刻 \(t\)，系统恰好有 \(k\) 个顾客的概率
状态转移的动态方程：\(\dfrac{dP_k(t)}{dt} = \text{在时间 } t \text{ 流入状态 } E_k \text{ 的概率流率 } - \text{在时间 } t \text{ 流出状态 } E_k \text{ 的概率流率 }\)
我们考虑一个稳定的系统，当 \(t \rightarrow \infty\) 时，\(P_k(t)\) 会收敛到一个与初始状态无关的固定值 \(p_k\)。\(p_k\) 表示在长时间运行下，系统中恰好有 \(k\) 个顾客的时间比例。例如，\(p_0 = 0.2\) 意味着从长远来看，系统有 20% 的时间是空的（没有顾客）
对于 \(M/M/1\) 队列，该系统具有泊松输入，那么
\(P_k(t) = \dfrac{(\lambda t)^k}{k!}e^{-\lambda t}\)
计算这个分布的平均值，可以发现就是 \(\bar{N}(t) = \lambda t\)