CS144 Lab2 笔记 — Sequence Numbers 与 TCP Receiver

今天的任务比较简单，总共就要实现两个任务：Sequence Numbers 的转化与 TCP Receiver 的实现。

下面对 Lab2 的两个任务进行分析。

Sequence Number

TCP 的序列结构本质上就是围绕「可靠、有序的字节流」设计的一套编号体系。TCP 不关心数据包，而关心一个连续的字节流，因此需要给每个字节编号。

TCP 中主要涉及三个东西：

TCP Sequence Number（报文中的序列号）
TCP Sequence Number 的空间结构
Absolute Sequence Number（内部逻辑序号）

概念	Sequence Number (seqno)	Absolute Sequence Number	Stream Index
起点	ISN（Initial Sequence Number）	0	0
是否包含 SYN/FIN	包含	包含	不包含
位数	32 bit，会回绕	64 bit，不回绕	64 bit，不回绕
用途	TCP 报文头里的 seq 字段	内部逻辑计算	ByteStream 中数据的位置

Sequence Number 直接在 TCP 报文当中，是一个 32 位整数；而 Absolute Sequence Number 是一个 64 位整数。当 Sequence Number 记录值超过 32 位时会以循环的形式进行计数。

我们这个实验的任务就是实现 unwrap 和 wrap 的 sequence number 换算。

wrap

具体换算逻辑如下：

//! Transform an "absolute" 64-bit sequence number (zero-indexed) into a WrappingInt32
//! \param n The input absolute 64-bit sequence number
//! \param isn The initial sequence number

我们得到的是 n——一个 64 位 absolute sequence number，和一个 WrappingInt32 类型的 isn（initial sequence number）。

直接取 n 的前 32 位和 isn 相加，然后返回 WrappingInt32 即可：

WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    return WrappingInt32(static_cast<uint32_t>(n) + isn.raw_value());
}

unwrap

对 unwrap 的实现则比刚刚那个相对复杂一些。需要输入 3 个参数：

//! Transform a WrappingInt32 into an "absolute" 64-bit sequence number (zero-indexed)
//! \param n The relative sequence number
//! \param isn The initial sequence number
//! \param checkpoint A recent absolute 64-bit sequence number
//! \returns the 64-bit sequence number that wraps to `n` and is closest to `checkpoint`

n 即发过来的 seqno，isn 是 initial sequence number，checkpoint 是最近的一个 absolute seqno。

因为 seqno 只有 32 位，会循环，所以一个 seqno 对应多个 absolute seqno：

absolute = offset + k * 2^32

其中：

offset = n - isn

k 表示第几次回绕。

unwrap 的目标：找到距离 checkpoint 最近的那个 absolute。

直接看我们当前得到的 uint64_t t = (checkpoint & 0xFFFFFFFF00000000) + offset，与两边的 checkpoint 相比较，取这 3 个可能的结果中距离 checkpoint 最近的那一个就行了。

最终代码：

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    uint32_t offset = n.raw_value() - isn.raw_value();
    uint64_t t = (checkpoint & (0xFFFFFFFF00000000)) + offset;
    uint64_t ret = t;
    if (abs(int64_t(t + (1ul << 32) - checkpoint)) < abs(int64_t(t - checkpoint)))
        ret = t + (1ul << 32);
    if (t >= (1ul << 32)
        && abs(int64_t(t - (1ul << 32) - checkpoint)) < abs(int64_t(ret - checkpoint)))
        ret = t - (1ul << 32);
    return ret;
}

TCP Receiver

TCP Receiver 是 TCP 协议里的重头戏，但总的来说，前面两次实验已经把该有的数据结构与算法部分完成了。今天主要要做的就是实现 TCP 接收方的连接过程。

我们都知道 TCP 的 connect 有三次握手，TCP 的 disconnect 有四次挥手。

三次握手

第一次握手：SYN 报文段

客户端向服务器发送一个 SYN（同步）报文段，其中包含客户端的初始序列号（ISN）。ISN 是一个随机值，用于标识数据包的顺序。

关键字段：

SYN 标志位：1（表示请求建立连接）
ACK 标志位：0（不携带确认信息）
序列号（Sequence Number）：客户端生成的随机数（如 ISN=1000）

第二次握手：SYN-ACK 报文段

服务器收到 SYN 报文段后，验证客户端 IP 和端口是否合法。若合法，则回复 SYN-ACK（同步确认）报文段。

关键字段：

SYN 标志位：1（表示同意建立连接）
ACK 标志位：1（表示确认客户端的 SYN）
确认号（Acknowledgment Number）：客户端 ISN+1（如 1001）
序列号：服务器生成的随机数（如 ISN=2000）

第三次握手：ACK 报文段

客户端收到 SYN-ACK 报文段后，验证服务器 IP 和端口。若合法，则发送 ACK（确认）报文段。

关键字段：

ACK 标志位：1（表示确认服务器的 SYN）
序列号：客户端 ISN+1（如 1001）
确认号：服务器 ISN+1（如 2001）

此时客户端和服务器均可开始数据传输。

四次挥手

第一次挥手：FIN 报文段

主动关闭方决定关闭连接时，发送 FIN（结束）报文段，表示不再发送数据。

关键字段：

FIN 标志位：1（表示请求关闭连接）
ACK 标志位：1（表示确认已接收的数据）
序列号：当前序列号（如客户端序列号=5000）
确认号：对方已接收的数据序列号+1（如服务器确认号=6001）

第二次挥手：ACK 报文段

被动关闭方收到 FIN 报文段后，回复 ACK 报文段，表示已收到关闭请求。

关键字段：

ACK 标志位：1（表示确认 FIN）
序列号：当前序列号（如服务器序列号=4000）
确认号：对方序列号+1（如客户端确认号=5001）

第三次挥手：FIN 报文段

被动关闭方完成数据传输后，发送 FIN 报文段，请求关闭连接。

关键字段：

FIN 标志位：1（表示请求关闭连接）
ACK 标志位：1（表示确认已接收的数据）
序列号：当前序列号（如服务器序列号=4000）
确认号：对方已接收的数据序列号+1（如客户端确认号=5001）

第四次挥手：ACK 报文段

主动关闭方收到 FIN 报文段后，回复 ACK 报文段，完成连接关闭。

关键字段：

ACK 标志位：1（表示确认 FIN）
序列号：当前序列号（如客户端序列号=5001）
确认号：对方序列号+1（如服务器确认号=4001）

三次握手与四次挥手和今天任务的关系

这和如何处理 TCP 请求头的信息并更新接收状态的关系非常紧密：

作为接收方，需要接收对面发来的 SYN 请求，这样才可以开始接收流，然后初始化 head_index 去移动滑动窗口接收 data
需要接收来自对面的 FIN 请求，这样才可以结束当前会话，给 ByteStream 加上一个 EOF 的结尾
同时也得拒绝在连接终止前再次发来的 SYN 请求，防止连接重复
抛弃没有接收到 SYN 请求前的 data（还没有建立连接）

只有明白了三次握手与四次挥手，才能确保 TCP Receiver 接收到的信息是合法的。

Receiver 的实现思路

结合 TCP 滑动窗口机制可以发现：rcv 有一个 rcv_base 用于指向窗口的头部，这个头部其实就是期待的数据。当这个数据被接收到后，窗口就可以右移，同时会把这片真正的数据压入流中。有一个长度为 N 的窗口，这个窗口内的数据就是缓存区域——处于这个缓存区域的数据，也就是之后 rcv_base 移动到这个地方时不用等待、直接就可以用的。

是不是很熟悉？没错，之前的 StreamReassembler 就是干的这活。而我们只需要注意如何从 TCP 携带的头与数据中提取出 index 信息、data 信息与 eof 信息，向这个 StreamReassembler 发送——这就是 TCP Receiver 要做的了。

综上，TCP Receiver 具体的逻辑如下：

判断对面发来的是否是 SYN 请求。若是，判断我们是否已经有 SYN 请求——若有，该请求被抛弃；若没有，对当前的连接状态进行更新（_syn_flag = true），同时初始化 absolute seqno = 1 以及 rcv_base = 1。然后记录当前接收到的 data 的长度。

确认是否是 SYN 请求后，确认连接已经建立：

if (seg.header().syn) {
    // ...
} else if (!_syn_flag) {
    return false;
}

如果确认了请求不是 SYN 且之前已经同步过，直接通过 unwrap 获取绝对序列号与数据长度：

abs_seqno = unwrap(WrappingInt32(seg.header().seqno.raw_value()),
                   WrappingInt32(_isn), abs_seqno);
length = seg.length_in_sequence_space();

FIN 处理

然后确认这个请求是否是 FIN 请求。

FIN 与 SYN 类似，同样会占用 TCP sequence space 中的一个序号，但不同的是 FIN 只代表发送方向的数据流结束。因此 Receiver 需要记录该状态，并将 FIN 信息传递给 StreamReassembler，最终由 ByteStream 表现为 EOF。

首先判断当前 segment 是否携带 FIN：

if (seg.header().fin) {
    if (_fin_flag) {
        return false;
    }
    _fin_flag = true;
    ret = true;
}

如果之前已经接收到 FIN，则说明这是重复 FIN，可以直接忽略。如果这是第一次 FIN，则记录 FIN 状态。

但是注意，收到 FIN 并不代表 ByteStream 可以立即结束，因为 FIN 之前可能还有未到达的数据。例如：

seq=100        seq=200
 DATA --------- FIN

如果中间 seq=150~199 的数据还没有收到，那么此时不能直接关闭输入流。

因此 FIN 不能简单理解为：

收到 FIN -> EOF

而应该理解为：

收到 FIN -> 记录结束位置
所有 FIN 之前的数据收到 -> EOF

所以 TCPReceiver 不负责直接关闭 ByteStream，而是继续将数据交给 StreamReassembler：

_reassembler.push_substring(
    seg.payload().copy(),
    abs_seqno - 1,
    seg.header().fin
);

这里：

seg.payload() 是 TCP 携带的数据
abs_seqno - 1 是对应 ByteStream 的 index
seg.header().fin 告诉 reassembler 当前数据后是否存在 EOF

为什么需要减一？

因为 TCP sequence number 与 Stream index 存在偏移：

SYN 占用一个序号

TCP seq:
ISN          SYN
ISN+1        第一个数据

Absolute:
0            SYN
1            第一个数据

Stream index:
0            第一个数据

所以：

absolute sequence number - 1 = ByteStream index

更新接收窗口

之后需要根据 reassembler 的状态更新 receiver 当前期待的下一个序号：

_base = _reassembler._head_index + 1;

其中 _base 就是当前 receive window 的左边界，也就是「下一个期望收到的数据序号」。

当 reassembler 已经将连续数据写入 ByteStream 后：

recv window:

        base
         |
---------v-----------------
|已接收|未接收缓存区域|
---------^-----------------

窗口向右移动。

如果 reassembler 判断输入已经结束：

if (_reassembler.input_ended()) {
    _base++;
}

说明 FIN 前的数据全部收到，并且 FIN 已经被处理。由于 FIN 自身占用一个 sequence number：

data sequence:
100 101 102 ... 200

FIN:
201

所以需要额外移动 _base 跳过 FIN。

TCPReceiver 核心流程总结

SYN 检查

没有 SYN:
    丢弃数据
收到 SYN:
    初始化 ISN
    建立 sequence number 映射

Sequence number 转换

TCP seqno
      |
      v
absolute sequence number
      |
      v
Stream index

窗口过滤 —— 丢弃超出 receive window 的数据、已经确认过的数据
交给 StreamReassembler

TCP segment
      |
      v
StreamReassembler
      |
      v
ByteStream

FIN 处理

收到 FIN
    |
记录结束位置
    |
等待之前数据全部重组
    |
ByteStream EOF

因此，TCPReceiver 本质上并不负责可靠传输本身，而是负责将 TCP 层的 segment 转换为 StreamReassembler 能理解的连续字节流，并维护 TCP 连接状态。前面实现的 StreamReassembler 正是 TCPReceiver 后半部分的核心组件。

最终实现

bool TCPReceiver::segment_received(const TCPSegment &seg) {
    bool ret = false;
    static size_t abs_seqno = 0;
    size_t length;
    if (seg.header().syn) {
        if (_syn_flag) {
            return false;
        }
        _syn_flag = true;
        _base = 1;
        _isn = seg.header().seqno.raw_value();
        abs_seqno = 1;
        ret = true;
        length = seg.length_in_sequence_space() - 1;
        if (length == 0) {
            return true;
        }
    } else if (!_syn_flag) {
        return false;
    } else {
        abs_seqno = unwrap(WrappingInt32(seg.header().seqno.raw_value()),
                           WrappingInt32(_isn), abs_seqno);
        length = seg.length_in_sequence_space();
    }
    if (seg.header().fin) {
        if (_fin_flag) {
            return false;
        }
        _fin_flag = true;
        ret = true;
    } else if (seg.length_in_sequence_space() == 0 && abs_seqno == _base) {
        return true;
    } else if (abs_seqno >= _base + window_size() || abs_seqno + length <= _base) {
        return ret;
    }
    _reassembler.push_substring(seg.payload().copy(), abs_seqno - 1, seg.header().fin);
    _base = _reassembler._head_index + 1;
    if (_reassembler.input_ended()) {
        _base++;
    }
    return true;
}

总的来说，Lab2 的任务较为简单，就是对之前任务的封装，以及一个序列转换小工具的实现。但依旧可以从中扩展出很多知识——比如今天所回顾到的三次握手与四次挥手，以及 TCP 的 header 机制，还是挺有意思的。

KPBOT / CS144 Lab2 笔记 — Sequence Numbers 与 TCP Receiver

Sequence Number

wrap

unwrap

TCP Receiver

三次握手

四次挥手

三次握手与四次挥手和今天任务的关系

Receiver 的实现思路

FIN 处理

为什么需要减一？

更新接收窗口

TCPReceiver 核心流程总结

最终实现