PERFORMANCE MODELLING AND EVALUATION OF PROTOCOLSBASED ON FORMAL SPECIFICATIONSBySijian ZhangB. Sc. (Computer Science) Beijing University, ChinaM. Sc. (Computer Science) Beijing University, ChinaA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIESCOMPUTER SCIENCEWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAJuly 1995© Sijian Zhang, 1995In presenting this thesis in partial fulfillment of the requirements for an advanced degreeat the University of British Columbia, I agree that the Library shall make it freelyavailable for reference and study. I further agree that permission for extensive copyingof this thesis for scholarly purposes may be granted by the head of my department or byhis or her representatives. It is understood that copying or publication of this thesis forfinancial gain shall not be allowed without my written permission.Computer ScienceThe University of British Columbia2366 Main MallVancouver, CanadaV6T 1Z4Date: 3AbstractProtocol performance issues are important in communication protocol designand network management, especially for those protocols which run in high-speednetworking 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’ performanceare not taken into consideration by the model.This thesis proposes a new performance model called performance extendedfinite state machine (PEFSM). PEFSM makes use of the strengths of both QMand FSM. A PEFSM is based on an FSM which is extended to include timeand probability. Furthermore, the transition time is refined and divided into twoparts: the transition wait time and the transition service time. This allows thePEFSMs to integrate message arrival and queueing models which provide usefuland 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 (AsPEFSMs) and hybrid PEFSMs (HyPEFSMs). While the hybrid model is the mostuseful and realistic model for communication protocols, the other two models arealso presented for completeness, and as a way to explain the hybrid model. Amethod for computing performance metrics based on SyPEFSMs is given in thethesis. Two types of AsPEFSMs— AsPEFSM-o and AsPEFSM-fi— and theirperformance evaluation methods are also presented. Then a class of HyPEFSMwhich is a hybrid model of SyPEFSM and AsPEFSM-o is introduced. The pro11posed performance evaluation method for this class of HyPEFSM is basically thecombination of those for SyPEFSMs and AsPEFSM-as. Our performance modeffing and evaluation approach has been applied to various examples, includingthe alternating bit protocol and multi-stage interconnection network (MIN).The performance evaluation method for PEFSMs makes use of stochastic process and queueing theory. A new queueing property for an M/G/1. with multiplejob classes and an analogous property for AsPEFSM-os have been discovered andproved.As a first step in improving system performance, the thesis defines softwareperformance 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 casesis 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 haveusually assumed the transition times to be known a priori without discussing howthey may be obtained.Simulations and measurement experiments have been conducted to validatethe methodologies proposed in this thesis. The results are quite promising.111ContentsAbstractContentsList of TablesList of FiguresAcronyms and TermsAcknowledgementDedication11ivvii’ixxixiiixv1 Introduction1.1 Background1.1.1 Objectives1.2 Queueing Models1.3 Formal Description Techniques .1.4 Problems1.5 Proposed Solution Approaches .1.6 Summary of Contributions1.7 Layout of The Rest of The Thesis2 Survey of Related Work2.1 Introduction2.2 Modeling Approaches2.2.1 Performance models2.2.2 Queueing models vs FSMs112346710111313151521iv2.2.3 Specifying performance elements 242.3 Analytic Methods 262.4 Simulation Tools 292.4.1 Simulators based on FDTs 292.4.2 Simulators based on queueing models 322.4.3 Simulation tools based on multiple models 352.5 Summary 373 A New Performance Model 383.1 Introduction 383.2 Finite State Machine (FSM) 433.3 PEFSM: a new performance model 443.3.1 Classification of messages 443.3.2 Transition time 453.3.3 State occupancy and stochastic process 483.3.4 Formal definition of PEFSM 503.4 Synchronous, Asynchronous and Hybrid PEFSMs 533.5 Embedded Stochastic Processes of a PEFSM 583.5.1 Pure state changing process (Model E) 583.5.2 Pure service delay process (Model S) 593.5.3 Pure wait process (Model W) 593.5.4 Relationships 603.6 Summary 634 Performance Evaluation of Synchronous PEFSMs 654.1 Introduction 654.2 Message Arrival Model 674.3 Performance Metrics of SyPEFSMs 674.3.1 Performance metrics computed from Model S 684.3.2 Performance metrics computed from Model ‘I’ 704.4 Related work 744.5 Summary 755 Performance Evaluation of Asynchronous PEFSMs 775.1 Introduction 775.1.1 Queueing models 795.1.2 Arrival models 795.2 AsPEFSM-of 80V5.2.3 Performance Metrics5.3 AsPEFSM-/35.3.1 ,6-arrival model5.3.2 Queueing and service model5.3.3 Performance metrics .5.4 Bounds of Performance Measures5.5 Related work5.6 Summary6 Performance Evaluation of Hybrid 1146.1 Introduction . .. 1146.1.1 Hybrid transition . . . 1156.1.2 Hybrid state . .. 1166.2 Models and Evaluation . .. 1196.2.1 Message arrival model . . . . 1196.2.2 Queuing and service model . . . 1206.2.3 Performance metrics . . . . . 1206.3 An Application Example . .. 1256.4 Summary and Discussion . .. 1297 Analysis of Performance Bottlenecks using PEFSMs7.1 Introduction7.2 Throughput Bottleneck7.3 Queue Wait Time Bottleneck7.4 Related Work7.5 Summary1541541571661721781819 Conclusions and Future Work 1845.2.15.2.2o-&riva1 model 81Queueing and service model 81849999102102111111113PEFSMs133• . . 134• . . 138139150• . . 1528 On Transition Time Testing based on FSMs8.1 Introduction8.2 T-test8.3 Testability8.4 Test Sequence Generation8.5 Experimental Results8.6 Summaryvi9.1 Conclusion9.1.1 Contributions.9.1.2 Applicability of PEFSM to EFSM9.2 Future Work9.2.1 System-wise performance evaluation9.2.2 Queueing theory9.2.3 New topics in stochastic processes9.2.4 On-line performance tuningBibliography 195209209210212213213214214215B Computation of 217C An Estelle specification for sliding window protocol 219D An Estelle specification of the hot-potato protocol 227E An application example of HyPEFSM 230F Bottleneck identification results 237G T-test results of a LAPB implementation 240184185188190190192193193A Mathematical BackgroundA.1 IntroductionA.2 Markov ProcessA.3 Continuous-time Semi-Markov ProcessA.3. 1 Steady-state state probabilityA.3.2 Limiting state lodging probabilityA.3.3 First passage timeA.3.4 State RecurrenceA.3.5 Transition recurrenceviiList of Tables2.1 The relationship of Modeling and Analysis approaches 276.1 Comparison of analytical result and simulation result 1287.1 A simulation result of bottleneck identification 1498.1 Simulation and Testing Results 181F.1 A simulation result 238G.1 Testing results of the LAPB implementation 241viiiList of Figures2.1 An example of a queueing model.2.2 An example of an FSM3.13.23.33.43.53.63.75.15.25.35.46.16.26.36.46.56.68.1 A sample conceptual testing architecture40414447555660115117• 129• 129• 130• 1311411431461471572123An FSM of the alternating bit protocolAn FSM of CCITT/ISO X.25 LAPBAn abstract FSMThe components of a transition timeAn FSM of the hot potato protocolAn FSM of an ATM serving two types of data . .Model W of the PEFSM in Figure 3.3The queueing system for an AsPEFSM-aReduction of a general FSM into a one-state EFSMMessages come to and leave state i in an AsPEFSM-crThe queueing system for an AsPEFSM-,8838893102An FSM of the alternating bit protocolThe possible situations of two transitions from a stateMean queue wait time vs. mean data arrival rateMean queue wait time vs. mean data arrival rateMean queue wait time vs. packet loss probabilityModelling of a hybrid state7.17.27.37.4Service order implied by the FSM of a PEFSM . .The subpaths to transition ij in a PEFSMAlgorithm for weight computationA simulation architectureix8.2 A sample time diagram of message sendings and executions . . . 1598.3 A sample time diagram where there is no queue wait time . . . 1608.4 Selecting the message sending intervals 1618.5 Two consecutive transitions with at least one visible transition . 1678.6 Two consecutive transitions without any visible transition . . . 1678.7 Example of test subpaths for invisible transitions 1698.8 A sample FSM graph showing disconnected subgraphs after deleting invisible transitions 1748.9 A sample FSM with untestable transitions 1758.10 An example FSM to show test subsequence generation 1768.11 Test subsequence generation procedure for the FSM in Figure 8.10 1778.12 A testing architecture of the t-test 1788.13 The FSM of an abstract protocol 1809.1 Two modules in system-wise analysis 191A.1 The occupancies of state i in time axis 216C.1 Module relation graph of sliding window protocol 219E.1 FSM for the hold protocol 231E.2 Mean queue wait time vs. arrival rate 236E.3 Mean queue wait time vs. blocking probability 236F.1 The FSM of FDDI MAC Transmitter 237xAcronyms and TermsVector of steady state probabilities of a PEFSMSteady-state probability of state i in a PEFSMp UtilizationThroughput ratee2 Entrance rate of state iArrival rate of incoming messagesArrival rate of class i incoming messagesPo,i Probability that protocol is idle in state i823 First passage time from state i to j in a CSMP‘rjj Transition time for transition ij in a PEFSMwrij Transition wait time for transition ij in a PEFSMsrij Transition service time for transition ii in a PEFSMMatrix of probability density functions of Transition Wait TimesSJ{ Matrix of probability density functions of transition service timesMatrix of probability density functions of transition timesM AnFSMQ The state set of an FSM or PEFSM‘I’ A PEFSMP Matrix of single-step transition probabilities of a PEFSMAM Algebraic ModelAsPEFSM Asynchronous PEFSMASP Abstract Service PrimitiveCCITT International Telegraph and Telephone Consulative CommitteeCSMP Continuous-time Semi-Markov ProcessxiDSMP Discrete-time Semi-Markov ProcessFSM Finite State MachineEFSM Extended Finite State MachineHyPEFSM Hybrid PEFSMISO International Organization for StandardizationJUT Implementation Under TestLAPB Link Access Procedure BMP Semi-Markov ProcessOSI Open Systems InterconnectionPCO Points of Control and Observationp.d.f. Probability Density FunctionPDU Protocol Data UnitPEFSM Performance Extended Finite State MachinePTE Protocol Testing EnvironmentPN Petri NetQM Queueing ModelSAP Service Access PointSMP Semi-Markov ProcessSUT System Under TestSyPEFSM Synchronous PEFSMTCP/IP Transmission Control Protocol/Internet ProtocolTL Temporal LogicX.25 CCITT Packet-switching ProtocolxliAcknowledgementI would like to thank my research supervisor, Dr. Sameul T. Chanson. Without his guidance and support over the past several years, I could hardly finishthis thesis. Sam is responsible and he has never disrupted his supervision eventhough he is on-leave at thousands of miles away. Throughout the meetings anddiscussions with Sam, I have learned a lot from him. I am always prodded tothink of more and better results by the motive of his serious, strict and criticattitude in research. This I believe in turn helped me to come up with the resultsin this thesis.I would also like to thank Dr. Hong Chen, Dr. Norm Hutchinson and Dr.Mabo R. Ito for their willingness to serve on my supervisory committee. Dr.Hong’s joining increased my confidence when I met the stochastic process problems and found myself was new to this area. Besides, I would like to presentmy special gratitude to Dr. Tao Yang (Dept. of Industrial Engineering, Tech.Univ. of Nova Scotia). Although we have never met until today, he has been veryhelpful. His expertise and insight provided the useful clue to the short proof ofthe equality of mean queue wait times using PASTA.I thank Dr. Son Vuong for his encourgements and discussions, particularlyduring the early days of my graduate program at UBC. He is one of the mosteasygoing professors in the department and he always let me borrow the referencematerial he collected.I am very grateful to Baokang Chen, Joel DeYoung, Cohn Hawes, ChristopherHealey, Dr. Runping Qi, Dr. Ying Zhang and Jinsong Zhu. They spent lots oftime and effort on proofreading the early versions of my thesis. Without theirxliiproofreadings, this thesis would not be so readable. Many other fellows have alsoprovided various help during my staying at UBC. I highly appreciate their longlasting friendships.I particularly thank my family which has given me so much. Their understanding and faith always keeps me going. I feel deeply indebted to my wife,Yuanmeng Lu, for her dedicated love and patience.Last but not least, I would like to thank UBC which provides so enjoyableliving and studying environments for its students.xivto my father and his elder brotherxvChapter 1Introduction1.1 BackgroundThe performance of a computer communication system is determined by twofactors: protocol performance and network performance. The first factor refersto the performance of the raw data processing of a communication protocol (forexample, TCP and ISO TPs) on a computer. The second factor refers to theperformance of data transmission between computers.We have seen a rapid evolution of computer networks in the past few years.The use of optical fiber has greatly improved the bandwidth of communicationchannels, making data transmission rates of several gigabits per second (Gbps)possible. As a result, transmission delays between computers have been significantly reduced. For instance, a packet of length 1KB takes only 8 microsecondsto transmit on a 1 Gbps line.Unfortunately, the improvement in processing speed of protocols has been1Chapter 1: introduction 2much less impressive. Although computer architectures, operating system support and new communication protocols have been developed in an effort to support high speed communications [Clark85, Giar89, Hehm89, Watson89, Zitt89,Doer9O, AbKa9l], the CPU processing time of protocol packets is still of theorder of tens of microseconds, on average [Svob89, Clark89, Nich9l].As a consequence, the performance bottlenecks in computer communicationshave shifted from the communication links to the communicating hosts that areunable to process, send and receive data as fast as the communication channelscan transmit the data[Clark89J. Therefore, the performance of communicationprotocols is becoming an important issue.1.1.1 ObjectivesPrior to the implementation and deployment of a protocol, it is very desirable toknow things like: how well the protocol will perform in certain operating environments, where the potential software bottlenecks of the protocol are, and how theperformance can be improved. For example, given the workload of the communication network, what is the ideal buffer size to store incoming messages for eachprotocol entity? What are the service delays and queue wait delays for each typeof incoming message? Which processing path is the most critical for improvingthe performance of the protocol? What is the network traffic generated by a protocol entity? The answers to these and other performance related questions areuseful in understanding and improving communication performance. Therefore,a proper performance modelling and evaluation method is needed in the protocoldesign phase as well as in tuning the performance of protocol implementations.Chapter 1: introduction 31.2 Queueing ModelsIn general, there are two approaches to evaluate the performance of a computersystem: simulation and analytic. Whichever way is chosen, performance modeffing is always the first step.Traditionally, performance modelling is often done using queueing models. Asingle server queueing system is usually adopted to represent the computer onwhich a protocol entity is running. The service time of the messages in thisqueueing system is assumed to be independent and identically distributed (i.i.d)(e.g., exponential distribution). The arrivals of the messages to the queueingsystem are also assumed to be i.i.d. in most cases to simplify the analysis.In a computer network, however, the actual arrival pattern of messages toa computer is quite complex. This traffic is usually managed by a combinationof flow control, rate control, congestion control and other mechanisms definedin a network protocol. Moreover, the order in which the messages are serveddepends on the protocol’s state. A particular class of messages of a protocol isserved only when the protocol is in a specific state. This important informationis neglected in queueing models for analyzing protocol performance. Althoughsimplifications make the conventional models tractable, they lead to inaccurateresults. As computer networks are becoming faster, this inaccuracy becomes moreand more significant.A new performance model is needed. The model should take into account moresystematic information about a protocol during performance evaluation than aqueueing model does.Chapter 1: introduction 41.3 Formal Description TechniquesFormal Description Techniques (FDTs) provide some answers to the problemsdiscussed in the previous sections.Until recently, almost all communication protocols have been specified in natural languages, often resulting in different interpretations by different users of thesame protocol. FDTs were introduced as a means of eliminating or minimizingambiguity in describing communication protocols and distributed systems.Many FDTs have been developed and used. One may categorize FDTs intotwo groups: formal models such as finite state machines (FSMs), Petri Nets, algebra and temporal logic, and formal specification languages such as SDL, Estelleand LOTOS.Unlike general-purpose computer programming languages, a formal specification language is usually designed to describe a certain formal model. For example,a formal specification in SDL or Estelle describes an extended FSM (EFSM), anda specification in LOTOS is based on a calculus of communicating systems (CCS)and communicating sequential processes (CSP). A formal specification languageprovides the functionality of variable definitions which formal models usually lack.Up to now, three formal languages were standardized by ISO and CCITT for descriptions of communication protocols: Estelle[1S08807], LOTOS[1SO9074] andSDL[SDL].Briefly, FDTs provide a formal way ofspecifying a communicating protocol unambiguously,Chapter 1: introduction 5• validating the design of a protocol,• generating test cases for conformance testing,• simulating the behaviour of a protocol before implementation,• implementing a protocol semi-automatically, and• predicting the performance of a protocol.With a specification in an FDT, validation and verification as well as implementation can be done automatically or semi-automatically [Vuong86, Azema89].Test sequences for conformance testing can also be derived from a formal specification [Sari86, Sari87, Ural87a, Wu89]. In the early 1980s, some basic ideas wereproposed by Rudin to use a formal protocol definition as the basis for the automated prediction of protocol performance [Rudin83}. Since then, other researchon this subject has appeared in the literature (see, for example, [Krit87, BoVa88,LiLi88, Shaw89, GuRu89, AFF9O, FVV91]). Chapter 2 contains a survey of thisresearch and other work on protocol performance analyses.FDTs are useful in performance studies and provide different levels of abstraction for both analysis and simulation of protocols. Furthermore, a formalspecification or a formal model explicitly describes the important aspects of acommunication protocol systematically. These aspects influence system performance. For example, from a given specification of a sliding window protocol (seeAppendix C for details), one can identify the factors which affect performancesuch as window size, timeout value, transition probabilities and data arrival rates.This is an important advantage of FDTs. [ZhCh93J proposed an approach toevaluate protocol performance considering the amplifier effect, i.e., one input andChapter 1: introduction 6multiple outputs. The coefficient matrix of an amplifier is derived from a givenEstelle specification.To exploit the power of FDTs, it is useful to have a framework for systematicperformance analyses. This is called single-specification / multiple-techniquesin [Heck9lJ. More and more system designers using FDTs find the need forperformance tools associated with FDTs. Developing performance models andtools based on an FDT is the general objective of this thesis.1.4 ProblemsSome research using FDTs for performance evaluation of protocols already exists[AFF9O, Rico9l, KrWh93]. The main problem is that either the models areincomplete or insufficient to capture the requirements discussed above, or theanalyses are computationally expensive or inaccurate.For example, [KrWh93] treats the FSM of a protocol as a discrete-time semiMarkov process and then predicts the performance of the protocol. However,this approach does not model the arrival process and does not study queueingproperties, which are important performance indices for most communicationprotocols and computer systems. For this reason, performance is expressed onlyin the form of bounds.The earlier work [Krit86, Krit87] did not take information about the statedependent service of a protocol into account. All the messages coming to/froma protocol entity were treated aggregately. As a result, only the overall queueingdelay of messages and the overall queue length of a protocol entity could becomputed. Furthermore, since no state-dependent service is considered, it isChapter 1: introduction 7difficult to have an accurate estimate of the performance.Other research such as (LiLi88, BaBu9l] uses validation/verification methods(mainly reachability analysis) for performance analysis. This approach inevitablyruns into the state space explosion problem because the size of a reachabilitytree grows exponentially. A great amount of effort has been spent on reducingthe size of the state space in this kind of approach. However, the reductiontechniques further increase the inaccuracy of performance measures. Moreover,this reachability approach usually cannot derive queueing characteristics.1.5 Proposed Solution ApproachesTo address the above problems, a new performance model called PerformanceExtended Finite State Machine (PEFSM) is proposed. We introduce this modelto reduce the computational complexity of performance analysis of a protocolwithout sacrificing too much accuracy. This performance model is essentially ahybrid model combining the FSM and queueing models.FSMs are chosen because they provide a reasonable abstraction about a communication protocol and are used commonly in communication systems. Othermodels are often transformed into FSMs before analysis. Examples include PetriNets [Mol182} and LOTOS [Mars94]. More discussion is given in Chapter 2.FSMs are also chosen because many communication protocols are given directly in this form. Using FSMs, the performance modelling and analysis are morestraightforward and the performance indices are easier to understand. Among thethree standardized formal specification languages, two of them, Estelle and SDL,are based on FSMs or extended FSMs. There exist many support tools for FSMs.Chapter 1: introduction 8A disadvantage of FSMs is that they do not model arrival processes, resourcecontentions and queue wait delays easily. Thus, our modelling approach tacklesthis problem by taking advantage of the strengths of both queueing models andFSMs.Similar to previous work in [LiLi88, BoVa88, KrWh93], the FSM of a PEFSMis extended with transition time and transition probability for performance evaluation. Each transition of the FSM is associated with an incoming and an outgoingmessage class, labeled with I/O. A transition time in a PEFSM is divided intotwo parts: the wait time for an incoming message associated with the transitionand the service time to execute the transition. Transition wait times are relatedto the arrival process of incoming messages, so an arrival model is associatedwith each PEFSM. The transition wait times of a PEFSM are computed fromthe given arrival model and the PEFSM.Arrival models depend on assumptions about the environment in which thecommunication protocols run. There are three basic types of arrival patternsfor incoming messages: synchronous, asynchronous or a combination of the two.Accordingly, PEFSMs are classified into three categories: synchronous PEFSMs(SyPEFSMs), asynchronous PEFSMs (AsPEFSMs) and hybrid PEFSMs (HyPEFSMs). The classification of a PEFSM is determined by the arrival modelused.A queue is assigned to each class of incoming messages in a PEFSM. Thismakes the analysis of queue wait delays possible. Queueing theory is employedto compute these delays. However, note that the queue wait delay of a messageincludes not only the service times of the messages in front of it in the samequeue but also possibly other transition times of transitions which have to beChapter 1: introduction 9processed before this message. This is because the service in a protocol entityis state-dependent. Therefore, some input values for the queueing analysis willcome from the result of analyzing the FSM of the associated PEFSM.To compute the statistics of the FSM, the state changing process of an FSMis examined. This process is actually a stochastic process and thus the theoryof stochastic processes is employed. In this thesis, we only study the stochasticprocesses which are continuous-time semi-Markov processes (CSMPs) [Howa7l].More complex stochastic processes are left for future research.Software performance bottlenecks are also studied in the framework of PEFSMs. A bottleneck with respect to a performance metric is defined as a bottleneck transition in the FSM of a PEFSM. A methodology to identify these criticaltransitions in PEFSMs is proposed. This allows the designer to focus on the fewtransitions that constrain system performance.This thesis also provides a solution to another fundamental issue. By definition, transition times are primitive data for a PEFSM. This data is essentialin performance evaluation. However, previous work has assumed the transitiontimes to be known a priori. How these values are obtained has widely been ignored. In the framework of performance evaluation for PEFSMs, we proposea technique to measure/compute transition times when an implementation of aprotocol is given as a black box.We have mentioned that in a PEFSM, transition time consists of transitionwait time and transition service time. The first component is computed froma given arrival model and the PEFSM. The computation methods of transitionwait times are given with respect to each type of PEFSM. To obtain transitionChapter 1: introduction 10service times accurately through measurement, an algorithm for transition timetesting called t-test is presented in the thesis. The methodology to generate testsequences for t-test is also proposed. The initial work on t-test was published in[ZhCh94].1.6 Summary of ContributionsThe contributions of this thesis can be summarized in three aspects:• performance prediction,• performance improvement, and• performance measurement.A new performance model — PEFSM together with the framework of performance evaluation based on this model — is proposed. The computation methodologies to obtain performance metrics of three classes of PEFSMs (SyPEFSMs,AsPEFSMs and HyPEFSMs) are developed. Accompanying this modelling approach, an interesting queueing property of the incoming messages in an AsPEFSM or a HyPEFSM is discovered and presented. This property is also usedin deriving performance metrics.To maximize the improvement of the performance of a protocol, softwareperformance bottlenecks are defined based on PEFSMs. A method for the identification of transition bottlenecks is proposed. To our knowledge, no other similarresearch exists which tries to pinpoint potential software performance bottlenecks based on an FDT. The bottleneck identification problem was one of theChapter 1: introduction 11outstanding issues without a good solution. Our experimental results showedthat the proposed method can accurately identify the bottleneck transition in aPEFSM with respect to a performance metric.Finally, we suggest a methodology called the t-test which can be used to obtaintransition service times through measurement and testing. The transition servicetimes are important parameters needed in all FSM and EFSM based models buthave been assumed to be known a priori in previous work.1.7 Layout of The Rest of The ThesisChapter 2 provides a survey of related work, focusing mainly on performanceevaluation methods related to FDTs. This survey serves in fact as a startingpoint for this thesis.Chapters 3 to 6 introduce the framework for modelling and evaluating performance of communication protocols based on the new performance model, PEFSM.Chapter 3 gives a formal definition of a general PEFSM. Three embedded modelsof a PEFSM are defined. This chapter provides the foundation for the analysesand performance metric derivations in the following three chapters.PEFSMs are categorized into three classes, SyPEFSMs, AsPEFSMs and HyPEFSMs, according to incoming message arrival patterns. Chapter 4 deals withSyPEFSMs, which assume incoming messages arrive synchronously. Chapter 5presents AsPEFSMs, which assume incoming messages arrive asynchronously.Chapter 6 deals with HyPEFSMs, which assume incoming messages arrive bothsynchronously and asynchronously. While the hybrid model is the most interesting and realistic one in the real world, the other two models are also presentedChapter 1: introduction 12for completeness and as a way to explain the hybrid model in a systematic way.The mathematical background necessary for this study is given in Appendix A.Chapter 7 defines software performance bottlenecks based on the PEFSMs.The methods to identify the bottlenecks are presented.Chapter 8 presents the testing methodology for deriving the transition servicetimes of a PEFSM accurately, although the protocol implementation is given asa black box.Chapter 9 summarizes the contributions of this thesis and identifies somefuture research directions.Chapter 2Survey of Related WorkAbstractThis chapter provides a survey of the related work on performance evaluation forcomputer systems, focussing mainly on communication protocols. It examines theprevious work of performance evaluation from three different points of view: modellingapproaches, analytic methods and simulation tools. The conclusion of this survey isthat queueing models (QMs) and finite state machines (FSMs) are complementarytechniques in modelling communication protocols. A hybrid model combining QM andFSM is suggested as a suitable way to model protocols for performance evaluation.2.1 IntroductionPerformance evaluation of computer systems is not a new research area. Numerous evaluation methodologies have been developed and published, rangingfrom very theoretical and complex mathematical derivations such as queueingtheory and automata theory to very practical approaches such as performance13Chapter 2: survey of related work 14benchmarks and simulators.It is not our intention to present a wide range of issues and methods on performance evaluation or specific (ad hoc) performance modelling and analysis methods. Instead, we will focus on the work related to formal description techniques(FDTs) which may exist in two forms: formal models and formal specificationlanguages.Generally, the approaches to performance evaluation of a system can be classified into the following three broad categories:1. analysis,2. simulation, and3. measurementThe first two approaches require performance models and could use a formaldescription of the system to be evaluated. Measurement is usually carried out onan implementation which is executable, and will not be covered in this chapter.As mentioned in the previous chapter, FDTs are becoming more and morewidely used in the design and development of large, complex computer networksand protocols. Rudin did pioneering work towards bridging the gap betweenformal specifications and the prediction of protocol performance [Rudin83J. Hepointed out three possible approaches in the early 1980s:1. analysis of a protocol to check for logical self-consistency, including timespecifications;2. simulation to predict performance;Chapter 2: survey of related work 153. analysis to predict performance.Rudin noted that the first approach had proven to be the most difficult andlittle progress had been made at the time. However, much research has been donesince (see, for example, [Drira95J) but mostly for verification purposes.The latter two approaches are currently the most widely used approaches inperformance evaluation based on FDTs. In the following sections, the techniquesor methodologies in these two categories are surveyed. The survey is presented inthree domains: modelling techniques, analytic methods and simulation methods.The rest of the chapter is organized as follows. Section 2.2 compares differentperformance modelling approaches. Section 2.3 investigates the different analytic methods and their relationships with the modelling approaches mentionedin Section 2.2. Section 2.4 lists simulation tools according to their underlyingmodels. Section 2.5 discusses software metrics, complexity problems and performance metrics. Section 2.6 summarizes the chapter.2.2 Modeling ApproachesIn both analytic and simulation studies, a performance model describing the computer system or communication protocol to be evaluated must be formulated.In this section, formal models based on FDTs are presented and their relativestrengths and weaknesses in performance evaluation are examined.2.2.1 Performance modelsThere are many ways to model communication systems. Some of them are general, while others are very specific. Some popular modelling techniques are:Chapter 2: survey of related work 16• Queueing Model (QM)• Finite State Machine (FSM)• Petri Net (PN)• Algebraic Model (AM)• Temporal Logic (TL)Queueing Models are perhaps the most traditional and also most popularway to model computer systems and analyze their performance. Queueing theorywas first introduced and studied in operations research in the 1950s [Mors58].Ever since John D. C. Little’s formulation of what has become known as Little’sLaw [Litt6lj, namelyL =)•W,the applications of QMs in computer systems have proliferated. A great amountof work has been published since the 1970s, both in theory and in practice. Oneof the most popular and widely cited books on queueing theory in the past twodecades was written by L. Kleinrock [Klein75].QMs have become popular partially due to their simplicity in modelling complex computer systems. These models focus on resource contention. With thisapproach, all components are reduced to two basic constructs— queue and server.Servers represent resources shared and/or consumed by jobs. Queues representbuffers or lines where jobs wait to be served.QMs are generally classified into two categories: queueing systems and queueing networks. A service center with only one server forms a queueing system.Chapter 2: survey of related work 17Queueing systems that are interconnected together constitute a queueing network.Queueing models model the behaviours of jobs in queues and servers as well asthe overall system behaviours. The performance measures of a system being modeled are estimated by analyzing or simulating the model. These measures includedelays (queueing delays and service delays), server utilizations and throughputs.Queueing models have been successfully used in modeffing computer memory,disk subsystems, processors and computer networks [Lazo84]. Recently, queueing models that take into consideration the behaviour of the traffic sources havebeen used in analyzing the performance of asynchronous transfer mode (ATM)networks [DiDe9O, Herr93, Kesi93J.FSM’ consists of states and transitions. FSMs originated from the study ofcomputer languages and computability. However, there are many variations ofFSMs whose applications are far beyond these original domains. Today, FSMsare one of the most widely used tools in modeffing communication protocols[PhGr88, Tane88, DeBu89, Stall9l, 1S02576, 1S07776]. This is because mostcommunication protocols are designed as FSMs [Dan8O].FSMs augmented with variables are called extended FSMs (EFSMs). FSMswith associated times in their transitions or states are called timed automata[LyAt92]. FSMs with probabilities assigned to the transitions are called probabilistic automata.With times and probabilities, FSMs (or EFSMs) can be used for performancemodelling. One typical approach is found in the work of Kritzinger and his‘FSMs are also called finite state automata in some literature.Chapter 2: survey of related work 18colleagues. [Krit86] introduced a way to model OSI communication architecturesusing FSMs. [Krit87J presented a way to reduce the complexity of communicationprotocol analysis using image protocols. [KrWh93} transformed a timed andprobabilistic FSM into a discrete-time semi-Markov process. The theory of thisstochastic process is then applied to derive the performance measures for theprotocol specified by the FSM. Other work using FSMs as performance modelscan be found in [LiLi88, BoVa88, Heck9l].None of the above models considers message arrival processes in performancemodeffing and evaluation. The transition times usually take only the servicetimes of transitions into account and thus the performance measures derived areupper bounds.Petri Nets are another useful tool in modelling communication systems. Ingeneral, Petri Nets can model control flow, concurrency and synchronization verywell. This modelling technique has been intensively studied since it was firstintroduced by Petri over thirty years ago [Petri62}. A PN consists of a number oftokens, places and transitions. A great number of modified PN models, such asplace-coloured PNs, predicate-transition PNs, time PNs and stochastic PNs havebeen proposed. [Diaz82] provides a general survey of PNs, and the introductionof [BeDi9l] contains a brief survey of time PNs.PNs have been used variously to model, validate and evaluate distributed systems, communication protocols and real-time systems [Mo1l82, Berth83, Ho1l87,Moll89a, Mars9O]. Graphical PNs are elegant in modelling simple protocols suchas the alternating bit protocol [Bart69]. However, PNs often lead to very complexnetwork models for more realistic protocols such as the sliding window protocolChapter 2: survey of related work 19[Tane88] and the CCITT n°7 protocol [Diaz82]. For instance, the PN for thealternating bit protocol has 14 places and 17 transitions [Mo1182], and the PNfor the CCITT n°7 protocol has 21 places and 22 transitions [Diaz82]. Muchresearch effort has been put into how to reduce the PNs before analysis. Some researchers have proposed to transform PNs into FSMs and then do analysis usingFSM techniques [Moll82].Algebraic Models in communication systems originated from Hoare’s Communicating Sequential Processes (CSP) [Hoar7S, Hoar85J and Milner’s Calculusof Communicating Systems (CCS) [Miln8O, Mi1n89]. In this approach, a computing process is represented using an algebra. LOTOS [1S088071 is an example ofan algebraic model.To model and evaluate performance, timing and other information should beintegrated into the algebra. For example, time attributes and probability attributesare defined as mappings in algebra [Nou85}. [Moller] introduced a kind of timedCCS, and other performance models using algebra with extensions can be foundin [Rico9l, Migu93, Mars94].Like PNs, in current research, most timed algebraic models are transformedto other forms (mostly FSMs) before performance analysis. The reason is notthat AMs provide too much detail; rather, they are too abstract. Some of theuseful information for performance analysis is omitted in an AM.Temporal Logic can also be used for performance modelling. It enhancestraditional logic with temporal formulas which are able to specify time propertiesabout a system. Three different concepts, program, property and satisfaction, areChapter 2: survey of related work 20replaced by the single logical concept, formula. Details about a system, such asprocedures and operations, are omitted.TL was first introduced to model and validate concurrent programs [Pnue77,Lamp9l, MaPn92]. TL is a useful and intuitive tool constructing prototypes ofsystem behaviour related to time [Hale9OJ. It is easy to use TL to prove somelogical properties about a system. For instance, TL can be used to check if certainperformance or real-time requirements are satisfied in a system being modeled.However, it is difficult to predict or compute performance measures using TL.For this reason, little progress has been made in performance evaluation usingTL, although there exists some work using TL to do performance validation andverification [Pnue77, Lamp9l, MaPn92].In summary, different models focus on different aspects of a system to bemodeled. QM and FSM are the two most popular approaches for performancemodelling. Each of them provides reasonable abstractions about the underlyingcomputer systems. This usually results in acceptable complexities in analysis. Insome of the previous work, other models were transformed into one of these twotypes of model before the performance analysis was carried out.In the following, we present a more detailed comparison between these twotypes of model in describing communication protocols. This shall help in understanding the new performance model defined in the next chapter.Chapter 2: survey of related work 212.2.2 Queueing models vs FSMsA QM consists of queues and servers. Both queues and servers represent thesystem resources such as buffers and processors. An example of a QM is givenin Figure 2.1. This figure shows a queueing network consisting of three servicecentres. Each service centre is a queueing system.IiidivduiJ queue OianneiOwweI2•Figure 2.1: An example of a queueing modelThe major weaknesses of the QM approach in modelling communication protocols are:1. Many important factors have to be omitted or simplified in a queueingmodel. For example, message arrival patterns, message lengths and errorrates are usually described in probabilistic distributions, such as exponential distributions. However, in communication protocols, message arrivalscannot always be assumed to be exponentially distributed, and arrivals arenot independent. For instance, a connection confirm (CC) message will usually arrive as a response after a connection request (CR) message is sent.Chapter 2: survey of related work 22Obviously, the conventional way used in QMs does not provide an adequatemeans to model the ordering relationship among message arrivals.2. Most protocols are specified as FSMs (or EFSMs). As a result, the services for a protocol are not identically distributed. The services are state-dependent. For instance, the order of transition execution in an FSM is notrandom. This correlation is specified in the FSM. However, it is difficultfor a QM to model this information.3. The queueing delay of a message in a protocol not only results from the othermessages in the same queue ahead of it, it has to wait until the system isin the right protocol state. QMs alone do not consider this aspect.4. In a QM, a job or an entire job class is usually modeled as a single unit.The coarse granularity makes the QM unsuitable for locating performancebottlenecks.A communication FSM consists of states and transitions. A transition usuallyrepresents the process of the system receiving an incoming message, executingsome actions and then generating an outgoing message. It is straightforward tospecify the service ordering relationship of the transitions in an FSM (or EFSM).An example of an FSM is illustrated in Figure 2.2. In this example, there arefour states and seven transitions. Each transition is labeled with its incomingand outgoing messages. The graph clearly shows the state-dependent service ofthe protocol. For example, when the protocol is in state 4, the only incomingmessage that can be served is 17 which is associated with the transition from state4 to state 1.Chapter 2: survey of related work 2311/01 12/02Nevertheless, FSMs alone are not perfect performance models for protocols.The problems of FSMs are:1. It is difficult to specify information about resources such as memory andCPU time, and to describe contention for shared resources.2. An FSM itself has no queue in its definition. So it is difficult for an FSMto describe the queueing behaviour of incoming messages of a protocol.Note that the disadvantages of FSMs in performance evaluation of protocolsare the advantages of QMs, and vice versa.In summary, although QMs and FSMs are not by themselves ideal performance models for communication protocols, QMs and FSMs offer complementaryfunctions. An FSM can be used to model the logic behaviour of a system which isstatic, while a queueing model can be used to model the service behaviour whichis dynamic. A combination of both can provide a good model for performanceanalysis of protocols. The performance extended finite state machine (PEFSM)Figure 2.2: An example of an FSMChapter 2: survey of related work 24which is described in the next chapter follows this approach.2.2.3 Specirying performance elementsWith the exception of QMs, all the above described models were initially developed to describe logical properties of a system. These models are not intendedfor performance analysis. Additional features have to be added so that essential performance aspects such as time and probability can be integrated into themodels. Examples include timed FSMs, timed Petri Nets, and time LOTOS. Inthis subsection, a brief survey is given on the integration of time and probabilityto formal models.Time and probability are the two major performance attributes used in currentperformance studies based on FDT specifications. Timing information is criticalfor performance. Almost all performance measures are related to time, such asthroughput, turnaround time, service delay time, queue wait time, response timeand interarrival time.Different kinds of time constraints have been used in FDTs. Examples include:• statement execution time [DeBu87, Qi88, Shaw89, FVV91, BaBu9l]• delay time [DeBu87, BoVa88, Qi88, DeBu89, BeDi9l, Shaw89, Groo9l]• timeout [Diaz82-1, BoVa88, DeBu89, Shaw89, QAF89j• response time [Qi88j• resource holding time [BoVa88]Chapter 2: survey of related work 25Time specifications take different forms in different modelling approaches.Generally speaking, there are at least three ways to specify time in a formalmodel or a formal specification:• timed statement [LiLi88, QAF89]• assertion with time [Shaw89j• data type with time [BoWi8OjIn addition to time, probability also plays an important role in performancecomputation. Many unpredictable factors affect communications performancesuch as job arrival patterns, service times and transmission errors.Briefly, there are two kinds of uncertainties in communication systems:• external uncertainties, and• internal uncertainties.External uncertainties refer to those that are not controllable by the systemsuch as job interarrival time and the class of the next arriving job. These external factors are usually modeled with probabilistic distributions or probabilities.Internal uncertainties are those that arise from inside a system because of nondeterministic choices. Probabilities are usually assigned to each possible choice.The traditional QMs do not provide any mechanism to model internal uncertainties. Most of the previous work using the models introduced earlier do notdistinguish these two uncertainties. For instance, in [KrWh93], only the transition probabilities of an FSM are considered. These transition probabilities areactually a combination of both uncertainties.Chapter 2: survey of related work 262.3 Analytic MethodsIn this section, we provide a brief survey of the major analytic techniques usedfor system performance.For each modelling approach discussed in the previous section, at least onemethodology has been developed to estimate system performance. The mostcommon methods are listed below:• Reachability Analysis (RA) [Krit86, LiLi88, BaBu9l, Jain9l, BeDi9l]• Markov Process (MP) [Klein75, GuRu89}• Queueing Theory (QT) [Klein75, SaCh8l, Allen9O]• Algebraic Theory (AT) [Nou85]• Temporal Logic and Proof Theory (TL) [Lamp9ljEach method is usually applicable to only a subset of the modelling approaches. Table 2.3 shows whether there is a known way of applying a particularmethodology to a given model.Similar to modelling methods, many analytic methods have to be enhancedwith time and probability so that realistic estimates of performance measurescan be computed. For example, reachability analysis is commonly used invalidation and verification of FSM or PN models of communication systems[Choi85, LiLi88j. This analysis technique is based on a (state) reachability graphin which nodes stand for states and edges represent transitions. Theoretically, itis possible to derive all the reachable states and thus analyze the properties ofChapter 2: survey of related work 27Table 2.1: The relationship of Modeling and Analysis approachesL ]RA MPEFSMY Y Y - -PN Y Y- Y -QM - Y Y - -TL - - - Y -AM - - Y Y YNotes: ‘Y’ means at least one paper has been published applying thisanalytic method to the model.‘-‘ means to our knowledge, there has been no work which hasapplied this analytic method to the specific model.a system. It has been proven effective in analyzing small to medium size systems. In order to use a reachability graph to reason about performance, timeand probability attributes have to be added to the graph. This results in a timereachability graph [LiLi88].The main problem of reachability analysis is state space explosion. The performance metrics which can be obtained are also very limited, mainly only through-puts and utilizations [LiLi88, BaBu9lj. To our knowledge, no work using thisapproach has derived queueing statistics.The theory of Markov Processes is another widely used method in performance evaluation based on FSMs. By adding time and probability to eachtransition (or state) of an FSM, it is straightforward to view the dynamicsof the system modeled as a kind of stochastic processes. The stochastic processes in this approach are usually assumed to be discrete-time Markov chains[GrDu87, KrWh93].Markov process analysis can also be applied to the algebraic model which isChapter 2: survey of related work 28not an FSM. Direct analyses of algebraic models for performance are difficult.Therefore, algebraic models are sometimes transformed into Markov processesbefore analysis. One example is reported in [Rico9l] where a LOTOS specificationis transformed into a Markov process. A LOTOS specification is described in aCCS-like communication algebra.Queueing Theory is a theory used to analyze queueing models. Queueingstatistics are important performance metrics for many systems. The queueingstatistics are obtained by studying the queueing process of the system. Queueingprocesses are mostly stochastic processes which are often more complex thanMarkov processes [Allen9OJ. In queueing theory, Little’s Law is almost alwaysemployed.Queueing theory provides a direct analytic technique for QMs. Performancemetrics are obtained via analyzing queueing processes. These measures includequeueing delay, queue length, server utilization, system residence time and throughput. Various approximation methods have been proposed to simplify the computation.Algebraic Theory is a branch of mathematics studying the use of variablesand operations relating the variables [West82]. The algebraic theory for communication is based on Hoare’s Communicating Sequential Processes (CSP) [Hoar78,Hoar85J and Mimer’s Calculus of Communicating Systems (CCS) [Miln8O, Mi1n89].Temporal Logic itself is not only a modelling tool but also an analytic tool.It inherits most of its inference rules from conventional logic which is the science ofproper reasoning. The properties of a computing system are expressed as logicalformulas, which can be reasoned or proved by using inference rules within a logicChapter 2: survey of related work 29system and can be used as invariants.2.4 Simulation ToolsGiven a performance model, performance evaluation can be achieved either byanalysis or simulation. This section presents some previous work on simulationtools.Simulators used for performance purposes may be classified into two categories: QM-based simulators and FDT-based simulators. The most traditionalperformance simulators are based on QMs. Recently, however, many FDT-basedsimulators have been developed to analyze performance of computer networksand communication protocols.2.4.1 Simulators based on FDTsA survey of FDT-based tools for protocol development is given in [Chan93aj.The paper provides a detailed classification of most of the existing tools basedon FDTs. As one can see, many simulation tools are not specifically designedfor performance analysis. However, some of them can be used for performanceevaluation with or without extensions.This subsection describes the simulators based on FDTs which can be adoptedfor performance evaluation.ANALYST is one of the earlier published tools which can be used to evaluate the performance of protocols [BargS6]. This system is the analysis engineof Columbia’s Unified Protocol Integrated Development environment (CUPID).ANALYST takes a CCS-like model of protocols and unifies both performanceChapter 2: survey of related work 30and functional analyses. Two aspects of protocol performance behaviour areaddressed: meeting timing requirements and computing performance measures.HIT is a performance modelling environment [Bei188J. [Heck9lj presents away to map an SDL2 specification to a model which HIT can accept using theHIT-SLANG language. In HIT-SLANG, the mapping of SDL components tocomputer resources and implementation-dependent parameters is given. Boththe SDL specification and the HIT-SLANG code are needed as inputs to thetool.PEW (Protocol Engineering Workbench) is an integrated tool for the design, testing and performance analysis of protocols specified in the Estelle FDT[KrWh89, WhKr9l]. The facilities provided in PEW are mainly for performanceanalysis. The FDT model in PEW is EFSM. The input is an Estelle specificationextended with times and probabilities to represent transitions.SDT is a design tool for SDL. More precisely, it is a Computer Aided SoftwareEngineering (CASE) tool used for real-time system development [Atle89]. SDTconsists of several modules such as a graphical editor, an analyzer and converter, asimulator and a report generator. SDT is not designed specifically for performanceevaluation purposes. However, some performance measures can be obtained byanalyzing the simulation results.TOPNET is a software package for simulating communication networks[Mars9O]. It is based on a class of timed Petri Nets called PPROT Nets [BrMa86].TOPNET allows graphical descriptions of the models, provides visualization ofthe dynamics of the simulation at run time, and presents the results graphically.2SDL is a formal description technique standardized by CCITT.Chapter 2: survey of related work 31TOP/PDT is a toolkit for the development of communication protocols.It is based on PDL, a specification language which is derived from SDL withadditional constructs. A set of functions is provided with the language PDL tocompute performance parameters. Below is one of the performance computationstatements provided by PDL:MEASURE quantity [LOCALLY I GENERALLY]PRINT [MEAN] [VARIANCE] [DEVIATION]WHEN conditionOne can define a performance metric in quantity and specify the condition underwhich the data of the metric is collected and analyzed. This statement is addedto a specification at the point where one wants to know a performance measure.Jo is an Estelle simulator for performance evaluation [FVV91]. It is based onEFSMs and allows the user to define transition execution and system evaluationtimes. The user can also control execution steps. The measurable performancemetrics are the CPU load and the average response time. The computable performance metrics are transmission delays, throughputs, processor loads, protocolefficiency and memory utilization.TSDL-Tool is an SDL based simulation tool for performance evaluation andvalidation [BaBu9l]. It takes as input a textual description in an extension ofSDL called timed TSDL and a control file which contains initial values of variablesand other parameters.EDT is a set of tools that help in the development of communication protocols[Budk92}. The tools include a compiler, a simulator and a debugger. EDT acceptsas input an Estelle specification which is essentially an EFSM. The prior version ofChapter 2: survey of related work 32EDT called EDB [Chari89b] could not do performance analysis. EDT is extendedto allow an Estelle specification with time parameters and thus some performancemetrics can be obtained.LOTO-SIM is a LOTOS based performance evaluation tool [Migu93]. Thetool takes as input a specification in a variant of LOTOS called LOTOS-TP, converts the specification into a LOTOS description and then compiles the LOTOSdescription into C for execution.2.4.2 Simulators based on queueing modelsSimulators based on QMs are used mainly to study queueing processes. Theperformance metrics obtained using these simulators are typically queue waittime, queue length, server utilization, system residence time and throughput rate.Queueing theory has been extensively studied and a number of simulatorshave been developed in the past several decades. Some of the most commonlyused tools are introduced below.Basically, simulators based on QMs can be classified into two categories: language embedded simulators and language independent simulators. Language embedded simulators are those which are integrated into a particular simulationlanguage. Simulation languages are similar to programming languages. A description of the system to be simulated is specified in the simulation language.This specification is then compiled into an executable simulator.GPSS is an example of a language embedded simulator. It is one of the mostwidely used simulators for discrete event systems. GPSS comes with a languagecalled GPSS V originally available on IBM mainframes. Later it evolved intoChapter 2: survey of related work 33GPSS/H which is a superset of GPSS V. GPSS/H is now available for a widerange of computers [Schr74, Schr9O]. Users describe queueing systems or queueingnetworks in GPSS/H which is then compiled into an executable form. Users canhave flexible control over the simulations by using control statements in the GPSSprogram.The Qsim tools also belong to the category of language embedded simulators.Qsim is used for creating and simulating queueing system models [Kimb89]. Themodels to be simulated are written in the programming language C. Some specialpurpose C functions, data structures, and macros such as DEFINE_QUEUE andcreate() are provided with Qsim. Qsim also provides many routines for computingspecial mathematical functions.Other language embedded simulators are SIMSCRIPT [DiMa64j, GASP[PrKi69] and DYNAMO [Pugh63]. [Nayl66J provides a chapter which surveysthe simulation languages.A language independent simulator takes as input the description of a QM tobe simulated and the description of the workload model. The workload modeltypically describes the arrival patterns and service time distributions. The twodescriptions are usually very simple and written in a specific format. This formatis typically not a programming language which has variable definitions. Thesimulator itself is fixed and the users do not have control over it. Typical amongthose are SimPack [Fish94], RESQ [SaMa85, KuGoS6], QNAP2 [VePo85j, andQ+ (or PAW) [MeMo85, Mela86j.SimPack is a set of tools that support experiments in computer simulation witha variety of model types. This simulation package is a public domain softwareChapter 2: survey of related work 34and is still under development. A graphical interface called Xsimcode comes withit and provides a user-friendly way to construct the model of the system to besimulated. The multimodel functionality of SimPact that allows users to specifymultiple models in one system is still under development.One generally needs some knowledge of mathematical statistics, probabilitytheory and differential equations in order to use the simulation tools that weredeveloped decades ago. Tools such as MAP [Lazo84j, RESQ [SaMa85, KuGo86]and QNAP2 [VePo85] are two of the most referenced tools which try to liberate the user from the requirement of being an expert in stochastic modellingand performance analysis. These tools adopt queueing networks together withsome extensions as the underlying specification technique, and employ analyticaltechniques as well as simulation.Language embedded simulators are more flexible than language independentsimulators. A language embedded simulator provides more functionality whichallows users to define controls on the simulator which can be applied throughout the simulation procedure. A language independent simulator does not havesuch fiexibilities, and the performance metrics which can be obtained from thesimulators of this kind are usually predefined.However, a language embedded simulator may introduce inaccuracies in thesimulation results. This is because the simulator allows a user to insert codewhich takes up some computational time. The user of the simulator normally isnot able to compensate for this effect.Chapter 2: survey of related work 352.4.3 Simulation tools based on multiple modelsThe simulation tools described above are based on one model only. For example,SimPack can model a queueing network which may have multiple nodes in thenetwork. However, all the nodes in the network are QMs. This limits the powerin modeffing computer networks. In a computer network, the nodes and the linksare best modeled as a QM. However, the protocol entity in each node controlshow the system operates. These control mechanisms are usually described asFSMs. So two types of models - FSMs and QMs- are needed in order to have amore accurate description of the system.Recently, some simulators which are based on multiple models have beendeveloped. Some examples are presented below.SMURPH (a System for Modeling Unslotted Real-time PHenomena) is apackage for simulating communication protocols at the medium access control(MAC) level. A simulation program in SMURPH is a combination of a protocolspecification language based on C++ and an event-driven, discrete-time simulator that provides a virtual environment for protocol execution. SMURPH canbe used in designing low-level communication protocols and investigating theirquantitative and qualitative properties.Ptolemy is a system-level design framework that allows a combination ofmultiple models in a computation [PTOLEMY]. Ptolemy covers practically allaspects of designing signal processing and communication systems, ranging fromthe design of algorithms and communication strategies, to simulation, hardwareand software design, parallel computing, and real-time prototyping. This toolis a powerful and versatile system and is about 80 MB in size. The tool canChapter 2: survey of related work 36even model VLSI circuits and power networks. A significant part of the Ptolemycode has to do with interaction between diverse models of computation. Theformal models which can be handled in Ptolemy include the synchronous dataflow models, the Boolean data flow models, and stochastic processes.Another huge and powerful tool kit for network performance modelling, analysis and simulation is known as OPNET [OPNET]. OPNET is similar to TOP-NET with respect to the hierarchical modelling ability. OPNET can integrateand simulate a system comprising of QNs and FSMs at different levels which arecalled domains. The tool allows three domains: process, node and network, andis more sophisticated than most conventional tools. For instance, in traditionalqueueing networks, each node is usually modeled as a single-server queueing system without further detailed description. However, in OPNET, one can easilydefine control schemes such as communication FSMs for flow control, rate control and congestion control as processes in a node. Furthermore, in each FSM,one can model in detail transition times and transition firing rates. Queues canbe defined in at least two levels: process and node domains. This allows morerealistic modelling of computer networks.The construction of network models and FSMs can be easily done in a providedgraphical environment similar to XFig or MacDraw. The OPNET package haslibraries for some networks and protocols like X.25 and TCP/IP. OPNET isquite flexible and the queueing network models are not necessarily restrictedto computer networks.Chapter 2: survey of related work 372.5 SummaryWe have outlined some prior work on performance evaluation using formal modelssuch as QMs and FSMs. Each performance model has its advantages and disadvantages in modelling communication protocols. Among the models introduced,QM and FSM complement each other in that the strengths of one model are theweaknesses of the other and vice versa. Therefore, a hybrid model combiningboth QM and FSM will be a good performance model for protocols.In this chapter, both analytical methods and simulation tools based on formalmodels have been surveyed. As can be seen, more and more simulators are capableof supporting more than one type of model. A typical example is the newlyreleased OPNET. Comparatively, much less work using multiple models has beendone in analytic approaches, although [KrWh93j made an attempt along thisdirection.Simulation approaches have many advantages over analytic approaches. Forexample, simulation is able to model the system more realistically. However, it isdifficult for a simulator to obtain performance relations such as server saturationcondition. A simulation result is numeric and is for a specific set of systemand workload parameters. Although analytic approaches may be less accuratedue to inevitable simplifying assumptions, the analytic results are very usefulbecause they provide more general answers to the behaviours of the analyzedsystems. This thesis investigates an analytic approach using a hybrid model toachieve better accuracy in modelling without introducing more complexity incomputation than the traditional approaches.Chapter 3A New Performance ModelAbstractA new performance model called Performance Extended Finite State Machine (PEFSM)is presented in this chapter. A PEFSM is defined as a finite state machine (FSM) extended with two performance elements— time and probability— on each of the transitionsin the FSM. The stochastic process of state changes in a PEFSM is defined. In addition,three other embedded stochastic processes of the PEFSM are defined and their relationships are examined. Moreover, according to the arrival characteristics of incomingmessages, PEFSMs are classified into three categories: synchronous PEFSMs (SyPEFSMs), asynchronous PEFSMs (AsPEFSMs) and hybrid PEFSMs (HyPEFSMs).3.1 IntroductionAs discussed in Chapter 2, the finite state machine (FSM) is a formal descriptiontechnique (FDT) having many advantages in performance modelling of communication protocols. An FSM consists of a set of states, a set of input symbols, a38Chapter 3: a new performance model 39set of output symbols, and a set of state change rules called transitions. All thesesets are finite.FSMs can be used to model various computer hardware and software systemsranging from compilers to communication protocols. Our focus is on communication protocols. For the rest of the thesis, one should keep in mind that theunderlying systems to be modelled by FSMs are communication protocols exceptwhen otherwise indicated.A communication protocol embeds a set of control mechanisms such as flowcontrol, rate control and congestion control. Each control mechanism is an FSMor an FSM extended with variables. Figure 3.1 shows graphically the FSM ofthe transmitter of a simple communication protocol. This protocol is known asthe alternating bit protocol1 in [Tane88](p.229) and is one of the most referencedprotocols in the literature. The protocol consists of one transmitter and onereceiver. Only the FSM of the transmitter is shown in Figure 3.1.Figure 3.2 depicts the FSM of another popular but more complex protocolcalled CCITT/ISO X.25 LAPB [ISO7776J. In this example, the FSM modelsboth the transmitter and the receiver.A protocol entity may consist of more than one FSM. These FSMs can becombined as one FSM. We assume only one FSM in a protocol entity hereafter.When the FSM of a protocol starts running and communicating with others,it typically receives input symbols one after another. When an FSM has finishedprocessing one symbol and generating the corresponding output symbol if there isone, the FSM changes its state. The next state can be the same as the current one.‘The alternating bit protocol is also called the stop arid wait protocol.Chapter 3: a new performance model 40Thi: DATA/DATASTATES:state 0: idlestate 1: waitingforACK(acknowledgement)Ti 1: timeout/DATATRANSITIONS:TOl : sending a DATA packetTiO: receiving an ACKTi 1: timeout retransmissionFigure 3.1: An FSM of the alternating bit protocolThis next state of the FSM usually depends on the current state, the current inputsymbol, and the selection rule(s) when more than one input symbol is available.The current input symbol is generally unpredictable and thus the next state israndom. As a result, the process of state change is actually a stochastic process.Properly modelling and analyzing the state changing process of the FSM ofa protocol is important. It provides a means to obtain the performance of theFSM.Treating an FSM of a communication protocol as a stochastic process forperformance analysis is not new. For example, [KrWh93] transformed an FSMinto a transition relation graph and then analyzed the graph as a discrete-timesemi-Markov process. The transition relation graph of an FSM is in fact alsoan FSM except that the states and the transitions in the original FSM becomethe transitions and the states in the graph, respectively. More discussion on thisparadigm can be found in Chapter 2.T10: ACK/Chapter 3: a new performance model 41Although most of the previous work on performance modelling is based onFSMs, there exist two problems in general. One problem is that they do not modelthe arrival processes of input symbols. Without considering any arrival process,the previous work assumes that input symbols to an FSM are always availableat any time and idle periods due to arrival delays do not exist. Therefore, theperformance measures obtained from the existing research are mostly bounds.Another common problem is that no queueing process due to service delaysis considered. Queueing delays are important performance indices for many corn-Nai.uI*ti(-.ASP):iioPVU,mDdu.on4noPDtJoASP)TflY:T.TI.o.._,jTIJ):.TIFigure 3.2: An FSM of CCITT/ISO X.25 LAPBChapter 3: a new performance model 42puter systems. Without considering queueing process, queue wait times of inputsymbols due to processing delays of other symbols cannot be computed. In asynchronous systems, a request may arrive at any time and may have to wait its turnto receive service.Both these two processes— the arrival process and the queueing process — arein fact very important in providing accurate modelling for a realistic FSM andobtaining performance measures for the FSM.To incorporate these two important performance aspects in the FSM formalism, we propose a new performance model called Performance Eztended FSM(PEFSM) in this chapter. A PEFSM is an FSM extended with time and probability on its transitions. The time of a transition is further refined and dividedinto two parts: the time to wait for the input symbol associated with the transition and the time to process the symbol and the transition. Defined in this way,a PEFSM models the stochastic process of state change in an FSM accurately.The formal definitions of PEFSM and its related models are given in thischapter. A brief mathematical background which introduces stochastic processesand the related theory is provided in Appendix A. It is intended to help thereader understand the PEFSMs and the analyses in the later chapters.The rest of this chapter is organized as follows. It starts with a formal definition of an FSM in Section 3.2. Readers who are already familiar with FSMscan skip this section. Section 3.3 presents the definitions of the new performancemodel— PEFSM. Section 3.4 outlines a classification of PEFSMs according tothe arrival characteristics of the input symbols. Section 3.5 discusses three embedded processes of a PEFSM and their relationships. Section 3.6 wraps up theChapter 3: a new performance model 43chapter.3.2 Finite State Machine (FSM)A finite state machine (FSM) is formally defined as a six-tupleM = (Q,I,O,5,,qo) (3.1)where Q — a finite set denoting states;I— a finite set denoting input symbols;0 — a finite set denoting output symbols;6 — a function denoting transitions;— a function denoting transition outputs;q0 — an initial state.6 is a function from Q x I to Q. is a function from Q x I to 0. And q E Q.The FSMs defined above are essentially Mealy machines [HoU179J.A directed graph can be used to present an FSM graphically. Figures 3.1and 3.2 are examples of FSMs. For the sake of simplicity, an abstract FSM inFigure 3.3 is used to illustrate the contents of each component of an FSM:Q = {1,2,3};I = {In,I12,I21,I23,I31};0 = {011,012,021,023,031};6 : 6(1,I) = 1, 6(1, 112) = 2, 6(2, 121) = 1,6(2, 123) = 3, 6(3,I) = 1;= (1,I) = 011, (1,Ij2) = 012, (2,I21) = 021,Chapter 3: a new performance model 44= 1.(2,‘23) = 023, (3, 131) = 03k;Ii i/Oil 112/012Figure 3.3: An abstract FSMNote that an FSM of a communication protocol does not necessarily have anyfinal state. This is because the execution of an FSM can span over an infiniteperiod of time without termination.3.3 PEFSM: a new performance modelBefore giving the formal definition of PEFSM, we start with the definitions ofthe related terms.3.3.1 Classification of messagesIn the domain of communications, the data which a protocol receives and thedata which the protocol outputs are often called messages. We shall use I of anFSM to refer to the set of incoming message classes to the FSM and 0 to the setof outgoing message classes generated from the FSM.131/OilChapter 3: a new performance model 45From the definition of FSM in Equation (3.1), each incoming message classof an FSM is associated with a transition. We assume that FSMs in this thesisare deterministic. For a deterministic FSM, the mapping between the incomingmessage classes of an FSM and the transitions of the FSM is one-to-one, so is themapping between the outgoing message classes and the transitions of an FSM.Therefore, each class of incoming messages of an FSM is uniquely identifiedwith the identifier of the transition associated with the messages. A transitionidentifier of an FSM usually consists of the transition’s starting state index andthe ending state index. For instance, transition ij identifies the transition fromstate i to state j. Hence, incoming message class ij (or class ij where no ambiguity occurs) refers to the incoming message class associated with transition ij,i.e.,Ii., = {x6(i,x) =j}where I E I and x represents an incoming message; outgoing message classij (or class ij where no ambiguity occurs) refers to the outgoing message classassociated with transition ij, i.e.,= {ylx E I & (i,x) = y}where O, E 0 and y represents an outgoing message.An incoming message of class ij of an FSM is called a firable message of statei in the FSM, or a firable message when the FSM is in state i.3.3.2 Transition timeWhen a firable message is selected by an FSM, the transition associated with thismessage will be processed. In other words, the FSM is making a state transition.Chapter 3: a new performance model 46Each transition is associated with a transition time which is the time period fromthe start to the completion of the transition. In general, a transition time fromstate i to j consists of two parts: the transition wait time and the transitionservice time. The transition wait time is the time to wait for a firable message ofclass ij and the transition service time is the time to service transition ij.Let ‘rjj, and denote the transition time, the transition wait time andthe transition service time of transition ij, respectively. Formally, br3 is writtenas“ru = rij +To define ‘t’Tj, and precisely, we first define the time instant of anFSM leaving state i and entering state j.Definition 3.1 (leaving and entering a state) The time instant of an FSMleaving state i and entering state j is the epoch when the service of transition ijis completed.Definition 3.1 precisely defines when a transition of an FSM begins and ends.Definition 3.2 (transition time) The transition time from state i to j in anFSM, is the interval between the time when the FSM enters state i and thetime when the FSM enters state j.Definition 3.3 (transition wait time) The transition wait time from state ito j in an FSM, is the interval between the time when the FSM entersstate i and the time when the FSM receives an incoming message associated withtransition ij and begins to process the message.Definition 3.4 (transition service time) The transition service time from stateChapter 3: a new performance model 47i to j of an FSM, 8rj, is the time to execute the computer instructions specifiedin transition ij.Note that “rj is neither negative nor constant. It depends on the workload.The transition wait time is not the time due to queueing either. Any wait timedue to queueing will be called queue wait time defined later in the thesis.S3 is also the service time of an incoming message of class ij. So 5r, includessome necessary processing time for a message such as checksum computation time.Figure 3.4 shows graphically the components of a transition time.enter state jenter state i leave state i‘ftI I Ik.I I I) II I Ia-TimeFSMFigure 3.4: The components of a transition timeAccording to the above definitions, it is not difficult to see that is zerowhen the FSM enters state i and a firable message of class ij is immediatelyexecuted. In this case, ‘-r =Often, the transition time in an FSM is longer than the associated servicetime, i.e., ‘t’rj > S23 This is because firable messages of a state of an FSM maynot always be immediately available when the FSM enters that state. Waitingfor a firable message is inevitable when an FSM enters a state but finds no firablemessage in this state.Chapter 3: a new performance model 483.3.3 State occupancy and stochastic processDefinition 3.1 precisely defines when an FSM enters and leaves a state. Withthis, we are now able to define the state holding time and the state occupancy ofan FSM, and specify the trajectory of the occupied states.Definition 3.5 (state holding time) The holding time of state i in an FSM(i e Q) is the interval between the time when the FSM enters state i and the timewhen the service of a transition starting from state i is completed.Definition 3.6 (state occupancy) An occupancy of state i by an FSM is anevent covering the period from the time when the FSM enters state i to the timewhen the service of the first transition starting from state i is completed. In otherwords, it describes the state the FSM is in, and the holding time of that state.According to the definition of FSM in Equation (3.1), a self-loop transitionfrom state i to i (i E Q) may occur in an FSM. If an FSM has a self-loop transitionfrom state i to i and the transition is selected, then the FSM is considered toenter state i again (i.e. one more time) when the service of this transition iscompleted.For a protocol in execution, its FSM goes through a sequence of state changes.This process is known as the state changing process of the FSM.The state changing process of an FSM cannot be fully predetermined. Thisis because a transition wait time WT and a transition service time S (i, j E Q)are not constant in actual practice. In general, and can be regarded asrandom variables. This means the holding time of the current state of an FSMis also a random variable. Moreover, before a transition of an FSM is selected,the next state of the FSM is also unknown. The selection of the next transitionChapter 3: a new performance model 49of an FSM depends on the current state of the FSM, the set of available firablemessages of the current state, and the transition selection policy which deals withthe case when more than one firable message of the current state is available.In particular, whether or not a firable message in the current state is availabledepends on the arrival model of the FSM which is usually a random process.All these uncertainties indicate that there are several random factors whichcollectively determine which next state an FSM is in and when. Consequently,the states occupied by an FSM over the time are a family of values of a randomvariable related to time. Therefore, the state changing process of an FSM is astochastic process. We denote this stochastic process as {X(t)It O}, whereX(t) E Q and Q is the set of the states of the FSM. X(t) represents the statethat FSM occupies at time t. X is called the state variable of the FSM and Q isthe state space of X. Obviously, the values of X are discrete and finite.To characterize the possibility of the next state which an FSM enters, weintroduce the single-step transition probability.Definition 3.7 (single-step transition probability) The single-step transition probability Pij of an FSM is the probability that state j will be the next statewhen the FSM enters state i, i.e.,Pij = Pr{X÷1= jIX = i}where X,- and X1 denote the current state and the next state, respectively.To be general, we assume that the times, W3 and 8r, (i, E Q) of an FSMare continuous. As such, (i, j E Q) are also continuous.Chapter 3: a new performance model 50The state changing stochastic process of an FSM, {X(t)It 0}, is a continuous-time semi-Markov process (CSMP)2 when the next state of the FSM does notdepend on the states occupied by the FSM other than the current state. In otherwords, if all Pu, and 5r, (i, j E Q) are independent of the past history ofX(t), X(t) is a CSMP. CSMP is commonly used in describing realistic systemsas demonstrated in the next three chapters.3.3.4 Formal definition of PEFSMWe have described in the previous section how an FSM extended with time andprobability can model the stochastic process of the state changes of the FSM.Since both time and probability are needed to model performance, we call anFSM with this extension a performance extended FSM (PEFSM).Formally, a PEFSM, denoted as ‘I’, is defined as a pair(M, 2) (3.2)where M= (Q, 1,0,6, , qo) is the kernel which is an FSM whose formal definitionis given in (3.1), and P = (P, ‘H, 8}{) is the running environment expressed interms of time and probability. The components of P areP— a matrix of the single-step transition probabilities;— a matrix of the probability density functions (p.d.f.s) of the transition wait times;— a matrix of the p.d.f.s of the transition service times.In a PEFSM, M, P, H and H are primitive data. M and H are assumedto be provided directly by the performance evaluator. P and ¶H will be derived2The formal definition of CSMP is given in Appendix A.Chapter 3: a new performance model 51from M, H and the more primitive data which are the arrival and service modelswhen P and ILH are not directly given.Let P = [pjj;1L7[{ [wh(t)J;=[3h23(t)];{X(t), t O} be the state change process of the PEFSM (definedin Section 3.3.3);t0,t1, ..., t,, ... be the sequence of the epochs right before the processing of a transition is completed;Xo, X1, ..., X, ... be the sequence of the states in the PEFSM corresponding to the time instant sequencet0, t1, t2, ..., t,, ..., respectively.The components of a PEFSM and their relationships are formally defined inthe following:1. X(t)eQforalltO.2. X(O) = Xo = q0.3. X,, = X(t;) and X,1 = X(t).4. Pr{X+i = iIX = i} = Pij•5• Wh(t) is the p.d.f. of i.e. Pr{ = = i, X1 = j} = wh(t).6. 3h22(t) is the p.d.f. of 3rj, i.e. Pr{ S2, = = i, X,÷1 = j} =7. If X,, = i and X,1 = j, then— t_1 = = “rtj + 8i-,, (n 1).3t; denotes the epoch right before the time instant t. t; <t but t; is infinitely close totn.Chapter 3: a new performance model 528. Let X,1 = i. If there is no available firable message in state i at t, thenthe PEFSM waits. If j is the next state after i, then the waiting time is W•This means that during the period [ta, t, + wr2), the PEFSM is idle andduring the period [t + + + transition ij is being processed.One can clearly see from the above that the trajectory of the state variableX of a PEFSM is governed by M, P, UH and H. M determines the state spaceof X and the possible next value of X statically. The others realize the dynamiccontrol of X.By the definition of PEFSM, M and f{ of a PEFSM are the primitive datawhich are independent of the state variable X of the PEFSM. Therefore, if thestate changing process of a PEFSM is a CSMP, P and ‘1H of the PEFSM shouldnot depend on the past state occupancies of the PEFSM. However, P and “Hof a PEFSM are determined by the arrival model of incoming messages to thePEFSM as well as the service model of the PEFSM which defines the selectionrules to choose a firable message to process at each state. Therefore, in orderto make the state changing process a CSMP, it is necessary to restrict both thearrival and service models with additional assumptions. These assumptions aregiven in the later chapters where each specific class of PEFSMs is described.The arrival model of a PEFSM specifies the arrival patterns of incoming messages. We note that the arrival patterns are closely related to the type of communication, synchronous, asynchronous or a combination of the two. In the nextsection, these three types of communication and their impacts on PEFSMs arediscussed.Chapter 3: a new performance model 533.4 Synchronous, Asynchronous and Hybrid PEFSMsSynchronizations may occur during communication when the participants rendezvous with each other at one or more points. When the FSM model is used,the points of rendezvous are usually defined as states in the FSM called synchronization states. Synchronizations in communication are often realized throughmessages exchanges. From the PEFSM point of view, the firable messages of asynchronization state arrive only after the PEFSM enters this state. Incomingmessages which are not of this type can arrive at any time. Therefore, two typesof message arrivals are possible:Definition 3.8 (synchronous arrival) The arrival model of incoming messagesto a PEFSM is synchronous if these messages arrive only when the PEFSM is ina synchronization state.Definition 3.9 (asynchronous arrival) The arrival model of incoming messages to a PEFSM is asynchronous if these messages arrive regardless of thecurrent state of the PEFSM.The distinction of incoming messages to PEFSMs according to synchronousand asynchronous arrivals gives rise to the following classification of PEFSMs:1. If all the incoming messages of a PEFSM arrive synchronously, the PEFSMis called a synchronous PEFSM (SyPEFSM).In a SyPEFSM, the next incoming message does not arrive before all thepreviously arrived messages have been processed and the outgoing messages(if any) have been sent. Whenever the SyPEFSM enters a state, it mustChapter 3: a new performance model 54wait for a firable message in the state. In this sense, the SyPEFSM issynchronized in each state. This also implies that no queue is needed forany incoming message of a SyPEFSM and consequently there is no queuewait time for each incoming message in a SyPEFSM.A simple example of a SyPEFSM is the FSM of a protocol called hot-potato protocol. A formal specification in Estelle of this protocol is given inAppendix D. This protocol describes the procedure of a team of memberstossing a hot potato among themselves in a circle. Each member catchesthe hot potato with his/her left hand from the member on his/her left side,passes it over to his/her right hand and then tosses it to the member onhis/her right side. Each member can be represented using an FSM. Oneexample of the FSMs is shown in Figure 3.5. There are two states in anFSM. State 0 stands for a member’s his/her left hand waiting to catch apotato, and state 1 for the member’s his/her right hand waiting to catch apotato. Il occurs only after the FSM enters state 0; 12 occurs only afterthe FSM enters state 1. Obviously, the PEFSM of this FSM is a SyPEFSM.Other examples of SyPEFSM include the PEFSMs of the communicationprotocols which assume zero buffer for incoming messages [HsWa94]. APEFSM of this type has to wait for a firable message in every state.2. If all the incoming messages of a PEFSM arrive asynchronously, the PEFSMis called an asynchronous PEFSM (AsPEFSM).Obviously, an AsPEFSM allows incoming messages to arrive before all thepreviously arrived messages have been processed. We assume that a firablemessage of a state in an AsPEFSM that arrives before the system is readyChapter 3: a new performance model 5511101(EEEEZ12/02II-- catch the hot-potato with the left hand from the member on the left side01 — pass the hot-potato to the right hand12 — catch the hot-potato with the right hand02— toss the hot-potato to the member on the right sidestate 0 -- the player has no potato and his/her left hand is waiting for a potatostate 1 --the player has a potato and his/her right hand is waiting for a potatoFigure 3.5: An FSM of the hot potato protocolto process it is buffered in a queue. If a firable message in a state is foundin the queue when the AsPEFSM enters this state, there is zero transitionwait time. However, this situation does not always occur in general, especially when the workload of the communication is light. In other words,AsPEFSMs may have to wait for a firable message in the same way thatSyPEFSMs do.An example of an AsPEFSM is the two-state FSM shown in Figure 3.6(a).This FSM models a switch processing the traffic data of ON-OFF Markovsources in an ATM network. The traffic model of ON-OFF Markov sourcesshown in Figure 3.6(b) is a well-known data model used in studying thebehavior of ATM networks [AtMa93, HsWa94j. In this example, two typesof data generated at different rates are modelled: video and text. Bothtypes of data come to an ATM switch asynchronously from different senders.Therefore, the service model of an ATM switch given in Figure 3.6(a) is anChapter 3: a new performance model 56AsPEFSM.11,14— receiving video data01,04— serving video data12,13— receiving text data02.03 - serving text datastate 0— system is in real-time modestate 1 -- system is in normal mode(a) an FSM for processing two sources of data> generatevideodataatahighrate. generate text data at a low rate(b) ON-OFF Markov sources of traffic modelFigure 3.6: An FSM of an ATM serving two types of data3. If a PEFSM has both synchronous and asynchronous incoming messages,the PEFSM is known as a hybrid PEFSM (HyPEFSM).In reality, incoming messages to the FSM of a protocol are often a combination of synchronous and asynchronous messages. For instance, the messages13/03Chapter 3: a new performance model 57for handshaking during a connection setup in the LAPB protocol [1S07776]and the messages for timeout in the same protocol are usually synchronousbecause they only arrive when the protocol is in certain states. The commands and data from the protocol user (or more generally, from the upperlayer of the protocol stack) are usually asynchronous because they may arrive without foreknowledge of the current state of the protocol. The FSMsof this kind of protocols are HyPEFSMs.The FSM shown in Figure 3.1 can be an example of a HyPEFSM. We assume that the data to be transmitted comes to this FSM asynchronously.The FSM always waits for an acknowledgement (ACK) from the receivereach time it sends out a packet of data. A timer is set after each datatransmission. When a timeout occurs, the unacknowledged data is retransmitted. The timeout value is assumed to be large enough that no delayedACK will arrive after a timeout. As a result, the timeout events come tothis FSM synchronously. Therefore, both synchronous and asynchronousincoming messages are sent to this FSM, making it a HyPEFSM.We have seen that PEFSMs are classified into three categories according tothe two types of arrival patterns of incoming messages— synchronous and asynchronous. Likewise, we define two types of transitions:Definition 3.10 (synchronous transition) A transition of a PEFSM is a synchronous transition if the message arrivals for the transition are synchronous.Definition 3.11 (asynchronous transition) A transition of a PEFSM is anasynchronous transition if the message arrivals for the transition are asynchronous.Chapter 3: a new performance model 58In a SyPEFSM, all the transitions are synchronous transitions. In an AsPEFSM, all the transitions are asynchronous transitions. In a HyPEFSM, thereare both synchronous and asynchronous transitions.We have mentioned in the definition of PEFSM that P and ‘H of a PEFSMare assumed to be given directly by the performance evaluator or computed fromthe information provided by the performance evaluator. The former case usuallyapplies in SyPEFSMs and the latter one in AsPEFSMs and HyPEFSMs. Differentarrival models make the computations of ‘H for a PEFSM very different. Thiswill be discussed in subsequent chapters.3.5 Embedded Stochastic Processes of a PEFSMThe state changing process of a PEFSM, {X(t), t O}, embeds many stochasticprocesses. This section discusses three of them and investigates their relationships. These processes are used in the performance evaluation studies in theremaining chapters of the thesis.3.5.1 Pure state changing process (Model E)If all the transition times in a PEFSM are ignored, i.e., only the instant valuesof X (t) right before the completion of each transition are considered, then thestochastic process of the PEFSM, {X(t), t O}, is a Markov process (MP). Thisis equivalent to the assumption that the values of the random variables of aPEFSM, W. and 8T (i,j E Q), are all zero. With this assumption, the statechanging process in fact describes only the sequence of the states entered by thePEFSM. We call this process the pure state changing process and denote it asChapter 3: a new performance model 59Model E.Formally, Model E of a PEFSM is defined as:E—(M,P) (3.3)where M and P are as defined in Equation 3.2.3.5.2 Pure service delay process (Model S)If the firable messages of a PEFSM are always immediately available, i.e., W o(i,j E Q), the state changing process of the PEFSM, {X(t),t O}, is a stochasticprocess, which depicts only the service delays (i.e., the transition service time) ateach state of the PEFSM in addition to the state changes. We call this processthe pure service delay process and denote it as Model S.Formally, Model S of a PEFSM is defined as= (M,P, SH) (3.4)where M, P and ‘H are as defined in Equation 3.2.3.5.3 Pure wait process (Model W)If the transition service times of a PEFSM are always zero, i.e., 8r 0, the statechanging process of the PEFSM, {X(t), t 0}, forms a stochastic process whichcharacterizes the wait times of the PEFSM for incoming messages at each state.We call this process the pure wait process of the PEFSM and denote it as Modelw.Chapter 3: a new performance model 60112Figure 3.7: Model W of the PEFSM in Figure 3.3Formally, Model W of a PFSM is defined asW=(M,P, tLH) (3.5)where M, P and H are as defined before in Equation 3.2.Figure 3.7 shows a graph of Model W of the PEFSM given in Figure 3.3. Inthe model, all outputs are removed from the transitions to denote the exclusionsof the transition services in Model W.A transition in W starts immediately after its start state is entered and endswhen a firable message of the state is received. The transition times of ModelW of a PEFSM are simply the transition wait times of the PEFSM. Duringthe transition wait times, the PEFSM is essentially idling. Therefore, Model Wdepicts the idle times of the PEFSM.3.5.4 RelationshipsFirst of all, Model E, Model W, Model S and W of a PEFSM share the samecomponents:‘31Chapter 3: a new performance model 61• the states;• the transitions;• the single-step transition probabilities.We define the steady-state state probability of state i in a stochastic process isthe probabifity that the process is seen in state i at state changing instants by anarbitrary observer after the process runs a very long time and is in steady state.4Let 7r be this probability. 7r can be computed by solving the following matrixequationand= 1iEQwhere ir = [7rJ (i e Q). The proof is given in Appendix A. Since P is the samefor E, W, S and W, these stochastic processes always have the same steady-statestate probabilities.Let H = [‘h2(t)] be the matrix of the p.d.f. of the state holding times ofthe PEFSM. Since ‘1’r, = + 3r23, and and S, are independent, thereforeh(t)=lVh(r). — r) . dr.In the extreme case when the PEFSM has no idle time and never waits forany firable message, then= 3h23(t)4The steady-state state probability is also the stationary state probability.Chapter 3: a new performance model 62and12J — T3•In this case, the PEFSM behaves as in Model S. If = is used to denote thisbehaviour equivalence, we can write in short• r23_sr, (i,jeQ).Likewise, by the definitions of W and E, we can also write• I1zWif sTEO,i.e. TjEWTjj (i,jeQ).• ‘I’Eif both wrjOand (i,jeQ).In general, when a PEFSM arrives at a state, if at least one firable message inthis state is already available, the PEFSM will immediately execute the transitionassociated with the message; otherwise the PEFSM waits for the first firablemessage. After having received a firable message and processed the correspondingtransition, the PEFSM then changes its state to the end state of the transition.Since waiting may occur, in general, it is always true that..>sT.. (..—o1TzJ— 2)where r3 and S.23 are as defined earlier in the chapter.If ‘P is a CSMP, Model E is a Markov process (MP). E is also a Markovchain (MC). This is because its state space Q, by definition, is finite and discrete.Furthermore, this Markov chain is irreducible because every state in the FSM isreachable from the idle state in a correct communication protocol, and after asequence of transitions, the system always returns to the idle state. And thisChapter 3: a new performance model 63FSM is positive recurrent because the number of states in Q is finite [Mo1189b].If we further assume that E is aperiodic5,then it is ergodic [Allen9O].When E of a PEFSM is ergodic and the running time of the PEFSM approaches infinity, E will achieve equilibrium (or steady-state). In this case, limiting state probabilities exist which are the probabilities that the FSM is seenin each state by an arbitrary observer at any time, and they are equal to thesteady-state state probabilities, r = [irJ (i E Q).3.6 SummaryThe formal definitions of a new performance model— PEFSM (denoted by ‘I’),its embedded models E, W and S, and their relationships— have been presented.Two types of message arrivals — synchronous and asynchronous— and theireffects on PEFSMs have also been discussed. With this distinction, PEFSMsare classified into three categories: SyPEFSMs, AsPEFSMs and HyPEFSMs.This classification determines the performance indices of interest to each class ofPEFSMs. For instance, throughput of a specific outgoing messages is importantto all types of PEFSMs; queueing statistics do not make sense to SyPEFSMsat all but are very important to AsPEFSMs and HyPEFSMs. All prematurelyarrived firable messages to an AsPEFSM or HyPEFSM are buffered. Therefore,any measure involving the queues is a useful performance index to an AsPEFSMor a HyPEFSM.5This assumption is not necessary for ‘I’ being a CSMP if the times of the PEFSM arecontinuous random variables [GrHaS5] (p.52). Moreover, this assumption can also be eliminatedfor E if there exists a reset in the communication protocol specified by the PEFSM at theprotocol’s initial state. This reset forms a self-loop transition in E.Chapter 3: a new performance model 64The state changing stochastic processes modelled by PEFSMs in this studyare very general. The distributions of transition service times are not as restrictedas in previous work. Only the message arrival times will have some restrictionsimposed on them to qualify the stochastic processes as CSMPs which are easy tocompute. These restrictions will be introduced in the next three chapters.One of the major differences between our models and those in earlier work isthat the waiting times for incoming messages on each transition of an FSM aredefined as a component in the transition time. By doing so, arrival models (orworkload models) can be integrated in our models. In addition, the queues of aPEFSM can also be modelled and associated with each incoming message class.Details are discussed in the later chapters.In short, this model makes our approach more realistic and accurate. Moreperformance indices can be obtained and even the properties of these indices suchas the probability distributions can be derived through analysis.In the next three chapters, we show how to derive the performance metrics forsynchronous, asynchronous and hybrid PEFSMs, respectively. While the hybridmodel is the most useful and realistic model for communication protocols, theother two models are also presented for completeness, and as a way to explainthe hybrid model.Chapter 4Performance Evaluation ofSynchronous PEFSMsAbstractA synchronous PEFSM (SyPEFSM) is a PEFSM where the arrivals of all incomingmessages are synchronized. This chapter analyzes statistical properties of a SyPEFSMand derives some performance measures for the SyPEFSM. While practical examples ofSyPEFSMs are not common, SyPEFSMs are interesting in their own right and usefulin understanding HyPEFSMs.4.1 IntroductionA synchronous PEFSM (SyPEFSM) is a type of PEFSM where the incomingmessages arrive synchronously. When a SyPEFSM enters a state, it has to waitfor a firable message of this state. There is no queue wait of any incoming message.The notations used to define PEFSM and SyPEFSM in the previous chapter65Chapter 4: performance evaluation of SyPEFSMs 66are also used in this chapter. Formally, a SyPEFSM is denoted by ‘I’, and‘I’ =(M,P)whereM and 3H of a SyPEFSM are primitive data and are presumably given bythe performance evaluator. P and ¶11 are related to the message arrival modelof a SyPEFSM. A message arrival model is important to a SyPEFSM from theperformance evaluation point of view, because the arrival model characterizes thetraffic pattern of the incoming messages. The arrival model is in fact a workloadmodel which directly influences the performance of a SyPEFSM. The arrivalmodel is therefore needed in computing any performance measures.As long as M, 3H, P and ‘H are known, the state changing stochastic processof the SyPEFSM can be analyzed and the performance of the SyPEFSM can beevaluated.The performance metrics of a SyPEFSM include the state holding time, therecurrence time of a state, the throughput of the outgoing messages of a specificclass and the utilization. The derivation of these performance metrics is presented in this chapter. Furthermore, the bounds of the performance measures ofa SyPEFSM are also obtained by analyzing Model S.The rest of this chapter is organized as follows. Section 4.2 provides a message arrival model for SyPEFSMs. Section 4.3 presents the derivations of someperformance metrics with the given message arrival model. Section 4.4 discussesthe related work on performance modelling and analysis by treating an FSM asa semi-Markov process. Section 4.5 summarizes the chapter.Chapter 4: performance evaluation of SyPEFSMs 674.2 Message Arrival ModelAccording to the definition of a SyPEFSM in Chapter 3, the SyPEFSM alwayshas to wait for a firable message at every state since any message firable at astate arriving before the state is entered will be discarded. In general, neither theclass of the next firable message nor the time when the next firable message willarrive is deterministic. Therefore, it is useful and natural to assume an arrivalmodel which consists of the probabilities of each class of the firable messages ofa state and the p.d.f.s of the wait times for each class of firable messages in eachstate. These are the transition probabilities, P, and the p.d.f.s of the transitionwaiting times of the SyPEFSM, ‘H, respectively.We define the arrival model of a SyPEFSM as (P, ‘H). These data are directlygiven by the performance evaluator. We further assume (P, UH) is independentof the past state occupancies of the SyPEFSM. With this assumption, the statechanging process of a SyPEFSM is a CSMP. The performance of the SyPEFSMcan be derived by applying the theory of CSMPs given in Appendix A. Someresults are shown in this chapter.4.3 Performance Metrics of SyPEFSMsWhen all the data of M, H, P and “H of a SyPEFSM are known, the statechanging stochastic process of the SyPEFSM is completely specified: the singlestep transition probability matrix is P; the transition times, ?,br,3 (i, j E Q), arecomputed asw. + S (4.1)Chapter 4: performance evaluation of SyPEFSMs 68where w, and 8r23 are the waiting time and the service time of transition ij,respectively.1 The p.d.f.s of w and Sri., are given in ‘H and 5H, respectively.With this information about a SyPEFSM, we first derive the performancemetrics from Model S of the SyPEFSM and then investigate the metrics fromModel ‘I’.4.3.1 Performance metrics computed from Model SAs discussed in the previous chapter, Model S of a SyPEFSM models the stochastic process of state change of the SyPEFSM under an extremely heavy workloadso that there is no wait time for any firable message. Firable messages are always immediately ready when the SyPEFSM needs them. Models 4’ and S havethe same states, transitions and even single-step transition probabilities but eachtransition time of ‘I’ is longer than that of the corresponding transition of ModelS. Therefore, the statistical and performance measures below obtained fromModel S of a SyPEFSM can be viewed as the upper bounds of the SyPEFSM.Upper bound of mean overall service timeFrom Chapter 3, it is seen that the steady state probabilities of Model E, ModelS and ‘I’ are the same. Let ir = [rJ be the vector of the steady state probabilitiesin a SyPEFSM. ir can be computed from the single-step transition probabilitymatrix P of the SyPEFSM. We shall assume ir is known hereafter.Let be the mean service time of transition ij of a SyPEFSM, 9j be themean service time of all the transitions out of state i, and be the mean service‘The definitions of transition waiting time and transition service time are given in Chapter 3.Chapter 4: performance evaluation of SyPEFSMs 69time of all the transitions in the SyPEFSM.According to the definition of Model S of a PEFSM, 8r is the transition timeof Model 5, is the mean transition time of all the transitions out of state i inModel S, and Sf is the mean transition time of all the transitions in Model S.We have= 7r = PijiEQ 1EQjEQwhere Pu is the element at (i, j) of the transition probability matrix P.According to the message classification in the previous chapter, the relationship between the transitions and the incoming message classes of a PEFSM is aone-to-one mapping. Therefore, 9 is also the mean overall service time of theincoming messages to the SyPEFSM.Upper bound of mean throughput rateWe define a class ij outgoing message is generated (if any) each time transition ijis served. Let 8e, be the mean entrance rate of state i in Model S of a SyPEFSM,and be the mean throughput rate of the outgoing messages of class ij of theSyPEFSM.Since class ij outgoing messages are associated with transition ij, therefore,is also the mean entrance rate of transition ij in Model S. Applying Theorem A.4 and Equation (A.2), we can derive 5ZJ as8ij = 3i Pij = ir (4.2)in fact is an upper bound of the mean throughput rate of class ij outgoing messages in the SyPEFSM because is computed without taking anyChapter 4: performance evaluation of SyPEFSMs 70message arrival delays into account. The corresponding lower bound of the meanrecurrence time of class ij outgoing messages is equal to the reciprocal ofi.e., —--.lr’.p’,4.3.2 Performance metrics computed from Model ‘I’According to the definition of PEFSM in the previous chapter, w (the delay ofwaiting for a firable message) as well as 8f (the service time of the transition)is included as part of the transition time of transition ij in a SyPEFSM.Let “‘f and Wf be the mean values of ‘t’r and respectively.From Equation (4.1), we have= W + (i, j E Q).Mean holding time at a specific state of WLet be the mean holding time at state i of a SyPEFSM. It is the mean value ofthe time that the SyPEFSM stays in state i before finishing a transition startingfrom state i.Therefore, fj can be computed asPij’ij (4.3)jEQ= Pij ( + S) (4.4)jEQ= w + s (45)where W. is the mean holding time at state i of Model W of the SyPEFSM.Chapter 4: performance evaluation of SyPEFSMs 71Mean overall holding time at a state of WLet ‘ be the mean overall holding time at an arbitrary state of a SyPEFSM.Since the steady-state state probabilities of each state of the SyPEFSM areknown, can be computed:= (4.6)iEQ= ) (4.7)iEQ jEQ= Trj 1V + (4.8)iEQjEQ iEQjEQ= W, + (4.9)where w is the mean overall holding times at an arbitrary state of Model W ofthe SyPEFSM.Limiting lodging probability of a state in ‘PLet Qj be the probability that a SyPEFSM is seen at state i by an arbitraryobserver when the SyPEFSM is in equilibrium. is also called the limitinglodging probability of state i of the SyPEFSM.By Theorem A.2, ‘qj can be computed as=where and i are computed using Equations (4.5) and (4.9), respectively.State recurrence time in I1We define the recurrence time of state i in a stochastic process is the intervalbetween two consecutive entrances of state i. Let ,“,and h16 be the meanChapter 4: performance evaluation of SyPEFSMs 72recurrence time of state i of Models S, W and W in a SyPEFSM, respectively.By Theorem A.5, “8j can be computed as=— (4.10)7rc-’IQI— LO7rU TU411‘IQI .— l_iu=O 11u t.tv=o Puu (4 12)=IQI Puv (W + (4.13)= ELo7ru EtfJ0Puv W+ (4.14)= “6ZZ + ¶8. (4.15)We know that as long as 7r, Puv, and Sy (u, v E Q) are known, themean recurrence time of state i in IJ can be computed using Equation (4.14).And from Equation (4.15), it is seen that this mean recurrence time is the sumof the mean recurrence time of state i in the waiting for arrival model plus thatof in the service model. This result coincides with the intuition because l’ is amodel which counts both waiting and service.UtilizationIt is not difficult to see from Equation (4.15) that in a period of ‘9j, the protocolspecified by a SyPEFSM is busy (i.e. executing) only an amount of time equalto Ojj on average.Let p. be the ratio of the busy time and the recurrence time for state i. Thenpi=Chapter 4: performance evaluation of SyPEFSMs 73Obviously, p2 is the mean utilization of the SyPEFSM in the recurrence timeof state i. From the above result, p2 is seen to be independent of state i of theSyPEFSM. Therefore, it is equal to the overall utilization of the SyPEFSM.Let the overall utilization be denoted as p. Thenp — p —TSince p is the probability that the SyPEFSM is busy, so (1—p) is the probability that the SyPEFSM is idle waiting for incoming messages.ThroughputWe define the limiting entrance rate of transition ij in a PEFSM is the ratio ofthe number of transition ij being served over a very long time. Let ‘fJ be thelimiting entrance rate of transition ij of a SyPEFSM.Similar to in (4.2), “t7ZJ can be computed as— ..— e Ptj= Pij—7tiPjjWf+Class ij outgoing messages are associated with transition ij. Each time transition ij is completed, an outgoing message of class ij is output. For this reason,Chapter 4: performance evaluation of SyPEFSMs 74‘i is also the mean throughput rate of class ij outgoing messages under theworkload specified by (P, UH).The mean recurrence time of class ij outgoing messages is the reciprocal ofthe mean entrance rate of transition ij, b13, i.e., UVf..%Let be the mean overall throughput rate of the outgoing messages in aSyPEFSM. It is the reciprocal of the overall mean transition time of the SyPEFSM,which is equal to the mean overall holding time at a state of the SyPEFSM. Thus,1i can also be computed from the weighted sum of the mean throughput ratesof all the outgoing message classes. Both the results are the same:=iEQjEQ= PijiEQJEQ= PijiEQJEQ T14.4 Related workA closely related work to this chapter can be found in [KrWh93]. That work alsouses the theory of semi-Markov processes (CMPs) to derive performance for agiven FSM of a communication protocol. The FSM of a protocol in that paperis first translated into an intermediate representation called transition relationgraph. A node in the transition relation graph of an FSM represents a transitionChapter 4: performance evaluation of SyPEFSMs 75of the FSM, and a transition in the graph corresponds to a state in the FSM. Allthe transitions of an FSM in [KrWh93] are assumed to be atomic and take notime to execute, but the occupancy of a state in the FSM does span over time.After the transformation from an FSM to a transition relation graph, a transitionin the graph then takes the same amount of time as the corresponding state inthe FSM.Unlike [KrWh93], the transformation from an FSM to a transition relationgraph is not necessary for SyPEFSMs. This is because in a SyPEFSM, transitionsand state occupancies are already associated with time.[KrWh93] did not consider the waiting time for an incoming message (i.e.,wr) in any transition time. Rather, that research treats a transition time as consisting of only the transition service time, 5r,. As a result, only the performancemetrics in Section 4.3.1 of this chapter could be derived.[KrWh93] assumes that all the transition times are discrete and have geometricdistributions. In contrast, we do not impose any restriction on the distributionsof transition service times or transition waiting times.Other work whose performance evaluation methodologies are similar to [KrWh93]can be found in [GrDu87, Rico9l, Mars94]. Likewise, they also have the problemsdiscussed above.4.5 SummaryAn arrival model for SyPEFSMs is presented in this chapter. The arrival model iscomprised of P — the transition probabilities and UH— the p.d.f.s of the waitingtimes for firable messages of each state. The p.d.f.s of transition wait times 9?, (t)Chapter 4: performance evaluation of SyPEFSMs 76and transtion service times sh (t) (i, j E Q) can assume any distribution functionas long as the variables of transition wait times VT and transition service timessr2, are independent of each other.Given a SyPEFSM with this arrival model, the performance measures of theSyPEFSM such as state recurrence times and throughputs can be obtained andshown in this chapter.The bounds of these performance measures of a given SyPEFSM are alsoderived by analyzing its Model S. These bounds do not depend on the arrivalmodel of the SyPEFSM.The results in this chapter form the basis for the evaluation of the morecomplex PEFSMs in the next two chapters.Chapter 5Performance Evaluation ofAsynchronous PEFSMsAbstractAn asynchronous PEFSM (AsPEFSM) is a PEFSM whose incoming messages arriveasynchronously. This chapter examines two types of possible asynchronous arrivalmodels for AsPEFSMs. Performance metrics such as utilization and queue wait timesof AsPEFSMs are derived for both types of arrival models.5.1 IntroductionIn the previous chapter, we have discussed the performance evaluation of synchronous PEFSMs (SyPEFSMs). The essential difference between asynchronousPEFSMs (AsPEFSMs) and SyPEFSMs is that the arrivals of incoming messagesin AsPEFSMs are asynchronous. Messages may arrive at an AsPEFSM independent of the states of the AsPEFSM and therefore, may arrive before theAsPEFSM is ready to process them.77Chapter 5: performance evaluation of AsPEFSMs 78Examples of AsPEFSMs include the FSM of the service model of the asynchronous transfer mode (ATM) switch that processes Markov modulated trafficand an FSM of the token ring protocol (IEEE 802.5). The former model has beenintroduced in Chapter 3. The latter is an AsPEFSM because both the token andthe data may arrive at the server asynchronously at any time.An AsPEFSM has no control or influence on the arrivals of incoming messages.A message to an AsPEFSM may arrive before the AsPEFSM enters the statewhere the message is firable. When this happens, the messages which arrive tooearly will be stored in a buffer, commonly called a queue. Whenever an AsPEFSMenters a new state, the queue of the AsPEFSM is first checked to see if there arefirable messages of the state. If so, one of the firable messages of that state isprocessed immediately; otherwise, the AsPEFSM has to wait. In the first case,the wait time of the AsPEFSM upon entering the state is zero; in the second case,the wait time depends on the arrival distributions of the firable messages of thatstate. The computation method for this wait time is presented in this chapter.The wait times at states of an AsPEFSM are important indices in evaluatingthe performance of the AsPEFSM. These times influence the queue wait times offirable messages of the other states.Since messages may be queued up from time to time, the queue wait timesof incoming messages to an AsPEFSM are also important performance indices.Queue wait times can be more easily computed using a queueing model. Forthat reason, in addition to FSMs and stochastic processes, queueing models areemployed in evaluating the performance of an AsPEFSM.Queueing models are able to model service delays due to resource contentionChapter 5: performance evaluation of AsPEFSMs 79by messages. Conventional queueing models do not take into account the order ofmessage arrivals and the order of services controlled by an FSM. However, theseorders are important in an AsPEFSM and they influence the performance of theprotocol specified by the AsPEFSM.A natural way to integrate this ordering information is to construct a hybridmodel consisting of both the AsPEFSM and the queueing model.5.1.1 Queueing modelsWe assume the AsPEFSM of a protocol runs on a single processor computersystem. This implies the queueing models of an AsPEFSM are single-servermodels.1The queueing discipline of incoming messages in each queue of an AsPEFSMis first in first out (FIFO). When there is more than one class of firable messagesavailable at the time an AsPEFSM enters a state, the service discipline is assumedto be first come first served (FCFS). No other priority is assumed.5.1.2 Arrival modelsIn contrast to SyPEFSMs, since the arrivals of incoming messages to an AsPEFSM are asynchronous and uncontrolled by the AsPEFSM, it is difficult togive a general arrival model of incoming messages for all AsPEFSMs.In this chapter, two kinds of typical arrival models of AsPEFSMs are examined. The first assumes the arrivals of incoming messages to an AsPEFSM areuncorrelated. Incoming messages of different classes arrive independently to the‘To extend the results to multiprocessor systems, it is necessary only to replace the singleserver queueing model by a multi-server queueing model.Chapter 5: performance evaluation of AsPEFSMs 80AsPEFSM. The interarrival times of incoming messages within each class have anexponential distribution. An AsPEFSM with this kind of arrival model is calledan AsPEFSM-.The second arrival model assumes the arrivals of incoming messages to an AsPEFSM are correlated. The order (but not the timing) of incoming messages toan AsPEFSM corresponds to one of the transition sequences in the AsPEFSM.A sequence consists of the consecutive transitions of the AsPEFSM. The interarrival times of incoming messages, regardless of classes, are assumed to beindependent and identically distributed. Assume the distribution is exponential.An AsPEFSM with this kind of arrival model is called an AsPEFSM-/3.The above are the informal descriptions about the two arrival models. Formaldefinitions will be given in the later sections. The performance metrics of the twokinds of AsPEFSMs are derived in this chapter.The rest of this chapter is organized as follows. Sections 5.2 and 5.3 presentthe performance metrics and their derivations with respect to AsPEFSM-as andAsPEFSM-3s, respectively. Section 5.4 discusses the related work and Section5.5 summarizes this chapter.5.2 AsPEFSM-oAs mentioned, each class of incoming messages to an AsPEFSM-o arrives independently. An arrival model with this property is introduced below and theperformance metrics of an AsPEFSM with this arrival model are derived.Chapter 5: performance evaluation of AsPEFSMs 815.2.1 a-arrival modelLet 4k = {a2k(O),a2k(1), ak(2), ...} be the ordered set of the arrival epochs2 ofincoming messages of class ik of an AsPEFSM (i, k E Q):ak(O) <ak(1) <a2k(2) <Definition 5.1 (cr-arrival model) An arrival model of incoming messages toan AsPEFSM is called an ce-arrival model if the arrival model satisfies the following conditions:1. the elements in Ak are uncorrelated with those in A1 if i j or k I(i,j,k,l E2. (a2k(n + 1)— ak(n)) (i, k e Q and n = 0, 1, 2, ...) are exponentially distributed.Definition 5.2 (AsPEFSM-c) An AsPEFSM is called an AsPEFSM-o if thearrival pattern of its incoming messages follows an ce-arrival model.5.2.2 Queueing and service modelThe arrivals of incoming messages of each class of an AsPEFSM are independentof the current state as well as other incoming message classes of the AsPEFSMcii. Messages may come before they are ready to be processed in which case theyare stored in queues. We assume that there is a FIFO queue for each incomingmessage class of the AsPEFSM-a.2The time is assumed to be recorded according to a global clock.Chapter 5: performance evaluation of AsPEFSMs 82Furthmore, we assume there is only one service center for an AsPEFSM-aand the service discipline is FCFS.Suppose that there is more than one transition out of a state in an AsPEFSMo. Because each transition is associated with a message class, the number ofincoming message classes of a state is the same as the number of the transitionsstarting from the state. When there are firable messages belonging to more thanone class waiting in their respective queues at the time the AsPEFSM enters astate, the earliest arrived firable message of the state will be selected for serviceand correspondingly, the transition associated with this message will be executed.Let min(.) — be a selecting function;min(D)— be equal to the smallest element in set D;argk(f(xk)) — return the index of the variable Xk which satisfies thefunction f;X,— represent the n-th state (n = 0, 1, 2,...) entered by theAsPEFSM-a;t represent the epoch when the AsPEFSM-c enters then-th state.The queueing and service model of an AsPEFSM-a is defined with the following procedure:1. if X = i, then X1 = argk (min({min(A2k)}));2. if X1= j, then A2 = — {min(A23)};3. goto Step 1where i,j, k, I e Q. This is explained below.In Step 1, the firable message of state i which arrives the earliest amongthe unserved firable messages is selected and the transition associated with thisChapter 5: performance evaluation of AsPEFSMs 83message is made. All the messages of class ij whose arrival times are still inthe set Ak are not yet served. min(A2k) returns the arrival time of the earliestarrived but unserved message of class ik. min({min(A1k)}) (k e Q) returnsthe arrival time of the earliest but unserved message among the different classesof firable messages in state i. argk (min({min(Ak)})) returns the index of theclass to which this selected message belongs. In Step 2, the arrival time of theselected message is removed from the set in which the time is kept. This meansthe message is served and will not be considered again.This type of queueing and service model for AsPEFSM-o is illustrated graphically in Figure 5.1. A controller (labelled as B) controls the selection of the nextmessage to be served based on the AsPEFSM-c’s current state (labelled as A)and the arrival times of the messages in the queues.current stateclass ij incoming messagesclass kl incoming messagesFigure 5.1: The queueing system for an AsPEFSM-aWe can also formalize the queue wait time of a firable message and the queuelength of a specific class of incoming messages as follows:1. the transition wait time— f 0 min(A2)<tmin(A,) — t,2 min(A,) > t,.,Aservercontoller to selectthe next firable messageChapter 5: performance evaluation of AsPEFSMs 842. the queue wait time of the firable message which is selected at t— f t — min(A3) min(A23) t,q,tj —min(A13 > t,-,3. the queue length of class ki incoming message at t is the number of theelements in Aki at t which satisfy aki () t,-, where k, 1 E Q.5.2.3 Performance MetricsLet (M, 1’) and P = (P, UH, øf{) be the components of an AsPEFSM-o. Thedefinitions are given in Chapter 3.Let ) be the mean arrival rate of class ij incoming messages of an AsPEFSMa(i,jeQ).In this section, M, H and X, (i, i E Q) of an AsPEFSM-a are assumed to begiven by the performance evaluator. The other parameters will be derived fromthis given information.To obtain the performance metrics for an AsPEFSM-o, P and ¶H of theAsPEFSM-o need to be derived first.Computation of P and ‘HLet Pij be the single-step probability of transition ij. According to the definitionof P in Chapter 3, we havePiy = Pr{X÷1= jIX = i}.Since the transitions and the incoming message classes are one-to-one mapped, Pijis the probability that a firable message of class ij is selected when the AsPEFSMa enters state i.Chapter 5: performance evaluation of AsPEFSMs 85Based on the queueing and service model of the AsPEFSM-o, when theAsPEFSM-o enters state i, the firable message to be served is the one whichcomes first after the arrival of the last served firable message of state i. Let c (t)be the probability that the first firable message of state i arrives at time t afterthe last served firable message arrived and this message is of class ij.Applying the memoryless property of Poisson arrivals, we can derivecj,(t) = Pr{no firable message of state i arrives within time tand a class ij message arrives at time t}IQI=. [Ik=O,kjTherefore,(00 A2p,= J c(t)dt =0 l_kEQ ‘ikFrom the above equation, it is seen that the transition probability matrixP = [Pu] can be computed directly from the given mean arrival rates of incomingmessages.Furthermore, by Theorem A.1, the steady-state state probabilities it can becomputed by solving the following equationirP = it.It means that given the arrival rates and the AsPEFSM-a, we can compute Pand it. Therefore, we assume P and it are known hereafter.Next, we compute H.By the definition of transition time given in Chapter 3,— w_L $T— To—i-- TChapter 5: performance evaluation of AsPEFSMs 86where is the transition time of transition ij, w is the time for the AsPEFSMc to wait for a firable message of class ij, and 3T is the service time of transition ijwhich is given by the performance evaluator. Both w and ‘1’r2 can be computedin the following way.Remember that we have assumed the interarrival times of incoming messagesin each class to be uncorrelated and exponentially distributed. It is also well-known that if the interarrival times of the jobs are exponentially distributed,then the number of the arrivals within a certain time is Poisson distributed, andvice versa. Therefore, the arrival patterns of incoming messages for all the classesin an AsPEFSM-c are independent Poissons.As a result, the arrivals of firable messages of state i regardless of their classesare also Poisson. Denote the mean arrival rate of the messages in state i by A.We have= E .jEQLet NoF denote the event that the AsPEFSM finds no firable message ofstate i in the queue when it enters state i and NoF denote the reverse of NoF(i.e., at least one firable message is available). Let Po,i be the probability of NoF(i.e., PO,i = Pr{NoF} and 0 PO,i < 1) when the AsPEFSM is in equilibrium.By the queueing and service model of an AsPEFSM-a, it is true that the waittime of the AsPEFSM-o is equal to zero when the AsPEFSM-o enters a stateand finds at least one firable message of the state. Formally,Pr{ = 0X = i, X÷1 = j, NoF} = 1orPr{ rij > = i, X÷1= j, NoF} = 0.Chapter 5: performance evaluation of AsPEFSMs 87Therefore,W. ffi 1II’ijIU) —— Po,i,andWh..(t) == Pr{ vr = = i, X,1 = j, NoF} Pr{NoF} +Pr{ w = tX = i, X,1 = j, NoF} Pr{NoF}= Pr{ ‘°r = tIX = i, X,÷1 = j, NoF} Po,—Pr{(X,÷i = j, W = t)IX = i, NoF}— Po, Pr{Xi = iIX = i, NoF}—x,t11kO,kj e— A1,EkEQ A1k= PO,ikEQ= PO,i Aieitwhere t > 0 and wT is the wait time for a firable message.Since Wh..(t) is the p.d.f. ofw =f thlh(t)dt=po, x (5.2)Apply this result in (5.1) and get1%= PO,i + (5.3)where 0 PO,i 1 and i,j E Q.We still need to compute PO,i — the probability of NoF.Focusing on state i of an AsPEFSM-o, we first give the following definitions.Chapter 5: performance evaluation of AsPEFSMs 88Definition 5.3 (first passage) A first passage from state i to j in an FSM isa sequence of consecutive transitions of the FSM which starts from state i, endsin state j and never passes state j in between.Definition 5.4 (virtual job) A virtual job with respect to state i in an AsPEFSMc consists of the transitions on a first passage from state i to itself in the FSMof the AsPEFSM-c.Definition 5.5 (virtual job class) Class ij virtual jobs in an AsPEFSM-ci arethe set of the first passages from state i to i in the FSM of the AsPEFSM-a. Thefirst transition of each first passage in this set is transition ij (i, E Q).Suppose there are n transitions out of state i. Applying the above threedefinitions, we transform all the first passages from state i to i in an AsPEFSMc into n virtual job classes. This transformation is illustrated in Figure 5.2.The arrival rate of class ij virtual jobs of an AsPEFSM-o is equal to thearrival rate of class ij incoming messages ),. Let (, denote the service time ofa virtual job of class ij. If transition ij is a self-loop transition from state i toi, then the service time of a class ij virtual job is equal to the service time ofthis transition; otherwise, the service time of the class ij virtual job is the serviceFigure 5.2: Reduction of a general FSM into a one-state EFSMChapter 5: performance evaluation of AsPEFSMs 89time of transition ij plus the time spent on the first passage from j to i in theAsPEFSM-a, i.e.,_f S• ifi=j 54— 1 + ‘‘9 if i jwhere b03 denotes the first passage time from state j to i in the AsPEFSM-o.‘1’6J consists of all the transition times on the first passage and does not includeany queue wait time.We can write the mean value equation as— I 3ii ifi=j—+ ‘ ifwhere ij — the mean of ij— the mean ofThe mean service time of class ij virtual jobs,,,can be computed as long as, and are known. , by defintion, is part of the primitive data provided bythe evaluator. From Theorem A.3, “6,, can be computed by solving the followingrecurrence equation1,1)8,.=+ Pjk—Pji (j i)kEQwhere i,j eQ.Applying the results we have obtained to the above equation, we further derive= ‘j + P,k Oki — Pji (5.5)kEQ= (5.6)kEQ kEQ= Pjk(PO,j + 8Tk) + Pjk 8ki— Pji ‘ (5.7)kEQ 3 kEQ= + s,+ Epjk”6kj—pj”i (5.8)3 kEQChapter 5: performance evaluation of AsPEFSMs 90wherei,j eQandji.This is still a recurrence equation, in which A3, Pjk, and 9, (j, k E Q) arealready known from the given primitive data of the AsPEFSM-a. is unknownbut it is the mean first passage time from state i to itself in the AsPEFSM-c.We also call the mean recurrence time of state i of an AsPEFSM-o. 8j can becomputed in the following way.Let j be the mean service time of the overall virtual jobs from state i to i inan AsPEFSM—c. Then,EPiiii.jEQBy the definitions of 8j and ç, we have6-u = p(W+) (5.9)iEQ= (5.10),EQ jEQPo,i—= (5.11)PO+ (5.12)With the above construction of the virtual jobs, the queueing system servingincoming messages of an AsPEFSM-c can be viewed as a queueing system servingthe virtual jobs. PO,i in turn is the idle probability that the transformed queueingsystem is waiting for virtual jobs.Let p, be the utilization of this queueing system. When (A2 () < 1,p=Ac. (5.13)Chapter 5: performance evaluation of AsPEFSMs 91According to [GrHa85](p.86), for a single server queueing system when thesystem is in equilibrium, it is true thatPO,i = 1 — p, (p < 1). (5.14)Substituting Equations (5.14) and (5.13) in Equation (5.12), we get= 1This result is under the condition that the system running the virtual jobs is inequilibrium, i.e., (A, ‘: < 1).Now we can rewrite Equation (5.8) with this result as:= 22. + + EP,k 8ki — Piir. (5.15)Moreover, we rewrite Equation (5.14) as:PO,i = 1 — p, (5.16)= 1—A (5.17)1 — (5.18)i€Q= 1_(EAjj(8f13+—A’) (5.19)jEQ= 1— +—(5.20)= 1— (E A( + ‘) — p) (5.21)jEQIn Equation (5.15), Po,j and (i,j E Q) are unknown. In Equation (5.21),PO,i and % are also to be determined. Therefore, solving the equations statedChapter 5: performance evaluation of AsPEFSMs 92in (5.15) and (5.21) for all i,j E Q together, we can find PO,i and (i,j e Q)if they exist.With PO,i (i E Q) known, w in Equation (5.2) can be computed, and so canIn many cases, Po,i = 0. The following theorem helps to identify some of thesecases.Theorem 5.1 In an AsPEFSM-c, if one of the following conditions is satisfied,then PO,i = 0 (i E Q):1. ) S9 > 1 where s is the mean first passage time from state i to i in ModelS of the AsPEFSM-ct;2. A > jEQProof:By the definition of virtual job, we note that the service time of each virtualjob of state i contains the service times of the transitions on a first passage fromstate i to state i in the AsPEFSM-c. Therefore, > S• If )., > 1, then)> 1 and this means the queuing system serving the virtual jobs is saturated.In other words, there are always virtual jobs (i.e., firable messages of state i)waiting in the queue. Hence, PO,i = 0.To prove the second situation, we refer to Figure 5.3. From the figure, it canbe seen that A, is the total possible arrival rate of entry messages whichput the AsPEFSM in state i, while= ZkEQ A2k is the total possible arrival rateof leaving messages which make the AsPEFSM leave state i.Let X(t) be the total number of entry messages that arrive within time t,Chapter 5: performance evaluation of AsPEFSMs 93entry cages leaving messages(also called firable messages)Figure 5.3: Messages come to and leave state i in an AsPEFSM-aX(t) be the total number of leaving messages that have arrived within the sameperiod, and X(t) be the total unserved messages leaving state i after the period.We note that each entry message of state i consumes only one leaving messageof state i. Therefore, we can writeX(t) — f (X(t) — X(t)) ifX1(t) > X.,(t) (5 22)— 1 ° ifX(t) <x(t)Their mean value relationship can be expressed asEX — (i—EjEQAji)t ifA, >EEQ)ji 52I — jEQ iiObviously, if > EJEQ and t —* 00, then E[X(t)] —* 00. This meansthe unserved leaving messages of state i will accumulate in the queue, i.e., firablemessages of state i are always available in the queue. Therefore, PO,i = 0.CUtilizationThe utilization Pt defined earlier is in fact only a virtual utilization of an AsPEFSMo. This utilization is not the real (actual) utilization of the queueing system serving the AsPEFSM-a because it does not take into consideration the idle periodswithin the first passages from state i to state i.Chapter 5: performance evaluation of AsPEFSMs 94Let p be the (real) utilization of the queueing system of an AsPEFSM-a(p<1).When the AsPEFSM-a is in equilibrium, we havep=.Applying Theorems A.5 and A.4, we get the recurrence time of state i as= =So that= (5.24)Substituting the above equation into Equation (5.2.3), we rewrite9:p=—The AsPEFSM is in equilibrium only if p < 1. Therefore,(i E Q)is the necessary condition for equilibrium.The following theorem follows directly from Equation (5.24):Theorem 5.2 When an AsPEFSM-c is in equilibrium and p < 1, the followingequation holds7r 1j for allt,jeQ.“i “jChapter 5: performance evaluation of AsPEFSMs 95ThroughputsWith •8 — the mean recurrence time of state i of an AsPEFSM-c, the meanthroughput rate of the outgoing messages of any specific class in the AsPEFSMc can be computed in a similar way given in (4.2).When an AsPEFSM-c is in equilibrium, the transition service rate is equalto its entrance rate.Let fjj be the throughput rate of the outgoing messages associated with transition ij out of state i.Then,= (5.25)= (5.26)= (5.27)= A,,. (5.28)The above result confirms the intuition: throughput rate = input rate for asystem in equilibrium.Queue wait timesFirst, we derive some queueing properties for M/G/13 queueing systems andAsPEFSM-s from a previously proven lemma:Lemma 5.3 Suppose Poisson arrivals observe a stochastic process as well asinteract with it. If the process being observed cannot anticipate the future state3M/G/1 is a single-server queueing system which has Poisson job arrivals and general distributed service times.Chapter 5: performance evaluation of AsPEFSMs 96change of the Poisson process, then the fraction of arrivals that see the process insome state is equal to the fraction of time the process is in that state.Proof:See [Wolf82, MeWh9O]. DThis lemma is called Poisson Arrivals Seeing Time Average (PASTA). Thefirst proof was given in [Wo1f82]. A new proof with a less restricted condition isgiven in [MeWh9O].According to this lemma, in an M/G/1 queueing system, the fraction of arrivals which find n customers in the system is equal to the fraction of time thesystem has n customers. For a M/G/1 queueing system with multiple job classes,we can derive the following theorem:Theorem 5.4 In an M/G/1 with multiple job classes, if the jobs in each classarrive in an independent Poisson pattern with the same mean, the mean queuewait times of each class are equal.Proof:Since the arrivals of the jobs of a specific class are Poisson, by Lemma 5.3,the mean number of jobs in the system at the arrival points of this class is equalto the average number of jobs in the system over time. By Little’s Law L =[Litt6l], the mean queue wait time of each class is the same and is equal to theoverall mean queue wait time.Based on the above theorem, the formula to compute the mean overall queuewait time of all the messages for an M/G/1 with multiple job classes (see [Allen9O] (p.688))can also be applied to compute the mean queue wait time of the messages of aspecific class.Chapter 5: performance evaluation of AsPEFSMs 97There is also an analogous queueing property with AsPEFSM-as. In thefollowing, we prove the property also using PASTA.Let the queueing system state of an AsPEFSM-a consist of the informationon incoming messages in each queue, the current state which the AsPEFSM-o isin and the current transition which is in service.Since we have assumed that in an AsPEFSM-a, the arrivals of incoming messages of each class are in an independent Poisson pattern, the following theoremis true for AsPEFSM-as.Theorem 5.5 The probability of each queueing system state seen by the incomingmessages of a specific class at their arrivals is equal to the fraction of time thesystem is in that state.Proof:Direct from Lemma 5.3.With Theorem 5.5, we can conclude:Theorem 5.6 The mean queue wait times of different classes of firable messagesin the same state of an AsPEFSM-c are equal.Proof:Since each class of messages arrive in Poisson, each message has the sameprobability of encountering a specific queueing system state as the other messages. The firable messages of the same state in the AsPEFSM-c have the sameprobability of waiting for a certain amount of time before the AsPEFSM-o entersthis state where the firable messages can be served. Therefore, the mean queuewait times of the firable messages of different classes of the same state are thesame. E:IChapter 5: performance evaluation of AsPEFSMs 98Let Wq,j be the mean queue wait time of all the classes of the firable messagesof state i in an AsPEFSM-o, and Wq,ij be the mean queue wait time of class iiincoming messages. By Theorem 5.6, we haveWq,i Wq,ij (i,j é Q).Therefore, only Wq,j of each state in an AsPEFSM-a need to be computed.Recall the construction of the virtual jobs described earlier in this section.Virtual jobs from the same state, say state i, in an AsPEFSM-a are categorizedinto different classes with respect to the first transitions on each first passagefrom state i to state i. This transforms the original queueing system serving theAsPEFSM-c into an M/G/1 with multiple job classes. Each class of jobs consistsof the virtual jobs which start with a transition from state i.By the definition of first passage, of an AsPEFSM-o includes the possible idle periods when the AsPEFSM-a waits for firable messages during a firstpassage. For a specific first passage, these times are independent from the pastoccupancies of the states of the AsPEFSM-a. The reason for this is that Poissonarrivals have the memoryless property.Moreover, “8, is not related to the next arrival of any class of firable messagesof state i in an AsPEFSM-o. This is because by definition, a first passage fromstate j to i does not contain any transition out of state i.Therefore, the service time of a class ij virtual job, (23, does not depend onthe arrival rate of any class of firable messages of state i in the AsPEFSM-o.As a result, the queueing system which serves these virtual jobs is a conventionalM/G/1 with multiple job classes. The queueing theory of M/G/1 can be employedfor this queueing system.Chapter 5: performance evaluation of AsPEFSMs 99Let < be the second moment of the service times of the virtual jobs fromstate i to itself in an AsPEFSM-o. Then, by definition,jEQcan be computed from the definition of (j given in Equation (5.4). Thedetail is given in Appendix B.By applying the solution techniques for M/G/1 (see [Allen9Oj(p.688)), themean queue wait time of the messages out of state i, Wq,j, isV’ ..t2W —________— /—‘jEQ “:i’,jjq,i— 2(1—p) — 2(1—p)The mean number of the firable messages of class ij in the queue, Lq,j, can becomputed using Little’s Law [Litt6l]:Lq,i = AiTVq,i.5.3 AsPEFSM-3In the AsPEFSM-c model, incoming messages of different classes are uncorrelated.However, some communication and distributed systems, the arrivals of incomingmessages are correlated. In this section, we study a simple type of correlatedarrival model, called /-arrival model. An AsPEFSM with this type of input iscalled an AsPEFSM-/3.5.3.1 6-arrival modelWe assume that the correlation of the arriving incoming messages is specified inthe FSM of an AsPEFSM as follows:Chapter 5: performance evaluation of AsPEFSMs 100Let A = {a(0), a(1), a(2),...} be the ordered set of the arrival epochs of allthe incoming messages to an AsPEFSM without distinguishing their class types:a(0)<a(1)<a(2)<...Let C(t) be the function which returns the class of the message which arrivesat time t. C(t) = if no message arrives at time t.Definition 5.6 (fl-arrival model) An arrival model of incoming messages toan AsPEFSM is called a /3-arrival model if the arrival model satisfies the followingconditions:1. a(n + 1) — a(n)) (n = 0, 1, 2,...) are exponentially distributed with mean2. if C(a(n)) is class ij (i, j Q), then C(a(n + 1)) must be one of class jk(k E Q). The probability that C(a(n + 1)) is class jk is Pjk, andP,k = 1.kEQThe first condition in the above definition says the overall arrivals of incomingmessages are a Poisson process with parameter A. The second condition impliesthe sequence of the incoming messages corresponds to a sequence of consecutivetransitions associated with the messages in the FSM of the AsPEFSM. The singlestep transition probabilities of an AsPEFSM-fl, Pi, (i, e Q), are actually givenwith the /3-arrival model.Definition 5.7 (AsPEFSM-/3) An AsPEFSM is called an AsPEFSM-/3 if itsincoming messages follow a /3-arrival model.Chapter 5: performance evaluation of AsPEFSMs 101Model AFrom the second condition of the definition of a 6-arrival model, we know that a/3-arrival model itself forms a stochastic process. This stochastic process is calledModel A.The kernel of Model A of an AsPEFSM is the same as that of the AsPEFSMwhich is usually an FSM denoted as M. Graphically, Model A has the same statesand transitions as the FSM of the AsPEFSM, except that the contents and actionsof the transitions are different. The single step transition probabilities of Model Aare given. The transition times in Model A are the interarrival times of incomingmessages which are identically distributed with mean 4. Each transition in ModelA sends out a message to the AsPEFSM.Let ir = [ir] (i E Q) be the steady-state state probability vector of Model A.By Theorem A.1, r can be computed from the given P. So we assume ir is knownhereafter.Let,be the mean transition time of transition ij in Model A (i, j E Q).Then,A-Let A and be the mean entrance rate of state i in Model A and therecurrence time of state i in Model A, respectively.By Theorem A.5, we have14—Âë.—whereA- A- 1T = ‘l1uPuv T, = —.u,vEQChapter 5: performance evaluation of AsPEFSMs 102Therefore,andAe_ ?ir5.3.2 Queueing and service modelWe assume there is only one queue to store all the messages that arrive early.The queueing discipline is FIFO.The queueing system for an AsPEFSM-/3 is shown in Figure 5.4.incoming messagesserverFigure 5.4: The queueing system for an AsPEFSM-3The order of processing the incoming messages is the same as the order of theirarrivals. The trajectories of the states occupied by the AsPEFSM-/3, Models S,W and E over time are identical to those of Model A. Therefore, the transitionprobabilities of the AsPEFSM-6, its Models S, E and A are all the same.5.3.3 Performance metricsIn this section, we investigate the performance metrics for AsPEFSM-j3s.Up to now, M, P and 3F1 of an AsPEFSM-16are known. The mean arrival rateof incoming messages A is also given. So similar to the performance evaluationChapter 5: performance evaluation of AsPEFSMs 103of AsPEFSM-a, we start with deriving “H of the A5PEFSM-/3 from the knowninformation.Computation of UHBy the definition of transition time given in Chapter 3, we have“Ti3 W7 + S, (5.30)Let NoF denote the event that the AsPEFSM-3 finds no firable message ofstate i in the queue when it enters state i and NoF (i.e., at least one firablemessage is available) denote the reverse of NoF. Let PO,i be the probability ofNoF.From the definition of the queueing and service model of an AsPEFSM-, weknow that the wait time of an AsPEFSM-fl at state i is zero when the AsPEFSMenters a state and finds a firable message of the state. Formally,Pr{Lrj= i, X÷1 =j, NoF} = 1orPr{”r > =i, X,÷1 =j, NoF} =0.Since wh,(t) is the p.d.f.s of w, we havewh,(o) = 1— PO,i•When t > 0, we haveWh..(t) = Pr{wT=tpX=j,X1j}Chapter 5: performance evaluation of AsPEFSMs 104= Pr{ Ur = i, X1= j, NoF} Pr{NoF} +Pr{ “r3 = tIX = i, X4 = j, NoF} Pr{NoF}— Pr{(’’r = t, X, =i, X,1 =j)NoF}— Pr{(X = i, Xn+i = i)IN0F} P0,PO,i Pr{ ‘°ri tINoF}PO,iwhere WT is the wait time of the AsPEFSM-6 for a firable message of state i.Therefore, we can derivep00— I Wi. I#\ # u — pO,zand— W j_ — !:?92!. _LT2:,— T2:,—-T T22.In the above equation, PO,i is unknown. To compute PO,i (i e Q), we adopt thetransformation introduced in Section 5.2.3 to construct virtual jobs with respectto state i of the AsPEFSM-fl. The definitions of first passage and virtual jobare the same as before. The difference is that here the mean arrival rate of classij virtual jobs in an AsPEFSM-/ is not given. This rate can be computed asfollows:Let \,:, be the mean arrival rate of class ij virtual jobs and X, be the meanarrival rate of all the virtual jobs with respect to state i in the AsPEFSM-/3.From Model A of the AsPEFSM-/3 and the definition of virtual jobs, it isknown that the arrival rate of class ij virtual jobs is equal to the arrival rateof the class ij incoming messages which is the entrance rate of transition ij inModel A. Formally,A = Aëp = AirpChapter 5: performance evaluation of AsPEFSMs 105and thus,A1 = A =Moreover, when an AsPEFSM-/3 is in equilibrium,— Ae,— e2.Therefore,22— —The rest of the work is to solve the equations stated in (5.8) and (5.19) for alli, j E Q, from which we obtain PO,i and ‘ji (i, j E Q).With PO,i (i E Q) computed, wj (i, j E Q) can be derived and so canThroughputsLet i be the throughput rate of class ij outgoing messages (i, e Q).When an AsPEFSM is in equilibrium, the throughput rate is equal to thearrival rate. Therefore, the throughput rate of class ij outgoing messages issimply= A13 = A Pu.UtilizationLet p be the utilization of the AsPEFSM-3.By definition, we havep = A•Chapter 5: performance evaluation of AsPEFSMs 106where ) is the given mean arrival rate of incoming message and is the meanservice time of incoming messages. 7 can be computed as follows:s__Tr. Si__7rj.pj. i,•iEQ iEQJEQIn this equation, Pu, ir and , (i, j E Q) are already known.Since p < 1 is the requirement for the AsPEFSM-/3 to be in equilibrium, theinequality, X < 1, must hold for the formula to work.Queue wait timesBy definition, the messages come to an AsPEFSM-j3 in a Poisson pattern, andthere is only one queue and one service center. As a result, the queueing systemof an AsPEFSM-3 serving the incoming messages is an M/G/1 queueing system.In this queueing system, the mean arrival rate is )., and the mean service timeof messages is . The second moment of the service times, 3r2, can be computedas follows:= f( pWh(t))t2d (5.31)0 i,jEQ= > irupu(f Wh(t)t2dt (5.32)i,jEQ 0-s2— 1z Pz, j.i,jEQThe mean overall queue wait time of the incoming messages can be obtainedusing the solution technique for M/G/1 (see, for example [Allen9O](p.688)):)w=q 2(1—p)Chapter 5: performance evaluation of AsPEFSMs 107By Little’s Law, the mean overall queue length is—_____L=AW=q 2(l—p)Probability of the number of messages in the queueing systemAn AsPEFSM accepts and processes incoming messages according to its Model Asequentially. Model A is independent of the transition services of an AsPEFSM3, but Model A and its AsPEFSM-fl share the same set of states. The statetrajectory of the AsPEFSM-16always follows that of its Model A.Due to the service delay, the present state of an AsPEFSM-,5 is never ahead ofthat of its Model A. Instead, the current state of an AsPEFSM-/3 is occasionallyone or more states behind that of Model A. For instance, when the AsPEFSM-/3is in state j, Model A may already be in state i and several incoming messagesare buffered in the queue of the AsPEFSM-,6. The AsPEFSM-/3 enters state iwhen these messages in the queue have been processed.A pair can be used to characterize this state relation of Model A and itsAsPEFSM-,6 at any instant. We denote a pair for this purpose as (i,j) (i,j E Q).The first element i of the pair represents the current state of Model A and thesecond element j represents the current state of the AsPEFSM-,6. If only thepresent state of Model A is of interest, (i,.) is used for indicating Model A is instate i at present and we do not care which state the AsPEFSM-/3 is in. Likewise,(., j) states that the AsPEFSM- is currently in state j and we do not care whichstate Model A is in.Since we want to indicate the number of messages in the system together withthis state relation, we add another element n to denote this number. This turnsChapter 5: performance evaluation of AsPEFSMs 108the pair (i, i) into a triple (n, i, j). (n, i, j) indicates that the system state ofModel A is at state i, the AsPEFSM-6 is in state j and there are n messages inthe system.Suppose that at time t, the system is in (i,j, n). This state is reached fromone of two possible states in one step:1. At time t1 (t < t), the system state is (n—i, i, j)4 if n > 0. After a periodof t2, an incoming message arrives but no message finishes its service yet.Then in the next (t — t1 — t2) time period, no message arrives or finishes itsservice.2. At time t1 (ti < t), the system state is (n + 1, i,jj. After a period of t2,a message finishes its service and leaves the queueing system. Then in thenext (t— t1 — t2) time period, no message arrives or finishes its service.Let ‘gjj (r) be the probability that no message arrives or finishes its servicewithin time r when the system is in state (., i, j). We havebgjj(r)— (1 — h(r)) . (1 —where _<Ah(r) and “I’h(r) are the cumulative distribution functions of the stateholding times of Model A and the AsPEFSM-16,respectively.Let be the probability that Model A is in state i, and the AsPEFSM-f3is in state j at time t with n messages in the queueing system.Formally, can be expressed as= 1 f2_1,,(t). pjj• Ah_(t2). — t1 —t2)dtd1i—EQ 2 04i refers to a state from which there is a one-step transition to state i in the AsPEFSM-f3.Chapter 5: performance evaluation of AsPEFSMs 109+ ff2 n+i,i,-(ti) Pi-,i’9h-,(t2) — t1 — t)dtdt1.i—EQ 2 0Applying the exponential transformation [Howa7l, Allen9Oj to the above equation, we get=_1,_,3(s) g(s)iEQ+ 8h_,(s). ‘g(s)i-EQ= [ Ah..(s)i-EQ+ ÷i,:j—(s) .pj—,j she(s)]i-EQRewriting the above equation in Matrix form yields{[pDAHe(S)]Te(S)+e(S)[pQsf{e(S)]}DGe(S)where (s) = [,3,,(s)j, AHe(s) = [3h:(s)1, sHe(s) [she.(s)], and Ge(s) =D is the matrix element multiplication5.Dividing the elements of the matrices on both sides of Equation (5.3.3) withGe(s), we get= [PD A}{e()]Te (s) +÷1(s)[PD sHe(s)]where D is the matrix element division operator6.We can rewrite the above equation as= [(s)OGe(s) — PDAHC(s)}Tx x [pQsfJe()]_l5ADB = [ab1j. This matrix operation is different from the matrix multiplication.6AB = [a:j/bzj].Chapter 5: performance evaluation of AsPEFSMs 110where [AlT is the transpose of the matrix A and [Aj1 is the inverse matrix ofA.This is a recurrence equation of the exponential transform of the probabilities of the number of messages in the queueing system at time t. The limitingnumber of messages in the queueing system after a very long period of time,limt can be obtained from this equation by final value property of theexponential transformation [Howa7lJ (p.697),lim = lim scbt—The initial values are knownko,o,o(O) = 1;and= 0 (i i).Therefore,sk,,(s) = 0 (i # j)andlins,,(s) = 0 (i i).Moreover, by definition, we haveurn= PO,i•t—ooTherefore,iilj = PO,i•Chapter 5: performance evaluation of AsPEFSMs 111The computations of PO,i (i E Q) in the above equation have been presentedearlier in this section. As a result, the initial matrix (s) is known. Thereafter,the other parameters can can be computed recursively.Theoretically, the probability mass function of the number of messages in thequeueing system can also be computed by finding the inverse function of theexponential transformation.5.4 Bounds of Performance MeasuresAs long as the transition probabilities of an AsPEFSM are known, the boundsof the performance measures can be computed by analyzing its Model S. Thecomputations of these bounds are the same as those in Section 4.3.1 and will notbe repeated here.5.5 Related workQueueing systems with semi-Markov arrival processes or service processes havebeen attracting more and more attention recently.Most of the published work focuses on studying the impact of the correlatedor batch arrival jobs on a queue system. For instance, many papers examine theinfluence of Markov modulated arrivals on the performance of ATM networks.The results from these papers are limited and are applicable only to some simplequeueing models in which the assumptions to simplify the service times are satisfied. For example, [Herr93] studies SMP/D/1s7for ATM networks. SMP/D/1 is a7SMP is the abbreviation of semi-Markov process.Chapter 5: performance evaluation of AsPEFSMs 112more general model than the models given in [DiDe9O, Ding9l]. The arrivals of anSMP/D/1 are correlated input streams and are assumed to be asynchronous, being controlled by an SMP. This is similar to the queueing systems of AsPEFSM-/3sin this chapter. However, the service times of an SMP/D/1 are assumed constantand there is no distinction of job classes. In contrast, we have fewer restrictionson the service times which are continuous random variables.[DsTa93] studies a more complicated queueing system than SMP/D/1. In thequeueing system of that work, the input flows are modulated by SMPs and theservice times depend on the states of the systems and the batch sizes of inputdata taken from the buffer. The queueing process of such a queueing system is themain object to be studied. The theories of point processes and semi-regenerativeprocesses were employed in this work to derive the steady-state distribution ofthe queueing process, the mean values of idle and busy periods, etc.. A state ofthe queueing process represents the size of the unserviced data (i.e., the numberof the customers) in the system.Unlike the previous work stated above, queueing processes are not the mainprocesses to be studied in our performance evaluation of AsPEFSMs. We focusmainly on the state changing process of the FSM of an AsPEFSM. The incomingmessages in the queues are distinguished on their classes. In this way, we notoniy obtain the queueing stochastics but also analyze the relationships betweenthe queueing processes and the states of the FSM of an AsPEFSM.Chapter 5: performance evaluation of AsPEFSMs 1135.6 SummaryIn this chapter, we have analyzed AsPEFSMs with two types of asynchronousarrival models: AsPEFSM-as and AsPEFSM-6s. In an AsPEFSM-a, incomingmessages arrive independently and are uncorrelated; in an AsPEFSM-f3, incomingmessages come correlated in an order which can be accepted by the FSM ofthe AsPEFSM-fi. In both cases, the transition service times (i, j E Q) areassumed to be independent of each other and independent of message arrivalpatterns. The service times may assume any distribution.The methods to compute transition probabilities and transition wait timesfor AsPEFSM-as and AsPEFSM-fls are given. Moreover, the derivations of theperformance metrics such as utilization, throughputs and queue wait times arepresented.From a queueing theory point of view, the queueing systems of AsPEFSMsare interesting queueing systems. The services of these queueing systems arestate-dependent (or more precisely, transition dependent). The arrivals of jobs tothese queueing systems are probably correlated. This kind of queueing system ismore realistic in computer networks.In addition, the queueing properties of an M/G/1 with multiple job classesand an AsPEFSM-a have been discovered and proved.Chapter 6Performance Evaluation ofHybrid PEFSMsAbstractThis chapter studies the third class of PEFSMs called hybrid PEFSMs (HyPEFSMs). HyPEFSMs are the most complex of all PEFSMs. We examine a specific typeof HyPEFSM and derive the performance metrics such as utilization, throughput andqueue wait time for the HyPEFSMs of this type.6.1 IntroductionIn the previous two chapters, we have studied the PEFSMs whose arrival models of incoming messages are either completely synchronous or completely asynchronous, respectively. In this chapter, we will study another type of PEFSMin which the incoming messages may come synchronously or asynchronously. APEFSM of this type is called a hybrid PEFSM (HyPEFSM).114Chapter 6: hybrid PEFSMs 1156.1.1 Hybrid transitionRecall the alternating bit protocol in Chapter 3. The FSM of the transmitterof this protocol was shown in Figure 3.1. In Chapter 3, that FSM is used asan example for a HyPEFSM. We use the same FSM for a transmitter here butwith different assumptions about the running environment of the transmitter.For convenience of discussion, we repeat the figure in Figure 6.1.TOl: DATAIDATATi 1: timeout/DATATiO: ACK!STATES: TRANSmONS:state 0: idle TOl : sending a DATA packetstate I: waiting for ACK Ti0 : receiving an ACK(acknowledgement) TI 1: timeout retransmissionFigure 6.1: An FSM of the alternating bit protocolWe now assume that the underlying communication network may delay anACK message. The delayed ACK may still arrive at the transmitter after atimeout but it is not discarded by the transmitter if the transmitter is in state1. A delayed ACK usually arrives asynchronously while a non-delayed ACKarrives synchronously. Therefore, in this case, transition T1O cannot simply beclassified as a synchronous transition or an asynchronous transition’. This isbecause the incoming messages of transition T1O consist of both synchronousand asynchronous ACK messages.‘We have defined synchronous transition and asynchronous transition in Chapter 3.Chapter 6: hybrid PEFSMs 116A transition, which is associated with both synchronous and asynchronousincoming messages, is called a hybrid transition.We have seen from the alternating bit protocol example that in a PEFSM,whether a transition is hybrid or not depends on the assumptions about theprotocol that the FSM specifies. If we assume that the timeout values are setlong enough so that no delayed ACK message will come after a timeout, thentransition Tb is solely a synchronous transition.In this chapter, we study a HyPEFSM which has only synchronous and asynchronous transitions.6.1.2 Hybrid stateIn a SyPEFSM or an AsPEFSM, by definition, all the transitions from a stateare completely synchronous or asynchronous, respectively. If all the transitionsfrom a state of a PEFSM are synchronous, we call this state a synchronous state.Likewise, if all the transitions from a state are asynchronous, we call this statean asynchronous state. Therefore, all states of a SyPEFSM are synchronous, andall states of an AsPEFSM are asynchronous.However, both types of states may co-exist in a HyPEFSM. This is becauseboth synchronous and asynchronous transitions are allowed in a HyPEFSM. Inaddition, a third type of state is possible in a HyPEFSM. From a state of thistype, some of the transitions are synchronous and some are asynchronous. Wecall this state a hybrid state. Figure 6.2 shows the three possible situations of astate from which there are two transitions in a HyPEFSM.A hybrid state makes it difficult to assume or determine the single-step probaChapter 6: hybrid PEFSMs 117cxZ:a - synchronous a- asynchronous a - synchronousb - synchronous b - asynchronous b-asynchronous(a) state i is synchronous (b) state i is asynchronous (c) state i is hybridFigure 6.2: The possible situations of two transitions from a statebilities for the transitions starting from that state. For instance, in Figure 6.2 (c),transition ij is synchronous while transition ik is asynchronous. Class ij incoming messages are associated with transition ij and class ik messages associatedwith transition ik. Suppose class ij messages are timeouts and class ik messagesare data packets with acknowledgement information. Usually, the occurrence ofclass ij messages depends on the availability of class ik messages when a HyPEFSM enters state i. For this reason, the single-step probability of transitionij depends on the probability that there is no class ik firable message when theHyPEFSM enters state i. This latter probability is related to the previous occupancies of the states and the previous arrivals of class ik firable messages. Inthis sense, with a hybrid state, the transition probabilities of a HyPEFSM depend on the past state occupancies. As a result, the state changing process ofthe HyPEFSM may not be a continuous-time semi-Markov process (CSMP). Thetheory for non-CSMPs which is much more complex than that of CSMPs shouldbe used to analyze the state changing process of the HyPEFSM. Unfortunately,few results on non-CSMP have been published. Therefore, we are not going tostudy the HyPEFSMs with any hybrid state in this chapter.Chapter 6: hybrid PEFSMs 118In the following, a class of HyPEFSMs which have only synchronous andasynchronous states is examined. A wide range of communication protocols canbe modelled using this class of HyPEFMS. This is because, in general, two typesof data may come to a protocol in the ISO protocol stack model. One typeof data is from the protocol user, the underlying system or a communicationparticipant as requests. The arrivals of these requests can usually be modelledas asynchronous arrivals. The other type is from a communication participantas responses. The arrivals of responses can usually be modelled as synchronousarrivals.We assume that the arrival information of a HyPEFSMs is given. Furthermore, similar to the AsPEFSM, the early asynchronous messages to a HyPEFSMare assumed to wait in queues. The performance metrics such as throughputs,utilization and queue wait time are derived for this class of HyPEFSMs in thischapter.The rest of this chapter is organized as follows. Section 6.2 describes themessage arrival model, the queuing model and the service model. The derivationof the performance metrics is also given in this section. Section 6.3 shows theapplication of the performance evaluation method to the alternating bit protocol and compares the analytical result with the simulation result. Section 6.4summarizes this chapter and provides some suggestion on the applicability of thesolution techniques given in this chapter to a HyPEFSM with hybrid states.Chapter 6: hybrid PEFSMs 1196.2 Models and EvaluationConsider a HyPEFSM, denoted as ‘, which has only two types of states: synchronous and asynchronous.Let (M, 1’) and P = (P, “B, ‘H) be the components of ‘I’. The semantics ofthese components are defined in Chapter 3.6.2.1 Message arrival modelBy definition, incoming messages arrive synchronously or asynchronously to ‘P.The arrival models of synchronous messages in ‘P are similar to those inSyPEFSMs in Chapter 4. Suppose that state i of ‘P is a synchronous state,and class ii firable messages of state i (j E Q) are synchronous. Only one firablemessage of state i will come each time I1 enters state i. We assume the probability that the next incoming firable message is of class ii is Pij (j E Q), and thep.d.f. of the wait time for this message is wh2(t). Both Pij and wh,(t) (j é Q)are given by the performance evaluator, andE Pij 1.jEQThe arrivals of asynchronous messages for each class in ‘P are assumed to bea Poisson process. Suppose that state k is an asynchronous state, and class kiis a class of firable messages of state k associated with transition ki (1 e Q).The arrival pattern of class ki messages is a Poisson process with mean Akj. Thismodel is the same as the a-arrival model of an AsPEFSM-a.Chapter 6: hybrid PEFSMs 1206.2.2 Queuing and service modelWe assume there is a queue for each class of asynchronous incoming messages in‘I’. The queuing discipline of each queue is first in first out. The service disciplineat an asynchronous state is first come first served.When ‘I’ enters a state, if the state is a synchronous state, ‘I’ will wait for afirable message of the state; if the state is an asynchronous state and ‘I! will firstcheck the queues to see whether there is a firable message. If there is none, ‘I’ willwait for the first firable message of this state to arrive; otherwise, it will selectthe earliest arrived firable message from a queue and process it.Therefore, the service model of ‘I’ in a synchronous state is the same as theone for a SyPEFSM. The queuing and service model of iji in an asynchronousstate is the same as the one for an AsPEFSM-o.Similarly, we can compute the transition probability of transition ij for asynchronous state i as:“iiPzj—jQ)ijWith this queuing and service model, the transition probability matrix P of‘I’ can be determined completely and directly from the given arrival model. Sowe assume P is known hereafter.6.2.3 Performance metricsWith the arrival model and the queuing and service model stated above, theprimitive data M, P, H of ‘Ii are known. wh is also known if transition ij issynchronous. So in the following, we first compute the transition wait times forthe asynchronous transitions and then show the derivation of the performanceChapter 6: hybrid PEFSMs 121metrics — throughput, utilization and queue wait time.Computation of UHLet r = [7r} be the steady-state state probability vector of W (i E Q). ByTheorem A.1, r can be computed from the given P. So we assume ir is knownhereafter.From the definition of transition time in Chapter 3, we have, _w.._I_sTjj— T1-i-- Tij.Therefore,— w— j_ 8—Tjj— TjmIf transition ij is synchronous, “j is already given in the arrival model;otherwise, is unknown and must be computed.Suppose that state i is asynchronous. Let NoF denote the event that ‘I’ findsno firable message of state i in the queues when it enters state i and NoF denotethe reverse of NoF (i.e., there is firable message(s)).Let be the probability of the event NoF.Following similar derivation of wh(t) for an AsPEFSM-o presented in Chapter 5, we can also get the following result for I1Wh f (lpo,i) fort=O 63— j pj . jeit for t > 0where= E Ak (6.4)kEQChapter 6: hybrid PEFSMs 122and X1k is the mean arrival rates of class ik incoming messages (k e Q).Since wh1(t) is the p.d.f. of thereforew= ft. ‘h1(t) •dt =P0,1 -, (6.5)andP0,i + . (6.6)In the above equation, P0,i is unknown. To compute P0,1 (i E Q), we adopt thetransformation introduced in Section 5.2.3 to construct virtual jobs with respectto state i of ‘I’. The definitions of first passage, virtual job and virtual job class in‘P are the same as those for an AsPEFSM-o. As a result, we obtain the followingequation that is similar to Equation (5.19):PO,i = 1— (A1(3f+ — AiiOij. (6.7)jEQSimilar to an AsPEFSM-c, when ‘P is in equilibrium, the mean recurrencetime of an asynchronous state, say state i, has the following property:=-. (6.8)However, the mean recurrence time of a synchronous state in W, say state k,still needs to be computed by using Theorem A.5:=— (6.9)Inwherer—InuPuv T.u,VEQChapter 6: hybrid PEFSMs 123is the overall mean transition time in ‘I’. is the transition time of transitionuv which can be rewritten using either Equation (6.2) or (6.6) depending onwhether transition uv is synchronous or asynchronous, i.e.,— I + , if transition ij is synchronous 6— 1 p• - + 9 if transition ij is asynchronousThe formula for is also different for a synchronous state and an asynchronous state. This is an essential difference between a HyPEFSM and anAsPEFSM-o in the derivations of performance metrics.The mean first passage time from state j to i (i, e Q) in Equation (6.7),can be computed using Theorem A.3:=+ Pjk 8ki— Pji ‘ZZ (6.11)kEQ= E Pk’k + Pjk1’8ki Pji”1’i . (6.12)kEQ kEQwhere‘kj can be rewritten using (6.2) or (6.6) depending on whether transitionki is synchronous or asynchronous, and can be rewritten using (6.9) or (6.9)also depending on whether state i is synchronous or asynchronous.Using equations (6.7) and (6.12) (i,j e Q), we can solve PO,i and andfurthermore obtain of asynchronous transition ij (i, E Q) and “6j2 of synchronous state i (i E Q).ThroughputsGiven bOZ,— the mean recurrence time of state i of a HyPEFSM (i e Q), oneis able to compute the mean throughput rate of any specific class of outgoingmessages associated with a transition in ‘I’.Chapter 6: hybrid PEFSMs 124Let i, be the throughput rate of the outgoing messages associated with transition ij.When a system is in equilibrium, it is true that mean throughput rate = meaninput rate. Class ij outgoing messages are associated with transition ij. For thatreason, the throughput rate of class ij messages is equal to the entrance rate oftransition ij, i.e.,= “1’e2p (6.13)= .—p23 (6.14)where-— f 2 if state i is synchronous (6 15)—- if state i is asynchronous‘f is computed earlier.UtilizationLet p be the utilization of a HyPEFSM. p is the ratio of the service time and thetransition time. We can use the following equation to compute p when ‘I’ is inequilibrium:(6.16)Queue wait timesIn ‘I’, there is no queue wait time for a synchronous message. However, anasynchronous message may have to wait in a queue if it arrives early. So here weonly have to compute the queue wait times for asynchronous messages.Chapter 6: hybrid PEFSMs 125Since asynchronous messages of each class arrive in a Poisson pattern, we candraw a conclusion similar to Theorem 5.5. That is, the mean queue wait timesof each class of asynchronous firable messages for an asynchronous state in IF arethe same. As a result, we only need to compute the overall mean queue wait timeof firable messages for each asynchronous state of IIi.This computation of the queue wait time is similar to what we did for theAsPEFSM-o. For each asynchronous state of ‘I’, we construct the virtual jobsas before: a virtual job consists of the consecutive transitions on a first passagestarting from the asynchronous state and ending at the same state. This approachthen transforms the queue system of ‘I’ into an M/G/1. The mean arrival rateof the virtual jobs of an asynchronous state, say state i, is.X is computed byapplying Equation (6.4). The solution techniques for M/G/1 (see, for example,Equation (5.29)) are applied to this M/G/1 to obtain the mean queue wait timeof the asynchronous message of the state.6.3 An Application ExampleIn this section, we apply the performance evaluation method to the alternatingbit protocol introduced at the beginning of this chapter (see Figure 6.1).The workload and system parameters are assumed as follows:The data packets arrive in a Poisson pattern at a mean rate of 50 packets/second. The transmission (or retransmission) of each data packet takes 0.001second. The distribution of wait time for ACK is between 0 and 0.010 secondwith a mean of 0.001 second. We assume that if a timeout occurs for a datapacket, no delayed acknowledge for that packet will arrive. The processing timeChapter 6: hybrid PEFSMs 126of ACK is assumed to be negligible. The loss probability of data or ACK is 0.1.The mean timeout value is set at 0.010 second.The above information is translated into input data required by the two stateHyPEFSM:(poo Poi’( 0 1‘\Pio Pu ) ‘ 0.9 0.1and)‘oo = 0; A01 = 50;oo = 0; = 0.001;= 0.001; W = 0.010;S= 0; ui = 0.001.By solving Equation (A.1) with P, we obtain the steady state probabilities ofthe states in the HyPEFSM9 10ir= (Tro,7r1)=The mean state holding time of the HyPEFSM in state 1 is computed as== pii(ii + 1i) = 0.0020.We can construct the equations for the first passage times between two statesby applying Theorem A.3:—L_ 100——7——Tr o+ri ‘i.oi= o + (P00 %1 + Poi % 1) — Poi 1 =io = ‘‘i + (Pm “‘Oo0 + Pu o) — Pio oo = u + Pu 7I’8uo.From the above equations we can directly obtain= 0.0200 (second), and= 0.0022 (second).Chapter 6: hybrid PEFSMs 127Let Po,o be the probability that a data packet arrives and sees no other datapacket being served or waiting for service. Applying Equation (6.7), we haveP0,0 = 1— )o(°oi + io) = 0.84.This means the probability that a data packet will be served immediately onarrival is 84%.Therefore, we can further derive the mean wait time of transition 01= 0.0168 (second).It means the average time that the system is idle waiting for a data packet is0.0168 second.With Wf we obtain= 0.0178 (second), and= 0.0180 (second).To compute the mean queue wait time of the data packets, we construct thevirtual jobs which consist of the transitions on the first passages from state 0 tostate 0. The second moment of the service time of the virtual jobs is computedas using Equation (B.1)—— o1= Sr + + 2•= 0.0000373.Then, the mean queue wait time is computed using Equation (5.29)\ t2117________VVq,O =2(1— Po)Chapter 6: hybrid PEFSMs 128where P0 = 1— Po,o = 0.16.A simulation run was also conducted to obtain the performance under thesame workload given above. The simulation results confirm the analytical results(see Table 6.1).performance metric analytical result simulation resultoo 0.0200 0.0199Oo 0.0178 0.01770.0022 0.0022u 0.0180 0.0179Po,o 0.8400 0.8404system utilizationa 0.0556 0.0557mean queue wait time 0.0011 0.0012aSee Equation 6.16.Table 6.1: Comparison of analytical result and simulation resultLet A0 be a variable while the other input data remain the same. We cananalyze the relation between the mean queue wait time of the data packets andtheir arrival rates. Figures 6.3 and 6.4 show such a relation. It can be seenintuitively from Figure 6.4 that the mean queue wait time grows rapidly whenthe mean arrival rate is larger than 250 packets/second.We can also let the packet loss probability (i.e., Pu) be a variable and analyzethe relationship of the mean queue wait time as a function of the packet lossprobability. Figure 6.5 illustrates that the growth of the mean queue wait timeincreases rapidly when the loss probability is larger than 50%.C)U)U)E.1-I.1-)•rIU)a)a)Queue wait time vs arrival ratea)0 1to0.150.1250.10.075U)0.050 . 025200 250 300(packets /sec)Figure 6.4: Mean queue wait time vs. mean data arrival rate6.4 Summary and DiscussionWe have given the derivations of throughput, utilization and queue wait time fora HyPEFSM with two types of states: synchronous and asynchronous. The so-Chapter 6: hybrid PEFSMs 129Queue wait time vs arrival rate0 20 40 60 80Mean arrival rate (packets/sec)Figure 6.3: Mean queue wait time vs. mean data arrival rateU) 0 50 100 150Mean arrival rateChapter 6: hybrid PEFSMs 130Queue wait time vs packet loss probabilitya)‘— 0.070.060.05-Ii0.040.03U)0.020 0.1 0.2 0.3 0.4Packet loss probabilityFigure 6.5: Mean queue wait time vs. packet loss probabilitylution technique for performance is basically a combination of the techniques forAsPEFSM-o and SyPEFSM. The assumptions used in HyPEFSMs comprise ofthe assumptions of AsPEFSM-o for asynchronous transitions and the assumptions of SyPEFSM for synchronous transitions. The HyPEFSM is more realisticin practice than either the AsPEFSM or the SyPEFSM alone.The performance evaluation of the alternating bit protocol is shown as anapplication example of the HyPEFM. A more complex example describing theperformance analysis of a class of multi-stage interconnection networks is givenin Appendix E.We have also briefly discussed that the main difficulty in solving a generalHyPEFSM is in the treatment of hybrid states. With a hybrid state, the statechanging process of a HyPEFSM is not a CSMP. A more general theory of stochastic processes needs to be employed and the computation will probably be much0.5Chapter 6: hybrid PEFSMs 131more complex.In spite of this, a hybrid state of a HyPEFSM can be modelled as a combination of synchronous and asynchronous states if we know the probability thatsynchronous transitions from the state are selected (or the probability that asynchronous transitions are selected). This is shown in Figure 6.6.} synchronous transitions with the probability p} transitions with the pmbahility (l-p)schronous transitionsp(l-p)Figure 6.6: Modelling of a hybrid stateState i is originally a hybrid state. The probability of synchronous transitionsfrom state i is known to be p. In the equivalent model, state i becomes a synchronous state. Two new states i’ and i” are added, and they are synchronousand asynchronous, respectively. We also add two new transitions: the one fromi to i’ is with probability p and its transition time is 0; the other is from i to i”with probability (1—p) and its transition time is also 0. All the synchronousChapter 6: hybrid PEFSMs 132transitions from state i are moved to state i’; and all the asynchronous transitionsare moved to state i”.After each hybrid state of a HyPEFSM has been modelled in this way, theHyPEFSM has only two types of states: synchronous and asynchronous. Thesolution techniques presented in Section 6.2 can thus be applied to this HyPEFSMto obtain the performance measures.The probability p can be obtained through measurement or simulation. Thisapproach combines analytical method with simulation result to evaluate the performance of a complex system. This concept has been used by other researchers.For example, in [KrWh93], many performance parameters such as the singlestep transition probability matrix P and transition times are obtained throughsimulation based on a formal specification.Chapter 7Analysis of PerformanceBottlenecks using PEFSMsAbstractThis chapter studies the problem of identifying performance bottlenecks in communication protocols. The identification method is based on the performance modelPEFSM which is defined earlier in Chapter 3. Informally, a bottleneck with respect toa performance metric is defined as the transition among all the transitions in a PEFSMwhich would produce the largest marginal improvement of the performance metric ifthe time of the transitions were reduced by the same small amount. We present twomethods to locate the bottleneck transitions with respect to two of the most importantperformance metrics: throughput and queue wait time. These methods are partiallyvalidated using simulation results.133Chapter 7: bottleneck identification 1347.1 IntroductionIn the previous three chapters, we have presented techniques to compute performance measures based on PEFSMs from given arrival information. In thischapter, we are interested in how to improve system performance in an efficientway. The key step in solving this problem is to identify the performance bottleneck.Performance bottlenecks exist in almost all computer systems in various forms.System designers, analyzers and users have worked on detection of the performance bottlenecks in a computer system for a long time. A bottleneck can bea service center of a system [Leung88, Allen9O] or, at a more abstract level, asystem parameter. For instance, in [ZiEt92j, the sensitivities of the parametersin the throughput expression are used to determine the throughput bottleneck.There exist many definitions of performance bottlenecks and most of them aredefined with respect to only throughput or utilization [Ferr7S, Lock84, Leung88,Yang89, Allen9O, ZiEt92].Nevertheless, all definitions of performance bottleneck have a common characteristic: a bottleneck is referred to the component in the system which hasthe most significant impact on system performance. A small improvement to thebottleneck component can greatly improve system response time, throughput orutilization.This chapter is concerned with finding performance bottlenecks in communication protocols. We have noted that it is common to specify communicationprotocols as interacting FSMs or EFSMs which are FSMs extended with variables.Many standardized protocols are directly given as FSMs or EFSMs. ExamplesChapter 7: bottleneck identification 135can be found in [Tane88, 1S02576, 1S07776j. At least two internationally standardized formal description techniques exist (Estelle [1S08807} and SDL [SDL])which provide a way to specify protocols and distributed systems based on FSMsor EFSMs. Therefore, it is reasonable to use a PEFSM which is defined based onEFSM (Chapter 3) as the underlying model for detection of performance bottlenecks. PEFSMs have been shown in the previous chapters as effective models forperformance analysis.In the FSM of a PEFSM, state and transition are the two main constructs.States are conceptual while transitions have direct correspondence in the implementation of the protocol specified by the FSM. The time of a transition directlyaffects performance. Therefore, it is natural to transform the bottleneck detection problem to the one of identifying the bottleneck transition in a PEFSM. Thisis useful because we then know where we should focus our efforts to improveperformance.The execution of a transition takes time which in turn may delay the processing of the following incoming messages of a PEFSM. The following messages maybe associated with other transitions in the PEFSM. Reducing the transition timein a PEFSM will improve the performance of the PEFSM. For example, reducinga transition time will increase the throughputs of each class of outgoing messagessince the recurrence times of each state are decreased. However, the degree ofimprovement to a performance metric depends on selected transitions. The onewhich can cause the most improvement to a performance metric is identified asthe bottleneck of this performance metric.We use weight to indicate the relation between the reduction of the time of atransition and the improvement of a performance metric. A weight with respectChapter 7: bottleneck identification 136to a performance metric is computed for each transition in a PEFSM. The higherthe weight of a transition with respect to the same performance metric, the morethe performance metric can be improved by reducing the same amount of time ofthis transition. As such, the transition with the greatest weight with respect to aperformance metric is the bottleneck transition with respect to the performancemetric. For instance, if the weight of transition ij in a PEFSM with respect tothe mean queue wait time of a message class is greater than that of any othertransition, then transition ij is the bottleneck transition with respect to the meanqueue wait time. In other words, if each transition time is independently reducedby the same amount, the mean queue wait time will decrease the most in the caseof a reduction in transition ij.In this chapter, we focus on two of the most important performance metrics ofa PEFSM. They are the throughput rate of a class of outgoing messages and themean queue wait time of a class of incoming messages. The methods to computethe weights of transitions with respect to each performance metric are presentedin this chapter.The first method is to use partial derivative. In general, if a performancemetric 1C can be expressed as a function of a set of parameters, t1, t2, .., t,then the partial derivatives of K with respect to t1, t2, .., t,,aca,c9t1’Ot2 ‘Ot,’indicate the relative impacts of the changes of each parameter on the performancemetric. The largest derivative, say (1 k n), indicates the correspondingChapter 7: bottleneck identification 137parameter, tk, has the greatest impact on the change of JC, and thus tk is thebottleneck of K. Therefore, the partial derivatives can be used as the weights ofthe parameters. In our case, we compute the partial derivatives of the throughputof outgoing messages of a specific class with respect to each transition time.These derivatives are taken as the weights of each transition with respect to thethroughput.The second method is to use an approximate approach to computing theweights with respect to the mean queue wait time of a specific incoming message class. This is because in the second case, it is difficult to compute partialderivatives.We again assume that the transition probability matrix, P, and the steady-state state probability vector, ir, are known. They can be obtained using thetechnique described in the previous three chapters.The rest of the chapter is organized as follows. Section 7.2 presents a methodto locate the bottleneck transition of the throughput rate of a class of outgoingmessages. Section 7.3 presents a different method to compute the weights foreach transition with respect to the mean queue wait time of a class of incomingmessages. The method is partially validated with a simulation. Section 7.4discusses related work on defining and locating performance bottlenecks, andSection 7.5 summarizes this chapter.Chapter 7: bottleneck identification 1387.2 Throughput BottleneckIn a PEFSM, an outgoing message of a class is generated when the transitionassociated with the class is processed. Therefore, the throughput rate of the outgoing messages of a class is equal to the entrance rate of the transition associatedwith the class.Let ‘t’e, and ë3 be the mean entrance rates of state i and transition ij of aPEFSM, respectively. From the FSM of the PEFSM, we havee23 — e2 Ptjwhere Pu is the probability of transition ij.By Theorem A.4, one can infer——TriPijEU,VEQ lrvPuv “‘iuvLet i be the throughput rate of class ij outgoing messages. Then,_.._,,_••_1iPij— e23—YU,VEQ uPuv TUVThe above equation illustrates the relationship of the throughput rate andthe transition times‘,,(u, v E Q). For a given PEFSM, ripij (i, E Q) is fixed.So the change of i relies on the denominator of the above equation.Using the derivatives, one can find that the coefficient lrvpuv of in thedenominator indicates the relative degree of the improvement of f, by transition uv (u, V E Q) compared to the other transitions. 7rVPUV in fact is thesteady-state probability of transition uv. Among the transitions, the one withChapter 7: bottleneck identification 139the largest steady-state transition probability has the greatest impact on increasing the throughput rate ,.So we can define lrvpuv as the weight of the transition uv with respect tof,. The bottleneck transition. of f is the transition which has the largest 7rvpuv(u,veQ).Since lrvpuv (u, v E Q) is not related to flj,, we can further conclude that thebottleneck transition is the same for the throughput rates of outgoing messagesof all the classes.7.3 Queue Wait Time BottleneckIn Chapter 3, PEFSMs are classified into three types: SyPEFSMs, AsPEFSMsand HyPEFSMs. The incoming messages in a SyPEFSM have no queue waittime. Only incoming messages in an AsPEFSM or asynchronous messages in aHyPEFSM may experience queue waits. Therefore, AsPEFSMs and HyPEFSMsare the two types of the PEFSMs that will be studied in this section. For simplicity, we use PEFSM to refer to an AsPEFSM or a HyPEFSM in the rest ofthis section.From the derivations of mean queue wait times, we know that different incoming message classes may experience different queue wait times on average. Weare interested in identifying the bottleneck transition with respect to the meanqueue wait time of a specific class of incoming messages, say Wq,:j.First of all, we will revisit the computation of the mean queue wait time ofincoming messages of a specific class in an AsPEFSM-a. The incoming messagesChapter 7: bottleneck identification 140of a class are assumed to arrive asynchronously and in a Poisson pattern. Withthis assumption, it can be proved that the mean queue wait times of differentclasses of firable messages of a state are the same, i.e.,Wq,ij = Wq,i (i,j E Q).So we need only to compute the overall mean queue wait time of all the classesof firable messages of a state.To compute the overall mean queue wait time, we construct the virtual jobsof a state and treat the queuing system of the PEFSM as an M/G/1. The meanqueue wait time is computed by applying the well-known solution technique forM/G/1‘ \ -2— Aj— L.ijEQ”ij’ij— 2(1—p) — 2(1—p)In the above equation, is the second moment of the service time of classij virtual jobs. From Appendix B, we see that to compute c (i, E Q), a set ofequations must be solved. The closed-form solution of ( is difficult to obtain.So it is infeasible to compute the partial derivatives of Wq,j with respect to eachtransition time (u, v E Q) for use as the weights to identify the bottlenecktransition of Wq,j. Therefore, the following approximate solution is proposed tocompute the weights for each transition with respect to the mean queue wait timeof a class of incoming messages.An approximate approachAs mentioned earlier, the FSM of a PEFSM provides the service order of incomingmessages. This ordering affects the performance of the PEFSM and should beChapter 7: bottleneck identification 141taken into consideration to obtain more accurate results.In general, we can assume the queuing system of a PEFSM consists of asingle server with a single queue. Figure 7.1 shows a queuing system which servesa PEFSM. The service order of incoming messages is controlled by the FSM ofthe PEFSM and the incoming messages.z. J*iOFigure 7.1: Service order implied by the FSM of a PEFSMWe know that an asynchronous incoming message to a PEFSM may arrivebefore the PEFSM is ready to process this message. When this happens, themessage will have to wait in a queue. The queue wait time of this message isthe elapsed time between the moment it arrives and the moment it is processed.From Figure 7.1, it is not difficult to see that the waiting period of this messageincludes not only the processing times of all the messages of the same class whichAChapter 7: bottleneck identification 142arrived earlier, but also the processing times of the transitions associated withthe messages of other classes. These transitions bring the PEFSM to the rightstate so that the target message can be processed. For example, in Figure 7.1,message m3 has to wait for service until the transitions associated with ml andm2 are processed.Next we will show how the incoming messages of a class in a PEFSM waitstatistically when they arrive early. First, we define transition path and transitionsubpath.Definition 7.1 (transition path) A transition path of a PEFSM is a sequenceof consecutive transitions in the PEFSM.Definition 7.2 (transition subpath ii) A transition subpath ij of a PEFSMis a finite number of consecutive transitions in the PEFSM starting from state iand ending at state j. The first transition of the subpath is called the head of thesubpath; the last transition is called the tail of the subpath.Figure 7.2 shows a state-transition tree of a PEFSM. Each state in the treeis a state in the FSM of the PEFSM; each transition is a transition in the FSM.This tree includes all the possible transition subpaths to transition ij.Suppose -y is an incoming message of class ij of the PEFSM and Wq,jj (Wq,ij >0) is the queue wait time of -y. Suppose transition subpath 1 in Figure 7.2 includesthe transitions which must be processed before -y.Assume the PEFSM is in state k0 when -y arrives. Then, the transition subpathk0i includes the transitions which are seen by -y and which will be processed before‘y. Let these transitions be transitions k01,k12,..., km_ikm (km = i), and D1,D2, D3, Dm are their transition times, respectively.Chapter 7: bottleneck identificationFigure 7.2: The subpaths to transition ij in a PEFSMBy definition, we havem mDn<Wq,ijn=2 n=1143(71.)Transition k01 may be already in process at the time -y arrives. The othertransitions have not yet been processed by then.We know that -y will wait until the processing of these transitions is finishedwhether or not the incoming messages associated with them have already arrived.The decrease of the transition time of any of these transitions will reduce thesubpath IIIsubpath 2Chapter 7: bottleneck identification 144queue wait time of y, Wq,jj. If some transitions appear in the transition subpathk0i more than once, then decreasing the time of the transition which appearsmost often in the subpatb will reduce Wg,ij the most.However, different class ij messages may see different transition subpathsat their arrivals. Furthermore, a transition may be seen in different transitionsubpaths. So the relative frequency of each transition subpath seen by shouldbe taken into account while computing the weights for all the transitions withrespect to Wq,jj. The relative frequency of a subpath can be computed using thetransition subpath probability defined below.Definition 7.3 (transition subpath probability) The probability of a transition subpath k0m is defined as:Pr{subpath k0m}where transition k_1 (n = 1, 2, ..., in) are the transitions of the subpath and= 7rk_1Pkis the steady-state probability of transition k_1. Pk_Ikis the single-step probability of transition k_1.Given the probabilities of transition subpaths, we can compute the relativefrequency of a transition seen by a specific class of incoming messages. Thefrequency is the sum of the probabilities that this transition appears in all thepossible transition subpaths which satisfy Inequality (7.1). It is useful to computethe relative frequency of a transition because decreasing the time of the transitionwith the highest frequency by the same amount will reduce the mean queue waittime of the specific class the most. Therefore, in this case, the frequency can beused as a weight to identify the bottleneck transition of the mean queue wait timeof the incoming messages of the specific class.Chapter 7: bottleneck identification 145Let w,.L, be the weight of transition uv. From the discussion above, we candefine= (Pr{subpath l} Pr{transition uv appears in the subpath l}).lésubpathsNext, we present an algorithm to compute the weights, given the mean queuewait time of a class of incoming messages.Computation of weightsAssume that the single-step transition probabilities in P of a PEFSM are given,and the steady-state state probabilities r as well as the transition times of eachtransition have been computed.Suppose Wq,ij is known either by computation or measurement. An algorithmto compute the weights with respect to Wq,jj is provided in Figure 7.3.Procedure 1 of the algorithm initializes all the weights to zero before callingProcedure 2. Procedure 2 computes the weights for all transitions in the PEFSM.Using a recursive procedure, it traverses all the transition subpaths which endat state i and satisfy Inequality (7.1). The subpath starts backwards from statei. A transition is added to the current head of the subpath in each iteration.This transition becomes the new head transition of the subpath. The transitionsubpath grows until the sum of the mean transition times of the transitions alongthe subpath is larger than the given mean queue wait time, Wq,jj. At each step,the current subpath probability is added to the weight of the head transition.When Procedure 2 terminates, the weights of all the transitions in the givenPEFSM with respect to the mean queue wait time, are computed. TheseChapter 7: bottleneck identification 146Procedure 1 : compute weights given mean queue wait timeInputs: Wq,jj — the mean queue wait time of class ij incomingmessages;Outputs : the weights of all the transitions in the PEFSM, w,L,(u,v e Q);Steps1. initialize the weights of all the transitions to zero,i.e., w23 = 0 for i,j E Q;2. call Procedure .2 with arguments (1, ii, Wq,jj).Procedure 2: recursively backtrack to add the subpath probabilitiesto the transitions which are the heads of the subpathsInputs: 1) the current subpath probability p;2) the reference of the current transition uv;3) the remaining waiting time R;Outputs : weights of the transitions;Steps1. if R 0, return;2. for (each transition which is immediately before the currenttransition uv in the FSM of the PEFSM, say transitionku) do:1) let p= p * i4 where p is the steady-state transitionprobability of transition ku;2) let Wku Wku +p3) call Procedure 2 with arguments (p, ku, (R—endfor.Figure 7.3: Algorithm for weight computationweights reflect the relative frequency of the transitions seen by class ij incoming messages. If the transition time of each transition is reduced by the sameamount one at a time, the one which has the largest weight will cause the largestimprovement in the mean queue wait time of class ij messages. Therefore, theChapter 7: bottleneck identification 147transition with the largest weight is the bottleneck transition with respect to thismean queue wait time.Simulation resultsSimulations have been conducted to validate the accuracy of the bottleneck identification method. The architecture of the simulation experiment is shown inFigure 7.4.The simulator module accepts a model description of the PEFSM and simulates the execution of transitions in the FSM of the PEFSM. The module contains an incoming message generator which generates the incoming messages tothe PEFSM based on the given arrival model of the PEFSM.The simulation results are fed to the weight computations module. This computation module also stores the description data of the PEFSM. The algorithmsin Figure 7.3 are used to compute the weights for all transitions with respect tothe mean queue wait time of a specific transition. Upon completion of the corn-transition waiting times andtransition probabilitiesFigure 7.4: A simulation architectureChapter 7: bottleneck identification 148putation of the weights for all transitions, the module identifies the bottlenecktransition.The modification module reduces the service time of each transition of thePEFSM by the same small amount one at a time. This module resends themodified data of the PEFSM to the simulation module and the simulation isrerun. All the mean queue wait times of class ij incoming messages in each runare recorded so as to verify if the bottleneck transition in fact causes the largestreduction in the mean queue wait time.Several protocols were used in our experiments which showed that the proposed technique for bottleneck transition identification works in practice. Wereport the result of the alternating bit protocol in the following and put otherresults in Appendix F.The FSM of the alternating bit protocol is given in Figure 6.1. The assumptions about this protocol are the same as those given in the introductionto Chapter 6. So the FSM with these assumptions is a HyPEFSM. The inputdata of the HyPEFSM are given in Columns 1, 2 and 3 of Table 7.1. The incoming data packets to be transmitted are asynchronous and their arrivals follow aPoisson pattern. All other transition wait times and transition service times areexponentially distributed. Their mean values are given in Columns 2 and 3 ofthe table, respectively.Columns 4, 5 and 6 are the simulation results. The steady-state transitionprobabilities are recorded in Column 4. These results agree with the results fromcomputation of p = 7fjjj where ir is the steady-state probability of state i andPij is the single-step probability of transition ij. The weights are computed withChapter 7: bottleneck identification 149transition mean wait mean service transition transition queue waitidentifier timea time probability6 weightc time reductiondTOl 200.Oe 0.001 0.4738 0.3102 0.0069T10 0.001 0.001 0.4738 0.6207 0.0090Til 0.001 0.001 0.0525 0.0343 0.0010°A1l times are in seconds except when otherwise indicated.‘Steady-state transition probability.cThe weight is computed with respect to the mean queue wait time of the data packets.dThe new average queue wait time is measured by decreasing the mean service time of thecorresponding transition by 0.002 second. The reduction of the queue wait time is equal to theoriginal value minus the new value.is the mean arrival rate (packets/second) because this transition is asynchronous.Table 7.1: A simulation result of bottleneck identificationrespect to the mean queue wait time of a class of incoming messages and recordedin Column 5. Then, in each of the following runs, we select one of the transitionsand reduce its service time by a small amount. The simulation is re-run with themodified data. The reduction in mean queue wait time is recorded in Column6. This procedure is repeated for all the transitions. From the table, we can seethat reducing the service time of the transition with the largest weight causes thelargest reduction in the mean queue wait time of that class of incoming messages.This result confirms the analysis given in this section.Experiments with different workload parameters were performed for severalprotocols. In most cases, the results (as in Table 7.1) from simulation agreedwith the analytic results. Only a few exceptions were found. However, eventhen, the reduction of the mean queue wait time by reducing the service timeof the bottleneck transition is close to the largest reduction. The reason whythe bottleneck transition occasionally is not identified correctly is that both theChapter 7: bottleneck identification 150queue wait times and the transition times have variance and we use oniy themean value to compute the weights for simplicity.7.4 Related WorkPerformance bottleneck detection and removal has received less attention in theliterature than performance prediction. This is not only because the problemitself is hard but also because there is a lack of adequate formal definitions andeffective analysis methods. Only a few methods have been proposed to locate theperformance bottleneck of a software system.The concept of critical path was first introduced in the context of projectmanagement and used to manage the progress of projects [Lock84]. It was lateradopted for parallel processing systems [Yang89j where there are both parallelevents and synchronization points. The critical path of a parallel program is thepath in the program activity graph’ which determines the program performance(e.g. shortest execution time). The scope of the potential bottleneck is reducedto within the critical path. Other techniques are used for locating the bottleneckwithin the critical path.Lockyer’s critical path analysis [Lock84] is often used to identify bottlenecksof parallel or distributed systems which are modeled as acydic directed graphs[Yang89, Wagn93].However, only one transition in a PEFSM can happen at a time. The execution of the transitions in a PEFSM are sequential and in a certain order.‘A program activity graph is a directed graph which depicts the synchronization points ofthe whole system.Chapter 7: bottleneck identification 151There is no synchronization with other transitions in a single PEFSM. Therefore,the method of critical path analysis cannot be directly applied to PEFSMs inidentifying bottlenecks.Although intuitively we all know what a bottleneck is, historically, the termbottleneck has had various definitions. They can be classified into the followingtwo categories according to their usage• definitions based on analytic approaches• definitions based on measurementsUsing a derivative is an analytical approach to identify a performance bottle—neck. For example, in [Ferr78], the derivatives of the mean throughput rates withrespect to the service rates of the constituent servers of the system are used todefine performance bottlenecks analytically. Suppose T is the mean throughputrate of the object system, and ik is the service rate of server E (k=1,2,...,s). If8T 87’.OUz UP2then server E, is the performance bottleneck of a system with s servers.However, this definition presents some problems. It cannot be used wheneverT is not differentiable. Moreover, the performance bottleneck is related to theperformance metric. The bottlenecks with respect to different metrics may bedifferent.Utilization based techniques constitute another analytical way to determineperformance bottlenecks [Leung88, Allen9O]. Among the servers in a queuingnetwork model, the one with the highest utilization or the one which first achievesChapter 7: bottleneck identification 152100% utilization with increasing workload on the system is considered to be thebottleneck of the system. However, this approach is not appropriate for a PEFSMbecause it is assumed to have only one service center.Generally, the analytical definition is applied to a model of the system. Whenan implementation of the system already exists, analysis of data from measurement can be used to identify the bottleneck. In [ZiEt92], the bottleneck is definedas the performance parameter which is most sensitive to performance. The sensitivity of a parameter is defined asdef %ChangelnPerformancesensitivity—%ChangelnParameterIntuitively, the sensitivity is similar to the weight to a certain extent. Bothcan be used in analytical approaches and measurement approaches.7.5 SummaryWe have proposed a methodology for identifying performance bottlenecks basedon the PEFSM performance model. As in the case for performance evaluation,the bottleneck identification methodology can be used in the design phase givenonly the specification, and also on an implementation when some of the modelparameters can be directly measured. In the latter case, it is still necessary tohave a formal specification of the implementation.Weights are used to measure the impact of the reduction of each transitiontime on the improvement of a specific performance metric. The bottleneck withrespect to a performance metric is defined as the transition in the PEFSM withthe maximum weight.Chapter 7: bottleneck identification 153The methods to compute the weights of the transitions in a PEFSM withrespect to two performance metrics are presented. The first method makes useof the closed-form expression of a performance metric such as throughput. Thisrequires both the closed-form expression of a performance metric and the partialderivatives of the performance metric with respect to each transition time to exist.The second method uses an algorithm to compute the weights with respect to aperformance metric. This method is used when no closed-form expression of theperformance metric or the derivatives exists or is easily computable.The second method which identifies the bottleneck transition with respect tothe mean queue wait time of a specific class of incoming messages is more generalthan the first one. It can be applied to the PEFSM in which the arrivals ofasynchronous messages are not Poisson, and the mean queue wait time may beobtained either by measurement or through computation.The mean transition time of the bottleneck transition can be reduced in twoways: reducing the mean transition wait time or the mean transition service time.To reduce the mean transition wait time, one may increase the arrival rate of theincoming messages associated with that transition. For example, we can increasethe throughput rate of messages or decrease the queue wait time of messages in aspecific workstation by shortening the token turnaround time for this workstationin a token ring network. To reduce the transition service time, one may try toimprove the software implementation of that transition or use faster hardware toprocess that transition.Chapter 8On Transition Time Testingbased on FSMsAbstractA number of methods have been developed to evaluate communication protocolperformance based on finite state machines (FSMs). One of the examples is to usePEFSMs. This is introduced in the previous chapters. The service times of the transitions are one of the key parameters in the performance analysis and are assumed tobe known a priori. This chapter presents a methodology to estimate transition service times by testing when the protocol implementation is given as a black box. Anapproach to deriving test sequences for transition service time testing is also proposed.8.1 IntroductionIn the previous chapters, we have discussed how to use PEFSMs to evaluatethe performance of communication protocols and to identify bottlenecks. In ouranalysis as well as in the work by others, the service times of the transitions in aPEFSM are primitive data and assumed to be known a priori. To our knowledge,no work has addressed the issue of how the transition times can be obtained,154Chapter 8: transition time testing 155particularly when the protocol implementation is given as a black box.In this chapter, we propose an approach to obtain the transition service timesof a communication FSM through performance testing. Since performance testinghas different meanings depending on the focuses of the studies, we shall classifyperformance testing for communication protocols into three categories1. transition time testing2. saturation testing3. benchmark testingEach of the above tests different performance aspects of the protocol implementation under a different workload condition. The objective of transition timetesting is to measure the transition service times with respect to the FSM on whichthe protocol is based; saturation testing aims at measuring the peak performanceof a communication protocol under the condition that a specific service centeris saturated; and benchmark testing is used to predict the system’s performanceunder a specific workload and hardware/software platform. In this chapter, onlytransition time testing is discussed.A major problem that makes transition time testing difficult is that the implementation under test (JUT) of a protocol is often given as a black box sothat inserting internal measurement points is almost impossible. Moreover, sometransitions in the FSM of a protocol can be invisible in that only their inputs oroutputs (but not both) are observable. To make matters worse, often a transitioncan produce a variable number of output messages and the transition can stillbe in progress at the time its first output message is seen from the outside. OnChapter 8: transition time testing 156the other hand, the transition may have finished before its first output messageis observed; or the transition has to wait in an internal queue until the previous transitions finish execution. Therefore, measured response times are ofteninaccurate, especially when the time period is measured in milliseconds or microseconds. It should be obvious from the above discussion that measuring thetransition times accurately is not a straightforward matter.This chapter presents a methodology for measuring/computing the transitionservice times effectively under certain circumstances. We assume the measurement is done under the same conditions as conformance testing as described inISO 9646 [ISO9646a]. The testing method (or architecture) used can be remotemethod [ISO9646a], and the JUT and the tester can be in different machines. Wedo not require the availability of globally synchronized clocks as long as there isa way to timestamp all the output data from the JUT and send the log file to thetester. Futhermore, we assume the JUT has already passed conformance testing,i.e., it is correct with respect to the specification.The rest of the chapter is organized as follows. Section 8.2 discusses therelationship between service times and response times and proposes a techniquewhich we shall call the t-test (standing for transition termination test) to estimatethe service times based on response times. Section 8.3 studies techniques dealingwith invisible transitions. Section 8.4 presents a framework for generating testsequences for transition time testing. Finally, Section 8.5 concludes the chapter.Chapter 8: transition time testing 1578.2 T-testAn JUT is an implementation of an FSM (or an EFSM). Since we have assumedthat the JUT has passed conformance testing, it is considered to be correct withrespect to the FSM. Furthermore, according to ISO 9646, the JUT is given as ablack box for conformance testing purpose. The tester may only send messages toan JUT and measure their response times. The measured data are used to analyzethe performance. An abstract architecture for performance testing is shown inFigure 8.1, where a tester simulates the peer entity which communicates with theJUT.ASPsTesterImplementationPDUs (Coordination &UnderTestMeasurement(IUT) Procedures)ASPsASP-- abstract service primitivePDU-- protocol data unitFigure 8.1: A sample conceptual testing architectureJn FSMs, transition and state are the two basic constructs. A state is rathera logical notation which represents some specific conditions of the system. Atransition usually consists of input and output events and data processing.Chapter 8: transition time testing 158Conceptually, the current state of an JUT changes after the JUT has receivedan incoming message from the environment and finished execution of the transition associated with the message. Therefore, executing an JUT can be viewed asexecuting a sequence of transitions of the corresponding FSM while moving fromstate to state.The intervals of sending messages to an JUT are crucial in performance testing.This is further explained in the following.Lett - the service time of message i;- the response time of message i;- the transmission delay of message i from the tester to the JUT;W, - the queue wait time of message i;- the latency of message i.t, is the service time of the transition associated with message i which includesonly the CPU time but no queue wait time as defined in Chapter 3. i, is definedas the interval between the time when the message is sent and the time when thefirst response (usually an outgoing message) is seen. For simplicity, we also usethe response time of a transition to refer to the response time of the message thatinvoked the transition. Note that some transitions may not produce any outgoingmessages and thus the response times of these transitions cannot be measureddirectly. This will be discussed in the next section.Normally, i can be measured directly and accurately if the transition associated with message i produces any output. However, t, cannot be accuratelymeasured because the transmission delay and the internal queue wait time forChapter 8: transition time testing 159service are difficult to obtain precisely when the JUT is given as a black box. Forthis reason, we propose a technique using the next message’s response time toestimate the transition service time.As shown in Figure 8.2, D2 is the interval between the moment that messagei is sent by the tester and the moment that the message arrives at the JUT. W, isthe time message i spends on waiting for service1. 6 is defined as the interval fromthe time when message i is sent by the tester to the time when the correspondingtransition begins to be executed. Their relationship can be expressed aswhere 6, is the latency of message i, D2 is the transmission delay of message iand W is the queue wait time of message i.i responseIsmetservice time t service time (IUTTimemessage sendingr___________________________________testersend message (i-i) send message iFigure 8.2: A sample time diagram of message sendings and executionsJn general, will decrease if ‘5 decreases. When the message sending intervalr increases, W will decrease (if W2 > 0). This in turn will reduce 6 and i.‘As defined in Chapter 3, to service an incoming message means to execute the transitionassociated with the message.Chapter 8: transition time testing 160In order to obtain the service time of transition i accurately, the interval r ofsending message i from the tester should be increased until i. will not reduce anyfurther. This means the waiting time W is approximately zero (i.e., processingof the previous transition is completed by the time when message i arrives). Inthis case, ö D. This situation is illustrated in Figure 8.3.responsetimet1service time t____,.j service time tJUT ‘ I I‘Timemessage sendinginterval titestersendinessage(i-1) sendmessageiFigure 8.3: A sample time diagram where there is no queue wait timeD, can be obtained accurately if the test environment is controllable. D2 canbe assumed to be negligible if the tester and the JUT are on the same computerand there is no other job with higher priority running concurrently with the JUT. 2This means that the technique is most useful when the tester and the JUT are onthe same computer or in the same location connected by a short and dedicatedlink where network load variation is not a problem. Under this condition, andassuming the response time and the service time end at the same time (we shallrelax this assumption later on), we haveti.2j this case, the value is usually very small compared to the other times.Chapter 8: transition time testing 161From the above analysis, we see that the tester should control not only whatto send to the JUT but also when to send it. When there is no queue wait time,the response time of a message provides a rough estimate of the service time ofthe corresponding transition.The above discussion also shows that the response time of a message canbe used to determine whether or not the processing of the previous transitionhas completed. This is useful when the response time of the previous transitioncannot be directly observed externally, or when we would like to have a moreaccurate estimate of the service time but the response time and the service timedo not end at the same time. The technique is called t-test and is explained indetail in the following.Suppose message i is sent at time A in Figure 8.4, and at time B the firstresponse due to message i is seen. Assume that the processing of the transitionassociated with message i finishes at time C. C may be before or after B, and Cmay not be observable externally to the JUT because of the black box assumptionof the JUT. Our objective is to determine C which will allow us to derive theservice time of the transition associated with message i (i.e., AC).H ‘:A lB D Ic EI(E’) Timesend messagei see response w message i send message i+1end of transitionsend message it-I in next roundservice time of transition i in the expanding phaseFigure 8.4: Selecting the message sending intervalsChapter 8: transition time testing 162We select a time E’ to send the next message (i.e., message (i+ 1)) to the JUT.E’ must be chosen after the last response to message i is seen. To determinewhether or not the JUT has finished processing the previous transitions at E’,we repeat the sequence of message transmissions except that in the next round,message (i + 1) is sent at time E” where the interval between B and E” is twiceas long as the one between B and E’, i.e.,(E”—B)=2.(E’—B).It is known from the prior discussion that increasing the sending interval willreduce or eliminate the queue wait time of message (i+ 1). Therefore, the responsetime of message (i + 1) can only decrease (or remain unchanged). If there is nochange in the response time in this round of test, it means the JUT has finishedprocessing message i and its associated transition by time 0. If not, the previousstep is repeated using the same test data but moving E’ to E” and selecting anew value of E” as before. This is continued until there is no change in responsetime or the change is smaller than a predefined small threshold.Without loss of generality, let us call the time instant E’ that was determinedin the round before the last one E, and the smallest response time that weobtained as RH4. The value of E’ in the second last round is used because theresponse times in that round and the last round are the same. Taking the valueof the second last round will reduce the overhead in the next phase of testing (seebelow). The interval between A and E is recorded as Based on the previousdiscussion, it is obvious that i is the smallest response time for message (i+1).This phase is called the expanding phase because E’ is moved further and3The transition associated with message i may generate more than one outgoing message.Chapter 8: transition time testing 163further from A. This is achievable because the testing environment is completelyunder our control so that no other jobs will interfere with the testing. The queuewait time will be zero when the message sending interval is larger than the servicetime of the previous transition.Now we are in a position to determine the instant C. We know from theexpanding phase that(B—A)(C—A)(E—A).The idea of the next testing phase is to repeat sending messages i and (i + 1), butin each round bring E closer to C until the time difference between two successivesendings of message (i + 1) is less than a predetermined margin. As a result, theinterval between C and E is less than this difference which is the error marginthat we are willing to tolerate. Note that all times in each round are measuredrelative to A.This procedure is formalized in the following algorithm. The function r isdefined as r(x2,xi) 1x2—xii (xi,x2 > 0). The parameters r1 and areinitialized with the values obtained in the expanding phase.Chapter 8: transition time testing 164Algorithm : determining transition completion time after the expandingphase has been completedInputs : 1) pr, — the preamblea of transition i;2) ps1r— the postambleb of transition (i + 1);3) r1+j — the interval between sending message i and message (i + 1)4) R— the smallest response time of message (i + 1);5) e — the predetermined error marginOutputs : t2— the service time of transition i;ProcedureI - , _1. se = r21 anu—2. send prj to set the protocol at the starting state of transition i;3. send message i and label the sending instant as A;4. send message i+1 at time D where r(D,A) =5. measure the response time of message i+1 and call it R+i;6. if (R÷1 R11) thenset =go to Step 2;elseccontinue Step 7;7. set T+i = Ti’+l +8. send pri to set the protocol at the starting state of transition i;9. send message i and label the sending instant as A;10. send message i+1 at time D where r(D, A) = T+i;11. measure the response time of message i+1 and call it R+i;12. if (R1 = R1) thenset =elseset = T+i;13. if (r(r1,)<= e) thenset t2 =stop;elsesend Pi+1 to set the protocol back at the idle state;go to Step 7.aThe preamble of a transition is a sequence of consecutive transitions starting fromthe idle state and leading to the start state of the transition.bThe postamble of a transition is a sequence of consecutive transitions bringing theprotocol from the end state of the transition back to the idle state.cNote that R+1 cannot be less than R because is the smallest responsetime obtained in the expanding phase.Chapter 8: transition time testing 165The first 6 steps of the algorithm try to find a lower bound on the servicetime. An upper bound on the service time has been obtained in the expandingphase. In each round from Steps 7 to 13, the difference between the lower boundand the upper bound is reduced by half to form the new upper bound. So thisalgorithm is actually a type of binary search. As a consequence, the distancebetween C and D can be made arbitrarily small. In this sense, the service timeof message i (i.e., time interval AC in Figure 8.4) can be determined accurately.This procedure can be automated and shall be referred to as the shrinking phasebecause the upper bound on the service time is gradually reduced in this phase.The shrinking phase implicitly assumes that the message sending intervals canbe made smaller than the minimum transition service time.The expanding phase and shrinking phase together constitute what we call thet-test.As shown above, the complete t-test needs to execute the same test subsequence a number of times. The number can be reduced if we are willing to accepta larger error in service time estimation. Moreover, if it is adequate to use theresponse time of a transition as an estimate of its service time in performanceanalysis, then only the expanding phase of the t-test is needed to make sure noqueue wait time occurs for the specific transition. The expanding phase of thet-test is much easier to achieve and in the best case it needs only two rounds.In the rest of the chapter, we assume only the expanding phase of the t-testis used in the transition time test whenever the response time of a transition canbe measured directly.Chapter 8: transition time testing 1668.3 TestabilityThe t-test requires at least two consecutive transitions. It assumes that the inputof the first transition is controllable and both the input and the output of thesecond transition are observable. However, not all transitions in an FSM haveboth observable input and output events. Transitions without any input areknown as spontaneous transitions [Sari84). We shall define a transition withoutany input (i.e., -/0) or a transition without any output (i.e., 1/-) as an invisibletransition. Conversely, a visible transition is defined as a transition in which bothits input and output are observable (i.e., I/O). A transition dealing with thetimeout event is a typical invisible transition because timeout is usually generatedinternally.Invisible transitions make performance measurement difficult. Their responsetimes cannot be obtained directly and thus these transitions cannot be used todetect the completion of previous transitions. Fortunately, sometimes this problem can be solved by combining an invisible transition with other transition(s).This will be discussed in detail later in this section.Figures 8.5 and 8.6 list all the possible situations of two consecutive transitions involving invisible transitions. Each of the cases is analyzed in the following:1. The simplest case is when both transitions are visible (Figure 8.5 (1)). Themeasured response time can be used to estimate the service time of thecorresponding transition. Furthermore, as explained in Section 8.2, theresponse time of the second transition can also be used to determine theservice time of the first transition accurately by the t-test.Chapter 8: transition time testing 167L0u00v002QU0Ou QQU U0Q4.QU040QQ40 QVO pFigure 8.5: Two consecutive transitions with at least one visible transitioni.QU wQ2.QU QQ3. ppQp40 p lb pFigure 8.6: Two consecutive transitions without any visible transition2. In Figure 8.5 (2), the second transition is invisible and its response timecannot be measured directly. Therefore, it cannot be used directly to determine the service time(s) of its preceding transition(s). However, if thefirst transition can be combined with other visible transitions following itas shown in path 2 of Figure 8.7 (1), then we have case 1 and the servicetime of the first transition can be accurately determined. Furthermore, thesecond transition can also be treated as a visible one by combining it witha visible transition that follows it (path 1 in Figure 8.7 (1)). Path 1 thenChapter 8: transition time testing 168becomes case (3) in Figure 8.5 and can be analyzed using the techniquedescribed below.3. The second transition in Figure 8.5 (3) is visible. T-test can be used todetermine the service time of the first transition (which is invisible) asdiscussed in Section 2.Alternatively, if the two transitions in Figure 6 (3) are treated as one transition, it is visible and its response time can be obtained directly. Supposethe response time is t and the response time of the second transition is t2.Therefore, the response time of the first transition, t1 can be obtained usingthe simple relation : t1 = t — t2. t1 can be used as a rough estimate of theservice time of the first transition.4. Figure 8.5 (4) can be handled in a way similar to that of Figure 8.5 (3).The second transition is invisible because it can be fired without any input.However, we can combine these two transitions and treat them as a singlevisible transition as discussed in case 3.5. The first transition of Figure 8.5 (5) is not useful and neither is the combination of the two transitions because it is still invisible. However, it maybe possible to calculate the service time of the first transition with the helpof the second visible transition and some simple computation as discussedlater in this section.6. In cases (1), (3) and (4) of Figure 8.6, like the case in Figure 8.5 (5), thetwo transitions are not very useful either individually or as a unit. Othertransitions in the FSM are needed to compute the service times of theseChapter 8: transition time testing 169two transitions (see below).7. The two transitions in Figure 8.6 (2) can be combined into one visible transition if necessary. However, the individual service time for each transitioncan only be obtained if at least one of them can be measured through othersubpaths.-2,‘o:d—v. .p11oppath I(I).path2 110o_y.•o pph I(2)Figure 8.7: Example of test subpaths for invisible transitionsAs we have seen, sometimes it is necessary to combine two or more consecutivetransitions in the FSM as one transition for use in the test. We shall refer to such atransition as a compound transition. A compound transition is visible if the inputof its first transition and the output of its last transition are both observable. Forexample, I/—,.. . , —/0,., is a visible compound transition.The response time of a transition is the response time of the associated incoming message which is the interval between the time when the incoming messageis sent and the time when the first outgoing message of the transition is seen. Atransition is defined as measurable if its response time can be measured. A visibleChapter 8: transition time testing 170(compound) transition is always measurable. Its service time can be estimatedby measuring its response time.We define a (compound) transition to be testable in transition time testingif its service time can be obtained by either direct or indirect measurement. Anexample of indirect measurement is the t-test. By this definition, a visible transition (either single or compound) is always testable. An invisible (compound)transition may become testable under certain circumstances as discussed earlier.It is reasonable to assume that in a communication protocol, there exists atleast one observable input event and one observable output event. Furthermore,since a correct FSM is always strongly connected, the following lemma is true.Lemma 8.1 An invisible transition can always be included either at the head orat the tail of a visible compound transition.Proof:An invisible (single) transition has the form 1/- or -/0. If the invisible transition is of the form 1/-, the visible compound transition is the transition pathstarting with 1/- and ending with the transition having an observable outputevent. If the invisible transition has the form -/0, the visible compound transition is the transition path that starts with an observable input event, and endingin-/0.To tackle invisible transitions, we present the following theorems.Theorem 8.2 An invisible transition is testable if it can be included as the heador tail of a testable compound transition and the rest of the compound transitionis testable.Proof: This follows directly from the definition of testable transition.Chapter 8: transition time testing 171Theorem 8.3 (1) An invisible transition 1/- is testable in an FSM if there is atleast a transition immediately following it which has the form of I’/O’ or I’/-, orwhich is a testable -/0’. (2) An invisible transition -/0 is testable if there is atleast a transition immediately before it which has the form of I’/O’ or -/0’, orwhich is a testable I’/-.Proof:(1) The testable (compound) transition succeeding 1/- may begin with a transition of the form I’/O’, I’,- or -/0’. If I’/O’ is the first transition in the testable(compound) transition, then we have case 3 of Figure 8.5 and the service time of1/- can be derived using the t-test. So 1/- becomes testable in this case.Otherwise, if I’/- follows 1/-, according to Lemma 8.1, I’,- can always form avisible compound transition with other transitions in the FSM and the compoundtransition is testable. So does 1/-. The service time of 1/- is the difference of theservice times of these two compound transitions. Therefore, 1/- is testable in thiscase.The last case is that a testable -/0’ follows 1/-. 1/- can form a visible compound transition with -/0’ and the compound transition is testable. The servicetime of 1/- is the service time of the compound transition minus that of -/0’. 1/-is also testable in this case.(2) Similar analysis can be applied to prove (2) of the theorem. 0In the next section, we present a method for selecting test sequences for transition time testing based on the above discussion of testability.Chapter 8: transition time testing 1728.4 Test Sequence GenerationThe objective of transition time testing is to obtain the service times of all thetransitions in the FSM of the protocol. The test data that are used to achievethis are called test sequences. Here a test sequence is defined as a sequence ofconsecutive transitions which takes the FSM from its beginning (usually idle)state back to the same state. A test subsequence is a segment of a test sequence,but not necessary starting from the beginning state or ending at the beginningstate.Since the service times of all the transitions in an FSM are primitive (i.e.,required) data for performance analysis, all the transitions should be covered inthe test sequences. Furthermore, the test sequences should be able to check thatthere is no queue wait time for the visible (compound) transitions so that.—* ti,as discussed before. For this reason, a test subsequence should include at leastone visible (compound) transition. As explained earlier, the visible (compound)transition can be used to estimate its own service time and/or to determine theservice time of its previous transition in the t-test.The framework for generating test subsequences for transition time testingconsists of two phases. In phase one, all the visible transitions in the FSM areselected to be tested and their service times obtained. In phase two, the othertransitions left (mostly invisible) are considered in the way presented in the previous section. This is discussed in detail below.The FSM of the protocol is considered as a directed graph, denoted as G,Chapter 8: transition time testing 173where the nodes stand for the states and the directed edges for the transitions.G is a strongly connected graph because, for any correct communication protocol(specified by an FSM), there should be at least one transition sequence leading toany state from the beginning state, and at least one transition sequence bringingthe protocol back to the beginning state.In the derivation of the test sequences, a subgraph of G is first constructed,denoted as It includes all the nodes and all the visible transitions of G(excluding the invisible transitions). The set $(O) initially contains all the invisibletransitions of the FSM. G° may not be a strongly connected graph any more asshown in Figure 8.8. However, all the edges in G° are visible and testable. Soeach transition in Q(O) is treated as a subsequence by itself.Phase two begins after the test subsequences for all the visible transitionshave been generated. Select any invisible transition from (0) and put it intoIf the selected invisible transition is of the form 1/-, check if there is anytransition in the current graph immediately after it. If not, put it back into S°and pick another transition. If the following transition is of the form I/O, thetest subsequence (1/-, I/O) is generated; otherwise, if the following transitionis of the form -/0, select the test subsequence (I/-,-/0). If the above cases are allfalse, the following transition must be of the form I/-. In this case, two visiblecompound transitions are generated, one starting with I/- and the other with(1/-, I/-). Note this is always possible since all transitions in G° are testable.The difference in service times of the two compound transitions gives an estimateof the service time of 1/-.Likewise, if the selected invisible transition is of the form -/0, check the graphto determine if there is any transition in the current graph immediately before it.Chapter 8: transition time testing 174() stateinvisible transitionG:visible transitionidleFigure 8.8: A sample FSM graph showing disconnected subgraphs after deletinginvisible transitionsIf not, put it back into S° and pick another one. If the transition preceding -/0is of the form 11/01, the test subsequence (I /0k, -/0) is generated; otherwise,if the preceding transition is of the form 1/-, the compound transition (1/-, -/0)is selected as a test subsequence. If both cases are false, the preceding transitionmust be of the form-/0k. In this case, two visible compound transitions aregenerated, one ending with-/01 and the other with an (-/01, -/0).If the newly selected invisible transition becomes testable, it remains inand the graph becomes G’ with one more edge while S° becomes S’ with onefewer transition.UChapter 8: transition time testing 175This process is repeated until the set of invisible transitions is empty or noneof the invisible transitions in the set can be made testable using this procedure.Finally, we reconsider all the transitions remaining in 8(n) First, for eachtransition of the form 1/-, check in G if there is another transition of the form‘k/ following it, which may still be in 8(n). If so, this transition can becometestable according to Theorem 8.3. Two visible compound transitions are thengenerated, one starting with Ik/— and the other with (1/—, Ik/—). Record thesetwo subsequences for the transition, remove I,- from and put it in Similarly, each invisible transition of the form -/0 in S’ is checked. The procedureends when all the transitions in 8(n) have been checked or the set is empty.If any invisible transition has become testable in this phase, Phase two of theprocedure is repeated until no remaining transitions can be made testable.Note that it is possible that some transitions in the FSM are untestable.Figure 8.9 shows an example FSM with two untestable transitions (1/- and -/0).How to deal with these transitions is left as future work. A simple method isto examine the source codes of these transactions to arrive at an estimate of theexecution times.Figure 8.9: A sample FSM with untestable transitionsEach test subsequence derived above is a visible compound transition. Toform the test sequences, a preamble which is a transition sequence starting fromChapter 8: transition time testing 176the beginning state of the FSM and ending at the starting state of the compoundtransition, and a postamble which is a transition sequence starting from theending state of the compound transition and ending at the beginning state mustbe added.Since a test subsequence may have to be tested many times, the shortestpreamble and postamble of an FSM should be used to reduce the testing cost.An algorithm to find the shortest path between two vertices in a directed graphcan be found in [RoWr88j.An exampleTo illustrate, we use an abstract FSM shown in Figure 8.10.Figure 8.10; An example FSM to show test subsequence generationSuppose that Figure 8.10 is graph G. The initial subgraph G° of G in the testsequence generation procedure is given in Figure 8.11 (a). The initial invisibletransition set is S° = {—/03, —/04, 15/—, 16/—}. Two test subsequences aregenerated from G° : 11/01 and 12/02.Next, the first invisible transition in -/03, is selected and put inIt can be made testable using the subsequence 12/02, -/03. Q(1) is given inChapter 8: transition time testing 177(0)6__________12102 C)C)(a)(I)11101 (21022(b)(c)Figure 8.11: Test subsequence generation procedure for the FSM in Figure 8.10Figure 8.11 (b) and S’ = {—/04, 15/—, 16/—}.Then, -/04 is selected because -/03 is now testable. The test subsequencefor -/04 is 12/02, -/03, -/04. G’ is given in Figure 8.11 (c) and S2 ={15/—, 16/—}.15/- can also become testable using i-test with the test subsequence (15/-,11/01). As a result, becomes {16/—}.Finally, (16/-, -/04) is used to derive the service time of 16/-.In summary, the test subsequences derived are(c) (d)Chapter 8: transition time testing 17811/01;12/02;12/02, —/03;12/02, —/03, —/04;15/—, 11/01;16/—, —/04;8.5 Experimental ResultsA tester which implements t-test was built to validate the methodology. Thistester uses the architecture shown in Figure 8.12.This architecture is a realization of the abstract one introduced in Figure 8.1.It consists of an JUT module and a tester module. The JUT and the testermay reside on two different computers. The clocks of the two computers are(1)(2)(3)(4)(5)(6)send messagesFigure 8.12: A testing architecture of the t-testChapter 8: transition time testing 179not required to be completely synchronized as long as their time differences arekept reasonably constant. This is because t-test uses the sending interval of twoconsecutive messages to approximate the service time of the first message. Thesending interval is computed using the clock of the tester. Nevertheless, if theclock of the JUT is behind the clock of the tester, then the response time ofa message which involves the two clocks may be close or equal to zero. Thissituation can be avoided easily by setting the clock of the JUT a little bit aheadof the clock of the tester.When the lower or upper service interfaces of the JUT are not directly accessible, then the JUT implementor or the test evaluator must add some codes shownin the shadow boxes of Figure 8.12 outside the JUT to record the times of theoutput data or service primitives. This is similar to the ferry clip testing method[Chan89, Chan93].The tester sends messages to the JUT to trigger transitions. This is implemented using UNIX’s datagram sockets (UDP). The timestamps of each of theoutgoing messages from the JUT are recorded in a log file. The tester also recordedin its memory the timestamps of each message it sends to the JUT. At the end ofeach round of test, the tester reads the log file and recomputes the message sending intervals for the next round according to the algorithms presented in Section8.2.Generally speaking, the IUT can be any protocol implementation. We implemented a simple protocol whose FSM is illustrated in Figure 8.13. The servicetime of each transition in this FSM consists of two parts: the first part is beforethe output event (if any) of the transition; the other is after. Both times aregenerated randomly but only once for an JUT. Therefore, the output event of aChapter 8: transition time testing 180transition is somewhere in the middle of the service of a transition. This is doneso as to make the response time of a message an inaccurate estimation of theservice time of the associated transition.L : Lower Layer PCOU : Upper Layer PCOFigure 8.13: The FSM of an abstract protocolWe used this implementation as an IUT, treated it as a black box and conducted the t-test.First, we derived a test case using the method introduced in Section 8.4. Thistest case is (L:I1/L:O1, U:12/-, L:13/U:03, L:I1/L:01). By the definition of ttest, the service times of all three transitions can be obtained only with this testcase.Secondly, we ran the t-test and got the results which are listed in Table 8.1. Foreach row in the table, the first column contains the transition identifier labelledwith their input and output events. The second column is the service times of thetransitions which were randomly generated. The third column is the measuredL:I1/L:O1U:121-Chapter 8: transition time testing 181response times. The forth column is the result of the shrinking phase of the t-test.Transition Service Timea Measured Response Timeb T-test Resultc11/01 136378 19713312/- 839081 N/As 85685313/03 1208362 1090068 1211972aThe service time of each transition is generated randomly in two parts: one is before theoutput of outgoing messages; the other is after the output.bThe response time is the difference between the message sending time and the output seeingtime.CThe error tolerance is 5%.dM1 times are in microseconds.eNot applicable because this transition has no output.Table 8.1: Simulation and Testing ResultsThe results show that the estimations of the transition service times (Column4) using t-test are much closer to the actual service times (Column 2) than themeasured response times (Column 3). Accurate results are obtained even forsome invisible transitions.We also apply the t-test to a real protocol implementation which contains asubset of LAPB. The test results are presented in Apprendix G.8.6 SummaryA number of papers have been published on performance analysis of communication protocols directly from their formal descriptions using analytic techniques orsimulation (see for example, [Krit87, BoVa88, LiLi88, GuRu89, AFF9O, FVV91,KrWh93, ZhCh93]). Most of the work is based on FSMs and with the assumptionthat the transition service times are somehow known in advance.Chapter 8: transition time testing 182In this chapter, we have shown that it is possible to obtain an accurate estimate of the service time of a transition in an FSM using the t-test, even thoughthe protocol implementation is given as a black box. The t-test uses the sameenvironment as an ISO conformance test and can be performed right after conformance testing. A t-test consists of two phases: expanding phase and shrinkingphase. In the expanding phase, the t-test needs to execute the same transitionsubsequence more than once in order to make sure the sending interval is longenough for the previous transitions to finish processing. Then, in shrinking phase,the t-test uses binary search technique to determine rapidly the finishing point ofthe service time of a transition. The key to the t-test is that a tester must havecontrol over both the test sequences and the sending intervals of the messages.The testability within the scope of transition time testing has also been discussed. Although some transitions of an FSM are invisible, it may be possibleto combine them with other transitions to form testable compound transitionswhich can be used to determine the service times of their own as well as other(compound) transitions.Based on the discussion of testability, a method of test subsequence generation(TSG) from a given FSM is proposed. The procedure of the TSG consists of twoiterative phases. The best case is when all the transitions of the FSM are visible.In this case, only Phase one of the generation procedure needs to be executedand its time complexity is 0(n), where n is the number of the transitions.Each round of Phase two will take 0(nm + m2) time, where m is the numberof invisible transitions remaining in the set. Phase two will have to be repeatedif any invisible transition becomes visible in the round. Therefore, the worstcase situation occurs when only one invisible transition becomes visible in everyChapter 8: transition time testing 183round so that Phase two has to be repeated the maximum number of times. Sothe worst case time complexity of the TSG is O(nm2+m3)where m is the numberof invisible transitions.‘When the service times of all the transitions in an FSM are determined,the performance of the protocol specified by the FSM can be computed using the PEFSM method presented in Chapter 4, 5 or 6 of this thesis, queueing analysis [ZhCh93J, reachability analysis [LiLi88, BaBu9l], or other methods[Krit87, KrWh93J.Chapter 9Conclusions and Future Work9.1 ConclusionFormal description techniques (FDTs) have found various applications in softwareengineering, including specification, semi-automatic implementation, test casegeneration, verification and performance prediction. The main objective of thisthesis is to develop models, algorithms and tools which further enhance the powerof existing FDTs in performance analysis.Each FDT has at least one embedded formal model (e.g. finite state machine(FSM)). The formal model can be used to characterize the properties of a communication protocol such as liveness, state reachability, message service order,and queueing and service disciplines. These properties are useful in analysis,design, simulation, performance evaluation and testing of the protocol. Compared to conformance testing of communication protocols, performance testingand evaluation based on FDTs are relatively under-developed; not much has been184Chapter 9: conclusions and future work 185published in this field.In this thesis, we have proposed a new performance model called PerformanceExtended Finite State Machine (PEFSM) and the solution techniques based onPEFSMs. This framework may be used to evaluate the performance of communication protocols in the design stage (based on a formal specification alone), oron the actual implementations. In the latter case, it is still necessary to have theformal specifications of the implementations.9.1.1 ContributionsThe thesis has addressed three aspects of performance evaluation:• performance prediction,• performance improvement, and• performance measurement.The major contributions of this thesis are summarized below:• formulation of a new performance model called PEFSM and a frameworkto evaluate performance based on PEFSMs;• proposal of a methodology to identify performance bottlenecks based onPEFSMs;• presentation of a testing methodology and architecture to obtain the transition service times when the protocol implementation is given as a blackbox;Chapter 9: conclusions and future work 186• discovery of a queueing property with M/G/1 queueing systems with multiple job classes and a similar property with a class of PEFSMs calledAsPEFSM-os;• survey of research work and tools on performance evaluation related toFDTs.Unlike the previous performance models based on FSMs, a PEFSM integratesan incoming message arrival model with an FSM. The distinction of incomingmessage arrival models based on synchronous and asynchronous characteristicsallows us to classify the PEFSMs into three categories: synchronous PEFSMs(SyPEFSM), asynchronous PEFSMs (AsPEFSMs) and hybrid PEFSMs (HyPEFSMs). Furthermore, queueing models are integrated with AsPEFSMs and HyPEFSMs to obtain the queue wait times of incoming messages. The solutiontechniques of performance evaluation for the HyPEFSMs in this thesis are basedon the techniques for the SyPEFSMs and the AsPEFSMs.The issue of which type of PEFSM should be used to analyze the performanceof a protocol that is specified by an FSM depends on many factors. As we haveseen in the thesis, some of the factors are related to the assumptions of the underlying system on which the protocol runs. In certain circumstances, a complexmodel such as a HyPEFSM can be transformed into a simpler model such asa SyPEFSM or an AsPEFSM for analysis. This can be achieved by obtainingthe values of some performance parameters such as transition probabilities andtransition wait times through simulation. This is an approach which combines analytic methods with simulation methods in performance analysis. This approachcan help the performance evaluator to achieve a reasonable trade-off between theChapter 9: conclusions and future work 187accuracy of performance evaluation and the computation complexity.In Chapter 7, we show that PEFSMs can be used not only to model andpredict performance in a more realistic manner but also to define and identifysoftware bottlenecks in terms of the transition that has the greatest impact onthroughput and mean queue wait time. Properly assigning weights to transitionsin a PEFSM with respect to a specific performance metric can help to identify andimprove the performance of this metric more effectively. Two different methodsto compute weights are presented in Chapter 7 with respect to the throughput ofa specific class of outgoing messages and the mean queue wait time of a specificclass of incoming messages.The transition service times are important parameters for many performancemodels. Previous work has assumed these times are known a priori. In Chapter8, we show how the transition service times can be measured/estimated from aprotocol implementation when it is given as a black box. A testing method calledt-test is proposed to obtain the transition service times of invisible transition.Each round of t-test involves at least two (compound) transitions. The responsetime of the second (compound) transition is used to identify the exact finishingtime of the first (compound) transition so that the service time of the first (compound) transition can be accurately computed. This makes t-test a very effectivemeans to obtaining the service time of an invisible transition.Simulations and measurement experiments were conducted to validate themethodologies proposed. The results showed the proposed models and methodologies are reasonably accurate.Chapter 9: conclusions and future work 188We have also observed and proved a queueing property for queueing systemswith multiple job classes. That is, for an M/G/1 queueing system with multiplejob classes, the mean queue wait times of different class jobs are the same. Wefurther prove that in an AsPEFSM, the mean queue wait times of firable messagesof the same state for different classes of jobs are also the same. With the latterproperty, the different classes of firable messages of the same state can be treatedas one class in the computation of mean queue wait times for AsPEFSMs andHyPEFSMs. Both of these properties are proved by applying the well-knownqueueing property— Poisson arrivals seeing time average (PASTA).9.1.2 Applicability of PEFSM to EFSMIn addition to FSM, EFSM is often used for modelling communication protocols.A conventional EFSM is an FSM extended with variables which are used tocontrol various aspects of the EFSM.We shall use the formal specification language Estelle [Chari89} as a casestudy. Estelle is designed to specify EFSMs for communication systems.A variable in the EFSM of an Estelle specification may appear within a transition or in the conditional clause of a transition. In the first case, the variablemay affect the transition service time or the generation of outgoing messages. Anexample is a variable in a while or if ... then ... statement within a transition. Ifthe variable in a transition affects only the service time, the performance modelPEFSM is still applicable. With the variable, the service time distribution ofthe transition may no longer be constant. Since PEFSM does not impose anyconstraint on the distributions of transition service times, performance metricsChapter 9: conclusions and future work 189can be derived as usual based on PEFSMs. Even if the influence of a variable ona transition affects the generation of outgoing messages, PEFSM is still applicable. Suppose a transition may produce one of two types of outgoing messages,say 0 and 02, depending on the value of a variable. We can define the class ofoutgoing messages generated by this transition to consist of either 0 or 02. Therest of the performance evaluation remains the same. However, we note that thethroughput computed using Equation (4.2) is concerned with the overall outgoingmessages (0 and 02) with no distinction between them.In the second case, the variable is contained in the condition of a transitionwhich determines state changes in an EFSM. An example would be a variablein a when or provided statement of an Estelle specification. We can define theincoming message class of the transition to be both the incoming message typeand the variable with the values (or range) which satisfy the condition of thetransition. In this way, PEFSM can still be used to model and evaluate theperformance of the system based on the EFSM.Some EFSMs are non-deterministic, i.e., a transition with exactly the sameinput may end up in different states in the EFSM at different times. We canaddress this in the conventional manner [LiLi88, BoVa88j: additional transitionprobabilities are used to model these non-deterministic choices. Let, for instance,(l)= Pr{6(i,I) =ii};(2)= Pr{6(i, I) = i2};(n)= Pr{6(i, I)= j,};Chapter 9: conclusions and future work 190and=where i,j1,j2•.,j, EQ.(k) is directly equivalent to the transition probability if I is the only class offirable messages of state i. Otherwise, p is used as the conditional probabilityin the computation to obtain the probability of the transition from state i to stateJk•9.2 Future WorkThe thesis has established a foundation for performance evaluation based onPEFSMs. The work creates a new research area which can be further developedin many directions.9.2.1 System-wise performance evaluationAn FDT specification of a communication protocol in a formal specification language such as Estelle could consist of more than one module (see for exampleFigure 9.1). As a result, two levels of performance analysis are needed:• single module (module-wise)• the entire system (system-wise)In module-wise analyses, only the module of interest is investigated. All information regarding the other modules is given as external factors, such as workloadChapter 9: conclusions and future work 191____XAModule AXB____ModuleBFigure 9.1: Two modules in system-wise analysisparameters. In this sense, the work reported in this thesis belongs to this category. To evaluate network performance, this level of analysis may not be enoughsince multiple modules should be considered at the same time.System-wise analyses take all the modules explicitly into consideration in performance evaluation. To use our performance evaluation method directly, onemay combine the FSMs in all the modules into one large FSM. Unfortunately,this combination usually increases the number of states in the resultant FSMexponentially. The computational complexity also increases tremendously as aconsequence.An alternative is the iteration method described below. Take the examplegiven in Figure 9.1 for a closed queueing model consisting of only two modules Aand B.It is obvious that= fl(XB)XA = g1G\A)= f2(XA)XB=g2(AB)Chapter 9: conclusions and future work 192where XA and XB are throughputs from modules A and B respectively and‘\Aand .AB are the arrival rates for modules A and B respectively.These parameters are dependent on each other. By substitution, for example,we have:where F= f o g2 o o g1 and fi °f2(x) =f1(f2x)).Some parameters are given initial values and the equations solved iteratively.Iterations in this way would refine the values of some performance elements. Theprocess stops when the change in values is less than some predefined limit. Fixedpoint theory [Dugu82] could also be applied to check for the existence of solutionsand to find the values.The applications of system-wise analysis could range from network performance evaluation to network management.9.2.2 Queueing theoryWe have studied only a few message arrival patterns in AsPEFSMs and HyPEFSMs. To increase the applicability of PEFSM, more arrival models need to beanalyzed. For example, the queueing systems in AsPEFSMs and HyPEFSMsmay have modulated or correlated inputs. Queueing models with these types ofworkload are still being researched although some results have been publishedwhich are mostly related to asynchronous transfer mode (ATM) networks. It isexpected that for a general arrival model, the performance computation wouldbe much more complex. These are interesting and challenging research topics.The distributions of outgoing messages from a single module are important forChapter 9: conclusions and future work 193those modules which take the messages as inputs. Therefore, another interestingtopic is how to derive these distributions. Our work has focussed on certain time-averaged statistical performance metrics such as mean throughputs, mean queuewait times and mean queue length. In particular, the distributions or at leasthigher moments of queue length, queue wait time, busy period and idle perioddeserve further study.9.2.3 New topics in stochastic processesThe stochastic processes of PEFSMs are different from those of traditional EFSMs. The PEFSMs allow waiting for incoming messages. Unlike the conventionalsemi-Markov processes where the single-step transition probabilities are given, thetransition probabilities of PEFSMs, with the exception of synchronous PEFSMs,are computed from the given workload descriptions. The computations involvesolving matrix equations which may be very complex and sometimes insoluble.Therefore, further approximation methods are needed to deal with this problem.9.2.4 On-line performance tuningBottleneck definition and identification provide insight on improving system performance. This forms the basis of on-line or real-time performance tuning. However, more studies are needed on how to remove a bottleneck efficiently. Forexample, the cost in reducing transition times has not been taken into accountin our bottleneck definition and identification methodology.In summary, the research reported in this thesis has identified and laid theground work for several new research directions, some of which have practicalChapter 9: conclusions and future work 194significance to industry.Bibliography[AFF9O] Guido Albertengo and Silvio Forno and Andrea Fumagalli.TOP/PDT: A Toolkit for the Development of CommunicationProtocols. IEEE Journal on Selected Areas in Communications,8(9):1763—1770, Sept. 1990.[AbKa9lJ Bandula W. Abeysundara and Ahmed E. Kamal. High-SpeedLocal Area Networks and Their Performance: A Survey. ACMComputing Surveys, 23(2), June 1991.[Allen9O} Arnold 0. Allen. Probability, Statistics, and Queueing Theorywith Computer Science Applications. Academic Press, Inc., 2ndedition, 1990.[AtMa93} Tulin Atmaca and Jon W. Mark. Voice and Data Integration at anATM Multiplexer. In H. Perros, G. Pujolle and Y. Takahashi, editor, Modelling and Performance Evaluation of A TM Technology(IFIP Trans. C-15), pages 173—182. Elsevier Science PublishersB.V. (North-Holland), 1993.[At1e89] Michael Atlevi. SDT— a real-time CASE tool for the CCITTspecification language SDL. In Proc. of 2nd Intl. Conf. on FormalDescription Techniques (IFIP FORTE’89), pages 49—53, Vancouver, Canada, 1989.[Azema89] P. Azema and J. C. Lloret, G. Papapanagiotakis and F. Vernadat. Estelle Validation and PROLOG Interpreted Petri Nets. InProc. of 2nd Intl. Conf. on Formal Description Techniques, (IFIPFORTE’89), Vancouver, Canada, 1989.195BIBLIOGRAPHY 196[BaBu9lj Falko Bause and Peter Buchholz. Protocol analysis using a timedversion of SDL. In Formal Description Techniques, III (IFIPFORTE’90), pages 239—254. Elsevier Science Publishers B. V.(North-Holland), 1991.[Barg86j N. Barghouti, N. Nounou and Y. Yemini. An integrated protocoldevelopment environment. In B. Sarikaya and C. v. Bochmann,editor, Proc. 6th Intl. Workshop Protocol Specification, Testing,Verification, pages 63—69, Montreal, P.Q., Canada, 1986. North-Holland.[Bart69] KA. Bartlett and R.A. Scantlebury and P.T. Wilkinson. Complex transmission over half-duplex links. Commun. Ass. Comput.Mach., 12:260—, May 1969.[BeDi9l] Bernard Berthomieu and Michel Diaz. Modeling and verificationof Time Dependent Systems Using Time Petri Nets. IEEE Trans.on Software Engineering, 17(3):259—273, March 1991.[Bei188j H. Beilner, J. Mater and N. Weissenberg. Towards a performancemodelling environment: News on HIT. In Proc. .4th mt. Conf.- Modelling Techniques and Tools for Computer Performance Evaluation, Palma, Spain., 1988. Plenum.[Berth83j B. Berthomieu and M. Menasche. An Enumerative Approach forAnalyzing Time Petri Net. In Information Processing 83, pages41—46, New York, 1983. North-Holland.[BoVa88J G.v. Bochmann and J. Vaucher. Adding performance aspects tospecification languages. In IFIP Symposium on Protocol Specification, Testing and Verification VIII, pages 19—31, Atlantic City,July 1988. Elsevier Science Publishers B. V. (North-Holland).[BoWi8Oj Taylor L. Booth and Cheryl A. Wiecek. Performance AbstractData Types as a Tool in Software Performance Analysis and Design. IEEE Trans. on Software Engineering, SE-6(2):138—151,March 1980.[BrMa86] G. Burno and G. Marchetto. Process-translatable Petri nets forthe rapid prototyping of process control systems. IEEE Trans.on Software Engineering, SE-12:346—357, Feb. 1986.BIBLIOGRAPHY 197[Budk92] S. Budkowski. Estelle development toolset (EDT). ComputerNetworks and ISDN Systems, 25(1):63—82, Aug. 1992.[Chan89] S.T. Chanson and B. Lee, N. Parakh and H. Zeng. Design andImplementation of a Ferry Clip based Test System. In Proc. of9th Intl. Symposium on Protocol Specification, Testing and Verification, pages 303—314, June 1989.[Chan93] Samuel T. Chanson, Hendra Dany, M.C. Kim, Qin Li, Son T.Vuong, Sijian Zhang, Limin Zhou and Jinsong Zhu. The UBCProtocol Testing Environment. In Proc. of 6th InternationalWorkshop on Protocol Testing Systems (IFIP), Pau, France, Sept.1993.[Chan93a] S.T. Chanson and A.A.F. Loureiro and S.T. Vuong. FDT Toolsfor Protocol Development. Computer Networks and ISDN Systems, Feb. 1993.[Chari89j V. Chari, J.F. Lenotre and E. Mariani. The Estelle translator. InThe Formal Description Technique Estelle, pages 325—35 1. NorthHolland, Amersterdam, 1989.[Chari89b] V. Chari and J. F. Lenotre, L. Lumbroso and E. Mariani. AnEstelle simulator/debugger tool (EDB). In M. Diaz, et al., editor, The Formal Description Technique Estelle- Results of theESPRIT/SEDOS Project, pages 381—396. North-Holland, Amsterdam, The Netherlands, 1989.[Choi85] Y. Choi. Formal Techniques for Specification, Verification, andConstruction of Communication Protocols. IEEE Communications Magazine, 23(10), Oct. 1985.[Clark85} David D. Clark. The Structuring of Systems Using UPCALLS.Communications of A CM, Dec. 1985.[Clark89J D.D. Clark and V. Jacobson, J. Romkey and H. Salwen. AnAnalysis of TCP Processing Overhead. IEEE CommunicationMagazine, June 1989.BIBLIOGRAPHY 198[Dan8O] A.S. Danthine. Protocol representation with finite-state models. IEEE Trans. on Communications, COM-28(4):632—643, April1980.[DeBu87] P. Dembinski and S. Budkowski. Simulating Estelle SpecificationsWith Time Parameters. In Proc. of 7th IFIP WG6. 1 Conferenceon Protocol Specification, Testing, and Verification. Elsevier Science Publishers B. V. (North-Holland), 1987.[DeBu89] P. Dembinski and S. Budkowski. Specification Language Estelle.In The Formal Description Technique Estelle. Elsevier SciencePublishers B. V. (North-Holland), 1989.[DiDe9Oj W. Ding and P. Decker. Waiting time distribution of a discreteSSMP/G/1 queue and its implications in ATM systems. In 7thITC Specialist Seminar, Morristown, USA, Oct. 1990.[DiMa64j B. Dimsdale and H.M. Markowitz. A Description of the SIMSCRIPT Language. IBM Systems Journal, 3(1):57—67, 1964.[Diaz82j Michel Diaz. Modelling and analysis of communication and cooperation protocol using Petri Net based models. In Protocol Specification, Testing, and Verification, IFIP, pages 465—510. ElsevierScience Publishers B. V. (North-Holland), 1982.[Diaz82-1] Michel Diaz. Modeling and Analysis of Protocols using Petri Nets.Computer Networks, pages 419—441, June 1982.[Ding9lj W. Ding. A unified correlated input process model for telecommunication networks. Teletraffic and Datatraffic in a Period ofChange, ITC-13:539—544, June 1991.[Doer9Oj Willibald Doeringer and Doug Dykeman, et al. A Survey of LightWeight Transport Protocols for High-Speed Networks. Communications/Computer Science 70152, IBM RZ, May 1990.[Drira95] Khalil Drira and Youcef Atamna and Guy Juanole. Quantifiedreduced views of state graphs using Markovian and timed observational equivalence, submitted to the International Conf. ofProtocol Specification, Testing and Verification (1995).BIBLIOGRAPHY 199[DsTa93j Jewgeni H. Dshalalow and Lotfi Tadj. A queueing system withrandom server capacity and multiple control. Queueing Systems,14(14):369—384, 1993.[DuguS2] James Dugundji. Fixed Point Theory. Warszawa: Polish Scientific Publishers, 1982.[FVV91] D. Fernandez and E. Vazquez and J. Vinyes. Jo: An EstelleSimulator for Performance Evaluation. In Proc. of 4th Intl. Confon Formal Description Techniques (IFIP FORTE’91), pages 52—68, 1991.[Ferr78] Domenico Ferrari. Computer Systems Performance Evaluation.Prentice-Hall Inc., New Jersey, 1978.[Fish94] Paul A. Fishwick. Simulation Model Design and Execution: Building Digital Worlds. Prentice Hall, 1994.[Giar89] D. Giarrizzo and M. Kaiserswerth, T. Wicki and R.C. Williamson.High-Speed Parallel Protocol Implementation. In Protocols forHigh-Speed Networks, IFIP. Elsevier Science Publishers B.V.(North-Holland), 1989.[GrDu87] Annie Gravey and Alain Dupuis. Performance Evaluation of TwoMutual Exclusion Distributed Protocols via Markovian Modeling.In B. Sarikaya and G.V. Bochmann, editors, Protocol Specification, Testing and Verification VI (IFIP), pages 335—346. ElsevierScience Publishers B. V. (North-Holland), 1987.[GrHa85J Donald Gross and Carl M. Harris. Fundamentals of QueueingTheory. John Wiley & Sons, New York, 1985.[Groo9lJ Jan Friso Groote. Specification and Verification of Real TimeSystems in ACP. Published in Computer Notes (?).[GuRuS9] Jan Gustafsson and Harry Rudin. Including a Queue in a Formal Description Driven Protocol Performance Analysis. In Proc.of 9th IFIP WG6. 1 Intnl. Symp. on Protocol Specification, Testing and Verfication, Enschede, The Netherlands, 1988. ElsevierScience Publishers B.V. (North-Holland).BIBLIOGRAPHY 200[HaPa93j Peter G. Harrison and Naresh M. Patel. Performance Modelling ofCommunication Networks and Computer Architectures. Addison-Wesley Publishing Company, 1993.[Hale9O] Roger Hale. Using Temporal Logic for Prototyping: The Designof a Lift Controller. In H.S.M. Zedan, editor, Real- Time Systems, Theory and Appliactioris, pages 81—118. Elsevier SciencePublisher B.V. (North-Holland), 1990.[Heck9l] E. Heck and D. Hogrefe and B. Muller-Clostermann. HierarchicalPerformance Evaluation Based on Formally Specified Communication Protocols. IEEE Trans. on Computers, 40(4):500—513,April 1991.[Hehm89J D.B. Hehmann and M.G. Salmony and H.J.Stuttgen. High-SpeedrI1.ansport Systems For Multi-media Applications. In Protocolsfor High-Speed Networks, IFIP. Elsevier Science Publishers B.V.(North-Holland), 1989.[Herr93] Christoph Herrmann. Analysis of the Discrete-time SMP/D/1/sFinite Buffer Queue with Applications in ATM. In Proc. of IEEEINFOCOM ‘98, pages 160—167, 1993.[H0U179J John E. Hopcroft and Jeffrey D. Uliman. Introduction to Automata Theory, Languages and Computation. Addison-WesleyPublishing Company, 1979.[Hoar78] C.A.R. Hoare. Communicating Sequential Processes. Communications of ACM, 21, 1978.[Hoar85} Charles A. R. Hoare. Communicating Sequential Processes.Prentice-Hall International, 1985.[Ho1187J Mark A. Holliday and Mary K. Vernon. A generalized timed Petrinet model for performance analysis. IEEE Trans. on SoftwareEngineering, SE-13( 12): 1297—1310, Dec. 1987.[Howa7l} Ronald A. Howard. Dynamic Probabilistic Systems: Vol. 1:Markov Models; Vol. : SemiMarkov and Decision Processes.John Wiley & Sons, Inc., 1971.BIBLIOGRAPHY 201[HsWa94j Ivy Hsu and Jean Walrand. Design and Control of ATM Networks: A Tutorial. In Tutorial Notes of The 14th Intl. IFIP Symposium on Protocol Specification, Testing and Verification, 1994.[1S025761 ISO TC97/SC16 N2576. Formal Specification of Transport Protocol in Estelle. Iso, 1986.[1S07776j ISO/TC 97, Information processing systems. Information Processing Systems— Data communication— High-level Data LinkControl Procedures — Description of the X..25 LAPB-compatibleDTE Data Link Procedures. ISO 7776 - 1986. ISO, 1st edition,Dec. 1986.[1508807] Iso TC 97/SC 21. Information Processing Systems— Open Systems Interconnection— LOTOS— A Formal Description Technique Based on The Temporal Ordering of Observational Behaviour. ISO 8807. Interational Organization for Standardization,1989.[1S09074] ISO TC 97/SC 21. Information Processing Systems— Open Systems Interconnection— Estelle (Formal Description TechniqueBased on an Extended State Transition Model. ISO 9074. Interational Organization for Standardization, 1989.[ISO9646a] ISO/IEC JTC 1/SC 21 N. Information Technology- Open Systems Interconnection- Conformance Testing Methodology andFramework- Part 1: General Concepts. ISO/IEC 9646-1. ISO,version 7.12 edition, March 1991.[Jain9l] Pradeep Jam and Simon S. Lam. Specificaiton of Real-TimeBroadcast Networks. IEEE Trans. on Computers, 40(4):404—422,April 1991.[Kesi93] G. Kesidis, J. Wairand, C. S. Chang. Effective Bandwidths forMulticlass Markov Fluids and other ATM Sources. IEEE/A CMTrans. on Networking, 1993.[Kimb89] Roy E. Kimbrell, Linda Correll, Robert Bass. The Qsim Simulation Toolkit. BYTE, pages 259—266, July 1989.BIBLIOGRAPHY 202[Klein75] L. Kleinrock. Queueing Systems: Vol. 1, Theory and Vol. 2,Computer Applications. John Wiley and Sons, 1975.[KrWh89J P. Kritzinger and G. Wheeler. A protocol engineering workstation. In Proc. of 2nd Intl. Conf. Formal Description Techniques(FORTE’89), Vancouver, Canada, 1989.[KrWh93] Pieter S. Kritzinger and Graham Wheeler. Semi-markoviananalysis of protocol performance. In P. Wolper A. Danthine,G. Leduc, editor, Protocol Specification, Testing and Verification,XIII, pages C3:1—14. IFIP, 1993.[Krit86J P. S. Kritzinger. A performance model of the OSI communicationarchitecture. IEEE Trans. on Communications, COM—43:554—563, 1986.[Krit87] Pieter S. Kritzinger. Protocol performance using image protocols.In H. Rudin and Cohn H. West, editors, IFIP Symposium onProtocol Specification, Testing and Verification VII, Zurich, May1987. Elsevier Science Publishers B. V. (North-Holland).[KuGo86] J.F. Kurose and K.J. Gordon. A graphics-oriented modeler’sworkstation environment for the RESearch Queueing package(RESQ). In Proc. FJCC’86, 1986.[Lamp9l} Leslie Lamport. The Temporal Logic of Actions. Technical Report 79, Digital Systems Research Center, 130 Lytton Avenue,Palo Alto, California 94301, Dec. 1991.[Lazo84] E.D. Lazowska and J. Zahorjan, G.S. Graham and K.C. Sevcik.Quantitative System Performance — Computer System AnalysisUsing Queueing Network Models. Prentice-Hall, Inc., EnglewoodCliffs, New Jersey, 1984.[Leung88] Clement H.C. Leung. Quantitative analysis of computer systems.Chichester; New York Wiley, 1988.[LiLi88] Fuchun Joseph Lin and Ming T. Liu. An Integrated Approach ToVerification And Performance Analysis of Communication Protocols. In IFIP Symposium on Protocol Specification, Testing andBIBLIOGRAPHY 203Verification VIII, pages 125—140, Atlantic City, July 1988. Elsevier Science Publishers B. V. (North-Holland).[Litt6lj John D. C. Little. A Proof For The Queuing Formula: L=A W.Operations Research, 9:383—387, 1961.[Lock84] K.G. Lockyer. Critical Path Analysis and Other Project NetworkTechniques. Pitman Publishing, 1984.[LyAt92] Nancy A. Lynch and Hagit Attiya. Using mappings to provetiming properties. Distributed Computing, 6:121—139, 1992.[MaPn92] Z. Manna and A. Pnueli. The Temporal Logic of Reactive andConcurrent Systems. Springer-Verlag, 1992.[Mars9O] M. A. Marsan and G. Balbo, G. Bruno and F. Neri. TOPNET:A Tool for the Visual Simulation of Communication Networks.IEEE Journal on Selected Areas in Communications, 8(9):1735—1747, Dec. 1990.[Mars94] Marco Ajmone Marsan, Andrea Bianco, Luigi Ciminiera, Riccardo Sisto, Adriano Valenzano. A LOTOS Extension for thePerformance Analysis of Distributed Systems. IEEE/ACM Trans.on Networking, 2(2):151—165, April 1994.[MeMo85] B. Melamed and R.J.T. Morris. Visual simulation: The performance analysis workstation. IEEE Computer, 18(8):87—94, Aug.1985.[MeWh9Oj Benjamin Melamed and Ward Whitt. On Arrivals That See TimeAverages. Operations Research, 38(1): 156—172, 1990.[Me1a86] B. Melamed. The performance analysis workstation: An interactive animated package for queueing networks. In Proc. FJCC’86,1986.[Migu93j C. Miguel and A. Fernandez, J.M. Ortuno and L. Vidaller. ALOTOS Based Performance Evaluation Tool. Special Issue ofCompouter Networks and ISDN, 25(7), Feb. 1993.BIBLIOGRAPHY 204[Miln8O] R. Mimer. A Calculus of Communicating Systems. Springer Verlag, 1980.[Mi1n89] R. Mimer. Communication and Concurrency. Prentice-Hall International, 1989.[Mo1182} M. K. Molloy. Performance analysis using stochastic Petri Nets.IEEE Trans. on Computers, C31(9):913—917, Aug. 1982.[Mo1189a] Michael K. Molloy. Petri Net Modelling — The Past, the Present,and the Future. In Petri Nets and Performance Models TheProc. of the 3rd Intl. Workshop (PN&PM 89 — Kyoto, Japan),pages 2—9. IEEE, 1989.[MollS9bJ Michael K. Molloy. Fundamentals of Performance Modeling.Macmillan Publishing Company, 1989.[Moller] Faron Moller. Process Algebra as a Tool for Real Time Analysis.In Processdings of the IV Banff Higher Order Workshop, 1991 (?).[Mors58j P.M. Morse. Queues, Inventories and Maintenance. Wiley, NewYork, 1958.[Nay166] T.H. Naylor and J.L. Balintfy, D.S. Burdick and K. Chu. Computer Simulation Techniques. John Wiley & Sons, Inc., 1966.[Nich9lJ A. Nicholson and J. Golio, J. Young and W. Roiger. High SpeedNetworking at Cray Research. Computer Communication Review,ACM SIGCOMM, 21(1):99—110, Jan. 1991.Nou85j Nihal Nounou and Yechiam Yemini. Algebraic specification-basedperformance analysis of communication protocols. In Y. Yemini,R. Strom, and S. Yemini, editors, Protocol Specification, Testing and Verification IV (IFIP), pages 541—560. Elsevier SciencePublishers B. V. (North-Holland), 1985.[OPNET] MIL 3, Inc., 3400 International Drive NW, Washington, DC20008. OPNET Tutorial Manual, 1994.BIBLIOGRAPHY 205[PTOLEMY] S. Bhattacharyya and J.T. Buck, W.T. Chang and M.J. Chen, etal. An overview of the Ptolemy project. Unpublished Memorandum, The Ptolemy Group, Dept. of EECS, Univ. of California,Berkeley, March 1994.[Petri62] C. A. Petri. Kommunikation mit Automaten. Technical report, Schriften des Rheinisch-Westfalischen Institutes fur Instrumentelle Mathematik an der Universitat Bonn, Heft 2, Bonn, W.Germany, 1962. translation: C. F. Greene, Supplement 1 to Tech.Rep. RADC-TR-65-337, Vol. 1, Rome Air Development Center,Grifiss Air Force Base, N.Y., 1965.[PhGr88] M. Phalippou and R. Groz. Using Estelle for Verification- AnExperience with the T.70 Teletex. In Formal Description Techniques, I (IFIP FORTE’88), 1988.[Pnue77] Amir Pnueli. The temporal logic of programs. In Proc. of the 18thSymposium on the Foundations of Computer Sciences, pages 46—57. ACM, 11 1977.[PrKi69j A. Alan B. Pritsker and Philip J. Kiviat. Simulation with GASPII. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1969.[Pugh63} Alexander L. Pugh. DYNAMO User’s Manual. The M.I.T. Press,Cambridge, Mass., 1963.[QAF89] J. Quemada and A. Azcorra and D. Frutos. A timed calculus forLOTOS. In Proc. of 2nd Intl. Conf. on Formal Description Techniques, (IFIP FORTE’89), pages 245—264, Vancouver, Canada,1989.[Qi881 Lu Qi and Valdis Berzins and Raymond T. Yeh. A PrototypingLanguage for Real-Time Software. IEEE Transactions on Software Engineering, 14(10), Oct. 1988.[Rico9l] Nathalie Rico and G.v. Bochmann. Performance description andanalysis for distributed systems using a variant of LOTOS. In 11thIntnl. IFIP WG6. 1 Symposium on Protocol Specification, Testing,and Verification, pages 177—199. Elsevier Science Publishers B. V.(North-Holland), 1991.BIBLIOGRAPHY 206[RoWr88J Kenneth A. Ross and Charles R.B. Wright. Discrete Mathematics.Prentice Hall, 1988.[Rudin83] Harry Rudin. From Formal Protocol Specification Towards Automated Performance Prediction. In Protocol Specification, Testing,and Verification, III (IFIP), pages 257—269. Elsevier Science Publishers B. V. (North-Holland), 1982.[SDL] CCITT. Specification and Description Language — Recommendation Z. 100. Geneva, Switzerland: CCITT press, 1986.[SaCh8l] C.H. Sauer and K.M. Chandy. Computer Systems PerformanceModelling. Prentice-Hall, Inc., 1981.SaMa85] C.H. Sauer and E.A. MacNair. The evolution of the researchqueueing package. In D. Potier, editor, Modelling Techniques andTools for Performance Analysis. North-Holland, 1985.[Sari84J B. Sarikaya. Test design for computer network protocols. PhDthesis, McGill University, Canada, March 1984.[Sari86j B. Sarikaya and G.v. Bochmann, M. Makesud and J.M.Serre. Formal specification based conformance testing. In Proc. ACM SIC-COMM Symposium, pages 236—240, Aug. 1986.ISari87] B. Sarikaya and G.v. Bochmann and E. Cerny. A Test DesignMethodology for Protocol Testing. IEEE Trans. on Software Engineering, SE-13(5):518—513, May 1987.[Schr74] Thomas Schriber. Simulation Using GPSS. New York: JohnWiley & Sons, 1974.lSchr9O] Thomas Schriber. An Introduction to Simulation Using GPSS/H.New York: John Wiley & Sons, 1990.[Shaw89j Alan C. Shaw. Reasoning About Time in Higher-Level Language.IEEE Trans. on Software Engineering, 15(7):875—889, July 1989.[Stall9l} William Stallings. Data and Computer Communications. NewYork: Macmillan Pub. Co., 1991.BIBLIOGRAPHY 207[Svob89J Liba Svobodova. Measured performance of transport service inLANs. Computer Networks and ISDN Systems, 18(1), 111989.[Tane88] Andrew S. Tanenbaum. Computer Networks. Prentice-Hall, Inc.,1988.[Ural87a] H. Ural. A test derivation method for protocol conformance testing. In Proc. of 7th IFIP/WG6. 1 International Workshop on Protocol Sepcification, Testing, and Verification, Zurich, Switzerland,May 1987.[VePo85j M. Veran and D. Protier. QNAP2: A portable environment forqueueing system modeffing. In D. Potier, editor, Modelling Techniques and Tools for Performance Analysis. North-Holland, 1985.[Vuong86] S. T. Vuong and D. D. Hui and D. D. Cowan. Valira- A ToolFor Protocol Validation via Reachability Analysis. In Proc. ofthe Sixth IFIP Workshop on Protocol Specification, Testing andVerification, Montreal - St. Jovite, June 1986.[Wagn93] A. Wagner, J. Jiang, and S. Chanson. TMON - A transputerperformance monitor. Concurrency: Practice and Experience,5(6):511—526, 1993.[Watson89] Richard W. Watson. The Delta-t Transport Protocol: Featuresand Experience. In Protocols for High-Speed Networks, IFIP. Elsevier Science Publishers B.V. (North-Holland), 1989.[West82] B.H. West and E.N. Griesback, J.D. Taylor and L.T. Taylor. ThePrentice-Hall Encyclopedia of Mathematics. Prentice-Hall, INC,1982.[WhKr9l] G. Wheeler and P.S. Kritzinger. PEW: A Tool for the AutomatedPerformance Analysis of Protocols. Technical Report CS91-08-00,Data Network Arhcitectures Lab., Dept. of Computer Science,Univ. of Cape Town, 1991.[Wolf82j Ronald W. Wolff. Poisson Arrivals See Time Averages. OperationsResearch, 30(2) :223—231, March-April 1982.BIBLIOGRAPHY 208[Wu89] Jianping Wu and S.T. Chanson. Test Sequence Derivation basedon external behaviour expression (EBE). In Proc. of InternationalWorkshop on Protocol Test Systems, Berlin, Germeny, Oct. 1989.[Yang89] Cui-Qing Yang and Barton P. Miller. Performance Measurementfor Parallel and Distributed Programs: A Structured and Automatic Approach. IEEE Trans. on Software Engineering, 15(12),Dec. 1989.[ZhCh93} Sijian Zhang and Samuel T. Chanson. An Approach to Evaluatingthe Performance of Communications Protocols based on FormalSpecifications. In Proc. of IEEE International Conference on Netowrk Protocols, San Francisco, USA, Oct. 1993.[ZhCh94} Sijian Zhang and Samuel T. Chanson. On Transition Time Testing based on Extended Finite State Machines. In Proc. of the 7thIFIP WG6. 1 International Workshop on Protocol Test Systems(IWPTS’94), Tokyo, Japan, Nov. 1994.[ZiEt92] John A. Zinky and Joshua Etkin. Troubleshooting throughputbottlenecks using executable models. Computer Networks andISDN Systems, 24(1):33—43, March 1992.[Zitt89J Maritina Zitterbart. High-Speed Protocol Implementations BasedOn A Multiprocessor Architecture. In Protocols for High-Speed Networks, IFIP. Elsevier Science Publishers B.V. (North-Holland), 1989.Appendix AMathematical BackgroundA.1 IntroductionThe semi-Markov process (SMP) has been extensively studied in the past decadesand used widely in performance evaluations. Its theory is also the foundation ofthe analysis in this thesis. This appendix provides the definitions and some of theproperties of MPs and SMPs. More detailed discussion of the material presentedin this appendix is referred to [Howa7lJ, [MollS9b] and [Allen9Oj.We extend their results to compute the limiting statistics of a state transitionin a SMP because both states and transitions are of the same importance in ourstudy.The rest of this appendix is organized as follows. Section 2 gives the definitionof Markov Process (MP). Section 3 provides the definition of continuous-timesemi-Markov process (CSMP) and the theorems about the statistical propertiesof a CSMP.209Appendix: mathematical background 210A.2 Markov ProcessA family of random variables {X(t)jt e T} is called a stochastic process, whereT is the index set of the process and X(t) is a random variable. Each value ofX(t) is called a state of the stochastic process. The set of all possible values thatthe random variables X(t) can assume is called the state space of the process.Definition A.1 (Markov process)A stochastic process {X(t), t e T} is a Markov processs (MP), if for any set ofn + 1 values, t1 < t2 < ... < t < in the index set and any set of n + 1states, 5i,S2,,Sn÷i, there isPr{X(t+i) = s+1jX(t)= s, X(t2) = 82, ..., X(t) = s,}= Pr{X(ti) = s+iIX(t) = s,j.This definition means that the next state of a MP depends only on the currentstate.Let p, be the single-step probability of transition ij which is defined as theprobability that j will be the next state when a MP is in state i at present. Bydefinition,Pij = Pr{Xj = iIX i}where X, and X1 denote the current state adn the next state, respectively.Definition A.2 (Markov chain)A Markov process is called a Markov chain if its state space is discrete.Definition A.3 (irreducible)A Markov chain is irreducible if every state is reachable from every other state.Appendix: mathematical background 211Definition A.4 (positive recurrent)A Markov chain is positive recurrent if for every state in the chain, the meantime to return to the state is finite.Definition A.5 (aperiodic)A Markov chain is aperiodic if for each state, there exists an integer k (k > 0) forwhich there are transition sequences in the chain starting from the state and backto itself and these sequences traverse k, k + 1, k + 2,.•• transitions respectively.Definition A.6 (ergodic)A Markov chain is ergodic if it is irreducible, recurrent nonnull and aperiodic.We define the steady-state state probability of state i in of a MP is the probability that the MP is seen at state i by an arbitary observer after the MP runsfor a very long period of time. This probability is denoted as 7r.Theorem A.1 (steady-state state probability)If a Markov chain is ergodic, its steady-state state probabilities exist and theyare equal to its stationary state probabilities which can be computed by solvingthe following matrix equationTrP=lr (A.1)where it=[irj is the vector of the steady-state state probabilities and it2 = 1;P = [p23] is the matrix of the single-step transition probabilities.Proof: See [Mo1189b](p.132). DAppendix: mathematical background 212A.3 Continuous-time Semi-Markov ProcessDefinition A.7 (continuous-time semi-Markov process)If the successive state occupancies of a stochastic process are governed by thetransition probabilities of a Markov process, but their stay in any state is describedby a positive continous variable which only depends on the current state, then theprocess is called a continous-time semi-Markov process (CSMP). The MarkovProcess is called the embedded Markov process of the CSMP.Let be the time between the moment a CSMP enters state i and themoment it enters the next state, say state j. r1 is called the holding time at statei before the CSMP enters state j. r, is also called the transition time from statei to j. By the definition of CSMP, r is a positive continous random variable.We denote the probability density function (p.d.f.) of this random variable ash(t).Let Ti denote the time the CSMP stays in state i before the CSMP entersany other state. Ti 15 called the holding time of the CSMP at state i. T is also acontinous random variable. Let h(t) be the p.d.f. of Ti. By [Howa7l}, h(t) canbe computed ash2(t)Therefore, the relation of the mean values of T and T, can be expressedLet be the overall mean holding time of the CSMP at any state. t can becomputed as=Appendix: mathematical background 213A.3.1 Steady-state state probabilityWe define the steady-state state probability of state i in a CSMP, ir1, is the probability that state i is seen at state change instants after the CSMP runs over along period of time.By the definition of CSMP, it is seen that the process at the state changeinstants in a CSMP is the embedded MP of the CSMP. Therefore, the steady-state state probabilities of the MP and the CSMP shall be the same which canbe computed by solving Equation (A.1).A.3.2 Limiting state lodging probabilityFor a CSMP, it is important and also very useful to know which state the processoccupies at an arbitrary moment.We define çb, (t) is the probability that the process is seen in state j at timet given that it entered state i at time zero. 2(t) is called the state lodgingprobability in this thesis. 1Theorem A.2 (limiting state lodging probability)If the embedded Markov chain of a CSMP is ergodic, the limiting state lodgingprobabilities exist and can be computed ascbjj = lim ,(t) = ==t—+oo EklrkTk rwhere f and ?, are the mean values of r, and r23, respectively.Proof: See [Howa7l](p.595). DFrom this theorem, it is seen that the limiting state lodging probability ofa state is no longer related to its starting state of the CSMP. Therefore,,is‘cb, (t) is called an interval transition probability in [Howa7l] (p.694).Appendix: mathematical background 214the probability that an arbitrary observer sees the CSMP is in state j when theCSMP is in steady state.A.3.3 First passage timeLet O, be the mean first passage time from state i to j in a CSMP, and 8,2 bethe second moment of the first passage time from state i to j.Theorem A.3 (First Passage Time Moments)When the CSMP is in steady-state, we can computeij = + Pikkj— Pij°jjand_.+ +).kjProof: See [Howa7l](p.735). DA.3.4 State RecurrenceAn instant entrance rate from state i to j is defined as that eij(kt), wherez is very small, is the probability that the CSMP will enter state j on its kthtransition in the time interval (t,t + ) given that it made its zeroth transitioninto state i at time zero. This instant entrance rate is denoted as ei,(klt).Let e3 be the limiting value of e(kt), i.e.,e3 = lime23(klt).t—+ooTheorem A.4 (limiting entrance rate)If the embedded Markov process is ergodic, e2, exists and is equal toe1, = ...2. = eAppendix: mathematical background 215where ir is the limiting state probability of state j for the imbedded Markov processand is the overall mean time between transitions.Proof: See [Howa7lj(p.725). CThis theorem says that after a long period of time, e23(kjt) is not related tothe starting state of the CSMP any more.The recurrence time of state i is the first passage time from state i to i in aCSMP. Let 8 denote this recurrent time.Theorem A.5 (mean recurrence time)When the CSMP is in steady state, the mean recurrence time of state i, jj, isequal to the reciprocal of the limiting entrance rate of state i, i.e.,— 1eu = —.eProof: See [Howa7l](p.735).From the above two theorems, it is seen that the limiting entrance rate of astate in a CSMP is also the mean entrance rate of the state. We denote the latterusing e.A.3.5 Transition recurrenceTransitions in a CSMP are as important as states in our study. It is useful toknow the statistics about the transitions of a CSMP. We extend the above resultsfor transitions in the following.We have defined the mean entrance rate to state i is ë2 when a CSMP in asteady-state.At state i, the CSMP may choose any state as its next state. By definition,the CSMP chooses the transition to state j with probability Pij. Therefore, theAppendix: mathematical background 216mean entrance rate of the transition from state i to state j is e2 Pu . Let ii,,denote this rate. We have?lij iPij (A.2)The mean rectrrence time of the transition from state i to state j is thereciprocal of the mean entrance rate, i.e.,We use Figure A.1 to illustrate these relationships.state i appearances‘Time\ -.-.. t “./ .yss_,._‘SI S,_.. IS%SsS,I,____•%__‘s Ienter state i enter a next state after state ithe transition time from state ito the next stateFigure A.1: The occupancies of state i in time axisAppendix BComputation ofSuppose X and Y are random variables. Let E[Xj be the mean of X, Var[X]be the variance of X, and Cov[X,Y] be the covariance of X and Y.Lemma B.1 1. E[X + Y] = E[X] + E[Y];2. Var[X + Y] = Var[XJ + Var[YJ + 2Cov[X, Y];3. Var[X] = E[X2j — (E[XJ)2.4. Cov[X, Yj = E[XYJ - E[X]E[Y].Proof:See [Allen9O](p52).E[X2] is called the second moment of X. We use to denote E[X2].Now we can compute the second moment of the service time By definition,f s(ij —+ Ofi i j217Appendix: computation of( 218We compute (, in two cases as follows:1. Ifi=j, then—s-2‘23_ tiwhere can be computed directly from the given probability densityfunction (p.d.f.) of the service time of transition ii, S/()2. Ifij, then= E[(8r2+b9)2]= ST2 + ‘‘8, + 2• E [Since 3r, and ?,t)9 are uncorrelated for the reason stated in Chapter 5,(B.1)where can be computed from the provided p.d.f. of 8r and ‘8J can becomputed using Theorem A.3.Appendix CAn Estelle specification forsliding window protocolThis appendix contains an Estelle specification of the sliding-window protocol.This specification is modified based on Tom Blumer’s specification in 1986 whichwas ftp-ed from est-specsudel.edu. The module graph is in Figure C.1.Figure C.1: Module relation graph of sliding window protocolThe specification in Estelle is as follows:specification sliding_window_protocol;default individual queue;219Appendix: an Estelle specification of the sliding-window protocol 220{Origin : November 3, 1986Tom BlumerProtocol Development Corporation1330 Beacon St.Brookline, MA 02146 USA(617)354—8558Modified by : Sijia.n Zhang, Oct. 7, 1992J.type seq...type = integer; { sequence number type, must be >= 0 }user_data_type =DTPDU_type = recordseq: seq_type;msg: user_data_type;end;AKPDU_type = recordseq: seq_type;end;chamiel user_chan(user, provider);by user:Data_Request(data : user_data_type);by provider:Data_Indication(data : user_data_type);channel comm_chan(DT_sender, DT_receiver);by DT_sender:DT(PDU : DTPDU_type);by DT_receiver:AK(PDU : AKPDU_type);channel timer_chan(user, provider);by user:timer_request(seq : seq_type);timer_ca.ucel(seq : seq_type);by provider:timer_response(seq : seq_type);module user_head systemprocess;Appendix: an Estelle specification of the sliding-window protocol 221ip U : user_chan(user);end;body transmitter_user for user_head; external;body receiver_user for user_head; external;module timer_head systemprocess;ip T : timer_chan(provider);end;body timer for timer_head; external;module transmitter_head systemprocess;ip U user_chan(provider);CT : comm_chan(DT_sender);T : timer_chan(user);end;{ transmitter module body }body transmitter for transmitter_head;const transmitter_window_size any integer;state SENDING;{ save user data in buffer until acknowledgment }procedure buf_save(s : seq_type; d user_data_type); primitive;{ free user data buffer entry after acknowledgment }procedure buf_free(s : seq_type); primitive;{ retrieve user data entry from buffer }function buf_retrieve(s : seq_type) : user_data_type; primitive;{ construct a DT PDU from the user data and sequence number }function PDU_DT(s seq_type; d : user_data_type)DTPDU_type; primitive;varAppendix: an Estelle specification of the sliding-window protocol 222Lowest_Unacked : seq_type;Highest_Sent : seq_type;TWS : integer;initializeto SENDINGbeginLowest_Unacked := 1;Highest_Sent : 0;TWS := transmitter_window_size;end;trans{ transmit while window not full }Ti: from SENDING to samewhen U. Data_Requestprovided Highest_Sent - Lowest_Unacked < TWSbeginHighest_Sent : Highest_Sent + 1;output T.timer_request(Highest_Sent);output CT.DT(PDU_DT(Highest_Sent, data));buf_save(Highest_Sent, data);end;{ receive acknowledgment }T2: from SENDING to samewhen CT.AKprovided (PDU.seq >= Lowest_Unacked) and (PDU.seq <= Highest_Sent)var s : seq_type;beginfor s : Lowest_Unacked to PDU.seq dobeginoutput T.timer_cancel(s);buf_free(s);end;Lowest_Unacked : PDU.seq + 1;end;{ receive ack not in window }Appendix: an Estelle specification of the sliding-window protocol 223T3: provided otherwisebegin{ ignore this ack }end;{ Timer response }T4: from SENDING to samewhen T . timer_responseprovided (seq >= Lowest_Unacked) and(seq < Highest_Sent)var s : seq_type;beginfor s := seq to Highest_Sent dobeginoutput T.timer_cancel(s);output CT.DT(PDU_DT(s, buf_retrieve(s)));output T.timer_request(s);end;end;T5: provided otherwisebegin{ ignore t response for sequence number outsidethe window. This can happen when an AK arrivesjust when a timer response occurs. }end;end; { tra.nsmr }module receiver_head systemprocess;ip U : user_chan(provider);CR : comm_chan(DT_receiver);end;{ receiver module body }body receiver for receiver_head;const receiver_window_size = any integer;Appendix: an Estelle specification of the sliding-window protocol 224state RECEIVING;{ construct an AK PDU, given the sequence number }function PDU_AK(s seq_type) : AKPDU_type; primitive;{ retrieve the PDU of sequence number s from the buffer.If it is not in the buffer, return a PDU with seq number set to 0 }function PDU_retrieve(s : seq_type) DTPDU_type; primitive;{ Save the PDU in the buffer }procedure PDU_save(PDU : DTPDU_type); primitive;{ returns true if the PDU is corrupted }function corrupted(PDU DTPDU_type) : boolean; primitive;{ Return the user data from the given PDU }function user_data(p DTPDU_type) : user_data_type; primitive;varNext_Required : seq_type;Highest_Received : seq_type;RWS : integer;initializeto RECEIVINGbeginNext_Required : 1;Highest_Received : 0;RWS receiver_window_size;end;trans{ receive message in window }from RECEIVING to samewhen CR.DTprovided (PDU.seq >= Next_Required) and(PDU.seq < Next_required + RWS) andnot corrupted(PDU)var s : seq_type;Appendix: an Estelle specification of the sliding-window protocol 225tpdu : DTPDU_type;done : boolea.u;beginPDU_save(PDU);s : Next_Required;done := false;{ Retrieve each PDU fromStop when we reach thethe first PDU that hasPDU_retrieve returns athe desired PDU is notrepeattpdu := PDU_retrieve(s);if tpdu.seq = s thenbegin{ extract user data from PDU and send to user }output U.Data_Indication(user_data(tpdu));S S + 1;endelse{ reached gap in buffer }done : true;until done;Next_Required : s;output CR.AK(PDU_AK(Next_Required- 1));end;{ receive message not in window }provided otherwisebeginoutput CR.AK(PDU_AK(Next_Required Ii);end; { receiver }modvar transmitter_instance transmitter_head;receiver_instance : receiver_head;transmitter_user_instance, receiver_user_instance : user_head;timer_instance timer_head;buffer and send it to the user.first gap in the buffer, i.e.,not been received.PDU with sequence number 0 ifin the buffer }end;Appendix: an Estelle specification of the sliding-window protocol 226initializebeginmit transmitter_user_instance with tra.nsmitter_user;mit receiver_user_instance with receiver_user;mit transmitter_instance with transmitter;mit receiver_instance with receiver;mit timer_instance with timer;connect transmitter_user_instance . U to transmitter_instance . U;connect receiver_user_instance .U to receiver_instance .U;connect transmitter_instance.CT to cms_instance.CR;connect transmitter_instance.T to timer_instance.T;end;end.Appendix DAn Estelle specification of thehot-potato protocolThis appendix contains an Estelle specification of the hot-potato protocol.SPECIFICATION hot_potato SYSTEMACTIVITY;CHANNEL toss (thrower, catcher);BY thrower:POTATO (thrower_num: integer);BY catcher:POTATO (catcher_num: integer);CHANNEL pass (left_hand, right_hand)BY left_hand:POTATO;BY right_hand:POTATO;MODULE player ACTIVITY (player_num: integer);IPLEFT_SIDE : toss(catcher) INDIVIDUAL QUEUE;RIGHT_SIDE: toss(thrower) INDIVIDUAL QUEUE;END; { MODULE player }227Appendix: an Estelle specification of the hot-potato protocol 228BODY player_process FOR player;STATE sO, si;IP { internal interact, points }LEFT_HAND : pass (left_hand);RIGHT_HAND: pass(right_hand);VARthe_player : integer;started : boolea.n;INITIALIZETO sOBEGINthe_player : 1;connect LEFT_HAND to RIGHT_HAND;the_player : 1;END;TRANSPROVIDED (player_num=1 AND started = false)BEGINOUTPUT RIGHT_HAND . POTATO;started : true;END;TRANSFROM sOTO siWHEN LEFT_SIDE. POTATOBEGIN{...}OUTPUT LEFT_HAND . POTATO;END;TRANSAppendix: an Estelle specification of the hot-potato protocol 229FROM siTO sOWHEN RIGHT_HAND. POTATO;BEGINif ((the_pla.yer+1)<NumPlayer) thenOUTPUT RIGHT_SIDE.POTATO(the_player+1);elseOUTPUT RIGHT_SIDE.POTATO(1);END;END; { BODY player_process }CONSTANTNumPlayer =...;MODVARPlayers array [1. .NumPlayer] of player;VARi: integer;INITIALIZEBEGINall i: 1. .NumPlayer doBEGININIT Players[i] WITH player_process (i);END;all i: 1. .NuinPlayer doBEGINCONNECT Players [i] . RIGHT_SIDE to Players [i] LEFT_SIDE;END;CONNECT Players [1] .LEFT_SIDE to Players[NumPlayer] .RIGHT_SIDE;END;END. { hot_potato }Appendix EAn application example ofHyPEFSMThe example described in this appendix is the circuit-switched multi-stageinterconnection network (MIN) with a hold protocol [HaPa93].A MIN is a matrix of small interconnected crossbars used in multiprocessorcomputers or network switches. MINs can be classified as blocking and non-blocking, and synchronous and asynchronous. Some well-known MINs are banyannetworks, Benes networks and Cbs networks.The MIN to be studied in this appendix belongs to a subclass of banyannetworks called delta networks. The MIN is asynchronous with a hold protocolwhich specifies the procedure for a processor to access a memory module. Thefinite state machine diagram of the hold protocol is given in Figure E. 1.State 0 is the starting state (often called the idle state) of the switch. Theswitch is in state 0 when there is no memory access request. Initially, the switchis in state 0, and it enters this state each time it finishes serving a request. Weassume that the memory access requests from processors arrive asynchronouslyin a Poisson pattern with parameter A. The requests will be queued on arrival if230Appendix: an application example of HyPEFSM 231the switch is not in state 0. The service policy for requests is first-come first-serve(FCFS) and the queuing discipline is first-in first-out (FIFO).When the switch accepts a request, it enters state 1 immediately. At state 1,the switch checks if link 1 is free or not. If link 1 is free, the switch acquires thelink and enters state 3 (= 2 x 1 + 1); otherwise, it enters the blocking state 2(= 2 x 1), waiting for the release of the link. As soon as link 1 is free, the switchacquires it and enters state 3. In state 3, the switch attempts to acquire link 2using the same procedure as before. This process is repeated until all requiredlinks have been acquired.We assume that there are a total of J links to be acquired before a processorcan access the memory. As soon as all J links have been obtained and the switchenters state 2 x J + 1, the actual memory access begins. After the access iscompleted, the switch goes back to state 0 to serve the next request.Therefore, the FSM of the hold protocol has a total of (2J + 2) states and(3J + 2) transitions. This FSM with the arrival and service model describedabove is a HyPEFSM that has only one asynchronous state (state 0) and oneasynchronous transition (from state 0 to state 1). The other states and transitionsare synchronous.Figure E.1: FSM for the hold protocolWe assume that the checking of the status of link i (1 i J) takes anAppendix: an application example of HyPEFSM 232average time h2. Let b, be the probability that link i is not free and 1/-)’, be themean time that the switch stays in state 2i waiting for link i. Finally, we assumethat the memory access time takes 1/p on average.We translate the above information into the input data required by the HyPEFSM:• P= [pJ where1 if(i=Oandj=l)or(i=2J+landj=O)ifi=2n—landj=2nandn=1,2,...,JEll—b ifi=2n—landj=2n+landn=1,2,...,J0 otherwise•= 0 except for S210 =• w2,_12= h where n = 1, 2,..., J and Wf210 = 0.W01 is unknown and it can be computed using the method introduced inChapter 6.We are interested in the performance metrics such as the probability that arequest is served on arrival without waiting (i.e., po,o), the mean queue wait timeof memory access requests (i.e., Wq,o), and the mean overhead for a request beforememory is accessed (i.e., Wq,o + 1,2J+1).The first passage times from state i (i = 2J + 1, 2J, ..., 2, 1) to state 0 arecomputed in the following using Formula (A.3):O2J+1,O = ‘1’T2J+ + P2J+148k0 — P2.J+1,0600 (E.2)1(E.3)IL82J,0 = ‘2J + P2J,k8ko— P2.1,o800 (E.4)=--+ (E.5)7J /1Appendix: an application example of HyPEFSM 23382J_1,o = ‘1T2J_1 + P2J—1,k6kO — P2.J—i,0900 (E.6)(E.7)(E.8)b• 1= Eh+E-+—. (E.9)11 i=1 7 Jio is in fact the mean holding time of the switch by a request after serviceon the request has started.The mean time spent on obtaining all the links required is“81,2J+1= 10— “‘02J+1,o=Ehi+E_.i=1 ;=i 7:Applying Equation (6.7), we getPo,o 1A01(%+ o) (E.1O)b• 1= 1—A.(Eh+-.+—) (E.1i)i=1 1=1 7where A = A. P0,0 is the probability that a memory access request will be servedimmediately upon its arrival.To compute the mean queue wait time, we need to obtain % first. ApplyingTheorem A.3, we derive‘Tj1 + p2J+1,k(2 ‘kO +) (E.12)k0= rj.,.jo; (E.13)J,o = 7ji + E p2J,k( ‘%J,2J+1 kO + ) (E.14)k0—2 q w— 2J + L P2J,2J+1 T2J,2J+1 V2J+1,0 + V2J+1,oU + 2. P2J,2J+1 + wrj; (E.16)Appendix: an application example of HyPEFSM 234= 22_1 + E p2J,k(2 ‘‘2J...1,2J• kO + (E.17)kO= ‘2J_1 +P2J—1,2J (22J_1,2J. ‘‘62J,o + (E.18)+P2J—1,2J+1 (2r2J_1,2J+l + i,+1,o); (E.19)(E.20)1O wT2 +pl2(2 T2 ‘82o+o) (E.21)+13 (2’13. %O (E.22)It can be seen that 4Yc, can be computed recurrently using the above recurrentequations. The mean queue wait time is obtained as—Wq,O — . (E.23)1 Po) Po,oWith (E) and (E.23), the mean overhead of a request in the switch, i.e.,14q.O + %,2J+1, can be obtained.In the following, we examine a simple case with only one link (i.e., J = 1)in the switch. We assume that the checking time, the blocking times and thememory accessing time are all exponentially distributed.In this case,1 1= h1 + — + —7i I’and— 2=— 2=— 27’— 2=— 2‘i2Appendix: an application example of HyPEFSM 235— 21Therefore,— 230 —=71 /17 It= 2(h+1+-)+2i(h+l !)./.t /1 71 11 7iUsing the information obtained above, we rewrite the mean queue wait timeas— 2•p0,—_________________—With the above formula, we can study the mean queue wait time vs. the arrivalrate. Figure E.2 shows the relation for h1 = O.OOlsecond, 71 = O.OOlsecon.d,/1 O.Olsecond and b1 = 10%. It can be seen from the figure that the mean queuewait time grows rapidly after the mean arrival rate reaches 80 requests/second.Figure E.3 shows the case when h1 = 0.OOlsecond, 7i = 0.O0lsecond, =0.Olsecond and ). = 5Orequests/second. It can be seen from the figure that thegrowth of the mean queue wait time vs. the blocking probability is approximatelylinear.Appendix: an application example of HyPEFSM30002500a). 20001500a)1000500z040 50 60 70Mean arrival rate (requests/sec)Figure E.2: Mean queue wait time vs. arrival rate14001200a)1000. 800) 6004002000236Queue wait time vs arrival rate20 30 80Queue wait time vs blocking probability0 0.2 0.4 0.6 0.8Blocking probabilityFigure E.3: Mean queue wait time vs. blocking probabilityAppendix FBottleneck identification resultsIn this appendix, we report the results of the FDDI MA C Transmitter. TheFSM of the transmitter is shown in Figure F.1.Stale 0: TX_IDLEState 1: REPEATStale 2: TX_DATAState 3: ISSUE_TKState 4: CLAIM_TKStateS: TXBEACONTransiuons:12: reset Tt2: ,saetTI: reenive stntt T13: another frame12: usable token reenived T14: dose12 token reenived sad mat usable T13: recovesyT4: recovery T16: jose,T5: beam, requested T17: token12: lobe, coam TIS: ,ecovesyT7:tobenro1 T19: ,eaelT8: smp 120: ntcczuM ctulm12: reset 121: lulledTt0: frame repented 122: roastTtt:rea,vay 123: CoedFigure F.l: The FSM of FDDI MAC TransmitterWe assume that all the incoming messages are asynchronous and the arrivalsof each class follow a Poisson pattern. Therefore, the FSM with these assumpTIS237Appendix: bottleneck identification results 238tions is an AsPEFSM-c. The distributions of the service times of the transitionsassociated with each class of incoming messages are exponential. The mean service times are given in Column 2 of Table F.1. The mean arrival rates of eachclass are given in Column 3 of the table. Columns 4, 5 and 6 are the simulationresults.transition service arrival rate transition transition average queuingnumber time(sec) (mesgs/sec) probability0 weight time reduction (sec)b0 0.025 10.0000 0.0614 0.0274 0.018711 0.025 10.0000 0.0613 0.0053 0.019052 0.025 10.0000 0.0613 0.0063 0.017793 0.025 10.0000 0.0614 0.0128 0.020324 0.025 10.0000 0.0613 0.0163 0.022905 0.025 10.0000 0.0613 0.0108 0.019546 0.025 10.0000 0.0102 0.0046 0.005807 0.025 10.0000 0.0102 0.0046 0.001998 0.025 10.0000 0.0102 0.0046 0.005349 0.025 10.0000 0.0102 0.0046 0.0076610 0.025 10.0000 0.0102 0.0046 0.0074811 0.025 10.0000 0.0102 0.0027 0.0085612 0.025 10.0000 0.0204 0.0091 0.0109213 0.025 10.0000 0.0204 0.0021 0.0019114 0.025 10.0000 0.0204 0.0043 0.0079915 0.025 10.0000 0.0204 0.0054 0.0101416 0.025 10.0000 0.0503 0.0225 0.0193317 0.025 10.0000 0.0503 0.0225 0.0209118 0.025 10.0000 0.0504 0.0134 0.0166419 0.025 10.0000 0.0691 0.0309 0.0241720 0.025 10.0000 0.0692 0.0145 0.0169021 0.025 10.0000 0.0692 0.0122 0.0199922 0.025 10.0000 0.0652 0.0291 0.0236623 0.025 10.0000 0.0653 0.0173 0.01773“the steady-state transition probability.bThe new average queue wait time is measured by decreasing the mean service time of thecorresponding transition by 0.005 second. The reduction is equal to the original value minusthe new value.Table F.1: A simulation resultFrom the table, we can see that reducing the service time of the transitionAppendix: bottleneck identification results 239with the largest weight causes the largest reduction in the mean queue wait timeof that class of incoming messages. This result confirms the analysis given in thissection.Appendix GT-test results of a LAPBimplementationThis appendix reports the t-test results for a LAPB implementation.The finite state machine (FSM) of LAPB is referred to in Figure 3.2. However,the implementation under test (IUT) is only a subset of the LAPB protocol. TheJUT is treated as a black box in testing. The testing architecture is the same asthe one shown in Figure 8.12. The interface modules are also similar but a littlemore complicated than those used to test abstract protocols (see Chapter 8).Here we have to use the service primitives such as lapb_down() and lapb_upOprovided by the LAPB implementation in the interface modules.Table G.1 shows the testing results of some transitions. The first threecolumns are starting states, ending states and I/O events of transitions. Thelast three columns record the results from measurement and testing. Columns 4and 5 are the measurement results and column 6 are the t-test results. All thetimes in Columns 4, 5 and 6 are in milliseconds (ms).The total overhead of network transmission and the interface with the JUTis about 0.2 ms. Deducing this overhead from each result in columns 5 and 6,240Appendix: T-test results of a LAPB implementation 241From To I/O Measured Measured T-testService Timec Response Timeb ResultcDISCONNECTED SABM..SENT LCONreq/SABM..CTRL 54.4 49.6 54.1DISCONNECTED DISCONNECTED SABM/LCONInd 49.4 39.6 49.9DISCONNECTED DATAJRANSFER LCONrsp/UACTRL 56.8 49.5 56.3DATA..TRANSFER DATAJRANSFER ICTRL/L..DATind 78.8 69.6 80.9DATA..TRANSFER DISCONNECTED DISCCTRL/UA..CTRL 39.4 29.5 38.2aThe service time of each transition is measured when the implementation is treated as awhite box.bThe response time is obtained by computing the difference between the message sendingtime and the response time. When there are two or more responses for one input such asDISC/(UA,L_DISC.ind), only one of them is chosen throughout the test.CThe error tolerance is 5%.Table G.1: Testing results of the LAPB implementationwe observe that the t-test results in column 6 are closer to the measured servicetimes of the same row in column 4 than the measured response times of the samerow in column 5.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Performance modelling and evaluation of protocols based...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Performance modelling and evaluation of protocols based on formal specifications Zhang, Sijian 1995
pdf
Page Metadata
Item Metadata
Title | Performance modelling and evaluation of protocols based on formal specifications |
Creator |
Zhang, Sijian |
Date Issued | 1995 |
Description | 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. |
Extent | 4802131 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-04-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051663 |
URI | http://hdl.handle.net/2429/7470 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1995-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1995-060942.pdf [ 4.58MB ]
- Metadata
- JSON: 831-1.0051663.json
- JSON-LD: 831-1.0051663-ld.json
- RDF/XML (Pretty): 831-1.0051663-rdf.xml
- RDF/JSON: 831-1.0051663-rdf.json
- Turtle: 831-1.0051663-turtle.txt
- N-Triples: 831-1.0051663-rdf-ntriples.txt
- Original Record: 831-1.0051663-source.json
- Full Text
- 831-1.0051663-fulltext.txt
- Citation
- 831-1.0051663.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051663/manifest