Back to results
US 10,764,182 B2Granted
Combining prefix lengths into a hash table
AssigneeHewlett Packard Enterprise Development LP
InventorJohn A. Wickeraad
Life of this patent
Estimating the term…
Abstract
Examples herein disclose a smaller prefix length and a greater prefix length which are identified from a routing table of various prefix lengths. The smaller prefix length is converted into the greater prefix length. The converted prefix length and the greater prefix length are combined into a hash table.
Claims12
A non-transitory machine-readable storage medium comprising instructions that when executed by a processing resource cause a networking device to:
- obtain a routing table of various prefix lengths;
- divide the routing table into a plurality of prefix-length-specific hash tables, wherein dividing the routing table comprises:
- identifying a set of greater prefix lengths from the routing table;
- for a respective greater prefix length, identifying, from the routing table, at least one smaller prefix length that is smaller than the respective greater prefix length;
- converting the smaller prefix length into the greater prefix length;
- constructing, for each greater prefix length in the set of greater prefix lengths, a prefix-length-specific hash table, wherein constructing a corresponding prefix-length-specific hash table for the respective greater prefix length comprises combining address entries corresponding to the converted smaller prefix length and address entries corresponding to the respective greater prefix length into a single hash table;
- examining a constructed prefix-length-specific hash table to identify duplicated address entries in the constructed prefix-length-specific hash table;
- and
- removing a duplicated address entry corresponding to a converted smaller prefix length from the constructed prefix-length-specific hash table;
- and
- perform address lookup of an incoming packet based at least on the plurality of prefix-length-specific hash tables.
8 more elements
A method, executable by a networking device, the method comprising:
- obtaining a routing table of various prefix lengths;
- dividing the routing table into a plurality of prefix-length-specific hash tables, wherein dividing the routing table comprises:
- identifying a set of greater prefix lengths from the routing table;
- for a respective greater prefix length, identifying, from the routing table, at least one smaller prefix length that is smaller than the respective greater prefix length;
- converting the smaller prefix length into the respective greater prefix length;
- constructing, for each greater prefix length in the set of greater prefix lengths, a prefix-length-specific hash table, wherein constructing a corresponding prefix-length-specific hash table for the respective greater prefix length comprises combining address entries corresponding to the converted smaller prefix length and address entries corresponding to the respective greater prefix length into a single hash table;
- examining a constructed prefix-length-specific hash table to identify duplicated address entries in the constructed prefix-length-specific hash table;
- and
- removing a duplicated address entry corresponding to a converted smaller prefix length from the constructed prefix-length-specific hash table;
- and
- performing address lookup of an incoming packet based at least on the plurality of prefix-length-specific hash tables.
8 more elements
A networking device comprising:
- a routing table of various prefix lengths;
- a networking controller to:
- divide the routing table into a plurality of prefix-length-specific hash tables, wherein dividing the routing table comprises:
- identifying a set of greater prefix lengths from the routing table;
- for a respective greater prefix length, identifying, from the routing table, at least one smaller prefix length that is smaller than the respective greater prefix length;
- converting the smaller prefix length into the respective greater prefix length;
- constructing, for each greater prefix length in the set of greater prefix lengths, a prefix-length-specific hash table, wherein constructing a corresponding prefix-length-specific hash table for the respective greater prefix length comprises combining address entries corresponding to the converted smaller prefix length and address entries corresponding to the respective greater prefix length from the routing table into a single hash table;
- examining a constructed prefix-length-specific hash table to identify duplicated address entries in the constructed prefix-length-specific hash table;
- and
- removing a duplicated address entry corresponding to a converted smaller prefix length from the constructed prefix-length-specific hash table;
- and
- perform address lookup of an incoming packet based at least on the plurality of prefix-length-specific hash tables.
9 more elements
Dependencies are inferred from the claim text.