APPARATUS AND FAST SEARCH ALGORITHMS FOR EFFICIENT NETWORK PACKET ROUTING
Original Publication Date: 2000-May-01
Included in the Prior Art Database: 2002-Sep-20
Internet (IP) address lookup is a major bottleneck in high-performance routers and switches. With Internet growth, the problem is compounded because of routing lookup table sizes, increased traf fic, higher speed link and migration of 128-bit IPv6 addresses. This paper describes an algorithm for building IP lookup tables for efficient and fast searching (10Ox faster than today's state of the art router) using network addressing field decomposition and horizontal pointers.