Link policy routing based on link utilization

• US 9,722,928 B2
• Filed: 04/05/2012
• Issued: 08/01/2017
• 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: Patel, Rahul G., Blair, Dana
• Primary Examiner(s): Mills, Donald
• Assistant Examiner(s): Baron, Henry
• Application Number:
  US13/440,712
• Publication Number:
  US 20120195204A1
• Time in Patent Office: 1,944 Days
• Field of Search: 370229, 370235, 370237, 370359
• 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

In one embodiment, a link utilization threshold is assigned to a first link. Link utilization of the first link and of one or more second links is monitored. The first link is considered to be out-of-policy (OOP) in the event that the link utilization of the first link surpasses the link utilization threshold. In response to the first link being considered OOP, action is taken. An excess utilization of the first link is determined. One or more prefixes currently routed over the first link whose collective per prefix utilization exceeds the excess utilization are determined. Provided that the collective per prefix utilization of the one or more prefixes currently routed over the first link, if added to the link utilization of the one or more second links, would not cause the one or more second links to be considered OOP, the one or more prefixes are redirected over them.

Claims

1. A method comprising:

calculating, by a processor, a first link utilization of a first link and a second link utilization of one or more second links, wherein the first link utilization is calculated based on first traffic associated with a plurality of first prefixes routed through the first link, and wherein the second link utilization is calculated based on second traffic associated with one or more second prefixes routed through the one or more second links;

determining that the second link utilization is lower than a second link utilization threshold associated with the one or more second links;

determining that the first link is out-of-policy (OOP) with respect to a first link policy when the first link utilization surpasses a first link utilization threshold of the first link;

determining an overall excess utilization of the first link, the overall excess utilization corresponding to a difference between the first link utilization and the first link utilization threshold;

receiving a configurable utilization amount such that the first link is in-policy with respect to the first link policy when the first link utilization is lower than the first link utilization threshold and the configurable utilization amount;

identifying a subset of prefixes, from the plurality of first prefixes routed through the first link, having a total utilization that is;

greater than the overall excess utilization of the first link and the configurable utilization amount; and

lower than the second link utilization threshold associated with the one or more second links; and

redirecting the subset of prefixes through the one or more second links.

2. The method of claim 1, further comprising:

determining that the subset of prefixes is reachable by the one or more second links.

3. The method of claim 1, wherein each of the subset of prefixes are redirected over a particular link of the one or more second links, and wherein each of the plurality of first prefixes is obtained by applying a respective subnet mask to a respective network address.

4. The method of claim 1, wherein the first link utilization threshold is a percentage of total capacity.

5. The method of claim 1, wherein the first link utilization threshold of the first link differs from the second link utilization threshold of the one or more second links.

6. The method of claim 1, wherein the first link utilization threshold is a relative threshold with respect to one or more other links.

7. The method of claim 1, wherein the first link and the one or more second links are load balanced links, and the subset of prefixes are redirected through the one or more second links to load balance the first traffic routed through the first link and the second traffic routed through the one or more second links.

8. The method of claim 1, wherein at least one of the first link or the second link comprises a virtual link.

9. The method of claim 1, further comprising:

determining that the first link is OOP with respect to a second link policy when the first link utilization exceeds a maximum difference between the first link utilization threshold and the second link utilization threshold.

10. An apparatus comprising:

a processor; and

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

calculating a first link utilization of a first link and a second link utilization of one or more second links, wherein the first link utilization is calculated based on first traffic associated with a plurality of first prefixes routed through the first link, and wherein the second link utilization is calculated based on second traffic associated with one or more second prefixes routed through the one or more second links;

determining that the second link utilization is lower than a second link utilization threshold associated with the one or more second links;

determining that the first link is out-of-policy (OOP) with respect to a first link policy when the first link utilization of the first link surpasses a first link utilization threshold;

determining an overall excess utilization of the first link, the overall excess utilization corresponding to a difference between the first link utilization and the first link utilization threshold;

receiving a configurable utilization amount such that the first link is in-policy with respect to the first link policy when the first link utilization is lower than the first link utilization threshold and the configurable utilization amount;

identifying a subset of prefixes, from the plurality of first prefixes routed through the first link, having a total utilization that is;

greater than the overall excess utilization of the first link and the configurable utilization amount; and

lower than the second link utilization threshold associated with the one or more second links; and

redirecting the subset of prefixes over the one or more second links.

11. The apparatus of claim 10, wherein each of the subset of prefixes is obtained by applying a respective subnet mask to a respective network address.

12. The apparatus of claim 11, wherein the computer-readable storage medium stores additional instructions which, when executed by the processor, cause the processor to perform operations comprising:

determining that the subset of prefixes is reachable by the one or more second links.

13. The apparatus of claim 11, wherein each of the subset of prefixes is routed over only one link of the one or more second links.

14. The apparatus of claim 10, wherein the first link utilization threshold is a percentage of total capacity.

15. The apparatus of claim 10, wherein the first link utilization threshold of the first link differs from the second link utilization threshold of the one or more second links.

16. The apparatus of claim 10, wherein the first link utilization threshold is a relative threshold with respect to one or more other links.

17. The apparatus of claim 10, wherein the first link and the one or more second links are load balanced links, and wherein the first link utilization threshold and the second link utilization threshold are relative to each other based on a load balancing scheme.

18. The apparatus of claim 10, wherein the first link is a virtual link.

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

determining a first link utilization of a first link and a second link utilization of one or more second links, wherein the first link utilization is calculated based on first traffic associated with a plurality of first prefixes routed through the first link, and wherein the second link utilization is calculated based on second traffic associated with one or more second prefixes routed through the one or more second links;

determining that the second link utilization is lower than a second link utilization threshold associated with the one or more second links;

determining that the first link is out-of-policy (OOP) with respect to a first link policy when the first link utilization surpasses a first link utilization threshold of the first link;

determining an overall excess utilization of the first link, the overall excess utilization corresponding to a difference between the first link utilization and the first link utilization threshold;

receiving a configurable utilization amount such that the first link is in-policy with respect to the first link policy when the first link utilization is lower than the first link utilization threshold and the configurable utilization amount;

identifying a subset of prefixes, from the plurality of first prefixes routed through the first link, having a total utilization that is;

greater than the overall excess utilization of the first link and the configurable utilization amount; and

lower than the second link utilization threshold associated with the one or more second links; and

redirecting the subset of prefixes over to the one or more second links.