INFOCOM 2016 Papers

Providing high end-to-end (E2E) performance is critical for cellular service providers to best serve their customers. Detecting and localizing E2E performance degradation is crucial for cellular service providers, content providers, device manufactures, and application developers to jointly troubleshoot root causes. To the best of our knowledge, detection and localization of E2E performance degradation at cellular service providers has not been previously studied. In this paper, we propose a holistic approach to detecting and localizing E2E performance degradation at cellular service providers across the four dimensions of user locations, content providers, device types, and application types. First, we use training data to build models that can capture the normal performance of every E2E-instance, which means flows corresponding to a specific location, content provider, device type, and application type. Second, we use our models to detect performance degradation for each E2E-instance on an hourly basis. Third, after each E2E-instance has been labeled as non-degrading or degrading, we use association rule mining techniques to localize the source of performance degradation. Our system detected performance degradation instances over a period of one week. In 80% of the detected degraded instances, content providers, device types, and application types were the only factors of performance degradation.

Energy saving in cellular systems is increasingly important due to ever-deteriorating global warming. Heterogeneous networks (HetNets) composed of various tiers of cells can attain energy savings thanks to the lower operational and transmit power consumptions of small cells. To address the inter-cell interference problem yet achieving network energy conservation, multicell cooperation facilitating cooperative transmission (also known as coordinated multipoint or CoMP) and sleep mode operation paves a way toward future green HetNets. To further alleviate the induced backhaul energy consumption caused by cooperative transmission, content caching which proactively caches popular files at local storages is regarded as a viable solution. In this paper, we investigate how energy-aware multicell cooperation in HetNets with content caching (ENCORE) can be achieved. On proving that the ENCORE problem is decomposable into two sub-problems, we claim that the place-then-transmit strategy is optimal to the ENCORE problem. Then, we design algorithms for the sub-problems and prove that the total energy consumption achieved by the proposed solution is upper-bounded. Our simulation results demonstrate that the proposed solution outperforms various dynamic clustering approaches in terms of energy savings, and show the impacts of content popularity and cache size on the backhaul energy consumption.

Social network data is widely shared, transferred and published for research purposes and business interests, but it has raised much concern on users' privacy. Even though users' identity information is always removed, attackers can still de-anonymize users with the help of auxiliary information. To protect against de-anonymization attack, various privacy protection techniques for social networks have been proposed. However, most existing approaches assume specific and restrict network structure as background knowledge and ignore semantic level prior belief of attackers, which are not always realistic in practice and do not apply to arbitrary privacy scenarios. Moreover, the privacy inference attack in the presence of semantic background knowledge is barely investigated. To address these shortcomings, in this work, we introduce knowledge graphs to explicitly express arbitrary prior belief of the attacker for any individual user. The processes of de-anonymization and privacy inference are accordingly formulated based on knowledge graphs. Our experiment on data of real social networks shows that knowledge graphs can strengthen de-anonymization and inference attacks, and thus increase the risk of privacy disclosure. This suggests the validity of knowledge graphs as a general effective model of attackers' background knowledge for social network privacy preservation.

Recent years have witnessed a growing number of location-based service providers (LBSPs) outsourcing their points of interest (POI) datasets to third-party cloud service providers (CSPs), which in turn answer various data queries from mobile users on their behalf. A main challenge in such systems is that the CSPs cannot be fully trusted, which may return fake query results for various bad motives, e.g., in favor of POIs willing to pay. As an important type of queries, location-based skyline queries (LBSQs) ask for the POIs that are not spatially dominated by any other POI with respect to some query position. In this paper, we propose three novel schemes that enable efficient verification of any LBSQ result returned by an untrusted CSP by embedding and exploring a novel neighboring relationship among POIs. The efficacy and efficiency of our schemes are thoroughly analyzed and evaluated.

Content Delivery Networks (CDNs) have emerged as a dominant mechanism to deliver content over the Internet. Despite their importance, to our best knowledge, large-scale analysis of CDN cache performance is lacking in prior literature. A CDN serves many content publishers simultaneously and thus has unique workload characteristics; it typically deals with extremely large content volume and high content diversity from multiple content publishers. CDNs also have unique performance metrics; other than hit ratio, CDNs also need to minimize network and disk load on cache servers. In this paper, we present measurement and analysis of caching workload at a large commercial CDN. Using detailed logs from four geographically distributed CDN cache servers, we analyze over 600 million content requests accounting for more than 1.3 petabytes worth of traffic. We analyze CDN workload from a wide range of perspectives, including request composition, size, popularity, and temporal dynamics. Using real-world logs, we also evaluate cache replacement algorithms, including two enhancements designed based on our CDN workload analysis: N-hit and content-aware caching. The results show that these enhancements achieve substantial performance gains in terms of cache hit ratio, disk load, and origin traffic volume.

In this work we study how to manage the freshness of status updates sent from a source to a remote monitor via a network server. A proper metric of data freshness at the monitor is the age-of-information, which is defined as how old the freshest update is since the moment this update was generated at the source. A logical policy is the zero-wait policy, i.e., the source submits a fresh update once the server is free, which achieves the maximum throughput and the minimum average delay. Surprisingly, this zero-wait policy does not always minimize the average age. This motivates us to study how to optimally control the status updates to keep data fresh and to understand when the zero-wait policy is optimal. We introduce a penalty function to characterize the level of “dissatisfaction” on data staleness, and formulate the average age penalty minimization problem as a constrained semi-Markov decision process (SMDP) with an uncountable state space. Despite of the difficulty of this problem, we develop efficient algorithms to find the optimal status update policy. We show that, in many scenarios, the optimal policy is to wait for a certain amount of time before submitting a new update. In particular, the zero-wait policy can be far from the optimum if (i) the penalty function grows quickly with respect to the age, and (ii) the update service times are highly random and positive correlated. To the best of our knowledge, this is the first optimal control policy which is proven to minimize the age-of-information in status update systems.

In this paper, we advocate Crowdlet, a novel self-organized mobile crowdsourcing paradigm, in which a mobile task requester can proactively exploit a massive crowd of encountered mobile workers at real-time for quick and high-quality results. We present a comprehensive system model of Crowdlet that defines task, worker arrival and worker ability models. Further, we introduce a service quality concept to indicate the expected service gain that a requester can enjoy when he recruits an encountered worker, by jointly taking into account worker ability, real-timeness and task reward. Based on the models, we formulate an online worker recruitment problem to maximize the expected sum of service quality. We derive an optimal worker recruitment policy through the dynamic programming principle, and show that it exhibits a nice threshold based structure. We conduct extensive performance evaluation based on real traces, and numerical results demonstrate that our policy can achieve superior performance and improve more than 30% performance gain over classic policies. Besides, our Android prototype shows that Crowdlet is cost-efficient, requiring less than 7 seconds and 6 Joule in terms of time and energy cost for policy computation in most cases.

In this paper, we consider the problem of distributing patrol officers inside a building to maximize the probability of catching multiple intruders while minimizing the distance the patrol officers travel to reach the locations of the intruders. In our problem setting, the patrol officers are assisted by the information collected by a network of binary proximity sensors installed in the building. We claim that learning even common movement sub-patterns that originate due to the constrained physical environment helps to find likely locations of intruders where each major location is instrumented using a sensor node. We use a series of binary detection events to infer likely future trajectories in a real-world building. For a given set of detectable nodes on the inferred future trajectories, we aim to find the optimal patrol dispatch node location with high exposure to intruders' future appearance using patrol officers in limited numbers, ideally fewer than the intruders. In order to prevent possible crime and perform responsive defense against potential intruders, our algorithm also tries to reduce the travel distance from patrols current positions to their dispatched positions at the same time. We validate our proposed scheme in terms of detection accuracy by varying the number of intruders, robustness against missing events, and responsiveness compared to a practical baseline counterpart through real-world system experiments.

This paper presents DiVA, a novel hybrid range-free and range-based acoustic source localization scheme that uses an ad-hoc network of microphone sensor nodes to produce an accurate estimate of the source's location in the presence of various real-world challenges. DiVA uses range-free pairwise comparisons of sound detection timestamps between local Voronoi neighbors to identify the node closest to the acoustic source, which then estimates the source's location using a constrained range-based method. Through simulation and experimental evaluations, DiVA is shown to be accurate and highly robust, making it practical for real-world applications.

Closed-loop flow control protocols, such as the prominent implementation TCP, are prevalent in the Internet, today. TCP has continuously been improved for greedy traffic sources to achieve high throughput over networks with large bandwidth delay products. Recently, the increasing use for streaming and interactive applications, such as voice and video, has shifted the focus towards its delay performance. Given the need for real-time communication of non-greedy sources via TCP, we present an estimation method for performance evaluation of closed-loop flow control protocols. We characterize an end-to-end connection by a transfer function that provides statistical service guarantees for arbitrary traffic. The estimation is based on end-to-end measurements at the application level, that include all effects induced by the network and by the protocol stacks of the end systems. From our measurements, we identify different causes for delays. We show that significant delays are due to queueing in protocol stacks. Notably, this occurs even if the utilization is moderate. Using our estimation method, we compare the impact of fundamental mechanisms of TCP. In detail, we analyze buffer provisioning and its impact on delays at the application level. We find that a good selection can largely improve the delay performance of TCP.

Recent advances have demonstrated the potential of network MIMO (netMIMO), which combines a practical number of distributed antennas as a virtual netMIMO AP (nAP) to improve spatial multiplexing of an WLAN. Existing solutions, however, either simply cluster nearby antennas as static nAPs, or dynamically cluster antennas on a per-packet basis so as to maximize the sum rate of the scheduled clients. To strike the balance between the above two extremes, in this paper, we present the design, implementation and evaluation of FlexNEMO, a practical two-phase netMIMO clustering system. Unlike previous per-packet clustering approaches, FlexNEMO only clusters antennas when client distribution and traffic pattern change, as a result being more practical to be implemented. A medium access control protocol is then designed to allow the clients at the center of nAPs to have a higher probability to gain access opportunities, but still ensure long-term fairness among clients. By combining on-demand clustering and priority-based access control, FlexNEMO not only improves antenna utilization, but also optimizes the channel condition for every individual client. We evaluated our design via both testbed experiments on USRPs and trace-driven emulations. The results demonstrate that FlexNEMO can deliver 94.7% and 93.7% throughput gains over static antenna clustering in a 4-antenna testbed and 16-antenna emulation, respectively.

Over the past decades, many large-scale social network systems, such as Facebook and Twitter, have been deployed in different countries. How to efficiently analyze the topological characteristics of large-scale social networks has been a challenging problem in the research community. One of the critical topological characteristics is the shortest distance between two nodes in a network. The existing shortest distance algorithms, such as Breadth First Search (BFS), work well with small networks. For a network with billions of nodes, calculating the pairwise shortest distances with these algorithms requires an overlong period of time. In this paper, we present a high-precision ShOrtest Distance Approximation (SODA) scheme, which utilizes a small set of pre-calculated distances to estimate the shortest distance between each pair of nodes in large-scale social networks. Compared with the existing shortest distance estimation schemes for social networks, SODA leads to high estimation accuracy since it utilizes a novel optimization method, Robust Discrete Matrix Decomposition (RDMD), to eliminate the impact of significant errors/outliers and generate the coordinates of the nodes in a network simultaneously. In addition, SODA differentiates the asymmetric distances in directed graphs. Consequently, SODA works well with both directed and undirected social networks. Finally, SODA only involves convex optimization. Therefore, SODA is highly competitive in terms of computation complexity. Our experimental results indicate that SODA outperforms the state-of-the-art shortest distance estimation schemes in terms of estimation accuracy and running time.

Online social networks have been one of the most effective platforms for marketing and advertising. Through the “world-of-mouth” exchanges, so-called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the Influence Maximization (IM) problem that seeks a set of k seed users that maximize the expected influence. Unfortunately, IM encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called Cost-aware Targeted Viral Marketing (CTVM), to find the most cost-effective seed users who can influence the most relevant users to the advertisement. Since CTVM is NP-hard, we design an efficient (1 − 1/√e-∊ − e)-approximation algorithm, named BCT, to solve the problem in billion-scale networks. Comparing with IM algorithms, we show that BCT is both theoretically and experimentally faster than the state-of-the-arts while providing better solution quality. Moreover, we prove that under the Linear Threshold model, BCT is the first sub-linear time algorithm for CTVM (and IM) in dense networks. In our experiments with a Twitter dataset, containing 1.46 billions of social relations and 106 millions tweets, BCT can identify key influencers in each trending topic in only few minutes.

Information propagation in online social networks (OSNs), which helps shaping consumers' purchasing decisions, has received a lot of attention. The ultimate goal of marketing and advertising in OSNs is to massively influence audiences and enlarge the number of product adoptions. Most of existing works focus on maximizing the influence of a single product or promoting the adoption of one product in competing campaigns. However, in reality, the majority of companies produce various products for supplying customers with different needs. Therefore, it is truly significant and also challenging to wisely distribute limited budget across multiple products in viral marketing. In this paper, we investigate a Profit Maximization with Multiple Adoptions (PM2A) problem, which aims at maximizing the overall profit across all products. The natural greedy fails to provide a bounded result. In order to select high quality seeds for information propagation, we first proposed the PMCE algorithm, which has a ratio 1/2 (1 - 1/e2). Moreover, we further improve this ratio to (1-1/e) by proposing the PMIS algorithm. Comprehensive experiments on three real social networks are conducted. And results show that our algorithms outperform other heuristics, and better distribute the budget in terms of profit maximization.

Mobile cloud computing (MCC) as an emerging and prospective computing paradigm, can significantly enhance computation capability and save energy of smart mobile devices (SMDs) by offloading computation-intensive tasks from resource-constrained SMDs onto the resource-rich cloud. However, how to achieve energy-efficient computation offloading under the hard constraint for application completion time remains a challenge issue. To address such a challenge, in this paper, we provide an energy-efficient dynamic offloading and resource scheduling (eDors) policy to reduce energy consumption and shorten application completion time. We first formulate the eDors problem into the energy-efficiency cost (EEC) minimization problem while satisfying the task-dependency requirements and the completion time deadline constraint. To solve the optimization problem, we then propose a distributed eDors algorithm consisting of three subalgorithms of computation offloading selection, clock frequency control and transmission power allocation. More importantly, we find that the computation offloading selection depends on not only the computing workload of a task, but also the maximum completion time of its immediate predecessors and the clock frequency and transmission power of the mobile device. Finally, our experimental results in a real testbed demonstrate that the eDors algorithm can effectively reduce the EEC by optimally adjusting the CPU clock frequency of SMDs based on the dynamic voltage and frequency scaling (DVFS) technique in local computing, and adapting the transmission power for the wireless channel conditions in cloud computing.

This paper presents a novel cache replacement method — Popularity-Driven Content Caching (PopCaching). PopCaching learns the popularity of content and uses it to determine which content it should store and which it should evict from the cache. Popularity is learned in an online fashion, requires no training phase and hence, it is more responsive to continuously changing trends of content popularity. We prove that the learning regret of PopCaching (i.e., the gap between the hit rate achieved by PopCaching and that by the optimal caching policy with hindsight) is sublinear in the number of content requests. Therefore, PopCaching converges fast and asymptotically achieves the optimal cache hit rate. We further demonstrate the effectiveness of PopCaching by applying it to a movie.douban.com dataset that contains over 38 million requests. Our results show significant cache hit rate lift compared to existing algorithms, and the improvements can exceed 40% when the cache capacity is limited. In addition, PopCaching has low complexity.

Even with the recent proliferation of in-memory computation in data-parallel frameworks (such as Spark), transfers over the network are still time-consuming. Similar to computation, network transfers serve as main roadblocks as we try to minimize job completion times. Existing schedulers were designed as isolated solutions that focused on computation or network performance only. Without any coordination, the utilization of computation and network resources may become unbalanced, leading to a reduced level of overall resource utilization. In this paper, we design, implement, and evaluate Symbiosis, a network-aware task scheduler designed to coordinate computation-bound and network-bound tasks in a large cluster, so that resources are utilized in a more balanced fashion. Symbiosis is an online scheduler that predicts resource imbalance before launching tasks, and correct such imbalance by co-locating computation-bound and network-bound tasks in the same executor process. As a guiding principle, it is engineered to be practically implemented within and to complement existing data-parallel frameworks. We have implemented Symbiosis within Spark, and carried out our experiments on a 100-node cluster. We show convincing evidence that Symbiosis reduces job completion times by 11.9% in comparison to Spark's current scheduler with little overhead.

Recently, there have been a growing number of applications that power wireless sensor networks (WSNs) by wireless charging technology. Although previous studies indicate that wireless charging can deliver energy reliably, it still faces regulatory challenges to provide high power density without incurring health risks. In particular, in clustered WSNs there exists a mismatch between the high energy demands from cluster heads and the relatively low energy supplies that wireless charging can provide. Fortunately, solar energy harvesting can provide high power density which is also risk-free. However, it is subject to weather dynamics. Therefore, in this paper, we propose a hybrid framework that combines the two technologies - cluster heads are equipped with solar panels to scavenge solar energy and the rest of nodes are powered by wireless charging. First, we study a placement problem on how to deploy solar-powered cluster heads that can minimize overall cost and propose a distributed 1.61(1 + ϵ)2-approximation algorithm for the placement. Second, we establish an energy balance in the network and explore how to maintain such balance when sunlight is unavailable. Third, we consider combining wireless charging and mobile data gathering in a joint tour in such networks, and propose a polynomial-time scheduling algorithm. Our extensive simulation demonstrates that the hybrid framework can reduce battery depletion by 20% and save system cost by 25% compared to previous results.

Multipath TCP (MPTCP) is a promising technique for boosting application throughput while using well-known and versatile network socket interfaces. Recently, many interesting applications of MPTCP in various environments such as wireless networks and data centers have been proposed, but little work has been done to investigate the impact of this protocol on conventional network devices. For example, MPTCP throughput advantage can be better achieved if all MPTCP subflows are routed on disjoint paths, but this is currently not feasible since routers are not designed to recognize the membership of MPTCP subflows. In this paper, we take a first step to address this issue by proposing SAMPO, an online algorithm to detect and associate MPTCP subflows in network. The main challenge is that sampling techniques and network dynamics may cause a network device to only obtain partial flow records. SAMPO takes advantage of both protocol information and statistical characteristics of MPTCP data sequence number to overcome the challenge in network. Through analysis and experimentation, we show that SAMPO is able to detect and associate MPTCP subflows with high accuracy even when a small portion of the entire flow records are available.