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

• US 8,571,034 B2
• Filed: 04/29/2011
• Issued: 10/29/2013
• 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 CHI
• Application Number:
  US13/097,770
• Publication Number:
  US 20110200038A1
• Time in Patent Office: 914 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 decompression module implemented in at least one of a memory or a processing device, the decompression module configured to define a first decompressed policy vector based on a compressed policy vector associated with a first portion of a data packet received at a multi-stage switch, 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 second decompressed policy vector being defined based on a second portion of the data packet different than the first portion of the data packet, the combined policy vector configured to trigger an element at the multi-stage switch to process the data packet based on the combined policy vector.

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

a key vector module configured to define a key vector including a bit sequence associated with the first portion of the data packet; and

a policy vector module configured to retrieve the compressed policy vector based on the key vector.

3. The apparatus of claim 1, further comprising:

a policy vector module configured to retrieve the compressed policy vector based on a key vector using at least one of a hash-based search function module or a node-based search function module.

4. The apparatus of claim 1, further comprising:

a policy vector module configured to define an index value based on a key vector; and

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.

5. The apparatus of claim 1, further comprising:

a packet processing module configured to receive the combined policy vector and configured to trigger the element based on a combination of bit values defined by the combined policy vector.

6. 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 the combination of bit values.

7. The apparatus of claim 1, wherein the policy is a first policy, the apparatus further comprising:

a packet processing module configured to trigger execution of an instruction associated with a second policy based on the combined policy vector.

8. The apparatus of claim 1, further comprising:

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

9. An apparatus, comprising:

a policy vector module implemented in at least one of a memory or a processing device, the policy vector module configured to produce an index value based on at least one of a hash-based search function or a node-based search function using a portion of a data packet received at a multi-stage switch, the policy vector module configured to retrieve a compressed policy vector based on the index value;

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

a packet processing module configured to trigger based on the decompressed policy vector an element at the multi-stage switch to process the data packet.

10. The apparatus of claim 9, wherein the packet processing module is 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 associated with 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, 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.

13. The apparatus of claim 9, wherein the data packet is defined based on Internet Protocol version 6 (IPv6).

14. A non-transitory processor-readable medium storing code representing instructions to be executed by a processor, the code comprising code to cause the processor to:

retrieve a first compressed policy vector based on a portion of a data packet and a hash-based search function;

define 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 a multi-stage switch to process the data packet when the policy bit value is set; and

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

15. The non-transitory processor-readable medium 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 non-transitory processor-readable medium of claim 14, wherein the decompressed policy vector is a first decompressed policy vector, the code further comprising code to cause the processor to:

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

17. The non-transitory processor-readable medium of claim 14, wherein each policy bit value from the plurality of policy bit values is associated with at least one term included in a policy associated with the multi-stage switch.

18. The non-transitory processor-readable medium of claim 14, wherein the data packet is defined based on Internet Protocol version 6 (IPv6).

19. The non-transitory processor-readable medium of claim 14, wherein the portion of the data packet is a first portion of the data packet, the code further comprising code to cause the processor to:

define a first key vector based on the first portion of the data packet, the code to cause the processor to retrieve the first compressed policy vector including code to cause the processor to retrieve the first compressed policy vector based on the first key vector; and

define 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 code to cause the processor to retrieve the second compressed policy vector including code to cause the processor to retrieve the second compressed policy vector based on the second key vector.

20. The non-transitory processor-readable medium of claim 14, wherein the portion of the data packet is a first portion of the data packet, the code further comprising code to cause the processor to:

define a first key vector based on the first portion of the data packet, the code to cause the processor to retrieve the first compressed policy vector including code to cause the processor to retrieve the first compressed policy vector based on the first key vector; and

define 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 code to cause the processor to retrieve the second compressed policy vector including code to cause the processor to retrieve the second compressed policy vector based on the second key vector.

21. The non-transitory processor-readable medium of claim 14, wherein the portion of the data packet is a first portion of the data packet, the code to cause the processor to retrieve the second compressed policy vector including code to cause the processor to retrieve the second compressed policy vector based on a second portion of the data packet.