在本章的简介中，我们注意到有两种类型的网络链路：**点对点链路和广播链路（point-to-point links and broadcast links）**。点对点链路由链路一端的单个发送方和链路另一端的单个接收方组成。已经为点对点链路设计了许多链路层协议；**点对点协议(point-to-point protocol，PPP)**和**高级数据链路控制(high-level data link control，HDLC)**是两种这样的协议。第二种类型的链路(广播链路)可以具有全部连接到相同的单个共享广播信道的多个发送和接收节点。**这里使用术语广播是因为当任何一个节点传输帧时，信道会广播该帧，而其他每个节点都会收到副本。**以太网和无线LAN是广播链路层技术的示例。在本节中，我们将从特定的链路层协议退回一步，首先研究对链路层至关重要的一个问题：如何协调多个发送和接收节点对共享广播信道的访问-**多路接入问题（multiple access problem）（译者注：也叫多路访问协议、多址接入协议）**。广播频道通常用于LAN中，即地理上集中在一栋建筑(或公司或大学校园)中的网络。因此，在本节结束时，我们将了解如何在LAN中使用多个访问信道。<br />我们都熟悉广播的概念--电视从发明之日起就一直在使用它。但传统电视是单向广播(即一个固定节点向多个接收节点发送)，而计算机网络广播信道上的节点既可以发送也可以接收。也许一个更贴切的人类对广播信道的类比是鸡尾酒会，许多人聚集在一个大房间(空气提供广播介质)里交谈和聆听。第二个很好的比喻是许多读者会熟悉的东西-教室-教师和学生类似地共享相同的单一广播媒体。这两种情况下的一个中心问题是确定谁可以讲话(即，传输到信道中)以及何时讲话。作为人类，我们进化出了一套精心设计的共享广播频道的协议：<br />“给每个人一个发言的机会。”<br />“在别人跟你说话之前，不要说话。”<br />“不要垄断谈话。”<br />“如果你有问题，请举手。”<br />“别人说话的时候不要插嘴。”<br />“别人说话的时候不要睡着。”<br />计算机网络类似地具有协议，即所谓的**多路接入协议（multiple access protocols）**，节点通过该协议来控制它们向共享广播信道的传输。如图6.8所示，各种网络设置(包括有线和无线接入网络以及卫星网络)都需要多个接入协议。虽然从技术上讲，每个节点都通过其适配器接入广播信道，但在本节中，我们将节点称为发送和接收设备。实际上，数百甚至数千个节点可以通过广播信道直接通信。<br /><br />**Figure 6.8 ♦ Various multiple access channels**<br />**图6.8.♦各种多址接入通道**<br />因为所有节点都能够传输帧，所以两个以上的节点可以同时传输帧。当这种情况发生时，所有节点同时接收多个帧；也就是说，传输的帧在所有接收器处发生**冲突（collision）**。通常，当发生冲突时，没有一个接收节点能够理解传输的任何帧；从某种意义上说，冲突帧的信号变得纠结在一起。因此，冲突中涉及的所有帧都会丢失，并且在冲突间隔期间会浪费广播信道。显然，如果许多节点想要频繁地传输帧，则许多传输将导致冲突，并且广播信道的大部分带宽将被浪费。<br />为了确保广播信道在多个节点活动时执行有用的工作，有必要以某种方式协调活动节点的传输。该协调工作由**多路接入协议（multiple access protocol）**负责。在过去的40年里，已经有数千篇论文和数百篇博士论文是关于多路接入协议的；对这一工作的前20年的全面调查是[ROM1990]。此外，由于不断出现新类型的链路，特别是新的无线链路，对多路接入协议的积极研究仍在继续。<br />多年来，在各种链路层技术中实施了数十种多路访问协议。然而，我们可以将几乎任何多路接入协议归类为以下三类之一：**信道划分协议、随机接入协议和轮流协议（channel partitioning protocols, random access protocols, and taking-turns protocols）**。我们将在以下三个小节中介绍这些类别的多路访问协议。<br />让我们通过注意，理想情况下，每秒R比特速率的广播信道的多路接入协议应该具有以下所需的特征来结束本概述：
- 当只有一个节点有数据要发送时，该节点的吞吐量为 R bps。
- 当M个节点有数据要发送时，这些节点中的每个节点的吞吐量都是R/M bps。这不一定意味着M个节点中的每个节点总是具有R/M的瞬时速率，而是每个节点在某个适当定义的时间间隔上应该具有R/M的平均传输速率。
- 该协议是分散的；也就是说，没有代表网络单点故障的主节点。
- 该协议很简单，因此实现成本不高。
6.3.1 信道划分协议 Channel Partitioning Protocols
回想一下我们在1.3节中的早期讨论，时分复用(time-division multiplexing，TDM)和频分复用(frequency-division multiplexing，FDM)是两种可用于在共享广播信道的所有节点之间划分广播信道带宽的技术。例如，假设信道支持N个节点，并且信道的传输速率为R bps。TDM将时间划分为时间帧（time frames），并将每个时间帧进一步划分为N个时隙（time slots）。(不应将TDM时间帧与发送适配器和接收适配器之间交换的链路层数据单元(也称为帧)混淆。为了减少混淆，在本小节中，我们将把交换的链路层数据单元称为数据包（packet）。)。然后，每个时隙被分配给N个节点中的一个。每当节点有数据包要发送时，它就会在循环的TDM帧中为其分配的时隙内传输数据包的比特。通常，选择时隙大小使得可以在时隙时间内发送单个数据包。图6.9显示了一个简单的四节点TDM示例。回到我们的鸡尾酒会类比，TDM监管的鸡尾酒会将允许一个派对常客在固定的时间段内发言，然后允许另一个派对常客在相同的时间内发言，以此类推。一旦每个人都有机会交谈，这种模式就会重复。
Figure 6.9 ♦ A four-node TDM and FDM example
图6.9♦四节点TDM和FDM示例
TDM很有吸引力，因为它消除了冲突，而且非常公平：每个节点在每个帧时间内都有R/N bps的专用传输速率。然而，它有两个主要缺点。首先，即使一个节点是唯一有数据包要发送的节点，它的平均速率也被限制在R/N bps。第二个缺点是节点必须始终在传输序列中等待轮到它-同样，即使它是唯一具有要发送帧的节点。想象一下，派对常客是唯一一个有话要说的人(想象一下，这是一种更罕见的情况，每个人都想听那个人说什么)。显然，对于这一特定方来说，TDM是多路接入协议的糟糕选择。
当TDM在时间上共享广播信道时，FDM将Rbps信道分成不同的频率(每个频率具有R/N的带宽)，并将每个频率分配给N个节点中的一个。因此，FDM从单个较大的Rbps信道中创建N个较小的R/Nbps信道。FDM既有TDM的优点，也有TDM的缺点。它避免了冲突，并在N个节点之间公平地分配了带宽。然而，FDM也与TDM有一个共同的主要缺点—一个节点被限制为R/N的带宽，即使它是唯一有数据包要发送的节点。
第三个信道划分协议是码分多路接入(code division multiple access，CDMA)。TDM和FDM分别为节点分配时隙和频率，而CDMA为每个节点分配不同的代码。然后，每个节点使用其唯一代码对其发送的数据比特进行编码。如果仔细选择代码，CDMA网络就具有这样的奇妙特性：不同的节点可以同时传输，而且即使其他节点的传输受到干扰，它们各自的接收器也可以正确地接收发送器的编码数据比特(假设接收器知道发送器的代码)。CDMA在军事系统中已经使用了一段时间(由于它的抗干扰特性)，现在已经广泛用于民用，特别是在蜂窝电话中。由于CDMA的使用与无线信道紧密相关，我们将把CDMA技术细节的讨论留到第7章。现在，只要知道CDMA码，比如时分复用中的时隙和频分复用中的频率，都可以分配给多路接入信道用户就足够了。6.3.2 随机接入协议 Random Access Protocols
第二大类多路接入协议是随机接入协议（multiple access protocols）。在随机接入协议中，发送节点总是以信道的全速率，即Rbps进行发送。当发生冲突时，参与冲突的每个节点都会重复重传其帧(即数据包)，直到其帧通过而没有冲突。但是，当节点遇到冲突时，它不一定立即重新传输帧。取而代之的是，它在重传帧之前等待随机延迟。冲突中涉及的每个节点选择独立的随机延迟。因为随机延迟是独立选择的，所以其中一个节点可能会选择一个比其他冲突节点的延迟小得多的延迟，并因此能够在没有冲突的情况下将其帧偷偷放入信道中。
文献[ROM1990；Bertsekas 1991]中描述的随机访问协议即使不是数百，也有几十种。在本节中，我们将描述几个最常用的随机接入协议-ALOHA协议[Abramson 1970；Abramson 1985；Abramson 2009]和载波侦听多路接入(CSMA)协议[Kleinrock1975b]。以太网[Metcalfe 1976]是一种流行且广泛部署的CSMA协议。时隙ALOHA Slotted ALOHA
让我们从最简单的随机访问协议之一—时隙（slotted）ALOHA协议开始我们对随机接入协议的研究。在我们对时隙ALOHA的描述中，我们假设如下：
- 所有帧都恰好由L个比特组成。
- 时间被分成大小为L/R秒的时隙(即，一个时隙等于传输一帧的时间)。
- 节点仅在时隙开始时开始传输帧。
- 这些节点是同步的，因此每个节点都知道时隙何时开始。
- 如果两个或多个帧在一个时隙中发生冲突，则所有节点都会在该时隙结束之前检测到冲突事件。
设p为概率，即0到1之间的一个数，每个节点的时隙ALOHA的运算很简单：
- 当节点有新的帧要发送时，它会等待到下一个时隙的开始，并在该时隙中传输整个帧。
- 如果没有冲突，则节点已成功传输其帧，因此不需要考虑重新传输该帧。(节点可以准备用于传输的新帧(如果有)。)
- 如果存在冲突，节点将在时隙结束之前检测到冲突。该节点在每个后续时隙中以概率p重发其帧，直到该帧在没有冲突的情况下被发送。
通过概率p重发，我们的意思是节点有效地抛出一个有偏向的硬币；事件头对应于“重发”，这以概率p发生。事件尾部对应于“跳过这个时隙，在下一个时隙中再次抛硬币”；这以概率(1-p)发生。所有参与冲突的节点都独立地抛出硬币。
时隙ALOHA似乎有很多优点。与信道划分不同，时隙ALOHA允许节点在该节点是唯一活动节点时以全速率R连续发送。(如果节点有帧要发送，则该节点称为活动节点。)。时隙ALOHA也是高度分散的，因为每个节点都会检测冲突并独立决定何时重传。(不过，时隙ALOHA确实需要在节点中同步时隙；稍后我们将讨论ALOHA协议的非时隙版本，以及CSMA协议，它们都不需要这种同步。)。时隙ALOHA也是一种极其简单的协议。
时隙ALOHA在只有一个活动节点时工作得很好，但当有多个活动节点时效率如何？这里有两个可能的效率问题。首先，如图6.10所示，当有多个活动节点时，一部分时隙将发生冲突，因此将被“浪费”。第二个顾虑是时隙的另一部分将是空的，因为作为概率传输策略的结果，所有活动节点都不进行传输。唯一的“未浪费”时隙将是其中正好有一个节点进行传输的那些时隙。恰好有一个节点在其中进行传输的时隙被称为成功时隙（successful slot）。时隙多路接入协议的效率（efficiency）被定义为在存在大量活动节点的情况下成功时隙的长期运行分数，每个活动节点总是有大量帧要发送。请注意，如果不使用任何形式的接入控制，并且每个节点在每次冲突后立即重新传输，则效率将为零。时隙ALOHA显然将效率提高到了零以上，但是提高了多少呢？
Figure 6.10 ♦ Nodes 1, 2, and 3 collide in the first slot. Node 2 finally succeeds in the fourth slot, node 1 in the eighth slot, and node 3 in the ninth slot
图6.10♦节点1、2和3在第一个插槽中冲突。节点2最终在第四个插槽中成功，节点1在第八个插槽中成功，节点3在第九个插槽中成功
现在，我们继续概述时隙ALOHA的最大效率的推导。为简单起见，让我们稍微修改一下协议，并假设每个节点尝试在每个时隙中以概率p发送一个帧。(也就是说，我们假设每个节点总是有一个帧要发送，并且该节点以概率p发送新帧以及已经遭受冲突的帧。)。假设有N个节点。则给定时隙是成功时隙的概率是节点之一发送而其余N-1个节点不发送的概率。给定节点发送的概率是p；其余节点不发送的概率是(1-p)N-1。因此，给定节点成功的概率是p(1-p)N-1。因为有N个节点，所以N个节点中的任何一个成功的概率是NP(1-p)N-1。
因此，当存在N个活动节点时，时隙ALOHA的效率为Np(1-p)N-1。要获得N个活动节点的最大效率，我们必须找到使该表达式最大化的p。(有关此推导的大致轮廓，请参阅作业问题。)。为了在大量活动节点的情况下获得最大效率，当N趋于无穷大时，我们取NP(1-p*)N-1的极限。(同样，请参阅作业问题。)。执行这些计算后，我们将发现协议的最大效率为1/e=0.37。也就是说，当大量节点有许多帧要传输时，那么(充其量)只有37%的时隙做有用的工作。因此，信道的有效传输速率不是Rbps，而是只有0.37Rbps！一项类似的分析还显示，37%的时隙为空，26%的插槽发生冲突。想象一下，贫穷的网络管理员购买了100 Mbps的时隙ALOHA系统，期望能够使用网络在大量用户之间以例如80 Mbps的聚合速率传输数据！虽然该信道能够以100 Mbps的全信道速率传输给定帧，但从长远来看，该信道的成功吞吐量将低于37 Mbps。
ALOHA
时隙ALOHA协议要求所有节点同步它们的传输以在时隙的开始处开始。第一个ALOHA协议[Abramson 1970]实际上是一个非时隙的、完全分散的协议。在纯ALOHA中，当帧第一次到达(即，网络层数据报在发送节点从网络层向下传递)时，该节点立即将整个帧传输到广播信道中。如果传输的帧与一个或多个其他传输发生冲突，则该节点将立即(在完全传输其冲突的帧之后)以概率p重传该帧。否则，该节点等待帧传输时间。在此等待之后，它然后以概率p发送帧，或者以概率1-p等待(保持空闲)另一个帧时间。
为了确定纯ALOHA的最大效率，我们将重点放在单个节点上。我们将做出与时隙ALOHA分析中相同的假设，并将帧传输时间作为时间单位。在任何给定时间，节点正在发送帧的概率是p。假设该帧在时间t0开始发送。如图6.11所示，为了成功传输该帧，没有其他节点可以在时间间隔[t0-1，t0]内开始传输。这样的传输将与节点i的帧的传输的开始部分重叠。所有其他节点在该间隔内不开始传输的概率是(1-p)N-1。类似地，当节点i正在传输时，没有其他节点可以开始传输，因为这样的传输将与节点i的传输的后半部分重叠。所有其他节点在该间隔内没有开始传输的概率也是(1-p)N-1。因此，给定节点成功传输的概率是p(1-p)2(N-1)。通过对时隙ALOHA协议进行求极限，我们发现纯ALOHA协议的最大效率为1/(2e)-恰好是时隙ALOHA协议的一半。这就是完全分散的ALOHA协议要付出的代价。
Figure 6.11 ♦ Interfering transmissions in pure ALOHA
图6.11♦纯ALOHA中的干扰传输
载波侦听多路访问 Carrier Sense Multiple Access (CSMA)
在时隙ALOHA和纯ALOHA中，节点的传输决定独立于连接到广播信道的其他节点的活动。具体地说，当一个节点开始传输时，它既不会注意另一个节点是否恰好正在传输，也不会在另一个节点开始干扰它的传输时停止传输。在我们的鸡尾酒会类比中，ALOHA协议非常像一个粗鲁的派对常客，无论其他人是否在交谈，他都会继续喋喋不休。作为人类，我们有人类的礼仪，这些礼仪不仅让我们的行为更有礼貌，而且还可以减少在对话中相互“冲突”的时间，从而增加我们在对话中交换的数据量。具体地说，礼貌的人类对话有两条重要规则：
- 说话之前先听一听（Listen before speaking）。如果其他人正在发言，请等到他们发言完毕。在网络世界中，这称为载波侦听（carrier sensing）-节点在传输之前侦听信道。如果来自另一个节点的帧当前正在传输到信道中，则节点会等待，直到它在短时间内检测到没有传输，然后开始传输。
- 如果其他人同时开始说话，不要说话（If someone else begins talking at the same time, stop talking）。在网络世界中，这称为冲突检测（collision detection）-发送节点在发送时监听信道。如果它检测到另一个节点正在传输干扰帧，它将停止传输并等待一段随机时间，然后再重复空闲时检测和传输周期。
这两个规则体现在载波侦听多路访问(carrier sense multiple access，CSMA)和具有冲突检测的CSMA(CSMA with collision detection，CSMA/CD)协议族中[Kleinrock1975b；Metcalfe1976；LAM1980；ROM1990]。已经提出了CSMA和CSMA/CD的许多变体。在这里，我们将考虑CSMA和CSMA/CD的一些最重要、最基本的特征。
CASE HISTORY 历史案例 NORM ABRAMSON AND ALOHANET 诺姆·艾布拉姆森与ALOHA内网 诺姆·艾布拉姆森(Norm Abramson)是一名博士生工程师，他热爱冲浪，对数据包交换感兴趣。这种兴趣的结合将他带到了1969年的夏威夷大学。夏威夷由许多多山岛屿组成，这使得安装和运营陆上网络变得困难。在不上网的时候，艾布拉姆森想到了如何设计一个通过无线电进行数据包交换的网络。他设计的网络有一台中央主机和几个分散在夏威夷群岛的从属节点。该网络有两个信道，每个信道使用不同的频段。下行链路信道（downlink channel）将数据包从中央主机广播到从属主机，而上行流信道（upstream channel ）将数据包从从属主机发送到中央主机。除了发送信息性数据包外，中央主机还在下行通道上为从从属主机成功接收的每个数据包发送确认。 由于从属主机以分散的方式传输数据包，因此在上行信道上不可避免地会发生冲突。这一观察结果促使艾布拉姆森设计了纯ALOHA协议，如本章所述。1970年，在ARPA的持续资助下，艾布拉姆森将他的ALOHAnet连接到了ARPAnet。艾布拉姆森的工作之所以重要，不仅是因为它是无线数据包网络的第一个例子，还因为它启发了鲍勃·梅特卡夫(Bob Metcalfe)。几年后，梅特卡夫修改了ALOHA协议，创建了CSMA/CD协议和以太网LAN。
关于CSMA，您可能会问的第一个问题是，如果所有节点都执行载波侦听，为什么会首先发生冲突？毕竟，只要一个节点检测到另一个节点正在发送，它就会停止发送。这个问题的答案可以用时空图来最好地说明[Molle 1987]。图6.12显示了连接到线性广播总线的四个节点(A、B、C、D)的时空图。横轴显示每个节点在空间中的位置；纵轴表示时间。<br /><br />**Figure 6.12 ♦ Space-time diagram of two CSMA nodes with colliding transmissions**<br />**图6.12♦CSMA节点冲突传输的时空图**<br />在时间t0，节点B感测到信道空闲，因为当前没有其他节点在发送。因此，节点B开始发送，其比特沿着广播介质在两个方向上传播。图6.12中B的比特随时间的增加而向下传播表明，B的比特实际沿广播介质传播(尽管速度接近光速)需要非零时间量。在时间t1(t1>t0)，节点D有帧要发送。虽然节点B当前在时间t1发送，但由B发送的比特尚未到达D，因此D在t1感测到信道空闲。因此，根据CSMA协议，D开始发送其帧。不久之后，B的传输开始干扰D在D的传输。从图6.12可以明显看出，**广播通道的端到端信道传播延迟（channel propagation delay ）-信号从一个节点传播到另一个节点所需的时间-将在决定其性能方面发挥关键作用。该传播延迟越长，载波侦听节点还不能侦听已经在网络中的另一个节点开始的传输的可能性就越大。**
具有冲突检测的载波侦听多路访问(CSMA/CD) Carrier Sense Multiple Access with Collision Detection (CSMA/CD)
在图6.12中，节点不执行冲突检测；即使发生冲突，B和D也会继续完整地传输其帧。当节点执行冲突检测时，它会在检测到冲突时立即停止传输。图6.13显示了与图6.12相同的场景，不同之处在于两个节点在检测到冲突后不久各自中止传输。显然，向多路接入协议添加冲突检测将有助于协议性能，因为它不会完整地传输无用的、损坏的(由于干扰来自另一个节点的帧)帧。
Figure 6.13 ♦ CSMA with collision detection
图6.13♦带冲突检测的CSMA
在分析CSMA/CD协议之前，现在让我们从连接到广播信道的适配器(在节点中)的角度总结其操作：
- 适配器从网络层获取数据报，准备链路层帧，并放置帧到适配器缓冲区。
- 如果适配器检测到通道空闲(即，没有信号能量从通道进入适配器)，则它开始传输帧。另一方面，如果适配器检测到信道繁忙，它将等待，直到没有检测到信号能量，然后开始传输帧。
- 在发送时，适配器监视是否存在来自使用广播信道的其他适配器的信号能量。
- 如果适配器在没有检测到来自其他适配器的信号能量的情况下传输整个帧，则适配器结束该帧。另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，它将中止传输(即停止传输其帧)。
- 中止后，适配器将随机等待一段时间，然后返回步骤2。
随机(而不是固定)等待时间的需要是显而易见的-如果两个节点同时传输帧，然后两个节点都等待相同的固定时间，则它们将永远继续冲突。但是，选择随机退避时间的合适时间间隔是多少呢？如果间隔较大而冲突节点的数量较少，则节点在重复空闲时检测和传输步骤之前可能会等待大量时间(信道保持空闲状态)。另一方面，如果间隔较小而冲突节点数量较多，则选择的随机值很可能几乎相同，发送节点将再次发生冲突。我们希望的是，当冲突节点数量较少时间隔较短，而当冲突节点数量较大时间隔较长。
在以太网和DOCSIS有线网络多路接入协议[DOCSIS 3.1 2014]中使用的二进制指数退避算法（binary exponential backoff algorithm）很好地解决了这一问题。具体地说，当发送已经经历了n次冲突的帧时，节点从{0，1，2，… , 2n-1}中随机选择K的值。因此，帧经历的冲突越多，从中选择K的间隔就越大。对于以太网，节点实际等待的时间量是K×512比特时间(即，将512比特发送到以太网中所需的时间量的K倍)，并且n可以采取的最大值被限制在10。
让我们来看一个例子。假设节点尝试第一次发送帧，并且在发送时检测到冲突。然后，该节点选择概率为0.5的K=0或概率为0.5的K=1。如果节点选择K=0，则它立即开始侦听信道。如果节点选择K=1，则它在开始空闲时检测和发送周期之前等待512比特时间(例如，对于100 Mbps以太网为5.12微秒)。在第二次冲突之后，以相等的概率从{0，1，2，3}中选择K。在三次碰撞之后，K以相等的概率从{0，1，2，3，4，5，6，7}中选择。在10次或更多碰撞之后，从{0，1，2，… ，1023}。因此，从中选择K的集合的大小随着冲突的数量呈指数增长；因此，该算法被称为二进制指数退避。
这里我们还注意到，每次节点准备要传输的新帧时，它都会运行CSMA/CD算法，而不考虑最近可能发生的任何冲突。因此，当其他几个节点处于指数退避状态时，具有新帧的节点将能够立即潜入成功的传输。
CSMA/CD效率 CSMA/CD Efficiency
当只有一个节点有帧要发送时，该节点可以以全信道速率发送(例如，对于以太网，典型速率是10 Mbps、100 Mbps或1Gbps)。然而，如果许多节点有帧要传输，则信道的有效传输速率可能要小得多。我们将CSMA/CD的效率（efficiency of CSMA/CD）定义为当存在大量活动节点且每个节点有大量帧要发送时在信道上无冲突地传输帧的长时间段。为了给出以太网效率的封闭近似形式，让dprop表示信号能量在任意两个适配器之间传播所需的最长时间。假设dtrans是传输最大大小的帧的时间(对于10 Mbps的以太网，大约1.2毫秒)。CSMA/CD效率的推导超出了本书的范围(参见[LAM 1980]和[Bertsekas 1991])。在这里，我们简单地陈述以下近似值：
我们从这个公式中看到，当dprop接近0时，效率接近1。这与我们的直觉相符，即如果传播延迟为零，冲突节点将立即中止，而不会浪费信道。此外，当dtrans变得非常大时，效率接近1。这也是直观的，因为当帧抢占信道时，它将在很长时间内保持信道；因此，信道将在大部分时间内进行生产性工作。
6.3.3 轮流协议 Taking-Turns Protocols
回想一下，多路接入协议的两个期望特性是(1)当只有一个节点活动时，活动节点具有Rbps的吞吐量，以及(2)当M个节点活动时，则每个活动节点具有接近R/Mbps的吞吐量。ALOHA和CSMA协议具有第一个属性，但没有第二个属性。这促使研究人员创造了另一类协议-轮流协议（taking-turns protocols）。与随机接入协议一样，有几十种轮流协议，每种协议都有许多变体。我们将在这里讨论两个更重要的协议。第一个是轮询协议（polling protocol）。轮询协议要求将其中一个节点指定为主节点。主节点以循环（polls）方式轮询每个节点。具体地说，主节点首先向节点1发送消息，说明它(节点1)可以发送最多某个最大数量的帧。在节点1传输一些帧之后，主节点告诉节点2它(节点2)可以传输最大数量的帧。(主节点可以通过观察信道上是否缺少信号来确定节点何时完成发送其帧。)。该过程以这种方式继续，其中主节点以循环方式轮询每个节点。
轮询协议消除了困扰随机接入协议的冲突和空隙。这允许轮询实现更高的效率。但它也有一些缺点。第一个缺点是该协议引入了轮询延迟-通知节点它可以传输所需的时间量。例如，如果只有一个节点是活动的，则该节点将以低于Rbps的速率发送，因为主节点必须在每次活动节点发送其最大帧数时轮询每个非活动节点。可能更严重的第二个缺点是，如果主节点发生故障，整个信道将无法运行。我们将在第6.3节中学习的蓝牙协议就是轮询协议的一个示例。
第二个轮流协议是令牌传递协议（token-passing protocol）。在该协议中没有主节点。称为令牌的小的专用帧以某种固定顺序在节点之间交换。例如，节点1可能总是将令牌发送到节点2，节点2可能总是将令牌发送到节点3，节点N可能总是将令牌发送到节点1。当节点接收到令牌时，它只在有一些帧要传输时才保留令牌；否则，它会立即将令牌转发到下一个节点。如果节点在收到令牌时确实有帧要传输，则它会发送最大数量的帧，然后将令牌转发到下一个节点。令牌传递是分散且高效的。但它也有自己的问题。例如，一个节点的故障可能会导致整个通道崩溃。或者，如果节点意外地忽略了释放令牌，则必须调用一些恢复过程来使令牌重新循环。多年来，已经开发了许多令牌传递协议，包括光纤分布式数据接口(FDDI)协议[Jain 1994]和IEEE 802.5令牌环协议[IEEE 802.5 2012]，每个协议都必须解决这些以及其他棘手的问题。
6.3.4 DOCSIS：有线互联网接入的链路层协议 DOCSIS: The Link-Layer Protocol for Cable Internet Access
在前面的三个小节中，我们已经了解了三大类多路接入协议：信道分区协议、随机接入协议和轮流协议。有线接入网络将成为这里的一个很好的案例研究，因为我们将在有线接入网络中找到这三类多路接入协议中每一类的各个方面！
回想一下第1.2.1节，有线接入网络通常将数千个住宅有线调制解调器连接到有线网络头端的有线调制解调器终端系统(cable modem termination system，CMTS)。有线数据服务接口规范(Data-Over-Cable Service Interface Specifications，DOCSIS)[DOCSIS 3.1 2014；Hamzeh 2015]规定了有线数据网络体系结构及其协议。DOCSIS使用FDM将下行(CMTS到调制解调器)和上行(调制解调器到CMTS)网段划分为多个信道。每个下行信道的带宽在24 MHz到192 MHz之间，每个信道的最大吞吐量约为1.6 Gbps；每个上行信道的信道宽度从6.4 MHz到96 MHz不等，最大上行吞吐量约为1 Gbps。每个上行和下行信道都是广播信道。由CMTS在下行信道上发送的帧由接收该信道的所有有线调制解调器接收；然而，由于只有一个CMTS发送到下行信道，因此不存在多路接入问题。然而，上行方向更有趣，在技术上也更具挑战性，因为多个有线调制解调器共享到CMTS的相同上行信道(频率)，因此可能会发生冲突。
如图6.14所示，每个上行信道被划分为时间间隔(类似TDM)，每个间隔包含一系列小型时隙，在此期间有线调制解调器可以向CMTS传输。CMTS明确地向各个电缆调制解调器授予在特定的迷你时隙期间进行传输的许可。CMTS通过在下行信道上发送称为MAP消息的控制消息来指定哪个电缆调制解调器(具有要发送的数据)可以在控制消息中指定的时间间隔内在哪个迷你时隙期间发送，来实现这一点。由于迷你时隙被明确分配给电缆调制解调器，因此CMTS可以确保在迷你时隙期间不存在冲突传输。
Figure 6.14 ♦ Upstream and downstream channels between CMTS and cable modems
图6.14♦CMTS和有线调制解调器之间的上行和下行信道
但是，CMTS如何知道哪些有线调制解调器首先需要发送数据呢？这是通过让有线调制解调器在专门用于此目的的一组特殊间隔迷你时隙期间向CMTS发送迷你时隙请求帧（mini-slot-request frames）来实现的，如图6.14所示。这些迷你时隙请求帧以随机接入方式发送，因此可能彼此冲突。有线调制解调器既不能检测上行信道是否繁忙，也不能检测冲突。取而代之的是，如果电缆调制解调器在下一个下行控制消息中没有接收到对所请求的分配的响应，则推断其迷你时隙请求帧经历了冲突。当推断出冲突时，有线调制解调器使用二进制指数退避将其迷你时隙请求帧的重新传输推迟到将来的时隙。当上行信道上的流量很少时，有线调制解调器实际上可以在名义上为迷你时隙请求帧分配的时隙期间发送数据帧(从而避免必须等待迷你时隙分配)。
因此，有线接入网络是多种接入协议的极好例子—FDM、TDM、随机接入和集中分配的时隙都在一个网络中！
若有收获，就点个赞吧
0 人点赞
