INFOCOM 2018 论文列表

This paper develops a constrained expectation maximization algorithm (CEM) that improves the accuracy of truth estimation in unguided social sensing applications. Unguided social sensing refers to the act of leveraging naturally occurring observations on social media as “sensor measurements”, when the sources post at will and not in response to specific sensing campaigns or surveys. A key challenge in social sensing, in general, lies in estimating the veracity of reported observations, when the sources reporting these observations are of unknown reliability and their observations themselves cannot be readily verified. This problem is known as fact-finding. Unsupervised solutions have been proposed to the fact-finding problem that explore notions of internal data consistency in order to estimate observation veracity. This paper observes that unguided social sensing gives rise to a new (and very simple) constraint that dramatically reduces the space of feasible fact-finding solutions, hence significantly improving the quality of fact-finding results. The constraint relies on a simple approximate test of source independence, applicable to unguided sensing, and incorporates information about the number of independent sources of an observation to constrain the posterior estimate of its probability of correctness. Two different approaches are developed to test the independence of sources for purposes of applying this constraint, leading to two flavors of the CEM algorithm, we call CEM and CEM-Jaccard. We show using both simulation and real data sets collected from Twitter that by forcing the algorithm to converge to a solution in which the constraint is satisfied, the quality of solutions is significantly improved.

Online knapsack problem is considered, where items arrive in a sequential fashion that have two attributes; value and weight. Each arriving item has to be accepted or rejected on its arrival irrevocably. The objective is to maximize the sum of the value of the accepted items such that the sum of their weights is below a budget/capacity. Conventionally a hard budget/capacity constraint is considered, for which variety of results are available. In modern applications, e.g., in wireless networks, data centres, cloud computing, etc., enforcing the capacity constraint in expectation is sufficient. With this motivation, we consider the knapsack problem with an expected capacity constraint. For the special case of knapsack problem, called the secretary problem, where the weight of each item is unity, we propose an algorithm whose probability of selecting any one of the optimal items is equal to 1 -1/e and provide a matching lower bound. For the general knapsack problem, we propose an algorithm whose competitive ratio is shown to be 1/4e that is significantly better than the best known competitive ratio of 1/10e for the knapsack problem with the hard capacity constraint.

Biological cells naturally exchange information for adapting to the environment, or even influencing other cells. One of the latest frontiers of synthetic biology stands in engineering cells to harness these natural communication processes for tissue engineering and cancer treatment, amongst others. Although experimental success has been achieved in this direction, approaches to characterize these systems in terms of communication performance and their dependence on design parameters are currently limited. In contrast to more classical communication systems, information in biological cells is propagated through molecules and biochemical reactions, which in general result in nonlinear input-output behaviors with system-evolution-dependent stochastic effects that are not amenable to analytical closed-form characterization. In this paper, a computational approach is proposed to characterize the information exchange in these systems, based on stochastic simulation of biochemical reactions and the estimation of information-theoretic parameters from sample distributions. In particular, this approach focuses on engineered cell-to-cell communications with a single transmitter and receiver, and it is applied to characterize the performance of a realistic system. Numerical results confirm the feasibility of this approach to be at the basis of future forward engineering practices for these communication systems.

Today's online marketing industry has widely employed email tracking techniques, such as embedding a tiny tracking pixel, to track email opens of potential customers and measure marketing effectiveness. However, email tracking could allow miscreants to collect metadata information associated with email reading without user awareness and then leverage the information for stealthy surveillance, which has raised serious privacy concerns. In this paper, we present an in-depth and comprehensive study on the privacy implications of email tracking. First, we develop an email tracking system and perform realworld tracking on hundreds of solicited crowdsourcing participants. We estimate the amount of privacy-sensitive information available from email reading, assess privacy risks of information leakage, and demonstrate how easy it is to launch a long-term targeted surveillance attack in real scenarios by simply sending an email with tracking capability. Second, we investigate the prevalence of email tracking through a large-scale measurement, which includes more than 44,000 email samples obtained over a period of seven years. Third, we conduct a user study to understand users' perception of privacy infringement caused by email tracking. Finally, we evaluate existing countermeasures against email tracking and propose guidelines for developing more comprehensive and fine-grained prevention solutions.

Mobile applications outsource their cloud infrastructure deployment and content delivery to cloud computing services and content delivery networks. Studying how these services, which we collectively denote Cloud Service Providers (CSPs), perform over Mobile Network Operators (MNOs) is crucial to understanding some of the performance limitations of today's mobile apps. To that end, we perform the first empirical study of the complex dynamics between applications, MNOs and CSPs. First, we use real mobile app traffic traces that we gathered through a global crowdsourcing campaign to identify the most prevalent CSPs supporting today's mobile Internet. Then, we investigate how well these services interconnect with major European MNOs at a topological level, and measure their performance over European MNO networks through a month-long measurement campaign on the MONROE mobile broadband testbed. We discover that the top 6 most prevalent CSPs are used by 85 % of apps, and observe significant differences in their performance across different MNOs due to the nature of their services, peering relationships with MNOs, and deployment strategies. We also find that CSP performance in MNOs is affected by inflated path length, roaming, and presence of middleboxes, but not influenced by the choice of DNS resolver.

Several organizations have built multiple datacenters connected via dedicated wide area networks over which large inter-datacenter transfers take place. Since many such transfers move the same data from one source to multiple destinations, using multicast forwarding trees can reduce bandwidth needs and improve completion times. However, using a single forwarding tree per transfer can lead to poor performance as the slowest receiver dictates the completion time for all receivers. Using multiple forwarding trees per transfer alleviates this concern-the average receiver could finish early; however, if done naively, bandwidth usage would also increase and it is apriori unclear how best to partition receivers, how to construct the multiple trees and how to determine the rate and schedule of flows on these trees. This paper presents QuickCast, a first solution to these problems. Using simulations on real-world network topologies, we see that QuickCast can speed up the average receiver's completion time by as much as 10× while only using 1.04× more bandwidth; further, the completion time for all receivers also improves by as much as faster at high loads. Thereby, while some implementation challenges remain, we advocate using a cohort of forwarding trees.

Datacenter networks are critical to Cloud computing. The coflow abstraction is a major leap forward of application-aware network scheduling. In the context of multistage jobs, there are dependencies among coflows. As a result, there is a large divergence between coflow-completion-time (CCT) and job-completion-time (JCT). To our best knowledge, this is the first work that systematically studies: how to schedule dependent coflows of multi-stage jobs, so that the total weighted job completion time can be minimized. We present a formal mathematical formulation. We also prove that this problem is strongly NP-hard. Inspired by the optimal solution of the relaxed linear programming, we design an algorithm that runs in polynomial time to solve this problem with an approximation ratio of (2M + 1), where M is the number of machines. Evaluation results demonstrate that, the largest gap between our algorithm and the lower bound is only 9.14%. We reduce the average JCT by up to 33.48 % compared with Aalo, a heuristic multi-stage coflow scheduler. We reduce the total weighted JCT by up to 83.31 % compared with LP-OV-LS, the state-of-the-art approximation algorithm of coflow scheduling.

Ultra-dense small cell networks will require sophisticated user association algorithms that consider (i) channel characteristics, (ii) base station load, and (iii) uplink/downlink (UL/DL) traffic profiles. They will also be characterized by high spatio-temporal variability in UL/DL traffic demand, due to the fewer users per BS. In this direction, Dynamic TDD is a promising new technique to match BS resources to actual demand. While plenty of literature exists on the problem of user association, and some recent on dynamic TDD, most works consider these separately. In this paper, we argue that user association policies are strongly coupled with the allocation of resources between UL and DL. We propose an algorithm that decomposes the problem into separate subproblems that can each be solved efficiently and in a distributed manner, and prove convergence to the global optimum. Simulation results suggest that our approach can improve UL and DL performance at the same time, with an aggregate improvement of more than 2×, compared to user association under static TDD allocation.

The surge in mobile broadband data demands is expected to surpass the available spectrum capacity below 6 GHz. This expectation has prompted the exploration of millimeter wave (mm-wave) frequency bands as a candidate technology for next generation wireless networks. However, numerous challenges to deploying mm-wave communication systems, including channel estimation, need to be met before practical deployments are possible. This work addresses the mm-wave channel estimation problem and treats it as a beam discovery problem in which locating beams with strong path reflectors is analogous to locating errors in linear block codes. We show that a significantly small number of measurements (compared to the original dimensions of the channel matrix) is sufficient to reliably estimate the channel. We also show that this can be achieved using a simple and energy-efficient transceiver architecture.

Efficient resource management is of paramount importance in today's production clusters. In this paper, we identify the demand elasticity of data-parallel jobs. Demand elasticity allows jobs to run with a significantly less amount of resources than they ideally need, at the expense of only a modest performance penalty. Our EC2 experiment using popular Spark benchmark suites confirms that running a job using 50% of demanded slots is sufficient to achieve at least 75% of the ideal performance. We show that such an elasticity is an intrinsic property of data-parallel jobs and can be exploited to speed up average job completion. In this regard, we propose Performance-Aware Fair (PAF) scheduler to identify the demand elasticity and use it to improve the average job performance, while still attaining near-optimal isolation guarantee close to fair sharing. PAF starts with a fair allocation and iteratively adjusts it by transferring resources from one job to another, improving the performance of resource-taker without penalizing resource-giver by a noticeable amount. We implemented PAF in Spark and evaluated its effectiveness through both EC2 experiments and large-scale simulations. Evaluation results show that compared with fair allocation, PAF improves the average job performance by 13%, while penalizing resource-givers by no more than 1%.

Evolving anomalous subgraphs detection in dynamic networks is an important and challenging problem that has arisen in multiple applications and is NP-hard in general. The evolving characteristic makes most existing methods incapable to tackle this problem effectively and efficiently, as it involves huge search spaces and continuous changes of evolving connected subgraphs, especially when the data are free of distributions. This paper presents a generic efficient framework, namely dynamic evolving anomalous subgraphs scanning (dGraphScan), to address this problem. We generalize traditional nonparametric scan statistics, and propose a large class of scan statistic functions for measuring the significance of evolving subgraphs in dynamic networks. Furthermore, we make a number of computational studies to optimize this large class of nonparametric scan statistic functions. Specifically, we first decompose each scan statistic function as a sequence of subproblems with provable guarantees, and then propose efficient approximation algorithms for tackling each subproblem, while analyzing their theoretical properties and providing rigorous approximation guarantees. Extensive experiments on three real-world datasets demonstrate that our general framework performs superior over state-of-the-art methods.

Multihop wireless networking is a key enabling technology for interconnecting a vast number of IoT devices. Measurement is fundamental to various network operations including management, diagnostics, and optimization. Out-of-band measurement approaches use external sniffers to monitor the network traffic passively, and they provide detailed information about the network. However, existing approaches do not carefully consider lossy and correlated links which are common in low-power wireless networks, resulting in unsatisfactory packet capture ratio and low measurement quality. In this paper, we present NetVision, a practical out-of-band measurement system with special consideration for sniffer deployment. By explicitly considering link quality and link correlation, we are able to achieve a high measurement quality while minimizing the deployment cost. We formulate the sniffer deployment problem as an optimization problem and propose efficient algorithms for solving this problem. We further design a set of instructions and APIs to simplify a variety of common measurement tasks. We implement NetVision on the TinyOS/TelosB platform and evaluate its performance extensively both in simulation and an indoor testbed with 80 TelosB nodes. Results show that NetVision is accurate, generic, and robust. Three typical case studies demonstrate that NetVision can facilitate various measurement and debugging tasks.

The robustness of system throughput with scheduling is a critical issue. In this paper, we analyze the sensitivity of multi-user scheduling performance to channel misreporting in systems with massive antennas. The main result is that for the round-robin scheduler combined with max-min power control, the channel magnitude misreporting is harmful to the scheduling performance and has a different impact from the purely physical layer analysis. Specifically, for the homogeneous users that have equal average signal-to-noise ratios (SNRs), underreporting is harmful, while overreporting is beneficial to others. In under-reporting, the asymptotic rate loss on others is derived, which is tight when the number of antennas is huge. One interesting observation in our research is that the rate loss “periodically” increases and decreases as the number of misreporters grows. For the heterogeneous users that have various SNRs, both underreporting and overreporting can degrade the scheduler performance. We observe that strong misreporting changes the user grouping decision and hence greatly decreases some users' rates regardless of others gaining rate improvements, while with carefully designed weak misreporting, the scheduling decision keeps fixed and the rate loss on others is shown to grow nearly linearly with the number of misreporters.

We consider the scenario where a source streams a flow at fixed rate to a receiver across a network, possibly using multiple paths. Transmission over a link incurs a delay modeled as a non-negative, non-decreasing and differentiable function of the link aggregated transmission rate. This setting models various practical network communication scenarios. We study network delay optimization concerning two popular metrics, namely maximum delay and average delay experienced by the flow. A well-known pessimistic result says that a flow cannot simultaneously achieve optimal maximum delay and optimal average delay, or even within constant-ratio gaps to the two optimums. In this paper, we pose an optimistic note on the fundamental compatibility of the two delay metrics. Specifically, we design two polynomial-time solutions to deliver (1 -ε) fraction of the flow with maximum delay and average delay simultaneously within 1/ε to the optimums for any ε ∈ (0,1). Hence, the two delay metrics are “largely” compatible. The ratio 1/ε is independent to the network size and link delay function, and we show that it is tight or near-tight. Simulations based on real-world continent-scale network topology verify our theoretical findings. Note that the proposed delay gap 1/ε, upon sacrificing ε fraction of the flow rate, is guaranteed even under the worst theoretical case setting. Our simulation results show that the empirical delay gaps observed under practical settings can be much smaller than 1/ε. Our results are of particular interest to delay-centric networking applications that can tolerate a small fraction of traffic loss, including cloud video conferencing that recently attracts substantial attention.

Interference Alignment (IA) has emerged as a promising interference coordination approach for cooperative MIMO systems. Due to heavy CSI feedback overhead, APs (Access Points) need to be partitioned into cooperation groups no larger than a certain size where only APs in the same group are able to cooperate with IA. We consider a general MIMO network using a hybrid interference coordination approach, i.e. intra-group interference is managed with IA, while inter-group interference is overcome with traditional orthogonal multiple access techniques. Users are usually non-uniformly distributed. Their throughput can be improved by association optimization. We study the novel problem of minimizing AP load by joint AP grouping and user association. The problem is shown to be NP-hard. Based on alternating direction optimization, we propose DAGA (Distributed Joint AP Grouping and User Association) to tackle the problem. DAGA is distributed and uses only long-term CSI. Based on current AP grouping, it produces an approximated user association solution which is at most elogm (m is the number of APs) times of the optimum. Based on current user association, it adjusts AP grouping with local search. Extensive simulation results show that it substantially outperforms other comparison schemes.

The advent of social networks poses severe threats on user privacy as adversaries can de-anonymize users' identities by mapping them to correlated cross-domain networks. Without ground-truth mapping, prior literature proposes various cost functions in hope of measuring the quality of mappings. However, there is generally a lacking of rationale behind the cost functions, whose minimizer also remains algorithmically unknown. We jointly tackle above concerns under a more practical social network model parameterized by overlapping communities, which, neglected by prior art, can serve as side information for de-anonymization. Regarding the unavailability of ground-truth mapping to adversaries, by virtue of the Minimum Mean Square Error (MMSE), our first contribution is a well-justified cost function minimizing the expected number of mismatched users over all possible true mappings. While proving the NP-hardness of minimizing MMSE, we validly transform it into the weighted-edge matching problem (WEMP), which, as disclosed theoretically, resolves the tension between optimality and complexity: (i) WEMP asymptotically returns a negligible mapping error in large network size under mild conditions facilitated by higher overlapping strength; (ii) WEMP can be algorithmically characterized via the convex-concave based de-anonymization algorithm (CBDA), finding the optimum of WEMP. Extensive experiments further confirm the effectiveness of CBDA under overlapping communities, in terms of averagely 90% re-identified users in the rare true cross-domain co-author networks when communities overlap densely, and roughly 70% enhanced reidentification ratio compared to non-overlapping cases.

Being the largest blockchain with the capability of running smart contracts, Ethereum has attracted wide attention and its market capitalization has reached 20 billion USD. Ethereum not only supports its cryptocurrency named Ether but also provides a decentralized platform to execute smart contracts in the Ethereum virtual machine. Although Ether's price is approaching 200 USD and nearly 600K smart contracts have been deployed to Ethereum, little is known about the characteristics of its users, smart contracts, and the relationships among them. To fill in the gap, in this paper, we conduct the first systematic study on Ethereum by leveraging graph analysis to characterize three major activities on Ethereum, namely money transfer, smart contract creation, and smart contract invocation. We design a new approach to collect all transaction data, construct three graphs from the data to characterize major activities, and discover new observations and insights from these graphs. Moreover, we propose new approaches based on cross-graph analysis to address two security issues in Ethereum. The evaluation through real cases demonstrates the effectiveness of our new approaches.

For many networking applications, recent data is more significant than older data, motivating the need for sliding window solutions. Various capabilities, such as DDoS detection and load balancing, require insights about multiple metrics including Bloom filters, per-flow counting, count distinct and entropy estimation. In this work, we present a unified construction that solves all the above problems in the sliding window model. Our single solution offers a better space to accuracy tradeoff than the state-of-the-art for each of these individual problems! We show this both analytically and by running multiple real Internet backbone and datacenter packet traces.

Emerging technologies and applications including Internet of Things (IoT), social networking, and crowd-sourcing generate large amounts of data at the network edge. Machine learning models are often built from the collected data, to enable the detection, classification, and prediction of future events. Due to bandwidth, storage, and privacy concerns, it is often impractical to send all the data to a centralized location. In this paper, we consider the problem of learning model parameters from data distributed across multiple edge nodes, without sending raw data to a centralized place. Our focus is on a generic class of machine learning models that are trained using gradient-descent based approaches. We analyze the convergence rate of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best trade-off between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment. The experimentation results show that our proposed approach performs near to the optimum with various machine learning models and different data distributions.