Cloud computing environments and Internet datacenters consist of a multitude of servers that process user requests. Performance and scalability can suffer greatly when the workload surges to levels that cause a system to become unstable (i.e., when the arrival rate of requests exceeds the system’s capacity to process them). This article presents a detailed design and evaluation of an autonomic elasticity controller for surges of any shape. This controller uses an analytical model, derived by the authors, of a single-queue multiple-server system (G/G/c) subject to workload surges that cause the system to become unstable during finite time intervals. The controller is evaluated through extensive simulations and by using publicly available Google traces. The controller is further extended to take into account VM startup delays. The article also illustrates how fudge factors can be used to more aggressively react to surges at the expense of additional resources. Finally, our controller is compared with a hypothetical oracle controller that knows the exact shape of the surge when it starts to occur.

Fog computing is a distributed computing paradigm that extends cloud computing capabilities to the edge of the network and aims at reducing high latency and network congestion, which are characteristics of cloud computing. This recent paradigm enables portions of a transaction to be executed at a fog server and other portions at the cloud. Fog servers are generally not as robust as cloud servers; at peak loads, the data that cannot be processed by fog servers is processed by cloud servers. The data that need to be processed by the cloud is sent over a Wide Area Network (WAN). Therefore, only a fraction of the total data needs to travel through the WAN, as compared with a pure cloud computing paradigm. Additionally, the fog/cloud computing paradigm reduces the cloud processing load when compared with the pure cloud computing model. This article presents a multiclass closed-form analytic queuing network model that is used by an autonomic controller to dynamically change the fraction of processing between edge and cloud servers in order to maximize a utility function of response time and cost. The model was validated using both synthetic and real IoT traces. A detailed design of the autonomic controller is presented and a series of experiments compare the efficacy and efficiency of the controller versus a brute force optimal controller and versus an uncontrolled system using synthetic and real traces. The results show that the controller is able to maintain a high utility in the presence of wide variations of request arrival rates.

Many real-time process-control and industrial control systems, such as Supervisory Control and Data Acquisition (SCADA), use a distributed software architecture and rely on trusted message exchanges among software components. This article presents the Trust but Verify (TBV) middleware that promotes the idea that software components should not blindly trust each other. The TBV intercepts messages between a sender and a receiver to verify the consistency of the messages against rules associated with message types; this verification considers the system state. Based on the verification, a message is either delivered to the recipient or blocked. Even when components are mutually authenticated, it is possible that their counterparts are faulty or acting maliciously, persuading the receiver to take harmful actions. The contributions of this article are: (1) The design of the TBV middleware. (2) A proof-of-concept implementation of the TBV on a cyberphysical system—a water treatment facility. (3) An experimental validation of the TBV through several attack scenarios that allow compromised or faulty components to randomly send erroneous messages. These experiments measure the TBV’s detection rate as well as its overhead. (4) An evaluation of the TBV overhead and performance degradation.

Moving Target Defense (MTD) has recently emerged as a game changer in the security landscape due to its proven potential to introduce asymmetric uncertainty that gives the defender a tactical advantage over the attacker. Many different MTD techniques have been developed, but, despite the huge progress made in this area, critical gaps still exist with respect to the problem of studying and quantifying the cost and benefits of deploying MTDs. In fact, all existing techniques address a very narrow set of attack vectors, and, due to the lack of shared metrics, it is difficult to quantify and compare multiple techniques. Building on our preliminary work in this field, we propose a quantitative analytic model for assessing the resource availability and performance of MTDs, and a method for maximizing a utility function that captures the tradeoffs between security and performance. The proposed model generalizes our previous model and can be applied to a wider range of MTDs and operational scenarios to improve availability and performance by imposing limits on the maximum number of resources that can be in the process of being reconfigured. The analytic results are validated by simulation and experimentation, confirming the accuracy of our model.

The job replication problem has been studied recently as a mechanism to improve performance and availability of systems with n parallel servers, each with its own queue. A dispatcher using some policy sends d (1 ≤ d ≤ n) copies of a job to d of the servers. Copies are eliminated from the system as soon as the first copy completes from any of the d servers. This article introduces a datadriven method to derive closed-form expressions for the average response time and other metrics of jobs as a function of the degree of replication d. This method consists of developing a simulator for the system in order to generate a very large number of datasets for a wide range of input parameters. A statistical and visualization analysis of the data provides the analytical models. It is important to emphasize the difference between using simulation methods to obtain the value of metrics (e.g., average response time) of a computer system given values of input parameters and using our data-driven method to obtain closed-form expressions that relate output metrics to input parameters. The latter is the focus of our approach. The analysis presented here covers results for homogeneous and heterogeneous servers with exponentially distributed service times and for homogeneous servers with hypo-exponentially and hyper-exponentially distributed service times. This article also presents a closed-form equation for the optimal replication degree for the case of homogeneous servers with hypo-exponentially distributed service times.

Many computer systems, such as cloud computing environments and Internet datacenters, consist of a multitude of servers that process user requests. The performance and scalability of these environments suffer significantly when the workload surges to levels that cause the arrival rate of requests to exceed the system's capacity to process them. This paper models these systems as G/G/c queues and derives equations that estimate the impact of workload surges on these multiserver systems. The existing queuing literature offers approximations and/or bounds for G/G/c systems in equilibrium, but not when these systems are subject to workload surges. This paper's main contributions are: (1) Generic equations for surges of any shape. (2) A set of equations to estimate the impact of trapezoidal and triangular shaped surges on response time. (3) Extensive validations of the derived equations using a G/G/c simulator developed by the authors (available online) and with Google cluster-usage trace workloads. The results show that the equations estimate with great accuracy the impact of surges on response time. The work presented in this paper can be utilized in the design of autonomic elasticity controllers in the cloud to vary the number of servers to mitigate the impact of workload surges.

This paper deals with the problem of evaluating and testing recovery and adaptation frameworks (RAF) for distributed software systems. We present TESS, a testbed for automatically generating distributed software architectures and their corresponding runtime applications, deploying them to the nodes of a cluster, running many different types of experiments involving failures and adaptation, and collecting in a database the values of a variety of failure recovery and adaptation metrics. Using the collected data, TESS automatically performs a thorough and scientific analysis of the efficiency and/or effectiveness of a RAF.This paper presents a case study on the use of TESS to evaluate DARE, a RAF developed by our group.

In this paper we report on the development of a software framework and system for composition, optimization and trade-off analysis of manufacturing and contract service networks based on a reusable repository of performance models. Performance models formally describe process feasibility constraints and metrics of interest, such as cost, throughput and CO2emissions, as a function of fixed and control parameters, such as equipment and contract properties and settings. The repository contains performance models for (1) unit manufacturing processes, (2) base contract services, and (3) a composite steady-state service network. The proposed framework allows process engineers to (1) hierarchically compose model instances of service networks, which can represent production cells, lines, factory facilities and supply chains, and (2) perform deterministic optimization based on mathematical programming and Pareto-optimal trade-off analysis. We case study the framework on a service network for a heat sink product which involves contract vendors and manufacturers, unit manufacturing process services including cutting/shearing and Computer Numerical Control (CNC) machining with milling and drilling steps, quality inspection, finishing and assembly.

Black-box modeling techniques are used when modeling computer systems with unknown internal structure or behavior and/or when it is not feasible or too time consuming to monitor a running computer system. The main challenge in these situations lies in estimating values for the parameters of these models, especially the values of service demands at the various devices for each transaction class. These estimates have to be compliant with the input-output relationships observed through measurements. This means that solving a model of the system with the estimated parameters should yield the same outputs (e.g., response times) for the same inputs (e.g., arrival rates or concurrency level). This paper presents a method for automatically estimating service demands for open, closed, single and multiclass queuing networks (QN). The method is based on casting the estimation problem as a non-linear optimization problem. However, because the solution of closed QNs does not have a closed form, we need to resort to black-box optimization techniques. The parameter estimation method presented here is part of iModel, a framework for automatically deriving performance models of systems whose detailed characteristics (structure and behavior) are unknown. Other portions of the framework were discussed in detail in previous publications by the authors. This paper illustrates the ideas through several numerical examples and then applies them to a multi-tiered operational system running OFBiz. The estimated service demands closely satisfy the input-output relationships at various workload intensity levels and can be used for prediction purposes.

Checkpointing and rollback is a key mechanism used to improve the reliability of software systems. The benefits of this mechanism can be offset by the overhead of checkpointing when the failure rate is low. The problem of developing analytic models of rollback and checkpointing has been continuously addressed for over four decades using different assumptions. This paper examines the problem under a more realistic angle, i.e., one in which there are several software components sharing resources (e.g., processors and I/O devices) among themselves and with the checkpointing processes. Additionally, the paper allows for different components to have different computing, rollback, and checkpointing demands, as well as different failure distributions. Our models also allow for various checkpointing processes to be executing concurrently to checkpoint the state of different software components. The analytic models developed here combine Markov Chains and Queuing Networks and allow us to compute the following metrics: (1) average time needed by a component to complete its execution, (2) average throughput of a component, (3) availability of a component, and (4) checkpointing overhead. The models were validated through extensive simulation and experimentation.

Manually developing analytic performance models of operational systems can be challenging, time consuming, and costly. This paper describes a method that uses system logs and configuration files to automatically derive analytic performance models of operational systems. The method described here automatically determines: (1) the system software servers, (2) the system devices, (3) the deployment of software servers to devices, (4) the communication patterns between software servers for each external use-case, and (5) the probability at which interactions between servers occur. The method was implemented and validated on a multi-tier system. The results showed that the method is capable of deriving the workload model and system model by parsing the system configuration files and log files and inferring user-system interaction patterns and client-server interaction diagrams.

Hundreds of papers on job scheduling for distributed systems are published every year and it becomes increasingly difficult to classify them. Our analysis revealed that half of these papers are barely cited. This paper presents a general taxonomy for scheduling problems and solutions in distributed systems. This taxonomy was used to classify and make publicly available the classification of 109 scheduling problems and their solutions. These 109 problems were further clustered into ten groups based on the features of the taxonomy. The proposed taxonomy will facilitate researchers to build on prior art, increase new research visibility, and minimize redundant effort.

In this paper, we propose an architectural design and software framework for fast development of descriptive, diagnostic, predictive, and prescriptive analytics solutions for dynamic production processes. The proposed architecture and framework will support the storage of modular, extensible, and reusable Knowledge Base (KB) of process performance models. The approach requires the development of automatic methods that can translate the high-level models in the reusable KB into low-level specialized models required by a variety of underlying analysis tools, including data manipulation, optimization, statistical learning, estimation, and simulation. We also propose an organization and key structure for the reusable KB, composed of atomic and composite process performance models and domain-specific dashboards. Furthermore, we illustrate the use of the proposed architecture and framework by performing diagnostic tasks on a composite performance model.

There is a growing adoption of cloud computing services, attracting users with different requirements and budgets to run their applications in cloud infrastructures. In order to match users' needs, cloud providers can offer multiple service classes with different pricing and Service Level Objective (SLO) guarantees. Admission control mechanisms can help providers to meet target SLOs by limiting the demand at peak periods. This paper proposes a prediction-based admission control model for IaaS clouds with multiple service classes, aiming to maximize request admission rates while fulfilling availability SLOs defined for each class. We evaluate our approach with trace-driven simulations fed with data from production systems. Our results show that admission control can reduce SLO violations significantly, specially in underprovisioned scenarios. Moreover, our predictive heuristics are less sensitive to different capacity planning and SLO decisions, as they fulfill availability SLOs for more than 91% of requests even in the worst case scenario, for which only 56% of SLOs are fulfilled by a simpler greedy heuristic and as little as 0.2% when admission control is not used.

Analyzing and predicting the performance of applications that run on multi-core computers is essential. This paper demonstrates experimentally that memory contention resulting from multiple cores accessing shared memory resources can become a significant component (i.e., over 50 percent) of an application's execution time. The paper develops singleand multi-class analytic performance models for predicting the effect of memory contention on a job's execution time. The models consider local and remote memory as in NUMA architectures. Model validation was done using a micro-benchmark and programs from HBench, UnixBench, and SPECCPU2006 running on machines with 4, 12, and 16 cores. The paper shows how to derive the model parameters and demonstrates that there is a significant difference in predicted values when memory contention is ignored. For example, a model that ignores memory contention predicts an average execution time about four times smaller than the experimental value for a concurrency level of 18 while the model with memory contention predicts a value that is 90 percent of the experimental value for the same concurrency level.

Large enterprises use clusters of computers to process Big Data workloads that are heterogeneous in terms of the type of jobs and the nature of their arrival processes. The scheduling of jobs from such workloads has a significant impact on their execution times. This paper presents a Trace Driven Analytic Model (TDAM) methodology to assess the impact of different scheduling schemes on job execution times. The analytic models used by this method consist of closed queuing network methods that estimate congestion at the various nodes of the cluster. The paper demonstrates the usefulness of this approach by showing how four different types of common schedulers affect the execution times of jobs derived from well-known benchmarks. This method is then implemented inside of a popular Hadoop job-trace simulator called Mumak, making Mumak contention-aware. The original Mumak tool completely ignores contention for processors and I/O at each node of the cluster. Our contentiion-aware Mumak predicts job completion times at a significantly higher level of accuracy.

This paper is focused on decision analytics for smart manufacturing. We consider temporal manufacturing processes with stochastic throughput and inventories. We demonstrate the use of the recently proposed concept of the decision guidance analytics language to perform monitoring, analysis, planning, and execution tasks. To support these tasks we define the structure of and develop modular reusable process component models, which represent data, decision/control variables, computation of functions, constraints, and uncertainty. The tasks are then implemented by posing declarative queries of the decision guidance analytics language for data manipulation, what-if prediction analysis, decision optimization, and machine learning.

This paper builds on SASSY, a system for automatically generating SOA software architectures that optimize a given utility function of multiple QoS metrics. In SASSY, SOA software systems are automatically re-architected when services fail or degrade. Optimizing both architecture and service provider selection presents a pair of nested NP-hard problems. Here we adapt hill-climbing, beam search, simulated annealing, and evolutionary programming to both architecture optimization and service provider selection. Each of these techniques has several parameters that influence their efficiency. We introduce in this paper a meta-controller that automates the run-time selection of heuristic search techniques and their parameters. We examine two different meta-controller implementations that each use online learning. The first implementation identifies the best heuristic search combination from various prepared combinations. The second implementation analyzes the current self-architecting problem (e.g. changes in performance metrics, service degradations/failures) and looks for similar, previously encountered re-architecting problems to find an effective heuristic search combination for the current problem. A large set of experiments demonstrates the effectiveness of the first meta-controller implementation and indicates opportunities for improving the second meta-controller implementation.

Parallel and concurrent structures are widely used both as standalone components and as building blocks of larger systems. Efficient models of parallelism and concurrency are therefore necessary to understand the impact of parallelism in system performance. These models become more critical with the proliferation of adaptive systems that require solving a large number of performance models in a short amount of time to facilitate configuration decisions dynamically. This paper presents efficient response time approximations for parallel constructs modeled as fork and join queues. These approximations can be used by practitioners and performance engineers to quickly compare the performance of contending configurations. The contributions over previous work are twofold. First, this paper considers heterogeneous multiclass fork and join open and closed queuing networks. Second, the paper also presents models for fork and join where each class of jobs might fork to different queues in a probabilistic manner.

Multi-core computers are becoming increasingly ubiquitous. Understanding and being able to predict the performance of applications that run on such machines is paramount. This paper first shows experimentally that memory contention resulting from multiple cores accessing shared memory can become a significant component of an application's execution time. Then, the paper develops an approximate single-class analytic performance model that captures the effect of memory contention. The model is validated through measurements taken on a micro-benchmark and on well known Unix memory benchmark programs on machines with 4, 12, and 16 cores. The paper also shows that there is a significant difference in the predictions when memory contention is not considered.

Service Oriented Architectures enable markets of functionally equivalent service providers delivering services at different Quality of Service (QoS) and cost levels. Under these circumstances, there is a need for mechanisms to optimally select service providers at run-time to support a business process execution so that a utility function for the business process is maximized subject to QoS and cost constraints. This is an NP-hard problem. This paper investigates this problem when the utility function is expressed in terms of multiple QoS metrics. An efficient optimal algorithm is presented, which eliminates the need to exhaustively search the state space. This algorithm can be used for small to medium size problems. A very efficient heuristic solution is also presented and scientifically evaluated against the optimal solution on a large set of randomly generated business processes.

Autonomic computing systems are able to adapt to changing environments (such as changes in the workload intensity or component failures) in a way that preserves highlevel operational goals, such as service level objectives. This paper focuses on autonomic computing systems that are self-optimizing and self-configuring. More specifically, the paper presents the detailed design of an autonomic load balancer (LB) for multi-tiered Web sites. It is assumed that customers can be categorized into distinct classes (gold, silver, and bronze) according to their business value to the site. While the example used in the paper is that of an auction site, the approach can be easily applied to any other Web site. The autonomic LB is able to dynamically change its request redirection policy as well as its resource allocation policy, which determines the allocation of servers to server clusters, in a way that maximizes a business-oriented utility function. The autonomic LB was evaluated through very detailed and comprehensive simulation experiments and was compared against a round-robin LB and against a situation where each customer category has a dedicated number of servers. The results showed that the autonomic LB outperforms the other load balancing approaches in terms of providing a higher utility for highly dynamic workloads.

Quality of service (QoS) is an important consideration in the dynamic service selection in the context of service oriented architectures. This paper extends previous work on QoS brokering for SOAs by designing, implementing, and experimentally evaluating a service selection QoS broker that maximizes a utility function for service consumers. Utility functions allow stakeholders to ascribe a value to the usefulness of a system as a function of several attributes such as response time, throughput, and availability. This work assumes that consumers of services provide to a QoS broker their utility functions and their cost constraints on the requested services. Service providers register with the broker by providing service demands for each of the resources used by the services provided and cost functions for each of the services. Consumers request services from the QoS broker, which selects a service provider that maximizes the consumer's utility function subject to its cost constraint. The QoS broker uses analytic queuing models to predict the QoS values of the various services that could be selected under varying workload conditions. The broker and services were implemented using a J2EE/Weblogic platform and experiments were conducted to evaluate the broker's efficacy. Results showed that the broker adequately adapts its selection of service providers according to cost constraints.

Performance, in terms of user response time and the consumption of processing and communications resources, is an important factor to be considered when designing authentication protocols. The mix of public key and secret key encryption algorithms typically included in these protocols makes it difficult to model performance using conventional analytical methods. In this article, we develop a validated modeling methodology to be used for analyzing authentication protocol features, and we use two examples to illustrate the methodology. In the first example, we analyze the environmental parameters that favor one proposed public-key-enabled Kerberos variant over another in the context of a large, multiple-realm network. In the second example, we propose a Kerberos variant for a mobile computing environment and analyze the performance benefits realized by introducing a proxy to offload processing and communications workload.

Authenticating mobile computing users can require a significant amount of processing and communications resources particularly when protocols based on public key encryption are invoked. These resource requirements can result in unacceptable response times for the user. In this paper, we analyze adaptations of the public key-enabled Kerberos network authentication protocol to a mobile platform by measuring the service time of a skeleton implementation and constructing a closed queuing network model. Our adaptation of Kerberos introduces a proxy server between the client and the server to mitigate potential performance deficiencies and add functional benefits. Our analysis indicates that assistance from the proxy makes public key Kerberos a viable authentication protocol from a performance perspective. However, as wireless network speeds increase from current 2G levels to the 3G targets, the proxy can become a response time liability. The proxy s role in the protocol, while warranted in current applications, will have to be re-modeled and re-considered as both wireless transmission speeds and proxy processing speeds increase.

The Quality of Service (QoS) of e-commerce sites plays a crucial role in attracting and retaining customers. The workload experienced by these sites tends to vary in a very dynamic way. The complexity of the sites combined with the large short-terms variations of the workload calls for automated methods for site configuration. This paper describes a method for dynamically monitoring and tuning e-commerce sites so that desired QoS levels are attained. Our approach uses hill climbing techniques combined with analytic queuing models to guide the search for the best combination of configuration parameters. We validate our approach in an experimental setting by comparing the QoS levels of a TPC-W e-commerce site with and without control. We showed that under increasing loads, the controlled system meets its QoS goals, while the uncontrolled site fails to do so.

Several proposals have been made to public-key-enable various stages of the secret-key-based Kerberos network authentication protocol. The computational requirements of public key cryptography are much higher than those of secret key cryptography, and the substitution of public key encryption algorithms for secret key algorithms impacts performance. This paper uses closed, class-switching queuing models to demonstrate the quantitative performance differences between PKCROSS and PKTAPP - two proposals for public-key-enabling Kerberos. Our analysis shows that, while PKTAPP is more efficient for authenticating to a single server, PKCROSS outperforms the simpler protocol if there are two or more remote servers per remote realm. This heuristic can be used to guide a high-level protocol that combines both methods of authentication to improve performance.

One of the challenges in designing and maintaining e-business sites is to ensure their scalability as the work-load increases. The article discusses a multi-layer reference model that can be used for capacity planning and analysis of e-business sites. It shows how to characterize the workload of e-commerce servers, taking into account customer behavior patterns. It further discusses how the various technologies used in e-commerce sites, such as authentication and payment protocols, affect their performance.

Understanding the nature and characteristics of e-business workloads is a crucial step to improve the quality of service offered to customers in electronic business environments.However, the variety and complexity of the interactions between customers and sites make the characterization of ebusiness workloads a challenging problem.Using a multilayer hierarchical model, this paper presents a detailed characterization of the workload of two actual e-business sites: an online bookstore and an electronic auction site.Through the characterization process, we found the presence of autonomous agents, or robots, in the workload and used the hierarchical structure to determine their characteristics.We also found that search terms follow a Zipf distribution.

Designing complex distributed client/server applications that meet performance requirements may prove extremely difficult in practice if software developers are not willing or do not have the time to help software performance analysts. The paper advocates the need to integrate both design and performance modeling activities so that one can help the other. We present a method developed and used by the authors in the design of a fairly large and complex client/server application. The method is based on a software performance engineering language developed by one of the authors. Use cases were developed and mapped to a performance modeling specification using the language. A compiler for the language generates an analytic performance model for the system. Service demand parameters at servers, storage boxes, and networks are derived by the compiler from the system specification. A detailed model of DBMS query optimizers allows the compiler to estimate the number of I/Os and CPU time for SQL statements. The paper concludes with some results of the application that prompted the development of the method and language.

Article Free Access Share on A methodology for workload characterization of E-commerce sites Authors: Daniel A. Menascé Dept. of Computer Science, George Mason University, Fairfax, VA Dept. of Computer Science, George Mason University, Fairfax, VAView Profile , Virgilio A. F. Almeida Dept. of Computer Science, Univ. Federal de Minas Gerais, Belo Horizonte, MG 30161, Brazil Dept. of Computer Science, Univ. Federal de Minas Gerais, Belo Horizonte, MG 30161, BrazilView Profile , Rodrigo Fonseca Dept. of Computer Science, Univ. Federal de Minas Gerais, Belo Horizonte, MG 30161, Brazil Dept. of Computer Science, Univ. Federal de Minas Gerais, Belo Horizonte, MG 30161, BrazilView Profile , Marco A. Mendes Dept. of Computer Science, Univ. Federal de Minas Gerais, Belo Horizonte, MG 30161, Brazil Dept. of Computer Science, Univ. Federal de Minas Gerais, Belo Horizonte, MG 30161, BrazilView Profile Authors Info & Claims EC '99: Proceedings of the 1st ACM conference on Electronic commerceNovember 1999 Pages 119–128https://doi.org/10.1145/336992.337024Published:01 November 1999Publication History 176citation2,293DownloadsMetricsTotal Citations176Total Downloads2,293Last 12 Months162Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The constant growth on the demands imposed on hierarchical mass storage systems creates a need for frequent reconfiguration and upgrading to ensure that the response times and other performance metrics are within the desired service levels. This paper describes the design and operation of two tools, Pythia and Pythia/WK, that assist system managers and integrators in making cost-effective procurement decisions. Pythia automatically buids and solves an analytic model of a mass storage system based on a graphical description of the architecture of the system, and on a description of the workload imposed on the system. The use of a modeling wizard to perform this conversion from a graphical description of a mass storage system to an analytic model makes Pythia unique among analytic performance tools. Pythia/WK uses clustering algorithms to characterize the workload from the log files of the mass storage system. The resulting workload characterization is used as input to Pythia. © 1997 John Wiley & Sons, Ltd.

Mass storage systems are finding greater use in scientific computing research environments for retrieving and archiving the large volumes of data generated and manipulated by scientific computations. This paper presents a queuing network model that can be used to carry out capacity planning studies of hierarchical mass storage systems. Measurements taken on a Unitree mass storage system and a detailed workload characterization provided the workload intensity and resource demand parameters for the various types of read and write requests. The performance model developed here is based on approximations to multiclass Mean Value Analysis of queuing networks. The approximations were validated through the use of discrete event simulation and the complete model was validated and calibrated through measurements. The resulting model was used to analyze three different scenarios: effect of workload intensity increase, use of file compression at the server and client, and use of file abstractions.

Network attached storage devices improve I/O performance by separating control and data paths and eliminating host intervention during data transfer. Devices are attached to a high speed network for data transfer and to a slower network for control messages. Hierarchical mass storage systems use disks to cache the most recently used files and tapes (robotic and manually mounted) to store the bulk of the files in the file system. This paper shows how queuing network models can be used to assess the performance of hierarchical mass storage systems that use network attached storage devices. The analytic model validated through simulation was used to analyze many different scenarios.

The Earth Observing System (EOS) Data and Information System (EOSDIS) is perhaps one of the most important examples of large-scale, geographically distributed, and data intensive systems. The paper presents various facets of a data and information architecture for EOSDIS. EOS data is organized by means of an object-oriented schema, while EOS knowledge is organized through multiple domain-specific thesauri, complemented by domain knowledge and rules. The information holdings are organized into the source data archives, a data warehouse which provides an integrated view of the information holdings, and information marts which generate value-added information products for specialized user communities. Finally a federated client-server architecture is proposed to allow non-EOSDIS systems to become members of the EOSDIS community, allowing them to access EOSDIS holdings, and sharing their own data with EOSDIS.

The Earth Observing System (EOS) Data and Information System (EOSDIS) is perhaps one of the most important examples of a large-scale, geographically distributed, and data-intensive systems. Designing such systems in a way that ensures that the resulting design will satisfy all functional and performance requirements is not a trivial task. This paper presents a performance oriented methodology to design large-scale distributed data intensive information systems. The methodology is then applied to the design of the EOSDIS Core System (ECS). Performance results, based on queueing network models of ECS are also presented.

Quorum attainment protocols are an important part of many mutual exclusion algorithms. Assessing the performance of such protocols in terms of number of messages, as is usually done, may be less significant than being able to compute the delay in attaining the quorum. Some protocols achieve higher reliability at the expense of increased message cost or delay. A unified analytical model which takes into account the network delay and its effect on the time needed to obtain a quorum is presented. A combined performability metric, which takes into account both availability and delay, is defined, and expressions to calculate its value are derived for two different reliable quorum attainment protocols: D. Agrawal and A. El Abbadi's (1991) and Majority Consensus algorithms (R.H. Thomas, 1979). Expressions for the primary site approach are also given as upper bound on performability and lower bound on delay. A parallel version of the Agrawal and El Abbadi protocol is introduced and evaluated. This new algorithm is shown to exhibit lower delay at the expense of a negligible increase in the number of messages exchanged. Numerical results derived from the model are discussed.>

The authors consider multiprogrammed multiprocessors and parallel programs modeled as random task graphs. A theoretical analytical model for studying combinations of extreme cases of workload parallelism (highly parallel versus highly sequential) and of system utilization (light versus heavy load) is presented. A simulation model was used to study intermediate cases. From these two models, conditions under which heterogeneity presents a significant performance improvement over homogeneous architectures are derived. A study of the effect of scheduling policies for heterogeneous architectures on workloads of different degrees of parallelism under various system load conditions is presented.>

The cost-performance of heterogeneity in supercomputer architectures is analyzed. Queuing models are used to study the performance of homogeneous and heterogeneous supercomputer models. Grosch's law, which states that computer performance increases as the square of its cost, is used to analyze cost aspects of the models. It is concluded that heterogeneity in supercomputer architectures is a quite promising design approach that deserves further investigation.>

The token bus based local area network, REDPUC, designed and implemented at the Pontíficia Universidade Católica do Rio de Janeiro is briefly described. Analytic models are presented, which allow one to obtain an approximation for the average packet delay, as well as exact upper and lower bounds for the same performance measure. A performance evaluation of interconnected local networks is also given.

Many concurrency control algorithms for distributed database management systems have been proposed in the last few years, but little has been done to analyse their performance. This paper presents the specification of a concurrency control algorithm based on the two-phase commit protocol for DDBs. The results of a complete performance analysis based on an analytic model are presented and discussed.

A locking protocol to coordinate access to a distributed database and to maintain system consistency throughout normal and abnormal conditions is presented. The proposed protocol is robust in the face of crashes of any participating site, as well as communication failures. Recovery from any number of failures during normal operation or any of the recovery stages is supported. Recovery is done in such a way that maximum forward progress is achieved by the recovery procedures. Integration of virtually any locking discipline including predicate lock methods is permitted by this protocol. The locking algorithm operates, and operates correctly, when the network is partitioned, either intentionally or by failure of communication lines. Each partition is able to continue with work local to it, and operation merges gracefully when the partitions are reconnected. A subroutine of the protocol, that assures reliable communication among sites, is shown to have better performance than two-phase commit methods. For many topologies of interest, the delay introduced by the overall protocol is not a direct function of the size of the network. The communications cost is shown to grow in a relatively slow, linear fashion with the number of sites participating in the transaction. An informal proof of the correctness of the algorithm is also presented in this paper. The algorithm has as its core a centralized locking protocol with distributed recovery procedures. A centralized controller with local appendages at each site coordinates all resource control, with requests initiated by application programs at any site. However, no site experiences undue load. Recovery is broken down into three disjoint mechanisms: for single node recovery, merge of partitions, and reconstruction of the centralized controller and tables. The disjointness of the mechanisms contributes to comprehensibility and ease of proof. The paper concludes with a proposal for an extension aimed at optimizing operation of the algorithm to adapt to highly skewed distributions of activity. The extension applies nicely to interconnected computer networks.

This paper descrbes two protocols for the detection of deadlocks in distributed data bases–a hierarchically organized one and a distributed one. A graph model which depicts the state of execution of all transactions in the system is used by both protocols. A cycle in this graph is a necessary and sufficient condition for a deadlock to exist. Nevertheless, neither protocol requires that the global graph be built and maintained in order for deadlocks to be detected. In the case of the hierarchical protocol, the communications cost can be optimized if the topology of the hierarachy is appropriately chosen.

A locking protocol to coordinate access to a distributed database and to maintain system consistency throughout normal and abnormal conditions is presented. The proposed protocol is robust in the face of crashes of any participating site, as well as communication failures. Recovery from any number of failures during normal operation or any of the recovery stages is supported. Recovery is done in such a way that maximum forward progress is achieved by the recovery procedures. Integration of virtually any locking discipline including predicate lock methods is permitted by this protocol. The locking algorithm operates, and operates correctly, when the network is partitioned, either intentionally or by failure of communication lines. Each partition is able to continue with work local to it, and operation merges gracefully when the partitions are reconnected.A subroutine of the protocol, that assures reliable communication among sites, is shown to have better performance than two-phase commit methods. For many topologies of interest, the delay introduced by the overall protocol is not a direct function of the size of the network. The communications cost is shown to grow in a relatively slow, linear fashion with the number of sites participating in the transaction. An informal proof of the correctness of the algorithm is also presented in this paper.The algorithm has as its core a centralized locking protocol with distributed recovery procedures. A centralized controller with local appendages at each site coordinates all resource control, with requests initiated by application programs at any site. However, no site experiences undue load. Recovery is broken down into three disjoint mechanisms: for single node recovery, merge of partitions, and reconstruction of the centralized controller and tables. The disjointness of the mechanisms contributes to comprehensibility and ease of proof.The paper concludes with a proposal for an extension aimed at optimizing operation of the algorithm to adapt to highly skewed distributions of activity. The extension applies nicely to interconnected computer networks.