INFOCOM 2017 Papers

We propose AccountTrade, a set of accountable protocols, for big data trading among dishonest consumers. To secure the big data trading environment, our protocols achieve book-keeping ability and accountability against dishonest consumers who may misbehave throughout the dataset transactions. Specifically, we study the responsibilities of the consumers in the dataset trading and design AccountTrade to achieve accountability against the dishonest consumers who may try to deviate from their responsibilities. Specifically, we propose uniqueness index, a new rigorous measurement of the data uniqueness, as well as several accountable trading protocols to enable data brokers to blame the dishonest consumer when misbehavior is detected. We formally define, prove, and evaluate the accountability of our protocols by an automatic verification tool as well as extensive evaluation in real-world datasets. Our evaluation shows that AccountTrade incurs negligible constant storage overhead per file (<;10KB), and it is able to handle 8-1000 concurrent data uploading per server depending on the data types.

Previous resource provisioning strategies in cloud datacenters allocate physical resources to virtual machines (VMs) based on the predicted resource utilization pattern of VMs. The pattern for VMs of a job is usually derived from historical utilizations of multiple VMs of the job. We observed that these utilization curves are usually misaligned in time, which would lead to resource over-prediction and hence over-provisioning. Since this resource utilization misalignment problem has not been revealed and studied before, in this paper, we study the VM resource utilization from public datacenter traces to verify the existence of the utilization misalignments. Then, to reduce resource over-provisioning, we propose three VM resource utilization pattern refinement algorithms to improve the original generated pattern by lowering the cap of the pattern, reducing cap provision duration and varying the minimum value of the pattern. These algorithms can be used in any resource provisioning strategy that considers predicted resource utilizations of VMs of a job. We then adopt these refinement algorithms in an initial VM allocation mechanism and test them in trace-driven experiments and real-world cluster experiments. The experimental results show that each improved mechanism can increase resource efficiency up to 74%, and reduce the number of PMs needed to satisfy tenant requests up to 47% while conforming the SLO requirement.

Personalized medicine performs diagnoses and treatments according to the DNA information of the patients. The new paradigm will change the health care model in the future. A doctor will perform the DNA sequence matching instead of the regular clinical laboratory tests to diagnose and medicate the diseases. Additionally, with the help of the affordable personal genomics services such as 23andMe, personalized medicine will be applied to a great population. Cloud computing will be the perfect computing model as the volume of the DNA data and the computation over it are often immense. However, due to the sensitivity, the DNA data should be encrypted before being outsourced into the cloud. In this paper, we start from a practical system model of the personalize medicine and present a solution for the secure DNA sequence matching problem in cloud computing. Comparing with the existing solutions, our scheme protects the DNA data privacy as well as the search pattern to provide a better privacy guarantee. We have proved that our scheme is secure under the well-defined cryptographic assumption, i.e., the sub-group decision assumption over a bilinear group. Unlike the existing interactive schemes, our scheme requires only one round of communication, which is critical in practical application scenarios. We also carry out a simulation study using the real-world DNA data to evaluate the performance of our scheme. The simulation results show that the computation overhead for real world problems is practical, and the communication cost is small. Furthermore, our scheme is not limited to the genome matching problem but it applies to general privacy preserving pattern matching problems which is widely used in real world.

For mobile apps, user-perceived delays are critical for user satisfaction. According to our measurement, long delays are commonly caused by network and storage I/O operations while short delays are mainly caused by UI rendering. Short delays are not uncommon, which account for 55.3% in our measurement cases. Previous app performance studies have largely focused on I/O operations but the understanding of UI rendering impact is limited. In this work, we propose DRAW, a system that performs two UI rendering analyses to help app developers pinpoint rendering problems and resolve short delays. The first analysis outlines the wasted rendering time on invisible or covered UI components, namely the overdraw problem. The second analysis is to identify the responsible UI components and rendering operations that cause overall low rendering efficiency. We implement DRAW on Android and apply it to study 1,158 real-world Android apps. Results show that DRAW is helpful as it can pinpoint the responsible UI components and specific rendering operations. Four concrete case studies of real-world apps are further presented to show how DRAW can help developers improve the UI rendering performance of their apps.

We introduce a new class of forward error correction (FEC) codes for VoIP communications which support different recovery delay depending on the channel conditions. Specifically, our proposed class of Dual-Delay (DD) codes can recover from challenging long bursts of losses with close to theoretical minimum delay so as to meet playback deadlines for recovered packets. They further improve conversational interactivity by achieving lower recovery delay during periods of random isolated losses. These DD codes are shown to achieve lower residual loss rates when compared to existing codes over a wide range of parameters of the Gilbert-Elliott channel. Experiments over real world packet traces further show performance gains of DD codes in terms of perceptually motivated ITU-T G.107 E-model.

We consider the Threshold Activation Problem (TAP): given social network G and positive threshold T, find a minimum-size seed set A that can trigger expected activation of at least T. We introduce the first scalable, parallelizable algorithm with performance guarantee for TAP suitable for datasets with millions of nodes and edges; we exploit the bicriteria nature of solutions to TAP to allow the user to control the running time versus accuracy of our algorithm through a parameter α ϵ (0, 1): given η > 0, with probability 1 - η our algorithm returns a solution A with expected activation greater than T - 2αT, and the size of the solution A is within factor 1-h 4α/T + log(T) of the optimal size. The algorithm runs in time O (α-2log (n/η) (n + m)|A|), where n, m, refer to the number of nodes, edges in the network. The performance guarantee holds for the general triggering model of internal influence and also incorporates external influence, provided a certain condition is met on the cost-effectivity of seed selection.

Network function virtualization enables flexible implementation of network functions, or middleboxes, as virtual machines running on standard servers. However, the flexibility also creates a challenge for efficiently placing such middleboxes, due to the availability of multiple hosting servers, capability of middleboxes to change traffic volumes, and dependency between middleboxes. In this paper, we address the optimal placement challenge of NFV middleboxes, and propose solutions for middleboxes of different traffic changing effects and with different dependency relations. First, we formulate the Traffic Aware Placement of Interdependent Middleboxes problem as a graph optimization problem. When the flow path is predetermined, we design optimal algorithms to place a non-ordered or totally-ordered middlebox set, and propose an efficient heuristic for the general scenario of a partially-ordered middlebox set after proving its NP-hardness. When the flow path is not predetermined, we show that the problem is NP-hard even for a non-ordered middlebox set, and propose a traffic and space aware routing heuristic. We have evaluated the proposed algorithms using large scale simulations and prototype experiments, and present extensive evaluation results to demonstrate the effectiveness of our design.

Beaconing is a fundamental networking service where each node broadcasts a packet to all its neighbors locally. Unfortunately, the problem Minimum Latency Beaconing Schedule (MLBS) in duty-cycled scenarios is not well studied. Existing works always have rigid assumption that each node is only active once per working cycle. Aiming at making the work more practical and general, MLBS problem in duty-cycled network where each node is allowed to active multiple times in each working cycle (MLBSDCA for short) is investigated in this paper. Firstly, a modified first-fit coloring based algorithm is proposed for MLBSDCA under protocol interference model. After that, a (ρ + 1)2*|W|-approximation algorithm is proposed to further reduce the beaconing latency, where ρ denotes the interference radius, and |W| is the maximum number of active time slots per working cycle. When ρ and |W| is equal to 1, the approximation ratio is only 4, which is better than the one (i.e., 10) in existing works. Furthermore, two approximation algorithms for MLBSDCA under physical interference model are also investigated. The theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in term of latency.

We present Stork - an extension of the EPC C1G2 protocol allowing streaming of data to multiple Computational Radio Frequency IDentification tags (CRFIDs) simultaneously at up to 20 times faster than the prior state of the art. Stork introduces downstream attributes never before seen in (C)RFIDs: (i) fast feedback for CRFID downstream verification based on the internal EPC C1G2 memory check command - which we analytically and experimentally show to be the best possible downstream verification process based on EPC C1G2; (ii) ability to perform multi-CRFID transfer - which in our experiments speeds up downstream by more than two times compared to sequential transmission; and (iii) the use of compressed data streams - which improves firmware reprogramming times by up to 10% at large reader-to-CRFID distances.

A cloud computing cluster equipped with a deadline-aware job scheduler faces fairness and efficiency challenges when greedy users falsely advertise the urgency of their jobs. Penalizing such untruthfulness without demotivating users from using the cloud service calls for advanced mechanism design techniques that work together with deadline-aware job scheduling. We propose a Bayesian incentive compatible pricing mechanism based on matching by replica-surrogate valuation functions. User valuations can be discovered by the mechanism, even when the users themselves do not fully understand their own valuations. Furthermore, users who are charged a Bayesian incentive compatible price have no reason to lie about the urgency of their jobs. The proposed mechanism achieves multiple desired truthful properties such as Bayesian incentive compatibility and ex-post individual rationality. We implement the proposed pricing mechanism. Through experiments in a Hadoop cluster with real-world datasets, we show that our prototype is capable of suppressing untruthful behavior from users.

A low-latency and reliable message switching network is critical for constructing high-speed datacenter networks. In this paper, we present the design, implementation, and evaluation of a novel Location basEd Source Switching (LESS) for datacenter networks. LESS enables lightweight source switching through a location-based addressing scheme. Each switch and host can independently derive a source route to reach a destination without requiring the full knowledge of the network topology. We demonstrate that using location-based source routes as forwarding labels allows LESS to eliminate the need for routing tables and integrate with minimum required functionality for packet forwarding. Moreover, we propose a fast rerouting solution to address the issue of fault tolerance in source routing. Each switch can locally derive an alternative source route during a failure. The paper evaluates the performance of LESS. Our evaluation results suggest that LESS improves the performance of datacenter networks in terms of latency, throughput, and reliability.

Large organizations often have users in multiple sites which are connected over the Internet. Since resources are limited, communication between these sites needs to be carefully orchestrated for the most benefit to the organization. We present a Mission-optimized Overlay Network (MON), a hybrid overlay network architecture for maximizing utility to the organization. We combine an offline and an online system to solve non-concave utility maximization problems. The offline tier, the Predictive Flow Optimizer (PFO), creates plans for routing traffic using a model of network conditions. The online tier, MONtra, is aware of the precise local network conditions and is able to react quickly to problems within the network. Either tier alone is insufficient. The PFO may take too long to react to network changes. MONtra only has local information and cannot optimize non-concave mission utilities. However, by combining the two systems, MON is robust and achieves near-optimal utility under a wide range of network conditions. While best-effort overlay networks are well studied, our work is the first to design overlays that are optimized for mission utility.

Real-time driving behavior monitoring is a corner stone to improve driving safety. Most of the existing studies on driving behavior monitoring using smartphones only provide detection results after an abnormal driving behavior is finished, not sufficient for driver alert and avoiding car accidents. In this paper, we leverage existing audio devices on smartphones to realize early recognition of inattentive driving events including Fetching Forward, Picking up Drops, Turning Back and Eating or Drinking. Through empirical studies of driving traces collected in real driving environments, we find that each type of inattentive driving event exhibits unique patterns on Doppler profiles of audio signals. This enables us to develop an Early Recognition system, ER, which can recognize inattentive driving events at an early stage and alert drivers timely. ER employs machine learning methods to first generate binary classifiers for every pair of inattentive driving events, and then develops a modified vote mechanism to form a multi-classifier for all inattentive driving events along with other driving behaviors. It next turns the multi-classifier into a gradient model forest to achieve early recognition of inattentive driving. Through extensive experiments with 8 volunteers driving for about half a year, ER can achieve an average total accuracy of 94.80% for inattentive driving recognition and recognize over 80% inattentive driving events before the event is 50% finished.

Multicast is a major solution in supporting the explosive growth of the wireless video traffic demand. Also, power saving is a key technology to extend battery life of mobile devices. To meet both purposes, IEEE 802.11 wireless local area network (WLAN) supports power save mode (PSM) for station (STA) while receiving multicast packets. According to recent studies, off-the-shelf chipsets configured to use PSM show un-desired functions, thus resulting in many multicast packet losses. From our extensive measurement, we also verify degradation of multicast performance with widely-used off-the-shelf chipsets using PSM, and present previously-unknown undesired functions. Without modification of the chipsets, STA in PSM cannot enjoy reliable multicast service. Given this, we develop a practical and readily-applicable AP-side solution, called ACT-AP, which avoids multicast packet losses by preventing STA from operating in PSM. Our prototype implementation with off-the-shelf chipsets demonstrates that ACT-AP improves packet delivery ratio by up to 216% with little additional protocol overhead. To our best knowledge, ACT-AP is the first practical effort to support multicast to real devices with undesired functions in PSM.

Delay tolerant networks (DTNs) are widely adopted to many network applications, such as disaster recovery and battlefield communications. Such critical network scenarios call for an outright prevention mechanism against contact-based attacks, e.g., blackmailing a legitimate user to compromise sensitive information at a contact. To the best of our knowledge, there is no work on secure routing protocol against contact-based attacks in DTNs. Therefore, in this paper, we first formulate the problem of contact avoidance routing, in which the node holding a message tries to avoid having a contact with an adversary. By applying the phase-type distribution, we build the secure opportunistic path model, which integrates the delivery probability within the deadline and the safety of opportunistic paths. Then, we propose a contact avoidance routing (CAR) protocol to securely deliver a message to its destination against the contact-based compromise attack. In addition, we further propose an adaptive CAR (A-CAR) to accommodate complicated network scenarios, where the capabilities of adversaries are parameterized. The extensive simulations using real traces as well as random graphs demonstrate that the proposed CAR and A-CAR protocols achieve their design goals.

Nowadays, there is a fast-paced shift from legacy telecommunication systems to novel Software Defined Network (SDN) architectures that can support on-the-fly network reconfiguration, therefore, empowering advanced traffic engineering mechanisms. Despite this momentum, migration to SDN cannot be realized at once especially in high-end cost networks of Internet Service Providers (ISPs). It is expected that ISPs will gradually upgrade their networks to SDN over a period that spans several years. In this paper, we study the SDN upgrading problem in an ISP network: which nodes to upgrade and when. We consider a general model that captures different migration costs and network topologies, and two plausible ISP objectives; first, the maximization of the traffic that traverses at least one SDN node, and second, the maximization of the number of dynamically selectable routing paths enabled by SDN nodes. We leverage the theory of submodular and supermodular functions to devise algorithms with provable approximation ratios for each objective. Using real-world network topologies and traffic matrices, we evaluate the performance of our algorithms and show up to 54% gains over state-of-the-art methods. Moreover, we describe the interplay between the two objectives; maximizing one may cause a factor of 2 loss to the other.

This paper presents unsupervised algorithms to uncover polarization in social networks (namely, Twitter) and identify polarized groups. The approach is language-agnostic and thus broadly applicable to global and multilingual media. In cases of conflict, dispute, or situations involving multiple parties with contrasting interests, opinions get divided into different camps. Previous manual inspection of tweets has shown that such situations produce distinguishable signatures on Twitter, as people take sides leading to clusters that preferentially propagate information confirming their individual cluster-specific bias. We propose a model for polarized social networks, and show that approaches based on factorizing the matrix of sources and their claims can automate the discovery of polarized clusters with no need for prior training or natural language processing. In turn, identifying such clusters offers insights into prevalent social conflicts and helps automate the generation of less biased descriptions of ongoing events. We evaluate our factorization algorithms and their results on multiple Twitter datasets involving polarization of opinions, demonstrating the efficacy of our approach. Experiments show that our method is almost always correct in identifying the polarized information from real-world twitter traces, and outperforms the baseline mechanisms by a large margin.

Mobile traffic data collected by network operators is a rich source of information about human habits, and its analysis provides insights relevant to many fields, including urbanism, transportation, sociology and networking. In this paper, we present an original approach to infer both spatial and temporal structures hidden in the mobile demand, via a first-time tailoring of Exploratory Factor Analysis (EFA) techniques to the context of mobile traffic datasets. Casting our approach to the time or space dimensions of such datasets allows solving different problems in mobile traffic analysis, i.e., network activity profiling and land use detection, respectively. Tests with real-world mobile traffic datasets show that, in both its variants above, the proposed approach (i) yields results whose quality matches or exceeds that of state-of-the-art solutions, and (ii) provides additional joint spatiotemporal knowledge that is critical to result interpretation.

Software defined networks (SDNs) reshape the ossified network architectures, by introducing centralized and programmable network control. Despite the huge benefits, SDNs also open doors to what we call rule modification attack, an attack largely overlooked by the community. In such an attack, the adversary can modify rules by exploiting implementation vulnerabilities of switch OSes and control channels. As a result, packets may deviate from their original paths, thereby violating network policies. To defend against rule modification attack, this paper introduces a new security primitive named rule enforcement verification (REV). REV allows a controller to check whether switches have enforced the rules installed by it, using message authentication code (MAC). Since using standard MACs will incur heavy switch-to-controller traffic, this paper proposes a new compressive MAC, which allows switches to compress MACs before reporting to the controller. Experiments show that REV based on compressive MAC can achieve a 97% reduction in switch-to-controller traffic, and a Sx increase in verification throughput.