计网-传输层

传输层的协议是在 end system 里实现的，在 router 中是感知不到的。无论是 TCP 和 UDP，在 router 眼里都是单纯的数据，router 不会解析传输层协议。

1. 传输层

传输层提供如下的功能：

• 进程间逻辑通信：网络层只能将数据从一个 host 传向另一个 host，而传输层提供了进程与进程之间的通信。

• 复用：发送方的多个应用进程可使用同一个传输层协议传送数据。

  网络层也有复用，指的是不同传输层协议的数据封装成 IP 数据报发送

• 分用：接收方的传输层在剥去报文首部之后能将数据正确交付给对应目标进程。

  网络层也有分用，指的是接受方根据首部的协议字段，将数据交付给相应的传输层协议。

• 差错检测：传输层对收到的整个报文（包括头部和数据部分）进行差错检测。

  网络层的 IP 协议仅对其头部进行校验，不校验数据部分。

• 提供面向连接和无连接的传输服务，隐藏底层网络的复杂性，使进程感知到的是一条端到端的逻辑通信信道。

端口

传输层提供端口这个概念，端口用于传输层和应用层进行交互。应用进程通过端口号标识。

端口号的长度为 16 bit，可标识 $2^{16} = 65536$ 个不同的端口号。端口号仅具有本地意义，不同主机的相同端口号是没有关联的。UDP 和 TCP 的端口号也是相互独立的。

端口号分成两类：

• 服务端使用的端口号，有分成两类

  • 熟知端口号（$0\sim 1023$），有 IANA 分配给最重要的应用程序。

  • 登记端口号（$1024\sim 49151$），供未获熟知端口号的应用程序使用，需要在 IANA 登记以避免冲突。

• 客户端使用的端口号（$49152\sim65535$），此类端口号在客户端进程运行时动态分配，又被称为短暂端口号。

套接字

网络上通过 IP 地址确定一个主机，然后通过端口号确定主机上的一个进程。IP 地址和端口号组成的一个二元组构成了一个套接字。

套接字唯一标识网络中某台主机上的一个应用进程，是通信的端点。

2. UDP 协议

UDP 协议相比于网络层，仅增加了分用、复用和差错检测的功能。

UDP 相比于 TCP 比较简陋，但是有如下的优点：

• UDP 能确保发送什么数据包，以及数据包什么时候发送出去。UDP 协议会直接把从应用层传递过来的数据包经过处理后直接发往目标。而 TCP 可能会将数据包分割成若干段，并且可能不会立刻发送数据包，而且可能会将一个数据包重复发送。

  UDP 发送的数据包太大的话可能会在网络层被分片

• UDP 没有连接这个概念，所以每次发数据前不需要花时间来建立连接，效率更高。同时 UDP 也不需要系统区维护连接状态。

• UDP 的头部只有 8 字节，而 TCP 的头部有 20 字节。

• UDP 支持一对一，一对多，多对多的通信。而 TCP 只支持一对一的通信。

UDP 常用于一次性传输少量数据的应用。一些多媒体应用由于更关注低时延而并非可靠性，也倾向于使用 UDP。

UDP 不保证可靠性，但是不意味着使用 UDP 的应用也不能保证可靠性。开发者可以在应用层实现可靠性机制。

2.1 数据包格式

• Source port：2 字节，源端口号。用于接收方回复时使用。不需要回复时可置为 $0$。

• Dest port：2 字节，目的端口号。

  传输层会根据目的端口号把 message 交给对应的进程。如果接收方发现目的端口号没有对应的进程，则直接丢弃该报文，并由 ICMP 发送端口不可达的差错报文给发送方。

• Length：2 字节，这个长度是整个 UDP 数据包的长度，单位是字节，包含 message 和头部，最小值是 $8$。

  这个字段其实是有点多余的，因为网络层的 IP 头部也有数据包长度字段。出现这个的原因是，设计 UDP 的时间要比设计 TCP 和 IP 的时间早，当时还不能单纯依靠 IP 协议算数据包长度。

  注意到这个字段只有 2 字节，也就是说整个 UDP 数据包最大也就是 65535 字节。再考虑上 UDP 头部和 IP 头部，负载数据最大是 65507 字节。如果发送数据包时，负载数据大小超过了 65507 字节，那么就会被操作系统拒绝。

• checksum：2字节，校验数据。

  在 IPv4 中，该字段可置为全 $0$ 表示未使用（但不建议），在 IPv6 中则强制启用。

  如果算出来的 Checksum 恰好就是 $0$，那么就置为全 $1$。如果算出来的 Checksum 恰好就是全 $1$，那么也不变了。数据校验的算法可以保证全 $0$ 改为全 $1$ 仍能直接通过校验，校验时无需特判。

2.2 数据校验

UDP 数据包的头部的 Checksum 是这样获得的：

• 将源 IP 地址（4字节）+目标 IP 地址（4字节）+0填充（1字节）+协议类型（1字节，UDP 就为 17）+UDP 长度（2字节，和 UDP 报文的头部的 Length 字段是一致的），这 12 字节（这些其实来自于网络层 IP 协议的头部。这 12 字节也称为伪头部。构造 UDP 头部的时候其实是先构造一部分，然后让链路层构造 IP 头，然后再回到传输层继续计算 Checksum 来完成整个 UDP 头部的计算）

  再加上 UDP 报文的头部中除了 Checksum 之外的字段（共 6 字节）以及负载数据。然后，再填充 0，使得长度最终是 16 位对齐的。

• 将上一步的数据，视为若干个 16 位的整数，然后进行 16 位的二进制反码求和运算，其规则如下：

  • 按正常的二进制加法运算
  • 如果最高位产生进位，则应该把进位的 $1$ 再加到最低位，这个过程被称作回卷。

• 再把最后的相加结果进行取反。

接收方在校验时，重复上述前两个步骤（不继续第三个步骤取反），然后最后再加上 Checksum 的值，看一下是不是二进制下全 1 即可。

如果接收方发现校验失败，通常会直接丢弃该报文。尽管 RFC 允许将其交付给上层并附带错误，但实际中极少使用。

由于我们在校验时还加了个伪头部，所以 UDP 实际上还校验了 IP 头部的源地址和目标地址是否错误。

3. TCP 协议

TCP 协议是基于不可靠的 IP 协议的可靠数据传输协议。

TCP 具有的特点：

• TCP 是面向连接的，有建立连接和释放连接的时间开销。
• 每一个 TCP 连接只能有两个端点，仅支持一对一通信。
• TCP 提供可靠交付，保证所传数据无差错、不丢失、不重复、按序到达。
• TCP 支持全双工通信，通信双方都可以在任何时候发送数据。
• TCP 是面向字节流的，不关心数据的边界。

3.1 报文段

TCP 一次的传输单元被称为报文段，报文段的结构如下：

头部的 20 字节是固定的，后面的 Options 段是根据需要而增加的选项，一个选项是 $4$ 字节。TCP 头部的最小长度为 20 字节。

• Source port：2 字节，源端口。

• Dest port：2 字节，目的端口。

• Sequence number 和 Acknowledgment number 主要用于 TCP 的可靠性传输。

  • Sequence number：4 字节，表示当前数据包的负载数据中的第一个字节，在整个字节流中的序号。序号可表示的范围是 $0\sim 2^{32}-1$，当序号到达 $2^{32}-1$ 后，下一个序号将回绕到 $0$。
  • Acknowledgment number：4 字节，表示数据包的发送方期望后面要从数据包的接收方那边收到的下一个数据包的 Sequence number。如果 Acknowledgment number 为 $x$ 的话，那么就意味着字节流中前 $x-1$ 个字节已经收到（cumulative acknowledgment），后面希望收到第 $x$ 字节。

• Header length，也叫数据偏移：4 bit，表示的是 TCP 头部的大小，单位是 4 字节。

  由于 TCP 头部最小为 20 字节，所以这个值最小为 $5$。最大为 $15$，这意味着 TCP 头部长度最多是 $60$ 字节。

  值得注意的是 TCP 并没有表示负载数据大小的字段，这是因为可以通过 IP 头部的数据包长度的字段来计算。

• Unused 填充：4 bit。

• 然后是 8 bit 的标识位。

  • CWR 和 ECE 用于后面的 ECN 拥塞控制。408 中认为这两个位也属于前面的填充。

  • URG 表明当前数据包包含紧急数据，应优先处理。紧急数据被放在报文段数据的最前面，后面的数据仍为普通数据。通过后面的 Urgent data pointer 来区分紧急数据和普通数据。

    现代操作系统一般忽略掉这个标识位。

  • ACK 表明当前数据包的 Acknowledgement number 是有意义的。

    实际上这个标识位基本在所有的 TCP 数据包中都会设置，并且 TCP 规定，连接建立之后，所有传送的报文段都必须将 ACK 设置为 $1$。

    但存在例外：当第一次握手时，第一个发出去的 SYN 包的 Acknowledgement number 是无意义的，因此不设置 ACK。此外，一些 RST 包可能有一些语义的区分，也不设置 ACK。

  • PSH 表示当前这个数据包应立刻交给应用层。在交互式通信中，应用进程希望输入命令后能立刻收到响应，此时就设置这个标识位。操作系统看到这个标识位之后会立刻把数据包交给应用层，而不必等到整个缓存填满后才向上交付。

    现代操作系统一般忽略掉这个标识位。

  • RST 用于直接主动断开连接。设置这个标识位时，表明 TCP 连接出现严重差错（比如主机崩溃），必须释放连接并重新建立连接。此外 RST 也可用于拒绝非法的报文段或连接请求。

  • SYN 和 FIN 标识位用于握手和挥手。

• Receive window：2 字节，用于后面的流量控制。

• Internet checksum：2 字节，校验值。

  校验值的计算和 UDP 是一样的，也是构造了个伪头部拼在 TCP 数据包的前面，然后每 2 字节进行二进制反码加法，最后再取反。

3.2 连接管理

主动请求建立连接的一方被称为客户端，另一方被称为服务端。

一个 TCP 连接由两个套接字，既目标 IP、目标端口号、来源 IP、来源端口号这个四元组共同描述。一个 IP 地址可以参与多个不同的 TCP 连接，同一个端口号也可以参与多个不同的 TCP 连接。

3.2.1 建立连接

在最开始，两端的进程均处于 CLOSED 状态。服务端完成一些准备工作后进入 LISTEN 状态，等待客户端的连接请求。

假设 $A$ 主动向 $B$ 建立连接，则有：

• $A$ 向 $B$ 发送 SYN。

  $A$ 会取一个随机数 $x$ 作为自己的初始序列号，$seq = x$。取随机数可以防止网络中残留的之前连接的数据包对当前连接产生干扰。$ack = 0$，因为尚未收到任何的报文段。

  TCP 规定 SYN 报文段不能携带数据，但仍消耗一个 sequence number，因此下一次 $A$ 在发送报文段，$seq = x + 1$。

  $A$ 进入 SYN-SENT 状态。

• $B$ 向 $A$ 发送 SYN 并 ACK $A$ 的 SYN，即 SYNACK。

  $B$ 也会选择自己的初始序列号 $seq = y$。同样地报文段不携带任何数据，但是会消耗一个序号。$ack = x + 1$。

  有可能 $A$ 请求的端口在 $B$ 上不存在，此时 $B$ 会响应一个 RST 包，表示目标端口不存在，让 $A$ 别再发送数据包了。

  $B$ 收到了 SYN 会立刻为此次连接分配资源。

  $B$ 进入 SYN-RECV 状态。

• $A$ 向 $B$ 再发送 ACK。$seq = x + 1$，$ack = y + 1$

  $A$ 收到 $B$ 的 SYNACK 后为此次连接分配资源。

  这个报文段可以携带数据，如果不携带数据的话则不消耗序号，下一个报文段的 $seq$ 仍为 $x+1$。

  此时 $A$ 进入 ESTABLISHED 状态，$B$ 在收到 ACK 后也进入 ESTABLISHED 状态。

  这一步握手看似没必要，因为其实可以 $A$ 先分配好资源，然后再向 $B$ 发送 SYN，然后这一步省略。但这却是必须的。抽象地说，第一次握手表示 $A$ 可以发送数据包，第二次握手表示 $B$ 可以接收和发送数据包，第三次握手表示 $A$ 可以收数据包。

上述过程实际上是比较古老的 TCP 协议过程，容易遭到 SYN flood 攻击。由于第二次握手的时候服务端就分配资源了，所以攻击方可以发送大量的 SYN 包来使得服务端的资源耗尽。解决方案是使用 SYN cookie：

• $B$ 收到 $A$ 的 SYN 之后，$B$ 根据源 IP、目的 IP、源端口、目的端口、时间戳、密钥，这六部分计算哈希值，得到发给 $A$ 的 SYNACK 的 sequence number。

  其中的密钥是一个全局密钥，在服务端启动时随机生成。

  其中的时间戳是一个比较粗的粒度的时间戳。比如可能每 $64$ 秒更新一次。

  生成的这个作为 sequence number 的哈希值就被称作 SYN cookie。

• $A$ 收到 $B$ 的 SYNACK 之后再发送 ACK。$B$ 收到 ACK 的时候，重新按之间的方法计算哈希值，然后与 ACK 数据包中的 ack number 再减一的值比对，比对失败则说明可能是恶意攻击，终止连接。

  由于哈希函数中有一个参数是时间戳，服务端一般会计算用当前时间戳和当前时间戳的上一个时间戳，计算出两个哈希值，然后进行比对，有一个比对上就可以。这也就意味着必须在两个时间戳间隔内完成连接的建立。如果网络延迟很高，建立连接的时间超过了两个时间戳间隔的话，服务端这边是没有连接的，客户端可能以为连接已经建立，但是客户端在发送第一个数据包后就会收到 RST 包，从而意识到没有真正建立连接。

SYN flood 攻击的攻击方一般需要伪造来源 IP。如果使用真实 IP 的话很容易被发现并针对性地进行封禁。而如果伪造了 IP 的话，服务端在第二次握手时发送的 SYNACK 会发往被伪造的 IP，攻击方无法收到 SYN cookie，从而无法完成第三次握手。

使用哈希函数来计算 SYN cookie 是必要的。如果服务端改用随机数的话，那么第三次握手时就无法分辨 ACK 包中提供的 ack number 是否是 SYN cookie。如果服务端选择将生成的随机数存下来的话，那么就又和原来一样容易被攻击了。

带一个时间戳也是有必要的，可以防止重放攻击，攻击者可以从网络中嗅探其他主机的握手过程，拿到 SYN cookie，然后就可以去伪装成这些主机了。

3.2.2 断开连接

无论是服务端还是客户端都可以主动提出断开连接。当对套接字进行 close() 操作时，函数会立刻返回，然后操作系统标记这个套接字不再被使用，该套接字变为“孤儿套接字”，由内核接管这个套接字接下来的行为。套接字的资源并不会立刻被释放，而是经历如下的过程。

假设 $A$ 主动向 $B$ 断开连接，则有：

• $A$ 向 $B$ 发送 FIN。设 $seq = u$

  FIN 的语义是表示不再发送任何数据了。如果 $A$ 的缓冲区中还有数据没有被发出去或者是没有被 ACK，那么需要等待这些数据发送并确保被 ACK 了。

  FIN 包可以顺便把缓冲区中最后一点没发出去的数据也给带上。同时 TCP 规定，FIN 报文段即使不携带数据，也会消耗一个序号。

  但是主流的操作系统一般不允许 FIN 携带数据。

  FIN 发送后，和普通的包一样，等待 ACK。没有被 ACK 的话会重发。

  发送后，$A$ 进入 FIN_WAIT_1 状态。

• $B$ 向 $A$ 发送 ACK。$ack = u + 1$，设 $seq = v$。

  这一步表示 $A$ 向 $B$ 的传输方向正式关闭了，但是 TCP 是全双工的，$B$ 向 $A$ 的传输方向还没正式关闭，后面 $A$ 仍能接收到 $B$ 发来的数据。此时 TCP 连接处于一种半关闭的状态，一些相关资源会被释放（比如写的缓冲区）。

  事实上，套接字可以进行 shutdown() 操作来人为做到一种半关闭状态。

  发送后，$B$ 进入 CLOSE_WAIT 状态。$A$ 收到 ACK 后进入 FIN_WAIT_2 状态。

• $B$ 向 $A$ 发送 FIN + ACK。$ack = u + 1$，$seq = w$

  在进行这一步之前，$B$ 同样地需要确保自己的缓冲区的数据都已经被发出去并且 ACK 了，因此 $w$ 不一定为 $v$。

  同样地，FIN 发送后，等待 ACK。没有被 ACK 的话会重发。

  发送后，$B$ 进入 LAST_ACK 状态。

• $A$ 向 $B$ 发送 ACK。$ack = w + 1$，$seq = u + 1$

  $B$ 在收到 ACK 之后会立刻释放套接字资源，关闭连接，进入 CLOSED 状态。

  而 $A$ 在发送出 ACK 之后，并不会释放套接字资源，而是进入 TIME_WAIT 阶段。这个阶段会等待 $2\times \text{MSL}$ 的时间，其中 $\text{MSL}$ 为报文最长存活时间，一般是个常量，在不同的操作系统上，这个值从 $15$ 秒到 $2$ 分钟不等。作用有两个：

  • 防止回复的 ACK 没有被 $B$ 收到，$B$ 重发 FIN。
  • 确保当前网络中已经不存在和当前连接有关的正在传输的数据包了，防止后面新的套接字收到已经关闭了的连接的数据包。

  等待结束之后就会进入 CLOSED 状态。

3.3 字节流

3.3.1 MSS

在链路层上存在一个 maximum transmission unit（MTU），表示链路层一次最大可传输的数据包大小，一般是 $1500$ 字节。如果要发送的数据超过了 MTU，那么 IP 协议会将要发送的数据分成若干段，逐个发送，这称为 IP 分段。但是如果有一个段在传输过程中丢失的话，整个数据包就相当于丢失了。因此 UDP 发送大数据包是容易丢包的。

为了防止 IP 分段提高丢包概率，TCP 在握手时，双方会约定 MSS（maximum segment size） 值，即单次实际可以传输的负载数据的大小。

TCP 对数据的传输是一种流式传输，并不会像 UDP 那样一整个包地传。TCP 单次传输时会保证负载数据的大小不会超过 MSS。

假设 $A$ 主动与 $B$ 建立连接，$A$ 可以在其发送的 SYN 包中的 Options 字段中添加如下内容：首先是 Options 种类（1字节），设置为 $2$，表示这是 MSS 协商的选项。然后是该 Options 的总长度（1字节），设置为 $4$ （单位字节）。最后是 $A$ 这边的 MSS 值（2字节）。这意味着 $B$ 向 $A$ 发送的数据包的负载数据大小不要超过这个 MSS 值。

$B$ 也可以在自己的 SYNACK 包中约定 MSS 值，表示 $A$ 向 $B$ 发送的数据包的负载数据大小不要超过这个 MSS 值。

MSS 的值一般是 MTU 的值减去 40 字节（IP 和 TCP 的头部，加起来大概是 40 字节）。MTU 的值可能要通过路径 MTU 发现来得到。

但是互联网路径是动态变化的，很难确定一个比较好的 MSS。TCP 规定默认的 MSS 值为 536 字节。如果有一方没有提供这个 Options，那么就按这个走。互联网上的所有主机应该都遵守这个规定，接收长度为 $536 + 20 = 556$ 字节的 TCP 报文段。

3.3.2 Nagle 算法

如果应用层传给 TCP 的数据包大小比较小，如果 TCP 立刻发送的话就容易使得大量小包充斥网络。如果 TCP 等着待发送的数据在缓冲区中凑够 MSS 再发送的话有可能导致不必要的延迟。Nagle 算法就考虑解决这个问题。

Nagle 算法是用来判断 TCP 要不要发送数据包，具体能发送多少还会受到流量控制和拥塞控制的限制。

• 如果有未被 ACK 的数据在网络中，将要发送的数据缓存下来
  • 如果收到了之前数据的 ACK，那么就立即发送缓冲的数据
  • 如果缓冲数据凑够了 MSS，也立即发送
• 如果没有未被 ACK 的数据的话，立即发送，不管多小

正常情况下 Nagle 大概会引入一个 RTT 的延迟。Nagle 和 Delayed ACK 在一起时会引入人为的延迟，Nagle 等待 ACK，Delayed ACK 会延迟一段时间再发 ACK。

Nagle 在操作系统中是默认开启的，对于一些交互性比较强的场景下（网络游戏、实时交易、SSH/Telnet，HTTP API）需要关闭：

python
1
serverSocket.setsockopt(socket.IPPROTO_TCP, socket.TCP_NODELAY, 1)

Nginx，Node.js(net)，Redis，MySQL，SSH 是会默认设置关闭 Nagle。

3.3.3 Cork 算法

Cork 算法比 Nagle 更加激进。他会强制等待缓冲区数据凑够 MSS 或者超时（大约 200ms）或者手动关闭 Grok 才发。

python
1
2
serverSocket.setsockopt(socket.IPPROTO_TCP, socket.TCP_CORK, 1) # 开启 Cork
serverSocket.setsockopt(socket.IPPROTO_TCP, socket.TCP_CORK, 0) # 关闭 Cork

3.3.4 Clark 算法

在接收方那边，可能也会有类似的问题：比如接收方缓冲区满后，接收方通知接收窗口为 $0$，然后应用层取走 $1$ 字节后，接收方通知接收窗口为 $1$，发送方发送了 $1$ 字节，然后应用层又取走了 $1$ 字节... 这样下去，网络中充斥了很多的小包，传输带宽很多都浪费在了 TCP 和 IP 头部上。

所以接收方在空出空间后，不会立即更新接收窗口，等到满足以下任一条件才更新：

• 空闲空间 $\ge MSS$
• 空闲空间 $\ge$ 缓冲区总大小的一半

3.4 可靠数据传输

3.4.1 ACK

• 为了防止出现 A 向 B 发送数据包，B 回复 ACK，然后 A 又回复 ACK 这种死循环的情况，TCP 不会对没有负载数据的数据包回复 ACK。

• 如果收到了顺序的带有期望 sequence number 的数据包，那么 TCP 会有个 Delayed ACK 行为，会等待一段时间（比 500 ms）看一下这段时间内是不是又继续收到了顺序的数据包（如果继续收到的话并不会再重新设置计时器）。这样可以充分利用 cumulative acknowledgment 来减小数据包的传输量。

• 如果连续收到 $N$（一般为 $2$）个顺序的数据包，会立刻回复 ACK，不再等待 Delayed ACK。

• 由于 TCP 是全双工的，所以可以在回复 ACK 的同时把自己要传给对方数据也顺手带上，这称为 piggyback ACK。要发送数据时会立刻回复 ACK，不再等待 Delayed ACK。

• 如果收到了乱序的数据包，或者对应的负载数据已经收到过了，那么会立刻回复 ACK。由于是乱序的，回复的这些 ACK 的 Acknowledgment number 都一样，所以也被称为 duplicate ACK。

  如果发送方收到了多个 duplicate ACK ，那么这就意味着接收方那边可能已经收到了很多乱序的数据，就差最开头的那个数据包了。TCP 有一个 fast retransmit 机制，如果连续收到 $3$ 个 duplicate ACK，那么就立刻重传第一个未被 ack 的部分。

  连续收到 $3$ 个 duplicate ACK 意味着对同一个序号 ack 了 $4$ 次。

  至于乱序的数据包本身，TCP 的标准并没有说明接收到乱序的数据包会怎么样，接收方可以直接丢掉，但更常见的做法是留着。

3.4.2 超时设置

超时时间一般要大概设置成 RTT，即数据包在双方之间来回的时间：

TCP 会持续采样测量当前的 RTT，采样值为 $\text{SampleRTT}$：

• 当 TCP 要把数据包交给网络层发送时，TCP 会判断当前是否设置了 rtt_seq，即当前是否有正在被采样的数据包。如果没有设置的话，就会把 rtt_seq 设置为该数据包的 sequence number，然后并设置 t_send 为当前的时间戳。
• 当 TCP 收到了 ACK 之后，如果当前设置了 rtt_seq 并且 ACK 的 acknowledge number 大于等于 rtt_seq 的话，记当前的时间戳 t_ack，于是就获得到了一个新的 $\text{SampleRTT}$ 为 t_ack - t_send。
• （Karn 规则） 上述采样过程可能出现一个问题，如果超过了超时时间，TCP 会重发数据包，于是 ACK 既可能是对应于原始的数据包，又可能是对应于重发的数据包，而对于后者，得到的 $\text{SampleRTT}$ 就会严重偏大。于是 Karn 规则规定，如果超过了超时时间，就把当前的 rtt_seq 清除，放弃之前的数据包的 RTT 采样。

$\text{SampleRTT}$ 仅能反应当前的 RTT。为了防止网络波动较大的影响，令：

$$\text{EstimatedRTT} = 0.875 \cdot \text{EstimatedRTT} + 0.125 \cdot \text{SampleRTT}$$

$\text{EstimatedRTT}$ 由多个 $\text{SampleRTT}$ 组成。当前最新得到的 $\text{SampleRTT}$ 有权重 $0.125$，避免网络波动的影响。而之前的 $\text{SampleRTT}$ 的权重会不断地以系数 $0.875$ 进行指数级衰减，这使得离现在较近的 $\text{SampleRTT}$ 的权重大，较远的 $\text{SampleRTT}$ 权重小。

同时还有 $\text{DevRTT}$ 反应当前网络波动的情况：

$$\text{DevRTT} = (1-\beta) \cdot \text{DevRTT} + \beta \cdot \left | \text{SampleRTT} - \text{EstimatedRTT} \right |$$

最终需要设置的超时时间为：

$$\text{TimeoutInterval} = \text{EstimatedRTT} + 4 \cdot \text{DevRTT}$$

初始时，$\text{TimeoutInterval}$ 设置为 $1$ 秒。

而如果计时器超时，触发重传时，说明当前网络情况很差，于是就会令 $\text{TimeoutInterval} = 2 \cdot \text{TimeoutInterval}$。但如果后续收到了 ACK，那么 $\text{TimeoutInterval}$ 就仍按照 $\text{EstimatedRTT}$ 和 $\text{DevRTT}$ 计算。如果后续仍没收到 ACK，$\text{TimeoutInterval}$ 会呈指数级增长，直到到达了操作系统的限制，TCP 连接就会断开。

3.5 流量控制

为了防止发送方发送数据太多太快，使得接收方的接收缓冲区溢出，于是就有了流量控制。

在接收方，令 $\text{LastByteRead}$ 为应用层读取的到的最后一个字节序号，$\text{LastByteRcvd}$ 为接收方接收到的最后一个字节序号，$\text{RcvBuffer}$ 为接收方缓冲区大小。那么接收方就有一个接收端口大小 $\text{rwnd}$，表示当前还能接收到的字节数，为：

$$\text{rwnd} = \text{RcvBuffer} - \left( \text{LastByteRcvd} - \text{LastByteRead} \right )$$

接收方通过 TCP 数据包头部把自己的 $\text{rwnd}$ 告诉发送方。发送方需要保证：

$$\text{LastByteSent} - \text{LastByteAcked} \le \text{rwnd}$$

不过这又会有一个问题，接收方并不会主动通知接收窗口。这会导致发送方在得知接收窗口为 $0$ 后就不发数据了，而不发数据就不知道新的接收窗口，这陷入了一个死循环。

因此发送方在得知接收窗口为 $0$ 后会启动一个持续计数器（Persist Timer），每次计数器触发时，都会发送一个窗口探测的数据包，这个数据包的负载数据只有 $1$ 字节，为想要发送的数据的第一个字节。是 $1$ 字节而不是 $0$ 字节的原因是，对于负载数据为 $0$ 的数据包是不回复 ACK 的。

接收方在收到这个窗口探测数据包后会回复 ACK，并在 ACK 数据包中告知当前接收窗口的大小。值得注意的是，如果接收方缓冲区仍满的话，接收方会直接丢弃这个 $1$ 字节的负载数据，Acknowledgment number 还是上一个字节。

3.6 拥塞控制

数据包在传输时会经过若干个 router，每个 router 的内部有一个队列，存放到达该 router 的数据包。当队列接近满时，说明这个链路上的拥塞程度比较大。当队列已经满时，router 会把到达的数据包直接丢弃。

TCP 为了防止丢包情况比较频繁，会在当前链路上的拥塞程度比较大时降低发送数据包的速率。

TCP 通过调整拥塞窗口 $\text{cwnd}$ 来控制数据包的速率，类似流量控制，需要满足当前已发送但是没有被 ack 的字节数不超过 $\text{cwnd}$，即：

$$\text{LastByteSent} - \text{LastByteAcked} \le \text{cwnd}$$

3.6.1 TCP Tahoe

TCP Tahoe 是 TCP 的早期版本。其拥塞控制分成两个阶段：

• Slow start 阶段：

  一般来说，初始时会将 $\text{cwnd}$ 大小设置为 $\text{MSS}$。服务端每收到一个 ACK，说明当前网络情况良好，就令 $\text{cwnd} = \text{cwnd} + \text{MSS}$ 并将重复 ACK 的计数归零。这就使得，基本上每经过一个 $\text{RTT}$，$\text{cwnd}$ 就会翻一倍，呈指数级增长（因为 $\text{cwnd}$ 越大，发出的报文段越多，收到的 ACK 越多）。

  slow start 阶段实际上 $\text{cwnd}$ 的增长速度并不慢，甚至很快，这里的慢只是意味着从较小的 $\text{cwnd}$ 开始。

  为避免 $\text{cwnd}$ 无限增长，我们设置一个 $\text{ssthresh}$ 值为 slow start 阶段的阈值，这个值初始时设置为 $64 \text{KB}$。

  如果 $\text{cwnd} \ge \text{ssthresh}$，就进入 Congestion avoidance 阶段。

• Congestion avoidance 阶段：

  进入这个阶段后，$\text{cwnd}$ 会随时间大致线性增加。具体来说是每收到一个 ACK 后，令 $\text{cwnd} = \text{cwnd} + \text{MSS} \cdot \frac{\text{MSS}}{\text{cwnd}}$，防止网络过早出现拥塞。

无论是在 Slow start 阶段还是在 Congestion avoidance 阶段，如果出现超时，或者连续四次收到了重复的 ACK（第一个 ACK 是初始的 ACK，然后后续连续三个表明服务端需要立刻重传当前第一个没被 ack 的数据包）（也即重复 ACK 的计数增长到 $3$），说明当前网络情况有点拥堵，于是会令 $\text{ssthresh} = \frac{\text{cwnd}}{2}$，再令 $\text{cwnd}=1$，同时回到 Slow start 最开始的阶段。如果是由于重复 ACK 触发的，还会将重复 ACK 的计数归零。

这么做的目的是为了迅速减少注入网络中的流量，使得发生拥塞的 router 有足够时间把队列中积压的部分处理完。

3.6.2 TCP Reno

TCP Reno 在 TCP Tahoe 的基础上增加了 Fast recovery 机制。如果连续四次收到了重复的 ACK ，那么会令 $\text{ssthresh} = \frac{\text{cwnd}}{2}$，同时令 $\text{cwnd} = \text{ssthresh}$，然后进入拥塞避免阶段，这相当于直接跳过了 Slow start 阶段。

Fast recovery 的道理是这样的：如果连续四次收到了重复的 ACK ，那么说明后续的多个报文段已经成功抵达接收方，网络中可能并未发生严重的拥塞。

一般来说处于 Slow start 阶段的时间比较短（毕竟是指数级增长超过 $\text{ssthresh}$），可以忽略不计。在 Congestion avoidance 阶段 $\text{cwnd}$ 是线性增长的，而触发 Fast recovery 机制，$\text{cwnd}$ 几乎是砍半的，于是整个连接的生命周期中 $\text{cwnd}$ 的变化大致如下：

AIMD 及公平性

TCP Tahoe 和 TCP Reno 有个共同点：$\text{cwnd}$ 增加时是加性的，减小时是乘性的，即 additive-increase, multiplicative-decrease（AIMD）。这种 AIMD 的算法可以保证，如果链路上吞吐量的瓶颈是 $R$，当前有 $n$ 个连接，则每个连接都能趋向于分到 $\frac{R}{n}$ 的吞吐量，每个连接之间是公平的。

可以用下图来进行大致的证明：

加性增可以使得点沿着平行于 Equal bandwidth share 方向移动，乘性减可以使得点沿着原点的方向移动，于是点就不断地靠近了 Equal bandwidth share。

AIMD 的调整是随着 ACK 包的到来而调整的。一个连接 ACK 包来的越快，即 RTT 越短，该连接的 $\text{cwnd}$ 调整地越快。当网络中拥塞情况缓解时，RTT 快的连接能够暂时占据到优势。

3.6.3 TCP Cubic

TCP Cubic 在 TCP Reno 的基础上对 Congestion avoidance 阶段进行了优化。

当超时或是重复 ACK 包发生时，会记录下当前的 $\text{cwnd}$ 值，令其为 $W_{\text{max}}$。后续再进入 Congestion avoidance 阶段时，Congestion avoidance 就不会再线性增长了，而是按一个三次函数的增长速度先慢后快地增长。大概如图所示：

3.6.4 ECN

上面三个算法是仅在传输层上实现的，一个缺点是不能及时调整，比较被动。

ECN，即 explicit congestion notification，借助网络层提供的功能来实现拥塞控制。

• 协商 ECN 能力

  TCP 头部的 ECE 和 CWR 标记在此时发挥了作用。在握手时，客户端发送 SYN 时，如果标记 ECE 为 $1$，CWR 为 $1$，则表明客户端一侧支持 ECN 能力。当服务端回复 SYNACK 时，如果标记 ECE 为 $1$，CWR 为 $0$ 则表明服务端支持，那么后续数据包将启用 ECN。服务端回复时如果标记 ECE 为 $0$，CWR 为 $0$ 则表明服务端不支持。

• 传输时 ECN 标记

  IP 头部的 Type of Service 字段的末尾是 ECN 字段。ECN 字段的取值有如下几种：00 表示不支持 ECN，01 或是 10 表示支持 ECN，11 表示链路上出现了拥塞。

  当链路上的 router 发现 IP 头部的 ECN 字段取值是 01 或是 10 ，且该 router 也支持 ECN 时，该 router 会判断当前是否拥塞（具体的判断方法并没有明确的标准），如果拥塞了则将 ECN 字段改成 11。

• 接收方通知发送方

  接收方收到数据包后，如果发现数据包的 IP 头部的 ECN 字段为 11，说明路径上存在了拥塞，那么在后续发送 ACK 时，都将 TCP 头部的 ECE 标记都设置为 $1$，直到收到了标记有 CWR 的数据包。

  发送方如果发现收到的 ACK 中含有 ECE 标记的话，就会收缩 $\text{cwnd}$，并回复 CWR ，表明自己已经降速。

3.6.5 TCP Vegas

TCP Vegas 使用基于延迟的拥塞控制算法。大概思想是，观察 RTT 的最小值 $RTT_{\text{min}}$（这个最小值一般是取近期的几个 RTT 采样中的最小值），这个值表明网络中处于空闲状态时的情况。设当前的拥塞窗口大小为 $\text{cwnd}$，当前的 RTT 值为 $RTT_{\text{now}}$。那么最好情况下的吞吐量 $Expected = \frac{\text{cwnd}}{RTT_{\text{min}}}$，当前的吞吐量 $Actual = \frac{\text{cwnd}}{RTT_{\text{now}}}$ ，中间的差值 $diff = Expected - Actual$ 表明了有多少数据积压在 router 的队列中。如果 $diff$ 过低，说明当前网络情况良好，可以适当提高 $\text{cwnd}$ 。如果 $diff$ 过高，说明当前网络比较拥堵，需要适当降低 $\text{cwnd}$。

TCP Vegas 貌似主要用在数据中心内部服务器之间的通信。因为现在网络上 TCP Cubic 和 TCP Reno 的流量比较多，而 TCP Vegas 的算法“过于礼貌”，容易吃亏。

4. 错题

选 D。应该是远程登录需要连接状态。