×

A stochastic model of data access and communication. (English) Zbl 0681.68130

Summary: Stochastic models are an important technique for predicting the performance of computer systems and communication networks. Although much work has been done to develop analytic and simulation models, these models usually assume that data access is uniformly distributed, that data is static, and that data access and communication occur according to the Poisson process. In practice, data access is highly skewed, does not occur at Poissonian times, and data items are constantly being created and deleted. A new stochastic model of data access is developed that includes all of these observed phenomena. The model displays a suprising richness of behaviour and yet has a small number of independent parameters, is analytically tractable, and is easy to simulate. An axiomatic framework for a general class of continuous models is introduced, and a specific discrete approximation of such a model is developed in detail. The extent to which the model fits empirical observations is also discussed.

MSC:

68U20 Simulation (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baclawski, K., An Algorithm for Generating Random Data Accesses, (Technical Report No. NU-CCS-87-27 (1987), Northeastern University, College of Computer Science)
[2] Fedorowicz, J., A Zipfian model of inverted file storage requirements, (Proceedings, 12th Annual Pittsburgh Conf. on Modeling and Simulation (April 1981)), 1393-1399
[3] Fedorowicz, J., The theoretical foundation of Zipf’s law and its application to the bibliographic database environment, J. Amer. Soc. Inform. Sci., 33, 285-293 (1982)
[4] Fedorowicz, J., Database performance evaluation in an indexed file environment, ACM Trans. Database Systems, 12, No. 1, 85-110 (1987)
[5] Gawlick, D., Processing of “hot spots” in high performance systems, (Proceedings of COMPCON ’85 (1985))
[6] Gawlick, D.; Kinkade, D., Varieties of concurrency control in IMS/VS Fast Path, IEEE Bull. Data Eng., 8, No. 2, 3-10 (1985)
[7] Hill, B., Zipf’s law and prior distributions for the composition of a population, J. Amer. Statist. Assoc., 65, 1220-1232 (1970) · Zbl 0224.92011
[8] Hill, B.; Woodroofe, M., Stronger forms of Zipf’s law, J. Amer. Statist. Assoc., 70, 212-219 (1975) · Zbl 0326.92014
[9] Mandelbrot, B., The Fractal Geometry of Nature (1982), Freeman: Freeman San Francisco · Zbl 0504.28001
[10] O’Neil, P., The escrow transactional method, ACM Trans. Database Systems, 11, No. 4, 405-430 (1986)
[11] Reuter, A., Concurrency on high-traffic data elements, (Proceedings, 1st ACM SIGACT-SIGMOD Symp. on Principles of Database Systems (March 1982)), 83-92
[12] Sichel, H., On a distribution law for word frequencies, J. Amer. Statist. Assoc., 70, 542-547 (1975)
[13] Tay, Y.; Goodman, N.; Suri, R., Locking performance in centralized databases, ACM Trans. Database Systems, 10, No. 4, 415-462 (1985) · Zbl 0579.68025
[14] Voldman, J.; Mandelbrot, B.; Hoevel, L. W.; Knight, J.; Rosenfeld, P., Fractal nature of software-cache interaction, IBM J. Res. Develop., 27, 164-170 (1983)
[15] Zipf, G., Human Behavior and the Principle of Least Effort (1949), Addison-Wesley: Addison-Wesley Reading, MA
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.