CS144计算机网络Lab2: The TCP Receiver

The arrangement of modules and dataflow in TCP implementation. `Lab2`要求实现一个`TCPReceiver`，包含以下几个功能：

• 接收TCPSegment；
• 调用字节流重组器；
• 向发送方发送相应确认信号；
• 流量控制。

这次的实验主要分为Translating between 64-bit indexes and 32-bit seqnos和Implementing the TCP receiver两个部分。前者是学习实现TCPSegment中的索引方式；后者是实现TCPReceiver的主要功能。

A. Translating between 64-bit indexes and 32-bit seqnos

这一部分需要实现TCP中表示索引的方式，在Lab1中我们实现了StreamReassembler，其中使用的index就是一个64-bit 并从0开始计数的stream index。然而TCP的首部空间寸土寸金，直接占用64-bit为免也太奢侈了，所以在实践中，通常使用32-bit的sequence number或seqno表示。这样一个用低位数据来表示高位数据的方法自然而然地又了了以下几个挑战：

• 当32-bit空间用完(到达2^32-1)后，需要对其进行重置，从0开始重新计数，即(mod 2^32)；
• 为了避免以前连接中旧数据包造成混淆，在TPC连接建立阶段需要随机确定一个32-bit的初始值即ISN(Initial Sequence Number)，尽量保证序列号不可被预判或与之前重复；
• 为了保证开始信号、字节数据和数据结束信号可靠接收，在TCP中，SYN(beginning of stream)和FIN(end of stream)分别占用两个序列号，SYN占用第一个序列号也就是ISN，数据字节后续的序列号如ISN+1 (mod 2^32)、ISN+2 (mod 2^32)等等，最后FIN占用流后的一个序列号。

在TCP中，索引有以下三种：

An Example of Bitstream "cat".

Three Different Types of Indexing Involved in TCP.

可以看到，absloute seqno与stream index之间非常好转换，而seqno与absolute seqno由于空间大小不一样，转换需要进行额外的操作。这一部分需要做的就是，根据头文件wrapping integers.hh完成wrapping integers.cc中的两个转换函数。

Convert absolute seqno → seqno.

对于64-bit的absolute seqno，先对它取模，确保在32-bit范围内，之后加上ISN再取模，得到32-bit的seqno。

WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
//    DUMMY_CODE(n, isn);
        uint64_t mod = 1LL << 32;
        WrappingInt32 seqno ((n % mod + isn.raw_value()) % mod);
        return seqno;
}

Convert seqno → absolute seqno.

对于32-bit的seqno，需要找到距离checkpoint最近的absolute seqno，

• 先确定seqno与ISN之间的偏移量；
• 在数轴上，位于checkpoint左侧的为absolute_seqno_left，右侧的为absolute_seqno_right，均初始化为absolute_seqno_wrap；
• 不断以2^32为单位增长absolute_seqno_wrap，直到absolute_seqno_wrap > checkpoint，此时获取到了absolute_seqno_left与absolute_seqno_right，选取他们之中距离checkpoint最近的即为absolute_seqno。

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    //    DUMMY_CODE(n, isn, checkpoint);
    uint64_t mod = 1UL << 32;
    uint64_t absolute_seqno_wrap = n.raw_value() - isn.raw_value();
    uint64_t absolute_seqno_right = absolute_seqno_wrap;
    uint64_t absolute_seqno_left = absolute_seqno_wrap;
    while (absolute_seqno_wrap < checkpoint) {
        absolute_seqno_wrap += mod;
        if (absolute_seqno_wrap < checkpoint)
            absolute_seqno_left = absolute_seqno_wrap;
        if (absolute_seqno_wrap > checkpoint)
            absolute_seqno_right = absolute_seqno_wrap;
    }
    return absolute_seqno_right - checkpoint > checkpoint - absolute_seqno_left ? absolute_seqno_left
                                                                                : absolute_seqno_right;
}

修改与改进

在测试test4的时候遇到了问题：

1/1 Test #4: t_wrapping_ints_roundtrip ........***Failed    0.16 sec
Expected unwrap(wrap()) to recover same value, and it didn't!
  unwrap(wrap(value, isn), isn, checkpoint) did not equal value
  where value = 1383509345922390960, isn = 549282053, and checkpoint = 1383509345922390960
  (Difference between value and checkpoint is 0.)

是因为没有考虑absolute_seqno_wrap == checkpoint的情况，于是增加了特判。除此之外为了防止absolute_seqno_wrap溢出增加了新的判定在while() {}中：

while (absolute_seqno_wrap <= checkpoint) {
        if (UINT64_MAX - absolute_seqno_wrap < mod || absolute_seqno_wrap == checkpoint)
            return absolute_seqno_wrap;
        else
            absolute_seqno_wrap += mod;
        if (absolute_seqno_wrap < checkpoint)
            absolute_seqno_left = absolute_seqno_wrap;
        if (absolute_seqno_wrap > checkpoint)
            absolute_seqno_right = absolute_seqno_wrap;
    }

然后又跑了一下，在test4怎么也不出结果，以为有死循环，但是查了半天逻辑并无错误，看了一眼测试，，，跑1000000轮，原来只是单纯的慢罢了。

那么如何改进，分析一下：

前面的方案是通过循环累加确定checkpoint附近的absolute seqno，这个流程可以通过取模+除法操作替代，这就意味着计算未接近checkpoint的32-bit区间是毫无意义的，我们只需要考虑checkpoint所在的当前区间以及其前后区间即可。

当前以及其前后32bit区间.

那么这样的话就有以下几种情况：

• 在checkpoint与当前区间的absolute seqno重合时，checkpoint的位置就是absolute seqno；
• 当checkpoint的位置在当前区间中的absolute seqno的右侧时，会存在两个情况：
  • checkpoint在最后一个区间中，只有当前区间才有absolute seqno；
  • checkpoint不在最后一个区间中，只有在当前区间和其后区间可能存在absolute seqno；
• 当checkpoint的位置在当前区间中的absolute seqno的左侧时，也会存在两个情况：
  • checkpoint在第一个区间中，只有当前区间才有absolute seqno；
  • checkpoint不在第一个区间中，只有在当前区间和前一个区间可能存在absolute seqno。

最后通过了测试的代码如下。

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    //    DUMMY_CODE(n, isn, checkpoint);
    const uint64_t mod = 1UL << 32;
    const uint32_t checkpoint_32 = checkpoint % mod;
    const uint32_t absolute_n = n.raw_value() - isn.raw_value();
    if (UINT64_MAX - checkpoint < mod || absolute_n == checkpoint_32)
        return (checkpoint / mod) * mod + absolute_n;
    if (checkpoint_32 > absolute_n)
        return checkpoint_32 - absolute_n > mod - checkpoint_32 + absolute_n
                   ? ((checkpoint / mod) + 1) * mod + absolute_n
                   : (checkpoint / mod) * mod + absolute_n;
    else {
        if (checkpoint < mod)
            return absolute_n;
        return absolute_n - checkpoint_32 > mod + checkpoint_32 - absolute_n
                   ? ((checkpoint / mod) - 1) * mod + absolute_n
                   : (checkpoint / mod) * mod + absolute_n;
    }
}

B. Implementing the TCP receiver

TCPReceiver在运行过程中会收到这样格式的TCPSegment：

TCPSegment.

现在，需要根据tcp_receiver.hh来实现一下TCPReceiver：

首先需要增加三个变量：

• _isn：储存存入第一次成功建立连接时的seqno；
• _syn ：判断连接是否建立；
• _fin：判断连接是否终止。

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

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

    WrappingInt32 _isn{0};
    bool _syn = false;
    bool _fin = false;
  	
  	/*codes*/
}

segment_received的实现思路是：

• 首先判断seg.header().syn是否为true且当前链接未建立时，设置_isn为seqno并建立连接，否则当链接不存在时，直接返回。
• 之后向reassembler中推送收到的TCPSegment中的数据；
• 最后当且仅当seg.header().fin为true时，将_fin记录为终止状态。

ackno的实现思路是：

• 首先判断链接是否建立，如果为建立则直接返回nullopt；
• 如果建立了则返回下一个需要进行整合的seqno，从absolute seqno的角度来看即为 _reassembler.stream_out().bytes_written() + 1，同时需要注意syn与fin也会分别占用了一个seqno，

void TCPReceiver::segment_received(const TCPSegment &seg) {
    //    DUMMY_CODE(seg);
    if (seg.header().syn && !_syn) {
        _isn = seg.header().seqno;
        _syn = seg.header().syn;
    } else if (!_syn) return;
    _reassembler.push_substring(seg.payload().copy(),
                                unwrap(seg.header().seqno, _isn, _reassembler.stream_out().bytes_written() + 1) - 1 +
                                    seg.header().syn,
                                seg.header().fin);
    if (seg.header().fin) _fin = seg.header().fin;
}

optional<WrappingInt32> TCPReceiver::ackno() const {
    return _syn ? optional<WrappingInt32>{wrap(_reassembler.stream_out().bytes_written() + _syn + (_fin && _reassembler.empty()), _isn)}
                : nullopt;
}

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

在写segment_received的时候，在recv_specal这个测试中卡了好久，这里面设计了很多syn、fin与数据结合的Segment，需要特别注意下。

本文链接: https://zone.ivanz.cc/p/b9f66227.html