主权项 |
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:
obtaining, at a search engine of the network device, a network address associated with a packet, wherein the search engine includes a plurality of Bloom filters, wherein each of at least some of the Bloom filters represents prefixes of a certain length in the routing table; applying, by the search engine of the network device, 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 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, 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, adapting the routing table to reduce a number of memory accesses to be performed for subsequent packets associated with the network address. |