INFOCOM 2018 Papers

60 GHz networks, with multi-Gbps bitrate, are considered as the enabling technology for emerging applications such as wireless Virtual Reality (VR) and 4K/8K real-time Miracast. However, user motion, and even orientation change, can cause mis-alignment between 60 GHz transceivers' directional beams, thus causing severe link outage. Within the practical 3D spaces, the combination of location and orientation dynamics leads to exponential growth of beam searching complexity, which substantially exacerbates the outage and hinders fast recovery. In this paper, we first conduct an extensive measurement to analyze the impact of 3D motion on 60 GHz link performance, in the context of VR and Miracast applications. We find that 3D motion exhibits inherent non-predictability, so conventional beam steering solutions, which targets 2D scenarios with lower search space and short-term motion coherence, fail in practical 3D setup. Motivated by these observations, we propose a model-driven 3D beam-steering mechanism called Orthogonal Scanner (OScan), which can maintain high performance for mobile 60 GHz links in 3D space. OScan discovers and leverages a hidden interaction between 3D beams and the spatial channel profile of 60 GHz radios, and strategically scans the 3D space so as to reduce the search latency by more than one order of magnitude. Experiment results based on a custom-built 60 GHz platform along with a trace-driven emulator demonstrate OScan's remarkable throughput gain, up to 5×, compared with the state-of-the-art.

Connected electric vehicles (EVs) are a key component of future intelligent and green transportation systems, and the penetration of EVs depends on convenient and cost-effective charging services. In addition to being charged at home or on parking lots, a charging network is needed for EVs right off the road. This paper first focuses on the optimal charging network design for charging service providers, considering the time-varying and location-dependent demands from vehicles and constraints of power grids. To optimize the charging station locations and the number of chargers in each station, we first model the coverage area of each possible location to estimate the dynamic charging requirements of EVs. Then, we formulate the problem as profit maximization, which is a mixed-integer program. To make the problem tractable, we investigate the features of the problem and obtain a necessary condition to deploy a charging station and derive the upper and lower bounds of the number of chargers in each station. Given the analysis, we take two steps to transform and relax the problem to convex optimization. A fast-converging search algorithm is further proposed based on the profit of each possible location. Using real vehicle traces, simulation results show that the proposed algorithm can maximize the total profit when fewer charging stations and chargers are initially needed, which is more attractive for charging service providers.

Due to network practices such as traffic engineering and multi-homing, the number of routes-also known as IP prefixes-in the global forwarding tables has been increasing significantly in the last decade and continues growing in a super linear trend. One of the most promising solutions is to use smart Forwarding Information Base (FIB) aggregation algorithms to aggregate the prefixes and convert a large table into a small one. Doing so poses a research question, however, i.e., how can we quickly verify that the original table yields the same forwarding behaviors as the aggregated one? We answer this question in this paper, including addressing the challenges caused by the longest prefix matching (LPM) lookups. In particular, we propose the VeriTable algorithm that can employ a single tree/trie traversal to quickly check if multiple forwarding tables are forwarding equivalent, as well as if they could result in routing loops or black holes. The VeriTable algorithm significantly outperforms the state-of-the-art work for both IPv4 and IPv6 tables in every aspect, including the total running time, memory access times and memory consumption.

Today, 360-degree video streaming has become a popular Internet service with the rise of affordable virtual reality (VR) technologies. However, streaming 360-degree videos suffers from the prohibitive bandwidth demand. Existing bandwidth-efficient solutions mainly focus on exploiting the inherent spatial adaptability of 360-degree videos, delivering only video content (spatially-cut tiles) in the viewer's region of interest (ROI) with higher quality. Temporal adaptability, which has been widely leveraged in HTTP streaming, has not been well exploited to select proper quality for video segments according to the bandwidth variations. When these two dimensions of adaptability are jointly considered, bitrate selection for the tiles become more complicated and challenging. The importance of a tile with a spatial coordination played at a specific time should be quantified so that we can determine how to allocate bandwidth for improving the viewer's quality of experience. Furthermore, viewer's head orientation prediction is highly variable, which makes the determination of important tiles highly dynamic. In addition, network fluctuations are very common on the Internet. To overcome these challenges, we propose Bi-Adaptive Streaming for 360-degree videos (BAS-360°). In BAS-360°, both spatial and temporal adaptabilities are explored in the bitrate selection for different tiles. The objective is to minimize the bandwidth waste by allocating bandwidth to more important tiles (the tiles that are more likely to be watched). To tackle the high variability of visual region prediction and the unpredictable network fluctuations, we employ two features provided by HTT P /2: stream termination and stream priority, to efficiently organize tile delivery. Evaluation results show that BAS-360° outperforms naive tile-based 360-degree video streaming strategies when network fluctuations or errors in viewport predictions occur.

In urban environments, mobile crowdsensing can be used to augment in-situ sensing deployments (e.g. for environmental and community monitoring) in a flexible and cost-efficient manner. The additional participation provided by crowdsensing enables improved data collection coverage and enhances timeliness of data delivery. However, as the number of participating devices/users increases, efficient management is required to handle the increased operational cost of the infrastructure and associated cloud services - exploiting spatiotemporal redundancy in sensing can help cost-efficient utilization of resources. In this paper, we develop solutions to exploit the mobility of the crowd and manage the sensing capability of participating devices to effectively meet application/user demands for hybrid urban sensing applications. Specifically, we address the spatiotemporal scheduling problem to create high-resolution maps (e.g. for pollution sensing) by developing a common framework to capture spatiotemporal impact of multiple sensor types that generate heterogeneous data at different levels of granularity. We develop an online scheduling approach that leverages the knowledge of device location and sensing capability to selectively activate nodes and sensors. We build a multi-sensor platform that enables data collection, data exchange, and node management. Prototype deployments in three different campus/community testbeds were instrumented for measurements. Traces collected from the testbeds are used to drive extensive large scale simulations. Results show that our proposed solution achieves improved data coverage and utility under data constraints with lower costs (30% fewer active nodes) than naive approaches.

Cloud-based computing technology is one of the most significant technical advents of the last decade and extension of this facility towards access networks by aggregation of cloudlets is a step further. To fulfill the ravenous demand for computational resources entangled with the stringent latency requirements of computationally-heavy applications related to augmented reality, cognitive assistance and context-aware computation, installation of cloudlets near the access segment is a very promising solution because of its support for wide geographical network distribution, low latency, mobility and heterogeneity. In this paper, we propose a novel framework, Cloudlet Cost OptiMization over PASSIve Optical Network (CCOMPASSION), and formulate a nonlinear mixed-integer program to identify optimal cloudlet placement locations such that installation cost is minimized whilst meeting the capacity and latency constraints. Considering urban, suburban and rural scenarios as commonly-used network deployment models, we investigate the feasibility of the proposed model over them and provide guidance on the overall cloudlet facility installation over optical access network. We also study the percentage of incremental energy budget in the presence of cloudlets of the existing network. The final results from our proposed model can be considered as fundamental cornerstones for network planning with hybrid cloudlet network architectures.

Efficient allocation of resources is an essential yet challenging problem in a virtual network environment, especially in an online setting whereby virtual network requests may arrive, depart, or be modified in real time. Virtual network reconfiguration may help to improve network performance by remapping a subset of virtual nodes or links to better align the allocation of resources to current network conditions. In this paper, we develop a virtual network reconfiguration scheme that aims to balance the load on the substrate network by dynamically reconfiguring the embedding of both virtual nodes and links. Our solution consists of decomposing the problem into two subproblems: i) virtual node selection, for which we present a linear programming-based fully polynomial time approximation scheme to select the virtual nodes to be migrated, and ii) virtual node remapping, for which we make use of random walk on a Markov chain to select new substrate nodes for the migrated virtual nodes.

In a Virtual Symmetric Multiprocessing (VSMP) environment, the behavior of hypervisor scheduler can significantly influence a guest's I/O responsiveness. The interrupt remapping mechanism, which can leverage multiple virtual CPUs in the VSMP guest to process I/O events, is known to be an efficient and prevalent solution to improve the I/O performance. However, in this paper we identified a novel challenge called the “Interruptability Holder Preemption” (IHP) problem in interrupt remapping mechanism. The IHP issue presents that a virtual CPU (vCPU) disabling the interruptability of guest's network device is descheduled by the hypervisor scheduler, which can easily invalidate the efficiency of the interrupt remapping mechanism. To solve this problem, we propose CoINT, a gasket coordinator residing in the hypervisor, to substantially enhance the network I/O performance by empowering the hypervisor to be proactively aware of the interruptability information of the guest's network device. ColNT completely eliminates the “Interruptability Holder Preemption” problem and largely reduces I/Ointerrupt processing delay caused by hypervisor scheduler. We implement ColNT in KVM hypervisor and evaluate its efficiency and responsiveness using both macro and microlevel benchmarks. The results show that ColNT can improve the netperf throughput up to 3x compared with native KVM, and up to 1.3x compared with traditional interrupt remapping of hypervisor-Ievel solution, in sacrifice of an negligible and reasonable overhead in the hypervisor.

Due to the loose authentication requirement between access points (APs) and clients, it is notoriously known that WLANs face long-standing threats such as rogue APs and network freeloading. Take the rogue AP problem as an example, unfortunately encryption alone does not provide authentication. APs need to be equipped with certificates that are trusted by clients ahead of time. This requires either the presence of PKI for APs or other forms of pre-established trust (e.g., distributing the certificates offline), none of which is widely used. Before any strong security solution is deployed, we still need a practical solution that can mitigate the problem. In this paper, we explore a non-cryptographic solution that is readily deployable today on end hosts (e.g., smartphones and laptops) without requiring any changes to the APs or the network infrastructure. The solution infers the Carrier Frequency Offsets (CFOs) of wireless devices from Channel State Information (CSI) as their hardware fingerprints without any special hardware requirement. CFO is attributed to the oscillator drift, which is a fundamental physical property that cannot be manipulated easily and remains fairly consistent over time but varies significantly across devices. The real experiments on 23 smartphones and 34 APs (with both identical and different brands) in different scenarios demonstrate that the detection rate could exceed 94%.

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. We consider two problems in this model: (Δ+1)-vertex coloring and maximal independent set (MIS), for a network of unknown size n and unknown maximum degree Δ. Solving these problems allows to overcome communication interferences, and to break symmetry, a core component of many distributed protocols. The presented results apply to general graphs, but are efficient in graphs with low edge density (sparse graphs), such as bounded degree graphs, planar graphs and graphs of bounded arboricity. We present O(Δ2log n + Δ3) time deterministic uniform MIS and coloring protocols, which are asymptotically time optimal for bounded degree graphs. Furthermore, we devise O(a2log2n+a3log n) time MIS and coloring protocols, as well as O(a2Δ2log2n + a3Δ3log n) time 2-hop MIS and 2-hop coloring protocols, where a is the arboricity of the communication graph. Building upon the 2-hop coloring protocols, we show how the strong CONGEST model can be simulated and by using this simulation we obtain an O ( a) -coloring protocol. No results about coloring with less than Δ + 1 colors were known up to now in the beeping model.

A fundamental challenge in wireless multicast has been how to simultaneously achieve high-throughput and low-delay for reliably serving a large number of users. In this paper, we show how to harness substantial throughput and delay gains by exploiting multi-channel resources. We develop a new scheme called Multi-Channel Moving Window Codes (MC-MWC) for multi-channel multi-session wireless multicast. The salient features of MC-MWC are three-fold. (i) High throughput: we show that MC-MWC achieves order-optimal throughput in the many-user many-channel asymptotic regime. Moreover, the number of channels required by a conventional channel-allocation based scheme is shown to be doubly-exponentially larger than that required by MC-MWC. (ii) Low delay: using large deviations theory, we show that the delay of MC-MWC decreases linearly with the number of channels, while the delay reduction of conventional schemes is no more than a finite constant. (iii) Low feedback overhead: the feedback overhead of MC-MWC is a constant that is independent of both the number of receivers in each session and the number of sessions in the network. Finally, our trace-driven simulation and numerical results validate the analytical results and show that the implementation complexity of MC-MWC is low.

We study a mobile wireless network in which nodes travel on an infinite plane along trajectories comprised of linear segments; a single packet is traveling towards a destination located at an infinite distance, employing both wireless transmissions and sojourns on node buffers. In this setting, we calculate analytically the long-term averages of (i) the speed with which the packet travels towards its destination and (ii) the rate with which the wireless transmission cost accumulates with distance traveled. Due to the problem's complexity, we use two approximations; simulations show that the resulting errors are modest.

Separation of control and data planes (SCDP) is a desirable paradigm for low-power multi-hop wireless networks requiring high network performance and manageability. Existing SCDP networks generally adopt an in-band control plane scheme in that the control-plane messages are delivered by their data-plane networks. The physical coupling of the two planes may lead to undesirable consequences. To advance the network architecture design, we propose to leverage on the long-range communication capability of the increasingly available low-power wide-area network (LPWAN) radios to form one-hop out-of-band control planes. We choose LoRaWAN, an open, inexpensive, and ISM band based LPWAN radio to prototype our out-of-band control plane called LoRaCP. Several characteristics of LoRaWAN such as downlink-uplink asymmetry and primitive ALOHA media access control (MAC) present challenges to achieving reliability and efficiency. To address these challenges, we design a TDMA-based multi-channel MAC featuring an urgent channel and negative acknowledgment. On a testbed of 16 nodes, we demonstrate applying LoRaCP to physically separate the control-plane network of the Collection Tree Protocol (CTP) from its ZigBee-based data-plane network. Extensive experiments show that LoRaCP increases CTP's packet delivery ratio from 65 % to 80 % in the presence of external interference, while consuming a per-node average radio power of 2.97mW only.

To optimize routing of flows in datacenters, SDN controllers receive a packet-in message whenever a new flow appears in the network. Unfortunately, flow arrival rates can peak to millions per second, impairing the ability of controllers to treat them on time. Flow scheduling copes with such sheer numbers by segmenting the traffic between elephant and mice flows and by treating elephant flows in priority, as they disrupt short lived TCP flows and create bottlenecks. We propose a learning algorithm called SOFIA and able to perform optimal online flow segmentation. Our solution, based on stochastic approximation techniques, is implemented at the switch level and updated by the controller, with minimal signaling over the control channel. SOFIA is blind, i.e., it is oblivious to the flow size distribution. It is also adaptive, since it can track traffic variations over time. We prove its convergence properties and its message complexity. Moreover, we specialize our solution to be robust to traffic classification errors. Extensive numerical experiments characterize the performance of our approach in vitro. Finally, results of the implementation in a real OpenFlow controller demonstrate the viability of SOFIA as a solution in production environments.

Centrality metrics are a key instrument for graph analysis and play a central role in many problems related to networking such as service placement, robustness analysis and network optimization. Betweenness centrality is one of the most popular and well-studied metric. While distributed algorithms to compute this metric exist, they are either approximated or limited to certain topologies (directed acyclic graphs or trees). Exact distributed algorithms for betweenness centrality are computationally complex, because its calculation requires the knowledge of all possible shortest paths within the graph. In this paper we consider load centrality, a metric that usually converges to betweenness, and we present the first distributed and exact algorithm to compute it. We prove its convergence, we estimate its complexity and we show it is directly applicable-with minimal modifications-to any distance-vector routing protocol based on Bellman-Ford. We finally implement it on top of the Babel routing protocol and we show that, exploiting centrality, we can significantly reduce Babel's convergence time upon node failure without increasing signalling overhead. Our contribution is relevant in the realm of wireless distributed networks, but the algorithm can be adopted in any distributed system where it is not possible, or computationally impractical, to reconstruct the whole network graph at each node and compute betweenness centrality with the classical approach based on Dijkstra's algorithm.

Motivated by the increasing importance of providing delay-guaranteed services in general computing and communication systems, and the recent wide adoption of learning and prediction in network control, in this work, we consider a general stochastic single-server multi-user system and investigate the fundamental benefit of predictive scheduling in improving timely-throughput, being the rate of packets that are delivered to destinations before their deadlines. By adopting an error rate-based prediction model, we first derive a Markov decision process (MDP) solution to optimize the timely-throughput objective subject to an average resource consumption constraint. Based on a packet-level decomposition of the MDP, we explicitly characterize the optimal scheduling policy and rigorously quantify the timely-throughput improvement due to predictive-service, which scales as Θ(p[C1[((a-amaxq))/(p-q)] ρτ+ C2(1-[1/p])](1-ρD)), where a, amax, ρ ∈ (0,1), C1> 0, C2≥ 0 are constants, p is the true-positive rate in prediction, Q is the false-negative rate, τ is the packet deadline and D is the prediction window size. We also conduct extensive simulations to validate our theoretical findings. Our results provide novel insights into how prediction and system parameters impact performance and provide useful guidelines for designing predictive low-latency control algorithms.

The explosive number of IoT nodes and adoption of software-defined radio have enabled an efficient method of exploiting idle frequency spectrums called dynamic spectrum access (DSA). The foremost problem in DSA is for a pair of nodes to rendezvous and form a control channel prior to communication. Existing schemes require a channel hopping (CH) pattern with length O(N2), which is overly complex especially when the number of channels N is large. Moreover, the CH patterns are designed assuming DSA nodes have unlimited CH capability, which is hardly satisfied by nodes with long frequency switching time and limited sensing capacity. In this paper, we design a low-complexity rendezvous scheme that account for CH capability limits. The CH capability is captured using spectrum slice graphs that describe the possible channels for the next hop, given the currently-visited channel. By viewing the CH patterns as random walks over the spectrum graphs, we assign the walks with optimal transition probabilities that achieve the smallest rendezvous delay. The resulting symmetric random CH (S-RCH) scheme, which is suitable for IoT nodes without predetermined roles, achieves a lower rendezvous delay than existing Modular Modified Clock (MMC) scheme and offers more than 80 % successful rendezvous in mobile networks.

In this paper, we present the first algorithm for exactly implementing the abstract MAC (absMAC) layer in the physical SINR model. The absMac layer, first presented by Kuhn et al. in [15], provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions, such that high-level algorithms can be designed in terms of these functions, independent of specific channel behavior. The implementation of absMAC layer is to design a distributed algorithm for the local broadcast communication primitives over a particular communication model that defines concrete channel behaviors, and the objective is minimizing the bounds of the abstract delay functions. Halldórsson et al. [10] have shown that in the standard SINR model (synchronous communication, without physical carrier sensing or location information), there cannot be efficient exact implementations. In this work, we show that physical carrier sensing, a commonly seen function performed by wireless devices, can help get efficient exact implementation algorithms. Specifically, we propose an algorithm that exactly implements the absMAC layer. The algorithm provides asymptotically optimal bounds for both acknowledgement and progress functions defined in the absMAC layer. Our algorithm can lead to many new faster algorithms for solving high-level problems in the SINR model. We demonstrate this by giving algorithms for problems of Consensus, Multi-Message Broadcast and Single-Message Broadcast. It deserves to point out that our implementation algorithm is designed based on an optimal algorithm for a General Local Broadcast (GLB) problem, which takes the number of distinct messages into consideration for the first time. The GLB algorithm can handle much more communication scenarios apart from those defined in the absMAC layer. Simulation results show that our proposed algorithms perform well in reality.

Set-valued data is useful for representing a rich family of information in numerous areas, such as market basket data of online shopping, apps on mobile phones and web browsing history. By analyzing set-valued data that are collected from users, service providers could learn the demographics of the users, the patterns of their usages, and finally, improve the quality of services for them. However, privacy has been an increasing concern in collecting and analyzing users' set-valued data, since these data may reveal sensitive information (e.g., identities, preferences and diseases) about individuals. In this work, we propose a privacy preserving aggregation mechanism for set-valued data: PrivSet. It provides rigorous data privacy protection locally (e.g., on mobile phones or wearable devices) and efficiently (its computational overhead is linear to the item domain size) for each user, and meanwhile allowing effective statistical analyses (e.g., distribution estimation of items, distribution estimation of set cardinality) on set-valued data for service providers. More specifically, in PrivSet, within the constraints of local e-differential privacy, each user independently responses with a subset of the set-valued data domain with calibrated probabilities, hence the true positive/false positive rate of each item is balanced and the performance of distribution estimation is optimized. Besides presenting theoretical error bounds of PrivSet and proving its optimality over existing approaches, we experimentally validate the mechanism, the experimental results illustrate that the estimation error in PrivSet has been reduced by half when compared to state-of-the-art approaches.