INFOCOM 2020 Papers

Off-blockchain payment channels can significantly improve blockchain scalability by enabling a large number of micro-payments between two blockchain nodes, without committing every single payment to the blockchain. Multiple payment channels form a payment network, so that two nodes without direct channel connection can still make payments. A critical challenge in payment network construction is to decide how many funds should be deposited into payment channels as initial balances, which seriously influences the performance of payment networks, but has been seldom studied by existing work. In this paper, we address this challenge by designing PnP, a balance planning service for payment networks. Given estimated payment demands among nodes, PnP can decide channel balances to satisfy these demands with a high probability. It does not rely on any trusted third-parties, and can provide strong protection from malicious attacks with low overhead. It obtains these benefits with two novel designs, the cryptographic sortition and the chance-constrained balance planning algorithm. Experimental results on a testbed of 30 nodes show that PnP can enable 30% more payments than other designs.

Industrial Scientific Medical (ISM) band has become more and more crowded due to the ever-growing size of many mainstream technologies, e.g., Wi-Fi, ZigBee and Bluetooth. Though they compete for limited spectrum resources leading to severe Cross Technology Interference (CTI), it also provides great opportunities to better utilize the scarce bandwidth resources. A fundamental question is how to ensure harmonious and effective operations for these networks? To exploit this issue, a novel global cooperation framework is proposed. In particular, our work enables direct and simultaneous Cross Technology Communication (CTC) from a single Wi-Fi to ZigBee, Bluetooth and Wi-Fi commodity devices sharing the same band. Compared to existing CTC approaches, our scheme improves the communication efficiency significantly, and hence is the foundation for effective global cooperation. Based on the proposed CTC scheme, a unified Media Access Control (MAC) approach is introduced to cooperate CTC message transmission and reception for heterogeneous devices with different MACs. Two proof-of-concepts applications, e.g. global synchronization and global CTI coordination are discussed to fully leverage the benefits of global cooperation. Extensive evaluations show that compared with existing schemes, the proposed framework achieves 13 times lower synchronization error and 9 times lower average packet delay in CTI intensive environments.

Live migration, the process of transferring a running application to a different physical location with minimal downtime, can provide many benefits desired by modern cloudbased systems. Furthermore, live migration between different cloud providers enables a new level of freedom for cloud users to move their workloads around for performance or business objectives without having to be tied down to any single provider. While this vision is not new, to-date, there are few solutions and proof-of-concepts that provide this capability. As containerized applications are gaining popularity, we focus on the design and implementation of live migration of containers across cloud providers. CloudHopper, our proof-of-concept live migration service for containers to hop around between Amazon Web Services, Google Cloud Platform, and Microsoft Azure is evaluated using a common web-based workload. CloudHopper is automated and supports pre-copy optimization, connection holding, traffic redirection, and multiple interdependent container migration. It is applicable to a broad range of application use cases.

Age of information, as a metric measuring the data freshness, has drawn increasing attention due to its importance in many data update applications. Most existing studies have assumed that there is one single channel in the system. In this work, we are motivated by the plethora of multi-channel systems that are being developed, and investigate the following question: how can one exploit multi-channel resources to improve the age performance? We first derive a policy-independent lower bound of the expected long-term average age in a multi-channel system. The lower bound is jointly characterized by the external arrival process and the channel statistics. Since direct analysis of age in multi-channel systems is very difficult, we focus on the asymptotic regime, when the number of users and number of channels both go to infinity. In the many-channel asymptotic regime, we propose a class of Maximum Weighted Matching policies that converge to the lower bound near exponentially fast. In the many-user asymptotic regime, we design a class of Randomized Maximum Weighted Matching policies that achieve a constant competitive ratio compared to the lower bound. Finally, we use simulations to validate the aforementioned results.

Dynamic spectrum access (DSA) is a promising platform to solve the spectrum shortage problem, in which auction based mechanisms have been extensively studied due to good spectrum allocation efficiency and fairness. Recently, Sybil attacks were introduced in DSA, and Sybil-proof spectrum auction mechanisms have been proposed, which guarantee that each single secondary user (SU) cannot obtain a higher utility under more than one fictitious identities. However, existing Sybil-poof spectrum auction mechanisms achieve only Sybil-proofness for SUs, but not for primary users (PUs), and simulations show that a cheating PU in those mechanisms can obtain a higher utility by Sybil attacks. In this paper, we propose TSUNAMI, the first Truthful and primary user Sybil-proof aUctioN mechAnisM for onlIne spectrum allocation. Specifically, we compute the opportunity cost of each SU and screen out cost-efficient SUs to participate in spectrum allocation. In addition, we present a bid-independent sorting method and a sequential matching approach to achieve primary user Sybil-proofness and 2-D truthfulness, which means that each SU or PU can gain her maximal utility by bidding with her true valuation of spectrum. We evaluate the performance and validate the desired properties of our proposed mechanism through extensive simulations.

This paper explores the design of dynamic network topologies which adjust to the workload they serve, in a demand-aware and online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. However, such reconfigurations also come at a cost, introducing a need for online algorithms which strike an optimal balance between the benefits and costs of reconfigurations.This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on a distributed implementation of skip lists (which serves as the topology) and provide additional interesting properties such as local routing. Our first contribution is SASL2, which is a randomized and sequential SAN algorithm that achieves the working set property. Then we show how SASL2can be converted to a distributed algorithm that handles concurrent communication requests and maintains SASL2's properties. Finally, we present deterministic SAN algorithms.

Age of Information (AoI) is an application layer performance metric that quantifies the freshness of information. This paper investigates scheduling problems at network edge when each source node has an AoI requirement (which we call Maximum AoI Threshold (MAT)). Specifically, we want to determine whether or not a vector of MATs for the source nodes is schedulable, and if so, find a feasible scheduler for it. For a small network, we present an optimal procedure called Cyclic Scheduler Detection (CSD) that can determine the schedulability with absolute certainty. For a large network where CSD is not applicable, we present a novel low-complexity procedure, called Fictitious Polynomial Mapping (FPM), and prove that FPM can find a feasible scheduler for any MAT vector when the load is under ln 2. We use extensive numerical results to validate our theoretical results and show that the performance of FPM is significantly better than a state-of-the-art scheduling algorithm.

We present an active measurement test (netflix) that downloads content from the Netflix content delivery network. The test measures latency and achievable throughput as key performance indicators when downloading the content from Netflix. We deployed the test on ~100 SamKnows probes connected to dual-stacked networks representing 74 different origin ASes. Using a ~2.75 year-long (Jul 2016-Apr 2019) dataset, we observe Netflix Open Connect Appliance (OCA) infrastructure to be highly available, although some vantage points experience low success rates connecting over IPv6. We witness that clients prefer connecting to Netflix OCAs over IPv6, although the preference over IPv6 tends to drop over certain peak hours during the day. The TCP connect times toward the OCAs have reduced by ~40% and the achievable throughput has increased by 20% over the measurement duration. We also provision scamper right after the netflix test to capture the forwarding path toward the Netflix OCAs. We observe that the Netflix OCA caches deployed inside the ISP are reachable within six IP hops and can reduce IP path lengths by 40% over IPv4 and by half over IPv6. Consequently, TCP connect times are reduced by 64% over both address families. The achieved throughput can~ also increase by a factor of three when such ISP caches are used to stream content. This is the first study to measure Netflix content delivery from residential networks, since the inception of the Netflix CDN infrastructure in 2011. To encourage reproducibility of our work, an anonymized version of the entire longitudinal dataset is publicly released.

This paper presents LiteNap which improves the energy efficiency of LoRa by enabling LoRa nodes to operate in a downclocked `light sleep' mode for packet reception. A fundamental limit that prevents radio downclocking is the Nyquist sampling theorem which demands the clock-rate being at least twice the bandwidth of LoRa chirps. Our study reveals under-sampled LoRa chirps suffer frequency aliasing and cause ambiguity in symbol demodulation. LiteNap addresses the problem by leveraging an empirical observation that the hardware of LoRa radio can cause phase jitters on modulated chirps, which result in frequency leakage in the time domain. The timing information of phase jitters and frequency leakages can serve as physical fingerprints to uniquely identify modulated chirps. We propose a scheme to reliably extract the fingerprints from under-sampled chirps and resolve ambiguities in symbol demodulation. We implement LiteNap on a software defined radio platform and conduct trace-driven evaluation. Experiment results show that LiteNap can downclock LoRa nodes to sub-Nyquist rates for energy savings (e.g., 1/8 of Nyquist rate), without substantially affecting packet reception performance (e.g., >95% packet reception rate).

We consider the scenario where a sender streams a flow at a fixed rate to a receiver across a multi-hop network, possibly using multiple paths. Data transmission over a link incurs a cost and a delay, both of which are traffic-dependent. We study the problem of minimizing network transmission cost subject to a maximum delay constraint and a throughput requirement. The problem is important for leveraging edge-cloud computing platforms to support computationally intensive IoT applications, which are sensitive to three critical performance metrics, i.e., cost, maximum delay, and throughput. Our problem jointly considers the three metrics, while existing ones only account for one or two of them. We first show that our problem is uniquely challenging, as (i) it is NP-complete even to find a feasible solution satisfying all constraints, and (ii) directly extending existing solutions to our problem results in problem-dependent maximum delay violations that can be unbounded. We then design both an approximation algorithm and an efficient heuristic. For any feasible instance, our approximation algorithm will achieve a cost no worse than the optimal, while violating the maximum delay constraint and the throughput requirement only by constant ratios. Meanwhile, our heuristic will construct feasible solutions for a large portion (over 60% empirically) of feasible instances, strictly satisfying the maximum delay constraint and the throughput requirement. We further characterize a condition under which the cost of our heuristic must be within a problem-dependent-ratio gap to the optimal. We simulate representative edge computing platforms, and observe that (i) when sacrificing 3% throughput, our approximation algorithm reduces 32% cost as compared to a greedy baseline, and satisfies the maximum delay constraint for 56% simulated instances; (ii) our heuristic solves 62% of feasible instances, and reduces 24% cost as compared to the baseline while strictly satisfying all constraints.

Ternary Content Addressable Memory (TCAM) is widely used by modern routers and switches to support policy-based forwarding. However, the limited TCAM capacity does not scale with the ever-increasing rule table size. Using TCAM just as a rule cache is a plausible solution, but one must resolve several tricky issues including the rule dependency and the associated TCAM updates. In this paper, we propose a new approach which can generate dependency-free rules to cache. By removing the rule dependency, the TCAM update problem also disappears. We provide the complete T-cache system design including slow path processing and cache replacement. Evaluations based on real-world and synthesized rule tables and traces show that T-cache is efficient and robust for network traffic in various scenarios.

The challenges in analysis and co-design of wireless networked control systems are well highlighted by considering wireless industrial control protocols. In this perspective, this paper addresses the modeling and design challenge by focusing on WirelessHART, which is a networking protocol stack widely adopted for wireless industrial automation. Specifically, we first develop and validate a Markov channel model that abstracts the WirelessHART radio link subject to channel impairments and interference. The link quality metrics introduced in the theoretical framework are validated in order to enable the accurate representation of the average and extreme behavior of the radio link. By adopting these metrics, it is straightforward to handle a consistent finite-state abstraction. On the basis of such a model, we then derive a stationary Markov jump linear system model that captures the dynamics of a control loop closed over the radio link. Subsequently, we show that our modeling framework is able to discover and manage the challenging subtleties arising from bursty behavior. A relevant theoretical outcome consists in designing a controller that guarantees stability and improves control performance of the closed-loop system, where other approaches based on a simplified channel model fail.

Wireless communications for status update are becoming increasingly important, especially for machine-type control applications. Existing work has been mainly focused on Age of Information (AoI) optimizations. In this paper, a status-aware predictive wireless interface design, networking and implementation are presented which aim to minimize the status recovery error of a wireless networked system by leveraging online status model predictions. Two critical issues of predictive status update are addressed: practicality and usefulness. Link-level experiments on a Software-Defined-Radio (SDR) testbed are conducted and test results show that the proposed design can significantly reduce the number of wireless transmissions while maintaining a low status recovery error. A Status-aware Multi-Agent Reinforcement learning neTworking solution (SMART) is proposed to dynamically and autonomously control the transmit decisions of devices in an ad hoc network based on their individual statuses. System-level simulations of a multi dense platooning scenario are carried out on a road traffic simulator. Results show that the proposed schemes can greatly improve the platooning control performance in terms of the minimum safe distance between successive vehicles, in comparison with the AoI-optimized status-unaware and communication latency-optimized schemes-this demonstrates the usefulness of our proposed status update schemes in a real-world application.

Internet of Things (IoT) includes numerous sensing nodes that constitute a large scale-free network. Optimizing the network topology for increased resistance against malicious attacks is an NP-hard problem. Heuristic algorithms, particularly genetic algorithms, can effectively cope with such problems. However, conventional genetic algorithms are prone to falling into premature convergence owing to the lack of global search ability caused by the loss of population diversity during evolution. Although this can be alleviated by increasing population size, additional computational overhead will be incurred. Moreover, after crossover and mutation operations, individual changes in the population are mixed, and loss of optimal individuals may occur, which will slow down the evolution of the population. Therefore, we combine the population state with the evolutionary process and propose an Adaptive Robustness Evolution Algorithm (AREA) with self-competition for scale-free IoT topologies. In AREA, the crossover and mutation operations are dynamically adjusted according to population diversity to ensure global search ability. Moreover, a self-competitive mechanism is used to ensure convergence. The simulation results demonstrate that AREA is more effective in improving the robustness of scale-free IoT networks than several existing methods.

With the popularization of Internet of Things (IoT) devices in smart home and industry fields, a huge number of IoT devices are connected to the Internet. However, what devices are connected to a network may not be known by the Internet Service Provider (ISP), since many IoT devices are placed within small networks (e.g., home networks) and are hidden behind network address translation (NAT). Without pinpointing IoT devices in a network, it is unlikely for the ISP to appropriately configure security policies and effectively manage the network. In this paper, we design an efficient and scalable system via spatial-temporal traffic fingerprinting. Our system can accurately identify typical IoT devices in a network, with the additional capability of identifying what devices are hidden behind NAT and how many they are. Through extensive evaluation, we demonstrate that the system can generally identify IoT devices with an F-Score above 0.999, and estimate the number of the same type of IoT device behind NAT with an average error below 5%. We also perform small-scale (labor-intensive) experiments to show that our system is promising in detecting user-IoT interactions.

Large-scale cloud block storage provides virtual disks for various applications and services like online booking, gaming, and offline data analytics. The state-of-the-art URSA [1] block store adopted a hybrid storage structure which placed primary data on solid-state drives (SSDs) and stored backup data on hard-disk drives (HDDs). URSA used small SSD journals to bridge the performance gap between SSDs and HDDs. Although URSA's SSD-HDD-hybrid storage structure achieves SSD-like I/O performance while using only one third of the SSDs required by the SSD-only storage pattern (storing both primary data and backup data on SSDs), we argue that the traditional HDDonly storage structure is still preferable for a large variety of relatively low-end customers and underloaded applications that are sensitive to the per-bit storage cost.To lower the storage cost, in this paper we design URSAL, an HDD-only block store which provides ultra efficiency, reliability, scalability and availability at low cost. Compared to existing block stores such as URSA, Ceph, and Sheepdog, URSAL has the following distinctions. First, URSAL designs the proxy-based storage architecture, where a proxy server process runs together with each virtual machine (VM) client mounting virtual disks and controls the procedure of all block-level I/O. Second, URSAL selectively performs direct block writes on raw HDDs or indirect log appends to HDD journals (which are then asynchronously replayed to raw HDDs), depending on the characteristics of the workloads. Third, URSAL runs one storage server process for each physical HDD, which conservatively has at most one active thread reading/writing the HDD to avoid I/O contention. We have implemented URSAL. Evaluation results show that URSAL significantly outperforms state-of-the-art HDD-only block stores (Ceph and Sheepdog) when providing virtual disks for underloaded applications.

Distributed streaming applications require the underlying network flows to transmit packets continuously to keep their output results fresh. These results will become stale if no updates come, and their staleness is determined by the slowest flow. At this point, coflows can be semantically comprised. Hence, efficient coflow transmission is critical for streaming applications. However, prior coflow-based solutions have significant limitations. They use a one-shot performance metric-CCT (coflow completion time), which cannot continuously reflect the staleness of the output results for a streaming application.To this end, we propose a new performance metric-coflow age (CA), for coflows generated by distributed streaming applications. The CA tracks the longest time-since-last-service among all flows in a coflow. In such a context, we consider a data center network with multiple coflows that continuously transmit packets between their source-destination pairs and address the problem of minimizing the average long-term CA while simultaneously satisfying the throughput constraints from the coflows. To solve this problem efficiently, we design a randomized algorithm and a drift-plus-age algorithm, and show that they can make the average long-term CA to achieve nearly two times and arbitrarily close to the optimal value, respectively. Through extensive simulations, we further demonstrate that both of the proposed algorithms can significantly reduce the CA of coflows, without violating the throughput requirement of any coflow, when compared to the state-of-the-art solution.

Routing policy configuration plays a crucial role in determining the path that network traffic takes to reach a destination. Network administrators/operators typically decide the routing policy for their networks/routers independently. The paths/routes resulted from these independently configured routing policies might not necessarily meet the intent of the network administrators/operators. Even the very basic networkwide properties of the routing policies such as reachability between a pair of nodes need to be verified.In this paper, we propose a scheme that characterizes routingpolicy verification problems into a Satisfiability Modulo Theories (SMT) problems. The key idea is to formulate the SMT model in a policy-aware manner so as to reduce/eliminate the mutual dependencies between variables as much as possible. Further, we reduce the size of the generated SMT model through pruning. We implement and evaluate the policy-aware model through an outof-box SMT solver. The experimental results show that the policyaware model can reduce the time it takes to perform verification by as much as 100x even under a modest topology size. It takes only a few minutes to answer a query for a topology containing tens of thousands of nodes.

The interaction among users in different social networks raises deep concern on user privacy, as it may facilitate the assailants to identify user identities by matching the anonymized networks with a correlated sanitized one. Prior arts regarding such de-anonymization problem can be primarily divided into a seeded case or a seedless one, depending on whether or not there are a subset of pre-identified nodes. The seedless case is much more complicated since the adjacency matrix representation of one-hop user relations delivers limited structural information. To address this issue, we, for the first time, integrate the multi-hop neighborhood relationships, which exhibit more structural commonness between the anonymized and the sanitized networks, into seedless de-anonymization process. Our aim is to sufficiently leverage these multi-hop neighbors of all nodes and minimize the total disagreements of these multi-hop adjacency matrices, which we call collective adjacency disagreements (CADs), between two networks of different sizes. Theoretically, we demonstrate that CAD enlarges the difference between wrongly matched node pairs and correctly matched pairs, whereby two networks can be correctly matched with high probability even when the network density is below logn. Algorithmically, we adopt the conditional gradient descending method on a collective-form objective, which can efficiently find the minimal CADs for networks with broad degree distributions. Experiments on both synthetic and realworld networks return desirable de-anonymization accuracies thanks to the rich structural information manifested by such collectiveness, since most nodes can be correctly matched with their correspondences, especially in sparse networks where merely utilizing adjacency relations might fail to work.