University of Bradford
Department of Computing
 

The Computer Systems Modelling Research Group



 

  • PURPOSE AND OBJECTIVES A research group in Computer Systems Modelling (CSM), Dept. of Computing, Bradford University, has been established by Professor Demetres Kouvatsos since early 80's. The group has pioneered widespread research work relating to the performance modelling and evaluation of computer systems and communication networks. The quantitative analysis and performance prediction of these discrete flow systems are of extreme importance in view of their ever expanding usage and the multiplicity of their component parts together with the complexity of their functioning. Performance predictions are of great value in system enhancement, identifying the most cost effective means for better resource utilisation without recourse to time consuming and expensive experimentation which may require exclusive use of the actual system. However, they are even more valuable during system design and development stages, where experimentation is no longer an option and careful performance modelling and analysis provide crucial guidance to the network designer.
    • Queueing network models, probabilistic models, queueing theory and stochastic processes have been used extensively in our work as powerful and realistic tools for representing computer and communication systems and analysing their performance. The main objective of the CSM research group has been to establish integrated research into the performance modelling and optimisation of computer systems and communication with particular emphasis on
  • the creation of novel analytic methodologies and the derivation of exact and approximate quantitative results
  • the development of cost - effective algorithms, software tools and model validation procedures.
  • ACHIEVEMENTS
  • METHODOLOGIES Over the years, our research has led to the establishment of a novel analytic methodologies for the formulation and solution of probabilistic models (PMs) and queueing network models (QNMs) of computer systems and communication networks. These methodologies are summarised below:
  • Higherarchical decomposition of complex design problems, based on PMs and the information theoretic concept of entropy functional (EF)
  • Node-by-node decomposition of arbitrary QNMs, based on queueing theoretic (QT) concepts and the probability inference method of entropy maximisation (ME)
  • Multilevel hierarchical aggregation of arbitrary QNMs, based on QT concepts and the principle of minimum relative entropy (MRE)
  • Approximate analysis of general QNMs of computer subsystems, based on PMs, QT concepts and the principle of ME
  • Approximate analysis of complex queueing models evolving in randomly changing environments, based on an asymptotic approximation technique (AAT) from Reliability Theory
  • Exact analysis of complex queueing models with correlated and bursty traffic, based on QT concepts and batch renewal processes (BRPs)
  • QUANTITATIVE RESULTS AND SOLUTION ALGORITHMS New performance evaluation results and cost-effective algorithms have been derived, based on the aforementioned methodologies, for the quantitative (exact and approximate) analysis of PMs and QNMs of computer systems and packet-switched communication networks. Product-form approximations have been characterised and closed-form metrics have been determined for throughputs, response-time and queue length distributions, end-end delays, loss and blocking probabilities, flow control and buffer management estimates etc. Highlights of our research are summarised below:
    • ME and MRE analysis of general continuous-time QNMs of multi- programmed/multiprocessor computer systems and packet-switched communication networks [1-11]
    The work is based on ME and MRE approximation algorithms for arbitrary QNMs, based on either node-by-node decomposition or multilevel hierarchical aggregation, respectively, subject to QT fully decomposable subset and aggregate mean value constraints. QNMs under investigation include arbitrary topologies, random and dynamic routing, multiple classes/chains of jobs (packets), multiple or infinite server stations, general independent interarrival and service (transmission) times, mixed (priority/non priority) scheduling disciplines, buffer management policies, infinite capacity stations or finite capacity stations with repetitive-service (RS) blocking and flow control mechanisms. Some of the quantitative results and solution algorithms are also applicable to the performance evaluation of flexible manufacturing and production systems and road traffic networks.
    Probabilistic analysis and ME approximations for QNMs of computer subsystems of user - resource subnetworks[12-14]
    The work is based on PMs, QT concepts and ME algorithms for complex QNMs involving complex Input/Output (I/O) subsystems (missed reconnection probabilities etc.), computer systems with variable concurrent programming structures and synchronisation and concurrency control algorithms for centralised and distributed database systems (transaction conflict probabilities etc).
    Asymptotic approximation analysis of complex continuous-time queueing models with finite capacity representing multiprocessor systems and also multi-buffered Asynchronous Transfer Mode (ATM) switch architectures evolving in randomly changing environments [15-17]
    The work is based on the AAT (from Reliability theory). This is a most appropriate technique when a sudden unpredictable alteration of system usage intensity due to an external phenomenon (e.g., crashing a switching exchange mode) is taken into account by adapting access and transmission rates to respond to randomly occurring fluctuations.
    Exact BRPs analysis and ME approximations for general continuous-time and discrete-time QNMs of ATM switch architectures and networks (with or without correlated traffic) [18-34]
    The work is based on the principle of ME, QT concepts and BRPs. New quantitative results and closed-form expressions (e.g., cell-loss probabilities, queue length and waiting time distributions, end-to-end delays etc.) and also cost effective solution algorithms have been derived including exact closed-form solutions for general discrete-time queues with single/multiple job classes and space priorities, arbitrary discrete-time QNMs with or without blocking, ATM correlated and bursty traffic characterisation (based on indices of dispersion of covariances and BRPs), queueing models of ATM switches and networks, based on multi-buffered, shared buffer and space division (Banyan interconnection networks) switch architectures with bursty/correlated arrivals, and ATM policing mechanisms. As a by product of this investigation, discrete-time queueing models have also been applied towards the performance modelling of unfairness issues in DQDB (Dual Queue Dual Bus) networks with bursty arrivals. A collaborative agreement is under way with Telematics International who are strongly interested in the emerging B-ISDN networks based on ATM technology.
    Validation procedures and software tools
    Rigorous validation of all approximation algorithms have been under-taken against exact numerical solutions and also simulation tests using the Queueing Network Analysis Package QNAP-2, as appropriate. Bottleneck analysis has also been conducted and performance bounds based on extremal distributions have been experimentally defined. A universal ME interactive package (UMEP), incorporating the source code of all solution algorithms for general queueing networks has been developed by the Computer System Modelling Group, Bradford University.
  • CURRENT RESEARCH Our current research is extended towards the performance modelling, prediction and optimisation of Broadband Integrated Services Digital Networks (B-ISDNs), based on ATM technology.

    •  

     

    Earlier established methodologies based on:

  • ME and MRE principles
  • Classical queueing theory
  • Asymptotic analysis
  • Batch renewal processes
    • together with alternative techniques based on:
  • Notion of queueing networks with 'negative' customers
  • Methods from Statistical mechanisms
  • Conservation laws
    • will be applied for the modelling, characterisation and cost-effective analysis of:
  • ATM traffic in the interior of the network, superposition of bursty and correlated arrival processes, optimal routing and flow control
  • Discrete-time queueing models of complex ATM switch architectures and networks including space division, shared buffer and shared medium switches
  • ATM design options, subject to performance and quality of service (QoS) constraints
  • Software performance engineering issues (including client-server systems), distributed database concurrency control mechanisms and service scheduling based on polling systems within an ATM environment
  • Model validation procedures, software tools and experimentation in commercially relevant case studies of multimedia applications.
  • SPONSORSHIPS/RESOURCES Since mid 80's our research work has been supported by several EPSRC (formerly SERC) research grants, industrial grants and other sponsorships. Some of the latest support include:
  • SERC (UK) support grant "GR/F/29271" (Communications and Distributed Systems Subcommittee of the Systems Architecture Committee). "General Queueing Network Models of Computer Communication Networks" 1989 - 1992 (£59,610).
  • SERC (UK) support grant "GR/H/18609" (Communications and Distributed Systems Subcommittee of Systems Architecture Committee.) "Performance Modelling and Analysis of ATM Networks" 1992-1995 (£87,777).
  • SERC CASE Award (UK) (in conjunction with General Post Office (UK)) "Performance Modelling of ATM Networks" 1992-1995 (£17,000).
  • COMDISCO Systems Ltd. (UK Branch) support "BoNes" Designer Performance Analysis Package, 1994 (~ £30,000)
  • EPSRC (UK) joint (D. Kouvatsos, Principal Investigator, Bradford University, and P. Harrison, Co-Investigator, Imperial College) support grant "GR/K/67809" (Communications and Distributed Systems Subcommittee of Systems Architecture Committee). "Performance Modelling and Evaluation of B-ISDNs" , 1995 -1998 (~£260,00, Bradford's share ~ £135,575).
  • INDUSTRIAL LINKS/CONTRACTS Industrial connections have been established with Telematics International and Skelton Technology Ltd., in association with the EPSRC research grants GR/F29271, GR/H18609 and GR/K67809. Research collaboration are under negotiation on an investigation of performance evaluation of ATM networks and product development.
  • NATIONAL/INTERNATIONAL CONNECTIONS Over the years we have maintained strong links with the Performance Engineering Group of the British Computer Society and other industrial and academic establishments at home and abroad. More recently, a research partnership has been established with the Imperial College and Telematics International via a joint EPSRC research grant. Currently, the group is a member of a European Consortium on long term research and the Performance Analysis of High Speed Networks. The Consortium involves:
  • Universities of Pisa and Bologna, and Research Institute CNUCE, Italy.
  • National and Technical University of Athens, Greece.
  • University of Amsterdam, Holland and
  • Imperial College and Bradford University, UK and
  • Skelton Technology Limited, UK and Telematics International, UK, both under advisory capacity.
  • CURRENT MEMBERS OF THE GROUP The CSM research group is currently headed by Professor Kouvatsos. Other Internal members of the group include:
  • Mr R.J. Fretwell (Research Assistant)
  • Dr C. Skianis (Research Assistant)
  • Dr I. Awan
  • Mr G. Dimakopoulos (Research Student)
  • Mr K. Smith (Research Student)
  • Mr V. Tsiantos (Research Student)
  • Mr V. Velentzas (Research Student)

    • IFIP ATM and IP 2000 Workshop

    Publications



    Authors:         D.Kouvatsos, C.Skianis, G.Dimakopoulos
    Last update:  27/11/97