IPv6查找数据结构

Question

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

这对IPv6地址也是如此吗？只是更深/更高的trie来容纳额外的96位？特里仍然是帕特里夏,还是一个不同的基数特里？

Answer 1

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

\n\n

\n
• 用于 IPv6 查找的动态二进制哈希方案(PDF)
\n
• 使用分布式和负载平衡布隆过滤器进行 100Gbps 核心路由器线卡的 IPv6 查找(PDF)
\n
• FlashTrie：基于哈希的 Pre\xef\xac\x81x 压缩 Trie，用于超过 100Gbps 的 IP 路由查找(PDF)
\n

\n\n

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

\n