A Closer Look at Network Traffic Dynamics

Krishanu Maulik

Dual Nature

• Large time scales (few hundred milliseconds or more)

– superposition of iid individual input processes due to different sources – additive structure

– the limiting behavior shows self-similarity

– only global connection characteristics (session arrivals, session length, duration of on/off periods) matter but details of packet arrivals within a connection do not

• Small time scales (hundred milliseconds or less)

– shows multifractal behavior

– multiplicative structure

– depends on the traffic rate patterns

– driven by protocols and congestion control mechanisms

Singularity Exponents

Singularity exponent of a function Y at time t is

α(t) = lim_{ε↓0} \frac{log sup_{u:|u−t|≤ε}|Y (u) − Y (ε)|}{log ε}

It is closely related, but not equal to the singularity exponent based on polynomial exponents:

α(t_{0}) is the best, i.e., largest α such that

|Y (t′) − Y (t_{0})| ≤ C|t′ − t_{0}|^{α}

for all t′ sufficiently close to t_{0}.

K. Maulik. Cornell University, 2001.

Multifractal Spectrum

Define the set

K_{α} = {t : α(t) = α}

For usual fractals, K_{α} is empty or whole line, one possible value of α and is called monofractal.

Multifractal spectrum is dim (K_{α}).

Observe small α corresponds to the bursty parts and large α corresponds to smooth parts.

Hausdorff Dimension

s-dimensional Hausdorff measure is

H^{s}(A) = lim_{δ↓0} inf { ∞ ; ∑ ; i=1 |U_{i}|^{s} : |U_{i}| ≤ δ, A ⊂ ∞ ; ⋃ ; i=1 U_{i}}

Hausdorff dimension of set A is

dim (A) = sup {s : H^{s}(A) = ∞}

K. Maulik. Cornell University, 2001.

Approximations to Multifractal Spectrum

For k_{n} = 1, 2, …, 2^{n}, define

α_{k_{n}}^{n} = −\frac{1}{n} log_{2} |Y ((k_{n} + 1)2^{−n}) − Y (k_{n}2^{−n})|

and

f_{n}(α, ε) = #{α_{k_{n}}^{n} ∈ (α − ε, α + ε)}

We define

f(α) := lim_{ε→0} lim_{n→∞} \frac{1}{n} log_{2} f_{n}(α, ε)

In general, dim (K_{α}) ≤ f(α).

K. Maulik. Cornell University, 2001.

Structure and Partition Functions

Structure function is

S_{n}(q) := 2^{n}−1 ; ∑ ; k=0 |Y ((k + 1)2^{−n}) − Y (k2^{−n})|^{q} = 2^{n}−1 ; ∑ ; k=0 2^{−qnα_{k}^{n}}
≈ _{α}^{∑} 2^{−n(qα−f(α))} ≈ 2^{−n inf_{α}(qα−f(α))}

Partition function is

τ(q) := lim_{n→∞} log_{2} S_{n}(q) ≈ inf_{α} (qα − f(α))

K. Maulik. Cornell University, 2001.

Further Approximations

Legendre transform of a function f is

f^{∗}(y) = inf_{x} (xy − f(x)).

Thus, τ(q) ≈ f^{∗}(q). If f is convex, we can obtain f back from f^{∗} by another Legendre transform. This motivates the following approximation to f:

τ^{∗}(α) = inf_{q} (qα − τ(q))

In general, f(α) ≤ τ^{∗}(α) and τ^{∗}(α) is an approximation to the multifractal spectrum.

K. Maulik. Cornell University, 2001.

Multiplicatively Generated Multifractals – Cascades

At n-th level, the unit interval is split into 2^{n} subintervals

I_{k_{n}}^{n} = [k_{n}2^{−n}, (k_{n} + 1)2^{−n}], k_{n} = 0, 1, 2, …, 2^{n} − 1.

At next level, the interval I_{k_{n}}^{n} is split into two equal intervals I_{2k_{n}}^{n+1} and I_{2k_{n}+1}^{n+1} and its mass is redistributed in the proportions M_{2k_{n}}^{n+1} and M_{2k_{n}+1}^{n+1} , where

M_{2k_{n}}^{n+1} + M_{2k_{n}+1}^{n+1} = 1.

Cascades (Continued)

For a nested sequence of dyadic intervals {I_{k_{n}}^{n}}, we assume that the sequence {M_{k_{n}}^{n}} is independent. We also assume all the M_{k_{n}}^{n} have same distribution as the random variable M.

Then we have a random distribution function Y. Given k_{n} ∈ {0, 1, 2, …, 2^{n} − 1}, define inductively k_{j−1} = [k_{j}/2]. Then

Y (I_{k_{n}}^{n}) = M_{k_{n}}^{n} · M_{k_{n−1}}^{n−1} ⋯ M_{k_{1}}^{1}.

Multifractal Spectrum of Cascades

For cascades,

E[S_{n}(q)] = 2^{n}(E[M^{q}])^{n}.

Then,

T (q) = lim_{n→∞} −\frac{1}{n} log_{2} E[S_{n}^{q}] = −1 − log_{2} E[M^{q}].

Multifractal spectrum:

dim (K_{α}) = f(α) = τ^{∗}(α) = T^{∗}(α) a.e. ,

when T^{∗}(α) > 0.

K. Maulik. Cornell University, 2001.

Examples

M follows Uniform distribution on [0, 1].

T (q) = −1 + log_{2}(1 + q)

T^{∗}(α) = \{ \begin{matrix}1 − α + log_{2} (\frac{eα}{log_{2} e}) , & if α > 0 \\ −∞, & if α ≤ 0 \end{matrix}

In general, if M follows a Beta distribution with parameters p and p, the resulting cascade has multifractal spectrum, which looks like a hump.

K. Maulik. Cornell University, 2001.

WAN Traffic at Small Time Scale

Individual TCP connection

• exhibits multifractal behavior

• looks like a conservative cascade

• at microscopic level is a product of large number of more or less independent multipliers

• is asymptotically log-normal at small time scales

Simple Model

(i) user-initiated sessions arrive according to a Poisson process

(ii) brings with them a workload (number of bytes, packets, flows, or session durations) that is heavy-tailed with infinite variance

(iii) distribute the workload over the lifetime of the session at a constant (unit) rate

Large Time Scale Asymptotics

The input rate of the Poisson process is allowed to vary with time scale.

The aggregate traffic, over large time scales, behave like stable Lévy motion or fBm

• For slow growth of the input rate, the limit is stable Lévy motion

• For fast growth of the input rate, the limit is fractional Brownian motion

Modifications

• Deterministic regularly varying traffic rate process

• Random linear traffic rate process, where the traffic rate is allowed to be weakly dependent on the lifetime of the session

• Convergence in 𝔻 space with M topology (for Lévy motion)

and with J topology (for fBm)

K. Maulik. Cornell University, 2001.

Multifractal Workload Model

Replace property (iii) in the simple model with (iii′) the traffic rate process is multiplicative The large time scale asymptotic results continue to hold.

K. Maulik. Cornell University, 2001.

Spectrum of the superposition of multifractals

For two multifractals μ and ν,

τ^{μ+ν} (q) = min (τ^{μ}(q), τ^{ν}(q)), q ≥ 0

and in general,

τ^{μ+ν} (q) ≥ min (τ^{μ}(q), τ^{ν}(q)), q < 0.

We assume the individual traffic rate processes are iid and thus have same spectra. Taking Legendre transform, the superposition has same spectrum for small α, but spectrum may reduce for large α. Superposition makes the process more bursty!

Limitations

• Cascades may not be conservative

• Within session structure is complicated mixture of additive and multiplicative components

• Number of TCP connections per unit time at large time

scales exhibits self-similar behavior

K. Maulik. Cornell University, 2001.

Alternative Model

(i) The TCP connections arrive according to a self-similar process (fBm?)

(ii) The connection workload is heavy-tailed with infinite variance (iii) The workload is distributed over lifetime in a multifractal

fashion (conservative binomial cascade?)

K. Maulik. Cornell University, 2001.

Further Model

The workload can be distributed in a multifractal fashion, which is asymptotically self-similar and may depend on the workload weakly.

However, the spectrum of the usual example, Lévy process, is only linear. We need to find an asymptotically self-similar process whose paths have multifractal spectrum of the required hump form.

References

1. Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons Ltd., Chichester, 1990.

2. A. Feldman, A. C. Gilbert, W. Willinger, and T. G. Kurtz. The changing nature of network traffic: Scaling phenomena. Computer Communications Review, 28(2):5–29, April 1998.

3. A. Feldmann, A. C. Gilbert, and W. Willinger. Data networks as cascades: Investigating the multifractal nature of internet WAN traffic. Computer Communications Review, 28(4):42–55, September 1998. Proceedings of ACM/SIGCOMM’98, Vancouver, Canada.

4. A. C. Gilbert, W. Willinger, and A. Feldmann. Scaling analysis of conservative cascades, with applications to network traffic. IEEE Transactions on Information Theory, 45(3):971–991, April 1999. Special Issue on “Multiscale statistical signal analysis and its applications”.

5. Stéphane Jaffard. The multifractal nature of Lévy processes. Probab. Theory Related Fields, 114(2):207–227, 1999.

6. Takis Konstantopoulos and Si-Jian Lin. Macroscopic models for longrange dependent network traffic. Queueing Systems Theory Appl., 28(1-3):215–243, 1998.

7. V. G. Kulkarni, J. S. Marron, and F. D. Smith. A cascaded on-off model for tcp connection traces. Technical Report, Department of Statistics, University of North Carolina, Chapel Hill, NC, 2001.

8. Krishanu Maulik, Sidney Resnick, and Holger Rootzén. A network traffic model with random transmission rate. Technical report 1278, available

at www.orie.cornell.edu/trlist/trlist.html, 2000.

9. Krishanu Maulik and Sidney Resnick. Large and small time scale analysis of network traffic. Technical report 1311, School of ORIE, Cornell Uni-

versity, Ithaca NY, 14853; available at www.orie.cornell.edu/trlist/trlist.html,

2001.

10. T. Mikosch, S. Resnick, H. Rootzén, and A. W. Stegeman. Is network traffic approximated by stable lévy motion or fractional Brownian motion? Technical report 1247, School of ORIE, Cornell University, Ithaca NY,

14853; available at www.orie.cornell.edu/trlist/trlist.html, 1999.

11. Sidney Resnick and Eric van den Berg. Weak convergence of high-speed network traffic models. J. Appl. Probab., 37(2):575–597, 2000.

12. R. H. Riedi Multifractal processes. In P. Doukhan, G. Oppenheim, and M. S. Taqqu, editors, Long Range Dependence: Theory and Applications. Birkhäuser, 2001. Forthcoming.

13. R. H. Riedi and J. Lévy Véhel. Multifractal properties of tcp traffic: a numerical study. Technical Report No. 3129, INRIA. Also available at

http://www.ece.rice.edu/~riedi/cv publications.html, 1997.

14. R. H. Riedi and W. Willinger. Towards an improved understanding of network traffic dynamics. In K. Park and W. Willinger, editors, Selfsimilar Network Traffic and Performance Evaluation. Wiley, 2000.