Lecture Notes for Simulation

23 February 2005 - Data Collection

Outline

Characterizing Data

• There are four ways of characterizing the data required by a model:

  1. Fit a distribution to system measurements.

  2. Sample a histogram of system measurements.

  3. Guess a distribution based on system characteristics.

  4. Use the system measurements as trace data.

Fitting Distributions

• Given some sampled data, find a distribution from which it might have come.

  • Then use the distribution to generate more data.

• The procedure is

  1. Create a frequency histogram from the sample data.

  2. Pick a distribution close to the frequency histogram.

  3. Calculate the mean and variance of the sample data.

  4. Calculate the mean and variance of the distribution.

  5. Compare goodness-of-fit between the data and distribution statistics.

Histogram Sampling

• Sometimes only the histograms of system measurements are available.

• There are two approaches in this case:

  • Start from step 2 in distribution fitting.

  • Use the histogram to derive an empirical distribution.

Characteristic-Based Selection

• Sometimes no measurements are available, or possible.

• Previous experience, analogous systems, or theoretical results can provide intuition as to what to do.

• In the worst case, use distributions that match the characteristics of the data of interest.

  • Model component lifetimes with the Weibull distribution.

  • Model retransmissions before success with the negative binomial distribution.

  • Model service times with the Erlang distribution.

  • Model random proportions with the beta distribution.

• But you still need parameters for the distributions.

Historic Data

• Use prior data sets.

  • Directly as inputs.

  • Indirectly via random sampling.

• Problems:

  • Simulation requirements may outstrip the available data.

  • Biased, dirty, skewed, or otherwise compromised data.

  • Limited ability to vary input data.

  • Predictions are difficult to make without detailed knowledge of data characteristics.

Empirical Distributions

• An empirical distribution is a distribution created from a specific data set.

• General approach:

  1. Create frequency counts for the data.

  2. Form the cumulative relative frequencies of the data.

  3. Generate samples from the cumulative relative frequencies.

Frequency Counts

• A frequency count is the amount of data belonging to a particular value range.

• Given a data set { x₁, ..., x_n }, create frequency counts by

  1. Creating a set of value ranges { r₁, ..., r_m }; the range set should

     • be contiguous (r_i.high == r_{i + 1}.low).

     • cover all possible values

     • provide enough samples per value range

  2. For each range r_i, count the value x_j such that r_i.low <= x_j < r_i.high.

Cumulative Relative Frequencies

• The cumulative relative frequencies indicate the growth of value counts in a range of values.

• Given a set of frequency counts { f₁, ..., f_n }, form the cumulative relative frequencies by

  • Finding the normalization value S = sum(i = 1 to n, f_i).

  • Form the cumulative relative frequency c_i = sum(j = 1 to i, f_j)/S.

    • Note c_n = 1.

Data Generation

• Given a set of cumulative relative frequencies, generate a data point from the distribution as follows:

  • Generate a sample x from the standard uniform distribution.

  • Locate the first (leftmost) cumulative relative frequency containing x.

  • Generate a sample from the data distribution by either

    • picking an endpoint of the cumulative relative frequency or

    • interpolating between the cumulative relative frequency endpoints.

Points to Remember

This page last modified on 24 February 2005.