In large-scale, distributed systems such as Grids, an agreement between a client and a service provider specifies service level objectives both as expressions of client requirements and as provider assurances. From an application perspective, these objectives should be expressed in a high-level, service or application-specific manner rather than requiring clients to detail the necessary resources. Resource providers on the other hand, expect low-level, resource-specific performance criteria that are uniform across applications and can be easily interpreted and provisioned. This paper presents a framework for service management that addresses this gap between high-level specification of client performance objectives and existing resource management infrastructures. The paper identifies three levels of abstraction for resource requirements a service provider needs to manage, namely: detailed specification of raw resources, virtualization of heterogeneous resources as abstract resources, and performance objectives at an application level. The paper also identifies three key functions for managing service-level agreements, namely: translation of resource requirements across abstraction layers, arbitration in allocating resources to client requests, and aggregation and allocation of resources from multiple lower-level resource managers. One or more of these key functions may be present at each abstraction layer of a service-level manager. Thus, layering and the composition of these functions across abstraction layers enables modeling of a wide array of management scenarios. The framework we present uses service metadata and/or service performance models to map client requirements to resource capabilities, uses business value associated with objectives to arbitrate between competing requests, and allocates resources based on previously negotiated agreements. We instantiate this framework for three different scenarios and explain how the architectural principles we introduce are used in the real-word.

In large-scale, distributed systs such as Grids, an agreent between a client and a service provider specifies service level objectives both as expressions of client requirents and as provider assurances. Ideally, these objectives are expressed in a high-level, service- or application-specific manner rather than requiring clients to detail the necessary resources. Resource providers on the other hand, expect low-level, resource specific performance criteria that are uniform across applications and can easily be interpreted and provisioned.

Using services across domain boundaries, be they organizations or self-managing components of large distributed systs, requires the setup of an agreent between the parties involved, defining the terms of the service including interfaces, security and Quality of Service (QoS) properties. In an on-dand environment in which services are contracted on a short notice, the establishment of an agreent as well as the setup of agreement-fulfilling and monitoring systs of the parties involved must be spontaneous and, partially, automated. WS-Agreent is a standardization effort being conducted in the Global Grid Forum defining a simple agreent establishment protocol, an XML-representation of agreements and agreent tplates as well as a runtime agreement monitoring interface, based on the WSRF set of standards.

This paper describes a novel contract based approach for defining, deploying, monitoring and enforcing service level agreements (SLA) in a dynamic e-Business environment. The current trend in application service delivery is to...

In typical video delivery systems offering programs on-demand, service should be be nearly immediate and continuous. A video server can provide this type of service by reserving sufficient network and server resources for the duration of playout. Scalability and reduced cost can be achieved using a single channel to serve multiple customers waiting for the same program (referred to as batching). Batching is especially useful during high load periods typically occuring during evening prime time hours. Typical channel allocation algorithms use a greedy, allocate-as-needed policy. Variations in system load can cause these algorithms to suffer poor and unpredictable short-term performance, and non-optimal long term performance. In this paper, we develop a set of realistic workloads, identify the limitations of greedy allocation algorithms, and propose a set of rate-based allocation schemes to solve these limitations. The performance of various video delivery systems are simulated and compared. The rate-based policies are shown to be robust for the workloads examined, and are easy to implement.

In a distributed environment, presentation of structured, composite multimedia information poses new challenges in dealing with variable bandwidth (BW) requirement and synchronization of media data objects. The detailed knowledge of BW requirement obtained by analyzing the document structure can be used to create a prefetch schedule that results in efficient utilization of system resources. A distributed environment consists of various system components that are either dedicated to a client or shared across multiple clients. Shared system components could benefit from Fine Granularity Advanced Reservation (FGAR) of resources based on true BW requirement. Prefetching by utilizing advance knowledge of BW requirement can further improve resource utilization. In this paper, we describe the JINSIL retrieval system that takes into account the available bandwidth and buffer resources and the nature of sharing in each component on the delivery path. It reshapes BW requirement, creates prefetch schedule for efficient resource utilization in each component, and reserves necessary BW and buffer. We also consider good choices for placement of prefetch buffers across various system components.

In a multinode data sharing environment, different buffer coherency control schemes based on various lock retention mechanisms can be designed to exploit the concept of deferring the propagation or writing of dirty pages to disk to improve normal performance. Two types of deferred write policies are considered. One policy only propagates dirty pages to disk at the times when dirty pages are flushed out of the buffer under LRU buffer replacement. The other policy also performs writes at the times when dirty pages are transferred across nodes. The dirty page propagation policy can have significant implications on the database recovery time. In this paper, we provide an analytical modeling framework for the analysis of the recovery times under the two deferred write policies. We demonstrate how these policies can be mapped onto a unified analytic modeling framework. The main challenge in the analysis is to obtain the pending update count distribution which can be used to determine the average numbers of log records and data I/Os needed to be applied during recovery. The analysis goes beyond previous work on modeling buffer hit probability in a data sharing system where only the average buffer composition, not the distribution, needs to be estimated, and recovery analysis in a single node environment where the complexities on tracking the propagation of dirty pages across nodes and the buffer invalidation effect do not appear.

In a video-on-demand server, resource reservation is required to guarantee continuous delivery. Hence any given storage device (or a striping group treated as a single logical device) can serve only up to a fixed number of client access streams. Each storage device is also limited by the number of video files it can store. For the reasons of availability, incremental growth, and heterogeneity, there may be multiple storage devices in a video server environment. Hence, one or more copies of a particular video may be placed on different storage devices. Since the access rates to different videos are not uniform, there may be load imbalance among the devices. In this paper, we propose a dynamic placement policy (called the Bandwidth to Space Ratio (BSR) Policy) that creates and/or deletes replica of a video, and mixes hot and cold videos so as to make the best use of bandwidth and space of a storage device. The proposed policy is evaluated using a simulation study.

In order to guarantee continuous delivery of a video stream in an on-demand video server environment, a collection of resources (referred to as a logical channel) are reserved in advance. To conserve server resources, multiple client requests for the same video can be batched together and served by a single channel. Increasing the window over which all requests for a particular video are batched results in larger savings in server capacity; however, it also increases the reneging probability of a client. A complication introduced by batching is that if a batched client pauses, a new stream (which may not be immediately available) needs to be started when the client resumes. To provide short response time to resume requests, some channels are set aside and are referred to as contingency channels. To further improve resource utilization, even when a nonbatched client pauses, the channel is released and reacquired upon resume. In this paper, we first develop an analytical model that predicts the reneging probability and expected resume delay, and then use this model to optimally allocate channels for batching, on-demand playback, and contingency. The effectiveness of the proposed policy over a scheme with no contingency channels and no batching is also demonstrated.

One major drawback of a RAIDS disk array system is that an update to a data block may involve four disk accesses. Such a high overhead is especially undesirable for workloads with a high update rate. In this paper, we present a dynamic parity grouping (DPG) scheme for efficient parity buffering to reduce the write overhead of a RAID-5 system. In DPG, special parity groups are dynamically created for data blocks with high write activity, referred to as the hot data blocks, in addition to default parity groups for the remaining cold data blocks. The parity blocks of the special parity groups are then buffered in the disk controller cache. As a result, the number of disk accesses on a write to a hot data block is reduced to two.

In an on-demand video server environment, clients make requests for movies to a centralized video server. Due to the stringent response time requirements, continuous delivery of a video stream to the client has to be guaranteed by reserving sufficient resources required to deliver a stream. Hence there is a hard limit on the number of streams that can be simultaneously delivered by a server. The server can satisfy multiple requests for the same movie using a single disk I/O stream by sending the same data pages to multiple clients (using the multicast facility if present in the system). This can be achieved by batching requests for the same movie that arrive within a short duration of time. In this paper, we consider various policies for selecting the movie to be multicast. The choice of a policy depends very much on the customer waiting time tolerance before reneging. We show that an FCFS policy that schedules the movie with the longest outstanding request can perform better than the MQL policy that chooses the movie with the maximum number of outstanding requests. Additionally, if the user behavior can be influenced by guaranteeing maximum waiting time then it may be beneficial to pre-allocate a fixed number of streams for popular movies. Finally, we demonstrate using empirical distribution for movie requests, that a substantial reduction (of the order of 60%) in required server capacity can be achieved by batching.

Clustering multiple computing nodes has become increasingly popular for reasons of capacity, availability and cost. One approach to clustering is the data sharing approach where a number of loosely coupled nodes share a common database. In this environment, a global shared buffer can be introduced to alleviate the multisystem invalidation effect either as a disk cache or shared intermediate memory. We develop an analytic model to evaluate different shared buffer management policies (SBMPs) which differ in their choice of data granules to be put into the shared buffer. The methodology analyzes all policies using a uniform framework by decomposing the input stream to the shared buffer into multiple (three) component streams based on their effects on the dependency between the private and shared buffer contents. This approach simplifies the problem of analyzing different SBMPs into 1) estimating the rate of each component stream, and 2) evaluating the impact of dependency on each type of component stream and hence the shared buffer hit probability. A detailed simulation model is also developed to validate the analytic model. We also illustrate how the analytic buffer model can be integrated with other system submodels to examine trade-offs between the SBMPs and to estimate optimal shared buffer allocations from a cost-performance point of view.>

Examines the effect of skewed database access on the transaction response time in a multisystem data sharing environment, where each computing node has access to shared data on disks, and has a local buffer of recently accessed granules. Skewness in data access can increase data contention since most accesses go to few data items. For the same reason, it can also increase the buffer hit probability. We quantify the resultant effect on the transaction response time, which depends not only on the various system parameters but also on the concurrency control (CC) protocol. Furthermore, the CC protocol can give rise to rerun transactions that have different buffer hit probabilities. In a multisystem environment, when a data block gets updated by a system, any copies of that block in other systems' local buffers are invalidated. Combining these effects, we find that higher skew does not necessarily lead to worse performance, and that with skewed access, optimistic CC is more robust than pessimistic CC. Examining the buffer hit probability as a function of the buffer size, we find that the effectiveness of additional buffer allocation can be broken down into multiple regions that depend on the access frequency distribution.>

Coupling multiple computing nodes for transaction processing has become increasingly attractive for reasons of capacity, cost, and availability. This paper presents a comparison of robustness (in terms of performance) of three different architectures for transaction processing. In the shared nothing (SN) architecture, neither disks nor memories are shared. In the shared disk (SD) architecture, all disks are accessible from all nodes, whereas in the shared intermediate memory (SIM) architecture, a shared intermediate level of memory is introduced. Coupling multiple nodes inevitably introduces certain interferences and overheads, which take on different forms and magnitudes under the different architectures. Affinity clustering, which attempts to partition the transactions into affinity clusters according to their database reference patterns, can be employed to reduce the coupling degradation under the different architectures, though in different ways. However, the workload may not be partitionable into N affinity clusters of equal size, where N is the number of nodes in the coupled system, so that the load can be evenly spread over all nodes. In addition to balancing the load, we need to maintain a large fraction of data references within the database affiliated with the affinity cluster. These become increasingly harder to achieve for large values of N. In this paper, we examine the impact of affinity on the performance of these three different coupling architectures.>

As the demand for high volume transaction processing grows, coupling multiple computing nodes becomes increasingly attractive. This paper presents a comparison on the resilience of the performance to system dynamics of three architectures for transaction processing. In the shared nothing (SN) architecture, neither disks nor memory is shared. In the shared disk (SD) architecture, all disks are accessible to all nodes while in the shared intermediate memory (SIM) architecture, a shared intermediate level of memory is introduced. A transaction processing system needs to be configured with enough capacity to cope with the dynamic variation of load or with a node failure. Three specific scenarios are considered: 1) a sudden surge in load of one transaction class, 2) varying transaction rates for all transaction classes, and 3) failure of a single processing node. We find that the different architectures require different amounts of capacity to be reserved to cope with these dynamic situations. We further show that the data sharing architecture, especially in the case with shared intermediate memory, is more resilient to system dynamics and requires far less contingency capacity compared to the SN architecture.>

A simple analysis for the transient buffer hit probability for a system starting with an empty buffer is presented. The independent reference model (IRM) is used for buffer accesses. It is shown that the expected buffer hit probability when the buffer becomes full is virtually identical to the steady state buffer hit probability when the replacement policy is least recently used (LRU). The method is generalized to estimate the transient behavior of the LRU policy starting with a non-empty buffer. It is shown that this method can be used to estimate the effect of a load surge on the buffer hit probability. It is also shown that after a short load surge, it can take much longer than the surge duration for the buffer hit probability to return to its steady state value.>

Presents a database access characterization method that first distinguishes three types of access pattern from a trace-locality within a transaction, random accesses by transactions, and sequential accesses by long queries. The authors describe a concise way to characterize the access skew across the randomly accessed pages by assuming that the large number of data pages may be logically grouped into a small number of partitions, such that the frequency of accessing each page within a partition can be treated as equal. They present an extensive validation of the buffer hit predictions, both for single-node as well as multiple-node systems, based on access characterization using production database traces. This approach can be applied to predict the buffer hit probability of a composite workload from those of its component files.>

Six buffer coherency policies for a multisystem transaction processing environment are compared. These policies differ in their basic approaches on how and when the invalidated pages are identified or if the updated pages are propagated to the buffers of the remote nodes. They can be classified as detection, notification (of invalid pages), and (update) propagation oriented approaches. The policies trade off CPU overhead of coherency messages with buffer hit probability in different ways, resulting in a tradeoff of response time and maximum throughput. The main contribution is to develop analytical models to predict buffer hit probabilities under various buffer coherency policies assuming the LRU replacement policy and the independent reference model (IRM). The buffer models are validated using simulation models and show excellent agreement. Integrated analytic models capturing buffer hit probability and CPU overhead are developed to predict the overall response times under these coherency policies. The difference in buffer hit probabilities amongst various policies are found to be very sensitive to the skewness of the data access.>

The authors present a comparison on the resilience of the performance to system dynamics of three multinode architectures for transaction processing. They describe the different architectures considered. The issues of system dynamics are addressed. The performance model is outlined. Three specific scenarios are considered: (1) a sudden load surge in one of the transaction classes, (2) varying transaction rates for all transaction classes, and (3) failure of a single node. It was found that the different architectures require different amounts of capacity to be reserved to cope with these dynamic situations. Quantitative comparisons of the three architectures are given.>

The knowledge of access skew (non-uniform access) in each database relation is useful for both workload management (buffer pool allocation, transaction routing, etc.), as well as capacity planning for changing workload mix. However, it is a challenging problem to characterize the access skew of a real database workload in a simple manner that can easily be used to compute the buffer hit probability under the LRU replacement policy. A concise way to characterize the access skew is proposed by assuming that the large number of data pages may be logically grouped into a small number of partitions such that the frequency of accessing each page within a partition can be treated as equal. Based on this approach, a recursive binary partitioning algorithm is presented that can infer the access skew from the buffer hit probabilities for a subset of the buffer sizes. This avoids explicit estimation of individual access frequencies for the large number of database pages. The method is validated of its ability to predict buffer hit from the skew characterization using production database traces.

The CLOCK algorithm is a popular buffer replacement algorithm because of its simplicity and its ability to approximate the performance of the Least Recently Used (LRU) replacement policy. The Generalized Clock (GCLOCK) buffer replacement policy uses a circular buffer and a weight associated with each page brought in buffer to decide on which page to replace. We develop an approximate analysis for the GCLOCK policy under the Independent Reference Model (IRM) that applies to many database transaction processing workloads. We validate the analysis for various workloads with data access skew. Comparison with simulations shows that in all cases examined the error is extremely small (less than 1%). To show the usefulness of the model we apply it to a Transaction Processing Council benchmark A (TPC-A) like workload. If knowledge of the different data partitions in this workload is assumed, the analysis shows that, with appropriate choice of weights, the performance of the GCLOCK algorithm can be better than the LRU policy. Performance very close to that for optimal (static) buffer allocation can be achieved by assigning sufficiently high weights, and can be implemented with a reasonably low overhead. Finally, we outline how the model can be extended to capture the effect of page invalidation in a multinode system.

Buffer coherency control can be achieved through retaining a lock (shared, exclusive, etc.) on each page in the buffer, even after the requesting transaction has committed. Depending upon the lock mode held for retention and the compatibility of lock modes specified, different retention policies can be devised. In addition to tracking the validity of the buffered data granules, additional capabilities can be provided such as deferred writes to support no-force policy on commit, (node) location identification of valid granules to support remote memory accesses, and shared/exclusive lock retention to reduce the number of global lock requests for concurrency control. However, these can have serious implications not only on the performance but also on the recovery complexity. In this paper, five different integrated coherency policies are considered. We classify these policies into three different categories according to their recovery requirements. A performance study based on analytic models is provided to understand the trade-offs on both maximum throughputs and response times of the policies with a similar level of recovery complexity and the performance gain achievable through increasing the level of recovery complexity.

A comparison is made of four buffer coherency policies: check on access, check on access with periodic notification, selective notification, and broadcast invalidation. These policies differ in their basic approaches on how and when the invalidated granules are identified, and hence, achieve different tradeoffs between buffer hits and overhead of notifications. Analytic models are developed to evaluate the buffer hit probability, CPU overhead, and overall response time under these coherency policies. The analysis is validated through simulations. It is found that the difference in buffer hit probabilities is very sensitive to the skewness of the data access and is further affected by the number of nodes, update rates, and the buffer size.>

In a data sharing environment, where a number of loosely coupled computing nodes share a common storage subsystem, the effectiveness of a private buffer at each node is limited due to the multi-system invalidation effect, particularly under a non-uniform data access pattern. A global shared buffer can be introduced to alleviate this problem either as a disk cache or shared memory. In this paper we developed an approximate analytic model to evaluate different shared buffer management policies (SBMPs) which differ in their choice of data granules to be put into the shared buffer. The analytic model can be used to study the trade-offs of different SBMPs and the impact of different buffer allocations between shared and private buffers. The effects of various parameters, such as, the probability of update, the number of nodes, the sizes of private and shared buffer, etc., on the performance of SBMPS are captured in the analytic model. A detailed simulation model is also developed to validate the analytic model. We show that dependency between the contents of the private and shared buffers can play an important role in determining the effectiveness of the shared buffer particularly for a small number of nodes.

A simple analytic buffer model for coupled systems sharing a common database is developed. When a data block gets updated by a system, copies of that block in other systems' buffers need to be invalidated. This cross-invalidation phenomenon makes the estimation of the buffer hit ratio interesting. The concurrency control (CC) scheme can also complicate the situation. Under the optimistic CC protocol, conflicting transactions can get aborted and need to be rerun. Rerun transactions tend to exhibit a higher hit ratio than first-run transactions since reference blocks, except those that were invalidated, are likely to continue to reside in the buffer. On the other hand, the buffer hit ratio affects not only the number of IOs but also the abort probability. The authors develop a buffer model to capture these effects and integrate it with a CC model to estimate the overall transaction response time Since the invalidation rate increases with buffer size, the advantage of a larger buffer size in the data-sharing environment becomes an issue. The model is then used to study this issue and estimates the maximum buffer that can be usefully employed in each system. The analysis is validated through simulations.>

In this paper, we develop approximate analytical models for predicting the buffer hit probability under the Least Recently Used (LRU) and First In First Out (FIFO) buffer replacement policies under the independent reference model. In the case of the analysis of the LRU policy, the computational complexity for estimating the buffer hit probability is O(KB) where B is the size of the buffer and K denotes the number of items having distinct access probabilities. In the case of the FIFO policy, the solution algorithm is iterative and the computational complexity of each iteration is O(K). Results from these models are compared to exact results for models originally developed by King [KING71] for small values of the buffer size, B, and the total number of items sharing the buffer, D. Results are also compared with results from a simulation for large values of B and D. In most cases, the error is extremely small (less than 0.1%) for both LRU and FIFO, and a maximum error of 3% is observed for very small buffer size (less than 5) when the access probabilities are extremely skewed. To demonstrate the usefulness of the model, we consider two applications. In our first application, we compare the LRU and FIFO policies to an optimal static buffer allocation policy for a database consisting of two classes of data items. We observe that the performance of LRU is close to that of the optimal allocation. As the optimal allocation requires knowledge of the access probabilities, the LRU policy is preferred when this information is unavailable. We also observe that the LRU policy always performs better than the FIFO policy in our experiments. In our second application, we show that if multiple independent reference streams on mutually disjoint sets of data compete for the same buffer, it is better to partition the buffer using an optimal allocation policy than to share a common buffer.

The authors use a mean value model for data contention and a piecewise linear model for resource contention. To show the usefulness of this methodology, they compare three different optimistic concurrency control protocols for a centralized system. The authors derive a closed-form expression for the transaction throughput as a function of workload parameters and the resource-access-time parameters. The resource-access-time parameters can be derived using a simple analytical model. The closed-form expressions are very useful as a quick evaluation of different protocols and to gain insight about protocol performance over a wide range of model parameters. They also yield a simple asymptotic analysis of the optimistic concurrency control protocols. The authors apply the methodology to predict the performance of a testbed database system.>