CS144-Lab2 – 任我行

本文最后更新于 677 天前，其中的信息可能已经有所发展或是发生改变。

Lab Checkpoint 2: the TCP receiver

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

first unassembled的索引（即ackno），是接收端当前所需要的第一个字节；
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点需要注意：

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

TCP三种不同索引方式

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

WrappingInt32 wrap(uint64 t n, WrappingInt32 isn)：absolute seqno. $\rightarrow$ seqno.
uint64 t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64 t checkpoint)：seqno. $\rightarrow$ absolute seqno. 其中checkpoint用于消除absolute seqno的歧义，最接近checkpoint的对应absolute seqno. 即为所求。

WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
    // implicit conversion: static_cast<uint32_t>(...)
    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。它将

从它的对等方接收segments；
使用StreamReassembler重新组装ByteStream；
维护确认号(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.

此外还在StreamReassembler添加了_first_unassembled的外部访问接口。

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(); }

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

Lab Checkpoint 2: the TCP receiver

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

3.1 Implementing the TCP receiver

参考

发送评论编辑评论

Lab Checkpoint 2: the TCP receiver

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

3.1 Implementing the TCP receiver

参考

发送评论 编辑评论

推荐文章

发送评论编辑评论