CS144 Lab2 The TCP Receiver

Lab 1 所做的都是些数据结构的东西，不涉及网络，而Lab 2会真正开始触及网络的内容。

Lab 2 会完成 TCPReceiver，从Internet接收一个TCP segment，解析其内容并交给Lab1做的StreamReassembler处理，然后应用层从StreamReassembler读取排列好的数据。

介绍

除了将bytes传入StreamReassembler以外，TCPReceiver还要告诉Sender两个东西：acknowledge number和window size。这俩定义了receiver所有 “感兴趣” 的bytes区间，也就是receiver可以接收的bytes区间。这个“感兴趣”区间之前的bytes已经确定无误不需要再重发，这个“感兴趣”区间之后的bytes太多了处理不过来。

在Lab1 中，所有的bytes都以index=0开始，且index是一个64位数，特别大而可以视为不会overflow。但TCP为节约空间，sequence number只有32位，且起点不为零，所以会出现overflow。而给定的window size可以帮助我们解决overflow，因为当给定一个较小范围的window，很容易判断一个seqno是否overflow了。

3.1 Translating between 64-bit indexes and 32-bit seqnos

这里也引入了另外两个概念，absolute sequence number和stream index。

用例子很好理解，当传输三个bytes ”cat” 时：

seqno 即TCP header里的随机生成的、SYN传递的那个东西，也是真实用在TCP中使用的用于表示包顺序的数。

而seqno不是从零开始的，把其开始index视为0，得到的这个抽象的概念上的seqno就是absolute seqno。因为这是一个抽象的数学上的数字，并不需要实际用计算机表示出来，所以也不会受到计算机里整型数大小的限制，所以不需要考虑wrapped around。

进而，SYN和FIN不携带有效数据，但其本身也会占用一个seqno。如果只考虑携带的有效数据占用的seqno，就得到了stream index，也是lab1中的index。

seqno 与 absolute seqno 之间的转换比较麻烦，所以写了专门的转换函数和测试。

如果编译时找不到 **<pcap/pcap.h>**，就先安装 libpcap，再删build重新编译就可以了。

wrap 和 unwrap 的实现看这里 即可，这个博客的实现非常美妙。c++的unsigned types是可以overflow的，不会导致undefined behavior; signed types 才会。

3.2 Implementing the TCP receiver

接下来开始实现TCP Receiver：（1）接受TCP segment; (2) reassemble；（3）计算ackno 和window size。

高亮出来的就是receiver需要关注的：seqno, SYN, FIN, Payload。 这些都是由sender写入，receiver需要读取的。

实现

这个lab实现也会有很多细节需要自己看test调试，讲义并没有写那么细，处理edge cases也是很烦的。给的test应该不全面，据说后面的lab会让前面埋的雷全爆掉，所以这里还是要仔细点考虑所有edge cases，即使tests全过也要小心。（后续更新：果然，我在lab4中因为Receiver实现不够robust，导致出现bug，debug很久……）

class TCPReceiver {
    // Our data structure for re-assembling bytes.
    StreamReassembler _reassembler;
    // If received syn flag.
    bool _received_syn{false};
    // Initial sequence number.
    WrappingInt32 _isn;
    // The maximum number of bytes we'll store.
    size_t _capacity;

  public:
	... ...
}


// Receiver has three status:
// 1. Not received syn.
// 2. received syn, and not received fin.
// 3. received fin.
//
// So focus on these three status.
// _received_syn can different between 1 and 2.
// _reassembler.stream_out().input_ended() can different between 2 and 3.

void TCPReceiver::segment_received(const TCPSegment &seg) {
    // not received syned.
    if (!_received_syn) {
        if (!seg.header().syn) {
            // Not syn, return;
            return;
        }
        _received_syn = true;
        _isn = seg.header().seqno;
    }
    // Receiver's abs ackno.
    uint64_t abs_ackno = _reassembler.stream_out().bytes_written() + 1;
    // Seg's abs seqno.
    uint64_t curr_abs_seqno = unwrap(seg.header().seqno, _isn, abs_ackno);
    // Begin Idx in stream.
    uint64_t stream_index = curr_abs_seqno - 1 + (seg.header().syn);
    _reassembler.push_substring(seg.payload().copy(), stream_index, seg.header().fin);
}

optional<WrappingInt32> TCPReceiver::ackno() const { 
    if (!_received_syn) {
        return std::nullopt;
    }
    uint64_t abs_ackno = _reassembler.stream_out().bytes_written() + 1;
    if (_reassembler.stream_out().input_ended()) {
        abs_ackno += 1;
    }
    return WrappingInt32(_isn) + abs_ackno;
}

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