Method and system for determining network-wide interactions between forwarding elements in a network

Patent metadata

Field	Value
Publication number	US-9548932-B2
Application number	US-201314236092-A
Country	US
Kind code	B2
Filing date	Apr 25, 2013
Priority date	Apr 27, 2012
Publication date	Jan 17, 2017
Grant date	Jan 17, 2017

Abstract

A method for detecting interactions on a forwarding element in a network, the element adapted to forward data according to rules, a rule set installed on the element, and including a match set and corresponding action set, the match set including at least one match field and the action set including one or more actions wherein action to be performed when matching a match set includes determining one or more relations between match sets based on match field relations, determining one or more relations between action sets, determining one or more interactions between rules based on determined relations between match sets and action sets, each rule being tested against another rule for determining the interaction, and reducing the rule set to an actual rule set according to determined interactions so that the actual rule set includes only rules with no interactions among them.

First claim

The invention claimed is:

1. A method to be executed by a computer device for detecting interactions on a forwarding element in a network (N), wherein the forwarding element (FE) forwards data according to rules, installable on the forwarding element (FE), and wherein a rule set (RS) is installed on the forwarding element (FE), and wherein the rule set (RS) comprises rules (R), and wherein a rule comprises a match set (M) and at least a corresponding action set (A), wherein the match set (M) comprises at least one match field (f) and wherein the action set (A) comprises one or more actions (a) wherein action set (A) to be performed when matching the match set (M) and a priority (P) assigned to each rule (R), comprising the steps of:
a) computing (S 1 ) one or more relations between the match sets (M) based on match field relations (f),
b) computing (S 2 ) one or more relations between the action sets (A),
c) computing (S 3 ) one or more interactions between the rules (R) based on the computed relations between the match sets (M) and the action sets (A), wherein each rule (Rx) is tested against another rule (Ry) for determining the interaction, wherein all of duplication, redundancy, generalization, shadowing, correlation, inclusion, and extension as rule interactions are determined, and
d) reducing (S 4 ) the rule set (RS) to an actual rule set (ARS) according to the computed interactions so that the actual rule set (ARS) comprises only rules (R) with no interactions among the rules,
wherein:
a2) the steps a), b), c) and d) are performed (V 1 ) for each forwarding element (FE) in the network (N),
b2) one of the forwarding elements (FE) is selected (V 2 ),
c2) a neighbor list of next neighbors (NNFE) with regard to the selected forwarding element (SFE) is determined (V 3 ),
d2) steps c1) to e1) are performed (V 4 ), as follows:
c1) performing (T 3 ) the steps a), b), c) and d) for each of the forwarding elements (NNFE) in the neighbor list for obtaining an actual rule set (ARS) for each of the forwarding elements (NNFE),
d1) determining (T 4 ) one or more interactions between the actual rule sets (ARS) of two neighbor forwarding elements (FE, NNFE),
e1) reducing (T 5 ) the actual rules sets (ARS) according to the computed interactions so that the actual rules sets (ARS) comprise only rules with no interactions to the rule (R) of the respective other actual rule set (ARS),

e2) the disjoint actual rule sets are merged (V 5 ) into one new actual rule set (ARS) representing both the neighbor forwarding element (NNFE) and the selected forwarding element (SFE),
f2) a merged forwarding element (MFE) is defined (V 6 ) with the new actual rule set (ARS) as new selected forwarding element (SFE), and
g2) performing (V 7 ) the steps c2) to f2) iteratively until a predetermined number have been merged to two forwarding elements (FE).

2. The method according to claim 1 , wherein match field relations are classified into any of a disjoint, equal, subset, superset and overlapping relation.

3. The method according to claim 1 , wherein match set relations are classified into any of a disjoint, exactly matching, subset, superset and correlated relation.

4. The method according to claim 1 , wherein action set relations are classified into any of a disjoint, related, subset, superset and equal relation.

5. The method according to claim 1 , wherein step d) is performed by performing the substeps
da) deleting all rules (R) classified as duplication, shadowed or inclusion, and
db) iteratively build the actual rule set (ARS) wherein the number of iterations is the number of rules (R) in the rule set (RS) to be reduced and wherein the match fields (f) are reduced depending on the relation between a match field (f) of the match fields (f) of a rule (Rx) with a higher priority and a match field (f) of another rule (Ry).

6. The method according to claim 1 , wherein, along with the performing (V 4 ) of steps c1) to e1), also performing steps a1) and b1) as follows:
a1) selecting (T 1 ) the one of the forwarding elements (SFE) as reference for determining the neighbor forwarding elements (NNFE), and
b1) determining (T 2 ) the neighbor list based on the forwarding elements (NNFE) directly connected to the selected forwarding element (SFE).

7. The method according to claim 6 , wherein the rules of the actual rule set (ARS) are splitted with respect to an ingress port of the forwarding element (FE).

8. The method according to claim 6 , wherein the actual rule set (ARS) of the selected forwarding element (SFE) comprises all forwarding rules forwarding to a neighbor forwarding element (NNFE) of the neighbor forwarding elements (NNFE), that interactions are determined between the actual rule set (ARS) and the actual rule set of the neighbor forwarding element (NNFE) of the neighbor forwarding elements (NNFE) and then interactions within the actual rule set (ARS) of the selected forwarding element (SFE) are checked with regard to ports.

9. The method according to claim 6 , wherein in step d1) match set transformations are checked.

10. The method according to claim 1 , wherein for merging ports of the forwarding elements (FE) are added with forwarding element identification information.

11. The method according to claim 1 , wherein for merging actions of at least two action sets (A1, A2) are combined to a single action set (A) based on the network topology.

12. The method according to claim 11 , wherein combining is performed by putting the actions (a) into appearance order in the network (N).

13. A system for determining network-wide interactions between forwarding elements (FE) in a network (N), comprising:
a reducing computer device performs steps for detecting interactions on a forwarding element in the network, the steps including:
a) computing (S 1 ) one or more relations between the match sets (M) based on match field relations (f),
b) computing (S 2 ) one or more relations between the action sets (A),
c) computing (S 3 ) one or more interactions between the rules (R) based on the computed relations between the match sets (M) and the action sets (A), wherein each rule (Rx) is tested against another rule (Ry) for determining the interaction, wherein all of duplication, redundancy, generalization, shadowing, correlation, inclusion, and extension as rule interactions are determined, and
d) reducing (S 4 ) the rule set (RS) to an actual rule set (ARS) according to the computed interactions so that the actual rule set (ARS) comprises only rules (R) with no interactions among the rules;

a determining device that selects one of the forwarding elements (FE) and to determine a neighbor list of next neighbors (NNFE) with regard to the selected forwarding element (SFE);
another reducing computer device that performs steps c1) to e1) as follows:
c1) performing (T 3 ), for each of the forwarding elements (NNFE) in the neighbor list, for obtaining an actual rule set (ARS) for each of the forwarding elements (NNFE), the steps of
computing one or more relations between the match sets based on match field relations,
computing one or more relations between the action sets,
computing one or more interactions between the rules based on the computed relations between the match sets and the action sets, wherein each rule is tested against another rule for determining the interaction, wherein all of duplication, redundancy, generalization, shadowing, correlation, inclusion and extension as rule interactions are determined, and
reducing the rule set to an actual rule set according to the computed interactions so that the actual rule set comprises only rules with no interactions amo

Assignees

• Nec Europe Ltd
• Nec Corp

Inventors

• Bifulco Roberto
• Hasselmeyer Peer
• Brunner Marcus

Classifications

• H04L45/00 Primary

  Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00) · CPC title

• H04L47/24 Primary

  Traffic characterised by specific attributes, e.g. priority or QoS · CPC title

• H04L45/645

  Splitting route computation layer and forwarding layer, e.g. routing according to path computational element [PCE] or based on OpenFlow functionality · CPC title