Edward W Walters

US Patent:

20050102428, May 12, 2005

Filed:

Sep 23, 2004

Appl. No.:

10/948483

Inventors:

Nevin Heintze - Worthington OH, US
Edward Walters - Belchertown MA, US

International Classification:

G06F015/16
G06F012/00

US Classification:

709245000, 711108000, 711170000

Abstract:

To support IP routing table longest-prefix matching, a (ternary content-addressable) memory is managed by assigning its locations to interleaved pages and gaps. Each page has zero or more locations assigned to it, where all entries in a page have the same prefix length. Each gap has zero or more empty locations assigned to it. The pages are organized by descending prefix length. Associated with each page is a free-list identifying empty locations in that page. An “invariant” rule may dictate that first and last page locations cannot be empty. Whenever an entry is deleted from the first or last location in a page, that location is shifted (i.e., reassigned) to the adjacent gap. The direction chosen to search for an empty location for inserting a new entry is based on a global measure of the relative fullness of memory regions above and below the new entry's page.