Lab6 Router

心得

要做什么

本次实验要实现的是IP层的路由工作，但是只用实现对路由表进行操作的部分，比如说增加表项以及查询路由表等，其他的什么RIP、OSPF都不用我们实现，所以这样一来其实就简单非常多了（）

有一点需要注意的是，它一直在强调一个“最长前缀匹配”。也就是：

image-20230309142032359

image-20230309141949757

还有一点需要注意的是路由的结构：

image-20230308142934287

实际上就是路由表+一堆网络接口，这些端口都是network interface。

路由器可分为两部分，一部分控制路由协议，包括完善路由表之类的；另一部分负责数据转发。

负责接收数据的端口既可能收到数据，也可能收到路由信息报文。收到前者，则需要查询转发表然后进行路由转发；收到后者，就需要将其交付给路由选择处理机进行处理。

它有一个地方说得很有意思：路由表需要对网络拓扑最优化，转发表需要使查找过程最优化

也就是说，路由表只是key为目的IP地址，value为下一跳IP地址的一个普通map，可以是unordered_map，因为无需对它进行查找操作；转发表的内容可能跟路由表差不多，但是由于它要被进行频繁的查找工作，因而其数据结构需要对查找的消耗较低。

不过在我们这边，一般不区分路由表和转发表的概念。

感想

说实话思路很直观很简单，懒得说了，直接看代码吧【开摆】

我唯一卡得比较久的有两个地方，一个是一开始数据结构选用的是set，图它的天然排序，针对prefix_length排序来优化查找，但是没有意识到，对于自定义比较运算符的结构体，set也是会自动去重的（）而不同路由项的prefix_length显然可以重复。因而这样是达咩的，最后不得已选用了一个普通的list。

另一个是子网掩码计算问题，刚开始一个小地方想错了。这个没什么好说的，纯纯脑子一抽。

代码

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
// ...
class Router {
    struct route_node {
        uint32_t route_prefix = 0;
        uint8_t prefix_length = 0;
        std::optional<Address> next_hop{};
        size_t interface_num = 0;
        // 降序
        bool operator<(const route_node &b) const { return prefix_length > b.prefix_length; }
    };

    std::list<route_node> route_table{};
// ...

具体实现

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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";
    // 添加
    route_node node;
    node.route_prefix = route_prefix;
    node.prefix_length = prefix_length;
    node.next_hop = next_hop;
    node.interface_num = interface_num;
    route_table.push_back(node);
    route_table.sort();
}

//! \param[in] dgram The datagram to be routed
void Router::route_one_datagram(InternetDatagram &dgram) {
    // 减少TTL
    if (dgram.header().ttl <= 1)
        return;  // drop
    dgram.header().ttl -= 1;

    const uint32_t target_ip = dgram.header().dst;
    for (auto it = route_table.begin(); it != route_table.end(); it++) {
        uint32_t mask = 0;
        mask = (((~mask) >> (32-it->prefix_length)) << (32-it->prefix_length));
        if (it->prefix_length == 0 || ((it->route_prefix & mask) == (target_ip & mask))){
            // 发送报文
            if (it->next_hop.has_value())
                interface(it->interface_num).send_datagram(dgram, it->next_hop.value());
            else
                interface(it->interface_num).send_datagram(dgram,
Address::from_ipv4_numeric(dgram.header().dst));
            return;  // 一定是最长前缀
        }
    }
}

void Router::route() {
    // Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
    for (auto &interface : _interfaces) {
        auto &queue = interface.datagrams_out();
        while (not queue.empty()) {
            route_one_datagram(queue.front());
            queue.pop();
        }
    }
}