The Medium Access Control Sublayer

考纲： 4.1 静态和动态信道分配        4.2 多路访问协议（ALOHA、CSMA、CSMA/CD、最小帧长、MACAW） 4.3 以太网（二进制指数后退算法，最小帧长、曼彻斯特编码、差分曼彻斯特编码、802.3帧格式） 4.4 WLAN（隐藏站和暴露站问题、CSMA/CA、802.11 MAC子层协议） 4.8 数据链路层交换（网桥（散列表；flooding算法；逆向学习；动态拓扑结构变化）、生成树网桥、中继器、集线器、交换机、路由器、网关）

本章讨论的是广播网络和相应的协议

• 在任何一个广播网络中，关键的问题是当多方竞争信道的使用权时如何确定谁可以使用信道
  • 用来确认多路访问信道下一个使用者的协议属于数据链路层的一个子层➡️Medium Access Control（介质访问控制，MAC)
    • MAC子层位于数据链路层的底部
• 广播信道有时也称为多路访问信道Multiaccess Channel或随机访问信道Random Access Channel

数据链路层的两个子层

• 逻辑链路控制 LLC (Logical Link Control)子层
• 媒体访问控制 MAC (Medium Access Control)子层
  • 局域网对 LLC 子层是透明的
  • 802 委员会制定的逻辑链路控制子层 LLC（即 802.2 标准）的作用已经不大了

4.1 信道分配问题

静态信道分配

在多个竞争用户之间分配单个信道的传统做法是把信道容量拆开分给多个用户使用。具体的方法同第二章中讨论的多路复用技术

时分复用(TDM)：将时间分为等长的"TDM帧"，每个"TDM帧"又分为等长的m个”时隙“，将m个时隙分配给m对用户节点使用

• 每个时隙在TDM帧中的位置不变 缺点：
• 每个节点最多只能分配到信道总带宽的1/m
• 如果某节点暂时不发送数据，会导致被分配的时隙闲置，信道利用率低 补充：STDM

频分复用(FDM):将信道的总频带划分为多个子频带，每个子频带作为一个子信道，每对用户使用一个子信道进行通信

优点：各节点可同时发送信号，充分利用信道带宽 缺点：FDM只能用于模拟信号（只有模拟信号有频率概念） 当发送方的数量非常多且经常不断变化/或者流量呈现突发性，FDM存在一些问题：

• 如果整个频谱被切割成N份，并且当前只有很少的用户需要进行通信，那么大量宝贵的频谱将被浪费掉
• 如果希望进行通信的用户数超过了N个，则有些用户因带宽不够而遭到拒绝 基本问题在于：当有些用户停止通信，他们的带宽实际上白白浪费，他们自己不使用这些带宽，其他用户也不允许使用

波分复用(WDM)---光的频分复用：复用器将各个节点发出的不同波长的光信号”复合“后传输到光纤上，分用器将不同波长的光信号分离出来

码分复用(CDM):

动态信道分配的假设

Five key assumptions（ 5个关键假设）：

• 站模型 Station model➡️流量独立：该模型由N个独立的站组成的，每个站都有一个程序或者用户产生要传输的帧，在长度为Δt的时间间隔内，期望产生的帧数λΔt（其中λ为常数，表示新帧的到达率）。一旦生成出一帧，则站就被阻塞，直到该帧成功发送出去
• 单信道 Single channel model：所有的通信都用这一个信道。所有的站可以在该信道上传输数据，也可以从该信道接收数据
• 冲突假设 Collision assumption
  • 冲突：如果两帧同时传输，则它们在时间上就重叠，由此产生的信号是混乱的，这种情况称为冲突
  • 所有的站都能够检测出冲突事件的发生，冲突的帧必须在以后再次被发送
• 时间连续或分槽 Continuous or slotted time
  • 时间连续：时间可以假设连续，在任何时刻都可以开始传输帧
  • 时间分槽/分成离散的间隔：帧的传输只能从某个时间槽的起始点开始。一个时间槽可能包含0、1或者多个帧➡️空闲的时间槽、一次成功发送、一次冲突
• 载波侦听或非载波侦听 Carrier sense or no carrier sense
  • 载波侦听：一个站在试图用信道之前就能知道该信道是否正在被使用
  • 非载波帧听：站就无法在使用信道前帧听信道，它们只能盲目传输，以后再判断该次传输是否成功

4.2 多路访问协议

ALOHA

(Additive Link On-Line Hawaii system) 先说后听

纯ALOHA

Pure ALOHA 非载波监听

基本思想：当有用户有数据需要发送时就发送/只要有待发数据，就让他们发 如果有帧被损坏了，则发送方要等待一段随机时间，然后重新发送该帧。等待的时间必须是随机的，否则同样的帧会一次又一次地冲突，降低冲突概率

• 冲突：只要两个帧在相同的时间试图占用信道，冲突就会发生，并且两帧都会被破坏
• 竞争系统：如果系统中多个用户共享同一个信道的方法会导致冲突，则这样的系统称为竞争系统

冲突危险期：保证数据能够成功发送：2t

分槽ALOHA

Slotted ALOHA

基本思想：把时间分为离散的时间片(slot)，每段对应一帧，要求用户遵守统一的时间槽边界 分槽ALOHA在发生冲突时，发生冲突的各个节点随机推迟若干个时间片

冲突危险期：t 分槽ALOHA避免了用户发送数据的随意性，降低了冲突概率，提高了信道的利用率

为什么Slotted和Pure ALOHA的吞吐量峰值分别出现的横坐标1和0.5？ Slotted ALOHA 有时隙，冲突危险期是 1 个帧时间，所以最优尝试负载是 G=1 Pure ALOHA 没有时隙，冲突危险期是 2 个帧时间，冲突机会翻倍，所以最优尝试负载要减半，也就是 G=0.5

CSMA

载波侦听多路访问协议 Carrier Sense Multiple Access Protocols

如果在一个协议中，站监听是否存在载波（是否有传输）并据此采取相应的动作，则这样的协议称为载波监听协议

基本思想：检测其它站点，调整自己的动作，大大提高利用率 CSMA协议在ALOHA协议基础上提出改进：在发送数据之前，先监听信道是否空闲，只有信道空闲时，才会尝试发送

1-坚持CSMA 1-persistent CSMA

• 当一个站有数据要发送时，首先侦听信道，确定当前是否有其他站正在传输数据
  • 如果信道空闲，它就发送数据
  • 否则，如果信道忙，该站等待直至信道变成空闲
• 当信道空闲，该帧立即发送一帧，如果发生冲突，则该站等待一段随机的时间，然后从头开始上述过程

之所以称为1-坚持，是因为当站发现信道空闲时，它传输数据的概率为1

发生冲突的情况：两个站在等待其余的站点传输数据的过程中都准备好了待发送的数据，都会礼貌等待直到当前的传输结束，然后双方将同时开始传输导致冲突发生

优点：信道利用率高，信道一旦空闲，就可以被下个节点使用 缺点：多个节点都已准备好数据时，一旦信道空闲，会有多个节点同时发送数据，冲突的概率大

非坚持CSMA Nonpersistent CSMA

• 站在发送数据前要先侦听信道
  • 如果没有其他站在发送数据，则该站自己开始发送数据
  • 如果信道当前正在使用中，则该站不持续对信道进行监听，以便传输结束后立即有抓住机会发送数据
  • 相反，它会等待一段随机时间，然后重复上述算法

优点：当多个节点都已准备好数据时，如果信道不空闲，则各节点会随机推迟/等待一段时间再尝试监听，从而使各节点错开发送数据，降低冲突概率 缺点：

• 信道刚恢复空闲时，可能不会被立即利用，导致信道利用率低
• 比起1-坚持，也带来了更大的延迟
  • 非坚持 CSMA 通过随机等待来减少多个站点同时发送的概率，因此冲突少了；但由于站点发现信道忙后不会持续监听，可能错过信道刚空闲的时刻，导致信道空闲也没人发送，从而增加平均等待时间和发送延迟。

p-坚持CSMA p-persistent CSMA
适用于分时间槽的信道

• 当一个站点准备好要发送的数据时，它就侦听信道
  • 如果信道是空闲的，则它按照概率p发送数据，而以概率q=1-p将此次发送推迟到下一个时间槽
  • 如果下一个时间槽也是空闲的，则它还是以概率p发送数据，而以概率q=1-p再次推迟发送
  • 如果该站再刚开始就监听到了信道为忙，则会等待到下一个时间槽再利用上述的算法

没有哪一种CSMA能完全避免冲突！

为什么1坚持和非坚持在横坐标接近1的位置交叉？

• 当G 较小时，每个帧时间内平均产生的帧数少，信道竞争不激烈。1-坚持 CSMA 在信道空闲时立即发送，减少了空闲等待时间，因此信道利用率和吞吐量较高。
• 随着 G增大到接近 1，平均每个帧时间内已有约 1 次发送尝试，多个站点同时等待发送的概率增大。
  • 1-坚持 CSMA 中各站点在信道一空闲时会同时发送，导致冲突和重传增多，系统吞吐量下降。
  • 非坚持 CSMA 在信道忙时随机等待，虽然增加了发送延迟，但分散了各站点的发送时刻，降低了冲突概率，提高了有效信道利用率。
• 因此在 G 接近 1 附近，非坚持的吞吐量开始超过 1-坚持，二者曲线发生交叉

CSMA/CD

CSMA with Collision Detection（CSMA/CD）带冲突检测的CSMA 先听后发 边听边发 冲突停发 随机重发 本质：1-坚持CSMA进化版本➡️每个站快速检测到发生冲突后立即停止传输帧，而不是继续完成传输

CSMA/CD模型将由交替出现的竞争期contention、传输期transmission以及当所有站都静止的空闲期idle组成 重要特性：

• 使用 CSMA/CD 协议的单信道网络不能进行全双工通信而只能进行双向交替通信（半双工通信）
• 每个站在发送数据之后的一小段时间内存在着遭遇碰撞的可能性

优缺点：

• 优点：
  • 原理比较简单，技术上易实现，网络中各工作站处于平等地位 ，不需集中控制，不提供优先级控制
  • 帧时相比传播时间长很多，大大提高协议的性能
• 缺点：在网络负载增大时，发送时间增长，发送效率急剧下降

二进制指数后退算法

The Binary Exponential Backoff Algorithm

用途：当冲突发生时如何确定随机等待时间 规则： 一般地，在第$i$次冲突之后，从$[0,2^i-1]$之间随机选择一个数，然后等待这么多个时间槽

• 第10次冲突：随机重发的分水岭➡️达到10次冲突之后，随机数的选择区间被固定在最大值1023，以后不再增加，也就是$[0,2^{10}-1]$
• 第16次冲突，放弃传帧，报告上级（网络层）➡️在16次冲突之后，控制器放弃努力，并给计算机返回一个失败报告

优势：二进制指数后退算法考虑了网络负载的变化情况

• 如果只有少量站发生冲突，可以保持较低的延迟
• 当许多站发生冲突，可以保证在一个相对合理的时间间隔内解决冲突
• 将延迟后退的步子截断在1023可避免延迟增长得太大 后退次数的多少往往与负载大小有关，二进制指数后退算法的优点是把后退时延的平均取值与负载的大小联系起来了，使得在重负载的情况下能有效地分解冲突

争用期/碰撞窗口

争用期=2×最大单向传播时延（考虑距离最远的两个节点） ~={green}通俗理解：一个节点最多需要花多久时间可以确信自己完全占领了地盘=~

• 最先发送数据帧的站，在发送数据帧后至多经过时间 2τ （两倍的端到端往返时延）就可知道发送的数据帧是否遭受了碰撞
• 若争用期内未发生冲突，就不可能再冲突
• CSMA/CD没有ACK机制，若发送过程中未检测到冲突，就认为帧发送成功
  • CSMA/CD协议中，一个节点判断自身发送数据是否成功的依据是：边发送数据边侦听总线，如果在发送结束时没有听到冲突，则认为本次数据发送成功
• 时延带宽积：A节点以最高速率向信道上源源不断地发送数据，当A发出的第一个bit到达B节点时（此时达到最大单向传播时延30微秒），整个信道上充斥着300个bit➡️任何一个其余节点监听信道都能发现信道忙碌，此时信道为A所用，不会被其余节点打断

最小帧长/最短帧长

最小帧长=2×最大单向传播时延×信道带宽=争用期×信道带宽

• 若收到的帧小于最短帧长，则视为无效帧
• 保证A节点还没有发完数据之前，意识到自己的数据在传输过程中发生了冲突，能够实现冲突停发
• 特别地，CSMA/CD协议的冲突停发规则会导致小于最短帧长的"非法帧"
• 如果实际要发送的数据很少，可填充至合法长度后再发送
• 判断收到的帧是否小于最短帧长的限制

最长帧长

规定最长帧长可防止某些节点一直占用信道 以太网规定：最短帧长=64B 最长帧长=1518B

4.3 以太网 Ethernet

在局域网中，硬件地址又称为物理地址，或 MAC 地址

• MAC地址是烧录在Network Interface Card(网卡, NIC)里的 ,在网络底层的物理传输过程中，是通过物理地址来识别主机的，它一般也是全球唯一的
  • 地址字段的前3个字节用作该站所在的组织唯一标识符OUI（Organizationally Unique Identfier）➡️该字段的值由IEEE分配，指明了网络设备制造商
  • 地址字段的后三个字节由制造商负责分配，并在设备出厂前把完整的地址用程序编入NIC中
• 48 bit

IEEE 802.3 推出的以太网标准

物理层

MAC层

• 👍DIX Ethernet V2 是世界上第一个局域网产品（以太网）的规约
• IEEE 802.3 标准 严格说来，“以太网”应当是指符合 DIX Ethernet V2 标准的局域网

以太网提供的服务

为了通信的简便，以太网采取了两种重要的措施

• 采用较为灵活的无连接的工作方式，即不必先建立连接就可以直接发送数据
• 以太网对发送的数据帧不进行编号，也不要求对方发回确认
  • 原因：局域网信道的质量很好，因信道质量产生差错的概率是很小的 因此：
• 以太网提供的服务是不可靠的交付，即尽最大努力的交付
• 当目的站收到有差错的数据帧时就丢弃此帧，其他什么也不做。差错的纠正由高层来决定

以太网不负责重传丢弃的帧

• 如果高层发现丢失了一些数据而进行重传，但以太网并不知道这是一个重传的帧，而是当作一个新的数据帧来发送

经典以太网MAC子层协议

V2标准的以太网MAC帧： 记忆口诀：6 6 2 N 4 收发协数验 以太网MAC帧长范围：64B-1518B

• 目的地址：接收方MAC地址 48bit
  • 目的地址全1表示，代表广播帧，会被局域网内所有地址接收/网络上的所有站接收
  • 如果传输出去的目标地址为第一位是0，则表示是普通地址，如果是1，表示是组地址
• 源地址：发送方MAC地址 48bit
• 类型：指明网络层协议
  • 类型字段用来标志上一层使用的是什么协议，以便把收到的 MAC 帧的数据上交给上一层的这个协议/知道应该调用哪个网络层的协议来处理帧携带的数据包
• 数据/ MAC 客户数据字段：46~1500（需限制最短、最长帧长）
  • IP数据包太长➡️分片
  • IP数据包太短➡️填充
• FCS：CRC校验码
• 前导码preamble
  • 每个字节包含比特模式10101010（除了最后一个字节的最后两位是11）
  • 前同步码：7B➡️打节奏，使步调一致/用来迅速实现 MAC 帧的比特同步
  • 帧开始定界符（start of Frame SOF）：1B➡️开始定界，连续两个1，表示后面的信息就是MAC帧
• 以太网MAC帧结束定界-违规编码法➡️曼彻斯特编码
  • 在曼彻斯特编码中，如果信号中间不跳变，就属于违规编码，当接收方检测到违规编码时就知道帧已经结束 总结：

IEEE 802.3 标准:

• Length长度：表明数据部分的长度

曼彻斯特编码

Manchester Encoding

• 不归零编码(NRZ)/二进制编码Binary encoding:低0高1，中不变
  • 除数据线之外，还需要专门的时钟线，发送时钟信号
• 归零编码(RZ):低0高1，中归零
• 反向非归零(NRZI):跳0不跳1看起点，中不变

NRZI=Non-Return-to-Zero Inverted

• 曼彻斯特编码：跳0反跳1看中间，中必变
  • 上0下1
  • 下0上1
• 差分曼彻斯特编码：跳0不跳1看起点，中必变 技巧：区分曼彻斯特编码和差分曼彻斯特编码
• 如果中间跳变方向和二进制能够一一对应，就是曼彻斯特

说明：

• 在曼彻斯特编码中，每一位的中间有一跳变，位中间的跳变既作时钟信号，又作数据信号
• 接收方利用包含有同步信号的特殊编码从信号自身提取同步信号来锁定自己的时钟脉冲频率，达到同步目的

数据通信中使用曼彻斯特编码的主要原因:实现对通信过程中收发双发的数据同步

• 每一个码元都被调成两个电平，所以数据传输速率只有调制速率的1/2

无效的MAC帧

• 数据字段的长度与长度字段的值不一致
• 帧的长度不是整数个字节
• 用收到的帧检验序列 FCS 查出有差错
• 数据字段的长度不在 46 ~ 1500 字节之间

4.4 无线局域网

基本概念：

• 802.11无线局域网是星形拓扑，中心点为接入点(AP),也可称为无线接入点WAP
• AP(Access Point)---接入点：可以通俗理解成平时连接的无线WiFi热点
  • 通常具有"帧格式转换"功能，可以将在无线链路上传输的802.11帧格式，与有线链路上传输的以太网帧格式相互转换
• 基本服务集BSS:1个基站(AP)+多个移动站(一个Wifi热点连接了很多台手机电脑)
  • 服务集标识符SSID：无线局域网的名字，不超过32字节➡️WiFi名字
  • 基本服务区BSA：一个基本服务集能够覆盖的地理范围➡️站在哪里可以搜索到WiFi
• 门户Portal：可将802.11无线局域网接入802.3有线以太网/实现协议的转换
• 扩展服务集ESS:将多个AP连接到同一个分配系统，组成更大的服务集
• 漫游：一个移动站从一个基本服务集切换到另一个基本服务集，仍然可以保持通信

无线局域网面临的新问题： 为什么不采用CSMA/CA协议

• 硬件上很难实现"边听边发，冲突检测“
  • 接收信号的强度往往远小于发送信号的强度，且在无线介质上信号强度的动态变化范围很大
  • 无线电几乎是半双工的，意味着它们不能在一个频率上传输的同时侦听该频率上的突发噪声
• 不同站的传输范围可能不同，需要减少究竟在哪个站发送的模糊不清
  • 存在隐藏站/隐蔽站问题：未能检测出媒体上已存在的信号的问题/由于竞争者离得太远而无法检测到潜在的竞争者的问题叫做隐蔽站问题
    • 在无线通信中，并非所有站点都能够听见对方，发送节点没有冲突不意味着在接收节点处没有冲突
    • eg:当 A 正在给B发送数据时，C 检测不到无线信号，以为 B 是空闲的，因而都向 B 发送数据，结果发生碰撞
  • 存在暴露站问题
    • 一个站点由于检测到附近节点正在发送信号，而误以为自己不能发送，实际上自己的发送并不会干扰目标接收方，却仍然被迫等待的问题，叫做暴露站问题
    • eg:B 向 A 发送数据，而 C 又想和 D 通信。C 检测到媒体上有信号，于是就不敢向 D 发送数据。 困难：在开始一个传输之前，一个站真正希望知道的是接收方的周围是否有无线电活动情况，而CSMA只能告知在侦听载波的站的附近是否有活动发生

802.11网络模式

802.11使用的网络模式有两种

• 有架构模式(Infrastructure mode)
  • 每个客户端与接入点AP相关联，该接入点又与其他网络连接。客户端发送和接收数据包都要通过AP进行
  • 几个接入点可通过一个称为分布式系统的有线网络连接在一起，形成一个扩展的802.11网络。在这种情况下，客户端可通过它们的接入点向其他客户端发送帧
• 自组织模式(ad hoc Ad-hoc mode)
  • 网络由一组相互关联的计算机组成，它们之间可以直接向对方发送帧，无接入点

MACA

Multiple Access with Collision Avoidance (MACA) 冲突避免多路访问协议

基本思想：发送发刺激接收方输出一个短帧，以便其附近的站能检测到该次传输，从而避免在接下去进行的较大数据帧传输中也发送数据 考虑A➡️B发送一帧：

• A首先向B发送一个RTS帧，这个短帧包含了随后将要发送的数据帧的长度
• B用CTS作为应答，此帧也包含数据长度（从RTS复制过来），A在收到了CTS帧之后便开始传输
• 如果一个站听到了RTS帧，那么一定距离A很近，它必须保持沉默，至少等待足够长的时间以便在无冲突情况下CTS返回A
• 如果一个站听到了CTS，那么一定距离B很近，在接下来的数据传送过程中它必须一直保持沉默，只要检查CTS帧，该站就知道数据帧的长度，也就知道数据传输要持续多久
• 如果同时听到RTS和CTS，则在数据帧完成之前必须保持安静

尽管有了这些防范措施，冲突仍有可能发生 eg：B和C可能同时给A发送RTS帧，这些帧将发送冲突，因而丢失 在发生冲突的情况下，一个不成功的发送方（在期望的时间内间隔内没有听到CTS）将等待一段随机的时间后重试

CSMA/CA协议

CSMA with Collision Avoidence 带冲突避免的CSMA 发送过程中不用检测冲突，发送前想办法尽量避免冲突（但无法完全避免） 适用于无线网络 eg:802.11标准无线局域网技术 WiFi

两种操作模式：

• 分布式协调功能 DCF(Distributed Coordination Function)
  • 每个站都独立行事，没有任何一个中央控制机制
  • IEEE 802.11 的基本接入方式。它没有中央控制机制，各站点通过 CSMA/CA 方式独立竞争无线信道。站点发送前先监听信道，若信道空闲则等待 DIFS 并进行随机退避，退避结束后发送数据帧，接收方再返回 ACK 确认。由于各站点分布式地竞争信道，因此称为分布式协调功能
• 点协调功能 PCF(Point Coordination Function)【可选】
  • AP控制自己覆盖范围内的一切活动
  • 实际很少用到PCF，因为通常没有办法阻止临近网络中的站发送竞争流量

简单的工作方式（不考虑隐藏站+暴露站问题） 协议要点：

• 发送方：先听后发，忙则退避
  • 若信道空闲，间隔DIFS后，再发送帧(一口气发完，发送过程中不用检测冲突)
  • 若信道不空闲，则进行"随机退避"
• "随机退避"原理
  • 二进制指数后退算法确定一段随机退避时间（可理解为倒计时）
    • 此处倒计时为信道空闲时开启，当监听发现信道忙碌时，需要持续监听，直到信道空闲可以倒计时，若中间信道出现忙碌，则倒计时暂停，继续监听
  • 发送方会保持监听信道，只有信道空闲才扣除倒计时，倒计时结束后会立即发送帧
• 接收方：停止-等待协议➡️每收到一个正确数据帧都返回ACK，若发送方超时未收到ACK，则进行"随机退避" 书本： 通过侦听确定在一个很短的时间内（这段时间称为 DIFS，我们在下面解释）没有信号；然后倒计数空闲时间槽，当有帧在发送时暂停该计数器；当计数器递减到 0，该站就发送自己的帧。如果帧发送成功，目标站立即发送一个短确认。如果没有收到确认，则可推断出传输发生了错误，无论是冲突或是其他什么错。在这种情况下，发送方要加倍后退选择的时间槽数，再重新试图发送。如此反复，连续像以太网那样以指数后退，直到成功发送帧或达到重传的最大次数

帧间间隔IFS（InterFrame Space）

• DIFS 分布式协调IFS：常规的帧间间隔
  • 可理解为一个规定好的固定的时间片
• SIFS 短IFS：最短的帧间间隔，预留SIFS用于处理收到的帧（如完成差错控制）
• PIFS 中等长度的IFS
• AIFS 仲裁IFS:显示了不同优先级的例子
• EIFS：扩展IFS：用于一个帧刚刚收到坏帧或未知帧的报告问题 DIFS>SIFS>PIFS

解决减少哪个站在发送的模糊不清： 802.11定义了信道侦听包括物理侦听和虚拟侦听

• 物理侦听：简单地检查介质，看是否存在有效的信号
• 虚拟侦听：每个站可以保留一个信道何时要用的逻辑记录
  • 跟踪网络分配向量NAV(Network Allocation Vector)
    • NAV信号不传输的，只是站内部使用，提醒自己保留一定时间内的安静
  • 每个帧携带一个NAV字段说明这个帧所属的一系列数据将要传输多长时间，无意中听到这个帧的站就知道无论自己是否能够侦听到物理信号，由NAV指出的时间段信道一定是忙碌的

解决隐藏站问题——信道预约机制

使用NAV来解决隐藏站问题

预约：

• RTS控制帧(Request To Send))请求发送
  • 包括源地址、目的地址和这次通信所需的持续时间 同意预约/广而告之（已被约，请勿打扰）：
• CTS控制帧(Clear To Send)允许发送
  • 包括源地址、目的地址和这次通信所需的持续时间 总结：
• 发送方广播RTS控制帧（先听后发，忙则退避）
• AP广播CTS控制帧
• 其他无关节点收到CTS后自觉“禁言”一段时间（虚拟载波监听机制），发送方收到CTS后，就可以发送数据帧
• AP收到数据帧，进行CRC检验，若无差错返回ACK帧

场景：
A 想要向 B 发送数据。C 是一个位于 A 通信范围内的站点。D 是一个位于 B 通信范围内、但不在 A 通信范围内的站点。 A 先向 B 发送 RTS 帧，请求发送许可；B 收到后向 A 返回 CTS 帧，表示允许发送。随后 A 开始发送数据，并启动一个 ACK 定时器，等待 B 返回确认帧。 C 能够接收到 A 发出的 RTS 帧，因此 C 会设置自己的 NAV。 D 虽然听不到 A 的 RTS 帧，但它能听到 B 发出的 CTS 帧，因此 D 也会设置自己的 NAV

802.11帧的结构

帧的分类

• 数据帧

• 控制帧

  • ACK、RTS、CTS等

• 管理帧

  • 探测请求/探测响应帧 数据帧的格式

• 帧控制 Frame Control字段（11子字段）

  • 去往DS（To DS）/来自DS（From DS）：该帧是发送到或者来自于与AP连接的网络
    • 其中DS表示分布式系统
  • 重传(Retry)：这是以前某一帧的重传
  • 电源管理(Power management)：指明发送方进入节能模式
  • 更多数据(More data)：表明发送方还有更多的帧需要发送给接收方
  • 受保护的(Protected Frame)：该帧的帧体已经被加密
  • 顺序(Order)：告诉接受方高层希望严格按照顺序处理帧序列

• 持续时间 Duration：通知本帧和其确认帧将会占用信道多长时间/表示在本帧结束后还需占用信道多少时间

• 序号 Sequence：帧的编号，可用于重复帧的检测

  • 前4位标识fragment，后12位标识帧（每发出去一帧该数字递增）

• 数据 Data：0-2312字节

• 帧校验序列字段 Frame check sequence 记忆口诀： 30 N 4 首数验 首部3+1地址 九十比特表去来 帧的中转靠AP 去往AP中起止 来自AP止中起

• 中：中转点AP的MAC地址

• 起：发送方的MAC地址

• 止：接收方的MAC地址 管理帧的格式：管理帧与数据帧类似，只是少了一个基站地址，因为管理帧的作用范围被限制在单个小区内 控制帧的格式要短一些

• 只有一个或两个地址

• 没有数据部分和序号部分

4.8 数据链路层交换

网桥

定义：网桥连接多个局域网形成更大的局域网/把多个物理局域网连接成一个逻辑局域网

• 网桥工作在数据链路层，它们通过检查数据链路层地址/MAC地址来转发帧【知道MAC帧结构】
• 当一个广播帧到达时，网桥向所有的端口转发此帧

网桥并不是向所有的端口转发此帧，而是先检查其目的MAC地址，然后再确定将该帧转发到哪一个端口。

• 网桥只适合于用户数不太多(不超过几百个)和通信量不太大的局域网，否则有时还会产生较大的广播风暴

透明网桥：它是数据链路层的一种网桥，主要作用是根据 MAC 地址 转发或过滤帧

• 主机完全感觉不到网桥的存在，不需要知道网桥在哪里，也不需要做特殊配置

为什么出现多个LAN+网桥的好处？

• 由于各个部门的目标不同，所以不同部门可能选择了不同的 LAN
• 一个组织可能在地理上分布在几个楼宇，这些楼宇之间有一定的距离。在每个楼内有一个独立的 LAN，然后通过网桥和光纤链路将这些 LAN 连接起来，这种做法比起把全部电缆连到一个中央交换机要经济实惠得多
• 有时候可能有必要将一个逻辑上的单个 LAN 分成多个独立的 LAN（用网桥连接）以便适应网络的负载
• 物理距离过大：例如，对于以太网来说，如果距离超过约 2.5 km，就可能超出正常通信范围。
• 可靠性：与中继器不同，网桥可以被插入到网络中，用来决定哪些帧需要转发，哪些帧不需要转发。
• 网桥也有助于安全性：因为它不会像中继器那样无条件转发所有信号，而是可以根据 MAC 地址进行过滤，减少不必要的帧传播。
• Promiscuous mode：混杂模式，指网卡接收经过它的所有帧，而不仅仅接收发给自己的帧。

学习网桥

两个局域网连接在一起的拓扑结构分为两种情况：

• (a)：两个多点局域网通过一个特殊的站连接在一起，这个站就是同属于两个局域网的网桥
• (b)：局域网用点到点电缆连接在一起，包括一个集线器。网桥是站和集线器都能与之相连的设备

自学习功能

• hash table 哈希表
  • 为每个网桥配备一个大的哈希表，该表列出每个可能的目的地以及它隶属的输出端口
  • 初始为空
• flooding algorithm 泛洪算法
  • 当网桥第一次接入网络时，所有的哈希表都是空的，没有一个网桥知道哪个目标地址该往哪里去
  • 泛洪算法：对于每个发向未知目标地址的入境帧，网桥将它输出到所有的端口，但它来的哪个输入端口除外
  • 随着时间推移网桥会学习到每个目标地址在哪里，一旦知道了一个目标地址，以后向该目标地址发送的帧只被放到正确的端口，不再泛洪到所有端口
• backward learning 后向学习法
  • 网桥工作在混杂模式下，可以看到每个端口上发送的所有帧，通过检查这些帧的源地址，网桥就可获知通过哪个端口能访问到哪个机器
  • 举个例子：
• dynamic topologies 动态拓扑结构变化
  • 当打开、关闭或者移动机器和网桥时，网络的拓扑结构也会发生变化。为了处理这种动态的拓扑结构，一旦构造出一个哈希表项后，帧的到达时间也被记录在响应的表项中。当一帧到达时，如果它的源地址已经在表中，那么对应表项的时间值记录为当前时间（修改时间）
    • 与每个表项相关联的时间值反映了网桥最后看到该机器发出一帧的时间➡️以防某些节点拔线跑路
    • 在网桥中有一个进程定期扫描哈希表，并且将那些时间值在几分钟以前的表项都清除掉

对于一个入境帧，它在网桥中的路由过程取决于从哪个端口来（源端口），以及向哪个目标地址去（目标端口），整个转发过程如下：

• 如果去往目标地址的端口与源端口相同，则丢弃该帧
• 如果去往目标地址的端口与源端口不同，则精准转发该帧到目标端口
• 如果目标端口未知，则使用泛洪法，将该帧发送到除了入境端口外所有的端口
  • 如果目的地址是广播地址，则进行广播即可

生成树网桥

Spanning Tree Bridges

为了提高可靠性，网桥之间可使用冗余链路。在一对网桥之间并行设置了两条链路。这种设计可确保一条链路宕掉后，网络不会被分成两组计算机，使得它们之间无法通信

引入的问题：拓扑环路 解决方式：让网桥相互之间通信，然后用一棵可以到达每个网桥的生成树覆盖实际的拓扑结构 目的：为了避免产生转发的帧在网络中不断地兜圈子/出现环路，消耗网络资源

• 通过去掉一些链路，将拓扑结构抽象的图简化为一颗生成树，这棵树上无环路
• 一旦网桥同意这棵生成树，则站之间所有转发都将沿着这棵树进行，由于从每个源到每个目标只有唯一一条路径可走，所以不可能产生环路
• 一旦某个网桥产生故障，重新计算生成树

生成树的过程

• 网桥运行一个分布式的算法
• 每个网桥周期性从所有端口广播一个配置信息给邻居
• 同时处理其他网桥的配置信息
• 这些消息不被转发，只用作构建树用于随后帧的转发

生成树算法

• 每个桥广播自己的桥编号，号最小的桥称为生成树的根；

选择具体最低标识符的网桥成为生成树的根

• 每个网桥计算自己到根的最短路径，构造出生成树，使得每个LAN和桥到根的路径最短；
• 如果路径长度相同，选择经过最低标识符的路径；
• 当某个LAN或网桥发生故障时，要重新计算生成树；
• 生成树构造完后，算法继续执行以便自动发现拓扑结构变化，更新生成树。

交换方式

直通式交换/虫孔路由：网桥只要看到MAC地址（前六个字节）就可以决定如何转发帧，有可能一旦从入境线路输入帧的目的地址字段马上就可以转发，此时帧的其余部分还在输入 优点：降低了帧通过网桥的延迟以及网桥必须能缓存的帧数 缺点：不适用于需要速率匹配、协议转换或差错检测的线路

存储转发交换：交换机将帧完整接收并放入高速缓存中，检测帧的目的地址决定到底从哪个端口转发出去 优点：适用于需要速率匹配、协议转换或差错检测的线路 缺点：转发时延高

中继器／集线器／网桥／交换机／路由器和网关

Repeaters, Hubs, Bridges, Switches, Routers and Gateways➡️运行在不同的层次上➡️不同的设备使用不同的信息来决定如何交换