Browse Prior Art Database

FAST IP-FORWARDING METHOD

IP.com Disclosure Number: IPCOM000014145D
Original Publication Date: 2001-May-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 3 page(s) / 56K

Publishing Venue

IBM

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 32% of the total text.

Page 1 of 3

FAST IP-FORWARDING METHOD

  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:

With 64 Mbit memory, it is feasible to inspect only the first 24-bits of the IP address first: This requires a lookup-table of 224 = 16 Million entries. I.e. a single 64 Million bit memory chip would return for every 24-bit address a four-bit 'handle'. This handle is enough to address 16 different output (i.e. next-hop) destinations. Sixteen is typically the number of ports/adapters a backbone Router has. In using two memory chips, an 8-bit handle could be returned, which would allow more finer-grain handling: e.g. to submit the packet to a second stage of inspection to also include the remaining low-order 8 bits of the destination address in...