INFOCOM 2015 论文列表

Accurate and sufficient range measurements are essential for range-based localization in wireless sensor networks. However, noise and data missing are inevitable in distance ranging, which may degrade localization accuracy drastically. Existing localization approaches often degrade in terms of accuracy in the co-existence of incomplete and corrupted range measurements. To address this challenge, a noise-tolerant localization algorithm called NLIRM is presented. By utilizing the natural low rank property of Euclidean distance matrix, the reconstruction of partially sampled and noisy distance matrix is formulated as a norm-regularized matrix completion problem, where Gaussian noises and outliers are smoothed by Frobenius-norm and L1norm regularization, respectively. As far as we are aware of, this is the first scheme that can recover the missing range measurements and explicitly sift Gaussian noise and outlier simultaneously. Simulation results demonstrate that, compared with traditional algorithms, NLIRM achieves better localization performance under the same experiment setting. In addition, our algorithm provides an accurate prediction of outlier positions, which is the prerequisite for malfunction diagnosis in WSN.

Tiered networks have been introduced to mitigate the issues related to poor cellular coverage in dead zones and indoor environments. However, the large-scale deployment of multiple tiers can result in severe intra-tier and inter-tier interference that can considerably degrade the performance of users in all tiers. Thus, the network interference analysis has been an important topic in tiered networks. In this paper, we focus on the uplink resource reusing scenario in a two-tier cellular network consisting of a macro cell and multiple femto cells. Without imposing any limitations on the shape of the macro/femto cells (as long as they are approximated by polygons), for the first time in the literature, we obtain the distance distributions associated with tiered structures. Utilizing these distance distributions and the path-loss model in an interference-limited environment, we obtain the distributions of the received signal and interference for both tiers. Further, we give details on how our approach applies to the downlink resource reusing scenario as well as a network with multiple macro cells. Our performance study provides insights into the Signal-to-Interference Ratio and outage probability for macro/femto-cell base stations.

Most of today's data center networks (DCNs) adopt a multi-rooted tree structure called fat-tree, which delivers large bisection bandwidth through rich path multiplicity. In fat-tree DCNs, core switch modules play an important role in providing nonblocking capability, and form a significant part of network cost simultaneously. Reducing core switches while simultaneously guaranteeing performance has been a constant challenge. For example, multicast is an essential communication pattern in cloud services which needs to be supported efficiently. In this paper, we propose virtual network embedding schemes to deal with this problem. In the first scheme, we place the virtual machines (VMs) of a multicast-capable virtual network (MVN) as compact as possible, without any disturbance to existing traffic. In the second scheme, we manage to keep VMs in an even more compact way to reduce cost by allowing a small degree of VM migration. Both schemes are guaranteed to support any multicast communications within MVNs, and simultaneously achieve significant cost saving in terms of core switches, compared to currently best known result. Moreover, we show that our schemes incur only a small overhead in terms of migrations. Finally, we evaluate the performance of proposed schemes and validate the theoretical analysis through extensive simulations.

Data center network has become an important facility for hosting various online services and applications, and thus its performance and underlying technologies are attracting more and more interests. In order to achieve better network performance, recent studies have proposed to tailor data center network traffic management in different aspects, devising various routing and transport schemes. In particular, for applications that must serve users in a timely manner, strict deadlines for their internal traffic flows should be met, and are explicitly taken into consideration in some latest flow rate control or scheduling algorithms in data center networks. In this paper, we advocate that when designing such deadline-aware rate control schemes, a simple principle should be followed: flows with different deadlines should be differentiated in their bandwidth allocation/occupation, and the more traffic load, the more differentiation should be made. We derive sufficient and necessary conditions for a flow rate control scheme to follow this principle, and present a simple congestion control algorithm called Load Proportional Differentiation (LPD) as its application. We have evaluated LPD under different topologies and load scenarios, both by simulation and in real testbed. Our results show that LPD nearly always outperforms D2TCP, a latest deadline-aware rate control scheme, and often reduces the number of flows missing their deadlines by more than 50%. We also give some other applications of this principle, for example, in reducing flow completion time.

The growing volume of mobile data traffic has led many Internet service providers (ISPs) to cap their users' monthly data usage, with overage fees for exceeding their caps. In this work, we examine a secondary data market in which users can buy and sell leftover data caps from each other. China Mobile Hong Kong recently introduced such a market. While similar to an auction in that users submit bids to buy and sell data, it differs from traditional double auctions in that the ISP serves as the middleman between buyers and sellers. We derive the optimal prices and amount of data that different buyers and sellers are willing to bid in this market and then propose an algorithm for ISPs to match buyers and sellers. We compare the optimal matching for different ISP objectives and derive conditions under which an ISP can obtain higher revenue with the secondary market: while the ISP loses revenue from overage fees, it can assess administration fees and take the differences between the buyer and seller prices. Finally, we use one year of usage data from 100 U.S. mobile users to illustrate that the conditions for a revenue increase can hold in practice.

In networking research, it is often desirable to generate synthetic graphs with certain properties. In this paper, we present a new algorithm, 2K_Simple, for exact construction of simple graphs with a target joint degree matrix (JDM). We prove that the algorithm constructs exactly the target JDM and that its running time is linear in the number of edges. Furthermore, we show that the algorithm poses less constraints on the graph structure than previous state-of-the-art construction algorithms. We exploit this flexibility to extend 2K_Simple and design two algorithms that achieve additional network properties on top of the exact target JDM. In particular, 2K_Simple_Clustering produces simple graphs with a target JDM and average clustering coefficient close to a target, while 2K_Simple_Attributes produces exactly simple graphs with a target JDM and joint occurrence of node attribute pairs. We exhaustively evaluate our algorithms through simulation for small graphs, and we also demonstrate their benefits in generating graphs that resemble real-world social networks in terms of accuracy and speed; we reduce the running time by orders of magnitudes compared to previous approaches that rely on Monte Carlo Markov Chains.

Empowered by today's rich tools for media generation and distribution, and the convenient Internet access, crowdsourced streaming generalizes the single-source streaming paradigm by including massive contributors for a video channel. It calls a joint optimization along the path from crowdsourcers, through streaming servers, to the end-users to minimize the overall latency. The dynamics of the video sources, together with the globalized request demands and the high computation demand from each sourcer, make crowdsourced live streaming challenging even with powerful support from modern cloud computing. In this paper, we present a generic framework that facilitates a cost-effective cloud service for crowdsourced live streaming. Through adaptively leasing, the cloud servers can be provisioned in a fine granularity to accommodate geo-distributed video crowdsourcers. We present an optimal solution to deal with service migration among cloud instances of diverse lease prices. It also addresses the location impact to the streaming quality. To understand the performance of the proposed strategies in the realworld, we have built a prototype system running over the planetlab and the Amazon/Microsoft Cloud. Our extensive experiments demonstrate that the effectiveness of our solution in terms of deployment cost and streaming quality.

Social Networking Service has become an essential part of our life today. However, many privacy concerns have recently been raised due to the centralized nature of such services. Decentralized Social Network (DSN) is believed to be a viable solution for these problems. In this paper, we design a protocol to coordinate the pulling operation of DSN nodes. The protocol is the result of forward engineering via utility maximization that takes communication layer congestion level as well as social network layer centrality into consideration. We solve the pulling rate control problem using the primal-dual approach and prove that the protocol can converge quickly when executed in a decentralized manner. Furthermore, we develop a novel “drumbeats” algorithm to estimate node centrality purely based on passively-observed information. Simulation results show that our protocol reduces the average message propagation delay by 15% when comparing to the baselined Fixed Equal Gap Pull protocol. In addition, the estimated node centrality matches well with the ground-truth derived from the actual topology of the social network.

Human tracking in video has many practical applications such as visual guided navigation, assisted living, etc. In such applications, it is necessary to accurately track multiple humans across multiple cameras, subject to real-time constraints. Despite recent advances in visual tracking research, the tracking systems purely relying on visual information fail to meet the accuracy and real-time requirements at the same time. In this paper, we present a novel accurate and real-time human tracking system called VM-Tracking. The system aggregates the information of motion (M) sensor on human, and integrates it with visual (V) data based on physical locations. The system has two key features, i.e. location-based VM fusion and appearance-free tracking, which significantly distinguish itself from other existing human tracking systems. We have implemented the VM-Tracking system and conducted comprehensive experiments on challenging scenarios.

Crowdsourcing services have emerged and become popular on the Internet in recent years. However, evidence shows that crowdsourcing can be maliciously manipulated. In this paper, we focus on the “dark side” of the crowdsourcing services. More specifically, we investigate the spam campaigns that are originated and orchestrated on a large Chinese-based crowdsourcing website, namely ZhuBaJie.com, and track the crowd workers to their spamming behaviors on Baidu Zhidao, the largest community-based question answering (QA) site in China. By linking the spam campaigns, workers, spammer accounts, and spamming behaviors together, we are able to reveal the entire ecosystem that underlies the crowdsourcing spam attacks. We present a comprehensive and insightful analysis of the ecosystem from multiple perspectives, including the scale and scope of the spam attacks, Sybil accounts and colluding strategy employed by the spammers, workers' efforts and monetary rewards, and quality control performed by the spam campaigners, etc. We also analyze the behavioral discrepancies between the spammer accounts and the legitimate users in community QA, and present methodologies for detecting the spammers based on our understandings on the crowdsourcing spam ecosystem.

The Software-Defined Networking approach permits to realize new policies. In OpenFlow in particular, a controller decides on behalf of the switches which forwarding rules must be installed and where. However with this flexibility comes the challenge of the computation of a rule allocation matrix meeting both high-level policies and the network constraints such as memory or link capacity limitations. Nevertheless, in many situations (e.g., data-center networks), the exact path followed by packets does not severely impact performances as long as packets are delivered according to the endpoint policy. It is thus possible to deviate part of the traffic to alternative paths so to better use network resources without violating the endpoint policy. In this paper, we propose a linear optimization model of the rule allocation problem in resource constrained OpenFlow networks with relaxing routing policy. We show that the general problem is NP-hard and propose a polynomial time heuristic, called OFFICER, which aims to maximize the amount of carried traffic in under-provisioned networks. Our numerical evaluation on four different topologies shows that exploiting various paths allows to increase the amount of traffic supported by the network without significantly increasing the path length.

Neighbor discovery is a crucial first step in configuring and managing a wireless network. Most existing studies on neighbor discovery are based on broadcast algorithms, where nodes send 1-way messages without getting response from their neighbors. However, when directional antennas are used, the ability to coordinate with a neighbor is crucial for later communication between nodes, which requires handshake-based (at least 2-way) protocols. In this paper, we provide a detailed analysis of neighbor discovery protocols with 2-way communication when using directional antennas. Based on this analysis, we present the design of a randomized 2-way neighbor discovery algorithm that uses a selective feedback. Our result shows that a node needs Θ(n2/k) time to discover its n neighbors with k antenna sectors, which yields a significant performance improvement over pure randomized algorithms. We also extend our schemes to practical cases, where the number of neighbors is unknown, and show a factor of no more than 4/3 slowdown in performance.

Fusing fingerprints with mutual distance information potentially improves indoor localization accuracy. Such distance information may be spatial (e.g., via inter-node measurement) or temporal (e.g., via dead reckoning). Previous approaches on distance fusion often require exact distance measurement, assume the knowledge of distance distribution, or apply narrowly to some specific sensing technology or scenario. Due to random signal fluctuation, wireless fingerprints are inherently noisy and distance cannot be exactly measured. We hence propose Wi-Dist, a highly accurate indoor localization framework fusing noisy fingerprints with uncertain mutual distances (given by their bounds). Wi-Dist is a generic framework applicable to a wide range of sensors (peer-assisted, INS, etc.) and wireless fingerprints (Wi-Fi, RFID, CSI, etc.). It achieves low errors by a convex-optimization formulation which jointly considers distance bounds and only the first two moments of measured fingerprint signals. We implement Wi-Dist, and conduct extensive simulation and experimental studies based on Wi-Fi in our international airport and university campus. Our results show that Wi-Dist achieves significantly better accuracy than other state-of-the-art schemes (often by more than 40%).

This paper demonstrates that end-to-end active measurements can give invaluable insights into the nature and characteristics of packet loss in cellular networks. We conduct a large-scale measurement study of packet loss in four UMTS networks. The study is based on active measurements from hundreds of measurement nodes over a period of one year. We find that a significant fraction of loss occurs during pathological and normal Radio Resource Control (RRC) state transitions. The remaining loss exhibits pronounced diurnal patterns and shows a relatively strong correlation between geographically diverse measurement nodes. Our results indicate that the causes of a significant part of the remaining loss lie beyond the radio access network.

In many computing and networking applications, arriving tasks have to be routed to one of many servers, with the goal of minimizing queueing delays. When the number of processors is very large, a popular routing algorithm works as follows: select two servers at random and route an arriving task to the least loaded of the two. It is well-known that this algorithm dramatically reduces queueing delays compared to an algorithm which routes to a single randomly selected server. In recent cloud computing applications, it has been observed that even sampling two queues per arriving task can be expensive and can even increase delays due to messaging overhead. So there is an interest in reducing the number of sampled queues per arriving task. In this paper, we show that the number of sampled queues can be dramatically reduced by using the fact that tasks arrive in batches (called jobs). In particular, we sample a subset of the queues such that the size of the subset is slightly larger than the batch size (thus, on average, we only sample slightly more than one queue per task). Once a random subset of the queues is sampled, we propose a new load balancing method called batch-filling to attempt to equalize the load among the sampled servers. We show that our algorithm dramatically reduces the sample complexity compared to previously proposed algorithms.

Signature-based network intrusion detection systems (S-IDS) have become an important security tool in the protection of an organisation's infrastructure against external intruders. By analysing network traffic, S-IDS' detect network intrusions. An organisation may deploy one or multiple S-IDS', each working independently with the assumption that it can monitor all packets of a given flow to detect intrusion signatures. However, emerging technologies (e.g., Multi-Path TCP) violate this assumption, as traffic can be concurrently sent across different paths (e.g., WiFi, Cellular) to boost network performance. Attackers may exploit this capability and split malicious payloads across multiple paths to evade traditional signature-based network intrusion detection systems. Although multiple monitors may be deployed, none of them has the full coverage of the network traffic to detect the intrusion signature. In this paper, we formalise this distributed signature-based intrusion detection problem as an asynchronous online exact string matching problem, and propose an algorithm for it. To demonstrate its effectiveness we conducted comprehensive experiments. Our results show that the behaviour of our algorithm depends only on the packet arrival rate: delay in detecting the signature grows linearly with respect to the packet arrival rate and with small communication overhead.

WiFi offloading, where mobile users opportunistically obtain data through WiFi rather than through cellular networks, is a promising technique to greatly improve spectrum efficiency and reduce cellular network congestion. We consider a system where the service provider deploys multiple WiFi hotspots to offload mobile traffic, and study the scheduling policy to maximize the amount of offloaded data. Since the movements of users are unpredictable, we focus on online scheduling policy where APs do not have any knowledge about the users' mobility patterns. We study performance of online policies by comparing against the optimal offline policy. We prove that any work-conserving policy is able to offload at least half as much data as the offline policy, and then propose an online policy that can offload (e-1)/e as much data as the offline policy. We further study the case where the service provider can increase the capacity of WiFi so as to provide guarantees on the amount of offloaded data. We propose a simple online policy and prove that our policy only needs half as much capacity as current mechanism to provide the same performance guarantee.

Cognitive radio networks rely on spectrum sensing performed in a collaborative manner by the cognitive nodes themselves. Priority differentiation in such a network can be accomplished through different scheduling policies, differentiated duration of mandatory spectrum sensing, or a combination of the two. This differentiation will affect not only packet delays, but also the accuracy of channel sensing and, by extension, the probability of collisions with primary user transmissions which will critically affect the operation of the network. In this paper we provide a probabilistic analysis of the interplay between priority differentiation and network performance, and investigate the resulting tradeoffs under different prioritization approaches.

Auctions are believed to be effective methods to solve the problem of wireless spectrum allocation. Existing spectrum auction mechanisms are all centralized and suffer from several critical drawbacks of the centralized systems, which motivates the design of distributed spectrum auction mechanisms. However, extending a centralized spectrum auction to a distributed one broadens the strategy space of agents from one dimension (bid) to three dimensions (bid, communication, and computation), and thus cannot be solved by traditional approaches from mechanism design. In this paper, we propose two distributed spectrum auction mechanisms, namely distributed VCG and FAITH. Distributed VCG implements the celebrated Vickrey-Clarke-Groves mechanism in a distributed fashion to achieve optimal social welfare, at the cost of exponential communication overhead. In contrast, FAITH achieves sub-optimal social welfare with tractable computation and communication overhead. We prove that both of the two proposed mechanisms achieve faithfulness, i.e., the agents' individual utilities are maximized, if they follow the intended strategies. We also implement FAITH and evaluate its performance in various setups. Evaluation results show that FAITH achieves superior performance compared with the Nash equilibrium based approach.