I:     Simulation and Modeling

For example, an airport designer might know the rates at which airplanes are coming in from other airports and how long it takes for a single plane to land. The designer would like to estimate how many runways are needed to handle the load and how long, on average, the airplanes would have to circle before they could land. Since planes don't come in from different airports at perfectly spaced intervals, it would be hard to figure out the answers to these questions by hand. However, a simple program to simulate the airport traffic can give good estimates to the designer.

The variation in traffic from the other airports can be modeled by generating arrival times at random from some statistical distribution. Much research has been done on what this distribution should be. The computer simulation just keeps track of the interarrivals as they are randomly picked and computes the estimates needed by the designer.

In this case study we will look the design of a network router. Network routers are the connection points between different links in a network. Fig. 1 shows a diagram of a simple network router. The router takes incoming messages from other routers and computers on a network (the incoming lines) and copies them to another destination (the outgoing line).

Figure 1:  The Network Router

A network router has a set of input lines (feeder airports) that carry messages (airplanes) to the node. The router forwards the messages to the outgoing lines (runways). It takes a certain amount of time to send the message on the outgoing line (land the plane). During that time the outgoing line (runway) cannot be used for anything else. The designer would like to know, given the expected input traffic, how many output lines (runways) are needed. If the router does not allow messages to wait (planes to circle) until an outgoing line becomes available, the designer would also like to know how many messages are lost (Planes are usually sent back to originating airport instead by being thrown away.)

II.     Event-driven Simulation

A second, more-common strategy is called event-driven simulation. Each thing that happens is represented by an event. Examples of events are the arrival of a message or the sending of a message in the network simulation. In the airport simulations events may include taking off, circling the airport, landing and taxiing to the gate. The components of the model generate events. The simulation itself keeps track of the events and sends them to the appropriate component for processing in the order that they occurred. Time is updated to the time of the next event at each step in the simulation.

The idea of event-driven operation may seem strange at first. However, you have experienced this mode of operation in using interactive computer applications such as word processors. When you open such an application, the program does an initial setup and then waits for an event (e.g., a keystroke or a mouse-click from you indicating what to do). The program processes the event and then resumes waiting for you to do something else. In contrast, most of the programs that you write for your courses are execution-driven. They begin execution at a well-defined point (the main method) and continue executing a well-specified sequence of commands until completion.

III.     Events

Fig. 2 shows a definition of the Event class that we will use in the simulation. Notice that Event implements the Java Comparable interface. This means that Event objects can be ordered. In this case they are ordered by their times.

Figure 2:  The Event Class

public class Event implements Comparable {
   public static final int STOP = 0;
   public static final int MSG_ARRIVAL = 1;
   public static final int MSG_SENT = 2;
   private int who; // Who did it
   private int what; // What they did
   private double when; // When they did it

   public Event(int ID, int type,
                double time) {
      who = ID;
      what = type;
      when = time;
   }

   public int getWho( ) {return who;}
   public int getWhat( ) {return what;}
   public double getWhen( ) {return when;}

   public int compareTo (Object rhs)
              throws ClassCastException{
      double rhsTime = ((Event)rhs).getWhen();
      return when < rhsTime ? -1:
             rhsTime < when ? 1: 0;
   }

   public String toString(){
        return "[Who:" + who + ", What:" + what + ", When:" + when +"]";
    }
 
}

In the simulation we will want to process events in the order that they occur. The priority queue is a natural data structure for storing events in a specified order as they come in. We can use the deleteMin method of PriorityQueue to remove the event from the priority queue with the smallest when, that is, the event that happened first.

We will use the priority queue specification and implementations from the Weiss Data Structures Textbook (Fig. 3):
 

Figure 3:  The PriorityQueue Interface

public interface PriorityQueue { 
   Position insert( Comparable x )   // --> Inserts x
   Comparable deleteMin( )   // --> Removes and returns the smallest item
   Comparable findMin( )     // --> Returns smallest item
   void makeEmpty( )         // --> Removes all items
   boolean isEmpty( )        // --> Returns true if empty; else false
   int size( )               // --> Returns the size of the queue 
   void decreaseKey(Position p, Comparable newVal) //--> For special implementations
}

   int numberEvents = 100; 
   double maxTime = 1000;
   PriorityQueue p = new BinaryHeap();
   Random randproc = new Random();

   // Generate the events and put them on the queue
   for (int i = 0; i < numberEvents; i++) {
      Event e = new Event(i, Event.MSG_ARRIVAL, 
                          randproc.nextDouble()*maxTime);
      p.insert(e);
   }

   double lastArrival = 0.0;
   for (int j = 0; j < numberEvents; j++) {
      Event e = (Event)(p.deleteMin());
      System.out.println("Removing " + e);
      lastArrival = e.getWhen();
    }
    System.out.println("The average interarrival is " + 
                        (lastArrival/numberEvents));

IV.     Incoming Lines and Messages

For example, the network router shown in Fig. 1 has two incoming lines. Statistically, the two lines are identical, in the sense that over long periods they follow the same distribution of times between messages. When you look at the times of the individual messages, they appear to be random. The incoming lines of Fig. 1 generate messages in the following order:

• Line 0 at time 10
• Line 1 at time 10
• Line 1 at time 33
• Line 0 at time 45
• Line 1 at time 50
• Line 0 at time 64
• Line 1 at time 69

Arrival times that are generated from statistical distributions are generally specified as relative times or interarrival times. That is, they are specified as the time between the current message and the previous one. These times were generated from a statistical distribution that had an average interarrival time of 20, meaning that if we generated a lot of numbers and averaged them, we would expect to get an average of about 20.  The line interarrival times for the two lines above are:

Figure 4:  Calculating the interarrival times for individual incoming lines.

  The network router sees the messages from the two incoming lines interleaved as shown in Fig. 5.

Figure 5:   Message arrival times of multiple incoming lines are interleaved at the network router.

When multiple incoming lines (sources of messages) are generating messages for the network router, the router will see the messages interleaved. In this particular run, the average time between messages for the individual lines was 20, so when two lines contribute messages, one would expect a time between messages to be around 20/2= 10  if the simulation were run for a long time. Fig. 6 shows how to calculate the interarrival time of the interleaved message stream seen by the network router.

Figure 6:   Calculating the interleaved interrrival times

How would we use this in a simulation? Given incoming lines that know their interarrival times, we just need to keep track of the events in the order they occur. The average interarrival time can be computed simply as the arrival time of the most recent message divided by the total number of messages.

• Initialization:
• Set the time to 0.
• Ask each line to generate its first messages (e.g., 10 time units from now).
• The next thing of interest is at time 10 when messages arrive from lines 0 and 1.
• Update the time to 10 and process messages that arrived at time 10:
• Ask line 0 when its next message will come in (e.g., 35 time units from now at time 45).
• Ask line 1 when its next message will come in (e.g., 23 time units from now at time 33).
• The next event of interest is at time 33, when the second message arrives from line 1. Update the time to 33 and process messages that arrived at time 33 ... .

If we were going to implement the simulation, we would need an incoming line that can generate messages (message arrival events). Fig. 7 shows an implementation of the IncomingLine class. The IncomingLine keeps its current time in the time field. Each time getNextArrival is called, IncomingLine randomly picks the time until it generates the next message. It then updates its time to that time. The IncomingLine uses getNextPoisson from the Random class of weiss.util to generate interarrival times that follow the Poisson distribution. Research has shown that the Poisson distribution gives a good statistical description of arrival times for many real-world problems.

Figure 7:   An IncomingLine class

 import weiss.util.*;
 import eventpkg.*;
 public class IncomingLine {
   private double interarrival;
   private int ID;
   private int totalMessages;
   private Random randProc;
   private double time;

   public IncomingLine(int theID, double start, double arrivalParm) {
      interarrival = arrivalParm;
      ID = theID;
      totalMessages = 0;
      randProc = new Random(ID + 1);
      time = start;
   }

    public int getID( ) {return ID;}
    public double getTime( ) {return time;}
    public int getTotalMessages ( ) {return totalMessages;}

    public Event getNextArrival( ) {
       time += randProc.nextPoisson(interarrival);
       totalMessages++;
       return new Event(ID, Event.MSG_ARRIVAL, time);
    }

    public String toString ( ) { return "Incoming[ID:" + ID + ","
             + "arrivalParm:" + interarrival +"]: current time="
             + time + ", generated " + totalMessages + " messages"; }

}

V.     A Simulation of One Incoming Line

Typically the events are stored in a priority queue ordered by the time of the occurrence. Find the next event means calling deleteMin on that priority queue. We then update the current time to the time of the event that has just "occurred" and process the event.
 

Figure 8:  The basic simulation algorithm

• generate the initial events and insert them in the priority queue
• while the priority queue is not empty and the simulation has not stopped:
  • get and delete the next event from the priority queue
  • update current time to event's time
  • if the event is STOP, break
  • process the event (possibly generating new events and inserting them on the priority queue)

An implementation of this algorithm for one incoming line is shown in Fig. 9. The simulation creates a priority queue called eventSet to hold the events. The run method runs the simulation until a stoppingTime has been reached.

Figure 9:  A simulation with a single incoming line

import weiss.nonstandard.*;
public class SingleIncoming {

   private double currentTime;
   private PriorityQueue eventSet;
   private int numberEvents;
   private String simulationTitle;
   private boolean simulationStopped;

   private IncomingLine inLine;  //<<

   public SingleIncoming(String title, double arrival) {
        currentTime = 0.0;
        eventSet = new BinaryHeap( );
        numberEvents = 0;
        simulationTitle = title;
        simulationStopped = false;

        inLine = new IncomingLine(1, 0, arrival); //<<
    }

 
    final public void addEvent( Event e) { eventSet.insert(e); }
    final public int getEvents( ) { return numberEvents; }
    final public double getTime( ) { return currentTime; }
    final public String getTitle( ) { return simulationTitle; }
 
    public void initializeEvents( ) { //<<
       addEvent(inLine.getNextArrival());
    }

    public void initializeSimulation(double stoppingTime){
        addEvent(new Event(0, Event.STOP, stoppingTime));
        simulationStopped = false;
    }

    public void processEvent(Event e) { //<<
       switch (e.getWhat()) {
          case Event.MSG_ARRIVAL:
             addEvent(inLine.getNextArrival());
             break;
         case Event.STOP:
             setSimulationStopped();
             break;
         default:
             System.err.println(e +  " {unrecognized event}");
             break;
       }
    }   

    public void setSimulationStopped(){
        simulationStopped = true;
    }
 
    final public void run(double stoppingTime) {
        Event e = null;
        initializeSimulation(stoppingTime);
        initializeEvents();
        while(!simulationStopped && !eventSet.isEmpty()) {
           e = (Event) (eventSet.deleteMin( ));
           numberEvents++;
           currentTime = e.getWhen( );
           processEvent(e);
        }
    }    
}

Figure 9:  Client code to run the simulation of Fig. 8

    SingleIncoming sim = new SingleIncoming("One incoming", 30);
    sim.run(100);
    System.out.println("Time = " + sim.getTime() + " Number events:" + sim.getEvents());
    sim.run(300);
    System.out.println("Time = " + sim.getTime() + " Number events:" + sim.getEvents());

VI.     Using an Abstract Class to Simplify the Models

All event-driven simulations handle the time and the events in essentially the same way. The specifics of the problem (in our case a network router with 1 incoming line) only appear in the generation of initial events and in what is done to process an event. This structure suggests that we implement the simulation with an abstract class:

Figure 10:  An abstract class SimulationModel

      SimulationModel(String title) --> indicates the particular problem
      final void addEvent( Event e) --> keep track of event e
      final int getEvents( ) --> returns number of events that occurred
      final double getTime( ) --> returns current time
      final String getTitle( ) --> returns name of the problem
      abstract void initializeEvents( ) --> generate starting events
      abstract void processEvent(Event e) --> process an event
      final void run(double stoppingTime)
      final void setSimulationStopped( )i --> sets a flag indicated simulation is stopped --> run the simulation

The final methods are complete and cannot be changed by any class that extends (is-a) SimulationModel.

Notice that two of the methods, initializeEvents and processEvent, are abstract. As a result, SimulationModel is abstract and SimulationModel objects cannot be instantiated. We will need to develop a subclass of SimulationModel for each problem that we want to solve.
  Fig. 11 gives the outline of a subclass for SimulationModel. It only needs to have initializeEvents and processEvent. The IncomingOnlyModel also has a constructor, because it needs specific setup values for the interarrival time parameter and the number of lines. only needs a construc

Figure 11  An example of a subclass that might implement the incoming line problem

public class IncomingOnlyModel extends SimulationModel {
  public IncomingOnlyModel (double interarrival, int numberLines) { } // --> specific to problem
  public void initializeEvents( ) { } //--> generate problem-specific initial events
  public void processEvent(Event e) { } // --> process problem-specific events

Fig. 12 Shows the actual code for the abstract class SimulationModel. It is the same for all of the simulations. We will then write subclasses that extend SimulationModel for each specific simulation. The subclass only has to have initializeEvents and processEvent methods. In this way we have separated what is common to all simulations in the abstract class and the specifics in the subclass.

Figure 12:  An implementation of the SimulationModel class.

public abstract class SimulationModel {
    private double currentTime;
    private PriorityQueue eventSet;
    private int numberEvents;
    private boolean simulationStopped;
    private String simulationTitle;

    public SimulationModel(String title ) {
        currentTime = 0.0;
        eventSet = new BinaryHeap( );
        numberEvents = 0;
        simulationTitle = title;
    }

    public final void addEvent( Event e) { eventSet.insert(e); }
    public final int getEvents( ) { return numberEvents; }
    public final double getTime( ) { return currentTime; }
    public final String getTitle( ) { return simulationTitle; }

    public abstract void initializeEvents( ); 
    public abstract void processEvent(Event e); 

    public void initializeSimulation(double stoppingTime){
        addEvent(new Event(0, Event.STOP, stoppingTime));
        simulationStopped = false;
    }

    public final void setSimulationStopped(){
        simulationStopped = true;
    }

 
    final public void run(double stoppingTime) {
        initializeSimulation(stoppingTime); 
        initializeEvents();                
        while(!simulationStopped && !eventSet.isEmpty()) {
            Event e = (Event) (eventSet.deleteMin( ));
            System.out.println("...processing " + e);
            numberEvents++;
            currentTime = e.getWhen( );
            processEvent(e);                // [[ 5 ]]
        }
    }    

    public String toString( ) {
        return simulationTitle + ": Time = " + currentTime
                + ", Events = " + numberEvents;
    }

}

Fig. 13 gives an implementation of the IncomingOnlyModel that consists of a single incoming line. Notice that the constructor first calls the constructor of SimulationModel (by super(title)) and then does some model-specific initialization.

Figure 13:  An implementation of the IncomingOnlyModel class.

public class IncomingOnlyModel extends SimulationModel {
  private IncomingLine inLine;

  public IncomingOnlyModel(String title, double arrival) {
     super(title);  // do all of the general initialization first 
     inLine = new IncomingLine(1, 0, arrival);
  }

   public void initializeEvents( ) {  
       addEvent(inLine.getNextArrival());
   }

   public void processEvent(Event e) { 
       switch (e.getWhat()) {
          case Event.MSG_ARRIVAL:
             addEvent(inLine.getNextArrival());
             break;
         case Event.STOP:
             setSimulationStopped();
             break;
         default:
             System.err.println(e +  " {unrecognized event}");
             break;
       }
  }
}

The types of events that are needed for this simulation are:  MSG_ARRIVAL and MSG_SENT.      The unbuffered router does not allow messages to wait until an outgoing line becomes available.  Therefore, the MSG_SENT event will only be placed in the priority queue if an outgoing line is not busy.

An outgoing line will need to be represented and will be responsible for the following information:
 

• ID
• How long the line takes to send a message
• The number of messages lost
• The number of messages sent
• The time when the most recent message is done being sent
• The utilization (the amount of time that the outgoing line is busy/the total time elapsed)

Figure 14:  The OutgoingLine

public class OutgoingLine {

    private int ID;
    private int messagesLost;
    private int messagesSent;
    private double sendTime;  // time to send a message
    private double whenDone;

    public OutgoingLine(int theID, double serviceTime ) {
        ID = theID;
        messagesLost = 0;
        messagesSent = 0;
        sendTime = serviceTime;
        whenDone = 0.0;
    }

    public int getID( ) { return ID; }
    public int getMessagesLost( ) { return messagesLost; }
    public int getMessagesSent( ) { return messagesSent; }
    public double getSendTime( ) { return sendTime; }
    public double getUtilization( ) {
       return (messagesSent == 0)? 0.0: messagesSent*sendTime/whenDone;
    }

    public boolean isBusy(double time ) {
       return (whenDone <= time) ? false : true;
    }

    public Event sendMessage(double time) {
        if (time < whenDone) { // can't handle this message
            messagesLost++;
            return null;
        }
        messagesSent++;
        whenDone = time + sendTime;
        return new Event(ID, Event.MSG_SENT, whenDone);
    }

    public String toString( ) {
        return "Outgoing[" + ID + "]: line speed=" + sendTime +
               ", msgs sent=" + messagesSent +
               ", msgs lost=" + messagesLost +
               ", utilization=" + getUtilization();
    }
}

Fig. 15 goes through a trace of a simple example of the unbuffered simulation. The simulation is set to stop at time 25. The service time for the outgoing line is 10. The incoming line generates messages at times 8, 15 and 19, and 31.

Figure 15:  A trace of an unbuffered simulation.

I.    Generate the initial events and insert them in the priority queue:
 

e	currentTime	numberEvents	messagesLost	messagesSent
----	0.0	0	0	0

 

who	what	when	where
in 0	STOP	25	[[ 1 ]]
in 0	MSG_ARRIVAL	8	[[ 2 ]]

< get and delete the next event>

e	currentTime	numberEvents	messagesLost	messagesSent
MSG_ARRIVAL	8	1	0	0

<get and delete the next event>

e	currentTime	numberEvents	messagesLost	messagesSent
MSG_ARRIVAL	15	2	1	0

<get and delete the next event>

e	currentTime	numberEvents	messagesLost	messagesSent
MSG_SEND	18	3	1	1

who	what	when	where
in 0	STOP	25	[[ 1 ]]
in 0	MSG_ARRIVAL	19	[[ 5 ]]

<get and delete the next event>

e	currentTime	numberEvents	messagesLost	messagesSent
MSG_ARRIVAL	19	4	1	1

 

<Generate a new send message>
<Generate a new message on line 0>
 

who	what	when	where
in 0	STOP	25	[[ 1 ]]
out 0	MSG_SEND	29	[[ 5 ]]
in 0	MSG_ARRIVAL	31	[[ 5 ]]

<get and delete the next event>

e	currentTime	numberEvents	messagesLost	messagesSent
STOP	25	5	1	1

At this point the simulation breaks out of its loop. If we do a toString, we will have:

  UnbufferedNodeModel: Time = 25.0, Events = 5
  [Outgoing[0]: line speed=10.0, utilization=0.5263157894736842,
                 msgs sent=1, msgs lost=1]
  [Incoming[0]: generated 4 messages]
  Completed Messages: 1

Fig. 17 shows a complete implementation of the UnbufferedNodeModel. It has an IncomingLine and an OutgoingLine.

Figure 17:  The UnbufferedNodeModel

public class UnbufferedNodeModel extends SimulationModel {
    private IncomingLine inLine;
    private OutgoingLine outLine;
    private int completedMessages;
    private int lostMessages;

    public UnbufferedNodeModel (double arrival, double sendtime) {
        super("UnbufferedNodeModel");
        inLine = new IncomingLine(0, 0, arrival);
        outLine = new OutgoingLine(0, sendtime);
        completedMessages = 0;
        lostMessages = 0;
    }

    public void initializeEvents( ) {
        addEvent(inLine.getNextArrival());
    }

    public void processEvent(Event e) {
        switch (e.getWhat()) {
            case Event.MSG_ARRIVAL:
                if (!outLine.isBusy())
                   addEvent(outLine.sendMessage(e.getWhen()));
                else
                   lostMessages++;
                addEvent(inLine.getNextArrival());
                break;
            case Event.MSG_SENT:
                completedMessages++;
                break;
            case Event.STOP:
                setSimulationStopped();
                break;
            default:
                System.err.println(e + " {unrecognized event}");
                break;
        }
    }    

    public String toString( ) {
        return super.toString() + "\n[" + outLine + "]\n[" + inLine + "]"
                        + " Completed Messages:" + completedMessages
                        + " Lost Messages:" + lostMessages;

    }
}