Method for estimating a traffic matrix in a communication network using stationary data
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 estimating the mean traffic between origin-destination node pairs of an IP network comprising a plurality of nodes connected by a plurality of links, each link being assigned a weight used to determine the shortest path route between the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, the traffic matrix describing the total amount of traffic between each origin-destination node pair in the network over a given time period k being X(k), the method comprising:
collecting link utilization values at different times denoted k, wherein k=0, 1, 2, . . . , K−1;
constructing link count vectors Y(k) using the collected link utilization values;
constructing routing matrices A(k) using the IP network's topological information and the weight assigned to each link in the IP network at each time k, such that Y(k)=A(k)X(k);
deleting missing and redundant rows in Y(k) and in A(k) to produce Y′(k) and A′(k), such that Y′(k)=A′(k)X(k);
modeling the traffic matrix X(k) as stationary, such that X(k)=X+W(k), wherein W(k) is a traffic fluctuation vector and X is a vector describing the mean traffic between each origin-destination node pair in the IP network;
defining, in block matrix notation:
Y
=
[
Y
′
(
0
)
Y
′
(
1
)
…
Y
′
(
K
-
1
)
]
;
A
=
[
A
′
(
0
)
A
′
(
1
)
…
A
′
(
K
-
1
)
]
;
and
estimating X, the vector describing the mean traffic between each origin-destination node pair in the IP network, as {circumflex over (X)}, such that {circumflex over (X)}=(A T A) −1 A T Y.
2. A method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network comprising a plurality of nodes connected by a plurality of links, each link being assigned a weight used to determine the shortest path route between each origin-destination node pairs, the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, the traffic matrix describing the total amount of traffic between each origin-destination node pair in the network over a given time period k being X(k), the method comprising:
collecting link utilization values at different times denoted k, wherein k=0, 1, 2, . . . , K−1;
constructing link count vectors Y(k) using the collected link utilization values;
constructing routing matrices A(k) using the IP network's topological information and the weight assigned to each link in the IP network at any time k, such that Y′(k)=A′(k)X(k);
deleting missing and redundant rows in Y(k) and in A(k) to produce Y′(k) and A′(k), such that Y′(k)=A′(k)X(k);
modeling the traffic matrix as stationary, such that X(k)=X+W(k), wherein W(k) is a traffic fluctuation matrix and x is a vector describing the mean traffic between each origin-destination node pair in the IP network;
defining, in block matrix notation:
Y
=
[
Y
′
(
0
)
Y
′
(
1
)
…
Y
′
(
K
-
1
)
]
;
A
=
[
A
′
(
0
)
A
′
(
1
)
…
A
′
(
K
-
1
)
]
;
W
=
[
W
(
0
)
W
(
1
)
…
W
(
K
-
1
)
]
,
and
C
=
[
A
′
(
0
)
0
…
0
0
A
′
(
1
)
…
0
…
…
…
…
0
0
…
A
′
(
K
-
1
)
]
;
defining B as the covariance matrix of W, such that B=E[WW T ]; and
iteratively estimating X, the vector describing the mean traffic between each origin-destination node pair in the IP network, and B, the covariance of the traffic fluctuation matrix.
3. The method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network of claim 2 , wherein estimating x comprises defining as an estimate {circumflex over (X)}, such that:
{circumflex over (X)}={circumflex over (X)} ( Y,B )=( A T ( CBC T ) −1 A T ( CBC T ) −1 Y.
4. The method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network of claim 2 , wherein iteratively estimating X and B comprises:
estimating X as {circumflex over (X)}, such that:
{circumflex over (X)}={circumflex over (X)} ( Y,B )=( A T ( CBC T ) −1 A ) −1 A T ( CBC T ) −1 Y,
using an estimate of B, the initial estimate being B=I, I being the identity matrix;
estimating B as {circumflex over (B)}, estimating B comprising:
defining Z, such that Z=B−WW T , such that matrix manipulation and substitution yields (Y−AX)(Y−AX) T =CBC T +CZC T ;
modeling B as a linear function of a parameter vector r, such that V x =Hr+D Z , wherein V x is a column vector comprising (Y−AX)(Y−AX) T stacked, Z is a column vector comprising Z stacked, H is a matrix of rank equal to the dimension of r, and D is a matrix;
estimating r as {circumflex over (r)} using {circumflex over (X)}, such that {circumflex over (r)}={circumflex over (r)}(x)=(H T H) − H T V x ;
calculating {circumflex over (B)} using {circumflex over (r)}; and
iteratively calculating {circumflex over (X)} using {circumflex over (B)} and calculating {circumflex over (B)} using {circumflex over (X)} until the estimates of {circumflex over (X)} and {circumflex over (B)} both converge.
5. The method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network of claim 2 , wherein iteratively estimating X and B comprises:
estimating X as {circumflex over (X)}, such that:
{circumflex over (X)}={circumflex over (X)} ( Y,B )=( A T ( CBC T ) −1 A ) −1 A T ( CBC T ) −1 Y,
using an estimate of B, the initial estimate being B=I, I being the identity matrix;
estimating B as {circumflex over (B)}, estimating B comprising:
estimating W as Ŵ, such that:
Ŵ ( k )=( A ′( k )) T ( A ′( k )( A ′( k )) T ) −1 ( Y ′( k )− A ′( k ) X );
calculating {circumflex over (B)} as {circumflex over (B)}=E[ŴŴ T ]; and
iteratively calculating {circumflex over (X)} using {circumflex over (B)} and calculating {circumflex over (B)} using {circumflex over (X)} until the estimates of {circumflex over (X)} and {circumflex over (B)} both converge.
6. The method for estimating the mean traffic and the covariance of the traffic between nodes of an IP network of claim 5 , wherein if E[W p (k)W q (k+m)]=0 for p≠q and m≠0; estimating B as {circumflex over (B)} comprises:
defining:
{circumflex over (B)}=E [( W p ( k )) 2 ]=Var ( W P ( k ))=τ p 2 ; and
estimating σ p 2 as {circumflex over (σ)} p 2 , such that
σ
^
P
2
=
1
K
∑
K
-
1
k
=
0
(
W
^
p
(
k
)
)
2
.
7. The method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network of claim 5 , wherein estimating W comprises estimating the autocorrelation function of the traffic fluctuations without assuming that the traffic fluctuations are uncorrelated in time.
8. The method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network of claim 2 , wherein collecting link utilization values at different times denoted k comprises collecting link utilization values daily.
9. The method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network of claim 4 , wherein collecting link utilization values at different times denoted k comprises collecting link utilization values daily.
10. The method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network of claim 5 , wherein collecting link utilization values at different times denoted k comprises collecting link utilization values daily.
11. A computer readable media for causing a computer to perform a method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network, the method for estimating the mean traffic and the covariance of traffic comprising:
collecting link utilization values at different times denoted k, wherein k=0, 1, 2, . . . , K−1;
constructing link count vectors Y(k) using the collected link utilization values;
constructing routing matrices A(k) using the IP network's topological information and the weight assigned to each link in the IP network at each time k, such that Y(k)=A(k)X(k);
deleting missing and redundant rows in Y(k) and in A(k) to produce Y′(k) and A′(k), such that Y′(k)=A′(k)X(k);
modeling the traffic matrix X(k) as stationary, such that X(k)=X+W(k), wherein W(k) is a traffic fluctuation vector and X is a vector describing the mean traffic between each origin-destination node pair in the IP network;
defining, in block matrix notation:
Y
=
[
Y
′
(
0
)
Y
′
(
1
)
…
Y
′
(
K
-
1
)
]
;
A
=
[
A
′
(
0
)
A
′
(
1
)
…
A
′
(
K
-
1
)
]
;
and
estimating X, the vector describing the mean traffic between each origin-destination node pair in the IP network, as {circumflex over (X)}, such that {circumflex over (X)}=(A T A) −1 A T Y.
12. A computer readable media for causing a computer to perform a method for estimating the mean traffic and the covariance of traffic between origin-destination node pairs of an IP network comprising a plurality of nodes connected by a plurality of links, each link being assigned a weight used to determine the shortest path route between each origin-destination node pairs, the shortest path route being the set of links connecting the nodes having the lowest possible sum of weights, the traffic matrix describing the total amount of traffic between each origin-destination node pair in the network over a given time period k being X(k), the method comprising:
collecting link utilization values at different times denoted k, wherein k=0, 1, 2, . . . , K−1;
constructing link count vectors Y(k) using the collected link utilization values;
constructing routing matrices A(k) using the IP network's topological information and the weight assigned to each link in the IP network at any time k, such that Y′(k)=A′(k)X(k);
deleting missing and redundant rows in Y(k) and in A(k) to produce Y′(k) and A′(k), such that Y′(k)=A′(k)X(k);
modeling the traffic matrix as stationary, such that X(k)=X+W(k), wherein W(k) is a traffic fluctuation matrix and X is a vector describing the mean traffic between each origin-destination node pair in the IP network;
defining, in block matrix notation:
Y
=
[
Y
′
(
0
)
Y
′
(
1
)
…
Y
′
(
K
-
1
)
]
;
A
=
[
A
′
(
0
)
A
′
(
1
)
…
A
′
(
K
-
1
)
]
;
W
=
[
W
(
0
)
W
(
1
)
…
W
(
K
-
1
)
]
;
and
C
=
[
A
′
(
0
)
0
…
0
0
A
′
(
1
)
…
0
…
…
…
…
0
0
…
A
′
(
K
-
1
)
]
;
defining B as the covariance matrix of W, such that B=E[WW T ]; and
iteratively estimating X, the vector describing the mean traffic between each origin-destination node pair in the IP network, and B, the covariance of the traffic fluctuation matrix.
13. The computer readable media of claim 12 , wherein estimating x comprises defining as an estimate {circumflex over (X)}, such that:
{circumflex over (X)}={circumflex over (X)} ( Y,B )=( A T ( CBC T ) −1 A ) −1 A T ( CBC T ) −1 Y.
14. The computer readable media of claim 12 , wherein iteratively estimating X and B comprises:
estimating X as {circumflex over (X)}, such that:
{circumflex over (X)}={circumflex over (X)} ( Y,B )=( A T ( CBC T ) −1 A ) −1 A T ( CBC T ) −1 Y,
using an estimate of B, the initial estimate being B=I, I being the identity matrix;
estimating B as {circumflex over (B)}, estimating B comprising:
defining Z, such that Z=B−WW T , such that matrix manipulation and substitution yields (Y−AX)(Y−AX) T =CBC T +CZC T ;
modeling B as a linear function of a parameter vector r, such that V x =Hr+D Z , wherein V x is a column vector comprising (Y−AX)(Y−AX) T stacked, Z is a column vector comprising Z stacked, H is a matrix of rank equal to the dimension of r, and D is a matrix;
estimating r as {circumflex over (r)} using {circumflex over (X)}, such that {circumflex over (r)}={circumflex over (r)}(X)=(H T H) −1 H T V X ;
calculating {circumflex over (B)} using {circumflex over (r)}; and
iteratively calculating {circumflex over (X)} using {circumflex over (B)} and calculating {circumflex over (B)} using {circumflex over (X)} until the estimates of {circumflex over (X)} and {circumflex over (B)} both converge.
15. The computer readable media of claim 12 , wherein iteratively estimating X and B comprises:
estimating X as {circumflex over (X)}, such that:
{circumflex over (X)}={circumflex over (X)} ( Y,B )=( A T ( CBC T ) −1 A ) −1 A T ( CBC T ) −1 Y,
using an estimate of B, the initial estimate being B=I, I being the identity matrix;
estimating B as {circumflex over (B)}, estimating B comprising:
estimating W as Ŵ, such that:
Ŵ ( k )=( A ′( k )) T ( A ′( k )( A ′( k )) T ) −1 ( Y ′( k )− A ′( k ) X );
calculating {circumflex over (B)} as {circumflex over (B)}=E[ŴŴ T ]; and
iteratively calculating {circumflex over (X)} using {circumflex over (B)} and calculating {circumflex over (B)} using {circumflex over (X)} until the estimates of {circumflex over (X)} and {circumflex over (B)} both converge.
16. The computer readable media of claim 15 , wherein if E[W p (k)W q (k+m)]=0 for p≠q and m≠0; estimating B as {circumflex over (B)} comprises:
defining:
{circumflex over (B)}=E [( W p ( k )) 2 ]=Var ( W P ( k ))=σ p 2 ; and
estimating σ p 2 as {circumflex over (σ)} p 2 , such that
σ
^
P
2
=
1
K
∑
K
-
1
k
=
0
(
W
^
p
(
k
)
)
2
.
17. The computer readable media of claim 15 , wherein estimating W comprises estimating the autocorrelation function of the traffic fluctuations without assuming that the traffic fluctuations are uncorrelated in time.
18. The computer readable media of claim 12 , wherein collecting link utilization values at different times denoted k comprises collecting link utilization values daily.
19. The computer readable media of claim 14 , wherein collecting link utilization values at different times denoted k comprises collecting link utilization values daily.
20. The computer readable media of claim 15 , wherein collecting link utilization values at different times denoted k comprises collecting link utilization values daily.