Browse Prior Art Database

FAST IP-FORWARDING METHOD Disclosure Number: IPCOM000014145D
Original Publication Date: 2001-May-01
Included in the Prior Art Database: 2003-Jun-19

Publishing Venue



A key function in the Internet of today is the forwarding i.e. "routing" of packets. Routing is accomplished by inspecting the 32-bit destination address in the IP (IP version 4) header and using the leftmost bits in the destination address to retrieve the next-hop address from a routing information base. Today, in the Internet, Classless Interdomain Routing (CIDR) is the common method used, which requires finding the longest entry in the routing information base which is a leading substring (also known as prefix) of the destination IP address. This longest-prefix matching process is tedious and costly. The routing information base is kept up-to-date by routing protocols. Basically, a 32-bit IP destination address can address 232 (4 Billion) destinations. A direct addressing of a 4 Billion entry table has long be thought to be impractical, because it was not feasible to build and maintain such a table. This direct addressing is tempting because it would completely eliminate the need for the mentioned complex longest-prefix matching. Of course, as with CIDR there is some information hiding done, a direct lookup method will have multiple identical entries in the lookup table, which are determined by the subset defined by the CIDR-prefix at hand.The following calculation shows, that with technology improvements currently underway, this 4 Billion entry table might no longer be so impractical: With 64 Megabit memory capacity on-line in 1998, and assuming Moore's law to hold (quadrupling memory capacity every three years), in 2007 it will be possible to have chips with 4 Billion bits of capacity: i.e. 1 bit in a chip for each possible IP-address. Of course, 128-bit IP addresses are on the horizon (IPv6). But IPv6 is a major restructuring of the internet, and has been continuously moved into the future by inventions in the past. One of these is the already mentioned Classless Interdomain Routing (CIDR) method. From a forwarding perspective, CIDR results in a compression of the number of entries in the routing information base, and because of the 'information hiding' it does, it sometimes requires less bits to be inspected in order to make the IP-forwarding decision. This could be used to implement on the basis of the direct lookup outlined above, fast routing already today: