Lab2：the TCP Receiver

lab2.pdf (cs144.github.io) (opens new window)

在这个 lab 中，我们要实现 TCP 的 Receiver。

在之前 lab1 中，我们给每一个字节都标了一个序号，序号从 0 开始，是一个 uint64_t 类型的数据。而在 TCP 中则有所不同，数据是无穷无尽的，所以显然 uint64_t 的数据会有溢出行为，因此我们采用 wrapping 的方法，并用 uint32_t 来存储，也就是说，序号将以 1 << 32 为周期循环。

在发送方第一次向接收方发送报文段时，会标记头部中的 SYN 字段，在最后一次发送时则会标记头部中的 FIN 字段。而在第一次发送时，也就是 SYN 被标记为 1 的报文段中头部的 seqno 就是 ISN，即要传输的这一组报文段的起始序号。ISN 是随机的，这是为了避免和上一轮 TCP 传输的报文段序号混淆。另外在接收方，我们将维护两个值 ackno 和 window_size。ackno 指的是接收方下一个希望接收到的序号，也就是 lab1 中的 expected_num（回想一下，TCP 是累积确认的），但区别在于 expected_num 并不统计标志位所占据的序号，而 ackno 会统计。 windows_size 是接收窗口的大小，起到了流量控制的作用，其值也就是 lab1 中的 capacity 再减去此时 ByteStream 中还未被进程读取的字节数，即 _capacity - stream_out().buffer_size()，那么很显然，我们接下来能接受的数据范围就是 [ackno，ackno + windows_size)。

在具体实现 TCP Receiver 之前，我们先要完成序号的 translation，下面是一张文档里的图片，这个例子中的 ISN 为

对于 wrap() 函数，我们要将 absolute seqno 转化为 seqno，还是比较简单的。

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

而 unwrap() 就有点 tricky 了，我们要将 seqno 转化为 absolute seqno，并且要选择离 checkpoint 最近的那个。

我们先令周期为 P = 1 << 32，我们先求出 checkpoint 所属的那个周期区间中的一个解，之后我们还要特殊判断一下下一个周期和上一个周期是否更优，具体看代码。

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    uint64_t down = checkpoint & 0xFFFFFFFF00000000; // 所属周期的最小值
    uint64_t offset = n.raw_value() - isn.raw_value(); // 偏移量
    uint64_t m = down + offset; // checkpoint 所属周期中的一个解
    uint64_t P = 1uL << 32; // 周期长度
    uint64_t res = m; 
    uint64_t dif = (checkpoint >= res) ? checkpoint - res : res - checkpoint; // 当前解的差
    // 下面是对下一个区间和上一个区间中的解进行判断是否更优，需要注意不要数据上溢和下溢
    if (m + P > P && (m + P - checkpoint) < dif) {
        dif = m + P - checkpoint;
        res = m + P;
    }
    if (m >= P && checkpoint - (m - P) < dif) {
        res = m - P;
    }
    return res;
}

接下来是正式进入了 TCP 的实现部分。

【这部分有参考过 PKUFlyingPig (opens new window)】

下面给出定义的 private 成员变量

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

//! The maximum number of bytes we'll store.
size_t _capacity;
bool syn; // 是否出现过 SYN
bool fin; // 是否出现过 FIN
WrappingInt32 isn; // the Initial Sequence Number 

我们先实现比较简单的求 ackno 和 windows_size

optional<WrappingInt32> TCPReceiver::ackno() const {
    if (syn) { // 接受过数据
        return wrap(_reassembler.exp() + syn + (_reassembler.empty() && fin), WrappingInt32(isn)); // syn 和 fin 都会占据一个 sequence number
    }
    return std::nullopt;
}

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

关于 window_size() 就不多赘述了。

而在 ackno() 中，需要注意的是 SYN 和 FIN 也会占据一个 seqno；(_reassembler.empty() && fin) 如果成立的话表示当前所有数据存储完了，也就是 FIN 已经在 ackno 的统计范围内了。

最后是重头戏 segment_received()

void TCPReceiver::segment_received(const TCPSegment &seg) {

    TCPHeader head = seg.header(); // 获取头部

    std::string data = seg.payload().copy();

    if (syn == false && head.syn == false) {
        return;
    }

    bool eof = false;

    if (syn == false && head.syn == true) { // 如果这是初始段
        syn = true;
        isn = head.seqno;
        if (fin == false && head.fin == true) { // 这也是末尾段
            eof = fin = true;
        }
        _reassembler.push_substring(data, 0, eof);
        return;
    }

    if (head.fin == true) {
        eof = fin = true;
    }

    _reassembler.push_substring(
        data,
        unwrap(head.seqno, isn, _reassembler.exp() + syn - 1) - syn, // syn 和 fin 都会占据一个 sequence number；checkpoint 是上一个 ackno - 1 的位置
        eof
    );
}

我们对 SYN 和 FIN 为 1 的报文段要特殊处理，最后将值写入 Reassembler 中。

在 push_substring 的时候，关于下标序号我们要去掉对 SYN 和 FIN 的统计，并根据我们要将当前报文段的 seqno 和 ISN 计算出正确的序号值。

需要注意的是，在这里 unwrap() 所使用的 checkpoint 是最后一个被 reassembler 的字节序号，也就是 ackno - 1，即 _reassembler.exp() + syn - 1（这里的序号是包含 syn 统计的）

而关于为什么要额外定义变量 eof，而不能直接用 fin 来代替是因为，fin 只是用来标记是否出现过 FIN 标记位为 1 的情况，但由于可能失序，因此当前的报文段不代表就是最后的一组。

实验结果