US Patent No. 9,413,662

INTRA-TERM LOGICAL OR OPERATION IN A NETWORK FILTER


Patent No. 9,413,662
Issue Date August 09, 2016
Title Intra-term Logical Or Operation In A Network Filter
Inventorship Anand Ammundi, Cupertino, CA (US)
Atul Mahamuni, San Jose, CA (US)
Assignee Juniper Networks, Inc., Sunnyvale, CA (US)

Claim of US Patent No. 9,413,662

1. A device comprising:
a computer memory to store instructions; and
one or more computer processors to execute the instructions to:
receive a filter definition,
the filter definition including one or more terms that define how network traffic is to be filtered through the device;
parse the filter definition into the one or more terms;
determine that a particular term, of the one or more terms, includes a logical OR condition;
determine attribute counts of the particular term,
the attribute counts including an attribute count for a particular attribute of the particular term, and
the attribute count being a quantity of different values being matched;
calculate a first expansion factor based on a product of the attribute counts;
calculate a second expansion factor that is different from the first expansion factor;
expand the particular term into a plurality of sub-terms based on determining that the particular term includes the logical
OR condition, based on the first expansion factor, and based on the second expansion factor,

the plurality of sub-terms including a first sub-term and a second sub-term,
the first sub-term including a first condition that specifies the particular attribute and a first discrete value for the
particular attribute,

the second sub-term including a second condition that specifies the particular attribute and a second discrete value for the
particular attribute,

the particular attribute being associated with an address, a port, or a protocol, and
the second discrete value being different from the first discrete value;
determine a particular priority associated with the particular term;
determine, for the plurality of sub-terms and based on the particular priority, locations within a ternary content-addressable
memory (TCAM);

store the plurality of sub-terms as a plurality of entries at the locations within the TCAM,
the plurality of entries including a value entry, and
when storing the plurality of sub-terms as the plurality of entries, the one or more computer processors are to:
determine that the first sub-term specifies the first discrete value for the particular attribute that corresponds to a first
field of the value entry,

set the first field, of the value entry, to the first discrete value based on determining that the first sub-term specifies
the first discrete value for the particular attribute,

determine that the first sub-term does not specify a value for a different attribute that corresponds to a second field of
the value entry,

 the second field being a virtual local area network (VLAN) field, and
set a field, of a mask entry, to an indicator that indicates that the value for the different attribute does not matter based
on determining that the first sub-term does not specify the value for the different attribute,

 the mask entry corresponding to the value entry; and
append strings, in the TCAM and to the plurality of entries, that indicate a spatial ordering of the plurality of sub-terms;
update the TCAM based on the strings to preserve the spatial ordering; and
process the network traffic based on one or more of the plurality of entries in the TCAM by performing an action corresponding
to the value entry,

the action being one of discarding, accepting, or counting.