OpenUCT :: Browsing by Author "Kritzinger, Pieter S"

Browsing by Author "Kritzinger, Pieter S"

Now showing 1 - 20 of 24

Open Access
Analytical performance evaluation of concurrent communicating systems using SLD and stochastic Petri nets
(1997) Kabutz, Heinz Max; Kritzinger, Pieter S
In this thesis, the performance analysis of SDL with a new type of stochastic Petri net is described. This new net is called SDL-net. The Concurrent Communicating System is described, and the need for qualitative and quantitative analysis of such systems is motivated. Formal methods are demonstrated which can be used to represent such Concurrent Communicating Systems. The Specification and Description Language (SDL) is shown in the context of Concurrent Communicating Systems and the software development cycle is described for SDL systems. Correctness and performance of SDL are discussed and it is shown how the semantics of time for performance can be introduced into SDL by adding external information, by extending the SDL syntax or by using compiler directives. In this thesis only external information is added.
Open Access
Bisimulation as a verification and validation technique for message sequence charts
(1998) Wall, Philip Gerhard; Kritzinger, Pieter S
The complexity of determining whether a system meets the requirements of its designers has increased with the widespread use of real time concurrent systems. This testing process has however been simplified with the emergence of Formal Description Techniques. FDTs not only provide the means for formally specifying a system, but also supply the theoretical basis for conformance testing. One such FDT is Message Sequence Charts(MSCs). MSCs have evolved out of the need to describe the inter-process flow of communication in a concise, easily understood, graphical format. MSCs originally took the form of system traces, but with the development of, and additions to the specification, the 1996 MSC specification now provides a comprehensive description technique. An FDT is of little use, unless it can be used in the validation and verification of a system specification. In the case of MSCs, this has usually involved the testing of a trace against a specification. Formal specification with MSCs has however provided the opportunity of testing the equivalence of MSC specifications.
Open Access
The complexity of Petri net transformations
(1993) Donaldson, Stephen Richard; Kritzinger, Pieter S
This study investigates the complexity of various reduction and synthesis Petri net transformations. Transformations that preserve liveness and boundedness are considered. Liveness and boundedness are possibly the two most important properties in the analysis of Petri nets. Unfortunately, although decidable, determining such properties is intractable in the general Petri net. The thesis shows that the complexity of these properties imposes limitations on the power of any reduction transformations to solve the problems of liveness and boundedness. Reduction transformations and synthesis transformations from the literature are analysed from an algorithmic point of view and their complexity established. Many problems regarding the applicability of the transformations are shown to be intractable. For reduction transformations this confirms the limitations of such transformations on the general Petri net. The thesis suggests that synthesis transformations may enjoy better success than reduction transformations, and because of problems establishing suitable goals, synthesis transformations are best suited to interactive environments. The complexity of complete reducibility, by reduction transformation, of certain classes of Petri nets, as proposed in the literature, is also investigated in this thesis. It is concluded that these transformations are tractable and that reduction transformation theory can provide insight into the analysis of liveness and boundedness problems, particularly in subclasses of Petri nets.
Open Access
Cross-layer RaCM design for vertically integrated wireless networks
(2010) Pileggi, Paolo P; Kritzinger, Pieter S
Wireless local and metropolitan area network (WLAN/WMAN) technologies, more specifically IEEE 802.11 (or wireless fidelity, WiFi) and IEEE 802.16 (or wireless interoperability for microwave access, WiMAX), are well-suited to enterprise networking since wireless offers the advantages of rapid deployment in places that are difficult to wire. However, these networking standards are relatively young with respect to their traditional mature high-speed low-latency fixed-line networking counterparts. It is more challenging for the network provider to supply the necessary quality of service (QoS) to support the variety of existing multimedia services over wireless technology. Wireless communication is also unreliable in nature, making the provisioning of agreed QoS even more challenging. Considering the advantages and disadvantages, wireless networks prove well-suited to connecting rural areas to the Internet or as a networking solution for areas that are difficult to wire. The focus of this study specifically pertains to IEEE 802.16 and the part it plays in an IEEE vertically integrated wireless Internet (WIN): IEEE 802.16 is a wireless broadband backhaul technology, capable of connecting local area networks (LANs), wireless or fixed-line, to the Internet via a high-speed fixed-line link.
Open Access
Distributed analysis of Markov chains
(1998) Mestern, Mark Andrew; Kritzinger, Pieter S
This thesis examines how parallel and distributed algorithms can increase the power of techniques for correctness and performance analysis of concurrent systems. The systems in question are state transition systems from which Markov chains can be derived. Both phases of the analysis pipeline are considered: state space generation from a state transition model to form the Markov chain and ﬁnding performance information by solving the steady state equations of the Markov Chain. The state transition models are speciﬁed in a general interface language which can describe any Markovian process. The models are not tied to a speciﬁc modelling formalism, but common formal description techniques such as generalised stochastic Petri nets and queuing networks can generate these models. Tools for Markov chain analysis face the problem of state Spaces that are so large that they exceed the memory and processing power of a single workstation. This problem is attacked with methods to reduce memory usage, and by dividing the problem between several workstations. A distributed state space generation algorithm was designed and implemented for a local area network of workstations. The state space generation algorithm also includes a probabilistic dynamic hash compaction technique for storing state hash tables, which dramatically reduces memory consumption.- Numerical solution methods for Markov chains are surveyed and two iterative methods, BiCG and BiCGSTAB, were chosen for a parallel implementation to show that this stage of analysis also beneﬁts from a distributed approach. The results from the distributed generation algorithm show a good speed up of the state space generation phase and that the method makes the generation of larger state spaces possible. The distributed methods for the steady state solution also allow larger models to be analysed, but the heavy communications load on the network prevents improved execution time.
Open Access
An Estelle compiler
(1988) Van Dijk, Jacques; Kritzinger, Pieter S
The increasing development and use of computer networks has necessitated international standards to be defined. Central to the standardization efforts is the concept of a Formal Description Technique (FDT) which is used to provide a definition medium for communication protocols and services. This document describes the design and implementation of one of the few existing compilers for the one such FDT, the language "Estelle" ([ISO85], [ISO86], [ISO87]).
Open Access
Generalised Markovian analysis of timed transition systems
(1996) Knottenbelt, William John; Kritzinger, Pieter S
This dissertation concerns. analytical methods for assessing the performance of concurrent systems. More specifically, it focuses on the efficient generation and solution of large Markov chains which are derived from models of unrestricted timed transition systems. Timed transition systems may be described using several high-level formalisms, including Generalised Stochastic Petri nets, queueing networks and Queueing Petri nets. A system modelled with one of these formalisms may be mapped onto a Markov chain through a process known as state space generation. The Markov chain thus generated can then be solved for its steady-state distribution by numerically determining the solution to a large set of sparse linear equations known as the steady-state equations. Existing techniques of state space generation are surveyed and a new space-saving probabilistic dynamic state management technique is proposed and analysed in terms of its reliability and space complexity. State space reduction techniques involving on-the-fly elimination of vanishing states are also considered. Linear equation solvers suitable for solving large sparse sets of linear equations are surveyed, including direct methods, classical iterative methods, Krylov Subspace techniques and decomposition-based techniques. Emphasis is placed on Krylov subspace techniques and the Aggregation-Isolation technique, which is a recent decomposition-based algorithm applicable to solving general Markov chains. Since Markov chains derived from real life models may have very large state spaces, it is desirable to automate the performance analysis sequence. Consequently, the new state management technique and several linear equation solvers have been implemented in the Markov chain analyser DNAmaca. DNAmaca accepts a high-level model description of a timed transition system, generates the state space, derives and solves the steady-state equations and produces performance statistics. DNAmaca is described in detail and examples of timed transition systems which have been analysed with DNAmaca are presented.
Open Access
A graphical representation for the formal description technique Estelle
(1998) Templemore-Finlayson, Justin George; Kritzinger, Pieter S
This dissertation concerns the specification and description of complex communicating systems using Formal Description Techniques. Specifically, we propose a standard graphical representation for the Formal Description Technique Estelle and present a prototype editor based on this representation. Together they integrate the new graphical representation with existing Estelle textual tools to create a powerful graphical design technique for Estelle. The perennial popularity of graphical techniques, combined with recent advances in computer graphics hardware and software which enable their effective application in a computing environment, provide a double impetus for the development of a graphical representation for Estelle. Most importantly, a graphical technique is more easily read and understood by humans, and can better describe the complex structure and inter-relationships of components of concurrent communicating systems. Modern graphical technology also presents a number of opportunities, separate from the specification method, such as hyperlinking, multiple windows and hiding of detail, which enrich the graphical technique. The prototype editor makes use of these opportunities to provide the protocol engineer with an advanced interface which actively supports the protocol design process to improve the quality of design. The editor also implements translations between the graphical representation and the standard Estelle textual representation, on the one hand allowing the graphical interpretation to be applied to existing textual specifications, and on the other, the application of existing text-based processing tools to a graphical specification description.
Open Access
A hardware testbed for measuring IEEE 802.11g DCF performance
(2009) Symington, Andrew; Kritzinger, Pieter S
The Distributed Coordination Function (DCF) is the oldest and most widely-used IEEE 802.11 contention-based channel access control protocol. DCF adds a significant amount of overhead in the form of preambles, frame headers, randomised binary exponential back-off and inter-frame spaces. Having accurate and verified performance models for DCF is thus integral to understanding the performance of IEEE 802.11 as a whole. In this document DCF performance is measured subject to two different workload models using an IEEE 802.11g test bed. Bianchi proposed the first accurate analytic model for measuring the performance of DCF. The model calculates normalised aggregate throughput as a function of the number of stations contending for channel access. The model also makes a number of assumptions about the system, including saturation conditions (all stations have a fixed-length packet to send at all times), full-connectivity between stations, constant collision probability and perfect channel conditions. Many authors have extended Bianchi's machine model to correct certain inconsistencies with the standard, while very few have considered alternative workload models. Owing to the complexities associated with prototyping, most models are verified against simulations and not experimentally using a test bed. In addition to a saturation model we considered a more realistic workload model representing wireless Internet traffic. Producing a stochastic model for such a workload was a challenging task, as usage patterns change significantly between users and over time.
Open Access
Improving requirements engineering : an enhanced requirements modelling and analysis method
(2005) Ryndina, Ksenia; Kritzinger, Pieter S
Open Access
Investigating cost effective communication alternatives for geographically hostile regions
(2001) Yavwa, Yakomba; Kritzinger, Pieter S
The lack of communication facilities in developing countries is a constraint to social, political and economic empowerment of the people. However, advances in technology promise to deliver voice, video and data communication services, that are urgently needed, under a common packet switched communication network. Using Zambia as a case study, the cost effectiveness of three design scenarios which involve a hybrid of radio and microwave, radio and satellite, and radio and optic fibre were evaluated. The communication links in each scenario were modelled as E1 trunks. The cost of establishing these links was determined. Each scenario was then subjected to generic input traffic patterns using a multiclass queueing network analysis model to determine its effectiveness. Our findings show that the scenario involving the microwave links as inter-regional links has the lowest cost. The second is the scenario involving satellite inter-regional links and the most expensive is the scenario involving optic fibre inter-regional links. Furthermore, the microwave- radio hybrid scenario was found to have the smallest cost-effectiveness ratio of 17.9 followed by the optic fibre-radio scenario with 20.3 and finally the satellite-radio scenario with 892.9. These results effectively imply that the microwave-radio hybrid scenario is a better option for developing countries.
Open Access
A methodology for analyzing power consumption in wireless communication systems
(2004) Chibesakunda, Mwelwa K; Kritzinger, Pieter S
Engergy usage has become an important issue in wireless communication systems. The energy-intensive nature of wireless communication has spurred concern over how best systems can make the most use of this non-renewable resource. Research energy-efficient design of wireless communication systems show that one of its challenges is that the over-all performance of the system depends, in a coupled way, on the different submodules of the system i.e. antenna, power amplifier, modulation, error control coding, and network architecture. Network architecture implementation strategies offer protocol software implementors an opportunity of incorporating low-power strategies into the design of the network protocols used for data communication.
Open Access
Model driven communication protocol engineering and simulation based performance analysis using UML 2.0
(2004) De Wet, Nico; Kritzinger, Pieter S
The automated functional and performance analysis of communication systems specified with some Formal Description Technique has long been the goal of telecommunication engineers. In the past SDL and Petri nets have been the most popular FDT's for the purpose. With the growth in popularity of UML the most obvious question to ask is whether one can translate one or more UML diagrams describing a system to a performance model. Until the advent of UML 2.0, that has been an impossible task since the semantics were not clear. Even though the UML semantics are still not clear for the purpose, with UML 2.0 now released and using ITU recommendation Z.109, we describe in this dissertation a methodology and tool called proSPEX (protocol Software Performance Engineering using XMI), for the design and performance analysis of communication protocols specified with UML.
Open Access
Modelling adaptive routing in Wide Area Networks
(1991) Hutchison, Andrew; Kritzinger, Pieter S
This study investigates the modelling of adative routing algorithms with specific reference to the algorithm of an existing Wide Area Network (WAN). Packets in the network are routed at each node on the basis of routing tables which contain internal and external delays for each route from the node. The internal delay on a route represents the time that packets queued for transmission will have to wait before being transmitted, while the external delay on a route represents the delay to other nodes via that route. Several modelling methods are investigated and compared for the purpose of identifying the most appropriate and applicable technique. A model of routing in the WAN using an analytic technique is described. The hypothesis of this study is that dynamic routing can be modelled as a sequence of models exhibiting fixed routing. The modelling rationale is that a series of analytic models is run and solved. The routing algorithm of the WAN studied is such that, if viewed at any time instant, the network is one with static routing and no buffer overflow. This characteristic, together with a real time modelling requirement, influences the modelling technique which is applied. Each model represents a routing update interval and a multiclass open queueing network is used to solve the model during a particular interval. Descriptions of the design and implementation of X wan, an X Window based modelling system, are provided. A feature of the modelling system is that it provides a Graphical User Interface (GUI), allowing interactive network specification and the direct observation of network routing through the medium of this interface. Various applications of the modelling system are presented, and overall network behaviour is examined. Experimentation with the routing algorithm is conducted, and (tentative) recommendations are made on ways in which network performance could be improved. A different routing algorithm is also implemented, for the purpose of comparison and to demonstrate the ease with which this can be affected.
Open Access
Office automation
(1989) Stutz, Peter; Kritzinger, Pieter S
Office automation systems have become an essential tool for the operation of the modern office. With the emphasis of a modern office being placed on efficiency and ease of communication, office automation systems have become the backbone of successful businesses. COSNET is a prototype office automation system designed and implemented at the Department of the University of Cape Town and runs on Personal Computers that are linked to a NCR UNIX TOWER, which acts as the host. This dissertation investigates the different facilities supported by some of the office automation systems compared in this thesis, and describes the COSNET features. This prototype office automation system supports many of the facilities that are supported by large office automation systems. COSNET allows the user to define any MS-DOS based editor or word processor, and uses a simple editor for the creation of mail. The electronic filing facility allows documents to be created, filed, retrieved and deleted, and thus provides the users with the necessary features for document exchange. A user may set access permissions to each of his documents and may grant other users either read or write access to a specific document. The mail facility lets the user read, file, forward, delete and print a message, and supports classification of mail. A calendar facility is used as an electronic diary and stores all the user's schedules. These schedules may be viewed in either daily, weekly and monthly display modes. Read and write access to the calendar can be set by the user, in order to allow other users to manipulate his schedules. Any MS-DOS based application software can be added to COSNET. This facility allows the COSNET user to configure the office automation system to simulate the office environment. COSNET thus supports most of the necessary features required by an office automation system.
Open Access
Parallelisation of algorithms
(1990) Schuilenburg, Alexander Marius; Gledhill, I M A; Kritzinger, Pieter S
Most numerical software involves performing an extremely large volume of algebraic computations. This is both costly and time consuming in respect of computer resources and, for large problems, often super-computer power is required in order for results to be obtained in a reasonable amount of time. One method whereby both the cost and time can be reduced is to use the principle "Many hands make light work", or rather, allow several computers to operate simultaneously on the code, working towards a common goal, and hopefully obtaining the required results in a fraction of the time and cost normally used. This can be achieved through the modification of the costly, time consuming code, breaking it up into separate individual code segments which may be executed concurrently on different processors. This is termed parallelisation of code. This document describes communication between sequential processes, protocols, message routing and parallelisation of algorithms. In particular, it deals with these aspects with reference to the Transputer as developed by INMOS and includes two parallelisation examples, namely parallelisation of code to study airflow and of code to determine far field patterns of antennas. This document also reports on the practical experiences with programming in parallel.
Open Access
Protocol engineering from Estelle specifications
(1993) Wheeler, Graham; Kritzinger, Pieter S
The design of efficient, reliable communication protocols has long been an area of active research in computer science and engineering, and will remain so while the technology continues to evolve, and information becomes increasingly distributed. This thesis examines the problem of predicting . the performance of a multi-layered protocol system directly from formal specifications in the ISO specification language Estelle, a general-purpose Pascal-based language with support for concurrent processes in the form of communicating extended finite-state machines. The thesis begins with an overview of protocol engineering, and a discusses the areas of performance evaluation and protocol specification. Important parts of the mathematics of discrete-time semi-Markov processes are presented to assist in understanding the approaches to performance evaluation described later. Not much work has been done to date in the area of performance prediction from specifications. The idea was first mooted by Rudin, who illustrated it with a simple model based on the global state reachability graph of a set of synchronous communicating FSMs. About the same time Kritzinger proposed a closed multiclass queueing model. Both of these approaches are described, and their respective strengths and weaknesses pointed out. Two new methods are then presented. They have been implemented as part of an Estelle-based CASE tool, the Protocol Engineering Workbench (PE!V). In the first approach, we show how discrete-time semi-Markov chain models can be derived from meta-executions of Estelle specifications, and consider ways of using these models predictively. The second approach uses a structure similar to a global-state graph. Many of the limitations of Rudin's approach are overcome, and our technique produces highly accurate performance predictions. The PEW is also described in some detail, and its use in performance evaluation illustrated with some examples. The thesis concludes with a discussion of the strengths and weaknesses of the new methods, and possible ways of improving them.
Open Access
ROLAND : a tool for the realistic optimisation of local access network design
(1999) Buffler, Simon; Kritzinger, Pieter S
Investment in the local access network represents between 50% and 70% of capital investment of a telecommunications company. This thesis investigates algorithms that can be used to design economical access networks and presents ROLAND: a tool that incorporates several of these algorithms into an interactive environment. The software allows a network designer to explore different approaches to solving the problem, before adopting a particular one. The family of problems that are tackled by the algorithms included in ROLAND involve determining the most economical way of installing concentrators in an access network and connecting demand nodes such as distribution points to these concentrators. The Centre-of-Mass (COM) Algorithm identifies clusters of demand in the network and suggests good locations for concentrators to be installed. The problem of determining which concentrators in a set of potential sites to install is known as the concentrator location problem (CPL) and is an instance of the classical capacitated plant location problem. Linear programming techniques such as branch-and-bound can be used to find an optimal solution to this problem, but soon becomes infeasible as the network size increases. Some form of heuristic approach is needed, and ROLAND includes two such heuristics, namely the Add and Drop Heuristic. Determining the layout of multi-drop lines, which allow a number of demand nodes to share the same connection to a concentrator, is analogous to finding minimal spanning trees in a graph. Greedy approaches such as Kruskal's algorithm are not ideal however, and heuristics such as Esau-William's algorithm achieve better results. Kruskal's algorithm and Kershenbaum's Unified Algorithm (which encapsulates a number of heuristics) have been implemented and come bundled with ROLAND. ROLAND also includes an optimal terminal assignment algorithm for associating distribution points to concentrators. A description of ROLAND's architecture and GUI are provided. The graphical elements are kept separate from the algorithm implementations, and an interface class provides common data structures and routines for use by new algorithm implementations. A test data generator, able to create random or localized data, is also included. A new hybrid concentrator location algorithm, known as the Cluster-Add Heuristic is presented. The implementation of this algorithm is included in ROLAND, and demonstrates the ease with which new solution methods can be integrated into the tool's framework. Experimentation with the concentrator location algorithms is conducted to show the Cluster-Add Heuristic's relative performance.
Open Access
Simulating raid storage systems for performance analysis
(2007) Perumal, Sameshan; Kritzinger, Pieter S
Redundant Array of Independent Disks (RAID) provides an inexpensive, fault-tolerant storage solution using commodity hard-drives. RAID storage systems have recently surged in popularity amongst enterprise clients, as they provide economical, scalable, high-performance solutions for their storage requirements. The performance of RAID systems is negatively affected by the overhead required to manage and access multiple drives, and multiple disk failures can result in data loss. As RAID has developed, various improvements have been devised by both academia and business to address these shortcomings. These improvements have suggested improved architectures to increase performance and new coding techniques to protect against data loss in the case of drive failure. Evaluating the effect on performance of these improvements is greatly simplified by the use of discrete-event, software simulations. The RAID Operations Simulator for Testing Implementations (RÖSTI) was developed to support such simulation experiments.
Open Access
Simulation modelling of QoS enhancements in IEEE, 802. 11 networks and the effects of channel modelling
(2011) Mundangepfupfu, Tinotenda Leslie; Kritzinger, Pieter S
In this work the impact of the channel effects in modelling EDCA and DCF protocols of the IEEE 802.11 Medium Access Control (MAC) protocol on overall network performance is investigated.