山东大学软件学院计算机网络知识总结第四章—介质访问控制子层_山东大学计算机网络

网络链路可以分成两大类：使用点到点连接和使用广播信道。

本章重点讨论广播网络和相应的协议。

广播信道有时候也称为多路访问信道( multiaccess channel) 或者随机访问信道（random access channel ）。

介质访问控制子层用来确定多路访问信道下一个使用者的协议属于数据链路层的一个子层，该层称为介质访问控制（MAC, Medium Access Control ）子层。

一.信道分配问题

静态信道假设（FDM,TDM）方式不适用于突发流量，需要动态分配信道的协议实现。

动态信道分配问题的假设：

• 流量独立：每个站独立产生流量
• 单信道假设：所有站共享同一信道
• 冲突假设：如果两帧“同时传输”（传输时间有重叠），会产生信号重叠造成信号混乱、不可识别，称为“冲突”。冲突使所有传输失败。
• 时间连续或分槽（离散）：如果时间连续，则在任何时刻可以开始传输数据；如果时间离散，则只能在某个时间槽的起始点开始传输。
• 载波侦听或不侦听：侦听判断当前信道是否空闲。

二.多路访问协议

1.介质访问控制基本解决思路：

介质访问控制问题的基本解决思路可以分为两种：基于冲突的和无冲突的解决方案。还有一种混杂协议结合这两种方案的特点—有限竞争协议。

基于冲突的解决方案没有事先约定的竞争顺序，各个站公平地竞争信道。此时，冲突不可避免。协议基于冲突解决各个站的发送顺序。这是本书的重点，经典以太网采用了这种解决思路。

无线局域网拥有不同于有线局域网的特点，冲突检测困难，信道侦听复杂，采用了类似于经典以太网但冲突避免的协议。

基于竞争解决MAC问题的几个关键思想：

• 时间离散化
• 随机发送
• 载波侦听（不干扰已有通信）
• 失败重传（基于冲突检测或基于确认是否回来）

经典以太网比较容易检测冲突，所以采用较为激进的1-坚持CSMA，冲突后使用2进制指数后退算法分解冲突；
无线局域网难于检测冲突，直接采用冲突避免的改进的p-坚持CSMA分解冲突；
交换式局域网采用缓存与合适的调度算法分解冲突。

无冲突解决下一个谁发送数据的方案：

各站点遵守事先确定的竞争规则，合理安排各个站发送数据的顺序，不会产生冲突。

基本位图法：在一个竞争周期内，如果某个站有数据发送，则当其对应的时槽到来时置1，错过则等待下一个竞争周期。竞争周期结束后，时槽置1的站轮流发送数据。需要事先安排各个站的编号及对应的竞争时槽。

令牌传递：所有站组成一个逻辑环，令牌按照某种方向在逻辑环上传递。获得令牌的站拥有发送数据的权力。发送完毕后，将令牌向后传递到下一个站。需要事先安排逻辑环上各个站的顺序。

二进制倒计数：每个站拥有一个逻辑地址，发送时各个站按位从高到低广播自己的逻辑地址。信道将所有地址位布尔或在一起。每个站将自己的地址位与布尔或后的位比较，自己地址位小的竞争失败并放弃发送后续的地址位。最终剩余的站竞争成功并随后发送数据。需要事先安排站的逻辑地址。

2.经典以太网使用的协议

经典以太网模型：

以太网遵守的协议：IEEE 802.3

无线局域网遵守的协议：802.11

经典以太网是最重要的一种局域网模式，通常工作在10Mbps。所有站点共享同一个传输介质（信道），采用基带信号，采用广播传输技术。即每个站将自己发送的数据通过收发器发送到传输介质上，信号占用信道所有带宽，信号沿传输介质传递到每个站点。当两个或多个站同时传输信号，则会发生信号叠加，造成接收方接收失败。所有传输都会失败。

经典以太网每个时刻只允许一个站点发送数据。没有事先规定的竞争顺序，允许竞争时产生冲突，并基于冲突解决介质访问控制问题。

a.纯ALOHA（想说就说）

纯ALOHA协议：当站点有数据要发送时就发送。如果多个用户同时发送则会发生冲突造成发送失败。发送失败后（发送站会依靠某种方法得知），等待一段随机时间再次发送。等待一段随机时间为了有效解决冲突。

如果系统中多个用户共享同一个信道的方法会导致冲突，则这样的系统称为竞争（ contention)系统。

无论何时，只要两个帧在相同时间试图占用信道，冲突就会发生（如上图 所示），并且两帧都会被破坏。

如果新帧的第一位与几乎快传完的前一帧的最后一位重叠，则这两帧都将被彻底毁坏（即具有不正确的校验和），稍后都必须被重传。校验和不可能（也不应该）区分出是完全损坏还是局部差错。坏了就是坏了。

效率：很低，18%的帧能够顺利发送。

b.分槽ALOHA

分槽ALOHA协议：是纯ALOHA协议的改进。将时间离散化，分为时间槽（一段事先规定的时间）。只有在时间槽的起始点可以发送。通过推迟发送时间，避免连续时间发送带来的某些冲突。

取得同步时间的一种办法是由一个特殊的站在每个间隔起始时发出一个脉冲信号，就好像一个时钟一样。

效率：依然很低；使用分槽 ALOHA，我们期望的最好结果是 37%空时间槽、 37%为成功，剩下 26%为冲突。

c.载波侦听多路访问协议（CSMA，Carrier Sense Multiple Access）（先听后说）

为了不打扰已有的通信，站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，代表有其它站点在发送数据，则不能发送，等待一段随机时间发送。

根据贪婪程度和处理策略不同，分为：

• 1-坚持CSMA
• 非坚持CSMA
• p-坚持CSMA

1-坚持CSMA：站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，则继续侦听，直到信道空闲，立即发送。1-坚持CSMA协议避免打扰已有的通信，但是不能完全避免冲突。

1-坚持CSMA只是将连续时间上的冲突压缩到前一个数据传递完毕（一个时刻）。

假如现在站点A正在发送数据，站点B想要发送数据，先侦听信道，信道忙，则站点B持续侦听信道。接着（或“同时”）站点C也有数据要发送，执行同样的协议。当站点A发送完毕后，站点B和C都侦听到信道空闲，都会选择立即发送。结果，站点B和C发送数据冲突，都会发送失败。

非坚持CSMA：站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，则等待一段随机时间再来侦听。

非坚持CSMA协议不再在信道忙时坚持侦听信道，而是等待一段随机时间再来侦听。能够有效避免1-坚持CSMA协议不能真正分解冲突的问题。

非坚持CSMA协议在提高整个系统吞吐量（系统在单位时间内能够真正完成的数据传输次数）的同时，可能会带来较大的延迟（对每一次数据传输而言）。

p-坚持CSMA：适用于时间分槽系统。站点在发送数据之前首先侦听信道。如果信道空闲，则以概率p发送数据；以概率1-p推迟到下一个时槽；重复以上过程，直到发送出去或听到信道忙。如果信道忙，则等待一段随机时间再来重复以上协议。

持续侦听，概率p发送。

p-坚持CSMA协议可以有效分解潜在的可能的冲突。由于每个站点都运行这个协议，选择了不同的发送时间槽，两个或多个站同时选择一个时间槽的概率随着p的变小而降低。可以提高吞吐量，但可能带来更大的延迟。

d.带冲突检测的CSMA协议—CSMA/CD（边说边听）

先听后说（CSMA）协议要求所有有数据发送的站点侦听到信道空闲时才能发送数据，从而不会打扰已有的通信过程，但是不能完全避免冲突（不能保证站点发送一定成功，或成功获得信道的使用权），尤其是当多个站点同时侦听到信道空闲。

当两个帧发生冲突时，两个被损坏帧继续传送毫无意义，而且信道无法被其他站点使用，对于有限的信道来讲，这是很大的浪费。如果站点边发送边监听，并在监听到冲突之后立即停止发送，并立即进入竞争周期，尽快得到竞争解决方案，可以提高信道的利用率，因此产生了CSMA/CD。

边说边听的实现机制：发送方一边向信道发送（说）数据，一边从信道上读取（听）数据，通过判断双方是否一致来判断是否发生了冲突。

边说边听：所有站点还要同时运行冲突检测（CD, Collision Detection）协议，边发送数据（竞争信号）边检测信道上是否发生了冲突。如果听到冲突，则表明还有其它站点“同时”发送数据，代表本次发送失败（所有发送站点都会意识到这一点）。听到冲突的站点立即停止发送（提高效率），运行BEB协议分解冲突。

如果站点在发送过程中没有听到冲突，则认为本次发送成功（或取得总线的控制权）。

e.二进制指数后退（BEB协议）

竞争期使用BEB协议：

站点运行CSMA/CD协议，听到冲突后进入竞争周期，时间离散为多个时间槽。如果第一次冲突，则参与竞争的站点在随后的两个时间槽内随机选择一个发送，发送前依然要侦听信道是否空闲。排在最前面的只有一个竞争者的时间槽对应的竞争者竞争成功，随后抓住信道发送数据，其它竞争者等到选择的竞争时间槽时侦听信道为忙，只能等待已有通信完成再次尝试发送。

当一个时间槽有两个竞争者都会听到冲突，全部竞争失败。竞争失败的站点将随机等待的时间槽数加倍，然后从中随机选择一个参与竞争，直到竞争成功或达到最大竞争次数。

二进制指数后退指的是每次冲突后随即后退的时间槽翻倍，直到1024个时间槽。如果在1024个时间槽运行6次依然解决不了冲突，则认为网络坏了。

竞争周期时间槽的时间应该远远小于普通帧长。这样能够减少冲突带来的消耗，提高信道使用效率。

竞争周期的最后结果是某一个站点获得信道使用权。

e.最小帧长

发送方必须发送的最小时间对应着必须发送的最少数据，称为最小帧长。

最小帧长计算（以10M以太网为例）应该适用于所有的以太网。常见的组网介质为：粗缆、细缆和双绞线。在10M速率下，粗缆、细缆和双绞线的最大传输距离分别为500米、185米和100米。为了拓展网络规模，增加信号的传输长度，引入了第一个网络设备—中继器（集线器）。中继器的功能是将信号的能量补足再传输出去，最多能够使用4个中继器。以太网最大的网络规模（信道的最大长度）分别为2500米、925米和500米（如果集线器不支持再生信号则为200米）。

最小帧长计算应该选用10base5以太网。即4个中继器连接的5段粗缆，每段500米。

最小帧长为64个字节。最大帧长选定为1518字节。

经典以太网MAC子层协议中帧的结构

广播和组播：地址字段分为目的地址和源地址。目的地址的第一位如果是0，表示这是一个普通地址，如果是1表示这是一个组地址。往一组地址的发送行为成为组播，由全1组成的特殊地址保留用作广播，被网络上的所有站接收。

3.交换式以太网

需要掌握中继器，网桥的工作过程，以及MAC端口映射表的知识。

4.无线局域网

无线局域网对应的标准为IEEE 802.11，也称为WiFi。

无线局域网工作在无需授权许可的ISM（Industrial Scientific and Medical）频段上。发送功率受限，易受其它电气设备干扰。

网络分为带有接入点AP（Access Point）或基站（base station）的网络（有架构模式），和没有接入点的网络（ad hoc）（自组织模式）两种工作模式。

a.带有接入点的网络模式：

带有接入点的网络模式中任意两个站点通信通过AP。隐含的假设为：所有站点都应该在AP的信号覆盖范围内，所有站点的信号范围能够覆盖AP。发送方首先将数据发送给AP，AP将数据再转发给接收方。AP之间通过有线连接。

b.没有接入点的网络（ad hoc）模式

ad hoc网络模式中任意两个站点可以直接通信。属于自组织网络。当AP不再作为网络内部任意两个站点通信的转发站点，只作为外部站点的代理时，AP和网内其它站点也组织为ad hoc网络模式

无线局域网只使用一个信道，支持广播传输模式。

无线局域网形式上类似于经典以太网，那么经典以太网的介质访问控制协议CSMA/CD是否能够直接应用于无线局域网？

不能。

原因：

无线和有线局域网的区别：

• 无线局域网的站点的信号可能无法覆盖所有的其它站点；而有线局域网任意站点发送的信号都能够到达其它所有站点。

• 冲突的本质是接收方接收到两路或多路信号时就会发生冲突。CSMA/CD的本质是发送方判断是否发生了冲突。

• 而无线通信系统通常不能检测出正在发生的冲突。站接收到的信号可能很微弱，也许比它发出去的信号弱 百万倍。要发现这样的冲突信号就像在海上寻找涟漪样的困难。相反，确认机制可用在事后发现冲突和其他错误。

• 使用无线 LAN 的一种单纯想法是尝试使用 CSMA：

  每个站侦听是否有其他站在传输，并且只有当没有其他站在传送数据时它才传输。

  这种方法的麻烦在于协议并未考虑无线传输特性，因为这里的冲突发生在接收方，而不是发送方。

无线局域网需要解决以下几个挑战：

冲突判断:不能直接使用“边说边听”方式来判断是否发生了冲突，因为可能根本听不到冲突（半双工）。事后确认来判断，如果发送后能够收到确认，则认为没有发生冲突；否则认为发生了冲突（无论是真的发生了由于站点竞争引起的冲突还是其它电气设备带来的噪声干扰，都可以认为发生了冲突）。由于整帧发送完成才能知道是否发生冲突，需要尽量避免可能的冲突发生。

冲突避免1:需要事先判断接收方是否空闲，并在接收期间避免其它站点贸然发送带来的干扰。（类似于CSMA，但更加复杂）

冲突避免2:当可能有多个站点同时竞争信道时，需要事先避免冲突的策略。（类似于p-坚持CSMA的随机后退策略）。每个站点随机选择发送的时间，减少多个站点同时发送引发冲突的概率。

MACA协议：冲突避免多路访问协议

MACA 的基本思想是发送方剌激接收方输出一个短帧，以便其附近的站能检测到该次传输，从而避免在接下去进行的（较大）数据帧传输中也发送数据。这项技术被用来替代载波侦听。

为了减少究竟哪个站在发送的模糊不清， 802.11 定义信道侦听包括物理侦听和虚拟侦听两部分。

物理侦听：只是简单地检查介质，看是否存在有效的信号。

虚拟侦听：每个站可以保留一个信道何时要用的逻辑记录，这是通过跟踪**网络分配向量（NAV, NetworkAllocation Vector ）**获得的。每个帧携带一个 NAV 宇段，说明这个帧所属的一系列数据将传输多长时间。无意中听到这个帧的站就知道无论自己是否能够侦听到物理信号，由 NAV所指出的时间段信道一定是繁忙的。例如，一个数据帧的 NAV 给出了发送一个确认所需要的时间。所有听到该数据帧的站将在发送确认期间推迟发送，而不管它们是否能昕到确认的发送。

MACA存在的问题：依然会有冲突。

如果两个站点同时发送给一个站点RTS帧，会发生冲突，两个发送站点都接收不到CTS帧。这时需要分解冲突。

无线局域网采用了随机后退策略，类似于p-坚持的CSMA协议+二进制指数后退协议。P-坚持用于事先尽量避免冲突，二进制指数后退用于发生冲突后的随机时间选择。

CSMA/CA（冲突避免）

为了克服无法根据冲突检测（CD）来判断发送是否成功的障碍，CSMA/CA协议使用CA协议，即尽量减少冲突的可能。主要包含下面技术：

• 随机选择发送时间。不像经典以太网听到空闲就发送，而是开始时就随机选择发送时间来避免大多数的冲突；
• 短帧发送。CSMA/CA协议采用离散时间，每次数据传输时间不超过时槽的长度。一方面可以保证每次发送的成功率；另一方面可以支持公平，提高效率；
• 确认机制。接收方正确接收到数据后，立即发送一个确认短帧，因为发送方没有其它手段判断自己的发送是否成功。发送数据的时间+确认时间不大于一个时槽的时间。

通过这几个技术，CA协议达到CD协议相似的效果：即发送方能够判断本次发送成功还是失败重传。