[网络协议]【计算机网络】第三部分 数据链路层 (12) 多路访问

在【计算机网络】第三部分 数据链路层(11) 数据链路控制讨论了数据链路控制，它是为链路提供可靠通信的一种机制。在我们描述的（那些）协议中，假定在发送方和接收方之间存在可用的专用链路（或通道）。这个假定可能不是真的。如果我们确实有一条专用链路，比如当我们使用PPP作为数据链路控制协议连接因特网时，那么这个假定是正确的，我们不需要任何其他东西。。

另一方面，如果我们使用移动电话去与其他移动电话连接，通道（分配给售方公司的波段）并不是专用的。离我们几英尺远的人，可能正在使用同一个通道与她的朋友交谈。

我们认为数据链路层有两个子层，上子层负责数据链路控制，下子层负责解决对共享介质的访问。如果通道是专用的，我们并不需要下子层；如果上层协议负责流量控制、差错控制和拥塞控制，则不需要上子层。图12.1显示了在数据链路层中的两个子层。在【计算机网络】第三部分 数据链路层(13) 有线局域网：以太网中，将会看到IEEE确实为LAN做了如此的分割：上子层负责流量控制和差错控制，被称为逻辑链路控制层 LLC ，下子层主要负责多路访问的解决方法，被称为介质访问控制层 MAC 。

当节点或站点被连接、并使用一个称为多点链路或广播链路 multipoint or broadcast link 的公共链路时，我们就需要一个多路访问协议 multiple-access protocol 去协调链路的访问。介质访问的控制问题，与在集会上发言的规则相似——有程序来为发言授权，并保证没有两个人会在同一时间发言，发言者不会打扰到彼此，不会独占发言权等。多点网络的情况与此相似。

许多正式的协议被设计出来，用于处理共享链路的访问。我们将这些协议分为三类，如图12.2所示。

12.1 随机访问

在随机访问 random access 或竞争访问方法 contention methods 中，没有任何站点是优于其他站点的，也没有任何站点能控制其他站点。一个站点没有权利允许、或者不允许另一个站点的发送。每一次，当一个站点要发送数据时，都要用「协议定义的程序」来决定是否要发送，这个决定取决于「介质的状态（空闲或忙碌）」。换言之，只要遵循预定义的程序，包括介质状态的检测，满足条件的每一个站点都能传输数据。

该方法之所以如此命名，是因为两个特性。

• 第一，每一个站点的传输没有特定的时间表，站点的传输是随机的。这就是该方法称为随机访问的原因。
• 第二，没有规则来规定下一个将要发送的站点是哪一个。为了访问介质，站点展开竞争。这就是该方法称为竞争访问的原因。

在随机访问中，每个站点都有权访问介质、且不受控于其他站点。然而，如果当一个以上的站点想要发送时，便会产生冲突 collision ，那么便会有帧被损坏或修改。为了避免访问冲突、或在访问冲突发生时解决这个问题，每个站点遵循一个程序，该程序回答了以下问题：

• 站点何时能访问介质?
• 如果介质忙碌，站点能做什么?
• 站点如何确定传输的成功或者失败?
• 如果发生访问冲突，站点能做什么?

这里学习的随机访问方法，是由一个十分有趣的称之为ALOHA的协议发展而来的，ALOHA使用一个十分简单的程序，其称为多路访问 multiple access, MA 。该方法是通过外加一种程序（在站点传送之前要对介质进行侦听）改进而来。它称为载波侦听多路访问 CSMA 。该方法后来又演化成两个并行的方法：带冲突检测的载波侦听多路访问 carrier sense multiple access with collision detection, CSMA/CD 和带避免冲突的载波侦听多路访问 carrier sense multiple access with collision avoidance, CSMA/CA 。CSMA/CD告诉站点一旦检测到冲突，下一步该做什么，而CSMA/CA尝试如何避免冲突。

12.1.1 ALOHA

ALOHA是最早的随机访问方法，它由夏威夷大学在20世纪70年代初期开发出来。它被设计用于无线电（无线）LAN ，但也可以使用在任何共享介质上。

很明显，在这种安排中有一些潜在的冲突。介质为各个站点所共享，当一个站点发送数据时，其他站点也可能在同时尝试发送，两个站点的数据相互冲突、并且相互混淆。

1. 纯ALOHA

最早的ALOHA协议，称为纯ALOHA pure ALOHA 。这是一个简单的、但优秀的协议。它的概念是只要每个站点有帧要发送，它就发送帧。然而，既然只有一条共享通道，不同站点之间的帧就有可能发生冲突。图12.3描述了一个在纯ALOHA中帧冲突的例子。

图中有 $4$ 个站点（非现实的假设）为访问共享通道彼此竞争。每个站点发送两个帧，共享介质中共有 $8$ 个帧。在为共享通道展开的多帧竞争中，某些帧冲突了。图12.3中只有两个帧是成功的：来自站点 $1$ 的帧 $1.1$ 和来自站点 $3$ 的帧 $3.2$ 。必须要提醒的是，只要一个帧的一个位与另一个帧的一个位同时存在于通道中，就会产生冲突、且两个帧都会被损坏。

很明显，我们需要重发在传输过程中损坏的帧。纯ALOHA协议依赖于接收方的确认，当一个站点发送一个帧时，它就等待接收方发送一个确认。如果超时之后确认还未达到，站点就认为帧（或者确认）被损坏了，于是重发帧（确认+超时重传机制）。

一个冲突涉及两个或更多的站点。如果这些站点在超时后都尝试重发帧，那么这些帧可能再次发生冲突。纯ALOHA规定，当超时时间过去时 the time-out period passes ，每个站点在重发帧之前，都会随机等待一段时间。这个随机性将有助于避免更多的冲突。我们称这个时间为补偿时间 back-off time $T_B$ 。

纯ALOHA还需要第二个方法来阻止重新传输的帧造成通道拥堵。一个站点在经过最大次数 $K_{\max }$ 的重发尝试后，它必须放弃并在以后再试。图12.4描述了基于上述策略的纯ALOHA进程。

超时周期等于往返传播延迟的最大可能值 The time-out period is equal to the maximum possible round-trip propagation delay ，也就是两个最远距离站点之间发送一个帧所需时间的两倍 $2\times T_p$ 。补偿时间 $T_B$ 是一个随机值，主要取决于 $K$（未成功的传输尝试次数）的值，且 $T_B$ 的公式取决于实现。一个通用公式是二进制指数回退 binary exponential back-off 。这种方法中，每一次传输随机选择 $0$ 到 $2^k?1$ 范围内的一个数，该数乘以 $T_p$（传输的最长时间）或乘以 $T_{fr}$（一个帧的平均传输时间）以得到 $T_B$ 的值。注意：在这个过程中，每一次冲突后随机数的范围便扩大了。$K_{\max }$ 的常用值是 $15$ 。

【例12.1】一个无线ALOHA网络中的站点之间的最远距离是 $600$ 公里。如果我们假设信号的传播速度是 $3\times 10^8$ 米/秒，那么 $T_p=600\times 10^5/(3\times 10)=2\text{ms}$ 。于是，对于不同的 $K$ 值，我们可以得到不同的 $T_B$ 值。

• 如果 $K=1$， 取值范围是 { 0 , 1 } \{0 ,1\} {0,1} 。站点会产生一个随机变量，变量值为 $0$ 或 $1$ 。这就意味着 $T_B$ 是 $0(0\times 2)$ 毫秒或 $2(1\times 2)$ 毫秒，取决于产生的随机变量。
• 如果 $K=2$ ， 取值范围是 { 0 , 1 , 2 , 3 } \{0 ,1, 2, 3\} {0,1,2,3} 。这就意味着 $T_B$ 是 $0,2,4,6$ 毫秒，取决于产生的随机变量。
• 如果 $K=3$ ， 取值范围是 { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{0 ,1, 2, 3, 4, 5, 6, 7\} {0,1,2,3,4,5,6,7} 。这就意味着 $T_B$ 是 $0,2,4,\dots ,14$ 毫秒，取决于产生的随机变量。
• 要提醒的一点是，如果 $K>10$ ， 它通常被设定为 $10$。

(1) 脆弱时间

我们来计算有可能发生冲突的时间（区域）的长度 the length of time in which there is a possibility of collision ，即脆弱时间 vulnerable time 。假设站点发送固定长度的帧，且每个帧的发送时间是 $T_{fr}$ 秒 Average transmission time for a frame 。图12.5显示了站点 $A$ 的脆弱时间。

站点 $A$ 在时刻 $t$ 发送一个帧。设想站点 $B$ 在时刻 $t?T_{fr}$ 和 $t$ 之间已经发送了一个帧，$B$ 帧的末端与 $A$ 帧的始端发生了冲突。另一方面，假定站点 $C$ 在时刻 $t$ 和 $t+T_{fr}$ 之间发送了一个帧。此时，站点 $A$ 和站点 $C$ 的帧之间发生了冲突。$C$ 帧的始端与 $A$ 帧的末端发生了冲突。

图12.5中，我们可以看到，纯ALOHA中的脆弱时间（其中一个冲突可能发生）是帧传输时间的 $2$ 倍，为 $2\times T_{fr}$ 。

【例12.2】一个纯ALOHA网络，在一个传输速度为 $200\text{kbps}$ 的共享通道上，传输 $200$ 位的帧。使这个帧在传输过程中避免冲突，要达到什么样的条件?
解：帧的平均传输时间 $T_{fr}$ 是 $\frac{200\text{bits?}}{200\text{kbps}}=1\text{ms}$ 。脆弱时间是 $2\times 1\text{ms}=2\text{ms}$ 。这就意味着，在该站点开始传输前的 $1$ 毫秒，没有站点会开始传输，并且当该站点正在传输的 $1$ 毫秒期间，也没有站点会开始传输。

(2) 吞吐量

我们称 $G$ 为一个帧传输时间内、系统产生的帧的平均数量。能证明 纯ALOHA成功传输帧的平均数量是 $S=G\times e^{?2G}$ 。当 $G=\frac{1}{2}$ ，得到最大吞吐量 $S_{\max }$ 是 $0.184$ 。即，在一个帧的传输时间内产生二分之一个帧（即两个帧的传输时间产生一个帧），这些帧的 $18.4\%$ 能成功到达目的地。因为脆弱时间是帧传输时间的 $2$ 倍，故这是一个可预期的结果。因此，如果一个站点在脆弱时间内只产生一个帧（且在这段时间内没有其他站点产生帧），这个帧便能成功地到达它的目的地。

【例12.3】一个纯ALOHA网络，在一个传输速度为 $200\text{kbps}$ 的共享通道上传输 $200$ 位的帧。如果系统（包括所有站点）产生以下数量的帧，吞吐量将是多少？1. 每秒 $1000$ 个帧；2. 每秒 $500$ 个帧；3. 每秒 $250$ 个帧。
解：帧的传输时间是 $200\text{bits}/200\text{kbps}$ ，即 $1$ 毫秒。

1. 如果系统每秒产生 $1000$ 个帧，也就是每毫秒产生一个帧。负载为 $1$ 。在这种情况下，即 $S=e^{?2}=0.135(13.5\%)$ 。也就是说，吞吐量是 $1000\times 0.135=135$ 帧。$1000$ 个帧中只有 $135$ 个可能成功。
2. 如果系统每秒产生 $500$ 个帧，也就是每毫秒产生 $\frac{1}{2}$ 个帧。负载为 $\frac{1}{2}$ 。在这种情况下，即 $S=e^{\frac{1}{2}}=0.184(18.4\%)$ 。也就是说，吞吐量是 $500\times 0.184=92$ 帧。$500$ 个帧中只有 $92$ 个可能成功。注意：这就是最大吞吐量百分比的例子。
3. 如果系统每秒产生 $250$ 个帧，也就是每毫秒产生 $\frac{1}{4}$ 个帧。负载为 $\frac{1}{4}$ 。在这种情况下，即 $S=0.152(18.4\%)$ 。也就是说，吞吐量是 $250\times 0.152=38$ 帧。$250$ 个帧中只有 $38$ 个可能成功。

2. 时隙ALOHA

纯ALOHA的脆弱时间是 $2\times T_{fr}$ 。这是因为没有规则来定义站点何时能发送。一个站点可能在另一个站点已经开始发送之后马上发送，也可能在另一个站点完成发送之前马上发送。

时隙ALOHA的发明改进了纯ALOHA的效率。在时隙ALOHA slotted ALOHA 中，我们把时间分割成 $T_{fr}$ 秒的时隙，并强制站点只有在时隙开始之时才能发送。图12.6描述了一个在时隙ALOHA中帧冲突的例子，帧 $2.1,3.1$ 冲突，帧 $1.2,4.1$ 冲突。

因为只允一个站点在同步时隙的开始时发送帧，如果一个站点错过了这个时刻，就要等到下一个时隙的开始之时。这就意味着：从这个时隙开始时发送帧的站点，在该时隙就已经完成了发送。当然，如果两个站点试图在同一个时隙的开始之时发送帧，那么仍然存在冲突的可能。无论如何，现在脆弱时间减少了一半，如图12.7所示，它等于 $T_{fr}$ 。图12.7说明了，时隙 ALOHA的脆弱时间只是纯ALOHA的一半。

吞吐量

能证明 时隙ALOHA成功传输帧的平均数量是 $S=G\times e^{?G}$ 。当 $G=1$ 时，得到最大吞吐量 $S_{\max }$ 是 $0.368$ 。即，当一个帧传输时间内有一个帧产生的话 a frame is generated during one frame transmission time ，这些帧 these frames 的 $36.8\%$ 会成功达到它们的目的地。这个结果是能被预知的，因为脆弱时间等于帧传输时间。因此，如果一个站点在脆弱时间内只产生一个帧（且在这个时段内没有其他站点产生帧），这个帧便能成功地到达它的目的地。

【例12.4】一个时隙ALOHA网络使用一个带宽为 $200\text{kbps}$ 的共享通道发送 $200$ 比特的帧。如果系统（包括所有站点）产生以下数量的帧，吞吐量将是多少？1. 每秒 $1000$ 个帧；2. 每秒 $500$ 个帧；3. 每秒 $250$ 个帧。
解：此情况与前一个练习相似，除了网络使用时隙ALOHA来代替纯ALOHA之外。帧传输时间是 $200/200\text{kbps}$ ，即 $1$ 毫秒。

1. 此例中 $G$ 为 $1$ ，因此 $S=G\times e^{?G}$，即 $S=0.368(36.8\%)$ 。这意味着吞吐量是 $1000\times 0.368=368$ 帧。$1000$ 个帧中只有 $368$ 个能成功。注意这就是最大吞吐量百分比的例子。
2. 此例中 $G$ 为 $1/2$ ，因此 $S=G\times e^{?G}$ ，即 $S=0.303(30.3\%)$ 。这意味着吞吐量是 $500\times 0.303=151$ 帧。$500$ 个帧中只有 $151$ 个能成功。
3. 此例中 $G$ 为 $1/4$ ，因此 $S=G\times e^{?G}$，即 $S=0.195(19.5\%)$ 。这意味着吞吐量是 $250\times 0.195=49$ 帧。$250$ 个帧中只有 $49$ 个能成功。

12.1.2 载波侦听多路访问 CSMA

为了减少冲突发生的概率、从而提高性能，我们采用CSMA方法。如果站点在发送前先侦听一下介质，其冲突的概率就会减少。载波侦听多路访问 Carrier sense multiple access, CSMA 要求：每一个站点在发送之前首先要监听介质（或者检查介质的状态）。换句话说，CSMA基于的原理就是"传输前先侦听"或"说话前先听"。

虽然CSMA能够减少冲突的概率，但是它不能消除冲突。原因如图12.8 ，一个CSMA网络的时空模型中所示。站点与一个共享通道连接（通常是一个专用介质）。

冲突的概率依然存在的原因是因为传播延迟 propagation delay 。当站点发送一帧时，它的第一个位到达每一个站点、和每一个站点检查到它的信号，都需要一定的时间（尽管这一时间非常之短）。即，一个站点之所以能够侦听到介质、并发现它处于空闲状态，仅仅是因为其他站点的传播信号还没有到达该站点。

在时刻 $t_1$ ，站点 $B$ 侦听介质、并发现介质处于空闲状态，所以它发送一个帧。在时刻 $t_2(t_2>t_1)$ ，站点 $C$ 侦听介质、并发现它处于空闲状态，因为这时从站点 $B$ 发来的第一个位还没有到达站点 $C$ 。站点 $C$ 也发送一个帧。于是这两个信号冲突、且两个帧同时被损坏了。

1. 脆弱时间

CSMA的脆弱时间是传播时间 $T_p$ ，这是一个信号从介质的末端到另一端的传播时间。当一个站点发送一个帧，且其他站点也试图在这个时间段内发送帧时，就会发生冲突；但是，如果帧的第一个位已经到达了介质的末端，其他每个站点都能"听到"这个位，并停止发送。图12.9显示了最差的状况。最左边的站点 $A$ 在时刻 $t_1$ 发送一个帧，它在时刻 $t_1+T_p$ 到达最右边的站点 $D$ 。灰色区域显示了时间上和空间上的脆弱区域。

2. 持续方法

如果通道繁忙，站点将如何做？如果通道空闲，站点又将做什么？有三种方法被设计用来回答这些问题：1-持续方法，非持续方法和 p-持续方法。图12.10描述了当一个站点发现通道繁忙时，三种持续方法的表现。

图12.11描述了这些方法的流量图。

• 1-持续方法 1-persistent method 是最简单直接的。该方法是，如果站点发现线路空闲，那么它就立即发送帧（概率是 $1$ ）。这种方法发生冲突的机率最高，因为在发现了线路空闲后，两个或更多的站点都可以发送它们的帧。在【计算机网络】第三部分 数据链路层(13) 有线局域网：以太网中，我们将看到以太网使用该方法。
• 非持续方法 nonpersistent method 中，要发送帧的站点侦听线路，如果线路空闲，它就立即发送；如果线路不空闲，站点就等待一个随机时间，然后再次侦听线路。非持续策略可以减少冲突的概率，因为不太可能存在两个或更多个站点，等待相同的时间、并且再次立即重新尝试。然而，这种方法降低了网络的效率，因为有时可能有要发送帧的站点、而介质保持空闲状态 because the medium remains idle when there may be stations with frames to send 。
• 如果通道有时隙、且时隙周期等于或大于最大传播时间时，使用p-持续方法 p-persistent method 。p-持续方法综合了其他两个策略的优点，它既减少了冲突的机会，又提高了网络效率。在此方法中，如果线路繁忙，则一直侦听；当站点发现线路空闲后，它会采取以下步骤：
  1. 如果概率是 $p$ ，站点发送帧。
  2. 如果概率是 $q=1?p$ ， 站点会等待下一个时隙的开始，并再次检查线路。a. 如果线路空闲，它将进入步骤 $1$ 。b.如果线路繁忙，它会当做一个冲突已经发生了、并使用补偿程序。

12.1.3 带冲突检测的载波侦听多路访问 CSMA/CD

CSMA方法没有规定冲突之后的处理程序。带冲突检测的载波侦听多路访问 CSMA/CD 提出了处理冲突的算法——在这一方法中，任意站点都可以发送帧，然后就监控介质看传送是否成功。如果成功，站点完成发送，如果不成功，就说明存在冲突，需要重新发送此帧。

为了更好地理解CMSA/CD ，看看冲突涉及的两个站点发送的第一个位的情况。每个站点都继续发送帧中的其他位、直到它检测到冲突，图12.12描述了第一个位发生冲突的情况，冲突的双方是站点 $A$ 和站点 $C$ 。
在时刻 $t_1$ ，站点 $A$ 执行它的持续程序并开始发送帧。在时刻 $t_2$ ，站点 $C$ 还未侦听到 $A$ 发送的第一个位，站点 $C$ 执行它的持续程序并开始发送帧，都是从左向右传输的。在时刻 $t_2$ 后的某一时刻，冲突发生了。在时刻 $t_3$ ，当站点 $C$ 收到 $A$ 的第一个位时，它检测到冲突，站点 $C$ 马上（或者一小段时间后，但我们假设为马上）放弃了传输。在时刻 $t_4$ ，当站点 $A$ 收到 $C$ 的第一个位时，它检测到冲突，它也同样马上放弃了传输。在图12.12中，我们可以看到站点 $A$ 进行传输的持续时间是 $t_4?t_1$ ，站点 $C$ 进行传输的持续时间是 $t_3?t_2$ 。

随后我们可以看到，在此协议中，任何帧的长度除以比特率（即该帧的传输延迟）必须大于这两个持续时间中的任何一个（或这些持续的时间段）。在时刻 $t_4$ ，虽然 $A$ 帧的传输还未完成，但却被放弃了；在时刻 $t_3$ ，虽然 $C$ 帧的传输还未完成，但却也被放弃了。

现在我们明白了这两个传输的持续时间，图12.13显示了一张更为完整的图。

1. 帧的最小长度

为了实现CSMA/CD，需要限定帧的长度：在发送帧的最后一位前，发送站点必须检测冲突，如有任何冲突要放弃传输。这是因为一旦整个帧被发送了，站点就无法保留帧的副本，并无法掌控线路的冲突检测。因此，帧传输时间 $T_{fr}$ 必须至少是最大传播时间 $T_p$ 的两倍。

为了理解这个缘由，让我们来考虑最差的情况。如果两个站点卷入一个冲突中，且这两个站点距离最远，信号从第一个站点到达第二个站点要花费时间 $T_p$ ，冲突的作用使得到达第一个站点还需要花费时间 $T_p$ 。因此，便要求第一个站点在 $2T_p$ 时间后仍在进行传输。

【例12.5】使用CMSA/CD的一个网络，带宽是 $10\text{Mbps}$ 。如果最大传播时间（包括设备的延迟、并忽略发送一个干扰信号所需的时间）是 $25.6\text{μs}$ ，那么帧的最小长度是多少？
解：帧的传输时间是 $T_{fr}=2\times T_p=51.2\text{μs}$ 。这就是说，最差的情况下，一个站点需要传输 $51.2\text{μs}$ 后才能检测到冲突。帧的最小长度是 $10\text{Mbps}\times 51.2\text{μs}=512\text{bits}$ 或 $64\text{bytes}$ 。这是标准以太网中帧的最小尺寸，在数据链路层(13) 有线局域网：以太网中会有介绍。

2. 程序

现在让我们看一下图12.14中的CMSA/CD流量图。它与ALOHA协议的流量图相似，但存在着不同。

第一个不同是增加了持续程序。在开始发送帧之前，我们要使用之前讨论过的持续程序中的一种（1-持续，非持续或者p-持续）来侦听通道。图12.11中相关的图形，将被持续程序中的一种所代替。

第二个不同是帧的传输。在ALOHA中，我们先传输一个完整的帧，然后等待确认。在CMSA/CD中，传输和冲突检测是一个连续的过程——我们并不是先发送一个完整的帧，然后才检测冲突。此外，站点的传输和接收是连续的和同步的（使用两个不同的端口），我们用一个循环来说明，传输是一个连续的过程 transmission is a continuous process 。我们不断地进行监控、以检测出以下两种情况中的一种：传输完成了或者检测到一个冲突。这两个事件都能使传输停止。如果从循环出来，还是没有检测到冲突，这就意味着传输已经完成了，整个帧被传输了。否则，便有冲突发生了。

第三个不同是万一其他站点仍未检查到冲突，便发送一个短小的干扰信号 j amming signal 使冲突加强。

3. 能量级别

通道中的能量级别有三个值：$0$ 、正常和不正常 zero, normal, and abnormal 。在级别 $0$ ，通道是空闲的；在正常级别，一个站点成功地占用了通道，并正在发送一个帧；在非正常级别，发生了冲突、且能量的级别是正常级别的两倍。将要发送或者正在发送帧的站点，必须监控能力级别来测定通道是处于空闲、繁忙还是冲突状态 idle, busy, or in collision mode 。图12.15描述了这个情形。

4. 吞吐量

CSMA/CD的吞吐量大于纯ALOHA或时隙ALOHA。不同的最大吞吐量将出现在不同的 $G$ 值，且基于不同的持续方法、以及在p持续方法中不同的 $p$ 值。1-持续方法中，当 $G=1$ 时，得到最大吞吐量约为 $50\%$ 。非持续方法中，当 $G$ 值在 $3$ 到 $8$ 之间时，能得到高达 $90\%$ 的最大吞吐量。

12.1.4 带冲突避免的载波侦听多路访问 CSMA/CA

CMSA/CD的基本理念是：一个站点为了在传输过程中检测到冲突，就要有能力去接收（信号）。没有冲突时，站点接收到一种信号：它自身的信号；冲突发生时，站点接收到两种信号：它自身的信号和第二个站点传输的信号。为了区分以上两种情况，不同情况中接收到的信号应该明显不同。换言之，来自第二个站点的信号需要为第一个站点产生的信号增加大量的能量 add a significant amount of energy 。

• 在一个有线网络中，接收信号的能量与发送信号的能量基本一样，或因线路长度较短，或因存在中继器放大了发送方和接收方之间的能量。这就是说在冲突中，被检测到的能量几乎翻倍。
• 然而，在一个无线网络中，大量发送信号的能量在传输中丢失。接收信号的能量也很小。因此，一个冲突可能只增加 $5\%～10\%$ 的额外能量。这对有效的冲突检测起不了什么作用。

因为无线网络的冲突无法检测到，故而我们要避免冲突。带冲突避免的载波侦听多路访问 CSMA/CA 就是为这种网络发明的。CSMA/CA通过使用三种方法来避免冲突：帧间间隔、竞争窗口和确认，如图12.16所示。

1. 帧间间隔 IFS

首先，可以通过推迟传输来避免冲突，即使通道是空闲的。当发现通道是空闲的时，站点并不马上发送。它会等待一段时间，这段时间称之为帧间间隔 interframe space, IFS 。即使当通道被侦听时，它看上去是空闲的，但是一个远端站点可能早已开始传输了，只是远端站点的信号还未到达这个站点而已。IFS 时间使得远端站点传输的信号能到达该站点。如果在 IFS 时间后，通道仍然是空闲的，那么站点就能发送了，但是它仍然要等待一段时间，这段时间等于竞争时间。

在CSMA/CA中，IFS 变量也能用来定义或区分一个站点或帧的优先次序。例如，一个站点被赋值的 IFS 越短，它的优先权越高。

2. 竞争窗口

竞争窗口将时间分割成时隙 The contention window is an amount of time divided into slots ，预备发送的站点选择随机数目的时隙 a random number of slots 作为等待的时间。窗口中时隙的数量，是根据二进制指数回避策略 binary exponential back-off strategy 而变化的。这意味着，它第一次被设置为一个时隙，以后每次站点在 IFS 时间后无法检测到空闲通道时，时隙的数量都要翻番 it is set to one slot the first time and then doubles each time the station cannot detect an idle channel after the IFS time 。这与p-持续方法很相似，除了等待站点根据随机结果来决定时隙的数量以外 a random outcome defines the number of slots taken by the waiting station 。

竞争窗口中有趣的一点是，每个时隙后站点都要侦听通道。然而，如果站点发现通道繁忙，它并不重启程序，而是停止定时器，并当侦听到通道空闲时再重启定时器。这给了等待时间最长的站点以优先权 This gives priority to the station with the longest waiting time. 。

3. 确认

虽然用了所有这些防范措施，但是仍然有可能产生冲突、而导致帧的损坏。另外，数据也可能在传输中被损坏。肯定的确认和定时器的超时将有助于确保接收方收到帧。

4、 程序

图12.17说明了程序。注意：通道在 IFS 之前和之后都要被侦听；在竞争时间内，通道也要被侦听——在竞争窗口中的每一个时隙内，通道都要被侦听。如果发现通道空闲，定时器继续；如果通道繁忙，定时器停止并在通道空闲后再继续。

5. CSMA/CA和无线网络

CSMA/CA被广泛地使用在无线网络中。然而，上述的程序还不能处理一些「与无线网络相关的特殊问题」，比如隐藏终端或暴露终端问题。我们将看到，如何通过为上述协议添加握手特性，来解决这些问题。CSMA/CA在无线网络中的应用，会在【计算机网络】第三部分 数据链路层(14) 无线局域网和蓝牙技术中讨论。

12.2 受控访问

在受控访问 controlled access 中，站点之间相互协商，以确定哪一个站点有权发送；某一个站点没有得到其他站点的认可，就无权发送。下面讨论三种流行的受控访问方法。

12.2.1 预约

在预约 reservation 方法中，站点在发送数据之前需要预约。将时间划分为时隙，在每一个时隙内，在该时隙中发送的数据帧之前有一个预约帧（预约帧 $\to$ 数据帧）。如果系统中有 $N$ 个站点，在预约帧中就恰好会有 $N$ 个预约子时隙。每个子时隙均属于一个站点。当一个站点想要发送一个数据帧时，它在自己的子时隙中做一个预约。已经预约完的站点，可以在预约帧之后发送数据帧。

图12.18描述了一个有五个站点和「有五个子时隙的预约帧」的情形。在第一个间隙，只有站点 $1,3,4$ 做了预约。在第二个问隙，只有站点 $1$ 做了预约。

12.2.2 轮询

轮询 polling 方法的拓扑结构是：一个设备作为主站 prirnary station ，而另一些设备作为从站 secondary station 。所有的数据交换都要通过主站点进行，即使最终的目的站点是从站点时也是这样。主设备控制链路，而从设备只是跟随着它的指令工作。主设备决定在给定的时间内，哪个设备被容许使用通道。所以，主设备始终是一个会话的发起者。(见图12.19 )

如果主设备希望接收数据，它就询问从设备是否有数据要发送，这一功能称做轮询。如果主设备希望发送数据，它就通知从设备准备接收，这一功能称做选择 select 。

1. 选择

在主设备要发送数据时，就使用选择功能。请记住，主设备控制链路。如果主设备既不发送数据、也不接收数据，那么它就知道链路是可用的。这时，如果它有数据要发送，主设备就可以发送，但是它不清楚的是，目标设备是否准备接收。所以，主设备必须通知从设备，为这即将到来的传输，并等待从设备发送「它已经处于准备好状态」的确认。

在发送数据之前，主设备要创建并发送一个选择 SEL 帧，其中的一个字段包含目标从设备的地址。

2. 轮询

主设备使用轮询功能，请求从设备传输数据。当主设备准备接收数据时，它必须逐个询问每一个设备是否要发送数据：

• 当询问到第一个设备时，如果它没有数据要发送，就用一个 NAK 帧来响应；
• 如果它要发送数据，就用数据（用数据帧格式）来响应。
• 如果响应的是否认帧 NAK ，主设备就用同样的方法，轮询下一个从站点，直到它找到一个要发送数据的站点为止。
• 如果响应是数据帧，主设备就读取该帧并返回一个确认 ACK 帧，表示已经接收。

12.2.3 令牌传递

在令牌传递 token-passing 方法中，网络中的站点被组织在一个逻辑环中。换言之，对每一个站点来说，都有它的前驱和后继。前驱是指逻辑环中处于该站点之前的站点；而后继是指在环中处于该站点之后的站点。该站点是目前正在进行访问的站点。访问的权限由该站点的前驱站点传递给它；当该站点没有数据再要发送时，便将权限传递给它的后继站点。

但是访问通道的权限如何一个站点一个站点地进行传递呢？在此方法中，一个特殊的信息分组被称为令牌 token 在环中循环。令牌的持有，赋予站点访问通道并发送数据的权限。

当一个站点有一些数据要发送时，它要等待从它的前驱站点传来的令牌。然后，它持有令牌并发送数据。当这个站点没有数据再要发送时，它释放令牌并传递给环中的下一个逻辑站点。站点只有在下一个循环中再次收到令牌时，才能再发送数据。在这个过程中，如果一个站点收到了令牌，但是它没有数据要发送，它便将令牌传递给下一个站点。

在这种访问方法中，令牌管理是必需的。站点占有令牌的时间必须得到限制；令牌必须得到监控，以确定它没有丢失或损坏。例如，如果一个站点持有令牌失败了，令牌就会在网络中消失。令牌管理的另一个功能是，给站点和被传输的数据类型分配优先权。最后，需要进行令牌管理，使低优先级站点将令牌释放给高优先级站点。

逻辑环

在令牌传递网络中，站点不必要真的连接在一个环中，这个环只是逻辑的。图12.20显示了能创造逻辑环的、四种不同的物理拓扑结构。

• 在物理环拓扑结构中，当一个站点把令牌传给它的后继站点时，其他站点无法看到令牌；后继站点是线路中的下一个。这意味着，令牌不必知道下一个后继站点的地址。这种结构的问题是：如果链路中的一个链路（在两个邻近站点之间的介质）出现了故障，整个系统就失败了。
• 在二重环拓扑结构中，则使用了一个二级（辅助的）环，二级环的运行方向与主环的正好相反。只在紧急情况才使用二级环（就像汽车的备用胎一样）。如果在主环链路中的一个链路发生了故障，系统会自动地将两个环合并为一个临时的环；当发生故障的链路修复好后，辅助环又进入空闲状态。注意：要运行这种拓扑结构，每个站点都要有两个传输端口和两个接收端口。
  被称为光纤分布式数据接口 Fiber Distributed Data Interface, FDDI 和铜线分布式数据接口 Copper Distributed Data Interface, CDDI 的高速令牌环网络，就使用这个拓扑结构。
• 在总线环拓扑结构（也称为令牌总线）中，站点与称为总线的单根光纤连接。然而，它们也组成了一个逻辑环，因为每个站点都知道它后继站点的地址（为了令牌管理的目的，它们同样也知道前驱站点的地址）。当一个站点完成数据发送后，它释放令牌、并将后继站点的地址插入令牌中，只有地址与令牌的目的地址相匹配的站点，才能访问共享介质。IEEE标准化的令牌总线局域网，就使用这种拓扑结构。
• 在星状环拓扑结构中，物理拓扑结构是星状的。其中，有一个网络集线器充当连接器。网络集线器中的电线形成了环；站点通过两根电线与环相连。这种拓扑结构使得网络不容易发生故障，因为如果一个链路失败了，网络集线器可以忽略它，而其他的站点还是能够运行的。而且，从环中增加和减少站点比较方便。IBM设计的令牌环局域网仍在使用这种拓扑结构。

12.3 通道化

通道化 channelization 也是一种多路访问方挂。在这一方法中，不同的站点间在时间上、频率上或通过编码来共享链路的可用带宽，相当于形成不同的通道。本节讨论三种通道化协议：FDMA、TDMA和CDMA。第16章中，讨论移动电话系统时，将看到所有这些方法的应用。

12.3.1 频分多路访问 FDMA

在频分多路访问 frequency-division multiple access, FDMA中，可用的带宽由所有的站点共享：公共通道的可用带宽被划分成频带，每一个站点都使用分配给它的频带发送数据。换言之，每一个频带都预留给特定的站点使用，该频带永远属于一个站点。每个站点也使用带通滤波器来限定传输器的频率。为了防止站点间的冲突，通过小的防护频带 guard bands 将指定的波段彼此分开。图12.21说明了FDMA的概念。

FDMA为整个通信期间指定一个预定频率的频带。这就意味着，FDMA能方便地使用流数据（无法分组的连续的数据流）。在第16章中，将看到移动电话系统是如何利用这一特性的。

必须强调的是，虽然FMDA与FDM概念上看似相似，但是两者之间存在区别。

• 第6章介绍的FDM是一种物理层技术，能组合低带宽通道的负载、并使用一个高带宽通道来传输它们，这些被组合的通道是低通的。多路复用器调制信号、将它们组合并产生一个带通信号。每个通道的带宽都被多路复用器移动了 The bandwidth of each channel is shifted by the multiplexer 。
• 另一方面，FDMA是数据链路层的一种访问方法。每个站点的数据链路层都告知它的物理层，把传递给它的数据转换成带通信号，且信号必须在被指定的频带中产生。在物理层并没有实际的多路复用器存在。每个站点产生的信号是自动带通过滤的。当它们被发送到公共通道时，它们是混合在一起的。

12.3.2 时分多路访问(TDMA)

在时分多路访问 time-division multiple access, TDMA 中，所有的站点在时间上共享通道的带宽：每一个站点被分配一个时隙，只有在这一时隙内它才能够发送数据。每个站点在指定的时隙中传输数据。图12.22说明了TDMA的概念。

TDMA的主要问题在于：如何使不同的站点达到同步。每个站点都要知晓自身时隙的开始点和所处的位置。如果站点分布在一个广泛的区域内，那么系统产生的传播延迟会给前述问题带来困难。为了使延迟得到补偿，我们插入了保护时间 guard times 。通过在时隙开始点插入同步位（通常称为前导位），我们完成同步化。

在TDMA中，带宽被视为是时间上共享的一个通道。同样要强调，虽然TDMA与TDM在概念上看似相似，但它们也存在不同。

• 第6章中介绍的TDM是一种物理层技术，它将来自低速通道的数据组合起来、并使用一个高速通道来传输它们。这个过程使用一个物理多路复用器，从每个通道交叉存取数据单元。
• 另一方面，TDMA是数据链路层的一种访问方法。每个站点的数据链路层都告知它的物理层使用指定的时隙。在物理层并没有实际的多路复用器存在。

12.3.3 码分多路访问 CDMA

码分多路访问 code-division multiple access, CDMA 的概念，在几十年前就已经提出来了。电子技术的新发展使得它的实现成为可能。与FDMA不同，CDMA仅有一个通道占据链路整个的带宽。而与TDMA不同的是，所有的站点都可以同时发送数据，没有时间的共享问题。即在CDMA中，一个通道同时承载所有的传输。

总体来说，在码分多路访问中，站点使用不同的编码以达到多路访问。CDMA基于编码理论、并使用芯片序列，且通过使用例如 Walsh 表的正交编码方法来产生芯片序列。这些在后文中会一一介绍。

1. 类比

我们先来给出一个类比。CDMA简指使用不同的编码来通信。例如，在一个大房间里有许多人，有两个人能用英语通话、而其他的人不懂英语。另外两个人能用中文通话，也只有他们两人懂中文，依此类推。换言之，公共通道即该例中的房屋空间，几对人很容易进行沟通，却要使用不同的语言（编码）。

2. 思想

我们假设有四个站点 $1,2,3,4$ 连接在同一通道上。来自站点 $1$ 的数据是 $d_1$ ，站点 $2$ 的是 $d_2$ ，依此类推。分配给第一个站点的编码是 $c_1$ ，第二个的是 $c_2$ ， 依此类推。假定被分配的编码有两个特性:

1. 两个编码相乘得 $0$（正交）
2. 编码自身相乘得 $4$（站点的数量）。

通过这两个假想的特性，看看以上四个站点如何使用同一公共通道同时发送数据，如图12.23所示。

站点 $1$ 将它的数据与编码相乘（正如我们将看到的那样，这是一种特殊的乘法）得到 $d_1\times c_1$ ，站点 $2$ 将它的数据与编码相乘得到 $d_2\times c_2$ ， 依此类推。如图中方块部分所示，通道上的数据是所有这些结果的总和，任何站点想要接收的数据是发送方的编码和数据的乘积。

例如，假定站点 $1$ 和站点 $2$ 正在通话，站点 $2$ 想知道站点 $1$ 在说什么。它在通道中将数据和站点 $1$ 的编码 $d_1$ 相乘。因为 $c_1\times c_1=4$ ，但 $c_2\times c_1,c_3\times c_1,c_4\times c_1$ 都为 $0$ ，站点 $2$ 为了获取从站点 $1$ 传来的数据，还需将结果除以 $4$ 。
$$\text{data}=(d_1{c}_1+d_2{c}_2+d_3{c}_3+d_4{c}_4)\times c_1=d_1{c}_1{c}_1+d_2{c}_2{c}_1+d_3{c}_3{c}_1+d_4{c}_4{c}_1=4\times d_1$$

3. 芯片

CDMA基于编码理论。每个站点被指定一个编码，编码是一个被称之为芯片 chips 的数字序列，如图12.24所示。图中的编码是上一个例子中的。

后面的内容还会介绍如何选择序列。现在，我们需要知道的是：序列的选择并非随机的，它们是被谨慎选择的，它们被称为正交序列 orthogonal sequences ，有以下的特性：

1. 每个序列有 $N$ 个元素，而 $N$ 正是站点的数量。
2. 如果将序列乘以一个数，序列中的每个元素都乘以这个数。这称为序列和标量的乘积。例如，$$2\times [+1+1?1?1]=[+2+2?2?2]$$
3. 如果将两个相同序列的元素逐个相乘，并将结果相加，结果为 $N$ ， 而 $N$ 是每个序列中元素的数量，也是站点的数量。这就是两个相同序列的内积。例如，$$[+1+1?1?1]\times [+1+1?1?1]=1+1+1+1=4$$
4. 如果将两个不同序列的元素逐个相乘，并将结果相加，结果为 $0$ 。这就是两个不同序列的内积。例如，
   $$[+1+1?1?1]\times [+1+1+1+1]=1+1?1?1=0$$
5. 将两个序列相应的元素相加，结果是另一个序列。例如，
   $$[+1+1?1?1]+[+1+1+1+1]=[+2+200]$$

4. 数据的表示

我们遵循的编码规则：如果一个站点发送位 $0$，编码为 $?1$ ，如果发送位 $1$，编码为 $+1$ 。当站点空闲时，它不发送信号，编码为 $0$ 。如图山5所示。

5. 编码和解码

作为一个简单的例子，我们来看看四个站点如何在 $1$ 位间隔 a 1-bit interval 内共享链路。可以在额外的时间间隔，很容易地重复这个过程 The procedure can easily be repeated for additional intervals 。我们假定站点 $1$ 和站点 $2$ 正在发送 $0$ 位，站点 $4$ 正发送 $1$ 位，而站点 $3$ 是静止的。发送方的数据被依次编码为 $?1,?1,0,+1$ 。每个站点将相应的数与它的芯片序列（正交序列）相乘，这对每个站点来说都是唯一的。结果是产生一个新的序列，并被发送到通道上。为了简化，我们假定所有的站点在同一时点发送结果序列。通道上的序列是所有四个序列的总和。图12.26说明了该种情况。

现在假定静止的站点 $3$ 正在"听"站点 $2$ 。站点 $3$ 将通道上的数据乘以站点 $2$ 的编码 $[+1?1+1?1]$ ，得到：$$[?1?1?3+1]\times [+1?1+1?1]=?4/4=?1?位0$$

6. 信号水平

如果我们说明了每个站点产生的数字信号、及目的地所恢复的数据（见图12.27） ，就能更好的理解这个过程。图中显示了每个站点相应的信号（为简化使用了 NRZ-L）以及在公共通道中的信号。

图12.28显示了，通过使用站点 $2$ 的编码，站点 $3$ 可以检测到来自站点 $2$ 的数据。「通道中的总数据」与「代表站点 $2$ 的芯片编码」的信号相乘（内积运算）产生一个新的信号。然后，站点将信号下的区域积分并相加 integrates and adds the area under the signal ，得到的值是 $?4$ ，$?4$ 除以 $4$ 的结果 $?1$ 代表位 $0$ 。

7. 序列的产生

为产生芯片序列，我们使用一张行列数相同的 Walsh 表，这是一张二维表（见图12.29）。

在 Walsh 表中，每一行是一个芯片序列。单芯片序列的 $W_1$ 有一行和一列。我们可以为 $W_1$ 选 $+1$ 或 $?1$ ，这里选 $+1$ 。根据 Walsh 表的通用规则和示例，如果我们知道 $N$ 序列 $W_N$ 的表，我们就能产生 $2N$ 序列 $W_{2N}$ 的表，如图12.29所示。

带上标线的 $\overline{W_N}$ 代表 $W_N$ 的反码，这里 $+1$ 的反码是 $?1$ ，而 $?1$ 的反码是 $+1$ 。图12.29也说明了我们如何从 $W_1$ 产生 $W_2$ 和 $W_4$ 。在我们选择了 $W_1$ 之后，$W_2$ 就能从四个 $W_1$ 中得出，最后一个是 $W_1$ 的反码。在 $W_2$ 产生之后，$W_4$ 就能从四个 $W_2$ 得出，最后一个是 $W_2$ 的反码。当然 ，$W_8$ 由四个 $W_4$ 组成，依此类推。注意，在 $W_N$ 产生后，会分配给每个站点「与某一行对应的芯片」。我们需要强调的是，（Walsh 表中的）序列个数 $N$ 需要是 $2$ 的幂次 $N=2^m$ 。

【例12.6】找出以下网络的芯片：1. 两个站点；2. 四个站点。
解：我们可以使用图12.29中的 $W_2$ 和 $W_4$ 。

1. 对于两个站点的网络，我们有 $[+1+1]$ 和 $[+1?1]$ 。
2. 对于四个站点的网络，我们有 $[+1+1+1+1],[+1?1+1?1],[+1+1?1?1]$ 和 $[+1?1?1+1]$ 。

【例12.7】如果在网络中有 $90$ 个站点，序列个数是多少?
解：序列个数需要是 $T$ 。我们可以选择 $m=7$ ，$N=2^7=128$ 。那么我们可以使用 $90$ 个序列作为芯片。

【例12.8】如果用通道中总的数据乘以发送方的芯片编码再除以站点个数，那么可以证明：接收站点能够接收特定发送方发送的数据。
解：让我们使用前面的四个站点的例子证明第一个站点。我们可以说通道上的数据 $D=d_1{c}_1+d_2{c}_2+d_3{c}_3+d_4{c}_4$ 。需要得到站点 $1$ 发送的数据的接收方用 $c_1$ 乘以这个数据。
$$\begin{array}{rl}D{c}_1& =(d_1{c}_1+d_2{c}_2+d_3{c}_3+d_4{c}_4)\times c1\\ & =d_1{c}_1{c}_1+d_2{c}_2{c}_1+d_3{c}_3{c}_1+d_4{c}_4+c_1\\ & =d_1\times N+d_2\times 0+d_3\times 0+d_4\times 0\\ & =d_1\times N\end{array}$$

当我们将结果除以 $N$ ，我们就得到 $d_1$ 。