Programme leader: A. Hordijk, J. Wessels
The research in this programme is on stochastic networks (sn).
Stochastic networks are networks of entities, with particles residing in
and moving between these entities according to stochastic processes. A
key example is a queueing network, where the entities are service
facilities and the particles customers.
In the design of computer-, communication-, and manufactoring systems, the most important criterion presently is quality of service, which is expressed in terms of performance and reliability of the systems in relation to their applications. Stochastic networks provide the mathematical models for the description and analysis of these systems.
Due to exciting breakthroughs, the theory of sn is going through a period of feverish activity.
The programme contains all main research themes on the key elements:
modelling, stability, traffic processes, performance analysis, and
control.
The already existing cooperation within this programme will be
intensified and extended through a SWON-project, in which the research
groups of Boxma (CWI), Hordijk (RUL), De Smit (UT), Tijms (VUA) and
Wessels (TUE) participate. These groups have partly complementary,
partly overlapping expertise in the main mathematical techniques to
analyse sn: queueing theory, Markov decision chains, reliability theory,
algorithmic probability, and stochastic simulation.
Research performed at CWI in Stochastic Operations Research contains:
queueing theory; Markov decision processes;
performance analysis and control of computer and communication networks;
reliability and availability of stochastic networks.
Performance analysis of ATM networks
Asynchronous Transfer Mode (ATM) networks are the new generation high
speed communication systems. Research has been done to how traffic
streams change due to interference with other traffic streams, when
they flow through the network. Furthermore, fluid flow analyses are
done for traffic shapers (buffers at the edge of the network which are
used for spreading out data bursts).
Real-time database systems
The aim of the project on real-time databases is to achieve that the
real-time performance of a database system can already be judged in the
design phase, so that later disappointment can be prevented.
The performance measure for a real-time database is the percentage of
transactions that meets its deadline. This percentage can be increased
by allowing transactions to be executed in parallel. However, then a
transaction scheduler is needed to preserve the consistency of the
database.
Two schedulers, Single Queue Static Locking and Optimistic Concurrency
Control, are analysed using stochastic models. The result for both
schedulers is a good approximation for the transaction response time
distribution, and thus also for the probability that a transaction meets its
deadline.
Anticipative and adaptive planning with neural networks
In this project it is explored how useful neural nets can be as
decision support tool in lot-sizing problems under uncertainty.
The approach chosen exploits results about regeneration points by
making a detailed plan until the next regeneration point. The first
problem is then solved by a neural net and the second by an algorithmic
method. This hybrid approach seems to combine the strengths of neural
and algorithmic computing.
Markovian queueing systems
Many problems in the area of production control lead to the study of multi-dimensional Markovian queueing models. For the exact solution of such models we developed a compensation approach. This approach has been succesfully applied to a number of queueing problems, e.g. to dynamic routing problems and multi-server non-exponential systems. In the future the scope of this approach will be further investigated. We also developed a Markov reward technique to establish bounds for the performance of systems which are hard to analyse exactly. This approach has been applied to queueing models for e.g. a maintance facility and a repair shop. Further approximate techniques have been developed for the analysis of periodic production processes.