INFOCOM 2015 Papers

Rapid disaster relief is important to save human lives and reduce property loss. With the wide use of smartphones and their ubiquitous easy access to the Internet, sharing and uploading images to the cloud via smartphones offer a nontrivial opportunity to provide information of disaster zones. However, due to limited available bandwidth and energy, smartphone-based crowdsourcing fails to support the real-time data analytics. The key to efficiently and timely share and analyze the images is to determine the value/worth of the images based on their significance and redundancy, and only upload those valuable and unique images. In this paper, we propose a near-realtime and cost-efficient scheme, called SmartEye, in the cloud-assisted disaster environment. The idea behind SmartEye is to implement QoS-aware in-network deduplication over DiffServ in the software-defined networks (SDN). Due to the ease of use, simplicity and scalability, DiffServ supports the in-network deduplication to meet the needs of differentiated QoS. SmartEye aggregates the flows with similar features via a semantic hashing, and provides communication services for the aggregated, not a single, flow. To achieve these goals, we leverage two main optimization schemes, including semantic hashing and space-efficient filters. Efficient image sharing is helpful to disaster detection and scene recognition. To demonstrate the feasibility of SmartEye, we conduct two real-world case studies in which the loss in Typhoon Haiyan (2013) and Hurricane Sandy (2012) can be identified in a timely fashion by analyzing massive data consisting of more than 22 million images using our SmartEye system. Extensive experimental results illustrate that SmartEye is efficient and effective to achieve real-time analytics in disasters.

For today's computer users, the mouse plays such an important role that it dominates the interaction interface in personal computer for nearly half a century since it was invented. However, the mouse is gradually unfit for the demand of modern 3D display techniques, e.g. 3D-projection or -screen, for the reason that the relevant interactions are confined in a surface. Although some new methods such as computer vision based techniques attempt to bridge the human-computer barrier, they suffer from many limitations such as ambiguity in multitargets and dependence on light. This paper presents a battery-free device called Tagball for 3D human-computer interaction via RFID tags. Tagball devises a control ball, on which N passive tags are attached, for users to generate two basic kinds of interactive commands: translation and rotation. Instead of locating N tags independently, we model the ball as a whole in a more cooperative way under the circumstance that their geometric relationships are known in advance. In addition, we consider the phase values measured by M RF antennas for these N tags as observations of the ball state. Our key innovations are the studies on motion behaviors of a group of tags by using Extended Kalman Filter, and the implementation based on purely Commercial Off-The-Shelf (COTS) RFID products. The systematical evaluation shows that Tagball traces the ball translation to 1.5cm and identifies ball orientation to 1.8° in 3D space.

Node searching in delay tolerant networks (DTNs) is of great importance for different applications, in which a locator node finds a target node in person. In the previous distributed node searching method, a locator traces the target along its movement path from its most frequently visited location. For this purpose, nodes leave traces during their movements and also store their long-term movement patterns in their frequently visited locations (i.e., preferred locations). However, such tracing leads to a long delay and high overhead on the locator by longdistance moving. Our trace data study confirms these problems and provides foundation of our design of a new node searching method, called target-oriented method (TSearch). By leveraging social network properties, TSearch aims to enable a locator to directly move towards the target. Nodes create encounter records (ERs) indicating the locations and times of their encounters and make the ERs easily accessible by locators through message exchanges or a hierarchical structure. In node searching, a locator follows the target's latest ER, the latest ERs of its friends (i.e., frequently meeting nodes), and its preferred locations in order. Extensive trace-driven and real-world experiments show that TSearch achieves significantly higher success rate and lower delay in node searching compared with previous methods.

Network inference is an effective mechanism to infer end-to-end flow rates and has enabled a variety of applications (e.g., network surveillance and diagnosis). The paper is focused on the opposite side of network inference, i.e., how to make inference inaccurate, which we call network anti-inference. As most research efforts have been focused on developing efficient inference methods, design of anti-inference is largely overlooked. Anti-inference scenarios can rise when network inference is not desirable, such as in clandestine communication and military applications. Our objective is to explore network dynamics to provide anti-inference. In particular, we consider two proactive strategies that cause network dynamics: transmitting deception traffic and changing routing to mislead the inference. We build an analytical framework to quantify the induced inference errors of the proactive strategies that maintain limited costs. We find via analysis and simulations that for deception traffic, a simple random transmission strategy can achieve inference errors on the same order of the best coordinated transmission strategy; while changing routing can cause inference errors of higher order than any deception traffic strategy. Our results not only reveal the fundamental perspective on proactive strategies, but also offer the guidance into practical design of anti-inference.

While most of existing efforts for dynamic spectrum access have focused on spectrum sensing of a narrowband band in a given region, this paper takes a holistic perspective to determine the usage profile of wide spectrum bands over a large geographic region. Specifically, a mobile crowdsensing approach is taken to develop a spectrum-profiling framework, which leverages the wisdom of many mobile devices to accomplish large-scale sensing tasks. A key step for spectrum profiling via mobile crowdsensing is to strategically assign sensing tasks to mobile users, so as to maximize the utility of the sensing data acquired. We cast this problem as a joint sensing task and subband allocation problem for utility maximization, capturing the location-specific characteristics of spectrum sensing. Since the problem is NP-hard, we design approximation algorithms. First, we design a greedy approximation algorithm as a baseline. Our analysis shows that the proposed greedy algorithm achieves an approximation ratio of 1/6, i.e., at least 1/6 of the utility obtained by the optimal allocation. Next, we design a Linear Program (LP) rounding based approximation algorithm, aiming to achieve a better approximation ratio than the greedy algorithm. We show that the propopsed LP-rounding algorithm attains an approximation ratio of 1/2 (1 - 1/e) for the general case, and further it achieves 1 - 1/e for a special case of the problem, which is the best possible approximation ratio. We also present the complexity analysis of the two proposed algorithms. We perform numerical experiments to evaluate the average performance of the the proposed algorithms.

Reducing the in-order delivery, or playback, delay of reliable transport layer protocols over error prone networks can significantly improve application layer performance. This is especially true for applications that have time sensitive constraints such as streaming services. We explore the benefits of a coded generalization of selective repeat ARQ for minimizing the in-order delivery delay. An analysis of the delay's first two moments is provided so that we can determine when and how much redundancy should be added to meet a user's requirements. Numerical results help show the gains over selective repeat ARQ, as well as the trade-offs between meeting the user's delay constraints and the costs inflicted on the achievable rate. Finally, the analysis is compared with experimental results to help illustrate how our work can be used to help inform system decisions.

Multi-packet reception (MPR) technology provides a means of boosting wireless network capacity without requiring additional spectrum. It has received widespread attention over the past two decades from both industry and academic researchers. Despite the huge promise and considerable attention, provable good algorithms for maximizing network capacity in MPR-capable wireless networks are missing in the state of the art. One major technical obstacle is due to the complicated non-binary nature of the link independence; something which appears intractable with existing graph-theoretic methods. In this paper, we present practical polynomial-time approximation algorithms for variants of capacity optimization problems in MPR-capable wireless networks which achieve constant approximation bounds for the first time ever. In addition, polynomial-time approximation schemes are developed for those variants in wireless networks with constant-bounded MPR capabilities.

Segment Routing is a proposed IETF protocol to improve traffic engineering and online route selection in IP networks. The key idea in segment routing is to break up the routing path into segments in order to enable better network utilization. Segment routing also enables finer control of the routing paths and can be used to route traffic through middle boxes. This paper considers the problem of determining the optimal parameters for segment routing in the offline and online cases. We develop a traffic matrix oblivious algorithm for robust segment routing in the offline case and a competitive algorithm for online segment routing. We also show that both these algorithms work well in practice.

This paper demystifies the adoption and cascading process of OSN-based applications that grow via user invitations. We analyze a detailed large-scale dataset of a popular Facebook gifting application, iHeart, that contains more than 2 billion entries of user activities generated by 190 million users during a span of 64 weeks. We investigate: (1) how users invite their friends to an OSN-based application, (2) what factors drive the cascading process of application adoptions, and (3) what are the good predictors of the ultimate cascade sizes. We find that sending or receiving a large number of invitations does not necessarily help to recruit new users to iHeart. We also identify a set of distinctive features that are good predictors of the growth of the application adoptions in terms of final population size. Finally, based on the insights learned from our analyses, we propose a prediction model to infer whether a cascade of application adoption will continue to grow in the future based on observing the initial adoption process. Results show our proposed model can achieve high precision (over 80%) in iHeart as well as in another OSN-based gifting application, Hugged.

Aggregation of computed sets of results fundamentally underlies the distillation of information in many of today's big data applications. To this end there are many systems which have been introduced which allow users to obtain aggregate results by aggregating along communication structures such as trees, but they do not focus on optimizing performance by optimizing the underlying structure to perform the aggregation. We consider two cases of the problem - aggregation of (1) single blocks of data, and of (2) streaming input. For each case we determine which metric of “fast” completion is the most relevant and mathematically model resulting systems based on aggregation trees to optimize that metric. Our assumptions and model are laid out in depth. From our model we determine how to create a provably ideal aggregation tree (i.e., with optimal fanin) using only limited information about the aggregation function being applied. Experiments in the Amazon Elastic Compute Cloud (EC2) confirm the validatity of our models in practice.

Enterprise 802.11 Network (EWLAN) is an important infrastructure to the Mobile Internet, but its performance is being significantly impacted by the ever-increasing Rogue access points (RAPs). For example, in the university EWLAN we studied, the number of RAPs is more than seven times that of the enterprise APs. In this paper, we propose a generic methodology to measure RAP's carrier sense interference and hidden terminal interference, and it only uses readily available SNMP metrics, without any additional measurement hardware. Our results show that, on average, the carrier sense interference due to RAPs causes only 5% access delay increase at the MAC layer, because of careful engineering and software optimization. However, hidden terminal interference due to RAPs causes (a much more severe) up to 30% MAC layer loss rate increase on average, because no existing approach has explicitly dealt with the hidden terminal impact from rogue APs. Overall, the RAP interference would increase the IP layer delay at the WiFi hop by up to 50%.

This paper presents VINCE - a novel visible light sensing design for smartphone-based Near Field Communication (NFC) systems. VINCE encodes information as different brightness levels of smartphone screens, while receivers capture the light signal via light sensors. In contrast to RF technologies, the direction and distance of such a Visible Light Communication (VLC) link can be easily controlled, preserving communication privacy and security. As a result, VINCE can be used in a wide range of NFC applications such as contactless payments and device pairing. We experimentally profile the impact of screen brightness levels and refresh rates of smartphones, and then use the results to guide the design of light intensity encoding scheme of VINCE. We adopt several signal processing techniques and empirically derive a model to deal with the significant variation of received light intensity caused by noises and low screen refresh rates. To improve the communication reliability, VINCE adopts a feedback-based retransmission scheme, and dynamically adjusts the number of encoding brightness levels based on the current light channel condition. We also derive an analytical model that characterizes the relation among the distance, SNR (Signal to Noise Ratio), and BER (Bit Error Rate) of VINCE. Our design and theoretical model are validated via extensive evaluations using a hardware implementation of VINCE on Android smartphones and the Arduino platform.

The growing popularity of smartphones and continuous user demand for a rich web experience has resulted in an exponential surge in cellular bandwidth requirements. Cellular providers have struggled to keep pace with the new requirements while users often face a monetary cost associated with the data downloaded to their device. While many modern websites have adapted to the new mobile habitat, they often take shortcuts to transition from their desktop to mobile versions, many times carrying redundant content that is never utilized. Moreover, mobile users are effectively paying for certain undesirable content, such as advertisements, in the form of their bandwidth costs. In this paper, we study the composition and complexity of modern websites, from both a mobile and desktop perspective, to identify sources of wasted bandwidth. We developed a custom crawler-based framework to perform an in-depth analysis of the top 100,000 popular sites ranked by Alexa. Our results show that 23% or more of the content size on an average website is unnecessary, unused or redundant. Our results serve as a motivation for developing optimized websites and enhancing the web infrastructure to better suit the mobile environment with emphasis on reducing bandwidth costs, while also improving performance and efficiency.

This paper considers reliable communication in presence of Byzantine faulty nodes, using multiple node-disjoint routes. To tolerate f Byzantine faults, at least 2f + 1 node-disjoint paths are needed between a source and destination node pair. However, often the faulty nodes' misbehavior manifests itself as a "disagreement" between information provided by the faulty node and its neighbors. This disagreement can be captured in the form of a conflict graph. Even though the conflict graph does not always allow us to identify faulty nodes precisely, we show that it can still be used to reduce the number of paths necessary for reliable communication (to smaller than 2f+1). We consider two strategies for using the node-disjoint paths for reliable delivery of messages: replication and coding across different paths. For each strategy, we propose iPath, a scheme to identify the optimal set of paths that needs to be used to achieve reliable communication for a given conflict graph.

Mobile Cloud Computing (MCC) is of particular importance to address the contradiction between the increasing complexity of user applications and the limited lifespan of mobile device's battery, by offloading the computational workloads from local devices to the remote cloud. Current offloading schemes either require the programmer's annotations, which restricts its wide application; or transmits too much unnecessary data, resulting bandwidth and energy waste. In this paper, we propose a novel method-level offloading methodology to offload local computational workload with as least data transmission as possible. Our basic idea is to identify the contexts which are necessary to the method execution by parsing application binaries in advance and applying this parsing result to selectively migrate heap data while allowing successful method execution remotely. Our implementation of this design is built upon Dalvik Virtual Machine. Our experiments and evaluation against applications downloaded from Google Play show that our approach can save data transmission significantly comparing to existing schemes.

The rapid growth of wireless mobile users and applications has led to high demand of spectrum. Auction is a powerful tool to improve the utilization of spectrum resource, and many auction mechanisms have been proposed thus far. However, none of them has considered both the privacy of bidders and the revenue gain of the auctioneer together. In this paper, we study the design of privacy-preserving auction mechanisms. We first propose a differentially private auction mechanism which can achieve strategy-proofness and a near optimal expected revenue based on the concept of virtual valuation. Assuming the knowledge of the bidders' valuation distributions, the near optimal differentially private and strategy-proof auction mechanism uses the generalized Vickrey-Clarke-Groves auction payment scheme to achieve high revenue with a high probability. To tackle its high computational complexity, we also propose an approximate differentially PrivAte, Strategy-proof, and polynomially tractable Spectrum (PASS) auction mechanism that can achieve a suboptimal revenue. PASS uses a monotone allocation algorithm and the critical payment scheme to achieve strategy-proofness. We also evaluate PASS extensively via simulation, showing that it can generate more revenue than existing mechanisms in the spectrum auction markets.

Interference management is one of the most important issues in the heterogeneous cellular networks (HetNet) with macro and pico cells. The enhanced inter cell interference coordination (eICIC) has been proposed to protect downlink pico cell transmissions by mitigating interference from neighboring macro cells. The adaptive eICIC configuration problem is studied in this paper to adjust the parameters including the ratio of Almost Blank Subframes (ABS) and the bias of cell range expansion (RE). We formulate the problem as a general form consensus problem with regularization, and solve the problem by providing an efficient distributed optimization framework. Our algorithm is based on the alternating direction method of multipliers (ADMM) in which the solutions to local subproblems on each macro cell and pico cell are coordinated to find a solution to the global problem for the whole network. We also propose the dynamic programming based algorithms to solve the local subproblems on macro cell or pico cell. The simulation results demonstrate the efficiency of the proposed algorithm compared with existing approaches, and verify the convergence properties of the proposed algorithm.

Conflict graph has been widely used for wireless network optimization in dealing with the issues of channel assignment, spectrum allocation, links scheduling and etc. Despite its simplicity, the traditional conflict graph suffers from two drawbacks. On one hand, it is a rough representation of the interference condition, which is inaccurate and will cause suboptimal results for wireless network optimization. On the other hand, it only defines the interference between two entities, which neglects the accumulative effect of small amount interference. In this paper, we propose the model of quantized conflict graph (QCG) to tackle the above issues. The properties, usage and construction methods of QCG are explored. We show that in its matrix form, a QCG owns the properties of low-rank and high-similarity. These properties give birth to three complementary QCG estimation strategies, namely low-rank approximation approach, similarity based approach, and comprehensive approach, to construct the QCG efficiently and accurately from partial interference measurement results. We further explore the potential of QCG for wireless network optimization by applying QCG in minimizing the total network interference. Extensive experiments using real collected wireless network are conducted to evaluate the system performance, which confirm the efficiency of the proposed algorithms.

The CSMA/CA protocol is based on the “Interference as Noise” (IAN) paradigm i.e. it always gets rid of strong interference near a receiver to ensure quality of reception. However, it is well known from Multi-user Information Theory that treating Interference as Noise is not optimal. This paper proposes a class of protocols that employ the Successive Interference Cancellation (SIC) technique in a systematic fashion to move beyond always treating interference as noise. Such protocols allow one to pack more links than the classical CSMA. We describe the protocols along with their signaling mechanism to implement them in a distributed fashion. We then perform Monte Carlo simulations to evaluate the performance and show significant gains over the IAN based CSMA/CA protocol in large random networks.