问对子网列表进行匹配

EN

创建一个树，其中每个级别表示IP地址的n个位。在每个级别上存储子网，以便掩码位数在n * level和n * (level +1)之间。例如，对于n= 4，每个节点有16个子节点。因此，如果您正在对11.12.13.14 (== 0x0b0c0d0e)进行测试，您可以这样遍历树：

0 -> b -> 0 -> c -> 0 -> d -> 0 -> e

在节点上，跟踪具有相应大小的子网。我的意思是:0级应该有子网/1到/4 (包括)，第1级应该有子网/5到/8，等等，直到/29到/32。请注意，/0匹配所有内容，因此在数据结构中使用它是无用的。

要在树中搜索，将IP分组为n位组(在我的示例4中)。下降到匹配前n位的第一级，并在该级别上测试所有子网。如果没有找到，下降到与下一个n位匹配的下一个级别。

这样，您必须测试每个2^n子网的32/n级别。对于n=4，您必须测试8个级别，每个级别最多有16个子网。这件事很快就做好了。

Clarification：一个节点是一个子网，例如(在十六进制中，一个数字是一个小块，它是4位)：0a.5a.00.00/16。该节点的父网将是一个包含该子网的子网:例如: 0a.50.00.00/12。子节点的边缘可以解释为：" contains "，如in："this (父)子网包含由子节点表示的子网“。若要使此树包含所需的所有子网，则可能必须插入节点，这些节点表示不在列表中的子网。因此，将这些节点标记为辅助节点，这样您知道在搜索这棵树时，在树下有更多特定的子网，但是节点本身并不是要检查的子网列表的一部分。您只应该添加这些直接在列表中的节点，以及所有的父节点，以使节点可以在树结构中访问。

下面是一个关于我如何看待它的struct：

struct subnet_tree_node
{
    uint_32 ip;  // 32 bit IP address
    subnet_tree_node *children;
    uint_8 number_of_children;
    uint_8 mask; // number of bits for this subnet
    uint_8 valid; // wether this node is valid or auxiliary
}

所以你已经确定了性能是个问题。

• 将每个网络掩码/addr对看作一对IP地址:第一个有效的，最后一个有效的。
• 让我们假设最后有效总是奇怪的(不确定/32网络是否正确，但这真的非常奇怪)。
• 构造这些IP地址的排序向量。(如果网络重叠或有什么愚蠢之处，请抱怨。)
• 使用某种二进制chop搜索目标IP地址。
• 如果IP地址位于向量中，则为a) wierd；b)在其中一个子网中。
• 如果IP地址不在向量中，并且下面的值为偶数，则它位于子网中。如果下面的值是奇数，它就不在子网中。

你有证据证明表演是个问题吗？只有2^24个子网(您可以拥有/28子网，但是它们通常是组织内部的，所以即使组织有A类网络，仍然只有2^24个子网)。

做1600万and和比较是不需要时间的。

保持简单(直到你真的需要做得更好)。