data-structures - IPv6 查找数据结构

Question

patricia trie 是众所周知的推荐数据结构，用于存储 IPv4 分配/分配和执行查找。

IPv6 地址也是如此吗？只是更深/更高的尝试来容纳额外的 96 位？trie 仍然是 patricia，还是不同的 radix trie？

Answer 1

您仍然可以使用具有更大深度的 Patricia 尝试，但问题是性能随 trie 深度线性下降。为 IPv6 查找设计专门的数据结构是一个活跃的领域。最近的出版物包括：

• 用于 IPv6 查找的动态二进制散列方案(PDF)
• 对 100Gbps 核心路由器线卡使用分布式和负载平衡布隆过滤器的 IPv6 查找(PDF)
• FlashTrie：用于超过 100Gbps 的 IP 路由查找的基于哈希的前缀压缩 Trie (PDF)

我不知道这些数据结构的任何可用（开源）实现。