INFOCOM 2015 Papers

This paper presents the first systematic investigation of the potential performance gains for crowdsourcing systems, deriving from available information at the requester about individual worker earnestness (reputation). In particular, we first formalize the optimal task assignment problem when workers' reputation estimates are available, as the maximization of a monotone (submodular) function subject to Matroid constraints. Then, being the optimal problem NP-hard, we propose a simple but efficient greedy heuristic task allocation algorithm. We also propose a simple “maximum a-posteriori“ decision rule. Finally, we test and compare different solutions, showing that system performance can greatly benefit from information about workers' reputation. Our main findings are that: i) even largely inaccurate estimates of workers' reputation can be effectively exploited in the task assignment to greatly improve system performance; ii) the performance of the maximum a-posteriori decision rule quickly degrades as worker reputation estimates become inaccurate; iii) when workers' reputation estimates are significantly inaccurate, the best performance can be obtained by combining our proposed task assignment algorithm with the LRA decision rule introduced in the literature.

This paper proposes a martingale extension of effective-capacity, a concept which has been instrumental in teletraffic theory to model the link-layer wireless channel and analyze QoS metrics. Together with a recently developed concept of an arrival-martingale, the proposed service-martingale concept enables the queueing analysis of a bursty source sharing a MAC channel. In particular, the paper derives the first rigorous and accurate stochastic delay bounds for a Markovian source sharing either an Aloha or CSMA/CA channel, and further considers two extended scenarios accounting for 1) in-source scheduling and 2) spatial multiplexing MIMO. By leveraging the powerful martingale methodology, the obtained bounds are remarkably tight and improve state-of-the-art bounds by several orders of magnitude. Moreover, the obtained bounds indicate that MIMO spatial multiplexing is subject to the fundamental power-of-two phenomena.

As a widely used programming model and implementation for processing large data sets, MapReduce performs poorly on heterogeneous clusters, which, unfortunately, are common in current computing environments. To deal with the problem, this paper: 1) analyzes the causes of performance degradation and identifies the key one as the large volume of inter-node data transfer resulted from even data distribution among nodes of different computing capabilities, and 2) proposes ActCap, a solution that uses a Markov chain based model to do node-capability-aware data placement for the continuously incoming data. ActCap has been incorporated into Hadoop and evaluated on a 24-node heterogeneous cluster by 13 benchmarks. The experimental results show that ActCap can reduce the percentage of inter-node data transfer from 32.9% to 7.7% and gain an average speedup of 49.8% when compared with Hadoop, and achieve an average speedup of 9.8% when compared with Tarazu, the latest related work.

We present an Internet measurement technique for finding machines that are hidden behind firewalls. That is, if a firewall prevents outside IP addresses from sending packets to an internal protected machine that is only accessible on the local network, our technique can still find the machine. We employ a novel TCP/IP side channel technique to achieve this. The technique uses side channels in “zombie” machines to learn information about the network from the perspective of a zombie. Unlike previous TCP/IP side channel techniques, our technique does not require a high packet rate and does not cause denial-of-service. We also make no assumptions about globally incrementing IPIDs, as do idle scans. This paper addresses two key questions about our technique: how many machines are there on the Internet that are hidden behind firewalls, and how common is ingress filtering that prevents our scan by not allowing spoofed IP packets into the network. We answer both of these questions, respectively, by finding 1,296 hidden machines and measuring that only 23.9% of our candidate zombie machines are on networks that perform ingress filtering.

Hybrid wireless networks are networks that are composed of both ad hoc transmissions and cellular transmissions. Many existing works have analyzed the capacity of hybrid wireless networks. By assuming the uniform traffic model that a source node would select a random node as the destination, the network capacity is a function of number of nodes and number of base stations. Nevertheless, the real network traffic pattern is related to the social behaviors of users. In this work, we study the capacity of hybrid wireless networks with the social traffic model under the L-maximum-hop routing policy. If two nodes are within L hops away, packets will be transmitted in the ad hoc mode; otherwise, packets are transmitted through the base stations. To our best knowledge, we are the first to study this problem and develop the capacity as a function of number of nodes, number of stations, traffic model parameters, and L.

People make decisions and express their opinions according to their communities. A natural idea for controlling the diffusion of a behavior is to find influential people, and employ them to spread a desired behavior. We investigate an influencing problem when individuals' behaviors are affected by their friends in an opinion formation process. Our goal is to design efficient algorithms for finding opinion leaders such that changing their opinions has a great impact on the overall external behaviors in the society. We study directed social networks and define a set of problems like maximizing the sum of individuals' behaviors or maximizing the number of individuals whose external behaviors are above a threshold. We discuss the complexity of the defined problems and design polynomial-time optimum algorithms for the non NP-hard variants of them. We also propose polynomial-time approximation algorithms with guaranteed performances and prove inapproximability results for the NP-hard variants of these problems. Furthermore, we run simulations on real-world social networks and show our proposed algorithm outperforms the classical algorithms such as degree-based algorithm, closeness-based algorithm, and pagerank-based algorithm.

A considerable amount of research effort has focused on developing metrics and approaches to assess network vulnerability. However, most of them neglect the network uncertainty arisen due to various reasons such as mobility and dynamics of the network, or noise introduced in data collection process. To this end, we introduce a framework to assess vulnerability of networks with uncertainty, modeling such networks as probabilistic graphs. We adopt expected pairwise connectivity (EPC) as a measure to quantify global connectivity and use it to formulate vulnerability assessment as a stochastic optimization problem. The objective is to identify a few number of critical nodes whose removal minimizes EPC in the residual network. While solutions for stochastic optimization problems are often limited to small networks, we present a practical solution that works for larger networks. The key advantages of our solution include 1) the application of a weighted averaging technique that avoids considering all, exponentially many, possible realizations of probabilistic graphs and 2) a Fully Polynomial Time Randomized Approximation Scheme (FPRAS) to efficiently estimate the EPC with any desired accuracy. Extensive experiments demonstrate significant improvement on performance of our solution over other heuristic approaches.

We present WiGest: a system that leverages changes in WiFi signal strength to sense in-air hand gestures around the user's mobile device. Compared to related work, WiGest is unique in using standard WiFi equipment, with no modifications, and no training for gesture recognition. The system identifies different signal change primitives, from which we construct mutually independent gesture families. These families can be mapped to distinguishable application actions. We address various challenges including cleaning the noisy signals, gesture type and attributes detection, reducing false positives due to interfering humans, and adapting to changing signal polarity. We implement a proof-of-concept prototype using off-the-shelf laptops and extensively evaluate the system in both an office environment and a typical apartment with standard WiFi access points. Our results show that WiGest detects the basic primitives with an accuracy of 87.5% using a single AP only, including through-the-wall non-line-of-sight scenarios. This accuracy increases to 96% using three overheard APs. In addition, when evaluating the system using a multi-media player application, we achieve a classification accuracy of 96%. This accuracy is robust to the presence of other interfering humans, highlighting WiGest's ability to enable future ubiquitous hands-free gesture-based interaction with mobile devices.

Optical data center networks (DCNs) are becoming increasingly attractive due to their technological strengths compared to traditional electrical networks. However, prior optical DCNs are either hard to scale, vulnerable to single point of failure, or provide limited network bisection bandwidth for many practical DCN workloads. To this end, we present WaveCube, a scalable, fault-tolerant, high-performance optical DCN architecture. To scale, WaveCube removes MEMS1, a potential bottleneck, from its design. Wave-Cube is fault-tolerant since it does not have single point of failure and there are multiple node-disjoint parallel paths between any pair of Top-of-Rack (ToR) switches. WaveCube delivers high performance by exploiting multi-pathing and dynamic link bandwidth along the path. Our extensive evaluation results show that WaveCube outperforms previous optical DCNs by up to 400% and delivers network bisection bandwidth that is 70%–85% of an ideal non-blocking network under both realistic and synthetic traffic patterns. WaveCube's performance degrades gracefully under failures — it drops 20% even with 20% links cut. WaveCube also holds promise in practice — its wiring complexity is orders of magnitude lower than Fattree, BCube and c-Through at large scale, and its power consumption is 35% of them.

Peering in the Internet interdomain network has long been considered a “black art”, understood in-depth only by a select few peering experts while the majority of the network operator community only scratches the surface employing conventional rules-of-thumb to form peering links through ad hoc personal interactions. Why is peering considered a black art? What are the main sources of complexity in identifying potential peers, negotiating a stable peering relationship, and utility optimization through peering? How do contemporary operational practices approach these problems? In this work we address these questions for Tier-2 Network Service Providers. We identify and explore three major sources of complexity in peering: (a) inability to predict traffic flows prior to link formation (b) inability to predict economic utility owing to a complex transit and peering pricing structure (c) computational infeasibility of identifying the optimal set of peers because of the network structure. We show that framing optimal peer selection as a formal optimization problem and solving it is rendered infeasible by the nature of these problems. Our results for traffic complexity show that 15% NSPs lose some fraction of customer traffic after peering. Additionally, our results for economic complexity show that 15% NSPs lose utility after peering, approximately, 50% NSPs end up with higher cumulative costs with peering than transit only, and only 10% NSPs get paid-peering customers.

Visible Light Communications (VLC) is emerging as an appealing technology to complement WiFi in indoor environments. Yet maintaining VLC performance under link dynamics remains a challenging problem. In this paper, we build a VLC software-radio testbed and examine VLC channel dynamics through comprehensive measurement. We find minor device movement or orientation change can cause the VLC link SNR to vary by tens of dB even within one packet duration, which renders existing WiFi rate adaptation protocols ineffective. We thus propose a new mechanism, DLit, that leverages two unique properties of VLC links (predictability and full-duplex) to realize fine-grained, in-frame rate adaptation. Our prototype implementation and experiments demonstrate that DLit achieves near-optimal performance for mobile VLC usage cases, and outperforms conventional packet-level adaptation schemes by multiple folds.

There is an increasing need for cloud service performance that can be tailored to customer requirements. In the context of jobs submitted to cloud computing clusters, a crucial requirement is the specification of job completion-times. A natural way to model this specification, is through client/job utility functions that are dependent on job completion-times. We present a method to allocate and schedule heterogeneous resources to jointly optimize the utilities of jobs in a cloud. Specifically: (i) we formulate a completion-time optimal resource allocation (CORA) problem to apportion cluster resources across the jobs that enforces max-min fairness among job utilities, and (ii) starting with an integer programming problem, we perform a series of steps to transform it into an equivalent linear programming problem, and (iii) we implement the proposed framework as a utility-aware resource scheduler in the widely used Hadoop data processing framework, and finally (iv) through extensive experiments with real-world datasets, we show that our prototype achieves significant performance improvement over existing resource-allocation policies.

Internet service providers increasingly deploy internal CDNs with the objective of reducing the traffic on their transit links and to improve their customers' quality of experience. Once ISP managed CDNs (nCDNs) become commonplace, ISPs would likely provide common interfaces to interconnect their nCDNs for mutual benefit, as they do with peering today. In this paper we consider the problem of using distributed algorithms for computing a content allocation for nCDNs. We show that if every ISP aims to minimize its cost and bilateral payments are not allowed then it may be impossible to compute a content allocation. For the case of bilateral payments we propose two distributed algorithms, the aggregate value compensation (AC) and the object value compensation (OC) algorithms, which differ in terms of the level of parallelism they allow and in terms of the amount of information exchanged between nCDNs. We prove that the algorithms converge, and we propose a scheme to ensure ex-post individual rationality. Simulations performed on a real AS-level network topology and synthetic topologies show that the algorithms have geometric rate of convergence, and scale well with the graphs' density and the nCDN capacity.

We address the problem of social network de-anonymization when relationships between people are described by scale-free graphs. In particular, we propose a rigorous, asymptotic mathematical analysis of the network de-anonymization problem while capturing the impact of power-law node degree distribution, which is a fundamental and quite ubiquitous feature of many complex systems such as social networks. By applying bootstrap percolation and a novel graph slicing technique, we prove that large inhomogeneities in the node degree lead to a dramatic reduction of the initial set of nodes that must be known a priori (the seeds) in order to successfully identify all other users. We characterize the size of this set when seeds are selected using different criteria, and we show that their number can be as small as n% for any small ε > 0. Our results are validated through simulation experiments on real social network graphs.

Multi-user MIMO (MU-MIMO) has recently been specified in wireless standards, e.g., LTE-Advance and 802.11ac, to allow an access point (AP) to transmit multiple unicast streams simultaneously to different clients. These protocols however have no specific mechanism for multicasting. Existing systems hence simply allow a single multicast transmission, as a result underutilizing the AP's multiple antennas. Even worse, in most of systems, multicast is by default sent at the base rate, wasting a considerable link margin available for delivering extra information. To address this inefficiency, we present the design and implementation of HybridCast, a MU-MIMO system that enables joint unicast and multicast. HybridCast efficiently leverages the unused MIMO capability and link margin to send unicast streams concurrently with a multicast session, while ensuring not to harm the achievable rate of multicasting. We evaluate the performance of HybridCast via both testbed experiments and simulations. The results show that HybridCast always outperforms single multicast transmission. The average throughput gain for 4-antenna AP scenarios is 6.22× and 1.54× when multicast is sent at the base rate and the best rate of the bottleneck receiver, respectively.

In dense wireless deployments at homes, such as apartment buildings, neighboring home WLANs share the same unlicensed spectrum by deploying consumer-grade access points in their individual homes. In such environments, WiFi networks can suffer from intermittent performance issues such as wireless packet losses, interference from WiFi and non-WiFi sources due to the rapid growth and increasing diversity of devices that share the spectrum. In this paper, we propose a vendor-neutral cloud-based centralized framework called COAP to configure, coordinate and manage individual home APs using an open API implemented by these commodity APs. The framework, implemented using OpenFlow extensions, allows the APs to share various types of information with a centralized controller - interference and traffic phenomenon and various flow contexts, and in turn receive instructions - configuration parameters (e.g., channel) and transmission parameters (through coarse-grained schedules and throttling parameters). This paper describes the framework and associated techniques, applications to motivate its potential benefits, such as, upto 47% reduction in channel congestion and our experiences from having deployed it in actual home environments.

Virtualizing Hadoop clusters provides many benefits, including rapid deployment, on-demand elasticity and secure multi-tenancy. However, a simple migration of Hadoop to a virtualized environment does not fully exploit these benefits. The dual role of a Hadoop worker, acting as both a compute node and a data node, makes it difficult to achieve efficient IO processing, maintain data locality, and exploit resource elasticity in the cloud. We find that decoupling per-node storage from its computation opens up opportunities for IO acceleration, locality improvement, and on-the-fly cluster resizing. To fully exploit these opportunities, we propose StoreApp, a shared storage appliance for virtual Hadoop worker nodes co-located on the same physical host. To completely separate storage from computation and prioritize IO processing, StoreApp pro-actively pushes intermediate data generated by map tasks to the storage node. StoreApp also implements late-binding task creation to take the advantage of prefetched data due to mis-aligned records. Experimental results show that StoreApp achieves up to 61% performance improvement compared to stock Hadoop and resizes the cluster to the (near) optimal degree of parallelism.

This paper considers a wireless link with randomly arriving data that is queued and served over a time-varying channel. It is known that any algorithm that comes within ε of the minimum average power required for queue stability must incur average queue size at least Ω(log(l/ε)). However, the optimal convergence time is unknown, and prior algorithms give convergence time bounds of O(l/ε2). This paper shows that it is possible to achieve the optimal O(log(l/ε)) average queue size tradeoff with an improved convergence time of O(log(l/ε)/ε). Further, this is shown to be within a logarithmic factor of the best possible convergence time. The method uses the simple drift-plus-penalty technique with an improved convergence time analysis.

Software-defined networking (SDN) is a novel paradigm that outsources the control of programmable network switches to a set of software controllers. The most fundamental task of these controllers is the correct implementation of the network policy, i.e., the intended network behavior. In essence, such a policy specifies the rules by which packets must be forwarded across the network. This paper studies a distributed SDN control plane that enables concurrent and robust policy implementation. We introduce a formal model describing the interaction between the data plane and a distributed control plane (consisting of a collection of fault-prone controllers). Then we formulate the problem of consistent composition of concurrent network policy updates (termed the CPC Problem). To anticipate scenarios in which some conflicting policy updates must be rejected, we enable the composition via a natural transactional interface with all-or-nothing semantics. We show that the ability of an f-resilient distributed control plane to process concurrent policy updates depends on the tag complexity, i.e., the number of policy labels (a.k.a. tags) available to the controllers, and describe a CPC protocol with optimal tag complexity f + 2.