Forward looking infrastructure re-provisioning

[0001] This application claims benefit of co-pending U.S. Provisional Application No. 60/368,930, filed Mar. 29, 2002, which is entirely incorporated herein by reference. In addition, this application is related to the following co-pending, commonly assigned U.S. applications, each of which is entirely incorporated herein by reference: Methods for Identifying Network Traffic Flows filed Mar. 31, 2003, and accorded Publication No. ______; and Systems and Methods for End-to-End Quality of Service Measurements in a Distributed Network Environment filed Mar. 31, 2003, and accorded Publication No. ______.

[0002] The field of the present invention relates generally to systems and methods for metering and measuring the performance of a distributed network. More particularly, the present invention relates to systems and methods for determining predicted values for performance metrics in a distributed network environment.

[0003] Network metering and monitoring systems are employed to measure network characteristics and monitor the quality of service (QoS) provided in a distributed network environment. In general, quality of service (QoS) in a distributed network environment is determined by fixing levels of service for performance of an application and the supporting network infrastructure. Examples of service level metrics include round trip response time, packet inter-arrival delays, and latencies across networks. By setting upper limit thresholds on performance levels, Service Level Agreements (SLA) can be derived that simultaneously benefit the application user community and can be met by the application and network service providers. While current network metering and monitoring systems are able to determine when a SLA has been violated, what is need is a system and method for predicting a SLA violation prior to the occurrence thereof. The ability to predict SLA violations would provide an opportunity to reprovision the network infrastructure in an attempt to avoid an actual SLA violation.

[0004] The present invention provides systems and methods for predicting expected service levels based on measurements relating to network traffic data. Measured network performance characteristics can be converted to metrics for quantifying network performance. Certain metrics are functions of more than one measured performance characteristics. For example, bandwidth, latency, and utilization of the network segments, as well as computer processing time, all combine to govern the response time of an application.

[0005] The response time metric may be described as a service level metric whereas bandwidth, latency, utilization and processing delays may be classified as component metrics of the service level metric. Service level metrics have certain entity relationships with their component metrics that may be exploited to provide a predictive capability for service levels and performance. The present invention involves system and methods for processing metrics representing current conditions in a network, in order to predict future values of those metrics. Based on predicted service level information, actions may be taken to avoid violation of a service level agreement including, but not limited to, deployment of network engineers, re-provisioning equipment, identifying rogue elements, etc.

[0006] Additional embodiments, examples, variations and modifications are also disclosed herein.

[0007] FIG. 1 illustrates a simple linear regression model using periodic samples of a typical component metric.

[0008] FIG. 2 illustrates a least squares fit calculation for component metric sampled data.

[0009] FIG. 3 illustrates a multiple regression model for periodic samples of multiple component metrics.

[0010] FIG. 4 shows a least squares fit calculation for each component metric in the multiple regression model.

[0011] FIG. 5 illustrates a model for predicting a service level metric.

[0012] As mentioned, the quality of service (QoS) delivered in a distributed network environment can be determined by fixing levels of service for performance of an application and supporting network infrastructure. Examples of service level metrics include round trip response time, packet inter-arrival delays, and latencies across networks. By setting upper limit thresholds on performance levels, Service Level Agreements (SLA) can be derived that simultaneously benefit the application user community and can be met by the application and network service providers. The present invention provides systems and methods for early warning of possible SLA violations in order to permit re-provisioning of network resources. Re-provisioning of network resources in response to a predicted SLA violation will reduce the chance of an actual SLA violation.

[0013] The present invention operates in conjunction with a network metering and monitoring system that is configured to measure performance characteristics within a network environment and to convert such measured performance characteristics into metrics. Although the present invention may be used in connection with any suitable network metering and monitoring system, a preferred embodiment of the invention is described in connection with a system known as PerformanceDNA, which is proprietary to Network Genimics, Inc. of Atlanta Georgia. Broadly described, PerformanceDNA is a system for providing end-to-end network, traffic, and application performance management within an integrated framework. PerformanceDNA manages SLA and aggregated quality of service (AQoS) for software applications hosted on and accessed over computer networks.

[0014] Using PerformanceDNA, service level metrics can be monitored and measured in real time to report conformance and violation of the service level agreements. PerformanceDNA measures and calculates service level metrics directly by periodically collecting data at instrumentation access points (IAPs) strategically placed throughout a software applications' supporting network infrastructure. Certain aspects of the PerformanceDNA system are describe in greater detail in U.S. Patent Applications titled Methods for Identifying Network Traffic Flows and Systems and Methods for End-to-End Quality of Service Measurements in a Distributed Network Environment, both filed on Mar. 31, 2003, and assigned Publication Nos. ______ and ______, respectively.

[0015] Variation in measured samples of a typical service level metric (e.g. system state) are caused by measurement uncertainties and system uncertainties. Measurement uncertainty is governed by errors in the measurement itself and is referred to as measurement noise. The system uncertainty is governed by random processes that perturb an otherwise constant system state (i.e. constant service level metric). The system uncertainty results from a wide variety of phenomena such as:

[0016] Collisions in multi-access protocol links

[0017] Error rates in the end-to-end transmission channel

[0018] Queueing delays for access to links and processors caused by congestion

[0019] Variable routes with variable bandwidth, queueing, and processing delays

[0020] Variable bytes transferred for bi-directional traffic

[0021] Availability of devices

[0022] Under ideal conditions, i.e., constant bandwidth with no congestion, no errors in the end-to-end transmission channel, a fixed number of bytes to be transferred in the bi-directional traffic, constant processing and switching speeds, etc., service level metrics can be calculated deterministically. However, application traffic on computer networks is never subject to ideal conditions. In general, it can be said that the system uncertainty results from the sum of many random variables, such as those listed above, whose distributions may or may not be known and are compounded by multiple users of the network infrastructure. The net result is to shift the service level metric of interest away from its ideal to a worse value and cause even more variation in the measured samples than that caused by the measurement noise. In addition, the same random processes may cause the service level metric of interest to exhibit a slope as it changes in response to changing conditions in the underlying network infrastructure.

[0023] In accordance with certain preferred embodiments of the present invention, time series analysis may be applied to the service level metrics collected by a network metering and monitoring system. Exemplary time series analysis techniques include, but are not limited to, an exponentially weighted moving average filter, Kalman filtering, or regression analysis. Applying time series analysis to a service level metric allows the trend of the service level metric to be monitored and used to derive the predicted next sample (PNS) of the metric. The PNS is then compared to definable thresholds in order to provide early warning of a potential SLA violation.

[0024] Some service level metrics that are measured directly are also functions of other measured performance characteristics. For example, the bandwidth, latency, and utilization of the network segments as well as the computer processing delays in the end-to-end path of an applications' transmitted and received packets will govern the round-trip response time of the application. While round-trip response time is a service level metric monitored, measured and reported by PerformanceDNA, the component metrics that govern response time are measured as well. Service level metrics may have entity relationships with component metrics, which are defined by weighted combinations of the component metrics. By monitoring the component metrics, performing time series analysis on them to get their PNS and weighting the importance of their contribution to the service level metric of interest, an early warning estimate of an SLA violation is derived.

[0025] FIG. 1 illustrates a simple linear regression model using periodic samples of a typical component metric. From simple linear regression, an optimal form of the linear equation (1) may be determined based on the measured samples of a component metric, y_i, at times, x_i, with random errors, _i:

[0026] The random errors, _i, typically are assumed to be normally distributed with zero mean and variance ².

[0027] By minimizing the sum of the squares of the error term, $\underset{i=1}{\overset{n}{}}{}_i^2,$

[0028] estimates of the regression coefficients, ₀ and ₁, can be derived and are given by:

[0029] $\begin{array}{cc}{\hat{}}_1=\frac{\underset{i=1}{\overset{n}{}}{y}_i{x}_i-\frac{\left(\underset{i=1}{\overset{n}{}}{y}_i\right)\left(\underset{i=1}{\overset{n}{}}{x}_i\right)}{n}}{\underset{i=1}{\overset{n}{}}{x}_i^2-\frac{{\left(\underset{i=1}{\overset{n}{}}{x}_i\right)}^2}{n}}& \left(3\right)\\ \mathrm{where}\stackrel{\_}{y}=\frac{\underset{i=1}{\overset{n}{}}{y}_i}{n}& \left(4\right)\\ \mathrm{and}\stackrel{\_}{x}=\frac{\underset{i=1}{\overset{n}{}}{x}_i}{n}& \left(5\right)\end{array}$

[0030] Estimates of the component metric, y, can be obtained at any value of x (time) over the interval of the regression. Predictions can be made beyond the interval with more uncertainty.

[0031] FIG. 2 illustrates a least squares fit calculation for component metric sampled data.

[0032] When multiple component metrics are involved, their equations may be estimated and used for multiple regression for the service level metrics of interest. FIG. 3 illustrates a multiple regression model for periodic samples of multiple component metrics. Using the same analysis as in simple linear regression model described above, for k different component metrics the model would have the following equations: $\begin{array}{cc}\begin{array}{c}{\hat{y}}_1={\hat{}}_{01}+{\hat{}}_{11}x\\ {\hat{y}}_2={\hat{}}_{02}+{\hat{}}_{12}x\\ \\ {\hat{y}}_k={\hat{}}_{0k}+{\hat{}}_{1k}x\end{array}& \left(7\right)\end{array}$

[0033] FIG. 4 shows a least squares fit calcualtion for each component metric in the multiple regression model.

[0034] Assume that measurements have yeilded j samples of a service level metric of interest at j different times within the regression interval (data collection interval), z₁,z₂, . . . , z_j, that is related to the component metrics. To find the relationship between the k component metrics, (7), and the service level metric of interest, z, the component metric estimates are needed at the same j sampling times as the service level metric samples. Therefore, the values of the k component metrics at the same j measurement times as the service level metric samples are sought.

	component 1	component 2		component k
Time 1	11 {circumflex over ()}01 {circumflex over ()}11x1	12 {circumflex over ()}02 {circumflex over ()}12x1	. . .	1k {circumflex over ()}0k {circumflex over ()}1kx1
Time 2	21 {circumflex over ()}01 {circumflex over ()}11x2	22 {circumflex over ()}02 {circumflex over ()}12x2	. . .	2k {circumflex over ()}0k {circumflex over ()}1kx2
.	.	.		.
.	.	.		.
.	.	.		.
Time j	j1 {circumflex over ()}01 {circumflex over ()}11xj	j2 {circumflex over ()}02 {circumflex over ()}12xj	. . .	jk {circumflex over ()}0k {circumflex over ()}1kxj (8)

[0035] A multiple linear regression model can be formulated for the service level metric of interest, where jk1, using the form: $\begin{array}{cc}\begin{array}{c}{z}_1={}_0+{}_1{\hat{y}}_{11}+{}_2{\hat{y}}_{12}++{}_k{\hat{y}}_{1k}\\ z_2={}_0+{}_1{\hat{y}}_{21}+{}_2{\hat{y}}_{22}++{}_k{\hat{y}}_{2k}\\ \\ z_j={}_0+{}_1{\hat{y}}_{\mathrm{j1}}+{}_2{\hat{y}}_{\mathrm{j2}}++{}_k{\hat{y}}_{\mathrm{jk}}\end{array}& \left(9\right)\end{array}$

[0036] Those skilled in the art will appreciate, however, that other multiple regression models are possible. For example a polynomial regression may best fit certain types of data.

[0037] Using matrix notation, where $\begin{array}{cc}\begin{array}{cccc}Z=\left[\begin{array}{c}{z}_1\\ z_2\\ \\ z_j\end{array}\right],& Y=\left[\begin{array}{ccccc}1& {\hat{y}}_{11}& {\hat{y}}_{12}& & {\hat{y}}_{1k}\\ 1& {\hat{y}}_{21}& {\hat{y}}_{22}& & {\hat{y}}_{2k}\\ & & & & \\ 1& {\hat{y}}_{\mathrm{j1}}& {\hat{y}}_{\mathrm{j2}}& & {\hat{y}}_{\mathrm{jk}}\end{array}\right],& \mathrm{and}& A=\left[\begin{array}{c}{}_0\\ {}_1\\ \\ {}_k\end{array}\right],\end{array}& \left(10\right)\end{array}$

[0038] equation (9) becomes:

[0039] The solution for the regression coefficients, ₁, ₂, . . . , _k, is given by:

[0040] At some future time, x_p, an estimate of the service level metric of interest is given by:

[0041] where

[0042] An estimate of the variance, {circumflex over ()}², of the service level metric of interest is given by: $\begin{array}{cc}{\hat{}}^2=\frac{\underset{i=1}{\overset{j}{}}{e}_i^2}{j-k-1}=\frac{\underset{i=1}{\overset{j}{}}{\left(z_i-{\hat{z}}_i\right)}^2}{j-k-1}& \left(15\right)\end{array}$

[0043] A probability may be assigned to the predicted service level metric of interest exceeding a certain threshold value, T, that represents a service level agreement. FIG. 5 illustrates a model for predicting a service level metric. The line in FIG. 5 that passes through the points (x₁,z₁) and (x₂,z₂) is the regression line for the service level metric of interest. The point (x₁,z₁) is the end of the regression interval used to model the service level metric and the point (x₂,z₂) is the predicted service level metric (PSLM). The actual value of the service level metric at time, x₂, will be normally distributed about the mean, z₂. The probability of the PSLM being below the threshold is the area under the normal probability density function from to T, i.e., Prob ZT. Therefore, the probability that the PSLM will exceed the threshold, T, is simply ProbZ>T1ProbZT.

[0044] The normal probability density function (pdf) is given by, $\begin{array}{cc}{f}_Z\left(z\right)=\frac{1}{\sqrt{2}{}_{\stackrel{\_}{z}}}{}^{-\frac{{\left(z-\stackrel{\_}{z}\right)}^2}{2{}_{\stackrel{\_}{z}}^2}},& \left(16\right)\end{array}$

[0045] for which the cumulative distribution function is: $\begin{array}{cc}{F}_Z\left(z\right)={}_{-}^z{f}_Z\left(u\right)u={}_{-}^z\frac{1}{\sqrt{2}{}_{\stackrel{\_}{z}}}{}^{-\frac{{\left(u-\stackrel{\_}{z}\right)}^2}{2{}_{\stackrel{\_}{z}}^2}}u.& \left(17\right)\end{array}$ $\mathrm{Let}w=\frac{u-\stackrel{\_}{z}}{{}_{\stackrel{\_}{z}}},$

[0046] and substitute in order to derive the unit normal form of the pdf. Upon substituting w, we have $\begin{array}{cc}{F}_W\left(w\right)={}_{-}^w\frac{1}{\sqrt{2}}{}^{-\frac{u^2}{2}}u,\mathrm{where}\stackrel{\_}{w}=0\mathrm{and}{}_{\stackrel{\_}{w}}^2=1.& \left(18\right)\end{array}$

[0047] where {overscore (w)}0 and _{{overscore (w)}}²1.

[0048] This integral is given by:

[0049] where the error function, erf (w), is tabulated or approximated with a series expansion or polynomial function.

[0050] Now, the ProbZ>T1ProbZT is $\begin{array}{cc}\begin{array}{c}\mathrm{Now},\mathrm{the}\mathrm{Prob}\left\{Z>T\right\}=1-\mathrm{Prob}\left\{ZT\right\}\mathrm{is}\\ =1-\mathrm{erf}\left(w\right)\mathrm{where}w=\frac{T-\stackrel{\_}{z}}{{}_{\stackrel{\_}{z}}}.\end{array}& \left(20\right)\end{array}$

[0051] When w>0, then the PSLM is below the threshold and therefore, $\begin{array}{cc}\mathrm{Prob}\left\{Z>T\right\}=1-\mathrm{erf}\left(\frac{T-\stackrel{\_}{z}}{{}_{\stackrel{\_}{z}}}\right).& \left(21\right)\end{array}$

[0052] When w<0, then the PSLM is above the threshold,

[0053] Therefore,

[0054] $\begin{array}{cc}\mathrm{Prob}\left\{Z>T\right\}=1-\mathrm{erf}\left(-w\right).& \left(23\right)\\ =1-\left(1-\mathrm{erf}\left(w\right)\right)& \left(24\right)\\ =\mathrm{erf}\left(w\right)& \left(25\right)\\ =\mathrm{erf}\left(\frac{T-\stackrel{\_}{z}}{{}_{\stackrel{\_}{z}}}\right)& \left(26\right)\end{array}$

[0055] In equations (21) and (26):

[0056] T is a constant>0 provided by a service level agreement,

[0057] {overscore (z)} is the predicted service level metric computed by the algorithm in equation (13) at any fixed time beyond the regression interval,

[0058] _{{overscore (z)}} is the standard deviation computed by the algorithm as the square root of equation (15).

[0059] The foregoing represents a closed form solution for predicting a future service level metric of interest as a function of measured component metrics and its probability of exceeding a given service level agreement, in accordance with preferred embodiments of the present invention. Additional closed form solutions may also be derived, as described above. The present invention provides one or more software modules for performing the above or similar calculations based on measured component metrics that are supplied by a network metering and monitoring system. Such software modules may be executed by a network server or other suitable network device. Generally, a software module comprises computer-executable instructions stored on a computer-readable medium. The software modules of the present invention may be further configured to provide a forward-looking mechanism that permits re-provisioning of a network infrastructure in the event of a predicted service level breach.

[0060] From a reading of the description above pertaining to various exemplary embodiments, many other modifications, features, embodiments and operating environments of the present invention will become evident to those of skill in the art. The features and aspects of the present invention have been described or depicted by way of example only and are therefore not intended to be interpreted as required or essential elements of the invention. It should be understood, therefore, that the foregoing relates only to certain exemplary embodiments of the invention, and that numerous changes and additions may be made thereto without departing from the spirit and scope of the invention as defined by any appended claims.