计算机网络

• 2024考研「计算机网络」笔记&复习要点。

综合考点

传输时间、速率

• 时延积带宽（第一个比特到终点时已经发出了多少） = 传播时延 * 带宽
• 发送时延：分组长度/带宽
• 传播时延：距离/电磁波速率
• 处理时延：存储转发所需时间
• 排队时延：路由器中排队等待时间
• 总时延
  • $(n-1)$*发送时延 + 发送时延 + 传播时延 + 中间设备*（发送时延 + 传播时延）
  • 也就是前n-1个分组一直发+最后一个分组的完整传播时间

模型设备

• 应用层，表示层：编码，会话层：会话管理

• 集线器（Hub）：不隔离冲突域和广播域

• 交换机：隔离冲突域，不隔离广播域

物理层

概念、模型

• 特性
  • 机械、电气、功能、规程
• 通信方式
  • 单向、半双工（两条）、全双工（两条）、串行、并行、同步、异步
• 速率
  • 码元传输速率（波特率）：单位时间码元个数（脉冲/变化次数）
  • 信息传输速率（比特率）：单位时间二进制码元个数

信道复用

1. 静态划分
   • 时分复用：时间片均分
   • 频分复用：占用不同频率带宽
   • 码分复用：采用不同编码
   • 波分复用
2. 动态划分
   • 纯ALOHA协议
   • 时隙ALOHA协议
   • CSMA协议

数据链路层

点对点信道

1. 功能：向网络层提供服务，将网络层数据可靠传输到相邻节点的目标网络层
2. 分类：点对点、广播
3. 问题：
   • 封装成帧：添加首尾部和最大传输单元MTU
   • 透明传输：内容二进制安全
   • 差错检测：保证可靠传输
4. PPP协议
   • 点对点、全双工、没最短帧
   • 满足：简单、封装成帧、透明传输、多种网络层协议/类型链路、差错检测、MTU（1500）、压缩/地址协商
   • 不满足：纠错、流量控制、编序号、多点序路
   • 功能
     • 将IP数据包封装到串行链路
     • 链路控制协议LCP：建立维护数据链路连接
     • 网络控制协议NCP：不同网络层协议由NCP配置，建立网络层逻辑链路
5. 差错检测CRC：
   • 计算
     • $G(x)$阶为$g$，m后面补$g$个0
     • 除以$G(x)$，余数便是$r$（高位的0要保留，共$g$位）
   • 校验
     • m位的帧和r位的序列（帧检验序列FCS）
     • 若$G(x)$整除m+r，则无差错

广播信道

1. 所有主机共享、总线型、星型、以太网
2. 局域网LAN
   • 特点：范围小、专门介质、延迟低、分布式控制广播通信
   • 拓扑：星型、环型、总线型、树型
3. 以太网
   • 总线型、CSMA/CD、803.3
   • 无连接、不可靠服务（不编号、不确认、错丢弃、高层纠错）、无差错接收
4. CSMA/CD（总线型、半双工网络、以太网）
   • 发送前/时监听电压，有碰撞则停
   • 争用期：2$\tau$（传播时延*2）
   • 最短帧长：总传播时延数据传输速率2 （64B）
   • 二进制指数退避
     • 选择$r\in[0,2^k-1]$，其中$k=\min(\text{次数}, 10)$，等待$r\cdot2\tau$
     • 重复16次还不成功则向高层报告
5. 以太网MAC帧
   • MTU 1500B
   • 最短数据：64B-6-6-2-4 = 46B
   • 前导码（不算入）+目的地址+源地址+类型+数据+（FCS/CRC）
6. 以太网扩展
   • HUB/集线器：物理层扩展
   • 网桥/交换机：链路层扩展，分离冲突
   • 路由器：网络层扩展，分离广播/冲突
7. 交换机
   • 分类：直通：查完就转发，存储转发：缓存检查正误再转发
   • 自学习
     • A->B使用1端口，写入转发表并广播给其他端口
     • 其他向A发送时，直接向1端口转发

协议

• 无线局域网802.11
  • 地址一：接收端的MAC
  • 地址二：发送方的MAC
  • 地址三：源/目的MAC
  • 地址三得看是往AP发还是AP发出的，主机发的话就是目的MAC，AP发出的话就是携带源MAC

网络层

概述

1. 向上提供灵活简单、无连接。尽最大努力交付的数据包
   • 运输层负责可靠交付（差错处理、流量控制）
   • 运行灵活、造价低
2. 分组从源传输到目的端、为分组交换网上不同主机提供通信服务
3. 传输单元是数据报
4. 两个服务
   • 面向连接的虚电路：逻辑电路
   • 无连接的数据报

   • 	虚电路	数据报
     思路	网络负责可靠	主机负责可靠
     连接	有	无
     终点地址	建立后使用虚电路号	使用完整地址
     分组转发	同一条路同一路由转发	每个分组独立选择路由
     故障	通过故障虚电路均不工作	故障结点丢失分组，路由改变
     分组顺序	有序	无序
     差错/流量	网络/主机负责	主机负责

5. 数据层和控制层
   • 数据平面
     • 具体处理转发过程
   • 控制平面
     • 控制和管理网络协议的运行
     • 传统方法：路由选择处理器
     • 现代方法：SDN软件定义网络 -> 远程控制器
     • 特点
       • SDN对开发者提供的接口称为北向接口
       • SDN控制器与转发设备提供的接口称为南向接口

IP

• IP = 网络号 + 主机号
• 主机号全0代表网络本身，全1为广播地址
• 127.x.x.x 为环回自检地址
• 0.0.0.0 代表本网络上的本主机，不能作为目的地址
• 255.255.255.255 代表整个TCP/IP广播地址（实际上由于隔离等效为本网络广播地址）
• MAC地址：硬件地址、不可修改、局域网内链路层使用，IP用于跨网通信
• ARP协议（IP到MAC的映射）
  • 有缓存
  • 广播MAC为全FF，每个主机都会收到该ARP请求
  • 只有特定主机（指定IP）收到请求后回复ARP响应，包含MAC和IP
• IP数据报
  • 版本
  • 首部长度：20B——60B（单位4B）
  • 总长度：65535B（单位1B），注意成帧时还有MTU
  • 标识
  • 标志：3位、低位MF=1之后有无分片，中位DF=0允许分片
  • 片偏移：单位8B，所以分片报文数据长度得是8整数倍
  • TTL、协议、校验和、源、目的
  • 分片：先计算数据部分（X-20B）、再在（MTU-20B）中找8整数倍，计算偏移，MF=1（最后一片除外），DF=0
• 分组转发
  • 基于终点转发
    • 相同网络直接发送
    • 不同网络查找目的网络进行交付
  • 最长前缀匹配
    • CIDR查表时按照最长前缀匹配查找
    • 失败时转发给默认路由0.0.0.0/0或报错
  • 二叉线索树，类似Trie

子网划分、超网聚合

• IP = 网络号 + 子网号 + 主机号

• 子网划分为内部事件，对外表现为无划分

• 题目问子网划分时只需记住：所有子网不重叠、不遗漏IP即可

• 子网掩码

  • 与IP与操作得网络号

• 无分类编址CIDR

  • IP = 网络前缀 + 主机号
  • 地址数$2^k$，实际可用$2^k-2$
  • 查表时按照最长前缀匹配查找

• CIDR超网

  • 网络前缀最长相同部分进行聚合为一个新的大CIDR地址
  • 减少路由器信息交换，提高性能

ICMP

• 差错报告报文
  • 终点不可达，路由器/主机无法交付
  • 源点抑制，由于拥塞而丢弃
  • 时间超过，TTL=0
  • 参数问题，首部字段有误
  • 重定向，返回改变的路由报文
• 询问报文
  • 回送请求/回答报文
  • 时间戳请求/回答报文
  • 地址掩码请求/回答报文
• 应用
  • PING：测连通性，工作在应用层（但未使用TCP/UDP）
  • Traceroute：路由跟踪，工作在网络层

路由选择协议

1. 分类
   • 内部网关协议：RIP、OSPF、IGRP、IS-IS
   • 外部网关协议：BGP
2. RIP
   • 概念
     • 每个路由器维护从它到其他目的网络的距离记录
     • 好的路由就是距离最小
     • RIP允许一条路径最多15个路由器，距离=16代表不可达（减少网络拥塞）
     • 任意两个RIP路由器之间每30s广播一次RIP更新信息
     • RIP不支持子网掩码的RIP广播（RIP网络每个子网掩码必须相同）
   • 特点
     • 仅和相邻路由交换信息
     • 交换当前全部表项
     • 按固定时间交换
     • 若干次交换后，每个路由器都知道到达本AS的任一网络的最短距离和下一跳地址
   • 距离向量算法
     • 修改相邻路由器X发来的RIP报文表项
       • 下一跳改成X
       • 距离+1
     • 原路由表没有该网络，则添加
       • 若有且下一跳是X，则替换
       • 若有但下一跳不是X，则比较距离，较少则更新
     • 优缺点
       • 优点：简单、开销小、收敛快
       • 缺点：
         • 限制了网络规模，最大距离15
         • 交换完整路由表，网络越大、开销越大
         • 坏消息传得慢，慢收敛问题，即故障需要等待超时才知道
   • 重点
     • RIP是应用层协议，使用UDP/520端口
     • RIP路径时间不一定最短，但跳数最少
3. OSPF
   • 特点
     • 使用分布式链路状态协议
     • 洪泛法向AS所有路由器发送消息（每个路由器都会受到）
     • 信息为本路由器和相邻路由器链路状态
     • 仅链路状态变化时发送
     • 所有路由器建立一个链路状态库，全网拓朴图
   • 链路状态路由算法
     • 初始化
       • 先发现邻结点（HELLO问候分组），了解邻结点网络地址
       • 设置到它邻居的成本度量metric
       • 构造DD数据库描述分组，向邻站给出自己的链路状态更新数据库的链路摘要
       • 邻站接收后，如果DD中摘要自己有，则不做处理，没有或需更新则发送LSR链路状态请求分组，请求详细信息
       • 收到LSR后发送LSU链路状态更新分组回去
       • 更新完毕后返回LSAck链路状态确认分组确认
     • 运行时
       • 有路由器链路状态变化，洪泛发送LSU，其他返回LSAck
       • 使用Dijkstra根据自己链路状态数据库构造到其他节点的最短路
   • OSPF将AS划分为更小区域，一个区域内最好不朝过200个路由器
   • 重点
     • 网络层协议，IP数据报发送
     • 每隔30min刷新一次数据库链路状态
     • 每个路由器只涉及相邻路由器联通状态，与互联网规模无直接联系，大网络比RIP号
     • 不存在坏消息传的慢，收敛速度快

传输层

概念和UDP

1. 提供进程间逻辑通信（端到端）
2. 复用：发送方不同进程可使用同一传输层协议传送数据
3. 分用：接收方剥去报文首部后能把数据正确交付到目的进程
4. 对收到的报文进行差错检测
5. 面向连接的TCP和无连接的UDP
6. 寻址与端口
   • 端口是传输层的SAP，65536个
   • 服务端端口
     • 熟知端口：0~1023
     • 登记端口：1024~49151
   • 客户端端口：49152~65535（临时端口）
   • FTP/21，TELNET/23，SMTP/25，DNS/53，TFTP/69，HTTP/80，SNMP/161
7. UDP
   • 无连接、最大努力交付，不保证可靠
   • 面向报文、适合一次少量数据的网络应用
   • 无拥塞控制、适合实时通信
   • 首部开销小：8B（源端口+目的端口+UDP长度+校验和）
   • 校验和：伪首部（12B）+首部+数据 计算，反码求和再求反

TCP

1. 面向连接
2. 每条TCP只能有两个端口、点对点通信
3. 提供可靠交付、无差错、不丢失、不重复、按序到达
4. 全双工通信（发送/接收缓存实现）
5. 面向字节流
6. 首部：20B + 可选首部（不定长）
7. 可靠传输
   • 校验：同UDP
   • 序号机制
   • 确认机制：收到后返回ACK，确认号为下一个希望收到的报文
   • 重传机制
     • 超时：每个报文都有计时器，过期则重传
     • 冗余ACK：连续回复3次A的冗余ACK，则立即重传A+1报文。
8. 停止等待：信道利用率$T_d/(T_d+RTT+T_a)$，$T_d$为发送时间，$T_a$为接收时间
9. 后退N帧（GBN）
   • 无须等待ACK，但发送N帧后若N个帧的前一个超时后都还没ACK，则重传出错后的N个帧。
   • 接收方只允许按序接收
   • 事件
     • 上层调用：发送窗口已满返回上层
     • 收到ACK：累积确认，无须每次ACK
     • 超时事件：重发送已发送但未确认的帧
     • 接收方：按序接收，其他丢弃，没有缓存，丢弃帧时重发最近按序接受的ACK
   • 发送窗口：$1\le W_T \le 2^n-1$
10. 选择重传
    • 窗口：$W_T = W_R = 2^{n-1}$
    • 事件：
      • 上层调用：窗口满则返回或缓存
      • 收到ACK：窗口移至最小未被确认帧处，并发送窗口内未发送的帧
      • 超时：每个帧有计时器，超时重传该帧
      • 接收方：
        • 接收窗口内的帧，返回ACK，移动窗口并按序交付给上层
        • 小于窗口下界，则返回ACK
        • 其他忽略并丢弃

流量控制、拥塞控制、连接管理

1. 连接建立

   1. $C\rightarrow S$，SYN=1，seq=x，$C$进入SYN-SENT同步已发送状态
   2. $S\rightarrow C$，SYN=1,ACK=1，seq=y，ack=x+1，$S$进入SYN-RCVD同步收到状态
   3. $C\rightarrow S$，ACK=1，seq=x+1，ack=y+1，$C$进入ESTABLISHED已建立连接状态
   • 3若未携带数据不消耗序号
   • 3发送后可立即发送数据，所以TCP连接耗时是1RTT

2. 连接关闭

   1. $C\rightarrow S$，FIN=1，seq=x，$C$进入FIN-WAIT-1终止等待状态
   2. $S\rightarrow C$，ACK=1，seq=y，ack=x+1，$S$进入CLOSE-WAIT状态，$C$收到后进入FIN-WAIT-2状态
   3. $S\rightarrow C$，FIN=1,ACK=1，seq=w，ack=x+1，$S$进入LAST-ACK状态
   4. $C\rightarrow S$，ACK=1，seq=x+1，ack=w+1，$C$进入TIME-WAIT状态，再等待2MSL进入CLOSED状态
   • 2发完后服务器会继续发送剩余数据
   • 2发完后没数据会立即发送3，所以S最快1.5RTT进入CLOSED
   • 4后还需等待2MSL，所以C最快1RTT+2MSL进入CLOSED

3. 流量控制

   • 接收方根据缓存大小动态调整发送方窗口
   • 每次ACK中包含窗口字段rwnd设为剩余能接受的数据量
   • 发送方收到ACK后设置发送窗口为rwnd值
   • rwnd=0代表启动计时器，超时后发送一个零窗口探测报文，接收方收到后给出新的rwnd值
   • 发送窗口=0时，之前报文超时可重传，但不能发新的报文
   • 和链路层流量控制区别
     • 传输层控制端到端用户之间的流量，窗口动态变化
     • 链路层控制相邻节点的流量，窗口固定

4. 拥塞控制

   • 和流量控制区别：拥塞控制为全局性、流量控制为点对点
   • 拥塞窗口：发送方根据拥塞程度设置的窗口值
   • 发送窗口：$\min(\mathrm{rwnd}, \text{拥塞窗口})$
   • 慢开始算法：
     • cwnd=1 MSS，每收到一个ACK，cwnd += 1
     • 增大到慢开始门限后改用拥塞避免算法
     • 初值小，每个RTT窗口指数倍增，指数倍增时不会越过门限值（因为以RTT的视角是翻倍，但到达门限后变成拥塞避免）
   • 拥塞避免算法：
     • 每经过一个RTT，cwnd+=1
     • 无论是慢开始还是拥塞避免阶段，发现拥塞将cwnd/2作为新的门限值，并将cwnd=1
   • 快重传：三次重复ACK后立即重传
   • 快恢复：三个重复ACK后，门限值设为cwnd/2，cwnd从新的门限值开始

应用层

框架

• C/S模型
  • 单一服务器，永远运行，随时提供服务，固定地址/域名
  • 多客户机，间歇接入网络，动态IP，不能与其他客户机直接通信
• P2P模型
  • 不存在永远在线的服务器
  • 每个主机既可以提供服务，也可以请求服务
  • 任意系统/节点间可以直接通信
  • 节点间间歇性接入网络
  • 节点可能改变IP
  • 优点
    • 可扩展性好
    • 网络健壮性强

DNS（53/UDP）

• 顶级域名（国家、通用、基础解析arpa）、二级域名（政府、公司、行政区）、...
• 递归方式（让S返回最终结果）
  • 本地 $\rightleftarrows$ 根域名 -> 顶级 -> 权限
• 迭代方式（自己一级一级请求）
  • 本地 -> 根域名
  • 本地 -> 顶级
  • 本地 -> 权限
• 主机向本地域名服务器使用递归方式
• 本地域名服务器向根域名服务器使用迭代方式
• DNS服务器都有缓存，每条数据也有相应TTL
• 解析使用UDP，但区域传输使用TCP

FTP（21/TCP）

• 功能
  • 基于C/S协议模型，使用TCP实现可靠传输
  • 不同种类主机之间的文件传输能力
  • 以用户权限管理的方式提供远程FTP管理能力
  • 以匿名FTP的方式提供公用文件共享
• 一个主进程，n个从属进程复制处理单个请求
• 控制连接始终保持、数据连接随开随关
• 传输模式
  • 主动方式：使用20/TCP传输数据
  • 被动方式：协商端口（>1024）传输数据

电子邮件

• SMTP（25/TCP）
  • 只向邮件服务器发送邮件
  • 通过MIME扩展内容
• POP3（110/TCP）
  • 只从邮件服务器读取邮件
• IMAP（TCP）
  • 读取邮件
• Hotmail、Gmail同邮箱服务器之间使用HTTP，不同才使用SMTP

万维网

• 标准
  • 统一资源定位符（URL）：唯一标识
  • 超文本传输协议（HTTP）：应用层协议，TCP
  • 超文本标记语言（HTML）：标记性语言
• HTTP（80/TCP）
  • 无状态无连接的协议
  • 非持久（用完就断开TCP、每次请求需2RTT额外时间）、持久连接（HTTP/1.1）
    • 持久非流水型：每个对象1RTT开销
    • 持久流水型：总共1RTT开销
  • 报文
    • 请求报文
      • 请求行：方法 URL 版本
      • 请求头：名字：值
      • 空行
      • 请求体
    • 响应报文
      • 状态行：版本 状态码 短语
      • 响应头：名字：值
      • 空行
      • 响应体

其他常见端口

• TELNET：23/TCP
• TFTP：69/UDP
• SNMP：161/UDP