INFOCOM 2019 论文列表

This paper considers the following fundamental maximum throughput routing problem: given a set of k (splittable) multicommodity flows with equal demands in an n-node network, select and route a subset of flows such that the total number of commodities routed that satisfy their demands (i.e., the allor-nothing throughput) is maximized. Our main contribution is the first constant (i.e., independent of k and n) through-putapproximation algorithm for this NP-hard problem, with sublin-ear, namely Õ(√k), edge capacity violation ratio. Our algorithm is based on a clever application of randomized rounding. We also present an interesting application of our result in the context of delay-tolerant network scheduling. We complement our theoretical contribution with extensive simulation in two different scenarios, and find that our algorithm performs significantly better than predicted in theory, achieving an edge capacity violation ratio of at most 3.

The notions of softwarization and virtualization of the radio access network (RAN) of next-generation (5G) wireless systems are ushering in a vision where applications and services are physically decoupled from devices and network infrastructure. This crucial aspect will ultimately enable the dynamic deployment of heterogeneous services by different network operators over the same physical infrastructure. RAN slicing is a form of 5G virtualization that allows network infrastructure owners to dynamically “slice” and “serve” their network resources (i. e., spectrum, power, antennas, among others) to different mobile virtual network operators (MVNOs), according to their current needs. Once the slicing policy (i.e., the percentage of resources assigned to each MVNO) has been computed, a major challenge is how to allocate spectrum resources to MVNOs in such a way that (i) the slicing policy defined by the network owner is enforced; and (ii) the interference among different MVNOs is minimized. In this article, we mathematically formalize the RAN slicing enforcement problem (RSEP) and demonstrate its NP-hardness. For this reason, we design three approximation algorithms that render the solution scalable as the RSEP increases in size. We extensively evaluate their performance through simulations and experiments on a testbed made up of 8 software-defined radio peripherals. Experimental results reveal that not only do our algorithms enforce the slicing policies, but can also double the total network throughput when intra-MVNO power control policies are used in conjunction.

Wireless rechargeable sensor networks (WRSNs), benefiting from recent breakthrough in wireless power transfer (WPT) technology, emerge as very promising for network lifetime extension. Traditional methods focus on scheduling algorithms and system optimization, and the issue of charging security/threat is ignored, causing it vulnerable to attacks. In this paper, we develop a novel attack for WRSN through Denial of Charge (DoC) aiming at maximizing destructiveness. At first, we form a generalized on-demand charging model, which provides fundamental basis for designing charging attacks. Then a request prediction method (RPM) is introduced for predicting the emergences of charging requests. Afterwards, a Collaborative DoC attacking algorithm (CoDoC) is developed, which tempers/modifies and generates fake charging requests, yielding normal nodes exhausted. Finally, to demonstrate the outperformed features of CoDoC, extensive simulations and test-bed experiments are conducted. The results show that, CoDoC outperforms in making sensor exhausted as well as causing missing events.

This paper describes the architecture and performance of ORACLE, an approach for detecting a unique radio from a large pool of bit-similar devices (same hardware, protocol, physical address, MAC ID) using only IQ samples at the physical layer. ORACLE trains a convolutional neural network (CNN) that balances computational time and accuracy, showing 99% classification accuracy for a 16-node USRP X310 SDR testbed and an external database of >100 COTS WiFi devices. Our work makes the following contributions: (i) it studies the hardware-centric features within the transmitter chain that causes IQ sample variations; (ii) for an idealized static channel environment, it proposes a CNN architecture requiring only raw IQ samples accessible at the front-end, without channel estimation or prior knowledge of the communication protocol; (iii) for dynamic channels, it demonstrates a principled method of feedback-driven transmitter-side modifications that uses channel estimation at the receiver to increase differentiability for the CNN classifier. The key innovation here is to intentionally introduce controlled imperfections on the transmitter side through software directives, while minimizing the change in bit error rate. Unlike previous work that imposes constant environmental conditions, ORACLE adopts the `train once deploy anywhere' paradigm with near-perfect device classification accuracy.

Spectrum defragmentation (DF) as a connection reconfiguration method is essential in elastic optical networks (EONs) in order to minimize connection blocking probability. This paper proposes the first exact Markov model to computing exact blocking probabilities in EONs with DF by taking into account the occupancy status of spectrum slices of all network links, and waiting and serving connections during a DF process. Since the complexity of the exact Markov model increases exponentially with the network capacity and size, we propose a reduced state model where a link occupancy state is defined by the total occupied slices on a fiber link. Furthermore, using a spectrum fragmentation factor in each occupancy state we calculate state-and class-dependent connection setup rates, which is used to compute approximate blocking in EONs with DF. Notably, we show individually the distinct blocking values, one due to resource unavailability and the other due to fragmentation, both under a random-fit and a first-fit spectrum allocation policies. Our numerical results show that the DF process is very useful in reducing overall connection blocking in EONs. We also observe that blocking due to spectrum fragmentation can be reduced, but not eliminated in a mesh network topology even when an optimal DF scheme is deployed.

This work proposes an innovative approach, named CapJack, to detect in-browser malicious cryptocurrency mining activities by using the latest CapsNet technology. To the best of our knowledge, this is the first work to introduce CapsNet to the field of malware detection through system behavioral analysis. It is particularly effective to detect malicious miners under multitasking environments where multiple applications run simultaneously. Experimental data show appealing performance of CapJack, with a detection rate of as high as 87% instantly and 99% within a window of 11 seconds.

In a network, a tunnel is a part of a path where a protocol is encapsulated in another one. A tunnel starts with an encapsulation and ends with the corresponding decapsulation. Several tunnels can be nested at some stage, forming a protocol stack. Tunneling is very important nowadays and it is involved in several tasks: IPv4/IPv6 transition, VPNs, security (IPsec, onion routing), etc. However, tunnel establishment is mainly performed manually or by script, which present obvious scalability issues. Some works attempt to automate a part of the process (e.g., TSP, ISATAP, etc.). However, the determination of the tunnel(s) endpoints is not fully automated, especially in the case of an arbitrary number of nested tunnels. The lack of routing protocols performing automatic tunneling is due to the unavailability of path computation algorithms taking into account encapsulations and decapsulations. There is a polynomial centralized algorithm to perform the task. However, to the best of our knowledge, no fully distributed path computation algorithm is known. Here, we propose the first fully distributed algorithm for path computation with automatic tunneling, i.e., taking into account encapsulation, decapsulation and conversion of protocols. Our algorithm is a generalization of the distributed Bellman-Ford algorithm, where the distance vector is replaced by a protocol stack vector. This allows to know how to route a packet with some protocol stack. We prove that the messages size of our algorithm is polynomial, even if the shortest path can be of exponential length. We also prove that the algorithm converges after a polynomial number of steps in a synchronized setting. We adapt our algorithm into aproto-protocol for routing with automatic tunneling and we show its efficiency through simulations.

The correctness of network protocol implementations is difficult to test mainly because of the temporal uncertain nature of network events. In order to test the correctness of a network protocol implementation using network simulators, we need to systematically simulate the behavior of the network protocol under all possible cases of temporal uncertain events, which is very time consuming. The recently proposed Symbolic Execution based Interval Branching (SEIB) simulates a group of uncertain cases together in a single simulation branch, and thus is more efficient than brute force testing. In this paper, we argue that the efficiency of SEIB could be further exponentially improved by eliminating unnecessary comparisons of the event timestamps. Specifically, we summarize and present three general types of unnecessary comparisons when SEIB is applied to a general network simulator, and then correspondingly propose three novel techniques to eliminate them. Our extensive simulations show that our techniques can improve the efficiency of SEIB by several orders of magnitude, such as from days to minutes.

To ensure the reliability of the Internet-based application services, KPIs (Key Performance Monitors) are closely monitored in real time and the anomalies presented in the KPIs must be discovered in time. While anomaly detection for the seasonal smooth service-level KPIs (e.g., number of transactions per minute) have been solved reasonably well in the literature, the intricate KPIs at the machine level (e.g., the number of I/O requests on a server monitored per second) has been little studied. These intricate KPIs are prevalent and important, but exhibit non-Gaussian noises and complex data distribution that are hard to model. In this paper, we propose an adversarial training method in the Bayesian network based on partition analysis with solid theoretical proof. Based on it, we propose the first unsupervised anomaly detection algorithmBuzz for intricate KPIs with high performance. Its best F-scores on the data from a global Internet company range from 0.92 to 0.99, significantly outperforming a state-of-art VAE-based unsupervised approach without adversarial training and a state-of-art supervised approach.

LTE-U is an extension of the Long Term Evolution (LTE) standard for operation in unlicensed spectrum. LTE-U differs from WiFi, the predominant technology used in unlicensed spectrum in that it utilizes a duty cycle mode for accessing the spectrum and allows for a more seamless integration with LTE deployments in licensed spectrum. There have been a number of technical studies on the co-existence of LTE-U and WiFi in unlicensed spectrum In this paper, we instead investigate the impact of such a technology from an economic perspective. We consider a model in which an incumbent service provider (SP) deploys a duty cycle-based technology like LTE-U in an unlicensed band along with operating in a licensed band and competes with one or more entrants that only operate in the unlicensed band using a different technology like WiFi. We characterize the impact of a technology like LTE-U on the market outcome and show that the welfare impacts of this technology are subtle, depending in part on the amount of unlicensed spectrum and number of entrants. We also investigate the impact of the duty cycle and the portion of unlicensed spectrum used by the technology.

In this paper, we consider a wireless powered backscatter communication (WPBC) network in which a full-duplex access point (AP) simultaneously transmits information and energy signals by injecting artificial noise (AN) to secure the backscatter transmission from multiple backscatter devices (BDs). To maximize the minimum throughput and ensure fairness and security, we formulate an optimization problem by jointly considering the power splitting ratio between dedicated information signals and AN, backscatter time and signal power allocation among multiple BDs. For a single BD network, we obtain a closed-form solution and evaluate its validity through proof-of-concept experiments. For the general case with multiple BDs, we present an iterative algorithm by leveraging block coordinate descent (BCD) and successive convex approximation optimization to solve a non-convex problem incurred in WPBC. We further show the convergence of the proposed algorithm and analyze its complexity. Finally, extensive simulation results show that the proposed algorithm achieves an optimal and equitable throughput for all BDs, and our work provides a good perspective of resource allocation to improve the performance of WPBC networks.

In a cognitive radio-based network (CRN), secondary users opportunistically access underutilized spectrum resources and stop utilizing these resources when licensed or primary users reappear. Recently, a new attack, off-sensing (OS), has shed light on a vulnerability in the FCC policy of CRN. OS-attack utilizes the off-sensing interval of a victim to perpetrate the attack and to manipulate the victim's spectrum availability. However, prior work on OS-attack considers a deterministic approach that is unrealistic and is futile to fortify against conventional defense techniques. In this paper, we propose a new random approach, the random-OS attack, which adapts to realistic scenarios and is difficult to detect using conventional techniques. Then, we propose a novel safeguard approach based on the Markov decision process to defend the proposed attack, namely hide and seek. We also introduce an OS-attack detection strategy, which utilizes the sensing history to detect the presence of attackers without violating any policy or design constraints and without any networking overhead. Mathematical analysis and extensive simulation results exhibit the superior performance of our proposed works and advent a direction in designing safeguard strategies without amending the current FCC policies.

This paper focuses on helping network providers to carry out network capacity planning and sales projection by answering the question: For a given topology and capacity, whether the network can serve current flow demands with high probabilities? We name such probability as “ flow availability” and present the -flow availability estimation (FAVE) problem, which is a generalisation of network connectivity or maximum flow reliability estimations. Realistic networks are often large and dynamic, so flow availabilities cannot be evaluated analytically and simulation is often used. However, naive Monte Carlo (MC) or importance sampling (IS) techniques take an excessive amount of time. To quickly estimate flow availabilities, we utilize the correlations among link and flow failures to figure out the importance of roles played by different links in flow failures, and design three “sequential importance sampling” (SIS) methods which achieve “bounded or even vanishing relative error” with linear computational complexities. When applying to a realistic network, our method reduces the flow availability estimation cost by 900 and 130 times compared with MC and baseline IS methods, respectively. Our method can also facilitate capacity planning by providing better flow availability guarantees, compared with traditional methods.

As the volume of traffic flows surges, providing Quality-of-Service (QoS) guarantees to flows by fair queueing has never been more challenging in Network Function Virtualization (NFV). There has been a recent effort in both industry and academia to develop fair queueing algorithms across multiple resources in NFV. However, all existing works fail to support hierarchical scheduling, a crucial feature that also provides QoS guarantees to grouped flows on tenant boundaries. In this paper, we present two new multi-resource fair queueing algorithms that support hierarchies, collapsed Hierarchical Dominant Resource Fair Queueing (collapsed H-DRFQ) and dove-tailing H-DRFQ, both of which provide hierarchical share guarantees. Through formal analysis, we find that the dove-tailing H-DRFQ outper-forms collapsed H-DRFQ by providing a smaller delay bound. However, according to the simulation results, both algorithms have their pros and cons. Dove-tailing H-DRFQ benefits to the flows with more complex hierarchies, while collapsed H-DRFQ is better for the flows with simpler attribution structures. Meanwhile, our simulation shows that both H-DRFQ algorithms can achieve near-perfect fairness.

We study a multi-agent partially observable environment in which autonomous agents aim to coordinate their actions, while also learning the parameters of the unknown environment through repeated interactions. In particular, we focus on the role of communication in a multi-agent reinforcement learning problem. We consider a learning algorithm in which agents make decisions based on their own observations of the environment, as well as the observations of other agents, which are collected through communication between agents. We first identify two potential benefits of this type of information sharing when agents' observation quality is heterogeneous: (1) it can facilitate coordination among agents, and (2) it can enhance the learning of all participants, including the better informed agents. We show however that these benefits of communication depend in general on its timing, so that delayed information sharing may be preferred in certain scenarios.

In this paper, we study online deadline-aware task dispatching and scheduling in edge computing. We jointly consider management of the networking bandwidth and computing resources to meet the maximum number of deadlines. We propose an online algorithm Dedas, which greedily schedules newly arriving tasks and considers whether to replace some existing tasks in order to make the new deadlines satisfied. We derive a non-trivial competitive ratio theoretically, and our analysis is asymptotically tight. We then build DeEdge, an edge computing testbed installed with typical latency-sensitive applications such as IoT sensor monitoring and face matching. Besides, we adopt a real-world data trace from the Google cluster for large-scale emulations. Extensive testbed experiments and simulations demonstrate that the deadline miss ratio of Dedas is stable for online tasks, which is reduced by up to 60% compared with state-of-the-art methods. Moreover, Dedas performs well in minimizing the average task completion time.

Least-recently-used (LRU) caching and its variants have conventionally been used as a fundamental and critical method to ensure fast and efficient data access in computer and communication systems. Emerging data-intensive applications over unreliable channels, e.g., mobile edge computing and wireless content delivery networks, have imposed new challenges in optimizing LRU caching systems in environments prone to failures. Most existing studies focus on reliable channels, e.g., on wired Web servers and within data centers, which have already yielded good insights with successful algorithms on how to reduce cache miss ratios. Surprisingly, we show that these widely held insights do not necessarily hold true for unreliable channels. We consider a single-hop multi-cache distributed system with data items being dispatched by random hashing. The objective is to achieve efficient cache organization and data placement. The former allocates the total memory space to each of the involved caches. The latter decides data routing strategies and data replication schemes. Analytically we characterize the unreliable LRU caches by explicitly deriving their asymptotic miss probabilities. Based on these results, we optimize the system design. Remarkably, these results sometimes are counterintuitive, differing from the ones obtained for reliable caches. We discover an interesting phenomenon: asymmetric cache organization is optimal even for symmetric channels. Specifically, even when channel unreliability probabilities are equal, allocating the cache spaces unequally can achieve a better performance. We also propose an explicit unequal allocation policy that outperforms the equal allocation. In addition, we prove that splitting the total cache space into separate LRU caches can achieve a lower asymptotic miss probability than resource pooling that organizes the total space in a single LRU cache. These results provide new and even counterintuitive insights that motivate novel designs for caching systems over unreliable channels. They can potentially be exploited to further improve the system performance in real practice.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacity of each server or path implies the distribution by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power hungry and are often also required for other tasks such as classification and routing. For splitting a universe of 2Waddresses into k pieces of particular sizes, we give a simple algorithm that computes an optimal representation in Õ(Wk) time. Furthermore, we prove that a recently published load balancer, called Niagara, which also runs in Õ(W k) time is in fact optimal. That is, both our algorithm and Niagara produce the smallest possible TCAM that splits the traffic exactly to the required pieces, where the only previously known algorithm for computing optimal exact representation has running time exponential in k. Finally, we rely on our optimal Õ(Wk) runtime algorithm to investigate through extensive experiments the amount of TCAM memory required to represent traffic splitting in typical scenarios.

Routing and flooding are important functions in wireless networks. However, until now routing and flooding protocols are investigated separately within the same network (i.e., a WiFi network or a ZigBee network). Moreover, further performance improvement has been hampered by the assumption of the harmful cross technology interference. In this paper, we present coexistent routing and flooding (CRF), which leverages the unique feature of physical layer cross-technology communication technique for concurrently conducting routing within the WiFi network and flooding among ZigBee nodes using a single stream of WiFi packets. We extensively evaluate our design under different network settings and scenarios. The evaluation results show that CRF i) improves the throughput of WiFi networks by 1.2 times than the state-of-the-art routing protocols; and ii) significantly reduces the flooding delay in ZigBee networks (i.e., 31 times faster than the state-of-the-art flooding protocol).