Methods and apparatus to implement except condition during data packet classification

• US 9,413,660 B1
• Filed: 06/23/2014
• Issued: 08/09/2016
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Goel, Deepak, Panwar, Ramesh Kumar, Jagannadhan, Srinivasan
• Primary Examiner(s): Renner, Brandon
• Application Number:
  US14/312,283
• Time in Patent Office: 778 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

In one embodiment, a method includes receiving a value associated with a data packet and identifying a data set based on the value. The data set is associated with a range of values and represents routing actions. The data set is a first data set from a plurality of data sets if the value is included in the range of values associated with the first data set. The data set is a default data set if the value is not included in a range of values associated with a data set from the plurality of data sets. The method includes combining the first data set with the default data set if the first data set is identified. The method includes combining the default data set with an except data set if the default data set is identified.

Claims

1. A method, comprising:

receiving, via a processor, a value associated with a portion of a data packet;

identifying, via the processor, one of a first data set or a default data set from a plurality of data sets based on the value, each data set from the plurality of data sets being associated with a range of values each associated with an instruction to trigger a routing action associated with a condition, the first data set being associated with a first range of values including the value, the default data set being associated with a default range of values each associated with an instruction to trigger a routing action associated with a default condition;

when the first data set is identified;

combining, via the processor, the first data set and the default data set to produce a first combined data set including a plurality of values each associated with an instruction to trigger a routing action associated with at least one of the condition or the default condition; and

sending the first combined data set; and

when the first data set is not identified;

sending the default data set.

2. The method of claim 1, wherein the value is an Internet Protocol address of a network entity associated with the data packet.

3. The method of claim 1, wherein the range of values associated with each data set from the plurality of data sets is associated with a range of Internet Protocol addresses.

4. The method of claim 1, wherein the value is a port identifier of a network entity associated with the data packet.

5. The method of claim 1, wherein the condition is a first condition, the method further comprising:

when the first data set is not identified;

identifying, via the processor, an except data set from the plurality of data sets based on the value, the except data set being associated with an excluded range of values associated with instructions to trigger routing actions associated with a second condition;

combining, via the processor, the default data set and the except data set to produce a second combined data set associated with instructions to trigger routing actions associated with at least one of the second condition or the default condition; and

sending the second combined data set.

6. The method of claim 1, wherein the combining the first data set and the default data set to produce the first combined data set is based on a logical combination.

7. A non-transitory processor-readable medium storing code representing instructions to cause a processor to:

define a key associated with a portion of a data packet received at a multi-stage switch;

generate a first policy vector based on the key and a set of keys, the first policy vector being represented by a plurality of bit values, each bit value from the plurality of bit values associated with an instruction to trigger a routing action associated with a first condition;

when the first policy vector does not include bit values associated with instructions to trigger routing actions associated with a default condition, generate a second policy vector associated with a set of default keys including the key, the second policy vector being represented by a plurality of bit values associated with instructions to trigger routing actions associated with the default condition; and

produce a composite policy vector, the composite policy vector being based on a logical combination of the plurality of bit values of the first policy vector and the plurality of bit values of the second policy vector when the first policy vector does not include bit values associated with instructions to trigger routing actions associated with the default condition, and the composite policy vector being the first policy vector when the first policy vector includes at least one value associated with instructions to trigger routing actions associated with the default condition.

8. The non-transitory processor-readable medium of claim 7, wherein the key is an Internet Protocol address of a network entity associated with the data packet.

9. The non-transitory processor-readable medium of claim 7, wherein the key is a port identifier of a network entity associated with the data packet.

10. The non-transitory processor-readable medium of claim 7, wherein the first policy vector is generated as a result of a search of a policy vector database based on the key.

11. The non-transitory processor-readable medium of claim 7, wherein the first policy vector is generated based on a hash function.

12. The non-transitory processor-readable medium of claim 7, wherein the first policy vector is generated based on a linked-node structure.

13. The non-transitory processor-readable medium of claim 7, further comprising:

generate a third policy vector when the first policy vector is a default policy vector, the third policy vector being associated with a set of exclusion keys including the key, the third policy vector being represented by a plurality of bit values associated with instructions to trigger routing actions associated with a third condition; and

the composite policy vector being based on a logical combination of the plurality of bit values of the first policy vector and the plurality of bit values of the third policy vector when the first policy vector includes at least one value associated with an instruction to trigger a routing action associated with the default condition.

14. The non-transitory processor-readable medium of claim 7, wherein the key is associated with multiple portions of the data packet.

15. An apparatus, comprising:

a memory configured to store a policy vector database including a plurality of policy vectors, each policy vector from the plurality of policy vectors being represented by a plurality of bit values associated with instructions to trigger routing actions associated with a condition in a multi-stage switch; and

a processor operatively coupled to the memory,

the processor configured to define a key associated with a portion of a data packet received at the multi-stage switch;

the processor configured to generate a first policy vector based on the key and a set of keys,

the processor configured to generate a second policy vector when the first policy vector does not include bit values associated with instructions to trigger routing actions associated with a default condition, the second policy vector being associated with a set of default keys including the key, and

the processor configured to produce a composite policy vector, the composite policy vector being based on a logical combination of the plurality of bit values of the first policy vector and the plurality of bit values of the second policy vector when the first policy vector does not include bit values associated with instructions to trigger routing actions associated with the default condition, and the composite policy vector being the first policy vector when the first policy vector includes at least one bit value associated with an instruction to trigger a routing action from the instructions to trigger routing actions associated with the default condition.

16. The apparatus of claim 15, wherein the key is an Internet Protocol address of a network entity associated with the data packet.

17. The apparatus of claim 15, wherein the key is a port identifier of a network entity associated with the data packet.

18. The apparatus of claim 15, wherein the first policy vector is generated as a result of a search of a policy vector database based on the key.

19. The apparatus of claim 15, wherein the first policy vector is generated based on a hash function.

20. The apparatus of claim 15, wherein the first policy vector is generated based on a linked-node structure.