CS144 Lab2: the TCP receiver

发表于 分类于 ， 本文字数： 1k 阅读时长 ≈ 4 分钟
TCP 接收器（Receiver）的实现。

实验概述

figure.png

当前实验需要实现一个 TCP 接收器，用于把接收到的 TCP segments 送入 Lab1 中实现的 StreamReassembler，之后再写入到 Lab0 中实现的 ByteStream。同时，接收器还要给发送方返回确认号（acknowledgment number, ackno）和窗口大小（window size）。以上两者描述了接收方的接收窗口并用于流量控制。

Translating between 64-bit indexes and 32-bit seqnos

首先需要实现的是 64 位与 32 位整型之间的相互转换。

实验说明中的例子如图：

Lab2-fig1.png

转换过程的具体实现如下：

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// sponge/libsponge/wrapping_integers.cc

// ...

//! 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 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) {
    // n 可以在 checkpoint 的左边，也可以在 checkpoint 的右边，
    // 留意无符号数相减求偏移量，例如：
    // n 为 1，checkpoint 为 7，1 - 7 等于 1<<32 + 1 - 7
    // 所以如果新位置距离 checkpoint 的偏移量大于 1<<32 的一半，即 1<<31
    // 那么离 checkpoint 最近的位置实际上是在 checkpoint 的左侧

    uint32_t offset = n - wrap(checkpoint, isn);
    uint64_t pos = checkpoint + offset;
    if (offset > (1u << 31) && pos >= (1ul << 32)) {
        pos -= (1ul << 32);
    }
    return pos;
}

几点说明：

  • 头文件 wrapping_integers.hh 中已经实现了一些运算符重载函数来方便我们使用。
  • unwrap() 函数需要计算 n 所对应的最接近 checkpoint 的 absolute seqno，可以通过计算 偏移量（offset） 来实现。
  • 形参 checkpoint 是 absolute seqno，代表最后一个重组字节的序号（the index of the last reassembled byte）。
  • unwrap() 中 n 所代表的位置既可以在 checkpoint 的左侧，也可以在 checkpoint 右侧，同时又是无符号数相减，因此要仔细考虑以上两种情况（具体可以参考代码中的注释）。

Implementing the TCP receiver

接下来就是要实现 TCP 接收器。我们需要实现三个函数，同时在实现中需要考虑以下几种状态的变化。

evolution.png

如上图所示，实验说明中给出了 TCP 接收器在连接过程中的演变。除了 ERROR 状态外，其他三种状态为：

  • LISTEN：等待 SYN 到达，在此之前到达的数据都会被丢弃。
  • SYN_RECV：正常接受数据。
  • FIN_RECV：获取 FIN，结束输入。

头文件中声明需要的私有变量：

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// sponge/libsponge/tcp_receiver.hh

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

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

    bool _syn_flag;
    WrappingInt32 _isn;

  public:
    //! \brief Construct a TCP receiver
    //!
    //! \param capacity the maximum number of bytes that the receiver will
    //!                 store in its buffers at any give time.
    TCPReceiver(const size_t capacity) : _reassembler(capacity), _capacity(capacity), _syn_flag(false), _isn(0) {}

    // ...
};

具体的实现如下：

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// sponge/libsponge/tcp_receiver.cc

#include "tcp_receiver.hh"

// Dummy implementation of a TCP receiver

// For Lab 2, please replace with a real implementation that passes the
// automated checks run by `make check_lab2`.

using namespace std;

void TCPReceiver::segment_received(const TCPSegment &seg) {
    const TCPHeader &header = seg.header();

    if (!_syn_flag) {
        if (!header.syn) {
            return;  // 直接丢弃
        }
        _syn_flag = header.syn;
        _isn = header.seqno;
    }
    // SYN_RECV 状态
    uint64_t checkpoint = header.syn ? 0 : stream_out().bytes_written() - 1;  // the index of last reassembled byte
    uint64_t abs_seqno = unwrap(header.seqno, _isn, checkpoint);
    uint64_t stream_idx = header.syn ? 0 : abs_seqno - 1;  // abs seqno 换算到 stream index，留意 SYN 为 true 的情况
    _reassembler.push_substring(seg.payload().copy(), stream_idx, header.fin);
}

optional<WrappingInt32> TCPReceiver::ackno() const {
    // 非 LISTEN 状态
    if (!_syn_flag) {
        return std::nullopt;
    }
    // LISTEN 状态
    uint64_t abs_ackno = stream_out().bytes_written() + 1;  // 加上 SYN flag 的长度
    // FIN_RECV 状态
    if (stream_out().input_ended()) {
        abs_ackno += 1;  // 加上 FIN flag 的长度
    }
    return wrap(abs_ackno, _isn);
}

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

一些说明：

  • segment_received() 中需要留意 SYN 标志为 true 的起始情况。
  • 如之前 unwrap() 中说明的那样，segment_received() 中的 checkpoint 为 the index of last reassembled byte。
  • window_size() 其实就是求 StreamReassembler 能接受的空间大小上限（Lab1 中 capacity 图中红色部分的极限大小）。