algorithm - 为 ipv6 实现最长前缀匹配的最佳方法是什么？

Question

一个 ipv6 路由器将许多路由存储为地址的前 n 位。 2000 年，研究人员在 1500 条 ipv6 路由中只发现了 14 个不同的前缀长度。传入数据包根据最长前缀匹配路由到不同的传出端口，因此如果数据包 x 的前 8 位匹配 8 位路由，但同一数据包的前 48 位匹配 48 位路由，则路由器必须选择48 位路由。

我的路由器正在处理如此多的数据包，以至于内存查找路由表的速度成为一个限制因素。在我的路由表中找到最长匹配前缀的好算法是什么？

Answer 1

使用 trie或 radix-tree存储“标准”前缀。后缀树/数组是不必要的矫枉过正；它们用于查找 infixes 之间的匹配项(使用任何中缀都是后缀的前缀这一事实，如果您想在多个字符串之间找到匹配项，请将它们连接起来)，而不是就在前缀之间。