# US 2018/0324082 A1 · Weight setting using inverse optimization

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

- Number: US 2018/0324082 A1
- Document ID: US20180324082A1
- Status: Published application
- Kind: A1
- Application number: 15/587,649
- Filed: 2017-05-05
- Published: 2018-11-08
- Earliest claimed: 2017-05-05
- Inventors: Fang Hao; Murali Kodialam; Tirunell V. Lakshman
- Web page: https://patentgrep.com/patent/US20180324082A1

## CPC

- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 41/0823: characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability (for optimising operational conditions of wireless networks H04W24/02)
- H04L 41/40: using virtualisation of network functions or resources, e.g. SDN or NFV entities
- H04L 43/0882: Utilisation of link capacity
- H04L 43/16: Threshold monitoring
- H04L 43/20: the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
- H04L 45/126: {minimising geographical or physical path length}
- H04L 45/14: {Routing performance; Theoretical aspects}
- H04W 40/02: Communication route or path selection, e.g. power-based or shortest path routing
- H04L 45/70: {Routing based on monitoring results}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

The present disclosure generally discloses improvements in computer performance for supporting use of shortest path routing in a communication network. The shortest path routing capability may be configured to support setting of link weights for use in shortest path routing. The shortest path routing capability may be configured to support setting of link weights for use in shortest path routing based on inverse optimization. The shortest path routing capability may be configured to support setting of link weights for use in shortest path routing based on distance between traffic matrices (e.g., distance between a requested traffic matrix and a routed traffic matrix). The shortest path routing capability may be configured to determine, based on the distance between a requested traffic matrix and a routed traffic matrix, whether to accept or reject a set of link weights for a network.

## Claims

### Claim 1

An apparatus, comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
receive a requested traffic matrix indicative of traffic to be routed through a network including a set of nodes and a set of links, a set of link weights associated with the respective links, and a performance metric;
determine, based on the requested traffic matrix and the set of link weights, a routed traffic matrix indicative of routing of the traffic of the requested traffic matrix in the network using the set of link weights;
determine, based on the performance metric, a distance between the requested traffic matrix and the routed traffic matrix; and
determine, based on the distance between the requested traffic matrix and the routed traffic matrix, whether to accept or reject the set of link weights for the network.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the performance metric comprises a maximum link utilization for the network.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the processor is configured to:
accept the set of link weights for the network based on a determination that the distance between the requested traffic matrix and the routed traffic matrix satisfies a threshold.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the processor is configured to:
reject the set of link weights for the network based on a determination that the distance between the requested traffic matrix and the routed traffic matrix fails to satisfy a threshold.

### Claim 5 (depends on 4)

The apparatus of claim 4, wherein the processor is configured to:
modify the set of link weights to provide a modified set of link weights;
determine, based on requested traffic matrix and the modified set of link weights, a new routed traffic matrix indicative of routing of the traffic of the requested traffic matrix in the network using the modified set of link weights;
determine, based on the performance metric, a new distance between the requested traffic matrix and the new routed traffic matrix; and
determine, based on the new distance between the requested traffic matrix and the new routed traffic matrix, whether to accept or reject the modified set of link weights for the network.

### Claim 6 (depends on 5)

The apparatus of claim 5, wherein, to modify the set of link weights to provide the modified set of link weights, the processor is configured to:
increase or decrease the link weight of one of the links by a predetermined amount.

### Claim 7 (depends on 1)

The apparatus of claim 1, wherein the processor is configured to:
modify the performance metric, based on a determination to accept the set of link weights for the network, to provide thereby a modified performance metric.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein the processor is configured to:
determine, based on the modified performance metric, a new distance between the requested traffic matrix and the routed traffic matrix; and
determine, based on the new distance between the requested traffic matrix and the routed traffic matrix, whether to accept or reject the set of link weights for the network.

### Claim 9 (depends on 1)

The apparatus of claim 1, wherein the processor is configured to:
based on a determination to accept the set of link weights for the network, initiate configuration of the network to support the set of link weights for the network.

### Claim 10 (depends on 9)

The apparatus of claim 9, wherein, to initiate configuration of the network to support the set of link weights for the network, the processor is configure to:
send, toward each of one or more of the nodes of the network, one or more messages configured to inform the respective node regarding one or more of the link weights in the set of link weights for the network.

### Claim 11

A method, comprising:
receiving, by a processor, a requested traffic matrix indicative of traffic to be routed through a network including a set of nodes and a set of links, a set of link weights associated with the respective links, and a performance metric;
determining, by the processor based on the requested traffic matrix and the set of link weights, a routed traffic matrix indicative of routing of the traffic of the requested traffic matrix in the network using the set of link weights;
determining, by the processor based on the performance metric, a distance between the requested traffic matrix and the routed traffic matrix; and
determining, by the processor based on the distance between the requested traffic matrix and the routed traffic matrix, whether to accept or reject the set of link weights for the network.

### Claim 12 (depends on 11)

The method of claim 11, wherein the performance metric comprises a maximum link utilization for the network.

### Claim 13 (depends on 11)

The method of claim 11, further comprising:
accepting the set of link weights for the network based on a determination that the distance between the requested traffic matrix and the routed traffic matrix satisfies a threshold.

### Claim 14 (depends on 11)

The method of claim 11, further comprising:
rejecting the set of link weights for the network based on a determination that the distance between the requested traffic matrix and the routed traffic matrix fails to satisfy a threshold.

### Claim 15 (depends on 14)

The method of claim 14, further comprising:
modifying the set of link weights to provide a modified set of link weights;
determining, based on requested traffic matrix and the modified set of link weights, a new routed traffic matrix indicative of routing of the traffic of the requested traffic matrix in the network using the modified set of link weights;
determining, based on the performance metric, a new distance between the requested traffic matrix and the new routed traffic matrix; and
determining, based on the new distance between the requested traffic matrix and the new routed traffic matrix, whether to accept or reject the modified set of link weights for the network.

### Claim 16 (depends on 15)

The method of claim 15, wherein modifying the set of link weights to provide the modified set of link weights comprises:
increasing or decreasing the link weight of one of the links by a predetermined amount.

### Claim 17 (depends on 11)

The method of claim 11, further comprising:
modifying the performance metric, based on a determination to accept the set of link weights for the network, to provide thereby a modified performance metric.

### Claim 18 (depends on 17)

The method of claim 17, further comprising:
determining, based on the modified performance metric, a new distance between the requested traffic matrix and the routed traffic matrix; and
determining, based on the new distance between the requested traffic matrix and the routed traffic matrix, whether to accept or reject the set of link weights for the network.

### Claim 19 (depends on 11)

The method of claim 11, further comprising:
based on a determination to accept the set of link weights for the network, initiate configuration of the network to support the set of link weights for the network.

### Claim 20 (depends on 19)

The method of claim 19, wherein initiating configuration of the network to support the set of link weights for the network comprises:
sending, toward each of one or more of the nodes of the network, one or more messages configured to inform the respective node regarding one or more of the link weights in the set of link weights for the network.

### Claim 21

A non-transitory computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method, the method comprising:
receiving a requested traffic matrix indicative of traffic to be routed through a network including a set of nodes and a set of links, a set of link weights associated with the respective links, and a performance metric;
determining, based on the requested traffic matrix and the set of link weights, a routed traffic matrix indicative of routing of the traffic of the requested traffic matrix in the network using the set of link weights;
determining, based on the performance metric, a distance between the requested traffic matrix and the routed traffic matrix; and
determining, based on the distance between the requested traffic matrix and the routed traffic matrix, whether to accept or reject the set of link weights for the network.
