CS144 笔记 📒

如果是 MacBook (with the ARM64 M1 chip)

sudo -i切换为 root 用户

2、输入dhclient -v

再输入ifconfig就可以看到多了一个 ip 地址

有的同学说重启后命令失效，请参考下面的方法： 1、执行vim ~/.bashrc 2、在最后一行添加dhclient -v 3、保存退出 4、执行source ~/.bashrc使其立即生效

Preparations

cs144 官网

Virtual machine setup instructions

Lab_FAQs

origin https://github.com/cs144/sponge (fetch) origin https://github.com/cs144/sponge (push)

推荐使用：vscode + ssh 连接虚拟机

Lab Checkpoint 0: networking warmup

2.1 Fetch a Web page

1
2
3
4
5
$ telnet cs144.keithw.org http
Trying 104.196.238.229...
Connected to cs144.keithw.org.
Escape character is '^]'.

输入下面的内容（太慢可能会关闭，可以先输入好后复制粘贴）。Hit the Enter key two times

1
2
3
GET /hello HTTP/1.1
Host: cs144.keithw.org
Connection: close
1
2
3
4
5
6
7
8
9
10
11
12
HTTP/1.1 200 OK
Date: Fri, 28 Oct 2022 16:55:15 GMT
Server: Apache
Last-Modified: Thu, 13 Dec 2018 15:45:29 GMT
ETag: "e-57ce93446cb64"
Accept-Ranges: bytes
Content-Length: 14
Connection: close
Content-Type: text/plain

Hello, CS144!
Connection closed by foreign host.

2.3 Listening and connecting

可能出现下面的错误：

1
2
cs144@cs144vm:~/sponge/build$ netcat -v -l -p 9090
netcat: getnameinfo: Temporary failure in name resolution

The problem could be with the DNS resolver. Try updating the namespace in /etc/resolv.conf as follows.

1
nameserver 8.8.8.8

3.4 Writing webget

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void get_URL(const string &host, const string &path) {
    // Your code here.

    // initialize variables
    TCPSocket Tsocket;
    Address addr = Address(host, "http");

    Tsocket.connect(addr);
    // Write a string, possibly blocking until all is written
    string msg = "GET " + path + " HTTP/1.1\r\n" +
                 "Host: " + host + "\r\n" +
                 "Connection: close\r\n\r\n";
    Tsocket.write(msg);
    // socket.h -> SHUT_RD/WR/RDWR，先用SHUT_WR关闭写，避免服务器等待
    Tsocket.shutdown(SHUT_WR);
    while(!Tsocket.eof()){
        cout << Tsocket.read();
    }
    Tsocket.close();
}

4 An in-memory reliable byte stream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// byte_stream.hh
class ByteStream {
  private:
    // Your code here -- add private members as necessary.

    std::deque<char> _deque{};
    size_t _capacity;
    // size_t _buffer_size;  // == _deque.size() [dynamic]
    size_t _bytes_written;
    size_t _bytes_read;
    // size_t _remaining_capacity;  // _
    bool _input_ended;
    // bool _buffer_empty;
    // bool _eof;  // _buffer_empty && _input_ended

    ...
}
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
61
62
63
64
ByteStream::ByteStream(const size_t capacity)
    : _capacity(capacity), _bytes_written(0), _bytes_read(0),
      _input_ended(false)
{
    // DUMMY_CODE(capacity);
}

size_t ByteStream::write(const string &data) {
    // DUMMY_CODE(data);
    size_t input_size = min(remaining_capacity(), data.length());
    for(size_t i = 0; i < input_size; ++i){
        _deque.emplace_back(data[i]);
    }
    _bytes_written += input_size;
    return input_size;
}

//! \param[in] len bytes will be copied from the output side of the buffer
string ByteStream::peek_output(const size_t len) const {
    // DUMMY_CODE(len);
    string output = "";
    size_t output_size = min(buffer_size(), len);
    for(size_t i = 0; i < output_size; ++i){
        output += _deque[i];
    }
    // _bytes_read += output_size; // READ-ONLY!
    return output;
}

//! \param[in] len bytes will be removed from the output side of the buffer
void ByteStream::pop_output(const size_t len) {
    // DUMMY_CODE(len);
    size_t pop_size = min(buffer_size(), len);
    for(size_t i = 0; i < pop_size; ++i){
        _deque.pop_front();
    }
    _bytes_read += pop_size;
}

//! Read (i.e., copy and then pop) the next "len" bytes of the stream
//! \param[in] len bytes will be popped and returned
//! \returns a string
std::string ByteStream::read(const size_t len) {
    // DUMMY_CODE(len);
    string ret = peek_output(len);
    pop_output(len);
    return ret;
}

void ByteStream::end_input() { _input_ended = true; }

bool ByteStream::input_ended() const { return _input_ended; }

size_t ByteStream::buffer_size() const { return _deque.size(); }

bool ByteStream::buffer_empty() const { return buffer_size() == 0; }

bool ByteStream::eof() const { return buffer_empty() && input_ended(); }

size_t ByteStream::bytes_written() const { return _bytes_written; }

size_t ByteStream::bytes_read() const { return _bytes_read; }

size_t ByteStream::remaining_capacity() const { return _capacity - buffer_size(); }

Lab Checkpoint 1: stitching substrings into a byte stream

In Lab 1, you’ll implement a stream reassembler—a module that stitches small pieces of the byte stream (known as substrings, or segments) back into a contiguous stream of bytes in the correct sequence.

3 Putting substrings in sequence

存储 substring 的数据结构选择的是红黑树(std::map)

  • key: index
  • value: substring

空间复杂度为\(O(\log n)\)，插入和删除的时间复杂度为\(O(\log n)\)，遍历时间复杂度为\(O(n)\)。

把接收的 substring 情况先大致分为下面几种，其中先要判断边界条件，窗口外的部分需要丢弃。

对于与 capacity 有重叠部分的 substring 简单分成两种情况：

  1. index > first unread
  2. index <= first unread

然后对end index进行判断，以此确定 substring 需要的区间。

对该所需区间与已存取的区间进行合并(merge)，判断是否能够 push substring。若能则更新几个指针参数(first unread, first unacceptable, etc)。

还需要注意的是 eof 的判断，然后就是实现合并算法和更新数据结构的策略，最后面向测试用例debug 了。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
StreamReassembler::StreamReassembler(const size_t capacity)
  : _first_unread(0), _first_unassembled(0), _first_unacceptable(capacity), _unassembled_bytes(0), _eof_index(-1),
    _outside_size(0), _eof(false), _auxiliary_storage({}), _output(capacity), _capacity(capacity) {}

//! \details This function accepts a substring (aka a segment) of bytes,
//! possibly out-of-order, from the logical stream, and assembles any newly
//! contiguous substrings and writes them into the output stream in order.
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    // DUMMY_CODE(data, index, eof);

    // The number of overlap chars.
    size_t overlap_size = 0;

    // if out of bounds, discard it.
    if(index + data.size() < _first_unread || index > _first_unacceptable){
        return;
    }

    // if in unaassembled area, store it.
    if(index > _first_unread){
        string substring = data.substr(0, min(_first_unacceptable - index, data.size()));
        // if never stored before
        if(_auxiliary_storage.find(index) == _auxiliary_storage.end()){
            _auxiliary_storage[index] = substring;
            overlap_size = overlap_length();
            if(_auxiliary_storage.find(index) == _auxiliary_storage.end()){  // if deleted after merge
                _unassembled_bytes +=  _auxiliary_storage[index].size() - _outside_size;
            }else{
                _unassembled_bytes +=  _auxiliary_storage[index].size() - overlap_size; // c bcd ->error
            }
        }else if(substring.size() > _auxiliary_storage[index].size()){  // update better(longer) substring
            size_t before_len = _auxiliary_storage[index].size();
            _auxiliary_storage[index] = substring;
            overlap_size = overlap_length();
            _unassembled_bytes += before_len + overlap_size;
        }
    }

    //if includes read & unread area, take unread area.
    if(index <= _first_unread){
        size_t end_index = min(data.size() - (_first_unread - index), _capacity);
        _auxiliary_storage[_first_unread] = data.substr(_first_unread - index, end_index);
        size_t len_before = _auxiliary_storage[_first_unread].size();
        overlap_size = overlap_length();
        _unassembled_bytes += len_before - overlap_size; // index -> _first_unread
    }

    // judge if it is possible to push substring
    map<size_t, string>::const_iterator iter = _auxiliary_storage.begin();
    if(iter->first == _first_unread){
        string to_be_written = _auxiliary_storage[_first_unread];
        size_t accepted_size = _output.write(to_be_written);
        _auxiliary_storage.erase(_first_unread); // important!!
        _first_unread += accepted_size;
        _first_unacceptable = _first_unread + _capacity;
        if(_unassembled_bytes < accepted_size){
            _unassembled_bytes = 0;
        } else {
            _unassembled_bytes -= accepted_size;
        }
    }

    if(eof){
        _eof_index = index + data.size();
    }

    if(_eof_index <= _first_unread){
        _output.end_input();
    }
}

size_t StreamReassembler::unassembled_bytes() const { return _unassembled_bytes; }

bool StreamReassembler::empty() const { return _unassembled_bytes == 0; }

size_t StreamReassembler::overlap_length() {
    size_t total_length = 0;
    std::map<size_t, string>::const_iterator iter1 = _auxiliary_storage.begin();
    std::map<size_t, string>::const_iterator iter2 = ++_auxiliary_storage.begin(); // iter next to iter1
    while(iter2 != _auxiliary_storage.end()){
        size_t overlap_size;
        size_t idx1 = iter1->first, idx2 = iter2->first;
        string s1 = iter1->second, s2 = iter2->second;
        if(idx1 + s1.size() >= idx2){  // overlap or neighbours
            iter2++;
            overlap_size = merge_substrings(idx1, idx2, s1, s2);  // _auxiliary_storage[idx2] would be erased
            if(overlap_size == 0){
                if(idx1 + s1.size() == idx2){ // neighbours
                    continue;
                }else{  // previous iter2 has been deleted
                    iter1++;
                    if(iter2 != _auxiliary_storage.end()){
                        iter2++;
                    }else{
                        break;
                    }
                }
            }else{  // overlap
                total_length += overlap_size;
            }
        }else{
            iter1++;
            iter2++;
        }
    }
    return total_length;
}

size_t StreamReassembler::merge_substrings(const size_t idx1, const size_t idx2, const string &data1, const string &data2) {
    size_t overlap = 0;
    // neighbour
    if(idx1 + data1.size() == idx2){
        string data = data1 + data2;
        _auxiliary_storage.erase(idx2);
        _auxiliary_storage[idx1] = data;
        _outside_size = data2.size();
        return overlap;
    }

    // overlap
    // 1. include
    if(idx1+ data1.size() >= idx2 + data2.size()){
        overlap = data2.size();
        _outside_size = 0;
    }else{ // 2. intersection
        overlap = idx1 + data1.size() - idx2;
        _outside_size = data2.size() - overlap;
        string data = data1 + data2.substr(overlap, _outside_size);
        _auxiliary_storage[idx1] = data;
    }
    _auxiliary_storage.erase(idx2);
    return overlap;
}

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

Lab Checkpoint 3: the TCP sender

Now, in Lab 3, you’ll implement the other side of the connection. The TCPSender is a tool that translates from an outgoing byte stream to segments that will become the payloads of unreliable datagrams.

modified files: tcp_sender.hh , tcp_sender.cc

sender part of TCP responsible for:

  1. reading from a ByteStream (created and written to by sender-side application)

  2. turing the stream into a sequence of outgoing TCP segments.

    TCP sender writes the sequence number, the SYN flag, the payload, and the FIN flag.

    TCP sender only reads the segment that written by the receiver: ackno and window_size.

TCPSender’s responsibility to:

  • Keep track of the receiver’s window (processing incoming ackno and window_size)

  • Fill the window when possible

    • Reading from the ByteStream, creating new TCP segments (including SYN and FIN flags if needed)
    • Sending them (until a. the window is full; b. the ByteStream is empty)

  • Keep track of "outstanding" segments

    have been sent but not yet acknowledged

  • Re-send "outstanding" segments if enough time passes since they were sent (time out) and haven't been asked yet

The basic principle is to send whatever the receiver will allow us to send (filling the window), and keep retransmitting until the receiver acknowledges each segment. This is called “automatic repeat request” (ARQ).

tcp_sender.hh

TCPTimer

Handle outstanding segments via TCP Timer. The timer is started when a segment is sent, and is reset when receiving an acknowledgment. If the timer expires (indicating a potential loss of a segment), the oldest unacknowledged segment is retransmitted, and the timer's interval is adjusted according to the exponential backoff algorithm (6(b)ii from lab3.pdf).

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
61
62
63
64
65
66
67
//! \brief TCP Timer
class TCPTimer {
  private:
    //! true: the timer is started
    //! false: the timer is not started
    bool _start;
    //! initial time
    unsigned int _initial_transmission_time;
    //! transmission time
    unsigned int _transmission_time;
    //! retransmission timeout
    unsigned int _RTO;

  public:
    //! number of consecutive retransmissions
    unsigned int num_of_retransmissions;

    TCPTimer(unsigned int t)
        : _start(false)
        , _initial_transmission_time(t)
        , _transmission_time(0)
        , _RTO(_initial_transmission_time) // initial value
        , num_of_retransmissions(0) {}

    //! \brief `true` when Timer is started and `false` when Timer is closed.
    bool status() { return _start; }

    void close() {
        _start = false;
        num_of_retransmissions = 0;
    }

    void start() {
        _start = true;
        _RTO = _initial_transmission_time;
        _transmission_time = 0;
        num_of_retransmissions = 0;
    }

    bool timeout(const size_t ms_since_last_tick) {
        if (!status()) {  // if the timer not running return false
            return false;
        }

        if (ms_since_last_tick + _transmission_time >= _RTO) {
            return true;
        }

        _transmission_time += ms_since_last_tick;
        return false;
    }

    void restart(const size_t window_size) {
        if (!status())
            return;

        // 6(b) If the window size is nonzero, double the value of RTO
        if (window_size != 0) {
            _RTO <<= 1;
        }

        // reset transmission time
        _transmission_time = 0;

        num_of_retransmissions++;
    }
};
TCPSender
  • Stores _ackno and _window_size from TCPSegment sent by the receiver.
  • Returns _bytes_in_flight in the function size_t bytes_in_flight() const;, and is also used for tracking the states illustrated in the diagram.
  • Uses timer to track outstanding segments.
  • Stores outstanding segments in _segments_in_flight.
  • The function void send_segment(TCPSegment &seg); is used for sending non-empty segments.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//! \brief The "sender" part of a TCP implementation.
class TCPSender {
  private:
		...
    /* ! added by myself */

    // the latest ack no has been received
    uint64_t _ackno;
    // receiver’s window size
    size_t _window_size;

    // sequence numbers are occupied by segments sent but not yet acked
    size_t _bytes_in_flight;  // == _next_seqno - _ackno
    // timer used for controlling retransmissions
    TCPTimer timer;
    // segments in flight queue
    std::queue<TCPSegment> _segments_in_flight{};

    // send segment that is not empty
    void send_segment(TCPSegment &seg);

  public:
  	...

tcp_sender.cc

TCPSender::ack_received processes the data from the received segment sent by the remote receiver.


graph LR
A["ack_received()"] -- update data --> C["full_window()"]
C --> D[timer]
D -- init --> F["start()"]
D -- end --> G["close()"]
C --> H[process states]
H --> C
H --> I["send_segment()"]
I --> H


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
//! \param ackno The remote receiver's ackno (acknowledgment number)
//! \param window_size The remote receiver's advertised window size
void TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) {
    uint64_t ackno_received = unwrap(ackno, _isn, _ackno);

    // out of boundary, discard it
    if (ackno_received > next_seqno_absolute()) {
        return;
    }

    // valid ackno
    // uint16_t -> size_t
    _window_size = static_cast<size_t>(window_size);

    // has been acked
    if (ackno_received <= _ackno) {
        return;
    }

    // received new valid ackno
    _ackno = ackno_received;

    // pop out all the segments that have been acked
    while (!_segments_in_flight.empty()) {
        TCPSegment seg = _segments_in_flight.front();
        cerr << "seg.header().seqno.raw_value(): " << seg.header().seqno.raw_value()
             << ", length: " << static_cast<uint32_t>(seg.length_in_sequence_space()) << endl;
        cerr << "ackno.raw_value(): " << ackno.raw_value() << endl;
        if (seg.header().seqno.raw_value() + static_cast<uint32_t>(seg.length_in_sequence_space()) >
            ackno.raw_value()) {
            break;
        }
        _bytes_in_flight -= seg.length_in_sequence_space();
        _segments_in_flight.pop();
        logPrint(seg.payload().str(), "has been poped out of `_segments_in_flight`");
    }

    fill_window();

    if (_segments_in_flight.empty()) {
        timer.close();
        cerr << "[DEBUG] timer closed" << endl;
    } else {
        timer.start();
        cerr << "[DEBUG] timer started" << endl;
    }
}

TCPSender::fill_window() sends segments according to corresponding states of the TCP sender.

Evolution states of the TCP sender

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
61
62
63
64
65
//! \brief create and send segments to fill as much of the window as possible
void TCPSender::fill_window() {
    /* STATUS: CLOSED */
    // waiting for stream to begin (no SYN sent)
    // definition:
    //   next_seqno_absolute() == 0
    if (next_seqno_absolute() == 0) {
        TCPSegment init_seg;
        init_seg.header().syn = true;
        init_seg.header().seqno = next_seqno();
        send_segment(init_seg);
        logPrint(init_seg.payload().str(), "init_seg sent (SYN)");
    }

    /* STATUS: SYN_SENT */
    // stream started but nothing acknowledged
    // definition:
    //   next_seqno_absolute() > 0
    //   and next_seqno_absolute() == bytes_in_flight()
    if (next_seqno_absolute() > 0 && next_seqno_absolute() == bytes_in_flight()) {
        return;
    }

    /* Conection has been built */

    // If the receiver has announced a window size of zero, the fill window method should act like the window size is
    // *one*.
    size_t window_size = _window_size == 0 ? 1 : _window_size;

    size_t remain_size;

    while ((remain_size = window_size - (next_seqno_absolute() - _ackno))) {
        TCPSegment seg;
        size_t len = remain_size < TCPConfig::MAX_PAYLOAD_SIZE ? remain_size : TCPConfig::MAX_PAYLOAD_SIZE;

        /* STATUS: SYN_ACKED */
        // “stream ongoing”
        // if output haven't reach the end
        if (next_seqno_absolute() > bytes_in_flight() && !stream_in().eof()) {
            seg.payload() = Buffer(_stream.read(len));
            // if all data has been read, set FIN value
            // second condition: "Don't add FIN if this would make the segment exceed the receiver's window"
            if (_stream.eof() && remain_size - seg.length_in_sequence_space() > 0) {
                seg.header().fin = true;
            }
            if (seg.length_in_sequence_space() == 0)
                return;  // _stream has nothing to send
            send_segment(seg);
        }

        /* STATUS: SYN_ACKED */
        // “stream ongoing” (stream has reached EOF, but FIN flag hasn't been sent yet)
        else if (stream_in().eof() && next_seqno_absolute() < stream_in().bytes_written() + 2) {
            seg.header().fin = true;
            send_segment(seg);
        }

        /* STATUS: FIN_SENT & FIN_ACKED */
        // have no business with `fill_window()`
        else if (stream_in().eof() && next_seqno_absolute() == stream_in().bytes_written() + 2) {
            return;
        }
        // return;
    }
}

When TCPSender::tick(const size_t ms_since_last_tick) is called, it handles the milliseconds and maintains the timer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void TCPSender::tick(const size_t ms_since_last_tick) {
    // if timer is closed or not timeout, do nothing
    if (!timer.timeout(ms_since_last_tick)) {
        return;
    }

    // if nothing can be retransmitted, close the timer
    if (_segments_in_flight.empty()) {
        timer.close();
        return;
    }

    // occurs timeout, retransmit the first segment in the `segments_in_filght`
    timer.restart(_window_size);
    segments_out().push(_segments_in_flight.front());
}

Build & Test

1
2
3
cd build
make -j8
ctest -R send_
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
cs144@cs144vm:~/sponge/build$ ctest -R send_
Test project /home/cs144/sponge/build
    Start 11: t_send_connect
1/7 Test #11: t_send_connect ...................   Passed    0.00 sec
    Start 12: t_send_transmit
2/7 Test #12: t_send_transmit ..................   Passed    0.03 sec
    Start 13: t_send_retx
3/7 Test #13: t_send_retx ......................   Passed    0.00 sec
    Start 14: t_send_window
4/7 Test #14: t_send_window ....................   Passed    0.01 sec
    Start 15: t_send_ack
5/7 Test #15: t_send_ack .......................   Passed    0.00 sec
    Start 16: t_send_close
6/7 Test #16: t_send_close .....................   Passed    0.00 sec
    Start 17: t_send_extra
7/7 Test #17: t_send_extra .....................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 7

Total Test time (real) =   0.06 sec
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
cs144@cs144vm:~/sponge/build$ make check_lab3
[100%] Testing the TCP sender...
Test project /home/cs144/sponge/build
      Start  1: t_wrapping_ints_cmp
 1/33 Test  #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
      Start  2: t_wrapping_ints_unwrap
 2/33 Test  #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
      Start  3: t_wrapping_ints_wrap
 3/33 Test  #3: t_wrapping_ints_wrap .............   Passed    0.00 sec
      Start  4: t_wrapping_ints_roundtrip
 4/33 Test  #4: t_wrapping_ints_roundtrip ........   Passed    0.06 sec
      Start  5: t_recv_connect
 5/33 Test  #5: t_recv_connect ...................   Passed    0.00 sec
      Start  6: t_recv_transmit
 6/33 Test  #6: t_recv_transmit ..................   Passed    0.03 sec
      Start  7: t_recv_window
 7/33 Test  #7: t_recv_window ....................   Passed    0.00 sec
      Start  8: t_recv_reorder
 8/33 Test  #8: t_recv_reorder ...................   Passed    0.00 sec
      Start  9: t_recv_close
 9/33 Test  #9: t_recv_close .....................   Passed    0.00 sec
      Start 10: t_recv_special
10/33 Test #10: t_recv_special ...................   Passed    0.00 sec
      Start 11: t_send_connect
11/33 Test #11: t_send_connect ...................   Passed    0.00 sec
      Start 12: t_send_transmit
12/33 Test #12: t_send_transmit ..................   Passed    0.02 sec
      Start 13: t_send_retx
13/33 Test #13: t_send_retx ......................   Passed    0.00 sec
      Start 14: t_send_window
14/33 Test #14: t_send_window ....................   Passed    0.01 sec
      Start 15: t_send_ack
15/33 Test #15: t_send_ack .......................   Passed    0.00 sec
      Start 16: t_send_close
16/33 Test #16: t_send_close .....................   Passed    0.00 sec
      Start 17: t_send_extra
17/33 Test #17: t_send_extra .....................   Passed    0.00 sec
      Start 18: t_strm_reassem_single
18/33 Test #18: t_strm_reassem_single ............   Passed    0.00 sec
      Start 19: t_strm_reassem_seq
19/33 Test #19: t_strm_reassem_seq ...............   Passed    0.00 sec
      Start 20: t_strm_reassem_dup
20/33 Test #20: t_strm_reassem_dup ...............   Passed    0.01 sec
      Start 21: t_strm_reassem_holes
21/33 Test #21: t_strm_reassem_holes .............   Passed    0.00 sec
      Start 22: t_strm_reassem_many
22/33 Test #22: t_strm_reassem_many ..............   Passed    0.04 sec
      Start 23: t_strm_reassem_overlapping
23/33 Test #23: t_strm_reassem_overlapping .......   Passed    0.00 sec
      Start 24: t_strm_reassem_win
24/33 Test #24: t_strm_reassem_win ...............   Passed    0.04 sec
      Start 25: t_strm_reassem_cap
25/33 Test #25: t_strm_reassem_cap ...............   Passed    0.06 sec
      Start 26: t_byte_stream_construction
26/33 Test #26: t_byte_stream_construction .......   Passed    0.00 sec
      Start 27: t_byte_stream_one_write
27/33 Test #27: t_byte_stream_one_write ..........   Passed    0.00 sec
      Start 28: t_byte_stream_two_writes
28/33 Test #28: t_byte_stream_two_writes .........   Passed    0.00 sec
      Start 29: t_byte_stream_capacity
29/33 Test #29: t_byte_stream_capacity ...........   Passed    0.30 sec
      Start 30: t_byte_stream_many_writes
30/33 Test #30: t_byte_stream_many_writes ........   Passed    0.00 sec
      Start 53: t_address_dt
31/33 Test #53: t_address_dt .....................   Passed    0.00 sec
      Start 54: t_parser_dt
32/33 Test #54: t_parser_dt ......................   Passed    0.00 sec
      Start 55: t_socket_dt
33/33 Test #55: t_socket_dt ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 33

Total Test time (real) =   0.61 sec
[100%] Built target check_lab3

Lab Checkpoint 4: the summit (TCP in full)

Now, in Lab 4, you will make the overarching module, called TCPConnection, that combines your TCPSender and TCPReceiver and handles the global housekeeping for the connection. The connection’s TCP segments can be encapsulated into the payloads of user (TCP-in-UDP) or Internet (TCP/IP) datagrams—letting your code talk to billions of other computers on the Internet that speak the same TCP/IP language.

modified files: tcp_connection.hh, tcp_connection.cc , tcp_sender.hh , tcp_sender.cc.

tcp_sender.hh

  • Add _fin_sent and corresponding function bool fin_sent().
  • Replace the return type void into bool to tell the caller whether the timer is restart.

tcp_sender.cc

  • Handle _fin_sent state and timeout situation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void TCPSender::fill_window() {
    ... // handle `_fin_sent` state
    /* STATUS: FIN_SENT & FIN_ACKED */
    // have no business with `fill_window()`
    else if (stream_in().eof() && next_seqno_absolute() == stream_in().bytes_written() + 2) {
        // cerr << "STATUS: FIN_SENT & FIN_ACKED; Timer is" << (timer.status() ? " " : " not ") << "running" << endl;
        /* FIN_SENT */
        if (bytes_in_flight() > 0) {
            // cerr << "STATUS: FIN_SENT" << endl;
            if(timer.timeout(0)) { // timeout, resend FIN
                // cerr << "Timeout, resend FIN" << endl;
                seg.header().fin = true;
                send_segment(seg);
            }
        }
        /* FIN_ACKED */
        else if (bytes_in_flight() == 0){
            // cerr << "STATUS: FIN_ACKED " << endl;
        }
        return;
    }
}

tcp_connection.hh

  • _active: Indicates whether the connection is currently active. Defaults to true.

  • _established: Represents whether the connection has been successfully established. Defaults to false.

  • _rst: Reset flag (RST). When set to true, it indicates an instant termination of the connection.

  • _ms_since_last_segment_received: Tracks the time (in milliseconds) since the last segment was received.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class TCPConnection {
  private:
		...

    //! my attributes
    bool _active = true;
    bool _established = false;
    //! reset flag - `RST`
    //! means instant death to the connection.
    bool _rst = false;
    size_t _ms_since_last_segment_received = 0;

    void send_segments();

    void set_rst();

    void final_operation();

    void fill_queue(std::queue<TCPSegment>& stream_queue);

  	...
};

tcp_connection.cc

  • send_segments(): Handles the logic for sending queued TCP segments from the sender's queue.

    1. If the queue is empty, an empty segment is sent.
    2. If the connection is in reset mode (_rst == true), the segments are filled with the reset flag.
    3. Segments are sent out until the queue is empty.

  • final_operation(): checks if the connection is done and can be closed. (Corresponding to 5

    The end of a TCP connection: consensus takes work)

    1. If the inbound stream is fully assembled, but the outbound stream has not yet ended, it disables lingering (_linger_after_streams_finish = false).
    2. If both the inbound and outbound streams are fully processed and there are no bytes in flight, the connection is marked inactive if lingering is disabled or if enough time has passed (10×RTT timeout) since the last segment was received.

  • fill_queue(std::queue<TCPSegment>& stream_queue): processes the queue of outgoing TCP segments from the sender.

    1. Each segment is popped from the queue.
    2. If the receiver has an acknowledgment number, it is added to the segment header.
    3. The segment is marked with the appropriate flags (RST, ACK, window size).
    4. The segment is pushed to the _segments_out queue for transmission.
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
size_t TCPConnection::remaining_outbound_capacity() const { return _sender.stream_in().remaining_capacity(); }

size_t TCPConnection::bytes_in_flight() const { return _sender.bytes_in_flight(); }

size_t TCPConnection::unassembled_bytes() const { return _receiver.unassembled_bytes(); }

size_t TCPConnection::time_since_last_segment_received() const { return _ms_since_last_segment_received; }

void TCPConnection::segment_received(const TCPSegment &seg) {
    if (!_active)
        return;

    _ms_since_last_segment_received = 0;

    if (seg.header().rst) {
        set_rst();
        return;
    }

    _receiver.segment_received(seg);

    // if the ACK feld is set, give that ackno and window size to TCPSender
    if (seg.header().ack) {
        _sender.ack_received(seg.header().ackno, seg.header().win);
    }

    // first handshake
    if (seg.header().syn && !_established) {
        if (seg.header().ack) {
            _established = true;
        } else {
            _sender.fill_window();
        }
    } else if (seg.header().ack && !_established) {
        /* SYN-RECEIVE -> ESTABLISHED */
        _established = true;
    }

    // reply when segment received is not empty or _sender's queue is not empty
    if (seg.length_in_sequence_space() != 0 || !_sender.segments_out().empty()) {
        send_segments();
    }

    final_operation();
}

bool TCPConnection::active() const { return _active; }

size_t TCPConnection::write(const string &data) {
    // DUMMY_CODE(data);
    // return {};
    size_t written_bytes = _sender.stream_in().write(data);
    _sender.fill_window();
    send_segments();

    final_operation();

    return written_bytes;
}

//! \param[in] ms_since_last_tick number of milliseconds since the last call to this method
void TCPConnection::tick(const size_t ms_since_last_tick) {
    // DUMMY_CODE(ms_since_last_tick);
    _ms_since_last_segment_received += ms_since_last_tick;

    if (_sender.tick(ms_since_last_tick)) {  // if timeout
        if (_sender.consecutive_retransmissions() > TCPConfig::MAX_RETX_ATTEMPTS) {
            set_rst();
            return;
        }
        send_segments();
    }

    final_operation();
}

void TCPConnection::end_input_stream() {
    _sender.stream_in().end_input();
    _sender.fill_window();

    send_segments();

    final_operation();
}

void TCPConnection::connect() {
    if (_sender.next_seqno_absolute() != 0) {
        // already connected
        return;
    }
    _sender.fill_window();
    send_segments();
    _active = true;
}

TCPConnection::~TCPConnection() {
    try {
        if (active()) {
            cerr << "Warning: Unclean shutdown of TCPConnection\n";

            // Your code here: need to send a RST segment to the peer
            set_rst();
        }
    } catch (const exception &e) {
        std::cerr << "Exception destructing TCP FSM: " << e.what() << std::endl;
    }
}

void TCPConnection::set_rst() {
    _active = false;
    _rst = true;
    _linger_after_streams_finish = false;
    _sender.stream_in().set_error();
    _receiver.stream_out().set_error();
    if (_established) {
        send_segments();
    }
}

void TCPConnection::send_segments() {
    std::queue<TCPSegment> &stream_queue = _sender.segments_out();
    if (stream_queue.empty()) {
        _sender.send_empty_segment();
    }
    if (_rst) {
        fill_queue(stream_queue);
        return;
    }
    while (!stream_queue.empty()) {
        fill_queue(stream_queue);
    }
}

void TCPConnection::final_operation() {
    // If the inbound stream ends before the TCPConnection has reached EOF on its outbound stream,
    // this variable needs to be set to `false`.
    if (_receiver.stream_out().input_ended() && !_sender.stream_in().eof() &&
        _sender.next_seqno_absolute() > 0) {  // NOTE: different
        if (_linger_after_streams_finish) {
        }
        _linger_after_streams_finish = false;
    }

    // At any point where prerequisites #1 through #3 are satisfied, the connection is “done” (and active() should return
    // false) if linger after streams finish is false. Otherwise you need to linger: the connection is only done after
    // enough time (10 × cfg.rt timeout) has elapsed since the last segment was received. Prereq # 1 The inbound stream
    // has been fully assembled and has ended.
    if (_receiver.unassembled_bytes() == 0 && _receiver.stream_out().eof()) {
        // Prereq # 2 and # 3
        // The outbound stream has been ended by the local application and fully sent
        // (including the fact that it ended, i.e. a segment with `fin` ) to the remote peer.
        if (_sender.stream_in().eof() && _sender.fin_sent() && bytes_in_flight() == 0) {
            if (!_linger_after_streams_finish) {
                _active = false;
            } else if (_ms_since_last_segment_received >= 10 * _cfg.rt_timeout) {
                _active = false;
            }
        }
    }
}

void TCPConnection::fill_queue(std::queue<TCPSegment> &stream_queue) {
    TCPSegment seg = stream_queue.front();
    stream_queue.pop();

    if (_receiver.ackno().has_value()) {
        seg.header().ack = true;
        seg.header().ackno = _receiver.ackno().value();
    }

    seg.header().rst = _rst;

    size_t window_size = _receiver.window_size();
    seg.header().win = window_size < std::numeric_limits<uint16_t>::max() ? static_cast<uint16_t>(window_size)
                                                                          : std::numeric_limits<uint16_t>::max();

    _segments_out.push(seg);
}

Test

Test Naming Conventions

Symbol Description
c Your code is the client (peer that sends the first SYN).
s Your code is the server.
u Testing TCP-over-UDP.
i Testing TCP-over-IP (TCP/IP).
n Trying to interoperate with Linux’s TCP implementation.
S Your code is sending data.
R Your code is receiving data.
D Data is being sent in both directions.
l Packet loss on the receiving (incoming segment) direction.
L Packet loss on the sending (outgoing segment) direction. 
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
# Release with Address Sanitizer for memory error detection
cmake .. -DCMAKE_BUILD_TYPE=RelASan

# optimized for performance, without debug information
cmake .. -DCMAKE_BUILD_TYPE=Release

# includes debug symbols for better traceability of errors
cmake .. -DCMAKE_BUILD_TYPE=Debug

# Run the TCP benchmarking application
./apps/tcp_benchmark

# Run the specified test
ctest --output-on-failure -V -R t_ucR_128K_8K # e.g., this could be test #67


## 6 Testing
# Play around with your custom TCP implementation, and capture traffic to debug with Wireshark.
# You may need to install tshark (command-line version of Wireshark) first:
sudo apt install tshark

# Capture traffic on interface 'tun144' and save to a file in raw format
sudo tshark -Pw /tmp/debug.raw -i tun144

# Start the TCP server, listening on IP 169.254.144.9 and port 9090
./apps/tcp_ipv4 -l 169.254.144.9 9090 # server

# Start the TCP client, sending traffic from IP 169.254.145.9 to the server at 169.254.144.9 on port 9090
./apps/tcp_ipv4 -d tun145 -a 169.254.145.9 169.254.144.9 9090 # client

Results and Improvements

This is the first time I've passed all the tests.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
cs144@cs144vm:~/sponge/build$ make check_lab4
[100%] Testing the TCP connection...
Test project /home/cs144/sponge/build
        Start   1: t_wrapping_ints_cmp
  1/162 Test   #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
        Start   2: t_wrapping_ints_unwrap
  2/162 Test   #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
        Start   3: t_wrapping_ints_wrap
  3/162 Test   #3: t_wrapping_ints_wrap .............   Passed    0.00 sec
        Start   4: t_wrapping_ints_roundtrip
  4/162 Test   #4: t_wrapping_ints_roundtrip ........   Passed    0.06 sec
        Start   5: t_recv_connect
  5/162 Test   #5: t_recv_connect ...................   Passed    0.00 sec
        Start   6: t_recv_transmit
  6/162 Test   #6: t_recv_transmit ..................   Passed    0.03 sec
        Start   7: t_recv_window
  7/162 Test   #7: t_recv_window ....................   Passed    0.00 sec
        Start   8: t_recv_reorder
  8/162 Test   #8: t_recv_reorder ...................   Passed    0.00 sec
        Start   9: t_recv_close
  9/162 Test   #9: t_recv_close .....................   Passed    0.00 sec
        Start  10: t_recv_special
 10/162 Test  #10: t_recv_special ...................   Passed    0.00 sec
        Start  11: t_send_connect
 11/162 Test  #11: t_send_connect ...................   Passed    0.00 sec
        Start  12: t_send_transmit
 12/162 Test  #12: t_send_transmit ..................   Passed    0.02 sec
        Start  13: t_send_retx
 13/162 Test  #13: t_send_retx ......................   Passed    0.00 sec
        Start  14: t_send_window
 14/162 Test  #14: t_send_window ....................   Passed    0.01 sec
        Start  15: t_send_ack
 15/162 Test  #15: t_send_ack .......................   Passed    0.00 sec
        Start  16: t_send_close
 16/162 Test  #16: t_send_close .....................   Passed    0.00 sec
        Start  17: t_send_extra
 17/162 Test  #17: t_send_extra .....................   Passed    0.00 sec
        Start  18: t_strm_reassem_single
 18/162 Test  #18: t_strm_reassem_single ............   Passed    0.00 sec
        Start  19: t_strm_reassem_seq
 19/162 Test  #19: t_strm_reassem_seq ...............   Passed    0.00 sec
        Start  20: t_strm_reassem_dup
 20/162 Test  #20: t_strm_reassem_dup ...............   Passed    0.00 sec
        Start  21: t_strm_reassem_holes
 21/162 Test  #21: t_strm_reassem_holes .............   Passed    0.00 sec
        Start  22: t_strm_reassem_many
 22/162 Test  #22: t_strm_reassem_many ..............   Passed    0.04 sec
        Start  23: t_strm_reassem_overlapping
 23/162 Test  #23: t_strm_reassem_overlapping .......   Passed    0.00 sec
        Start  24: t_strm_reassem_win
 24/162 Test  #24: t_strm_reassem_win ...............   Passed    0.04 sec
        Start  25: t_strm_reassem_cap
 25/162 Test  #25: t_strm_reassem_cap ...............   Passed    0.05 sec
        Start  26: t_byte_stream_construction
 26/162 Test  #26: t_byte_stream_construction .......   Passed    0.00 sec
        Start  27: t_byte_stream_one_write
 27/162 Test  #27: t_byte_stream_one_write ..........   Passed    0.00 sec
        Start  28: t_byte_stream_two_writes
 28/162 Test  #28: t_byte_stream_two_writes .........   Passed    0.00 sec
        Start  29: t_byte_stream_capacity
 29/162 Test  #29: t_byte_stream_capacity ...........   Passed    0.31 sec
        Start  30: t_byte_stream_many_writes
 30/162 Test  #30: t_byte_stream_many_writes ........   Passed    0.00 sec
        Start  31: t_webget
 31/162 Test  #31: t_webget .........................   Passed    1.99 sec
        Start  34: t_tcp_parser
 32/162 Test  #34: t_tcp_parser .....................   Passed    0.00 sec
        Start  35: t_ipv4_parser
 33/162 Test  #35: t_ipv4_parser ....................   Passed    0.00 sec
        Start  36: t_active_close
 34/162 Test  #36: t_active_close ...................   Passed    0.00 sec
        Start  37: t_passive_close
 35/162 Test  #37: t_passive_close ..................   Passed    0.00 sec
        Start  39: t_ack_rst
 36/162 Test  #39: t_ack_rst ........................   Passed    0.00 sec
        Start  41: t_ack_rst_win
 37/162 Test  #41: t_ack_rst_win ....................   Passed    0.00 sec
        Start  43: t_connect
 38/162 Test  #43: t_connect ........................   Passed    0.00 sec
        Start  45: t_listen
 39/162 Test  #45: t_listen .........................   Passed    0.00 sec
        Start  46: t_winsize
 40/162 Test  #46: t_winsize ........................   Passed    0.02 sec
        Start  48: t_retx
 41/162 Test  #48: t_retx ...........................   Passed    0.00 sec
        Start  49: t_retx_win
 42/162 Test  #49: t_retx_win .......................   Passed    0.00 sec
        Start  50: t_loopback
 43/162 Test  #50: t_loopback .......................   Passed    0.08 sec
        Start  51: t_loopback_win
 44/162 Test  #51: t_loopback_win ...................   Passed    0.04 sec
        Start  52: t_reorder
 45/162 Test  #52: t_reorder ........................   Passed    0.09 sec
        Start  53: t_address_dt
 46/162 Test  #53: t_address_dt .....................   Passed    0.00 sec
        Start  54: t_parser_dt
 47/162 Test  #54: t_parser_dt ......................   Passed    0.00 sec
        Start  55: t_socket_dt
 48/162 Test  #55: t_socket_dt ......................   Passed    0.00 sec
        Start  56: t_udp_client_send
 49/162 Test  #56: t_udp_client_send ................   Passed    0.24 sec
        Start  57: t_udp_server_send
 50/162 Test  #57: t_udp_server_send ................   Passed    0.24 sec
        Start  58: t_udp_client_recv
 51/162 Test  #58: t_udp_client_recv ................   Passed    0.24 sec
        Start  59: t_udp_server_recv
 52/162 Test  #59: t_udp_server_recv ................   Passed    0.23 sec
        Start  60: t_udp_client_dupl
 53/162 Test  #60: t_udp_client_dupl ................   Passed    0.24 sec
        Start  61: t_udp_server_dupl
 54/162 Test  #61: t_udp_server_dupl ................   Passed    0.24 sec
        Start  62: t_ucS_1M_32k
 55/162 Test  #62: t_ucS_1M_32k .....................   Passed    0.26 sec
        Start  63: t_ucS_128K_8K
 56/162 Test  #63: t_ucS_128K_8K ....................   Passed    0.24 sec
        Start  64: t_ucS_16_1
 57/162 Test  #64: t_ucS_16_1 .......................   Passed    0.24 sec
        Start  65: t_ucS_32K_d
 58/162 Test  #65: t_ucS_32K_d ......................   Passed    0.24 sec
        Start  66: t_ucR_1M_32k
 59/162 Test  #66: t_ucR_1M_32k .....................   Passed    0.26 sec
        Start  67: t_ucR_128K_8K
 60/162 Test  #67: t_ucR_128K_8K ....................   Passed    0.24 sec
        Start  68: t_ucR_16_1
 61/162 Test  #68: t_ucR_16_1 .......................   Passed    0.24 sec
        Start  69: t_ucR_32K_d
 62/162 Test  #69: t_ucR_32K_d ......................   Passed    0.24 sec
        Start  70: t_ucD_1M_32k
 63/162 Test  #70: t_ucD_1M_32k .....................   Passed    0.28 sec
        Start  71: t_ucD_128K_8K
 64/162 Test  #71: t_ucD_128K_8K ....................   Passed    0.24 sec
        Start  72: t_ucD_16_1
 65/162 Test  #72: t_ucD_16_1 .......................   Passed    0.24 sec
        Start  73: t_ucD_32K_d
 66/162 Test  #73: t_ucD_32K_d ......................   Passed    0.24 sec
        Start  74: t_usS_1M_32k
 67/162 Test  #74: t_usS_1M_32k .....................   Passed    0.26 sec
        Start  75: t_usS_128K_8K
 68/162 Test  #75: t_usS_128K_8K ....................   Passed    0.24 sec
        Start  76: t_usS_16_1
 69/162 Test  #76: t_usS_16_1 .......................   Passed    0.24 sec
        Start  77: t_usS_32K_d
 70/162 Test  #77: t_usS_32K_d ......................   Passed    0.24 sec
        Start  78: t_usR_1M_32k
 71/162 Test  #78: t_usR_1M_32k .....................   Passed    0.26 sec
        Start  79: t_usR_128K_8K
 72/162 Test  #79: t_usR_128K_8K ....................   Passed    0.24 sec
        Start  80: t_usR_16_1
 73/162 Test  #80: t_usR_16_1 .......................   Passed    0.24 sec
        Start  81: t_usR_32K_d
 74/162 Test  #81: t_usR_32K_d ......................   Passed    0.24 sec
        Start  82: t_usD_1M_32k
 75/162 Test  #82: t_usD_1M_32k .....................   Passed    0.28 sec
        Start  83: t_usD_128K_8K
 76/162 Test  #83: t_usD_128K_8K ....................   Passed    0.25 sec
        Start  84: t_usD_16_1
 77/162 Test  #84: t_usD_16_1 .......................   Passed    0.24 sec
        Start  85: t_usD_32K_d
 78/162 Test  #85: t_usD_32K_d ......................   Passed    0.24 sec
        Start  86: t_ucS_128K_8K_l
 79/162 Test  #86: t_ucS_128K_8K_l ..................   Passed    0.25 sec
        Start  87: t_ucS_128K_8K_L
 80/162 Test  #87: t_ucS_128K_8K_L ..................   Passed    0.52 sec
        Start  88: t_ucS_128K_8K_lL
 81/162 Test  #88: t_ucS_128K_8K_lL .................   Passed    0.61 sec
        Start  89: t_ucR_128K_8K_l
 82/162 Test  #89: t_ucR_128K_8K_l ..................   Passed    0.39 sec
        Start  90: t_ucR_128K_8K_L
 83/162 Test  #90: t_ucR_128K_8K_L ..................   Passed    0.24 sec
        Start  91: t_ucR_128K_8K_lL
 84/162 Test  #91: t_ucR_128K_8K_lL .................   Passed    0.64 sec
        Start  92: t_ucD_128K_8K_l
 85/162 Test  #92: t_ucD_128K_8K_l ..................   Passed    0.55 sec
        Start  93: t_ucD_128K_8K_L
 86/162 Test  #93: t_ucD_128K_8K_L ..................   Passed    0.38 sec
        Start  94: t_ucD_128K_8K_lL
 87/162 Test  #94: t_ucD_128K_8K_lL .................   Passed    0.56 sec
        Start  95: t_usS_128K_8K_l
 88/162 Test  #95: t_usS_128K_8K_l ..................   Passed    0.24 sec
        Start  96: t_usS_128K_8K_L
 89/162 Test  #96: t_usS_128K_8K_L ..................   Passed    0.50 sec
        Start  97: t_usS_128K_8K_lL
 90/162 Test  #97: t_usS_128K_8K_lL .................   Passed    0.81 sec
        Start  98: t_usR_128K_8K_l
 91/162 Test  #98: t_usR_128K_8K_l ..................   Passed    0.44 sec
        Start  99: t_usR_128K_8K_L
 92/162 Test  #99: t_usR_128K_8K_L ..................   Passed    0.24 sec
        Start 100: t_usR_128K_8K_lL
 93/162 Test #100: t_usR_128K_8K_lL .................   Passed    0.48 sec
        Start 101: t_usD_128K_8K_l
 94/162 Test #101: t_usD_128K_8K_l ..................   Passed    0.47 sec
        Start 102: t_usD_128K_8K_L
 95/162 Test #102: t_usD_128K_8K_L ..................   Passed    0.53 sec
        Start 103: t_usD_128K_8K_lL
 96/162 Test #103: t_usD_128K_8K_lL .................   Passed    0.62 sec
        Start 104: t_ipv4_client_send
 97/162 Test #104: t_ipv4_client_send ...............   Passed    0.24 sec
        Start 105: t_ipv4_server_send
 98/162 Test #105: t_ipv4_server_send ...............   Passed    0.24 sec
        Start 106: t_ipv4_client_recv
 99/162 Test #106: t_ipv4_client_recv ...............   Passed    0.24 sec
        Start 107: t_ipv4_server_recv
100/162 Test #107: t_ipv4_server_recv ...............   Passed    0.24 sec
        Start 108: t_ipv4_client_dupl
101/162 Test #108: t_ipv4_client_dupl ...............   Passed    0.24 sec
        Start 109: t_ipv4_server_dupl
102/162 Test #109: t_ipv4_server_dupl ...............   Passed    0.24 sec
        Start 110: t_icS_1M_32k
103/162 Test #110: t_icS_1M_32k .....................   Passed    0.29 sec
        Start 111: t_icS_128K_8K
104/162 Test #111: t_icS_128K_8K ....................   Passed    0.24 sec
        Start 112: t_icS_16_1
105/162 Test #112: t_icS_16_1 .......................   Passed    0.24 sec
        Start 113: t_icS_32K_d
106/162 Test #113: t_icS_32K_d ......................   Passed    0.24 sec
        Start 114: t_icR_1M_32k
107/162 Test #114: t_icR_1M_32k .....................   Passed    0.28 sec
        Start 115: t_icR_128K_8K
108/162 Test #115: t_icR_128K_8K ....................   Passed    0.24 sec
        Start 116: t_icR_16_1
109/162 Test #116: t_icR_16_1 .......................   Passed    0.24 sec
        Start 117: t_icR_32K_d
110/162 Test #117: t_icR_32K_d ......................   Passed    0.24 sec
        Start 118: t_icD_1M_32k
111/162 Test #118: t_icD_1M_32k .....................   Passed    0.32 sec
        Start 119: t_icD_128K_8K
112/162 Test #119: t_icD_128K_8K ....................   Passed    0.26 sec
        Start 120: t_icD_16_1
113/162 Test #120: t_icD_16_1 .......................   Passed    0.25 sec
        Start 121: t_icD_32K_d
114/162 Test #121: t_icD_32K_d ......................   Passed    0.24 sec
        Start 122: t_isS_1M_32k
115/162 Test #122: t_isS_1M_32k .....................   Passed    0.29 sec
        Start 123: t_isS_128K_8K
116/162 Test #123: t_isS_128K_8K ....................   Passed    0.24 sec
        Start 124: t_isS_16_1
117/162 Test #124: t_isS_16_1 .......................   Passed    0.24 sec
        Start 125: t_isS_32K_d
118/162 Test #125: t_isS_32K_d ......................   Passed    0.25 sec
        Start 126: t_isR_1M_32k
119/162 Test #126: t_isR_1M_32k .....................   Passed    0.29 sec
        Start 127: t_isR_128K_8K
120/162 Test #127: t_isR_128K_8K ....................   Passed    0.25 sec
        Start 128: t_isR_16_1
121/162 Test #128: t_isR_16_1 .......................   Passed    0.24 sec
        Start 129: t_isR_32K_d
122/162 Test #129: t_isR_32K_d ......................   Passed    0.24 sec
        Start 130: t_isD_1M_32k
123/162 Test #130: t_isD_1M_32k .....................   Passed    0.32 sec
        Start 131: t_isD_128K_8K
124/162 Test #131: t_isD_128K_8K ....................   Passed    0.25 sec
        Start 132: t_isD_16_1
125/162 Test #132: t_isD_16_1 .......................   Passed    0.24 sec
        Start 133: t_isD_32K_d
126/162 Test #133: t_isD_32K_d ......................   Passed    0.24 sec
        Start 134: t_icS_128K_8K_l
127/162 Test #134: t_icS_128K_8K_l ..................   Passed    0.25 sec
        Start 135: t_icS_128K_8K_L
128/162 Test #135: t_icS_128K_8K_L ..................   Passed    0.41 sec
        Start 136: t_icS_128K_8K_lL
129/162 Test #136: t_icS_128K_8K_lL .................   Passed    0.43 sec
        Start 137: t_icR_128K_8K_l
130/162 Test #137: t_icR_128K_8K_l ..................   Passed    0.35 sec
        Start 138: t_icR_128K_8K_L
131/162 Test #138: t_icR_128K_8K_L ..................   Passed    0.25 sec
        Start 139: t_icR_128K_8K_lL
132/162 Test #139: t_icR_128K_8K_lL .................   Passed    0.50 sec
        Start 140: t_icD_128K_8K_l
133/162 Test #140: t_icD_128K_8K_l ..................   Passed    0.46 sec
        Start 141: t_icD_128K_8K_L
134/162 Test #141: t_icD_128K_8K_L ..................   Passed    0.50 sec
        Start 142: t_icD_128K_8K_lL
135/162 Test #142: t_icD_128K_8K_lL .................   Passed    0.58 sec
        Start 143: t_isS_128K_8K_l
136/162 Test #143: t_isS_128K_8K_l ..................   Passed    0.24 sec
        Start 144: t_isS_128K_8K_L
137/162 Test #144: t_isS_128K_8K_L ..................   Passed    0.42 sec
        Start 145: t_isS_128K_8K_lL
138/162 Test #145: t_isS_128K_8K_lL .................   Passed    0.56 sec
        Start 146: t_isR_128K_8K_l
139/162 Test #146: t_isR_128K_8K_l ..................   Passed    0.54 sec
        Start 147: t_isR_128K_8K_L
140/162 Test #147: t_isR_128K_8K_L ..................   Passed    0.24 sec
        Start 148: t_isR_128K_8K_lL
141/162 Test #148: t_isR_128K_8K_lL .................   Passed    0.39 sec
        Start 149: t_isD_128K_8K_l
142/162 Test #149: t_isD_128K_8K_l ..................   Passed    0.46 sec
        Start 150: t_isD_128K_8K_L
143/162 Test #150: t_isD_128K_8K_L ..................   Passed    0.46 sec
        Start 151: t_isD_128K_8K_lL
144/162 Test #151: t_isD_128K_8K_lL .................   Passed    0.44 sec
        Start 152: t_icnS_128K_8K_l
145/162 Test #152: t_icnS_128K_8K_l .................   Passed    0.25 sec
        Start 153: t_icnS_128K_8K_L
146/162 Test #153: t_icnS_128K_8K_L .................   Passed    0.22 sec
        Start 154: t_icnS_128K_8K_lL
147/162 Test #154: t_icnS_128K_8K_lL ................   Passed    0.21 sec
        Start 155: t_icnR_128K_8K_l
148/162 Test #155: t_icnR_128K_8K_l .................   Passed    0.85 sec
        Start 156: t_icnR_128K_8K_L
149/162 Test #156: t_icnR_128K_8K_L .................   Passed    0.25 sec
        Start 157: t_icnR_128K_8K_lL
150/162 Test #157: t_icnR_128K_8K_lL ................   Passed    0.53 sec
        Start 158: t_icnD_128K_8K_l
151/162 Test #158: t_icnD_128K_8K_l .................   Passed    0.46 sec
        Start 159: t_icnD_128K_8K_L
152/162 Test #159: t_icnD_128K_8K_L .................   Passed    0.23 sec
        Start 160: t_icnD_128K_8K_lL
153/162 Test #160: t_icnD_128K_8K_lL ................   Passed    0.66 sec
        Start 161: t_isnS_128K_8K_l
154/162 Test #161: t_isnS_128K_8K_l .................   Passed    0.12 sec
        Start 162: t_isnS_128K_8K_L
155/162 Test #162: t_isnS_128K_8K_L .................   Passed    0.27 sec
        Start 163: t_isnS_128K_8K_lL
156/162 Test #163: t_isnS_128K_8K_lL ................   Passed    0.41 sec
        Start 164: t_isnR_128K_8K_l
157/162 Test #164: t_isnR_128K_8K_l .................   Passed    0.26 sec
        Start 165: t_isnR_128K_8K_L
158/162 Test #165: t_isnR_128K_8K_L .................   Passed    0.25 sec
        Start 166: t_isnR_128K_8K_lL
159/162 Test #166: t_isnR_128K_8K_lL ................   Passed    0.69 sec
        Start 167: t_isnD_128K_8K_l
160/162 Test #167: t_isnD_128K_8K_l .................   Passed    1.01 sec
        Start 168: t_isnD_128K_8K_L
161/162 Test #168: t_isnD_128K_8K_L .................   Passed    0.25 sec
        Start 169: t_isnD_128K_8K_lL
162/162 Test #169: t_isnD_128K_8K_lL ................   Passed    0.66 sec

100% tests passed, 0 tests failed out of 162

Total Test time (real) =  41.45 sec
[100%] Built target check_lab4
cs144@cs144vm:~/sponge/build$
1
2
3
cs144@cs144vm:~/sponge/build$ ./apps/tcp_benchmark
CPU-limited throughput                : 1.14 Gbit/s
CPU-limited throughput with reordering: 0.87 Gbit/s
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
cs144@cs144vm:~/sponge/build$ curl google.com
<HTML><HEAD><meta http-equiv="content-type" content="text/html;charset=utf-8">
<TITLE>301 Moved</TITLE></HEAD><BODY>
<H1>301 Moved</H1>
The document has moved
<A HREF="http://www.google.com/">here</A>.
</BODY></HTML>
cs144@cs144vm:~/sponge/build$ ./apps/webget google.com /
DEBUG: Connecting to 172.217.25.14:80... done.
DEBUG: Outbound stream to 172.217.25.14:80 finished (56 bytes still in flight).
DEBUG: Outbound stream to 172.217.25.14:80 has been fully acknowledged.
HTTP/1.1 301 Moved Permanently
Location: http://www.google.com/
Content-Type: text/html; charset=UTF-8
Content-Security-Policy-Report-Only: object-src 'none';base-uri 'self';script-src 'nonce-4IjQrdJDtNiCR8ugZdgnwQ' 'strict-dynamic' 'report-sample' 'unsafe-eval' 'unsafe-inline' https: http:;report-uri https://csp.withgoogle.com/csp/gws/other-hp
Date: Wed, 21 Feb 2024 09:23:56 GMT
Expires: Fri, 22 Mar 2024 09:23:56 GMT
Cache-Control: public, max-age=2592000
Server: gws
Content-Length: 219
X-XSS-Protection: 0
X-Frame-Options: SAMEORIGIN
Connection: close

<HTML><HEAD><meta http-equiv="content-type" content="text/html;charset=utf-8">
<TITLE>301 Moved</TITLE></HEAD><BODY>
<H1>301 Moved</H1>
The document has moved
<A HREF="http://www.google.com/">here</A>.
</BODY></HTML>
DEBUG: Waiting for clean shutdown... DEBUG: Inbound stream from 172.217.25.14:80 finished cleanly.
DEBUG: Waiting for lingering segments (e.g. retransmissions of FIN) from peer...
DEBUG: TCP connection finished cleanly.
done.
BufferList

Use BufferList from utl/buffer.hh instead of std::deque<char> for _queue to store the content. BufferList reduces overhead by managing larger blocks of data more efficiently, minimizing the need for frequent allocations and reducing memory fragmentation compared to handling individual characters. It supports batch operations, allowing efficient appending, copying, and removal of large data chunks, which is ideal for stream processing. Additionally, peeking and removing data is faster, as BufferList provides direct access to underlying buffers without shifting elements in memory.

BufferList 
1
2
3
cs144@cs144vm:~/sponge/build$ ./apps/tcp_benchmark
CPU-limited throughput                : 6.32 Gbit/s
CPU-limited throughput with reordering: 2.49 Gbit/s
std::move

Using std::move when inserting a std::string into a std::map<size_t, std::string> is advantageous because it avoids the overhead of copying the string's contents, instead transferring ownership of its internal resources. This makes the operation faster and more efficient, especially for large strings, as moving a string simply transfers pointers rather than duplicating data. Additionally, it ensures better resource management by leaving the original string in a valid but empty state, reducing memory and CPU usage compared to assignment.

move 
1
2
3
cs144@cs144vm:~/sponge/build$ ./apps/tcp_benchmark
CPU-limited throughput                : 6.31 Gbit/s
CPU-limited throughput with reordering: 3.22 Gbit/s

Lab Checkpoint 5: down the stack (the network interface)

In this lab, you’ll go down the stack and implement a network interface: the bridge between Internet datagrams that travel the world, and link-layer Ethernet frames that travel one hop.

modified files: network_interface.hh, network_interface.cc.

network_interface.hh

  • _arp_table: A soft-state mapping cache that stores the association between IP addresses and Ethernet addresses for 30 seconds.

    1. Stores ARP_Entry objects, which contain the Ethernet address and a time-to-live (TTL) value.
    2. The TTL ensures that mappings expire after 30 seconds, preventing stale mappings.

  • _arp_requests_timer: Tracks the time since the last ARP request was sent for a specific IP address.

    1. If an ARP request has been sent for an IP address in the last 5 seconds, no new request is sent.

  • _arp_requests_ip_datagram: A queue of InternetDatagrams that are waiting for ARP replies before they can be sent.

    1. Holds datagrams that cannot be sent until the destination Ethernet address is known.
    2. Once the ARP reply is received, the datagrams are sent immediately.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NetworkInterface {
  private:
		...

    //! remember the mapping between the sender’s IP address and Ethernet address for 30 seconds
    const size_t _arp_entry_default_ttl = 30 * 1000;

    //! If the network interface already sent an ARP request about the same IP address in the last five seconds, don’t send a second request
    const size_t _arp_request_default_ttl = 5 * 1000;

    //! ARP Entry
    struct ARP_Entry {
        EthernetAddress eth_addr;
        size_t ttl;
    };

    //! Mapping cache (soft state)
    std::map<uint32_t, ARP_Entry> _arp_table{};
    std::map<uint32_t, size_t> _arp_requests_timer{};

    std::list<std::pair<uint32_t, InternetDatagram>> _arp_requests_ip_datagram{};
		...
};

network_interface.cc

  • send_datagram(const InternetDatagram &dgram, const Address &next_hop): Sends the IPv4 datagram to the specified next-hop IP address.

    1. If the Ethernet address for the next-hop IP is known, the datagram is encapsulated in an Ethernet frame and sent.
    2. If the Ethernet address is unknown, an ARP request is broadcasted and the datagram is queued until a reply is received.

  • recv_frame(const EthernetFrame &frame): Handles incoming Ethernet frames.

    1. If the frame contains an IPv4 datagram, it is parsed and returned to the caller.
    2. If the frame contains an ARP message, the IP-to-Ethernet mapping is remembered, and any queued datagrams for the IP are sent.
    3. In response to an ARP request targeting the network interface's IP address, an ARP reply is sent back to the requester.

  • tick(const size_t ms_since_last_tick): Manages the expiration of ARP table entries and ARP request timers.

    1. Decreases the TTL of each ARP table entry and removes entries that have expired.
    2. Decreases the timer for ARP requests and resends ARP requests if necessary after 5 seconds.
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
//! \param[in] dgram the IPv4 datagram to be sent
//! \param[in] next_hop the IP address of the interface to send it to (typically a router or default gateway, but may also be another host if directly connected to the same network as the destination)
//! (Note: the Address type can be converted to a uint32_t (raw 32-bit IP address) with the Address::ipv4_numeric() method.)
void NetworkInterface::send_datagram(const InternetDatagram &dgram, const Address &next_hop) {
    // convert IP address of next hop to raw 32-bit representation (used in ARP header)
    const uint32_t next_hop_ip = next_hop.ipv4_numeric();

    // cerr << "[DEBUG] send_datagram\n";
    const auto &arp_iter = _arp_table.find(next_hop_ip);

    // If the destination Ethernet address is already known, send it right away.
    if (arp_iter != _arp_table.end()) {
        // cerr << "the destination Ethernet address is already known, send it right away\n";
        // Create an Ethernet frame
        EthernetFrame eth_frame;

        // set the source and destination addresses
        eth_frame.header().dst = arp_iter->second.eth_addr;
        eth_frame.header().src = this->_ethernet_address;
        eth_frame.header().type = EthernetHeader::TYPE_IPv4;

        // set the payload to be the serialized datagram
        eth_frame.payload() = dgram.serialize();

        frames_out().push(eth_frame);
    }
    // If the destination Ethernet address is unknown, broadcast an ARP request
    else if (_arp_requests_timer.find(next_hop_ip) == _arp_requests_timer.end()) {
        // cerr << "the destination Ethernet address is unknown, broadcast an ARP request\n";
        ARPMessage arp_request;

        arp_request.opcode = ARPMessage::OPCODE_REQUEST;

        arp_request.sender_ethernet_address = this->_ethernet_address;
        arp_request.sender_ip_address = this->_ip_address.ipv4_numeric();

        // `arp_request.target_ethernet_address` is what we want
        arp_request.target_ip_address = next_hop_ip;

        // queue the IP datagram so it can be sent after the ARP reply is received.
        _arp_requests_ip_datagram.emplace_back(std::pair<uint32_t, InternetDatagram>(next_hop_ip, dgram));
        _arp_requests_timer[next_hop_ip] = NetworkInterface::_arp_request_default_ttl;

        EthernetFrame eth_frame;
        eth_frame.header().dst = ETHERNET_BROADCAST;
        eth_frame.header().src = this->_ethernet_address;
        eth_frame.header().type = EthernetHeader::TYPE_ARP;

        eth_frame.payload() = BufferList(arp_request.serialize());

        frames_out().push(eth_frame);
    }
}

//! \param[in] frame the incoming Ethernet frame
optional<InternetDatagram> NetworkInterface::recv_frame(const EthernetFrame &frame) {
    // cerr << "[DEBUG] recv_frame \n";
    // ignore any frames not destined for the network interface
    // the Ethernet destination is either the broadcast address or the interface’s own Ethernet address stored in the
    // `_ethernet_address` member variable
    if (frame.header().dst != this->_ethernet_address && frame.header().dst != ETHERNET_BROADCAST) {
        return {};
    }

    if (frame.header().type == EthernetHeader::TYPE_IPv4) {
        // parse the payload as an InternetDatagram and, if successful (meaning the parse() method returned
        // ParseResult::NoError), return the resulting InternetDatagram to the caller.
        InternetDatagram dgram;
        if (dgram.parse(frame.payload()) == ParseResult::NoError) {
            return dgram;
        }
    }
    // Parse the payload as an ARPMessage and, if successful, remember the mapping
    else if (frame.header().type == EthernetHeader::TYPE_ARP) {
        ARPMessage arp_msg;
        if (arp_msg.parse(frame.payload()) == ParseResult::NoError) {
            const uint32_t &src_ip_addr = arp_msg.sender_ip_address;
            const uint32_t &dst_ip_addr = arp_msg.target_ip_address;
            const EthernetAddress &src_eth_addr = arp_msg.sender_ethernet_address;
            const EthernetAddress &dst_eth_addr = arp_msg.target_ethernet_address;

            // ARP request asking for our IP address
            bool is_valid_arp_request =
                (dst_ip_addr == this->_ip_address.ipv4_numeric() && arp_msg.opcode == ARPMessage::OPCODE_REQUEST);
            // ARP reply for our ARP request
            bool is_valid_arp_reply =
                (dst_eth_addr == this->_ethernet_address && arp_msg.opcode == ARPMessage::OPCODE_REPLY);

            // if successful, remember the mapping between the sender’s IP address and Ethernet address for 30 seconds
            // (Learn mappings from both requests and replies.)
            if (is_valid_arp_request || is_valid_arp_reply) {
                _arp_table[src_ip_addr] = {src_eth_addr, NetworkInterface::_arp_entry_default_ttl};

                // send the IP datagram in the queue
                std::list<std::pair<uint32_t, InternetDatagram>>::iterator iter = _arp_requests_ip_datagram.begin();
                while (iter != _arp_requests_ip_datagram.end()) {
                    if (iter->first == src_ip_addr) {
                        send_datagram(iter->second, Address::from_ipv4_numeric(src_ip_addr));
                        iter = _arp_requests_ip_datagram.erase(iter);
                    } else {
                        iter++;
                    }
                }
                _arp_requests_timer.erase(src_ip_addr);
            }

            // In addition, if it’s an ARP request asking for our IP address, send an appropriate ARP reply.
            if (is_valid_arp_request) {
                // cerr << "   [DEBUG] is_valid_arp_request \n";
                ARPMessage arp_reply;
                arp_reply.sender_ip_address = this->_ip_address.ipv4_numeric();
                arp_reply.sender_ethernet_address = this->_ethernet_address;
                arp_reply.target_ip_address = src_ip_addr;
                arp_reply.target_ethernet_address = src_eth_addr;
                arp_reply.opcode = ARPMessage::OPCODE_REPLY;

                EthernetFrame eth_frame;
                eth_frame.header().src = arp_reply.sender_ethernet_address;
                eth_frame.header().dst = arp_reply.target_ethernet_address;
                eth_frame.header().type = EthernetHeader::TYPE_ARP;

                eth_frame.payload() = BufferList(arp_reply.serialize());

                frames_out().push(eth_frame);
            }
        }
    }
    return {};
}

//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void NetworkInterface::tick(const size_t ms_since_last_tick) {
    /* ARP table */
    // Expire any IP-to-Ethernet mappings that have expired.
    for (std::map<uint32_t, ARP_Entry>::iterator iter = _arp_table.begin(); iter != _arp_table.end();
         /* removed (Segment Fault) */) {
        if (iter->second.ttl <= ms_since_last_tick) {
            iter = _arp_table.erase(iter);
        } else {
            iter->second.ttl -= ms_since_last_tick;
            iter++;  // increment at this line
        }
    }

    /* ARP request */
    for (auto iter = _arp_requests_timer.begin(); iter != _arp_requests_timer.end(); ++iter) {
        // Resend ARP request for expired ARP request
        if (iter->second <= ms_since_last_tick) {
            // cerr << "Resend ARP request for expired ARP request. [ip="
            //      << Address::from_ipv4_numeric(iter->first).to_string() << "]\n";
            ARPMessage arp_request;

            arp_request.opcode = ARPMessage::OPCODE_REQUEST;

            arp_request.sender_ethernet_address = this->_ethernet_address;
            arp_request.sender_ip_address = this->_ip_address.ipv4_numeric();

            // `arp_request.target_ethernet_address` is what we want
            arp_request.target_ip_address = iter->first;

            EthernetFrame eth_frame;
            eth_frame.header().dst = ETHERNET_BROADCAST;
            eth_frame.header().src = this->_ethernet_address;
            eth_frame.header().type = EthernetHeader::TYPE_ARP;

            eth_frame.payload() = BufferList(arp_request.serialize());

            frames_out().push(eth_frame);

            iter->second = NetworkInterface::_arp_request_default_ttl;
        } else {
            iter->second -= ms_since_last_tick;
        }
    }
}

Test

1
ctest --output-on-failure -V -R "^arp"

Results

1
2
3
4
5
6
7
8
9
10
11
12
cs144@cs144vm:~/sponge/build$ make check_lab5
Testing Lab 5...
Test project /home/cs144/sponge/build
    Start 31: t_webget
1/2 Test #31: t_webget .........................   Passed    2.02 sec
    Start 32: arp_network_interface
2/2 Test #32: arp_network_interface ............   Passed    0.00 sec

100% tests passed, 0 tests failed out of 2

Total Test time (real) =   2.03 sec
Built target check_lab5
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
cs144@cs144vm:~/sponge/build$ ctest --output-on-failure -V -R "^arp"
UpdateCTestConfiguration  from :/home/cs144/sponge/build/DartConfiguration.tcl
UpdateCTestConfiguration  from :/home/cs144/sponge/build/DartConfiguration.tcl
Test project /home/cs144/sponge/build
Constructing a list of tests
Done constructing a list of tests
Updating test list for fixtures
Added 0 tests to meet fixture requirements
Checking test dependency graph...
Checking test dependency graph end
test 32
    Start 32: arp_network_interface

32: Test command: /home/cs144/sponge/build/tests/net_interface
32: Test timeout computed to be: 10000000
32: DEBUG: Network interface has Ethernet address 62:9f:b7:22:23:5c and IP address 4.3.2.1
32: DEBUG: Network interface has Ethernet address 1e:fb:05:3f:41:b9 and IP address 5.5.5.5
32: DEBUG: Network interface has Ethernet address ba:a7:34:13:93:2d and IP address 5.5.5.5
32: DEBUG: Network interface has Ethernet address 22:a9:60:f2:a1:dd and IP address 1.2.3.4
32: DEBUG: Network interface has Ethernet address be:3f:99:d2:5b:43 and IP address 4.3.2.1
32: DEBUG: Network interface has Ethernet address 26:15:35:db:24:9e and IP address 10.0.0.1
1/1 Test #32: arp_network_interface ............   Passed    0.01 sec

The following tests passed:
	arp_network_interface

100% tests passed, 0 tests failed out of 1

Lab Checkpoint 6: building an IP router

In this lab checkpoint, you’ll implement an IP router on top of your existing NetworkInterface. A router has several network interfaces, and can receive Internet datagrams on any of them. The router’s job is to forward the datagrams it gets according to the routing table: a list of rules that tells the router, for any given datagram,

  • What interface to send it out
  • The IP address of the next hop

router.hh

  • router_entry: Represents an entry in the router's routing table.

  • _routing_table: A set that stores all routing entries for the router.

    1. Each entry is sorted according to the router_entry comparison operator.
    2. This ensures the most specific routes are checked first when forwarding a datagram.

  • check_prefix(uint32_t entry_prefix, uint32_t compared_prefix, uint8_t prefix_length): Checks if the destination IP matches the network defined by the routing table entry.

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
class Router {
    ...

    // Routing table
    struct router_entry {
        uint32_t route_prefix;
        uint8_t prefix_length;
        std::optional<Address> next_hop;
        size_t interface_num;

        // Define the comparison operator
        bool operator<(const router_entry &other) const {
            // Sort by prefix_length in descending order
            if (prefix_length != other.prefix_length) {
                return prefix_length > other.prefix_length;
            }
            return route_prefix < other.route_prefix;
        }
    };

    std::set<router_entry> _routing_table{};

    // Define a function to print the routing table for testing purposes
    void print_routing_table() {
        for (const auto &entry : _routing_table) {
            std::cerr << "  Address: " << Address::from_ipv4_numeric(entry.route_prefix).to_string()
                      << ", Length: " << static_cast<int>(entry.prefix_length) << ", Interface: " << entry.interface_num
                      << std::endl;
        }
    }

    bool check_prefix(uint32_t entry_prefix, uint32_t compared_prefix, uint8_t prefix_length);
  ...
};

router.cc

  • route_one_datagram(InternetDatagram &dgram): Handles forwarding of an Internet datagram according to the routing table.

    1. The TTL is decremented. If the TTL reaches zero, the datagram is discarded to prevent it from circulating indefinitely.
    2. The routing table is traversed to find a matching entry for the destination IP.
    3. If a match is found, the router forwards the datagram:
    • If the router is directly connected to the destination network, the datagram is sent directly to the destination IP.
    • Otherwise, the datagram is sent to the next hop specified in the routing table.

  • check_prefix(uint32_t entry_prefix, uint32_t compared_prefix, uint8_t prefix_length): Verifies if a datagram’s destination matches a routing table entry.

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
//! \param[in] dgram The datagram to be routed
void Router::route_one_datagram(InternetDatagram &dgram) {
    // The router decrements the datagram’s TTL (time to live).
    // If the TTL was zero already, or hits zero after the decrement, the router should drop the datagram.
    if (dgram.header().ttl <= 1) {
        return;
    } else {
        dgram.header().ttl--;
    }

    // bool is_found = false;

    for (auto &entry : _routing_table) {
        if (check_prefix(entry.route_prefix, dgram.header().dst, entry.prefix_length)) {
            cerr << "[DEBUG] dst: " << Address::from_ipv4_numeric(dgram.header().dst).to_string() << "/"
                 << int(entry.prefix_length)
                 << " -> router: " << Address::from_ipv4_numeric(entry.route_prefix).to_string() << endl;
            // If the router is directly* attached to the network in question, the next hop will be an empty optional.
            // In that case, the next hop is the datagram’s destination address.
            if (!entry.next_hop.has_value()) {
                interface(entry.interface_num).send_datagram(dgram, Address::from_ipv4_numeric(dgram.header().dst));

            } else {
                interface(entry.interface_num).send_datagram(dgram, entry.next_hop.value());
            }
            return;
        }
    }
}

bool Router::check_prefix(uint32_t entry_prefix, uint32_t compared_prefix, uint8_t prefix_length) {
    uint32_t mask = prefix_length == 0 ? 0 : UINT32_MAX << (32 - prefix_length);
    cerr << "check prefix:\n  mask            =" << std::bitset<32>(mask) << endl;
    cerr << "  entry_prefix    =" << std::bitset<32>(entry_prefix & mask) << " ("
         << Address::from_ipv4_numeric(entry_prefix & mask).to_string() << ")"
         << "\n  compared_prefix =" << std::bitset<32>(compared_prefix & mask) << " ("
         << Address::from_ipv4_numeric(compared_prefix & mask).to_string() << ")" << endl;
    return (entry_prefix & mask) == (compared_prefix & mask);
}

Results

1
2
3
4
5
6
7
8
9
10
11
12
cs144@cs144vm:~/sponge/build$ make check_lab6
[100%] Testing Lab 6...
Test project /home/cs144/sponge/build
    Start 32: arp_network_interface
1/2 Test #32: arp_network_interface ............   Passed    0.00 sec
    Start 33: router_test
2/2 Test #33: router_test ......................   Passed    0.01 sec

100% tests passed, 0 tests failed out of 2

Total Test time (real) =   0.01 sec
[100%] Built target check_lab6

参考

其他

Project Description

Implemented a series of labs covering key aspects of networking, focusing on building reliable transport protocols and understanding TCP/IP stack concepts. The project demonstrates proficiency in socket programming, byte stream manipulation, TCP segment handling, and connection management.

Technical Keywords

  • Networking
  • TCP/IP
  • C++

Key Achievements and Technologies

  • Lab 1: Implemented a ByteStream and basic socket communication to fetch web pages using low-level TCP connections. Developed an understanding of TCP socket programming fundamentals.
    • Utilized C++ sockets for network communication.
    • Implemented stream reassembly logic for ordered byte stream delivery.
  • Lab 2: Built the TCP Receiver, handling incoming TCP segments and reconstructing the byte stream by managing sequence numbers, acknowledgment numbers, and window sizes.
    • Managed 64-bit sequence numbers and 32-bit TCP sequence number wrapping.
    • Developed logic to track TCP window size and maintain in-order stream reassembly.
  • Lab 3: Developed the TCP Sender, responsible for transforming byte streams into TCP segments and ensuring reliable transmission through retransmission and acknowledgment handling.
    • Implemented Automatic Repeat Request (ARQ) and exponential backoff for retransmissions.
    • Handled TCP segment creation, including SYN, ACK, and FIN flags.
  • Lab 4: Integrated both the sender and receiver into a complete TCP connection, managing the lifecycle of TCP connections, including connection establishment, data transmission, and teardown.
    • Implemented a full TCP connection state machine, tracking connection state and handling connection errors (RST, FIN).
    • Applied TCP flow control and congestion control mechanisms to ensure reliable and efficient data transmission.
  • Lab 5: Extended the TCP implementation with timeout mechanisms and optimizations for handling large data transfers with minimal packet loss.
    • Fine-tuned the retransmission timeout (RTO) mechanism.
    • Enhanced error handling and packet loss recovery using adaptive retransmission strategies.
  • Lab 6: Tested the full TCP stack implementation with real-world benchmarking tools, including Wireshark for packet analysis and tuning the system for optimal performance under varying network conditions.
    • Used tshark to capture and analyze network traffic.
    • Achieved 100% pass rate on extensive test suites, validating the robustness and correctness of the implementation.

Each lab focused on gradually constructing a reliable, efficient, and standard-compliant TCP stack, culminating in a full TCP-over-UDP and TCP/IP solution that interoperates with existing network stacks.

项目：CS144 实验（Lab 1-6）

总结：

通过一系列实验，开发了一个 TCP/IP 网络栈，实现了可靠的字节流、TCP 发送端、接收端以及连接模块。

技术关键词：

  • TCP/IP 网络, C++, 可靠字节流

主要贡献：

  • Lab 1-3: 字节流与 TCP 接收端实现

    • 开发了支持读写操作的内存字节流，使用动态缓冲区管理数据。
    • 实现了 Stream Reassembler，能够处理乱序的字节段并有效地将其重新组装为连续的数据流。
    • 构建了 TCPReceiver，将接收到的 TCP 段转换为连续的字节流，并正确处理 SYN、ACK 和 FIN 标志。

  • Lab 4: TCP 发送端实现

    • 设计了 TCPSender，处理具有序列号的段的传输，并使用定时器和指数退避算法实现重传逻辑。
    • 管理 TCP 段的创建、窗口大小的跟踪以及自动重传请求（ARQ），以确保数据可靠传输。
    • 处理超时重传等边缘情况，并维护未确认的段以等待确认。

  • Lab 5-6: TCP 连接管理

    • 将 TCPReceiver 和 TCPSender 集成到完整的 TCPConnection 中，管理双向数据传输。
    • 实现了三次握手、段确认、窗口更新及连接关闭的逻辑。
    • 使用基准测试工具和 Wireshark 数据包捕获分析进行调试和测试，确保 TCP 栈的正确性和性能。

项目：CS144 实验（Lab 1-6）

总结：

通过一系列实验，开发了一个 TCP/IP 网络栈，实现了可靠的字节流、TCP 发送端、接收端以及连接模块。

技术关键词：

  • TCP/IP 网络, C++, 可靠字节流

主要贡献：

  • Lab 1-3: 字节流与 TCP 接收端实现 我开发了一个支持动态读写操作的内存字节流，并实现了数据缓冲区的有效管理。通过构建 Stream Reassembler，我能够将乱序接收到的字节段重新组装为正确顺序的连续流。随后实现了 TCPReceiver，用于接收 TCP 段并将其转换为完整的字节流，同时处理 TCP 协议中的 SYN、ACK 和 FIN 标志。

  • Lab 4: TCP 发送端实现 我设计并实现了 TCPSender，负责从应用程序的字节流中创建 TCP 段并进行发送。通过引入定时器和自动重传机制（ARQ），系统能够在网络丢包的情况下自动重传未确认的段，确保可靠的数据传输。同时，TCP 发送端能够根据接收方的窗口大小动态调整发送速率。

  • Lab 5-6: TCP 连接管理 在这些实验中，我将 TCPReceiver 和 TCPSender 组合成一个完整的 TCPConnection 模块，管理双向的 TCP 数据流传输。通过实现三次握手、ACK 确认、窗口更新及连接关闭的功能，确保了 TCP 连接的可靠性。最后，我使用基准测试工具和 Wireshark 分析工具对实现进行调试和优化，确保了网络栈的性能和稳定性。

[!Caution]

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