FreshPatents.com Logo
stats FreshPatents Stats
2 views for this patent on FreshPatents.com
2012: 2 views
Updated: July 25 2014
newTOP 200 Companies filing patents this week


    Free Services  

  • MONITOR KEYWORDS
  • Enter keywords & we'll notify you when a new patent matches your request (weekly update).

  • ORGANIZER
  • Save & organize patents so you can view them later.

  • RSS rss
  • Create custom RSS feeds. Track keywords without receiving email.

  • ARCHIVE
  • View the last few months of your Keyword emails.

  • COMPANY DIRECTORY
  • Patents sorted by company.

Follow us on Twitter
twitter icon@FreshPatents

Tuning routing metrics to reduce maximum link utilization and/or provide failure resiliency

last patentdownload pdfdownload imgimage previewnext patent


20120287780 patent thumbnailZoom

Tuning routing metrics to reduce maximum link utilization and/or provide failure resiliency


A metric tuning technique optimizes the maximum link utilization of a set of links incrementally. Changes to the metric are constrained to be metric increases to divert routes from select links, thereby minimizing the number of changes required to achieve the optimization by avoiding the potential cascade of changes caused by attracting routes to a link. An interactive user interface is provided to allow a user to specify limits and constraints, and to select the sets of links to be addressed, including, for example, only the links that exceed a given link utilization threshold, the links having the highest link utilizations, the links having the highest failure effect, and so on. This incremental optimization technique is also used to optimize network resiliency by minimizing the network degradation caused by the failure of one or more links.

Inventors: Bobby Ninan, Gordon M. Bolt, Olivier Goldschmidt
USPTO Applicaton #: #20120287780 - Class: 370228 (USPTO) - 11/15/12 - Class 370 
Multiplex Communications > Fault Recovery >Bypass An Inoperative Channel >Spare Channel

view organizer monitor keywords


The Patent Description & Claims data below is from USPTO Patent Application 20120287780, Tuning routing metrics to reduce maximum link utilization and/or provide failure resiliency.

last patentpdficondownload pdfimage previewnext patent

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 12/143,799, entitled “TUNING ROUTING METRICS TO REDUCE MAXIMUM LINK UTILIZATION AND/IR OR PROVIDE FAILURE RESILIENCY,” filed Jun. 22, 2008, which claims the benefit of U.S. Provisional Patent Applications 60/950,574, filed 18 Jul. 2007, and 61/022,563, filed 22 Jan. 2008

BACKGROUND

This invention relates to the field of network engineering and analysis, and in particular to a method and system for managing traffic flow in a network for efficient link utilization and resilient performance under failure conditions.

Routing algorithms are generally structured to select a route for traffic between nodes of a network based on the relative ‘cost’ associated with each potentially available route. For example, an Interior Gateway Protocol (IGP) is commonly used on Internet Protocol (IP) networks to determine the optimal route from a source node to a destination node based on a total cost of each available route, using one or more metrics for determining such costs. Example Interior Gateway Protocols include Routing Information Protocol (RIP), Open Shortest Path First (OSPF), and Intermediate System to Intermediate System (IS-IS) protocols.

Typically, when a link is added to a network, the metric is assigned at the interface to the link, reflecting the relative cost/impact of using the link. For example, if the link is a high capacity link, the relative impact of sending a packet over the link is generally slight, compared to the impact of sending that same packet over a link with very limited capacity. By assigning low costs to high capacity links, and high costs to low capacity links, more traffic will generally be routed by such cost/metric based routing algorithms to the high capacity links, thereby avoiding congestion on the low capacity links.

FIG. 1A illustrates an example network with links A-V between nodes of the network. FIG. 1B illustrates an example set of metrics associated with each link A-V, and FIG. 1C illustrates an example set of routes and composite metrics associated with each. In this example, only four traffic flow demands are presented for consideration, from San Francisco 110 to each of: New York 120 (SF-NY, 60 Mb/s), Chicago 130 (SF-CH, 40 Mb/s), Atlanta 140 (SF-AT, 40 Mb/s), and Houston 150 (SF-HO, 20 Mb/s). The composite metric for the routes is determined in this example as the sum of the metrics of the links along the route; other techniques for determining a composite metric based on link metrics may also be used, such as a composite that is based on the metric of each link and the number of links (hops) along the route.

In FIG. 1C, five sample routes are illustrated for the traffic from SF 110 to NY 120. The first route, using links D (SF to AT), L (AT to DC), and Q (DC to NY), has a composite metric of 58 (44+8+6); the second route, A-E, has a composite metric of 50 (10+40), the third route, A-F-N-O, has a composite metric of 42 (10+16+4+12), and so on. Based on these composite metrics, the 60 Mb/s traffic from SF to NY is preferably routed along the route A-F-N-O, the route with the lowest composite metric. In like manner, the 40 Mb/s traffic from SF to CH is preferably routed along A-F-N; the 20 Mb/s traffic from SF to HO along route A-C; and the 40 Mb/s traffic from SF to AT along route A-F-H.

It is significant to note that in this example, each of the preferred routes include the link A. Therefore all of the traffic from SF to NY, CH, HO, and AT will travel over link A. With the routing in this example, link A will have 160 Mb/s of load. Whether or not link A can efficiently handle this load is based on the capacity of link A. If link A\'s capacity is 320 Mb/s, for example, its utilization is 50%; if link A\'s capacity is under 160 Mb/s, link A is over-utilized, and the traffic demand will not be satisfied. Network managers strive to avoid over-utilized links, and try to minimize the link utilization on each of the links to assure efficient traffic flow across the network.

Traffic engineering addresses techniques for optimizing network performance, including the configuration of resources of a network to provide effective and efficient traffic flow through the network. In “Internet Traffic Engineering by Optimizing OSPF weights” at IEEE INFOCOM 2000, B. Fortz and M. Thorup presented the concept of adjusting the metrics assigned to links from their initially assigned values so as to cause devices that use an existing routing protocol (OSPF) to select different routes than those selected based on the default metric values, to achieve an overall desired traffic flow through the network. Extensions for dealing with varying traffic and transient link failures were proposed by Fortz et al. (B. Fortz and M. Thorup. “Optimizing OSPF/IS-IS weights in a changing world”, IEEE JSAC 2001) and Nucci et al. (Nucci et al. “IGP link weight assignment for transient link failures”, ITC 2003) respectively. Currently in the commercial arena, Cariden Technologies (www.cariden.com) and WANDL (www.wandl.com) have competing solutions for IGP metric optimization.

Techniques that provide for global optimization of networks are well suited for an initial installation of a network, and for ongoing management of small networks, but are generally poorly suited for routine ongoing maintenance of large networks. Often, relatively minor changes to a network can have a major effect on determining the optimal solution in a large network, due to the cascading of change effects. For example, a relatively minor reduction in a link\'s metric may ‘attract’ a large number of routes that previously had relatively equivalent costs, and other metrics may need to be adjusted to subsequently attract some of the traffic from this now-overloaded link. That is, a minor improvement in network performance may require a substantial number of individual metric changes, as the conventional processes strive to tune the network for truly optimal performance.

It would be advantageous to provide improvements to network performance in an incremental manner, preferably with minimal changes to the configuration of devices in the network. It would also be advantageous to identify and address the links that are in violation of a maximum link utilization threshold, as well as the links whose failure will introduce a significant number of threshold violations.

These advantages, and others, can be realized by a metric tuning technique that optimizes the maximum link utilization of a set of links incrementally. Changes to the metric are constrained to be metric increases to divert routes from select links, thereby minimizing the number of changes required to achieve the optimization by avoiding the potential cascade of changes caused by attracting routes to a link. An interactive user interface is provided to allow a user to specify limits and constraints, and to select the sets of links to be addressed, including, for example, only the links that exceed a given link utilization threshold, the links having the highest link utilizations, the links having the highest failure effect, and so on. This incremental optimization technique is also used to optimize network resiliency by minimizing the network degradation caused by the failure of one or more links.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention is explained in further detail, and by way of example, with reference to the accompanying drawings wherein:

FIGS. 1A-1D illustrate an example network, routing metrics, routes, and traffic load as a function of the metric for an example link;

FIG. 2 illustrates an example flow diagram for iteratively improving network performance in accordance with an aspect of this invention;

FIG. 3 illustrates an example flow diagram for iteratively improving network resiliency in accordance with an aspect of this invention; and

FIG. 4 illustrates an example block diagram of a traffic engineering system in accordance with this invention.

Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.

DETAILED DESCRIPTION

In the following description, for purposes of explanation rather than limitation, specific details are set forth such as the particular architecture, interfaces, techniques, etc., in order to provide a thorough understanding of the concepts of the invention. However, it will be apparent to those skilled in the art that the present invention may be practiced in other embodiments, which depart from these specific details. In like manner, the text of this description is directed to the example embodiments as illustrated in the Figures, and is not intended to limit the claimed invention beyond the limits expressly included in the claims. For purposes of simplicity and clarity, detailed descriptions of well-known devices, circuits, and methods are omitted so as not to obscure the description of the present invention with unnecessary detail.

FIG. 1A illustrates an example network.

The flow diagram of FIG. 2 provides an overview of a first aspect of this invention; additional features and alternatives are presented further on.

At 210, the network and traffic characteristics are obtained. These characteristics include, for example, the network topology and the traffic matrix. The network topology includes an identification of each of the links of the network, and their characteristics, such as the routing protocol used at the interfaces to the links. The traffic characteristics identify the amount of traffic flowing between nodes of the network. Other parameters and characteristics may also be obtained, as required for subsequent processes.

At 215, the network is assessed to determine the existing metrics that are used for creating routes on this network. Generally, the particular routing protocol is predefined, and may include, for example, Open Shortest Path First (OSPF), and Intermediate System to Intermediate System (IS-IS) protocols. As discussed subsequently, the particular routing protocol used at each interface to each link is used in the system of this invention to determine resultant routes as the metrics are changed. For comparative consistency, the system is also preferably used to determine the routes corresponding to the existing metrics. Optionally, some or all of the metrics of the network can be initialized to default or particularly defined values, to allow the system to start from a preferred baseline configuration.

At 220, the links that are to be targeted for optimization are identified. For ease of reference and understanding, two sets of links are defined herein, target links and candidate links. Target links are the links for which the performance of the network is evaluated and potentially improved. Candidate links are the links that are available for change. Generally, these sets of links are the same, but in some cases, are preferably different. For example, a user may specify links that may not be changed, or that may only be changed in a particular manner. Often, such links are on ‘sensitive’ routes, such as routes for particularly important customers, routes that have been optimized for a particular purpose, and so on. Although, for example, the metric associated with the links along a sensitive route may be specified to remain the same, thereby maintaining the existing route, these links would generally be included in the determination of the measure of overall system performance, because a metric change at another link might either reduce or increase the utilization of the targeted link. In like manner, the optimization may be targeted to cure known problems on particular links, and changes to any link that is not barred from change would be a candidate for change consideration.

Any of a variety of techniques may be used to identify the set of target links, ranging, for example, from having a user explicitly identify each link, to performing an exhaustive assessment of all links. Generally, the user identifies any links that are known to be problematic, or instructs the system to assess the “N” links with the highest link utilization, or instructs the system to assess any link that violates one or more constraints, and so on. In addition to such ‘targeted’ assessments, the system may also be configured to select random target links for assessment, to determine if improvements can be achieved.

At 225, a measure of network performance is determined with regard to the targeted links. Any of a variety of network performance measures may be used to assess the effectiveness of the current routing over these links. In an example embodiment of this invention, link utilization is used as a measure of effectiveness, and the peak link utilization among the targeted links is used as a network performance measure. In like manner, a threshold value of link utilization can be specified, and the number of targeted links that exceed this threshold value can be used as the network performance measure. Other statistics based on link utilization, such as average, mean, variance, and so on, may also be used. Other parameters may also be used, such as throughput, delay, number of links/hops per path, and so on. Preferably, a network performance measure that is easy to determine is preferred, to facilitate rapid iterative performance determinations.

The measure of network performance is typically a combination of individual performance measures. For example, the measure may be dependent upon the peak link utilization as well as other measures, such as the average link utilization, the number of link utilizations that exceed a threshold limit, and so on.

At 230, the constraints that are to be applied to the optimization are specified. In a typical embodiment, the constraints include both operational and parametric constraints. Operational constraints may include, for example, an identification of links that should not be modified, high priority links, and so on, while parametric constraints may include, for example, limits imposed on system or network parameters, such as link utilization, the possible values for the metric, the number of links exceeding a given threshold, the number of demands using each link, and so on.

At 235, the set of change candidates is determined. In one embodiment, any link whose metric is not explicitly prohibited from change can be identified as a candidate link. In many cases, the set of candidate links is determined based on the constraints specified above. For example, the set of change candidates might include only those links whose utilization is above 80%.

The loop 240-280 selects a candidate link from the set of change candidates and determines whether an improvement in the measure of system performance can be achieved by modifying the metric that characterizes this link to the routing protocol. Preferably, candidate links are selected in decreasing order based on utilization, but other selection criteria could also be used. Although the process 240-280 is illustrated as a sequential, one link after another, process, for ease of illustration and understanding, one of skill in the art will recognize that the system can be configured to identify improvements to the system performance based on multiple modifications to a select set of links.

At 245, the candidate link is assessed to determine a change to the value of its metric that causes a desired change to the original routing. Not all changes to the metric will cause a change in routing, and not all changes in routing will produce a decrease in utilization on the candidate link. The routing protocols generally use the assigned metric to compare alternative routes for a given traffic flow between nodes. If the candidate link provides the only path for a particular traffic flow, the routing of that path will always include this link, regardless of the value of the metric, because there is no alternative link for this segment of the path. In like manner, if the metric for this link is substantially different from any of the other links, small changes to the metric will not affect the routing based on a comparison of these metrics. Only when the metric is comparatively similar to another metric will a change to the metric have a potential effect on the choice of routes for the particular traffic flow.

In FIG. 1D, the load across link A is illustrated as a function of link A\'s metric. FIG. 1B identifies that the metric of link A has a metric value of 10. Based on this metric, each of the four traffic demands (SF-NY, SF-CH, SF-AT, SF-HO) are preferably routed along link A, amounting to 160 Mb/s, as discussed above. If link A\'s metric is increased to 11, there will be no change, because the composite metric for each preferred route A-F-N-O (43), A-F-N (31), A-F-H (37), and A-C (35) based on this metric will still be the lowest among the alternative routes for each demand.

If link A\'s metric is 14, the composite metric for route A-C (14+24)) will be equal to the composite metric for route B (38) for the demand SF-HO. In that case, the 20 Mb/s demand from SF to HO will be shared equally by route B and route A-C, reducing the load on link A to 150 Mb/s (160−(20/2)), as illustrated at 160 in FIG. 1D. If link A\'s metric is 15, the composite metric for route A-C (15) will be larger than the metric for route B (14), and thus route B will be the preferred route, removing all of the 20 Mb/s demand from SF to HO from link A, as illustrated at 165 of FIG. 1D.

If link A\'s metric is 18, the composite metric for route A-F-H (18+16+10) will equal the composite metric for route D (44) for the demand SF-AT, and half of the 40 Mb/s demand will be shared between route D and route A-F-H, removing another 20 Mb/s from the demand on link A, as illustrated at 170. If link A\'s metric is 19, route D will be preferred for this demand, and the entire 40 Mb/s demand from SF to AT will be removed from link A, as illustrated at 175.

Similarly, if link A\'s metric is 20, the 50 Mb/s demand from SF to NY will be shared between route A-F-N-O and route R-K-N-O, and the 40 Mb/s demand from SF to CH will be shared between route A-F-N and R-K-N, reducing the load on link A by another 50 MB/s, as illustrated at 180; and completely removed from link A if link A\'s metric is 21 or more, as illustrated at 185.

Note that a similar off-loading of demand from link A can also be achieved by reducing the metric of other links. For example, if link A\'s metric is the original value of 10, reducing link B\'s metric to 34 will result in the sharing of the SF-HO demand between routes A-C and B, and reducing link B\'s metric will remove the entire SF-HO demand from link A. In this case, the reduction of load on link A is achieved by ‘attracting’ load to link B.

In accordance with an aspect of this invention, the metric of a candidate link is only modified in such a way so as to cause the routing protocol to remove traffic from that link. Conventionally, a lower metric is favorable for routing, and in such cases, the system is configured to modify the metric only by increasing it. If a particular protocol is configured to favor higher metrics, the system would be configured to modify the metric by decreasing it. For ease of reference, the term ‘increasing the metric’ is used herein for ‘changing the metric of a link in such a manner as to cause the routing protocol to deter traffic from that link’.

The inventors have recognized that rerouting traffic to offload traffic from specific over-utilized links has fewer secondary effects than rerouting traffic to increase traffic on specific under-utilized links. The potential increase of traffic to another link by making the current link less attractive is bounded by the particular traffic flows on the current link, whereas the potential increase in traffic to the current link by making the link more attractive is bounded only by the total amount of traffic from all other links that could use the current link. The offloading of specific traffic flows from a link typically affects only the links used in the alternate routes for the diverted traffic flows, whereas the attraction of flow to an underutilized link often produces a compounding effect on the routing and traffic flow across multiple links, and is significantly more complex to predict. That is, each demand that has a composite metric of a current route that is comparable to the composite metric of a route that includes the attracting link may be switched to the route that includes the link.

Optionally, the determination of the increase in the metric that improves performance can also be limited to a change that also assures that no constraints are violated. In this manner, the process can be used to find metrics that will eliminate constraint violations at each link.

Returning to the flow diagram of FIG. 2, having determined an increase in the metric that will introduce a change to the routing of one or more traffic flows, and optionally remove or ameliorate constraint violations at the targeted links, at 245, the system determines the effect of this change on the network performance, at 250. If, at 260, the metric change results in a performance improvement, the changed metric and corresponding changed network performance is saved for further consideration, at 265. Otherwise, if, at 260, the change does not improve the network performance, the new metric is not saved. Optionally, if the change eliminates a constraint violation without introducing another constraint violation in the network (a “Pareto-efficiency” solution), the new metric may be saved for further consideration, regardless of other measures of network performance; that is, eliminating a violation can be considered an improvement in network performance, regardless of the defined numerical measure of network performance. In like manner, the elimination of a constraint violation can cause the network performance measure to increase by a given amount, so that the elimination of multiple constraints has a cumulative effect on the network performance measure.

After all of the candidate links are assessed, or some other stopping criteria is met, at 270, the improvement in network performance will have been determined for each identified metric modification. Some or all of these modifications are selected for implementation on the network, at 280. For example, the amount of improvement in the network performance can be used to prioritize the metric modifications for selection, such that metric changes that provide the most improvement in the network performance are selected, or such that only metric changes that provide an improvement above a given threshold are considered for selection, or such that any metric change that eliminates a constraint violation is given priority for selection. Similarly, the selected changes can be limited to a maximum number of changes, or a particular number of changes that exceed a particular performance goal.

One of skill in the art will recognize that the change of one metric may affect the margin of improvement that subsequent changes of the remaining metrics will provide. That is, in the selection of metrics to change, the margins of improvement are based on the current level of performance, and the selection of the first metric change will provide a different ‘current level of performance’ than the next change will provide. Conventional multi-variate optimization techniques may be applied to address this issue. For example, in a straightforward embodiment, a ‘greedy’ algorithm is used, wherein the metric change that provides the largest margin of improvement is first selected, then the entire process 240-280 is repeated to determine the next change that provides the largest margin of improvement, based on the measure of performance provided by the first metric change.

When the targeted links are only those that have constraint violations, so that the process is configured to ‘repair’ the network, a ‘hill-climbing’ algorithm may be used for selecting from among the metrics that eliminate such constraint violations. In this process, a cost is associated with each metric change. Each of the targeted links is assessed to determine the change required to eliminate the violation and the cost corresponding to this change. From among all of the evaluated links with violations, the least cost metric change is selected to eliminate the corresponding violation, and the process is repeated until either all violations are eliminated or until a given number of metric changes is reached.

Other techniques for selecting from among the determined metrics that provide an improvement in network performance are presented further below.

After the metric changes are selected for implementation in the network, the system is configured to generate command files that can be used to automate the reconfiguration process, at 290. In a preferred embodiment, the system provides the set of change orders and other information corresponding to the change set in a form that facilitates further analysis before the changes are actually implemented on the network. Copending U.S. patent application Ser. No. 11/503,553, “INCREMENTAL UPDATE OF VIRTUAL DEVICES IN A MODELED NETWORK”, filed 11 Aug. 2006 for Pradeep Singh, Raymond Onley, Nishant Gupta, and Alain Cohen, and incorporated by reference herein, teaches a technique for providing incremental changes to the configuration of modeled networks (“configlets”) so that the assortment of network analysis tools commonly used can be used to assess the impact of such changes. In a preferred embodiment of this invention, the system will automatically produce the “configlets” corresponding to the configuration change required to implement the identified changes. These generated configlets are also used to implement the selected changes on the actual network, typically via executable command files.

In addition to improving network performance and eliminating constraint violations, the principles of this invention can also be applied to improve the resiliency of a network. In a typical network, when a link failure occurs, the network re-routes the demands that use that link. For example, in the network of FIG. 1A, if link N fails, the 60 Mb/s SF-NY demand will be re-routed from route A-F-N-O to the next preferable route (a secondary route) that does not use link N; in this case, to route A-E. In like manner, the 40 Mb/s SF-CH demand will be re-routed from A-F-N to R-J. Note, however, that this failure of link N will introduce a new demand of 60 Mb/s to link E and 40 Mb/s to links R and J. Depending upon the capacity and other loads of links E, R, and J, this re-routed demand may introduce constraint violations, over-utilized links, and so on.

The system of this invention can be used to determine the effects of a failure of a link by evaluating the network performance when the secondary routes are used. Then, changes to the link metrics that modify the routing can be evaluated to determine whether an improvement to the performance can be achieved in the network under a failure condition, preferably without adversely affecting the network performance without the failure condition. As in the basic approach, the change to a link\'s metric is limited to a change that decreases the demand on the link, rather than attracting loads to under-utilized links. As also in the basic approach, the network improvement can be based on the change of a single metric or a set of metrics.



Download full PDF for full patent description/claims.

Advertise on FreshPatents.com - Rates & Info


You can also Monitor Keywords and Search for tracking patents relating to this Tuning routing metrics to reduce maximum link utilization and/or provide failure resiliency patent application.
###
monitor keywords



Keyword Monitor How KEYWORD MONITOR works... a FREE service from FreshPatents
1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored.
3. Each week you receive an email with patent applications related to your keywords.  
Start now! - Receive info on patent apps like Tuning routing metrics to reduce maximum link utilization and/or provide failure resiliency or other areas of interest.
###


Previous Patent Application:
Transmission apparatus and path switching method
Next Patent Application:
Mobile virtual network operator mediator
Industry Class:
Multiplex communications
Thank you for viewing the Tuning routing metrics to reduce maximum link utilization and/or provide failure resiliency patent info.
- - - Apple patents, Boeing patents, Google patents, IBM patents, Jabil patents, Coca Cola patents, Motorola patents

Results in 0.62459 seconds


Other interesting Freshpatents.com categories:
Computers:  Graphics I/O Processors Dyn. Storage Static Storage Printers

###

All patent applications have been filed with the United States Patent Office (USPTO) and are published as made available for research, educational and public information purposes. FreshPatents is not affiliated with the USPTO, assignee companies, inventors, law firms or other assignees. Patent applications, documents and images may contain trademarks of the respective companies/authors. FreshPatents is not affiliated with the authors/assignees, and is not responsible for the accuracy, validity or otherwise contents of these public document patent application filings. When possible a complete PDF is provided, however, in some cases the presented document/images is an abstract or sampling of the full patent application. FreshPatents.com Terms/Support
-g2-0.2551
     SHARE
  
           

FreshNews promo


stats Patent Info
Application #
US 20120287780 A1
Publish Date
11/15/2012
Document #
13556178
File Date
07/23/2012
USPTO Class
370228
Other USPTO Classes
370252, 370237
International Class
/
Drawings
5



Follow us on Twitter
twitter icon@FreshPatents