CS144-check5

在我们完成了TCP的实现以后，如标题所述，我们开始down the stack，实现网卡的部分逻辑，尤其是 ARP（Address Resolution Protocol，地址解析协议，是用来将IP地址解析为MAC地址的协议） 部分。如果你不理解ARP的功能，请自行查找资料。

目标

你在这个实验中的主要任务是在 network_interface.cc 文件中实现 NetworkInterface 的三个主要方法,维护从 IP 地址到以太网地址的映射。这个映射是一个缓存,或者说是”软状态”:NetworkInterface 为了效率而保留它,但如果必须从头开始,映射将自然地重新生成,而不会导致问题。

1. void NetworkInterface::send_datagram(const InternetDatagram &dgram, const Address &next_hop);

当调用者(例如,你的 TCPConnection 或路由器)想要向下一跳发送出站 Internet (IP)数据报时,就会调用这个方法。你的接口的工作是将这个数据报转换为以太网帧并(最终)发送出去。

• 如果目标以太网地址已知,立即发送。创建一个以太网帧(type = EthernetHeader::TYPE_IPv4),将有效载荷设置为序列化的数据报,并设置源和目标地址。
• 如果目标以太网地址未知,广播一个 ARP 请求来获取下一跳的以太网地址,并将 IP 数据报排队,以便在收到 ARP 回复后发送。

例外:你不想用 ARP 请求淹没网络。如果网络接口在过去 5 秒内已经发送了关于同一 IP 地址的 ARP 请求,不要发送第二个请求——只需等待对第一个请求的回复。同样,将数据报排队,直到你知道目标以太网地址。

2. void NetworkInterface::recv_frame(const EthernetFrame &frame);

当以太网帧从网络到达时,会调用此方法。代码应该忽略任何不是发往网络接口的帧(意味着以太网目标是广播地址或接口自己的以太网地址,存储在 ethernet_address 成员变量中)。

• 如果入站帧是 IPv4,将有效载荷解析为 InternetDatagram,如果成功(意味着 parse() 方法返回 ParseResult::NoError),将生成的数据报推送到 datagrams_received 队列。
• 如果入站帧是 ARP,将有效载荷解析为 ARPMessage,如果成功,记住发送方 IP 地址和以太网地址之间的映射 30 秒。(从请求和回复中学习映射。)此外,如果它是一个请求我们 IP 地址的 ARP 请求,发送一个适当的 ARP 回复。

3. void NetworkInterface::tick(const size_t ms_since_last_tick);

随着时间的推移调用此方法。使任何已过期的 IP 到以太网映射过期。

Q & A

• 你期望有多少代码?

  总的来说,我们预计实现(在 network_interface.cc 中)总共需要大约 100-150 行代码。

• 我如何”发送”一个以太网帧?

  在它上面调用 transmit()。

• 我应该使用什么数据结构来记录下一跳 IP 地址和以太网地址之间的映射?

  由你决定!

• 我如何将以 Address 对象形式出现的 IP 地址转换为我可以写入 ARP 消息的原始 32 位整数?

  使用 Address::ipv4_numeric() 方法。

• 如果 NetworkInterface 发送了一个 ARP 请求但从未得到回复,我应该怎么做?是否应该在某个超时后重新发送?是否使用 ICMP 向原始发送者发出错误信号?

  在现实生活中,是的,这两件事都要做,但在这个实验中不用担心。(在现实生活中,如果接口无法获得对其 ARP 请求的回复,最终会通过 Internet 向原始发送者发回一个 ICMP “主机不可达”。)

• 如果一个 InternetDatagram 排队等待了解下一跳的以太网地址,而该信息从未到来,我应该怎么做?是否应该在某个超时后丢弃数据报?

  同样,在现实生活中肯定是”是”,但在这个实验中不用担心这个问题。

实现

好的，现在让我们开始思考，我需要维护会过期的ip到mac的映射，也就是说我需要维护（time,ip,mac）, 并且根据ip查找mac，并且在tick后检索按时间顺序检查过期。
考虑到分别索引是复杂的，我们发现ip是一一对应time和mac的，于是我们维护两个数据结构，

std::unordered_map<uint32_t, EthernetAddress> arp_table_ {};
std::map<uint64_t, uint32_t> arp_timestamp_ {};

来实现$O(1)$的查找。

在现实中ARP通常采用老化策略，即一段时间不使用则过期，可以使用类似LRU的数据结构去维护，但在本次实验中我们不需要考虑。

之后，在尝试发送IPv4报文时，如果我们的ARP表中没有对应的地址，那么我们就要发送ARP报文来询问该IP对应的mac，并且在收到ARP response（或者从其他ARP中学习到对应的mac）时，将这个IPv4报文发送。

这里强调IPv4是因为在IPv6中邻居发现协议（NDP）用于代替地址解析协议（ARP）。下文中IP均指v4。

所以，我们需要将等待发送的IP数据报缓存，并且在ARP到来时检查是否有缓存的数据报能够发送。注意到对相同的IP可能有多个数据报等待发送，我们使用multimap进行维护。

std::unordered_multimap<uint32_t,EthernetFrame> wait_queue_ {}; 
```  

以及，我们不希望ARP淹没网络（毕竟ARP请求是广播），所以我们存储针对相同的IP，上一次发送ARP的时间戳

```cpp
std::unordered_map<uint32_t,uint64_t> retransmit_arp_queue_ {};

这样，我们需要的数据结构就基本完成了。

我们在梳理一下逻辑：

• 发送报文时,如果ARP表中有对应记录，发送IP。没有则发送ARP请求(短时间内不重复发送相同ARP)并将IP报文送入waitqueue中。

• 收到报文时，如果是ARP，学习src的ip-mac映射。如果ARP是request且目标是本网卡，则回复。如果是IP，则将payload送入receive队列。

• tick后更新计时器，遗忘过期的ARP记录。

发送报文时，假如我需要发送ARP,那么我是先将报文送入waitqueue还是先发送ARP呢？

在本次实验中是没有区别的，但是下次实验中多个网卡使用多线程进行协同，所以需要先送入waitqueue再发送ARP。

以下是完整代码，细心即可。

void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )
{ 
  if ( arp_table_.contains( next_hop.ipv4_numeric() ) ) {
    EthernetFrame frame{
      .header = {
        .dst = arp_table_[next_hop.ipv4_numeric()],
        .src = ethernet_address_,
        .type = frame.header.TYPE_IPv4,
      },
      .payload = serialize(dgram),
    };
    transmit( frame );
  } else {
    EthernetFrame wait_frame{
      .header = {
        .dst = ETHERNET_BROADCAST,
        .src = ethernet_address_,
        .type = wait_frame.header.TYPE_IPv4,
      },
      .payload = serialize(dgram),
    };
    wait_queue_.emplace( next_hop.ipv4_numeric(), wait_frame );
    bool f = true;
    if ( retransmit_arp_queue_.contains( next_hop.ipv4_numeric() ) ) {
      if ( timer_ - retransmit_arp_queue_[next_hop.ipv4_numeric()] < 5000 ) {
        f = false;
      }
    }
    if ( f ) {
      ARPMessage arp_msg {
        .opcode = ARPMessage::OPCODE_REQUEST,
        .sender_ethernet_address = ethernet_address_,
        .sender_ip_address = ip_address_.ipv4_numeric(),
        .target_ethernet_address = 0,
        .target_ip_address = next_hop.ipv4_numeric(),
      };
      EthernetFrame arp_frame{
      .header = {
        .dst = ETHERNET_BROADCAST,
        .src = ethernet_address_,
        .type = arp_frame.header.TYPE_ARP,
      },
      .payload = serialize(arp_msg),
      };
      transmit( arp_frame );
      retransmit_arp_queue_.emplace( next_hop.ipv4_numeric(), timer_ );
    }
  }
}

//! \param[in] frame the incoming Ethernet frame
void NetworkInterface::recv_frame( const EthernetFrame& frame )
{ 
  if ( frame.header.dst != ethernet_address_ && frame.header.dst != ETHERNET_BROADCAST ) {
    return;
  }
  if ( frame.header.type == frame.header.TYPE_ARP ) {
    ARPMessage arp_msg;
    auto success = parse( arp_msg, frame.payload );
    if ( !success ) {
      return;
    }
    arp_timestamp_[timer_] = arp_msg.sender_ip_address;
    arp_table_[arp_msg.sender_ip_address] = arp_msg.sender_ethernet_address;
    if ( wait_queue_.contains( arp_msg.sender_ip_address ) ) {
      auto range = wait_queue_.equal_range( arp_msg.sender_ip_address );
      for ( auto i = range.first; i != range.second; i++ ) {
        i->second.header.dst = arp_msg.sender_ethernet_address;
        transmit( i->second );
      }
      wait_queue_.erase( range.first, range.second );
    }
    if ( arp_msg.target_ip_address == ip_address_.ipv4_numeric() && arp_msg.opcode == ARPMessage::OPCODE_REQUEST ) {
      ARPMessage reply {
        .opcode = ARPMessage::OPCODE_REPLY,
        .sender_ethernet_address = ethernet_address_,
        .sender_ip_address = ip_address_.ipv4_numeric(),
        .target_ethernet_address = arp_msg.sender_ethernet_address,
        .target_ip_address = arp_msg.sender_ip_address,
      };
      EthernetFrame arp_frame{
        .header = {
          .dst = arp_msg.sender_ethernet_address,
          .src = ethernet_address_,
          .type = frame.header.TYPE_ARP,
        },
        .payload = serialize(reply),
      };
      transmit( arp_frame );
    }
  } else if ( frame.header.type == frame.header.TYPE_IPv4 ) {
    InternetDatagram ip_msg;
    auto success = parse( ip_msg, frame.payload );
    if ( !success ) {
      return;
    }
    datagrams_received_.push( ip_msg );
  }
}

//! \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 )
{
  timer_ += ms_since_last_tick;
  while ( !arp_timestamp_.empty() ) {
    auto [time, ip] = *arp_timestamp_.begin();
    if ( timer_ - time > 30000 ) {
      arp_timestamp_.erase( arp_timestamp_.begin() );
      arp_table_.erase( ip );
    } else {
      break;
    }
  }
}