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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

Do you have some spare memory?

Make a structure like this:

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

Now you can do lookups like so:

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

Answer 4

I found a cool paper on this subject called Longest Prefix Matching using Bloom Filters.

Abstract: We introduce the first algorithm that we are aware of to employ Bloom filters for Longest Prefix Matching (LPM). The algorithm performs parallel queries on Bloom filters, an efficient data structure for membership queries, in order to determine address prefix membership in sets of prefixes sorted by prefix length. We show that use of this algorithm for Internet Protocol (IP) routing lookups results in a search engine providing better performance and scalability than TCAM-based approaches.

Their basic idea is to use bloom filters stored in a processor's embedded SRAM (fast) to guide prefix hash table lookups in slower but more plentiful memory. For the IPv4 case they tune their algorithm to account for the fact that most of the routing table prefixes are 24 bits. For IPv6 they found only 14 unique prefix lengths in 1550 BGP entries.