计算机网络复习笔记
第一章 计算机网络和因特网
分组交换和电路交换
两种电路交换：频分复用（FDM）和时分复用（TDM）
分组交换的电路交换的比较：
分组交换提供了比电路交换更好的带宽共享，比电路交换更简单，更有效，成本更低
趋势：分组交换
网络结构
接入ISP：为端系统提供有线或无线连接，包括DSL、电缆、FTTH、WiFi、蜂窝等多种接入技术。
第一层ISP：全球承载ISP
IXP：为多个ISP实现共同对等
内容提供商：承载特定服务器主机的流量，如谷歌
分组交换时延、丢包、吞吐量
- 处理时延、排队时延、传输时延、传播时延
- 流量强度
协议分层
| 网络层 | 作用范围 | 分组名称 | 协议 | 特点 |
|---|---|---|---|---|
| 应用层 | 多个端系统 | 报文 | HTTP、SMTP、FTP、DNS、POP3 | 通过套接字向网络发送和接收报文 |
| 运输层/传输层 | 应用程序端点间 | 报文段 | （只有）TCP、UDP | TCP提供拥塞控制，UDP没有可靠性、没有流量控制、没有拥塞控制 |
| 网络层 | 主机间 | 数据报 | IP、ICMP、ARP、RARP | |
| 链路层 | 帧 | |||
| 物理层 |
恶意软件
- 病毒：需要某种形式的用户交互来感染用户设备
- 蠕虫：无需任何明显用户交互就能进入设备
第二章 应用层
进程通信
套接字（socket）
进程通过套接字这一软件接口向网络发送和接收报文
套接字是建立网络应用程序的可编程接口，因此也被称为应用程序编程接口（API）
进程寻址
IP地址标识主机，端口号指定运行在接收主机上的接收进程（接收套接字）。
运输服务
对应用程序服务要求分类的四个角度
- 可靠数据传输
- 吞吐量
- 定时
- 安全性
TCP服务和UDP服务
TCP服务
面向连接服务
三次握手建立TCP连接，连接全双工（双方进程可以同时进行报文收发）
可靠服务
能够实现无差错，按适当顺序交符所有数据
拥塞控制机制
UDP服务
轻量级传输协议，仅提供最小服务，无握手过程，不可靠数据传输，无拥塞控制
HTTP
持续连接和非持续连接
非持续连接的响应时间：两个RTT+服务器传输HTML文件的时间
HTTP请求报文
第一行叫请求行，其后继的行叫首部行
HTTP响应报文
一个初始状态行，六个首部行，实体体
常见状态码
Web缓存/代理服务器
通过缓存的hit rate计算加入缓存后的流量强度
条件GET
例：
电子邮件
SMTP协议
- 使用持续连接，是一个“推协议”（相较于HTTP协议的“拉协议”）
- 使用7比特ASCII码格式
- 把所有对象放在一个报文中
邮件访问协议
POP3
POP3服务器不在POP3会话中携带状态信息
IMAP
可以使用一个在远程服务器上的层次文件夹，允许用户代理只读取报文的一部分
HTTP
使用Web服务器收发电子邮件（但邮件服务器之间的发送和接收仍然是SMTP）
DNS
DNS提供的服务
主机名到IP地址的转换
主机别名（相较于规范主机名）
邮件服务器别名（同上）
负载分配
对于冗余的Web服务器，每台服务器有不同的IP地址，在DNS请求中循环响应这些地址次序来分配负载
集中式DNS服务器设计的问题
- 单点故障
- 通信容量
- 远距离的集中式数据库
- 维护
分布式、层次数据库
两种查询方法
- 递归查询
- 迭代查询
DNS缓存
DNS记录
资源记录是一个4元组:(Name, Value, Type, TTL) TTL是该记录的生存时间
Type有以下几类：
- A，则Name是主机名，Value是IP地址
- NS，则Name是个域，Value是可获取该域IP地址的，权威DNS服务器的主机名
- CNAME，则Value是别名为Name的主机的规范主机名
- MX，则Value是别名为Name的邮件服务器的规范主机名
DNS报文
查询和回答报文格式一致
P2P
文件分发
简化假设：所有瓶颈都在网络接入线路，且服务器和客户所有上传和下载访问带宽能被全部用于分发该文件。
客户 - 服务器体系结构：
P2P体系结构：
BitTorrent
- 最稀缺优先
- “一报还一报”
第三章 运输层/传输层
多路复用和多路分解
多路分解：将运输层报文段中的数据交付到正确的套接字
多路复用：为每个数据块封装上首部信息，从而生成报文段，然后将报文段传递到网络层
要求：套接字有唯一标识符，且每个报文段有特殊字段（源端口号字段和目的端口号字段）来指示该报文段要交付到的套接字
周知端口号：0~1023，保留给如http，ftp之类的周知应用层协议
TCP套接字（面向连接）：
由四元组识别（源IP地址，源端口号，目的IP地址，目的端口号）
无连接运输：UDP
UDP无需建立连接、无连接状态
分组首部开销小（8字节，相较于TCP首部20字节）
UDP报文结构（IP地址保存在网络层IP协议里，因此报文段没有IP地址）
UDP检验和
相比于原码，补码，二进制反码循环移位加法求和具有以下优点：不依赖系统是大端小端。即无论你是发送方计算机或者接收方检查校验和时，都可直接通过上面的算法得到正确的结果。
可靠数据传输(rdt)原理
rdt1.0 无受损、无丢包，仅有发送接收
rdt2.0 考虑比特受损，引入ACK/NAK重传机制
rdt2.1 考虑ACK/NAK也会损坏 接收方受到损坏的ACK/NAK时重发
rdt2.2 用冗余ACK代替NAK
rdt3.0 考虑丢包，引入定时重传机制
回退N步（GBN）
使用序号、累计确认、检验和、超时/重传操作
选择重传（SR）
接收方将确认一个正确接收的分组而不管其是否按序，失序的分组将被缓存。
面向连接的运输：TCP
TCP连接：
最大报文段长度MSS和最大传输单元MTU
基于MTU设置MSS，如以太网和PPP链路层协议具有1500字节的MTU，则MSS要保证一个TCP报文段加上TCP/IP首部长度（40字节）适合单个链路层帧，因此MSS典型值为1460字节。
TCP报文段结构（20字节）
确认号和序号
主机A填充进报文段的确认号是主机A期望从主机B收到的下一字节的序号
TCP累积确认
RTT估计与超时
可靠数据传输
超时间隔加倍
快速重传
3个冗余ACK触发快速重传
流量控制
接收窗口twnd：给发送方一个指示：接收方还有多少可用的缓存空间
TCP连接管理
三次握手
第一次确认发送方发送能力，第二次确认接收方接收、发送能力，第三次确认发送方接收能力，第三次可以承载有效载荷
四次挥手
TCP状态
拥塞控制原理
两种拥塞控制方法
端到端拥塞控制
将TCP报文段丢失或三次冗余ACK作为网络拥塞的迹象
网络辅助的拥塞控制
路由器向发送方提供关于网络拥塞情况的显示反馈
与流量控制的区别
拥塞控制是一个全局性的过程，涉及到所有的主机、路由器，以及与降低网络性能有关的所有因素。 拥塞控制是防止过多的数据注入到网络中，可以使网络中的路由器或链路不致过载，是一个全局性的过程。 流量控制是对点对点通信量的控制，是一个端对端的问题，主要就是权衡发送端发送数据的速率，以便接收端来得及接收。
TCP拥塞控制
慢启动
拥塞窗口cwnd以一个MSS开始，每过一个RTT，cwnd就翻倍。
即TCP发送速率起始慢，但在慢启动阶段以指数增长。
拥塞避免
对于丢包事件，TCP将cwnd减半（为了弥补三个冗余ACK，再加上3个MSS效果更好）
快速恢复
ssthresh（慢启动门限）将被设置为0.5cwnd（TCP Reno下将被设置为0.5cwnd+3），在达到ssthresh前指数增长，达到ssthresh后线性增长，每个RTT增加一个MSS
加性增、乘性增
第四章 网络层：数据平面
转发和路由选择
- 转发是指将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作。
- 路由选择是网络范围的过程，以决定分组从源到目的地所采取的端到端路径。
虚电路网络和数据包网络
虚电路网络：仅在网络层提供连接服务
数据包网络：仅在网络层提供无连接服务
转发表的最长前缀匹配规则
路由器交换结构
经内存交换
最早、最传统的交换结构
吞吐量受限于若内存带宽，若内存带宽为每秒可写进内存或从内存读出B个分组，则总的转发吞吐量必然小于B/2
经总线交换
一次只有一个分组能够跨越总线，交换带宽受总线速率限制
经互联网络交换
纵横式网络能够并行转发多个分组，然而若来自两个不同输入端口的两个分组其目的地为相同的输出端口，则一个分组必须在输入端等待，因为某个时刻经给定总线仅有一个分组能够发送。
路由器输出端口
排队
缓存大小计算
分组调度程序
先来先服务（FCFS）调度
RR调度
加权公平排队（WFQ）
主动队列管理（AQM）
- 弃尾
- 随机早期检测（RED）
IP协议
网络层协议
- 路由选择协议：路径选择（RIO、OSPF、BGP）
- IP协议：编制规则、数据包格式、分组处理规则
- ICMP协议：差错报告、路由器“信令”
IP数据报结构
- 数据包长度为16比特，于是IP数据包的理论最大长度为65535字节，但实际上很少超过1500字节
- 标识、标志、片偏移与IP分片有关，IPv6不允许对分组分片
- 寿命（TTL）每当数据报由一台路由器处理时减1，若减为0 则必须丢弃
- 首部检验和：将首部每两个字节当作一个数，用反码计算对这些数求和，将该和的反码存放在检验和字段，每台路由器上必须重新计算检验和并放回原处，因为TTL字段以及选项字段会改变。
- 无选项的IP数据包首部长度为20字节
IP数据报分片
一个例子：一个4000字节（20字节IP首部+3980字节IP有效载荷）的数据报，被转发到一条MTU为1500字节的链路上，则初始数据报中3980字节数据必须被分配为3个独立的片
除了最后一片，所有初始有效载荷数据的数量应当是8字节的倍数，且偏移值应当被规定以8字节块为单位；最后一个片的标志比特被设为0，而所有其他片的标志比特被设为1
即长度为X的数据报，被转发到MTU为Y的链路，则需要$\lceil\frac{X-20}{Y-20}\rceil$个分片
分片Dos攻击
发送一系列古怪、无法预期的片，如没有一个片的偏移量是0；发送交迭的IP片
IPv6从根本上废止了分片
子网
子网掩码
223.1.1.0/24 子网掩码(/24)指示了最左侧24比特定义了子网地址
为了确定子网，分开主机和路由器的每个接口，产生几个隔离的网络岛，使用接口端接这些隔离的网络端点。这些隔离的网络中的每一个都叫做一个子网。
CIDR被采用前，分类编址方案为8、16、24比特子网地址，分别被称为A、B、C类网络
CIDR将子网寻址的概念一般化
动态主机配置协议（DHCP）
- DHCP服务器发现：使用广播目的地址255.255.255.255，本主机源地址0.0.0.0
- DHCP服务器提供：仍然使用IP广播地址255.255.255.255，包含事务ID、向客户推荐的IP地址、网络掩码和IP地址租用期
- DHCP请求：新客户从一个或多个服务器提供中选择一个，并提供一个DHCP请求报文进行相应，回显配置参数
- DHCP ACK：服务器用DHCP ACK报文进行响应，证实所要求的参数
网络地址转换（NAT）
问题：NAT协议将端口号用于主机编址，且妨碍P2P应用程序（可用NAT穿越解决）
IPv6
IPv6数据报格式
任播地址：可以使数据报交付给一组主机中的任意一个
不复存在：分片/重新组装、首部检验和、选项
IPv4到IPv6的迁移：
建隧道
通用转发和SDN
flow table
数据平面抽象
第五章 网络层：控制平面
转发(forwarding)：数据平面
路由(routing)：控制平面
两种构建控制平面的方法：
路由器控制（传统）
逻辑集中控制（SDN）
路由选择算法
全局算法（LS）
每个路由器都有完整的拓朴结构和每条连接的代价信息
去中心化算法（DV）
路由器知晓物理上与它相连的连接和邻居的信息
迭代计算，邻居之间交换信息
LS算法
Dijkstra算法计算最短路
DV算法
本质上是基于Bellman-Ford的动态规划
迭代直至收敛
连接代价发生改变的两种情况：
好消息传播快
坏消息传播慢
- 增加毒性逆转来减少迭代次数：如果Z通过Y到达X，则Z将告知Y：$D_Z(X)=\infty$
LS与DV算法的比较
| 消息复杂度 | 收敛速度 | 鲁棒性 | |
|---|---|---|---|
| DV | $O(nE)$ | $O(n^2)/O(nlgn)$+$O(nE)$(消息传递)，但可能发生震荡 | 每个点计算自己的转发表 |
| LS | 只在邻居间交换消息，取决于收敛次数 | 收敛次数不同，可能由无穷计数问题 | 每个点的转发表被邻居使用，错误的连接代价会随着网络传播 |
因特网中自治系统
- 自治系统AS(autonomous systems)/domains
- IGP
OSPF
- 开放最短路优先
- 使用洪范链路状态信息的链路状态协议
- Dijkstra最低费用路径算法
- 优点
- 安全，所有OSPF消息都被验证（MD5），防止恶意入侵
- 多条相同费用路径情况下，OSPF允许使用多条路径，无需单一路径承载所有流量
- 单播和多播支持
- 层次结构
- 区域边界路由器
- 主干
BGP
SDN控制平面
- 传统控制平面：通过分布式、单一路由器方法
- 逻辑集中控制平面的优点
- 易于网络管理，避免路由器配置错误，灵活性
- 路由器编程
- 开放的控制平面实现
SDN控制器
- 维护网络信息
- 通过北API与应用程序交互
- 通过南API与网络交换机交互