CS144 learns (4) IP routes

The last experiment is to implement an IP routing table, which only needs to implement two parts of adding routing entries and prefix matching, and does not involve routing protocols. The experiment is pretty simple, just 20 lines of code.

The key to the experiment is how to store the routing table. The easiest and slowest way is to store the routing table in an array and match it one by one in order n time.

One way is to improve it by using hash tables, but the hash tables are unordered and cannot be prefixed, so 33 hash tables need to be set up to store them separately by prefix. When a match is made, the hash table with the longest prefix is matched, and when a match is reached, the match is successful. The problem with this approach, however, is that in the worst case, it takes a lot of time to find a match through all 33 hash tables. This is the way I use it in my code, and it’s the way I used it in older Linux kernels.

In fact, the longest prefix matching problem is very suitable to use prefix Tree (trie-tree) to implement. Each bit is a 0 or a 1, which corresponds to the left and right children of the binary tree. Thus, the maximum height of the tree is 32, the worst case is 32 matches, and the structure of the tree is not cache friendly.

In fact, many paths in the routing table tree can be compressed. For example, if there is only one route entry on a path, the path can be compressed to reduce the height of the tree. In this way, the prefix tree of path compression is formed.

Routing table, on the other hand, the corresponding tree has a property is in some parts will be populated, so for the quality of the dense we can further compress, used in the node length is 2 ^ n array to hold more than one child, can be find corresponding subscript children directly lookup, and before is a more than one into a match, This makes better use of the cache and reduces the height of the tree. This Tree is known as lC-trie-tree and is used in the Linux kernel. In the actual test, the height of the routing table with tens of thousands of routing entries generally does not exceed 5, so the efficiency of prefix matching is greatly improved.

The code for this experiment is as follows:

#include "router.hh"

#include <iostream>

using namespace std;

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() < <"/" << int(prefix_length)
         << "= >" << (next_hop.has_value()? next_hop->ip() : "(direct)") < <" on interface " << interface_num << "\n";

    uint32_t mask = 0xffffffff << prefix_length;
    if((route_prefix & mask) ! = route_prefix) { cerr <<"Bad router_prefix" << endl;
    }
    _router_table[prefix_length][route_prefix] = {next_hop, interface_num};
}

void Router::route_one_datagram(InternetDatagram &dgram) {
    if (dgram.header().ttl == 1 || dgram.header().ttl == 0) return; // drop dgram
    uint32_t mask = 0xffffffff;
    uint32_t target = dgram.header().dst;
    for(int i = 32; i >= 0; i--) {
        if (_router_table[i].count(target & mask)) {
            // match
            dgram.header().ttl -= 1;
            auto record = _router_table[i][target & mask];
            auto next_hop = record.address;
            Address targetAddr = Address::from_ipv4_numeric(target);
            _interfaces[record.interface].send_datagram(dgram, next_hop.value_or(targetAddr));
            return;
        } else {
            mask <<= 1; }}}void Router::route(a) {
    // Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
    for (auto &interface : _interfaces) {
        auto &queue = interface.datagrams_out(a);while (not queue.empty()) {
            route_one_datagram(queue.front());
            queue.pop(a); }}}Copy the code