该课程主要的作业是自己使用c++实现一个tcp，能够加深对计网的理解。记录解决lab的过程。

目录

环境搭建LAB0Networking by handFetch a web pageSend yourself an emailListening and connecting Writing a network program using an OS stream socketWriting webgetAn in-memory reliable byte stream注意 LAB1：stitching substrings into a byte stream对于StreamReassembler的理解调试方法论 lab2：the TCP receiver开始之前任务一：Translating between 64-bit indexes and 32-bit seqnos任务二：Implementing the TCP receiver LAB3：the TCP sender参考

环境搭建

开始时，我使用的是ubuntu16.04，apt下载的gcc版本较低，中间make编译时发现gcc要求8+（lab0的pdf也明确说明），装了半天没成功于是又装了一个ubuntu20.04。之后参考课程网站lab0的pdf，在git上clone项目即可开始实验。

LAB0

Networking by hand

Fetch a web page

使用telnet 发送http（命令中http换成80也是可以的)请求，需要注意的最后一行需要输入一个回车。

Send yourself an email

可以尝试使用国内的邮箱，稍微比文档中的要麻烦一些。

Listening and connecting

略

Writing a network program using an OS stream socket

本次lab的核心，分别是实现一个get_URL函数以及完成一个字节流控制类，在开始之前，最好仔细读一下PDF。有详细的文档、作业要求以及对于C++的使用有一些要求。

Writing webget

实现webget，这是一个使用操作系统的TCP支持和流套接字抽象在Internet上提取网页的程序，就像上面使用telnet进行的操作一样。 webget.cc

void get_URL(const string &host, const string &path) { TCPSocket tcpSocket; tcpSocket.connect(Address("cs144.keithw.org", "http")); tcpSocket.write("GET " + path + " HTTP/1.1\r\nHost: " + host + "\r\n\r\n"); string response; while (tcpSocket.eof() == false) { response = tcpSocket.read(); cout << response; } tcpSocket.close(); }

An in-memory reliable byte stream

实现一个有序字节流类，按最大努力交付。 byte_stream.cc

#include "byte_stream.hh" // Dummy implementation of a flow-controlled in-memory byte stream. // For Lab 0, please replace with a real implementation that passes the // automated checks run by `make check_lab0`. // You will need to add private members to the class declaration in `byte_stream.hh` template <typename... Targs> void DUMMY_CODE(Targs &&... /* unused */) {} using namespace std; ByteStream::ByteStream(const size_t capacity):_capacity(capacity) {} size_t ByteStream::write(const string &data) { size_t len = data.size(); if (_capacity - _buffer.size() < len) len = _capacity - _buffer.size(); for (size_t i = 0; i < len; i++) _buffer.push_back(data[i]); _bytes_write += len; return len; } //! \param[in] len bytes will be copied from the output side of the buffer string ByteStream::peek_output(const size_t len) const { size_t length = len; if (length > _buffer.size()) length = _buffer.size(); return string().assign(_buffer.begin(), _buffer.begin() + length); } //! \param[in] len bytes will be removed from the output side of the buffer void ByteStream::pop_output(const size_t len) { size_t length = len; if (length > _buffer.size()) length = _buffer.size(); _bytes_read += length; while (length--) _buffer.pop_front(); return; } //! 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) { string ans{}; ans = peek_output(len); pop_output(len); return ans; } void ByteStream::end_input() { _end_input = true; } bool ByteStream::input_ended() const { return _end_input; } size_t ByteStream::buffer_size() const { return _buffer.size(); } bool ByteStream::buffer_empty() const { return (_buffer.size() == 0? true: false); } bool ByteStream::eof() const { return (_end_input == true) && (_buffer.size()==0); } size_t ByteStream::bytes_written() const { return _bytes_write; } size_t ByteStream::bytes_read() const { return _bytes_read; } size_t ByteStream::remaining_capacity() const { return _capacity - _buffer.size(); }

byte_stream.hh仅仅贴出类的private域。

class ByteStream { private: size_t _capacity = 0; deque<char> _buffer{}; bool _end_input = false; size_t _bytes_read = 0; size_t _bytes_write = 0; // Your code here -- add private members as necessary. // Hint: This doesn't need to be a sophisticated data structure at // all, but if any of your tests are taking longer than a second, // that's a sign that you probably want to keep exploring // different approaches. bool _error{}; //!< Flag indicating that the stream suffered an error. }

注意

在byte_stream.c的代码中下行代码 bool ByteStream::eof() const { return (_end_input == true) && (_buffer.size()==0); } 判断条件最初我写成了return (_end_input == true) ;无法通过3个样例，仔细分析，实际上如果发送方设置了_end_input = true,然后接收方不仅仅查看到_end_input，也需要流中没有数据才可以判断读到了eof。同时对于发送数据的长度和buffer以及buffer的最大长度的处理判断，也正考虑到了题目要求的尽最大努力交付。实现中使用deque实现，实际上vector、字符串等等都可以实现。

LAB1：stitching substrings into a byte stream

根据任务描述，实现一个流重组器，将子串按序列重组。对于题目主要的限制capacity，在byteStream和StreamReassembler中，可以理解成窗口。即重组器中流（byteStream中暂未read)的和StreamReassembler中暂未重组，二者之和，长度要小于等于capacity。如果嫌命令行GDB调试麻烦，可以参考我下面一节说的。 流程图如下：对于head_index和eof的维护等细节没标识出。 代码如下： stream_reassembler.hh

#ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH #define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH #include "byte_stream.hh" #include <iostream> #include <cstdint> #include <string> #include <set> //! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order, //! possibly overlapping) into an in-order byte stream. class StreamReassembler { private: // Your code here -- add private members as necessary. std::set<pair<uint64_t, string> > _blocks{}; size_t _unassembled_bytes = 0; size_t _head_index = 0; bool _eof{false}; ByteStream _output; //!< The reassembled in-order byte stream size_t _capacity; //!< The maximum number of bytes pair<uint64_t, string> merge_node(pair<uint64_t, string> a, pair<uint64_t, string> b); public: //! \brief Construct a `StreamReassembler` that will store up to `capacity` bytes. //! \note This capacity limits both the bytes that have been reassembled, //! and those that have not yet been reassembled. StreamReassembler(const size_t capacity); //! \brief Receive a substring and write any newly contiguous bytes into the stream. //! //! The StreamReassembler will stay within the memory limits of the `capacity`. //! Bytes that would exceed the capacity are silently discarded. //! //! \param data the substring //! \param index indicates the index (place in sequence) of the first byte in `data` //! \param eof the last byte of `data` will be the last byte in the entire stream void push_substring(const std::string &data, const uint64_t index, const bool eof); //! \name Access the reassembled byte stream //!@{ const ByteStream &stream_out() const { return _output; } ByteStream &stream_out() { return _output; } //!@} //! The number of bytes in the substrings stored but not yet reassembled //! //! \note If the byte at a particular index has been pushed more than once, it //! should only be counted once for the purpose of this function. size_t unassembled_bytes() const; //! \brief Is the internal state empty (other than the output stream)? //! \returns `true` if no substrings are waiting to be assembled bool empty() const; }; #endif // SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH

stream_reassembler.cc

#include "stream_reassembler.hh" // Dummy implementation of a stream reassembler. // For Lab 1, please replace with a real implementation that passes the // automated checks run by `make check_lab1`. // You will need to add private members to the class declaration in `stream_reassembler.hh` template <typename... Targs> void DUMMY_CODE(Targs &&... /* unused */) {} using namespace std; pair<uint64_t, string> StreamReassembler::merge_node(pair<uint64_t, string> a, pair<uint64_t, string> b){ pair<uint64_t, string> ans; ans.first = a.first; if (a.first + a.second.size() < b.first + b.second.size()) ans.second = a.second.substr(0, b.first - a.first) + b.second; else ans.second = a.second; return ans; } StreamReassembler::StreamReassembler(const size_t capacity) : _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) { //完全超出窗口 if (index >= _head_index + _output.remaining_capacity()) return; pair<uint64_t, string> a{index, data}; //裁剪超出窗口的 if (a.first + a.second.size() > _head_index + _output.remaining_capacity()) { a.second = a.second.substr(0, _head_index + _output.remaining_capacity() - a.first); } else { if (eof == true) _eof = eof; } int flag = 1; //裁剪已经排序完成的前缀 if (index < _head_index) { if (index + data.size() > _head_index) { a.first = _head_index; a.second = data.substr(_head_index - index); } else { flag = 0; } } if (a.second.size() == 0) flag = 0; if (flag) { while (1) { if (empty()) break; //防止it段错误 auto it = _blocks.lower_bound(a); if (it == _blocks.end()) break; if (a.first + a.second.size() >= it->first) { a = merge_node(a, *it); _unassembled_bytes -= it->second.size(); _blocks.erase(*it); } else { break; } } while (1) { if (empty()) break; //防止it段错误 auto it = _blocks.lower_bound(a); if (it == _blocks.begin()) break; it--; if (it->first + it->second.size() >= a.first) { a = merge_node(*it, a); _unassembled_bytes -= it->second.size(); _blocks.erase(*it); } else { break; } } _blocks.insert(a); _unassembled_bytes += a.second.size(); } auto it = _blocks.begin(); if (it != _blocks.end()) { a = *it; if (a.first <= _head_index) { _blocks.erase(*it); _unassembled_bytes -= a.second.size(); size_t writen_len = _output.write(a.second); if (writen_len != a.second.size()) { a.first += writen_len; a.second = a.second.substr(writen_len); _head_index = a.first; _blocks.insert(a); _unassembled_bytes += a.second.size(); } else { _head_index = a.first + a.second.size(); } } } if (empty() && _eof) _output.end_input(); return; } size_t StreamReassembler::unassembled_bytes() const { return {_unassembled_bytes}; } bool StreamReassembler::empty() const { return {_unassembled_bytes == 0}; }

对于StreamReassembler的理解

在按照文档要求完成lab1之后，对于StreamReassemblerStream和ByteStream这两个类的关系还感觉很模糊，再做完了lab2之后，应该是对lab1有一个清晰的认识了。ByteStream可以看作是StreamReassemblerStream+1个buffer（缓存数组），在红黑树中前缀重组完成的，则放入buffer数组中。从StreamReassemblerStream和ByteStream的最大容量相同可以看出。 同时，对于给定了最大容量capacity，则lab2中的窗口其实就是最大容量（capacity）减去StreamReassemblerStream中已经排序好，但是还没有被最终取走（即在ByteStream中没有被取走)的前缀。

实验中把接受过的字节序列。分成已经排序好的和未排序的分成两个类ByteStream和StreamReassemblerStream完成，感觉弊大于利，容易误解。下面给出一个例子。

例: capacity = 100,ByteStream中buffer长度为5，StreamReassemblerStream中长度为10，这时候，能够接受字符串右边界是多少？

按照ByteStream和StreamReassemblerStream各自维护一个capacity，则还能接受字符串的有边界是(5 + 100) = 105。而实际上，如果把上述两个类看成一个整体来维护滑动窗口，则右边界应该为100。

（上述两种情况在lab1、lab2上可能根据处理细节不同都能跑通，但我认为应该第2种是正确的，因此我简单修改了lab1的代码） 可以参考rookie0080（知乎）的图。

在我按照例上述思想重新修改lab1的代码以后，lab1报错了。这时候一个细节是，如果一次性接受了超过容量的字符串，会进行一次裁剪，但是一旦进行尾步裁剪，就需要把这次调用push_substring函数传入的eof标记给忽略掉，原因很容易想明白。正如文档里说的，样例很弱，真的！

调试方法论

此节参考了【计算机网络】Stanford CS144 学习笔记。 LAB1写了一天多，一度绝望，肉眼实在找不到BUG。GDB命令行用起来又贼难受。参考了该博主的方法之后调试效率大增。通过该博主的大致描述我调试的步骤如下：

步骤 安装vscode以及插件Remote-SSH（以及其他插件比如:C/C++有代码补全功能）通过远程连接虚拟机后，可以设置调试配置文件如下：（比如调试fsm_stream_reassembler_overlapping这个样例） { // Use IntelliSense to learn about possible attributes. // Hover to view descriptions of existing attributes. // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387 "version": "0.2.0", "configurations": [ { "name": "g++-9 - Build and debug active file", "type": "cppdbg", "request": "launch", //"program": "${fileDirname}/../build/tests/${fileBasenameNoExtension}", //"program": "/home/wangqi/cs144/sponge/build/tests/fsm_stream_reassembler_single", "program": "/home/wangqi/cs144/sponge/build/tests/fsm_stream_reassembler_overlapping", //对应要调试的程序 "args": [], "stopAtEntry": false, "cwd": "${workspaceFolder}", "environment": [], "externalConsole": false, "MIMode": "gdb", "setupCommands": [ { "description": "Enable pretty-printing for gdb", "text": "-enable-pretty-printing", "ignoreFailures": true } ], //"preLaunchTask": "C/C++: g++-9 build active file", //注释掉 "miDebuggerPath": "/usr/bin/gdb" } ] } 之后就可以打断点进行调试！（我调试时候发现LAB1中断点打在下图的文件上时调试比较方便）本来打算参考那个博主打在fsm_stream_reassembler_overlapping.cc样例源文件上，但是可能编译时候进行优化了，该代码上的断点经常打不上，而且报错的位置也有问题。

lab2：the TCP receiver

本次lab2完成tcp receiver部分，主要做的事有:

完成几种序号之间的转换处理syn和fin处理seqno返回ack

开始之前

如果编译无法通过，则需要下载下述的包。可以参考Ubuntu下libpcap安装步骤。

任务一：Translating between 64-bit indexes and 32-bit seqnos

在ISN初始序列号一般都是随机的（并非从0开始）。完成64位到32位之间的转换，可以降低在网络上传递数据的位数。64位转32位，直接根据ISN和64位序列号进行一个取模运算即可。而对于32位转64位置。原理如下： 文档中的介绍我任务不够准确，应该说absolute可以是17、17+2³²、17+2³²+2³²、17+2³²+2³²+2³²…，转换规则如下:（红色部分是我的理解） 之后完成题目要求的下面两个函数（即在seqno和streamindex)直接转换。 wrapping_integers.cc

#include "wrapping_integers.hh" // Dummy implementation of a 32-bit wrapping integer // For Lab 2, please replace with a real implementation that passes the // automated checks run by `make check_lab2`. template <typename... Targs> void DUMMY_CODE(Targs &&... /* unused */) {} using namespace std; //! Transform an "absolute" 64-bit sequence number (zero-indexed) into a WrappingInt32 //! \param n The input absolute 64-bit sequence number //! \param isn The initial sequence number WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) { uint32_t ans = 0; ans = (n + isn.raw_value()) % (1LL << 32); return WrappingInt32{ans}; } //! Transform a WrappingInt32 into an "absolute" 64-bit sequence number (zero-indexed) //! \param n The relative sequence number //! \param isn The initial sequence number //! \param checkpoint A recent absolute 64-bit sequence number //! \returns the 64-bit sequence number that wraps to `n` and is closest to `checkpoint` //! //! \note Each of the two streams of the TCP connection has its own ISN. One stream //! runs from the local TCPSender to the remote TCPReceiver and has one ISN, //! and the other stream runs from the remote TCPSender to the local TCPReceiver and //! has a different ISN. uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) { //绝对 n -> 相对ans // ans = n - isn + k*(1ULL << 32) //n - isn + k * (1ULL << 32) 接近 checkpoint ,同时满足ans >= 0 ,求k //即 k * (1ULL << 32) 接近 checkpoint - n + isn ， 求k //cout << " n = " << n.raw_value() << " isn = " << isn.raw_value() << " checkpoint = " << checkpoint << endl; if (checkpoint + static_cast<uint64_t>(isn.raw_value()) < static_cast<uint64_t>(n.raw_value())) { return {static_cast<uint64_t>(n.raw_value()) - isn.raw_value()}; } else { checkpoint = checkpoint - n.raw_value() + isn.raw_value(); uint64_t k = checkpoint / (1ULL << 32); uint64_t r = checkpoint % (1ULL << 32); if(r < ((1ULL << 32) - r)) if (k == 0 && n.raw_value() < isn.raw_value()) return {(1ULL << 32) + n.raw_value() - isn.raw_value()}; else return {k * (1ULL << 32) + n.raw_value() - isn.raw_value()}; else return {(k + 1) * (1ULL << 32) + n.raw_value() - isn.raw_value()}; } }

任务二：Implementing the TCP receiver

完成剩余的任务，这里如果理解了LAB1，那么这节的任务非常容易，（LAB1折磨了我2天，LAB2就写了一下）。 这节我觉得有两个看了文档比较难想明白细节

一个是SYN和FIN虽然占据两个序列号，但是并不会真实的存在于buffer和tcp的数据段中。第二个就是我LAB1最后补充的，window_size窗口指实际上是LAB1中的两个类（公用一个capacity)的容量减去已经在那两个类中但是还没有被read的字节数。

同时，为了获得ack号，需要在前面的stream_reassembler.hh中添加函数，获得_head_index。 代码: stream_reassembler.hh

public: uint64_t getter_head_index() const { return _head_index; }

tcp_receiver.hh

#ifndef SPONGE_LIBSPONGE_TCP_RECEIVER_HH #define SPONGE_LIBSPONGE_TCP_RECEIVER_HH #include "byte_stream.hh" #include "stream_reassembler.hh" #include "tcp_segment.hh" #include "wrapping_integers.hh" #include <optional> //! \brief The "receiver" part of a TCP implementation. //! Receives and reassembles segments into a ByteStream, and computes //! the acknowledgment number and window size to advertise back to the //! remote TCPSender. class TCPReceiver { //! Our data structure for re-assembling bytes. StreamReassembler _reassembler; //! The maximum number of bytes we'll store. size_t _capacity; //0:listen 1:syn_recv 2:fin_recv uint64_t _state = 0; uint32_t _isn = 0; bool _syn = false; bool _fin = false; public: //! \brief Construct a TCP receiver //! //! \param capacity the maximum number of bytes that the receiver will //! store in its buffers at any give time. TCPReceiver(const size_t capacity) : _reassembler(capacity), _capacity(capacity) {} //! \name Accessors to provide feedback to the remote TCPSender //!@{ //! \brief The ackno that should be sent to the peer //! \returns empty if no SYN has been received //! //! This is the beginning of the receiver's window, or in other words, the sequence number //! of the first byte in the stream that the receiver hasn't received. std::optional<WrappingInt32> ackno() const; //! \brief The window size that should be sent to the peer //! //! Operationally: the capacity minus the number of bytes that the //! TCPReceiver is holding in its byte stream (those that have been //! reassembled, but not consumed). //! //! Formally: the difference between (a) the sequence number of //! the first byte that falls after the window (and will not be //! accepted by the receiver) and (b) the sequence number of the //! beginning of the window (the ackno). size_t window_size() const; //!@} //! \brief number of bytes stored but not yet reassembled size_t unassembled_bytes() const { return _reassembler.unassembled_bytes(); } //! \brief handle an inbound segment void segment_received(const TCPSegment &seg); //! \name "Output" interface for the reader //!@{ ByteStream &stream_out() { return _reassembler.stream_out(); } const ByteStream &stream_out() const { return _reassembler.stream_out(); } //!@} }; #endif // SPONGE_LIBSPONGE_TCP_RECEIVER_HH

tcp_receiver.cc

#include "tcp_receiver.hh" // Dummy implementation of a TCP receiver // For Lab 2, please replace with a real implementation that passes the // automated checks run by `make check_lab2`. template <typename... Targs> void DUMMY_CODE(Targs &&... /* unused */) {} using namespace std; void TCPReceiver::segment_received(const TCPSegment &seg) { if (_state == 2) return; //payload中实际上并不包含syn和fin //size_t length_space; //seg 序列长度 //绝对序列号，同时作为下一次seg的checkpoint，用于将相对序列号转换成绝对序列号 //使用abs_seq确定checkpoint实际上,窗口不能太大否则checkpoint不好确定了 static size_t abs_seqno = 0; size_t length = seg.length_in_sequence_space(); if (seg.header().syn == true) { if (_syn == true) //重复建立链接，丢弃 return; _syn = true; _isn = seg.header().seqno.raw_value(); _state = 1; abs_seqno = 1; //记录checkpoint,seg中第一个字节数据的绝对序号 length--; //length_space = seg.length_in_sequence_space() - 1; //序列长度，不包括syn if (seg.length_in_sequence_space() - 1 == 0) //只有syn return; } else if (!_syn) { //尚未建立连接就开始传送数据，丢弃 return; } else { //拆包成绝对地址（64位 初始位是0），同时获得该seg的index abs_seqno = unwrap(WrappingInt32(seg.header().seqno.raw_value()), WrappingInt32(_isn), abs_seqno); //length_space = seg.length_in_sequence_space(); } if (seg.header().fin) length--; // //处理超出窗口的和ackno之前的 if (abs_seqno >= _reassembler.getter_head_index() + 1 + window_size()) return; if (seg.header().fin) _fin = true; // if (abs_seqno + length <= _reassembler.getter_head_index() + 1) // return; //seq syn fin都已经处理。 最后处理payload //abs_seqno -> index _reassembler.push_substring(seg.payload().copy(), abs_seqno - 1, _fin); if (_reassembler.stream_out().input_ended()) _state = 2; return; } optional<WrappingInt32> TCPReceiver::ackno() const { if (_state == 1) { //把64位绝对位置+ISN打包成32位相对位置 //index ->-> abs_seq ->-> seq // +1 wrap return wrap( _reassembler.getter_head_index() + 1, WrappingInt32(_isn)); } else if (_state == 2){ return wrap( _reassembler.getter_head_index() + 2, WrappingInt32(_isn)); } else { return nullopt; } } size_t TCPReceiver::window_size() const { //容量(buffer的最大长度) - 已经重组排好序的部分(buffer_size)，把ressemble理解成对bytetream的一层封装 return { _capacity - _reassembler.stream_out().buffer_size()}; }

LAB3：the TCP sender

本次lab实现一个TCP发送方。lab3的讲义看了3-4遍，最后还是有一个细节一点一点调试才找到。 总体来说虽然样例全过了，但总感觉这次lab写了很多bug。 一些细节：

使用seg.payload() = Buffer(std::move(str));复制数据时候用到了移动，不是很了解还需要进一步学习理解。第一个发送的syn段不能包含数据。_timer在发送第一个包、接受到数据、重传时候置为0。关于重发时重发时间间隔翻倍这个地方。如果是一个试探包（window_size为0时发出的），则重发时间间隔不翻倍。但是，如果是第一个包（syn）始终不能建立连接（此时window_size)，则重发时间间隔需要翻倍（我可以判断重新传的包是否是syn包）。

tcp_sender.hh

#ifndef SPONGE_LIBSPONGE_TCP_SENDER_HH #define SPONGE_LIBSPONGE_TCP_SENDER_HH #include "byte_stream.hh" #include "tcp_config.hh" #include "tcp_segment.hh" #include "wrapping_integers.hh" #include <functional> #include <queue> //! \brief The "sender" part of a TCP implementation. //! Accepts a ByteStream, divides it up into segments and sends the //! segments, keeps track of which segments are still in-flight, //! maintains the Retransmission Timer, and retransmits in-flight //! segments if the retransmission timer expires. class TCPSender { private: //! our initial sequence number, the number for our SYN. WrappingInt32 _isn; //! outbound queue of segments that the TCPSender wants sent std::queue<TCPSegment> _segments_out{}; //! retransmission timer for the connection unsigned int _initial_retransmission_timeout; //! outgoing stream of bytes that have not yet been sent ByteStream _stream; //! the (absolute) sequence number for the next byte to be sent uint64_t _next_seqno{0}; uint64_t _recv_ackno{0}; //已发送但尚未确认的段占用的序号数 uint64_t _bytes_in_flight{0}; unsigned int _retransmission_timeout; bool _time_run{false}; size_t _timer = 0; bool _timer_running = false; bool _syn{}; bool _fin{}; uint16_t _window_size{0}; //跟踪_segments_out（中发送了但是没有被确认的) std::queue<TCPSegment> _outstanding_segments_out{}; //连续重传次数 unsigned int _consecutive_retransmissions{0}; public: //! Initialize a TCPSender TCPSender(const size_t capacity = TCPConfig::DEFAULT_CAPACITY, const uint16_t retx_timeout = TCPConfig::TIMEOUT_DFLT, const std::optional<WrappingInt32> fixed_isn = {}); //! \name "Input" interface for the writer //!@{ ByteStream &stream_in() { return _stream; } const ByteStream &stream_in() const { return _stream; } //!@} //! \name Methods that can cause the TCPSender to send a segment //!@{ //! \brief A new acknowledgment was received void ack_received(const WrappingInt32 ackno, const uint16_t window_size); //! \brief Generate an empty-payload segment (useful for creating empty ACK segments) void send_empty_segment(); //! \brief create and send segments to fill as much of the window as possible void fill_window(); //! \brief Notifies the TCPSender of the passage of time void tick(const size_t ms_since_last_tick); //!@} //! \name Accessors //!@{ //! \brief How many sequence numbers are occupied by segments sent but not yet acknowledged? //! \note count is in "sequence space," i.e. SYN and FIN each count for one byte //! (see TCPSegment::length_in_sequence_space()) size_t bytes_in_flight() const; //! \brief Number of consecutive retransmissions that have occurred in a row unsigned int consecutive_retransmissions() const; //! \brief TCPSegments that the TCPSender has enqueued for transmission. //! \note These must be dequeued and sent by the TCPConnection, //! which will need to fill in the fields that are set by the TCPReceiver //! (ackno and window size) before sending. std::queue<TCPSegment> &segments_out() { return _segments_out; } //!@} //! \name What is the next sequence number? (used for testing) //!@{ //! \brief absolute seqno for the next byte to be sent uint64_t next_seqno_absolute() const { return _next_seqno; } //! \brief relative seqno for the next byte to be sent WrappingInt32 next_seqno() const { return wrap(_next_seqno, _isn); } //!@} }; #endif // SPONGE_LIBSPONGE_TCP_SENDER_HH

tcp_sender.cc

#include "tcp_sender.hh" #include "tcp_config.hh" #include <random> #include <algorithm> #include <iostream> // Dummy implementation of a TCP sender // For Lab 3, please replace with a real implementation that passes the // automated checks run by `make check_lab3`. template <typename... Targs> void DUMMY_CODE(Targs &&... /* unused */) {} using namespace std; //! \param[in] capacity the capacity of the outgoing byte stream //! \param[in] retx_timeout the initial amount of time to wait before retransmitting the oldest outstanding segment //! \param[in] fixed_isn the Initial Sequence Number to use, if set (otherwise uses a random ISN) TCPSender::TCPSender(const size_t capacity, const uint16_t retx_timeout, const std::optional<WrappingInt32> fixed_isn) : _isn(fixed_isn.value_or(WrappingInt32{random_device()()})), _initial_retransmission_timeout{retx_timeout}, _stream(capacity),_retransmission_timeout(retx_timeout) {} //已经发送但是还没有被确认的长度 uint64_t TCPSender::bytes_in_flight() const { return {_bytes_in_flight}; } void TCPSender::fill_window() { TCPSegment seg; if (_syn == false) { //syn段不存数据 seg.header().syn = true; seg.header().seqno = wrap(_next_seqno, _isn); _next_seqno += seg.length_in_sequence_space(); _bytes_in_flight += seg.length_in_sequence_space(); _syn = true; _segments_out.push(seg); _outstanding_segments_out.push(seg); } else { uint64_t window_size = (_window_size == 0 ? 1 : _window_size); uint64_t remain_size; while (!_fin && (remain_size = window_size - (_next_seqno - _recv_ackno)) != 0) { size_t payload_size = min(TCPConfig::MAX_PAYLOAD_SIZE, remain_size); string str = _stream.read(payload_size); seg.payload() = Buffer(std::move(str)); //cout << "length_in_sequence_spac= " << seg.length_in_sequence_space() << " remain_size" << remain_size << endl; if (_stream.eof() && seg.length_in_sequence_space() < remain_size) { seg.header().fin = true; _fin = true; } // stream is empty if (seg.length_in_sequence_space() == 0) break; seg.header().seqno = wrap(_next_seqno, _isn); _next_seqno += seg.length_in_sequence_space(); _bytes_in_flight += seg.length_in_sequence_space(); _segments_out.push(seg); _outstanding_segments_out.push(seg); } } //cout << "fill_window中的seqno为：" << seg.header().seqno << endl; if (_time_run == false) { _time_run = true; _timer = 0; } return; } //! \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) { //cout << "ack_received中的ackno为：" << ackno.raw_value() << endl; size_t abs_ackno = unwrap(ackno, _isn, _recv_ackno); _window_size = window_size; if (abs_ackno <= _recv_ackno) return; _recv_ackno = abs_ackno; TCPSegment seg; while (!_outstanding_segments_out.empty()) { seg = _outstanding_segments_out.front(); if (unwrap(seg.header().seqno, _isn, _recv_ackno) + seg.length_in_sequence_space() <= abs_ackno) { _bytes_in_flight -= seg.length_in_sequence_space(); _outstanding_segments_out.pop(); } else { break; } } fill_window(); _retransmission_timeout = _initial_retransmission_timeout; _consecutive_retransmissions = 0; _timer = 0; return; } //! \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) { _timer += ms_since_last_tick; //cout << "_timer= " << _timer << ", _outstanding_segments_out.size()= " << _outstanding_segments_out.size() << endl; if (_timer >= _retransmission_timeout && !_outstanding_segments_out.empty()) { _segments_out.push(_outstanding_segments_out.front()); _consecutive_retransmissions++; if (_outstanding_segments_out.front().header().syn == true || _window_size != 0) //巨坑！ _retransmission_timeout *= 2; _timer = 0; } } unsigned int TCPSender::consecutive_retransmissions() const { return {_consecutive_retransmissions}; } void TCPSender::send_empty_segment() { TCPSegment seg; seg.header().seqno = wrap(_next_seqno, _isn); _segments_out.push(seg); }

参考

课程网址 知乎 【计算机网络】Stanford CS144 学习笔记