CS 144 Checkpoint 5 - Network Interface

“In this week’s checkpoint, you’ll go down the stack and implement a network interface: the bridge between Internet datagrams that travel the world, and link-layer Ethernet frames that travel one hop.”

There isn’t much to say about this checkpoint. We can use three hash tables to store all the information we need to handle the network interface. The cache_ table stores the mapping between IP addresses and Ethernet addresses. The requests_ table is used to deduplicate ARP requests. The queue_ table is used to store datagrams that are waiting for an ARP response.

using IPV4Address = uint32_t;
using Timestamp = size_t;
std::unordered_map<IPV4Address, Expirable<EthernetAddress>> cache_ {};
std::unordered_map<IPV4Address, Expirable<std::monostate>> requests_ {};
std::unordered_map<IPV4Address, std::queue<InternetDatagram>> queue_ {};

Since we need to handle TTL for both the ARP requests and the cache entries, we can create a wrapper to separate the concerns.

template<typename T>
struct Expirable
{
  T data;
  size_t expiry_time_ms;

  [[nodiscard]] bool expired( size_t current_time_ms ) const noexcept
  {
    return current_time_ms >= expiry_time_ms;
  }
};

For the requests_ map, we don’t need to store any data, but just the expiry time. C++ 17 introduces monostate the Unit type in C++, which is the perfect fit for this use case.

My implementation does not attempt to delete any expired entries. I simply check whether an entry has expired when I need to access it. This approach passes all test cases without issues. But one can easily perform cleanup inside the tick function, or impose a soft and hard limit on the number of entries in the cache if the memory usage is a concern.

This concludes Checkpoint 5.