Chapter 4 - 网络层：数据平面

IPV4与无类别域间路由选择（CIDR）

IPV4：

  • $32$ 位，$X.X.X.X/Y$ 代表前 $Y$ 位掩码的子网。
  • 路由器的每个端口作为子网的边界
  • 广播地址：255.255.255.255 & 子网掩码，用于全子网广播
  • 标识地址：子网内IP | 子网掩码，用户子网对外标识
  • 因此，$/Y$ 的子网可用 IP 数为 $2^Y - 2$

路由器与路由表

路由器
  • 在输入和输出端口处均会发生拥塞
  • 处理拥塞的调度算法：
    • 先进先出
    • 优先权排队
    • 加权公平排队（带权的 Round Robin 轮盘赌）
  • MTU：最大传送单元；超过 MTU 大小的数据报需要分片
    • 分片：切分大数据报的载荷，分成多个小数据报
    • 额外设置一个标志位代表是否是最后一片
  • 路由器每个 WAN 口都有一个独立的 IP 和一个独立的 MAC
路由表
  • 跳转算法采用最长前缀匹配算法
  • 路由器通过 OSPF、BGP 等协议填写路由表

路由表的例子：
假设我们有一个网络设备（如路由器），它连接到以下网络：

  • 本地网络 A: 192.168.1.0/24 (直连 eth0)
  • 本地网络 B: 10.0.0.0/8 (直连 eth1)
  • 远程网络 C: 172.16.0.0/16 (通过网关 192.168.1.254 转发)
  • 默认路由: 指向 8.8.8.8（用于访问互联网）
Destination Subnet Mask Gateway Interface Metric
192.168.1.0 255.255.255.0 0.0.0.0 eth0 0
10.0.0.0 255.0.0.0 0.0.0.0 eth1 0
172.16.0.0 255.255.0.0 192.168.1.254 eth0 10
0.0.0.0 0.0.0.0 8.8.8.8 eth0 20
动态主机配置协议（DHCP）
  • 用途：为新接入子网的用户分配一个子网 IP
  • DHCP 发现：新接入的用户以 0.0.0.0 身份向 255.255.255.255 广播 DHCP 发现报文
  • DHCP 提供：DHCP 服务器向 255.255.255.255 广播 DHCP 提供报文
  • DHCP 请求：用户选择一个 DHCP 服务器发送 DHCP 请求报文
  • DHCP 确认：防止两个用户争抢同一次 DHCP 提供报文
网络地址转换（NAT）
  • 目的：IPV4 地址不够用
  • NAT 路由器将子网内所有数据的 SrcIP 更改为自己的公网 IP，同时对子网内不同的 $(IP,Port)$ 对分配一个唯一的 SrcPORT
  • NAT 转换表：包含 WAN 端和 LAN 端，每条记录包含 WAN 端 IP 和端口以及 LAN 端 IP 和端口

Chapter 5-网络层：控制平面

链路状态路由选择算法（LS）
  • 集中式路由选择算法
  • 基于 Dijkstra 的贪心算法
  • 记录 $D(v),p(v)$ ：距离源点 $s$ 的距离、最短路径上最后一跳出发点（见下表）
Step N’（已固定的点集） D(v),p(v) D(w),p(w) D(x),p(x) …
0 u 2,u 4,u $\infty$ …
1 uv 2,u 3,v 5,v …
距离向量算法（DV）
  • 分布式路由选择算法
  • 基于 Bellman-Ford 算法
  • 距离向量 $d_u\in \mathrm{R}^n$，其中 $d_u(i)$ 表示 $u$ 与 $i$ 的最短距离
  • 多轮迭代：
    • 初始化：$d_u(i)=c(u,i)\textbf{ if }i\in N_u\textbf{ else }\infty$
    • 迭代：不断尝试使用 $c(u,j)+d_j(i)$ 更新 $d_u(i)$，更新时记录下一条方向
  • 毒性逆转：若 $z$ 前往 $x$ 的下一条是 $y$，则 $y$ 询问得到的 $d_z(x)=\infty$
开放最短路优先协议（OSPF）
  • 自治系统：AS (Autonomous System)
  • OSPF 用于 AS 内路由选择
  • OSPF 使用 LS 协议（Disjktra）
  • OSPF 采用两层架构（上层为 backbone，下层为 area），广播信息不越层。每个 area 有一个边界服务器，负责计算 area 内部路由；每个 backbone 有一个边界，负责计算 backbone 内部路由
边界网关协议（BGP）
  • BGP 用于 AS 间路由选择
  • BGP 路径由 iGBP (AS 内部) 和 eBGP (AS 间) 组成
  • 路由选择算法：（优先级由高到低）
    • 本地偏好（管理员设置）
    • AS-PATH 较短的优先
    • 热土豆原则（NEXT-HOP 较短的优先，即最快跳出当前 AS 的优先）
    • BGP 标识符（管理员设置）
因特网控制报文协议（ICMP）
  • 用于交互网络层信息
    • 错误检测：报告具体错误情况（例如：HTTP 错误码）
    • 状态检测（例如：ping）
    • traceroute

Chapter 6-链路层

链路层服务与术语

  • Framing（成帧）：帧 = 首部字段 + 数据字段
  • 链路接入：媒体访问控制（MAC）
  • 相邻节点的可靠交付
  • 错误检测与纠正
  • 网络接口卡（网卡）：NIC

错误检测与纠正

  • EDC：差错检测和纠正比特
  • 简单的方法：奇偶校验、二维奇偶校验、checksum
循环冗余检测（CRC）
  • $d$ 位的待发送数据 $D$、$r$ 位的校验位 $R$、$r+1$ 位的生成多项式 $G$
  • 以下所有乘除法中的加减运算都是异或运算
  • 满足：$(D\cdot 2^r \oplus R)=nG$，即 $G$ 异或整除 $D||R$
  • **公式：$R=(D\cdot 2^r)%G$**（注意取余计算时，除法中使用异或和）
  • 可以检测出不超过 $r$ 位的错误，不可以纠正

多路访问链路和协议

  • 信道划分协议（FDM/TDM/CDMA）
  • 随机接入协议（时隙ALOHA/ALOHA/CSMA/CSMA-CD）
  • 轮流协议（主机轮询/令牌传递）
时隙ALOHA
  • 特征
    • 所有帧都定长，有 $L$ 位；信道速率为 $R$
    • 每一个时隙都定长，为 $L/R$
    • 节点只在时隙开始时传输，并且所有节点的时隙同步
    • 节点在时隙结束前知晓是否发生了碰撞
  • 算法
    • 有帧要发送就在下一个时隙开始时立刻发送
    • 若碰撞则以 $p$ 的概率在后续每个时隙重传，直到成功
  • 效率
    • 假设每个节点都以概率 $p$ 一直发送
    • 效率为 $Np(1-p)^{N-1}\to 1/e$
ALOHA
  • 特征
    • 所有帧都定长，有 $L$ 位；信道速率为 $R$
    • 定义帧传输时间为 $L/R$，记为 $T$
    • 节点在传输结束时知晓是否发生了碰撞
  • 算法
    • 有帧要发送就立刻发送
    • 若碰撞则重复：等待一个帧传输时间，然后以概率 $p$ 发送
  • 效率
    • 假设每个节点都以概率 $p$ 一直发送
    • 效率为 $Np(1-p)^{2(N-1)}\to 1/2e$（需要前后宽度为 $2T$ 时间段中，都没有别人开始传输）
载波监听多路访问（CSMA/CD）
  • 思想
    • 说话之前先听：如果信道里有别人在说，我就不说
    • 碰撞检测：如果和别人一起讲，那就停止讲话
  • 算法
    • （1）NIC 收到一个需要发送的帧
    • （2）NIC 等待信道空闲，然后开始发送这个帧
    • （3）若检测到信道中同时有别人在发送数据：
      • 【消耗一个碰撞检测/放弃时间】停止说话
        • 有些协议会向信道中发送 jam signal（强烈的干扰信号），告知全体设备发生了碰撞
      • 开始 backoff 计时（该帧的第 $m$ 次冲突将选择一个 $k={0,1,2,3,\cdots,2^m-1}$，并计时 $k\cdot 512$ 比特时间）
      • backoff 计时结束后回到步骤（2）（此处不需要再等待）
    • IFG 时间（$96$ 比特时间）：帧间最小间隔时间。部分协议需要发送前等待信道空闲期满 $96$ 后，确保两帧间至少相距 $96$ 比特距离后再发送。（目的：确保设备能够处理连续的帧）
  • 效率
    • $t_{prop}$：信道中最远两点传输时间
    • $t_{trans}$：单帧传输时间
    • 效率为 $\eta=(1+5t_{prop}/t_{trans})^{-1}$

交换局域网（LAN）

  • MAC 地址：$48$ 位，每个设备都有唯一的 MAC 地址
  • 路由器的 LAN 口和交换机没有 IP 和 MAC；路由器的每个 WAN 口有独立的 IP 和 MAC
地址解析协议（ARP）
  • 每个路由器/主机内部存储一个 ARP 表
  • 本地 ARP 表查询失败时：
    • 向 255.255.255.255 发送 ARP 分组内广播，查询 DestIP 对应的 MAC
    • DestIP 向 SrcIP 发送 ARP 回复
    • 路上经过的所有人都自动学习到两人的 IP-MAC 对应关系
      • 特别注意！！：在传输的过程中，链路层数据报里的 SrcMAC 和 DestMAC 一直动态地指示局部信息
      • ARP 协议属于网络层协议，其中保存的 SrcMAC 是不变的；路上经过的节点根据 ARP 数据报里的 SrcMAC 更新 ARP 表，而不是根据链路层协议的 SrcMAC 更新

ARP表的例子：
假设一台主机有以下网络接口：

  • eth0: 连接到子网 192.168.1.0/24。
  • eth1: 连接到子网 10.0.0.0/8。
  • eth2: 连接到子网 172.16.0.0/16。
IP Address MAC Address Interface Status TTL
192.168.1.1 00:1A:2B:3C:4D:5E eth0 Reachable 120 sec
192.168.1.2 00:1B:3D:5E:6F:7A eth0 Reachable 110 sec
192.168.1.3 00:1C:4D:6E:7F:8B eth0 Stale 15 sec
192.168.1.254 00:FF:AA:BB:CC:DD eth0 Reachable 100 sec
10.0.0.1 11:22:33:44:55:66 eth1 Reachable 200 sec
10.0.0.2 12:34:56:78:9A:BC eth1 Stale 50 sec
172.16.0.1 AA:BB:CC:DD:EE:FF eth2 Reachable 180 sec
172.16.0.100 FF:EE:DD:CC:BB:AA eth2 Incomplete -
向局域网外部发送信息
  • 路由器检测 ARP 请求通往局域网外部时，返回一个自身的接口的 MAC 作为地址
  • 当路由器接受到通往外部的数据报时，根据其路由表转发至下一跳

交换机

  • 交换机对其他设备完全透明
  • 交换机可以全双工工作，因此不存在碰撞问题
交换机表
  • 交换机维护一个（被动）自学习的交换机表来工作
  • 一个交换机表表项包括：MAC 地址、接口号、表项产生时间
  • 自学习过程：
    • 当交换机从一个端口收到一个 SrcMAC 的链路层数据报时，将其作为一个表项记录
  • 交换机不会主动自学习：遇到不认识的 DestMAC 时，其向所有非来源端口发送一份相同的数据报副本（泛洪，flood）
与路由器比较
交换机 路由器
链路层设备 网络层设备
完全透明，只起转发作用 每个 WAN 口有独立的 IP 和 MAC，起转发和路由作用
依据 MAC 地址，使用链路层算法（泛洪、交换机表等） 依据 IP 地址，使用路由算法（ARP、路由表等）
泛洪：只是为了全局分发数据，不期望得到回复，不限定范围 广播：为了向某不知道地址的人发送数据，期望得到回复，有限定范围

Chapter 7-无线网络

无线网络特征
  • 信号强度衰减
  • 来自其他信号源的干扰
  • 多径传播：电磁波经过反射后走不同路线传播，可能导致接收信号模糊化
  • SNR：信噪比；BER：比特错误率
  • Hidden Terminal Problem： A 和 C 的信道在 B 处发生干扰，但 A 和 C 互相感知不到；使用 RTS/CTS 解决
码分多址协议（CDMA）

  • 思想：采用一个频率较高的编码函数将数据特征化
  • 抗干扰、部分情况下线性可分
802.11 无线 LAN（WiFi）
  • 基本服务集（BSS）：包含多个无线站点，和一个接入点（AP）作为中央基站
  • WiFi 丛林：能收到多个 AP 的强信号
  • 关联（associate）：设备关联到一个 AP
  • 信标帧（signal frame）：AP 会周期性发送信标帧，包含其 SSID 和 MAC，用于设备识别和连接
  • 被动扫描：
    • AP 广播信标帧
    • 设备 H 接受到（一个或多个）信标帧，选择一个 AP 发送关联请求帧
    • 被选择的 AP 向 H 发送关联响应帧
  • 主动扫描：
    • 设备 H 广播探测请求帧
    • 接受到的 AP 均发送探测响应帧
    • 设备 H 接受到（一个或多个）探测响应帧，选择一个 AP 发送关联请求帧
    • 被选择的 AP 向 H 发送关联响应帧
  • 采用 CSMA/CA 碰撞检测协议
CSMA/CA
  • RTS: Request to Send
  • CTS: Clear to Send

  • RTS 和 CTS 可解决隐藏终端问题：A 和 C 即使无法互相检测到信道冲突，但由于其二者均可与 B 通信，因此必须要预约信道后才能发送；预约失败时将推迟发送。