Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A method for analyzing, modeling and simulating a two-level arrival--counting process is presented. This method is particularly appropriate when the number of independent processes is large. The initial motivation for this method was the need to analyze and represent computer file system trace data that involves activity on some 8,000 files. The method is also applicable to network trace data characterizing communication patterns between pairs of computers. Cluster analysis with a novel stopping rule is used to decompose the arrival process into groups. The resulting clusters can be characterized using the time between clusters, the time between arrivals within clusters, and the size of each cluster. Each of these three components is then analyzed as a univariate problem. The effectiveness of this method is measured by comparing the output of a simulation driven by the original trace data to the output of the same simulation driven by the input model.

REFERENCES

• 1: Devroye, L. (1986), Non-Uniform Random Variate Generation, Springer-Verlag, New York, NY.
• 2: Guy, R. G., Heidemann, J. S., Mak, W., Page, Jr., T. W., Popek, G. J. & Rothmeier, D. (1990), Implementation of the Ficus replicated file system, in 'USENIX Conference Proceedings', USENIX, pp. 63-71.
• 3: Hisgen, A. (1990), Dec firefly trace data, Data obtained from author on 8mm tape.
• 4: Jain, R. (1991), The Art of Computer Systems Performance Analysis: Techniques for Experiment Design, Measurement, Simulation and Modeling, John Wiley & Sons, Inc.
• 5: Jain, R. & Routhier, S. A. (1986), 'Packet trainsmeasurements and a new model for computer network traffic', IEEE Journal on Selected Areas in Communications SAC-4(6), 986-995.
• 6: Johnson, N. L. (1949), 'Systems of frequency curves generated by methods of translation', Biometrika 36, 149-176.
• 7: Kaufman, L. & Rousseeuw, J. (1990), Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc, New York, NY.
• 8: Milligan, G. W. & Cooper, M. C. (1985), 'An examination of procedures for determining the number of dusters in a data set', Psychometrika 50(2), 159-179.
• 9: Ord, j. K. (1972), Families of Frequency Distributions, Griffin, London.
• 10: Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990 [doi>10.1109/12.54838]
• 11: Swain, J. J., Venkatraman, S. & Wilson, J. R. (1988), 'Least-squares estimation of distribution functions in Johnson's translation system', Journal of Statistical Computation and Simulation 29, 271-297.
• 12: D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States [doi>10.1145/224056.224070]