# US 12,764,068 B2 · Updating multiple LPM (longest prefix match) tables > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,764,068 B2 - Document ID: US12764068B2 - Status: Granted - Kind: B2 - Application number: 18/985,986 - Filed: 2024-12-18 - Published: 2026-06-18 - Granted: 2026-10-13 - Earliest claimed: 2024-12-18 - Assignees: Arista Networks, Inc. - Applicants: Arista Networks, Inc. - Inventors: Ganesan Venkataraman; Chen Jia Jang; Bhavin Rameshbhai Patel - Web page: https://patentgrep.com/patent/US12764068B2 ## CPC - H04L 45/748: using longest matching prefix - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the route groups are identified based on lengths of the prefixes of the routes in the single trie data structure and storage constraints of the first and second data stores. ### Claim 3 (depends on 1) The method of claim 1, wherein the pivot prefix of a route group is a longest prefix that is common among the prefixes of the plurality of routes in the given route group. ### Claim 4 (depends on 1) The method of claim 1, wherein the first and second data stores comprise rows of buckets, the method further comprising storing the first subset of routes in a plurality of buckets in a row of buckets of the first data store; and storing the second subset of routes in a plurality of buckets in a row of buckets of the second data store. ### Claim 5 (depends on 4) The method of claim 4, wherein associating the entry in the first TCAM with the first subset of routes stored in the first LPM table includes storing an identifier of the row of buckets of the first data store into a pivot entry in an ADS (associated data structure) in the first LPM table, wherein associating the entry in the second TCAM with the second subset of routes stored in the second LPM table includes storing an identifier of the row of buckets of the second data store into a pivot entry in an ADS in the second LPM table. ### Claim 6 (depends on 5) The method of claim 5, wherein the pivot entry in the ADS in the first LPM table is associated with the entry in the first TCAM in the first LPM, wherein the pivot entry in the ADS in the second LPM table is associated with the entry in the second TCAM in the second LPM. ### Claim 7 A network device comprising: one or more computer processors; and a computer-readable storage device comprising instructions for controlling the one or more computer processors 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. ### Claim 8 (depends on 7) The network device of claim 7, wherein the first subset of the routes in the route group comprises routes having prefixes that are longer than prefixes of the second subset of routes. ### Claim 9 (depends on 7) The network device of claim 7, wherein the route groups are identified based on lengths of the prefixes of the routes in the single trie data structure and storage constraints of the first and second data stores. ### Claim 10 (depends on 7) The network device of claim 7, wherein the pivot prefix of a route group is a longest prefix that is common among the prefixes of the plurality of routes in the given route group. ### Claim 11 (depends on 7) The network device of claim 7, wherein the first and second data stores comprise rows of buckets, wherein the computer-readable storage device further comprises instructions for controlling the one or more computer processors to: store the first subset of routes in a plurality of buckets in a row of buckets of the first data store; and store the second subset of routes in a plurality of buckets in a row of buckets of the second data store. ### Claim 12 (depends on 11) The network device of claim 11, wherein the computer-readable storage device further comprises instructions for controlling the one or more computer processors to: store an identifier of the row of buckets of the first data store into a pivot entry in an ADS (associated data structure) in the first LPM table; and store an identifier of the row of buckets of the second data store into a pivot entry in an ADS in the second LPM table. ### Claim 13 (depends on 12) The network device of claim 12, wherein the pivot entry in the ADS in the first LPM table is associated with the entry in the first TCAM in the first LPM, wherein the pivot entry in the ADS in the second LPM table is associated with the entry in the second TCAM in the second LPM. ### Claim 14 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. ### Claim 15 (depends on 14) The non-transitory computer-readable storage device of claim 14, wherein the first subset of the routes in the route group comprises routes having prefixes that are longer than prefixes of the second subset of routes. ### Claim 16 (depends on 14) The non-transitory computer-readable storage device of claim 14, wherein the route groups are identified based on lengths of the prefixes of the routes in the single trie data structure and storage constraints of the first and second data stores. ### Claim 17 (depends on 14) The non-transitory computer-readable storage device of claim 14, wherein the pivot prefix of a route group is a longest prefix that is common among the prefixes of the plurality of routes in the given route group. ### Claim 18 (depends on 14) The non-transitory computer-readable storage device of claim 14, wherein the first and second data stores comprise rows of buckets, wherein the computer executable instructions, which when executed, further cause the network device to: store the first subset of routes in a plurality of buckets in a row of buckets of the first data store; and store the second subset of routes in a plurality of buckets in a row of buckets of the second data store. ### Claim 19 (depends on 18) The non-transitory computer-readable storage device of claim 18, wherein the computer executable instructions, which when executed, further cause the network device to: store an identifier of the row of buckets of the first data store into a pivot entry in an ADS (associated data structure) in the first LPM table; and store an identifier of the row of buckets of the second data store into a pivot entry in an ADS in the second LPM table. ### Claim 20 (depends on 19) The non-transitory computer-readable storage device of claim 19, wherein the pivot entry in the ADS in the first LPM table is associated with the entry in the first TCAM in the first LPM, wherein the pivot entry in the ADS in the second LPM table is associated with the entry in the second TCAM in the second LPM.