# US 10,374,939 B2 · Hop constrained maximum flow with segment routing

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

- Number: US 10,374,939 B2
- Document ID: US10374939B2
- Status: Granted
- Kind: B2
- Application number: 15/605,790
- Filed: 2017-05-25
- Published: 2018-11-29
- Granted: 2019-08-06
- Earliest claimed: 2017-05-25
- Assignees: Nokia of America Corporation
- Applicants: Fang Hao; Murali Kodialam; T. V. Lakshman
- Inventors: Fang Hao; Murali Kodialam; T. V. Lakshman
- Web page: https://patentgrep.com/patent/US10374939B2

## CPC

- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 45/34: {Source routing}
- H04L 43/0882: Utilisation of link capacity
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method of determining a maximum flow on a network path using segment routing, the method including establishing a segment graph, establishing underlying dual weights on the segment graph, computing the dual weights from the segment graph, finding a minimum dual weight path not having more than a predetermined number of hops, augmenting a flow on the dual weight path, and updating the dual weights on the underlying segment graph.

## Claims

### Claim 1

A method of determining a maximum flow on a network path using segment routing, the method comprising:
establishing a segment graph;
establishing underlying dual weights on the segment graph;
computing the dual weights from the segment graph;
finding a minimum dual weight path not having more than a predetermined number of hops;
augmenting a flow on the dual weight path; and
updating the dual weights on the underlying segment graph until a dual objective value exceeds a threshold based on link capacity c(e) and link weight π(e).

### Claim 2 (depends on 1)

The method of claim 1, wherein the dual weight is computed by summing Σe∈SP(q)Fq(e)π(e), where q is a link on the segment graph, Fq(e) is an amount of flow on one link in the segment graph, and π(e) represents the link weight associated with link e on the underlying segment graph.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
initializing π(e) to δ/c(e), wherein δ is a parameter chosen to obtain a required accuracy guarantee.

### Claim 4 (depends on 1)

The method of claim 1, wherein a total amount of flow generated on link e in a physical topology due to a flow of Δ on P*f(e)=Σq∈P*F(e), where P* is a new path and Fq(e) is the amount of flow on one link in the segment graph.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
calculating a new dual objective value D(π)=Σec(e)π(e).

### Claim 6 (depends on 5)

The method of claim 5, wherein the method of determining the maximum flow on the network path using segment routing is repeated as long as D(π)≤1 and terminates the first time the weight of the shortest path D(π)>1.

### Claim 7

A non-transitory machine-readable medium comprising program instructions for causing a computer processor to perform a method, the non-transitory machine-readable storage medium comprising:
instructions for establishing a segment graph;
instructions for establishing underlying dual weights on the segment graph;
instructions for computing the dual weights from the segment graph;
instructions for finding a minimum dual weight path not having more than a predetermined number of hops;
instructions for augmenting a flow on the dual weight path; and
instructions for updating the dual weights on the underlying segment graph until a dual objective value exceeds a threshold based on link capacity c(e) and link weight π(e).

### Claim 8 (depends on 7)

The non-transitory machine-readable storage medium of claim 7, wherein the dual weight is computed by summing Σe∈SP(q)Fq(e)π(e), where q is a link on the segment graph, Fq(e) is an amount of flow on one link in the segment graph, and π(e) represents the link weight associated with link e on the underlying segment graph.

### Claim 9 (depends on 8)

The non-transitory machine-readable storage medium of claim 8, further comprising:
instructions for initializing π(e) to δ/c(e), wherein δ is a parameter chosen to obtain a required accuracy guarantee.

### Claim 10 (depends on 7)

The non-transitory machine-readable storage medium of claim 7, wherein a total amount of flow generated on link e in a physical topology due to a flow of Δ on P*f(e)=Σq∈P*Fq(e), where P* is a new path and Fq(e) is the amount of flow on one link in the segment graph.

### Claim 11 (depends on 7)

The non-transitory machine-readable storage medium of claim 7, further comprising:
instructions for calculating a new dual objective value D(π)=Σec(e)π(e).

### Claim 12 (depends on 11)

The non-transitory machine-readable storage medium of claim 11, wherein the method of determining the maximum flow on the network path using segment routing is repeated as long as D(π)≤1 and terminates the first time the weight of the shortest path D(π)>1.