Jump label

Service navigation

Main navigation

You are here:

Main content

Research

 

Research Areas

 

 

Quantitative Models: Specification and Analysis

PE-Tools: Development and Usage

On the combination of PE and other evaluation techniques

Computer Networks and Distributed Systems

 

 

Traditionally the main interest of Informatik IV is in a methodology and techniques for the performance evaluation (PE) of computer and communication systems. The key results of our work concern a model-based performance evaluation which comprises the specification and analysis of quantitative models, development and implementation of corresponding tools, and their pratical use. Furthermore the integration of other formalisms and system properties (dependability, functional correctness) were examined recently.

 

Quantitative Models: Specification and Analysis

 

Stochastic discrete-event models are used for the PE of systems. The specification of such a model comprises the description of a (discrete) state space and the (stochastic) state transition rules. Techniques for their analysis can be separated into three broad categories: ``algebraic'', ``numeric'' and ``simulative''.

 

Markov processes form the theoretical basis for algebraical and numerical techniques. Algebraic models are often specified using Queueing Networks, since they provide an explicit and very efficient solution (``product-form solution'') for a large subclass (``product-form nets''). In this field we were able to improve exact algorithms for product-form nets and approximative techniques for nearly product-form nets significantly. Markov processes without an explicit solution, described e.g. by Extended QNs or Stochastic Petri nets, can be solved using numerial techniques. In theory ``only'' a system of linear equations has to be solved. In practice the number of equations, being given by the number of model states, might become huge. Using modern linear algebra techniques we were able to develop solution techniques for huge models which consist of 2-3 million states using standard workstations. The main idea is to use a hierarchically specified model, which is always recommended in system design and to exploit the hierarchical structure for solution purposes.

 

Decomposition and aggregation are further techniques leading to more efficient solution algorithms. The basic idea is to determine a simple, similar behaving substitute for a specific model part. This leads to approximative results which can be determined very efficiently. We were able to extend these techniques significantly by constructing aggregates for non product-form subnets using numerical and/or simulative techniques. This results in models with a tremendously reduced aggregation error.

 

top

 

PE-Tools: Development and Usage

 

Parallel to our methodological work we continuously developed and used PE-Tools. Their intention is to provide facilities for a model description close to the original system specification and hiding details of the analysis techniques. Such tools map the model specification automatically to an analysable model. The set of tools developed by Informatik IV comprises amongst others

 

  • HIT, a modelling environment which supports the specification of modular and hierarchical descriptions of especially large and complex models. The analysis techniques provided by HIT include simulation and a large variety of exact and approximative, analytical and numerical techniques.

  • MACOM, using extended queueing network models for the performance analysis of communication systems. These models are mapped onto a Markov chain for numerical analysis or simulative techniques are applied.

  • HiQPN-Tool supporting the analysis of hierarchical QPN models, a superset of Coloured GSPNs and Queueing Networks. These models can be analysed with respect to qualitative and quantitative aspects.

 

All tools provide a graphical user interface and are available for usual type of workstations. They are tested exhaustively and have been employed for the evaluation of operating systems in the development phase, future hardware architectures, and the assessment of distributed and telecommunication systems. The tools also suit for an evaluation of flexible manufacturing systems. Their practical usability has been proved by a large number of external installations in universities, research institutes and industry.

 

top

 

On the combination of PE and other evaluation techniques

 

Methods for a combined evaluation of functional and performance aspects are getting more and more important in the field of performability, and fault-tolerant and distributed systems.

 

In performability models the rates between events concerning the normal system operations and the occurrence of error indicating events normally differ several orders of magnitude. Thus applying aggregation techniques seems to be very promising. We were able to obtain good approximation results in this field and furthermore developed efficient approximative product form solvers for special problem classes.

 

The analysis of functional aspects is supported by several formalisms like e.g. Petri nets, process algebras and finite state machines, and in a more user friendly form by formal specification languages as SDL and Estelle. All these formalisms usually do not support the analysis of performance aspects, thus forcing the user to devise a further model of his system for that purpose. To avoid consistency problems we investigated combinations of functional and performance modelling formalisms. Stochastic Petri nets were enriched by elements from queueing networks facilitating the model description. Efficient analysis techniques of the Petri net area can then be used for a preanalysis of the stochastic model. These results have been integrated in a modelling tool (HiQPN-Tool) with a graphical user interface. In the same spirit we combined also other PE and formal description techniques. Especially results for the performance evaluation of SDL specifications using the PE tool HIT are available.

 

top

 

Computer Networks and Distributed Systems

 

Modern computer networks combine worldwide communication facilities with local information bases and processing functions in order to support powerful distributed application systems. Central topics of our practical research work are the logical architectures of applications, underlying computer networks, and telecommunication systems as well as suitable hard/software structures for their implementation. In this context, we study the application of formal methods for the functional modelling and specification of event-discrete systems. Tools are provided supporting the computer-assisted productive development of high-quality systems.

 

With respect to the modelling by extended communicating finite state machines, reachability graph based analysis tools are applied in the development process of communication software. So, in cooperation with a manufacturer of communication systems, a logical protocol stack has been analysed and its high-performance implementation combining activity-thread and server architectures has been verified.

 

With respect to more general state transition system models, the TLA-project resorts to L. Lamport's approach 'Temporal Logic of Actions'. Construction tools (e.g., syntax-directed editor, browser, parser, interpreter, visualisation and animation) and verification tools (e.g., frontends to predicate logic theorem provers, on-the-fly model checker for safety and liveness properties) are under study. At present they are adapted to a compositional TLA specification style which supports the modular description and decompositional verification of process systems. Currently the style is used for the modelling of flexible application-driven configurations of high-speed transfer protocols. Secondly, an approach for the tool-assisted construction of distributed applications is based on the style.

 

 

Our research focuses on:

 

 

Forschung

  • network protocols:

    • specification, verification, and efficient implementation,

  • distributed applications:

    • computer-assisted quality-assured development,
    • configuration and management of distributed applications,

  • integrated network and system management:

    • policy- and model-based automation of technical management tasks,

  • security of networks and distributed systems:

    • tool-assisted security-analysis,
    • trust-adapted security policy enforcement,
    • automated security management.


 

Recent developments enclose the modular formal specification technique cTLA, a technique translating state-machine-models to efficient implementations of network protocols, control wrappers interacting with trust information services in order to secure component-structured applications, the approach of object-oriented security analysis, the automated management approach model-based management (MBM), and the Web Services server implementation Java Multi Edition DPWS Stack (JMEDS).

 

Model-based Service Configuration

 

 

The MBM approach is an extension of the so-called policy-based technical network, system and application management. MBM provides the refinement of abstract high-level policy definitions into configuration descriptions and executable management rules. Its application is supported by the tool MoBaSeC (model-based service configuration) and a run-time management system. The tool performs the interactive graphical modelling of management policies and system structures. Moreover, it translates representations of abstract policies into low-level policies which are automatically enforced by the management system at runtime. The MBM approach has successfully been applied for the configuration of security services and protection mechanisms of networked systems as well as for the technical management of distributed service systems including general configuration, fault, performance, security and account management.

 

 

Device Profile for Web Services

 

The JMEDS DPWS server implementation supports the light-weight implementation of service systems by means of resource-restricted devices and embedded systems. The implementation is Java-based and suitable for the Micro Java Edition. It is compliant with the OASIS standard Devices Profile for Web Services (DPWS).

 

MBM and JMEDS have been developed in close cooperation together with the industrial partner MATERNA, Dortmund. Both approaches will be applied in the project OSAMI, where JMEDS will be adapted to OSGi environments and support the interactions between distributed devices. MBM will form the basis of policy-controlled self-management functions which will support the adaptation of device-based service systems to changing conditions, user needs and environments.

 

 

top