US 12,764,068 B2Granted

Updating multiple LPM (longest prefix match) tables

AssigneeArista Networks, Inc.

InventorsGanesan Venkataraman, Chen Jia Jang, Bhavin Rameshbhai Patel

Life of this patent

Estimating the term…

Loading patent…

Abstract

Route updates from multiple sources are stored in a forwarding information base (FIB). An agent executing on the network device reads routes stored in the FIB and inserts them into a trie. Route groups from among the routes stored in the trie are identified based on storage capabilities of the longest prefix match (LPM) tables into which the routes will be programmed. Routes in each route group are distributed among the LPM tables according to prefix lengths, the first LPM table receives a subset of routes having the longest prefix lengths, a second LPM table receives the next subset of routes with the next longest prefix lengths, and so on.

Claims20

Dependent claims

A method in a network device for updating routes in at least a first LPM (longest prefix match) table and a second LPM table in the network device, the method comprising:

receiving routes and storing the received routes in a FIB (forwarding information base);
and
updating the first and second LPM tables with routes stored in the FIB, including:
inserting routes stored in the FIB into a single trie data structure;
identifying a plurality of route groups from among the routes stored in the trie data structure, each route group comprising a corresponding plurality of routes, each route group associated with a pivot prefix determined based on prefixes of the corresponding plurality of routes;
and
distributing routes in each of the plurality of route groups between the first LPM table and the second LPM table, including for each route group:
storing the pivot prefix of the route group into a same entry in a first TCAM of the first LPM table and a second TCAM of the second LPM table;
sorting the plurality of routes in the route group in order of decreasing prefix lengths of the the routes;
storing a first subset of the plurality of routes in the route group into a first data store of the first LPM table;
associating the entry in the first TCAM with the first subset of routes stored in the first LPM table;
storing a second subset of the plurality of routes in the route group into a second data store of the second LPM table;
and
associating the entry in the second TCAM with the second subset of routes stored in the second LPM table,
wherein routes in the first subset of routes have longer prefixes than prefixes of routes in the second subset of routes.

12 more elements

A non-transitory computer-readable storage device in a network device, the non-transitory computer-readable storage device having stored thereon computer executable instructions, which when executed, cause the network device to:

receive routes and storing the received routes in a FIB (forwarding information base);
and
update the first and second LPM tables with routes stored in the FIB, including:
inserting routes stored in the FIB into a single trie data structure;
identifying a plurality of route groups from among the routes stored in the trie data structure, each route group comprising a corresponding plurality of routes, each route group associated with a pivot prefix determined based on prefixes of the plurality of routes;
and
updating the first and second LPM tables with each of the identified route groups, including for each route group:
storing the pivot prefix of the route group into a same entry in a first TCAM of the first LPM table and a second TCAM of the second LPM table;
and
distributing the plurality of routes in the route group between the first and second LPM tables based on lengths of the prefixes of the routes, including storing a first subset of the routes in a first data store of the first LPM table and storing a second subset of the routes in a second data store of the second LPM table.

7 more elements

Dependencies are inferred from the claim text.