Offline optimization for traffic engineering with segment routing

Patent metadata

Field	Value
Publication number	US-2016294702-A1
Application number	US-201514672782-A
Country	US
Kind code	A1
Filing date	Mar 30, 2015
Priority date	Mar 30, 2015
Publication date	Oct 6, 2016
Grant date	—

Abstract

Various exemplary embodiments relate to a method of offline traffic matrix aware segment routing. The method may include receiving a traffic matrix based upon all the traffic between nodes i and j that is routed in the network; and determining the amount of traffic between nodes i and j will be routed through node k, based on minimizing a maximum link utilization for the traffic matrix by determining that the total amount of flow on a link e in the network is less than the link's capacity.

First claim

What is claimed is:

1 . A method of offline traffic matrix aware segment routing comprising:
receiving a traffic matrix based upon all the traffic between nodes i and j that is routed in the network; and determining the amount of traffic between nodes i and j will be routed through node k, based on minimizing a maximum link utilization for the traffic matrix by determining that the total amount of flow on a link e in the network is less than the link's capacity.

2 . The method of claim 1 wherein minimizing the link utilization further comprises:
constraining the amount of traffic between i and j that may be routed through intermediate node k to be positive.

3 . The method of claim 2 wherein minimizing the link utilization further comprises:
constraining the total amount of traffic through the node k between nodes i and j to be equal to or greater than the traffic between i and j.

4 . The method of claim 3 wherein minimizing the link utilization further comprises:
constraining the sum of the flow that results on a link e, when a unit flow is routed from i to j through intermediate node k multiplied by the sum of the amount of traffic between i and j that may be routed through node k, to be less than the maximum link utilization of link e.

5 . The method of claim 1 further comprising:
using a linear program to minimize the maximum link utilization for the traffic matrix, wherein:
the sum of traffic between i and j that may be routed through node k is more than or equal to the traffic between nodes i and j;
the sum of the flow that results on link e, when a unit flow is routed from i to j through intermediate node k multiplied by the sum of the amount of traffic between i and j that may be routed through node k, is less than the maximum link utilization; and
the amount of traffic between i and j that may be routed through node k is positive.

6 . The method of claim 4 , wherein the linear program minimizes theta for the following set of equations:

∑
k



x
ij
k

≥

t
ij





∀

(
ij
)

;

∑
ij



∑
k



g
ij
k



(
e
)



x
ij
k

≤

θ




c


(
e
)





∀
e

;

x
ij
k

≥

0




∀

(
ij
)

;

where t ij denotes the traffic between nodes i and j, x ij k denotes the amount of traffic between i and j that may be routed through node k, g ij k (e) denotes the flow that results on link e if a unit flow may be routed from i to j through intermediate node k, c(e) denotes the capacity of link e, theta denotes the maximum link utilization.

7 . A device for offline traffic matrix aware segment routing, the device comprising:
a memory; and a processor configured to:
receive a traffic matrix based upon all the traffic between nodes i and j that is routed in the network; and
determining the amount of traffic between nodes i and j will be routed through node k, based on a minimization of a maximum link utilization for the traffic matrix, by determining that the total amount of flow on a link, e in the network is less than the link's capacity based on.

8 . The device of claim 7 wherein minimizing the link utilization further comprises:
constraining the amount of traffic between i and j that may be routed through intermediate node k to be positive.

9 . The device of claim 8 wherein minimizing the link utilization further comprises:
constraining the total amount of traffic through the node k between nodes i and j to be equal to or greater than the traffic between i and j.

10 . The device of claim 9 wherein minimizing the link utilization further comprises:
constraining the sum of the flow that results on a link e, when a unit flow is routed from i to j through intermediate node k multiplied by the sum of the amount of traffic between i and j that may be routed through node k, to be less than the maximum link utilization of link e.

11 . The device of claim 7 further comprising:
using a linear program to minimize the maximum link utilization for the traffic matrix, wherein:
the sum of traffic between i and j that may be routed through node k is more than or equal to the traffic between nodes i and j;
the sum of the flow that results on link e when a unit flow is routed from i to j through intermediate node k multiplied by the sum of the amount of traffic between i and j that may be routed through node k, is less than the maximum link utilization; and
the amount of traffic between i and j that may be routed through node k is positive

12 . The device of claim 10 , wherein the linear program minimizes theta for the following set of equations:

∑
k



x
ij
k

Assignees

• Alcatel Lucent Usa Inc

Inventors

• Kodialam Murali
• Bhatia Randeep
• Hao Fang
• Lakshman T V

Classifications

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L41/142

  using statistical or mathematical methods · CPC title

• H04L45/42

  Centralised routing · CPC title

• H04L45/08

  Learning-based routing, e.g. using neural networks or artificial intelligence · CPC title

• H04L45/14

  Routing performance; Theoretical aspects · CPC title