Efficient Memory Utilization for Cartesian Products of Rules

A method in a network device, the method comprising:

• exchanging packets over a network, each packet comprising a packet header having at least first and second header fields;
• for a given packet, determining a first search key based on the first header field of the given packet, and a second search key based on the second header field of the given packet;
• comparing the first search key to a first group of compare values, and, responsively to a match between the first search key and a first compare value in the first group, outputting a multi-element vector in which:
• one or more elements, having indices corresponding to indices of second compare values in the second group that match the second search key, are set;
• and
• one or more other elements, having indices corresponding to indices of second compare values in the second group that do not match the second search key, are not set;
• generating a composite search key, by concatenating the first search key and the multi-element vector;
• comparing the composite search key to a second group of compare values, and, responsively to a match between the composite search key and a second compare value in the second group, outputting an action indicator for applying to the given packet;
• and
• processing the packets responsively to the packet headers, including applying an action to the given packet responsively to the action indicator, which was output by the compare circuitry.

A method for determining actions to be applied to packets in a network device, the method comprising:

• for a given packet being processed in the network device, determining a first search key based on a first header field of the given packet, and a second search key based on a second header field of the given packet;
• comparing the first search key to a first group of compare values, and, responsively to a match, outputting a multi-element vector in which:
• one or elements, indices more having corresponding to indices of second compare values in the second group that match the second search key, are set;
• and
• one or more other elements, having indices corresponding to indices of second compare values in the second group that do not match the second search key, are not set;
• generating a composite search key, by concatenating the first search key and the multi-element vector;
• comparing the composite search key to a second group of compare values, and, responsively to a match, outputting an action indicator for applying to the given packet.