4. 数据链路层

性质

基本职能
- 成帧 Framing:
  - encapsulate network layer data 数据链路层会将来自网络层(第三层)的数据进行分组, 添加头部和尾部信息, 以形成一个个帧(Frame)
- 链路访问 Link Access:
  - Medium access control (MAC) protocol defines when to transmit frames 在多点接入的介质 (例如共享式以太网, 无线网络等) 中, 多个设备可能需要同时传输数据
  - 需要负责决定什么时候由哪一个设备向链路发送数据
- 可靠交付 Reliable Delivery:
  - Primarily for mediums with high error rates (wireless)
  - 某些网络环境中可能会受到干扰而导致帧丢失或损坏
  - 数据链路层可以提供重传, 确认等机制, 确保帧能可靠地到达接收方
    - 虽然TCP/IP协议栈中大多由传输层(TCP)来保证可靠性, 但一些链路层协议(如PPP)也会提供基本的可靠性功能
- 差错检测与纠正 Error detection and correction
  - 帧的尾部通常会包含检错码(例如CRC校验), 用于检测帧在传输过程中是否出错

link layer protocols 是在硬件层面被实现的
frame 格式可以随着 link layer 协议而改变

链路访问 link access

共享广播信道(如传统以太网或无线网络)中, 多个节点同时竞争使用同一个物理介质, 如果没有合理的访问控制, 就会导致数据碰撞(collision), 使得传输数据无法被正确接收
点到点/广播的媒介
- Point-to-Point:两个节点之间建立一条专用通信链路, 只有这两个节点可以在这条链路上进行通信
  - 可用于远距离 fiber link
  - 可用于以太网交换机与主机之间的链路 (b/n Ethernet switch)
- Broadcast: 通过 wire 或者其他媒介交互
  - 传统以太网 pre2000 使用
  - 802.11 wireless LAN
多重访问算法(Multiple Access Algorithm)
- 让所有节点都能有序地使用信道, 需要一个分布式算法来确定什么时候由哪个节点发送数据
- 三大类算法
  - Channel Partitioning 将共享信道按照时间, 频率或编码进行切分, 每个节点只在被分配到的那部分信道上发送数据
  - Taking Turns 节点轮流获得发送权, 在一个节点发送完成后, 再轮到下一个节点发送
  - Random Access 节点在发送之前并不进行严格的时隙或频率分配, 而是"随机地"在需要发送时直接尝试访问介质, 如果检测到碰撞则重传
- Random Access MAC Protocols
  - 需要发送的时候发送数据包到完整的 channel 中, w/o coordination
  - 如果出现多个 transmitting nodes 会导致 collision
  - Random access MAC protocol 明确了如何 detect and recover from collisions
  - Examples:
    - ALOHA, Slotted ALOHA
    - CSMA, CSMA/CD, CSMA/CA (wireless)

以太网 Ethernet

为了广播技术被发明出来
- Hosts share channel 共享信道 同一条总线或集线器(Hub)
- Each packet received by all attached hosts 当某台主机发送数据时, 介质上所有设备都能收到该帧(即广播), 再由每台设备自行判断是否接收(检查帧中目的地址)
- CSMA/CD for media access control 带碰撞检测的载波监听多点访问是早期以太网介质访问控制的核心
优点
- Plug-n-Play: 不需要进行任何 configuration
- Simple
- Cheap
现代以太网是交换式
- 现代以太网普遍使用交换机(Switch)而非集线器,交换机将每个端口都变成一个独立的冲突域, 主机与交换机之间是点对点链接;
- 无碰撞 => 不再需要 CSMA/CD 因为每条链路只连着交换机和单一主机, 介质不再共享, 因此不会发生碰撞事件, 也就无需使用 CSMA/CD
  - 使用 “self learning” 和 “spanning tree” algorithm 来计算 routing
CSMA (Carrier Sense Multiple Access)
- listen before transmit
  - sense idle: transmit entire frame
  - sense busy: defer transmission
- does not eliminate all collisions
  - 由于信号传播延迟(Propagation Delay), 会仍然会存在 detect
    和实际情况并不一致的情况
- CSMA/CD (Collison Detection)
  - Collitions detected within short time
    - easy in wired LANs: compare transmitted received signals
    - difficult in wireless LANs
  - Colliding transmission aborted, reducing wastage 由于节点可以在发送过程中快速检测到碰撞并停止发送, 所以不会继续浪费带宽发送整帧数据
  - 需要限制最小 frame 尺寸和最大传输距离
    - 最小 frame 尺寸限制: 对于小包数据, 发送端误认为帧已经成功发送, 实际上帧中的部分数据可能已经被干扰或损坏; 接收端在收到数据后, 通常会进行错误校验(例如 CRC 校验), 如果校验失败, 就会丢弃这帧数据
    - 网络长度限制: 延迟取决于 link 的物理长度, 也就是从一个 end 到另一个的
      propagation time (这里称为 d), 那么当一端发出信号的时候(时间节点
      t), 另一段需要在大概 t+d 的时候才会收到数据包, [t,t+d]
      时间范围内被认为是空闲的
      - 如果另一段在这个区间内发送了信息, 则会后续监测到 collision
        并且发送一个 jamming signal, 但是 A 直到 t + 2d 的时间节点才会看到
      - 在 2d 的时间区间内, A 一直在发送数据信息, 并且检查所有可能的
        collision
      - imposes restrictions: 10 Mbps Ethernet
        
        max wire length: 2500 meters
        
        min frame length: 512b
- Random Access 三个核心要点
  - Carrier Sense 载波监听: wait for link to be idle
    - listen before speaking andd don’t interrupt 在发送数据之前, 节点会先"监听"物理介质(线缆或无线信道), 以判断是否有其他节点正在发送数据
    - checking if someone else is already sending and waiting until other node
      is done
  - Collision Detection 碰撞检测: listen while transmitting
    - 在发送数据的同时, 节点会监测介质上实际的信号是否与自己发送的信号相符; 若出现异常(如电平, 波形不匹配, garbled 乱码), 说明可能有其他节点也在发送, 发生了碰撞
  - Randomness 随机退避: binary exponential back-off
  - 检测到碰撞后, 每个节点会等待一个随机长度的时间(退避时间)再尝试重新发送
  - m-th collision 之后随机选择 K 于 $0 - 2^m - 1$ , 并且等待 K * 512 bit times
    before trying again
  - 如果准备发送的时候仍然监测到有数据正在发送, 等到结束再说
- Efficiency 定义
  - 长时间的运转下 frames 被传输而没有发生 collision 的时间比例
  - $d_{prop}$ 表示 max propagation time between two adapters
  - $d_{trans}$ 表示传输最大尺寸 frame 的时间

交换机以太网 Switched Ethernet

现代以太网就是交换机组成的
- switch 之间, host 与 switch 之间是 point-to-point
- no sharing -> no CSMA/CD
交换法的优点
- enables concurrent communication
  - 可以局部点到点直接连接而不需要让所有无关的 host 都知道这个信息
  - 不大容易 collision 因此不需要 csma/cd
  - 对于 link length 没有限制
以太网帧结构 Ethernet Frame
- Preamble: 7B 用来同步时钟, 1B 用来表示 frame 的开头
- Addresses: 6B
- EtherType: 2B, protocol (包含 IP, length 等)
- Data Payload: 最大 1500B 最小 46B
- CRC: 4B 来检查 error (收发出错)
- 以太网帧的最大实现问题: dl 层如何知道什么时候 frame end 了
  - TODO:
地址 Addressing (MAC)
- 一个 48 bit 的 flat-namespace 并且和网络适配器 (network adapter)
  相关的数字地址
- unique, hard-coded in the adapter when built
- MAC 地址的分配机制(分层式结构)
  - 前 24 位(高 3 个字节): 由 IEEE(电气与电子工程师协会)分配给设备厂商, 也称为 OUI(Organizationally Unique Identifier);
  - 后 24 位(低 3 个字节): 由厂商自行分配给其生产的不同设备, 以确保在同一厂商内部不会出现重复;
- Portable, 可以随着用户移动而保持不变
寻路 Routing
- 帧在链路层的处理流程
  - 当设备 A 发送一个帧时, 这个帧会通过交换机或集线器(逻辑上都是广播域)传到所有其他设备上;
  - 但是, 并不是所有设备都会将这个帧交给自己的上层(网络层);各设备的链路层会先检查帧头中的目的 MAC 地址(Destination MAC Address, 简称 DMAC);
  - 只有当以下条件满足时, 设备才会把帧交给自己的网络层:
    1. 目的 MAC 地址与本机网卡的 MAC 地址相同;
    2. 目的 MAC 地址为广播地址 ff:ff:ff:ff:ff:ff(即表示所有设备都要接收该帧);
- 为什么 dl 层不采用 ls/dv 的算法?
  - 可扩展性(Scalability)问题
    - MAC 地址是平面(flat)的, 而 IP 地址是层次化(hierarchical)的;
    - 不方便像 ip 那样 aggregate
- 历史与兼容性(Legacy & Backward Compatibility)
  - 以太网早期的设计就是 “广播介质” + “自学习(learning)” 的方式, 不需要复杂的路由计算;早期的集线器, 交换机等设备都基于这种广播与自学习机制;
  - **生成树协议(STP)**是一个二层协议, 它通过禁用冗余链路来避免广播风暴 (broadcast storm), 使得以太网在物理上可以有冗余, 但逻辑上呈现一个无环的树状拓扑;
  - 这种机制相对简单, 能与老设备保持向后兼容(Backward Compatibility);
  - Ethernet 的设计理念也想保持**“插上就能用”(Plug-and-Play)**的特性, 而不像 IP 网络需要配置路由或依赖 DHCP/手动设置 IP 地址;
- 生成树方法解决 Flooding Loop
  - 分成两步: 1. Pick a root; 2. Compute the Shortest paths to the root
  - Pick Root: 选取 mac 地址最低的
  - Shortest Path:
    - 最短路径一定没有 loop
    - break ties in some way: 选取临近交换机中 id 最低的
  - 生成树构建信息格式 Message (Y, d, X)
    - From node X
    - Proposing Y as the root
    - Advertising a distance to Y
  - 实现步骤:
    1. 最初每个 switch 将自己作为 root 广播信息 (X, 0, X)
    2. 将最低的 id 交换机设置为 root, 并且转发 (Y, d, Z) 信息来更新距离
    3. 每个交换机计算其到达 root 的距离
    - 每次转发的时候都将最短距离 + 1
    1. 如果发生最短路径变化或者 root 变化, 发送 (Y, d+1, X) 到 neighbor
  - 稳定生成树算法 Robust Spanning Tree Algorithm
    - Algo react to failures (root node failure, other node/link failure)
    - Root send periodic root announcement msg
    - Detect failures through timeout
Forwarding 转发
- Flooding: 在最初没有建立 spanning tree 的时候是向每一个 port 都发出 msg
  - 建立生成树的时候, 在一个端口收到一个包, 向其他所有端口都转发这个包
  - 建立生成树之后, 忽略所有不符合生成树branch 对应的 link 的 port
  - Wasteful: 发送之后所有的 node 都会知道如何到达这个节点
    - 对比某个节点的 response 只能被一些交换机知道其位置
  - 交换机学习机制:
    - 将 src 的 mac 地址和接受该包的 port 形成一个映射
    - 将映射关系存入 switch 内部的表中
    - 使用 ttl (time-to-live) 来定义遗忘机制
Discovery and Bootstrapping:
- host 初始化情况下只知道自身的 mac 地址
  - 能交流之前需要先收集大量信息: 要用到 ARP 和 DHCP 协议服务
  - 这些都是局限于一个 LAN (Local Area Network) 的情况
  - 依赖于 broadcast capability

DHCP 协议 (Dynamic Host Configuration Protocol 动态地址分配协议)

自身是 应用层 协议, 但是功能会直接作用于网络层自动为局域网内的设备分配 IP 地址及其他网络配置信息, 从而简化网络管理工作, 而不是单纯"普及"本地 IP 地址
通常由路由器, 专用服务器或网络中中央服务器提供, 而不一定存在于本地交换机上;在家庭网络中, 路由器通常充当 DHCP 服务器
功能
- 发现自身 ip 地址, netmask (子网掩码)
- local DNS name server IP
- first-hop default router’s IP
运行机制
- DHCP 服务器保存一个可用地址池, 比如可以发放哪些 IP 地址
- 使用 udp (port 67) 进行交流
- 四步握手协议 (DORA)
  1. DHCP Discover: 广播(Broadcast), 目标地址是 FF:FF:FF:FF:FF:FF, 意思是对所有人说
  2. DHCP Offer: 多个 DHCP 服务器可能都回应你, 给出不同的 IP 地址和配置信息; 每个 Offer 都是临时的 (lease time)
  3. DHCP Request: 客户端从众多 Offer 中选择一个, 广播发出一个 DHCP Request, 请求指定那个 IP; 其他 dhcp 服务器能知道其没有被选中
  4. DHCP ACK: DHCP 服务器最终确认并将配置绑定到客户端: 你获得了 IP, 网关, DNS 等信息;租期(lease time)开始计时
- 如果 DHCP 服务器不在同一个广播域中(例如在另一个网络), 广播是到不了的;这时, 网络管理员可以设置一个 DHCP Relay Agent, 作为"中继者"转发 Discover 请求
- DHCP 软状态 Soft State
  - Hard State: 系统中的状态是明确设定, 持久存储, 不会自动失效的;状态一旦建立, 就必须通过显式的动作来更改或删除
  - IP 地址是租来的(Lease), 有失效时间 (lease period);
  - server sets a timer for each allocation, resets timer when a refresh arrives and ACKs, or reclaims allocated address when timer expires
  - 客户端在租期快到时 (expires) 需要续租(Renew);
  - 如果网络崩溃或服务器宕机, 系统不会强制记住你的 IP, 等你重新上线时再协商一次;
- Robustness under Failure
  - Host Failure: refresh from host 无法刷新, 因此 server 在 O(lease period) 之后会 reclaim 对应 ip
  - Server Failure: ack from server 没了, host 在 O(lease period) 时间段之后
  - Network Failure: refresh 和 ack 无法发送, 导致 host 丢失 ip 地址, server 重新收获地址

ARP 协议 (Address Resolution Protocol)

注意 link layer 用的是 mac 地址, 因此需要从 IP 地址转换成 mac 地址
每个 host 都会有一个 ARP 协议表 (IP addr <-> MAC addr 一一映射)
- 发包之前需要先根据 ip 查找 mac
- encapsulate the ip pack in an Ethernet level frame (发出去的包也是 mac 打头)
arp 表查不到对应 ip:
- sender broadcast 对应 ip 地址
- 对应的 receiver reply mac address
- sender caches into arp table
非局域网的地址查找
- 会将前往对应 IP 的第一跳 (first-hop) router (注意 switch 是在局域网内部的通信设备, 而 router 往往是处于 border BGP 的路由器) 记录在 ip-mac 表中
- 判断不是同一局域网: 看 netmask 部分是否匹配 (netmask & ip1) == (netmask & ip2), 这些信息来自于 dhcp 服务器

查找机制对比 (`ARP+DHCP` v.s. `DNS`)

property	ARP + DHCP	DNS
Scale	Flooding, not scalable	No flooding, scalable
Centralize	No center, robust	need a root, which is vulnerable
configuration	plug-n-play	Needs configuration to bootstrap

NAT (Network Address Translation)

当内网主机(私有 IP)访问外网时, 由 NAT 设备将内网 IP 和端口映射成 NAT 设备对外暴露的公共 IP 和全新的端口; 返回的流量再通过 NAT 设备转换回原来的内网地址和端口
- Outgoing Replace: 将每个出站数据包的源 IP 和源端口替换成 NAT 的 IP 和新的端口号
- Remember: 在 NAT 转换表中记录每个(内网源 IP, 源端口)与(NAT 公网 IP, 新端口)的映射关系
- Incoming Replace: 对每个入站数据包, 将目标字段中的(NAT 公网 IP, 新端口)替换回在 NAT 表中对应的(内网源 IP, 源端口)
以太网的缺点
- 很多 bandwidth 都是 unused
  - 转发只会经过 spanning tree 的 branch (link)
- 建立 spanning tree 会导致延迟
- 对于 host 的转移会非常延迟响应
- root 的地址会决定 forwarding 效率

设备接入网络的流程

设备广播 dhcp 请求并且监听 dhcp 响应来获取本机 ip 地址, dns 的 ip 地址以及下一跳的路由器 ip 地址
广播 arp 信息来获取本地 dns 服务器 mac 地址 (第一步获取了 ip)
发送 dns 请求来获得 www.google.com 的 ip 地址
广播 arp 请求来获取下一跳 (next-hop) router 的 mac 地址 (第一步获取了 ip)
建立 tcp 连接
建立 tls 连接
发送 http GET 请求来获取页面

无线网络 Wireless Network

无线网络元素

无线主机(Wireless Hosts)
智能手机, 笔记本电脑等终端设备, 可运行应用程序, 可能为固定或移动设备 (wireless != mobility);
网络基础设施(Network Infrastructure)
- 基站(Base Station / Access Point, AP): 连接无线主机与有线网络的中继设备(如WiFi路由器);
- 无线链路(Wireless Link): 连接移动设备与基站, 支持多种速率和传输距离;
无线与移动的区别
- 无线(Wireless): 基于无线链路的通信 (不会有有线链路的冲突问题);
- 移动(Mobility): 设备切换连接点(如基站切换);

无线网络分类 (taxonomy)

模式	单跳(Single Hop)	多跳(Multiple Hops)
基础设施模式 (Infrastructure)	主机直接连接基站(WiFi, 蜂窝网络)	通过多个无线节点中继连接(Mesh网络)
无基础设施模式 (Ad-hoc)	无基站, 短距离直连(蓝牙)	自组织网络(MANET, VANET)

Relay: 负责将无线 host 的数据包和接入有线网的节点之间互相发送包
Access Point (AP): 上述接入有线网的节点

无线链路特性与挑战

无线链路特性

Data Rate (Mbps) 种类多样, 4G 网络的 dr 率高于 3G 网络
易受影响
- 信号衰减(Path Loss)
  信号强度随距离和障碍物衰减, 公式: $FSPL = \left( \frac{4\pi df}{c} \right)^2$ ( $d$ : 距离, $f$ : 频率, $c$ : 光速)
- 多径效应(Multipath Propagation)
  - 信号反射导致接收端多路径干扰(Self-Interference);
  - 接收机会在微小的时间差内收到来自同一个发射源的多个"拷贝"版本的信号(相位有冲突)
- 干扰(Interference)
  共享频段(如2.4GHz)中其他设备或环境噪声的干扰;
媒介: 无线信号会以电磁波的形式向四周辐射, 也就是"广播"出去;任何在信号覆盖范围内的设备都可能接收或探测到这一信号
发送期间无法接受 (half-duplex 半双工限制) 无线设备在发送时, 其功率大大超过接收灵敏度, 使得接收机在本设备发射信号的同时"被淹没"而无法正常接收
Hidden-Terminal-Problem: 某些节点(如 A 和 C)虽然同时与同一个接收端(如 B)通信, 但它们彼此之间由于距离, 障碍或信号强度等原因, 无法"听到"彼此的存在, 导致发生冲突和干扰却无法感知
- 例子 A <-> B <-> C
- 这里 AB 可以互相通信, BC 可以互相通信, 但是 AC 之间道理上无法感知对方的存在也无法互相通信
- 如果 A, C 同时给 B 发送信息, 那么 B 的接收端可能会出现两条信息波互相干涉的情况

信噪比与误码率

SNR(Signal-to-Noise Ratio): 信噪比越高, 信号质量越好;
BER(Bit Error Rate): 误码率与SNR负相关, 不同调制方式(如QAM, BPSK)BER不同;
- 发送端能量越大, 信噪比越大, 误码率越小
- 纠错编码与重传: 链路层重传(如TCP Westwood);
  - 用更多的 error code 来检测和区分错误

802.11无线局域网(WiFi)

架构与工作模式

Basic Service Set (BSS 或称 cell): 基本服务集合, 包括一个 Base Station (AP) 和多个 wireless hosts
基础设施模式(Infrastructure Mode)
- 基本服务集(Basic Service Set, BSS): 包含AP和关联的无线主机;
灯塔帧 Beacon Frame
- 各个 AP 会周期性地在自己的信道上发送 Beacon 帧(类似"灯塔"信号), 其中包含网络名称(SSID), 支持的速率, 安全模式等信息
- 只用于 passive

被动扫描(Passive Scanning)	主动扫描(Active Scanning)
host 监听AP的 Beacon Frames, 不需要主动发送 request	主机广播 Probe Request, AP响应 Probe Response
选中 ap 并且对其发出 association request	选中 ap 并且对其发出 association request
AP 收到关联请求后, 会返回一个 Association Response, 内容包括是否允许该终端加入, 所支持的速率等	选定 AP 接收并确认关联, 向终端发送 Association Response

802.11帧结构

地址字段:
- Address 1: 接收端MAC地址(目标AP或主机);
- Address 2: 发送端MAC地址(源主机或AP);
- Address 3: AP连接的路由器接口MAC地址(用于跨子网通信, 位于 bss 外面);

多址接入协议: CSMA/CA

冲突避免机制(Collision Avoidance)
1. 载波侦听(Carrier Sense): 检测信道是否空闲;
- 如果 busy, 选择一个随机时间间隔
- 等待上述时间之后再次发送数据包
1. 指数时长退避(binary exponential Backoff): 信道忙时等待 $2^n$ 的时间
- 收到 receiver 的 ack 表示没有 collision
发包组合
- 首先由 sender 发送一个 RTS(request to send) 指令并且等待接收端发送 CTS (clear to send) 准入指令
- 双方完成一次 RTS+CTS 之后开始发送 data, 发送完成之后接收方返回 ack
- sender 收不到 cts 就会认为发生了 collision
- 特点:
  - explicitly reserving channel, enables avoidance
  - required to avoid hidden terminals
  - 例如上面的 ABC 模型, 如果 AC 同时给 B 发送, 那么先到达的一方产生的 cts 会被广播并且让被冲突的一方也收到, 从而误认为发包成功
分频避免冲突
- 频率谱可以被分为多个 channel, 不同频率选择不同 channel 从而有效避免 collision

移动性管理

同一子网内切换:
- IP 地址保持不变, 交换机通过 self-learning 更新端口映射;
- AP 切换由主机的关联请求 (Association Request) 触发;

其他无线技术 802.15(蓝牙)

个人局域网(PAN): 覆盖范围<10米, 主从架构(Master/Slave);
应用场景: 鼠标, 键盘, 耳机等短距离设备连接;

性质

链路访问 link access

以太网 Ethernet

交换机以太网 Switched Ethernet

DHCP 协议 (Dynamic Host Configuration Protocol 动态地址分配协议)

ARP 协议 (Address Resolution Protocol)

查找机制对比 (ARP+DHCP v.s. DNS)

NAT (Network Address Translation)

设备接入网络的流程

无线网络 Wireless Network

无线网络元素

无线网络分类 (taxonomy)

无线链路特性与挑战

无线链路特性

信噪比与误码率

802.11无线局域网(WiFi)

架构与工作模式

802.11帧结构

多址接入协议: CSMA/CA

移动性管理

其他无线技术 802.15(蓝牙)

查找机制对比 (`ARP+DHCP` v.s. `DNS`)