5

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

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

4

4 回答 4

5

使用trie或基数树来存储“标准”前缀。后缀树/数组是不必要的过度杀戮；它们用于查找中缀之间的匹配（使用任何中缀都是后缀的前缀这一事实，如果您想在多个字符串之间找到匹配，请将它们相互连接），而不仅仅是在前缀之间。

于 2009-02-04T19:00:13.303 回答
2

我发现了一篇关于这个主题的很酷的论文，叫做Longest Prefix Matching using Bloom Filters。

摘要：我们介绍了我们知道的第一个算法，它使用 Bloom 过滤器进行最长前缀匹配 (LPM)。该算法对布隆过滤器（一种用于成员查询的有效数据结构）执行并行查询，以确定按前缀长度排序的前缀集中的地址前缀成员资格。我们表明，将这种算法用于 Internet 协议 (IP) 路由查找会导致搜索引擎提供比基于 TCAM 的方法更好的性能和可扩展性。

他们的基本想法是使用存储在处理器的嵌入式 SRAM（快速）中的布隆过滤器来指导在较慢但更充足的内存中查找前缀哈希表。对于 IPv4 情况，他们调整算法以解释大多数路由表前缀都是 24 位的事实。对于 IPv6，他们在 1550 个 BGP 条目中仅发现 14 个唯一前缀长度。

于 2009-02-10T20:56:12.847 回答
0

我相信通常计算最长公共前缀的最有效方法是后缀树或后缀数组（运行时与预处理后的前缀长度成线性关系）。

于 2009-02-04T16:06:09.863 回答
0

你有多余的内存吗？

做一个这样的结构：

typedef struct node {
  struct node* table[256];
  Port_type port;
} Node;
Node* root[256];

现在您可以像这样进行查找：

Node* table = root;
for (i=0; table != NULL; i++)
{
   node = table[address_byte[i]];
   table = node->table;
}
destination = node->port;
于 2009-02-04T21:38:20.990 回答