计算机网络和因特网

网络基础

  • 数据分段：将数据分成固定大小的分段，每个分段加上首部称为分组
  • 分组交换机
    • 链路层交换机（link-layer switch, switch）：接入网
    • 路由器（router）：网络核心
  • 因特网工程任务组（Internet Engineering Task Force, IETF）：制定因特网标准
    • 标准文档：RFC（Request for Comments）

网络边缘

  • 主机（host）：主机=端系统
    • 客户端（client）：请求服务
    • 服务器（server）：提供服务

接入网

家庭接入

  • 数字用户线（Digital Subscriber Line，DSL）：通过电话线与电话公司的中心局相连
    • 家庭中的DSL调解调制器将设备的数字信号转化为模拟信号（高频音，共享线路）
    • 中心局接入复用器（DSLAM）将模拟信号转化为数字信号
  • 电缆接入（cable Internet modem）：通过有线电视公司的有线电视网络共享线路
    • 混合光纤同轴电缆（Hybrid Fiber Coax, HFC）：光纤到地区枢纽，有线电视到户
    • 有线电视调制解调器将设备的数字信号转化为模拟信号
    • 电缆调制解调器（CMTS）将模拟信号转化为数字信号
  • 光纤到户（Fiber TO The Home，FTTH）：本地中心局光纤接入用户家中的光纤接入网
    • 有源光纤网络（Active Optical Network，AON）：每个用户有一个光接口
    • 无源光纤网络（Passive Optical Network，PON）：多个用户共享一个光接口
      • 家庭光纤网络端接器（Optical NetWork Terminator，ONT）：连接到附近的光纤分配器（splitter）
      • 光纤线路端接器（OLT）：光信号和电信号转换

企业接入

  • 以太网：局域网（LAN）接入
  • Wi-Fi：无线局域网（WLAN）接入

广域无线接入

  • 蜂窝网络（cellular network）：无线接入

物理媒介

  • 导引型媒介（固体）：双绞线、同轴电缆、光纤
  • 无导引型媒介（空气和外层空间）：无线电波

双绞铜线

  • 便宜常用
  • 无屏蔽双绞线（Unshielded Twisted Pair, UTP）：四对绝缘铜线
  • 电话网

同轴电缆

  • 电视有线

光纤

  • 高带宽、低延迟、抗干扰
  • 高成本

陆地无线电信道

  • 短距离
  • 局域
  • 广域

卫星无线电信道

  • 同步卫星：距离远，时延大
  • 近地轨道卫星：距离近，时延小，但由于不是固定的，需要部署多颗卫星

分组交换

  • 端到端时延：$d_{end-end}=N\frac{L}{R}$，存储转发情况下，在有$N$条速率为$R$链路组成的路径上传输$1$个大小为$L$的分组的时延

电路交换

  • FDM（Frequency-Division Multiplexing）：频分复用，频段宽度称为带宽，TDM（Time-Division Multiplexing）：时分复用，时段被划分为帧，每个帧被划分为固定数量的时隙
  • 同时活跃的用户数量少，分组交换优于电路交换

网络结构

  • 互联网服务提供商（Internet Service Provider, ISP）
    • 第一层ISP：必须全部互联
    • 区域ISP：连接到第一层ISP
    • 接入ISP：家庭、企业
    • 多宿（multi-home）：非顶层ISP连接多个ISP
    • 互联网交换点（IXP）：多个ISP在此交换流量（对等）
    • 内容提供商（Content Provider NetWork）：仅承载内容提供商自身的流量

分组交换网络的评估

时延

类型：

  • 处理时延（$d_{proc}$）：检查首部、决定分组的输出端口，微秒级
  • 排队时延（$d_{queue}$）：分组在队列中等待传输，毫秒到微秒级
  • 传输时延（$d_{trans}$）：路由器向链路推出分组，毫秒到微秒级
  • 传播时延（$d_{prop}$）：分组在链路上传播，毫秒级

总时延：$d_{end-end}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$

令$a$表示分组到达队列的平均速率（分组/秒，pkt/s）,$R$为传输速率（bps），分组大小为$L$bit且假设路由器队列的容量无限

流量强度：$\frac{La}{R}$，必须小于1，否则会导致无限制的排队时延，与平均排队时延成近似平方关系

从源主机到目的主机之间有$N-1$台路由器（$N$条链路），忽略排队时延情况下的总时延：
$d_{end-end}=N(d_{proc}+d_{tr}+d_{prop})$

吞吐量

  • 瞬时吞吐量和平均吞吐量
  • 瓶颈链路
  • 限制通常是接入网

协议分层

  • 应用层：HTTP、SMTP、FTP
  • 传输层：TCP、UDP
  • 网络层：IP
  • 链路层：以太网
  • 物理层：双绞线、光纤

应用层

应用体系结构

客户端-服务器体系结构：客户端向服务器请求服务，服务器向客户端提供服务

P2P体系结构：对等体系结构，对等方既是客户端也是服务器

进程通信

套接字（socket）：进程间通信的端点，也称为应用程序接口（API），端口用于标识进程

HTTP

Web页面：HTML文件、对象（图片、视频、音频）
客户端：Web浏览器
服务端：Web服务器

  • TCP连接：HTTP使用TCP连接，每个HTTP报文都通过一个单独的TCP连接发送
  • 无状态：HTTP是无状态协议，服务器不保留客户端的任何状态信息
  • 非持续连接：每个对象都需要一个新的TCP连接
  • 持续连接：多个对象可以通过一个TCP连接发送
    • 非流水线：一个请求的响应返回后再发送下一个请求
    • 流水线：多个请求可以并行发送，但是响应必须按照请求的顺序返回

往返时间（RTT）：从发送方发送数据到接收方确认收到数据的时间
HTTP的TCP连接建立时间：$2\times RTT$，其中三次握手花费$1.5\times RTT$

持续连接的HTTP请求时间：$2\times RTT+传输时间$

HTTP报文格式

首部行和实体主体之间有一个空行

请求报文

  • 请求行：
    • 方法字段：GET、POST、HEAD
    • URL
    • HTTP版本
  • 首部行：键值对
    • Host：服务器主机名
    • Connection：持续连接
    • User-Agent：浏览器信息
    • Accept-Language：接受的语言
  • 实体主体：请求的数据

响应报文

  • 状态行：
    • HTTP版本
    • 状态码：200 OK、404 Not Found
    • 状态码原因短语
  • 首部行：键值对
    • Connection：持续连接
    • Date：响应时间
    • Server：服务器信息
    • Last-Modified：最后修改时间
    • Content-Length：实体主体长度
    • Content-Type：实体主体类型
  • 实体主体：响应的数据

cookie：服务器向客户端发送的数据，客户端保存，下次请求时发送给服务器

  • 对应首部行：Set-Cookie，Cookie
  • 会话cookie：浏览器关闭后失效
  • 持久cookie：指定过期时间
  • 第三方cookie：第三方网站的cookie

Web缓存（Web cache）：代理服务器（proxy server）既是服务器又是客户，缓存Web页面，减少响应时间

  • 现实命中率一般在$0.2$到$0.7$之间

条件GET方法：首部行中包含If-modified-since，未过期时响应报文实体为空

HTTP2

优化

  • 队首（Head of Line，HOL）阻塞：一个对于大容量对象请求的延迟会影响其他请求
  • HTTP/2成帧：将每个HTTP对象分成多个帧，交错发送。优先次序帧优先发送（权值1-256）
  • 服务器推：服务器可以在客户端请求之前推送对象，对一个请求发送多个响应

HTTP3

  • 使用QUIC协议，基于UDP
  • 低延迟连接建立：0-RTT连接建立
  • 报文复用：多个HTTP请求可以在一个连接上并行发送

FTP

  • 文件传输协议The File Transfer Protocol，控制端口21，数据传输端口20
  • 每次传输一个文件后关闭文件传输，保持状态（当前文件夹、权限）
  • Passive模式：客户端打开$N>1023$和$N+1$作为控制端口和数据传输端口，向服务器端口$21$请求数据传输端口，服务器返回$P>1023$作为数据传输端口

DNS

主机表示方法：IP地址、域名

DNS（Domain Name System）：域名系统，将域名映射到IP地址

  • 分层的DNS服务器实现的分布式数据库
  • 查询分布式数据库的应用层协议
  • 运行在UDP上，端口53
  • 提供服务
    • 主机别名：获取规范主机名和IP地址
    • 邮件服务器别名
    • 负载均衡：将多个IP地址映射到一个域名，通过循环返回不同的IP地址

DNS服务器：递归查询、迭代查询

  • 根DNS服务器：顶层域名服务器
  • 顶级域名（TLD）服务器：com、org、net、edu、cn
  • 权威DNS服务器：负责一个特定域名的IP地址映射
  • DNS缓存服务器：缓存查询结果

DNS记录：域名、类型、值、TTL（Time To Live）
类型：

  • A：主机地址
  • NS：域名服务器
  • CNAME：规范名字
  • MX：邮件服务器
  • AAAA：IPv6地址

P2P文件分发

中心化架构Napster

  • 单点故障
  • 性能瓶颈
  • 版权问题

纯P2P架构

  • 无服务器
  • 端到端通讯
  • 间断连接、IP地址改变

Gnutella协议

  • flooding：向所有邻居发送递归查询
  • 使用HTTP协议用于文件传输

无结构P2P

  • 搜索：广播、随机游走
  • 缓存

有结构P2P

  • 特定节点维护网络拓扑
  • 分布式哈希表（DHT API）
    • 每个节点运行DHT应用，维护一个哈希表
    • 通过哈希函数将文件名映射到节点
    • 算法：Chord
      • 固定大小表示空间，$2^m$，$m$为哈希值的位数
      • 每个节点和键通过哈希函数映射到ID
      • 一致性哈希：环形结构，每个节点负责一个区间
      • 查找：顺时针查找最近的节点，编号为$s$的节点第$i$个邻居为$s+2^i \mod ID space$

分发时间：$F/u_s$，$F$为文件大小，$u_s$为服务器上传速率
有$N$个对等方，每个对等方下载速率为$d_i$，上传速率为$u_i$，服务器上传速率为$u_s$，文件大小为$F$

客户-服务器体系
$D_{cs}\ge \max{\frac{NF}{u_s}, \frac{F}{d_{min}}}$

P2P体系
$D_{p2p}\ge \max{\frac{F}{u_s}, \frac{F}{d_{min}}, \frac{NF}{u_{s}+\sum\limits_{i=1}^{N}u_i}}$

BitTorrent

  • 一种P2P文件分发协议
  • 洪流：参与一个特定文件分发的所有对等方，彼此交换文件块
  • 追踪器（tracker）：维护所有洪流的对等方列表
  • 最稀缺优先：优先下载最少的对等方拥有的文件块

DASH

HTTP的动态适应流（Dynamic Adaptive Streaming over HTTP）

  • 根据网络状况选择不同的码率
  • 告示文件：描述视频的码率、分辨率、时长等信息，供客户端选择下一个要下载的块

内容分发网络（CDN）

解决的问题：跨越多个ISP的延迟、发送重复的内容、单点故障
专用CDN：内容提供商自己的CDN
第三方CDN：多个内容提供商共享CDN

操作：

  1. 第一次DNS请求返回CDN的主机名
  2. 第二次DNS请求返回CDN的IP地址
  3. HTTP GET请求CDN的内容

运输层

提供服务

  • 多路分解：将运输层报文段中的数据交付到正确的套接字\
  • 多路复用：从套接字中收集数据，封装首部形成报文段并传递给网络层

UDP

报文结构

  • 首部：
    • 源端口
    • 目的端口
    • 长度：首部+数据
    • 检验和：对于所有的16位字求和（溢出回卷）后取反，端到端检测
  • 数据：应用层数据

可靠数据传输

假设发送的包按序到达

rdt1.0

假设不会出错，不会丢包
发送端仅发送数据，接收端仅接收数据

rdt2.0

自动重传请求（Automatic Repeat reQuest，ARQ）：接收端发送ACK，发送端等待ACK

  • 差错检测
  • 接收方反馈
  • 重传

假设出错，不会丢包
发送端依靠接收端的ACK和NAK，接收端依靠发送端的重传
无法解决受损ACK

解决方案：加入序号（01），发送端重传未收到的包，接收端重复接收的包

  • rdt2.1：接收端发送NAK0或NAK1，发送端重传未收到的包
  • rdt2.2：接收端发送ACK0或ACK1，发送端重传未收到的包

rdt3.0

假设出错，可能丢包
加入了超时重传机制，发送端发送包后等待ACK并启动定时器，超时后重传

流水线协议

rdt协议的效率问题：发送方每次发送一个分组，接收方每次接收一个分组

发送方利用率：$U_{sender}=\frac{发送方传输时间}{总发送时间}$

流水线技术：发送方发送多个分组，接收方接收多个分组

  • 增加序号范围
  • 发送方和接收方缓存多个分组
  • 处理异常分组

基本方法

  • 回退N步（GBN）：维护一个大小为$N$的窗口
    • 基序号（base）：第一个未确认的分组
    • 下一个发送的分组序号（nextseqnum）
    • 丢弃失序分组
    • 采用累积确认：接收方正确接收了所有小于等于确认号的分组
    • 发送方维护一个定时器，超时后重传窗口内的所有分组
  • 选择重传（SR）：维护两个大小为$N$的窗口
    • 发送方窗口
      • 第一个已发送但未确认分组序号（send_base）
      • 下一个发送的分组序号（nextseqnum）
    • 接收方窗口
      • 第一个期望接收的分组序号（rcv_base）
    • 超时重传引起超时的分组
    • 有限序号：窗口必须小于等于序号的一半

TCP

只在发送方和接收方之间的连接上运行，不在路由器上运行

报文段结构

  • 首部：
    • 源端口
    • 目的端口
    • 序号：字节流中的第一个字节的序号
    • 确认号：期望接收的下一个字节的序号
    • 首部长度：4位，最大60字节
    • 标志位：SYN、ACK、FIN、RST、PSH、URG
    • 接收窗口：接收方的缓存大小
    • 检验和
    • 紧急指针：紧急数据的末尾
    • 选项：最大报文段长度（MSS，通常由最大链路层帧长度（MTU）确认）、窗口缩放、时间戳
  • 数据

往返时间估计：$RTT_{est}=\alpha \cdot RTT_{est}+(1-\alpha)\cdot RTT_{sample}$，$\alpha=0.125$

RTT偏差估计：$RTT_{dev}=(1-\beta)\cdot RTT_{dev}+\beta\cdot |RTT_{sample}-RTT_{est}|$，$\beta=0.25$

超时计算：$Timeout=RTT_{est}+4\cdot RTT_{dev}$

  • 超时间隔加倍
  • 快速重传：接收方收到失序分组后立即发送ACK
  • 类似GBN，但是仅重传丢失的分组
  • 流量控制：接收方发送窗口大小，发送方根据窗口大小发送数据

连接：三次握手

  • 客户端发送SYN报文，序号为$x$
  • 服务器发送SYN+ACK报文，序号为$y$，确认号为$x+1$
  • 客户端发送ACK报文，确认号为$y+1$

断开：四次挥手

  • 客户端发送FIN报文，序号为$x$
  • 服务器发送ACK报文，确认号为$x+1$
  • 服务器发送FIN报文，序号为$y$
  • 客户端发送ACK报文，确认号为$y+1$
  • 客户端等待2MSL（最长报文段寿命）后关闭连接

拥塞控制

端到端

  • 慢启动
    • 窗口大小为$1MSS$，每首次收到ACK，窗口大小加倍
    • 结束
      • 超时：重设窗口大小为$1MSS$，并记录$ssthresh$（慢启动阈值）为$cwnd/2$
      • 当$cwnd\ge ssthresh$时，进入拥塞避免
      • 检测到三个重复ACK时，记录$ssthresh$为$cwnd/2$，设置窗口大小为$ssthresh+3MSS$，重传丢失的分组并进入快速恢复模式
  • 拥塞避免
    • 每个$RTT$，窗口大小增加$1MSS$，具体做法是每次遇到新的ACK就将$cwnd$增加$\frac{MSS}{cwnd}MSS$
    • 结束：除了$cwnd\ge ssthresh$的情况和慢启动一样
  • 快速恢复
    • 每次收到重复的ACK，$cwnd$增加$1MSS$并重传丢失的分组
    • 结束
      • 超时：操作和慢启动一样，并进入慢启动
      • 丢失的分组被成功接收：$cwnd=ssthresh$，并进入拥塞避免

TCP Tahoe不包含快速恢复，TCP Reno包含快速恢复

TCP CUBIC：拥塞避免阶段，窗口大小随时间变化，$W(t)=C(t-K)^3+W_{max}$，$C$为常数，$K$为时间常数

TCP的传输速率：$\big\lbrack\frac{W}{2RTT},\frac{W}{RTT}\big\rbrack$，$W$为窗口大小

一条TCP连接的平均吞吐量：$T=\frac{3}{4}\frac{W}{RTT}$，$W$为窗口大小

网络辅助

  1. 明确拥塞通告（Explicit Congestiong, Notification，ECN）：显式拥塞通知，路由器向发送方发送拥塞通知（TCP、DCCP）
  2. 基于时延的拥塞控制：路由器根据时延调整窗口大小（TCP Vegas），未拥塞吞吐量$cwnd/RTT_{min}$

网络层

数据平面

链路层交换机：基于链路层中的目的地址转发数据
路由器：基于网络层数据报首部转发数据

转发表

  • 目的地址范围
  • 链路接口
  • 最长前缀匹配

交换技术

  • 内存交换
  • 总线交换
  • 互联网络交换

排队

  1. 输入排队：HOL阻塞
  2. 输出排队：必须丢弃分组，解决方案是填满之前丢弃分组或添加拥塞标记

缓存并不是越大越好，缓存过大会导致缓存膨胀，导致更多的分组丢失
合适缓存大小：$B=RTT\cdot C/\sqrt N$，$C$为链路容量，$N$为TCP连接数

分组调度

  1. 先进先出（FIFO）
  2. 优先级调度：高优先级分组优先
  3. 循环（加权）调度：每个队列（按照队列长度）轮流发送一个分组

IPV4

数据报格式

  • 版本
  • 首部长度：确定IP数据报的载荷
  • 服务类型：优先级、延迟、吞吐量、可靠性
  • 数据报长度：总长度=首部+数据
  • 标识、标志、片偏移：分片
  • 生存时间：TTL，路由器减1，为0时丢弃
  • 协议：到达目的地后交付的协议
  • 首部校验和：检验IP首部
  • 源地址、目的地址
  • 选项：时间戳、记录路由
  • 数据：上层数据

IPV4地址：32位，分为网络号和主机号
子网掩码：确定网络号和主机号的位数
子网：隔离的网络

255.255.255.255为广播地址

互联网地址分配策略：CIDR（无类域间路由选择），将IP地址分为网络号和主机号
之前采用的是分类地址，网络部分的地址长度被固定为8、16、24位

组织获取地址的方式：ICANN（Internet Corporation for Assigned Names and Numbers）

主机获取地址

  • 主动配置
  • 动态主机配置协议（Dynamic Host Configuration Protocol，DHCP）：每次连接到网络时获取IP地址
    • 获取子网掩码
    • 获取默认网关地址（第一跳路由器）
    • 获取DNS服务器地址
    • 报文格式：发现、提供、请求、确认

网络地址转换（NAT）

原因：IP地址不足
解决方案：内部网络使用私有地址，外部网络使用公有地址，路由器使用NAT转换表转换地址

地址空间：10.0.0.0/8

IPV6

IPV4地址耗尽，采用128位地址
数据报格式

  • 版本
  • 流量类型：与服务类型类似
  • 流标签：标识特殊流
  • 有效载荷长度：数据长度
  • 下一个首部：上层协议
  • 跳限制：TTL
  • 源地址、目的地址
  • 数据

与IPV4的不同

  • 取消了首部校验和，由运输层和链路层负责
  • 取消了分片，超过MTU的数据报被丢弃并告知发送方，发送方减小分片大小
  • 选项：通过下一个首部扩展

与IPV4兼容：隧道技术，将IPV6数据报封装在IPV4数据报中

控制平面

路由选择算法

链路状态（LS）算法：使用Dijsktra算法，每个节点维护链路状态数据库，每个节点向所有邻居发送链路状态信息，会产生振荡的问题

距离向量（DV）算法：使用Bellman-Ford算法，每个节点维护距离向量表，每个节点向邻居发送距离向量，会因为选择环路而产生计数到无穷的问题，通过毒性逆转一部分解决

自治系统（Autonomous System，AS）：一组处于相同管理下的路由器

开放最短路优先（Open Shortest Path First，OSPF）：链路状态算法，每个AS内部使用，每个路由器维护链路状态数据库，每个路由器向AS内所有路由器广播链路状态信息

边界网关协议（Border Gateway Protocol，BGP）：距离向量算法，每个AS之间使用，每个AS维护距离向量表，每个AS向相邻AS发送距离向量

  • BGP中分组是路由到CIDR化的前缀（x:138.16.68/22, I:接口号)
  • 网关路由器：连接两个AS的路由器
  • 内部BGP（iBGP）：AS内部使用
  • 外部BGP（eBGP）：AS之间使用
  • BGP路由表：AS路径、下一跳、目的地前缀
  • 路由选择
    • 热土豆路由：最快离开AS
    • 实际选择
      • 本地偏好
      • 最短AS路径（跨越最少AS）
      • 最快离开AS
  • 实现IP任播：多个服务器拥有相同的IP地址，接收方选择最近的服务器

软件定义网络（SDN）

  • 基于流转发
  • 控制平面和数据平面分离
  • 网络控制功能
  • 可编程网络

OpenFlow协议：控制器向交换机发送流表，交换机根据流表转发数据

  • 运行在TCP上，端口6633
  • 报文格式：控制器向交换机发送控制消息，交换机向控制器发送状态消息
    • 控制器向交换机
      • 查询交换机配置
      • 修改交换机状态
      • 读状态
      • 发送分组
    • 交换机向控制器
      • 删除流表项
      • 通知端口状态变化
      • 无法处理的分组

ICMP

因特网控制报文协议（Internet Control Message Protocol）：用于主机和路由器间的网络故障诊断和报告，承载在IP数据报中，IP首部的协议字段为1

ICMP报文

  • 类型：回显请求、回显应答、目的不可达、超时、路由器通告
  • 编码：具体信息

链路层和局域网

链路层提供服务

  • 封装数据报为帧
  • 链路接入
  • 可靠交付
  • 差错检测和纠正

在网络适配器上实现

差错检测和纠正

奇偶校验

  • 一维奇偶校验：添加一个比特，使得整个数据报的1的个数为偶数（偶校验）或奇数（奇校验）
  • 二维奇偶校验：行和列

循环冗余校验（CRC）

也称为多项式编码，将数据看作多项式，除以生成多项式，余数作为校验码

选择$r+1$位生成多项式$G$，$r$位的校验码$R$，数据为$d$位的$D$
则$D\cdot 2^r \oplus R = nG$，有$R\equiv D\cdot 2^r \pmod G$

  • 能够检测小于$r+1$位的错误
  • 有$1-0.5^r$的概率检测大于$r+1$位的错误

多路访问协议

对于速率为$R$bps的广播信道，期望：

  • $M$个节点发送数据饰，每个节点平均发送速率为$R/M$
  • 协议去中心化，不会因为单个节点故障而导致整个网络故障
  • 协议简单

信道划分协议

  • FDM和TDM避免冲突，但是利用率低，$N$个节点，每个节点发送速率为$R/N$
  • 码分多址（Code Division Multiple Access，CDMA）：每个节点有唯一的码，接收方根据码译码，编码类似TDM的时隙和FDM的频段

随机接入协议

传输节点以信道的速率发送数据，碰撞时等待一个随机时延后重发

  1. 时隙ALOHA

    假设

    • 所有帧都为$L$比特
    • 时隙长度为$L/R$
    • 节点在时隙开始时发送帧
    • 节点是同步的
    • 节点在时隙结束时检测冲突

    具体过程

    • 发送节点在时隙开始时发送帧
    • 如果检测到碰撞，以一个固定的概率$p$在下一个时隙重发

    最大效率：使$Np(1-p)^{N-1}$最大

  2. ALOHA

    不必等待时隙开始，发送帧后立即检测冲突并以概率$p$重发

    成功的概率为$p(1-p)^{2(N-1)}$，最大效率为$1/(2e)$

  3. CSMA

    载波监听多路访问（Carrier Sense Multiple Access）：发送前检测信道是否繁忙，繁忙则等待

未完待续

电波交流