US 9,288,290 B2Granted

Interactive dynamic ordering of deep packet inspection rules

AssigneeCisco Technology, Inc.

InventorsKadathur Natarajan, Prakash Suthar

Life of this patent

Estimating the term…

Loading patent…

Abstract

A network device processes packets transiting the device using successive deep packet inspection (DPI) rules. For each rule, the device attempts to apply the DPI rule to each packet, applies the DPI rule to each packet for which the attempt is successful, determines a probability that the attempt is successful across a plurality of packets, determines an average computational cost of applying the rule across a plurality of packets, and determines a merit of the DPI rule based on the average computational cost and the probability. The device reorders the successive DPI rules in an order of decreasing merit (computational cost), and processes new packets using the optimized DPI rules. The method of re-arranging DPI rules provides significant saving for network devices including mobile gateways in terms of computational cost.

Claims15

Dependent claims

A method comprising:

processing packets transiting a network device using successive deep packet inspection (DPI) rules arranged in a given order, the processing including, for each rule:
attempting to apply the DPI rule to each packet;
applying the DPI rule to each packet for which the attempt is successful;
determining a probability that the attempt is successful across a plurality of packets;
determining an average computational cost of applying the DPI rule across a plurality of packets;
and
determining a merit of the DPI rule that is proportional to a ratio of the probability to the average computational cost;
determining, based on the computational costs and the probabilities for each DPI rule, a total expected cost that indicates a computational efficiency of the given order;
reordering the successive DPI rules in an order of decreasing merit so as to decrease the total expected cost;
displaying statistics for each of the DPI rules and a list of the DPI rules as reordered according to the reordering;
prompting a user to select whether to use the reordered DPI rules;
if the user selects to use the reordered DPI rules, repeating the processing using the reordered DPI rules;
and
if the user selects not to use the reordered DPI rules, repeating the processing using the DPI rules in the given order.

11 more elements

An apparatus comprising:

a network interface unit configured to send and receive packets to and from a network;
and
a processor coupled to the network interface unit, and configured to:
process the packets using successive deep packet inspection (DPI) rules arranged in a given order, wherein the processor is configured to, for each rule:
attempt to apply the DPI rule to each packet;
apply the DPI rule to each packet for which the attempt is successful;
determine a probability that the attempt is successful across a plurality of packets;
determine an average computational cost of applying the DPI rule across a plurality of packets;
and
determine a merit of the DPI rule that is proportional to a ratio of the probability to the average computational cost;
determine, based on the computational costs and the probabilities for each DPI rule, a total expected cost that indicates a computational efficiency of the given order;
reorder the successive DPI rules in an order of decreasing merit so as to decrease the total expected cost;
display statistics for each of the DPI rules and a list of the DPI rules as reordered according to the reorder operation;
prompt a user to select whether to use the reordered DPI rules;
if the user selects to use the reordered DPI rules, repeat the process operation using the reordered DPI rules;
and
if the user selects not to use the reordered DPI rules, repeat the process operation using the DPI rules in the given order.

14 more elements

A tangible processor readable medium storing instructions that, when executed by a processor, cause the processor to:

process packets transiting a network device using successive deep packet inspection (DPI) rules arranged in a given order, wherein the processor is configured to, for each rule:
attempt to apply the DPI rule to each packet;
apply the DPI rule to each packet for which the attempt is successful;
determine a probability that the attempt is successful across a plurality of packets;
determine an average computational cost of applying the DPI rule across a plurality of packets;
and
determine a merit of the DPI rule that is proportional to a ratio of the probability to the average computational cost;
determine, based on the computational costs and the probabilities for each DPI rule, a total expected cost that indicates a computational efficiency of the given order;
and
reorder the successive DPI rules in an order of decreasing merit so as to decrease the total expected cost;
display statistics for each of the DPI rules and a list of the DPI rules as reordered according to the reorder operation;
prompt a user to select whether to use the reordered DPI rules;
if the user selects to use the reordered DPI rules, repeat the process operation using the reordered DPI rules;
and
if the user selects not to use the reordered DPI rules, repeat the process operation using the DPI rules in the given order.

12 more elements

Dependencies are inferred from the claim text.