Method and apparatus for integration of traffic measurement and queueing performance evaluation in a network system

Claim 2

A computer-implemented method for modeling and analyzing traffic flow in a network node, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral function from said real traffic data; generating a stochastic model of a nonnegative rate random process using frequency domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral function, wherein said step of generating uses linear programming techniques; inputting said nonnegative rate random process in a queue of said network node after said step of generating; performing queuing analysis on said queue to determine a design of the network node; and constructing said network node using said design.

Claim 3

The method of claim 1, wherein said step of generating comprises: constructing a transition rate vector α of a circulant-modulated-rate process to statistically match said power spectral function; and constructing an input rate vector γ of said circulant-modulated-rate process to statistically match said steady state distribution function.

Claim 4

The method of claim 2, wherein said step of constructing said transition rate vector α comprises the steps of: a. performing parametric signal processing methods to express said power spectral function in analytical form defined by vectors (λ,ψ); b. adjusting and expanding said vectors (λ,ψ) to new vectors (λ E ,ψ E ), wherein ψ E is a non-negative real vector, wherein said new vectors define an adjusted power spectral function, and wherein said step of adjusting and expanding minimizes the difference between said power spectral function of (λ,ψ) and said adjusted power spectral function of (λ E ,ψ E ); c. eliminating bell components of said adjusted power spectral function that are either in the high frequency band or that have negligible power, wherein said step of eliminating produces a new vector of key eigenvalues, λ key .OR right.λ E ; d. expanding said vector λ key to an expanded new vector λ c with λ c .OR left.λ key adding noneffective eigenvalues, wherein the power of said noneffective eigenvalues are set at zero as defined in a power vector ψ c , to obtain said transition rate vector α of a discrete Fourier transform problem ##EQU69## subject to α j ≧0 for j>0 and α 0 =-Σ j=1 N-1 α j ; e. transforming said problem of finding α into a linear programming problem under the condition of said vector λ key ; f. obtaining a solution of α, wherein said step of obtaining comprises one or more of the steps of: adaptively changing indices of said key eigenvalues in λ c ; and gradually expanding the dimension of λ c ; g. obtaining one or more solutions of α, h. determining a solution of α having a reasonable dimension, wherein said solution of α produces a solution of λ c ; i. determining said power vector ψ c using said solution of λ c , wherein said power vector ψ c minimizes the difference between said power spectral function of (λ,ψ) and a constructed power spectral function of (λ c ,ψ c ).

Claim 5

The method of claim 3, wherein said steady state distribution function includes a steady state rate density function f(χ) and a steady state cumulative function F(χ), wherein said steady state rate density function and said steady state cumulative function are functions of a rate χ: wherein said step of constructing said input rate vector γ comprises constructing said input rate vector γ of said circulant-modulated-rate process to statistically match said steady state rate cumulative function.

Claim 6

The method of claim 4, wherein said step of constructing said input rate vector γ comprises the steps of: a. discretizing said steady state rate cumulative function F(χ) by partitioning a range of χ into a set of N equal-probability rates, denoted by a distribution vector γ' in ascending order; b. determining said input rate vector γ by taking discrete Fourier transform, γ=√NβF, subject to γ j ≧0, ∀j with β j =√ψ j e.sup.√-1θ.sbsb.j, with respect to one or more selected phase vectors θ c for said power vector ψ c ; c. adjusting said one or more phase vectors θ c to determine said input rate vector γ that minimizes the difference between said steady state rate cumulative function F(χ) of said distribution vector γ' and a distribution function F c (χ) constructed from said input rate vector γ, wherein said step of adjusting said phase vectors θ c to determine said input rate vector γ is formulated into a minimization problem: min.sub.θ.sbsb.c ∥γ'-γ p ∥ subject to γ p ≧0 where γ p is a sorted vector of said input rate vector γ in ascending order; d. obtaining one or more solutions of said phase vector θ c ; e. determining a solution from said one or more solutions of said phase vector θ c which provides an acceptable matching error.

Claim 7

The method of claim 5, further comprising the steps of: readjusting said power of said noneffective eigenvalues in said power vector ψ c to further reduce distribution matching error after said step of determining a solution from said one or more solutions of said phase vector, wherein said step of readjusting does not cause significant impact on power spectral matching; assigning said sorted vector γ p equal to said distribution vector γ' after said step of determining a solution from said one or more solutions of said phase vector, wherein said step of assigning alters said power vector ψ c in some degree without changing said phase vector θ c , wherein said step of assigning introduces extra power spectral matching errors; and partitioning a pair of said power vector and said phase vector (ψ c ,θ c ) into two parts, comprising a pair of a low frequency power vector and a low frequency phase vector (ψ l ,θ l ), and a pair of high frequency power vector and a high frequency phase vector (ψ h ,θ h ), such that said pair of low frequency power vector and said low frequency phase vector (ψ l ,θ l ) are used to match input rate distribution of said steady state cumulative rate function F(χ) in the low frequency band and said pair of said high frequency power vector and said high frequency phase vector (ψ h ,θ h ) are used to match input rate distribution of said steady state rate cumulative function F(χ) in the high frequency band.

Claim 8

The method of claim 1, wherein said step of performing comprises performing queueing analysis to determine optimal design of link capacity and buffer size of the network node.

Claim 9

The method of claim 1, wherein said step of computing includes filtering out unwanted statistical data.

Claim 10

The method of claim 1, wherein said step of performing queueing analysis uses a generalized Folding-algorithm.

Claim 11

The method of claim 9, wherein said step of performing queueing analysis using said generalized Folding-algorithm comprises the steps of: performing transient and time-dependent analysis of said network queue.

Claim 12

The method of claim 10, wherein said step of performing queueing analysis generates a K-level block tri-diagonal matrix and a K-level vector; and wherein said step of performing queueing analysis using said generalized Folding-algorithm comprises the steps of: performing a reduction phase which reduces said K-level block tri-diagonal matrix and said K-level vector to a one-level block matrix and a one-level vector by a sequence of permutation-reduction steps; determining a boundary solution vector from said one-level block matrix and said one-level vector; performing an expansion phase which is a reverse process of said reduction phase to obtain a sequence of expansion factors; determining a final solution as a product of said boundary solution vector and said expansion factors.

Claim 13

The method of claim 1, wherein said step of performing queueing analysis uses a non-generalized Folding-algorithm.

Claim 14

The method of claim 1, wherein said step of performing queueing analysis uses computer simulation methods.

Claim 15

A computer-implemented method for modeling and analyzing traffic flow in a network of multiple interconnected nodes, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral function from said real traffic data; generating a stochastic model of a nonnegative rate random process using frequency domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral function, wherein said step of generating uses linear programming techniques; inputting said nonnegative rate random process in a queue of each of said multiple interconnected nodes after said step of generating; performing network analysis on one or more of said multiple interconnected nodes to determine information regarding design of said network of multiple interconnected nodes; and constructing said network of multiple interconnected nodes using said determined information.

Claim 16

A computer-implemented method for modeling and analyzing traffic flow in a network of multiple interconnected nodes, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral function from said real traffic data; generating a stochastic model of a nonnegative rate random process using frequency domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral function, wherein said step of generating uses linear programming techniques; inputting said nonnegative rate random process in a queue of each of said multiple interconnected nodes after said step of generating; performing network analysis on one or more of said multiple interconnected nodes to determine information regarding design of said network of multiple interconnected nodes; and constructing said network of multiple interconnected nodes using said determined information.

Claim 17

The method of claim 14, wherein said step of performing comprises determining routing, call admission, and load balancing information about said network of multiple interconnected nodes.

Claim 18

A computer-implemented method for generating traffic in a network for network simulation and performance evaluation, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral function from said real traffic data; generating a stochastic model of a nonnegative rate random process using frequency domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral function, wherein said step of generating uses linear programming techniques, wherein said nonnegative rate random process comprise network traffic which may be input to a network for network simulation and performance evaluation; and inputting said nonnegative rate random process in said network after said step of generating.

Claim 19

A computer-implemented method for generating traffic in a network for network simulation and performance evaluation, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral function from said real traffic data; generating a stochastic model of a nonnegative rate random process using frequency domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral function, wherein said step of generating uses linear programming techniques, wherein said nonnegative rate random process comprise network traffic which may be input to a network for network simulation and performance evaluation; and inputting said nonnegative rate random process in said network after said step of generating.

Claim 20

A computer-implemented method for modeling and analyzing traffic flow in a network node, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral/correlation function from said real traffic data; generating a stochastic model of a nonnegative rate random process using time domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral/correlation function, wherein said step of generating uses linear programming techniques; inputting said nonnegative rate random process in a queue of said network node after said step of generating; performing queuing analysis on said queue to determine a design of the network node; and constructing said network node using said design.

Claim 21

A computer-implemented method for modeling and analyzing traffic flow in a network node, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral/correlation function from said real traffic data; generating a stochastic model of a nonnegative rate random process using time domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral/correlation function, wherein said step of generating uses linear programming techniques; inputting said nonnegative rate random process in a queue of said network node after said step of generating; performing queuing analysis on said queue to determine a design of the network node; and constructing said network node using said design.

Claim 22

The method of claim 17, wherein said step of generating comprises: constructing a transition rate vector α of a circulant-modulated-rate process to statistically match said power spectral/correlation function; and constructing an input rate vector γ of said circulant-modulated-rate process to statistically match said steady state distribution function.

Claim 23

The method of claim 18, wherein said step of constructing said transition rate vector α comprises the steps of: a. performing parametric signal processing methods to express said power spectral/correlation function in analytical form defined by vectors (λ,ψ); b. adjusting and expanding said vectors (λ,ψ) to new vectors (λ E , ψ E ), wherein ψ E is a non-negative real vector, wherein said new vectors define an adjusted power spectral/correlation function, and wherein said step of adjusting and expanding minimizes the difference between said power spectral/correlation function of (λ,ψ) and said adjusted power spectral/correlation function of (λ E , ψ E ); c. eliminating bell components of said adjusted power spectral/correlation function that are either in the high frequency band or that have negligible power, wherein said step of eliminating produces a new vector of key eigenvalues, λ key .OR right.λ E ; d. expanding said vector λ key to an expanded new vector λ C with λ C .OR left.λ key by adding noneffective eigenvalues, wherein the power of said noneffective eigenvalues are set at zero as defined in a power vector ψ c , to obtain said transition rate vector α of a discrete Fourier transform problem ##EQU70## subject to α j ≧0 for j>0 and α 0 =-Σ j=1 N-1 α j ; e. transforming said problem of finding α into a linear programming problem under the condition of said vector λ key ; f. obtaining a solution of α, wherein said step of obtaining comprises one or more of the steps of: adaptively changing indices of said key eigenvalues in λ c ; and gradually expanding the dimension of λ c ; g. obtaining one or more solutions of α; h. determining a solution of α having a reasonable dimension, wherein said solution of α produces a solution of λ c ; and i. determining said power vector ψ c using said solution of λ c , wherein said power vector ψ c minimizes the difference between said power spectral/correlation function of (λ,ψ) and a constructed power spectral/correlation function of (λ c , ψ c ).

Claim 24

The method of claim 19, wherein said steady state distribution function includes a steady state rate density function f(χ) and a steady state rate cumulative function F(χ), wherein said steady rate density function and said steady state rate cumulative function are functions of a rate χ; wherein said step of constructing said input rate vector γ comprises constructing said input rate vector γ of said circulant-modulated-rate process to statistically match said steady state rate cumulative function.

Claim 25

The method of claim 20, wherein said step of constructing said input rate vector γ comprises the steps of: a. discretizing said steady state rate cumulative function F(χ) by partitioning a range of χ into a set of N equal-probability rates, denoted by a distribution vector γ' in ascending order; b. determining said input rate vector γ by taking discrete Fourier transform, γ=√NβF, subject to γ j ≧0, ∀j with β j =√ψje.sup.√-1θj, with respect to one or more selected phase vectors θ c for said power vector ψ c ; c. adjusting said one or more phase vectors θ c to determine said input rate vector γ that minimizes the difference between said steady state rate cumulative function F(χ) of said distribution vector γ' and a distribution function F c (χ) constructed from said input rate vector γ, wherein said step of adjusting said phase vectors θ c to determine said input rate vector γ is formulated into a minimization problem: minθ c ∥γ'-γ p ∥ subject to γ p ≧0 where γ p is a sorted vector of said input rate vector γ in ascending order; d. obtaining one or more solutions of said phase vector θ c ; e. determining a solution from said one or more solutions of said phase vector θ c which provides an acceptable matching error.

Claim 26

The method of claim 21, further comprising the steps of: readjusting said power of said noneffective eigenvalues in said power vector ψ c to further reduce distribution matching error after said step of determining a solution from said one or more solutions of said phase vector, wherein said step of readjusting does not cause significant impact on power spectral/correlation matching; assigning said sorted vector γ p equal to said distribution vector γ' after said step of determining a solution from said one or more solutions of said phase vector, wherein said step of assigning alters said power vector ψ c in some degree without changing said phase vector θ c , wherein said step of assigning introduces extra power spectral/correlation matching errors; and partitioning a pair of said power vector and said phase vector (ψ c ,θ c ) into two parts, comprising a pair of a low frequency power and a low frequency phase vector (ψ l ,θ l ), and a pair of high frequency power vector and a high frequency phase vector (ψ h ,θ h ), such that said pair of low frequency power vector and said low frequency phase vector (ψ l ,θ l ) are used to match input rate distribution of said steady state cumulative rate function F(χ) in the low frequency band and said pair of said high frequency power vector and said high frequency phase vector (ψ h ,θ h ) are used to match input rate distribution of said steady state rate cumulative function F(χ) in the high frequency band.

Claim 27

The method of claim 17, wherein said step of performing comprises performing queueing analysis to determine optimal design of link capacity and buffer size of the network node.

Claim 28

The method of claim 17, wherein said step of performing includes filtering out unwanted statistical data.

Claim 29

The method of claim 17, wherein said step of performing queueing analysis uses a generalized Folding-algorithm.

Claim 30

The method of claim 25, wherein said step of performing queueing analysis using said generalized Folding-algorithm comprises the steps of: performing transient and time-dependent analysis of said network queue.

Claim 31

The method of claim 26, wherein said step of performing queueing analysis generates a K-level block tri-diagonal matrix and a K-level vector and wherein said step of performing queueing analysis using said generalized Folding-algorithm comprises the steps of: performing a reduction phase which reduces said K-level block tri-diagonal matrix and said k-level vector to a one-level block matrix and a one-level vector by a sequence of permutation-reduction steps; determining a boundary solution vector from said one-level block matrix and said one-level vector; performing an expansion phase which is a reverse process of said reduction phase to obtain a sequence of expansion factors; determining a final solution as a product of said boundary solution vector and said expansion factors.

Claim 32

The method of claim 17, wherein said step of performing queueing analysis uses a non-generalized Folding-algorithm.

Claim 33

The method of claim 17, wherein said step of performing queueing analysis uses computer simulation methods.

Claim 34

A computer-implemented method for modeling and analyzing traffic flow in a network of multiple interconnected nodes, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral/correlation function from said real traffic data; generating a stochastic model of a nonnegative rate random process using time domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral/correlation function, wherein said step of generating uses linear programming techniques; inputting said nonnegative rate random process in a queue of each of said multiple interconnected nodes after said step of generating; performing network analysis on one or more of said multiple interconnected nodes to determine information regarding design of said network of said multiple interconnected nodes; and constructing said network of multiple interconnected nodes using said determined information.

Claim 35

A computer-implemented method for modeling and analyzing traffic flow in a network of multiple interconnected nodes, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral/correlation function from said real traffic data; generating a stochastic model of a nonnegative rate random process using time domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral/correlation function, wherein said step of generating uses linear programming techniques; inputting said nonnegative rate random process in a queue of each of said multiple interconnected nodes after said step of generating; performing network analysis on one or more of said multiple interconnected nodes to determine information regarding design of said network of said multiple interconnected nodes; and constructing said network of multiple interconnected nodes using said determined information.

Claim 36

The method of claim 30, wherein said step of performing comprises determining routing, call admission, and load balancing information about said network of multiple interconnected nodes.

Claim 37

A computer-implemented method for generating traffic in a network for network simulation and performance evaluation, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral/correlation function from said real traffic data; generating a stochastic model of a nonnegative rate random process using time domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral/correlation function, wherein said step of generating uses linear programming techniques, wherein said nonnegative rate random process comprises network traffic which may be input to a network for network simulation and performance evaluation; and inputting said nonnegative rate random process in said network after said step of generating.

Claim 38

A computer-implemented method for generating traffic in a network for network simulation and performance evaluation, comprising the steps of: receiving real traffic data; computing a steady state distribution function and power spectral/correlation function from said real traffic data; generating a stochastic model of a nonnegative rate random process using time domain techniques, wherein said stochastic model matches said computed steady state distribution function and power spectral/correlation function, wherein said step of generating uses linear programming techniques, wherein said nonnegative rate random process comprises network traffic which may be input to a network for network simulation and performance evaluation; and inputting said nonnegative rate random process in said network after said step of generating.