INFOCOM 2019 论文列表

This paper studies the problem of allocating band-width and computation resources to data analytics tasks in Internet of Things (IoT) networks. IoT nodes are powered by batteries, can process (some of) the data locally, and the quality grade or performance of how data analytics tasks are carried out depends on where these are executed. The goal is to design a resource allocation algorithm that jointly maximizes the network lifetime and the performance of the data analytics tasks subject to energy constraints. This joint maximization problem is challenging with coupled resource constraints that induce non-convexity. We first show that the problem can be mapped to an equivalent convex problem, and then propose an online algorithm that provably solves the problem and does not require any a priori knowledge of the time-varying wireless link capacities and data analytics arrival process statistics. The algorithm's optimality properties are derived using an analysis which, to the best of our knowledge, proves for the first time the convergence of the dual subgradient method with time-varying sets. Our simulations seeded by real IoT device energy measurements, show that the network connectivity plays a crucial role in network lifetime maximization, that the algorithm can obtain both maximum network lifetime and maximum data analytics performance in addition to maximizing the joint objective, and that the algorithm increases the network lifetime by approximately 50% compared to an algorithm that minimizes the total energy consumption.

The Multipath TCP (MPTCP) protocol, featured by its ability of capacity aggregation across multiple links and connectivity maintenance against single-path failure, has been attracting increasing attention from the industry and academy. Multipath packet scheduling is a unique and fundamental mechanism for the design and implementation of MPTCP, which is responsible for distributing the traffic over multiple subflows. The existing multipath schedulers are facing the challenges of network heterogeneities, comprehensive QoS goals, and dynamic environments, etc. To address these challenges, we propose ReLeS, a Reinforcement Learning based Scheduler for MPTCP. ReLeS uses modern deep reinforcement learning (DRL) techniques to learn a neural network to generate the control policy for packet scheduling. It adopts a comprehensive reward function that takes diverse QoS characteristics into consideration to optimize packet scheduling. To support real-time scheduling, we propose an asynchronous training algorithm that enables parallel execution of packet scheduling, data collecting, and neural network training. We implement ReLeS in the Linux kernel and evaluate it over both emulated and real network conditions. Extensive experiments show that ReLeS significantly outperforms the state-of-the-art schedulers.

Since Age of Information (AoI) has been proposed as a metric that quantifies the freshness of information updates in a communication system, there has been a constant effort in understanding and optimizing different statistics of the AoI process for classical queueing systems. In addition to classical queuing systems, more recently, systems with no queue or a unit capacity queue storing the latest packet have been gaining importance as storing and transmitting older packets do not reduce AoI at the receiver. Following this line of research, we study the distribution of AoI for the GI/GI/1/1 and GI/GI/1/2* systems, under non-preemptive scheduling. For any single-source-single-server queueing system, we derive, using sample path analysis, a fundamental result that characterizes the AoI violation probability, and use it to obtain closed-form expressions for D/GI/1/1, M/GI/1/1 as well as systems that use zero-wait policy. Further, when exact results are not tractable, we present a simple methodology for obtaining upper bounds for the violation probability for both GI/GI/1/1 and GI/GI/1/2* systems. An interesting feature of the proposed upper bounds is that, if the departure rate is given, they overestimate the violation probability by at most a value that decreases with the arrival rate. Thus, given the departure rate and for a fixed average service, the bounds are tighter at higher utilization.

In-the-cloud middleboxes have drawn widespread attentions recently, along with the rapid advancement of network function virtualization (NFV). Despite the well known benefits like reduced hardware and maintenance cost, deploying middleboxes in the remote environment poses new performance and security concerns, due to invisibility of the untrusted cloud and susceptible software implementations. One essential requirement for enterprise customers is to monitor performance compliance, while ensuring that packets are faithfully processed by remote middleboxes. In this paper, we propose a practical scheme towards verifiable performance measurement over in-the-cloud middleboxes. It employs “sample and replay” to achieve performance measurement and packet processing attestation. It estimates performance by collecting receipts in a tunable way, while coping with dynamic traffic changes made by middleboxes. In particular, our sampling is stateful which can capture a sequence of packets sharing same states of middleboxes for correct local replay. More importantly, it ensures high-confidence packet processing attestation by enforcing middleboxes to bind execution assurances with packets using commitment messages, and by using delayed verification procedure to defeat any potential biased results against selected sampling. To demonstrate the feasibility and efficiency of our scheme, we implement a prototype consisting of various types of middleboxes on Click, and conduct extensive experiments on Amazon EC2 with real traces. The experimental results show that our scheme imposes marginal processing delay for packets with various middleboxes and presents negligible throughput degradation.

Since the early development of Software-Defined Network (SDN) technology, researchers have been concerned with the idea of physical distribution of the control plane to address scalability and reliability challenges of centralized designs. However, having multiple controllers managing the network while maintaining a “logically-centralized” network view brings additional challenges. One such challenge is how to coordinate the management decisions made by the controllers which is usually achieved by disseminating synchronization messages in a peer-to-peer manner. While there exist many architectures and protocols to ensure synchronized network views and drive coordination among controllers, there is no systematic methodology for deciding the optimal frequency (or rate) of message dissemination. In this paper, we fill this gap by introducing the SDN synchronization problem: how often to synchronize the network views for each controller pair. We consider two different objectives; first, the maximization of the number of controller pairs that are synchronized, and second, the maximization of the performance of applications of interest which may be affected by the synchronization rate. Using techniques from knapsack optimization and learning theory, we derive algorithms with provable performance guarantees for each objective. Evaluation results demonstrate significant benefits over baseline schemes that synchronize all controller pairs at equal rate.

DNS poisoning attacks inject malicious entries into the DNS resolution system, allowing an attacker to redirect clients to malicious servers. These attacks typically target a DNS resolver allowing attackers to poison a DNS entry for all machines that use the compromised resolver. However, recent defenses can effectively protect resolvers rendering classical DNS poisoning attacks ineffective. In this paper, we present a new class of DNS poisoning attacks targeting the client-side DNS cache. The attack initiates DNS poisoning on the client cache, which is used in all main stream operating systems to improve DNS performance, circumventing defenses targeting resolvers. Our attack allows an off-path attacker to collaborate with a piece of an unprivileged malware to poison the OS-wide DNS cache on a client machine. We developed the attack on Windows, Mac OS, and Ubuntu Linux. Interestingly, the behaviors of the three operating systems are distinct and the vulnerabilities require different strategies to exploit. We also generalize the attack to work even when the client is behind a Network Address Translation (NAT) router. Our results show that we can reliably inject malicious DNS mappings, with on average, an order of tens of seconds. Finally, we propose a defense against this type of poisoning attacks.

The rise of edge computing gives birth to a spectrum of delay-sensitive applications. Many of these applications build their services atop the functionality that the edge nodes quickly negotiate a unique order on the events received from a massive number of client devices, even under very high event rates. To this end, we propose a protocol, called Nomad, for achieving fast event ordering in edge computing environments. Nomad is designed as a consensus protocol that employs a lease-based approach to take advantage of the locality of the unbalanced workload across the system. It also dynamically adjusts the leadership distribution on the edge nodes based on the recent running history, and relies on a cloud-based arbitrator to resolve contentions. Experiments demonstrate that Nomad outperforms the existing solutions, such as Multi-Paxos, Mencius and E-Paxos, in achieving fast event ordering for large-scale, delay-sensitive edge-cloud applications.

To meet the performance and complexity requirements from practical deployment of non-orthogonal multiple access (NOMA) systems, several users are grouped together for NOMA transmission while orthogonal resources are allocated among groups. User grouping strategies have significant impact on the power consumption and system performance. However, existing related studies divide users into groups based on channel conditions, where diverse quality of service (QoS) and interference have not been considered. In this paper, we focus on the interference-aware user grouping strategy in NOMA systems, aiming at minimizing power consumption with QoS constraints. We define a power consumption and externality (PCE) function for each user to represent the power consumption involved by this user to satisfy its QoS requirement as well as interference that this user brings to others in the same group. Then, we extend the definition of PCE to multi-user scenarios and convert the user grouping problem into the problem of searching for specific negative loops in the graph. Bellman-Ford algorithm is extended to find these negative loops. Furthermore, a greedy suboptimal algorithm is proposed to approach the solution within polynomial time. Simulation results show that the proposed algorithms can considerably reduce the total power consumption compared with existing strategies.

As communication networks are growing at a fast pace, the need for more scalable approaches to operate such networks is pressing. Decentralization and locality are key concepts to provide scalability. Existing models for which local algorithms are designed fail to model an important aspect of many modern communication networks such as software-defined networks: the possibility to precompute distributed network state. We take this as an opportunity to study the fundamental question of how and to what extent local algorithms can benefit from preprocessing. In particular, we show that preprocessing allows for significant speedups of various networking problems. A main benefit is the precomputation of structural primitives, where purely distributed algorithms have to start from scratch. Maybe surprisingly, we also show that there are strict limitations on how much preprocessing can help in different scenarios. To this end, we provide approximation bounds for the maximum independent set problem-which however show that our obtained speedups are asymptotically optimal. Even though we show that physical link failures in general hinder the power of preprocessing, we can still facilitate the precomputation of symmetry breaking processes to bypass various runtime barriers. We believe that our model and results are of interest beyond the scope of this paper and apply to other dynamic networks as well.

The rapid development of network function virtualization (NFV) enables a communication network to provide in-network services using virtual network functions (VNFs) deployed on general IT hardware. While existing studies on NFV focused on how to provision VNFs from the provider's perspective, little is known about how to validate the provisioned resources from the user's perspective. In this work, we take a first step towards this problem by developing an inference framework designed to “look into” the NFV network. Our framework infers the structure and state of the overlay formed by VNF instances, ingress/egress points of measurement flows, and critical points on their paths (branching/joining points). Our solution only uses external observations such as the required service chains and the end-to-end performance measurements. Besides the novel application scenario, our work also fundamentally advances the state of the art on topology discovery by considering (i) general topologies with general measurement paths, and (ii) information of service chains. Evaluations based on real network topologies show that the proposed solution significantly improves the accuracy over existing solutions, and service chaining information is critical in revealing the structure of the underlying topology.

We consider an ad hoc network where multiple users access the same set of channels. The channel characteristics are unknown and could be different for each user (heterogeneous). No controller is available to coordinate channel selections by the users, and if multiple users select the same channel, they collide and none of them receive any rate (or reward). For such a completely decentralized network we develop algorithms that aim to achieve optimal network throughput. Due to lack of any direct communication between the users, we allow each user to exchange information by transmitting in a specific pattern and sense such transmissions from others. However, such transmissions and sensing for information exchange do not add to network throughput. For the wideband sensing and narrowband sensing scenarios, we first develop explore-and-commit algorithms that converge to near-optimal allocation with high probability in a small number of rounds. Building on this, we develop an algorithm that gives logarithmic regret. We validate our claims through extensive experiments and show that our algorithms perform significantly better than the state-of-the-art CSM-MAB, dE3and dE3-TS algorithms.

Managed DNS (MDNS) services today excel at providing a simple and cost-effective way to outsource domain management and ensure rapid lookup times for geo-distributed users. The intense focus on optimizing lookup performance coupled with DNS’ inherent expectations of weak consistency has had unfortunate side effects: updates are inexplicably slow and MDNS providers pay scant attention to consistency correctness. We conduct an empirical measurement-driven study of 8 top-tier managed DNS providers and find that inter-nameserver update propagation delays commonly take tens of seconds with little improvement over the last several years. Client-perceived inconsistency is rampant with roughly a third of end-users being vulnerable to TTL abuse by local DNS resolvers. Furthermore, we find that 6 of the 8 MDNS providers violate monotonic read consistency under frequent updates and at least one large MDNS provider appears to violate even eventual consistency.

Traditional cloud Service Level Agreement (SLA) suffers from lacking a trustworthy platform for automatic enforcement. The emerging blockchain technique brings in an immutable solution for tracking transactions among business partners. However, it is still very challenging to prove the credibility of possible violations in the SLA before recording them onto the blockchain. To tackle this challenge, we propose a witness model using game theory and the smart contract techniques. The proposed model extends the existing service model with a new role called “witness” for detecting and reporting service violations. Witnesses gain revenue as an incentive for performing these duties, and the payoff function is carefully designed in a way that trustworthiness is guaranteed: in order to get the maximum profit, the witness has to always tell the truth. This is analyzed and proved through game theory using the Nash equilibrium principle. In addition, an unbiased sortition algorithm is proposed to ensure the randomness of the independent witnesses selection from the decentralized witness pool, to avoid possible unfairness or collusion. An auditing mechanism is also introduced in the paper to detect potential irrational or malicious witnesses. We have prototyped the system leveraging the smart contracts of Ethereum blockchain. Experimental results demonstrate the feasibility of the proposed model and indicate good performance in accordance with the design expectations.

Recent advances in quality adaptation algorithms leave adaptive bitrate (ABR) streaming architectures at a cross-roads: When determining the sustainable video quality one may either rely on the information gathered at the client vantage point or on server and network assistance. The fundamental problem here is to determine how valuable either information is for the adaptation decision. This problem becomes particularly hard in future Internet settings such as Named Data Networking (NDN) where the notion of a network connection does not exist. In this paper, we provide a fresh view on ABR quality adaptation for QoE maximization, which we formalize as a decision problem under uncertainty, and for which we contribute a sparse Bayesian contextual bandit algorithm denoted CBA. This allows taking high-dimensional streaming context information, including client-measured variables and network assistance, to find online the most valuable information for the quality adaptation. Since sparse Bayesian estimation is computationally expensive, we develop a fast new inference scheme to support online video adaptation. We perform an extensive evaluation of our adaptation algorithm in the particularly challenging setting of NDN, where we use an emulation testbed to demonstrate the efficacy of CBA compared to state-of-the-art algorithms.

The goal of opinion maximization is to maximize the positive view towards a product, an ideology or any entity among the individuals in social networks. So far, opinion maximization is mainly studied as finding a set of influential nodes for fast content dissemination in a social network. In this paper, we propose a novel approach to solve the problem, where opinion maximization is achieved through efficient information spreading. In our model, multiple sources inject information continuously into the network, while the regular nodes with heterogeneous social learning abilities spread the information to their acquaintances through gossip mechanism. One of the sources employs smart information spreading and the rest spread information randomly. We model the social interactions and evolution of opinions as a dynamic Bayesian network (DBN), using which the opinion maximization is formulated as a sequential decision problem. Since the problem is intractable, we develop multiple variants of centralized and decentralized algorithms to obtain approximate solutions. Through simulations in synthetic and real-world networks, we demonstrate two key results: 1) the proposed methods perform better than random spreading by a large margin, and 2) even though the smart source (that spreads the desired content) is unfavorably located in the network, it can outperform the contending random sources located at favorable positions.

Live virtual machine migration technique allows migrating an entire OS with running applications from one physical host to another, while keeping all services available without interruption. It provides a flexible and powerful way to balance system load, save power and tolerant faults in data centers. Meanwhile, with the stringent requirements of latency, scalability, and availability, an increasing number of applications are deployed across distributed cloud data-centers. However, existing live migration approaches still suffer from long downtime and serious performance degradation in cross data-center scenes due to the mass of dirty retransmission, which limits the ability of cross data-center scheduling. In this paper, we propose a system named Memory/disk operation aware Lightweight VM Live Migration across data-centers with low performance impact (MLLM). It significantly improves the cross data-center migration performance by reducing the amount of dirty data in the migration process. In MLLM, we predict disk read workingset (i.e., more frequently read contents) and memory write workingset (i.e., more frequently write contents) based on the access sequence trace. And then we adjust the migration models and data transfer sequence based on the workingset information. We also present two optimizing methods to filter unused blocks and to de-duplicate data content by a hot data cache, thereby greatly decreasing the amount of data to be transferred. We implement MLLM on the QEMU/KVM platform and conduct several real-world experiments. The experimental results show that our method averagely reduces 67.0% of total migration time and 41.6% service downtime over existing methods.

Since the number of cars has grown rapidly in recent years, driving safety draws more and more public attention. Drowsy driving is one of the biggest threatens to driving safety. Therefore, a simple but robust system that can detect drowsy driving with commercial off-the-shelf devices (such as smart-phones) is very necessary. With this motivation, we explore the feasibility of purely using acoustic sensors embedded in smart-phones to detect drowsy driving. We first study characteristics of drowsy driving, and find some unique patterns of Doppler shift caused by three typical drowsy behaviors, i.e., nodding, yawning and operating steering wheel. We then validate our important findings through empirical analysis of the driving data collected from real driving environments. We further propose a real-time Drowsy Driving Detection system (D3-Guard) based on audio devices embedded in smartphones. In order to improve the performance of our system, we adopt an effective feature extraction method based on undersampling technique and FFT, and carefully design a high-accuracy detector based on LSTM networks for the early detection of drowsy driving. Through extensive experiments with 5 volunteer drivers in real driving environments, our system can distinguish drowsy driving actions with an average total accuracy of 93.31% in real-time. Over 80% drowsy driving actions can be detected within first 70% of action duration.

Control plane programmability, primarily enabled by SDN/OpenFlow, has brought new impetus to already consolidated management and planning practices in the area of computer networks. However, applications that require high responsiveness and demand more dynamic mechanisms executing beyond the control plane can only be effectively exploited through interactions with the data plane, where decisions and reactive responses can be made at line rate. P4 achieves this goal by providing directives that allow a certain level of control over the hardware that performs packet forwarding tasks, bringing programmability to the data plane. In this paper, we present a multipath routing strategy that takes full advantage of a hybrid SDN/OpenFlow and P4 architecture. In the data plane, P4 and the Flowlet abstraction are used to actively perform load balancing and routing over multiple asymmetric paths, in addition to monitor active links. In the logically centralized control plane, the overall view of the network is leveraged to perform more elaborate passive tasks, which include mapping paths, configuring devices and updating routes asynchronously. Experimental evaluations are conducted in which we analyze different strategies for choosing the routes that provide the best results based on RTT values received from the switches.

We consider large scale Internet of Things applications requesting data from physical devices. We study the problem of timely dissemination of sensor data towards applications with freshness requirements by means of a cache. We aim to minimize direct access to the possibly battery powered physical devices, yet improving Age of Information as a data freshness metric. We propose an Age of Information-aware scheduling policy for the physical device to push sensor updates to the caches located in cloud data centers. Such policy groups application requests based on freshness thresholds, thereby reduces the number of requests and threshold misses, and accounts for delay variation. The policy is incrementally introduced as we study its behavior over ideal and more realistic communication links with delay variation. We numerically evaluate the proposed policy against a simple yet widely used periodic schedule. We show that our informed schedule outperforms the periodic schedule even under high delay variations.