US Patent No. 10,230,639

ENHANCED PREFIX MATCHING


Patent No. 10,230,639
Issue Date March 12, 2019
Title Enhanced Prefix Matching
Inventorship Vasant Shankargouda Patil, San Jose, CA (US)
Puneet Agarwal, Cupertino, CA (US)
Gururaj Ananthateerta, Santa Clara, CA (US)
Rupa Budhia, San Jose, CA (US)
Assignee Innovium, Inc., San Jose, CA (US)

Claim of US Patent No. 10,230,639

1. A network device comprising:one or more memories storing a prefix table represented as a prefix index coupled to a plurality of prefix arrays;
forwarding logic configured to search for a longest prefix match in the prefix table for a particular input key by:
searching for a first longest prefix match for the particular input key in the prefix index;
reading address information that corresponds to the first longest prefix match;
reading a particular prefix array from a particular location indicated by the address information;
examining each prefix entry in the particular prefix array until determining that a particular prefix entry corresponds to a second longest prefix match in the particular prefix array, the second longest prefix match being the longest prefix match for the particular input key in the prefix table;
prefix table management logic configured to:
generate a prefix tree representing the prefix table, each prefix entry in the prefix table having a corresponding node in the prefix tree;
divide the prefix tree into non-overlapping subtrees;
for each subtree of the subtrees:
store, within a prefix array for the subtree, a set of all prefix entries in the prefix table that correspond to nodes in the subtree;
add, to the prefix index, an entry comprising: a location at which the prefix array is stored and a prefix corresponding to a root node of the subtree, each subtree having a single root node.