Technique for policy conflict resolution using priority with variance

• US 7,751,331 B1
• Filed: 09/29/2005
• Issued: 07/06/2010
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Blair, Dana, Lynn, Kerry
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): MASUR, PAUL H
• Application Number:
  US11/239,573
• Time in Patent Office: 1,741 Days
• Field of Search: 370/230, 370/235, 370/236, 709223-226, 709/238, 726/2, 726/3, 726/5, 726/6, 379/1.01, 379/9, 379/15.01, 379/111, 379/112.01, 379/112.06, 702/127, 702/182, 702/186
• US Class Current: 370/236
• CPC Class Codes: G01V 1/28 Processing seismic data, e.g. for interpretation or for event detection G01V1/48 takes precedence
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0866 Checking the configuration
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 65/1101 Session protocols

Abstract

A technique efficiently renders a policy-based decision from a plurality of options based on policy priority in a computer network. According to the novel technique, each of a plurality of policies is assigned an exclusive priority value, as well as a “variance” specifying an acceptable value range (e.g., a percentage). Beginning at the highest priority policy, values corresponding to the plurality of options are analyzed based upon the current priority policy, and a “best” option is determined according to the current policy. Thereafter, the variance for the current policy is applied to the value of the best option, defining a range of acceptable values for the current policy, and remaining options having an acceptable value for the current policy are established. If only one remaining option exists, that option is selected as the best option. Otherwise, the remaining options are analyzed based upon the next priority policy, a best option is determined, the variance is applied, and remaining options are established in the same manner, until a single best option exists.

Claims

1. A method for efficiently rendering a policy-based decision from a plurality of options based on policy priority in a computer network, the method comprising:

assigning an exclusive priority value to each of a plurality of policies;

assigning a variance to each of the plurality of policies, the variance to specify an acceptable value range;

setting a current policy to a highest priority policy;

analyzing values corresponding to the plurality of options based upon the current policy;

determining, by a processor of a node in the computer network, a best option according to the current policy;

applying, by the processor of the node, the variance for the current policy to a value of the best option to define a range of acceptable values for the current policy;

establishing, by the processor of the node, remaining options having an acceptable value for the current policy; and

in response to only one option remaining, selecting, by the processor of the node, the one remaining option as the best option.

2. The method as in claim 1, further comprising:

in response to more than one remaining option, setting the current policy to a next lower priority policy, and repeating the steps of analyzing, determining, applying, establishing, selecting and setting the current policy to a next lower priority policy until a single best option exists.

3. The method as in claim 1, further comprising:

in response to more than one remaining option after the lowest priority policy, selecting the best option based upon a technique selected from the group consisting of;

a weighted policy, a strict policy, and a random selection.

4. The method as in claim 1, further comprising:

assigning the variance as a percentage value.

5. The method as in claim 1, wherein the plurality of options are a plurality of paths from a source to a destination.

6. The method as in claim 5, wherein the selection of the best path is performed in accordance with Optimized Edge Routing (OER).

7. A node for efficiently rendering a policy-based decision from a plurality of options based on policy priority in a computer network, the node comprising:

one or more network interfaces;

a processor coupled to the one or more network interfaces and adapted to execute software processes; and

a memory adapted to store a decision making process executable by the processor, the decision making process configured to perform operations, including operations to;

assign an exclusive priority value to each of a plurality of policies;

assign a variance to each of the plurality of policies, the variance to specify an acceptable value range;

set a current policy to a highest priority policy;

analyze values corresponding to the plurality of options based upon the current policy;

determine a best option according to the current policy;

apply the variance for the current policy to a value of the best option to define a range of acceptable values for the current policy;

establish remaining options having an acceptable value for the current policy; and

in response to only one option remaining, select the one remaining option as the best option.

8. The node as in claim 7, wherein the decision making process is further configured to:

in response to more than one remaining option, set the current policy to a next lower priority policy, and repeat the operations to analyze, determine, apply, establish, select, and set the current policy to a next lower priority policy until a single best option exists.

9. The node as in claim 7, wherein the decision making process is further configured to:

in response to more than one remaining option after the lowest priority policy, select the best option based upon a technique selected from the group consisting of;

a of a weighted policy, a strict policy, and a random selection.

10. The node as in claim 7, wherein the variance is assigned as a percentage value.

11. The node as in claim 7, wherein the plurality of options is a plurality of paths from a source to a destination.

12. The node as in claim 11, further comprising:

an Optimized Edge Routing (OER) process as the decision making process.

13. An apparatus for efficiently rendering a policy-based decision from a plurality of options based on policy priority in a computer network, the apparatus comprising:

means for assigning an exclusive priority value to each of a plurality of policies;

means for assigning a variance to each of the plurality of policies, the variance to specify an acceptable value range;

means for setting a current policy to a highest priority policy;

means for analyzing values corresponding to the plurality of options based upon the current policy;

means for determining a best option according to the current policy;

means for applying the variance for the current policy to a value of the best option to define a range of acceptable values for the current policy;

means for establishing remaining options having an acceptable value for the current policy; and

means for selecting the one remaining option as the best option, in response to only one option remaining.

14. The apparatus as in claim 13, further comprising:

means for setting the current policy to a next lower priority policy in response to more than one remaining option.

15. The apparatus as in claim 13, further comprising:

means for selecting, in response to more than one remaining option after the lowest priority policy, the best option based upon a technique selected from the group consisting of;

a weighted policy, a strict policy, and a random selection.

16. The apparatus as in claim 13, wherein the plurality of options is a plurality of paths from a source to a destination.

17. A non-transitory computer readable medium containing executable program instructions for of rendering a policy-based decision from a plurality of options based on policy priority in a computer network, the executable program instructions comprising program instructions for:

assigning an exclusive priority value to each of a plurality of policies;

assigning a variance to each of the plurality of policies, the variance to specify an acceptable value range;

setting a current policy to a highest priority policy;

analyzing values corresponding to the plurality of options based upon the current policy;

determining a best option according to the current policy;

applying the variance for the current policy to a value of the best option to define a range of acceptable values for the current policy;

establishing remaining options having an acceptable value for the current policy; and

in response to only one option remaining selecting the one remaining option as the best option.

18. The computer readable medium as in claim 17, the executable program instructions further comprising program instructions for:

in response to more than one remaining option, setting the current policy to a next lower priority policy, and repeating execution of the instructions for analyzing, determining, applying, establishing, selecting and setting the current policy to a next lower priority policy until a single best option exists.

19. The computer readable medium as in claim 17, the executable program instructions further comprising program instructions for:

in response to more than one remaining option after the lowest priority policy, selecting the best option based upon a technique selected from the group consisting of;

a weighted policy, a strict policy, and a random selection.

20. The computer readable medium as in claim 17, wherein the plurality of options is a plurality of paths from a source to a destination.