INFOCOM 2016 Papers

A fundamental problem to all data-parallel applications is data locality. An example is map task scheduling in the MapReduce framework. Existing theoretical work analyzes systems with only two levels of locality, despite the existence of multiple locality levels within and across data centers. We found that going from two to three levels of locality changes the problem drastically, as a tradeoff between performance and throughput emerges. The recently proposed priority algorithm, which is throughput and heavy-traffic optimal for two locality levels, is not even throughput-optimal with three locality levels. The JSQ-MaxWeight algorithm proposed by Wang et al. is heavy-traffic optimal only for a special traffic scenario with two locality levels. We show that an extension of the JSQ-MaxWeight algorithm to three locality levels preserves its throughput-optimality, but suffers from the same lack of heavy-traffic optimality for most traffic scenarios. We propose a novel algorithm that uses Weighted-Workload (WW) routing and priority service. We establish its throughput and heavy-traffic optimality for all traffic scenarios. The main challenge is the construction of an appropriate ideal load decomposition that allows the separate treatment of different subsystems.

WiFi multicast to very large groups has gained attention as a solution for multimedia delivery in crowded areas. Yet, most recently proposed schemes do not provide performance guarantees and none have been tested at scale. To address the issue of providing high multicast throughput with performance guarantees, we present the design and experimental evaluation of the Multicast Dynamic Rate Adaptation (MuDRA) algorithm. MuDRA balances fast adaptation to channel conditions and stability, which is essential for multimedia applications. MuDRA relies on feedback from some nodes collected via a light-weight protocol and dynamically adjusts the rate adaptation response time. Our experimental evaluation of MuDRA on the ORBIT testbed with over 150 nodes shows that MuDRA outperforms other schemes and supports high throughput multicast flows to hundreds of receivers while meeting quality requirements. MuDRA can support multiple high quality video streams, where 90% of the nodes report excellent or very good video quality.

The model is a “generalized switch”, serving multiple traffic flows in discrete time. The switch uses MaxWeight algorithm to make a service decision (scheduling choice) at each time step, depending on the current queue lengths. In some applications, it is not important to keep the queue lengths/delays small (e.g., when queues are virtual, rather than physical), but is important that the service processes provided to each flow remains “smooth” (i.e., without large gaps in service) even when the switch is heavily loaded. Addressing this question reduces to the analysis of the asymptotic behavior of the unscaled queue-differential process in heavy traffic. We prove that the stationary regime of this process converges to that of a positive recurrent Markov chain, whose structure we explicitly describe. This in turn implies “smoothness” of the service processes.

Although privacy leaking through content analysis of Wi-Fi traffic has received an increased attention, privacy inference through meta-data (e.g. IP, Host) analysis of Wi-Fi traffic represents a potentially more serious threat to user privacy. Firstly, it represents a more efficient and scalable approach to infer users' sensitive information without checking the content of Wi-Fi traffic. Secondly, meta-data based demographics inference can work on both unencrypted and encrypted traffic (e.g., HTTPS traffic). In this study, we present a novel approach to infer user demographic information by exploiting the meta-data of Wi-Fi traffic. We develop a proof-of-concept prototype, Demographic Information Predictor (DIP) system, and evaluate its performance on a real-world dataset, which includes the Wi-Fi access of 28,158 users in 5 months. DIP extracts four kinds of features from real-world Wi-Fi traffic and proposes a novel machine learning based inference technique to predict user demographics. Our analytical results show that, for unencrypted traffic, DIP can predict gender and education level of users with an accuracy of 78% and 74% respectively. It is surprising to show that, even for HTTPS traffic, user demographics can still be predicted at a precision of 67% and 72% respectively, which well demonstrates the practicality of the proposed privacy inference scheme.

The legacy concept of exclusion zones (EZs) is inept at enabling efficient utilization of fallow spectrum by secondary users (SUs), since legacy EZs are static and overly-conservative. The notion of a static EZ implies that it has to protect incumbent users (IUs) from the union of likely interference scenarios, leading to a worst-case, conservative solution. In this paper, we propose the concept of dynamic, multi-tier EZs, which takes advantage of participatory spectrum sensing carried out by SUs to support efficient database-driven spectrum sharing while protecting IUs against SU-induced aggregate interference. Specifically, the database directly incentivizes SUs to participate in spectrum sensing, which augments geolocation database by defining smaller EZs with dynamic boundaries and creating additional spectrum access opportunities for SUs. We propose an incentive mechanism based on a two-level game-theoretic model, in which the database conducts dynamic pricing in a first-level Stackelberg game in the presence of SUs who strategically contribute to spectrum sensing in a second-level stochastic game. The existence of an equilibrium solution is proven. According to our findings, the proposed incentive mechanism for the concept of dynamic, multi-tier EZs is effective to improve spectrum utilization efficiency while guaranteeing incumbent protection.

In recent years, a suite of Glauber dynamics-based CSMA algorithms have attracted great attention due to their simple, distributed implementations with guaranteed throughput-optimality. However, these algorithms often suffer from poor delay performance and the starvation problem. Among several attempts to improve the delay performance, a remarkable improvement has recently been made in a class of CSMA algorithms that utilize multiple instances of the algorithm (or Markov chains). In this paper, we develop a new approach via an antithetic coupling (AC) method, which can further improve the delay performance of those that virtually emulate multiple chains. The key enabler of utilizing AC method lies in our skilful choice of manipulating the driving sequences of random variables that govern the evolution of schedule instances, in such a way that those multiple instances of chains become negatively correlated as oppose to having them run independently. This contributes faster change of the link state, rendering it more like a periodic process and thus leading to better queueing performance. We rigorously establish an ordering relationship for the effective bandwidth of each net-input process to the queue, between our proposed algorithm (AC-CSMA) and other state-of-the-art existing algorithms in the literature, under a mild set of assumptions. The proposed algorithm involves very simple modification onto existing CSMA-based algorithms, and can be implemented in a fully distributed manner without any additional message overhead. Our extensive simulation results also confirm that AC-CSMA always delivers better queueing performance over a variety of network scenarios.

In this work we outline a framework for measurement-based performance evaluation in SDN environments. The SDN paradigm, which is based on a strict separation of the network logic from the underlying physical substrate, necessitates a comprehensive global view of the network state. To augment the network representation, we propose mechanisms for extracting traffic characteristics from network observations which are used to derive performance metrics. Such metrics can be exploited by SDN applications to optimize the performance of SDN services. Given the bursty nature of network traffic and the well known adverse impact of this property on network performance, we propose an approach for extracting flow autocorrelations from switch counters. Our main contribution is a random sampling approach that reduces the monitoring overhead while enabling a fine grained characterization of the flow autocorrelation structure. We analytically evaluate the impact of random sampling and demonstrate how services may use the estimated traffic properties to compute useful performance metrics.

Recent advances in the design of in-band full-duplex (IBFD) radios promise to double the throughput of a wireless link. However, IBFD-capable nodes are more vulnerable to jamming attacks than their out-of-band full-duplex (OBFD) counterparts, and any advantages offered by them over the OBFD nodes can be jeopardized by such attacks. A jammer needs to attack both the uplink and the downlink channels to completely break the communication link between two OBFD nodes. In contrast, he only needs to jam one channel (used for both uplink and downlink) in the case of two IBFD nodes. Even worse, a jammer with the IBFD capability can learn the transmitters' activity while injecting interference, allowing it to react instantly with the transmitter's strategies. In this paper, we investigate frequency hopping (FH) technique for countering jamming attacks in the context of IBFD wireless radios. Specifically, we develop an optimal strategy for IBFD radios to combat an “IBFD reactive sweep jammer”. First, we introduce two operational modes for IBFD radios: transmission reception and transmission-detection. These modes are intended to boost the anti-jamming capability of IBFD radios. We then jointly optimize the decision of when to switch between the modes and when to hop to a new channel using Markov decision processes. Numerical investigations show that our policy significantly improves the throughput of IBFD nodes under jamming attacks.

In this work, we propose for the first time an autonomous system, called WiSpiro, that continuously monitors a person's breathing volume with high resolution during sleep from afar. WiSpiro relies on a phase-motion demodulation algorithm that reconstructs minute chest and abdominal movements by analyzing the subtle phase changes that the movements cause to the continuous wave signal sent by a 2.4 GHz directional radio. These movements are mapped to breathing volume, where the mapping relationship is obtained via a short training process. To cope with body movement, the system tracks the large-scale movements and posture changes of the person, and moves its transmitting antenna accordingly to a proper location in order to maintain its beam to specific areas on the frontal part of the person's body. It also incorporates interpolation mechanisms to account for possible inaccuracy of our posture detection technique and the minor movement of the person's body. We have built WiSpiro prototype, and demonstrated through a user study that it can accurately and continuously monitor user's breathing volume with a median accuracy from 90% to 95.4% (or 0.0581 to 0.111 of error) to even in the presence of body movement. The monitoring granularity and accuracy are sufficiently high to be useful for diagnosis by clinical doctor.

Monitoring Round-Trip Time provides important insights for network troubleshooting and traffic engineering. The common monitoring technique is to actively send probe packets from selected vantage points (hosts or middleboxes). In traditional networks, the control over the network routing is limited, making it impossible to monitor every selected path. The emerging concept of Software Defined Networking simplifies network control. However, OpenFlow, the common SDN protocol, does not support RTT monitoring as part of its specification. In this paper, we leverage the ability of OpenFlow to control the routing, and present GRAMI, the Granular RTT Monitoring Infrastructure. GRAMI uses active probing from selected vantage points for efficient RTT monitoring of all the links and any round-trip path between any two switches in the network. GRAMI was designed to be resource efficient. It requires only four flow entries installed on every switch in order to enable RTT monitoring of all the links. For every round-trip path selected by the user, it requires a maximum of two additional flow entries installed on every switch along the measured path. Moreover, GRAMI uses a minimal number of probe packets, and does not require the involvement of the controller during online RTT monitoring.

The performance of mobile computing would be significantly improved by leveraging cloud computing and migrating mobile workloads for remote execution at the cloud. In this paper, to efficiently handle the peak load and satisfy the requirements of remote program execution, we propose to deploy cloud servers at the network edge and design the edge cloud as a tree hierarchy of geo-distributed servers, so as to efficiently utilize the cloud resources to serve the peak loads from mobile users. The hierarchical architecture of edge cloud enables aggregation of the peak loads across different tiers of cloud servers to maximize the amount of mobile workloads being served. To ensure efficient utilization of cloud resources, we further propose a workload placement algorithm that decides which edge cloud servers mobile programs are placed on and how much computational capacity is provisioned to execute each program. The performance of our proposed hierarchical edge cloud architecture on serving mobile workloads is evaluated by formal analysis, small-scale system experimentation, and large-scale trace-based simulations.

This paper studies wireless networks consisting of multiple real-time flows that impose hard delay bounds for all packets. In contrast to most current studies that focus on the long-term average rate of timely deliveries, we aim to model and optimize the short-term performance of each real-time flow, which is vital for most safety-critical applications. We propose to define the instantaneous performance of a flow by a moving average within a short window in the past. Each flow incurs some penalty if its moving average is below some specified requirement, and we aim to minimize the overall penalty of the system. We approximate the system by Brownian motions, and formulate an optimization problem for minimizing the overall penalty. While the optimization problem is not convex, we establish a low-complexity algorithm for optimally solving it by leveraging inherent structures of real-time wireless networks. We also propose a simple online packet scheduling policy and prove that it achieves the minimum overall penalty. Simulation results show that Brownian approximations are accurate in capturing short-term performance, and our policies achieve much better performance than other policies. Moreover, they also demonstrate that policies with optimal long-term average delivery rates can actually have poor short-term performance.

For CDMA cell-based systems we propose an uplink power control scheme for low data packet queueing delay. The scheme can be seen as a simple extension to the Foschini-Miljanic algorithm which takes the transmit queue sizes at the mobile stations into account. The proposed scheme minimizes the draining time compared to all other policies with the same power consumption. This is because of resource pooling effects which arise when all queues empty at the same time. Although in CDMA systems there is no idle capacity as in wired systems, greater cummulative service is obtained by simultaneous transmissions than through time-sharing. Simulations exhibit significant reductions in queueing delay compared to other power control schemes proposed in the literature.

In this paper, we study network utility maximization over both routing choice and path rate assignment for any given path cardinality constraint. We provide a novel convex relaxation, which leads to a randomized algorithm with performance guarantees. The new relaxation also enables distributed algorithm design and allows us to obtain performance estimation for nonconvex routing optimization problems that is significantly better than previous work based on the multipath routing relaxation. Convergence and performance of the proposed randomized algorithm are characterized theoretically and further illustrated numerically through examples to demonstrate its superiority over existing work.

In recent years, the underwater cognitive acoustic network (UCAN) has been advocated as an efficient technique to enhance the utilization of acoustic channel, while not interrupting the activity of marine mammals, sonars and other acoustic users. In cognitive radios, the common control channel (CCC) based media access control (MAC) protocols are very popular for their high reliability, easy implementation and low overhead. However, due to the severe frequency-dependent attenuation of acoustic waves, a UCAN may not have enough bandwidth for CCC. How to prevent the control channel from congesting in a UCAN with heavy traffic should be investigated carefully. With this in mind, we propose a dynamic control channel MAC (DCC-MAC) for distributed UCANs. Nodes in DCC-MAC could adjust the bandwidth of their control channel adaptively based on the situation of network traffic. Whenever acoustic nodes detected the congestion of CCC, they could flexibly select proper data channels to extend the bandwidth of their control channel, and return excessive frequency bands back when the control channel becomes idle. Simulation results show that DCC-MAC could reduce the collision probability among control messages significantly, thereby providing a better network performance in terms of throughput and energy efficiency than conventional cognitive MAC protocols.

Processing time variability is commonplace in distributed systems, where resources display disparate performance due to, e.g., different workload levels, background processes, and contention in virtualized environments. However, it is paramount for service providers to keep variability in response time under control in order to offer responsive services. We investigate how request replication can be used to exploit processing time variability to reduce response times, considering not only mean values but also the tail of the response time distribution. We focus on the distributed setup, where replication is achieved by running copies of requests on multiple servers that otherwise evolve independently, and waiting for the first replica to complete service. We construct models that capture the evolution of a system with replicated requests using approximate methods and observe that highly variable service times offer the best opportunities for replication - reducing the response time tail in particular. Further, the effect of replication is non-uniform over the response time distribution: gains in one metric, e.g., the mean, can be at the cost of another, e.g., the tail percentiles. This is demonstrated in wide range of numerical virtual experiments. It can be seen that capturing service time variability is key to the evaluation of latency tolerance strategies and in their design.

We consider single-hop topologies with saturated transmitting nodes, using IEEE 802.11 DCF for medium access, where the propagation delays among the nodes are not negligible compared to the backoff slot duration. In this situation, we find that there is misaligned sensing of channel idleness, and also short-term unfairness in access to the medium. We demonstrate that existing analysis techniques (or, extensions thereof) are unable to account for these features, resulting in inaccurate prediction of the performance. Focusing on the case in which transmitters are equidistant from one another, and also each receiver is equidistant from all the transmitters, we provide a detailed stochastic model that accurately captures the system evolution. Since an exact analysis of this model is computationally intractable, we develop a novel approximate, but accurate, analysis that uses a parsimonious state representation for computational tractability. Numerical experiments show, the approximate analysis predicts the system throughput to a relative accuracy of 2-3%, and collision probabilities to a relative accuracy of 3-8% compared to simulations. Interestingly, we observe that as propagation delay increases, the collision probability of a node initially increases, but then flattens out, contrary to what one might intuitively expect. Finally, we also demonstrate how to optimize slot duration using the approximate analysis for maximizing system throughput.

Sophisticated adversaries usually initiate their attacks with a reconnaissance phase to discover exploitable vulnerabilities on the targeted networks and systems. To mitigate the effectiveness of persistent reconnaissance attacks, we develop a defensive mechanism that dynamically mutates network topology with a large number of decoys to invalidate the attacker's knowledge from network scanning. We combine the IP randomization technique with decoy techniques and solve two challenges, namely, service availability to legitimate users and service security against unauthorized users. First, our solution can minimize the probability of the real servers being identified and compromised by unauthorized users through deploying a large number of decoy nodes, which change their IP addresses along with the real servers to prolong the scanning time of the attackers. Second, our solution can ensure seamless connection migration so that all existing communication connections between the legitimate users and the servers are always kept alive even after the servers migrate to different IP addresses multiple times. We implement a virtual machine based system prototype and evaluate it using state-of-the-art scanning techniques. Both theoretical analysis and experimental results show that our solution can effectively mitigate network reconnaissance attacks without sacrificing service availability.

Due to the smaller size of mobile devices, on-screen keyboards become inefficient for text entry. In this paper, we present CamK, a camera-based text-entry method, which uses an arbitrary panel (e.g., a piece of paper) with a keyboard layout to input text into small devices. CamK captures the images during the typing process and uses the image processing technique to recognize the typing behavior. The principle of CamK is to extract the keys, track the user's fingertips, detect and localize the keystroke. To achieve high accuracy of keystroke localization and low false positive rate of keystroke detection, CamK introduces the initial training and online calibration. Additionally, CamK optimizes computation-intensive modules to reduce the time latency. We implement CamK on a mobile device running Android. Our experiment results show that CamK can achieve above 95% accuracy of keystroke localization, with only 4.8% false positive keystrokes. When compared to on-screen keyboards, CamK can achieve 1.25X typing speedup for regular text input and 2.5X for random character input.