Methods for performing packet classification via prefix pair bit vectors

• US 20060221956A1
• Filed: 06/28/2005
• Published: 10/05/2006
• Est. Priority Date: 03/31/2005
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kumar, Alok, Narayan, Harsha L.
• Application Number:
  US11/170,230
• Publication Number:
  US 20060221956A1
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 2101/604 Address structures or formats
• 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/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

Methods for performing packet classification via prefix pair bit vectors. Unique prefix pairs in an access control list (ACL) are identified, with each prefix pair comprising a unique combination of a source prefix and a destination prefix. Corresponding prefix pair bit vectors (PPBVs) are defined for each unique source prefix and unique destination prefix in the ACL, with each PPBV including a string of bits and each bit position in the string associated with a corresponding prefix pair. A list of transport field value combinations are associated with each prefix pair based on corresponding entries in the ACL. During packet-processing operations, PPBV lookups are made using the source and destination prefix header values, and the PPBVs are logically ANDed to identify applicable prefix pairs. A search is then performed on transport field value combinations corresponding to the prefix pairs and the packet header to identify a highest priority rule.

Claims

1. A method, comprising:

identifying unique prefix pairs in an access control list (ACL), each prefix pair comprising a combination of a source prefix and a destination prefix;

defining a prefix pair bit vector for each unique source prefix and unique destination prefix in the ACL, each prefix pair bit vector including a string of bits, each bit position in the string associated with a corresponding prefix pair; and

associating a list of transport field value combinations with each prefix pair, each list comprising at least one instance of transport field values defined by a corresponding entry in the ACL including the source prefix and destination prefix defining the prefix pair.

2. The method of claim 1, further comprising:

storing the prefix pairs, prefix pair bit vectors, and lists of transport field value combinations in respective data structures.

3. The method of claim 1, wherein the list transport field value combinations comprise a List-of-PPPFs, each list including at least one instance of {Priority, Port ranges, Protocol, Flags} values defined by a corresponding entry in the ACL including the source prefix and destination prefix defining the prefix pair.

4. The method of claim 3, further comprising:

identifying unique List-of-PPPF instances;

storing the unique List-of-PPPF instances in a data structure; and

employing pointers to associate each prefix pair with its corresponding List-of-PPPF instance.

5. The method of claim 1, wherein the ACL is partitioned into a plurality of partitions, the method further comprising:

defining a plurality of partition bit vectors, each partition bit vector including a string of bits, each bit position in the string associated with a corresponding partition; and

associating each prefix pair bit vector with a corresponding partition bit vector.

6. The method of claim 1, further comprising:

defining a plurality of aggregated bit vectors, each aggregated bit vector including a string of bits, each bit position in the string associated with a corresponding set of bits in a bit string structure for the prefix pair bit vectors; and

storing data corresponding to the prefix pair bit vectors as a combination of a aggregated bit vector and a corresponding prefix pair bit vector.

7. The method of claim 1, further comprising storing the prefix pair bit vectors in recursive flow classification (RFC) chunks.

8. The method of claim 1, further comprising storing the prefix pair bit vectors in trie data structures.

9. A method, comprising:

extracting header data from a packet, the header data including a source prefix, a destination prefix, and a plurality of transport field values;

for each of the source prefix and destination prefix;

retrieving a corresponding prefix pair bit vector, each prefix pair bit vector including a string of bits, each bit position in the string associated with a corresponding prefix pair comprising a unique combination of source and destination prefixes in an access control list (ACL);

logically ANDing the prefix pair bit vectors to identify one or more prefix pairs that match the packet; and

performing a search of transport field value combinations associated with the one or more prefix pairs to identify a highest priority rule matching the packet.

10. The method of claim 9, wherein the search of the transport field value combinations is performed using a hardware-based search mechanism.

11. The method of claim 9, wherein the prefix pair bit vectors corresponding to each of the source prefix and destination prefix dimensions are stored in respective source prefix and destination prefix trie data structures, and the method further comprises:

employing the source prefix in the packet header to perform a longest-match prefix lookup on the source prefix trie data structure to obtain the prefix pair bit vector for the source prefix; and

employing the destination prefix in the packet header to perform a longest-match prefix lookup on the destination prefix trie data structure to obtain the prefix pair bit vector for the destination prefix.

12. The method of claim 9, wherein the prefix pair bit vectors corresponding to each of the source prefix and destination prefix dimensions are stored in respective recursive flow classification (RFC) chunks, and the method further comprises:

calculating a first index value based on the source prefix value in the packet header;

employing the first index value to locate an applicable prefix pair bit vector entry in the RFC chunk corresponding to the source prefix value;

calculating a second index value based on the destination prefix value in the packet header; and

employing the second index value to locate an applicable prefix pair bit vector entry in the RFC chunk corresponding to the destination prefix value.

13. A machine-readable medium, to store instructions that if executed perform operations comprising:

extracting header data from a packet, the header data including a source prefix, a destination prefix, and a plurality of transport field values;

for each of the source prefix and destination prefix;

retrieving a corresponding prefix pair bit vector, each prefix pair bit vector including a string of bits, each bit position in the string associated with a corresponding prefix pair comprising a unique combination of source and destination prefixes in an access control list (ACL); and

logically ANDing the prefix pair bit vectors to identify one or more prefix pairs that match the packet.

14. The machine-readable medium of claim 13, wherein execution of the instructions performs further operations comprising:

providing input identifying the one or more prefix pairs that match the packet to a search mechanism that performs a search of transport field value combinations associated with the one or more prefix pairs to identify a highest priority rule matching the packet.

15. The machine-readable medium of claim 14, wherein execution of the instructions performs further operations comprising:

employing the highest priority rule that is identified to process the packet.

16. The machine-readable medium of claim 13, wherein the prefix pair bit vectors corresponding to each of the source prefix and destination prefix dimensions are stored in respective source prefix and destination prefix trie data structures, and wherein execution of the instructions performs further operations comprising:

employing the source prefix in the packet header to perform a longest-match prefix lookup on the source prefix trie data structure to obtain the prefix pair bit vector for the source prefix; and

employing the destination prefix in the packet header to perform a longest-match prefix lookup on the destination prefix trie data structure to obtain the prefix pair bit vector for the destination prefix.

17. The machine-readable medium of claim 13, wherein the prefix pair bit vectors corresponding to each of the source prefix and destination prefix dimensions are stored in respective recursive flow classification (RFC) chunks, and wherein execution of the instructions performs further operations comprising:

calculating a first index value based on the source prefix value in the packet header;

employing the first index value to locate an applicable prefix pair bit vector entry in the RFC chunk corresponding to the source prefix value;

calculating a second index value based on the destination prefix value in the packet header; and

employing the second index value to locate an applicable prefix pair bit vector entry in the RFC chunk corresponding to the destination prefix value.

18. A network line card, comprising:

a network processor,

a plurality of input/output (I/O) ports, communicatively-coupled to the network processor;

memory, communicatively-coupled to the network processor; and

a storage device, communicatively-coupled to the network processor, having instructions stored therein that if executed perform operations comprising;

extracting header data from a packet, the header data including a source prefix, a destination prefix, and a plurality of transport field values;

for each of the source prefix and destination prefix;

retrieving a corresponding prefix pair bit vector, each prefix pair bit vector including a string of bits, each bit position in the string associated with a corresponding prefix pair comprising a unique combination of source and destination prefixes in an access control list (ACL); and

logically ANDing the prefix pair bit vectors to identify one or more prefix pairs that match the packet; and

providing input identifying the one or more prefix pairs that match the packet to a search mechanism that performs a search of transport field value combinations associated with the one or more prefix pairs to identify a highest priority rule matching the packet.

19. The network line card of claim 18, wherein the prefix pair bit vectors corresponding to each of the source prefix and destination prefix dimensions are stored in respective source prefix and destination prefix trie data structures, and wherein execution of the instructions performs further operations comprising:

employing the source prefix in the packet header to perform a longest-match prefix lookup on the source prefix trie data structure to obtain the prefix pair bit vector for the source prefix; and

employing the destination prefix in the packet header to perform a longest-match prefix lookup on the destination prefix trie data structure to obtain the prefix pair bit vector for the destination prefix.

20. The network line card of claim 18, wherein the prefix pair bit vectors corresponding to each of the source prefix and destination prefix dimensions are stored in respective recursive flow classification (RFC) chunks, and wherein execution of the instructions performs further operations comprising:

calculating a first index value based on the source prefix value in the packet header;

employing the first index value to locate an applicable prefix pair bit vector entry in the RFC chunk corresponding to the source prefix value;

calculating a second index value based on the destination prefix value in the packet header; and

employing the second index value to locate an applicable prefix pair bit vector entry in the RFC chunk corresponding to the destination prefix value.