Policy verification methods and apparatus

• US 7,023,852 B1
• Filed: 11/21/2001
• Issued: 04/04/2006
• Est. Priority Date: 11/24/2000
• Status: Active Grant

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Redback Networks Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Westfall, Ronald Leonard, Mar, Aaron S.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): ABELSON, RONALD B
• Application Number:
  US09/991,031
• Time in Patent Office: 1,595 Days
• Field of Search: 370/252, 370/389, 370/392, 370/395.1, 370/398, 370/395.21, 370/395.42, 370/395.43, 370/241
• US Class Current: 370/392
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

A number of classes are received. Each class has a number of classification rules. A result is output indicating a first class of the number of classes conflicts with a second class of the number of classes upon determining that at least one of classification rules of the first class overlaps with one of the classification rules of the second class.

Claims

1. A computer implemented method for verifying service policies of routing network traffic in a network element, the method comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating a first class of the number of classes conflicts with a second class of the number of classes upon determining that at least one of classification rules of the first class overlaps with one of the classification rules of the second class, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class is nested overlapped with one of the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

2. The method of claim 1, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class duplicates one of the classification rules of the second class.

3. The method of claim 1, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class partially overlaps with one of the classification rules of the second class.

4. A computer implemented method for verifying service policies of routing network traffic in a network element, the method comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating a first class of the number of classes conflicts with a second class of the number of classes upon determining that at least one of classification rules of the first class overlaps with one of the classification rules of the second class, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class is cyclic nested overlapped with one of the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routine network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

5. A computer implemented method for verifying service policies of routing network traffic in a network element, the method comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating a first class of the number of classes conflicts with a second class of the number of classes upon determining that at least one of classification rules of the first class overlaps with one of the classification rules of the second class, wherein the number of classification rules of each class include a number of dimensions, each dimension including a number of rule terms, wherein the method comprises merging the number of rule terms for each dimension;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

6. The method of claim 5, wherein the merging of the number of rule terms for each dimension comprises merging adjacent, overlapping and duplicate ranges of the number of rule terms for each dimension.

7. A computer implemented method for verifying service policies of routing network traffic in a network element, the method comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating whether a first class of the number of classes conflicts with a second class of the number of classes based on whether the classification rules of the first class overlap with the classification rules of the second class, wherein the number of classification rules of each class include a number of dimensions, each dimension including a number of rule terms, wherein the method comprises merging the number of rule terms for each dimension;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

8. The method of claim 7, wherein the merging of the number of rule terms for each dimension comprises merging adjacent, overlapping and duplicate ranges of the number of rule terms for each dimension and wherein outputting the result indicating whether the first class conflicts with the second class is based on whether the number of rule terms for each dimension of the classification rules of the first class overlap with the number of rule terms for each dimension of the classification rules of the second class.

9. The method of claim 7, wherein the outputting of the result indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class are duplicates of the classification rules of the second class.

10. The method of claim 7, wherein the outputting the result indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class partially overlap with the classification rules of the second class.

11. A computer implemented method for verifying service policies of routing network traffic in a network element, the method comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating whether a first class of the number of classes conflicts with a second class of the number of classes based on whether the classification rules of the first class overlap with the classification rules of the second class, wherein the outputting the result indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class nested overlap with the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

12. A computer implemented method for verifying service policies of routing network traffic in a network element, the method comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating whether a first class of the number of classes conflicts with a second class of the number of classes based on whether the classification rules of the first class overlap with the classification rules of the second class, wherein the outputting the result indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class cyclic nested overlap with the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

13. A computer implemented method for verifying service policies of routing network traffic in a network element, the method comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

for each classification rule of a first class of the number of classes, performing the following;

determining whether a classification rule of the first class partially overlaps a classification rule of a second class of the number of classes;

determining whether a classification rule of the first class nested overlaps a classification rule of the second class;

determining whether a classification rule of the first class is a duplicate of a classification rule of the second class;

outputting a result indicating the first class conflicts with the second class upon determining that a classification rule of the first class partially overlaps, nested overlaps, or is a duplicate of a classification rule of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

14. The method of claim 13, wherein the number of classification rules of each class include a number of dimensions, each dimension including a number of rule terms, wherein the method comprises merging the number of rule terms for each dimension.

15. The method of claim 14, wherein the merging of the number of rule terms for each dimension comprises merging adjacent, overlapping and duplicate ranges of the number of rule terms for each dimension.

16. The method of claim 15, wherein outputting the result indicating the first class conflicts with the second class comprises outputting the result indicating the first class conflicts with the second class upon determining that the number of rule terms for each dimension of the number of classification rules of the first class partially overlaps, nested overlaps, or is a duplicate of the number of rule terms for each dimension of the number of classification rules of the second class.

17. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies of routing network traffic in a network element, the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating a first class of the number of classes conflicts with a second class of the number of classes upon determining that at least one of classification rules of the first class overlaps with one of the classification rules of the second class, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class is nested overlapped with one of the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

18. The machine-readable medium of claim 17, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class duplicates one of the classification rules of the second class.

19. The machine-readable medium of claim 17, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class partially overlaps with one of the classification rules of the second class.

20. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies of routing network traffic in a network element, the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating a first class of the number of classes conflicts with a second class of the number of classes upon determining that at least one of classification rules of the first class overlaps with one of the classification rules of the second class, wherein the outputting of the result indicating the first class conflicts with the second class upon determining that the at least one of the classification rules of the first class is cyclic nested overlapped with one of the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

21. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies of routing network traffic in a network element, the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating a first class of the number of classes conflicts with a second class of the number of classes upon determining that at least one of classification rules of the first class overlaps with one of the classification rules of the second class, wherein the number of classification rules of each class include a number of dimensions, each dimension including a number of rule terms, wherein the method comprises merging the number of rule terms for each dimension;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

22. The machine-readable medium of claim 21, wherein the merging of the number of rule terms for each dimension comprises merging adjacent, overlapping and duplicate ranges of the number of rule terms for each dimension.

23. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies of routing network traffic in a network element the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating whether a first class of the number of classes conflicts with a second class of the number of classes based on whether the classification rules of the first class overlap with the classification rules of the second class, wherein the number of classification rules of each class include a number of dimensions, each dimension including a number of rule terms, wherein the method comprises merging the number of rule terms for each dimension;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

25. The machine-readable medium of claim 23, wherein the outputting of the result indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class are duplicates of the classification rules of the second class.

26. The machine-readable medium of claim 23, wherein the outputting the result indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class partially overlap with the classification rules of the second class.

24. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies of routing network traffic in a network element, the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating whether a first class of the number of classes conflicts with a second class of the number of classes based on whether the classification rules of the first class overlap with the classification rules of the second class, wherein the merging of the number of rule terms for each dimension comprises merging adjacent, overlapping and duplicate ranges of the number of rule terms for each dimension and wherein outputting the result indicating whether the first class conflicts with the second class is based on whether the number of rule terms for each dimension of the classification rules of the first class overlap with the number of rule terms for each dimension of the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

27. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies or routing network traffic in a network element, the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating whether a first class of the number of classes conflicts with a second class of the number of classes based on whether the classification rules of the first class overlap with the classification rules of the second class, wherein the outputting the result indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class nested overlap with the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second; and

routine network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

28. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies of routing network traffic in a network element, the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

outputting a result indicating whether a first class of the number of classes conflicts with a second class of the number of classes based on whether the classification rules of the first class overlap with the classification rules of the second class, wherein the outputting the result, indicating whether the first class conflicts with the second class is based on whether the classification rules of the first class cyclic nested overlap with the classification rules of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

29. A machine-readable storage medium that provides instructions, which when executed by a machine, causes the machine to perform operations for verifying service policies of routing network traffic in a network element, the operations comprising:

receiving a number of classes of network traffic, each class having a number of classification rules;

for each classification rule of a first class of the number of classes, performing the following;

determining whether a classification rule of the first class partially overlaps a classification rule of a second class of the number of classes;

determining whether a classification rule of the first class nested overlaps a classification rule of the second class;

determining whether a classification rule of the first class is a duplicate of a classification rule of the second class;

outputting a result indicating the first class conflicts with the second class upon determining that a classification rule of the first class partially overlaps, nested overlaps, or is a duplicate of a classification rule of the second class;

in response to the result, modifying at least a portion of the classification rules of the first and second classes to reduce the conflicts between the first and second classes; and

routing network traffic associated with the first and second classes according to the modified classification rules of the first and second classes.

30. The machine-readable medium of claim 29, wherein the number of classification rules of each class include a number of dimensions, each dimension including a number of rule terms, wherein the method comprises merging the number of rule terms for each dimension.

31. The machine-readable medium of claim 30, wherein the merging of the number of rule terms for each dimension comprises merging adjacent, overlapping and duplicate ranges of the number of rule terms for each dimension.

32. The machine-readable medium of claim 31, wherein outputting the result indicating the first class conflicts with the second class comprises outputting the result indicating the first class conflicts with the second class upon determining that the number of rule terms for each dimension of the number of classification rules of the first class partially overlaps, nested overlaps, or is a duplicate of the number of rule terms for each dimension of the number of classification rules of the second class.