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

信道分配问题

  • 用于来自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“着色”