Longest prefix matching (LPM) using a fixed comparison hash table
AssigneeNortel Networks Limited
InventorAndrew Davis
Life of this patent
Estimating the term…
Abstract
Described are an apparatus and method of forwarding Internet Protocol (IP) packets. At least one fixed-length key having a predetermined number of bits is produced in response to an IP address in an IP packet. At least a portion of the fixed-length key is hashed to obtain a hash value. The fixed-length key is compared with a key value stored in each data-item in a hash bucket associated with the hash value to find the data item that has the key value that matches the fixed-sized key and to obtain from that data item routing information that is used to forward the IP packet.
Claims20
A method of forwarding Internet Protocol (IP) packets, comprising:
- producing at least one fixed-length key having a predetermined number of bits in response to an IP address in an IP packet;
- hashing at least a portion of the fixed-length key to obtain a hash value;
- and
- comparing the fixed-length key with a key value stored in each data item in a hash bucket associated with the hash value to find the data item that has the key value that matches the fixed-length key and to obtain from that data item routing information that is used to forward the IP packet.
An apparatus for forwarding IP packets, comprising:
- a key generator producing a fixed-length key having a predetermined number of bits in response to an IP address;
- a hash value generator hashing a portion of the fixed-length key to produce a hash value;
- and
- a comparator comparing the fixed-length key with a key value stored in each data item in a hash bucket associated with the hash value to find the data item that has the key value that matches the fixed-length key and to obtain from that data item routing information that is used to forward the IP packet.
Dependencies are inferred from the claim text.