Hybrid search memory for network processor and computer systems

• US 20030110180A1
• Filed: 12/11/2001
• Published: 06/12/2003
• Est. Priority Date: 12/11/2001
• Status: Active Grant

• Current Assignee: Daedalus Blue LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Calvignac, Jean Louis, Verplanken, Fabrice Jean
• Granted Patent: US 8,195,705 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

A data structure, system and method of searching the data structure are disclosed. The system includes a data structure having a Direct Table (DT), Patricia-Trees, Pointers and high speed storage systems such as Contents Address Memory (CAM). The DT has a plurality of entries with each one coupled to a Patricia Tree having multiple nodes coupled to leaves. The number of Nodes, termed a threshold, that can be traversed to obtain information in the leaves is limited to a predetermined value. Once the threshold is reached a pointer indicates the address of the CAM and the address of the leaves is stored in the CAM. By using the disclosed structure and method the latency associated with tree search is significantly reduced.

Claims

1. A search method comprising the acts of:

a) using N bits, N being an integer, from a packet as an index into a data structure including a Direct Table with at least one entry and a tree structure operatively coupled to said one entry;

b) setting a threshold based upon a first predetermined characteristic of the tree structure;

c) using select bits from the packet to traverse said tree structure until the threshold is met;

d) storing in a Contents Address Memory (CAM) at least one entry based upon a predetermined characteristic of the packet and a second predetermined characteristic of said tree structure; and

e) using the at least one entry to access a memory location whereat action to be taken relative to the packet is stored.

2. The method of claim 1 wherein N includes the first sixteen bits of a Destination MAC Address.

3. The method of claim 2 wherein the tree structure includes a plurality of nodes and leaves operatively coupled to selected nodes.

4. The method of claim 3 further including Pattern Search Control Blocks (PSCBS) carrying search information positioned at selected nodes.

5. The method of claim 1 wherein the first predetermined characteristic includes nodes and the threshold is set to a count of the nodes.

6. The method of claim 2 wherein the selected bits include the remaining thirty two bits of the Destination MAC Address.

7. The method of claim 2 wherein the second predetermined characteristic includes leaves.

8. A method for correlating a search key with a database comprising the acts of:

a) using N bits, N≧

1, from the search key as an index into the database including entries having a Direct Table with at least one entry and a tree structure operatively coupled to said one entry;

b) setting a threshold based upon a first predetermined characteristic of the tree structure;

c) using M bits (M>

1) from the search key to access said tree structure until the threshold is met; and

d) reading from a CAM information that indicates action to be taken relative to the search key.

9. The method of claim 8 wherein the search key includes a portion of a data packet.

10. The method of claim 9 wherein the information includes the address of a leaf in which the action is stored.

11. The method of claim 8 wherein the reading step further includes the step of using the N bits as index into the CAM.

12. An apparatus comprising:

an embedded processor complex including a plurality of protocol processors;

a control point processor operatively coupled to the processor complex;

a plurality of hardware accelerator co-processors accessible to each protocol processor and providing high speed pattern searching, data manipulation and frame parsing;

at least one memory device, operatively coupled to the processor complex, that stores data structures including a Direct Table, nodes and leaves operatively chained together; and

a Memory location operatively coupled to the processor complex and storing a value representative of the maximum number of nodes to be accessed during a tree search routine.

13. The apparatus of claim 12 further including a Contents Address Memory (CAM) operatively coupled to the processor complex and storing a pointer identifying a location whereat a leaf is stored.

14. The apparatus of claim 13 wherein the leaf contains information on actions to be taken relative to a packet.

15. The apparatus of claim 14 wherein the CAM further includes an indicia paired with the pointer, said indicia being selected from a portion of the packet.

16. The apparatus of claim 15 wherein the indicia includes a portion of a Destination MAC Address in the packet.

17. The apparatus of claim 15 further including a circuit that deletes pointers from the CAM based upon leaf adjustments in the tree structure and/or NONE use of the information within a predetermined time interval.

18. The apparatus of claim 17 wherein the leaf adjustments include deletion.

19. The apparatus of claim 12 wherein the Control Point Processor is programmed to generate and forward frames containing information that adjusts the data structure.

20. The apparatus of claim 19 wherein the adjustment includes leaf deletion and/or insertion.

21. A data structure comprising:

a Direct Table having at least two entries;

a tree structure operatively coupled to the at least two entries and having a plurality of nodes and leaves operatively chained together; and

a storage storing a threshold value indicating the maximum number of nodes to be accessed during a walk of said tree structure.

22. The data structure of claim 21 further including Contents Address Memory, CAM, in which leaf information is stored if the leaf is connected to a node above the threshold value.

23. The data structure of claim 22 further including a co-processor responsive to at least a command to use part of the DA of a packet to index into the DT and the remaining part of said DA to search the associated tree, said co-processor selecting, information stored in a leaf if the leaf is attached to a node below the threshold value or selecting information stored in the CAM if the leaf is attached to a node above the threshold value.

24. A system comprising:

a processor to provide a key extracted from a data packet;

a tree walk logic responsive to use the key to walk a tree structure until a threshold is reached;

a CAM controller to use the key to search a CAM; and

a controller that uses the first available result from the tree walk logic or the CAM controller to determine an action to be taken relative to the data packet.

25. A search method comprising the acts of:

(a) providing a key extracted from a data packet;

(b) using said key by a tree walk logic to search a tree structure until a threshold is reached;

(c) using said key by a CAM controller to search a CAM; and

using the first result from acts (b) or (c) to determine an action to be taken relative to the data packet.