CS144-check5

overview

在这个checkpoint中，我们需要实现network interface，即网络接口。一台路由器/主机会有多个网络接口。我们实现的network interface，连接了物理层和链路层，即会将IP报文封装成Ethernet frame。

现在我们需要研究怎么正确地封装，并附上正确的物理地址。

一般来说，我们会在网络接口处维护一张IP地址-MAC地址的转换表，并按照这个表，根据IP地址，为封装附上物理地址。

当我们在表中查不到时，需要用到ARP协议。具体可以看书，大概就是如何请求物理地址的协议。下文就是其具体的实现。

implement

实现的过程很快，大概几个小时。基本完全按照实验的要求来写，去掉一些语法错误之后一次就通过了测试。

members

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
class NetworkInterface
{
...
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_ {};

  // Mapping between next-hop IP address and Ethernet address
  // recording entry's exist time, delete entry if exceed 30s
  struct entry{
    EthernetAddress eaddr;
    size_t time;
  };
  std::unordered_map<uint32_t, entry> ip_map_ {};

  // Dategrams that wait to be sent
  struct dgram_buffered{
    InternetDatagram dgram;
    uint32_t ip;
  };
  std::vector<dgram_buffered> datagrams_buffered_ {};

  // send the buffered datagrams to dst after receive ARP
  void datagrams_clear( uint32_t dst );
  
  // Mapping between request IP and the time the ARP has been sent
  // if its time exceed 5 seconds, it should be discarded.
  std::unordered_map<uint32_t, size_t> ip_request_ {};
};

先介绍我添加的private memebers：

  • ip_map_：用于记录查找表的每个表项，每个表项都包含了该ip地址对应的物理地址以及这个表项的存活时间，采用ip地址的raw value来索引。使用unordered_map是因为无需按顺序排，仅仅需要查询而很少修改，属于是对整体帮助不大的局部小优化。
  • datagrams_buffered_：当一个报文因为未获得物理地址而无法发出时，需要先将其排队，并存下其ip地址，方便ARP到时取出并发送。
  • datagrams_clear()：在获得ARP后，发送对应的积压的报文。
  • ip_request_：用来记录ARP请求的ip地址的从发送到现在的时间，如果超过5秒，才能允许同一个ip请求发送ARP。

send_datagram

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
void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )
{
  auto it = ip_map_.find(next_hop.ipv4_numeric());
  if(it != ip_map_.end()) 
  {
    EthernetHeader header;
    header.type = EthernetHeader::TYPE_IPv4;
    header.dst = (it->second).eaddr;
    header.src = ethernet_address_;

    EthernetFrame frame;
    frame.header = header;
    frame.payload = serialize(dgram);
    transmit(frame);
  } else {
    // boardcast an ARP request
    if(ip_request_.find(next_hop.ipv4_numeric()) != ip_request_.end())
      return;
      
	dgram_buffered d;
    d.dgram = dgram;
    d.ip = next_hop.ipv4_numeric();
    datagrams_buffered_.push_back(d);
    ip_request_.insert({next_hop.ipv4_numeric(), 0});
    
    ARPMessage arp;
    arp.opcode = ARPMessage::OPCODE_REQUEST;
    arp.sender_ip_address = ip_address_.ipv4_numeric();
    arp.sender_ethernet_address = ethernet_address_;
    arp.target_ip_address = next_hop.ipv4_numeric();
    
    EthernetHeader header;
    header.type = EthernetHeader::TYPE_ARP;
    header.dst = ETHERNET_BROADCAST;
    header.src = ethernet_address_;

    EthernetFrame frame;
    frame.header = header;
    frame.payload = serialize(arp);
    transmit(frame);
  }
}

基本上按照实验手册的逻辑来写就行。但值得注意的是，check5的代码还是串行运行的，check6可能是并行的？我开始的实现是，先发送ARP，再将报文推入等待队列，可以通过check5的测试，但check6不行。需要先推入等待队列，再发送ARP。显然，如果先发送ARP，在推入之前ARP到了，我们将无法发送这个报文。

recv_frame

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
void NetworkInterface::datagrams_clear( uint32_t dst)
{
  auto it = ip_map_.find(dst);
  for(auto i = datagrams_buffered_.begin(); i != datagrams_buffered_.end();) {
    dgram_buffered d = *i;
    if(d.ip == dst) {
      EthernetHeader header;
      header.type = EthernetHeader::TYPE_IPv4;
      header.dst = (it->second).eaddr;
      header.src = ethernet_address_;

      EthernetFrame frame;
      frame.header = header;
      frame.payload = serialize(d.dgram);
      transmit(frame);
      i = datagrams_buffered_.erase(i);
    } else {
      i ++;
    }
  }
}


void NetworkInterface::recv_frame( const EthernetFrame& frame )
{
  if(frame.header.dst != ETHERNET_BROADCAST && frame.header.dst != ethernet_address_)
    return;

  if(frame.header.type == EthernetHeader::TYPE_IPv4) {
    InternetDatagram dgram;
    if(parse(dgram, frame.payload))
      datagrams_received_.push(dgram);
  }

  if(frame.header.type == EthernetHeader::TYPE_ARP) {
    ARPMessage arp;
    if(parse(arp, frame.payload) == false)
      return;
    
    if(arp.opcode == ARPMessage::OPCODE_REPLY) {
      ip_map_.insert({arp.sender_ip_address, {arp.sender_ethernet_address, 0}});
      datagrams_clear(arp.sender_ip_address);
      
      auto it = ip_request_.find(arp.sender_ip_address);
      if(it != ip_request_.end())
        ip_request_.erase(it);
    }

    if(arp.opcode == ARPMessage::OPCODE_REQUEST) {
      ip_map_.insert({arp.sender_ip_address, {arp.sender_ethernet_address, 0}});

      auto it = ip_request_.find(arp.sender_ip_address);
      if(it != ip_request_.end())
        ip_request_.erase(it);

      // send an ARP reply if ask for our address
      if(arp.target_ip_address == ip_address_.ipv4_numeric()){
        ARPMessage ar;
        ar.opcode = ARPMessage::OPCODE_REPLY;
        ar.sender_ip_address = ip_address_.ipv4_numeric();
        ar.sender_ethernet_address = ethernet_address_;
        ar.target_ip_address = arp.sender_ip_address;
        ar.target_ethernet_address = arp.sender_ethernet_address;
        
        EthernetHeader header;
        header.type = EthernetHeader::TYPE_ARP;
        header.dst = arp.sender_ethernet_address;
        header.src = ethernet_address_;

        EthernetFrame f;
        f.header = header;
        f.payload = serialize(ar);
        transmit(f);
      }
      
    }
  }
}

没什么说的，记得重置计时器，其他实现就行。

tick

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void NetworkInterface::tick( const size_t ms_since_last_tick )
{
  // check the time of the request ARP
  for(auto it = ip_request_.begin(); it != ip_request_.end();) {
    it->second += ms_since_last_tick;
    if(it->second >= 5000)
      it = ip_request_.erase(it);
    else
      it++;
  }

  // check the time of the mapping between IP address and Ethernet address
  for(auto it = ip_map_.begin(); it != ip_map_.end();) {
    (it->second).time += ms_since_last_tick;
    if((it->second).time >= 30000)
      it = ip_map_.erase(it);
    else
      it++;
  }
}

我们一共有两个计时器：IP地址-物理地址的表的表项的存活时间、对于一个ip地址的ARP的已发送时间。

#Computer-Networking
CS144-check5
https://pactheman123.github.io/2024/09/30/CS144-check5/
作者
Xiaopac
发布于
2024年9月30日
许可协议