# US 9,438,505 B1 · System and method for increasing capacity in router forwarding tables

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

- Number: US 9,438,505 B1
- Document ID: US9438505B1
- Status: Granted
- Kind: B1
- Application number: 13/434,094
- Filed: 2012-03-29
- Granted: 2016-09-06
- Earliest claimed: 2012-03-29
- Assignees: Google Inc.
- Applicants: Junlan Zhou; Zhengrong Ji
- Inventors: Junlan Zhou; Zhengrong Ji
- Web page: https://patentgrep.com/patent/US9438505B1

## CPC

- H04L 45/74591: {using content-addressable memories [CAM]}
- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- H04L 47/24: Traffic characterised by specific attributes, e.g. priority or QoS
- H04L 47/32: by discarding or delaying data units, e.g. packets or frames
- H04L 49/3009: {Header conversion, routing tables or routing tags}
- H04W 40/04: based on wireless node resources
- H04W 40/246: {Connectivity information discovery}
- H04L 47/2483: involving identification of individual flows
- H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

A multi-stage TCAM may include a plurality of tables on a pipeline and may store flow rules, including a key, an action, and a priority. The flow rule's key, which may consist of a number of bits, may be divided into several buckets. For each bucket, a hardware table on the multi-stage TCAM may be created. The first bucket may be used as a lookup key to the first table, and an output from this first table may be used as a lookup key to the next table on the pipeline. Because the full flow key need not be stored in a single TCAM table, a capacity of the TCAM can be maximized with its width minimized.

## Claims

### Claim 1

A method for routing a data packet received at a router, comprising:
accessing a multi-stage forwarding table in memory, the multi-stage forwarding table including a plurality of tables linked in a pipeline, each table of the plurality of tables including a plurality of entries, and each entry includes a lookup key and a corresponding output;
wherein:
respective lookup keys of entries of a first table of the plurality of tables include bits from flow keys selected from a first set of flow key bit positions belonging to a plurality of sets of flow key bit positions,
respective lookup keys of entries in each of at least one remaining table of the plurality of tables include the output of an entry of an immediately preceding table and bits from flow keys selected from respective corresponding additional sets of flow key bit positions belonging to the plurality of sets of flow key bit positions,
respective outputs in the entries of a last table of the plurality of tables include respective actions for forwarding a data packet,
each set of flow key bit positions includes bit positions that do not overlap with bit positions in any other set of flow key bit positions belonging to the plurality of sets of flow key bit positions;
receiving a data packet at an input port of the router, the data packet including routing information of the data packet;
obtaining a received data packet flow key based on the routing information included in the received data packet;
matching bits in the first set of flow key bit positions in the received data packet flow key to a lookup key in the first table of the plurality of tables;
sequentially for each remaining table:
matching a combination of bits in a corresponding set of flow key bit positions in the received data packet flow key and an output from an entry in an immediately preceding table with lookup keys of entries in the respective table to determine a respective output; and
routing the data packet based on forwarding information included in determined output of the last table.

### Claim 2 (depends on 1)

The method of claim 1, further comprising reducing a width of at least one table of the plurality of tables.

### Claim 3 (depends on 2)

The method of claim 2, wherein reducing a width of at least one table of the plurality of tables includes reducing a width of one of the remaining tables of the plurality of tables by reducing a width of an output in an entry of the immediately preceding table, and reducing a width of the lookup key in an entry in the one of the remaining tables that includes the output of the immediately preceding table.

### Claim 4 (depends on 2)

The method of claim 2, wherein reducing the width of at least one table of the plurality of tables includes reducing a number of outputs in the at least one table of the plurality of tables, and reducing a number of bits used to represent a reduced number of outputs in the at least one table.

### Claim 5 (depends on 2)

The method of claim 2, wherein reducing the width of at least one table of the plurality of tables includes aggregating two or more different lookup keys having a same output into a single lookup key.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
determining a minimum configurable width of the last table of the plurality of tables;
setting a configurable width of the last table of the plurality of tables to the minimum configurable width;
identifying candidate sets of flow key bit positions;
determining a first candidate set of flow key bit positions from the candidate sets of flow key bit positions such that a first sum of a width of the first candidate set of flow key bit positions and a width of an output from an immediately preceding table is less than the configurable width of the last table of the plurality of tables;
using the first candidate set of flow key bit positions as the set of flow key bit positions corresponding to the last table of the plurality of tables.

### Claim 7 (depends on 6)

The method of claim 6, further comprising, if the first candidate set of flow key bit positions cannot be determined for the configurable width that is set to the minimum configurable width of the last table:
repeatedly increasing the configurable width of the last table of the plurality of tables until one candidate set of flow key bit positions, from the candidate sets of flow key bit positions, can be determined such that a sum of a width of the one candidate set of flow key bit positions and a width of an output from the immediately preceding table is less than a current configurable width of the last table.

### Claim 8 (depends on 6)

The method of claim 6, further comprising:
determining a minimum configurable width of a second table of the plurality of tables, the second table immediately preceding the last table of the plurality of tables;
excluding the first candidate set of flow key bits from the candidate sets of flow key bits to create a remainder candidate sets of flow key bits;
determining a second candidate set of flow key bit positions from the remainder candidate sets of flow key bit positions such that a second sum of a width of the second candidate set of flow key bit positions and a width of an output from an immediately preceding table is less than the minimum configurable width of the second table of the plurality of tables; and
using the second candidate set of flow key bit positions as the set of flow key bit positions corresponding to the second table of the plurality of tables.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
identifying a new rule to be added to the multi-stage forwarding table, the new rule including a new flow key and a new action;
dividing the new flow key into a plurality of proposed lookup key bits, each of the plurality of proposed lookup key bits including bits from the new flow key selected from a corresponding set of flow key bit positions of the plurality of sets of flow key bit positions;
for each of the plurality of tables:
creating a new entry having a new lookup key and a new output, the new lookup key including the respective proposed lookup key bits, if the respective proposed lookup key bits are not found in a lookup key in any of the respective entries,
wherein creating a new entry in the last table of the plurality of tables includes storing the new action included in the new rule as the new output of the new entry in the last table.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
identifying a rule to be deleted from the multi-stage forwarding table, the rule including candidate flow key and a candidate action;
dividing the candidate flow key into a plurality of proposed lookup key bits, each of the plurality of proposed lookup key bits including bits from the candidate flow key selected from respective corresponding set of flow key bit positions;
for each of the plurality of tables:
identifying an entry having a lookup key that includes the respective proposed lookup key bits;
deleting the identified entry if the lookup key of the identified entry is not shared with another rule.

### Claim 11

A network router comprising:
a memory storing a multi-stage forwarding table, the multi-stage forwarding table including a plurality of tables linked in a pipeline, each table of the plurality of tables including a plurality of entries, and each entry including a lookup key and a corresponding output,
wherein:
respective lookup keys of entries of a first table of the plurality of tables include bits from flow keys selected from a first set of flow key bit positions belonging to a plurality of sets of flow key bit positions,
respective lookup keys of the entries in each of the remaining tables of the plurality of tables include the output of an entry of an immediately preceding table and bits from flow keys selected from respective corresponding additional sets of flow key bit positions belonging to the plurality of sets of flow key bit positions,
respective outputs in the entries of a last table of the plurality of tables include respective actions for forwarding a data packet, and
each set of flow key bit positions includes bit positions that do not overlap with bit positions in any other set of flow key bit positions belonging to the plurality of sets of flow key bit positions;
an input port configured to receive a data packet from a network, the data packet including routing information; and
a processor coupled to the memory and to the input port configured to:
obtain a received data packet flow key based on the routing information included in the received data packet;
match bits in the first set of flow key bit positions in the received data packet flow key to a lookup key in the first table of the plurality of tables;
sequentially for each remaining table:
match a combination of bits in a corresponding set of flow key bit positions in the received data packet flow key and an output from an entry in an immediately preceding table with lookup keys of entries in the respective table to determine a respective output; and
route the data packet based on forwarding information included in determined output of the last table.

### Claim 12 (depends on 11)

The router of claim 11, wherein the processor is further configured to reduce a width of at least one table of the plurality of tables.

### Claim 13 (depends on 12)

The router of claim 12, wherein the processor is further configured to reduce a width of one of the remaining tables of the plurality of tables by reducing a width of an output in an entry of the immediately preceding table, and reducing a width of the lookup key in an entry in the one of the remaining tables that includes the output of the immediately preceding table.

### Claim 14 (depends on 12)

The router of claim 12, wherein the processor is further configured to reduce a number of outputs in the at least one table of the plurality of tables, and reduce a number of bits used to represent a reduced number of outputs in the at least one table.

### Claim 15 (depends on 12)

The router of claim 12, wherein the processor is further configured to aggregate two or more different lookup keys having a same output into a single lookup key.

### Claim 16 (depends on 11)

The router of claim 11, wherein the processor is further configured to:
determine a minimum configurable width of the last table of the plurality of tables;
set a configurable width of the last table of the plurality of tables to the minimum configurable width;
identify candidate sets of flow key bit positions;
determine a first candidate set of flow key bit positions from the candidate sets of flow key bit positions such that a first sum of a width of the first candidate set of flow key bit positions and a width of an output from an immediately preceding table is less than the configurable width of the last table of the plurality of tables;
use the first candidate set of flow key bit positions as the set of flow key bit positions corresponding to the last table of the plurality of tables.

### Claim 17 (depends on 16)

The router of claim 16, wherein the processor is further configured to, if the first candidate set of flow key bit positions cannot be determined for the configurable width that is set to the minimum configurable width of the last table:
repeatedly increase the configurable width of the last table of the plurality of tables until one candidate set of flow key bit positions, from the candidate sets of flow key bit positions, can be determined such that a sum of a width of the one candidate set of flow key bit positions and a width of an output from the immediately preceding table is less than a current configurable width of the last table.

### Claim 18 (depends on 16)

The router of claim 16, wherein the processor is further configured to:
determine a minimum configurable width of a second table of the plurality of tables, the second table immediately preceding the last table of the plurality of tables;
exclude the first candidate set of flow key bits from the candidate sets of flow key bits to create a remainder candidate sets of flow key bits;
determine a second candidate set of flow key bit positions from the remainder candidate sets of flow key bit positions such that a second sum of a width of the second candidate set of flow key bit positions and a width of an output from an immediately preceding table is less than the minimum configurable width of the second table of the plurality of tables; and
use the second candidate set of flow key bit positions as the set of flow key bit positions corresponding to the second table of the plurality of tables.

### Claim 19 (depends on 11)

The router of claim 11, wherein the processor is further configured to:
identify a new rule to be added to the multi-stage forwarding table, the new rule including a new flow key and a new action;
divide the new flow key into a plurality of proposed lookup key bits, each of the plurality of proposed lookup key bits including bits from the new flow key selected from a corresponding set of flow key bit positions of the plurality of sets of flow key bit positions;
for each of the plurality of tables:
create a new entry having a new lookup key and a new output, the new lookup key including the respective proposed lookup key bits, if the respective proposed lookup key bits are not found in a lookup key in any of the respective entries,
wherein creating a new entry in the last table of the plurality of tables includes storing the new action included in the new rule as the new output of the new entry in the last table.

### Claim 20 (depends on 11)

The router of claim 11, wherein the processor is further configured to:
identify a rule to be deleted from the multi-stage forwarding table, the rule including a candidate flow key and a candidate action;
divide the candidate flow key into a plurality of proposed lookup key bits, each of the plurality of proposed lookup key bits including bits from the candidate flow key selected from a corresponding set of flow key bit positions of the plurality of sets of flow key bit positions;
for each of the plurality of tables:
identify an entry having a lookup key that includes the respective proposed lookup key bits, and
delete the identified entry if the lookup key of the identified entry is not shared with another rule.

### Claim 21 (depends on 11)

The router of claim 11, wherein the memory is a tertiary content addressable memory (TCAM).