链路层

5.1 数据链路层服务

链路层服务

• 组帧
  • 封装数据报构成数据帧，加首部和尾部
  • 帧同步
• 链路接入
• 相邻节点间可靠交付
  • 低误码率的有线链路上很少采用（如光纤、某些双绞线等）
  • 无线链路：高误码率，需要可靠交付
• 流量控制
• 差错检测和纠正
  • 信号衰减和噪声会引起差错

链路层实现

• 网络适配器（网络接口卡——NIC）
• 由硬件和软件构成

5.2 差错编码

• 汉明距离
  • 两个码字对应位置不同字符的个数
• 最小汉明距离
  • 在一个码组集合中，任意两个编码之间汉明距离的最小值
• $L-1=D+C$
  • 检错码
    • 若编码集的汉明距离$d_s=r+1$，则给差错编码可以检测r位的差错
  • 纠错码
    • 若编码集的汉明距离$d_s=2r+1$，则该差错编码可以纠正r位的差错
• 奇偶校验码
  • 1bit校验位
  • 二维奇偶校验
• Internet校验和（Checksum）
• 循环冗余校验码（CRC）
  • 基于模2运算
  • 生成多项式G（r+1位）；
    D为待传输的数据比特；
    R为r位的CRC校验码
  • 发送端：生成R（D除以G的余数），使得<D,R>刚好能被G整除
  • 接收端：利用G除<D,R>，余式全0，则没有出错；否则，出错

5.3 多路访问协议

• 链路分类

  链路	举例
  点对点链路	点对点协议(PPP)、高级数据链路控制(HDLC)
  广播链路	局域网

信道划分协议

• 时分多址（TDMA）
  • 消除了碰撞且公平
  • 传输速率受限
• 频分多址（FDMA）
  • 消除了碰撞且公平
  • 传输速率受限
• 码分多址（CDMA）
  • 不同节点可同时传输
  • 蜂窝电话

随机接入协议

• 一个传输节点总是以信道的全部速率发送分组
• 节点间没有事先协调

时隙ALOHA

• 每个节点同步
• 当节点有新的数据帧，在下一个时隙发送
  • 如果无冲突：该节点可以在下一个时隙继续发送新的帧
  • 如果冲突：该节点在下一个时隙以概率p重传该帧，直至成功
• 效率：长期运行时，成功发送帧的时隙所占比例
  • $Np(1-p)^{N-1}$
  • 最大效率 $= 1/e = 0.37$ （多个活跃节点）

ALOHA

非时隙ALOHA

• 当有新的帧生成时，立即发送
• 冲突可能性增大
• 效率 $=Np(1-p)^{2(N-1)}$
  • 最大效率 $= 1/2e = 0.18$ （多个活跃节点）

载波侦听多路访问（CSMA）

• 载波侦听：一个节点在传输前先听信道
  • 信道空闲：发送完整帧
  • 信道忙：推迟发送
    • 1-坚持CSMA：一直监听信道
    • 非坚持CSMA：随机等待一段时间，再监听信道（例：二进制指数后退算法）
    • P-坚持CSMA：以概率p监听信道
• 冲突仍可能发生：信号传播时延
• CSMA/CD（具有碰撞检测的CSMA）
  • 短时间内可以检测到冲突
  • 冲突后传输终止，减少信道浪费
  • 有线局域网易于实现，无线局域网难以实现
  • $L/R\geq 2d_{max}/V$
  • $L_{min}/R = 2d_{max}/V$
  • $L_{min}/R = RTT_{max}$
  • 效率：$=\frac{1}{1+5t_{prop}/t_{trans}}$
• CSMA/CA（带碰撞避免的CSMA）
  • 应用于802.11无线局域网

轮流协议

• 轮询协议
  • 存在主节点
    • 主节点轮流“邀请”从属节点发送数据（通过报文通知）
  • 问题：轮询开销、等待延迟、单点故障
• 令牌传递
  • 控制令牌依次从一个节点传递到下一个节点（以某种固定顺序）
    • 持有令牌才可发送帧
  • 令牌：特殊帧
  • 问题：令牌开销、等待延迟、单点故障

5.4 链路层寻址和ARP

MAC地址

也称：LAN地址、物理地址、链路层地址

• 作用：由局域网内标识一个帧从哪个接口发出，到达哪个物理相连的其他接口
• 长度：48位，6个字节，由十六进制表示，固化在网卡的ROM中，有时也可用软件更改
  • 广播地址：FF-FF-FF-FF-FF-FF
• 扁平结构
  • IEEE管理MAC空间地址
  • 没有两块适配器具有相同的地址

ARP：地址解析协议

• ARP表：每台主机或路由器维护一个表
  • IP/MAC地址映射关系
    • TTL：从表中删除每个映射的时间（过期时间）
    • <IP地址；MAC地址；TTL>
• 同一局域网内
  • 发送方构造查询ARP报文，在广播帧中发送
  • 正确的接收方构造响应ARP报文（附有自己的MAC地址），在标准帧中发送
• 子网以外
  • 将目的MAC地址设置为默认网关的MAC地址
• “即插即用”协议
  • 节点自主创建ARP表，无需干预

5.5 以太网

• 物理拓扑
  • 总线(bus)
    • 所有节点在同一冲突域
  • 星型(star)
    • 使用中心交换机
    • 每个节点一个单独冲突域（节点间彼此不冲突）
• 提供的服务
  • 无连接：没有“握手”
  • 不可靠：不进行确认

以太网CSMA/CD算法（二进制指数退避）

1. NIC从网络层接收数据报，创建数据帧
2. 监听信道
   • 如果NIC监听到信道空闲，则开始发送帧
   • 如果NIC监听到信道忙，则一直等待到信道空闲，然后发送帧
3. NIC发送完整个帧，若没有检测到其他节点的数据发送，则NIC确认帧发送成功
4. 如果NIC检测到其他节点传输数据，则终止发送，并发送堵塞信号
5. 中止发送后，NIC进入二进制指数退避：
   • 第m次连续冲突后：
     • 取$n = Min$ { $ m, 10 $ }
     • NIC从{$0,1,2,……,2^n-1$}中随机选择一个数K
     • NIC等待$K·512$比特的传输延迟时间，再返回第2步
   • 连续中途次数越多，平均等待时间越长

以太网帧结构

• 前导码（前同步码）
  • 共8B：前7个字节为10101010；第8个字节为10101011
  • 用于发送端与接收端的时钟同步
• 目的MAC地址、源MAC地址（各6B）
• 类型（2B）
  • 指示帧中封装的是哪种高层协议的分组（IP、Novell IPX或AppleTalk等）
• 数据（46-1500B）
• CRC（4B）：循环冗余校验码
  • 丢弃差错帧

不同标准

• 802.3中不同的以太网标准
  • 采用相同的MAC协议和帧格式
  • 不同速率：2Mbps、10Mbps、100Mbps、1Gbps、10Gbps
  • 不同物理介质：光纤、线缆

以太网交换机

• 功能：存储-转发以太网帧
• 特点：
  • 透明：主机感知不到交换机的存在
  • 即插即用
  • 自学习
  • 交换机在每段链路上利用CSMA/CD收发帧，但无冲突，且可以全双工（每段链路一个独立的冲突域）
  • 多端口间同时传输
• 交换表
  • (主机的MAC地址、到达主机的接口、时间戳)
  • 通过自学习建立交换表：接收到帧时，记录帧的源MAC地址与输入链路接口
  • 过滤、转发
    • 目的MAC在表中
      • 位于收到帧的局域网网段——>丢弃帧
      • 否则——>将该帧转发到表中对应的接口（放到输出缓存）
    • 目的MAC不在表中
      • 泛洪（广播该帧）
• 安全隐患
  • 交换机毒化

交换机 vs 路由器

• 两者均为存储-转发设备
  • 路由器：网络层设备（检测网络层分组首部）
  • 交换机：链路层设备（检测链路层帧的首部）
• 两者均使用转发表
  • 路由器：利用路由算法（路由协议）计算，依据IP地址
  • 交换机：利用自学习、泛洪构建转发表，依据MAC地址

• 网络设备对比

  	集线器	交换机	网桥	路由器
  层次	1	2	2	3
  流量隔离 (冲突域)	n	y	y	y
  广播域隔离	n	n	n	y
  即插即用	y	y	y	n
  优化路由	n	n	n	y
  直通传输 (边收边发)	y	y	y	n

5.6 虚拟局域网（VLAN）

• 支持VLAN划分的交换机，可逻辑地划分定义多个VLAN
  • 流量隔离：每个VLAN中的端口形成一个广播域
  • 动态成员：端口可以动态分配给不同VLAN
• VLAN间转发
  1. 通过一台外部路由器（厂家通常会将VLAN交换机和路由器会集成在一起）
  2. 多线缆连接
     • 每个线缆连接一个VLAN
  3. VLAN干线连接（VLAN trunking）
     • 交换机的干线端口互联
     • 802.1Q帧
       • VLAN标签（4B）
         • 2B的标记协议ID：0x8100
         • 2B标记控制信息

5.7 PPP协议

设计需求

• 组帧
• 比特透明传输：数据域必须支持承载任何比特模式
• 差错检测
• 连接活性检测：检测、并向网络层通知链路失效
• 网络层地址协商：端节点可以学习/配置彼此网络地址

数据帧

字段	说明
标志	定界符(01111110)，位于首尾
地址	无效
控制	无效
协议	上层协议
信息	上层协议分组数据
校验	CRC校验，用于差错检测

• 字节填充
  • 发送端
    • 在数据中的01111110和01111101字节前添加额外的字节01111101
  • 接收端
    • 01111101+上述二者其一：丢弃第1个，第2个作为数据接收
    • 单个01111110：标志字节

进行数据交换之前

• 配置PPP链路
  • 最大帧长
  • 身份认证
  • ……
• 学习/配置网络层信息
  • 对于IP协议：通过交换IPCP协议报文，完成IP地址等相关信息配置

5.8 WiFi: 802.11 无线LAN

IEEE 802.11标准

• 802.11b
  • 2.4~2.5GHz频段
  • 最高速率：11Mbps
  • 物理层：直接序列扩频技术（DSSS）
    • 所有主机使用相同的码片序列
• 802.11a
  • 5~6GHz频段
  • 最高速率：54Mbps
  • 物理层：OFDM
• 802.11g
  • 2.4~2.5GHz频段
  • 最高速率：54Mbps
  • 物理层：OFDM
• 802.11n
  • 2.4~2.5GHz频段
  • 最高速率：600Mbps
  • 物理层：多天线(MIMO)、OFDM
• 均使用CSMA/CA多路访问控制协议
• 均有基础设施（基站）网络模式和特定网（自组网）网络模式

体系结构

• 基站=接入点AP
• 基本服务集BSS
  • 包含一个或多个无线站点和一个AP
• 基础设施网络模式：无线主机+AP
• 自组网模式：只有主机

信道与关联

• 802.11运行在2.4GHz~2.485GHz频谱划分为11个部分重叠的信道
  • 每个AP选择一个信道
  • 每一个AP由服务集标识符(SSID)标记
• 扫描信道
  • 被动扫描
    • 各AP发送信标帧（AP的SSID和MAC地址）
    • 主机向选择的AP发送关联请求帧
    • AP向主机发送关联响应帧
  • 主动扫描
    • 主机主动广播探测请求帧
    • AP发送探测响应帧
    • 主机向选择的AP发送关联请求帧
    • AP向主机发送关联响应帧
• AP鉴别无线站点
  • 基于无线站点的MAC地址
  • 用户名和口令

802.11 MAC协议—CSMA/CA

不实现碰撞检测的原因

• 在802.11适配器上，接收信号的强度通常 « 发送信号的强度
• 适配器会由于隐藏终端问题和衰减问题而无法检测到所有的碰撞

• 使用链路层确认/重传（ARQ）方案
• 通信流程
  • DIFS（分布式帧间间隔）
  • SIFS（短帧间间隔）
• 处理隐藏终端问题
  • RTS（短请求发送控制帧）
    • 包括源地址、目的地址和这次通信所持续的时间
  • CTS（短允许发送控制帧）
    • AP广播该帧：一方面返回确认给源主机；另一方面，告诉其他节点，信道已经被预约，请不要发送数据
  • 注：RTS/CTS交换仅仅用于为长数据帧预约信道

802.11 帧

在相同IP子网中的移动性

• 主机从BSS1移动到BSS2（其中，BSS1和BSS2位于同一个子网中），它可以保持自己的IP地址和所有正在进行的TCP连接

蓝牙和ZigBee

• IEEE 802.15.1网络（蓝牙）

  也称无线个人域网络（WPAN）

  • 使用TDM
  • 自组织网络
    • piconet(皮可网)
      • 主设备、从设备、寄放设备
• IEEE 802.15.4网络（ZigBee）