SIM.JS - Discrete Event Simulation in JavaScript

• Download demo - 10.9 KB
• Download sim-0.26-debug.js.zip - 10.1 KB

 

Introduction 

SIM.JS (project website) is a general-purpose Discrete Event Simulation library written entirely in JavaScript and capable of running on a web browser.

SIM.JS is a library for modeling discrete time event systems:

• The library provides constructs to create Entities which are the active actors in the system and encapsulates the state and logic of components in a system.
• The entities contend for resources, which can be Facilities (services that are requested by entities; supports FIFO, LIFO with preemption and Processor Sharing service disciplines), Buffers (resources that can store finite amount of tokens) and Stores (resources that can store JavaScript objects).
• The entities communicate by waiting on Events or by sending Messages.
• Statistics recording and analysis is provided by Data Series Statistics (collection of discrete, time-independent observations), Time Series Statistics (collection of discrete, time-dependent observations) and Population Statistics (the behavior of population growth and decline).
• SIM.JS also provides a random number generation library to generate seeded random variates from various distributions, including uniform, exponential, normal, gamma, pareto and others.

SIM.JS is written in *idiomatic* JavaScript. The library is written in event-based design paradigm: the changes in system states are notified via callback functions. The design takes advantage of the powerful feature sets of JavaScript: prototype based inheritance, first-class functions, closures, anonymous functions, runtime object modifications and so on. Of course, a knowledge of these principles is not required (a lot of this behind the scenes), but we do certainly hope that using SIM.JS will be pleasurable experience for the amateur as well as the experienced practitioners of JavaScript.

Background

Briefly speaking, Discrete Event Simulation (DES) is a technique to model a complex system in order to study its behavior. The system is modeled as a collection of states that change over time. Within DES, the time advances in discrete steps. We refer the readers to the excellent article at Wikipedia and the references therein as an entry point to this interesting field of Computer Science.

A typical model of a system includes (a) entities, which are the active actors in the system and encapsulate the state and logic of the system components, (b) resources, which are consumed by the entities, (c) communication primitives, to coordinate actions between entities across time, and of course, (d) statistics, which is the output of a simulation run.

Using the Code

Lets try to simulate a buffet-style restaurant. Customer arrive at restaurant, pick up food from buffet area (we will assume only one food item: salad), reach cashier for payment and leave the restaurant. The salad buffet is a finite resource, and is replenished every few minutes by the chef. In this restaurant the customers may have to wait at two places:

• At the buffet. If the salad is all gone, customers have to wait until the chef brings in more.
• At the cashier. If there are other customers ahead in line.

Simulation Objectives. We would like to find out: The average time spent by customers at the restaurant? The average number of customers inside the restaurant?

We observe first that the system has two resources:

1. The salad buffet. We will model this as Buffer.
2. The cashier. We will model her as Facility.

There will be two entities in the system: the chef and the customers. We will use Population Statistics to record the arrival and departure of customers. The following code lists all the global variables we will need in our simulation:

var sim = new Sim();
var stats = new Sim.Population();
var cashier = new Sim.Facility('Cashier');
var buffet = new Sim.Buffer('Buffet', BuffetCapacity);
var random = new Random(Seed);

Lets start with the Entity Prototype for Chef first. The chef replenishes the salad buffer every PreparationTime interval. The code is very simple:

var Chef = {
    start: function () {
        this.putBuffer(buffet, BuffetCapacity - buffet.current());
        this.setTimer(PreparationTime).done(this.start);
    }
};

Note here that the chef fills only the empty portion in the buffet. Next, let us look at the Customer entity. This entity prototype will generate request for all customers, where the time interval between customer arrivals is exponentially distributed. We will first look at the start function, which is somewhat similar to the start function of Chef. The customer will order (this.order(), which we will see next), and the function is called again after an exponentially distributed random delay:

var Customer = {
    start: function () {
        this.order();

        var nextCustomerAt = random.exponential (1.0 / MeanArrival);
        this.setTimer(nextCustomerAt).done(this.start);
    },
    ...

The Customer.order() function models the actions of customers inside the restaurant. First we will log the arrival of customer (line 3) and record in the statistics object (line 6). The customer then request to get one unit from the buffer (line 8) and will execute the anonymous function (argument to done() function) when the request is satisfied. The request may be satisfied immediately, if the buffer not empty, or wait otherwise. In the callback function, we log again that the customer has cleared the buffer stage and will now proceed to the cashier (line 10). The service time at cashier is also exponential distributed (line 13), and we use the this.useFacility() function to request service from the cashier (line 14). The callback function here will log that the customer will now leave the restaurant (line 16) and we also record this time in the statistics (line 20).

 1 order: function () {
 2     // Logging
 3     sim.log("Customer ENTER at " + this.time());
 4
 5     // statistics
 6     stats.enter(this.time());
 7
 8     this.getBuffer(buffet, 1).done(function () {
 9         // Logging
10         sim.log("Customer at CASHIER " + this.time()
11             + " (entered at " + this.callbackData + ")");
12
13         var serviceTime = random.exponential(1.0 / CashierTime);
14         this.useFacility(cashier, serviceTime).done(function () {
15             // Logging
16             sim.log("Customer LEAVE at " + this.time()
17                 + " (entered at " + this.callbackData + ")");
18
19             // Statistics
20             stats.leave(this.callbackData, this.time());
21         }).setData(this.callbackData);
22     }).setData(this.time());
23 }

Finally, we create entities (lines 1 and 2), optionally set a logger function (lines 5-7), start the simulation (line 9) and report back the statistics (line 11).

 1 sim.addEntity(Customer);
 2 sim.addEntity(Chef);
 3
 4
 5 sim.setLogger(function (msg) {
 6     document.write(msg);
 7 });
 8
 9 sim.simulate(Simtime);
10
11 return [stats.durationSeries.average(),
12        stats.durationSeries.deviation(),
13        stats.sizeSeries.average(),
14        stats.sizeSeries.deviation()];

You can play with this simulation model (in your web browser!).

Points of Interest

Simulations have always been done in C/C++, so why Javascript?

• The authors of this library are passionate about Discrete Event Simulations, and hope to see its widespread use in education as well as everyday applications. The authors also believe that in this era of Web 2.0, web-based applications are the best way to reach people. Which is why they concluded that there is a need for a Web enabled simulation engine. You can look at an interesting web-based M/M/1 Queue Simulator developed using SIM.JS.
• These days when one can boot linux with JavaScript, play Doom, run myriad of productivity applications on the Web, we ask – why not simulations? (And we say its about time!)

The quality of simulations highly depends on the random number generation libraries. However, the JavaScript’s native Math.random() function is not suited for Discrete Event Simulations, since:

• The Math.random() function cannot be seeded. There is no way to guarantee that the same random stream will be produced the next time the script is executed.
• There is only one stream of random numbers. Statistics purists frown upon when two independent random distributions are drawn from same seed.
• The javascript library provides only the uniform probability distribution function. In DES, as also in many other scientific applications, there is a need for other kinds of distributions, such as exponential, gaussian, pareto etc.
• The native Math.random() does not use (at the time of writing) the arguably better Mersenne Twister algorithm for random number generator.

We, therefore, ended up writing a random number generation ourself for SIM.JS. This library is available as a separate download as well from the project website.