Pavol Mederly
email: mederly@fiit.stuba.sk

Marián Lekavý
email: lekavy@fiit.stuba.sk

Marek Závodský
email: zavodsky@fiit.stuba.sk

Pavol Návrat
email: navrat@fiit.stuba.sk

Construction of Messaging-Based Enterprise Integration Solutions Using AI Planning

Keywords: Enterprise Application Integration, Enterprise Integration Patterns, Messaging, Action-Based Planning, STRIPS-like Planning

This paper presents a novel method of using action-based planning for construction of enterprise integration solutions that utilize messaging technologies. More specifically, the presented method is able to generate a sequence of processing steps needed to transform input message flow(s) to specified output message flow(s), taking into account requirements in areas of throughput, availability, service monitoring, message ordering, and message content and format conversions. The method has been implemented as a research prototype. It has been evaluated using scenarios taken from the literature as well as from realworld experience of the authors.

Introduction

Enterprise application integration deals with making independently developed and sometimes also independently operated applications in an enterprise to work together to produce a unified set of functionality [START_REF] Hohpe | Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions[END_REF]. It is a significant concern for many enterprises and a lot of resources are being spent in order to achieve its aims [START_REF] Chappell | Enterprise Service Bus[END_REF].

When creating an integration solution many issues have to be addressed. Some of them are related to correctly designing the business logic of the solution, i.e. algorithms such as "when a purchase order arrives, the system has to call 'check customer credit' and 'check inventory' services 1 , and then, depending on the results, it should continue with order processing or return an error message to the client". Currently this business logic is, and very probably will continue to be, designed by human users, preferably by business analysts in cooperation with business owners.

Other issues to be addressed when designing an integration solution can be characterized as technical ones: these are concerned with differences in message transport protocols, application programming interfaces (APIs), message format and syntax, security requirements, availability and performance properties, logging and auditing requirements, etc. Resolution of these issues is driven by requirements and capabilities of participating services, by technical infrastructure available, and by business requirements. Although powerful tools in this area have appeared recently, e.g. those grouped under umbrella term "Enterprise Service Bus" [START_REF] Chappell | Enterprise Service Bus[END_REF], technical aspects are still being dealt with by people, mostly IT specialists.

In the long term, our research is directed towards automatic or semiautomatic resolution of these technical issues. 2 One of the first results achieved is a method of generating parts of messaging-based integration solutions using action-based planning approach. From many potential design aspects present in creating such solutions we have concentrated on the following ones: throughput, availability, service monitoring, message ordering, and message content and format conversions.

We have chosen the planning approach because there is a strong similarity between searching for an integration solution and planning in general: when constructing an integration solution we are looking for a sequence of services transforming input message flow to an output one, while when planning we are looking for a sequence of actions transforming the world from the initial state to a goal state. From the practical point of view it is reasonable to use existing planners capable of efficiently finding such sequences of actions (i.e. plans).

The remainder of this paper is organized as follows: Section 2 briefly characterizes messaging-based integration solutions, exemplifying some aspects of their design using a case study. In Section 3 the novel method of using an action-based planner to generate integration solutions is presented. Section 4 is devoted to the prototype implementation and the evaluation of the method. Section 5 describes related work. Section 6 closes this paper, giving some ideas on future work.

Messaging-Based Integration Solutions

The hypothetical online retailer company "Widgets and Gadgets 'R Us" buys widgets and gadgets from manufacturers and resells them to customers. 3 The company wants to automate purchase orders processing. Since parts of the whole process are implemented in disparate (and incompatible) systems, in order to achieve seamless operation, the company has to integrate systems involved in the process.

Handling of purchase orders looks like this: Orders are being placed by customers through three systems, namely through web interface, call center and fax gateway. Each order is stored in a separate message. A message containing an order is then translated from source system-specific data model to a common data model. After that, the customer's credit standing as well as inventory is checked. If both checks are successful, goods are shipped to the customer and an invoice is generated. Otherwise, the order is rejected.

Due to historical reasons, information about stock levels is kept in two separate systems: Widgets Inventory and Gadgets Inventory. So each purchase order is inspected to see if the items ordered are widgets, gadgets, or something else. Based on this information the request for checking inventory is sent to one of these systems or to a special message channel reserved for invalid orders.

The situation is shown in Fig. 1. We have chosen to use the Business Process Modeling Notation (BPMN) here as it is a technology-independent way of process modeling. This kind of abstract description has to be implemented using concrete software entities. There are many technology approaches to do that. As stated above, in this paper we concentrate on messaging-based integration solutions, i.e. those that use an asynchronous messaging middleware (for example, a Java Message Service implementation) as a primary means for their components' communication.

This integration style is frequently used in practice. Below we shortly describe some of the design considerations that usually arise when creating solutions using this paradigm. These and other issues and their solutions are discussed in depth in the influential Hohpe and Woolf's Enterprise Integration Patterns book [START_REF] Hohpe | Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions[END_REF] in the form of patterns. We extensively use these patterns to describe integration solutions generated by our method.

Messaging-based integration solutions generally follow the Pipes and Filters pattern: 4 they receive messages at their input side (in one or more message flows), process them by a sequence of services connected by various channels, and put them on the output side (again, in the form of one or more message flows). One of fundamental design choices is how individual services should be connected. A standard way of communication is through messaging middleware, using either Point-to-Point Channels (often called "queues") or Publish-Subscribe Channels (often called "topics" or "subjects"). The basic difference between these types of channels is that a message arriving at a Point-to-Point Channel is consumed by exactly one of receivers listening on this channel, while message arriving at a Publish-Subscribe Channel is consumed by all receivers listening on that channel. If services reside in the same address space, they can communicate via in-memory channels as well, eliminating the overhead of going through messaging middleware.

It is often the case that the throughput and/or availability of a service running in single thread of execution is not adequate. A typical solution is to deploy such a service in multiple threads, in multiple processes, or even on multiple hosts, using the Message Dispatcher and/or the Competing Consumers pattern. This limits the choices of an input channel for that service, e.g. not allowing topics to be used in some cases.

Another issue is that we might need to monitor some services -for example their quality-of-service attributes like throughput, response time, or availability. In most cases this means that we have to be able to "see" messages entering selected services and messages leaving them -typically using topics or a special Wire Tap service.

Yet another issue is that of message ordering. There are situations when it is important that the order of messages in the flow is kept unchanged. Unfortunately, in some cases, typically when processing messages in multiple threads, their order is not preserved. The solution is often based on a Content Enricher generating message sequence numbers paired with a Resequencer restoring original order of messages.

Almost all services require the messages to be in a specified format, e.g. commaseparated values, fixed-length records, XML, JSON (JavaScript Object Notation), or other. The integration architect has to employ specific converters appropriately.

Even though the basic process structure is designed by a business analyst, it is sometimes possible to choose from alternative implementations of business services available, depending e.g. on quality-of-service attributes, ease of access, and/or cost.

In order to see a concrete integration solution let us consider the following requirements: (1) while all services in our scenario work with messages in XML format, inventory checking ones use JSON format instead, (2) due to performance reasons the "Check gadgets inventory" service has to be deployed on multiple hosts, (3) we need to monitor correct functioning of credit checking service and both inventory checking services, and (4) the order of messages arriving at "Order feasibility check" service should be the same as original order of messages at the input side.

One of possible solutions implementing these requirements is shown in Fig. 2. It should be noted that this integration solution has been generated by the prototype implementation of our method. It is correct and optimal with respect to number of components. Placing Resequencer in one of the branches might look a bit strange, yet it is adequate -as the ordering of messages in the left branch is unchanged, the "Aggregate results" service produces a message flow with the original ordering of messages.

Description of the Method

Given a specification of an integration scenario (consisting of description of input and output message flows, services available and other requirements and constraints), the method uses a planner to generate an integration solution, i.e. a structure of services that will transform input message flow(s) to output one(s) while complying with specified requirements and constraints.

The message flow is a fundamental concept of the method. We do not keep track of individual messages processed by the integration solution -we observe message flows instead. A flow is characterized e.g. by content and format of messages it contains, their ordering, and so on (see below). A message flow is being transformed by services, can be split into alternative or parallel flows, and these flows can be eventually joined back into one flow later.

Input and Output of the Method

The input of the method consists of the following:

1. A specification of input message flow(s). Each flow is described in terms of the content and format of messages in it and the type of channel it is present in. As an example, a flow can be specified as "a sequence of messages representing purchase orders entered via web interface, XML-formatted, available in a message queue". Note that the scenario described in our case study has three input message flows. 2. A specification of required output message flow(s). This type of flow is specified in the same way as an input flow, with the possibility to add a requirement that messages should be in the same order as they were at the input. The scenario described in the case study has four output message flows. 3. A set of services that are available for processing the messages. These can be business and mediation services. Each service is described by a set of parameters, namely (1) input/output message content and/or format, (2) throughput and availability characteristics per deployment mode, (3) parameters related to monitoring and message ordering, (4) a cost of using the service. 4. A set of other conditions that have to be met, e.g. ( 1) the integration solution has to provide a sustained throughput of at least 100 messages per minute, (2) the availability of solution has to be "normal"5 , (3) each call to "Check customer credit", "Check widgets inventory" and "Check gadgets inventory" service has to be monitored. 5. A set of general configuration options, like whether to use action costs (or use a default cost of 1 for each action instead) or whether to take formatting, monitoring and message ordering aspects into account. This last option is very important for optimizing time taken to generate plans, as will be shown.

The output of the method is the plan that encodes a structure of services sought. Concrete examples of the method's input and output as implemented in the prototype can be found in [START_REF] Mederly | Report on Evaluation of the Method for Construction of Messaging-Based Enterprise Integration Solutions Using AI Planning[END_REF].

Action-Based Planners

Due to similarities between searching for an integration solution and planning we conduct a search of the services to be used by employing a symbolical action-based planner.

Action-based (or STRIPS-like) planners, as descendants of the automated planner STRIPS [START_REF] Fikes | STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving[END_REF], are based on the situation calculus. States of the world (situations) are described as conjunctions of grounded first-order predicate formulas; these formulas are literals. A state of the world can be modified by applying operators.

An operator is a triple Op = (pre, del, add) where pre is a set of predicate formulas that must be satisfied in order for the operator to be invoked (a precondition), del is a set of predicate formulas that are deleted and add are predicate formulas that are added to the description of the state of the world. Together, del and add represent the effect of the operator. The operators can be parameterized, i.e. predicate formulas in pre, del, add are allowed to contain free variables.

The planning problem consists of the planning domain (a set of operators) and the definition of the initial state and the goal state (states). The planner then tries to find a plan, consisting of operators that incrementally transform the world from the initial state to a goal state. Operators used in a plan are called actions and are usually required to have all their variables bounded. Although the plan is usually a sequence of actions, it is also possible to create plans with concurrent actions.

A frequently used algorithm of action-based planning is based on sequential adding of operators to the plan. Plan construction is guided by operators' preconditions and effects, usually employing some kind of heuristics. In our method, we only use the planner as a black box. The exact plan search algorithm is not important, as long as it provides correct results in acceptable time. More information on action-based planning can be found e.g. in [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF].

Detailed Method Description

The principle of the method is the following: the integration problem to be solved is transformed into an input data for an action-based planner, written using the standard Planning Domain Description Language (PDDL). The planner is then executed and its output (i.e. the plan) is interpreted as a structure of services forming the integration solution. The situation is depicted in Fig. 3. The plan (a sequence of actions, i.e. operators applied) represents the integration solution we are looking for. Actions in the plan correspond to the technology elements of the solution and action dependencies (in the form of predicate formulas) correspond to connections (carrying message flows) between the elements. The transformation from the plan to integration solution description is straightforward.

In the following paragraphs we explore the problem encoding in more details.

State Description. Each message flow is described by the following predicate formula: message (?Content ?Format ?Ordered ?OrderMarked ?Monitoring ?Channel ?FlowID) message is a 7-ary predicate symbol. This predicate formula describes a message flow that fulfills the following conditions: (1) messages in the flow have content prescribed by the variable ?Content 6 , (2) messages in the flow are well formed according to a format specified by the variable ?Format, (3) order of messages in the flow is (or is not, as indicated by the variable ?Ordered) guaranteed to be identical to the order to messages in the input flow, (4) the original message ordering is (or is not, as indicated by the variable ?OrderMarked) recorded somewhere, typically in a dedicated message property, (5) the messages are in a monitoring-related state prescribed by the variable ?Monitoring, and ( 6) the messages are (or are not) currently available in the messaging middleware as prescribed by the variable ?Channel. The last variable is used to distinguish among multiple identical flows coming out e.g. from a topic or from a Recipient List service.

If there is only one flow active, the state of the world contains only one message predicate formula. If there are multiple flows, like in our case study, there is one message predicate formula for each flow.

Operators. The most important operators we use are those directly derived from services available. Each service is transformed to up to four operators, one for each of the following modes of deployment (parallelism levels): (1) single thread, (2) single process, multiple threads, (3) single host, multiple processes, and (4) multiple hosts. Each mode of deployment provides specific levels of performance and availability, e.g. CreditCheck service in parallelism level 1 could achieve a throughput of 100 messages per minute and availability at the level of "normal".

What operators is the service transformed into is controlled by: (a) the list of allowed parallelism levels given in the service description, (b) comparing solution throughput and availability requirements (goals) to throughput and availability characteristics of this service deployed at a particular level of parallelism. 7 As an example, the CreditCheck service that expects a message with content "Order" (c_ord) and transforms it into a "Order with Credit Information" (c_ord_cr- 6 Actually in some cases we use this variable to encode part of contextual information as well (an example of such information is "the flow contains orders that have been rejected"). 7 With a slight simplification we assume that the necessary and sufficient condition for the solution meeting its throughput and availability goals is that each of services involved meets these throughput and availability goals individually. We also assume that the performance and availability of underlying messaging middleware is not a limiting factor. Providing more sophisticated treatment of these aspects is one of the topics of future work.

info), deployed on multiple hosts, with monitoring required, is represented by the following operator (symbols starting with ? depict operator parameters): Correct use of channels is controlled by acceptable_input_channel_for-_PLx predicates that allow e.g. for PL1 the use of a topic, a queue or a single-process in-memory channel. For PL4 it is allowed to use only a queue or an in-memory channel going out from a previous PL4-deployed service. 8 Transport of messages through messaging middleware is modeled by two special operators, Queue and Topic. If one of them is added after a service, it means that the service sends its output through this kind of channel. This allows modeling the fact that sending messages via these channels is more costly than using direct in-memory connections (when using a planner that supports action costs this can be expressed quantitatively).

operator: CreditCheck_PL4_M // parallelism
Message ordering is accounted for by a set of two services: an OrderMarker service (implementing a Content Enricher pattern) that puts sequence numbers of messages into a dedicated message property, and a Resequencer service that reestablishes the order of messages using this property. When using multiple (alternative or parallel) message flows special care is taken with respect to message ordering and message order marking, but we have no space to cover the details here.

Monitoring is dealt with in the following way: services that have to be monitored require the value of monitored in the ?Monitored parameter of message predicate formula in the precondition and set the value of monitoring_requested in the ?Monitored parameters in its effects. This ensures that the input and output messages go either through a topic or through a WireTap service, because only operators corresponding to a topic and the WireTap are able to set the monitored value and "clear" the monitoring_requested one. Services that do not have to be monitored expect the value of not_monitored or monitored at the input and set the value of not_monitored at the output. As in message ordering aspect, the monitoring flag is also treated specially when using multiple flows.

For joining alternative or parallel message flows, a special "declarative" kind of operator is used. This operator does not correspond to any real service, it only serves as a declaration that message flows containing e.g. results from check of widgets inventory and results from check of gadgets inventory are merging in one queue into a message flow containing results from (an unspecified) inventory check. When using action costs these declarative operators are assigned the lowest possible cost. (When merging parallel flows, such declarative operator should be followed by a "real" Aggregate service, like the "Aggregate results" service in Fig. 2

.)

In order to shorten the time needed to find a plan it is possible to choose whether the solution should take aspects of monitoring, message formats, and message ordering into account. Parameters (of predicate formulas and operators) for disabled aspects are not created, so for example the message predicate can have an arity from 3 to 7, depending on the settings. As shown in the following section, this has strong performance implications.

Implementation and Evaluation

The method described above has been implemented in the form of a research prototype.

We have tried several planners. For practical reasons we have limited our search to those accepting PDDL as an input language. The selection of planners was guided by the results at the International Planning Competitions9 and our previous experience.

We have selected four problems to demonstrate the evaluation results here: Problems 1 and 2 correspond to a part of Widgets and Gadgets order processing scenario described in Section 2. The part covered begins when orders from three sources are merged in a queue and ends as orders enter feasibility check. Problem 1 takes into account monitoring and throughput aspects. Problem 2 takes into account aspects of monitoring, message format, and throughput. Problems 3 and 4 capture the whole order processing scenario as described in the case study; Problem 3 does not take aspects of monitoring, message format, message ordering, and throughput into account, while Problem 4 does. These settings are summarized in Table 1. Acronyms for aspects are: monitoring (M), message formats (F), message ordering (O), and throughput (T). "Message predicate arity" refers to the arity of the message predicate, "Parameters/operator" means average number of parameters of individual operators. These measures, along with number of operators and number of objects in the domain, very roughly indicate the size of state-space and plan-space that have to be searched -a major factor of complexity of the planning process.

The results (quality of solution found and CPU time needed to find it) for some of the planners are summarized in Table 2. 10the number of involved actions. This way the solution usually contains more software components than necessary.

We have also created several additional scenarios stemming from real-life experience of the authors [START_REF] Mederly | Enterprise Service Bus at Comenius University in Bratislava[END_REF] and have verified that the solutions produced by the prototype implementation are correct and optimal in the sense of number of components.

More detailed evaluation report that includes descriptions of integration problems, PDDL files, output produced by individual planners as well as the discussion of results achieved by particular types of planners can be found in [START_REF] Mederly | Report on Evaluation of the Method for Construction of Messaging-Based Enterprise Integration Solutions Using AI Planning[END_REF].

As a final remark, we can say that this method solves a defined subset of technical problems present in the creation of messaging-based integration solutions. We expect that the business-level decisions, e.g. the correct sequence of business services that have to be integrated or the business rules governing the mapping between incompatible message schemas and/or semantics, have to be provided by business users and are therefore out of scope of this method. Similarly, there are many technical aspects presently not dealt with by the method -e.g. creation of mediation components solving message schema and business protocol incompatibilities between systems being integrated, design issues related to security and reliability of the solution, issues of different communication protocols/mechanisms used, etc. Some of these are being worked on by the research community (e.g. [START_REF] Nezhad | Semi-Automated Adaptation of Service Interactions[END_REF]), while others are the subject of our future work. Finally, there are issues like dealing with unclear, changing and/or not correctly implemented components' interfaces that are possibly out of scope of any automated method for integration solution creation.

Related Work

We know of no existing research dealing with the problem of automatic creation of messaging-based integration solutions in a way similar to the one outlined above. More generally, however, there are several attempts to reduce human effort needed to solve technical issues present in construction of such solutions. Many of them are based on the idea of developing an abstract, platform-independent model of the integration solution and then incrementally refining it into platform-specific model(s) and/or executable code. For example, Scheibler and Leymann [START_REF] Scheibler | A Framework for Executable Enterprise Application Integration Patterns[END_REF] based their platform-independent models on enterprise integration patterns [START_REF] Hohpe | Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions[END_REF] enriched by configurable parameters. These models can then be automatically transformed into executable code, either written in Business Process Execution Language or in a configuration language of a specific integration tool (Apache ServiceMix).

This and similar approaches require the developer to specify technology-related model elements manually -albeit at a higher level of abstraction, compared to directly writing platform-specific configuration or code. Our method, in contrast, generates such elements automatically.

The work of Umapathy and Purao [START_REF] Umapathy | Representing and Accessing Design Knowledge for Service Integration[END_REF] is directed towards choosing solution elements (described in the form of integration patterns) automatically. The authors have devised an inference engine based system that accepts an integration scenario described as annotated model written in Business Process Modeling Notation and offers the developer a set of possible enterprise integration patterns to implement individual parts of the scenario. The difference to our approach is that this system only provides an aid to the developer, offering him or her a set of more or less relevant alternatives to choose from. Our method, in contrast, automatically generates a directly executable solution. The human interaction can be added in the future, but it is not necessary for the method to work. AI planners have been successfully used in various areas of software engineering. Some examples are test cases generation [START_REF] Fröhlich | Automated Test Case Generation from Dynamic Models[END_REF][START_REF] Scheetz | Generating Test Cases from an OO Model with an AI Planning System[END_REF] or assembly of algorithms having specified characteristics, using components from a properly annotated domain-specific library [START_REF] Troy | Context-Sensitive Domain-Independent Algorithm Composition and Selection[END_REF]. Another example is the method of creating a plan for dynamic reconfiguration of distributed systems after failure [START_REF] Arshad | Deployment and Dynamic Reconfiguration Planning for Distributed Software Systems[END_REF], focusing mainly on a (re)distribution of components and connectors to individual machines and finding a correct sequence of starting machines, components and connectors. More related to the topic of this paper is the use of AI planners for web service composition, as described e.g. in [START_REF] Oh | A Comparative Illustration of AI Planning-based Web Services Composition[END_REF] and [START_REF] Rao | A Survey of Automated Web Service Composition Methods[END_REF]. Works in this area deal primarily with creating compositions at the business level, not paying attention to technical aspects, as we do.

Conclusion and Future Work

The research results presented here demonstrate that planning techniques are useful for solving technical problems related to enterprise application integration. Our method is able to create parts of integration solutions from the description of "what" has to be achieved, not "how" it should be done. Evaluation using a case study and a set of real-world integration scenarios has shown that the method presented is able to solve practically-sized problems. In comparison, existing works in this area either require the developer to specify technology-related elements manually or, if not, they are not able to generate an executable solution (only provide hints for the developer).

Our aims for the future include covering other aspects of messaging-based integration solutions, for example questions of assured message delivery (using Guaranteed Delivery and/or Transactional Client patterns) or a support for diverse message transport protocols. We also plan to provide a code-generation module that would read the plan and provide a partially or fully executable integration solution for selected integration tool(s). As mentioned above, we want to further elaborate the notion of solution optimality and aspects of throughput and availability.

We also plan to have a look at the possibility of using other techniques for automatic generation of the solution, like logic inference engines, and integrate them in a framework for automatic or semi-automatic resolution of technical issues present in enterprise application integration solutions construction.

Fig. 1 .

 1 Fig. 1. A sample integration scenario.

Fig. 2 .

 2 Fig. 2. A messaging-based implementation of the sample integration scenario.

Fig. 3 .

 3 Fig. 3. Basic principle of our method

Table 1 .

 1 Description of problems selected for method evaluation.

	# Scope	Aspects	Message	Parameters/	# of	Domain	Optimal
			predicate	operator	operators	objects	plan length
			arity
	1 reduced	M, T	4	3.67	21	21	15
	2 reduced	M, T, F	5	4.12	25	23	19
	3 full	-	3	2.50	22	28	26
	4 full	M, F, O, T	7	6.81	36	39	36

Slightly simplifying, in this paper we use the term "service" to denote any software component providing business functionality that needs to be integrated and also to denote any component providing integration facilities like message routing, message format conversion, etc. The former are sometimes called business services, while the latter are called mediation (or integration) services.

As also described in "Business-driven automated compositions Grand Challenge"[START_REF] Papazoglou | Service-Oriented Computing Research Roadmap[END_REF].

This case study is taken from[START_REF] Hohpe | Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions[END_REF].

Hohpe and Woolf's patterns are referenced by using names with capitalized words.

We are considering 3 levels of availability: "low", "normal", and "high".

Assuming that this service runs in the same set of processes as its predecessor.

http://ipc.icaps-conference.org/

These results are only informative: some planners provided settings affecting performance, e.g. possibility to choose heuristics, weighting factors, etc. We tried to find optimal settings, but in some cases it might be possible to find better settings.

Acknowledgments

This work was partially supported by the Slovak Research and Development Agency (contract No. APVV-0391-06) and by the Scientific Grant Agency of Republic of Slovakia, grant No. VEGA 1/0508/09.

Acronyms for domains and search algorithms are: sequential plans (seq), parallel plans (par), action costs (cost), non-deterministic actions (non-det), state-space search (state), transformation to satisfiability problem (SAT), generating optimal plan (opt), not guaranteed to generate optimal plans (subopt). Acronyms for results are: optimal plan found (O), suboptimal plan found (SO), computation failed (Error).

These results show that our method is able to find solutions for practical integration problems using currently available planners. The majority of the planners had difficulties solving the most complex Problem 4. We suspect that some of them were not designed to work with such a large state-space as it was present in this problem. In our opinion, however, this is not a result of planning methods used, but more a result of implementation decisions made by the planners' designers.

When considering experiences from solving these and other integration problems, as the most suitable come HSP 2.0 planner (it is fast, although it produces suboptimal plans in some cases) and MIPS-XXL and Gamer (they are slower, but generate optimal sequential plans).

The planners are of different types, for example some generate sequential plans while other parallel ones. What type of planner do we actually need? Generally, it depends on what we want to optimize. Basically there are four (interrelated) possibilities: 1) integration solution complexity (number of components used in the solution), 2) latency (time needed for an integration solution to process a message), 3) throughput (number of messages processed by the solution per time unit), 4) resource consumption (e.g. network bandwidth, CPU time of message broker and/or application servers and so on).

At this moment, we use the criterion 1, corresponding to the shortest sequential plan. We can incorporate the criterion 4 by assigning costs to individual actions based on resource consumption. If we would like to optimize latency (criterion 2) we could use a parallel planner with durative actions (i.e. actions that have been assigned an execution time). For now we stay with the goal of finding the solution with the smallest complexity and leave the issue of exact optimality definition to be a subject of a future research. Therefore, for now optimal sequential planners with no other extensions are sufficient. The use of parallel planners in this context has a drawback in that they generally produce plans with the optimal makespan (number of steps of plan execution), not optimizing


Sławomir Samolej
email: ssamolej@prz.edu.pl

Tomasz Szmuc

HTCPNs-based Modelling and Evaluation of Dynamic Computer Cluster Reconfiguration

Keywords: Hierarchical Timed Coloured Petri Nets, Web-Server Systems, Performance Evaluation, Dynamic Reconfiguration

An extension of HTCPNs-based software tool for Internet systems modelling and evaluation has been proposed in the paper. After the extension the tool provides new possibilities for modelling and analysis of dynamic cluster reconfiguration algorithm. Some implementation details of the algorithm has been presented. The algorithm has been preliminary assessed by simulation.

Introduction

Current Internet (or web) servers usually have distributed multi-tier structure [START_REF] Cardellini | The State of the Art in Locally Distributed Web-Server Systems[END_REF][START_REF] Kounev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF][START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF][START_REF] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF][START_REF] Samolej | Coloured Petri Nets Application in a WWW Clusters Modelling and Development Method[END_REF][START_REF] Samolej | HTCPNs Application for Selected Internet Requests Scheduling Algorithms Analysis[END_REF][START_REF] Urgaonkar | Analytic Modeling of Multitier Internet Applications[END_REF]. Each tier consist of one or more computers and constitutes a hardware platform for layers of a distributed software system running on it. The tier including a set of computers is often called a computer cluster. Typically, a user of the software system connects to its presentation layer seen as a web site and forces actions to acquire some data. The user request is then send to system's application layer that may offer the requested data or may pass the request to database layer. The above-mentioned software system's layers may be attached to separate hardware layers or may be only partly distributed. Figure 1 shows a hardware structure of an exemplary Internet system. Presentation and application software layers are deployed in "WWW cluster" and cooperate with "Database cluster" that stores a distributed data base. This distributed multi-tier development approach enables natural scalability and redundancy of both hardware and software modules of the system.

Current Internet servers are developed to efficiently serve an average frequency of requests stream, and to "survive" transient overloads [START_REF] Cardellini | The State of the Art in Locally Distributed Web-Server Systems[END_REF][START_REF] Kounev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF][START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF][START_REF] Urgaonkar | Analytic Modeling of Multitier Internet Applications[END_REF]. The typical development procedure covers: estimation of hardware/software performance parameters of system components and performance analysis of prototype or model of the system under different load. The systematic performance analysis makes it possible to detect bottlenecks in the system and to predict overall system efficiency. As the system is of distributed structure, it is possible to iteratively analyse it, and then reconfigure it in order to remove defects. It seems that the main thread of research concerning development of future Internet servers concentrate on the following subjects. Firstly, load balancing procedures for clusters are systematically proposed and evaluated [START_REF] Cardellini | Dynamic Load Balancing on Web-Server Systems[END_REF][START_REF] Park | Adaptive Load Balancing Mechanism for Server Cluster[END_REF][START_REF] Shan | Modelling and Performance Analysis of QoSaware Load Balancing of Web-Server Clusters[END_REF][START_REF] Zhang | Workload-aware Load Balancing for Clustered Web Servers[END_REF][START_REF] Zhang | Web Server Load Balancing: A Queuing Analysis[END_REF]. Secondly, the software of individual Internet server nodes is modified to satisfy average response time for 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]. Thirdly, a possibility of dynamic reconfiguration of the clusters to reduce power consumption [START_REF] Chen | Energy-aware Server Provisioning and Load Dispatching for Connection-Intensive Internet Services[END_REF][START_REF] Guerra | Improving Response Time and Energy Efficiency in Server Clusters[END_REF][START_REF] Pinheiro | Dynamic Cluster Reconfiguration for Power and Performance[END_REF][START_REF] Rusu | Energy-efficient Real-time Heterogeneous Server Clusters[END_REF] or to compensate failure of some nodes [START_REF] Christodoulopoulou | Fast and Transparent Recovery for Continuous Availability of Cluster-based Servers[END_REF][START_REF] Kim | A Load Cluster Management System Using SNMP and Web[END_REF] are investigated. In this paper the third of the abovementioned research paths will be developed in detail.

The research reported in this paper constitute a part of long-term programme that concentrates on applications of Hierarchical Timed Coloured Petri Nets (HTCPNs) [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF][START_REF] Jensen | Coloured Petri Nets Modelling and Validation of Concurrent Systems[END_REF] for distributed Internet systems modelling, development, and performance evaluation [START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][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] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF][START_REF] Samolej | Coloured Petri Nets Application in a WWW Clusters Modelling and Development Method[END_REF][START_REF] Samolej | HTCPNs Application for Selected Internet Requests Scheduling Algorithms Analysis[END_REF]. The main aim of the programme is to acquire the systematic HTCPNs-based method for Internet systems development. It is planned to develop a set of HTCPNs models for current and future hardware/software subsystems of distributed Internet systems. The models will constitute a set of design patterns or building blocks. The blocks or patterns might be used to compose a virtual prototype of a distributed Internet system. It seems that a main advantage of using HTCPNs as a modelling language is a possibility to acquire both structural and executable model of system. Consequently future developer would have the possibility to model, simulate and evaluate developed system using one formalism. So far preliminary HTCPNs based Internet systems modelling and analysis was introduced [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], and also more mature methodology for systematic modeling and analysis was proposed [START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][START_REF] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF][START_REF] Samolej | Coloured Petri Nets Application in a WWW Clusters Modelling and Development Method[END_REF]. The modelling framework was used for current Internet systems modelling [START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF], analyses of admission control [START_REF] Samolej | Dedicated Internet Systems Design Using Timed Coloured Petri Nets[END_REF] and scheduling [START_REF] Samolej | HTCPNs Application for Selected Internet Requests Scheduling Algorithms Analysis[END_REF] of Internet requests algorithms, and selected cluster load balancing policies modelling and evaluation [START_REF] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF][START_REF] Samolej | Coloured Petri Nets Application in a WWW Clusters Modelling and Development Method[END_REF]. In this paper the method will be extended by a dynamic cluster reconfiguration algorithm model and its performance analysis.

The next subsections of the paper are organised as follows. Firstly, a method of applying the TCPNs for distributed Internet system modelling will be briefly reminded. Secondly, the set of HTCPNs-based patterns will be extended by a new cluster dynamic reconfiguration algorithm. Some algorithm parameters setting rules will also be proposed. Then, simulation results of the algorithm application for an example cluster will be presented and discussed. The final part of the paper will include related works discussion, conclusions and future research plans.

The HTCPNs-based Internet system modelling and performance analysis method applied in this paper combines features from the two formalisms: Queueing Networks [START_REF] Bolch | Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications[END_REF][START_REF] Dattatreya | Performance Analysis of Queuing and Computer Networks[END_REF] and Hierarchical Timed Coloured Petri Nets [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF][START_REF] Jensen | Coloured Petri Nets Modelling and Validation of Concurrent Systems[END_REF] . The models presented in the paper were created using DesignCPN software toolkit [START_REF]Meta Software Corporation: Design/CPN Reference Manual for X-Windows[END_REF] and analysed by its performance evaluation subsystem [START_REF] Linstrom | Design/CPN Perf. Tool Manual[END_REF]. The equivalent results may be easily obtained with CPN Tools toolkit [START_REF] Jensen | Coloured Petri Nets and CPN Tools for Modelling and Validation of Concurrent Systems[END_REF][START_REF] Wells | Performance Analysis Using CPN Tools[END_REF].

Web-Server Modelling Methodology Overview

Internet systems development is one of the rapidly extended branch of computer engineering. The predominant amount of research concerning this area concentrates on developing or applying new practical algorithms or procedures that improve selected features of the system. In most solutions at hoc experimental systems are constructed and analysed to prove the benefits of the improvement proposed [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][START_REF] Park | Adaptive Load Balancing Mechanism for Server Cluster[END_REF][START_REF] Pinheiro | Dynamic Cluster Reconfiguration for Power and Performance[END_REF][START_REF] Rusu | Energy-efficient Real-time Heterogeneous Server Clusters[END_REF][START_REF] Shan | Modelling and Performance Analysis of QoSaware Load Balancing of Web-Server Clusters[END_REF][START_REF] Zhang | Workload-aware Load Balancing for Clustered Web Servers[END_REF]. Research reported in this paper and our previous works [START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][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] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF][START_REF] Samolej | Coloured Petri Nets Application in a WWW Clusters Modelling and Development Method[END_REF][START_REF] Samolej | HTCPNs Application for Selected Internet Requests Scheduling Algorithms Analysis[END_REF] aim at systematisation of modern Internet system development techniques into one consistent methodology. Inspired by research described in [START_REF] Bause | Queueing Petri Nets -a Formalism for the Combined Qualititative and Quantitative Analysis of Systems[END_REF][START_REF] Kounev | Performance Modelling and Evaluation of Distributed Component-Based Systems Using Queuing Petri Nets[END_REF][START_REF] Kounev | SimQPN-A Tool and Methodology for Analyzing Queueing Petri Net Models by Means of Simulation[END_REF] we decided to propose both methodology and software tool based on application of Hierarchical Timed Coloured Petri nets and Queueing Systems, and providing systematic modelling and performance analysis of Internet systems.

The main features of the methodology at its current state of development are:

-Hierarchical Timed Coloured Petri Nets (HTCPNs) [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF][START_REF] Jensen | Coloured Petri Nets Modelling and Validation of Concurrent Systems[END_REF] are used as modelling language, -A set of the so called HTCPNs design patterns (predefined net structures) have been prepared and validated to model typical Internet or web systems components; -The basic patterns are executable models of "classic" and "modified" queueing systems; -Internet or web systems are modelled using the three levels: queueing systems level, packet distribution level, and top system model level; -A set of design rules of composing system models using the patterns has been formulated; -A way of applying the performance analysis subsystem [START_REF] Linstrom | Design/CPN Perf. Tool Manual[END_REF] of DesignCPN software toolkit [START_REF]Meta Software Corporation: Design/CPN Reference Manual for X-Windows[END_REF] for the analysis of the models have been proposed.

The main concept of the methodology lies in a definition of reusable timed coloured Petri nets structures (patterns) giving possibilities for composition of web-server models in a systematic way. The patterns have been divided into three levels described below.

The queueing systems level includes the basic set of the patterns that are TCPNs implementations of queueing systems [START_REF] Bolch | Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications[END_REF][START_REF] Dattatreya | Performance Analysis of Queuing and Computer Networks[END_REF]. So far some "classic" queueing system models, such as -/M/PS/1 , -/M/FIFO/1 were defined [START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][START_REF] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF]. Additionally, some extended queueing system models were proposed, i.e. the queueing system with admission control of serviced items [START_REF] Samolej | Dedicated Internet Systems Design Using Timed Coloured Petri Nets[END_REF], and the queueing systems with real-time scheduling policies for serviced items [START_REF] Samolej | HTCPNs Application for Selected Internet Requests Scheduling Algorithms Analysis[END_REF]. A role of the packet distribution level is to provide some predefined web-server cluster substructures composed from the queueing systems. At this stage of system modelling a queueing system is represented as a separate substitution transition [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF][START_REF] Jensen | Coloured Petri Nets Modelling and Validation of Concurrent Systems[END_REF]. So far some models representing typical current Internet systems structures [START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][START_REF] Samolej | Timing Properties of Internet Systems Modelling Using Coloured Petri Nets[END_REF] and load balancing Internet systems modules [START_REF] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF][START_REF] Samolej | Coloured Petri Nets Application in a WWW Clusters Modelling and Development Method[END_REF] were proposed.

At the top system model level of system description the main components or clusters are highlighted. Each component is usually a substitution transition "hiding" a computer cluster structure.

For the performance evaluation purposes it is possible to define the external input process that generates Internet requests according to an adequate distribution function or according to some historical data. As the complete system model may be treated as an open queueing network, the requests are generated, then sent to the computer system model, and afterward served and removed.

Each Internet request is a HTCPNs token defined as a tuple PACKAGE = (ID, PRT, START TIME, PROB, AUTIL, RUTIL), where ID is a request identifier, PRT is a request priority, START TIME is a value of simulation time when the request is gene-rated, PROB is a random value, AUTIL is an absolute request utilization value, and RUTIL is a relative request utilization value. Request identifier makes it possible to assign unique number to any request. Request priority is an integer value that may be used when requests are scheduled according priority driven strategy [START_REF] Kim | Improving Web Services Performance Using Priority Allocation Method[END_REF]. START TIME 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).

Figure 2 illustrates the system modelling methodology above explained. It includes selected elements of the multi-tier web-system outlined in Fig. 1. The top system model level consists of three HTCPNs substitution transitions representing "input process", "presentation and application layer" and "database layer". The presentation and application layer is executed in the cluster that consist of two computers depicted as FIFO1 and FIFO2 substitution transitions respectively. The cluster belongs to packet distribution level. Each of computers in the cluster are modelled in detail as a -/M/FIFO/1 quequeing system that belongs to the queueing systems level. The model is a HTCPNs subpage that can communicate with the parent page via INPUT PACKS, OUTPUT PACKS and QL port places. The request packets (that arrive through INPUT PACK place) are placed into a queue structure within PACK QUEUE place after ADD FIFO transition execution. TIMERS place and REMOVE FIFO transition constitute a clock-like structure and is used for modelling the duration of packet execution. When REMOVE FIFO transition fires, the first packet from the queue is withdrawn and directed to the service procedure. The packets under service acquire time stamps generated according to the assumed service time calculated using 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][START_REF] Jensen | Coloured Petri Nets Modelling and Validation of Concurrent Systems[END_REF]). The packets are treated as serviced when they can leave OUTPUT PACKS place as their time stamps expired. The number of tokens in TIMERS place defines the quantity of queue servicing units in the system.

The complete system model can be executed and evaluated. It has been assumed that performance analysis will be the main way of the model evaluation. The corresponding DesignCPN toolkit subroutines [START_REF] Linstrom | Design/CPN Perf. Tool Manual[END_REF] are responsible for capturing 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 off-line. At the currently reported version of the software tool for web-server systems modelling and analysis, queue lengths and service time lengths can be stored during the model execution. The performance analysis of models can be applied in the following domains. Firstly, the system instability and bottlenecks may be easily detected. Secondly, the average values of queueing system parameters such as average queue lengths, and average servicing time for the balanced model can be estimated. Thirdly, some individual properties of cluster node structures or load balancing strategies may be observed.

The modeling and analysis method discussed in the paper has been tested so far with good results on small and medium system models (e.g. 2 tiers and up to 15 ququeing systems). To us, much more complex system models may be naturally constructed and examined as DesignCPN [START_REF]Meta Software Corporation: Design/CPN Reference Manual for X-Windows[END_REF][START_REF] Linstrom | Design/CPN Perf. Tool Manual[END_REF] and CPN Tools [START_REF] Jensen | Coloured Petri Nets and CPN Tools for Modelling and Validation of Concurrent Systems[END_REF][START_REF] Wells | Performance Analysis Using CPN Tools[END_REF] software toolkits have been already successfully used for detailed modeling and tracking of big hardware/software systems [START_REF] Jensen | Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use[END_REF][START_REF] Jensen | Coloured Petri Nets Modelling and Validation of Concurrent Systems[END_REF][START_REF] Wells | Simulation Based Performance Analysis of Web Servers[END_REF]. The analysis method, based on performance reports collected during simulation, do not suffer from state explosion problem, so it also should give stable results in complex model system assessing. Moreover, the detailed evaluation of the method and the software toolkits capabilities for complex system modeling and analysis will be subject of one of our research paths.

Example Dynamic Cluster Reconfiguration Algorithm Evaluation

The distributed structure of current Internet systems entails natural possibility of their reconfiguration. If the system is not efficient enough, some new resources can be added to improve its performance. On the contrary, it is quite natural to switch off some of the nodes when the cluster is evidently underloaded. The states leading to reconfigurations have usually two reasons: an attempt of power consumption reduction, or failures of some system nodes. Currently, the system reconfiguration is made by the administrator, however recent research have shown that it is possible to automate of this procedure [START_REF] Chen | Energy-aware Server Provisioning and Load Dispatching for Connection-Intensive Internet Services[END_REF][START_REF] Guerra | Improving Response Time and Energy Efficiency in Server Clusters[END_REF][START_REF] Pinheiro | Dynamic Cluster Reconfiguration for Power and Performance[END_REF][START_REF] Rusu | Energy-efficient Real-time Heterogeneous Server Clusters[END_REF]. The cluster reconfiguration algorithm works as follows. M QL1 , M QL2 , M QL3 and M QL4 places provide the average queue's lengths of each cluster node. Periodically fired T2 transition collects the average lengths of the queues and adjust the number of "running" cluster nodes to fulfill the following conditions:

the average queue length must be kept between assumed extreme values; the power consumption (the number of running cluster nodes) must be minimised.

The O TABLE place includes the tuple that decides which cluster node is enabled to run. The corresponding tuple values are used as parameters of guard functions attached to T3, T4, T5, and T6 transitions. Only the transitions which guard functions acquire positive value let the requests to go through. The set of "open" transitions define the set of "executing" nodes of the cluster. For example, if the tuple has of (1,1,1,0) value, three cluster nodes are turned on, whereas one (the last) does not work.

The "control" procedure setting the number of the nodes allowed to execution is specified using the following CPN ML code:

(
(1,0,0,0) => (1,1,0,0) |(1,1,0,0) => (1,1,1,0) |(1,1,1,0) => (1,1,1,1)
|(1,1,1,1) => (1,1,1,1) else ( * if average queue length is smaller than or equal * ) ( * to the assumed value * ) ( * then turn of the next cluster node: * ) if(av_ql <= (ref_ql -ref_ql_eps)) then case ot_ of (1,1,1,1) => (1,1,1,0) |(1,1,1,0) => (1,1,0,0) |(1,1,0,0) => (1,0,0,0) |(1,0,0,0) => (1,0,0,0) ( * else do not reconfigure the cluster: * ) else ot_ end;

The main parameters of the procedure are:

average queue lengths (mql1 , mql2 , mql3 mql4 ); assumed average queue length (ref ql); assumed extreme queue length fluctuation value (ref ql eps) that enforces the reconfiguration; frequency of the transition firing.

The procedure has been constructed under assumption that all of the nodes are homogeneous. In the case when it is possible, the procedure tries to reduce number of running nodes, under condition of preservation of average queues lengths for cluster nodes. The condition can be naturally converted into cluster's average response time.

Figure 4 shows queue lengths (Fig. 4a) and number of executing cluster nodes (Fig. 4b) in the cluster controlled by the example dynamic reconfiguration procedure during the sample simulation. After 2000000 time units the external system load was reduced. That caused activation of the reconfiguration procedure. The procedure has kept the average queues lengths at the same level, and has modified number of executing cluster nodes. In a typical Internet system all the cluster nodes would have been servicing the requests. In the modelled system some servers have been turned off for some amount of time. The number of executing cluster nodes can be directly interpreted as an amount of power needed for efficient service of the acquired requests stream [START_REF] Pinheiro | Dynamic Cluster Reconfiguration for Power and Performance[END_REF]. It can be easily calculated that the reconfiguration procedure saved approximately 20% of power in the case modelled by this experiment. One of the earliest research results were these published in [START_REF] Pinheiro | Dynamic Cluster Reconfiguration for Power and Performance[END_REF]. The authors proposed an algorithm of power-aware dynamic homogeneous cluster reconfiguration. The input for the algorithm are CPU, disk and network interface utilisations and their dynamics. The dynamics of the input is interpreted by PID control algorithm.

In [START_REF] Rusu | Energy-efficient Real-time Heterogeneous Server Clusters[END_REF] and [START_REF] Guerra | Improving Response Time and Energy Efficiency in Server Clusters[END_REF] the authors independently propose a set of solutions dedicated for heterogeneous computer clusters treated as real-time systems. Firstly, a new on/of policy has been proposed that causes turn on/off machines according to their power efficiency. Secondly, a possibility of Dynamic Voltage Scaling (DVS) application in cluster power management has been analysed.

A set of interesting dynamic reconfiguration policies dedicated to Internet services keeping long-lived connections has been proposed in [START_REF] Chen | Energy-aware Server Provisioning and Load Dispatching for Connection-Intensive Internet Services[END_REF]. The proposed solutions use forecasting techniques, load balancing, and load skewing for reduction of the cluster power consumption.

In [START_REF] Heath | Energy Conservation in Heterogeneous Server Clusters[END_REF] the problem of heterogeneous computer cluster power consumption reduction is tackled by attempt to find the best Internet requests distribution among the cluster nodes. An iterative optimisation algorithm that evaluates off-line the space of Internet requests distributions and cluster configurations has been applied to solve the problem.

In [START_REF] Kim | A Load Cluster Management System Using SNMP and Web[END_REF] and [START_REF] Christodoulopoulou | Fast and Transparent Recovery for Continuous Availability of Cluster-based Servers[END_REF] dynamic reconfiguration policies have been applied for the modification of cluster structure, where some nodes were failed.

The dynamic cluster reconfiguration algorithm shown in this paper can be treated as a simplified version of policies proposed in [START_REF] Rusu | Energy-efficient Real-time Heterogeneous Server Clusters[END_REF][START_REF] Guerra | Improving Response Time and Energy Efficiency in Server Clusters[END_REF]. The main algorithm input data (queue lengths) come from typical system performance values. The cluster model is constructed on the basis of our previous research [START_REF] Rak | Distributed Internet Systems Modeling Using TCPNs[END_REF][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] Samolej | HTCPNs-based Tool for Web-server Clusters Development[END_REF][START_REF] Samolej | Coloured Petri Nets Application in a WWW Clusters Modelling and Development Method[END_REF][START_REF] Samolej | HTCPNs Application for Selected Internet Requests Scheduling Algorithms Analysis[END_REF], and can be easily related to the one proposed in [START_REF] Guerra | Improving Response Time and Energy Efficiency in Server Clusters[END_REF].

Conclusions and Future Research

An extension of HTCPNs-based software tool for Internet systems modelling and evaluation has been proposed in the paper. After the extension the tool provides new possibilities for modeling and analysis of dynamic cluster reconfiguration algorithm using executable model. Some implementation details of the algorithm has been presented and discussed. Advantages of the algorithm has been preliminary assessed by simulation.

The paper may also be treated as an attempt to systematisation and generalisation of current research concerning efficiency of current and future Internet systems. It seems that the results of the research discussed in this paper and the previous ones have proved that it is possible to construct a HTCPNs-based methodology and related software tool for distributed Internet systems modelling, development, and performance evaluation.

Still, the software tool extended in the paper can be applied for modelling and validation of limited structures of Internet systems. Thereafter the main stream of authors' future research will concentrate on developing models for the next structures. In the nearest future, dynamic load-balancing and dynamic cluster reconfiguration policies will be systematically modelled and assessed by the correspondingly extended software tool. Some improvements of the previously proposed policies are also expected.

So far simulation and performance evaluation were the main ways of the modelled system analysis in the proposed method. However, recent research results announced in [START_REF] Jensen | Coloured Petri Nets Modelling and Validation of Concurrent Systems[END_REF][START_REF] Szpyrka | Analysis of RTCP-nets with Reachability Graphs[END_REF] seem to provide the possibility to effective analyse Timed Coloured Petri Nets using the modified reachability graphs. The attempt of application of the mentioned analysys methods to system models presented in this and the previous papers will be another subject of the authors' research.

Fig. 1 .

 1 Fig. 1. Hardware configuration of an example multi-tier Internet system.

Fig. 2 .

 2 Fig. 2. An overview of HTCPNs-based Internet systems modelling methodology.

Fig. 3 .

 3 Fig. 3. HTCPNs model of example dynamic cluster reconfiguration algorithm.

Figure 3

 3 Figure3includes a HTCPNs-based model of computer cluster where an example power-aware dynamic cluster reconfiguration algorithm was implemented. The model belongs to set of patterns assigned to packet distribution level (comp. sect. 2). The cluster consist of 4 computers represented as FIFO1..FIFO4 substitution transitions, where each transition is attached to a FIFO queueing pattern. Internet requests serviced by the cluster arrive through PACKS2 port place and lives the cluster through the PACKS13 one.The cluster reconfiguration algorithm works as follows. M QL1 , M QL2 , M QL3 and M QL4 places provide the average queue's lengths of each cluster node. Periodically fired T2 transition collects the average lengths of the queues and adjust the number of "running" cluster nodes to fulfill the following conditions:

Fig. 4 .

 4 Fig. 4. Queue lengths (a) and number of executing servers (b) -under different load conditions.

  * input: table of running nodes, queue lengths, * )

	( *	reference queue length, * )
	( *	queue length insensitivity zone; * )
	( * output: new table of running * )
	fun set_ot(ot_: ON_TABLE,
	mql1_: MEAN_TABLE, mql2_: MEAN_TABLE,
		mql3_: MEAN_TABLE, mql4_: MEAN_TABLE,
		ref_ql: INT, ref_ql_eps: INT)=
	let
	( * calculate average queue length: * )
	val av_ql=count_av_ql4(ot_,mql1_,mql2_,mql3_,mql4_)
	in
	( * if average queue length is bigger then or equal * )
	( * to the assumed value * )
	( * then turn on the next cluster node: * )
	if (av_ql >= (ref_ql + ref_ql_eps))
	then
	case ot_ of

Related WorkThe need of dynamic cluster reconfiguration in future Internet systems was noticed by several authors making independent research.