Method and apparatus for determining a longest matching prefix from a dictionary of prefixes

• US 5,983,223 A
• Filed: 05/06/1997
• Issued: 11/09/1999
• Est. Priority Date: 05/06/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Perlman, Radia J.
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US08/852,230
• Time in Patent Office: 917 Days
• Field of Search: 709/238, 709/243, 712/898, 707/3, 707/6, 707/10, 707/100, 707/101, 370/396, 370/397, 370/407, 370/428
• US Class Current: 1/1
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• 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/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An arrangement efficiently renders forwarding decisions for a packet using a forwarding database dictionary of an intermediate node configured to optimize space consumed by addresses stored therein as well as to reduce time required to search those addresses. The arrangement generally includes a lookup mechanism comprising a search engine coupled to a set of registers and to the dictionary. The register set, in turn, comprises a number of registers operating in parallel to compare values specified by a number of bits with a predetermined starting point of an input string. The specified values are preferably representative of address prefixes stored in the dictionary and the input string is a destination address of the packet.

Claims

1. Method for determining a longest matching prefix from a dictionary of prefixes compared with an input string, the method comprising the steps of:

providing a set of registers for executing a search engine configured to search the prefixes of the dictionary, each register of the set containing a value specified by a number of bits;

comparing, in parallel, the values of the registers with a corresponding number of bits of the input string beginning with a first bit of the input string;

specifying a number of matching bits as an output of each register whose value equals the corresponding number of bits of the input string; and

selecting the register having a largest number of matching bits as the longest match.

2. The method of claim 1 wherein the step of specifying comprises one of the steps of:

providing a false indication as the output of each register if there is not a match between the value and the input string; and

indicating the number of bits matched in the register as the output of each register if there is match between the value and the input string.

3. The method of claim 2 wherein the step of selecting comprises the step of comparing the outputs of all registers of the set.

4. A computer readable medium containing executable program instructions for creating a search engine configured to determine a longest matching prefix from a dictionary of prefixes compared with an input string, the executable program instructions comprising program instructions for:

allocating a fixed number of registers within a register set as hash buckets with predetermined designations;

assigning each prefix to one of the hash buckets having a matching designation;

expanding the predetermined designation of each hash bucket if there is a common substring of values among the prefixes assigned to each hash bucket;

determining if there are any remaining registers of the register set;

determining if there are any registers with more than one assigned prefix; and

if not, providing an optimized search engine.

5. The medium of claim 4 further comprising program instructions for, if there are remaining registers:

selecting the register with the most assigned prefixes; and

apportioning those prefixes among the remaining registers on the basis of the common substring terminated by the predetermined designations.

6. The medium of claim 5 further comprising program instructions for:

recycling any hash buckets having no assigned prefixes.

7. The medium of claim 6 further comprising program instructions for, if there are registers with more than one assigned prefix:

writing values to be loaded in the registers during execution of the search engine to a predetermined data structure;

allocating storage locations for each hash bucket with more than one entry; and

setting a pointer for each hash bucket to reference the storage locations.

8. The medium of claim 7 further comprising program instructions for:

returning to the step of allocating; and

continuing with the program instruction steps until each register has only one assigned prefix, thereby providing the optimized search engine.

9. A computer readable medium containing executable program instructions for executing a search engine configured to determine a longest matching prefix from a dictionary of prefixes compared with an input string, the executable program instructions comprising program instructions for:

initializing k=1, wherein k is a variable that specifies a starting bit position of the input string;

initializing a longest match prefix variable to a false value;

loading each register of a register set with a common substring of prefix values, a number of matching bits and a pointer referencing a data structure containing values for loading the registers;

comparing contents of each register with the input string beginning with a k bit of the input string;

providing the number of matching bits as an output of each register;

comparing the outputs of all matching registers;

determining whether there is a match between the contents of any register and the input string; and

if not, specifying a longest match equal to the contents of the longest match prefix variable.

10. The medium of claim 9 further comprising program instructions for, if there is a match between the contents of the register and the input string:

selecting the register with the largest number of matching bits.

11. The medium of claim 10 further comprising program instructions for:

specifying the value of the largest number of matching bits equal to the contents of the longest match prefix variable;

determining whether the selected register has a value ending in *; and

if so, designating that value as the longest match.

12. The medium of claim 11 further comprising program instructions for, if the selected register does not have a value ending in *:

accessing the data structure referenced by the pointer of the selected register;

loading the registers of the register set with the values contained in the data structure; and

updating k=k+the largest number of matching bits.

13. The medium of claim 12 further comprising program instructions for:

comparing the contents of each register with the input string beginning with a k bit of the input string.

14. The medium of claim 13 further comprising program instructions for:

providing the number of matching bits as an output of each register;

comparing the outputs of all matching registers;

determining whether there is a match between the contents of any register and the input string; and

if not, designating the contents of the longest match prefix variable as the longest match.

15. Apparatus for determining a longest matching prefix from a dictionary of prefixes compared with an input string, the apparatus comprising:

a set of registers for searching the prefixes of the dictionary, each register of the set containing a value specified by a number of bits;

a search engine for comparing, in parallel, the values of the registers with a corresponding number of bits of the input string beginning with a first bit of the input string;

means for specifying a number of matching bits as an output of each register whose value equals the corresponding number of bits of the input string; and

means for selecting the register having a largest number of matching bits as the longest match.

16. The apparatus of claim 15 wherein the means for specifying comprises:

means for providing a false indication as the output of each register if there is not a match between the value and the input string; and

means for indicating the number of bits matched in the register as the output of each register if there is match between the value and the input string.

17. The apparatus of claim 16 wherein the means for selecting comprises means for comparing the outputs of all registers of the set.