CS144 Lab 4

by on under CS144
5 minute read

上一个实验:Lab 3

这篇比较水,聊聊 CS144 Lab 4。

如果你参考了我前面 Lab 的实现,请一定要看这里。

前面的 Lab 测试例不是非常完善,因此有一些隐藏的小问题没有暴露出来,现在(发布时)已经在原文中修正了,如果你在这篇文章的发布前参考的,请务必重新看一下 Lab 1 和 Lab 3(/cs144/2021/10/09/cs144-lab-3/)。

Lab 4

比较水的原因是自己做的非常卡,基本上就是借鉴这篇文章的思路,和wine99 的博客的代码,在他们的基础上进行一些小修,直到我看懂了他们的代码,我才意识到这个 Lab 要做什么,感觉还是挺有收获的。

这个 Lab 考察的是 TCP 自动机,不过和课程里的自动机可能会有很小的一点点区别,要以 Lab 2 和 Lab 3 里的状态转换机为准(参考上面贴出来的第一篇文章)。

实现时的思路基本上是这样的:

  • 思考现在 Sender 和 Receiver 分别在什么状态。
  • 思考他们可以转换成什么状态,这在 TCP FSM 上对应的哪一步?
  • 思考这个转换是如何发生的(收到了什么样的 Segment? 被调用了什么函数?)。
  • 思考这个转换发生的时候,Sender 和 Receiver 应该有什么表现。

还有一些 debug 的小 tips。

  • 如果有 timeout,先看看是不是网络问题。
    • 如果不是网络问题,问题出现在关闭 TCP 链接相关的地方可能性会比较大。
    • 一定要确认是不是自己所有函数都实现了。

这篇文章就直接贴完整代码吧。

tcp_connection.hh:

#ifndef SPONGE_LIBSPONGE_TCP_FACTORED_HH
#define SPONGE_LIBSPONGE_TCP_FACTORED_HH

#include "tcp_config.hh"
#include "tcp_receiver.hh"
#include "tcp_sender.hh"
#include "tcp_state.hh"

//! \brief A complete endpoint of a TCP connection
class TCPConnection {
  private:
    TCPConfig _cfg;
    TCPReceiver _receiver{_cfg.recv_capacity};
    TCPSender _sender{_cfg.send_capacity, _cfg.rt_timeout, _cfg.fixed_isn};

    //! outbound queue of segments that the TCPConnection wants sent
    std::queue<TCPSegment> _segments_out{};

    //! Should the TCPConnection stay active (and keep ACKing)
    //! for 10 * _cfg.rt_timeout milliseconds after both streams have ended,
    //! in case the remote TCPConnection doesn't know we've received its whole stream?
    bool _linger_after_streams_finish{true};
    bool _isActive{true};
    size_t _time_since_last_segment_received{0};

  public:
    //! \name "Input" interface for the writer
    //!@{

    //! \brief Initiate a connection by sending a SYN segment
    void connect();

    //! \brief Write data to the outbound byte stream, and send it over TCP if possible
    //! \returns the number of bytes from `data` that were actually written.
    size_t write(const std::string &data);

    //! \returns the number of `bytes` that can be written right now.
    size_t remaining_outbound_capacity() const;

    //! \brief Shut down the outbound byte stream (still allows reading incoming data)
    void end_input_stream();
    //!@}

    //! \name "Output" interface for the reader
    //!@{

    //! \brief The inbound byte stream received from the peer
    ByteStream &inbound_stream() { return _receiver.stream_out(); }
    //!@}

    //! \name Accessors used for testing

    //!@{
    //! \brief number of bytes sent and not yet acknowledged, counting SYN/FIN each as one byte
    size_t bytes_in_flight() const;
    //! \brief number of bytes not yet reassembled
    size_t unassembled_bytes() const;
    //! \brief Number of milliseconds since the last segment was received
    size_t time_since_last_segment_received() const;
    //!< \brief summarize the state of the sender, receiver, and the connection
    TCPState state() const { return {_sender, _receiver, active(), _linger_after_streams_finish}; };
    //!@}

    //! \name Methods for the owner or operating system to call
    //!@{

    //! Called when a new segment has been received from the network
    void segment_received(const TCPSegment &seg);

    //! Called periodically when time elapses
    void tick(const size_t ms_since_last_tick);
    void send_sender_segments();
    void unclean_shutdown();
    void clean_shutdown();

    //! \brief TCPSegments that the TCPConnection has enqueued for transmission.
    //! \note The owner or operating system will dequeue these and
    //! put each one into the payload of a lower-layer datagram (usually Internet datagrams (IP),
    //! but could also be user datagrams (UDP) or any other kind).
    std::queue<TCPSegment> &segments_out() { return _segments_out; }

    //! \brief Is the connection still alive in any way?
    //! \returns `true` if either stream is still running or if the TCPConnection is lingering
    //! after both streams have finished (e.g. to ACK retransmissions from the peer)
    bool active() const;
    //!@}
    bool in_listen_state() const;
    bool in_syn_sent_state() const;
    bool in_syn_recv_state() const;

    //! Construct a new connection from a configuration
    explicit TCPConnection(const TCPConfig &cfg) : _cfg{cfg} {}

    //! \name construction and destruction
    //! moving is allowed; copying is disallowed; default construction not possible

    //!@{
    ~TCPConnection();  //!< destructor sends a RST if the connection is still open
    TCPConnection() = delete;
    TCPConnection(TCPConnection &&other) = default;
    TCPConnection &operator=(TCPConnection &&other) = default;
    TCPConnection(const TCPConnection &other) = delete;
    TCPConnection &operator=(const TCPConnection &other) = delete;
    //!@}
};

#endif  // SPONGE_LIBSPONGE_TCP_FACTORED_HH

tcp_connection.cc:

#include "tcp_connection.hh"

#include <iostream>

// Dummy implementation of a TCP connection

// For Lab 4, please replace with a real implementation that passes the
// automated checks run by `make check`.

template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {}

using namespace std;

size_t TCPConnection::remaining_outbound_capacity() const { return _sender.stream_in().remaining_capacity(); }

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

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

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

void TCPConnection::segment_received(const TCPSegment &seg) {
    if (!active())
        return;
    _time_since_last_segment_received = 0;
    if (!_receiver.ackno().has_value() && _sender.next_seqno_absolute() == 0) {
        // RECEIVER: LISTEN, Sender: CLOSE
        if (!seg.header().ack) {
            return;
        } else {
            _receiver.segment_received(seg);
            connect();
            return;
        }
    }
    if (_sender.next_seqno_absolute() > 0 && _sender.bytes_in_flight() == _sender.next_seqno_absolute() &&
        !_receiver.ackno().has_value()) {
        // Sender: SYN_SENT, Receiver: LISTEN
        if (seg.payload().size()) {
            return;
        } else if (!seg.header().ack) {
            if (seg.header().syn) {
                // simultaneous open
                _receiver.segment_received(seg);
                _sender.send_empty_segment();
            }
            return;
        } else if (seg.header().rst) {
            _receiver.stream_out().set_error();
            _sender.stream_in().set_error();
            _isActive = false;
            return;
        }
    }
    // SYN
    _receiver.segment_received(seg);
    _sender.ack_received(seg.header().ackno, seg.header().win);

    if (_sender.stream_in().buffer_empty() && seg.length_in_sequence_space()) {
        _sender.send_empty_segment();
    }

    if (seg.header().rst) {
        _sender.send_empty_segment();
        unclean_shutdown();
        return;
    }

    send_sender_segments();
}

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

size_t TCPConnection::write(const string &data) {
    if (!data.size()) {
        return 0;
    }
    size_t write_size = _sender.stream_in().write(data);
    _sender.fill_window();
    send_sender_segments();
    return write_size;
}

//! \param[in] ms_since_last_tick number of milliseconds since the last call to this method
void TCPConnection::tick(const size_t ms_since_last_tick) {
    if (!active()) {
        return;
    }

    if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
        _sender.bytes_in_flight() == 0 && _linger_after_streams_finish && _receiver.stream_out().input_ended()) {
        clean_shutdown();
    }
    _time_since_last_segment_received += ms_since_last_tick;
    _sender.tick(ms_since_last_tick);
    if (_sender.consecutive_retransmissions() > TCPConfig::MAX_RETX_ATTEMPTS) {
        unclean_shutdown();
    }
    send_sender_segments();
}

void TCPConnection::send_sender_segments() {
    TCPSegment seg;
    while (!_sender.segments_out().empty()) {
        seg = _sender.segments_out().front();
        _sender.segments_out().pop();
        if (_receiver.ackno().has_value()) {
            seg.header().ack = true;
            seg.header().ackno = _receiver.ackno().value();
            seg.header().win = _receiver.window_size();
        }
        _segments_out.push(seg);
    }
    clean_shutdown();  // check logic inside
}

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

void TCPConnection::connect() {
    _sender.fill_window();
    send_sender_segments();
}

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

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

void TCPConnection::unclean_shutdown() {
    // send or received rst
    _receiver.stream_out().set_error();
    _sender.stream_in().set_error();
    _isActive = false;
    TCPSegment seg = _sender.segments_out().front();
    _sender.segments_out().pop();
    seg.header().ack = true;
    if (_receiver.ackno().has_value()) {
        seg.header().ackno = _receiver.ackno().value();
    }
    seg.header().win = _receiver.window_size();
    seg.header().rst = true;
    _segments_out.push(seg);
}

void TCPConnection::clean_shutdown() {
    if (_receiver.stream_out().input_ended()) {
        if (!_sender.stream_in().eof()) {
            _linger_after_streams_finish = false;
        } else if (_sender.bytes_in_flight() == 0) {
            if (!_linger_after_streams_finish || time_since_last_segment_received() >= 10 * _cfg.rt_timeout) {
                _isActive = false;
            }
        }
    }
}

完成后我们在build目录下编译并测试,和之前类似:

$ CXX=g++-8 cmake ..
$ make format
$ make -j4
$ make check_lab4

通过的话会得到类似字样:

100% tests passed, 0 tests failed out of 162

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

还有一部分是性能调优,我就不太想做了,因为最近工作比较忙,这个 Lab 拖的也有点久,所以需要加快些进度,想做的朋友参考一下开头贴的两个博客就好。

CS144, computer networking
comments powered by Disqus