Media Access Control Sublayer (介质访问控制子层)：
负责决定谁在多路访问链路上发送下一个消息
链路层的重要组成部分，特别是对于局域网
局域网特别是无线局域网中MAC非常重要，因为无线信道是广播信道
广播信道也称为多路访问信道（multiaccess channel）或者随机访问信道（random access channel）
介质访问控制（MAC）：用于在多路访问信道问题上确定下一个使用者的问题。
4.1 信道分配问题
静态和动态信道分配
4.1.1 静态信道分配
在有N个用户的静态信道：
使用FDM，TDM，CDMA等多路复用的方式将带宽分配成N等分
静态的信道分配使每个用户获得固定的信道
静态信道分配是低效的：
- 分配给一些用户的信道有时候没有被使用
- 在静态信道分配中，如果有的用户不再使用信道，信道也不能被其他用户使用
静态信道分配（FDM,TDM）方式不适用于突发流量，需要动态分配信道的协议实现
4.1.2 动态信道分配模型的假设
- 流量独立 Independent traffic：N 个独立的站（计算机、电话）组成，每个站独立产生流量；帧的到达是独立的
- 单信道假设 Single channel：所有站共享同一信道，可发送可接收
- 冲突可观察假设 Observable collisions：如果两帧 “同时传输”（传输时间有重叠），会产生信号重叠造成信号混乱、不可识别，称为 “冲突”。冲突使所有传输失败，除了冲突产生错误，不会再有其他错误。所有站都可以检测到冲突的发生。而且发生冲突需要重新传输。
- 时间连续或分槽（离散）Continuous or slotted time：如果时间连续，则在任何时刻可以开始传输数据；如果时间离散，则只能在某个时间槽的起始点开始传输。
- 载波侦听或不侦听 Carrier sense：侦听判断当前信道是否空闲，一个站在试图使用信道之前知道该信道是否被使用。
动态信道分配模型根据用户的需求分配信道
4.2 多路访问协议
4.2.1 ALOHA
ALOHA
pure ALOHA（纯 ALOHA）
先说后听
基本思想：在纯ALOHA（纯ALOHA）中，用户只要有数据就发送帧；用户在随机冲突时间后重试
在低负载下高效低延迟
当其他用户在两倍于帧时间的易受攻击时段进行传输时，就会发生冲突
将发送器同步到插槽可以减少冲突
分槽 ALOHA
将时间分成离散的间隔（时间槽），每个时间槽对应一帧。
用户要遵守统一的时间槽边界。
系统中有一个特殊的站在每个间隔起始时刻发出一个脉冲信号。
用户需要等待下一个时间槽开始时刻发送数据。
易受冲突期减少了一半。
分槽ALOHA的效率是纯ALOHA的两倍
- 低负载会浪费插槽，高负载会导致碰撞
- 随机流量模型的效率高达1/e（37%）
4.2.2 CSMA（载波侦听多路访问协议）
先听后说
检测其他站点，调整自己的动作
CSMA
1-Persistence CSMA
① 当一个站有数据要发送时先侦听信道
② 若信道空闲，立即发送数据
③ 若信道忙，持续监听等待直至信道变为空闲
④ 若发生冲突，等待随机时间，返回步骤 1
1-persistence 代表出现信道空闲，传输数据的概率为 1
如果 2 个以上的站在某个站传输数据过程中准备好了数据，在空闲到来时会产生冲突
若传输延迟大，第一个站的信号没有到达第二个站时，后者认为信道是空闲的，发送数据导致冲突（带宽延迟积越大，越严重）
Non-Persistence CSMA
① 当一个站有数据要发送时先侦听信道
② 若信道空闲，立即发送数据
③ 若信道忙，不持续监听，等待一个随机时间返回步骤 1
④ 若发生冲突，等待随机时间，返回步骤 1
与 1-Persisitence CSMA 相比，Non-persistence CSMA 的信道利用率更好（冲突发生概率低），但延迟更大（更多的随机等待）
P-Persistence CSMA
p-Persistence 适用于分时间槽的信道
① 当一个站有数据要发送时先侦听信道
② 若发现信道空闲，在下一个时间槽到达时，以 p 的概率发送数据，有 q=1-p 的概率，将发送推迟到下一个时间槽
③ 在新的时间槽如果还是空闲，依然以 p 的概率发送数据，q 的概率推迟。
④ 以上过程一直重复直到发出，或有其他站发送数据，随即等待一段时间，重复以上步骤
p-Persistence 的 p 越小，信道利用率越高，但带来的延迟也越大
p=1 时与 1-Persistence CSMA 等价，但是 p=0 时不与 Non-Persistence CSMA 等价
CSMA/CD （Carrier Sense Multiple Access with Collision Detection，带冲突检测的载波侦听多路访问）
边听边说
两个站都侦听到信道为空，并且开始传输。信号会产生冲突
每个站检测到发生冲突后立即停止传输帧，并发送一个拥塞信号，通过二进制指数后退算法确定等待时间后重新开始监听信道。
站的硬件在传输时监听信道，读回的信号不同于发送的信号说明发生了冲突。
当一个站传输了 2𝝉 的时间后可以确定不会发生冲突了（ 𝝉 是网络中两个最远站点之间数据传输需要的时间）
也就是说所有站点都发现信道被占用
考虑到信号传输的延迟，最开始发的时候会有还没接收到信号的站点认为信道空闲
2𝝉 的时间是传输与回传的时间
所以我们可以让发送的帧足够大，传到以太网最远端时仍在发送。（我们可以计算出最小帧长）
CSMA/CD的发送流程可以概括为：
- 先听后发
- 边听边发
- 冲突停止
- 延迟重发
CSMA/CD 控制方式的优点是：
原理比较简单，技术上易实现，网络中各工作站处于平等地位 ，不需集中控制，不提供优先级控制。但在网络负载增大时，发送时间增长，发送效率急剧下降
CSMA/CD 跟非坚持的 CSMA 区别在于听与说的关系，非坚持的 CSMA 发送时也会有传输延迟的问题，但并不会管是否发生了冲突，若一定时间内没有收到确认，则尝试重发即可。CSMA/CD 监听到冲突后会立即停止重发。
4.2.3 无冲突协议
无冲突的解决方案各站点遵守事先确定的竞争规则，合理安排各个站发送数据的顺序，不会产生冲突。包括以下几个协议：
基本位图法 Bitmap
在一个竞争周期内，如果某个站有数据发送，则当其对应的时槽到来时置 1，错过则等待下一个竞争周期。竞争周期结束后，时槽置 1 的站轮流发送数据。 需要事先安排各个站的编号及对应的竞争时槽。
基本位图协议：
如果发送方有数据，则在争用时隙中设置一个位
发件人依次发送；每个人都知道谁有数据
高位的站预期的等待时间低于低位的站
令牌传递
所有站组成一个逻辑环，令牌按照某种方向在逻辑环上传递。获得令牌的站拥有发送数据的权力。发送完毕后，将令牌向后传递到下一个站。需要事先安排逻辑环上各个站的顺序。
带有令牌的站点可以在通过前发送一帧
Idea也可以在没有响铃的情况下使用，例如token bus
为了阻止帧进入无限的循环，接收站或者发送站要把数据从循环中取下
所有站的预期等待时间相同
二进制倒计数：
每个站拥有一个逻辑地址，发送时各个站按位从高到低广播自己的逻辑地址。信道将所有地址位布尔或（只要有一个/多个1，结果就是1）在一起。每个站将自己的地址位与布尔或后的位比较，自己地址位小的竞争失败并放弃发送后续的地址位。最终剩余的站竞争成功并随后发送数据。需要事先安排站的逻辑地址。
站在竞争时隙中发送其地址（log N位而不是N位）
Medium ORs bits; 当电台发送“0”但看到“1”时，就会放弃
看到其完整地址的站将在旁边发送
基于冲突的解决方案没有实现约定的竞争顺序，各个站公平地竞争信道。此时，冲突不可避免。协议基于冲突解决各个站的发送顺序。这是本书的重点，经典以太网采用了这种解决思路。
有限竞争协议综合以上两种协议特点，将所有站分成若干个组，组内公平竞争（基于冲突），组间按照一定顺序竞争（无冲突）。常见的有限竞争协议为自适应树遍历协议。
无线局域网拥有不同于有线局域网的特点，冲突检测困难，信道侦听复杂，采用了类似于经典以太网但冲突避免的协议。
4.2.4 有限竞争协议
如何在一个广播网络中获取信道，我们已经考虑了两种基本策略：一种是竞争的方法，如同CSMA 的做法那样；另一种是无竞争协议。
每一种都可以用两个重要性能指标来衡量：低负载下的延迟，以及高负载下的信道利用率。
在负载较轻的情况下，竞争方法（即纯ALOHA 或者分槽ALOHA）更为理想，因为它的延迟较短（冲突很少发生）。随着负载的增加，竞争方法变得越来越缺乏吸引力，因为信道仲裁所需要的开销变得越来越大。
而对于无冲突协议，则结论刚好相反。在低负载情况下，它们有相对高的延迟，但是随着负载的增加，信道的效率反而得到提高（因为开销是固定的）。
显然，如果我们能够把竞争协议和无冲突协议的优势结合起来，那就太好了。这样得到的新协议在低负载下来用竞争的做法而提供较短的延迟，但在高负载下来用无冲突技术，从而获得良好的信道效率。我们把这样的协议称为有限竞争协议（limited-contention protocol）
由上图可以看出，只要减少参与竞争的站数量，则站获得信道的概率就会增加。有限竞争协议正是这样做的。
把站进行分组，保证每个分组里每次只有少部分的站想要发送数据（降低站内冲突）
避免闲置周期和冲突造成的信道浪费
4.2.5 无线局域网协议
MACA 冲突避免多路访问（Multiple Access with Collision Avoidance)
与有线相比，无线电传输范围有限，导致它具有复杂性。
节点可能具有不同的覆盖区域，导致隐藏和暴露终端问题
节点无法检测到冲突，即在发送时进行感应，使碰撞变得昂贵且需要避免
下图中无线电的覆盖范围是这样的：A和B都在对方的范围内，可能潜在地相互之间有干扰： C也可能潜在地干扰到B和D，但不会干扰A。
隐藏站和暴露站问题
隐藏终端是无法相互感知但仍在预期接收器处发生碰撞的发送器
暴露终端是可以相互感知但仍然安全传输（到不同的接收器）的发送器
无线局域网在传输数据时会产生隐藏终端问题和暴露终端问题
【隐藏终端】站A正在给站B发送数据，C监听信道，它什么也监听不到，从而得出错误的结论：现在可以给B发送数据了。
【暴露终端】站B给站A传输数据，此时站C想给站D传输数据，站C侦听介质，则它会听到一个传输正在进行，从而得出错误的结论：C不能给D传输数据。
MACA 的基本思想是发送方剌激接收方输出一个短帧，以便其附近的站能检测到该次传输，从而避免在接下去进行的（较大）数据帧传输中也发送数据。这项技术被用来替代载波侦听。
具体例子：A如何向B发送一帧？
A首先发送给B一个RTS（request to send），这个短帧包含了随后将要发送的数据帧的长度；然后，B用一个CTS（clear to send）作为应答，此CTS 帧也包含了数据长度（从RTS帧中复制过来）。A在收到了 CTS帧之后便开始传输。
C落在A 的范围内，但不在B 的范围内。因此，它听到了A发出的RTS，但是没有听到B发出的CTS，只要它没有干扰CTS，那么在数据帧传送过程中，它可以自由地发送任何信息。
相反， D落在B的范围内，但不在A 的范围内。它听不到RTS帧，但是听到了 CTS 帧。只要听到了 CTS 帧，这意味着它与一个将要接收数据帧的站离得很近；所以，它就延缓发送任何信息直到那个帧如期传送完毕。
E听到了这两条控制消息，与D一样在数据帧完成之前它必须保持安静。
4.3 以太网
4.3.1 经典以太网
经典以太网是最重要的一种局域网模式，通常工作在10Mbps。所有站点共享同一个传输介质（信道），采用基带(什么是基带？)传输信号，采用广播传输技术，即每个站将自己发送的数据通过收发器发送到传输介质上，信号占用信道所有带宽，信号沿传输介质传递到每个站点。当两个或多个站同时传输信号，则会发生信号叠加，造成接收方接收失败。所有传输都会失败。
经典以太网每个时刻只允许一个站点发送数据。没有事先规定的竞争顺序，允许竞争时产生冲突，并基于冲突解决介质访问控制问题。
经典以太网出现过程
a)Ethernet的核心技术是CSMA/CD介质访问控制方法；
b)随机争用技术起源于夏威夷大学校园网ALOHA；
c)1972年，Xerox[zieroks]公司开始Ethernet实验网的研究；
d)1979年，Xerox公司宣布了Ethernet产品；
e)1980年，Xerox、DEC与Intel联合宣布Ethernet V2.0规范 ；
f)20世纪90年代，10Base-T标准使得Ethernet性能价格比大大提高；
g)目前，交换式Ethernet与最高速率为10Gb/s的高速Ethernet的出现，更确立了它在局域网中的主流地位。
经典以太网– 物理层
一根 shared coaxial（共享的同轴电缆），所有主机都连接到该电缆上
- 传输速率最高10Mpbs，使用曼彻斯特编码
- 所有主机运行经典以太网协议来接入网络
- 19世纪物理学家认为ether是一种假想的电磁波传输媒介
- 最初科学家认为信息可以以电磁波的形式沿同轴电缆传播
曼彻斯特编码
曼彻斯特编码、差分曼彻斯特编码
4.3.2 经典以太网MAC子层协议
经典以太网的MAC子层协议最早使用1-persistent CSMA/CD
- 当发生冲突后，使用二进制指数后退（BEB）算法决定随机等待的时间
- 经典以太网的帧结构被仍然在现代以太网中使用
- Preamble：8个字节的先导码，每个字节的比特模式10101010，最后一个字节10101011，作为帧的定界符（SOF）
- 目标地址第一位为0对应普通地址，第一位是1代表组地址（组播），全1的特殊地址广播
- 源地址具有全球唯一性：前三个字节是组织唯一标识符（制造商），每个制造商224个地址
- 数据字段最多包含1500个字节，最小帧长64字节（区分有效帧和垃圾数据）
- Pad用来填充小于46字节的数据字段，校验和使用32位CRC
a)前导码与帧前定界符字段
前导码：7个字节，10101010…101010比特序列。
帧前定界符：1字节，10101011。
b)目的地址和源地址字段
地址字段长度：2个字节或6个字节 。
目的地址类型：
单一结点地址（unicast address）第一位0；
多点地址（multicast address）第一位1；
广播地址（broadcast address）全1。
以太网（本书中）最大帧长和最小帧长（不包括前导码）
4.3.3 以太网中MAC层协议对竞争和冲突的处理思路
想说就说
按照对时间管理的不同，分为连续时间和离散时间，对应的协议分别为：纯ALOHA，分槽ALOHA
纯ALOHA协议：当站点有数据要发送时就发送。如果多个用户同时发送则会发生冲突造成发送失败。发送失败后（发送站会依靠某种方法得知），等待一段随机时间再次发送。等待一段随机时间为了有效解决冲突。
分槽ALOHA协议：是纯ALOHA协议的改进。将时间离散化，分为时间槽（一段事先规定的时间）。只有在时间槽的起始点可以发送。通过推迟发送时间（未准备好的被推迟到下一个时间槽），避免连续时间发送带来的某些冲突。
先听后说
为了不打扰已有的通信，站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，代表有其它站点在发送数据，则不能发送，等待一段随机时间发送。
这种发送数据之前先侦听信道是否空闲的协议称为载波侦听多路访问协议（CSMA，Carrier Sense Multiple Access）。根据贪婪程度和处理策略不同，分为：
- 1-坚持CSMA
- 1-坚持CSMA只是将连续时间上的冲突压缩到前一个数据传递完毕（一个时刻）。
1-坚持CSMA：站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，则继续侦听，直到信道空闲，立即发送。
1-坚持CSMA协议避免打扰已有的通信，但是不能完全避免冲突。
假如现在站点A正在发送数据，站点B想要发送数据，先侦听信道，信道忙，则站点B持续侦听信道。接着（或“同时”）站点C也有数据要发送，执行同样的协议。当站点A发送完毕后，站点B和C都侦听到信道空闲，都会选择立即发送。结果，站点B和C发送数据冲突，都会发送失败。
- 非坚持CSMA
非坚持CSMA：站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，则等待一段随机时间再来侦听。
非坚持CSMA协议不再在信道忙时坚持侦听信道，而是等待一段随机时间再来侦听。能够有效避免1-坚持CSMA协议不能真正分解冲突的问题。
非坚持CSMA协议在提高整个系统吞吐量（系统在单位时间内能够真正完成的数据传输次数）的同时，可能会带来较大的延迟（对每一次数据传输而言）
- p-坚持CSMA
p-坚持CSMA：适用于时间分槽系统。站点在发送数据之前首先侦听信道。如果信道空闲，则以概率p发送数据；以概率1-p推迟到下一个时槽；重复以上过程，直到发送出去或听到信道忙。如果信道忙，则等待一段随机时间再来重复以上协议。
p-坚持CSMA协议可以有效分解潜在的可能的冲突。由于每个站点都运行这个协议，选择了不同的发送时间槽，两个或多个站同时选择一个时间槽的概率随着p的变小而降低。
可以提高吞吐量，但可能带来更大的延迟。
边说边听
先听后说（CSMA）协议要求所有有数据发送的站点侦听到信道空闲时才能发送数据，从而不会打扰已有的通信过程，但是不能完全避免冲突（不能保证站点发送一定成功，或成功获得信道的使用权），尤其是当多个站点同时侦听到信道空闲。
当两个帧发生冲突时，两个被损坏帧继续传送毫无意义，而且信道无法被其他站点使用，对于有限的信道来讲，这是很大的浪费。如果站点边发送边监听，并在监听到冲突之后立即停止发送，可以提高信道的利用率，因此产生了CSMA/CD。
边说边听的实现机制：发送方一边向信道发送（说）数据，一边从信道上读取（听）数据，通过判断双方是否一致来判断是否发生了冲突。
边说边听：所有站点还要同时运行冲突检测（CD, Collision Detection）协议，边发送数据（竞争信号）边检测信道上是否发生了冲突。如果听到冲突，则表明还有其它站点“同时”发送数据，代表本次发送失败（所有发送站点都会意识到这一点）。听到冲突的站点立即停止发送（提高效率），等待一段随机时间后再次运行CSMA/CD。
如果站点在发送过程中没有听到冲突，则认为本次发送成功（或取得总线的控制权）。
二进制指数后退
二进制指数后退算法
站点运行CSMA/CD协议，听到冲突后进入竞争周期，时间离散为多个时间槽。如果第一次冲突，则参与竞争的站点在随后的两个时间槽内随机选择一个发送，发送前依然要侦听信道空闲。排在最前面的只有一个竞争者的时间槽对应的竞争者竞争成功，随后抓住信道发送数据，其它竞争者等到选择的竞争时间槽时侦听信道为忙，只能等待已有通信完成再次参与竞争。
当一个时间槽有两个竞争者都会听到冲突，全部竞争失败。竞争失败的站点将随机等待的时间槽数加倍，然后从中随机选择一个参与竞争，直到竞争成功或达到最大竞争次数。
二进制指数后退指的是每次冲突后随即后退的时间槽翻倍，直到1024（0~1023）个时间槽，此时运行了16次依然解决不了冲突，则认为网络坏了。
竞争周期时间槽的时间应该远远小于普通帧长。这样能够减少冲突带来的消耗，提高信道使用效率。
对每一个站点，选择任何一个时间槽都是公平的。因为一个时间槽的好坏不只是取决于是否靠前，更重要的是是否其它竞争者也选择了这个时间槽（博弈论）。
竞争周期的最后结果是某一个站点获得信道使用权。
最小帧长
最小帧长
一个站点执行CSMA/CD协议，当发送（竞争）过程中没有听到冲突，则认为发送（竞争）成功。
考虑到信道传输延迟时，这个结论需要前提条件保证才是正确的。
发送方必须发送足够长时间的数据，才能够检测到发生在“远方”的冲突，从而做出正确的判断。
本质是一个分布式系统，每个站点只能依据自己周围的是否有信号叠加（ “局部信息” ）来推断整个信道上是否有冲突（ “全局结论” ）。或依据自己周围是否空闲来推断整个信道是否空闲。
由图可知，站 A 在发送帧后至多经过时间 2𝝉 （端到端传播时延的 2 倍）就能知道所发送的帧有没有发生碰撞（当 时）。因此把以太网端到端往返时间 2T 称为争用期（又称冲突窗口或碰撞窗口）。每个站在自己发送数据之后的一小段时间内，存在发生碰撞的可能性，只有经过争用期这段时间还未检测到碰撞时，才能确定这次发送不会发生碰撞。
为了确保发送站在发送数据的同时能检测到可能存在的碰撞，需要在发送完帧之前就能收到自发送出去的数据，即帧的传输时延至少要两倍于信号在总线中的传播时延，所以 CSMA / CD 总线网中的所有数据帧都必须要大于一个最小帧长。任何站点收到帧长小于最小帧长的帧时，就把它当作无效帧立即丢弃。最小帧长的计算公式为
最小帧长＝总线传播时延 × 数据传输速率 ×2
例如，以太网规定取 为争用期的长度。对于 10Mb/s 的以太网，在争用期内可发送 512bit，即 64B。在以太网发送数据时，如果前 64B 未发生冲突，那么后续数据也就不会发生冲突（表示已成功抢占信道）。换句话说，如果发生冲突，那么就一定在前 64B。由于一旦检测到冲突就立即停止发送，因此这时发送出去的数据一定小于 64B。因此，以太网规定最短帧长为 64B，凡长度小于 64B 的帧都是由于冲突而异常中止的无效帧，收到这种无效帧时应立即丢弃。
如果只发送小于 64B 的帧，如 40B 的帧，那么需要在 MAC 子层中于数据字段的后面加入一个整数字节的填充字段，以保证以太网的 MAC 帧的长度不小于 64B。
例如：
4.3.4 经典以太网的传输效率
4.3.5 交换式以太网
经典以太网的问题：随着网络规模不断扩大，依然是同一个CSMA冲突域。即每个时间只能够有一个站点发送数据，介质利用率低，每个站点的平均使用带宽下降。
解决思路：能够同时支持尽可能多的通信。将一个冲突域划分为多个冲突域（网络微分段）。使用的网络设备为网桥或交换机。
网桥（交换机）的功能是将连接断开，需要时连接（桥、桥接）。这样，发生在一个网段的通信信号不会“自动”（像中继器、集线器那样）转发到另外的网段。
Hubs(集线器) 将多个用户线连接到同一个CSMA/CD竞争域
交换机则把每个端口隔离，每个端口都有独立的冲突域
- 当有多个端口接入时，能达到（比集线器）大得多的吞吐量
- 交换机的高速背板把帧传输到目的地端口（传输速度multiple Gbps）
- 因为接口独立，在全双工模式下，不需要使用CSMA/CD
- 每个端口的接线通常是全双工的，站和端口可以同时发送数据；如果使用半双工，则需要CSMA/CD方式竞争（但只有两方竞争）
集线器：工作在物理层（最底层），没有相匹配的软件系统，是以硬件设备，主要用于连接计算机等网络终端。采用共享式带宽。只能采取广播形式传递数据。
交换机：工作在数据链路层，高端的交换机有独立系统也可工作在第三层，允许连接在交换机上的设备并行通讯。有系统的交换机可以记录mac地址表。划分冲突域实现并行传输。
交换机可以连接电脑，也可以连接集线器或是其他交换机
- 通过简单的插入或者拔出线缆就可以添加和删除一台计算机
- 集线器把来自多个计算机的流量集中起来
- 集线器会把帧发送给所有连接上它的计算机，交换机只会发送到目的接口（有利于信息安全和隐私）
4.3.6 快速以太网
Fast Ethernet 将以太网从10 Mbps扩展到100 Mbps
- 新的ethernet协议要求向下兼容。
- 最低可以使用3类双绞线
- 实际上5类双绞线是最常用的线缆
4.3.7 千兆/万兆以太网
千兆/万兆以太网上每一根网线只可以连接两台设备
全双工模式连接两台电脑或者连接电脑和交换机，甚至交换机和交换机
千兆以太网标准设计要求：
增加10倍的传输速度（与上一代相比）
与现有的其他以太网标准兼容（向下兼容），自动协商
千兆网需要提供单播和广播的无确认数据报服务
使用相同的48位（6比特）地址
保持相同的帧格式包括最大和最小的帧尺寸
千兆网支持全双工（正常模式）和半双工
正常模式下，不需CSMA/CD，因此线缆最大长度跟冲突无关（不需考虑t ）
计算机被连接到集线器（无法缓存）时会使用半双工模式
- 最长电缆长度降为25m
- 使用载波扩充让帧长度扩充到512字节，效率只有9%（64字节帧有46字节有效数据）
- 帧突发：允许发送方多个待发帧连在一起发送（不足的长度再扩充）
万兆以太网标准设计要求：
增加10倍的传输速度（与上一代相比）
与现有的其他以太网标准兼容（向下兼容），自动协商
主要用来连接高端路由器，交换机和服务器，端局间中继线
万兆网只支持全双工，不需CSMA/CD
4.4 无线局域网
无线局域网对应的标准为IEEE 802.11，也称为WiFi。
无线局域网工作在无需授权许可的ISM（Industrial Scientific and Medical）频段上，易受其它电气设备干扰。
网络分为两种模式：带有接入点AP（Access Point）或基站（base station）的网络（有架构模式），和没有接入点的网络（ad hoc）（自组织模式）两种工作模式。
4.4.1 802.11 体系结构和协议栈
带有接入点的网络模式（有架构模式）中任意两个站点通信通过AP(Access Point 接入点)。隐含的假设为：所有站点都应该在AP的信号覆盖范围内，所有站点的信号范围能够覆盖AP。发送方首先将数据发送给AP，AP将数据再转发给接收方。AP之间通过有线连接。
ad hoc network（自组织网络）模式中任意两个站点可以直接通信。属于自组织网络。当AP不再作为网络内部任意两个站点通信的转发站点，只作为外部站点的代理时，AP和网内其它站点也组织为ad hoc网络模式。
无线局域网只使用一个信道，支持广播传输模式。
形式上类似于经典以太网，那么经典以太网的介质访问控制协议CSMA/CD是否能够直接应用于无线局域网？
无线和有线局域网的区别：无线局域网的站点的信号可能无法覆盖所有的其它站点；而有线局域网任意站点发送的信号都能够到达其它所有站点。
冲突的本质是接收方接收到两路或多路信号时就会发生冲突。CSMA/CD的本质是发送方判断是否发生了冲突。
但是由于无线信号的物理性质，无线局域网中发送方很难侦测到冲突的发生
4.4.2 802.11 物理层
802.11物理层使用2.4G和5GHz两个频段，都属于ISM，发射功率不能超过1w（实际上50mW已经很高）
2.4G拥挤（其他无线通信，微波炉，车库门），5GHz传输范围小
802.11b支持1、2、5.5、11Mpbs速率（一般为11），802.11a在5Ghz速率54Mpbs
使用OFDM（正交频分复用）增强频谱使用效率，抵抗多径衰减
常见的无线局域网产品在单一网卡上同时支持802.11a/b/g
802.11n使用4跟天线，结合多入多出（MIMO）技术提高网络吞吐量（100Mbps）
4.4.3 802.11 MAC 子层协议
802.11 MAC子层协议
存在的主要问题
无线信道的MAC子层协议与有线信道相比更加复杂
冲突检测非常困难
- 无线信道是半双工的，节点不能在同一个频率上传输的同时侦听到该频率上的突发噪声
- 接收信号比发送信号的强度低很多，无法在发送同时识别到微弱的信号（接收信号强度过低类似噪声）
无线节点具有不同的覆盖区域
Leads to hidden and exposed terminals（隐藏和暴露终端问题）
见4.2.5
无线局域网需要解决以下几个挑战：
冲突判断：不能直接使用“边说边听”方式来判断是否发生了冲突，因为可能根本听不到冲突（半双工）。事后确认来判断，如果发送后能够收到确认，则认为没有发生冲突；否则认为发生了冲突（无论是真的发生了由于站点竞争引起的冲突还是其它电气设备带来的噪声干扰，都可以认为发生了冲突）。由于整帧发送完成才能知道是否发生冲突，需要尽量避免可能的冲突发生。
冲突避免1：需要事先判断接收方是否空闲，并在接收期间避免其它站点贸然发送带来的干扰。（类似于CSMA，但更加复杂）
冲突避免2：当可能有多个站点同时竞争信道时，需要事先避免冲突的策略。（类似于p-坚持CSMA的随机后退策略）。每个站点随机选择发送的时间，减少多个站点同时发送引发冲突的概率。
支持并发：无线信号范围受限带来问题复杂性的同时也带来了可能的好处：可以支持多个通信同时“并发”进行，提高信道的利用率。（类似于网桥将一个冲突域分段为多个冲突域）
一个早期的但有影响力的方案是MACA（冲突避免多路访问）。通过短帧声明自己可能的接收时间段，其它站点根据声明安排自己的发送时间。
MACA冲突避免多路访问
CSMA/CA
CSMA/CA：带有冲突避免的CSMA
MACA存在的问题：依然会有冲突。
如果两个站点同时发送给一个站点RTS帧，会发生冲突，两个发送站点都接收不到CTS帧。这时需要分解冲突。
无线局域网采用了随机后退策略，类似于p-坚持的CSMA协议+二进制指数后退协议。P-坚持用于事先尽量避免冲突，二进制指数后退用于发生冲突后的随机时间选择。
带有冲突避免的CSMA（CSMA/CA）：在发送前侦听信道（物理侦听+虚拟侦听），如果信道忙则继续侦听，如果信道空闲，则按照随机选择后退的时间槽发送，冲突后指数后退。
- 通过侦听确定在一个很短的时间内（DIFS）没有信号，则认为信道空闲；
- 倒计数空闲时间槽（时间槽数事先随机选定），当有帧发送时暂停该计数器；
- 当计数器为0，发送自己的帧；
- 如果发送成功，则目标站立即发送一个短确认；
- 在规定时间内没有收到确认，加倍后退时间槽，再试；
- 直到发送成功或达到最大发送次数。
CSMA/CA机制下发送时序：
- CSMA/CA 在发送数据前使用随机指数后退（时间槽）来避免冲突
- MAC层使用ACK/重传机制来解决无线传输错误
侦听
CSMA/CA侦听机制：为了克服隐藏/暴露站点问题，采用物理侦听+虚拟侦听机制。
- 物理侦听只是简单地检查信道，看是否存在有效信号。
- 虚拟侦听根据听到的RTS/CTS帧（或其它类型帧）中包含的相关字段（Duration字段 ：用于说明该帧需要的传输时间）设置自己的网络分配向量（NAV，Network Allocation Vector），维护自己的一个关于信道使用的逻辑记录。代表无论能否真正听到信号，在NAV声明的时间信道一定是忙的。
- NAV也可以优化为声明自己接收确认的时间段，从而有效地支持并发。
- 无论物理侦听或虚拟侦听，只要有一个是忙的，则代表信道忙。
CSMA/CA协议使用可选的RTS/CTS虚拟侦听机制，用来解决隐藏站点问题：
虚拟侦听中每个站保留一个信道何时要用的逻辑记录，通过网络分配向量NAV获得
每一帧所携带的NAV说明这个帧所属的一系列数据将传输多长时间
RTS/CTS是可选的，但一般不用。只对隐藏终端有好处，并且影响效率。802.11中该机制会降低操作速度，所有终端都会听到RTS和CTS。
帧间隔
通过定义不同的帧间隔给予不同帧流量以不同的优先级
短帧有更高的优先级
为了节省移动设备电量，MAC具有节能机制
- 省电模式：AP缓冲数据，客户端信标帧苏醒，检查是否有为其缓冲的流量
- 自动省电交付：AP缓冲数据，客户端发送帧到AP后，AP将缓存帧发送到客户端
4.4.4 802.11 帧结构
- 帧控制：包括11个子字段：协议版本，类型字段（数据/控制/管理），子类型（RTS/CTS），去往/来自DS（发送还是来自AP），更多段，重传，电源管理，更多数据（更多帧），受保护的（加密），顺序（严格按照顺序处理）
- 持续时间：占用信道的时间（其他站用该字段管理NAV）
- 地址1，地址2，地址3：接收、发送、远端地址
- 序号：该帧的编号
- 数据：有效载荷，最长2312字节
- 校验序列：32位CRC
4.4.5 服务
Association：关联服务被移动站用来把自己连接到AP上，AP可能会接收也可能会拒绝。
Disassociation：解除关联服务一个移动站在离开本地或关闭之前，需要解除关联，AP在停止运行进行维护之前也会解除关联
Reassociation：重新关联服务允许站改变它的首选AP。用于从一个AP移动到另一个AP。
Distribution：分发服务决定了如何对帧进行路由；如果帧目的地是本地，则AP直接发送，否则需要通过有线网络转发。
Integration：集成服务处理协议转换（一帧发往或者来自局域网外）。
Authentication：AP发送帧之前必须认证，认证模式：开放；WiFi Protected Access 2（WPA2）；
Deauthentication：解除认证
Data Delivery：数据传送服务；802.11传输不能保证可靠性
Privacy：通过无线局域网发送的信息要求保密时，需要使用隐私服务，该服务管理加密解密的细节。
Privacy和Authentication的区别？
- Authentication是对用户是否有权使用AP进行认证和授权
- Privacy是指用户数据的隐私保护，用户通过802.11传输数据时要进行 数据加密，避免他人窃听
4.8 数据链路层交换
4.8.1 网桥的使用
网桥（散列表；flooding算法；逆向学习；动态拓扑结构变化）
网桥（路由器）把多个局域网连接起来组成更大的局域网
- 以太网交换机是网桥的现代称呼
- 网桥工作在数据链路层，通过检查数据链路层地址来转发帧
- 网桥把多个物理局域网连接成一个逻辑局域网
- 虚拟局域网（VLAN）是把一个物理局域网看成多个逻辑局域网
网桥使用的三种情况
- 学校和公司不同部门使用不同的 LAN，需要网桥把这些不同的 LAN 连接起来
- 一个组织分布在不同的楼宇，每个楼内有独立的 LAN，通过网桥把分布在不同空间的 LAN 连接起来
- 把逻辑上的单个 LAN 分成多个独立的 LAN。例如在大学中需要几千台工作站，系统规模很大，不适合把所有的工作站都放在一个 LAN 上：要上网的计算机数目远大于任何以太网集线器的端口数。
使用网桥的好处
- 使用网桥可以增加局域网的容量
- 使用网桥可以隔离出错的节点（通过转发规则）
- 网桥是全透明的，只需要将 LAN 线缆插入网桥就可以使用
网桥（交换机）的交换功能主要由三个模块组成：转发模块、自学习模块和MAC-端口映射表（也称MAC地址表）。
转发模块依据映射表决定入境的帧应该从哪个端口转出。转发规则为：
- 目标LAN和源LAN相同，丢弃
- 目标LAN和源LAN已知，转发
- 目标LAN未知（网桥新接入），使用泛洪算法（flooding）
- 使用哈希表列出目的地和他所属的输出端口（例：B给D发送数据）
4.8.2 学习网桥
A bridge operates as a switched LAN (not a hub)
带有交换功能的LAN，而不像集线器（将线缆的一端物理的连接在一起）
网桥的端口可以连接计算机、集线器和其他网桥
不同种类的线缆也可以附接到同一个网桥上
自学习模块
负责“实时”（可能几分钟）地将网络拓扑（主要指站点和端口的连接关系）的情况和MAC-端口映射表同步。
让映射表能够动态反应网络拓扑的变化。
向后学习，Backward learning
网桥使用向后学习(backward learning)来构建端口和目的地对应关系哈希表
- 网桥可以看到每个端口发送的所有帧
- 当收到一个入境帧时，将其内部携带的“源地址”与进入端口的关联关系写入映射表中。
- 建立哈希表后，就可以通过检查帧的目的地地址来发往对应的端口
- 如果发现还未学习到的目的地地址，通过Flooding发往所有的其他端口
自学习模块是一种动态学习机制。映射表是动态建立的，能够动态反应网络拓扑。开始时为空，随着流量的增多，映射表不断完善。
- 为了适应拓扑结构变化，会记录每个地址最新帧的时间
- 映射表中每个表项关联一个计时器，在规定时间内没有刷新的表项删除。
- 一台机器改变物理位置后，旧的对应关系将被遗忘，学习新的关系
- 一台计算机沉默几分钟之后也会被遗忘，需要重新学习
直通式交换（cut-through switching）或虫孔路由（wormhole switching）
- 算法实现采用专用的大规模集成电路芯片查找和更新哈希表
- 看到MAC地址就可以决定如何转发
- 速度快，可能帧还没传完就开始转发
- 降低了网桥的延迟和需要缓冲的帧数
MAC-端口映射表（也称MAC地址表）记录了站点和端口的映射关系。（考虑多个网桥连接时映射表的情况，如B1的4号端口与站点D\E\F\G的映射，B2的4号端口与站点A/B/C的映射）
请给出上图最终（收敛）的两个映射表。
网桥（交换机）实现机制
网桥（交换机）的交换功能主要位于交换机概念模型中的中继（Relay）功能中。三个模块的相互关系为：
- 转发模块使用MAC-端口映射表（也称MAC地址表）进行转发，使用入境帧中携带的目的地址查找映射表，将帧转发到相应表项对应的端口。
- 自学习模块执行逆学习算法，建立入境帧的源地址与入境端口的映射关系。
- 映射表将转发模块和自学习模块的实现解耦合。其它网络设备的工作机制大体如此（表驱动）。
4.8.3 生成树网桥
生成树网桥
网桥的拓扑结构存在环形，只使用向后学习可能会造成帧的传输陷入永远的循环
- 为了提高可靠性，网桥之间有冗余链路，造成了拓扑环路（两个网桥之间有两条甚至更多的路径）
- 提出基于生成树（Spanning tree）拓扑结构的网桥来解决拓扑环路问题
生成树拓扑结构
- 生成树要能够到达每个网桥
- 每个站到另外一个站只有一条路径
- 无环的生成树拓扑结构是实际拓扑结构的一个子集
生成树的过程
- 网桥运行一个分布式的算法
- 每个网桥周期性从所有端口广播一个配置信息给邻居
- 同时处理其他网桥的配置信息
- 这些消息不被转发，只用作构建树用于随后帧的转发
生成树算法
- 每个桥广播自己的桥编号，号最小的桥称为生成树的根；
- 每个网桥计算自己到根的最短路径，构造出生成树，使得每个LAN和桥到根的路径最短；
- 如果路径长度相同，选择经过最低标识符的路径；
- 当某个LAN或网桥发生故障时，要重新计算生成树；
- 生成树构造完后，算法继续执行以便自动发现拓扑结构变化，更新生成树。
4.8.4 中继器／集线器／网桥／交换机／路由器和网关
中继器、集线器、交换机、路由器、网关
应用层 | 应用网关 | |
传输层 | 传输网关 | 设在传输层的叫传输层网关。 |
网络层 | 路由器 | 用于连接多个逻辑上分开的网络。当一个分组进入到路由器中时，帧头和帧尾被剥掉，将IP分组传递给路由软件，路由软件根据分组的头信息来选择一条输出线路。 |
数据链路层 | 网桥
交换机 | 工作在数据链路层，将多个LAN连接起来，通过检查数据链路层地址来转发帧 |
物理层 | 中继器
集线器 |
4.8.5 虚拟局域网
新的网桥以太网卡与802.1Q兼容，并且能够正确填写VLAN字段
- 第一个能感知VLAN的网桥添加VLAN字段
- 路径最后一个网桥删除VLAN字段
- 帧的颜色取决于接收它的端口，因此一个端口上所有机器必须属于同一个VLAN
