SIGMETRICS '16: Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science

Full Citation in the ACM Digital Library

SESSION: Contributed Session 1: Queueing Theory

Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems

We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate λ N, with 0<λ<1, and are immediately dispatched to one of several queues associated ...

Optimal Heavy-Traffic Queue Length Scaling in an Incompletely Saturated Switch

We consider an input queued switch operating under the MaxWeight scheduling algorithm. This system is interesting to study because it is a model for Internet routers and data center networks. Recently, it was shown that the MaxWeight algorithm has ...

A Necessary and Sufficient Condition for Throughput Scalability of Fork and Join Networks with Blocking

Due to emerging applications such as cloud computing and big data analytics, modern information processing systems are growing increasingly large and complex. A critical issue concerns the throughput performance as the system grows in size. This paper ...

SESSION: Contributed Session 2: Graph Theory

Generalized Threshold-Based Epidemics in Random Graphs: The Power of Extreme Values

Bootstrap percolation is a well-known activation process in a graph, in which a node becomes active when it has at least r active neighbors. Such process, originally studied on regular structures, has been recently investigated also in the context of ...

Reverse Ranking by Graph Structure: Model and Scalable Algorithms

Distances in a network capture relations between nodes and are the basis of centrality, similarity, and influence measures. Often, however, the relevance of a node u to a node v is more precisely measured not by the magnitude of the distance, but by the ...

Improved Achievability and Converse Bounds for Erdos-Renyi Graph Matching

We consider the problem of perfectly recovering the vertex correspondence between two correlated Erdos-Renyi (ER) graphs. For a pair of correlated graphs on the same vertex set, the correspondence between the vertices can be obscured by randomly ...

SESSION: Keynote Lecture: Mor Harchol-Balter (CMU)

A Better Model for Task Assignment in Server Farms: How Replication can Help

An age-old problem in the design of server farms is the choice of the task assignment policy. This is the algorithm that determines how to assign incoming jobs to servers. Popular policies include Round-Robin assignment, Join-the-Shortest-Queue, Join-...

SESSION: Contributed Session 3: Data Centers and CDNs

Costly Circuits, Submodular Schedules and Approximate Carathéodory Theorems

Hybrid switching -- in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch -- is a promising alternative to interconnect servers in today's large scale data centers. Circuit switches ...

Reducing Latency Through Page-aware Management of Web Objects by Content Delivery Networks

As popular web sites turn to content delivery networks (CDNs) for full-site delivery, there is an opportunity to improve the end-user experience by optimizing the delivery of entire web pages, rather than just individual objects. In particular, this ...

SESSION: Contributed Session 4: Caching

Optimizing TTL Caches under Heavy-Tailed Demands

In this paper we analyze the hit performance of cache systems that receive file requests with general arrival distributions and different popularities. We consider timer-based (TTL) policies, with differentiated timers over which we optimize. The ...

Adaptive Caching Networks with Optimality Guarantees

We study the problem of optimal content placement over a network of caches, a problem naturally arising in several networking applications, including ICNs, CDNs, and P2P systems. Given a demand of content request rates and paths followed, we wish to ...

SESSION: Keynote Lecture: Philippe Jacquet (Bell Labs)

Breathing Mankind Thoughts

Mankind has never been connected as it is now and as it will be tomorrow. Nowadays thanks to the rise of social networks such as Tweeter and Facebook, we can follow in real time the thought of millions of people. In fact we can almost feel the thoughts ...

SESSION: Contributed Session 5: Classification and Data Structure

Unsupervised Clustering Under Temporal Feature Volatility in Network Stack Fingerprinting

Maintaining and updating signature databases is a tedious task that normally requires a large amount of user effort. The problem becomes harder when features can be distorted by observation noise, which we call volatility. To address this issue, we ...

Noisy Bloom Filters for Multi-Set Membership Testing

This paper is on designing a compact data structure for multi-set membership testing allowing fast set querying. Multi-set membership testing is a fundamental operation for computing systems and networking applications. Most existing schemes for multi-...

SESSION: Contributed Session 6: Graphs and Social Networks

Rumor Source Obfuscation on Irregular Trees

Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. Messages in these applications propagate anonymously (without authorship metadata) over a network that is ...

Inference in OSNs via Lightweight Partial Crawls

Are Online Social Network (OSN) A users more likely to form friendships with those with similar attributes? Do users at an OSN B score content more favorably than OSN C users? Such questions frequently arise in the context of Social Network Analysis (...

Social Clicks: What and Who Gets Read on Twitter?

Online news domains increasingly rely on social media to drive traffic to their websites. Yet we know surprisingly little about how a social media conversation mentioning an online article actually generates clicks. Sharing behaviors, in contrast, have ...

SESSION: Contributed Session 7: Learning and Optimization

Using Predictions in Online Optimization: Looking Forward with an Eye on the Past

We consider online convex optimization (OCO) problems with switching costs and noisy predictions. While the design of online algorithms for OCO problems has received considerable attention, the design of algorithms in the context of noisy predictions is ...

Collaborative Filtering with Low Regret

There is much empirical evidence that item-item collaborative filtering works well in practice. Motivated to understand this, we provide a framework to design and analyze various recommendation algorithms. The setup amounts to online binary matrix ...

Achieving Low-Delay and Fast-Convergence in Stochastic Network Optimization: A Nesterovian Approach

Due to the rapid growth of mobile data demands, there have been significant interests in stochastic resource control and optimization for wireless networks. Although significant advances have been made in stochastic network optimization theory, to date, ...

SESSION: Contributed Session 8: Network Economics

On the Viability of a Cloud Virtual Service Provider

Cloud service providers (CSPs) often face highly dynamic user demands for their resources, which can make it difficult for them to maintain consistent quality-of-service. Some CSPs try to stabilize user demands by offering sustained-use discounts to ...

The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms and Fundamental Limits

We study the value of data privacy in a game-theoretic model of trading private data, where a data collector purchases private data from strategic data subjects (individuals) through an incentive mechanism. The private data of each individual represents ...

SESSION: Contributed Session 9: Networking

Instability in Distributed Mobility Management: Revisiting Configuration Management in 3G/4G Mobile Networks

Mobility support is critical to offering seamless data service to mobile devices in 3G/4G cellular networks. To accommodate policy requests by users and carriers, micro-mobility management scheme among cells (i.e., handoff) is designated to be ...

Transiently Secure Network Updates

Computer networks have become a critical infrastructure. Especially in shared environments such as datacenters it is important that a correct, consistent and secure network operation is guaranteed at any time, even during routing policy updates. In ...

SESSION: Contributed Session 10: Theoretical Tools for Performance Analysis

On the Approximation Error of Mean-Field Models

Mean-field models have been used to study large-scale and complex stochastic systems, such as large-scale data centers and dense wireless networks, using simple deterministic models (dynamical systems). This paper analyzes the approximation error of ...

On the Duration and Intensity of Competitions in Nonlinear Pólya Urn Processes with Fitness

Cumulative advantage (CA) refers to the notion that accumulated resources foster the accumulation of further resources in competitions, a phenomenon that has been empirically observed in various contexts. The oldest and arguably simplest mathematical ...

Asymptotics of Insensitive Load Balancing and Blocking Phases

Load balancing with various types of load information has become a key component of modern communication and information systems. In many systems, characterizing precisely the blocking probability allows to establish a performance trade-off between ...

SESSION: Contributed Session 11: Memory Systems

Understanding Latency Variation in Modern DRAM Chips: Experimental Characterization, Analysis, and Optimization

Long DRAM latency is a critical performance bottleneck in current systems. DRAM access latency is defined by three fundamental operations that take place within the DRAM cell array: (i) activation of a memory row, which opens the row to perform accesses;...

Hash, Don't Cache (the Page Table)

Radix page tables as implemented in the x86-64 architecture incur a penalty of four memory references for address translation upon each TLB miss. These 4 references become 24 in virtualized setups, accounting for 5%--90% of the runtime and thus ...

Exploiting Core Criticality for Enhanced GPU Performance

Modern memory access schedulers employed in GPUs typically optimize for memory throughput. They implicitly assume that all requests from different cores are equally important. However, we show that during the execution of a subset of CUDA applications, ...

SESSION: Extended Abstracts

A Service System with Randomly Behaving On-demand Agents

We consider a service system where agents (or, servers) are invited on-demand. Customers arrive as a Poisson process and join a customer queue. Customer service times are i.i.d. exponential. Agents' behavior is random in two respects. First, they can be ...

An Analysis of Load Imbalance in Scale-out Data Serving

Despite the natural parallelism across lookups, performance of distributed key-value stores is often limited due to load imbalance induced by heavy skew in the popularity distribution of the dataset. To avoid violating service level objectives expressed ...

Analyzing the Power Consumption of the Mobile Page Load

Automated Test Location Selection For Cellular Network Upgrades

Cellular networks are constantly evolving due to frequent changes in radio access and end user equipment technologies, applications, and traffic. Network upgrades should be performed with extreme caution since millions of users heavily depend on the ...

CAR: A Compression-Aware Refresh Approach to Improve Memory Performance and Energy Efficiency

DRAM memory is suffering increasingly aggravating refresh penalty, which no longer causes trivial performance degradation and power consumption. As memory capacity increases, refresh penalty has become increasingly worse as more rows have to be ...

Contrasting Effects of Replication in Parallel Systems: From Overload to Underload and Back

Task replication has recently been advocated as a practical solution to reduce latencies in parallel systems. In addition to several convincing empirical studies, analytical results have been provided, yet under some strong assumptions such as ...

Explicit Back-off Rates for Achieving Target Throughputs in CSMA/CA Networks

CSMA/CA networks have often been analyzed using a stylized model that is fully characterized by a vector of back-off rates and a conflict graph. We present an explicit formula for the unique vector of back-off rate needed to achieve any achievable ...

Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing

In this work, we study a challenging research problem that arises in minimizing the cost of storing customer data online for reliable accesses in a cloud. It is how to near-perfectly balance the remaining capacities of all disks across the cloud system ...

Joint Data Purchasing and Data Placement in a Geo-Distributed Data Market

This paper studies design challenges faced by a geo-distributed cloud data market: which data to purchase (data purchasing) and where to place/replicate the data (data placement). We show that the joint problem of data purchasing and data placement ...

Majority Rule Based Opinion Dynamics with Biased and Stubborn Agents

In this paper, we investigate the impact of majority-rule based random interactions among agents in a large social network on the diffusion of opinions in the network. Opinion of each agent is assumed to be a binary variable taking values in the set {0, ...

Mean Field Equilibria of Pricing Games in Internet Marketplaces

We model an Internet marketplace using a set of servers that choose prices for performing jobs. Each server has a queue of unfinished jobs, and is penalized for delay by the market maker via a holding cost. A server completes jobs with a low or high "...

Modeling SMR Drive Performance

Multipath Streaming: Fundamental Limits and Efficient Algorithms

We investigate streaming over multiple links. We provide lower bounds on the starvation probability of any policy and simple, order-optimal policies with matching and tractable upper bounds.

Network Calculus Analysis of a Feedback System with Random Service

Feedback mechanisms are integral components of network protocols and traffic control algorithms. Their performance evaluation is hard due to intricate time correlations introduced by feedback. Network calculus has been successfully applied for the ...

QoE Analysis of a Large-Scale Live Video Streaming Event

Streaming video has received a lot of attention from industry and academia. In this work, we study the characteristics and challenges associated with large-scale live video delivery. Using logs from a commercial Content Delivery Network (CDN), we study ...

Safe Randomized Load-Balanced Switching by Diffusing Extra Loads

Load-balanced switch architectures are known to be scalable in both size and speed, which is of interest due to the continued exponential growth in Internet traffic. However, the main drawback of load-balanced switches is that packets can depart out of ...

Searching For A Single Community in a Graph

In standard graph clustering/community detection, one is interested in partitioning the graph into more densely connected subsets of nodes. In contrast, the search problem of this paper aims to only find the nodes in a single such community, the target, ...

Shoot for the Moon and You Will Never Miss: Characterizing and Detecting Aimbots in Online Games

Spatial Multi-LRU Caching for Wireless Networks with Coverage Overlaps

This article introduces a novel family of decentralised caching policies for wireless networks, referred to as spatial multi-LRU. Based on these, cache inventories are updated in a way that provides content diversity to users that are covered by, and ...

SSD Failures in Datacenters: What, When and Why?

Despite the growing popularity of Solid State Disks (SSDs) in the datacenter, little is known about their reliability characteristics in the field. The little knowledge is mainly vendor supplied, which cannot really help understand how SSD failures can ...

The Power of d Choices for Redundancy

An increasingly prevalent technique for improving response time in queueing systems is the use of redundancy. In a system with redundant requests, each job that arrives to the system is copied and dispatched to multiple servers. As soon as the first ...

Time-Based Bandwidth Allocation for Heterogeneous Storage

Providing fairness and system efficiency are important, often conflicting, requirements when allocating shared resources. In a hybrid storage system the problem is complicated by the high variability in request service times, caused by speed differences ...

Towards Multi-Resource Fair Allocation with Placement Constraints

Multi-resource fair schedulers have been widely implemented in compute clusters to provide service isolation guarantees. Existing multi-resource sharing policies, notably Dominant Resource Fairness (DRF) and its variants, are designed for unconstrained ...

Trading Discount for Reputation?: On the Design and Analysis of E-Commerce Discount Mechanisms

We develop an optimization framework to trade short-term profits for reputation (i.e., reducing ramp-up time). We apply the stochastic bandits framework to design an online discounting mechanism which infers the optimal discount from a seller's ...