为ipv6实施最长前缀匹配的最佳方法是什么？
为ipv6实施最长前缀匹配的最佳方法是什么？
提问于 2009-02-04 15:43:52
ipv6路由器将多个路由存储为地址的第一个n位。2000年，研究人员发现1500条ipv6路由中只有14个不同的前缀长度。传入的数据包根据最长的前缀匹配被路由到不同的传出端口，因此，如果数据包x的前8位与8位路由匹配，但同一数据包的前48位与48位路由匹配，则路由器必须选择48位路由。
我的路由器正在处理如此多的数据包，以至于在路由表中查找内存的速度是一个限制因素。在我的路由表中查找最长匹配前缀的好算法是什么？
回答 3
Stack Overflow用户
回答已采纳
发布于 2009-02-04 19:00:13
使用trie或radix-tree来存储“标准”前缀。后缀树/数组是一种不必要的过度杀伤力；它们用于查找中缀之间的匹配(利用任何中缀都是后缀的前缀这一事实，如果您想要找到几个字符串之间的匹配，请将它们彼此连接起来)，而不仅仅是前缀之间的匹配。
Stack Overflow用户
发布于 2009-02-04 16:06:10
我认为计算最长公共前缀的最有效方法通常是suffix tree或suffix array (运行时与预处理后的前缀长度成线性关系)。
Stack Overflow用户
发布于 2009-02-04 21:38:21
你有空闲的内存吗？
制作一个这样的结构：
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;页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/511903
复制相关文章
相似问题
腾讯云开发者
