Modelling using Classic DEVS 

General Information

  • The due date is Sunday 14 December, before 23:55.
  • Submissions must be done via BlackBoard. Beware that BlackBoard's clock may differ slightly from yours. All results must be uploaded to BlackBoard and accessible from links in the main (index.html) file.
  • The assignment must be made in groups of maximum 2 people. It is understood that all partners will understand the complete assignment (and will be able to answer questions about it). Clearly identify who did what.
  • Grading will be done based on correctness and completeness of the solution. Do not forget to document your requirements, assumptions, design, implementation and modelling and simulation results in detail!
  • To get feedback about the assignment workload, provide the number of hours you spent on this assignment.

Goals

This assignment will make you familiar with modelling, simulation, and performance analysis in DEVS.

The problem

The purpose of this assignment is to model the behaviour of the polling component from the chat client. The client will generate messages, which are transmitted to the server, which replies to them. To allow for optimization, you have to model the network in between the client and server. Furthermore, another component is required to generate additional load on the network.

This model will be used to analyze the influence of model parameters on the behaviour. You will find the optimal value to set for timeout parameter, which is as strict as possible (doesn't wait excessively long), but doesn't result in too frequent false positives (doesn't time out the connection if the server was still alive). Depending on the load of the network in between, and possibly of the server too, the response time of such messages can vary significantly. It is thus required to show, for a variety of network loads, what the influence on the response time is and what would be a good configuration parameter in these cases.

The model will consist of a Coupled DEVS model named Root. This model is made up of of a concatenation of one ChatClient Atomic DEVS, followed by a Network Atomic DEVS, and terminated by a ChatServer Atomic DEVS. There is a connection from the client to the server, and a connection back. This setup is shown in Figure 1.

overview.svg
Figure 1: Overview of the model

The following is a detailed description of the three different Atomic DEVS as well as of the Message and Packet entities sent (as events) between the Atomic DEVS building blocks.

Message

Messages sent by the ChatClient are instances of the Message class and are generated by the ChatClient Atomic DEVS, passed through the Network Atomic DEVS model, ending up at the ChatServer Atomic DEVS model. Afterwards, the message is sent back to the ChatClient through a different Network instance.

The Message class is a container for all the relevant information pertaining to the exchanged message, including the time at which it is sent and the size of the message.

Packet

Packets are a more generic form of messages, only defined by their size (and thus the time required to process them).

They represent the objects generated by the LoadGenerator Atomic DEVS models. Note that you cannot use inheritance in the AToMPM Classic DEVS formalism.

ChatClient

The ChatClient will behave just like the polling component from the previous exercise: it will send a poll Message after a certain period of time, after which it waits for a response. For the parameter that we wish to optimize, there is no need to time out after a certain period in time.

As soon as a reply is received, the model will wait for a certain amount of time, after which a new poll message is sent again.

For statistics gathering at the end, it is required that the ChatClient performs some processing of the responses, so that this value can be accessed at the end of simulation.

Network

The Network Atomic DEVS model will be a significantly simplified version of a network. It simply exists to introduce a certain delay for messages to be processed by the ChatServer.

To make the network configurable, the Network model should take a parameter signifying its bandwidth (in bits per second). After the message is processed, the message is output at the output port and thus forwarded to the ChatServer.

Because packets might arrive before the previous one is processed, a queue should be present in the model. For simplicity, a FIFO (First In, First Out) queue is used.

As the Packet objects only exist to introduce load, they can be dropped at the Network component after being processed. Alternatively, they could be placed on another output port, that is not connected to the ChatServer Atomic DEVS model.

For example: if the Network component (bandwidth 2000 bits/s) receives a Packet (size 100 bits) at time 0.0, the network has processed the Packet at time 0.0 + 100 / 2000. It is possible that another Packet (size 200 bits) is received while processing, in which case the new Packet will be queued. The processing of the second Packet will only commence at time 0.0 + 100 / 2000, so it will be processed at time 0.0 + 100 / 2000 + 200 / 2000.

ChatServer

The ChatServer simply has to reply to incoming messages from the ChatClient. Generic Packet events can be ignored, as they do not have an influence on the behaviour.

Before replying to the message, a specific delay has to be introduced, to signify the time it takes to process the message at the server side. This is again an abstraction of the real world, but it is sufficient for our purposes. In more detailed models, it would be possible to incorporate a maximum load for the server.

LoadGenerator

To allow the modelling of other load on the network, an Atomic DEVS model is introduced that will model the additional load on the network. This load is represented by the LoadGenerator outputting a Packet, with a random size, after a certain interval.

The exact distribution for the random size does not matter, as long as the resulting average load stays lower than the maximum bandwidth of the Network

By supporting different types of load generators, it would become possible to test the setup under a variety of situations. This way, you can e.g. compare the difference between sizes drawn from a uniform and a normal distribution.

Note that there should be load on both directions of the network: from the client to the server and from the server to the client.

Simulation

Perform a reasonable number of simulation experiments. Always choose the simulation duration sufficiently long enough to get statistically relevant measurements.

Choose some meaningful values for the various parameters to demonstrate the correctness of your model. In particular, make the behaviour deterministic, for extreme cases, so it is possible to analytically determine the performance metrics.

Discuss your results !

Practical issues

Modelling of the DEVS model can be done using the AToMPM Classic DEVS formalism. For installation, see the AToMPM installation instructions (only section 1 is required for this course). Afterwards, please unzip the patch file in your root AToMPM folder. This patch contains the Statecharts and DEVS formalisms used in this assignment. To use AToMPM, use Google Chrome (Firefox or others are NOT supported) and go to http://localhost:8124/atompm. In the toolbar, load the toolbar /Formalisms/ClassicDEVS/ClassicDEVS.defaultIcons.metamodel. Designed models can be exported by loading the /Toolbars/ClassicDEVS/export.buttons.model toolbar and pressing the 'export' icon. The files are generated in the folder 'exported_to_pypdevs' in the root of your AToMPM folder.

Left click on the desired model and afterwards right click somewhere in the canvas to place the selected model. You can edit attributes of the model by either using the middle mouse button, or selecting the model and pressing the 'insert' key on your keyboard. As the synthesized model will be in Python, you should write your methods in Python code. Drawing connections is done by right clicking on the source model and dragging the mouse to the destination model. When you are happy with your model, you can export it to PythonPDEVS and run it by invoking "python experiment.py".

You will need to update the experiment.py file to resemble your experiment. As you will be comparing different approaches, you would normally have to create multiple simulators, one for each model being compared. The statistics can be printed after the simulate call and printed to the console, to be plotted at the end (e.g. using gnuplot). You are strongly advised to first study the Classic DEVS traffic light example.

You will use the PyPDEVS (Python PDEVS) simulator. Installing PythonPDEVS can be done by executing python setup.py install --user. Note that you need Python 2.7 to be able to run PythonPDEVS. Finally, you can run the simulation by executing python experiment.py.

Note that in PythonPDEVS, when an external transition is triggered, this means that some external input has arrived on one or more of the ports. The inputs will be passed to the method in the form of a dictionary, which is the only argument of the extTransition method. The key values of this dictionary are the ports. If a port is not present in the dictionary, there was no input on that port. The elapsed time can be accessed using the elapsed attribute, but note that this is only correct in the extTransition method. It is therefore not allowed to access the elapsed attribute in an intTransition (and its value will be undefined).

Additional patches

There was an error in the traffic light example, where the condition on the external transition simply started with "isintance(...". This is solved in the patch, so copy over the trafficlight.model file over into your own user folder. The error was that conditions (and basically everything else in Python code) should return the result. The code should thus have started as: "return isinstance(...".
Maintained by Hans Vangheluwe. Last Modified: 2014/12/01 04:06:07.