INFOCOM 2015 Papers

In search of scalable solutions, CDNs are exploring P2P support. However, the benefits of peer assistance can be limited by various obstacle factors such as ISP friendliness - requiring peers to be within the same ISP, bitrate stratification - the need to match peers with others needing similar bitrate, and partial participation - some peers choosing not to redistribute content. This work relates potential gains from peer assistance to the average number of users in a swarm, its capacity, and empirically studies the effects of these obstacle factors at scale, using a month-long trace of over 2 million users in London accessing BBC shows online. Results indicate that even when P2P swarms are localised within ISPs, up to 88% of traffic can be saved. Surprisingly, bitrate stratification results in 2 large sub-swarms and does not significantly affect savings. However, partial participation, and the need for a minimum swarm size do affect gains. We investigate improvements to gain from increasing content availability through two well-studied techniques: content bundling-combining multiple items to increase availability, and historical caching of previously watched items. Bundling proves ineffective as increased server traffic from larger bundles outweighs benefits of availability, but simple caching can considerably boost traffic gains from peer assistance.

Contradicting the widely believed assumption of link independence, recently the phenomenon of reception correlation among nearby receivers has been revealed and exploited for varieties of protocols [3], [8], [17], [21], [23], [24]. However, despite the diversified correlation-aware designs proposed up to date, they commonly suffer from a shortcoming where link correlation is inaccurately measured, which leads them to sub-optimal performance. In this work we propose a general framework for accurate capturing of link correlation, enabling better utilization of the phenomenon for protocols lying on top of it. Our framework uses SINR (Signal to Interference plus Noise Ratio) to detect correlations, followed by modeling the correlations for in-network use. We show that our design is light-weight, both computation and storage-wise. We apply our model to opportunistic routing and network coding on a physical 802.15.4 test-bed for energy savings of 25% and 15%.

Image search has been widely deployed in many applications for the rich content that images contain. In the era of big data, image search engines have to be hosted in data centers. As a viable solution, outsourcing the image search to public clouds is an economic choice for many small organizations. However, as many images contain sensitive information, e.g., healthcare information and personal faces/locations, directly outsourcing image search services to public clouds obviously raises privacy concerns. With this observation, several attempts are made towards secure image search over encrypted dataset, but they are limited by either search accuracy or search efficiency. In this paper, we propose a lightweight secure image search scheme over encrypted data, namely SEISA. Compared with image search techniques over plaintexts, SEISA only increases about 9% search cost and sacrifices about 3% on search accuracy. SEISA also efficiently supports search access control by employing a novel polynomial based design, which enables data owners to define who can search a specific image. Furthermore, we design a secure k-means outsourcing algorithm that significantly saves the data owner's cost. To demonstrate SEISA's performance, we implement a prototype of SEISA on Amazon EC2 cloud over a dataset with 10 million images.

RFID has been widely adopted as an effective method for anti-counterfeiting. Legacy systems based on security protocol are either too heavy to be affordable by passive tags or suffering from various protocol-layer attacks, e.g. reverse engineering, cloning, side-channel. In this work, we present a novel anti-counterfeiting system, TagPrint, using COTS RFID tags and readers. Achieving a low-cost and offline genuineness validation utilizing passive tags has been a daunting task. Our system achieves these three goals by leveraging a few of federated tags' fingerprints and geometric relationships. In TagPrint, we exploit a new kind of fingerprint, called phase fingerprint, extracted from the phase value of the backscattered signal, provided by the COTS RFID readers. To further solve the separation challenge, we devise a geometric solution to validate the genuineness. We have implemented a prototype of TagPrint using COTS RFID devices. The system has been tested extensively over 6,000 tags. The results show that our new fingerprint exhibits a good fitness of uniform distribution and the system achieves a surprising Equal Error Rate of 0.1% for anti-counterfeiting.

Searchable encryption is an important and challenging issue. It allows people to search on encrypted data. This is a very useful function when more and more people choose to host their data in the cloud and the cloud server is not fully trustable. Existing solutions for searchable encryption are only limited to some simple functions of search, such as boolean search or similarity search. In this paper, we propose a scheme for Generalized Pattern-matching String-search on Encrypted data (GPSE) in cloud systems. GPSE allows users to specify their search queries by using generalized wildcard-based string patterns (such as SQL-like patterns). It gives users great expressive power in specifying highly targeted search queries. In the framework of GPSE, we particularly implemented two most commonly used pattern matching search functions on encrypted data, the substring matching and the longest-prefix-first matching. We also prove that GPSE is secure under the known-plaintext model. Experiments over real data sets show that GPSE achieves high search accuracy.

Although geometric routing is proposed as a memory-efficient alternative to traditional lookup-based routing and forwarding algorithms, it still lacks: (i) adequate mechanisms to trade stretch against load balancing, and (ii) robustness to cope with network topology change. The main contribution of this paper involves the proposal of a family of routing schemes, called Forest Routing. These are based on the principles of geometric routing, adding flexibility in its load balancing characteristics. This is achieved by using an aggregation of greedy embeddings along with a configurable distance function. Incorporating link load information in the forwarding layer enables load balancing behavior while still attaining low path stretch. In addition, the proposed schemes are validated regarding their resilience towards network failures.

We analyze synchronization issues arising between two stochastic point processes, one of which models data churn at an information source and the other periodic downloads from its replica (e.g., search engine, web cache, distributed database). Due to lazy (pull-based) synchronization, the replica experiences recurrent staleness, which translates into some form of penalty stemming from its reduced ability to perform consistent computation and/or provide up-to-date responses to customer requests. We model this system under non-Poisson update/refresh processes and obtain sample-path averages of various metrics of staleness cost, generalizing previous results and exposing novel problems in this field.

Digital signature has been widely employed in wireless mobile networks to ensure the authenticity of messages and identity of nodes. A paramount concern in signature verification is reducing the verification delay to ensure the network QoS. To address this issue, researchers have proposed the batch cryptography technology. However, most of the existing works focus on designing batch verification algorithms without sufficiently considering the impact of invalid signatures. The performance of batch verification could dramatically drop, if there are verification failures caused by invalid signatures. In this paper, we propose a Game-theory-based Batch Identification Model (GBIM) for wireless mobile networks, enabling nodes to find invalid signatures with the optimal delay under heterogeneous and dynamic attack scenarios. Specifically, we design an incomplete information game model between a verifier and its attackers, and prove the existence of Nash Equilibrium, to select the dominant algorithm for identifying invalid signatures. Moreover, we propose an auto-match protocol to optimize the identification algorithm selection, when the attack strategies can be estimated based on history information. Comprehensive simulation results demonstrate that GBIM can identify invalid signatures more efficiently than existing algorithms.

Crowdsourcing of jobs to online freelance markets is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs (e.g., image classification) with no specific quality requirement since freelancers are functionally identical. For skilled jobs (e.g., software development) with specific requirements, however, this does not ensure the maximum number of job requests is satisfied. In this work we determine the capacity of freelance markets, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom of choice for customers and freelancers, we propose simple schemes compatible with the operation of current crowd-sourcing platforms that approximately achieve capacity. Further, for settings where job requests exceed capacity, we propose an optimal and fair scheme for declining jobs without wait.

This paper presents an analytically tractable stochastic geometry model for urban wireless networks, where the locations of the nodes and the shadowing are highly correlated and different path loss functions can be applied to line-of-sight (LOS) and non-line-of-sight (NLOS) links. Using a distance-based LOS path loss model and a blockage (shadowing)-based NLOS path loss model, we are able to derive the distribution of the interference observed at a typical location and the joint distribution at different locations. When applied to cellular networks, this model leads to tractable expressions for the coverage probability (SINR distribution). We show that this model captures important features of urban wireless networks, which cannot be analyzed using existing models. The numerical results also suggest that even in the presence of significant penetration loss, ignoring the NLOS interference can lead to erroneous estimations on coverage. They also suggest that allowing users to be associated with NLOS BSs may provide a non-trivial gain on coverage.

Current data mining techniques used to create failure predictors for online services require massive amounts of data to build, train, and test the predictors. These operations are tedious, time consuming, and are not done in real-time. Also, the accuracy of the resulting predictor is highly compromised by changes that affect the environment and working conditions of the predictor. We propose a new approach to creating a dynamic failure predictor for online services in real-time and keeping its accuracy high during the services run-time changes. We use synthetic transactions during the run-time lifecycle to generate current data about the service. This data is used in its ephemeral state to build, train, test, and maintain an up-to-date failure predictor. We implemented the proposed approach in a large-scale online ad service that processes billions of requests each month in six data centers distributed in three continents. We show that the proposed predictor is able to maintain failure prediction accuracy as high as 86% during online service changes, whereas the accuracy of the state-of-the-art predictors may drop to less than 10%.

A software defined network (SDN) separates the centralized control plane from the distributed data plane. This approach simplifies control logic at the cost of a heavy burden on the software-based controller and potential long reaction time to data plane events. One solution to this problem is to distribute control logic to multiple controllers spread across the network. Such a solution, however, requires additional mechanisms to enforce correctness properties (e.g., consistency) among the controllers and it still does not fully eliminate latency, as controller decisions happen in software. In this paper, we explore a novel approach to this problem: configuring the rules used by the data plane switches to allow these switches to effectively handle latency-sensitive network management tasks without the direct intervention of the control plane. We are not suggesting to add distributed control logic capability to the switches, we are instead exploring the feasibility of encoding such logic using the standard forwarding rules already available to these devices. To this end, we formally model a network of SDN switches, and then prove using tools from computability theory that such systems are capable of simulating polynomial space Turing Machines, indicating a surprising amount of computational power.

Network Function Virtualization (NFV) is a new networking paradigm where network functions are executed on commodity servers located in small cloud nodes distributed across the network, and where software defined mechanisms are used to control the network flows. This paradigm is a major turning point in the evolution of networking, as it introduces high expectations for enhanced economical network services, as well as major technical challenges. In this paper, we address one of the main technical challenges in this domain: the actual placement of the virtual functions within the physical network. This placement has a critical impact on the performance of the network, as well as on its reliability and operation cost. We perform a thorough study of the NFV location problem, show that it introduces a new type of optimization problems, and provide near optimal approximation algorithms guaranteeing a placement with theoretically proven performance. The performance of the solution is evaluated with respect to two measures: the distance cost between the clients and the virtual functions by which they are served, as well as the setup costs of these functions. We provide bi-criteria solutions reaching constant approximation factors with respect to the overall performance, and adhering to the capacity constraints of the networking infrastructure by a constant factor as well. Finally, using extensive simulations, we show that the proposed algorithms perform well in many realistic scenarios.

Heterogeneous cellular networks use small base stations, such as femtocells and WiFi APs, to offload traffic from macrocells. While network operators wish to globally balance the traffic, users may selfishly select the nearest base stations and make some base stations overcrowded. In this paper, we propose to use an auction-based algorithm - Femto-Matching, to achieve both load balancing among base stations and fairness among users. Femto-Matching optimally solves the global proportional fairness problem in polynomial time by transforming it into an equivalent matching problem. Furthermore, it can efficiently utilize the capacity of randomly deployed small cells. Our trace-driven simulations show Femto-Matching can reduce the load of macrocells by more than 30% compared to non-cooperative game based strategies.

Estimating the number of RFID tags is a fundamental operation in RFID systems and has recently attracted wide attentions. Despite the subtleties in their designs, previous methods estimate the tag cardinality from the slot measurements, which distinguish idle and busy slots and based on that derive the cardinality following some probability models. In order to fundamentally improve the counting efficiency, in this paper we introduce PLACE, a physical layer based cardinality estimator. We show that it is possible to extract more information and infer integer states from the same slots in RFID communications. We propose a joint estimator that optimally combines multiple sub-estimators, each of which independently counts the number of tags with different inferred PHY states. Extensive experiments based on the GNURadio/USRP platform and the large-scale simulations demonstrate that PLACE achieves approximately 3~4× performance improvement over state-of-the-art cardinality estimation approaches.

Due to considerable increases in user mobility and frame length through aggregation, the wireless channel remains no longer time-invariant during the (aggregated) frame transmission time. However, the existing IEEE 802.11 standards still define the channel estimation to be performed only once at the preamble for coherent OFDM receivers, and the same channel information to be used throughout the entire (aggregated) frame processing. Our experimental results reveal that this baseline channel estimation approach seriously deteriorates the WiFi performance, especially for pedestrian mobile users and the recently adopted frame aggregation scheme. In this paper, we propose Channel-Aware Symbol Error Reduction (ChASER), a new practical channel estimation and tracking scheme for WiFi receivers. ChASER utilizes the re-encoding and re-modulation of the received data symbol to keep up with the wireless channel dynamics at the granularity of OFDM symbols. Our extensive, trace-driven link-level simulation shows significant performance gains over a wide range of channel conditions based on the real wireless channel traces collected by the off-the-shelf WiFi device. In addition, the feasibility of its low-complexity and standard compliance is demonstrated by Microsoft's Software Radio (Sora) prototype implementation and experimentation. To our knowledge, ChASER is the first IEEE 802.11n-compatible channel tracking algorithm since other approaches addressing the time-varying channel conditions over a single (aggregated) frame duration require costly modifications of the IEEE 802.11n standard.

Barrier coverage in visual camera sensor networks (visual barrier coverage) has important real-world applications like battlefield surveillance, environmental monitoring, and protection of government property. Cost-effective deployment, a fundamental issue of visual barrier coverage, considers how to deploy the fewest camera sensors along the barrier to detect intruders (e.g., capture faces) with desirable performance. Existing visual barrier coverage approaches like full-view coverage require numerous camera sensors for capturing intruders' faces deterministically for any trajectory and facing angle. However, intruders' trajectories and facing angles are bounded and deterministic intruder detection requires many camera sensors for rare intrusion cases. Certain practical applications can tolerate limited intrusion mis-detection given budget limitations. This paper proposes local face-view barrier coverage, a novel concept that achieves statistical barrier coverage in camera sensor networks leveraging intruders' trajectory lengths ℓ along the barrier and head rotation angles δ. Using (ℓ, δ) and other parameters, we derive a rigorous probability bound for intruder detection for local face-view barrier coverage via a feasible deployment pattern. Our detection probability bound and deployment pattern can guide practical camera sensor network deployments with camera sensor budgets. Extensive evaluations show that local face-view barrier coverage requires up to 50% fewer camera sensors than full-view barrier coverage.

We establish a network formation game for the Internet's Autonomous System (AS) interconnection topology. The game includes different types of players, accounting for the heterogeneity of ASs in the Internet. We incorporate reliability considerations in the player's utility function, and analyze static properties of the game as well as its dynamic evolution. We provide dynamic analysis of topological quantities, and explain the prevalence of some “network motifs” in the Internet graph. We assess our predictions with real-world data.

This paper focuses on regular expression matching over compressed traffic. The need for such matching arises from two independent trends. First, the volume and share of compressed HTTP traffic is constantly increasing. Second, due to their superior expressibility, current Deep Packet Inspection engines use regular expressions more and more frequently. We present an algorithmic framework to accelerate such matching, taking advantage of information gathered when the traffic was initially compressed. HTTP compression is typically performed through the GZIP protocol, which uses back-references to repeated strings. Our algorithm is based on calculating (for every byte) the minimum number of (previous) bytes that can be part of a future regular expression matching. When inspecting a back-reference, only these bytes should be taken into account, thus enabling one to skip repeated strings almost entirely without missing a match. We show that our generic framework works with either NFA-based or DFA-based implementations and gains performance boosts of more than 70%. Moreover, it can be readily adapted to most existing regular expression matching algorithms, which usually are based either on NFA, DFA or combinations of the two. Finally, we discuss other applications in which calculating the number of relevant bytes becomes handy, even when the traffic is not compressed.