METRIC OPTIMIZATION FOR TRAFFIC ENGINEERING IN A METRIC-ROUTED NETWORK

• US 20080123534A1
• Filed: 01/31/2008
• Published: 05/29/2008
• Est. Priority Date: 10/18/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cariden Technologies, Inc. (Cisco Systems, Inc.)
• Inventors: Gous, Alan Thornton
• Granted Patent: US 7,782,773 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/083 for increasing network speed
• CPC Class Codes: H04L 41/0836 to enhance reliability, e.g. reduce downtime
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/06 Generation of reports
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A method is performed to optimize metrics associated with links of a network that is routed utilizing a shortest-path-first (SPF) routing method. The method includes identifying at least one failure scenario applicable to the network and identifying at least one bandwidth level scenario applicable to point-to-point demands routed through the network. A metric is automatically calculated for each of a plurality of links of a network, such that routings of demands through the network are optimized for the at least one failure scenario, and for the at least one bandwidth level.

Claims

1. A system to optimize metrics associated with links of a network that is routed utilizing a shortest-path-first (SPF) routing method, the system including:

a metric traffic engineering module to identify at least one failure scenario applicable to the network, to identify at least one bandwidth level scenarios applicable to point-to-point demands routed through the network, and automatically to calculate a metric for each of a plurality of links of a network, such that routings of demands through the network are optimized into the at least one failure scenarios and in the at least one bandwidth level scenarios; and

a changeover module, coupled to the metric traffic engineering module, to signal network configuration changes to a network controller in accordance with the calculated metric for each of the plurality of links of the network.

2. A method to optimize metrics associated with links of a network that is routed utilizing a shortest-path-first (SPF) routing method, the method including:

identifying at least one failure scenario applicable to the network;

identifying at least one bandwidth level scenario applicable to point-to-point demands routed through the network; and

automatically calculating a metric for each of a plurality of links of a network, such that routings of demands through the network are optimized for the at least one failure scenario, and for the at least one bandwidth level.

3. The method of claim 2, including identifying a plurality of failure scenarios and a plurality of bandwidth level scenarios applicable to the network, and automatically calculating the metric for each of the plurality of links of the network such that the link utilizations resulting from demand routings determined by the metrics are below a predetermined threshold for each of the plurality of links of the network, for each of the plurality of failure scenarios, and for each of the plurality of bandwidth level scenarios.

4. The method of claim 3, wherein the automatic calculation is to calculate the metric for each of the plurality of links of the network such that the maximum link utilization, for each of the plurality of links, is minimized, the maximum link utilization being over the plurality of links, the plurality of failure scenarios, and the plurality of bandwidth level scenarios, and the minimization being performed over all possible choices of link metrics.

5. The method of claim 2, wherein the at least one failure scenario is as a result of a voluntary action taken by a network operator to disable at least a portion of the network.

6. The method of claim 2, including applying the metric calculated for each of the plurality of links in the shortest-path-first routing method so as to route traffic within the network according to the calculated metrics.

7. The method of claim 2, including communicating the maximum link utilizations, over the at least one failure scenario and the at least one bandwidth level scenarios, which result from an application of the automatically calculated metrics, for at least one link, to a user.

8. The method of claim 7, wherein the communication of the maximum link utilizations includes indicating whether at least one maximum link utilization exceeds a predetermined threshold link utilization.

9. The method of claim 7, wherein the communication of the maximum link utilizations includes generating a user interface in which at least one maximum link utilization is visually indicated.

10. The method of claim 2, including storing the calculated metrics within the network so that the network is routed, utilizing the shortest-path-first routing method, according to the stored metrics.

11. The method of claim 2, including identifying the plurality of links of the network for which respective metrics are calculated as being core links of the network.

12. The method of claim 11, wherein sets of point-to-point demands are identified that follow a common routing through a core of the network for any choice of metrics of the core links, and demands are aggregated together and treated as a single demand in the automatic calculation.

13. A system to migrate a shortest-path-first (SPF) routed network from a first routing state to a second routing state, the system including:

a changeover module to generate a sequence of intermediate network plans, each of which modifies a preceding network state according to a preceding network plan such that a routing of at least one demand in the network changes, the sequence of intermediate network plans to migrate the network from the first routing state to the second routing state; and

a network controller sequentially to configure the network according to the sequence of intermediate network plans to migrate the network from the first routing state to the second routing state,

wherein each intermediate network plan of the sequence configures the network to operate within at least one predetermined constraint.

14. A method to migrate a shortest-path-first (SPF) routed network from a first network plans, which associates a first set of metrics with links of the network, to a second network plan, which associates a second set of metrics with links of the network, the method including:

generating a sequence of intermediate network plans, each of which modifies a preceding network state according to a preceding network plan such that a routing of at least one demand in the network changes, the sequence of intermediate network plans to migrate the network from a first routing state in accordance with the first network plan to a second routing state in accordance the second network plan; and

sequentially configuring the network according to the sequence of intermediate network plans to migrate the network from the first routing state to the second routing state,

wherein each intermediate network plan of the sequence configures the network to operate within at least one predetermined constraint.

15. The method of claim 14, wherein the predetermine constraint is that a convergence time between the preceding network state and a resulting network state is less than a predetermined maximum time.

16. The method of claim 14, wherein the at least one predetermined constraint is a maximum percentage increase of a bandwidth demand without exceeding a predetermined capacity of at least one link of the network.

17. The method of claim 14, wherein the at least one predetermined constraint is a maximum demand latency associated with a point-to-point demand within the network.

18. The method of claim 17, wherein the maximum demand latency is specified as a percentage increase over an existing demand latency associated with the point-to-point demand.

19. The method of claim 14, wherein the at least one predetermined constraint is a maximum link bandwidth utilization for at least one link of the network, wherein the maximum link bandwidth utilization is over at least one failure scenario of the network.

20. The method of claim 14, wherein the at least one predetermined constraint is a minimum quality of service to be provided on the network.

21. The method of claim 14, wherein the at least one predetermined constraint is a maximum link bandwidth utilization over a plurality of failure scenarios.

22. The method of claim 14, wherein the generation of the sequence of intermediate network plans includes defining a tree of network routing states, the tree having the first routing a state as a root, and identifying a path in the tree from the root to the second network routing state such that a respective network state that each node in the path configures the network to operate within the at least one predetermined constraint.

23. The method of claim 14, wherein the generation of the sequence of intermediate network plans includes determining that a first sequence of intermediate network plans exceeds a first constraint, and then modifying the first constraint to generate the at least one predetermined constraint according to which the sequence of intermediate network plans are generated.

24. The method of claim 14, wherein a specific intermediate network plan of the sequence of intermediate network plan differs in that only a single metric from a preceding intermediate network plan.

25. The method of claim 14, wherein a specific intermediate network plan of the sequence of intermediate network plan differs in at least one metric from a preceding intermediate network plan.

26. The method of claim 14, wherein a specific intermediate network plan of the sequence differs from a preceding intermediate network plan in that a state of at least one link of the network differs from a preceding state specified by the preceding intermediate network plan.

27. The method of claim 26, wherein the state is an active state and the preceding state is an inactive state, or vice versa.

28. The method of claim 14, including identifying a first set links, and wherein the first intermediate network plan of the sequence differs from the preceding intermediate network plan in that the state of each link within the first set differs from a preceding state specified by the preceding intermediate network plan.

29. The method of claim 14, wherein the sequential configuration of the network includes sequentially communicating each of the sequence of intermediate network plans from a changeover sequence module to a network controller, wherein the changeover sequence module receives an acknowledgment from the network controller that a specific intermediate network plan has been configured prior to communicating a subsequent intermediate network plan.

30. A method to optimize routing within a shortest-path-first routed network, the method including:

estimating bandwidth demand within the network;

utilizing the estimated bandwidth demand, determining bandwidth utilizations within the network in a current state;

performing an optimization of metrics associated with links of the network, to thereby identify a desired state for the network within which bandwidth utilizations are reduced within the network relative to the current state; and

generating a changeover sequence to migrate the network from the current state to the desired state.