INFOCOM 2016 论文列表

Video Content Distribution Networks (CDNs) serve a significant fraction of the Internet traffic through a global network of cache servers. In a planet-scale CDN with millions of videos, cache servers only consider their own request patterns for managing their content. We analyze how, in the absence of cooperative caching, the knowledge of requests in remote serving locations can lead to better caching decisions overall and can reduce serving costs. We call this practice cache coordination. Our analyses in this paper are based on actual video workload data from a global CDN. We analyze the spatial correlation of video popularities worldwide, the effectiveness and feasibility of cache coordination, and its scalability: from a city to across countries.

In wireless local area networks (WLANs), association of the access points (APs) is often not uniform due to joining and leaving of wireless users. Such imbalance leads to unsatisfactory user throughput due to congestion at some APs and channel under-utilization at others. As users may be covered by multiple APs in WLAN deployment, their throughput can be improved by AP re-association, i.e., migrating some users from the congested APs to the less loaded neighboring APs. Such reassociation is expected to come with some cost (due to overhead in handshaking, authentication and data flow management). In this paper, we study the novel problem of optimizing AP re-association by maximizing the minimum user throughput (i.e., max-min fairness), subject to a certain total user migration cost constraint. We show that the problem is NP-hard. We then propose an efficient approximation algorithm called CACA (Cost-constrained Association Control Algorithm). CACA has provable performance, achieving an approximation factor of (4+ϵ), for any ϵ > 0. It is simple and implementable. Our extensive simulation results based on NS3 show that it substantially outperforms other comparison schemes with close-to-optimal performance (the case without cost constraint). Our testbed experiments further confirm the effectiveness of CACA.

Software-Defined Network (SDN) controllers include mechanisms to globally reconfigure the network in order to respond to a changing environment. While iterative methods are employed to solve flow optimization problems, demands arrive or leave the system changing the optimization instance and requiring further iterations. In this paper, we focus on the general class of iterative solvers considering an exponential decrease over time in the optimality gap. Assuming dynamic arrivals and departures of demands, the computed optimality gap at each iteration Q(t) is described by an auto-regressive stochastic process. At each time slot the controller may choose to apply the current iteration to the network or not. Applying the current iteration improves the optimality gap but requires flow reconfiguration which hurts QoS and system stability. To limit the reconfigurations, we propose two control policies that minimize the flow allocation cost while respecting a network reconfiguration budget. We validate our model by experimenting with a realistic network setting and using standard Linear Programming tools used in the SDN industry. We show that our policies provide a practical means of keeping the optimally gap small within a given reconfiguration constraint.

In modern Cloud Data Centers (DC)s, correct implementation of network policies is crucial to provide secure, efficient and high performance services for tenants. It is reported that the inefficient management of network policies accounts for 78% of DC downtime, challenged by the dynamically changing network characteristics and by the effects of dynamic Virtual Machine (VM) consolidation. While there has been significant research in policy and VM management, they have so far been treated as disjoint research problems. In this paper, we explore the simultaneous, dynamic VM and policy consolidation, and formulate the Policy-VM Consolidation (PVC) problem, which is shown to be NP-Hard. We then propose Sync, an efficient and synergistic scheme to jointly consolidate network policies and virtual machines. Extensive evaluation results and a testbed implementation of our controller show that policy and VM migration under Sync significantly reduces flow end-to-end delay by nearly 40%, and network-wide communication cost by 50% within few seconds, while adhering strictly to the requirements of network policies.

Though not recommended, Internet users often include parts of personal information in their passwords for easy memorization. However, the use of personal information in passwords and its security implications have not yet been studied systematically in the past. In this paper, we first dissect user passwords from a leaked dataset to investigate how and to what extent user personal information resides in a password. In particular, we extract the most popular password structures expressed by personal information and show the usage of personal information. Then we introduce a new metric called Coverage to quantify the correlation between passwords and personal information. Afterwards, based on our analysis, we extend the Probabilistic Context-Free Grammars (PCFG) method to be semantics-rich and propose Personal-PCFG to crack passwords by generating personalized guesses. Through offline and online attack scenarios, we demonstrate that Personal-PCFG cracks passwords much faster than PCFG and makes online attacks much easier to succeed.

Software-Defined Networking (SDN) promises un-precedentedly flexible network management but it is susceptible to forwarding faults. Such faults originate from data-plane rules with missing faults and priority faults. Yet existing fault detection ignores priority faults because they are not discovered on commercial switches until recently. In this paper, we present RuleScope, a more comprehensive solution for inspecting SDN forwarding. RuleScope offers a series of accurate and efficient algorithms for detecting and troubleshooting rule faults. They inspect forwarding behavior using customized probe packets to exercise data-plane rules. The detection algorithm exposes not only missing faults but also priority faults. Beyond simply detecting rule faults, the troubleshooting algorithms uncover actual data-plane flow tables. They help track real-time forwarding status and benefit reliable network monitoring. We explore various techniques for enhancing algorithm efficiency without sacrificing inspection accuracy. Experiments with our prototype on the Ryu SDN controller and Pica8 P-3297 switch show that RuleScope achieves accurate and efficient forwarding inspection with limited bandwidth and packet-switching overhead.

Constructive Interference (CI) phenomenon has been exploited by Glossy, a mechanism for low-latency and reliable network flooding and time synchronization for wireless sensor networks. Recently, CI has also been used for other applications such as data collection and multicasting in static and mobile WSNs. These applications base their working on the high reliability promised by Glossy regardless of the physical conditions of deployment, number of nodes in the network, and unreliable wireless channels that may be detrimental for CI. There are several works that study the working of CI, but they present inconsistent views. We study CI from a receiver's viewpoint, list factors that affect CI and also specify how and why they affect. We validate our arguments with results from extensive and rigorous experimentation in real-world settings. This paper presents comprehensive insights into CI phenomenon. With this understanding, we improve the performance of CI through an energy-efficient and distributed algorithm. We cause destructive interference on a designated byte to provide negative feedback. We leverage this to adapt transmission powers. Compared to Glossy, we achieve 25% lesser packet losses while using only half of its transmission power.

Distributed link-flooding attacks constitute a new class of attacks with the potential to segment large areas of the Internet. Their distributed nature makes detection and mitigation very hard. This work proposes a novel framework for the analytical modeling and optimal mitigation of such attacks. The detection is modeled as a problem of relational algebra, representing the association of potential attackers (bots) to potential targets. The analysis seeks to optimally dissolve all but the malevolent associations. The framework is implemented at the level of online Traffic Engineering (TE), which is naturally triggered on link-flooding events. The key idea is to continuously re-route traffic in a manner that makes persistent participation to link-flooding events highly improbable for any benign source. Thus, bots are forced to adopt a suspicious behavior to remain effective, revealing their presence. The load-balancing objective of TE is not affected at all. Extensive simulations on various topologies validate our analytical findings.

An increasing number of real-time applications with compute and/or communication deadlines are being supported on shared infrastructure. Such applications can often tolerate occasional deadline violations without substantially impacting their Quality of Service (QoS). A fundamental problem in such systems is deciding how to allocate shared resources so as to meet applications' QoS requirements. A simple framework to address this problem is to, (1) dynamically prioritize users as a possibly complex function of their deficits (difference of achieved vs required QoS), and (2) allocate resources so to expedite users with higher priority. This paper focuses on a general class of systems using such priority-based resource allocation. We first characterize the set of feasible QoS requirements and show the optimality of max weight-like prioritization. We then consider simple weighted Largest Deficit First (w-LDF) prioritization policies, where users with higher weighted QoS deficits are given higher priority. The paper gives an inner bound for the feasible set under w-LDF policies, and, under an additional monotonicity assumption, characterizes its geometry leading to a sufficient condition for optimality. Additional insights on the efficiency ratio of w-LDF policies, the optimality of hierarchical-LDF and characterization of clustering of failures are also discussed.

Wireless RF power transmission from dedicated Energy Transmitters (ETs) is emerging as a promising approach to enable battery-less wireless networked sensor systems. However, when data communication and RF energy recharging occur in-band, sharing the RF medium and devoting separate access times for both operations raises architectural and protocol level challenges. This paper proposes a novel method of concurrent transmission of data and energy to solve this problem, allowing ETs to transmit energy and sensors to transmit data in the same band synchronously. Our key idea concerns devising a physical layer modulation scheme that allows the data transmitting node to introduce variations in the envelope of the energy signal at the intended recipient. We implemented a proof-of-concept receiver, modeled and validated through extensive experimentation. We then propose a new physical layer mechanism for guaranteed successful delivery of information in a point-to-point link. Quantitative results demonstrate the feasibility of joint energy-data transfer, along with its associated benefits and tradeoffs.

Video surveillance has been widely adopted to ensure home security in recent years. Most video encoding standards such as H.264 and MPEG-4 compress the temporal redundancy in a video stream using difference coding, which only encodes the residual image between a frame and its reference frame. Difference coding can efficiently compress a video stream, but it causes side-channel information leakage even though the video stream is encrypted, as reported in this paper. Particularly, we observe that the traffic patterns of an encrypted video stream are different when a user conducts different basic activities of daily living, which must be kept private from third parties as obliged by HIPAA regulations. We also observe that by exploiting this side-channel information leakage, attackers can readily infer a user's basic activities of daily living based on only the traffic size data of an encrypted video stream. We validate such an attack using two off-the-shelf cameras, and the results indicate that the user's basic activities of daily living can be recognized with a high accuracy.

In this paper, we present MobTrack, a single device system which aims to locate interfering radios on unlicensed ISM band in indoor environments. Compared with existing techniques which require a deployment of dense access points (APs), MobTrack only demands a single device equipped with multiple antennas. The location of an interfering signal source are estimated by computing the angle of arrival (AoA) of Line of Sight (LoS) component using an antenna array. Taking advantage of cyclostationary property, MobTrack differentiates interfering signals from working signals. By moving the device around for a short distance within one meter, it depresses multipath effects and determines the LoS component. Simultaneously, the AoAs on the moving trace are recorded to estimate the location of the interfering radio by triangulation. We evaluate the performance of MobTrack by setting up a prototype experimental system. Compared with recent interference localization schemes, MobTrack has much lower hardware complexity and gets better localization accuracy with a median of 0.55 meters.

Sharding is a method for allocating data items to nodes of a distributed caching or storage system based on the result of a hash function computed on the item identifier. It is ubiquitously used in key-value stores, CDNs and many other applications. Despite considerable work has focused on the design and the implementation of such systems, there is limited understanding of their performance in realistic operational conditions from a theoretical standpoint. In this paper we fill this gap by providing a thorough modeling of sharded caching systems, focusing particularly on load balancing and caching performance aspects. Our analysis provides important insights that can be applied to optimize the design and configuration of sharded caching systems.

Mobile social media enables people to record ongoing physical events they witness and share them instantaneously online. However, since these event pictures are often individually provided, they are typically fragmented and possess high redundancy. Though there have been studies about visual event summarization, they pay little attention to collaborative sensing, subevent detection, and event summary. In this paper, we present several building blocks for a cooperative visual sensing and sharing system. We create a virtual opportunistic community associated with an event, where members collaborate to cover different aspects of the event. More specifically, a crowd-powered approach is first used to localize the event. We then propose three subevent segmentation methods based on crowd-event interaction patterns. Based on the segmentation results, we summarize the event at two levels: multi-facet subevent summary and crowd-behavior-based highlights. Experiments over 21 online datasets and two real world datasets demonstrate the effectiveness of our approaches.

In interdomain routing, competing network operators encode policies about possible routes in routing protocol configuration. The operation of the protocol should lead to satisfactory routes for all operators, but this process may not terminate or take a long time, exploring exponentially many alternative paths before stabilizing. In this paper, we study convergence for the partial policy specification model where preferences are set for only some paths and the ranking for the remaining paths is indifferent to the network operator. We consider policy restrictions that ensure a network to stabilize quickly. Specifically, we show that even when each operator only specifies preferences for two paths and each path has at most three hops, a network may still encounter exponentially many steps before convergence. However, restricting the policy any further ensures poly-time convergence. From another direction, it is well known that preferences based only on the `next-hop' node always converge within linear-time. We show that even relaxing the preference to be based on the `next-two-hop' leads to exponential-time convergence. Finally, we further study policy completion that leads to a stable state that minimizes the hop-length of the longest path, and establish a hardness result along with an approximation algorithm.

The problem of allocating jobs to appropriate servers in cloud computing is studied in this paper. We consider that jobs of various types arrive in some unpredictable pattern and the system is required to allocate a certain ratio of jobs. In order to meet the hard allocation ratio requirement in the presence of unknown arrival patterns, one can increase the capacity of servers by expanding the size of data centers. We then aim to find the minimum capacity needed to meet a given allocation ratio requirement. We propose two online job allocation policies with low complexity. We prove that, given a hard allocation ratio requirement, these two policies can achieve the requirement with the least capacity. We also derive a closed-from expression for the amount of capacity needed to achieve any given requirement. Two other popular policies are studied, and we demonstrate that they need at least an order higher capacity to meet the same hard allocation ratio requirement. Simulation results demonstrate that our policies remain far superior than the other two when jobs arrive according to some random process.

Recently, Network Function Virtualization (NFV) has been proposed to transform from network hardware appliances to software middleboxes. Normally, a demand needs to invoke several Virtual Network Functions (VNFs) in a particular order following the service chain along a routing path. In this paper, we study the joint problem of VNF placement and path selection to better utilize the network. We discover that the relation between the link and server usage plays a crucial role in the problem. We first propose a systematic way to elastically tune the proper link and server usage of each demand based on network conditions and demand properties. In particular, we compute a proper routing path length, and decide, for each VNF in the service chain, whether to use additional server resources or to reuse resources provided by existing servers. We then propose a chain deployment algorithm to follow the guidance of this link and server usage. Via simulations, we show that our design effectively adapts resource usage to network dynamics, and, hence, serves more demands than other heuristics.

Object tracking applications are gaining popularity and will soon utilize Energy Harvesting (EH) low-power nodes that will consume power mostly for Neighbor Discovery (ND) (i.e., identifying nodes within communication range). Although ND protocols were developed for sensor networks, the challenges posed by emerging EH low-power transceivers were not addressed. Therefore, we design an ND protocol tailored for the characteristics of a representative EH prototype: the TI eZ430-RF2500-SEH. We present a generalized model of ND accounting for unique prototype characteristics (i.e., energy costs for transmission/reception, and transceiver state switching times/costs). Then, we present the Power Aware Neighbor Discovery Asynchronously (Panda) protocol in which nodes transition between the sleep, receive, and transmit states. We analyze Panda and select its parameters to maximize the ND rate subject to a homogeneous power budget. We also present Panda-D, designed for non-homogeneous EH nodes. We perform extensive testbed evaluations using the prototypes and study various design tradeoffs. We demonstrate a small difference (less then 2%) between experimental and analytical results, thereby confirming the modeling assumptions. Moreover, we show that Panda improves the ND rate by up to 3x compared to related protocols. Finally, we show that Panda-D operates well under non-homogeneous power harvesting.

On-demand wireless data broadcast is an efficient way to disseminate data to a large number of mobile users. In many applications, such as stock quotes and flight schedules, users may have to download multiple data items per request. However the multi-item request scheduling has not yet been thoroughly investigated for on-demand wireless data broadcasts. In this paper, we step-up on investigating this problem from viewpoint of theory and simulation. We develop a two-stage scheduling scheme to arrange the requested data items with the objective of minimizing the average access latency. The first stage is to select the data items to be broadcast in the next time period and the second stage is to schedule the broadcasting order for the data items selected in the first stage. We develop algorithms for the two stages respectively and analyze them both theoretically and practically. We also compare the proposed algorithms with other well known scheduling methods through simulation. The theoretical findings and simulation results reveal that significantly better access latency can be obtained by using our scheduling scheme rather than its competitors.