Efficient longest prefix matching techniques for network devices

Patent metadata

Field	Value
Publication number	US-9819637-B2
Application number	US-201414192579-A
Country	US
Kind code	B2
Filing date	Feb 27, 2014
Priority date	Feb 27, 2013
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

A network address associated with a packet is obtained at a search engine of a network device. The search engine includes a plurality of Bloom filters that represent prefixes of respective lengths in the routing table. Respective Bloom filters are applied to respective prefixes of the network address to determine a set of one or more prefixes for which a match potentially exists in the routing table. A number of accesses to the memory are performed using prefixes in set of prefixes, beginning with a longest prefix and continuing in decreasing order of prefix lengths until a matching entry is found in the routing table, and routing information for the packet is retrieved. If the number of performed memory accesses exceeds a threshold, the routing table is adapted to reduce a number of memory accesses to be performed for subsequent packets associated with the network address.

First claim

What is claimed is:

1. A method for performing longest prefix match lookup operations in a memory storing a routing table used for forwarding packets in a network device, the method comprising:
receiving, at a search engine of the network device, a network address associated with a packet, wherein the network address is provided by a packet processor of the network device, the packet processor configured to perform processing of the packet at least to determine a forwarding decision for the packet, and wherein the search engine includes a plurality of Bloom filters, each of at least some of the Bloom filters representing prefixes of a respective certain length in the routing table;
applying, by the search engine, respective Bloom filters of the plurality of Bloom filters to respective prefixes of the network address to determine a set of one or more prefixes, of the network address, for which a match potentially exists in the routing table;
performing, by the search engine, a number of accesses to the memory using prefixes in the set of prefixes, beginning with a longest prefix in the set of prefixes and continuing in decreasing order of prefix length in the set of prefixes until an entry having a matching prefix is found in the routing table;
retrieving, by the search engine, from the entry in the routing table, routing information for the packet;
determining, by the search engine, that the number of performed memory accesses exceeds a threshold; and
in response to determining that the number of performed memory accesses exceeds the threshold,
generating, by the search engine, a feedback signal indicating that the number of performed memory accesses based on the network address exceeds the threshold,
providing the feedback signal from the search engine to the packet processor configured to perform processing of the packet,
in response to providing the feedback signal to the packet processor, receiving, at the search engine from the packet processor, an instruction to adapt the routing table to the network address, and

in response to receiving the instruction from the packet processor, adapting, by the search engine, the routing table to the network address to reduce a number of memory accesses to be performed for subsequent packets associated with the network address.

2. The method of claim 1 , wherein a first Bloom filter of the plurality of Bloom filters represent prefixes of a first length in the routing table, and wherein the first Bloom filter includes:
a first Bloom filter block that represents a first subset of prefixes of the first length in the routing table; and
a second Bloom filter block that represents a second subset of prefixes of the first length in the routing table;
wherein the first subset of prefixes does not overlap with the second subset of prefixes.

3. The method of claim 2 , wherein applying the first Bloom filter to a prefix includes:
calculating a hash value based on the prefix;
using a first portion of the hash value to select the first Bloom filter block or the second Bloom filter block;
using a second portion of the hash value to select a location in the selected one of the first Bloom filter block and the second Bloom filter block; and
determining whether a match in the routing table potentially exists in the routing table based on the location.

4. The method of claim 1 , wherein adapting the routing table comprises inserting a new entry into the routing table, wherein the new entry includes (i) a prefix of the network address, wherein the prefix is longer than the matching prefix associated with an entry found in the routing table based on the network address and (ii) the routing information retrieved from the entry found in the routing table.

5. The method of claim 1 , wherein adapting the routing table is performed in a data plane of the network device.

6. The method of claim 1 , further comprising:
configuring, at the search engine, a first Bloom filter of the plurality of Bloom filters, the first Bloom filter having at least one Bloom filter block to represent a set of prefixes of a first length in the routing table; and
dynamically adjusting, using the search engine, a size of the first Bloom filter, including:
determining, based on one or more factors associated with the first Bloom filter, that one of (i) the size of the first Bloom filter should be increased or (ii) the size of the first Bloom filter should be decreased; and
in response to determining that the size of the first Bloom filter should be increased, adding one or more additional Bloom filter blocks to the first Bloom filter; and

in response to determining that the size of the first Bloom filter should be decreased, removing one or more Bloom filter blocks from the first Bloom filter.

7. The method of claim 6 , wherein adding one or more additional Bloom filter blocks to the first Bloom filter comprises adding the one or more additional Bloom filter blocks without interrupting operation of the first Bloom filter.

8. The method of claim 6 , wherein determining, based on one or more factors associated with the first Bloom filter, that one of (i) the size of the first Bloom filter should be increased or (ii) the size of the first Bloom filter should be decreased comprises:
determining a false positive probability for the first Bloom filter; and
determining that the size of the first Bloom filter should be increased when the false positive probability exceeds a first threshold; and
determining that the size of the first Bloom filter should be decreased when the false positive probability falls below a second threshold.

9. The method of claim 6 , wherein the first Bloom filter includes a first Bloom filter block and wherein adding one or more additional Bloom filter blocks to the first Bloom filter comprises:
adding a second Bloom filter block to the first Bloom filter; and
configuring the first Bloom filter block to represent a first subset of the set of prefixes in the routing table represented by the first Bloom filter and configuring the second Bloom filter block to represent a second subset of prefixes in the set of prefixes represented by the first Bloom filter.

10. The method of claim 9 , wherein configuring the first Bloom filter block to represent the first subset of the set of prefixes in the routing table represented by the first Bloom filter and configuring the second Bloom filter block to represent the second subset of prefixes in the set of prefixes represented by the first Bloom filter comprises:
copying contents of the first Bloom filter block to the second Bloom filter block;
calculating a respective hash value for each of the prefixes in the set of prefixes, the hash value having a first portion and a second portion; and
for each prefix in the set of prefixes,
using a first portion of the hash value calculated for the prefix to determine whether the prefix belongs to the first subset of the set of prefixes or to the second subset of the set of prefixes; and
if it is determined that the prefix belongs to the first subset, setting a location, in the second Bloom filter block, to a value that indicates that the prefix does not belong to the second subset, wherein the location is indicated by the second portion of the hash value; and
if it is determined that the prefix belongs to the second subset, setting a location, in the first Bloom filter block, to a value that indicates that the prefix does not belong to the first subset, wherein the location is indicated by the second portion of the hash value.

11. The method of claim 10 , further comprises storing, in the routing table, prefixes, of the set of prefixes, in a compressed form, and wherein

Assignees

• Marvell World Trade Ltd

Inventors

• Roitshtein Amir
• Levy Gil
• Arad Carmi

Classifications

• H04L61/103 Primary

  across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP] · CPC title

• H04L45/748 Primary

  using longest matching prefix · CPC title

• H04L45/7453

  using hashing · CPC title