我想为我的学习实现一个小的路由表.我知道它是在路由器中使用radix/patricia树实现的.

Question

我想为我的学习实现一个小的路由表？我知道它是在路由器中使用radix/patricia树实现的吗？

有人可以给我一个如何实现相同的想法吗？

我觉得的主要问题是存储IP ADDRESS.例如:10.1.1.0网络下一跳20.1.1.1 10.1.0.0网络下一跳40.1.1.1

有人能给我一个结构的声明,我可以从中得到一个想法吗？

Answer 1

这不使用基数，但实现起来很简单。

您的查找键并不是绝对的。部分匹配是可能的，这意味着您找到了网络匹配规则而不是主机匹配规则。

我建议您使用容器列表（子表）。第一个列表将按子网掩码从最严格（掩码为 255.255.255.255 的主机路由规则）到最不严格（掩码为 0.0.0.0 的默认网关）排序。

列表中的每个条目下面都有一个易于搜索的结构（树、哈希表或只是一个列表），该结构以您尝试查找的地址的屏蔽部分为键。

对于您尝试查找的每个地址，您应该依次在每个网络掩码的子表中搜索它，并选择您遇到的第一个匹配项作为要使用的路由。它将具有尽可能严格的网络掩码，因为它们是从最严格到最严格的顺序排列的，如果在到达网络掩码列表末尾时未找到匹配项，您将在以下位置找到默认网关网络掩码条目清单（如果有的话）。该条目与其他条目略有不同，因为如果子表中有多个条目，它们都将具有相同的网络地址。如果您只想拥有一个默认网关，那么您可以选择不使用 0.0.0.0 条目，并将其视为一种特殊情况。

您可能还希望有一个指标（成本、速度等）作为每个条目的子键（或者让每个网络匹配是具有按其指标排序的相同网络/目标地址的条目列表）。这将允许您拥有多于一条 192.168.1.0 路由（一条通过 WiFi，一条通过有线以太网），而不会让事情变得困难。

当网络掩码条目变空时，您可能想要将其删除。

struct route4_table_subnet {
    uint32_t mask;
    struct route_table_network_container sub_table;
    struct route_table_subnet * next;
};

struct route4_table_network_container_entry {
    // The route_table_network_container contains nodes of this type, but
    // however you want to implement this container is up to you
    uint32_t network; // this is the key
    uint32_t metric;

    // route info

    struct route4_table_network_container_entry * next;
};

路线信息很棘手。您可以简单地在此处列出一个 IP 地址，并在您获得本地网络上的 IP 地址时识别并停止查找内容。这需要您识别何时要查找本地网络中的地址。这将使设置路由规则来发送数据包变得困难，这些数据包对于路由器来说看起来是本地地址，而这通常很有用。

您可以像 Linux 那样做，除了地址路由之外还允许使用接口路由。

您可能会通过使用一个标志来告诉它是什么类型的路由并使用一个包含该类型路由的数据的联合类型来实现这一点。这使得像 PPP 这样的接口，即使您知道调制解调器另一端机器的 IP 地址，也可以非常干净地工作。它还允许您本地连接的网络不会出现奇怪的情况。您只需像表中的任何其他地址一样查找它们，它们就会显示“使用以太网接口 0”。

在这种情况下，当您有一个数据包需要路由时，您会将目标 IP 地址传递给路由查找功能，该功能将返回最佳匹配。如果最佳匹配是 IP 地址条目，那么您将转身并在路由表中查找该 IP 地址，它将返回该地址的最佳匹配。您将继续此操作，直到达到接口匹配（因此需要接口匹配路由）。

您可能希望保留其查找导致接口路由条目的 IP 地址。对于以太网路由，您需要将此地址提供给 ARP 查找。最后匹配的 IP 可能与目标地址相同，也可能是与您的网络接口之一位于同一网络的路由器。

每次找到接口匹配时，您都可以在从route_lookup例程返回之前测试该接口是否仍然存在。如果接口不再存在，您可以将其删除，然后继续寻找最佳匹配。您不必在网络掩码列表中重新启动搜索，但需要确保您没有错过当前网络列表中的某个条目，该条目的度量比您刚刚注意到已删除的接口更昂贵。假设您的本地家庭网络有 WiFi 和有线以太网，但您刚刚拔掉了以太网，其使用成本低于 WiFi（以太网速度更快且耗电更少，因此您给了它一个更有利的指标）——您现在会您想要将这个数据包发送到 WiFi。

我不知道这与基数树实现相比如何。我怀疑它在 IPv4 的 32 位机器上会具有竞争力（取决于您如何选择route_table_network_container），但在 IPv6 中可能不太有利，其中地址大小较大并且不使用子网掩码（是吗？我不是遗憾的是对 IPv6 过于熟悉）

我完全忽略了这里的线程。我假设任何时候只有一个线程会访问路由表。如果不是这种情况，那么添加和删除节点将需要您包含某种类型的锁，这取决于您计划在其上实现此操作的平台。