Methods for performing packet classification via prefix pair bit vectors

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.

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.

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.