Andrzej Ratkowski
email: a.ratkowski@elka.pw.edu.pl

Andrzej Zalewski
email: a.zalewski@ia.pw.edu.pl

Transformational Design of Business Processes for SOA

Keywords: SOA, BPEL, business process design

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The ability to define and execute business processes seems to be one of the most important advantages introduced by the research and commercial developments on Service-Oriented Architectures (SOA). The two worlds of business modeling and software systems development have never been closer to each other -it is now possible to express software requirements and business processes in terms of services. BPEL has become a standard for defining executable business processes. This in turn triggered an extensive research on the modeling and verification techniques suitable for BPEL-like notations.

The recent research is concentrated on converting BPEL processes to one of the formal models that can be analysed with model-checking techniques. A survey of such approaches can be found in [START_REF] Koshkina | Models and verification of bpel[END_REF]. It reveals that all the most important formal modeling techniques developed for concurrent systems are applicable here: Petri nets (basic model, high-level, coloured) -(see e.g. [START_REF] Hinz | Transforming BPEL to Petri Nets[END_REF], [START_REF] Ouyang | Formal semantics and analysis of control flow in ws-bpel[END_REF], [START_REF] Yang | Transformation bpel to cp-nets for verifying web services composition[END_REF]), Process Algebras -(see e.g. [START_REF] Foster | Using a rigorous approach for engineering web service compositions: A case study[END_REF], [START_REF] Foster | Model-based verification of web service compositions[END_REF]), Lotos -(see e.g. [START_REF] Ferrara | Web services: a process algebra approach[END_REF], [START_REF] Salaün | Negotiation among web services using lotos/cadp[END_REF]), Promela and LTL -(see e.g. [START_REF] Fu | Analysis of interacting bpel web services[END_REF], [START_REF] Holzmann | The SPIN Model Checker : Primer and Reference Manual[END_REF]), Abstract State Machines -(see e.g. [START_REF] Fahland | Asm-based semantics for bpel: The negative control flow[END_REF], [START_REF] Reisig | Modeling and Analysis Techniques for Web Services and Business Processes[END_REF]), Finite State Automata -(see e.g. [START_REF] Foster | Model-based verification of web service compositions[END_REF]). These conversions make possible deadlock and livelock detection as well as reachability analysis with automated model checkers.

The approaches presented above accompanied by appropriate verification techniques can detect certain flows in BPEL processes. However, they are not methods of business processes design -they do not provide any guidance on how to improve the quality attributes of designed systems like maintainability, performance, reusability etc. This is what our approach is aimed at.

In this paper we advocate an idea of transformational design of BPEL business processes in which specified behavior remains preserved, while quality attributes get improved. There are three basic roots of our approach:

1. Software refactoring -the approach introduced by Opdyke in [START_REF] William | Refactoring Object-Oriented Frameworks[END_REF], further developed in [START_REF] Martin | Refactoring: improving the design of existing code[END_REF], in which the transformations of source code are defined so as to improve its quality attributes; 2. Business process design -in the realm of SOA informal or semiformal methods dominate the research carried out so far -e.g. Service Responsibility and Interaction Design Method (SRI-DM) [START_REF] Hofacker | Algorithmical approaches to business process design[END_REF]; 3. Business process equivalence -there have already been developed several notions of the equivalence between business processes based on Petri Nets [START_REF] Martens | Simulation and equivalence between bpel process models[END_REF] and Process Algebras [START_REF] Salaün | Describing and reasoning on web services using process algebra[END_REF].

The transformations of Business Processes are in the core of our approach and represent similar concept as popular software refactorings. In a formal Process Algebra model of business processes there have been introduced our original notion of business process equivalence (explained and discussed in section Behavioral Equivalence) and it has been proved that the defined transformations create processes equivalent to the one being transformed. These transformed processes are compliant in terms of their behavior, however, quality attributes have changed.

This provides a foundation for the transformational design method in which a starting BPEL process is subject to a series of transformations yielding as a result behaviorally compatible model with improved non-functional properties like modifiability, maintainability, performance, reusability etc.

The rest of the paper has been organized as follows: the section Transformational Approach describes generally concept of our transformational approach, sections Behavioral Equivalence drills down formal aspects of our method, finally section Process Design Example shows practical example of the application of the proposed approach.

Transformational Approach

The process of transformational design of business processes has been depicted in figure 1.

1. The transformational desing starts from establishing reference process representing only functionality of the process, order of the activities, relations between them as well as exchanged data and external services invocations. In following iterations the original process is gradually changed by refactoring transformations [START_REF] Ratkowski | Performance refactoring for service oriented architecture[END_REF], [START_REF] Martin | Refactoring: improving the design of existing code[END_REF] like:

-Service split -dividing one complex services into two or more more simple ones, -Service aggregation -opposite to service split: composing two or more services into one larger, -Parallelization -making serial activities to run in parallel, -Asynchronization -replacing synchronous communication protocol with asynchronous one. The above transformations are referred to as refactorings or transformations and are only examples of possible refactorings. 2. A few independent refactorings or transformations executed on a given process create a few alternative processes, which should be equivalent to the original one or at least changes in behaviour should be known. 3. Behavioral equivalence verification step is aimed at checking behaviour preservation. In this step formal methods of Process Algebra (PA) [START_REF] Cleaveland | Process algebra[END_REF] are used. The result of verification is either elimination of not-equivalent alternative or acceptance of changes in behaviour that transformations caused. The transformation changes behaviour is exactly known thanks to PA formalism. 4. After eliminating some of the alternatives or accepting all of them, alternatives are evaluated against non-functional properties like:

performance, -safety, -maintainability, -availability, -or any important property. The measure of each property is calculated e.g. with the metrics [START_REF] Everald | Software metrics[END_REF], models [START_REF] Ambrogio | A model-driven approach to describe and predict the performance of composite services[END_REF] or simulation. 5. A single alternative is selected from the set of acceptable processes. This is based on the evaluation performed in the previous phase as well as the predefined desing preferences.

The above steps should lead from the process, which is correct from functional point of view, to the process that has desired non-functional quality attributes.

All steps of algorithm are guided by a human designer and supported by automatic tools that may:

-Suggest possible transformations of reference process, -Verify behavioral equivalence, -Compute quality metrics of alternatives, -Point out quality attribute trade-off points.

Behavioral Equivalence

Behavioral equivalence verification is based on the transformation of BPEL processes to Process Algebras [START_REF] Cleaveland | Process algebra[END_REF], which is a formal model, particularly suitable for the modeling of concurrent, loosely coupled and asynchronously communicating systems such as BPEL business processes.

Process Algebra for Behavioral Equivalence

We use LOTOS [START_REF] Bolognesi | Introduction to the iso specification language lotos[END_REF] implementation of PA as a model of BPEL process. To achieve this we have devised a mapping from BPEL to PA terms. There have already been proposed a number of BPEL to PA mappings -e.g. [START_REF] Ferrara | Web services: a process algebra approach[END_REF] or [START_REF] Cámara | Formalizing wsbpel business processes using process algebra[END_REF], however, they do not meet the needs of transformational design as they define full semantic equivalence preserving every detail of the internal structure of the process (i.e. the order of activities and their relation with other activities). This strictness narrows the possibility of changing the process structure or even makes it impossible. Therefore, we need a looser equivalence definition to assure that enough freedom is given to the trasformation of business processes.

A separate issue is that transformations should produce simple models with possibly smallest statespace (the mappings referred above produce rather complicated models). During design procedure a few alternative process structures are considered and the equivalence of each of them has to be verified -this in turn should not be too time-consuming if the method is expected to be of a practical importance.

Most important mappings of BPEL activities to PA formulas have been presented in table 1.

The mappings neither take into account data values nor condition fulfillment. This is motivated by simplicity of the model and its more efficient verification with a model-checker.

There has also been added an artificial mapping of activity which is not explicit part of BPEL but is necessary for equivalence verification. This is activity dependency mapping. Let us assume that there are two activities in BPEL process that are not directly attached to each other (by e.g. <sequence> or <switch>) but by shared variable, like in the following example: <receive variable="PurchaseOrder" name="ReceivePurchase" /> ... <assign name="assignOrder"> <copy> <from variable="PurchaseOrder"/> The activity dependency expresses indirect dependency of two activities that one needs output data from another, no matter what structural dependencies (sequence or parallel) in the process are.

BPEL Behavioral Equivalence

The key structure of our definition of behavioral equivalence is minimal dependency process (MDP). MDP is the process that is as simple as possible but still gives the same response for given stimulation as original process. MDP is constructed as set of activities executed in parallel that do not interact with each other. It is achieved by relaxing unnecessary structural activities that are in the original process. Current section supplies theoretical basis for the construction of MDP and the evidence that it can be used for process equivalence definition.

There are few approaches to determine behavioral equivalence (or other words behaviour preservation) of refactored processes. In [START_REF] William | Refactoring Object-Oriented Frameworks[END_REF] author proposes definition that two systems are equivalent when response for each request is the same from both systems. According to [START_REF] Moore | Automatic inheritance hierarchy restructuring and method refactoring[END_REF] communication oriented systems are equivalent, if they send messages in the same order.

In case of transformational design we assume that every service fulfills stateless assumption. It means that when BPEL process invokes external service then every response for some request is the same and do not depend on history. This assumption leads to the conclusion that state of external services (and all environment) is encapsulated inside the invoking service.

To make this assumption usable and to prove how it can be used we need basic PA theory.

B x -→ B ′ (1)
The above formula means that process B reaches state B' after receiving event (message) x Now PA semantics is defined using inference rules that has form:

premises conclusions (sidecondition) (2)
For example parallel execution (without synchronization) || has 2 symmetric rules :

B1 x -→ B1 ′ B1||B2 x -→ B1 ′ ||B2 and B2 x -→ B2 ′ B1||B2 x -→ B1||B2 ′ (3)
and precedes (sequential composition) >> has 2 rules :

B1 x -→ B1 ′ B1 >> B2 x -→ B1 ′ >> B2 and B2 σ -→ B2 ′ B1 >> B2 i -→ B2 (4)
where σ is successful termination and i is unobservable (hidden) event.

If external services S is stateless then:

∀y ∈ Y S y -→ S ( 5
)
where Y is a set of all events. This means that every event, generated externally by the subject service, does not change the state and answer of the service.

To analyse BPEL process using PA terms, the BPEL process has to be translated into PA using the mapping mentioned above. The result of the translation is a set of PA processes that are sequentially ordered by BPEL steering instructions -sequences, flows, switches and so on. Additionally, part of the mapping is activity dependency process. This artifact symbolizes data dependency between the activities (one needs data generated by the other one).

Let us denote it with dependency operator

A]x]B (6)
which means that state B can be started after A is successfully terminated and event x is emitted (or received). Below we illustrate the foundations of the behavioral equivalence concept. Let us consider a process that has a set of operations connected with dependency sequence:

(A]x]C]z]D) (7)
C waits for A result and D for C result. Apart from the above dependency, the process has also structural sequence defined by <sequence> instruction A -> B -> C -> D, where B is an instruction, which is not connected by activity dependency. We can relax the structural sequence and consider the process as:

(A]x]C]z]D)||B (8)
That means, we can treat (A]x]C]z]D) and B as two parallel, independent activities.

Proof that ( 8) is true for stateless services.

1. if there is no external service, ( 8) is true by the definition because there is no interaction between (A]x]C]z]D) and B 2. if there is stateless external service S, then:

∀y(A]x]C]z]D)||S y -→ ((A]x]C]z]D)) ′ ||S (9)
and ∀yS||B

y -→ S||B ′ (10)
which leads to :

(A]x]C]z]D) y -→ (A]x]C]z]D) ′ ⇒ (A]x]C]z]D)||B y -→ (A]x]C]z]D) ′ ||B (11)
and

B y -→ B ′ ⇒ (A]x]C]z]D)||B y -→ (A]x]C]z]D)||B ′ (12)
Equation ( 12) is parallel execution inference rules ( 3) which is proof of [START_REF] Ambrogio | A model-driven approach to describe and predict the performance of composite services[END_REF] If S was statefull, then

∃y(A]x]C]z]D)||S y -→ (A]x]C]z]D) ′ ||S ′ (13) then (A]x]C]z]D)||B y -→ (A]x]C]z]D) ′ ||B ′ (14)
this would mean that there are some interactions between (A]x]C]z]D) and B, and that they can not be treated independently.

The above theory makes possible to break the whole BPEL process into a set of subprocesses, which depend on each other only by data dependecies represented as activity dependencies. This technique can be related to program slicing [START_REF] Binkley | Program slicing[END_REF] used broadly in source code refactoring. BPEL service with defined activity dependencies and without structured constraints (sequences, flows, conditional and so on) is called minimal dependency process (MDP). Such a MDP becomes a basis for verification of equivalence of transformed (refactored) process with the requirements specified by MDP. After refactoring, new (refactored) process has to be translated to PA and its PA image must fulfill preorder relationship specified by MDP, therefore, refactored process has to be a subgraph of MDP's states graph.

Application of PA in Refactoring

As it was mentioned in the transformational approach introduction, PA formalism can help to decide if examined process is equivalent to reference one or points changes between processes. This is done by comparing execution state graphs of reference and refactored process. There are two possible results of this examination:

execution graph of refactored process is subgraph of MDP reference process -this means that refactored process is equivalent to reference process or -execution graph is not subgraph of MDP reference process -processes are not equivalent, but the information that can be obtained from the comparision is: what edges or nodes of execution graph are in refactored process but does not exist in MDP graph. Those extra edges and/or nodes are related to instructions or parts of code that makes importand diference between original and refactored process. The human designer can then decide, if theese differences are acceptable or not, in context of refactored process. Algorithm of equivalence verification consist of three steps:

Algorithm and Tools for Equivalence Verification

1. Translating BPEL process to minimal dependency process (MDP) -this step is made only once at the beginning of refactoring process; 2. Translating BPEL process to its PA image; 3. Checking preorder relationship of PA image with minimal dependency process.

For purposes of the test, translation BPEL to PA was made by using XSLT [START_REF] W3c | Xsl transformations[END_REF] processor, as the PA processor Concurrency Workbench for New Century (CWB-NC) [START_REF] Cleaveland | Concurrency workbench of the new century[END_REF] has been used. The structure of the verification system is presented in figure 2.

Process Design Example

Entire approach can be illustrated on a practical example of an order handling process. During the transformations two quality attributes are taken into account: performance and reusability. First of them is measured by a response time under given load, the latter one by a number of interfaces the whole considered system provides.

2. Alternative (2): the process runs parallely all three requests -to invoice, shipping and scheduling services. 3. Alternative (3): a bit more sophisticated one -the reference service is splited into three separate services. First of them invokes shipping service, second one invokes invoice and scheduling services, the third one composes the other two subservices.

Equivalence verification

Each of the three alternatives are verified whether they are behaviorally equivalent to the reference process. Technique of the verification has been described in section 4. The result of the verification is as follows:

-Alternative ( 1) is behaviorally equivalent unconditionally, -Alternative (2) is not equivalent, because the request to invoicing and shipping services depends on the data received from shipping service. When all three requests start at the same time, we can not guarantee that the data from shipping service is received before the request to scheduling and invoicing services. This alternative cannot be accepted. -Alternative (3) is behaviorally equivalent.

Alternatives Evaluation -Performance

As it was mentioned at the beginning of the section, alternatives performance and reusability is assessed so as to chose a preferred process' structure. Performance is measured as a mean response time under certain load level. The web service and connections between services can be modeled with queueing theory like M/M/1//inf system [START_REF] Ambrogio | A model-driven approach to describe and predict the performance of composite services[END_REF]. It means that requests arrive to the system independently with exponential interval distribution and response time is also exponentially distributed. Thanks to the above assumptions, average response time of the whole system can be estimated as a sum of average response times of its components: services and links between them. To make evaluation simpler, we assume that every network connection has the same average latency R N . So average response time of the reference process is:

R RP = R BP ELRP + R shipping + R invoicing + R scheduling + 7R N (15)
Please note that average response times of invoicing, shipping and scheduling are simply added, thanks to the fact that services are invoked consecutively. Let us assume additionally that the values of appropriate parameters are as follows:

-R BP ELRP = 2 ms (average time of processing of main BPEL process) -R shipping = 3 ms (avg. resp. time. from shipping service) -R invoicing = 5 ms (avg. resp. time. from invoicing service) -R scheduling = 4 ms (avg. resp. time. from service)

R A1 = R BP ELA1 + R shipping + max(R invoicing , R scheduling ) + 7R N (16)
the difference between alternative (1) and reference process is that invoice and scheduling services are requested parallelly, so response time of parallel part is the maximum of response times of invoicing and scheduling processes. When we assume that R BP ELA1 = R BP ELRP then: R A1 = 17ms. Finally alternative (3) average response time is given by:

R A3 = R BP ELA31 +R BP ELA32 +R BP ELA33 +R shipping +max(R invoicing , R scheduling )+11R N (17)
that yields: R A3 = 25ms

Alternatives Evaluation -Reusability

Total number of interfaces provided by the considered system (i.e. process and acompanying services) has been used as a reusability metric (the more interfaces the higher reusability). Reference process and alternative (1) deliver four interfaces: one to the purchase process and three to the elementary services: invoicing, shipping and scheduling. Alternative (3) delivers six interfaces: three to the elementary services, one to the composite service (process) and two new interfaces to two subservices.

All the above data is gathered in table 2

Alternatives Selection

There is a trade-off between the two considered quality attributes: systems consisting of more basic services are more reusable at the expense of performance and vice versa. The designer has to decide according to assumed design preferences: when reusability is prefered -alternative (3) should be chosen, otherwise when performance is the most important attribute -alternative (1) should be preferred.

Summary

The paper presents a transformational approach to the design of electronic business processes denoted in BPEL. The approach has been founded on a novel concept of business processes equivalence, which makes possible to construct business processes by their gradual transformations. Processes resulting from those transformations can be formally verified against their specification as well as against typical properties of concurrent systems like livenes or reachability. The designer, who steeres the transformations by evaluating non-functional attributes, is informed either that transformed process meets predefined requirements or which parts of process' behaviour has changed. He can accept or reject such a non-equivalent transformation, beeing also assisted by supporting tools. The usefulness of our approach has been presented on a not-trivial example. The directions for tool support development have also been provided, some of these tools have already been implemented: e.g. BPEL to LOTOS transformation tool. Further research can include development of predefined transformations that have been proved to preserve a priori properties like process equivalence as well as the development of a business process design environemnt (software tools) integrating all the tools needed to support the presented approach. The challenge in building such tools is to make one consistent process out of all the separated method steps and to build an integrated development environment. Integrated tool can be built as an extension of one of the open-source software development environments like Eclipse or NetBeans.

Fig. 1 .

 1 Fig. 1. Process transformation algorithm

Fig. 2 .

 2 Fig. 2. Structure of verification process

Fig. 4 .

 4 Fig. 4. Discussed alternatives for the reference process

Table 1 .

 1 Sample mappings BPEL activities to PA formulas.

	BPEL	LOTOS Process Algebra
	external service invocation
	<invoke inputVariable="inputName" outputVariable="outputName" name="invokeName" [...] </invoke>	process invoke_invokeName [inputName,outputName] := hide tau in ( inputName;tau;outputName;ended;exit )
		endproc
	receive message
	<receive variable="variableName" name="receiveName" [...] </receive>	process receive_receiveName [variableName] := hide tau in ( variableName;tau;ended;exit
		)
		endproc
	assign variable value
	<assign name="assignName" <copy> <from variable="fromVar"> <from to="toVar"> </copy> </assign>	process assign_assignName [fromVar, toVar] := hide tau in ( fromVar;tau;toVar;ended;exit ) endproc
	parallel execution
	<flow name="flowName">	process flow_flowName[dmmy] :=
	< ... name="activityA"/>	hide ended in (
	< ... name="activityB"/> [...]	activityA |[ended]| activityB ...
	</flow>	)
		endproc
	sequential execution
	<sequence name="seqName">	process sequence_seqName[dmmy] :=
	< ... name="activityA"/>	activityA >> activityB >> ...
	< ... name="activityB"/>[...]	endproc
	</sequence>
	conditional execution
	<switch name="switchName">	process switch_switchName[dmmy] :=
	<case ...>	hide ended in (
	< ... name="activityA"/>	activityA [] activityB ...
	</case>	)
	<case ...>	endproc
	< ... name="activityB"/>
	</case>
	</switch>

Table 2 .

 2 Quality metrics for the reference process and its alternatives.

			Reference	Alternative 1 Alternative 3
			process
	Average	response	21 ms	17 ms	25 ms
	time
	Reusability		4	4	6
	Services quantity	1	1	3

Reference process

The order handling process service is composed of three basic activities: invoicing, order shipping and production scheduling, which operate as follows:

1. A purchase order is received -it defines purchased product type, quantity and desired shipping method, 2. Shipping service is requested, which returns the shipping costs, 3. Invoice service provides the process with an invoice, 4. Production of ordered goods is scheduled with the request to scheduling service.

All the activities are performed consecutively. The reference process with accompanying services is depicted in fig. 3.

Process Alternatives

The designer consideres three alternatives to the reference process shown in fig. 4: 1. Alternative (1): the purchase process first makes request to the shipping service then in parallel to scheduling and invoice services.


Slawomir Samolej
email: ⋆ssamolej@prz.edu.pl

Tomasz Szmuc

HTCPNs-based Tool for Web-Server Clusters Development

Keywords: Hierarchical Timed Coloured Petri Nets, Web-Server Clusters, Performance Evaluation

A new software tool for web-server clusters development is presented. The tool consist of a set of predefined Hierarchical Timed Coloured Petri Net (HTCPN) structures -patterns. The patterns make it possible to naturally construct typical and experimental server-cluster structures. The preliminary patterns are executable queueing systems. A simulation based methodology of web-server model analysis and validation has been proposed. The paper focuses on presenting the construction of the software tool and the guidelines for applying it in cluster-based web-server development.

Introduction

Gradually, the Internet becomes the most important medium for conducting business, selling services and remote control of industrial processes. Typical modern software applications have a client-server logical structure where predominant role plays an Internet server offering data access or computation abilities for remote clients. The hardware of an Internet or web-server is now usually designed as a set of (locally) deployed computers-a server cluster [START_REF] Cardellini | The State of the Art in Locally Distributed Web-Server Systems[END_REF][START_REF] Konunev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF][START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF][START_REF] Urgaonkar | et all: An Analytical Model for Multi-tier Internet Services and Its Applications[END_REF]. This design approach makes it possible to distribute services among the nodes of a cluster and to improve the scalability of the system. Redundancy which intrinsically exists in such hardware structure provides higher system dependability.

To improve the quality of service of web-server clusters two main research paths are followed. First, the software of individual web-server nodes is modified to offer average response time to dedicated classes of consumers [START_REF] Kim | Improving Web Services Performance Using Priority Allocation Method[END_REF][START_REF] Liu | Online Response Time Optimization of Apache Web Server[END_REF][START_REF] Liu | Timing Performance Control in Web Server Systems Utilizing Server Internal State Information[END_REF]. Second, some distribution strategies of cluster nodes are investigated [START_REF] Cardellini | The State of the Art in Locally Distributed Web-Server Systems[END_REF] in conjunction with searching for load balancing policies for the nodes [START_REF] Guo | Load Balancing in a Cluster-Based Web Server for Multimedia Applications[END_REF][START_REF] Spies | Modeling of Optimal load balancing strategy using queueing theory[END_REF][START_REF] Zhang | Web server load balancing: A queuing analysis[END_REF]. In several research projects reported in [START_REF] Konunev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF][START_REF] Shan | Modelling and performance analysis of QoS-aware load balancing of Web-server clusters[END_REF][START_REF] Urgaonkar | et all: An Analytical Model for Multi-tier Internet Services and Its Applications[END_REF] load balancing algorithms and modified cluster node structures are analyzed together.

It is worth noticing that in some of abovementioned manuscripts searching for a solution of the problem goes together with searching for the adequate formal language to express the system developed [START_REF] Cao | Web Server Performance Modeling Using an M/G/1/K*PS Queue[END_REF][START_REF] Konunev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF][START_REF] Shan | Modelling and performance analysis of QoS-aware load balancing of Web-server clusters[END_REF][START_REF] Spies | Modeling of Optimal load balancing strategy using queueing theory[END_REF][START_REF] Urgaonkar | et all: An Analytical Model for Multi-tier Internet Services and Its Applications[END_REF][START_REF] Zhang | Web server load balancing: A queuing analysis[END_REF]. In [START_REF] Cao | Web Server Performance Modeling Using an M/G/1/K*PS Queue[END_REF][START_REF] Spies | Modeling of Optimal load balancing strategy using queueing theory[END_REF][START_REF] Urgaonkar | et all: An Analytical Model for Multi-tier Internet Services and Its Applications[END_REF][START_REF] Zhang | Web server load balancing: A queuing analysis[END_REF] Queueing Nets whereas in [START_REF] Shan | Modelling and performance analysis of QoS-aware load balancing of Web-server clusters[END_REF] Stochastic Petri Nets are applied for system model construction and examination. However, the most mature and expressive language proposed for the web-cluster modelling seems to be Queueing Petri Nets (QPNs) [START_REF] Konunev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF]. The nets combine coloured and stochastic Petri nets with queueing systems [START_REF] Bause | Queueing Petri Nets -a formalism for the combined qualititative and quantitative analysis of systems[END_REF] and consequently make it possible to model relatively complex web-server systems in a concise way. Moreover, there exists a software tool for the nets simulation [START_REF] Kounev | SimQPN-A tool and methodology for analyzing queueing Petri net models by means of simulation[END_REF]. The research results reported in [START_REF] Konunev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF] include a systematic approach to applying QPNs in distributed applications modelling and evaluation. The modelling process has been divided into following stages: system components and resources modelling, workload modelling, intercomponent interactions and processing steps modelling, and finally -model parameterization. The final QPNs based model can be executed and used for modelled system performance prediction.

The successful application of QPNs in web-cluster modelling become motivation to research reported in this paper. The aim of the research is to provide an alternative methodology and software tool for cluster-based hardware/software systems development. The main features of the methodology are as follows:

-The modelling language will be Hierarchical Timed Coloured Petri Nets (HTCPNs) [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF], -A set of so called HTCPNs design patterns (predefined net structures) will be prepared and validated to model typical web cluster components, -The basic patterns will be executable models of queueing systems, -A set of design rules will be provided to cope with the patterns during the system model creation, -The final model will be an executable and analyzable Hierarchical Timed Coloured Petri Net, -A well established Design/CPN and CPN Tools software toolkits will be used for the design patterns construction and validation, -The toolkits will also be used as a platform for the web-server modelling and development, -Performance analysis modules of the toolkits will be used for capturing and monitoring the state of the net during execution.

The choice of HTCPNs formalism as a modelling language comes from the following prerequisites. First, HTCPNs has an expression power comparable to QPNs. Second, the available software toolkits for HTCPNs composition and validation seem to be more popular than"SimQPN" [START_REF] Kounev | SimQPN-A tool and methodology for analyzing queueing Petri net models by means of simulation[END_REF]. Third, there exist a reach knowledge base of successful HTCPNs applications to modelling and validation of wide range software/hardware systems [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF] including web-servers [START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF][START_REF] Samolej | Dedicated Internet Systems Design Using Timed Coloured Petri Nets[END_REF][START_REF] Wells | et all: Simulation Based Performance Analysis of Web Servers[END_REF]. The rest named features of design methodology introduced in this paper results from both generally known capabilities of software toolkits for HTCPNs modelling and some previous experience gained by the authors in application HTCPNs to real-time systems development [START_REF] Samolej | TCPN-Based Tool for Timing Constraints Modelling and Validation[END_REF][START_REF] Samolej | Time Constraints Modeling And Verification Using Timed Colored Petri Nets[END_REF].

This paper is organized as follows. Section 2 describes some selected design patterns and rules of applying them to web-server cluster model construction. An example queueing system, web-server subsystem and top-level system models are presented. Section 3 touches the simulation based HTCPNs models validation methods. Conclusions and future research program complete the paper.

It has been assumed that the reader is familiar with the basic principles of Hierarchical Timed Coloured Petri Nets theory [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF]. All the Coloured Petri Nets in the paper have been edited and analysed using Design/CPN tool.

Cluster Server Modelling Methodology

The main concept of the methodology lies in the definition of reusable timed coloured Petri nets structures (patterns) making it possible to compose webserver models in a systematic manner. The basic set of the patterns includes typical queueing systems TCPNs implementations, eg. -/M/PS/∞ , -/M/FIFO/∞ [START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF][START_REF] Samolej | Dedicated Internet Systems Design Using Timed Coloured Petri Nets[END_REF]. Packet distribution TCPNs patterns constitute the next group of reusable blocks. They preliminary role is to provide some predefined web-server cluster substructures composed from the queueing systems. At this stage of subsystem modelling the queueing systems are represented as substitution transitions (compare [START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF][START_REF] Samolej | Dedicated Internet Systems Design Using Timed Coloured Petri Nets[END_REF]). The separate models of system arrival processes are also the members of the group mentioned. The packet distribution patterns represented as substitution transitions are in turn used for the general top-level system model composition. As a result, the 3-level web-server model composition has been proposed. The top-level TCPN represents the general view of system components. The middle-level TCPNs structures represent the queueing systems interconnections. And the lowest level includes executable queueing systems implementations.

The modelling methodology assumes, that the actual state of the Internet requests servicing in the system can be monitored. Moreover, from the logical point of view the model of the server cluster is an open queueing network, so the requests are generated, serviced and finally removed from the system. As a result an important component of the software tool for server cluster development is the logical representation of the requests.

In the next subsections the following features of the modelling methodology will be explained in detail. First, the logical representation of Internet requests will be shown. Second, queueing system modelling rules will be explained. Third, an example cluster subsystem with an individual load-balancing strategy will be proposed. Fourth, Internet request generator structure will be examined. Finally, top-level HTCPNs structure of an example cluster-server model will be shown.

Logical request representation

In the server-cluster modelling methodology that is introducing in the paper the structure of the HTCPN represents a hardvare/software architecture of webserver. Yet, the dynamics of the modelled system behavior is determined by state and allocation of tokens in the net structure. Two groups of tokens has been proposed for model construction. The fist group consist of so-called local tokens, that"live" in individual design patters.They provide local functions and data structures for the patterns. The second group tokens represent Internet requests that are serviced in the system. They are transported throughout several cluster components. Their internal state carries the data that may be used for timing and performance evaluation of the system modelled. As the tokens representing the requests have the predominant role in the modelling methodology, they structure will be explained in detail.

Each token representing an Internet request is a tuple

P ACKAGE = (ID, P RT, ST ART T IM E, P ROB, AU T IL, RU T IL)
, where ID is a request identifier, P RT is a request priority, ST ART T IM E is a value of simulation time when the request is generated, P ROB is a random value, AU T IL is an absolute request utilization value, and RU T IL is a relative request utilization value. Request identifier makes it possible to give the request an unique number. Request priority is an integer value that may be taken into consideration when the requests are scheduled according priority driven strategy [START_REF] Kim | Improving Web Services Performance Using Priority Allocation Method[END_REF]. ST ART T IM E parameter can store a simulation time value and can be used for the timing validation of the requests. Absolute request utilization value, and relative request utilization value are exploited in some queueing systems execution models (eg. with processor sharing service).

Queueing system models

The basic components of the software tool for web-server clusters development that is being introduced in this paper are the executable queueing systems models. At the current state of the software tool construction the queueing systems models can have FIFO, LIFO, processor sharing or priority based service discipline. For each queue an arbitrary number of service units may be defined. Additionally, the basic queueing systems has been equipped with auxiliary components that make it possible to monitor the internal state of the queue during it's execution. The packets under service acquire the adequate time stamps generated according the assumed service time random distribution function. The time stamps associated with the tokens prevent from using the packet tuples (the tokens) for any transition firing until the stated simulation time elapses (according to firing rules defined for HTCPNs [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF]). The packets are treated as serviced when they can leave OU T P U T P ACKS place as their time stamps expired. The number of tokens in TIMERS place defines the quantity of queue servicing units in the system.

The main parameters that define the queueing system model dynamics are the queue mean service time, the service time probability distribution function and the number of servicing units. The capacity of the queue is not now taken into consideration and theoretically may be unlimited.

For future applications the primary queueing system design pattern explained above has been equipped with an auxiliary "plug-in". COU N T QL transition and T IM ER QL, QL and COU N T ER places make it possible to measure the queue length and export the measured value to the parent CPNs page during the net execution. T IM ER QL place includes a timer token that can periodically enable the COU N T QL transition. QL port place includes a token storing the last measured queue length and an individual number of a queueing system in the system. The COU N T ER place includes a counter token used for the synchronization purpose.

Cluster load-balancing model

Having a set of queueing systems design patterns some packet distribution HTCPNs structures may be proposed. In [START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF] a typical homogenous multi-tier web-server structure pattern was examined, whereas in [START_REF] Samolej | Dedicated Internet Systems Design Using Timed Coloured Petri Nets[END_REF] a preliminary version of server structure with feedback like admission control of Internet requests was introduced. The packet distribution pattern presented in this paper touches the load balancing in web-server cluster problem. A load balancer decides where the currently acquired request should be send to achieve an uniform load for all, even heterogenic nodes of the cluster. Generally, the load balancing procedure can follow the Fewest Server Processes First [START_REF] Shan | Modelling and performance analysis of QoS-aware load balancing of Web-server clusters[END_REF] or the Adaptive Load Sharing [START_REF] Guo | Load Balancing in a Cluster-Based Web Server for Multimedia Applications[END_REF] algorithms. In both algorithms some feedback information about the state of cluster nodes under balance is needed. QL1 , QL2 and QL3 places (connected to corresponding QL port places of F IF O queueing system models-compare section 2.2) provide the queue's lengths of each cluster node to the load balance procedure. The less loaded server nodes have the highest probability to get a new request to serve.

The HTCPNs implementation of the algorithms involves periodical firing BALAN CE transition. During the firing, a set of threshold values is generated and stored in B T ABLE place. Finally, the thresholds values are mapped to guard functions associated to T 3, T 4 and T 5 transitions and can be understand as some kind of bandwidths for the requests streams. At current state of the design pattern composition, the only load balancer parameter that influences its dynamics is the frequency at witch the load of cluster nodes is measured.

Request generator model

According to one of main assumptions of the web-server cluster modelling methodology presented in this paper, the system model can be treated as an open queueing network. Consequently, the crucial model component must be a network arrival process simulating the Internet service requests that are sent to the server.

Fig. 3 shows an example HTCPNs subpage that models a typical Internet request generator. The core of the packet generator is a clock composed from T IM ER0 place and T 0 transition. The code segment attached to the T 0 transition produces values of timestamps for tokens stored in T IM ER0 place. The values have the probability distribution function defined. As a result the Internet requests appear into P ACKS1 place at random moments in simulation time. The frequency at which tokens appear in P ACKS1 place follows the distribution function mentioned. P ACKS1 place has a port place status and thereafter tokens appearing in it can be consumed by other model components (e.g. server cluster model). The Internet request frequency can have any standard probability distribution function or can be individually constructed as it was proposed in [START_REF] Wells | et all: Simulation Based Performance Analysis of Web Servers[END_REF].

Example top-level cluster server model

Having the adequate set of design patterns, a wide area of server cluster architectures can be modelled and tested at the early stage of development process. At the top-level modelling process each of the main components of the system can be represented as a HTCPNs substitution transition. The modelling methodology presented in the paper suggest that at the top-level model construction the arrival process and main server cluster layers should be highlighted. After that each of the main components (main substitution transition) should be decomposed into an adequate packed distribution subpage, were under some of transitions queueing system models will be attached. It is easily to notice that a typical top-down modelling approach of software/hardware system modelling has been adapted in the web server modelling methodology proposed in the paper.

Fig. 4 includes an example top-level HTCPN model of server cluster that follows the abovementioned modelling development rules. The HTCPN in fig. 4 consist of 2 substitution transitions. IN P U T P ROCS transition represents the arrival process for the server cluster whereas SERV ER CLU ST ER transition represents example one-layer web-server cluster. The modelling process can be easily continued by attaching the request generator model as in section 2.4 under the IN P U T P ROCS transition and by attaching the cluster model with load balancing module as in section 2.3 under SERV ER CLU ST ER transition. The final executable model can be acquired by attaching FIFO design patterns under F IF O1, F IF O2 and F IF O3 transitions in the load balancing module (compare sections 2.2 and 2.3).

Top-level cluster model

Model validation capabilities

Typical elements of HTCPNs modelling software tools are performance evaluation routines, e.g.: [START_REF] Linstrom | Design/CPN Perf. Tool Manual[END_REF] . The routines make it possible to capture the state of dedicated tokens or places during the HTCPN execution. A special kind of log files showing the changes in the state of HTCPN can be received and analyzed offline.

At the currently reported version of web-server cluster modelling and analysis software tool, queue lengths and service time lengths can be stored during the model execution. Detecting the queue lengths seem to be the most natural load measure available at typical software systems. The service time lengths are measurable in the modelling method proposed because of a special kind P ACKAGE type tokens construction (compare section 2.1). The tokens "remember" the simulation time at witch their appear at the cluster and thereafter the time at each state of their service may be captured. In real systems the service time is one of predominant quality of service parameters for performance evaluation. The performance analysis of models of web servers constructed according the proposed in the paper methodology can be applied in the following domains. First, the system instability may be easily detected. The stable or balanced queueing system in a steady state has an approximately constans average queue length and average service time. On the contrary, when the arrival process is to intensive for the queueing systems to serve, both queue lengths and service times increase. This kind of analysis is possible because there are not limitations for queue lengths in the modelling method proposed. Fig. 5 shows the queue lengths (fig. 5a) and service time lengths (fig. 5b) when the example web server cluster model presented in the paper experiences the permanent overload.

Second, the average values of queueing system systems parameters such as average queue lengths and average servicing time for the balanced model can be estimated. Provided that the arrival process model and the server nodes models parameters are acquired from the real devices as in [START_REF] Liu | Online Response Time Optimization of Apache Web Server[END_REF][START_REF] Shan | Modelling and performance analysis of QoS-aware load balancing of Web-server clusters[END_REF][START_REF] Urgaonkar | et all: An Analytical Model for Multi-tier Internet Services and Its Applications[END_REF][START_REF] Wells | et all: Simulation Based Performance Analysis of Web Servers[END_REF], the software model can be used for derivation the system properties under different load conditions. In the fig. 6 queue lengths (fig. 6a) and service times (fig. 6b) under stable system execution are shown. The cluster had a heterogenic structure, where server 2 (fifo 2 model) had 4 times lower performance. The load balance procedure was trying to reduce amount of Internet requests for the second server executing the Adaptive Load Sharing [START_REF] Guo | Load Balancing in a Cluster-Based Web Server for Multimedia Applications[END_REF] algorithm. FIFO1 and FIFO3 average queue length was 1.7, whereas FIFO3 queue length was 4.4. The average service time for FIFO1 and FIFO3 cluster nodes was 811 time units whereas for FIFO2 was 7471 time units. Third, some individual properties of cluster node structures or load balancing strategies may be observed. For example, in some load balancing strategies mentioned in [START_REF] Guo | Load Balancing in a Cluster-Based Web Server for Multimedia Applications[END_REF], the load of cluster node is estimated without any feedback information from the node. Such load balancing strategy may easily fail when node performance becomes reduced due to some external reasons (e.g. hardware fail or some extra node load). Fig. 7 shows a possible web-server cluster reaction to the not reported performance reduction of one server node. It can be easily noticed that under some disadvantageous conditions the loss or unavailability of feedback information about the current state of cluster server can lead to its unstable behavior. The Internet requests scheduled to server 2 node after the node performaance reduction (at approximately 1000000 time units) may not be serviced due to the server overload.

Conclusions and future research

The paper introduces the HTCPNs-based software tool making it possible to construct and validate some web-server clusters executable models. The main concept of the tool lies in the definition of reusable HTCPNs structures (patterns) involving typical components of cluster-based server structures. The preliminary patterns are executable models of typical queueing systems. The queueing systems templates may be arranged into server cluster subsystems by means of packet distribution patterns. Finally, the subsystems patterns may be naturally used for top level system modelling, where individual substitution transitions "hide" the main components of the system.

The final model is a hierarchical timed coloured Petri net. Simulation and performance analysis are the predominant methods that can be applied for the model validaton. Queueing systems templates was checked whether they meet theoretically derived performance functions.

The analysis of HTCPNs simulation reports makes it possible to predict the load of the modelled system under the certain arrival request stream; to detect the stability of the system; to test a new algorithms for Internet requests redirection and for their service within cluster structures.

Currently, the software tool announced in the paper can be applied for a limited web-server cluster structures modelling and validation. Thereafter the main stream of author's future research will concentrate on developing next webserver node structures models. This may result in following advantages. First, an open library of already proposed web-server cluster structures could be created and applied by the future web-server developers. Second, some new solutions for distributed web-server systems may be proposed and validated.

  The example HTCPNs based queueing system model is shown in fig. 1. The model is a HTCPNs subpage that can communicate with the parent page via IN P U T P ACKS, OU T P U T P ACKS and QL port places. The request packets (that arrive through IN P U T P ACK place) are placed into a queue structure within P ACK QU EU E place after ADD F IF O transition execution. T IM ERS place and REM OV E F IF O transition constitute a clock-like structure and make it possible to model the duration of packet execution. When REM OV E F IF O transition fires, the first packet from the queue is withdrawn and directed to the service procedure.

Fig. 1 :

 1 Fig. 1: HTCPNs based -/1/FIFO/∞ queueing system model.

Fig. 2

 2 Fig. 2 includes an example cluster load-balancing HTCPNs model.The cluster consist of 3 computers represented as F IF O1...F IF O3 substitution transitions, where each transition is attached to a F IF O queueing pattern. The Internet requests serviced by the cluster arrive through P ACKS2 port place.A load balancer decides where the currently acquired request should be send to achieve an uniform load for all, even heterogenic nodes of the cluster.

Fig. 2 :

 2 Fig. 2: Server cluster with load balancing model.

Fig. 3 :

 3 Fig. 3: Web-server arrival process model.

Fig. 4 :

 4 Fig. 4: Example top-level cluster server model.

Fig. 5 :

 5 Fig. 5: Queue lengths (a) and service times (b) under overload condition.

Fig. 6 :

 6 Fig. 6: Queue lengths (a) and service times (b) under stable system execution.

Fig. 7 :

 7 Fig. 7: Example queue lengths (a) and service times (b) of unbalanced web-server cluster.