CS144计算机网络 Lab2

一、简介

这里记录了笔者学习 CS144 计算机网络 Lab2 的一些笔记 - TCP接收方实现 TCPReceiver

CS144 Lab2 实验指导书 - Lab Checkpoint 2: the TCP receiver

个人 CS144 实验项目地址 - github

二、环境配置

当前我们的实验代码位于 master 分支，而在完成 Lab 之前需要合并一些依赖代码，因此执行以下命令：

git merge origin/lab2-startercode

之后重新 make 编译即可。

三、TCPReceiver 简述

在 Lab2，我们将实现一个 TCPReceiver，用以接收传入的 TCP segment 并将其转换成用户可读的数据流。

TCPReceiver 除了将读入的数据写入至 ByteStream 中以外，它还需要告诉发送者两个属性：

• 第一个未组装的字节索引，称为确认号ackno，它是接收者需要的第一个字节的索引。
• 第一个未组装的字节索引和第一个不可接受的字节索引之间的距离，称为 窗口长度window size。

ackno 和 window size 共同描述了接收者当前的接收窗口。接收窗口是 发送者允许发送数据的一个范围，通常 TCP 接收方使用接收窗口来进行流量控制，限制发送方发送数据。

总的来说，我们将要实现的 TCPReceiver 需要做以下几件事情：

• 接收TCP segment
• 重新组装字节流（包括EOF）
• 确定应该发回给发送者的信号，以进行数据确认和流量控制

四、索引转换

TCP 报文中用来描述**当前数据首字节的索引（序列号 seqno）**是32位类型的，这意味着在处理上增加了一些需要考虑的东西：

• 由于 32位类型最大能表达的值是 4GB，存在上溢的可能。因此当 32位的 seqno 上溢后，下一个字节的 seqno 就重新从 0 开始。

• 处于安全性考虑，以及避免与之前的 TCP 报文混淆，TCP 需要让每个 seqno 都不可被猜测到，并且降低重复的可能性。因此 TCP seqno 不会从 0 开始，而是从一个 32 位随机数起步（称为初始序列号 ISN）。

  而 ISN 是表示 SYN 包（用以表示TCP 流的开始）的序列号。

• TCP 流的逻辑开始数据包和逻辑结束数据包各占用一个 seqno。除了确保接收到所有字节的数据以外，TCP 还需要确保接收到流的开头和结尾。 因此，在 TCP 中，SYN（流开始）和 FIN（流结束）控制标志将会被分别分配一个序列号（SYN标志占用的序列号就是ISN）。

  流中的每个数据字节也占用一个序列号。

  但需要注意的是，SYN 和 FIN 不是流本身的一部分，也不是传输的字节数据。它们只是代表字节流本身的开始和结束。

字节索引类型一多就容易乱。当前总共有三种索引：

• 序列号 seqno。从 ISN 起步，包含 SYN 和 FIN，32 位循环计数
• 绝对序列号 absolute seqno。从 0 起步，包含 SYN 和 FIN，64 位非循环计数
• 流索引 stream index。从 0 起步，排除 SYN 和 FIN，64 位非循环计数。

这是一个简单浅显的例子，用于区分开三种索引的区别：

序列号和绝对序列号之间相互转换稍微有点麻烦，因为序列号是循环计数的。在该实验中，CS144 使用自定义类型 WrappingInt32 表示序列号，并编写了它与绝对序列号之间的转换。

但这个需要我们自己实现，天下没有免费的午餐（笑）

这个实现稍微有点麻烦，而且实现的时候也最好避免各类循环，减少使用条件判断的次数，以提高执行效率。

我的实现如下所示，相关细节以注释形式写入至代码中：

//! 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
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    return WrappingInt32{isn + static_cast<uint32_t>(n)};
}

//! 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`
//!
//! \note Each of the two streams of the TCP connection has its own ISN. One stream
//! runs from the local TCPSender to the remote TCPReceiver and has one ISN,
//! and the other stream runs from the remote TCPSender to the local TCPReceiver and
//! has a different ISN.
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    // 32位的范围
    const constexpr uint64_t INT32_RANGE = 1l << 32;
    // 获取 n 与 isn 之间的偏移量（mod）
    // 实际的 absolute seqno % INT32_RANGE == offset
    uint32_t offset = n - isn;
    /// NOTE: 最大的坑点！如果 checkpoint 比 offset 大，那么就需要进行四舍五入
    /// NOTE: 但是!!! 如果 checkpoint 比 offset 还小，那就只能向上入了，即此时的 offset 就是 abs seqno
    if(checkpoint > offset) {
        // 加上半个 INT32_RANGE 是为了四舍五入
        uint64_t real_checkpoint = (checkpoint - offset) + (INT32_RANGE >> 1);
        uint64_t wrap_num = real_checkpoint / INT32_RANGE;
        return wrap_num * INT32_RANGE + offset;
    }
    else
       return offset;
}

四、TCPReceiver 实现

1. 要求

需要实现一些类成员函数

• segment_received(): 该函数将会在每次获取到 TCP 报文时被调用。该函数需要完成：

  • 如果接收到了 SYN 包，则设置 ISN 编号。

    注意：SYN 和 FIN 包仍然可以携带用户数据并一同传输。同时，同一个数据包下既可以设置 SYN 标志也可以设置 FIN 标志。

  • 将获取到的数据传入流重组器，并在接收到 FIN 包时终止数据传输。

• ackno()：返回接收方尚未获取到的第一个字节的字节索引。如果 ISN 暂未被设置，则返回空。

• window_size()：返回接收窗口的大小，即第一个未组装的字节索引和第一个不可接受的字节索引之间的长度。

这是 CS144 对 TCP receiver 的期望执行流程：

2. 具体实现

思路

对于 TCPReceiver 来说，除了错误状态以外，它一共有3种状态，分别是：

• LISTEN：等待 SYN 包的到来。若在 SYN 包到来前就有其他数据到来，则必须丢弃。
• SYN_RECV：获取到了 SYN 包，此时可以正常的接收数据包
• FIN_RECV：获取到了 FIN 包，此时务必终止 ByteStream 数据流的输入。

在每次 TCPReceiver 接收到数据包时，我们该如何知道当前接收者处于什么状态呢？可以通过以下方式快速判断：

• 当 isn 还没设置时，肯定是 LISTEN 状态
• 当 ByteStream.input_ended()，则肯定是 FIN_RECV 状态
• 其他情况下，是 SYN_RECV 状态

Window Size 是当前的 capacity 减去 ByteStream 中尚未被读取的数据大小，即 reassembler 可以存储的尚未装配的子串索引范围。

ackno 的计算必须考虑到 SYN 和 FIN 标志，因为这两个标志各占一个 seqno。故在返回 ackno 时，务必判断当前 接收者处于什么状态，然后依据当前状态来判断是否需要对当前的计算结果加1或加2。而这条准则对 push_substring 时同样适用。

源码实现

类声明：

class TCPReceiver {
    WrappingInt32 _isn;
    bool _set_syn_flag;

    //! Our data structure for re-assembling bytes.
    StreamReassembler _reassembler;

    //! The maximum number of bytes we'll store.
    size_t _capacity;

  public:
    ...
}

方法实现：

/**
 *  \brief 当前 TCPReceiver 大体上有三种状态， 分别是
 *      1. LISTEN，此时 SYN 包尚未抵达。可以通过 _set_syn_flag 标志位来判断是否在当前状态
 *      2. SYN_RECV, 此时 SYN 抵达。只能判断当前不在 1、3状态时才能确定在当前状态
 *      3. FIN_RECV, 此时 FIN 抵达。可以通过 ByteStream end_input 来判断是否在当前状态
 */

void TCPReceiver::segment_received(const TCPSegment &seg) {
    // 判断是否是 SYN 包
    const TCPHeader &header = seg.header();
    if (!_set_syn_flag) {
        // 注意 SYN 包之前的数据包必须全部丢弃
        if (!header.syn)
            return;
        _isn = header.seqno;
        _set_syn_flag = true;
    }
    uint64_t abs_ackno = _reassembler.stream_out().bytes_written() + 1;
    uint64_t curr_abs_seqno = unwrap(header.seqno, _isn, abs_ackno);

    //! NOTE: SYN 包中的 payload 不能被丢弃
    //! NOTE: reassember 足够鲁棒以至于无需进行任何 seqno 过滤操作
    uint64_t stream_index = curr_abs_seqno - 1 + (header.syn);
    _reassembler.push_substring(seg.payload().copy(), stream_index, header.fin);
}

optional<WrappingInt32> TCPReceiver::ackno() const {
    // 判断是否是在 LISTEN 状态
    if (!_set_syn_flag)
        return nullopt;
    // 如果不在 LISTEN 状态，则 ackno 还需要加上一个 SYN 标志的长度
    uint64_t abs_ack_no = _reassembler.stream_out().bytes_written() + 1;
    // 如果当前处于 FIN_RECV 状态，则还需要加上 FIN 标志长度
    if (_reassembler.stream_out().input_ended())
        ++abs_ack_no;
    return WrappingInt32(_isn) + abs_ack_no;
}

size_t TCPReceiver::window_size() const { return _capacity - _reassembler.stream_out().buffer_size(); }

测试结果就不贴了，不同的机器上跑所消耗的时间是不一样的，没什么可比性。