INFOCOM 2018 论文列表

This paper proposes a network architecture and supporting optimization framework that allows Unmanned Aerial Vehicles (UAVs) to perform city-scale video monitoring of a set of Points of Interest (PoI). Our approach is systems-driven, relying on experimental studies to identify the permissible number of hops for multi-UAV video relaying in a noisy 3-D environment. Our architecture itself is innovative in the sense that it defines a mathematical framework for selecting the UAVs for periodic re-charging by landing on public transportation buses, and then `riding' the bus to the successive chosen Pol. Specifically, we show that our UAV scheduler can be modeled as an instance of multicommodity flow problems, and mathematically solved through Mixed Integer Linear Programming (MILP) techniques. Thus, our centralized formulation identifies the UAV, the next bus, and the next PoI, given the information about energy thresholds, the bus routes in the city and their next arrival times, to ensure persistent and reliable video coverage of all PoIs in the city. Finally, our work is validated via emulation of a city environment with live traffic updates from a real bus transportation network.

Bloom filters and their variants are widely used as space efficient probabilistic data structures for representing set systems and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications a common engineering solution is to set the false positive rate very small, and ignore the existence of the very unlikely false positive answers. This paper is devoted to close the gap between the two design concepts of unlikely and not having false positives. We propose a data structure, called EGH filter, that supports the Bloom filter operations and besides it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false positive free zone of a filter and generalize the filter to support listing of the elements. We evaluate the performance of the filter in comparison with the traditional Bloom filters. Our data structure is based on recently developed combinatorial group testing techniques.

Mining user behaviors over high speed links is important for applications such as network anomaly detection. Previous work focuses on monitoring anomalies such as extremely frequent users occurring in a short timeslot such as 1 minute. Little attention has been paid to detect users with stealthy behaviors such as persistent frequent and co-occurrence behaviors over a long period of time at the timeslot granularity (e.g., 1 minute granularity level). Unlike frequent users, persistent users do not necessarily occur more frequently than other users in a single timeslot, but persist and occur in a larger number of timeslots. Due to limited computation and storage resources on routers, it is prohibitive to collect massive network traffic in a long period of time. We develop an end-to-end method for solving challenges in both long-term online traffic collection and offline user behavior analysis. To achieve this goal, we design a user embedding (UE) method to fast build compact sketches of user-occurrence events over time. To reduce the estimation error introduced by Bloom Filter, we model UE as a sampling method and propose methods to accurately mine a variety of user behaviors from user-occurrence events rebuilt from UE sketches. In addition, we introduce another new embedding method reversible UE (RUE) to detect persistent frequent behaviors when monitored users' IDs are not given in advance for offline analysis. We conduct extensive experiments on real-world traffic, and the results demonstrate that our methods significantly outperform state-of-the-art methods.

Millimeter-wave (mmWave) communication is a promising technology to cope with the expected exponential increase in data traffic in 5G networks. mmWave networks typically require a very dense deployment of mmWave base stations (mmBS). To reduce cost and increase flexibility, wireless backhauling is needed to connect the mmBSs. The characteristics of mmWave communication, and specifically its high directionality, imply new requirements for efficient routing and scheduling paradigms. We propose an efficient scheduling method, so-called schedule-oriented optimization, based on matching theory that optimizes QoS metrics jointly with routing. It is capable of solving any scheduling problem that can be formulated as a linear program whose variables are link times and QoS metrics. As an example of the schedule-oriented optimization, we show the optimal solution of the maximum throughput fair scheduling (MTFS). Practically, the optimal scheduling can be obtained even for networks with over 200 mmBSs. To further increase the runtime performance, we propose an efficient edge-coloring based approximation algorithm with provable performance bound. It achieves over 80% of the optimal max-min throughput and runs 5 to 100 times faster than the optimal algorithm in practice. Finally, we extend the optimal and approximation algorithms for the cases of multi-RF-chain mmBSs and integrated backhaul and access networks.

Many large-scale compute-intensive and mission-critical online service applications are being deployed on geo-distributed datacenters, which require transfers of bulk business data over Wide Area Networks (WANs). The bulk transfers are often associated with different requirements on deadlines, either a complete transfer before a hard deadline or a best-effort delivery within a soft deadline. In this paper, we study the online bulk transfer problem over inter-datacenter WANs, while taking into consideration the requests with a mixture of hard and soft deadlines. We use Linear Programming (LP) to mathematically formulate the problem with the objective of maximizing a system utility represented by the service provider's revenue, taking into account the revenue earned from deadline-met transfers and the penalty paid for deadline-missed ones. We propose an online framework to efficiently manage mixed bulk transfers and design a competitive algorithm that applies the primal-dual method to make routing and resource allocation based on the LP. We perform theoretical analysis to prove that the proposed approach can achieve a competitive ratio of (e-1)/e with little link capacity augmentation. In addition, we conduct comprehensive simulations to evaluate the performance of our method. Simulation results show that our method irrespective of the revenue model, can accept at least 25% more transfer requests and improve the network utilization by at least 35%, compared to prior solutions.

Percolation theory has been studied to investigate network resilience by identifying a critical value of node occupation probability where a giant component (i.e., a largest component in a network) represents high network resilience. However, the concept of network resilience studied in percolation theory has been limited to measuring network fault-tolerance in the presence of failures/attacks. In this work, we take a step to extend the concept of network resilience beyond fault-tolerance by introducing network adaptability. We consider a tactical network where a node is executing multiple tasks by belonging to multiple task groups. In this type of tactical networks, a node is limited with its resource while aiming to maximize its resource utilization and task execution without being overloaded. We investigate network resilience and resource utilization of the tactical network where the network is attacked by either infectious or non-infectious attacks. To mitigate the impact of the failed/attacked nodes in the network, we propose a suite of the proposed adaptation strategies to deal with correlated, cascading failures caused by overloaded nodes due to increased workload introduced by other failed nodes. We conduct a comparative performance analysis of the set of proposed adaptation strategies and a baseline scheme with no adaptation based on metrics including a size of a giant component, node resource utilization, a number of active tasks in execution, and adaptation cost. Our simulation results show that a large size of a giant component does not necessarily ensure high resource utilization of nodes and task performance in the given tactical network.

Radio-frequency identification (RFID) technologies have been widely used in inventory management, object tracking and supply chain management. One of the fundamental system functions is called cardinality estimation, which is to estimate the number of tags in a covered area. We extend the research of this function in two directions. First, we perform joint cardinality estimation among tags that appear at different geographical locations and at different times. Moreover, we collect category-level information, which is more significant in practical scenarios where we need to monitor the tagged objects of many different types. Second, we require anonymity in the process of information gathering in order to preserve the privacy of the tagged objects. These capabilities will enable new applications such as tracking how products are moved in a large, distributed supply network. We propose a novel protocol design to meet the requirements of anonymous category-level joint estimation over multiple tag sets. We formally analyze the performance of our estimator and determine the optimal system parameters. Extensive simulations show that the proposed protocol can efficiently obtain accurate category-level estimation, while preserving tags' anonymity.

Distributed computing networks, tasked with both packet transmission and processing, require the joint optimization of communication and computation resources. We develop a dynamic control policy that determines both routes and processing locations for packets upon their arrival at a distributed computing network. The proposed policy, referred to as Universal Computing Network Control (UCNC), guarantees that packets i) are processed by a specified chain of service functions, ii) follow cycle-free routes between consecutive functions, and iii) are delivered to their corresponding set of destinations via proper packet duplications. UCNC is shown to be throughput-optimal for any mix of unicast and multicast traffic, and is the first throughput-optimal policy for non-unicast traffic in distributed computing networks with both communication and computation constraints. Moreover, simulation results suggest that UCNC yields substantially lower average packet delay compared with existing control policies for unicast traffic.

Many mobile applications (abbrev. apps) reward the users who physically visit some locations tagged as POIs (places-of-interest) by the apps. In this paper, we study the POI-based collaboration between apps and venues (e.g., restaurants and cafes). On the one hand, an app charges a venue and tags the venue as a POI, which attracts users to visit the venue and potentially increases the venue's sales. On the other hand, the venue can invest in the app-related infrastructure (e.g., Wi-Fi networks and smartphone chargers), which enhances the users' experience of using the app. However, the existing POI pricing schemes of the apps (e.g., Pokemon Go and Snapchat) cannot incentivize the venue's infrastructure investment, and hence cannot achieve the most effective app-venue collaboration. We model the interactions among an app, a venue, and users by a three-stage Stackelberg game, and design an optimal two-part pricing scheme for the app. This scheme has a charge-with-subsidy structure: the app first charges the venue for becoming a POI, and then subsidizes the venue every time a user interacts with the POI. Compared with the existing pricing schemes, our two-part pricing better incentivizes the venue's investment, attracts more users to interact with the POI, and achieves a much larger app revenue. We analyze the impacts of the app's and venue's characteristics on the app's optimal revenrevenueue, and show that the apps with small and large congestion effects should collaborate with opposite types of venues.

Recently, non-orthogonal multiple access (NOMA) has been proposed to achieve higher spectral efficiency over conventional orthogonal multiple access. Although it has the potential to meet increasing demands of video services, it is still challenging to provide high performance video streaming. In this research, we investigate, for the first time, a multi-user NOMA system design for video transmission. Various NOMA systems have been proposed for data transmission in terms of throughput or reliability. However, the perceived quality, or the quality-of-experience of users, is more critical for video transmission. Based on this observation, we design a quality-driven scalable video transmission framework with cross-layer support for multiuser NOMA. To enable low complexity multi-user NOMA operations, a novel user grouping strategy is proposed. The key features in the proposed framework include the integration of the quality model for encoded video with the physical layer model for NOMA transmission, and the formulation of multiuser NOMA-based video transmission as a quality-driven power allocation problem. As the problem is non-concave, a global optimal algorithm based on the hidden monotonic property and a suboptimal algorithm with polynomial time complexity are developed. Simulation results show that the proposed multi-user NOMA system outperforms existing schemes in various video delivery scenarios.

Nowadays, the demand for novel approaches of 2D human-computer interaction has enabled the emergence of a number of intelligent devices, such as Microsoft Surface Dial. Surface Dial realizes 2D interactions with the computer via simple clicks and rotations. In this paper, we propose RF-Dial, a battery-free solution for 2D human-computer interaction based on RFID tag arrays. We attach an array of RFID tags on the surface of an object, and continuously track the translation and rotation of the tagged object with an orthogonally deployed RFID antenna pair. In this way, we are able to transform an ordinary object like a board eraser into an intelligent HCI device. According to the RF-signals from the tag array, we build a geometric model to depict the relationship between the phase variations of the tag array and the rigid transformation of the tagged object, including the translation and rotation. By referring to the fixed topology of the tag array, we are able to accurately extract the translation and rotation of the tagged object during the moving process. Moreover, considering the variation of phase contours of the RF-signals at different positions, we divide the overall scanning area into the linear region and non-linear region in regard to the relationship between the phase variation and the tag movement, and propose tracking solutions for the two regions, respectively. We implemented a prototype system and evaluated the performance of RF-Dial in the real environment. The experiments show that RF-Dial achieved an average accuracy of 0. 6cm in the translation tracking, and an average accuracy of 1.9°in the rotation tracking.

The ability of a P2P network to scale its throughput up in proportion to the arrival rate of peers has recently been shown to be crucially dependent on the chunk sharing policy employed. Some policies can result in low frequencies of a particular chunk, known as the missing chunk syndrome, which can dramatically reduce throughput and lead to instability of the system. For instance, commonly used policies that nominally “boost” the sharing of infrequent chunks such as the well-known rarest-first algorithm have been shown to be unstable. Recent efforts have largely focused on the careful design of boosting policies to mitigate this issue. We take a complementary viewpoint, and instead consider a policy that simply prevents the sharing of the most frequent chunk(s). Following terminology from statistics wherein the most frequent value in a data set is called the mode, we refer to this policy as mode suppression. We prove the stability of this algorithm using Lyapunov techniques. We also design a distributed version that suppresses the mode via an estimate obtained by sampling three randomly selected peers. We show numerically that both algorithms perform well at minimizing total download times, with distributed mode suppression outperforming all others that we tested against.

The widespread deployment of end-to-end encryption protocols such as HTTPS and QUIC has reduced the visibility for operators into traffic on their networks. Network operators need the visibility to monitor and mitigate Quality of Experience (QoE) impairments in popular applications such as video streaming. To address this problem, we propose a machine learning based approach to monitor QoE metrics for encrypted video traffic. We leverage network and transport layer information as features to train machine learning classifiers for inferring video QoE metrics such as startup delay and rebuffering events. Using our proposed approach, network operators can detect and react to encrypted video QoE impairments in real-time. We evaluate our approach for YouTube adaptive video streams using HTTPS and QUIC. The experimental evaluations show that our approach achieves up to 90% classification accuracy for HTTPS and up to 85 % classification accuracy for QUIC.

In this paper we develop a simple, yet accurate, performance model to understand if and how evolutions of traditional cellular network protocols can be exploited to allow large numbers of devices to gain control of transmission resources in smart factory radio access networks. The model results shed light on the applicability of evolved access procedures and help understand how many devices can be served per base station. In addition, considering the simultaneous presence of different traffic classes, we investigate the effectiveness of prioritised access, exploiting access class barring techniques. Our model shows that, even with the sub-millisecond time slots foreseen in LTE Advanced Pro and 5G, a base station can accommodate at most few thousand devices to guarantee access latencies below 100 ms with high transmission success probabilities. This calls for a rethinking of wireless access strategies to avoid ultra-dense cell deployments within smart factory infrastructures.

Indoor localization is very important to enable Internet-of-things (IoT) applications. Visible light communication (VLC)-based indoor localization approaches enjoy many advantages, such as utilization of existing ubiquitous lighting infrastructure, high location and orientation accuracy, and no interruption to RF -based devices. However, existing VLC-based localization methods lack a real-time backward channel from the device to landmarks and necessitate computation at the device, which make them unsuitable for real-time tracking of small IoT devices. In this paper, we propose and prototype a retroreflector-based visible light localization system (RETRO), that establishes an almost zero-delay backward channel using a retroreflector to reflect light back to its source. RETRO localizes passive IoT devices without requiring computation and heavy sensing (e.g., camera) at the devices. Multiple photodiodes (i.e., landmarks) are mounted on any single unmodified light source to sense the retroreflected optical signal (i.e., location signature). We theoretically derive a closed-form expression for the reflected optical power related to the location and orientation of the retroreflector, and validate the theory by experiments. The characterization of received optical power is applied to a received signal strength indicator and trilateration based localization algorithm. Extensive experiments demonstrate centimeter-level location accuracy and single-digit angular error.

LED-Camera Visible Light Communication (VLC) is gaining increasing attention, thanks to its readiness to be implemented with Commercial Off-The-Shelf devices and its potential to deliver pervasive data services indoors. Nevertheless, existing LED-Camera VLC systems employ mainly low-order modulations such as On-Off Keying (OOK) given the simplicity of their implementation, yet such rudimentary modulations cannot yield a high throughput. In this paper, we investigate various opportunities of using a high-order modulation to boost the throughput of LED-Camera VLC systems, and we decide that Amplitude-Shift Keying (ASK) is the most suitable scheme given the limited operating frequency of such systems. However, directly driving an LED to emit different levels of luminance may suffer heavy distortions caused by the nonlinear behavior of LED. As a result, we innovatively propose to generate ASK using the composition of light emission. In other words, we digitally control the On-Off states of several groups of LED chips, so that their light emissions compose in the air to produce various ASK symbols. We build a prototype of this novel ASK-based VLC system and demonstrate its superior performance over existing systems: it achieves a rate of 2 kbps at a 1 m distance with only a single LED luminaire.

Emerging network architectures in 60GHz millimeter wave bands will likely use dense deployment of access points (APs) given the high attenuation and frequent line-of-sight related outages. We show in this paper that naively connecting to any available AP, or even multiple APs, may not fully realize the promise of efficiently utilizing the extremely large bandwidths available in this band. This paper holistically addresses these problems through the Multi-AP Association Protocol (MAP) that: (i) indicates ideal durations for beam-searching at the physical/link layers of the protocol stack that will result in minimal interruptions to user-traffic, (ii) devises a Multi-AP association framework based on multipath TCP, which increases the network robustness by allowing immediate redirection of traffic to alternative APs whenever an existing connection is interrupted, and (iii) designs an exploration-exploitation aware flow scheduling algorithm that dynamically activates the sub-flows to optimize transport layer performance. MAP is a lightweight, client side system that needs zero modifications to existing protocol stack, though it interacts with the latter to opportunistically trigger standards-defined functions. The paper also presents convergence analysis of throughput, experimental validation on a 60GHz network testbed, and trace-driven simulation studies that shows MAP achieving 5-7x reduction in re-buffering rate in HD video streaming, rapid convergence to the best possible AP, and fair allocation of resources among clients.

S-The emergence of the Internet-of-Things (IoT) has inspired numerous new applications. However, due to the limited resources in current IoT infrastructures and the stringent quality-of-service requirements of the applications, providing computing and communication supports for the applications is becoming increasingly difficult. In this paper, we consider IoT applications that receive continuous data streams from multiple sources in the network, and study joint application placement and data routing to support all data streams with both bandwidth and delay guarantees. We formulate the application provisioning problem both for a single application and for multiple applications, with both cases proved to be NP-hard. For the case with a single application, we propose a fully polynomial-time approximation scheme. For the multi-application scenario, if the applications can be parallelized among multiple distributed instances, we propose a fully polynomial-time approximation scheme; for general non-parallelizable applications, we propose a randomized algorithm and analyze its performance. Simulations show that the proposed algorithms greatly improve the quality-of-service of the IoT applications compared to the heuristics.

The emerging energy harvesting technology enables charging sensor batteries with renewable energy sources, which has been effectively integrated into Wireless Sensor Networks (EH-WSNs). Meanwhile, data aggregation is an essential operation in a WSN. The problem of Minimum Latency Aggregation Scheduling (MLAS) which seeks a fast and collision-free aggregation schedule has been well studied when nodes are energy-abundant. However, due to the limited energy harvesting capacities of tiny sensors, the captured energy remains scarce and differs greatly among nodes. Thus, all of the previous algorithms for MLAS are not suitable in EH-WSNs. In this paper, we investigate the MLAS problem in EH-WSNs. To make use of the harvested energy smartly, we construct an aggregation tree adaptively according to the residual battery level at each node. Furthermore, we identify a new kind of collision, named as energy -collision, and design a special structure to assist in avoiding it. By considering transmitting time, residual energy, and energy-collision, we propose three scheduling algorithms for MLAS problem in EH-WSNs. The theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of aggregation latency compared with the baseline methods.