首页计软杂谈学习笔记
  • 负责确定多路访问信道下一个使用者
  • 数据链路层的一个重要部分，特别是对于局域网

# 信道分配问题

  • 用于来自 N 个用户的固定通道和流量
    • 使用 FDM、TDM、CDMA 等划分带宽
    • 这是一种静态分配，例如调频收音机
    • 这种静态分配对于突发流量的性能很差
    • 分配给用户的资源有时会被闲置
  • 动态分配在用户需要时为其提供通道
    • 对于 N 个用户，效率可能是 N 倍

# 动态信道分配的假设

  • 流量独立
  • 单信道
  • 冲突可观察
  • 时间连续或分槽
  • 载波侦听或不听

# 多访问协议

# ALOHA

  • 由夏威夷大学的 Norm Abramson 开发
  • 完全分散协议

# 纯 ALOHA

  • 在纯 ALOHA 中，用户只要有数据就发送帧
  • 用户在发生冲突后选择随机的时间后重试
    • 低负载下的高效低延迟
  • 当其他用户在两倍于帧时间的脆弱时段内传输时，会发生冲突
  • 将发送端与时间槽同步可以减少冲突
    • 帧时间：帧长度除以比特率
  • 吞吐量S=G×e(−2G)S = G \times e^ {(-2G)}
  • 最大吞吐量出现在G=0.5，S=1/2e=18.4%G = 0.5，S = 1/2e = 18.4\%

# 分槽 ALOHA

  • 分槽 ALOHA 的效率是纯 ALOHA 的两倍
  • 低负载浪费时间槽，高负载导致碰撞
  • 吞吐量S=G×e(−G)S = G \times e^ {(-G)}
  • 最大吞吐量出现在G=1，S=1/e=36.8%G = 1，S = 1/e = 36.8\%

# CSMA

  • CSMA 通过感知信道改进了 ALOHA
    • 如果用户感觉到其他人，则不会发送
    • “先感知后传输” 或 “先听后说” 的原则
  • 1 - 坚持 CSMA 持续侦听，一有空闲立即发送
  • 非坚持 CSMA 如果侦听存在载波，则等待随机时间，然后重复上述步骤，会带来更大延迟，但有更好的信道利用率
  • p - 坚持 CSMA 试用与分时间槽的信道。如果侦听时信道空闲，则按概率 p 发送数据，概率 1-p 推迟到下一个时间槽，如果发生冲突，则等待随机时间，然后重复上述步骤

# 带冲突检测的 CSMA

  • CSMA/CD 的改进是检测 / 中止冲突
  • 减少竞争时间以提高性能
  • 一个站在发送帧后监听介质，以查看传输是否成功
    • 如果是这样的话，这个站就结束了
    • 如果发生碰撞，将立即终止发送，随机等待一段时间后帧将再次发送
  • 一个站传输了 2τ 后没有监听到冲突，则可以确保自己抓住了信道（τ 为两个相距最远的站传播信号所需要的时间）

# 无冲突协议

  • 无冲突协议完全避免冲突
  • 发送方必须知道何时轮到他们发送

# 位图协议

  • 如果发送方有数据，则在竞争槽中设置一位
  • 发送者依次发送；每个人都知道谁有数据

# 令牌传递

  • 令牌发送环定义发送顺序
    • 具有令牌的站点可以在通过之前发送帧
    • 也可以在没有环的情况下使用，例如令牌总线

# 二进制倒计数

  • 二进制倒计数改进了位图协议
  • 站点在争用插槽中以二进制位串的形式广播自己的地址
  • 异或这些位；站点在发送 “0” 但异或结果为 “1” 时放弃

# 有限竞争协议

  • 在低负载下采用竞争的做法而提供较短的延迟，而在高负载下采用无冲突技术，从而获得良好的信道效率
  • 将站分成几组，其中只有很少一部分可能想要发送
    • 避免因空闲时间和冲突而造成的浪费

# 自适应树遍历协议

  • 树将站点分成组（节点）进行轮询
    • 深度优先搜索具有冲突的节点下的树
    • 如果 > 1 个站点，则在较低层开始搜索

# 无线局域网协议

  • 与有线相比，无线具有复杂性
  • 节点可能具有不同的覆盖区域，这导致了隐藏终端和暴露终端
  • 节点无法检测冲突，即发送时无法感知冲突，这使碰撞变得昂贵且必须避免

# 隐藏终端

  • 隐藏终端是发送方，它们不能相互感知，但会在预期的接收方处发生碰撞

# 暴露终端

  • 暴露终端是能够相互感知但仍能安全传输（到不同接收器）的发送方

# 冲突避免多路访问（MACA）

  • MACA 协议授予 A 发送给 B 的访问权：
    • A 向 B 发送 RTS；B 回复 CTS
    • A 可以使用暴露但不隐藏的终端进行发送

# 以太网

# 经典以太网

  • 一条共享同轴电缆，所有主机都连接到该电缆
  • 高达 10 Mbps，采用曼彻斯特编码
  • 主机运行经典的以太网协议进行访问
  • MAC 协议是 1-persistent CSMA/CD（早期）
  • 使用 BEB（二进制指数后退的 CSMA/CA）计算碰撞后的随机延迟（后退）
  • 帧格式仍然用于现代以太网
    • DIX 前导码 + 目标地址 + 源地址 + 类型 + 数据 + 填充 + 校验和
    • IEEE802.3 前导码（SOF）+ 目标地址 + 源地址 + 长度 + 数据 + 填充 + 校验和
    • 最大数据长度 1500 字节，最小数据长度 46 字节（帧最小数据长度 64 字节，为了有效冲突检测）

# BEB

  • 在第 i 次冲突后，从 0-2^i-1 之间选择一个随机数，等待这么多的时间槽
  • 达到 10 次冲突后，随机数的选择区间被固定在 1023
  • 16 次冲突后，放弃努力并返回一个失败报告

# 单播 / 组播 / 多播

  • 要找到地址的类型，我们需要查看左边的第二个十六进制数字
    • 如果是偶数，则地址为单播
    • 如果是奇数，则地址为多播
    • 如果所有数字都是 F，则为广播地址

# 性能

  • 适用于大帧，即使有多个发送者
  • 小帧（和长局域网）性能下降

# 交换式以太网

  • 集线器将所有线路连接到单个 CSMA/CD 域中
  • 交换机将每个端口隔离到单独的域
    • 多端口的吞吐量要大得多
    • 无需使用带有全双工线路的 CSMA/CD

# 快速以太网

  • 快速以太网扩展以太网，从 10 Mbps 扩展到 100 Mbps
    • MAC 子层保持不变
    • 为了保持帧的最小大小，网络电缆的最大长度应缩短 10 倍
    • 双绞线（5 类）占据市场

# 千兆 / 10 千兆以太网

  • 在计算机 / 交换机之间使用全双工线路
  • 地址长度、帧格式以及最大和最小帧长度保持不变。
  • 为了实现 1 Gbps 的数据速率，这不再可能保持 MAC 子层不变
  • 千兆以太网有两种不同的介质访问方法：
    • 半双工：与集线器一起使用。需要 CSMA/CD。最大距离是传统以太网（2500m）的 1/100 倍（2500m->25m）
    • 全双工：“正常” 模式。用于中央交换机。所有的线路具有缓冲能力。没有竞争，无需 CSMA/CD
  • 增加半径的两个标准功能：
    • 载波扩充（carrier extension）：告诉硬件在正常帧（64 字节）后添加自己的填充，以将帧扩展到 512 字节
    • 帧突发（frame bursting）：允许发送方在一次传输中传输多个帧的串联序列
  • 这两个功能将网络的半径扩展到 200 米

# 无线局域网

# 802.11 体系结构和协议栈

  • 无线客户端与有线 AP（接入点）关联
    • 这被称为基础设施模式；也有没有 AP 的自组织模式，较罕见
  • MAC 用于不同的物理层

# 802.11 物理层

  • 网卡与多个物理层兼容
    • 例如 802.11 a/b/g

# 802.11MAC 子层

  • CSMA/CA 插入后退槽以避免冲突
  • MAC 对无线错误使用 ACK / 重传

# 802.11 帧结构

  • 帧因其类型而异（帧控制）
  • 数据帧有 3 个地址要通过 AP 传递

# 数据链路层交换

# 学习网桥

  • 后向学习算法选择输出端口：
    • 将帧上的源地址与输入端口关联
    • 带有目标地址的帧被送到已经学习过的端口
    • 未学习的目的地将发送到所有其他端口（泛洪算法）

# 生成树网桥

  • 具有循环和只有反向学习的桥接拓扑将导致帧永远循环
    • 需要支持生成树来解决问题
  • 数据转发端口的子集用于避免循环
  • 使用 Perlman 生成算法选择 Perlman 生成树

# 虚拟局域网

  • VLAN（虚拟 LAN）将一个物理 LAN 拆分为多个逻辑 LAN，以简化管理任务
    • 端口根据其 VLAN “着色”