Manual For Accompanying Tools
The FlowSim tool suite is supported by two random model generators, r-dtmc for DTMCs and
r-mdp for PAs/MDPs, and a model examination tool, modelstat, which prints out
generic information about input models.
Random DTMC Generator
The random DTMC generator is a command-line application which will generate a single stochastic DTMC per invocation, according to user-specified parameters, and output that model in the input format used by FlowSim. It offers relatively fine-grained control over the properties of the generated model.
r-dtmc can be used in three different ways:
| 1) r-dtmc N P | |
| 2) r-dtmc N A B | |
| 3) r-dtmc N A B C Fb Lb Cb Pb Sb | |
| N | number of states, > 0 |
| P | probability of an edge existing between two states, [0,1] |
| A | minimum number of successors per state, A ≥ 0 |
| B | maximum number of successors per state, B ≥ A |
| C | number of clusters in model, 1 ≤ C ≤ N |
| Fb | bias towards A or B successors per state, [-1,1] |
| Lb | bias towards linear model (acyclic), [0,1] |
| Cb | bias towards clustering, [0,1] |
| Pb | probability distribution bias, 0=uniform, [0,1] |
| Sb | bias towards certain states being picked as successors more often than others, [0,1] |
These parameters are the same as those used to specify random models to FlowSim. You can find a more detailed explanation of each parameter in the FlowSim manual at the bottom of the page.
Usage examples
The following commands each illustrate one parameter set:
r-dtmc 200 0.01
This command will generate a model with 200 states. In such a model, 40000 transitions can be
formed at most; for each potential transition, there is a 1% chance that it will end up in
the model, so the result models will have 400 transitions on average, which are distributed
randomly across the state space. Transition probabilities are equal within the successor set
of any one state.
r-dtmc 200 5 10
This command will also generate a model with 200 states, but each of those states will have
between 5 and 10 successors. The transition probabilities are again equal within the successor
set of any one state.
r-dtmc 200 5 10 2 0 1 1 0 0
In this mode, the first three arguments have the same meaning as in the previous example.
The state space will also be partitioned into two sets (not necessarily of equal size), such
that there are no transitions between the two sets (C=2, Cb=1). This model will also not
contain any cycles (Lb=1). The remaining arguments are left at their default, so the number
of successors will be uniformly random between 5 and 10 (Fb=0), transition probabilities will
be equal within each successor set (Pb=0) and there are no preferred successors (Sb=0).
Notes
It is important to understand that the effects of some settings are mutually exclusive, and the behavior of certain configurations isn't always defined. However, the tool doesn't forbid any combinations of settings, so long as the specified values are in their respective valid ranges. A few examples of problematic cases:
- If Cb=1 and the number of clusters approaches the number of states, it may not be possible to create the requested minimum number of successors, because there may not be enough successors to pick from in a cluster.
- As the number of successors per state approaches the number of states, the successor bias becomes decreasingly meaningful, because (almost) all states will be in every successor set anyway.
- If the linearity bias is 1, there must be a sink state without any outgoing transitions, so a minimum number of transitions greater than zero cannot be fulfilled.
Also note that when this tool was developed, the goal was to be able to effect a gradual change of the model features described by the biases. There is no guarantee that the values specified for the biases are meaningful as probabilities in the context of conducting statistical analysis on the output models, or that the quality of the random number generator is adequate for such use.
Random PA Generator
The random PA generator functions similarly to the random DTMC generator, but creates PAs/MDPs instead. It offers less finegrained control over the created models.
| r-mdp N A B NA [min-A [max-A [R [Lbias]]]] | |
| N | number of states, > 0 |
| A | minimum number of successors per action (not state!), A ≥ 0 |
| B | maximum number of successors per action, B ≥ A |
| NA | total number of different actions, > 0 |
| min-A | minimum number of actions outgoing from each state, > 0, default 1 |
| max-A | maximum number of actions outgoing from each state, ≥ min-A, default max(min-A,NA) |
| R | likelihood of all actions outgoing from a state being the same, i.e. R=0.0: actions are random, R=1.0: all actions the same, default 0.0 |
| Lbias | linearity bias, 0.0=uniformly random, 1.0=acyclic model, default 0.0 |
Similar to r-dtmc, not all parameters are necessary. r-mdp only
requires the first four command-line arguments, the remaining ones may be specified if additional
control is desired. However, so arguments may be skipped; you cannot specify Lbias
without also specifying min-A, max-A and R.
The first three parameters, N, A and B, specify the
number of states in the model as well as the minimum and maximum numbers of transitions per
successor distribution, as with the random DTMC generator. NA is the number of action
labels for the model, e.g. a value of 3 would mean that there are three distinct action labels
to be assigned to the actions of a state.
The generated model can be further specified through the min-A and max-A
parameters, which define the minimum and maximum numbers of actions per state. By default, the minimum
number if 1 and the maximum number is NA, the number of distinct action labels. Note that
if you set max-A to a value higher than NA, the generated model will have
states where multiple actions have the same label.
Furthermore, you can control the likelihood of the actions of any one state all sharing the same action
label using the R parameter. At zero, the action labels will be random (several actions
may share the same label). With higher values of R, the likelihood of action
labels being the same will increase. Note that this parameter cannot be used to specify that the labels
should be different.
Finally, the Lbias parameter has the same effect as with r-dtmc.
Usage example
r-mdp 200 5 10 3 1 2 1
This command will generate a model with 200 states with successor distributions of orders between 5 and 10.
There will be 3 distinct action labels in this model and any one state will have between 1 and 2 outgoing
actions. For states with two actions, these two actions will always have the same labels. The last parameter,
Lbias, is omitted, so that the transitions will be random and most likely create cycles.
Modelstat
Modelstat is a command-line utility used to examine generic model properties, such as the number of states, average number of successors, and to determine the autodetected floating-point approximation value. When invoking modelstat, pass the models that you wish to examine as command-line arguments.
Modelstat looks for the model type in the file extension (e.g. mymodel.dtmc would be recognized
as a DTMC). If the extension is something else, you need to tell modelstat what type of model it is looking at
by prefixing the filename with the model type, for example dtmc:mymodel.txt.
Usage example
Assume you want to examine the model stabilising0.pa, which can be found in the
examples/stabilising/ directory of your FlowSim tree. Assuming that modelstat is in your $PATH, you
would use the following command:
modelstat examples/stabilising/stabilising0.pa
There is no need for the prefix here, since the file extension contains the required information. Modelstat will output a listing detailing the total numbers of states, actions and transitions in the model, followed by minimum, maximum and average actions per state as well as min/max/avg transitions per action. You will also see the total numbers of states with a certain number of actions; this list can get rather long for some models, so occasionally it can be helpful to redirect modelstat's output into a text file for examination. The last block shows the lowest detected transition probability, deviation from stochastic distribution and floating-point approximation threshold.
