FreshPatents.com Logo
stats FreshPatents Stats
2 views for this patent on FreshPatents.com
2012: 2 views
Updated: April 21 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.

AdPromo(14K)

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.



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.54583 seconds


Other interesting Freshpatents.com categories:
Computers:  Graphics I/O Processors Dyn. Storage Static Storage Printers -g2-0.1892
     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