Patent ID: 7363386

Claim:
A method for estimating the mean traffic between nodes 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 pair, 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 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 a link count vector Y(k) using the collected link utilization values; constructing a routing matrix A(k) using the weight assigned to each link in the communication 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 X(k) as non-stationary, such that: X(k)=x(k)+W(k), wherein x(k) is a vector function of k describing the mean traffic between each origin-destination node pair in the IP network; and W(k) is a traffic fluctuation vector, and wherein: {X(k)} is cyclo-stationary with a period designated N; {W(k)} is cyclo-stationary to the second order, such that E[W(k)W T (k+m)]=B (k,m) , wherein covariance matrices B (k,m) are such that B (k,m) =B (k+N),m ; W(k) is zero mean; and X(k) is a deterministic sequence with a period N; modeling x(k) as the weighted sum of 2N b +1 basis functions, such that x ⁡ ( k ) = ∑ n = 0 2 ⁢ N b ⁢ θ n ⁢ b n ⁡ ( k ) , wherein θ n is a p×1 vector θ n =[θ 1n θ 2n . . . θ pn ] T and b n is a scalar periodic basis function having period N; defining b n (k), such that: b n ⁡ ( k ) = { cos ⁡ ( 2 ⁢ π ⁢ ⁢ kn / N ) , if ⁢ ⁢ 0 ≤ k < N ⁢ ⁢ and ⁢ ⁢ 0 ≤ n ≤ N b sin ⁡ ( 2 ⁢ π ⁢ ⁢ k ⁡ ( n - N b ) / N ) , if ⁢ ⁢ 0 ≤ k < N ⁢ ⁢ and ⁢ ⁢ N b + 1 ≤ n ≤ 2 ⁢ N b ; defining θ as a (2N b +1)P×1 vector, such that: θ = [ θ 0 θ 1 … θ 2 ⁢ N b ] ; defining A″(k) as the M k ×(2N b +1)P matrix, such that: A″(k)=[A′(k)b 0 (k) A′(k)b 1 (k) . . . A′(k)b 2N b (k)], such that by matrix manipulation and substitution Y′(k)=A″(k)θ+A′(k)W(k); redefining matrix A to be of dimension M×(2N b +1)P such that: A = [ A ″ ⁡ ( 0 ) A ″ ⁡ ( 1 ) … A ″ ⁡ ( K - 1 ) ] ; defining : Y = [ Y ′ ⁡ ( 0 ) Y ′ ⁡ ( 1 ) … Y ′ ⁡ ( 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 ) ] ; such that by substitution Y=Aθ+CW; estimating θ as {circumflex over (θ)}, such that {circumflex over (θ)}=(A T A) −1 A T Y; and using {circumflex over (θ)} to calculate an estimate of x(k).