A DEVS LIBRARY FOR LAYERED QUEUING NETWORKS
Dorin B. Petriu and Gabriel Wainer
Department of Systems and Computer Engineering
Carleton University, 1125 Colonel By Drive
Ottawa, Ontario K1S 5B6, Canada.
{dorin | gwainer}@sce.carleton.ca
ABSTRACT
The DEVS formalism is a modeling and simulation framework
with well-defined concepts for coupling components and the
construction of hierarchical modular models. Different
formalisms, including Petri Nets, PDE, and state machines,
have been mapped into DEVS. In this paper, a Layered
Queuing Network (LQN) library is developed and mapped into
DEVS using the CD++ toolkit. LQNs are used for performance
analysis of software systems. LQNs can model multilayer
client-server applications, and as such they can be used to
detect performance bottlenecks and deadlocks in both software
and hardware. This paper shows how to build LQNs as DEVS
models, thus integrating between the two kinds of models, and
providing a framework for defining complex models through
the use of multiformalism modeling.
Keywords: DEVS, LQN, CD++, multiformalism model,
performance analysis
1. INTRODUCTION
The DEVS formalism [1] is a discrete-event modeling
specification mechanism based on systems theory, which
supports the definition of hierarchical modular models that can
be easily reused.
DEVS hierarchical constructions enable multi-formalism
modeling; that is, the coupling of and transformation between
models described in different formalisms. Using different
formalisms to represent systems enables a modeler to choose
the best formalism for each sub-system. The CD++ [2] tool
allows the user to implement DEVS models. CD++ is built as a
hierarchy of models, each related to a simulation entity. Atomic
models can be programmed in C++. A specification language
exists for defining a model's interfaces to other models and for
defining a model’s initial values and external events. The tool
also enables a user to build models using graph-based
notations, which allows for a more abstract visualization of the
problem, as well as for the definition of cellular models. In the
long term, the goal is to provide users with a set of libraries to
develop complex models based on multiformalisms. There
already are libraries for Finite State Automata, Petri Nets,
DEVS graphs, and DEVS atomic models written in C++.
In this work we show how to define Layered Queuing
Networks (LQNs) [3, 4] in a DEVS environment. LQNs are
built as client/server models that triggered by discrete events.
They are provided with modular entry points and the layered
definition permits hierarchical construction. This paper shows
that the mapping of LQNs into DEVS models is
straightforward.
2. BACKGROUND
A real system modeled with DEVS is described as a
composite of submodels, each of them being behavioral
(atomic) or structural (coupled).
A DEVS atomic model is formally described by:
M = < X, S, Y, dint, dext, l, D >
where X is the input events set; S is the state set; Y is the output
events set; dint is the internal transition function; dext is the
external transition function; l is the output function; and D is
the duration function. Each model is provided with an interface
consisting of input and output ports to communicate with other
models. Input external events (those events received from other
models) are collected in input ports. The external transition
function specifies how to react to those inputs. The internal
transition function is activated after a period defined by the
time advance function. The goal is to produce internal state
changes. Model execution results are spread through output
ports. This is done by the output function, which executes
before any internal transition
A DEVS coupled model is composed of several atomic or
coupled submodels. They are formally defined as:
CM = < X, Y, D, {Mi}, {Ii}, {Zij} >
where X is the set of input events; Y is the set of output
events; D is an index for the components of the coupled model,
and " i ΠD, Mi is a basic DEVS (that is, an atomic or coupled
model), Ii is the set of influencees of model i (that is, the
models that can be influenced by outputs of model i), and " j Œ
Ii, Zij is the i to j translation function.
Queuing Networks are based on a customer-server
paradigm: customers request service to servers, which queue
the requests until they can be serviced. Traditional Queuing
Networks model only a single layer of customer-server
relationships. LQNs allow for an arbitrary number of clientserver
levels. LQNs can model intermediate software servers,
and be used to detect software deadlocks and software as well
as hardware performance bottlenecks [5]. The layered aspect of
LQNs makes them very suitable for evaluating the performance
of distributed systems [6, 7].
LQNs model both software and hardware resources. The
basic software resource is a task, which represents any software
object having its own thread of execution. Tasks have entries
that act as service access points. The basic hardware resource is
a device. Typical devices are CPUs and disks [8]. Figure 1
shows the visual notation used for tasks, entries, and devices.
.....