This paper presents a prediction algorithm for estimating the upper bound of future Web traffic volume. Unlike traditional traffic predictions that are performed at a single time scale using curve fitting, we employ a multiple time scale approach and utilize traffic statistical properties to do forecasting. We have applied our prediction algorithm to the 1998 World Cup data set. Experiments show that it is effective for short term traffic bound predictions, applicable to bursty traffic, and useful for Web server overload prevention.
Traffic prediction, upper bound, multiple time scale approach, self-similar, overload prevention.
To provide expected quality of services, a Web site needs to predict its future traffic volume: long term predictions (e.g., in months or years) are useful for capacity planning, while short term predictions (e.g., in seconds or minutes) are useful for overload prevention.
As Web has a large number of potential users, a Web site may receive highly bursty requests and get overwhelmed, which is known as the flash crowd phenomenon. When a Web server becomes overloaded, its service quality will be seriously degraded: its users will perceive longer delays or even lose services. To prevent overload, capacity planning is not sufficient since the real traffic volume may exceed the planned capacity. Moreover, provisioning according to the peak traffic volume or even over-provisioning is not cost effective since Web traffic has a large variance. To better handle overload, dynamic load shedding and migration are needed, such as the Hotspot Rescue Service [2]. Short term traffic predictions are important for a server to take needed actions in advance when it anticipates an approaching peak load which is likely to exceed its capacity or a preset threshold.
Note that for overload prevention, we only need to predict an upper bound of the future traffic volume. More precisely, whether the future traffic volume will exceed the server's capacity or a preset threshold. As long as the future traffic volume is below the predicted bound, the exact volume does not matter much here. Also note that for overload prevention, over-prediction has a less penalty than under-prediction because a false alarm only incurs unnecessary overheads, but a miss prediction of an excess traffic can cause the server being overloaded.
In this paper, we describe a prediction algorithm for estimating the upper bound of future Web traffic volume. We employ a multiple time scale approach by using traffic information at a smaller time scale to forecast traffic volume at a larger time scale. Furthermore, we utilize traffic statistical properties other than curve fitting to do forecasting. The rest of this paper is organized as follows: we give the motivation in Section 2, describe our prediction algorithm in Section 3, discuss the parameter selection in Section 4, present experiment results in Section 5, and conclude in Section 6.
Traditionally, traffic predictions are carried at a single time scale
using curve fitting. A difficult issue here is to choose the right number
(denoted as ) of history intervals used for predictions: if
is too large, then predictions are
based upon less relevant information in history, whereas if
is too small, then predictions are made from incomplete
information; both cases lead to poor predictions. Usually
better predictions can be achieved by varying
dynamically,
but it is hard to derive the correct
.
To avoid the trouble of choosing , we seek a new approach to
traffic predictions by only using traffic information in current interval.
More specifically, we try to correlate how traffic changes within current
interval at a smaller time scale (e.g., one tenth of current time scale)
with that at current time scale. Previous work on self similarity
[3] has shown that statistical correlations
exist for Web traffic at different time scales. From a first look, it seems
that self similarity is not useful for traffic predictions since it is a
property for stationary processes, whereas predictions are more useful when
traffic volume changes quickly and dramatically. A careful re-consideration
reveals that no matter how quickly a traffic changes, at sufficiently small
time scales, the change between adjacent intervals will be small. Equivalently,
we can regard the mean of traffic volume in adjacent intervals as unchanged
and the real change as variability. Note that for three consecutive intervals:
,
, and
, we can view that
and
have
the same mean
, and
and
have the same mean
; but
and
can be unequal (i.e.,
and
can have different means). In this way, we can perform
predictions by utilizing self similarity within two adjacent intervals at
sufficiently small time scales. A good fit here is that self similarity is
measured in terms of statistical correlations between two different time
scales, which are just what we need to predict the upper bound of future
traffic volume.
We formulate our prediction problem as follows: given a time scale
(such as
seconds), we want to predict the upper bound of traffic
volume in next interval based on traffic information in current interval.
Note that the length of each interval is
. Let
and
denote the traffic volume in current interval (
) and next interval
(
), respectively, and
denote the difference between
and
(i.e.,
). If we can find an
upper bound (denoted as
) of
, then we can estimate that
.
In other words, predicting an upper bound for
is equivalent to estimating
. Next we show using statistical properties and self
similarity to estimate
.
Let random variable denote the difference of traffic volume
between adjacent intervals at time scale
, and
and
denote the mean and standard deviation of
, respectively.
If assuming that
follows normal distribution, we can estimate
the bound of
using
and
. For example,
since about
samples of
fall into the range of
, we can say that
a sample of
will be less than
with more
than
probability.
In order to derive
, we divide
into
equal sub-intervals
with length of
, and look at
in these
intervals. With a sufficient number of samples
(e.g.,
),
we can have an estimation for
and
. If assuming that the traffic is self-similar
with Hurst parameter
within the period of
and
, then we have
, and
.
With
and
, we can estimate
as
. Note that here we choose
rather than
mainly because we want to have
a closer upper bound estimation to avoid unnecessary false alarms.
Also note that since our prediction is based on statistical properties,
the predicted upper bound is correct only with a high probability.
Several parameters affect the prediction performance. The first
one is the prediction interval . As we use self similarity
to derive statistical correlations between two different time scales,
the mean of traffic volume should be roughly unchanged within the
period of
. Usually
should not exceed
seconds.
The second parameter is the scaling factor
between the two
different time scales
and
. As this parameter
decides the number of samples in time scale
used for deriving
statistical properties,
should be no less than
. The third
one is the Hurst parameter
. Since we do not know the correct
in advance, and using a larger
tends to over estimate whereas using
a smaller
tends to under estimate, the general guidances are as
follows: (1) the burstier the traffic, the larger
[4];
(2) a right
will result in roughly the same prediction performance
when
changes; and (3) use a little bit larger
if not sure,
usually in the range of
.
To evaluate our prediction algorithm, we apply it
to the 1998 World Cup data set [1], which includes
billion requests made to
servers at four different regions
during a period of
days. We run our prediction algorithm for three servers
on three days. The three chosen servers are server5, server41 and server64,
which are selected from three different regions since servers in the same
region have very similar traffic curves. The three chosen days are June 29
(day65), July 7 (day73) and July 8 (day74), which are among the busiest
days in the data set. In each day, we choose a period of three hours that
includes a dramatic traffic spike.
We carry experiments in three steps. For preparation, we calculate
the number of requests at the following time scales (in second):
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
.
In different experiments, we vary
,
and
to evaluate
their effects on predictions. After each experiment, we calculate
the percentage of prediction intervals in which the real traffic
volume fall below the predicted upper bound.
In the first experiment, we fix and
, but vary
from
to
seconds. We get consistent prediction performance
across all nine different server-day combinations. For clarity, we only
show the results for the three servers on day74 in
Figure 1. As we anticipate,
prediction performance changes as
increases: around
when
seconds, slowly degraded to around
when
seconds, and down quickly when
seconds. We show the detailed
prediction results for server41 on day65 in
Figure 2.
Since the finest time scale in the data set is second, and a good
prediction interval
seconds, we have
.
In the second experiment, we fix
and
, but vary
.
We predict using
, respectively, and get roughly the same
results. For example, for server41 on day65, the three predictions using
all have a
performance, while the prediction using
has a
performance with just one more miss prediction. This
validates that with a right
, predictions using different
(within
a certain range) are roughly equivalent, and that
appears to be
the right value for this data set.
In the last experiment, we fix , but vary
and
. This is
to determine a right
based on the following property: increasing
will raise the prediction performance if we are using a larger
, but
lower the prediction performance if we are using a smaller
.
In this paper, we described a prediction algorithm for estimating the upper bound of future Web traffic volume, in which we employ a multiple time scale approach and utilize traffic statistical properties to do forecasting. We evaluated three algorithm parameters and showed that our algorithm is simple, effective for short term traffic bound predictions, applicable to bursty traffic, and useful for Web server overload prevention.
The work described in this paper was supported in part by the National Science Foundation under Grant No. ANI-0117738. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation.