title: What is the best way to implement longest-prefix matching for ipv6?
body: <p>An ipv6 router stores a number of routes as the first <code>n</code> 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.</p>
  
  <p>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?</p>