CS144-Lab2 计算机网络：TCP Receiver的实现

TCP Receiver

Index和Seqno的转换

为了节省在TCP Header当中的空间，在StreamReassembler里面写的index虽然是一个uint64_t的类型，但是在实际的Header中是使用一个uint32_t的seqno来进行标记位置的。对于uint32_t的seqno和uint64_t的index的相互转换则是通过以4GiB (2^32 bytes)为一个长度进行取模来实现。

同时为了提高TCP本身的安全性，并且确保每次获得的segments数据段都是来自于本次连接的，因此提出了ISN(Initial Sequence Number)的概念，即本次链接是从序号为isn开始作为seqno进行通信，大于isn的seqno所代表的index是本次链接所需要的数据段，早于isn的seqno则是来自于上一次连接的老数据段，并不需要处理。

如果想要将uint32_t的seqno转为一个uint64_t则需要一个checkpoint作为定位，防止seqno被定位到错误的位置上。这个checkpoint在实现中就是最后一个重新组装后的字符位置

按lab2的原文：In your TCP implementation, you’ll use the index of the last reassembled byte as the checkpoint.

通过寻找距离checkpoint最近的seqno就可以定位到本来需要插入的seqno位置了

代码思路

对于将uint32_t转为uint64_t的代码实现很简单，只需要将uint64_t的index加上isn的值之后对2^32进行取模就行了，具体代码实现如下

WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    uint64_t result = (n + isn.raw_value()) % (static_cast<uint64_t>(UINT32_MAX) + 1);
    return WrappingInt32(static_cast<uint32_t>(result));
}

而对于将wrap后的seqno转回index，我直接通过类似分类讨论的枚举找到了四个临界点，只需要判断checkpoint相对于临界点的位置就可以得到答案。代码如下

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    const uint64_t L = (1ul << 32);
    const uint64_t a = (checkpoint / L) * L - isn.raw_value() + n.raw_value();
    if (checkpoint > a + (L * 3) / 2) {
        return a + 2 * L;
    } else if (checkpoint > a + L / 2) {
        return a + L;
    } else if (checkpoint < L) {
        return n.raw_value() < isn.raw_value() ? a + L : a;
    } else {
        return checkpoint < a - L / 2 ? a - L : a;
    }
}

详细思路点这里(硬分类，感觉好蠢，但是有效.jpg)

通解推导

checkpoint > L

由以下公式

$\left ( index+isn \right )\mod{ L } = seqno$

通过推导可以得到

$index = seqno + k * L - isn$

因此如果需要得到离checkpoint最近的index就只需要找到合适的k即可，在这里不妨设

$m = checkpoint / L$

取m作为一个附近值，通过画图可以知道，在一般情况下，答案一定在checkpoint附近的三个区间内

seqno - isn > 0

在这种情况下，checkpoint的前中后三个区间都存在，只要列举并讨论范围就很简单了

当seqno - isn为正数的时候，index可能的一个取值会落在第②个区间上，有

$index'' = m * L + seqno - isn$

此时第①区间和第③区间上的index可以分别表示为

$index' = index'' - L \\\\ index''' = index'' + L$

对index'、index''和index'''的中间值进行判断，很容易得到以下规律

$\begin{array}{l} a = m*L+seqno-isn \\\\ L = UINT32\_MAX+1 \\\\ \left \{\begin{matrix} checkpoint < a - L/2 & \text{index=a-L}\\\\ a-L/2\leq checkpoint< a+L/2 & \text{index=a}\\\\ a+L/2\leq checkpoint & \text{index=a+L} \end{matrix}\right. \end{array}$

注：此时checkpoint一定小于 a+L，因为a+L属于第③区间，而checkpoint在第②区间内

seqno - isn < 0

此时因为是从m*L的位置向前移动，所以相比于上面，三个可能是答案的index的分布则改为了

$index' = m * L + seqno - isn\\ index'' = index' + L\\ index''' = index' + 2 * L$

所以很容易得到以下结果

$\begin{array}{l} a = m*L+seqno-isn\\ L = UINT32\_MAX+1\\ \left \{\begin{matrix} checkpoint < a + L/2 & \text{index=a}\\ a+L/2\leq checkpoint< a+(3*L)/2 & \text{index=a + L}\\ a+(3*L)/2\leq checkpoint & \text{index=a+2*L} \end{matrix}\right. \end{array}$

将以上两种规律整合，我们很容易可以得到以下通解

$\begin{array}{l} a = m*L+seqno-isn\\ L = UINT32\_MAX+1\\ \left \{\begin{matrix} checkpoint < a - L/2 & \text{index=a-L}\\ a-L/2\leq checkpoint< a+L/2 & \text{index=a}\\ a+L/2\leq checkpoint< a+(3*L)/2 & \text{index=a + L}\\ a+(3*L)/2\leq checkpoint & \text{index=a+2*L} \end{matrix}\right. \end{array}$

特殊情况

checkpoint < L

在checkpoint < L的时候，通解中对于a - L的一部分(即checkpoint < a + L)就不适用了，不过分析起来也很简单，由于有

$\left ( index+isn \right )\mod{ L } = seqno$

所以当seqno小于isn的时候，答案一定在下一个区间，因此答案即L - isn + seqno，当seqno大于isn且checkpoint < a + L，所以答案一定为a

所以就可以得到上述代码了。

TCP 段接收处理

这部分代码逻辑完成的是tcp握手中对于tcp段的接受处理。

我自己增加的私有成员和用途大致为：

• _is_syn: 判断链接是否建立
• _isn: 存入第一次建立连接时接受的seqno来初始化
• _is_fin: 用于判断结束输入的报文是否传入

对于ackno和checkpoint的实现机制是：

• ackno: 本质上就是返回已经整合好的数据量，也就是bytes_stream的bytes_written()，同时建立连接后一定存在syn所以可以直接加一，之后只需要判断fin是否到达并且整合完毕，然后再次加一即可。
• checkpoint: 和ackno差别不大，只需要直接返回已经写入完成的字符个数即可

知道了上述几个逻辑以后就只需要通过调整简单的逻辑flag加上lab1里面的push_substring来对payload()进行整合就可以通过了。

void TCPReceiver::segment_received(const TCPSegment &seg) {
    // 等待并处理第一个syn链接
    if ((_is_syn == 0) && seg.header().syn) {
        _is_syn = 1;
        _isn = seg.header().seqno;
    } else if (_is_syn == 0) {
        return;
    }

    // checkpoint的位置就是已经写入完成的字符的数量
    // In your TCP implementation, you’ll use the index of the last reassembled byte as the checkpoint.
    const uint64_t checkpoint = _reassembler.stream_out().bytes_written() + 1;

    // 将内容写入reassembler，其中之所以要有(- 1 + seg.header().syn)这个部分，是因为当握手成功以后
    // seqno是从1开始的，而没有握手的时候stream_index应该将包含syn的报文写在index为0的位置上
    uint64_t stream_index = unwrap(seg.header().seqno, _isn, checkpoint) - 1 + seg.header().syn;
    _reassembler.push_substring(seg.payload().copy(), stream_index, seg.header().fin);

    // 标志结尾的TCP段是否送达
    if (seg.header().fin) {
        _is_fin = 1;
    }
}

optional<WrappingInt32> TCPReceiver::ackno() const {
    // 返回已经消耗的index长度，也就是ackno确认了的长度
    WrappingInt32 result = _isn + _is_syn + _reassembler.stream_out().bytes_written();
    if ((_is_fin != 0) && _reassembler.unassembled_bytes() == 0) {
        // 判断是否包含结束的报文
        result = result + _is_fin;
    }
    // 如果建立了链接才返回ackno，在建立报文之前是没有ackno的，因为没有对方的信息可以让自己确认
    return _is_syn ? optional<WrappingInt32>(result) : nullopt;
}

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

这里有一个让我感觉很疑惑的点就是在单元测试中存在两种测试样例，这里做个记录，后面如果知道了原因就来解决一下

• 存在同时携带SYN和FIN报文，按照正常的TCP握手感觉这是不合理的
• 在接受SYN的同时会接受一部分的Data进行处理，按正常的TCP也是不会这么做的