为ipv6实现最长前缀匹配的最佳方法是什么？ [英] What is the best way to implement longest-prefix matching for ipv6?

问题描述

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

An ipv6 router stores a number of routes as the first n bits of the address. In 2000, researchers found only 14 distinct prefix lengths in 1500 ipv6 routes. Incoming packets are routed to different outgoing ports based on the longest prefix match, so if the first 8 bits of packet x match an 8 bit route but the first 48 bits of the same packet match a 48-bit route then the router must choose the 48-bit route.

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

My router is processing so many packets that the speed of memory lookup into the routing table is a limiting factor. What is a good algorithm to find the longest matching prefix in my routing table?

推荐答案

使用 trie 或 radix-tree 来存储标准前缀。后缀树/数组是不必要的过度杀伤；它们用于查找后缀之间的匹配项（使用任何后缀均是后缀的前缀这一事实，如果要在多个字符串之间找到匹配项，则将它们彼此连接），而不是只是在前缀之间。

Use either a trie or a radix-tree to store the "standard" prefixes. A suffix tree/array is an unnecessary over-kill; they are used to find matches between infixes (using the fact that any infix is a prefix of a suffix, and if you want to find a match between several strings, concatenate them to one another), and not just between prefixes.

这篇关于为ipv6实现最长前缀匹配的最佳方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！