CS144 Lab 5

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

Checkpoint5 spec

注意，这篇笔记My implementation的后半部分全程代码剧透！

Overview

In this lab, you'll go down the stack and implement the network interface: the bridge between Internet datagrams that travel the world, and link-layer Ethernet frames that travel one hop.

The figure below shows that the network interface we are going to implement is part of a host's TCP/IP protocol stack and also a part of an IP router.

Our protocol stack

What's the responsibility of the network interface?

When an IP datagram is handed to the kernel, the kernel needs to construct an appropriate link-layer (Ethernet) frame with the IP datagram as its payload. This means the kernel needs to know its (IP address, Ethernet address) mapping. These functions are performed by the network interface.

Most of the work you will do is to implement the Address Resolution Protocol(ARP), which looks up (and cache) the Ethernet address for each next-hop IP address.

In lab6, you will use this network interface as part of an IP router.

My implementation

前言：coding前一定要认真读spec，将逻辑细节清楚后再写code。这个lab的代码量会相对较大，一定要多写helper functions！否则函数内部实现就会很臃肿。spec将函数逻辑讲解得很清晰，而且不像lab2和lab3那样有那么多corner case，所以难度适中。如果test没有通过，那一定是你在函数的逻辑细节问题上疏漏了。

这个lab需要我们实现网络层(IP)和链路层(Ethernet)之间的网络接口(Network Interface)，负责：

  1. 将从host/router上层(IP)收到的network datagram包装成Ethernet frame发送给上层IP协议指定的下一个host(next hop)。可能需要发送ARP request并将datagram暂放在waiting area中等待发送（详见ARP协议）
  2. 接收外来的Ethernet frame，解析出payload，并根据其类型决定下一步操作：
    • 如果是IPv4 datagram, 则将其存入buffer中供上层协议读取
    • 如果是ARP message，则记录下sender's IP-to-Ethernet mapping，如果是ARP request for自己的Ethernet地址，那就回复相应的ARP reply

如spec所说，这个Network Interface的关键在于实现ARP协议：

这个Network Interface需要一个结构来缓存所有next hop的IP-to-Ethernet mapping。当需要发送一个network datagram的时候，如果next hop的Ethernet地址未知，就需要broadcast一个ARP request，并将这个datagram放入一个waiting area等待接收到ARP reply后再发送出去

当Network Interface接收到一个ARP message的时候，需要将sender's IP-to-Ethernet mapping缓存下来。这时候需要检查waiting area中是否有正在等待这个mapping的datagram，如果有的话现在就可以发送这个datagram了。如果是一个ARP request，并且请求的还是自己的Ethernet地址，那么还需要将相应的ARP reply发送给sender

需要注意的点：

next hop的IP-to-Ethernet mapping是会随着设备的接入和离开随时变化的，因此每个缓存的IP-to-Ethernet mapping每隔一段时间（lab规定为30秒）会过期，需要清除。

在发送一个ARP request之后，5秒内（lab规定的）不应再发送针对相同IP地址的ARP request，但是仍需要将datagram放入waiting area中。

datagram不会永远等待在waiting area中，如果被放入waiting area后的5秒内（lab规定的）还没接收到等待的Ethernet地址，那么我们的Network Interface就会drop掉这个datagram。

接下来进入我的实现细节（后面将是全程代码剧透！）：

首先要确定用什么数据结构来表示：

  1. 所有缓存的IP-to-Ethernet mappings
  2. 所有在waiting area中的datagrams

考虑到清除IP-to-Ethernet mappings操作是清除那些早于当前时间30秒的所有mappings，因此我决定使用可以根据mapping插入的时间顺序（时间戳）来排序所有mappings的数据结构，以提高清除操作的速度。我选择使用一个multimap，将mapping插入的时间（时间戳）作为key，IP-to-Ethernet mapping pair作为value。用multimap而不是map是因为不同mapping pair的时间戳可能相同。

1
2
3
4
5
6
7
8
// Define the value type as a pair of EthernetAddress and IP address.
using MappingPair = std::pair<EthernetAddress, uint32_t>;

// Define the map type with timestamp as key and (Ethernet, IP) pair as value.
// This is the data structure that will be used to store all the IP-to-Ethernet mappings.
using NetworkMappings = std::multimap<uint64_t, MappingPair>;

NetworkMappings mappings {};

同样的道理，在waiting area中等待过期的datagrams也需要定期清除（每次调用tick时），因此我也用一个multimap存储queued datagram。注意queued datagram需要包含datagram本身，以及其需要去往的next hop的ip地址。

注意不要将datagram_queued_与datagram_received_搞混淆了，前者是需要等待ARP request收到回应后才能发送出去的pending(queued) datagrams，而datagram_received_是Network Interface从外部接收并解析出的IPv4 datagrams，暂存在Network Interface中供上层协议读取的。

1
2
3
4
5
6
7
8
struct QueuedDatagram
{
    uint32_t next_hop_ip {};
    InternetDatagram dgram {};
};

// Datagrams that queued to learn the Ethernet address of the next hop
std::multimap<uint64_t, QueuedDatagram> datagrams_queued_ {};

send_datagram method还需要一个结构来存储针对每一个ip地址发送的ARF request的上一次发送时间，以此来检查是否可以发送当前的ARP request，这里我选择使用unordered_map，ip地址作为key，时间戳作为value。因为访问该结构的时候是通过ip地址寻找的，无法进行顺序查找，因此不需要排序，用hash table存储访问效率较高。

1
std::unordered_map<uint32_t, uint64_t> last_arp_request_time_ {};

确定好所有的数据结构后，就可以开始尝试实现Network Interface提供的3个methods，实现的过程中尽量将具体的逻辑细节封装在helper functions中：

  • tick

tick是最容易实现的，首先更新当前时间，然后就是根据更新后的时间将过期的IP-to-Ethernet mappings和queued datagram清除。这里可以分别写两个helper function来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Remove expired mappings (older than 30 seconds)
void remove_expired_mappings()
{
    if ( time_elapsed_ < MAPPING_TIMEOUT ) {
        return;
    }

    // Calculate the expiration threshold
    uint64_t expiration_threshold = time_elapsed_ - MAPPING_TIMEOUT;

    // Find the first element that is not expired
    // Since map is ordered by timestamp, we can remove all elements
    // from beginning until we find a non-expired entry
    auto it = mappings.lower_bound( expiration_threshold );
    mappings.erase( mappings.begin(), it );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Drop any expired datagrams
void drop_expired_datagrams()
{
    // Calculate the expiration threshold
    uint64_t expiration_threshold = time_elapsed_ - ARP_REQUEST_TIMEOUT;
    if ( time_elapsed_ < ARP_REQUEST_TIMEOUT ) {
        return;
    }

    // Drop all expired datagrams
    auto it = datagrams_queued_.begin();
    while ( it != datagrams_queued_.end() && it->first <= expiration_threshold ) {
        it = datagrams_queued_.erase( it );
    }
}

这两个helper function虽然是处理不同的数据结构，但是逻辑很相似，都是从multimap的开头开始顺序清除，直到遇到第一个没有过期的元素后停止。

1
2
3
4
5
6
7
8
9
10
11
//! \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 )
{
  time_elapsed_ += ms_since_last_tick;

  // Remove any expired IP-to-Ethernet mappings
  remove_expired_mappings();

  // Drop any expired datagrams
  drop_expired_datagrams();
}
  • send_datagram

分两种情况：

  1. 已知next hop的Ethernet address（缓存在Network Interface中了）

从IP-to-Ethernet中获取需要的mapping，创建并设置Ethernet frame，frame header中的dst field设为获取的mapping中的Ethernet address。将frame的payload设为serialized后的datagram。设置完成后传输该Ethernet frame

根据next hop的ip地址获取mapping缓存，并将获知的Ethernet地址写入frame header的过程可以写一个helper function：

1
2
3
4
5
6
7
8
9
10
11
// Get mapping by IP address
bool getMapping( uint32_t target_ip, EthernetAddress& eth ) const
{
    for ( const auto& [ts, mapping] : mappings ) {
        if ( mapping.second == target_ip ) {
            eth = mapping.first;
            return true;
        }
    }
    return false;
}

在send_datagram中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
EthernetFrame eframe;

// If the destination Ethernet address is already known, create a Ethernet frame and send it right away
if ( getMapping( next_hop.ipv4_numeric(), eframe.header.dst ) ) {
    // Set up the Ethernet frame header
    eframe.header.type = EthernetHeader::TYPE_IPv4;
    eframe.header.src = ethernet_address_;

    // Set up the Ethernet frame payload to be the serialized datagram
    Serializer serializer;
    dgram.serialize( serializer );
    eframe.payload = serializer.finish();

    // Send the Ethernet frame
    transmit( eframe );
    return;
}
  1. 未知next hop的Ethernet address（不在缓存中）

需要发送一个请求next hop的ip地址的ARP request（如果5秒内没发送过请求该ip地址的ARP request），并将datagram放入waiting area中。

我用一个helper function来创建ARP message：

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
EthernetFrame create_arp_message( uint16_t opcode,
                                 const EthernetAddress& sender_eth,
                                 uint32_t sender_ip,
                                 const EthernetAddress& target_eth,
                                 uint32_t target_ip )
{
    EthernetFrame frame;
    if ( opcode == ARPMessage::OPCODE_REQUEST ) {
        frame.header.dst = ETHERNET_BROADCAST;
    } else {
        frame.header.dst = target_eth;
    }
    frame.header.src = sender_eth;
    frame.header.type = EthernetHeader::TYPE_ARP;

    ARPMessage arp;
    arp.opcode = opcode;
    arp.sender_ethernet_address = sender_eth;
    arp.sender_ip_address = sender_ip;
    arp.target_ethernet_address = target_eth;
    arp.target_ip_address = target_ip;

    Serializer serializer;
    arp.serialize( serializer );
    frame.payload = serializer.finish();

    return frame;
}

注意，send_datagram（可能）需要的ARP request message和recv_frame（可能）需要的ARP reply message都是用上面这个函数创建。创建request和reply message使用的参数模板都是一样的，不同的是：

  1. opcode不同

  2. request message的target_ethernet_address是{ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }，而reply message的是要回复对象的Ethernet地址

  3. request message的target_ip_address是请求的ip地址，reply message的是要回复对象的ip地址

  4. request message的frame header中的dst是Ethernet Broadcast地址，而reply message的就是要回复对象的Ethernet地址

接下来，我用一个helper function来检查是否可以发送ARP request，再用一个来更新ARP request发送时间：

1
2
3
4
5
6
7
8
9
10
11
bool can_send_arp_request( uint32_t target_ip ) const
{
    auto it = last_arp_request_time_.find( target_ip );
    if ( it == last_arp_request_time_.end() ) {
        return true;
    }

    return time_elapsed_ - it->second >= ARP_REQUEST_TIMEOUT;
}

void update_arp_request_time( uint32_t target_ip ) { last_arp_request_time_[target_ip] = time_elapsed_; }

在send_datagram中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// The destination Ethernet address is unknown,
// broadcast an ARP request and queue the datagram
EthernetFrame arp_request = create_arp_message( ARPMessage::OPCODE_REQUEST,
                                               ethernet_address_,
                                               ip_address_.ipv4_numeric(),
                                               { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
                                               next_hop.ipv4_numeric() );

if ( can_send_arp_request( next_hop.ipv4_numeric() ) ) {
    transmit( arp_request );
    update_arp_request_time( next_hop.ipv4_numeric() );
}

QueuedDatagram qdgram;
qdgram.next_hop_ip = next_hop.ipv4_numeric();
qdgram.dgram = dgram;
datagrams_queued_.insert( make_pair( time_elapsed_, qdgram ) );
  • recv_datagram

首先判断接收到的Ethernet frame是不是发送给自己的，如果不是的话直接ignore：

1
2
3
4
// Ignore any frames not destined for the network interface
if ( frame.header.dst != ethernet_address_ && frame.header.dst != ETHERNET_BROADCAST ) {
    return;
}

后续处理该frame也分两种情况：

  1. 如果接收到的是IPv4类型的frame，将payload解析为network datagram，如果解析成功就将其放入datagram_received_ buffer中供上层协议读取
1
2
3
4
5
6
7
8
9
10
11
// If inbound frame is IPv4, parse the payload as an InternetDatagram
// and if successful, push the resulting datagram to the datagrams_received_ queue
if ( frame.header.type == EthernetHeader::TYPE_IPv4 ) {
    Parser parser( frame.payload );

    InternetDatagram dgram;
    dgram.parse( parser );
    if ( parser.has_error() )
        return;
    datagrams_received_.push( dgram );
}

  1. 如果接收到的是ARP类型的frame，将payload解析为ARP message，如果解析成功就将sender的IP-to-Ethernet mapping写入缓存中。并且，如果是ARP request，那么还需要回复相应的ARP reply。

    最后，我们需要遍历datagram_queued_检查刚接收到的IP-to-Ethernet mapping是否可以让我们发送等待在waiting area中的pending(queued) datagrams。

写入IP-to-Ethernet mapping缓存的过程可以用一个helper function：

1
2
3
4
5
// Add a new IP-to-Ethernet mapping
void addMapping( uint64_t timestamp, const EthernetAddress& eth, uint32_t ip )
{
    mappings.insert( make_pair( timestamp, MappingPair( eth, ip ) ) );
}

创建并设置ARP reply使用之前写的create_arp_message function。

在recv_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
// If the inbound frame is ARP, parse the payload as an ARPMessage
// an if successful, add the IP-to-Ethernet mapping to the mappings.
// In addition, if it's an ARP request asking for our IP address,
// send an appropriate ARP reply.
if ( frame.header.type == EthernetHeader::TYPE_ARP ) {
    Parser parser( frame.payload );

    ARPMessage arp_message;
    arp_message.parse( parser );
    if ( parser.has_error() )
        return;
    addMapping( time_elapsed_, arp_message.sender_ethernet_address, arp_message.sender_ip_address );
    if ( arp_message.opcode == ARPMessage::OPCODE_REQUEST
        && arp_message.target_ip_address == ip_address_.ipv4_numeric() ) {
        EthernetFrame arp_reply = create_arp_message( ARPMessage::OPCODE_REPLY,
                                                     ethernet_address_,
                                                     ip_address_.ipv4_numeric(),
                                                     arp_message.sender_ethernet_address,
                                                     arp_message.sender_ip_address );
        transmit( arp_reply );
    }

    // Since we have received an ARP message, we can probably send any queued datagrams
    auto it = datagrams_queued_.begin();
    while ( it != datagrams_queued_.end() ) {
        if ( it->second.next_hop_ip == arp_message.sender_ip_address ) {
            send_datagram( it->second.dgram, Address::from_ipv4_numeric( it->second.next_hop_ip ) );
            it = datagrams_queued_.erase( it );
        } else {
            ++it;
        }
    }
}

Finish!

All tests in check5 pass!

Test check5

Computer Networking > CS144
#CS144 #计算机网络 #Protocol Stack
CS144 Lab 5
http://oooscar8.github.io/2025/02/19/cs144-lab5/
作者
Alex Sun
发布于
2025年2月19日
许可协议