这里回顾CS 144 Lab 3: the TCP sender。

实验资料:

Lab 3: the TCP sender

准备工作

下载代码以及跑通流程

git checkout -b lab3-startercode
git fetch
git merge origin/lab3-startercode
make -j4 && make check_lab3

说明

  • 为了模块化,增加了Timer类。
  • 整体思路是发送数据,然后判断是否要重传。
  • SYN, FIN对应的负载长度为0。
  • ack n表示序号n之前的都收到。

代码

Timer

实现 Timer类,方便后续使用:

class Timer {
    private:
        // 是否过期
        bool _expired = false;
        // RTO
        unsigned int _rto = 0;
        // 经历的时间
        unsigned int _time = 0;
    public:
        Timer() {};
        Timer(unsigned int rto) : _rto(rto) {};
        // expired
        bool is_expired() { return _expired; };
        // rto
        void update_rto(unsigned int rto) { 
            _rto = rto;
            _expired = false;
        };
        unsigned int get_rto() { return _rto; };
        void double_rto() { 
            _rto *= 2; 
            _expired = false;
        };
        // _time, 更新时间, 并判断是否过期
        void update_time(unsigned int t) {
            _time += t;
            if (_time >= _rto) {
                _expired = true;
            }
        }
};

TCPSender

TCPSender需要添加一些成员变量和方法,具体作用见注释:

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

    // add begin
    // 已发送, 未确认的segments
    std::queue<TCPSegment> _segments{};
    // 窗口大小, 初始化为1
    unsigned int _window_size = 1;
    // 已发送, 未确认的字节数
    size_t _bytes_in_flight = 0;
    // 连续重传次数
    unsigned int _cnt = 0;
    // 上一次ack的index
    uint64_t _last_ack{0};

    // Timer
    // timer是否运行
    bool _is_timer_running = false;
    // 重传计时器
    Timer _timer;
    // RTO
    unsigned int _rto = 0;

    // SYN, FIN
    // 下一个segment对应的syn
    bool _syn = true;
    // 下一个segment对应的fin
    bool _fin = false;
    // add end

  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
    bool 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); }
    //!@}

    // add begin
    // 将seqno和str封装为TCPSegment, 设置对应的syn, fin
    TCPSegment get_segment(WrappingInt32 &seqno, std::string &str);
    // add end
};

构造函数TCPSender

添加_timer_rto的初始化即可:

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)
    , _timer()
    , _rto(retx_timeout) {}

bytes_in_flight

uint64_t TCPSender::bytes_in_flight() const { 
    return _bytes_in_flight; 
}

get_segment

// add
TCPSegment TCPSender::get_segment(WrappingInt32 &seqno, std::string &str) {
    // 设置seqno和标志位
    TCPHeader header;
    header.syn = _syn;
    header.fin = _fin;
    header.seqno = seqno;
    // 设置负载
    Buffer payload(std::move(str));
    // 设置TCPSegment
    TCPSegment tcp_segment;
    tcp_segment.header() = header;
    tcp_segment.payload() = payload;
    // 更新
    size_t l = tcp_segment.length_in_sequence_space();
    _bytes_in_flight += l;
    _next_seqno += l;
    // 4. 每次发送包含数据(在序列空间中长度非零)的段(不管是第一次还是重传),如果timer没有运行,就启动它,使它在RTO毫秒后失效(对于RTO的当前值)
    if (!_is_timer_running) {
        _timer = Timer(_rto);
        _is_timer_running = true;
    }

    return tcp_segment;
}

fill_window

void TCPSender::fill_window() {
    // 根据FAQ, fill_window时候将窗口大小视为至少1
    unsigned int window_size = _window_size ? _window_size : 1;
    // send syn
    if (_syn) {
        std::string str = "";
        WrappingInt32 seqno = next_seqno();
        TCPSegment tcp_segment = get_segment(seqno, str);
        // 更新已发送, 未确认的segments
        _segments_out.push(tcp_segment);
        // 发送segment
        _segments.push(tcp_segment);
        // 更新_syn
        _syn = false;

        return;
    }

    uint64_t free_size; 
    // [_last_ack, _next_seqno)部分已发送
    // 当窗口未满, 并且还没收到fin
    while (((free_size = window_size - (_next_seqno - _last_ack)) > 0) && (!_fin)) {
        size_t l = free_size;
        // 不能超过最大负载
        l = min(l, TCPConfig::MAX_PAYLOAD_SIZE);
        // 获得tcp_segment, 注意是read
        std::string str = _stream.read(l);
        WrappingInt32 seqno = next_seqno();
        // 读取后再判断是否为fin
        if (_stream.eof()) {
            _fin = true;
        }
        TCPSegment tcp_segment = get_segment(seqno, str);
        // 如果负载为空则返回
        if (tcp_segment.length_in_sequence_space() == 0) {
            break;
        }
        // 更新已发送, 未确认的segments
        _segments_out.push(tcp_segment);
        // 发送segment
        _segments.push(tcp_segment);
    }
}

ack_received

bool TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) {
    // [_last_ack, _next_seqno)部分已发送未确认

    // 绝对序列号
    uint64_t abs_ackno = unwrap(ackno, _isn, _last_ack);
    // 收到了未发送的确认, 直接返回false
    if (abs_ackno > _next_seqno) {
        return false;
    }

    // 更新窗口大小
    _window_size = window_size;

    // 确认已经收到, 直接返回true
    if (abs_ackno < _last_ack) {
        return true;
    }

    // 其余情况更新
    _last_ack = abs_ackno;

    // 7. 当接收方给发送方确认成功接收新数据的`ackno`时(该`ackno`反映了一个大于之前的任何`ackno`的绝对序列号)。
    // 将RTO调回其“初始值”
    _rto = _initial_retransmission_timeout;
    // 如果发送方有任何未完成的数据,重新启动重传timer,使其在RTO毫秒后失效(对于RTO的当前值)
    if (!_segments.empty()) {
        _timer = Timer(_rto);
        _is_timer_running = true;
    }
    // 将“连续重传”的计数重设为零
    _cnt = 0;

    // 删除已确认的部分
    while (!_segments.empty()) {
        TCPSegment seg = _segments.front();
        TCPHeader header = seg.header();
        // 序列范围是[start, end)
        // 注意是seqno
        WrappingInt32 start = header.seqno;
        WrappingInt32 end = start + seg.length_in_sequence_space();
        // 如果[start, end)都小于ackno, 则表示已确认; 否则退出循环
        if (ackno - end >= 0) {
            _segments.pop();
            _bytes_in_flight -= seg.length_in_sequence_space();
        } else {
            break;
        }
    }

    // 5. 当所有未完成的数据都被确认后,关闭重传计时器。
    if (_segments.empty()) {
        _is_timer_running = false;
    }

    // window
    fill_window();

    return true;
}

tick

void TCPSender::tick(const size_t ms_since_last_tick) { 
    // 更新时间
    _timer.update_time(ms_since_last_tick);
    // 6. 如果tick被调用,并且重传计时器已经过期
    // 有可以重传的部分
    if (_timer.is_expired() && (!_segments.empty())) {
        // 重传TCP接收方尚未完全确认的最早段
        _segments_out.push(_segments.front());
        // 如果窗口大小为非零
        if (_window_size) {
            _cnt++;
            _rto *= 2;
        }
        // 启动重传timer,使其在RTO毫秒后过期
        _timer = Timer(_rto);
        _is_timer_running = true;
    }
}

consecutive_retransmissions

直接返回即可:

unsigned int TCPSender::consecutive_retransmissions() const { 
    return _cnt;
}

send_empty_segment

void TCPSender::send_empty_segment() {
    // 设置负载为空
    std::string str = "";
    WrappingInt32 seqno = next_seqno();
    TCPSegment tcp_segment = get_segment(seqno, str);
    // 注意空段不需要存储到未确认的部分
    _segments_out.push(tcp_segment);
}

测试

make -j4 && make check_lab3

Test project /cs144/sponge/build
      Start  1: t_wrapping_ints_cmp
 1/31 Test  #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
      Start  2: t_wrapping_ints_unwrap
 2/31 Test  #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
      Start  3: t_wrapping_ints_wrap
 3/31 Test  #3: t_wrapping_ints_wrap .............   Passed    0.00 sec
      Start  4: t_recv_connect
 4/31 Test  #4: t_recv_connect ...................   Passed    0.00 sec
      Start  5: t_recv_transmit
 5/31 Test  #5: t_recv_transmit ..................   Passed    0.05 sec
      Start  6: t_recv_window
 6/31 Test  #6: t_recv_window ....................   Passed    0.00 sec
      Start  7: t_recv_reorder
 7/31 Test  #7: t_recv_reorder ...................   Passed    0.00 sec
      Start  8: t_recv_close
 8/31 Test  #8: t_recv_close .....................   Passed    0.00 sec
      Start  9: t_send_connect
 9/31 Test  #9: t_send_connect ...................   Passed    0.00 sec
      Start 10: t_send_transmit
10/31 Test #10: t_send_transmit ..................   Passed    0.05 sec
      Start 11: t_send_retx
11/31 Test #11: t_send_retx ......................   Passed    0.00 sec
      Start 12: t_send_window
12/31 Test #12: t_send_window ....................   Passed    0.11 sec
      Start 13: t_send_ack
13/31 Test #13: t_send_ack .......................   Passed    0.00 sec
      Start 14: t_send_close
14/31 Test #14: t_send_close .....................   Passed    0.00 sec
      Start 15: t_strm_reassem_cap
15/31 Test #15: t_strm_reassem_cap ...............   Passed    0.00 sec
      Start 16: t_strm_reassem_single
16/31 Test #16: t_strm_reassem_single ............   Passed    0.00 sec
      Start 17: t_strm_reassem_seq
17/31 Test #17: t_strm_reassem_seq ...............   Passed    0.00 sec
      Start 18: t_strm_reassem_dup
18/31 Test #18: t_strm_reassem_dup ...............   Passed    0.00 sec
      Start 19: t_strm_reassem_holes
19/31 Test #19: t_strm_reassem_holes .............   Passed    0.00 sec
      Start 20: t_strm_reassem_many
20/31 Test #20: t_strm_reassem_many ..............   Passed    0.40 sec
      Start 21: t_strm_reassem_overlapping
21/31 Test #21: t_strm_reassem_overlapping .......   Passed    0.00 sec
      Start 22: t_strm_reassem_win
22/31 Test #22: t_strm_reassem_win ...............   Passed    0.36 sec
      Start 23: t_byte_stream_construction
23/31 Test #23: t_byte_stream_construction .......   Passed    0.00 sec
      Start 24: t_byte_stream_one_write
24/31 Test #24: t_byte_stream_one_write ..........   Passed    0.00 sec
      Start 25: t_byte_stream_two_writes
25/31 Test #25: t_byte_stream_two_writes .........   Passed    0.00 sec
      Start 26: t_byte_stream_capacity
26/31 Test #26: t_byte_stream_capacity ...........   Passed    0.00 sec
      Start 27: t_byte_stream_many_writes
27/31 Test #27: t_byte_stream_many_writes ........   Passed    0.01 sec
      Start 28: t_webget
28/31 Test #28: t_webget .........................   Passed    1.05 sec
      Start 48: t_address_dt
29/31 Test #48: t_address_dt .....................   Passed    0.00 sec
      Start 49: t_parser_dt
30/31 Test #49: t_parser_dt ......................   Passed    0.00 sec
      Start 50: t_socket_dt
31/31 Test #50: t_socket_dt ......................   Passed    0.01 sec

100% tests passed, 0 tests failed out of 31

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