CS144 lab2 笔记 📒

Lab Checkpoint 2: the TCP receiver

In Lab 2, you will implement the TCPReceiver, the part of a TCP implementation that handles the incoming byte stream. The TCPReceiver translates between incoming TCP segments (the payloads of datagrams carried over the Internet) and the incoming byte stream.

TCPReceiver除了写入即将到来的数据之外，还需要告诉发送端：

  1. first_unassembled的索引（即ackno），是接收端当前所需要的第一个字节；
  2. first_unassembled和first unacceptable之间的距离（即window size）。

二者共同描述了接收端的窗口信息：「TCP 发送端允许发送的索引范围」：

\[ \left[ackno, ackno + window\ size \right) \]

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

Lab1 中实现的StreamReassembler能够重组数据流字符串（64-bit indexes）。可以认为 64-bit index 足够大到不可能溢出。[1]而在 TCP 首部，由于空间非常宝贵，数据流的每个字节的索引即"sequence number"/"seqno."以 32-bit 呈现。以下 3 点需要注意：

  1. 实现需要考虑包装 32-bit 整型。\(2^{32}\) bytes 只有 \(4\) GiB，需要循环计数（\(0\ \sim \ 2^{32}-1\)）；
  2. TCP sequence numbers 起始于一个随机数。为了提高安全性和避免不同连接之间的混淆，TCP 试图确保序列号不能被猜到，而且不太可能重复。因此，一个流的序列号不从零开始。流中的第一个序列号通常是一个随机的 32-bit 整型，称为初始序列号（ISN）。这是代表 SYN（流的开始）的序列号。数据的第一个 byte 的序列号将会是\(\rm{ISN} + 1(\rm{mod}\ 2^{32})\)；
  3. 开始和结束都算作序列中的一个位置。除了确保收到所有字节的数据外，TCP 必须确保也能收到流的开始和结束。因此，在 TCP 中，SYN（数据流的开始）和 FIN（数据流的结束）标志都被分配了序列号。这些计数都在序列中占据一个位置。数据流中的每个字节也在序列中占据一个位置。

下面是cat字符串的例子，其中ISN = \(2^{32}-2\)

\[ \begin{array}{r|c|c|c|c|c} \text { element } & \text { SYN } & \text { c } & \text { a } & \text { t } & \text { FIN } \\ \hline \text { seqno } & 2^{32}-2 & 2^{32}-1 & 0 & 1 & 2 \\ \hline \text { absolute seqno } & 0 & 1 & 2 & 3 & 4 \\ \hline \text { stream index } & & 0 & 1 & 2 & \end{array} \]

TCP 涉及到的三种不同索引方式如下表所示

Sequence Numbers Absolute Sequence Numbers Stream Indices
Start at the ISN Start at 0 Start at 0
Include SYN/FIN Include SYN/FIN Omit SYN/FIN
32 bits, wrapping 64 bits, non-wrapping 64 bits, non-wrapping
“seqno” “absolute seqno” “stream index”

实现前两者的相互转换将通过以下两个函数：

  1. WrappingInt32 wrap(uint64_t n, WrappingInt32 isn)：absolute seqno. \(\rightarrow\) seqno.
  2. uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint)：seqno. \(\rightarrow\) absolute seqno. 其中checkpoint用于消除 absolute seqno 的歧义，最接近 checkpoint 的对应 absolute seqno. 即为所求。(checkpoint表示最近一次转换求得的absolute seqno，而本次转换出的absolute seqno应该选择与上次值最为接近的那一个)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    // implicit conversion: static_cast<uint32_t>(...)
    // return WrappingInt32(static_cast<uint32_t>(n) + isn.raw_value());
    return WrappingInt32(n + isn.raw_value());
}

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    uint32_t offset = n.raw_value() - wrap(checkpoint, isn).raw_value();
    uint64_t result = checkpoint + offset;
    if(offset > (1ul << 31) && result >= (1ul << 32)){
        result -= (1ul << 32);
    }
    return result;
}

3.1 Implementing the TCP receiver

将实现TCPReceiver。它将

    1. 从它的对等方接收 segments；

    1. 使用StreamReassembler重新组装ByteStream

    2. 维护确认号(ackno) 和 窗口大小。

  • 需要注意的是 ackno 的更新，因为 TCPsegment 的传入可能是乱序的，同时 SYN 和 FIN 也影响着 ackno，还要考虑可能同时到达的情况。

  • window_size实质上是接收者能够接受的索引范围大小。也就是first unassembled和first unacceptable之间的距离。

    In other words: it's the capacity minus the number of bytes that the TCPReceiver is holding in the byte stream.

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
void TCPReceiver::segment_received(const TCPSegment &seg) {
    bool is_init = false;

    // update status
    if(seg.header().fin){ _fin_flag = true;}

    if(!_syn_flag && seg.header().syn && !_init_seqno.has_value()){
        _syn_flag = true;
        // make sure stream must be ended with_syn().with_fin()
        string data = seg.payload().copy();
        uint64_t abs_seqno = unwrap(seg.header().seqno, seg.header().seqno, _reassembler.first_unassembled());
        bool eof = seg.header().fin;
        // void push_substring(const std::string &data, const uint64_t index, const bool eof)
        _reassembler.push_substring(data, abs_seqno, eof);

        WrappingInt32 absolute_seqno_zero = wrap(_reassembler.first_unassembled(), seg.header().seqno);
        _ack_no = WrappingInt32(absolute_seqno_zero.raw_value() + 1);
        _init_seqno = _ack_no;
        is_init = true;
    }

    // push seg's string
    if(_init_seqno.has_value() && !is_init){
        string data = seg.payload().copy();
        uint64_t abs_seqno = unwrap(seg.header().seqno, _init_seqno.value(), _reassembler.first_unassembled());
        bool eof = seg.header().fin;
        // void push_substring(const std::string &data, const uint64_t index, const bool eof)
        _reassembler.push_substring(data, abs_seqno, eof);
        _ack_no = wrap(_reassembler.first_unassembled(), _init_seqno.value());
    }

    // seg with FIN had come before and all data has been wrtten
    if(_fin_flag && _reassembler.stream_out().input_ended()){
        _ack_no = WrappingInt32(_ack_no.value() + 1);
    }
}

optional<WrappingInt32> TCPReceiver::ackno() const { return _ack_no; }

size_t TCPReceiver::window_size() const { return stream_out().remaining_capacity(); }

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
cs144@cs144vm:~/sponge/build$ make check_lab2
[100%] Testing the TCP receiver...
Test project /home/cs144/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.06 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.05 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.05 sec
      Start 25: t_strm_reassem_cap
18/26 Test #25: t_strm_reassem_cap ...............   Passed    0.05 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.23 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.51 sec
[100%] Built target check_lab2

更新：将第 27 行代码更新为第 28 行代码 修复了下述情况遇到的错误

1
2
with_syn().with_seqno(5).with_fin()
SYN received (ackno exists), and input to stream hasn't ended
seqno230325116123032511622303251163230325116423032511652303251166230325116723032511682303251169
e
g
c
ab
f
  1. 添加_first_unassembled的接口
  2. 修复了上述 bug

参考

  1. 以 100Gbps 的传输速度计算，需要接近 50 年的时间才能达到 (2^{64}) bytes 的数据量；作为对比，只需要约 (1/3) 秒即可达到 (2^{32}) bytes 的数据量。 ↩︎
courses
#notes #CS144 #C++
CS144 lab2 笔记 📒
http://example.com/2023/12/09/CS144-note-lab2/
作者
臣皮蛋
发布于
2023年12月9日
许可协议