本文记录了 Lab 2: the TCP receiver 的实验过程

Lab 材料：Lab 2: the TCP receiver

在前面两个 Lab 中我们已经实现了 ByteStream 和 StreamReassembler，在这里 Lab 中，我们将实现完整的 TCP receiver 部分，它会处理即将到来的 byte stream。

Task #1：Translating between 64-bit indexes and 32-bit seqnos

在 StreamReassembler 中，每个字串都有一个 64-bit 的 index，它表示这个子串的第一个字符在整个 streams 中的位置（index 从 0 开始）。然而在 TCP 的头部，为了节省空间，我们会使用 32-bit 的序列号（seqno）来表示每个 stream 的 index，这样就增加了实现的难度：

  • TCP 的 streams 可以是无限长的，然而 32-bit 最多表示 $2^{32}$ 个字节，也就是 4 GiB。一旦序列号到达 $2^{32}-1$，那么下一个序列号从 0 继续开始
  • 为了安全，一个 streams 的第一个序列号（ISN）应该是随机的，ISN 也就是携带 SYN = true 的这个 segment 的序列号。数据部分的序列号为 $(ISN + k)\ mod \ 2^{32}，k=1\cdots n$
  • 在 TCP 中，SYN 和 FIN 控制标志也占用一个 seqno，但是 SYN 和 FIN 并是 stream 的一部分，即它们不是 bytes，它们表示 streams 的开始和结束

实验指导书有一个例子，可以仔细对着看一下

Sequence Numbers Absolute Sequence Numbers Stream Indices
从 ISN 开始 从 0 开始 从 0 开始
包括了 SYN/FIN 包括了 SYN/FIN 不包括 SYN/FIN
32 bits，wrapping 64 bits，non-wrapping 64 bits，non-wrapping
“seqno” “absolute seqno” “stream index”

因此，首先查看一下 wrapping_integers.hh 文件的函数，再实现 wrapping_integers.cc 文件中的两个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * n 表示一个绝对序列号，isn 表示初始序列号
 */
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    uint32_t offset = n & (0xffffffff);
    return isn + offset;
}

/**
 * 计算 n 的绝对序列号，使它最接近 checkpoint
 */
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    WrappingInt32 wrap_checkpoint = wrap(checkpoint, isn);
    int32_t diff = n - wrap_checkpoint;
    if (static_cast<int64_t>(diff + checkpoint) < 0) {
        return checkpoint + static_cast<uint32_t>(diff);
    }
    return checkpoint + diff;
}

测试

1
2
make -j4
ctest -R wrap

Task #2：Implementing the TCP receiver

TCPReceiver 会：

  1. 接收对方发送的 segments
  2. 使用 StreamReassembler 来重新组装 ByteStream
  3. 计算 ackno 以及 window size，ackno 和 window size 会通过 sender 发送给对方

查看实验指导书 P6 的 TCP Segment 的 格式

思路

在第一个带有 SYN = true 的 segment 被接收之前，我们不需要处理收到的 segment，因此我添加了两个私有成员

1
2
3
4
5
6
7
8
9
10
11
//! The initial sequence number.
WrappingInt32 _isn;
WrappingInt32 _ackno;

//! `true` if receive the first segment with SYN = true.
bool _syn;

//! `true` if receive the last segment with SYN = true.
bool _fin;

uint64_t _checkpoint;

然后实现下面三个需要实现的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 1. TCPReceiver 不会接收还未开始或者已经结束的 segment
 * 2. 如果 TCPReceiver 的 _syn 为 false 且收到的 segment 的头部 `SYN = true`，那么更新对应的成员变量
 * 3. 计算窗口区间 [win_begin, win_end]、序列号区间 [seq_begin, seq_end] 以及 payload 的长度（注意 SYN/FIN
 *    不算在 payload 的长度里面，但是它们分别占用一个序列号）
 * 4. 如果这个 segment 在窗口区间内，则接收这个 segment，同时更新 _checkpoint
 * 5. 判断 receiver 是否应该结束
 * 6. 更新 _ackno
 */
void TCPReceiver::segment_received(const TCPSegment &seg) {}

/**
 * 1. 如果 `_syn` 为 false，则返回空
 * 2. 返回 _ackno
 */
optional<WrappingInt32> TCPReceiver::ackno() const { return {}; }

/**
 * 窗口大小为 ByteStream 的剩余容量
 */
size_t TCPReceiver::window_size() const {}

测试

1
2
make -j4
make check_lab2