Hash Table-Based Mask Length Computation for Longest Prefix Match Caching
AssigneeMellanox Technologies Tlv Ltd.
InventorsGil Levy, Aviv Kfir, Salvatore Pontarelli, Pedro Reviriego
Life of this patent
Estimating the term…
Abstract
A data packet is received in a network element. The network element has a cache memory in which cache entries represent a portion of addresses stored in a main memory, The destination address and the cache entries each comprise a binary number. A hash function is applied to the masked destination address to access a hash table. When the number of most significant bits corresponding to the value in the hash table in one of the cache entries and in the destination address are identical, routing information for the packet is retrieved from the cache entry.
Claims22
A method of communication, comprising the steps of:
- assigning a mask length;
- receiving via a data network a packet having a destination address;
- providing a cache memory having cache entries that correspond to addresses of a main memory, the destination address and the cache entries each comprising a binary number having most significant bits;
- masking the destination address with the mask length;
- applying a hash function to the masked destination address to access a hash table;
- obtaining a value from the hash table;
- determining that a number of most significant bits in one of the cache entries and the number of most significant bits of the destination address are identical, wherein the number of most significant bits is equal to the value obtained from the hash table;
- and
- retrieving routing information for the packet from the one cache entry.
An apparatus, comprising:
- a network element operative for receiving via a data network a packet having a destination address;
- a processor in the network element;
- a main memory storing a database of packet forwarding information;
- a hash table stored in a memory, the database and the hash table accessible to the processor;
- a cache memory accessible to the processor, the cache memory having cache entries therein that represent a portion of the packet forwarding information of the main memory, the destination address and the cache entries each comprising a binary number having most significant bits, wherein the processor is operative to perform the steps of;
- assigning a mask length;
- masking the destination address with the mask length;
- applying a hash function to the masked destination address to access the hash table;
- obtaining a value from the hash table;
- determining that a number of most significant bits in one of the cache entries and the number of most significant bits of the destination address are identical, wherein the number of most significant bits is equal to the value obtained from the hash table;
- and
- retrieving routing information for the packet from the one cache entry.
Dependencies are inferred from the claim text.