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.