概述
网络协议
三要素：语法(数据格式)、语义(控制信息)、时序(事件顺序)
多路复用
频分多路复用(FDM): 各用户占据不同频率的带宽发送数据。
时分多路复用(TDM): 将时间分片，周期性为不同用户发送数据。
波分多路复用(WDM): 光的FDM。
码分多路复用(CDM): 特点如下：应用于无线网络，各用户使用相同频率带宽，利用各自码片序列编码数据。各用户编码相互正交。
CDM的步骤为：
- 每个设备先被分配一个码片序列。
- 实际传输的数据中，0用-1表示，1用+1表示，将之与码片序列相乘，得到该用户的编码值。多个用户的编码值相加，传输数据。
- 解码时，码片序列与实际接收到的数据做内积，即可获得码片序列对应用户的信息。
数据交换方式与计算
电路交换：独占资源，按照“呼叫建立-通信-拆除呼叫”步骤运作。
报文交换：一次发送信息整体。采用“存储转发”方式。
分组交换：将信息拆分，分组多次发送。采用“存储转发”方式。
假设AB主机之间有唯一一条通讯链路，带宽为$R$bps，报文为$M$bits，分组大小为$L$bits，链路上有$n$个路由器(需要走$n+1$段小链路，即$n+1$跳)，则：
报文交换耗时为$T=\frac{(n+1)M}{R}$。
分组交换耗时为$T=\frac{M}{R}+n\frac{L}{R}$。
几个重要参数
- 速率(数据率、数据传输速率、比特率)：常指额定速率、标称速率。
- 带宽：链路的最高速率。
- 节点处理延迟：路由器存储-转发数据包所消耗的时间。
- 排队延迟：由于数据包过多，路由器没法一次性将所有数据包传输出去。等待传输链路可用的时间称作排队延迟。
- 传输延迟与传播延迟：传输延迟为数据包长度除以链路带宽；传播延迟为链路长度除以信号传播速度。
- 流量强度：设链路带宽为$R$，分组长度为$L$，平均分组到达速率为$a$，则流量强度为$\frac{La}{R}$。
- 时延带宽积：传播延迟和带宽之积。
- 丢包率：丢失的数据包个数占已发送的数据包个数的比例。
- 吞吐量：整条链路能够达到的最大带宽，对于一条多段链路来说，其吞吐量为其各段链路带宽的最小值，这段链路也被称为瓶颈链路。
OSI与TCP参考模型
OSI参考模型有七层：
- 应用层
- 表示层
- 会话层
- 传输层
- 网络层
- 链路层
- 物理层
前四层为端到端层，即他们不考虑底层的逻辑，建立主机-目标机之间的传输抽象。
TCP参考模型中，删去了表示层和会话层。
应用层
应用层通过socket发送/接收消息，每个进程通过“IP+端口号”方式标识。
HTTP协议的计算
HTTP1.0使用非持久性连接，每个TCP连接最多允许传输一个对象。
HTTP1.1使用持久性连接，每个TCP连接允许传输多个对象。
非持久性连接：传输N个对象，则该协议需要$2+2N$个RTT，TCP连接的建立和HTTP的请求需要2个RTT，每个对象各自需要一个请求文件RTT和发送文件RTT。
非流水线的持久性连接：传输N个对象，则该协议需要$2+N$个RTT，TCP连接的建立和HTTP的请求需要2个RTT，每个对象只需要一个发送文件RTT。
流水线的持久性连接：传输N个对象，则该协议需要$3$个RTT，TCP连接的建立和HTTP的请求需要2个RTT，每个对象并行发送，只需要一个RTT。
HTTP协议的消息格式
请求消息包括四部分：请求行、请求头部、空行和请求数据。
响应消息包括四部分：状态行、消息报头、空行和响应正文。
Cookie技术
HTTP是无状态的，有时为了保存一些状态(登录状态等)，需要用到Cookie，其包括四个部分：
- HTTP响应消息的Cookie头部行。
- HTTP请求消息的Cookie头部行。
- 保存在客户端的Cookie文件。
- Web服务器端的后端数据库。
E-mail应用
邮件服务器之间传递消息使用SMTP协议，按照“握手-传输-关闭”的方式工作，其消息包含：头部、空行、消息体三部分。通过MIME(多媒体扩展)，可以令E-mail消息支持不同的文件格式。
从服务器获取邮件可以用如下三个协议：POP协议、HTTP协议、IMAP协议。
DNS服务
DNS服务采用分布式层次服务器架构，使用UDP协议。解析服务器分为：
- 顶级域名服务器：负责解析
.com、.org等顶级域名和国家顶级域名。 - 权威域名服务器：负责组织内部服务器的解析。
- 本地域名服务器：每个ISP都有一个本地域名服务器，当主机发起解析请求时，首先在本地域名服务器中查询。
DNS记录常为资源记录(RR)，其为一个四元组（name, value, type, ttl），对于type：
- 若为A，则表示value是name的主机域名。
- 为NS，则value表示name域权威域名服务器的主机域名。
- 为CNAME，则表示value为name的真实域名。
- 为MX，则表示value是name的对应邮件服务器。
文件分发速度的计算
C/S架构：$max(\frac{NF}{u_s},\frac{F}{min(d_i)})$
P2P架构：$max(\frac{F}{u_s},\frac{F}{min(d_i)}，\frac{NF}{u_s+\sum u_i})$
对于C/S架构来说，这里进行了一个非常粗糙的建模，相当于一个大水管和很多小水管相连。
对于P2P架构来说，建模同样粗糙，认为上传下载是同时发生的。此时服务器必须上传一份文件副本就好，之后交给P2P网络传来传去，客户机下载需要下载N份，而默认上传速率就是$u_s+\sum u_i$。
P2P索引
P2P需要和其他主机建立连接，就必须有一个服务器(tracker)记录其他服务器的信息。
如果服务器是中心化的，就是集中式索引，每个主机和该中心化的服务器建立连接。
如果服务器是完全分布式的，每个主机都存储一些信息，就是洪泛式索引。
也可以设立一些局部中心化的节点，这些局部中心化的节点之间洪泛式查询，而主机和这些节点采用中心化的查询方式，这就是层次式覆盖网络。
传输层
传输层负责两个主机进程间的通讯。
复用和解复用
复用：从多个socket获取数据，封装给网络层。
分用：收到数据包时，拆分数据包，发送给对应的socket。对于UDP协议，以二元组标识（目的IP，目的端口号）；对于TCP协议，以四元组标识（源IP，源端口号，目的IP，目的端口号）
UDP协议
“能到就到，到不了拉倒”。值得一提的是其校验和机制，将段的内容视作16位整数，相加，进位置于和的后面，按位求反即得校验值。
可靠性传输原理(RDT)
RDT模型是抽象的建模。
RDT1.0：可靠信道上的可靠传输。压根不会发生错误。
RDT2.0：产生位翻转的传输。应用确认机制，接收方接收到消息时，先验证，然后显式发送ACK告知成功接收，否则发送NAK。
RDT2.1：重复分组的处理。添加分组序号。
RDT2.2：ACK/NAK消息失真。舍弃NAK机制，成功就发送NAK，否则不发送消息。
RDT3.0：引入定时器机制和停等机制。
GBN协议(后退N帧协议)
发送方和接收方各设定一个滑窗。当接收方受到消息后，会向发送方发送一个ACK(n)信号，表示n和n之前的所有数据包被正确成功接收，乱序到达的分组被丢弃，当数据包超时，则发送序列号大于等于n的所有数据包。
SR协议(选择性重复协议)
GBN重传的数据包太多，SR协议优化了一些。
SR协议只重传那些没有受到ACK的分组。
但是，要满足$N_s+N_r\leq 2^k$，其中$N_s,N_r$为发送方、接收方窗口大小，$2^k$为序列号的最大值。
TCP协议
其为一个点对点的、全双工的、面向连接的可靠传输协议。
其中，ACK(n)表示到n-1包都完全接收了，序列号为segment中第一个字节的编号。
TCP超时时间的确定
$$
TimeoutInterval = EstimatedRTT + 4DevRTT
$$
$$
EstimatedRTT=(1-\alpha)EstimatedRTT+\alpha\times SampleRTT
$$
$$
DevRTT=(1-\beta)DevRTT+\beta\times |SampleRTT-EstimatedRTT|
$$
TCP快速重传机制
如果发送方3次收到了同一数据的ACK，就断定这之后的数据全丢失了，于是重传后面的包。
TCP流量控制机制
接收方在发送给发送方的数据头部，声明可用空间，从而使发送方调整发送速度。
TCP连接管理
三次握手：
四次挥手：
TCP拥塞控制
AIMD(加性增-乘性减)：逐渐增加传输速率，拥塞窗口每个RTT增大一个MSS(Maximum Segment Size)探测可用带宽，直到loss，发生loss时，拥塞窗口减半。
慢启动：TCP连接建立时，拥塞窗口大小为1，随后指数型增长，直到loss或者达到threshold。
拥塞避免：达到loss时，其拥塞窗口的半值会被设定为threshold，未达到threshold，按慢启动运行；当达到threshold时，线性增长。
网络层
网络层的核心功能为：转发和路由。
虚电路网络
其提供网络层的有连接服务，这种网络可以抽象成：两台主机之间搭建起了一条通讯电路。其按照“呼叫建立-通讯-呼叫拆除”的方式运行。
路径上的每一段小链路都有一个VCID(虚电路ID)，路径上的数据分组，不携带目标地址，只标识VCID。
数据包网络
其提供网络层的无连接服务，每个分组携带目的地址，路由器根据分组的目的地址转发分组。
路由算法采取最长前缀匹配优先算法，根据目的地址确定链路接口。
IP数据报
结构如下：
其中：
- 版本号：4/6，标识IPv4/IPv6协议。
- 首部长度：标识IP数据包首部的长度，以4字节为单位。比如，如果首部长度为4，就表明头部长16字节。
- 总长度：标识IP数据包的总字节数。
- 生存时间(TTL)：IP分组在网络中最多可以经过的Hop数，路由器转发一次分组，TTL就减去一。
- 协议：6为TCP，17为UDP。
- 首部校验和：和UDP的checksum计算方法一致。
IP分片
网络链路中存在MTU(最大传输单元)，一段大MTU链路向小MTU链路传递信息时，数据可以被分片，分片到达目的主机后，进行重组操作。
利用数据报中的总长度、标识、标志位和位偏移标识分片和相对顺序：
- 每产生一个分组，标识位就加一。
- 标志位有三位，分别为Reserved、DF(Don’t fragment)和MF(More Fragment)，DF为1表示未分片，为0表示分片了，MF为1表示该数据片不是最后一片，为0则表示该片为最后一片。
- 位偏移标识该分片对于原数据IP的偏移量。
分片时，每个分片都要复制原IP的报头。
设原IP数据报长度为$L$，待转发链路的MTU为$M$，则一个最大分片所能承载的数据量为：
$$
d=\lfloor{\frac{M-20}{8}}\rfloor\times8
$$
20为IP数据报头长度。
需要的总片数为：
$$
n=\lceil\frac{L-20}{d} \rceil
$$
片偏移为：
$$
F_i=\frac{d}{8}\times (i-1), 1\leq i\leq n
$$
IP编址
网络号-主机号