Simple and resource-efficient resilient network systems
View Patent ↗The invention is related to a method for resilient multi-path connections between edge devices of a communication network. First are determined connection-specific traffic distribution functions for the multi-paths depending on a plausible failure pattern of active and inactive paths of the multi-path of this connection. Further is selected the traffic distribution function for a multi-path depending on the current failure pattern of active and an inactive paths of the multi-path of this connection and is distributed the traffic of the connection onto the path of the corresponding multi-path pursuant to the selected traffic distribution function. An essential advantage of the invention is a significant decrease of network capacity for resilient multi-path connections. Another advantage of the invention is the short reaction time in case of an outage of one or more paths of the multi-path connections.
1. A method for providing a resilient multi-path connection, wherein traffic is distributed over several paths between edge devices of a communication network, comprising, in one or more devices connected to or forming part of the communication network, performing the following steps:
calculating connection-specific traffic distribution functions of the multi-path connection based upon path failure patterns of the multi-path connection;
selecting a traffic distribution function of the multi-path connection based upon the calculated connection-specific traffic distribution functions and based upon current path failure pattern of the multi-path connection; and
distributing traffic into corresponding paths of the multi-path connection based upon the selected traffic distribution function.
2. The method as claimed in claim 1 , wherein one path of multi-path is a primary path over which traffic is transmitted in a failure-free scenario and remaining paths are backup paths.
3. The method as claimed in claim 1 , wherein the traffic of the multi-path connection is distributed over a plurality of primary paths over which the traffic is transmitted in a failure-free scenario.
4. The method as claimed in claim 1 , wherein the calculation of the connection-specific traffic distribution functions of the multi-path connection depends on a topology of the communication network, routes of paths of the multi-path connection through the communication network, and both an expected traffic between the edge devices and available link capacities.
5. The method as claimed in claim 1 , wherein the paths of the multi-path connection are logically or physically disjoint.
6. The method as claimed in claim 1 , wherein the paths of the multi-path connection are link or node disjoint.
7. The method as claimed in claim 1 , wherein a path failure pattern is a combination of detected active or inactive paths of the multi-path connection.
8. The method as claimed in claim 7 , wherein a partial outage of a path is indicated as inactive by a failure information at the edge devices.
9. The method as claimed in claim 8 , wherein a failure of a path due to an outage of a contained network element is indicated by a monitoring information which is periodically transmitted over the path.
10. The method as claimed in claim 1 , wherein the traffic distribution function is optimized for likely and foreseeable path failure pattern.
11. The method as claimed in claim 1 , wherein the path failure pattern is determined by the following equation:
f g ( s )=(φ( p g 0 ,s ) . . . (φ( p g kg-1 ,s )) τ with
Φ(p,s) is a function indicating whether a partial (single) path p is active or inactive if a failure scenario s (set of failed network elements) occurs, and
F g is the failure pattern comprising a set of active and inactive partial path p i g within the multi-path P g for a connection g between two edge devices
kg is the maximum number of partial paths p i g within the multi-path P g , i.e., 0<=i<kg.
12. The method as claimed in claim 1 , wherein a primary capacity of a link is a capacity allocated to a flow if no failure occurs.
13. The method as claimed in claim 1 , wherein the primary capacity of a link is reused and the traffic distribution function is computed by a linear program with several constraints whose optimization function is determined by following equation:
∀
g
∈
S
:
∑
g
∈
Gs
P
g
τ
l
g
(
f
g
(
s
)
)
c
(
g
)
≤
b
with
S is a set of all failure scenarios,
Gs is a set of all active aggregate connections in case of failure scenario s,
f g (s) is the path failure pattern,
L g (f) is a load distribution function based upon a failure pattern f,
P g τ| g (f)*c(g): τ transposes a proceeding vector, this computes a vector with a fraction of a traffic rate c(g) caused by the multi-path Pg and a rate c(g) of a aggregate connection g,
b is a vector with a capacity of links which are larger than corresponding traffic rates caused by any failure scenario and
∑
g
∈
Gs
c
(
g
)
P
g
τ
l
g
(
f
g
(
0
)
)
≤
b
.
14. The method as claimed in claim 1 , wherein the primary capacity of a link is not reused and the traffic distribution function is computed by a linear program with several constraints whose optimization function is determined by following equations:
∀
g
∈
S
:
∑
g
∈
Gs
P
g
τ
l
g
(
f
g
(
s
)
)
c
(
g
)
≤
b
and
∀
g
∈
F
g
:
l
g
(
f
)
+
f
≥
l
g
(
f
g
(
0
)
)
with
S is a set of all failure scenarios,
Gs is a set of all active aggregate connections in case of failure scenario s,
f g (s) is the path failure pattern,
L g (f) is a load distribution function based upon a failure pattern f,
P g τ| g (f)*c(g): τ transposes a proceeding vector, this computes a vector with a fraction of a traffic rate c(g) caused by a multi-path P g and a rate c(g) of a aggregate connection g,
b is vector with a capacity of links which are larger than corresponding traffic rates caused by any failure scenario and
∑
g
∈
Gs
c
(
g
)
P
g
τ
l
g
(
f
g
(
0
)
)
≤
b
.
15. The method as claimed in claim 1 , wherein the step of calculating is performed in a calculator.
16. A non-transitory computer readable medium having stored thereon a set of computer readable instructions for providing a resilient multi-path connection, wherein traffic is distributed over several paths between edge devices of a communication network, the set of computer readable instructions comprising:
a program subroutine for calculating connection-specific traffic distribution functions of the multi-path connection based upon path failure patterns of the multi-path connection;
a program subroutine for selecting a traffic distribution function of the multi-path connection based upon the calculated connection-specific traffic distribution functions and based upon current path failure pattern of the multi-path connection; and
a program subroutine for distributing traffic into corresponding paths of the multi-path connection based upon the selected traffic distribution function.
17. The non-transitory computer readable medium as claimed in claim 16 , wherein the calculation of the connection-specific traffic distribution functions of the multi-path connection depends on a topology of the communication network, routes of paths of the multi-path connection through the communication network, and both an expected traffic between the edge devices and available link capacities.