计算机网络背诵笔记

发表于 更新于 Waline： 阅读次数：

本提纲是计算机网络课程的复习背诵，根据西交的考点截取了内容。这个课程使用 Tanenbaum, Andrew S. 的著名课本。

这次考的不难，居然没有 TCP 拥塞控制。

开悟

计算机网络是一组通过单一技术相互连接的自主计算机集合

分布式系统强调整体性

分类

[Personal | Local | Metropolitan | Wide] Area Networks、internetworks

按其他标准

子网：一组路由器和通信线路的集合，主要负责将数据包从源主机移动到目的主机

分层模型

优点：各层独立，灵活性好，结构分离，易于实现维护，促进标准化

原则：根据功能需要，功能明确，利于标准，信息量少，层数合适

OSI 七层模型（主要概念：服务、接口、时序）

协议三要素：语法、语义、时序

Unit exchanged 层 协议
APDU 应用 HTTP, SMTP, RTP, DNS, TELNET, FTP, DNS
PPDU 表示
SPDU 会话
TPDU (Segment) 传输 TCP, UDP
Packet 网络 IP, ICMP, RIP, OSPF, BGP
Frame 数据链路 PPP
Bit 物理

TCP/IP 模型：应用层，传输层，互联网层（Host to network）（Link layer）

会话层：管理应用程序间的会话；表示层：处理语法语义

服务

有无连接，有无确认

服务 例子
可靠消息流 帧序列
可靠字节流 远程登录
不可靠连接 数字语音
不可靠数据报 垃圾邮件
确认数据报 挂号信
请求-回复 数据库查询

Standardization

Body Area E.g.
ITU Telecommunication G.992 (ASDL), H.264
IEEE Communications 802.3, 802.11, 802.15 (PAN)
IETF Internet RFC 2616, RFC 1034/1035
W3C Web HTML5

Internet Architecture

  • POP: Point Of Presence；ISP 存点
  • IXP: internet exchange point；Internet 交换点
  • CMTS: cable modem termination system
  • DSLAM: access multiplexer
image-20220223102513412

物理层

机械特性；电气特性；规程特性（同步、信号时序、应答关心、操作过程）；功能特性

傅立叶分析

假设周期是 8 个 Bit，8 次谐波足以复原信号

则 \(b\) Bit/s 的第一个谐波频率为 \(b/8\) Hz，可发送的谐波次数是截止频率（电话线 3kHz）除以一次谐波频率

Nyquist 采样定理

波特率：符号一秒变换的次数 \(B_r\)；比特率 \(s\)（bps）；离散等级 \(V\) \[ s=B_r\log_2 V \] 采样定理 \[ \max{s} = 2B\log_2V \]

其中 \(B\) 为带宽

也就是说，带宽 \(B\) 的信道最多做两倍频率采样来到达 \(2B\) 的波特率

Shanon 定理

\[ \text{Maximum Bit Rate} = B\log_2(1+S/N) \]

其中 \(S/N\) 是信噪比

dB: \(10\log_{10}(S/N)\)

介质

引导型介质：磁，双绞线（S/U TP），同轴线，电力线，光纤（0.85um, 1.30um, 1.55um）

非引导型介质：电磁波，微波，红外，可见光

VLF，LF，MF 地面传播（AM）

HF、VHF、UHF 电离层反射（FM/TV）

卫星：LEO，MEO（GPS），GEO（L, S, C, Ku, Ka）（SHF、EHF）

小口径终端可使用地面 Hub 放大

数字调制

比特（数据）与代表他们的信号之间的转换过程称为数字调制

Baseband、Passband

2-20
  • T1/USB：NRZI
  • Ethernet：Manchester

解决 NRZI 长串 0：4B/5B 码，扰频

解决直流分量：双极编码（1/-1 均为 1，用于平衡直流分量），8B/10B码

通带传输

ASK 幅移键控

FSK 频移键控

PSK 相移键控：二进制相移键控 BPSK，正交相移键控 QPSK

QAM 正交调幅

2-22

信道复用

频分复用 FDM

利用通带传输使多个用户共享信道

OFDM 正交频分复用：取消保护带，在所有子载波上调制

波分复用 WDM

（SONET）波长，光纤上极高频率的频分多路复用

时分复用 TDM

时间槽，保护时间

统计时分复用

码分复用 CDMA

Code Division Multiple Access，由 Walsh 码产生正交码片序列，每个比特分为 \(m\) 个码片，每个站发送被分配的码片序列或其反码

所有站的码片序列两两正交，\(S\cdot T=\dfrac{1}{m}\sum_{i=1}^mS_iT_i=0\)

2-28

电话交换网

Local loop; Trunks; Switching offices

LATA (Local Access and Transport Access), LEC, IXC

DSL: Cat3 UTP

ASDL (Asymmetric Digital Subscriber Lines) 256x4kHz Channels; 0-25 Voice

数字电话中使用脉冲编码调制 PCM，Pulse Code Modulation，每秒采集 8000 个样值，T1 载波每帧（125 \(\mu\text{s}\)）24 个信道（TDM），每信道 8 bit，一个帧标记位，共 193 bit，\((8\times 24 + 1)\times 8000 = 1.544\) Mbps，信令控制 8 kbps

T2 = 4 T1，T3 = 7 T2，T4 = 6 T3

SONET（Synchronous Optical Network），每帧 \(87+3\) 列，\(9\) 行， \(8\times810\times((87+3)\times 9)\times 8000 = 51.84\) Mbps

有线电视网同轴搭接，同轴接到光纤节点；固话每家回环到 End Office

交换

电路交换（Strowger 装置）：建立电路，传输数据，拆除电路

包交换（存储-转发）：报文交换（逻辑上完整），分组交换（数据报、虚电路），信元交换（固定长度的信息段）

2-43

发送时延、传播时延、转发时延

蜂窝网络

频率可跨蜂窝复用，并随着用户的移动而切换蜂窝

模拟语音 1G（AMPS），临近蜂窝不复用，832 个信道（Control/Paging/Access/Data），FDM，频分双工（FDD）

数字语音 2G（GSM），124 FDM，8 TDM，148 bit 数据帧

移动交换中心 MSC，归属位置寄存器 HLR，拜访位置寄存器 VLR，鉴权中心 HLR

数字语音数据 3G，CDMA（长伪随机序列），功率控制

4G，TD-LTE（TDD 时分双工）

5G，融合怪

数据链路层

主要功能：物理地址；成帧（定界与同步）；差错控制；流量控制；信道访问控制

PPP：成帧，链路控制（启动、测试线路、协商参数）、协商网络层选项（没有差错流量控制）

上层服务：不可靠（无 ACK）无连接，可靠无连接，可靠连接

应答：最常采用正向（负向，双向）

成帧

原则：易区分，带宽小

  • 字节计数法
  • 字节填充的标志字节法 FLAG，ESC
  • 含位填充的分界标志法：使用 01111110 定界，连续 1 塞 0
  • 物理层编码违例法：冗余编码使用

错误控制

自动纠错

  1. Hamming codes

  2. Binary convolutional codes

  3. Reed-Solomon codes

  4. Low-Density Parity Check codes

汉明距离即异或值的 1 数量

纠错码 \(n=m+r\) 位，对于一位错误纠错，\(m+r+1\le 2^r\)（对于合法的 \(2^m\) 个码字，距离 1 内的 \(n+1\) 个码字都纠错至它）

Hamming Code

汉明码 index \([1,n]\)，第 \(2^k, k\ge 0\) 位是二进制 index \(k\) 位为 1 的所有值（包括自己）的偶校验

纠错位置为所有校验结果拼接成的二进制串表示的 index（...P8P4P2P1）

检错反馈重发

  1. Parity

  2. Checksums

  3. Cyclic Redundancy Checks

CRC

\(r\) 阶生成多项式 \(G(x)\)，向帧追加 \(r\) 位使得多项式能被 \(G(x)\) 模二除尽

流量控制

Utopian

无错，理想信道，单工

链路层进什么出什么

无错信道下的单工停等协议

收方有有限的速度和缓冲区，每收一包发送确认；

发方只有确认后才可发下一包。

有错信道下的单工停等协议

采用正向应答、定时重传、循环序列号

有错信道下的双工协议

Piggybacking：ACK 序列号在数据帧中附带

缺点：同时开始传送时，若超时计时器不合理，将会传送三次以上

ack_timeout 用于 Piggyback 缺少反向流量的情况

滑动窗口协议

发送端维护允许连续发送未应答帧的序号，当收到 ACK 后该序号移除并后移窗口

接收端维护允许连续接收未处理帧的序号，当收到后将该序号移除并后移窗口

延迟-带宽乘积 \(BD\)，窗口大小（发送容许未 ACK 的帧数量）为 \(w\)，链路利用率小于 \(\dfrac{w}{1+2BD}\)

损坏帧处理

根据接收缓冲区和带宽的 Trade-off，有两种方案

Go Back N

在该帧之后的所有帧都会被忽略，接收窗口大小为 1

使用累计确认（accumulative acknowledgement），确认某帧会确认之前帧

每一帧都要给一个计数器

Selective Repeat

仅重传该帧，需要 NAK

为了防止发送接收窗口重叠，序列号空间至少为窗口大小的两倍

数据链路层协议例子

SONET

IP 包；PPP 帧；SONET 载荷

PPP 负责成帧，链路控制（LCP），协商网络层选项（NCP），错误检测；不需要错误纠正，流量控制，有序性，多点链路

PPP 帧结构：Flag 转义 0x7D 0x5E；控制域在不可靠线路上可以使用有序号的传输

image-20220223141513564
image-20220223142343462

ASDL

PPP；AAL5；ATM；ASDL 载荷

image-20220223144101981

介质访问控制子层

静态信道分配：FDM，TDM

动态信道分配假设：独立流量、单信道、检测冲突、连续时间或时间槽、载波监听或无载波监听

发送站行为假设：所有帧长相等，泊松分布发送每帧时间发送包均值 \(0<N<1\)，带重传均值 \(G\)，冲突率 \(P_0\)，吞吐率 \(S=GP_0\)

给定时间发送 \(k\) 帧的概率

\[ \mathrm{Pr}[k]=\frac{G^ke^{-G}}{k!} \]

ALOHA

连续时间

无载波监听，若要发送，则直接发送，若冲突，随机重传；\(G=0.5\) 时效率最好 \(18.4\%\)

\(S=Ge^{-2G}\)

时间槽

时间槽内才能发送，冲突时间减半，最高效率翻倍 \(G=1\) 时效率最好 \(36.8\%\)

\(S=Ge^{-G}\)

CSMA

Carrier Sence Multiple Access，有载波监听的多站访问

1-persistent

监听，若可发，立即发

Non-persistent

监听，若不可发，随机时间后再次尝试

p-persistent

使用时间槽，若信道可用，以 \(p\) 概率发送，\(1-p\) 概率下一槽发送

CSMA-CD

CSMA with Collision Detection，带冲突检测

如果冲突发生，立即停止发送，等随机时间

Bit-Map Protocol

N 个冲突槽，在冲突时间发比特以预约，接下来由编号高的站先发

Token Ring

拥有 Token 的站可以发，并把 Token 传递给下一个站

Binary Countdown

在竞争期间从高到低发自己的编号，若看到 1 且自己为 0 则放弃（上述两种每站在竞争期间都需要一位，\(O(N)\)；此方法 \(O(\log N)\)）

Limited-Contention Protocols

思路：对 \(k\) 个站来说，每个站该槽发的概率若是 \(p\)，成功发的几率是 \(kp(1-p)^{k-1}\)。对 \(p\) 求导可得最优概率 \(((k-1)/k)^{k-1}\)。将多个站分为组，组内竞争，组间无竞争。

The Adaptive Tree Walk Protocol

自适应树遍历协议：叶子是站，节点是组，有冲突则深度优先走直到不冲突

假设 \(q\) 个 ready 站均匀分布，\(i\) 层某节点的 ready 站期望为 \(2^{-i}q\)

Wireless LAN Protocols

Hidden terminal problem：A 给 B 发，看不见的 C 也给 B 发

Exposed terminal problem：A 因为 C 不给 B 发，但实际上 C 对 B 没影响

MACA (Multiple Access with Collision Avoidance)：RTS (Request To Send)，CTS (Clear To Send)；其他收到 CTS 的站不能发，仅收到 RTS 的站可以发

Ethernet

Classic Ethernet

Physical Layer

全部通过 Transceiver 接到同一根同轴线上，同轴线可以 Repeater 串接

发曼彻斯特码

线：xBasey/xBase-T/F，x 表示速率（Mbps），Base 基带传输，y 表示 coax 长度（100m），Twisted pair/Fiber；用四个中继器最长 2500 米

MAC Sublayer

帧格式

前导码每字节 10101010，除了最后一位 Start of frame；它是曼彻斯特码方波

MAC 地址第一位 1 是组播地址，全 1 是广播地址

由于 Ethernet 和 IEEE 的兼容问题，0x600 以下为 Length，否则 Type

Data 最长限制最早来自于 Transceiver 的 RAM 容量

传播时延 \(\tau\)，最长 \(2\tau\) 时检测到错误，帧长不得小于该时间（2500m，50 \(\mu\)s，10 Mbps，则最小帧长 500 bit）；每一个检测到冲突的站都发 4-6 Byte 的干扰串；最小帧长 64 字节

32 bit CRC Checksum

CSMA-CD

一个时间槽 64 bit

802.3：1-坚持 CSMA-CD

Binary Exponential Backoff: 假设我发的帧已经撞了 \(i\) 次，下次发之前等待 randfrom(0, 2^i) 个时间槽；第 10-15 次冲突等最多 1023 个时间槽，第十六次没成功就开摆

交换以太网

全双工则无冲突

混杂模式：所有的帧给所有的电脑，不只给 dst

快速以太网

802.3u，直接快十倍，再变短（210 m）

100Base-TX 4B-5B 125 MHZ, 100 Mbps (Cat 5 UTP)

image-20220222181549156

千兆以太网

支持 200m：

  • 载波扩展（加 Padding 到 512 Byte）
  • 帧突发（合并多个帧）

万兆

10GBase-[S|L|E]R/CX4/T，三种光纤/四对同轴/四对双绞线（Cat 6a）

无线网络

802.11

数据链路层分为 MAC 子层和 LLC（Logical Link Control）子层

Physical Layer

802.11 Frequency hopping

802.11b Spread spectrum, CDMA 2.4G

802.11a OFDM 5G

802.11g OFDM 2.4G

802.11n MIMO OFDM

MAC Sublayer

CSMA-CA

准备发之前先随机后退（Backoff）一段时间，若冲突使用 Binary Exponential Backoff

使用 ACK 推断冲突

DCF: Distributed Coordination Function 分布式协调功能

Point Coordination Function 用于单 AP 情况，通常无用

Virtual Sensing: Network Allocation Vector 记录别的站要发多久，RTS CTS 实际上没啥用

DIFS (DCF Interframe Spacing) 每种帧后退不一

802.11 帧格式

三个地址：AP, src, dst; rcv, AP, src

802.16 Broadband Wireless

早期试图作为有线本地回环的无线替代的产物，挑战 4G

数据链路层有三个子层：Security Sublayer; MAC common sublayer; Service specific convergence sublayer.

Physical

802.16a OFDM, Fixed; 802.16e Scalable OFDMA Mobile

3.5 GHz/2.5 GHz

MAC

Classes of service (same as ATM)

  • constant bit rate (uncompressed voice)

  • real-time variable bit rate (compressed multimedia)

  • non-real-time variable bit rate (file transfer)

  • best-effort (else)

Bluetooth

Piconet: Master and slaves

TDM 系统（时分复用）

活跃从节点最大 7 个，最多 255 个驻留节点

Scatternet: overlapping piconets

对于不同的应用预先定义 Profile

Linkcontrol \(\sim\) MAC

L2CAP: Logical Link Control Adaptation Protocol

Header：F 流量控制 A 确认 S 序号；重复三遍是保证大量冗余

RFID

Radio Frequency Identification

EPC (Electronic Product Code) Gen 2 RFID

Physical layer

标签选择不反射或反射读写器的信号（后向散射 Backscatter）

Tag Identification Layer

Slotted ALOHA

读写器告诉标签的时间槽范围（Query Qrepeat），标签随机选择时间槽应答 RN16，收到读写器ACK后，再发 EPC

二层交换

学习网桥

网桥工作在混杂模式（dst 不是网桥的包也可以处理）

泛洪：不知道就全发

后向学习：看源端口学

生成树网桥

802.1D

选举一个根，然后按到根的距离做生成树

VLAN

802.1Q

最大长度 1522 字节（本来是 1518）

Type 字段魔改一番；CFI: Canonical Format Indicator

网络层

主要功能：寻址；路由选择；数据分组转发；流量控制；拥塞控制；差错检测恢复；审计

面向连接实现

标签交换：路由器可以分配连接标识符

多协议标签交换 MPLS

路由算法

  • 泛洪算法：设最大跳数，通过维护源路由器的最大序号表判断泛洪过的数据包

  • 距离矢量路由：表告诉你某目的走哪条路

    • 有无穷计数问题

  • 链路状态路由（OSPF/IS-IS）：把完整的链路信息发给别的节点

    • 广播 LAN（一根 Ethernet）被建模成一个节点，指定一台做路由工作

    • 发现邻居、度量成本、构造信息包、发给其他路由器、接收信息包、计算最短路

    • 每一个链路信息数据包都有 Age，每次转发或走过一秒减一

    • 状态包缓冲区里记录了 Age，Seq，发送标志（要发到哪里），ACK 标志（从哪个端口来）

  • 层次路由：分层，最优的层数是 \(\ln N\)

  • 广播路由：逆向路径转发（沿着生成树来的泛洪包可以转，其他的不用）

  • 组播路由：距离矢量组播路由协议（生成树子树如果没儿子有兴趣就剪掉，但是每个组播源都可能是根）；核心树（发给某个组的树根然后转发，树其实是同一颗）

  • 任播路由（Anycast，发给最近的组成员）：层次路由即可

  • 移动路由：家乡代理

  • Ad Hoc 路由（ADOV）：按需发现（泛洪），路由维护（周期 Hello）

拥塞控制

  • 网络供给：加钱

  • 流量感知路由：依照负载调节路由权重

  • 准入控制：应用于虚电路，控制虚电路建立

  • 流量调节：向上游发 Choke 包（抑制包）；ECN（应答包上打标记）；逐跳后压（每一跳收到抑制都要减缓）

  • 负载脱落：Wine；Milk；Priority；RED（Random Early Detection，平均队列长度超阈值即丢）

服务质量

  • 应用需求（带宽；延迟；抖动；丢失）

  • 流量整形

    • 漏桶：数据包恒定速率流出

    • 令牌桶：用令牌发包，令牌恒定速率供给，可以存一些

  • 包调度：同一个流的数据包需要统一路由；预约带宽、缓冲和 CPU 时钟

    • Round-robon 多个流公平队列

    • Weighted Fair Queueing 计算 Finish Time \(F_i=\max(A_i, F_{i-1})+L_i/W\)，按 Finish Time 排序发送

  • 准入控制：建立流时生成流规范（令牌桶容量，令牌桶速率，峰值速率，最小最大包大小），一路上的路由器调整规范并预留资源

  • 综合服务，资源预留协议：沿着组播生成树往上走做预留

  • 区分服务：基于类别的服务质量，单跳行为（在服务器的待遇）

    • 加速转发：开了一个新的快道

    • 确保转发：先过分类器，再过监管器，生成 12 个 优先级（4 个分类 3 个丢包），进 WFQ

互联网络

网络层要隐藏下面不同的链路层技术

多协议路由，管道技术：直接把整个带头的包包住（v4 包 v6）

数据包分段

限制包长的理由

  • 硬件（如以太网 1500）

  • 操作系统（如 512 Byte 缓冲区）

  • 协议（IP 65515 Byte）

  • 标准

  • 减少错误带来的重传（802.11 2272 Byte）

  • 防止占信道

MTU (Path Maximum Transmission Unit)

Transparent fragmentation: 出网关重组（需要计数，路由器支持，需要缓冲）

Nontransparent fragmentation: 直到目的再重组（分段开销，丢包，主机突发大）

分段相关字段：包编号（分段后一样）；Offset（第一字节的偏移量）；终止位（最后一段）

路径 MTU 发现：如果包太大就传回去告诉源重发个小的

IPv4

IP 头

(4b) IHL: 头长度，5-15 Words

(1B) Diff.Serv.: 6b 标识确保服务，2b ECN

(2B) L: 65535 Max

(2B) ID: 包序号，同一个包的所有段一样

(1b) Unused

(1b) DF: Don't Fragment，来检测 MTU

(2b) MF: More Fragments: 同包最后一段置 0

(13b) Frag.Offs: 第一字节的位置，段按 8 Byte 对齐，则少三位

(1B) TTL: 最多活 255 跳

(1B) Protocol: 传输层协议

(1B) Checksum: 所有半字的和的补码（加起来是零）

Option 基本不管了

IP 地址

The prefix is network address; the suffix is the host address.

Subnetting: 加长给的 prefix

CIDR-Classless InterDomain Routing 无类域间路由：

  • 路由聚合，即高层路由器的表项前缀变短

  • Longest matching prefix：聚合完了可以加项，这些前缀长的优先匹配

Classful addressing

Special addresses:

127.*.*.* 环回

0.0.0.0 This host

255.255.255.255 广播

(Network)11...1 某网络下的所有主机

224.0.0.0/24 本地网络组播

NAT

依赖 TCP/UDP 协议

三种内网 IP

1
2
3
10.0.0.0    - 10.255.255.255/8
172.16.0.0  - 172.31.255.255/12
192.168.0.0 - 192.168.255.255/16

  • Full Cone NAT：第一次使用建立映射 (IP:Port) \(\to\) (IP:Port)，内发外外发内地址不变

  • Restricted Cone NAT：外网主机 S 按映射地址发内网主机 C 时，C 必须向 S 的 IP 发过包

  • Port Restricted Cone NAT：外网主机 S 按映射地址发内网主机 C 时，C 必须向 S 的 IP:Port 发过包

  • Symmetric NAT：外网主机与内网建立连接，NAT 都会创建新的 IP:Port，其他外网主机无法通过别的连接建立的 IP:Port 访问

IPv6

目标

  • 很多

  • 减小路由表

  • 简化，更快

  • 安全

  • 关注服务类型

  • 辅助组播

  • 漫游不换地址

  • 给发展留空间

  • 共存

流标签为零时不是虚电路，流标签和地址有关

Payload Length 不算 40 个字节的头

Next Header 是可选头的类型，若没有可选头就是下一个协议头

不分段，直接发现 MTU

ICMP

它是包裹在 IP 里的

ARP

Who has (Some IP)? Tell (Some IP);

(Some IP) is at (Some MAC).

缓存 ARP 表，ARP 表会超时，以允许动态

广播可以把自己的表也给你一份

ARP 别的网会问到网关的 MAC，这样就发给网关了

DHCP

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

需要 DHCP 服务器，路由器也支持

DISCOVER;

OFFER.

MPLS

多协议标签交换

可以多加很多层标签，这样按最外层路由，可以将多条路径合并节省

S 表示后面是不是还有标签

OSPF

Open Shortest Path First

域内路由算法（内部网关协议）（RIP 也是内部网关协议）：自治系统（AS）里的协议

如果有多条最短路，OSPF 会平均载荷

支持物理距离、延迟等距离尺度

一个区域内的最短路计算是一样的

边界路由器可以传递拓扑的摘要，如果边界只有一个路由器（stub 存根），不需要传递路由信息

BGP

Border Gateway Protocol

域间路由算法，解决政治、经济问题

是距离矢量协议

路由器通过 TCP 通信

所有 AS 从 AS1 买服务，AS2 3 间有对等传输

IGMP

组播

Mobile IP

  • Use home IP everywhere

  • No software changes

  • No router/table changes

  • Restrict detours

  • No overhead at home

ARP 代理

gratuitous ARP

传输层

主要工作：屏蔽子网差异；弥补应用层差异；提供进程级通信能力

传输实体：Kernel/so/proc，给应用层提供两种服务

单独的一层：位置不一样，主机，路由器。用户对网络层没有控制权

Segment: TPDU (Transport Protocol Data Unit)（想想为啥它也要 Seq）

Berkeley Socket 原语

NSAP(Network Service Access Point): IP

TSAP(Transport Service Access Point): Port

如何区分并拒绝重复的段：数据包存活上限 \(T\)（120s for Internet），序号在 \(T\) 内不被重用（划禁止区域），初始序号即（不同步的）计数器的低位，序号递增速率不得大于时间进度

三次握手（目的是让服务器区分连接请求是否确是当前的）

段也要时间戳，为了防止 32 位序号绕回（因为现在太快了）（序号需要随机以防被预测）

非对称释放：挂电话；对称释放：我不发了哦

四次挥手，因为要是对方决定好了要放开连接才放开连接，那就放不了了

挥手以及 ACK 超时都会释放连接

多路复用：多个连接过一个地址（路由器）；逆向多路复用：一个连接利用多个网络地址冲

差错控制

链路层的差错控制可以避免整条路径重传

传输层差错控制可以防止路由器出错

BL 积非常大，窗口和缓冲要大，多连接：缓冲池

动态缓冲区分配，发送端告知要多少缓冲，接收端分配并告诉实际缓冲数量（Window size 字段）

窗口大小跟踪网络承载能力的变化，也可以达到拥塞控制

主机崩溃恢复只能由上层完成（A for ACK；W for write to process；C for crash）（S0 没有未完成的段但有确认，S1 没有确认）

流量控制

流量分配

  • 最大最小公平：（所有的流从零开始增长）如果分配给一个流的带宽在不减少分配给另一个流带宽的前提下无法得到进一步增长，那么就不给这个流更多带宽

  • 事实上模糊地按连接分配流量，所以电驴毒瘤

XCP(eXplicit Congestion Protocol) 路由器告诉源速率，ECN 路由器告诉源减速，其他是测量并控制

关于丢包式检测：无线链路层毫秒级重传，传输层秒级

加法递增乘法递减：

UDP

没有流量控制，差错控制或者重传；有多路复用

校验和包括的伪头如下（没有传输，算的时候按下面，实际上破坏分层）

远程过程调用（Remote Procedure Call）：不需要 Socket，客户端和服务器都有 Stub

实时传输协议 RTP（应用层上实现的传输协议）：UDP 实现（配合 RTCP 控制协议获得更多功能）

P：四字节对齐；X：扩展头；CC：有多少贡献源；M 应用解释（一般为标记开始）；Payload Type（MP3）；时间戳用于减少抖动

同步源标识符 (Synchronization source identifier) 指明了该数据包属于哪一个流

TCP

头

一个 TCP 段最多 65535-20(IP)-20(TCP) = 65495 数据

TCP 给每个字节编了址，ACK number 是下一个期待的字节（累计确认）

标志位

  • 有 ECN 时，ECE（ECN-Echo）告诉发送端网络给了 ECN；CWR（Congestion Window Reduced）表示发送端已放缓

  • URG 是否使用紧急指针，紧急指针指向数据里紧急的那个部分（实际上不怎么用）

  • PSH 刷缓冲区

  • RST 被用于突然重置一个己经变得混乱的连接，或者拒绝连接

  • SYN/ACK=1/0 表示连接请求，SYN/ACK=1/1 表示连接接受

  • FIN 挥手

校验和包括头、数据和 TCP 伪头（和 UDP 一样），校验是强制的

选项可以有的字段：

  • 最大段长 MSS

  • 窗口尺度（可以将窗口大小左移最多 14 位）

  • 时间戳（解决序号绕回）

  • SACK 已经接收到的段序号范围

连接

右：如果同时发起连接，结果是建立了一个 (x, y) 的连接

SYN 泛洪解决方法：序号加密送出去，握手回来解密拿到序号

四次挥手 SYN 和 ACK 可能在同一个包，就变成了三次

TCP 连接是十一个状态的有限状态机

滑动窗口

窗口探测：强制宣告下一个窗口大小

延迟确认：接收端最晚到缓冲区满才确认（延迟 50 ms 等搭车）

Nagle（避免发的全是小包）：发送端只发送第一次到达的数据，后面的缓冲起来（相当于停等）

Clark（低能窗口综合症，应用一次读一个，窗口就 1）：窗口更新在 空缓存\(=\min(\) 一半，最大段长 \()\) 时才发生

计时器管理

重传计时器

记录 \(SRTT\) 平滑平均往返时间：\(SRTT=\alpha SRTT+(1-\alpha)RTT\)，\(\alpha\) 典型值 \(7/8\)

\(RTTVAR\) 是上述的均方差：\(RTTVAR=\beta RTTVAR + (1-\beta)|SRTT-RTT|\) 典型值 \(3/4\)

重传超时 \(RTO=SRTT+4RTTVAR\)

第一次重传不更新估计值，接下来每一次连续重传超时加倍

持续计时器

发送端做窗口探测以免窗口更新丢了

保活计时器

连接没有活动时查看另一端是否存在（争议）

连接终止计时器

等待最大包存活时间的两倍

拥塞控制

拥塞窗口（cnwd）：任何时候发送端可以向网络发送的字节数

确认时钟：ACK 包的速率代表了这个网络上最慢的链路的速度

慢启动：拥塞窗口初始值 4 个段，每 ACK 一个发出的包增加一个段的字节量（任何时候未确认的数据包的数量就是拥塞窗口的大小）

TCP Tahoe

  • 慢启动阈值：慢启动的上限，每当检测到丢包，慢启动阈值就设为拥塞窗口的一半，慢启动超过阈值之后就到线性增加（近似每个 RTT 增加一段，针对 cwnd/MSS 中每个可能被确认的包，增加 (MSS*MSS)/cnwd）

  • 丢包：意味着拥塞窗口满，无法发包，等到重传可发再开始慢启动，阈值为拥塞窗口一半

  • 重复确认：当丢失数据包的后续数据包到达接收端时，它们触发给发送端返回确认，这些确认段携带着相同的确认号（因为是累积确认）；TCP 假设三个确认意味着丢包了（快速重传）

快速恢复（维持确认时钟避免重新慢速启动）：对重复确认计数直到网络内的数据包数量下降到新阈值，从此时往后，每接收到一个重复确认就发送一个新的数据包；一个 RTT 后丢的包被确认（就没有重复确认了），重新开始线性增加

性能问题

  • Performance problems in computer networks

  • Network performance measurement

    • 确保样值空间足够大，确保样值具有代表性，缓存可以破坏测量结果，确保测试期间不会发生不可知事情，小心使用粗粒度时钟，小心推断结果

  • System design for better performance

    • 主机速度比网络速度更重要，减少包数量来降低开销，最小化数据复制（一起实现层），带宽能买延时不行，最小化上下文切换，避免拥塞比从中恢复更好，避免超时（重复）

  • Fast TPDU processing

    • Make common cases fast; TCP/IP 相邻段一般一样（存好）；计时轮（每个槽一个 Tick，指向一个触发的计时器列表）

  • Protocols for high-speed networks

    • 序号回绕；大窗口；重传策略；延时瓶颈；简洁协议少计算

Delay Tolerant Networking

处理间歇性的连接，按消息处理，存储转发

Custodian 托管标识符（路上的节点承担照看数据安全的责任）

应用层

DNS

记录格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Domain name   Time to live    Class     Type     Value
cs.mit.edu    86400           IN        CNAME    csail.mit.edu
; Authoritative data for cs.vu.nl
cs.vu.nl      86400           IN        SOA      star boss (9527,....)
cs.vu.nl      86400           IN        MX       1 zephyr
cs.vu.nl      86400           IN        MX       2 top
cs.vu.nl      86400           IN        NS       star
star          86400           IN        A        130.37.56.205
zephyr        86400           IN        A        130.37.20.10
top           86400           IN        A        130.37.20.11
www           86400           IN        CNAME    star.cs.vu.nl
ftp           86400           IN        CNAME    zephyr.cs.vu.nl
rowboat                       IN        A        130.37.56.201
                              IN        MX       1 rowboat
                              IN        MX       2 zephyr

IN：Internet

PTR 可用于反向查找（IP 查名字）

域名解析

权威记录：管辖的服务器返回的结果（相对于缓存记录）

13 个根服务器 a.root-servers.net 到 m.root-servers.net，选播路由

递归查询：服务器全权帮你干完，给你返回最终结果

迭代查询：返回部分方案和下一个操作

Email

SMTP->SMTP->POP3/IMAP

MIME：多媒体支持

五种传输编码和一个扩充入口：文本、8 位编码、二进制文件、base64、可打印编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
From: alice@cs.washington.edu
To: bob@ee.uwa.edu.au
MIME-Version: 1.0
Message-Id: <0704760941.AA00747@cs.washington.edu>
Content-Type: multipart/alternative; boundary=qwertyuiopasdfghjklzxcvbnm
Subject: Earth orbits sun integral number of times

This is the preamble. The user agent ignores it. Have a nice day.

--qwertyuiopasdfghjklzxcvbnm
Content-Type: text/html

<p>Happy birthday to you<br>
Happy birthday to you<br>
Happy birthday dear <b> Bob </b><br> Happy birthday to you</p>

--qwertyuiopasdfghjklzxcvbnm
Content-Type: message/external-body;
    access-type="anon-ftp";
    site="bicycle.cs.washington.edu";
    directory="pub";
    name="birthday.snd"

content-type: audio/basic
content-transfer-encoding: base64
--qwertyuiopasdfghjklzxcvbnm--

SMTP (Simple Mail Transfer Protocol) 端口 25，纯 ASCII 协议，不包括认证，明文传输；4 个单词的命令（HELO, MAIL FROM, RCPT TO, DATA）

IMAP (Internet Message Access Protocol) 端口 143

POP3 (Post Office Protocol) 端口 110

WWW

URL (Uniform Resourse Locator); URI (Uniform Resourse Identifier)

Cookie 最多 4KB

动态页面

  • 公共网关接口 (CGI, Common Gateway Interface)：后端程序到 Web 服务器的接口

  • PHP <?php echo $name; ?>; JSP; ASP.NET

  • JS; VBScript

HTTP

  • HTTP1.1 持续连接（一次连接多次请求、流水请求）

  • ASCII 协议

每个响应都有状态码

消息头 (Cookie; Set-Cookie ...)

缓存

  • Check expiry

  • Conditional GET (If-Modified-Since; Etag; If-None-Match)

  • Not modified / Responce

移动 Web (XHTML)

流媒体

量化 CD: 44100 / 16 bit / 1.4 Mbps stereo

编码 AAC 96k 128kbps；

  • 波形编码：FFT 后传未被截止的频率

  • 感知编码：利用频率屏蔽

JPEG

  1. 块准备（YCbCr 三个矩阵各切成 8x8）

  2. 离散余弦变换

  3. 量化（除权值）

  4. 差分量化

  5. 行程编码（蛇皮发送顺序）

  6. 静态输出编码（霍夫曼编码）

MPEG

  • I 帧内编码

  • P 前向（I）帧

  • B 前后向（IP）帧

视频

  • 前向纠错（发校验，组播路由大家丢不一样）

  • 交替传输（一个包只传奇数帧，掉个帧罢了）

  • 缓冲

实时会议 H.323（可以电话拨入）

建立 5 条逻辑信道：呼叫信令（Q.931）；呼叫控制（H.245）；“双工”数据（两条RTP）；数据控制（RTCP）

IP 语音 SIP

Content Delivery

Zipf 分布

服务器农场（DNS/负载均衡）

Web 代理（缓存）

CDN

P2P

Overlay networks

BitTorrent

Torrent（种子）：跟踪器的名称、块清单（和哈希）

Tracker：上传下载该内容的用户列表

DHT 分布式哈希表（Cord 方案）节点保留少量其他节点信息

逻辑上 Key 是 hash(Torrent)，Value 是 IP

标识符构成一个环，有可能代表实际节点

successor(k) 是 k 之后第一个实际节点的标识符，key 和 k 在同一个空间做映射

朴素找：向 successor 发 query，沿着环走，找到了返回给请求者

指取表（倍增找）：每个节点一张，Key 是 0-(m-1)（m 是实际节点数）；标识符 k 的第 i 项是 start=(k+(1<<i))%(1<<m) 和 successor(start[i]) 的 IP

网安

密码学

密码分析学：唯密文/已知明文（有一些明文密文对）/选择明文（可以由明文生成密文）

密码编码学：努力在选择明文保持安全

\[ D_K(E_K(P))=P \]

Kerckhoff 原则：保密性仅取决于对密钥的保密，而算法是公开的。密钥作为算法参数

置换密码：做置换

替代密码：按行排，然后按列按列顺序写

一次性密钥：xor

量子密钥

密码学原则：冗余度、新鲜度

对称密钥

加密解密是一个密钥

DES

三重 DES，K1 加密 K2 解密 K1 加密

AES

密码长度和块长度 128-128 / 128-256

生成 11 个轮密钥干牛b事情

公钥算法

  • \(D(E(P))=P\)

  • 从 E 推导 D 极其困难

  • E 不会被选择明文破解

加密公钥，解密私钥

RSA

  • 选大素数 \(p\)，\(q\)

  • 计算 \(n=pq\)，\(z=(p-1)(q-1)\)

  • 找一个与 \(z\) 互质的 \(d\)

  • 找到 \(e\) 使 \(ed=1\mod z\)

加密：\(C=P^e\mod n\)，解密 \(P=C^d\mod n\)

数字签名

  • 接收方可验证

  • 发送方无法否认

  • 接收方无法编造

对称密钥：Big Brother

非对称：要求 \(E(D(P))=P\)；主要问题是 Alice 可以公开私钥

消息摘要

认证但不需要保密

SHA

MD5（8 行了）

证书

安全地分发公钥

证书证明某个公钥属于某人，这个证书附带一个签名块（证书的 SHA 被私钥签名）

X.509 证书

PKI 信任链