Technique for maintaining and enforcing relative policies with thresholds

• US 9,197,533 B1
• Filed: 09/29/2005
• Issued: 11/24/2015
• 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, Xia, Lei
• Primary Examiner(s): TANG, KIET G
• Application Number:
  US11/239,613
• Time in Patent Office: 3,708 Days
• Field of Search: 709/239, 709/201, 709/232, 709/227, 709/235, 709/223, 370/235, 370/352, 370/328, 370/396, 718/104, 713/201, 705/37, 703/2, 702/18
• US Class Current: 1/1
• 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 dynamically maintains and enforces relative policies for a prefix in a computer network. According to the novel technique, a node (e.g., an optimized edge router, OER) monitors performance characteristics for a particular prefix policy over a current path, and maintains a long-term average (LTA) value and a short-term average (STA) value of the performance characteristic. In the event the STA is worse than the LTA by a configurable amount, the prefix is considered “out-of-policy” (OOP) for that policy, and a new path may be selected accordingly. Otherwise, the prefix is considered “in-policy,” and the current path is upheld. Notably, a threshold may be manually configured to account for slow performance deterioration or “spikes,” such that if the performance characteristic (or STA) surpasses the threshold, the prefix is considered OOP.

Claims

1. A method for dynamically maintaining and enforcing relative policies for a prefix in a computer network, the method comprising:

monitoring, by a node of the computer network, a performance characteristic for a prefix over a current path, the prefix associated with a policy;

maintaining a long-term average (LTA) value of the performance characteristic;

maintaining a short-term average (STA) value of the performance characteristic;

comparing the LTA value to the STA value to determine if the STA value indicates a worse value than the LTA value by at least a configurable amount;

in the event the STA value indicates a worse value than the LTA value by at least the configurable amount, considering, by the node, the prefix to be out-of-policy (OOP) for the policy, wherein a prefix is a portion common to a plurality of addresses that is used by a routing protocol to render routing decisions;

in the event the prefix is considered to be OOP, determining whether a more optimal path exists than the current path; and

selecting the more optimal path as a new current path.

2. The method as in claim 1, wherein the more optimal path comprises a path which, when used by the prefix, is estimated to result in the prefix being in-policy.

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

in the event the STA value indicates a value not worse than the LTA value by at least the configurable amount, considering, by the node, the prefix in-policy for the prefix policy.

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

in the event the prefix is in-policy, continuing to use the current path.

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

configuring a threshold value, such that in the event the STA value surpasses the threshold value, the prefix is considered OOP by the node.

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

configuring a threshold value, such that in the event the performance characteristic surpasses the threshold value, the prefix is considered OOP by the node.

7. The method as in claim 1, wherein the configurable amount is configured from the group consisting of:

a percentage, and a fixed amount.

8. The method as in claim 1, wherein the STA value and LTA value are maintained as a rolling average.

9. The method as in claim 1, wherein the method is performed by an optimized edge router (OER).

10. A node for dynamically maintaining and enforcing relative policies for a prefix 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 an optimized edge routing (OER) process executable by the processor, the OER process configured to;

i) monitor a performance characteristic for a prefix over a current path, the prefix associated with a policy,

ii) maintain a long-term average (LTA) value of the performance characteristic,

iii) maintain a short-term average (STA) value of the performance characteristic,

iv) compare the LTA value to the STA value to determine if the STA value indicates a worse value than the LTA value by at least a configurable amount, and

v) in the event the STA value indicates a worse value than the LTA value by at least the configurable amount, consider the prefix to be out-of-policy (OOP) for the policy, wherein a prefix is a portion common to a plurality of addresses that is used by a routing protocol to render routing decisions;

vi) in the event the prefix is considered OOP, determine whether a more optimal path exists than the current path; and

vii) select the more optimal path as a new current path.

11. The node as in claim 10, wherein the more optimal path comprises a path which, when used by the prefix, is estimated to result in the prefix being in-policy.

12. The node as in claim 10, wherein the OER process is further configured to:

in the event the STA value indicates a value not worse than the LTA value by at least the configurable amount, consider the prefix in-policy for the prefix policy.

13. The node as in claim 12, wherein the OER process is further configured to:

in the event the prefix is in-policy, continue to use the current path.

14. The node as in claim 10, further comprising:

a threshold value stored in the memory, such that in the event the STA value surpasses the threshold value, the OER process is configured to consider the prefix OOP.

15. The node as in claim 10, further comprising:

a threshold value stored in the memory, such that in the event the performance characteristic surpasses the threshold value, the OER process is configured to consider the prefix OOP.

16. The node as in claim 10, wherein the configurable amount is configured from the group consisting of:

a percentage, and a fixed amount.

17. The node as in claim 10, wherein the STA value and LTA value are maintained as a rolling average.

18. The node as in claim 10, further comprising:

a table configured to store one or more prefix policies.

19. An apparatus for dynamically maintaining and enforcing relative policies for a prefix in a computer network, the apparatus comprising:

a processor; and

a computer-readable storage device having stored therein instructions which, when executed by the processor, cause the processor to perform operations comprising;

monitoring a performance characteristic for a prefix over a current path, the prefix associated with a policy;

maintaining a long-term average (LTA) value of the performance characteristic;

maintaining a short-term average (STA) value of the performance characteristic;

comparing the LTA value to the STA value to determine if the STA value indicates a worse value than the LTA value by at least a configurable amount;

considering the prefix to be out-of-policy (OOP) for the policy in the event the STA value indicates a worse value than the LTA value by at least the configurable amount, wherein a prefix is a portion common to a plurality of addresses that is used by a routing protocol to render routing decisions;

in the event the prefix is considered to be OOP, determining whether a more optimal path exists than the current path; and

selecting the more optimal path as a new current path.

20. The apparatus as in claim 19, the operations further comprising:

configuring a threshold value, such that in the event the STA value surpasses the threshold value, the prefix is considered OOP by the node.

21. The apparatus as in claim 19, the operations further comprising:

configuring a threshold value, such that in the event the performance characteristic surpasses the threshold value, the prefix is considered OOP by the node.

22. A non-transitory computer-readable storage medium having stored therein instructions which, when executed by a processor, cause the processor to perform operations comprising:

monitoring a performance characteristic, at a node of a computer network, for a prefix over a current path, the prefix associated with a policy;

maintaining a long-term average (LTA) value of the performance characteristic;

maintaining a short-term average (STA) value of the performance characteristic;

comparing the LTA value to the STA value to determine if the STA value indicates a worse value than the LTA value by at least a configurable amount;

in the event the STA value indicates a worse value than the LTA value by at least the configurable amount, considering at the node the prefix to be out-of-policy (OOP) for the policy, wherein a prefix is a portion common to a plurality of addresses that is used by a routing protocol to render routing decisions;

in the event the prefix is considered to be OOP, determining whether a more optimal path exists than the current path; and

selecting the more optimal path as a new current path.

23. The non-transitory computer-readable storage medium as in claim 22, the operations further comprising:

configuring a threshold value, such that in the event the STA value surpasses the threshold value, the prefix is considered OOP at the node.

24. The non-transitory computer-readable storage medium as in claim 22, the operations further comprising:

configuring a threshold value, such that in the event the performance characteristic surpasses the threshold value, the prefix is considered OOP at the node.

25. A method, comprising:

monitoring, by a node of a computer network, a performance characteristic for a prefix over a current path, the prefix associated with a policy;

maintaining a long-term average (LTA) value of the performance characteristic;

maintaining a short-term average (STA) value of the performance characteristic;

comparing the LTA value to the STA value, to determine if the STA value indicates a worse value than the LTA value by at least a configurable amount;

in response to the comparing indicating that the STA value indicates the worse value than the LTA value by at least the configurable amount, considering, by the node, the prefix to be out-of-policy (OOP) for the policy;

in response to the prefix being considered to be OOP, identifying a new path exists having a better performance characteristic than the current path used with the prefix; and

selecting the new path as a new current path, wherein the prefix comprises a portion common to a plurality of addresses that is used by a routing protocol to render routing decisions.

26. The method as in claim 25, further comprising:

when the STA value does not indicate the worse value than LTA value by at least the configurable amount, considering, by the node, the prefix to be in-policy for the policy; and

in response to the prefix being considered to be in-policy, continuing to use the current path.

27. The method as in claim 25, further comprising:

configuring a threshold value, wherein, in the event the STA value of the performance characteristic for the prefix surpasses the threshold value, the prefix is considered to be OOP by the node.

28. The method as in claim 25, further comprising:

configuring a threshold value, wherein, in the event the performance characteristic for the the prefix surpasses the threshold value, the prefix is considered to be OOP by the node.

29. The method as in claim 25, wherein the configurable amount is selected from the group consisting of:

a percentage, and a fixed amount.