Offline optimization for traffic engineering with segment routing
View Patent ↗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.
1. A method of offline traffic matrix aware segment routing comprising:
receiving a traffic matrix based upon all the traffic between a node i and a node j that is routed in a network; and
determining the amount of traffic between the node i and the node j that will be routed through a node k, based on minimizing a maximum link utilization for a set of links.
2. The method of claim 1 , wherein minimizing the link utilization further comprises:
constraining the amount of traffic between the node i and the node j that may be routed through the 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 the node i and the node j to be equal to or greater than the traffic between the node i and the node 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 to be less than the maximum link utilization multiplied by the capacity of the 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 the node i and the node j that may be routed through the node k is more than or equal to the traffic between the node i and the node j;
the sum of the flow that results on a link e is less than the maximum link utilization multiplied by the capacity of the link e; and
the amount of traffic between the node i and the node j that may be routed through the node k is positive.
6. The method of claim 5 , wherein the linear program minimizes theta for the following set of equations:
∑
k
x
i
j
k
≥
t
i
j
∀
(
i
j
)
;
∑
i
j
∑
k
g
i
j
k
(
e
)
x
i
j
k
≤
θ
c
(
e
)
∀
e
;
x
i
j
k
≥
0
∀
(
i
j
)
;
where t ij denotes the traffic between the node i and the node j, x ij k denotes the amount of traffic between the node i and the node j that may be routed through the node k, g ij k (e) denotes the flow that results on the link e if a unit flow may be routed from the node i and the node j through the node k, c(e) denotes the capacity of the link e, theta denotes the maximum link utilization.
7. The method of claim 1 , further comprising:
determining that the total amount of flow on a link e in the network is less than the link e's capacity.
8. 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 a node i and a node j that is routed in a network; and
determine the amount of traffic between the node i and the node j that will be routed through a node k, based on a minimization of a maximum link utilization for a set of links.
9. The device of claim 8 , wherein minimizing the link utilization further comprises:
constraining the amount of traffic between the node i and the node j that may be routed through the node k to be positive.
10. The device of claim 9 , wherein minimizing the link utilization further comprises:
constraining the total amount of traffic through the node k between the node i and the node j to be equal to or greater than the traffic between the node i and the node j.
11. The device of claim 10 , wherein minimizing the link utilization further comprises:
constraining the sum of the flow that results on a link e to be less than the maximum link utilization multiplied by the capacity of the link e.
12. The device of claim 8 , further comprising:
using a linear program to minimize the maximum link utilization for the traffic matrix, wherein:
the sum of traffic between the node i and the node j that may be routed through the node k is more than or equal to the traffic between the node i and the node j;
the sum of the flow that results on a link e is less than the maximum link utilization multiplied by the capacity of the link e; and
the amount of traffic between the node i and the node j that may be routed through the node k is positive.
13. The device of claim 11 , wherein the linear program minimizes theta for the following set of equations:
∑
k
x
i
j
k
≥
t
i
j
∀
(
i
j
)
;
∑
i
j
∑
k
g
i
j
k
(
e
)
x
i
j
k
≤
θ
c
(
e
)
∀
e
;
x
i
j
k
≥
0
∀
(
i
j
)
;
where t ij denotes the traffic between the node i and the node j, x ij k denotes the amount of traffic between the node i and the node j that may be routed through the node k, g ij k (e) denotes the flow that results on the link e if a unit flow may be routed from the node i and the node j through the node k, c(e) denotes the capacity of the link e, theta denotes the maximum link utilization.
14. The device of claim 8 , wherein the processor is further configured to determine that the total amount of flow on a link e in the network is less than the link e's capacity.
15. A non-transitory machine-readable storage medium encoded with instructions for execution of a method of offline traffic matrix aware segment routing, the medium comprising:
instructions for receiving a traffic matrix based upon all the traffic between a node i and a node j that is routed in a network; and
instructions for determining the amount of traffic between the node i and the node j that will be routed through a node k, based on minimizing a maximum link utilization for a set of links.
16. The non-transitory machine-readable storage medium of claim 15 , wherein minimizing the link utilization further comprises:
constraining the amount of traffic between the node i and the node j that may be routed through the node k to be positive.
17. The non-transitory machine-readable storage medium of claim 16 , wherein minimizing the link utilization further comprises:
constraining the total amount of traffic through the node k between the node i and the node j to be equal to or greater than the traffic between the node i and the node j.
18. The non-transitory machine-readable storage medium of claim 17 , wherein minimizing the link utilization further comprises:
constraining the sum of the flow that results on a link e to be less than the maximum link utilization multiplied by the capacity of the link e.
19. The non-transitory machine-readable storage medium of claim 15 , further comprising:
instructions for using a linear program to minimize the maximum link utilization for the traffic matrix, wherein:
the sum of traffic between the node i and the node j that may be routed through the node k is more than or equal to the traffic between the node i and the node j;
the sum of the flow that results on a link e is less than the maximum link utilization multiplied by the capacity of the link e; and
the amount of traffic between the node i and the node j that may be routed through the node k is positive.
20. The non-transitory machine-readable storage medium of claim 19 , wherein the linear program minimizes theta for the following set of equations:
∑
k
x
i
j
k
≥
t
i
j
∀
(
i
j
)
;
∑
i
j
∑
k
g
i
j
k
(
e
)
x
i
j
k
≤
θ
c
(
e
)
∀
e
;
x
i
j
k
≥
0
∀
(
i
j
)
;
where denotes the traffic between the node i and the node j, x ij k denotes the amount of traffic between the node i and the node j that may be routed through the node k, g ij k (e) denotes the flow that results on the link e if a unit flow may be routed from the node i and the node j through intermediate the node k, c(e) denotes the capacity of the link e, theta denotes the maximum link utilization.
21. The non-transitory machine-readable storage medium of claim 15 , further comprising:
instructions for determining that the total amount of flow on a link e in the network is less than the link e's capacity.