The rapid growth of Artificial Intelligence (AI) workloads has introduced unprecedented challenges to modern cloud-native systems, particularly in Kubernetes (K8s)-based environments. These workloads often demand low-latency communication, high resource locality, and efficient utilization of heterogeneous hardware devices such as Graphics Processing Units (GPUs) and specialized accelerators. However, the existing scheduling mechanisms in K8s are typically unaware of the underlying physical topology, leading to performance degradation and inefficient resource usage. This paper presents Sakkara, a novel topology-aware scheduling framework designed to optimize the placement of AI workloads in K8s clusters. Sakkara incorporates a hierarchical model of the Data Center (DC), including nodes and racks, enabling flexible scheduling strategies that account for resource availability and risk-aware metrics that mitigate performance interference and constraint violations caused by topology-unaware placement. Sakkara extends existing scheduling logic in K8s with placement strategies that guide pod allocation using configurable topology constraints, aiming to minimize communication costs and maximize workload performance. We evaluated Sakkara on a representative AI workload, a distributed training application under different cluster configurations. Experimental results show that Sakkara improves job completion time, throughput, and memory utilization compared to available K8s schedulers, achieving improvements of up to 10%. Sakkara, available as open-source, offers a promising pathway toward topology-conscious orchestration of AI workloads in next-generation cloud environments.

Increasing demand from AI/ML workloads is exacerbating the rising energy consumption of data centers. Recent advances in hardware such as NVIDIA's Multi Instance GPUs (MIGs) offer improvements in flexibility and computational power and the opportunity for data centers to manage incoming jobs in energy-efficient ways, while maintaining acceptable performance. The challenge in achieving this multi-objective in a MIG environment through job scheduling is multi-faceted. Firstly, for a given MIG configuration, one seeks an easy-toimplement scheduling algorithm which selects a job from the queue as well as decides on which slice in the configuration the job runs. Secondly, for the identified scheduling algorithm, a particular MIG configuration may not always be suitable (as the workload fluctuates) and may need to be repartitioned. We tackle both problems using simulations and reinforcement learning (RL). We present a dynamic repartitioning scheduling framework for a single MIG as a solution to a multi-objective heterogeneous machine scheduling problem with preemption. In particular, we compare four scheduling algorithms and identify a promising one. Then, we employ reinforcement learning to perform dynamic repartitioning over a day. Furthermore, using a diurnal workload pattern based on real-world data center traces, we demonstrate the superiority of our dynamic repartitioning algorithm over twice-daily repartitioning (26%), static partitioning (31%) and no partitioning at all (68%) according to a multi-objective function of energy consumption and tardiness. Our results indicate specific preferred configurations at different times of the day under different queue conditions, suggesting a policy for predictive and automatic reconfiguration.

The exponential growth in Artificial Intelligence (AI) adoption presents unique challenges and opportunities for deploying AI workloads in modern Data Center (DC) networks, particularly in terms of performance, scalability, and reliability. AI workloads, such as inference and distributed training, impose different network demands: inference is primarily computebound and typically requires low network latency, while distributed training is network-bound and requires high bandwidth, placing significant strain on the network. This paper focuses on the network requirements of widely known AI communication patterns, and studies their impact on modern DC architectures by analyzing the effects of different orchestration strategies-specifically packing and spreading-on throughput, response time, and network congestion. The results show that packing strategies generally deliver higher performance for most covered AI collectives. However, spreading strategies can be beneficial in certain scenarios, such as when larger workloads span across higher number of racks, as they can help mitigate network congestion between the switches of leaf-spine network configurations. This paper offers valuable insights into optimizing the orchestration of popular AI collectives in data center networks, presenting informed strategies to improve performance in response to growing AI demands, with findings demonstrating completion time reductions of up to 30 %.

This paper explores resource allocation in server-less cloud computing platforms and proposes an optimization approach for autoscaling systems. Serverless computing relieves users from resource management tasks, enabling focus on application functions. However, dynamic resource allocation and function replication based on changing loads remain crucial. Typically, autoscalers in these platforms utilize threshold-based mechanisms to adjust function replicas independently. We model applications as interconnected graphs of functions, where requests probabilistically traverse the graph, triggering associated function execution. Our objective is to develop a control policy that optimally allocates resources on servers, minimizing failed requests and response time in reaction to load changes. Using a fluid approximation model and Separated Continuous Linear Programming (SCLP), we derive an optimal control policy that determines the number of resources per replica and the required number of replicas over time. We evaluate our approach using a simulation framework built with Python and simpy. Comparing against threshold-based autoscaling, our approach demonstrates significant improvements in average response times and failed requests, ranging from 15% to over 300% in most cases. We also explore the impact of system and workload parameters on performance, providing insights into the behavior of our optimization approach under different conditions. Overall, our study contributes to advancing resource allocation strategies, enhancing efficiency and reliability in serverless cloud computing platforms.

As cloud-native workflow orchestration tools become increasingly important for complex data science workloads, there is a growing need for more efficient scheduling. Existing cloud schedulers rely on basic heuristics and user choice for task partitioning for parallel computing, leading to under-utilization of cluster resources and prolonged job completion times. To address this, we propose a novel workflow scheduling algorithm that leverages workflow characteristics to enhance resource utilization and reduce weighted job completion time. The algorithm combines three sub-algorithms, each reflecting a distinct aspect of the scheduling strategy: 1) Hybrid Maximum Children (MC) -Weighted Shortest Critical Path Time (WSCPT) rule alternates between two heuristics, MC and WSCPT, which prioritize jobs based on workflow structure and critical path, respectively. The choice between these heuristics is dynamically adjusted according to the cluster queue size. 2) Dynamic Resource Allocation (DRA), which dynamically adjusts the number of executors assigned to each workflow, and 3) Dynamic Task Partition (DTP), which autonomously determines the task parallelism level. We tested our algorithm with extensive experiments on various workflow types using Spark-imitated simulation. Our algorithm outperformed other schedulers, including learning-based models, by reducing 21-47% of the combined performance of average job completion time and makespan for unweighted workflows and reducing at least 50% of weighted job completion time for weighted workflows.

The surge in demand for computing resources in data centers coupled with the rise of environmental concerns has motivated cloud providers to reduce carbon emission due to computational energy consumption. An opportunity lies in the fluctuating availability of renewable energy over time and the variability of power sources over grid regions, leading to variations in space and time in carbon intensity. Exploiting such variations, this paper introduces Caspian, a carbon-aware workload scheduler in multi-cluster Kubernetes environments, which aims at reducing the Carbon Footprint (CFP) due to executing workloads, while satisfying Quality of Service (QoS) requirements. Caspian cooperates with a multi-cluster management platform to apply scheduling and placement decisions over distributed clusters. We present efficient optimization algorithms to achieve these goals. Further, we describe an implementation of Caspian, integrated with Multi Cluster App Dispatcher (MCAD), a multi-cluster management platform which handles queuing and dispatching of workloads over multiple clusters. Our experimental results show that Caspian effectively reduces CFP with reasonable QoS, compared to a baseline scheduler which only satisfies the QoS of workloads. Specifically, Caspian reduces CFP by about 33%, with about 98% of workloads completing at an average fraction of 0.6 of their deadline.

The amount of carbon emission associated with the computational energy consumption in data centers depends, in a significant way, on the schedule of the workloads. Due to the inconsistent availability of renewable energy over time, in addition to the existence of various sources of power in grid regions, the carbon intensity of data centers changes over time and location. Thus, the placement and scheduling of flexible workloads, based on the carbon intensity of power sources in data centers, can remarkably decrease the carbon emission. In this paper, we address the problem of placement and scheduling of workloads over geographically distributed data centers. We propose two algorithms that take the variability of carbon intensity of the power sources of the data centers, as well as their computational resource availability, into account when deciding about the placement and scheduling of the workloads. The first is a randomized rounding approximation algorithm that provides solutions that are guaranteed to be within a given distance from the optimal solution. The second is a sample-based algorithm that improves the solutions obtained by the randomized rounding approximation algorithm. The experimental results show that the proposed algorithms can solve the problem efficiently.

Efficient placement of advanced HPC and AI workloads with application constraints is raising challenges for resource schedulers on shared infrastructures, such as the Cloud. In this work, we propose a novel Constraints- and Heuristics-based scheduler on HIerarchical Topologies for High-Performance Computing workloads in the Cloud (chic-sched, for short). Our heuristics-based algorithm enables placement across multiple levels in a network hierarchy with loosely specified constraints, and it works without retries by providing suboptimal placements to minimize placement failures. This allows for fast scheduling at scale, and the O(N log N) complexity enables placement decisions within tens of milliseconds for groups of hundreds of virtual machines (VM). We introduce a new and simple metric to quantify the goodness of group placements. With this metric, in terms of deviation from ideal placements, we show that chic-sched is 20-50% better than the common bestFit or worstFit algorithms in all scenarios of two-level placements with spreading and packing constraints. We evaluate chic-sched with publicly available VM-request traces from a production Cloud, and, comparing against bestFit, we show that it achieves 8% lower placement failure rates and more than 40% better placement locality. Finally, to quantify the goodness of constraints-based placements, we conduct experiments with a realistic MPI workload on synthetically allocated VM clusters in a public cloud. We measure a 9% performance improvement over an adverse placement in a scenario where our heuristics-based scheduler would return a good, but not perfect, placement.

In this paper, we address the problem of workload scheduling in data centers, while considering the greenness of the power sources. We prove that finding a feasible solution for the problem is NP-hard. Therefore, we develop an LP-based approximation algorithm to solve the problem in polynomial time. The proposed algorithm provides strong approximation bounds on the constraints and the objective of the problem. We conduct an extensive experimental analysis to evaluate the performance of the proposed algorithm using real world data.

Demand for efficient cloud-native workflow scheduling is growing as many data science workloads are composed of several tasks with dependencies. As container technology becomes more prevalent in cloud communities, containerized workflow orchestration tools are introduced and become standard for scheduling workflows. However, current schedulers use simple heuristics and rely on the user's choice on priority and parallelism level of tasks without accounting for workflow-specific information.

Large cloud providers offer spot instances at attractive prices to improve resource utilization, resulting in a spot market where users bid for resources and providers alter prices dynamically. As prices surpass bid values, resources may be relinquished from users with low bids. Achieving predictable performance on spot markets is challenging for data analytics workloads because they are very sensitive to preemptions due to the excessive cost of recomputations.We introduce capri, a scheduling system for running cloud data analytics in spot markets in which users may experience periods of degraded performance. capri dynamically predicts the functional relationship between bid and performance, thus helping with managing expectations and bid advice. We propose a new spot market abstraction called the bribe scheduler which delivers differentiated service levels based on bids. capri uses a prediction mechanism built on a queueing approximation of the bribe scheduler. capri dynamically estimates parameters to adapt the queueing model and provide accurate performance predictions in the face of time-varying workloads.We collect measurements using capri running two realistic workloads, imdb and tpcds, and demonstrate the accuracy of our approximation and parameter estimation methodology. We show that capri achieves a median prediction error below 3% in bursty workloads. We find that capri‘s service level prediction is pessimistic as users are likely to experience better performance than they should receive for their bids.

Deep learning (DL) is becoming increasingly popular in several application domains and has made several new application features involving computer vision, speech recognition and synthesis, self-driving automobiles, drug design, etc. feasible and accurate. As a result, large scale "on-premise" and "cloud-hosted" deep learning platforms have become essential infrastructure in many organizations. These systems accept, schedule, manage and execute DL training jobs at scale.

Hosting data analytics services is challenging as their workload is often composed of on-line (e.g., interactive or streaming), requiring fast on-demand provisioning, and batch jobs. As workload demand fluctuations lead to varying idle capacity, efficient resource management is difficult, in particular given different provider objectives, e.g., utilization, revenue.

Spark Streaming discretizes streams of data into micro-batches, each of which is further sub-divided into tasks and processed in parallel to improve job throughput. Previous work [2, 3] has lowered end-to-end latency in Spark Streaming. However, two causes of high tail latencies remain unaddressed: 1) data is not load-balanced across tasks, and 2) straggler tasks can increase end-to-end latency by 8 times more than the median task on a production cluster [1]. We propose a feedback-control mechanism that allows frameworks to adaptively load-balance workloads across tasks according to their processing speeds. The task runtimes are thus equalized, lowering end-to-end tail latency. Further, this reduces load on machines that have transient resource bottlenecks, thus resolving the bottlenecks and preventing them from having an enduring impact on task runtimes.

Recently, more and more enterprises have adopted hybrid cloud strategies to simultaneously enjoy the security of on-premise clouds and the low cost of public clouds. The key challenge of hybrid clouds, though, stems from the difficulty of specifying where the data should be stored and where the information could flow efficiently. In order to meet security concerns and performance requirements, we introduce a coarse-grained information flow control (CIFC) model to limit storing, accessing, and disclosing of confidential data in public clouds. The CIFC model aims at providing information control implicitly, without the large overhead of periodically checking access privileges. Moreover, since the CIFC model may request redistributing data whenever the secrecy level of a dataset changes, we formulate the data redistribution problem as an optimization problem and propose the Partition Biased Sampling Algorithm (PBSA) for its solution. We implemented the CIFC model on top of Spark, and our results show that Spark applications can achieve 1.4 to 2.1 times better performance by utilizing the additional computational capacity of public cloud to process non-sensitive data. Furthermore, we integrate the PBSA algorithm into Spark and demonstrate a saving of more than 35% in execution time, compared to the Spark default data distribution strategy.

We consider a cloud environment, consisting of physical entities, subjected to user application requests, consisting of logical entities with relationship constraints among them, such as location constraints. We are concerned with the application placement problem, which is a mapping of logical to physical entities that satisfies the constraints and optimizes an objective function, which combines system and user performance. We describe an efficient technique that is based on random search methods and uses biased statistical sampling methods and demonstrate the feasibility of our methodology using a large-size simulation experiment. We note that the magnitude of biasing has an important impact on the quality of placement and investigate the tradeoff between biasing and optimality of placement solutions.

Cloud service providers enable enterprises with the ability to place their business applications into availability zones across multiple locations worldwide. While this capability helps achieve higher availability with smaller failure rates, business applications deployed across these independent zones may experience different quality of service (QoS) due to heterogeneous physical infrastructures. Since the perceived QoS against specific requirements are not usually advertised by cloud providers, selecting an availability zone that would best satisfy the user requirements is a challenge. In this paper, we introduce a predictive approach to identify the cloud availability zone that maximizes satisfaction of an incoming request against a set of requirements. The prediction models are built from historical usage data for each availability zone and are updated as the nature of the zones and requests change. Simulation results show that our method successfully predicts the unpublished zone behavior from historical data and identifies the availability zone that maximizes user satisfaction against specific requirements.

Cloud service providers enable enterprises with the ability to place their business applications into availability zones across multiple locations worldwide. While this capability helps achieve higher availability with smaller failure rates, business applications deployed across these independent zones may experience different Quality of Service (QoS) due to heterogeneous physical infrastructures. Since the perceived QoS against specific requirements are not usually advertised by cloud providers, selecting an availability zone that would best satisfy the user requirements is a challenge. In this paper, we introduce a predictive approach to identify the cloud availability zone that maximizes satisfaction of an incoming request against a set of requirements. The predictive models are built from historical usage data for each availability zone and are updated as the nature of the zones and requests change. Simulation results show that our method successfully predicts the unpublished zone behavior from historical data and identifies the availability zone that maximizes user satisfaction against specific requirements.

A fully functional hybrid cloud solution requires a placement service to automatically decide whether an application should be deployed on premise, in a public cloud, or across private and public clouds. Such a service must consider application structure and communication patterns, application affinity requirements, which usually result from data protection rules, and deployment costs. In this paper, we propose a hybrid cloud placement approach which addresses these challenges. Our approach considers application requirements, cost, and private cloud capacity. Further, it is tunable to allow for changing application patterns and business objectives and offers a useful trade-off between application QoS and its deployment cost.

Given the dynamic nature of the cloud, resulting from mapping virtual to physical resources, changes in the usage pattern of resources, migration of virtual resources and the dynamic nature of the applications themselves, the bottleneck resource in a given application changes over time. Promptly identifying the bottleneck of cloud application and consequently taking corrective actions (e.g. admission control) are essential requirements for cloud application performance management. The traditional threshold based bottleneck detection technology, which adopts a pre-defined target performance measure (e.g. response time, CPU utilization, etc.), requires a good understanding of the application. It is difficult to identify which performance measures need to be monitored and how to set accurate threshold values for them. The commonly used technique of model-based workload management also faces a big challenge in modeling the highly dynamic, cloud application behavior. In this paper, we propose a self-optimizing application workload management solution for cloud applications which adapts well to the cloud dynamics. It utilizes a target-less bottleneck detection mechanism, without the need to define target thresholds. It also contains a model-free controller for workload management, thus avoiding the complexity of dynamically changing the model as the cloud environment changes. We believe that this is the first time such a design principle to cloud application performance management is introduced. The validity and efficiency of this solution have been verified by a real-case study on an IBM cloud platform, using the RUBiS web application benchmark.

We consider the problem of admitting sets of, possibly heterogenous, virtual machines (VMs) with stochastic resource demands onto physical machines (PMs) in a Cloud environment. The objective is to achieve a specified quality-of-service related to the probability of resource over-utilization in an uncertain loading condition, while minimizing the rejection probability of VM requests. We introduce a method which relies on approximating the probability distribution of the total resource demand on PMs and estimating the probability of over-utilization. We compare our method to two simple admission policies: admission based on maximum demand and admission based on average demand. We investigate the efficiency of the results of using our method on a simulated Cloud environment where we analyze the effects of various parameters (commitment factor, coefficient of variation etc.) on the solution for highly variate demands.

We consider the problem of placing virtual clusters, each consisting of a set of heterogeneous virtual machines (VM) with some interrelationships due to communication needs and other dependability-induced constraints, onto physical machines (PM) in a large data center. The placement of such constrained, networked virtual clusters, including compute, storage, and networking resources is challenging. The size of the problem forces one to resort to approximate and heuristics-based optimization techniques. We introduce a statistical approach based on importance sampling (also known as cross-entropy) to solve this placement problem. A straightforward implementation of such a technique proves inefficient. We considerably enhance the method by biasing the sampling process to incorporate communication needs and other constraints of requests to yield an efficient algorithm that is linear in the size of the data center. We investigate the quality of the results of using our algorithm on a simulated system, where we study the effects of various parameters on the solution and performance of the algorithm.

In this work we are concerned with the cost associated with replicating intermediate data for dataflows in Cloud environments. This cost is attributed to the extra resources required to create and maintain the additional replicas for a given data set. Existing data-analytic platforms such as Hadoop provide for fault-tolerance guarantee by relying on aggressive replication of intermediate data. We argue that the decision to replicate along with the number of replicas should be a function of the resource usage and utility of the data in order to minimize the cost of reliability. Furthermore, the utility of the data is determined by the structure of the dataflow and the reliability of the system. We propose a replication technique, which takes into account resource usage, system reliability and the characteristic of the dataflow to decide what data to replicate and when to replicate. The replication decision is obtained by solving a constrained integer programming problem given information about the dataflow up to a decision point. In addition, we built a working prototype, CARDIO of our technique which shows through experimental evaluation using a real testbed that finds an optimal solution.

We introduce an algorithm for the placement of constrained, networked virtual clusters in the cloud, that is based on importance sampling (also known as cross-entropy). Rather than using a straightforward implementation of such a technique, which proved inefficient, we considerably enhance the method by biasing the sampling process to incorporate communication needs and other constraints of placement requests to yield an efficient algorithm that is linear in the size of the cloud. We investigate the quality of the results of using our algorithm on a simulated cloud.

This paper introduces several novel load-balancing algorithms for distributing Session Initiation Protocol (SIP) requests to a cluster of SIP servers. Our load balancer improves both throughput and response time versus a single node while exposing a single interface to external clients. We present the design, implementation, and evaluation of our system using a cluster of Intel x86 machines running Linux. We compare our algorithms to several well-known approaches and present scalability results for up to 10 nodes. Our best algorithm, Transaction Least-Work-Left (TLWL), achieves its performance by integrating several features: knowledge of the SIP protocol, dynamic estimates of back-end server load, distinguishing transactions from calls, recognizing variability in call length, and exploiting differences in processing costs for different SIP transactions. By combining these features, our algorithm provides finer-grained load balancing than standard approaches, resulting in throughput improvements of up to 24% and response-time improvements of up to two orders of magnitude. We present a detailed analysis of occupancy to show how our algorithms significantly reduce response time.

System noise or Jitter is the activity of hardware, firmware, operating system, runtime system, and management software events. It is shown to disproportionately impact application performance in current generation large-scale clustered systems running general-purpose operating systems (GPOS). Jitter mitigation techniques such as co-scheduling jitter events across operating systems improve application performance but their effectiveness on future petascale systems is unknown. To understand if existing co-scheduling solutions enable scalable petascale performance, we construct two complementary jitter models based on detailed analysis of system noise from the nodes of a large-scale system running a GPOS. We validate these two models using experimental data from a system consisting of 128 GPOS instances with 4096 CPUs. Based on our models, we project a minimum slowdown of 2.1%, 5.9%, and 11.5% for applications executing on a similar one petaflop system running 1024 GPOS instances and having global synchronization operations once every 1000 msec, 100 msec, and 10 msec, respectively. Our projections indicate that additional system noise mitigation techniques are required to contain the impact of jitter on multi-petaflop systems, especially for tightly synchronized applications.

This paper describes an integrated monitoring and control framework for managing performance of distributed enterprise systems.

This paper introduces several novel load balancing algorithms for distributing session initiation protocol (SIP) requests to a cluster of SIP servers. Our load balancer improves both throughput and response time versus a single node, while exposing a single interface to external clients. We present the design, implementation and evaluation of our system using a cluster of Intel x86 machines running Linux. We compare our algorithms with several well-known approaches and present scalability results for up to 10 nodes. Our best algorithm, transaction least-work-left (TLWL), achieves its performance by integrating several features: knowledge of the SIP protocol; dynamic estimates of back-end server load; distinguishing transactions from calls; recognizing variability in call length; and exploiting differences in processing costs for different SIP transactions. By combining these features, our algorithm provides finer-grained load balancing than standard approaches, resulting in throughput improvements of up to 24 percent and response time improvements of up to two orders of magnitude. We present a detailed analysis of occupancy to show how our algorithms significantly reduce response time.

Modern, adaptive software systems must often adjust or reconfigure their architecture in order to respond to continuous changes in their execution environment. Efficient autonomic control in such systems is highly dependent on the accuracy of their representative performance model. In this paper, we are concerned with real-time estimation of a performance model for adaptive software systems that process multiple classes of transactional workload. Based on an open queueing network model and an Extended Kalman Filter (EKF), experiments in this work show that: (1) the model parameter estimates converge to the actual value very slowly when the variation in incoming workload is very low, (2) the estimates fail to converge quickly to the new value when there is a step-change caused by adaptive reconfiguration of the actual software parameters. We therefore propose a modified EKF design in which the measurement model is augmented with a set of constraints based on past measurement values. Experiments demonstrate the effectiveness of our approach that leads to significant improvement in convergence in the two cases.

In this paper, we propose a novel duty cycling algorithm for a large-scale dense wireless sensor networks. The proposed algorithm is based on a social behavior of nodes in the sense that individual node's sleep/wakeup decision is influenced by the state of its neighbors. We analyze the behavior of the proposed duty cycling algorithm using a stochastic spatial process. In particular, we consider a geometric form of neighborhood dependence and a reversible Markov chain, and apply this model to analyze the behavior of the duty cycling network. We then identify a set of parameters for the reversible spatial process model, and study the steady state of the network with respect to these parameters. We report that our algorithm is scalable to a large network, and can effectively control the active node density while achieving a small variance. We also report that the social behavior of nodes has interesting and non-obvious impacts on the performance of duty cycling. Finally, we present how to set the parameters of the algorithm to obtain a desirable duty cycling behavior.

Since many Internet applications employ a multitier architecture, in this article, we focus on the problem of analytically modeling the behavior of such applications. We present a model based on a network of queues where the queues represent different tiers of the application. Our model is sufficiently general to capture (i) the behavior of tiers with significantly different performance characteristics and (ii) application idiosyncrasies such as session-based workloads, tier replication, load imbalances across replicas, and caching at intermediate tiers. We validate our model using real multitier applications running on a Linux server cluster. Our experiments indicate that our model faithfully captures the performance of these applications for a number of workloads and configurations. Furthermore, our model successfully handles a comprehensive range of resource utilization---from 0 to near saturation for the CPU---for two separate tiers. For a variety of scenarios, including those with caching at one of the application tiers, the average response times predicted by our model were within the 95% confidence intervals of the observed average response times. Our experiments also demonstrate the utility of the model for dynamic capacity provisioning, performance prediction, bottleneck identification, and session policing. In one scenario, where the request arrival rate increased from less than 1500 to nearly 4200 requests/minute, a dynamic provisioning technique employing our model was able to maintain response time targets by increasing the capacity of two of the tiers by factors of 2 and 3.5, respectively.

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.

We introduce and evaluate a middleware clustering technology capable of allocating resources to web applications through dynamic application instance placement. We define application instance placement as the problem of placing application instances on a given set of server machines to adjust the amount of resources available to applications in response to varying resource demands of application clusters. The objective is to maximize the amount of demand that may be satisfied using a configured placement. To limit the disturbance to the system caused by starting and stopping application instances, the placement algorithm attempts to minimize the number of placement changes. It also strives to keep resource utilization balanced across all server machines. Two types of resources are managed, one load-dependent and one load-independent. When putting the chosen placement in effect our controller schedules placement changes in a manner that limits the disruption to the system.

Since many Internet applications employ a multi-tier architecture, in this paper, we focus on the problem of analytically modeling the behavior of such applications. We present a model based on a network of queues, where the queues represent different tiers of the application. Our model is sufficiently general to capture (i) the behavior of tiers with significantly different performance characteristics and (ii) application idiosyncrasies such as session-based workloads, concurrency limits, and caching at intermediate tiers. We validate our model using real multi-tier applications running on a Linux server cluster. Our experiments indicate that our model faithfully captures the performance of these applications for a number of workloads and configurations. For a variety of scenarios, including those with caching at one of the application tiers, the average response times predicted by our model were within the 95% confidence intervals of the observed average response times. Our experiments also demonstrate the utility of the model for dynamic capacity provisioning, performance prediction, bottleneck identification, and session policing. In one scenario, where the request arrival rate increased from less than 1500 to nearly 4200 requests/min, a dynamic provisioning technique employing our model was able to maintain response time targets by increasing the capacity of two of the application tiers by factors of 2 and 3.5, respectively.

We present an architecture and prototype implementation of a performance management system for cluster-based web services. The system supports multiple classes of web services traffic and allocates server resources dynamically so to maximize the expected value of a given cluster utility function in the face of fluctuating loads. The cluster utility is a function of the performance delivered to the various classes, and this leads to differentiated service. In this paper, we will use the average response time as the performance metric. The management system is transparent: it requires no changes in the client code, the server code, or the network interface between them. The system performs three performance management tasks: resource allocation, load balancing, and server overload protection. We use two nested levels of management. The inner level centers on queuing and scheduling of request messages. The outer level is a feedback control loop that periodically adjusts the scheduling weights and server allocations of the inner level. The feedback controller is based on an approximate first-principles model of the system, with parameters derived from continuous monitoring. We focus on SOAP-based web services. We report experimental results that show the dynamic behavior of the system.

In Web services environments, classes of service are offered at different performance levels. Requests belonging to various service classes are to be handled differently in order to yield their expected corresponding performance level. We investigate a mechanism that provides this service discrimination by deploying an optimized external scheduler, as opposed to common mechanisms for prioritization and internal server scheduling. A measure of Service Performance Level (SPL) that combines target and achieved performance values is introduced. Our approach is based on simple Weighted Round-Robin (WRR) scheduling with dynamically adjustable weights that are computed by solving an integer resource allocation problem. We present experimental results, contrasting a few scheduling policies. Further, we provide an analytic queueing network model to approximate the behavior of the system, and show its effectiveness.

We propose an architecture for hybrid services, i.e., services that span many network technologies, such as the public switched telephone network (PSTN), cellular networks, and networks based on IP. These services will play an important role in the future because they leverage on the existing infrastructures rather than requiring new and sophisticated mechanisms to be deployed. We explore a few issues related to hybrid services and propose a platform as well as a set of components to facilitate their creation and deployment. The existing infrastructure is only required to generate specific events when requests for hybrid services are detected. We present the design of a service layer, based on Java, that handles the treatment of these special requests. Our service layer is provided with a set of generic components realized according to the JavaBeans model. We illustrate the strength of our architecture by discussing two hybrid-service examples: a calendar service and a call forwarding service.

An emerging application of mobile computing and communication is the delivery of information related to the transportation system to drivers and travelers. Such real-time information would be very valuable in providing services such as pre-trip planning, route guidance, intermodal transportation, yellow pages, and ride matching and reservation. This so-called advanced traveler information system (ATIS) is an important subset of an intelligent transportation system (ITS). The authors are developing an ATIS operational field test called SWIFT (Seattle wide-area information for travelers) in the Seattle metropolitan area which uses technological advances in wireless communication, personal digital assistants (PDA), and traffic modeling and analysis. SWIFT uses an advanced 19 kbps FM subcarrier broadcast medium for the delivery of transportation information as well as personal paging information. Preliminary description of the logical and physical architecture of the SWIFT system along with communication loading analysis for this system, are presented.

The performance of voice and video services is evaluated for isochronous LANs or systems that have time division multiplexing (TDM) channels with fixed bandwidth for real-time traffic. The isochronous bandwidth resources are shared by voice and video traffic which have different bandwidth requirements. The blocking probabilities for voice and video arrivals are obtained analytically for the case where channels are allocated randomly without using a policy. Two policies for bandwidth allocation of voice and video traffics under various traffic load conditions are evaluated. The simulation results show that substantial improvements can be achieved if efficient allocation policies are used.

A protocol with strictly preemptive priorities that does not admit low-priority traffic if the load from high-priority traffic exceeds the capacity of the transmission channel in a MAN is presented. The protocol guarantees fairness for transmissions at the highest priority level. By introducing a general characterization of bandwidth allocation schemes for dual bus networks, existing priority mechanisms can be categorized according to the provided quality of service. The unique existence of a bandwidth allocation scheme for multiple priority traffic is shown with a full utilization of the channel capacity, with a fair distribution of bandwidth respective to traffic from a particular priority level, and with preemptive priorities. The performance of the presented protocol is compared to existing proposals for multiple priority mechanisms. It is shown that adopting the new protocol results in shorter access delays for high-priority transmissions. The protocol allows the stations of the network to react quickly to load changes. It is shown that the effectiveness of the priority scheme, compared to priority schemes using the bandwidth-balancing mechanism, is less dependent on increasing the transmission speed of the network.>

A media access protocol that achieves a fair distribution of the bandwidth in one round-trip delay is presented. The protocol is based on a unique solution to a fair and waste-free bandwidth allocation. This bandwidth allocation can be implemented in a distributed manner. A comparison of the new protocol with the DQDB (distributed queue dual bus) protocol shows considerable advantages regarding the transmission delay of messages and the time a station needs to obtain a fair portion of the available bandwidth. The advantages of the protocol become more apparent for large networks and high transmission speeds. In addition, the new protocol can perform nonuniform bandwidth allocations.>

A scheduling scheme that allows a number of customers to share a common resource in an efficient and fair way is presented. Each customer is allowed to use the resource for an amount of time that does not exceed a certain limit, the limit being a function of the waiting time elapsed between the time of its last request and the time of access to the resource. After expiration of the service time allocated to a customer, if more service is still needed, the customer has to re-enter the request queue and issue a new service request. The scheme combines the advantages of both processor-sharing and first-come, first-served disciplines in a dynamic way. The applicability and the advantages of the scheme in both open and closed system environments are discussed.>

The IEEE 802.6 standard for Metropolitan Area Networks does not provide multiple priority traffic for connectionless data services. A priority mechanism that was considered for the standard showed to be not effective. As of now, there exists no protocol for multiple access dual bus networks that is able to implement pre-emptive priorites and, at the same time, can satisfy minimal fairness requirements for transmissions at the highest priority level. In this study, a protocol with strictly pre-emptive priorities, i.e., a protocol that does not admit low priority traffic if the load from high priority traffic exceeds the capacity of the transmission channel, is presented. The protocol is derived from a unique bandwidth allocation scheme with a full utilization of the bus capacity, with a fair distribution of bandwidth respective to traffic from a particular priority level and with pre-emptive priorities. The performance of the presented protocol is compared to a priority mechanism that is based on the bandwidth balancing mechanism. It is shown that adopting the new protocol results in shorter access delays for high priority transmissions.

The performance implications of asynchronous disk interleaving are examined. In an asynchronous system, adjacent subblocks are placed independently of each other. Since each of the disks in such a system is treated independently while being accessed as a group, the access delay of a request for a data block in an n-disk system is the maximum of n access delays. Using approximate analysis, a simple expression for the expected value of such a maximum delay is obtained. The analysis approximation is verified by simulation using trace data; the relative error is found to be at most 6%.>

A queuing model of a parallel processor with an interconnection network incorporating a hierarchy of paths is developed and analyzed. The model captures the behavior of the processors, the interconnection network, and the storage modules. The network considered includes fast paths that operate in the absence of contention and alternate paths with contention resolution. The network overall performance is shown to be close to that of a contention-free network of fast paths. It is shown that, as the load varies, this hierarchical interconnection network is robust with respect to ideal networks with no delay. An analysis of the effects of hot spots shows that processor throughput is limited by storage rather than communications bandwidth and that an upper bound on the processor utilization is inversely proportional to the miss probability. The analysis suggests that a fetch-and-add network could be incorporated into a connection hierarchy whose average performance is close to that of a network with no combining, so this may be an effective way to handle hot spots without much penalty to overall system performance.>

A model of a packet radio network in which transmitters with range R are distributed according to a two-dimensional Poisson point process with density D is examined. To ensure network connectivity, it is shown that pi R/sup 2/D, the expected number of nearest neighbors of a transmitter, must grow logarithmically with the area of the network. For an infinite area there exists an infinite connected component with nonzero probability if pi R/sup 2/D>N/sub 0/, for some critical value N/sub 0/. It is shown that 2.195>

A class-constrained resource allocation problem is considered. In this problem, a set of M heterogeneous resources is to be allocated optimally among a set of L users belonging to K user classes. A set of class allocation constraints, which limit the number of users of a given class that could be allocated to a given resource, is imposed. An algorithm with worst case time complexity O(M (LM + M2 + LK)) is presented along with a proof of its correctness. This problem arises in many areas of resource management in computer systems, such as load balancing in distributed systems, transaction processing in distributed database systems, and session allocation in time-shared computer systems. We illustrate the behavior of this algorithm with an example where file servers are to be allocated to workstations of multiple classes.

A success (risk) measure of guaranteed availability is proposed. Using a genetic system model, the authors describe the measure and study the effects of the guaranteed level and the observation period on it. Furthermore, they introduce a numerical approach for continuous-time Markov chain models which allows component-level modeling, Coxian failure and repair distributions, time-dependent failure and repair rates and deferred repair and nondeferred repair strategies to be handled. An example of a fault-tolerant database computer system is considered and the measure of guaranteed availability is evaluated for various guaranteed levels and observation periods.>

An approximation technique, called scaling approximation, is introduced and applied to the analysis of homogeneous fork/join queuing systems consisting of K>or=2 servers. The development of the scaling approximation technique is guided by both experimental and theoretical considerations. The approximation is based on the observation that there exist upper and lower bounds on the mean response time that grow at the same rate as a function of K. Simple, closed-form approximate expressions for the mean response time are derived and compared to simulation results. The relative error in the approximation is less than 5% for K>

A bulk arrival M/sup x//M/c queuing system is used to model a centralized parallel processing system with job splitting. In such a system, jobs wait in a central queue, which is accessible by all the processors, and are split into independent tasks that can be executed on separate processors. The job response-time consists of three components: queuing delay, service time, and synchronization delay. An expression for the mean job response-time is obtained for this centralized parallel-processing system. Centralized and distributed parallel-processing systems (with and without job-splitting) are considered and their performances compared. Furthermore, the effects of parallelism and overheads due to job-splitting are investigated.>

A centralized parallel processing system with job splitting is considered. In such a system, jobs wait in a central queue, which is accessible by all the processors, and are split into independent tasks that can be executed on separate processors. This parallel processing system is modeled as a bulk arrival MX/M/c queueing system where customers and bulks correspond to tasks and jobs, respectively. Such a system has been studied in [1, 3] and an expression for the mean response time of a random customer is obtained. However, since we are interested in the time that a job spends in the system, including synchronization delay, we must evaluate the bulk response time rather than simply the customer response time. The job response time is the sum of the job waiting time and the job service time. By analyzing the bulk queueing system we obtain an expression for the mean job waiting time. The mean job service time is given by a set of recurrence equations.

The performability of degradable heterogeneous computer systems containing k > 1 types of components is considered. Previous analyses of such systems have been numerical in nature and yielded algorithms with either exponential complexity in the number of system states n, or polynomial in n with approximate truncations of infinite series. In this paper, a closed form expression for the performability of degradable heterogeneous systems is derived. Furthermore, an algorithm with polynomial complexity, O(kn3), is presented and applied to study the performability of a multiprocessor computer system.

A distributed computer system that consists of a set of heterogeneous host computers connected in an arbitrary fashion by a communications network is considered. A general model is developed for such a distributed computer system, in which the host computers and the communications network are represented by product-form queuing networks. In this model, a job may be either processed at the host to which it arrives or transferred to another host. In the latter case, a transferred job incurs a communication delay in addition to the queuing delay at the host on which the job is processed. It is assumed that the decision of transferring a job does not depend on the system state, and hence is static in nature. Performance is optimized by determining the load on each host that minimizes the mean job response time. A nonlinear optimization problem is formulated, and the properties of the optimal solution in the special case where the communication delay does not depend on the source-destination pair is shown. Two efficient algorithms that determine the optimal load on each host computer are presented. The first algorithm, called the parametric-study algorithm , generates the optimal solution as a function of the communication time. This algorithm is suited for the study of the effect of the speed of the communications network on the optimal solution. The second algorithm is a single-point algorithm ; it yields the optimal solution for given system parameters. Queuing models of host computers, communications networks, and a numerical example are illustrated.

A widely used error recovery technique in database systems is the rollback and recovery technique.Former models of rollback and recovery assumed Poisson failures and fixed (or exponential) checkpointing intervals.Extending these models, we consider general failure distributions.We also allow checkpointing intervals to depend on the reprocessing time and the failure distribution.Furthermore, failures may occur during checkpointing and error recovery.After deriving a general expression for system availability, we find that system availability resulting from the well-known equidistant checkpointing strategy depends only on the mean of the failure distribution.We then introduce a failure-dependent reprocessing-independent checkpointing strategy called equicost strategy.For Weibull failure distributions, which are good approximations of actual failure distributions of computer systems, we show that the equicost strategy achieves higher system availabilty than the equidistant strategy, which is known to be optimal under Poisson failures.

A widely used error recovery technique in database systems is the rollback and recovery technique. This technique saves periodically the state of the system and records all activities on a reliable log tape. The operation of saving the system state is called checkpointing. The elapsed time between two consecutive checkpointing operations is called checkpointing interval. When the system fails, the recovery process uses the log tape and the state saved at the most recent checkpoint to bring the system to the correct state that preceded the failure. This process is called error recovery and consists of loading the most recent state and then reprocessing all the activities, stored on the log tape, that took place since the most recent checkpoint and prior to failure.