Network models
Throughout this chapter, we discuss the specification of Network
models, which are extended queueing networks.
Line currently supports open, closed, and
mixed networks with non-exponential service and arrivals, and
state-dependent routing. All solvers support the computation of basic
performance metrics, while some more advanced features are available
only in specific solvers. Each Network
model requires in input a
description of the nodes, the network topology, and the characteristics
of the jobs that circulate within the network. In output,
Line returns performance and reliability
metrics.
The default metrics supported by all solvers are as follows:
-
Mean queue-length (
QLen
). This is the mean number of jobs residing at a node when this is observed at a random instant of time. -
Mean utilization (
Util
). For nodes that serve jobs, this is the mean fraction of time the node is busy processing jobs. In both single-server and multi-server nodes, this is a number normalized between 0 and 1, corresponding to 0% and 100%. In infinite-server nodes, the utilization is set by convention equal to the mean queue-length, therefore taking the interpretation of the mean number of jobs in execution at the station. -
Mean response time (
RespT
). This is the mean time a job spends traversing a node within a network. If the node is visited multiple times, the response time is the time spent for a single visit to the node. -
Mean residence time (
ResidT
). This is the total time a job accumulates, on average, to traverse a node within a network. If the node is visited multiple times, the residence time is the time accumulated overall visits to the node prior to returning to the reference station or arriving to a sink. -
Mean throughput (
Tput
). This is the mean departure rate of jobs completed at a resource per time unit. Typically, this matches the mean arrival rate, unless the node switches the class of the jobs in which case the arrival rate of a class may not match its departure rate.
The above metrics refer to the performance characteristics of individual nodes. Response times and throughputs can also be system-wide, meaning that they can describe end-to-end performance during the visit to the network. In this case, these metrics are called system metrics.
A queueing network can be described in
Line using the Network
class
constructor with a unique string identifying the model name:
model = Network('myModel');
The returned object of the Network
class offers functions to
instantiate and manage resource nodes (stations, delays, caches, ...)
visited by jobs of several types (classes).
A node is a resource in the network that can be visited by a job. A node
must have a unique name and can either be stateful or stateless, the
latter meaning that the node does not require state variables to
determine its state or actions. If jobs visiting a stateful node can be
required to spend time in it, the node is also said to be a station. A
list of nodes available in Network
models is given in
Table 1.1.
Node | Description |
---|---|
Cache |
A node to switch job classes based on hits/misses in its cache |
ClassSwitch |
A node to switch job classes based on a static probability matrix |
Delay |
A station where jobs spend time without queueing |
Fork |
A node that forks jobs into tasks |
Join |
A node that joins sibling tasks into the original job |
Logger |
A node that logs passage of jobs |
Queue |
A node where jobs queue and receive service |
Router |
A node that routes jobs to other nodes |
Sink |
Exit point for jobs in open classes |
Source |
Entry point for jobs in open classes |
Nodes available in Network
models.
We now provide more details on each of the nodes available in Network
models.
A Queue
specifies a queueing station from its name and scheduling
strategy, e.g.
queue = Queue(model, 'Queue1', SchedStrategy.FCFS);
specifies a first-come first-served queue. It is alternatively possible
to instantiate a queue using the QueueingStation
constructor, which is
merely an alias for Queue
.
Queueing stations have by default a single server. The
setNumberOfServers
method can be used to instantiate multi-server
stations.
Valid scheduling strategies are specified within the SchedStrategy
static class and include:
-
First-come first-serve (
SchedStrategy.FCFS
) -
Infinite-server (
SchedStrategy.INF
) -
Processor-sharing (
SchedStrategy.PS
) -
Service in random order (
SchedStrategy.SIRO
) -
Discriminatory processor-sharing (
SchedStrategy.DPS
) -
Generalized processor-sharing (
SchedStrategy.GPS
) -
Shortest expected processing time (
SchedStrategy.SEPT
) -
Shortest job first (
SchedStrategy.SJF
) -
Head-of-line priority (non-preemptive) (
SchedStrategy.HOL
)
If a strategy requires class weights, these can be specified directly as
an argument to the setService
function or using the setStrategyParam
function, see later the description of DPS scheduling for an example.
Delay stations, also called infinite server stations, may be
instantiated either as objects of Queue
class, with the
SchedStrategy.INF
scheduling strategy, or using the following
specialized constructor
delay = Delay(model, 'ThinkTime');
As for queues, for readability it is possible to instantiate delay nodes
using the DelayStation
class which is an alias for the Delay
class.
As seen in the M/M/1 getting started example, these nodes are mandatory elements for the specification of open classes. Their constructor only requires a specification of the unique name associated to the nodes:
source = Source(model, 'Source');
sink = Sink(model, 'Sink');
The fork and join nodes are currently available only for the JMT
solver. The Fork
splits an incoming job into a set of sibling tasks,
sending out one task for each outgoing link. These tasks inherit the
class of the original job and are served as normal jobs until they are
reassembled at a Join
station.
Their specification of Fork and Join nodes only requires the name of the node
fork = Fork(model, 'Fork');
join = Join(model, 'Join', fork);
The number of tasks sent by a Fork
on each output link can be set
using the setTasksPerLink
method of the fork
object. To enable
effective analytical approximations, presently
Line requires that every join node is
bound to a specific fork node, although specific solvers will ignore
this information (e.g., JMT).
Also note that the routing probabilities out of the Fork
node need to
be set to 1.0 towards every other node connected to the Fork
. For
example, a Fork
sending jobs in class 1 to nodes
After splitting a job into tasks, Line
takes the convention that visit counts refer to the average number of
passages at the target resources for the original job, scaled by the
number of tasks. For example, if a job is split into two tasks at a fork
node, each visiting respectively nodes
This is a stateless node to change the class of a transiting job based
on a static probabilistic policy. For example, it is possible to specify
that all jobs belonging to class 1 should become of class 2 with
probability
cs = ClassSwitch(model, 'ClassSwitchPoint',[0.0, 1.0; 0.3, 0.7]);
This is a stateful node to store one or more items in a cache of finite size, for which it is possible to specify a replacement policy. The cache constructor requires the total cache capacity and the number of items that can be referenced by the jobs in transit, e.g.,
cacheNode = Cache(model, 'Cache1', nitems, capacity, ReplacementStrategy.LRU);
If the capacity is a scalar integer (e.g., [15]
), then it represents
the total number of items that can be cached and the value cannot be
greater than the number of items. Conversely, if it is a vector of
integers (e.g., [10,5]
) then the node is a list-based cache, where the
vector entries specify the capacity of each list. We point to
[@GastH16] for more details on list-based caches and their replacement
policies.
Available replacement policies are specified within the
ReplacementStrategy
static class and include:
-
First-in first-out (
ReplacementStrategy.FIFO
) -
Random replacement (
ReplacementStrategy.RR
) -
Least-recently used (
ReplacementStrategy.LRU
) -
Strict first-in first-out (
ReplacementStrategy.SFIFO
)
Upon cache hit or cache miss, a job in transit is switched to a user-specified class. More details are given later in Section 1.1.5.
This node is able to route jobs according to a specified
RoutingStrategy
, which can either be probabilistic or not (e.g.,
round-robin). Upon entering a Router
, a job neither waits nor receives
service; it is instead directly forwarded to the next node according to
the specified routing strategy. A Router
can be instantiated as
follows:
router = Router(model, 'RouterNode');
An example of use of this node is given in
Section [example-4-round-robin-load-balancing].
Routing strategies need to be specified for each class using the
setRouting
method and valid choices are as follows
-
Random routing (
RoutingStrategy.RAND
) -
Round robin (
RoutingStrategy.RROBIN
) -
Probabilistic routing (
RoutingStrategy.PROB
) -
Join-the-shortest-queue (
RoutingStrategy.JSQ
)
For example, assume that oclass
is a class of jobs. In order to route
jobs in this class with equal probabilities to every outgoing link we
set
router.setRouting(oclass, RoutingStrategy.RAND);
It should be noted that setRouting
is also available for all other
nodes such as queueing stations, delays, etc. Therefore, the added value
of the Router
node is the ability to represent certain system elements
that centralize the routing logic, such as load balancers.
A logger node is a node that closely resembles the logger node available
in the JSIMgraph simulator within JMT. At present, models that include
this element can only be solved using the JMT
solver.
A Logger
node records information about passing jobs in a csv
file,
such as the timestamp of passage and general information about the jobs.
The node can be instantiated as follows
logger=Logger(self,'LoggerNode','logfile.csv');
The following methods can be used to specify the information that needs
to be stored in the csv
file
-
setStartTime
: record a timestamp for the wallclock time when the simulation started. -
setJobID
: record a unique id for the passing job. -
setJobClass
: record the class of the passing job. -
setTimestamp
: record a timestamp for the simulated time when the job passed in the logger. -
setTimeSameClass
: record the time elapsed since the last passage of a job of the same class. -
setTimeAnyClass
: record the time elapsed since the last passage of a job of any class.
Each method can be called either with a single true
or false
argument, to enable or disable the recording of the corresponding
information, e.g.
logger.setJobClass(true);
The routing behavior of jobs can be set up as explained for regular nodes such as queues or delay stations.
Upon setting service distributions at a station, one may also specify
scheduling parameters such as weights as additional arguments to the
setService
function. For example, if the node implements
discriminatory processor sharing (SchedStrategy.DPS
), the command
queue.setService(class2, Cox2.fitMeanAndSCV(0.2,10), 5.0);
assigns a weight 5.0 to jobs in class 2. The default weight of a class is 1.0.
The functions setCapacity
and setChainCapacity
of the Station
class are used to place constraints on the number of jobs, total or for
each chain, that can reside within a station. Note that
Line does not allow one to specify buffer
constraints at the level of individual classes unless chains contain a
single class, in which case setChainCapacity
is sufficient for the
purpose.
For example,
example_closedModel_3
delay.setChainCapacity([1,1])
model.refreshCapacity()
creates an example model with two chains and three classes (specified in
example_closedModel_3.m
) and requires the second station to accept a
maximum of one job in each chain. Note that if we were to ask for a
higher capacity, such as setChainCapacity([1,7])
, which exceeds the
total job population in chain 2, Line
would have automatically reduced the value 7 to the chain 2 job
population (2). This automatic correction ensures that functions that
analyze the state space of the model do not generate unreachable states.
The refreshCapacity
function updates the buffer parameterizations,
performing appropriate sanity checks. Since example_closedModel_3
has
already invoked a solver prior to our changes, the requested
modifications are materially applied by
Line to the network only after calling an
appropriate refreshStruct
function, see the sensitivity analysis
section. If the buffer capacity changes were made before the first
solver invocation on the model, then there would not be the need for a
refreshCapacity
call, since the internal representation of the
Network
object used by the solvers is still to be created.
Jobs travel within the network placing service demands at the stations. The demand placed by a job at a station depends on the class of the job. Jobs in open classes arrive from the external world and, upon completing the visit, leave the network. Jobs in closed classes start within the network and are forbidden to ever leave it, perpetually cycling among the nodes.
The constructor for an open class only requires the class name and the
creation of special nodes called Source
and Sink
source = Source(model, 'Source');
sink = Sink(model, 'Sink');
Sources are special stations holding an infinite pool of jobs and
representing the external world. Sinks are nodes that route a departing
job back into this infinite pool, i.e., into the source. Note that a
network can include at most a single Source
and a single Sink
.
Once source and sink are instantiated in the model, it is possible to instantiate open classes using
class1 = OpenClass(model, 'Class1');
Line does not require explicitly
associating source and sink with the open classes in their constructors,
as this is done automatically. However, the
Line language requires explicitly
creating these nodes since the routing topology needs to indicate the
arrival and departure points of jobs in open classes. However, if the
network does not include open classes, the user will not need to
instantiate a Source
and a Sink
.
To create a closed class, we need instead to indicate the number of jobs
that start in that class (e.g., 5 jobs) and the reference station for
that class (e.g., queue
), i.e.:
class2 = ClosedClass(model, 'Class2', 5, queue);
The reference station indicates a point in the network used to calculate
certain performance indexes, called system performance indexes. The
end-to-end response time for a job in an open class to traverse the
system is an example of a system performance index (system response
time). The reference station of an open class is always automatically
set by Line to be the Source
.
Conversely, the reference station needs to be indicated explicitly in
the constructor for closed classes since the point at which a class job
completes execution depends on the semantics of the model.
Line also supports a special class of jobs, called self-looping jobs, which perpetually loop at the reference station, remaining in their class. The following example shows the syntax to specify a self-looping job, which is identical to closed classes but there is no need later to specify routing information.
model = Network('model');
% Block 1: nodes
delay = Delay(model, 'Delay');
queue = Queue(model, 'Queue1', SchedStrategy.FCFS);
% Block 2: classes
cclass = ClosedClass(model, 'Class1', 10, delay, 0);
slclass = SelfLoopingClass(model, 'SLC', 1, queue, 0);
delay.setService(cclass, Exp(1.0));
queue.setService(cclass, Exp(1.5));
queue.setService(slclass, Exp(1.5));
% Block 3: topology
P = model.initRoutingMatrix;
P{cclass} = [0.7,0.3;1.0,0];
model.link(P);
Note that any routing information specified for the self-looping class will be ignored.
Line also accepts models where a user has instantiated both open and closed classes. The only requirement is that, if two classes communicate by means of a class-switching mechanism, then the two classes must either be all closed or all open. In other words, classes in the same chain must either be both closed or open. Furthermore, for all closed classes in the same chain, it is required for the reference station to be the same.
If a class has a priority, with 0 representing the highest priority,
this can be specified as an additional argument to both OpenClass
and
ClosedClass
, e.g.,
class2 = ClosedClass(model, 'Class2', 5, queue, 0);
In Network
models, priorities are intended as hard priorities and the
only supported priority scheduling strategy (SchedStrategy.HOL
) is
non-preemptive. Weight-based policies such as DPS and GPS may be used,
as an alternative, to prevent starvation of jobs in low-priority
classes.
In Line, jobs can switch their class while they travel between nodes (including self-loops on the same node). For example, this feature can be used to model queueing properties such as re-entrant lines in which a job visiting a station a second time may require a different average service demand than at its first visit.
A chain defines the set of reachable classes for a job that starts in
the given class
Jobs in open classes can only switch to another open class. Similarly, jobs in closed classes can only switch to a closed class. Thus, class switching from open to closed classes (or vice-versa) is forbidden. More details about class-switching are given in Section 1.1.5.
Before we have shown that the specification of classes requires choosing a reference station. In Line, reference stations are properties of chains, thus if two closed classes belong to the same chain they must have the same reference station. This avoids ambiguities in the definition of the completion point for jobs within a chain.
For example, the system throughput for a chain is defined as the sum of
the arrival rates at the reference station for all classes in that
chain. That is, the solver counts a return to the reference station as a
completion of the visit to the system. In the case of open chains, the
reference station is always the Source
and the system throughput
corresponds to the rate at which jobs arrive at the sink Sink
, which
may be seen as the arrival rate seen by the infinite pool of jobs in the
external world. If there is no class switching, each chain contains a
single class, thus per-chain and per-class performance indexes will be
identical.
Occasionally, it is possible to encounter situations where a job needs to change class while remaining inside the same station. In this case, Line modifies the network automatically to introduce a class-switching node for the job to route out of the station and immediately return to it in the new class.
One complication of the approach is that, by departing the node and returning to it, the job visits the station one additional time, affecting the visit count to the station and therefore performance metrics such as the residence time. To cope with this issue, Line offers a method for the class objects, called setReferenceClass, that allows users to specify whether the visit of that class to the reference station should be considered upon computing the residence times across the network for the chain to which the class belongs. By default, all classes traversing the reference station are used in the visit count calculation.
Jobs travel between nodes according to the network topology and a
routing strategy. Typically a queueing network will use a probabilistic
routing strategy (RoutingStrategy.PROB
), which requires specifying
routing probabilities among the nodes. The simplest way to specify a
large routing topology is to define the routing probability matrix for
each class, followed by a call to the link
function. This function
will automatically add certain nodes to the network to ensure the
correct class switching for jobs moving between stations (ClassSwitch
elements).
In the running case, we may instantiate a routing topology as follows:
P = model.initRoutingMatrix;
P{class1}(source,queue) = 1.0;
P{class1}(queue,[queue,delay]) = [0.3,0.7]; % self-loop with probability 0.3
P{class1}(delay,sink) = 1.0;
P{class2}(delay,queue) = 1.0; % note: closed class jobs start at delay
P{class2}(queue,delay) = 1.0;
model.link(P);
When used as arguments to a cell array or matrix, class, and node objects will be replaced by a corresponding numerical index. Normally, the indexing of classes and nodes matches the order in which they are instantiated in the model and one can therefore specify the routing matrices using this property. In this case, we would have
P = model.initRoutingMatrix;
P{class1} = [0,1,0,0; % row: source
0,.3,.7,0; % row: queue
0,0,0,1; % row: delay
0,0,0,0]; % row: sink
P{class2} = [0,0,0,0;
0,0,1,0;
0,1,0,0;
0,0,0,0];
model.link(P);
Where needed, the getClassIndex
and getNodeIndex
functions return
the numerical index associated with a node name, for example
model.getNodeIndex(’Delay’)
. Class and node names in a network must
be unique. The list of names already assigned to nodes in the network
can be obtained with the getClassNames
, getStationNames
, and
getNodeNames
functions of the Network
class.
It is also important to note that the routing matrix in the last example
is specified between nodes, instead of between just stations or
stateful nodes, which means that for example elements such as the Sink
need to be explicitly considered in the routing matrix. The only
exception is that ClassSwitch
elements do not need to be explicitly
instantiated in the routing matrix, provided that one uses the link
function to instantiate the topology. Note that the routing matrix
assigned to a model can be printed on the screen in a human-readable
format using the printRoutingMatrix
function, e.g.,
>> model.printRoutingMatrix
Delay [Class1] => Queue1 [Class1] : Pr=1.000000
Delay [Class2] => Queue1 [Class2] : Pr=0.001000
Queue1 [Class1] => Queue1 [Class1] : Pr=0.300000
Queue1 [Class1] => Source [Class1] : Pr=0.700000
Queue1 [Class2] => Source [Class2] : Pr=1.000000
Source [Class1] => Sink [Class1] : Pr=1.000000
Source [Class2] => Queue1 [Class2] : Pr=1.000000
Sink [Class2] => Source [Class2] : Pr=1.000000
The above routing specification style is only for models with probabilistic routing strategies between every pair of nodes. A different style should be used for scheduling policies that do not require to explicit routing probabilities, as in the case of state-dependent routing. Currently supported strategies include:
-
Round robin (
RoutingStrategy.RROBIN
). This is a deterministic strategy that sends jobs to outgoing links in a cyclic order. -
Random routing (
RoutingStrategy.RAND
). This is equivalent to a standard probabilistic strategy that for each class assigns identical values to the routing probabilities of all outgoing links. When a target is invalid its probability is kept to zero, e.g., random routing will not send a job in a closed class to a sink. -
Join-the-Shortest-Queue (
RoutingStrategy.JSQ
). This is a non-probabilistic strategy that sends jobs to the destination with the smallest total number of jobs in it (either queueing or receiving service). If multiple stations have the same total number of jobs, then the destination is chosen at random with equal probability.
For the above policies, the function addLink
should be first used to
specify pairs of connected nodes
model.addLink(queue, queue); %self-loop
model.addLink(queue, delay);
Then an appropriate routing strategy should be selected at every node, e.g.,
queue.setRouting(class1,RoutingStrategy.RROBIN);
assigns round robin among all outgoing links from the queue
node.
A model could also include both classes with probabilistic routing strategies and classes that use round-robin or other non-probabilistic strategies. To instantiate routing probabilities in such situations one should then use, e.g.,
queue.setRouting(class1,RoutingStrategy.PROB);
queue.setProbRouting(class1, queue, 0.7)
queue.setProbRouting(class1, delay, 0.3)
where setProbRouting
assigns the routing probabilities to the two
links.
In the presence of open classes, and in mixed models with both open and closed classes, one needs only to specify the routing probabilities out of the source. The probabilities out of the sink can all be set to zero for all classes and destinations (including self-loops). The solver will take care of adjusting these inputs to create a valid routing table.
Tandem networks are open queueing networks with a serial topology. Line provides functions that ease the definition of tandem networks of stations with exponential service times. For example, the getting started Example 1 on the M/M/1 queue illustrates a simplified way to specify a serial routing topology, i.e.,
model.link(Network.serialRouting(source,queue,sink));
In a similar fashion, we can also rapidly instantiate a tandem network consisting of stations with PS and INF scheduling as follows
lambda = [10,20]; % lambda(r) - arrival rate of class r
D = [11,12; 21,22]; % D(i,r) - class-r demand at station i (PS)
Z = [91,92; 93,94]; % Z(i,r) - class-r demand at station i (INF)
modelPsInf = Network.tandemPsInf(lambda,D,Z)
The above snippet instantiates an open network with two queueing
stations (PS), two delay stations (INF), and exponential distributions
with the given inter-arrival rates and mean service times. The
Network.tandemPs
, Network.tandemFcfs
, and Network.tandemFcfsInf
functions provide static constructors for networks with other
combinations of scheduling policies, namely only PS, only FCFS, or FCFS
and INF.
A tandem network with closed classes is instead called a cyclic network. Similar to tandem networks, Line offers a set of static constructors:
-
Network.cyclicPs
: cyclic network of PS queues -
Network.cyclicPsInf
: cyclic network of PS queues and delay stations -
Network.cyclicFcfs
: cyclic network of FCFS queues -
Network.cyclicFcfsInf
: cyclic network of FCFS queues and delay stations
These functions only require replacing the arrival rate vector A
by a
vector N
specifying the job populations for each of the closed
classes, e.g.,
N = [10,20]; % N(r) - closed population in class r
D = [11,12; 21,22]; % D(i,r) - class-r demand at station i (PS)
modelPsInf = Network.cyclicPs(N,D)
Depending on the specified probabilities, a job will be able to switch
its class only among a subset of the available classes. Each subset is
called a chain. Chains are computed in
Line as the weakly connected components
of the routing probability matrix of the network when this is seen as an
undirected graph. The function model.getChains
produces the list of
chains for the model, inclusive of a list of their composing classes.
The definition of class switching in a model is integrated in the specification of the routing between stations as described next.
In models with class switching and probabilistic routing at all nodes, a
routing matrix is required for each possible pair of source and target
classes. For instance, suppose that in the previous example the job in
the closed class class2
switches into a new closed class (class3
)
while visiting the queue
node. We can specify this routing strategy as
follows:
class3 = ClosedClass(model, 'Class3', 0, queue, 0);
P = model.initRoutingMatrix;
P{class1,class1}(source, queue) = 1.0;
P{class1,class1}(queue, [queue,delay]) = [0.3,0.7];
P{class1,class1}(delay, sink) = 1.0;
P{class2,class3}(delay, queue) = 1.0;
P{class3,class2}(queue, delay) = 1.0;
model.link(P);
where P{r,s}
is the routing matrix for jobs switching from class r
to s
. That is, P{r,s}(i,j)
is the probability that a job in class
r
departs node i
routing into node j
as a job of class s
.
Importantly, Line assumes that a job switches class an instant after leaving a station, thus the performance metrics of a class at the node refer to the class that jobs had upon arrival to that node.
In the presence of non-probabilistic routing strategies, such as
round-robin or join-the-shortest-queue, one may need to manually specify
the details of the class switching mechanism. This can be done through
addition to the network topology of ClassSwitch
nodes.
The constructor of the ClassSwitch
node requires to specify a
probability matrix
%% Block 1: nodes
...
csnode = ClassSwitch(model, 'ClassSwitch 1');
%% Block 2: classes
jobclass{1} = OpenClass(model, 'Class1', 0);
jobclass{2} = OpenClass(model, 'Class2', 0);
...
%% Block 3: topology
C = csnode.initClassSwitchMatrix;
C(jobclass{1},jobclass{2}) = 1.0;
C(jobclass{2},jobclass{2}) = 1.0;
csnode.setClassSwitchingMatrix(C);
Note that for a network with ClassSwitch
elements may be required to implement class-switching across all
possible links, including self-loops. Moreover, when multiple
ClassSwitch
nodes are present, then .
An advanced feature of Line available for
example within the Cache
node, is that the class-switching decision
can dynamically depend on the state of the node (e.g., cache hit/cache
miss). However, in order to statically determine chains,
Line requires that every class-switching
node declares the pair of classes that can potentially communicate with
each other via a switch. This is called the class-switching mask and
it is automatically computed. The boolean matrix returned by the
model.getClassSwitchingMask
function provides this mask, which has an
entry in row
Upon cache hit or cache miss, a job in transit is switched to a
user-specified class, as specified by the setHitClass
and
setMissClass
, so that it can be routed to a different destination
based on whether it found the item in the cache or not. The setRead
function allows the user to specify a discrete distribution (e.g.,
Zipf
, DiscreteSampler
) for the frequency at which an item is
requested. For example,
refModel = Zipf(0.5,nitems);
cacheNode.setRead(initClass, refModel);
cacheNode.setHitClass(initClass, hitClass);
cacheNode.setMissClass(initClass, missClass);
Here initClass
, hitClass
, and missClass
can be either open or
closed instantiated as usual with the OpenClass
or ClosedClass
constructors.
A number of statistical distributions are available to specify job
service times at the stations and inter-arrival times from the Source
station. The class PhaseType
offers distributions that are
analytically tractable, which are defined using absorbing Markov chains
consisting of one or more states (phases) and called phase-type
distributions. They include as special cases the following
distributions:
-
Exponential distribution:
Exp
$(\lambda)$ , where$\lambda$ is the rate of the exponential -
$n$ -phase Erlang distribution:Erlang
$(\alpha, n)$ , where$\alpha$ is the rate of each of the$n$ exponential phases -
$2$ -phase hyper-exponential distribution:HyperExp
$(p,\lambda_1,\lambda_2)$ , that returns an exponential with rate$\lambda_1$ with probability$p$ , and an exponential with rate$\lambda_2$ otherwise. -
$n$ -phase hyper-exponential distribution:HyperExp
$(p,\lambda)$ , that builds a$n$ -phase hyper-exponential from a rate vector$\lambda=[\lambda_1,\ldots,\lambda_n]$ and phase selection probabilities$p=[p_1,\ldots,p_n]$ . -
$2$ -phase Coxian distribution:Coxian
$(\mu_1,\mu_2,\phi_1)$ , which assigns phases$\mu_1$ and$\mu_2$ to the two rates, and completion probability from phase 1 equal to$\phi_1$ (the probability from phase 2 is$\phi_2=1.0$ ). -
$n$ -phase Coxian distribution:Coxian
$(\mu,\phi)$ , which builds an arbitrary Coxian distribution from a vector$\mu=[\mu_1,\ldots,\mu_n]$ of$n$ rates and a completion probability vector$\phi=[\phi_1,\ldots,\phi_n]$ with$\phi_n=1.0$ . -
$n$ -phase acyclic phase-type distribution:APH
$(\alpha,T)$ , which defines an acyclic phase-type distribution with initial probability vector$\alpha=[\alpha_1,\ldots,\alpha_n]$ and transient generator$T$ .
For example, given mean
queue.setService(class2, Cox2.fitMeanAndSCV(0.2,10));
where Cox2
is a static class to fit Coxian
distributions.
Inter-arrival time distributions can be instantiated in a similar way,
using setArrival
instead of setService
on the Source
node. For
example, if the Source
is node 3 we may assign the inter-arrival times
of class 2 to be exponential with mean 0.1 as follows
source.setArrival(class2, Exp.fitMean(0.1));
Is it also possible to plot the structure of a phase-type distribution
using PhaseType.plot
static method.
Non-Markovian distributions are also available, but typically they can
restrict the available solvers to the JMT
simulator. They include the
following distributions:
-
Deterministic distribution:
Det
$(\mu)$ assigns probability 1.0 to the value$\mu$ . -
Uniform distribution:
Uniform
$(a,b)$ assigns uniform probability$1/(b-a)$ to the interval$[a,b]$ . -
Gamma distribution:
Gamma
$(\alpha, k)$ assigns a gamma density with shape$\alpha$ and scale$k$ . -
Pareto distribution:
Pareto
$(\alpha, k)$ assigns a Pareto density with shape$\alpha$ and scale$k$ .
Lastly, we discuss two special distributions. The Disabled
distribution can be used to explicitly forbid a class to receive service
at a station. This may be useful to declare in models with sparse
routing matrices to debug the model specification. Performance metrics
for disabled classes will be set to NaN
.
Conversely, the Immediate
class can be used to specify instantaneous
service (zero service time). Typically,
Line solvers will replace zero service
times with small positive values
(GlobalConstants.FineTol
).
The fitMeanAndSCV
function is available for all distributions that
inherit from the PhaseType
class. This function provides exact or
approximate matching of the first two moments, depending on the
theoretical constraints imposed by the distribution. For example, an
Erlang distribution with SCV=0.75 does not exist, because in a Erlang.fitMeanAndSCV(1,0.75)
will return the closest approximation,
e.g., a 2-phase Erlang (SCV=0.5) with unit mean. The Erlang distribution
also offers a function fitMeanAndOrder
In distributions that are uniquely determined by more than two moments,
fitMeanAndSCV
chooses a particular assignment of the residual degrees
of freedom other than mean and SCV. For example, HyperExp
depends on
three parameters, therefore it is insufficient to specify mean and SCV
to identify the distribution. Thus, HyperExp.fitMeanAndSCV
automatically chooses to return a probability of selecting phase 1 equal
to 0.99. Compared to other choices, this particular assignment
corresponds to a higher probability mass in the tail of the
distribution. HyperExp.fitMeanAndSCVBalanced
instead assigns
To verify that the fitted distribution has the expected mean and SCV it
is possible to use the getMean
and getSCV
functions, e.g.,
>> dist = Exp(1);
>> dist.getMean
ans =
1
>> dist.getSCV
ans =
1
Moreover, the sample
function can be used to generate values from the
obtained distribution, e.g. we can generate 3 samples as
>> dist.sample(3)
ans =
0.2049
0.0989
2.0637
The evalCDF
and evalCDFInterval
functions return the cumulative
distribution function at the specified point or within a range, e.g.,
>> dist.evalCDFInterval(2,5)
ans =
0.1286
>> dist.evalCDF(5)-dist.evalCDF(2)
ans =
0.1286
For more advanced uses, the distributions of the PhaseType
class also
offer the possibility to obtain the standard getRepresentation
function [@BolGMT06]. The result will be a cell
array where element
A queueing station
Line presently supports limited
load-dependence [@CasHH21], meaning that it is possible to specify
the form of the load-dependent service up to a finite range of
To specify a load-dependence service for a queueing station over the
range setLoadDependence
method, passing a vector of size
queue.setLoadDependence(min(1:N,c)); % multi-server with c servers
where the setLoadDependence
is the scaling factor
A generalization of the load-dependent service model is
class-dependent service, where the service rate is now a function of
the vector $n_i=[n_{i,1},\ldots,{i,R}]$, where $n{i,r}$ is the current
number of class-$r$ jobs at station
Line supports class-dependence in the MVA
solver, provided that this is specified as a function handle. The solver
implicitly assumes that the function is smooth and defined also for
fractional values of
queue.setClassDependence(@(ni) min(ni(2),c));
applies a multiserver-type only to class-2 jobs, but not to the others.
It is sometimes useful to specify the statistical properties of a time
series of service or inter-arrival times, as in the case of systems
with short- and long-range dependent workloads. When the model is
stochastic, we refer to these as situations where one specifies a
process, as opposed to only specifying the distribution of the
service or inter-arrival times. In Line
processes inherit from the PointProcess
class, and include the 2-state
Markov-modulated Poisson process (MMPP2
) and empirical traces read
from files (Replayer
).
For the latter, Line assumes that
empirical traces are supplied as text files (ASCII), formatted as a
column of numbers. Once specified, the Replayer
object can be used as
any other distribution. This means that it is possible to run a
simulation of the model with the specified trace. However, analytical
solvers will require tractable distributions from the PhaseType
class.
In this section, we discuss the internal representation of the Network
objects used within the Line solvers. By
applying changes directly to this internal representation it is possible
to considerably speed up the sequential evaluation of models.
For efficiency reasons, once a user requests to solve a Network
,
Line calls internally generate a static
representation of the network structure using the refreshStruct
function. This function returns a representation object that is then
passed on to the chosen solver to parameterize the analysis.
The representation used within Line is
the NetworkStruct
class, which describes an extended multiclass
queueing network with class-switching and acyclic phase-type (APH)
service times. APH generalizes known distributions such as Coxian,
Erlang, Hyper-Exponential, and Exponential. The representation can be
obtained as follows
sn = model.getStruct()
The next tables present the properties of the NetworkStruct
class.
Table 1.2 gives the invariant properties of the
class, which specify the initial parameterization of the nodes, which we
refer to as static parameters.
Table 1.3 further details parameters that
require algorithmic calculations to derive from the static parameters.
Field | Type | Description |
---|---|---|
cdscaling |
cell |
class-dependent scaling when station |
classnames |
char |
Name of class |
classprio |
integer |
Priority of class |
connmatrix |
logical |
true if node |
dropid |
integer |
drop rule for class |
fj |
logical |
true if forked tasks from fork node |
inchain |
integer |
indexes of classes in chain |
isslc |
logical |
true if class |
isstatedep |
logical |
true if node |
isstation |
logical |
true if node |
isstateful |
logical |
true if node |
lldscaling |
double |
load-dependent scaling when station |
lst |
function handle |
Laplace-Stieltjes transform of the service or arrival distribution for class |
mu |
double |
Service or arrival rate in phase mu ${i,r}=Immediate . |
nclasses |
integer |
Number of classes in the network |
nclosedjobs |
integer |
Total number of jobs in closed classes |
njobs |
integer |
Number of jobs in class Inf for open classes) |
nnodes |
integer |
Number of nodes in the network |
nservers |
integer |
Number of servers at station |
nstations |
integer |
Number of stations in the network |
nstateful |
integer |
Number of stateful nodes in the network |
nodenames |
string |
Name of node |
nodeparam |
double |
Parameters for local variable instantiation at stateful node |
nodetype |
integer |
Type of node NodeType.Sink ) |
noutputvars |
integer |
Number of ouput section state variables for stateful node |
nvars |
integer |
Number of local state variables for stateful node nclasses +$s$ for class-$s$ routing; positions after nclasses are used for class-independent variables. |
phases |
integer |
Number of phases for service process of class |
phasessz |
integer |
Number of state vector elements used to describe phase |
phaseshift |
integer |
Position shift to read phase element in state |
proc |
cell |
Matrix representation of [^1] the class |
procid |
integer |
Service or arrival process type id at station ProcessType.ID_HYPEREXP ) |
refclass |
integer |
Index of reference class for class |
refstat |
integer |
Index of reference station for class |
routing |
integer |
Routing strategy type id for class RoutingStrategy.ID_JSQ ) |
rtorig |
double |
Probability matrix specified by the user at model definition time for class switch from class |
sched |
char |
Scheduling strategy at station SchedStrategy.PS ) |
schedid |
integer |
Scheduling strategy id at station SchedStrategy.ID_PS ) |
schedparam |
double |
Parameter for class |
sync |
struct |
Data structure specifying a synchronization |
stateprior |
double |
Prior probability for states of node |
NetworkStruct
static properties
Field | Type | Description |
---|---|---|
cap |
integer |
Total capacity at station |
chains |
logical |
true if class false otherwise |
classcap |
integer |
Maximum buffer capacity available to class |
csmask |
logical |
true if class |
nchains |
integer |
Number of chains in the network |
nodevisits |
double |
Number of visits that a job in chain |
phi |
double |
Completion probability in phase |
pie |
double |
Entry probability in phase |
rates |
double |
Service rate of class Source ) |
rt |
double |
Probability of routing from stateful node |
rtnodes |
double |
Same as rt , but |
rtfun |
function handle |
State-dependent routing table given initial (st1 ) and final (st2 ) state cell arrays. Table entries are defined as in rt . |
scv |
double |
Squared coefficient of variation of class Source ) |
space |
integer |
The |
state |
integer |
Current state of stateful node |
visits |
double |
Number of visits that a job in chain |
NetworkStruct
computed properties
For advanced nodes, such as Cache and Transition, additional parameters
are specified under the nodeparam
cell array for the corresponding
node. Table 1.4 illustrates the properties
specified within the nodeparam{i}
cell array for Transition node nodeparam{i}
array for a Cache node
Field | Type | Description |
---|---|---|
enabling |
integer |
Enabling condition for mode |
firing |
integer |
Firing outputs of class |
firingprio |
integer |
Firing priority for mode |
firingid |
integer |
Firing type at node TimingStrategy.IMMEDIATE ) |
firingphases |
integer |
Number of phases for firing process of mode |
firingproc |
cell |
Matrix representation of the mode |
firingprocid |
integer |
Firing process type id for mode ProcessType.ID_HYPEREXP ) |
fireweight |
integer |
Firing weight for mode |
inhibiting |
integer |
Inhibiting condition for mode |
modenames |
string |
Name of mode |
nmodes |
integer |
Number of modes for transition node |
nmodeservers |
integer |
Number of servers for mode |
nodeparam
Field | Type | Description |
---|---|---|
accost |
double |
Access cost for class |
hitclass |
integer |
Class switching for class |
itemcap |
integer |
Item capacity in list |
missclass |
integer |
Class switching for class |
nitems |
integer |
Number of items |
pread |
double |
Probability for class |
rpolicy |
integer |
Replacement policy id (e.g., ReplacementPolicy.ID_LRU ) |
nodeparam
As shown in the tables, internally to Line there is an explicit differentiation between properties of nodes, stations, and stateful nodes. This distinction has impact in particular over routing and class-switching mechanisms, and also allows solvers to better differentiate between different kinds of nodes.
In some cases, one may want to access some properties of nodes that are
contained in NetworkStruct
fields that are however referenced by
station or stateful node index. To help this and similar situations, the
NetworkStruct
class also provides static methods to quickly convert
the indexing of nodes, stations, and stateful nodes, which is used in
referencing its data structures:
-
nodeToStateful
-
nodeToStation
-
stationToNode
-
stationToStateful
-
statefulToNode
As an example, we can determine the portion of the nodevisits
field
that refers to stateful nodes in chain
c = 1;
V = zeros(sn.nstateful,1);
sn = model.getStruct(); % NetworkStruct object
for ind=1:sn.nnodes
if sn.isstateful(ind)
isf = sn.nodeToStateful(ind);
V(isf,1) = sn.nodevisits{c}(ind,2);
end
end
JSIMgraph is the graphical simulation environment of the JMT suite. Line can export models to this environment for visualization purposes using the command
model.jsimgView
An example is shown in
Figure [jsimgView-function] below.
Using a related function, jsimwView
, it is also possible to export the
model to the JSIMwiz environment, which offers a wizard-based interface.
Another way to debug a Line model is to transform it into a MATLAB graph object, e.g.
G = model.getGraph();
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','Layered')
plots a graph of the network topology in term of stations only. In a similar manner, the following variant of the same command shows the model in terms of nodes, which corresponds to the internal representation within Line.
[~,H] = model.getGraph();
plot(H,'EdgeLabel',H.Edges.Weight,'Layout','Layered')
The latter example is invoked by default if we type
plot(model)
which also adds automatic node coloring to highlight the class-switch nodes.
Figure 1.2 shows the difference between the
two commands for an open queueing network with two classes and
class-switching. Weights on the edges correspond to routing
probabilities. In the station topology on the left, note that since the
Sink
node is not a station, departures to the Sink
are drawn as
returns to the Source
. The node topology on the right, illustrates all
nodes, including ClassSwitch
nodes that are automatically added by
Line to apply the class-switching routing
strategy. Double arcs between nodes indicate that both classes are
routed to the destination.
getGraph
function: station topology (left) and
node topology (right) for a 2-class tandem queueing network with
class-switching.
Furthermore, the graph properties concisely summarize the key features of the network
>> G.Nodes
ans =
2x5 table
Name Type Sched Jobs ClosedClass1
________ _________________ _____ ____ ____________
'Delay' 'Delay' 'inf' 5 1
'Queue1' 'Queue' 'ps' 0 2
>> G.Edges
ans =
3x4 table
EndNodes Weight Rate Class
____________________ ______ ____ ______________
'Delay' 'Delay' 0.7 1 'ClosedClass1'
'Delay' 'Queue1' 0.3 1 'ClosedClass1'
'Queue1' 'Delay' 1 0.5 'ClosedClass1'
Here, Edge.Weight
is the routing probability between the nodes,
whereas Edge.Rate
is the service rate of the node appearing in the
first column under EndNodes
.
Line offers a number of scripts to import
external models into Network
object instances that can be analyzed
through its solvers. The available scripts are as follows:
-
JMT2LINE
imports a JMT simulation model (.jsimg
or.jsimw
file) instance. -
PMIF2LINE
imports an XML file containing a PMIF 1.0 model.
Both scripts require in input the filename and desired model name, and return a single output, e.g.,
sn = PMIF2LINE([pwd,'\\examples\\data\\PMIF\\pmif_example_closed.xml'],'Mod1')
where sn
is an instance of the Network
class.
Network
object can be saved in binary .mat
files using MATLAB’s
standard save
command. However, it is also possible to export a
textual script that will dynamically recreate the same Network
object.
For example,
example_closedModel_1; LINE2SCRIPT(model, 'script.m')
creates a new file script.m
with code
model = Network('model');
%% Block 1: nodes
node{1} = DelayStation(model, 'Delay');
node{2} = Queue(model, 'Queue1', SchedStrategy.FCFS);
%% Block 2: classes
jobclass{1} = ClosedClass(model, 'Class1', 10, node{1}, 0);
node{1}.setService(jobclass{1}, Exp.fitMean(1.000000)); % (Delay,Class1)
node{2}.setService(jobclass{1}, Exp.fitMean(1.500000)); % (Queue1,Class1)
%% Block 3: topology
P = model.initRoutingMatrix(); % initialize routing matrix
P{1,1}(1,1) = 7.000000e-01; % (Delay,Class1) -> (Delay,Class1)
P{1,1}(1,2) = 3.000000e-01; % (Delay,Class1) -> (Queue1,Class1)
P{1,1}(2,1) = 1; % (Queue1,Class1) -> (Delay,Class1)
model.link(P);
that is equivalent to the model specified in example_closedModel_1.m
.
Using the features presented in the previous section, one can create a model in JMT and automatically derive a corresponding Line script from it. For instance, the following command performs the import and translation into a script, e.g.,
LINE2SCRIPT(JMT2LINE('myModel.jsimg'),'myModel.m')
transforms and save the given JSIMgraph model into a corresponding Line model.
Line also provides two static functions
to inspect jsimg
and jsimw
files before conversion, called
SolverJMT.jsimgOpen
and SolverJMT.jsimwOpen
require as an input
parameter only the JMT file name, e.g., ’myModel.jsimg’.
It is also possible to automate the editing and import of JMT models
from MATLAB using the jsimgEdit
command. This will open an empty JMT
model and upon saving this will be automatically reimported into MATLAB.
Table 1.6 lists the JSIMgraph/JSIMwiz model
features supported by the JMT2LINE
transformation. We indicate as
“Fully” supported a feature that is supported in the import and such
that the resulting model can be solved in Line
using at least
SolverJMT
. A feature with “Partial” support implies that some core
aspects of this feature available in JSIM are not available in
Line.
A few notes are needed to clarify the entries with partial support:
-
Fork
andJoin
are supported with their default policies. Advanced policies, such as partial joins or setting a distribution for the forked tasks on each output link, are not supported yet. -
a single
Sink
and a singleSource
can be instantiated in a Line model, whereas there is no such constraint in JMT.
JMT Feature | Support | Notes |
---|---|---|
Distributions | Full | Phase-Type, Burst (MAP), Burst (MMPP2), Deterministic, Disabled, Exponential, Erlang, Gamma, Hyperexponential, Coxian, Logistic, Pareto, Uniform, Zero Service Time, Replayer, Weibull |
Classes | Full | Open class, Closed class, Class priorities |
Metrics | Full | Number of customers, Residence Time, Throughput, Response Time, Throughput per sink, Utilization, Arrival Rate |
Nodes | Full | Finite Capacity Region, ClassSwitch, Place, Delay, Logger, Queue, Router, Transition |
Routing | Full | Random, Probabilities, Round Robin, Join the Shortest Queue |
Scheduling | Full | FCFS, HOL, LCFS, LCFS-PR, SIRO (Random), SJF, SEPT, LJF, LEPT, PS, DPS, GPS |
Nodes | Partial | Fork, Join, Source, Sink |
Distributions | No | Burst (General), Normal |
Nodes | No | Scaler, Semaphore |
Routing | No | Shortest Response Time, Least Utilization, Fastest Service, Load Dependent, Class Switch Routing |
Metrics | No | Drop rate, Response time per sink, Power |
Scheduling | No | Polling, LPS, EDD, EDF, TBS, SRPT |
Mechanisms | No | Load Dependence, Retrial, Impatience, Setup times, Deadlines |
Supported JSIM features for automated model import and analysis
[^1]: For Markovian distributions, this follows the standard