xQNM

Projects
xQNM

xQNM: A Model-Driven Approach to Simulate Queuing Network Models

Overview

Here we present xQNM, a Domain-Specific Language (DSL) for the specification and simulation of Queuing Network Models (QNMs).

xQNM defines a high-level and generic behavioral model for QNMs, which allows arrival and service times to follow arbitrary probability distributions, respects a common interchange format, and can be simulated using standar Model-Driven Engineering (MDE) techniques.

System Modeling

The modeling of a system as a DSL consits of:

1) Defining the abstract syntax, i.e., describing the structure of QNMs (by means of a metamodel).
2) Defining the concrete syntax, which is the graphical notation given to the elements in the metamodel.
3) Defining the semantics, for which we have developed a set of behavioral rules.

The abstract and concrete syntaxes are shown later. However, although the metamodel shown, named ePMIF, is used to depict the models in the tool graphical user interface, we use another metamodel, internal to our tool and transparent to users, in order to internally perform the simulations in e-Motions. The internal metamodel is explained in [5]

Creating ePMIF Models in xQNM

In order to draw a queuing network model, a general project has to be created. Then, in the project, we have to select New -> Other -> Example EMF Model Creation Wizards -> PMIF Model. Assign the name that the model will have (with .pmif extension). Another window appears where we have to select the root element. It will always be Queuing Network Model:

(Important note: when a new project is created, its path must not contain any space, nor does the name of the project. As mentioned later, our tool uses Maude for the simulations, and Maude requires paths not to include any spaces)

When the file is created, the QNM is visualized in a tree view form. To open the graphical editor, rigth click on the file -> initialize pmif_diagram diagram file. Give the same name to the new file (.pmif_diagram extension) and select the root element (Queuing Network Model):

The graphical editor is launched. The different elements (OpenWorkload, ClosedWorkload, SinkNode, SourceNode, Server, WorkUnitServer, WorkUnitSR, TimeSR, DemandSR and Arc) can be selected from the panel on the rigth and be placed on the main panel. The panel at the bottom is the one for specifying the properties of the elements. It may not appear when the graphical editor is launched. In that case, right button on the main panel of the graphical editor -> Show Properties View.

Arcs are used for connecting nodes. In this way, they connect source nodes, sink nodes, servers and work unit servers among them. The remaining references present in the metamodel in ePMIF [1] MUST be specified in the Properties View. In fact, in order to be able to simulate and properly export a QNM model depicted in xQNM, all the attributes and references of every element have to be specified in the Properties View. As an exception, there are some attributes that do not need to be specified for simulating the QNM. They are timeUnits in every element and numberOfVisits in WorkUnitSR and TimeSR. In DemandSR, instead, the timeUnits attribute has to be specified.

Attributes whose type is an enumerated type (for example, arrivalDistr in OpenWorkload) can be selected using a drop down list. References are also created in this way. Please note that the element to be referenced has to be already created and a name has to be given to it. An auxiliary window is used to assign values to attributes which are sequences. In this way, the attribute has to be selected in the Properties View in order to open the window.

Those attributes representing the parameters of probabilistic distributions are of type sequence of real values. The order of the attributes in the sequence matters. These attributes are arrivalParams, thinkParams and serviceParams. The parameters in the sequences are ordered according to the alphabetical order of the name of the parameters. In this way, depending on the probabilistic distribution, the parameters order is:

Constant(double time)
Uniform(double lowerBound ; double upperBound)
Exponential(double mean)
Normal(double mean ; double variance)
Gamma(double scale ; double shape)
Weibull(double scale ; double shape)
Erlang(double scale ; double shape)
F(double denominatorDegreesOfFreedom ; double numeratorDegreesOfFreedom)
ChiSquare(double degreesOfFreedom)
Geometric(double probOfSuccess)
Lognormal(double logScale ; double shape)
Pareto(double scale ; double shape)
Pascal(double numOfSuccesses ; double probOfSuccess)
Poisson(double mean)

A QNM similar to that in page 572 in Jain's book [2] can be seen in the next figure. Some service distributions are different. The file with the graphical model and it's tree view can be found here.

ePMIF metamodel

When depicting a model with the xQNM graphical user interface, the model has to conform to the ePMIF metamodel proposed in [1]. It can be seen as the MDE version of the PMIF 2 metamodel presented in [3], and is the following:

The following paragraphs provide a deep explanation of the metamodel, should the reader be only interested in the functionality of the xQNM tool, please procede to the next section.

A QueuingNetworkModel is composed of one or more Workloads, zero or more Arcs, one or more Nodes and one or more ServiceRequests. The Arc class connects Nodes among them. In a queuing network, jobs flow from node to node. There are two types of nodes, Servers and NonServerNodes. The former ones provide some processing service, while the latter show the topology of the network and represent the origin (SourceNode) and exit point (SinkNode) of OpenWorkloads. The Server class has a specialization class, named WorkUnitServer, that represents resources with a fixed processing service for each Workload that makes a request for service.

A Server provides service for different Workloads, where a Workload represents a collection of jobs that make similar ServiceRequests from Servers. Depending on the type of queuing network (open or closed), there are two types of Workloads:

OpenWorkload. It represents a set of jobs which arrive from the outside world, receive service, and exit. The number of jobs belonging to an OpenWorkload at any time is variable. A job represented by an OpenWorkload arrives at a SourceNode and departs at a SinkNode.
ClosedWorkload. It represents a fixed population of jobs that circulates among the Servers. A ClosedWorkload has a Server which acts as ThinkDevice and which is characterized by a think time.

A ServiceRequest associates Workloads with Servers. According to the relation from ServiceRequest to Workload and Server (one to one in both cases), a ServiceRequest associates one (and only one) Server with one (and only one) Workload. In this way, when a job which is represented by a workload arrives to a server, the service request associated to the workload and the server specifies how the job will be treated in that server. There are three types of ServiceRequests (for all of them, the numberOfVisits is an optional attribute):

WorkUnitServiceRequest. They are ServiceRequests associated to WorkUnitServers, so nothing about the service time has to be specified, since it is already in the WorkUnitServer.
TimeServiceRequest. It specifies the service time that the jobs representing the Workload associated to the ServiceRequest will have in the associated Server.
DemandServiceRequest. Same, but service time is specified in terms of service demand (service time multiplied by number of visits).

So far, the features described of our metamodel are similar to those of PMIF 2 [3], so we describe the differences from here. In PMIF 2, probabilities are specified as classes in the metamodel, and then those elements that need them (ServiceRequests and Workloads) have a reference to those classes. In a QNM where there are many forks in many servers, this approach results in a model with many elements. To reduce this number of elements, probabilities are specified as attributes in our metamodel. There are two classes that specify transitions: Workload and ServiceRequest. Probabilities in the former specify where a job transits after entering the SourceNode. In the latter, probabilities specify where a job transits after being processed by the Server associated with the ServiceRequest. In the PMIF 2 metamodel, an element of type Transit was needed for each path in a fork. In our case, no matter how many paths a Workload may follow, we only need two attributes: transitTo and transitProbs. The former contains a sequence (the order matters) with the names of the Nodes where the Workload can transit. The latter contains a sequence with the probabilities of transitions to the Servers contained in the transitTo attribute. Please note that the order in both attributes has to match.

As an example, suppose that in the QNM shown in the xQNM graphical interface in the figure above (the first node represents a CPU and the other two connected to it represent a disk A and a disk B), the ServiceRequest associated to the CPU contains the following two attributes for specifying the transitions: transitTo: {DISKA, DISKB, SINK} and transitProbs: {0.4375, 0.5, 0.0625}. It means that the probability to transit to the disk A is 0.4375, it is 0.5 to transit to disk B, and it leaves the system with a probability of 0.0625. The addition of the values in the transitProbs sequence must be 1. In the transitions where there is only one path, the sequences of both attributes only contain one element.

Another difference is how service and arrival times are specified. In PMIF 2, they were specified with the attributes ArrivalRate and ServiceTime respectively. It is assumed that these values represent parameters of Poisson and Exponential distributions, respectively. In our case, we want PMIF to accept different probabilistic distributions for service and arrival times. In this way, we have a type (ProbDistributions) which is an enumeration with literals Constant, Uniform, Exponential, Normal, Gamma, Weibull, Erlang, F, ChiSquare, Geometric, Lognormal, Pareto, Pascal and Poisson. Our idea to specify arrival and service times is to use two attributes: arrivalDistr or serviceDistr, and arrivalParams or serviceParams. The former ones are of type ProbDistributions and specify the distribution that will model the arrival/service time. The latter ones contain a sequence (the order matters) with the parameters of such distributions. To apply an order to the parameters in the sequence, these will be ordered according to the alphabetical order of the name of the parameters.

The last significant difference with PMIF 2 is the use of references instead of attributes referring to names in some classes. Thus, for example, class Open Workload has attributes ArrivesAt and DepartsAt in the PMIF 2 metamodel which are of type String. They specify the name of the Source Node and Sink Node, respectively, that they are referring to. The same happens with class Service Request and attributes WorkloadName and ServerID. In our metamodel these attributes are references. This has the advantage that a reference cannot be incorrectly specified since a reference to an object that does not exist or to an object belonging to a different class from the one specified in the metamodel cannot be created, but a name, instead, can be improperly written.

Exporting and Importing Models in xQNM

Exporting models

Once a QNM model is defined in xQNM, we can export it to an XML file. We can choose the schema of the XML generated to be PMIF 2 [3] or ePMIF. When we choose the former, all the information about the probability distributions is lost, since PMIF 2 does not have that information. When we export the QNM model to a ePMIF file, that information is preserved.

To export a model, we have to do right click on the file with the .pmif extension -> xQNM -> export to PMIF 2 xml file or xQNM -> export to xPMIF xml file. A file with the same name but with .xml extension is automatically created. To view its content, simply double click on it.

The generated xml file from the QNM depicted before can be found here.

Importing models

In xQNM it is possible to import XML files containing models conforming to either ePMIF [1] or PMIF 2 [3]. To do that, we first need to add the XML file into our proyect in Eclipse. We can do it by simply draging and droping it or doing a copy/paste from the file in the system to the project. Then, right click on the file -> xQNM -> import from PMIF 2 or xPMIF file (see the considerations below). When we import a QNM from an XML file to xQNM, we obtain a .pmif file where the model can be visualized in a tree view. However, it is possible to obtain a file (with .pmif_diagram extension) where the model is graphically depicted. To do that, right click on the .pmif file -> Initialize pmif_diagram diagram file. Then, the root of the model (the Queuing Network Model) has to be selected.

When the .pmif_diagram file is created, simply doble click on it to open it. The elements appear in a random possition in the graphical editor, so the user simply has to arrange them as desired.

The original XML file representing the example in Jain's book [2], page 572 can be seen here. The .pmif file generated from it as well as the .pmif_diagram file with the non-arranged elements can be found here.

Considerations

A very small modification has to be done to XML files containing a QNM that conforms to PMIF 2 (with XML files conforming to ePMIF we do not need to to this) that we want to import. We need to modify the beginning and the end of the XML file. In this way, an XML file conforming to PMIF 2 has this form:

<?xml version=...>

<QueuingNetworkModel xmlns=...>

...

</QueuingNetworkModel>

We simply have to change the second and last lines so that the file should look like the following:

<?xml version=...>

<PMIFSimple:QueueingNetworkModel xmi:version="2.0" xmlns:xmi="http://www.omg.org/XMI" xmlns:PMIFSimple="PMIFSimple">

...

</PMIFSimple:QueueingNetworkModel>

Simulating QNMs in xQNM

Once a QNM is defined with xQNM, it can be simulated to obtain performance metrics. Please note that in order to successfully simulate a model in xQNM, it has to be correctly defined conforming to the ePMIF metamodel [1]. In this way, all the attributes and references of every element have to be specified. However, there are some attributes that do not need to be specified for simulating the QNM. They are timeUnits in every element and numberOfVisits in WorkUnitSR and TimeSR. In DemandSR, instead, the timeUnits attribute has to be specified.

There are two buttons to start and stop a simulation. When starting a simulation, the .pmif file has to be specified.

Please note that simulations last from some minutes until a few or several hours. It depends on the complexity of the model, how many performance measures that user wants to monitor and the stopping criteria and parameters chosen (since this will influenciate the time taken until the simulation reaches the steady state) [1].

While a simulation is running, a process bar appears in the lower right corner. When it finishes, a windows with a message is displayed.

When the simulation finishes, a file with .csv extension with the same name as the input .pmif model appears in the menu on the left. It can be open with spreadhsheet applications. A template showing the structure of the results can be seen here. Please note that for closed networks, their jobs average value will be shown as "0", since that meassure is not significant in those networks.

The behavioral rules applied for the simulation are described in [5].

Resources

The current version of xQNM works for Windows XP, Windows Vista and Windows 7.

here

eclipse.exe

The xQNM needs Maude 2.4 to simulate the QNMs. Maude 2.4 for Windows can be downloaded from here

Configuration

Once the eclipse for xQNM has been downloaded and unzipped, some configuration steps have to be followed:

If the operating system is Windows XP, it is alright. If it is Windows Vista or 7, the first time the eclipse.exe file is executed, it has to be run using the compatibility mode. To activate this option, right click on the eclipse.exe and select the compatibility mode. Then, selected the Windows XP (Service Pack 2) compatibility mode.

Please note that the Windows version of the figure is in Spanish.

The first time a new workspace is created, Maude has to be configured in Eclipse. To do that, once the eclipse.exe has been launched, go to Window -> Preferences -> Maude. Then, select the maude.exe file in Maude binary file and the path where the workspace is in Temporal files. This is necessary in order to successfully simulate in Maude.

Examples

An open QNM similar to that in Jain's book [2], page 572, can be found here.
The PMIF 2 XML file exported from the previous QNM can be found here.
The ePMIF XML file exported from the previous QNM can be found here.
The .pmif file generated from the previous XML file as well as the .pmif_diagram file with the non-arranged elements can be found here
A closed QNM can be found here.
The ePMIF XML file exported from the previous QNM can be found here.
An open QNM for the two-stage tandem network example in Trivedi's book [4], page 556, can be found here.

References

[1] Javier Troya, Antonio Vallecillo. "Specification and Simulation of Queuing Network Models using Domain-Specific Languages", Computer Standards & Interfaces, Volume 36, 5 (2014), pp. 863-879
[2] Jain, R.: "The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling". Wiley (1991)
[3] Smith, Connie U. and Lladó, Catalina M. and Puigjaner, Ramon: "Performance Model Interchange Format (PMIF 2): a comprehensive approach to Queueing Network Model interoperability". Performance Evaluation 67(7) (2010) 548 - 568
[4] Trivedi, K.S.: "Probability and Statistics with Reliability, Queuing and Computer Science Applications". Wiley (2002)
[5] Generic behavioral rules for any QNM (link), 2012