Method and apparatus for multiple field matching in network device

• US 6,778,530 B1
• Filed: 11/08/1999
• Issued: 08/17/2004
• Est. Priority Date: 11/08/1999
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Greene, Spencer
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US09/436,439
• Time in Patent Office: 1,744 Days
• Field of Search: 370/389, 370/392, 370/401, 370/411, 370/412, 370/428, 370/429, 709/245
• US Class Current: 370/389
• 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/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A system for providing multiple field matching capabilities for network data packets is disclosed. According to one embodiment (700) the system includes a number of prefix engines (704-0, 704-1, 712-0 and 712-1) coupled together in a pipelined fashion. First level prefix engines (704-0 and 704-1) perform longest prefix matching operations on address values (Dest-IP and Src-IP) and provide address equivalence class values (daclass and saclass). The address class equivalence values (daclass and saclass) are combined with port identification values (Dest-Port and Src-Port) and applied to second level prefix engines (712-0 and 712-1) which provide tuple equivalence class values (dtclass and stclass). The tuple equivalence class values (dtclass and stclass) are combined and applied to an output mapping circuit (718) which provides a flow specification value corresponding to each applied set of address (Dest-IP and Src-IP) and port (Dest-Port and Src-Port) values.

Claims

1. A system that provides output values when an input search key value matches a multiple field rule, the system comprising:

a first prefix engine that receives at least a first search key field, the first prefix engine translating values of the first search key field into first field equivalence class numbers by prefix matching, a first equivalence class number representing a stored subset S of a range of the first search key field such that, regardless of values of search keys applied for other fields, any member of the subset S may be substituted for any other member of the subset S, without changing a result returned by a search;

a first combining circuit that combines the first field equivalence class numbers with third field values to form first combination values; and

a first cross-product prefix engine that receives the first combination values and translates the first combination values into first tuple equivalence class numbers by prefix matching, a tuple equivalence class number representing a previously computed and stored subset T of the cross-product of the ranges of at least two search key fields such that, regardless of the values of search keys applied for other fields, any member of the subset T may be substituted for any other member of the subset T, without changing a result returned by the search.

2. The system of claim 1, further including:

a second prefix engine that receives at least a second field from the search key value, the second prefix engine translating values of the second field into second field equivalence class numbers.

3. The system of claim 2, further including:

a mapping circuit that provides output values in response to combinations of the first field equivalence numbers and the second field equivalence numbers.

4. The system of claim 2, further including:

a second combining circuit that combines the second field equivalence class numbers with fourth field values to form second combination values; and

a second cross-product prefix engine that receives the second combination values and translates the second combination values into second tuple equivalence class numbers by prefix matching.

5. The system of claim 4, further including:

a mapping circuit that provides output values in response to the first tuple equivalence class numbers and the second tuple equivalence class numbers.

6. A system for generating output values in response to multiple field match criteria, the system comprising:

a first single-field prefix engine that receives first data field values and provides first class values, each first class value corresponding to a predetermined subset of possible first data field values;

a first combining circuit that combines the first class values with second data field values and provides first combination values;

a first cross-product prefix engine that provides second class values in response to the first combination values, each of the second class values corresponding to a predetermined subset of possible first combination values, and

an output circuit that receives the second class values and provides corresponding output values that indicate a multiple field match with a key value having at least a first data field and a second data field.

7. The system of claim 6, wherein:

the first single-field prefix engine provides the first class values according to longest prefix matching.

8. The system of claim 6, wherein:

the first cross-product prefix engine provides the second class values according to longest prefix matching.

9. The system of claim 6, wherein:

the output circuit includes a random access memory.

10. The system of claim 6, wherein:

the output circuit includes an output prefix engine that generates output values in response to a predetermined subset of possible second class values.

11. The system of claim 6, further including:

the first single-field prefix engine provides a first class value a first processing delay period after receiving a first data field value; and

a first delay circuit disposed between a second data field bus and the first combining circuit, the first delay circuit delaying the second data field values from the second data field bus by approximately the first processing delay period.

12. A system that provides multiple field matching of input key values, comprising:

a plurality of data field inputs;

a prefix engine coupled to at least one of the data field inputs, the prefix engine compressing ranges of field values of the at least one of the data field inputs into equivalence class values according to prefix matching operations, the prefix engine being a first single-field prefix engine coupled to a first data field input that provides first equivalence class values;

a first combining circuit that combines the first equivalence class values with third field values and provides first field combination values; and

a first cross-product prefix engine coupled to the first combining circuit, the first cross-product prefix engine compressing the first field combination values into first tuple equivalence class values according to prefix matching operations, the first tuple equivalence class values representing a previously computed and stored subset T of the cross-product of the ranges of at least two input key values such that, regardless of input key values applied for other fields, any member of the subset T may be substituted for any other member of the subset T, without changing a result returned by a search.

13. The system of claim 12 further comprising:

a mapping circuit that stores output values accessed in response to particular equivalence class values.

14. The system of claim 13, wherein:

the prefix engine is coupled to the plurality of data field inputs, the prefix engine compressing ranges of multiple field values into corresponding equivalence class values according to prefix matching operations.

15. The system of claim 13, further comprising:

a second single-field prefix engine coupled to a second data field input that provides second equivalence class values.

16. The system of claim 15, further including:

a second combining circuit that combines the second equivalence class values with fourth field values and provides second field combination values;

a second cross-product prefix engine coupled to the second combining circuit, the second cross-product prefix engine compressing the second field combination values into second tuple equivalence class values according to prefix matching operations; and

the mapping circuit accesses particular output values in response to the first and the second tuple equivalence class values.

17. The system of claim 12, wherein:

at least one of the data field inputs receives a network address value.