Methods for performing packet classification via prefix pair bit vectors
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17)
-
-
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. - View Dependent Claims (19, 20)
-
Specification