Stanford CS144：计算机网络导论

Internet 和 IP 简介

应用的一天生活

网络应用：通过网络读写数据

模型：双向、可靠的字节数据流连接 connection

• 一边读，一边写
• 可靠
• 双向操作

万维网（HTTP）就是一个服务器-客户端模型：

比特流 BitTorrent 是多客户端之间的连接：

Skype 有两个客户端，方法较多，分为三种情况：

Internet 四层模型

链路层 link：

• 一次通过一个链路传递数据
• 以太网 Ethernet，WIFI 等就是属于这一层

网络层 network：其数据包称为数据报 datagram

注意到从网络层的角度看，其是在与另一个网络层通信，却不关心这是通过链路层实现的

网络层

• 尽可能传递数据报
• 但有可能丢失
• 只有 Internet Protocol（IP）

传输层 Transport：

• 保证端到端的正确、顺序的数据传递
• 控制阻塞
• 包括 TCP，UDP 等

应用层 Application：

• 两个应用间双向可靠的字节流
• HTTP 等

可以注意到，只有网络层中只有 IP 一种方法，故 IP 被称为 thin waist

国际标准化组织 International Standards Organization(ISO) 制定了开放式通信系统互联参考模型 Open System Interconnection（OSI），即 ISO/OSI，这个模型有 7 层，但 Internet 在实现时合并了其中的几层，故只有 4 层（或 5 层）

IP 服务模型

将传输段作为数据包中的数据，并附上头，然后传递给链路层：

特点：

• 数据报：独立的路由包，hop-by-hop 路由
• 不可靠：可能丢包
• 努力：只有必要时才会丢包
• 无连接：到达可能是无序的

简单：

• 构建和维护的成本低
• 端到端原则：尽可能在终端实现特性
• 允许上层服务
• 对下层的假设少

细节：

• 使用**生存时间 Time To Live（TTL）**字段防止包永远循环
• 如果包太大，则会分裂包
• 使用检验和减少传递到错误地点的可能性
• IPv4 & IPv6
• 运行新功能添加到包头中

包的一天

传输控制协议 Transmission Control Protocol (TCP) 字节流：

三次握手 3-way handshake：

• syn：客户端对服务器同步信息
• syn/ack：同步消息的服务器响应同时确认客户端的同步
• ack：客户端确认服务做出响应

建立连接需要 IP 地址和 TCP 端口

在流的内部通过 hop 在一个一个路由之间传递：

在每个 hop 的内部，路由器通过转发表 forwarding table 选择要使用哪个链路

包交换原则

包 packet：自我包含的数据单元，载着到达目的地的必要信息

包交换 packet switching：独立地为每个抵达的包选择其传出链路，如果链路空闲，则发送；否则保持，并等待

结果：

• 包转发更简单
• 有效共享链接

流 flow：属于相同端到端通信的数据报集合

• 包交换不需要每个流的状态，包自我包含
• 无需添加/移除/储存每个流的状态

数据交通是突发的 burst

• 单一资源在多个用户之间共享的想法叫统计复用 statistical multiplexing

分层原则

• 层 layer 是功能单元
• 每层向上层提供定义好的服务
• 层顺序通过下层通信

理由：

• 模块化
• 定义明确的服务
• 复用
• 分离关注
• 连续提高
• 点对点通信

封装

两种画法：头在左边，头在右边

简单来说就是层层套娃

字节序

小端：x86，arm

大端：Internet

所以在处理时需要小心，使用 ntohs() 等转换

IPv4 地址

32 bit：a.b.c.d

子网掩码 netmask：使用这个 mask，如果匹配，则在相同网络内

最初的层级：网络 network + 主机 host

最初有 3 类地址：

但这种分法太粗糙了，故有了无类别域间路由 Classless Inter-Domain Routing(CIDR)

• 地址块是一对：地址，计数 count
• count 是 2 的幂次，表示子网掩码长度
• 171.64.0.0/16 表示 171.64.0.0 - 171.64.255.255 地址范围

互联网号码分配局 Internet Assigned Numbers Authority（IANA） 分发 /8s 给地区性互联网注册管理机构 Regional Internet Registries(RIR)，则已经用完了

最长前缀匹配

转发表是 CIDR 项集合，使用最长前缀匹配的项转发

地址解析协议

地址解析协议 Address Resolution Protocol(ARP)：网络层使用这个来发现与其直接连接的网络地址关联的链接地址

链接地址描述特定的网卡，辨识设备

ARP

• 生成层级 2 和 3 的地址值
• 简单的请求-回复协议
  • 请求发送到链接层网络地址
  • 回复发送请求地址
• 包头包括冗余数据
• 状态不会共享

运输层

TCP 服务模型

• 接受来自应用层字节流，封装到 TCP 段的数据中，发送给网络层
• TCP 对等通信
• 通过三次握手建立连接

连接关闭：四次挥手

• A 发送 Fin 消息表示自己不发送数据了
• B 确认 A 不再有发送的数据，但仍可以向 A 发送数据，即关闭了 A 到 B 的数据流
• B 发送 Fin 给 A
• A 确认

特点：

• 字节流
• 可靠的传递：
  • 确认表示正确接受
  • 校验和检测污染的数据
  • 序列号检测丢失的数据
  • 流量控制防止接受者超速运行
• 顺序
• 阻塞控制

TCP 端口和 IP 头共同形成一个唯一的 TCP ID

• 主机 A 为每个连接增加原端口
• TCP 选择随机的 ISN（起始序列号）来防止和之前的连接有相同的 ID

TCP 端口解复用

UDP 服务模型

注意校验和中包括了 IP 地址，这违反了层的分离，为了检测目的地是否正确

UDP 也是端口解复用的，故有人称其为用户多路复用协议 User Demultiplexing Protocol

特点：

• 无连接：包无序
• 自我包括
• 不可靠传递：
  • 无确认
  • 无检测丢包或乱包的机制
  • 无流控制

ICMP 服务模型

网络层工作：

• IP
• 路由表
• ICMP

因特网控制消息协议 Internet Control Message Protocol(ICMP)：报告错误信息，帮助检测问题

ICMP 在网络层之上工作：

特点：

• 报告消息：自我包含 消息报告错误
• 不可靠

一些 ICMP 消息类型：

类型	代码	描述
0	0	echo 回复
3	0	目的网络不可达
3	1	目的主机不可达
3	3	目的端口不可达
8	0	echo 回应
11	0	TTL 过期

对于 traceroute，分别发送 TTL 为 0，1 … 的包，路由器会返回 TTL 过期的消息，即可直到每一站的路由地址等信息

端到端原则

网络可以做很多事情来提供帮助，有助于提高效率等，但是想要保证正确，必须在端到端实现

强端到端 strong end-to-end：网络的工作在于尽可能地高效和灵活地传递数据报，其余的事情应该在边缘实现，否则整个系统会越来越复杂

错误检测

检验和(IP,TCP,UDP)：

• 对包中所有 16 bit 字求和
• 简单，快速
• 只能保证检测一个位的错误

循环冗余校验码 Cyclic Redundancy Check (CRC)：链路层

• 把 n bit 的数据拆卸成 c bit，c << n

可以检测：

• 奇数个数的 bit 错误
• 2 bit 的错误
• <= c bit 的一个突发错误

消息认证码 Message Authentication Code(MAC)：

• 当字节翻转时，有很大概率会有变化，而不能保证检测出任何一个错误
• 所以通常用于保护信息被恶意篡改，而不是检测错误

有限状态机

流控制

不能比接受者能够处理的速度还要快地发送包

停止并等待 stop and wait：

• 任何时候最多一个包在飞行中
• 发送者发送一个包
• 接收者收到包时发送确认包
• 收到确认包时，发送者发送新的包
• 超时时，发送者重新发送当前包

注意到如果接收者发送了确认，但是速度较慢，发送方认为超时了，又重新发送，然后又收到了之前的确认，就会出问题，故需要序列号标识确认的是哪个包

滑动窗口 sliding window：

• 一次发送多个包

发送者：

• 每个段都有一个序列化
• 发送窗口大小 SWS
• 最后确认收到 LAR
• 最后发送的段 LSS
• 维护不变量 LSS - LAR <= SWS
• 当收到新的确认时，前进 LAR
• 缓冲最多 SWS 段

接受者：

• 接受窗口大小 RWS
• 最后确认的段 LAS
• 最后收到的段 LSR
• 维护不变量 LAS - LSR <= RWS
• 如果接受的包 < LAS，则发送确认
  • 发送的是累积确认

RWS, SWS, 序列空间：

• 需要 RWS + SWS 个序列号

TCP 流控制：

• 接收者使用 window 域广告 RWS
• 发送者只发送最多 LAR + window 的数据

重传策略

返回 N：一个丢失导致整个窗口重传

选择性重复：一个丢失只重传那个包

连接建立与拆除

注意 syn 同步的就是序列号，尽管其没有数据，却会导致序列号 +1

如果双方同时发送，则是四次握手

同样的，在拆除连接时，fin 也会使序列号 +1

为了防止忘记了最后的信息，故会等待一定时间再关闭

包交换

历史

通信中的五个概念：

• 编码
• 流控制
• 同步
• 纠错和重传
• 加密

发明的四个阶段：

• 预先定义好的信息
• 传输任意信息
• 常用字词使用数字编码压缩
• 控制信号

端到端延迟和传播延迟

传播延迟：一个 bit 以传播速度 c 沿链接传播的时间

$$t_l = \frac lc$$

封包组装延迟：一个包的第一个 bit 到最后一个 bit 传输所用时间

$$t_p = \frac pr$$

但是在路由器中还有排队延迟，故端到端延迟

$$t = \sum_i (\frac{p}{r_i} + \frac{l_i}{c} + Q_i(t))$$

注意到排队延迟是唯一具有变量的延迟，却导致了端到端延迟的变化，一般经过的路由器越多，方差越大

播放缓冲

实时应用程序使用播放缓冲来吸收排队延迟的变化

简单确定性排队模型

画成折线图，竖直代表队列长度 $Q(t)$，水平代表延迟 $d(t)$

更小的包使用了流水线从而减少延迟：

$$t = \sum_i (\frac{p}{r_i} + \frac{l_i}{c}) + \frac{M}{p-1} * \frac{p}{r_{min}}$$

统计复用意味着出口链路不需要运行在 NR 的速率，因为 buffer 会吸收超出 R 的速率，但是因为 buffer 是有限的，所以一定会有丢失

统计复用增益：

有两种表示方法：

$$\text{gain} = 2C/R$$

其中 $R$ 可以是顶峰，也可以是恰好填充满时的速率

排队模型属性

详见排队论，这里只需记住几个性质

1. 突发增加了延迟

2. 一般来说，确定性最小化延迟

3. 里特尔结果：如果没有丢失或抛弃，$L = λ d$，其中 $\lambda$ 为抵达速度，$L$ 为平均队列长度，$d$ 为平均延迟

泊松过程：经过包抵达不是泊松过程，但是这个模型很好

M/M/1 队列：

$$d = \frac{1}{\mu - \lambda}$$

交换和转发

以太网交换机 Ethernet Switch

• 检查每个到达的框架的头
• 如果以太网目标地址在转发表中，则转发到正确的端口
• 如果不在，则向所有端口广播（除了来的端口）
• 表中的项通过检查到达包的源地址学习

因特网路由器 Internet Router

• 如果以太网目标地址属于这个路由器，则接受栈帧
• 检查 IP 版本号和数据包长度
• 减少 TTL，更新校验和
• 检查 TTL == 0？
• 如果目标 IP 地址在转发表中，则转发到下一个 hop 的正确出口端口
• 找到下一个 hop 路由器的以太网目标地址
• 创建新的以太网框架并发送

基本操作：查找地址和交换

以太网查找地址：用 hash 表存储地址，找到精确匹配

IP 地址查找使用最长前缀匹配，有 trie 实现和 TCAM 实现，后者并行比较，速度快但是成本高

通用查询地址：<Match, Action>

注意到输出排队的包交换机不可伸缩，如果把队列移动到输入端，则内存速度要求明显下降

对于每个队列，尽管有的有黑色，但是每行的头都是橙色，故只能等待

可以通过虚拟输出队列实现，即在输入队列中做好分类

输出排队：

• 工作节约
• 吞吐量最大化
• 期望延迟最小

虚拟输出队列相当于十字路口的车道

比率保证

因为队列是 FIFO 的，故偏向于流量大的数据，这鼓励了恶性竞争

严格优先：通常用于控制信号

加权优先：

在具体实现中，包的开始时间 $s_k$ 和结束时间 $F_k$ 有递归关系

$$F_k = S_k + \frac{L}{W_1}$$

$$S_k = \max (F_{k-1}, now)$$

延迟保证

控制延迟的方法：

• 比率(WFQ)
• 队列的大小

约束交通：在任何时间长度 $t$ 的周期中，到达的 bit 数被 $σ + ρ t$，被称为“($\sigma$，$\rho$约束）”

在我们的例子中，$σ = B, ρ = R_1$

漏斗 leaky bucket 调节器

然后使用这个调节发送的速率

阻塞控制

基础

导致阻塞的原因：网络能缓冲的包数量是有限的，当进入网络的包速度高于流出的速度时，则经过足够长的时间，一定会有阻塞

所以阻塞是不可避免的，但是在阻塞不太多的情况下是有益的，因为其保持了网络的利用率；但另一方面，如果过大，则延迟过大

公平的定义——最大-最小公平：无法在不减少其它流的速率时增加某一个流的速率

基于网络的控制：ECN 路由器指出阻塞的程度，标记数据包中的位，接收者把这位包括到确认消息中，从而传递回发送者，令其调整发送速度

基于终端：

想起之前的滑动窗口：

通过变化窗口大小改变网络中未处理的包数量，要保证

窗口大小 = min{广告窗口（接收者），阻塞窗口（传递者“cwnd”）}

AIMD (Addictive Increase, Multiplicative Decrease)：

• 如果包成功接受，则 $W ← W + \frac{1}{W}$
• 如果包丢弃，则 $W ← \frac W2$

AIMD 锯齿：

简单 AIMD 流的动态

每当窗口大小增加一时，因为链路已经满了，所以相当于把一个包放到路由器的缓冲区中，当其减半时，相当于等待路由器将缓冲区中的包清空

可以注意到，在理想情况下，链路可以保持充满，缓冲区的占用重复填满-清空的过程

$\frac{W}{RTT} = R$ 是一个常数，因为我们事实上没有调节速率，而是在探索缓冲区的大小

链路速率 $C$，则缓冲区的理想大小 $B = RTT × C$

多个流的 AIMD

从整个缓冲区来看，则占有率几乎保持满；但从其中一个流来看，则其经历了和之前相同的历程。

注意到因为 buffer 占用率不在改变，故 RTT 是一个常数，则吞吐量 = $\frac{W(t)}{RTT}$

通过几何图形的两种计算方法，可以得到

$$R = \sqrt{\frac 32} \frac{1}{RTT \sqrt{p}}$$

其中 $p$ 为丢包的概率

TCP Tahoe

有几个问题：

• 何时发送？
• 何时重传？
• 何时确认？

早期的 TCP 开始时预设的窗口太大了，白白浪费了很多时间在重传上

TCP Tahoe 做出了三大改进：

• 阻塞窗口
• 超时估计
• 自我计时

把阻塞控制分成两个状态：

• 慢开始：连接建立或包超时
• 防止阻塞：稳定操作

慢开始：

• 窗口在最大段大小（MSS）开始
• 对每个确认的包增长窗口 MSS
• 也就是指数级增长，“慢”是相当于之前使用的网络策略的，其实很快

如果估计的往返时间太短，则无意义的重传；太长，则空闲时间浪费了容量

但是 RTT 是高度动态的

在获取 RTT 时，要同时更新考虑到估计值和方差，即

• $r$ 是 RTT 估计值
• $g$ 是 EWMA 增益
• $m$ 是最近的确认的数据包的 RTT 测量值
• 误差为 $e = m - r$
• $r = r + g ⋅ e$
• 方差 $v = v + g(|e| - v)$
• 超时 $= r + β v(β = 4)$

自我计时：返回的时候已经以一个合适的速率均匀分布好了

TCP Reno 和 New Reno

TCP Reno

• 超时和 Tahoe 一样
• 三重确认时
  • 设置门槛为 window/2
  • 设置阻塞窗口为 window/2（快速恢复）
  • 重传丢失段（快速重传）
  • 保持在避免阻塞状态

TCP New Reno

• 超时和 Tahoe 一样
• 在快速恢复阶段
  • 跟踪最后一个未确认的包
  • 在每次重复确认，膨胀阻塞窗口最大段大小
  • 当最后一个包裹确认时，返回避免阻塞状态，设为 cwnd 为进入快速恢复的值
  • 当快速重传在传输中时，开始发送新的包裹

AIMD

可以用 Chiu Jain 图表示为什么 AIMD 是有效的

RFC

Request For Comment(RFC) 是一系列文件

应用层和 NAT

NAT 类型

网络地址转化 Network Address Translator(NAT)：将某主机的端口映射到公网 IP 的另一端口上，外部设备无法主动向内网设备打开连接

完全圆锥型 NAT full cone NAT：普通的 NAT 没有什么限制

受限圆锥型 NAT Restrict Cone NAT：尽管内部端口和 IP 没变，但是外部的 IP 不一样，则不一样的外部 IP 无法连接到该内部主机

端口受限型 NAT：类似，但对于不同的端口无效

对称 NAT：不同的外部 IP 对应相同的内部端口，会建立不同的外部端口

Hairpinning：A 和 B 相互通信时，必须要经过 NAT，但明明可以直接通过 switch 通信，这降低了网络效率

影响

外部设备无法主动向内网设备打开连接，故对于两个都在内网的设备，必须通过中继通信，但还有一种方法——内网穿透 NAT Hole-Punching

• 服务器与两个客户端建立连接，并分别报告另一方的 IP 和端口
• 两个客户端同时向另一方发起连接的请求
• 这对于对称型 NAT 没有用，但这并不是很常见

此外，NAT 只支持 IP，TCP，UDP 三种协议，故很难有其他的协议能够普及

所以 NAT 在一定程度上提高了安全性，缓解了 IP 地址缺少带来的问题，但也带来了非常多的不便

操作

对于没有映射的端口，NAT 和普通的终端一样没有什么区别，所以可以打开自己路由器的配置网页

HTTP

普通的 ASCII 字符

HTTP/1.0

• 打开连接
• 发送 GET
• 服务器在回复后关闭连接

HTTP/1.1 保活

为请求/回应添加连接头，使对方不要着急关闭连接

BitTorrent

Torrent 文件描述了下载的文件

• tracker
• 文件长度，块长度，SHA1 哈希
• 额外元数据

客户端对话 tracker，开始和同伴连接

无 tracker 的 torrent 使用 DHT（分布式哈希表）

• 信息存在许多结点群上
• 分布式协调机制

piece 的哈希值保证了端到端的完整

最稀缺优先策略

以牙还牙 tit-for-tat 策略：上传给你的数据的同伴

绝大多数 peer 被 choke 了而没有得到数据

按照下载速率给未 choke 的 peer 排序，choke 非 P 最好的

随机解除 choke 一个 peer

BitTyrant

• 给 peer 刚足够使其 unchoke 你
• 使尽可能多的 peers unchoke 你
• 给更多 peers 分享容量而不是给其中每个更多

DNS

两个性质使得 DNS 可行：

• 只读和经常读的数据库
• 一致性宽松

这两个性质允许广泛的缓存

层次结构区域（root，edu，Stanford，scs）

每个区域分开管理

美育区域从几个复制的服务器服务

两类请求：

• 递归
• 非递归

UDP 端口 53

可以通过修改缓存中的数据达到污染 DNS 的目的

所有 DNS 消息以**资源记录 Resource Records(RRs)**形式表示：

name [TTL] [class] type rdata

• name：域名
• TTL：存活时间
• class：通常是 IN 1（Internet）
• type：记录的类型
  • A（IPv4 地址）
  • NS（域名服务器）
• rdata：依赖于 type 的资源数据

dig 工具

• QR：0=查询，1=回应
• OPCODE：0=标准查询
• RCODE：错误代码
• flags
  • AA：authoritative answer
  • TC：truncated
  • RD：Recursion desired
  • RA：Recursion available

域名压缩：

• 把名字分成标签，每个标签用长度编码，如：15old-driver-zero，6github，2io
• 以偏移量引用

glue record：父域中的 A 记录，与 NS 记录关联

CNAME (canonical name) 记录：一个名字是别名

• 任何规范名字的记录都会与这个名字关联
• cname 阻止其他名字的 RR

MX 记录：邮件交换记录

其他类型的记录：

• SOA：开始权威
• TXT：任意文本
• PTR：将地址映射为名字
• AAAA：IPv6 地址

DHCP

用 IP 通信需要：

• IP 地址
• 子网掩码
• 网关路由
• DNS 服务器 IP 地址

手动配置

动态主机配置协议 DHCP（Dynamic Host Configuration Protocol)

• 可以向 DHCP 服务器请求配置
• discover，offer，Request，ack，release
• 可以有多个服务器返回 offer，选择一个

无 IPv4 通信：

• UDP 端口 67（服务器）和 68（客户端）
• 广播地址：255.255.255.255
• 使用中继通过链接转发

路由

泛洪，源路由和生成树

flooding：每个路由向所有端口传递包，可能会出现环，所以需要 TLL，在对拓扑结构一无所知的情况下有用

源路由：源在包头中指定路由的路径（端到端）

生成树

多路径：通过多个路径将数据包散布到目的地，不给一条路径增加大量负担

多播 multicast：将数据包发送给多个主机

Bellman Ford 算法

假设每个路由直到邻居链路的花费，每个路由 $R_i$ 都维护抵达 $R_8$ 的花费 $C_i$

向量 $C=(C_1, C_2, \dots, C_7)$ 是到 $R_8$ 的距离向量，所以这个算法是一种距离向量算法

Bellman-Ford 算法的问题在于坏消息传播慢

解决方法：

• 将无穷设置为某个较小的整数
• 水平分裂：因为 $R_2$ 从 $R_3$ 处获取最小路径，故其不会反过来通过 $R_3$

Dijkstra's 最短路径优先算法

这是一种链路状态算法

交换链路状态：一个路由向每个与其相连的链路状态路由泛洪

每个路由独立地运行 Dijkstra's 最短路径优先算法

特点：

• 链路状态被每个路由得知
• 每个路由找到向其他路由的最短路径生成树

这是 **OSPF（Open Shortest Path First）**的基础

算法的直观理解：将小球用线连接在一起，慢慢举起一个小球

Internet 中的路由

自治系统 Autonomous System(AS) 是互联网层次结构的基本单元

• 在 AS 中，所有者决定路由方式
• 在 AS 间，必须使用 BGP-4（边界网关协议 Border Gateway Protocol, v4)

内部路由协议 Interior Routing Protocol：

• 路由信息协议 Routing Information Protocol (RIP)：使用 Bellman-Ford 算法，现在很少用
• OSPF 路由协议 Open Shortest Path First(OSPF)：每个路由使用 Dijkstra 算法，广泛使用
• IS-IS 路由协议：类似，也广泛使用

路由到一个出口：每个包都发送到默认路由器即可

路由到多个出口：

• 热土豆路由：发送到最近的出口
• 选择离目的地最近的出口

外部路由协议：

BGP-4：解决不同 AS 的边境争端

BGP

BGP 使用路径向量，其发布完整的路径，也称作 AS_PATH

• 有环的路径在局部被检测并忽略
• 局部政策在选项中选择路径

BGP 消息：

• Open：建立 BGP 对话
• Keep Alive：定期提供一次握手
• Notification：关闭同伴对话
• update：宣布或撤销之前宣布的路线

BGP announcement = prefix + path attributes

• path attributes 包括：下一跳，AS 路径，局部选择，多出口鉴别器

多播

反向路径广播（RPB 或 RPF）：相当于剪枝后的洪泛算法，每个路由只接受来自生成树上的包并向所有端口扩散，这样就避免了成环

剪枝 pruning 策略：无目的主机的路由向源发送剪枝消息

一棵树 vs 多棵树：维护某一路由的最小生成树，所有路由都要经过那个路由，而不是每个路由都有一颗最小生成树

D 类 IPv4 地址用于多播

Internet 组管理协议 IGMP (Internet Group Management Ptotocol)：

• 在主机和直接连接的路由器中
• 主机询问接受属于一个特定的多播组的包
• 路由器周期性地询问注意想要哪个组
• 如果没有回应，则成员关系超时

距离矢量组播路由选择协议 DVMRP (Distance Vector Multicast Routing Protocol)：

• 第一个互联网路由协议
• 使用 RPB + Prune

协议无关多播 PIM (Protocol Independent Multicast)：

• 稠密模式：类似于 DVMRP
• 稀疏模式：建造集会点

在实践中多播使用并不广泛（主要是流媒体的兴起）

生成树协议

防止循环：

• 决定树的根
• 决定转发的端口

工作：

• 所有的交换机广播网桥协议数据单元 Bridge Protocol Data Unit (BPDU)

  • 发送者的 ID，根的 ID，从发送者到根的距离

• 每个交换机都声称是根：设置距离为 0

• 每个交换机广播直到收到一个更好的信息

• 如果一个交换机收到一个更好的信息，则重传

• 根端口：最接近根的端口

• 指派端口：用于抵达根的端口

• 其余端口被阻塞转发，但仍可以发送和接收 BPDU

IPv6

• 128 位
• 写成 8 块 16 bit
• 可以使用 :: 省略大量的 0
• 在 URL 中使用 []
• 低 32 位可以像 IPv4 一样书写

可以从子网掩码 /64 和以太网地址中自动生成 IPv6 地址：

| c c c c c c 0 g | c c c c c c c c | c c c c c c c c | m m m m m m m m | m m m m m m m m | m m m m m m m m |

反转 0 和插入 0xfffe：

| c c c c c c 1 g | c c c c c c c c | c c c c c c c c | 1 1 1 1 1 1 1 1 | 1 1 1 1 1 1 1 0 | m m m m m m m m | m m m m m m m m | m m m m m m m m |

更低的层级

容量与调制

香农极限：信道容量 = $B\log_2(1+S/N)$

• $B$ 是带宽，$S$ 是信号强度，$N$ 是噪声

振幅键控方式 Amplitude Shift Keying(ASK)：在有线网中有用，因为信号强度不会衰减很多

PMA-5：五级脉冲振幅调制：在 100BASE-T 和 1000BASE-T 以太网中常用

PMA-16：16 级，在 10GBASE-T 中使用

相位偏移调制 Phase Shift Keying(PSK)：更广泛使用

• 二进制相移键控 BPSK：两个相位 (0, $\pi$)
• 正交相移键控 QPSK：四个相位

IQ 星座 I/Q Constellation：在二维图中表示相位偏移调制的符号

符号 symbol 是物理层的传输单元，一个符号可以容纳多个 bit

正交振幅调制 Quadrature Amplitude Modulation(QAM) 同时使用了振幅和相位

• 16-QAM：16 个符号
• 256-QAM：256 个符号

位错误和编码

信噪比 Signal to Noise Ratio(SNR)

bit 错误率可能很低，但绝不会为 0

编码：在物理层添加一些冗余提高链接层的吞吐量

编码增益 coding gain

• 3/4 编码：每 3 个链路层的 bit 对应物理层的 4 bit

bitrate = bits/symbol _ symbol rate _ coding rate

时钟和时钟恢复

数据通过时钟传递，但是不知道发送者的时钟，可能会有一定偏差

因为始终没有单独发送，故数据流必须有足够多的转移使接受者确定时钟

曼彻斯特 Manchester 编码：数据为 0 时对应下降沿，为 1 时对应上升沿，两个相同的则会在中间添加一个时钟沿

优点：

• 保证了每个 bit 周期都有一个转移
• 保证了 d.c. 平衡，即高电平和低电平数量一样

缺点：最坏情况下带宽加倍

方法 2：4b5b 编码

优点：

• 带宽利用率更高
• 允许控制信息的额外编码

缺点：转移较少，恢复较难

转发错误纠正

Reed-Solomon 错误纠正：广泛使用，数学上较简单

思想：

• 选择 k 块数据
• 使其成为 k-1 阶多项式的系数
• 沿着多项式计算 n 个点，作为编码数据发送
  • n 个点中的任意 k 个点都能还原多项式系数

细节：

• 可以纠正至多 n-k 个擦除 erasure（直到错误发生的位置）
• 纠正至多 (n-k)/2 个错误（不知道发生的位置）

因为物理媒介通常是并发的错误，所以可以通过交错 interleaving 使编码更强健

CSMA/CD

在以太网，多个主机共享媒介，所以需要决定谁去发送，何时发送

有一类媒质访问控制协议 Medium Access Control(MAC) Protocol Protocol

目标：

• 共享信道的高利用率
• 公平
• 低成本，简单
• 对错误强健

Aloha 协议：

• 如果有数据要发送，就发送
• 如果传输和其他冲突了，则过一会儿重传

**带有冲突检测的载波侦听多路存取 Carrier Sense Multiple Access/collision detection (CSMA/CD) 协议：**当有包想要传递时

• 载波侦听 carrier sense：在传输之前检查线路
• 冲突检测：尽可能检测冲突，如果检测到冲突，则等待；等待随机时间（二项式指数后退），然后返回

要等到两个发送者都能检测出冲突，所以必须满足 $\frac PR ≥ \frac {2L}{c}$

以太网

• preamble：恢复时钟
• SFD：指示开始帧
• DA：48 位的全局唯一的目标地址，有制造商赋予
• type：封装数据的协议 IP=0x0800
• pad：满足最小帧长度
• CRC：循环冗余检查，检验序列，用于检测位错误

最常见的是 10Base-T：双绞线以太网

当数据速度 R 提升时，为了满足之前的不等式，可以限制 L 或使用以太网交换机

100Base-TX：

• 全双工 full duplex，即数据可以在两个方向上同时传输

现代不再用 hub 了，而是全部改成了 switch

无限网络

不同之处：

• 空间传播：衰减快（平方反比）
• 无法控制的介质：信号强度随着时间改变
• 干扰

CSMA/CA

以太网的 CSMA/CD 无法直接使用，因为发送者可能无法得知发生了冲突

故这里采用 CSMA/CA，区别在于如果接收方成功接收到了数据，则发送 ack；如果发送方未收到 ack，则认为发生了冲突

这种方法也存在一些问题，如

隐藏的终端：A 和 C 无法感知到对方的存在，但会发生冲突

暴露的终端：B 和 C 可以同时发送，却根据规则，其中一方无法发送

无法区分是冲突还是信噪比低：

RTS/CTS

可以解决第一个问题，可以帮助解决第二和第三个问题

问题在于当传输速率提到时，这种方法的开销占比明显增大

802.11 格式和开销

链路层头的前两项用于虚拟载波感知 Virtual Carrier Sense

接下来的地址项为无限连接的节点提供有线的虚拟访问

为了向后兼容，无法全速发送物理层的头，否则一些旧设备无法接收到，故当传输速率较大时，会收到这一段的传输速率限制

碎片化

高层的数据单元比较低层的数据单元大，故要将其分裂为更小的块

组装：合并为原来的数据单元

TCP 一般要避免 IP 碎片化，故需要选择合适的段大小，可以二分查找，但一般直接尝试几种常见的 IP 碎片大小就行了

安全

介绍

• 窃听 eavesdrop：被动嗅探或记录网络数据
• 修改，删除，插入：主动篡改数据
• 阻止通信：denial of service

都可以发生在网络的各个层级

中间人攻击：伪装成另一方，作为一个两者通信的中间人

我们需要：

• 保密性 confidentiality：没人可以监听通信——加密
• 完好 integrity：消息不被篡改——消息验证码
• 身份验证 authentication：确认其他另一方的身份——数字签名和证书

攻击

第二层：

• 监听杂乱模式的接口
• 强制包广播，然后使用上面的方法
• 伪装成 DHCP 或 ARP 服务器，重定向包到一个不同的端主机

MAC 溢出攻击

第三层攻击

使用 ICMP 告诉源端主机重定向交通

BGP 劫机：

• ISP 广告属于其他人的前缀，阻塞交通
• 广告无效的路径，制造黑洞
• 需要伪装成 ISP 或接管 BGP TCP 段

更具体的前缀

拒绝服务

分布式拒绝服务攻击 DDOS

保密性

对称式加密

一次一密 one-time pad：使用异或加密和解密

但是注意到如果使用同一个密钥加密了两个数据，这两个加密后的数据会泄露信息

流密码：伪随机的 pad

块密码：对固定大小的块操作

注意到攻击者可以学习重复的明文块

密码分组链接 Cipher-block chaining (CBC)

完整性

• 加密哈希
• 消息验证码（MACs）

加密哈希

• 抗碰撞，即很难找到哈希值相同的两个不同的数据
• SHA-256 或 SHA-512

HMAC：从密钥和哈希中生成 MAC，即 HMAC(K,M) = H(K ⊕ opad, H(K ⊕ ipad, M))

加密和 MAC 混用时，注意一定要先加密，再计算 MAC

公钥加密

非对称式加密

• 机密性：公钥加密，私钥解密
  • 加密必须是随机的，否则可以猜出简单的明文
• 签名：私钥加密，公钥解密

杂交方法：用公钥加密对称式密钥

注意不要给未指定的信息签名，如未填写收件人信息和时间等

证书

如何证明服务器的公钥是真的？

每个人信任几个签名机构并获知其公钥，通过信任链去信任更多的证书

是 TLS/HTTPS 的工作原理

TLS

传输层安全 TLS：TCP 之上的会话层安全

TLS 会话指派了四个密钥：

• 服务器和客户端的身份验证（RSA）
• 密钥交换（RSA）
• 对称式加密（AES）
• 完整性（HMAC-MD5）

TLS 将数据流分裂为记录，记录可以被压缩，记录通过 TCP 发送