ACM DL

ACM Transactions on

Modeling and Performance Evaluation of Computing Systems (TOMPECS)

Menu
Latest Articles

Scheduling Storms and Streams in the Cloud

Motivated by emerging big streaming data processing paradigms (e.g., Twitter Storm, Streaming MapReduce), we investigate the problem of scheduling graphs over a large cluster of servers. Each graph is a job, where nodes represent compute tasks and edges indicate data flows between these compute tasks. Jobs (graphs) arrive randomly over time and,... (more)

PEAS

Numerous auto-scaling strategies have been proposed in the past few years for improving various Quality of Service (QoS) indicators of cloud applications, for example, response time and throughput, by adapting the amount of resources assigned to the application to meet the workload demand. However, the evaluation of a proposed auto-scaler is... (more)

A Control-Theoretic Analysis of Low-Priority Congestion Control Reprioritization under AQM

Recently, a negative interplay has been shown to arise when scheduling/Active Queue Management (AQM) techniques and low-priority congestion control... (more)

NEWS

About TOMPECS

ACM Transactions on Modeling and Performance Evaluation of Computing Systems (ToMPECS) is a new ACM journal that publishes refereed articles on all aspects of the modeling, analysis, and performance evaluation of computing and communication systems.

The target areas for the application of these performance evaluation methodologies are broad, and include traditional areas such as computer networks, computer systems, storage systems, telecommunication networks, and Web-based systems, as well as new areas such as data centers, green computing/communications, energy grid networks, and on-line social networks.

Issues of the journal will be published on a quarterly basis, appearing both in print form and in the ACM Digital Library. The first issue will likely be released in late 2015 or early 2016.

READ MORE

New options for ACM authors to manage rights and permissions for their work

ACM introduces a new publishing license agreement, an updated copyright transfer agreement, and a new author-pays option which allows for perpetual open access through the ACM Digital Library. For more information, visit the ACM Author Rights webpage.

Forthcoming Articles
A Truthful Incentive Mechanism for Emergency Demand Response in Geo-distributed Colocation Data Centers

Data centers are key participants in demand response programs, including emergency demand response (EDR), where the grid coordinates large electricity consumers for demand reduction in emergency situations to prevent major economic losses. While existing literature concentrates on owner-operated data centers, this work studies EDR in geo-distributed multi-tenant colocation data centers where servers are owned and managed by individual tenants. EDR in colocation data centers is significantly more challenging, due to lack of incentives to reduce energy consumption by tenants who control their servers and are typically on fixed power contracts with the colocation operator. Consequently, to achieve demand reduction goals set by the EDR program, the operator has to rely on the highly expensive and/or environmentally-unfriendly on-site energy backup/generation. To reduce cost and environmental impact, an efficient incentive mechanism is therefore in need, motivating tenants voluntary energy reduction in case of EDR. This work proposes a novel incentive mechanism, Truth-DR, which leverages a reverse auction to provide monetary remuneration to tenants according to their agreed energy reduction. Truth-DR is computationally efficient, truthful, and achieves 2-approximation in colocation-wide social cost. Trace-driven simulations verify the efficacy of the proposed auction mechanism.

Fairness and Incentive Considerations in Energy Apportionment Policies

The energy consumption of a system is determined by the system component usage patterns and interactions between the coexisting entities and resources. Energy accounting plays an essential role to reveal the contribution of each entity to the total consumption and for energy management. Unfortunately, energy accounting inherits the cost allocation or apportionment problem of accounting in general, which does not have a general single best solution. In this paper we leverage cooperative game theory commonly used in cost allocation problems to study the energy apportionment problem, i.e., the problem of dividing the actual energy consumption of a system among the consuming entities (e.g., applications, processes or users of the system). We present a detailed categorisation and analysis of eight previously proposed energy apportionment policies from different fields in computer and communication systems and propose two novel apportionment policies based on cooperative game theory. Our comparative analysis in terms of information requirement, computational complexity and fairness (which relates to incentives) shows that there is a trade-off between fairness and the other evaluation criteria. We provide guidelines to select an energy apportionment policy depending on the characteristics of the system.

Analysis of an offloading scheme for data centers in the framework of fog computing

In the context of fog computing, we consider a simple case when data centers installed at the edge of the network are backed up by a central (bigger) data center. The system considered precisely comprises two data centers in parallel. We assume that if a request arrives at an overloaded data center, it is forwarded to the other data center with a given probability. Both data centers are assumed to have a large number of servers (rescaling of the system) and that traffic to one of them is causing saturation so that the other data center may help to cope with this saturation regime by reducing the rejection of requests. Our aim here is to qualitatively estimate the gain achieved by the collaboration of the two data centers. After proving some convergence results, related to the scaling limits of loss systems, for the process describing the number of free servers at both data centers, we show that the performance of the system can be expressed in terms of the invariant distribution of a random walk in the quarter plane. By using and developing existing results in the technical literature, explicit formulas for the blocking rates of such a system are derived.

On Fair Attribution of Costs Under Peak-based Pricing to Cloud Tenants

The costs incurred by cloud providers towards operating their data centers are often determined in large part by their peak demands. The pricing schemes currently used by cloud providers to recoup these costs from their tenants, however, do not distinguish tenants based on their contributions to the cloud's overall peak demand. Using the concrete example of peak-based pricing as employed by many electric utility companies, we show that this "gap" may lead to unfair attribution of costs to the tenants. Simple enhancements of existing cloud pricing (e.g., analogous to the coincident peak pricing (CPP) used by some electric utilities) do not adequately address these shortcomings and suffer from short-term unfairness and undesirable oscillatory price vs. demand relationship offered to tenants. To overcome these shortcomings, we define an alternative pricing scheme to more fairly distribute a cloud's costs among its tenants. Our approach to fair attribution of cloud's costs is inspired by the concept of Shapley values used to fairly divide revenue among participants of a financial coalition. We demonstrate the efficacy of our scheme under price-sensitive tenant demand response using a combination of (i) extensive empirical evaluation with recent data center workloads from commercial data centers operated by IBM, and (ii) analytical modeling through non-cooperative game theory for a special case of tenant demand model.

File dissemination in dynamic graphs: The case of independent and correlated links in series

In this paper we investigate the traversal time of a file across N communication links subject to stochastic changes in the sending rate of each link. Each link's sending rate is modeled by a finite-state Markov process. Two cases, one where links evolve independently of one another (N mutually independent Markov processes), and the second where their behaviors are dependent (these N Markov processes are not mutually independent) are considered. A particular instance where the above is encountered is in ad hoc delay/tolerant networks where edges are subject to intermittent unavailability.

List of Reviewers

Contention-Aware Workload Placement for In-Memory Databases in Cloud Environments

Big data processing is driven by new types of in-memory database systems. In this paper we apply performance modeling to efficiently optimize workload placement for such systems. In particular, we propose novel response time approximations for in-memory databases based on fork-join queuing models and contention probabilities to model variable threading levels and per-class memory occupation under analytical workloads. We combine these approximations with a non-linear optimization methodology that seeks for optimal load dispatching probabilities in order to minimize memory swapping and resource utilization. We compare our approach with state-of-the-art response time approximations using real data from an SAP HANA in-memory system and show that our models markedly improve accuracy over existing approaches, at similar computational costs.

Detecting Sponsored Recommendations

With a vast number of items, web-pages, and news to choose from, online services and the customers both benefit tremendously from personalized recommender systems. Such systems however provide great opportunities for targeted advertisements, by displaying ads alongside genuine recommendations. We consider a {\em biased} recommendation system where such ads are displayed without any tags (disguised as genuine recommendations), rendering them indistinguishable to a single user. We ask whether it is possible for a small subset of collaborating users to detect such a bias. We propose an algorithm that can detect such a bias through statistical analysis on the collaborating users' feedback. The algorithm requires only binary information indicating whether a user was satisfied with each of the recommended item or not. This makes the algorithm widely appealing to real world issues such as identification of search engine bias and pharmaceutical lobbying. We prove that the proposed algorithm detects the bias with high probability for a broad class of recommendation systems when sufficient number of users provide feedback on sufficient number of recommendations. We provide extensive simulations with real data sets and practical recommender systems, which confirm the trade offs in the theoretical guarantees.

False Positive Probability and Compression Optimization for Tree-structured Bloom filters

Bloom filters are frequently used to perform set queries that test the existence of items. However, Bloom filters face a dilemma: the transmission bandwidth and the accuracy cannot be optimized simultaneously. This dilemma is particularly severe for transmitting Bloom filters to remote nodes when the network bandwidth is limited. We propose a novel Bloom filter called \textbf{BloomTree} that consists of a tree-structured organization of smaller Bloom filters, each one using a set of independent hash functions. BloomTree spreads items across levels that are compressed to reduce the transmission bandwidth need. We investigate in detail under which conditions BloomTree performs better than the compressed Bloom filter and the standard Bloom filter. Finally, we use the intersection of BloomTrees to predict the set intersection, decreasing the false positive probabilities by several orders of magnitudes compared to both the compressed Bloom filter and the standard Bloom filter.

All ACM Journals | See Full Journal Index