# US 8,279,750 B2 · Simple and resource-efficient resilient network systems

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

- Number: US 8,279,750 B2
- Document ID: US8279750B2
- Status: Granted
- Kind: B2
- Application number: 12/571,180
- Filed: 2009-09-30
- Published: 2010-03-25
- Granted: 2012-10-02
- Earliest claimed: 2003-09-03
- Assignees: Nokia Siemens Networks Oy
- Inventors: Michael Menth; Jens Milbrandt; Andreas Reifert; Phuoc Tran-Gia
- Web page: https://patentgrep.com/patent/US8279750B2

## CPC

- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- H04L 45/24: Multipath
- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- H04L 47/50: Queue scheduling
- H04L 47/522: {Dynamic queue service slot or variable bandwidth allocation}
- H04L 47/54: {Loss aware scheduling}
- H04L 47/626: {channel conditions}
- H04W 8/04: Registration at HLR or HSS [Home Subscriber Server]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

The method as claimed in claim 1, wherein the paths of the multi-path connection are logically or physically disjoint.

### Claim 6 (depends on 1)

The method as claimed in claim 1, wherein the paths of the multi-path connection are link or node disjoint.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 1)

The method as claimed in claim 1, wherein the traffic distribution function is optimized for likely and foreseeable path failure pattern.

### Claim 11 (depends on 1)

The method as claimed in claim 1, wherein the path failure pattern is determined by the following equation:
fg(s)=(φ(pg0,s) . . . (φ(pgkg-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
Fg is the failure pattern comprising a set of active and inactive partial path pig within the multi-path Pg for a connection g between two edge devices
kg is the maximum number of partial paths pig within the multi-path Pg, i.e., 0<=i<kg.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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,
fg(s) is the path failure pattern,
Lg(f) is a load distribution function based upon a failure pattern f,
Pgτ|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
.

### Claim 14 (depends on 1)

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,
fg(s) is the path failure pattern,
Lg(f) is a load distribution function based upon a failure pattern f,
Pgτ|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 Pg 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
.

### Claim 15 (depends on 1)

The method as claimed in claim 1, wherein the step of calculating is performed in a calculator.

### Claim 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.

### Claim 17 (depends on 16)

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.
