Back to results
US 9,438,505 B1Granted
System and method for increasing capacity in router forwarding tables
AssigneeGoogle Inc.
InventorsJunlan Zhou, Zhengrong Ji
Life of this patent
Estimating the term…
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.
Claims21
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.
10 more elements
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.
12 more elements
Dependencies are inferred from the claim text.