INFOCOM 2015 Papers

Since TCP Incast has been identified as a catastrophic problem in many typical data center applications, a lot of efforts have been made to analyze or solve it. The analysis work intends to model Incast problem from certain perspective, and the solutions try to solve the problem through designing enhanced mechanisms or algorithms. However, the proposed models are either closely coupled with particular protocol version or dependent on empirical observations, and the solutions cannot eliminate Incast problem entirely because the underlying issues are not identified completely. There is little work which attempts to close the gap between “analyzing” and “solving”, and present a comprehensive understanding. In this paper, we provide an in-depth understanding of how TCP Incast problem happens. We build up an interpretive model which emphasizes particularly on describing qualitatively how various factors, including system parameters and mechanism variables, affect network performances in Incast traffic pattern, but not on calculating the accurate throughput. With this model, we give plausible explanations why the various solutions for TCP Incast problem can help, but do not solve it entirely.

Amongst data center structures, flattened butterfly (FBFly) networks have been shown to outperform their common counterparts such as fat-trees in terms of energy proportionality and cost efficiency. This efficiency is achieved by using less networking equipment (switches, ports, cables) at the expense of increased control plane complexity. In this paper we show that cabling complexity can be further reduced by an order of magnitude, by reconfiguring the optical fully meshed components into optical “pseudo”-fully meshed components. Following established methods, optical star networks are obtained by exchanging the FBFly's regular (grey) optical transceivers for dense wavelength division multiplexing (DWDM or colored) optical transceivers and placing an arrayed waveguide grating router (AWGR) in the center. Depending on the data center configuration and equipment prices, our colored FBFly (C-FBFly) proposal yields lower capital expenditure than the original FBFly. The key advantage of our structural modification of FBFly, however, is that in large FBFly networks (e.g., > 50K nodes) it reduces the number of inter-rack cables by a factor as large as 48.

The recent breakthrough in wireless full-duplex communication makes possible a brand new way of multi-hop wireless communication, namely full-duplex cut-through transmission, where for a traffic flow that traverses through multiple links, every node along the route can receive a new packet and simultaneously forward the previously received packet. This wireless transmission scheme brings new challenges in the design of MAC layer algorithms that aim to reap its full benefit. First, the MAC layer rate region of the cut-through enabled network is directly a function of the routing decision, leading to a strong coupling between routing and scheduling. Second, it is unclear how to dynamically form/change cut-through routes based on the traffic rates and patterns. In this work, we introduce a novel method to characterize the interference relationship between links in the network with cut-through transmission, which decouples the routing decision with the scheduling decision and enables a seamless adaptation of traditional half-duplex routing/scheduling algorithm into wireless networks with full-duplex cut-through capabilities. Based on this interference model, a queue-length based CSMA-type scheduling algorithm is proposed, which both leverages the flexibility of full-duplex cut-through transmission and permits distributed implementation.

As many-to-one traffic patterns prevail in data center networks, TCP flows often suffer from severe unfairness in sharing bottleneck bandwidth, which is known as the TCP outcast problem. The cause of the TCP outcast problem is the bursty packet losses by a drop-tail queue that triggers TCP timeouts and leads to decreasing the congestion window. This paper proposes TCPRand, a transport layer solution to TCP outcast. The main idea of TCPRand is the randomization of TCP payload size, which breaks synchronized packet arrivals between flows from different input ports. We investigate how TCPRand reduces consecutive packet drops and demonstrate various benefits of TCPRand with extensive experiments and ns-3 simulation. Our evaluation results show that TCPRand guarantees the superior enhancement of TCP fairness with negligible overheads in all of our test cases.

We study how an innovation (e.g., product or technology) diffuses over a social network when individuals strategically make selfish, rational choices in adopting the new innovation. This diffusion has been studied by modeling individuals' interactions with a noisy best response dynamic over a networked coordination game, but mainly in the nonprogressive setup. In this paper, we study the case when people are progressive, i.e., never going back to the old technology once the new technology is chosen, where such a progressive behavior is explained using the notion of sunk cost fallacy in social psychology. Our main focus is on the diffusion time, i.e., time till all choose the new innovation. To this end, we first provide a combinatorial characterization of the diffusion time that corresponds to the time reaching the absorbing state in a Markov chain. Based on this, we propose a polynomial-time algorithm that computes the diffusion time, where such a task is known to be computationally intractable in the non-progressive diffusion. Second, we asymptotically quantify the diffusion times for a class of well-known social graph topologies, and compare them to those under the non-progressive diffusion. Finally, we study the impact of seeding to speed up the diffusion in the progressive setup, and show that the diffusion speed is impossible to significantly accelerate with just a small-budget seeding, which is in part in stark contrast to that in the non-progressive diffusion. Our results provide not only understandings on the progressive strategic diffusion in a social network, but also computational tractability on other related problems, e.g., seeding, which we believe should be of broader interest in the future.

Full-duplex (FD) radios have the potential to double a link's capacity. However, it has been recently reported that the network throughput gain of FD radios over half-duplex (HD) ones is unexpectedly marginal or even negative. This is because both ends of each link transmit at the same time, a set of concurrent FD links will experience more network interference (hence, reduction in the spatial reuse). This article identifies the unique advantages of FD radios and leverage multi-input multioutput (MIMO) communications to translate the FD spectral efficiency gain at the PHY level to throughput and power efficiency gain at the network layer. To that end, we first study the power minimization problem subject to rate demands in a FD-MIMO network. Sufficient conditions under which the FD network throughput can asymptotically double that of an HD network are then established. These conditions also guarantee the existence of a unique Nash Equilibrium that the game quickly converges to. By capturing “spatial signatures” of other radios, a FD-MIMO radio can instantly adjust its ongoing radiation pattern to avoid interfering with the reception directions at other radios. We exploit that to develop a novel MAC protocol that allows multiple FD links to concurrently communicate while adapting their radiation patterns to minimize network interference. The protocol does not require any feedback or coordination among nodes, but relies on the network interference perceived by these FD radios. Extensive simulations show that the proposed MAC design dramatically outperforms traditional FD-based CSMA protocols and HD radios w.r.t. both throughput and energy efficiency. A centralized algorithm for the FD network-wide transmit power minimization problem is also developed. Simulations show that, the proposed MAC protocol on average achieves almost the same power efficiency as the centralized algorithm. Interestingly, we even observe cases when the proposed distributed algorithm outperforms the centralized approach.

The Internet is facing the double-challenge of accelerating growth of routing table size and ever higher reliability requirements. Considerable progress has been made toward the scalability and reliability of the Internet. However, most of the proposals are only partial solutions that address some of the challenges. In this paper, we present a new addressing encoding scheme and a corresponding forwarding mechanism for Internet routing to solve the aforementioned problems. Underlying our design is a succinct data structure that allows us to compactly embed a set of addresses into packet headers. At the same time, the structure allows the data plane to efficiently extract multiple address information for the same destination without decompression. We provide time and space complexity analysis, and present experimental results evaluating the performance of our encoding method. It shows that the proposed encoding method can achieve a good compression factor without degrading packet-forwarding performance.

LTE network service reliability is highly dependent on the wireless coverage that is provided by cell towers (eNB). Therefore, the network operator's response to outage scenarios needs to be fast and efficient, in order to minimize any degradation in the Quality of Service (QoS). In this paper, we propose an outage mitigation framework for LTE-Advanced (LTE-A) wireless networks. Our framework exploits the inherent design features of LTE-A; it performs a dual optimization of the transmission power and beamforming weight parameters at each neighbor cell sector of the outage eNBs, while taking into account both the channel characteristics and residual eNB resources, after serving its current traffic load. Assuming statistical Channel State Information about the users at the eNBs, we show that this problem is theoretically NP-hard; thus we relax it as a convex optimization problem and solve for the optimal points using an iterative algorithm. Contrary to previously-proposed power control studies, our framework is specifically designed to alleviate the effects of sudden LTE-A eNB outages, where a large number of mobile users need to be efficiently offloaded to nearby towers. We present the detailed analytical design of our framework, and we assess its efficacy via extensive NS-3 simulations on an LTE-A topology. Our simulations demonstrate that our framework provides adequate coverage and QoS across all examined outage scenarios.

Motivated by the recent push to deploy LTE in unlicensed spectrum, this paper develops a novel system to enable co-existence between LTE and WiFi. Our approach leverages LTE and WiFi antennas already available on smartphones to let LTE and WiFi transmit together and successfully decode the interfered signals. Our system offers several distinct advantages over existing MIMO work: (i) it can decode all the interfering signals under cross technology interference even when the interfering signals have similar power and occupy similar frequency, (ii) it does not need clean reference signals from either WiFi or LTE transmission, (iii) it can decode interfering WiFi MIMO and LTE transmissions, and (iv) it has a simple yet effective carrier sense mechanism for WiFi to access the medium under interfering LTE signals while avoiding other WiFi transmissions. We use USRP implementation and experiments to show its effectiveness.

Indoor localization has been an active research field for decades, where the received signal strength (RSS) fingerprinting based methodology is widely adopted and induces many important localization techniques such as the recently proposed one building the fingerprint database with crowd-sourcing. While efforts have been dedicated to improve the accuracy and efficiency of localization, the fundamental limits of RSS fingerprinting based methodology itself is still unknown in a theoretical perspective. In this paper, we present a general probabilistic model to shed light on a fundamental question: how good the RSS fingerprinting based indoor localization can achieve? Concretely, we present the probability that a user can be localized in a region with certain size, given the RSS fingerprints submitted to the system. We reveal the interaction among the localization accuracy, the reliability of location estimation and the number of measurements in the RSS fingerprinting based location determination. Moreover, we present the optimal fingerprints reporting strategy that can achieve the best accuracy for given reliability and the number of measurements, which provides a design guideline for the RSS fingerprinting based indoor localization facilitated by crowdsourcing paradigm.

The popularity of QR code clearly indicates the strong demand of users to acquire (or pull) further information from interested sources (e.g., a poster) in the physical world. However, existing information pulling practices such as a mobile search or QR code scanning incur heavy user involvement to identify the targeted posters. Meanwhile, businesses (e.g., advertisers) are also interested to learn about the behaviors of potential customers such as where, when, and how users show interests in their offerings. Unfortunately, little such context information are provided by existing information pulling systems. In this paper, we present Contextual-Code (C-Code) - an information pulling system that greatly relieves users' efforts in pulling information from targeted posters, and in the meantime provides rich context information of user behavior to businesses. C-Code leverages the rich contextual information captured by the smartphone sensors to automatically disambiguate information sources in different contexts. It assigns simple codes (e.g., a character) to sources whose contexts are not discriminating enough. To pull the information from an interested source, users only need to input the simple code shown on the targeted source. Our experiments demonstrate the effectiveness of C-Code design. Users can effectively and uniquely identify targeted information sources with an average accuracy over 90%.

Distributed coherent transmission is necessary for a variety of high-gain communication protocols such as distributed MIMO and creating codes over the air. Unfortunately, however, distributed coherent transmission is intrinsically difficult because different nodes are driven by independent clocks, which do not have the exact same frequency. This causes the nodes to have frequency offsets relative to each other, and hence their transmissions fail to combine coherently over the air. This paper presents AirShare, a primitive that makes distributed coherent transmission seamless. AirShare transmits a shared clock on the air and feeds it to the wireless nodes as a reference clock, hence eliminating the root cause for incoherent transmissions. The paper addresses the challenges in designing and delivering such a shared clock. It also implements AirShare in a network of USRP software radios, and demonstrates that it achieves tight phase coherence. Further, to illustrate AirShare's versatility, the paper uses it to deliver a coherent-radio abstraction on top of which it demonstrates two cooperative protocols: distributed MIMO, and distributed rate adaptation.

Encrypted data search allows cloud to offer fundamental information retrieval service to its users in a privacy-preserving way. In most existing schemes, search result is returned by a semi-trusted server and usually considered authentic. However, in practice, the server may malfunction or even be malicious itself. Therefore, users need a result verification mechanism to detect the potential misbehavior in this computation outsourcing model and rebuild their confidence in the whole search process. On the other hand, cloud typically hosts large outsourced data of users in its storage. The verification cost should be efficient enough for practical use, i.e., it only depends on the corresponding search operation, regardless of the file collection size. In this paper, we are among the first to investigate the efficient search result verification problem and propose an encrypted data search scheme that enables users to conduct secure conjunctive keyword search, update the outsourced file collection and verify the authenticity of the search result efficiently. The proposed verification mechanism is efficient and flexible, which can be either delegated to a public trusted authority (TA) or be executed privately by data users. We formally prove the universally composable (UC) security of our scheme. Experimental result shows its practical efficiency even with a large dataset.

The tightness of stochastic performance bounds has been a lingering issue in the theory and practical applications of stochastic network calculus (SNC). More often than not, inappropriate stochastic traffic arrival models and/or service models lead to loose stochastic bounds. In practice, loose bounds occur due to inaccurate a-prior assumption on traffic arrivals and/or the obliviousness to possible correlation between arrivals. To alleviate this problem, this paper uses copula analysis to capture the correlation in traffic flows and introduces a statistical method to infer traffic arrival models. Using copula theory, we show the range of performance bounds that SNC can achieve. With concrete numerical examples and real-world experiments, it is demonstrated that copula analysis offers a new opportunity for extending SNC research and augmenting its impact in practice.

Web browsers are one of the most important enduser applications to browse, retrieve, and present Internet resources. Malicious or compromised resources may endanger Web users by hijacking web browsers to execute arbitrary malicious code in the victims' systems. Unfortunately, the widely-adopted Just-In-Time compilation (JIT) optimization technique, which compiles source code to native code at runtime, significantly increases this risk. By exploiting JIT compiled code, attackers can bypass all currently deployed defenses. In this paper, we systematically investigate threats against JIT compiled code, and the challenges of protecting JIT compiled code. We propose a general defense solution, JITScope, to enforce Control-Flow Integrity (CFI) on both statically compiled and JIT compiled code. Our solution furthermore enforces the W⊕X policy on JIT compiled code, preventing the JIT compiled code from being overwritten by attackers. We show that our prototype implementation of JITScope on the popular Firefox web browser introduces a reasonably low performance overhead, while defeating existing real-world control flow hijacking attacks.

To reduce the operation cost incurred by the rapidly growing energy consumption in internet data centers (IDCs), more and more internet service providers have spontaneously started using energy storage in various forms. The approach of energy storage is used to store cheap electricity energy when the electricity price from smart gird is low or the renewable energy is used. There are two typical forms of energy storage equipped in many IDCs, i.e., the battery storage and thermal energy storage. Recent work shows the energy storage can significantly reduce the operation cost for IDCs. However, the cost of the energy storage devices are still at a high level, and it may increase the operation cost for IDCs. In this paper, we investigate the comprehensive understanding on the operation cost reduction for IDCs using the energy storage. To this end, we conduct a quantitative analysis on the normalized electricity price in the two energy storage forms. The experiments demonstrate that the cost of the storage devices and renewable energy supply are largely affected by the storage capacity and the location of data centers, and we conclude that it does not always reduce operation cost using energy storage for IDCs.

Fixed channelization configuration in today's wireless devices falls inefficient in the presence of growing data traffic and heterogeneous devices. In this regard, a number of fairly recent studies have provided spectrum adaptation capabilities for current wireless devices, however, they are limited to inband adaptation or incur substantial coordination overhead. The target of this paper is to fill the gaps in spectrum adaptation by overcoming these limitations. We propose Seer, a frame-level wideband spectrum adaptation system which consists of two major components: i) a specially-constructed preamble that can be detected by receivers with arbitrary RF bands, and ii) a spectrum detection algorithm that identifies the intended transmission band in the context of multiple asynchronous senders by exploiting the preamble's temporal and spectral properties. Seer can be realized on commodity radios, and can be easily integrated into devices running different PHY/MAC protocols. We have prototyped Seer on the GNURadio/USRP platform and tested it under various environments. Furthermore, our evaluation using 1.6GHz spectrum measurements shows that Seer largely improves system throughput over fixed channel configuration and state-of-the-art spectrum adaptation approaches.

In January 2014, AT&T introduced sponsored data to the U.S. mobile data market, allowing content providers (CPs) to subsidize users' cost of mobile data. As sponsored data gains traction in industry, it is important to understand its implications. This work considers CPs' choice of how much content to sponsor and the implications for users, CPs, and ISPs (Internet service providers). We first formulate a model of user, CP, and ISP interaction for heterogeneous users and CPs and derive their optimal behaviors. We then show that these behaviors can reverse our intuition as to how user demand and utility change with different user and CP characteristics. While all three parties can benefit from sponsored data, we find that sponsorship disproportionately favors less cost-constrained CPs and more cost-constrained users, exacerbating CP inequalities but making user demand more even. We also show that users' utilities increase more than CPs' with sponsored data. We finally illustrate these results in practice through numerical simulations with data from a commercial pricing trial and introduce a framework for CPs to decide which, in addition to how much, content to sponsor.

Wireless video traffic has grown at an unprecedented rate and put significant burden on wireless networks. Multicast can significantly reduce traffic by sending a single video to multiple receivers simultaneously. On the other hand, wireless receivers are heterogeneous due to both channel and antenna heterogeneity, the latter of which is rapidly increasing with the emergence of 802.11n and 802.11ac. In this paper, we develop optimized layered integrated video encoding (LIVE) to guarantee reasonable performance to weaker receivers (with worse channel and/or fewer antennas) and allow stronger receivers to enjoy better quality. Our approach has three distinct features: (i) It uses a novel layered coding to naturally accommodate the heterogeneity of different video receivers; (ii) It uses an optimization framework to optimize the amount of time used for transmission and the amount of information to transmit at each layer under the current channel condition; and (iii) It uses an integrated modulation, where most video data are transmitted using soft modulation to enjoy efficiency and resilience while the most important video data are transmitted using a combination of soft modulation and conventional hard modulation to further enhance their reliability. To our knowledge, this is the first approach that handles MIMO antenna heterogeneity in wireless video multicast. We demonstrate its effectiveness through extensive Matlab simulation and USRP testbed experiments.