INFOCOM 2016 论文列表

Whenever our smartphones have their WiFi radio interface on, they periodically try to connect to known wireless APs (networks the user has connected to in the past). This is done through WiFi Probe requests - special wireless frames that contain the MAC address of the sending device and, in most of the cases, the human-readable name-string (SSID) of the known AP. This semantic information, inherent to the network protocol, is sent in the clear and, if sniffed, can help discover important information and phenomena of people and human nature that have nothing to do with technology. In this paper we present the idea of exploiting WiFi probe requests to de-anonymize the origin of participants in large events. We make use of several, publicly available datasets containing more than 11M of probe requests collected in scenarios that are of citywide, national (two political meetings), and international religion-related relevance. We show how, by exploiting the semantic information brought by the relative WiFi probes, we are able to discover with high accuracy the provenance of the crowds in each event. In particular, the de-anonymization outcome of the two political meetings held few days before the election days in Italy match surprisingly well the official voting results reported for the two respective parties.

Crowdsourcing is a crowd-based outsourcing, where a requester (task owner) can outsource tasks to workers (public crowd). Recently, mobile crowdsourcing, which can leverage workers' data from smartphones for data aggregation and analysis, has attracted much attention. However, when the data volume is getting large, it becomes a difficult problem for a requester to aggregate and analyze the incoming data, especially when the requester is an ordinary smartphone user or a start-up company with limited storage and computation resources. Besides, workers are concerned about their identity and data privacy. To tackle these issues, we introduce a three-party architecture for mobile crowdsourcing, where the cloud is implemented between workers and requesters to ease the storage and computation burden of the resource-limited requester. Identity privacy and data privacy are also achieved. With our scheme, a requester is able to verify the correctness of computation results from the cloud. We also provide several aggregated statistics in our work, together with efficient data update methods. Extensive simulation shows both the feasibility and efficiency of our proposed solution.

Modern data centres provide large aggregate network capacity and multiple paths among servers. Traffic is very diverse; most of the data is produced by long, bandwidth hungry flows but the large majority of flows, which commonly come with strict deadlines regarding their completion time, are short. It has been shown that TCP is not efficient for any of these types of traffic in modern data centres. More recent protocols such MultiPath TCP (MPTCP) are very efficient for long flows, but are ill-suited for short flows. In this paper, we present Maximum MultiPath TCP (MMPTCP), a novel transport protocol which, compared to TCP and MPTCP, reduces short flows' completion times, while providing excellent goodput to long flows. To do so, MMPTCP runs in two phases; initially, it randomly scatters packets in the network under a single congestion window exploiting all available paths. This is beneficial to latency-sensitive flows. After a specific amount of data is sent, MMPTCP switches to a regular MultiPath TCP mode. MMPTCP is incrementally deployable in existing data centres as it does not require any modifications outside the transport layer and behaves well when competing with legacy TCP and MPTCP flows. Our extensive experimental evaluation in simulated FatTree topologies shows that all design objectives for MMPTCP are met.

In wireless sensor networks, Virtual Backbone (VB) construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Transmission ranges of sensors are not always equivalent. A sensor networks is modeled as a directed graph while sensors have different transmission ranges. In this paper, we will try to find a special Strongly Connected Bidirectional Dominating Set (SCBDS) within minimum routing cost for each pair of nodes in directed graphs. The SCBDS forms a VB of the networks whose sensors have different transmission radius. For any pair of sensors, the length of the shortest path they communicate with each other through VB should be no more than a constant times the length of the shortest path without using VB. We propose a constant approximate scheme to construct the SCBDS with the bounded size 3*(8ρ+1)2(2ρ+1)2/2 opt. A centralized and a distributed algorithm with the same performance ratio are presented to show the details to construct the SCDS in directed graphs. Simulation results show that the average shortest path length through our algorithms is reduced greatly compared with other algorithms.

In this paper, we are interested in online multistage decisions to ensure robust power grid operations under high renewable uncertainty. We jointly consider both the reliability assessment commitment (RAC) and the real-time dispatch problems. We first focus on the real-time dispatch problem and define “maximally robust algorithms,” which can provably ensure grid safety whenever there exists any other algorithm that can ensure grid safety under the same level of future uncertainty. We characterize a class of maximally robust algorithms using the concept of “safe dispatch set,” which also provides conditions for verifying grid safety for RAC. However, in general such safe dispatch sets may be difficult to compute. We then develop efficient computational algorithms for characterizing the safe dispatch sets. Specifically, for a simpler single-bus two-generator case, we show that the safe dispatch sets can be exactly characterized by a polynomial number of convex constraints. Then, based on this two-generator characterization, we develop a new solution for the multi-bus multi-generator case using the idea of virtual demand splitting (VDS), which can effectively compute a suitable subset of the safe-dispatch set. Our numerical results demonstrate that a VDS-based economic dispatch algorithm outperforms the standard economic dispatch algorithm in terms of robustness, without sacrificing economy.

As mobile Internet is now indispensable in our daily lives, WiFi's latency performance has become critical to mobile applications' quality of experience. Unfortunately, WiFi hop latency in the wild remains largely unknown. In this paper, we first propose an effective approach to break down the round trip network latency. Then we provide the first systematic study on WiFi hop latency in the wild based on the latency and WiFi factors collected from 47 APs on T university campus for two months. We observe that WiFi hop can be the weakest link in the round trip network latency: more than 50% (10%) of TCP packets suffer from WiFi hop latency larger than 20ms (100ms), and WiFi hop latency occupies more than 60% in more than half of the round trip network latency. To help understand, troubleshoot, and optimize WiFi hop latency for WiFi APs in general, we train a decision tree model. Based on the model's output, we are able to reduce the median latency by 80% from 50ms to 10ms in one real case, and reduce the maximum latency from 250ms to 50ms in another real case.

End-to-end IPv6 performance is a factor that can influence IPv6 adoption. The stability of IPv6 - both in the control and data plane - is an important determinant of end-to-end performance, as it influences packet loss, network latency, and hence application performance. In this paper we compare stability and performance measurements from the control and data plane in IPv6 and IPv4. To study control plane stability, we use BGP feeds from five dual-stacked vantage points to measure routing dynamics towards IPv4 and IPv6 destinations. To study data plane stability, we probe dual-stacked webservers in 629 target ASes to determine the availability, RTT performance and RTT stability of paths toward these targets. In both control and data plane experiments IPv6 exhibited less stability than IPv4. In the control plane, most routing dynamics were generated by a small fraction of pathological unstable prefixes. In the data-plane, episodes of unavailability were longer on IPv6 than on IPv4. We found evidence of correlated performance degradation over IPv4 and IPv6 caused by shared infrastructure.

The increasing traffic demand has become a serious concern for cellular networks. To solve the traffic explosion problem in a vehicular network environment, there have been many efforts to offload the traffic from cellular links to Roadside Units (RSUs). Compared with the cost of downloading from cellular link, downloading through RSUs is considered practically free. In most cases, we have to wait for one or several RSUs to download the entire data, which causing huge delays. However, people can always download data from the cellular network. In reality, people are sensitive to the downloading delay but would like to pay little money for downloading the data. As the result, there exists a delay-cost trade-off. In this paper, we unify the downloading cost and downloading delay as the user's satisfaction. The objective of this paper is to maximize the user's satisfaction. A user will be unsatisfied if they are paying too much for data, or if they wait for a long time. We analyze the optimal solution under the condition that the encountering time between vehicles and RSUs follows the exponential and Gaussian distributions. Generally, we propose an adaptive algorithm. A downloading strategy is made based on the historical encountering situation between the vehicle and multiple RSUs. After a period of time, if the real situation is different with the initial prediction, the data downloading strategy will be correspondingly adjusted. Extensive real-trace driven experiment results show that our algorithm achieves a good performance.

The last decade has seen significant advances in optimization-based resource allocation and control approaches for wireless networks. However, the existing work suffer from poor performance in one or more of the metrics of optimality, delay, and convergence speed. To overcome these limitations, in this paper, we introduce a largely overlooked but highly effective heavy-ball optimization method. Based on this heavy-ball technique, we develop a cross-layer optimization framework that offers utility-optimality, fast-convergence, and significant delay reduction. Our contributions are three-fold: i) we propose a heavy-ball joint congestion control and routing/scheduling framework for both single-hop and multi-hop wireless networks; ii) we show that the proposed heavy-ball method offers an elegant three-way trade-off in utility, delay, and convergence, which is achieved under a near index-type simple policy; and more importantly, iii) our work opens the door to an unexplored network control and optimization paradigm that leverages advanced optimization techniques based on “memory/momentum” information.

Smart grid is characterized by a large number of smart meters (SMs) that exchange huge amounts of data with control center, where an effective communication network is required to guarantee reliable data transmission. In this paper, we introduce software defined network (SDN) technology to the smart grid, which decouples the control plane from the data plane so as to satisfy the communication requirements in the mart grid effectively. Aggregation points (APs) are employed in the data plane to process and forward data between SMs and control center. A general mathematical model is formulated to plan the APs, where we try to minimize the total deployment cost, including the opening expenditure of the APs, the connection cost between SMs and APs, and the connection cost between APs and control center. We present a 5-approximation algorithm to address the generated NP-hard problem, which yields performance-guaranteed solutions. Three representative scenarios are investigated to verity the efficiency of our proposal. Numerical results show that our proposed algorithm has great advantages over other heuristic ones.

Given a set of communication links in cognitive radio networks, assume that the underlying channel state information along each link is unknown; however, we can estimate it by exploiting the feedbacks and evolutions of channel states. Assume time is divided into time-slots. Under the protocol interference model, the opportunistic spectrum scheduling problem aims to select interference-free links to transmit at each time-slot to maximize the average throughput over the long time horizon. Existing works on the opportunistic spectrum scheduling problem cannot satisfyingly address the wireless interference constraints. We apply the framework of restless multi-armed bandit and develop approximation algorithms for the problem with stochastic identical links and nonidentical links respectively. Based on the updated estimations of channel states, the proposed algorithms keep refining future link scheduling decisions. We also obtain approximation bounds of these two proposed algorithms.

The ICT industry has come under criticism as being one of the major energy consumers to exacerbate high global carbon emissions. Meanwhile, using renewable energy to power ICT infrastructure is becoming an attractive solution and is gaining its momentum due to the recent breakthroughs of converting solar and wind energies as power sources at competitive costs. Although significant amounts of fossil fuel based-energy can be saved by allowing network devices (e.g., routers and line-cards) to be set to sleep, this optimization approach comes at a price of degrading routing performance, i.e., the quality of service. This paper addresses the problem of minimizing fossil fuel consumption in large Internet Service Provider (ISP) networks, by utilizing a novel gradient-based routing protocol, which favors forwarding packets along routers powered by the highest quantity of renewable energies. Besides favoring renewable energy, the proposed routing protocol can support putting routers to sleep in order to optimize energy consumption while ensuring a minimum degradation in routing performance. Through our evaluation utilizing real meteorological data, our proposed solution has demonstrated a massive reduction of fossil fuel usage by the network (> 70%) while maintaining the routing performance to a similar level when no energy optimization is applied.

This paper proposes online scheduling policies to optimize quality of experience (QoE) for video-on-demand applications in wireless networks. We consider wireless systems where an access point (AP) transmits video content to clients over fading channels. The QoE of each flow is measured by its duration of video playback interruption. We are specifically interested in systems operating in the heavy-traffic regime. We first consider a special case of ON-OFF channels and establish a scheduling policy that achieves every point in the capacity region under heavy-traffic conditions. This policy is then extended for more general fading channels, and we prove that it remains optimal under some mild conditions. We then formulate a network utility maximization problem based on the QoE of each flow. We demonstrate that our policies achieve the optimal overall utility when their parameters are chosen properly. Finally, we compare our policies against three popular policies. Simulation results validate that the proposed policy indeed outperforms existing policies.

With the rise of Software Defined Networks (SDN), there is growing interest in dynamic and centralized traffic engineering, where decisions about forwarding paths are taken dynamically from a network-wide perspective. Frequent path reconfiguration can significantly improve the network performance, but should be handled with care, so as to minimize disruptions that may occur during network updates. In this paper we introduce Time4, an approach that uses accurate time to coordinate network updates. We characterize a set of update scenarios called flow swaps, for which Time4 is the optimal update approach, yielding less packet loss than existing update approaches. We define the lossless flow allocation problem, and formally show that in environments with frequent path allocation, scenarios that require simultaneous changes at multiple network devices are inevitable. We present the design, implementation, and evaluation of a time4-enabled OpenFlow prototype. The prototype is publicly available as open source. Our work includes an extension to the OpenFlow protocol that has been adopted by the Open Networking Foundation (ONF), and is now included in OpenFlow 1.5. Our experimental results demonstrate the significant advantages of Time4 compared to other network update approaches.

Today, given data center networks' sizes and bursty workloads, it is likely that at any moment there is packet loss due to some type of failure in the network. This paper focuses on solving the two most common types of data center network failures: congestion and routing failures. Recently, there has been demand for lossless Ethernet (DCB) in data center networks as a solution to congestion failures. However, DCB complicates fault tolerance by introducing a new type of failure, deadlock. If DCB is enabled, then all routing must be deadlock free. To the best of our knowledge, this paper describes the first ever deadlock-free approaches to local fast failover that can be combined with DCB, DF-FI and DF-EDST resilience. Moreover, in the evaluation, this paper shows that DF-EDST resilience, which is the paper's main contribution, can improve fault tolerance without adversely impacting performance when compared to a state-of-the-art approach to deadlock-free routing. If, however, a small reduction in aggregate throughput is acceptable, then it is possible to build routes such that only 0.00001% of the total flows in the network are likely to fail given 16 edge failures on networks with 1K-4K hosts.

In this paper, we propose a structural importance-aware approach to quantify the vulnerability/de-anonymizability of graph data to structure-based De-Anonymization (DA) attacks [1][2][3][4]. Specifically, we quantify both the seed-based and the seed-free Relative De-anonymizability (RD) of graph data for both perfect DA (successfully de-anonymizing all the target users) and partial DA (where some DA error is tolerated) under a general data model. In our relative quantification, instead of treating all the users in graph data as structurally equivalent, we adaptively quantify their RD in terms of their structural importance. Leveraging 15 real world graph datasets, we validate the accuracy of our relative quantifications and compare them with state-of-the-art seed-based and seed-free quantification techniques. The results demonstrate that our structural importance-aware relative quantifications are more sound and precise when measuring graph data's real vulnerability/de-anonymizability.

Predicting the future location of users in wireless networks has numerous applications, and can help service providers to improve the quality of service perceived by their clients. The location predictors proposed so far estimate the next location of a specific user by inspecting the past individual trajectories of this user. As a consequence, when the training data collected for a given user is limited, the resulting prediction is inaccurate. In this paper, we develop cluster-aided predictors that exploit past trajectories collected from all users to predict the next location of a given user. These predictors rely on clustering techniques and extract from the training data similarities among the mobility patterns of the various users to improve the prediction accuracy. Specifically, we present CAMP (Cluster-Aided Mobility Predictor), a cluster-aided predictor whose design is based on recent non-parametric Bayesian statistical tools. CAMP is robust and adaptive in the sense that it exploits similarities in users' mobility only if such similarities are really present in the training data. We analytically prove the consistency of the predictions provided by CAMP, and investigate its performance using two large-scale datasets. CAMP significantly outperforms existing predictors, and in particular those that only exploit individual past trajectories.

Energy awareness of mobile devices with limited battery capacity can be achieved by embedding battery drain rate monitoring capability into the devices. With Li-ion battery, battery drain rate varies with temperature and battery aging, since they affect battery characteristics such as capacity and internal resistance. We develop BattTracker, an algorithm to estimate battery drain rate without knowing the exact capacity and internal resistance by incorporating the concept of effective resistance. BattTracker tracks the instantaneous battery drain rate with up to 0.5 second time granularity. Extensive evaluation with smartphones demonstrates that BattTracker accurately estimates the battery drain rate with less than 5% estimation error, thus enabling energy-aware operation of smartphones with finegrained time granularity. To the best of our knowledge, this is the first effort to estimate the instantaneous battery drain rate by considering both temperature and aging effects on the battery characteristics.

Public transport in suburban cities (covers 80% of the urban landscape) of developing regions suffer from the lack of information in Google Transit, unpredictable travel times, chaotic schedules, absence of information board inside the vehicle. Consequently, passengers suffer from lack of information about the exact location where the bus is at present as well as the estimated time to be taken to reach the desired destination. We find that off-the-shelf deployment of existing (non-GPS) localization schemes exhibit high error due to sparsity of stable and structured outdoor landmarks (anchor points). Through rigorous experiments conducted over a month however, we realize that there are a certain class of volatile landmarks which may be useful in developing efficient localization scheme. Consequently, in this paper, we design a novel generalized energy-efficient outdoor localization scheme - UrbanEye, which efficiently combines the volatile and non-volatile landmarks using a specialized data structure, the probabilistic timed automata. UrbanEye uses speed-breakers, turns and stops as landmarks, estimates the travel time with a mean accuracy of ±2.5 mins and produces a mean localization accuracy of 50 m. Results from several runs taken in two cities, Durgapur and Kharagpur, reveal that UrbanEye provides more than 50% better localization accuracy compared to the existing system Dejavu [1], and consumes significantly less energy.