2017 IEEE Conference on Computer Communications, INFOCOM 2017, Atlanta, GA, USA, May 1-4, 2017. IEEE 【DBLP Link】
【Paper Link】 【Pages】:1-9
【Authors】: Chen Tian ; Ali Munir ; Alex X. Liu ; Yingtong Liu ; Yanzhao Li ; Jiajun Sun ; Fan Zhang ; Gong Zhang
【Abstract】: In datacenter networks, flows can have different performance objectives. We use a tenant-objective division to denote all flows of a tenant that share the same objective. Bandwidth allocation in datacenters should support not only performance isolation among divisions but also objective-oriented scheduling among flows within the same division. This paper studies the Multi-Tenant Multi-Objective (MT-MO) bandwidth allocation problem. To our best knowledge, no existing practical work support performance isolation and objective scheduling simultaneously. We propose Stacked Congestion Control (SCC), a distributed host-based bandwidth allocation design, where an underlay congestion control (UCC) layer handles contention among divisions, and a private congestion control (PCC) layer for each division optimizes its performance objective. Via the tenant-objective tunnel abstraction, SCC achieves weighted bandwidth sharing for each division in a distributed and transparent way. By adding a rate-limiting send queue in the ingress of each tunnel, mechanisms between performance isolation and objective scheduling are completely decoupled. We evaluate SCC both on a small-scale testbed and with large-scale NS-2 simulations. Compared to the direct coexistence cases, SCC reduces latency by up to 40% for Latency-Sensitive flows, deadline miss ratio by up to 3.2× for Deadline-Sensitive flows, and average flow-completion-time by up to 53% for Completion-Sensitive flows.
【Keywords】: Channel allocation; Bandwidth; Switches; Interference; Optimal scheduling; Conferences; Servers
【Paper Link】 【Pages】:1-9
【Authors】: Ruozhou Yu ; Guoliang Xue ; Xiang Zhang ; Dan Li
【Abstract】: Cloud computing has emerged as a powerful and elastic platform for internet service hosting, yet it also draws concerns of the unpredictable performance of cloud-based services due to network congestion. To offer predictable performance, the virtual cluster abstraction of cloud services has been proposed, which enables allocation and performance isolation regarding both computing resources and network bandwidth in a simplified virtual network model. One issue arisen in virtual cluster allocation is the survivability of tenant services against physical failures. Existing works have studied virtual cluster backup provisioning with fixed primary embeddings, but have not considered the impact of primary embeddings on backup resource consumption. To address this issue, in this paper we study how to embed virtual clusters survivably in the cloud data center, by jointly optimizing primary and backup embeddings of the virtual clusters. We formally define the survivable virtual cluster embedding problem. We then propose a novel algorithm, which computes the most resource-efficient embedding given a tenant request. Since the optimal algorithm has high time complexity, we further propose a faster heuristic algorithm, which is several orders faster than the optimal solution, yet able to achieve similar performance. Besides theoretical analysis, we evaluate our algorithms via extensive simulations.
【Keywords】: Virtual cluster; survivability; bandwidth guarantee
【Paper Link】 【Pages】:1-9
【Authors】: Yuanwei Lu ; Guo Chen ; Larry Luo ; Kun Tan ; Yongqiang Xiong ; Xiaoliang Wang ; Enhong Chen
【Abstract】: Ideally, minimizing the flow completion time (FCT) requires millions of priorities supported by the underlying network so that each flow has its unique priority. However, in production datacenters, the available switch priority queues for flow scheduling are very limited (merely 2 or 3). This practical constraint seriously degrades the performance of previous approaches. In this paper, we introduce Explicit Priority Notification (EPN), a novel scheduling mechanism which emulates fine-grained priorities (i.e., desired priorities or DP) using only two switch priority queues. EPN can support various flow scheduling disciplines with or without flow size information. We have implemented EPN on commodity switches and evaluated its performance with both testbed experiments and extensive simulations. Our results show that, with flow size information, EPN achieves comparable FCT as pFabric that requires clean-slate switch hardware. And EPN also outperforms TCP by up to 60.5% if it bins the traffic into two priority queues according to flow size. In information-agnostic setting, EPN outperforms PIAS with two priority queues by up to 37.7%. To the best of our knowledge, EPN is the first system that provides millions of priorities for flow scheduling with commodity switches.
【Keywords】: Switches; Hardware; Processor scheduling; Dynamic scheduling; Conferences; Bandwidth
【Paper Link】 【Pages】:1-9
【Authors】: Jinlong E ; Yong Cui ; Peng Wang ; Zhenhua Li ; Chaokun Zhang
【Abstract】: Cloud storage services such as Dropbox have been widely used for file collaboration among multiple users. However, this desirable functionality is yet restricted to the “walled-garden” of each service. At present, the only effective approach to cross-cloud file collaboration seems to be using web APIs, whose performance is known to be highly unstable and unpredictable. Now that using inefficient web APIs is inevitable, in this paper we attempt to achieve sound user-perceived performance for cross-cloud file collaboration. This attempt is enabled by two key observations from real-world measurements. First, for each cloud, we are always able to deploy one or several nearby (client) proxies which can efficiently access the web APIs. Second, during file collaboration, significant similarity exists among different versions of a file. This can be exploited to substantially reduce inter-proxy traffic and thus shorten the data sync time. Guided by the observations, we design and implement an open-source prototype system called CoCloud. Currently, it supports file collaboration among four popular cloud storage services in the US and China. Its performance is well acceptable to users under representative workloads, even approaching or exceeding intra-cloud performance in many cases.
【Keywords】: Collaboration; Cloud computing; Synchronization; Servers; Protocols; Google; Metadata
【Paper Link】 【Pages】:1-9
【Authors】: Chen Chen ; Wei Wang ; Shengkai Zhang ; Bo Li
【Abstract】: Cluster scheduler serves as a critical component to data-parallel systems in datacenters. Ideally, a scheduler should provide predictable performance with guarantees on the maximal job completion delay, while at the same time ensuring the minimal mean response time. Practically however, performance predictability and optimality are often conflicting with each other. The results often are a plethora of scheduling policies that either achieve predictable performance at the expense of long response times (e.g., max-min fairness), or run the risk of starving some jobs to obtain the minimal mean response time (e.g., Shortest Remaining Processing Time First). To address these problems, we develop a new scheduler, Cluster Fair Queueing (CFQ), which preferentially offers resources to jobs that complete the earliest under a fair sharing policy. We show that CFQ is able to minimize the mean response time while at the same time ensuring jobs to finish within a constant time after their completion under fair sharing. Our Spark deployment on a 100-node EC2 cluster demonstrates that compared to the built-in fair scheduler, CFQ can decrease the mean response time by 40%, which speeds up more than 40% of jobs by over 75% on average.
【Keywords】: Time factors; Sparks; Resource management; Delays; Global Positioning System; Prediction algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Li Chen ; Shuhao Liu ; Baochun Li ; Bo Li
【Abstract】: It has become routine for large volumes of data to be generated, stored, and processed across geographically distributed datacenters. To run a single data analytic job on such geo-distributed data, recent research proposed to distribute its tasks across datacenters, considering both data locality and network bandwidth across datacenters. Yet, it remains an open problem in the more general case, where multiple analytic jobs need to fairly share the resources at these geo-distributed data-centers. In this paper, we focus on the problem of assigning tasks belonging to multiple jobs across datacenters, with the specific objective of achieving max-min fairness across jobs sharing these datacenters, in terms of their job completion times. We formulate this problem as a lexicographical minimization problem, which is challenging to solve in practice due to its inherent multi-objective and discrete nature. To address these challenges, we iteratively solve its single-objective subproblems, which can be transformed to equivalent linear programming (LP) problems to be efficiently solved, thanks to their favorable properties. As a highlight of this paper, we have designed and implemented our proposed solution as a fair job scheduler based on Apache Spark, a modern data processing framework. With extensive evaluations of our real-world implementation on Amazon EC2, we have shown convincing evidence that max-min fairness has been achieved using our new job scheduler.
【Keywords】: Bandwidth; Data analysis; Sparks; Distributed databases; Minimization; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Chunguang Li ; Dan Feng ; Yu Hua ; Wen Xia ; Leihua Qin ; Yue Huang ; Yukun Zhou
【Abstract】: Live migration of virtual machines (VM) is one of the key characteristics of virtualization for load balancing, system maintenance, power management, etc., in data centers or clusters. In order to reduce the data transferred and shorten the migration time, the compression techniques have been widely used to accelerate VM migration. However, different compression approaches have different compression ratios and speeds. Because there is a trade-off between compression and transmission, the migration performance improvements obtained from different compression approaches are differentiated, and the improvements vary with the network bandwidth. Besides, the compression window sizes used in most compression algorithms are typically much larger than a single page size, so the traditional single page compression loses some potential compression benefits. In this paper, we design and implement a Bandwidth-Aware Compression (BAC) scheme for VM migration. BAC chooses suitable compression approach according to the network bandwidth available for the migration process, and employs multi-page compression. These features make BAC obtain more migration performance improvements from compression. Experiments under various network scenarios demonstrate that, compared with conventional compression approaches, BAC shortens the total migration time while achieving comparable performance for the total data transferred and the downtime.
【Keywords】: Bandwidth; Acceleration; Kernel; Virtualization; Load management; Maintenance engineering
【Paper Link】 【Pages】:1-9
【Authors】: Ahmed Osama Fathy Atya ; Zhiyun Qian ; Srikanth V. Krishnamurthy ; Thomas F. La Porta ; Patrick D. McDaniel ; Lisa M. Marvel
【Abstract】: Attacker VMs try to co-reside with victim VMs on the same physical infrastructure as a precursor to launching attacks that target information leakage. VM migration is an effective countermeasure against attempts at malicious co-residency. In this paper, we first undertake an experimental study on Amazon EC2 to obtain an in-depth understanding of the side-channels an attacker can use to ascertain co-residency with a victim. Here, we identify a new set of stealthy side-channel attacks which, we show to be more effective than currently available attacks towards verifying co-residency. Based on the study, we develop a set of guidelines to determine under what conditions victim VM migrations should be triggered given performance costs in terms of bandwidth and downtime, that a user is willing to bear. Via extensive experiments on our private in-house cloud, we show that migrations using our guidelines can limit the fraction of the time that an attacker VM co-resides with a victim VM to about 1 % of the time with bandwidth costs of a few MB and downtimes of a few seconds, per day per VM migrated.
【Keywords】: Side-channel attacks; Timing; Guidelines; Bandwidth; Cloud computing; Conferences; Virtual machine monitors
【Paper Link】 【Pages】:1-9
【Authors】: Wenhai Sun ; Ning Zhang ; Wenjing Lou ; Y. Thomas Hou
【Abstract】: As the cost of human full genome sequencing continues to fall, we will soon witness a prodigious amount of human genomic data in the public cloud. To protect the confidentiality of the genetic information of individuals, the data has to be encrypted at rest. On the other hand, encryption severely hinders the use of this valuable information, such as Genome-wide Range Query (GRQ), in medical/genomic research. While the problem of secure range query on outsourced encrypted data has been extensively studied, the current schemes are far from practical deployment in terms of efficiency and scalability due to the data volume in human genome sequencing. In this paper, we investigate the problem of secure GRQ over human raw aligned genomic data in a third-party outsourcing model. Our solution contains a novel secure range query scheme based on multi-keyword symmetric searchable encryption (MSSE). The proposed scheme incurs minimal ciphertext expansion and computation overhead. We also present a hierarchical GRQ-oriented secure index structure tailored for efficient and large-scale genomic data lookup in the cloud while preserving the query privacy. Our experiment on real human genomic data shows that a secure GRQ request with range size 100,000 over more than 300 million encrypted short reads takes less than 3 minutes, which is orders of magnitude faster than existing solutions.
【Keywords】: Genomics; Bioinformatics; Encryption; Sequential analysis; Cloud computing
【Paper Link】 【Pages】:1-9
【Authors】: Xin Li ; Qinghan Xue ; Mooi Choo Chuah
【Abstract】: Image retrieval has become an important function in many emerging computer vision applications e.g. online shopping via images, medical health care systems. More and more images are being generated and stored in public clouds. However, recent photo leakage events raise concerns about privacy leaks for images stored in public clouds. In this paper, we present an efficient scalable hierarchical image retrieval system (CASHEIRS) which provides privacy-aware image retrieval feature. CASHEIRS employs transformed Convolutional Neural Network features to improve image retrieval accuracy and an encrypted hierarchical index tree to speed up the query process. Extensive evaluations using Caltech256 and INRIA Holiday datasets show that CASHEIRS is more effective than three existing schemes. We also demonstrate its practicality on a mobile device.
【Keywords】: Hierarchical image retrieval; Convolutional Neural Network; image privacy
【Paper Link】 【Pages】:1-9
【Authors】: Lei Yang ; Qingji Zheng ; Xinxin Fan
【Abstract】: The integration of cloud computing and Internet of Things (loT) is quickly becoming the key enabler for the digital transformation of the healthcare industry by offering comprehensive improvements in patient engagements, productivity and risk mitigation. This paradigm shift, while bringing numerous benefits and new opportunities to healthcare organizations, has raised a lot of security and privacy concerns. In this paper, we present a reliable, searchable and privacy-preserving e-healthcare system, which takes advantage of emerging cloud storage and IoT infrastructure and enables healthcare service providers (HSPs) to realize remote patient monitoring in a secure and regulatory compliant manner. Our system is built upon a novel dynamic searchable symmetric encryption scheme with forward privacy and delegated verifiability for periodically generated healthcare data. While the forward privacy is achieved by maintaining an increasing counter for each keyword at an IoT gateway, the data owner delegated verifiability comes from the combination of the Bloom filter and aggregate message authentication code. Moreover, our system is able to support multiple HSPs through either data owner assistance or delegation. The detailed security analysis as well as the extensive simulations on a large data set with millions of records demonstrate the practical efficiency of the proposed system for real world healthcare applications.
【Keywords】: Cloud computing; Servers; Medical services; Encryption; Reliability
【Paper Link】 【Pages】:1-9
【Authors】: Qian Wang ; Shengshan Hu ; Minxin Du ; Jingjun Wang ; Kui Ren
【Abstract】: A massive explosion of various types of data has been triggered in the “Big Data” era. In big data systems, machine learning plays an important role due to its effectiveness in discovering hidden information and valuable knowledge. Data privacy, however, becomes an unavoidable concern since big data usually involve multiple organizations, e.g., different healthcare systems and hospitals, who are not in the same trust domain and may be reluctant to share their data publicly. Applying traditional cryptographic tools is a straightforward approach to protect sensitive information, but it often renders learning algorithms useless inevitably. In this work, we, for the first time, propose a novel privacy-preserving scheme for canonical correlation analysis (CCA), which is a well-known learning technique and has been widely used in cross-media retrieval system. We first develop a library of building blocks to support various arithmetics over encrypted real numbers by leveraging additively homomorphic encryption and garbled circuits. Then we encrypt private data by randomly splitting the numerical data, formalize CCA problem and reduce it to a symmetric eigenvalue problem by designing new protocols for privacy-preserving QR decomposition. Finally, we solve all the eigenvalues and the corresponding eigenvectors by running Newton-Raphson method and inverse power method over the ciphertext domain. We carefully analyze the security and extensively evaluate the effectiveness of our design. The results show that our scheme is practically secure, incurs negligible errors compared with performing CCA in the clear and performs comparably in cross-media retrieval systems.
【Keywords】: Cryptography; Correlation; Servers; Wires; Eigenvalues and eigenfunctions; Protocols; Big Data
【Paper Link】 【Pages】:1-9
【Authors】: Pan Li ; Hoang Dau ; Gregory J. Puleo ; Olgica Milenkovic
【Abstract】: Motivated by applications in social network community analysis, we introduce a new clustering paradigm termed motif clustering. Unlike classical clustering, motif clustering aims to minimize the number of clustering errors associated with both edges and certain higher order graph structures (motifs) that represent “atomic units” of social organizations. Our contributions are two-fold: We first introduce motif correlation clustering, in which the goal is to agnostically partition the vertices of a weighted complete graph so that certain predetermined “important” social subgraphs mostly lie within the same cluster, while “less relevant” social subgraphs are allowed to lie across clusters. We then proceed to introduce the notion of motif covers, in which the goal is to cover the vertices of motifs via the smallest number of (near) cliques in the graph. Motif cover algorithms provide a natural solution for overlapping clustering and they also play an important role in latent feature inference of networks. For both motif correlation clustering and its extension introduced via the covering problem, we provide hardness results, algorithmic solutions and community detection results for two well-studied social networks.
【Keywords】: Correlation; Clustering algorithms; Social network services; Conferences; Clustering methods; Approximation algorithms; Linear programming
【Paper Link】 【Pages】:1-9
【Authors】: Guangmo Amo Tong ; Weili Wu ; Ling Guo ; Deying Li ; Cong Liu ; Bin Liu ; Ding-Zhu Du
【Abstract】: Social networks allow rapid spread of ideas and innovations while the negative information can also propagate widely. When the cascades with different opinions reaching the same user, the cascade arriving first is the most likely to be taken by the user. Therefore, once misinformation or rumor is detected, a natural containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of the positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of (1 - 1/e- δ) by a classic greedy algorithm combined with Monte Carlo simulation with the running time of O(k3 mn ln n/δ2), where n and m are the number of users and edges, respectively. Unfortunately, the Monte-Carlo-simulation-based methods are extremely time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized algorithm which runs in O(km ln n/δ2) expected time and provides a (1 - 1/e - δ)-approximation with a high probability. The experimentally results on both the real-world and synthetic social networks have shown that the proposed randomized rumor blocking algorithm is much more efficient than the state-of-the-art method and it is able to find the seed nodes which are effective in limiting the spread of rumor.
【Keywords】: Social network services; Integrated circuit modeling; Approximation algorithms; Diffusion processes; Monte Carlo methods; Sampling methods
【Paper Link】 【Pages】:1-9
【Authors】: Jungseul Ok ; Jinwoo Shin ; Yung Yi
【Abstract】: We consider a problem of how to effectively diffuse a new product over social networks by incentivizing selfish users. Traditionally, this problem has been studied in the form of influence maximization via seeding, where most prior work assumes that seeded users unconditionally and immediately start by adopting the new product and they stay at the new product throughout their lifetime. However, in practice, seeded users often adjust the degree of their willingness to diffuse, depending on how much incentive is given. To address such diffusion willingness, we propose a new incentive model and characterize the speed of diffusion as the value of a combinatorial optimization. Then, we apply the characterization to popular network graph topologies (Erdos-Renyi, planted partition and power law graphs) as well as general ones, for asymptotically computing the diffusion time for those graphs. Our analysis shows that the diffusion time undergoes two levels of order-wise reduction, where the first and second one are solely contributed by the number of seeded users, i.e., quantity, and the amount of incentives, i.e., quality, respectively. In other words, it implies that the best strategy given budget is (a) first identify the minimum seed set depending on the underlying graph topology, and (b) then assign largest possible incentives to users in the set. We believe that our theoretical results provide useful implications and guidelines for designing successful advertising strategies in various practical applications.
【Keywords】: Games; Social network services; Topology; Noise measurement; Algorithm design and analysis; Conferences; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Md. Tanvir Al Amin ; Charu C. Aggarwal ; Shuochao Yao ; Tarek F. Abdelzaher ; Lance M. Kaplan
【Abstract】: This paper presents unsupervised algorithms to uncover polarization in social networks (namely, Twitter) and identify polarized groups. The approach is language-agnostic and thus broadly applicable to global and multilingual media. In cases of conflict, dispute, or situations involving multiple parties with contrasting interests, opinions get divided into different camps. Previous manual inspection of tweets has shown that such situations produce distinguishable signatures on Twitter, as people take sides leading to clusters that preferentially propagate information confirming their individual cluster-specific bias. We propose a model for polarized social networks, and show that approaches based on factorizing the matrix of sources and their claims can automate the discovery of polarized clusters with no need for prior training or natural language processing. In turn, identifying such clusters offers insights into prevalent social conflicts and helps automate the generation of less biased descriptions of ongoing events. We evaluate our factorization algorithms and their results on multiple Twitter datasets involving polarization of opinions, demonstrating the efficacy of our approach. Experiments show that our method is almost always correct in identifying the polarized information from real-world twitter traces, and outperforms the baseline mechanisms by a large margin.
【Keywords】: Twitter; Algorithm design and analysis; Media; Natural language processing; Conferences; Clustering algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Quan Chen ; Hong Gao ; Siyao Cheng ; Jianzhong Li ; Zhipeng Cai
【Abstract】: Data aggregation is an essential operation for the sink to obtain summary information in a Wireless Sensor Network (WSN). The problem of Minimum Latency Aggregation Schedule (MLAS) which seeks a fastest and collision-free aggregation schedule has been well studied when nodes are always awake. However, in duty-cycle WSNs, nodes can only receive data in active state. In such networks, it is of great importance to exploit the limited active time slots to reduce aggregation latency. Unfortunately, few studies have addressed this issue and most previous aggregation methods rely on fixed structures which greatly limit the exploitation of the active time slots from other neighbors. In this paper, we investigate the MLAS problem in duty-cycle WSNs without considering structures. We propose the first distributed aggregation algorithm for duty-cycle WSNs, in which the aggregation tree and a conflict-free schedule are generated simultaneously. Compared with the previous centralized and distributed methods, the aggregation latency and the utilization ratio of available time slots are greatly improved. The theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency and communication cost.
【Keywords】: Schedules; Wireless sensor networks; Data aggregation; Interference; Scheduling algorithms; Approximation algorithms; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Kin Sum Liu ; Tyler Mayer ; Hao-Tsung Yang ; Esther M. Arkin ; Jie Gao ; Mayank Goswami ; Matthew P. Johnson ; Nirman Kumar ; Shan Lin
【Abstract】: In this paper we study the following problem: given a set of m sensors that collectively cover a set of n target points with heterogeneous coverage requirements (target j needs to be covered every fj slots), how to schedule the sensor duty cycles such that all coverage requirements are satisfied and the maximum number of sensors turned on at any time slot is minimized. The problem models varied real-world applications in which sensing tasks exhibit high discrepancy in coverage requirements - critical locations often need to be covered much more frequently. We provide multiple algorithms with best approximation ratio of O (log n + log m) for the maximum number of sensors to turn on, and bi-criteria algorithm with (α, β)-approximation factors with high probability, where the number of sensors turned on is an α = O(δ(log (n) + log(m))/β)-approximation of the optimal (satisfying all requirements) and the coverage requirement is a β-approximation; δ is the approximation ratio achievable in an appropriate instance of set multi-cover. When the sensor coverage exhibits extra geometric properties, the approximation ratios can be further improved. We also evaluated our algorithms via simulations and experiments on a camera testbed. The performance improvement (energy saving) is substantial compared to turning on all sensors all the time, or a random scheduling baseline.
【Keywords】: Sensors; Schedules; Approximation algorithms; Optimal scheduling; Monitoring; Computer science; Cameras
【Paper Link】 【Pages】:1-9
【Authors】: Kaibo Fu ; Wei Ren ; Wei Dong
【Abstract】: Mobile vehicles, equipped with low-cost sensors, can provide unprecedented opportunities for urban monitoring with a wide coverage. The quality of collected data is very important for many applications. The low-cost mobile sensors can, however, suffer from limited accuracy, high instability, and sensor drift. Therefore, they need to be frequently calibrated to preserve a good data quality. Frequent sensor calibration can be achieved by deploying static high-precision sensors (called reference sensors) and exploiting meeting points (i.e., rendezvous) between the reference sensors and mobile sensors. A calibrated mobile sensor can also be used to calibrate an uncalibrated mobile sensor when they meet, referred to as multihop calibration. In this paper, we introduce a novel concept, k-hop calibratability, in the context of multihop calibration: a sensor is k-hop calibratable if the calibration path is no larger than k. We consider the problem of how to deploy the reference sensors to ensure that all sensors in the network are k-hop calibratable. To address this problem, we formally define the rendezvous connection graph to precisely describe the relationship between mobile sensors and (virtual) reference sensors. Based on this definition, we formulate the reference sensor deployment problem as a set cover problem. We also extend our problem to consider practical deployment requirements. We propose efficient algorithms and conduct an extensive evaluation in the context of mobile air quality monitoring. We present a detailed prototype implementation of the mobile sensors and reference sensors. Evaluations using real-world datasets show the effectiveness of the algorithms.
【Keywords】: Mobile communication; Calibration; Robot sensing systems; Monitoring; Air quality; Urban areas
【Paper Link】 【Pages】:1-9
【Authors】: Yibo Wu ; Yi Wang ; Guohong Cao
【Abstract】: Photos crowdsourced from mobile devices can be used in many applications such as disaster recovery to obtain information about a target area. However, such applications often have resource constraints in terms of bandwidth, storage, and processing capability, which limit the number of photos that can be crowdsourced. Thus, it is a challenge to use the limited resources to crowdsource photos that best cover the target area. In this paper, we leverage various geographical and geometrical information about photos, called metadata, to address this challenge. Metadata includes the location, orientation, field of view, and range of a camera. Based on metadata, we define photo utility to measure how well a target area is covered by a set of photos. We propose various techniques to analyze such coverage and calculate photo utility accurately and efficiently. We also study the problem of selecting photos with the largest utility under a resource budget, and propose an efficient algorithm that achieves constant approximation ratio. With our design, the crowdsourcing server can select photos based on metadata instead of real images, and thus use the limited resources to crowdsource the most useful photos. Both simulation and experimental results demonstrate the effectiveness of our design.
【Keywords】: Metadata; Cameras; Crowdsourcing; Bandwidth; Servers; Mobile handsets; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Yiwei Zhuo ; Hongzi Zhu ; Hua Xue ; Shan Chang
【Abstract】: WiFi technology has gained a wide prevalence for not only wireless communication but also pervasive sensing. A wide variety of emerging applications leverage accurate measurements of the Channel State Information (CSI) information obtained from commodity WiFi devices. Due to hardware imperfection of commodity WiFi devices, the frequency response of internal signal processing circuit is mixed with the real channel frequency response in passband, which makes deriving accurate channel frequency response from CSI measurements a challenging task. In this paper, we identify non-negligible non-linear CSI phase errors and report that IQ imbalance is the root source of non-linear CSI phase errors. We conduct intensive analysis on the characteristics of such non-linear errors and find that such errors are prevalent among various WiFi devices. Furthermore, they are rather stable along time and the received signal strength indication (RSSI) but sensitive to frequency bands used between a transmission pair. Based on these key observations, we propose new calibration methods to compensate both non-linear and linear CSI phase errors. We demonstrate the efficacy of the proposed methods by applying them in CSI splicing. Results of extensive real-world experiments indicate that accurate CSI phase measurements can significantly improve the performance of splicing and the stability of the derived power delay profiles (PDPs).
【Keywords】: Channel State Information (CSI); non-linear phase errors; rotation phase error; empirical study; CSI splicing
【Paper Link】 【Pages】:1-9
【Authors】: Seongho Byeon ; Kangjin Yoon ; Changmok Yang ; Sunghyun Choi
【Abstract】: IEEE 802.11n/ac wireless local area network (WLAN) supports frame aggregation, called aggregate medium access control (MAC) protocol data unit (A-MPDU), to enhance MAC efficiency by reducing protocol overhead. However, the current channel estimation process conducted only once during the preamble reception is known to be insufficient to ensure robust delivery of long A-MPDU frames in mobile environments. To cope with this problem, we first build a model which represents the impact of mobility with a noise vector in the I-Q plane, and then analyze how the mobility affects the A-MPDU reception performance. Based on our analysis, we develop STRALE, a standard-compliant and mobility-aware PHY rate and A-MPDU length adaptation scheme with ease of implementation. Through extensive simulations with 802.11ac using ns-3 and prototype implementation with commercial 802.11n devices, we demonstrate that STRALE achieves up to 2.9x higher throughput, compared to a fixed duration setting according to IEEE 802.11 standard.
【Keywords】: Wireless LAN; Channel estimation; OFDM; Signal to noise ratio; Protocols; Receivers; MIMO
【Paper Link】 【Pages】:1-9
【Authors】: Sihui Han ; Kang G. Shin
【Abstract】: Signal decay is the fundamental problem of wireless communications, especially in an indoor environment where line-of-sight (LOS) paths for signal propagation are often blocked and various indoor objects exacerbate signal fading. There are three reasons for signal decay: long transmission distance, signal penetration, and reflection. In this paper, we propose OptRe which optimally places metallic reflectors - providing a highly reflective surface that can reflect impinging signals almost 100% - in indoor environments to reduce the reflection loss and enhance wireless transmissions. It enhances both WiFi signal and low-power IoT devices without changing their configurations or network protocols. To enable OptRe, we first develop an empirical signal propagation model that can accurately estimate the signal strength and adapt itself to the reflectors' location. Using micro-benchmarks, our empirical signal propagation model is shown to be more accurate than the other existing path loss models. We also optimally place reflectors to maximize the worst-case signal coverage within the target indoor areas. Our extensive experimental evaluation results have shown OptRe to enhance signal strength for different types of wireless signals by almost 2x.
【Keywords】: Wireless communication; Wireless fidelity; Adaptation models; Conferences; Indoor environments; Fading channels; Propagation losses
【Paper Link】 【Pages】:1-9
【Authors】: Alireza Ameli Renani ; Jun Huang ; Guoliang Xing ; Abdol-Hossein Esfahanian
【Abstract】: The design trade-offs of transceiver hardware are crucial to the performance of wireless systems. In this paper, we present an in-depth study to characterize the surprisingly notable systemic impacts of low-pass filter (LPF) design, which is a small yet indispensable component used for shaping spectrum and rejecting interference. Using a bottom-up approach, we examine how signal-level distortions caused by the trade-off of LPF design propagate to the upper-layers of wireless communication, reshaping bit error patterns and degrading link performance of today's 802.11 systems. Moreover, we propose a novel algorithm that harnesses LPF defects for improving video streaming, which substantially enhances video quality in mobile environments.
【Keywords】: Distortion; IEEE 802.11 Standard; Distortion measurement; Wireless communication; Frequency measurement; Semiconductor device measurement; Hardware
【Paper Link】 【Pages】:1-9
【Authors】: Ganesh Chennimala Sankaran ; Krishna M. Sivalingam
【Abstract】: This paper deals with the efficient design of network switch/routers for an optical data center network. Each switch has multiple components such as ingress/egress interfaces, optical and/or electronic buffers, interconnection switching fabric and so on. There are several possible choices available for each of these components. This paper presents a systematic approach to designing the switch architecture using a combination of these component choices, while meeting specified design criteria. It requires formally defining the structure of a switch and enforcing semantics across components. This is formulated as a constraint optimization problem with formal language grammar guiding its search process. This problem formulation is used to identify the best-possible architecture for a hierarchical DCN. Two of the three solutions identified were new and were not reported in literature. These solutions were also validated experimentally.
【Keywords】: Optical switches; Servers; Computer architecture; Grammar; Formal languages
【Paper Link】 【Pages】:1-9
【Authors】: Su Jia ; Xin Jin ; Golnaz Ghasemiesfeh ; Jiaxin Ding ; Jie Gao
【Abstract】: Modern planetary-scale online services have massive data to transfer over the wide area network (WAN). Due to the tremendous cost of building WANs and the stringent timing requirement of distributed applications, it is critical for network operators to make efficient use of network resources to optimize data transfers. By leveraging software-defined networking (SDN) and reconfigurable optical devices, recent solutions design centralized systems to jointly control the network layer and the optical layer. While these solutions show it is promising to significantly reduce data transfer times by centralized cross-layer control, they do not have any theoretical guarantees on the proposed algorithms. This paper presents approximation algorithms and theoretical analysis for the online transfer scheduling problem over optical WANs. The goal of the scheduling problem is to minimize the makespan (the time to finish all transfers) or the total sum of completion times. We design and analyze various greedy, online scheduling algorithms that can achieve 3-competitive ratio for makespan, 2-competitive ratio for minimum sum completion time for jobs of unit size, and 3α-competitive ratio for jobs of arbitrary transfer size and each node having degree constraint d, where α = 1 when d = 1 and α = 1.86 when d ≥ 2. We also evaluated the performance of these algorithms and compared the performance with prior heuristics.
【Keywords】: Optical devices; Wide area networks; Optical fiber networks; Data transfer; Algorithm design and analysis; Schedules
【Paper Link】 【Pages】:1-9
【Authors】: Yu Nakayama ; Takuya Tsutsumi ; Kazuki Maruta ; Kaoru Sezaki
【Abstract】: Metropolitan areas witness significant fluctuations in mobile traffic due to patterns of human mobility. This fluctuation drastically deteriorates the efficiency and financial viability of conventional maximum-based network design. If networks are deployed to deal with the peak traffic rate at each site, their capacities are underutilized for most of time. To improve the efficiency of deploying base stations (BSs), this paper proposes a concept of an Autonomous Base Station with Optical Reflex Backhaul (ABSORB) architecture that can adapt to fluctuations in mobile traffic. In the ABSORB architecture, traffic at demand nodes is forwarded to and from an ABS with an arbitrary radio access technology (RAT). An ABS is connected to a gateway node through ORB, which consists of fiber optic networks. ABSs move to new locations following the demand movement, according to a relocation schedule that is periodically rearranged by an ABSORB controller. The network is flexibly reconstructed according to the demand distribution. The ABSORB architecture can be employed in various networks, and can coexist with traditional static architectures. It will drastically reduce the number of BSs, total deployment cost, and power consumption in comparison with the traditional design.
【Keywords】: Computer architecture; Mobile communication; Topology; Optical fiber communication; Network topology; Adaptation models; Ad hoc networks
【Paper Link】 【Pages】:1-9
【Authors】: Steven Gay ; Renaud Hartert ; Stefano Vissicchio
【Abstract】: In this paper, we study how to perform traffic engineering at an extremely-small time scale with segment routing, addressing a critical need for modern wide area networks. Prior work has shown that segment routing enables to better engineer traffic, thanks to its ability to program detours in forwarding paths, at scale. Two main approaches have been explored for traffic engineering with segment routing, respectively based on integer linear programming and constraint programming. However, no previous work deeply investigated how quickly those approaches can react to unexpected traffic changes and failures. We highlight limitations of existing algorithms, both in terms of required execution time and amount of path changes to be applied. Thus, we propose a new approach, based on local search and focused on the quick re-arrangement of (few) forwarding paths. We describe heuristics for sub-second recomputation of segment-routing paths that comply with requirements on the maximum link load (e.g., for congestion avoidance). Our heuristics enable a prompt answer to sudden criticalities affecting network services and business agreements. Through extensive simulations, we indeed experimentally show that our proposal significantly outperforms previous algorithms in the context of time-constrained optimization, supporting radical traffic changes in few tens of milliseconds for realistic networks.
【Keywords】: Routing; Optimization; Routing protocols; Computational modeling; Conferences; Proposals; Heuristic algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Huanle Xu ; Gustavo de Veciana ; Wing Cheong Lau
【Abstract】: The completion times of jobs in a computing cluster may be influenced by a variety of factors including job size and machine processing variability. In this paper, we explore online resource allocation policies which combine size-dependent scheduling with redundant execution and opportunistic checkpointing to minimize the overall job flowtime. We introduce a simplified model for the job service capacity of a computing cluster while leveraging redundant execution/checkpointing. In this setting, we propose two resource allocation algorithms, SRPT+R and LAPS+R(β) subject to checkpointing overhead not exceeding the number of jobs which are processed. We provide new theoretical performance bounds for these algorithms: SRPT+R is shown to be O(1/ϵ) competitive under (1 + ϵ)-speed resource augmentation, while LAPS+R(β) is shown to be O(1/βϵ) competitive under (2+ 2β + 2ϵ)-speed resource augmentation.
【Keywords】: Job Scheduling; Redundancy; Optimization; Competitive Analysis; Dual-Fitting
【Paper Link】 【Pages】:1-9
【Authors】: Yipei Niu ; Fangming Liu ; Xincai Fei ; Bo Li
【Abstract】: Flash deal applications, which offer significant benefits (e.g., discount) to subscribers within a short period of time, are becoming increasingly prevalent. Motivated by such transient profit, flash crowds of subscribers request services simultaneously. Considering the unique business logic, a hybrid cloud with soft guarantee, i.e., bounding the response time of delay-tolerant requests, has great potential to handle flash crowds. In this paper, to cost-effectively withstand flash crowds with soft guarantee, we propose a solution that makes smart decisions on scheduling requests in the hybrid cloud and adjusting the capacity of the public cloud. In respect of scheduling requests, we apply Sequential Quadratic Programming (SQP) to achieve soft guarantee. Furthermore, for adjusting capacity, we design an online algorithm to tune the scale of the public cloud towards jointly minimizing cost and response time, yet without a priori knowledge of request arrival rate. We prove that the online algorithm can obtain a competitive ratio of 1-6ε against the optimal solution, where ε can be tuned close to 0. By conducting extensive trace-driven experiments in a website prototype deployed on OpenStack Mitaka and Amazon Web Service, our solution reduces response time by 15% compared with previous work under given budget.
【Keywords】: Cloud computing; Time factors; Algorithm design and analysis; Degradation; Outsourcing; Computational modeling; Web servers
【Paper Link】 【Pages】:1-9
【Authors】: Robert Birke ; Juan F. Pérez ; Zhan Qiu ; Mathias Björkqvist ; Lydia Y. Chen
【Abstract】: Replicating redundant requests has been shown to be an effective mechanism to defend application performance from high capacity variability - the common pitfall in the cloud. While the prior art centers on single-tier systems, it still remains an open question how to design replication strategies for distributed multi-tier systems, where interference from neighboring workloads is entangled with complex tier interdependency. In this paper, we design a first of its kind PArtial REplication system, sPARE, that replicates and dispatches read-only workloads for multi-tier web applications, determining replication factors per tier. The two key components of sPARE are (i) the variability-aware replicator that coordinates the replication levels on all tiers via an iterative searching algorithm, and (ii) the replication-aware arbiter that uses a novel token-based arbitration algorithm (TAD) to dispatch requests in each tier. We evaluate sPARE on web serving and web searching applications, i.e., MediaWiki and Solr, deployed on our private cloud testbed. Our results based on various interference patterns and traffic loads show that sPARE is able to improve the tail latency of MediaWiki and Solr by a factor of almost 2.7x and 2.9x, respectively.
【Keywords】: Servers; Interference; Cloud computing; Protocols; Redundancy; Dispatching; Measurement
【Paper Link】 【Pages】:1-9
【Authors】: Zhe Huang ; S. Matthew Weinberg ; Liang Zheng ; Carlee Joe-Wong ; Mung Chiang
【Abstract】: A cloud computing cluster equipped with a deadline-aware job scheduler faces fairness and efficiency challenges when greedy users falsely advertise the urgency of their jobs. Penalizing such untruthfulness without demotivating users from using the cloud service calls for advanced mechanism design techniques that work together with deadline-aware job scheduling. We propose a Bayesian incentive compatible pricing mechanism based on matching by replica-surrogate valuation functions. User valuations can be discovered by the mechanism, even when the users themselves do not fully understand their own valuations. Furthermore, users who are charged a Bayesian incentive compatible price have no reason to lie about the urgency of their jobs. The proposed mechanism achieves multiple desired truthful properties such as Bayesian incentive compatibility and ex-post individual rationality. We implement the proposed pricing mechanism. Through experiments in a Hadoop cluster with real-world datasets, we show that our prototype is capable of suppressing untruthful behavior from users.
【Keywords】: Cost accounting; Pricing; Resource management; Quality of service; Cloud computing; Bayes methods; Processor scheduling
【Paper Link】 【Pages】:1-9
【Authors】: Xu Zheng ; Zhipeng Cai ; Jianzhong Li ; Hong Gao
【Abstract】: Local business service systems (LBSS), such as Yelp and Dianping, play an essential role in making decisions like choosing a restaurant for our daily life. These systems heavily rely on individuals' voluntarily submitted reviews to build the reputation for nearby businesses. Unfortunately, the reviews expose users' private information such as visited places to the public and adversaries. Even worse, such location information is always public as it is the basic information of businesses, and adversaries could be anyone ranging from advertisement spammer to physical stalker. This paper formalizes the privacy preserving problem in local business service systems and propose a novel location privacy preserving framework. The framework can preserve users' location privacy in arbitrary local area and can maintain a good utility for both the system and every user. We evaluate our framework thoroughly towards real-world data traces. The results validate that the framework can achieve a good performance.
【Keywords】: Privacy; Business; Publishing; Conferences; Computer science; Electronic mail; Mobile radio mobility management
【Paper Link】 【Pages】:1-9
【Authors】: Shaowei Wang ; Yiwen Nie ; Pengzhan Wang ; Hongli Xu ; Wei Yang ; Liusheng Huang
【Abstract】: The categorical data that have natural ordering between categories are termed ordinal data, which are pervasive in numerous areas, including discrete sensor readings, metering data or preference options. Though aggregating such ordinal data from the population is facilitating plenty of crowdsourcing applications, contributing such data is privacy risky and may reveal sensitive information (e.g. locations, identities) about individuals. This work studies ordinal data aggregation for distribution estimation meanwhile locally preserving individuals' data privacy (such as on their mobile devices). Under ε-geo-indistinguishable constraints, which capture intrinsic dissimilarity between ordinal categories in the framework of differential privacy, we provide an efficient and effective locally private mechanism: Subset Exponential Mechanism (SEM) for ordinal data distribution estimation. The mechanism randomly responds with a fixed-size subset of the categories with calibrated probability assignment. Specially for uniform ordinal data, we propose a circling technique to symmetrically randomizing categories and estimating frequencies of categories, hence the computational/space costs and estimation performance of SEM are further optimized. Besides contributing theoretical error bounds of SEM, we also evaluate the mechanism on extensive scenarios, the evaluation results show that SEM reduces distribution estimation error on average by exp(ϵ/2) factor over existing private mechanisms.
【Keywords】: Data privacy; Estimation; Privacy; Data models; Crowdsourcing; Data aggregation; Databases
【Paper Link】 【Pages】:1-9
【Authors】: Hai Liu ; Xinghua Li ; Hui Li ; Jianfeng Ma ; XinDi Ma
【Abstract】: Since the dummy-based method can provide precise query results without any requirement for a third party or key sharing, it has been widely used to protect the user's location privacy in location-based services. However, the neighboring location sets submitted in consecutive requests always include a close spatiotemporal correlation, which enables the adversary to identify some dummies. Therefore, the existing dummy-based schemes cannot protect the user's location privacy completely. To solve this problem, based on the dummies generated by the existing schemes, this paper filters out the dummies that can be identified by taking into account of the spatiotemporal correlation from three aspects, namely time reachability, direction similarity and in-degree/out-degree. In this way, the rest dummies can satisfy the user's personalized privacy protection requirement. Security analysis shows that the proposed scheme successfully perturbs the spatiotemporal correlation between neighboring location sets, therefore, it is infeasible for the adversary to distinguish the user's real location from the dummies. Furthermore, extensive experiments indicate that the proposal is able to protect the user's location privacy effectively and efficiently.
【Keywords】: Privacy; Spatiotemporal phenomena; Correlation; Mobile radio mobility management; Conferences; Computer security
【Paper Link】 【Pages】:1-9
【Authors】: Marco Gramaglia ; Marco Fiore ; Alberto Tarable ; Albert Banchs
【Abstract】: Mobile network operators can track subscribers via passive or active monitoring of device locations. The recorded trajectories offer an unprecedented outlook on the activities of large user populations, which enables developing new networking solutions and services, and scaling up studies across research disciplines. Yet, the disclosure of individual trajectories raises significant privacy concerns: thus, these data are often protected by restrictive non-disclosure agreements that limit their availability and impede potential usages. In this paper, we contribute to the development of technical solutions to the problem of privacy-preserving publishing of spatiotemporal trajectories of mobile subscribers. We propose an algorithm that generalizes the data so that they satisfy-anonymity, an original privacy criterion that thwarts attacks on trajectories. Evaluations with real-world datasets demonstrate that our algorithm attains its objective while retaining a substantial level of accuracy in the data. Our work is a step forward in the direction of open, privacy-preserving datasets of spatiotemporal trajectories.
【Keywords】: Trajectory; Spatiotemporal phenomena; Privacy; Mobile communication; Data privacy; Databases; Couplings
【Paper Link】 【Pages】:1-9
【Authors】: Abhishek Sinha ; Eytan Modiano
【Abstract】: We consider the problem of throughput-optimal packet dissemination, in the presence of an arbitrary mix of unicast, broadcast, multicast and anycast traffic, in a general wireless network. We propose an online dynamic policy, called Universal Max-Weight (UMW), which solves the above problem efficiently. To the best of our knowledge, UMW is the first throughput-optimal algorithm of such versatility in the context of generalized network flow problems. Conceptually, the UMW policy is derived by relaxing the precedence constraints associated with multi-hop routing, and then solving a min-cost routing and max-weight scheduling problem on a virtual network of queues. When specialized to the unicast setting, the UMW policy yields a throughput-optimal cycle-free routing and link scheduling policy. This is in contrast to the well-known throughput-optimal BackPressure (BP) policy which allows for packet cycling, resulting in excessive delay. Extensive simulation results show that the proposed policy incurs a substantially lower delay as compared to the BP policy. The proof of throughput-optimality of the UMW policy combines techniques from stochastic Lyapunov theory with a sample path argument from adversarial queueing theory and may be of independent theoretical interest.
【Keywords】: Routing; Unicast; Delays; Wireless networks; Heuristic algorithms; Spread spectrum communication; Throughput
【Paper Link】 【Pages】:1-9
【Authors】: Kai Lampka ; Steffen Bondorf ; Jens B. Schmitt ; Nan Guan ; Wang Yi
【Abstract】: Real-time Calculus (RTC) is a non-stochastic queuing theory to the worst-case performance analysis of distributed real-time systems. Workload as well as resources are modelled as piece-wise linear, pseudo-periodic curves and the system under investigation is modelled as a sequence of algebraic operations over these curves. The memory footprint of computed curves increases exponentially with the sequence of operations and RTC may become computationally infeasible fast. Recently, Finitary RTC has been proposed to counteract this problem. Finitary RTC restricts curves to finite input domains and thereby counteracts the memory demand explosion seen with pseudo periodic curves of common RTC implementations. However, the proof to the correctness of Finitary RTC specifically exploits the operational semantic of the greed processing component (GPC) model and is tied to the maximum busy window size. This is an inherent limitation, which prevents a straight-forward generalization. In this paper, we provide a generalized Finitary RTC that abstracts from the operational semantic of a specific component model and reduces the finite input domains of curves even further. The novel approach allows for faster computations and the extension of the Finitary RTC idea to a much wider range of RTC models.
【Keywords】: Mathematical model; Computational modeling; Real-time systems; Analytical models; Delays; Semantics; Calculus
【Paper Link】 【Pages】:1-9
【Authors】: Peng-Jun Wan ; Huaqiang Yuan ; Xiaohua Jia ; Jiliang Wang ; Zhu Wang
【Abstract】: Consider a set of point-to-point communication requests in a multi-channel multihop wireless network, each of which is associated with a traffic demand of at most one unit of transmission time, and a weight representing the utility if its demand is fully met. A subset of requests is said to be schedulable without spectral splitting if they can be scheduled within one unit of time subject to the constraint each request is assigned with a unique channel throughout its transmission. This paper develops efficient and provably good approximation algorithms for finding a maximum-weighted subset of communication requests schedulable without spectral splitting.
【Keywords】: Schedules; Approximation algorithms; Channel allocation; Interference; Computer science; Receivers; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Subhashini Krishnasamy ; P. T. Akhil ; Ari Arapostathis ; Sanjay Shakkottai ; Rajesh Sundaresan
【Abstract】: In small-cell wireless networks where users are connected to multiple base stations (BSs), it is often advantageous to opportunistically switch off a subset of BSs to minimize energy costs. We consider two types of energy cost: (i) the cost of maintaining a BS in the active state, and (ii) the cost of switching a BS from the active state to inactive state. The problem is to operate the network at the lowest possible energy cost (sum of activation and switching costs) subject to queue stability. In this setting, the traditional approach - a Max-Weight algorithm along with a Lyapunov-based stability argument - does not suffice to show queue stability, essentially due to the temporal co-evolution between channel scheduling and the BS activation decisions induced by the switching cost. Instead, we develop a learning and BS activation algorithm with slow temporal dynamics, and a Max-Weight based channel scheduler that has fast temporal dynamics. We show using convergence of time-inhomogeneous Markov chains, that the co-evolving dynamics of learning, BS activation and queue lengths lead to near optimal average energy costs along with queue stability.
【Keywords】: wireless scheduling; base-station activation; energy minimization
【Paper Link】 【Pages】:1-9
【Authors】: Yuxiao Hou ; Yuanqing Zheng
【Abstract】: Tree-based RFID identification adopts a binary-tree structure to collect IDs of an unknown set. Tag IDs locate at the leaf nodes and the reader queries through intermediate tree nodes and converges to these IDs using feedbacks from tag responses. Existing works cannot function well under random ID distribution as they ignore the distribution information hidden in the physical-layer signal of colliding tags. Different from them, we introduce PHY-Tree, a novel tree-based scheme that collects two types of distribution information from every encountered colliding signal. First, we detect if all colliding tags send the same bit content at each bit index by looking into inherent temporal features of the tag modulation schemes. If such resonant states are detected, either left or right branch of a certain subtree can be trimmed horizontally. Second, we estimate the number of colliding tags in a slot by computing a related metric defined over the signal's constellation map, based on which nodes in the same layers of a certain subtree can be skipped vertically. Evaluations from both experiments and simulations demonstrate that PHY-Tree outperforms state-of-the-art schemes by at least 1.79×.
【Keywords】: Indexes; Physical layer; Radiofrequency identification; Encoding; Conferences; Feature extraction; Modulation
【Paper Link】 【Pages】:1-9
【Authors】: Jia Liu ; Feng Zhu ; Yanyan Wang ; Xia Wang ; Qing-feng Pan ; Lijun Chen
【Abstract】: Shelf scanning is one of the most important processes for inventory management in a library. It helps the librarians and library users discover the miss-shelved books and pinpoint where they are, improving the quality of service. By traditional means, however, manually checking each bookshelf suffers from extremely intensive labor and long scanning delay. Although some existing RFID-enabled approaches have been proposed, they suffer from either high-cost infrastructure or complicated system deployment, forming a great barrier to commercial adoption. In light of this, we in this paper propose a smart system called RF-Scanner that can perform the shelf scanning automatically by combining the robot technology and the RFID technology. The former is used for replacing the librarians and liberating them from intensively manual labor. The later is installed on the robot and moves with the robot to scan the on-the-shelf books. We formulate two important issues concerned by librarians, the book localization and the lying-down book detection, and give the sophisticated solutions to them. Besides, we implement RF-Scanner and put it into practical use in our school library. Long-term experiments and studies show that RF-Scanner provides fine-grained book localization with a mean error of just 1.3 cm and accurate detection accuracy of lying-down books with a mean error of 6%.
【Keywords】: Libraries; Radiofrequency identification; Robot kinematics; Radio frequency; Manuals; Systems architecture
【Paper Link】 【Pages】:1-9
【Authors】: Min Chen ; Jia Liu ; Shigang Chen ; Yan Qiao ; Yuanqing Zheng
【Abstract】: RFID technologies are making their way into numerous applications, including inventory management, supply chain, product tracking, transportation, logistics, etc. One important application is to automatically detect anomalies in RFID systems, such as missing tags, unknown tags, or cloned tags due to theft, management error, or targeted attacks. Existing solutions are all designed to detect a certain type of RFID anomalies, but lack a general functionality for detecting different types of anomalies. This paper attempts to propose a general framework for anomaly detection in RFID systems, thereby reducing the complexity for readers and tags to implement different anomaly-detection protocols. We introduce a new concept of differential Bloom filter (DBF), which turns physical-layer signal data into a segmented Bloom filter that encodes the IDs of abnormal tags. As a case study, we propose a protocol that builds DBF for identifying all missing tags in an efficient way. We implement a prototype for missing-tag identification using USRP and WISP tags to verify the effectiveness our protocol, and use large-scale simulations for performance evaluation. The results show that our solution can significantly improve time efficiency, when comparing with the best existing work.
【Keywords】: Radiofrequency identification; Anomaly detection; Nickel; Protocols; Wireless communication; Aggregates; Databases
【Paper Link】 【Pages】:1-9
【Authors】: Henko Aantjes ; Amjad Yousef Majid ; Przemyslaw Pawelczak ; Jethro Tan ; Aaron N. Parks ; Joshua R. Smith
【Abstract】: We present Stork - an extension of the EPC C1G2 protocol allowing streaming of data to multiple Computational Radio Frequency IDentification tags (CRFIDs) simultaneously at up to 20 times faster than the prior state of the art. Stork introduces downstream attributes never before seen in (C)RFIDs: (i) fast feedback for CRFID downstream verification based on the internal EPC C1G2 memory check command - which we analytically and experimentally show to be the best possible downstream verification process based on EPC C1G2; (ii) ability to perform multi-CRFID transfer - which in our experiments speeds up downstream by more than two times compared to sequential transmission; and (iii) the use of compressed data streams - which improves firmware reprogramming times by up to 10% at large reader-to-CRFID distances.
【Keywords】: Protocols; Radiofrequency identification; Robustness; Software; Payloads
【Paper Link】 【Pages】:1-9
【Authors】: Zhe Chen ; Xu Zhang ; Sulei Wang ; Yuedong Xu ; Jie Xiong ; Xin Wang
【Abstract】: Large-scale MU-MIMO is a promising technology to scale network capacity and the capacity gain grows linearly with the numbers of antennas and users in theory. However, its practical deployment faces three critical challenges in the state-of-the-art WLANs: i) the demand of a large number of expensive RF chains; ii) the linear growth of feedback overheads with the number of antennas; iii) the lack of scalable user selection scheme for a large user population. In this paper, we design BUSH, a large-scale MU-MIMO prototype that performs scalable beam user selection with hybrid beamforming for phased-array antennas in legacy WLANs. The architecture of BUSH consists of three components. Firstly, a low complexity algorithm assigns each pair of RF chain and analog beam to the users to effectively reduce channel correlation and cross-talk interference without instantaneous CSI feedbacks. Secondly, as a prerequisite of user selection, BUSH presents a low-overhead probing scheme in multi-carrier WLANs, and designs a highly accurate blind Power Azimuth Spectrum (PAS) estimation algorithm using a single RF chain. Thirdly, the phased-array antennas use analog beamforming to steer spatial beams toward each selected downlink user, and the finite number of RF chains use beamforming to further mitigate the interference among users. We implement BUSH on the WARPv3 boards and evaluate its performance in more than 30 indoor scenarios. The experimental results show that in terms of total throughput BUSH outperforms the legacy 802.11ac by 2.08×, and an alternative benchmark system by 1.22× on average.
【Keywords】: Array signal processing; Radio frequency; Antennas; Throughput; Interference; Estimation; MIMO
【Paper Link】 【Pages】:1-9
【Authors】: Meenupriya Swaminathan ; Anna Vizziello ; Davy Duong ; Pietro Savazzi ; Kaushik R. Chowdhury
【Abstract】: Implants are poised to revolutionize personalized healthcare by monitoring and actuating physiological functions. Such implants operate under challenging constraints of limited battery energy, heterogeneous tissue-dependent channel conditions and human-safety regulations. To address these issues, we propose a new cross-layer protocol for galvanic coupled implants wherein weak electrical currents are used in place of classical radio frequency (RF) links. As the first step, we devise a method that allows multiple implants to communicate individual sensed data to each other through CDMA code assignments, but delegates the computational burden of decoding only to the on-body surface relays. Then, we devise a distributed beamforming approach that allows coordinated transmissions from the implants to the relays by considering the specific tissue path chosen and tissue heating-related safety constraints. Our contributions are two fold: First, we devise a collision-free protocol that prevents undue interference at neighboring implants, especially for multiple deployments. Second, this is the first application of near-field distributed beamforming in human tissue. Results reveal significant improvement in the network lifetime for implants of up to 79% compared to the galvanic coupled links without beamforming.
【Keywords】: Implants; Relays; Array signal processing; Muscles; Multiaccess communication; Transmitters; Sensors
【Paper Link】 【Pages】:1-9
【Authors】: Abdul Salam ; Mehmet C. Vuran
【Abstract】: Current wireless underground (UG) communication techniques are limited by their achievable distance. In this paper, a novel framework for underground beamforming using adaptive antenna arrays is presented to extend communication distances for practical applications. Based on the analysis of propagation in wireless underground channel, a theoretical model is developed which uses soil moisture information to improve wireless underground communications performance. Array element in soil is analyzed empirically and impacts of soil type and soil moisture on return loss (RL) and resonant frequency are investigated. Accordingly, beam patterns are analyzed to communicate with underground and above ground devices. Depending on the incident angle, refraction from soil-air interface has adverse effects in the UG communications. It is shown that beam steering improves UG communications by providing a high-gain lateral wave. To this end, the angle, which enhances lateral wave, is shown to be a function of dielectric properties of the soil, soil moisture, and soil texture. Evaluations show that this critical angle varies from 0° to 16° and decreases with soil moisture. Accordingly, a soil moisture adaptive beamforming (SMABF) algorithm is developed for planar array structures and evaluated with different optimization approaches to improve UG communication performance.
【Keywords】: Soil moisture; Antenna arrays; Array signal processing; Resonant frequency; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Joan Palacios ; Danilo De Donno ; Joerg Widmer
【Abstract】: In order to cope with the severe path loss, millimeter-wave (mm-wave) systems exploit highly directional communication. As a consequence, even a slight beam mis-alignment between two communicating devices (for example, due to mobility) can generate a significant signal drop. This leads to frequent invocations of time-consuming mechanisms for beam re-alignment, which deteriorate system performance. In this paper, we propose smart beam training and tracking strategies for fast mm-wave link establishment and maintenance under node mobility. We leverage the ability of hybrid analog-digital transceivers to collect channel information from multiple spatial directions simultaneously and formulate a probabilistic optimization problem to model the temporal evolution of the mm-wave channel under mobility. In addition, we present for the first time a beam tracking algorithm that extracts information needed to update the steering directions directly from data packets, without the need for spatial scanning during the ongoing data transmission. Simulation results, obtained by a custom simulator based on ray tracing, demonstrate the ability of our beam training/tracking strategies to keep the communication rate only 10% below the optimal bound. Compared to the state of the art, our approach provides a 40% to 150% rate increase, yet requires lower complexity hardware.
【Keywords】: Training; Radio frequency; Transceivers; Maintenance engineering; Heuristic algorithms; Probabilistic logic; Array signal processing
【Paper Link】 【Pages】:1-9
【Authors】: Hongli Xu ; Zhuolong Yu ; Chen Qian ; Xiang-Yang Li ; Zichun Liu
【Abstract】: In a software defined network (SDN), the control plane needs to frequently collect flow statistics measured at the data plane switches for different applications, such as traffic engineering, flow re-routing, and attack detection. However, existing solutions for flow statistics collection may result in large bandwidth cost in the control channel and long processing delay on switches, which significantly interfere with the basic functions such as packet forwarding and route update. To address this challenge, we propose a Cost-Optimized Flow Statistics Collection (CO-FSC) scheme using wildcard-based requests. We prove that the CO-FSC problem is NP-Hard and present a rounding-based algorithm with an approximation factor f, where f is the maximum number of switches visited by each flow. Moreover, our CO-FSC problem is extended to the general case, in which only a part of flows in a network need to be collected. The extensive simulation results show that the proposed algorithms can reduce the bandwidth overhead by over 41% and switch processing delay by over 45% compared with the existing solutions.
【Keywords】: Software Defined Networks; Flow Statistics Collection; Cost; Wildcard; Approximation
【Paper Link】 【Pages】:1-9
【Authors】: Wenrui Ma ; Oscar Sandoval ; Jonathan Beltran ; Deng Pan ; Niki Pissinou
【Abstract】: Network function virtualization enables flexible implementation of network functions, or middleboxes, as virtual machines running on standard servers. However, the flexibility also creates a challenge for efficiently placing such middleboxes, due to the availability of multiple hosting servers, capability of middleboxes to change traffic volumes, and dependency between middleboxes. In this paper, we address the optimal placement challenge of NFV middleboxes, and propose solutions for middleboxes of different traffic changing effects and with different dependency relations. First, we formulate the Traffic Aware Placement of Interdependent Middleboxes problem as a graph optimization problem. When the flow path is predetermined, we design optimal algorithms to place a non-ordered or totally-ordered middlebox set, and propose an efficient heuristic for the general scenario of a partially-ordered middlebox set after proving its NP-hardness. When the flow path is not predetermined, we show that the problem is NP-hard even for a non-ordered middlebox set, and propose a traffic and space aware routing heuristic. We have evaluated the proposed algorithms using large scale simulations and prototype experiments, and present extensive evaluation results to demonstrate the effectiveness of our design.
【Keywords】: NFV; SDN; middlebox
【Paper Link】 【Pages】:1-9
【Authors】: Peng Zhang
【Abstract】: Software defined networks (SDNs) reshape the ossified network architectures, by introducing centralized and programmable network control. Despite the huge benefits, SDNs also open doors to what we call rule modification attack, an attack largely overlooked by the community. In such an attack, the adversary can modify rules by exploiting implementation vulnerabilities of switch OSes and control channels. As a result, packets may deviate from their original paths, thereby violating network policies. To defend against rule modification attack, this paper introduces a new security primitive named rule enforcement verification (REV). REV allows a controller to check whether switches have enforced the rules installed by it, using message authentication code (MAC). Since using standard MACs will incur heavy switch-to-controller traffic, this paper proposes a new compressive MAC, which allows switches to compress MACs before reporting to the controller. Experiments show that REV based on compressive MAC can achieve a 97% reduction in switch-to-controller traffic, and a Sx increase in verification throughput.
【Keywords】: Software defined networks; Rule modification attack; verification; Compressive MAC
【Paper Link】 【Pages】:1-9
【Authors】: RhongHo Jang ; DongGyu Cho ; Youngtae Noh ; DaeHun Nyang
【Abstract】: In this work, we propose an SDN-based WLAN monitoring and management framework called RFlow+ to address WiFi service dissatisfaction caused by the limited view (lack of scalability) of network traffic monitoring and absence of intelligent and timely network treatments. Existing solutions (e.g., OpenFlow and sFlow) have limited view, no generic flow description, and poor trade-off between measurement accuracy and network overhead depending on the selection of the sampling rate. To resolve these issues, we devise a two-level counting mechanism, namely a distributed local counter (on-site and real-time) and central collector (a summation of local counters). With this, we proposed a highly scalable monitoring and management framework to handle immediate actions based on short-term (e.g., 50 ms) monitoring and eventual actions based on long-term (e.g., 1 month) monitoring. The former uses the local view of each access point (AP), and the latter uses the global view of the collector. Experimental results verify that RFlow+ can achieve high accuracy (less than 5% standard error for short-term and less than 1% for long-term) and fast detection of flows of interest (within 23 ms) with manageable network overhead. We prove the practicality of RFlow+ by showing the effectiveness of a MAC flooding attacker quarantine in a real-world testbed.
【Keywords】: computer network management; computerised monitoring; IP networks; software defined networking; telecommunication security; telecommunication traffic; wireless LAN
【Paper Link】 【Pages】:1-9
【Authors】: Parimal Parag ; Archana Bura ; Jean-François Chamberland
【Abstract】: Modern communication and computation systems consist of large networks of unreliable nodes. Yet, it is well known that such systems can provide aggregate reliability via information redundancy, duplicating paths, or replicating computations. While redundancy may increase the load on a system, it can also lead to major performance improvements through the judicious management of additional system resources. Two important examples of this abstract paradigm are content access from multiple caches in content delivery networks and master/slave computations on compute clusters. Many recent articles in the area have proposed bounds on the latency performance of redundant systems, characterizing the latency-redundancy tradeoff under specific load profiles. Following a similar line of research, this article introduces new analytical bounds and approximation techniques for the latency-redundancy tradeoff for a range of system loads and two popular redundancy schemes. The proposed framework allows for approximating the equilibrium latency distribution, from which various metrics can be derived including mean, variance, and the tail decay of stationary distributions.
【Keywords】: Data storage; forward error correction; content delivery networks; distributed storage systems; Markov processes; queueing analysis; equilibrium distribution; waiting time
【Paper Link】 【Pages】:1-9
【Authors】: Vaneet Aggarwal ; Jingxian Fan ; Tian Lan
【Abstract】: Distributed storage systems are known to be susceptible to long tails in response time. It has been shown that in modern online applications such as Bing, Facebook, and Amazon, the long tail of latency is of particular concern, with 99.9th percentile response times being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique in distributed storage to achieve high data reliability while attaining space efficiency, taming tail latency remains an open problem due to the lack of mathematical models for analyzing such erasure-coded storage systems. In this paper, we quantify tail latency in distributed storage systems that employ erasure coding. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Simulation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload.
【Keywords】: Optimization; Probabilistic logic; Servers; Upper bound; Encoding; Queueing analysis; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Shuzhan Wei ; Yongkun Li ; Yinlong Xu ; Si Wu
【Abstract】: Nowadays many clustered file systems adopt asynchronous encoding which transforms replicated data into erasure coding to maintain data availability with bounded storage overhead. Existing implementations of asynchronous encoding construct coding stripes with logically sequential data blocks, which suffers from heavy cross-rack traffic and necessitates data block redistribution. Recent work [12] solves this problem by carefully distributing replicated data blocks among racks at the time when they are being written, but it is not applicable to the cases when existing systems have different data layouts or the data layout changes. In this paper, we propose Dynamic Stripe Construction (DSC) to transform N-way replication to erasure coding. DSC does not induce to any cross-rack traffic for encoding, and it does not require data block redistribution after encoding. Besides, DSC is general enough to be applied to any existing CFSes with various erasure codes, and it can also be deployed on a distributed file system in a hot-plugging-in manner. To validate the effectiveness of DSC, we implement it on HDFS. Through extensive testbed experiments in a real storage cluster, we show that DSC can significantly increase the encoding throughput and reduce the foreground user response time over the traditional approach.
【Keywords】: Encoding; Fault tolerance; Fault tolerant systems; Distributed databases; Ear; Layout
【Paper Link】 【Pages】:1-9
【Authors】: Xuefeng Liu ; Wenhai Sun ; Wenjing Lou ; Qingqi Pei ; Yuqing Zhang
【Abstract】: In this paper, we investigate the problem of integrity auditing for cloud deduplication storage. Specifically, in addition to the outsourced data confidentiality, we also aim to ensure the integrity of the deduplicated cloud storage. With the existing works based on Provable Data Possession (PDP)/Proof of Retrievability (PoR), we are either required to rely on a fully trusted proxy server or inevitably sacrifice the privacy and efficiency. In contrast, we present a novel message-locked integrity auditing scheme without an additional proxy server, which is applicable to both file-level and chunk-level deduplication systems. In particular, our scheme is storage efficient in the sense that apart from eliminating the ciphertext redundancy, we also enable the integrity tag deduplication by a message-derived signing key, which merely incurs minimal client-side computation overhead. Besides, we can still publicly perform the integrity check over any client's cloud storage by incorporating the proxy re-signature technique. We show that the proposed scheme will not disclose the data ownership information and is provably secure under the Computational Diffie-Hellman (CDH) assumption in the random oracle model. Finally, the performance evaluation demonstrates its effectiveness and efficiency.
【Keywords】: Cloud computing; Servers; Encryption; Public key; Protocols; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Michael Dinitz ; Jeremy T. Fineman ; Seth Gilbert ; Calvin Newport
【Abstract】: Load balancing is an important activity in distributed systems. At a high-level of abstraction, this problem assumes processes in the system begin with a potentially uneven assignment of “work” which they must then attempt to spread evenly. There are many different approaches to solving this problem. In this paper, we focus on local load balancing-an approach in which work is balanced in an iterative and distributed manner by having processes exchange work in each round with neighbors in an underlying communication network. The goal with local load balancing is to prove that these local exchanges will lead over time to a global balance. We describe and analyze a new local load balancing strategy called max neighbor, and prove a bound on the number of rounds required for it to obtain a parameterized level of balance, with high probability, in a general dynamic network topology. We then prove this analysis tight (within logarithmic factors) by describing a network and initial work distribution for which max neighbor matches its upper bound, and then build on this to prove that no load balancing algorithm in which every node exchanges work with at most one partner per round can converge asymptotically faster than max neighbor.
【Keywords】: Load management; Convergence; Heuristic algorithms; Network topology; Communication networks; Conferences; Hypercubes
【Paper Link】 【Pages】:1-9
【Authors】: Hongli Xu ; He Huang ; Shigang Chen ; Gongming Zhao
【Abstract】: Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which however face scalability challenge due to (1) limited TCAM and on-die memory for storing the forwarding table and (2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching design, which integrates traditional switching and SDN switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. Numerical evaluation demonstrates the superior performance of hybrid switching when comparing with the state-of-the-art SDN design.
【Keywords】: Switches; Routing; Scalability; Ports (Computers); Centralized control; Aggregates
【Paper Link】 【Pages】:1-9
【Authors】: Syed Mohammad Irteza ; Hafiz Mohsin Bashir ; Talal Anwar ; Ihsan Ayyub Qazi ; Fahad Rafique Dogar
【Abstract】: Datacenter networks are often structured as multi-rooted trees to provide high bisection bandwidth at low cost. To utilize the available bisection bandwidth, an efficient load balancing algorithm is required. Packet Spraying is known to perform well in symmetric topologies as it provides per-packet load balancing over equal cost paths. However, packet spraying performs poorly in asymmetric topologies. In this paper we ask, “How can we make packet spraying effective in asymmetric topologies while retaining its simplicity?” Towards this end, we propose SAPS, “Symmetric Adaptive Packet Spraying”, an SDN-based scheme that uses packet spraying over symmetric virtual topologies. SAPS is based on the key insight that if we provide each flow with a symmetric view of the network fabric, then packet spraying can produce near-optimal performance. We evaluate SAPS using simulations and testbed experiments. Our results indicate that SAPS performs well for a variety of application workloads and asymmetric network scenarios.
【Keywords】: Topology; Spraying; Load management; Network topology; Switches; Bandwidth; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Stefanie Roos ; Martin Byrenheid ; Clemens Deusser ; Thorsten Strufe
【Abstract】: Balancing the load in content addressing schemes for route-restricted networks represents a challenge with a wide range of applications. Solutions based on greedy embeddings maintain minimal state information and enable efficient routing, but any such solutions currently result in either imbalanced content addressing, overloading individual nodes, or are unable to efficiently account for network dynamics. In this work, we propose a greedy embedding in combination with a content addressing scheme that provides balanced content addressing while at the same time enabling efficient stabilization in the presence of network dynamics. We point out the tradeoff between stabilization complexity and maximal permitted imbalance when deriving upper bounds on both metrics for two variants of the proposed algorithms. Furthermore, we substantiate these bounds through a simulation study based on both real-world and synthetic data.
【Keywords】: Routing; Topology; Heuristic algorithms; Content addressable storage; Complexity theory; Conferences; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Taeho Jung ; Xiang-Yang Li ; Wenchao Huang ; Jianwei Qian ; Linlin Chen ; Junze Han ; Jiahui Hou ; Cheng Su
【Abstract】: We propose AccountTrade, a set of accountable protocols, for big data trading among dishonest consumers. To secure the big data trading environment, our protocols achieve book-keeping ability and accountability against dishonest consumers who may misbehave throughout the dataset transactions. Specifically, we study the responsibilities of the consumers in the dataset trading and design AccountTrade to achieve accountability against the dishonest consumers who may try to deviate from their responsibilities. Specifically, we propose uniqueness index, a new rigorous measurement of the data uniqueness, as well as several accountable trading protocols to enable data brokers to blame the dishonest consumer when misbehavior is detected. We formally define, prove, and evaluate the accountability of our protocols by an automatic verification tool as well as extensive evaluation in real-world datasets. Our evaluation shows that AccountTrade incurs negligible constant storage overhead per file (<;10KB), and it is able to handle 8-1000 concurrent data uploading per server depending on the data types.
【Keywords】: Protocols; Big Data; Monitoring; Cryptography; Data models; Conferences; Indexes
【Paper Link】 【Pages】:1-9
【Authors】: Xin Yao ; Rui Zhang ; Yanchao Zhang ; Yaping Lin
【Abstract】: Social data outsourcing is an emerging paradigm for effective and efficient access to the social data. In such a system, a third-party Social Data Provider (SDP) purchases complete social datasets from Online Social Network (OSN) operators and then resells them to data consumers who can be any individuals or entities desiring the complete social data satisfying some criteria. The SDP cannot be fully trusted and may return wrong query results to data consumers by adding fake data and deleting/modifying true data in favor of the businesses willing to pay. In this paper, we initiate the study on verifiable social data outsourcing whereby a data consumer can verify the trustworthiness of the social data returned by the SDP. We propose three schemes for verifiable queries over outsourced social data. The three schemes all require the OSN provider to generate some cryptographic auxiliary information, based on which the SDP can construct a verification object for the data consumer to verify the query-result trustworthiness. They differ in how the auxiliary information is generated and how the verification object is constructed and verified. Extensive experiments based on a real Twitter dataset confirm the high efficacy and efficiency of our schemes.
【Keywords】: Outsourcing; Twitter; Cryptography; Facebook; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Prasanna Giridhar ; Shiguang Wang ; Tarek F. Abdelzaher ; Raghu K. Ganti ; Lance M. Kaplan ; Jemin George
【Abstract】: This paper develops an algorithm that exploits picture-oriented social networks to localize urban events. We choose picture-oriented networks because taking a picture requires physical proximity, thereby revealing the location of the photographed event. Furthermore, most modern cell phones are equipped with GPS, making picture location, and time metadata commonly available. We consider Instagram as the social network of choice and limit ourselves to urban events (noting that the majority of the world population lives in cities). The paper introduces a new adaptive localization algorithm that does not require the user to specify manually tunable parameters. We evaluate the performance of our algorithm for various real-world datasets, comparing it against a few baseline methods. The results show that our method achieves the best recall, the fewest false positives, and the lowest average error in localizing urban events.
【Keywords】: Algorithm design and analysis; Flickr; Twitter; Urban areas; Event detection; Metadata
【Paper Link】 【Pages】:1-9
【Authors】: Yinghao Yu ; Wei Wang ; Jun Zhang ; Khaled Ben Letaief
【Abstract】: Memory caches are being aggressively used in today's data-parallel systems such as Spark, Tez, and Piccolo. However, prevalent systems employ rather simple cache management policies - notably the Least Recently Used (LRU) policy - that are oblivious to the application semantics of data dependency, expressed as a directed acyclic graph (DAG). Without this knowledge, memory caching can at best be performed by “guessing” the future data access patterns based on historical information (e.g., the access recency and/or frequency), which frequently results in inefficient, erroneous caching with low hit ratio and a long response time. In this paper, we propose a novel cache replacement policy, Least Reference Count (LRC), which exploits the application-specific DAG information to optimize the cache management. LRC evicts the cached data blocks whose reference count is the smallest. The reference count is defined, for each data block, as the number of dependent child blocks that have not been computed yet. We demonstrate the efficacy of LRC through both empirical analysis and cluster deployments against popular benchmarking workloads. Our Spark implementation shows that, compared with LRU, LRC speeds up typical applications by 60%.
【Keywords】: Sparks; Data analysis; Semantics; Random access memory; Conferences; Benchmark testing
【Paper Link】 【Pages】:1-9
【Authors】: Yehuda Afek ; Anat Bremler-Barr ; Lior Shafir
【Abstract】: Traditional DDoS anti-spoofing scrubbers require dedicated middleboxes thus adding CAPEX, latency and complexity in the network. This paper starts by showing that the current SDN match-and-action model is rich enough to implement a collection of anti-spoofing methods. Secondly we develop and utilize advance methods for dynamic resource sharing to distribute the required mitigation resources over a network of switches. None of the earlier attempts to implement anti-spoofing in SDN actually directly exploited the match and action power of the switch data plane. They required additional functionalities on top of the match-and-action model, and are not implementable on an SDN switch as is. Our method builds on the premise that an SDN data path is a very fast and efficient engine to perform low level primitive operations at wire speed. The solution requires a number of flow-table rules and switch-controller messages proportional to the legitimate traffic. To scale when protecting multiple large servers the flow tables of multiple switches are harnessed in a distributed and dynamic network based solution. We have fully implemented all our methods in either Open-Flow1.5 in Open-vSwitch and in P4. The system mitigates spoofed attacks on either the SDN infrastructure itself or on downstream servers.
【Keywords】: Computer crime; Servers; Control systems; Software; Materials handling; Conferences; Electronic mail
【Paper Link】 【Pages】:1-9
【Authors】: Shang Gao ; Zhe Peng ; Bin Xiao ; Aiqun Hu ; Kui Ren
【Abstract】: The separated control and data planes in software-defined networking (SDN) with high programmability introduce a more flexible way to manage and control network traffic. However, SDN will experience long packet delay and high packet loss rate when the communication link between two planes is jammed by SDN-aimed DoS attacks with massive table-miss packets. In this paper, we propose FloodDefender, an efficient and protocol-independent defense framework for SDN/OpenFlow networks to mitigate DoS attacks. It stands between the controller platform and other controller apps, and can protect both the data and control plane resources by leveraging three new techniques: table-miss engineering to prevent the communication bandwidth from being exhausted; packet filter to identify attack traffic and save computational resources of the control plane; and flow rule management to eliminate most of useless flow entries in the switch flow table. All designs of FloodDefender conform to the OpenFlow policy, requiring no additional devices. We implement a prototype of FloodDefender and evaluate its performance in both software and hardware environments. Experimental results show that FloodDefender can efficiently mitigate the SDN-aimed DoS attacks, incurring less than 0.5% CPU computation to handle attack traffic, only 18ms packet delay and 5% packet loss rate under attacks.
【Keywords】: Switches; Computer crime; Bandwidth; Delays; Monitoring; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Anat Bremler-Barr ; Eli Brosh ; Mor Sides
【Abstract】: Auto-scaling mechanisms are an important line of defense against Distributed Denial of Service (DDoS) in the cloud. Using auto-scaling, machines can be added and removed in an on-line manner to respond to fluctuating load. It is commonly believed that the auto-scaling mechanism casts DDoS attacks into Economic Denial of Sustainability (EDoS) attacks. Rather than suffering from performance degradation up to a total denial of service, the victim suffers only from the economic damage incurred by paying for the extra resources required to process the bogus traffic of the attack. Contrary to this belief, we present and analyze the Yo-Yo attack, a new attack against the auto-scaling mechanism, that can cause significant performance degradation in addition to economic damage. In the Yo-Yo attack, the attacker sends periodic bursts of overload, thus causing the auto-scaling mechanism to oscillate between scale-up and scale-down phases. The Yo-Yo attack is harder to detect and requires less resources from the attacker compared to traditional DDoS. We demonstrate the attack on Amazon EC2 [4], and analyze protection measures the victim can take by reconfiguring the auto-scaling mechanism.
【Keywords】: Cloud attack; Auto-scaling; Denial-of-service attack; Economic-Denial-of-Sustainability attack; Distributed systems security
【Paper Link】 【Pages】:1-9
【Authors】: Mathieu Jadin ; Gautier Tihon ; Olivier Pereira ; Olivier Bonaventure
【Abstract】: MultiFath TCP (MPTCP) is a recent TCP extension that enables hosts to send data over multiple paths for a single connection. It is already deployed for various use cases, notably on smartphones. In parallel with this, there is a growing deployment of encryption and authentication techniques to counter various forms of security attacks. Tcpcrypt and TLS are some of these security solutions. In this paper, we propose MPTCPsec, a MultiPath TCP extension that closely integrates authentication and encryption inside the protocol itself. Our design relies on an adaptation for the multipath environment of the ENO option that is being discussed within the IETF tcpinc working group. We then detail how MultiPath TCP needs to be modified to authenticate and encrypt all data and authenticate the different TCP options that it uses. Finally, we implement our proposed extension in the reference implementation of MultiPath TCP in the Linux kernel and we evaluate its performance.
【Keywords】: Protocols; Encryption; Authentication; Smart phones; Linux
【Paper Link】 【Pages】:1-9
【Authors】: Mark van der Boor ; Sem C. Borst ; Johan van Leeuwaarden
【Abstract】: Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-d policies. Specifically, JiQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit. The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck. Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.
【Keywords】: Servers; Load modeling; Conferences; Load management; Algorithm design and analysis; Large-scale systems
【Paper Link】 【Pages】:1-9
【Authors】: Wasiur R. KhudaBukhsh ; Amr Rizk ; Alexander Frömmgen ; Heinz Koeppl
【Abstract】: Fork-Join (FJ) queueing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed. In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies.
【Keywords】: Servers; Time factors; Optimal scheduling; Computational modeling; Steady-state; Processor scheduling
【Paper Link】 【Pages】:1-9
【Authors】: Arjun Anand ; Gustavo de Veciana
【Abstract】: Traditional wireless schedulers have been driven by rate-based criteria, e.g., utility maximizing/proportionally fair, and/or queue-based packet schedulers which do not directly reflect the Quality of Experience (QoE) associated with flow-based transactions and services. This paper proposes, a Measurement-Based Delay Optimal (MBDO) scheduler, which optimizes a cost function of the mean flow delays in a multi-class system, e.g,. web interactive, file downloads, etc. In this context the cost function expresses desired trade-offs amongst traffic classes reflecting heterogeneous QoE sensitivities which are nonlinear in the flow delays and/or system loads. To achieve optimality, MBDO scheduling uses measured system variables and knowledge (or measurement) of class flow-size distributions to adapt a weighted Gittins index scheduler. We show that under mild assumptions, and in a stationary regime, that MBDO scheduling is indeed asymptotically optimal. Perhaps more importantly, MBDO schedulers can self-optimize by adapting to slowly varying traffic loads, mixes and flow size distributions. Our extensive simulations confirm the effectiveness at realizing trade-offs and performance of the proposed approach.
【Keywords】: Delays; Cost function; Base stations; Wireless networks
【Paper Link】 【Pages】:1-9
【Authors】: Alex Davydow ; Pavel Chuprikov ; Sergey I. Nikolenko ; Kirill Kogan
【Abstract】: Modern datacenters are increasingly required to deal with latency-sensitive applications. A major question here is how to represent latency in desired objectives. Incorporation of multiple traffic characteristics (e.g., packet values and required processing requirements) significantly increases the complexity of buffer management policies. In this work, we consider weighted throughput optimization (total transmitted value) in the setting where every incoming packet is branded with intrinsic value, required processing, and slack (an offset from the arrival time when a packet should be transmitted), and the buffer is unbounded but effectively bounded by slacks. The main result is a 3-competitive algorithm as the slack-to-work ratio increases. Our results supported by a comprehensive evaluation study on CAIDA network traces.
【Keywords】: Throughput; Process control; Algorithm design and analysis; Conferences; Optimization; Scheduling; Upper bound
【Paper Link】 【Pages】:1-9
【Authors】: Yu Luo ; Lina Pu ; Yanxiao Zhao ; Guodong Wang ; Min Song
【Abstract】: Energy harvesting is emerging as a promising alternative source to power the next generation of wireless networks. This paper introduces a new energy harvesting strategy that uses a dedicated energy source to optimally replenish energy for radio frequency (RF) based wireless communication systems. Specifically, we develop a two-step dual tunnel energy requesting (DTER) strategy that allows an energy harvesting device to effectively obtain energy from a dedicated energy source. While minimizing the system energy consumption, DTER takes into account the practical constraints on both the energy source and the energy harvesting device. Additionally, the overhead issue and the charge characteristics of an energy storage component are examined to make the proposed strategy practical. To solve the nonlinear optimization problem in DTER, we convert the design of optimal energy requesting problem into a classic shortest path problem and thus enable us to find a global optimal solution through dynamic programming algorithms. Theoretical analysis and simulation study verify that DTER outperforms two other schemes in the literature.
【Keywords】: Energy consumption; Energy harvesting; Batteries; Radio frequency; Data communication; Erbium
【Paper Link】 【Pages】:1-9
【Authors】: Haipeng Dai ; Xiaoyu Wang ; Alex X. Liu ; Huizhen Ma ; Guihai Chen
【Abstract】: Wireless Power Transfer (WPT) technology has witnessed huge development because of its convenience and reliability. This paper concerns the fundamental issue of wireless charger PLacement with Optimized charging uTility (PLOT), that is, given a fixed number of chargers and a set of points on the plane, determining the positions and orientations of chargers such that the overall expected charging utility for all points is maximized. To address PLOT, we propose a 1 - 1/e - ε approximation algorithm. First, we present techniques to approximate the nonlinear charging power and the expected charging utility to make the problem almost linear. Second, we develop a Dominating Coverage Set extraction method to reduce the continuous search space of PLOT to a limited and discrete one without performance loss. Third, we prove that the reformulated problem is essentially maximizing a monotone submodular function subject to a matroid constraint, and propose a greedy algorithm to address this problem. We conduct both simulation and field experiments to validate our theoretical results, and the results show that our algorithm can outperform comparison algorithms by at least 46.3%.
【Keywords】: Wireless communication; Wireless sensor networks; Approximation algorithms; Conferences; Greedy algorithms; Performance evaluation; Reliability
【Paper Link】 【Pages】:1-9
【Authors】: Fei Wang ; Xi Zhang
【Abstract】: We address secure communications over energy-harvesting based OFDMA cooperative cognitive radio networks, where one primary user (PU) cooperates with several secondary users (SUs) in terms of both information transmission and energy harvesting. To improve spectrum utilization and ensure that SU transmitters can harvest as much energy as possible, we suppose that SUs are equipped with orthogonally dual-polarized antennas. Based on these setting-ups, we propose the polarization-enabled two-phase cooperative framework, where SU transmitters first apply power splitting technique to harvest energy from radio frequency signals radiated by the PU transmitter, and then use the harvested energy to concurrently transmit their own and the PU's data. Under the proposed framework, we develop the secure resource allocation schemes for the scenarios when SU receivers are untrusted users, implying that each SU receiver may overhear the PU's and the other SUs' confidential information. For this scenario, which has hardly been studied, we investigate the joint allocation of relays, subcarriers, power splitting ratios, and powers, with the objective to maximize the total secrecy rate of all SUs while guaranteeing the PU's minimum secrecy rate. Finally, we validate and evaluate our proposed cooperative framework and resource allocation schemes through numerical analyses.
【Keywords】: Energy harvesting; cooperative overlay CRN; orthogonally dual-polarized antennas (ODPAs); secure communication; resource allocation; RF signals
【Paper Link】 【Pages】:1-9
【Authors】: Li Yan ; Haiying Shen ; Juanjuan Zhao ; Chengzhong Xu ; Feng Luo ; Chenxi Qiu
【Abstract】: The future generation of transportation system will be featured by electrified public transportation. To fulfill metropolitan transit demands, electric vehicles (EVs) must be continuously operable without recharging downtime. Wireless Power Transfer (WPT) techniques for in-motion EV charging is a solution. It however brings up a challenge: how to deploy charging lanes in a metropolitan road network to minimize the deployment cost while enabling EVs' continuous operability. In this paper, we propose CatCharger, which is the first work that handles this challenge. From a metropolitan-scale dataset collected from multiple sources of vehicles, we observe the diversity of vehicle passing speed and daily visit frequency (called traffic attributes) at intersections (i.e., landmarks), which are important factors for charging lane deployment. To select landmarks for deployment, we first group landmarks with similar traffic attribute values using the entropy minimization clustering method, and choose better candidate landmarks from each group suitable for deployment. To determine the deployment locations from the candidate landmarks, we infer the expected vehicle residual energy at each landmark using a Kernel Density Estimator fed by the vehicles' mobility, and formulate and solve an optimization problem to minimize the total deployment cost while ensuring a certain level of expected residual energy of EVs at each landmark. Our trace-driven experiments demonstrate the superior performance of CatCharger over other methods.
【Keywords】: Roads; Charging stations; Inductive charging; Optimization; Batteries; Wireless power transfer; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Xianjin Xia ; ShiNing Li ; Yu Zhang ; Lin Li ; Tao Gu ; Yongji Liu ; Yan Pan
【Abstract】: This paper identifies two energy saving opportunities of Wi-Fi interface emerged during smartphone's screen-off periods. Exploiting the opportunities, we propose a new power saving strategy, BackPSM, for screen-off Wi-Fi communications. BackPSM regulates client to send and receive packets in batches and coordinates multiple clients to communicate at different slots (i.e., beacon interval). The core problem in BackPSM is how to coordinate client without incurring extra traffic overheads. To handle the problem, we propose a novel paradigm, Out-of-Band Communication (OBC), for client-to-client direct communications. OBC exploits the TIM (Traffic Indication Map) field of Wi-Fi Beacon to create a free side-channel between clients. It is based upon the observation that a client may control 1 → 0 appearing on TIM bit by locally regulating packet receiving operations. We adopt this 1 → 0 as the basic signal, and leverage the time length in between two signals to encode information. We demonstrate that OBC can be used to convey coordination information with close to 100% accuracy. We have implemented and evaluated BackPSM on a testbed. The results show that BackPSM reduces screen-off energy by up to 60%, and outperforms state-of-the-art strategies by 16%-42%.
【Keywords】: Wireless fidelity; Switches; Smart phones; Delays; Energy consumption; Scalability
【Paper Link】 【Pages】:1-9
【Authors】: Meng Jin ; Yuan He ; Dingyi Fang ; Xiaojiang Chen ; Xin Meng ; Tianzhang Xing
【Abstract】: Smartphone theft is a non-negligible problem that causes serious concerns on personal property, privacy, and public security. The existing solutions to this problem either provide only functions like retrieving a phone, or require dedicated hardware to detect thefts. How to protect smartphones from being stolen at all times is still an open problem. In this paper, we propose iGuard, a real-time anti-theft system for smartphones. iGuard utilizes only the inertial sensing data from the smartphone. The basic idea behind iGuard is to distinguish different people holding a smartphone, by identifying the order of the motions during the `take-out' behavior and how each motion is performed. For this purpose, we design a motion segmentation algorithm to detect the transition between two motions from the noisy sensing data. We then leverage the distinct feature contained in each sub-segment of a motion, instead of the entire motion, to estimate the probability that the motion is performed by the smartphone owner himself/herself. Based on such pre-processed data, we propose a Markov Chain based model to track the behavior of a smartphone user. According to this model, iGuard instantly alarms once the tracked data deviate from the smartphone owner's usual habit. We implement iGuard on Android and evaluate its performance in real environments. The experimental results show that iGuard is accurate and robust in various scenarios.
【Keywords】: Smart phones; Legged locomotion; Acceleration; Sensors; Feature extraction; Real-time systems; Tracking
【Paper Link】 【Pages】:1-9
【Authors】: Xiangyu Xu ; Hang Gao ; Jiadi Yu ; Yingying Chen ; Yanmin Zhu ; Guangtao Xue ; Minglu Li
【Abstract】: Real-time driving behavior monitoring is a corner stone to improve driving safety. Most of the existing studies on driving behavior monitoring using smartphones only provide detection results after an abnormal driving behavior is finished, not sufficient for driver alert and avoiding car accidents. In this paper, we leverage existing audio devices on smartphones to realize early recognition of inattentive driving events including Fetching Forward, Picking up Drops, Turning Back and Eating or Drinking. Through empirical studies of driving traces collected in real driving environments, we find that each type of inattentive driving event exhibits unique patterns on Doppler profiles of audio signals. This enables us to develop an Early Recognition system, ER, which can recognize inattentive driving events at an early stage and alert drivers timely. ER employs machine learning methods to first generate binary classifiers for every pair of inattentive driving events, and then develops a modified vote mechanism to form a multi-classifier for all inattentive driving events along with other driving behaviors. It next turns the multi-classifier into a gradient model forest to achieve early recognition of inattentive driving. Through extensive experiments with 8 volunteers driving for about half a year, ER can achieve an average total accuracy of 94.80% for inattentive driving recognition and recognize over 80% inattentive driving events before the event is 50% finished.
【Keywords】: Smart phones; Erbium; Doppler effect; Automobiles; Monitoring; Turning
【Paper Link】 【Pages】:1-9
【Authors】: Yi Gao ; Yang Luo ; Daqing Chen ; Haocheng Huang ; Wei Dong ; Mingyuan Xia ; Xue Liu ; Jiajun Bu
【Abstract】: For mobile apps, user-perceived delays are critical for user satisfaction. According to our measurement, long delays are commonly caused by network and storage I/O operations while short delays are mainly caused by UI rendering. Short delays are not uncommon, which account for 55.3% in our measurement cases. Previous app performance studies have largely focused on I/O operations but the understanding of UI rendering impact is limited. In this work, we propose DRAW, a system that performs two UI rendering analyses to help app developers pinpoint rendering problems and resolve short delays. The first analysis outlines the wasted rendering time on invisible or covered UI components, namely the overdraw problem. The second analysis is to identify the responsible UI components and rendering operations that cause overall low rendering efficiency. We implement DRAW on Android and apply it to study 1,158 real-world Android apps. Results show that DRAW is helpful as it can pinpoint the responsible UI components and specific rendering operations. Four concrete case studies of real-world apps are further presented to show how DRAW can help developers improve the UI rendering performance of their apps.
【Keywords】: Rendering (computer graphics); Androids; Humanoid robots; Mobile applications; Delays; Smart phones; Time factors
【Paper Link】 【Pages】:1-9
【Authors】: Guanyu Gao ; Yonggang Wen ; Han Hu
【Abstract】: Adaptive bitrate (ABR) streaming is the de facto solution in online video services to cope with heterogeneous devices and varying network connections. However, this solution is computation intensive, demanding a large number of servers for encoding videos. Moreover, due to the time-varying nature of video generation, intelligent strategies are required in order to determine the right amount of resources for encoding. The situation is further complicated by the fact that, the two types of co-existing video content, live content and Video-on-Demand (VoD) content, have different QoS requirements for encoding. These observations posit daunting challenges for meeting the heterogeneous QoS requirements with a minimum computing capacity. This paper proposes the QoS-differentiated low-cost video encoding (QDLCoding) scheme to address these challenges. We develop a framework for scheduling the encoding workloads of the two types of videos with statistical QoS guarantees. Each type of videos is specified with a QoS criterion and a QoS loss bound. The objective is to provision the minimum amount of resources while keeping the QoS loss probabilities within the prescribed bounds. We design an online algorithm that can determine the minimum required capacity by learning content arrival distributions. The experiment results demonstrate that our method can greatly reduce the required capacity for encoding online videos while controlling the likelihood of QoS loss precisely.
【Keywords】: Streaming media; Quality of service; Encoding; Servers; Resource management; Delays; Capacity planning
【Paper Link】 【Pages】:1-9
【Authors】: Ming Tang ; Shou Wang ; Lin Gao ; Jianwei Huang ; Lifeng Sun
【Abstract】: Crowdsourced mobile video streaming enables nearby mobile video users to aggregate their network resources to improve the video streaming performance. However, users are often selfish and may not be willing to cooperate without proper incentives. Designing an incentive mechanism for such a scenario is challenging due to the users' asynchronous downloading behaviors as well as their private valuations for multi-bitrate encoded videos. In this work, we propose a multi-object multi-dimensional auction-based incentive framework, through which users can download multiple video segments with different bitrates for multiple nearby users (and themselves). Based on this incentive framework, we propose a Vickrey-score auction, which is the first multi-object multi-dimensional auction that achieves both truthfulness and efficiency. Simulations with real traces show that crowdsourced mobile streaming outperforms noncooperative streaming by 48.6% (on average) in terms of social welfare. We further implement our proposed auction mechanism in a demostration system, and show that the crowdsourced framework together with the auction mechanism can substantially increase mobile user's welfare and video service stability.
【Keywords】: Streaming media; Bit rate; Adaptation models; Mobile communication; Resource management; Mobile computing; Cost accounting
【Paper Link】 【Pages】:1-9
【Authors】: Kazuhisa Matsuzono ; Hitoshi Asaeda ; Thierry Turletti
【Abstract】: Owing to the rapid growth in high-quality video streaming over the Internet, preserving high-level robustness against data loss and low latency, while maintaining higher data transmission rates, is becoming an increasingly important issue for high-quality real-time delay-sensitive streaming. In this paper, we propose a low latency, low loss streaming mechanism, L4C2, specialized for high-quality delay-sensitive streaming. With L4C2, nodes in the network estimate the acceptable delay and packet loss probability in their uplinks, aiming at retrieving lost data packets from in-network cache and/or coded data packets using in-network coding within an acceptable delay, by extending the Content-Centric Networking (CCN) approach. Further, L4C2 naturally provides multiple paths and multicast technologies to efficiently utilize network resources while sharing network resources fairly with competing data flows by adjusting the video quality when necessary. We validate through comprehensive simulations that L4C2 achieves a high success probability of data transmission considering the acceptable one-way delay, and higher QoE while suppressing the interest and redundant data traffic than the proposed multipath congestion control mechanism in CCN.
【Keywords】: Streaming media; Delays; Real-time systems; Encoding; Robustness; Video recording; Quality assessment
【Paper Link】 【Pages】:1-9
【Authors】: Ahmed Badr ; Ashish Khisti ; Wai-tian Tan ; Xiaoqing Zhu ; John G. Apostolopoulos
【Abstract】: We introduce a new class of forward error correction (FEC) codes for VoIP communications which support different recovery delay depending on the channel conditions. Specifically, our proposed class of Dual-Delay (DD) codes can recover from challenging long bursts of losses with close to theoretical minimum delay so as to meet playback deadlines for recovered packets. They further improve conversational interactivity by achieving lower recovery delay during periods of random isolated losses. These DD codes are shown to achieve lower residual loss rates when compared to existing codes over a wide range of parameters of the Gilbert-Elliott channel. Experiments over real world packet traces further show performance gains of DD codes in terms of perceptually motivated ITU-T G.107 E-model.
【Keywords】: VoIP Audio Quality; Interactive Multimedia Applications; Application Layer Forward Error Correction (AL-FEC); Burst Erasures; E-model
【Paper Link】 【Pages】:1-9
【Authors】: Guoming Tang ; Kui Wu ; Richard Brunner
【Abstract】: The content delivery network (CDN) intensively uses cache to push the content close to end users. Over both traditional Internet architecture and emerging cloud-based framework, cache allocation has been the core problem that any CDN operator needs to address. As the first step for cache deployment, CDN operators need to discover or estimate the distribution of user requests in different geographic areas. This step results in a statistical spatial model for the user requests, which is used as the key input to solve the optimal cache deployment problem. More often than not, the temporal information in user requests is omitted to simplify the CDN design. In this paper, we disclose that the spatial request model alone may not lead to truly optimal cache deployment. By considering the temporal information in user requests, we provide a dynamic traffic based solution to this broadly studied problem. Via experiments over the North American ISPs Points of Presence (PoPs) network, our new solution outperforms traditional CDN design method and saves the overall delivery cost by 16% to 20%.
【Keywords】: Optimization; Servers; Network topology; Topology; Internet; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Samta Shukla ; Alhussein A. Abouzeid
【Abstract】: We consider the problem of proactive (i.e. predictive) content caching that is aware of the costs of retention of the content in the cache. Prior work on caching (whether proactive or reactive) does not explicitly take into account the storage cost due to the duration of time for which a content is cached. This new problem, which we call retention aware caching, is motivated by two recent technological developments that are described in the paper: cloud storage rental costs and flash memory damage. We consider a hierarchical network consisting of a server connected to a number of cache-enabled nodes, located either at the edge of a network (e.g. base stations) or in the core of a data center. There are two types of network costs: storage cost at the caches and download cost from the server. We formulate the problem of proactive retention aware data caching (PRAC), which minimizes the total cost subject to the node capacity constraints. We first prove that PRAC is NP-Hard in general and then analyze PRAC for two cases: (1) linear storage cost, (2) convex storage cost. We show that PRAC admits efficient polynomial time algorithms when the storage cost is linear in retention times and caches have a large capacity. Furthermore, we derive bounds on the performance of PRAC for the case when the storage cost is a practically motivated convex function. Numerical evaluations demonstrate that PRAC outperforms other state-of-the-art caching policies for a wide range of parameters of interest.
【Keywords】: Servers; Cloud computing; Delays; Conferences; Multicast communication; Hardware
【Paper Link】 【Pages】:1-9
【Authors】: Li Qiu ; Guohong Cao
【Abstract】: In wireless ad hoc networks, due to the interference between concurrent transmissions, the per node capacity generally decreases with the increasing number of nodes in the network. Caching can help improve the network capacity, as it shortens the content transmission distance and reduces the communication interference. However, current researches on the capacity of wireless ad hoc networks with caching generally assume that content popularity follows uniform distribution. They ignore the fact that contents in reality have skewed popularity, which may lead to totally different capacity results. In this paper, we evaluate how the distribution of the content popularity affects the network capacity, and derive different capacity scaling laws based on the skewness of the content popularity. Our results suggest that for wireless networks with caching, when contents have skewed popularity, increasing the number of nodes monotonically increases the per node capacity.
【Keywords】: Mobile ad hoc networks; Wireless networks; Interference; Conferences; Throughput; Internet
【Paper Link】 【Pages】:1-9
【Authors】: Livia Elena Chatzieleftheriou ; Merkourios Karaliopoulos ; Iordanis Koutsopoulos
【Abstract】: Caching decisions by default seek to maximize some notion of social welfare: the content to be cached is determined so that the maximum possible aggregate demand over all users served by the cache is satisfied. Recommendation systems, on the contrary, are oriented towards user individual preferences: the recommended content should be most appealing to the user so as to elicit further content consumption. In our paper we explore how these, phenomenically conflicting, objectives can be jointly addressed. To this end, we depart radically from current practice with recommender systems, and we approach them as network traffic engineering tools that can actively shape content demand towards optimizing user- and network-centric performance objectives. We formulate the resulting joint theoretical optimization problem of deciding on the cached content and the recommendations to each user so that the cache hit ratio is maximized subject to a maximum tolerable distortion that the recommendation should undergo. We conclude on its complexity, and we propose a practical algorithm for its solution. The algorithm is essentially a form of lightweight control over the user recommendations so that the recommended content is both appealing to the end user and more friendly to the caching system and the network resources.
【Keywords】: Recommender systems; Wireless networks; Distortion; Conferences; Shape; Mobile computing
【Paper Link】 【Pages】:1-9
【Authors】: Mingjun Xiao ; Jie Wu ; Sheng Zhang ; Jiapeng Yu
【Abstract】: Mobile crowdsensing is a new paradigm in which a requester can recruit a group of mobile users via a platform and coordinate them to perform some sensing tasks by using their smartphones. In mobile crowdsensing, each user might perform multiple tasks with different sensing qualities. An important problem is recruiting the minimum number of users while achieving a satisfactory sensing quality for each task. Meanwhile, in order to ease users' worries about privacy disclosures, the user recruitment process needs to protect each user's sensing quality information from being revealed to other users or to the platform. We prove that this problem is NP-hard. To solve this problem, we first propose a Basic User Recruitment (BUR) protocol based on a greedy strategy, which can recruit nearly the minimum amount of users while ensuring that the total sensing quality of each task is no less than a given threshold. Based on BUR, we further propose a Secure User Recruitment (SUR) protocol by using secret sharing schemes. We analyze the approximation ratio and prove the security of the SUR protocol in the semi-honest model. Moreover, we extend SUR to deal with a more general case where the total sensing quality of each task might be an increasing submodular function. Finally, we demonstrate the significant performance of the proposed protocol through extensive simulations and execution in real smartphones.
【Keywords】: Mobile crowdsensing; privacy; sensing quality; secret sharing; user recruitment
【Paper Link】 【Pages】:1-9
【Authors】: Shengzhong Liu ; Zhenzhe Zheng ; Fan Wu ; Shaojie Tang ; Guihai Chen
【Abstract】: With the rapid growth of smart devices, mobile crowdsensing is becoming an important paradigm to acquire information from physical environments. Considering that the sensing data collected by mobile users are normally noisy and imprecise, one of the pressing problems in mobile crowdsensing is to evaluate the data quality in real time and to steer users to acquire data with high quality. However, it is challenging to estimate the data quality without the availability of ground truth data. In this paper, we observe that sensing context has a significant impact on data quality, which motivates us to propose a context-aware data quality estimation scheme. With historical sensing data, we train a context-quality classifier, which captures the relation between context information and data quality, to estimate data quality in an online manner. We apply such a context-aware data quality estimation scheme to guide user recruitment in mobile crowdsensing. We model the process of user recruitment as a stochastic submodular maximization problem, and design a random adaptive greedy algorithm to guarantee a constant approximation ratio. We evaluate our algorithm on a real-world temperature data set. The evaluation results show that our algorithm outperforms other existing techniques, in terms of prediction accuracy.
【Keywords】: Sensors; Mobile communication; Estimation; Real-time systems; Recruitment; Noise measurement; Legged locomotion
【Paper Link】 【Pages】:1-9
【Authors】: Qiang Xu ; Rong Zheng
【Abstract】: An important category of mobile crowdsensing applications involve collecting sensor measurements from mobile devices and querying mobile users for annotations to build machine learning models for inference and prediction. Trade-offs between inference performance and the costs of data acquisition (both unlabeled and labeled) are not yet well understood. In this paper, we develop, ALSense, a distributed active learning framework for mobile crowdsensing. The goal is to minimize prediction errors for classification-based mobile crowdsensing tasks subject to upload and query cost constraints. Novel stream-based active learning strategies are developed to orchestrate queries of annotation data and the upload of unlabeled data from mobile devices. We evaluate the effectiveness of ALSense through two applications that can benefit from mobile crowdsensing, namely, WiFi fingerprint-based indoor localization and IMU-based human activity recognition. Extensive experiments demonstrate that ALSense can indeed achieve higher classification accuracy given fixed data acquisition budgets for both applications.
【Keywords】: Mobile handsets; Mobile communication; Servers; Sensors; Data acquisition; Predictive models
【Paper Link】 【Pages】:1-9
【Authors】: Man Hon Cheung ; Fen Hou ; Jianwei Huang
【Abstract】: In a mobile crowdsensing (MCS) application, user diversity and social effect are two important phenomena that determine its profitability, where the former improves the sensing quality, while the latter incentives the users' participation. In this paper, we consider a reward mechanism design for the service provider to achieve diversity in the collected data by exploiting the users' social relationship. Specifically, we formulate a two-stage decision problem, where the service provider first optimizes its rewards for profit maximization. The users then decide their effort levels through social network interactions as a participation game. The analysis is particularly challenging due to the users' interplay in both the diversity and social graphs, which leads to a non-convex bilevel optimization problem. Surprisingly, we find that the service provider can focus on one superimposed graph that incorporates the diversity and social relationship and compute the optimal reward as the Katz centrality in closed-form. Simulation results, based on the random graph and a real Facebook trace, show that the availability of network information improves both the service provider's profit and the users' social surplus over the incomplete information cases.
【Keywords】: Cultural differences; Sensors; Mobile communication; Facebook; Games
【Paper Link】 【Pages】:1-9
【Authors】: Yu Sang ; Bo Ji ; Gagan Raj Gupta ; Xiaojiang Du ; Lin Ye
【Abstract】: Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1))lnm (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1))ln m + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.
【Keywords】: Greedy algorithms; Network topology; Resource management; Topology; Heuristic algorithms; Algorithm design and analysis; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Rui Han ; Fan Zhang ; Zhentao Wang
【Abstract】: The growing demands of processing massive datasets have promoted irresistible trends of running machine learning applications on MapReduce. When processing large input data, it is often of greater values to produce fast and accurate enough approximate results than slow exact results. Existing techniques produce approximate results by processing parts of the input data, thus incurring large accuracy losses when using short job execution times, because all the skipped input data potentially contributes to result accuracy. We address this limitation by proposing AccurateML that aggregates information of input data in each map task to create small aggregated data points. These aggregated points enable all map tasks producing initial outputs quickly to save computation times and decrease the outputs' size to reduce communication times. Our approach further identifies the parts of input data most related to result accuracy, thus first using these parts to improve the produced outputs to minimize accuracy losses. We evaluated AccurateML using real machine learning applications and datasets. The results show: (i) it reduces execution times by 30 times with small accuracy losses compared to exact results; (ii) when using the same execution times, it achieves 2.71 times reductions in accuracy losses compared to existing approximate processing techniques.
【Keywords】: MapReduce; machine learning; approximate processing; result accuracy; information aggregation
【Paper Link】 【Pages】:1-9
【Authors】: Juan F. Pérez ; Robert Birke ; Lydia Y. Chen
【Abstract】: To ensure the scalability of big data analytics, approximate MapReduce platforms emerge to explicitly trade off accuracy for latency. A key step to determine optimal approximation levels is to capture the latency of big data jobs, which is long deemed challenging due to the complex dependency among data inputs and map/reduce tasks. In this paper, we use matrix analytic methods to derive stochastic models that can predict a wide spectrum of latency metrics, e.g., average, tails, and distributions, for approximate MapReduce jobs that are subject to strategies of input sampling and task dropping. In addition to capturing the dependency among waves of map/reduce tasks, our models incorporate two job scheduling policies, namely, exclusive and overlapping, and two task dropping strategies, namely, early and straggler, enabling us to realistically evaluate the potential performance gains of approximate computing. Our numerical analysis shows that the proposed models can guide big data platforms to determine the optimal approximation strategies and degrees of approximation.
【Keywords】: Time factors; Analytical models; Big Data; Computational modeling; Conferences; Measurement
【Paper Link】 【Pages】:1-9
【Authors】: Hao Feng ; Jaime Llorca ; Antonia Maria Tulino ; Danny Raz ; Andreas F. Molisch
【Abstract】: Distributed cloud networking builds on network functions virtualization (NFV) and software defined networking (SDN) to enable the deployment of network services in the form of elastic virtual network functions (VNFs) instantiated over general purpose servers at distributed cloud locations. We address the design of fast approximation algorithms for the NFV service distribution problem (NSDP), whose goal is to determine the placement of VNFs, the routing of service flows, and the associated allocation of cloud and network resources that satisfy client demands with minimum cost. We show that in the case of load-proportional costs, the resulting fractional NSDP can be formulated as a multi-commodity-chain flow problem on a cloud-augmented graph, and design a queue-length based algorithm, named QNSD, that provides an O(ε) approximation in time O (1/ε). We then address the case in which resource costs are a function of the integer number of allocated resources and design a variation of QNSD that effectively pushes for flow consolidation into a limited number of active resources to minimize overall cloud network cost.
【Keywords】: Cloud computing; Algorithm design and analysis; Approximation algorithms; Routing; Network function virtualization; Servers; Resource management
【Paper Link】 【Pages】:1-9
【Authors】: János Tapolcai ; Lajos Rónyai ; Balazs Vass ; Laszlo Gyimothi
【Abstract】: Shared Risk Link Group (SRLG) is a failure the network is prepared for, which contains a set of links subject to a common risk of single failure. During planning a backbone network, the list of SRLGs must be defined very carefully, because leaving out one likely failure event will significantly degrade the observed reliability of the network. Regional failures are manifested at multiple locations of the network, which are physically close to each other. In this paper we show that operators should prepare a network for only a small number of possible regional failure events. In particular, we give a fast systematic approach to generate the list of SRLGs that cover every possible circular disk failure of a given radius r. We show that this list has O((n + x)σr) SRLGs, where n is the number of nodes in the network, x is the number of link crossings, and σr is the maximal number of links that could be hit by a disk failure of radius r. Finally through extensive simulations we show that this list in practice has size of ≈ 1.2 n.
【Keywords】: Reliability; Earthquakes; Tornadoes; Conferences; Computer network reliability; Hurricanes; Topology
【Paper Link】 【Pages】:1-9
【Authors】: Ying Zhang ; Wenfei Wu ; Sujata Banerjee ; Joon-Myung Kang ; Mario A. Sánchez
【Abstract】: Network verification has been recently proposed to detect network misconfigurations. Existing work focuses on the reachability. This paper proposes a framework that verifies the Service Level Agreement (SLA) compliance of the network using static verification. This work proposes a quantitative model and a set of algorithms for verifying performance properties of a network with switches and middleboxes, i.e., service chains. We develop SLA-Verifier and evaluate its efficiency using simulation on real-world data and testbed experiments. To improve the SLA violation detection accuracy, our system uses verification results to optimize online monitoring.
【Keywords】: Bandwidth; Middleboxes; Quality of service; Load modeling; Monitoring; Noise measurement
【Paper Link】 【Pages】:1-9
【Authors】: Stefano Ciavarella ; Novella Bartolini ; Hana Khamfroush ; Thomas F. La Porta
【Abstract】: After a massive scale failure, the assessment of damages to communication networks requires local interventions and remote monitoring. While previous works on network recovery require complete knowledge of damage extent, we address the problem of damage assessment and critical service restoration in a joint manner. We propose a polynomial algorithm called Centrality based Damage Assessment and Recovery (CeDAR) which performs a joint activity of failure monitoring and restoration of network components. CeDAR works under limited availability of recovery resources and optimizes service recovery over time. We modified two existing approaches to the problem of network recovery to make them also able to exploit incremental knowledge of the failure extent. Through simulations we show that CeDAR outperforms the previous approaches in terms of recovery resource utilization and accumulative flow over time of the critical services.
【Keywords】: Maintenance engineering; Monitoring; Schedules; Knowledge engineering; Inspection; Communication networks; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Yigal Bejerano ; Chandru Raman ; Chun-Nam Yu ; Varun Gupta ; Craig Gutterman ; Tomas Young ; Hugo Infante ; Yousef Abdelmalek ; Gil Zussman
【Abstract】: LTE evolved Multimedia Broadcast/Multicast Service (eMBMS) is an attractive solution for video delivery to very large groups in crowded venues. However, deployment and management of eMBMS systems is challenging, due to the lack of realtime feedback from the User Equipment (UEs). Therefore, we present the Dynamic Monitoring (DyMo) system for low-overhead feedback collection. DyMo leverages eMBMS for broadcasting Stochastic Group Instructions to all UEs. These instructions indicate the reporting rates as a function of the observed Quality of Service (QoS). This simple feedback mechanism collects very limited QoS reports from the UEs. The reports are used for network optimization, thereby ensuring high QoS to the UEs. We present the design aspects of DyMo and evaluate its performance analytically and via extensive simulations. Specifically, we show that DyMo infers the optimal eMBMS settings with extremely low overhead, while meeting strict QoS requirements under different UE mobility patterns and presence of network component failures. For instance, DyMo can detect the eMBMS Signal-to-Noise Ratio (SNR) experienced by the 0.1% percentile of the UEs with Root Mean Square Error (RMSE) of 0.05% with only 5 to 10 reports per second regardless of the number of UEs.
【Keywords】: Wireless Monitoring; LTE; eMBMS; Multi-cast; Feedback Mechanism
【Paper Link】 【Pages】:1-9
【Authors】: Meng Zhang ; Lin Gao ; Jianwei Huang ; Michael L. Honig
【Abstract】: Mobile Crowdsourced Access (MCA) enables mobile users (MUs) to share their Internet connections by serving as tethers to other MUs, hence can improve the quality of service of MUs as well as the overall utilization of network resources. However, MCA can also reduce the revenue-generating mobile traffic and increase the network congestion for mobile network operators (MNOs), and thus has been blocked by some MNOs in practice. In this work, we reconcile the conflicting objectives of MNOs and MUs by introducing a pricing framework for MCA, where the direct traffic and tethering traffic are charged independently according to a data price and a tethering price, respectively. We derive the optimal data and tethering prices systematically for MUs with the α-fair utility in two scenarios with cooperative and competitive MNOs, respectively. We show that the optimal tethering prices are zero and the optimal usage-based data prices are identical for all MUs, in both the cooperative and competitive scenarios. Such optimal pricing schemes will lead to mutually beneficial results for MNOs and MUs. Our simulation results show that the proposed pricing scheme approximately triples both the MNOs' profit and the MUs' payoff when the MNOs cooperate, comparing to the case where MCA is blocked. Moreover, competition among MNOs will decrease MNOs' profit and further increase the MUs' payoff.
【Keywords】: Pricing; Mobile communication; Mobile computing; Internet; Wireless fidelity; Downlink; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Dario Bega ; Marco Gramaglia ; Albert Banchs ; Vincenzo Sciancalepore ; Konstantinos Samdanis ; Xavier Pérez Costa
【Abstract】: In addition to providing substantial performance enhancements, future 5G networks will also change the mobile network ecosystem. Building on the network slicing concept, 5G allows to “slice” the network infrastructure into separate logical networks that may be operated independently and targeted at specific services. This opens the market to new players: the infrastructure provider, which is the owner of the infrastructure, and the tenants, which may acquire a network slice from the infrastructure provider to deliver a specific service to their customers. In this new context, we need new algorithms for the allocation of network resources that consider these new players. In this paper, we address this issue by designing an algorithm for the admission and allocation of network slices requests that (i) maximises the infrastructure provider's revenue and (ii) ensures that the service guarantees provided to tenants are satisfied. Our key contributions include: (i) an analytical model for the admissibility region of a network slicing-capable 5G Network, (ii) the analysis of the system (modelled as a Semi-Markov Decision Process) and the optimisation of the infrastructure provider's revenue, and (iii) the design of an adaptive algorithm (based on Q-learning) that achieves close to optimal performance.
【Keywords】: Base stations; 5G mobile communication; Algorithm design and analysis; Throughput; Ecosystems; Adaptation models; Mobile computing
【Paper Link】 【Pages】:1-9
【Authors】: Pablo Caballero Garces ; Albert Banchs ; Gustavo de Veciana ; Xavier Pérez Costa
【Abstract】: Network slicing to enable resource sharing among multiple tenants-network operators and/or services-is considered a key functionality for next generation mobile networks. This paper provides an analysis of a well-known model for resource sharing, the `share-constrained proportional allocation' mechanism, to realize network slicing. This mechanism enables tenants to reap the performance benefits of sharing, while retaining the ability to customize their own users' allocation. This results in a network slicing game in which each tenant reacts to the user allocations of the other tenants so as to maximize its own utility. We show that, under appropriate conditions, the game associated with such strategic behavior converges to a Nash equilibrium. At the Nash equilibrium, a tenant always achieves the same, or better, performance than under a static partitioning of resources, hence providing the same level of protection as such static partitioning. We further analyze the efficiency and fairness of the resulting allocations, providing tight bounds for the price of anarchy and envy-freeness. Our analysis and extensive simulation results confirm that the mechanism provides a comprehensive practical solution to realize network slicing. Our theoretical results also fill a gap in the literature regarding the analysis of this resource allocation model under strategic players.
【Keywords】: Resource management; Base stations; Mobile communication; Mobile computing; Analytical models; Nash equilibrium; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Mao Zou ; Richard T. B. Ma ; Xin Wang ; Yinlong Xu
【Abstract】: As Internet applications have become more diverse in recent years, users having heavy demand for online video services are more willing to pay higher prices for better services than light users that mainly use e-mails and instant messages. This encourages the Internet Service Providers (ISPs) to explore service differentiations so as to optimize their profits and allocation of network resources. Much prior work has focused on the viability of network service differentiation by comparing with the case of a single-class service. However, the optimal service differentiation for an ISP subject to resource constraints has remained unsolved. In this work, we establish an optimal control framework to derive the analytical solution to an ISP's optimal service differentiation, i.e., the optimal service qualities and associated prices. By analyzing the structures of the solution, we reveal how an ISP should adjust the service qualities and prices in order to meet varying capacity constraints and users' characteristics. We also obtain the conditions under which ISPs have strong incentives to implement service differentiation and whether regulators should encourage such practices.
【Keywords】: Pricing; Capacity planning; Optimal control; Conferences; Regulators; Quality of service; Resource management
【Paper Link】 【Pages】:1-9
【Authors】: Peshal Nayak ; Michele Garetto ; Edward W. Knightly
【Abstract】: In this paper we present the first cross-layer analysis of wireless LANs operating under downlink multi-user MIMO (MU-MIMO), considering the fundamental role played by closed-loop (TCP) traffic. In particular, we consider an 802.11ac scenario in which the access point transmits on the downlink via MU-MIMO, whereas stations must employ single-user transmissions on the uplink. With the help of analytical models built for the different regimes that can occur in the considered system, we identify and explain crucial performance anomalies that can result in very low throughput in some scenarios, completely offsetting the theoretical gains achievable by MU-MIMO. We discuss solutions to mitigate the risk of this performance degradation and alternative uplink strategies allowing WLANs to approach their maximum theoretical capacity under MU-MIMO.
【Keywords】: Downlink; Uplink; Throughput; MIMO; Servers; Wireless LAN; Standards
【Paper Link】 【Pages】:1-9
【Authors】: Dolvara Gunatilaka ; Mo Sha ; Chenyang Lu
【Abstract】: Industrial automation has emerged as an important application of wireless sensor-actuator networks (WSANs). To meet stringent reliability requirements of industrial applications, industrial standards such as WirelessHART adopt Time Slotted Channel Hopping (TSCH) as its MAC protocol. Since every link hops through all the channels used in TSCH, a straightforward policy to ensure reliability is to retain a link in the network topology only if it is reliable in all channels used. However, this policy has surprising side effects. While using more channels may enhance reliability due to channel diversity, more channels may also reduce the number of links and route diversity in the network topology. We empirically analyze the impact of channel selection on network topology, routing, and scheduling on a 52-node WSAN testbed. We observe inherent tradeoff between channel diversity and route diversity in channel selection, where using an excessive number of channels may negatively impact routing and scheduling. We propose novel channel and link selection strategies to improve route diversity and network schedulability. Experimental results on two different testbeds show that our algorithms can drastically improve routing and scheduling of industrial WSANs.
【Keywords】: Routing; Reliability; Network topology; Wireless sensor networks; Wireless communication; IEEE 802.15 Standard
【Paper Link】 【Pages】:1-9
【Authors】: Andrea Baiocchi ; Ilenia Tinnirello ; Domenico Garlisi ; Alice Lo Valvo
【Abstract】: In this paper we propose ReCo, a robust contention scheme for emerging wireless technologies, whose efficiency is not sensitive to the number of contending stations and to the settings of the contention parameters (such as the contention windows and retry limits). The idea is iterating a basic contention mechanism, devised to select a sub-set of stations among the contending ones, in consecutive elimination rounds, before performing a transmission attempt. Elimination rounds can be performed in the time or frequency domain, with different overheads, according to the physical capabilities of the nodes. Closed analytical formulas are given to dimension the number of contention rounds in order to achieve an arbitrary low collision probability. Simulation results and a real implementation for the time-domain solution demonstrate the effectiveness and robustness of this approach in comparison to IEEE 802.11 DCF.
【Keywords】: Frequency-domain analysis; OFDM; Wireless communication; IEEE 802.11 Standard; Protocols; Multiaccess communication
【Paper Link】 【Pages】:1-9
【Authors】: Chao-Fang Shih ; Raghupathy Sivakumar
【Abstract】: Lightweight control planes are techniques that create a control plane in WiFi networks without any additional spectrum requirements. Flash signals are an example of such control signals that exploit the link margin that typically exists in WiFi communication. In this paper we consider the problem of allowing transmitters and receivers of a transmission to exploit such control channels while the communication is ongoing. We present a mechanism called switch that facilitates switches in communication modes (Tx to Rx and vice-versa). We then use switch as the core building block to solve problems in WiFi networks such as starvation due to hidden terminals, early collision termination, and frequency backoffs. We rely on WARP radios to experimentally verify that switch is indeed possible, and use ns-3 simulations to study the impact of using switch to solve the aforementioned WiFi problems.
【Keywords】: Switches; Receivers; Wireless fidelity; Radio transmitters; Delays
【Paper Link】 【Pages】:1-9
【Authors】: Wenchi Cheng ; Xi Zhang ; Hailin Zhang
【Abstract】: In the non-time-slotted cognitive radio networks (CRNs), the synchronization between PUs and secondary users (SUs) cannot be guaranteed, resulting in two challenging problems: the reactivation-failure of PUs and the frequently unexpected hand-offs among SUs. The reactivation-failure of PUs is the incident that the SUs cannot detect the PUs' reactivation when the SUs are occupying the channels to transmit their data in non-time-slotted CRNs. The frequently unexpected handoffs among SUs are the events that the SU cannot distinguish between the PUs' reactivation and the other SUs' contention, thus causing many unexpected hand-offs among SUs, which severely degrade the achieved throughput of SUs in non-time-slotted CRNs. Employing the energy-detection based wireless full-duplex spectrum sensing schemes, the PUs' reactivation-failure problem can be efficiently solved, thus guaranteeing the required throughput of PUs. However, the key of CRNs is not only the throughput-guarantees for PUs, but also the throughput-boosts for SUs. To optimize the throughput of SUs in multichannel non-time-slotted CRNs, in this paper we develop the pilot-based full-duplex spectrum sensing (PF-SS) scheme and the pilot-based medium access control (P-MAC) protocol to not only guarantee the required throughput of PUs, but also significantly increase the throughput of SUs in multichannel non-time-slotted CRNs. Using the PF-SS scheme, the SUs can identify whether the PUs' signal or the SUs' signal, thus significantly reducing the frequently unexpected hand-offs among SUs. Then, based on the PF-SS scheme, the P-MAC protocol can significantly increase the throughput of SUs. We conduct extensive numerical analyses to show that our developed PF-SS scheme and P-MAC protocol can significantly increase the throughput of SUs while guaranteeing the required throughput for PUs in multichannel non-time-slotted CRNs.
【Keywords】: Non-time-slotted cognitive radio networks; hand-offs among secondary users; pilot-based full-duplex spectrum sensing; pilot-based medium access control protocol
【Paper Link】 【Pages】:1-9
【Authors】: Xingya Liu ; Jiang Xie
【Abstract】: Ideally, users in cognitive radio networks (CRNs) are capable of sensing and exploiting any potential transmission opportunities in the available spectrum band ranging from 30 KHz to 300 GHz. With the multiple-diverse-band spectrum, the network can provide more radio resources and capacity to a large number of CR users. However, the multiband scenario (e.g., TV band + 2/3G band + 4/5G band) also introduces significant challenges in channel rendezvous, a fundamental operation for users in CRNs to set up their communication link on a common channel. Existing studies on channel rendezvous suffer from unacceptable long delay and high energy consumption when applied to such scenarios. In this paper, we propose a two-dimensional heterogeneous rendezvous (2D-HR) protocol which can support multi-wideband CRNs (MWB-CRNs) with a significantly reduced rendezvous delay and energy consumption for various rendezvous scenarios, such as the pair-wise rendezvous, any-wise rendezvous, and multi-wise rendezvous. The proposed design also performs better than existing efforts even when dealing with traditional single-band rendezvous. The merits of 2D-HR are proved theoretically and validated against extensive simulations. To the best of our knowledge, this is the first work that addresses heterogeneous rendezvous in MWB-CRNs.
【Keywords】: Delays; Algorithm design and analysis; Wideband; Energy consumption; Conferences; Protocols; Cognitive radio
【Paper Link】 【Pages】:1-9
【Authors】: Changhee Joo ; Ness B. Shroff
【Abstract】: We consider a cognitive radio network, where primary users have priority over the spectrum resources, and secondary users can exploit the unused resources through channel sensing. Due to sensing inaccuracy, the secondary traffic may obstruct the primary traffic. A penalty for collision has been used to protect the primary traffic, which is often designed to provide a fixed per-collision compensation or to restrict the collision rate at an acceptable level. In this work, we develop a framework that can protect the primary traffic taking into account the Quality of Service of the primary traffic. In particular, we pay attention to the delay performance, which is determined not only by the collision rate but also by the amount of traffic in both networks. We design a novel model with coupled queues, and successfully incorporate dynamic interactions between the two systems through the standard optimization problem. We also consider the practical requirement of no direct sharing of the system information between the two networks, and develop a close-to-optimal solution of per-collision price and channel sensing under mild assumptions. We evaluate its performance through simulations.
【Keywords】: Sensors; Quality of service; Cognitive radio; Signal to noise ratio; Interference; Throughput; Load management
【Paper Link】 【Pages】:1-9
【Authors】: Amr Abdelfattah ; Naceur Malouch
【Abstract】: In order to cope with the exponential growth of mobile traffic, mobile operators need to access more spectrum resources. LTE in unlicensed spectrum (LTE-U) has been proposed to extend the usual operation of LTE in licensed spectrum to cover also unlicensed spectrum. However, this extension poses significant challenges especially regarding the coexistence between LTE-U and legacy systems like Wi-Fi. In case of LTE-U adopts Time-Division Multiplexing (TDM) schemes to share the spectrum with Wi-Fi, we expect performance degradations of Wi-Fi networks. In this paper, we quantify the impact of TDM schemes on Wi-Fi performance in a coexistence scenario. We provide detailed analytical models using two different random walk approaches to compute the probability of collision faced by Wi-Fi stations and their throughput performance. Besides, we derive the performance results using an exponential approximation which shows its insufficiency to capture the exact behavior. We implement the coexistence in the NS3 simulator and we show that the models estimate accurately the collision probability and the throughput experienced by Wi-Fi. The models are then used to study and compare different coexistence schemes showing for instance that the Wi-Fi frame size has a non-negligible impact on the performance of Wi-Fi users.
【Keywords】: LTE-U; CSAT; Wi-Fi; 5G; Mobile Communication; Collision Probability; Performance Evaluation; Simulation
【Paper Link】 【Pages】:1-9
【Authors】: Yanyuan Qin ; Ruofan Jin ; Shuai Hao ; Krishna R. Pattipati ; Feng Qian ; Subhabrata Sen ; Bing Wang ; Chaoqun Yue
【Abstract】: Adaptive bitrate streaming (ABR) has become the de facto technique for video streaming over the Internet. Despite a flurry of techniques, achieving high quality ABR streaming over cellular networks remains a tremendous challenge. ABR streaming can be naturally modeled as a feedback control problem. There has been some initial work on using PID, a widely used feedback control technique, for ABR streaming. Existing studies, however, either use PID control directly without fully considering the special requirements of ABR streaming, leading to suboptimal results, or conclude that PID is not a suitable approach. In this paper, we take a fresh look at PID-based control for ABR streaming. We design a framework called PIA that strategically leverages PID control concepts and incorporates several novel strategies to account for the various requirements of ABR streaming. We evaluate PIA using simulation based on real LTE network traces, as well as using real DASH implementation. The results demonstrate that PIA outperforms state-of-the-art schemes in providing high average bitrate with significantly lower bitrate changes (reduction up to 40%) and stalls (reduction up to 85%), while incurring very small runtime overhead.
【Keywords】: Streaming media; Bit rate; PI control; PD control; Bandwidth; Cellular networks
【Paper Link】 【Pages】:1-9
【Authors】: Tong Zhang ; Fengyuan Ren ; Wenxue Cheng ; Xiaohui Luo ; Ran Shu ; Xiaolan Liu
【Abstract】: Recently, HTTP-based adaptive video streaming has been widely adopted in the Internet. Up to now, HTTP-based adaptive video streaming is standardized as Dynamic Adaptive Streaming over HTTP (DASH), where a client-side video player can dynamically pick the bitrate level according to the perceived network conditions. Actually, not only the available bandwidth is varying, but also the chunk sizes in the same bitrate level significantly fluctuate, which also influences the bitrate adaptation. However, existing bitrate adaptation algorithms do not accurately involve the chunk size variation, leading to performance losses. In this paper, we theoretically analyze the influence of chunk size variation on bitrate adaptation performance. Based on DASH system features, we build a general model describing the playback buffer evolution. Applying stochastic theories, we respectively analyze the influence of the chunk size variation on rebuffering probability and average bitrate level. Furthermore, based on theoretical insights, we provide several recommendations for algorithm designing and rate encoding, and also propose a simple bitrate adaptation algorithm. Extensive simulations verify our insights as well as the efficiency of the proposed recommendations and algorithm.
【Keywords】: Chunk Size; bitrate adaptation; rebuffering; average video rate; DASH
【Paper Link】 【Pages】:1-9
【Authors】: Cong Zhang ; Qiyun He ; Jiangchuan Liu ; Zhi Wang
【Abstract】: Recent years have witnessed an explosion of gamecasting applications in the market, in which game players (or gamers in short) broadcast their game scenes in real-time. Such pioneer applications as YouTube Gaming, Twitch, and Mobcrush have attracted a massive number of online broadcasters, and each of them can attract hundreds or thousands of fellow viewers. The growing number however has created significant challenges to the network and end-devices, particularly considering bandwidth- and battery-limited smartphones or tablets are becoming dominating for both gamers and viewers. Yet the unique touch operations of the mobile interface offer opportunities, too. In this paper, our crowdsourced measurement reveals that strong associations exist between the gamers' touch interactions and the viewers' gazing patterns. Motivated by this, we present a novel interaction-aware optimization framework to improve the energy utilization and stream quality for mobile gamecasting (MGC). Our framework incorporates a touch-assisted prediction module to extract association rules for gazing pattern prediction and a tile-based optimization module to utilize energy on mobile devices efficiently. Trace-driven simulations illustrate the effectiveness of our framework in terms of energy consumption and streaming quality. Our user study experiments also demonstrate much improved (3%-13%) quality satisfaction than the state-of-the-art solution with similar network resources.
【Keywords】: Games; Optimization; Land mobile radio; Smart phones; YouTube
【Paper Link】 【Pages】:1-9
【Authors】: Khaled M. Diab ; Mohamed Hefeeda
【Abstract】: Multiview videos offer unprecedented experience by allowing users to explore scenes from different angles and perspectives. Thus, such videos have been gaining substantial interest from major content providers such as Google and Facebook. Adaptive streaming of multiview videos is, however, challenging because of the Internet dynamics and the diversity of user interests and network conditions. To address this challenge, we propose a novel rate adaptation algorithm for multiview videos (called MASH). Streaming multiview videos is more user centric than single-view videos, because it heavily depends on how users interact with the different views. To efficiently support this interactivity, MASH constructs probabilistic view switching models that capture the switching behavior of the user in the current session, as well as the aggregate switching behavior across all previous sessions of the same video. MASH then utilizes these models to dynamically assign relative importance to different views. Furthermore, MASH uses a new buffer-based approach to request video segments of various views at different qualities, such that the quality of the streamed videos is maximized while the network bandwidth is not wasted. We have implemented a multiview video player and integrated MASH in it. We compare MASH versus the state-of-the-art algorithm used by YouTube for streaming multiview videos. Our experimental results show that MASH can produce much higher and smoother quality than the algorithm used by YouTube, while it is more efficient in using the network bandwidth. In addition, we conduct large-scale experiments with up to 100 concurrent multiview streaming sessions, and we show that MASH maintains fairness across competing sessions, and it does not overload the streaming server.
【Keywords】: Streaming media; Multi-stage noise shaping; Switches; Adaptation models; Computational modeling; Heuristic algorithms; YouTube
【Paper Link】 【Pages】:1-9
【Authors】: Ian D. Markwood ; Yao Liu ; Kevin A. Kwiat ; Charles A. Kamhoua
【Abstract】: The power flow model for DC power grids has been used theoretically to launch false data injection attacks (FDIAs) against state estimation. We recognize FDIAs are just one possible attack using the power flow model and that the grid topology information within the model implies its discovery may also facilitate topology-based attacks. We show attackers can derive the power flow model, and thus the topology also. Indeed, with incomplete data, attackers can accurately reconstruct regions of the model, or topology, all that is necessary to launch an attack. We also illustrate how to cause such attackers to derive instead a convincing fake model by camouflaging the real model. Consequently, no sensitive information will leak, so attacks based on this fake model will be ineffective, rather alerting grid administrators to the attacker's efforts. Using five test cases included in the MATLAB power flow analysis tool MATPOWER, ranging from 9 to 300 buses, an average 67.0% of the topology may be derived with a 69.1% model accuracy. Lastly, we find reconstructions of small portions of the model sufficient for performing FDIAs with 75% success, and that camouflage prevents 93% of them in all but the 9-bus case.
【Keywords】: Mathematical model; Data models; Topology; Computational modeling; Meters; Admittance; Power grids
【Paper Link】 【Pages】:1-9
【Authors】: Zhuo Lu ; Mingkui Wei ; Xiang Lu
【Abstract】: In the smart grid, computer networks (i.e., the cyber domain) are built upon physical infrastructures (i.e., the physical domain) to facilitate advanced functionalities that were considered not possible in legacy systems. It is envisioned that such a cyber-physical paradigm enables intelligent, collaborative controls to prevent faults from propagating along large-scale infrastructures, which is a primary cause for massive blackouts (e.g., Northeast blackout of 2003). Despite this promising vision, how effective cyber and physical interactions are against fault propagation is not yet fully investigated. In this paper, we use analysis and system-level simulations to characterize such interactions during load shedding, which is a process to stop fault propagation by shedding a computed amount of loads based on collaborative communication. Specifically, we model faults happening in the physical domain as a counting process, with each count triggering a load shedding action on the fly in the cyber domain. We show that although global load shedding design is considered optimal by globally coordinating shedding actions in power engineering, its induced failure probability (defined as the one that at least a given number of power lines fail) is scalable to the delay performance and the system size in the cyber domain, thus less likely to stop fault propagation in large systems than local shedding design that sheds loads within a limited system scope. Our study demonstrates that a joint view on cyber and physical factors is essential for failure prevention design in the smart grid.
【Keywords】: Smart grid; load shedding; fault propagation; cascading failure; failure prevention; modeling and simulations
【Paper Link】 【Pages】:1-9
【Authors】: Xin Lou ; Rui Tan ; David K. Y. Yau ; Peng Cheng
【Abstract】: Increasing dynamics of electrical loads presents uncertainty and hence new challenges for power grid controls and optimization. In economic dispatch control (EDC) for minimizing generation cost, demand reporting by customers is a promising approach for managing the uncertainty, but it raises important privacy concerns. Adding random noise to aggregate queries of demand reports can provide differential privacy (DP) for the individual customers. But the noisy query results can adversely impact the EDC's optimality. In this paper, we analyze the privacy cost in demand reporting in terms of how DP-induced noise will increase the total generation cost. Our analysis shows that the noise amounts for different customers are intricately coupled with one another in determining the total cost. In view of the coupling, we apply the principle of Shapley value to attribute fair shares of the total cost to the power grid buses. For efficient sharing of the privacy cost, in a manner scalable to large power systems with many buses, we additionally propose heuristic algorithms to approximate the Shapley value. Trace-driven simulations based on a 5-bus power system model validate our analysis and illustrate the performance of the proposed cost sharing algorithms.
【Keywords】: Privacy; Power grids; Aggregates; Uncertainty; Generators; Power system dynamics
【Paper Link】 【Pages】:1-9
【Authors】: Ali Sehati ; Majid Ghaderi
【Abstract】: To reduce the energy consumption of a smartphone, multiple data transfer requests from applications can be bundled together and granted at once in order to reduce the time the radio interface is on. The side effect of bundling is the increased delay experienced by mobile applications. While several bundling algorithms have been proposed in the literature, a general and systematic solution to balance the energy-delay tradeoff is missing. In this paper, we formulate bundling as a cost minimization problem, in which the tradeoff between energy and delay is captured by a cost function. We then propose an online algorithm for minimizing the bundling cost and show that the algorithm is 4-competitive with respect to the optimal offline algorithm that knows the entire sequence of data transfer requests a priori. We evaluate the performance of the proposed algorithm and the accuracy of our results in a range of realistic scenarios using both model-driven simulations and real experiments on a smartphone. Our results show that depending on the delay tolerance level of a user, energy savings ranging from zero (delay intolerant) to about 100% (delay tolerant) can be achieved using our algorithm.
【Keywords】: Delays; Algorithm design and analysis; Data transfer; Smart phones; Energy consumption; Mobile communication; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Lorenzo De Carli ; Ruben Torres ; Gaspar Modelo-Howard ; Alok Tongaonkar ; Somesh Jha
【Abstract】: Network protocol reverse engineering of botnet command and control (C&C) is a challenging task, which requires various manual steps and a significant amount of domain knowledge. Furthermore, most of today's C&C protocols are encrypted, which prevents any analysis on the traffic without first discovering the encryption algorithm and key. To address these challenges, we present an end-to-end system for automatically discovering the encryption algorithm and keys, generating a protocol specification for the C&C traffic, and crafting effective network signatures. In order to infer the encryption algorithm and key, we enhance state-of-the-art techniques to extract this information using lightweight binary analysis. In order to generate protocol specifications we infer field types purely by analyzing network traffic. We evaluate our approach on three prominent malware families: Sality, ZeroAccess and Ramnit. Our results are encouraging: the approach decrypts all three protocols, detects 97% of fields whose semantics are supported, and infers specifications that correctly align with real protocol specifications.
【Keywords】: Encryption; Protocols; Malware; Ciphers; Payloads
【Paper Link】 【Pages】:1-9
【Authors】: Antonios A. Chariton ; Eirini Degkleri ; Panagiotis Papadopoulos ; Panagiotis Ilia ; Evangelos P. Markatos
【Abstract】: Trust in SSL-based communications is provided by Certificate Authorities (CAs) in the form of signed certificates. Checking the validity of a certificate involves three steps: (i) checking its expiration date, (ii) verifying its signature, and (iii) ensuring that it is not revoked. Currently, such certificate revocation checks are done either via Certificate Revocation Lists (CRLs) or Online Certificate Status Protocol (OCSP) servers. Unfortunately, despite the existence of these revocation checks, sophisticated cyber-attackers, may trick web browsers to trust a revoked certificate, believing that it is still valid. Consequently, the web browser will communicate (over TLS) with web servers controlled by cyber-attackers. Although frequently updated, nonced, and timestamped certificates may reduce the frequency and impact of such cyber-attacks, they impose a very large overhead to the CAs and OCSP servers, which now need to timestamp and sign on a regular basis all the responses, for every certificate they have issued, resulting in a very high overhead. To mitigate this overhead and provide a solution to the described cyber-attacks, we present CCSP: a new approach to provide timely information regarding the status of certificates, which capitalizes on a newly introduced notion called signed collections. In this paper, we present the design, preliminary implementation, and evaluation of CCSP in general, and signed collections in particular. Our preliminary results suggest that CCSP (i) reduces space requirements by more than an order of magnitude, (ii) lowers the number of signatures required by 6 orders of magnitude compared to OCSP-based methods, and (iii) adds only a few milliseconds of overhead in the overall user latency.
【Keywords】: Browsers; Web servers; Protocols; Public key; Conferences; Receivers
【Paper Link】 【Pages】:1-9
【Authors】: Binghui Wang ; Le Zhang ; Neil Zhenqiang Gong
【Abstract】: Detecting Sybils in online social networks (OSNs) is a fundamental security research problem as adversaries can leverage Sybils to perform various malicious activities. Structure-based methods have been shown to be promising at detecting Sybils. Existing structure-based methods can be classified into two categories: Random Walk (RW)-based methods and Loop Belief Propagation (LBP)-based methods. RW-based methods cannot leverage labeled Sybils and labeled benign users simultaneously, which limits their detection accuracy, and they are not robust to noisy labels. LBP-based methods are not scalable, and they cannot guarantee convergence. In this work, we propose SybilSCAR, a new structure-based method to perform Sybil detection in OSNs. SybilSCAR maintains the advantages of existing methods while overcoming their limitations. Specifically, SybilSCAR is Scalable, Convergent, Accurate, and Robust to label noises. We first propose a framework to unify RW-based and LBP-based methods. Under our framework, these methods can be viewed as iteratively applying a (different) local rule to every user, which propagates label information among a social graph. Second, we design a new local rule, which SybilSCAR iteratively applies to every user to detect Sybils. We compare SybilSCAR with a state-of-the-art RW-based method and a state-of-the-art LBP-based method, using both synthetic Sybils and large-scale social network datasets with real Sybils. Our results demonstrate that SybilSCAR is more accurate and more robust to label noise than the compared state-of-the-art RW-based method, and that SybilSCAR is orders of magnitude more scalable than the state-of-the-art LBP-based method and is guaranteed to converge. To facilitate research on Sybil detection, we have made our implementation of SybilSCAR publicly available on our webpages.
【Keywords】: Robustness; Image edge detection; Training; Belief propagation; Convergence; Twitter
【Paper Link】 【Pages】:1-9
【Authors】: Shouling Ji ; Shukun Yang ; Anupam Das ; Xin Hu ; Raheem A. Beyah
【Abstract】: In this paper, we study the correlation between passwords across different datasets which quantitatively explains the success of existing training-based password cracking techniques. We also study the correlation between a user's password and his/her social profile. This enabled us to develop the first social profile-aware password strength meter, namely SociaLShield. Our quantification techniques and SocialShield have meaningful implications to system administrators, users, and researchers, e.g., helping them quantitatively understand the threats posed by a password leakage incident, defending against emerging profile-based password attacks, and facilitating the research of countermeasures against existing and newly developed training-based password attacks. We validate our proposed quantification techniques and SocialShield through extensive experiments by leveraging real-world leaked passwords. Experimental results demonstrate that our quantification techniques are accurate in measuring correlation among different leaked datasets and that although SocialShield is light-weight, it is effective in defending against profile-based password attacks.
【Keywords】: Correlation; Markov processes; Meters; Measurement; Security; Standards; LinkedIn
【Paper Link】 【Pages】:1-9
【Authors】: Alan Kuhnle ; Tianyi Pan ; Md Abdul Alim ; My T. Thai
【Abstract】: We consider the Threshold Activation Problem (TAP): given social network G and positive threshold T, find a minimum-size seed set A that can trigger expected activation of at least T. We introduce the first scalable, parallelizable algorithm with performance guarantee for TAP suitable for datasets with millions of nodes and edges; we exploit the bicriteria nature of solutions to TAP to allow the user to control the running time versus accuracy of our algorithm through a parameter α ϵ (0, 1): given η > 0, with probability 1 - η our algorithm returns a solution A with expected activation greater than T - 2αT, and the size of the solution A is within factor 1-h 4α/T + log(T) of the optimal size. The algorithm runs in time O (α-2 log (n/η) (n + m)|A|), where n, m, refer to the number of nodes, edges in the network. The performance guarantee holds for the general triggering model of internal influence and also incorporates external influence, provided a certain condition is met on the cost-effectivity of seed selection.
【Keywords】: Social network services; Integrated circuit modeling; Computational modeling; TV; Conferences; Context modeling
【Paper Link】 【Pages】:1-9
【Authors】: Xiang Li ; J. David Smith ; Thang N. Dinh ; My T. Thai
【Abstract】: One of the most central problems in viral marketing is Influence Maximization (IM), which finds a set of k seed users who can influence the maximum number of users in online social networks. Unfortunately, all existing algorithms to IM, including the state of the art SSA and IMM, have an approximation ratio of (1 - 1/e - ϵ). Recently, a generalization of IM, Cost-aware Target Viral Marketing (CTVM), asks for the most cost-effective users to influence the most relevant users, has been introduced. The current best algorithm for CTVM has an approximation ratio of (1 - 1/√e - ϵ). In this paper, we study the CTVM problem, aiming to optimally solve the problem. We first highlight that using a traditional two stage stochastic programming to exactly solve CTVM is not possible because of scalability. We then propose an almost exact algorithm TIPTOP, which has an approximation ratio of (1 - ϵ). This result significantly improves the current best solutions to both IM and CTVM. At the heart of TIPTOP lies an innovative technique that reduces the number of samples as much as possible. This allows us to exactly solve CTVM on a much smaller space of generated samples using Integer Programming. While obtaining an almost exact solution, TIPTOP is very scalable, running on billion-scale networks such as Twitter under three hours. Furthermore, TIPTOP lends a tool for researchers to benchmark their solutions against the optimal one in large-scale networks, which is currently not available.
【Keywords】: Viral Marketing; Influence Maximization; Algorithms; Online Social Networks; Optimization
【Paper Link】 【Pages】:1-8
【Authors】: Zhao Zhang ; Yishuo Shi ; James Willson ; Ding-Zhu Du ; Guangmo Tong
【Abstract】: One model for viral marketing is the positive influence. In this model, an inactive node is changed into active if and only if at least half of its neighbors are already in active state. The positive influence model can be viewed as a special case of a general threshold model, in which the threshold function at each node has value one if at least a certain fraction of neighbors are in active state, and value 0 otherwise. This function can be proved to be monotonically increasing and nonsubmodular for any predefined fraction. Therefore, given a seed set, the number of influenced nodes is not submodular with respect to the size of the seed set. This fact makes those optimization problems related with positive influence very hard, including the minimum partial positive influence seeding problem: Given a social network G = (V, E) and a number 0 <; p <; 1, find a minimum seed set S which can positively influence at least p|V| nodes. In this paper, we present an O ((log n)2 H ([pn]))-approximation algorithm for the minimum partial positive influence seeding problem, where n is the number of nodes, and H(·) is the Harmonic number.
【Keywords】: viral marketing; partial positive-influence seeding problem; approximation algorithm
【Paper Link】 【Pages】:1-9
【Authors】: Chul-Ho Lee ; Xin Xu ; Do Young Eun
【Abstract】: We study how the so-called Rao-Blackwellization, which is a variance reduction technique via “conditioning” for Monte Carlo methods, can be judiciously applied for graph sampling through neighborhood exploration. Despite its popularity for Monte Carlo methods, it is little known for Markov chain Monte Carlo methods and has never been discussed for random walk-based graph sampling. We first propose two forms of Rao-Blackwellization that can be used as a swap-in replacement for virtually all (reversible) random-walk graph sampling methods, and prove that the `Rao-Blackwellized' estimators reduce the (asymptotic) variances of their original estimators yet maintain their inherent unbiasedness. The variance reduction can translate into lowering the number of samples required to achieve a desired sampling accuracy. However, the sampling cost for neighborhood exploration, if required, may outweigh such improvement, even leading to higher total amortized cost. Considering this, we provide a generalization of Rao-Blackwellization, which allows one to choose a suitable extent of obtaining Rao-Blackwellized samples in order to achieve a right balance between sampling cost and accuracy. We finally provide simulation results via real-world datasets that confirm our theoretical findings.
【Keywords】: Monte Carlo methods; Sampling methods; Markov processes; Conferences; Random variables; Simulation; Social network services
【Paper Link】 【Pages】:1-9
【Authors】: Yunlong Wu ; Bo Zhang ; Shaoshi Yang ; Xiaodong Yi ; Xuejun Yang
【Abstract】: In this paper, we consider a surveillance scenario where a team of sensing robots survey a sensitive area and transmit the monitored data to a remote base station through a mobile relay. In this scenario, it is challenging to autonomously adjust the position of the mobile relay for the sake of minimizing the total communication-motion energy consumption of the system, while maintaining the communication quality of the mobile sensing robots. We first derive the asymptotically optimal transmit powers of the mobile relay and of the sensing robots according to the predefined end-to-end packet error rate (PER) requirement. Then, we propose a joint communication-motion planning (JCMP) method for minimizing the total communication-motion energy consumption in both: single- and multi-sensing-robot scenarios, where the trajectories of the sensing robots are rigorously defined. We further consider the scenario where the sensing robots' trajectories are not fixed but can be optimized in restrained areas. The effectiveness of the proposed JCMP is verified by analysis and numerical results for different system configurations, showing that a substantial energy-efficiency improvement may be achieved in comparison with the benchmark that only optimizes the communication energy consumption.
【Keywords】: Joint communication-motion planning; energy-efficient relays; optimization methods; robots; surveillance
【Paper Link】 【Pages】:1-9
【Authors】: Tuo Shi ; Siyao Cheng ; Jianzhong Li ; Zhipeng Cai
【Abstract】: Currently, the limitation of battery has become a serious obstacle for the development of Internet of things (IoTs). Therefore, a new network architecture, named as battery-free network, were proposed. In a typical battery-free network, the battery-free nodes are equipped with any battery and can only gain energy from the environment. Such network extremely expands the scope of the IoT applications, however, it also brings many troubles for some network operations, e.g. data collection, since the energy of each node is quite small. Considering that the Connected Dominating Sets (CDSs) are commonly used to support data collection and network communication in wireless networks, and thus we will also investigate the CDS construction problem in battery-free networks. In this paper, the problem of constructing CDS in a battery-free network is formally defined, and we prove that it is NP-Complete. Thus, four approximation algorithms were proposed to deal with the snapshot, continuous and time-window based CDS construction requirements, respectively. Finally, the extensive experiments were carried out and the results verify that the proposed algorithms have high performance in term of accuracy and efficiency.
【Keywords】: Sensors; Batteries; Wireless sensor networks; Bridges; Monitoring; Windows; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Yi Gao ; Wei Dong ; Xiaoyu Zhang ; Wenbin Wu
【Abstract】: Most sensor networks employ dynamic routing protocols so that the routing topology can be dynamically optimized with environmental changes. The routing behaviors can be quite complex with increasing network scale and environmental dynamics. Knowledge on the routing path of each packet is certainly a great help in understanding the complex routing behaviors, allowing effective performance diagnosis and efficient network management. We propose PAT, a universal sensornet path tracing approach. PAT includes an intelligent path encoding scheme that allows efficient decoding at the PC side. To make PAT more scalable, we propose techniques to accurately estimate the degree information by exploiting timing information, allowing more compact path encoding. Moreover, we employ subpath concatenation to infer excessively long paths with a high recovery probability. We carefully evaluate PAT's performance using testbed experiments and and extensive simulations with up to 4,000 nodes. Results show that PAT significantly outperforms existing approaches.
【Keywords】: Routing; Topology; Network topology; Wireless sensor networks; Robot sensing systems; Encoding; Monitoring
【Paper Link】 【Pages】:1-9
【Authors】: Fujuan Guo ; Baofeng Zhou ; Mehmet C. Vuran
【Abstract】: System-level timing inconsistency and wireless communication delays are the main uncertainties of existing synchronization mechanisms for wireless sensor networks. Existing solutions mainly rely on timestamp exchanges to estimate clock offset and skew, which results in frequent synchronization, high overhead, and high energy consumption to maintain a well-synchronized network. This paper introduces a novel clock syntonization approach to estimate the differences between clock frequencies of network nodes without the need for timestamp exchanges. The carrier frequency offset (CFO) assisted syntonization (CFOSynt) utilizes the carrier information obtained from wireless packet transmission for clock skew compensation. The key idea of CFOSynt is that, in any wireless communication system, where carrier modulation is employed, carrier frequency delivers information about the transmitter RF clock. Consequently, clock frequency offset between a pair of sensor nodes will result in a carrier frequency offset detected by the receiver node. By leveraging the CFO information, CFOSynt can estimate the system clock skew based on digital counter theory. Extensive experiments and numerical analysis have been demonstrated to evaluate clock skew estimation.
【Keywords】: Clocks; Synchronization; Wireless sensor networks; Estimation; Wireless communication; Radio frequency; Delays
【Paper Link】 【Pages】:1-9
【Authors】: Xiaojian Lin ; Shaowei Wang
【Abstract】: Cloud radio access network (C-RAN) is deemed as a promising architecture to meet the exponentially increasing traffic demand in mobile networks, where baseband processing is separated from remote radio heads (RRHs) and performed in a centralized baseband unit (BBU) pool. However, the densely deployed RRHs, as well as the passive optical network which provides high capacity backhauls between the RRHs and the BBU pool, consume a large amount of energy. In this paper, we propose efficient RRH switching schemes to achieve a tradeoff between the system energy saving and the load balance among the RRHs in the C-RAN. We first develop an approximation algorithm to address the intractable user association problem for a given set of RRHs, based on which we introduce efficient local search algorithms to perform RRH selection procedure, which can reduce the load fairness index of the C-RAN by controlling the active/inactive state of each RRH. We also discuss the handover signalling overhead issue and introduce an adaptive trigger mechanism to avoid switching on/off too many RRHs simultaneously so as to keep the signalling overhead of the C-RAN below an acceptable level. Numerical results demonstrate that the proposed RRH switching schemes can improve the system performance of the C-RAN significantly. Moreover, our proposal sheds light on how to design effective and efficient handover schemes for next generation mobile networks.
【Keywords】: Optical switches; Power demand; Interference; Indexes; Heuristic algorithms; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: David W. Griffith ; Aziza Ben Mosbah ; Richard Rouil
【Abstract】: Device-to-device (D2D) communications for Long Term Evolution (LTE) networks relies on a discovery process to enable User Equipment (UE) to determine which D2D applications and services are supported by neighboring UEs. This is especially important for groups of UEs that operate outside the coverage area of any base station. The amount of time required for discovery information to reach every UE in a group depends on the number of UEs in the group and the dimensions of the discovery resource pool associated with the Physical Sidelink Discovery Channel (PSDCH); an additional factor is the half-duplex property of current UEs. In this paper, we use a Markov chain to characterize the performance of Mode 2 direct discovery. The resulting analytical model gives the distribution of the time for a UE to discover all other UEs in its group. We validate the model using Monte Carlo and network simulations.
【Keywords】: Device-to-device communication; Markov processes; Mathematical model; Superluminescent diodes; Analytical models; Indexes; Long Term Evolution
【Paper Link】 【Pages】:1-9
【Authors】: Roberto Calvo-Palomino ; Domenico Giustiniano ; Vincent Lenders ; Aymen Fakhreddine
【Abstract】: Crowdsourced signal monitoring systems are gaining attention for capturing the wireless spectrum at large geographical scale. Yet, most of the current systems are still limited to simple power spectrum measurements reported by each sensor. Our objective is to enhance such systems with signal decoding capabilities performed in the backend while retaining the original vision of a low-cost and crowdsourced setup. We propose a distributed system architecture for collaborative radio signal monitoring and decoding that builds on $12 low-cost radio frequency (RF) frontends and embedded boards and that takes into consideration the limited network bandwidth from the sensors to the backend. We present a distributed time multiplexing mechanism to sample the spectrum in a coordinated fashion that exploits the similarity of the radio signal received by more than one RF frontend in the same radio coverage. We address the strict time synchronization required among sensors to reconstruct the signal from the samples they receive when in the same radio coverage. We study and implement techniques to identify and overcome errors in the timing information in the presence of noise sources and decode the data in the backend. We provide an evaluation based on simulations and on real signals transmitted by Long-Term Evolution (LTE) base stations. Our results show that we can reliably reconstruct and decode radio signals received by low-cost crowdsourced sensors.
【Keywords】: Decoding; Radio frequency; Synchronization; Monitoring; Bandwidth; Internet; Economic indicators
【Paper Link】 【Pages】:1-9
【Authors】: Ying Zhang ; Lei Deng ; Minghua Chen ; Peijian Wang
【Abstract】: We consider the scenario where a cloud service provider (CSP) operates multiple geo-distributed datacenters to provide Internet-scale service. Our objective is to minimize the total electricity and bandwidth cost by jointly optimizing electricity procurement from wholesale markets and geographical load balancing (GLB), i.e., dynamically routing workloads to locations with cheaper electricity. Under the ideal setting where exact values of market prices and workloads are given, this problem reduces to a simple LP and is easy to solve. However, under the realistic setting where only distributions of these variables are available, the problem unfolds into a non-convex infinite-dimensional one and is challenging to solve. Our main contribution is to develop an algorithm that is proven to solve the challenging problem optimally and efficiently, by exploring the full design space of strategic bidding. Trace-driven evaluations corroborate our theoretical results, demonstrate fast convergence of our algorithm, and show that it can reduce the cost for the CSP by up to 20% as compared to baseline alternatives. Our study highlights the intriguing role of uncertainty. While variability in workloads deteriorates the cost-saving performance of joint electricity procurement and GLB, counter-intuitively, variability in market prices can be exploited to achieve a cost reduction even larger than the setting without price variability.
【Keywords】: Real-time systems; Procurement; Standards; Load management; Electricity supply industry; Conferences; Uncertainty
【Paper Link】 【Pages】:1-9
【Authors】: Abdul Kabbani ; Milad Sharif
【Abstract】: Various topologies have been proposed in the context of high-performance computing and data center networking. Direct-connect topologies generally offer large capacity with high path diversity and are highly cost effective for general data center traffic patterns. However, the lack of simple yet efficient load balancing techniques for direct-connect fabrics has hindered these networks from gaining traction in data centers. This paper presents the design, implementation, and evaluation of Flicr, a light-weight host-based load balancing mechanism for direct-connect data centers. Flicr dynamically reroutes traffic through minimal and non-minimal routes to avoid congesting the fabric. This enables Flicr to efficiently minimize networking resource consumption while exploiting high path diversity in direct-connect fabrics to balance the network and gracefully handle link failures. Flicr requires only a simple kernel modification and is readily deployable in commodity data centers today. Our evaluations show that Flicr consistently outperforms other state-of-the-art load balancing designs, achieving 25-60% lower average flow completion time compared to adaptive routing. Flicr is also more robust against link failures and has 5-8 χ better performance relative to other schemes in the presence of link failures.
【Keywords】: Routing; Load management; Fabrics; Topology; Network topology; Robustness
【Paper Link】 【Pages】:1-9
【Authors】: Rui Zhu ; Di Niu ; Baochun Li ; Zongpeng Li
【Abstract】: Virtualized datacenter networks have been deployed in production platforms, e.g., Amazon VPC and VMware's NVP, to offer the flexibility of network management to enterprise-level clients. A common characteristic of these platforms is that they adopt software switches, such as Open vSwitch (OvS), instead of hardware switches to transfer data between VMs. Although group communication is common in enterprise applications, the unique characteristics of software switches have posed new challenges to the design of multicast protocols. How logical multicast can be optimally performed with software switches is still not well understood. In this paper, we observe that unlike hardware switches, the per-stream output rate in a software switch critically depends on the packet processing overhead of flow cloning. We study the optimal OvS multicast topology with or without the help of additional dedicated software switches called service nodes, and formulate the throughput maximization as a new class of degree-supervised combinatorial graph problems due to the presence of flow cloning costs. We propose a lineartime optimal solution that translates into simple forwarding rules installed at each software switch. Through emulation-based OvS profiling and extensive simulation results, we demonstrate that our proposed logical multicast solutions can significantly improve session throughput with the ability to handle load balancing and latency issues, as compared to the state-of-the-art in the literature.
【Keywords】: Software; Virtual machine monitors; Throughput; Topology; Hardware; Cloning; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Ziyang Li ; Wei Bai ; Kai Chen ; Dongsu Han ; Yiming Zhang ; Dongsheng Li ; Hongfang Yu
【Abstract】: Flow completion times (FCTs) are critical for many cloud applications. To minimize the average FCT, recent transport designs, such as pFabric, PASE, and PIAS, approximate the Shortest Remaining Time First (SRTF) scheduling. A common, implicit assumption of these solutions is that the remaining time is only determined by the remaining flow size. However, this assumption does not hold in many real-world scenarios where applications generate data at diverse rates that are smaller than the network capacity. In this paper, we look into this issue from system perspective and find that the operating system (OS) kernel can be exploited to better estimate the remaining time of a flow. In particular, we use the rate of copying data from user space to kernel space to measure the data generation rate. We design RAX, a rate aware flow scheduling method, that calculates the remaining time of a flow more accurately, based on not only the flow size but also the data generation rate. We have implemented a RAX prototype in Linux kernel and evaluated it through testbed experiments and ns-2 simulations. Our testbed results show that RAX reduces FCT by up to 14.9%/41.8% and 7.8%/22.9% over DCTCP and PIAS for all/medium flows respectively.
【Keywords】: Kernel; Servers; Schedules; Throughput; Conferences; Hard disks
【Paper Link】 【Pages】:1-9
【Abstract】: Recent diversification of mobile computing devices allows a mobile user to own multiple types of devices for different application scenarios, but also results in various restrictions on the performance and usability of these devices. A viable solution to such restriction is to incorporate and interconnect mobile devices towards a personal mobile cloud where these devices can complement each other via cooperative resource sharing, but is challenging due to the heterogeneity of mobile devices in both hardware and software aspects. In this paper, we propose a novel design of resource sharing framework to address these challenges and generically interconnect heterogeneous mobile devices. Our basic idea is to mask the hardware and software heterogeneity in mobile systems by exploiting the existing mobile OS services as the interface of resource sharing, and further develop the resource sharing framework as a middleware in the mobile OS. We have implemented our design over various mobile platforms with diverse characteristics and resource limits, and demonstrated that our design can efficiently support generic resource sharing among heterogeneous mobile devices without incurring significant system overhead or requiring individual system modification.
【Keywords】: Mobile communication; Hardware; Resource management; Mobile handsets; Mobile applications; Androids; Humanoid robots
【Paper Link】 【Pages】:1-9
【Authors】: Liuhua Chen ; Haiying Shen
【Abstract】: Previous resource provisioning strategies in cloud datacenters allocate physical resources to virtual machines (VMs) based on the predicted resource utilization pattern of VMs. The pattern for VMs of a job is usually derived from historical utilizations of multiple VMs of the job. We observed that these utilization curves are usually misaligned in time, which would lead to resource over-prediction and hence over-provisioning. Since this resource utilization misalignment problem has not been revealed and studied before, in this paper, we study the VM resource utilization from public datacenter traces to verify the existence of the utilization misalignments. Then, to reduce resource over-provisioning, we propose three VM resource utilization pattern refinement algorithms to improve the original generated pattern by lowering the cap of the pattern, reducing cap provision duration and varying the minimum value of the pattern. These algorithms can be used in any resource provisioning strategy that considers predicted resource utilizations of VMs of a job. We then adopt these refinement algorithms in an initial VM allocation mechanism and test them in trace-driven experiments and real-world cluster experiments. The experimental results show that each improved mechanism can increase resource efficiency up to 74%, and reduce the number of PMs needed to satisfy tenant requests up to 47% while conforming the SLO requirement.
【Keywords】: Resource management; Google; Correlation; Prediction algorithms; Clustering algorithms; Extraterrestrial measurements
【Paper Link】 【Pages】:1-9
【Authors】: Jaya Prakash Champati ; Ben Liang
【Abstract】: We revisit the problem of assigning n jobs to m machines/servers. We study this problem under more general settings, which capture important aspects of applications that arise in networking and information systems. In particular, we consider jobs that have placement constraints and machines that are heterogeneous. The cost incurred at a machine is given by any general convex function on the number of jobs assigned to it. We aim to minimize the sum cost and the maximum differential cost. Through a network-flow equivalence transformation, we observe how these two objectives are fundamentally related, showing that sum-cost minimization implies maximum-differential-cost minimization. We propose an efficient algorithm termed Maximum Edge-Cost Cycle Cancelling (MEC3) to solve the sum-cost minimization problem with O(n2 m2) time complexity. Furthermore, for applications where only the maximum differential cost is of concern, we further improve the efficiency of MEC3 by proposing an early stop condition. We implement MEC3 and two other algorithms from the literature. Using benchmark input instances, we show that MEC3 has substantially lower run time than the other algorithms.
【Keywords】: Minimization; Cost function; Time complexity; Conferences; Benchmark testing; Algorithm design and analysis; Information systems
【Paper Link】 【Pages】:1-9
【Authors】: Wenchao Jiang ; Zhimeng Yin ; Song Mim Kim ; Tian He
【Abstract】: Cross-technology communication (CTC) techniques are introduced in recent literatures to explore the opportunities of collaboration between heterogeneous wireless technologies, such as WiFi and ZigBee. Their applications include context-aware services and global channel coordination. However, state-of-the-art CTC schemes either suffer from channel inefficiency, low throughput, or disruption to existing networks. This paper presents the CTC via data packets (DCTC), which takes advantage of abundant existing data packets to construct recognizable energy patterns. DCTC features (i) a significant enhancement in CTC throughput while (ii) keeping transparent to upper layer protocols and applications. Our design also features advanced functions including multiplexing to support concurrent transmissions of multiple DCTC senders and adaptive rate control according to the traffic volume. Testbed implementations across WiFi and ZigBee platforms demonstrate reliable bidirectional communication of over 95% in accuracy while achieving throughput 2.3x of the state of the art. Meanwhile, experiment results show that DCTC has little and bounded impact on the delay and throughput of original data traffic.
【Keywords】: Throughput; Wireless fidelity; ZigBee; Delays; Wireless communication; Protocols; Wireless sensor networks
【Paper Link】 【Pages】:1-9
【Authors】: Jie Ren ; Ling Gao ; Hai Wang ; Zheng Wang
【Abstract】: Web browsing is an activity that billions of mobile users perform on a daily basis. Battery life is a primary concern to many mobile users who often find their phone has died at most inconvenient times. The heterogeneous multi-core architecture is a solution for energy-efficient processing. However, the current mobile web browsers rely on the operating system to exploit the underlying hardware, which has no knowledge of individual web contents and often leads to poor energy efficiency. This paper describes an automatic approach to render mobile web workloads for performance and energy efficiency. It achieves this by developing a machine learning based approach to predict which processor to use to run the web rendering engine and at what frequencies the processors should operate. Our predictor learns offline from a set of training web workloads. The built predictor is then integrated into the browser to predict the optimal processor configuration at runtime, taking into account the web workload characteristics and the optimisation goal: whether it is load time, energy consumption or a trade-off between them. We evaluate our approach on a representative ARM big.LITTLE mobile architecture using the hottest 500 webpages. Our approach achieves 80% of the performance delivered by an ideal predictor. We obtain, on average, 45%, 63.5% and 81% improvement respectively for load time, energy consumption and the energy delay product, when compared to the Linux heterogeneous multi-processing scheduler.
【Keywords】: Mobile Web Browsing; Energy Optimisation; big.LITTLE; Mobile Workloads
【Paper Link】 【Pages】:1-9
【Authors】: Qingjun Xiao ; You Zhou ; Shigang Chen
【Abstract】: Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just a single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internetscale database. To solve the problem, we propose an algorithm named HLL-TailCut+, which implements the estimation standard error 1.0/√m using the memory units of three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.
【Keywords】: Registers; Estimation; Radiation detectors; Memory management; Google; Algorithm design and analysis; Monitoring
【Paper Link】 【Pages】:1-9
【Authors】: Angelo Fumo ; Marco Fiore ; Razvan Stanica
【Abstract】: Mobile traffic data collected by network operators is a rich source of information about human habits, and its analysis provides insights relevant to many fields, including urbanism, transportation, sociology and networking. In this paper, we present an original approach to infer both spatial and temporal structures hidden in the mobile demand, via a first-time tailoring of Exploratory Factor Analysis (EFA) techniques to the context of mobile traffic datasets. Casting our approach to the time or space dimensions of such datasets allows solving different problems in mobile traffic analysis, i.e., network activity profiling and land use detection, respectively. Tests with real-world mobile traffic datasets show that, in both its variants above, the proposed approach (i) yields results whose quality matches or exceeds that of state-of-the-art solutions, and (ii) provides additional joint spatiotemporal knowledge that is critical to result interpretation.
【Keywords】: Mobile communication; Loading; Mobile computing; Maximum likelihood estimation; Sociology; Mathematical model; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Jing Wang ; Jian Tang ; Zhiyuan Xu ; Yanzhi Wang ; Guoliang Xue ; Xing Zhang ; Dejun Yang
【Abstract】: In this paper, we propose to leverage the emerging deep learning techniques for spatiotemporal modeling and prediction in cellular networks, based on big system data. First, we perform a preliminary analysis for a big dataset from China Mobile, and use traffic load as an example to show non-zero temporal autocorrelation and non-zero spatial correlation among neighboring Base Stations (BSs), which motivate us to discover both temporal and spatial dependencies in our study. Then we present a hybrid deep learning model for spatiotemporal prediction, which includes a novel autoencoder-based deep model for spatial modeling and Long Short-Term Memory units (LSTMs) for temporal modeling. The autoencoder-based model consists of a Global Stacked AutoEncoder (GSAE) and multiple Local SAEs (LSAEs), which can offer good representations for input data, reduced model size, and support for parallel and application-aware training. Moreover, we present a new algorithm for training the proposed spatial model. We conducted extensive experiments to evaluate the performance of the proposed model using the China Mobile dataset. The results show that the proposed deep model significantly improves prediction accuracy compared to two commonly used baseline methods, ARIMA and SVR. We also present some results to justify effectiveness of the autoencoder-based spatial model.
【Keywords】: Cellular Network; Big Data; Spatiotemporal Modeling; Deep Learning; Autoencoder; Recurrent Neural Network
【Paper Link】 【Pages】:1-9
【Authors】: Novella Bartolini ; Ting He ; Hana Khamfroush
【Abstract】: Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by egde-nodes. We consider the problem of optimizing the capability of identifying network failures through the design of monitoring schemes. Finding an optimal solution is NP-hard and a large body of work has been devoted to heuristic approaches providing lower bounds. Unlike previous works, we provide upper bounds on the maximum number of identifiable nodes, given the number of monitoring paths and different constraints on the network topology, the routing scheme, and the maximum path length. The proposed upper bounds represent a fundamental limit on the identifiability of failures via Boolean network tomography. This analysis provides insights on how to design topologies and related monitoring schemes to achieve the maximum identifiability under various network settings. Through analysis and experiments we demonstrate the tightness of the bounds and efficacy of the design insights for engineered as well as real networks.
【Keywords】: Monitoring; Routing; Upper bound; Tomography; Testing; Encoding; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Sergey I. Nikolenko ; Kirill Kogan ; Antonio Fernández Anta
【Abstract】: We introduce structural transformations that allow simplifying a given network while preserving its original “bandwidth” and “routing” capabilities, transparently to specific allocations. We minimize a certain objective such as the aggregate capacity of network links, number of nodes, or number of links, in such a way that all the bandwidth that could be routed in the original network can also be routed in the reduced one. This improves cost-efficiency for both inter- and intra-datacenter connections and simplifies network management. We also identify a fundamental tradeoff between extra added capacity and simplicity of representation for a given network. Our analytic results are supported by extensive simulation results on hundreds of real network topologies. One result is that by adding 10-30% extra capacity to evaluated real-world networks one can simplify them down to a star topology with a single switch, while all routing and bandwidth allocation decisions on the simplified topology can be mapped back to the original network. This is an important step towards simplifying network management via a reduced virtualized network infrastructure.
【Keywords】: Bandwidth; Channel allocation; Routing; Network topology; Capacity planning; Topology; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Josu Doncel ; Samuli Aalto ; Urtzi Ayesta
【Abstract】: We consider a parallel-server system with K homogeneous servers where incoming tasks, arriving at rate λ, are dispatched by n dispatchers. Servers are FCFS queues and dispatchers implement a size-based policy such that the servers are equally loaded. We compare the performance of a system with n> 1 dispatchers and of a system with a single dispatcher. Every dispatcher handles a fraction 1/n of the incoming traffic and balances the load to K/n servers. We show that the performance of a system with n dispatchers, K servers and arrival rate λ coincides with that of a system with one dispatcher, K/n servers and arrival rate λ/n. Therefore, the performance comparison can be interpreted as the economies of scale in a system with one dispatcher when we scale up the number of servers and the arrival rate proportionately. We consider two continuous service time distributions: uniform and Bounded Pareto that have increasing and decreasing failure rates, respectively; and a discrete distribution with two values, which is the distribution that maximizes the variance for a given mean. We show that the performance degradation is small for uniformly distributed job sizes, but that for Bounded Pareto and two points distributions it can be unbounded.
【Keywords】: Servers; Degradation; Routing; Economies of scale; Conferences; Time factors
【Paper Link】 【Pages】:1-9
【Authors】: Xinzhe Fu ; Zhiying Xu ; Qianyang Peng ; Luoyi Fu ; Xinbing Wang
【Abstract】: Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P=NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov Decision Process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, it has comparable performance than some other seemingly more sophisticated algorithms. Second, by harnessing the sub-modularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms are justified through extensive simulations on three real network datasets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.
【Keywords】: Approximation algorithms; Testing; Heuristic algorithms; Algorithm design and analysis; Markov processes; Dynamic programming; Reliability
【Paper Link】 【Pages】:1-9
【Authors】: Kongyang Chen ; Guang Tan
【Abstract】: Indoor-outdoor (IO) detection provides very useful hints for a mobile device to perform context-aware services. To that end, GPS presents a viable solution by relating a device's IO status with its positioning performance, which depends on the device's exposure to the open sky. This approach, however, is prohibitively expensive in terms of energy consumption and response time. Recent work has thus been focused on exploiting low-energy sensors such as light, cellular, and magnetic sensors to infer the IO status indirectly, at the cost of reduced adaptability or explicit user involvement. In this paper, we propose an improving solution to this problem. Our method, called SatProbe, reverts to the GPS approach for its directness and robustness, but avoids its drawback by extracting only the number of visible satellites from the raw GPS data, instead of going through extensive computation to obtain a final position. This metric provides a clear indicator of the IO status, yet can be obtained with great efficiency. Experiments on 79 raw GPS traces with 2595 detection points across a variety of environments show that SatProbe produces higher detection accuracy than previous solutions, with more than an order of magnitude reductions in energy consumption and detection time.
【Keywords】: Global Positioning System; Satellites; Receivers; Magnetic sensors; Correlation; Multiaccess communication
【Paper Link】 【Pages】:1-9
【Authors】: Jin Wang ; Nicholas Tan ; Jun Luo ; Sinno Jialin Pan
【Abstract】: Given the ever-expanding scale of WiFi deployments in metropolitan areas, we have reached the point where accurate GPS-free outdoor localization becomes possible by relying solely on the WiFi infrastructure. Nevertheless, the existing industrial practices do not seem to have the right implementation to achieve an adequate accuracy, while the academic researches that are mostly attracted by indoor localization have largely neglected this outdoor aspect. In this paper, we propose WOLoc (WiFi-only Outdoor Localization) as a solution that offers meter-level accuracy, by holistically treating the large number of WiFi hotspot labels gather by crowdsensing. On one hand, we do not take these labels as fingerprints as it is almost impossible to extend indoor localization mechanisms by fingerprinting metropolitan areas. On the other hand, we avoid the over-simplified local synthesis methods (e.g., centroid) that significantly lose the information contained in the labels. Instead, we accommodate all the labeled and unlabeled data for a given area using a semi-supervised manifold learning technique, and the output concerning the unlabeled part will become the estimated locations for both users and WiFi hotspots. We conduct extensive experiments with WOLoc in several outdoor areas, and the results have strongly indicated the efficacy of our solution.
【Keywords】: Wireless fidelity; Urban areas; Manifolds; Conferences; Global Positioning System; Estimation; Roads
【Paper Link】 【Pages】:1-9
【Authors】: Robert Margolies ; Richard A. Becker ; Simon D. Byers ; Supratim Deb ; Rittwik Jana ; Simon Urbanek ; Chris Volinsky
【Abstract】: User location is of critical importance to cellular network operators. It is often used for network capacity planning and to aid in the analysis of service and network diagnostics. However, existing localization techniques rely on user-provided information (e.g., Angle-of-Arrival), which are not available to the operator, and often require a significant effort to collect training data. Our main contribution is the design and evaluation of the Network-Based Localization (NBL) System for localizing a user in a 4G LTE network. The NBL System consists of 2 stages. In an offline stage, we develop RF coverage maps based on a large-scale crowd-sourced channel measurement campaign. Then, in an online stage, we present a localization algorithm to quickly match RF measurements (which are already collected as part of normal network operation) to coverage map locations. The system is more practical than related works, as it does not make any assumptions about user mobility, nor does it require expensive manual training measurements. Despite the realistic assumptions, our extensive evaluations in a national 4G LTE network show that the NBL System achieves a localization accuracy which is comparable to related works (i.e., a median accuracy of 5% of the cell's coverage region).
【Keywords】: Localization; wireless networks; crowd-sourcing
【Paper Link】 【Pages】:1-9
【Authors】: Mah-Rukh Fida ; Andra Lutu ; Mahesh K. Marina ; Ozgu Alay
【Abstract】: The accuracy of measurement-driven mobile coverage maps depends on the quality, density and pattern of the signal strength observations. Thus, identifying an efficient measurement data collection methodology is essential, especially when considering the cost associated with the measurement collection approaches (e.g., drive tests, crowd approaches). We propose ZipWeave, a novel measurement data collection and fusion framework for building efficient and reliable measurement-based mobile coverage maps. ZipWeave incorporates a novel nonuniform sampling strategy to achieve reliable coverage maps with reduced sample size. Assuming prior knowledge of the propagation characteristics of the region of interest, we first examine the potential gains of this non-uniform sampling strategy in different cases via a measurement-based statistical analysis methodology; this involves irregular spatial tessellation of the region of interest into sub-regions with internally similar radio propagation characteristics and sampling based on these sub-regions. We then present a practical form of ZipWeave nonuniform sampling strategy that can be used even without any prior information. In all our evaluations, we show that the ZipWeave non-uniform sampling approach reduces the samples by half compared to the common systematic-random sampling, while maintaining similar accuracy. Moreover, we show that the other key feature of ZipWeave to combine high-quality controlled measurements (that present limited geographic footprint similar to drive tests) with crowdsourced measurements (that cover a wider footprint) leads to more reliable mobile coverage maps overall.
【Keywords】: Reliability; Mobile communication; Atmospheric measurements; Battery charge measurement; Particle measurements; Monitoring; Urban areas
【Paper Link】 【Pages】:1-9
【Authors】: Jiayao Tan ; Cam-Tu Nguyen ; Xiaoliang Wang
【Abstract】: The recently enhanced computing capability and rich sensing functionality on mobile devices lead to the ubiquitous application of speech recognition. Traditional speech recognition records acoustic signals or visual images to interpret speech. However, the acoustic based scheme has many drawbacks. It is easily affected by the environmental noise when users are in the factory or market, and can not be used in a place where people need to be quite such as library. Specifically the current design is not suitable for people with speaking or hearing difficulties. Unfortunately, the visual-based approach is sensitive to fight conditions which shows poor performance in the dark area. As a result, it is necessary to provide an new human-computer interaction channel to assist speech recognition. This paper presents SilentTalk, a non-invasive lip reading system based on ultrasonic Doppler effect The main idea is to generate ultrasonic signals from a mobile phone, then capture the reflections and analyze the fine-grained frequency shift caused by mouth movements. A Frequency Shift Detection Model (FSDM) is proposed to quantify the correlation between frequency variations and mouth movements that form different syllables. SilentTalk then applies a Continuous Lip Reading Model (CLRM) on top of FSDM to realize continuous lip reading. Based on Markov assumption, CLRM effectively combines pronunciation rules and context knowledge to connect isolated syllables to words and sentences. Experiments show that SilentTalk can identify 12 basic mouth motions up to 95.4% accuracy in English. The system can also recognize short sentences up to six words with an average accuracy of 74.8%.
【Keywords】: Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Yu-Lin Wei ; Hsin-I Wu ; Han-Chung Wang ; Hsin-Mu Tsai ; Kate Ching-Ju Lin ; Rayana Boubezari ; Hoa Le Minh ; Zabih Ghassemlooy
【Abstract】: Accurate orientation information is the key in many applications, ranging from map reconstruction with crowdsourcing data, location data analytics, to accurate indoor localization. Many existing solutions rely on noisy magnetic and inertial sensor data, leading to limited accuracy, while others leverage multiple, dense anchor points to improve the accuracy, requiring significant deployment efforts. This paper presents LiCompass, the first system that enables a commodity camera to accurately estimate the object orientation using just a single optical anchor. Our key idea is to allow a camera to observe varying intensity level of polarized light when it is in different orientations and, hence, perform estimation directly from image pixel intensity. As the estimation relies only on pixel intensity, instead of the location of the anchor in an image, the system performs reliably at long distance, with low resolution images, and with large perspective distortion. LiCompass' core designs include an elaborate optical anchor design and a series of signal processing techniques based on trigonometric properties, which extend the range of orientation estimation to full 360 degrees. Our prototype evaluation shows that LiCompass produces very accurate estimates with median errors of merely 2.5 degrees at 5 meters and 7.4 degrees at 2.5 meters with an irradiance angle of 55 degrees.
【Keywords】: Cameras; Estimation; Optical polarization; Adaptive optics; Optical imaging; Optical distortion; Optical receivers
【Paper Link】 【Pages】:1-9
【Authors】: Huijie Chen ; Fan Li ; Yu Wang
【Abstract】: This paper explores the limits of acoustic ranging on smart phone in the scenario of device-free hand tracking. Tracking the hand is challenging since it requires continuously locating the moving hand in the air with fine resolution. Existing work on hand tracking relies on special hardware or requires users hold the mobile device. This paper presents EchoTrack, which continuously locates the hand by leveraging mobile audio hardware advances without special infrastructure supported. EchoTrack measures the distance from the hand to the speaker array embedded in smart phone via the chirp's Time of Flight (TOF). The speaker array and hand yield a unique triangle. The hand can be located with this triangular geometry. The trajectory accuracy can be improved with the method of Doppler shift compensation and trajectory correction (i.e., roughness penalty smoothing method). We implement a prototype on smart phone and the evaluation shows that EchoTrack can achieve tracking accuracy within about three centimeters of 76% and two centimeters of 48%.
【Keywords】: Chirp; Microphones; Smart phones; Distance measurement; Trajectory; Hardware; Doppler shift
【Paper Link】 【Pages】:1-9
【Authors】: Han Xu ; Zheng Yang ; Zimu Zhou ; Ke Yi ; Chunyi Peng
【Abstract】: Cross-device interaction is becoming an increasingly hot topic as we often have multiple devices at our immediate disposal in this era of mobile computing. Various cross-device applications such as file sharing, multi-screen display, and cross-device authentication have been proposed and investigated. However, one of the most fundamental enablers remains unsolved: How to achieve ubiquitous multi-device localization? Though pioneer efforts have resorted to gesture-assisted or sensing-assisted localization, they either require extensive user participation or impose some strong assumptions on device sensing abilities. This introduces extra costs and constraints, and thus degrades their practicality. To overcome these limitations, we propose TUM, an acoustic-assisted localization scheme Towards Ubiquitous Multi-device localization. The basic idea of TUM is to utilize the dual-microphones and speakers to obtain distance cues among devices. At the same time it resolves the location ambiguity with the help of MEMS sensors. We devise techniques for distance constraint extraction, static localization, continuous localization, and multi-device localization, and build a prototype that runs on commodity devices. Extensive experiments show that TUM provides a real-time 3D relative localization service under 10cm mean error for both static and continuous localization.
【Keywords】: Microphones; Acoustics; Sensors; Smart devices; Distance measurement; Three-dimensional displays; Clocks
【Paper Link】 【Pages】:1-9
【Authors】: Wenjun Jiang ; Jie Wu
【Abstract】: Recommendation systems usually try to “guess” a user's preferences from the system's view. We study another side of recommendation: active opinion-formation from the perspective of the user. In real life, a user's opinion evolves with time and refines when new evidence occurs. Then, how does an online user form his/her own opinion actively in large social networks? The problem has three challenges: the factor, the effect and the open environment. To address those challenges, we investigate: (1) what factors or channels a user will consider, (2) how those channels will take effect, and (3) an incremental approach to incorporate multiple channels. We explore three types of channels: the internal opinion of an individual user, influences from trusted friends, and influences from public channels. A novel simulator, OpinionFormer, is proposed to incorporate those channels incrementally. It differentiates the effects of friends and public channels as well as positive and negative opinions. We validate the performance of OpinionFormer by predicting users' opinions using real-world data sets. Experimental results show that our model can improve accuracy over other models that ignore some channels or that neglect the evolving features.
【Keywords】: opinion formation; internal opinion; trusted friend; public channel; fluid dynamics
【Paper Link】 【Pages】:1-9
【Authors】: Aakas Zhiyuli ; Xun Liang ; Zhiming Xu
【Abstract】: Learning distributed representations of symbolic data were introduced by Hinton[1], and first developed in modeling networks for learning the node vectors by Perozzi et al (2014). In this work, we proposed Dnps, a novel nodes embedding approach for acquiring distributed representations of large-scale dynamic social networks. Dnps is suitable for many types of social networks: dynamic/static, directed/undirected, and weighted/unweighted. Recently, several works of nodes embedding were proposed. However, they were designed for static networks, such as language networks. To address this problem, first, we develop a damping based positive sampling (DpS) algorithm to learn the hierarchical structure of social networks. Then, we devise a local search based DpS algorithm to obtain incremental information of network evolution. Finally, we show Dnps's potentials on future link prediction task for three real-life large-scale dynamic social networks. The results show that Dnps consistently outperforms all baseline methods and exhibits an improvement of 12%, 6%, 4% on Digg, Flickr and YouTube over the second-highest level, respectively. Moreover, Dnps is also scalable. For example, Dnps can speed up the training process in 2 ~ 36 times compared with benchmarks on Flickr network. The source codes of the project is available online1.
【Keywords】: Social network services; Damping; Heuristic algorithms; Training; Algorithm design and analysis; Prediction algorithms; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Weiyu Chen ; Christopher G. Brinton ; Da Cao ; Mung Chiang
【Abstract】: We study learning outcome prediction for online courses. Whereas prior work has focused on semester-long courses with frequent student assessments, we focus on short-courses that have single outcomes assigned by instructors at the end. The lack of performance data makes the behavior of learners, captured as they interact with course content and with one another in Social Learning Networks (SLN), essential for prediction. Our method defines several (machine) learning features based on behaviors collected on the modes of (human) learning in a course, and uses them in appropriate classifiers. Through evaluation on data captured from three two-week courses hosted through our delivery platforms, we make three key observations: (i) behavioral data is predictive of learning outcomes in short-courses (our classifiers achieving AUCs ≥ 0.8 after the two weeks), (ii) it has an early detection capability (AUCs ≥ 0.7 with the first week of data), and (iii) the content features have an “earliest” detection capability (with higher AUC in the first few days), while the SLN features become the more predictive set over time, as the network matures. We also discuss how our method can generate behavioral analytics for instructors.
【Keywords】: Feature extraction; Training; Programmable logic arrays; Data models; Computational modeling; Conferences; Discussion forums
【Paper Link】 【Pages】:1-9
【Authors】: Guangchi Liu ; Qi Chen ; Qing Yang ; Binhai Zhu ; Honggang Wang ; Wei Wang
【Abstract】: Massive trust assessment (MTA) in an Online Social Network (OSN), i.e., computing the trustworthiness of all users in the network, is crucial in various OSN-related applications. Existing solutions are either too slow or inaccurate in addressing the MTA problem. We propose the OpinionWalk algorithm that accurately and efficiently conducts MTA in an OSN. OpinionWalk models trust by the Dirichlet distribution and uses a matrix to represent the direct trust relations among users. From the perspective of a user, other users' trustworthiness are stored in a column vector that is iteratively updated when the algorithm “walks” through the network, in a breadth-first search manner. We identify the overlapping subproblems property in MTA and prove OpinionWalk is a more efficient solution. The accuracy and execution time of OpinionWalk are evaluated and compared to benchmark algorithms including EigenTrust, TrustRank, MoleTrust, TidalTrust and AssessTrust, using two real-world datasets (Advogato and Pretty Good Privacy). Experimental results indicate that OpinionWalk is an efficient and accurate solution to MTA, compared to previous algorithms.
【Keywords】: Massive trust assessments; online social networks; threes-valued subjective logic; trust model
【Paper Link】 【Pages】:1-9
【Authors】: Zhimeng Yin ; Wenchao Jiang ; Song Min Kim ; Tian He
【Abstract】: Recent research on CTC (cross-technology communication) demonstrates the viability of direct coordination among heterogeneous devices (e.g., WiFi and ZigBee) with incompatible physical layers. Although encouraging, current solutions suffer from either severe inefficiency in channel utilization or low throughput using limited beacons. To address these limitations, this paper presents C-Morse, which leverages all traffic (such as through data packets, beacons and other control frames) to achieve a high cross-technology communication throughput. The key idea of C-Morse is to slightly perturb the transmission timing of existing WiFi packets to construct recognizable radio energy patterns without introducing noticeable delays to upper layers. At the receiver side, ZigBee captures such patterns by sensing the RSSI value, and then decodes the transmitted symbols. C-Morse also introduces a novel timing-based multiplexing technique to allow the coexistence of multiple C-Morse access points and reject other interference, showing a reliable symbol delivery ratio. As a result, C-Morse achieves a free side-channel, whose CTC throughput is as much as 9 χ of the present state of the art, while maintaining the through traffic within a negligible delay that goes unnoticed by applications and end-users.
【Keywords】: Wireless fidelity; ZigBee; Delays; Wireless communication; Throughput; Wireless sensor networks
【Paper Link】 【Pages】:1-9
【Authors】: Xiuzhen Guo ; Xiaolong Zheng ; Yuan He
【Abstract】: The proliferation of loT applications drives the need of ubiquitous connections among heterogeneous wireless devices. Cross-Technology Communication (CTC) is a significant technique to directly exchange information among heterogeneous devices that follow different standards. By exploiting a side-channel like frequency, amplitude or temporal modulation, the existing works enable CTC but have limited performance under channel noise. In this paper, we propose WiZig, a novel CTC technique that employs modulation techniques in both the amplitude and temporal dimensions to optimize the throughput over a noisy channel. We establish a theoretical model of the energy communication channel to clearly understand the channel capacity. We then devise an online rate adaptation algorithm to adjust the modulation strategy according to the channel condition. Based on the theoretical model, WiZig can accurately control the number of encoded energy amplitudes and the length of a receiving window, so as to optimize the CTC throughput. We implement a prototype of WiZig on a software radio platform and a commercial ZigBee device. The evaluation show that WiZig achieves a throughput of 153.85 bps with less than 1 % symbol error rate in a real environment. The results demonstrate that WiZig realizes efficient and reliable CTC under varied channel conditions.
【Keywords】: Receivers; Wireless communication; Throughput; Error analysis; Noise measurement; Wireless sensor networks; Modulation
【Paper Link】 【Pages】:1-9
【Authors】: Zicheng Chi ; Zhichuan Huang ; Yao Yao ; Tiantian Xie ; Hongyu Sun ; Ting Zhu
【Abstract】: The exponentially increasing number of IoT devices makes the unlicensed industrial, scientific, and medical (ISM) radio bands (e.g., 2.4 GHz) extremely crowded. Currently, there is no efficient solution to coordinate the large amount heterogeneous IoT devices that have different communication technologies (e.g., WiFi and ZigBee). To fill this gap, in this paper, we introduce embedded multiple flows (EMF) communication method, which (i) embeds different pieces of information in existing traffic and (ii)concurrently sends out these information from one IoT sender to multiple IoT receivers that have a different communication technology from the sender. By doing this, our EMF method (i) enables cross-technology communication among heterogeneous IoT devices, (ii) does not introduce any extra control traffic, and (iii) is transparent to the higher layer applications. Our approach is implemented on USRPs and commercial off-the-shelf (COTS) ZigBee devices. We also conducted extensive experiments to evaluate our approach in real-world settings. The evaluation results show that EMF's throughput is more than 14 times higher than the latest cross-technology communication technique (i.e. FreeBee[1]).
【Keywords】: Wireless fidelity; ZigBee; Receivers; Modulation; Throughput; Bit error rate; Logic gates
【Paper Link】 【Pages】:1-9
【Authors】: Tomoya Osuki ; Kazuya Sakai ; Satoshi Fukumoto
【Abstract】: Delay tolerant networks (DTNs) are widely adopted to many network applications, such as disaster recovery and battlefield communications. Such critical network scenarios call for an outright prevention mechanism against contact-based attacks, e.g., blackmailing a legitimate user to compromise sensitive information at a contact. To the best of our knowledge, there is no work on secure routing protocol against contact-based attacks in DTNs. Therefore, in this paper, we first formulate the problem of contact avoidance routing, in which the node holding a message tries to avoid having a contact with an adversary. By applying the phase-type distribution, we build the secure opportunistic path model, which integrates the delivery probability within the deadline and the safety of opportunistic paths. Then, we propose a contact avoidance routing (CAR) protocol to securely deliver a message to its destination against the contact-based compromise attack. In addition, we further propose an adaptive CAR (A-CAR) to accommodate complicated network scenarios, where the capabilities of adversaries are parameterized. The extensive simulations using real traces as well as random graphs demonstrate that the proposed CAR and A-CAR protocols achieve their design goals.
【Keywords】: Contact avoidance routing; network security; delay tolerant networks; DTNs
【Paper Link】 【Pages】:1-9
【Authors】: Haiming Jin ; Lu Su ; Klara Nahrstedt
【Abstract】: The recent proliferation of increasingly capable mobile devices has given rise to mobile crowd sensing (MCS) systems that outsource the collection of sensory data to a crowd of participating workers that carry various mobile devices. Aware of the paramount importance of effectively incentivizing participation in such systems, the research community has proposed a wide variety of incentive mechanisms. However, different from most of these existing mechanisms which assume the existence of only one data requester, we consider MCS systems with multiple data requesters, which are actually more common in practice. Specifically, our incentive mechanism is based on double auction, and is able to stimulate the participation of both data requesters and workers. In real practice, the incentive mechanism is typically not an isolated module, but interacts with the data aggregation mechanism that aggregates workers' data. For this reason, we propose CENTURION, a novel integrated framework for multi-requester MCS systems, consisting of the aforementioned incentive and data aggregation mechanism. CENTURION's incentive mechanism satisfies truthfulness, individual rationality, computational efficiency, as well as guaranteeing non-negative social welfare, and its data aggregation mechanism generates highly accurate aggregated results. The desirable properties of CENTURION are validated through both theoretical analysis and extensive simulations.
【Keywords】: Sensors; Reliability; Data aggregation; Mobile communication; Conferences; Mobile handsets
【Paper Link】 【Pages】:1-9
【Authors】: Chao Huang ; Dong Wang ; Shenglong Zhu
【Abstract】: Crowdsourcing has emerged as an important data collection paradigm in participatory and human-centric sensing applications. While many crowdsourcing studies focus on sensing and recovering the status of the physical world, this paper investigates the problem of profiling the crowd sensors (i.e., humans). In particular, we study the problem of accurately inferring the home locations of people from the noisy and sparse crowdsourcing data they contribute. In this study, we propose a semi-supervised framework, Where Are You From (WAYF), to accurately infer the home locations of people by explicitly exploring the localness of people and the dependency between people based on their check-in behaviors under a rigorous analytical framework. We perform extensive experiments to evaluate the performance of our scheme and compared it to the state-of-the-art techniques using three real world data traces collected from Foursquare. The results showed the effectiveness of our scheme in accurately profiling the home locations of people.
【Keywords】: Home Location Profiling; Crowdsourcing; Location Based Social Networks (LBSN)
【Paper Link】 【Pages】:1-9
【Authors】: Ayon Chakraborty ; Md. Shaifur Rahman ; Himanshu Gupta ; Samir R. Das
【Abstract】: We describe an end-to-end platform called SpecSense to support large scale spectrum monitoring. SpecSense crowdsources spectrum monitoring to low-cost, low-power commodity SDR/embedded platforms and provides necessary analytics support in a central spectrum server. In this work, we describe SpecSense and address specific challenges related to accurately estimate spectrum occupancy on demand with low overhead. To address the accuracy question, we augment state-of-the-art spatial interpolation techniques to accommodate scenarios where RF propagation characteristics change across space. To address the overhead question, we solve the sensor selection problem to select the minimum number of spectrum sensors that can best estimate the spectrum at the requested locations.
【Keywords】: Interpolation; Radio frequency; Monitoring; RF signals; Crowdsourcing; Sensors; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Chenglin Miao ; Lu Su ; Wenjun Jiang ; Yaliang Li ; Miaomiao Tian
【Abstract】: The recent proliferation of human-carried mobile devices has given rise to the mobile crowd sensing (MCS) systems. However, the sensory data provided by the participating workers are usually not reliable. As an efficient technique to extract truthful information from unreliable data, truth discovery has drawn significant attention. Currently, the privacy concern of the participating workers poses a major challenge on the design of truth discovery mechanisms. Although the existing mechanism can conduct truth discovery with high accuracy and strong privacy guarantee, tremendous overhead is incurred on the worker side. In this paper, we propose a novel lightweight privacy preserving truth discovery framework, L-PPTD, which is implemented by involving two non-colluding cloud platforms and adopting additively homomorphic cryptosystem. This framework not only achieves the protection of each worker's sensory data and reliability information but also introduces little overhead to the workers. In order to further reduce each worker's overhead in the scenarios where only the sensory data need to be protected, we propose another more lightweight framework named L2-PPTD. The desirable performance of the proposed frameworks is verified through extensive experiments conducted on real world MCS systems.
【Keywords】: Reliability; Sensors; Cryptography; Privacy; Mobile handsets; Zinc
【Paper Link】 【Pages】:1-9
【Authors】: Juan Li ; Yanmin Zhu ; Jiadi Yu ; Chengnian Long ; Guangtao Xue ; Shiyou Qian
【Abstract】: Auctions have been adopted by many major cloud providers, such as Amazon EC2. Unfortunately, only simple auctions have been implemented. Such simple auction has serious limitations, such as being unable to accept elastic user demands and having to allocate different types of VMs independently. These limitations create a big gap between the real needs of cloud users and the available services of cloud providers. In response to the limitations of the existing auction mechanisms, this paper proposes a novel online auction mechanism for IaaS clouds, with the unique features of an elastic model for inputting time-varying user demands and a unified model for requesting heterogeneous VMs together. However, several major challenges should be addressed, such as NP hardness of optimal VM allocation, time-varying user demands and potential misreports of private information of cloud users. We propose a truthful online auction mechanism for maximizing the profit of the cloud provider in IaaS clouds, which is composed of a price-based allocation rule and a payment rule. In the allocation rule, the online auction mechanism determines the number of VMs of each type to each user. In the payment rule, by introducing a marginal price function for each type of VMs, the mechanism determines how much the cloud provider should charge each cloud user. With solid theoretical analysis and trace-driven simulations, we demonstrate that our mechanism is truthful and individually rational, and has a polynomial-time complexity.
【Keywords】: IaaS Clouds; online auctions; time-varying; elastic user demands; weighted heterogeneous VMs; profit maximization
【Paper Link】 【Pages】:1-9
【Authors】: Haisheng Tan ; Zhenhua Han ; Xiang-Yang Li ; Francis C. M. Lau
【Abstract】: In edge-cloud computing, a set of edge servers are deployed near the mobile devices such that these devices can offload jobs to the servers with low latency. One fundamental and critical problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of a job and the arrival of the computation result at its device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and times at the mobile devices and offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time over all the jobs. The weight is set based on how latency sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any constant ε ϵ (0,1). Moreover, OnDisc can be easily implemented in distributed systems. Extensive simulations on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.
【Keywords】: Servers; Cloud computing; Mobile handsets; Algorithm design and analysis; Dispatching; Time factors; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Rui Zhu ; Di Niu ; Zongpeng Li
【Abstract】: We study the problem of personalized Quality of Service (QoS) estimation for web services. State-of-the-art methods use matrix factorization or collaborative prediction to estimate web service response times and throughput for each user based on partial measurements collected from past invocations. We point out that in reality, both the response times and through-put of web services follow highly skewed distributions. In this case, the conditional mean QoS estimates generated by traditional matrix completion approaches can be heavily biased toward a few outliers, leading to poor web service recommendation performance. In this paper, we propose the Quantile Matrix Factorization (QMF) technique for web service recommendation by introducing quantile regression into the matrix factorization framework. We propose a novel and efficient algorithm based on Iterative Reweighted Least Squares (IRLS) to solve the QMF problem involving a non-smooth objective function. We further extend the proposed QMF approach to take into account user and service side attributes. Extensive evaluation based on a large-scale QoS dataset has shown that our schemes significantly outperform various state-of-the-art web service QoS estimation schemes in terms of personalized recommendation performance.
【Keywords】: Web services; Quality of service; Time factors; Throughput; Estimation; Measurement; Collaboration
【Paper Link】 【Pages】:1-9
【Authors】: Xiaoxi Zhang ; Chuan Wu ; Zongpeng Li ; Francis C. M. Lau
【Abstract】: Network Function Virtualization (NFV) represents a new paradigm of network service provisioning. NFV providers acquire cloud resources, install virtual network functions (VNFs), assemble VNF service chains for customer usage, and dynamically scale VNF deployment against input traffic fluctuations. While existing literature on VNF scaling mostly adopts a reactive approach, we target a proactive approach that is more practical given the time overhead for VNF deployment. We aim to effectively estimate upcoming traffic rates and adjust VNF deployment a priori, for flow service quality assurance and resource cost minimization. We adapt online learning techniques for predicting future service chain workloads. We further combine the online learning method with a multi-timescale online optimization algorithm for VNF scaling, through minimization of the regret due to inaccurate demand prediction and minimization of the cost incurred by sub-optimal online decisions in a joint online optimization framework. The resulting proactive online VNF provisioning algorithm achieves a good performance guarantee, as shown by both theoretical analysis and simulation under realistic settings.
【Keywords】: Prediction algorithms; Algorithm design and analysis; Cloud computing; Optimization; Minimization; Hardware; Dynamic scheduling
【Paper Link】 【Pages】:1-9
【Authors】: Setareh Sharifian ; Fuchun Lin ; Reihaneh Safavi-Naini
【Abstract】: Key agreement using physical layer properties of communication channels is a well studied problem. iJam is a physical layer key agreement protocol that achieves security by creating a “virtual” wiretap channel for the adversary through a subprotocol between the sender and the receiver that uses self-jamming by the receiver. The protocol was implemented and its security was shown through extensive experiments. The self-jamming subprotocol of iJam was later modelled as a wiretap channel and used for designing a secure message transmission protocol with provable security. We use the same wiretap model of the subprotocol to design secret key agreement protocols with provable security. We propose two protocols that use the wiretap channel once from Alice to Bob, and a protocol that uses two wiretap channels, one from Alice to Bob, and one in the opposite direction. We provide security proof and efficiency analysis for the protocols. The protocols effectively give physical layer security protocols that can be implemented and have provable security. We discuss our results and propose directions for future research.
【Keywords】: Protocols; Security; Receivers; Jamming; Random variables; Physical layer; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Pengwei Wang ; Reihaneh Safavi-Naini
【Abstract】: In Wyner wiretap II model of communication, Alice and Bob are connected by a channel that can be eavesdropped by an adversary with unlimited computation who can select a fraction of communication to view, and the goal is to provide perfect information theoretic security. Information theoretic security is increasingly important because of the threat of quantum computers that can effectively break algorithms and protocols that are used in today's public key infrastructure. We consider interactive protocols for wiretap II channel with active adversary who can eavesdrop and add adversarial noise to the eavesdropped part of the codeword. These channels capture wireless setting where malicious eavesdroppers at reception distance of the transmitter can eavesdrop the communication and introduce jamming signal to the channel. We derive a new upperbound R ≤ 1 - ρ for the rate of interactive protocols over two-way wiretap II channel with active adversaries, and construct a perfectly secure protocol family with achievable rate 1 - 2ρ + ρ2. This is strictly higher than the rate of the best one round protocol which is 1 - 2ρ, hence showing that interaction improves rate. We also prove that even with interaction, reliable communication is possible only if ρ <; 1/2. An interesting aspect of this work is that our bounds will also hold in network setting when two nodes are connected by n paths, a ρ of which is corrupted by the adversary. We discuss our results, give their relations to the other works, and propose directions for future work.
【Keywords】: Protocols; Reliability; Security; Mobile communication; Random variables; Upper bound; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Kai-Wei Jiang ; Tao Jing ; Zhen Li ; Yan Huo ; Fan Zhang
【Abstract】: Recently, a new paradigm of multiple access (MAC) along with one eavesdropper to achieve secrecy transmissions has been getting in focus. However, all existing work on such multiple access wiretap channel (MAC-WT) mainly concentrates on the secrecy performance of the system as a whole from an information theoretic perspective. In this work, we investigate the secrecy performance of a single transmitter in the quasi-static Rayleigh fading MAC-WT on basis of two decoding methods, zero-forcing (ZF) and minimum mean-square error (MMSE), jointly with successive interference cancellation (SIC). We evaluate the secrecy performance in three metrics: positive secrecy capacity probability, secrecy outage probability and effective secrecy throughput. The analytical and simulation results show that, 1) the SIC order has great impacts on the secrecy performance for both methods; 2) MMSE-SIC outperforms ZF-SIC, while the performance gap can be overcome via adjusting SIC order, or increasing SNR, or enhancing the spatial diversity gain; 3) in high SNR regime, the secrecy performance is only determined by the relative distance to eavesdropper over legitimate receiver rather than the SNR.
【Keywords】: Decoding; Silicon carbide; Signal to noise ratio; Transmitters; Fading channels; Interference; Receivers
【Paper Link】 【Pages】:1-9
【Authors】: Matthew Bradbury ; Arshad Jhumka
【Abstract】: Source location privacy (SLP) is becoming an important property for a large class of security-critical wireless sensor network applications such as monitoring and tracking. Much of the previous work on SLP has focused on the development of various protocols to enhance the level of SLP imparted to the network, under various attacker models and other conditions. Other work has focused on analysing the level of SLP being imparted by a specific protocol. In this paper, we adopt a different approach where we model the attacker movement as a time series and use information theoretic concepts to infer the properties of a routing protocol that imparts high levels of SLP. We propose the notion of a properly competing path that causes an attacker to “stall” when moving towards the source. This concept provides the basis for developing a perturbation model, similar to those in privacy-preserving data mining. We then show how to use properly competing paths to develop properties of an SLP-aware routing protocol. Further, we show how different SLP-aware routing protocols can be obtained through different instantiations of the framework. Those instantiations are obtained based on a notion of information loss achieved through the use of the perturbation model proposed.
【Keywords】: Source Location Privacy; Wireless Sensor Networks; Entropy; Mutual Information; Time Series
【Paper Link】 【Pages】:1-9
【Authors】: Liang Zheng ; Carlee Joe-Wong ; Jiasi Chen ; Christopher G. Brinton ; Chee Wei Tan ; Mung Chiang
【Abstract】: Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.
【Keywords】: Mobile communication; Quality of service; Throughput; Economics; Wireless fidelity; Switches; Pricing
【Paper Link】 【Pages】:1-9
【Authors】: Debasis Mitra ; Qiong Wang ; Ao Hong
【Abstract】: We study engineering and business relationships between Content Providers and broadband access ISPs in various organizational and policy environments. We focus on pricing and capacity decisions for bandwidth and caches for delivery of the CP's content over the “last mile” of the ISP's infrastructure. We model the CP-ISP interaction by the Stackelberg “leader-follower” game and the Integrated Operations model. We consider cases where premium bandwidth is offered to subscribers of the CP's service over the last mile, and cases where this is prohibited by Net Neutrality regulations. We develop a uniform solution procedure for all four resulting models. We explore the connections between optimal bandwidth and cache deployments, and, together with fees, their impact on the number of users, and related business and policy topics. We show that the decrease in profitability of caching due to Net Neutrality regulations is greater than the decrease from Integrated Operations to the Stackelberg game. In the Stackelberg game we prove that if a certain condition is satisfied, then with Net Neutrality the ISP will increase the cache price so that it is unprofitable for the CP to use caches. Moreover, this condition is satisfied in a typical case studied in detail.
【Keywords】: Bandwidth; Artificial neural networks; Network neutrality; Elasticity; Business; Internet
【Paper Link】 【Pages】:1-9
【Authors】: John Z. F. Pang ; Hu Fu ; Won I. Lee ; Adam Wierman
【Abstract】: This paper studies how the efficiency of an online platform is impacted by the degree to which access of platform participants is open or controlled. The study is motivated by an emerging trend within platforms to impose increasingly fine-grained control over the options available to platform participants. While early online platforms allowed open access, e.g., Ebay allows any seller to interact with any buyer; modern platforms often impose matches directly, e.g., Uber directly matches drivers to riders. This control is performed with the goal of achieving more efficient market outcomes. However, the results in this paper highlight that imposing matches may create new strategic incentives that lead to increased inefficiency. In particular, in the context of networked Cournot competition, we prove that open access platforms guarantee social welfare within 7/16 of the optimal; whereas controlled allocation platforms can have social welfare unboundedly worse than optimal.
【Keywords】: Open Access; Resource management; Production; Economics; Conferences; Market research; Companies
【Paper Link】 【Pages】:1-9
【Authors】: Diego Ximenes Mendes ; Edmundo de Souza e Silva ; Daniel Sadoc Menasché ; Rosa Maria Meri Leão ; Don Towsley
【Abstract】: Swarming systems, such as BitTorrent, are one of the most common solutions for scalable, robust and inexpensive content distribution. Although the service capacity of swarming systems has been studied for decades through modeling and analysis, there is a lack of experimental evidence about how the throughput of such systems behaves in under-provisioned regimes. The aim of this paper is to fill this gap. In this paper, we consider a closed-loop model to assess the throughput of peer-to-peer systems. Then, we show through controlled experiments using BitTorrent clients that some analytical findings recently reported in the literature, such as the missing piece syndrome, occur in practice. In particular, we indicate that when seeds have a small effective service capacity, or when seeds are intermittent, the throughput saturates as the population size grows. Finally, we discuss the implications of such findings on the modeling and design of swarming systems.
【Keywords】: Throughput; Sociology; Statistics; Analytical models; Computational modeling; Scalability; Peer-to-peer computing
【Paper Link】 【Pages】:1-9
【Authors】: Chi-Han Lin ; Yi-Ting Chen ; Kate Ching-Ju Lin ; Wen-Tsuen Chen
【Abstract】: Multi-User Multiple Input Multiple Output (MU-MIMO) enables a multi-antenna access point (AP) to serve multiple users simultaneously, and has been adopted as the IEEE 802.11ac standard. While several PHY-MAC designs have recently been proposed to improve the throughput performance of a MU-MIMO WLAN, they, however, usually assume that all the concurrent streams are of roughly equal length. In reality, users usually have frames with heterogeneous lengths even after aggregation, leading to different lengths of transmission time. Hence, the concurrent transmission opportunities might not always be fully utilized when some streams finish earlier than the others in a transmission opportunity (TXOP). To resolve this inefficiency, this paper presents acPad, a PHY-MAC design that adds additional frames to fill up the idle channel time and better utilize the spatial multiplexing gain. Our acPad identifies proper users as the padding so as to improve the padding gain, while preventing this padding from harming all the ongoing streams. Our evaluation via large-scale trace-driven simulations demonstrates that acPad improves the throughput by up to 2.83×, or by 1.36× on average, as compared to the conventional 802.11ac.
【Keywords】: Signal to noise ratio; Interference; Precoding; Throughput; MIMO; Standards; Array signal processing
【Paper Link】 【Pages】:1-9
【Authors】: Seongwon Kim ; Jaehong Yi ; Youngwook Son ; Seungmin Yoo ; Sunghyun Choi
【Abstract】: With increasing demand for wireless connectivity, IEEE 802.11 WLANs have become ubiquitous and continue to grow in number. This leads to high density of basic service sets with the significant co-channel interference (CCI) among them. This paper sheds light on the CCI caused by 802.11 MAC ACK frames, which has been less studied than the CCI caused by data frames. Based on stochastic geometry analysis, we propose Quiet ACK (QACK), a dynamic transmit power control algorithm for ACK frames. Fine-grained transmit power adjustment is enabled by CCI detection and CCI power estimation in the middle of a data frame reception. Our prototype using software-defined radio shows the feasibility and performance gain of QACK, i.e., 1.5x higher throughput than the legacy 802.11 WLANs. The performance of QACK is further evaluated in more general WLAN environments via extensive simulations using ns-3.
【Keywords】: Interference; Power control; IEEE 802.11 Standard; Wireless LAN; Power system reliability; Probability; Heuristic algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Gyujin Lee ; Yeonchul Shin ; Jonghoe Koo ; Junyoung Choi ; Sunghyun Choi
【Abstract】: Multicast is a major solution in supporting the explosive growth of the wireless video traffic demand. Also, power saving is a key technology to extend battery life of mobile devices. To meet both purposes, IEEE 802.11 wireless local area network (WLAN) supports power save mode (PSM) for station (STA) while receiving multicast packets. According to recent studies, off-the-shelf chipsets configured to use PSM show un-desired functions, thus resulting in many multicast packet losses. From our extensive measurement, we also verify degradation of multicast performance with widely-used off-the-shelf chipsets using PSM, and present previously-unknown undesired functions. Without modification of the chipsets, STA in PSM cannot enjoy reliable multicast service. Given this, we develop a practical and readily-applicable AP-side solution, called ACT-AP, which avoids multicast packet losses by preventing STA from operating in PSM. Our prototype implementation with off-the-shelf chipsets demonstrates that ACT-AP improves packet delivery ratio by up to 216% with little additional protocol overhead. To our best knowledge, ACT-AP is the first practical effort to support multicast to real devices with undesired functions in PSM.
【Keywords】: Power system management; Wireless LAN; Unicast; Packet loss; Semiconductor device measurement; IEEE 802.11 Standard
【Paper Link】 【Pages】:1-9
【Authors】: Ramanujan K. Sheshadri ; Dimitrios Koutsonikolas
【Abstract】: The knowledge of link packet loss rates (PLRs) at different PHY layer configurations is vital for a number of wireless network optimization schemes. However, the very large number of PHY layer configurations offered by modern 802.11 n/ac networks has made probing-based PLR estimation at each available configuration extremely challenging. In this paper, we seek to answer the question “How to estimate the PLRs at each available PHY layer configuration with minimal overhead?” Our analysis of the PLR datasets collected from three 802.11 n/ac testbeds reveals that, for any given link, there are several configurations with similar PLR. However, capturing this similarity using well-known link quality indicators like RSSI, or PHY layer features such as MCS or number of MIMO streams is hard. Consequently, we explore the approach of clustering the available PHY layer configurations into a small number of clusters with similar PLR, independent of any other parameter, and only probe one representative configuration in each cluster. Using two real-world case studies - rate adaptation and multihop routing, we show that the proposed clustering-based PLR estimation helps network optimization schemes to reach optimal configurations faster leading to significant performance improvements.
【Keywords】: MIMO; IEEE 802.11n Standard; Bit rate; Estimation; Probes
【Paper Link】 【Pages】:1-9
【Authors】: Alessio Marcone ; Massimiliano Pierobon ; Maurizio Magarini
【Abstract】: Molecular Communication (MC) is an enabling paradigm for the interconnection of future devices and networks in the biological environment, with applications ranging from bio-medicine to environmental monitoring and control. The engineering of biological circuits, which allows to manipulate the molecular information processing abilities of biological cells, is a candidate technology for the realization of MC-enabled devices. In this paper, inspired by recent studies favoring the efficiency of analog computation over digital in biological cells, an analog decoder design is proposed based on biological circuit components. In particular, this decoder computes the a-posteriori log-likelihood ratio of parity-check-encoded bits from a binary-modulated concentration of molecules. The proposed design implements the required L-value and the box-plus operations entirely in the biochemical domain by using activation and repression of gene expression, and reactions of molecular species. Each component of the circuit is designed and tuned in this paper by comparing the resulting functionality with that of the corresponding analytical expression. Despite evident differences with classical electronics, biochemical simulation data of the resulting biological circuit demonstrate very close performance in terms of Mean Squared Error (MSE) and Bit Error Rate (BER), and validate the proposed approach for the future realization of MC components.
【Keywords】: Biological information theory; Cells (biology); Decoding; Proteins; Transmitters; Receivers; Mathematical model
【Paper Link】 【Pages】:1-9
【Authors】: Stefano Basagni ; Valerio Di Valerio ; Petrika Gjanci ; Chiara Petrioli
【Abstract】: This paper concerns the smart exploitation of multimodal communication capabilities of underwater nodes to enable reliable and swift underwater networking. To contrast adverse and highly varying channel conditions we define a smart framework enabling nodes to acquire knowledge on the quality of the communication to neighboring nodes over time. Following a model-based reinforcement learning approach, our framework allows senders to select the best forwarding relay for its data jointly with the best communication device to reach that relay. We name the resulting forwarding method MARLIN, for MultimodAl Reinforcement Learning-based RoutINg. Applications can choose whether to seek reliable routes to the destination, or whether faster packet delivery is more desirable. We evaluate the performance of MARLIN in varying networking scenarios where nodes communicate through two acoustic modems with widely different characteristics. MARLIN is compared to state-of-the-art forwarding protocols, including a channel-aware solution, a machine learning-based solution and to a flooding protocol extended to use multiple modems. Our results show that a smartly learned selection of relay and modem is key to obtain a packet delivery ratio that is twice as much that of other protocols, while maintaining low latencies and energy consumption.
【Keywords】: Underwater Wireless Sensor Networks; multimodal communications; reinforcement learning-based routing
【Paper Link】 【Pages】:1-9
【Authors】: Giuseppe Enrico Santagati ; Tommaso Melodia
【Abstract】: Wirelessly networked systems of implantable medical devices endowed with sensors and actuators will be the basis of many innovative, sometimes revolutionary therapies. The biggest obstacle in realizing this vision of networked implantable devices is posed by the dielectric nature of the human body, which strongly attenuates radio-frequency (RF) electromagnetic waves. In this paper we present the first hardware and software architecture of an Internet of Medical Things (IoMT) platform with ultrasonic connectivity for intra-body communications that can be used as a basis for building future IoT-ready medical implantable and wearable devices. We show that ultrasonic waves can be efficiently generated and received with low-power and mm-sized components, and that despite the conversion loss introduced by ultrasonic transducers the gap in attenuation between 2.4 GHz RF and ultrasonic waves is still substantial, e.g., ultrasounds offer 70 dB less attenuation over 10 cm. We show that the proposed IoMT platform requires much lower transmission power compared to 2.4 GHz RF with equal reliability in tissues, e.g., 35 dBm lower over 12 cm for 10-3 Bit Error Rate (BEr) leading to lower energy per bit and longer device lifetime. Finally, we show experimentally that 2.4 GHz RF links are not functional at all above 12 cm, while ultrasonic links achieve a reliability of 10-6 up to 20 cm with less than 0 dBm transmission power.
【Keywords】: Acoustics; Radio frequency; Sensors; Implants; Hardware; Wireless communication; Field programmable gate arrays
【Paper Link】 【Pages】:1-9
【Authors】: Zhenghao Zhang ; Piyush Kumar
【Abstract】: Error estimation code estimates the bit error ratio of the received data bits with low overhead. It has many applications, especially in estimating the number of errors in a packet transmitted over a wireless link. In this paper, we propose a novel error estimation code, mEEC, that outperforms the existing code by more than 10%-20% depending on the packet sizes, at the same time being less biased. mEEC is mainly based on the idea of grouping multiple blocks of sampled data bits into a super-block, thus creating a multi-dimensional feature. It then compresses these features into a single number, called the color, as the coded bits. Through an intelligent coloring scheme, the blocks in a super-block share the cost of covering low probability events, which allows the decoder to recover the actual feature values from the color even in the presence of error. mEEC also adopts a lightweight redistribution step, which is guided by the solution of an optimization problem and further reduces the estimation errors and bias. We also show that mEEC can be implemented with reasonable storage sizes and low time complexity.
【Keywords】: Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Heng Pan ; Gaogang Xie ; Zhenyu Li ; Peng He ; Laurent Mathy
【Abstract】: Software-Defined Networking (SDN) provides network administrators opportunities to control network devices more simply and easily than in traditional networking. However, heterogeneity in switch hardware, especially in forwarding pipeline architecture, renders the task of network application developers and network administrators tedious, by hampering portability across switch models. In this paper, we propose FlowConvertor, an algorithm capable of converting rules from any forwarding pipeline to any other different forwarding pipeline, as long as both pipelines offer compatible operations. More precisely, FlowConvertor is an online algorithm that operates on flow updates issued to the origin pipeline and computes the corresponding updates for the target pipeline in real time. Performance evaluation shows that the latency introduced by FlowConvertor on the path between the SDN controller and the target switch is of the order of 1ms in most cases, and is thus acceptable for practical deployment.
【Keywords】: Switches; Pipelines; Metadata; Pipeline processing; Hardware; Engines; Ports (Computers)
【Paper Link】 【Pages】:1-9
【Authors】: Konstantinos Poularakis ; George Iosifidis ; Georgios Smaragdakis ; Leandros Tassiulas
【Abstract】: Nowadays, there is a fast-paced shift from legacy telecommunication systems to novel Software Defined Network (SDN) architectures that can support on-the-fly network reconfiguration, therefore, empowering advanced traffic engineering mechanisms. Despite this momentum, migration to SDN cannot be realized at once especially in high-end cost networks of Internet Service Providers (ISPs). It is expected that ISPs will gradually upgrade their networks to SDN over a period that spans several years. In this paper, we study the SDN upgrading problem in an ISP network: which nodes to upgrade and when. We consider a general model that captures different migration costs and network topologies, and two plausible ISP objectives; first, the maximization of the traffic that traverses at least one SDN node, and second, the maximization of the number of dynamically selectable routing paths enabled by SDN nodes. We leverage the theory of submodular and supermodular functions to devise algorithms with provable approximation ratios for each objective. Using real-world network topologies and traffic matrices, we evaluate the performance of our algorithms and show up to 54% gains over state-of-the-art methods. Moreover, we describe the interplay between the two objectives; maximizing one may cause a factor of 2 loss to the other.
【Keywords】: Approximation algorithms; Routing; Network topology; Routing protocols; Conferences; Optimization
【Paper Link】 【Pages】:1-9
【Authors】: Haopei Wang ; Abhinav Srivastava ; Lei Xu ; Sungmin Hong ; Guofei Gu
【Abstract】: The need of customized network functions for enterprises in Infrastructure-as-a-Service (IaaS) clouds is emerging. However, existing network functions in IaaS clouds are very limited, inflexible, and hard to control by the tenants. Recently, the introduction of Software-Defined Networking (SDN) technology brings the hope of flexible control of network flows and creation of diverse network functions. Unfortunately, enterprises lose access to the SDN controller when they move to clouds. Moreover, the cloud SDN controller is only managed by the provider administrators for security and performance reasons. To allow enterprise tenants to develop and deploy their own SDN apps in the cloud, in this paper, we introduce a new cloud usage paradigm: Bring Your Own Controller (BYOC). BYOC offers each tenant an individual SDN controller, where tenants can deploy SDN apps to manage their network. To manage these tenant SDN controllers, we propose BYOC-Visor, a new SDN-based virtualization platform. BYOC-VISOR addresses several security and performance challenges which are specific to IaaS clouds. We show that BYOC-Visor supports different controller platforms and diverse SDN security applications such as firewall, IDS, and access control. We implement a prototype system and the performance evaluation results show that our system has low overhead.
【Keywords】: Cloud computing; Topology; Network topology; Security; Control systems; Virtualization; Prototypes
【Paper Link】 【Pages】:1-9
【Authors】: Hesham Mekky ; Fang Hao ; Sarit Mukherjee ; T. V. Lakshman ; Zhi-Li Zhang
【Abstract】: Software Defined Networking (SDN) can benefit a Network Function Virtualization solution by chaining a set of network functions (NF) to create a network service. Currently, control on NFs is isolated from the SDN, which creates routing inflexibility, flow imbalance and choke points in the network as the controller remains oblivious to the number, capacity and placement of NFs. Moreover, a NF may modify packets in the middle, which makes flow identification at a SDN switch challenging. In this paper, we postulate native NFs within the SDN data plane, where the same logical controller controls both network services and routing. This is enabled by extending SDN to support stateful flow handling based on higher layers in the packet beyond layers 2-4. As a result, NF instances can be chained on demand, directly on the data plane. We present an implementation of this architecture based on Open vSwitch, and show that it enables popular NFs effectively using detailed evaluation and comparison with other alternative solutions.
【Keywords】: Switches; Noise measurement; Kernel; Routing; Inductors
【Paper Link】 【Pages】:1-9
【Authors】: Chase Q. Wu
【Abstract】: An increasing number of high-performance networks are built over the existing IP network infrastructure to provision dedicated channels for big data transfer. The links in these overlay networks correspond to underlying paths and may share lower-level link segments. We consider a model of overlay networks that incorporates correlated link capacities and linear capacity constraints (LCCs) to formulate such shared bottleneck components. The overlay links are typically shared by multiple users through advance reservations, resulting in varying bandwidth availability in future time. Therefore, efficient bandwidth scheduling algorithms are needed to improve the network resource utilization and also meet the user's transport requirements. We investigate two advance scheduling problems in overlay networks with LCCs: Fixed-Bandwidth Path and Varying-Bandwidth Path, with the objective to minimize the data transfer end time for a given data size. We prove that both problems are NP-complete and non-approximable, and propose heuristic algorithms using a gradual relaxation procedure on the maximum number of links from each LCC allowed for path computation. The performance superiority of these heuristics is verified by extensive simulation results in comparison with optimal and greedy strategies.
【Keywords】: bandwidth scheduling; overlay networks; approximate algorithm
【Paper Link】 【Pages】:1-9
【Authors】: Parisa Rahimzadeh ; Carlee Joe-Wong ; Kyuyong Shin ; Youngbin Im ; Jongdeog Lee ; Sangtae Ha
【Abstract】: Video streaming applications based on Peer-to-Peer (P2P) systems are popular for their scalability, which is hard to achieve with traditional client-server approaches. In particular, layered video streaming has been much-studied due to its ability to differentiate users' streaming qualities in heterogeneous user environments. Previous work, however, has shown that user misbehavior (e.g., free-riding and protocol deviation) poses a serious threat to P2P systems that are not equipped with proper incentive mechanisms. We propose a method to disincentivize such misbehavior. Our SVC-TChain is a layered P2P video streaming method based on scalable video coding (SVC), which uses the recently proposed T-Chain incentive mechanism to discourage free-riding. After introducing T-Chain, we present the first analytical framework to study SVC piece selection with multiple video layers, using it to efficiently choose SVC-TChain's optimal piece selection parameters and thus discourage deviations from the piece selection policy. Extensive experimental results show that SVC-TChain outperforms layered extensions of BiTos and Give-to-Get, two popular P2P video streaming approaches, both in the absence of user misbehavior and when some users misbehave.
【Keywords】: Streaming media; Static VAr compensators; Video coding; Peer-to-peer computing; Standards; Encryption
【Paper Link】 【Pages】:1-9
【Authors】: Omer Bilgen ; Aaron B. Wagner
【Abstract】: Recent studies have suggested that the stability of peer-to-peer networks may rely on persistent peers, who dwell on the network after they obtain the entire file. In the absence of such peers, one piece becomes extremely rare in the network, which leads to instability. Technological developments, however, are poised to reduce the incidence of persistent peers, giving rise to a need for a protocol that guarantees stability with nonpersistent peers. We propose a novel peer-to-peer protocol, the group suppression protocol, to ensure the stability of peer-to-peer networks under the scenario that all the peers adopt non-persistent behavior. Using a suitable Lyapunov potential function, the group suppression protocol is proven to be stable when the file is broken into two pieces, and detailed experiments demonstrate the stability of the protocol for arbitrary number of pieces. Straightforward incorporation of the group suppression protocol into BitTorrent while retaining most of BitTorrent's core mechanisms is also presented. Subsequent simulations show that under certain assumptions, BitTorrent with the official protocol cannot escape from the missing piece syndrome, but BitTorrent with group suppression does.
【Keywords】: Protocols; Stability analysis; Peer-to-peer computing; Wireless communication; Conferences; Mobile communication; Servers
【Paper Link】 【Pages】:1-9
【Authors】: Bruce Spang ; Anirudh Sabnis ; Ramesh K. Sitaraman ; Donald F. Towsley ; Brian DeCleene
【Abstract】: Large organizations often have users in multiple sites which are connected over the Internet. Since resources are limited, communication between these sites needs to be carefully orchestrated for the most benefit to the organization. We present a Mission-optimized Overlay Network (MON), a hybrid overlay network architecture for maximizing utility to the organization. We combine an offline and an online system to solve non-concave utility maximization problems. The offline tier, the Predictive Flow Optimizer (PFO), creates plans for routing traffic using a model of network conditions. The online tier, MONtra, is aware of the precise local network conditions and is able to react quickly to problems within the network. Either tier alone is insufficient. The PFO may take too long to react to network changes. MONtra only has local information and cannot optimize non-concave mission utilities. However, by combining the two systems, MON is robust and achieves near-optimal utility under a wide range of network conditions. While best-effort overlay networks are well studied, our work is the first to design overlays that are optimized for mission utility.
【Keywords】: Optimization; Organizations; Overlay networks; Computer architecture; Routing; Internet telephony
【Paper Link】 【Pages】:1-9
【Authors】: László Toka ; Balázs Lajtha ; Éva Hosszu ; Bence Formanek ; Daniel Gehberger ; János Tapolcai
【Abstract】: Internet of Things (IoT) systems produce great amount of data, but usually have insufficient resources to process them in the edge. Several time-critical IoT scenarios have emerged and created a challenge of supporting low latency applications. At the same time cloud computing became a success in delivering computing as a service at affordable price with great scalability and high reliability. We propose an intelligent resource allocation system that optimally selects the important IoT data streams to transfer to the cloud for processing. The optimization runs on utility functions computed by predictor algorithms that forecast future events with some probabilistic confidence based on a dynamically recalculated data model. We investigate ways of reducing specifically the upload bandwidth of IoT video streams and propose techniques to compute the corresponding utility functions. We built a prototype for a smart squash court and simulated multiple courts to measure the efficiency of dynamic allocation of network and cloud resources for event detection during squash games. By continuously adapting to the observed system state and maximizing the expected quality of detection within the resource constraints our system can save up to 70% of the resources compared to the naive solution.
【Keywords】: Internet of Things; cloud computing; cloud control; resource provisioning; adaptive; dynamic; QoS; QoE
【Paper Link】 【Pages】:1-9
【Authors】: Demetris Trihinas ; George Pallis ; Marios D. Dikaiakos
【Abstract】: As more knowledge is vastly added to the devices fuelling the Internet of Things (IoT) energy efficiency and real-time data processing are great challenges that must be tackled. In this paper, we introduce ADMin, a low-cost IoT framework that reduces on device energy consumption and the volume of data disseminated across the network. This is achieved by efficiently adapting the rate at which IoT devices disseminate monitoring streams based on run-time knowledge of the stream evolution, variability and seasonal behavior. Rather than transmitting the entire stream, ADMin favors sending updates for its estimation model from which values can be inferred, triggering dissemination only when shifts in the stream evolution are detected. Results on real-life testbeds, show that ADMin is able to reduce energy consumption by at least 83%, data volume by 71%, shift detection delays by 61% while maintaining accuracy above 91% in comparison to other IoT frameworks.
【Keywords】: Measurement; Monitoring; Estimation; Adaptation models; Energy consumption; Receivers; Sensors
【Paper Link】 【Pages】:1-9
【Authors】: Jiansong Zhang ; Zeyu Wang ; Zhice Yang ; Qian Zhang
【Abstract】: Internet of Things (IoT) devices are largely embedded devices which lack a sophisticated user interface, e.g., touch screen, keyboard, etc. As a consequence, traditional Pre-Shared Key (PSK) based authentication for mobile devices becomes difficult to apply. For example, according to our study on home automation devices which leverage smartphone for PSK input, the current process does not protect against active impersonating attack and also leaks the Wi-Fi password to eavesdroppers, i.e., currently these IoT devices can be exploited to enter into critical infrastructures, e.g., home networks. Motivated by this real-world security vulnerability, in this paper we propose a novel proximity-based mechanism for IoT device authentication, called Move2Auth, for the purpose of enhancing IoT device security. In Move2Auth, we require user to hold smartphone and perform one of two hand-gestures (moving towards and away, and rotating) in front of IoT device. By combining (1) large RSS-variation and (2) matching between RSS-trace and smartphone sensor-trace, Move2Auth can reliably detect proximity and authenticate IoT device accordingly. Based on our implementation on Samsung Galaxy smartphone and commodity Wi-Fi adapter, we prove Move2Auth can protect against powerful active attack, i.e., the false-positive rate is consistently lower than 0.5%.
【Keywords】: Wireless fidelity; Authentication; Home automation; Cryptography; Performance evaluation; Phase shift keying
【Paper Link】 【Pages】:1-9
【Authors】: So-Yeon Park ; Sunil Lim ; Dahee Jeong ; Jungjin Lee ; Joon-Sung Yang ; HyungJune Lee
【Abstract】: A low-end embedded platform for Internet of Things (IoT) often suffers from a critical trade-off dilemma between security enhancement and computation overhead. We propose PUFSec, a new device fingerprint-based security architecture for IoT devices. By leveraging intrinsic hardware characteristics, we aim to design a computationally lightweight security software system architecture so that complex cryptography computation can dramatically be prohibited. We exploit the innovative idea of Public Physical Unclonable Functions (PPUFs) that fundamentally protects attackers from recovering the secret key from public gate delay information. We implement its hardware logic in a real-world FPGA board. On top of the PPUF fingerprint hardware, we present an adaptive security control mechanism consisting of adaptive key generation and key exchange protocol, which adjusts security strength depending on system load dynamics. We demonstrate that our PPUF FPGA implementation embeds distinctive variability enough to distinguish between two different PPUFs with high fidelity. We validate our PUFSec architecture by implementing necessary algorithms and protocols in a real-world IoT platform, and performing empirical evaluation in terms of computation and memory usages, proving its practical feasibility.
【Keywords】: Hardware; Logic gates; Delays; Cryptography; Software; Radiation detectors
【Paper Link】 【Pages】:1-9
【Authors】: Kathleen Sucipto ; Dimitris Chatzopoulos ; Sokol Kosta ; Pan Hui
【Abstract】: The increasing complexity of smartphone applications and services necessitate high battery consumption but the growth of smartphones' battery capacity is not keeping pace with these increasing power demands. To overcome this problem, researchers gave birth to the Mobile Cloud Computing (MCC) research area. In this paper we advance on previous ideas, by proposing and implementing the first known Near Field Communication (NFC)-based computation offloading framework. This research is motivated by the advantages of NFC's short distance communication, with its better security, and its low battery consumption. We design a new NFC communication protocol that overcomes the limitations of the default protocol; removing the need for constant user interaction, the one-way communication restraint, and the limit on low data size transfer. We present experimental results of the energy consumption and the time duration of two computationally intensive representative applications: (i) RSA key generation and encryption, and (ii) gaming/puzzles. We show that when the helper device is more powerful than the device offloading the computations, the execution time of the tasks is reduced. Finally, we show that devices that offload application parts considerably reduce their energy consumption due to the low-power NFC interface and the benefits of offloading.
【Keywords】: Protocols; Batteries; Wireless fidelity; Androids; Humanoid robots; Mobile communication; Bluetooth
【Paper Link】 【Pages】:1-9
【Authors】: Sladana Josilo ; György Dán
【Abstract】: Offloading computation to a mobile cloud is a promising approach for enabling the use of computationally intensive applications by mobile devices. In this paper we consider autonomous devices that maximize their own performance by choosing one of many wireless access points for computation offloading. We develop a game theoretic model of the problem, prove the existence of pure strategy Nash equilibria, and provide a polynomial time algorithm for computing an equilibrium. For the case when the cloud computing resources scale with the number of mobile devices we show that all improvement paths are finite. We provide a bound on the price of anarchy of the game, thus our algorithm serves as an approximation algorithm for the global computation offloading cost minimization problem. We use extensive simulations to provide insight into the performance and the convergence time of the algorithms in various scenarios. Our results show that the equilibrium cost may be close to optimal, and the convergence time is almost linear in the number of mobile devices.
【Keywords】: Mobile handsets; Games; Cloud computing; Mobile communication; Approximation algorithms; Computational modeling; Performance evaluation
【Paper Link】 【Pages】:1-9
【Authors】: Jaya Prakash Champati ; Ben Liang
【Abstract】: We study the problem of scheduling n tasks on m + m' parallel processors, where the processing times on m processors are known while those on the remaining m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with the m known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m' = 1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(n log n). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on m. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m' > 1. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.
【Keywords】: Program processors; Processor scheduling; Cloud computing; Computational modeling; Servers; Heuristic algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Meng-Hsi Chen ; Ben Liang ; Min Dong
【Abstract】: We consider a general multi-user mobile cloud computing system with a computing access point (CAP), where each mobile user has multiple independent tasks that may be processed locally, at the CAP, or at a remote cloud server. The CAP serves both as the network access gateway and a computation service provider to the mobile users. We aim to jointly optimize the offloading decisions of all users' tasks as well as the allocation of computation and communication resources, to minimize the overall cost of energy, computation, and delay for all users. This problem is NP-hard in general. We propose an efficient three-step algorithm comprising of semidefinite relaxation (SDR), alternating optimization (AO), and sequential tuning (ST). It is shown to always compute a locally optimal solution, and give nearly optimal performance under a wide range of parameter settings. Through evaluating the performance of different combinations of the three components of this SDR-AO-ST algorithm, we provide insights into their roles and contributions in the overall solution. We further compare the performance of SDR-AO-ST against a lower bound to the minimum cost, purely local processing, purely cloud processing, and hybrid local-cloud processing without using the CAP. Our numerical results demonstrate the effectiveness of the proposed algorithm in the joint management of computation and communication resources in mobile cloud computing systems with a CAP.
【Keywords】: Mobile communication; Delays; Cloud computing; Servers; Resource management; Mobile handsets
【Paper Link】 【Pages】:1-9
【Authors】: Yiming Zhang ; Dongsheng Li ; Tian Tian ; Ping Zhong
【Abstract】: RAM-based storage aggregates the RAM of servers in data center networks (DCN) to provide extremely high storage performance. For quick recovery of storage server failures, Mem-Cube [1] exploits the proximity of the BCube network to limit the recovery traffic to the recovery servers' 1-hop neighborhood. However, previous design is applicable only to BCube, and has suboptimal recovery performance due to congestion and contention. To address these problems, in this paper we propose CubeX, which generalizes the “1-hop” principle of MemCube for all cube-based networks, and improves the throughput and recovery performance of RAM-based key-value (KV) store via cross-layer optimizations. At the core of CubeX is to leverage the glocality (= globality + locality) of cube-based networks: it scatters backup data across a large number of disks globally distributed throughout the cube, and restricts all recovery traffic within the small local range of each server node. Our evaluation shows that CubeX efficiently supports RAM-based KV store for cube-based networks, and CubeX remarkably outperforms MemCube in both throughput and recovery time.
【Keywords】: Servers; Random access memory; Throughput; Hypercubes; Bandwidth; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Feng Wang ; Lixin Gao ; Xiaozhe Shao ; Hiroaki Harai ; Kenji Fujikawa
【Abstract】: A low-latency and reliable message switching network is critical for constructing high-speed datacenter networks. In this paper, we present the design, implementation, and evaluation of a novel Location basEd Source Switching (LESS) for datacenter networks. LESS enables lightweight source switching through a location-based addressing scheme. Each switch and host can independently derive a source route to reach a destination without requiring the full knowledge of the network topology. We demonstrate that using location-based source routes as forwarding labels allows LESS to eliminate the need for routing tables and integrate with minimum required functionality for packet forwarding. Moreover, we propose a fast rerouting solution to address the issue of fault tolerance in source routing. Each switch can locally derive an alternative source route during a failure. The paper evaluates the performance of LESS. Our evaluation results suggest that LESS improves the performance of datacenter networks in terms of latency, throughput, and reliability.
【Keywords】: Switches; Ports (Computers); Topology; Network topology; Routing; Reliability; IP networks
【Paper Link】 【Pages】:1-9
【Authors】: Jingyuan Fan ; Chaowen Guan ; Yangming Zhao ; Chunming Qiao
【Abstract】: Network Function Virtualization (NFV) is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named Service Function Chain (SFC) mapping, with which different network services are deployed over virtualized and shared platforms in data centers. However, such an evolution towards software-defined network functions introduces new challenges to network services which require high availability. One effective way of protecting the network services is to use sufficient redundancy. By doing so, however, the efficiency of physical resources may be greatly decreased. To address such an issue, this paper defines an optimal availability-aware SFC mapping problem and presents a novel online algorithm that can minimize the physical resources consumption while guaranteeing the required high availability within a polynomial time. Simulation results show that our proposed algorithm can significantly improve SFC mapping request acceptance ratio and reduce resource consumption.
【Keywords】: Redundancy; Delays; Computational modeling; Bandwidth; Conferences; Approximation algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Hiroshi Saito ; Hirotada Honda ; Ryoichi Kawahara
【Abstract】: This paper proposes a disaster avoidance control method for use against heavy rainfall and discusses its effectiveness through actual weather data. The proposed control method uses geographical information data including weather data, hazard area data, and physical network data. By applying technologies related to meteorology, erosion control, and civil engineering to such data, the proposed method can evaluate the risk of a physical network being disconnected. On the basis of the evaluated risk, the proposed method reconfigures a logical network to reduce service disruption. The proposed method is applied to a cloud computing service network where, in addition to route changes, the relocation of virtual machines is possible, increasing its effectiveness. By using empirical data, we show that the proposed method reduces the probability of service disconnection to almost zero even for heavy rainfall causing landslides. Finally, an experimental system of the proposed method was implemented through software defined network technology and successfully controlled the experimental network.
【Keywords】: Hazards; Measurement; Rain; Control systems; Conferences; Terrain factors
【Paper Link】 【Pages】:1-9
【Authors】: Mahmoud Ashour ; Jingyao Wang ; Constantino Lagoa ; Necdet Serhat Aybat ; Hao Che
【Abstract】: This paper proposes an algorithm for optimal decentralized traffic engineering in communication networks. We aim at distributing the traffic among the available routes such that the network utility is maximized. In some practical applications, modeling network utility using non-concave functions is of particular interest, e.g., video streaming. Therefore, we tackle the problem of optimizing a generalized class of non-concave utility functions. The approach used to solve the resulting non-convex network utility maximization (NUM) problem relies on designing a sequence of convex relaxations whose solutions converge to that of the original problem. A distributed algorithm is proposed for the solution of the convex relaxation. Each user independently controls its traffic in a way that drives the overall network traffic allocation to an optimal operating point subject to network capacity constraints. All computations required by the algorithm are performed independently and locally at each user using local information and minimal communication overhead. The only non-local information needed is binary feedback from congested links. The robustness of the algorithm is demonstrated, where the traffic is shown to be automatically rerouted in case of a link failure or having new users joining the network. Numerical simulation results are presented to validate our findings.
【Keywords】: Distributed optimization; non-concave utility maximization; traffic engineering
【Paper Link】 【Pages】:1-9
【Authors】: Peng-Jun Wan ; Fahad Al-dhelaan ; Huaqiang Yuan ; Sai Ji
【Abstract】: Fractional Link scheduling is one of the most fundamental problems in wireless networks. The prevailing approach for shortest fractional link scheduling is based on a reduction to the maximum-weighted independent set problem, which itself may not admit efficient approximation algorithms. In addition, except for the wireless networks under the protocol interference model, none of the existing scheduling algorithms can produce a link schedule with explicit upper bounds on its length in terms of the link demands. As the result, the polynomial approximate capacity regions in these networks remain blank. This paper develops a purely combinatorial paradigm for fractional link scheduling in wireless networks. In addition to the superior efficiency, it is able to provide explicit upper bounds on the lengths of the produced link schedule. By exploiting these upper bounds, polynomial approximate capacity regions are derived. The effectiveness of this new paradigm is demonstrated by its applications in wireless networks under the physical interference model and wireless MIMO networks under the protocol interference model.
【Keywords】: Wireless networks; Interference; Schedules; Games; Approximation algorithms; Protocols; Upper bound
【Paper Link】 【Pages】:1-9
【Authors】: Hao Yu ; Michael J. Neely
【Abstract】: The backpressure algorithm has been widely used as a distributed solution to the problem of joint rate control and routing in multi-hop data networks. By controlling a parameter V in the algorithm, the backpressure algorithm can achieve an arbitrarily small utility optimality gap. However, this in turn brings in a large queue length at each node and hence causes large network delay. This phenomenon is known as the fundamental utility-delay tradeoff. The best known utility-delay tradeoff for general networks is [O(1/V), O(V)] and is attained by a backpressure algorithm based on a drift-pluspenalty technique. This may suggest that to achieve an arbitrarily small utility optimality gap, the existing backpressure algorithms necessarily yield an arbitrarily large queue length. However, this paper proposes a new backpressure algorithm that has a vanishing utility optimality gap, so utility converges to exact optimality as the algorithm keeps running, while queue lengths are bounded throughout by a finite constant. The technique uses backpressure and drift concepts with a new method for convex programming.
【Keywords】: Routing; Delays; Heuristic algorithms; Approximation algorithms; Conferences; Optimization; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Shay Vargaftik ; Isaac Keslassy ; Ariel Orda
【Abstract】: Network providers now want to enable users to define their own flow priorities, and commercial devices already implement this ability. However, it has been shown that directly applying arbitrary user-defined priorities can fundamentally destabilize a network. In this paper, we show that it is possible to apply user-defined priorities while keeping the network stable. We introduce U-BP, a scalable approach that extends backpressure-based scheduling techniques to service user-defined flow priorities and rates while maintaining throughput optimality and strong network performance. We explain how our approach relies on a dual-layer scheme with an exponential convergence to requested priorities. We further prove analytically the network stability of our solution, and show how it achieves a strong performance for high-priority flows.
【Keywords】: Stability analysis; Heuristic algorithms; Standards; Topology; Delays; Conferences; Throughput
【Paper Link】 【Pages】:1-9
【Authors】: Jia Liu ; Min Chen ; Shigang Chen ; Qing-feng Pan ; Lijun Chen
【Abstract】: Identifying an object's spatial direction (or orientation) plays a fundamental role in a variety of applications, such as automatic assembly, indoor navigation, and robot driving. In this paper, we design a fine-grained direction finding system called Tag-Compass that attaches a single tag to an object (whose size may be small) and identifies the tagged object's orientation by determining the spatial direction of the tag. We exploit the polarization properties of the RF waves used in the communications between an RFID reader and the tag on the object. Polarization mismatch between the tag and the reader's antenna affects the received signal strength at the reader. From the measured signal strength values, we are able to deduce the tag's direction through a series of transformations and deviation minimization. We propose a system design for Tag-Compass and implement a prototype. We evaluate the performance of TagCompass through extensive experiments using the prototype. The experimental results show that Tag-Compass provides accurate direction estimates with a median error of just 2.5° when the tag's position is known and a median error of 3.8° when the tag's position is unknown.
【Keywords】: Robots; Radiofrequency identification; Receivers; Transmitters; Object recognition; Directive antennas; Radio frequency
【Paper Link】 【Pages】:1-9
【Authors】: Shigeng Zhang ; Xuan Liu ; Jianxin Wang ; Jiannong Cao
【Abstract】: In this paper, we study the tag size profiling (TSP) problem in RFID systems with multiple readers, which is to estimate the number of tags in every subregion in the system covered by different set of readers. The TSF problem is vitally important to reader scheduling and many other related operations in large scale multi-reader RFID systems. To our knowledge, however, it is not well solved in previous researches. We propose a novel approach to the TSF problem. The key idea is to treat the size of subregions as variables and construct a linear system in these variables to solve them. We theoretically prove that for any multi-reader RFID system, a linear system that can be used to uniquely solve the variables corresponding to the subregion sizes can always be constructed. We then propose a time-efficient algorithm that uses two heuristics to quickly find enough linearly independent equations to construct the linear system. Extensive simulation results show that the proposed approach achieves very high accuracy. When the estimation results of individual readers contain 5% errors, our approach achieves median estimation error of smaller than 0.02 and 90-percentile estimation error of smaller than 0.04 in large systems containing more than one hundred readers.
【Keywords】: Radio Frequency Identification; Multiple Readers; Reader Scheduling; RFID Estimation
【Paper Link】 【Pages】:1-9
【Authors】: Chunhui Duan ; Xing Rao ; Lei Yang ; Yunhao Liu
【Abstract】: In recent years, both the RFID and computer vision technologies have been widely employed in indoor scenarios aimed at different goals while faced with respective limitations. For example, the RFID-based EAS system is useful in quickly identifying tagged objects but the accompanying false alarm problem is troublesome and hard to tackle with except that the accurate trajectory of the target tag can be easily acquired. On the other side, the CV system performs fairly well in tracking multiple moving objects precisely while finding it difficult to screen out the specific target among them. To overcome the above limitations, we present TagVision, a hybrid RFID and computer vision system for fine-grained localization and tracking of tagged objects. A fusion algorithm is proposed to organically combine the position information given by the CV subsystem, and phase data output by the RFID subsystem. In addition, we employ the probabilistic model to eliminate the measurement error caused by thermal noise and device diversity. We have implemented TagVision with COTS camera and RFID devices and evaluated it extensively in our lab environment. Experimental results show that TagVision can achieve 98% blob matching accuracy and 10.33mm location tracking precision.
【Keywords】: RFID; computer vision; tracking; TagVision
【Paper Link】 【Pages】:1-9
【Authors】: Chouchang Yang ; Jeremy Gummeson ; Alanson P. Sample
【Abstract】: Communication costs dominate the energy consumption, and ultimately limit the utility, of low power devices and sensor nodes. Backscatter communication based on deliberate and ambient sources has the potential to radically alter this paradigm by offering two to three orders of magnitude better communication efficiency (in terms of nJ/Bit) then conventional radio architectures. Initial work on ambient backscatter shows promising results but has focused on narrow band operation in well controlled laboratory settings. The goal of this work is to enable the ubiquitous deployment of ultra-low power nodes that communicate via ambient backscatter to wired Universal Backscatter Readers, in real-world environments. This is accomplished through ultra-wideband backscatter techniques that leverage the breath of commercial broadcast signals in the 80 MHz to 900 MHz range from FM radios, digital TVs, and cellular networks. Additionally the use of powered Universal Backscatter Readers allows a network of ultra-low power nodes to operate on ambient carriers as low as -80 dBm, which is typical for indoor home and office environments. For the first time we demonstrate the simultaneous use of 17 ambient signal sources to achieve node-to-reader communication distances of 50 meters, with data rates up to 1 kbps.
【Keywords】: Ultra-Wideband; Ambient Backscatter Communication; Sensor Node; Energy Harvesting
【Paper Link】 【Pages】:1-9
【Authors】: Chao Wu ; Yaoxue Zhang ; Lan Zhang ; Bowen Yang ; Xu Chen ; Wenwu Zhu ; Lili Qiu
【Abstract】: The ever increasing of display resolution on mobile devices raises high demand for GPU rendering details. However, the challenge of poor hardware support but fine-grained rendering details often makes user unsatisfied especially in calling for high frame rate scenarios, e.g., game. To resolve such issue, we propose BUTTERFLY, a novel system which collaboratively utilizes mobile GPUs to process high-quality rendering details for on-the-go mobile users. In particular, ButterFly achieves two technical contributions for the collaborative design: (1) a mobile device can migrate GPU workloads in buffer queue to peers, and (2) the collaborative rendering mechanism benefits user high quality details while significant power saving performance. Both techniques are compatible with the OpenGL ES standards. Furthermore, a 40-person survey perceives that ButterFly can provide excellent user experience of both rendering details and frame rate over Wi-Fi network. In addition, our comprehensive trace-driven experiments on Android prototype reveal the benefits of Butterfly have more superior performance over state-of-the-art systems, which achieves more than 28.3% power saving.
【Keywords】: Rendering (computer graphics); Graphics processing units; Mobile communication; Collaboration; Androids; Humanoid robots; Hardware
【Paper Link】 【Pages】:1-9
【Authors】: Changhua Pei ; Zhi Wang ; Youjian Zhao ; Zihan Wang ; Yuan Meng ; Dan Pei ; Yuanquan Peng ; Wenliang Tang ; Xiaodong Qu
【Abstract】: Today's WiFi networks deliver a large fraction of traffic. However, the performance and quality of WiFi networks are still far from satisfactory. Among many popular quality metrics (throughput, latency), the probability of successfully connecting to WiFi APs and the time cost of the WiFi connection set-up process are the two of the most critical metrics that affect WiFi users' experience. To understand the WiFi connection set-up process in real-world settings, we carry out measurement studies on 5 million mobile users from 4 representative cities associating with 7 million APs in 0.4 billion WiFi sessions, collected from a mobile “WiFi Manager” App that tops the Android/iOS App market. To the best of our knowledge, we are the first to do such large scale study on: how large the WiFi connection set-up time cost is, what factors affect the WiFi connection set-up process, and what can be done to reduce the WiFi connection set-up time cost. Based on our data-driven measurement and analysis, we reveal the insights as follows: (1) Connection set-up failure and large connection set-up time cost are common in today's WiFi use. As large as 45% of the users suffer connection set-up failures, and 15% (5%) of them have large connection set-up time costs over 5 seconds (10 seconds). (2) Contrary to the state-of-the-art work, scan, one of the subphase of four phases in the connection set-up process, contributes the most (47%) to the overall connection set-up time cost. (3) Mobile device model and AP model can greatly help us to predict the connection set-up time cost if we can make good use of the hidden information. Based on the measurement analysis, we develop a machine learning based AP selection strategy that can significantly improve WiFi connection set-up performance, against the conventional strategy purely based on signal strength, by reducing the connection set-up failures from 33% to 3.6% and reducing 80% time costs of the connection set-up processes by more than 10 times.
【Keywords】: Wireless fidelity; Mobile handsets; IP networks; Authentication; Mobile communication; Switches; Measurement
【Paper Link】 【Pages】:1-9
【Authors】: Faraz Ahmed ; Jeffrey Erman ; Zihui Ge ; Alex X. Liu ; Jia Wang ; He Yan
【Abstract】: It is crucial for cellular data network operators to understand the service quality perceived by its customers. The state-of-art systems deployed in cellular networks mostly report service quality aggregated on cell site level, which is typically an aggregation of tens or hundreds of customers depending on the locations of the cell sites. In this paper, we propose to enhance the measurement of customer-perceived service quality by leveraging M2M devices as sensors in the field, which provide an unprecedented opportunity for cellular network operators to measure what end-users experience with better accuracy and coverage. Our approach is to identify a set of M2M devices which are stationary and communicate continuously over the cellular network over an indefinite period of time. We use these M2M devices to estimate the customer-perceived service quality during cell site outages. We implement our methodology as a system called M2MScan and evaluate M2MScan with both synthetic outages and real outages from a large-scale operational cellular network. To the best of our knowledge, this is the first work that employs M2M devices to measure the service quality perceived by customers in operational cellular networks at a large scale.
【Keywords】: Machine-to-machine communications; Cellular networks; Monitoring; Object recognition; Performance evaluation; Sensors; Level measurement
【Paper Link】 【Pages】:1-9
【Authors】: Lei Xue ; Xiaobo Ma ; Xiapu Luo ; Le Yu ; Shuai Wang ; Ting Chen
【Abstract】: Many apps have been developed to measure the performance of mobile networks. Unfortunately, their measurement results may not be what users expect, because the results could be biased by various factors and the apps' descriptions may confuse users. Although a few recent studies pointed out several factors, they missed other important factors and lacked of finegrained analysis on the factors and measurement apps. Moreover, none has studied whether or not the descriptions of such apps will mislead users. In this paper, we conduct the first systematic study of the factors that could bias the result from measurement apps and their descriptions. We identify new factors, revisit known factors, and propose a novel approach with new tools to discover these factors in proprietary apps. We also develop a new measurement app named MobiScope for demonstrating how to mitigate the negative effects of these factors. Furthermore, we construct enhanced descriptions for measurement apps to provide users more information about what is measured. The extensive experimental results illustrate the negative effects of various factors, the improvement in performance measurement brought by MobiScope, and the clarity of the enhanced descriptions.
【Keywords】: Androids; Humanoid robots; Runtime; Delays; Mobile communication; Protocols; Smart phones
【Paper Link】 【Pages】:1-9
【Authors】: Zhibo Wang ; Yongquan Zhang ; Yijie Li ; Qian Wang ; Feng Xia
【Abstract】: Event-based Social Networks (EBSNs) which bridge the gap between online and offline interactions among users have received increasing popularity. The unique cold-start nature makes event recommendation more challenging than traditional recommendation problems, since even for two events with the same content, they may not happen at the same time, the same location, or be organized by the same host. Existing event recommendation algorithms mainly exploit the basic context information (e.g., location, time and content), while the social influence of event hosts and group members have been ignored. In this paper, we propose a Social Information Augmented Recommender System (SIARS), which fully exploits the social influence of event hosts and group members together with basic context information for event recommendation. In particular, we combine the information of EBSNs and other social networks to characterize the social influence of event hosts, and take interactions between group members into consideration for event recommendation. In addition, we propose a new content-aware recommendation model using the topic model to find the most similar topic the event belongs to, and a new location-aware recommendation model integrating location popularity with location distribution for event recommendation. Extensive experiments on real-world datasets demonstrate that SIARS outperforms other recommendation algorithms.
【Keywords】: Recommender systems; Conferences; Facebook; Twitter; Computer security; Collaboration
【Paper Link】 【Pages】:1-9
【Authors】: Bidisha Samanta ; Abir De ; Niloy Ganguly
【Abstract】: With social media platform such as Twitter becoming the de facto destination for users' views and opinions, it is of great importance to forecast an information outbreak. In Twitter, tweets are often annotated with hashtags to help its users to quickly extract their contents. The existing approaches for modeling the dynamics of tweet-messages are usually limited to individual or simple aggregates of tweets rather than the underlying hashtags. In this paper, we develop, STRM, a novel point process driven model that considers the effect of cross-tweet impact in hashtag popularity. STRM, by assuming hashtag to be a heterogeneous collection of tweet-chains. Through extensive experimentation, we find that our algorithm - STRM, shows consistent performance boosts with six diverse real datasets against several strong baselines. Moreover surprisingly, it also offers significant accuracy gains in popularity-prediction for individual tweets as compared with the existing paradigms.
【Keywords】: Twitter; Tagging; Computational modeling; Predictive models; Data models; Proposals; History
【Paper Link】 【Pages】:1-9
【Authors】: Xin Xu ; Chul-Ho Lee ; Do Young Eun
【Abstract】:
Graph sampling techniques via random walk crawling have been popular for analyzing statistical characteristics of large online social networks due to simple implementation and provable guarantees on unbiased estimates. Despite the growing popularity, the cost' of sampling and its true impact on the accuracy of estimates still have not been carefully studied. In addition, the random walk-based methods inherently suffer from the sluggish nature of random walks and theslow-mixing' structure of social graphs, thereby leading to high correlation in the samples obtained. With these in mind, in this paper, we develop a mathematical framework such that the cost of sampling is properly taken into account, which in turn re-defines a widely used asymptotic variance into a cost-based asymptotic variance. Our new metric enables us to compare a class of sampling policies under the same cost constraint, integrating “random skipping” (bypassing nodes without sampling) into the random walk-based sampling. We obtain an optimal policy striking the right balance between sampling quality (less correlation) and sampling quantity (higher cost per sample), which greatly improves over the usual skip-free crawling-based samplers. We further extend our framework, enabling one to design more sophisticated sampling strategies with an array of control knobs, which all produce unbiased estimates under the same cost constraint.
【Keywords】: Web pages; Crawlers; Social network services; Conferences; Correlation; Measurement; Sampling methods
【Paper Link】 【Pages】:1-9
【Authors】: Qiongzheng Lin ; Lei Yang ; Yunhao Liu
【Abstract】: Millions of people nowadays share their television (TV) experience with other people through social media like Twitter or Facebook with mobile devices. It is generally believed that TV has been repurposed for social networks, called as social television. A key functionality of social television is that it allows the viewers to interchange their comments through mobile devices, thus creating the impression of watching TV like alongside a group of friends. To do so, mobile devices have to be aware of the current media context (identifier and progress) of what the TV is playing, known as synchronizing context from TVs to mobile devices. Unfortunately, most legacy systems are not able to track the playing progresses or need to upgrade TV devices. To address the issue, we design a purely software-based solution, called as TagScreen, which inserts a series of hidden sound markers into the audio of the content. TagScreen supports longrange or multipath-resistant synchronization at second-level, being independent of device diversity over severely frequency-selective acoustic channels. We implement TagScreen by using COTS TVs and mobile devices. The system has been extensively tested on 150 movies and 150 TV series across five different environments. Results show that TagScreen has a mean recognition accuracy of 98% up to 35m, and a mean tracking accuracy of 97%.
【Keywords】: TV; Mobile handsets; Media; Social network services; Synchronization; Motion pictures; Frequency modulation
【Paper Link】 【Pages】:1-9
【Authors】: Qingkai Liang ; Eytan Modiano
【Abstract】: A coflow is a collection of parallel flows belonging to the same job. It has the all-or-nothing property: a coflow is not complete until the completion of all its constituent flows. In this paper, we focus on optimizing coflow-level delay, i.e., the time to complete all the flows in a coflow, in the context of an N × N input-queued switch. In particular, we develop a throughput-optimal scheduling policy that achieves the best scaling of coflow-level delay as N → ∞. We first derive lower bounds on the coflow-level delay that can be achieved by any scheduling policy. It is observed that these lower bounds critically depend on the variability of flow sizes. Then we analyze the coflow-level performance of some existing coflow-agnostic scheduling policies and show that none of them achieves provably optimal performance with respect to coflow-level delay. Finally, we propose the Coflow-Aware Batching (CAB) policy which achieves the optimal scaling of coflow-level delay under some mild assumptions.
【Keywords】: Delays; Scheduling; Optimal scheduling; Processor scheduling; Ports (Computers)
【Paper Link】 【Pages】:1-9
【Authors】: Wei Wang ; Shiyao Ma ; Bo Li ; Baochun Li
【Abstract】: Fair and efficient coflow scheduling improves application-level networking performance in today's datacenters. Ideally, a coflow scheduler should provide isolation guarantees on the minimum coflow progress to achieve predictable networking performance. Network operators, on the other hand, strive to decrease the average coflow completion time (CCT). Unfortunately, optimal isolation guarantees and minimum average CCT are conflicting objectives and cannot be achieved at the same time. Existing coflow schedulers either optimize isolation guarantees at the expense of long CCTs (e.g., HUG [1]), or decrease the average CCT without performance isolation (e.g., Varys and Aalo [2], [3]). The lack of a smooth tradeoff in between poses a dilemma between low efficiency and no performance isolation. To bridge this gap, we develop a new coflow scheduler, Coflex, to navigate this tradeoff. Coflex allows network operators to specify the desired level of isolation guarantee using a tunable fairness knob, while at the same time decreasing the average CCT. Both our real-world deployments and trace-driven simulations have shown that Coflex offers a smooth tradeoff between fairness and efficiency. At an appropriate tradeoff level, Coflex outperforms fair schedulers by 2 × in minimizing the average CCT.
【Keywords】: Bandwidth; Resource management; Fabrics; Navigation; Production; Silicon; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Chang-Heng Wang ; Siva Theja Maguluri ; Tara Javidi
【Abstract】: Optical switches have been drawing attention due to their large data bandwidth and low power consumption. However, scheduling policies need to account for the schedule reconfiguration delay of optical switches to achieve good performance. The Adaptive MaxWeight policy achieves optimal throughput for switches with nonzero reconfiguration delay, and has been shown in simulation to have good delay performance. In this paper, we analyze the queue length behavior of a switch with nonzero reconfiguration delay operating under the Adaptive MaxWeight. We first show that the Adaptive MaxWeight policy exhibits a weak state space collapse behavior in steady-state, which could be viewed as an inheritance of the MaxWeight policy in a switch with zero reconfiguration delay. We then use the weak state space collapse result to obtain a steady state delay bound under the Adaptive MaxWeight algorithm in heavy traffic by applying a recently developed drift technique. The resulting delay bound is dependent on the expected schedule duration. We then derive the relation between the expected schedule duration and the steady state queue length through drift analysis, and obtain asymptotically tight queue length bounds in the heavy traffic regime.
【Keywords】: Schedules; Delays; Optical switches; Steady-state; Throughput; Ports (Computers); Queueing analysis
【Paper Link】 【Pages】:1-9
【Authors】: Sen Yang ; Bill Lin ; Paul Tune ; Jun (Jim) Xu
【Abstract】: Chang et al. proposed the load-balanced switch in their seminal work [1], which has received wide attention due to its inherent scalability properties in both size and speed. These scalability properties continue to be of significant interest due to the relentless exponential growth in Internet traffic. The main drawback of the load-balanced switch is that packets can depart out-of-order from the switch, which can significantly degrade network performance by negatively interacting with TCP congestion control. Hence, a large body of subsequent work has proposed a variety of modifications for ensuring packet ordering, but all the proposed approaches tend to increase packet delay significantly in comparison to the basic load-balanced switch. In this paper, we show that the amount of packet reordering that can occur with the load-balanced switch is actually quite limited, which means that packet reordering can simply be rectified by employing reordering buffers at the switch outputs. In particular, we formally bound the worst-case amount of time that a packet has to wait in these output reordering buffers before it is guaranteed to be ready for in-order departure with high probability, and we prove that this bound is linear with respect to the switch size. This linear bound is significant because previous approaches can add quadratic or cubic delays to the load-balanced switch. In addition, we use a hash-grouping method that further reduces resequencing delays significantly. Although simple and intuitive, our experimental results show that our output packet reordering approach substantially outperforms existing load-balanced switch architectures.
【Keywords】: Ports (Computers); Optical switches; Delays; Out of order; Semantics; Computer architecture
【Paper Link】 【Pages】:1-9
【Authors】: Jian Lin ; Ming Li ; Dejun Yang ; Guoliang Xue ; Jian Tang
【Abstract】: The rapid growth of sensor-embedded smartphones has led to a new data sensing and collecting paradigm, known as crowdsensing. Many auction-based incentive mechanisms have been proposed to stimulate smartphone users to participate in crowdsensing. However, none of them have taken into consideration the Sybil attack where a user illegitimately pretends multiple identities to gain benefits. This attack may undermine existing inventive mechanisms. To deter the Sybil attack, we design Sybil-proof auction-based incentive mechanisms for crowdsensing in this paper. We investigate both the single-minded and multi-minded cases and propose SPIM-S and SPIM-M, respectively. SPIM-S achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SPIM-M achieves individual rationality, truthfulness, and Sybil-proofness. We evaluate the performance and validate the desired properties of SPIM-S and SPIM-M through extensive simulations.
【Keywords】: Sensors; Smart phones; Cost function; Conferences; Electronic mail; Computational modeling
【Paper Link】 【Pages】:1-9
【Authors】: Chun-Chi Liu ; Shengling Wang ; Liran Ma ; Xiuzhen Cheng ; Rongfang Bie ; Jiguo Yu
【Abstract】: Crowdsourcing applications are vulnerable to malicious behaviors, posing serious threats to their adoption and large deployment. Based on the notion that the requestor (i.e., the crowdsourcer) can block malicious behaviors via leveraging the market power through task allocation and pricing, we propose two novel frameworks based on the mechanism design game theory (i.e., the reverse game theory). To the best of our knowledge, we are the first to exploit the market power and to apply the mechanism design game theory in thwarting malicious behaviors in crowdsourcing. The first proposed framework is built on a requestor-dominant mechanism design game (Rd-MDG), where the game rule is determined solely by the requestor. The second proposed framework is based on the worker-assisted mechanism design game (WaMDG), where the worker (i.e., the contributor) can assist the requestor to determine the game rules by offering advices. These two frameworks have the following salient features: i) neither of them requires the workers to reveal their private information; ii) the game rules of each framework are designed to be able to force the workers to calculate their best strategies based on their actual private information; iii) our theoretical analysis shows that equilibriums exist for both frameworks; and iv) our extensive simulation results demonstrate that these two frameworks can thwart malicious behaviors by driving the workers with a higher attack intent into obtaining lower utilities.
【Keywords】: Games; Crowdsourcing; Game theory; Resource management; Electronic mail; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Fudong Qiu ; Zhengxian He ; Linghe Kong ; Fan Wu
【Abstract】: Secret key establishment is a fundamental requirement for private communication between two wireless entities. An intriguing solution is to extract secret keys from the inherent randomness shared between them. Although several works have been done to extract secret keys from different kinds of mediums (e.g., RSSI, CSI, CIR), the efficiency and security problems are not fully solved. In this paper, we consider the problem of secret key establishment for wireless devices, and propose MAGIK, a secure and efficient scheme based on dynamic geoMAGnetic field in Indoor environment for Key establishment. We carefully study the feasibility of utilizing indoor geomagnetic field for key extraction through extensive measurements. Our results demonstrate that geomagnetic field has several dynamic properties, including space-varying, time-varying, sensitive to measurement device, and correlative between two observed points in proximity. We also optimize the key extraction process and present two rotation-angle-based quantification methods, which can achieve faster key generation rates and lower bit mismatching ratios. Besides, we build a prototype on commodity mobile devices, and evaluate its performance by conducting real-word experiments in indoor scenarios. The experiment results confirm that our system is efficient, in terms of key extraction rate, and robust in secret key establishment without requiring additional overhead on mobile devices.
【Keywords】: Mobile handsets; Wireless communication; Communication system security; Magnetometers; Wireless sensor networks; Security; Extraterrestrial measurements
【Paper Link】 【Pages】:1-9
【Authors】: Bing Wang ; Wei Song ; Wenjing Lou ; Y. Thomas Hou
【Abstract】: Personalized medicine performs diagnoses and treatments according to the DNA information of the patients. The new paradigm will change the health care model in the future. A doctor will perform the DNA sequence matching instead of the regular clinical laboratory tests to diagnose and medicate the diseases. Additionally, with the help of the affordable personal genomics services such as 23andMe, personalized medicine will be applied to a great population. Cloud computing will be the perfect computing model as the volume of the DNA data and the computation over it are often immense. However, due to the sensitivity, the DNA data should be encrypted before being outsourced into the cloud. In this paper, we start from a practical system model of the personalize medicine and present a solution for the secure DNA sequence matching problem in cloud computing. Comparing with the existing solutions, our scheme protects the DNA data privacy as well as the search pattern to provide a better privacy guarantee. We have proved that our scheme is secure under the well-defined cryptographic assumption, i.e., the sub-group decision assumption over a bilinear group. Unlike the existing interactive schemes, our scheme requires only one round of communication, which is critical in practical application scenarios. We also carry out a simulation study using the real-world DNA data to evaluate the performance of our scheme. The simulation results show that the computation overhead for real world problems is practical, and the communication cost is small. Furthermore, our scheme is not limited to the genome matching problem but it applies to general privacy preserving pattern matching problems which is widely used in real world.
【Keywords】: DNA; Cloud computing; Testing; Computational modeling; Encryption
【Paper Link】 【Pages】:1-9
【Authors】: Qianwen Yin ; Jasleen Kaur ; F. Donelson Smith
【Abstract】: Delay and rate-based alternatives to TCP congestion-control have been around for nearly three decades and have seen a recent surge in interest. However, such designs have faced significant resistance in being deployed on a wide-scale across the Internet - this has been mostly due to serious concerns about noise in delay measurements, pacing inter-packet gaps, and/or required changes to the standard TCP stack/headers. With the advent of high-speed networking, some of these concerns become even more significant. In this paper, we consider Rapid, a recent proposal for ultra-high speed congestion control, which perhaps stretches each of these challenges to the greatest extent. Rapid adopts a framework of continuous fine-scale bandwidth probing, which requires a potentially different and finely-controlled gap for every packet, high-precision timestamping of received packets, and reliance on fine-scale changes in inter-packet gaps. While simulation-based evaluations of Rapid show that it has outstanding performance gains along several important dimensions, these will not translate to the real-world unless the above challenges are addressed. We design a Linux implementation of Rapid after carefully considering each of these challenges. Our evaluations on a 10Gbps testbed confirm that the implementation can indeed achieve the claimed performance gains, and that it would not have been possible unless each of the above challenges was addressed.
【Keywords】: Bandwidth; Protocols; Probes; Noise measurement; Delays; Performance gain; Loss measurement
【Paper Link】 【Pages】:1-9
【Authors】: Thomas Bonald ; James W. Roberts ; Christian Vitale
【Abstract】: The paper relates to multi-resource sharing between flows with heterogeneous requirements as arises in networks with wireless links or software routers implementing network function virtualization. Bottleneck max fairness (BMF) is a sharing objective in this context with good performance. The paper shows that BMF results when local fairness is imposed at each resource while flow rates are controlled by an end-to-end window. We analytically prove convergence to BMF under a fluid model when flows share a network limited to 2 resources while numerical results confirm BMF convergence for larger networks. Simulation results illustrate the impact of packetized transmission.
【Keywords】: Resource management; Convergence; Mathematical model; Wireless communication; Bit rate
【Paper Link】 【Pages】:1-9
【Authors】: Danfeng Shan ; Fengyuan Ren
【Abstract】: In data centers, micro-burst is a common traffic pattern. The packet dropping caused by it usually leads to serious performance degradations. Therefore, much attention has been paid to avoiding buffer overflow caused by micro-burst traffic. In particular, ECN is widely used in data centers to keep persistent queue occupancy low, so that enough buffer space can be available as headroom to absorb micro-burst traffic. However, we find that instantaneous-queue-length-based ECN may cause problems in another direction - buffer underflow. Specifically, current ECN marking scheme in data centers is easy to trigger spurious congestion signals, which may result in overreaction of senders and queue length oscillations in switches. Since ECN threshold is low, the buffer may underflow and link capacity is not fully used. In this paper, we reveal this problem by experiments and simulations. Besides, we theoretically deduce the amplitude of queue length oscillations. The analysis result shows that overreaction of senders is caused by ECN mis-marking. Therefore, we propose Combined Enqueue and Dequeue Marking (CEDM), which can mark packets more accurately. Through simulations, we show that CEDM can greatly reduce throughput loss and improve flow completion time.
【Keywords】: ECN marking; Micro-burst traffic; Large Segment Offload; Interrupt Coalescing
【Paper Link】 【Pages】:1-9
【Authors】: Jia Zhao ; Jiangchuan Liu ; Haiyang Wang ; Chi Xu
【Abstract】: Nearly 50% of the energy overhead in today's datacenters comes from host-to-host data transfers, which largely depend on the transport layer performance. Multipath TCP (MPTCP) has recently been suggested as a promising transport protocol to improve datacenter network throughput, yet it also increases the host CPU power consumption. It remains unclear whether datacenters can indeed benefit from using MPTCP from the perspective of energy efficiency. By analyzing the performance of MPTCP, we show that (1) despite consuming higher host CPU power than TCP, MPTCP can largely reduce the long flow completion time and thus save the aggregated energy; (2) link-sharing subflows in MPTCP not only has negative impact on both throughput-sensitive long flows and latency-sensitive short flows, but also noticeably increases the host CPU power, especially for short flows. We present MPTCP-D, an energy-efficient variant of multipath TCP for datacenters. MPTCP-D incorporates a novel congestion control algorithm that can provide energy efficiency by minimizing the flow completion time, and an extra subflow elimination mechanism that can preclude link-sharing subflows from increasing the host CPU power. We implement MPTCP-D in the Linux kernel and study its performance by experiments on Amazon EC2. Our results show that, without degrading the performance of the long flow throughput and short flow completion time, MPTCP-D reduces the long flow energy consumption by up to 72% compared to DCTCP for data transfers, and reduces the short flow power consumption by up to 46% compared to MPTCP with linksharing subflows.
【Keywords】: Throughput; Energy consumption; Data transfer; Servers; Power demand; Transport protocols; Interference
【Paper Link】 【Pages】:1-9
【Authors】: Joan Palacios ; Paolo Casari ; Joerg Widmer
【Abstract】: Device localization is a highly important functionality for a range of applications. It is particularly beneficial in mmWave networks, where it can be used to reduce the beam training overhead and anticipate handovers between access points. In this paper, we present JADE, an algorithm that estimates the location of a mobile user in an indoor space without any knowledge about the surrounding environment (floor plan, location of walls and presence of reflective surfaces) or about the location and number of access points available therein. JADE leverages the beam procedure used in pre-standard and commercial mmWave equipment to estimate the angle-of-arrival of multipath components of the signal sent by visible access points. This information is then employed to localize the mobile user, estimate the position of access points and finally form a map of the environment. No radar-like ranging operations are required for this. Our results demonstrate that JADE can localize a user with sub-meter accuracy in the broad majority of the cases, and that it even outperforms localization algorithms that require full knowledge of the environment and access point positions.
【Keywords】: Millimeter wave; localization; indoor; virtual anchors; mobility; simulation
【Paper Link】 【Pages】:1-9
【Authors】: Zenghua Zhao ; Jiankun Wang ; Xingya Zhao ; Chunyi Peng ; Qian Guo ; Bin Wu
【Abstract】: Thanks to the highly-dense lighting infrastructure in public areas, visible light emerges as a promising means to indoor localization and navigation. State-of-the-art techniques generally require customized hardware (sensing boards), and mainly work with one single light source (e.g., customized LEDs). This greatly limits their application scope. In this paper, we propose NaviLight, a generic indoor localization and navigation framework based on existing lighting infrastructure with any unmodified light sources (e.g., LED, fluorescent, and incandescent lights). NaviLight simply adopts commercial off-the-shelf mobile phones as receivers, and light intensity values as location signatures. Unlike existing WiFi systems, a single light intensity value is not discriminative enough over space though the light intensity field does vary, which makes our design more challenging. We thus propose a LightPrint as a location signature using a vector of multiple light intensity values obtained during user's walks. Such LightPrints are created by leveraging any user movement (of varying distance and direction) in order to minimize user efforts. A set of techniques are proposed to achieve quick LightPrint matching, which includes a coarse-grained classification and a fine-grained matching over dynamic time warping. We have implemented NaviLight to provide real-time service on Android phones in three typical indoor environments, covering a total area size over 1000m2. Our experiments show that NaviLight can achieve sub-meter localization accuracy to meet practical engineering requirements.
【Keywords】: Light emitting diodes; Navigation; Indoor environments; Light sources; High intensity discharge lamps; Sensors
【Paper Link】 【Pages】:1-9
【Authors】: Xi Chen ; Chen Ma ; Michel Allegue ; Xue Liu
【Abstract】: Device-free Passive (DfP) indoor localization releases the users from the burden of wearing sensors or carrying smartphones. Instead of locating devices, DfP technology directly locates human bodies. This promising technology upgrades and even redefines many services, such as intruder alarm, fire rescue, fall detection, baby monitoring, etc. Using Wi-Fi based fingerprints, DfP approaches can achieve a nearly perfect accuracy with a resolution less than one meter. However, Wi-Fi localization profiles may easily drift with a minor environment change, resulting in an inconsistency between fingerprints and new profiles. This inconsistency issue could lead to large errors, and may quickly ruin the whole system. To address this issue, we propose a approach named AutoFi to automatically calibrate the localization profiles in an unsupervised manner. AutoFi embraces a new technique that online estimates and cancels profile contaminants introduced by environment changes. It applies an autoencoder to preserve critical features of fingerprints, and reproduces them later in new localization profiles. Experiment results demonstrate that AutoFi indeed rescues the Wi-Fi fingerprints from variations in the surrounding. The localization accuracy is improved from 18.8% (before auto-calibration) to 84.9% (after auto-calibration).
【Keywords】: Wireless fidelity; Antenna arrays; Databases; Wireless communication; Signal resolution; OFDM; Array signal processing
【Paper Link】 【Pages】:1-9
【Authors】: Ruipeng Gao ; Bing Zhou ; Fan Ye ; Yizhou Wang
【Abstract】: Lacking of floor plans is a fundamental obstacle to ubiquitous indoor location-based services. Recent work have made significant progress to accuracy, but they largely rely on slow crowdsensing that may take weeks or even months to collect enough data. In this paper, we propose Knitter that can generate accurate floor maps by a single random user's one hour data collection efforts. Knitter extracts high quality floor layout information from single images, calibrates user trajectories and filters outliers. It uses a multi-hypothesis map fusion framework that updates landmark positions/orientations and accessible areas incrementally according to evidences from each measurement. Our experiments on 3 different large buildings and 30+ users show that Knitter produces correct map topology, and 90-percentile landmark location and orientation errors of 3 ~ 5m and 4 ~ 6°, comparable to the state-of-the-art at more than 20× speed up: data collection can finish in about one hour even by a novice user trained just a few minutes.
【Keywords】: Trajectory; Calibration; Geometry; Gyroscopes; Layout; Data collection; Cleaning
【Paper Link】 【Pages】:1-9
【Authors】: Raphael Naves ; Hicham Khalife ; Gentian Jakllari ; Vania Conan ; André-Luc Beylot
【Abstract】: We investigate the potential gains of Physical-Layer Network Coding (PLNC) in multi-hop wireless networks. Physical-Layer Network Coding was first introduced as a solution to increase the throughput of a two-way relay channel communication. Unlike most wireless communications techniques which try to avoid collisions, PLNC allows two simultaneous transmissions to a common receiver. Such transmitted messages are summed at signal level and then decoded at packet level. In basic topologies, Physical-Layer Network Coding has been shown to significantly enhance the throughput performance compared to classical communications. However, the impact of PLNC in large multi-hop networks remains an open question. We therefore exploit Linear Programming to evaluate the impact of this paradigm in large realistic radio deployments. Our numerical results show that PLNC can increase the throughput in large multi-hop topologies by 30%. Such gains set theoretical benchmarks for designing new access methods and routing protocols to efficiently exploit the Physical-Layer Network Coding concept.
【Keywords】: Network coding; Throughput; Network topology; Topology; Spread spectrum communication; Wireless communication; Computational modeling
【Paper Link】 【Pages】:1-9
【Authors】: Anfu Zhou ; Xinyu Zhang ; Huadong Ma
【Abstract】: Low robustness under mobility is the Achilles' heel of the emerging 60 GHz networking technology. Instead of using omni-directional antennas as in existing Wi-Fi/cellular networks, 60 GHz radios communicate via highly-directional links formed by phased-array beam-forming, so as to upgrade wireless link throughput to multi-Gbps. However, user motion causes misalignment between the Tx's and Rx's beam directions, and often leads to link outage. Legacy 60 GHz protocols realign the beams by scanning alternative Tx/Rx beams. But unfortunately this tedious process can easily overwhelm the useful channel time, leaving the Tx/Rx in misalignment most of the time during mobility. In this paper, we propose Beam-forecast, a novel model-driven beam steering approach that can sustain high performance for mobile 60 GHz links. Beam-forecast is built on the observation that 60 GHz channel profiles at nearby locations are highly-correlated. By exploiting this correlation, Beam-forecast can reconstruct the channel profile as the Tx/Rx moves, without explicit channel scanning. In this way, it can predict new optimal beams and realign links for mobile users with minimal overhead. We evaluate Beam-forecast using a reconfigurable 60 GHz testbed along with a trace-driven simulator. Our experiments demonstrate multi-fold throughput gain compared with state-of-the-art under various practical scenarios.
【Keywords】: Correlation; Mobile communication; Horn antennas; Array signal processing; Antenna measurements; Beam steering; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Quan Chen ; Hong Gao ; Yingshu Li ; Siyao Cheng ; Jianzhong Li
【Abstract】: Beaconing is a fundamental networking service where each node broadcasts a packet to all its neighbors locally. Unfortunately, the problem Minimum Latency Beaconing Schedule (MLBS) in duty-cycled scenarios is not well studied. Existing works always have rigid assumption that each node is only active once per working cycle. Aiming at making the work more practical and general, MLBS problem in duty-cycled network where each node is allowed to active multiple times in each working cycle (MLBSDCA for short) is investigated in this paper. Firstly, a modified first-fit coloring based algorithm is proposed for MLBSDCA under protocol interference model. After that, a (ρ + 1)2* |W|-approximation algorithm is proposed to further reduce the beaconing latency, where ρ denotes the interference radius, and |W| is the maximum number of active time slots per working cycle. When ρ and |W| is equal to 1, the approximation ratio is only 4, which is better than the one (i.e., 10) in existing works. Furthermore, two approximation algorithms for MLBSDCA under physical interference model are also investigated. The theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in term of latency.
【Keywords】: Interference; Approximation algorithms; Protocols; Schedules; Scheduling algorithms; Algorithm design and analysis; Scheduling
【Paper Link】 【Pages】:1-9
【Authors】: Sudipta Saha ; Mun Choon Chan
【Abstract】: In this paper, we address the fundamental problem of improving the performance of many-to-one and many-to-many communications. Our approach is Time Division Multiple Access (TDMA) based but addresses the limitations of existing TDMA implementations in a novel way. In a nutshell, we combine packets from many senders into a single large packet transmission by exploiting capture effect achieved through fine grained power control at the level of segments within a single packet. We applied our technique to the design of a one-hop, many-to-one communication protocol, SyncMerge, and a multi-hop, many-to-many communication protocol, ByteCast. Our evaluation shows that SyncMerge is able to achieve 2 to 15 times improvement over traditional many-to-one communication schemes. In addition, ByteCast is able to disseminate 1 byte of data from every node to all other nodes in about 600 ms with 99.5% reliability on a 90 node testbed. Compared to the state-of-the-art protocols such as LWB and Chaos, ByteCast is able to reduce the radio-on time by up to 90% while achieving similar reliability.
【Keywords】: Protocols; Time division multiple access; Power control; Synchronization; Reliability; Conferences; Chaos
【Paper Link】 【Pages】:1-9
【Authors】: Huichen Dai ; Bin Liu ; Haowei Yuan ; Patrick Crowley ; Jianyuan Lu
【Abstract】: Collapsed forwarding has long been used in cache systems to reduce the load on servers by aggregating requests for the same content. Named Data Networking (NDN) as a future Internet architecture incorporates this technique through a data structure called Pending Interest Table (PIT). The request aggregation feature suggests that PIT can be viewed as a nonreset time-to-live (TTL) based cache. The Content Store (CS) is a content cache placed in front of the PIT on the NDN forwarding path, so they make up a tandem cache network. To investigate the metrics of interest in this network, like the hit probability for the PIT and the CS, the expected PIT size, non-zero download delay (non-ZDD) should be taken into consideration. Caching policies usually assume zero download delay (ZDD), i.e., request and object arrive simultaneously, and numerous analytical methods have been proposed to study the ZDD caching policies. In this paper, after dissecting the LRU policy, we for the first time propose two LRU variants considering non-ZDD by defining separate operations for the request and object arrivals. When CS adopts the proposed LRU variants, the analysis of the CS-PIT network can still take advantage of the existing models, so the metrics of interest can be computed. Especially, the distribution for the “inter-miss” time of this network can be derived, which has not been achieved by prior works. Finally, the analytical results are verified through simulations.
【Keywords】: Delays; Computational modeling; Random variables; Conferences; Data structures; Analytical models
【Paper Link】 【Pages】:1-9
【Authors】: Giovanni Neglia ; Damiano Carra ; Pietro Michiardi
【Abstract】: Cache policies to minimize the content retrieval cost have been studied through competitive analysis when the miss costs are additive and the sequence of content requests is arbitrary. More recently, a cache utility maximization problem has been introduced, where contents have stationary popularities and utilities are strictly concave in the hit rates. This paper bridges the two formulations, considering linear costs and content popularities. We show that minimizing the retrieval cost corresponds to solving an online knapsack problem, and we propose new dynamic policies inspired by simulated annealing, including DynqLRU, a variant of qLRU. For such policies we prove asymptotic convergence to the optimum under the characteristic time approximation. In a real scenario, popularities vary over time and their estimation is very difficult. DynqLRU does not require popularity estimation, and our realistic, trace-driven evaluation shows that it significantly outperforms state-of-the-art policies, with up to 45% cost reduction.
【Keywords】: Simulated annealing; Estimation; Approximation algorithms; Space exploration; Detectors; Conferences; Heuristic algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Minsheng Zhang ; Vince Lehman ; Lan Wang
【Abstract】: In Named Data Networking (NDN), data synchronization plays an important role similar to transport protocols in IP. Many distributed applications, including pub-sub applications such as news and weather services, require a synchronization protocol where each consumer can subscribe to a different subset of a producer's data streams. However, existing Sync protocols support only full-data synchronization, which is a special case of this problem. We propose PSync to efficiently address different types of data synchronization. Names are used in PSync messages to carry producers' latest namespace information and each consumer's subscription information, which allows producers to maintain a single state for all consumers and enables consumers to synchronize with any producer that replicates the same data. We have implemented PSync in the NDN codebase and used it to develop a prototype pub-sub module for building management. Our experimental results show that PSync scales well as the number of consumers, subscriptions, and data streams increases and it outperforms the state-of-the-art Sync protocol in supporting full-data synchronization.
【Keywords】: Synchronization; Protocols; Arrays; Distributed databases; Conferences; Buildings
【Paper Link】 【Pages】:1-9
【Authors】: Jaeyoung Choi ; Sangwoo Moon ; Jiin Woo ; Kyunghwan Son ; Jinwoo Shin ; Yung Yi
【Abstract】: Social networks are the major routes for most individuals to exchange their opinions about new products, social trends and political issues via their interactions. It is often of significant importance to figure out who initially diffuses the information, i.e., finding a rumor source or a trend setter. It is known that such a task is highly challenging and the source detection probability cannot be beyond 31% for regular trees, if we just estimate the source from a given diffusion snapshot. In practice, finding the source often entails the process of querying that asks “Are you the rumor source?” or “Who tells you the rumor?” that would increase the chance of detecting the source. In this paper, we consider two kinds of querying: (a) simple batch querying and (b) interactive querying with direction under the assumption that queriees can be untruthful with some probability. We propose estimation algorithms for those queries, and quantify their detection performance and the amount of extra budget due to untruthfulness, analytically showing that querying significantly improves the detection performance. We perform extensive simulations to validate our theoretical findings over synthetic and real-world social network topologies.
【Keywords】: Network topology; Topology; Conferences; Computational modeling; Internet; Maximum likelihood estimation
【Paper Link】 【Pages】:1-9
【Authors】: Stefan Achleitner ; Thomas F. La Porta ; Patrick D. McDaniel ; Srikanth V. Krishnamurthy ; Alexander Poylisher ; Constantin Serban
【Abstract】: Live virtual machine (VM) migration is commonly used for enabling dynamic resource or fault management, or for load balancing in datacenters or cloud platforms. A service hosted by a VM may also be migrated to prevent its visibility to an external adversary who may seek to disrupt its operation by launching a DDoS attack against it. We first show that current systems cannot adequately hide a VM migration from an external adversary. The key reason for this is that a migration typically manifests a traffic pattern with distinguishable statistical properties. We introduce two new attacks that can allow an adversary to effectively track a migration in progress, by leveraging observations of these properties. As our primary contribution, we design and implement a stealth migration framework that causes migration traffic to be indistinguishable from regular Internet traffic, with a negligible latency overhead of approximately 0.37 seconds, on average.
【Keywords】: Virtual machining; Virtual machine monitors; Hardware; Timing; Conferences; Cloud computing
【Paper Link】 【Pages】:1-9
【Authors】: Yong Xiao ; Marwan Krunz
【Abstract】: This paper studies the workload offloading problem for fog computing networks in which a set of fog nodes can offload part or all the workload originally targeted to the cloud data centers to further improve the quality-of-experience (QoE) of users. We investigate two performance metrics for fog computing networks: users' QoE and fog nodes' power efficiency. We observe a fundamental tradeoff between these two metrics for fog computing networks. We then consider cooperative fog computing networks in which multiple fog nodes can help each other to jointly offload workload from cloud data centers. We propose a novel cooperation strategy referred to as offload forwarding, in which each fog node, instead of always relying on cloud data centers to process its unprocessed workload, can also forward part or all of its unprocessed workload to its neighboring fog nodes to further improve the QoE of its users. A distributed optimization algorithm based on distributed alternating direction method of multipliers (ADMM) via variable splitting is proposed to achieve the optimal workload allocation solution that maximizes users' QoE under the given power efficiency. We consider a fog computing platform that is supported by a wireless infrastructure as a case study to verify the performance of our proposed framework. Numerical results show that our proposed approach significantly improves the performance of fog computing networks.
【Keywords】: Fog computing; response-time analysis; power efficiency; offload forwarding; ADMM
【Paper Link】 【Pages】:1-9
【Authors】: Roy D. Yates ; Mehrnaz Tavan ; Yi Hu ; Dipankar Raychaudhuri
【Abstract】: This work introduces a new model for cloud gaming systems aimed at optimizing the timeliness of video frames based on an age of information (AoI) metric. Mobile clients submit actions through an access network to a game server. The game server generates video frames at a constant frame rate. At the mobile device, the display of these frames represent game status updates. We develop a Markov model to characterize the frame delivery process in low-latency edge cloud gaming systems. Based on this model, we derive a simple formula for the average status age of a tightly synchronized low-latency mobile gaming system in which the inter-frame period is a significant contributor to the system latency. We validate the model by ns-3 simulation of a low-latency edge cloud gaming system. Our evaluation scenarios included single-player games as well as multi-player games in which the game processing was conducted by a combination of a centralized game server and edge cloud renderers.
【Keywords】: Servers; Mobile communication; Delays; Cloud gaming; Streaming media; Mobile computing
【Paper Link】 【Pages】:1-9
【Authors】: Xiumin Wang ; Xiaoming Chen ; Weiwei Wu
【Abstract】: Despite the increased capabilities of mobile devices, resource-demanded mobile applications still transcend what can be accomplished on a single device. As such, mobile device cloud (MDC), an environment that enables computation-intensive tasks to be performed among a set of nearby mobile devices, offers a promising architecture to support real-time mobile applications. To stimulate mobile devices to execute tasks for others, it is essential to design an incentive mechanism that appropriately charges the owners of the tasks, acted as the buyers, and rewards the mobile devices, acted as the sellers. In this paper, we propose two truthful auction mechanisms for two different task models, heterogeneous and homogeneous task models, which assume the different and the same resource requirements of the tasks, respectively. Specifically, for heterogeneous task model, we propose an efficient heuristic winning bids determination algorithm to allocate the tasks, and decide the payment of each seller for its winning bids. For homogeneous task model, we design an optimal winning bid determination algorithm, and propose a Vickrey-Clarke-Groves (VCG) based auction mechanism to determine the payment of each bid. Both theoretical analysis and simulations show that the proposed auction mechanisms achieve several desirable properties such as individual rationality, truthfulness and computational efficiency.
【Keywords】: Mobile handsets; Computational modeling; Cloud computing; Mobile communication; Resource management; Batteries
【Paper Link】 【Pages】:1-9
【Authors】: Chunqiang Hu ; Abdulrahman Alhothaily ; Arwa Alrawais ; Xiuzhen Cheng ; Carl Sturtivant ; Hang Liu
【Abstract】: Matrix inverse computation is one of the most fundamental mathematical problems in large-scale data analytics and computing. It is often too expensive to be solved in resource-constrained devices such as sensors. Outsourcing the computation task to a cloud server or a fog server is a potential approach as the server is able to perform large-scale scientific computations on behalf of resource-constrained users with special software. However, outsourcing brings in new security concerns and challenges such as data privacy violations and result invalidation. In this paper, we propose a secure and verifiable outsourcing scheme to compute the matrix inverse in a server. In our scheme, the client generates two secret key sets based on two chaotic systems, which are utilized to create two sparse matrices whose permuted versions are used for matrix encryption and decryption to protect input and output privacy. The server computes the inverse over the ciphertext matrix and returns the result to the client who can verify the validity of the inverse. We analyze the proposed scheme in terms of correctness, security, verifiability, and attack resistance, and compare its performance (computation, storage, and communication overheads) with those of the state-of-the-art. Our theoretical results and comparison study demonstrate that the proposed scheme provides a secure and efficient outsourcing mechanism for matrix inverse computation.
【Keywords】: Matrix inversion; cloud/fog computing; secure outsourcing; verification; data privacy; chaotic systems
【Paper Link】 【Pages】:1-9
【Authors】: Xiaotao Feng ; Zizhan Zheng ; Derya Cansever ; Ananthram Swami ; Prasant Mohapatra
【Abstract】: Incentive-driven advanced attacks have become a major concern to cyber-security. Traditional defense techniques that adopt a passive and static approach by assuming a fixed attack type are insufficient in the face of highly adaptive and stealthy attacks. In particular, a passive defense approach often creates information asymmetry where the attacker knows more about the defender. To this end, moving target defense (MTD) has emerged as a promising way to reverse this information asymmetry. The main idea of MTD is to (continuously) change certain aspects of the system under control to increase the attacker's uncertainty, which in turn increases attack cost/complexity and reduces the chance of a successful exploit in a given amount of time. In this paper, we go one step beyond and show that MTD can be further improved when combined with information disclosure. In particular, we consider that the defender adopts a MTD strategy to protect a critical resource across a network of nodes, and propose a Bayesian Stackelberg game model with the defender as the leader and the attacker as the follower. After fully characterizing the defender's optimal migration strategies, we show that the defender can design a signaling scheme to exploit the uncertainty created by MTD to further affect the attacker's behavior for its own advantage. We obtain conditions under which signaling is useful, and show that strategic information disclosure can be a promising way to further reverse the information asymmetry and achieve more efficient active defense.
【Keywords】: Games; Computational modeling; Bayes methods; Uncertainty; Face; Servers; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Jing Chen ; Shixiong Yao ; Quan Yuan ; Ruiying Du ; Guoliang Xue
【Abstract】: Recent real-world attacks against Certification Authorities (CAs) and fraudulently issued certificates arouse the public to rethink the security of public key infrastructure for web-based connections. To distribute the trust of CAs, notaries, as an independent party, are introduced to record certificates, and a client can request an audit proof of certificates from notaries directly. However, there are two challenges. On one hand, existing works consider the security of notaries insufficiently. Due to lack of systematic mutual verification, notaries might bring safety bottlenecks. On the other hand, the service of these works is not sustainable, when any party leaks its private key or fails. In this paper, we propose a Tripartite Public Key Infrastructure (TriPKI), using Certificates Authorities, Integrity Log Servers, and Domain Name Servers, to provide a basis for establishing secure SSL/TLS connections. Specifically, we apply checks-and balances among those three parties in the structure to make them verify mutually, which avoids any single party compromise. Furthermore, we design a collaborative certificate management scheme to provide sustainable services. The security analysis and experiment results demonstrate that our scheme is suitable for practical usage with moderate overhead.
【Keywords】: Public Key Infrastructure; DNS-based; Mutual Verification
【Paper Link】 【Pages】:1-9
【Authors】: Amit Klein ; Haya Shulman ; Michael Waidner
【Abstract】: DNS caches are an extremely important tool, providing services for DNS as well as for a multitude of applications, systems and security mechanisms, such as anti-spam defences, routing security (e.g., RPKI), firewalls. Subverting the security of DNS is detrimental to the stability and security of the clients and services, and can facilitate attacks, circumventing even cryptographic mechanisms. We study the caching component of DNS resolution platforms in diverse networks in the Internet, and evaluate injection vulnerabilities allowing cache poisoning attacks. Our evaluation includes networks of leading Internet Service Providers and enterprises, and professionally managed open DNS resolvers. We test injection vulnerabilities against known payloads as well as a new class of indirect attacks that we define in this work. Our Internet evaluation indicates that more than 92% of the Internet's DNS resolution platforms are vulnerable to records injection and can be persistently poisoned.
【Keywords】: Electronic mail; IP networks; Servers; Payloads; Internet; Computer crime
【Paper Link】 【Pages】:1-9
【Authors】: Yongli Cheng ; Hong Jiang ; Fang Wang ; Yu Hua ; Dan Feng
【Abstract】: Nowadays, high-bandwidth networks are easily accessible in data centers. However, existing distributed graph-processing frameworks fail to efficiently utilize the additional bandwidth capacity in these networks for higher performance, due to their inefficient computation and communication models, leading to very long waiting times experienced by users for the graph-computing results. The root cause lies in the fact that the computation and communication models of these frameworks generate, send and receive messages so slowly that only a small fraction of the available network bandwidth is utilized. In this paper, we propose a high-performance distributed graph-processing framework, called BlitzG, to address this problem. This framework fully exploits the available network bandwidth capacity for fast graph processing. Our approach aims at significant reduction in (i) the computation workload of each vertex for fast message generation by using a new slimmed-down vertex-centric computation model and (ii) the average message overhead for fast message delivery by designing a lightweight message-centric communication model. Evaluation on a 40Gbps Ethernet, driven by real-world graph datasets, shows that BlitzG outperforms the state-of-the-art distributed graph-processing frameworks by up to 27x with an average of 20.7x.
【Keywords】: Computational modeling; Message systems; Kernel; Conferences; Bandwidth; Receivers; Scalability
【Paper Link】 【Pages】:1-9
【Authors】: Tong Shu ; Chase Q. Wu
【Abstract】: Cloud computing provides a cost-effective computing platform for big data workflows where moldable parallel computing models such as MapReduce are widely applied to meet stringent performance requirements. The granularity of task partitioning in each moldable job has a significant impact on workflow completion time and financial cost. We investigate the properties of moldable jobs and design a big-data workflow mapping model, based on which, we formulate a workflow mapping problem to minimize workflow makespan under a budget constraint in public clouds. We show this problem to be strongly NP-complete and design i) a fully polynomial-time approximation scheme (FPTAS) for a special case with a pipeline-structured workflow executed on virtual machines in a single class, and ii) a heuristic for a generalized problem with an arbitrary directed acyclic graph-structured workflow executed on virtual machines in multiple classes. The performance superiority of the proposed solution is illustrated by extensive simulation-based results in Hadoop/YARN in comparison with existing workflow mapping models and algorithms.
【Keywords】: Cloud computing; Computational modeling; Big Data; Optimization; Scheduling; Program processors
【Paper Link】 【Pages】:1-9
【Authors】: Xinxin Mei ; Xiaowen Chu ; Hai Liu ; Yiu-Wing Leung ; Zongpeng Li
【Abstract】: Conserving the energy consumption of large data centers is of critical significance, where a few percent in consumption reduction translates into millions-dollar savings. This work studies energy conservation on emerging CPU-GPU hybrid clusters through dynamic voltage and frequency scaling (DVFS). We aim at minimizing the total energy consumption of processing a sequence of real-time tasks under deadline constraints. We compute the appropriate voltage/frequency setting for each task through mathematical optimization, and assign multiple tasks to the cluster with heuristic scheduling algorithms. In performance evaluation driven by real-world power measurement traces, our scheduling algorithm shows comparable energy savings to the theoretical upper bound. With a GPU scaling interval where analytically at most 38% of energy can be saved, we record 30-36% of energy savings. Our results are applicable to energy management on modern heterogeneous clusters. In particular, our model stresses the nonlinear relationship between task execution time and processor speed for GPU-accelerated applications, for more accurately capturing real-world GPU energy consumption.
【Keywords】: Graphics processing units; Energy consumption; Servers; Runtime; Power demand; Scheduling algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Dazhao Cheng ; Yuan Chen ; Xiaobo Zhou ; Daniel Gmach ; Dejan S. Milojicic
【Abstract】: Streaming data analytics has become increasingly vital in many applications such as dynamic content delivery (e.g., advertisements), Twitter sentiment analysis, and security event processing (e.g., intrusion detection systems, and spam filters). Emerging stream processing systems, such as Spark Streaming, treat the continuous stream as a series of micro-batches of data and continuously process these micro-batch jobs. Such micro-batch based stream processing provides several advantages over traditional stream processing systems, which process streaming data one record at a time, including fast recovery from failures, better load balancing and scalability. However, efficient scheduling of micro-batch jobs to achieve high throughput and low latency is very challenging due to the complex data dependency and dynamism inherent in streaming workloads. In this paper, we propose A-scheduler, an adaptive scheduling approach that dynamically schedules parallel micro-batch jobs in Spark Streaming and automatically adjusts scheduling parameters to improve performance and resource efficiency. Specifically, A-scheduler dynamically schedules multiple jobs concurrently using different policies based on their data dependencies and automatically adjusts the level of job parallelism and resource shares among jobs based on workload properties. We implemented A-scheduler and evaluated it with a real-time security event processing workload. Our experimental results show that A-scheduler can reduce end-to-end latency by 42% and improve workload throughput and energy efficiency by 21% and 13%, respectively, compared to the default Spark Streaming scheduler.
【Keywords】: Sparks; Parallel processing; Resource management; Throughput; Schedules; Real-time systems
【Paper Link】 【Pages】:1-9
【Authors】: Wei Wang ; Yingjie Chen ; Lin Yang ; Qian Zhang
【Abstract】: The ability to detect which wearables and smartphones are on the same body has the potential to support a wealth of applications, including user authentication, automatic data synchronization, and personalized profile loading. This paper brings this feature to commercial off-the-shelf (COTS) wearables and smartphones, by creating a virtual “on-body detection sensor” based on devices' inherent wireless capabilities. We investigate using the peculiar propagation characteristics of creeping waves to discern on-body wearables. To this end, we decompose signals into multiple independent components to exploit the variation features of creeping waves. We implement our system on COTS wearables and a smartphone. Extensive experiments are conducted in a lab, apartments, malls, and outdoor areas, involving 12 volunteer subjects of different age groups, to demonstrate the robustness of our system. Results show that our system can identify on-body devices at 92.3% average true positive rate and 5% average false positive rate.
【Keywords】: Creeping waves; wearables; on-body detection
【Paper Link】 【Pages】:1-9
【Authors】: Xiaonan Guo ; Jian Liu ; Yingying Chen
【Abstract】: Acknowledging the powerful sensors on wearables and smartphones enabling various applications to improve users' life styles and qualities (e.g., sleep monitoring and running rhythm tracking), this paper takes one step forward developing FitCoach, a virtual fitness coach leveraging users' wearable mobile devices (including wrist-worn wearables and arm-mounted smartphones) to assess dynamic postures (movement patterns & positions) in workouts. FitCoach aims to help the user to achieve effective workout and prevent injury by dynamically depicting the short-term and long-term picture of a user's workout based on various sensors in wearable mobile devices. In particular, FitCoach recognizes different types of exercises and interprets fine-grained fitness data (i.e., motion strength and speed) to an easy-to-understand exercise review score, which provides a comprehensive workout performance evaluation and recommendation. FitCoach has the ability to align the sensor readings from wearable devices to the human coordinate system, ensuring the accuracy and robustness of the system. Extensive experiments with over 5000 repetitions of 12 types of exercises involve 12 participants doing both anaerobic and aerobic exercises in indoors as well as outdoors. Our results demonstrate that FitCoach can provide meaningful review and recommendations to users by accurately measure their workout performance and achieve 93% accuracy for workout analysis.
【Keywords】: Biomedical monitoring; Performance evaluation; Wearable sensors; Monitoring; Smart phones
【Paper Link】 【Pages】:1-9
【Authors】: Lei Xie ; Xu Dong ; Wei Wang ; Dawei Huang
【Abstract】: Activity sensing has become a key technology for many ubiquitous applications, such as exercise monitoring and elder care. Most traditional approaches track the human motions and perform activity recognition based on the waveform matching schemes in the raw data representation level. In regard to the complex activities with relatively large moving range, they usually fail to accurately recognize these activities, due to the inherent variations in human activities. In this paper, we propose a wearable approach for logic cognition-based activity sensing scheme in the logical representation level, by leveraging the meta-activity recognition. Our solution extracts the angle profiles from the raw inertial measurements, to depict the angle variation of limb movement in regard to the consistent body coordinate system. It further extracts the meta-activity profiles to depict the sequence of small-range activity units in the complex activity. By leveraging the least edit distance-based matching scheme, our solution is able to accurately perform the activity sensing. Based on the logic cognition-based activity sensing, our solution achieves lightweight-training recognition, which requires a small quantity of training samples to build the templates, and user-independent recognition, which requires no training from the specific user. The experiment results in real settings shows that our meta-activity recognition achieves an average accuracy of 92% for user-independent activity sensing.
【Keywords】: Coordinate measuring machines; Motion measurement; Training; Activity recognition; Transforms; Optical wavelength conversion
【Paper Link】 【Pages】:1-9
【Authors】: Xiaohui Liang ; Tianlong Yun ; Ronald A. Peterson ; David Kotz
【Abstract】: Wearables are small and have limited user interfaces, so they often wirelessly interface with a personal smartphone/computer to relay information from the wearable for display or other interactions. In this paper, we envision a new method, LightTouch, by which a wearable can establish a secure connection to an ambient display, such as a television or a computer monitor, while ensuring the user's intention to connect to the display. LightTouch uses standard RF methods (like Bluetooth) for communicating the data to display, securely bootstrapped via the visible-light communication (the brightness channel) from the display to the low-cost, low-power, ambient light sensor of a wearable. A screen `touch' gesture is adopted by users to ensure that the modulation of screen brightness can be securely captured by the ambient light sensor with minimized noise. Wireless coordination with the processor driving the display establishes a shared secret based on the brightness channel information. We further propose novel onscreen localization and correlation algorithms to improve security and reliability. Through experiments and a preliminary user study we demonstrate that LightTouch is compatible with current display and wearable designs, is easy to use (about 6 seconds to connect), is reliable (up to 98% success connection ratio), and is secure against attacks.
【Keywords】: Brightness; Biomedical monitoring; Radio frequency; Security; Monitoring; Correlation; Light sources
【Paper Link】 【Pages】:1-9
【Authors】: Zhao Li ; Kang G. Shin ; Lu Zhen
【Abstract】: Interference management (IM) is essential to wireless communication networks, but interference suppression, a key component of IM, is known to degrade users' achievable spectral efficiency (SE). It is thus important to select an appropriate IM method with optimal operating parameters according to diverse network deployments, transmit power differences of various communication equipments, and dynamically changing channel conditions so as to balance the benefits brought by and the cost of IM. Interference neutralization (IN) has recently been receiving considerable attention, with which a duplicate of interference of the same strength and opposite phase w.r.t. the original interfering signal is generated to neutralize the disturbance at the intended receiver. However, to the best of our knowledge, all existing IN schemes assume that interference is completely neutralized without accounting for their power consumption. To remedy this deficiency, we propose a novel scheme, called dynamic interference neutralization (DIN). By intelligently determining the appropriate portion of interference to be neutralized, we balance the transmitter's power used for IN and the desired signal's transmission. We then present a new way to adaptively select one of DIN and other IM methods by taking into account the cost of multiple IM methods and their benefits. Our analysis has shown that DIN can include complete IN and non-interference management (non-IM) as special cases. The proposed strategy is shown via simulation to be able to make better use of the transmit power than existing IM methods, hence enhancing users' SE.
【Keywords】: Interference; Transmitters; Receivers; Relays; Macrocell networks; Conferences; Array signal processing
【Paper Link】 【Pages】:1-9
【Authors】: Kai-Cheng Hsu ; Kate Ching-Ju Lin ; Hung-Yu Wei
【Abstract】: Recent studies have experimentally shown the gains of full-duplex radios. However, due to its relatively higher cost and complexity, we can envision a more practical step in the network evolution is to have a full-duplex access point (AP) but keep the clients half-duplex. Unfortunately, the full-duplex gains can hardly be extracted in practice as the uplink transmission from a half-duplex client introduces inter-client interference to another downlink client. To address this issue, we present the design and implementation of IC2 (Inter-Client Interference Cancellation), the first physical layer solution that exploits the AP's full-duplex capability to actively cancel the interference at the downlink client. Such active cancellation not only improves the achievable capacity, but also better tolerates imperfect user pairing, simplifying the MAC design as a result. We build a prototype of IC2 on USRP-N200 and evaluate its performance via both testbed experiments and large-scale trace-driven simulations. The results show that, without IC2, about 60% of client pairs produce no gain from full-duplex transmissions, while, with IC2 the median throughput gain over conventional half-duplex networks can be 1.65× even when clients are simply paired randomly.
【Keywords】: Downlink; Uplink; Interference cancellation; Throughput; Hardware; Relays
【Paper Link】 【Pages】:1-9
【Authors】: Tom Vermeulen ; Mihir Laghate ; Ghaith Hattab ; Danijela Cabric ; Sofie Pollin
【Abstract】: Wireless devices are ubiquitous nowadays and, since most of them use the same unlicensed frequency bands, the high number of packet losses due to interference and collisions degrade performance. Reliability, energy consumption, and latency are key challenges for future dense networks. Allowing the transmitter to take action, i.e., vacating the channel, as soon as a collision or interference is detected is crucial in improving these metrics. In-band full duplex radios enable the transmitter to simultaneously transmit packets and sense the spectrum for collisions and interference. This paper studies two important questions regarding transmitter-based collision and interference detection: (1) from an overall system perspective, does such detection outperform receiver-based detection and (2) which test statistic is the most accurate and sensitive at detecting collisions and interference. First, NS-3 simulations are used to show that transmitter-based detection reduces the energy consumption while improving the throughput in a typical star topology network. Next, we present a measurement-based study of four different techniques for transmitter-based collision and interference detection. In particular, we compare the energy detector with three goodness-of-fit tests in terms of probability of detection and false alarm. Our analysis shows that transmitter-based detection can detect between 80% to 100% of the collisions and interference occurring at the receiver, depending on the distance between the transmitter and the receiver. Of those detectable by the transmitter, our measurement results show that goodness-of-fit tests can detect nearly 100% of the collisions and have at least 10 dB better sensitivity as compared to the commonly proposed energy detection test. In general, the proposed techniques can detect interfering signals that are up to 25 dB below the remaining self-interference power.
【Keywords】: Interference; Receivers; Radio transmitters; Silicon; Reliability; Energy consumption
【Paper Link】 【Pages】:1-9
【Authors】: Gaurang Naik ; Jinshan Liu ; Jung-Min Park
【Abstract】: The 5.9 GHz band is being actively explored for possible spectrum sharing opportunities between Dedicated Short Range Communications (DSRC) and IEEE 802.11ac networks in order to address the increasing demand for bandwidth-intensive Wi-Fi applications. In this paper, we study the implications of this spectrum sharing to the performance of Wi-Fi systems. Through experiments performed on our testbed, we first investigate band sharing options available for Wi-Fi devices. Using experimental results, we show the need for using conservative Wi-Fi transmission parameters to enable harmonious coexistence between DSRC and Wi-Fi. Moreover, we show that under the current 802.11ac standard, certain channelization options, particularly the high bandwidth ones, cannot be used by Wi-Fi devices without causing interference to the DSRC nodes. Under these constraints, we propose a Real-time Channelization Algorithm (RCA) for Wi-Fi Access Points (APs) operating in the shared spectrum. Evaluation of the proposed algorithm using a prototype implementation on commodity hardware as well as via simulations show that informed channelization decisions can significantly increase Wi-Fi throughput compared to static channelization schemes.
【Keywords】: Wireless fidelity; Transmitters; IEEE 802.11 Standard; Bandwidth; Hardware; Performance evaluation
【Paper Link】 【Pages】:1-9
【Authors】: Ran Ben-Basat ; Gil Einziger ; Roy Friedman ; Yaron Kassner
【Abstract】: Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) - a novel algorithm for the frequency and top-k estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top-k identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the workloads' skewness. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. Additionally, we present d-Way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits.
【Keywords】: Radiation detectors; Frequency estimation; Monitoring; Random access memory; Probabilistic logic; Algorithm design and analysis; Estimation
【Paper Link】 【Pages】:1-9
【Authors】: Ran Ben-Basat ; Gil Einziger ; Roy Friedman ; Yaron Kassner
【Abstract】: Monitoring the traffic volumes of elephant flows, including the total byte count per flow, is a fundamental capability for online network measurements. We present an asymptotically optimal algorithm for solving this problem in terms of both space and time complexity. This improves on previous approaches, which can only count the number of packets in constant time. We evaluate our work on real packet traces, demonstrating an up to X2.5 speedup compared to the best alternative.
【Keywords】: Radiation detectors; Maintenance engineering; Monitoring; Data structures; Software algorithms; Runtime; Real-time systems
【Paper Link】 【Pages】:1-9
【Authors】: Gaogang Xie ; Kun Xie ; Jun Huang ; Xin Wang ; Yuxiang Chen ; Jigang Wen
【Abstract】: Detecting anomalous traffic is a critical task for advanced Internet management. The traditional approaches based on Principal Component Analysis (PCA) are effective only when the corruption is caused by small additive i.i.d. Gaussian noise. The recent Direct Robust Matrix Factorization (DRMF) is proven to be more robust and accurate in anomaly detection, but it incurs a high computation cost due to its need of singular value decomposition (SVD) for low-rank matrix approximation and the iterative use of SVD execution to find the final solution. To enable the anomaly detection for large traffic matrix with the use of DRMF, we formulate the low-rank matrix approximation problem as a problem of searching for the subspace to project the traffic matrix with the minimum error. We propose a novel approach, LSH-subspace, for fast low-rank matrix approximation. To facilitate the matrix partition for the quick search of the subspace, we propose several novel techniques: a multi-layer locality sensitive hashing (LSH) table to reorder the OD pairs based on LSH function, a partition principle to guide the partition to minimize the projection error, and a lightweight algorithm to exploit the sparsity of the outlier matrix to update the LSH table at low overhead. Our extensive simulations based on real trace data demonstrate that our LSH-subspace is 3 times faster than DRMF with high anomaly detection accuracy.
【Keywords】: Low-Rank Matrix Approximation; Anomaly Detection
【Paper Link】 【Pages】:1-9
【Authors】: Kun Xie ; Can Peng ; Xin Wang ; Gaogang Xie ; Jigang Wen
【Abstract】: The inference of the network traffic matrix from partial measurement data becomes increasingly critical for various network engineering tasks, such as capacity planning, load balancing, path setup, network provisioning, anomaly detection, and failure recovery. The recent study shows it is promising to more accurately interpolate the missing data with a three-dimensional tensor as compared to interpolation methods based on two-dimensional matrix. Despite the potential, it is difficult to form a tensor with measurements taken at varying rate in a practical network. To address the issues, we propose Reshape-Align scheme to form the regular tensor with data from dynamic measurements, and introduce user-domain and temporal-domain factor matrices which takes full advantage of features from both domains to translate the matrix completion problem to the tensor completion problem based on CP decomposition for more accurate missing data recovery. Our performance results demonstrate that our Reshape-Align scheme can achieve significantly better performance in terms of two metrics: error ratio and mean absolute error (MAE).
【Keywords】: Internet traffic data recovery; Matrix completion; Tensor completion
【Paper Link】 【Pages】:1-9
【Authors】: Fan Dang ; Pengfei Zhou ; Zhenhua Li ; Ennan Zhai ; Aziz Mohaisen ; Qingfu Wen ; Mo Li
【Abstract】: Automated Fare Collection (AFC) systems have been globally deployed for decades, particularly in public transportation. Although the transaction messages of AFC systems are mostly transferred in plaintext, which is obviously insecure, system operators do not need to pay much attention to this issue, since the AFC network is well isolated from public network (e.g., the Internet). Nevertheless, in recent years, the advent of Near Field Communication (NFC)-equipped smartphones has bridged the gap between the AFC network and the Internet through Host-based Card Emulation (HCE). Motivated by this fact, we design and practice a novel paradigm of attack on modern distance-based pricing AFC systems, enabling users to pay much less than actually required. Our constructed attack has two important properties: 1) it is invisible to AFC system operators because the attack never causes any inconsistency in the backend database of the operators; and 2) it can be scalable to large number of users (e.g., 10,000) by maintaining a moderate-sized AFC card pool (e.g., containing 150 cards). Based upon this constructed attack, we developed an HCE app, named LessPay. Our real-world experiments on LessPay demonstrate not only the feasibility of our attack (with 97.6% success rate), but also its low-overhead in terms of bandwidth and computation.
【Keywords】: Protocols; Authentication; Smart phones; Conferences; Urban areas; Web servers
【Paper Link】 【Pages】:1-9
【Authors】: Yimin Chen ; Jingchao Sun ; Xiaocong Jin ; Tao Li ; Rui Zhang ; Yanchao Zhang
【Abstract】: Face authentication emerges as a powerful method for preventing unauthorized access to mobile devices. It is, however, vulnerable to photo-based forgery attacks (PFA) and videobased forgery attacks (VFA), in which the adversary exploits a photo or video containing the user's frontal face. Effective defenses against PFA and VFA often rely on liveness detection, which seeks to find a live indicator that the submitted face photo or video of the legitimate user is indeed captured in real time. In this paper, we propose FaceHeart, a novel and practical face authentication system for mobile devices. FaceHeart simultaneously takes a face video with the front camera and a fingertip video with the rear camera on COTS mobile devices. It then achieves liveness detection by comparing the two photoplethysmograms independently extracted from the face and fingertip videos, which should be highly consistent if the two videos are for the same live person and taken at the same time. As photoplethysmograms are closely tied to human cardiac activity and almost impossible to forge or control, FaceHeart is strongly resilient to PFA and VFA. Extensive user experiments on Samsung Galaxy S5 have confirmed the high efficacy and efficiency of FaceHeart.
【Keywords】: Face; Authentication; Mobile handsets; Cameras; Streaming media; Feature extraction; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Hao Fu ; Zizhan Zheng ; Somdutta Bose ; Matt Bishop ; Prasant Mohapatra
【Abstract】: Mobile applications (apps) often transmit sensitive data through network with various intentions. Some transmissions are needed to fulfill the app's functionalities. However, transmissions with malicious receivers may lead to privacy leakage and tend to behave stealthily to evade detection. The problem is twofold: how does one unveil sensitive transmissions in mobile apps, and given a sensitive transmission, how does one determine if it is legitimate? In this paper, we propose LeakSemantic, a framework that can automatically locate abnormal sensitive network transmissions from mobile apps. LeakSemantic consists of a hybrid program analysis component and a machine learning component. Our program analysis component combines static analysis and dynamic analysis to precisely identify sensitive transmissions. Compared to existing taint analysis approaches, LeakSemantic achieves better accuracy with fewer false positives and is able to collect runtime data such as network traffic for each transmission. Based on features derived from the runtime data, machine learning classifiers are built to further differentiate between the legal and illegal disclosures. Experiments show that LeakSemantic achieves 91% accuracy on 2279 sensitive connections from 1404 apps.
【Keywords】: Runtime; Mobile communication; Androids; Humanoid robots; Conferences; Analytical models; Privacy
【Paper Link】 【Pages】:1-9
【Authors】: Yingyuan Yang ; Jinyuan Sun
【Abstract】: Motivated by the great potential of implicit and seamless user authentication, we attempt to build an efficient middle layer running on mobile devices to support implicit authentication (IA) systems with adaptive sampling. Various activities, such as user location, application usage, user motion, and battery usage have been popular choices to generate behaviors, the soft biometrics, for implicit authentication. Unlike password-based or hard biometric-based authentication, implicit authentication does not require explicit user action or expensive hardware. However, user behaviors can change unpredictably which renders it more challenging to develop systems that depend on them. Various machine learning algorithms have been used to address this challenge. The expensive training process is usually outsourced to the remote server but this can potentially increase the chance of data leakage. In addition, mobile devices may not always have reliable network connections to send real-time data to the server for training. Motivated by these limitations, we propose a W-layer, an overlay that provides an energy-efficient solution for real-time implicit authentication on mobile devices. The size of the data the system needs to collect at different times depends on the legitimacy of the user. This in turn affects how the sampling rate is adjusted which can reduce energy consumption. To evaluate our method, we conducted several experiments on both synthetic and real datasets. The average accuracy of identifying legitimate users is 96.73% using the synthetic dataset and 96.70% using the real dataset. Furthermore, we tested the power consumption on a low-end Nexus S smartphone to obtain a more pessimistic result. We found that our method consumed 14.5% of the device's total battery usage. The power consumption performance is expected to improve significantly on high-end mobile devices.
【Keywords】: Authentication; Sensors; Real-time systems; Mobile handsets; Biometrics (access control); Servers; Training
【Paper Link】 【Pages】:1-9
【Authors】: Rahul Vaze
【Abstract】: Two related online problems: knapsack and truthful bipartite matching are considered. For these two problems, the common theme is how to `match' an arriving left vertex in an online fashion with any of the available right vertices, if at all, so as to maximize the sum of the value of the matched edges, subject to satisfying a sum-weight constraint on the matched left vertices. Assuming that the left vertices arrive in an uniformly random order (secretary model), two almost similar algorithms are proposed for the two problems, that are 2e competitive and 24 competitive, respectively. The proposed online bipartite matching algorithm is also shown to be truthful: there is no incentive for any left vertex to misreport its bid/weight. Direct applications of these problems include job allocation with load balancing, generalized adwords, crowdsourcing auctions, and matching wireless users to cooperative relays in device-to-device communication enabled cellular network.
【Keywords】: Device-to-device communication; Impedance matching; Conferences; Resource management; Load management; Crowdsourcing; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Jianan Zhang ; Eytan Modiano
【Abstract】: We consider a model of two interdependent networks, where every node in one network depends on one or more supply nodes in the other network and a node fails if it loses all of its supply nodes. We develop algorithms to compute the failure probability of a path, and obtain the most reliable path between a pair of nodes in a network, under the condition that each supply node fails independently with a given probability. Our work generalizes the classical shared risk group model, by considering multiple risks associated with a node and letting a node fail if all the risks occur. Moreover, we study the diverse routing problem by considering two paths between a pair of nodes. We define two paths to be d-failure resilient if at least one path survives after removing d or fewer supply nodes, which generalizes the concept of disjoint paths in a single network, and risk-disjoint paths in a classical shared risk group model. We compute the probability that both paths fail, and develop algorithms to compute the most reliable pair of paths.
【Keywords】: Routing; Computer network reliability; Robustness; Computational modeling; Approximation algorithms; Algorithm design and analysis
【Paper Link】 【Pages】:1-9
【Authors】: Jiguo Yu ; Xueli Ning ; Yunchuan Sun ; Shengling Wang ; Yawei Wang
【Abstract】: As a virtual backbone structure, connected dominating sets (CDSs) play an important role in topology control for wireless networks. In this paper, we develop a distributed self-stabilizing CDS construction algorithm under the SINR model (also known as the physical interference model), a more practical yet more challenging interference model for distributed algorithm design. Specifically, we propose a randomized distributed algorithm that can construct a CDS in O (log n) timeslots with a high probability, where n is the total number of nodes in the network. The constructed CDS achieves constant approximation in both density and diameter. To the best of our knowledge, this is the first known asymptotically optimal self-stabilizing result in terms of both density and diameter for distributed CDS construction under the practical SINR model.
【Keywords】: Interference; Signal to noise ratio; Algorithm design and analysis; Approximation algorithms; Wireless networks; Wireless sensor networks
【Paper Link】 【Pages】:1-9
【Authors】: Wenzhong Li ; Jinggong Zhang ; Yanchao Zhao
【Abstract】: With the dense deployment of wireless infrastructure such as radio towers and WiFi access points, wireless network optimization becomes very important for improving the network capacity and enhancing the communication quality of wireless links. Most optimization algorithms rely on the conflict graph to describe the interference situation. However, building a conflict graph requires exhaustive measurements of the whole network and the existing estimation approaches are static and inaccurate. In this paper, we propose a conflict graph embedding approach to assess network interference situations by representing the wireless nodes with low-dimensional vectors while preserving their conflict relationships. Specifically, our approach introduces a sliding-window based partial measurement method to sample the interference graph in the network, then adopts a learning algorithm to obtain the vector representation of the nodes, and then infers the interference situations by exploring the feature vectors. The proposed approach has been proved to be low measurement overhead, low computational cost, and self-adaptive, which is suitable for large-scale dynamic wireless networks. We illustrate that conflict graph embedding can be used for interference-aware wireless network optimizations. We conduct extensive experiments based on real wireless network datasets, which show the efficiency of the proposed approach.
【Keywords】: Interference; Wireless networks; Optimization; Extraterrestrial measurements; Time measurement
【Paper Link】 【Pages】:1-9
【Authors】: Shih-Chun Lin ; Ian F. Akyildiz
【Abstract】: Millimeter-wave communication is one of the enabling technologies to meet high data-rate requirements of 5G wireless systems. Millimeter-wave systems due large available bandwidth enable gigabit-per-second data rates for line-of-sight (LOS) transmissions in short distances. However, for non-line-of-sight (NLOS) transmissions, millimeter-wave systems suffers performance degradation because the received signal strengths at user equipments (UEs) are not satisfactory. In this paper, the NLOS problem in millimeter-wave systems is treated from SoftAir (a wireless software-defined networking architecture) perspective. In particular, a so-called dynamic base station (BS) formation is introduced, which adaptively coordinates BSs and their multiple antennas to always satisfy UEs' quality-of-service (QoS) requirements in NLOS cases. First, the architecture for software-defined millimeter-wave system is introduced, where remote radio heads (RRHs) coordination is explained and millimeter-wave channel model between RRHs and UEs is analyzed. A ubiquitous millimeter-wave coverage problem is formulated, which jointly optimizes RRH-UE associations and beamforming weights of RRHs to maximize the UE sum-rate while guaranteeing QoS and system-level constraints. After proving the np-hardness of the coverage optimization problem with non-convex constraints, an iterative algorithm is developed for dynamic BS formation that achieves ubiquitous coverage with high data rates in LOS and NLOS cases. Through successive convex approximations, the proposed dynamic BS formation algorithm transforms the original mixed-integer nonlinear programming into a mixed-integer second-order cone programming, which is efficiently solved by convex tools. Simulations validate the efficacy of our solution that completely solves NLOS problem by facilitating ubiquitous coverage in 5G millimeter-wave systems.
【Keywords】: Millimeter wave communication; Nonlinear optics; 5G mobile communication; Array signal processing; Computer architecture; Antennas
【Paper Link】 【Pages】:1-9
【Authors】: Sem C. Borst ; Aliye Özge Kaya ; Doru Calin ; Harish Viswanathan
【Abstract】: Emerging 5G networks will not only offer higher link rates, but also integrate a variety of Radio Access Technologies (RATs) in order to provide ultra-reliable broadband access to a wide range of applications with high throughput and low latency requirements. SDN-enabled dynamic path selection is of critical importance in exploiting the collective transmission resources in such heterogeneous multi-RAT environments and delivering excellent user performance. In the present paper we propose the `best-rate' path selection algorithm for multi-RAT networks with various types of traffic flows. The best-rate algorithm accounts for the radio conditions and performance requirements of individual flows as well as the load conditions at the various access points. We analytically establish that the rates received by the various flows under the best-rate path selection, in conjunction with local fair resource sharing at the individual access points, are close to globally Proportional Fair. Detailed simulation experiments demonstrate that the best-rate algorithm achieves significant gains in terms of user-perceived throughput performance over various baseline policies.
【Keywords】: Resource management; Throughput; Heuristic algorithms; Streaming media; Sociology; Statistics; Load management
【Paper Link】 【Pages】:1-9
【Authors】: Jian-Jhih Kuo ; Shan-Hsiang Shen ; Hongyu Kang ; De-Nian Yang ; Ming-Jer Tsai ; Wen-Tsuen Chen
【Abstract】: With software-defined network (SDN) and network function virtualization (NFV) techniques, we can embed the service chain consisting of a sequence of virtualized network functions (VNFs), i.e., we can determine the flow path and deploy the VNFs contained in the service chain at any place on the path. In the literature, the methods of service chain embedding bound the number of VNFs at a node, whereas the link capacities are disregarded and the amount of flows is not considered, which could cause serious congestion. In addition, according to our experiment, the process overhead on a computation node is linear to the total amount of flows processed. In this paper, we propose a method of service chain embedding to maximize the total amount of flows while bounding the process overhead of the flows on a node by its computation capability and the total amount of flows on an link by its bandwidth capacity. To our knowledge, our method is the first approximation algorithm of service chain embedding with considering flow in the literature. Simulations show our algorithm has good performance in terms of the total amount of flows.
【Keywords】: Routing; Encapsulation; Approximation algorithms; Bandwidth; Servers; Software; Network function virtualization
【Paper Link】 【Pages】:1-9
【Authors】: Vincenzo Sciancalepore ; Konstantinos Samdanis ; Xavier Pérez Costa ; Dario Bega ; Marco Gramaglia ; Albert Banchs
【Abstract】: The emerging network slicing paradigm for 5G provides new business opportunities by enabling multi-tenancy support. At the same time, new technical challenges are introduced, as novel resource allocation algorithms are required to accommodate different business models. In particular, infrastructure providers need to implement radically new admission control policies to decide on network slices requests depending on their Service Level Agreements (SLA). When implementing such admission control policies, infrastructure providers may apply forecasting techniques in order to adjust the allocated slice resources so as to optimize the network utilization while meeting network slices' SLAs. This paper focuses on the design of three key network slicing building blocks responsible for (i) traffic analysis and prediction per network slice, (ii) admission control decisions for network slice requests, and (iii) adaptive correction of the forecasted load based on measured deviations. Our results show very substantial potential gains in terms of system utilization as well as a trade-off between conservative forecasting configurations versus more aggressive ones (higher gains, SLA risk).
【Keywords】: Forecasting; Admission control; 5G mobile communication; 3GPP; Prediction algorithms; Training; Resource management
【Paper Link】 【Pages】:1-9
【Authors】: Swadhin Pradhan ; Lili Qiu ; Abhinav Parate ; Kyu-Han Kim
【Abstract】: In today's always-connected world, we receive a large number of notifications on our mobile devices. These notifications cause interruptions, stress, and even impact users' lifestyle. To understand how users respond to notifications, we develop an application that monitors various features (e.g., importance) of the notifications, users' actions, and the level of users' engagement with the notifications. We recruit 30 users to use the application and monitor over 30 days, and subsequently find that 20% to 50% of the notifications generally get ignored by the users. In addition, we also solicit explicit feedback about the importance of notifications from 12 users over 14 days and identify the relation between perceived importance and users' engagement level. Based on this study, we identify the key characteristics of notifications and users' engagement, which is further substantiated by an onfine survey of 400+ users. In addition, we develop a notification manager that includes a machine learning based prediction model and that shows only the important notifications and delays the unimportant notifications. Our experimental results show that our notification manager automatically assesses the importance of notifications with more than 87% accuracy. We believe this work is a promising step toward intelligent personal assistant that manages notifications.
【Keywords】: Electronic mail; Monitoring; Vibrations; Delays; Conferences; Mobile communication; Operating systems
【Paper Link】 【Pages】:1-9
【Authors】: Yimin Chen ; Xiaocong Jin ; Jingchao Sun ; Rui Zhang ; Yanchao Zhang
【Abstract】: Which apps a mobile user has and how they are used can disclose significant private information about the user. In this paper, we present the design and evaluation of POWERFUL, a new attack which can fingerprint sensitive mobile apps (or infer sensitive app usage) by analyzing the power consumption profiles on Android devices. POWERFUL works on the observation that distinct apps and their different usage patterns all lead to distinguishable power consumption profiles. Since the power profiles on Android devices require no permission to access, POWERFUL is very difficult to detect and can pose a serious threat against user privacy. Extensive experiments involving popular and sensitive apps in Google Play Store show that POWERFUL can identify the app used at any particular time with accuracy up to 92.9%, demonstrating the feasibility of POWERFUL.
【Keywords】: Androids; Humanoid robots; Mobile communication; Feature extraction; Power demand; Google; Mobile handsets
【Paper Link】 【Pages】:1-9
【Authors】: Zhenjiang Li ; Mo Li ; Prasant Mohapatra ; Jinsong Han ; Shuaiyu Chen
【Abstract】: This paper presents iType, a system that uses eye gaze for typing private information on commodity mobile platforms. The design combats three primary challenges: 1) relatively low accuracy of mobile gaze tracking; 2) difficulties in correcting input errors due to lacking the comparison with the true text-entry value; and 3) device motions and other noises that may interfere gaze tracking accuracy and thus the iType performance. We devise a set of effective techniques, including leveraging a collective behavior of the gaze tracking results, unique correlation of the typing error spatial distributions, and motion sensor hints from mobile devices, to address above challenges. A set of enhancement techniques are applied to further improve iType's robustness and reliability. We consolidate above designs and implement iType on iOS platform. Evaluations show that iType achieves high keystroke detection accuracy for the secure typing within a reasonable short latency.
【Keywords】: Gaze tracking; Mobile handsets; Cameras; Keyboards; Engines; Mobile communication; Privacy
【Paper Link】 【Pages】:1-9
【Authors】: Paul Y. Cao ; Gang Li ; Adam C. Champion ; Dong Xuan ; Steve Romig ; Wei Zhao
【Abstract】: In this research, we conduct a comprehensive measurement study on the predictability of human mobility with respect to demographic differences. We leverage an extensive WLAN dataset collected on a large university campus. Specifically, our dataset includes over 41 million WLAN entries gathered from over 5,000 students (with demographic information) during a four-month period in 2015. We observed surprising patterns on large increases of long-term mobility entropy by age, and the impact of academic majors on students long-term mobility entropy. The distribution of long-term entropy follows a bimodal distribution, which is different from previous studies. We also find that the predictability of students' short-term (daily or weekly) mobility varies on different days of the week and with student gender. Because of the large campus size, our results can mimic people's mobility patterns in metropolitan areas. We also anticipate that our results will provide insight that guides academic administrators' decisions regarding facilities planning, emergency management, etc. on campus.
【Keywords】: Entropy; Wireless LAN; Mobile handsets; Buildings; Mobile communication; Global Positioning System; Conferences