Transcript 5-2_ICC03 prediction..

Traffic modeling and Prediction
----Linear Models
Traffic models are important in
 the design, engineering and performance
evaluation of networks.
 studying network traffic
 generating linear processes
 traffic modeling using linear models
 predicting traffic in various fields of
networks
 Minimum mean square error forecast
ARIMA(p,d,q) Models
(Auto Regressive Integrated Moving Average)


Let {at: t =..., -1, 0, 1, ...} be a white noise WN(0, 2)
with zero mean and variance 2
Then Xt is an ARIMA(p,d,q) process if
 (B) 
d
X t   (B ) a t
 ( B)  1  1B  2 B     p B ,
2
p
 ( B)  1   1 B   2 B 2     q B q .


B is the backward-shift operator, i.e. BXt = Xt-1
 (B) and  (B) are polynomials in complex variables
with no common zeroes, and in addition  (B) has no
zeroes in the unit disk
ARIMA (p,d,q) Models




p -- autoregressive order, non-negative integer
 p = 0 : MA (q) models
q -- moving average order, non-negative integer
 q = 0 : AR (p) models
d is the level of differencing
 d = 0: stationary
 d is non-negative integer: nonstationary
d is the differencing operator defined as

 d 
 d  ( 1  B ) d     (  B ) k   1  B
k 0  k 
 d
    ( d  1 ) / [  ( k  1 )  ( d  k  1 ) ]
k
 
Wireless Traffic Modeling and
Prediction Using Seasonal
ARIMA Model
Yantai Shu1 Minfang Yu1 Jiakun Liu1
Tianjin University1
Presenter: Oliver W.W. Yang2
University of Ottawa2
May 2003
Outline





Introduction
 Motivation
 Objective
Building a seasonal ARIMA model to
describe a trace
Traffic Prediction
Feasibility study
Conclusion
Introduction
Traffic(Erlang)
Statistics of China Mobile in Tianjin indicates
that the number of mobile phone users is
increasing at an exponential rate
 need proper modeling
 important to forecast wireless traffic workload
2 50 0 0 0
200000
150 0 0 0
10 0 0 0 0
1
41
81
12 1
16 1
201
241
281
321
T ime scale (day)
Previous Work



Seasonal ARIMA (Auto Regressive Integrated
Moving Average) model
linear prediction scheme used in the dynamic
bandwidth allocation schemes for VBR video
Predictive congestion control for broadband WAN
Our work on
 the fractional ARIMA model in admission control
 the seasonal ARIMA model for the prediction of
traffic in the dial-up access network of ChinanetTianjin with one periodicity.
Objective



Studying the characteristic of wireless traffic
 provide a general expression for the
wireless traffic in China
Fitting seasonal ARIMA model to capture the
properties of real wireless traffic
 Seasonal model with two periodicities
Using the model to forecast wireless traffic
 Provide guidance in designing, engineering
and performance evaluating of networks
Seasonal ARIMA Model
Exploits the periodic effect, i.e., the relation among
values of different observation time intervals.
Let
 Xt be the tth observation in an interval
 s be the period
  t , t 1 be the error (noise) components (general
correlated)
Then using relationship
 ( B)  t  ( B)a t
d
we obtain
( B )
s
D
s X t
 ( B ) t
s
Seasonal ARIMA model
General multiplicative model
 with one period of order
 p ( B)  P ( B ) 
s

d
 p, d , q  P, D, Qs
X t   q ( B)  Q ( B ) a t
D
s
s
with two period of order
( p, d , q)  ( P1 , D1 , Q1 ) s  ( P2 , D2 , Q2 ) s
1
 p  B  P  Bs

  q  B  Q
Bs
1
1

1

P
2
1


Bs
2
Q
2


 d  sD  sD X t
1
1
Bs
2
2
2
a.
t
can similarly obtain models with three or more
periodic components with similar argument
2
Building a seasonal ARIMA
model to describe a trace


Use spectrum analysis to uncover different
periodicities in the time series
 basis of building a seasonal model
Transfer the ARIMA problem to an ARMA problem
 Make use of the several known ways for fitting
ARMA models to traffic traces
 Identify the necessary parameters (d and D)
 Obtain from the ARMA model on process
Wt    X t ,
d
D
s
Algorithm A: Procedure to fit a
seasonal ARIMA model to traffic trace
Step 1: Obtaining the periods such as s1 and s2 through
spectrum analysis.
Step 2: Obtaining an estimate of d, D1 and D2 according
to incremental analysis of the trace, determining d, D1
and D2 using ADF test.
Step 3: Performing differencing on Xt according to
d D
Wt    s X t , to obtain a stationary series.
Step 4: Model identification
- Determining all the orders p, P1, P2, q, Q1 and Q2
Step 5: Estimating all the parameters like i and j
Step 6:Obtaining the fitted multiplicative seasonal
ARIMA models from
 p ( B)  P ( B s )  d  sD X t   q ( B)  Q ( B s ) a t
Prediction:
Using seasonal ARIMA model to forecast time series
Using linear prediction to make forecasts
 since seasonal ARIMA model is linear model
 based on the minimum mean square error (MMSE)
 Useful to specify the probability limits of a given
prediction algorithm
 new call can be blocked if actual arrivals are
continuously greater than predicted traffic value
 obtaining the traffic prediction based on upper
probability limit after
 adding a bias  to the minimum mean square
u
error forecast

Algorithm B:
Procedure to predict traffic of a given
upper-bound call blocking probability
Step 1: Determine the value of u from the QoS
requirement
e.g. call blocking probability
Step 2: From u, determine the value of u
Step 3: Determine the time granularity and the stepparameter h
Step 4: Use Algorithms A to construct a seasonal
ARIMA models to fit the traffic trace.
Step 5: Predict the next value of the time series using
h-step minimum mean square error forecast.
Step 6: Obtain the predicted traffic by adding a bias u
i.e. Xˆ u h  Xˆ h 
t
t
u
Feasibility study
Experiments of proposed algorithms on modeling and
prediction using real traffic trace
 measured from the GSM net of China Mobile Tianjin
 we have original hourly traffic trace from 0:00
June 1, 2001 (Friday) to 0:00 April 27, 2002
(Saturday), a total of 330 days
 accumulating the traffic in each day to obtain the
daily traffic trace for the same 330 days
** using the previous 300 day data trace to do
modeling and forecast next 30 day values
 comparing the forecasted value with original value
to evaluate the performance of the prediction
algorithms
Feasibility study ---Analyzing actual GSM traffic
Fig. 1 Original traces of daily traffic

Fig. 2 Original traces of hourly traffic
240000
14000
220000
12000
200000
10000
Erlang
Erlang
180000
160000
8000
6000
4000
140000
2000
120000

Abscissa represents the
accumulated time length, and
unit is day
y-axis represents the sample of
traffic and unit is Erlang


341
321
301
281
261
241
221
201
181
161
141
121
101
81
61
41
1
321
301
281
261
241
221
201
181
161
141
121
81
101
61
41
1

day
21
0
100000
21

hour
Abscissa represents the
accumulated time length, and
unit is hour
y-axis represents the sample of
traffic and unit is Erlang
Feasibility study ---Analyzing actual GSM traffic on daily granularity

From Fig. 3, we can see that:
 A peak occurs at about 0.14
 getting the period 1/0.14=7
 in accordance with the actual
situation
 A second peak occurs at about
0.28, because of
 the asymmetry of network
traffic in the seven days period
 A third peak occurs at about 0.42
 due to the traffic on Saturday
and Sunday is far below the
traffic in workdays

Fig. 3 Periodogram based
on daily trace
110
100
90
80
70
60
50
40
0.0
0.1
0.2
0.3
0.4
0.5
1/day


abscissa represents
frequency, unit is 1/day
y-axis represents energy
Feasibility study ---Analyzing actual GSM traffic on hourly granulariy

Form Fig. 4, we can see that:
 Fig. 4 Periodogram based
on hourly trace
 main frequency is about 0.042
 getting the period
110
100
1/0.042=24
90
 there are also second and
80
third harmonics.
70
60
 another main frequency at
50
0.006
40
 with second and third
30
harmonics.
20
0.00
0.05
 this corresponds to the
1/hour 0.10
periodicity of 168
 abscissa represents
 i.e. one week.
frequency, unit is
 Thus, the hourly traffic shows
1/hour
two periodicities of 24 (one day)
 y-axis represents
and 168 (one week)
energy
Feasibility study ----
Building Seasonal ARIMA Model for Actual GSM
Traffic


From Fig.1,We notice:
 the GSM traffic increases linearly over time
 during long holidays
st
 e.g.Chinese new year and October 1 national day
 we see a dramatic drop in traffic.
 These dips has effect on our predictions
Before building model for actual traffic trace, we preprocess
the two traces
 use the average of corresponding date of the week and
time of day during the period preceding and following to
replace the dip in the corresponding time interval values
 use Algorithm A to process the two traces.
Feasibility study ---Traffic Prediction for Actual GSM Traffic

Using the model built above to forecast



using the daily and hourly traffic of 300 days
to forecast the values of the next 30 days
also showing the upper probability 98% limit
 using adjusted traffic prediction
 correspond to a bias  = 2 (1)
u
t
Fig. 5 and Fig. 6 show these result respectively
Feasibility study ---Traffic Prediction for Actual GSM Traffic
Fig.5 Forecast of daily traffic trace
Erlang

235000
225000
215000
9 8 % u p limits
fo re c a s ts
tra c e
205000
195000
185000
1
4
7
10
13
16
19
22
25
28
day
Feasibility study ---Traffic Prediction for Actual GSM Traffic

Fig.6 Forecast of hourly traffic trace
Erlang
98%uplimits
forecasts
18000
trace
16000
14000
12000
10000
8000
6000
4000
2000
0
1
25
49
73
97
121
145
169
hour
Feasibility study ---Comparing the Forecasts with the Actual Traffic Traces
The comparison was repeated with many prediction experiments
on the actual measured GSM traces of China Mobile of
Tianjin.
 the relative error between forecasting values and actual
values
 all less than 0.02
 lend a strong support to our prediction method
 our experiments showed that the seasonal ARIMA model is
a good traffic model capable of capturing the properties of
real traffic.
Have used fractional ARIMA models to describe the GSM trace
and forecast traffic
 did not find any improvement
 attribute to the weakness of the long-range dependency
in the traffic characteristics
Conclusion
Studying a method of fitting multiplicative seasonal
ARIMA models to measured wireless traffic traces.
 gave a general expression of the multiplicative
ARIMA models with two periodicities
 proposed a practical algorithm for building
seasonal ARIMA model.
 proposed an adjusted traffic prediction method
using seasonal ARIMA model.
Future work
 extend the seasonal ARIMA model based traffic
prediction to network design, management,
planning and optimization.