CS144 Lab 6

Lab Checkpoint 6: building an IP router

Checkpoint6 spec

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

Overview

In this lab, you will implement an IP router on top of your existing NetworkInterface. A router has several network interfaces, and can receive Internet datagrams on any of them. The router’s job is to forward the datagrams it gets according to the routing table: a list of rules that tells the router, for any given datagram:

• What interface to send it out

• The IP address of the next hop

Your job is to implement a router that can figure out these two things for any given datagram.

根据上图，一个router包含多个network interface，router根据routing table得知其收到的datagram的next hop，然后将其放到合适的outbound interface上。

注意这个lab不需要你实现Network Control Plane中生成routing table的routing algorithm（如RIP, OSPF, BGP, SDN controller），只需要实现Network Data Plane的功能：根据routing table来实现forwarding algorithm，也就是根据longest-prefix-match logic在routing table中寻找next hop和outbound interface

My implementation

我们的router需要干两件事情：

1. 维护并添加routing table中的条目
2. 根据longest-prefix-match，将下层Network Interface的datagrams送往合适的next hop和outbound interface

那么首先第一步，就是要确定用什么数据结构表示routing table，用来存储route prefix， prefix_length以及对应的next hop，outbound interface。lab的spec里面说我们不需要什么fancy的数据结构和算法来支持寻找longest-prefix-match的操作，O(N)的时间复杂度就够用。所以很简单，就用一个map，将<route prefix, prefix_length>作为key，<next hop, outbound interface>作为value就可以了。寻找longest-prefix-match就是遍历这个map，找到match的条目中prefix_length最长的。所以我希望这个map能按照prefix_length从大到小排序，这样从头开始遍历找到的第一个match的条目就是longest-prefix-match！

要让map按照prefix_length从大到小排序，我得自己给这个map定义一个比较函数：

// Define a comparison function for the routing table
struct RouteCompare
{
    bool operator()( const std::pair<uint32_t, uint8_t>& a, const std::pair<uint32_t, uint8_t>& b ) const
    {
        // Sort by prefix_length in descending order (from largest to smallest)
        if ( a.second != b.second ) {
            return a.second > b.second;
        }
        // If prefix_length is the same, sort by route_prefix in ascending order
        return a.first < b.first;
    }
};

std::map<std::pair<uint32_t, uint8_t>, std::pair<std::optional<uint32_t>, size_t>, RouteCompare> routing_table_ {};

add_route负责向routing table中添加条目，注意如果next_hop为空说明datagram要去往的network是直接与当前router连接着的，与当前条目匹配的datagram的next hop就是其destination ip address。这就是为什么上面的routing table结构中next_hop可能为空，要用std::optional<>来封装。

// route_prefix: The "up-to-32-bit" IPv4 address prefix to match the datagram's destination address against
// prefix_length: For this route to be applicable, how many high-order (most-significant) bits of
//    the route_prefix will need to match the corresponding bits of the datagram's destination address?
// next_hop: The IP address of the next hop. Will be empty if the network is directly attached to the router (in
//    which case, the next hop address should be the datagram's final destination).
// interface_num: The index of the interface to send the datagram out on.
void Router::add_route( const uint32_t route_prefix,
                       const uint8_t prefix_length,
                       const optional<Address> next_hop,
                       const size_t interface_num )
{
    cerr << "DEBUG: adding route " << Address::from_ipv4_numeric( route_prefix ).ip() << "/"
        << static_cast<int>( prefix_length ) << " => " << ( next_hop.has_value() ? next_hop->ip() : "(direct)" )
        << " on interface " << interface_num << "\n";

    // debug( "unimplemented add_route() called" );

    optional<uint32_t> next_hop_ip;

    if ( !next_hop.has_value() ) {
        next_hop_ip = nullopt;
    } else {
        next_hop_ip = next_hop->ipv4_numeric();
    }

    routing_table_.insert( { make_pair( route_prefix, prefix_length ), make_pair( next_hop_ip, interface_num ) } );
}

接下来就是实现route，负责将router在所有Network Interface上接收到的datagrams都在routing table中寻找longest-prefix-match，由合适的Network Interface将他们送到各自的next hop。

这需要我们遍历router的所有Network Interface，将等待在queue中的datagram一个个拿过来，去routing table中寻找longest-prefix-match，然后根据match结果送往合适的outbound interface（或drop）。

寻找longest-prefix-match的过程我用helper functions来完成，每扫描一个条目，用is_prefix_match判断是否match，直到找到第一个match的条目。

is_prefix_match的实现也很简单，就是比较两个32 bits数高N位是否相等的问题，用掩码轻松搞定。

bool find_longest_prefix_match( const uint32_t dest_ip, uint32_t& next_hop_ip, size_t& interface_num ) const
{
    for ( const auto& it : routing_table_ ) {
        if ( is_prefix_match( dest_ip, it.first.first, it.first.second ) ) {
            if ( !it.second.first.has_value() ) {
                next_hop_ip = dest_ip;
            } else {
                next_hop_ip = *it.second.first;
            }
            interface_num = it.second.second;

            return true;
        }
    }

    return false;
}

bool is_prefix_match( const uint32_t address, const uint32_t prefix, const uint8_t prefix_length ) const
{
    // Special case: if prefix_length is 0, all addresses match
    if ( prefix_length == 0 ) {
        return true;
    }

    uint32_t mask = 0xffffffff << ( 32 - prefix_length );

    return ( address & mask ) == ( prefix & mask );
}

但是要注意prefix_length = 0的special case，routing table中可能会有0.0.0.0/0的条目，也就是无论datagram的destination ip address是多少都match。如果用mask = 0xffffffff << ( 32 - prefix_length )来构造掩码会造成未定义行为，因此要特殊处理，否则test会报错：

有了find_longest_prefix_match这个helper function，route就很简单了：

// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
void Router::route()
{
    // debug( "unimplemented route() called" );

    size_t i = 0;
    while ( i < interfaces_.size() ) {
        queue<InternetDatagram>& datagrams_queue = interface( i )->datagrams_received();
        while ( !datagrams_queue.empty() ) {
            InternetDatagram dgram = datagrams_queue.front();
            datagrams_queue.pop();
            if ( dgram.header.ttl <= 1 ) {
                // If the TTL field is already 0, or hits 0 after the decrement, drop the datagram.
                cerr << "DEBUG: Dropped datagram: ttl = " << static_cast<int>( dgram.header.ttl )
                    << ", src = " << Address::from_ipv4_numeric( dgram.header.src ).ip()
                    << ", dst = " << Address::from_ipv4_numeric( dgram.header.dst ).ip() << "\n";
                continue;
            }
            dgram.header.ttl--;

            uint32_t next_hop_ip;
            size_t interface_num;
            if ( !find_longest_prefix_match( dgram.header.dst, next_hop_ip, interface_num ) ) {
                // If no route is found, drop the datagram.
                cerr << "DEBUG: No route found for datagram: ttl = " << static_cast<int>( dgram.header.ttl )
                    << ", src = " << Address::from_ipv4_numeric( dgram.header.src ).ip()
                    << ", dst = " << Address::from_ipv4_numeric( dgram.header.dst ).ip() << "\n";
                continue;
            }
            interface( interface_num )->send_datagram( dgram, Address::from_ipv4_numeric( next_hop_ip ) );
            cerr << "DEBUG: Routed datagram: ttl = " << static_cast<int>( dgram.header.ttl )
                << ", src = " << Address::from_ipv4_numeric( dgram.header.src ).ip()
                << ", dst = " << Address::from_ipv4_numeric( dgram.header.dst ).ip()
                << ", to next hop = " << Address::from_ipv4_numeric( next_hop_ip ).ip() << " on interface "
                << interface_num << "\n";
        }
        ++i;
    }
}

这里我故意留了一个小错误，也是我自己实现的时候忽略的，导致我在下面的test fail处卡了很久：

你看出来问题出在哪了吗？我当时百思不得其解，明明router接收到的datagram还是正常的，为什么发送出去的就是bad IPv4 datagram呢？

原来我在将datagram header中的TTL减1后忘记重新计算header的checksum了！如果这样发送出去接收到datagram的host/router检查了checksum之后就会判定datagram损坏了！仅仅漏这一行代码，这个router发送出去的所有datagram都是坏了没法用的！

...
dgram.header.ttl--;
dgram.header.compute_checksum();
...

Finish!

Your router will be tested in the simulated network below:

All tests in check5 pass!

Conclusion

写完这个lab后，你应该能感受到Internet分层分工设计的优雅之处。我们的router不需要关心上层的TCP，下层的Link Layer长什么样（不用关心Ethernet frame，或者link layer的ARP协议），只需要关心Network Datagrams，剩下的就交给下层的Network Interface处理就行了。我们不需要关心Network Interface是怎么从外部接收到Network Datagrams的，也不需要关心他是怎么把Network Datagrams送出到next hop的，只需要把router需要他做到的事情交给他做，并信任他能够做到就可以了。