What is the best way to implement longest-prefix search for ipv6?

Question

The ipv6 router stores several routes as the first bits of an n address. In 2000, researchers found only 14 different prefix lengths in 1,500 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 correspond to an 8-bit route, but the first 48 bits of the same packet correspond to a 48-bit route, then the router should select 48-bit route.

My router processes so many packets that the search speed in memory in the routing table is a limiting factor. What is a good algorithm for finding the longest matching prefix in my routing table?

Answer 1

Use a trie or base-base to save the "standard" prefixes. Suffix tree / array - unnecessary super-kill; they are used to find matches between infixes (using the fact that any infix is ​​a suffix prefix, and if you want to find a match between several lines, connect them to each other), and not just between prefixes.

Answer 2

I found a cool paper on this subject called The Longest Match Prefix Using Color Filters .

Abstract: We introduce the first algorithm that we know to use Bloom filters for Longest Prefix Matching (LPM). The algorithm performs concurrent requests for Bloom filters, an efficient data structure for membership requests to determine membership in an address prefix in sets of prefixes sorted by prefix length. We show that using this algorithm to search for Internet routing (IP) leads to a search engine that provides better performance and scalability than TCAM-based approaches.

The basic idea is to use flowering filters stored in the built-in SRAM processor (fast) to search for hash table tables of prefixes in slower but more numerous memory. For the IPv4 case, they configure their algorithm to take into account the fact that most routing table prefixes are 24 bits. For IPv6, they found only 14 unique prefix lengths in 1,550 BGP entries.

Answer 3

I believe that the most efficient way to calculate the longest common prefix in the general case is a suffix tree or suffix array (the runtime is linear along the length of the prefix after preprocessing).

Answer 4

Do you have spare memory?

Create a structure like this:

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

Now you can search as follows:

 Node* table = root; for (i=0; table != NULL; i++) { node = table[address_byte[i]]; table = node->table; } destination = node->port;