Multiscale analysis and control of networks with fractal traffic. (English) Zbl 0984.90006

Summary: A recently introduced multiscale framework is used to develop efficient analysis and design techniques for networks with self-similar traffic. These allow the inter-arrival density function for fractal point processes under Bernoulli random erasure to be determined, as well as the counting process distribution for superposition of these processes. The results suggest that fractal characteristics are preserved under traffic branching and merging, which may, in turn, provide insight into the prevalence of self-similarity in aggregate traffic broadly observed on real networks. Multiscale techniques are also developed for analyzing fractal queueing scenarios. The persistent memory inherent in the underlying point processes leads to substantially different behavior than is observed in traditional queueing scenarios, and important implications on resource consumption and quality of service are discussed. Finally, we show how multiscale methods can be used with dynamic programming techniques to develop efficient and practical control policies for these fractal queues. In particular, optimal server control is developed for a memoryless queueing system with self-similar traffic input, and optimal flow control is formulated for self-similar service of memoryless traffic. Exploiting recent history, these controllers are shown to achieve substantially better performance, both in terms of quality of service and resource utilization, than queueing control strategies traditionally used.


90B20 Traffic problems in operations research
90C39 Dynamic programming
90B22 Queues and service in operations research
90B18 Communication networks in operations research
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
Full Text: DOI Link


[1] Beran, J.; Sherman, R.; Taqqu, M.S.; Willinger, W., Long-range dependence in variable-bit-rate video traffic, IEEE trans. comm., 43, 1566-1579, (1995)
[2] Leland, W.E.; Taqqu, M.S.; Willinger, W.; Wilson, D.V., On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM trans. network., 2, 1-15, (1994)
[3] Mandelbrot, B., Self-similar error clusters in communication systems and the concept of conditional stationarity, IEEE trans. comm. tech., 13, 71-90, (1965)
[4] Paxson, V.; Floyd, S., Wide area traffic: the failure of Poisson modeling, IEEE/ACM trans. network., 3, 226-244, (1995)
[5] D. H. Johnson, and, A. R. Kumar, Modeling and analyzing fractal point processes, in, Proc. Int. Conf. Acoust. Speech, Signal Processing, 1990.
[6] Lowen, S.B.; Teich, M.C., Fractal renewal processes generate 1/f noise, Phys. rev. E, 47, 992-1001, (1993)
[7] Willinger, W.; Taqqu, M.S.; Sherman, R.; Wilson, D.V., Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level, Computer comm. rev., 25, 100-113, (1995)
[8] Lam, W.M.; Wornell, G.W., Multiscale representation and estimation of fractal point processes, IEEE trans. signal process., 43, 2606-2617, (1995)
[9] Kleinrock, L., Queueing systems, (1975), Wiley New York · Zbl 0334.60045
[10] Lam, W.M., Multiscale methods for the analysis and application of fractal point processes and queues, (1997), Massachusetts Institute of Technology Cambridge
[11] Sussman, S.M., Analysis of the Pareto model for error statistics on telephone circuits, IEEE trans. comm. sys., 11, 213-221, (1963)
[12] Neuts, M., Matrix-geometric solutions in stochastic models, (1981), Johns Hopkins Univ. Press Baltimore
[13] Law, A.M.; Kelton, W.D., Simulation modeling and analysis, (1991), McGraw-Hill New York
[14] Addie, R.G.; Warfield, R.E., Bandwidth switching and new network architectures, Teletraffic sci., ITC-12, 665-671, (1989)
[15] Hui, J.Y., Resource allocation for broadband networks, IEEE trans. comm., 6, 1598-1608, (1988)
[16] Bertsekas, D.P., Dynamic programming and optimal control, (1995), Athena Scientific Belmont · Zbl 0904.90170
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.