INFOCOM 2016 论文列表

Thanks to the widespread use of smart devices, recent years have witnessed the proliferation of mobile apps available on online stores such as Apple iTunes and Google Play. As the number of new mobile apps continues to grow at a rapid pace, automatic classification of the apps has become an increasingly important problem to facilitate browsing, searching, and recommending them. This paper presents a framework that automatically labels apps with a richer and more detailed categorization and uses the labeled apps to study the app market. Leveraging a fine-grained, hierarchical ontology as a guide, we developed a framework not only to label the apps with fine-grained categorical information but also to induce a customized class hierarchy optimized for mobile app classification. With the classification accuracy of 93%, large-scale categorization conducted with our framework on 168,000 Google Play apps discovers novel inter-class relationships among categories of Google Play market.

In this paper, we expand the scope of PHY-layer security by investigating TX-based friendly jamming (FJ) for the wiretap channel in multi-link settings. For the single-link scenario, creating a TX-based FJ is an effective and practical method in improving the secrecy rate. In a multi-link setting, several information signals must be transmitted simultaneously. Thus, the design must guarantee that the FJ signal of a given transmitter does not interfere with unintended but legitimate receivers. Under the assumption of exact knowledge of the eavesdropping channel, we first propose a distributed price-based approach to improve the secrecy sum-rate of a two-link network with one eavesdropper while satisfying an information-rate constraint for both link. Simulations show that price-based FJ control outperforms greedy FJ, and is close to the performance of a centralized approach. Next, we propose a method based on mixed strategic games that can offer robust solutions to the distributed secrecy sum-rate maximization problem under the assumption of an unknown eavesdropping channel. Lastly, we use simulations to show that in addition to outperforming the greedy approach, our robust optimization also satisfies practical network considerations. In particular, the transmission time for the robust optimization can be determined flexibly to match the channel's coherence time.

We consider the problem of capacitated kinetic clustering in which n mobile terminals and k base stations with respective operating capacities are given. The task is to assign the mobile terminals to the base stations such that the total squared distance from each terminal to its assigned base station is minimized and the capacity constraints are satisfied. This paper focuses on the development of distributed and computationally efficient algorithms that adapt to the motion of both terminals and base stations. Suggested by the optimal transportation theory, we exploit the structural property of the optimal solution, which can be represented by a power diagram on the base stations such that the total usage of nodes within each power cell equals the capacity of the corresponding base station. We show by using the kinetic data structure framework the first analytical upper bound on the number of changes in the optimal solution, i.e., its stability. On the algorithm side, using the power diagram formulation we show that the solution can be represented in size proportional to the number of base stations and can be solved by an iterative, local algorithm. In particular, this algorithm can naturally exploit the continuity of motion and has orders of magnitude faster than existing solutions using min-cost matching and linear programming, and thus is able to handle large scale data under mobility.

Network tomography is an attractive approach for inferring internal network states at edge nodes. Recently, there is a growing interest in the basic understanding of the topological conditions that ensure identifiability in a general network. Un, existing works assume an ideal network model where all network elements are reliable. In this paper, we are aiming to propose topological conditions to ensure identifiability in the presence of any k link failures (k ≥ 0), using measurement paths and cycles. We propose a novel concept called k-identifiability. We propose sufficient and necessary topological conditions to ensure k-identifiability. Based on the established theoretical foundations, we propose two efficient polynomial-time algorithms for addressing two closely related questions. (1) Given a network with specified monitors, which links are k-identifiable? (2) Given a network and κ monitors, where should these monitors be placed such that the number of k-identifiable links is maximized? Simulation results on real ISP network topologies show the effectiveness of our algorithms.

Massive visual traffic data have become available recently, which provides an opportunity for intelligent traffic analysis. Timely processing is particularly necessary for traffic analysis. In this paper, we study time-bounded aggregation analytics on large visual traffic data. We first find that current MapReduce framework can not work well due to two challenges: first, significant dual diversities exist on data distributions and processing time; second, no apriori knowledge on these distributions and time costs is available. However, we also observe spatial and temporal locality on data values and processing time. Based on the examination, we design TaG, an augmented MapReduce framework for time-bounded traffic analytics jobs. Particularly, we propose a novel sampling algorithm that exploits traffic data localities and stratifies samples based on data distributions and processing time. It runs in an iterative, adaptive manner without apriori knowledge. Moreover, we propose a heuristic scheduling algorithm with considerations of batch processing overhead. Further, we refine load balancing mechanism based on data processing time locality to respect job time bounds. We implement TaG on Hadoop and conduct extensive experiments on a large traffic image dataset. The evaluations on different data sizes show TaG is able to achieve high accuracy within different time bounds.

Many-to-one data collection is a fundamental operation in wireless sensor networks (WSNs). To support long-term deployment of WSNs, sensor nodes normally operate at low-duty-cycles. However, the low-duty-cycle operation significantly reduces the communication chance between nodes. Consequently, the risk of data collisions significantly increases when multiple senders transmit packets to a receiver during its very short active period. Data collision not only results in wasted packet transmissions, but also incurs a large delivery latency. Under such conditions, collision-free medium access is more appealing than recovering after collision for low-duty-cycle WSNs. In this work, we propose an incast-collision-free data collection protocol, named iCore, to address the many-to-one collision problem in low-duty-cycle WSNs. iCore employs the dynamic forwarding technique and establishes a non-conflicting schedule for delay reduction. Specifically, we design efficient forwarder assignment and forwarding optimization algorithms that ensure low end-to-end latency under diverse data traffic types. Through comprehensive performance evaluations, we demonstrate that, compared with the state-of-the-art protocol, iCore effectively minimizes the end-to-end delay by 25% ∼ 57% and maintains high delivery ratio and energy efficiency for different many-to-one convergecast scenarios.

Due to the hierarchical structure and heterogeneity of most deployed wireless networks, multiple data transmissions using the same communication resource, such as frequency band and time slot, are likely to occur in the same area. Hence, interference becomes critical to the decoding of interfered signals. There have already been numerous techniques dealing with interferences that can be implemented either at the transmitter, the receiver or both, to support simultaneous multi-user transmissions. This paper focuses on the reception design in multiple access channels (MACs) where multiple transmitters send data to a common receiver simultaneously. By exploiting the constructive/destructive interactions among interfering signals, we propose a receiver structure based on interference combination (ICom) incorporating zero-forcing (ZF) and successive interference cancellation (SIC). The proposed receiver structure does not require coordination at the transmitter side and can significantly reduce the number of receiving antennas at a moderate processing cost. The ICom-based reception is shown to be able to not only achieve a significant improvement of system spectral efficiency (SE) under stringent latency constraints, but also make a flexible tradeoff between the requirement of receiving antennas and signal processing complexity, thus facilitating its implementation and deployment.

Identifying heavy hitter flows is a fundamental problem in various network domains. The well established method of using sketches to approximate flow statistics suffers from space inefficiencies. In addition, flow arrival rates are dynamic, thus keeping track of the most recent heavy hitters poses a challenge. Sliding window approximations address this problem, reducing space at the cost of increasing point query time. This paper presents two novel algorithms for identifying heavy hitters in streams and sliding windows. Both algorithms use statically allocated memory and support constant time point queries. For sliding windows, this is an asymptotic improvement over previous work. We also demonstrate reduced memory requirements of up to 85% in streams and 66% in sliding windows over synthetic and real Internet packet traces.

A Wireless Sensor Network consists of a number of sensors. The energy of each sensor is limited which limits network lifetime. There are many existing energy efficiency algorithms to prolong network lifetime. Basically, there are two kinds of methods. One is energy-efficiency management, such as duty-cycling using virtual-backbones. The other one is energy provision, such as energy harvest from the environment. In this paper, we introduce a new problem, CDSEH, to combine these two methods together. We also propose a new standard to define the network lifetime of a WSN. We prove that the CDSEH problem is NP-Complete and propose two approximate algorithms accordingly. Extensive simulation results are shown to validate the performance of our algorithms.

In a crowdsourcing system, it is important for the crowdsourcer to engineer extrinsic rewards to incentivize the participants. With mobile social networking, a user enjoys an intrinsic benefit when she aligns her behavior with the behavior of others. Referred to as network effects, such an intrinsic benefit becomes more significant as the number of users grows in the crowdsourcing system. But should a crowdsourcer design her extrinsic rewards differently when such network effects are taken into account? In this paper, we, for the first time, consider network effects as a contributing factor to intrinsic rewards, and study its influence on the design of extrinsic rewards. Rather than assuming a fixed participant population, we show that the number of participating users evolves to a steady equilibrium, thanks to subtle interactions between intrinsic rewards due to network effects and extrinsic rewards offered by the crowdsourcer. Taken network effects into consideration, we design progressively more sophisticated extrinsic reward mechanisms, and propose new and optimal strategies for a crowdsourcer to obtain a higher utility. Via extensive simulations, we demonstrate that with our new strategies, a crowdsourcer is able to attract more participants with higher contributed efforts; and participants gain higher utilities from both intrinsic and extrinsic rewards.

Global broadcasting is a fundamental problem in wireless multi-hop networks. In this paper, we propose two distributed deterministic algorithms for global broadcasting based on the Signal-to-Interference-plus-Noise-Ratio (SINR) model. In both algorithms, an arbitrary node can become the source node, and the rest of the nodes are divided into different layers according to their distance to the source node. A broadcast message is propagated from the source node to all the other nodes in a layer by layer fashion. Our first proposed algorithm (named TEGB) selects a Maximal Independent Set (MIS) for each layer. Subsequently, multiple subsets of the MIS are carefully selected so as to allow the most concurrent transmissions. Our theoretical analysis shows that TEGB has the time complexity of O(D log n), where n is the total number of nodes in the network and D is the diameter of the network. Compared with the popular algorithm DetGenBroadcast proposed in the work of Jurdzinski et al.(2013), TEGB has a logarithmic improvement in running time. Furthermore, we develop the second algorithm (named TBGB) to reduce the number of duplicated broadcast messages at each layer. To be specific, TBGB attempts to form a unidirectional spanning tree of the network. On the spanning tree, only the non-leaf nodes transmit the broadcast message. Therefore, the redundant broadcasts in the same layer are eliminated. Our theoretical analysis shows that TBGB has the time complexity of O(DΔ log n), where Δ is the maximum node degree.

Femtocells (small cells) augment the current mobile network by providing users short-range radio access at home and small-business settings. They have rapidly emerged as a promising scheme to alleviate capacity and coverage shortage by offloading traffic from the conventional Macrocells (large cells). Despite its increasing popularity, the real-world Femtocell performance has remained largely unexplored. In this paper, we conduct an in-depth study to assess Femtocell performance and diagnose identified issues in operational carrier networks. We focus on user-deployed Femtocells in a top-tier US mobile network. While the Femtocell generally works well, unanticipated performance degradations and even failures still occur. Contrary to conventional wisdom in the research community, we find that, radio link quality and interference is not the main bottleneck of Femtocells in many real-life usage scenarios. For instance, while Femtocell deployment at blind-zones with no radio coverage is desirable, not all deployments have succeeded; Compared with their Macrocell counterparts, Femtocells exhibit lower speed and larger speed variations, and induce larger delay for data services. Moreover, mobility support for femtocells is incomplete and no seamless migration is available under certain usage scenarios. We pinpoint their root causes, quantify the potential impacts, and share the learned lessons.

Openflow is a key step in abstracting network functions by separating the control and the forwarding plane. However, even with continuous innovation and evolution of the protocol, its adoption on forwarding device targets remains laborious and time consuming. In this paper, we present a semantic-based approach to packet forwarding design that tailors flow classification to the underlying switch device. Its key idea consist in streamlining flow classification through rule compiling and thus to optimize forwarding operations and improve switch resources usage. The compiling itself exploits a rule grouping gleaned through Frequent Pattern Mining and Network Calculus in optimizing flow classification w.r.t. the switch pipelined architecture.

Fast Reroute (FRR) and other forms of immediate failover have long been used to recover from certain classes of failures without invoking the network control plane. While the set of such techniques is growing, the level of resiliency to failures that this approach can provide is not adequately understood. We embark upon a systematic algorithmic study of the resiliency of immediate failover in a variety of models (with/without packet marking/duplication, etc.). We leverage our findings to devise new schemes for immediate failover and show, both theoretically and experimentally, that these outperform existing approaches.

Contamination in drinkable water distribution networks can be potentially monitored by new and agile mobile sensor networks. These sensor networks are composed of static sensor nodes, which are pre-installed, of mobile sensor nodes, which are released into the water network for a more punctual monitoring, and of sink nodes, which are used to collect data from mobile sensor nodes. Thus, the activation of the sink nodes as well as the release locations of the mobile nodes must be carefully decided to ensure timely and accurate event detections. Unfortunately, no approach can be found in the literature to optimally determine the release locations of the mobile sensor nodes and the activation of the sink nodes. In this paper, a novel optimization approach to solve such a problem is posed. The problem is particularly challenging due to the potential large size of the networks, the undetermined movement of the mobile sensor nodes, the integer decision variables associated to the release locations of these mobile sensor nodes, and the binary decision variables associated to the activation of the sink nodes. To account for the mobile node mobility across the water distribution network, a stochastic mobility model is considered. It is shown that the objective function of the optimization problem exhibits submodular properties, which allow establishing a mobile nodes release algorithm. The benefits and efficiency of the proposed algorithm are illustrated by analysis and numerical evaluations. It is concluded that the proposed optimization based approach allows efficient monitoring of water distribution networks by mobile sensor nodes.

We consider distributed network routing for networks that support differentiated services, where services are prioritized by a proportional weighting system. We use the classical Generalized Processor Sharing (GPS) scheme for scheduling traffic on network links. In such a scheme, each type of traffic is guaranteed a minimum capacity rate based on its priority. To model the performance of this scheme and to account for autonomous routing we consider scheduling games on networks. We consider both networks with a set of parallel links (which also applies to processor scheduling) and more general scenarios where the network is a multi-graph. In each of these settings we consider two different routing schemes: Atomic and Non-Atomic. Atomic routing requires all traffic of one type to follow a single path. Non-Atomic routing splits traffic into a flow over multiple paths. For each type of game, we prove either the existence of Nash Equilibrium or give a counterexample. We consider the inefficiency of equilibrium (termed as the price of anarchy) and provide price of anarchy upper bounds under reasonable assumptions. In general, this inefficiency in queuing systems is unbounded. We also provide complexity results on computing optimal solutions and the existence of equilibrium in these games.

We propose FLIP, a new algorithm for SDN network updates that preserve forwarding policies. FLIP builds upon the dualism between replacements and additions of switch flow-table rules. It identifies constraints on rule replacements and additions that independently prevent policy violations from occurring during the update. Moreover, it keeps track of alternative constraints, avoiding the same policy violation. Then, it progressively explores the solution space by swapping constraints with their alternatives, until it reaches a satisfiable set of constraints. Extensive simulations show that FLIP outperforms previous proposals. It achieves a much higher success rate than algorithms based on rule replacements only, and massively reduces the memory overhead with respect to techniques solely relying on rule additions.

Neighbor discovery, the process of discovering all neighbors in a device's communication range, is one of the bootstrapping networking primitives of paramount importance and is particularly challenging when devices have directional antennas instead of omni-directional ones. In this paper, we study the following fundamental problem which we term as oblivious neighbor discovery: How can neighbor nodes with heterogeneous antenna configurations and without clock synchronization discover each other within a bounded delay in a fully decentralised manner without any prior coordination? We first establish a theoretical framework on oblivious neighbor discovery and establish the performance bound of any neighbor discovery protocol achieving oblivious discovery. Guided by the theoretical results, we then design an oblivious neighbor discovery protocol and prove that it achieves guaranteed oblivious discovery with order-minimal worst-case discovery delay in the asynchronous and heterogeneous environment. We further demonstrate how our protocol can be configured to achieve a desired trade-off between average and worst-case performance.

Network operators can better understand their networks when armed with a detailed understanding of the network traffic and host activities. Software-defined networking (SDN) techniques have the potential to improve enterprise security, but the current techniques have well-known data plane scalability concerns and limited visibility into the host's operating context. In this work, we provide both detailed host-based context and fine-grained control of network flows by shifting the SDN agent functionality from the network infrastructure into the end-hosts. We allow network operators to write detailed network policy that can discriminate based on user and program information associated with network flows. In doing so, we find our approach scales far beyond the capabilities of OpenFlow switching hardware, allowing each host to create over 25 new flows per second with no practical bound on the number of established flows in the network.