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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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