Methods and apparatus related to packet classification associated with a multi-stage switch

• US 7,961,734 B2
• Filed: 09/30/2008
• Issued: 06/14/2011
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Panwar, Ramesh, Goel, Deepak, Jagannadhan, Srinivasan, Frailong, Jean-Marc
• Primary Examiner(s): Ho; Duc C
• Application Number:
  US12/242,168
• Publication Number:
  US 20100083345A1
• Time in Patent Office: 987 Days
• Field of Search: None
• US Class Current: 370/392
• 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/12 Shortest path evaluation
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/503 Policing

Abstract

In one embodiment, an apparatus can include a policy vector module configured to retrieve a compressed policy vector based on a portion of a data packet received at a multi-stage switch. The apparatus can also include a decompression module configured to receive the compressed policy vector and configured to define a decompressed policy vector based on the compressed policy vector. The decompressed policy vector can define a combination of bit values associated with a policy.

Claims

1. An apparatus comprising:

a policy vector module implemented in at least one of a memory or a processing device, configured to retrieve a compressed policy vector based on a portion of a data packet received at a multi-stage switch; and

a decompression module configured to receive the compressed policy vector and configured to define a first decompressed policy vector based on the compressed policy vector, the first decompressed policy vector defining a combination of bit values associated with a policy; and

a combination module configured to receive the first decompressed policy vector and configured to produce a combined policy vector based on a combination of the first decompressed policy vector and a second decompressed policy vector, the combined policy vector configured to trigger an element at the multi-stage switch to process the data packet.

2. The apparatus, of claim 1, further comprising:

a key vector module configured to define a key vector including a bit sequence corresponding to the portion of the data packet, the policy vector module configured to receive the key vector from the key vector module and configured to retrieve the compressed policy vector based on the key vector.

3. The apparatus of claim 1, wherein the policy vector module includes at least one of a hash-based search function module or a node-based search function module.

4. The apparatus of claim 1, wherein the portion of the data packet is a first portion of the data packet,

The combination module configured to produce the combined policy vector based on a boolean combination of the first decompressed policy vector and the second decompressed policy vector, the second decompressed policy vector being defined based on a second portion of the data packet different than the first portion of the data packet.

5. The apparatus of claim 1, wherein the policy vector module is configured to define an index value based on a key vector,

the apparatus further comprising:

a policy vector database including a plurality of compressed policy vectors, the compressed policy vector being retrieved from the policy vector database based on the index value.

6. The apparatus of claim 1, further comprising:

a packet processing module configured to receive the first decompressed policy vector and configured to trigger an element at the multi-stage switch to process the data packet based on a combination of bit values defined by the first decompressed policy vector.

7. The apparatus of claim 1, further comprising:

a packet processing module configured to execute an instruction associated with the data packet based on the combined policy vector defining a sequence of bit values, the combined policy vector being defined based on the combination of the first decompressed policy vector and the second decompressed policy vector.

8. The apparatus of claim 1, further comprising:

a switch fabric associated with the multi-stage switch; and

a packet processing module configured to trigger routing through the switch fabric based on a sequence of bit values defined by the first decompressed policy vector.

9. An apparatus, comprising:

a memory configured to store a policy vector database including a plurality of compressed policy vectors;

a policy vector module configured to produce an index value based on a portion of a data packet received at a multi-stage switch, the policy vector module configured to retrieve a compressed policy vector from the plurality of compressed policy vectors based on the index value, the memory and the policy vector module being integrated on a common chip;

a decompression module configured to receive the compressed policy vector and configured to produce a decompressed policy vector based on the compressed policy vector; and

a packet processing module configured to receive the decompressed policy vector and configured to trigger based on a set of bit values defined by the decompressed policy vector an element at the multi-stage switch to process the data packet.

10. The apparatus of claim 9, wherein:

the set of bit values are configured to trigger execution of an instruction associated with a policy.

11. The apparatus of claim 9, further comprising:

a key vector module configured to define a key vector including a bit sequence corresponding to the portion of the data packet, the policy vector module configured to receive the key vector from the key vector module and configured to produce the index value based on the key vector.

12. The apparatus of claim 9, wherein the policy vector module is configured to produce the index value based on at least one of a hash-based search function module or a node-based search function module.

13. The apparatus of claim 9, further comprising:

an exception module configured to associate the portion of the data packet with an exception vector based on an exception condition being satisfied, the exception module configured to modify the decompressed policy vector based on the exception vector.

14. A method, comprising:

defining a key vector based on a portion of a data packet received at a multi-stage switch;

retrieving a first compressed policy vector based on the key vector and a hash-based search function module;

defining a decompressed policy vector having a plurality of policy bit values based on the first compressed policy vector, a policy bit value from the plurality of policy bit values being configured to trigger an element at the multi-stage switch to process the data packet when the policy bit value is set; and

retrieving a second compressed policy vector based on a node-based search function module.

15. The method of claim 14, wherein the data packet is included in a flow of data packets, the element at the multi-stage switch is configured to process the flow of data packets.

16. The method of claim 14, wherein the decompressed policy vector is a first decompressed policy vector, the method further comprising:

defining a combined policy vector based on a logical combination of the first decompressed policy vector and a second decompressed policy vector.

17. The method of claim 14, wherein each of the policy bit values is associated with at least one term included in a policy associated with the multi-stage switch.

18. The method of claim 14, wherein the data packet is defined based on Internet Protocol version 6.

19. The method of claim 14, wherein the key vector is a first key vector, the portion of the data packet is a first portion of the data packet,

the method further comprising:

defining a second key vector based on a second portion of the data packet, the second portion of the data packet being mutually exclusive from the first portion of the data packet,

the retrieving the second compressed policy vector being based on the second key vector.

20. The method of claim 14, wherein the key vector is a first key vector, the portion of the data packet is a first portion of the data packet,

the method further comprising:

defining a second key vector based on a second portion of the data packet, the second portion of the data packet overlapping with the first portion of the data packet,

the retrieving the second compressed policy vector being based on the second key vector.