INFOCOM 2019 论文列表

This paper considers the fundamental problem of Placement of unmanned Aerial vehicles achieviNg 3D Directional cover Age (PANDA), that is, given a set of objects with determined positions and orientations in a 3D space, deploy a fixed number of UAVs by adjusting their positions and orientations such that the overall directional coverage utility for all objects is maximized. First, we establish the 3D directional coverage model for both cameras and objects. Then, we propose a Dominating Coverage Set (DCS) extraction method to reduce the infinite solution space of PANDA to a limited one without performance loss. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint, and present a greedy algorithm with 1 -1 /e approximation ratio to address this problem. We conduct simulations and field experiments to evaluate the proposed algorithm, and the results show that our algorithm outperforms comparison ones by at least 75.4%.

In this paper, we develop an optimization decomposition framework for cache management under “BIG” cache abstraction which fully utilizes the cache resources in a cache network. We assign a utility function to each content, and formulate a joint optimization problem to maximize the overall utility of a cache network. We show that this global network utility maximization problem can be decomposed into two sub-problems, the cache allotment problem and object placement problem, which can be solved separately and iteratively. This decoupling enables us to separately optimize the performance objectives from the perspectives of content providers, cache network operators, and users. We provide exact solution to the object placement problem with Poisson and Pareto request interarrival distributions. We also devise a primal-dual algorithm for online content management. We conduct extensive numerical analysis and simulations to evaluate the performance of our optimization decomposition framework, and study the impact of various key factors such as hazard rate functions of the request interarrival distributions and object popularities. We show that our optimization decomposition framework outperform existing heuristic methods.

Fast detection of heavy flows (e.g., heavy hitters and heavy changers) in massive network traffic is challenging due to the stringent requirements of fast packet processing and limited resource availability. Invertible sketches are summary data structures that can recover heavy flows with small memory footprints and bounded errors, yet existing invertible sketches incur high memory access overhead that leads to performance degradation. We present MV-Sketch, a fast and compact invertible sketch that supports heavy flow detection with small and static memory allocation. MV-Sketch tracks candidate heavy flows inside the sketch data structure via the idea of majority voting, such that it incurs small memory access overhead in both update and query operations, while achieving high detection accuracy. We present theoretical analysis on the memory usage, performance, and accuracy of MV-Sketch. Trace-driven evaluation shows that MVSketch achieves higher accuracy than existing invertible sketches, with up to 3.38× throughput gain. We also show how to boost the performance of MV-Sketch with SIMD instructions.

Visible Light Communication (VLC) systems relying on commercial-off-the-shelf (COTS) devices have gathered momentum recently, due to the pervasive adoption of LED lighting and mobile devices. However, the achievable throughput by such practical systems is still several orders below those claimed by controlled experiments with specialized devices. In this paper, we engineer SynLight aiming to significantly improve the data rate of a practical VLC system. SynLight adopts COTS LEDs as its transmitter, but it innovates in its simple yet delicate driver circuit wiring an array of LED chips in a combinatorial manner. Consequently, modulated signals can directly drive the on-off procedures of individual chip groups, so that the spatially synthesized light emissions exhibit a varying luminance following exactly the modulation symbols. To obtain a readily usable receiver, SynLight interfaces a COTS Photo-Diode with a smartphone through the audio jack. The evaluations on SynLight are both promising and informative: they demonstrate a throughput up to 60 kbps, more than 50× of that achieved by state-of-the-art systems, while suggesting various potentials to further enhance the performance.

Leading cloud providers recently introduced a new instance type named burstable instances to better match the time-varying workloads of tenants and further reduce their costs. In the research community, however, little has been done to understand burstable instances from a theoretical perspective. This paper presents the first unified framework to model, analyze, and optimize the operation of burstable instances. Specifically, we model the resource provisioning of burstable instances in different service classes, identify key performance metrics, and derive the performance given the resource provisioning decisions. We then characterize the equilibrium behind tenants' responses to the prices offered for different burstable instance service classes, taking into account the impact of tenants' actions on the performance achieved by each service class. In addition, we investigate how a cloud provider can leverage the knowledge of this equilibrium to find the prices that maximize its total revenue. Finally, we validate our framework on real traces and demonstrate its usage to price a public cloud.

The IT infrastructure of large organizations consists of devices and software services purchased from multiple vendors. The problem of measuring the quality of service (QoS) of each of these vendor devices (and services) is challenging since the vendors may tamper with the measurements for monetary benefits or saving debugging efforts. Existing solutions for QoS measurement in trusted environments cannot be extended for this problem since the vendors can easily circumvent them. Solutions borrowed from other areas such as client-server QoS measurement do not help either since they incur unreasonable storage and network overheads, or require extensive modifications to the packet headers. In this paper, we propose the Measuring Tape scheme, comprised of (1) a novel data structure called evidence Bloom filter (e-BF) that can be deployed at the vendor devices (and services), and (2) unique querying techniques, which can be used by the administrator to query the e-BF to measure QoS. While e-BF uses storage and computational resources judiciously, the querying techniques ensure resilience to adversarial behavior. We evaluate our solution based on a few real-world and synthetic traces and with different adversaries. Our results highlight the trade-off between resources (i.e., storage and computation) and the accuracy of QoS predictions, as well as its implications on security. We also present an analytical model of e-BF that establishes the relationship between storage, prediction accuracy, and security. Further, we present security arguments to illustrate how our solution thwarts adversarial attempts to tamper QoS.

Wireless sensor-actuator networks enable an efficient and cost-effective approach for industrial sensing and control applications. To satisfy the real-time requirement of such applications, these networks adopt centralized scheduling algorithms to optimize the real-time performance based on global information. Existing centralized algorithms mostly focus on scheduling time-triggered flows. They cannot effectively schedule event-triggered flows due to the dynamics and unpredictability of events. In this paper, we propose three fundamental centralized algorithms that reserve as few resources as possible for event-triggered flows such that the real-time performance of time-triggered flows is not affected. We then analyze their advantages and disadvantages. Based on the analysis, we combine their advantages, including those in terms of their resource requirements, into a centralized algorithm. Finally, we conduct extensive simulations based on both real topologies and random topologies. The simulations indicate that for most test cases the schedulability of our combined algorithm is close to optimal solutions.

Visible light positioning (VLP) is a promising direction for indoor localization. VLP depends on Visible light communication (VLC) to receive location anchors sent by light bulbs. In order to decode high-frequency VLC signals, today's VLP systems require the receiver to equip either rolling shutter cameras or high-frequency light sensors, which bring considerable overhead or are even unavailable on many mobile devices. This paper introduces ALS-P, a lightweight VLP approach which only requires the commercially widely available ambient light sensor (ALS). ALS is conventionally not treated as a feasible VLC receiver as its sampling rate is far less than that of VLC signals. Our basic idea is to leverage the property of frequency aliasing. Through dynamically adjusting the sampling rate of the ALS sensor, the down-converted signals can be uniquely distinguished. To realize this idea, we propose novel designs to address challenges which stem from ALS hardware, high-order light aliasing, and environmental interference cancellation. Besides, ALS can also enable a lightweight VLC via changing LED frequencies. We implement the ALS-P on commercial LED bulbs and the ALS of existing smartphones. The evaluation shows that the ALSP can enable robust and efficient LED frequency decoding with at least 4LEDs bulbs in practical scenarios. As a result, ALS-P can enable VLC at a data rate of 5bit/s per each LED bulb and achieve a sub-meter level indoor localization accuracy.

This paper uses Poisson geometry to define a power control mechanism for large mobile ad hoc networks. It considers a homogeneous Poisson bipole network on the Euclidean plane. Bipoles, which represent transmitter-receiver pairs, adapt their power in a local and distributed way. The common aim of the bipoles is to maximize network wide proportional fairness. The mechanism is based on a heuristic which consists of simplifying the interference field seen by each receiver to its dominant term. This max-interference approximation decomposes the global (and infinite dimensional) optimization problem into a collection of finite problems involving the so called descending chains of the Poisson nearest neighbor graph. In addition, in the Rayleigh fading and interference limited case, the problem further factorizes into a collection of pairwise optimization problems with closed form solution. The properties of this power control mechanism are studied both analytically and by discrete event simulation. Significant performance gains are seen despite these approximations, for the motivating metric and other metrics.

Despite years of research attention, localization-based indoor navigation has not found wide-spread practical use, largely due to the high burden on deployment and bootstrapping. Lightweight peer-to-peer navigation systems that use a leader-follower model have recently been proposed to alleviate these burdens. However, typical peer-to-peer navigation suffers from poor scalability and flexibility as navigation is only possible over pre-collected leader paths. In this paper, we present FollowUs, an easily-deployable (bootstrap-free) and scalable indoor navigation system. In addition to robust navigation through real-time trace-following, FollowUs integrates cloud services to process and combine traces at large scale. Optionally, it can also leverage floor plans to further enhance navigation efficiency. We design and implement FollowUs, including mobile app and cloud services. Experimental results from a company-internal beta release show that 91% of FollowUs' spatial errors on reaching destinations to be 3m or less, and 95% of navigation instructions are shown to users within a 4-step error margin during navigation.

Diverse anonymous communication systems are widely deployed as they can provide the online privacy protection and Internet anti-censorship service. However, these systems are severely abused and a large amount of anonymous traffic is malicious. To mitigate this issue, we propose a novel and practical traceback technique to confirm the communication relationship between the suspicious server and the user. We leverage the software-defined network (SDN) switch at a destination server side to intercept target traffic towards the server and alter the advertised TCP window sizes so as to stealthily vary the traffic rate at the server. By carefully varying the traffic rate, we can successfully modulate a secret signal into the traffic. The traffic carrying the signal passes through the anonymous communication system and reaches the SDN switch at the user side. Then we can detect the modulated signal from the traffic so as to confirm the communication relationship between the server and the user. To validate the feasibility and effectiveness of our technique, extensive real-world experiments are performed using three popular anonymous communication systems, i.e., SSH tunnel, OpenVPN tunnel, and Tor. The results demonstrate that the detection rates approach 100% for SSH and Open VPN and 95% for Tor while the false positive rates are significantly low, approaching 0% for these three systems.

Searchable encryption (SE) is a practical crypto-graphic primitive to build encrypted databases. Recently there has been much attention in leakage-abuse attacks against SE. Among others, attacks based on inference of keyword frequency can easily identify query keywords from the access pattern, i.e., query results. To mitigate these attacks, database padding is considered as a conceptually simple yet effective counter-measure. Unfortunately, none of the existing studies formally understand the relationship between padding security strength and its overhead. Also, how to craft padding is not restricted in current countermeasures, where bogus files are likely to be distinguishable from real ones. In this paper, we propose an information theory based framework to analyse the security strength under certain padding overhead. First, we leverage relative entropy to measure the “closeness” between the distributions of the original dataset and padded dataset. Second, we quantity the attack efforts against padding countermeasures by entropy analysis. Apart from theoretical findings, we further devise an algorithm via outlier detection for padding generation, which considers both the padded dataset distribution and the similarity between real and bogus files. Evaluations on a real-world dataset confirm our theoretical results and demonstrate the efficiency and effectiveness of our proposed padding generation algorithm.

We consider the problem of timely exchange of updates between a central station and a set of ground terminals$V$, via a mobile agent that traverses across the ground terminals along a mobility graph$G = (V, E)$. We design the trajectory of the mobile agent to minimize average-peak and average age of information (AoI), two recently proposed metrics for measuring timeliness of information. We consider randomized trajectories, in which the mobile agent travels from terminal$i$to terminal$j$with probability$P_{i,j}$. For the information gathering problem, we show that a randomized trajectory is average-peak age optimal and factor-$8\mathcal {H}$average age optimal, where$\mathcal {H}$is the mixing time of the randomized trajectory on the mobility graph$G$. We also show that the average age minimization problem is NP-hard. For the information dissemination problem, we prove that the same randomized trajectory is factor-$O(\mathcal {H})$average-peak and average age optimal. Moreover, we propose an age-based trajectory, which utilizes information about current age at terminals, and show that it is factor-2 average age optimal in a symmetric setting.

While Narrow-Band Internet of Things (NB-IoT) has been standardized by 3GPP to provide wireless Internet access for IoT devices, this service is expected to come with a monthly fee (e.g., $1 or $2 per month per device). As the number of IoT devices tends to be large, the service charge will impose a considerable financial burden on the end users. In this paper, we propose an Energy-Efficient IoT (EE-IoT) communication scheme by taking advantage of the existing WiFi infrastructure that is widely available in home, office, campus, and city environments. EE-IoT will not only avoid monthly service charge for the end users but also maintain a low power consumption for IoT devices. The key component of EE-IoT is an asymmetric physical (PHY) design, which enables an OFDM-based broadband AP to communicate with multiple QAM-based narrowband IoT devices at a low sampling rate (250 ksps) in both uplink and downlink. The trick in our design is that, instead of using the same carrier frequency as the AP, each IoT device tunes its carrier frequency to a particular subcarrier of the AP's OFDM signal, making it possible to encode/decode the data on that subcarrier at a low sampling rate. Based on this new PHY, we propose a MAC protocol to enable EE-IoT in WLANs. We have built a prototype of EE-IoT on a USRP2 wireless testbed and evaluated its performance in an office building environment. Experimental results show that an AP can serve 24 IoT devices simultaneously and each IoT device can achieve more than 187 kbps in the downlink and more than 125 kbps in the uplink.

Respiration rate monitoring is beneficial for the diagnosis of a variety of diseases, such as heart failure and sleep disorders. Radio Frequency (RF) based respiration rate monitoring systems, namely ultra-wideband radar and COTS device, have been proposed without requiring any direct contact with the detected person. However, existing RF based systems either require expensive UWB radio (radar based) or work only in stationary environments (COTS device based). To address the limitations of both radar based and COTS device based systems, in this paper, we propose RespiRadio, a system that can detect a person's respiration rate in dynamic ambient environments via a single TX-RX pair of WiFi cards. The key novelty of RespiRadio is that it overcomes the limit of existing COTS device based respiration rate systems by synthesizing a wider-bandwidth WiFi radio. With the synthesized WiFi radio, we can identify the path reflected by the breathing person and then analyze the periodicity of the signal power measurements only from this path to infer the respiration rate. We experimentally evaluate the performance of RespiRadio in non-static indoor environments and the results demonstrate that the overall estimation error is 0.152 breaths per minute (bpm).

Network utility maximization (NUM) is an iconic problem in network traffic management which is at the core of many current and emerging network design paradigms - and, in particular, software-defined networks (SDNs). Thus, given the exponential growth of modern-day networks (in both size and complexity), it is crucial to develop scalable algorithmic tools that are capable of providing efficient solutions in time which is dimension-free, i.e., independent-or nearly-independent-on the size of the system. To do so, we leverage a suite of modified gradient methods known as “mirror descent” and we derive a scalable and efficient algorithm for the NUM problem based on gradient exponentiation. We show that the convergence speed of the proposed algorithm only carries a logarithmic dependence on the size of the network, so it can be implemented reliably and efficiently in massively large networks where traditional gradient methods are prohibitively slow. These theoretical results are sub-sequently validated by extensive numerical simulations showing an improvement of several order of magnitudes over standard gradient methods in large-scale networks.

The formation of consortiums of a broadband access Internet Service Provider (ISP) and multiple Content Providers (CP) is considered for large-scale content caching. The consortium members share costs from operations and investments in the supporting infrastructure. Correspondingly, the model's cost function includes marginal and fixed costs; the latter has been important in determining industry structure. Also, if Net Neutrality regulations permit, additional network capacity on the ISP's last mile may be contracted by the CPs. The number of subscribers is determined by a combination of users' price elasticity of demand and Quality of Experience. The profit generated by a coalition after pricing and design optimization determines the game's characteristic function. Coalition formation is by a bargaining procedure due to Okada (1996) based on random proposers in a non-cooperative, multi-player game-theoretic framework. A necessary and sufficient condition is obtained for the Grand Coalition to form, which bounds subsidies from large to small contributors. Hence, for the Grand Coalition to form it is necessary to administer Coalition Admission Control. Caching is generally supported even under Net Neutrality regulations. The Grand Coalition's profit matches upper bounds. Numerical results illustrate the analytic results.

In this paper, we generally formulate the dynamics prediction problem of various network systems (e.g., the prediction of mobility, traffic and topology) as the temporal link prediction task. Different from conventional techniques of temporal link prediction that ignore the potential non-linear characteristics and the informative link weights in the dynamic network, we introduce a novel non-linear model GCN-GAN to tackle the challenging temporal link prediction task of weighted dynamic networks. The proposed model leverages the benefits of the graph convolutional network (GCN), long short-term memory (LSTM) as well as the generative adversarial network (GAN). Thus, the dynamics, topology structure and evolutionary patterns of weighted dynamic networks can be fully exploited to improve the temporal link prediction performance. Concretely, we first utilize GCN to explore the local topological characteristics of each single snapshot and then employ LSTM to characterize the evolving features of the dynamic networks. Moreover, GAN is used to enhance the ability of the model to generate the next weighted network snapshot, which can effectively tackle the sparsity and the wide-value-range problem of edge weights in real-life dynamic networks. To verify the model's effectiveness, we conduct extensive experiments on four datasets of different network systems and application scenarios. The experimental results demonstrate that our model achieves impressive results compared to the state-of-the-art competitors.

This paper studies jamming-resilient distributed backbone construction in multi-hop wireless networks. Specifically, a strong adversarial jamming model is proposed that captures the general jamming phenomena suffered by wireless communications. The jamming model is based on the realistic Signal-to-Interference-plus-Noise-Ratio (SINR) interference model, and is featured by local-uniformity, unrestricted energy budget and reactivity, which covers more jamming scenarios and is much closer to reality than existing jamming models. Under the strong adversarial jamming model, we propose a randomized distributed algorithm that can construct a backbone in J(O(log n + logR)) rounds with high probability, where J(O(log n + log R)) is the number of rounds in the interval from the beginning of the algorithm execution that contains O(log n + log R) unjammed rounds for every node. This result is asymptotically optimal considering the trivial lower bound of Ω(log n) for a successful transmission even without interference and jamming.