Method for altering link weights in a communication network to provide traffic information for improved forecasting
View Patent ↗The present invention comprises methods for increasing the rank of the routing matrix of an IP network by systematically altering link weights in the IP network. A full rank routing matrix may be used with further methods in accordance with the present invention to estimate the mean traffic of the IP network based upon the full rank routing matrix and measured link utilization values. The mean traffic and the covariance of the traffic may be iteratively estimated until the estimates coverage. Example methods in accordance with the present invention for estimating mean traffic and covariance of traffic are described for both stationary and non-stationary link utilization data.
1. A method for altering link weights in an IP network having a plurality of nodes connected by a plurality of links to increase the rank of the IP network's routing matrix, wherein traffic in the IP network is described as Y=AX, Y being a link count vector obtained by measuring link utilization, A being a routing matrix derived from IP network topological information and the weights assigned to links in the IP network, and X being a traffic matrix describing the traffic between each origin-destination node pair, traffic being routed between an origin-destination node pair along the shortest path route between the nodes, the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, each set of link weights being a snapshot for which link utilization data may be collected, the method comprising:
limiting the candidate snapshots to those with link weight changes that will create a new shortest route path between at least one origin-destination node pair;
evaluating the candidate snapshots to determine:
whether a candidate snapshot will increase the rank of the IP network's routing matrix; and
whether a candidate snapshot will make the IP network's routing matrix full rank;
discarding candidate snapshots that will not increase the rank of the IP network's routing matrix;
discarding unevaluated candidate snapshots when a candidate snapshot is identified that will make the IP network's routing matrix full rank;
applying the link weight changes of the remaining candidate snapshots to the IP network at predetermined time intervals; and
collecting link utilization data for each applied snapshot.
2. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 1 , further comprising:
limiting candidate snapshots to those that alter no more than two link weights.
3. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 1 , further comprising:
limiting candidate snapshots to those that alter no more than three link weights.
4. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 1 , further comprising:
limiting candidate snapshots to those that alter exactly one link weight.
5. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 4 , the method further comprising:
if none of the candidate snapshots will make the IP network's routing matrix full rank:
expanding the candidate snapshots to those that alter no more than two link weights; and
repeating the step of evaluating the candidate snapshots using the expanded candidate snapshots.
6. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 5 , wherein expanding the candidate snapshots to those that alter no more than two link weights further comprises:
expanding candidate snapshots to those that alter the weights of two adjacent links in the IP network.
7. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 5 , the method further comprising:
if none of the expanded candidate snapshots will make the IP network's routing matrix full rank:
further expanding the candidate snapshots to those that alter no more than three link weights; and
repeating the step of evaluating the candidate snapshots using the further expanded candidate snapshots.
8. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 7 , wherein further expanding the candidate snapshots to those that alter no more than three link weights further comprises:
further expanding the candidate snapshots to those that alter the weights of three links forming a triangle in the IP network.
9. A method of altering link weights in an IP network having a plurality of nodes connected by a plurality of links to increase the rank of the IP network's routing matrix, wherein traffic in the IP network is described as Y=AX, Y being a link count vector obtained by measuring link utilization, A being a routing matrix derived from IP network topological information and the weights assigned to links in the IP network, and X being a traffic matrix describing the traffic between each origin-destination node pair, traffic being routed between an origin-destination node pair along the shortest path route between the nodes, the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, each set of link weights being a snapshot for which link utilization data may be collected, the method comprising:
limiting the candidate snapshots to those with link weight changes that will create a new shortest route path between at least one origin-destination node pair;
ordering the candidate snapshots based upon the amount of network traffic information a candidate snapshot is likely to provide, the candidate snapshots being ordered from those likely to provide the most network traffic information to those likely to provide the least network traffic information;
evaluating the candidate snapshots in order, from those likely to provide the most network traffic information to those likely to provide the least network traffic information, to determine:
whether a candidate snapshot will increase the rank of the IP network's routing matrix; and
whether a candidate snapshot will make the IP network's routing matrix full rank;
discarding candidate snapshots that will not increase the rank of the IP network's routing matrix;
discarding candidate snapshots ordered after the candidate snapshot that will make the IP network's routing matrix full rank;
applying the link weight changes of the remaining candidate snapshots to the IP network at predetermined intervals; and
collecting link utilization data for each applied snapshot.
10. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 9 , wherein ordering the candidate snapshots based upon the amount of network traffic information a candidate snapshot is likely to provide comprises:
determining how many origin-destination node pairs would become well known using the snapshot, a node pair being well known if traffic between that node pair is shifted to a different shortest path route so as to permit the traffic between the node pair to be measured exactly; and
ranking the snapshots from those that would result in the most origin-destination node pairs becoming well known to those that would result in the least origin-destination node pairs becoming well known.
11. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 9 , further comprising:
limiting candidate snapshots to those that alter exactly one link weight.
12. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 11 , the method further comprising:
if none of the candidate snapshots will make the IP network's routing matrix full rank;
expanding the candidate snapshots to those that alter no more than two link weights; and
repeating the steps of ordering and evaluating the candidate snapshots using the expanded candidate snapshots.
13. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 12 , wherein expanding the candidate snapshots to those that alter no more than two link weights further comprises:
expanding candidate snapshots to those that alter the weights of two adjacent links in the IP network.
14. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 12 , the method further comprising:
if none of the expanded candidate snapshots will make the IP network's routing matrix full rank:
further expanding the candidate snapshots to those that alter no more than three link weights; and
repeating the steps of ordering and evaluating the candidate snapshots using the further expanded candidate snapshots.
15. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 13 , wherein ordering the candidate snapshots based upon the amount of new link utilization information a candidate snapshot is likely to provide comprises:
determining how many origin-destination node pairs would become well known using the snapshot, a node pair being well known if traffic between that node pair is shifted to a different shortest path route so as to permit the traffic between the node pair to be measured exactly; and
ranking the snapshots from those that would result in the most origin-destination node pairs becoming well known to those that would result in the least origin-destination node pairs becoming well known.
16. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 15 , wherein ordering the candidate snapshots based upon the amount of network traffic information a candidate snapshot is likely to provide comprises constructing a ranking function that provides a measure of the number of origin-destination node pairs that would become well known using the snapshot, a node pair being well known if traffic between that node pair is shifted to a different shortest route path so as to permit the traffic between the node pair to be measured exactly, and the amount of other network traffic information that would be obtained using the snapshot.
17. The method for altering link weights in an IP network to increase the rank of the IP network's routing matrix of claim 16 , wherein the ranking function comprises:
M
hi
=
∑
p
t
∈
Γ
hi
(
1
/
(
Bm
hi
(
p
t
)
+
1
)
)
∀
w
hi
:
(
l
h
,
w
hi
)
∈
S
,
wherein:
B is a large factor;
the snapshot changes the link weight on link l h ;
the prior weight of link l h is w h ;
the new weight of link l h is w hi =w h +Δw h (p i );
Γ hi is the set of origin-destination node pairs whose routing is affected by changing the weight of link l h ;
an origin-destination node pair whose routing is affected by changing the weight of link l h is p t ;
R hi (p t ) is the set of new links along the shortest path route between origin-destination node pair p t ;
β hi (p) binary variable equal to one if node pair p t uses link l h and that is equal to zero if node pair p t does not use link l h after the link weight change; and
the ambiguity of p t after a weight change is:
m
hi
(
p
t
)
=
min
l
h
∈
R
hi
∑
p
∈
Γ
hi
/
p
t
β
hi
(
p
)
∀
w
hi
:
(
l
h
,
w
hi
)
∈
S
.
18. At least one computer readable media for causing at least one computer to perform a method for altering link weights in an IP network having a plurality of nodes connected by a plurality of links to increase the rank of the IP network's routing matrix, wherein traffic in the IP network is described as Y=AX, Y being a link count vector obtained by measuring link utilization, A being a routing matrix derived from IP network topological information and the weights assigned to links in the IP network, and X being a traffic matrix describing the traffic between each origin-destination node pair, traffic being routed between an origin-destination node pair along the shortest path route between the nodes, the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, each set of link weights being a snapshot for which link utilization data may be collected, the method comprising:
limiting the candidate snapshots to those with link weight changes that will create a new shortest route path between at least one origin-destination node pair;
evaluating the candidate snapshots to determine:
whether a candidate snapshot will increase the rank of the IP network's routing matrix; and
whether a candidate snapshot will make the IP network's routing matrix full rank;
discarding candidate snapshots that will not increase the rank of the IP network's routing matrix;
discarding unevaluated candidate snapshots when a candidate snapshot is identified that will make the IP network's routing matrix full rank;
applying the link weight changes of the remaining candidate snapshots to the IP network at predetermined time intervals; and
collecting link utilization data for each applied snapshot.
19. The at least one computer readable media of claim 18 , wherein the method further comprises:
limiting candidate snapshots to those that alter no more than two link weights.
20. The at least one computer readable media of claim 18 , wherein the method further comprises:
limiting candidate snapshots to those that alter no more than three link weights.
21. The at least one computer readable media of claim 18 , wherein the method further comprises:
limiting candidate snapshots to those that alter exactly one link weight.
22. The at least one computer readable media of claim 21 , wherein the method further comprises:
if none of the candidate snapshots will make the IP network's routing matrix full rank:
expanding the candidate snapshots to those that alter no more than two link weights; and
repeating the step of evaluating the candidate snapshots using the expanded candidate snapshots.
23. The at least one computer readable media of claim 22 , wherein the method further comprises:
expanding candidate snapshots to those that alter the weights of two adjacent links in the IP network.
24. The at least one computer readable media of claim 23 , wherein the method further comprises:
if none of the expanded candidate snapshots will make the IP network's routing matrix full rank:
further expanding the candidate snapshots to those that alter no more than three link weights; and
repeating the step of evaluating the candidate snapshots using the further expanded candidate snapshots.
25. The at least one computer readable media of claim 24 , wherein the method further comprises:
further expanding the candidate snapshots to those that alter the weights of three links forming a triangle in the IP network.
26. At least one computer readable media for causing at least one computer to perform a method of altering link weights in an IP network having a plurality of nodes connected by a plurality of links to increase the rank of the IP network's routing matrix, wherein traffic in the IP network is described as Y=AX, Y being a link count vector obtained by measuring link utilization, A being a routing matrix derived from IP network topological information and the weights assigned to links in the IP network, and X being a traffic matrix describing the traffic between each origin-destination node pair, traffic being routed between an origin-destination node pair along the shortest path route between the nodes, the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, each set of link weights being a snapshot for which link utilization data may be collected, the method comprising:
limiting the candidate snapshots to those with link weight changes that will create a new shortest route path between at least one origin-destination node pair;
ordering the candidate snapshots based upon the amount of network traffic information a candidate snapshot is likely to provide, the candidate snapshots being ordered from those likely to provide the most network traffic information to those likely to provide the least network traffic information;
evaluating the candidate snapshots in order, from those likely to provide the most network traffic information to those likely to provide the least network traffic information, to determine:
whether a candidate snapshot will increase the rank of the IP network's routing matrix; and
whether a candidate snapshot will make the IP network's routing matrix full rank;
discarding candidate snapshots that will not increase the rank of the IP network's routing matrix;
discarding candidate snapshots ordered after the candidate snapshot that will make the IP network's routing matrix full rank;
applying the link weight changes of the remaining candidate snapshots to the IP network at predetermined intervals; and
collecting link utilization data for each applied snapshot.
27. The at least one computer readable media of claim 26 , wherein the method further comprises:
determining how many origin-destination node pairs would become well known using the snapshot, a node pair being well known if traffic between that node pair is shifted to a different shortest path route so as to permit the traffic between the node pair to be measured exactly; and
ranking the snapshots from those that would result in the most origin-destination node pairs becoming well known to those that would result in the least origin-destination node pairs becoming well known.
28. The at least one computer readable media of claim 26 , wherein the method further comprises:
limiting candidate snapshots to those that alter exactly one link weight.
29. The at least one computer readable media of claim 28 , wherein the method further comprises:
if none of the candidate snapshots will make the IP network's routing matrix full rank;
expanding the candidate snapshots to those that alter no more than two link weights; and
repeating the steps of ordering and evaluating the candidate snapshots using the expanded candidate snapshots.
30. The at least one computer readable media of claim 29 , wherein expanding the candidate snapshots to those that alter no more than two link weights further comprises:
expanding candidate snapshots to those that alter the weights of two adjacent links in the IP network.
31. The at least one computer readable media of claim 29 , wherein the method further comprises:
if none of the expanded candidate snapshots will make the IP network's routing matrix full rank:
further expanding the candidate snapshots to those that alter no more than three link weights; and
repeating the steps of ordering and evaluating the candidate snapshots using the further expanded candidate snapshots.
32. The at least one computer readable media of claim 30 , wherein ordering the candidate snapshots based upon the amount of new link utilization information a candidate snapshot is likely to provide comprises:
determining how many origin-destination node pairs would become well known using the snapshot, a node pair being well known if traffic between that node pair is shifted to a different shortest path route so as to permit the traffic between the node pair to be measured exactly; and
ranking the snapshots from those that would result in the most origin-destination node pairs becoming well known to those that would result in the least origin-destination node pairs becoming well known.
33. The at least one computer readable media of claim 32 , wherein ordering the candidate snapshots based upon the amount of new link utilization information a candidate snapshot is likely to provide comprises constructing a ranking function that provides a measure of the number of origin-destination node pairs that would become well known using the snapshot, a node pair being well known if traffic between that node pair is shifted to a different shortest route path so as to permit the traffic between the node pair to be measured exactly, and the amount of other network traffic information that would be obtained using the snapshot.
34. The at least one computer readable media of claim 33 , wherein the ranking function comprises:
M
hi
=
∑
p
t
∈
Γ
hi
(
1
/
(
Bm
hi
(
p
t
)
+
1
)
)
∀
w
hi
:
(
l
h
,
w
hi
)
∈
S
,
wherein:
B is a large factor;
the snapshot changes the link weight on link l h ;
the prior weight of link l in is w h ;
the new weight of link l h is w hi =w h +Δw h (p i );
Γ hi is the set of origin-destination node pairs whose routing is affected by changing the weight of link l h ;
an origin-destination node pair whose routing is affected by changing the weight of link l h is p t ;
R hi (p t ) is the set of new links along the shortest path route between origin-destination node pair p t ;
β hi (p) binary variable equal to one if node pair p t uses link l h and that is equal to zero if node pair p t does not use link l h after the link weight change; and
the ambiguity of p t after a weight change is:
m
hi
(
p
t
)
=
min
l
h
∈
R
hi
∑
p
∈
Γ
hi
/
p
t
β
hi
(
p
)
∀
w
hi
:
(
l
h
,
w
hi
)
∈
S
.