Information Systems and

On the Self-Similar Nature of ATM Network Traffic

Humam Elagha

Arab Academy for Banking and Financial Sciences, Faculty of Information Systems and Technology, Amman, Jordan

humam@students.aabfs.org

Maher AlShafee

Royal Scientific Society, Information Technology Centre, Amman, Jordan

maher_s@rss.gov.jo

Abstract

Modeling multimedia traffic is an important issue in performance analysis and design of commu-nication networks. With introduction of new applications, the characteristics of data traffic

changes. In this paper, a measurement study of ATM Network traffic has been carried out and it is shown that the recorded data exhibit self-similar features. The conclusions are supported by a comprehensive analysis using one of the most popular statistical methods called Indices of Dis-persion. Our results validate one of the most striking findings of the present teletraffic research: a broad range of packet network traffic has fractal-like behavior. We also investigate three popular synthetic self-similar traffic models and find out the most accurate one for the measured traffic. Keywords: ATM, Modeling, Self-similar traffic, Indices of Dispersion, Hurst parameter, Per-formance Testing.

Introduction

The characterization of real traffic is a critical issue to the success of efficient traffic engineering in ATM networks. Research in this field has resulted in numerous models and techniques over the last decade (Bjorkman, Latour-Henner, Hasson, pers, and Miah, 1995; Stamoulis, Anagostu, and Georgantas, 1994). However, the developed traffic characterization methods have been, in gen-eral, rather complicated and demand intensive computation of several statistical parameters. There is a lack of simple and accurate methods that can be of practical use to network operators. Extensive data studies indicate that traffic in high-speed communications networks has long-memory and heavy tailed (impulsive) characteristics. With the rising popularity of multimedia applications over networks, these properties of the traffic are only likely to become more domi-nant, posing unique new challenges to designers of network systems and protocols. Traditional

teletraffic theory cannot capture these traffic characteristics. During the last Material published as part of this publication, either on-line or

few years, significant research results in print, is copyrighted by the Informing Science Institute.

Permission to make digital or paper copy of part or all of these have been proposed on models that cap-works for personal or classroom use is granted without fee ture self-similarity of traffic. These provided that the copies are not made or distributed for profit

models, however, are inadequate for or commercial advantage AND that copies 1) bear this notice

predicting queuing performance, delays, in full and 2) give the full citation on the first page. It is per-missible to abstract these works so long as credit is given. To and buffer dimensions since the implica-copy in all other cases or to republish or to post on a server or tions of the combination of self-to redistribute to lists requires specific permission and payment

similarity and impulsiveness queuing of a fee. Contact Publisher@InformingScience.org to request

performance can be dramatically differ-redistribution permission.

On the Self-Similar Nature of ATM Network Traffic

ent from that of self-similarity alone. To the best of my knowledge there are no models that have been derived based on real traffic dynamics that also capture the data impulsiveness?

The modeling of self-similar traffic appeared as an emerging and challenging field of the present teletraffic research. It seems that there are different promising approaches to capture this complex fractal-like behavior. Norros (1993, 1995) used a Gaussian self-similar process known as the Fractional Brownian Motion. Willinger, Taqqu, Sherman and Wilson (2004) applied the superpo-sition of on/off sources with heavy-tailed on and off period. Erramilli (1994) and Singh and Er-ramilli (1999) studied different chaotic maps.

The rest of this paper is organized as follows. In section 2 we give information about the self-similar traffic characteristics and the used techniques for measuring the self-similarity level (Hurst-parameter H). In section 3 we present the analysis based on the real measurements taken from the Eastern Mediterranean University (EMU) ATM network and find out the self-similarity level. In section 4 we investigate the three promising self-similar modeling approaches to capture the observed properties, and we find out the most appropriate model for EMU ATM network traf-fic. Finally, section 5 summarizes the results of the paper and identifies areas for future research.

The Self-Similarity Phenomena and its Testing

A self-similar phenomenon represents a process displaying structural similarities across a wide range of scales of a specific dimension. In other words, the reference structure is repeating itself over a wide range of scales of diverse dimensions (geometrical, or statistical, or temporal). How-ever, these properties do not hold indefinitely for real phenomena and, at some point, this struc-ture breaks down.

Consider a time series X=Xn,n∈Z+ and define another time series (m-aggregated)

(m)X(m)=Xn,n∈Z+ by averaging the original time series over non-overlapping, adjacent

{}{}blocks of size m:

Xn

(m)1nm

=Xi∑mi=nm−(m−1)

X(1) represents in this case the highest resolution that is possible for the process. Lower resolu-tion evolutions of the process X(m) can be obtained by m-aggregating the Xn process, like for

instance

(4)Xn=

X4n−3+X4n−2+X4n−1+X4n

4

There are two classes of self-similar processes, namely exactly self-similar processes and asymp-totically self similar processes.

A process X is said to be exactly self-similar with parameter β(0<β<1) if, for m∈Z+the

following conditions are fulfilled • Variance VarX(m)=[]Var[X] βm2

Elagha & AlShafee

• Autocorrelation

R(k,X(m))=R(k,X)

The parameter β is related to the so-called Hurst parameter (H) by the following formula

β=2(1−H)

It is observed that for stationary ergodic processes, β=1 and the variance decays to zero. On the contrary, for exactly self-similar processes the variance decays more slowly.

Another class of self-similar processes is the so-called asymptotically self-similar processes. A process X is said to be asymptotically self-similar if, for k large enough • Variance

VarX(m)=

• Autocorrelation

[]Var[X] mβRk,X(m)→R(k,X)

as m→∞

It is observed that, for both classes of self-similar processes, the variance of X(m)decreases more

()1

asm→∞. This is to compare with the case of stochastic processes where the m

1

variance decreases proportional to and approaches zero m→∞ (consistent with white noise,

m

slowly than

i.e., uniform power spectrum).

The most striking feature of self-similar processes is however that the autocorrelation function does not degenerate whenm→∞. This is in contrast to stochastic processes, where the autocor-relation function degenerates asm→∞.

Properties

• Long Range Dependence:

A self-similar process with parameter 0.5 < H < 1 is long-range dependence. By definition the process X is called long-range dependent if

∑Cov(k)=∞is non-summable .Otherwise it is called short range dependence

k=0

∞

• Slowly Decaying Variance

The variance of the sample mean decreases much more slowly than the reciprocical of the sample size in the case of a self-similar process.

VarX(m)~m−β

for sufficiently large m.

[] 3

On the Self-Similar Nature of ATM Network Traffic

• Fractal Dimensions

The fractal dimension d of an object is defined as

d=

lnN

1ln

ηwhere N is the number of self-similar objects/pieces (versions of itself) to cover a given d-dimensional object, and η is the linear scale size of the covering objects.

Tests

The level of self-similarity in a time series is indicated by the Hurst parameter H. This H parame-ter has a value range of 0.5 ≤ H ≤ 1.0 and strong self-similarity means that H has larger values (close to 1.0). Several methods are available today to estimate self-similarity in a time series (Stallings, 1998; Abry and Veitch, 2005; Beran, 1994).

1. Indices of Dispersion : A commonly used measure for capturing the variability of traffic over different time scales is provided by the index of dispersion for counts (IDC), Cox and Lewis (1966),

IDC(L)=var{∑X}/E{∑X}

L

L

j=1

j

j=1

j

Self-similar processes produce a monotonically increasing IDC. Plotting log IDC(L) against log L results in an asymptotic straight line with slope 2H -1(Leland, Taqqu , Willinger and Wilson , 2003).

2. Rescaled Range Analysis

For a given set of observations X = {Xn, n∈Z} with sample meanX(n), sample variance

+

−

S2(n), and range R(n), the rescaled adjusted range or R/S statistic is given by

R(n)max(0,Δ1,Δ2,...,Δn)−min(0,Δ1,Δ2,...,Δn) =S(n)S(n)

Where

Δ

k

=

∑

k

X

i

−kX

i=1

for k= 1,2,….,n. It is also observed that for many natural phenomena

⎡R(n)⎤

E⎢≈cnH ⎥⎣S(n)⎦

as n→∞ and c being a finite positive constant independent of n. Taking the logarithm of both sides, we have

4

Elagha & AlShafee

⎧⎡R(n)⎤⎫⎨E⎢⎥⎬≈Hlog(n)+log(c)

S(n)⎦⎭⎩⎣

⎡R(n)⎤

Thus, one can estimate H by plotting log { E⎢} versus log(n) on a graph, and least-squares ⎥⎣S(n)⎦

fitting a straight line, with slope H, through the resulting points.

EMU’s ATM Traffic Measurements and Analysis

The EMU Network

The measurements were made on the Eastern Mediterranean University ATM network. Univer-sity’s ATM Network is completely built with FORE SYSTEMS, Inc.’s devices. Some of the de-vices in this ATM network can be listed as an ATM backbone switch, ATM workgroup switches and special devices for video and voice over ATM.

Measuring Tool and Configuration

The measurements were made in the EMU Computer Center using the ATM Sniffer Pro. ATM Sniffer Pro is a full bandwidth, Asynchronous Transfer Mode analysis and management system. It is designed to be used by network managers, technicians, and development engineers involved with all aspects of ATM technology. ATM Sniffer Pro allows the user to monitor, analyze, and manage the physical interface to each ATM device, as well as the traffic passing through each port.

There are two analysis devices which can be used with the ATM Sniffer Pro, the ATM Book and UTP-5 Pod. UTP-5 Pod presents the data as ATM frame size in multiples of 48 bytes (the same size of the payload of ATM cells), but the ATM book presents the data as ATM cells. Since the ATM book is not available, we used the UTP-5 Pod.

We can connect the UTP-5 pod to the network in either of the following two methods:

1. 2.

User-to-Switch. In this method, the pod is installed between an ATM switch and a workstation with ATM adaptor card.

Switch-to-Switch. In this method, the pod is installed between two switches in the ATM network.

The Measured Data

In both of the above configurations the measured data was the number of cells received in one-second intervals.

In the first scenario, the ATM Sniffer Pro is connected to the network as user-to-Switch Configu-ration. Two data files were captured, EMUN1, EMUN3; each file contains about 620,000 cells in a 60 hours capture duration.

In the second measurement scenario, the ATM Sniffer Pro is connected to the network as switch-to-Switch Configuration. Two data files were captured, EMUN2, EMUN4. Even though, all files contains approximately the same number of cells, the capture duration was about 30 minutes to 6 hours according to the network load, which is very small compared with the first scenario. A summary description of these data sets is given in Table 1.

5

On the Self-Similar Nature of ATM Network Traffic

Table 1: Summary of Data Sets

File name

Number of cells

Length (hour)

Configuration

EMUN1 620,000 62 hour User-to-switch EMUN2 656,128 6.5

hour EMUN3 620,000 59.5

hour

EMUN4 688,882 ½ hour Switch-to switch Switch-to switch User-to-switch

Analysis

To test the self-similarity parameter H, we performed the IDC plots analysis. Figure 1, shows the IDC curve corresponding to the trace EMUN1. The sequence of cell counts in every one-second interval was analyzed. The IDC curve for the EMUN1 file increases monotonically throughout a time span that covers 3-4 orders of magnitude and shows an asymptotic slope that is strictly dif-ferent from the horizontal line resulting in an estimate H of 0.84. This behavior is in stark contrast to conventional traffic models such as Poisson processes, where the IDC is constant (H = 0.5). The same analysis is made for the second data set (EMUN2); the analyzed process was the se-quence of cells in each second interval as in the case of EMUN1.

We can conclude, that for the EMUN measurements the estimated value of H is about 0.85 for all the data sets and the measured ATM traffic definitely exhibit the features of self-similarity. To estimate the self-similarity parameter H more precisely, more refined statistical methods with confidence intervals for H and longer measurements with more data are needed.

Ploting LOG IDC(L) against LOG L3.5LOG10 IDC(L)32.521.510.5002LOG10 L4

EMUN1(H=0.84)EMUN2(H=0.87)Figure 1: IDC Plots for EMUN1, EMUN2

6

Elagha & AlShafee

Modeling of Self-Similar Traffic

There are three different promising self-similar traffic generators based on different modeling approaches:

1. Fractional Brownian traffic

This model was introduced by Norros (1993). The fractional Brownian traffic is a process of the form At = mt + sqrt (am) Zt, where At is the amount of traffic in [0, t), and Zt is a normalized fractional Brownian motion, i.e., a strictly self-similar process. The process has three parameters: the mean input rate m, the variance coefficient a and the Hurst-parameter H of Zt. 2. Superposed on/off sources

The model was introduced by Mandelbrot (1994). The basic idea of the model is the construction of self-similar processes based on aggregating many simple on/off processes with heavy-tailed on and off periods. 3. Chaotic maps

Erramiili and Singh (1994, 1999) proposed chaotic maps for fractal traffic modeling. The under-lying idea is based on a nonlinear map that describes the evolution of a state variable over dis-crete time.

Performance Testing

The self-similar traffic traces of the models were generated by Monlar and Vidacs (2005). They calculated the value of the Hurst-parameter of synthetic traffic traces as given in Table 2.

Table 2: Hurst-parameter for synthetic traffic models Traffic Trace Fractional Brownian traffic

Superposed on/off sources Chaotic maps

Hurst-parameter value 0.71 0.73 0.80

The investigated three different models are all capable to capture the self-similar properties of ATM traffic but the chaotic map model was found to be the closest model for EMU network traf-fic.

Conclusion

In this paper, we presented ATM traffic measurements, analysis and modeling results focusing on capturing the self-similarity phenomenon. On the basis of the considerations presented in our pa-per, the following conclusions can be drawn:

For the EMUN measurements, the calculated value of H is about 0.85 for all the data sets and the measured ATM traffic definitely exhibit the features of self-similarity. To estimate the self-similarity parameter H more precisely, more refined statistical methods with confidence intervals for H and longer measurements with more data are needed. The interpretation of the estimated Hurst parameter is problematic in practice.

7

On the Self-Similar Nature of ATM Network Traffic

The most promising modeling approach in our case is the chaotic map model. The synthetic traf-fic trace generated by the model has nearly the same statistical properties and self-similar features than the measured traffic trace.

Some important areas that are impacted by self-similarity are data analysis, statistical inference, mathematical modeling, queueing and performance analysis. These are questions that are still under investigation and research, and more efforts must be done in the future to answer them.

References

Abry, P. & Veitch, D. (2005). Wavelet analysis of long range dependent traffic. IEEE Transactions on In-formation Theory, 44(1). Beran, J. (1994). Statistics for long-memory processes. Chapman and Hall.

Bjorkman, N., Latour-Henner, A., Hasson, U., Pers, O., & Miah, A. (1995). Practical ATM resource di-mensioning based on real-time traffic measurements and analysis. GLOBECOM, 1, 399-403. Cox, D.R & Lewis, P.A.W. (1966). The statistical analysis of series of events. Menthuen. Erramilli, A. (1994). Chaotic maps as models of packet traffic. Proceedings of ITC-14.

Leland, W., Taqqu, M., Willinger, W., & Wilson, D. (2003). On the self-similar nature of Ethernet traffic.

IEEE/ACM Transactions on Networking, 2(1). Mandelbrot, B.B. (1994). Long-run linearity, locally Gaussian processes, H-spectra and infinite variances.

International Economic Review, 10, 54- 60. Monlar, S. & Vidacs, A. (2005). On modeling and shaping self-similar ATM traffic. TR. High speed Net-works Laboratory, Department of Telecommunications and Telematics, Technical University of Buda-pest, Budapest, Hungary. Norros, I. (1993). Studies on a model for connectionless traffic, based on fractional Brownian motion. Con-ference on Applied Probability in Engineering, Computer and Communication Sciences, Paris, France, June. Norros. I. (1995). On the use of fractional Brownian motion in the theory of connectionless networks. IEEE

JSAC, 13(6), 953-962, August. Norros, I. (2004). A storage model with self-similar input. Queueing Systems Theory and Applications, 16,

387-396. Singh, R.P. & Erramilli, A. (1999). Application of deterministic chaotic maps to model packet traffic in

broadband networks. Proceedings of 7th ITC Specialists Seminar, pp. 8.1.1- 8.1.3. Stallings, W. (1998). High-speed networks TCP/IP and ATM design principles. Prentice-Hall.

Stamoulis, G.D., Anagostu, M.E., & Georgantas, A.D. (1994). Traffic source models for ATM networks: A

survey. Computer Communications,17(6), 428-438. Willinger, W., Taqqu, M.S., Sherman, R. & Wilson, D.V. (2004). Self-similarity through high variability:

Statistical analysis of Ethernet LAN traffic at the source level. IEEE/ACM Transactions on Network-ing, 5(1).

8

Elagha & AlShafee

Biographies

Humam Elagha is currently a PhD student at Faculty of Information Systems and Technology at Arab Academy for Banking and Financial Sciences, Jordan. His main research interests include IT Governance, Strategic Alignment, IT Value Assessment and High Speed Networks Measurements and Analysis. He holds BSc and MSc in Computer En-gineering from Eastern Mediterranean University, Cyprus. He worked as a full-time lecturer at Faculty of Information Technology at Islamic University of Gaza, Palestine. He teaches Database Management Sys-tems, Management Information Systems, Operating systems, Software Engineering, Systems Analysis and Design, Logic Design, Computer

Networks, Systems Simulation and Automata Theory Courses. He is a Certified ATM Network Manager. His work appears in number International Journals and Conferences. He is a member of ACM and IEEE.

Maher Alshafee is currently Programmer and Training Coordinator at the Information Technology Center / Royal Scientific Society, Jordan. His research interests include Information Systems Management, Technology Change Management, Human Recourses Management, Software Engineering, Network Analysis and Quality Assurance. He holds BSc in Computer Studies and Information Technology from Eastern Mediterranean University, Cyprus. He worked at UNITED NATIONS EDUCATIONAL, SCENTIFIC AND CULTURAL OR-GANIZATION “UNESCO” as Technical Support & Quality Assur-ance (QA) Supervisor for the International Computer Driving License (ICDL) Programme, executed by the UNESCO Cairo Office, the ICDL Program in Jordan. He is a Training Coordinator Professional. His work appears in number International Journals and Conferences. He is

a member of ACM and IEEE.

9