五、链路层

5.1 概述

5.1.1 术语

  • 主要讨论传播时延：从输出链路的起点到目的地传播所需的时间

  • 节点：主机和路由器

  • 链路：沿着通信路径连接相邻节点的通信信道

  • 帧：数据链路层的分组单元

    链路层负责将数据报封装成帧通过链路从一个节点传输到物理上相邻的下一个节点

5.1.2 链路层基本模型

  • 数据报在不同链路上可能由不同的链路层协议进行处理

    第一段链路上由$PPP$处理，最后一段链路上由以太网处理，中间链路上由广域链路层协议处理

  • 不同的链路层协议可能提供不同的服务

  • 链路层提供的服务

    • 成帧、链路访问：将数据加上头部和尾部，封装成数据帧，其中帧头部用$MAC$地址标识源和目的地
    • 可靠传递：用于误码率高的链路，如无线链路
    • 流量控制：在相邻的收发节点间限制流量
    • 差错检测：接收方检测到错误存在后，给发送方发送信号要求重传或丢弃该数据帧
    • 差错纠正：接收方检测和纠正帧中错误，不用重传
    • 半双工和全双工：半双工时，链路两端的节点都能传输分组，但不能同时传输

  • 链路层的实现

    • 链路层在“适配器”（网卡$NIC$）或者芯片上实现

5.1.3 差错检测和纠正

  • 单比特奇偶校验：检测单个比特错误
  • 二维奇偶校验：检测和纠正单个比特错误
  • 因特网检查和：用于$TCP$、$UDP$和$IPv4$协议中
  • $CRC$冗余校验：广泛应用于以太网、$802.11\enspace WiFi$、$ATM$

5.2 多路访问链路和协议

5.2.1 链路概述

  • 链路类型

    • 点到点链路：$PPP$/以太网交换机和主机之间的点到点链路
    • 广播链路(共享线路或介质)：传统以太网/$802.11$无线$LAN$

  • 链路特点

    • 单个共享广播信道

    • 两个或多个节点同时传输时，会相互干扰

      碰撞：一个节点同时收到两个或多个信号

5.2.2 信道划分协议

  • 协议概述

    • 信道划分协议：将信道划分成小的“片”（时隙、频率、编码）分配给节点使用

  • $TDMA(Time\enspace Division\enspace Multiple\enspace Access)$

    • 循环访问信道
    • 每个节点在每次循环中得到固定长度的时隙（时隙长度＝传输单个分组时间）
    • 没有数据发送的时隙空闲

  • $FDMA(Frequence\enspace Division\enspace Multiple\enspace Access)$

    • 信道按频谱分成若干频段
    • 每个节点分配固定频段
    • 在频段不用时该部分信道被闲置和浪费

  • $CDMA(Code\enspace Division\enspace Multiple\enspace Access)$

    • 每个用户使用自己的码片序列对数据编码
    • 当需要发送比特$1$时，发送$mbit$码片序列
    • 当需要发送比特$0$时，发送$mbit$码片序列的二进制反码

5.2.3 随机访问协议

  • 协议概述
    • 当节点有数据发送时，以信道全部速率$R$传输，没有主节点起协调作用，因此两个或多个节点发送时会发生碰撞
    • 如何检测碰撞
    • 如何从碰撞中恢复，如延时后重传
  • $ALOHA(Additive\enspace Link\enspace On-Line\enspace HAwaii\enspace system)$
  • 时隙$ALOHA$
  • 载波监听$CSMA$
  • 带冲突检测的载波侦听$CSMA/CD$

5.2.4 轮流协议

  • 协议概述

    • 信道划分协议在低负荷时效率低——即使只有一个活动节点，也只能分配到$\frac{1}{N}$的带宽
    • 随机访问协议在高负荷时效率低——碰撞的开销增加

  • 轮询协议

  • 令牌传递协议

5.3 交换局域网

5.3.1 $MAC$地址

  • 又称为$LAN$地址、物理地址
  • $48$比特，前$24$比特由$IEEE$分配管理——$OUI$号，后$24$比特由厂商自行分配
  • 通常采用十六进制表示法，如$5C-66-AB-90-75-B1$
  • 在数据链路层标识每块网络适配器，使得能够在广播信道上寻址目标节点
  • $MAC$地址烧入网络适配器的$ROM$中，不可更改
  • $MAC$地址类似于身份证号，不会随着网络迁移而改变；$IP$类似于邮件通信地址，需要根据网络配置策略更改
  • 和网络层地址类似，主机和路由器上的每个接口（适配器）也都有链路层地址，但是链路层交换机的接口没有链路层地址
  • 链路层交换机的作用是在主机和路由器之间承载数据报，并透明地执行该任务

5.3.2 地址解析协议$ARP$

  • 协议概述

    • 根据目标的$IP$地址获取其$MAC$地址
    • 每台主机或路由器上存在$ARP$表，包含从$IP$地址到$MAC$地址的映射关系，具体存储为$\langle IP,MAC,TTL\rangle$
    • $ARP$协议工作在网络层和链路层之间

  • 同一局域网内工作流程

    • 建立$ARP$请求包

    • 广播$ARP$请求包

    • 建立$ARP$应答包

      • 局域网内的所有适配器都把帧中的$ARP$分组向上传递给$ARP$模块

      • 与目的$IP$地址匹配的适配器构建应答包

      • 向源发送应答包

        • 源更新$ARP$表

  • 局域网间工作流程

    • 发送方主机首先获取两个局域网间路由器的端口的$MAC$地址（ARP）
    • 发送方向路由器发送帧
    • 路由器根据路由转发表转发数据报到输出接口
    • 输出接口将数据报发送给其适配器
    • 适配器封装称新的帧，发送至另一个子网，此时的$MAC$地址即为目的主机地址

5.4 以太网

5.4.1 以太网帧结构

  • 数据最长$1500$个字节

  • 前同步码：总共$8$字节

    • 前$7$字节用于唤醒接收适配器，并同步时钟

    • 前$7$字节为$10101010$，最后一个字节为$10101011$

  • 地址：$6$字节，若适配器收到以太网帧，目的地址为自己的$MAC$地址或广播地址（如$ARP$包），就将帧中的数据传给网络层，否则丢弃该帧

  • 类型：上层协议类型（大多为$IP$协议，也支持其它协议，如$AppleTalk$）

  • $CRC$：由接收方检查,若检测到错误，就将该帧丢弃

  • 以太网提供的服务

    • 无连接的服务：在发送适配器和接收适配器之间不需要握手
    • 不可靠的服务：接收适配器不发送确认帧或否认帧给发送方

5.4.2 $CSMA/CD$

  • 特点

    • 没有时隙
    • 当适配器侦听到其它适配器在传输，则它不传输帧，即载波侦听
    • 正在传输的适配器若检测到其它适配器也在传输，则它中止自己的传输，即碰撞检测
    • 在重新传输之前，适配器要等待一段随机时间，即随机回退

  • 术语

    • 拥塞信号：长度为$48$比特，用来确保所有传输者都能检测到碰撞而传输的信号

    • 比特时间：传输$1$比特所需时间

      在$10Mbps$的以太网中，当$K=1023$时，等待时间大约为$50ms$

  • 算法

    • 适配器收到来自网络层的数据报，创建帧

    • 若适配器检测到信道空闲，则开始传输帧；若检测到信道忙，就开始等待，直到信道空闲再开始传输该帧

    • 若适配器传输了整个帧而没有检测到其它适配器的传输，则该适配器完成该帧的传输

    • 若适配器在传输时检测到其它适配器也在传输，则停止传输，发送拥塞信号

    • 中止传输后，适配器进入指数回退阶段，在经历第$m$次碰撞后，适配器随机从${0,1,2,\cdots,2^m-1}$中选择$K$值。适配器在等待$ K*512$比特时间后，返回第$2$步

  • 指数回退算法

    • 目的：适配器重传时试图估计正确的负载
      • 重载：随机等待的时间可能会更长
    • 第一次碰撞后：从${0,1}$中选择$K$；延迟是$K*512$比特传输时间
    • 第二次碰撞后：从${0,1,2, 3}$中选择$K$
    • 第十次碰撞后：从${0,1,2,3,4,…,1023}$中选择$K$

  • 只能进行半双工通信

5.4.3 争用期

  • 什么是争用期
    • $A$向$B$发送数据，$\tau$后到达$B$（端到端传播时延，记为$τ$）
    • 若$B$在$A$的数据到达之前，发送自己的数据（这时$B$检测信道是空闲的，因为它没收到任何数据），则必然会与$A$的数据在信道中发生碰撞
    • $A$在发送后多久才能知道发生碰撞？要等到$B$的数据到达$A$，而$A$还未结束发送
    • 假设一个极端情况，当图中所示的时间差$\delta$（$\delta$为$B$发送数据时刻与$A$数据到达$B$的时刻的时间差）趋向于$0$，则$A$检测到发生碰撞的时间$2\tau-\delta= 2\tau$
    • 当超过这个时间都未检测到碰撞，则$A$发送出的数据就一定不会产生碰撞了。
    • 以太网中端到端的往返时间$2\tau$称为争用期，也叫碰撞时间
    • 只有经过争用期这段时间还未检测到碰撞，才能肯定这次发送不会发生碰撞，这时就可以放心把这一帧发送完毕。
  • 传统以太网（$10Mbps$）规定争用期为$51.2μs$，最短有效帧长为$64$字节
  • 最短有效帧长=$2τ*$链路传输速率
  • 当传送前$64$个字节内没有发生碰撞时，就一直占用信道直到传输完毕所有字节（此时有其他数据来到时必须等待）
  • 如果发生碰撞，则一定是在发送的前$64$字节之内
  • 任何小于$64$字节的帧都是由于冲突而异常中止的无效帧

5.4.4 以太网交换机

  • 链路层设备，负责存储转发以太网帧

  • 主机不知道交换机的存在

  • 检查帧头部，根据目的$MAC$地址转发

  • 交换机的工作原理

    • 交换机不转发同一网段内通信的帧
    • 当收到帧的目的地$MAC$地址属于另一个网段，则通过交换表决定向何端口转发
    • 类比于物流中转站，从不同的物流点接受包裹（帧），当物流中转站发现包裹没有问题（帧无差错）时，保留包裹（缓存帧），否则丢弃包裹但不会要求商家重发包裹（不会要求帧重发），而由运输层处理丢包问题。物流中转站根据包裹发往的地址决定转到什么物流（交换机转发），并且不会修改包裹的寄件人地址（交换机不修改帧的源地址）

  • 交换机转发和过滤

    • 过滤：决定一个帧应该转发到某个接口还是丢弃帧
    • 转发：决定一个帧应该被导向到哪个接口，并将其移动到那些接口
    • 转发和过滤借助交换机表完成，其表项为<$MAC$地址，通向该地址的交换机接口，表项放在表中的时间>

  • 交换机自学习

    • 交换机表初始为空
    • 对于在每个接口接收到的每个入帧，存储一个表项
    • 根据表项存储时间和老化期清除表项

  • 与路由器对比

路由器 以太网交换机 集线器
类型 网络层设备 链路层设备 链路层设备
维护 维护路由表 维护交换表
算法 路由算法 MAC地址过滤、学习算法
是否需配置 需要配置 即插即用 即插即用

六、无线网络

6.1 概述

  • 特性
    • 无线特性：基于无线链路
    • 移动特性：用户的网络接入点变化
  • 包含固定基础设施的网络组成
    • 无线主机——手机
    • 无线链路——大气层
      • 信号强度递减
      • 会受到来自其他源的干扰
      • 多径传播
      • 比特差错率高于有线网络
        • 采用$CRC$进行校验
        • 采用$ARQ$协议重传
    • 基站——连接无线网络，负责转发覆盖范围内的主机的分组，起到链路层中继作用
      • 关联：主机在某个基站的覆盖范围内
      • 切换：主机从某个基站切换到另一个基站
    • 基础设施——预先建立的固定基站
  • $Ad\enspace hoc$网络
    • 不包含固定基础设施的自组网络——无基站
    • 每个移动主机兼具主机和基站的作用
    • 节点(移动主机)仅仅能够在其覆盖范围内向其他节点传送数据
    • 节点之间相互通信组成的临时网络：在它们内部进行选路和地址分配
  • 无线链路的质量
    • 信噪比$SNR(SIGNAL-NOISE\enspace RATIO)$：信号强度与噪声强度的比值
    • 比特差错率$BER(Bit\enspace Error\enspace Rate)$
    • 调制方案相同，$SNR$越高，$BER$越低；$SNR$相同 ，比特传输率高的调制方案的$BER$高

6.2 $WiFi$概述

  • 执行$802.11$协议的无线$LAN$
  • $802.11$协议是一个协议簇，使用$CSMA/CA$协议进行多路访问
    • $802.11a$的频率范围为$5.1\sim5.8GHz$
    • $802.11ac$的频率范围为$5.1\sim5.8GHz$，支持单流和多流通信
    • $802.11b$的频率范围为$2.4\sim2.485GHz$，不需要许可证
    • $802.11g$的频率范围为$2.4\sim2.485GHz$
    • $802.11n$的频率范围为$2.4\sim2.485GHz$和$5.1\sim5.8GHz$，支持单流和多流通信
  • $802.11b$的信道划分
    • 将$85MHz$划分为$11$个部分重叠的信道，仅当两个信道间隔$4$个及以上的信道时没有重叠，可以同时工作，如$1、6、11$
    • 每个无线访问接入点$AP$周期性发送信标帧，包含自己的$SSID$和$MAC$
    • 主机扫描$11$个信道获取所有可用的$AP$的信标帧
    • 主机连接到某个$AP$，加入其子网，并通过$dhcp$获取$IP$地址（需要身份鉴别）
  • 发送流程
    • 监听到信道闲置$DIFS$秒后才开始传输帧，并且不进行冲突检测
    • 监听到信道忙后，则定时避退，定时到且信道闲置就发送数据
    • 接收方收到帧后，等待$SIFS$秒发送$ACK$
    • 发送方收到确认后，继续发送数据；没有收到确认则重新发送
  • 冲突避免
    • 发送方在发送帧之前，使用$CSMA$协议发送短的请求$RTS$帧给$AP$（$RTS$也可能冲突）预约信道
    • $AP$回应允许发送$CTS$帧表示预约成功
    • 其他发送方也能接收到$RTS$帧，收到后推迟自己的发送
    • 如果$RTS$发生冲突，则两个发送方进行随即回退，总有一方先发送第二个$RTS$帧