US7978594B2ExpiredUtilityPatentIndex 84
Efficient and robust routing of potentially-variable traffic with local restoration against link failures
Est. expiryMay 28, 2024(expired)· nominal 20-yr term from priority
H04L 45/04H04L 47/125H04L 45/12H04L 45/24
84
PatentIndex Score
8
Cited by
54
References
23
Claims
Abstract
In one embodiment, a method for supporting recovery from failure of a link in a network of nodes interconnected by links. An intermediate node between an ingress point and an egress point of the network is selected to minimize the sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point. The selection identifies two path structures, each comprising a primary path and one or more link backup detours protecting each link on the primary path, with a first path structure between the ingress point and the intermediate node, and a second path structure between the intermediate node and the egress point. To maximize network throughput, packets are routed in two phases, first to the intermediate node via the first path structure in predetermined proportions, and then from the intermediate node to the final destination via the second path structure.
Claims
exact text as granted — not AI-modified1. A computer-implemented method for supporting recovery from failure of a link in a network of nodes interconnected by links, the method comprising: (a) the computer generating, for each of a plurality of potential intermediate nodes between an ingress point and an egress point of the network, a sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point; (b) the computer selecting, from among the potential intermediate nodes, an intermediate node that minimizes the sum generated in step (a), wherein the selection identifies a first path structure between the ingress point and the intermediate node, and a second path structure between the intermediate node and the egress point, each path structure comprising a primary path and one or more link backup detours protecting each link on the primary path; (c) the computer implementing, after completion of step (b) and during a first routing phase, a first routing method for routing a first fraction of a service level between the ingress point and the intermediate node along the primary path of the first path structure; (d) the computer implementing, after completion of step (b) and during a second routing phase, a second routing method for routing a second fraction of the service level between the intermediate node and the egress point along the primary path of the second path structure; and (e) the computer computing a split ratio by determining the minimum value, across all links e, of the link capacity for link e divided by the sum of the ingress capacity constraints of the paths of the first path structure that contain link e and the egress capacity constraints of the paths of the second path structure that contain link e; wherein: the first fraction of the service level is determined by the product of the split ratio and the capacity constraint between the ingress point and the intermediate node; and the second fraction of the service level is determined by the product of the split ratio and the capacity constraint between the intermediate node and the egress point.
2. The invention of claim 1 , wherein:
a traffic matrix corresponding to the ingress and egress points has row and column sum bounds;
the capacity constraint between the ingress point and the intermediate node is the row sum bounds of the traffic matrix; and
the capacity constraint between the intermediate node and the egress point is the column sum bounds of the traffic matrix.
3. The invention of claim 1 , further comprising (f) for all links e, computing the capacity usage on link e and for all links e, incrementing the flow sent on link e by an amount equal to the computed capacity usage on link e.
4. The invention of claim 3 , further comprising:
(h) for all links e, updating the link weights for each of the path structures based on the incremented flow sent on link e.
5. The invention of claim 4 , further comprising:
(i) incrementing the split ratio corresponding to the intermediate node by the split ratio computed in step (e).
6. The invention of claim 5 , wherein the determination of the split ratio in step (e) is made by solving a linear program having primal and dual solutions, wherein flows along the links are augmented in the primal solution, and weights of the links are updated in a multiplicative fashion in the dual solution.
7. The invention of claim 6 , further comprising:
(j) repeating steps (a) through (i) until the feasibility constraints of the dual solution are satisfied.
8. The invention of claim 7 , further comprising:
(k) scaling down the split ratio corresponding to the intermediate node by a maximum capacity violation factor, the maximum capacity violation factor being the factor by which the capacity constraint on each link e is violated.
9. The invention of claim 8 , further comprising:
(l) using the scaled-down split ratio as the optimal traffic split ratio for a subsequent instance of step (e).
10. The invention of claim 6 , wherein:
the primal solution is represented by the following linear programming formulation:
maximize
∑
i
∈
N
α
i
,
subject
to
∑
P
∈
??
ij
x
(
P
)
=
α
j
R
i
+
α
i
C
j
∀
i
,
j
∈
N
,
i
≠
j
,
∑
i
,
j
∑
P
∈
??
ij
,
e
∈
W
(
P
)
x
(
P
)
+
∑
i
,
j
∑
P
∈
??
ij
,
e
∈
B
f
(
P
)
x
(
P
)
≤
u
e
∀
e
,
f
∈
E
,
e
≠
f
,
x
(
P
)
≥
0
∀
P
∈
??
ij
,
∀
i
,
j
∈
N
;
and
the dual solution is represented by the following linear programming formulation:
minimize
∑
e
∈
E
u
e
∑
f
∈
E
,
f
≠
e
w
(
e
,
f
)
,
subject
to
∑
i
:
i
≠
k
R
i
SP
(
i
,
k
)
+
∑
j
:
j
≠
k
C
j
SP
(
k
,
j
)
≥
1
∀
k
∈
N
,
w
(
e
,
f
)
≥
0
∀
e
,
f
∈
E
,
e
≠
f
;
wherein:
N represents the set of all nodes, which includes source node i, destination node j, and intermediate node k;
E represents the set of all links e;
P represents a given path structure from node i to node j;
x(P) represents the traffic on path structure P;
α i represents the split ratio for traffic sent to node i;
α j represents the split ratio for traffic sent to node j;
R i represents the maximum total bandwidth of traffic that node i sends into the network at any time;
C j represents the maximum total bandwidth of traffic that node j receives from the network at any time;
u e represents the available capacity for link e;
w(e,f) represents the set of weights for link e, given failed link f;
c(e) represents the link costs for link e;
W(P) represents the working path containing primary links e;
B e (P) represents the set of backup detours protecting each primary link e;
SP(i,k) represents a minimum cost path structure P between node i and node k whose links e on working path W(P) have cost
∑
f
≠
e
w
(
e
,
f
)
and backup detours B e (P) protecting each primary link e have cost g(e);
SP(k,j) represents a minimum cost path structure P between node k and node j whose links e on working path W(P) have cost
∑
f
≠
e
w
(
e
,
f
)
and backup detours B e (P) protecting each primary link e have cost g(e); and
g(e) represents the cost of the shortest detour protecting link e under link costs c(e′)=w(e′,e)∀e′□E, e′≠e and c(e)=∞.
11. Apparatus for supporting recovery from failure of a path in a network of nodes interconnected by links, the apparatus adapted to: (a) generate, for each of a plurality of potential intermediate nodes between an ingress point and an egress point of the network, a sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point; (b) select, from among the potential intermediate nodes, an intermediate node that minimizes the sum generated in step (a), wherein the selection identifies a first path structure between the ingress point and the intermediate node, and a second path structure between the intermediate node and the egress point, each path structure comprising a primary path and one or more link backup detours protecting each link on the primary path; (c) implement, after completion of step (b) and during a first routing phase, a first routing method for routing a first fraction of a service level between the ingress point and the intermediate node along the primary path of the first path structure; (d) implement, after completion of step (b) and during a second routing phase, a second routing method for routing a second fraction of the service level between the intermediate node and the egress point along the primary path of the second path structure; and (e) compute a split ratio by determining the minimum value, across all links e, of the link capacity for link e divided by the sum of the ingress capacity constraints of the paths of the first path structure that contain link e and the egress capacity constraints of the paths of the second path structure that contain link e; wherein: the first fraction of the service level is determined by the product of the split ratio and the capacity constraint between the ingress point and the intermediate node; and the second fraction of the service level is determined by the product of the split ratio and the capacity constraint between the intermediate node and the egress point.
12. The invention of claim 11 , wherein:
a traffic matrix corresponding to the ingress and egress points has row and column sum bounds;
the capacity constraint between the ingress point and the intermediate node is the row sum bounds of the traffic matrix; and
the capacity constraint between the intermediate node and the egress point is the column sum bounds of the traffic matrix.
13. The invention of claim 11 , wherein the apparatus is further adapted: (f) for all links e, to compute the capacity usage on link e; and (g) for all links e, to increment the flow sent on link e by an amount equal to the computed capacity usage on link e.
14. The invention of claim 13 , wherein the apparatus is further adapted: (f) for all links e, to update the link weights for each of the path structures based on the incremented flow sent on link e.
15. The invention of claim 14 , wherein the apparatus is further adapted: (i) to increment the split ratio corresponding to the intermediate node by the split ratio computed in step (e).
16. The invention of claim 15 , wherein the determination of the split ratio in step (e) is made by solving a linear program having primal and dual solutions, wherein flows along the links are augmented in the primal solution, and weights of the links are updated in a multiplicative fashion in the dual solution.
17. The invention of claim 16 , wherein the apparatus is further adapted: (j) to repeat steps (a) through (i) until the feasibility constraints of the dual solution are satisfied.
18. The invention of claim 17 , wherein the apparatus is further adapted: (k) to scale scaling down the split ratio corresponding to the intermediate node by a maximum capacity violation factor, the maximum capacity violation factor being the factor by which the capacity constraint on each link e is violated.
19. The invention of claim 18 , wherein the apparatus is further adapted: (l) to use the scaled-down split ratio as the optimal traffic split ratio for a subsequent instance of step (e).
20. The invention of claim 16 , wherein:
the primal solution is represented by the following linear programming formulation:
maximize
∑
i
∈
N
α
i
,
subject
to
∑
P
∈
??
ij
x
(
P
)
=
α
j
R
i
+
α
i
C
j
∀
i
,
j
∈
N
,
i
≠
j
,
∑
i
,
j
∑
P
∈
??
ij
,
e
∈
W
(
P
)
x
(
P
)
+
∑
i
,
j
∑
P
∈
??
ij
,
e
∈
B
f
(
P
)
x
(
P
)
≤
u
e
∀
e
,
f
∈
E
,
e
≠
f
,
x
(
P
)
≥
0
∀
P
∈
??
ij
,
∀
i
,
j
∈
N
;
and
the dual solution is represented by the following linear programming formulation:
minimize
∑
e
∈
E
u
e
∑
f
∈
E
,
f
≠
e
w
(
e
,
f
)
,
subject
to
∑
i
:
i
≠
k
R
i
SP
(
i
,
k
)
+
∑
j
:
j
≠
k
C
j
SP
(
k
,
j
)
≥
1
∀
k
∈
N
,
w
(
e
,
f
)
≥
0
∀
e
,
f
∈
E
,
e
≠
f
;
wherein:
N represents the set of all nodes, which includes source node i, destination node j, and intermediate node k;
E represents the set of all links e;
P represents a given path structure from node i to node j;
x(P) represents the traffic on path structure P;
α i represents the split ratio for traffic sent to node i;
α j represents the split ratio for traffic sent to node j;
R i represents the maximum total bandwidth of traffic that node i sends into the network at any time;
C j represents the maximum total bandwidth of traffic that node j receives from the network at any time;
u e represents the available capacity for link e;
w(e,f) represents the set of weights for link e, given failed link f;
c(e) represents the link costs for link e;
W(P) represents the working path containing primary links e;
B e (P) represents the set of backup detours protecting each primary link e;
SP(i,k) represents a minimum cost path structure P between node i and node k whose links e on working path W(P) have cost
∑
f
≠
e
w
(
e
,
f
)
and backup detours B e (P) protecting each primary link e have cost g(e);
SP(k,j) represents a minimum cost path structure P between node k and node j whose links e on working path W(P) have cost
∑
f
≠
e
w
(
e
,
f
)
and backup detours B e (P) protecting each primary link e have cost g(e); and
g(e) represents the cost of the shortest detour protecting link e under link costs c(e′)=w(e′,e)∀e′□E, e′≠e and c(e)=∞.
21. A network of nodes interconnected by links, wherein the network comprises an apparatus for supporting recovery from failure of a path of the network, the apparatus adapted to: (a) generate, for each of a plurality of potential intermediate nodes between an ingress point and an egress point of the network, a sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point; (b) select, from among the potential intermediate nodes, an intermediate node that minimizes the sum generated in step (a), wherein the selection identifies a first path structure between the ingress point and the intermediate node, and a second path structure between the intermediate node and the egress point, each path structure comprising a primary path and one or more link backup detours protecting each link on the primary path; (c) implement, after completion of step (b) and during a first routing phase, a first routing method for routing a first fraction of a service level between the ingress point and the intermediate node along the primary path of the first path structure; (d) implement, after completion of step (b) and during a second routing method for routing a second fraction of the service level between the intermediate node and the egress point along the primary path of the second path structure; and (e) compute a split ratio by determining the minimum value, across all links e, of the link capacity for link e divided by the sum of the ingress capacity constraints of the paths of the first path structure that contain link e and the egress capacity constraints of the paths of the second path structure that contain link e; wherein: the first fraction of the service level is determined by the product of the split ratio and the capacity constraint between the ingress point and the intermediate node; and the second fraction of the service level is determined by the product of the split ratio and the capacity constraint between the intermediate node and the egress point.
22. The network of claim 21 , wherein the apparatus is a centralized controller adapted to communicate with the nodes to control routing through the network.
23. The network of claim 21 , wherein each node comprises an instance of the apparatus such that control of routing is distributed within the network.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.