iptrie

这个crate实现了针对IP地址和前缀查找的专用Trie。

它为Ipv4、Ipv6以及两者混合提供了集合和映射。

每个结构都有两个版本

• 一个基于Patricia Trie，可以看作是一个标准的带查找操作（寻找最长前缀匹配）的映射或集合
• 另一个基于Level-Compressed Trie（LC-Trie），针对查找操作（最长前缀匹配）进行了优化，但不能修改

示例

fn main()
{
    let prefixes = [
        "1.1.0.0/24",
        "1.1.1.0/24",
        "1.1.0.0/20",
        "1.1.2.0/24"
    ];

    let iter = prefixes.iter().map(|x| x.parse::<Ipv4Prefix>().unwrap());

    // a set based on Patricia trie
    let trie = Ipv4RTrieSet::from_iter(iter);

    // lpm lookup for Ipv4 address
    assert_eq!(trie.lookup(&"1.1.1.2".parse::<Ipv4Addr>().unwrap()).to_string(), "1.1.1.0/24");
    assert_eq!(trie.lookup(&"1.1.2.2".parse::<Ipv4Addr>().unwrap()).to_string(), "1.1.0.0/20");

    // lpm lookup for Ipv4 prefix also works
    assert_eq!(trie.lookup(&"1.1.0.0/25".parse::<Ipv4Prefix>().unwrap()).to_string(), "1.1.0.0/24");
    assert_eq!(trie.lookup(&"1.1.0.0/21".parse::<Ipv4Prefix>().unwrap()).to_string(), "1.1.0.0/20");


    // now, compute the set based on LC-trie
    let lctrie = trie.compress();

    // lpm lookup for Ipv4 address
    assert_eq!(lctrie.lookup(&"1.1.1.2".parse::<Ipv4Addr>().unwrap()).to_string(), "1.1.1.0/24");
    assert_eq!(lctrie.lookup(&"1.1.2.2".parse::<Ipv4Addr>().unwrap()).to_string(), "1.1.0.0/20");

    // lpm lookup for Ipv4 prefix also works
    assert_eq!(lctrie.lookup(&"1.1.0.0/25".parse::<Ipv4Prefix>().unwrap()).to_string(), "1.1.0.0/24");
    assert_eq!(lctrie.lookup(&"1.1.0.0/21".parse::<Ipv4Prefix>().unwrap()).to_string(), "1.1.0.0/20");
}

性能

对于这个crate，我们希望在插入操作的同时实现最高的查找性能。在接下来的章节中，我们将与crate ip_network_table-deps-treebitmap 进行比较，该crate通过 IpLookupTable 进行标识。

查找算法

随机生成的前缀

我们为Ipv4和Ipv6生成了100万个随机前缀，以便填充查找表。然后，我们使用随机生成的IP地址检查了查找过程。

基于树形图的查找表是最佳选择。

BGP前缀

但是，互联网有一个非随机的内部结构。因此，我们使用了一个包含超过1M个Ipv4前缀和超过175k个Ipv6前缀的真实BGP表。然后，我们使用随机生成的IP地址检查了查找过程。

这次，基于LC-Trie的查找性能最佳。

构建Trie

耗时

我们从100k个随机Ipv4前缀和同样数量的Ipv6前缀中构建了查找表，然后从真实BGP表中的100k个前缀中为Ipv4和同样数量的Ipv6前缀构建了查找表。

BGP表按前缀顺序读取并插入（即，最长的前缀先），这是构建前缀Trie的最佳情况。

请注意，构建LC-Trie包括构建Patricia Trie然后压缩。

内存

我们使用包含超过1M个IPv4前缀和超过175k个IPv6前缀的真实BGP表。

IpLookupTable无疑是内存有限的程序的理想选择。

（我猜我将在下一个版本中处理这个问题）