Hallam July 2002

Discrete Modeling and Simulation in TOOMS:
A Combined Event/Process Approach
by Nasreddine Hallam
University Multimedia

Turbo Object-Oriented Modeling and Simulation (TOOMS) is an object-oriented general-purpose simulator for combined systems that allows multi-systems modeling and therefore, multi-models simulation. The modeler is given the ability to perform modular modeling or concurrent modeling. Indeed, s(he) can model a complex system into many sub-models, or in one-shot, models many systems into many concurrent models. This is the main characteristic of TOOMS. This work is to unfold the technical design of the discrete part of TOOMS.

1. INTRODUCTION

    The project TOOMS, Turbo Object-Oriented Modeling and Simulation, is an environment of simulation modeling supporting an alternative approach of modeling (Process and/or event and/or continuous), and allowing the execution of several models or sub-models that can eventually interact together to perform some logic. One can say that the way to view a complex system of real world in several sub-models, each one representing one part of the system, facilitates considerably the modeling task, and enhances the analysis task. In this sense, the user has to divide the system in question into several sub-models, and adequately models the interaction between them to preserve the initial logic of the system. Or it might be the case where the modeler would model many systems into many models that s(he) would execute them concurrently.
    From a programming standpoint, this is nothing but a multiprogramming technique (pseudo-parallelism) where several resident processes (models) in memory are (simultaneously with regard of the user) executed with respect of the simulation clock.
    This new simulation language has been designed and developed under the Object-Oriented approach rules. [1,2]
    Before going any further, a background and a theoretical foundation are introduced to ease the jargon used later in describing the author's work.
    Modeling a system is "abstracting" the real world. Simulating a model is executing it. It is in the simulation part that the details of executing the model (or models) are set and studied more thoroughly. It is very useful to give the modeler the ability to divide his system into many subsystems thus coming up with several models that are complementary to each other.
    The modeler would have to decide how these models are to be executed, i.e. in which order or what are the triggers/sequences. These are provided as synchronization tools, and mainly implemented by the Wait, Accum and Event predefined nodes to name a few. Refer to section 3.1
    In this paper I try to define a framework for modeling that will ultimately dictate the logic of the execution, i.e. the algorithms/heuristics for synchronization between many processes (models). However, the discussion is based on discrete modeling and simulation, since a continuous modeling and simulation is, in its own right, another article.
    It is clear that systems models can be classified in three broad categories. Discrete, Continuous, and Combined (mixed) models. Usually the time is the only independent variable where the rest are dependent on time. It is worth pointing out that the simulation time is a non-negative variable that is incremented with discrete jumps, in order to advance the clock. Human reflex and perception are inherently discrete, this is perhaps the reason why we are unconscious during long (relative) period of times when the magnitude is of the order of fractions of nanoseconds, so to say, and consequently, we can never be on time!
    In a discrete modeling approach, objects are called entities. These entities possess attributes and are engaged into activities that are triggered by the start-activity event and end-activity event. An event is something that happens at a point in time. A change in a condition deemed significant in the context under study might be seen as an event at which the system will transit into another state. This unscheduled change in state is a result of a state event. Or, sometimes, we can schedule an event to occur at a very known point in time, at which the system also changes to another state. This is known as temporal event or time event.
    As a result of an event occurrence, the entities will have the values of their attributes changed thus "simulating" the transition of the system from one state to another one.
    It is worth pointing out that the values of the attributes of a variable may rigorously change at very specific point of time. In such case, we are dealing with a discrete variable. Otherwise, i.e. changes occur (uniformly) along periods (interval) of time, we are dealing with a continuous variable.
    The discrete model of a system can be simply developed by coding the "logics" that will immediately follow the occurrences of events. This incurs the modeler to think about all events that might happen. Simulation would then be the execution of these kinds of "logics" one by one. This is known as event modeling. This is the main approach in simulating a discrete model. Other discrete approaches, namely activity modeling and process modeling, can be chosen instead.
    In the discrete modeling by the activity approach, entities basically undertake activities. The modeler would have to describe every activity by stating the triggers or transitions (start/end) of an activity and the function(s) that would be accomplished by entities while under the activity. This view is normally orthogonal to the event-oriented approach.
    As for the process approach, events that occur in the same pattern are clustered together to form a process. Usually, it is depicted by graphical nodes and branches describing a network through which entities flow. The logic associated to each pattern is also defined by a statement/instruction. In other words, the routing of entities through nodes (stations) and branches (activities, links) is simply modeled by a command-like program.
    More specialized texts, such as in [3,4], can constitute a good reference for the basics of computer modeling and simulation.

    Turbo Object-Oriented Modeling and Simulation, TOOMS for short [1,2], is a simulation and modeling environment that has been devised for an academic research project. The amazingly interesting inherent features of object oriented approach, such as object abstraction and instantiation in one hand, and inheritance and polymorphism on the other hand, were of a great deal in laying down a very flexible modeling environment. By flexibility, it is meant that the modeling task of the user is to draw several models that relate to several independent systems, or map a very complex system into several "sub-models" which can be executed concurrently and/or synchronously according to the original logic of the system.
    The main attractive feature of TOOMS is that each model or sub-model is an instance object manipulated by the simulator, whereas the interactions between sub-models or models are nothing but message passing between the corresponding objects. Besides, TOOMS is event-driven modeling and simulation language, handles continuous and discrete systems (known as Combined system), and is mainly inspired from SLAM II. [5,6]
    TOOMS adopts the event modeling and process modeling for its discrete part. The event approach is chosen because of its slightly higher modeling flexibility, whereas the process approach is regarded as a complementary modeling approach.
    The process modeling approach in TOOMS is a set of graphical nodes that carry a specific procedural meaning. To each graphical node, corresponds a predefined statement that is much like a command. Therefore, the modeler can either draw a network of nodes that represent the system, or write a sequence of commands (program). See fig.1 [1,2]
    Therefore, executing (simulating) the model is simply interpreting every command. This naturally suggests that the graphical model (network of nodes) must ultimately be translated into a textual model (sequence of commands, a program). On the other hand, the modeler can chose to code very detailed routines (usually a function in C++) and associate it to the "Event" command and schedule the event to happen at a specific point of time.

In this section, the environment for the discrete modeling and simulation part is introduced. It provides a flexible support for building and executing models. The flexibility is seen in the capability of viewing systems from process and/or events and/or state variable perspectives [1,2].
    The user can model his system by drawing a network referring the process part (novice user), and/or by coding potential events in the high level language (C/C++) (expert user).
    For simple systems in which entities flow through a network of all kind of stations and undergo or provide some elementary and standard services, the modeling task is well handled using the process modeling approach. In this approach, a set of restricted number of network branches and nodes can respectively simulate the flow and the services undertaken by entities. Note also, that the modeler might chose to write a set of process commands.
    However, for complex systems where the nature of service provided to ( or by) an entity cannot be supported by any of the network node, a user-event procedure has to be explicitly coded, where the logic of that procedure is in fact the new service that is to be incorporated and provided. See section 3.3 for more detailed discussion.
    Therefore, the discrete execution model is two folds. A process model consisting of linked lists of polymorphic objects representing the different nodes, and of an event model, mainly described by a calendar of pre-scheduled events that ultimately would trigger procedures to carry out their intended functions at very specific points of time. These two discrete modeling approaches can cooperate together according to the logic dictated by the modeler.
    The cooperation is facilitated by some dedicated nodes and predefined procedures. These are are more like interfacing tools, and monitored by the Kernel object of TOOMS [1].

It is depicted by a graphical network whose the elements are entities, nodes, branches, blocks, and queues. See Figure 1 for an example.
The meta-structure of the network representation (an hierarchical structure.) is depicted in the class diagram given in Fig 2. The notation and semantics of Fig. 2 are those originally proposed in the Object Modeling Technique [7] (OMT) methodology and recently being used in the Unified Modeling language (UML) [8].

a) Entity: It is an object of a discrete system (people, car, machine,...) that has attributes which will be assigned values to denote an activity. An entity flows through the network. It seizes resources, passes gates, undergoes a service, and exits the system.

b) Nodes and Branches: Their combination constitutes the network structure. Nodes are elements of network in which an entity is affected by a special treatment provided by a branch (also called activity).

c) Blocks: two kinds of blocks
     Resource Block: During an activity, an entity can require a resource block in order to complete a treatment. Each resource has a name, a capacity, a storage tile, and a number of available resource units.
     Gate Block: It can halt the flow of entities denoting a specific logic of the system (i.e. no entity can flow until the server becomes idle). Each gate has a name, a status (opened/closed), and files in which entities wait in for its opening.
    class Node : public LinkableElement2              class Branch: public LinkableElement
    { Id, Name,                                               { Id, Name, duration, Prob, Trigger, Chosen;
    TopLeftCorner, BottomRightCorner,               Distrib_Fction;
    N-BranchesOut,,N-BranchesIn                       Node * Next …
    Element *Next;                                          Node * Last;
    Element *Last;                                          Branch * ParallelBranches;
    Public:                                                      public:
    Draw(); Delete();                                       Draw(); Delete();
    Trans_Satetment();…                                 Trans_Satetment();Evaluate_Trigger();
    };                                                            LinkParallelBranches()
                                                                   Compute_ Distribution_Function();
                                                                    };

d) Queues: They are implemented as dynamic lists and the strategies for storage/search/insertion/deletion can be FIFO (default), LIFO, LVF, or HVF. The modeler is given the flexibility to change the manipulation strategy for any queue interactively at execution time.

class WaitingQueue
    { Id, Name
    Priority // FIFO by default
    Maximun, Average, StdDeviation;
    Public:
    WaitingQueue();
    Retrieve( ); InsertEntity (); FreeEntity();
    ChangePriority();
    //some statistical routines.
    };

There are major design issues to be taken into account. One concerns the sequencing of the nodes, the second deals with the parallel probabilistic activities, whereas the other one deals with the choice of the standard variant formula.

The argument is to have a sequence of network elements as general as possible (to handle the versatility of the nodes) and yet flexible. This will propel the following inherently legitimate constraints.

a) Allow a node to have either another node as a successor or one or many branches as successors (same thing for predecessor)

c) Some nodes/branches must know beforehand, the type of their predecessors in order to do their jobs.

The nodes and branches have lot of pictorial and semantic similarities with those defined and used in SLAM II[5,6], SIMAN [9] and perhaps GPSS [10].
Given the above requirements/constraints, the most efficient design structure of the network would be a bi-directional and bilateral linked list. The bilateral part of the linked list concerns exclusively activities. It is a linked list of activities that are either parallel (probabilistic) and/or exclusive to each other (conditional).

Referring to the constraint (a) above-mentioned, there might be a case where there are parallel activities emanating from a single node. See fig.3 below.
If the activities are conditionally mutually excluded, the choice for one activity is as straightforward as the evaluation of a conditional expression. However, if the activities are probabilistic, then the selection of one activity must obey to the randomness and likelihood associated to all the involved activities. The following is a design strategy that allows the achievement of this purpose.
For the sake of efficiency, the list of parallel activities is ordered in an descending order of the probabilities. So the least probable one is at the tail of the list. To each activity, a distribution function (Distrib_Fction) is associated (Fig 3.).

Now to choose amid the activities, a random real number x, (between 0 and 1) is generated, and using the method of Inverse Transform, x will be projected to the graph (step-curve) of the distribution function of the activities in order to select one and only one activity.

The inherent idea behind simulation is to collect data and statistics on some network elements. Queues (passive and active) and blocks (resources and gates) are the two important network element types that need to perform some statistics. This is very useful in decision making.
Observe that the most important statistical observations are the mean and standard deviation. Below, the formula for the mean and two alternative formulae for the standard deviation are given. While the mean formula is straightforward, the question lies in the choice of the standard deviation formula.

The formula of the standard deviation given in (3) is an expedient choice since it is a function of the average, and therefore needs not an explicit collection of observations x_i as formula in (2) would have required

3.3 The Event Modeling and Simulation Part

     The modeler is equipped with some built-in directives for event routine coding, and event scheduling. There is also the possibility to interfacing the process part with the event part.
    Basically, the modeler has to code procedures/functions that simulate the changes that result from the occurrences of events. In each procedure, the modeler has to schedule the event by binding that procedure to an Event Identifier, stating the occurrence time or the trigger.
    Using the predefined function signature Schedule (K_Event, CountDown, Buffer), the modeler can sequence his events according to their occurrence time. K_Event is the event key or Id, CountDown is the difference between the occurrence time and the actual current execution time (|Tnow-OccTime|), and Buffer is an array that contains the attributes associated to the event in question and deemed of a certain importance to its execution.
    For instance, Consider a case where we want to model the event Arrival ( ), whose occurrence time is the current time plus a sample of an exponential distribution of mean 5. The first attribute of this entity is set to 5 denoting the entity Id for example.
    The modeler would have to model the above by writing a procedure called Arrival () in which (s)he has to insert the predefined procedure Schedule(- , - , -) with the appropriate arguments as shown below.

void Arrival ( )
    { Attribute[1] = 5;
         float Timing = Expon(5);
         Schedule (1, Timing, Attribute);
    }

The Kernel of TOOMS automatically generates a predefined procedure called Event(int Key) in which Arrival() is inserted as the "first switch" as suggested by the first parameter in the procedure Schedule. Therefore Kernel will call Event(1) whenever it intends to call Arrival(). More precisely, the Kernel would call Event (1) exactly at the time corresponding to TNow+Expon(5), where TNow is the is the current simulation time.

void Event(int ID)
    { switch(ID) {
                case 1: Arrival (); break;
                  case 2: Start_Service(); break;
                  case 3: Terminate_Service (); break;
    }

This means that in Start_Service(), the modeler has set the first parameter of the predefined function Schedule to 2, and the first parameter of Terminate-Service() to 3.

3.3.1 Calendar

It is circular and bi-directional linked list of events ordered on their occurrence time. The events of such calendar are preferably called event notices. See fig. 5 below.

It is important to note that entities entering nodes induce the creation of what we call arrival node events. Each node has a specific procedure dictating the changes (actions) to be taken whenever an entity hits the node in question. These arrival node events have the EventType attribute set with the name of the node.
Inversely, events that are explicitly scheduled by the modeler via the directive (predefined procedure) Schedule are called user event, and their corresponding EventType attributes are set with event key. See fig 4.

An event notice is as follow:
    class Event_Notice
    { Event_Notice *Last;
       float Time_Event
       EventType event_Type;
        Union { Node * Arrival_Node;
       Int Event_Key ;}
       Discrete_Object * discret_Object;
       Event_Notice *Last;
    public: Attach_To_Last( Event_Notice *Last);
               Set_Time_Event (int time); Set_Type ( EventType)….
               Insert_Event_Notice(float TimeEvent)
               Delete_Event_Notice ();
               Dichotomous_Search (float); …
    };

The list is constantly kept sorted in an ascending order based on TimeEvent. Whenever an event notice is about to be inserted, the insertion code must fulfill the formal specification of the sorted calendar list. i.e.:

Both pre-condition and post-condition must obey the following formal specification
" i,j, i<j Û Calendar->Event_Notice_i.Time_Event £

It follows that for insertions, the binary (dichotomous) search is used for efficiency.

Therefore, the head of the calendar list contains the event that is meant to occur the first (the most recent). The list is maintained ordered (LVF) all the time. If it happened that some event notices are to occur at the same time, then the FIFO strategy is used to linear sequencing these happening-at-the-same-time events in the calendar.

To give an abstract form to the simulation time, a function clock is introduced that maps all kinds of events to real positive numbers, i.e. their occurrence time.

clock : E Â⁺
Where E is the set of all possible events and Â⁺ is the set of positive real numbers.

The function is not injective, since two or more events might happen at the same time, nor surjective, since it may be the case where at given point of time no event happens, the system might have been in a stationary state.
This function is modeled by the class Clock.

Class Clock
    { float TNow, TLast, TEnd;
    public: SetTNow(float ); GetTNow( );
    SetTLast(float ); GetTLast( );
    SetTEnd(float ); GetTEnd( );

TLast is the time occurrence of the last event.
TNow is the time occurrence of the current event.
TEnd is the time of the end of the simulation if ever the modeler has set it. By default is indefinite.

The Kernel of TOOMS calls the Scanner object that scans all the process models, investigates every node, and creates event notices whose EventType attribute is "Arrival Node" and inserts them into the calendar. Next, the Kernel investigates all the Schedule(-,-,key) directives to generate event notices whose EventType attribute is "User Event" and insert them into the calendar too. This order of insertion is not random, but heuristically justified in the sense that arrival node events are usually more closer (in time space) to each other, whereas user events tend to be scattered throughout time. This will minimize the time of insertion and therefore decreases the simulation execution time.

Remember from the very previous paragraph that all events of different types of all the models have already been carefully inserted in the calendar in a very appropriate way that guarantees the synchronization

The discrete modeling and simulation part in TOOMS encompasses two approaches, namely process and event approaches.
    The process approach provides the modeler with a small concise number of pictorial nodes to sketch out a rough model.
    In the event modeling approach based on the calendar strategy, the modeler has to explicitly code the logic of the non-standard services, i.e. not provided by the process approach. In such case, process modeling can be regarded as a feasibility study before a go-ahead can be granted. Or perhaps it can be seen as the plain or straightforward part of the system that is easily modeled and later, finer details can complement the model using the event-oriented part that involves event routine coding and scheduling.
    The design of this module (discrete part of TOOMS) was successfully achieved thanks to the object-oriented design. Every discrete object is an aggregate of smaller objects (entities, waiting queues, blocks, nodes, activities, …), which in their turn are organized through a quite natural hierarchy that provides inheritance and polymorphism (fig1). This can just ensure a cleaner design which, as software engineers like to coin, very opened to extensions.
    The whole discrete model is an object. This turns out that we can instanciate as many discrete objects as we need. Thus, the modeler can either divide his systems into many sub-models, or simulate many systems in one shot. The latter would be of real usefulness if we (physically) distribute the execution (simulation) of the models (objects). This is quite naturally an advocate to a distributed simulation.

[1]: Hallam, N and Khodja, R. " Object-Oriented Design of a Mixed simulator", In: IEEE SMC’98
International Conference on Systems, Man, and Cybernetics,. Intelligent Systems For Human In A
Cyberworld, October 11-14, 1998, San Diego, California, USA, pp. 3697-3702

[2] Hallam, N and Benyamina, D. " An Object Oriented Design of The Discrete Part of A General Purpose Modeling and Simulating Environment ", To appear in: IEEE SMC’2002 International Conference on Systems, Man, and Cybernetics,. October 6-9, Tunisia.

[3] Discrete-event System Theory: An Introduction, by Tornambe A., World Scientific, 1995.

[4] Theory of Modeling and Simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems, by B. Zeigler, H. Praehofer, T-G. Kim, Academic Press, 2000.

[5] Pritsker, A., B. "Introduction to Simulation and SLAM II", Halsted Press, 1986, Edition 3. ISBN 0‑470‑20292‑0.

[6] Pritsker, A., B., Introduction to Simulation & SLAM II, John Wiley & Sons, Inc., New York, 1995

[7] Rumbaugh, J., Blaha, M., Premerlani, W., Eddy, F. and Lorensen, W., Object-Oriented Modeling and Design, Prentice Hall, 1991.

[8] Booch, G., Rumbaugh, J. and Jacobson, I., "The Unified Modeling Language User Guide", Addison-Wesley, 1998.

[9] Pegden, C., D.,Computer Simulation/Verification: Introduction to Simulation Using SIMAN, by, WCB/McGraw-Hill, 1995.

[10] Karian, Z., and Dudewicz, E., Modern Statistical Systems and GPSS Simulation, by CRC Press, 1998.

2 Those important attributes inherited from super classes are also shown in these two classes.

Nasreddine Hallam is currently teaching computer science subjects at Multimedia University, Malaysia. His main research interests and paper contributions are in Fuzzy Inference Schemes and Computer Modeling and Simulation.