计算机网络笔记

约 21582 字大约 72 分钟

2025-02-06

第一章绪论

计算机网络概念与组成

计算机网络定义
- 指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统、网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统
网络组成
- 网络边缘：端系统（位于互联网边缘与互联网相连的计算机和其他设备）
  - 客户端：各类主机
  - 服务器：通常部署在数据中心
- 网络核心：由互联端系统的分组交换设备和通信链路构成的网状网络
  - 分组交换设备：路由器、链路层交换机
  - 通信链路：光纤、铜缆、无线电、激光链路等
- 协议（三要素）
  - 语法：规定传输数据的格式（如何讲）
  - 语义：规定所要完成的功能（讲什么）
  - 时序：规定各种操作的顺序（双方讲话的顺序）
互联网服务提供商ISP
- 为用户提供互联网接入服务
- ISP之间相互转发报文
- 域内路由和域间路由
网络服务
- 互联网是为网络应用提供通信服务的基础设施
- 互联网提供两种通信服务：
  - 可靠服务：TCP
  - 不可靠服务：UDP
接入网
- 将终端连接到其边缘路由器的物理链路（边缘路由器是端系统去往任何其它远程端系统的路径上的第一台路由器）

网络核心

网络、互联网、因特网
- 互联网：网络的网络
- 因特网：世界上最大互联网
  - 端系统直接连接到的是接入ISP，要实现端系统间通信，接入ISP必须相互连接，由此形成的网络的网络，即因特网（Internet）
数据交换方式
- 电路交换
  - 带宽和时延有保证：建立连接并预留资源
  - 线路的传输效率低：物理通路被通信双方独占，即使空闲也不与其他连接共享
  - 如果传输中发生设备故障，则传输被中断
- 分组交换
  - 优点
    - 没有建立连接和释放连接的过程
    - 分组传输过程中逐段占用通信链路，有较高的通信线路利用率
    - 交换节点可以为每一个分组独立选择转发路由，使得网络有很好的生存性
  - 缺点
    - 分组首部带来了额外的传输开销
    - 交换节点存储转发分组会造成一定的时延：分组交换机需要接收到完整的整个数据分组后，才能开始向下一跳发送
    - 无法确保通信时端到端通信资源全部可用，在通信量较大时可能造成网络拥塞
    - 分组可能会出现失序和丢失等问题

网络性能指标及分层模型

分组交换网络性能指标
- 时延
  - 处理时延
    - 检查分组首部
    - 确定输出链路
    - 检查比特错误
    - 微秒或更低量级
  - 排队时延
    - 在缓存队列中等待被传输
    - 时间长短取决于队列前方等待传输的分组数量
    - 毫秒到微秒量级
    - 流量强度 = $\frac{La}{R}$ $\frac{L a}{R}$ （a: 分组到达速率）
      - >1 平均时延趋于无穷大
      - < 1 排队时延与流量性质相关
        突发式流量，平均排队时延显著增加
        周期性流量，排队时延较小
  - 传输时延
    - 将分组发送到链路上所需时间 $d_{trans} = \frac{L}{R}$
    - 微秒到毫秒，低速链路上较大
  - 传播时延
    - 信号在链路上传播所需时间 $d_{prop} = \frac{d}{s}$
    - 几微秒到几百毫秒，长距离链路上较大
- 丢包率
  - 在一定的时间范围内，传输过程中丢失的分组数量与总分组数量的比率。
  - 丢包原因
    - 分组到达速率超过输出链路的传输速率
    - 数据错误（误码）
- 吞吐量
  - 发送端和接收端之间的比特传输速率
  - 瓶颈链路：在端到端路径上，限制端到端吞吐量的通信链路
协议分层模型（五层模型）
- 数据单元
  - 协议数据单元（Protocol Data Unit，PDU）：对等层次之间传送的数据包
  - 服务数据单元（Service Data Unit，SDU）：同一系统内层与层之间交换的数据包称为

第二章链路层

链路层概述与差错检测

链路层
- 节点：主机、路由器、交换机等
- 链路（Link）：从一个节点到相邻节点的一段物理线路（有线或无线），而中间没有任何其他的交换节点
  - 有线链路
  - 无线链路
  - 交换局域网
- 帧（frame）：封装网络层数据报
  - 头标（Header）
  - 尾标（Trailer）
  - 有效载荷
封装成帧和透明传输
- 字节计数法（ Byte count ）
- 带字节填充的定界符法（ Flag bytes with byte stuffing ）
  - 定界符（FLAG）：一个特殊的字节，比如 01111110，即 0x7E
  - 发送方：采用ESC作为转义符（转义字节），对帧内FLAG进行转义
  - 接收方：逐个检查收到的每一个字节，收到ESC，则后一字节无条件成为有效载荷，不予检查
- 带比特填充的定界符法（ Flag bits with bit stuffing ）
  - 定界符：两个0比特之间，连续6个1比特，即01111110，0x7E
  - 发送方：检查有效载荷，若在有效载荷中出现连续5个1比特，则直接插入1个0比特
  - 接收方：若出现连续5个1比特
    - 若下一比特为0，则为有效载荷，直接丢弃0比特
    - 若下一比特为1，则连同后一比特的0，构成定界符，一帧结束
差错检测与纠正：EDC (error-detection and correction )
- 检错码：不能推断哪位发生错误
  - 奇偶校验（Parity Check）：增加1位校验位
    - 偶校验：保证1的个数为偶数
  - 循环冗余校验（Cyclic Redundancy Check，CRC）
    - 收发双方约定n+1位二进制位模式G(X) (称为生成多项式)，G的最高位和最低位为1
    - 发送方：基于待发送的数据和生成多项式G(X)，计算出差错检测码（冗余码），将冗余码添加到待发送数据的后面一起传输
    - 接收方：收到数据和冗余码后，通过生成多项式G(X)来计算收到的数据和冗余码是否产生了误码
- 纠错码：定位出错的位置
  - 二维奇偶校验
  - 海明码（Hamming Code）
    - 本质上是多重分组奇偶校验
以太网与卫星无线链路的比较
- 以太网
  - 可靠率高、误码率低
  - 传输速度快，时延低
  - 重点关注传输速度
  - 差错检测技术
- 卫星无线
  - 可靠率较低、误码率较高
  - 传输时延大，重传代价大
  - 重点关注覆盖范围
  - 差错纠正技术

多路访问链路和协议

链路类型
- 点对点链路
  - 应用
    - 长距离链路连接的两台路由器之间（广域网路由器之间的专用链路）
    - 因特网用户计算机通过点对点链路连接到接入ISP
  - 协议：PPP协议
- 广播链路
  - 应用
    - 早期以太网的总线型链路
    - 无线链路
  - 弊端：冲突！如何解决？多路访问协议！
多路访问协议（MAC）
- 定义：协调多个节点共享信道的分布式算法，即决定节点何时进行传输
- 分类
  - 信道划分协议（静态划分）：一经分配，不再变动
    - 时分多址接入（TDMA）
      - 从时间维度将信道划分为时间帧（time frame），每帧进一步划分为N个时隙（slot），每个节点在帧中被分配一个固定的时隙。节点只能在分配的时隙内发送数据，没有数据发送，则其时隙空闲
      - 所有用户在不同的时间串行占用同样的频带
    - 频分多址接入（FDMA）
      - 从频率维度将信道划分为不同的频段，每个节点被分配一个固定的频段。若节点不发送，其频段空闲
      - 频分复用的所有用户同时占用不同的频带资源并行通信
    - 优缺点比较
  - 轮流协议（动态划分）：每个节点轮流获得一个信道的使用权
    - 令牌环网络：令牌（Token）在各个节点间循环传递，拿到令牌的节点可以发送数据，其他节点等待
    - 缺点：令牌开销、接入延迟、单点失效问题
  - 随机接入协议（动态划分）
    - ALOHA系列：发送前不侦听信道
      - 纯ALOHA协议
        基本思想
        任何节点有数据发送就可以立即发送
        节点通过侦听信道判断本次发送是否成功
        若不成功，立即以概率p重传（以概率1-p推迟一个帧时间）
        发生冲突的情形：在时刻t0发送的帧与在(t0-1,t0+1)时段内发送的其它帧冲突
      - 时隙ALOHA协议
        基本思想
        所有链路帧长度相同，将时间划分成等长的时隙（时隙长度为传输一帧的时间）
        节点只能在时隙开始时发送帧
        节点之间需要时钟同步，每个节点都知道时隙何时开始
        若有多个节点同时发送，要求所有节点能够在该时隙结束前检测到冲突
        节点从上层收到数据后，等下一个时隙开始时发送
        若没有检测到冲突，则发送成功，节点可在下一时隙发送新的帧
        若检测到冲突，节点在随后的每一个时隙中以概率p重传直到发送成功
        优缺点
    - CSMA系列：发送前侦听信道
      - 载波侦听多路访问（CSMA）
        基本思想
        节点发送数据前首先侦听信道
        若信道空闲，则发送整个数据帧
        若信道忙，则推迟发送
        发送过程中无碰撞检测
        弊端
        仍然可能出现冲突
        由于存在传播时延，节点可能没侦听到其它节点正在发送
        一旦发送冲突，整个数据帧传输时间被浪费
      - 带碰撞检测（CSMA/CD）
        基本思想
        “先听后说”
        “边说边听”
        一旦发现总线上出现碰撞，立即停止发送，退避一段随机时间后再次从载波监听开始进行发送
        补充：以太网的争用期
        共享总线以太网的端到端往返时间2U被称为争用期
        经过争用期2U这段时间还没有检测到碰撞，就可以肯定这次发送不会产生碰撞
        补充：二进制指数退避算法
        $\text{退}\text{避}\text{时}\text{间}=\text{争}\text{用}\text{期}\times \text{随}\text{机}\text{数}$
        随机数：r从离散的整数集合$$\left {0,1,…,2^k−1\right } $$中随机选出一个数，k=min(⁡重传次数，10)
        补充：最小帧长
        为了确保共享总线以太网上的每一个站点在发送完一个完整的帧之前，能够检测出是否产生了碰撞，帧的发送时延就不能少于共享总线以太网端到端的往返时间
        最小帧长为512b，即64B
        半双工通信：由于正在发送帧的站点必须“边发送帧边检测碰撞”，因此站点不可能同时进行发送和接收，也就是不可能进行全双工通信，而只能进行半双工通信（双向交替通信）

局域网

定义
- 局域网（LAN）
  - 一般指二层可达的网络。也就是网络里面不需要三层设备（路由器）就可以保证可达性
- 以太网（Ethernet）
  - 以太网是局域网的一种特殊类型，局域网包含以太网、令牌环网等多种技术
共享式以太网
- 网络适配器（Adapter，网卡）
  - 在计算机内部，网卡与CPU之间的通信，一般是通过计算机主板上的I/O总线以并行传输方式进行
  - 网卡与外部以太网（局域网）之间的通信，一般是通过传输媒体（同轴电缆、双绞线电缆、光纤）以串行方式进行的
- MAC地址（媒体接入控制，Medium Access Control，与多路访问协议的MAC不同）
  - 当多个主机连接在同一个广播信道上，要想实现两个主机之间的通信，则每个主机都必须有一个唯一的标识，即一个数据链路层地址（全球唯一性）
  - 硬件地址/物理地址：固化在网卡的电可擦可编程只读存储器EEPROM中
    - 物理地址属于数据链路层范畴，而不是物理层！
  - MAC地址长6个字节，一般用“-”分隔的12个16进制数表示，例如1A-2F-BB-76-09-AD
    - 广播地址：FF-FF-FF-FF-FF-FF
  - MAC地址标识的是插在主机上的网卡，而非标识主机
    - 一般情况下，普通用户计算机中往往会包含两块网卡
      - 用于接入有线局域网的以太网卡
      - 用于接入无线局域网的Wi-Fi网卡
    - 路由器往往具有更多的网络接口（网卡），所以会拥有更多的MAC地址
- ARP协议（IP地址与MAC转换）
  - IP地址封装在网络层的IP数据报中，而MAC地址封装在数据链路层的帧中
  - 每个主机保存IP与MAC地址的对应表，并记录TTL（Time To Live）
    - 一般为20分钟：主机IP地址具有动态性
  - ARP协议运行在数据链路层，无法实现跨网络IP地址到MAC地址的解析
- 共享以太网的扩展
  - 集线器：扩大了广播域，扩大了碰撞域
交换式以太网
- 定义：仅使用交换机（而不使用集线器）的以太网就是交换式以太网
  - 交换机：连接主机与路由器的一种交换设备（与集线器不同，交换机基于MAC地址转发分组，而不是所有端口转发）
    - 全双工通信、并发交换
    - 采用存储-转发模式，有缓存
    - 交换机无MAC地址，对节点是透明的，即主机或路由器并不知道交换机的存在
    - 即插即用设备
    - 扩大了广播域，隔离了碰撞域
- 交换机转发表：交换机将A的帧发给B时，怎么知道要选择哪个输出端口？
  - 交换机自学习算法
    - 地址表初始为空
    - 对于在一个端口上收到的每个入帧，交换机在它的表中存储
      - 该帧的源地址字段中的MAC地址
      - 该帧到达的端口
      - 当前时间
    - 如果在一段时间（老化时间）后，没有接收到以表中某个地址作为源地址的帧，交换机将表中的这个地址删除
  - 基于转发表的转发过程
    - 当一个帧到达一个端口时，查找该帧的目的地址
      - 如能找到：将该帧转发到对应的端口
      - 如果找不到：交换机将该帧广播到所有其他端口
    - 对于广播类型的帧，在所有端口转发
- 优势
  - 通信效率高
  - 全双工通信
  - 安全性更高
  - 可扩展性更强
  - 兼容异质链路

第三章网络层

网络层概述

网络层功能：将分组从源主机经过多个网络和多段链路传输到目的主机
- 数据平面（分组转发）：决定了数据报文如何从路由器的输入端口转发到输出端口
- 控制平面（路由选择）：决定了数据报文根据源主机和目的主机的端到端路径，经过哪些路由器
  - 传统路由算法：运行在每个路由器中
  - 软件定义网络（SDN）：由服务器实现
网络层提供的服务
- 因特网服务
  - 数据报服务
    - 网络层向上只提供简单灵活无连接的、尽最大努力（best-effort）交付的数据报服务
    - 发送分组时不需要先建立连接，每个分组独立发送
    - 数据报独立转发，相同源-目的的数据报可能经过不同的路径
    - 网络层不提供服务质量的承诺（丢包、乱序、错误）
    - 优点：网络的造价大大降低，运行方式灵活，能够适应多种应用

IP协议与编址技术

网际协议（Internet Protocol，IP）是TCP/IP体系结构网际层中的核心协议
IPv4数据报首部格式
- 首部长度：以4字节为单位
- 总长度：以字节为单位，用来表示IPv4数据报的长度（首部长度+数据载荷长度）
- 标识：属于同一个IPv4数据报的各分片数据报应该具有相同的标识（IP软件会维持一个计数器，每产生一个IPv4数据报，计数器值就加1，并将此值赋给标识字段）
- 标志
  - 最低位（More Fragment，MF）
    - MF=1表示本分片后面还有分片
    - MF=0表示本分片后面没有分片
  - 中间位（Don’t Fragment，DF）
    - DF=1表示不允许分片
    - DF=0表示允许分片
  - 片偏移
    - 以8字节为单位，用来指出分片IPv4数据报的数据载荷偏移其在原IPv4数据报的位置有多远
IPv4编址
- 分类IP
  - 地址范围
    - A类：1.0.0.0~127.255.255.255
    - B类：128.0.0.0~191.255.255.255
    - C类：192.0.0.0~223.255.255.255
  - 特殊IP地址
  - 缺点：编址方法不够灵活、容易造成大量IPv4地址资源浪费
- 划分子网
  - 将现有IP地址进一步划分，在 IP 地址中增加“子网号字段”，使两级的 IP 地址变成为三级的 IP 地址
  - IP地址= {<网络号>, <子网号>, <主机号>}
  - 子网掩码：从一个 IP 地址无法判断该地址标识的网络是否进行了子网划分
    - 使用子网掩码(subnet mask)，找出 IP 地址中的子网部分
    - 子网掩码：32位0/1比特串，用点分十进制表示，网络号的部分为1
- 无类别域间路由编址（CIDR）
  - 用左起多个连续的比特1对应IPv4地址中的网络前缀，之后的多个连续的比特0对应IPv4地址中的主机号
  - 优点
    - 可以根据客户的需要分配适当大小的CIDR地址块，因此可以更加有效地分配IPv4的地址空间
    - 路由聚合（也称为构造超网）
网络地址转换NAT
- NAT路由器，至少要有一个有效的外部全球地址IP。所有使用内部专用地址的主机在和外部因特网通信时，都要在NAT路由器上将其内部专用地址转换成IP
- 单位和组织不需要申请就可以自行使用，不可在因特网中出现；不同网络内的主机，可能使用相同的IP地址；使大量使用内部专用地址的专用网络用户共享少量外部全球地址来访问因特网上的主机和资源
- 路由器通过端口号标识内网中的主机
- 缺点：外网主机不能首先发起通信
动态主机配置协议
- 地址块：由ICANN地址分配机构或者上层ISP分配
- 主机地址：本组网络管理员分配
  - 网络管理员手动分配地址
  - DHCP（从DHCP服务器动态获取IP地址）

路由器原理

路由器的基本结构
- 输入端口
  - 最长前缀匹配规则
    - 当给定目的地址，通过转发表查询转发端口时，根据与目的地址前缀的最长匹配项来选择
- 交换结构
  - 将分组报文从输入端口缓存传输到合适的输出缓存
  - 分类
    - 共享内存
      - 输入端与输出端之间的交换由路由选择处理器控制，报文被复制到系统内存
      - 交换速率的瓶颈是内存访存带宽（每个数据报文传输至少要经过两个总线周期）
    - 共享总线
      - 数据报文通过共享总线从输入端口存储器传到输出端口存储器
      - 总线冲突：交换速率的瓶颈是总线带宽（一次只有一个报文占用总线）
    - 纵横式（互联网络）
      - 突破总线带宽限制
      - 2N个总线组成的互联网络，N为输入/输出端口数
      - 每一个交叉点交换结构控制器（开启/闭合）
      - 可完成多个分组报文的同时转发（理想情况下可实现所有报文的同时转发）
- 输出端口
路由器排队问题
- 调度策略
  - 先进先出调度策略
  - 优先级调度策略
  - 循环调度策略
  - 加权公平排队

路由算法与协议

控制平面概述
- 路由协议
  - 目标：在由路由器互联而成的网络中，找到源节点到目的节点间好的路径（路由）
    - 什么是好的：数据报能最快到达、开销最小、拥塞程度最小等
  - 分类
    - 内部网关协议（[[#^67ad10|IGP]]，Interior Gateway Protocol）：在一个自治系统内部使用的路由选择协议（RIP和OSPF），主要解决最优路径选择问题
    - 外部网关协议（EGP，External Gateway Protocol）：将路由选择信息传递到另一个自治系统中（[[#^3f29cf|BGP]]-4），主要解决路径可达性问题
- 自治系统
  - 路由协议设计挑战
    - 因特网规模非常大，不可能让所有的路由器知道所有的网络应怎样到达
    - 许多单位不愿意外界了解自己单位网络的布局细节、本部门所采用的路由选择协议
  - 自治系统（Autonomous System，AS）
    - 定义：在同一管理机构下、有独立而统一的内部路由策略的一系列路由器和网络构成的系统
    - 目的：以自治系统为单位进行路由（域内路由选择、域间路由选择）
IGP路由协议 ^67ad10
- 分布式：距离向量路由算法（RIP）
  - 定义：每一个路由器仅知道与其直接相连的邻居路由器及到达邻居的链路开销，通过与邻居路由器交互信息，送代计算路由（无全局拓扑信息）
  - 距离向量算法DV（迭代的、分布式）
    - 每个节点维护一个距离向量，其到邻居节点的距离是准确值
    - 节点在每次送代中向所有邻居发送自身的距离向量
    - 节点每次收到邻居发送的距离向量，就根据Bellman-Ford方程校正自身的距离向量
      - Bellman-Ford方程：x到y的最优路径代价值等于MIN(x到某一邻居的代价值+该邻居到y的最优路径代价值)
    - 只要所有节点以异步方式交换距离向量，每个节点的距离向量值都会收敛到精确最短路径值
    - 距离向量收敛后，只要链路没有更新，节点就不会向邻居发出新距离向量报文，也不会收到邻居的报文，算法进入静止状态
  - 代价：跳数（Hop Count）
    - 路由器到直连网络的距离定义为1
    - 路由器到非直连网络的距离定义为所经过的路由器数加1
    - 允许一条路径最多只能包含15个路由器，距离等于16时相当于不可达
      - RIP只适用于小型互联网
  - 特点
    - 和谁交换信息：仅和相邻路由器交换信息
    - 交换什么信息：路由器自己的路由表（即本路由器到所在自治系统中各网络的最短距离，以及到各网络应经过的下一跳路由器）
    - 何时交换信息
      - 周期性交换（如每30秒)
        若180秒没有收到某条路由条目的更新报文，则把该路由条目标记为无效（把RP距离设置为16，表示不可达）
        若再过一段时间（如120秒），还没有收到该路由条目的更新报文，则将该路由条目从路由表中删除
      - 触发更新（当网络拓扑发生变化时）
  - 基于DV算法的更新规则
    - 到达同一目的网络，相同的下一跳，无论RIP距离增大还是减小，均需更新
    - 发现了新的网络，添加
    - 到达同一目的网络，不同的下一跳，新路由优势，要更新；新路由劣势，不更新
    - 到达同一目的网络，不同的下一跳，RIP距离相等，可以等价负载均衡，添加
  - 优缺点
    - 优点
      - 实现简单，路由器开销小
      - “好消息传播快”：如果一个路由器发现了RIP距离更短的路由，那么这种更新信息就传播得很快
    - 缺点
      - RIP限制了最大RIP距离为15：限制了使用RIP的自治系统的规模
      - 随着网络规模的扩大，开销也随之增大：相邻路由器之间交换的路由信息是路由器中的完整路由表
      - “坏消息传播得慢”：路由环路或RIP距离无穷计数问题
        解决措施（无法彻底解决）
        限制最大RIP距离为15
        触发更新
        水平分割：让路由器记录收到某个特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传送
- 全局式：链路状态路由算法（OSPF）
  - 定义：每个路由器能够获取全局拓扑、各条链路状态信息
  - 链路状态路由选择算法LS
    - 所有节点都有该网络的网络结构和链路信息
      - 通过链路状态广播实现
      - 节点独立计算出相同结果
    - 计算从某源节点到网络中所有其它节点的最短路径
      - 采用Dijkstra算法
      - 生成转发表
  - 特点
    - 和谁交换信息：整个AS内所有路由器
    - 交换什么信息：直连网络的链路状态信息
    - 何时交换信息
      - 周期性交换（如每约30分钟）
      - 链路状态发生变化
  - 代价
    - 供考虑的因素有链路带宽、链路负载、延迟等
    - 网络管理人员决定选择何种元素量化链路“代价”
  - OSPF基本工作过程
    - 路由器邻居关系的建立和维护
      - 相邻路由器之间通过交互问候（Hello）分组来建立和维护邻居关系
        问候分组封装在IP数据报中，发往组播地址224.0.0.5
        IP数据报首部中的协议号字段的取值为89
      - 发送时机
        发送周期：10秒
        若40秒未收到来自邻居路由器的问候分组，则认为邻居路由器不可达
      - 每个路由器都会建立一张邻居表
    - 链路状态通告（Link State Advertisement，LSA）
      - 包含内容
        直连网络的链路状态信息
        邻居路由器的链路状态信息
      - LSA被封装在链路状态更新（Link State Update，LSU）分组中，采用洪泛法（Flooding）发送
        路由器向所有的邻居路由器发送链路状态更新分组，收到该分组的各路由器又将该分组转发给自己所有的邻居路由器（但其上游路由器除外）
        收到重复的更新分组无需再次转发
    - 链路状态数据库（Link State Database，LSDB）
      - 使用OSPF的每一个路由器都有一个LSDB，用于存储链路状态通告LSA
      - 通过各路由器洪泛发送封装有各自链路状态通告LSA的链路状态更新分组LSU，各路由器的链路状态数据库LSDB最终将达到一致
    - 最短路径计算
  - 优缺点
    - 优点
      - OSPF是基于链路状态的，而不像RIP是基于距离向量的
      - OSPF基于链路状态并采用最短路径算法计算路由，从算法上保证了不会产生路由环路
      - OSPF不限制网络规模，更新效率高，收敛速度快
    - 缺点
      - 洪泛法更新链路状态，更新开销大（洪泛危机）
        把一个自治系统AS再划分为若干个更小的区域（area）
        洪泛法交换路由信息局限于每一个区域内
      - 复杂，资源消耗大
BGP路由协议 ^3f29cf
- 自治域边界路由器需要同时运行IGP和BGP
- BGP功能：基于TCP连接，发送BGP报文通告BGP路由信息
  - 外部BGP（eBGP）：从相邻的AS获得网络可达信息
  - 内部BGP（iBGP）：将网络可达信息传播给AS内的路由器
- BGP会话：两个BGP路由器通过TCP连接交换BGP报文
  - 通告到不同网络前缀的路径，即路径向量协议
  - BGP通告：NEXT-HOP：AS-PATH：网络前缀
    - NEXT-HOP：AS-PATH起始的路由器接口的IP地址（注意其不在当前AS）
    - AS-PATH：前缀通告所经过的AS列表
- BGP路由选择：路由器可能选择不止一个路由器到目的AS（以下原则优先级依次递减）
  - 本地的偏好属性：由策略决定
  - 最短AS-PATH
    - 距离测度使用AS跳的跳数，而不是路由器跳的跳数
  - 最近的NEXT-HOP路由器：热土豆路由
    - 选择具有最小域内开销的本地网关，不要担心域间开销
  - 其他指标

IPv6与SDN

网际控制报文协议ICMP
- 目的：更有效地转发IP数据报以及提高IP数据报交付成功的机会
- ICMP报文被封装在IP数据报中发送
- 分类
  - 差错报告报文：用来向主机或路由器报告差错情况
    - 终点不可达：当路由器或主机不能交付IP数据报时，就向源点发送终点不可达报文
    - 源点抑制：当路由器或主机由于拥塞而丢弃IP数据报时，就向发送该IP数据报的源点发送源点抑制报文
    - 超时
      - 当路由器收到一个目的IP地址不是自己的IP数据报时，会将其首部中生存时间TTL字段的值减1
      - 若结果不为0，则路由器将该数据报转发出去；若结果为0，路由器不但要丢弃该数据报，还要向发送该IP数据报的源点发送超时报文
    - 参数问题：当路由器或目的主机收到IP数据报后，根据其首部中的检验和字段的值发现首部在传送过程中出现了误码，就丢弃该数据报，并向发送该数据报的源点发送参数问题报文
    - 改变路由（重定向）：路由器把改变路由报文发送给主机，让主机知道下次应将IP数据报发送给另外的路由器，这样可以通过更好的路由到达目的主机
  - 询问报文：用来向主机或路由器询问情况
    - 分类
      - 回送请求和回答：用来测试目的站是否可达以及了解其有关状态
      - 时间戳请求和回答：用来进行时钟同步和测量时间
    - 应用
      - 分组网间探测（Packet InterNet Groper, PING）
      - 跟踪路由（traceroute）
        用于探测IP数据报从源主机到达目的主机要经过哪些路由器
        命令和实现机制
        UNIX：“traceroute”，在运输层使用UDP协议，在网络层使用ICMP报文（差错报告报文）
        Windows：“tracert”，在应用层直接使用网际层的ICMP协议（回送请求和回答报文、差错报告报文）
IPv6
- 地址格式
  - 地址压缩
    - 左侧零：指两个冒号间的十六进制数中最前面的一串0可以省略不写
    - 连续零：指一连串连续的0可以用一对冒号取代（只能用一次）
- 数据报格式
  - 下一个首部
    - 没有扩展首部时，该字段指出了IPv6数据报基本首部后面的数据是何种协议数据单元PDU
    - 有扩展首部时，该字段标识了后面第一个扩展首部的类型
  - 版本字段：对于IPv6该字段的值是6
  - 流量类型字段：用来区分不同的IPv6数据报的类别或优先级
  - 流标号字段：所有属于同一个流的IPv6数据报都具有同样的流标号（流标号用于资源分配）
  - 有效载荷长度字段：指明IPv6数据报基本首部后面的有效载荷（包括扩展首部和数据部分）的字节数量（最大取值为65535字节）
  - 跳数限制字段：防止IPv6数据报在因特网中永久兜圈（与IPv4数据报首部中TTL字段完全一样）
IPv6与IPv4
- 区别
  - 地址长度从32位→128位，有效解决IPv4地址短缺问题
  - 精简IP报文首部，加快处理速度
    - 固定首部40字节
    - 不允许分片
    - 删除了校验和字段
    - 选项字段不再属于首部范围，通过“下一首部”指出
  - 首部中加入流标签，支持QoS优先级服务
- IPv4向IPv6迁移：隧道技术（Tunneling）
  - 当IPv6数据报要进入IPv4网络时，将IPv6数据报重新封装成IPv4数据报，即整个IPv6数据报成为IPv4数据报的数据载荷
    - 要使双协议栈路由器知道IPv4数据报的数据载荷是IPv6数据报，则IPv4数据报首部中协议字段的值必须设置为41
  - 封装有IPv6数据报的IPv4数据报在IPv4网络中传输
  - 当IPv4数据报要离开IPv4网络时，再将其数据载荷（即原来的IPv6数据报）取出并转发到IPv6网络
传统意义上数据层面 vs SDN的泛化转发
- 传统意义上的数据层面的任务：根据转发表转发分组
  - 匹配：查找转发表中的网络前缀（最长前缀匹配）
  - 操作：把分组从匹配结果指明的接口转发出去
  - 实现：在网络层工作，设备为路由器，使用转发表
- SDN的泛化转发
  - 匹配：能够对网络体系结构中各层（数据链路层、网络层、运输层）首部中的字段进行匹配
  - 操作：不仅转发分组，还可以负载均衡、重写IP首部（类似NAT路由器中的地址转换）、人为地阻挡或丢弃一些分组（类似防火墙）
  - 实现：并不局限在网络层工作，设备为[[#^9889b3|分组交换机]]，使用流表（Flow Table）
分组交换机 ^9889b3
- 必须有一个或多个流表
- 每一个流表可以包含多个流表项
- 每个流表项包含三个字段
  - 首部字段值（或称匹配字段）
  - 计数器
    - 记录已经与该流表项匹配的分组数量的计数器
    - 记录该流表项上次更新到现在经历时间的计数器
  - 动作
    - 把分组转发到指明的端口
    - 丢弃分组
    - 把分组进行复制后再从多个端口转发出去
    - 重写分组的首部字段（包括数据链路层、网际层以及运输层的首部）

第四章传输层

传输层概述与UDP协议

传输层服务
- 传输层位置
  - 传输层位于应用层和网络层之间：基于网络层提供的服务，向分布式应用程序提供通信服务
  - 传输层向上为应用程序提供通信服务，是面向通信部分的最高层；同时也是用户功能中的最底层，只有网络边缘部分的主机协议栈才有传输层
  - 传输层应提供进程之间本地通信的抽象：即运行在不同终端上的应用进程仿佛是直接连在一起的
- 跨主机进程通信
  - 套接字（socket）是应用层和传输层的接口，也是应用程序和网络之间的API
- 网络层和传输层提供的服务：传输层依赖网络层服务（延时、带宽等），并扩展网络层服务（数据丢失、顺序混乱、加密等）
  - 网络层提供“尽力而为”的服务
    - 尽最大努力在主机间交付分组但不提供任何承诺：不保证交付，不保证按序交付，不保证数据完整，不保证延迟，不保证带宽等
  - 传输层提供的服务
    - 最低限度的传输服务（UDP）：将主机-主机的数据交付扩展到进程-进程的数据交付、报文检错
    - 增强服务（TCP）：面向连接、可靠传输、流量控制、拥塞控制
多路复用与分解
- 多路复用与分解概念
  - 传输层基本服务：将主机间交付扩展到进程间交付，通过复用和分用实现（每个套接字有唯一的套接字标识）
    - 复用（发送端）：传输层从多个套接字收集数据交给网络层发送
    - 分用（接收端）：传输层将从网络层收到的数据，交付给正确的套接字
- 端口号（是套接字标识的一部分）
  - 分类
    - 熟知端口（0～1023）：由公共域协议使用
    - 注册端口（1024～49151）：需要向IANA注册才能使用
    - 动态/私有端口（49152～65535）：一般程序使用
  - 分配
    - 自动分配：创建套接字时不指定端口号（客户端）
      - 由操作系统从49152～65535中分配
    - 使用指定端口号创建套接字（服务器）
      - 实现公共域协议的服务器应分配众所周知的端口号（0~1023）
- UDP多路复用与分解方法
  - 使用<目的IP地址，目的端口号>二元组进行标识
  - 服务器使用一个套接字服务所有客户
  - <目的IP地址，目的端口号>相同的UDP报文段被交付给同一个套接字，与<源IP地址，源端口号>无关
- TCP多路复用与分解方法
  - 使用<源IP地址，目的IP地址，源端口号，目的端口号>四元组标识连接套接字
  - 服务器使用一个监听套接字和多个连接套接字服务多个客户，每个连接套接字服务一个客户
无连接传输UDP
- UDP报文段结构
- UDP报文
  - 首部（8字节）：携带协议处理需要的信息
    - 用于复用和分用的字段：源端口号、目的端口号
    - 用于检测报文错误的字段：报文总长度（首部+数据）、校验和（checksum）
  - 载荷（payload）：携带上层数据
- 校验和计算方法（可选）
  - 发送方
    - 计算范围：伪首部、UDP首部和UDP数据（checksum字段填0）
      - UDP伪首部信息取自IP数据报首部：为了避免由于IP地址错误等造成的误投递
        源IP地址，目的IP地址
        UDP的协议号（17）
        UDP报文段总长度
  - 接收方
    - 计算范围：伪首部、UDP首部和UDP数据（checksum字段填接受到的值）
      - 若结果为0xFFFF，认为没有错误
  - 计算方法
- UDP优点
  - 可以尽可能快地发送报文
    - 无建立连接的延迟
    - 不限制发送速率（不进行拥塞控制和流量控制）
  - 报头开销小
  - 协议处理简单
- UDP应用（若要求基于UDP进行可靠传输：由应用层实现可靠性）
  - 容忍丢包但对延迟敏感的应用：如流媒体
  - 以单次请求/响应为主的应用：如DNS

可靠数据传输原理

rdt（reliable data transfer，可靠数据传输协议）
- rdt1.0：理想信道上的可靠传输
  - 假设：报文不出错、无重复、无丢失、按顺序
- rdt2：出错信道上的可靠传输
  - rdt2.0
    - 差错检测：比如检错码（如checksum）
    - 接收方反馈：比如ACK和NAK（假设ACK和NAK不会出错）
    - 重传：发送方收到NAK后重传出错的报文
  - rdt2.1
    - 重传：如果ACK/NAK出错，发送方不知道接收方是否正确接收报文
    - 处理重复报文
      - 发送方给每个报文添加一个序号，接收方根据序号检测冗余的重复报文，并丢弃
      - 报文序号的长度：只需1个比特，用于接收方区分是新报文，还是重发报文
  - rdt2.2
    - 不用NAK，只用ACK
      - 接收方：发送的ACK中携带所确认的报文序号
        对接收到的每个正确报文发送ACK
        若接收到错误报文、或重复报文，重发对前一个接收到的正确报文的ACK
      - 发送方：若ACK的序号不是所期待的（重复的），重发当前报文
    - FSM描述
- rdt3.0：丢包信道上的可靠传输
  - 内容
    - 检测报文丢失：若发送方在“合理的”时间内未收到ACK，则认为丢包
    - 重传：定时器超时，发送方重传当前报文
  - 性能低：网络协议限制了物理资源的利用
- 流水线可靠数据传输协议：允许发送方有多个已发送、未确认的报文
  - 报文的序号范围要扩大（停等协议只是用1比特序号）
  - 发送方和接收方可能需要缓存多个报文（停等协议中发送方缓存一个报文，接收方不缓存）
  - 两种重传协议
    - 回退N步（GBN，Go-back-N）：出错率低
      - 内容
        发送方
        允许N个已发送、未确认的报文
        为序号最小的一个未确认报文设置计时器
        超时则重传从该报文起的所有报文
        接收方
        使用累积确认
        若ACK包含序号q，则表明“序号至q的报文均正确收到”
        失序报文处理
        丢弃（不缓存）：没有接收缓存（也就没有接收窗口）
        对保序的最大序列号的报文重发ACK
      - 性能：在带宽较大和窗口较大的情况下，一次传输出错就会引起大量重传
    - 选择重传（SR，selective repeat）：出错率高
      - 内容
        发送方
        发送端窗口：N个连续的序列号
        只对没有收到ACK确认的报文重新发送
        对于每个未确认报文都设置定时器
        接收方
        逐个确认所有正确收到的报文
        按需缓存报文，最终按序提交给上层协议
      - SR协议的困境
        情况(b)中：冗余数据被当成新数据而接收
        为避免此情况：接收方的滑动窗口的大小必须小于等于序号空间大小的一半

面向连接TCP协议

TCP概述
- 是面向连接的传输层协议，在“尽力而为”的网络层服务基础之上提供可靠交付的服务
- 在网络层不可靠的分组交付基础之上，增加了保证可靠性的一系列措施
- TCP vs UDP
TCP特点
- 每一条TCP连接只能有两个端点（endpoint），点到点通信
  - 端点是套接字（socket）
  - TCP连接::={socket1,socket2}= {(IP1:port1),(IP2:port2)}
- 提供全双工通信
- TCP提供流量控制和拥塞控制
- TCP提供面向字节流的可靠交付服务
  - 虽然应用程序和TCP的交互是一次一个数据块，但TCP把应用程序交下来的数据看成仅仅是一连串无结构的字节流
TCP报文段格式
- 序号：传送的数据流中的每一个字节都编上一个序号。序号字段指的是本报文段所发送的数据的第一个字节的序号
- 确认号：期望收到对方的下一个报文段的数据的第一个字节的序号
- 首部长度：也叫数据偏移，它指出TCP报文段中数据的起始处，以4字节为计算单位
- URG（紧急）：它告诉系统此报文段中有紧急数据，应尽快传送（相当于高优先级的数据）
- ACK（确认）：只有当 ACK =1 时字段才有效
- PSH（PuSH，推送）：收到 PSH = 1的报文段，就尽快地交付接收应用进程，不再等到整个缓存都填满了后再向上交付
- RST（ReSeT，复位）：当RST=1时，表明TCP连接中出现严重差错（如由于主机崩溃或其他原因），必须释放连接，然后再重新建立运输连接
- SYN（同步）：SYN=1表示这是一个连接请求或连接接受报文
- FIN（FINish，终止）：FIN=1表明此报文段的发送端的数据已发送完毕，并要求释放运输连接
- 接收窗口字段：用来向发送方报告当前接收窗口的大小，是发送方设置发送窗口的依据，单位为字节
- 校验和：检验的范围包括首部和数据这两部分。在计算校验和时，要在TCP报文段的前面加上12字节的伪首部
- 紧急指针字段：指出在本报文段中紧急数据共有多少个字节（紧急数据放在本报文段数据的最前面）
TCP可靠传输
- 简化协议
  - 接收方（累积确认，与GBN类似）
    - 仅在正确、按序收到报文后，发送确认序号，并向前滑动窗口
    - 其余情况，重复前一次的确认序号
  - 发送方
    - 流水线方式发送报文，通过发送窗口限制一次发送的数据量
    - 仅对最早未确认的报文使用一个重传定时器（与GBN类似）
    - 仅在超时后重发引起超时（最早未确认）的报文（与GBN不同，与SR类似）
    - 收到新的确认序号后，向前滑动发送窗口
- TCP通过采用以下机制减少了不必要的重传
  - 只使用一个定时器，避免了超时设置过小时重传大量报文段
  - 利用流水式发送和累积确认，可以避免重传某些丢失了ACK的报文段
- ACK实现建议
  - 快速重传：如果发送方收到同一个数据的3个冗余ACK，则立刻进行重传 ^497ba3
- 超时重传时间RTO（参考：30-tcp可靠传输——超时重传时间）
  - $RTO=RTT_S+4\times RTT_D$ $RTO = RT T_{S} + 4 \times RT T_{D}$
    - RTT偏差的加权平均 $RTT_D$ $RT T_{D}$
      - $RTT_{D1}=RTT_1/2$
      - $\text{新}\text{的}RTT_D=(1-\beta)\times \text{旧}\text{的}RTT_D+\beta \times|\text{旧}\text{的}RTT_S-\text{新}\text{的}RTT\text{样}\text{本}|$
    - 加权平均往返时间 $RTT_S$ $RT T_{S}$
      - $RTT_{S1}=RTT_1$
      - $\text{新}\text{的}RTT_S=(1-\alpha)\times \text{旧}\text{的}RTT_S+\alpha \times\text{新}\text{的}RTT\text{样}\text{本}$
  - 报文段发生重传，就不采用RTT样本计算RTO而是把RTO增大一些。典型的做法是将新RTO的值取为I旧RTO的2倍
TCP流量控制
- 概述
  - 目的：解决因发送方发送数据太快而导致接收方来不及接收，造成接收方的接收缓存溢出的问题
  - 基本方法：接收方根据自己的接收能力（接收缓存的可用空间大小）控制发送方的发送速率
- 协议
  - TCP接收端
    - 使用显式的窗口通告，告知发送方可用的缓存空间大小
    - 在接收窗口较小时，推迟发送确认
    - 仅当接收窗口显著增加时，通告新的窗口大小
  - TCP发送端
    - 使用接收窗口限制发送的数据量，已发送未确认的字节数不超过接收窗口的大小
- 由于非零窗口通知报文段丢失而引起的死锁
  - TCP为每一个连接都设有一个持续计时器
  - 只要TCP连接的一方收到对方的零窗口通知，就启动持续计时器
  - 当持续计时器超时时，就发送一个零窗口探测报文段，仅携带1字节的数据
  - 对方在确认这个零窗口探测报文段时，给出自己现在的接收窗口值
  - 如果接收窗口值仍然是0，那么收到这个报文段的一方就重新启动持续计时器
  - 如果接收窗口值不是0，那么死锁的局面就可以被打破了
- 讨论：为什么GBN/SR和UDP不需要流量控制
  - GBN/SR均假设
    - 正确、按序到达的分组被立即交付给上层
    - 其占用的缓冲区被立即释放
    - 因此，发送方根据确认序号即可知道哪些分组已被移出接收窗口，接收窗口还可以接受多少分组
  - UDP不保证交付
    - 接收端UDP将收到的报文载荷放入接收缓存
    - 应用进程每次从接收缓存中读取一个完整的报文载荷
    - 当应用进程消费数据不够快时，接收缓存溢出，报文数据丢失，UDP不负责任
TCP连接管理
- 建立连接：三次握手
  - Step1：客户TCP发送SYN报文段（SYN=1，ACK=0）
    - 给出客户选择的起始序号
      - 讨论：为什么起始序号不从0开始？起始序号如何选择？
        客户端和服务端的初始化序列号都是随机生成，能很大程度上避免历史报文被下一个相同四元组的连接接收
        然后又引入时间戳的机制，从而完全避免了历史报文被接收的问题
    - 不包含数据
  - Step2：服务器TCP用SYN&ACK报文段响应（SYN=1，ACK=1）
    - 给出服务器选择的起始序号
    - 确认客户的起始序号
    - 不包含数据（服务器端分配缓存和变量）
  - Step3：客户TCP用ACK报文段响应（SYN=0, ACK=1）
    - 确认服务器的起始序号
    - 可能包含数据（客户端分配缓存和变量）
    - 讨论：为什么需要第三次握手？两次握手为什么不行？
      - 防止历史连接的混淆，避免造成双方资源的浪费
      - 确保双方的初始序列号同步，保证了后续数据传输的正确性和顺序性
- 释放连接：四次挥手
  - Step1：客户TCP发送FIN报文段
    - 数据传输结束后，通信的双方都可释放连接
    - 发出连接释放报文段，并停止再发送数据，主动关闭TCP连接
  - Step2：服务器TCP发出响应
    - 服务器TCP通知应用进程
    - 从A到B这个方向的连接就释放了，但B到A方向还可以发送数据，TCP连接处于半关闭状态
  - Step3：服务器TCP发送FIN报文段
    - 若B已经没有数据要向A发送，其应用进程就通知TCP释放连接
    - 可与Step2合并变成三次挥手
  - Step4：客户TCP发出确认
- 拓展：SYN泛洪攻击
  - 过程
    - 攻击者采用伪造的源IP地址，向服务器发送大量的SYN报文段
    - 服务器发送SYN&ACK响应，分配资源，但却得不到ACK确认
    - 若未收到ACK报文段，服务器超时后重发SYN&ACK报文段
    - 服务器等待一段时间（称SYN超时）后丢弃未完成的连接（SYN超时的典型值为30秒~120秒）
  - 结果
    - 服务器为维护大量的半开连接表耗尽资源，导致无法处理正常客户的连接请求，表现为服务器停止服务

拥塞控制原理与方法

拥塞控制概述
- 拥塞（congestion)：在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络性能就要变坏
  - 网络的资源：计算机网络中的链路容量（带宽）、交换节点中的缓存和处理机等
- 拥塞产生原因
  - 节点缓存的容量太小
  - 链路的容量不足
  - 节点处理的速率太慢
  - 拥塞本身会进一步加剧拥塞
- 讨论：增加资源能够解决网络拥塞吗？不能！
  - 增大缓存：但未提高输出链路的容量和处理机的速度，排队等待时间将会大大增加，引起大量超时重传，解决不了网络拥塞
  - 提高处理机处理的速率：会将瓶颈转移到其他地方
- 流量控制 vs 拥塞控制
  - 流量控制
    - 以接收方的接收能力控制发送方（源点）的发送速率流量控制
    - 只与特定的点对点通信的发送方和接收方之间的流量有关
  - 拥塞控制
    - 源点根据各方面因素，按拥塞控制算法自行控制发送速率拥塞控制
    - 全局性问题，涉及网络中所有的主机、路由器等
- 一般原理
  - 开环控制
    - 特点：从一开始就保证问题不会发生，一旦系统启动并运行起来，就不需要中途修正
    - 适用：当网络的流量特征可以准确规定且性能要求可以事先获得时
  - 闭环控制
    - 特点：基于反馈的控制方法
      - 监测网络拥塞在何时、何地发生
      - 把拥塞发生的相关信息传送到可以采取行动的地方
      - 调整网络的运行以解决拥塞问题
    - 适用：当网络的流量特征不能准确描述或者当网络不提供资源预留时
- 衡量网络拥塞的指标
  - 由于缓存溢出而丢弃的分组的百分比
  - 路由器的平均队列长度
  - 超时重传的分组数量
  - 平均分组时延和分组时延的标准差
- 拥塞信息的反馈形式
  - 显式反馈算法：从拥塞节点（即路由器）向源点提供关于网络中拥塞状态的显式反馈信息
  - 隐式反馈算法：源点自身通过对网络行为的观察（例如超时重传或往返时间RTT）来推断网络是否发生了拥塞
- 拥塞控制方法
  - 增加网络可用资源
  - 减少用户对资源的需求（如降低数据发送量）
TCP拥塞控制方法：闭环控制
- 检测
  - 收到三个重复的ACK：预示网络可能会出现拥塞（轻度拥塞，实际可能还未发生拥塞）
    - 三次重复的ACK，可能是丢包引起的，丢包可能是网络拥塞造成的
  - 重传定时器超时：网络已经发生了拥塞（重度拥塞）
- 反馈：显式反馈算法必须涉及网络层，因特网主要利用隐式反馈在传输层实现拥塞控制
- 控制：用基于窗口的方法进行拥塞控制
  - TCP发送方维持一个拥塞窗口cwnd（Congestion Window）
    - TCP拥塞控制的关键便是基于网络拥塞状况动态调整cwnd的值
    - 控制拥塞窗口的原则
      - 只要网络没有出现拥塞，拥塞窗口就可以再增大一些，以便把更多的分组发送出去，提高网络的利用率
      - 但只要网络出现拥塞或有可能出现拥塞，就必须把拥塞窗口减小一些，以减少注入到网络中的分组数，以缓解网络出现的拥塞
  - 发送窗口大小不仅取决于接收方窗口，还取决于网络的拥塞状况
    - 真正的发送窗口值=Min(接收窗口值，拥塞窗口值)
  - 慢启动和拥塞避免两个阶段
    - 划分
      - 慢启动门限（ssthresh）
        用于确定慢启动与拥塞避免切换
        防止拥塞窗口增长过大引起网络拥塞
      - 当cwnd<ssthresh时，使用慢启动算法
      - 当cwnd>ssthresh时，改用拥塞避免算法
      - 当cwnd=ssthresh时，既可使用慢启动算法，也可使用拥塞避免算法
    - 慢启动（slow start）
      - 目的：用来确定网络的负载能力或拥塞程度
      - 算法的思路：由小到大逐渐增大拥塞窗口数值
        初始cwnd=1个最大报文段
        每经过一个传输轮次，cwnd加倍
      - 解释：“慢启动”是指一开始向网络注入的报文段少，而并不是指拥塞窗口cwnd的值增长速度慢
    - 拥塞避免（congestion avoidance）
      - 每经过一个传输轮次，拥塞窗口cwnd=cwnd+1
      - 解释：“拥塞避免”也并非指完全能够避免拥塞，而是指在拥塞避免阶段将cwnd值控制为按线性规律增长，使网络比较不容易出现拥塞
  - 超时重传和三个重复ACK两种情况
    - 超时重传
      - 目的：迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕
      - 算法
        ssthresh = cwnd/2
        cwnd = 1
        执行慢启动算法
    - 三个重复ACK：快速恢复算法（Fast Recovery）
      - 依赖于[[#^497ba3|快速重传]]
      - 算法
        ssthresh=cwnd/2
        cwnd=ssthresh +3（注：下图有误，应该要+3）
        执行拥塞避免算法

第五章应用层

应用层概述和HTTP

应用层概述
- 应用层协议：为了解决某一应用问题，通过位于不同主机中的多个应用进程之间的通信和协同工作来完成
- 两台主机通信实际是其上对应的两个应用进程（process）在通信
网络应用体系结构
- 客户/服务器（Client/Server，C/S）方式
  - 特点
    - 客户和服务器是指通信中所涉及的两个应用进程
      - 客户是服务请求方，服务器是服务提供方
    - 服务器总是处于运行状态，并等待客户的服务请求
    - 服务器具有固定端口号，而运行服务器的主机也具有固定的IP地址
    - 客户端互相之间不直接通信
  - 应用：服务集中型
    - 万维网WWW、电子邮件、文件传输FTP
  - 特例：浏览器/服务器(B/S，Browser/Server) 方式
    - 客户软件改为浏览器
    - 采取浏览器请求、服务器响应的工作模式
    - 用户界面完全通过Web浏览器实现，一部分事务逻辑在前端实现，但主要的事务逻辑在服务器端实现
- 对等（Peer-to-Peer，P2P）方式
  - 特点
    - 没有固定的服务请求者和服务提供者，分布在网络边缘各端系统中的应用进程是对等的，被称为对等方
    - 对等方相互之间直接通信，每个对等方既是服务的请求者，又是服务的提供者
  - 应用：服务分散型
    - P2P文件共享、即时通信、P2P流媒体、分布式存储
  - 优势
    - 可扩展性：因为系统每增加一个对等方，不仅增加的是服务的请求者，同时也增加了服务的提供者，系统性能不会因规模的增大而降低
    - 成本：因为它通常不需要庞大的服务器设置和服务器带宽
  - 劣势
    - 安全性
    - 管理复杂性
进程通信
- 实现方式
  - 同一主机：使用OS提供的进程间通信机制
  - 不同主机：通过网络交换报文进行通信
- 套接字：类似于一扇门，是应用层与传输层的接口，也是应用程序和网络之间的API
  - 发送进程将报文推出门
  - 运输设施（即因特网）将报文运送到接收进程的门口
应用层需要的传输服务
- 传输可靠性
  - 可以容忍一定程度的数据丢失：音视频
  - 要求数据100%完整：文件传输、网上银行
- 吞吐量
  - 要求保证最低可用带宽：多媒体
  - 可以适应各种可能的带宽：电子邮件、文件传输（弹性应用）
- 时延保证
  - 要求最低时延保证：网络电话、网络游戏
  - 对延迟不敏感：电子邮件、文件传输
- 安全需求
  - 数据加密、数据完整性
万维网概述
- 定义：并非某种特殊的计算机网络。它是一个大规模的、联机式的信息储藏所，是运行在因特网上的一个分布式应用，一种信息共享服务
- 服务器
  - Web页面（HTML文档）：包含到多种对象或链接
  - Web对象（包括静态对象和动态对象）：可以是 HTML文档、图像文件、视频文件、声音文件、脚本文件等
- 客户端
  - 发出请求、接收响应、解释HTML文档并显示
  - 有些对象需要浏览器安装插件
- 万维网需要解决哪些问题
  - 怎样标志和寻找万维网的对象：路标
    - 统一资源定位符：URL（Uniform Resource Locator）
    - 协议和域名部分不分大小写，路径部分是否区分大小写则不一定
  - 怎样编辑和显示万维网的对象：语言
    - HTML（超文本标记语言，HyperText Markup Language）
    - XML（EXtensible Markup Language）
      - 一种用于标记电子文件使其具有结构性的标记语言
      - 具有比HTML更强的扩展性
    - JSON（JavaScript Object Notation）
      - 一种轻量级的数据交换格式，易于人阅读和编写
      - 易于机器解析和生成，有效地提升网络传输效率
    - YAML（YAML Ain't a Markup Language）
      - 可读性高，用来表达数据序列化的格式
      - 用缩进和换行表示层次关系，可读性更强
      - 用来写配置文件的语言，非常简洁和强大
  - 怎样传送万维网的对象：传输工具
    - Web应用采用C/S模型
      - 客户端：浏览器
      - 服务器：Web服务器程序
    - HTTP协议
      - 定义了浏览器和Web服务器之间的通信规则（报文交换模式、方法、报文结构）
      - 基于TCP协议，默认使用TCP的80端口
        建立TCP连接：浏览器向Web服务器的80端口发起TCP连接请求；Web服务器接受来自客户端的TCP连接，连接建立
        交换HTTP报文：浏览器和Web服务器交换HTTP报文
        关闭TCP连接
      - 无状态协议
        服务器端不保留之前请求的状态信息
        效率低，但简单
HTTP
- HTTP发展过程
  - HTTP/1.0（1996）
    - 特点
      - 无状态
      - 非持久连接：每次浏览器要请求一个文件都要与服务器建立TCP连接，当收到响应后就立即关闭连接
    - 为了减小时延，浏览器通常会建立多个并行的TCP连接同时请求多个对象
      - 这会大量占用万维网服务器的资源，特别是万维网服务器往往要同时服务于大量客户的请求
  - HTTP/1.1（1999）
    - 特点
      - 缓存策略优化、部分资源请求及断点续传
      - 持续连接：服务器在发送响应后仍然保持这条连接，使同一个客户（浏览器）和该服务器可以继续在这条连接上传送后续的HTTP请求报文和响应报文。这并不局限于传送同一个页面上引用的对象，而是只要这些文档都在同一个服务器上就行。
      - 流水线机制：浏览器在收到HTTP的响应报文之前就能够连续发送多个请求报文。这样的一个接一个的请求报文到达服务器后，服务器就发回一个接一个的响应报文。这样就节省了很多个RTT时间，使TCP连接中的空闲时间减少，提高了下载文档的效率。
  - HTTPS：HTTP+TLS（2008）
    - 增加SSL/TLS（TLS 1.3）层，在TCP之上提供安全机制
  - HTTP/2.0（2015）
    - 目标：提高带宽利用率、降低延迟
    - 增加二进制格式、TCP多路复用、头压缩、服务端推送等功能
  - HTTP/3.0 (2018提案，2022年发布)
    - 采用QUIC+UDP
- HTTP报文格式
  - 特点
    - HTTP是面向文本的
    - 报文中的每一个字段都是一些ASCII码串
    - 每个字段的长度都是不确定的
  - 请求报文
    - 示例
  - 响应报文
Cookie技术
- 特点
  - Cookie提供了一种机制使得万维网服务器能够“记住”用户，而无需用户主动提供用户标识信息
  - Cookie是一种对无状态的HTTP进行状态化的技术
- 第三方Cookies：当用户访问一个网站（如example.com）时，该网站可能通过嵌入的广告或社交媒体插件请求另一个域名（如ads.example.net）设置Cookie，这些Cookie即为第三方Cookie
Web缓存技术
- 目的：提高万维网的效率
- 特点
  - 可位于客户机，也可位于中间系统上，位于中间系统上的Web缓存又称为代理服务器（Proxy Server）
  - Web缓存把最近的一些请求和响应暂存在本地磁盘中。当新请求到达时，若发现这个请求与暂时存放的请求相同，就返回暂存的响应，而不需要按URL的地址再次去因特网访问该资源
- 若Web服务器存储的文件发生了修改怎么办
  - 基于Last-Modified的协商缓存：服务器在响应请求时，返回资源文件最后被修改的时间（Last-Modified）。客户端在下次请求时，会携带上次请求返回的Last-Modified值，通过If-Modified-Since字段告诉服务器资源上次请求返回的最后被修改时间。服务器根据这个时间与资源当前的最后修改时间做对比，如果未改变，则返回304状态码，客户端继续使用缓存；如果时间不同，则返回新的资源。

DNS

域名系统概述
- ARPANET时期
  - hosts文件列出所有主机名和IP地址的对应关系
  - 由某个机构集中管理，其它主机定期下载最新的hosts文件
  - 网络规模不断扩展，接入的计算机数量不断增加，hosts文件集中管理的方式不再可行
- 域名系统DNS
  - 一个由大量DNS服务器按层次结构组织形成的分布式数据库，并配以允许主机查询分布式数据库的应用层协议
  - 功能：提供域名到IP地址的解析（翻译）
  - 特点
    - 使用C/S模式运行在端系统
    - 使用传输层的UDP，端口号为53
    - 使用者是其它应用程序
域名管理
- 顶级域名：ICANN
- 国家/地区顶级域名下的二级域名由该国/地区自行确定
  - .cn下的二级域名注册由中国互联网络信息中心（CNNIC）负责
- 三级域名注册由其所属二级域名机构负责
  - .edu.cn下三级域名注册由CERNET负责
域名服务器：每个域名服务器存储下级域域名服务器或主机的IP地址
- 根域名服务器提供所有顶级域名服务器的IP地址
  - 本地域名服务器无法解析时首先求助于根域名服务器
  - 全球有13台根域名服务器，大部分在美国
- 顶级域名服务器提供其下一级权威域名服务器的IP地址
- 权威域名服务器提供域内所有公共可访问主机的IP地址
  - 每一个主机都必须在某个权威域名服务器处注册登记
  - 因此权威域名字服务器知道其管辖的域名应当转换成什么IP地址
  - 权威域名服务器一般只解析本辖域的域名，通常由一个机构或组织维护
- 本地域名服务器：严格来说不属于DNS服务器的层次结构
  - 离主机最近
  - 每个ISP、或一个大学，甚至一个系都可以有一台本地DNS服务器，称为默认DNS服务器
  - 工作过程：本地DNS服务器起着代理作用
    - 主机的DNS查询报文发送给本地DNS服务器
    - 将来自主机的查询报文转发到DNS层次结构中
    - 将查询结果返回给主机
    - 缓存
域名解析
- 两种方式：从客户端到本地DNS服务器是递归查询，从本地DNS服务器到其他DNS服务器的查询采用迭代查询
  - 迭代解析
  - 递归解析
- DNS缓存
  - 作用：提高DNS的查询效率，并减轻根域名服务器的负荷和减少因特网上的DNS查询报文数量
  - 特点：如果某台主机改变了IP地址，需要等到所有TTL过期才能在世界范围内被更新
    - 由于域名到IP地址的映射关系并不是永久不变，为保持高速缓存中的内容正确，域名服务器应为每项内容设置计时器TTL并删除超过合理时间的项（例如，每个项目只存放两天）。
    - 顶级域名服务器内容通常在本地域名服务器缓存，因此根服务器通常不会被访问
    - 用户主机中也有高速缓存
      - 许多用户主机在启动时从本地域名服务器下载域名和IP地址的全部数据库，维护存放自己最近使用的域名的高速缓存，并且只在从缓存中找不到域名时才向域名服务器查询
      - 同理，主机也需要保持高速缓存中内容的正确性。
域名系统资源记录
- DNS：存储资源记录 (RR)的分布式数据库
- RR格式
  - 示例
DNS报文
- 报文类型
  - 查询请求（query）查询响应（reply）
  - 请求和响应的报文结构基本相同
- 报文格式
  - 基础结构部分
    - 事务ID：DNS报文的ID标识。对于请求报文和其对应的响应报文，该字段的值是相同的。通过它可以区分 DNS 应答报文是对哪个请求进行响应的
    - 标志：DNS报文中的标志字段
      - 请求还是响应？
      - 是否需要递归查询？
      - 是否支持递归查询？
      - 是否是所请求域名的权威域名服务器？
  - 问题部分
    - 用来显示DNS查询请求的问题，通常只有一个问题
    - 包含正在进行的查询信息，包含查询名（被查询主机名字）、查询类型、查询类
      - 查询名(name)：一般为要查询的域名，有时是IP地址，用于反向查询
      - 查询类型(type)：DNS查询请求的资源类型。通常查询类型为A类型，表示由域名获取对应的IP地址
      - 查询类(class)：地址类型，通常为互联网地址，值为1(IN)
  - 资源记录部分
    - 资源记录部分只有在DNS响应报文中才出现，包括回答问题区域字段、权威名字服务器区域字段、附加信息区域字段。这3个字段都采用资源记录的格式

电子邮件

体系结构：C/S
组成构件：用户代理，邮件服务器，以及电子邮件所需的协议
- 用户代理：用户与电子邮件系统的接口，又称为电子邮件客户端软件
- 邮件服务器：电子邮件系统的基础设施。因特网上所有的因特网服务提供者ISP都有邮件服务器，其功能是发送和接收邮件，同时还要负责维护用户的邮箱。
- 协议：邮件发送协议（例如SMTP）和邮件读取协议（例如POP3，IMAP）
SMTP协议
- 特点
  - 采用TCP作为传输层协议，服务端口号为25
  - 发件人和收件人的邮件服务器之间直接传输邮件
- 采用命令/响应交互方式
  - 命令：ASCII文本
  - 响应：状态码和短语
- 传输过程：连接握手、传输阶段、结束传输
邮件格式
- 报头由一些首部行组成
  - To:
  - From:
  - Subject:
- 消息体
  - 邮件正文：只能使用简单ASCII字符
邮件两阶段交付
- 第一阶段：采用SMTP协议将邮件投递到收信人的邮箱
- 第二阶段：采用邮件访问协议从邮箱中获取邮件
  - POP3(Post Office Protocol v3)，邮局协议第三版
  - IMAP(Internet Mail Access Protocol)，Internet邮件访问协议
  - Webmail(HTTP)，基于Web的电子邮件

P2P和文件共享

P2P工作方式
- 没有总是在线的服务器
- 每个用户既从别的用户获得服务，也向其他用户提供服务
P2P网络实例
- 文件共享（BitTorrent）
- 流媒体（迅雷看看）
- IP电话（Skype）
BitTorrent协议：一种用于文件分发的流行P2P协议
- 特点
  - 洪流（Torrent）：所有参与某个文件分发的对等方集合（数百或数千个）
  - 追踪器（Tracker）：跟踪Torrent网络中的对等方
  - 文件被划分成固定长度的文件块集合（典型长度256KB）
  - 同时上传/下载文件块，可随时离开洪流
- 过程
  - 给定时刻，不同的对等方拥有文件块的不同子集
  - 周期性地询问每个邻居他们拥有的数据块列表（L个邻居，L个数据块列表）
  - 向邻居请求缺少的数据块
- 策略
  - 问题1：应当优先请求哪些块？
    - 根据文件块在邻居中的副本数量，最稀有的优先
    - 目的：尽快增加稀缺块的数量，均衡每个块的副本数量
  - 问题2：应当响应哪些对等方的请求？
    - “一报还一报”（tit-for-tat）
      - Alice选择向其发送数据最快的4个邻居（Top4），响应他们的请求，每隔10秒重新评估
      - 每隔30秒，随机选择另外一个对等方，并响应其请求
      - 允许新的对等方得到文件块，新的对等方也可能成为Alice的Top4
文件共享
- C/S
  - 从一台服务器分发一个大小为F的文件给N个用户
- P2P

内容分发网络

视频分发
- 视频：一系列的图片按照一定的速率进行播放（例如 24 帧/秒）
- 图片：像素的阵列
- 编码：使用图片内部和图片之间的冗余来减少用于编码图像的位
  - 空间上（图片内部）
  - 时间上（一张图片与下一张图片之间）
  - 编码方式
    - CBR（constant bit rate）：恒定比特率编码
    - VBR（variable bit rate）：可变比特路编码
DASH（Dynamic, Adaptive Streaming over HTTP）
- 是一种自适应流媒体传输协议，它允许视频在不同的网络条件下动态调整质量
- 核心思想
  - DASH通过将视频编码为多个不同质量的版本，并在播放时根据用户的网络带宽和设备性能动态选择最合适的视频块（分块传输的数据）
- 过程
  - 服务端
    - 将视频文件分成多个块
    - 每个块以多个不同的速率编码
    - 不同的速率编码存储在不同的文件中
    - 在各个CDN节点上复制文件
    - manifest file:为不同的块提供url
  - 客户端
    - 定期估计服务器到客户端的带宽
    - 请求 manifest, 一次一个请求快
    - 在给定当前带宽的情况下选择最大编码速率
    - 在不同的时间点（取决于当时的可用带宽）和不同的服务器上选择不同的编码速率
- 客户端的“智能” :
  - 何时请求块（以避免缓冲区耗尽或溢出）
  - 请求什么编码速率（可用带宽越多，质量越高）
  - 在哪里请求块（可以从“接近”客户端或具有高可用带宽的URL服务器请求）
内容分发网络CDN（Content Delivery Network，or Content Distribution Network）
- 基本思想
  - 在分布在多个地理位置的服务器上存储资源的副本，从而就近为用户提供服务，这些服务器节点形成的网络称为CDN
- 优势
  - 降低响应时延，避免网络拥塞
  - 避免原始服务器过载及防止DDoS攻击
  - 分布式架构，具有良好的可扩展性
  - 对用户透明，无需用户感知
- 关键问题
  - CDN节点部署在哪里？
    - 深入接入网：将CDN服务器深入部署到很多接入ISP网络的内部，距离用户近
    - 邀请做客：在少量（例如10个）靠近接入网的关键位置（例如IXP），建造大集群，邀请到ISP做客
  - 在CDN节点上缓存资源的副本，缓存哪些副本呢？
    - 拉高速缓存：用户访问的资源不在CDN节点上时，从中心服务器拉取
    - 推高速缓存：在非高峰时段将高频内容推送到CDN节点上
  - 如何进行重定向，将用户请求调度到较近或负载较轻的CDN服务器？
    - CDN的权威DNS服务器需要收集CDN服务器的位置和负载情况，并负责决策CDN节点

网络安全

网络安全概述
- 机密性(confidentiality): 仅有发送者和希望的接收者能理解传输的报文内容
  - 发送者加密报文
  - 接收者解密报文
- 验证(authentication): 发送者和接收者需要验证双方的身份
- 完整性(integrity): 发送者和接收者想要确保通信内容在传输过程中未被改变
- 可达与可用性(access and availability): 服务和数据对于用户是可达且可用的
密码学基础
- 密码攻击场景
  - 唯密文攻击:仅仅知道密文
  - 已知明文攻击:掌握部分明文和对应密文
  - 选择明文攻击:攻击者拥有加密机的访问权限，可以构造任意明文所对应的密文
  - 选择密文攻击:攻击者掌握对解密机的访问权限，可以选择对攻击有利的特定密文及其对应的明文
- 加密方法
  - 对称密钥加密：需要共享相同的密钥
    - DES (Data Encryption Standard)
      - 特点
        56-bit 对称密钥
        64-bit 明文输入
        分组密码与密码块链接
      - 安全性：暴力破解是可行的
      - 提升
        3DES：用不同的3组密钥进行3次加密
      - AES (Advanced Encryption Standard)
        特点
        按128 bit块进行处理
        支持128, 192, 或 256 bit 密钥
        安全性：暴力破解不可行
  - 公钥加密：发送者和接收者不需要共享密钥
    - 特点
      - 加密公钥大家都知道。
      - 解密私钥只有接收者自己知道。
    - RSA算法：最经典的公钥加密算法
      - 安全性：依赖于目前没有已知的算法可以快速进行一个数的因数分解（大数分解难题）。
      - 加密过程
验证与消息完整性
- 消息摘要
  - 问题：对于长消息加解密时间计算开销大
  - 目标：生成一个固定长度，易于计算的数字指纹
  - 方法
    - 利用哈希函数 H, 得到消息摘要（指纹）, H(m)
    - 给定 x, 计算上不可能找到m 使得 x = H(m)
      - 典型hash算法：MD5和SHA-1
- 验证与消息完整性流程
- 中间人攻击
  - 问题出在哪？公钥的安全性！
- 公钥验证机构CA：将公钥绑定到实体上
  - 流程
    - 实体 (个人，网站，设备) 向CA提供身份证明并申请公钥
    - CA 生成E的身份证书并和E公钥绑定
  - 示例：当Alice想知道Bob公钥时
    - 获取Bob证书(Bob or elsewhere)
    - 发送Bob证书给CA获取Bob的公钥
安全电子邮件
Transport-layer security (TLS)
- 特点
  - 传输层上被广泛采用的安全协议
  - 几乎所有浏览器都支持：HTTPS (443)
- 功能
  - 机密性：通过对称密钥
  - 完整性：通过密码散列（hash）
  - 验证：通过公钥加密
- 过程
  - 握手过程：Alice，Bob 使用他们的证书、私钥来验证对方身份，并生成或交换共享密钥
    - 具体过程
      - Bob 和 Alice建立TCP连接
      - Bob 验证 Alice 身份
      - Bob 给 Alice 发送一个主密钥 (MS), 用于后续本TLS连接的所有密钥生成
  - 密钥生成：Alice，Bob 使用共享密钥生成一系列后续需要的密钥
    - 四个密钥
      - Kc：客户端给服务端的会话数据传输密钥
      - Mc：客户端到服务端的数据会话HMAC密钥
      - Ks：服务端给客户端的会话数据传输密钥
      - Ms：服务端到客户端的数据会话HMAC密钥
    - 密钥是由密钥生成函数 (KDF)生成：通过主密钥MS和一些随机数、参数等
  - 数据传输：进行安全数据传输
  - 关闭连接：安全关闭连接
网络层安全：IPSec
- 提供报文级的加密、验证、完整性保护
  - 对于用户流量和控制流量（如DNS）都可以提供
  - IPSec是面向连接的
- 两种模式
  - 传输模式：只有报文负载部分被加密
  - 隧道模式：整个报文被加密（加密后封装在了一个新的报文中，重新加上新的IP头）
- 两种主要的协议
  - 鉴别首部协议AH
    - 提供源验证和数据完整性服务，但不提供机密性服务
  - 封装安全性载荷协议 (ESP)
    - 提供了源验证、数据完整性、机密性服务
    - 比AH使用更广泛
- 安全关联security association (SA)
  - 发送数据前，在发送和接收实体间建立一个SA
  - 双方维护SA的状态信息
运行安全
- 防火墙
  - 将组织内部网络与更大的互联网隔离开来，允许一些数据包通过，阻止其他数据包通过
  - 作用
    - 阻止一些攻击如DDoS
    - 防止非法修改/访问内部数据
    - 访问控制，只允许授权访问内部网络
  - 三种类型
    - 无状态报文过滤
      - 内部网络通过路由器防火墙连接到Internet
      - 过滤器逐个报文进行决策，依据:
        source IP address, destination IP address
        TCP/UDP source, destination port numbers
        ICMP message type
        TCP SYN, ACK bits
    - 有状态报文过滤
      - 会追踪每一个TCP连接的状态
      - 跟踪连接设置（SYN，FIN）：确定是否传入，传出数据包“有意义”
    - 应用网关
      - 要求所有Telnet用户通过网关进行Telnet
      - 对于授权用户，网关建立到目的主机的Telnet连接
      - 路由器过滤器阻止所有非来自网关的Telnet连接
- 入侵检测IDS：深度报文检测deep packet inspection
  - 会关注报文的内容
  - 也会关注报文间的关系
    - 端口扫描
    - DoS攻击