US 7,353,294 B1Granted

Method for estimating a traffic matrix in a communication network using stationary data

AssigneeSprint Communications Company L.P.

InventorsAntonio Nucci, Nina Taft

Life of this patent

Estimating the term…

Abstract

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.

Claims20

Dependent claims

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)}=(ATA)−1ATY.

57 more elements

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[WWT];
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.

120 more elements

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[WWT];
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.

120 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract