# US 2006/0050634 A1 · Methods and systems to perform traffic engineering in a metric-routed network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0050634 A1
- Document ID: US20060050634A1
- Status: Published application
- Kind: A1
- Application number: 10/937,988
- Filed: 2004-09-09
- Published: 2006-03-09
- Earliest claimed: 2004-09-09
- Assignees: Cariden Technologies, Inc.
- Inventors: Alan Gous
- Web page: https://patentgrep.com/patent/US20060050634A1

## CPC

- H04L 43/0882: Utilisation of link capacity
- H04L 41/06: Management of faults, events, alarms or notifications
- H04L 41/083: for increasing network speed
- H04L 41/0836: {to enhance reliability, e.g. reduce downtime}
- H04L 41/12: Discovery or management of network topologies
- H04L 41/22: comprising specially adapted graphical user interfaces [GUI]
- H04L 43/06: Generation of reports
- H04L 43/16: Threshold monitoring
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A system, to migrate a shortest-path-first (SPF) routed network from a first routing state to a second routing state, includes 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 migrates the network from the first routing state to the second routing state. A network controller sequentially configures the network according to the sequence of intermediate network plans to migrate the network from the first routing state to the second routing state. Each intermediate network plan of the sequence configures the network to operate within at least one predetermined constraint.

## Claims

### Claim 1

A system to estimate point-to-point bandwidth demand within a network including a plurality of nodes and a plurality of links between the plurality of nodes, the system including:
a network controller to determine link traffic measures for a set of links of the network, the link traffic measures each indicating a measured utilization of a respective link, and to determine point-to-point bandwidth demand measures between a set of nodes of the network, the point-to-point bandwidth demand measures each indicating a measured demand between a source node and a destination node included in the set of nodes; and
a demand estimation module, coupled to the network controller, to receive the link traffic measures and the point-to-point bandwidth demand measures from the network controller, and to calculate a plurality of point-to-point bandwidth demand estimates for the plurality of nodes utilizing the link traffic measures and the point-to-point bandwidth demand measures.

### Claim 2

A method to estimate point-to-point bandwidth demand within a network including a plurality of nodes and a plurality of links between the plurality of nodes, the method including:
determining link traffic measures for a set of links of the network, the link traffic measures each indicating a measured utilization of a respective link;
determining point-to-point bandwidth demand measures between a set of nodes of the network, the point-to-point bandwidth demand measures each indicating a measured demand between a source node and a destination node included in the set of nodes; and
calculating a plurality of point-to-point bandwidth demand estimates for the plurality of nodes utilizing the link traffic measures and the point-to-point bandwidth demand measures.

### Claim 3 (depends on 2)

The method of claim 2, including utilizing the plurality of point-to-point demand estimates to simulate network routing under changes in a network routing state.

### Claim 4 (depends on 2)

The method of claim 2, wherein the changes include network topology changes.

### Claim 5 (depends on 2)

The method of claim 2, wherein the changes result from a failure of a network component.

### Claim 6 (depends on 2)

The method of claim 2, wherein the network is a shortest-path-first routed network, and the changes result from changes to metrics associated with the plurality of links of the network.

### Claim 7 (depends on 2)

The method of claim 2, including utilizing the plurality of point-to-point demand estimates to perform a simulation of routing of the network, so as identified identify link utilizations for each link within the network under each of the plurality of point-to-point demand estimates.

### Claim 8 (depends on 2)

The method of claim 2, including utilizing the plurality of point-to-point demand estimates to optimize link utilizations over the plurality of point-to-point demand estimates and a plurality of network failure scenarios.

### Claim 9 (depends on 2)

The method of claim 2, wherein the determination of the link traffic measures includes performing a measurement of traffic of the set of links utilizing a network controller.

### Claim 10 (depends on 2)

The method of claim 2, wherein the determination of the point-to-point bandwidth demand measures includes performing a measurement of bandwidth demands between the nodes of the set of nodes utilizing a network controller.

### Claim 11 (depends on 2)

The method of claim 2, wherein if the link traffic measures and the point-to-point bandwidth demand measures are inconsistent, the point-to-point bandwidth demand estimates are calculated to reconcile the inconsistencies.

### Claim 12 (depends on 11)

The method of claim 11, including retrieving prior point-to-point bandwidth demand estimates for the plurality of nodes, and utilizing the prior point-to-point bandwidth demand estimates in the calculation of the point-to-point bandwidth demand estimates.

### Claim 13 (depends on 2)

The method of claim 2, wherein the calculation includes identifying a set of link traffic values such that there exists a valid set of point-to-point bandwidth demand levels that, when routed through the network, yield the set of link traffic values.

### Claim 14 (depends on 13)

The method of claim 13, wherein the identifying of the set of link traffic values is such that the valid set of point-to-point bandwidth demand levels closely match the point-to-point bandwidth demand measures.

### Claim 15 (depends on 14)

The method of claim 14, wherein differences between the valid set of point-to-point bandwidth demand levels and the point-to-point bandwidth demand measures are minimized.

### Claim 16 (depends on 15)

The method of claim 15, wherein the identifying of the set of link traffic values is such that the set of link traffic values closely match the link traffic measures.

### Claim 17 (depends on 2)

The method of claim 2, wherein the calculating includes identifying a set of point-to-point bandwidth demand levels that is close to the point-to-point bandwidth demand measures.

### Claim 18 (depends on 17)

The method of claim 17, wherein the calculating includes identifying a set of point-to-point demand bandwidth levels such that a calculated set of link traffic values, calculated based on the identified set of point-to-point bandwidth demand levels, corresponds to the identified set of point-to-pointed bandwidth demand levels.

### Claim 19 (depends on 18)

The method of claim 18, wherein the calculating includes identifying a set of point-to-point demand bandwidth levels such that the identified set of point-to-point demand levels closely match the prior point-to-point prior demand bandwidth levels 20.

### Claim 20

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.

### Claim 21

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.

### Claim 22 (depends on 21)

The method of claim 21, 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.

### Claim 23 (depends on 22)

The method of claim 22, 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.

### Claim 24 (depends on 21)

The method of claim 21, 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.

### Claim 25 (depends on 21)

The method of claim 21, 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.

### Claim 26 (depends on 21)

The method of claim 21, 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.

### Claim 27 (depends on 26)

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

### Claim 28 (depends on 26)

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

### Claim 29 (depends on 21)

The method of claim 21, 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.

### Claim 30 (depends on 21)

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

### Claim 31 (depends on 30)

The method of claim 30, 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.

### Claim 32

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.

### Claim 33

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.

### Claim 34 (depends on 33)

The method of claim 33, 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.

### Claim 35 (depends on 33)

The method of claim 33, 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.

### Claim 36 (depends on 33)

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

### Claim 37 (depends on 36)

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

### Claim 38 (depends on 33)

The method of claim 33, 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.

### Claim 39 (depends on 33)

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

### Claim 40 (depends on 33)

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

### Claim 41 (depends on 33)

The method of claim 33, 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.

### Claim 42 (depends on 33)

The method of claim 33, 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.

### Claim 43 (depends on 33)

The method of claim 33, 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.

### Claim 44 (depends on 33)

The method of claim 33, 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.

### Claim 45 (depends on 33)

The method of claim 33, 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.

### Claim 46 (depends on 45)

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

### Claim 47 (depends on 33)

The method of claim 33, 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.

### Claim 48 (depends on 33)

The method of claim 33, 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.

### Claim 49

An automated method to generate an interface to display information regarding a network, the method including:
identifying at least one collection of network nodes as constituting a network site;
generating a first display, to be included with the interface, of graphical nodes and graphical links representative of respective network nodes and network links within the network, wherein the at least one collection of network nodes is represented by a single graphical node within the display;
generating a second display, to be included with an interface, depicting the at least one collection of network nodes and network links between nodes of the at least one collection; and
generating the interface simultaneously to present the first and second displays to a user.

### Claim 50 (depends on 49)

The method of claim 49, wherein the identification of the collection of network nodes includes identifying the at least one collection of nodes as residing at a common physical location.

### Claim 51 (depends on 49)

The method of claim 49, wherein the generation of the second display includes depicting further network links between nodes of the at least one collection and nodes outside the at least one collection within the second display.

### Claim 52 (depends on 49)

The method of claim 49, wherein at least two links between a pair of nodes of the network constitutes a circuit to facilitate bidirectional communications between the nodes of the pair, the generation of at least the first display including a graphical circuit representative of a circuit between the pair of nodes.

### Claim 53 (depends on 52)

The method of claim 52, including generating the graphical circuit to be visually indicative of a bandwidth capacity between the pair of nodes.

### Claim 54 (depends on 53)

The method of claim 53, wherein the generation of the graphical circuit to be visually indicative of the bandwidth capacity includes dimensioning the graphical circuit to be indicative of the bandwidth capacity.

### Claim 55 (depends on 52)

The method of claim 52, including generating the graphical circuit to depict network links that constitute the represented network circuit.

### Claim 56 (depends on 52)

The method of claim 52, including generating the graphical circuit to be visually indicative of a bandwidth utilization of a represented network circuit.

### Claim 57 (depends on 56)

The method of claim 56, wherein the generating of the graphical link to be visually indicative of the bandwidth utilization includes coloring the graphical link according to a color/utilization index.

### Claim 58 (depends on 56)

The method of claim 56, wherein the generating of the graphical link to be visually indicative of the bandwidth utilization includes coloring of section of the graphical link in proportion to the bandwidth utilization.

### Claim 59 (depends on 49)

The method of claim 49, including generating the interface to allow user-specification of a failure scenario with respect to the network, and to present a display of re-routed demand through the network responsive to the failure scenario.

### Claim 60 (depends on 49)

The method of claim 49, including generating the interface to allow user-specification of a bandwidth demand level with respect to the network, and to present a display of bandwidth utilization within the network responsive to the specified bandwidth demand level.

### Claim 61 (depends on 49)

The method of claim 49, including generating the interface to allow a user-specification of a network traffic service class, and to present one or more of bandwidth demand and bandwidth utilization information specific to the specified network traffic service class.

### Claim 62 (depends on 49)

The method of claim 49, including generating the interface to present an indication of capacity equal to an amount of capacity available to network traffic in the network belonging to the specified network traffic service class, and to show the bandwidth utilization information as a proportion of the capacity.

### Claim 63 (depends on 49)

The method of claim 49, including generating the interface to display at least one of bandwidth demand and bandwidth utilization information for at least one link of the network in a defined worst-case failure scenario.

### Claim 64 (depends on 63)

The method of claim 63, wherein each link to display within the interface to be colored based on the highest utilization across a plurality of failure scenarios and a plurality of demand bandwidth levels, so that the plurality links are depicted as having utilizations represented for at least one of the plurality of failure scenarios and the plurality of demand bandwidth levels.

### Claim 65

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 identifying 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.
