بهینه سازی زمانبندی در کوپلینگ خدمات مستقل به عنوان یک معامله گرید

Due to the dynamic properties of autonomous resource providers, the coupling of independent services as a Grid transaction may abort with inconsistency. In many situations people would resort to compensation actions to regain consistency; consequently there comes the issue of compensation-cost. To handle such an issue, for the first time we set up a costing model for the all-or-nothing transaction of Grid services, and introduce the ECC metric to evaluate related service scheduling. The analysis of ECC estimation is based on the so-called CC-PreC commit pattern, which is an abstract of a category of common use cases of commit handling. Our analysis theoretically illustrates the high degree of computational complexity of scheduling optimization with respect to the cost labeling, timing and order of requests. Under certain typical conditions we prove that infinite possible schemes of scheduling can be reduced down to a finite set of candidates of scheduling. Especially based on the ECC metric, the caution scheduling is thoroughly investigated, which as a basic policy could be employed in certain common scenarios, and under which the intuitive product-first or cost-first schemes are justified in several typical situations.

With the evolvement of Grid applications, Grid scheduling problems attract more and more people seeking optimal approaches for fulfilling their work. At the same time, the increasing demands for a transaction guarantee from a variety of Grid computations are raising concerns. However, dynamic and autonomous behaviors of the underlying Grid resource providers might make scheduling problems in transaction processing more subtle or sophisticated. Challenging questions might arise [1] like this one: given that all jobs of the work are supposed to satisfy some constraints such as the overall atomicity, how can we best schedule the work onto different resources,1 so that we cater to the constraints whilst trying to minimize expenditure or maximize efficiency? Furthermore, by what metrics do we measure the expenditure or efficiency? In this paper, we try to explore similar issues with emphasis on compensation-cost analysis. More precisely, the primary constraint herein is to couple necessary independent Grid services on demand as an all-or-nothing Grid transaction, under which this work is devoted to providing a theoretical basis to seek an appropriate scheduling for lower compensation-cost or shorter time-span. Since the issue of optimizing scheduling for lower compensation-cost is still lacking systematic investigation in the service computing fields, we start with basic models and notions, and then try to identify and solve typical problems. The calculability, complexity, and workability of scheduling schemes, and trade-offs are of major interest. For a better understanding, we outline our contributions first: (a) a formal pattern for time-related composite transactions; (b) a formal model for pricing the compensation-cost of aborted transactions; (c) metrics and a framework of probabilistic analysis for evaluating scheduling. The rest of this paper is organized as follows. First, related researches are reviewed in Section 2. The terminology and conditions are given in Section 3, and subsequently the underlying CC-PreC commit pattern is introduced and explained in Section 4. After basic models for scheduling analysis are prepared in Section 5, two basic schedulings, i.e., the caution and the efficiency-first, and the computation of their ECC are presented in Section 6 while the time-metric analysis of these schedulings is given in Section 7. In-depth discussions of scheduling optimization on ECC are developed in Section 8. Illustrative numerical examples are included in Section 9. After the analysis of computational complexity in Section 10, the paper is concluded in Section 11.

The approach of estimating compensation-cost is based on the pricing model of published and relatively-fixed cost of resources (service or goods), which is widely adopted by retail-stores, department stores, ticket agents, or declared by business contracts online or offline, etc. According to business conventions, the service provider should clearly post the compensation-cost for their services in advance. The label of compensation-cost can be set up through a statistical calculation or by experience. It is the responsibility of SP to price the compensation-cost, and it is a normal practice that a dynamic cost should be converted into a step-price or even a single price on average, since the very detail of the price construction is not of interest for most of customers. All these aspects together define our approach’s applicability while the usability depends on the availability of success ratio and/or the compensation-cost label. The main content of this paper is devoted to quantitatively studying the compensation-cost issue related to scheduling optimization for the CC-PreC commit pattern of Grid transaction. During the analysis, several economics indexes like ECC, FCP and decision time are introduced first to measure the effect of scheduling algorithms. The joint usage of ECC metric, pricing and probability models for fixed services is a key contribution here, which is also crucial for similar quantitative analyses related to compensation-cost. From the socioeconomic point of view, cost consists of two parts [5]: the technical and the mental. Our analysis on ECC of scheduling can serve as a basis for understanding and reducing the technical cost; the proposed basic schedulings may ease users or their agents of the trouble of sophisticated trade-offs in certain situations considering the very high computational complexity of scheduling optimization. As a major theoretical result we have proven certain kinds of common cases can be reduced to simple ones, which can be further utilized in developing middleware or agents to assist customers to well assemble services as a transaction. Indeed, more efforts are needed to extend our approach to broader scenarios beyond the Simple Abort-Predicate and/or fixed cost-label model. To model more real-world scenarios, the CC-PreC pattern and the Pricing model may need some extensions to make it more adaptive and more feasible. This paper is a step in that direction. Future work may concern: (1) the all-or-nothing transaction scenarios in Delay Tolerant Network, where the randomicity of the composite application is dominated by the diversity and uncertainty of communication delay, which makes the analysis of ECC even more complex but also crucial; (2) the compensation-cost optimization for typical changeful pricing systems, e.g., where the compensation-cost label is a linear function of time. A possible extension of the ECC computing model may be developed for the scenarios where for a Grid service gsigsi of a specific function FF there is the maximum group, denoted as group(gsi)(gsi), of candidate Grid services that can provide the same service function FF as gsigsi. To apply our models in this case, we can coin a virtual Grid service View the MathML sourcegsi¯ to stand for the group(gsi)(gsi) equivalently. Let group(gsi)={iv|v∈Ψm}(gsi)={iv|v∈Ψm}, the average success probability of View the MathML sourcegsi¯ can be expressed as View the MathML source1−∏v=1m(1−ρiv). Whereas the average compensation-cost label of View the MathML sourcegsi¯, View the MathML sourceCC(gsi¯), depends on how to try to obtain a successful Grid service out of group(gsi)(gsi). In the case that the Grid services of group(gsi)(gsi) are attempted sequentially, the View the MathML sourceCC(gsi¯) is estimated as View the MathML sourceCC(gsi¯)=∑k=1m∏v=1k−1(1−ρiv)⋅ρikcik(t)/[1−∏v=1m(1−ρiv)], which indicates that, in general, the View the MathML sourceCC(gsi¯) is a multi-step function of time. This reminds us that the ECC optimization analysis regarding CC-labels of multi-step time function is very much needed, which, however, is much more difficult to approach, and is far beyond the scope of this paper. As to the implementation of such a virtual Grid service View the MathML sourcegsi¯, we recommend utilizing the WS-Service Group (WSRF-SG) [24] approach to form a by-reference collection of web services that offer the same function. Another straight broadening of the application of our analysis models is to relax the constraint of tr(j)>tp(j)tr(j)>tp(j). However, the relevant ECC estimation must involve the statistical distribution model of the network delay, and it has to take into account the probability that a successful service commit might be mistaken as failed due to its late response. Since this may disperse our focus and introduce much additional mathematical processing, we do not investigate it further in this paper.