Stanford CS144 Lab 5

Lab Checkpoint 5: down the stack (the network interface)

August 20, 2025

#Cs144 #C++

我们前面算是已经完成了 TCP 的实现，可以与任意系统交换 TCP 报文。从这个 checkpoint 起，我们将实现 network interface，其位于 TCP/IP 协议栈的相对底部，负责处理上层的 IP 包 (Internet datagram) 和下层的以太网帧 (Ethernet frames)。也就是说，我们最终的目的是实现 TCP-in-IP-in-Ethernet。

Checkpoint 4 是一些测量真实世界互联网的实验，无需在实验框架中填充代码，就不在此系列文章中赘述了。

2 Checkpoint 5: The Address Resolution Protocol #

这个 checkpoint 的主要任务是处理 ARP 协议。具体地，我们需要修改给出的 NetworkInterface 类，完成其中的 send_datagram recv_frame tick 三个方法。

send_datagram 是用来将 IP 包包装为以太网帧发送的，同时也要处理 ARP 报文广播的发送。该方法接受 IP 包和下一跳作为参数。一旦下一跳的 MAC 地址 (Ethernet address) 已知，则包装并发送该包；否则，广播一个 ARP request。为了避免造成 flood，发送 ARP request 的频率还受到一些限制。

recv_frame 接受以太网帧，并维护相应状态。传入的以太网帧可能有两种类型：IP 包和 ARP 报文。如果是 IP 包，解析其 payload 并压入 NetworkInterface 的内部队列；如果是 ARP 报文，更新 ARP 表，并查看有没有因为找不到 MAC 地址而没发出去的 IP 包，有则发之。

tick 是测试的时候用来计时的，主要是 ARP 广播超时需要利用其维护状态。

我个人感觉 send_datagram 和 recv_frame 两个方法在功能上会有些耦合，并且后者需要直接调用前者，不是很优雅，各种副作用比较影响思考。假如是一个真实的操作系统内核（我没写过或者读过，基于个人猜测），或许可以采用更加“事件驱动”的方式，把 ARP 表管理的部分拆出来，在每一个 tick 进行处理过期的 ARP entry，遍历 pending 状态的 IP 包等操作，缺点是根据 tick 粒度的不同，会有一定延迟。或许等我学习了 OS，会有更正确的理解吧。

实现上，状态管理还是全靠 std::map。给 NetworkInterface 添加了如下 private 成员：

// A map of IP address -> {Ethernet address, timestamp} for ARP lookups
std::map<uint32_t, std::pair<EthernetAddress, size_t>> arp_table_ {};

// A map of IP address in ARP requests -> timestamp for ARP requests that already have been sent
std::map<uint32_t, size_t> arp_requests_sent_ {};

// A map of IP address -> queue of datagrams that are waiting for an ARP reply
std::map<uint32_t, std::queue<InternetDatagram>> datagrams_pending_ {};

size_t last_tick_ms_ = {};

send_datagram 的实现：

void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )
{
  uint32_t next_hop_ip = next_hop.ipv4_numeric();

  auto arp_entry = arp_table_.find( next_hop_ip );
  if ( arp_entry != arp_table_.end() ) {
    EthernetFrame frame = {
      .header = {
        .dst = arp_entry->second.first,
        .src = ethernet_address_,
        .type = EthernetHeader::TYPE_IPv4,
      },
      .payload = serialize(dgram)
    };
    transmit( frame );
    return;
  }

  datagrams_pending_[next_hop_ip].push( dgram );

  // Ethernet address unknown, send ARP request
  // Check timestamp first to avoid flooding
  auto arp_request_it = arp_requests_sent_.find( next_hop_ip );
  if ( arp_request_it != arp_requests_sent_.end() && last_tick_ms_ - arp_request_it->second < 5000 ) {
    return;
  }

  ARPMessage arp_request = {
    .opcode = ARPMessage::OPCODE_REQUEST,
    .sender_ethernet_address = ethernet_address_,
    .sender_ip_address = ip_address_.ipv4_numeric(),
    .target_ip_address = next_hop_ip,
  };
  EthernetFrame arp_frame = {
    .header = {
      .dst = ETHERNET_BROADCAST,
      .src = ethernet_address_,
      .type = EthernetHeader::TYPE_ARP,
    },
    .payload = serialize(arp_request)
  };
  transmit( arp_frame );
  arp_requests_sent_[next_hop_ip] = last_tick_ms_;
}

recv_frame 的实现。调用了 send_frame 实现 IP 包的重传：

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

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

  if ( frame.header.type == EthernetHeader::TYPE_ARP ) {
    ARPMessage msg;
    if ( parse( msg, move( frame.payload ) ) ) {
      arp_table_[msg.sender_ip_address] = { msg.sender_ethernet_address, last_tick_ms_ };
      if ( msg.opcode == ARPMessage::OPCODE_REQUEST && msg.target_ip_address == ip_address_.ipv4_numeric() ) {
        ARPMessage arp_reply = {
          .opcode = ARPMessage::OPCODE_REPLY,
          .sender_ethernet_address = ethernet_address_,
          .sender_ip_address = ip_address_.ipv4_numeric(),
          .target_ethernet_address = msg.sender_ethernet_address,
          .target_ip_address = msg.sender_ip_address,
        };
        EthernetFrame arp_frame = {
          .header = {
            .dst = msg.sender_ethernet_address,
            .src = ethernet_address_,
            .type = EthernetHeader::TYPE_ARP,
          },
          .payload = serialize(arp_reply)
        };
        transmit( arp_frame );
      }

      auto it = datagrams_pending_.find( msg.sender_ip_address );
      if ( it != datagrams_pending_.end() ) {
        while ( !it->second.empty() ) {
          InternetDatagram dgram = move( it->second.front() );
          it->second.pop();

          send_datagram( dgram, Address::from_ipv4_numeric( msg.sender_ip_address ) );
        }
        datagrams_pending_.erase( it );
      }
    }
  }
}

tick 主要处理 ARP 表和未获响应的 ARP requests 的过期：

void NetworkInterface::tick( const size_t ms_since_last_tick )
{
  last_tick_ms_ += ms_since_last_tick;

  for ( auto it = arp_table_.begin(); it != arp_table_.end(); ) {
    if ( last_tick_ms_ - it->second.second > 30000 ) { // 30 seconds
      it = arp_table_.erase( it );
    } else {
      ++it;
    }
  }

  for ( auto it = arp_requests_sent_.begin(); it != arp_requests_sent_.end(); ) {
    if ( last_tick_ms_ - it->second > 5000 ) { // 5 seconds
      datagrams_pending_.erase( it->first );
      it = arp_requests_sent_.erase( it );
    } else {
      ++it;
    }
  }
}

这里还有一个小插曲，测试的第一阶段 compile with bug-checkers 在我的机器上需要 18 秒才能跑完，但限时了 15 秒。可以通过修改 etc/tests.cmake 调大时限。