Narasimha Raghavan
email: raghavan@ifi.uio.no

Roman Vitenberg
email: romanvi@ifi.uio.no

Hein Meling
email: hein.meling@uis.no

Reliability Modeling and Analysis of Modern Distributed Interactive Multimedia Applications: A Case Study of a Distributed Opera Performance

Keywords: Reliability Analysis, Reliability Block Diagrams, Stochastic Activity Networks, World Opera, Distributed Interactive Multimedia Applications

With the increase in processing power of computers, proliferation of specialized software and hardware, and the availability of greater communications bandwidth, it is possible to deploy more demanding modern Distributed Interactive Multimedia Applications such as World Opera. The World Opera application realizes the vision of a distributed real-time opera performance in which artists who are distributed around the globe are interacting with each other as though they were co-located. The application is driven by the artistic consortium that encompasses several major opera houses worldwide. In this paper, we build a high-level reliability model to predict the system reliability of the deployed architecture for supporting World Opera. Furthermore, we conduct a sensitivity analysis to understand the reliability requirements that individual components need to meet in order to provide desired system reliability.

Introduction

Recently we have been witnessing a proliferation of Distributed Interactive Multimedia Applications (DIMAs), such as Massive Online Multiplayer Games (MOMG) [START_REF] Hampel | A peer-to-peer architecture for massive multiplayer online games[END_REF] and video conferencing systems. These applications are characterized by interactive exchange of voice, video, control, and other data (such as sensor information) between a number of participants through an electronic medium in real-time. Because of its interactive and real-time nature, the paradigm imposes stringent requirements on latency and synchronization.

Classical DIMAs have traditionally been limited in terms of the complexity of interactions, types and numbers of streams, and the number of participants at each location, as we explain in Section 2. With the increase in processing power of the computers, advent of specialized software and hardware, and availability of greater communications bandwidth, it is possible to deploy more demanding modern DIMAs such as World Opera, an application envisioned by the World Opera artistic consortium [START_REF]The World Opera[END_REF]. In this application, artists, musicians and singers who are physically located at different opera houses dispersed across the globe, participate in a single united performance and interact as if they were co-located.

One of the observations made during early experimentation with World Opera performances is that it is notoriously difficult to maintain a smooth technical operation for the entire duration of a performance, even with rigorous preparations. In this paper, we strive to give a rigorous explanation to this phenomenon by modeling the reliability of a World Opera performance. We further conduct sensitivity analysis in order to understand the reliability requirements of the components of the World Opera.

A World Opera Application

The World Opera (WO) consortium and its partners are engaged in conducting distributed, real-time, live opera performances across several world renowned opera houses. Each opera house represents a real-world stage with its own musicians, singers, dancers, and actors. Interaction between the artists is orchestrated by a single conductor present at a single selected stage. Participating artists from different real-world stages map to virtual-world stages, which are projected as video on display devices, and shown to the audience at the local opera house as well as audiences at geographically distributed (remote) opera houses. Additionally, virtual-world stages can display animated cartoon characters mimicking the behavior of the artists at remote stages. The virtual-world and real-world stages together form a mixed-reality stage. A collection of distributed mixed-reality stages together constitute a WO application.

At a high level, a WO performance is organized into several sessions, each representing a time interval during which a specified set of components is in use. A session starts when directors3 at all stages agree on the set of components to be used for the duration of the session.

The WO application exhibit complex interactions between the real-world and virtualworld. These interactions are established on a per-session basis. They require synchronization across several dimensions: spatial, temporal, and precedence.

Spatial synchronization means that real-world locations must be mapped to appropriate locations in the virtual-world. Consider two cameras at a remote stage each capturing video of the upper and lower part of a human body, respectively. When these two video streams are projected to the virtual stages, their spatial location must be correlated so as to produce a single image of the human body.

Temporal synchronization means that artists at a given real-world stage should act in unison and remain synchronized with artists at the remote stages. For example, a singer at a local stage should be synchronized with musicians located at remote stages. Similarly, actors at the local stage should have a correct lip synchronization with respect to the dialogues of actors at remote stages.

Precedence synchronization means that some streams are given a higher priority for processing than the other streams. For example, a stream from the conductor is given a higher priority than a stream from a violinist. These complex interactions depend upon a) the software components such as middleware services and b) hardware components such as cameras, transmitters, audio and video receiving devices, musical instruments used by the artists, and network links.

Component failures taking place during these complex interactions, could severely affect the synchronization between the real-world and virtual-world. This in turn would affect the entire performance.

World Opera Architecture

We provide a brief selective description about details of the deployed World Opera architecture that are relevant to the reliability model in Section 4 and evaluation in Section 5. There are three participating physical stages in the current preliminary deployment scenario. The stages are symmetric: Each stage includes the same number of components of the same type. Specific component types in the deployed architecture as well as the number of components of each type at a stage are shown in Table 1.

Reliability Model for World Opera

It is imperative for WO application to operate smoothly for the entire duration of a performance. The probability for continuous smooth operation is represented by the reliability metric [START_REF] Trivedi | Probability and Statistics with Reliability, Queueing, and Computer Science Applications[END_REF], which is the main focus of our work. The reliability of WO is defined as the probability that the functionality provided by all the components of WO is operational for the duration of the performance, or the mission-time. While in principle it is possible to define an acceptable degraded quality of experience based on reduced functionality (the audience can hear the singer without seeing her), we leave it for future work to consider such metrics. Furthermore, the script for the opera performance is written considering all the participating stages. Hence, the failure of one stage results in the failure of the script, which in turn leads to the failure of the opera performance.

In this section we provide reliability models for the WO application that are used for reliability analysis in Section 5. We employ the Reliability Block Diagram (RBD) [START_REF] Trivedi | Probability and Statistics with Reliability, Queueing, and Computer Science Applications[END_REF] modeling method that captures the operational relations between the components of WO. This method also allows us to predict the reliability requirements of individual components.

For a system consisting of a number of hardware components, RBD represents functional relationships between the components using a series-parallel structure. When connected in a series structure, all components need to be working for a system to be operational. On the other hand, a parallel structure requires that at least one of the components must be working for the system to be operational. A variety of applications have used RBDs for modeling system reliability, e.g. in [START_REF] Nanda | A formal method approach to analyze the design of aircraft flight control systems[END_REF], [START_REF] Roczen | Reliability block diagram methodology applied to gold book standard network[END_REF], [START_REF] Chen | Reliability and availability analysis for the jpl remote exploration and experimentation system[END_REF], and [START_REF] Kervarrec | A realistic reliability and availability prediction methodology for power supply systems[END_REF].

It should be noted that the models only focus on the new set of components installed in opera houses exclusively for WO performances. They do not consider permanent components and functionality inherent to opera houses such as power supplies or physical stage movement because it is assumed that experienced stage engineers of reputed opera houses are able to deliver such functionality with a very high reliability. We now present our modelling assumptions.

Independent failures: In line with an assumption commonly made in the dependability modelling literature [START_REF] Lai | A model for availability analysis of distributed software/hardware systems[END_REF], we consider component failures to be mutually independent. Crash failures: Only crash failures of the components are considered because other failure types are less common. In particular, failures in the network connecting the stages are deemed to have a negligible probability because the network consists of dedicated lines leased from a commercial provider. Similarly, byzantine failures are significantly less typical in the tightly-controlled production environment of WO. Fail-stop failures: All the components are non-repairable during the performance. During WO performance, a repair is considered too time consuming to be practical, and it would severely impact on the performance.

Reliability Block Diagram Models for World Opera

In this section, we present three-level hierarchical RBD models reflecting the deployed architecture of WO. In hierarchical RBD models, lower-level RBD models are used as building blocks in larger higher-level RBD models so that the top-level RBD model corresponds to the overall architecture. Each block in the top-level RBD (see Figure 1a)) represents a participating stage in WO so that the number of blocks is 3, following the actual number of stages. The blocks are connected in a series structure as the failure of any participating stage will lead to the failure of WO. The model reflects the current settings for WO, in which the participating stages have identical architecture with respect to the number of components and component types. Each block at the middle level (see Figure 1b)) of the hierarchy represents a component type used within a stage. Similarly to the top-level RBD, the blocks are connected in a series structure because the failure of any single component type will lead to the failure of a stage which will in turn lead to the failure of the WO performance.

At the bottom of the hierarchy, each block represents one component of a particular type. Since a failure of any single component will lead to a failure of a component type (we do not consider degraded quality of experience in this paper), the blocks are connected in a series structure. To illustrate these points, consider a scenario where 3 cameras capture a stage from three different viewpoints and all these viewpoints are required for the performance. In this case, each block represents a camera with a specified failure rate as shown in Figure 1c). Since we need all the cameras, we connect the blocks representing the cameras in a series structure. Likewise, Figures 1d),1e), 1f), 1g), and 1h) show the RBD models for the following component types: camera workstations, display workstations, projectors, speakers, wired microphones, and wireless microphones, respectively.

R cam R cws R dws R aws1 R aws2 R spk R m R wm R mix R gat Stage1 R proj Stage3 Stage2 a) b) R cam1 R cam2 R cam3 R dws1 R dws2 R dws3 R proj1 R proj2 R proj3 c) d) e) R spk1 R spk2 R apk3 R m1 R m3 R m4 R m2 R wm1 R wm3 R wm4 R wm2 f) g) h)
Fig. 1: Hierarchical RBD models for World Opera with three stages

Evaluation Results

We use SHARPE [START_REF] Sahner | Performance and reliability analysis of computer systems: an example-based approach using the SHARPE software package[END_REF] to construct and evaluate the RBD models shown in Figure 1. We fix the mission-time to 2 hours, representative of most Opera performances. The RBD models are evaluated with the failure rates shown in Table 2. The rates are based on conservative estimates and partially known product failure rates information made available by the manufacturers. While our model is independent of the failure rate distribution, we assumed for our experiments that failure rates are exponentially distributed following conventional practice. We have two objectives for our experiments. First, we evaluate the reliability of a WO performance (i.e., the probability that all the participating stages remain operational for the duration of the performance) under the settings shown in Table 2. Table 3 shows our results wrt reliability and unreliability values for different time points in the course of a WO performance. The mean time to performance failure is 6.38691959 hours. Second, we perform sensitivity analysis in order to derive minimum reliability of the individual components (i.e., the probability that the component is operational for the entire duration of the mission time) that would result in the desirable level of reliability for WO. We consider the target reliability of 0.99 for a three-stage WO, representing that one out of 100 performances fail. This level of reliability would allow a business model in which the audience of the failed performance get free tickets for a new performance.

We used a dependability package [START_REF] Helvik | Dependability analysis with reliability block diagrams[END_REF] for Mathematica [START_REF] Research | [END_REF] to perform the sensitivity analysis on the RBD model shown in Figure 1. As a part of the sensitivity analysis, we vary the combination of the reliability values for different components. Table 4 shows one possible solution out of many solutions of the sensitivity analysis. The table presents the minimum reliability of various component types, that is the probability that all individual components of a specific component type remain operational during the mission time. It also provides the minimum reliability of a single stage, that is the probability that all of the components at a stage remain operational during the mission time.

As the table shows, the "most relaxed" reliability requirement of a component is 0.9997 and most components must support a minimum reliability of 0.99999995 in order to achieve the target reliability for WO. This observation holds for all other possible solutions of the sensitivity analysis. In other words, the component failure rate is required to be very low, e.g., 10 -6 per hour, during the two hour mission time.

R stage1 R stage2 R stage3 0.996656 R cam R mix R cws R dws R aws1 R aws2 R m R wm R gat R pro j R spk 1 -10 -4 1 -10 -6 1 -10 -3 1 -10 -5 1 -2.16 × 10 -4 1 -9 × 10 -4 R cam1 R cam2 R cam3 0.999967 R cws1 R cws2 R cws3 R dws1 R dws2 R dws3 0.9999995 R pro j1 R pro j2 R pro j3 0.999928 R spk1 R spk2 R spk3 0.9997 R m1 R m2 R m3 R m4 R wm1 R wm2 R wm3 R wm4 0.99975

Related Work

While both client-server and P2P teleconferencing applications are wide-spread nowadays, the complexity of most architectures supporting these application stems from the protocols rather than the variety, scale, and complexity of utilized components. Accordingly, the research into fault-tolerance aspects of teleconferencing applications has traditionally been focusing on overcoming network packet losses by decoders [START_REF] Apostolopoulos | Reliable video communication over lossy packet networks using multiple state encoding and path diversity[END_REF], redundant routing [START_REF] Shan | Overlay multi-hop FEC scheme for video streaming over peer to peer networks[END_REF], and network coding techniques [START_REF] Nguyen | Chameleon: Adaptive peer-to-peer streaming with network coding[END_REF]. P2P systems additionally devote a lot of attention to handling node churn [START_REF] Castro | Splitstream: high-bandwidth multicast in cooperative environments[END_REF]. Since these applications are primarily oriented towards desktop users, the architectures designed for these applications can only support limited hardware (microphone and web camera) and software components (client application) per location, limited number of participants at each location, and limited number of simultaneous multi-point communications. This reduces the need for reliability analysis for such architectures. In [START_REF] Katker | A generic model for fault isolation in integrated management systems[END_REF], the authors provide a service dependency model for a teleconferencing scenario, mainly focusing on analyzing faults at the level of network connectivity. Failure of the client-side hardware devices (such as webcamera and microphone) is not considered. In contrast, recently emerging tele-immersive applications are designed to provide more sophisticated features such as extensive configurability, high-resolution audio and video. Such systems typically include a multitude of specialized hardware and software components. To meet the bandwidth requirements of the high resolution audio and video, these systems are designed over the advanced networking infrastructure such as Internet2. Accordingly, network packet losses have a smaller impact on the dependability of tele-immersive applications compared to malfunctioning of individual components.

[17], [START_REF] Yang | Collaborative dancing in tele-immersive environment[END_REF], [START_REF] Zimmermann | Distributed musical performances: Architecture and stream management[END_REF] have shown that these applications benefit the artists community to a great extent. [START_REF] Wu | Implementing a distributed tele-immersive system[END_REF] developed a distributed 3D-tele-immersive system, where the motion of a human body from different geographical locations are captured and shared in a virtual space among the participants. The architecture is mainly designed to deal with video streams and not audio or sensor streams. [START_REF] Zimmermann | Distributed musical performances: Architecture and stream management[END_REF] described a distributed immersive performance application and presented the requirements and challenges it posed for managing the data generated in this environment. [START_REF] Yang | Collaborative dancing in tele-immersive environment[END_REF] presented the experimental results of performing collaborative dancing in the context of a 3D-tele-immersive system. The results conclude that the collaborative dance performance over network is feasible.

To the best of our knowledge, none of the existing tele-immersive applications considered failure scenarios in the design of their architecture. For this reason, the applications developed on top of these architectures do not provide guaranteed quality of experience to the end users in presence of failures. The models that we propose in Section 4 are directly applicable to the reliability analysis of these applications.

Conclusion

We have provided a reliability model for the WO application and a corresponding sensitivity analysis. We show that the currently deployed architecture requires components with very high reliability in order to satisfy the requirement of only one failed perfor-mance out of 100. In the future we would like to extend and generalize the analysis to address the large class of modern tele-immersive applications.

Table 1 :

 1 Components used in each stage in WO architecture

	Component Types	# components
	Camera	3
	Camera workstations	3
	Display workstations	3
	Audio workstation1	1
	Audio workstation2	1
	Projector	3
	Speaker	3
	Wired microphone	4
	Wireless microphone	4
	Mixer	1
	Gateway	1

Table 2 :

 2 Parameter notation and values

	Component Types	Failure rate Reliability
	Camera	λ cam	0.002	R cam
	Camera workstations λ cws 0.00001	R cws
	Display workstations λ dws 0.00001	R dws
	Audio workstation1 λ aws1 0.00001 R aws1
	Audio workstation2 λ aws2 0.00001 R aws2
	Projector	λ pro j 0.006 R pro j
	Speaker	λ spk	0.004	R spk
	Wired microphone λ m	0.002	R m
	Wireless microphone λ wm	0.002	R wm
	Mixer	λ mix 0.0001	R mix
	Gateway	λ gat 0.00001	R gat

Table 3 :

 3 Evaluation Results of the RBD model

	Time (hrs)	Three stages Reliability Unreliability
	0.5	0.924700849 0.0752991508
	1.0	0.855071661 0.144928339
	1.5	0.790685491 0.209314509
	2.0	0.731147545 0.268852455

Table 4 :

 4 Sensitivity analysis results derived from the RBD model

A director is a technician with artistic knowledge responsible for controlling the technical components based on the artistic requirements. One director is present at each stage during the performance.


Diana Comes

Harun Baraki

Roland Reichle

Kurt Geihs
email: geihs@vs.uni-kassel.debaraki@student.uni-kassel.de

BPRules and the BPR-Framework: Comprehensive Support for Managing QoS in Web Service Compositions

For a successful collaboration between enterprises, Web services and service compositions need to fulfill certain QoS (Quality of Service) requirements so that they can be trusted by their clients. Thus, the best services have to be chosen for the composition, the performance of the composition needs to be monitored and in case of QoS deviations, appropriate management actions are required. We propose the BPRules language and the BPR-framework that offer novel capabilities and improved flexibility for the management of BPEL processes with regard to QoS concerns. The BPRules language allows to specify the QoS monitoring of BPEL processes and offers a variety of management actions for controlling the process and for the improvement of its QoS behavior. Thereby, the BPR-framework provides the necessary components to perform the QoS monitoring and to execute the management actions. For the selection of high quality services, the BPR-framework comes with efficient selection algorithms, like our OP T IM P RO algorithm. We present the features of BPRules that we consider as indispensable for managing the services' QoS behavior.

Introduction

Web Services gained much interest through their reliance on XML based standards (e.g. SOAP, WSDL) and their accessibility over the Internet. Web services from different partners may cooperate to form a business process that delivers a higher business value to its clients. In a service oriented architecture (SOA), business processes are commonly realized as Web service compositions. The Web Services Business Process Execution Language, shortly WS-BPEL [START_REF]Web Services Business Process Execution Language Version 2.0, OASIS standard[END_REF] (or BPEL) has emerged as the standard technology for executing such a process. Services need to offer and maintain adequate quality, also known as Quality of Service (QoS) (e.g. response time, availability, reliability) to accomplish clients' expectations. Usually, the QoS values that were negotiated between the client and the service provider are kept in a service level agreement (SLA). We assume that in future service markets, there are multiple services offered from different service providers having the same functionality but with different service levels. Thus, choosing the services with appropriate QoS levels is an important issue for the success of the business process. Unfortunately, undesired situations, like a service becoming unavailable or not responding in the desired time frame, might happen in a dynamic environment like SOA. The malfunction of one single service might cause the failure of the entire process and lead to clients' dissatisfaction. In order to avoid such situations, the business process needs to be continuously monitored and immediate management actions have to be undertaken to improve the business process behavior. In this paper, we address exactly these challenges and propose the BPRules language (Business Process Rules Language) and the BPR-framework which offer novel management capabilities and flexible monitoring of QoS for BPEL processes. The rules specified with BPRules are executed within our BPR-framework, which is responsible with the monitoring of QoS and triggering appropriate corrective actions on the business process when undesired QoS values are measured. Specifying the rules properly may prevent possible SLA violations and ensures a better control of the BPEL process. We especially designed BPRules with features that we envision as mandatory for the QoS management of business processes. Among the features of BPRules are: flexible QoS data retrieval, section control, instance-set handling, a corrective actions set including flexible service selection methods and a dynamic rule set change. The BPR-framework and BPRules go beyond the state of the art by offering novel features like instance set handling and a dynamic rule set change, but also by improving the flexibility of already established features as e.g. for QoS data retrieval, section control and an advanced decision and control support for the business analyst. With regard to these features BPRules provides more sophisticated means to specify management rules compared to already existing approaches. Improved flexibility is also achieved with regard to the service selection strategies, where for each section of the process a different service selection algorithm can be employed depending on the section size (number of involved services) and the expected number of service candidates. Since QoS dimensions vary over time, we designed the BPR-framework to be flexible when new QoS dimensions or new corrective actions need to be considered.

The remainder of the paper is structured as follows. In section 2 we present some foundations about BPEL and QoS. Section 3 presents the BPRules language and its features. The architecture of the BPR-framework is described in section 4. Finally, we compare our approach with related works in section 5 and conclude the paper in section 6. [START_REF]Web Services Business Process Execution Language Version 2.0, OASIS standard[END_REF] is a language for the specification of service compositions and their execution. A BPEL process may consist of several activities, like invoke for calling a Web service, activities for defining loops (e.g. while, repeatUntil ) and conditional activities (e.g. if ). The activities can either be called sequentially (nested inside a sequence activity) or in parallel (nested inside a flow activity). A BPEL instance may be started with the arrival of a request message from the client by the receive or the onMessage activity. After processing the request, the response may be sent back to the client by the reply activity. As an example we consider the bookshop process for buying books in an online shop, which we implemented using BPEL. The process starts with the arrival of a request from the client, which contains the list of books the client wants to purchase. Then, the stock service is invoked and it verifies, whether all of the books from the list are in stock. If this is not the case, the distributor service is invoked to purchase the missing books from a book wholesaler. If the distributor service returns several books with different prices, the books with the minimum prices are selected to be bought. The books are assigned to the client's bill and the billing service is invoked for creating the bill. Finally a bank service is invoked to make the withdrawal from the clients' credit card to the shop account.

Service composition and QoS

Overview

WS-BPEL

We considered QoS dimensions like availability, reliability, response time and cost, but the framework is not limited to these dimensions as it can be easily extended to other QoS properties as well. In our framework, we interpret the QoS of a Web service as described by Zeng et al. [START_REF] Zeng | QoS-Aware Middleware for Web Services Composition[END_REF]. Response time is computed as the duration of the time when the service operation was requested and the time when the result is received by the requestor. It is the sum of the transmission time and the processing time. The cost of the service is the price of invoking an operation of the service. Availability is the probability that the service is accessible. Reliability is the probability that the request is responded correctly in the expected time frame.

Service Composition representation

In the BPR-framework service compositions are represented as trees. This is achieved by transforming the BPEL description file into a BPEL tree. The BPEL activities are represented as tree nodes and the tree structure is built from the BPEL XML file structure. We consider only the activities, which are relevant for the QoS monitoring (e.g. partnerlinks are not included). The BPEL engine creates a new process instance for every request that it receives from the client. In the BPEL process, an abstract service represents the functionality of the desired service. We assume that there are multiple concrete services that provide this functionality but at different QoS levels. Selecting the right concrete services for the composition is known as the service selection problem and is known to be NP-hard [START_REF] Baligand | A Declarative Approach for QoS-Aware Web Service Compositions[END_REF]. We give a short insight of how we handled this problem in section 3.1 and further details can be found in [START_REF] Comes | Heuristic Approaches for QoS-based Service Selection[END_REF]. In Figure 1 we consider a simple BPEL tree for illustration purposes. We have four abstract services: S A , S B , S C , and S D . We denote with S.V the service variants being the set of concrete services that can realize the service S. The QoS requirements for the service selection are specified using our BPRules language. Guaranteeing the fulfillment of the QoS requirements needs runtime monitoring and management if there is a risk of QoS violations. BPRules is a rule-based language that offers management capabilities with regard to the QoS behavior of single Web services and Web service compositions. The business analyst may specify rules for the service process by stating what corrective actions should be undertaken if specific QoS requirements are not met. Appropriately chosen rules enable a proper execution of the business process even when unpredictable problems occur (e.g. a service is not accessible). The rules are specified in BPRdocuments in the BPRules language and are processed by the BPR-framework.

Corrective actions might rank from just notifying the interested parties about certain events, over starting or stopping the process to actions like selecting and replacing some services with others that provide better QoS. The rules are specified in XML and the syntax is validated against the BPRules XSD schema. We developed BPRules with the following design rationales in mind: simplicity, expressivity, reusability and separation of concerns. BPRules is simple to use because rules are specified in XML. The business analyst who specifies the rules is not required to have any programming skills. BPRules is expressive because it provides various features for QoS management, as will be shown in the next section. Reusability is supported by the possibility of reusing elements specified inside the BPR-document. Elements are identified by ids and can be reused throughout the BPR-document by simply referencing the id. Also other BPR-documents can be included or external BPR-documents can be referred to by their URI. We achieve separation of concerns by specifying rules in BPRdocuments which are stored separately from the business logic.

A regular BPR rule consists of a QoS condition which is monitored and the corresponding action which is triggered when undesired QoS values are measured. The action part in turn might enclose several BPR corrective actions available in the actions set of BPRules. A BPR-document contains several elements like sections for the specification of sub-orchestrations and rule sets for grouping rules together. We designed BPRules with several features that we envision as mandatory for the QoS monitoring and management. In the following we give an overview of these features.

BPRules features

Flexible QoS data retrieval: Interpreting and processing the QoS data may be dependent on the period of time when the execution of the process took place. For example, past QoS behavior may be retrieved for a report or analysis while current QoS behavior malfunction may be remediated by updating the process at runtime. With BPRules we can specify rule sets that consider process instances from a specific period of time. For instance, the period may be a time interval in the past or might range from a moment in the past till the actual moment. It can be specified as a concrete time interval (with a start and end date/time) or as a relative period in the form: last x time-unit (e.g.: last 10 hours).

Section Control: For a better control and detection of QoS deviations we can divide the process into several parts, which we call sections. We may define a section by referring to a structured activity with its nested sub-activities (e.g. all activities inside a flow ). Another way for specifying a section is to consider all activities between a start and an end activity inside a sequence. As an example, in our bookshop process we define a section which consists of several activities, involving the invocation of the distributor service for checking if the book is available, then choosing the book with the minimal price and buying it. The Listing 1.1 contains a rule example defined for the distributor section, where a low response time and cost is required. The example also shows the general structure of a rule set and a BPR-rule. Please note here that at some places in the example listings, commentaries are used instead of the lengthy XML syntax for brevity reasons. When the QoS of the section reaches some risky values (response time > 3 s or cost > 0.25) then the distributor service will be replaced with another one that provides better QoS and whose WSDL description is available at the specified URL. The expression element contains the QoS constraints which can be linked by the logical operators AND, OR and NOT to form more complex conditions. We can specify different QoS requirements in different sections. With BPRules it is also possible to establish relations between the QoS of different sections and the entire process. For example a query like this is possible: the response time from the distributor section is less than 1/2 of the response time of the bookshop process. Thus, the business analyst may be informed if the distributor section consumes too much time in comparison to the response time of the entire process, which can be a good indication for a malfunction in the distributor section. Furthermore, this kind of QoS conditions may ensure keeping an appropriate proportion between the QoS parameters between process sections and the process.

Instance-set handling: With BPRules, we can specify a certain set of instances to which the QoS constraints apply. This is an important task since, for example, situations when 2% of the instances failed or over 20% of the instances failed need to be treated differently. While the first case could be tolerable, the second case needs to be addressed adequately. In Listing 1.2 it is stated that if minimum 20% of the instances failed then a select services action should be undertaken to replace the services with others that provide better QoS. OptimPRO"> <s e r v i c e -r e g i s t r i e s > <ws-u r l ><!--u r l t o r e g i s t r y --></ws-u r l > </ s e r v i c e -r e g i s t r i e s > <qos-r e q u i r e m e n t s > <!--r e s p < 3 ; a v a i l > 0 . 9 5 ; c o s t < 0 . 3 --> <!--o b j f = max ( 5 * a v a i l ) / ( r e s p + c o s t ) --> </qos-r e q u i r e m e n t s > </ s e l e c t -s e r v i c e s > </ a c t i o n > </ r u l e > Listing 1.2. A service selection example As described in Listing 1.2, the state of the instances can be queried with the property-check element (line 6). We distinguish between states like FAULTED for instances with activities that have thrown an exception, RUNNING for instances with activities that are still executed, and COMPLETED for instances where all of their activities are completed. For querying the size of the instances set that fulfill or violate the QoS constraints, BPRules offers a set of functions:

FORALL targeting all the instances in the set, EXISTS for at least one instance, MIN nr(%), MAX nr(%), EQUALS nr(%) to refer to a percentage of the total number of instances. With these functions, BPRules makes it possible to trigger appropriate actions according to the runtime behavior of the instances.

Flexible Service selection: BPRules provides extra flexibility for the selection of services. The select-services action from BPRules may be employed for the entire process, for an abstract service or only for some of its sections. It triggers a selection algorithm to search for services in specified service registries and to replace the old services in the process with new ones that provide better QoS. The selection algorithms receive as input the QoS requirements of the process, which consists of the QoS constraints and an objective function to be optimized. In contrast to other works [START_REF] Zeng | QoS-Aware Middleware for Web Services Composition[END_REF], our selection strategies are also able to deal with non-linear objective functions, aggregation functions and constraints.

Our selection action is customizable with regard to the selection method (algorithm). For example, when searching a few services, like within a section, a trivial brute-force search is sufficient, while in a search that involves many services (e.g. for the entire process) during runtime, a more advanced and rapid search is needed. For this purpose, the BPR-framework provides three algorithms, OP T IM S, OP T IM P RO and OP T IM HW eight, that can be employed for the selection of services. For brevity reasons we only present a rough sketch of OP T IM P RO in this paper. Further details about the selection algorithms can be found in [START_REF] Comes | Heuristic Approaches for QoS-based Service Selection[END_REF]. OP T IM P RO is an iterative algorithm and improves the variant found on the root node (the objective value of the variant) with each iteration step. Figure 1 represents a simple iteration example. The QoS of the root node variant is computed by performing a QoS aggregation from the bottom of the tree to the top. The objective value of the root node is computed by applying the objective function to the found variant on the root node. All nodes of the tree are assigned with a priority factor, which means that nodes that are executed more often receive a higher priority. In the following steps, new services are selected for the nodes in the order of their priorities. For each service candidate we make a copy of the root node, where the currently selected service candidate replaces the old service candidate, aggregate the QoS of the root copy variant, check it against the QoS constraints and compute the objective value. If this objective value represents an improvement in comparison to the old root variant, then the root is going to receive the value and the services of its root copy variant, otherwise the root variant remains the same. The variants that no longer can be improved are saved into the list vlist. The same process starts again with a randomly selected service variant. Finally the variants from the vlist are sorted by the objective function and the best found variant is returned. Listing 1.2 (lines 11-18) represents an example of a select-services action defined with BPRules. New services are searched in the service registries. We assume that a service registry is exposed as a web service and accessible via a URL. The methodClass attribute (line 11) is used to specify which of the selection algorithms is employed. In the listing example, the OP T IM P RO algorithm is called. There may be situations when certain services are preferred and it is not desired to replace them during service selection. In this case, we may declare these services in BPRules as fix, which means that they will not be replaced during the selection procedure.

The BPR corrective actions set: BPRules offers several corrective actions which we divided into 4 categories: (1) actions for controlling the BPEL process, (2) actions that are meant to improve the QoS behavior of the process, (3) actions which offer information about the QoS behavior and (4) actions for controlling the rule sets. Table 1 gives an overview of the actions offered by BPRules. The actions from the first category offer support for controlling the process and its instances, like deploying and undeploying the process, or stopping a set of process instances. The actions from the categories (1) and ( 2) trigger changes in the state of the process and the process goes into the managed state. In the managed state, the actions from the categories (1) or ( 2) may be triggered only sequentially in order to avoid process inconsistencies. The actions from the category (2) are meant to improve the QoS behavior of the process, by replacing one or more services with other services that provide better QoS. If errors were detected inside the process, these usually have to be repaired by updating the BPEL file. This kind of correction is supported by our update action, which overwrites the process description file with another file from a given path or registry. The third category is meant to inform the interested parties about the behavior of the process. BPRules can provide information during process execution (e.g.: throw-event, notify-client) but also reports for longer periods of time. For the business analyst BPRules offers different kinds of reports: a regular report, a rules-report, and an error-report. All these reports deliver a good picture of the process behavior to the business analyst. In the rules report the business analyst can see how the rules were executed, which helps him with future rules specifications. The actions described in Table 1 are atomic actions. Usually, for managing the process properly, several actions need to be triggered. For this purpose, the atomic actions can be composed into so called complex actions. BPRules has some predefined complex actions. Also, the business analyst is able to specify its own complex actions which he may reuse. The different kinds of reports and the possibilities of composing actions, defining custom actions or applying manual actions (see the < replace -ws >, < f ix > declarations) deliver an advanced control and decision support for the business analyst. This feature was included as not always a fully automatic management is desired.

Dynamic rule set change:

We may activate or deactivate rule sets at runtime. Active rule sets are those rule sets which are executed, while inactive rule sets are temporarily ignored. We may use the various rule sets for different alarm states analogously to a traffic light system. For example, if the process behaves well, then the active rules could only inform the interested parties about the behavior. In contrast, if the QoS of the process gets worse another rule set could be activated with rules that have more impact on the process, e.g: replacing one or several services. In this way we may adapt the rule sets dynamically at runtime, according to the behavior of the process. This mechanism reduces complexity by removing the rules that are no longer needed from the memory.

Control the process

Deploy/Undeploy Deploys/ Undeploys the process from the specified path or registry identified by a URI.

Stop

Stops the process identified by the processID. All the process instances of this process are stopped. All the requests that are received while the process is stopped, are stored into a request-queue.

Start

Starts the process identified by the processID so that the process is able to receive requests. New process instances are started for the requests from the request-queue if the waiting time in the queue didn't exceed the given threshold (timeout).

Stop-instances

Stops a set of process instances. (E.g.: instances that started within a given time interval) Resume-inst.

Resumes a set of process instances, that were previously stopped. Cancel -instances Cancels a set of process instances.

Improve the QoS process behavior

Update

Updates the BPEL process description (or section) from the specified path or registry identified by a URI.

Replace-ws

Replaces the Web service that realizes a given abstract service with a new concrete service (or replaces an entire list of services). The URL of the WSDL of the new concrete service has to be specified.

Select-services

Selects services with better QoS from the repository and replaces the Web services in the specified section/process/abstract service.

Information about the process behavior

Report

Makes a report about all the monitored artifacts: the measured QoS values, including exceptions and events of a process during a given time period.

Report-rules

Makes a report with the rules that were triggered for a process during a given time period. The report can be created for all rule sets or only for the specified rules.

Report-error

Makes a report with the errors that were encountered during process execution during a given time period.

Notify-client

Sends a message to the client announcing him about e.g. QoS constraints fulfillments/violations or details about the execution.

Throw-event

Generates an event and informs the subscribers.

Custom action

An interested party may implement a customized action for its own specific needs. Therefore the path to the class file that implements the action interface from the BPR-framework has to be provided.

Control the rule sets

SetActive-ruleset Activates or deactivates the rule set identified by an ID.

Reload-ruleset

Reloads a new rule set at runtime. Table 1. Corrective Actions Set from BPRules

BPRules provides also a reload-ruleset action for updating the rules at runtime. This is necessary in a dynamic SOA where partners or contracts may change.

The reload-ruleset action permits overwriting, adding new rules into the rule set or removing rules. We even may retrieve rules from a URI.

4 The BPR-Framework

Architecture and implementation

We have designed and implemented the BPR-framework for evaluating how our BPR-rules impact the QoS behavior of BPEL processes. The processes are executed on the Oracle BPEL Process Manager engine [START_REF]Oracle BPEL Process Manager[END_REF] and the Web services on the Apache Axis2 engine. We have implemented a service registry using a MySQL database where services can be searched or published. Besides the WSDL files of the services, we also store the QoS values promised by the service providers in the registry. The BPR-framework (see Fig. 2) is implemented in Java and it contains several modules: the BPRules Manager (shortly Manager), which is the core module, the QoS Monitor & Aggregator module for QoS monitoring, and the Process Management module for performing the corrective actions. The BPR-documents are stored into the BPR-repository. We distinguish between two execution phases: the initial phase, when all the necessary monitoring artifacts are deployed, and the monitoring phase, when the actual QoS monitoring and management takes place. In the initial phase the Manager loads the BPRdocuments (see Fig. 2, step Ini 1 ) from the BPR-repository. The Manager reads from the BPR-documents which BPEL processes, sections and QoS Parameters are going to be monitored. The service selection algorithm is triggered by the Manager to select appropriate concrete services. The Manager creates a proxy for each of the abstract services, which contains a reference to the URL of the currently selected concrete service. It intercepts all the messages that are transmitted to the concrete service. The Manager may update the endpoint references from the BPEL file with the URL of the proxy. When a service replacement is triggered, the proxy is updated, referencing to another concrete service URL. Currently, the BPR-framework supports synchronous, stateless web services.

For the monitoring we use a feature of the Oracle BPEL engine which offers the possibility to attach sensors to the BPEL activities. Such a sensor may inform when a BPEL activity is started/ended or when a failure occurred. The Manager dynamically attaches sensors to all the activities of the BPEL process. By this, all the monitoring artifacts were created and the BPEL process can be deployed (step Ini 2 ). In the next step (Ini 3 ) the BPR-rules need to be deployed on the rules engine. We employed the Drools rules engine from JBoss for executing the rules. Before deployment, the rules from the BPR-documents are dynamically transformed into Drools files (having the Drools syntax), which can be processed by the Drools engine. Since the BPRules and the Drools rules contain common rules constructions (e.g. condition/action, logic operators) the transformations between the two syntaxes can be done dynamically. We also used the possibility offered by Drools to implement customized functions for percentage, MIN, MAX that are applied to the QoS objects. Finally, the Drools files are deployed to the Drools engine and the initial phase is terminated. During process execution, the sensor messages (from each activity) are delivered to the Manager (step 1). The sensor message contains the instance ID of the process, the sensor ID, the timestamp, the evaluation time (activation or completion of the activity) and whether an error occurred. If the sensor represents the end of a section or of the process, the Manager calls the QoS Monitor and Aggregator to perform the QoS computation of the section or the process instance (steps 2.1, 2.2). The QoS of the section or process are computed out of the QoS of the atomic services within the section or process. Further details about our aggregation algorithm can be found in [START_REF] Comes | A Flexible Approach for Business Processes Monitoring[END_REF]. With these new QoS values, the Manager updates the QoS objects from the Drools memory (step 3.1). The Drools engine permanently evaluates the QoS conditions and in case they are met it delegates the corrective actions to the Process Management (PM) module. Finally, the PM module is able to execute the actions on the process. The Oracle BPEL engine offers a Client API for querying and controlling the BPEL instances (e.g. stopping instances, deploying the process). Our PM module makes use of this Oracle API and additionally adds other necessary actions (e.g. select-services, replace-ws, etc.).

Evaluation

For evaluation purposes we used a Lenovo R60 notebook with Intel Core 2 Duo processor T5600 (2x1,83GHz) with 2 GB memory and Windows XP SP3. As example we used the bookshop process and several other processes and tested the BPRules features. We defined several rules and simulated QoS constraints violations, like services being not available, not responding in the desired time frame or services causing errors and being not reliable. Our experiments revealed that the conditions of several rules might be met simultaneously, which results in the situation that a number of management actions on the process are performed at the same time. To overcome this undesired situation we enhanced the BPR-framework to block a process in the managed state until the actions that are impacting the process are finished. We also added an adjustable mandatory time interval between triggering two consecutive actions that impact the process. We observed that grouping rules into rule sets and activating or deactivating them, makes it much easier for the developers to trace rules. In this respect, the dynamic rule set change offered by BPRules provides an important mechanism to relax the problem of dealing with simultaneously applicable and potentially contradictory rules. So far there are no mechanisms for avoiding contradictory rules. This issue is still left to the business analyst to be solved. In our future work, however, we aim to provide more development support to the business analyst.

Another possibility to deal with contradictory rules is to automatically resolve the conflicts. The authors of [START_REF] Lu | Support for Concurrent Adaptation of Multiple Web Service Compositions to Maximize Business Metrics[END_REF] propose in their architecture a Policy Conflict Resolution module based on business metrics. We plan to analyze if this approach can be adopted for our BPR-Framework. For our bookshop process that has 40 activities we measured the average QoS aggregation time for a process instance as being 0.48 ms. We observed that the aggregation time grows linearly with the number of instances. The time value represents the pure computation time for the QoS aggregation and does not include the time for the database access of QoS data retrieval. For the evaluation of the service selection algorithms we generated multiple BPEL trees with different structures and we varied the number of abstract and concrete services. We performed several experiments for comparing our OP T IM P RO with the genetic algorithm from [START_REF] Canfora | An approach for QoS-aware service composition based on genetic algorithms[END_REF] with regard to computation time and optimality of the solution. Our experiments have shown that OP T IM P RO was faster than the genetic algorithm, in average it needed about 22% of the time of the genetic algorithm. Concerning optimality our algorithm achieved up to 7% better values for the objective function in comparison to the genetic algorithm.

Related Work

By addressing QoS requirements for services, our BPRules language has similar goals as the two languages Quality of Service Language for Business Processes (QoSL4BP) [START_REF] Baligand | A Declarative Approach for QoS-Aware Web Service Compositions[END_REF][START_REF] Baligand | QoS Policies for Business Processes in Service Oriented Architectures[END_REF] and the Web Service Requirements and Reactions Policy (WS-Re2Policy) [START_REF] Repp | Towards Automated Monitoring and Alignment of Service-based Workflows[END_REF] language. All three languages have a similar structure by means of specifying actions to be undertaken upon QoS violations. Even though, BPRules, QoSL4BP and WS-Re2Policy differ in the provided features and syntax. BPRules offers various additional features like: instance-set handling with the possibility to query the state of the instances and the instances' set, dynamic rule set change and the specification of rule sets applied on instances from different time periods, which are not supported by the other languages. Also BPRules provides increased flexibility for the QoS data retrieval for past and/or running process executions, and an advanced control and decision support for the business analyst. Similar to the section control feature from BPRules, the authors from [START_REF] Baligand | A Declarative Approach for QoS-Aware Web Service Compositions[END_REF] are able to query structured activities for QoS. However, they cannot relate QoS parameters from different sections like in BPRules (e.g: the response time from the distributor section is less than 1/2 of the response time of the bookshop process). A crucial action for managing QoS is the service selection action. The service selection is supported by all of the three languages but the used selection algorithms are different. In [START_REF] Baligand | QoS Policies for Business Processes in Service Oriented Architectures[END_REF] it is mentioned that a constraint programming and a backtracking algorithm are used. BPRules may employ our OP T IM S, OP T IM P RO or OP T IM HW eight algorithms which can be triggered depending on the number of the service candidates. Canfora et. al [START_REF] Canfora | An approach for QoS-aware service composition based on genetic algorithms[END_REF] describe a genetic approach for the service selection. We implemented their algorithm because it can be applied also to non-linear objective and aggregation functions. We used the same aggregation functions as [START_REF] Canfora | An approach for QoS-aware service composition based on genetic algorithms[END_REF] and compared our OP T IM P RO algorithm to the genetic algorithm of Canfora. Our evaluations revealed that our algorithm needs less computation time and provide results which are at least as good as the genetic algorithm.

Baresi et. al describe in [START_REF] Baresi | Towards Dynamic Monitoring of WS-BPEL Processes[END_REF] an approach for service monitoring. The authors define monitoring rules in their Web Service Constraint Language (WS-Col) for WS-BPEL processes. In comparison to our language, WS-Col is limited to monitoring and doesn't allow to specify any corrective actions. In their work [START_REF] Leitner | Preventing SLA Violations in Service Compositions Using Aspect-Based Fragment Substitution[END_REF], the authors describe an approach for preventing SLA violations by a dynamic substitution of fragments (equivalent to our sections) at runtime. We may perform a similar kind of substitution with our update action, but in our approach the business analyst has to specify in the rules the exact replacement (e.g. the path) for the section or process. Thus, the work presented in [START_REF] Leitner | Preventing SLA Violations in Service Compositions Using Aspect-Based Fragment Substitution[END_REF] can be considered as an improvement for our update action for a more dynamic substitution of a section, which we plan to adopt in our future work. However, our focus was not on the dynamic substitution of sections. The authors have addressed only this particular substitution aspect in [START_REF] Leitner | Preventing SLA Violations in Service Compositions Using Aspect-Based Fragment Substitution[END_REF]. With our framework we aim to provide a comprehensive support for managing QoS of service compositions, that includes monitoring but also a rich set of corrective actions as well as efficient service selection strategies. The authors of [START_REF] Lu | Support for Concurrent Adaptation of Multiple Web Service Compositions to Maximize Business Metrics[END_REF] also propose a language and a framework for adaptation of Web-Service compositions, which is able to select the appropriate adaptation strategies for different classes of instances. The strategy selection is not only considering QoS dimensions but also business metrics. With BPRules and the BPR-framework we intend to improve the long-term QoS behavior by selecting and replacing services. Thus, in comparison to [START_REF] Lu | Support for Concurrent Adaptation of Multiple Web Service Compositions to Maximize Business Metrics[END_REF] our focus is much more on service selection algorithms and on specifying rules that define when and how to replace services.

Conclusion

Monitoring and managing QoS are crucial tasks that are decisive for the success of the business process. Our BPR-framework addresses exactly these matters and by means of the BPRules language, novel features are provided to overcome possible QoS deviations. BPRules and the BPR-framework offer improved QoS monitoring features, like monitoring QoS over sections, querying the QoS behavior of running instances (instance-set handling, states querying) but also of instances which are already terminated. For managing the services, we provide several corrective actions like starting and stopping instances, service replacement, flexible service selection or dynamic rule set changes. The service selection action from BPRules offers the possibility of choosing the right selection algorithm depending on the number of abstract services and the number of available service candidates. OP T IM P RO, for example, is a very efficient heuristic algorithm suitable for processes with many abstract services. By providing sophisticated support for QoS monitoring, a rich set of management actions and efficient service selection algorithms, BPRules and the BPR-framework constitute a comprehensive solution for the QoS management of Web service compositions.

1 ) 2 )Fig. 1 .

 121 Fig. 1. BPEL Tree example

<

  r u l e s e t i d =" d i s t r i b u t o r "> <p e r i o d > <!--t i m e i n t e r v a l --> </ p e r i o d > <r u l e > <c o n d i t i o n > <c o n s t r a i n t s > <!--min 10 % o f t h e i n s t a n c e s --> <e x p r e s s i o n a p p l y s e c t i o n =" d i s t r i b u t o r s e c t i o n "> <or> <!--r e s p o n s e t i m e > 3 o r c o s t > 0 . 2 5 --> </or> </ e x p r e s s i o n > </ c o n s t r a i n t s > </ c o n d i t i o n > 10 <a c t i o n > <!--from t h e BPR-c o r r e c t i v e a c t i o n s s e t --> 11 <r e p l a c e -ws> < s e r v i c e name="bookshop / D i s t r i b u t o r S e r v i c e "> 12 <wsdl-u r l > <!--u r l t o t h e WSDL o f t h e new s e r v i c e --> 13 </wsdl-u r l > </ s e r v i c e > 14 </ r e p l a c e -ws> 15 </ a c t i o n > 16 </ r u l e > 17 </ r u l e s e t > Listing 1.1. A BPR-rule example for a section

1

  <r u l e i d =" s e l e c t A l l "> 2 <c o n d i t i o n > 3 <c o n s t r a i n t s > 4 <i n s t a n c e s -s u b s e t f u n c t i o n ="MIN">20%</ i n s t a n c e s -s u b s e t > 5 <e x p r e s s i o n > 6 <p r o p e r t y -c h e c k s e l e c t =" s t a t e ">FAULTED</p r o p e r t y -check> 7 </ e x p r e s s i o n > 8 </ c o n s t r a i n t s > 9 </ c o n d i t i o n > <a c t i o n > <s e l e c t -s e r v i c e s methodClass="ALG.

Fig. 2 .

 2 Fig. 2. The BPR Framework


Dimokritos Stamatakis

Nikos Tsikoudis

Ourania Smyrnaki

Kostas Magoutis

Scalability of Replicated Metadata Services in Distributed File Systems

There has been considerable interest recently in the use of highly-available configuration management services based on the Paxos family of algorithms to address long-standing problems in the management of large-scale heterogeneous distributed systems. These problems include providing distributed locking services, determining group membership, electing a leader, managing configuration parameters, etc. While these services are finding their way into the management of distributed middleware systems and data centers in general, there are still areas of applicability that remain largely unexplored. One such area is the management of metadata in distributed file systems. In this paper we show that a Paxos-based approach to building metadata services in distributed file systems can achieve high availability without incurring a performance penalty. Moreover, we demonstrate that it is easy to retrofit such an approach to existing systems (such as PVFS and HDFS) that currently use different approaches to availability. Our overall approach is based on the use of a general-purpose Paxos-compatible component (the embedded Oracle Berkeley database) along with a methodology for making it interoperate with existing distributed file system metadata services.

Introduction

There has recently been a surge in research into the use of distributed consensus algorithms such as Paxos [START_REF] Lamport | The Part-Time Parliament[END_REF] and viewstamped replication [START_REF] Oki | Viewstamped Replication: A New Primary Copy Method to Support Highly Available Distributed Systems[END_REF] in building highly-available configuration management services. The usefulness of this approach for the construction of general-purpose highly-available systems has been highlighted in the past [START_REF] Lampson | How to Build a Highly Available System using Consensus[END_REF]. This line of research has culminated into real, practical services such as Chubby [START_REF] Burrows | The Chubby Lock Service for Loosely-Coupled Distributed Systems[END_REF] and ZooKeeper [START_REF] Junqueira | High-performance Broadcast for Primary-Backup Systems[END_REF], which expose file-system like APIs along with locking services. Other Paxos-compatible systems such as Oracle Berkeley DB [START_REF] Olson | Proceedings of USENIX Annual Technical Conference[END_REF][START_REF] Perl | Data Management for Internet-Scale Single-Sign-On[END_REF] expose a standard key-value API. While such systems have been used for configuration management of heterogeneous distributed middleware and data centers in general [START_REF] Chang | Bigtable: A Distributed Storage System for Structured Data[END_REF][START_REF] Perl | Data Management for Internet-Scale Single-Sign-On[END_REF][START_REF] Redstone | Paxos Made Live: An Engineering Perspective[END_REF], their use in managing other types of metadata has not been sufficiently investigated. What is currently lacking is a study of Paxos-compatible systems under high-throughput scenarios typical of distributed file systems. The high rate of failures and changes in modern data centers call for a high degree of replication (5 or more replicas is not atypical today). In this paper we focus on the use of a Paxos-compatible replicated key-value store as a metadata-server backend for two well-known and widelydeployed distributed file systems: The Parallel Virtual File System (PVFS) and the Hadoop File System (HDFS). We study the scalability of these two systems, which is defined as the ability to sustain performance as the number of replicas grows, under metadata-intensive workloads on Amazon's EC2 Cloud.

Consistent replication has been used in the domain of distributed file systems in the past. Petal [START_REF] Lee | Petal: Distributed Virtual Disks[END_REF] was an early storage system that used Paxos for replicating metadata. Although Petal featured an ambitious design where metadata were fully replicated across all system nodes (potentially tens of them), it was never evaluated for scalability under intense metadata updates at a large system size. Harp [START_REF] Liskov | Replication in the Harp File System[END_REF] used viewstamped replication for handling replica group reconfiguration under failures. Later Boxwood [START_REF] Maccormick | Boxwood: Abstractions as the Foundation for Storage Infrastructure[END_REF] proposed Paxos as a general-purpose primitive for maintaining global state as well as an underlying component of a lock service. Recently, Paxos has been used for configuration metadata management in systems such as Niobe [START_REF] Maccormick | Niobe: A Practical Replication Protocol[END_REF]. Generally speaking, most distributed file systems that use Paxos today are reserving it for infrequently accessed/updated state (i.e., not file system metadata).

Modern distributed and parallel file systems such as pNFS [START_REF] Shepler | Parallel NFS[END_REF], PVFS [START_REF] Ligon | Overview of the Parallel Virtual Fle System[END_REF], HDFS [START_REF] Shvachko | The Hadoop Distributed File System[END_REF], and GoogleFS [START_REF] Ghemawat | The Google File System[END_REF] treat metadata services as an independent system component, separately from data servers. A reason behind this separation is to ensure that metadata access does not obstruct the data access path. Another reason is design simplicity and the ability to scale the two parts of the system independently. Given the overwhelming popularity of this paradigm we focus exclusively on it in this paper. Significant past research has improved the performance and reliability of data access in these systems, through data partitioning and replication, typically implemented in a primary-backup style [START_REF] Liskov | Replication in the Harp File System[END_REF][START_REF] Maccormick | Niobe: A Practical Replication Protocol[END_REF]. The metadata component however, has been traditionally dealt with separately via different techniques and often in an ad-hoc and non-scalable manner.

Existing approaches to high availability of metadata servers in PVFS and HDFS (as well as other similar file systems) are: (a) using a network-accessible disk device such as Amazon's Elastic Block Store (EBS) to store the underlying metadata, enabling an active-backup or active-active scenario (Figure 1-(a), in the case of PVFS); (b) using a checkpoint and roll-forward solution where the metadata server is periodically checkpointing its state and logging each mutation between checkpoints (Figure 1-(b), in the case of HDFS) to a shared store such as EBS or NFS. Drawbacks of option (a) are the need for special protocols and/or hardware for the shared storage-area network, as well as the bottleneck on the I/O path through a SAN server, limiting scalability. Drawbacks of option (b) are the limited amount of state the server can maintain (typically up to the size of main memory) and the need for a shared network file system, again limiting overall scalability.

Our proposed architecture (depicted in Figure 1-(c)) differs from (a) and (b) above by following a consistent-replication approach [START_REF] Lamport | The Part-Time Parliament[END_REF][START_REF] Oki | Viewstamped Replication: A New Primary Copy Method to Support Highly Available Distributed Systems[END_REF] at the file system level, avoiding the SAN or centralized network file server bottleneck, requiring no special hardware, and avoiding limits to overall metadata size. Our approach is to extend a single-system metadata server into a replicated one via combination of three interoperating components: a highly-available (HA) networking layer, identical stateless replicas of the metadata server, and a replicated database.

To make our approach practical, we base it on an existing replicated data store exposing a key-vale API (Oracle Berkeley DB or BDB). For interoperability with that API, metadata servers should be designed with BDB as their underlying store or be retrofitted to it. We have experimented with both options: Our experience with PVFS, a system originally designed to use the BDB keyvalue API, shows that improving the availability of the metadata server through replication can be straightforward in this case. Our experience with HDFS, a system that was not originally implemented over BDB, shows that it is possible to retrofit our solution into the metadata server without much complexity, achieving high availability as well as larger file system sizes than main-memory permits.

Our contributions in this paper are:

-A general methodology for building highly-available metadata services.

-Design and implementation of replicated metadata servers in the context of PVFS and HDFS.

-Evaluation of the above systems on Amazon Web Services' EC2 Cloud.

The rest of the paper is organised as follows. In Section 2 we describe the overall design. In Section 3 we provide the details of our implementation and in Section 4 we evaluate our systems. We describe related work in Section 5 and finally, in Section 6 we conclude.

Design

Our design, depicted in Figure 2, consists of a number of metadata-serving nodes, one of which is designated as the master and the rest as followers. Clients are accessing the master node (accessible through a single client-visible network address) for metadata reads and writes. Each node consists of three software layers: At the top is a network availability layer responsible for dynamically mapping a single client-visible IP address to the node that is currently elected master. At the intermediate layer is the metadata service adapted to map its file system state to a database key-value schema (examples of such a schema are shown in Figures 3 and4). Finally, the bottom tier is a replicated database implementing consistent replication of tabular data exported via a generic keyvalue API. Coordination between the network availability layer and BDB is required upon master failure to ensure that only one layer holds elections and notifies the other of the outcome. The metadata server cache (FS state in Figure 2) follows a write-through policy with clearly defined disk-synchronization points (typically at transaction boundaries) to ensure durability of metadata updates. In some cases however, commiting a transaction may be decoupled from synchronizing with the disk (e.g., when performing group commits), trading off durability with performance.

In the process of commiting a transaction, the master expects a configurable number of acknowledgements from followers. Typical choices for the ack policy are : (a) master must receive acks from all followers; (b) master must receive acks from a weighted majority of electable peers; (c) master commits after receiving a single ack; or (d) master commits immediately without waiting for any ack. Luckily, the interplay between ack policy and group commit can achieve better durability in a replicated system than is possible in a single-node system. For example, when using group commit, a node failure may require undoing some number of the most recently committed transactions on that node during recovery. However, the existence of replicas in other nodes ensures that these transactions can be recovered from the surviving replicas. In this case it is important to choose the right acknowledgement policy and to ensure that replica nodes fail independently of each other. Finally, our design can support multiple masters and thus increase overall throughput by statically partitioning metadata across servers [START_REF] Bhide | A Highly Available Network File Server[END_REF]. Dynamic partition of metadata across servers is another possibility that has been explored in past research [START_REF] Anderson | Serverless Network File Systems[END_REF][START_REF] Weil | Ceph: A Scalable, High-Performance Distributed File System[END_REF] but is outside the scope of this paper.

Implementation

In this section we describe the implementation of our metadata architecture on PVFS and HDFS, two systems that follow the prevailing trend of separating data from metadata services. Our PVFS implementation was straightforward to complete since the PVFS metadata server was already designed to use singlenode BDB as its underlying store. The HDFS implementation required more involved re-design but turned out reasonably straightforward to carry out as well.

PVFS

We first describe the PVFS metadata schema and provide examples of the metadata operations performed when executing client requests. We then describe our transformation of the PVFS metadata server to use the replicated rather than the single-node version of BDB. The PVFS metadata schema (which in not modified by our implementation) is depicted in Figure 3. PVFS uses four types of metadata objects: directories, directory data objects, metafiles, and datafiles, which when combined make up logical objects such as files and directories. These objects are depicted in the schema of Figure 3.

A metafile object (T METAFILE) represents a logical file. It stores metadata such as owner, group, permissions and change/access/modify times about the file. It also stores the datafile distribution (md), controling how data is striped on data servers. A metafile stores an array of data-file handles (dh) and their size (datafile count). Datafile objects (T DATAFILE) store information about the actual content of files (such as their size) in data servers.

A directory object (T DIRECTORY) represents a logical directory. It stores metadata such as owner, group, permissions and change/access/modify times about the directory. It also stores hints such as distribution name (dist name), parameters (dist params), and datafile count (num files). Distribution name and parameters control how data for a new file are striped over the data servers. The datafile count sets the number of datafile objects for a file. The directory object stores the handle to a directory data object. A directory data object (T DIRDATA) describes the contents of each directory object as pairs of the form (file name, handle to directory or metafile object). Next we give an example of the database operations (put/get) performed by the metadata server when executing an mkdir command. File/directory names and handle ids have been picked up randomly. The root directory ("/") of the filesystem maps to a directory object with handle 1 and a directory data object with handle 2. Note that the order of update operations is such as to ensure metadata consistency in the event of a metadata-server failure before the operation has been fully applied to stable storage. In case of failure, a consistency check (similar to the UNIX fsck [START_REF] Vahalia | Unix Internals: The New Frontiers[END_REF]) is necessary to fully restore consistency. mkdir /dir1/:

1. get "de" from handle 1 -→ handle 2. 2. get "dist name", "dist params", "num dfiles" from handle 1. 3. create new directory object with handle 3. 4. put T DIRECTORY, id, gid, permissions, {a,c,m}time into "ds type", "uid", "gid", "permissions", "{a,c,m}time" in handle 3. 5. create new directory data object with handle 4. 6. put T DIRDATA into "ds type" in handle 4 7. put handle 4 into "de" of handle 3 8. get "de" of handle 1 -→ handle 2. 9. put handle 3 under key "dir1" in handle 2. 10. get "directory entries count" of handle 2 -→ X. 11. put "X+1" into directory entries count of handle 2.

The original version of PVFS uses BDB without transactions or locking support. Our implementation modified the PVFS code to start BDB for replication, enabling the locking and transactional subsystems that are required under that mode. As part of the startup process we register the local and remote sites (the replication group), set configuration parameters, and then call for a BDB election. After electing a master, BDB communicates its decision to PVFS via an asynchronous upcall. This upcall is also invoked any time the BDB node state (master or follower) changes. PVFS in turn instructs the network availability layer to switch the client-visible cluster IP address to the new master.

To operate under the transactional BDB mode while avoiding major changes to PVFS, we modified it so as to automatically wrap every database modification within a transaction. We did this by setting the db auto commit flag at server startup. While this method protects standard database accesses, it does not cover cursor operations. For this purpose we explicitly created transactions that protect cursor operations, ensuring that cursor handles are correctly deallocated to avoid running out of locks. Another important configuration setting was the use of master leases for consistent reads under network partitions.

HDFS

HDFS follows a main-memory database [START_REF] Garcia-Molina | Main Memory Database Systems: An Overview[END_REF] approach in its metadata server (also called a NameNode), keeping the entire namespace in main memory while occasionally taking checkpoints and logging each metadata mutation to a log for recovery purposes. Information about the organization of application data as files and directories (their inodes [START_REF] Vahalia | Unix Internals: The New Frontiers[END_REF]) and the list of blocks belonging to each file comprise the namespace image kept in main memory. The persistent record of the image typically stored on disk is called a checkpoint. The locations of block replicas may change over time and are not part of the persistent checkpoint. The NameNode stores metadata mutations in a write-ahead log called the journal.

Our implementation introduces BDB as a storage back-end of the NameNode creating a disk-resident representation of the image, using the schema depicted in Figure 4. HDFS now performs in-place updates to BDB during metadata updates. With this change, the memory-resident data structures of the NameNode can be thought of as a cache rather than a complete image of all metadata. In addition to providing the on-disk permanent locations of the image, BDB completely replaces the HDFS journal and checkpoint for recovery purposes. In the schema of Figure 4, each file and directory in the system maps to a table containing more specific file or directory attributes. In case of a file, a table of type T FILE contains attributes of the file as well as the handles of all blocks in the file. For a directory, a table of type T DIRECTORY contains attributes of the directory and the names of all files in the directory. Those names can be used as keys to further walk the filesystem namespace. The HDFS schema is simpler than that of PVFS but fully matches the semantics of HDFS.

The standard HDFS recovery methodology (checkpointing plus log replay) is replaced by a method in which failure of the master causes a surviving NameNode to be elected new master and to resume operation by accessing a fresh BDB replica. Logging is not completely gone from the system: it still takes place within BDB. Our design improves recovery time over original HDFS by starting from a fresh replica rather than reconstructing metadata from a checkpoint and log replay.

Another key improvement of our design is extending the capacity of a Na-meNode beyond main-memory limits. By using a write-through cache (just as in the case of PVFS) we eliminate cache consistency issues across NameNodes. Our policy is to have a NameNode erase its cache when demoted to a follower and thus a new master HDFS NameNode always starts with a cold cache. The HDFS NameNode should now be extended with the following cache-management actions: During each metadata read, the server looks up its memory-resident data structures and reads from them in the case of a hit or otherwise fetches from BDB. For a metadata update, the server reads from BDB whatever is currently missing from the cache and then performs in-place writes of the modified BDB entries. The NameNode can simplify the creation of memory-resident data structures from table entries read from BDB by invoking high-level operations (such as mknod, mkdir, etc) rather than low-level data structure manipulations.

Durability/performance tradeoffs in a Cloud setup. BDB offers two ways to achieve durability. One way is the use of synchronous writes to a disk log at commit time. Executing in a Cloud environment however means that a virtual disk may be ephemeral (e.g., an Amazon EC2 instance store). In addition, synchronous file system writes on the guest operating system may not result in synchronous writes to an underlying physical disk. Synchronous commits by BDB therefore do not necessarily translate into strong durability guarantees. Another way to achieve durability is the use of BDB's distributed replication protocol where the master collects acks from a number of followers to reach agreement before committing a transaction (Section 2). Combining replication with synchronous commits in a Cloud environment may hurt performance (as our evaluation shows) without in fact achieving stronger durability.

Network high availability. We require a mechanism to be able to assign and relocate an IP address to the current master. We experimented with two approaches: In platforms where we control address allocation and assignment (such as our in-house Eucalyptus Cloud) we used Pacemaker [START_REF] Pacemaker | A Scalable High-Availability Cluster Resource Manager[END_REF] to manage the floating IP address as a cluster resource. We disabled elections at that level (via setting negative election probabilities for all nodes) to avoid conflicts with BDB's independent election process. In a platform such as the Amazon EC2 Cloud that provides custom control over address assignment, we use EC2 elastic addresses to allocate, assign, and relocate a public address. Elastic addresses are Internet routable IP addresses that map to VM-private addresses.

Evaluation

Our experimental setup consists of Amazon EC2 VMs running Debian 5 32-bit Linux. Each VM has one virtual core, 1.7GB of memory, and a 168GB local virtual disk (EC2 instance store) with an ext3 file system. Our baseline software is PVFS version 2.8.1, HDFS version 0.20.205.0, and Berkeley DB version 5.30 configured with a 512MB cache. All PVFS and HDFS installations were configured with a single data-node collocated in the same VM with clients. Key parameters in our tests are: number of replicas; ack policy (one, quorum, all); and synchronous vs. asynchronous commits (sync vs. nosync). nosync transactions are considered committed as soon as their commit record is stored in the log memory buffer. The BDB replication protocol is configured to perform bulk transfers of log updates over the network.

Microbenchmarks

We first evaluate performance of a single metadata server by measuring average response time of 2000 invocations of the mkdir command (a heavyweight metadata operation) using synchronous (sync) or asynchronous (nosync) commits. Table 1 summarizes our results. Standard deviation was small (<3%) in all tests. Our implementation of PVFS is 15%-20% slower than the original PVFS due to the use of transactions and locking. PVFS generally has higher response time compared to HDFS due to its more complex schema and use of many put/get operations (Section 3.1). Our implementation of HDFS matches the performance of original HDFS when it uses a single file to back all database tables (which is also what PVFS does). We tested HDFS with multiple files (one file per BDB table) and found that table creation and open/close operations in the critical path slow down our version considerably (up to 3.3 times) compared to the original. Next we evaluate performance of 3-, 5-, and 10-replicated metadata servers. Figure 5 depicts the average response time of 2000 mkdir operations under four setups: the strictest (sync, all), a Paxos-like configuration (sync, quorum), balancing performance with reliability (nosync, quorum), and the most relaxed (nosync, one). Focusing on HDFS results first, we observe a clear distinction between the nosync setups on the one hand and the sync setups on the other. The former exhibit clearly scalable behavior; the case of (nosync, quorum) is especially interesting since it provides sufficiently strong durability with little performance deterioration for up to 10 replicas. We attribute this to efficient network pipelining due to the use of bulk data transfers and the lack of synchronous commits. The PVFS results are similar except that (sync, quorum) results in only a 20-30% slowdown (rather than factor of two) compared to (nosync, quorum).

Postmark

To evaluate our systems under a more realistic workload we use Postmark [START_REF] Katcher | PostMark: A New File System Benchmark[END_REF], a synthetic benchmark aimed at measuring file system performance over a workload composed of many short-lived, relatively small files. Such a workload is typical of mail and netnews servers used by Internet Service Providers. Postmark workloads are characterized by a mix of metadata-intensive operations.

The benchmark begins by creating a pool of 500 files with random sizes in the range 8-32KB. After creating the files, a sequence of 2000 transactions is performed. These transactions are chosen randomly from a file creation or deletion operation paired with a file read or write. A file creation operation creates and writes random text to a file in blocks of 4KB. File deletion removes a random file from the active set. File read reads a random file in its entirety and file write appends a random amount of data to a randomly chosen file. Each run involves two Postmark clients blasting the metadata server cluster.

Figure 6 depicts Postmark performance with 3, 5, and 10 metadata servers. Average transaction throughput with PVFS is higher than with HDFS due to differences in file I/O performance between the two systems (HDFS is not optimized for low-latency data access). HDFS results clearly highlight the gap between the nosync and sync setups, similar to the gap observed in Figure 5-(b). The key observation is again that the (nosync, quorum) setup provides strong durability guarantees with little performance degradation as the number of replicas grows. PVFS results indicate a somewhat higher drop of (nosync, quorum) compared to (nosync, one) but still within 5-10% of it.

Recovery

In this section we compare the recovery of standard HDFS to our replicated version. The experimental setup for standard HDFS consists of two VMs, one hosting the NameNode and another hosting a helper process producing checkpoints of NameNode state, communicating with the NameNode via the HTTP protocol. We use an elastic block store (EBS) volume remotely-mount on the first VM to store the most recent checkpoint and operation log (Figure 1-(b)). Clients access the NameNode through an EC2 elastic address. Our experiments use a client that creates a number of files and then issues operations on them measuring response time (including retries). In case of failure of the NameNode VM, we restart the NameNode in the second VM, migrate the elastic address to it, and re-mount the elastic block store. Prior to resuming operations, the NameNode must recover its state by loading the last checkpoint and replaying the operation log. The recovery process for our replicated version of HDFS is described in Section 3.2.

Our experiments show that a large fraction of recovery time is spent in establishing the communication path between the client and the new NameNode and (in the case of standard HDFS) remounting the EBS volume. Failover of the elastic IP takes on average 38 sec whereas remounting an EBS volume takes on average 35 sec (24 sec to unmount/detach and 11 sec to attach/mount again). Our experiments show that these steps cannot be parallelized. Table 2 presents our measurements with two standard HDFS setups parameterized by (checkpoint, log) sizes (MB), as well as a triply-replicated HDFS setup. In the former case, NameNode recovery is initiated manually by a script, right after a crash. In the replicated case, failure detection is performed by BDB. The replicated server does not have to wait for the failover of an EBS volume or for reconstruction of metadata state and thus provides significantly lower client outage.

Related work

General fault-tolerance methods typically rely on replication to protect against failures. The main replication mechanisms for high-availability in distributed systems include state machine [START_REF] Schneider | Implementing Fault-Tolerant Services Using the State Machine Approach: a Tutorial[END_REF], process-pairs [START_REF] Gray | Why Do Computers Stop and What Can be Done About it? Technical report[END_REF], and quorum systems [START_REF] Gifford | Weighted Voting for Replicated Data[END_REF]. A class of highly-available configuration management systems based on the replicated state machine approach using distributed asynchronous consensus algorithms such as Paxos at the core [START_REF] Lamport | The Part-Time Parliament[END_REF][START_REF] Oki | Viewstamped Replication: A New Primary Copy Method to Support Highly Available Distributed Systems[END_REF] have recently emerged. Paxos-related approaches have also been used for maintaining configuration information within storage systems such as Petal [START_REF] Lee | Petal: Distributed Virtual Disks[END_REF] and Niobe [START_REF] Maccormick | Niobe: A Practical Replication Protocol[END_REF]. They are also the underlying technology for systems such as Chubby [START_REF] Burrows | The Chubby Lock Service for Loosely-Coupled Distributed Systems[END_REF] and Oracle Berkeley DB [START_REF] Olson | Proceedings of USENIX Annual Technical Conference[END_REF]. The issue of metadata placement and handling in distributed file systems has been a topic of intense research for a long time. Systems such as NFS opted for a centralized metadata server architecture, which allows for a simpler design at the expense of a scalability bottleneck. Other approaches that opted for distributing metadata symmetrically across the system nodes (such as Petal [START_REF] Lee | Petal: Distributed Virtual Disks[END_REF], Frangipani [START_REF] Thekkath | Frangipani: a Scalable Distributed File System[END_REF], and xFS [START_REF] Anderson | Serverless Network File Systems[END_REF]) resulted in complex designs that eventually restricted their applicability. Several modern distributed storage systems such as HDFS [START_REF] Shvachko | The Hadoop Distributed File System[END_REF], PVFS [START_REF] Ligon | Overview of the Parallel Virtual Fle System[END_REF], pNFS [START_REF] Shepler | Parallel NFS[END_REF], and Ceph/RADOS [START_REF] Weil | Ceph: A Scalable, High-Performance Distributed File System[END_REF], separate data and metadata paths avoiding the centalized metadata server bottleneck. Their popularity and impact motivates our focus on them in this paper.

We presented the adaptation of two modern, widely-deployed distributed file systems, PVFS and HDFS, to use a replicated Paxos-compatible key-value database (Oracle Berkeley DB) for achieving high availability of their file-related metadata. We found that high availability and data durability are achievable with minimal performance penalty under metadata-intensive workloads on the Amazon EC2 Cloud. Response time was found to be within 15-20% of the standard (non-replicated version) in the case of a single metadata server replica for both PVFS and HDFS. The replicated metadata server remains practically unaffected (0-5% drop) for higher number of replicas (3-10) when using asynchronous commits (a choice that does not sacrifice durability). Performance is noticeably impacted when turning to synchronous commits under the quorum or all acknowledgment policies. Overall our approach is straightforward, whether the distributed file system is designed for the target key-value API (as in the case of PVFS) or must be retrofitted to it (HDFS), and yields robust, performant distributed file systems that are easy to build and reason about.

Fig. 1 .

 1 Fig. 1. Metadata server architecture options.

Fig. 2 .

 2 Fig. 2. Architecture of replicated metadata server

Fig. 3 .

 3 Fig. 3. The schema used in PVFS.

Fig. 4 .

 4 Fig. 4. The schema used in HDFS.

Fig. 5 .

 5 Fig. 5. Response time of mkdir on 3, 5, 10 replicas (ms).

Fig. 6 .

 6 Fig. 6. Postmark throughput for different replication factors.

Table 1 .

 1 Response time of mkdir on single metadata server (ms).

			PVFS		HDFS
		sync	nosync	sync	nosync
	Original	4.5	4.3	-	3.0
	1-repl single file	5.1	5.1	3.7	3.0
	1-repl one file per table	-	-	10.9	10.9

Table 2 .

 2 Recovery time components and total outage (sec).

		Network/disk	State	Total client
		failover	reconstruction outage
	HDFS (8, 1)	38+35	7.3	80.3
	HDFS (0.8, 1)	38+35	1.9	74.9
	HDFS 3-replicas	38	0	38

Acknowledgments

We thank Yiannis Kesapidis, Konstantinos Chasapis, and Yiannis Linardakis for contributions to the PVFS implementation. We thankfully acknowledge the support of the European ICT-FP7 program through the CUMULONIMBO (STREP 257993) project, and of Amazon Web Services through an Education Grant.