METHODS AND APPARATUS RELATED TO PACKET CLASSIFICATION ASSOCIATED WITH A MULTI-STAGE SWITCH

• US 20100083345A1
• Filed: 09/30/2008
• Published: 04/01/2010
• 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
• Granted Patent: US 7,961,734 B2
• Time in Patent Office: Days
• US Class Current: 726/1
• 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 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 decompressed policy vector based on the compressed policy vector, the decompressed policy vector defining a combination of bit values associated with a policy.

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 decompressed policy vector is a first decompressed policy vector,

the apparatus further comprising:

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.

5. The apparatus of claim 1, wherein the decompressed policy vector is a first decompressed policy vector, the portion of the data packet is a first portion of the data packet,

the apparatus further comprising:

a combination module configured to receive the first decompressed policy vector and configured to produce a combined policy vector based on a boolean combination of the first decompressed policy vector and a 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.

6. The apparatus of claim 1, wherein the policy vector module is configured to define an index value based on the 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.

7. The apparatus of claim 1, further comprising:

a packet processing module configured to receive the 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 decompressed policy vector.

8. The apparatus of claim 1, wherein the decompressed policy vector is a first decompressed policy vector,

the apparatus further comprising:

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

9. 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 decompressed policy vector.

10. An apparatus, comprising:

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

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.

11. The apparatus of claim 10, further comprising:

a decompression module configured to receive the compressed policy vector and configured to produce a decompressed policy vector based on the compressed policy vector, the decompressed policy vector including a set of bit values configured to trigger execution of an instruction associated with a policy.

12. The apparatus of claim 10, 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.

13. The apparatus of claim 10, 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.

14. The apparatus of claim 10, further comprising:

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.

15. The apparatus of claim 10, further comprising:

a decompression module configured to receive the compressed policy vector and configured to produce a decompressed policy vector based on the compressed policy vector, the decompressed policy vector 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; and

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.

16. A method, comprising:

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

retrieving a compressed policy vector based on the key vector; and

defining a decompressed policy vector having a plurality of policy bit values based on the 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.

17. The method of claim 16, 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.

18. The method of claim 16, 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 decompressed policy vector and a second decompressed policy vector.

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

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

21. The method of claim 16, wherein the compressed policy vector is a first compressed policy vector, the retrieving associated with the first compressed policy vector includes retrieving based on a hash-based search function module,

the method further comprising:

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

22. The method of claim 16, wherein the compressed policy vector is a first compressed policy vector, 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; and

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

23. The method of claim 16, wherein the compressed policy vector is a first compressed policy vector, 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; and

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