Network search engine (NSE) and method for performing interval location using prefix matching

• US 7,624,226 B1
• Filed: 12/20/2006
• Issued: 11/24/2009
• Est. Priority Date: 12/20/2005
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Gupta, Pankaj, Venkatachary, Srinivasan
• Primary Examiner(s): Thai; Tuan V
• Assistant Examiner(s): Doan; Duc T
• Application Number:
  US11/614,075
• Time in Patent Office: 1,070 Days
• Field of Search: None
• US Class Current: 711/108
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/645 Splitting route computation layer and forwarding layer, e.g. routing according to path computational element [PCE] or based on OpenFlow functionality
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A communication network, networking device and method is provided herein for locating (i.e., searching for) an interval of numbers i within a set of numbers N given a point P. The search algorithm provided herein provides fast search speed (e.g., requires only one memory access) with minimum storage requirements (e.g., consumes up to, but not exceeding, N entries within a memory device).

Claims

1. A method of determining which of a plurality of numeric intervals encompasses a search value, the method comprising:

comparing the search value to a plurality of interval definition values stored within a content addressable memory (CAM) to generate a match signal that corresponds to one of the interval definition values, each of the interval definition values defining a respective numeric interval;

retrieving a multi-field values from an associated memory that is external to the CAM in response to the match signal, the multi-field values including upper and lower boundary fields that indicate upper and lower boundaries, and values that indicate respective numeric intervals associated with the upper and lower boundaries, wherein the multi-field values are prefix left (prefixL), prefix right (prefixR), pointer less than prefix left (pointer_ltprefixL), pointer_middle, and pointer greater than or equal to prefix right (pointer_geprefixR).

2. The method of claim 1 further comprising:

comparing the search value and at least one of the upper and lower boundaries indicated by the upper and lower boundary fields to generate a comparison result.

3. The method of claim 2 wherein comparing the search value and at least one of the upper and lower boundaries comprises comparing the search value with both the upper boundary and the lower boundary.

4. The method of claim 3 wherein comparing the search value with both the upper boundary and the lower boundary comprises simultaneously comparing the search value with the upper and lower boundaries.

5. The method of claim 2 wherein comparing the search value and at least one of the upper and lower boundaries comprises comparing the search value with at least one of the upper boundary and the lower boundary within a programmed processor.

6. The method of claim 2 wherein selecting one of the values that indicate numeric values based on the comparison result comprises selecting a value that indicates a numeric interval for which the lower boundary defines an upper bound if the search value is less than the lower boundary.

7. The method of claim 2 wherein selecting one of the values that indicate numeric values based on the comparison result comprises selecting a value that indicates a numeric interval for which the upper boundary defines a lower bound if the search value is greater than the upper boundary.

8. The method of claim 2 wherein selecting one of the values that indicate numeric values based on the comparison result comprises selecting a value that indicates a numeric interval that falls between the upper and lower boundaries if the search value is greater than the lower boundary and less than the upper boundary.

9. A method for locating an interval of numbers i within a set of numbers N given a point P, the method comprising:

searching a first database of entries, each entry comprising W-bits, to find an entry having the most number of bits in common with the point P wherein the first database of entries is stored within a network search engine (NSE);

accessing a second database of entries to obtain information relating to the entry found to have the most number of bits in common with the point P wherein the second database of entries is stored within a memory device associated with, but located external to, the NSE; and

comparing the point P with some of the information obtained from the second database to locate the interval of numbers i containing the point P, wherein the first database of entries comprises a plurality of branch nodes obtained by representing the set of numbers N in a binary tree configuration, wherein the second database of entries comprises a table containing a set of values for each of the plurality of branch nodes, and wherein the set of values are prefix left (prefixL), prefix right (prefixR), pointer less than prefix left (pointer_ltprefixL), pointer middle, and pointer greater than or equal to prefix right (pointer_geprefixR).