CS144 Lab

学习笔记 / 计算机网络
字数统计: 3.8k   |   阅读时长≈ 21 分钟
  1. Checkpoint 0: networking warmup
    1. warmup
    2. webget
    3. byte_stream
  2. Checkpoint 1: stitching substrings into a byte stream
  3. CheckPoint 1.5 Optimizing ByteStream
  4. Check2
  5. Check 3
  6. Check 5
  7. Check6
  8. Check 7

学二进制的不懂计网很正常吧…
潦草记录,只是证明没在摆烂…



Checkpoint 0: networking warmup

warmup

使用telnet发http报文

nc监听并与telnet交互:

webget

编写webget,刚开始时报getaddrinfo(cs144.keithw.org, http): Servname not supported for ai_socktype,查阅发现getaddrinfo是从/etc/services查询服务对应的端口,而我使用的docker环境中没有这一文件,从主机上拷贝过来即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void get_URL( const string& host, const string& path )
{
  cerr << "Function called: get_URL(" << host << ", " << path << ")\n";
  TCPSocket tsocket;
  string read_buf;
  tsocket.connect( Address { host, "http" } );

  tsocket.write( "GET " + path + " HTTP/1.1\r\n" );
  tsocket.write( "Host: " + host + "\r\n" );
  tsocket.write( "Connection: close\r\n" );
  tsocket.write( "\r\n" );

  while ( !tsocket.eof() ) {
    tsocket.read( read_buf );
    cout << read_buf;
  }

  tsocket.close();
}

byte_stream

编写内存中可靠的字节流(其实不可靠,容量满了直接丢了).
使用deque做底层缓冲区: 双端开口,”连续”空间.

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
#pragma once

#include <cstdint>
#include <deque>
#include <string>
#include <string_view>

class Reader;
class Writer;

class ByteStream
{
public:
  explicit ByteStream( uint64_t capacity );

  // Helper functions (provided) to access the ByteStream's Reader and Writer interfaces
  Reader& reader();
  const Reader& reader() const;
  Writer& writer();
  const Writer& writer() const;

  void set_error() { error_ = true; };       // Signal that the stream suffered an error.
  bool has_error() const { return error_; }; // Has the stream had an error?

protected:
  // Please add any additional state to the ByteStream here, and not to the Writer and Reader interfaces.
  uint64_t capacity_;
  std::deque<char> buffer_ {};
  bool error_ {};
  bool closed_ {};
  uint64_t bytes_pushed_ {};
  uint64_t bytes_popped_ {};
  std::string tmp_buf_;
};

class Writer : public ByteStream
{
public:
  void push( std::string data ); // Push data to stream, but only as much as available capacity allows.
  void close();                  // Signal that the stream has reached its ending. Nothing more will be written.

  bool is_closed() const;              // Has the stream been closed?
  uint64_t available_capacity() const; // How many bytes can be pushed to the stream right now?
  uint64_t bytes_pushed() const;       // Total number of bytes cumulatively pushed to the stream
};

class Reader : public ByteStream
{
public:
  std::string_view peek() const; // Peek at the next bytes in the buffer
  void pop( uint64_t len );      // Remove `len` bytes from the buffer

  bool is_finished() const;        // Is the stream finished (closed and fully popped)?
  uint64_t bytes_buffered() const; // Number of bytes currently buffered (pushed and not popped)
  uint64_t bytes_popped() const;   // Total number of bytes cumulatively popped from stream
};

/*
 * read: A (provided) helper function thats peeks and pops up to `len` bytes
 * from a ByteStream Reader into a string;
 */
void read( Reader& reader, uint64_t len, std::string& out );

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"

using namespace std;

ByteStream::ByteStream( uint64_t capacity ) : 
capacity_( capacity ) {}

bool Writer::is_closed() const
{
  return closed_;
}

void Writer::push( string data )
{
  for(const auto ch : data)
  {
    if(available_capacity())
    {
      buffer_.push_back(ch);
      bytes_pushed_++;
    }
  }
  tmp_buf_ = string(buffer_.begin(),buffer_.end());
  return;
}

void Writer::close()
{
  closed_ = true;
}

uint64_t Writer::available_capacity() const
{
  return capacity_-buffer_.size();
}

uint64_t Writer::bytes_pushed() const
{
  return bytes_pushed_;
}

bool Reader::is_finished() const
{
  return closed_&&!bytes_buffered();
}

uint64_t Reader::bytes_popped() const
{
  return bytes_popped_;
}

string_view Reader::peek() const
{
  return string_view(tmp_buf_);
}

void Reader::pop( uint64_t len )
{
  while ((buffer_.size()&&len--))
  {
    buffer_.pop_front();
    bytes_popped_++;
  }
  tmp_buf_ = string(buffer_.begin(),buffer_.end());
}

uint64_t Reader::bytes_buffered() const
{
  return buffer_.size();
}

但是效率非常慢,0.11Gbit/s勉强过最低要求

1
2
3
4
5
6
7
8
        Start 38: byte_stream_speed_test
             ByteStream throughput: 0.11 Gbit/s
10/10 Test #38: byte_stream_speed_test ...........   Passed    0.80 sec

100% tests passed, 0 tests failed out of 10

Total Test time (real) =   3.60 sec
Built target check0

Checkpoint 1: stitching substrings into a byte stream

调试准备

1
set (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wpedantic -Wextra -Weffc++ -Werror -Wshadow -Wpointer-arith -Wcast-qual -Wformat=2 -Wno-unqualified-std-cast-call -Wno-non-virtual-dtor -g -O0 -fdebug-prefix-map='/root/minnow/build'='.'")

实现思路

用vector<char>做缓冲区,接受[unassembled_idx,unassembled_idx+capacity)区间内的数据并保存,其余的丢弃,使用valid_mask标识对应位置的数据是否已经保存到Reassembler中.

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
class Reassembler
{
public:
  // Construct Reassembler to write into given ByteStream.
  explicit Reassembler( ByteStream&& output );

  /*
   * Insert a new substring to be reassembled into a ByteStream.
   *   `first_index`: the index of the first byte of the substring
   *   `data`: the substring itself
   *   `is_last_substring`: this substring represents the end of the stream
   *   `output`: a mutable reference to the Writer
   *
   * The Reassembler's job is to reassemble the indexed substrings (possibly out-of-order
   * and possibly overlapping) back into the original ByteStream. As soon as the Reassembler
   * learns the next byte in the stream, it should write it to the output.
   *
   * If the Reassembler learns about bytes that fit within the stream's available capacity
   * but can't yet be written (because earlier bytes remain unknown), it should store them
   * internally until the gaps are filled in.
   *
   * The Reassembler should discard any bytes that lie beyond the stream's available capacity
   * (i.e., bytes that couldn't be written even if earlier gaps get filled in).
   *
   * The Reassembler should close the stream after writing the last byte.
   */
  void insert( uint64_t first_index, std::string data, bool is_last_substring );

  // How many bytes are stored in the Reassembler itself?
  uint64_t bytes_pending() const;

  // Access output stream reader
  Reader& reader() { return output_.reader(); }
  const Reader& reader() const { return output_.reader(); }

  // Access output stream writer, but const-only (can't write from outside)
  const Writer& writer() const { return output_.writer(); }

private:
  ByteStream output_; // the Reassembler writes to this ByteStream
  size_t capacity {};
  std::vector<char> buffer;
  std::vector<bool> valid_mask;
  size_t unassembled_idx {};
  uint64_t total_bytes {};
  bool total_bytes_mask {};
};
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
#include "reassembler.hh"

using namespace std;

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )
{
  //重组数据
  //data是否有在当前buffer区域内的部分
  if(first_index+data.size()>=unassembled_idx && first_index<unassembled_idx+capacity)
  {
    //截断unassembled_idx之前的部分
    if(first_index < unassembled_idx)
    {
      data = data.substr(unassembled_idx-first_index);
      first_index = unassembled_idx;
    }

    //保存最后一个字节的位置
    if(is_last_substring)
    {
      total_bytes_mask = true;
      total_bytes = first_index+data.size();
    }
    auto psize = min(data.size(),
    unassembled_idx+capacity-first_index);


    auto start = std::next(buffer.begin(),first_index-unassembled_idx);
    std::copy_n(data.begin(),psize,start);
    
    auto mask_start = std::next(valid_mask.begin(),first_index-unassembled_idx);
    std::fill_n(mask_start,psize,true);
  }

  //尝试output
  auto mask_iter = valid_mask.begin();
  auto& writer_ref = static_cast<Writer&>(output_);
  for(;mask_iter!=valid_mask.end()&&*mask_iter==true;++mask_iter);
  
  if(mask_iter != valid_mask.begin())
  {
    auto output_end = std::next(buffer.begin(),(mask_iter-valid_mask.begin()));

    writer_ref.push(std::string(buffer.begin(),output_end));
    unassembled_idx = writer_ref.bytes_pushed();

    //输出完成后移动unassembled的数据
    std::copy(output_end,buffer.end(),buffer.begin());
    auto invalid_iter = std::copy(mask_iter,valid_mask.end(),valid_mask.begin());
    std::fill(invalid_iter,valid_mask.end(),false);
  }

  if(total_bytes_mask&&writer_ref.bytes_pushed() == total_bytes)
      writer_ref.close();

}

uint64_t Reassembler::bytes_pending() const
{
  // Your code here.
  uint64_t pendings = 0;
  for(const auto b : valid_mask)
  {
    if(b)
      ++pendings;
  }
  return pendings;
}


Reassembler::Reassembler( ByteStream&& output ): 
output_( std::move( output ) ),capacity(writer().available_capacity()),
buffer(capacity) , valid_mask(capacity,false) 
{

}

平均用时8秒多,1.10 Gbit/s,非常慢了.

1
2
3
4
5
6
7
8
9
10
11
12
15/17 Test #37: compile with optimization ........   Passed    0.07 sec
      Start 38: byte_stream_speed_test
             ByteStream throughput: 0.10 Gbit/s
16/17 Test #38: byte_stream_speed_test ...........   Passed    0.84 sec
      Start 39: reassembler_speed_test
             Reassembler throughput: 1.10 Gbit/s
17/17 Test #39: reassembler_speed_test ...........   Passed    0.22 sec

100% tests passed, 0 tests failed out of 17

Total Test time (real) =   8.56 sec
Built target check1

CheckPoint 1.5 Optimizing ByteStream

1.5.1 一次性insert和erase

把push和pop改成一次性insert和erase,Reassembler throughput提升到4.40 Gbit/s,ByteStream throughput仍为0.1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Writer::push( string data )
{
  size_t ilen = min(data.size(),available_capacity());
  buffer_.insert(buffer_.end(),data.begin(),data.begin()+ilen);
  bytes_pushed_ += ilen;
  tmp_buf_ = string(buffer_.begin(),buffer_.end());
  return;
}

void Reader::pop( uint64_t len )
{
  size_t rlen = min(len,buffer_.size());
  buffer_.erase(buffer_.begin(),buffer_.begin()+rlen);
  bytes_popped_ += rlen;
  tmp_buf_ = string(buffer_.begin(),buffer_.end());
}

1.5.2 以string替代char作为字节流基本单元

全部重构了,改为直接插入string能节省大量对deque的插入操作.
能这么写是peek不要求返回字节流内所有的字节.
ByteStream throughput: 10.21 Gbit/s,Reassembler throughput: 5.36 Gbit/s.

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
std::queue<std::string> buffer_;

void Writer::push( string data )
{
  size_t ilen = min(data.size(),available_capacity());
  if(ilen)
  {
    data.resize(ilen);

    buffer_.push(data);
    bytes_pushed_ += ilen;
    size_ += ilen;

    if(buffer_.size() == 1)
    {
      view_buf_ = std::string(buffer_.front());
    }

  }
  return;
}


string_view Reader::peek() const
{
  return view_buf_;
}

void Reader::pop( uint64_t len )
{
  size_t rlen = min(len,size_);
  size_t rlen_remaind = rlen;
  if(rlen)
  {
    while(!buffer_.empty() && rlen_remaind >= buffer_.front().size())
    {
      rlen_remaind -= buffer_.front().size();
      buffer_.pop();
    }

    bytes_popped_ += rlen;
    size_ -= rlen;

    if(!buffer_.empty())
    {
      buffer_.front() = buffer_.front().substr(rlen_remaind);
      view_buf_ = std::string(buffer_.front());
    }
    else
      view_buf_ = std::string();
  }
}

Reassembler的优化放到之后,大概看了一下是vector容量过大时,每一次输出会导致大量的数据拷贝和填充.

Check2

实现TCP接收端的数据重组.

2.1 Translating between 64-bit indexes and 32-bit seqnos

wrap直接用cpp本身的截断即可.unwrap主要基于 A-B的结果再截断与先将A,B截断再相减(再截断)的值是相同的.
(我是数学白痴…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "wrapping_integers.hh"

using namespace std;

Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point )
{
  return Wrap32 { zero_point+n };
}

uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const
{
  uint32_t ckmod = wrap(checkpoint,zero_point).raw_value_;
  uint32_t off = raw_value_-ckmod;
  uint64_t upper = static_cast<uint64_t>(UINT32_MAX)+1;
  
  if(off <= (upper>>1) || checkpoint+off<upper)
    return static_cast<uint64_t>(checkpoint+off);

  return static_cast<uint64_t>(checkpoint+off-upper);

}

很乱的草稿..

2.2 Implementing the TCP receive

实验文档挺模糊的,甚至感觉有歧义,大概写完对着测试改一改.

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
void TCPReceiver::receive( TCPSenderMessage message )
{
  if(message.SYN)
    ISN = message.seqno;
  
  if(ISN.has_value())
  {
    uint64_t first_index = message.seqno.unwrap(*ISN,writer().bytes_pushed())+message.SYN-1;
    reassembler_.insert(first_index,message.payload,message.FIN);
  }

  if(message.RST)
  {
    reader().set_error();
  }
  
}

TCPReceiverMessage TCPReceiver::send() const
{
  TCPReceiverMessage message {};
  if(ISN.has_value())
  {
    message.ackno = Wrap32::wrap(writer().bytes_pushed()+1+writer().is_closed(),*ISN);
  }
  message.window_size = min(writer().available_capacity(),static_cast<uint64_t>(UINT16_MAX));

  message.RST = writer().has_error(); 
  return message;
}

Check 3

实现TCP的超时重传,建立与断开连接,所以需要在内部保存发送的message.选择什么样的数据结构呢?
在两个情形下会查找内部保存的message,1是tick时重发超时的message,这是过期时间与message的对应关系.
2是收到对某消息的确认时,需要从内部移除该message,这是ackno与message的对应.
两种情形都偏向有排序和查找的意思,这里使用map<ackno,pair<expire_time,message> >的数据结构来保存消息.

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

class TCPSender
{
public:
  /* Construct TCP sender with given default Retransmission Timeout and possible ISN */
  TCPSender( ByteStream&& input, Wrap32 isn, uint64_t initial_RTO_ms )
    : input_( std::move( input ) ), isn_( isn ), initial_RTO_ms_( initial_RTO_ms ),RTO_ms(initial_RTO_ms)
  {}

  /* Generate an empty TCPSenderMessage */
  TCPSenderMessage make_empty_message() const;

  /* Receive and process a TCPReceiverMessage from the peer's receiver */
  void receive( const TCPReceiverMessage& msg );

  /* Type of the `transmit` function that the push and tick methods can use to send messages */
  using TransmitFunction = std::function<void( const TCPSenderMessage& )>;

  /* Push bytes from the outbound stream */
  void push( const TransmitFunction& transmit );

  /* Time has passed by the given # of milliseconds since the last time the tick() method was called */
  void tick( uint64_t ms_since_last_tick, const TransmitFunction& transmit );

  // Accessors
  uint64_t sequence_numbers_in_flight() const;  // How many sequence numbers are outstanding?
  uint64_t consecutive_retransmissions() const; // How many consecutive *re*transmissions have happened?
  Writer& writer() { return input_.writer(); }
  const Writer& writer() const { return input_.writer(); }

  // Access input stream reader, but const-only (can't read from outside)
  const Reader& reader() const { return input_.reader(); }

private:
  // Variables initialized in constructor
  ByteStream input_;
  Wrap32 isn_;
  uint64_t initial_RTO_ms_;

  std::map<Wrap32,std::pair<uint64_t,TCPSenderMessage> > rt_segments;
  uint64_t RTO_ms;
  uint64_t cur_ms;
  std::optional<uint64_t> window_size {};
  uint64_t retransmissions_cnt {};
  uint64_t in_flight_cnt;
  bool syned {};
  bool fined {};
  bool zero_window {};
};

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
#include "tcp_sender.hh"
#include "tcp_config.hh"

using namespace std;

uint64_t TCPSender::sequence_numbers_in_flight() const
{
  return in_flight_cnt;
}

uint64_t TCPSender::consecutive_retransmissions() const
{
  return retransmissions_cnt;
}

void TCPSender::push( const TransmitFunction& transmit )
{


  while (!syned || ((reader().bytes_buffered() || (reader().is_finished() && !fined)) && *window_size) )
  {
    TCPSenderMessage msg {};
    uint64_t tmp_window_size = window_size.has_value() ? *window_size : 1;

    if(!syned)
      msg.SYN = true;
    
    msg.seqno = Wrap32::wrap(reader().bytes_popped()+syned,isn_);

    uint64_t max_payload_len = min(TCPConfig::MAX_PAYLOAD_SIZE,tmp_window_size);
    max_payload_len -= msg.SYN;
    read(input_.reader(),max_payload_len,msg.payload);

    if(reader().is_finished() && ((tmp_window_size-msg.SYN) > msg.sequence_length()))
    {
      msg.FIN = true;  
      fined = true;
    }
    
    if(reader().has_error())
      msg.RST = true;

    rt_segments.insert( {Wrap32::wrap(reader().bytes_popped()+syned+msg.SYN+msg.FIN,isn_), {cur_ms+RTO_ms,msg} } );
    transmit(msg);

    syned = true;
    in_flight_cnt += msg.sequence_length();
    if(window_size.has_value())
      *window_size -= msg.sequence_length();
  }
  


}

TCPSenderMessage TCPSender::make_empty_message() const
{
  TCPSenderMessage message {};
  
  message.seqno = Wrap32::wrap(reader().bytes_popped()+syned+fined,isn_);
  if(reader().has_error())
    message.RST = true;

  return message;
}

void TCPSender::receive( const TCPReceiverMessage& msg )
{
  bool newdata_flag = (msg.ackno.has_value() && msg.ackno >= (*rt_segments.begin()).first);
  if(msg.ackno.has_value())
  {
    if(!rt_segments.empty() && msg.ackno <= (*rt_segments.rbegin()).first)
    {
      for(auto iter = rt_segments.begin();iter!=rt_segments.upper_bound(*msg.ackno);++iter)
      {
        in_flight_cnt -= (*iter).second.second.sequence_length();
        rt_segments.erase(iter);
      }
    }
  }

  if(newdata_flag)
  {
    RTO_ms = initial_RTO_ms_;
    retransmissions_cnt = 0;
    for(auto& f : rt_segments)
    {
      f.second.first = cur_ms+RTO_ms;
    }
  }
  window_size = msg.ackno->unwrap(isn_,reader().bytes_popped()+syned+fined)  - (reader().bytes_popped()+syned+fined) + (msg.window_size ? msg.window_size : 1);

  zero_window = !msg.window_size;
  if(msg.RST)
    input_.reader().set_error();
}



void TCPSender::tick( uint64_t ms_since_last_tick, const TransmitFunction& transmit )
{
  cur_ms += ms_since_last_tick;
  if(!rt_segments.empty())
  {
    auto& f = *rt_segments.begin();
    if(f.second.first <= cur_ms)
    {
      if(!zero_window)
        RTO_ms += RTO_ms;
      f.second.first = cur_ms+RTO_ms;
      transmit(f.second.second);
      ++retransmissions_cnt;
    }
  }
}


Check 5

实现ARP协议,将IP数据报发送给下一跳.
核心数据结构如下.

1
2
3
4
5
6
7
8
9
10
11

/*从IP地址到以太网地址的映射,由于对每条记录要维护一个过期时间,所以值是air<expire_time,EthernetAddress>*/
  std::unordered_map<uint32_t,std::pair<uint64_t, EthernetAddress> > ARP_table {};

/* 等待目的IP地址的ARP解析中的IP数据报,便于获取到某个IP地址对应的EthernetAddress后发送对应数据报
*/
  std::unordered_multimap<uint32_t,InternetDatagram> dgrams_waiting {}; 

/* 对某IP发送ARP解析时的时间,避免flooding.
*/
  std::unordered_map<uint32_t,uint64_t> ips_waiting {};
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
#pragma once

#include <queue>
#include <map>
#include <unordered_map>

#include "address.hh"
#include "ethernet_frame.hh"
#include "ipv4_datagram.hh"

// A "network interface" that connects IP (the internet layer, or network layer)
// with Ethernet (the network access layer, or link layer).

// This module is the lowest layer of a TCP/IP stack
// (connecting IP with the lower-layer network protocol,
// e.g. Ethernet). But the same module is also used repeatedly
// as part of a router: a router generally has many network
// interfaces, and the router's job is to route Internet datagrams
// between the different interfaces.

// The network interface translates datagrams (coming from the
// "customer," e.g. a TCP/IP stack or router) into Ethernet
// frames. To fill in the Ethernet destination address, it looks up
// the Ethernet address of the next IP hop of each datagram, making
// requests with the [Address Resolution Protocol](\ref rfc::rfc826).
// In the opposite direction, the network interface accepts Ethernet
// frames, checks if they are intended for it, and if so, processes
// the the payload depending on its type. If it's an IPv4 datagram,
// the network interface passes it up the stack. If it's an ARP
// request or reply, the network interface processes the frame
// and learns or replies as necessary.
class NetworkInterface
{
public:
  // An abstraction for the physical output port where the NetworkInterface sends Ethernet frames
  class OutputPort
  {
  public:
    virtual void transmit( const NetworkInterface& sender, const EthernetFrame& frame ) = 0;
    virtual ~OutputPort() = default;
  };

  // Construct a network interface with given Ethernet (network-access-layer) and IP (internet-layer)
  // addresses
  NetworkInterface( std::string_view name,
                    std::shared_ptr<OutputPort> port,
                    const EthernetAddress& ethernet_address,
                    const Address& ip_address );

  // Sends an Internet datagram, encapsulated in an Ethernet frame (if it knows the Ethernet destination
  // address). Will need to use [ARP](\ref rfc::rfc826) to look up the Ethernet destination address for the next
  // hop. Sending is accomplished by calling `transmit()` (a member variable) on the frame.
  void send_datagram( const InternetDatagram& dgram, const Address& next_hop );

  // Receives an Ethernet frame and responds appropriately.
  // If type is IPv4, pushes the datagram to the datagrams_in queue.
  // If type is ARP request, learn a mapping from the "sender" fields, and send an ARP reply.
  // If type is ARP reply, learn a mapping from the "sender" fields.
  void recv_frame( const EthernetFrame& frame );

  // Called periodically when time elapses
  void tick( size_t ms_since_last_tick );

  // Accessors
  const std::string& name() const { return name_; }
  const OutputPort& output() const { return *port_; }
  OutputPort& output() { return *port_; }
  std::queue<InternetDatagram>& datagrams_received() { return datagrams_received_; }

private:
  // Human-readable name of the interface
  std::string name_;

  // The physical output port (+ a helper function `transmit` that uses it to send an Ethernet frame)
  std::shared_ptr<OutputPort> port_;
  void transmit( const EthernetFrame& frame ) const { port_->transmit( *this, frame ); }

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

  // Datagrams that have been received
  std::queue<InternetDatagram> datagrams_received_ {};

  uint64_t cur_ms {};

/*从IP地址到以太网地址的映射,由于对每条记录要维护一个过期时间,所以值是air<expire_time,EthernetAddress>*/
  std::unordered_map<uint32_t,std::pair<uint64_t, EthernetAddress> > ARP_table {};

/* 等待目的IP地址的ARP解析中的IP数据报,便于获取到某个IP地址对应的EthernetAddress后发送对应数据报
*/
  std::unordered_multimap<uint32_t,InternetDatagram> dgrams_waiting {}; 

/* 对某IP发送ARP解析时的时间,避免flooding.
*/
  std::unordered_map<uint32_t,uint64_t> ips_waiting {};
};

Check6

根据最长前缀匹配进行路由转发(不包括路由选择).也就是为Check5那一层选择next_hop的ip.

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
#pragma once

#include <memory>
#include <optional>
#include <map>

#include "exception.hh"
#include "network_interface.hh"

// \brief A router that has multiple network interfaces and
// performs longest-prefix-match routing between them.
class Router
{
public:
  // Add an interface to the router
  // \param[in] interface an already-constructed network interface
  // \returns The index of the interface after it has been added to the router
  size_t add_interface( std::shared_ptr<NetworkInterface> interface )
  {
    _interfaces.push_back( notnull( "add_interface", std::move( interface ) ) );
    return _interfaces.size() - 1;
  }

  // Access an interface by index
  std::shared_ptr<NetworkInterface> interface( const size_t N ) { return _interfaces.at( N ); }

  // Add a route (a forwarding rule)
  void add_route( uint32_t route_prefix,
                  uint8_t prefix_length,
                  std::optional<Address> next_hop,
                  size_t interface_num );

  // Route packets between the interfaces
  void route();

private:
  // The router's collection of network interfaces
  std::vector<std::shared_ptr<NetworkInterface>> _interfaces {};

  struct prefix_info
  {
    prefix_info(const uint8_t prefix_lenth,const uint32_t route_prefix) :
    mask(~(UINT32_MAX >> (prefix_lenth))),prefix(route_prefix) {}

    auto operator>(const prefix_info& other) const
    {
      return mask != other.mask ? (mask > other.mask)
                 : (prefix > other.prefix);
    }
    uint32_t mask;
    uint32_t prefix;
  };
  
  using RouterT = std::map<prefix_info,std::pair<size_t,std::optional<Address> >,std::greater<prefix_info>>;

  RouterT RouterTable {};
};

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
#include "router.hh"

#include <iostream>
#include <limits>

using namespace std;

// route_prefix: The "up-to-32-bit" IPv4 address prefix to match the datagram's destination address against
// prefix_length: For this route to be applicable, how many high-order (most-significant) bits of
//    the route_prefix will need to match the corresponding bits of the datagram's destination address?
// next_hop: The IP address of the next hop. Will be empty if the network is directly attached to the router (in
//    which case, the next hop address should be the datagram's final destination).
// interface_num: The index of the interface to send the datagram out on.
void Router::add_route( const uint32_t route_prefix,
                        const uint8_t prefix_length,
                        const optional<Address> next_hop,
                        const size_t interface_num )
{
  cerr << "DEBUG: adding route " << Address::from_ipv4_numeric( route_prefix ).ip() << "/"
       << static_cast<int>( prefix_length ) << " => " << ( next_hop.has_value() ? next_hop->ip() : "(direct)" )
       << " on interface " << interface_num << "\n";

  // Your code here.
  RouterTable.emplace(prefix_info(prefix_length,route_prefix),
                                make_pair(interface_num,next_hop));
}

// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
void Router::route()
{
  for(auto pNetInterface : _interfaces)
  {
    auto& incoming_dgrams = pNetInterface->datagrams_received();
    while(!incoming_dgrams.empty())
    {
      auto& dgram = incoming_dgrams.front();
      if(dgram.header.ttl <= 1)
      {
        incoming_dgrams.pop();
        continue;
      }
      
      for(auto& RTE : RouterTable)
      {
        if((dgram.header.dst & RTE.first.mask) == RTE.first.prefix)
        {
          --dgram.header.ttl;
          dgram.header.compute_checksum();

          const auto& [interface_num,next_hop] = RTE.second;
          _interfaces[interface_num]->send_datagram(dgram,(next_hop.has_value() ? *next_hop : Address::from_ipv4_numeric(dgram.header.dst)));

          incoming_dgrams.pop();
          break;
        }
      }
    }
  }
}

Check 7


  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2024 翰青HanQi

请我喝杯咖啡吧~

支付宝
微信