Methods and apparatus to implement except condition during data packet classification

• US 8,798,057 B1
• Filed: 09/30/2008
• Issued: 08/05/2014
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Goel, Deepak, Panwar, Ramesh, Jagannadhan, Srinivasan
• Primary Examiner(s): RENNER, BRANDON M
• Application Number:
  US12/242,278
• Time in Patent Office: 2,135 Days
• Field of Search: 370/392, 370/395.21, 370/411
• US Class Current: 370/392
• 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 non-transitory processor-readable medium storing code representing instructions to cause a processor to:

receive a value associated with a portion of a data packet;

identify one of a first data set from a plurality of data sets or a default data set based on the value, each data set from the plurality of data sets being associated with a range of values, the plurality of data sets representing routing action triggering instructions, the default data set representing a routing action triggering instruction, the first data set being associated with a first range of values including the value if the first data set is identified, the default data set being associated with a default range of values, an except data set being associated with an excluded range of values, the except data set representing a routing action triggering instruction;

combine, if the first data set is identified, the first data set and the default data set to produce a first combined data set;

combine, if the default data set is identified, the default data set with the except data set to produce a second combined data set;

send the first combined data set if the first combined data set is produced; and

send the second combined data set if the second combined data set is produced.

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

3. The non-transitory processor readable medium of claim 1, wherein the value is a port identifier of a network entity associated with the data packet.

4. The non-transitory processor readable medium of claim 1, wherein:

the code representing instructions to cause the processor to identify includes code representing instructions to identify the first data set if the first range of values associated with the first data set is a subset of a second range of values including the value and associated with a second data set from the plurality of data sets.

5. The non-transitory processor-readable medium of claim 1, wherein the default data set includes a plurality of bit elements configured to trigger a routing action in the switch fabric, the except data set including a plurality of bit elements configured to trigger a routing action in the switch fabric,

the code representing instructions to cause the processor to combine the default data set with the except data set including code configured to preserve a bit element from the plurality of bit elements of the default data set and code configured to preserve a bit element from the plurality of bit elements of the except data set.

6. 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 bit sequence and associated with a set of keys, each policy vector from the plurality of policy vectors being associated with at least one action triggering instruction in a switch fabric based on a bit value of each bit element in that policy vector;

a processor operatively coupled to the memory,

the processor configured to produce an indicator associated with an availability of a policy vector from the plurality of policy vectors, the policy vector from the plurality of policy vectors being associated with a set of keys including a key, associated with a portion of a data packet received at a multi-stage switch; and

the processor configured to produce a composite policy vector, the composite policy vector being a logical bit combination of a first default policy vector from the plurality of policy vectors with one of, based on the indicator, the policy vector from the plurality of policy vectors or a second default policy vector from the plurality of policy vectors, the first default policy vector being associated with a default set of keys, the second default policy vector being associated with an excepted set of keys, the excepted set of keys including a second set of keys to be excepted from the default set of keys.

7. The apparatus of claim 6, wherein each policy vector from the plurality of policy vectors is uniquely associated with a set of keys having no disjunctive overlaps with the set of keys associated with each remaining policy vector from the plurality of policy vectors.

8. The apparatus of claim 6, wherein the portion of the data packet is associated with an Internet Protocol address.

9. The apparatus of claim 6, wherein the set of keys associated with each policy vector from the plurality of policy vectors is associated with a range of Internet Protocol addresses.

10. The apparatus of claim 6, wherein:

the policy vector database in the memory is a first policy vector database in the memory, the portion of the data packet is a first portion of the data packet, the composite policy vector being a first composite policy vector; and

the memory is configured to store a second policy vector database including a plurality of policy vectors, each policy vector from the plurality of policy vectors of the second policy vector database being represented by a bit sequence and associated with a set of keys, each policy vector from the plurality of policy vectors of the second policy vector database being associated with one or more action triggering instructions in the switch fabric based on a bit value of each bit element in the policy vector;

the processor is further configured to produce an indicator associated with an availability of a policy vector from the plurality of policy vectors of the second policy vector database, the policy vector from the plurality of policy vectors of the second policy vector database being associated with a set of keys including a key associated with a second portion of the data packet received at the multi-stage switch;

the processor is further configured to produce a second composite policy vector, the second composite policy vector being a logical bit combination of a third default policy vector from the plurality of policy vectors of the second policy vector database with one of, based on the indicator produced by the second policy vector module, the policy vector from the plurality of policy vectors of the second policy vector database or a fourth default policy vector from the plurality of policy vectors of the second policy vector database; and

the processor is further configured to produce a third composite policy vector, the third composite policy vector being a logical bit combination of the first composite policy vector with the second composite policy vector.

11. The apparatus of claim 6, wherein the composite policy vector includes a bit element from the bit sequence of the first default policy vector from the plurality of policy vectors and a bit element from the bit sequence of one of the policy vector from the plurality of policy vectors or the second default policy vector from the plurality of policy vectors.

12. A method, comprising:

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

accessing a first policy vector associated with one of a first set of keys including the key or a default set of keys, the first policy vector having a plurality of bit elements, each bit element from the plurality of bit elements of the first policy vector being uniquely associated with an action triggering instruction in a switch fabric of the multi-stage switch;

accessing a second policy vector based on the first set of keys or the default set of keys, the second policy vector being associated with an excepted set of keys including a second set of keys associated with an except condition, the second policy vector having a plurality of bit elements, each bit element from the plurality of bit elements of the second policy vector being uniquely associated with an action triggering instruction in the switch fabric; and

producing a composite policy vector based on a logical combination of the first policy vector with the second policy vector.

13. The method of claim 12, wherein:

the accessing the first policy vector is based on a hash-based function; and

the accessing the second policy vector is based on a linked-node function.

14. The method of claim 12, wherein the second policy vector is accessed based on the default set of keys, the first policy vector being associated with the default set of keys.

15. The method of claim 12, wherein the accessing the second policy vector includes determining whether the first policy vector is associated with the default set of keys.

16. The method of claim 12, further comprising receiving an indication that the first policy vector is associated with the default set of keys before the accessing the second policy vector.

17. The method of claim 12, wherein:

the logical combination is configured to preserve a bit element from the plurality of bit elements of the first policy vector configured to trigger an action in the switch fabric; and

the logical combination is configured to preserve a bit element from the plurality of bit elements of the second policy vector configured to trigger an action in the switch fabric.

18. The method of claim 12, wherein the accessing the second policy vector includes accessing the second policy vector based on a type of the first set of keys or a type of the default set of keys.