On the estimation of Hurst exponent with application to network traffic analysis

• Autorzy: Włodarski P.
• Języki publikacji: EN

Abstrakty

EN

It is generally accepted that computer network traffic reveals second-order self-similar properties. It has a big impact on queueing performance, which ensures the quality of service expected by network users. This article discusses the most often used methods of estimating Hurst exponent that is responsi-ble for the level of self-similarity in network traffic. The results are based on measurements in computer networks. A new method of aggregating random variable that leads to more stable results obtained by variance-time and Index of Dispertion for Counts method is proposed. It has also been shown that an analysis of network performance based on real network traffic and self-similar models is closely related to the value of Hurst exponent

PL

Powszechnie wiadomo, że natężenie ruchu w sieciach komputerowych wykazuje występowanie cechy samopodobieństwa. Ma to duży wpływ na wydajność kolejkowania, która z kolei ściśle związana jest z zapewnianiem odpowiedniego poziomu usług (QoS) wymaganego przez użytkowników aplikacji sieciowych. Tradycyjne podejście do analizy ruchu sieciowego oparte o modele Poissona czy Markova, gdzie strumień pakietów jest nieskorelowany albo wykazuje cechy zależności krótkoterminowej (short-range dependent SRD), pociąga za sobą niedokładności w analizie. Skorelowany ruch powoduje bowiem dłuższe opóźnienia i wyższy poziom strat pakietów. W artykule omówiono najczęściej stosowane metody estymacji wykładnika Hursta, parametru odpowiedzialnego za poziom samopodobieństwa w ruchu sieciowym. Wszystkie przedstawione wyniki oparte są o pomiary przeprowadzone w rzeczywistych sieciach komputerowych. Zaproponowano nową metodę agregacji zmiennej losowej, która prowadzi do bardziej stabilnych rezultatów otrzymanych przez metody variance-time oraz Index of Dispertion for Counts. Pokazano również, że analiza wydajności oparta z jednej strony o zarejestrowany ruch w sieciach komputerowych, z drugiej o modele samopodobne, odgrywa kluczową rolę w wyznaczaniu parametrów QoS dla usług czasu rzeczywistego takich jak Yoice over IP czy Video on Demand.

Słowa kluczowe

EN

traffic analysis; QoS

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2006
• Tom: Vol. 18, nr 1
• Strony: 29--56
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Włodarski P.

• Szczecin University of Technology Chair of Signal Processing and Multimedia Engineering Computer Science Depertment 26 Kwietnia 10, 71-126 Szczecin

Bibliografia

• [1]   Abry, P., Yeitch, D., Wavelet analysis of long-range dependent traffic. IEEE Trans. Information Theory,44(l), 1998,2-15.
• [2] Abry, P., Yeitch, D., Flandrin, P., Long-range dependence: revisiting aggregation with wavelets. Journal of Time Series Analysis, 19 (3), 1998, 253-266.
• [3] Anis, A. A., Lloyd, E. H., The expected value of the adjusted rescaled Hurst rangę of independent normal summands. Biometrika 63, 1976, 111-116.
• [4] Czachórski, T., Modele kolejkowe w ocenie efektywności sieci i systemów komputerowych.. Wydawnictwo pracowni komputerowej Jacka Skalmierskiego, 1999.
• [5] Horning, Ch., Standard for the transmission of IP datagrams over Ethernet networks. RFC-894, Symbolics Cambridge Research Center, 1984.
• [6] Leland, W., Wilson, D., High Time-Resolution Measurement and Analysis of LAN Traffic: Implications for LAN interconnection. Proceedings of the IEEE INFOCOM'91, Bal Harbour, FL, 1991, 1360-1366.
• [7] Le-Ngoc T., Subramanian S. N., A Pareto-modulated Poisson process (PMPP) model for long-range dependent traffic. Computer Communications, 2000, 123-132.
• [8] Leland, W., Taqqu, M., Willinger, W., Wilson, D., On the self-similar nature of Ethernet traffic (extended version). IEEE/ACM Transactions on Networking, 2, l (Feb 1994) 1-15.
• [9] Lin G. C., Suda, T., On the impact of long-range dependent traffic in dimensioning ATM network buffer. Proc. Of IEEE INFOCOM, 1998.
• [10] Medhi, J., Stochastic models in queueing theory. Academic Press, 2003.
• [11]  Norros, L, A storage model with self-similar input. Queueing Systems, 16, 1994, 387-396.
• [12] Peitgen, H. O., Jurgens, H., Saupe, D., Chaos and Fractals: New Frontiers of Science. Springer Verlag, 1992.
• [13] Peha, J. M., Retransmission mechanisms and self-similar traffic models, IEEE/ACM/SCS Communication Networks and Distributed Systems Modeling and Simulation, 1997, 47-52.
• [14] Park, K., Kim G,. T., Crovella, M. E., On the relationship between file sizes, transport protocols and self-similar network traffic. Technical report, Boston University, Computer Science Department, 1996.
• [15] Park, K., Willinger, W., Self-similar network traffic and performance evaluation. John Wiley & Sons, 2000.
• [16] Paxson, V. Fast, Approximate synthesis of fractional Gaussian noise for generating self-similar network traffic. ACM SIGCOMM Computer Communication Review 27, 5 (Oct 1997), 5-18.
• [17] Postel, J., Internet protocol. RFC-791, USC/Information Sciences Institute, 1981.
• [18] Robinson, P. M., Gaussian semiparametric estimation of long-range dependence. The Annals of Statistics, 23, 1995, 1630-1661.
• [19] Taqqu M. S., Teverovsky V., Robustness of Whittle-type estimators for time series with long-range dependence. Stochastic Models, 13, 1997, 723-757.
• [20] Taqqu M. S., Teverovsky V., Willinger W., Estimators for long-range dependence: an empirical study. Fractals, 3 (4), 1995;785-798.
• [21] Veitch, D., Abry, P., A wavelet based joint estimator for the parameters of LRD. IEEE Transactions on Information Theory, 45 (3), 1999.