INFOCOM 2015 论文列表

Based on the tool of stochastic geometry, we present in this paper a framework for analyzing the coverage probability and ergodic rate in a D2D overlaying multi-channel downlink cellular network. Different from previous works, 1) we consider a flexible new scheme for mobile UEs to select operation mode individually, under which a mobile UE decides to establish a cellular link (with a BS) or a D2D link (with a neighboring UE) based on the pilot signal strength received from its nearest BS; 2) we allow a mobile UE which is located far from BSs to connect to a nearby BS via another intermediate UE in a two-hop manner. Our results indicate that the developed framework is very helpful for network designers to efficiently determine the optimal network parameters at which the optimum system performance can be achieved. Furthermore, as corroborated by extensive numerical results, enabling the D2D link based two-hop connection can significantly improve the network coverage performance, especially for the low SIR regime.

Advanced botnets adopt a peer-to-peer (P2P) infrastructure for more resilient command and control (C&C). Traditional detection techniques become less effective in identifying bots that communicate via a P2P structure. In this paper, we present PeerClean, a novel system that detects P2P botnets in real time using only high-level features extracted from C&C network flow traffic. PeerClean reliably distinguishes P2P bot-infected hosts from legitimate P2P hosts by jointly considering flow-level traffic statistics and network connection patterns. Instead of working on individual connections or hosts, PeerClean clusters hosts with similar flow traffic statistics into groups. It then extracts the collective and dynamic connection patterns of each group by leveraging a novel dynamic group behavior analysis. Comparing with the individual host-level connection patterns, the collective group patterns are more robust and differentiable. Multi-class classification models are then used to identify different types of bots based on the established patterns. To increase the detection probability, we further propose to train the model with average group behavior, but to explore the extreme group behavior for the detection. We evaluate PeerClean on real-world flow records from a campus network. Our evaluation shows that PeerClean is able to achieve high detection rates with few false positives.

Multi-user multiple input and multiple output (MU-MIMO) is one predominate approach to improve the wireless capacity. However, since the aggregate capacity of MU-MIMO heavily depends on the channel correlations among the mobile users in a beamforming group, unwisely selecting beamforming groups may result in reduced overall capacity, instead of increasing it. How to select users into a beamforming group becomes the bottleneck of realizing the MU-MIMO gain. The fundamental challenge for user selection is the large searching space, and hence there exists a tradeoff between search complexity and achievable capacity. Previous works have proposed several low complexity heuristic algorithms, but they suffer a significant capacity loss. In this paper, we present a novel MU-MIMO MAC, called SIEVE. The core of SIEVE design is its scalable multi-user selection module that provides a knob to control the aggressiveness in searching the best beamforming group. SIEVE maintains a central database to track the channel and the coherence time for each mobile user, and largely avoids unnecessary computing with a progressive update strategy. Our evaluation, via both small-scale testbed experiments and large-scale trace-driven simulations, shows that SIEVE can achieve around 90% of the capacity compared to exhaustive search.

Traditional models in opinion dynamics involve agents updating their opinions based on the opinions of their neighbors in a static social-graph, regardless of their differences in opinions. In contrast, the bounded confidence opinion dynamics does not presume a static interaction graph, and instead models interactions between those agents that share similar opinions (i.e., are close to one another, capturing online discussion groups and conventional meetings). We generalize the bounded confidence opinion dynamics model by incorporating pairwise stochastic interactions based on opinion differences as well as the self or endogenous evolution of the agent opinions, which is represented by a random process. We analytically characterize the conditions under which this stochastic dynamics is stable in an appropriate sense. This characterization relates well to what is observed in social systems. Moreover, this generalization sheds light on dynamics that combine aspects of graph-based updates and bounded confidence models.

Efficient use of shared resources is a key problem in a wide range of computer systems, from cloud computing to multicore processors. Optimized allocation of resources among users can result in dramatically improved overall system performance. Resource allocation is in general NP-complete, and past works have mostly focused on studying concave performance curves, applying heuristics to nonconcave curves, or finding optimal solutions using slow dynamic programming methods. These approaches have drawbacks in terms of generality, accuracy and efficiency. In this paper, we observe that realistic performance curves are often not concave, but rather can be broken into a small number of concave or convex segments. We present efficient algorithms for optimal and approximately optimal resource allocation leveraging this idea. We also introduce several algorithmic techniques that may be of independent interest. Our optimal algorithm runs in O(snα(m)m(log m)2) time, and our approximation algorithm finds a 1 - ε optimal allocation for any ε > 0 in O(s/ε α(n/ε)n2log n/ε log m) time; here, s is the number of segments, n the number of processes, m the amount of shared resource, and α is the inverse Ackermann function that is ≤ 4 in practice. Existing exact and approximation algorithms have O(nm2) and O(n2m/ε) running times, resp., so our algorithms are much faster in the practical case where n <;<; m. Experiments show that our algorithms are 215 times faster than dynamic programming for finding optimal solutions when m = 1M, and produce solutions with 33% better performance than greedy algorithms.

The Metropolis-Hastings (MH) algorithm, in addition to its application for Markov Chain Monte Carlo sampling or simulation, has been popularly used for constructing a random walk that achieves a given, desired stationary distribution over a graph. Applications include crawling-based sampling of large graphs or online social networks, statistical estimation or inference from massive scale of networked data, efficient searching algorithms in unstructured peer-to-peer networks, randomized routing and movement strategies in wireless sensor networks, to list a few. Despite its versatility, the MH algorithm often causes self-transitions of its resulting random walk at some nodes, which is not efficient in the sense of the Peskun ordering - a partial order between off-diagonal elements of transition matrices of two different Markov chains, and in turn results in deficient performance in terms of asymptotic variance of time averages and expected hitting times with slower speed of convergence. To alleviate this problem, we present simple yet effective distributed algorithms that are guaranteed to improve the MH algorithm over time when running on a graph, and eventually reach `efficiency-optimality', while ensuring the same desired stationary distribution throughout.

Emerging heterogeneous wireless architectures consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). We design a coded caching-and-delivery scheme for such architectures that equips APs with storage, enabling content pre-fetching prior to knowing user demands. Users requesting content are served by connecting to local APs with cached content, as well as by listening to a BS broadcast transmission. For any given content popularity profile, the goal is to design the caching-and-delivery scheme so as to optimally trade off the transmission cost at the BS against the storage cost at the APs and the user cost of connecting to multiple APs. We design a coded caching scheme for non-uniform content popularity that dynamically allocates user access to APs based on requested content. We demonstrate the approximate optimality of our scheme with respect to information-theoretic bounds. We numerically evaluate it on a YouTube dataset and quantify the trade-off between transmission rate, storage, and access cost. Our numerical results also suggest the intriguing possibility that, to gain most of the benefits of coded caching, it suffices to divide the content into a small number of popularity classes.

With mobile devices increasingly able to connect to cloud servers from anywhere, resource-constrained devices can potentially perform offloading of computational tasks to either improve resource usage or improve performance. It is of interest to find optimal assignments of tasks to local and remote devices that can take into account the application-specific profile, availability of computational resources, and link connectivity, and find a balance between energy consumption costs of mobile devices and latency for delay-sensitive applications. Given an application described by a task dependency graph, we formulate an optimization problem to minimize the latency while meeting prescribed resource utilization constraints. Different from most of existing works that either rely on an integer linear programming formulation, which is NP-hard and not applicable to general task dependency graph for latency metrics, or on intuitively derived heuristics that offer no theoretical performance guarantees, we propose Hermes, a novel fully polynomial time problem approximation scheme (FPTAS) algorithm to solve this problem. Hermes pros vides a solution with latency no more than (1 + ε) times of the minimum while incurring complexity that is an polynomial in problem size and //ε We evaluate the performance by using real data set collected from several benchmarks, and show that Hermes improves the latency by 16% (36% for larger scale application) compared to a previously published heuristic and increases CPU computing time by only 0.4% of overall latency.

We study a fundamental question that arises in social recommender systems: whether it is possible to simultaneously maximize (a) an individual's benefit from using a social network and (b) the efficiency of the network in disseminating information. To tackle this question, our study consists of three components. First, we introduce a stylized stochastic model for recommendation diffusion. Such a model allows us to highlight the connection between user experience at the individual level, and network efficiency at the macroscopic level. We also propose a set of metrics for quantifying both user experience and network efficiency. Second, based on these metrics, we extensively study the tradeoff between the two factors in a Yelp dataset, concluding that Yelp's social network is surprisingly efficient, though not optimal. Finally, we design a friend recommendation and news feed curation algorithm that can simultaneously address individuals' need to connect to high quality friends, and service providers' need to maximize network efficiency in information propagation.

Today's WLANs are struggling to provide desirable features like high efficiency, fairness and QoS because of the use of Distributed Coordination Function (DCF). In this paper we present OpenTDMF, an architecture to enable TDMA on commodity WLAN devices. Our hope is to provide the desirable features without entirely rebuilding the WLAN infrastructure. OpenTDMF is inspired by and architecturally similar to Software Defined Networking (SDN). Specifically, we leverage the backhaul of WLAN to coordinate all the stations for channel access. This fine-grained coordination is performed in a decoupled control plane which includes a central controller and programmable APs. To realize OpenTDMF on commodity WLAN devices, we develop several novel techniques to achieve μs-level time synchronization among all the APs. We also enable AP-triggered uplink transmission so that all the transmissions in the WLAN can be determined. We implemented a prototype of OpenTDMF based on commodity WLAN devices. Empirical results validate the OpenTDMF design and demonstrate its benefits.

In the data flow models of today's data center applications such as MapReduce, Spark and Dryad, multiple flows can comprise a coflow group semantically. Only completing all flows in a coflow is meaningful to an application. To optimize application performance, routing and scheduling must be jointly considered at the level of a coflow rather than individual flows. However, prior solutions have significant limitation: they only consider scheduling, which is insufficient. To this end, we present Rapier, a coflow-aware network optimization framework that seamlessly integrates routing and scheduling for better application performance. Using a small-scale testbed implementation and large-scale simulations, we demonstrate that Rapier significantly reduces the average coflow completion time (CCT) by up to 79.30% compared to the state-of-the-art scheduling-only solution, and it is readily implementable with existing commodity switches.

Mixing time is a global property of a network that indicates how fast a random walk gains independence from its starting point. Mixing time is an essential parameter for many distributed algorithms, but especially those based on gossip. We design, implement, and evaluate a distributed protocol to measure mixing time. The protocol extends an existing algorithm that models the diffusion of information seen from each node in the network as the impulse response of a particular dynamic system. In its original formulation, the algorithm was susceptible to topology changes (or “churn”) and was evaluated only in simulation. Here we present a concrete implementation of an enhanced version of the algorithm that exploits multiple parallel runs to obtain a robust measurement, and evaluate it using a network testbed (Emulab) in combination with a peer-to-peer system (FreePastry) to assess both its performance and its ability to deal with network churn.

Device-to-device (D2D) communication underlaying cellular networks is a promising technology to improve network resource utilization. In D2D-enabled cellular networks, the interference among spectrum-sharing links is more severer than that in traditional cellular networks, which motivates the adoption of interference cancellation techniques such as successive interference cancellation (SIC) at the receivers. However, to date, how SIC can affect the performance of D2D-enabled cellular networks is still unknown. In this paper, we present an analytical framework for studying the performance of SIC in large-scale D2D-enabled cellular networks using the tools from stochastic geometry. To facilitate the interference analysis, we propose the approach of stochastic equivalence of the interference, which converts the two-tier interference (interference from both the cellular tier and D2D tier) to an equivalent single-tier interference. Based on the proposed stochastic equivalence models, we derive the general expressions for the successful transmission probabilities of cellular uplinks and D2D links with infinite and finite SIC capabilities respectively. We demonstrate how SIC affects the performance of large-scale D2D-enabled cellular networks by both analytical and numerical results.

Incentive mechanisms for crowdsourcing have been extensively studied under the framework of all-pay auctions. Along a distinct line, this paper proposes to use Tullock contests as an alternative tool to design incentive mechanisms for crowdsourcing. We are inspired by the conduciveness of Tullock contests to attracting user entry (yet not necessarily a higher revenue) in other domains. In this paper, we explore a new dimension in optimal Tullock contest design, by superseding the contest prize - which is fixed in conventional Tullock contests - with a prize function that is dependent on the (unknown) winner's contribution, in order to maximize the crowdsourcer's utility. We show that this approach leads to attractive practical advantages: (a) it is well-suited for rapid prototyping in fully distributed web agents and smartphone apps; (b) it overcomes the disincentive to participate caused by players' antagonism to an increasing number of rivals. Furthermore, we optimize conventional, fixed-prize Tullock contests to construct the most superior benchmark to compare against our mechanism. Through extensive evaluations, we show that our mechanism significantly outperforms the optimal benchmark, by over three folds on the crowdsourcer's utility cum profit and up to nine folds on the players' social welfare.

Multiflow problems are one of the most fundamental problems in both wired networks and wireless networks. Due to the cross-layer nature, multiflow problems in wireless networks are significantly harder than their counterparts in wired networks and have received much research interest over the past decade. Common to most other early-staged research, the characterization of computational hardness and the “war” on achievable approximation bounds have been the priority to the existing studies of multiflow problems in wireless networks while their practical feasibility in both running time and memory requirement is ignored as long they are polynomial. In fact, almost all of the state-of-the-art approximation algorithms for multiflow problems in wireless networks are all resorted to the traditional linear programming (LP) methods exclusively. However, those traditional LP methods can require an inordinate amount of running time and memory even for a moderate sized input, and consequently they often prove unusable in practice. This paper presents a completely new paradigm for multiflow problems in general wireless networks which is radically different from the prevailing LP-based paradigm, and develops practical algorithmic solutions which are much faster and simpler.

With limited opportunities to open up new unencumbered bands to mobile wireless services, interest in enhancing methods for sharing of spectrum between services is high. For example, the band 1695-1710 MHz is expected to be made available to 3GPP Long-Term Evolution cellular network uplinks by sharing with incumbent meteorological satellite services already in the band. The LTE networks are to be operated in a manner that ensures no loss of incumbent capability by adhering to protection requirements such as a limit on the aggregate interference power at fixed incumbent earth station locations. In this paper, we consider this specific spectrum sharing scenario as motivation and formulate an optimization framework for power control and time-frequency resource scheduling on the LTE uplink with an aggregate interference constraint. We design and propose a novel algorithm inspired by numerical solution and analysis of the optimization problem. Using theory and simulation, we show that our algorithm significantly outperforms more simplistic approaches, well approximates the optimal solution, and is of sufficient scope and complexity for practical implementation, even in relatively large LTE networks. Algorithms of this kind are necessary for mobile wireless networks to make the most of constrained spectrum resources in shared bands.

Controlling a dynamic network is interesting and important in practical applications, which is to drive the network from any initial state to any desired state. Much research has been conducted in revealing the controllability and seeking the underlying correlations of the network. However, no existing works have considered the time needed to control the network, which we refer to as control latency. In this paper, we initiate the study of control latency of dynamic networks. First of all, we formulate the minimum control latency (MCL) problem for designing the controlling pattern with minimum number of controllers. We show that the MCL problem is NP-hard by reducing the multiprocessor scheduling problem to it. Then, we propose a greedy algorithm for designing a controlling pattern that can control the network within two times the minimum control latency. Moreover, when the control latency is bounded by a given value, we propose another constant approximation algorithm to design a controlling pattern which uses at most three times the minimum number of controllers. We conduct extensive simulations on both synthetic and real networks to corroborate our theoretic analysis.

The Bring-Your-Own-Handheld-device (BYOH) phenomenon continues to make inroads as more people bring their own handheld devices to work or school. While convenient to device owners, this trend presents novel management challenges to network administrators. Prior efforts only focused on studying either the comparative characterization of aggregate network traffic between BYOHs and non-BYOHs or network performance issues, such as TCP and download times or mobility issues. We identify one critical question that network administrators need to answer: how do these BYOHs behave individually? In response, we design and deploy Brofiler, a behavior-aware profiling framework that improves visibility into the management of BYOHs. The contributions of our work are two-fold. First, we present Brofiler, a time-aware device-centric approach for grouping devices into intuitive behavioral groups. Second, we conduct an extensive study of BYOHs using our approach with real data collected over a year, and highlight several novel insights on the behavior of BYOHs. These observations underscore the importance of that BYOHs need to be managed explicitly as they behave in unique and unexpected ways.

How many links can be cut before a network is bisected? What is the maximal bandwidth that can be pushed between two nodes of a network? These questions are closely related to network resilience, path choice for multipath routing or bisection bandwidth estimations in data centers. The answer is quantified using metrics such as the number of edge-disjoint paths between two network nodes and the cumulative bandwidth that can flow over these paths. In practice though, such calculations are far from simple due to the restrictive effect of network policies on path selection. Policies are set by network administrators to conform to service level agreements, protect valuable resources or optimize network performance. In this work, we introduce a general methodology for estimating lower and upper bounds for the policy-compliant path diversity and bisection bandwidth between two nodes of a network, effectively quantifying the effect of policies on these metrics. Exact values can be obtained if certain conditions hold. The approach is based on regular languages and can be applied in a variety of use cases.