Introduction

In order to help design and control the emerging high-speed communication networks, we want source traffic models that can be both realistically fit to data and successfully analyzed. Many recent traffic measurements have shown that network traffic is quite complex, exhibiting phenomena such as long-tailed probability distributions and long-range dependence; e.g., see Cáceres, Danzig, Jamin and Mitzel [3], Leland, Taqqu, Willinger, and Wilson [18], Paxson and Floyd [19], Crovella and Bestavros [6] and Feldmann [11]. In fact, the long-tailed distributions may be the cause of all these phenomena, because they tend to cause long-range dependence and (asymptotic) self-similarity. For example, the input and buffer content processes associated with an on-off source exhibit long-range dependence when the on and off times have long-tailed probability distributions; e.g. see Section 8. Long-tailed distributions are known to cause self-similarity in models of (asymptotically largely) aggregated traffic; see Willinger, Taqqu, Sherman and Wilson [22].

In this paper we propose a way to analyze the performance of a network with multiple on-off sources and more general multi-level sources in which the on-time, off-time, and level-holding-time distributions are allowed to have long tails. To do so we must go beyond the familiar Markovian analysis. To achieve the required analyzability with this added model complexity, we propose a simplified kind of analysis. In particular, we avoid the customary queueing detail (and its focus on buffer content and overflow) and instead concentrate on the probability that aggregate demand (the input rate from a collection of sources) exceeds capacity (the maximum possible output rate) at any time. (This approach also can generate approximations describing loss and delay with finite capacity; e.g., Section 5 of [10].)

Motivation for considering on-off and multi-level models as source models comes from traces of frame-sizes generated by certain video encoders; e.g., see Grasse, Frater and Arnold [14]. Shifts between levels in mean frame size appear to arise from scene changes in the video, with the distribution of scene durations long-tailed. Indeed, the expectation that scene durations will have long-tailed distributions in one of the motivations behind the Renegotiated Constant Bit Rate (RCBR) proposal of Grossglauser, Keshav and Tse [15].

A key to being able to analyze the system with such complex sources represented by our traffic model is exploiting asymptotics associated with multiplexing a large number of sources. The ever-increasing network bandwidth implies that more and more sources will be able to be multiplexed. This gain is generally possible, even in the presence of long-tailed distributions and more general long-range dependence; e.g. see Duffield [8,9] for demonstration of the multiplexing gains available for long-range dependent traffic in shared buffers. As the scale increases, describing the detailed behavior of all sources becomes prohibitively difficult, but fortunately it becomes easier to describe the aggregate, because the large numbers produce statistical regularity. As the size increases, the aggregate demand can be well described by laws of large numbers, central limit theorems and large deviation principles.

We have in mind two problems: first, we want to do capacity planning and, second, we want to do real-time connection admission control and congestion control. In both cases, we want to determine whether any candidate capacity is adequate to meet the aggregate demand associated with a set of sources. In both cases, we represent the aggregate demand simply as the sum of the bandwidth requirements of all sources. In forming this sum, we regard the bandwidth processes of the different sources as probabilistically independent.

The performance analysis for capacity planning is coarser, involving a longer time scale, so that it may be appropriate to do a steady-state analysis. However, when we consider connection admission control and congestion control, we suggest focusing on a shorter time scale. We are still concerned with the relatively long time scale of connections, or scene times in video, instead of the shorter time scales of cells or bursts, but admission control and congestion control are sufficiently short-term that we propose focusing on the transient behavior of the aggregate demand process. In fact, even for capacity planning the transient analysis plays an important role. The transient analysis determines how long it takes to recover from rare congestion events. One application we have in mind is that of networks carrying rate-adaptive traffic. In this case the bandwidth process could represent the ideal demand of a source, even though it is able to function when allocated somewhat less bandwidth. So from the point of view of quality, excursion of aggregate bandwidth demand above available supply may be acceptable in the short term, but one would want to dimension the link so that such excursions are sufficiently short-lived. In this or other contexts, if the recovery time from overload is relatively long, then we may elect to provide extra capacity (or reduce demand) so that overload becomes less likely. The main contribution of this paper is to show how the transient analysis for design and control can be done.

Our approach is interesting for on-off and multi-level source models, but with little extra effort we can treat a wider class. The general model we consider has two components. The bandwidth demand of each source as a function of time $\{B(t):t \geq 0 \}$, is represented as the sum of two stochastic processes: (1) a macroscopic (longer-time-scale) level process $\{L(t):t \geq 0 \}$ and (2) a microscopic (shorter-time-scale) within-level variation process $\{W(t): t \geq 0 \}$, i.e.,  

$$B(t) = L(t) + W(t) ~, \quad t \geq 0 ~.$$ (1)

We let the macroscopic level process $\{L(t):t \geq 0 \}$ be a semi-Markov process (SMP) as in Chapter 10 of Çinlar [5]; i.e., the level process is constant except for jumps, with the jump transitions governed by a Markov process, while the level holding times (times between jumps) are allowed to have general distributions depending on the originating level and the next level. Given a transition from level j to level k, the holding time in level j has cumulative distribution function (cdf) F_jk. Conditional on the sequence of successive levels, the holding times are mutually independent. To obtain models compatible with traffic measurements cited earlier, we allow the holding-time cdf's F_jk to have long tails.

We assume that the within-level variation process $\{W(t): t \geq 0 \}$ is a zero-mean piecewise-stationary process. During each holding-time interval in a level, the within-level variation process is an independent segment of a zero-mean stationary process, with the distribution of each segment being allowed to depend on the level. We allow the distribution of the stationary process segment to depend on the level, because it is natural for the variation about any level to vary from level to level.

We will require only a limited characterization of the within-level variation process; it turns out that the fine structure of the within-level variation process plays no role in our analysis. Indeed, that is one of our main conclusions. In several examples of processes which we envisage modeling by these methods, there will only be the level process. First, the level process may be some smoothed functional of a raw bandwidth process. This is the case with algorithms for smoothing stored video by converting into piecewise constant rate segments in some optimal manner subject to buffering and delay constraints; see Salehi, Zhang, Kurose and Towsley [20]. With such smoothing, the input rate will directly be a level process as we have defined it. Alternatively, the level process may stem from rate reservation over the period between level-shifts, rather than the bandwidth actually used. This would be the case for RCBR previously mentioned. In this situation we act as if the reservation level is the actual demand, and thus again have a level process.

The remainder of this paper is devoted to showing how to do transient analysis with the source traffic model. As in our previous paper [10], we suggest focusing on the future time-dependent mean conditional on the present state. The present state of each level process consists of the level and age (elapsed holding time in that level). Because of the anticipated large number of sources, the actual bandwidth process should be closely approximated by its mean, by the law of large numbers (LLN). As in [10], the conditional mean can be thought of as a deterministic fluid approximation; e.g., see Chen and Mandelbaum [4]. Since the within-level variation process has mean zero, the within-level variation process has no effect upon this conditional mean. Hence, the conditional mean of the aggregate bandwidth process is just the sum of the conditional means of the component level processes. Unlike the more elementary M/G/$\infty$ model considered in [10], however, the conditional mean here is not available in closed form.

The outline of the paper is as follows. In Section 2, we show that the Laplace transform of the mean of the transient conditional aggregate demand can be expressed concisely. This is the main enabling result for the remainder of the paper. The conditional mean itself can be very efficiently computed by numerically inverting its Laplace transform. To carry out the inversion, we use the Fourier-series method in Abate and Whitt [1] (the algorithm Euler exploiting Euler summation), although alternative methods could be used. The inversion algorithm is remarkably fast; computation for each time point corresponds simply to a sum of fifty terms. We provide numerical examples in Examples 3.1, 4.2 and 7.1. Example 7.1 is of special interest, because the level-holding-time distribution there is Pareto.

In Section 3 we show that in some cases we can avoid the inversion entirely and treat much larger models. We can avoid the inversion if we can assume that the level holding times are relatively long compared to the times of interest for control. Then we can apply a single-transition approximation, which amounts to assuming that the Markov chain is absorbing after one transition. Then the conditional mean is directly expressible in terms of the level holding-time distributions. In Section 4 we show the value of having more detailed state information, specifically the current ages of levels. With long-tailed distributions, a large elapsed holding time means that a large remaining holding time is very likely; e.g. see Section 8 of [10] for background, and Harchol-Balter and Downey [16] for an application in another setting. In Section 5 we illustrate the use of state information for network control. In Section 6 we turn to applications to capacity planning. The idea is to approximate the probability of an excursion in demand using Chernoff bounds and other large deviation approximations, then chart its recovery to a target acceptable level using the results on transience. Interestingly, the time to recover from excursions sufficiently close to the target level depends on the level durations essentially only through their mean. Correspondingly, the conditional mean demand relaxes linearly from it excursion, at least approximately so, for sufficiently small times. If the chance for a larger excursion is negligible (as determined by the large deviation approximation mentioned) then this simple description may suffice. An example is given in Section 7. In Section 8 we show how long-range dependence in the level process arises through long-tailed level-holding-time distributions.