[网络协议]CS144-Lab2: the TCP receiver

更好的阅读体验

实验架构

除了写入传入流之外，TCPReceiver 还负责通知 sender 两件事：

1. “First unassembled” 字节的索引，称为“acknowledgment”或 “ackno”。这是接收方需要来自发送方的第一个字节。
2. “first unassembled ” 索引和“first unacceptable ”索引之间的距离。这称为“window size”。

总的来说，ackno 和 window size 述了 TCPreceiver 的窗口：TCPsender 被允许发送一系列索引。使用该窗口，TCPreceiver 可以做到流量控制，使发送方限制它发送的数量，直到接收方准备好更多的数据。有时，我们将 ackno 称为窗口的“左边”( TCPRecsigner 的最小索引)，而 ackno + window size 则称为“右边缘”(略大于 TCPReceiver 的最大索引)。

在编写 Stream Reassembler 和 Byte Stream 时，您已经完成了实现 TCP Receiver 所涉及的大部分算法工作；本实验是将这些通用类连接到 TCP 的细节。最困难的部分将涉及考虑 TCP 将如何表示每个字节在流中的位置——称为“sequence number”。

我们将要实现的 TCPReceiver 需要完成的功能：

• 接收 TCP segment
• 重新组装 ByteStream
• 发送 ackno 和 window size 回 TCP sender ，以进行流量控制和数据确认

环境配置

当前我们的实验代码位于 master 分支，而在完成 Lab 之前需要合并一些依赖代码，因此执行以下命令：

git merge origin/lab2-startercode

之后重新 make 编译即可。

The TCP Receiver

在 Lab2，我们将实现一个 TCPReceiver，用以接收传入的 TCP segment 并将其转换成用户可读的数据流。

TCPReceiver 除了将读入的数据写入至 ByteStream 中以外，它还需要告诉发送者两个属性：

• 第一个未组装的字节索引，称为确认号ackno，它是接收者需要的第一个字节的索引。
• 第一个未组装的字节索引和第一个不可接受的字节索引之间的距离，称为 窗口长度window size。

ackno 和 window size 共同描述了接收者当前的接收窗口。接收窗口是 发送者允许发送数据的一个范围，通常 TCP 接收方使用接收窗口来进行流量控制，限制发送方发送数据。

总的来说，我们将要实现的 TCPReceiver 需要做以下几件事情：

• 接收TCP segment
• 重新组装字节流（包括EOF）
• 确定应该发回给发送者的信号，以进行数据确认和流量控制

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

作为热身，我们需要实现TCP表示索引的方式。上周您创建了一个StreamReassembler，它重组子字符串，其中每个字节都有一个64位流索引，流中的第一个字节总是索引为0。64位索引足够大，我们可以将其视为永不溢出。然而，在TCP报头中，空间是宝贵的，流中的每个字节的索引不是用64位的索引表示的，而是用32位的“序列号”或“seqno”表示的。这增加了三个复杂性:

1. 您的实现需要为32位整数进行规划：TCP中的流可以是任意长的——对于可以通过TCP发送的字节流的长度没有限制。但是232字节只有4GiB，并不是很大。一旦一个32位的序列号计数到232?1，流中的下一个字节的序列号将为0。
2. TCP序列号从一个随机值开始：为了提高安全性，并避免被属于同一端点之间早期连接的旧段所混淆，TCP试图确保序列号不会被猜测，并且不太可能重复。所以流的序列号不是从0开始的。流中的第一个序列号是一个随机的32位数字，称为初始序列号(Initial sequence number, ISN)。这是表示SYN(流的开始)的序列号。其余的序列号在此之后正常运行:数据的第一个字节将有ISN+1 (mod 232)的序列号，第二个字节将有ISN+2 (mod 232)，等等。
3. 每个逻辑开始和结束占用一个序列号：除了确保接收到所有字节的数据外，TCP还确保可靠地接收流的开始和结束。因此，在TCP中SYN (start -ofstream)和FIN (end- stream)控制标志被分配了序列号。每一个都占用一个序列号。(SYN标志占用的序列号是ISN。)流中的每个数据字节也占用一个序列号。请记住，SYN和FIN不是流本身的一部分，也不是“字节”——它们表示字节流本身的开始和结束。

第一行是32位的seqno，可以想象成在圆环上走路（正反走均可），二三行是64位的absolute seqno，四五行是64位的stream index。

absolute seqno转seqno：$isn+n\%2^{32}$ ，$n$ 直接强制类型转换即可截取低32位。
seqno 转 absolute seqno：有点麻烦，可能对应多个结果，因此选择距离checkpoint最近的那个结果，checkpoint取前一次所收段的absolute seqno。原因在于两个前后到达的段absolute seqno 的差值几乎不可能超过 $2^{3}2$。有个 corner case是当checkpoint比较小时计算得到的 absolute seqno 可能小于0，需要加上232232即1UL<<32。

wrapping_integers.hh:

#ifndef SPONGE_LIBSPONGE_WRAPPING_INTEGERS_HH
#define SPONGE_LIBSPONGE_WRAPPING_INTEGERS_HH

#include <cstdint>
#include <ostream>

//! \brief A 32-bit integer, expressed relative to an arbitrary initial sequence number (ISN)
//! \note This is used to express TCP sequence numbers (seqno) and acknowledgment numbers (ackno)
class WrappingInt32 {
  private:
    uint32_t _raw_value;  //!< The raw 32-bit stored integer

  public:
    //! Construct from a raw 32-bit unsigned integer
    explicit WrappingInt32(uint32_t raw_value) : _raw_value(raw_value) {}

    uint32_t raw_value() const { return _raw_value; }  //!< Access raw stored value
};

//! Transform a 64-bit absolute sequence number (zero-indexed) into a 32-bit relative sequence number
//! \param n the absolute sequence number
//! \param isn the initial sequence number
//! \returns the relative sequence number
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn);

//! Transform a 32-bit relative sequence number into a 64-bit absolute sequence number (zero-indexed)
//! \param n The relative sequence number
//! \param isn The initial sequence number
//! \param checkpoint A recent absolute sequence number
//! \returns the absolute 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);

//! \name Helper functions
//!@{

//! \brief The offset of `a` relative to `b`
//! \param b the starting point
//! \param a the ending point
//! \returns the number of increments needed to get from `b` to `a`,
//! negative if the number of decrements needed is less than or equal to
//! the number of increments
inline int32_t operator-(WrappingInt32 a, WrappingInt32 b) { return a.raw_value() - b.raw_value(); }

//! \brief Whether the two integers are equal.
inline bool operator==(WrappingInt32 a, WrappingInt32 b) { return a.raw_value() == b.raw_value(); }

//! \brief Whether the two integers are not equal.
inline bool operator!=(WrappingInt32 a, WrappingInt32 b) { return !(a == b); }

//! \brief Serializes the wrapping integer, `a`.
inline std::ostream &operator<<(std::ostream &os, WrappingInt32 a) { return os << a.raw_value(); }

//! \brief The point `b` steps past `a`.
inline WrappingInt32 operator+(WrappingInt32 a, uint32_t b) { return WrappingInt32{a.raw_value() + b}; }

//! \brief The point `b` steps before `a`.
inline WrappingInt32 operator-(WrappingInt32 a, uint32_t b) { return a + -b; }
//!@}

#endif  // SPONGE_LIBSPONGE_WRAPPING_INTEGERS_HH

wrapping_integers.cc:

#include "wrapping_integers.hh"

// Dummy implementation of a 32-bit wrapping integer

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

template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {}

using namespace std;

//! 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 + 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) {
    WrappingInt32 w_cp = wrap(checkpoint, isn);

    // find out the min step between n and checkpoint
    int32_t min_step = n - w_cp;

    // The result of unwrap
    int64_t res = checkpoint + min_step;

    // If overflow, add 2 ^ 32
    if(res < 0) {
        res += (1ul << 32);
    }

    return uint64_t(res);
}

2. Implementing the TCP receiver

1. 要求

在本实验室的其余部分，您将实现TCPReceiver。它将(1)从它的peer接收段(2)使用你的StreamReassembler重新组装ByteStream(3)计算确认号码(ackno)和窗口大小。确认码和窗口大小最终会在传出的段中传输回对等体。

首先，请回顾TCP段的格式。这是两个端点互相发送的消息;它是低级数据报的有效负载。未显示为灰色的字段表示本实验室感兴趣的信息：序列号、有效负载以及SYN和FIN标志。这些字段由发送方写入，接收方读取并处理。

需要实现一些类成员函数

• segment_received(): 该函数将会在每次获取到 TCP 报文时被调用。该函数需要完成：

  • 如果接收到了 SYN 包，则设置 ISN 编号。

    注意：SYN 和 FIN 包仍然可以携带用户数据并一同传输。同时，同一个数据包下既可以设置 SYN 标志也可以设置 FIN 标志。

  • 将获取到的数据传入流重组器，并在接收到 FIN 包时终止数据传输。

• ackno()：返回接收方尚未获取到的第一个字节的字节索引。如果 ISN 暂未被设置，则返回空。

• window_size()：返回接收窗口的大小，即第一个未组装的字节索引和第一个不可接受的字节索引之间的长度。

2. 实现

在stream_reassembler中添加如下接口以获取 ACK号：

stream_reassembler.hh:

class StreamReassembler {
    ...
    //! The acknowledge index of the stream, i.e., 
    //! the index of the next interested substring
    size_t ack_index() const;
    ...
};

stream_reassembler.cc:

size_t StreamReassembler::ack_index() const { return unass_base; }

tcp_receiver.hh：

#ifndef SPONGE_LIBSPONGE_TCP_RECEIVER_HH
#define SPONGE_LIBSPONGE_TCP_RECEIVER_HH

#include "byte_stream.hh"
#include "stream_reassembler.hh"
#include "tcp_segment.hh"
#include "wrapping_integers.hh"

#include <optional>

//! \brief The "receiver" part of a TCP implementation.

//! Receives and reassembles segments into a ByteStream, and computes
//! the acknowledgment number and window size to advertise back to the
//! remote TCPSender.
class TCPReceiver {
    //! Our data structure for re-assembling bytes.
    StreamReassembler _reassembler;

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

    //! Flag to indicate whether the first SYN message has received
    bool _synRecv;

    //! Flag to indicate whether FIN mesaage has received
    bool _finRecv;

    //! Inital Squence Number
    WrappingInt32 _isn;

    //! \brief The operation after receive the first SYN flag
    void firstSYN(const TCPHeader& head, std::string& data, bool & _eof);

    //! \brief push the data into stream reassembler
    void push_data(const TCPHeader& head, std::string& data, bool& _eof);

  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)
      , _synRecv(false)
      , _finRecv(false)
      , _isn(0) {}

    //! \name Accessors to provide feedback to the remote TCPSender
    //!@{

    //! \brief The ackno that should be sent to the peer
    //! \returns empty if no SYN has been received
    //!
    //! This is the beginning of the receiver's window, or in other words, the sequence number
    //! of the first byte in the stream that the receiver hasn't received.
    std::optional<WrappingInt32> ackno() const;

    //! \brief The window size that should be sent to the peer
    //!
    //! Operationally: the capacity minus the number of bytes that the
    //! TCPReceiver is holding in its byte stream (those that have been
    //! reassembled, but not consumed).
    //!
    //! Formally: the difference between (a) the sequence number of
    //! the first byte that falls after the window (and will not be
    //! accepted by the receiver) and (b) the sequence number of the
    //! beginning of the window (the ackno).
    size_t window_size() const;
    //!@}

    //! \brief number of bytes stored but not yet reassembled
    size_t unassembled_bytes() const { return _reassembler.unassembled_bytes(); }

    //! \brief handle an inbound segment
    void segment_received(const TCPSegment &seg);

    //! \name "Output" interface for the reader
    //!@{
    ByteStream &stream_out() { return _reassembler.stream_out(); }
    const ByteStream &stream_out() const { return _reassembler.stream_out(); }
    //!@}
};

#endif  // SPONGE_LIBSPONGE_TCP_RECEIVER_HH

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`.

template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {}

using namespace std;

void TCPReceiver::firstSYN(const TCPHeader& head, string& data, bool& _eof) {
    _synRecv = true;
    _isn = head.seqno;
    
    // if the syn and fin in the same segment
    if (head.fin) {
        _finRecv = _eof = true;
    }

    _reassembler.push_substring(data, 0, _eof);
}

void TCPReceiver::push_data(const TCPHeader& head, string& data, bool& _eof) {
    uint64_t _ack = _reassembler.ack_index();
    uint64_t _abs_seq = unwrap(head.seqno, _isn, _ack);
    uint64_t _idx = _abs_seq - _synRecv;

    _reassembler.push_substring(data, _idx, _eof);
}

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

    // Not the target
    if (!head.syn && !_synRecv) {
        return;
    }

    //! Extract data from the payload
    string data = seg.payload().copy();

    //! Indicate that this seg is the last 
    bool _eof = false;

    // First SYN received
    if (head.syn && !_synRecv) {
        firstSYN(head, data, _eof);
        return;
    }

    // FIN received
    if (_synRecv && head.fin) {
        _finRecv = _eof = true;
    }

    push_data(head, data, _eof);
}

optional<WrappingInt32> TCPReceiver::ackno() const {
    //  The ISN hasn’t been set yet, return an empty optional.
    if (!_synRecv) {
        return nullopt;
    }
    
    uint64_t _ack = _reassembler.ack_index();

    //! FIN flags occupy one sequence number
    uint64_t _eof = _reassembler.empty() && _finRecv;
    uint64_t _res = _ack + _eof + 1;

    return wrap(_res, _isn);
}

size_t TCPReceiver::window_size() const {
    //！ The maximum amount that can currently be read from the stream
    size_t _rest = _reassembler.stream_out().buffer_size();
    
    // The window size is the capacity sub the _rest
    return _capacity - _rest; 
}

3.编译测试

$ make -j8 && make check_lab2
[  5%] Built target spongechecks
[ 24%] Built target sponge
[ 37%] Built target byte_stream_capacity
[ 37%] Built target recv_connect
[ 40%] Built target recv_close
[ 40%] Built target wrapping_integers_wrap
[ 40%] Built target wrapping_integers_unwrap
[ 37%] Built target recv_transmit
[ 43%] Built target wrapping_integers_cmp
[ 45%] Built target webget
[ 48%] Built target recv_special
[ 60%] Built target byte_stream_many_writes
[ 60%] Built target byte_stream_one_write
[ 62%] Built target fsm_stream_reassembler_cap
[ 60%] Built target fsm_stream_reassembler_single
[ 62%] Built target recv_window
[ 64%] Built target tcp_parser
[ 67%] Built target wrapping_integers_roundtrip
[ 81%] Built target byte_stream_construction
[ 81%] Built target recv_reorder
[ 81%] Built target fsm_stream_reassembler_seq
[ 85%] Built target fsm_stream_reassembler_holes
[ 85%] Built target fsm_stream_reassembler_dup
[ 86%] Built target fsm_stream_reassembler_overlapping
[ 86%] Built target fsm_stream_reassembler_many
[ 89%] Built target fsm_stream_reassembler_win
[ 94%] Built target parser_dt
[ 94%] Built target socket_dt
[ 97%] Built target byte_stream_two_writes
[100%] Built target address_dt
[100%] Testing the TCP receiver...
Test project /home/misaka/Desktop/sponge/build
      Start  1: t_wrapping_ints_cmp
 1/26 Test  #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
      Start  2: t_wrapping_ints_unwrap
 2/26 Test  #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
      Start  3: t_wrapping_ints_wrap
 3/26 Test  #3: t_wrapping_ints_wrap .............   Passed    0.00 sec
      Start  4: t_wrapping_ints_roundtrip
 4/26 Test  #4: t_wrapping_ints_roundtrip ........   Passed    0.12 sec
      Start  5: t_recv_connect
 5/26 Test  #5: t_recv_connect ...................   Passed    0.00 sec
      Start  6: t_recv_transmit
 6/26 Test  #6: t_recv_transmit ..................   Passed    0.03 sec
      Start  7: t_recv_window
 7/26 Test  #7: t_recv_window ....................   Passed    0.00 sec
      Start  8: t_recv_reorder
 8/26 Test  #8: t_recv_reorder ...................   Passed    0.00 sec
      Start  9: t_recv_close
 9/26 Test  #9: t_recv_close .....................   Passed    0.00 sec
      Start 10: t_recv_special
10/26 Test #10: t_recv_special ...................   Passed    0.00 sec
      Start 18: t_strm_reassem_single
11/26 Test #18: t_strm_reassem_single ............   Passed    0.00 sec
      Start 19: t_strm_reassem_seq
12/26 Test #19: t_strm_reassem_seq ...............   Passed    0.00 sec
      Start 20: t_strm_reassem_dup
13/26 Test #20: t_strm_reassem_dup ...............   Passed    0.00 sec
      Start 21: t_strm_reassem_holes
14/26 Test #21: t_strm_reassem_holes .............   Passed    0.00 sec
      Start 22: t_strm_reassem_many
15/26 Test #22: t_strm_reassem_many ..............   Passed    0.08 sec
      Start 23: t_strm_reassem_overlapping
16/26 Test #23: t_strm_reassem_overlapping .......   Passed    0.00 sec
      Start 24: t_strm_reassem_win
17/26 Test #24: t_strm_reassem_win ...............   Passed    0.09 sec
      Start 25: t_strm_reassem_cap
18/26 Test #25: t_strm_reassem_cap ...............   Passed    0.06 sec
      Start 26: t_byte_stream_construction
19/26 Test #26: t_byte_stream_construction .......   Passed    0.00 sec
      Start 27: t_byte_stream_one_write
20/26 Test #27: t_byte_stream_one_write ..........   Passed    0.00 sec
      Start 28: t_byte_stream_two_writes
21/26 Test #28: t_byte_stream_two_writes .........   Passed    0.00 sec
      Start 29: t_byte_stream_capacity
22/26 Test #29: t_byte_stream_capacity ...........   Passed    0.31 sec
      Start 30: t_byte_stream_many_writes
23/26 Test #30: t_byte_stream_many_writes ........   Passed    0.00 sec
      Start 53: t_address_dt
24/26 Test #53: t_address_dt .....................   Passed    0.00 sec
      Start 54: t_parser_dt
25/26 Test #54: t_parser_dt ......................   Passed    0.00 sec
      Start 55: t_socket_dt
26/26 Test #55: t_socket_dt ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 26

Total Test time (real) =   0.74 sec
[100%] Built target check_lab2

Evolution of the TCPReceiver over the life of the connection

在一个TCP连接的过程中，你的TCPReceiver将通过一系列的状态演进:从等待SYN(空的确认)，到一个正在进行的流，到一个已经完成的流，这意味着输入已经在ByteStream上结束。测试套件将检查你的TCPReceiver是否正确处理传入的TCPSegments，并通过这些状态演进，如下所示。(在实验4之前，您不必担心错误状态或RST标志。)