INFOCOM 2016 论文列表

Parallel systems have received increasing attention with numerous recent applications such as fork-join systems, load-balancing, and l-out-of-k redundancy. Common to these systems is a join or resequencing stage, where tasks that have finished service may have to wait for the completion of other tasks so that they leave the system in a predefined order. These synchronization constraints make the analysis of parallel systems challenging and few explicit results are known. In this work, we model parallel systems using a max-plus approach that enables us to derive statistical bounds of waiting and sojourn times. Taking advantage of max-plus system theory, we also show end-to-end delay bounds for multi-stage fork-join networks. We contribute solutions for basic G|G|1 fork-join systems, parallel systems with load-balancing, as well as general (k, l) fork-join systems with redundancy. Our results provide insights into the respective advantages of l-out-of-k redundancy vs. load-balancing.

Using a connected dominating set (CDS) to serve as a virtual backbone of a wireless sensor network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). A subset of nodes C ⊆ V(G) is a (k, m)-CDS of G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. In this paper, we present an approximation algorithm for the minimum (3, m)-CDS problem with m > 3, which has size at most γ times that of an optimal solution, where γ = α + 8 + 21n(2α - 6) for α > 4 and γ = 3α + 2 In 2 for α <; 4, and α is the approximation ratio for the minimum (2, m)-CDS problem. This is the first performance-guaranteed algorithm for the minimum (3, m)-CDS problem in a general wireless network, and improves previous performance ratio in a homogeneous wireless sensor network by a large amount.

Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and additional operational costs. However, some routers are able to encapsulate, decapsulate and convert protocols and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and automate the routing configurations. Software-Defined Networking (SDN) based architectures, such as OpenFlow, offer a chance to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem and study several cases: Path computation without bandwidth constraint, under bandwidth constraint and under other Quality of Service constraints. We study the complexity and the scalability of our algorithms and evaluate their performances on real topologies. The results show that they outperform the previous ones proposed in the literature.

Wi-Fi Direct, now part of Android smartphones, makes it possible for Wi-Fi devices to communicate directly without passing through an access point. Before starting actual data exchange, two devices should apparently find each other through a device discovery process, called find phase. After identifying the limitation of the legacy find phase, incurring long discovery delay, we propose a simple and efficient scheme, called Listen Channel Randomization (LCR), in order to expedite device discovery. Both the legacy find phase and LCR are evaluated with our elaborate Markov model and ns-3 simulations for comprehensive comparisons. Moreover, we have implemented a prototype of LCR in Android smartphone. Our experimental results reveal that LCR can significantly reduce the device discovery delay, yielding up to 72% delay reduction compared to the legacy find phase.

The future Internet of Things (IoT) networks are expected to be composed of a large population of low-cost devices communicating dynamically with access points or neighboring devices to communicate small bundles of delay-sensitive data. To support the high-intensity and short-lived demands of these emerging networks, we propose an Efficient MAC paradigm for IoT (EMIT). Our paradigm bypasses the high overhead and coordination costs of existing MAC solutions by employing an interference-averaging strategy that allow users to share their resources simultaneously. In contrast to the predominant interference-suppressing approaches, EMIT exploits the dense and dynamic nature of IoT networks to reduce the spatio-temporal variability of interference to achieve low-delay and high-reliability in service. This paper introduces foundational ideas of EMIT by characterizing the global interference statistics in terms of single-device operation and develops power-rate allocation strategies to guarantee low-delay high-reliability performance. A significant portion of our work is aimed at validating these theoretical principles in experimental testbeds, where we compare the performance of EMIT to a CSMA-based MAC protocol. Our comparisons confirm the beneficial characteristics of EMIT, and reveal significant gains over CSMA strategies in the case of IoT traffic.

Owing to the proliferation of mobile devices and their corresponding app ecosystems, more and more people are accessing the internet via various mobile apps, which generates tremendous volume of mobile data. Despite the growing importance of these mobile apps, we have a rather sparse understanding of how they are accessed and what issues affect their usage patterns. To address this problem, we perform a comprehensive measurement on large-scale anonymized network data collected from a tier-1 cellular carrier in China. In this measurement, we characterize the usage pattern of mobile apps and exhibit how the mobility, geospatial properties and behaviours of subscribers affect their mobile app usage at a fine-grained level.

Increasing popularity of mobile devices and upload-intensive applications is rapidly driving the uplink traffic demand in wireless LANs. Network MIMO (netMIMO) can potentially meet the demand by enabling concurrent uplink transmissions to an AP cluster (APC) comprised of multiple access points. NetMIMO's PHY-layer communication algorithms have been well explored, but the MAC-level signaling procedure remains an open issue: prior to uplink transmission, a group of clients must gain channel access, and ensure synchronization and channel orthogonality with each other. But such signaling is fundamentally challenging, because netMIMO clients tend to be widely distributed and may not even sense each other. In this paper, we introduce the first signaling protocol, called NURA, to meet the challenge. NURA clients employ a novel medium-access-signaling mechanism to realize group-based random access and synchronization, without disturbing ongoing uplink transmissions. The APC leverages a lightweight user-admission mechanism to group users with orthogonal channels (and hence high uplink capacity), without requiring costly channel-state feedback from all users. We have implemented NURA on a software-radio based netMIMO platform. Our experiments show that NURA is feasible, efficient, and can readily serve as the a priori signaling mechanism for distributed asynchronous netMIMO clients.

The Poisson building features a Poisson collection of random planes orthogonal to the axes of the 3-D Euclidean space. It divides the space into rectangular rooms of random sizes. The addition of wireless small cell base stations, deployed as Poisson point processes along the ceiling and corner lines of these rooms, provides a first stochastic geometric model representing in-building 3-D wireless networks. The main challenge for analyzing interference in such an environment is the fact that electromagnetic signals originating from different locations are blocked by common obstacles like walls and floors, which makes the path loss highly correlated in space. We propose a natural propagation model taking this phenomenon into account. We give analytical expressions for the interference field and its correlation within this framework. We illustrate the tractability of this model by providing analytical expressions for the spectral efficiency of the downlink in such indoor cellular networks and for D2D communications in such an environment. We combine the model and spatial simulations to show that classical 2-D and distance based attenuation models cannot be used in this context and to argue for the need of such 3-D models to assess the performance of this type of indoor communications.

Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E| = O(|V|2)) based on a traffic matrix, the time complexity is actually O(|E|3 = |V|6). If we were allowed to reduce this dense network into a sparse one before embedding, the time complexity could be decreased to O(|V|3); the time gap can be a million times for |V| = 100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction algorithms and analyze them with several interesting theorems. The analysis indicates that the embedding cost increases only linearly with exponential decay of embedding time. Thorough numerical evaluation justifies the desirability of the trade-off.

Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs' resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs' resource demands. Most approaches in the latter category are heuristical and lack theoretical performance guarantees. In this work, we formulate dynamic VM management as a large-scale Markov Decision Process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, MadVM can be implemented in a distributed system, which should suit the needs of real data centers. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.

Today's cloud is shared among multiple tenants running different applications, and a desirable multi-tenant datacenter network infrastructure should provide bandwidth guarantees for throughput-intensive applications, low latency for latency-sensitive short messages, as well as work conservation to fully utilize the network bandwidth. Despite significant efforts in recent years, none of them can achieve these three properties simultaneously. In this paper, we identify the key deficiency of prior solutions and use this insight to motivate our design of Trinity - a simple, practical yet effective solution that achieves bandwidth guarantees, work conservation and low latency simultaneously in the cloud. We implement Trinity using existing commodity hardwares and demonstrate its superior performance over prior solutions using testbed experiments.

Inspired by cognitive radio networks, we consider a setting where multiple users share several channels modeled as a multi-user multi-armed bandit (MAB) problem. The characteristics of each channel are unknown and are different for each user. Each user can choose between the channels, but her success depends on the particular channel chosen as well as on the selections of other users: if two users select the same channel their messages collide and none of them manages to send any data. Our setting is fully distributed, so there is no central control. As in many communication systems, the users cannot set up a direct communication protocol, so information exchange must be limited to a minimum. We develop an algorithm for learning a stable configuration for the multi-user MAB problem. We further offer both convergence guarantees and experiments inspired by real communication networks, including comparison to state-of-the-art algorithms.

With the popular applications of SDN in load balancing and failure recovery, the controller schedules affected flows to redundant paths to avoid network congestions and failures by updating flow tables in data plane. However, inconsistent flow table updating may lead to transient incorrect network behaviors or undesired performance degradation. Therefore, the consistency imposes dependencies among updates, so that the order of updates must be carefully considered to keep the consistency. To update flow tables consistently and efficiently, in this paper, we propose an update ordering approach — Cupid. To avoid high overhead in update ordering, we divide the global dependencies among updates into local restrictions by: 1) partitioning a new routing path into several independent segments, 2) identifying critical nodes controlling traffic shifting between the old path and new path, and 3) constructing a dependency graph among critical nodes for potential congested links. We then design a heuristic algorithm to resolve the dependency graph. To save the flow table space, a switch keeps only one flow entry with multiple ports for a flow during updating. Our simulation shows that Cupid schedules updates at least 2 times faster and has less throughput losses than the state-of-the-art approaches in both fat-tree and mesh networks.

Modern mobile devices are equipped with multiple antennas, which brings various wireless sensing applications such as accurate localization, contactless human detection and wireless human-device interaction. A key enabler for these applications is phased array signal processing, especially Angle of Arrival (AoA) estimation. However, accurate AoA estimation on commodity devices is non-trivial due to limited number of antennas and uncertain phase offsets. Previous works either rely on elaborate calibration or involve contrived human interactions. In this paper, we aim to enable practical AoA measurements on commodity off-the-shelf (COTS) mobile devices. The key insight is to involve users' natural rotation to formulate a virtual spatial-temporal antenna array and conduce a relative incident signal of measurements at two orientations. Then by taking the differential phase, it is feasible to remove the phase offsets and derive the accurate AoA of the equivalent incoming signal, while the rotation angle can also be captured by built-in inertial sensors. On this basis, we propose Differential MUSIC (D-MUSIC), a relative form of the standard MUSIC algorithm that eliminates the unknown phase offsets and achieves accurate AoA estimation on COTS mobile devices with only one rotation. We further extend D-MUSIC to 3-D space and fortify it in multipath-rich scenarios. We prototype D-MUSIC on commodity WiFi infrastructure and evaluate it in typical indoor environments. Experimental results demonstrate a superior performance with an average AoA estimation error of 13°. Requiring no modifications or calibration, D-MUSIC is envisioned as a promising scheme for practical AoA estimation on COTS mobile devices.

In a number of RFID-based applications such as logistics monitoring, the RFID systems are deployed to monitor a large number of RFID tags. They are usually required to track the movement of all tags in a real-time approach, since the tagged-goods are moved in and out in a rather frequent approach. However, a typical cycle of tag inventory in COTS RFID system usually takes tens of seconds to interrogate hundreds of RFID tags. This hinders the system to track the movement of all tags in time. One critical issue in such type of tag monitoring is to efficiently distinguish the motion status of all tags, i.e., stationary or moving. According to the motion status of different tags, the state-of-art localization schemes can further track those moving tags, instead of tracking all tags. In this paper, we propose a real-time approach to detect the moving tags in the monitoring area, which is a fundamental premise to support tracking the movement of all tags. We achieve the time efficiency by decoding collisions from the physical layer. Instead of using the EPC ID, which cannot be decoded in collision slots, we are able to extract two kinds of physical-layer features of RFID tags, i.e., the phase profile and the backscatter link frequency, to distinguish among different tags in different positions. By resolving the two physical-layer features from the tag collisions, we are able to derive the motion status of multiple tags simultaneously, and greatly improve the time-efficiency. Experiment result shows that our solution can accurately detect the moving tags while reducing 80% of inventory time compared with the state-of-art solutions.

Software Defined Networking (SDN) has recently emerged as a new network management platform. The centralized control architecture presents many new opportunities. Among the network management tasks, measurement is one of the most important and challenging one. Researchers have proposed many solutions to better utilize SDN for network measurement. Among them, how to detect Distributed Denial-of-Services (DDoS) quickly and precisely is a very challenging problem. In this paper, we propose methods to detect DDoS attacks leveraging on SDN's flow monitoring capability. Our methods utilize measurement resources available in the whole SDN network to adaptively balance the coverage and granularity of attack detection. Through simulations we demonstrate that our methods can quickly locate potential DDoS victims and attackers by using a constrained number of flow monitoring rules.

There have been recent attempts to develop scheduling schemes for downlink transmission in a single cell of a multi-channel (e.g., OFDM-based) cellular network. These works have been quite promising in that they have developed low-complexity index scheduling policies that are delay-optimal (in a large deviation rate-function sense). However, these policies require that the channel is ON or OFF in each time-slot with a fixed probability (i.e., there is no memory in the system), while the reality is that due to channel fading and doppler shift, channels are often time-correlated in these cellular systems. Thus, an important open question is whether one can find simple index scheduling policies that are delay-optimal even when the channels are time-correlated. In this paper, we attempt to answer this question for time-correlated ON/OFF channels. In particular, we show that the class of oldest packets first (OPF) policies that give a higher priority to packets with a large delay is delay rate-function optimal under two conditions: 1) The channel is non-negatively correlated, and 2) The distribution of the OFF period is geometric. We use simulations to further elucidate the theoretical results.

Wireless underground sensor networks (WUSNs) are becoming ubiquitous in many areas and designing robust systems requires extensive understanding of the underground (UG) channel characteristics. In this paper, UG channel impulse response is modeled and validated via extensive experiments in indoor and field testbed settings. Three distinct types of soils are selected with sand and clay contents ranging from 13% to 86% and 3% to 32%, respectively. Impacts of changes in soil texture and soil moisture are investigated with more than 1,200 measurements in a novel UG testbed that allows flexibility in soil moisture control. Time domain characteristics of channel such as RMS delay spread, coherence bandwidth, and multipath power gain are analyzed. The analysis of the power delay profile validates the three main components of the UG channel: direct, reflected, and lateral waves. It is shown that RMS delay spread follows a log-normal distribution. The coherence bandwidth ranges between 650 kHz and 1.15MHz for soil paths of up to 1m and decreases to 418 kHz for distances above 10m. Soil moisture is shown to affect RMS delay spread non-linearly, which provides opportunities for soil moisture-based dynamic adaptation techniques. The model and analysis paves the way for tailored solutions for data harvesting, UG sub-carrier communication, and UG beamforming.

Many companies now use crowdsourcing to leverage external (as well as internal) crowds to perform specialized work, and so methods of improving efficiency are critical. Tasks in crowdsourcing systems with specialized work have multiple steps and each step requires multiple skills. Steps may have different flexibilities in terms of obtaining service from one or multiple agents, due to varying levels of dependency among parts of steps. Steps of a task may have precedence constraints among them. Moreover, there are variations in loads of different types of tasks requiring different skill-sets and availabilities of different types of agents with different skill-sets. Considering these constraints together necessitates the design of novel schemes to allocate steps to agents. In addition, large crowdsourcing systems require allocation schemes that are simple, fast, decentralized and offer customers (task requesters) the freedom to choose agents. In this work we study the performance limits of such crowdsourcing systems and propose efficient allocation schemes that provably meet the performance limits under these additional requirements. We demonstrate our algorithms on data from a crowdsourcing platform run by a non-profit company and show significant improvements over current practice.