Descrete Event Simulation Library

   
1 Introduction
   1.1 Portability
2 Package Overview
   2.1 List of files
   2.2 Dependency of #include files
   2.3 Hierarchy of Classes
   2.4 Data Types
   2.5 Structure of DESL
   2.6 Output streams
3 Creating DESL elements
   3.1 CBase class
   3.2 CClock and CClockSync classes
   3.3 Class MultiPort<int16s PORTS> classes
   3.4 Derivation of Network Elements
   3.5 DESL Network Element Template
   3.6 Example of Link Object
Q & A

1 Introduction

[ Top ]
Discrete Event Simulation Library (DESL) is a C++ library developed under Microsoft Visual C++.NET 2003. It contains classes and routines that facilitate creating simulation models and performing an analysis.

1.1 Portability

[ Top ]
DESL uses some Microsoft – specific extensions, for example _int64 – a 64-bit integer. Should the DESL be ported to another platform, some code modifications may be necessary.

2 Package Overview

[ Top ]
DESL is a collection of classes that allow creation of a Pending Event Set (PES) engine as well as creation of network elements (objects) that are able to generate or process various simulated events. To explain the design concepts of the DESL package, the examples given below are based on a simulation model of Interleaved Polling with Adaptive Cycle Time (IPACT) algorithm designed for Ethernet Passive Optical Networks.

2.1 List of files

[ Top ]
_types.h Contains general type definitions and macros.
_util.h Generic error handler for heap memory allocations.
_list.h Data structure for double-linked list.
_stack.h Data structure for stack.
MersenneTwister.h Mersenne Twister random number generator is designed by Makoto Matsumoto and Takuji Nishimura. This file is Mersenne Twister RNG implemented as C++ class by Rick Wagner.
_rand_MT.h Contains routines for generating random values. Most of these are just wrapper functions for Mersenne Twister class.
avltree.h Contains class declarations for AVL tree structure. AVL tree structure is discovered by Adelson-Velsky and Landis (G.M. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information," Soviet Math. Dokl., 3:1259--1262, 1962). AVL tree is used here to store sub-streams sorted in order of burst arrival time and to add and retrieve elements in O(logN) time.
desl.h Classes used to create simulation environment:
class Cbase - base class for all network elements;
class Cevent - simulation event;
class CEventQueue - pending event set.
clock.h Contains classes that know how to maintain local clock (timeoffset and drift).
mport.h Contains class that maintains one or more interfaces to other network elements.
stats.h Contains classes that collect sample values and calculate simple statistics or build histograms.
trf_gen_v3.h Refer to description of self-similar traffic generator v.3.
broadcom_pdf.h Array representing distribution function of packet sizes. This array can be used with Traffic Generator v3. Refer to description of self-similar traffic generator v.3.
sl_main.cpp Main function.

The following files contain classes or routines specific for IPACT simulation model. They may or may not apply to different simulation models.

link.h DESL network elements representing various links: LossLessLink, LossyLink, BiDirLink, and JitterLink.
pktsrc.h DESL network element representing packet source.
olt.h Optical Line Terminal
onu.h Optical Network Unit
sim_output.h Routines for output to screen and file.
sim_config.h Configuration parameters, non-dependant on specific test scenarios.
conf_001.h Test-specific configuration parameters.
test_001.h Test scenario. This file should define 3 functions specific for each test: InitializeEPON(), DestroyEPON(), and Execute(). The main simulation loop is located in the Execute() function.

Notes:
  1. File desl.zip contains an archive of all files.
  2. The above code was compiled under MSVC++.NET 2005. An executable for Windows is located here.
  3. Microsoft made VC++ 2005 (Express edition) available free of charge. You may download it at http://msdn.microsoft.com/vstudio/express/visualc/.
  4. There were some breaking changes in VC++ 2005. If you have downloaded previous version of DESL (for MS VC++ 2003), please note that there were few minor changes to this code to make it 2005-compatible.

2.2 Dependency of #include files

[ Top ]
To create a compact project with a reduced number of files, class declarations and definitions of the class members are grouped together in a single header file. The entire project contains a single file with extension "cpp" and a multitude of header files. The dependency of the header files is shown in figure 1.

Figure 1: Dependency of included header files for the IPACT project.
(Click figure to enlarge.)

In Figure 1, the files created to model a specific EPON system are shown with yellow background. The files with clear background are generic and are intended to be used in any simulation model.

2.3 Hierarchy of Classes

[ Top ]
Figure 2 illustrates a hierarchy of classes. The boxes with a darker background represent classes created for the specific EPON system, while the boxes with a lighter background represent generic classes intended to be used in any simulation model.

Figure 2: Hierarchy of classes.
(Click figure to enlarge.)

2.4 Data Types

[ Top ]
Following are the data types used in DESL; in order to use the DESL efficiently, it is important to be familiar with them. These data types are defined in file _types.h.
int##s
int##u
It is an integer variable with sign specified by s or u and size specified by ##. (e.g. int16u is a 16-bit unsigned integer and int32s is a 32-bit signed integer.)
BOOLAlias of type bool.
BYTEAn 8-bit unsigned integer.
CHARAlias of type char.
WORDAn unsigned integer.
FLOATAlias of type float.
DOUBLEAlias of type double.
In addition, some frequently used data types are defined in file desl.h within the DESL namespace. These types are shown below:
DESL::time_tEvent time. It is a 64-bit integer.
DESL::base_tBase class for all DESL classes.
DESL::data_tData associated with each event.
DESL::obid_tObject ID.
DESL::evnt_tCEvent class.

2.5 Structure of DESL

[ Top ]
Structure of DESL is as shown in the Figure 3.

Figure 3: Structure of DESL.
A central object of DESL package is the Event object. Each object of class CEvent has an activation time, and pointers to event′s Producer and Consumer (objects of type DESL::base_t). In addition, each event has one or more event-specific members.
All future events are stored in a Pending Event Set (PES) queue. The PES stores all the events in order of their activation times. When the head event (event with the smallest activation time) is removed from the PES, the system clock is advanced to the activation time of this event. When an event reaches the top of the queue it is passed to Monitor function and then to the Dispatcher which will dispatch the event to event′s Consumer, where this event will be processed. In this structure, any event in entire simulation will always go through Monitor function. This provides a good opportunity to look into each event and collect desired data and statistics.
As a result of Consumer′s processing the event, more future events may be generated by the Consumer; these events will be stored in PES in order of their activation times.

2.6 Output Streams

[ Top ]
While running the simulation, any information messages and results output can be directed to the screen and/or to a file. Following are the different types of output streams.
MSG_CONFAll the Configuration parameters of the simulation test scenario are directed to this stream.
MSG_WARNAll the warnings and errors related to operation of system under test are directed to this stream. For example, if a grant is too small, an ONU would output a corresponding message to MSG_WARN stream.
MSG_INFOAll the uncritical information such as the state of the simulation is directed to this output stream. This information would typically include state or progress of running tests, etc.
MSG_RSLTAll the simulation results are directed to this output stream.

3 Creating DESL Elements

[ Top ]
All DESL elements that process events must be ultimately derived from a base class DESL::CBase. If in addition to sinking events, a network element must generate its own events, such an element should be derived from either class CClock or CClockSync.

3.1 Class CBase

[ Top ]
DESL::CBase is an abstract class - it has three pure virtual functions that should be implemented by each derived class that is to be instantiated. The three pure virtual functions are
virtual void Free( void )
virtual void Reset( void )
virtual void ProcessEvent( DESL::evnt_t* pEvent ) 
Explanations of these functions are given later.

3.2 Classes CClock and CClockSync

[ Top ]
If a network element needs a capability to generate its own events, it should be derived from either class CClock or CClockSync. These two classes add a notion of local time, and can internally translate local times into global (device independent) times. All classes derived from CClock and CClockSync can create events with a specific activation times.
Note that both CClock and CClockSync classes still remain abstract as they don′t implement any of the pure virtual functions declared in class DESL::CBase. Classes derived from CClock and CClockSync must define these functions.
The instances of classes derived from CClock have an ability to specify local clock with a time offset and a time drift relative to the global clock. The timeOffset member specified the absolute difference between the two clocks at the beginning of system time. The clock drift, measured in parts-per-million (ppm) is an additional difference that is gained as the clocks advance. In general, localTime=GlobalTime * clockDrift + timeOffset. The CClockSync class is similar to CClock, but it assumes the local clock being synchronous with the global clock, i.e., clock drift being zero.

3.3 Class MultiPort <int16s PORTS>

[ Top ]
In DESL simulation environment, network elements interact with each other by passing events from one element (the Producer) to another element (the Consumer). A port is represented by a pointer to a Consumer element. (Recall, that events are not passed directly from the Producer to the Consumer, but rather are stored in the Pending Events Set structure and retrieved in order of their activation times.) For example, if we are to simulate transmission of a packet by an ONU (as a single event) , an object representing ONU would issue an event with the following parameters:
Event type=EV_PCKT_ARRIVAL
Event Producer=<address of ONU>
Event Consumer=<address of PON link>.
To simulate an arrival of a GATE message to the ONU, the PON link would issue an event with
Event type=EV_GATE_ARRIVAL
Event Producer=<address of PON link>
Event Consumer=<address of ONU>.


In order to connect to other network elements (i.e., in order to form a network), each DESL network element should inherit one or more ports (interfaces) from a template class MultiPort <PORTS>. To establish a connection, a source element should invoke function void SetPort( DESL::base_t* dst_node, int16u src_port=0 ) which takes address of the desination element as an argument. A connection is always unidirectional. To establish bi-directional connections, the SetPort(...) should be called twice:
//A and B are some network elements
//set bi-directional connection between A and B

A.SetPort( &B );
B.SetPort( &A );

Class MultiPort <PORTS> is a template class, that takes number of ports (interfaces) as a template parameter. An element. which represents a traffic source would typically have only one interface - an interface to an element that consumes packets from the source. A bi-directional link would have 2 interfaces - one on each end of the link. A switch would have many interfaces. In simulation model for IPACT, for simplification, PON topology is represented by a collection of point-to-point bi-directional links of various lengths. Thus, each ONU would have only one interface, but the OLT would have an interface per each ONU. The connections are established as follows:
    // pOLT             - pointer to OLT element 
    //                    ('NUM_LLID' interfaces)
    //
    // pONU[ NUM_LLID ] - array of pointers to ONUs
    //                    (1 interface)
    //
    // pSRC[ NUM_LLID ] - array of pointers to traffic sources
    //                    (1 interface)
    //
    // pLNK[ NUM_LLID ] - array of pointers to bi-directional links
    //                    (2 interfaces)


    for( int16s n=0; n < NUM_LLID; n++ )
    {
        // downstream connection for GATE messages
        pOLT   ->SetPort( pLNK[n], n );    // connect OLT's port to a link 
        pLNK[n]->SetPort( pONU[n], 0 );    // connect link to an ONU 

        // upstream connection for data and REPORT messages
        pSRC[n]->SetPort( pONU[n]    );    // connect packet source to ONU 
        pONU[n]->SetPort( pLNK[n]    );    // connect ONU to a link  
        pLNK[n]->SetPort( pOLT,    1 );    // connect link to the OLT  
    }

This setup is illustrated in Figure 4.

Figure 4: Connections between elements for the IPACT project.
(Click figure to enlarge.)

3.4 Derivation of Network Elements

[ Top ]
To facilitate creation of network elements, a common base class SimBase is created for the given project. The SimBase is a parametrized class that takes number of ports as a parameters and inherits from both CClockSync and MultiPort<>. SimBase is an abstract class.

Figure 5: Derivation of various network elements with different number of ports.
(Click figure to enlarge.)
Figure 5 shows the class hierarchy for network elements with different number of ports. For example, objects like LossLessLink (which is a unidirectional link) and PacketSource have only one port – they pass events only to one Consumer. In this model, the class ONU is also a single-port element since this model was concerned with only upstream flow of packets, and so ONU′s Consumer was always the LossLessLink.
Unlike a unidirectional link, the element BiDirLink (bi-directional link) has two ports and can pass events in two directions, i.e., it has two different Consumers.
Intuitively, the OLT should be a single-port device, since it passes all the events to a single PON link those later splits into multiple branches. However, this approach would generate a large number of useless events – every GATE will be passed to every ONU, but will be accepted only by a single ONU. To avoid unnecessary processor work we model PON topology by using N bi-directional links. In this case, the OLT becomes a multi-port device since it should be able to connect to multiple links. Such modeling is simply an optimization step and does not detriment the validity of our model. The single-copy broadcast frames are simulated by simply issuing multiple EV_PCKT_ARRIVAL or EV_GATE_ARRIVAL events that all activate at the same time.

3.5 DESL Network Element Template

[ Top ]
As mentioned before, class SimBase has three pure virtual functions: Reset, Free and ProcessEvent. Any new system or network element should implement these three functions. Below we provide a template to create a new object.
class ClassName : public SimBase<number_of_ports> //number_of_ports >= 1
{
private:
    // Declare private members of the class here.

public:

    // Constructor
    ClassName(DESL::obid_t id=0): SimBase<number_of_ports>(id)  
    {
        // Put Constructor implementation here
    } 

    // Declare other public members of the class here.


    ////////////////////////////////////////////////////////////////////
    // Implement all pure virtual functions of class DESL::CBase.
    ////////////////////////////////////////////////////////////////////
    
    virtual void Free( void )
    { 
        // Free is used when memory associated with the 
        // private members of the class is to be deallocated.

        // ... implementation here 
    }

    virtual void Reset( void )
    { 
        // Reset is used to reset the values of all private members 
        //  of the class. It will not deallocate any memory.

        // ... implementation here 
    }
    
    virtual void ProcessEvent( DESL::evnt_t* pEvent ) 
    {
         // ProcessEvent is used to receive any events that are
         // sent to the object by the Dispatcher. 
         // Inside the function object takes appropriate actions 
         // based on the event type.

         // ... implementation here 
    }    
};

3.6 Examples of Link Elements

[ Top ]
Below is the example code of Link element. This class implements a simple unidirectional lossless link. LossLessLink class is derived from SimBase with number_of_ports equal to 1 (default value). It has one private member Delay, which is the propagation delay of the link. The value of Delay member is set in the constructor. This class also implements virtual functions Reset, Free, and ProcessEvent. Functions Reset and Free do nothing, while function ProcessEvent registers the same event to the PES, but with interval equal to its propagation delay and it sets the consumer of this event. This will make the event-dispatcher dispatch this event to its consumer after the link propagation delay.
class LossLessLink : public SimBase<>
{
private:
    DESL::time_t Delay; 

public:

    LossLessLink(DESL::time_t delay, DESL::obid_t id=0): SimBase<>( id )  
    {
        Delay=delay;
    } 

    ////////////////////////////////////////////////////////////////////
    virtual void  Free( void )      {}
    virtual void  Reset( void )     {}
    
    ////////////////////////////////////////////////////////////////////
    virtual void ProcessEvent( DESL::evnt_t* pEvent ) 
    {
        pEvent->Consumer=OutPort[0];        // redirect the event  
        RegisterEvent( pEvent, Delay );       // register with 'Delay'
    } 
}; 


In the second example code below we show another link element – a bi-directional link. It demonstrates an object with multiple output ports. BiDirLink class has two output ports, one for each direction. ProcessEvent function simply takes the event from one port and sends it to the "opposite" port with delay equal to the link′s propagation delay.
class BiDirLink : public SimBase< 2 >
{
private:
    DESL::time_t Delay; 

public:

    BiDirLink(DESL::time_t delay, DESL::obid_t id=0) : SimBase<2>( id )  
    {
        Delay=delay;
    } 

    ////////////////////////////////////////////////////////////////////
    virtual void  Free( void )      {}
    virtual void  Reset( void )     {}
    
    ////////////////////////////////////////////////////////////////////
    virtual void ProcessEvent( DESL::evnt_t* pEvent ) 
    {
        // redirect the event 
        pEvent->Consumer=OutPort[ pEvent->Producer == OutPort[0]? 1: 0 ];
        RegisterEvent( pEvent, Delay );      // register with 'Delay'
    }    
};

[ Top ]