# US 2008/0186970 A1 · System and method of fast adaptive TCAM sorting for IP longest prefix matching

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0186970 A1
- Document ID: US20080186970A1
- Status: Published application
- Kind: A1
- Application number: 11/702,554
- Filed: 2007-02-06
- Published: 2008-08-07
- Earliest claimed: 2007-02-06
- Assignees: Alcatel Lucent
- Inventors: James Wisener; Adrian Grah
- Web page: https://patentgrep.com/patent/US20080186970A1

## CPC

- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- H04L 45/54: {Organization of routing tables}
- H04L 45/74591: {using content-addressable memories [CAM]}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A system and method are provided for sorting IP routing table entries in a TCAM for longest IP prefix matching LPM of destination IP addresses. The IP routing table is divided into logical blocks, for each block an associated routing entry IP prefix length. Each block is of a respective size whose proportion of the total size of the routing table is determined by the associated IP prefix length. The blocks are ordered so that the TCAM returns an LPM when queried. Starting block sizes can be initialized to proportions which reflect actual expected numbers by proportion of routing entries by IP prefix length. The blocks also grow and shrink as entries are added and deleted so as to more closely mirror real-world populations of expected entries having the IP prefix length in question.

## Claims

### Claim 1

A method of managing a routing table of a TCAM for longest IP prefix matching, the method comprising:
dividing the routing table into a plurality of logical blocks wherein each logical block is associated with a respective IP prefix length and is for storing respective routing entries having said respective IP prefix length, and wherein each logical block is of a respective size whose proportion to a total size of the routing table is determined by the respective IP prefix length, and wherein said plurality of logical blocks are ordered in said routing table such that the TCAM returns a longest IP prefix match when passed an IP address.

### Claim 2 (depends on 1)

A method of managing a routing table of a TCAM according to claim 1 wherein said proportion for each respective size of each logical block is determined by the respective IP prefix length, by being initialized to an expected proportion of non-empty routing entries of said IP prefix length to a total number of non-empty routing entries in the routing table during operation.

### Claim 3 (depends on 1)

A method of managing a routing table of a TCAM according to claim 1 wherein said proportion for each respective size of each logical block is determined by the respective IP prefix length, by being changed in accordance with an actual proportion of non-empty routing entries of said IP prefix length to a total number of non-empty routing entries in the routing table during operation.

### Claim 4 (depends on 2)

A method of managing a routing table of a TCAM according to claim 2 wherein adding a routing entry to a logical block of said plurality of logical blocks of said table comprises:
inserting the routing entry into the center of the logical block if the logical block is empty;
inserting the routing entry into an empty entry adjacent to a used portion of the logical block on a side of the used portion which has a greatest number of empty entries, if the logical block has non-empty entries and empty entries; and
growing the logical block into an adjacent empty portion of a neighboring logical block, if the logical block is full, and inserting the routing entry into said adjacent empty portion in an empty entry adjacent to a used portion of the logical block.

### Claim 5 (depends on 4)

A method of managing a routing table of a TCAM according to claim 4 wherein the adjacent empty portion of the neighboring logical block is larger than a second adjacent empty portion, if any, of a second neighboring logical block, if any, and wherein half of said adjacent empty portion is taken by said logical block in said growing of the logical block.

### Claim 6 (depends on 4)

A method of managing a routing table of a TCAM according to claim 4 wherein adding a routing entry to a logical block of said plurality of logical blocks of said table further comprises:
if there is no adjacent empty portion in said neighboring logical block before said step of growing, creating said adjacent empty portion by shifting an adjacent neighboring routing entry of said neighboring logical block to a second empty portion of said neighboring logical block.

### Claim 7 (depends on 6)

A method of managing a routing table of a TCAM according to claim 6 wherein the second empty portion of said neighboring logical block is larger than a third empty portion, if any, of a second neighboring logical block, if any.

### Claim 8 (depends on 6)

A method of managing a routing table of a TCAM according to claim 6 wherein adding a routing entry to a logical block of said plurality of logical blocks of said table further comprises:
if there is no second empty portion in said neighboring logical block before said step of creating said adjacent empty portion, creating said second empty portion by growing the neighboring logical block into a further adjacent empty portion of a further neighboring logical block.

### Claim 9 (depends on 4)

A method of managing a routing table of a TCAM according to claim 4 wherein deleting a routing entry to be deleted from said logical block of said plurality of logical blocks of said table comprises:
copying a non-empty routing entry, from a used portion of said logical block and adjacent to an empty portion of said logical block, over said routing entry to be deleted; and
clearing said non-empty routing entry creating an empty entry.

### Claim 10 (depends on 9)

A method of managing a routing table of a TCAM according to claim 9 wherein the empty portion of said logical block is larger than a second empty portion, if any, of said logical block.

### Claim 11

A system for routing IP packets according to longest IP prefix matching, the system comprising:
a TCAM having a routing table for longest IP prefix matching; and
a table manager for dividing the routing table into a plurality of logical blocks wherein each logical block is associated with a respective IP prefix length and is for storing respective routing entries having said respective IP prefix length, and wherein each logical block is of a respective size whose proportion to a total size of the routing table is determined by the respective IP prefix length,
wherein said plurality of logical blocks are ordered in said routing table such that the TCAM returns a longest IP prefix match when passed an IP address.

### Claim 12 (depends on 11)

A system for routing IP packets according to longest IP prefix matching according to claim 11 wherein said proportion for each respective size of each logical block is determined by the respective IP prefix length, by being initialized by said table manager to an expected proportion of non-empty routing entries of said IP prefix length to a total number of non-empty routing entries in the routing table during operation.

### Claim 13 (depends on 11)

A system for routing IP packets according to longest IP prefix matching according to claim 11 wherein said proportion for each respective size of each logical block is determined by the respective IP prefix length, by being changed by said table manager in accordance with an actual proportion of non-empty routing entries of said IP prefix length to a total number of non-empty routing entries in the routing table during operation.

### Claim 14 (depends on 12)

A system for routing IP packets according to longest IP prefix matching according to claim 12 wherein the table manager is further for adding a routing entry to a logical block of said plurality of logical blocks of said table by:
inserting the routing entry into the center of the logical block if the logical block is empty;
inserting the routing entry into an empty entry adjacent to a used portion of the logical block on a side of the used portion which has a greatest number of empty entries, if the logical block has non-empty entries and empty entries; and
growing the logical block into an adjacent empty portion of a neighboring logical block, if the logical block is full, and inserting the routing entry into said adjacent empty portion in an empty entry adjacent to a used portion of the logical block.

### Claim 15 (depends on 14)

A system for routing IP packets according to longest IP prefix matching according to claim 14 wherein the adjacent empty portion of the neighboring logical block is larger than a second adjacent empty portion, if any, of a second neighboring logical block, if any, and wherein half of said adjacent empty portion is taken by said logical block in said growing of the logical block.

### Claim 16 (depends on 14)

A system for routing IP packets according to longest IP prefix matching according to claim 14 wherein said table manager is further for adding a routing entry to a logical block of said plurality of logical blocks of said table by:
if there is no adjacent empty portion in said neighboring logical block before said step of growing, creating said adjacent empty portion by shifting an adjacent neighboring routing entry of said neighboring logical block to a second empty portion of said neighboring logical block.

### Claim 17 (depends on 16)

A system for routing IP packets according to longest IP prefix matching according to claim 16 wherein the second empty portion of said neighboring logical block is larger than a third empty portion, if any, of a second neighboring logical block, if any.

### Claim 18 (depends on 16)

A system for routing IP packets according to longest IP prefix matching according to claim 16 wherein said table manager is further for adding a routing entry to a logical block of said plurality of logical blocks of said table by:
if there is no second empty portion in said neighboring logical block before said step of creating said adjacent empty portion, creating said second empty portion by growing the neighboring logical block into a further adjacent empty portion of a further neighboring logical block.

### Claim 19 (depends on 14)

A system for routing IP packets according to longest IP prefix matching according to claim 14 wherein said table manager is for deleting a routing entry to be deleted from said logical block of said plurality of logical blocks of said table by:
copying a non-empty routing entry, from a used portion of said logical block and adjacent to an empty portion of said logical block, over said routing entry to be deleted; and
clearing said non-empty routing entry creating an empty entry.

### Claim 20 (depends on 19)

A system for routing IP packets according to longest IP prefix matching according to claim 19 wherein the empty portion of said logical block is larger than a second empty portion, if any, of said logical block.

### Claim 21 (depends on 19)

A system for routing IP packets according to longest IP prefix matching according to claim 19 wherein each logical block associated with a small IP prefix length has an initial size of two to the power of the prefix length.

### Claim 22 (depends on 19)

A system for routing IP packets according to longest IP prefix matching according to claim 19 wherein logical blocks associated with medium IP prefix lengths have a majority of entries.

### Claim 23 (depends on 22)

A system for routing IP packets according to longest IP prefix matching according to claim 22 wherein the IP packets are IPv4 packets, and wherein an expected proportion of non-empty routing entries having an IP prefix length of 24 to a total number of non-empty routing entries in the routing table during operation is greater than 50 percent.
