UBC Theses and Dissertations
Performance modelling and evaluation of protocols based on formal specifications Zhang, Sijian
Protocol performance issues are important in communication protocol design and network management, especially for those protocols which run in high-speed networking environments. An accurate performance modelling and evaluation approach is necessary to obtain reliable performance estimations and to improve system performance. Using queueing models (QMs) or finite state machines (FSMs) alone is difficult to achieve this goal because many aspects that affect performance are not taken into consideration by the model. This thesis proposes a new performance model called performance extended finite state machine (PEFSM). PEFSM makes use of the strengths of both QM and FSM. A PEFSM is based on an FSM which is extended to include time and probability. Furthermore, the transition time is refined and divided into two parts: the transition wait time and the transition service time. This allows the PEFSMs to integrate message arrival and queueing models which provide useful and essential information necessary for studying real world protocols. PEFSMs are classified into three categories based on the message arrival characteristics: synchronous PEFSMs (SyPEFSMs), asynchronous PEFSMs (AsPEF SMs) and hybrid PEFSMs (HyPEFSMs). While the hybrid model is the most useful and realistic model for communication protocols, the other two models are also presented for completeness, and as a way to explain the hybrid model. A method for computing performance metrics based on SyPEFSMs is given in the thesis. Two types of AsPEFSMs — AsPEFSM-α and AsPEFSM-β — and their performance evaluation methods are also presented. Then a class of HyPEFSM which is a hybrid model of SyPEFSM and AsPEFSM-α is introduced. The proposed performance evaluation method for this class of HyPEFSM is basically the combination of those for SyPEFSMs and AsPEFSM-αs. Our performance mod effing and evaluation approach has been applied to various examples, including the alternating bit protocol and multi-stage interconnection network (MIN). The performance evaluation method for PEFSMs makes use of stochastic pro cess and queueing theory. A new queueing property for an M/G/1. with multiple job classes and an analogous property for AsPEFSM-os have been discovered and proved. As a first step in improving system performance, the thesis defines software performance bottlenecks based on PEFSMs. Two bottleneck identification methods are proposed and tested. This thesis also proposes a testing method called t-test which in most cases is able to obtain the service times of invisible transitions when the protocol implementation under test is given as a black box. Transition service times are important parameters in FSM-based performance models. Studies in the past have usually assumed the transition times to be known a priori without discussing how they may be obtained. Simulations and measurement experiments have been conducted to validate the methodologies proposed in this thesis. The results are quite promising.
Item Citations and Data