Hop constrained maximum flow with segment routing

Patent metadata

Field	Value
Publication number	US-10374939-B2
Application number	US-201715605790-A
Country	US
Kind code	B2
Filing date	May 25, 2017
Priority date	May 25, 2017
Publication date	Aug 6, 2019
Grant date	Aug 6, 2019

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.

First claim

The invention claimed is:

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

2. The method of claim 1 , wherein the dual weight is computed by summing Σ e∈SP(q) F q (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.

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

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

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

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

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

8. The non-transitory machine-readable storage medium of claim 7 , wherein the dual weight is computed by summing Σ e∈SP (q)F q (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.

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

10. 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* F q (e), where P* is a new path and Fq(e) is the amount of flow on one link in the segment graph.

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

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

Assignees

• Hao Fang
• Kodialam Murali
• Lakshman T V
• Nokia America Corp

Inventors

• Hao Fang
• Kodialam Murali
• Lakshman T V

Classifications

• H04L45/122 Primary

  by minimising distances, e.g. by selecting a route with minimum of number of hops · CPC title

• H04L43/0882

  Utilisation of link capacity · CPC title

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04L45/34

  Source routing · CPC title