Controlled incremental multi-protocol label switching (MPLS) traffic engineering
View Patent ↗An existing network configuration is assessed, and potential changes to the existing configuration are identified that provide the greatest incremental improvements to the performance of the network. In a preferred embodiment, the user of the system identifies the maximum number (N) of changes that may be implemented in an existing network, and the system provides a set of possible reconfigurations, each requiring fewer than N changes. The user is presented a display of the potential improvement provided by each set as a function of the number of changes in the set, so that the relative incremental gain can be easily visualized. The objective function of the optimization may include conventional load-balancing objectives, or other objectives, such as a global minimization of path lengths.
1. A method comprising:
obtaining, at a network analysis system:
a model of a network that includes links between nodes of the network,
a current configuration of the network that includes a plurality of virtual circuits,
one or more constraints related to the virtual circuits, and
one or more objectives relative to optimizing the virtual circuits;
selectively unrouting a plurality of selected routes associated with one or more of the virtual circuits, the plurality of routes being substantially fewer than a totality of the routes associated with the plurality of virtual circuits;
rerouting, by the network analysis system, the plurality of the routes to produce a modified set of virtual circuits;
evaluating the modified set based on the one or more objectives, subject to the one or more constraints;
repeating the selective unrouting, rerouting, and evaluating to provide a plurality of modified sets of virtual circuits;
selecting, by the network analysis system, one or more preferred modified sets for presentation to a user based on an evaluation of each of the plurality of modified sets; and
presenting, by the network analysis system, a measure based on the evaluation of each of the preferred modified sets as a function of a number of changes in the set relative to the current configuration of the network.
2. The method of claim 1 , wherein the plurality of selected routes are selected based on a random process.
3. The method of claim 1 , wherein the number of changes in each set includes at least one of:
a number of circuits changed,
a number of routes changed, and
a number of devices whose configuration must be changed.
4. The method of claim 1 , wherein each of the one or more preferred modified sets of virtual circuits includes a number of changes relative to the current configuration of the network, and
the selecting of the one or more preferred modified sets is based on the number of changes in each of the sets.
5. The method of claim 4 , including setting an upper limit to the number of changes in each modified set of virtual circuits.
6. The method of claim 1 , wherein the plurality of virtual circuits include explicitly defined virtual circuits and dynamically defined virtual circuits.
7. The method of claim 1 , including:
selectively unrouting one or more of the routes based on a heuristic process; and
rerouting the one or more routes to produce a first modified set of virtual circuits.
8. The method of claim 7 , wherein the heuristic process includes identifying routes to be unrouted based on the virtual circuits routed over an oversubscribed link and a total number of oversubscribed links traversed by the route.
9. The method of claim 8 , wherein the heuristic process includes identifying routes to be unrouted based on the paths routed over an oversubscribed link and a product of the total number of oversubscribed links traversed by the route and a subscription bandwidth associated with the route.
10. The method of claim 7 , wherein the heuristic process includes identifying routes to be unrouted based on a failure of the route to satisfy one or more of the constraints.
11. The method of claim 1 , wherein the objective includes a minimization of a maximum link subscription.
12. The method of claim 1 , wherein the objective includes a minimization of a total amount of subscribed bandwidth.
13. The method of claim 1 , wherein the selective unrouting and evaluating are based on a method of simulated annealing.
14. The method of claim 1 , wherein the selective unrouting and evaluating are based on a genetic/evolutionary algorithm.
15. The method of claim 1 , including:
receiving a selection of a chosen set from the one or more preferred modified sets, and
providing one or more reports that are configured to contrast a new configuration based on the chosen set from the current configuration.
16. A system comprising:
an path optimizer that is configured to:
receive:
a model of a network that includes links between nodes of the network,
a current configuration of the network that includes a plurality of virtual circuits,
one or more constraints related to the virtual circuits, and
one or more objectives relative to optimizing the virtual circuits;
selectively unroute a plurality of selected routes associated with one or more of the virtual circuits, the plurality of routes being substantially fewer than a totality of the routes associated with the plurality of virtual circuits;
a router that is configured to reroute the plurality of the routes to produce a modified set of virtual circuits; and
a report generator;
wherein
the path optimizer is further configured to:
evaluate the modified set based on the one or more objectives, subject to the one or more constraints; and
repeat the selective unrouting, rerouting, and evaluating to provide a plurality of modified sets of virtual circuits; and
select one or more preferred modified sets of the plurality of modified sets for presentation to the user, based on an evaluation of each of the plurality of modified sets; and
the report generator is configured to present a measure based on the evaluation of each of the preferred modified sets as a function of the number of changes in the set relative to the current configuration.
17. The system of claim 16 , including a random search engine that is configured to select the plurality of selected routes.
18. The system of claim 16 , wherein the number of changes in each set includes at least one of:
a number of circuits changed,
a number of routes changed, and
a number of devices whose configuration must be changed.
19. The system of claim 16 , wherein each of the one or more preferred modified sets of virtual circuits includes a number of changes relative to the current configuration of the network, and
the path optimizer is configured to select the one or more preferred modified sets based on the number of changes in each of the sets.
20. The system of claim 19 , wherein the path optimizer is configured to set an upper limit to the number of changes in each modified set of virtual circuits.
21. The system of claim 16 , wherein the plurality of virtual circuits include explicitly defined virtual circuits and dynamically defined virtual circuits.
22. The system of claim 16 , wherein the path optimizer is configured to selectively unroute one or more of the routes based on a heuristic process.
23. The system of claim 22 , wherein the heuristic process includes identifying routes to be unrouted based on the virtual circuits routed over an oversubscribed link and a total number of oversubscribed links traversed by the route.
24. The system of claim 23 , wherein the heuristic process includes identifying routes to be unrouted based on the paths routed over an oversubscribed link and a product of the total number of oversubscribed links traversed by the route and a subscription bandwidth associated with the route.
25. The system of claim 22 , wherein the heuristic process includes identifying routes to be unrouted based on a failure of the route to satisfy one or more of the constraints.
26. The system of claim 16 , wherein the objective includes a minimization of a maximum link subscription.
27. The system of claim 16 , wherein the objective includes a minimization of a total amount of subscribed bandwidth.
28. The system of claim 16 , wherein the selective unrouting and evaluating are based on a method of simulated annealing.
29. The system of claim 16 , wherein the selective unrouting and evaluating are based on a genetic/evolutionary algorithm.
30. The system of claim 16 , including a user interface that is configured to:
receive a selection of a chosen set from the one or more preferred modified sets, and
provide one or more reports that are configured to contrast a new configuration based on the chosen set from the current configuration.
31. A non-transitory computer readable storage medium that includes a computer program that, when executed by a processing system, causes the processing system to:
receive:
a model of a network that includes links between nodes of the network,
a current configuration of the network that includes a plurality of virtual circuits,
one or more constraints related to the virtual circuits, and
one or more objectives relative to optimizing the virtual circuits;
selectively unroute a plurality of selected routes associated with one or more of the virtual circuits, the plurality of routes being substantially fewer than a totality of the routes associated with the plurality of virtual circuits; and
reroute the plurality of the routes to produce a modified set of virtual circuits;
evaluate the modified set based on the one or more objectives, subject to the one or more constraints; and
repeat the selective unrouting, rerouting, and evaluating to provide a plurality of modified sets of virtual circuits;
select one or more preferred modified sets of the plurality of modified sets, based on an evaluation of each of the plurality of modified sets; and
present a measure based on the evaluation of each of the preferred modified sets as a function of the number of changes in the set relative to the current configuration.