计算机网络

引言

互联网标准(Internet Standards)

RFC(Request for Comments)
- 这是一个在软件工程和互联网技术领域中广泛使用的文档标准
IETF(Internet Engineering Task Force)
- 互联网工程任务组，负责维护和发布 RFC 文档

网络数据概览

alt text

Delay

\[d_{nodal} =(d_{proc}) + (d_{queue}) + d_{trans} + d_{prop} \\ = N \times \frac{L}{R} + \frac{d}{s}\]

带宽时延积

带宽时延积(Bandwidth-Delay Product, BDP): 表示在网络中传输数据时，链路上可能存在的最大数据量

应用层

架构

client - server

client: initiates communication
server: waits to be contacted

peer to peer(P2P)

protocols

open protocols: HTTP, FTP, SMTP.. defined in RFC

TCP vs UDP

多数应用层协议基于 TCP

基于UDP的:DNS,DHCP,SNMP以及一些流媒体应用s

Web & HTTP

HTTP: HyperText Transfer Protocol

Port: 80(HTTP), 443(HTTPS)

URL: Uniform Resource Locator

标识互联网资源的地址

格式:

{scheme}://{hostname}/{pathname}?{query}#{fragment}

连接类型

Non-persistent

每个请求/响应对使用一个单独的TCP连接

下载一个对象的时间: $T=2RTT+文件传输时间$

Persistent

HTTP/1.1默认使用持久连接,在花费 $1RTT$ 建立连接后,之后的每次请求对象都只需要 $1RTT$

报文格式

request

GET /path/to/resource.html HTTP/1.1\r\n    <--- request line
Host: www.example.com\r\n                  <--- header begin
User-Agent: Mozilla/5.0\r\n
... 
\r\n                                       <--- 空行表示header结束

response

HTTP/1.1 200 OK\r\n                              <--- status line
Date: Mon, 27 Jul 2009 12:28:53 GMT\r\n          <--- header begin
...
Last-Modified: Wed, 21 Oct 2015 07:28:00 GMT\r\n <--重要
\r\n
<html>...</html>                                 <--- body,可以是data

status line

<HTTP-version> <status-code> <reason-phrase>

200 OK
- request succeeded, requested object later in this msg
301 Moved Permanently
- requested object moved
304 Not Modified
400 Bad Request
- request msg not understood by server
404 Not Found
- requested document not found on this server
505 HTTP Version Not Supported

Last-Modified

用于缓存验证,当本地有缓存这个资源时,client会发送If-modified-since: <date>

如果自上次访问后资源未被修改,服务器可以返回一个简短的响应,节省带宽

用于keep state, 因为http是无状态协议

mail

alt text

发送邮件

SMTP:Simple Mail Transfer Protocol

接收邮件

POP: Post Office Protocol
IMAP: Internet Message Access Protocol
HTTP: 一些现代邮箱服务使用(gmail etc.)

DNS(Domain name system)

translate hostname to IP address

DNS Tree

根域 (Root Domain) (13个根服务器)
- 顶级域 (Top-Level Domain, TLD):gTLD (通用顶级域), ccTLD(国家顶级域)
  - Authority DNS Server (权威DNS服务器)
    - 负责存储特定域名的DNS记录，并对外提供解析服务

resolution

iterated query

客户端向本地DNS服务器发送查询请求,如果本地DNS服务器没有对应的记录,它会返回下一个DNS服务器的地址,客户端继续向下一个DNS服务器发送请求,直到找到目标记录或查询失败

recursive query

本地DNS服务器代表客户端向其他DNS服务器发送查询请求,直到找到目标记录或查询失败,然后将结果返回给客户端

caching

PC & local DNS server都会缓存DNS记录,减少查询时间和网络流量,TTL(Time to live)决定过期时间

record types

RR format: (name(hostname), value, type, ttl)

A: IPv4 address
AAAA: IPv6 address
CNAME: 别名
MX: mail exchange server
NS: name server(这个域的权威DNS服务器)

protocol

ID (16b): 标识符,唯一,用于匹配请求和响应
Flags (16b): 控制标志,如查询/响应标志,客户端递归查询,服务器递归支持,是否来自权威DNS服务器
四个计数器:问题数,回答数,授权记录数,附加记录数

传输层

传输层提供进程之间的通信(网络层是主机之间的通信),通过端口标识不同的进程

Ports

端口号(port number)

标识应用层进程的数字,UDP和TCP可以分开使用同一个端口号
dist port (目的端口号,服务器进程对应的端口号)

well-known ports(0-1023]:

DNS: 53
HTTP: 80
HTTPS: 443
SSH: 22
FTP: 20/21
SMTP: 25
POP3: 110

小于1024的端口号通常只分配服务进程使用,通过这一点可以判断client-server

multiplexing and demultiplexing

多路复用和解复用

多路复用: 从多个套接字(socket)收集数据,将多个应用层数据流合并到一个传输层连接中进行传输
解复用: 将传输层连接中的数据流分离，交付给对应的应用层进程

UDP vs TCP

UDP通过(destination IP, destination port)二元组识别

TCP通过(source IP, source port, destination IP, destination port)四元组识别

其中

| source port (16 bits) | destination port (16 bits) |

是两个协议共同最前头部字段,IP地址从网络层获取

UDP(User Datagram Protocol)

特点

迅速,简单,头部开销小(64b)
unreliable: 可能丢包,乱序
connectionless: 无连接
best effort
无拥塞控制,无流量控制

Header

    |<--           32 bits           -->|
    0      7 8     15 16    23 24      31
    +--------+--------+--------+--------+
    | Source Port     | Dest Port       |
    +--------+--------+--------+--------+
    | Length          | Checksum        |
    +--------+--------+--------+--------+
    | Data ...
    +---------------- ...

checksum

用于detect errors

发送方

把数据每16位一组划分
把划分出的数字做一补加法
- 如果有进位,把进位加到结果的最低位
- 每次溢出都wrap around
对结果取反,得到checksum

接收方

把所有16bit字+checksum做一补加法,结果应该是全1,否则出错

Reliable Data Transfer

window

发送方窗口 (Sender Window)
- 发送方可以在等待确认之前发送的最大数据量

Go-Back-N (GBN)

发送方维护一个发送窗口(Sending Window)
- 发送窗口大小为N
- 发送方可以在等待确认之前发送N个分组
接收方只需要维护一个期望序号(ExpectSeqNum)
- 只接受按序到达的分组,否则丢弃
窗口滑动:任意ACK,且序列号大小>发送窗口大小

ACK: 对最后一个按序收到的分组进行确认

Selective Repeat (SR)

发送方维护一个发送窗口(Sending Window),one timer per packet
接收方接受乱序到达的分组,并缓存,对每个正确收到的分组发送ACK
窗口滑动:左侧边界ACK,且序列号大小>=发送窗口大小*2

TCP(Transmission Control Protocol)

所有会改变连接语义的事件，都必须被确认

concept

MSS (Maximum Segment Size)
- TCP数据段中包体的最大长度,三次握手时协商
Payload
- TCP数据段中包体的实际长度

Header

ACK number: 收到数据包的确认号,表示期望收到下一个数据包的序列号
SEQ number: 记录自己发送数据的序列号,序列号是在包体第一个字节的在 window 中的编号,双方的ISN(Initial Sequence Number)都被各自的SYN包消耗
SYN位: 置1为三次握手包,置0为普通数据包
ACK位: 第一个SYN包置0（确认号无效），从第二个握手开始以及后续所有TCP段中，ACK置1，表示确认号字段有效

receive window(rwnd): 通知对方自己当前的接收窗口大小,用于流量控制

 | <--                        32 bits                        --> |
 +---------------------------------------------------------------+
 |          Source Port          |       Destination Port        |
 +---------------------------------------------------------------+
 |                        Sequence Number                        |
 +---------------------------------------------------------------+
 |                    Acknowledgment Number                      |
 +---------------------------------------------------------------+
 | head |Rese-|     |U|A|P|R|S|F|                                |
 | len  |rved|Flags |R|C|S|S|Y|I|        receive window          |
 +---------------------------------------------------------------+
 |       Checksum                |     Urgent Pointer            |
 +---------------------------------------------------------------+
 |                    Options (if any)                           |
 +---------------------------------------------------------------+
 |                             Data                              |
 +---------------------------------------------------------------+

Timeout and Retransmission

TCP使用自适应定时器,根据往返时间RTT动态调整超时时间

重传主要由两个机制触发:

RTO (Retransmission TimeOut): 如果在超时时间内没有收到确认,重传数据包
fast retransmit: 如果收到三个重复的ACK,说明该数据已经丢失,立刻重传(多个包丢失只能触发一次)

connnetion

三次握手(Three-way Handshake)

客户端发送一个SYN包,选择一个初始序列号ISNc
服务器收到SYN包后,回复一个SYN-ACK包,确认号为ISNc+1(SYN消耗数据),并选择自己的初始序列号ISNs
客户端收到SYN-ACK包后,回复一个ACK包,确认号为ISNs+1,连接建立

1-2是一个RTT,3通常随请求数据一起发送,故HTTP下载单对象需要2RTT建立连接

四次挥手(Four-way Handshake)

客户端发送 FIN=1，进入 FIN_WAIT_1
服务器收到 FIN，发送 ACK，进入 CLOSE_WAIT；客户端收到 ACK，进入 FIN_WAIT_2
服务器发送自己的 FIN=1，进入 LAST_ACK(收到 ACK 后进入 CLOSED)
客户端收到 FIN，发送 ACK，进入 TIME_WAIT
- TIME_WAIT: 客户端等待 $2 \times MSL$ (最大报文段寿命) 后才真正进入 CLOSED，以确保 ACK 能到达服务器

1-4都在一个RTT内完成

Flow Control

$\text{Throughput} = \frac{\text{send\_window}}{\text{RTT}}$ $\text{send\_window = min(cwnd, rwnd)}$

Congestion Control

cwnd的含义: 发送方认为网络当前可承受的最大未确认数据量

注意,拥塞控制只在发送方进行

Slow Start

初始时,拥塞窗口cwnd设为1 MSS
每经过一个RTT,cwnd加倍(每收到一个ACK,cwnd+1)

Congestion Avoidance

当cwnd >= ssthresh时,进入拥塞避免阶段,每经过一个RTT,cwnd增加1 MSS(线性增加)

ssthresh=丢包时cwnd的一半

Detecting Loss

Timeout

超时丢包

ssthresh = cwnd/2
cwnd = 1 MSS

重新进入slow start

Triple Duplicate ACKs

收到3个重复ACK

ssthresh = cwnd/2
cwnd
- Tacho 算法: cwnd = 1 MSS
- Reno 算法: cwnd = ssthresh (fast recovery)

网络层

router

input port: 处理物理链路和数据链路层,提取IP包,进行查表转发
switching fabric: 在输入端口和输出端口之间传输包
output port: 处理排队和链路层封装,将包发送到物理链路
routing processor: 计算路由表,维护路由协议,通常由软件实现,负责control plane功能

IP(Internet Protocol)

protocols

header

Version (4b): IP协议版本号,IPv4为4,IPv6为6
TTL (Time to Live) (8b): 数据包在网络中可以经过的最大跳数,每经过一个路由器减1,为0时丢弃
identifier (16b): 标识符,用于唯一标识一个IP数据包,用于分片和重组
Flag:
- MF(More Fragments): 1表示后面还有片段,0表示最后一个片段
- DF(Don’t Fragment): 1表示不允许切片,0表示允许切片
Offset:
- 片段偏移量,表示该片段在原始数据包中的位置(不含包头),单位为8字节,同时约束了片段的大小必须是8的倍数(除了最后一个片段)
- 所以本片段的第一个字节在原始数据包中的位置为: Offset * 8(0开始)

IP层切片

MTU(Maximum Transmission Unit)
- 最大传输单元,链路层能够传输的最大数据包大小
切片(fragmentation)
- 当IP数据包的大小超过MTU时,路由器将数据包切分成多个片段进行传输
- 每个片段都有自己的IP头,但共享相同的标识符(identifier)
重组(reassembly)
- 接收方(主机)根据每个片段的标识符和偏移量,将切片重新组装成完整的数据包

DHCP(Dynamic Host Configuration Protocol)

动态主机配置协议(包含IP及其他配置信息)

配置步骤:

DHCP Discover (广播)
DHCP Offer (服务器响应)
DHCP Request (广播)
DHCP Ack (服务器响应)

ICANN(Internet Corporation for Assigned Names and Numbers)
- 负责全球IP地址分配和管理的非营利组织

address

广播地址 (Broadcast Address) 最大
- 用于向同一子网内的所有主机发送数据包(在链路层广播)
- 主机号全为1
- 对于255.255.255.255: 用于本地网络广播,不能路由
网络地址 (Network Address) 最小
- 用于标识一个子网
- 主机号全为0

subnet mask (子网掩码)

用于区分网络号和主机号,前缀部分全为1,主机部分全为0
与IP地址进行按位与运算,得到网络号
CIDR(Classless Inter-Domain Routing)表示法: /n 表示子网掩码中有n个连续的1

ABCDE分类

类别	二进制前缀	地址范围
A 类	0xxxxxxx	1.0.0.0 ~ 126.255.255.255
B 类	10xxxxxx	128.0.0.0 ~ 191.255.255.255
C 类	110xxxxx	192.0.0.0 ~ 223.255.255.255
D 类	1110xxxx	224.0.0.0 ~ 239.255.255.255
E 类	1111xxxx	240.0.0.0 ~ 255.255.255.255

子网划分

子网只能是2的幂次方个

从大到小排序
大的找最近的$2^k$,使得$2^k \geq$所需主机数+2(网络地址和广播地址),分配$k$位给主机号
相当于网络号加一位(倒数第k+1位为0的已经被划走了),重复上一个过程

NAT(Network Address Translation)

出站数据包

把(source IP, source port)映射为(NAT 公网 IP, 新端口)

维护NAT表

包括(内部IP, 内部端口, 外部IP, 外部端口)的映射关系

入站数据包

根据(NAT 公网 IP, 端口)查找NAT表,映射回(内部IP, 内部端口)

内网地址端:

192.168.x.x
10.x.x.x
172.16.x.x ~ 172.31.x.x

画NAT表

LAN IP	LAN 端口	WAN IP	WAN 端口
内部IP	内部端口	外部IP	外部端口

IPv6

地址长度: 128b
format: 8组每组4个16进制数,组间用:分隔

features (compare to IPv4)

固定报头长度(40Bytes)
- 扩展信息在扩展报头,通过next header字段链接
取消了checksum字段
只允许主机分片,路由器超大就丢弃

共存方案

双栈（Dual Stack）
- 主机同时支持IPv4和IPv6协议栈，根据目的地址选择使用哪种协议进行通信
隧道（Tunneling）
- 在IPv4网络中封装IPv6数据包，使其能够通过IPv4网络传输

网络层-control plane

Routing Protocols

Link State

朴素Dijkstra算法

维护

N′：已经确定最短路径的节点集合
D(v)：从源节点 s 到节点 v 的当前最短距离估计
NextHop(v)：从 s 到 v 的当前最短路径上的下一个节点

初始化

N′ = {s}
D(s) = 0
D(v) = ∞
NextHop(v) = v

算法步骤（重复执行）

从 所有不在 N′ 中的节点里，选择一个节点 w，使得 D(w) 最小
将 w 加入集合 N′
对于 w 的每个邻居 v 不在 N′ 中，执行松弛操作: $D(v) = min(D(v), D(w) + c(w, v))$
如果更新了 D(v)，则更新 NextHop(v) 为 NextHop(w)
重复步骤 1-3，直到所有节点都在 N′ 中,收敛

Distance Vector

分布式Bellman-Ford算法

维护

vertex	D(v)	NextHop(v)
(示例) A	0	A

初始化

每个节点根据自己的邻居初始化路由表(初始只有邻居)

算法步骤

每个节点周期性地将自己的路由表发送给所有邻居
当节点 u 收到邻居 w 的路由表时,对每个目的节点 v 执行松弛操作: $D(v) = min(D(v), c(u, w) + D_w(v))$
如果更新了 D(v)，则更新 NextHop(v) 为 w
重复步骤 1-2，直到路由表不再变化,收敛(轮数 ≈ 网络直径)

poisoned reverse

用于防止路由环路

如果节点 u 通过邻居 w 到达目的节点 v，则在发送给 w 的路由表中，将 D(v) 设置为无穷大

5.3-5.4 路由协议

IGP(Interior Gateway Protocol)
- 用于同一自治系统内的路由选择和信息交换
- 主要找最短路径,30s更新一次
- OSPF(Open Shortest Path First)
  - 基于链路状态算法(LS)的路由协议
  - 数据包封装在IP中,在网络层封装
  - router flooding (路由器泛洪): 每个路由器将其链路状态信息发送给相邻的路由器,然后这些路由器如果更新了自己的链路数据库就会再将信息转发给它们的邻居,直到整个自治系统内的所有路由器都收到该信息
  - 层次结构: 将自治系统划分为多个区域(Area),每个区域内使用LS算法,区域之间使用ABR(Area Border Router)进行连接
- RIP(Routing Information Protocol)
  - 邻居交换路由表,基于距离向量算法(DV)
  - 数据包封装在UDP中
BGP(Border Gateway Protocol)
- 用于不同自治系统之间的路由选择和信息交换
- 主要基于策略

其他

SDN

见上

ICMP

网络层协议,把“网络事件”封装成控制报文，通过 IP 原路送回源主机,为 IP 层提供差错报告、状态反馈和网络诊断能力

例如:

路由器发现 TTL 减到 0
路由表找不到目的网络

应用场景

ping
traceroute

SNMP(Simple Network Management Protocol)

简单网络管理协议

链路层

EDC(Error Detection and Correction)

Single Bit Parity

偶校验：使得数据加上校验位后，整体包含的“1”的个数为偶数
奇校验：使得整体“1”的个数为奇数

checksum

发送方: 把数据每16位一组划分,把划分出的数字做一补加法,如果有进位,把进位加到结果的最低位,每次溢出都wrap around,对结果取反,得到checksum
接收方: 把所有16bit字+checksum做一补加法,结果应为全1

CRC(Cyclic Redundancy Check)

计算生成多项式

多项式中指数为k的项存在,则第k位为1,否则为0

例如:$G(x)=x^4+x^3+1$对应二进制11001

原始数据补0

在数据后面补上 r 个0 , r 为生成多项式的最高次数(=位数-1)

原始数据:     10110011
补 4 个 0:    10110011  0000

模二除法

用生成多项式对补0后的数据进行模二除法,得到余数R

101100110000 ÷ 11001

模二除法:

减法就是异或运算
如果被除数当前的最高位是1,就用生成多项式去除商1,否则向右移一位商0

最后得到的余数R就是CRC码

把CRC码附加到原始数据后面

10110011  0100

接收方难道对这整个数做模二除法,如果余数为0则无错,否则出错

多路访问协议 (Multiple Access Protocols)

防止不同的节点同时发送数据包导致碰撞(collision)

分类:

channel partitioning (信道划分) : 适合大量节点持续发送
- TDMA (Time Division Multiple Access,时分多路)
- FDMA (Frequency Division Multiple Access,频分多路)
random access (随机接入)
- Slotted ALOHA & (pure) ALOHA
  区别: Pure ALOHA 随到随发、只要重叠就冲突；Slotted ALOHA 强制对齐到时隙，只在同一时隙才会冲突，因此把冲突概率减半、吞吐量翻倍
- CSMA (Carrier Sense Multiple Access)
  监听信道,有信号则等待,无信号则发送
  - CSMA/CD (Collision Detection)
    遇到碰撞就停止发送
    以太网CSMA/CD算法:
    - 网卡准备数据,封帧
    - 监听信道,若空闲则发送,否则等待
    - 发送过程中监听信道,若检测到碰撞,则立即停止发送,并发送jam signal(48b)通知其他节点
    - 放弃掉当前数据包,两个起冲突的网卡进入二进制指数退避(binary [exponential] backoff)
  - CSMA/CA

binary exponential backoff

定义参数$k$,$k=\min(n,10)$,$n$为冲突次数
在$[0,2^k-1]$中随机选择一个整数 r
等待 r 个时隙(slot)重传,每个时隙时间为512bit/bit rate

ARP(Address Resolution Protocol)

IP地址到MAC地址的映射

MAC

硬件地址,链路层地址
长度: 48b
FF:FF:FF:FF:FF:FF 广播地址

ARP表

IP Address	MAC Address	TTL
(示例) 192.168.0.2	aa:bb:cc:dd:ee:ff	20 s

ARP请求与响应

查表
广播query
单播response
缓存（Caching）

跨网段通信

目标IP不在本地子网内,发送给默认网关(router)
发送ARP请求给默认网关,获取其MAC地址

最后发送的请求是(destination IP, gateway MAC)

链路层的 MAC 地址只负责“这一跳”的传输, 数据包每经过一个路由器，源 MAC 和目的 MAC 都会改变，但源 IP 和目的 IP 通常保持不变(除非遇到 NAT)

引言

互联网标准(Internet Standards)

网络数据概览

Delay

带宽时延积

应用层

架构

client - server

peer to peer(P2P)

protocols

TCP vs UDP

Web & HTTP

URL: Uniform Resource Locator

连接类型

Non-persistent

Persistent

报文格式

request

response

status line

Last-Modified

cookie

mail

发送邮件

接收邮件

DNS(Domain name system)

DNS Tree

resolution

iterated query

recursive query

caching

record types

protocol

Header

传输层

Ports

multiplexing and demultiplexing

多路复用和解复用

UDP vs TCP

UDP(User Datagram Protocol)

特点

Header

checksum

发送方

接收方

Reliable Data Transfer

window

Go-Back-N (GBN)

Selective Repeat (SR)

TCP(Transmission Control Protocol)

concept

Header

Timeout and Retransmission

connnetion

三次握手(Three-way Handshake)

四次挥手(Four-way Handshake)

Flow Control

Congestion Control

Slow Start

Congestion Avoidance

Detecting Loss

Timeout

Triple Duplicate ACKs

网络层

router

IP(Internet Protocol)

protocols

header

IP层切片

DHCP(Dynamic Host Configuration Protocol)

address

subnet mask (子网掩码)

ABCDE分类

子网划分

NAT(Network Address Translation)

内网地址端:

画NAT表

IPv6

features (compare to IPv4)

共存方案