Description and comparision of various techniques for traffic prediction.

time_series.svg

traffic_prediction.md

Title: Load and Traffic Prediction Author: Christoph Schniedermeier Date: July 9, 2012

Introduction

If knowledge about the future state of a network is available, you can control the network traffic to reduce congestion, latency and packet loss. Since network trafic has a high self-similarity, meaning its behaviour is "roughly" the same on any scale, a reasonable prediction of the behaviour should be feasible Self-Similarity.

In this paper I will introduce three common techniques for traffic prediction, explain how and why the are working, and compare them to each other.

Modelling Network Traffic

Network traffic is described as the used bandwidth over a certain time on a specific node of the network. Here we will only work with discrete time models in a time series Time series. This time series contain a sequance of traffic values, where the time interval for all values stays the same.

To model the behaviauor of real bandwidth usage two stochastic models are commonly used. The hidden Markov and the autoregressive moving avarage model. Both models are suited for certain scenarios. Also an aproach using maschine learning via neural networks can be used to predict future network states.

Hidden Markov Model

The hidden Markov model is used for modeling and analyzing sequential data. It describes a markov process with hidden states, meaning the states are known, but you do not know which one is the current state. You only observe some behaviour that is related to the current state.

Fundamentals

A hidden Markov model can be described using the following parameters:

• N: Number of states
• T: Number of observations
• x(i): state i, 0 <= i < N
• y(i): obeservation i, 0 <= i < T
• π(i): propabilitiy of being initially in step i
• a(i, j): propability of transition form state x(i) to state x(j)
• b(i, j): propability to observe observation y(i) in state x(j)

Given a hidden Markov model there are three questions that can solved:

1. What is the propability to observe a specific sequence?
2. What is the most likely sequenze of states, to generate given a sequence of observations?
3. What can we learn about the parameters a and b of a hidden Markov model, given a sequence of observations and/or states?

The prediction of network traffic falls under category 2. To calculate the most likely sequence of states the Viterbi Algorithm is used.

The Baum–Welch algorithm can be used to learn the model parameters from existing data traces.

Example

To predict the network traffic of an access point, we first need a classification for traffic states. This simplified model will assume High, Medium and Low traffic.

Autoregressive Moving Avarage

The autoregressive-moving-average (ARMA) model is the combination of autoregressive (AR) and moving-average models, which could also be used individually.

Fundamentals

Example

Neural Network

Metrics for the Quality of Predictions

The quality of a certain prediction technique can be expressed in different ways, depending analyzed network model and the prediction technique. Two usefull quality metrics for prediction that are going to be examined in this paper are:

• how far in the future a prediction can be made
• the minimum prediction error over a certain period of time

These two metrics affect each other, so a trad-off has to be made.