INFOCOM 2015 论文列表

Mobile crowdsensing is a new paradigm in which a crowd of mobile users exploit their carried smart devices to conduct complex computation and sensing tasks in mobile social networks (MSNs). In this paper, we focus on the task assignment problem in mobile crowdsensing. Unlike traditional task scheduling problems, the task assignment in mobile crowdsensing must follow the mobility model of users in MSNs. To solve this problem, we propose an oFfline Task Assignment (FTA) algorithm and an oNline Task Assignment (NTA) algorithm. Both FTA and NTA adopt a greedy task assignment strategy. Moreover, we prove that the FTA algorithm is an optimal offline task assignment algorithm, and give a competitive ratio of the NTA algorithm. In addition, we demonstrate the significant performance of our algorithms through extensive simulations, based on four real MSN traces and a synthetic MSN trace.

Many BigData applications (e.g., MapReduce, web caching, search in large graphs) process streams of random key-value records that follow highly skewed frequency distributions. In this work, we first develop stochastic models for the probability to encounter unique keys during exploration of such streams and their growth rate over time. We then apply these models to the analysis of LRU caching, MapReduce overhead, and various crawl properties (e.g., node-degree bias, frontier size) in random graphs.

A problem of much current practical interest is the replacement of the wiring infrastructure connecting approximately 200 sensor and actuator nodes in automobiles by an access point. This is motivated by the considerable savings in automobile weight, simplification of manufacturability, and future upgradability. A key issue is how to schedule the nodes on the shared access point so as to provide regular packet delivery. In this and other similar applications, the mean of the inter-delivery times of packets, i.e., throughput, is not sufficient to guarantee service-regularity. The time-averaged variance of the inter-delivery times of packets is also an important metric. So motivated, we consider a wireless network where an Access Point schedules real-time generated packets to nodes over a fading wireless channel. We are interested in designing simple policies which achieve optimal mean-variance tradeoff in interdelivery times of packets by minimizing the sum of time-averaged means and variances over all clients. Our goal is to explore the full range of the Pareto frontier of all weighted linear combinations of mean and variance so that one can fully exploit the design possibilities. We transform this problem into a Markov decision process and show that the problem of choosing which node's packet to transmit in each slot can be formulated as a bandit problem. We establish that this problem is indexable and explicitly derive the Whittle indices. The resulting Index policy is optimal in certain cases. We also provide upper and lower bounds on the cost for any policy. Extensive simulations show that Index policies perform better than previously proposed policies.

Use of IP-layer anycast has increased in the last few years: once relegated to DNS root and top-level domain servers, anycast is now commonly used to assist distribution of general purpose content by CDN providers. Yet, the measurement techniques for discovering anycast replicas have been designed around DNS, limiting their usefulness to this particular service. This raises the need for protocol agnostic methodologies, that should additionally be as lightweight as possible in order to scale up anycast service discovery. This is precisely the aim of this paper, which proposes a new method for exhaustive and accurate enumeration and city-level geolocation of anycast instances, requiring only a handful of latency measurements from a set of known vantage points. Our method exploits an iterative workflow that enumerates (an optimization problem) and geolocates (a classification problem) anycast replicas. We thoroughly validate our methodology on available ground truth (several DNS root servers), using multiple measurement infrastructures (PlanetLab, RIPE), obtaining extremely accurate results (even with simple algorithms, that we compare with the global optimum), that we make available to the scientific community. Compared to the state of the art work that appeared in INFOCOM 2013 and IMC 2013, our technique (i) is not bound to a specific protocol, (ii) requires 1000 times fewer vantage points, not only (iii) achieves over 50% recall but also (iv) accurately identifies the city-level geolocation for over 78% of the enumerated servers, with (v) a mean geolocation error of 361 km for all enumerated servers.

Latest developments in cloud computing technologies have enabled a plethora of cloud based data storage services. Cloud storage service providers are facing significant bandwidth cost as the user population scales. Such bandwidth cost can be substantially slashed by exploring a hybrid cloud storage architecture that takes advantage of under-utilized storage and network resources at storage clients. A critical component in the new hybrid cloud storage architecture is an economic mechanism that incentivizes clients to contribute their local resources, while at the same time minimizes the provider's cost for pooling those resources. This work studies online procurement auction mechanisms towards these goals. The online nature of the auction is in line with asynchronous user request arrivals in practice. After carefully characterizing truthfulness conditions under the online procurement auction paradigm, we prove that truthfulness can be guaranteed by a price-based allocation rule and payment rule. Our truthfulness characterization actually converts the mechanism design problem into an online algorithm design problem, with a marginal pricing function for resources as variables set by cloud storage service providers for online procurement auction. We derive the marginal pricing function for the online algorithm. We also prove the competitive ratio of the social cost of our algorithm against that of the offline VCG mechanism and of the resource pooling cost of our algorithm against that of the offline optimal auction. Simulation studies driven by real-world traces are conducted to show the efficacy of our online auction mechanism.

This paper considers the problem of server-side scheduling for jobs composed of multiple pieces with consecutive (progressive) deadlines. One example is server-side scheduling for video service, where clients request flows of content from a server with limited capacity, and any content not delivered by its deadline is lost. We consider the simultaneous goals of 1) minimizing overall loss, and 2) differentiating loss fractions across classes of flows in proportion to relative weights. State-of-the-art policies, like Discriminatory Processor Sharing and Weighted Fair Queueing, use a fixed static proportional allocation of service rate and fail to achieve both goals. The well-known Earliest Deadline First policy minimizes overall loss, but fails to provide proportional loss across flows, because it treats packets as independent jobs. This paper introduces the Earliest Progressive Deadline First (EPDF) class of policies. We prove that all policies in this broad class minimize overall loss. Furthermore, we demonstrate that many EPDF policies accurately differentiate loss fractions in proportion to class weights, satisfying the second goal.

Optical Network on Chip (ONoC) is a promising technology for the next-generation many-core chip multiprocessors owing to its tremendous advantages in low power consumption, low communication delay, and high bandwidth. In this paper we present WRH-ONoC, a novel wavelength-reused hierarchical architecture that is capable of interconnecting thousands of cores using a limited number of wavelengths while providing extremely high-throughput data communication between connected cores. In WRH-ONoC, the cores are divided into small subsystems that are interconnected using multiple λ-routers and gateways in a hierarchical manner. Each λ-router can provide non-blocking parallel communication among the directly connected cores or gateways, and all λ-routers can reuse the limited number of available wavelengths. Communications between cores in different subsystems are routed via gateways in which optical signals can change their wavelengths via optical-electrical signal conversions. For a given number of cores, we give the minimum number of levels, λ-routers, and gateways required to interconnect these cores, and derive the expected end-to-end data communication delay under the Uniform-Poisson traffic pattern. Both theoretical analysis and simulation results demonstrate that WRH-ONoC can achieve significant improvement on performance and reduction on hardware cost in comparison with the existing solutions.

The potential of crowdsourcing for complex problem solving has been revealed by smartphones. Nowadays, vehicles have also been increasingly adopted as participants in crowd-sourcing applications. Different from smartphones, vehicles have the distinct advantage of predictable mobility, which brings new insight into improving the crowdsourcing quality. Unfortunately, utilizing the predictable mobility in participant recruitment poses a new challenge of considering not only current location but also the future trajectories of participants. Therefore, existing participant recruitment algorithms that only use the current location may not perform well. In this paper, based on the predicted trajectory, we present a new participant recruitment strategy for vehicle-based crowdsourcing. This strategy guarantees that the system can perform well using the currently recruited participants for a period of time in the future. The participant recruitment problem is proven to be NP-complete, and we propose two algorithms, a greedy approximation and a genetic algorithm, to find the solution for different application scenarios. The performance of our algorithms is demonstrated with traffic trace dataset. The results show that our algorithms outperform some existing approaches in terms of the crowdsourcing quality.

We consider a new type of distinct element counting problem in dynamic data streams, where (1) insertions and deletions of an element can appear not only in the same data stream but also in two or more different streams, (2) a deletion of a distinct element cancels out all the previous insertions of this element, and (3) a distinct element can be re-inserted after it has been deleted. Our goal is to count the number of distinct elements that were inserted but have not been deleted in a continuous data stream. We also solve this new type of distinct element counting problem in a distributed setting. This problem is motivated by several network monitoring and attack detection applications where network traffic can be modelled as single or distributed dynamic streams and the number of distinct elements in the data streams, such as unsuccessful TCP connection setup requests, is calculated to be used as an indicator to detect certain network events such as service outage and DDoS attacks. Although there are known tight bounds for distinct element counting in insertion-only data streams, no good bounds are known for it in dynamic data streams, neither for this new type of problem. None of the existing solutions for distinct element counting can solve our problem. In this paper, we will present the first solution to this problem, using a space-bounded data structure with a computation-efficient probabilistic data streaming algorithm to estimate the number of distinct elements in single or distributed dynamic data streams. We have done both theoretical analysis and experimental evaluations, using synthetic and real data traces, of our algorithm to show its effectiveness.

With an increasing popularity of real-time applications, such as live chat and gaming, latency prediction between personal devices including mobile devices becomes an important problem. Traditional approaches recover all-pair latencies in a network from sampled measurements using either Euclidean embedding or matrix factorization. However, these approaches targeting static or mean network latency prediction are insufficient to predict personal device latencies, due to unstable and time-varying network conditions, triangle inequality violation and unknown rank of latency matrices. In this paper, by analyzing latency measurements from the Seattle platform, we propose new methods for both static latency estimation as well as the dynamic estimation problem given 3D latency matrices sampled over time. We propose a distance-feature decomposition algorithm that can decompose latency matrices into a distance component and a network feature component, and further leverage the structured pattern inherent in the 3D sampled data to increase estimation accuracy. Extensive evaluations driven by real-world traces show that our proposed approaches significantly outperform various state-of-the-art latency prediction techniques.

Dynamic spectrum access is the key to solving worldwide spectrum shortage. The open wireless medium subjects DSA systems to unauthorized spectrum use by illegitimate users. This paper presents SpecGuard, the first crowdsourced spectrum misuse detection framework for DSA systems. In SpecGuard, a transmitter is required to embed a spectrum permit into its physical-layer signals, which can be decoded and verified by ubiquitous mobile users. We propose three novel schemes for embedding and detecting a spectrum permit at the physical layer. Detailed theoretical analyses, MATLAB simulations, and USRP experiments confirm that our schemes can achieve correct, low-intrusive, and fast spectrum misuse detection.

This paper initiates the study of distributed information exchange in multi-channel wireless ad hoc networks. Information exchange is a basic operation in which each node of the network sends an information packet to other nodes within a specific distance R. Our study is motivated by the increasing presence and popularity of wireless networks and devices that operate on multiple channels. Consequently, there is a need for a better understanding of how and by how much multiple channels can improve communication. Based on the SINR interference model, we propose a multi-channel network model which incorporates certain features commonly seen in wireless ad hoc networks, including asynchrony, little non-local knowledge, limited message size, and limited power control. We then present a randomized algorithm that can accomplish information exchange in O ((Δ/F + Δlog n/P) log n + log Δ log n) timeslots with high probability, where n is the number of nodes in the network, Δ is the maximum number of nodes within the range R, F is the number of available channels and P is the maximum number of packets that can fit in a message. Our algorithm significantly surpasses the best known results in single-channel networks, achieving a Θ(F) times speedup if Δ and P are sufficiently large. We conducted empirical studies that confirmed the performance of the proposed algorithm as derived in the analysis.

This paper presents Pop-Forecast, a systematic method for accurately forecasting the popularity of videos promoted through social networks. Pop-Forecast aims to optimize the forecasting accuracy and the timeliness with which forecasts are issued, by explicitly taking into account the dynamic propagation of videos in social networks. The forecasting is performed online and requires no training phase or a priori knowledge. We analytically bound the performance loss of Pop-Forecast as compared to that obtained by an omniscient oracle and prove that the bound is sublinear in the number of video arrivals, thereby guaranteeing its fast rate of convergence as well as its asymptotic convergence to the optimal performance. We validate the performance of Pop-Forecast through extensive experiments using real-world data traces collected from the videos shared in RenRen, one of the largest online social networks in China. These experiments show that our proposed method outperforms existing approaches for popularity prediction (which do not take into account the propagation in social network) by more than 30% in terms of prediction rewards.