next up previous contents
Next: Poisson Resampling Up: diss Previous: Summary   Contents

Trace Resampling and Load Scaling

$\textstyle \parbox{0.2in}{\mbox{}}$$\textstyle \parbox{5.25in}{\begin{singlespace}\textit{That which is static and ...
...ich is dynamic and random is confusing. In between lies art.}\end{singlespace}}$$\textstyle \parbox{0.2in}{\mbox{}}$
$\textstyle \parbox{5.25in}{\begin{flushright}--- \textsc{{John A. Locke (1632--1704)}}\end{flushright}}$

$\textstyle \parbox{0.2in}{\mbox{}}$$\textstyle \parbox{5.25in}{\begin{singlespace}\textit{Everything that can be co...
everything that counts cannot necessarily be counted.}\end{singlespace}}$$\textstyle \parbox{0.2in}{\mbox{}}$
$\textstyle \parbox{5.25in}{\begin{flushright}--- \textsc{{Albert Einstein (1879--1955)}}\end{flushright}}$

The previous chapters presented a complete methodology for reproducing the traffic observed on a network link in a closed-loop manner, and proposed a number of metrics for studying the realism of the generated traffic. In this chapter, we study ways to introduce statistical variability in synthetic traffic in a meaningful and controlled manner. In addition, we address the need for changing offered load in network experiments. The methods that we introduce in this chapter add significant flexibility to our traffic generation approach, enabling researchers to perform a wider range of experiments.

In the approach presented so far, traffic is generated according to a trace \(\mathcal{T}_c=\{(T_i, C_i)\}\). Each augmented connection vector \(C_i\) is replayed starting at time \(T_i\). This implies that two different replays of \(\mathcal{T}_c\) using the same hardware and the same physical network result in very similar synthetic traffic. In both cases, the synthetic traffic has the same number of TCP connections, replaying the same source-level behaviors under the same network-level parameters, and starting exactly at the same times. Only tiny variations would be introduced on the end-systems by changes in clock synchronization, operating system scheduling and interrupt handling, and at switches and routers by the stochastic nature of packet multiplexing. This reproducibility was exactly what was needed to evaluate how well synthetic traffic approximated the real traffic from which it derived.

However, in the practice of experimental networking, experimenters often want to introduce more variability in their experiments. One way of accomplishing this is to use more than one trace in a replay, exposing the studied network protocol or mechanism to different types of workloads. This is highly desirable, but it has its drawbacks. First, the experimenter may want to perform a number of experiments that is larger than the number of available traces. Second, traces from different sites, and even traces from the same site but collected at different times of the day, may be so different that it becomes difficult to extrapolate from the results of the experiments.

A different, and complementary, approach is to conduct several experiments using traffic that ``looks like'' some specific trace \(\mathcal{T}_c\), without exactly replaying \(\mathcal{T}_c\) over and over. The first challenge in devising a method for accomplishing this task is to define what ``looks like'' mean. This involves creating a model (either formal or informal) of the traffic which is general enough to contain \(\mathcal{T}_c\) but specific enough to always resemble the original trace. Running different experiments then requires to instantiate this model several times to create new derived traces \(\mathcal{T}_c^\prime \), \(\mathcal{T}_c^{\prime\prime}, \dots\) and to generate traffic with these new traces using their source-level trace replay. In this chapter, this instantiation consists of resampling the set of connection vectors in \(\mathcal{T}_c\) and assigning them new start times. Statistical variability in the derived traces comes from the resampling of the original connection vectors, and from the process of connection start times. We preserve the statistical properties of the original set of connection vectors by resampling entire connection vectors, i.e., we do not manipulate the sizes and order of the ADUs and inter-ADU quiet times inside connection vectors. Our belief is that a trace created by modifying the source-level behavior of the connection vectors or their network-level parameters ``does not look like'' the original trace. For example, doubling the size of the ADUs in \(\mathcal{T}_c\) is an easy way of creating a new trace and increasing the offered load. However, the resulting connection vectors have little to do with the connections observed in the link from which \(\mathcal{T}_c\) was collected. Our choice to maintain connection vectors intact is reasonable, and consistent with the spirit of our overall methodology, which goes to great lengths to accurately characterize the source-level characteristics of each connection. Other researchers may have a different mental model of the legitimate level of statistical variability which could be introduced in \(\mathcal{T}_c^\prime , \mathcal{T}_c^{\prime\prime}, \dots\) We propose a specific solution and demonstrate that it is reasonable using quantitative data. A discussion of the different philosophies is outside the scope of this work.

The two sections in this chapter describe two techniques for introducing variability in the source-level replay of a trace. Section 7.1 describes Poisson Resampling. This technique assumes that connections are independent of each other, which is a reasonable choice for highly aggregated traffic. Poisson Resampling involves randomly resampling the connection vectors in \(\mathcal{T}_c\) in an independent manner to create a new \(\mathcal{T}_c^\prime \). New start times are given to each resampled connection vector in a such a way that connection inter-arrivals are exponentially distributed. As we will show, empirical data support the choice of exponential inter-arrivals.

Section 7.2 describes Block Resampling. This technique involves resampling blocks of connection vectors, preserving arrival dependencies among the connections inside the same block. Each block is the set of connections observed in an interval of fixed duration (e.g., 1 minute) in the original trace. We will demonstrate that this technique, unlike Poisson Resampling, preserves the long-range dependence in the connection arrival process found in real traces. This cannot be achieved by sampling independently from an exponential (or any other) distribution. Note that we will reserve the term resampling for randomly selecting connection vectors, and the term sampling for randomly drawing values from a parametric distribution, such as the exponential distribution.

The second topic of this chapter is how to manipulate a trace \(\mathcal{T}_c\) to modify the traffic load (i.e., average byte throughput) that this trace offers during its source-level replay. This is a common need in experimental networking research, where the performance of a network mechanism or protocol is often affected by the amount of traffic to which it is exposed. For example, active queue management mechanisms have very different performance depending on the level of utilization of the input link, so researchers generally perform experiments with offered loads that range from 50% to 120% of the link bandwidth. Rather than trying to find or collect traces with the exact range of loads needed (which is generally difficult), we propose to produce a collection of resampled traces with the intended range of offered loads.

Average load \(l\) is defined as the total number of bytes injected in the network \(s\) divided by the total duration of the experiment \(d\). Changing the average load in an experiment of constant duration therefore implies creating a scaled trace \(\mathcal{T}_c^\prime \) with a higher or a lower total number of bytes. Once again, the assumption is that it is possible to create a scaled trace \(\mathcal{T}_c^\prime \) which ``looks like'' the original \(\mathcal{T}_c\) but with a larger or smaller number of bytes. This requires a model of traffic that is general enough to encompass \(\mathcal{T}_c\) and traces derived from \(\mathcal{T}_c\) with different offered loads. As should be obvious, the problems of introducing statistical variability and changing average load are related, and can naturally be treated together, as we will do in this chapter. The two techniques mentioned above, Poisson Resampling and Block Resampling, provide the foundation for deriving scaled traces. In both cases, the resampling of \(\mathcal{T}_c\) to create a scaled \(\mathcal{T}_c^\prime \) can be modified to achieve a target average load. This means that our scaling method is predictable, which is an advance over earlier traffic generation methods, e.g., [CJOS00,LAJS03,SB04]. These earlier methods required a separate experimental study, a calibration, to construct a function coupling the parameters of the traffic generator and the achieved load. For example, web traffic generators usually require a calibration to discover the relationship between average load and the number of user equivalents. The scaling methods presented in this chapter eliminate the need for this extra study. Their starting point is the observation that the average load offered by the source-level replay of \(\mathcal{T}_c\) is a deterministic function of the total number of bytes in the ADUs of \(\mathcal{T}_c\). We will show that these observation holds true using numerical simulations and testbed experiments. In contrast, the same analysis will demonstrate that the average load offered by the replay of \(\mathcal{T}_c\) is not strongly correlated with its number of connections. In the case of Poisson Resampling, our method to construct a new trace \(\mathcal{T}_c^\prime \) with a specific target offered load involves resampling \(\mathcal{T}_c\) until the desired total number of bytes (coming from ADUs) is reached. In the case of Block Resampling, constructing a new trace \(\mathcal{T}_c^\prime \) with a specific target offered load involves subsampling blocks (``thinning'') to decrease load, or combining two or more blocks (``thickening'') to increase load.

next up previous contents
Next: Poisson Resampling Up: diss Previous: Summary   Contents

Doctoral Dissertation: Generation and Validation of Empirically-Derived TCP Application Workloads
© 2006 Félix Hernández-Campos