Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005

# Simulation Simplified

Prof. Alan Kaminsky
Rochester Institute of Technology -- Department of Computer Science

 Preface A Dice Game Bernoulli Distribution Gathering and Displaying Data Chi-Square Test A Distributed Encyclopedia Graphs Random Subsets and Permutations Breadth-First Search Mean, Median, and the Like Knob Turning Regression Multiple Knob Turning Discrete Event Simulation Exponential Distribution Priority Queues A Web Server A DOS Attack Uniform Distribution A Distributed Encyclopedia, Part 2 Encyclopedia: Scalable? Source Code Listings Further Reading

## Preface

While teaching various courses, including Data Communications and Networks, Ad Hoc Networks, and Distributed Systems, I have found myself wanting to explore questions such as these with the class:

• How long does it take for a packet to travel from source to destination through a network of routers?

• What is the probability that a packet will be dropped due to congestion in the network as a function of the network traffic level?

• A bunch of sensor nodes are placed at random positions within a certain area. The nodes' transmitters are not powerful enough to reach the base station; instead, messages are relayed from node to node until they reach the base station. Will the base station be able to communicate with every sensor node?

• A group of peer devices is organized into a distributed hash table (DHT). A query originates at a certain device and hops from device to device according to a certain algorithm until the query reaches the device containing the answer. The DHT algorithm's authors claim that the number of hops is proportional to the logarithm of the number of devices. Is it?

There are three ways to answer such questions:

• Build the actual system, collect data by observing the system in operation, and answer the questions by analyzing the data. But this might be prohibitively expensive, or it might take too long, or it might not be possible to measure the desired quantities, or one might want to design the system before actually building it.

• Make a mathematical model of the system and answer the questions by analyzing the model. But the system might be too complicated to make a mathematical model (at least one that can be easily analyzed), or one might lack the mathematical skill to build and analyze a model.

• Write a computer program to simulate the system, run the program to collect data, and answer the questions by analyzing the data. This is often much more practical than the alternatives.

There exist general-purpose simulation languages, as well as specialized simulation packages in various domains, such as network simulation. However, I've usually found these languages and packages to be large, complex, and feature-laden, such that writing even a simple little simulation requires climbing a steep learning curve. At the same time, I've usually found these languages and packages to lack features I want, and it's either difficult (because the language's or package's source code is unreadable) or impossible (because the language or package is proprietary) to add features.

All is not lost! I have found that with the ability to write high level language code plus a modicum of background in probability and statistics, one can develop a broad range of useful simulation programs. However, the techniques for writing simulation programs are not usually taught in computer science curricula. Through a series of examples in Chapters 1-20, this book teaches the art of simulation programming. This book is intended to be used as a supplement in a course that uses simulation as an investigatory tool.

The Java programming language is used for the examples in this book. However, those with experience in other high level languages should have no difficulty following the discussion and adapting the programs to their preferred language. The example program source files are free, GNU GPL licensed software and may be downloaded from my web site (http://www.cs.rit.edu/~ark/ss/). Source file listings appear in Appendix A.

This book also makes use of Java classes from my Parallel Java 2 Library. The Parallel Java 2 Library is free, GNU GPL licensed software and may be downloaded from my web site (http://www.cs.rit.edu/~ark/pj2.shtml). The download includes complete source code and Javadoc documentation. While the Parallel Java 2 Library is mainly intended for writing parallel programs in Java, it contains many classes useful for non-parallel programs as well. (I may discuss parallel simulation programming in a later edition of this book.)

For those desiring further information about various topics mentioned in this book, I recommend the sources listed in Appendix B, "Further Reading."

Alan Kaminsky
February 2014

The program source files described in this book and listed in Appendix A ("The Programs") are copyright © 2014 by Alan Kaminsky.

The Programs are free software: you can redistribute them and/or modify them under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

The Programs are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with The Programs. If not, see http://www.gnu.org/licenses/.

The book Simulation Simplified, version 04-Feb-2014 (1,486,110 bytes): ss20140204.pdf
Please consider the environment before printing this book!

Java archive with example programs, version 04-Feb-2014 (31,377 bytes): ss20140204.jar

## Source Code Listings

 1. A Dice Game — Class Dice01 — Class Dice02 2. Bernoulli Distribution — Class Dice03 — Class edu.rit.numeric.BernoulliPrng — Class Dice04 3. Gathering and Displaying Data — Class Dice05 — Class Dice06 4. Chi-Square Test — Class Dice07 6. Graphs — Class P2Pedia01 7. Random Subsets and Permutations — Class edu.rit.util.RandomSubset — Class P2Pedia01 8. Breadth-First Search — Class P2Pedia01 9. Mean, Median, and the Like — Class P2Pedia02 — Class P2Pedia03 — Class P2Pedia03a 10. Knob Turning — Class P2Pedia04 11. Regression — Class P2Pedia05 12. Multiple Knob Turning — Class P2Pedia06 14. Exponential Distribution — Class edu.rit.numeric.DoublePrng — Class edu.rit.numeric.ExponentialPrng 15. Priority Queues — Class edu.rit.sim.Event — Class edu.rit.sim.Simulation 16. A Web Server — Class WebServer01 17. A DOS Attack — Class WebServer02 18. Uniform Distribution — Class edu.rit.numeric.UniformPrng 19. A Distributed Encyclopedia, Part 2 — Class P2Pedia07 20. Encyclopedia: Scalable? — Class P2Pedia08

 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005