TIMES

Trace-based Inference of Models for Emulation and Simulation

Overview

The task of TIMES is to model a network and use trace plus the inferred models to emulate or simulate the network.  To emulate or simulate a network, we need to know continuous-time information of the network. For example, at any point of time, what is the packet delay or whether the packet is lost or not. This can not be provided by the trace itself or by a discrete-time model. The main idea of this project is to infer continuous-time model from discrete-time traces.

Currently,  continuous-time hidden Markov model (CT-HMM) is used to model a network. A CT-HMM is inferred from delay and loss observations seen by a sequence of probes sent from one end host to another end host. This CT-HMM can then be incorporated into a simulator or an emulator to drive the simulation of a network protocol or application by providing losses and delays to packets in the network at arbitrary points of time. By collecting probe traces in a wide variety of network settings, one can construct a library of CT-HMMs, with each model representing a particular network setting. A model can then be selected to simulate a network protocol or application under a particular network environment. This simulation method can thus provide users with a simulation environment representing a wide range of real network scenarios. The datagram for the whole process is shown below:
 
 

Trace

Periodic or geometric probing is used to send packet from the probe sender to the probe receiver. At the same time,  a TCP connection is set up from the probe ender to the probe receiver for validation purpose. The following are two traces from University of Massachusetts (UMass) to University of Southern California (USC). The method of probing and probing interval are shown in the following table.
 

Trace	Time	Probing	Length
T1 forward backward	03/08/2002	Periodic  probing interval: 20ms	5 minutes
T2 forward backward	03/16/2002	Geometric Smallest probing interval:10ms  Average probing interval: 50ms	20 minutes

 

The loss rate and throughput of the TCP connection is shown in the following table:
 

Trace	Loss rate	Throughput
T1	1.51%	0.214Mbps
T2	0.41%	1.578Mbps

 

Model Inference

There are two steps in the model inference.
1. Inference of the discrete-time model.

The discrete-time hidden Markov model P is infered from the trace by using an EM(Expectation Maximization) algorithm.
An example of the discrete-time hidden Markov Model:
M= 2
N= 2
P:
0.9177 0.0071 0.0749 0.0003
0.0000 0.2752 0.0256 0.6992
0.0000 0.0975 0.8450 0.0575
0.4333 0.0000 0.0000 0.5667
pi:
1.000000 0.000000 0.000000 0.000000
S:
0.016064 0.013438

M is the number of discritized delay. N is the number of hidden states. Matrix P is transition matrix of the discrete-time hidden Markov model. pi is the initial distribution of the Markov model. S is the vecotr of the loss probabilities of each discritized delay.

2. Obtaining the continuous-time model from the discrete-time model.

The continuous-time hidden Markov model Q is obtain from the discrete-time hidden Markov model using a matrix transformation.
M=2
N=2
Q:
-4.512640 0.191663 4.246672 0.074306
0.000000 -90.979298 4.253531 86.725767
1.803028 9.633508 -11.436536 0.000000
29.726238 0.063252 0.000000 -29.789491
pi:
1.000000 0.000000 0.000000 0.000000
S:
0.016064 0.013438

Here Q is the rate matrix of the conitnuous-time hidden Markov model.

Simulation

The simulator take the continuous-time model Q and the simulation script to do a simulation. The delay and loss of packets sent at any time point are governed by the continuous-time model Q. The basic idea of the simulation is simulating a continuous-time Markov chain.

The simulator is implemented in ns. A link object called EmulPathQ is defined. This EmulPathQ object gives delay and loss to a packet according to the continuous-time model Q. Here is the link for the implementation.
 

One example of the input file to the simulator.

One example of the simulation scripts.
 

 

 

Papers

 

· Continuous-time Hidden Markov Models for Network Performance Evaluation
Wei Wei, Bing Wang, Don Towsley
Performance Evaluation 49(1/4): 129-146 (2002).
 

Wei Wei's Home Page