Program Structure and Design

计时器结构

首先这里也是需要一个计时器结构的，由于这里还是通过 tick 方法传入距离上次调用过去了多长时间，和之前的 check3 类似，所以我也采用了相似的做法，写了一个 timer 来统一管理计时，由于这里的request和record有两种不同的过期时间，所以我选择用继承的方式来实现两种不同的timer

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
class BasicTimer
{
protected:
  bool is_running_;
  uint64_t time_passed_;

public:
  BasicTimer& operator=( const BasicTimer& tm ) = default;
  BasicTimer() : is_running_( false ), time_passed_( 0 ) {};
  void tick( uint64_t ms_since_last_tick ) { time_passed_ += ms_since_last_tick; }
  void start()
  {
    if ( is_running_ ) {
      throw std::runtime_error( "Starting a started timer" );
    } else {
      is_running_ = true;
      time_passed_ = 0;
    }
  }
  void stop()
  {
    if ( !is_running_ ) {
      throw std::runtime_error( "Stopping a not running timer" );
    } else {
      is_running_ = false;
    }
  }
  void reset_time()
  {
    time_passed_ = 0;
    is_running_ = true;
  }
  bool is_running() const { return is_running_; }
  virtual bool is_expired() const = 0;
};

class ArpRequestTimer : public BasicTimer
{
private:
  const uint64_t expire_time = 5 * 1000;

public:
  ArpRequestTimer() : BasicTimer() {};
  ArpRequestTimer& operator=( const ArpRequestTimer& tm ) = default;
  bool is_expired() const override { return is_running_ && time_passed_ >= expire_time; };
};

class ArpRecordTimer : public BasicTimer
{
private:
  const uint64_t expire_time = 30 * 1000;

public:
  ArpRecordTimer() : BasicTimer() {};
  ArpRecordTimer& operator=( const ArpRecordTimer& tm ) = default;
  bool is_expired() const override { return is_running_ && time_passed_ >= expire_time; };
};

但是现在看起来这个设计很冗余，不应该用继承，可以直接写一个模版来实现：

1
2
template<int expire_time>
class Timer

然后后面直接

1
2
using ArpRequestTimer = Timer<5>
using ArpRecordTimer = Timer<30>

就行了

缓存已经发送的Arp请求

这里我选择一个

1
std::unordered_map<uint32_t, ArpRequestTimer> arp_request_timers_ {};

结构来缓存已经发送但没有得到回复的Arp请求，这里面前面的 uint32_t 记录的是请求的 ip 地址，后面的timer进行计时

缓存因没有获得Mac而无法发送的消息

我使用结构

1
map<uint32_t, queue<InternetDatagram>> dgram_waiting_list_ {};

来实现，其实这里应该用 unordered_map 但在 uint32_t 这个范围下面应该差距不大

缓存arp记录

使用如下结构进行arp记录的缓存：

1
2
using arp_record = std::pair<EthernetAddress, ArpRecordTimer>;
map<uint32_t, arp_record> arp_table_ {};

这里的每一条记录都由一个Mac地址和一个timer组成

具体api的实现

这里的实现就是翻译文档就行了，没什么技术含量，也没什么坑，不过我这里设计了一个函数来辅助更新ip和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
26
27
28
29
30
31
32
33
34
35
void NetworkInterface::handle_ip_ethernet_update_and_send( uint32_t ip, EthernetAddress eth )
{
  // check whether there is a ARP request in air
  auto arp_rq_it = arp_request_timers_.find( ip );
  if ( arp_rq_it != arp_request_timers_.end() ) {
    arp_request_timers_.erase( arp_rq_it );
  }

  // add this record to list and start the timer
  auto arp_rec_it = arp_table_.find( ip );
  if ( arp_rec_it != arp_table_.end() ) {
    // 1. if the record is already in the list, renew the record and reset the timer
    arp_rec_it->second.first = eth;
    arp_rec_it->second.second.reset_time();
  } else {
    // 2. if the this is a new record, add it to the list and start the timer
    arp_table_.emplace( ip, std::make_pair( eth, ArpRecordTimer() ) );
    arp_table_[ip].second.start();
  }

  // Check if there is any datagram waiting for this ARP reply
  auto it = dgram_waiting_list_.find( ip );
  if ( it != dgram_waiting_list_.end() ) {
    // There are datagrams waiting for this ARP reply
    while ( !it->second.empty() ) {
      InternetDatagram dgram = it->second.front();
      it->second.pop();
      EthernetFrame frame { .header = { .dst = eth, .src = ethernet_address_, .type = EthernetHeader::TYPE_IPv4 },
                            .payload = serialize( dgram ) };
      this->transmit( frame );
    }
    dgram_waiting_list_.erase( it );
  }
}

这样在recv一个arp报文的时候，无论是请求还是回复都可以正确地更新，并且省去了重复的代码量

Implementation Challenges

测试用例有个比较迷惑的地方，某些包的ip不是本地的ip但是mac是本地的mac，这些包应该是被接受的，但是最开始我校验了ip反而过不了样例

Remaining Bugs

我认为是没有bug的

Experimental results and performance.


这里面感觉把所有的map换成unordered应该更快