计网一直只是看了点书（学校大三才给选），感觉看了也很容易忘，这个lab做完只能说tcp应该是理解且记住了(

环境为本地VMware workstation+ubuntu 20.04

依赖可以参考官网https://stanford.edu/class/cs144/vm_howto/

You’re welcome to use any Linux installation, in a VM or not, provided that it has a reasonably recent kernel (4.x should be fine) and a C++17 compiler.

Please note that the CAs will not be available to help you debug a BYO Linux installation. If you’re in doubt, please consider using the prepared image or following our VM setup instructions.

Packages you’ll need

To run the labs, you’ll need the following software:

  • g++ version 8.x
  • clang-tidy version 6 or 7
  • clang-format version 6 or 7
  • cmake version 3 or later
  • libpcap development headers (libpcap-dev on Debian-like distributions)
  • git
  • iptables
  • mininet 2.2.0 or later
  • tcpdump
  • telnet
  • wireshark
  • socat
  • netcat-openbsd
  • GNU coreutils
  • bash
  • doxygen
  • graphviz

Note: there are at least three versions of netcat. You won’t be using it much, but when you do, we will assume you’ve got the OpenBSD variant. Others might also work, though it is possible that they will require different commandline flags.

We’ve tested the labs with recent Debian-derived systems (Ubuntu 18.04 and similar) and Arch Linux. In all likelihood, other modern Linux distributions will also work.

资料主要参考课程文档

lab0

获取网页：

image-20221228224208183

1
2
3
4
5
telnet cs144.keithw.org http //telnet 用于在本地计算机与远程计算机之间打开一个可靠的字节流，并在该计算机上运行特定的服务：http服务
GET /hello HTTP/1.1 //告诉服务器URL的路径
Host: cs144.keithw.org //告诉服务器主机
Connection: close //告诉服务请完成请求，在完成回复后立刻关闭
//这里的话必须再按一次回车，用于告诉服务器你已经完成了http请求，否则将会收到 408 Request Timeout

netcat+telnet 实现简单客户端服务端

image-20221228225514738

实现webget

参考https://cs144.github.io/doc/lab0/class_t_c_p_socket.html 文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "socket.hh"
#include "util.hh"

#include <cstdlib>
#include <iostream>
#include <socket.hh>
using namespace std;

void get_URL(const string &host, const string &path) {
    // Your code here.

    // You will need to connect to the "http" service on
    // the computer whose name is in the "host" string,
    // then request the URL path given in the "path" string.

    // Then you'll need to print out everything the server sends back,
    // (not just one call to read() -- everything) until you reach
    // the "eof" (end of file).

    TCPSocket sock;
    sock.connect(Address(host,"http"));
    sock.write("GET "+path+" HTTP/1.1\r\nHost: "+host+"\r\n");
    sock.write("Connection: close\r\n\r\n");

    while(!sock.eof()){
        cout<<sock.read();
    }
    sock.close();

    return;
}

int main(int argc, char *argv[]) {
    try {
        if (argc <= 0) {
            abort();  // For sticklers: don't try to access argv[0] if argc <= 0.
        }

        // The program takes two command-line arguments: the hostname and "path" part of the URL.
        // Print the usage message unless there are these two arguments (plus the program name
        // itself, so arg count = 3 in total).
        if (argc != 3) {
            cerr << "Usage: " << argv[0] << " HOST PATH\n";
            cerr << "\tExample: " << argv[0] << " stanford.edu /class/cs144\n";
            return EXIT_FAILURE;
        }

        // Get the command-line arguments.
        const string host = argv[1];
        const string path = argv[2];

        // Call the student-written function.
        get_URL(host, path);
    } catch (const exception &e) {
        cerr << e.what() << "\n";
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

image-20230104152159878

lab0

实现抽象字节流对象：

  • 有输出输入端
  • 写者可以结束输入
  • …

要实现一段输入另一端输出，可以考虑用循环队列deque实现。

坑点：只有读写都完成了，也就是input_ended同时buffer也为空时 才判定为eof

image-20230104165012511

byte_stream.hh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#ifndef SPONGE_LIBSPONGE_BYTE_STREAM_HH
#define SPONGE_LIBSPONGE_BYTE_STREAM_HH

#include <deque>
#include <string>
//! \brief An in-order byte stream.

//! Bytes are written on the "input" side and read from the "output"
//! side.  The byte stream is finite: the writer can end the input,
//! and then no more bytes can be written.
class ByteStream {
  private:
    // 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.
    std::deque<char> _stream_buffer;
    size_t _capacity ;
    size_t _read_cnt ;
    size_t _write_cnt ;
    bool _end_of_input ;

    bool _error;  //!< Flag indicating that the stream suffered an error.

  public:
    //! Construct a stream with room for `capacity` bytes.
    ByteStream(const size_t capacity);

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

    //! Write a string of bytes into the stream. Write as many
    //! as will fit, and return how many were written.
    //! \returns the number of bytes accepted into the stream
    size_t write(const std::string &data);

    //! \returns the number of additional bytes that the stream has space for
    size_t remaining_capacity() const;

    //! Signal that the byte stream has reached its ending
    void end_input();

    //! Indicate that the stream suffered an error.
    void set_error() { _error = true; }
    //!@}

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

    //! Peek at next "len" bytes of the stream
    //! \returns a string
    std::string peek_output(const size_t len) const;

    //! Remove bytes from the buffer
    void pop_output(const size_t len);

    //! Read (i.e., copy and then pop) the next "len" bytes of the stream
    //! \returns a string
    std::string read(const size_t len);

    //! \returns `true` if the stream input has ended
    bool input_ended() const;

    //! \returns `true` if the stream has suffered an error
    bool error() const { return _error; }

    //! \returns the maximum amount that can currently be read from the stream
    size_t buffer_size() const;

    //! \returns `true` if the buffer is empty
    bool buffer_empty() const;

    //! \returns `true` if the output has reached the ending
    bool eof() const;
    //!@}

    //! \name General accounting
    //!@{

    //! Total number of bytes written
    size_t bytes_written() const;

    //! Total number of bytes popped
    size_t bytes_read() const;
    //!@}
};

#endif  // SPONGE_LIBSPONGE_BYTE_STREAM_HH

byte_stream.cc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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) :_stream_buffer(),_capacity(capacity),_read_cnt(0),_write_cnt(0),_end_of_input(false),_error(false)
{ }

size_t ByteStream::write(const string &data) {
/*    if (_end_of_input)
        return 0;*/

    size_t len = min(data.length(), _capacity - _stream_buffer.size());
    _write_cnt += len;
    for (size_t i = 0; i < len; i++) {
        _stream_buffer.push_back(data[i]);
    }
    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 peek_size = min(len, _stream_buffer.size());
    return string(_stream_buffer.begin(), _stream_buffer.begin() + peek_size);
}

//! \param[in] len bytes will be removed from the output side of the buffer
void ByteStream::pop_output(const size_t len) {
    size_t pop_size = min(len, _stream_buffer.size());

    for (size_t i = 0; i < pop_size; i++)
        _stream_buffer.pop_front();

    _read_cnt += 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) {
    string data = this->peek_output(len);
    this->pop_output(len);

    return data;
}

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

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

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

bool ByteStream::buffer_empty() const { return _stream_buffer.empty(); }

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

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

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

size_t ByteStream::remaining_capacity() const { return {_capacity - _stream_buffer.size()}; }

lab1

运行git 以获取lab1的初始代码以及测试

1
git merge origin/lab1-starterco

在build目录下执行

1
make -j4

子串拼接

本实验会对后续实验的速度造成影响，所以得写好些。

TCP ⾃⾝可以使⽤不可靠的数据报提供⼀对可靠的字节流，以此为基础，我们将完成数据报到字节流的拼接。

实验给出的数据报 以函数参数的形式给出，分别包含index，以及data，这其实是为后面TCP接受实际数据包的载体做准备

完成本实验的难点主要在于理解题目。。

image-20230104234752817

  • 我们会不断接受到 无序的，可能带有重复字节的数据报
  • 如果收到的字节流刚好覆盖了我们写的起始点，我们就执行写入
  • 对收到的字节流进行去重 合并操作

思路：

需要一个_next_assembled_index 来记录我们下一次要写入字节流的位置

_capacity为总的容量，那么_capacity+next_assembled_index 就是我们当前需要接受的一个范围。

这里分成三种情况即可：

  1. 要写入的index + data.len < =next_assembled_index ，说明已经写过了，略过即可。
  2. 要写入的 index + data.len > next_assembled_index （过了1的话这里已经成立了）同时（index < _next_assembled_index），也就是说有一部分数据是在我们要写入的位置之后，是有效的， 我们就直接对该数据报去重，方便后面统一的操作。
  3. index > _next_assembled_index ，完全没写过的情况，正常处理即可。

然后再对数据报进行去重，这里我选择用set对数据报进行临时存储（查询快），每次都去找相零的数据报，如果有重复的部分就去重，注意，这是一个类似迭代的操作，因为去重完了合成的新数据报可能可以继续去重。

去重分为两种，一种是后面重合了，一种是前面重合了。

最后就是执行写入和判断eof的操作。

仅有当数据完全写入，也就是empty，同时已经接受到有eof的数据报后，才能算作处理结束了。

测试结果：

image-20230104234319667

stream_reassembler.hh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
#define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH

#include "byte_stream.hh"

#include <cstdint>
#include <set>
#include <string>

//! \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.
struct broken_bytestream {
    std::string _data;
    size_t _begin_index;
    size_t _len;

    bool operator<(const broken_bytestream t) const { return _begin_index < t._begin_index; }
    bool operator>(const broken_bytestream t) const { return _begin_index > t._begin_index; }
    bool operator==(const broken_bytestream t) const { return _begin_index == t._begin_index; }
    broken_bytestream(std::string data, size_t index) : _data(data), _begin_index(index), _len(data.length()) {}
    broken_bytestream() : _data(), _begin_index(0), _len(0) {}

};

class StreamReassembler {
  private:
    // Your code here -- add private members as necessary.

    ByteStream _output;    //!< The reassembled in-order byte stream
    size_t _capacity = 0;  //!< The maximum number of bytes

    std::set<broken_bytestream> _fragments{};
    size_t _next_assembled_index = 0;
    size_t _unassembled_bytes = 0;
    bool _eof_flag = false;

    ssize_t  merge_fragments(broken_bytestream &t1, const broken_bytestream &t2);
    void judge_eof(const bool _eof);
  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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include "stream_reassembler.hh"
#include <iostream>
// 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;

StreamReassembler::StreamReassembler(const size_t capacity)
    : _output(capacity)
    , _capacity(capacity)
    , _fragments()
    , _next_assembled_index(0)
    , _unassembled_bytes(0)
    , _eof_flag(false) {}

//! \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::judge_eof(const bool _eof) {
    if (_eof) {
        _eof_flag = true;
    }
    if (_eof_flag && empty()) {
        _output.end_input();
    }
}

void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
	//这里要是 >= ，因为lab4会给到刚好等于的样例。。。 虽然> 也能过lab1，但是会过不了lab4
    if (index >= _next_assembled_index + _capacity)
        return;  // overflow

    broken_bytestream current_stream;
    if (index + data.length() <= _next_assembled_index) {
        judge_eof(eof);
        return;  

    } else if (index < _next_assembled_index) {
        // cut prev  
        size_t offset = _next_assembled_index-index ;
        current_stream._begin_index = _next_assembled_index;
        current_stream._data.assign(data.begin() + offset, data.end());
        current_stream._len = current_stream._data.length();
    } else {  // index > _next_assembled_index 
        current_stream._begin_index = index;
        current_stream._data = data;
        current_stream._len = data.length();
    }

    _unassembled_bytes += current_stream._len;

    // do merge
     do{
    // find next fragments
    ssize_t merged_size = 0;
    auto near_iter = _fragments.lower_bound(current_stream);
    // merge next
    while (near_iter != _fragments.end() && (merged_size = merge_fragments(current_stream, *near_iter)) >= 0) {
        _unassembled_bytes -= merged_size;
        _fragments.erase(near_iter);  // merged next overed, delete the next;
        near_iter = _fragments.lower_bound(current_stream);
    }
    // merge prev
    if (near_iter == _fragments.begin()) 
        break;
    near_iter--;

    while ((merged_size = merge_fragments(current_stream, *near_iter)) >= 0) {
        _unassembled_bytes -= merged_size;
        _fragments.erase(near_iter);
        near_iter = _fragments.lower_bound(current_stream);
        if (near_iter == _fragments.begin()) {
            break;
        }
        near_iter--;
    }

    }while(false);

    _fragments.insert(current_stream);


    if (!_fragments.empty() && _fragments.begin()->_begin_index == _next_assembled_index) {
        const broken_bytestream head = *_fragments.begin();
        size_t write_cnt = _output.write(head._data);
        _next_assembled_index += write_cnt;
        _unassembled_bytes -= write_cnt;

        _fragments.erase(_fragments.begin());
    }
    

    judge_eof(eof);
}

ssize_t StreamReassembler::merge_fragments(broken_bytestream &t1, const broken_bytestream &t2) {
    broken_bytestream front = min(t1, t2);
    broken_bytestream back = ((front == t1) ? t2 : t1);
    if (front._begin_index + front._len < back._begin_index)
        return -1;
    else if (front._begin_index + front._len >= back._begin_index + back._len) {
        t1 = front;
        return back._len;
    } else {  // front._begin_index+front.len < back._begin_index+back.len
        int merge_num = front._begin_index + front._len - back._begin_index;
        t1._begin_index = front._begin_index;
        t1._data = front._data + back._data.substr(merge_num);
        t1._len = t1._data.length();
        return merge_num;
    }
}

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

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



lab2

TCP报文：

image-20230105222033664

结构体以及函数的使用可以查看https://cs144.github.io/doc/lab2/class_t_c_p_segment.html#details 或者源代码

序列号转换

  • 序列号 seqno。从 ISN 起步，包含 SYN 和 FIN，32 位循环计数
  • 绝对序列号 absolute seqno。从 0 起步，包含 SYN 和 FIN，64 位非循环计数
  • 流索引 stream index。从 0 起步，排除 SYN 和 FIN，64 位非循环计数。

image-20230105191357818

完成 序列号<==> 绝对序列号 的相互转换

从序列号转到绝对序号号时， 其实就只需要比较 x ， x+2^32 , x- 2^32 这三个数哪个和checkpoints最接近即可。

checkpoint表示最近一次转换求得的absolute seqno，而本次转换出的absolute seqno应该选择与上次值最为接近的那一个。原理是虽然segment不一定按序到达，但几乎不可能出现相邻到达的两个segment序号差值超过INT32_MAX的情况，除非延迟以年为单位，或者产生了比特差错（后面的LAB可能涉及）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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) { return WrappingInt32{static_cast<uint32_t>(n) + isn.raw_value()}; }

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

//  ( offset  + a * 2^32)mod 2^32 = (offset)mod 2 ^ 32 =  n
// a = checkpoint >> 32

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    uint32_t offset = n.raw_value() - isn.raw_value();

    uint64_t base = (checkpoint & 0xFFFFFFFF00000000) + offset;
    uint64_t max_base = base + 0x100000000;
    uint64_t min_base = base > 0x100000000 ? (base - 0x100000000) : base;

    if ((base < checkpoint) && ((max_base - checkpoint) < (checkpoint - base)))
        return max_base;
    if ((base > checkpoint) && ((checkpoint - min_base) < (base - checkpoint)))
        return min_base;
    return base;
}

测试结果：

image-20230105191322368

TCP 接收器

流程图

image-20230105222600136

  • listen：等待syn包，ackno为空，其余包很简单地直接丢弃。
  • syn_recv：已经接收了syn包，正常接收数据报
  • fin_recv : 已经接收了fin包，终止Bytestream的输入。

我对计网仅有的了解来源于我大一随便翻了翻的《自顶向下》那本书，翻完后我基本全忘了。所以写这里的时候我是极其懵逼的 ，一直过不了，最后是参考了一下@Kiprey师傅的。

问题主要在于，一开始我把SYN报和FIN报当成普通的报文看待，认为只是带了SYN/FIN标志而已。，同时能且也有携带payload。

实际上，每个 SYN/FIN 报文 还会额外的占用一个seqno，为什么要这么做？

SYNs and FINs require acknowledgement, thus they increment the stream’s sequence number by one when used.For example, if the connection is closed without sending any more data, then if theFIN did not consume a sequencenumber the closing end couldn’t tell the difference between an ACK for the FIN,and an ACK for the data that was sent prior to the FIN.

简单来说，就是我们需要ack 确认 收到的SYN/FIN 报文，尤其是FIN报文，如果不再消耗一个seqno的话，前一个ACK和FIN的ACK就没有区别了。

但我对这里误解很深的最大原因是，我把SYN报和FIN报当成普通的报文看待，还以为他们能正常携带数据，但事实上，一般TCP在处理SYN报文的时候都会忽略携带的数据…

关于SYN报文传输数据的问题，在此我看到了一篇文章：https://zhuanlan.zhihu.com/p/468912961，有兴趣的可以看看。

这样就很容易理解后面那句，我一开始很疑惑这样岂不是让后面一个报文没法写入了

1
uint64_t index=absolute_seqno -1 + header.syn;

这里要加上header.syn，也就是syn报额外占一个seqno，这样我们就可以包含syn报的payload，index 从0开始到payload长度的字节就都被syn报写了，后面再来 absolute_seqno -1 小于这个长度的数的报文也无所谓了，因为我们在StreamReassembler 结构体中已经对这样有重复字节的报文进行处理了。

每次看这个表我都会误解

image-20230105213550652

文档中有提到关于携带数据的：

image-20230105222413892

tcp_receiver.hh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
...
//! \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;
    bool _syn_flag;
    WrappingInt32 _isn;

  public:
 ...

tcp_receiver.cc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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) { 
    const TCPHeader &header=seg.header();
    if(!_syn_flag){
        if(!header.syn) return ;
        _isn=header.seqno;
        _syn_flag=true;

    }


    uint64_t absolute_seqno=unwrap(header.seqno,_isn, _reassembler.stream_out().bytes_written());
    
    uint64_t index=absolute_seqno -1 + header.syn;

    _reassembler.push_substring(seg.payload().copy(),index,header.fin);
}

optional<WrappingInt32> TCPReceiver::ackno() const {
    if(!_syn_flag) return nullopt;
    uint64_t ack_no=_reassembler.stream_out().bytes_written()+1;
    if (_reassembler.stream_out().input_ended())
        ++ack_no;
    return _isn+ack_no;
}

size_t TCPReceiver::window_size() const {
 return {_capacity - _reassembler.stream_out().buffer_size()}; 
}

image-20230105204943898

lab3

TCP发送器

这个lab主要在于理解。。但是文档又很长，各个点又没有总结的特别清楚。

总的来说主要是实现滑动窗口，并且是累计确认的，也就是当接收到一个ackno时，代表该ackno之前的所有段都成功被接收了。

image-20230106193633801

  • 内部使用tick() 进行计时

    • 仅有在ack_received被调用时，计时器才会移动，也就是说，计时器追踪的是 最近的一次ack_received，而不是追踪某一个seg
    • 如何判断超时？
      • 计时器超时
      • 缓冲队列不为空
    • 什么时候要增加超时时间窗口 RTO
      • 超时，且 window_size >0 , 这点在文档有说，但是window_size的判断非常容易漏

  • fill windows

    • 窗口为0的话，应该把它当成1，否则发送方有可能永远不被允许再次发送。当成1以后，发送方可能会发送一个最终被接收方拒绝的字节，但这会使得接收方发送新的ack报文，传回来window_size 将会有更多的空间。
    • payload size 与 seg length 并不一样，payload不包括 syn/fin，window包括
    • 如果没有数据，则不发送seg

  • ack_received

    • 设置RTO为初始值
    • 连续重传计数重置为0
    • 若缓存队列不为空，则重置计时器

最后调试的时候 调了好一会，一直有3个test过不了

问题出在两个地方：

  1. 计算窗口长度的时候 我一开始用的seg.length_in_sequence_space() ，后面才注意到它与payload.size()是不相等的，如果是syn的话，seg.length_in_sequence_space()会比payload.size() 大 1 。

​ 于时我改成了 seg_length -seg.header().syn ，结果还是不行。 然后改来改去死活都不行，就只有payload.size()可以，我把它们逐一输出 ，也没发现有什么区别。

​ 2. 计时器时间等于超时时间时就算超时了，我一直写的大于， test13的测试样例 刚好就是卡的等于 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//! segments if the retransmission timer expires.
class TCPSender {
  private:
    //! our initial sequence number, the number for our SYN.
    WrappingInt32 _isn;
    bool _set_syn_flag{false};
    bool _set_fin_flag{false};
    size_t _window_size{1};


    size_t _timer{0};

    size_t _bytes_in_flight{0};
    //! outbound queue of segments that the TCPSender wants sent
    std::queue<TCPSegment> _segments_out{};
    std::queue<TCPSegment> _segments_backup{};
    //! retransmission timer for the connection
    size_t _retransmission_timeout{0};
    size_t _consecutive_retransmissions_cnt{0};
    unsigned int _initial_retransmission_timeout{};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include "tcp_sender.hh"

#include "tcp_config.hh"

#include <random>
#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) {}

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

void TCPSender::fill_window() {
    size_t window_size=_window_size>0?_window_size:1;

    while(window_size > _bytes_in_flight ){
        TCPSegment seg;
        size_t seg_length;
        if(!_set_syn_flag){
            seg.header().syn=true;
            _set_syn_flag=true;
        }

        seg.header().seqno=next_seqno();
        size_t payload_size=min(TCPConfig::MAX_PAYLOAD_SIZE, window_size- _bytes_in_flight -seg.header().syn);
        string payload = _stream.read(payload_size);

        
        //size_t temp=payload.size();


        //cout<<temp.size()<<" "<<seg_length -seg.header().syn<<endl;
        
/*        if (temp != (seg_length -seg.header().syn)) {
            cout<<endl<<endl<<endl;
            cout<<temp <<" "  << " ";
            cout<<seg_length -seg.header().syn<<endl<<endl<<endl;
        }*/

        if( _stream.eof() && (  payload.size() +_bytes_in_flight  < window_size ) &&  !_set_fin_flag ){
            seg.header().fin=true;
            _set_fin_flag=true;
        }

        seg.payload()=Buffer(move(payload));
        seg_length=seg.length_in_sequence_space();

        if(!seg_length)
            break;

        if(_segments_backup.empty()){
            _retransmission_timeout=_initial_retransmission_timeout;
            _timer=0;
        }

        _segments_out.push(seg);
        _segments_backup.push(seg);

        _bytes_in_flight+=seg_length;
        _next_seqno+=seg_length;

        if(seg.header().fin)
            break;
    }

}

//! \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) { 
    size_t  absolute_seqno=unwrap(ackno,_isn,_next_seqno);
    if(absolute_seqno > _next_seqno) return ;

    while(!_segments_backup.empty()){
        TCPSegment seg=_segments_backup.front();
        if( unwrap(seg.header().seqno,_isn,_next_seqno) +seg.length_in_sequence_space()<= absolute_seqno ){
            _bytes_in_flight-=seg.length_in_sequence_space();
            _segments_backup.pop();
            _retransmission_timeout=_initial_retransmission_timeout;
            _timer=0;
        }else{
            break;
        }
    }
    _consecutive_retransmissions_cnt=0;
    _window_size=window_size;
    fill_window();

}

//! \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;
    if(!_segments_backup.empty() && (_timer >= _retransmission_timeout)){
        if(_window_size)
            _retransmission_timeout*=2;
        _segments_out.push(_segments_backup.front());
        _consecutive_retransmissions_cnt++;
        _timer=0;
    }
 }

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

void TCPSender::send_empty_segment() {
    TCPSegment seg;
    seg.header().seqno=next_seqno();
    _segments_out.push(seg);
}


lab4

最折磨的lab，test样例也没有全过

FSM状态图：

img

img

先建立链接，也就是常说的 三次握手：

起点均为 CLOSED

img

涉及4种状态

1
2
3
4
5
6
7
8
// 未发送SYN ，服务器处于监听状态 
FSM_LISTEN = SENDER_CLOSED && RECEIVER_LISTEN 
// 客户端发送了SYN，但还没有接收到服务器的ack
FSM_SYN_SENT = SENDER_SYN_SENT && RECEIVER_LISTEN
// 服务器接收到了SYN ，发送了SYN
FSM_SYN_RCVD = RECEIVER_SYN_RECV && SENDER_SYN_SENT;
// 客户端确认接收到了服务器 SYN，发送了SYN_ack
FSM_ESTABLISHED = RECEIVER_SYN_RECV && SENDER_SYN_ACKED

有了这样三次握手，才可以确保两个事实：

  1. 客户端 确认 ：服务器 可以接受到消息 ，客户端也可以收到消息

  2. 服务器 确认 ：客户端 可以接收到消息 ， 服务器也可以收到消息

    （如果是两次的话 ，就服务器无法确保客户端可以收到消息）

这样可以防止失效的连接请求到达服器，让服务器错误打开连接。客户端发送的连接请求如果在网络中滞留，那么就会隔很长一段时间才能收到服务器端发回的连接确认。客户端等待一个超时重传时间之后，就会重新请求连接。但是这个滞留的连接请求最后还是会到达服务器，如果不进行三次握手，那么服务器就会打开两个连接。如果有第三次握手，客户端会忽略服务器之后发送的对滞留连接请求的连接确认，不进行第三次握手，因此就不会再次打开连接。

结束链接， 也就是常说的 四次挥手 ：

客户端主动关闭连接 —— TCP 四次挥手

涉及六种状态：

_linger_after_streams_finish 代表数据传输完毕后是否保持tcp连接状态（stay active && keep ACKing）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 客户端发送 FIN 报文 ，此时客户端所有数据发送完毕 ,等待该FIN的ack报文
FSM_FIN_WAIT_1 = RECEIVER_SYN_RECV && SENDER_FIN_SENT
// 服务器接收客户端 FIN 报文， 返回FIN_ack报文 ，此时服务端仍然可以发送数据
FSM_CLOSE_WAIT = RECEIVER_FIN_RECV && SENDER_SYN_ACKED && (_linger_after_streams_finish = false)
// 客户端接收到 FIN_ack 报文，此时代表 客户端知道服务端已经接收了客户端所有数据，等待接受服务端所有数据
FSM_FIN_WAIT_2 = RECEIVER_SYN_RECV && SENDER_FIN_ACKED
// 服务端数据发送完毕，发送 FIN 报文， 此时服务端所有数据发送完毕，等待该FIN的ack报文
FSM_LAST_ACK = RECEIVER_FIN_RECV && SENDER_FIN_SENT && (_linger_after_streams_finish = false)
// 客户端接收到了服务端的FIN报文，返回FIN_ack报文 
FSM_TIME_WAIT = SENDER_FIN_ACKED && RECEIVER_FIN_RECV

// 对服务端而言： 接收到了 FIN_ack 报文，代表此时 服务端知道客户端已经接收了服务端的所有数据， 服务端关闭
// 对客户端而言： 等待2MSL（一个片段在网络中最大的存活时间），若没有收到回复，则代表服务端已关闭，客户端可以关闭了；如果收到回复，则说明服务器未正常关闭，有可能是服务端重发的FIN报文，这也代表客户端需要重发FIN_ack报文
FSM_CLOSED = RECEIVER_FIN_RECV && SENDER_FIN_ACKED && (_linger_after_streams_finish = false) && (_active = false)


// 比较特殊 ，少见的 closing状态：双方都发送了FIN报文，且也接收到了对方的报文FIN报文，也就是 “同时发送” 了  FIN报文，这样就会进入closing状态，两边都等待FIN_ack报文
FSM_CLOSING = RECEIVER_FIN_RECV && SENDER_FIN_SENT

这样的四次挥手，也是确认两个事实：

服务端确认 ： 服务端已发送所有数据，客户端已接受所有数据。

客户端确认： 客户端已发送所有数据，服务端已接受所有数据。

（如果少最后一次ack，服务端就不知道客户端已经接受所有数据）

为什么握手是三次，挥手是四次呢？

原因很简单，第二次握手的报文 同时充当了 SYN报文和ack报文，所以会少一次。

重置：

1
2
FSM_RESET = RECEIVER_ERROR && SENDER_ERROR && (_linger_after_streams_finish = false) &&
(_active = false)

实验要求实现TPC connection：

image-20230110222657916

两方任意一方都同时充当 sender和 receiver，负责对输入输出流的分别处理

对segment_received 函数而言 ：

  • 了解自己写的 receiver，前面lab写的过了check，但不一定过得了这次的check…（对syn之类的考虑应该在里面实现了）
  • 每次接收到报文时，除了给 receiver处理，同时还要考虑sender是否需要返回ack报文（注意，不应该有回应 ack的ack报文），一般返回长度为0的空报文 附加上ack 作为ack报文即可。
  • 如果接收到了rst 就需要停止，具体看文档。
  • 对ack报文，receiver不进行处理，但sender需要其window_size和ackno

对 sender：

没什么好说的，把自己写的_sender.fill_window() 写好些，同理，对syn之类的考虑也应该在之前实现了

至于各变量什么时候改变，参照上面的状态变量对应的值即可：

FSM_CLOSE_WAIT 和 FSM_RESET 均使得 _linger_after_streams_finish = false

FSM_CLOSED 和 FSM_RESET 均使得 _active = false

FSM_TIME_WAIT 超时以后 也可以使得 _active = false ，_linger_after_streams_finish = false

了解状态图以后 写起来就容易不少了，不然会一直debug

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#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) {
    _time_since_last_segment_received = 0;
    _receiver.segment_received(seg);
    bool _send_empty = true;

    // don't ack the ack
    if (!seg.length_in_sequence_space()) {
        _send_empty = false;
    }

    if (seg.header().rst) {
        unclean(false);
        return;
    }

    if (seg.header().ack) {
        _sender.ack_received(seg.header().ackno, seg.header().win);
        if (_send_empty && !_sender.segments_out().empty())
            _send_empty = false;
    }

    if (TCPState::state_summary(_receiver) == TCPReceiverStateSummary::SYN_RECV &&
        TCPState::state_summary(_sender) == TCPSenderStateSummary::CLOSED) {
        connect();
        return;
    }

    if (TCPState::state_summary(_receiver) == TCPReceiverStateSummary::FIN_RECV &&
        TCPState::state_summary(_sender) == TCPSenderStateSummary::SYN_ACKED)
        _linger_after_streams_finish = false;

    if (TCPState::state_summary(_receiver) == TCPReceiverStateSummary::FIN_RECV &&
        TCPState::state_summary(_sender) == TCPSenderStateSummary::FIN_ACKED && !_linger_after_streams_finish) {
        _active = false;
        return;
    }

    if (_send_empty)
        _sender.send_empty_segment();

    push_segments_out();
}

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

size_t TCPConnection::write(const string &data) {
    size_t write_cnt = _sender.stream_in().write(data);
    _sender.fill_window();
    push_segments_out();
    return write_cnt;
}

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

//! \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;
    _time_since_last_segment_received += ms_since_last_tick;
    _sender.tick(ms_since_last_tick);
    if (_sender.consecutive_retransmissions() > _cfg.MAX_RETX_ATTEMPTS) {
        // pop
        _sender.segments_out().pop();
        unclean(true);
        return;
    }
    //_sender.fill_window();
    push_segments_out();

    if (TCPState::state_summary(_receiver) == TCPReceiverStateSummary::FIN_RECV &&
        TCPState::state_summary(_sender) == TCPSenderStateSummary::FIN_ACKED && _linger_after_streams_finish &&
        _time_since_last_segment_received >= 10 * _cfg.rt_timeout) {
        _active = false;
        _linger_after_streams_finish = false;
    }
}

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

void TCPConnection::connect() {
    _active = true;
    _sender.fill_window();
    push_segments_out();
}

void TCPConnection::unclean(bool rst) {
    _active = false;
    _receiver.stream_out().set_error();
    _sender.stream_in().set_error();
    _linger_after_streams_finish = false;
    if (rst) {
        TCPSegment seg;
        seg.header().rst = true;
        _segments_out.push(seg);
    }
}

TCPConnection::~TCPConnection() {
    try {
        if (active()) {
            cerr << "Warning: Unclean shutdown of TCPConnection\n";
            unclean(false);
            // 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;
    }
}

结果：

image-20230110204008050

image-20230110211702250

一直都有随机几个是timeout，，，调不出来是什么问题 就当没看见吧

image-20230110225048877

修改webget为自己的TCPSocket：

image-20230110231851279

至此，TCP部分的实验就完结了，哪天有空我可能会再回头看进行改进(?)

lab5

实现ARP协议

整体不算很难，比较需要注意的点是，并非只能从ARP_reply中获取对方的mac，从ARP_request中也可以获取对方的mac。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class NetworkInterface {
  private:
    //! Ethernet (known as hardware, network-access-layer, or link-layer) address of the interface
    EthernetAddress _ethernet_address;

    //! IP (known as internet-layer or network-layer) address of the interface
    Address _ip_address;

    //! outbound queue of Ethernet frames that the NetworkInterface wants sent
    std::queue<EthernetFrame> _frames_out{};

    const size_t _arp_stay_ttl = 30000;  // 30 s
    const size_t _arp_wait_ttl = 5000;   // 5  s
    struct ARP_item {
        EthernetAddress mac;
        size_t ttl;
    };
    struct frame_item {
        Address ip_address;
        InternetDatagram dgram;
    };

    std::map<uint32_t, ARP_item> _arp_table{};
    std::map<uint32_t, size_t> _arp_searching_list{};
    std::list<frame_item> _arp_waiting_list{};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include "network_interface.hh"

#include "arp_message.hh"
#include "ethernet_frame.hh"

#include <iostream>

// Dummy implementation of a network interface
// Translates from {IP datagram, next hop address} to link-layer frame, and from link-layer frame to IP datagram

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

// You will need to add private members to the class declaration in `network_interface.hh`

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

using namespace std;

//! \param[in] ethernet_address Ethernet (what ARP calls "hardware") address of the interface
//! \param[in] ip_address IP (what ARP calls "protocol") address of the interface
NetworkInterface::NetworkInterface(const EthernetAddress &ethernet_address, const Address &ip_address)
    : _ethernet_address(ethernet_address), _ip_address(ip_address) {
    cerr << "DEBUG: Network interface has Ethernet address " << to_string(_ethernet_address) << " and IP address "
         << ip_address.ip() << "\n";
}

//! \param[in] dgram the IPv4 datagram to be sent
//! \param[in] next_hop the IP address of the interface to send it to (typically a router or default gateway, but may also be another host if directly connected to the same network as the destination)
//! (Note: the Address type can be converted to a uint32_t (raw 32-bit IP address) with the Address::ipv4_numeric() method.)
void NetworkInterface::send_datagram(const InternetDatagram &dgram, const Address &next_hop) {
    // convert IP address of next hop to raw 32-bit representation (used in ARP header)
    const uint32_t next_hop_ip = next_hop.ipv4_numeric();
    // search in table
    auto iter = _arp_table.find(next_hop_ip);

    if (iter == _arp_table.end()) {
        // not found in table
        if (_arp_searching_list.find(next_hop_ip) == _arp_searching_list.end()) {
            // havedn't send arp
            ARPMessage arp_msg;
            arp_msg.sender_ethernet_address = _ethernet_address;
            arp_msg.sender_ip_address = _ip_address.ipv4_numeric();
            arp_msg.target_ethernet_address = {};
            arp_msg.target_ip_address = next_hop_ip;
            arp_msg.opcode = ARPMessage::OPCODE_REQUEST;

            EthernetFrame frame;
            frame.header().dst = ETHERNET_BROADCAST;
            frame.header().src = _ethernet_address;
            frame.header().type = EthernetHeader::TYPE_ARP;
            frame.payload() = arp_msg.serialize();
            _frames_out.push(frame);

            _arp_searching_list[next_hop_ip] = _arp_wait_ttl;
        }
        struct frame_item item {
            next_hop, dgram
        };
        _arp_waiting_list.push_back(item);

    } else {
        // found in table
        EthernetFrame frame;
        frame.header().dst = iter->second.mac;
        frame.header().src = _ethernet_address;
        frame.header().type = EthernetHeader::TYPE_IPv4;
        frame.payload() = dgram.serialize();
        _frames_out.push(frame);
    }
}

//! \param[in] frame the incoming Ethernet frame
optional<InternetDatagram> NetworkInterface::recv_frame(const EthernetFrame &frame) {
    if (frame.header().dst != _ethernet_address && frame.header().dst != ETHERNET_BROADCAST)
        return nullopt;
    if (frame.header().type == EthernetHeader::TYPE_IPv4) {
        InternetDatagram dgram;
        if (dgram.parse(frame.payload()) == ParseResult::NoError)
            return dgram;
        return nullopt;
    } else if (frame.header().type == EthernetHeader::TYPE_ARP) {
        ARPMessage arp_msg;
        if (arp_msg.parse(frame.payload()) != ParseResult::NoError)
            return nullopt;

        if (arp_msg.opcode == ARPMessage::OPCODE_REQUEST && arp_msg.target_ip_address == _ip_address.ipv4_numeric()) {
            // arp request
            ARPMessage arp_reply;
            arp_reply.opcode = ARPMessage::OPCODE_REPLY;
            arp_reply.sender_ethernet_address = _ethernet_address;
            arp_reply.sender_ip_address = _ip_address.ipv4_numeric();
            arp_reply.target_ethernet_address = arp_msg.sender_ethernet_address;
            arp_reply.target_ip_address = arp_msg.sender_ip_address;

            EthernetFrame frame_t;
            frame_t.header().dst = arp_msg.sender_ethernet_address;
            frame_t.header().src = _ethernet_address;
            frame_t.header().type = EthernetHeader::TYPE_ARP;
            frame_t.payload() = arp_reply.serialize();
            _frames_out.push(frame_t);
        }
        if ((arp_msg.opcode == ARPMessage::OPCODE_REQUEST && arp_msg.target_ip_address == _ip_address.ipv4_numeric()) ||
            (arp_msg.opcode == ARPMessage::OPCODE_REPLY && arp_msg.target_ethernet_address == _ethernet_address)) {
            // arp reply

            ARP_item item;
            item.mac = arp_msg.sender_ethernet_address;
            item.ttl = _arp_stay_ttl;
            _arp_table[arp_msg.sender_ip_address] = item;
            for (auto iter = _arp_waiting_list.begin(); iter != _arp_waiting_list.end();) {
                if (iter->ip_address.ipv4_numeric() == arp_msg.sender_ip_address) {
                    send_datagram(iter->dgram, iter->ip_address);
                    iter = _arp_waiting_list.erase(iter);

                } else {
                    iter++;
                }
            }
            _arp_searching_list.erase(arp_msg.sender_ip_address);
        }
    }
    return nullopt;
}

//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void NetworkInterface::tick(const size_t ms_since_last_tick) {
    for (auto iter = _arp_table.begin(); iter != _arp_table.end();) {
        if (iter->second.ttl <= ms_since_last_tick) {
            iter = _arp_table.erase(iter);
        } else {
            iter->second.ttl -= ms_since_last_tick;
            iter++;
        }
    }

    for (auto iter = _arp_searching_list.begin(); iter != _arp_searching_list.end();) {
        if (iter->second <= ms_since_last_tick) {
            ARPMessage arp_msg;
            arp_msg.sender_ethernet_address = _ethernet_address;
            arp_msg.sender_ip_address = _ip_address.ipv4_numeric();
            arp_msg.target_ethernet_address = {};
            arp_msg.target_ip_address = iter->first;
            arp_msg.opcode = ARPMessage::OPCODE_REQUEST;

            EthernetFrame frame;
            frame.header().dst = ETHERNET_BROADCAST;
            frame.header().src = _ethernet_address;
            frame.header().type = EthernetHeader::TYPE_ARP;
            frame.payload() = arp_msg.serialize();
            _frames_out.push(frame);

            iter->second = _arp_wait_ttl;
        } else {
            iter->second -= ms_since_last_tick;
            iter++;
        }
    }
}

结果：

image-20230111170241462

lab6

实现简单的路由转发，代码就不贴了

image-20230112154149848