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)

cs144@cs144vm:~/sponge/build$ git config --list
user.email=FacundoChan01@gmail.com
user.name=Facundo Chan
core.editor=vim
core.repositoryformatversion=0
core.filemode=true
core.bare=false
core.logallrefupdates=true
remote.origin.url=https://github.com/cs144/sponge
remote.origin.fetch=+refs/heads/*:refs/remotes/origin/*
branch.master.remote=origin
branch.master.merge=refs/heads/master
branch.lab0-startercode.remote=origin
branch.lab0-startercode.merge=refs/heads/lab0-startercode
branch.lab1-startercode.remote=origin
branch.lab1-startercode.merge=refs/heads/lab1-startercode
branch.lab2-startercode.remote=origin
branch.lab2-startercode.merge=refs/heads/lab2-startercode

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

Lab Checkpoint 0: networking warmup

2.1 Fetch a Web page

$ telnet cs144.keithw.org http
Trying 104.196.238.229...
Connected to cs144.keithw.org.
Escape character is '^]'.

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

GET /hello HTTP/1.1
Host: cs144.keithw.org
Connection: close

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

可能出现下面的错误：

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.

nameserver 8.8.8.8

3.4 Writing webget

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

// 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

    ...
}

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 了。

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;
        _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应该选择与上次值最为接近的那一个)

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；

• 2. 使用StreamReassembler重新组装ByteStream

  3. 维护确认号(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.

void TCPReceiver::segment_received(const TCPSegment &seg) {
    bool is_init = false;

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

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

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

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

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

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

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

cs144@cs144vm:~/sponge/build$ make check_lab2
[100%] Testing the TCP receiver...
Test project /home/cs144/sponge/build
      Start  1: t_wrapping_ints_cmp
 1/26 Test  #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
      Start  2: t_wrapping_ints_unwrap
 2/26 Test  #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
      Start  3: t_wrapping_ints_wrap
 3/26 Test  #3: t_wrapping_ints_wrap .............   Passed    0.00 sec
      Start  4: t_wrapping_ints_roundtrip
 4/26 Test  #4: t_wrapping_ints_roundtrip ........   Passed    0.06 sec
      Start  5: t_recv_connect
 5/26 Test  #5: t_recv_connect ...................   Passed    0.00 sec
      Start  6: t_recv_transmit
 6/26 Test  #6: t_recv_transmit ..................   Passed    0.03 sec
      Start  7: t_recv_window
 7/26 Test  #7: t_recv_window ....................   Passed    0.00 sec
      Start  8: t_recv_reorder
 8/26 Test  #8: t_recv_reorder ...................   Passed    0.00 sec
      Start  9: t_recv_close
 9/26 Test  #9: t_recv_close .....................   Passed    0.00 sec
      Start 10: t_recv_special
10/26 Test #10: t_recv_special ...................   Passed    0.00 sec
      Start 18: t_strm_reassem_single
11/26 Test #18: t_strm_reassem_single ............   Passed    0.00 sec
      Start 19: t_strm_reassem_seq
12/26 Test #19: t_strm_reassem_seq ...............   Passed    0.00 sec
      Start 20: t_strm_reassem_dup
13/26 Test #20: t_strm_reassem_dup ...............   Passed    0.00 sec
      Start 21: t_strm_reassem_holes
14/26 Test #21: t_strm_reassem_holes .............   Passed    0.00 sec
      Start 22: t_strm_reassem_many
15/26 Test #22: t_strm_reassem_many ..............   Passed    0.05 sec
      Start 23: t_strm_reassem_overlapping
16/26 Test #23: t_strm_reassem_overlapping .......   Passed    0.00 sec
      Start 24: t_strm_reassem_win
17/26 Test #24: t_strm_reassem_win ...............   Passed    0.05 sec
      Start 25: t_strm_reassem_cap
18/26 Test #25: t_strm_reassem_cap ...............   Passed    0.05 sec
      Start 26: t_byte_stream_construction
19/26 Test #26: t_byte_stream_construction .......   Passed    0.00 sec
      Start 27: t_byte_stream_one_write
20/26 Test #27: t_byte_stream_one_write ..........   Passed    0.00 sec
      Start 28: t_byte_stream_two_writes
21/26 Test #28: t_byte_stream_two_writes .........   Passed    0.00 sec
      Start 29: t_byte_stream_capacity
22/26 Test #29: t_byte_stream_capacity ...........   Passed    0.23 sec
      Start 30: t_byte_stream_many_writes
23/26 Test #30: t_byte_stream_many_writes ........   Passed    0.00 sec
      Start 53: t_address_dt
24/26 Test #53: t_address_dt .....................   Passed    0.00 sec
      Start 54: t_parser_dt
25/26 Test #54: t_parser_dt ......................   Passed    0.00 sec
      Start 55: t_socket_dt
26/26 Test #55: t_socket_dt ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 26

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

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

with_syn().with_seqno(5).with_fin()
SYN received (ackno exists), and input to stream hasn't ended

seqno	2303251161	2303251162	2303251163	2303251164	2303251165	2303251166	2303251167	2303251168	2303251169
						e
								g
				c
		a	b
							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).

//! \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.

//! \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

//! \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.

//! \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.

//! \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

cd build
make -j8
ctest -R send_

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

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)

31% tests passed, 112 tests failed out of 162

Total Test time (real) = 395.44 sec

The following tests FAILED:
         36 - t_active_close (Failed)
         37 - t_passive_close (Failed)
         43 - t_connect (Failed)
         45 - t_listen (Failed)
         48 - t_retx (Failed)
         49 - t_retx_win (Failed)
         50 - t_loopback (Failed)
         51 - t_loopback_win (Failed)
         56 - t_udp_client_send (Failed)
         57 - t_udp_server_send (Failed)
         58 - t_udp_client_recv (Failed)
         59 - t_udp_server_recv (Failed)
         60 - t_udp_client_dupl (Failed)
         61 - t_udp_server_dupl (Failed)
         62 - t_ucS_1M_32k (Failed)
         63 - t_ucS_128K_8K (Failed)
         64 - t_ucS_16_1 (Failed)
         65 - t_ucS_32K_d (Failed)
         66 - t_ucR_1M_32k (Failed)
         67 - t_ucR_128K_8K (Failed)
         68 - t_ucR_16_1 (Failed)
         69 - t_ucR_32K_d (Failed)
         70 - t_ucD_1M_32k (Failed)
         71 - t_ucD_128K_8K (Failed)
         72 - t_ucD_16_1 (Failed)
         73 - t_ucD_32K_d (Failed)
         74 - t_usS_1M_32k (Failed)
         75 - t_usS_128K_8K (Failed)
         76 - t_usS_16_1 (Failed)
         77 - t_usS_32K_d (Failed)
         78 - t_usR_1M_32k (Failed)
         79 - t_usR_128K_8K (Failed)
         80 - t_usR_16_1 (Failed)
         81 - t_usR_32K_d (Failed)
         82 - t_usD_1M_32k (Failed)
         83 - t_usD_128K_8K (Failed)
         84 - t_usD_16_1 (Failed)
         85 - t_usD_32K_d (Failed)
         86 - t_ucS_128K_8K_l (Failed)
         87 - t_ucS_128K_8K_L (Failed)
         88 - t_ucS_128K_8K_lL (Failed)
         89 - t_ucR_128K_8K_l (Failed)
         90 - t_ucR_128K_8K_L (Failed)
         91 - t_ucR_128K_8K_lL (Failed)
         92 - t_ucD_128K_8K_l (Failed)
         93 - t_ucD_128K_8K_L (Failed)
         94 - t_ucD_128K_8K_lL (Failed)
         95 - t_usS_128K_8K_l (Failed)
         96 - t_usS_128K_8K_L (Failed)
         97 - t_usS_128K_8K_lL (Failed)
         98 - t_usR_128K_8K_l (Failed)
         99 - t_usR_128K_8K_L (Failed)
        100 - t_usR_128K_8K_lL (Failed)
        101 - t_usD_128K_8K_l (Failed)
        102 - t_usD_128K_8K_L (Failed)
        103 - t_usD_128K_8K_lL (Failed)
        104 - t_ipv4_client_send (Failed)
        105 - t_ipv4_server_send (Failed)
        106 - t_ipv4_client_recv (Failed)
        107 - t_ipv4_server_recv (Failed)
        108 - t_ipv4_client_dupl (Failed)
        109 - t_ipv4_server_dupl (Failed)
        110 - t_icS_1M_32k (Failed)
        111 - t_icS_128K_8K (Failed)
        112 - t_icS_16_1 (Failed)
        113 - t_icS_32K_d (Failed)
        114 - t_icR_1M_32k (Failed)
        115 - t_icR_128K_8K (Failed)
        116 - t_icR_16_1 (Failed)
        117 - t_icR_32K_d (Failed)
        118 - t_icD_1M_32k (Failed)
        119 - t_icD_128K_8K (Failed)
        120 - t_icD_16_1 (Failed)
        121 - t_icD_32K_d (Failed)
        122 - t_isS_1M_32k (Failed)
        123 - t_isS_128K_8K (Failed)
        124 - t_isS_16_1 (Failed)
        125 - t_isS_32K_d (Failed)
        126 - t_isR_1M_32k (Failed)
        127 - t_isR_128K_8K (Failed)
        128 - t_isR_16_1 (Failed)
        129 - t_isR_32K_d (Failed)
        130 - t_isD_1M_32k (Failed)
        131 - t_isD_128K_8K (Failed)
        132 - t_isD_16_1 (Failed)
        133 - t_isD_32K_d (Failed)
        134 - t_icS_128K_8K_l (Failed)
        135 - t_icS_128K_8K_L (Failed)
        136 - t_icS_128K_8K_lL (Failed)
        137 - t_icR_128K_8K_l (Failed)
        138 - t_icR_128K_8K_L (Failed)
        139 - t_icR_128K_8K_lL (Failed)
        140 - t_icD_128K_8K_l (Failed)
        141 - t_icD_128K_8K_L (Failed)
        142 - t_icD_128K_8K_lL (Failed)
        143 - t_isS_128K_8K_l (Failed)
        144 - t_isS_128K_8K_L (Failed)
        145 - t_isS_128K_8K_lL (Failed)
        146 - t_isR_128K_8K_l (Failed)
        147 - t_isR_128K_8K_L (Failed)
        148 - t_isR_128K_8K_lL (Failed)
        149 - t_isD_128K_8K_l (Failed)
        150 - t_isD_128K_8K_L (Failed)
        151 - t_isD_128K_8K_lL (Timeout)
        153 - t_icnS_128K_8K_L (Timeout)
        154 - t_icnS_128K_8K_lL (Timeout)
        159 - t_icnD_128K_8K_L (Timeout)
        160 - t_icnD_128K_8K_lL (Timeout)
        162 - t_isnS_128K_8K_L (Timeout)
        163 - t_isnS_128K_8K_lL (Timeout)
        168 - t_isnD_128K_8K_L (Timeout)
        169 - t_isnD_128K_8K_lL (Timeout)

(segments_out) + [ack=0, seqno=0]
(segments_out) + [ack=0, seqno=1]
(segments_out) + [ack=0, seqno=1]
(segments_out) + [ack=0, seqno=2]
(segments_out) + [ack=0, seqno=2]
(segments_out) + [ack=0, seqno=2]
Test Failure on expectation:
        Expectation: exactly one segment sent with (A=1,ackno=2,)

Failure message:
        The TCP produced a segment with `ackno = 1`, but ackno was expected to be `2`

List of steps that executed successfully:
        Action:      connect
        Expectation: exactly one segment sent with (A=0,R=0,S=1,F=0,seqno=0,payload_size=0,)
        Action:      packet arrives: Header(flags=SA,seqno=0,ack=1,win=137) with no payload
        Expectation: exactly one segment sent with (A=1,R=0,S=0,F=0,ackno=1,payload_size=0,)
        Action:      close
        Expectation: exactly one segment sent with (A=1,R=0,S=0,F=1,ackno=1,seqno=1,)
        Action:      packet arrives: Header(flags=A,seqno=1,ack=2,win=137) with no payload
        Action:      4000ms pass
        Expectation: TCP in state sender=`stream finished and fully acknowledged`, receiver=`SYN received (ackno exists), and input to stream hasn't ended`, active=1, linger_after_streams_finish=1
        Action:      packet arrives: Header(flags=AF,seqno=1,ack=2,win=137) with no payload
        Action:      1ms pass

Note:
        test 3 failed: wrong ACK for FIN

Warning: Unclean shutdown of TCPConnection
(segments_out) + [ack=0, seqno=2]
The TCP produced a segment with `ackno = 1`, but ackno was expected to be `2`

146/162 Test #153: t_icnS_128K_8K_L .................   Passed    0.41 sec
        Start 154: t_icnS_128K_8K_lL
147/162 Test #154: t_icnS_128K_8K_lL ................   Passed    0.44 sec
        Start 155: t_icnR_128K_8K_l
148/162 Test #155: t_icnR_128K_8K_l .................   Passed    0.88 sec
        Start 156: t_icnR_128K_8K_L
149/162 Test #156: t_icnR_128K_8K_L .................   Passed    0.26 sec
        Start 157: t_icnR_128K_8K_lL
150/162 Test #157: t_icnR_128K_8K_lL ................   Passed    0.59 sec
        Start 158: t_icnD_128K_8K_l
151/162 Test #158: t_icnD_128K_8K_l .................   Passed    0.74 sec
        Start 159: t_icnD_128K_8K_L
152/162 Test #159: t_icnD_128K_8K_L .................   Passed    0.39 sec
        Start 160: t_icnD_128K_8K_lL
153/162 Test #160: t_icnD_128K_8K_lL ................***Timeout  10.01 sec
DEBUG: Connecting to 169.254.144.1:23365... done.
DEBUG: Outbound stream to 169.254.144.1:23365 finished (63000 bytes still in flight).
DEBUG: Outbound stream to 169.254.144.1:23365 has been fully acknowledged.
DEBUG: Inbound stream from 169.254.144.1:23365 finished cleanly.
DEBUG: Waiting for lingering segments (e.g. retransmissions of FIN) from peer...

        Start 161: t_isnS_128K_8K_l
154/162 Test #161: t_isnS_128K_8K_l .................   Passed    0.13 sec
        Start 162: t_isnS_128K_8K_L
155/162 Test #162: t_isnS_128K_8K_L .................   Passed    0.29 sec
        Start 163: t_isnS_128K_8K_lL
156/162 Test #163: t_isnS_128K_8K_lL ................   Passed    0.28 sec
        Start 164: t_isnR_128K_8K_l
157/162 Test #164: t_isnR_128K_8K_l .................   Passed    0.84 sec
        Start 165: t_isnR_128K_8K_L
158/162 Test #165: t_isnR_128K_8K_L .................   Passed    0.26 sec
        Start 166: t_isnR_128K_8K_lL
159/162 Test #166: t_isnR_128K_8K_lL ................***Timeout  10.01 sec
DEBUG: Listening for incoming connection... new connection from 169.254.144.1:37094.
DEBUG: Outbound stream to 169.254.144.1:37094 finished (1 byte still in flight).
DEBUG: Outbound stream to 169.254.144.1:37094 has been fully acknowledged.
DEBUG: Inbound stream from 169.254.144.1:37094 finished cleanly.
DEBUG: Waiting for lingering segments (e.g. retransmissions of FIN) from peer...

        Start 167: t_isnD_128K_8K_l
160/162 Test #167: t_isnD_128K_8K_l .................   Passed    0.92 sec
        Start 168: t_isnD_128K_8K_L
161/162 Test #168: t_isnD_128K_8K_L .................   Passed    0.29 sec
        Start 169: t_isnD_128K_8K_lL
162/162 Test #169: t_isnD_128K_8K_lL ................   Passed    0.90 sec

83% tests passed, 28 tests failed out of 162

Total Test time (real) = 311.01 sec

The following tests FAILED:
         87 - t_ucS_128K_8K_L (Timeout)
         88 - t_ucS_128K_8K_lL (Timeout)
         89 - t_ucR_128K_8K_l (Timeout)
         91 - t_ucR_128K_8K_lL (Timeout)
         92 - t_ucD_128K_8K_l (Timeout)
         93 - t_ucD_128K_8K_L (Timeout)
         94 - t_ucD_128K_8K_lL (Timeout)
         96 - t_usS_128K_8K_L (Timeout)
         97 - t_usS_128K_8K_lL (Timeout)
         98 - t_usR_128K_8K_l (Timeout)
        100 - t_usR_128K_8K_lL (Timeout)
        101 - t_usD_128K_8K_l (Timeout)
        103 - t_usD_128K_8K_lL (Timeout)
        135 - t_icS_128K_8K_L (Timeout)
        136 - t_icS_128K_8K_lL (Timeout)
        137 - t_icR_128K_8K_l (Timeout)
        139 - t_icR_128K_8K_lL (Timeout)
        140 - t_icD_128K_8K_l (Timeout)
        141 - t_icD_128K_8K_L (Timeout)
        142 - t_icD_128K_8K_lL (Timeout)
        145 - t_isS_128K_8K_lL (Timeout)
        146 - t_isR_128K_8K_l (Timeout)
        148 - t_isR_128K_8K_lL (Timeout)
        149 - t_isD_128K_8K_l (Timeout)
        150 - t_isD_128K_8K_L (Timeout)
        151 - t_isD_128K_8K_lL (Timeout)
        160 - t_icnD_128K_8K_lL (Timeout)
        166 - t_isnR_128K_8K_lL (Timeout)
Errors while running CTest
make[3]: *** [CMakeFiles/check_lab4.dir/build.make:59: CMakeFiles/check_lab4] Error 8
make[2]: *** [CMakeFiles/Makefile2:382: CMakeFiles/check_lab4.dir/all] Error 2
make[1]: *** [CMakeFiles/Makefile2:389: CMakeFiles/check_lab4.dir/rule] Error 2
make: *** [Makefile:181: check_lab4] Error 2

(7192 bytes still in flight). X
_receiver.unassembled_bytes()

157/162 Test #164: t_isnR_128K_8K_l .................   Passed    0.54 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.71 sec
        Start 167: t_isnD_128K_8K_l
160/162 Test #167: t_isnD_128K_8K_l .................   Passed    0.64 sec
        Start 168: t_isnD_128K_8K_L
161/162 Test #168: t_isnD_128K_8K_L .................   Passed    0.27 sec
        Start 169: t_isnD_128K_8K_lL
162/162 Test #169: t_isnD_128K_8K_lL ................   Passed    0.73 sec

99% tests passed, 1 tests failed out of 162

Total Test time (real) =  51.64 sec

The following tests FAILED:
        155 - t_icnR_128K_8K_l (Timeout)

cs144@cs144vm:~/sponge/build$ ./apps/tcp_benchmark
CPU-limited throughput                : 1.14 Gbit/s
CPU-limited throughput with reordering: 0.87 Gbit/s

83 - t_usD_128K_8K (Timeout)
92 - t_ucD_128K_8K_l (Timeout)

root@cs144vm:/home/cs144/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.05 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.05 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.26 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    0.93 sec
        Start  34: t_tcp_parser
 32/162 Test  #34: t_tcp_parser .....................   Passed    0.02 sec
        Start  35: t_ipv4_parser
 33/162 Test  #35: t_ipv4_parser ....................   Passed    0.01 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.03 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.10 sec
        Start  51: t_loopback_win
 44/162 Test  #51: t_loopback_win ...................   Passed    0.06 sec
        Start  52: t_reorder
 45/162 Test  #52: t_reorder ........................   Passed    0.11 sec
        Start  53: t_address_dt
 46/162 Test  #53: t_address_dt .....................   Passed    0.01 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.24 sec
        Start  60: t_udp_client_dupl
 53/162 Test  #60: t_udp_client_dupl ................   Passed    0.26 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.27 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.27 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.25 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.27 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.30 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.29 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.26 sec
        Start  87: t_ucS_128K_8K_L
 80/162 Test  #87: t_ucS_128K_8K_L ..................   Passed    0.45 sec
        Start  88: t_ucS_128K_8K_lL
 81/162 Test  #88: t_ucS_128K_8K_lL .................   Passed    0.51 sec
        Start  89: t_ucR_128K_8K_l
 82/162 Test  #89: t_ucR_128K_8K_l ..................   Passed    0.61 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.70 sec
        Start  92: t_ucD_128K_8K_l
 85/162 Test  #92: t_ucD_128K_8K_l ..................   Passed    0.45 sec
        Start  93: t_ucD_128K_8K_L
 86/162 Test  #93: t_ucD_128K_8K_L ..................   Passed    0.47 sec
        Start  94: t_ucD_128K_8K_lL
 87/162 Test  #94: t_ucD_128K_8K_lL .................   Passed    0.58 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.37 sec
        Start  97: t_usS_128K_8K_lL
 90/162 Test  #97: t_usS_128K_8K_lL .................   Passed    0.43 sec
        Start  98: t_usR_128K_8K_l
 91/162 Test  #98: t_usR_128K_8K_l ..................   Passed    0.37 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.49 sec
        Start 101: t_usD_128K_8K_l
 94/162 Test #101: t_usD_128K_8K_l ..................   Passed    0.41 sec
        Start 102: t_usD_128K_8K_L
 95/162 Test #102: t_usD_128K_8K_L ..................   Passed    0.41 sec
        Start 103: t_usD_128K_8K_lL
 96/162 Test #103: t_usD_128K_8K_lL .................   Passed    0.61 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.25 sec
        Start 110: t_icS_1M_32k
103/162 Test #110: t_icS_1M_32k .....................   Passed    0.30 sec
        Start 111: t_icS_128K_8K
104/162 Test #111: t_icS_128K_8K ....................   Passed    0.25 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.29 sec
        Start 115: t_icR_128K_8K
108/162 Test #115: t_icR_128K_8K ....................   Passed    0.25 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.33 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.24 sec
        Start 126: t_isR_1M_32k
119/162 Test #126: t_isR_1M_32k .....................   Passed    0.30 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.33 sec
        Start 131: t_isD_128K_8K
124/162 Test #131: t_isD_128K_8K ....................   Passed    0.26 sec
        Start 132: t_isD_16_1
125/162 Test #132: t_isD_16_1 .......................   Passed    0.25 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.47 sec
        Start 136: t_icS_128K_8K_lL
129/162 Test #136: t_icS_128K_8K_lL .................   Passed    0.48 sec
        Start 137: t_icR_128K_8K_l
130/162 Test #137: t_icR_128K_8K_l ..................   Passed    0.49 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.53 sec
        Start 140: t_icD_128K_8K_l
133/162 Test #140: t_icD_128K_8K_l ..................   Passed    0.48 sec
        Start 141: t_icD_128K_8K_L
134/162 Test #141: t_icD_128K_8K_L ..................   Passed    0.40 sec
        Start 142: t_icD_128K_8K_lL
135/162 Test #142: t_icD_128K_8K_lL .................   Passed    0.61 sec
        Start 143: t_isS_128K_8K_l
136/162 Test #143: t_isS_128K_8K_l ..................   Passed    0.27 sec
        Start 144: t_isS_128K_8K_L
137/162 Test #144: t_isS_128K_8K_L ..................   Passed    0.48 sec
        Start 145: t_isS_128K_8K_lL
138/162 Test #145: t_isS_128K_8K_lL .................   Passed    0.33 sec
        Start 146: t_isR_128K_8K_l
139/162 Test #146: t_isR_128K_8K_l ..................   Passed    0.41 sec
        Start 147: t_isR_128K_8K_L
140/162 Test #147: t_isR_128K_8K_L ..................   Passed    0.25 sec
        Start 148: t_isR_128K_8K_lL
141/162 Test #148: t_isR_128K_8K_lL .................   Passed    1.01 sec
        Start 149: t_isD_128K_8K_l
142/162 Test #149: t_isD_128K_8K_l ..................   Passed    0.41 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.13 sec
        Start 153: t_icnS_128K_8K_L
146/162 Test #153: t_icnS_128K_8K_L .................   Passed    0.43 sec
        Start 154: t_icnS_128K_8K_lL
147/162 Test #154: t_icnS_128K_8K_lL ................   Passed    0.29 sec
        Start 155: t_icnR_128K_8K_l
148/162 Test #155: t_icnR_128K_8K_l .................   Passed    0.94 sec
        Start 156: t_icnR_128K_8K_L
149/162 Test #156: t_icnR_128K_8K_L .................   Passed    0.24 sec
        Start 157: t_icnR_128K_8K_lL
150/162 Test #157: t_icnR_128K_8K_lL ................   Passed    1.30 sec
        Start 158: t_icnD_128K_8K_l
151/162 Test #158: t_icnD_128K_8K_l .................   Passed    0.32 sec
        Start 159: t_icnD_128K_8K_L
152/162 Test #159: t_icnD_128K_8K_L .................   Passed    0.29 sec
        Start 160: t_icnD_128K_8K_lL
153/162 Test #160: t_icnD_128K_8K_lL ................   Passed    0.53 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.37 sec
        Start 163: t_isnS_128K_8K_lL
156/162 Test #163: t_isnS_128K_8K_lL ................   Passed    0.54 sec
        Start 164: t_isnR_128K_8K_l
157/162 Test #164: t_isnR_128K_8K_l .................   Passed    0.59 sec
        Start 165: t_isnR_128K_8K_L
158/162 Test #165: t_isnR_128K_8K_L .................   Passed    0.26 sec
        Start 166: t_isnR_128K_8K_lL
159/162 Test #166: t_isnR_128K_8K_lL ................   Passed    1.77 sec
        Start 167: t_isnD_128K_8K_l
160/162 Test #167: t_isnD_128K_8K_l .................   Passed    0.96 sec
        Start 168: t_isnD_128K_8K_L
161/162 Test #168: t_isnD_128K_8K_L .................   Passed    0.27 sec
        Start 169: t_isnD_128K_8K_lL
162/162 Test #169: t_isnD_128K_8K_lL ................   Passed    0.54 sec

100% tests passed, 0 tests failed out of 162

Total Test time (real) =  42.82 sec
[100%] Built target check_lab4

-> BufferList

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

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

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.

参考

1. 以 100Gbps 的传输速度计算，需要接近 50 年的时间才能达到 (2^{64}) bytes 的数据量；作为对比，只需要约 (1/3) 秒即可达到 (2^{32}) bytes 的数据量。 ↩︎