MOTIVATION: Many advances in biomedical research are driven by structural analysis, which investigates interconnections between elements in biological systems (e.g. structural analysis of proteins to infer their function). Herein, we consider subnet discovery in chemical reaction networks (CRNs)-discovering a subset of a target CRN, i.e. structurally identical to a reference CRN. Structural analysis techniques such as motif finding and graph mining look for small, arbitrary, and commonly occurring substructures (e.g. three gene feedforward loops). In contrast, subnet discovery looks for larger, specific, and infrequently occurring substructures (e.g. 10 reactions mitogen-activated protein kinase (MAPK) pathway). RESULTS: We introduce pySubnetSB, an open source Python package for discovering subnets in CRNs that are represented in the Systems Biology Markup Language (SBML) community standard. We show that pySubnetSB achieves large reductions in computational complexity for subnet discovery. For example, in studies of randomly selected target networks with 100 reactions each with a random reference network with 20 reactions, computations are reduced from an infeasible 1078 evaluations to a more practical 108 evaluations. We develop a methodology for assessing the statistical significance of subnet discovery. Last, we study subnets in BioModels for approximately 200 000 pairs of reference and target models. We show that for a reference MAPK pathway, subnet discovery correctly indicates the presence of MAPK function in several target models. The studies also suggest two interesting hypotheses: (a) the potential presence of hidden oscillators in several models in BioModels, and (b) the possibility of a conserved mechanism for intracellular immune response. AVAILABILITY AND IMPLENETATION: pySubnetSB is installed using pip install pySubnetSB, and is hosted at https://github.com/ModelEngineering/pySubnetSB/.

SBMLNetwork is an open-source software library that makes the SBML Layout and Render packages practical for standards-based visualization of biochemical models. Current tools often manage model visualization data in custom-designed, tool-specific formats and store it separately from the model itself, hindering interoperability, reproducibility, and the seamless integration of visualization with model data. SBMLNetwork addresses these limitations by building directly on the SBML Layout and Render specifications, automating the generation of standards-compliant visualization data, offering a modular implementation with broad integration support, and providing a robust API tailored to the needs of systems biology researchers. We illustrate the capabilities of SBMLNetwork across key visualization tasks, including SBGN-compliant visualization, application of predefined style templates, layout arrangement to reflect pathway logic, and integration of model data into network diagrams. These examples demonstrate how SBMLNetwork enables high-level visualization features and seamlessly translate user intent into reproducible outputs that support both structural representation and dynamic data visualization within the SBML model. SBMLNetwork is freely available at https://github.com/sys-bio/SBMLNetwork under the MIT license.

The BioModels Repository contains over 1000 manually curated mechanistic models from published literature, most often encoded in the Systems Biology Markup Language (SBML). This community-based standard formally specifies each model, but does not describe the computational experimental conditions to run a simulation and collect data. Therefore, it can be challenging to reproduce any figure or result from a publication with an SBML model alone. The Simulation Experiment Description Markup Language (SED-ML) provides a solution: a standard way to specify exactly how to run an experiment corresponding to a specific figure or result. BioModels was established years before SED-ML, and both systems evolved over time, both in content and acceptance. Hence, only about half of the entries in BioModels contained SED-ML files, and these files reflected the version of SED-ML that was available at the time. Additionally, almost all of these SED-ML files had at least one minor mistake that made them impossible to run. To make these models and their results more reproducible, we report here on our work updating, correcting and generating new SED-ML files for 1055 curated mechanistic models in BioModels. In addition, because SED-ML is implementation-independent, it can be used for verification, demonstrating that results hold across multiple simulation engines. We tested, corrected, and improved over 450 existing SED-ML files in the BioModels database, and created basic files for the rest of the entries. Then, we used a wrapper architecture for interpreting SED-ML, and report verification results across five different ODE-based biosimulation engines, after further improving the models, the wrappers, and the engines themselves. Our work with SED-ML and the BioModels collection aims to improve the utility of these models by making them more reproducible and credible. Improved reproducibility means these models are now even more fit for re-use, such as in new investigations and as components of multiscale models.

MOTIVATION: Developing biochemical models in systems biology is a complex, knowledge-intensive activity. Some modelers (especially novices) benefit from model development tools with a graphical user interface. However, as with the development of complex software, text-based representations of models provide many benefits for advanced model development. At present, the tools for text-based model development are limited, typically just a textual editor that provides features such as copy, paste, find, and replace. Since these tools are not "model aware," they do not provide features for: (i) model building such as autocompletion of species names; (ii) model analysis such as hover messages that provide information about chemical species; and (iii) model translation to convert between model representations. We refer to these as BAT features. RESULTS: We present VSCode-Antimony, a tool for building, analyzing, and translating models written in the Antimony modeling language, a human readable representation of Systems Biology Markup Language (SBML) models. VSCode-Antimony is a source editor, a tool with language-aware features. For example, there is autocompletion of variable names to assist with model building, hover messages that aid in model analysis, and translation between XML and Antimony representations of SBML models. These features result from making VSCode-Antimony model-aware by incorporating several sophisticated capabilities: analysis of the Antimony grammar (e.g. to identify model symbols and their types); a query system for accessing knowledge sources for chemical species and reactions; and automatic conversion between different model representations (e.g. between Antimony and SBML). AVAILABILITY AND IMPLEMENTATION: VSCode-Antimony is available as an open source extension in the VSCode Marketplace https://marketplace.visualstudio.com/items?itemName=stevem.vscode-antimony. Source code can be found at https://github.com/sys-bio/vscode-antimony.

MOTIVATION: Annotations of biochemical models provide details of chemical species, documentation of chemical reactions, and other essential information. Unfortunately, the vast majority of biochemical models have few, if any, annotations, or the annotations provide insufficient detail to understand the limitations of the model. The quality and quantity of annotations can be improved by developing tools that recommend annotations. For example, recommender tools have been developed for annotations of genes. Although annotating genes is conceptually similar to annotating biochemical models, there are important technical differences that make it difficult to directly apply this prior work. RESULTS: We present AMAS, a system that predicts annotations for elements of models represented in the Systems Biology Markup Language (SBML) community standard. We provide a general framework for predicting model annotations for a query element based on a database of annotated reference elements and a match score function that calculates the similarity between the query element and reference elements. The framework is instantiated to specific element types (e.g. species, reactions) by specifying the reference database (e.g. ChEBI for species) and the match score function (e.g. string similarity). We analyze the computational efficiency and prediction quality of AMAS for species and reactions in BiGG and BioModels and find that it has subsecond response times and accuracy between 80% and 95% depending on specifics of what is predicted. We have incorporated AMAS into an open-source, pip-installable Python package that can run as a command-line tool that predicts and adds annotations to species and reactions to an SBML model. AVAILABILITY AND IMPLEMENTATION: Our project is hosted at https://github.com/sys-bio/AMAS, where we provide examples, documentation, and source code files. Our source code is licensed under the MIT open-source license.

MOTIVATION: The growing complexity of reaction-based models necessitates early detection and resolution of model errors. Considerable work has been done on the detection of mass balance errors, especially atomic mass analysis (AMA) (which compares the counts of atoms in the reactants and products) and Linear Programming analysis (which detects stoichiometric inconsistencies). This article extends model error checking to include: (i) certain structural errors in reaction networks and (ii) error isolation. First, we consider the balance of chemical structures (moieties) between reactants and products. This balance is expected in many biochemical reactions, but the imbalance of chemical structures cannot be detected if the analysis is done in units of atomic masses. Second, we improve on error isolation for stoichiometric inconsistencies by identifying a small number of reactions and/or species that cause the error. Doing so simplifies error remediation. RESULTS: We propose two algorithms that address isolating structural errors in reaction networks. Moiety analysis finds imbalances of moieties using the same algorithm as AMA, but moiety analysis works in units of moieties instead of atomic masses. We argue for the value of checking moiety balance, and discuss two approaches to decomposing chemical species into moieties. Graphical Analysis of Mass Equivalence Sets (GAMES) provides isolation for stoichiometric inconsistencies by constructing explanations that relate errors in the structure of the reaction network to elements of the reaction network. We study the effectiveness of moiety analysis and GAMES on curated models in the BioModels repository. We have created open source codes for moiety analysis and GAMES. AVAILABILITY AND IMPLEMENTATION: Our project is hosted at https://github.com/ModelEngineering/SBMLLint, which contains examples, documentation, source code files and build scripts used to create SBMLLint. Our source code is licensed under the MIT open source license. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The explosive growth in semiconductor integrated circuits was made possible in large part by design automation software. The design and/or analysis of synthetic and natural circuits in living cells could be made more scalable using the same approach. We present a compiler which converts standard representations of chemical reaction networks and circuits into hardware configurations that can be used to simulate the network on specialized cytomorphic hardware. The compiler also creates circuit-level models of the target configuration, which enhances the versatility of the compiler and enables the validation of its functionality without physical experimentation with the hardware. We show that this compiler can translate networks comprised of mass-action kinetics, classic enzyme kinetics (Michaelis-Menten, Briggs-Haldane, and Botts-Morales formalisms), and genetic repressor kinetics, thereby allowing a large class of models to be transformed into a hardware representation. Rule-based models are particularly well-suited to this approach, as we demonstrate by compiling a MAP kinase model. Development of specialized hardware and software for simulating biological networks has the potential to enable the simulation of larger kinetic models than are currently feasible or allow the parallel simulation of many smaller networks with better performance than current simulation software.

The considerable difficulty encountered in reproducing the results of published dynamical models limits validation, exploration and reuse of this increasingly large biomedical research resource. To address this problem, we have developed Tellurium Notebook, a software system for model authoring, simulation, and teaching that facilitates building reproducible dynamical models and reusing models by 1) providing a notebook environment which allows models, Python code, and narrative to be intermixed, 2) supporting the COMBINE archive format during model development for capturing model information in an exchangeable format and 3) enabling users to easily simulate and edit public COMBINE-compliant models from public repositories to facilitate studying model dynamics, variants and test cases. Tellurium Notebook, a Python-based Jupyter-like environment, is designed to seamlessly inter-operate with these community standards by automating conversion between COMBINE standards formulations and corresponding in-line, human-readable representations. Thus, Tellurium brings to systems biology the strategy used by other literate notebook systems such as Mathematica. These capabilities allow users to edit every aspect of the standards-compliant models and simulations, run the simulations in-line, and re-export to standard formats. We provide several use cases illustrating the advantages of our approach and how it allows development and reuse of models without requiring technical knowledge of standards. Adoption of Tellurium should accelerate model development, reproducibility and reuse.

Data centers consume tremendous amounts of energy in terms of power distribution and cooling. Dynamic capacity provisioning is a promising approach for reducing energy consumption by dynamically adjusting the number of active machines to match resource demands. However, despite extensive studies of the problem, existing solutions have not fully considered the heterogeneity of both workload and machine hardware found in production environments. In particular, production data centers often comprise heterogeneous machines with different capacities and energy consumption characteristics. Meanwhile, the production cloud workloads typically consist of diverse applications with different priorities, performance and resource requirements. Failure to consider the heterogeneity of both machines and workloads will lead to both sub-optimal energy-savings and long scheduling delays, due to incompatibility between workload requirements and the resources offered by the provisioned machines. To address this limitation, we present Harmony, a Heterogeneity-Aware dynamic capacity provisioning scheme for cloud data centers. Specifically, we first use the K-means clustering algorithm to divide workload into distinct task classes with similar characteristics in terms of resource and performance requirements. Then we present a technique that dynamically adjusting the number of machines to minimize total energy consumption and scheduling delay. Simulations using traces from a Google's compute cluster demonstrate Harmony can reduce energy by 28 percent compared to heterogeneity-oblivious solutions.

Data centers today consume tremendous amount of energy in terms of power distribution and cooling. Dynamic capacity provisioning is a promising approach for reducing energy consumption by dynamically adjusting the number of active machines to match resource demands. However, despite extensive studies of the problem, existing solutions for dynamic capacity provisioning have not fully considered the heterogeneity of both workload and machine hardware found in production environments. In particular, production data centers often comprise several generations of machines with different capacities, capabilities and energy consumption characteristics. Meanwhile, the workloads running in these data centers typically consist of a wide variety of applications with different priorities, performance objectives and resource requirements. Failure to consider heterogenous characteristics will lead to both sub-optimal energy-savings and long scheduling delays, due to incompatibility between workload requirements and the resources offered by the provisioned machines. To address this limitation, in this paper we present HARMONY, a Heterogeneity-Aware Resource Management System for dynamic capacity provisioning in cloud computing environments. Specifically, we first use the K-means clustering algorithm to divide the workload into distinct task classes with similar characteristics in terms of resource and performance requirements. Then we present a novel technique for dynamically adjusting the number of machines of each type to minimize total energy consumption and performance penalty in terms of scheduling delay. Through simulations using real traces from Google's compute clusters, we found that our approach can improve data center energy efficiency by up to 28% compared to heterogeneity-oblivious solutions.

Large-scale online service providers have been increasingly relying on geographically distributed cloud infrastructures for service hosting and delivery. In this context, a key challenge faced by service providers is to determine the locations where service applications should be placed such that the hosting cost is minimized while key performance requirements (e.g., response time) are ensured. Furthermore, the dynamic nature of both demand pattern and infrastructure cost favors a dynamic solution to this problem. Currently most of the existing solutions for service placement have either ignored dynamics, or provided solutions inadequate to achieve this objective. In this paper, we present a framework for dynamic service placement problems based on control- and game-theoretic models. In particular, we present a solution that optimizes the hosting cost dynamically over time according to both demand and resource price fluctuations. We further consider the case where multiple service providers compete for resources in a dynamic manner. This paper extends our previous work [1] by analyzing the outcome of the competition in terms of both price of stability and price of anarchy. Our analysis suggests that in an uncoordinated scenario where service providers behave in a selfish manner, the resulting Nash equilibrium can be arbitrarily worse than the optimal centralized solution in terms of social welfare. Based on this observation, we present a coordination mechanism that can be employed by the infrastructure provider to maximize the social welfare of the system. Finally, we demonstrate the effectiveness of our solutions using realistic simulations.

Cloud providers such as Google are interested in fostering research on the daunting technical challenges they face in supporting planetary-scale distributed systems, but no academic organizations have similar scale systems on which to experiment. Fortunately, good research can still be done using traces of real-life production workloads, but there are risks in releasing such data, including inadvertently disclosing confidential or proprietary information, as happened with the Netflix Prize data. This paper discusses these risks, and our approach to them, which we call systematic obfuscation. It protects proprietary and personal data while leaving it possible to answer interesting research questions. We explain and motivate some of the risks and concerns and propose how they can best be mitigated, using as an example our recent publication of a month-long trace of a production system workload on a 11k-machine cluster.

Evaluating the performance of large compute clusters requires benchmarks with representative workloads. At Google, performance benchmarks are used to obtain performance metrics such as task scheduling delays and machine resource utilizations to assess changes in application codes, machine configurations, and scheduling algorithms. Existing approaches to workload characterization for high performance computing and grids focus on task resource requirements for CPU, memory, disk, I/O, network, etc. Such resource requirements address how much resource is consumed by a task. However, in addition to resource requirements, Google workloads commonly include task placement constraints that determine which machine resources are consumed by tasks. Task placement constraints arise because of task dependencies such as those related to hardware architecture and kernel version.

The nine papers in this special issue focus on recent advances in autonomic communications. This issue addresses four areas in which autonomics play a central role: network architectures, traffic management, monitoring, and resource management.

Resource managers (RMs) often expose configuration parameters that have a significant impact on the performance of the systems they manage. Configuring RMs is challenging because it requires accurate estimates of performance for a large number of configuration settings and many workloads, which scales poorly if configuration assessment requires running performance benchmarks. We propose an approach to evaluating RM configurations called model fuzzing that combines measurement and simple models to provide accurate and scalable configuration evaluation. Based on model fuzzing, we develop a methodology for configuring RMs that considers multiple evaluation criteria (e.g., high throughput, low number of threads). Applying this methodology to the .NET thread pool, we find a configuration that increases throughput by 240% compared with the throughput of a poorly chosen configuration. Using model fuzzing reduces the computational requirements to configure the .NET thread pool from machine-years to machine-hours.

A wide variety of software systems employ closed loops (feedback) to achieve service level objectives and to optimize resource usage. Control theory provides a systematic approach to constructing closed loop systems, and is widely used in disciplines such as mechanical and electrical engineering. This paper describes recent advances in applying control theory to computing systems, and identifies research challenges to address so that control engineering can be widely used by software practitioners.

Application lifecycle management (ALM) provides a wholistic approach to software products, from product requirements through operations. The advent of software product lines (SPLs) such as Microsoftpsilas Visual Studio creates challenges for ALM since product codes are combined in various ways to produce different customer releases or SKUs. This paper proposes an approach to making packaging decisions for SPLs. We begin by showing how industry best practices for application management as described in the IT Infrastructure Library (ITIL) should be extended to include packaging. Next, we develop a cost model and several algorithms that quantify the trade-offs between vendor costs and customer costs. Ideally, we want a packaging scheme that has the smallest customer cost at a given vendor cost. Unfortunately, finding this optimal trade-off by exhaustive search has computational complexity greater than O(n22n), where n is the number of SKUs. We develop a ldquogreedyrdquo algorithm that iteratively selects SKUs to place in the same package so that the smallest packaging overheads result. This approach has complexity O(n4). Our studies of Visual Studio SKUs show that the trade-offs produced by the greedy algorithm converge rapidly to the optimal trade-offs as we increase the number of packages in a packaging scheme.

The complexity of configuring computing systems is a major impediment to the adoption of new information technology (IT) products and greatly increases the cost of IT services. This paper develops a model of configuration complexity and demonstrates its value for a change management system. The model represents systems as a set of nested containers with configuration controls. From this representation, we derive various metrics that indicate configuration complexity, including execution complexity, parameter complexity, and memory complexity. We apply this model to a J2EE-based enterprise application and its associated middleware stack to assess the complexity of the manual configuration process for this application. We then show how an automated change management system can greatly reduce configuration complexity.

The need for service differentiation in Internet services has motivated interest in controlling multi-tier web applications. This paper describes a tier-to-tier (T2T) management architecture that supports decentralized actuator management in multi-tier systems, and a testbed implementation of this architecture using commercial software products. Based on testbed experiments and analytic models, we gain insight into the value of coordinated exploitation of actuators on multiple tiers, especially considerations for control efficiency and control granularity. For control efficiency, we show that more effective utilization of tiers can be achieved by using actuators on the bottleneck tier rather than only using actuators on the entry tier. For granularity of control (the ability to achieve a wide range of service level objectives) we show that a fine granularity of control can be achieved through a coordinated, cross-tier exploitation of coarse grained actuators (e.g., multiprogramming level), an approach that can greatly reduce controllerinduced variability.

Temporal event correlation is essential to managing quality of service in distributed systems, especially correlating events from multiple components to detect problems with availability, performance, and denial of service attacks. Two challenges in temporal event correlation are: (1) handling lost events and (2) dealing with inaccurate clocks. We show that both challenges are related to event propagation delays that result from contention for network and server resources. We develop an approach to adjusting the timer values of event correlation rules based on propagation delays in order to reduce missed alarms and false alarms. Our approach has three parts: an infrastructure for real-time measurement of propagation delay, a statistical approach to estimating propagation delays, and a controller that uses estimates of propagation delays to update timer values in temporal rules. Our approach eliminates the need for manual adjustments of timer values. Further, studies of a prototype implementation suggest that our approach produces results that are at least as good as an optimal fixed adjustment in timer values

In this paper we present a hybrid performance model for modeling differentiated service of multi-tier web applications with per-tier concurrency limits, cross-tier interactions, as well as a work-conserving resource allocation model. The service dependencies between multiple tiers are captured first using a layered queueing model. We then show how to model per-tier concurrency limits and service differentiation between multiple classes while maintaining work conservation at each tier. We use a function approximation approach combined with a coupled processor model. Our model is calibrated from an actual multitier J2EE testbed, and we show the ability of the model to accurately model common performance metrics. Our proposed (layered) model shows 78% improvement in root mean square error over a single-tier machine repair model as well as a tandem queue model. We also demonstrate one application of the model for model-based resource allocation.

The complexity of configuring computing systems is a major impediment to the adoption of new information technology (IT) products and greatly increases the cost of IT services. This paper develops a model of configuration complexity and demonstrates its value for a change management system. The model represents systems as a set of nested containers with configuration controls. From this representation, we derive various metrics that indicate configuration complexity, including execution complexity, parameter complexity, and memory complexity. We apply this model to a J2EE-based enterprise application and its associated middleware stack to assess the complexity of the manual configuration process for this application. We then show how an automated change management system can greatly reduce configuration complexity.

A key concern in utility computing is managing capacity so that application service providers (ASPs) and computing utilities (CUs) operate in a cost effective way. To this end, we propose a framework for applying inventory control to capacity management for utility computing. The framework consists of: conceptual foundations (e.g., establishing connections between concepts in utility computing and those in inventory control); problem formulations (e.g., what factors should be considered and how they affect computational complexity); and quality of service (QoS) forecasting, which is predicting the future effect on QoS of ASP and CU actions taken in the current period (a critical consideration in searching the space of possible solutions).

The high cost of operating large computing installations has motivated a broad interest in reducing the need for human intervention by making systems self-managing. This paper explores the extent to which control theory can provide an architectural and analytic foundation for building self-managing systems. Control theory provides a rich set of methodologies for building automated self-diagnosis and self-repairing systems with properties such as stability, short settling times, and accurate regulation. However, there are challenges in applying control theory to computing systems, such as developing effective resource models, handling sensor delays, and addressing lead times in effector actions. We propose a deployable testbed for autonomic computing (DTAC) that we believe will reduce the barriers to addressing research problems in applying control theory to computing systems. The initial DTAC architecture is described along with several problems that it can be used to investigate.

Utility computing provides a pay-as-you-go approach to information systems in which application providers (e.g., web sites) can better manage their costs by adding capacity in response to increased demands and shedding capacity when it is no longer needed. This paper addresses application providers who use clusters of servers. Our work develops a framework to determine the number of servers that minimizes the sum of quality-of-service (QoS) costs resulting from service level penalties and server holding costs for the server cluster. The server characteristics considered are service rate, failure rates, repair rates, and costs. The contributions of this paper are: 1) a model for the performance and availability of an e-Commerce system that is consistent with data from a multisystem testbed with an e-Commerce workload; 2) a business-oriented cost model for resource allocation for application providers; 3) a closed form approximation for the optimal allocation of servers for an application provider based on the performance model in 1) and the cost model in 2); and 4) a simple criteria for utility owners and server manufacturers to make tradeoffs between server characteristics.

Summary form only given. The high cost of ownership of computing systems has resulted in a number of industry initiatives to reduce the burden of operations and management by making systems more self-managing. A major challenge in realizing self-managing systems is understanding how automated actions affect system behavior, especially system stability. Other disciplines such as mechanical, electrical, and aeronautical engineering make use of control theory to design feedback systems. The talk uses control theory as a way to identify a number of requirements for and challenges in building self-managing, or autonomic, systems. In essence, the autonomic computing architecture describes feedback control loops for self-managing systems. The talk has three goals: (1) educating systems oriented computer science researchers and practitioners on the concepts and techniques needed to apply control theory to computing systems; (2) describing how control theory can aid in building self-managing systems and identifying the challenges in doing so; (3) describing a deployable testbed for autonomic computing that is intended to foster research that addresses the challenges identified.

Autonomic computing (AC) is an initiative that addresses the challenge of managing information technology (IT). The AC approach is to develop technologies and methodologies that make systems more self-managing and more resilient to changes in configurations, workloads and other factors. By so doing, AC reduce the total cost of ownership of IT systems, enable IT systems to deliver business value more rapidly, and increase the quality of service of IT systems. This work highlights the concepts of AC, the business drivers behind it and how the domains of AC address the challenges in today's IT environments. It describes principles of an overarching unified architecture, common building blocks for autonomic systems, some areas of progress and the challenges ahead.

Change management is a process by which IT systems are modified to accommodate considerations such as software fixes, hardware upgrades and performance enhancements. This paper discusses the CHAMPS system, a prototype under development at IBM Research for Change Management with Planning and Scheduling. The CHAMPS system is able to achieve a very high degree of parallelism for a set of tasks by exploiting detailed factual knowledge about the structure of a distributed system from dependency information at runtime. In contrast, today's systems expect an administrator to provide such insights, which is often not the case. Furthermore, the optimization techniques we employ allow the CHAMPS system to come up with a very high quality solution for a mathematically intractable problem in a time which scales nicely with the problem size. We have implemented the CHAMPS system and have applied it in a TPC-W environment that implements an on-line book store application.

Load balancing is widely used in computing systems as a way to optimize performance by reducing bottleneck utilizations, such as adjusting the size of buffer pools to balance resource demands in a database management system. Load balancing is generally approached as a constrained optimization problem in which only the benefits of load balancing are considered. However, the costs of control are important as well. Herein, we study the value of including in controller design the trade-off between the cost of transient imbalances in resource utilizations and the cost of changing resource allocations. An example of the latter are actions such as resizing buffer pools that can reduce throughputs. This is because requests for data in pools whose memory is reduced immediately have longer access times whereas requests for data in pools whose memory is increased must fill this memory with data from disk before accessed times are reduced. We frame our study of control costs in terms of the widely used linear quadratic regulator (LQR). We develop a cost model that allows us to specify the LQR Q and R matrices based on the impact on system performance of changing resource allocations and transient load imbalances. Our studies of a DB2 universal database server using benchmarks for online transaction processing and decision support workloads show that incorporating our cost model into the MIMO LQR controller results in a 14% improvement in performance beyond that achieved by dynamically allocating the size of buffers without properly considering the cost of control.

Optimizing configuration parameters for achieving service level objectives is time-consuming and skills-intensive. This paper proposes a generic approach to automating this task. By generic, we mean that the approach is relatively independent of the target system for which the optimization is done. Our approach uses online adjustment of configuration parameters to discover the system's performance characteristics. Doing so creates two challenges: (1) handling interdependencies between configuration parameters and (2) minimizing the deleterious effects on production workload while the optimization is underway. Our approach addresses (1) by including in the architecture a rule-based component that handles interdependencies between configuration parameters. For (2), we use a feedback mechanism for online optimization that searches the parameter space in a way that generally avoids poor performance at intermediate steps. Our studies of a DB2 Universal Database Server under an e-commerce workload indicate that our approach is effective in practice.

Quantitative models are needed for a variety of management tasks, including identification of critical variables to use for health monitoring, anticipating service-level violations by using predictive models, and ongoing optimization of configurations. Unfortunately, constructing quantitative models requires specialized skills that are in short supply. Even worse, rapid changes in provider configurations and the evolution of business demands mean that quantitative models must be updated on an ongoing basis. This paper describes an architecture and algorithms for online discovery of quantitative models without prior knowledge of the managed elements. The architecture makes use of an element schema that describes managed elements using the Common Information Model (CIM). Algorithms are presented for selecting a subset of the element metrics to use as explanatory variables in a quantitative model and for constructing the quantitative model itself. We further describe a prototype system based onthis architecture that incorporates these algorithms. We apply the prototype to online estimation of response times for DB2 Universal Database under a TPC-W workload. Of the approximately 500 metrics available from the DB2 performance monitor, our system chooses three to construct a model that explains 72 percent of the variability of response time.

Event management is a focal point in building and maintaining high quality information infrastructures. We have witnessed the shift of the paradigm of event management in practice from root cause analysis (RCA) to action-oriented analysis (AOA). IBM has developed a pioneer event management methodology (EMD) based on the AOA paradigm and applied it to more than two hundred production sites with success. Foreseeably, more and more event management professionals will apply AOA in different incarnations in building proactive management facilities. By that, building correct and effective Event Relationship Networks (ERNs) becomes the dominating activity in AOA service design process. Currently, the quality of ERNs and the cost of building them largely depend on the knowledge of domain experts. We believe that we can utilize historical event logs in shortening the ERNs design process and perfecting the quality of ERNs. In this paper, we describe in detail how to apply this data-driven approach in ERN validation, completion and construction.

Exploring large data sets typically involves activities that iterate between data selection and data analysis, in which insights obtained from analysis result in new data selection. Further, data analysis needs to use a combination of analysis techniques: data summarization, mining algorithms and visualization. This interweaving of functions arises both from the semantics of what the analyst hopes to achieve and from scalability requirements for dealing with large data volumes. We refer to such a process as a progressive analysis. Herein is described a tool, Event Miner, that integrates data selection, mining and visualization for progressive analysis of temporal, categorical data. We discuss a data model and architecture. We illustrate how our tool can be used for complex mining tasks such as finding patterns not occurring on Monday. Further, we discuss the novel visualization employed, such as visualizing categorical data and the results of data mining. Also, we discuss the extension of the existing mining framework needed to mine temporal events with multiple attributes. Throughout, we illustrate the capabilities of Event Miner by applying it to event data from large computer networks.

There has been a growing interest in mining frequent itemsets in relational data with multiple attributes. A key step in this approach is to select a set of attributes that group data into transactions and a separate set of attributes that labels data into items. Unsupervised and unrestricted mining, however is stymied by the combinatorial complexity and the quantity of patterns as the number of attributes grows. In this paper we focus on leveraging the semantics of the underlying data for mining frequent itemsets. For instance, there are usually taxonomies in the data schema and functional dependencies among the attributes. Domain knowledge and user preferences often have the potential to significantly reduce the exponentially growing mining space. These observations motivate the design of a user-directed data mining framework that allows such domain knowledge to guide the mining process and control the mining strategy. We show examples of tremendous reduction in computation by using domain knowledge in mining relational data with multiple attributes.

Policy-based management provides a means for IT systems to operate according to business needs. Unfortunately, there is often an "impedance mismatch" between the policies administrators want and the controls they are given. Consider the Apache Web server. Administrators want to control CPU and memory utilizations, but this must be done indirectly by manipulating tuning parameters such as MaxClients and KeepAlive. There has been much interest in using feedback control to bridge the impedance mismatch. However, these efforts have focused on a single metric that is manipulated by a single control and hence have not considered interactions between controls such as those that are common in computing systems. This paper shows how multiple-input, multiple-output (MIMO) control theory can be used to enforce policies for interrelated metrics. MIMO is used both to model the target system, Apache in our case, and to design feedback controllers. The MIMO model captures the interactions between KA and MC, and can be used to identify infeasible metric policies. In addition, MIMO control techniques can provide considerable benefit in handling trade-offs between speed of metric convergence and sensitivity to random fluctuations while enforcing the desired policies.

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...

1 Introduction As it becomes feasible to collect large volumes of data, businesses are increasingly looking for ways to capitalize on these data, especially market data. To date, the focus has been frequent patterns, especially frequent association rules. However, in applications such as detecting anomalies in computer networks and identifying security intrusions, there is much more interest in patterns that predict undesirable situations, such as service disruptions. Such patterns are often infrequent (at least in well managed systems) and are characterized by statistical dependency rather than their frequency. Unfortunately, the statistical dependency based on the dependency test yields neither upward nor downward closure, and hence efficient algorithms cannot be constructed. Herein, we circumvent this problem by proposing fully dependent patterns, d-patterns. D-patterns are defined so as to ensure downward closure, which makes it possible for us to construct an efficient algorithm for their discovery. We apply our algorithm to data from a network at a large insurance company and show that several patterns of interest are discovered[8]. For example, a group of hosts generated port-scan events three times in a week. This provides a possible indicator of a security intrusion. In another example, we observed three events: network interface card failure, unreachable destination, and “cold start” trap often occurred together, although not frequent. The last event indicates that the router has failed and restarted. Then, the first two events may provide advance warning of when the third will occur.

In some domains, such as isolating problems in computer networks and discovering stock market irregularities, there is more interest in patterns consisting of infrequent, but highly correlated items rather than patterns that occur frequently (as defined by minsup, the minimum support level). We describe m-pattern, a new pattern that is defined in terms of minp, the minimum probability of mutual dependence of items in the pattern. We show that all infrequent m-pattern can be discovered by an efficient algorithm that makes use of: (1) a linear algorithm to qualify an m-pattern; (2) an effective technique for candidate pruning based on a necessary condition for the presence of an m-pattern; and (3) a level-wise search for m-pattern discovery (which is possible because m-patterns are downward closed). Further, we consider frequent m-patterns, which are defined in terms of both minp and minsup. Using synthetic data, we study the scalability of our algorithm. Then, we apply our algorithm to data from a production computer network both to show the m-patterns present and to contrast with frequent patterns. We show that when minp=0, our algorithm is equivalent to finding frequent patterns. However, with a larger minp, our algorithm yields a modest number of highly correlated items, which makes it possible to mine for infrequent but highly correlated itemsets. To date, many actionable m-patterns have been discovered in production systems.

Periodic behavior is common in real-world applications. However in many cases, periodicities are partial in that they are present only intermittently. The authors study such intermittent patterns, which they refer to as p-patterns. The formulation of p-patterns takes into account imprecise time information (e.g., due to unsynchronized clocks in distributed environments), noisy data (e.g., due to extraneous events), and shifts in phase and/or periods. We structure mining for p-patterns as two sub-tasks: (1) finding the periods of p-patterns and (2) mining temporal associations. For (2), a level-wise algorithm is used. For (1), we develop a novel approach based on a chi-squared test, and study its performance in the presence of noise. Further we develop two algorithms for mining p-patterns based on the order in which the aforementioned sub-tasks are performed: the period-first algorithm and the association-first algorithm. Our results show that the association-first algorithm has a higher tolerance to noise; the period-first algorithm is more computationally efficient and provides flexibility as to the specification of support levels. In addition, we apply the period-first algorithm to mining data collected from two production computer networks, a process that led to several actionable insights.

In some domains, such as isolating problems in computer networks and discovering stock market irregularities, there is more interest in patterns consisting of infrequent, but highly correlated items rather than patterns that occur frequently (as defined by minsup, the minimum support level). We describe the m-pattern, a new pattern that is defined in terms of minp, the minimum probability of mutual dependence of items in the pattern. We show that all infrequent m-patterns can be discovered by an efficient algorithm that makes use of: (a) a linear algorithm to qualify an m-pattern; (b) an effective technique for candidate pruning based on a necessary condition for the presence of an m-pattern; and (c) a level-wise search for m-pattern discovery (which is possible because m-patterns are downward closed). Further, we consider frequent m-patterns, which are defined in terms of both minp and minsup. Using synthetic data, we study the scalability of our algorithm. Then, we apply our algorithm to data from a production computer network both to show the m-patterns present and to contrast with frequent patterns. We show that when minp=0, our algorithm is equivalent to finding frequent patterns. However, with a larger minp, our algorithm yields a modest number of highly correlated items, which makes it possible to mine for infrequent but highly correlated itemsets. To date, many actionable m-patterns have been discovered in production systems.

Mining for frequent itemsets typically involves a preprocessing step in which data with multiple attributes are grouped into transactions, and items are defined based on attribute values. We hake observed that such fixed attribute mining can severely constrain the patterns that are discovered. Herein, we introduce mining spaces, a new framework for mining multi-attribute data that includes the discovery of transaction and item definitions (with the exploitation of taxonomies and functional dependencies if they are available). We prove that special downward closure properties (or anti-monotonic property) hold for mining spaces, a result that allows us to construct efficient algorithms for mining patterns without the constraints of fixed attribute mining. We apply our algorithms to real world data collected from a production computer network. The results show that by exploiting the special kinds of downward closure in mining spaces, execution times for mining can be reduced by a factor of three to four.

For large installations, event management is critical to ensuring service quality by responding rapidly to exceptional situations. The key to this is having experts encode their knowledge (e.g., in rules, state machines, codebooks) about the relationship between event patterns and actions to take. Unfortunately, doing so is time-consuming and knowledge-intensive. We propose reducing this burden by using offline decision support consisting of visualizing and mining event histories to discover patterns in event data. Our experience with a wide variety of production data has identified several patterns of interest such as, event bursts and partial periodicities. Herein, we use production data to illustrate how to visualize and mine event patterns, and we describe a tool we have developed to aid in pattern discovery.

A widely used approach to achieving service level objectives for a software system (e.g., an email server) is to add a controller that manipulates the target system's tuning parameters. We describe a methodology for designing such controllers for software systems that builds on classical control theory. The classical approach proceeds in two steps: system identification and controller design. In system identification, we construct mathematical models of the target system. Traditionally, this has been based on a first-principles approach, using detailed knowledge of the target system. Such models can be complex and difficult to build, validate, use, and maintain. In our methodology, a statistical (ARMA) model is fit to historical measurements of the target being controlled. These models are easier to obtain and use and allow us to apply control-theoretic design techniques to a larger class of systems. When applied to a Lotus Notes groupware server, we obtain model fits with R/sup 2/ no lower than 75% and as high as 98%. In controller design, an analysis of the models leads to a controller that will achieve the service level objectives. We report on an analysis of a closed-loop system using an integral control law with Lotus Notes as the target. The objective is to maintain a reference queue length. Using root-locus analysis from control theory, we are able to predict the occurrence (or absence) of controller-induced oscillations in the system's response. Such oscillations are undesirable since they increase variability, thereby resulting in a failure to meet the service level objective. We implement this controller for a real Lotus Notes system, and observe a remarkable correspondence between the behavior of the real system and the predictions of the analysis. This indicates that the control theoretic analysis is sufficient to select controller parameters that meet the desired goals, and the need for simulations is reduced.

Event management is a corner stone of high quality service delivery. To date, the focus of event management has been root cause analysis (RCA). We believe that this focus is misdirected in that it does not consider what action to take. Indeed, the root cause may not be actionable, and actions may be required for factors that are unrelated to a root cause (e.g., a condition that signals the end of a problem). We propose a new framework for event management-action oriented analysis (AOA). AOA assigns roles to events so as to determine the actions to take if an event is received. In many cases, the same event can have different roles depending on the context. These ambiguities are resolved by analyzing event relationship networks. AOA also addresses what information is needed from event sources and subject matter experts. This information is identified and extracted by a set of four activities that we refer to as event management design. AOA has been used with much success at IBM's ISM installation and over fifty other production sites.

Studies the effects of correlations between the inter-arrival times of different service classes. An analysis of distributed information systems reveals that such inter-class correlations exist, in part as a result of the interactions between the server and its clients. To gain insight into the performance implications of these correlations, we formulate a general stochastic model that explicitly captures client-server interactions, and we derive a matrix analysis of a specific instance of the model. Our results illustrate and quantify the impact that such inter-class correlations can have on system performance.

Predicting network performance problems enables network operators to take corrective actions in advance of service disruptions. Typically, service problems are detected by tests that compare a metric (e.g., response time) to a threshold. The authors present an online algorithm for predicting the probability of threshold violations over a time horizon. The algorithm uses two cascaded submodels. The first removes non-stationarities by employing a discrete time Kalman filter in combination with analysis of variance. We derive parameters of the Kalman filter from differential equations that describe characteristics of the data. The second submodel estimates the probability of threshold violations by using a second order autoregressive model in combination with change-point detection. Using data from a production Web server, we evaluate our approach and show that it produces average accuracies that are comparable to those of an offline algorithm. However, our online algorithm produces predictions with considerably smaller variances. Further advantages of our approach are: (a) requiring much less data than the offline technique, one day versus multiple months; and (b) adapting to changes in the system and workloads since parameters are estimated online.

Proactive management holds the promise of taking corrective actions in advance of service disruptions. Achieving this goal requires predictive models so that potential problems can be anticipated. Our approach builds on previous research in which HTTP operations per second are studied in a Web server. As in this prior work, we model HTTP operations as two subprocesses, a (deterministic) trend subprocess and a (random but stationary) residual subprocess. Herein, the trend model is enhanced by using a low-pass filter. Further, we employ techniques that reduce the required data history, thereby reducing the impact of changes in the trend process. As in the prior work, an autoregressive model is used for the residual process. We study the limits of the autoregressive model in the prediction of network traffic. Then we demonstrate that long-range dependencies remain in the residual process even after autoregressive components are removed, which impacts our ability to predict future observations. Last, we analyze the validity of assumptions employed, especially the normality assumption.

Detecting and resolving performance problems in distributed systems often requires measurements of end-to-end ("finger tip to eyeball") response times. Existing approaches embed transaction definitions in instrumentation codes. As a result, service providers (e.g., ISPs) cannot tailor transaction definitions to the usage patterns of their customers. We propose a new approach-ETE (end-to-end)-in which transaction definitions are externalized so that they can be customized. This is accomplished by having instrumentation generate events (not transactions) and employing a separate component-the transaction generator-that uses external definitions of transactions to construct response time measurements from event streams. ETE provides measurements of both end-to-end response times and their components. The latter reflect delays for services within distributed systems (e.g., name resolution service). We have used ETE to measure response times for Web transactions, terminal emulators, and Lotus Notes.

Service providers typically define quality of service problems using threshold tests, such as "are HTTP operations greater than 12 per second on server XYZ?" This paper explores the feasibility of predicting violations of threshold tests. Such a capability would allow providers to take corrective actions in advance of service disruptions. Our approach estimates the probability of threshold violations for specific times in the future. We modeled the threshold metric (e.g., HTTP operations per second) at two levels: (1) nonstationary behavior (as is done in workload forecasting for capacity planning) and (2) stationary, time-serial dependencies. Using these models, we compute the probability of threshold violations. We asses our approach using measurements of HTTP operations per second collected from a production Web server. These assessments suggest that our approach works well if: (a) the actual values of predicted metrics are sufficiently distant from their thresholds; and/or (b) the prediction horizon is not too far into the future.

Constructing quantitative models typically requires characterizing a system in terms of algebraic relationships and then using these relationships to compute quantitative values from numerical data. For real-life systems, such as computer operating systems, an algebraic characterization is often difficult, if not intractable. The paper proposes a statistical approach to constructing quantitative models using monotone relationships. Referred to as nonparametric interpolative-estimation for monotone functions (NIMF), our approach uses monotone relationships to search historical data for bounds that provide a desired level of statistical confidence. NIMF makes no assumption about the algebraic form of the monotone relationship, not even continuity. We present two examples of applying NIMF to computer measurements, and compare NIMF's confidence intervals with those of least-squares regression, a traditional technique that requires specifying an algebraic relationship. Our results suggest that when an algebraic characterization is not known with precision, using NIMF with an accurate monotone relationship can produce more accurate confidence intervals than employing least-squares regression with a polynomial approximation to the unknown algebraic relationship.>

No abstract available.

Decay usage scheduling is a priority- and usage-based approach to CPU allocation in which preference is given to processes that have consumed little CPU in the recent past. The author develops an analytic model for decay usage schedulers running compute-bound workloads, such as those found in many engineering and scientific environments; the model is validated from measurements of a Unix system. This model is used in two ways. First, ways to parameterize decay usage schedulers are studied to achieve a wide range of service rates. Doing so requires a fine granularity of control and a large range of control. The results show that, for a fixed representation of process priorities a larger range of control makes the granularity of control coarser, and a finer granularity of control decreases the range of control. A second use of the analytic model is to construct a low overhead algorithms for achieving service rate objectives. Existing approaches require adding a feedback loop to the scheduler. This overhead is avoided by exploiting the feedback already present in decay usage schedulers. Using both empirical and analytical techniques, it is shown that the algorithm is effective and that it provides fairness when the system is over- or under-loaded.>

No abstract available.

Resolving intermittent performance problems in computer systems is made easier by pinpointing when a change occurs in the system's perforrnance-determinin g factors (e.g., workload composition, configuration). Since we often lack direct measurements of performance factors, this paper presents a procedure for indirectly detecting such changes by analyzing performance characteristics (e.g., response times, queue lengths). Our procedure employs a widely used clustering algorithm to identify candidate change points (the times at which performance factors change), and a newly developed statistical test (based on an AR(1) time series model) to determine the signficance of candidate change points. We evaluate our procedure by using simulations of M/M/1, FCFS queueing systems and by applying our procedure to measurements of a mainframe computer system at a large telephone company. These evaluations suggest that our procedure is effective in practice, especially for larger sample sizes and smaller utilizations. We further conclude that indirectly detecting changes in performance factors appears to be inherently difficult in that the sensitivity of a detection procedure depends on the magnitude of the change in performance characteristics, which often has a nonlinear relationship with the change in performance factors. Thus, a change in performance factors (e.g., increased service times) may be more readily detected in some situations (e.g., very low or very high utilizations) than in others (e.g., moderate utilizations). A key insight here is that the sensitivity of the detection procedure can be improved by choosing appropriate measures of performance characteristics. For example, our experience and analysis suggest that queue lengths can be more sensitive than response times to changes in arrival rates.

Managing a computer system requires that good performance (e.g., large throughputs, small response times) be maintained in order to meet business objectives. Rarely is performance consistently bad. More frequently, performance is good one day and bad the next. Diagnosing such intermittent performance-problems involves determining what distinguishes bad days from good days, such as larger paging rates. Once this is understood, an appropriate remedy can be found, such as buying more memory. This paper describes a statistical approach to diagnosing intermittent performance-problems when the relationships among measurement variables are expressed qualitatively as monotone relationships (e.g., paging delays increase with the number of logged-on users). We present a non-parametric test for monotonicity (NTM) that evaluates monotone relationships based on FA, the fraction of observation-pairs that agree with the monotone relationship. An interpretation of FA in terms of statistical significance levels is presented, and NTM is compared to least-squares regression. Based on NTM, an algorithm for diagnosing intermittent performance-problems is presented. NTM and our diagnosis algorithm are applied to measurements of four similarly configured IBM 9370 model 60s running IBM's operating-system Virtual Machine System Product (VM SP).

Consistency control protocols can be classified as either pessimistic or optimistic. Pessimistic protocols check for conflicting file accesses before a transaction references shared files; this prevents transaction restarts but adds intercomputer synchronization delays to execution response times TE. Optimistic protocols avoid intercomputer synchronization delays for TE, but existing optimistic protocols repeatedly restart a transaction until it executes without conflict. Repeated restarts lengthen the time to finalize an update TU, and can saturate the computing and communication resources. We present two new optimistic protocols that avoid repeated restarts: the exclusive-writer protocol (EWP) and the exclusive-writer protocol with locking option (EWL). EWP has no transaction restarts, database rollbacks, or deadlocks due to shared data access. But EWP ensures only a limited form of serializability. EWL is an extension of EWP that ensures full serializability. EWL has no database rollbacks. Also, EWL can guarantee that a transaction will be restarted at most once. To further reduce restarts, each site can independently and dynamically switch between primary site locking (PSL), which has no restarts, and EWL. Such switching requires no additional messages or delays to synchronize protocol selection. Analytic models are developed to study the response times (i.e., TEand TU) of EWP, EWL, PSL, and basic timestamps (BTS). Our study reveals that EWP and EWL have the smallest TF since neither requires update-log maintenance (unlike BTS) nor intercomputer synchronization delays for TE(unlike PSL). EWP has the smallest TUunless the cost of communicating and processing updates is high.

Communication among program modules plays an important role in the performance of distributed processing systems. In this paper, a model for estimating intermodule communication (IMC) is developed. The model derives communication volume based on module invocation rates and file access probabilities via the control-and-data-flow graph. The IMC model is validated by simulation experiments. Interprocessor communication (IPC) and system resources utilization can be estimated from the IMC. We show that IMC and IPC are useful in finding good module assignments in distributed processing systems.