Lab 6: building an IP router

准备工作

下载代码以及跑通流程

git checkout -b lab6-startercode
git fetch
git merge origin/lab6-startercode
cd build
make -j4 && make check_lab6

说明

为了实现方便，使用vector存储转发表的每一项
当收到datagram时，搜索转发表，找到最长前缀匹配以及interface_num
- 通过interface_num对应的interface发送datagram

代码

router.hh

添加ForwardTableEntry, _forward_table, get_mask：

class ForwardTableEntry {
    public:
        uint32_t route_prefix = 0;
        uint8_t prefix_length = 0;
        std::optional<Address> next_hop = {};
        size_t interface_num = 0;
};

class Router {
    //! The router's collection of network interfaces
    std::vector<AsyncNetworkInterface> _interfaces{};

    //! Send a single datagram from the appropriate outbound interface to the next hop,
    //! as specified by the route with the longest prefix_length that matches the
    //! datagram's destination address.
    void route_one_datagram(InternetDatagram &dgram);

    // add 
    std::vector<ForwardTableEntry> _forward_table{};

  public:
    //! Add an interface to the router
    //! \param[in] interface an already-constructed network interface
    //! \returns The index of the interface after it has been added to the router
    size_t add_interface(AsyncNetworkInterface &&interface) {
        _interfaces.push_back(std::move(interface));
        return _interfaces.size() - 1;
    }

    //! Access an interface by index
    AsyncNetworkInterface &interface(const size_t N) { return _interfaces.at(N); }

    //! Add a route (a forwarding rule)
    void add_route(const uint32_t route_prefix,
                   const uint8_t prefix_length,
                   const std::optional<Address> next_hop,
                   const size_t interface_num);

    //! Route packets between the interfaces
    void route();

    // add
    uint32_t get_mask(uint8_t prefix_length);
};

add_route

直接push到_forward_table即可：

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";

    // DUMMY_CODE(route_prefix, prefix_length, next_hop, interface_num);
    // Your code here.
    ForwardTableEntry entry;
    entry.route_prefix = route_prefix;
    entry.prefix_length = prefix_length;
    entry.next_hop = next_hop;
    entry.interface_num = interface_num;

    // ForwardTableEntry entry(route_prefix, prefix_length, next_hop, interface_num);
    _forward_table.push_back(entry);
}

route_one_datagram

根据说明部分的算法转发datagram：

void Router::route_one_datagram(InternetDatagram &dgram) {
    IPv4Header header = dgram.header();
    // 最长匹配长度
    uint8_t max_l = 0;
    int index = -1;
    ForwardTableEntry entry;
    int n = _forward_table.size();

    for (int i = 0; i < n; i++) {
        // 路由器搜索路由表，以找到与数据报的目的地址相匹配的路由。我们所说的"匹配"是指目的地址的最高有效`prefix_length`比特与`route_prefix`的最高有效`prefix_length`比特相同的。
        uint32_t mask = get_mask(_forward_table[i].prefix_length);
        if ((header.dst & mask) == (_forward_table[i].route_prefix & mask)) {
            // 注意最长匹配长度可能为0, 所以要通过index判断
            if ((index == -1) || (_forward_table[i].prefix_length > max_l)) {
                max_l = _forward_table[i].prefix_length;
                index = i;
                entry = _forward_table[index];
            }
        }
    }

    // 如果没有匹配的路由，路由器会丢弃数据报。
    if (index == -1) {
        return;
    }
    // 路由器会递减数据报的TTL（生存时间）。如果TTL已经为零，或在递减后为零，路由器应该放弃该数据报。
    if (dgram.header().ttl <= 1) {
        return;
    }
    dgram.header().ttl--;

    // 选择interface
    if (_forward_table[index].next_hop.has_value()) {
        // 但如果路由器是通过其他路由器连接到有关网络的，则`next_hop`将包含路径上下一路由器的IP地址。
        Address next_hop = _forward_table[index].next_hop.value();
        interface(_forward_table[index].interface_num).send_datagram(dgram, next_hop);
    } else {
        // 如果路由器直接连接到有关的网络，`next_hop`将是一个空的可选项。在这种情况下，`next_hop`是数据报的目标地址。
        Address next_hop = Address::from_ipv4_numeric(header.dst);
        // 发送
        interface(_forward_table[index].interface_num).send_datagram(dgram, next_hop);
    }
}

get_mask

根据prefix_length生成mask：

uint32_t Router::get_mask(uint8_t prefix_length) {
    if (prefix_length == 0) {
        return 0;
    } else {
        return ~((1 << (32 - prefix_length)) - 1);
    }
}

测试

make -j8 && make check_lab6

Test project /home/cs144/sponge/build
    Start 29: arp_network_interface
1/2 Test #29: arp_network_interface ............   Passed    0.00 sec
    Start 30: router_test
2/2 Test #30: router_test ......................   Passed    0.01 sec

100% tests passed, 0 tests failed out of 2

Total Test time (real) =   0.02 sec