Open access

Performance Evaluation of Distributed System Using SPN

Written By

Razib Hayat Khan, Poul E. Heegaard and Kazi Wali Ullah

Submitted: 02 February 2012 Published: 29 August 2012

DOI: 10.5772/48813

From the Edited Volume

Petri Nets - Manufacturing and Computer Science

Edited by Pawel Pawlewski

Chapter metrics overview

2,335 Chapter Downloads

View Full Metrics

1. Introduction

Distributed system poses one of the main streams of information and communication technology arena with immense complexity. Designing and implementation of such complex systems are always an intricate endeavour. Likewise, performance evaluation is also a great concern of such complex system to evaluate whether the system meets the performance related system requirements. Hence,modelingplays an important role in the whole design process of the system for qualitative and quantitative analysis. However, in a distributed system, system functional behavior is normally distributed among several objects. The overall behavior of the system is composed of the partial behavior of the distributed objects of the system. So it is indispensable to capture the functional behavior of the distributed objects for appropriate analysis to evaluate the performance related factors of the overall system. We therefore adopt UML collaboration and activity oriented approach as UML is the most widely used modeling language which models both the system requirements and qualitative behavior through different notations. Collaboration and activity diagram are utilized to demonstrate the overall system behavior by defining both the structure of the partial object behavior as well as the interaction between them as reusable specification building blocks and later on, this UML specification style is applied to generate the SPN model by our performance modeling framework. UML collaboration and activity provides a tremendous modeling framework containing several interesting properties. Firstly, collaborations and activity model the concept of service provided by the system very nicely. They define structure of partial object behavior, the collaboration roles and enable a precise definition of the overall system behavior. They also delineate the way to compose the services by means of collaboration and role bindings [12].

Considering system execution architecture to specify the deployment of the service components is realized by the UML deployment diagram. Abstract view of the system execution architecturecaptured by the UML deployment diagram defines the execution architecture of the system by identifying the system components and the assignment of software artifacts to those identified system components. Considering the system architecture to generate the performance model resolves the bottleneck of system performance by finding a better allocation of service components to the physical nodes. This needs for an efficient approach to deploy the service components on the available hosts of distributed environment to achieve preferably high performance and low cost levels. The most basic example in this regard is to choose better deployment architectures by considering only the latency of the service. The easiest way to satisfy the latency requirements is to identify and deploy the service components that require the highest volume of interaction onto the same resource or to choose resources that are connected by the links with sufficiently high capacity [12].

It is indispensable to extend the UML model to incorporate the performance-related quality of service (QoS) information to allow modeling and evaluating the properties of a system like throughput, utilization and mean response time. So the UML models are annotated according to the UML profile forMARTE: Modeling& Analysis of Real-Time Embedded Systems to include quantitative system parameters [1]. Thus, it helps to maintain consistency between system design and implementation with respect to requirement specifications.

Markov models, stochastic process algebras, SPN (Stochastic Petri Net) are popular and much studied analytical approaches to conduct performance modeling and evaluation. Among all of them, we will focus on the SPN as the performance model generated by our framework due to its increasingly popular formalismsfor describing and analyzing systems, its modeling generality, its ability to capture complex system behavior concisely, its ability to preserve the original architecture of the system, to allow marking dependency firing rates & reward rates defined at the net level, to facilitate any modification according to the feedback from performance evaluation and above all,the existence of analysis tools.

Several approaches have been followed to generate the performance model from system design specification. Lopez-Graoet al.,described a conversion method from annotated UML activity diagram to stochastic petrinet model [2]. Distefanoet al.,proposed a possible solution to address software performance engineering that evolves through system specification using an augmented UML notation, creation of an intermediate performance context model, generation of an equivalent stochastic petri net model whose analytical solution provides the required performance measures [3]. D’Ambrogio proposeda framework for transforming source software models into target performance models by the use of meta-modeling techniques for defining the abstract syntax of models, the interrelationships between model elements and the model transformation rules [4]. Trowitzsch and Zimmermann proposed the modeling of technical systems and their behavior by means of UML and for the resulting models, a transformation into a Stochastic Petri Net was established [13]. Abdullatif and Pooly presented a method for providing computer support for extracting Markov chains from a performance annotated UML sequence diagram [14].However, most existing approaches do not highlight more on the issue of how to optimally conduct the system modeling and performance evaluation. The approach presented here is the first known attempt that introduces a new specification style utilizing UML behavioral diagrams as reusable specification building block which is later on used for generating performance model to produce performance prediction result at early stage of the system development process. Building blocks describe the local behavior of several components and the interaction between them. This provides the advantage of reusability of building blocks, since solution that requires the cooperation of several components may be reused within one self-contained, encapsulated building block. In addition, the resulting deployment mapping provided by our approach has great impact with respect to QoS provided by the system. Our aim here is to deal with vector of QoS properties rather than restricting it in one dimension. Our presented deployment logic is surely able to handle any properties of the service, as long as we can provide a cost function for the specific property. The cost function defined here is flexible enough to keep pace with the changing size of search space of available host in the execution environment to ensure an efficient deployment of service components. Furthermore, we aim to be able to aid the deployment of several different services at the same time using the same framework. The novelty of our approach also reflected in showing the optimality of our solution with respect to both deployment logic and evaluation of performance metrics.

The objective of the chapter is to provide an extensive performance modeling framework that provides a translation process to generate SPN performance model from system design specification captured by the UML behavioral diagram and solves the model for relevant performance metrics to demonstrate performance prediction results at early stage of the system development life cycle. To incorporate the cost function to draw relation between service component and available physical resources permit us to identify an efficient deployment mapping in a fully distributed manner. The work presented here is the extension of our previous work described in [5, 6, 7, 12] where we present our framework with respect to the execution of single and multiple collaborative sessions and to consider alternatives system architecture candidatesto describe system functional behavior and later on to evaluate the performance factors. The chapter is organizedas follows: section 2 describes the performance evaluation of distributed system where the requirements of the successful performance evaluation are mentioned, section 3 introduces our performance modeling framework in details by considering the requirements outlined in the previous section, section 4 shows the applicability of our performance modeling framework with respect to performance modeling of a distributed system, and section 5 mentions the concluding remarks with future directions.

Advertisement

2. Performance evaluation of distributed software system

Performance evaluation is an integral part of any distributed software system which gives an indication of whether the system will meet non functional properties, once system built. The evaluation can be done in one of the two stages of the software development process:

  1. Evaluation can be conducted at the early stage of the software development process

  2. Evaluation can be done when the development process is completed.

Conducting the performance evaluation in any of the two stages has some merits and demerits. Early assessment of performance evaluation allows system designer predicting the system response in order to meet the non functional requirements before the system being built. This in turn guides the system designer about the system development process in right manner which thus increases the productivity and quality in accordance with the reduction in cost. But conducting performance evaluation in the early stage of the software development process is challenging because of the absence of the real system in hand. So predication in advance not always guides the system designer in right way. Modeling system functional behavior perfectly works as a catalyst to successfully conduct the system performance evaluation. System functional behavior is disseminated across several components that are physically distributed which increases the complexity in developing distributed software systems. Perfect modeling of distributed system functional behavior is realized by capturing the local behavior of the system components and also the interaction among them. It is very difficult to achieve these tasks in correct way when development of system is limited in the laboratory where modeling will be done by generating case study or scenario.

Conducting performance evaluation after the system development process being completed is less challenging than the former case. It is possible to retrieve the real system response in order to meet the system non functional requirements as the real system is already implemented. So the designer can get a real understanding about the correct status of the development process to know whether the system can meet the non functionalrequirements and end user’s expectation. If the system fails to satisfy non functional requirements and can’t meet the end user expectation, the only alternative is to rethink about the system design process. Any change in the system design process can cause the modification in the system development process. In worst case the development process might start from the beginning which in turn costs a lot.

In order to conduct the performance evaluation of distributed software system, the decision is not only influenced by when the evaluation should be performed but also other factors like which evaluation technique is appropriate and reasonable. There are mainly two evaluation techniques:

  1. Simulation based evaluation

  2. Analytic solution

Simulation based solution of the actual implementation gives a better assessment of the performance evaluation of the system. Simulation based solution gives the freedom to build the system arbitrary detailed and there is no restriction on building the simulation model of the real system [8]. Thus, it allows modeling and evaluating the system performance in a flexible way. But to develop the simulation model is not an easy task and sometimes it is error-prone. Implementing a complex system is usually a time-consuming, expensive task and needs experience [8]; mastering to handle this complexity is driven by the gaining vast knowledge in simulation language and how to apply this language to build and present the logic behind the complex distributed system to capture system functional behavior properly for conducting performance evaluation.

Analytical solution is another way to conduct the performance evaluation of the complex distributed software system. Presence of well established mathematical formula for analytical methods makes it popular to the scientific community to obtain the performance evaluation of the systems. This method of finding solution is more acceptable than simulation based evaluation because of the direct applicability of the mathematical formula and the availability of evaluation tools. Another advantage of using analytic model is the rapid development of model for performance evaluation of large and multifaceted system using the formalismsof analytical methods. However, sometimes such analytical models can usually be constructed by placing some structural restrictions and assumptions on the original system model based on the explicit modeling formalism which has been selected; the reason is that analytical models have a limited expressiveness in some cases to capture the complex system behavior. While it is sometimes doable to simplify the model of the system in order to make it analytically tractable, there are many cases in which the significant aspects of the system can not be effectively represented into the analytical model for performance evaluation [8].

In this chapter we particularly focus on the performance evaluation of the distributed software system at the early stage of the system development process using analytical models. The requirements for performance evaluation of distributed software system are not only influenced by the question of when to conduct the evaluation and which method is appropriate for the obtaining performance results but also driven by the other requirements such as:

  1. Need for an efficient approach that will help to model the system functional behavior in a way that can reflect real system behavior so that performance evaluation can be meaningful afterwards.

  2. Deployment mapping is an integral part of the distributed software system development process which is defined by the assignment of software components in the physical resources that are distributed. For large and complex system it requires an efficient approach for handling the deployment mapping so that itcan also ensure the efficiency with respect to performance evaluation.

  3. Model that captures the system functional behavior will be used as an input model for developing the analytical model. So we need a mechanism that can also include the performance parameters to the input models for conducting the successful evaluation.

  4. Need for a scalable and efficient approach to establish the correspondence between the input model that will be utilized to capture the system functional behavior and the output model that will be used to conduct the performance evaluation of the distributed software system.

  5. At last, developing a tool based support for the whole process of performance evaluation considering above requirementswhich can ensure the rapid development, evaluation and user friendliness.

The following Figure 1 mentions the requirements or factors that we need to consider for the successful performance evaluation of the distributed software systems. In order to capture all the above mentioned factors, it needs an efficient approach or developing a framework that will allow rapid and successful performance evaluation of distributed software system which at the end reflects the aim of this chapter.

Figure 1.

Performance modeling framework

Advertisement

3. Performance modeling framework

We already mentioned our main objective in the previous section that will be presented broadly in this section. In order to achieve the main objective, we need to follow an engineering approach that will accelerate the distributed software system development process. We also need to define the method that will be accounted for evaluating the system performance. We limit ourselves to methods targeting system development process using the standards of UML (Unified Modeling Languages) [9]. In the evaluation side we limit ourselves to methods that will analytically solve our problem using the technique SPN (Stochastic Petri Nets). This section mainly presents these two main techniques and also focuses on their properties that will be utilized to design our performance modeling framework.

3.1. Capturing system functional behavior

We use UML collaboration as main specification unit to specify system functional behavior. The UML standard focuses in particular on the structural aspects of UML collaborations. UML does not, however, elaborate detailed semantics of the behavioral implications of the structural composition. Collaborations are intended as a context in which behaviors may be defined. Compared to the other uses of collaborations, and what we need, this is an obvious shortcoming. We will later see how a combination of collaborations with activities may solve this problem [9].

Collaboration is an illustration of the relationship and interaction among software objects in the UML. Objects are shown as rectangles with naming label inside. The relationships between the objects are shown as line connecting the rectangles [11]. As a representative example, we introduce a scenario description utilizing UML collaboration 2. Several users equipped with cell phone or smart phone want to receive weather information of their current location using his/her hand held device. The user request is first transferred to authentication server through base transceiver station to ensure the authenticity of the user. Thereafter, the request of the legitimate user is transferred to the locationserver to retrieve the location information of the user. The location information is then transferred to weather server for retrieving the weather information according to the location of the user. Figure 2 defines this scenario as UML 2 collaboration. Participants in the system are users, mobile terminals, base transceiver stations, authentication servers, location servers, weather servers which are represented by the collaboration roles user, MT, BTS, AuS, LS, and WS. The users are the part of the environment and therefore labeled as <<external>>.The default multiplicity of the users, mobile terminals, base transceiver stations, authentication servers, location servers, weather servers are one to many, which are denoted by (1..*). The interactions between the collaboration roles are represented by the collaboration such as mobile terminal and BTS interact through t: transfer, BTS and authentication server, location server, weather server interact successively through a: authenticate, l: request location info, w: request weather info, while the user interacts with the mobile terminal by collaboration g: generate request[6].

Figure 2.

Collaboration diagram

The specifications for collaborations are given as coherent, self-contained reusable building blocks. The internal behavior of building block is described by the UMLactivity. It is declared as the classifier behavior of the collaboration and has one activity partition for each collaboration role in the structural description [6]. For each collaboration, the activity declares a corresponding call behavior action refereeing to the activities of the employed building blocks. Depending on the number of participants, connectivity to other blocks and level of decomposition, we distinguish three different kinds of building blocks [10]:

  1. The most general building block is collaboration with two participants providing functionality that is intended to be composed with other functionality. We refer to such a building block as service collaboration.

  2. Building blocks that involve only local behavior of one participant are referred to as activity blocks. They are represented by activities.

  3. A special building block is system collaboration, which is collaboration on the highest composition level. In contrast to a service, a system is closed and cannot be composed with other building blocks.

Figure 3.

Activity diagram for expressing the internal behavior of collaboration

Hereby collaborations of Figure 2 are modeled by a call behavior action referring to the activity describing the behavior of the corresponding collaboration [10]. Activity diagram presents complete behavior in a quite compact form and may define connections to other behaviors via input and output pins [6]. Here we specify the behavior of one user request to show how the request is generated from his/her mobile terminal and served by the BTS, authentication server, location server and weather server and later on, composethis behavior to show how the requests will be processed by the BTS, authentication servers, location servers and weather servers so that the overall system behavior can be delineated. The activity transfer describes the behavior of the corresponding collaboration shown in Figure 3 (a). It has one partition for each collaboration role: mobile terminal (MT) and base transceiver station (BTS). Activities base their semantics on token flow [1]. The system starts by placing a token in the initial node of the mobile terminal when one request is generated by the user through his/her mobile terminal. The token is then transferred to the BTS where it moves through the fork node generating two flows. One flow places a token in the waiting decision node w which is the extension of a decision node with the difference that it may hold a token similar to an initial node, as defined in [1]. w is used in combination with join nodes j1 and j2 to explicitly model the acceptance or rejection of the user request based on the user authenticity. The other flow is forwarded as input to the authentication server to check whether the user is legitimate to generate service request. If the user is legitimate to generate the request a token is offered to the join node j1. If w still has its token j1 can fire which emits a token which then forwarded to the location server for further processing. If the user is not legitimate to generate the request, a token is offered to the join node j2. If w still has its token j2 can fire notifying the user upon the cancellation of request and then terminates the activity.

In order to validate the user identity (mobile number in this case) provided by a user who requests for service, BTS participates in the collaboration authenticate together with the authentication server. This is specified by collaboration a: authenticate where BTS plays the role of client and the authentication server plays the role of server. The behavior of the collaboration defined by the UML activity which is divided into two partitions, one for each collaboration role: client & server shown in Figure 3(b). The activity is started on the client side, when user id is provided as parameter u_id at the input pin. The input is then directly sent to the server, where it is converted into a database request in the call behavior action processing. Thereafter, it is the task of the collaboration between the server and the database to provide the stored user information. In order to get the information, the request leaves the activity authenticate and the server waits for the reception of the response. This is modeled with the input and output pins request and response. Depending on the validity of the user id, the server may decide to report ok or nok(not ok)to the client by the call behavior action validate. The result is then forwarded to the corresponding output pin in the client side and the activity is terminated. The semantics of all the pins are given in [12]. Likewise, we can describe the behavior of collaboration l: Request Location info ( shown in Figure 3(c)) and w: RequestWeather info through activity partition of client and server where BTS plays the role of client and location server and weather server play the role of server to deliver the requested information to the user through his/her mobile terminal.

The collaborative building blocks with help of activities specify overall system functional behavior which is introduced in Figure 4 for our scenario. For specifying detail behavior, UML collaborations and activities are used complementary to each other; UML collaborations focus on the role binding and structural aspect, while UML activities complement this by covering also the behavioral aspect for composition. For this purpose, call behavior actions are used. Each sub-service is represented by a call behavior action referring to the respective activity of the building blocks. Each call behavior action represents an instance of a building block. For each activity parameter node of the referred activity, a call behavior action declares a corresponding pin. Pins have the same symbol as activity parameter nodes to represent them on the frame of a call behavior action. Arbitrary logic between pins may be used to synchronize the building block events and transfer data between them. By connecting the individual input and output pins of the call behavior actions, the events occurring in different collaborations can be coupled with each other. There are different kinds of pins described as follows [10]:

  1. Starting pins activate the building block, which is the precondition of any internal behavior.

  2. Streaming pin may pass tokens throughout the active phase of the building block.

  3. Terminating pins mark the end of the block’s behavior. If collaboration is started and terminated via several alternative pins, they must belong to different parameter sets. This is visualized in UML diagram by an additional box around the corresponding node.

Figure 4 shows the activity diagram for our system to highlight the overall behavior of the system by composing all the building blocks. The initial node (∙) marks the starting of the activity. The activity is started on the client side. When a user service request is generated via mobile terminal, g: Generate request will transfer the user service request as parameter u_req to the BTS via collaboration t: Transfer. Once the request arrived at the BTS the user id as parameter u_id is transferred to the authentication server to check whether the user is authentic to accept the service and the activity is represented by a:authenticate. The activity authenticate initiates a database request, modeled by collaboration d1: DBRetrieve and terminates with one of the alternative results ok or nok. After arriving the positive response at the BTS, request for location information is forwarded to the location server represented by activity Request location info. Location server makes a database request which is modeled by d1: DBRetrieve and terminates with result l_info (Location information). After getting the location information, request for weather information according to user current location is forwarded by the BTS to the weather server represented by activity Request weather info. Weather server makes a database request which is modeled by d2: DBRetrieve and terminates with result w_info (Weather information). After that, the final result is transferred to the user hand held device by BTS via activity t: Transfer.But if the user is failed to prove his/her identity then immediately a nok is sent to the user’s hand held device.

So far, we introduced the system functional behavior with respect to specific example. Now we would like to introduce the specification in more generalized way. For example, the general structure of the building block tis given in Figure 5 where it only declares the participants A and B as collaboration roles and the connection between them is defined as collaboration use tx(x=1…nAB (number of collaborations between collaboration roles A and B)). The internal behavior of the same building block is shown in Figure6(b). The activity transferij(where ij = AB) describes the behavior of the corresponding collaboration. It has one activity partition for each collaboration role: A and B. Activities base their semantics on token flow [1]. The activity starts by placing a token when there is a response (indicated by the streaming pin res) to transfer by either participant A or B. After completion of the processing by the collaboration role A and B the token is transferred from the participant A to participant B and from participant B to Participant A which is represented by the call behavior action forward.

Figure 4.

Activity diagram for detail system behavior

Figure 5.

Collaboration diagram in generalized way

The detailed behavior of collaboration is given in following Figure6(a). The initial node (∙) indicates the starting of the activity. The activity is started at the same time from each participant A and B. After being activated, each participant starts its processing of the request which is mentioned by call behavior action Pi(Processingi, where i = A, B). Completions of the processing by the participants are mentioned by the call behavior action di(Processing_donei, i = A, B). After completion of the processing, the responses are delivered to the corresponding participants indicated by the streaming pin res. The response of the collaboration role A will be forwarded to B and vice versa which is mentioned by collaboration t: transferij (where ij = AB).

Figure 6.

a) Detail behavior of collaborative building block (b).Internal behavior of collaboration

3.2. Method for efficient Deployment mapping

Deployment diagram can be used to define the execution architecture of the system by identifying the system physical components and the assignment of software artifacts to those identified physical components [11]. After designing the deployment diagram the relation between system component and collaboration will be delineated to describe the service delivered by the system. The service is delivered by the joint behavior of the system components which may be physically distributed. The necessary partial behavior of the component used to realize the collaboration is represented by the collaboration role. In this way, it is possible to expose direct mapping between the collaboration roles to the system components to show the probable deployment of service components to the physical nodes of the system [6].

We consider two design alternatives of system architecture captured by UML deployment diagram to demonstrate the relationship between collaboration and system component for the scenario mentioned in Figure 2. For our defined scenario the identified system components by the 1st variation of deployment diagram are Mobile terminal, Base transceiver station, Authentication server, Location server and Weather server. After designing the deployment diagram the relationship between system component and collaboration will be delineated to describe the service delivered by the system. The service is delivered by the joint behavior of system components which may be physically distributed. The necessary partial behavior of the components used to realize the collaboration is represented by the collaboration role.Behavior of the components Mobile terminal, Base transceiver station, Authentication server, Location server, Weather server are represented by the collaboration roles MT, BTS, AuS, LS & WS to utilize the collaboration t: transfer, a: authenticate, l: request location info, w: request weather info. Here it is one to one mapping between system component & collaboration role shown in Figure 7(a).

We consider other variation of deployment diagram for mentioned scenario. In this variation of deployment diagram the identified system components are mobile terminal, Base transceiver station, application server. In this case,the behavior of the components Mobile terminal and Base transceiver station is represented by the collaboration roles MT and BTS to utilize the collaboration t: transfer and the behavior of the component application behavior is represented jointly by the collaboration role AuS, LS and WS to utilize the collaboration a: authenticate, l: request location info, w: request weather info. In second case, the mapping between system component & collaboration role is generalized into one to many relations mentioned in Figure 7(b).

Figure 7.

UML deployment diagram with service components deployment mapping

For large and complex system, conducting the deployment mapping is not straight forward like the previous cases. The deployment mapping has implication with respect to satisfying the non functional properties of the system. So we need for an approach that will be apposite for conducting the deployment mapping for complex system considering constraints and capabilities of the system components. We introduce our approach by considering the system as collection of N interconnected nodes. Our objective is to find a deployment mapping for this execution environment for a set of service components C available for deployment that comprises the service. Deployment mapping M can be defined as(M:CN)between a numbers of service components instances c, onto nodes n mentioned in Figure 8. A components ciC can be a client process or a service process, while a node, nN is a physical resource. Generally, nodes can have different responsibilities, such as providing services (S1), relaying traffic (R1), accommodating clients (C1), or a mixture of these (SC1). Components can communicate via a set of collaborations. We consider 3 types of requirements in the deployment problem where the term cost is introduced to capture several non-functional requirements those are later on utilized to conduct performance evaluation of the systems:

  1. Components have execution costs

  2. Collaborations have communication costs and costs for running of background process known as overhead cost

  3. Some of the components can be restricted in the deployment mapping to specific nodes which are called bound components.

Figure 8.

Service component mapping example

Furthermore, we consider identical nodes that are interconnected each other and are capable of hosting components with unlimited processing demand. We observe the processing cost that nodes impose while host the components and also the target balancing of cost among the nodes available in the network. Communication costs are considered if collaboration between two components happens remotely, i.e. it happens between two nodes [15]. In other words, if two components are placed onto the same node the communication cost between them will not be considered. The cost for executing the background process for conducting the communication between the collaboration roles is always considerable no matter whether the collaboration roles deploy on the same or different nodes. Using the above specified input, the deployment logic provides an optimal deployment architecture taking into account the QoS requirements for the components providing the specified services. We then define the objective of the deployment logic as obtaining an efficient (low-cost, if possible optimum) mapping of components onto the nodes that satisfies the requirements in reasonable time. The deployment logic providing optimal deployment architecture is guided by the cost function F(M). The cost function is designed here to reflect the goal of balancing the execution cost and minimizing the communications cost. This is in turn utilized to achieve reduced task turnaround time by maximizing the utilization of resources while minimizing any communication between processing nodes. That will offer a high system throughput, taking into account the expected execution and inter-node communication requirements of the service components on the given hardware architecture. The evaluation of cost function F(M) is mainly influenced by our way of service definition. Service is defined in our approach as a collaboration of total E components labeled as ci (where i = 1…. E) to be deployed and total K collaborations between them labeled as kj, (where j = 1 … K). The execution cost of each service component can be labeled as fci; the communication cost between the service components is labeled as fkj and the cost for executing the backgroundprocess for conducting the communication between the service components is labeled as fBj. Accordingly,we only observe the total cost (l^n, n = 1…X)ofa given deployment mapping at each node where X defines the total number of physical nodes availablein the execution environment. We will strive for an optimal solution of equally distributed cost among the processing nodes and the lowest cost possible, while taking into account the execution cost fci, i = 1….E, communication cost fkj, j = 1….K and cost for executing the background process fBj, j = 1….k. fci, fkj and fBj are derived from the service specification, thus the offered execution cost can be calculated asi=1|E|fci. This way, the logic can be aware of the target cost T [15]:

T=1|X|i=1|E|fciE1

To cater for the communication cost fkj, of the collaboration kj in the service, the function q0(M, c) is defined first [15]:

q0(M,c)={nN|(cn)M}E2

This means thatq0(M,c)returns the node nthat hosts componentsin the list mapping M. Let collaborationkj=(c1,c2). The communication cost of kj is 0 if components c1 and c2 are collocated, i.e.q0(M,c1)=q0(M,c2), and the cost is fkjif components are otherwise (i.e. the collaboration is remote). Using an indicator function I(x), which is 1 if x is true and 0 otherwise, this expressed asI(q0(M,c1)q0(M,c2))=1, if the collaboration is remote and 0 otherwise. In order to determine which collaboration kjis remote, the set of mapping M is used. Given the indicator function, the overall communication cost of service, Fk(M), is the sum [15]:

Fk(M)=j=1|k|I(q0(M,Kj,1)q0(M,Kj,2))fkjE3

Given a mapping M = {mn}(where mn is the set of components at node n& nϵ N) the total load can be obtained asl^n=cimnfci. Furthermore the overall cost function F(M) becomes (where Ij= 1, if kj external or 0 if kj internal to a node) [15]:

F(M)=n=1|N||l^nT|+Fk(M)+j=1|k|fBjE4

3.3. Approach for incorporating performance information

UML is no doubt a well established language for modeling system functional behavior. But UML has lacking of incorporating non functional parameters in the model while specifying the functional behavior of any system. This needs for an approach or specification to incorporate the performance parameters in the UML for quantitative analysis. That’s why we use a specification called the UML profile for MARTE for Modeling and Analysis of Real-Time and Embedded systems, provides support for specification, design, and verification/validation stages [1]. This new profile is intended to replace the existing UML Profile for Schedulability, Performance and Time. This specification of a UML profile adds capabilities to UML for model-driven development of Real Time and Embedded Systems (RTES) [1].

MARTE defines foundations for model-based descriptions of real time and embedded systems. These core concepts are then refined for both modeling and analyzing concerns. Modeling parts provides support required from specification to detailed design of real-time and embedded characteristics of systems. MARTE concerns also model-based analysis. In this sense, the intent is not to define new techniques for analyzing real-time and embedded systems, but to support them. Hence, it provides facilities to annotate models with information required to perform specific analysis. Especially, MARTE focuses on performance and schedulability analysis. But it defines also a general analysis framework that intends to refine/specialize any other kind of analysis. Among others, the benefits of using this profile are thus [1]:

  1. Providing a common way of modeling both hardware and software aspects of an RTES in order to improve communication between developers.

  2. Enabling interoperability between development tools used for specification, design, verification, code generation, etc.

  3. Fostering the construction of models that may be used to make quantitative predictions regarding real-time and embedded features of systems taking into account both hardware and software characteristics.

We apply several stereotypes of MARTE that permit us to map model elements into the semantics of an analysis domain such as schedulability, and give values for properties that are needed in order to carry out the analysis [1]. Specific tagged values are also applied. Tagged values are a kind of value slots associated with attributes of specific UML stereotypes [1]. In order to annotate the UML diagram we use several stereotypes and tag values according to the UML profile for MARTE. The stereotypes are the following [1]:

  1. saStepis a kind of step that begins and ends when decisions about the allocation of system resources are made.

  2. ComputingResourcerepresents either virtual or physical processing devices capable of storing and executing program code. Hence its fundamental service is to compute.

  3. Scheduler is defined a kind of ResourceBroker that brings access to its brokered ProcessingResource or resources following a certain scheduling policy mentioned by tag value schedPolicy. The ResourceBroker is a kind of resource that is responsible for allocation and de-allocation of a set of resource instances (or their services) to clients according to a specific access control policy [1].

The tagged values are the following [1]:

  1. execTime:The duration of the execution time is mentioned by the tagged value execTimewhich is the average time in our case.The execution cost of service component is expressed by this tagged value in the annotated UML model that is later on used by the performance model to conduct the performance evaluation.

  2. deadlinedefines the maximum time bound on the completion of the particular execution segment that must be met. The overhead cost and communication cost between the service components are specified by this tagged value in the annotated UML model that is later on used as well by the performance model to conduct the performance evaluation.

3.4. Scalable and automated model transformation

We already mentioned that SPN model will be generated as analytical model from the UML specification style to conduct the performance evaluation. This needs for an efficient, scalable and automated approach to conduct the model transformation for large, complex and multifaceted distributed system. In this literature, the approach for efficient model transformation is realized by producing model transformation rules that can be applied in generalized way for various application domains. As we generate SPN model as analytical model we will give a brief introduction about SPN model. SPN model has the following elements: Finite set of the places (drawn as circles), finite set of the transition defined as either timed transition (drawn as thick transparent bar) or immediate transition (drawn as thin black bar), set of arcs connecting places and transition, multiplicity associated with the arcs, marking that denotes the number of token in each place. SPN model is mentioned formally by the 6-tuple {Φ, T, A, K, N, m0}:

Φ = Finite set of the places

T = Finite set of the transition

A{Φ × T} {T × Φ} is a set of arcs connecting Φ and T

K: T → {Timed (time>0), Immediate (time = 0)} specifies the type of the each transition

N: A→ {1, 2, 3…} is the multiplicity associated with the arcs in A

m: Φ → {0, 1, 2...} is the marking that denotes the number of tokens for each place in Φ. The initial marking is denoted as m0.

By utilizing the above formal representation of the SPN model, we initiate the model transformation rules that will generate SPN model from UML collaboration and activity oriented approach that captures the system functional behavior. The model transformation rules are the following:

Rule 1: The SPN model of a collaboration role is represented by the 6-tuple in the following way:

Φ= {Pi, di}

T = {do, exit}

A = {{(Pi × do) (do × di)}, {(di × exit) (exit × Pi)}}

K = (do → Timed, exit → Immediate)

N = {(Pi × do) →1, (do × di) →1, (di × exit) →1, (exit × Pi)→1}

mo= {(Pi→1}, (di →0)}

Figure 9.

Modeltransformationrule 1

SPN model of a collaboration role is mentioned in Figure 9 (where Pi = Processing of ith collaboration role and di = Processing done of the ith collaboration role).

Rule 2: Whenthe collaboration role of a building block deploys onto a physical node the equivalent SPN model is represented by 6-tuple in following way:

Φ= {Pi, di, PPn}

T= {do, exit}

A = {{(Pi × do) (do × di)}, {(PPn × do) (do × PPn)}, {(di × exit) (exit × Pi)}}

K = (do → Timed, exit → Immediate)

N= {(Pi × do) →1, (do × di) →1, (PPn × do) →1, (do × PPn) →1(di × exit) →1, (exit × Pi)→1}

mo= {(Pi→1}, (di →0), (PPn→q)}

Initially place PPncontains q (where integer q> 0) tokens which define the upper bound of the execution of the process in parallel by a physical node n and the timed transition do will fire only when there is a token available in both the place Pi and PPn. The place PPn will again get back it’s token after firing of the timed transition do indicating that the node is ready to execute other processes deployed on that physical node. The equivalent SPN model when a collaboration role deploy on a physical node is mentioned in Figure 10:

Figure 10.

Modeltransformationrule 2

Rule 3: The SPN model of a collaboration where collaboration connects only two collaboration roles those deploy on the same physical node can be represented by the 6-tuple in the following way in Figure 11:

Φ= {Pi, di, Pj,djPPn}

T= {doi, doj,tij}

A = {(Pi × doi) (doi × di), (PPn × doi) (doi × PPn), (di × tij) (tij × Pi), (Pj × doj) (doj × dj), (PPn × doj) (doj × PPn), (dj × tij) (tij × Pj)}

K = {(doi, doj, tij) → Timed}

N= {((Pi × doi), (doi× di), (PPn × doi), (doi × PPn), (di × tij), (tij × Pi), (Pj × doj), (doij× dj), (PPn × doj), (doj × PPn), (dj × tij), (tij × Pj)) →1}

mo= {(Pi→1), (di →0), (Pj→1) (dj→0), (PPn→q)}

Here timed transition tij in the SPN model is only realized by the overhead cost as service components i and j deploy on the same physical node which makes the communication cost = 0.

Figure 11.

Modeltransformationrule 3

The SPN model of a collaboration where collaboration connects only two collaboration roles those deploy on the different physical node can be represented by the 6-tuple in the following way in Figure 11:

Φ= {Pi, di, Pj,djPPn, PPm}

T= {doi, doj,tij}

A = {(Pi × doi) (doi × di), (PPn × doi) (doi × PPn), (di × tij) (tij × Pi), (Pj × doj) (doj × dj), (PPm × doj) (doj × PPm), (dj × tij) (tij × Pj)}

K = {(doi, doj, tij) → Timed}

N= {((Pi × doi), (doi× di), (PPn × doi), (doi × PPn), (di × tij), (tij × Pi), (Pj × doj), (doij× dj), (PPm × doj), (doj × PPm), (dj × tij), (tij × Pj)) →1}

mo= {(Pi→1), (di →0), (Pj→1), (dj→0), (PPn→q), (PPm→q)}

Here timed transition tij in the SPN model is realized by both the overhead cost and communication cost as service components iand j deploy on the different physical node.

3.5. Performance model Evaluation

We focus on measuring the throughput of the system from the developed SPN model. We are interested in throughput calculation as a measure of job that a system can process in a given time period which in turn justify the efficiency of our deployment logic mentioned in section 3.2 in accordance with system performance evaluation. Before deriving formula for throughput estimation, we consider several assumptions that will allow us to determine the parameters necessary for the throughput calculation of our system.

  1. Executions of the processes occur independently each other.

  2. All the communications occur in parallel.

  3. Finally the communications between interconnected nodes will be started following the completion of all the processing and communication inside each physical node.

The above assumption is important for retrieving the parameters necessary for the throughput calculation from our system specification. We define the throughput as function of expected number of jobs in the system, E(N) and cost of the network, C_Net which defines the time required to complete the expected number of jobs in the system. The value of E(N) is calculated by solving the SPN model using SHARPE [16]. Cost of the network, C_Net is defined in the following: First the cost of a subnet (Csn) will be calculated as follows:

Csnx=i=1|m|fci+max{fBj}+Fk(M)=i=1|m|fci+max{fBj}E5

Here:

  • Csnx = cost of the xth subnet (where x = 1….n; n is the total number of subnet that comprises the network)

  • fci= execution cost of the ith process of the xth subnet

  • m = total number of service components deployed on the xth subnet

  • fBj = overhead cost of collaboration j (where j =1….n; n is the total number of collaboration in the xth subnet)

  • fkj = communication cost of collaboration j (where j =1….n; n is the total number of collaboration in the xth subnet)

  • Fk(M) = 0 (defined in section 3.2.); as in this case processes connected by the collaboration deploy on the same physical node

Now we evaluate the cost between each pair of subnet with respect to the subnet’s own processing cost, overhead cost and the cost associated with the communication with other subnet in the network.

Csnpx={max(Csni,Csnj)}+fBj+Fk(M)}E6

Here:

  • Csnpy = cost of the yth subnet pair (y = 1….n; n is the total number of subnet pair in the network where each subnet pair corresponds between two subnets)

  • Csni, Csni= cost of the ith and jth subnet (where (i, j) ϵ x and i≠j)

  • Fk(M) = 1 (defined in section 3.2.2); as in this case processes connected by the collaboration deploy on the different physical nodes

C_Net=max{Csnp1,....,....,Csnpn}E7
Throughput=E(N)C_NetE8
Advertisement

4. Case study

As a representative example, we consider the scenario dealing with heuristically clustering of modules and assignment of clusters to nodes [15, 17]. This scenario is sufficiently complex to show the applicability of our performance modeling framework. The problem is defined in our approach as a service of collaboration of E = 10 components or collaboration roles (labeledC1... C10) to be deployed and K = 14 collaborations between them depicted in Figure 12. We consider three types of requirements in this specification. Besides the execution cost, communication cost and overhead cost, we have a restriction on components C2, C7, C9 regarding their location. They must be bound to nodes n2, n1, n3, respectively. The internal behavior of the collaboration Ki of our example scenario is realized by the call behavior action through same UML activity diagram mentioned in Figure 6(b). The detail behavior of the collaboration role C is realized through same UML activity diagram already illustrated in Figure 6(a). However, there is no behaviormodeled in detail, only that collaboration between processes deployed on different physical nodes. The UML collaboration diagram can be modeled by the activity that may model the detail behavior but the level of details must be selected with care in order for the model to scale while generating the performance model.

In this example, the target environment consists only of N = 3 identical, interconnected nodes with a single provided property, namely processing power and with infinite communication capacities depicted in Figure 13. The optimal deployment mapping can be observed in Table. 1. The lowest possible deployment cost, according to equation (4) is 17 + 100 +70 = 187 [15, 17].

Figure 12.

Collaborations and components in the example scenario

Figure 13.

The target network of hosts

Figure 14.

Annotated UML model

In order to annotate the UML diagram in Figure 12 and 13 we use the stereotypessaStep, computingResource, scheduler and the tag values execTime, deadline and schedPolicy which are already described in section 3.3. Collaboration Ki is associated with two instances of deadline (Figure 14)as collaborations in example scenario are associated with two kinds of cost: communication cost and overhead cost.

NodeComponentsln| ln – T |Internal collaborations
n1c4, c7, c8702k8, k9
n2c2, c3, c5608k3, k4
n3c1, c6, c9, c10757k11, k12, k14
∑ cost17100
117

Table 1.

Optimal deployment mapping in the example scenario [15, 17]

By considering the above deployment mapping and the transformation rules, the corresponding SPN model of our example scenario is depicted in Figure 15. Figure 15sketches the resulting SPN model by illustrating details of all the places and transitions.According to the transformation rule 1, each collaboration role is defined by the two places Piand diand the passing of token from placePi to diis realized by the timed transition tiwhich is derived from the annotated UML model. Initially, there will be a token from place P1 to P10. According to rule 2, in order to define the upper bound of the execution of parallel processes by a network node, we introduce three places PP1, PP2 and PP3 in the SPN modelfor the corresponding three physical nodes and initially, these three places will contain q (q> 0) tokens where qwill define the maximum number of the process that will be handled in parallel by a physical node at certain time. In order to ensure the upper bound of the parallel processing of a network node n1, we introduce arcs from place PP1 to transition t4, t7and t8. That means, components C4, C7 and C8can start their processing if there is token available in place PP1 as the firing of transitions t4, t7 and t8not onlydepend on the availability of the token in the place P4, P7 and P8but also depend on the availability of the token in the place PP1. Likewise, to ensure the upper bound of the parallel processing of a network node n2 and n3,we introduce arcs from place PP2 to transition t2, t3and t5 and from place PP3 to transition t1, t6, t9, t10.

Figure 15.

SPN model of our example scenario

For generating the SPN model from annotated UML model, firstly, we will consider the collaboration roles deploy on the processor node n1which are C4, C7 and C8. Here components C7 connects to C4 and C8. The communication cost between the components is zero but there is still cost for execution of the background process. So according to rule 3, after the completion of the transition from place P7 to d7 (places of component C7), from P4 to d4 (places of component C4) and from P8 to d8 (places of component C8) the places d7, d4 and d7, d8 are connected by the timed transition k8and k9to generate the SPN model. Collaboration roles C2, C3and C5 deploy on the processor node n2. Likewise, after the completion of the transition from place P2 to d2 (places of component C2), from P3 to d3(places of component C3) and from P5 to d5 (places of component C5) the places d2, d3 and d2, d5 are connected by the timed transition k3 and k4 to generate the SPN model according to rule 3. Collaboration roles C6, C1, C9and C10 deploy on the processor node n3. In the same way, after the completion of the transition from place P1 to d1(places of component C1), from P6 to d6(places of component C6), P9to d9 (places of component C9) and from P10 to d10 (places of component C10) the places d1, d6; d1, d9 andd9, d10 are connected by the timed transition k11, k12 and K14 to generate the SPN model following rule 3. In order to generate the system level SPN model we need to combine the entire three SPN model generated for three processor nodes by considering the interconnection among them. In order to compose the SPN models of processor node n1 and n2, places d4 and d3 are connected by the timed transition k1and places d4and d5 are connected by the timed transition k2 according to rule 3. Likewise, to compose the SPN models of processor node n2 and n3, places d2 and d1 areconnected by the timed transition k5 and places d5 and d1 are connected by the timed transition k6 according to rule 3. In order to compose the SPN models of processor node n1 and n3, places d7 and d1 are connected by the timed transition k7, places d8 and d6 are connected by the timed transition k10 and places d8 and d9 are connected by the timed transition k13 according to rule 3. By the above way, the system level SPN model is derived and all these are done automatically. The algorithm for automatic generation of SPN model from the annotated UML model is beyond the scope of this chapter.

The throughput calculation according to equation (8) for the different deployment mapping including the optimal deployment mapping is shown in Table2. The optimal deployment mapping presented in Table 1 (first entry) also ensures the optimality in case of throughput calculation though we present here the throughput calculation of some of the deployment mappings of the software artifacts but obviously, the approach presented here confirms the optimality.

Deployment MappingPossible total costThroughput
n1n2n3
{c4, c7, c8}{c2, c3, c5}{c1, c6, c9, c10}187 (min)0.0663 (max)
{ c4, c7},{c2, c3, c5, c6,}{c1, c8, c9, c10}2320.0603
{c4, c6, c7, c8}{c2, c3, c5}{c1, c9, c10}2180.0575
{c5, c7, c8}{c2, c3, c4}{ c1, c6, c9, c10}2270.0574
{c1, c6, c7, c8}{c2, c3, c4}{c5, c9, c10}2470.0545
{ c3, c7, c8}{c2, c4,c5}{c1, c6, c9, c10}2520.0538
{c4, c7, c8}{ c1, c2, c3, c5}{ c6, c9, c10}2170.0532
{ c1, c6, c7, c8}{c2, c3, c5}{ c4, c9, c10}}2570.052
{c3, c6, c7, c8}{c1, c2, c4, c5},{c9, c10}3020.0469
{c6, c7, c8}{ c1, c2, c4, c5}{c3, c9, c10}}2880.0464

Table 2.

Deployment mapping in the example scenario along with throughput

Advertisement

5. Conclusion

The contribution of this chapter is to develop a framework that focuses on the performance evaluation of the distributed system using SPN model. The developed framework recognizes the fact of rapid and efficient way of capturing the system dynamics utilizing reusable specification of software components that has been utilized to generate SPN performance model. The deployment logic presented here, is applied to provide the optimal, initial mapping of components to hosts, i.e. the network is considered rather static. Performance related QoS information is taken into account and included in the SPN model with equivalent timing and probabilistic assumption for enabling the evaluation of performance prediction result of the system at the early stage of the system development process. However, our eventual goal is to develop support for run-time redeployment of components, this way keeping the service within an allowed region of parameters defined by the requirements. Our modeling framework support that, our logic will be a prominent candidate for a robust and adaptive service execution platform for assessing a deployment of service components on an existing physical topology. Future work includes providing a tool based support of the developed performance modeling framework.

References

  1. 1. OMG2009UML Profile for MARTE: Modeling& Analysis of Real-Time Embedded Systems”, 1
  2. 2. LopezJ. P.MerseguerJ.CamposJ.From“.ActivityU. M. L.Diagramsto. S. P. N.Applicationto.SoftwarePerformance.Engineering”Workshop.onSoftware.PerformanceA. C. M. S. I. G. S. O. F. T.softwareengineering.notespp.2536NY, 2004
  3. 3. DistefanoS.ScarpaM.PuliafitoA.Software“.PerformanceAnalysis.inU. M. L.Models”Workshop.onTechniques.MethodologiesToolsfor.PerformanceEvaluation.ofComplex.SystemsVol.2005115125
  4. 4. D’AmbrogioA.Model“. A.TransformationFramework.forthe.AutomatedBuilding.ofPerformance.Modelsfrom. U. M. L.Models”Workshop.onSoftware.PerformanceA. C. M. S. I. G. S. O. F. T.softwareengineering.notesN. Y.2005
  5. 5. KhanR. H.HeegaardP. E.Translation“.fromU. M. L.toS. P. N.modelA.PerformanceModeling.Framework”E. U. N. I. C. E.pp27027 .L. N. C. S.Springer, 2010
  6. 6. KhanR. H.HeegaardP. E.Translation“.fromU. M. L.toS. P. N.modelA.PerformanceModeling.Frameworkfor.ManagingBehavior.ofMultiple.CollaborativeSessions.Instances”I. C. C. D. A.ppV5-7.5-72V5-80, IEEE computer Society, China, 2010
  7. 7. KhanR. H.HeegaardP. E.Performance“. A.ModelingFramework.IncorporatingCost.EfficientDeployment.ofCollaborating.Components”I. C. S. T. E.ppV1-34.1-340V1-349, IEEE computer Society, San Juan, USA, 2010
  8. 8. Moreno Marzolla, “Simulation-based Performance Modeling of UML Software Architectures”, PhD thesis, Universit`aCa’ Foscari di Venezia, 2004
  9. 9. Frank Kræmer, “Engineering System: A Compositional and Mode-Driven Method Based on Collaborative Building block”, PhD Thesis, NTNU, Trondheim, Norway, 2008
  10. 10. KramerF. A.BrækR.HerrmannP.Synthesizes“.Componentswith.Sessionsfrom.Collaboration-orientedService.Specifications”Proceedings.ofS. D. L.V-474SpringerL. N. C. S.2007
  11. 11. OMG UMLSuperstructure, Version-2.2
  12. 12. KhanR. H.HeegaardP. E.Performance“. A.ModelingFramework.IncorporatingCost.EfficientDeployment.ofMultiple.CollaboratingInstances”. I. C. S. E. C. S.pp3145Springer, 2011
  13. 13. J. Trowitzsch, A. Zimmermann, “Using UML State Machines and Petri Nets for the Quantitative Investigation of ETCS”, Valuetools, 2006
  14. 14. AbdullatifR.Pooly“. A.ComputerAssisted.StateMarking.Methodfor.ExtractingPerformance.Modelsfrom.DesignModels”.InternationalJournal.ofSimulation.Vol336462008
  15. 15. Mate J Csorba, “Cost Efficient Deployment of Distributed Software Services”, PhD Thesis, NTNU, Norway, 2011
  16. 16. K. S. Trivedi and R Sahner, “Symbolic Hierarchical Automated Reliability / Performance Evaluator (SHARPE)”, Duke University, NC, 2002
  17. 17. Efe, K.,“Heuristic Models of Task Assignment Scheduling in Distributed Systems”, Computer,1982

Written By

Razib Hayat Khan, Poul E. Heegaard and Kazi Wali Ullah

Submitted: 02 February 2012 Published: 29 August 2012