2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019. IEEE 【DBLP Link】
【Paper Link】 【Pages】:1-9
【Authors】: Bahman Abolhassani ; John Tadrous ; Atilla Eryilmaz
【Abstract】: In this work, we provide a comprehensive analysis of stability properties and delay gains that wireless multicasting capabilities, as opposed to more traditional unicast transmissions, can provide for content distribution in mobile networks. In particular, we propose a model and characterize the average queue-length (and hence average delay) performance of unicasting and various multicasting strategies for serving a dynamic user population at the wireless edge. First, we show that optimized static randomized multicasting (we call it 'blind multicasting') leads to stable-everywhere operation irrespective of the network loading factor (given by the ratio of the demand rate to the service rate) and the content popularity distribution. In contrast, traditional unicasting suffers from unstable operation when the loading factor approaches one, although it outperforms blind multicasting at small loading factor levels. This motivates us to study 'work-conserving multicast' policies next that always outperform unicasting while still offering stable-everywhere operation. Then, in the worst-case of uniformly-distributed content popularity, we explicitly characterize the scaling of the average queue-length (and hence delay) under a first-come-first-serve multicast strategy as a function of the database size and the loading factor. Consequently, this work provides the fundamental limits, as well as the guidelines, for the design and performance analysis of efficient multicasting strategies for wireless content distribution.
【Keywords】: Wireless Content Distribution; Multicast; Delay Gains; Information-Centric Networking
【Paper Link】 【Pages】:10-18
【Authors】: Konstantinos Poularakis ; Jaime Llorca ; Antonia Maria Tulino ; Ian Taylor ; Leandros Tassiulas
【Abstract】: The proliferation of innovative mobile services such as augmented reality, networked gaming, and autonomous driving has spurred a growing need for low-latency access to computing resources that cannot be met solely by existing centralized cloud systems. Mobile Edge Computing (MEC) is expected to be an effective solution to meet the demand for low-latency services by enabling the execution of computing tasks at the network-periphery, in proximity to end-users. While a number of recent studies have addressed the problem of determining the execution of service tasks and the routing of user requests to corresponding edge servers, the focus has primarily been on the efficient utilization of computing resources, neglecting the fact that non-trivial amounts of data need to be stored to enable service execution, and that many emerging services exhibit asymmetric bandwidth requirements. To fill this gap, we study the joint optimization of service placement and request routing in MEC-enabled multi-cell networks with multidimensional (storage-computation-communication) constraints. We show that this problem generalizes several problems in literature and propose an algorithm that achieves close-to-optimal performance using randomized rounding. Evaluation results demonstrate that our approach can effectively utilize the available resources to maximize the number of requests served by low-latency edge cloud servers.
【Keywords】: Routing; Bandwidth; Cloud computing; Approximation algorithms; Heuristic algorithms; Uplink; Downlink
【Paper Link】 【Pages】:19-27
【Authors】: Wei Wang ; Xin Liu ; Yao Yao ; Yan Pan ; Zicheng Chi ; Ting Zhu
【Abstract】: Routing and flooding are important functions in wireless networks. However, until now routing and flooding protocols are investigated separately within the same network (i.e., a WiFi network or a ZigBee network). Moreover, further performance improvement has been hampered by the assumption of the harmful cross technology interference. In this paper, we present coexistent routing and flooding (CRF), which leverages the unique feature of physical layer cross-technology communication technique for concurrently conducting routing within the WiFi network and flooding among ZigBee nodes using a single stream of WiFi packets. We extensively evaluate our design under different network settings and scenarios. The evaluation results show that CRF i) improves the throughput of WiFi networks by 1.2 times than the state-of-the-art routing protocols; and ii) significantly reduces the flooding delay in ZigBee networks (i.e., 31 times faster than the state-of-the-art flooding protocol).
【Keywords】: Wireless fidelity; Zigbee; Routing; Emulation; Throughput; Interference; Physical layer
【Paper Link】 【Pages】:28-36
【Authors】: Itamar Cohen ; Gil Einziger ; Roy Friedman ; Gabriel Scalosub
【Abstract】: Having multiple data stores that can potentially serve content is common in modern networked applications. Data stores often publish approximate summaries of their content to enable effective utilization. Since these summaries are not entirely accurate, forming an efficient access strategy to multiple data stores becomes a complex risk management problem.This paper formally models this problem, and introduces practical algorithms with guaranteed approximation ratios, and in particular we show that our algorithms are optimal in a variety of settings. We also perform an extensive simulation study based on real data, and show that our algorithms are more robust than existing heuristics. That is, they exhibit near optimal performance in various settings whereas the efficiency of existing approaches depends upon system parameters that may change over time, or be otherwise unknown.
【Keywords】: Approximation algorithms; Data models; Data centers; Encoding; Risk management; Heuristic algorithms; 5G mobile communication
【Paper Link】 【Pages】:37-45
【Authors】: Jaya Prakash Champati ; Hussein Al-Zubaidy ; James Gross
【Abstract】: Since Age of Information (AoI) has been proposed as a metric that quantifies the freshness of information updates in a communication system, there has been a constant effort in understanding and optimizing different statistics of the AoI process for classical queueing systems. In addition to classical queuing systems, more recently, systems with no queue or a unit capacity queue storing the latest packet have been gaining importance as storing and transmitting older packets do not reduce AoI at the receiver. Following this line of research, we study the distribution of AoI for the GI/GI/1/1 and GI/GI/1/2 systems, under non-preemptive scheduling. For any single-source-single-server queueing system, we derive, using sample path analysis, a fundamental result that characterizes the AoI violation probability, and use it to obtain closed-form expressions for D/GI/1/1, M/GI/1/1 as well as systems that use zero-wait policy. Further, when exact results are not tractable, we present a simple methodology for obtaining upper bounds for the violation probability for both GI/GI/1/1 and GI/GI/1/2 systems. An interesting feature of the proposed upper bounds is that, if the departure rate is given, they overestimate the violation probability by at most a value that decreases with the arrival rate. Thus, given the departure rate and for a fixed average service, the bounds are tighter at higher utilization.
【Keywords】: Upper bound; Measurement; Receivers; Servers; Random variables; Information age; Closed-form solutions
【Paper Link】 【Pages】:46-54
【Authors】: Mengxue Liu ; Andréa W. Richa ; Matthias Rost ; Stefan Schmid
【Abstract】: This paper considers the following fundamental maximum throughput routing problem: given a set of k (splittable) multicommodity flows with equal demands in an n-node network, select and route a subset of flows such that the total number of commodities routed that satisfy their demands (i.e., the allor-nothing throughput) is maximized. Our main contribution is the first constant (i.e., independent of k and n) through-putapproximation algorithm for this NP-hard problem, with sublin-ear, namely Õ(√k), edge capacity violation ratio. Our algorithm is based on a clever application of randomized rounding. We also present an interesting application of our result in the context of delay-tolerant network scheduling. We complement our theoretical contribution with extensive simulation in two different scenarios, and find that our algorithm performs significantly better than predicted in theory, achieving an edge capacity violation ratio of at most 3.
【Keywords】: Throughput; Approximation algorithms; IP networks; Routing; Capacity planning; Prediction algorithms; Scheduling
【Paper Link】 【Pages】:55-63
【Authors】: Bin Han ; Vincenzo Sciancalepore ; Di Feng ; Xavier Costa-Pérez ; Hans D. Schotten
【Abstract】: The combination of recent emerging technologies such as network function virtualization (NFV) and network programmability (SDN) gave birth to the Network Slicing revolution. 5G networks consist of multi-tenant infrastructures capable of offering leased network “slices” to new customers (e.g., vertical industries) enabling a new telecom business model: Slice-as-a-Service (SlaaS). In this paper, we aim i) to study the slicing admission control problem by means of a multi-queuing system for heterogeneous tenant requests, ii) to derive its statistical behavior model, and iii) to provide a utility-based admission control optimization. Our results analyze the capability of the proposed SlaaS system to be approximately Markovian and evaluate its performance as compared to legacy solutions.
【Keywords】: 5G; network slicing; NFV; cloud service; resource management; queuing theory
【Paper Link】 【Pages】:64-72
【Authors】: Stanislav Lange ; Leonardo Linguaglossa ; Stefan Geissler ; Dario Rossi ; Thomas Zinner
【Abstract】: Network Functions Virtualization (NFV) is among the latest network revolutions, bringing flexibility and avoiding network ossification. At the same time, all-software NFV implementations on commodity hardware raise performance issues with respect to ASIC solutions. To address these issues, numerous software acceleration frameworks for packet processing have appeared in the last few years. Common among these frameworks is the use of batching techniques. In this context, packets are processed in groups as opposed to individually, which is required at high-speed to minimize the framework overhead, reduce interrupt pressure, and leverage instruction-level cache hits. Whereas several system implementations have been proposed and experimentally benchmarked, the scientific community has so far only to a limited extent attempted to model the system dynamics of modern NFV routers exploiting batching acceleration. In this paper, we fill this gap by proposing a simple generic model for such batching-based mechanisms, which allows a very detailed prediction of highly relevant performance indicators. These include the distribution of the processed batch size as well as queue size, which can be used to identify loss-less operational regimes or quantify the packet loss probability in high-load scenarios. We contrast the model prediction with experimental results gathered in a high-speed testbed including an NFV router, showing that the model not only correctly captures system performance under simple conditions, but also in more realistic scenarios in which traffic is processed by a mixture of functions.
【Keywords】: Discrete-Time Model; Queueing Theory; NFV; DPDK; netmap; FD.io; VPP
【Paper Link】 【Pages】:73-81
【Authors】: Tao Wu ; Panlong Yang ; Haipeng Dai ; Wanru Xu ; Mingxue Xu
【Abstract】: The recent breakthrough in Wireless Power Transfer (WPT) provides a promising way to support rechargeable sensors to enrich a series of energy-consuming applications. Unfortunately, two major design restrictions hinder the applicability of rechargeable sensor networks. First, most of the sensor placement schemes are focusing on the sensing tasks instead of the charging utility, which leaves a considerably high performance gap towards the optimal result. Second, the charging scheduling is non-flexible, where full or nothing charging policy suffers from the relatively low charging coverage as well as efficiency. In this paper, we focus on how to efficiently improve the charging utility when introducing charging oriented sensor placement and flexible scheduling policy. To this end, we jointly consider optimizing node positions and charging allocations. In particular, we formulate a general convex optimization problem under a general routing constraint, which generates great difficulty. We utilize area partition and charging discretization methods to reformulate a submodular function maximization problem. Thus a constant approximation algorithm is delivered to construct a near optimal charging tour. To this end, we analyze the performance loss from the discretization to guarantee that the output of the proposed algorithm has more than (1-ε)/4(1-1/e) of the optimal solution, where ε is an arbitrarily small positive parameter (0 ≤ ε ≤ 1). Both simulations and field experiments are conducted to evaluate the performance of our proposed algorithm.
【Keywords】: Task analysis; Resource management; Scheduling; Sensors; Convex functions; Energy consumption; Routing
【Paper Link】 【Pages】:82-90
【Authors】: Xi Zhang ; Qixuan Zhu
【Abstract】: The device-to-device (D2D) communication is an efficient mobile-data offloading technique to significantly improve the cellular base station (BS) spectrum efficiency in the fifth generation (5G) wireless networks by enabling mobile users to directly receive the multimedia data from a nearby mobile users through D2D communication. On the other hand, D2D multimedia-data offloading imposes the new modeling challenges in characterizing the statistical delay-bounded quality of service (QoS) provisioning over two-hop tandem wireless links when a mobile user receives its requested data from the cellular BS and relays it to the next mobile user which is requesting the same data via D2D communications. Thus, one of the most important challenges of the D2D multimedia-data offloading architecture lies in how to satisfy the statistical delay-bounded QoS requirements over the two-hop wireless links which consists of two tandem single-hop links. To tackle these challenges, we propose the overall two-hop wireless link QoS provisioning schemes based on its two individual single-hop statistical QoS requirements. We derive the overall effective capacity's expression of the two-hop tandem wireless links as a function of the single-hop's effective capacities and prove that the overall equivalent effective capacity of the two-hop wireless link is upper bounded by the single-hop effective capacity with the smaller QoS exponent. Moreover, we derive the upper-bound and lower-bound of the equivalent QoS exponent for the overall two-hop wireless links and also show its monotonicity with respect to single-hop QoS exponents. To show the network performance's improvement after integrating the cellular networks and D2D offloading, we compare the scalability of the BS-based cellular wireless networks with and without D2D offloading. We also evaluate and validate our proposed two-hop wireless link statistical delay bounded QoS provisioning schemes over multimedia D2D offloading architecture through numerical analyses.
【Keywords】: Two-hop wireless link; effective capacity; multimedia data offloading; statistical delay-bounded QoS; device-to-device (D2D) communication; performance modeling
【Paper Link】 【Pages】:91-99
【Authors】: Saadallah Kassir ; Gustavo de Veciana ; Nannan Wang ; Xi Wang ; Paparao Palacharla
【Abstract】: The automotive industry is undergoing disruptive changes, e.g., ride sharing and self-driving cars which, in addition to leveraging wireless connectivity, may lead to dramatic changes in the volume of infotainment and work related data consumption of vehicle bound passengers. This paper studies the potential gains of leveraging clusters of V2V interconnected vehicles to enable: (1) improved opportunistic access to the cellular infrastructure; and (2), balancing traffic loads across cells through cluster multihoming. A stochastic geometric model and associated analysis are used to obtain a preliminary understanding of possible gains of cluster-based opportunistic relaying and its sensitivity to the system parameters, e.g., base station density, vehicular cluster size and density etc. An optimal network utility maximization formulation is then developed to serve as a baseline to evaluate a simple distributed cluster management algorithm which for the scenarios considered proves to be near-optimal. Overall the results suggest that 3-10x throughput gains are possible along with significant improvements in user rate fairness depending on the system parameters.
【Keywords】: Vehicular Network; Vehicle-to-Vehicle Communication; Opportunism; Load Balancing
【Paper Link】 【Pages】:100-108
【Authors】: Zhao Li ; Jie Chen ; Kang G. Shin ; Jia Liu
【Abstract】: With the rapid development of wireless communication technologies, the demand for higher data rate and more concurrent transmissions has been continually increasing. Due to the widespread deployment of various wireless technologies, interference has become a key roadblock to the improvement of network performance. Interference has long been known to be harmful, leading to development of numerous interference management (IM) mechanisms based on resource segmentation or signal processing to mitigate or suppress interference. Since a desired signal can be distorted by interference, and thus be incorrectly decoded at the destination, we argue that interference can also be transformed intentionally to extract the desired data from interfering signal(s). Based on this observation, we propose Interference ReCycling (IRC). Under IRC, a recycling signal is generated with the interference a victim receiver (Rx) is subjected to, and then sent by the Rx's associated transmitter (Tx). Under the influence of the recycling signal, the desired data of the victim Tx-Rx pair can be recovered from the interference at the victim Rx. That is, by exploiting the interactions among multiple signals, i.e., recycling signal and interference, useful data information can be extracted from interference, or the unintended data carried in interference can be artificially converted to the desired one. Our theoretical analysis and numerical evaluation have shown that the proposed IRC can fully exploit interference, and hence can significantly improve the spectral efficiency (SE) of the victim Rx compared to the other existing IM methods.
【Keywords】: Interference; Recycling; Wireless communication; Receivers; Data communication; Macrocell networks; Signal processing
【Paper Link】 【Pages】:109-117
【Authors】: Bo Yin ; Shuai Zhang ; Yu Cheng ; Lin X. Cai ; Zhiyuan Jiang ; Sheng Zhou ; Zhisheng Niu
【Abstract】: Motivated by the increasingly urgent demands for delivering fresh information, the age-of-information (AoI) has recently been introduced as an important metric for evaluating the timeliness performance of information update systems and has shed light on a number of research studies. Nevertheless, the most common goal of the existing works does not characterize the value of information freshness from the users' perspective. In this paper, we introduce the concept of effective AoI (EAoI) to quantify the freshness of the information users utilize for decision-making. We consider a general request-response model, which captures both proactive information update and timely information delivery, for investigating the scheduling problem with respect to EAoI minimization. By decomposing the scheduling problem into multiple computationally tractable subproblems, we propose request-aware scheduling policies for static and dynamic request models, respectively. The numerical results show that serving users requests proactively can reduce time-average EAoI in both scenarios.
【Keywords】: Servers; Dynamic scheduling; Processor scheduling; Computational modeling; Numerical models; Indexes
【Paper Link】 【Pages】:118-126
【Authors】: Chengzhang Li ; Shaoran Li ; Y. Thomas Hou
【Abstract】: Recently, a new metric, called Age of Information (AoI), has become popular to quantify the freshness of information collected at network edge. AoI research is still in its infancy and most prior efforts assume overly simplified models in their investigation. In this paper, we consider a more general model for AoI research that is closer to what happens in the real world. Specifically, we consider general and heterogeneous sampling behaviors among source nodes, varying sample size, and multiple data transmission units in each time slot. Under this much general setting, we develop new theoretical results (in terms of properties and performance bounds) and a new near-optimal low-complexity scheduling algorithm. Our results make a major advance of AoI research in terms of more realistic models.
【Keywords】: Scheduling algorithms; Optimal scheduling; Data communication; Information age; Uplink; Measurement; Base stations
【Paper Link】 【Pages】:127-135
【Authors】: Antonio Massaro ; Francesco De Pellegrini ; Lorenzo Maggi
【Abstract】: In the framework of queuing theory with multiclass jobs, trunk-reservation is an admission control technique to handle job class priority in an online fashion, and serve as many high priority jobs as possible. This is achieved by rejecting jobs with sufficiently low priority when the buffer space becomes a scarce resource, i.e., when the queue may soon overflow. Mathematically, the objective is to maximize the long-term reward of the admitted jobs, where each job is assigned a reward which is monotonic with respect to the priority class it belongs to. In this paper we study online learning of optimal trunk-reservation policies when the system parameters, i.e., class arrival rates and service time, are unknown. Starting from a Markov Decision Process (MDP) formulation, we leverage the stairway structure of the optimal policy to define Integer Gradient Ascent (IGA), a reinforcement learning (RL) algorithm based on policy-gradient methods, specifically tailored to the mathematical properties of the problem at hand. We provide theoretical results on the convergence properties of IGA. Extensive numerical experiments characterize its behavior and confirm that it outperforms standard RL techniques in terms of convergence rate.
【Keywords】: trunk-reservation; reinforcement learning; policy gradient; reinforce
【Paper Link】 【Pages】:136-144
【Authors】: Isfar Tariq ; Rajat Sen ; Gustavo de Veciana ; Sanjay Shakkottai
【Abstract】: In this paper we propose an online algorithm for clustering channel-states and learning the associated achievable multiuser rates. Our motivation stems from the complexity of multiuser scheduling. For instance, MU-MIMO scheduling involves the selection of a user subset and associated rate selection each time-slot for varying channel states (the vector of quantized channels matrices for each of the users) - a complex integer optimization problem that is different for each channel state. Instead, our algorithm clusters the collection of channel states to a much lower dimension, and for each cluster provides achievable multiuser capacity trade-offs, which can be used for user and rate selection. Our algorithm uses a bandit approach, where it learns both the unknown partitions of the channel-state space (channel-state clustering) as well as the capacity region for each cluster along a pre-specified set of directions, by observing the success/failure of the scheduling decisions (e.g. through packet loss). We propose an epoch-greedy learning algorithm that achieves a sub-linear regret, given access to a class of classifying functions over the channel-state space. Finally, we empirically validate the performance of our algorithm through simulations.
【Keywords】: Online Learning; Bandit Algorithms; Wireless Networks; Scheduling; Capacity Region
【Paper Link】 【Pages】:145-153
【Authors】: Bruna Soares Peres ; Otavio Augusto de Oliveira Souza ; Olga Goussevskaia ; Chen Avin ; Stefan Schmid
【Abstract】: We consider the problem of designing dynamic network topologies that self-adjust to the (possibly changing) traffic pattern they serve. Such demand-aware networks currently receive much attention, especially in the context of datacenters, due to emerging technologies supporting the fast reconfiguration of the physical topology. We present the first fully distributed, provably efficient self-adjusting network. Our network called DiSptayNet relies on algorithms that perform decentralized and concurrent topological adjustments to account for changes in the demand. We present a rigorous formal analysis of the correctness and performance of DiSptayNet, which can be seen as an interesting generalization of analyses known from sequential self-adjusting datastructures. We also report on results from extensive trace-driven simulations.
【Keywords】: Network topology; Topology; Peer-to-peer computing; Distributed algorithms; Routing; Upper bound; Knowledge engineering
【Paper Link】 【Pages】:154-162
【Authors】: Fenghua Li ; Zhe Sun ; Ang Li ; Ben Niu ; Hui Li ; Guohong Cao
【Abstract】: Photo sharing on Online Social Networks (OSNs) has become one of the most popular social activities in our daily life. However, some associated friends or bystanders in the photos may not want to be viewed due to privacy concerns. In this paper, we propose the design, implementation and evaluation of HideMe, a framework to preserve the associated users' privacy for online photo sharing. HideMe acts as a plugin to existing photo sharing OSNs, and it enables the following: a) extraction of factors when users upload their photos, b) associated friends in the uploaded photos are able to set their own privacy policies based on scenarios, instead of a photo-by-photo setting, c) any user in other friend's uploaded photos could be hidden away from unwanted viewers based on one time policy generation. We also design a distance-based algorithm to identify and protect the privacy of bystanders. Moreover, HideMe not only protects users' privacy but also reduces the system overhead by a carefully designed face matching algorithm. We have implemented a prototype of HideMe, and evaluation results have demonstrated its effectiveness and efficiency.
【Keywords】: Privacy; Face; Access control; Data privacy; Facebook; Databases
【Paper Link】 【Pages】:163-171
【Authors】: Prasanna Karthik Vairam ; Gargi Mitra ; Vignesh Manoharan ; Chester Rebeiro ; Byrav Ramamurthy ; Kamakoti Veezhinathan
【Abstract】: The IT infrastructure of large organizations consists of devices and software services purchased from multiple vendors. The problem of measuring the quality of service (QoS) of each of these vendor devices (and services) is challenging since the vendors may tamper with the measurements for monetary benefits or saving debugging efforts. Existing solutions for QoS measurement in trusted environments cannot be extended for this problem since the vendors can easily circumvent them. Solutions borrowed from other areas such as client-server QoS measurement do not help either since they incur unreasonable storage and network overheads, or require extensive modifications to the packet headers. In this paper, we propose the Measuring Tape scheme, comprised of (1) a novel data structure called evidence Bloom filter (e-BF) that can be deployed at the vendor devices (and services), and (2) unique querying techniques, which can be used by the administrator to query the e-BF to measure QoS. While e-BF uses storage and computational resources judiciously, the querying techniques ensure resilience to adversarial behavior. We evaluate our solution based on a few real-world and synthetic traces and with different adversaries. Our results highlight the trade-off between resources (i.e., storage and computation) and the accuracy of QoS predictions, as well as its implications on security. We also present an analytical model of e-BF that establishes the relationship between storage, prediction accuracy, and security. Further, we present security arguments to illustrate how our solution thwarts adversarial attempts to tamper QoS.
【Keywords】: Quality of service; Security; Silicon; Reliability; Organizations; Receivers; Software
【Paper Link】 【Pages】:172-180
【Authors】: Shaohuai Shi ; Xiaowen Chu ; Bo Li
【Abstract】: Distributed synchronous stochastic gradient descent has been widely used to train deep neural networks on computer clusters. With the increase of computational power, network communications have become one limiting factor on the system scalability. In this paper, we observe that many deep neural networks have a large number of layers with only a small amount of data to be communicated. Based on the fact that merging some short communication tasks into a single one may reduce the overall communication time, we formulate an optimization problem to minimize the training iteration time. We develop an optimal solution named merged-gradient wait-free backpropagation (MG-WFBP) and implement it in our open-source deep learning platform B-Caffe. Our experimental results on an 8-node GPU cluster with 10GbE interconnect and trace-based simulation results on a 64-node cluster both show that the MG-WFBP algorithm can achieve much better scaling efficiency than existing methods WFBP and SyncEASGD.
【Keywords】: Deep Learning; GPU; Distributed Stochastic Gradient Descent; Gradient Communication; Merged-gradient
【Paper Link】 【Pages】:181-189
【Authors】: Shuyu Shi ; Yaxiong Xie ; Mo Li ; Alex X. Liu ; Jun Zhao
【Abstract】: Respiration rate monitoring is beneficial for the diagnosis of a variety of diseases, such as heart failure and sleep disorders. Radio Frequency (RF) based respiration rate monitoring systems, namely ultra-wideband radar and COTS device, have been proposed without requiring any direct contact with the detected person. However, existing RF based systems either require expensive UWB radio (radar based) or work only in stationary environments (COTS device based). To address the limitations of both radar based and COTS device based systems, in this paper, we propose RespiRadio, a system that can detect a person's respiration rate in dynamic ambient environments via a single TX-RX pair of WiFi cards. The key novelty of RespiRadio is that it overcomes the limit of existing COTS device based respiration rate systems by synthesizing a wider-bandwidth WiFi radio. With the synthesized WiFi radio, we can identify the path reflected by the breathing person and then analyze the periodicity of the signal power measurements only from this path to infer the respiration rate. We experimentally evaluate the performance of RespiRadio in non-static indoor environments and the results demonstrate that the overall estimation error is 0.152 breaths per minute (bpm).
【Keywords】: Wireless fidelity; Monitoring; Bandwidth; Radio frequency; Delays; Ultra wideband radar
【Paper Link】 【Pages】:190-198
【Authors】: Pengfei Liu ; Panlong Yang ; Wen-Zhan Song ; Yubo Yan ; Xiang-Yang Li
【Abstract】: WiFi has become a pervasive communication medium in connecting various devices of WLAN and IoT. However, WiFi connections are vulnerable to the impersonation attack from rogue access points (AP) or devices, whose SSID and/or MAC/IP address are identical to the legitimate devices. This kind of attack is difficult to countermeasure with traditional network security mechanisms. In this paper, we present a novel security mechanism to detect and identify rogue WiFi devices or AP using environment-independent characteristics extracted from channel state information (CSI), and refuse their connections. We find that nonlinear phase errors of different subcarriers change with WiFi network interface cards (NIC), due to the I/Q imbalance and imperfect oscillator of each WiFi NIC. Validated by our experiments, this phase feature across subcarriers is consistent and invariant to location and external environment, and can be extracted to build an essential signature of the NIC itself. Such signature of the transmitter can be calculated in real-time by the receiver and cannot be forged by rogue devices. Extensive experiments with dozens of WiFi devices demonstrate that the proposed mechanism can reliably detect the rogue WiFi connections and prevent impersonation in various scenarios. The speed of identification is 8× faster than that of the state-of-the-art solution. Moreover, the accuracy of rogue connection detection is up to 96% and false alarm rate is shown below 2%.
【Keywords】: Wireless fidelity; Feature extraction; Receivers; Security; Hardware; Transmitters; Mobile handsets
【Paper Link】 【Pages】:199-207
【Authors】: Tianhang Zheng ; Zhi Sun ; Kui Ren
【Abstract】: Trusted identification is critical to secure IoT devices. However, the limited memory and computation power of low-end IoT devices prevent the direct usage of conventional identification systems. RF fingerprinting is a promising technique to identify low-end IoT devices since it only requires the RF signals that most IoT devices can produce for communication. However, most existing RF fingerprinting systems are data-dependent and/or not robust to impacts from wireless channels. To address the above problems, we propose to exploit the mathematical expression of the physical-layer process, regarded as a function T(·), for device identification. T(·) is not directly derivable, so we further propose a model to learn it and employ this function model as the device fingerprint in our system, namely TID. Our proposed function model characterizes the unique physical-layer process of a device that is independent of the transmitted data, and hence, our system TID is data-independent and thus resilient against signal replay attacks. Modeling and further separating channel effects from the function model makes TID channelrobust. We evaluate TID on thousands of random signal packets from 33 different devices in different environments and scenarios, and the overall identification accuracy is over 99%.
【Keywords】: PHY identification; function model
【Paper Link】 【Pages】:208-216
【Authors】: Zhiyuan Jiang ; Sheng Zhou ; Zhisheng Niu ; Yu Cheng
【Abstract】: Information source sampling and update scheduling have been treated separately in the context of real-time status update for age of information optimization. In this paper, a unified sampling and scheduling (S 2 ) approach is proposed, focusing on decentralized updates in multiaccess wireless networks. To gain some insights, we first analyze an example consisting of two-state Markov sources, showing that when both optimized, the unified approach outperforms the separate approach significantly in terms of status tracking error by capturing the key status variation. We then generalize to source nodes with random-walk state transitions whose scaling limit is Wiener processes, the closed-form Whittle's index with arbitrary status tracking error functions is obtained and indexability established. Furthermore, a mean-field approach is applied to solve for the decentralized status update design explicitly. In addition to simulation results which validate the optimality of the proposed S 2 scheme and its advantage over the separate approach, a use case of dynamic channel state information (CSI) update is investigated, with CSI generated by a ray-tracing electromagnetic software.
【Keywords】: Markov processes; Wireless networks; Indexes; Delays; Optimal scheduling; Error probability
【Paper Link】 【Pages】:217-225
【Authors】: Milad Mahdian ; Armin Moharrer ; Stratis Ioannidis ; Edmund Yeh
【Abstract】: We study networks of M/M/1 queues in which nodes act as caches that store objects. Exogenous requests for objects are routed towards nodes that store them; as a result, object traffic in the network is determined not only by demand but, crucially, by where objects are cached. We determine how to place objects in caches to attain a certain design objective, such as, e.g., minimizing network congestion or retrieval delays. We show that for a broad class of objectives, including minimizing both the expected network delay and the sum of network queue lengths, this optimization problem can be cast as an NP-hard submodular maximization problem. We show that so-called continuous greedy algorithm [1] attains a ratio arbitrarily close to 1-1/ e ≈ 0.63 using a deterministic estimation via a power series; this drastically reduces execution time over prior art, which resorts to sampling. Finally, we show that our results generalize, beyond M/M/1 queues, to networks of M/M/k and symmetric M/D/1 queues.
【Keywords】: Kelly networks; cache networks; ICN
【Paper Link】 【Pages】:226-234
【Authors】: Pariya Babaie ; Eman Ramadan ; Zhi-Li Zhang
【Abstract】: In this paper, we develop an optimization decomposition framework for cache management under “BIG” cache abstraction which fully utilizes the cache resources in a cache network. We assign a utility function to each content, and formulate a joint optimization problem to maximize the overall utility of a cache network. We show that this global network utility maximization problem can be decomposed into two sub-problems, the cache allotment problem and object placement problem, which can be solved separately and iteratively. This decoupling enables us to separately optimize the performance objectives from the perspectives of content providers, cache network operators, and users. We provide exact solution to the object placement problem with Poisson and Pareto request interarrival distributions. We also devise a primal-dual algorithm for online content management. We conduct extensive numerical analysis and simulations to evaluate the performance of our optimization decomposition framework, and study the impact of various key factors such as hazard rate functions of the request interarrival distributions and object popularities. We show that our optimization decomposition framework outperform existing heuristic methods.
【Keywords】: Servers; Optimization; Hazards; Content management; Bandwidth; Resource management; Content distribution networks
【Paper Link】 【Pages】:235-243
【Authors】: Georgios S. Paschos ; Apostolos Destounis ; Luigi Vigneri ; George Iosifidis
【Abstract】: This paper introduces a novel caching analysis that, contrary to prior work, makes no modeling assumptions for the file request sequence. We cast the caching problem in the framework of Online Linear optimization (OLO), and introduce a class of minimum regret caching policies, which minimize the losses with respect to the best static configuration in hindsight when the request model is unknown. These policies are very important since they are robust to popularity deviations in the sense that they learn to adjust their caching decisions when the popularity model changes. We first prove a novel lower bound for the regret of any caching policy, improving existing OLO bounds for our setting. Then we show that the Online Gradient Ascent (OGA) policy guarantees a regret that matches the lower bound, hence it is universally optimal. Finally, we shift our attention to a network of caches arranged to form a bipartite graph, and show that the Bipartite Subgradient Algorithm (BSA) has no regret.
【Keywords】: Optimization; Measurement; Servers; Routing; Bipartite graph; Libraries; Machine learning
【Paper Link】 【Pages】:244-252
【Authors】: Haisheng Tan ; Shaofeng H.-C. Jiang ; Zhenhua Han ; Liuyan Liu ; Kai Han ; Qinglin Zhao
【Abstract】: Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a file request might be relayed to other caches or bypassed directly to the memory when a cache miss happens. We take the relaying, bypassing and fetching costs altogether into consideration. We first show the inherent difficulty of the problem even when the online requests are of uniform cost. We propose an O(log K)-competitive randomized algorithm Camul and an O(K)-competitive deterministic algorithm Camul-Det, where K is the total number of slots in all caches. Both online algorithms achieve asymptotically optimal competitive ratios, and can be implemented efficiently such that each request is processed in amortized constant time. We conduct extensive simulations on production data traces from Google and a benchmark workload from Yahoo. It shows that our algorithms dramatically outperform existing schemes, i.e., reducing the total cost by 85% and 43% respectively compared with important baselines and their strengthened versions with request relaying. More importantly, Camul achieves such a good total cost without sacrificing other performance measures, e.g., the hit ratio, and can perform consistently well on various settings of experiment parameters.
【Keywords】: Servers; Cloud computing; Edge computing; Optimized production technology; Google
【Paper Link】 【Pages】:253-261
【Authors】: Ruirong Chen ; Wei Gao
【Abstract】: Cross-technology coexistence is crucial to avoid collisions of wireless transmissions and improve the efficiency of spectrum utilization in today's large-scale wireless network systems, especially the Internet of Things. However, existing approaches to cross-technology coexistence incur additional transmission delay and signal processing overhead, which are unaffordable by extremely weak wireless devices such as embedded sensors and computational RFIDs. These schemes hence fail when being applied to emerging application scenarios, such as smart cities and connected healthcare where weak devices play important roles. In this paper, we design and implement EmBee, a new wireless PHY technique that enables cross-technology coexistence at zero cost or performance loss to these extremely weak wireless devices. The basic idea of EmBee is to exploit the diversity of different wireless technologies' spectrum utilization, so as to adaptively reserve occupied spectrum from the strong devices for weak wireless devices' concurrent data transmissions. We have implemented EmBee over custom wireless hardware and evaluated EmBee under different wireless scenarios. Experiment results show that EmBee can effectively support ZigBee transmissions over a fully occupied WiFi channel without causing any extra delay, while only resulting in 10% WiFi throughput loss.
【Keywords】: Wireless networks; cross-technology coexistence; spectrum reservation
【Paper Link】 【Pages】:262-270
【Authors】: Taekyung Kim ; Wonjun Lee
【Abstract】: Wi-Fi backscatter is an emerging technique that enables ultra-low power wireless communications thanks to the simplicity of a backscatter tag. This simplicity drastically reduces communication power. However, this simplicity also removes channel selectivity of the backscatter tag. In this regard, we introduce two issues, violation of the wireless regulations and the waste of resources, in Wi-Fi backscatter networks. To solve these problems, we introduce channel independent packet detection and error vector demodulation. We first design a backscatter receiver accepting Wi-Fi frames on the listening channel as well as adjacent channels, because the backscatter tag responds to all incoming signals regardless of their frequencies. We then investigate how the error vectors of each subcarrier are changed in Wi-Fi backscatter systems. Based on the analysis, we propose a method that translates the error vectors into a backscatter frame. We implement and evaluate our design with commodity 802.11n access points as carrier sources, a software-defined radio as a receiver, and a 2.4 GHz backscatter tag. The results show that channel independent Wi-Fi backscatter is always better than channel dependent approaches.
【Keywords】: Backscatter; Wireless fidelity; Receivers; Wireless communication; OFDM; Radio frequency; Antennas
【Paper Link】 【Pages】:271-279
【Authors】: Zihan Wang ; Yuan Zhuang ; Zhi Wang ; Xin Wu
【Abstract】: High-quality cellular wireless connection has become a necessity for today's internet users, who however, have to pay high prices when they use conventional ISPs' networks. To alleviate this pain, a new type of “mobile virtual network operators which purchases data plans from multiple ISPs and resells them to individuals in an on-demand way, has emerged. A great challenge for such virtual network operators is to determine how to “match” available data plans to dynamically changing users' demands in an intelligent and instant manner. To this end, we propose CAPITAL, a proactive resource allocation framework based on behavior-driven individual cellular data usage prediction. First, based on measurement studies of a real-world virtual network provider over 2 years covering 3 million users, we reveal the dynamical cellular data demands of users, and the spatial, temporal and behavioral factors that affect individuals' data usage; Second, we propose a context-aware prediction model based on wide & deep network, to capture individual data usage; Third, we formulate the data plan allocation as an assignment problem, and use a shortest augmenting path algorithm to solve it efficiently. Our trace-driven experiments show that our design can reduce the cellular data cost by 78.6% for the network operator, while retaining the same user experience level.
【Keywords】: Resource management; Correlation; IP networks; Context modeling; Predictive models; Space exploration; Wireless communication
【Paper Link】 【Pages】:280-288
【Authors】: Dario Bega ; Marco Gramaglia ; Marco Fiore ; Albert Banchs ; Xavier Costa-Pérez
【Abstract】: Network slicing is a new paradigm for future 5G networks where the network infrastructure is divided into slices devoted to different services and customized to their needs. With this paradigm, it is essential to allocate to each slice the needed resources, which requires the ability to forecast their respective demands. To this end, we present DeepCog, a novel data analytics tool for the cognitive management of resources in 5G systems. DeepCog forecasts the capacity needed to accommodate future traffic demands within individual network slices while accounting for the operator's desired balance between resource overprovisioning (i.e., allocating resources exceeding the demand) and service request violations (i.e., allocating less resources than required). To achieve its objective, DeepCog hinges on a deep learning architecture that is explicitly designed for capacity forecasting. Comparative evaluations with real-world measurement data prove that DeepCog's tight integration of machine learning into resource orchestration allows for substantial (50% or above) reduction of operating expenses with respect to resource allocation solutions based on state-of-the-art mobile traffic predictors. Moreover, we leverage DeepCog to carry out an extensive first analysis of the trade-off between capacity overdimensioning and unserviced demands in adaptive, sliced networks and in presence of real-world traffic.
【Keywords】: Resource management; Deep learning; Base stations; Neural networks; Maximum likelihood detection; Nonlinear filters; 5G mobile communication
【Paper Link】 【Pages】:289-297
【Authors】: Peng-Jun Wan ; Zhu Wang ; Huaqiang Yuan ; Jinling Zhang ; XuFei Mao
【Abstract】: Motivated by the fair rate allocation in a multiaccess Gaussian channel, this paper studies the problem of fair rate allocation over a generalized symmetric polymatroid with box constraints. The best-known algorithm for this problem has time complexity O(n 5 ln O(1) n). In this paper, we present a divide-and-conquer algorithm for this problem with quadratic running time. It is an implementation of a refined decomposing method for the more general separate concave maximization over a polymatroid with box constraints. A key ingredient of the algorithm is a linear-time algorithm for a generalized knapsack problem.
【Keywords】: Resource management; Mathematical model; Computer science; Base stations; Time complexity; Minimization
【Paper Link】 【Pages】:298-306
【Authors】: Ruozhou Yu ; Vishnu Teja Kilari ; Guoliang Xue ; Dejun Yang
【Abstract】: Advances in virtualization technologies and edge computing have inspired a new paradigm for Internet-of-Things (IoT) application development. By breaking a monolithic application into loosely coupled microservices, great gain can be achieved in performance, flexibility and robustness. In this paper, we study the important problem of load balancing across IoT microservice instances. A key difficulty in this problem is the interdependencies among microservices: the load on a successor microservice instance directly depends on the load distributed from its predecessor microservice instances. We propose a graph-based model for describing the load dependencies among microservices. Based on the model, we first propose a basic formulation for load balancing, which can be solved optimally in polynomial time. The basic model neglects the quality-of-service (QoS) of the IoT application. We then propose a QoS-aware load balancing model, based on a novel abstraction that captures a realization of the application's internal logic. The QoS-aware load balancing problem is NP-hard. We propose a fully polynomial-time approximation scheme for the QoS-aware problem. We show through simulation experiments that our proposed algorithm achieves enhanced QoS compared to heuristic solutions.
【Keywords】: IoT; microservice; application graph; load balancing; fully polynomial-time approximation scheme
【Paper Link】 【Pages】:307-315
【Authors】: Zhilong Zheng ; Jun Bi ; Heng Yu ; Haiping Wang ; Chen Sun ; Hongxin Hu ; Jianping Wu
【Abstract】: Network Function Virtualization (NFV) has the potential to offer service delivery flexibility and reduce overall costs by running service function chains (SFCs) on commodity servers with many cores. Existing solutions for placing SFCs in one server treat all CPU cores as equal and allocate isolated CPU cores to different network functions (NFs). However, advanced servers often adopt Non-Uniform Memory Access (NUMA) architecture to improve the scalability of many-core systems. CPU cores are grouped into nodes, incurring performance bottleneck due to cross-node memory access and intra-node resource contention. Our evaluation shows that randomly selecting cores to place NFs in an SFC could suffer from 39.2% lower throughput comparing to an optimal placement solution. In this paper, we propose Octans, an NFV orchestrator to achieve maximum aggregate throughput of all SFCs in many-core systems. Octans first formulates the optimization problem as a Non-Linear Integer Programming (NLIP) model. Then we identify the key factor for problem solving as evaluating the throughput drop of an NF caused by other NFs in the same SFC or different SFCs, i.e. performance drop index, and propose a formal and precise prediction model based on system level performance metrics. Finally, we propose an efficient heuristic algorithm to quickly find near-optimal placement solutions. We have implemented a prototype of Octans. Extensive evaluation shows that Octans significantly improves the aggregate throughput comparing to two state-of the-art placement mechanisms by 26.7%~51.8%, with very low prediction errors of SFC performance (an average deviation of 2.6%). Moreover, Octans could quickly find a near-optimal placement solution with tiny optimality gap (1.2%~3.5%).
【Keywords】: Noise measurement; Servers; Throughput; Aggregates; Instruction sets; Problem-solving
【Paper Link】 【Pages】:316-324
【Authors】: Cuiying Feng ; Luning Wang ; Kui Wu ; Jianping Wang
【Abstract】: Network performance tomography infers performance metrics on internal network links with end-to-end measurements. Existing results in this domain are mainly Boolean-based, i.e., they check whether or not a link is identifiable, and return the exact value on identifiable links. If a link is not identifiable, Boolean-based solution gives no performance result for the link. In this paper, we extend Boolean-based network tomography to bound-based network tomography where the lower and upper bounds are derived for unidentifiable links. We develop an efficient algorithm to obtain the tightest total error bound, and present a solution that can significantly reduce the total number of measurement paths required for deriving the tightest total error bound. Furthermore, we propose a method to deploy a new monitor over existing ones such that the total error bound could be maximally reduced. Compared to the random monitor deployment and the monitor deployment that maximizes the total number of identifiable links, our monitor deployment method can lead to up to 15 and 2.4 times more reduction on total error bound, respectively.
【Keywords】: Monitoring; Tomography; Linear systems; Delays; Upper bound; Measurement uncertainty
【Paper Link】 【Pages】:325-333
【Authors】: Djob Mvondo ; Boris Teabe ; Alain Tchana ; Daniel Hagimont ; Noel De Palma
【Abstract】: vNUMA is the most recent technology used by hypervisors to deal with Non Uniform Memory Access (NUMA) machines, which currently composed most datacenters. vNUMA consists in presenting to the virtual machine (VM) the initial mapping (at boot time) of its virtual resources to physical resources. By this way, all NUMA optimizations implemented by almost all VM's OS (e.g. Linux) can become effective. However, in order to be effective itself, vNUMA imposes that the initial resource mapping of the VM should remain unchanged during the VM lifetime. Current hypervisors enforce this requirement by avoiding virtual resource migration (between different NUMA nodes, in the same machine), VM migration (between different machines), and memory ballooning.However, we found that memory flipping the most efficient network virtualization approach violates the above requirement. In other words, a VM which performs network operations leads the hypervisor implicitly performs memory page migrations. In this paper, we show that violating this requirement can degrade performance by up to 18%. We present two solutions which mitigate the issue. We prototype these solutions in Xen hypervisor, a popular open source hypervisor, which is widely used by Amazon Web Services. The evaluation results, performed with well known benchmarks, show that our two solutions are able to almost cancel the issue, while keeping memory flipping effective.
【Keywords】: Virtual machine monitors; Topology; Virtualization; Benchmark testing; Hardware; Virtual machining; Network topology
【Paper Link】 【Pages】:334-342
【Authors】: Bin Shi ; Haiying Shen
【Abstract】: Live virtual machine migration technique allows migrating an entire OS with running applications from one physical host to another, while keeping all services available without interruption. It provides a flexible and powerful way to balance system load, save power and tolerant faults in data centers. Meanwhile, with the stringent requirements of latency, scalability, and availability, an increasing number of applications are deployed across distributed cloud data-centers. However, existing live migration approaches still suffer from long downtime and serious performance degradation in cross data-center scenes due to the mass of dirty retransmission, which limits the ability of cross data-center scheduling. In this paper, we propose a system named Memory/disk operation aware Lightweight VM Live Migration across data-centers with low performance impact (MLLM). It significantly improves the cross data-center migration performance by reducing the amount of dirty data in the migration process. In MLLM, we predict disk read workingset (i.e., more frequently read contents) and memory write workingset (i.e., more frequently write contents) based on the access sequence trace. And then we adjust the migration models and data transfer sequence based on the workingset information. We also present two optimizing methods to filter unused blocks and to de-duplicate data content by a hot data cache, thereby greatly decreasing the amount of data to be transferred. We implement MLLM on the QEMU/KVM platform and conduct several real-world experiments. The experimental results show that our method averagely reduces 67.0% of total migration time and 41.6% service downtime over existing methods.
【Keywords】: Hidden Markov models; Bandwidth; Adaptation models; Cloud computing; Quality of service; Hardware; Memory management
【Paper Link】 【Pages】:343-351
【Authors】: Dinuni Fernando ; Jonathan Terner ; Kartik Gopalan ; Ping Yang
【Abstract】: Post-copy is one of the two key techniques (besides pre-copy) for live migration of virtual machines in data centers. Post-copy provides deterministic total migration time and low downtime for write-intensive VMs. However, if post-copy migration fails for any reason, the migrating VM is lost because the VM's latest consistent state is split between the source and destination nodes during migration. In this paper, we present PostCopyFT, a new approach to recover a VM after a destination or network failure during post-copy live migration using an efficient reverse incremental checkpointing mechanism. We have implemented and evaluated our approach in the KVM/QEMU platform. Our experimental results show that the total migration time of post-copy remains unchanged while maintaining low failover time, downtime, and application performance overhead.
【Keywords】: virtual machine; live migration; fault tolerance
【Paper Link】 【Pages】:352-360
【Authors】: Jian Li ; Jianmin Qian ; Haibing Guan
【Abstract】: The non-uniform memory access (NUMA) architecture has become the dominant server architecture due to its scalable bandwidth performance. However, the NUMA architecture also introduces the complicated performance influences to the applications, because of the differentiated remote devices access latency and shared resource access contention. Secondly, quick developments of high speed networking devices make I/O resource be another important performance affecting element for I/O-intensive cloud applications on NUMA server. Thirdly, it is more critical in virtualized environment since all resources are managed uniformly and transparently to the VM, and the application behaviors in the VM are shielded from the Virtual Machine Manager (VMM). In this paper, we first give an analytic evaluation for performance influence from the various resource affinity. Motivated by the observations, we then build an accurate performance prediction model, named Resource Affinity performance Influence Estimation (RAIE). RAIE provides a novel performance prediction model with the holistic resource affinity parameters that are measured with the platform independent quantification approaches that need be executed in one-off manner. Moreover, RAIE model takes into account the actual influence of resource affinity according to the VM behaviours that can be monitored online without VM modification. Comprehensive evaluations prove that the RAIE model for a VM's performance prediction can increase the average prediction accuracy by 3.27x on a 4node NUMA server with high speed Network Interface Cards (NIC). The RAIE guided scheduling case validates that it can achieve 2.1x performance improvement for actual VMM resource management servicing a VM running the dynamic applications.
【Keywords】: Bandwidth; Throughput; Predictive models; Performance evaluation; Virtualization; Virtual machine monitors; Hardware
【Paper Link】 【Pages】:361-369
【Authors】: Hossein Pirayesh ; Pedram Kheirkhah Sangdeh ; Huacheng Zeng
【Abstract】: While Narrow-Band Internet of Things (NB-IoT) has been standardized by 3GPP to provide wireless Internet access for IoT devices, this service is expected to come with a monthly fee (e.g., $1 or $2 per month per device). As the number of IoT devices tends to be large, the service charge will impose a considerable financial burden on the end users. In this paper, we propose an Energy-Efficient IoT (EE-IoT) communication scheme by taking advantage of the existing WiFi infrastructure that is widely available in home, office, campus, and city environments. EE-IoT will not only avoid monthly service charge for the end users but also maintain a low power consumption for IoT devices. The key component of EE-IoT is an asymmetric physical (PHY) design, which enables an OFDM-based broadband AP to communicate with multiple QAM-based narrowband IoT devices at a low sampling rate (250 ksps) in both uplink and downlink. The trick in our design is that, instead of using the same carrier frequency as the AP, each IoT device tunes its carrier frequency to a particular subcarrier of the AP's OFDM signal, making it possible to encode/decode the data on that subcarrier at a low sampling rate. Based on this new PHY, we propose a MAC protocol to enable EE-IoT in WLANs. We have built a prototype of EE-IoT on a USRP2 wireless testbed and evaluated its performance in an office building environment. Experimental results show that an AP can serve 24 IoT devices simultaneously and each IoT device can achieve more than 187 kbps in the downlink and more than 125 kbps in the uplink.
【Keywords】: Internet of Things; energy efficiency; Wi-Fi; wireless communication; wireless local area network
【Paper Link】 【Pages】:370-378
【Authors】: Kunal Sankhe ; Mauro Belgiovine ; Fan Zhou ; Shamnaz Riyaz ; Stratis Ioannidis ; Kaushik R. Chowdhury
【Abstract】: This paper describes the architecture and performance of ORACLE, an approach for detecting a unique radio from a large pool of bit-similar devices (same hardware, protocol, physical address, MAC ID) using only IQ samples at the physical layer. ORACLE trains a convolutional neural network (CNN) that balances computational time and accuracy, showing 99% classification accuracy for a 16-node USRP X310 SDR testbed and an external database of >100 COTS WiFi devices. Our work makes the following contributions: (i) it studies the hardware-centric features within the transmitter chain that causes IQ sample variations; (ii) for an idealized static channel environment, it proposes a CNN architecture requiring only raw IQ samples accessible at the front-end, without channel estimation or prior knowledge of the communication protocol; (iii) for dynamic channels, it demonstrates a principled method of feedback-driven transmitter-side modifications that uses channel estimation at the receiver to increase differentiability for the CNN classifier. The key innovation here is to intentionally introduce controlled imperfections on the transmitter side through software directives, while minimizing the change in bit error rate. Unlike previous work that imposes constant environmental conditions, ORACLE adopts the `train once deploy anywhere' paradigm with near-perfect device classification accuracy.
【Keywords】: Radio transmitters; Hardware; Radio frequency; Wireless communication; Receivers; Nonlinear distortion; Protocols
【Paper Link】 【Pages】:379-387
【Authors】: Mingyu Yang ; Li-Xuan Chuo ; Karan Suri ; Lu Liu ; Hao Zheng ; Hun-Seok Kim
【Abstract】: This paper presents a novel RF local positioning system, iLPS, specifically designed for challenging indoor non-lineof-sight (NLOS) scenarios and/or urban canyons where global positioning systems (GPS) fail to reliably operate. iLPS enables decimeter-level localization of numerous tags concurrently with wireless communication using frequency-shifting active reflector anchors and orthogonal frequency division multiple access (OFDMA) waveforms. OFDMA signals are devised with carefully assigned subcarriers so that each tag can estimate the time-difference-of-arrival (TDoA) by analyzing the channel impulse response (CIR) from the main and reflector anchors without interfering each other. The proposed active reflection scheme efficiently eliminates the stringent time synchronization requirement while providing the diversity gain for enhanced information decoding reliability at the tag. Significant challenges from NLOS multipaths and the usage of relatively narrow bandwidth of 80MHz in the ISM-band are successfully mitigated by machine learning assisted algorithms. Field trials with the prototype system on Universal Software Radio Peripheral (USRP) confirm that iLPS can achieve decimeter-level accuracy localization and concurrent wireless communication over up to 100m distances.
【Keywords】: Indoor localization; OFDMA; Channel estimation; RF ranging; Time-difference-of-arrival; Neural network
【Paper Link】 【Pages】:388-396
【Authors】: Kai Lei ; Meng Qin ; Bo Bai ; Gong Zhang ; Min Yang
【Abstract】: In this paper, we generally formulate the dynamics prediction problem of various network systems (e.g., the prediction of mobility, traffic and topology) as the temporal link prediction task. Different from conventional techniques of temporal link prediction that ignore the potential non-linear characteristics and the informative link weights in the dynamic network, we introduce a novel non-linear model GCN-GAN to tackle the challenging temporal link prediction task of weighted dynamic networks. The proposed model leverages the benefits of the graph convolutional network (GCN), long short-term memory (LSTM) as well as the generative adversarial network (GAN). Thus, the dynamics, topology structure and evolutionary patterns of weighted dynamic networks can be fully exploited to improve the temporal link prediction performance. Concretely, we first utilize GCN to explore the local topological characteristics of each single snapshot and then employ LSTM to characterize the evolving features of the dynamic networks. Moreover, GAN is used to enhance the ability of the model to generate the next weighted network snapshot, which can effectively tackle the sparsity and the wide-value-range problem of edge weights in real-life dynamic networks. To verify the model's effectiveness, we conduct extensive experiments on four datasets of different network systems and application scenarios. The experimental results demonstrate that our model achieves impressive results compared to the state-of-the-art competitors.
【Keywords】: Temporal Link Prediction; Weighted Dynamic Networks; Generative Adversarial Networks; Graph Convolutional Networks
【Paper Link】 【Pages】:397-405
【Authors】: Qingkai Liang ; Eytan Modiano
【Abstract】: The effectiveness of many optimal network control algorithms (e.g., BackPressure) relies on the premise that all of the nodes are fully controllable. However, these algorithms may yield poor performance in a partially-controllable network where a subset of nodes are uncontrollable and use some unknown policy. Such a partially-controllable model is of increasing importance in real-world networked systems such as overlay-underlay networks. In this paper, we design optimal network control algorithms that can stabilize a partially-controllable network. We first study the scenario where uncontrollable nodes use a queue-agnostic policy, and propose a low-complexity throughput-optimal algorithm, called Tracking-MaxWeight (TMW), which enhances the original MaxWeight algorithm with an explicit learning of the policy used by uncontrollable nodes. Next, we investigate the scenario where uncontrollable nodes use a queue-dependent policy and the problem is formulated as an MDP with unknown queueing dynamics. We propose a new reinforcement learning algorithm, called Truncated Upper Confidence Reinforcement Learning (TUCRL), and prove that TUCRL achieves tunable three-way tradeoffs between throughput, delay and convergence rate.
【Keywords】: Routing; Heuristic algorithms; Reinforcement learning; Throughput; Protocols; Optimization; Stability analysis
【Paper Link】 【Pages】:406-414
【Authors】: Chaoqun You
【Abstract】: As the volume of traffic flows surges, providing Quality-of-Service (QoS) guarantees to flows by fair queueing has never been more challenging in Network Function Virtualization (NFV). There has been a recent effort in both industry and academia to develop fair queueing algorithms across multiple resources in NFV. However, all existing works fail to support hierarchical scheduling, a crucial feature that also provides QoS guarantees to grouped flows on tenant boundaries. In this paper, we present two new multi-resource fair queueing algorithms that support hierarchies, collapsed Hierarchical Dominant Resource Fair Queueing (collapsed H-DRFQ) and dove-tailing H-DRFQ, both of which provide hierarchical share guarantees. Through formal analysis, we find that the dove-tailing H-DRFQ outper-forms collapsed H-DRFQ by providing a smaller delay bound. However, according to the simulation results, both algorithms have their pros and cons. Dove-tailing H-DRFQ benefits to the flows with more complex hierarchies, while collapsed H-DRFQ is better for the flows with simpler attribution structures. Meanwhile, our simulation shows that both H-DRFQ algorithms can achieve near-perfect fairness.
【Keywords】: Scheduling; Quality of service; Middleboxes; Network function virtualization; Delays; Bandwidth; Surges
【Paper Link】 【Pages】:415-423
【Authors】: Paolo Laffranchini ; Luís E. T. Rodrigues ; Marco Canini ; Balachander Krishnamurthy
【Abstract】: The emergence of programmable switches has sparked a significant amount of work on new techniques to perform more powerful measurement tasks, for instance, to obtain fine-grained traffic and performance statistics. Previous work has focused on the efficiency of these measurements alone and has neglected flexibility, resulting in solutions that are hard to reuse or repurpose and that often overlap in functionality or goals. In this paper, we propose the use of a set of reusable primitive building blocks that can be composed to express measurement tasks in a concise and simple way. We describe the rationale for the design of our primitives, that we have named MAFIA (Measurements As FIrst-class Artifacts), and using several examples we illustrate how they can be combined to realize a comprehensive range of network measurement tasks. Writing MAFIA code does not require expert knowledge of low-level switch architecture details. Using a prototype implementation of MAFIA, we demonstrate the applicability of our approach and show that the use of our primitives results in compiled code that is comparable in size and resource usage with manually written specialized P4 code, and can be run in current hardware.
【Keywords】: Task analysis; Current measurement; Security; Semiconductor device measurement; Hardware; Monitoring; Packet loss
【Paper Link】 【Pages】:424-432
【Authors】: Sandeep Kumar Singh ; Admela Jukan
【Abstract】: Spectrum defragmentation (DF) as a connection reconfiguration method is essential in elastic optical networks (EONs) in order to minimize connection blocking probability. This paper proposes the first exact Markov model to computing exact blocking probabilities in EONs with DF by taking into account the occupancy status of spectrum slices of all network links, and waiting and serving connections during a DF process. Since the complexity of the exact Markov model increases exponentially with the network capacity and size, we propose a reduced state model where a link occupancy state is defined by the total occupied slices on a fiber link. Furthermore, using a spectrum fragmentation factor in each occupancy state we calculate state-and class-dependent connection setup rates, which is used to compute approximate blocking in EONs with DF. Notably, we show individually the distinct blocking values, one due to resource unavailability and the other due to fragmentation, both under a random-fit and a first-fit spectrum allocation policies. Our numerical results show that the DF process is very useful in reducing overall connection blocking in EONs. We also observe that blocking due to spectrum fragmentation can be reduced, but not eliminated in a mesh network topology even when an optimal DF scheme is deployed.
【Keywords】: Computational modeling; Bandwidth; Analytical models; Radio frequency; Resource management; Markov processes
【Paper Link】 【Pages】:433-441
【Authors】: Ahmed Khalid ; Ahmed H. Zahran ; Cormac J. Sreenan
【Abstract】: Evolved Multimedia Broadcast Multicast Service (eMBMS) is a 3GPP standard that improves the utilization of scarce wireless resources and the quality of the received content. eMBMS uses a Single Frequency Network (SFN) to transmit real-time videos over synchronized resources across neighboring base stations (eNBs) and allows users to share wireless spectrum across multiple cell sites. However the user with the worst channel condition and the eNB with the least available resources limit the throughput of a session. To overcome such limitations, the SFN can be divided into non-overlapping clusters of eNBs and in each cluster users can be split into groups. We formulate an optimization problem that maximizes an operator-defined utility for multiple eMBMS sessions served at multiple bitrates by choosing the optimal set of SFN clusters and user groups for each session. We propose an algorithm, RTOP, that finds the optimal or a near-optimal solution in real-time regardless of the number of eMBMS users. Our extensive simulations indicate that, in comparison to state-of-the-art schemes, RTOP improves the system utility and average user bitrate by up to 14% and 90% respectively. Additionally, we show that the utility of RTOP always stays within a 1% gap from the optimal solution.
【Keywords】: Bit rate; Streaming media; Unicast; Optimization; Real-time systems; Resource management; Standards
【Paper Link】 【Pages】:442-450
【Authors】: Salvatore D'Oro ; Francesco Restuccia ; Alessandro Talamonti ; Tommaso Melodia
【Abstract】: The notions of softwarization and virtualization of the radio access network (RAN) of next-generation (5G) wireless systems are ushering in a vision where applications and services are physically decoupled from devices and network infrastructure. This crucial aspect will ultimately enable the dynamic deployment of heterogeneous services by different network operators over the same physical infrastructure. RAN slicing is a form of 5G virtualization that allows network infrastructure owners to dynamically “slice” and “serve” their network resources (i. e., spectrum, power, antennas, among others) to different mobile virtual network operators (MVNOs), according to their current needs. Once the slicing policy (i.e., the percentage of resources assigned to each MVNO) has been computed, a major challenge is how to allocate spectrum resources to MVNOs in such a way that (i) the slicing policy defined by the network owner is enforced; and (ii) the interference among different MVNOs is minimized. In this article, we mathematically formalize the RAN slicing enforcement problem (RSEP) and demonstrate its NP-hardness. For this reason, we design three approximation algorithms that render the solution scalable as the RSEP increases in size. We extensively evaluate their performance through simulations and experiments on a testbed made up of 8 software-defined radio peripherals. Experimental results reveal that not only do our algorithms enforce the slicing policies, but can also double the total network throughput when intra-MVNO power control policies are used in conjunction.
【Keywords】: Network Slicing; 5G; Radio Access Network (RAN); Interference Management
【Paper Link】 【Pages】:451-459
【Authors】: Lou Salaun ; Marceau Coupechoux ; Chung Shue Chen
【Abstract】: Non-orthogonal multiple access (NOMA) has received significant attention for future wireless networks. NOMA outperforms orthogonal schemes, such as OFDMA, in terms of spectral efficiency and massive connectivity. The joint subcarrier and power allocation problem in NOMA is NP-hard to solve in general, due to complex impacts of signal superposition on each users achievable data rates, as well as combinatorial constraints on the number of multiplexed users per sub-carrier to mitigate error propagation. In this family of problems, weighted sum-rate (WSR) is an important objective function as it can achieve different tradeoffs between sum-rate performance and user fairness. We propose a novel approach to solve the WSR maximization problem in multi-carrier NOMA with cellular power constraint. The problem is divided into two polynomial time solvable sub-problems. First, the multi-carrier power control (given a fixed subcarrier allocation) is non-convex. By taking advantage of its separability property, we design an optimal and low complexity algorithm (MCPC) based on projected gradient descent. Secondly, the single-carrier user selection is a non-convex mixed-integer problem that we solve using dynamic programming (SCUS). This work also aims to give an understanding on how each sub-problem's particular structure can facilitate the algorithm design. In that respect, the above MCPC and SCUS are basic building blocks that can be applied in a wide range of resource allocation problems. Furthermore, we propose an efficient heuristic to solve the general WSR maximization problem by combining MCPC and SCUS. Numerical results show that it achieves near-optimal sum-rate with user fairness, as well as significant performance improvement over OMA.
【Keywords】: Resource management; Decoding; NOMA; Complexity theory; Silicon carbide; Multiplexing; Interference
【Paper Link】 【Pages】:460-468
【Authors】: Pu Wang ; Ning Wang ; Monireh Dabaghchian ; Kai Zeng ; Zheng Yan
【Abstract】: In this paper, we consider a wireless powered backscatter communication (WPBC) network in which a full-duplex access point (AP) simultaneously transmits information and energy signals by injecting artificial noise (AN) to secure the backscatter transmission from multiple backscatter devices (BDs). To maximize the minimum throughput and ensure fairness and security, we formulate an optimization problem by jointly considering the power splitting ratio between dedicated information signals and AN, backscatter time and signal power allocation among multiple BDs. For a single BD network, we obtain a closed-form solution and evaluate its validity through proof-of-concept experiments. For the general case with multiple BDs, we present an iterative algorithm by leveraging block coordinate descent (BCD) and successive convex approximation optimization to solve a non-convex problem incurred in WPBC. We further show the convergence of the proposed algorithm and analyze its complexity. Finally, extensive simulation results show that the proposed algorithm achieves an optimal and equitable throughput for all BDs, and our work provides a good perspective of resource allocation to improve the performance of WPBC networks.
【Keywords】: Backscatter; Resource management; Throughput; Security; Radio frequency; RF signals; Optimization
【Paper Link】 【Pages】:469-477
【Authors】: Klaus-Tycho Foerster ; Yvonne Anne Pignolet ; Stefan Schmid ; Gilles Trédan
【Abstract】: To meet the stringent requirements on the maximally tolerable disruptions of traffic under link failures, many communication networks feature some sort of static failover mechanism for fast rerouting. However, configuring such static failover mechanisms to achieve a high degree of robustness is known to be challenging, in particular when packet tagging or dynamic node state cannot be used. This paper initiates the systematic study of such local fast failover mechanisms which not only provide connectivity guarantees, even under multiple link failures, but also account for the quality of the resulting failover routes, with respect to locality (i.e., route length) and congestion. Failover quality has received less attention in the literature so far, yet it is increasingly important to support emerging applications.We first show that there exists an inherent tradeoff in terms of achievable locality and congestion of failover routes. We then present CASA, an algorithm providing a high degree of robustness as well as a provable quality of fast rerouting. CASA combines two crucial static resilient routing techniques: combinatorial designs and arc-disjoint arborescences. We complement our formal analysis with a simulation study, in which we compare our algorithms with the state-of-the-art in different scenarios and show benefits in terms of stretch, load, and resilience.
【Keywords】: Routing; Load modeling; Resilience; Robustness; Tagging; Resource management; Computer science
【Paper Link】 【Pages】:478-486
【Authors】: Huanle Xu ; Yang Liu ; Wing Cheong Lau ; Jun Guo ; Alex X. Liu
【Abstract】: Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today's large-scale data analytics [1], [2]. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job's lifetime, which makes it difficult to assign valuable tasks to well-performed machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.
【Keywords】: Multi-armed bandit; online optimization; approximation jobs; regret bound
【Paper Link】 【Pages】:487-495
【Authors】: Tian Pan ; Enge Song ; Zizheng Bian ; Xingchen Lin ; Xiaoyu Peng ; Jiao Zhang ; Tao Huang ; Bin Liu ; Yunjie Liu
【Abstract】: With the ever-increasing complexity of networks, fine-grained network monitoring enables better network reliability and timely feedback control. The In-band Network Telemetry (INT) allows cost-effective network monitoring by encapsulating device-internal states into probe packets. However, INT only specifies an underlying device-level primitive while how to achieve network-wide traffic monitoring remains undefined. In this work, we propose INT-path, a network-wide telemetry framework, by decoupling the system into a routing mechanism and a routing path generation policy. Specifically, we embed source routing into INT probes to allow specifying the route the probe packet takes through the network. Above the mechanism, we develop an Euler trail-based path planning policy to generate non-overlapped INT paths that cover the entire network with a minimum path number. Besides, an exhaustive analysis of algorithm's run-time complexity is also provided. INT-path can “encode” the network-wide traffic status into a series of “bitmap images”, transforming network troubleshooting into pattern recognition problems. INT-path is very suitable for deployment in data center networks thanks to their symmetric network topologies.
【Keywords】: Probes; Monitoring; Telemetry; Routing; Path planning; Routing protocols; IP networks
【Paper Link】 【Pages】:496-504
【Authors】: Sisi Xiong ; Qing Cao ; Weisheng Si
【Abstract】: One critical challenge of managing modern data center networks lies in that existing network protocols provide limited visibility on the internal routing and forwarding decisions made by the control plane, leading to difficulties on fast diagnosis and identification of root causes for performance bugs and anomalies. In this paper, we develop and evaluate a “debugging mode” for packet forwarding, where we demonstrate a possible design space by introducing a programmable header field into data packets used for diagnosis purposes. These headers can be manipulated by routers in intermediate hops to perform tracing and diagnosis operations, thereby providing much greater visibility on the control plane and data plane operations. To make this design scalable and feasible, we exploit the software APIs provided by the latest software-defined networking (SDN) technologies, where the network control plane is separated from the underlying data plane, so that we can reprogram the network forwarding functions dynamically. Compared to existing alternative approaches, our approach is adaptive and programmable, allowing dynamic and on-demand receiver-side decoding with extremely low overhead. We emphasize that as this “debugging mode” can be enabled and disabled by network managers as demanded, it introduces zero overhead to normal traffic if everything is operating as expected. Our evaluation results on a real SDN network testbed demonstrate the effectiveness of the proposed approaches.
【Keywords】: Network topology; Lenses; Debugging; Data centers; Routing; Switches
【Paper Link】 【Pages】:505-513
【Authors】: Yixin Bao ; Yanghua Peng ; Chuan Wu
【Abstract】: Production machine learning (ML) clusters commonly host a variety of distributed ML workloads, e.g., speech recognition, machine translation. While server sharing among jobs improves resource utilization, interference among co-located ML jobs can lead to significant performance downgrade. Existing cluster schedulers (e.g., Mesos) are interference-oblivious in their job placement, causing suboptimal resource efficiency. Interference-aware job placement has been studied in the literature, but was treated using detailed workload profiling and interference modeling, which is not a general solution. This paper presents Harmony, a deep learning-driven ML cluster scheduler that places training jobs in a manner that minimizes interference and maximizes performance (i.e., training completion time). Harmony is based on a carefully designed deep reinforcement learning (DRL) framework augmented with reward modeling. The DRL employs state-of-the-art techniques to stabilize training and improve convergence, including actor-critic algorithm, job-aware action space exploration and experience replay. In view of a common lack of reward samples corresponding to different placement decisions, we build an auxiliary reward prediction model, which is trained using historical samples and used for producing reward for unseen placement. Experiments using real ML workloads in a Kubernetes cluster of 6 GPU servers show that Harmony outperforms representative schedulers by 25% in terms of average job completion time.
【Keywords】: Training; Servers; Interference; Graphics processing units; Computational modeling; Machine learning; Resource management
【Paper Link】 【Pages】:514-522
【Authors】: Stephen Pasteris ; Shiqiang Wang ; Mark Herbster ; Ting He
【Abstract】: Mobile edge computing (MEC) is a promising technique for providing low-latency access to services at the network edge. The services are hosted at various types of edge nodes with both computation and communication capabilities. Due to the heterogeneity of edge node characteristics and user locations, the performance of MEC varies depending on where the service is hosted. In this paper, we consider such a heterogeneous MEC system, and focus on the problem of placing multiple services in the system to maximize the total reward. We show that the problem is NP-hard via reduction from the set cover problem, and propose a deterministic approximation algorithm to solve the problem, which has an approximation ratio that is not worse than(1-e -1 )/4. The proposed algorithm is based on two subroutines that are suitable for small and arbitrarily sized services, respectively. The algorithm is designed using a novel way of partitioning each edge node into multiple slots, where each slot contains one service. The approximation guarantee is obtained via a specialization of the method of conditional expectations, which uses a randomized procedure as an intermediate step. In addition to theoretical guarantees, simulation results also show that the proposed algorithm outperforms other state-of-the-art approaches.
【Keywords】: Approximation algorithms; Partitioning algorithms; Hardware; Government; Optimized production technology; Edge computing; Simulation
【Paper Link】 【Pages】:523-531
【Authors】: Gamal Sallam ; Bo Ji
【Abstract】: With the advent of Network Function Virtualization (NFV), network services that traditionally run on proprietary dedicated hardware can now be realized using Virtual Network Functions (VNFs) that are hosted on general-purpose commodity hardware. This new network paradigm offers a great flexibility to Internet service providers (ISPs) for efficiently operating their networks (collecting network statistics, enforcing management policies, etc.). However, introducing NFV requires an investment to deploy VNFs at certain network nodes (called VNF-nodes), which has to account for practical constraints such as the deployment budget and the VNF-node capacity. To that end, it is important to design a joint VNF-nodes placement and capacity allocation algorithm that can maximize the total amount of network flows that are fully processed by the VNF-nodes while respecting such practical constraints. In contrast to most prior work that often neglects either the budget constraint or the capacity constraint, we explicitly consider both of them. We prove that accounting for these constraints introduces several new challenges. Specifically, we prove that the studied problem is not only NP-hard but also non-submodular. To address these challenges, we introduce a novel relaxation method such that the objective function of the relaxed placement subproblem becomes submodular. Leveraging this useful submodular property, we propose two algorithms that achieve an approximation ratio of 1/2(1 - 1/e) and 1/3(1 - 1/e) for the original non-relaxed problem, respectively. Finally, we corroborate the effectiveness of the proposed algorithms through extensive evaluations using both trace-driven simulations and simulations based on synthesized network settings.
【Keywords】: Resource management; Network function virtualization; Hardware; Linear programming; Approximation algorithms; Relaxation methods; Web and internet services
【Paper Link】 【Pages】:532-540
【Authors】: Chen Chen ; Wei Wang ; Bo Li
【Abstract】: Deep learning is usually performed in GPU clusters where each worker machine iteratively refines the model parameters by communicating the update with the Parameter Server (PS). More often than not, workers communicate in a synchronous manner, so as to avoid using out-of-dated parameters and make high-quality refinement in each iteration. However, as all workers synchronize with the PS simultaneously, the communication becomes a severe bottleneck. To address this problem, in this paper we propose the Round-Robin Synchronous Parallel (R 2 SP) scheme, which coordinates workers to make updates in an evenly-gapped, round-robin manner. This way, R 2 SP can minimize the network contention at a minimum cost of the refinement quality. We further extend R 2 SP to heterogeneous clusters by adaptively tuning the batch size of each worker based on its processing capability. We have implemented R 2 SP as a ready-to-use python library for status-quo deep learning frameworks. EC2 deployment in GPU clusters show that R 2 SP effectively mitigates the communication bottlenecks, accelerating the training of popular image classification models by up to 25%.
【Keywords】: Training; Synchronization; Graphics processing units; Bandwidth; Servers; Computational modeling; Convergence
【Paper Link】 【Pages】:541-549
【Authors】: Yongzhi Wang ; Yulong Shen ; Cuicui Su ; Ke Cheng ; Yibo Yang ; Anter Faree ; Yao Liu
【Abstract】: When a program is executed on an untrusted cloud, the confidentiality of the program's logics needs to be protected. Control flow obfuscation is a direct approach to obtain this goal. However, existing methods in this direction cannot achieve both high confidentiality and low overhead. In this paper, we propose CFHider, a hardware-assisted method to protect the control flow confidentiality. By combining program transformation and Intel Software Guard Extension (SGX) technology, CFHider moves branch statement conditions to an opaque and trusted memory space, i.e., the enclave, thereby offering a guaranteed control flow confidentiality. Based on the design of CFHider, we developed a prototype system targeting on Java applications. Our analysis and experimental results indicate that CFHider is effective in protecting the control flow confidentiality and incurs a much reduced performance overhead than existing software-based solutions (by a factor of 8.8).
【Keywords】: Cloud computing; Software; Java; Security; Transforms; Prototypes
【Paper Link】 【Pages】:550-558
【Authors】: Mohannad Alhanahnah ; Qiben Yan ; Hamid Bagheri ; Hao Zhou ; Yutaka Tsutano ; Witawas Srisa-an ; Xiapu Luo
【Abstract】: Java reflection and dynamic class loading (DCL) are effective features for enhancing the functionalities of Android apps. However, these features can be abused by sophisticated malware to bypass detection schemes. Advanced malware can utilize reflection and DCL in conjunction with Android Inter-App Communication (IAC) to launch collusion attacks using two or more apps. Such dynamically revealed malicious behaviors enable a new type of stealthy, collusive attacks, bypassing all existing detection mechanisms. In this paper, we present DINA, a novel hybrid analysis approach for identifying malicious IAC behaviors concealed within dynamically loaded code through reflective/DCL calls. DINA continuously appends reflection and DCL invocations to control-flow graphs; it then performs incremental dynamic analysis on such augmented graphs to detect the misuse of reflection and DCL that may lead to malicious, yet concealed, IAC activities. Our extensive evaluation on 3,000 real-world Android apps and 14,000 malicious apps corroborates the prevalent usage of reflection and DCL, and reveals previously unknown and potentially harmful, hidden IAC behaviors in real-world apps.
【Keywords】: Mobile security; inter-app communication; reflection; dynamically loaded code
【Paper Link】 【Pages】:559-567
【Authors】: Liyao Xiang ; Jingbo Yang ; Baochun Li
【Abstract】: With the amount of user data crowdsourced for data mining dramatically increasing, there is an urgent need to protect the privacy of individuals. Differential privacy mechanisms are conventionally adopted to add noise to the user data, so that an adversary is not able to gain any additional knowledge about individuals participating in the crowdsourcing, by inferring from the learned model. However, such protection is usually achieved with significantly degraded learning results. We have observed that the fundamental cause of this problem is that the relationship between model utility and data privacy is not accurately characterized, leading to privacy constraints that are overly strict. In this paper, we address this problem from an optimization perspective, and formulate the problem as one that minimizes the accuracy loss given a set of privacy constraints. We use sensitivity to describe the impact of perturbation noise to the model utility, and propose a new optimized additive noise mechanism that improves overall learning accuracy while conforming to individual privacy constraints. As a highlight of our privacy mechanism, it is highly robust in the high privacy regime (when ∈ → 0), and against any changes in the model structure and experimental settings.
【Keywords】: crowdsourcing; data mining; differential privacy; deep learning; optimization
【Paper Link】 【Pages】:568-576
【Authors】: Chaoyue Niu ; Zhenzhe Zheng ; Shaojie Tang ; Xiaofeng Gao ; Fan Wu
【Abstract】: With the commoditization of personal data, pricing privacy has become an intriguing topic. In this paper, we study time-series data trading from the perspective of a data broker in data markets. We thus propose HORAE, which is a PufferfisH privacy based framewOrk for tRAding timE-series data. HORAE first employs Pufferfish privacy to quantity privacy losses under temporal correlations, and compensates data owners with distinct privacy strategies in a satisfying way. Besides, HORAE not only guarantees good profitability at the data broker, but also ensures arbitrage freeness against cunning data consumers. We further apply HORAE to physical activity monitoring, and extensively evaluate its performance on the real-world Activity Recognition with Ambient Sensing (ARAS) dataset. Our analysis and evaluation results reveal that HORAE compensates data owners in a more fine-grained manner than entry/group differential privacy based approaches, well controls the profit ratio of the data broker, and thwarts arbitrage attacks launched by data consumers.
【Keywords】: Data Trading; Data Privacy; Time-Series Data
【Paper Link】 【Pages】:577-585
【Authors】: Zicheng Chi ; Yan Li ; Zhichuan Huang ; Hongyu Sun ; Ting Zhu
【Abstract】: With the exponentially increasing number of Internet of Things (IoT) devices and the huge volume of data generated by these devices, there is a pressing need to investigate a more efficient communication method in both frequency and time domains at the edge of the IoT networks. In this paper, we present Amphista, a novel cross-layer design for IoT communication and data forwarding that can more efficiently utilize the ever increasingly crowded 2.4 GHz spectrum near the gateway. Specifically, by using a single ZigBee data stream, Amphista enables a ZigBee device to send out two different pieces of information to both the WiFi gateway and another ZigBee device. We further leverage this unique feature and design a novel forwarding protocol that can simultaneously forward uplink (e.g., collecting sensing data) and downlink (e.g., disseminating software updates) data by using a single ZigBee data stream. Our extensive experimental results show that Amphista significantly improves throughput (by up to 400×) and reduces the latency.
【Keywords】: Zigbee; Wireless fidelity; Logic gates; Demodulation; Uplink; Downlink; Cameras
【Paper Link】 【Pages】:586-594
【Authors】: Vijay K. Shah ; Simone Silvestri ; Brian Luciano ; Sajal K. Das
【Abstract】: This paper presents a novel network architecture, termed neXt-generation CHAllenged NeTwork (X-CHANT), for improving connectivity in rural environments. The underlying idea is to deploy diverse Dynamic Spectrum Access (d-DSA) radio devices on the public transportation vehicles, such as buses. This results in a d-DSA enabled delay-tolerant network in which the devices can operate in various (un)licensed bands (e.g., TV, LTE, ISM, CBRS), if available. Given the lack of research in efficient routing for such time-varying d-DSA enabled networks, we propose a novel diverse DSA aware routing (dDSAaR) protocol that jointly exploits various (un)licensed bands besides the time-varying yet sufficiently predictable mobility of public transportation vehicles. We compare X-CHANT, utilizing dDSAaR, to the conventional non-DSA/DSA architectures, utilizing a standard (single band) routing protocol (e.g., Epidemic). We use real bus mobility traces collected at the University of Massachusetts, Amherst campus. Results show that X-CHANT achieves better message delivery, negligible message overhead, and better energy expenditure, at the expense of a slight increase in delay. Never-theless, the delay improves with higher predictable mobility.
【Keywords】: Dynamic spectrum access; Space-time-band graph; Challenged networks; Rural connectivity
【Paper Link】 【Pages】:595-603
【Authors】: Ali Rahmati ; Xiaofan He ; Ismail Güvenç ; Huaiyu Dai
【Abstract】: Aerial base station (ABS) is a promising solution for public safety as it can be deployed in coexistence with cellular networks to form a temporary communication network. However, the interference from the primary cellular network may severely degrade the performance of an ABS network. With this consideration, an adaptive dynamic interference avoidance scheme is proposed in this work for ABSs coexisting with a primary network. In the proposed scheme, the mobile ABSs can reconfigure their locations to mitigate the interference from the primary network, so as to better relay the data from the designated source(s) to destination(s). To this end, the single/multi-commodity maximum flow problems are formulated and the weighted Cheeger constant is adopted as a criterion to improve the maximum flow of the ABS network. In addition, a distributed algorithm is proposed to compute the optimal ABS moving directions. Moreover, the trade-off between the maximum flow and the shortest path trajectories is investigated and an energy-efficient approach is developed as well. Simulation results show that the proposed approach is effective in improving the maximum network flow and the energy-efficient approach can save up to 39% of the energy for the ABSs with marginal degradation in the maximum network flow.
【Keywords】: Aerial base station; UAV; optimal trajectory; maximum flow problem; energy efficiency
【Paper Link】 【Pages】:604-612
【Authors】: Minh Vu ; Lisong Xu ; Sebastian G. Elbaum ; Wei Sun ; Kevin Qia
【Abstract】: The correctness of network protocol implementations is difficult to test mainly because of the temporal uncertain nature of network events. In order to test the correctness of a network protocol implementation using network simulators, we need to systematically simulate the behavior of the network protocol under all possible cases of temporal uncertain events, which is very time consuming. The recently proposed Symbolic Execution based Interval Branching (SEIB) simulates a group of uncertain cases together in a single simulation branch, and thus is more efficient than brute force testing. In this paper, we argue that the efficiency of SEIB could be further exponentially improved by eliminating unnecessary comparisons of the event timestamps. Specifically, we summarize and present three general types of unnecessary comparisons when SEIB is applied to a general network simulator, and then correspondingly propose three novel techniques to eliminate them. Our extensive simulations show that our techniques can improve the efficiency of SEIB by several orders of magnitude, such as from days to minutes.
【Keywords】: Network protocol testing; symbolic execution; temporal uncertainty; discrete event simulator
【Paper Link】 【Pages】:613-621
【Authors】: Moinul Hossain ; Jiang Xie
【Abstract】: In a cognitive radio-based network (CRN), secondary users opportunistically access underutilized spectrum resources and stop utilizing these resources when licensed or primary users reappear. Recently, a new attack, off-sensing (OS), has shed light on a vulnerability in the FCC policy of CRN. OS-attack utilizes the off-sensing interval of a victim to perpetrate the attack and to manipulate the victim's spectrum availability. However, prior work on OS-attack considers a deterministic approach that is unrealistic and is futile to fortify against conventional defense techniques. In this paper, we propose a new random approach, the random-OS attack, which adapts to realistic scenarios and is difficult to detect using conventional techniques. Then, we propose a novel safeguard approach based on the Markov decision process to defend the proposed attack, namely hide and seek. We also introduce an OS-attack detection strategy, which utilizes the sensing history to detect the presence of attackers without violating any policy or design constraints and without any networking overhead. Mathematical analysis and extensive simulation results exhibit the superior performance of our proposed works and advent a direction in designing safeguard strategies without amending the current FCC policies.
【Keywords】: Sensors; Jamming; FCC; Interference; Markov processes; White spaces; Security
【Paper Link】 【Pages】:622-630
【Authors】: Parinaz Naghizadeh ; Maria Gorlatova ; Andrew S. Lan ; Mung Chiang
【Abstract】: We study a multi-agent partially observable environment in which autonomous agents aim to coordinate their actions, while also learning the parameters of the unknown environment through repeated interactions. In particular, we focus on the role of communication in a multi-agent reinforcement learning problem. We consider a learning algorithm in which agents make decisions based on their own observations of the environment, as well as the observations of other agents, which are collected through communication between agents. We first identify two potential benefits of this type of information sharing when agents' observation quality is heterogeneous: (1) it can facilitate coordination among agents, and (2) it can enhance the learning of all participants, including the better informed agents. We show however that these benefits of communication depend in general on its timing, so that delayed information sharing may be preferred in certain scenarios.
【Keywords】: Multi-agent reinforcement learning; information sharing; cooperative games
【Paper Link】 【Pages】:631-639
【Authors】: Debasis Mitra ; Abhinav Sridhar
【Abstract】: The formation of consortiums of a broadband access Internet Service Provider (ISP) and multiple Content Providers (CP) is considered for large-scale content caching. The consortium members share costs from operations and investments in the supporting infrastructure. Correspondingly, the model's cost function includes marginal and fixed costs; the latter has been important in determining industry structure. Also, if Net Neutrality regulations permit, additional network capacity on the ISP's last mile may be contracted by the CPs. The number of subscribers is determined by a combination of users' price elasticity of demand and Quality of Experience. The profit generated by a coalition after pricing and design optimization determines the game's characteristic function. Coalition formation is by a bargaining procedure due to Okada (1996) based on random proposers in a non-cooperative, multi-player game-theoretic framework. A necessary and sufficient condition is obtained for the Grand Coalition to form, which bounds subsidies from large to small contributors. Hence, for the Grand Coalition to form it is necessary to administer Coalition Admission Control. Caching is generally supported even under Net Neutrality regulations. The Grand Coalition's profit matches upper bounds. Numerical results illustrate the analytic results.
【Keywords】: Content Delivery; Nash Bargaining; Net Neutrality; Consortiums
【Paper Link】 【Pages】:640-648
【Authors】: Costas Courcoubetis ; Antonis Dimakis
【Abstract】: We introduce a queueing model for passengers waiting to get transport by drivers participating in a ridesharing system. The effect of available drivers' mobility pattern, their willingness to accept rides in a given location, and the incentives offered by the platform, on system throughput is considered. We characterize the largest set of passenger arrival rates which can be served by a fixed number of drivers under any policy dictating the mobility pattern of available drivers. It turns out that any rate in this set can be achieved by offering appropriate constant but region-dependent rewards to drivers for passenger pick up. Moreover, it is shown that dynamic rewards which scale in proportion to the number of passengers waiting for pick up in each region, not only maximize throughput but also significantly decrease pick up delays.
【Keywords】: crowdsourcing; ridesharing; pricing; queueing model; stability
【Paper Link】 【Pages】:649-657
【Authors】: Shi Su ; Wai-Tian Tan ; Xiaoqing Zhu ; Rob Liston
【Abstract】: Multi-user MIMO (MU-MIMO) is a technique in 802.11ac and 802.11ax that improves spectral efficiency by allowing concurrent communication between one AP and multiple clients. In practice, the expected gain is not always achieved and is sometimes even negative. Using a commodity 802.11ac AP, we experimentally determine that the inclusion of clients either in motion or with low SNR can cause throughput below that of single-user transmissions. We then propose a pre-screening algorithm using reinforcement learning to predict if a client can benefit from participating in MU-MIMO. Our algorithm is based on a sequence of channel state information (CSI), SNR, and client device type, and can automatically adapt to the motion of individual clients. Experimental results using a commodity AP show that the additional implementation of the pre-screening algorithm alone, without otherwise modifying MU-MIMO client grouping or link parameter selection algorithms, can improve system throughput by up to 40% when half of the clients are moving. Over 20% throughput improvement is maintained when between 25% to 75% of the clients are moving.
【Keywords】: MU-MIMO; IEEE 802.11ac; Reinforcement Learning
【Paper Link】 【Pages】:658-666
【Authors】: Junyang Shi ; Mo Sha
【Abstract】: Wireless Sensor-Actuator Network (WSAN) technology is gaining rapid adoption in process industries in recent years. A WSAN typically connects sensors, actuators, and controllers in industrial facilities, such as steel mills, oil refineries, chemical plants, and infrastructures implementing complex monitoring and control processes. IEEE 802.15.4 based WSANs operate at low-power and can be manufactured inexpensively, which make them ideal where battery lifetime and costs are important. Recent studies have shown that the selection of network parameters has a significant effect on the network performance. However, the current practice of parameter selection is largely based on experience and rules of thumb involving a coarse-grained analysis of expected network load and dynamics or measurements during a few field trials, resulting in non-optimal decisions in many cases. In this work, we develop the Parameter Selection and Adaptation FramEwork (P-SAFE) that optimally configures the network parameters based on the application Quality of Service (QoS) demand and adapts the configuration at runtime to consistently satisfy the dynamic requirements. We implement P-SAFE and evaluate it on three physical testbeds. Experimental results show our solution can significantly better meet the application QoS demand compared to the state of the art.
【Keywords】: Industrial Wireless Sensor-Actuator Networks; Parameter Adaptation; Parameter Selection
【Paper Link】 【Pages】:667-675
【Authors】: Vincenzo Mancuso ; Paolo Castagno ; Matteo Sereno ; Marco Ajmone Marsan
【Abstract】: In this paper we investigate the allocation of resources to slices on the radio interface of one cell. In particular, we develop a detailed stochastic model of the behaviour of the sliced cell radio access, including most features of the standard access procedures. Our model allows the computation of the throughput achieved by each slice, as well as the distribution of delays for each slice. The availability of a model capable of accurately predicting the performance achieved by services using different slices as a function of the cell parameters is extremely important for the automated run time management of the cell and for the correct setting of its parameters.Specifically, while our model can cope with a number of slices, we focus on the case of one cell comprising one slice for human type communications and one slice for machine type communications, and we discuss relevant emerging behaviours in the slices performance, as functions of the cell parameters.We validate the analytical predictions by comparison against the estimates of a detailed simulator, proving the accuracy of the model. Our model turns out to be very effective in providing insight and guidelines for allocation and management of resources in cells hosting slices carrying traffic derived from services with different characteristics and performance requirements.
【Keywords】: Resource management; Computer architecture; Throughput; Analytical models; Microprocessors; Network slicing; Computational modeling
【Paper Link】 【Pages】:676-684
【Authors】: Amit Sheoran ; Sonia Fahmy ; Chunyi Peng ; Navin Modi
【Abstract】: Caller-ID spoofing deceives the callee into believing a call is originating from another user. Spoofing has been strategically used in the now-pervasive telephone fraud, causing substantial monetary loss and sensitive data leakage. Unfortunately, caller-ID spoofing is feasible even when user authentication is in place. State-of-the-art solutions either exhibit high overhead or require extensive upgrades, and thus are unlikely to be deployed in the near future. In this paper, we seek an effective and efficient solution for 4G (and conceptually 5G) carrier networks to detect (and block) caller-ID spoofing. Specifically, we propose Nascent, Network-assisted caller ID authentication, to validate the caller-ID used during call setup which may not match the previously-authenticated ID. Nascent functionality is split between data-plane gateways and call control session functions. By leveraging existing communication interfaces between the two and authentication data already available at the gateways, Nascent only requires small, standard-compatible patches to the existing 4G infrastructure. We prototype and experimentally evaluate three variants of Nascent in traditional and Network Functions Virtualization (NFV) deployments. We demonstrate that Nascent significantly reduces overhead compared to the state-of-the-art, without sacrificing effectiveness.
【Keywords】: Authentication; Logic gates; IP networks; Instant messaging; Telephone sets; Long Term Evolution; Protocols
【Paper Link】 【Pages】:685-693
【Authors】: Damiano Carra ; Giovanni Neglia ; Pietro Michiardi
【Abstract】: We consider in-memory key-value stores used as caches, and their elastic provisioning in the cloud. The cost associated to such caches not only includes the storage cost, but also the cost due to misses: in fact, the cache miss ratio has a direct impact on the performance perceived by end users, and this directly affects the overall revenues for content providers. Our aim is to adapt dynamically the number of caches based on the traffic pattern, to minimize the overall costs.We present a dynamic algorithm for TTL caches whose goal is to obtain close-to-minimal costs. We then propose a practical implementation with limited computational complexity: our scheme requires constant overhead per request independently from the cache size. Using real-world traces collected from the Akamai content delivery network, we show that our solution achieves significant cost savings specially in highly dynamic settings that are likely to require elastic cloud services.
【Keywords】: Cloud computing; Throughput; Time complexity; Heuristic algorithms; Servers; Random access memory
【Paper Link】 【Pages】:694-702
【Authors】: Guocong Quan ; Jian Tan ; Atilla Eryilmaz
【Abstract】: Least-recently-used (LRU) caching and its variants have conventionally been used as a fundamental and critical method to ensure fast and efficient data access in computer and communication systems. Emerging data-intensive applications over unreliable channels, e.g., mobile edge computing and wireless content delivery networks, have imposed new challenges in optimizing LRU caching systems in environments prone to failures. Most existing studies focus on reliable channels, e.g., on wired Web servers and within data centers, which have already yielded good insights with successful algorithms on how to reduce cache miss ratios. Surprisingly, we show that these widely held insights do not necessarily hold true for unreliable channels. We consider a single-hop multi-cache distributed system with data items being dispatched by random hashing. The objective is to achieve efficient cache organization and data placement. The former allocates the total memory space to each of the involved caches. The latter decides data routing strategies and data replication schemes. Analytically we characterize the unreliable LRU caches by explicitly deriving their asymptotic miss probabilities. Based on these results, we optimize the system design. Remarkably, these results sometimes are counterintuitive, differing from the ones obtained for reliable caches. We discover an interesting phenomenon: asymmetric cache organization is optimal even for symmetric channels. Specifically, even when channel unreliability probabilities are equal, allocating the cache spaces unequally can achieve a better performance. We also propose an explicit unequal allocation policy that outperforms the equal allocation. In addition, we prove that splitting the total cache space into separate LRU caches can achieve a lower asymptotic miss probability than resource pooling that organizes the total space in a single LRU cache. These results provide new and even counterintuitive insights that motivate novel designs for caching systems over unreliable channels. They can potentially be exploited to further improve the system performance in real practice.
【Keywords】: Resource management; Hash functions; Nickel; Organizations; System performance; Reliability theory
【Paper Link】 【Pages】:703-711
【Authors】: Rashid Tahir ; Sultan Durrani ; Faizan Ahmed ; Hammas Saeed ; Fareed Zaffar ; Saqib Ilyas
【Abstract】: With the recent boom in the cryptocurrency market, hackers have been on the lookout to find novel ways of commandeering users' machine for covert and stealthy mining operations. In an attempt to expose such under-the-hood practices, this paper explores the issue of browser cryptojacking, whereby miners are secretly deployed inside browser code without the knowledge of the user. To this end, we analyze the top 50k websites from Alexa and find a noticeable percentage of sites that are indulging in this exploitative exercise often using heavily obfuscated code. Furthermore, mining prevention plug-ins, such as NoMiner, fail to flag such cleverly concealed instances. Hence, we propose a machine learning solution based on hardware-assisted profiling of browser code in real-time. A fine-grained micro-architectural footprint allows us to classify mining applications with >99% accuracy and even flags them if the mining code has been heavily obfuscated or encrypted. We build our own browser extension and show that it outperforms other plug-ins. The proposed design has negligible overhead on the user's machine and works for all standard off-the-shelf CPUs.
【Keywords】: Browsers; Hardware; Cryptocurrency; Computer hacking; Data mining
【Paper Link】 【Pages】:712-720
【Authors】: Lailong Luo ; Deke Guo ; Ori Rottenstreich ; Richard T. B. Ma ; Xueshan Luo ; Bangbang Ren
【Abstract】: The emergence of large-scale dynamic sets in networking applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional k candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.
【Keywords】: Cuckoo filter; consistent hashing; elasticity
【Paper Link】 【Pages】:721-729
【Authors】: Amjad Yousef Majid ; Michel Jansen ; Guillermo Ortas Delgado ; Kasim Sinan Yildirim ; Przemyslaw Pawelczak
【Abstract】: We characterize the performance of a backscatter tag-to-tag (T2T) multi-hop network. For this, we developed a discrete component-based backscatter T2T transceiver and a communication protocol suite. The protocol composed of a novel (i) flooding-based link control tailored towards backscatter transmission, and (ii) low-power listening MAC. The MAC design is based on the new insight that backscatter reception is more energy costly than transmission. Our experiments show that multi-hopping extends the coverage of backscatter networks by enabling longer backward T2T links (tag far from the exciter sending to the tag close to the exciter). Four hops, for example, extend the communication range by a factor of two. Furthermore, we show that dead spots in multi-hop T2T networks are far less significant than those in the single-hop T2T networks.
【Keywords】: Backscatter; Spread spectrum communication; Transceivers; Protocols; Network topology; Topology; Receivers
【Paper Link】 【Pages】:730-738
【Authors】: Marcelo Pizzutti ; Alberto E. Schaeffer Filho
【Abstract】: Control plane programmability, primarily enabled by SDN/OpenFlow, has brought new impetus to already consolidated management and planning practices in the area of computer networks. However, applications that require high responsiveness and demand more dynamic mechanisms executing beyond the control plane can only be effectively exploited through interactions with the data plane, where decisions and reactive responses can be made at line rate. P4 achieves this goal by providing directives that allow a certain level of control over the hardware that performs packet forwarding tasks, bringing programmability to the data plane. In this paper, we present a multipath routing strategy that takes full advantage of a hybrid SDN/OpenFlow and P4 architecture. In the data plane, P4 and the Flowlet abstraction are used to actively perform load balancing and routing over multiple asymmetric paths, in addition to monitor active links. In the logically centralized control plane, the overall view of the network is leveraged to perform more elaborate passive tasks, which include mapping paths, configuring devices and updating routes asynchronously. Experimental evaluations are conducted in which we analyze different strategies for choosing the routes that provide the best results based on RTT values received from the switches.
【Keywords】: multipath; load balance; Flowlet; control plane; data plane; programmability; P4; hybrid architecture
【Paper Link】 【Pages】:739-747
【Authors】: Harsh Gupta ; Atilla Eryilmaz ; R. Srikant
【Abstract】: We consider the optimal link rate selection problem in time-varying wireless channels with unknown channel statistics. The aim of optimal link rate selection is to transmit at the optimal rate at each time slot in order to maximize the expected throughput of the wireless channel/link or equivalently minimize the expected regret. Lack of information about channel state or channel statistics necessitates the use of online/sequential learning algorithms to determine the optimal rate. We present an algorithm called CoTS - Constrained Thompson sampling algorithm which improves upon the current state-of-the-art, is fast and is also general in the sense that it can handle several different constraints in the problem with the same algorithm. We also prove an asymptotic lower bound on the expected regret and a high probability large-horizon upper bound on the regret, which show that the regret grows logarithmically with time in an order sense. We also provide numerical results which establish that CoTS significantly outperforms the current state-of-the-art algorithms.
【Keywords】: Constrained Thompson sampling; Optimal link rate selection; Regret minimization
【Paper Link】 【Pages】:748-756
【Authors】: Lixing Chen ; Jie Xu
【Abstract】: Vehicular Cloud Computing (VCC) is a new technological shift which exploits the computation and storage resources on vehicles for computational service provisioning. Spare onboard resources are pooled by a VCC operator, e.g. a roadside unit, to serve computational tasks using the vehicle-as-a-resource framework. This paper investigates timely service provisioning for deadline-constrained tasks in VCC systems by leveraging the task replication technique (i.e., allowing one task to be executed by vehicles). A learning-based algorithm, called DATEV (Deadline-Aware Task rEplication for Vehicular Cloud), is proposed to address the special issues in VCC systems including uncertainty of vehicle movements, volatile vehicle members, and large vehicle population. The proposed algorithm is developed based on a novel contextual-combinatorial multi-armed bandit learning framework. DATE-V is “ contextual ” because it utilizes side information (context) of vehicles and tasks to infer the completion probability of a task replication under random vehicle movements. DATE-V is “combinatorial” because it replicates the received task and sends task replications to multiple vehicles to guarantee the service timeliness. When learning with multi-armed bandit, DATE-V also addresses the practical concern of delayed feedbacks caused by the task transmission/computational delay in using VCC. We rigorously prove that our learning algorithm achieves a sublinear regret bound compared to an oracle algorithm that knows the exact completion probability of any task replications. Simulations are carried out based on real-world vehicle movement traces and the results show that DATE-V significantly outperforms benchmark solutions.
【Keywords】: Task analysis; Cloud computing; Uncertainty; Delays; Automobiles; Servers; Benchmark testing
【Paper Link】 【Pages】:757-765
【Authors】: Suining He ; Kang G. Shin
【Abstract】: To realize an efficient and flexible urban crowd-flow identification, we propose a new scheme called CFid by fusing fine-grained spatio-temporal smartphone signal features. Considering the abundance of ambient WiFi and geomagnetism, we design and validate several of their fine-grained features and similarity metrics to determine if two individuals belong to the same crowd-flow. We formalize a graph stream clustering problem, where co-flow user pairs are opportunistically identified and fed as a dynamic sequence of edges connecting each other. Given such a flexible form, a fast and accurate algorithm processes the edges and identifies the crowd-flows for further upper-level applications, including urban-flow monitoring and shopping-advertisement/recommendation. Using extensive data-driven analytics and 8-month experimental studies upon 50 users (over 2,500 walking traces at 7 different urban sites), we have validated the accuracy (usually >95%), efficiency (only <;5% extra energy-footprint on average than normal usage on mobiles) and flexibility of CFid in identifying large-scale crowd-flows.
【Keywords】: Image edge detection; Wireless fidelity; Feature extraction; Monitoring; Sensors; Geomagnetism; Legged locomotion
【Paper Link】 【Pages】:766-774
【Authors】: Daniel Yue Zhang ; Dong Wang
【Abstract】: With the advance of mobile computing, Internet of Things, and 5G networks, social sensing based edge computing (SSEC) systems have emerged as a new computation paradigm where people and their personally owned devices collect and process sensing measurements about the physical world at the edge of networks. In this paper, we focus on the task allocation problem in SSEC where rational edge devices are motivated by incentives to collectively accomplish the computation tasks in the system. Several unique challenges exist to solve this problem: (i) the edge devices often do not share the complete context information (e.g., CPU, memory usage) in the task allocation process due to privacy concerns; (ii) the edge devices are rational actors who may have competing objectives with the application; (iii) the application server and edge devices are usually owned by different entities, making the coordination in task allocation more challenging. This paper develops a novel integrated Top-Down and Bottom-Up (TDBU) task allocation framework to address these challenges. In particular, TDBU incorporates abottom-up game-theoretic model that allows the edge devices to specify their task preferences in a way that maximizes their payoffs. It also incorporates atop-down control model that ensures the performance of the applications using control theory. The TDBU was implemented on a real-world edge computing testbed that consists of heterogeneous devices (Jetson TX1, TK1 boards, Raspberry Pi3). We compared the performance of TDBU with state-of-the-art baselines through a real-world social sensing application. The results showed that our solution significantly outperformed the baselines in various application settings.
【Keywords】: Task analysis; Sensors; Resource management; Edge computing; Servers; Computational modeling; Real-time systems
【Paper Link】 【Pages】:775-783
【Authors】: Li Lu ; Jiadi Yu ; Yingying Chen ; Yanmin Zhu ; Xiangyu Xu ; Guangtao Xue ; Minglu Li
【Abstract】: This paper demonstrates the feasibility of a side-channel attack to infer keystrokes on touch screen leveraging an off-the-shelf smartphone. Although there exist some studies on keystroke eavesdropping attacks on touch screen, they are mainly direct eavesdropping attacks, i.e., require the device of victims compromised to provide side-channel information for the adversary, which are hardly launched in practical scenarios. In this work, we show the practicability of an indirect eavesdropping attack, KeyListener, which infers keystrokes on QWERTY keyboards of touch screen leveraging audio devices on a smartphone. We investigate the attenuation of acoustic signals, and find that a user's keystroke fingers can be localized through the attenuation of acoustic signals received by the microphones in the smartphone. We then utilize the attenuation of acoustic signals to localize each keystroke, and further analyze errors induced by ambient noises. To improve the accuracy of keystroke localization, KeyListener further tracks finger movements during inputs through phase change and Doppler effect to reduce errors of acoustic signal attenuation-based keystroke localization. In addition, a binary tree-based search approach is employed to infer keystrokes in a context-aware manner. The proposed keystroke eavesdropping attack is robust to various environments without the assistance of additional infrastructures. Extensive experiments demonstrate that the accuracy of keystroke inference in top-5 candidates can approach 90% with a top-5 error rate of around 6%, which is a strong indication of the possible user privacy leakage of inputs on QWERTY keyboard.
【Keywords】: Acoustics; Touch sensitive screens; Keyboards; Eavesdropping; Attenuation; Tracking; Microphones
【Paper Link】 【Pages】:784-792
【Authors】: Pranvera Kortoçi ; Liang Zheng ; Carlee Joe-Wong ; Mario Di Francesco ; Mung Chiang
【Abstract】: Urban environments are a particularly important application scenario for the Internet of Things (IoT). These environments are usually dense and dynamic; in contrast, IoT devices are resource-constrained, thus making reliable data collection and scalable coordination a challenge. This work leverages the fog networking paradigm to devise a multi-tier data offloading protocol suitable for diverse data-centric applications in urban IoT scenarios. Specifically, it takes advantage of heterogeneity in the network so that sensors can collaboratively offload data to each other or to mobile gateways. Second, it evaluates the performance of this offloading process through the amount of data successfully reported to the cloud. In detail, it provides an analytical characterization of data drop-off rates as a random process and derives a light-weight yet efficient method for collaborative data offloading. Finally, it shows that the proposed fog-based solution significantly decreases the data drop-off rate through both analysis and extensive trace-driven simulations based on human mobility data from real urban settings.
【Keywords】: Fog networking; collaborative offloading; data drop-off rate; Internet of Things
【Paper Link】 【Pages】:793-801
【Authors】: Jian-Jhih Kuo ; Sheng-Hao Chiang ; Shan-Hsiang Shen ; De-Nian Yang ; Wen-Tsuen Chen
【Abstract】: Traffic engineering (TE) and efficient network updating have been considered as separate problems in previous SDN research. Traffic engineering mostly focuses on static traffic and does not consider the rerouting overheads to support dynamic traffic. Efficient network updating assumes the new routing is provided by TE and focuses on minimizing only the rerouting overheads, and therefore, the improved new routing with bandwidth consumption similar to the new routing from TE but much lower rerouting overheads has not been explored. In this paper, we explore Multi-tree Low-overhead Multicast Rerouting (MLMR) to jointly solve both problems for SDN multicast. We prove that MLMR is NP-hard and design a new approximation algorithm, named Multicast Rerouting and Update Scheduling Algorithm (MRUSA). Equipped with the notions of deterioration indicator, motivator, and inhibitor, MRUSA provides incremental tree updating and multi-tree update scheduling to address the trade-off between the bandwidth consumption and rerouting overheads. Frequent rerouting due to tiny changes of multicast users can be effectively avoided, because rerouting time for each group can be correctly identified. Simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 35% compared with SPT and ST, and the computation time is small for massive SDN.
【Keywords】: Routing; Bandwidth; Unicast; Approximation algorithms; Multicast algorithms; Computer science; Control systems
【Paper Link】 【Pages】:802-810
【Authors】: Subhrendu Chattopadhyay ; Soumyajit Chatterjee ; Sukumar Nandi ; Sandip Chakraborty
【Abstract】: Management of networked Internet of Things (IoT) infrastructure with in-network processing capabilities is becoming increasingly difficult due to the volatility of the system with low-cost resource-constraint devices. Traditional software-defined networking (SDN) based management systems are not suitable to handle the plug and play nature of such systems. Therefore, in this paper, we propose Aloe, an elastically auto-scalable SDN orchestration framework. Instead of using service grade SDN controller applications, Aloe uses multiple lightweight controller instances to exploit the capabilities of in-network processing infrastructure. The proposed framework ensures the availability and significant reduction in flow-setup delay by deploying instances near the resource constraint IoT devices dynamically. Aloe supports fault-tolerance and can recover from network partitioning by employing self-stabilizing placement of migration capable controller instances. The performance of the proposed system is measured by using an in-house testbed along with a large scale deployment in Amazon web services (AWS) cloud platform. The experimental results from these two testbed show significant improvement in response time for standard IoT based services. This improvement of performance is due to the reduction in flow-setup time. We found that Aloe can improve flow-setup time by around 10%-30% in comparison to one of the state of the art orchestration framework.
【Keywords】: Network architecture; Fault-tolerance; Programmable network; software defined network
【Paper Link】 【Pages】:811-819
【Authors】: Gengbiao Shen ; Qing Li ; Shuo Ai ; Yong Jiang ; Mingwei Xu ; Xuya Jia
【Abstract】: Software-Defined Networking (SDN) provides a tractable and efficient architecture for operators to customize their network functions. Many traditional Data Center Networks (DCNs) are upgraded by SDN to improve link utilization and management flexibility, but they are lack of the instructions for selecting the substitutive SDN switches with the proper flow table space to achieve cost-effective and energy-saving networks. In this paper, we fill the gap of solving the flow table space estimation problem based on queuing theory. First, we divide the life process of a flow table entry into the packet-in process, the handling process and the serving process to establish a queuing system to estimate the least required number of the flow table entries of SDN switches. Second, we analyze the traffic distribution of DCNs to calculate the critical parameters in our model. Third, on the basis of the essence of the structured topologies in DCNs, we construct a probability model of routing strategies to quantize the influence of path selection. Comprehensive experiments show that the relative flow table space estimation error of our model can be less than 10%, which can give operators insights into the requirement of the SDN switches at specific positions.
【Keywords】: Routing; Process control; Queueing analysis; Analytical models; Estimation; Topology
【Paper Link】 【Pages】:820-828
【Authors】: Junjie Xie ; Chen Qian ; Deke Guo ; Minmei Wang ; Shouqian Shi ; Honghui Chen
【Abstract】: Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, these edge servers cache data to provide services for edge users. The data sharing among edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where the switches and the data indexes are associated with the coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying the data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve the data index compared to using Chord, a well-known DHT solution.
【Keywords】: Indexing; Servers; Edge computing; Peer-to-peer computing; Bandwidth; Control systems
【Paper Link】 【Pages】:829-837
【Authors】: Shengling Wang ; Chenyu Wang ; Qin Hu
【Abstract】: The great market success of Blockchain makes it an extremely valuable target for attackers. A well-known attack in Blockchain is the forking attack, where divergent blockchains are produced for inserting some new features to facilitate security breaches. The state-of-the-art works mostly focus on how to detect attacks in real-time transactions, which is in hindsight and cannot deter the forking attack from the root. To take precautions, we employ the large deviation theory to study the vulnerability of blockchain networks incurred by intentional forks from a micro point of view, boosting forward-looking and strategic planning mechanisms for resisting the forking attack. Our study is fine-grained, because it offers not only the vulnerability probability of a blockchain network but also its decay speed, through which we find setting the parameter related to the robust level has more power than enhancing the computer power in speeding up the failure of attacks. This finding is valuable since it renders an opportunity to improve the robustness of a blockchain network in a cost-efficient way. Our analysis is complementary, since it studies both the impacts of the computational power as well as the number of confirmations on the vulnerability of a blockchain network, providing a theoretical basis to design reasonable schemes for invigorating a blockchain network from technical as well as managerial levels. Extensive experiments carried out on a large-scale cloud platform running the Ethereum protocol show the experimental and analytical results match well, verifying the effectiveness of our analysis.
【Keywords】: Blockchain; Bitcoin; Peer-to-peer computing; Protocols; Robustness; Real-time systems
【Paper Link】 【Pages】:838-846
【Authors】: Hui Xia ; Fu Xiao ; Sanshun Zhang ; Chun-qiang Hu ; Xiuzhen Cheng
【Abstract】: The concept of social networking is integrated into Internet of things (IoT) to socialize smart objects by mimicking human behaviors, leading to a new paradigm of Social Internet of Things (SIoT). A crucial problem that needs to be solved is how to establish reliable relationships autonomously among objects, i.e., building trust. This paper focuses on exploring an efficient context-aware trustworthiness inference framework to address this issue. Based on the sociological and psychological principles of trust generation between human beings, the proposed framework divides trust into two types: familiarity trust and similarity trust. The familiarity trust can be calculated by direct trust and recommendation trust, while the similarity trust can be calculated based on external similarity trust and internal similarity trust. We subsequently present concrete methods for the calculation of different trust elements. In particular, we design a kernel-based nonlinear multivariate grey prediction model to predict the direct trust of a specific object, which acts as the core module of the entire framework. Besides, considering the fuzziness and uncertainty in the concept of trust, we introduce the fuzzy logic method to synthesize these trust elements. The experimental results verify the validity of the core module and the resistance to attacks of this framework.
【Keywords】: Social Internet of Things; trustworthiness inference framework; kernel-based nonlinear multivariate grey prediction; fuzzy logic method
【Paper Link】 【Pages】:847-855
【Authors】: Minmei Wang ; Chen Qian ; Xin Li ; Shouqian Shi
【Abstract】: Public-key certificate validation is an important building block for various security protocols for IoT devices, such as secure channel establishment, handshaking, verifying sensing data authenticity from cloud storage, and Blockchains. However, certification validation incurs non-trivial overhead on resource-constrained IoT devices, because it either requires long latency or large cache space. This work proposes to utilize the power of distributed caching and explores the feasibility of using the cache spaces on all IoT devices as a large pool to store validated certificates. We design a Collaborative Certificate Validation (CCV) protocol including a memory-efficient and fast locator for certificate holders, a trust model to evaluate the trustworthiness of devices, and a protocol suite for dynamic update and certificate revocation. Evaluation results show that CCV only uses less than 25% validation time and reduces >90% decryption operations on each device, compared to a recent method. Malicious devices that conduct dishonest validations can be detected by the network using the proposed trust model.
【Keywords】: Public key; Protocols; Collaboration; Sensors; Internet of Things; Cloud computing
【Paper Link】 【Pages】:856-864
【Authors】: Chi Lin ; Zhi Shang ; Wan Du ; Jiankang Ren ; Lei Wang ; Guowei Wu
【Abstract】: Wireless rechargeable sensor networks (WRSNs), benefiting from recent breakthrough in wireless power transfer (WPT) technology, emerge as very promising for network lifetime extension. Traditional methods focus on scheduling algorithms and system optimization, and the issue of charging security/threat is ignored, causing it vulnerable to attacks. In this paper, we develop a novel attack for WRSN through Denial of Charge (DoC) aiming at maximizing destructiveness. At first, we form a generalized on-demand charging model, which provides fundamental basis for designing charging attacks. Then a request prediction method (RPM) is introduced for predicting the emergences of charging requests. Afterwards, a Collaborative DoC attacking algorithm (CoDoC) is developed, which tempers/modifies and generates fake charging requests, yielding normal nodes exhausted. Finally, to demonstrate the outperformed features of CoDoC, extensive simulations and test-bed experiments are conducted. The results show that, CoDoC outperforms in making sensor exhausted as well as causing missing events.
【Keywords】: Scheduling algorithms; Wireless sensor networks; Security; Batteries; Optimization; Prediction methods; Collaboration
【Paper Link】 【Pages】:865-873
【Authors】: Chuyu Wang ; Lei Xie ; Keyan Zhang ; Wei Wang ; Yanling Bu ; Sanglu Lu
【Abstract】: Nowadays, the growing demand for the 3D human-computer interaction (HCI) has brought about a number of novel approaches, which achieve the HCI by tracking the motion of different devices, including the translation and the rotation. In this paper, we propose to use a spinning linearly polarized antenna to track the 3D motion of a specified object attached with the passive RFID tag array. Different from the fixed antenna-based solutions, which suffer from the unavoidable signal interferences at some specific positions/orientations, and only achieve the good performance in some feasible sensing conditions, our spinning antenna-based solution seeks to sufficiently suppress the ambient signal interferences and extracts the most distinctive features, by actively spinning the antenna to create the optimal sensing condition. Moreover, by leveraging the matching/mismatching property of the linearly polarized antenna, i.e., in comparison to the circularly polarized antenna, the phase variation around the matching direction is more stable, and the RSSI variation in the mismatching direction is more distinctive, we are able to find more distinctive features to estimate the position and the orientation. We build a model to investigate the RSSI and the phase variation of the RFID tag along with the spinning of the antenna, and further extend the model from a single RFID tag to an RFID tag array. Furthermore, we design corresponding solutions to extract the distinctive RSSI and phase values from the RF-signal variation. Our solution tracks the translation of the tag array based on the phase features, and the rotation of the tag array based on the RSSI variation. The experimental results show that our system can achieve an average error of 13. 6cm in the translation tracking, and an average error of 8.3° in the rotation tracking in the 3D space.
【Keywords】: Tracking; Spinning; Three-dimensional displays; Directive antennas; Antenna arrays; Feature extraction
【Paper Link】 【Pages】:874-882
【Authors】: Jia Liu ; Xingyu Chen ; Shigang Chen ; Xiulong Liu ; Yanyan Wang ; Lijun Chen
【Abstract】: Sleep monitoring plays an important role in many medical applications, including SIDS prevention, care of patients with pressure ulcers, and assistance to patients with sleep apnea, where studies have shown that autonomous and continuous monitoring of sleep postures provides useful information for lowering health risk. Existing systems are designed based on electrocardiogram, cameras and pressure sensors, which are expensive to deploy, intrusive to privacy, or uncomfortable to use. This paper presents TagSheet, the first sleep monitoring system based on passive RFID tags, which provides a convenient, non-intrusive, and comfortable way of monitoring the sleeping postures. It does not require attaching any tag directly to a patient's body. Tags are taped under a bed sheet. With a combination of hierarchical recognition, image processing and polynomial fitting, the proposed system identifies body postures based on the observed variation caused by the patient body to the backscattered signals from tags. The system does not require any personalized data training, making it plug-n-play in use. One additional advantage is that the system can also estimate the patient's respiration rate. This is particularly helpful in assisting patients with sleep apnea. We have implemented a prototype system, and experiments show that the system performs posture identification with an accuracy up to 96.7% and in the meantime it measures the respiration rate with a small error of about 0.7 bpm (breath per minute).
【Keywords】: Sleep apnea; Monitoring; Diversity reception; Cameras; Pressure sensors; Training; Pediatrics
【Paper Link】 【Pages】:883-891
【Authors】: Junchen Guo ; Ting Wang ; Yuan He ; Meng Jin ; Chengkun Jiang ; Yunhao Liu
【Abstract】: Liquid leakage detection is a crucial issue in modern industry, which concerns industrial safety. Traditional solutions, which generally rely on specialized sensors, suffer from intrusive deployment, high cost, and high power consumption. Such problems prohibit applying those solutions for large-scale and continuously industrial monitoring. In this work, we present a RFID-based solution, TwinLeak, to detect liquid leakage using COTS RFID devices. Detecting the leakage accurately with coarse-grained RSSI and phase readings of tags has been a daunting task, which is especially challenging when low detection delay is required. Our system achieves these goals based on the fact that the inductive coupling between two adjacent tags is highly sensitive to the liquid leaked between them. Therefore, instead of judging according to the signals of each individual tag, TwinLeak utilizes the relationship between the signals of two tags as an effective feature for leakage detection. Specifically, Twin-Leak extracts discriminative signal features from short segments of signals and instantly identifies leakage using a light-weight classifier. A model-guided method for leakage progress tracking is further devised to simultaneously estimate the leakage volume and rate. We implement TwinLeak, evaluate its performance across various scenarios, and deploy it in a real-world industrial IoT system. In average, TwinLeak achieves a TPR higher than 97.2%, a FPR lower than 0.5%, and a relative property estimation error around 10%, while triggering early alarms after only about 4.6mL liquid leaks.
【Keywords】: Liquids; Couplings; Feature extraction; Cotton; Radiofrequency identification; Humidity
【Paper Link】 【Pages】:892-900
【Authors】: Ping Li ; Zhenlin An ; Lei Yang ; Panlong Yang
【Abstract】: Conventional vibration sensing systems, equipped with specific sensors (e.g., accelerometer) and communication modules, are either expensive or cumbersome in deployment. In recent years, the community revisits this classic topic by taking advantage of off-the-shelf RFIDs. However, limited by lower reading rate and larger wavelength, current RFID based solutions can only sense low-frequency (e.g. below 100Hz) mechanical vibrations with larger amplitude (e.g. (>) 5mm). To address this issue, this work presents TagSound, an RFID-based vibration sensing system that explores a tag's harmonic backscattering to recover high-frequency and tiny mechanical vibrations accurately. The key innovations are in two aspects: harmonics based sensing and a new recovery scheme. We implement TagSound with USRP platforms. Our comprehensive evaluation shows TagSound can achieve a mean error of 0.37 Hz when detecting vibrations at frequencies below 100Hz, and a mean error of 4.2 Hz even when the vibration frequency is up to 2500Hz.
【Keywords】: Vibrations; Harmonic analysis; Backscatter; Radiofrequency identification; Time-domain analysis; Wireless sensor networks
【Paper Link】 【Pages】:901-909
【Authors】: Xu Wang ; Randall A. Berry
【Abstract】: LTE-U is an extension of the Long Term Evolution (LTE) standard for operation in unlicensed spectrum. LTE-U differs from WiFi, the predominant technology used in unlicensed spectrum in that it utilizes a duty cycle mode for accessing the spectrum and allows for a more seamless integration with LTE deployments in licensed spectrum. There have been a number of technical studies on the co-existence of LTE-U and WiFi in unlicensed spectrum In this paper, we instead investigate the impact of such a technology from an economic perspective. We consider a model in which an incumbent service provider (SP) deploys a duty cycle-based technology like LTE-U in an unlicensed band along with operating in a licensed band and competes with one or more entrants that only operate in the unlicensed band using a different technology like WiFi. We characterize the impact of a technology like LTE-U on the market outcome and show that the welfare impacts of this technology are subtle, depending in part on the amount of unlicensed spectrum and number of entrants. We also investigate the impact of the duty cycle and the portion of unlicensed spectrum used by the technology.
【Keywords】: Wireless fidelity; Bandwidth; Long Term Evolution; Monopoly; Numerical models
【Paper Link】 【Pages】:910-918
【Authors】: Fangxin Wang ; Cong Zhang ; Feng Wang ; Jiangchuan Liu ; Yifei Zhu ; Haitian Pang ; Lifeng Sun
【Abstract】: Recent years have seen booming development and great success in interactive crowdsourced livecast (i.e., crowdcast). Different from traditional livecast services, crowdcast is featured with tremendous video contents at the broadcaster side, highly diverse viewer side content watching environments/preferences as well as viewers' personalized quality of experience (QoE) demands (e.g., individual preferences for streaming delays, channel switching latencies and bitrates). This imposes unprecedented key challenges on how to flexibly and cost-effectively accommodate the heterogeneous and personalized QoE demands for the mass of viewers. In this paper, we propose DeepCast, an edge-assisted crowdcast framework, which makes intelligent decisions at edges based on the massive amount of real-time information from the network and viewers to accommodate personalized QoE with minimized system cost. Given the excessive computation complexity in this context, we propose a data-driven deep reinforcement learning (DRL) based solution that can automatically learn the best suitable strategies for viewer scheduling and transcoding selection. To our best knowledge, DeepCast is the first edge-assisted framework that applies the advance of DRL to explicitly accommodate personalized QoE optimization for crowdcast services. We collect multiple real-world datasets and evaluate the performance of DeepCast using trace-driven experiments. The results demonstrate the superiority of our DeepCast framework and its DRL-based solution.
【Keywords】: Quality of experience; Servers; Bit rate; Switches; Bandwidth; Delays; Transcoding
【Paper Link】 【Pages】:919-927
【Authors】: Meng Zhang ; Jianwei Huang
【Abstract】: Network utility maximization (NUM) is a general framework for optimally allocating constrained resources in many networked applications. When agents have asymmetric and private information, a fundamental economic challenge is how to solve the NUM Problem considering the self-interests of strategic agents. Many previous related works have proposed economic mechanisms that can cope with agents' private utilities. However, the related literature largely neglected the issue of information asymmetries regarding constraints, and limited closely related studies provided solutions only applicable to specific application scenarios. To tackle this issue, we propose the DeNUM Mechanism, the first mechanism for solving a general class of decomposable NUM Problems considering both private utility and constraint information. The key idea is to decentralize the decision process to agents, who will make resource allocation decisions without the need of revealing private information to others. We further show that the DeNUM mechanism yields the network-utility maximizing solution at an equilibrium, and achieves other desirable economic properties (such as individual rationality and budget balance). However, the corresponding equilibrium solution concept, the generalized Nash equilibrium (GNE), makes it difficult to achieve through a distributed algorithm. To address this issue, we further establish the connection between the structure of GNE and that of the primal-dual solution to a reformulated NUM problem, based on which we present the convergent DeNUM Algorithm that is provably convergent. Finally, as a case study, we apply the DeNUM Mechanism to solving the NUM problem for a user-provided network, and show that the DeNUM algorithm improves the network utility by 17% compared to a non-cooperation benchmark.
【Keywords】: Resource management; Distributed algorithms; Optimization; Economics; Throughput; Nash equilibrium; Bandwidth
【Paper Link】 【Pages】:928-936
【Authors】: Yunpeng Li ; Costas Courcoubetis ; Lingjie Duan
【Abstract】: Mobile social network applications constitute an important platform for traffic information sharing, helping users collect and share sensor information about the driving conditions they experience on the traveled path in real time. In this paper we analyse the simple but fundamental model of a platform choosing between two paths: one with known deterministic travel cost and the other that alternates over time between a low and a high random cost states, where the low and the high cost states are only partially observable and perform respectively better and worse on average than the fixed cost path. The more users are routed over the stochastic path, the better the platform can infer its actual state and use it efficiently.At the Nash equilibrium, if asked to take the riskier path, in many cases selfish users (that are allowed to have access to the information collected by the platform) will myopically disregard the optimal path suggestions of the platform, leading to a suboptimal system without enough exploration on the stochastic path. We prove the interesting result that if the past collected information is hidden from users, the system becomes incentive compatible and even `sophisticated' users (in the sense that they have full capability to reverse-engineer the platform's recommendation and derive the path state distribution conditional on the recommendation) prefer to follow the platform's recommendations. In a more practical setting where the platform implements a model-free Q-learning algorithm to minimise the social travel cost, our analysis suggests that increasing the accuracy of the learning algorithm increases the range of system parameters for which sophisticated users follow the recommendations of the platform, becoming in the limit fully incentive compatible. Finally, we extend the two-path model to include more stochastic paths, and show that incentive compatibility holds under our information restriction mechanism.
【Keywords】: Analytical models; Routing; Markov processes; Roads; Hazards; Information management
【Paper Link】 【Pages】:937-945
【Authors】: Yi Zhao ; Zimu Zhou ; Xu Wang ; Tongtong Liu ; Yunhao Liu ; Zheng Yang
【Abstract】: Understanding customer mobility patterns to commercial districts is crucial for urban planning, facility management, and business strategies. Trade areas are a widely applied measure to quantity where the visitors are from. Traditional trade area analysis is limited to small-scale or store-level studies because information such as visits to competitor commercial entities and place of residence is collected by labour-intensive questionnaires or heavily biased location-based social media data. In this paper, we propose CellTradeMap, a novel district-level trade area analysis framework using mobile flow records (MFRs), a type of fine-grained cellular network data. CellTradeMap extracts robust location information from the irregularly sampled, noisy MFRs, adapts the generic trade area analysis framework to incorporate cellular data, and enhances the original trade area model with cellular-based features. We evaluate CellTradeMap on a large-scale cellular network dataset covering 3.5 million mobile phone users in a metropolis in China. Experimental results show that the trade areas extracted by CellTradeMap are aligned with domain knowledge and CellTradeMap can model trade areas with a high predictive accuracy.
【Keywords】: Cellular networks; Base stations; Mobile handsets; Switches; Urban areas; Internet; Data mining
【Paper Link】 【Pages】:946-954
【Authors】: Ran He ; Jin Cao ; Lisa Zhang ; Denny Lee
【Abstract】: Inference on location data has generated a great amount of interest and there are two data sources. GPS location data from GPS-based endpoint devices have high precision, but suffer from intermittent availability, small coverage of users and extra demand on devices' battery. Telecom mobility data, on the other hand, have the complementary advantages of continuous availability and complete coverage but generally with coarse location accuracy. The focus of this paper is on the development of a location insight system for activity labeling and user segment inference, based only on Telecom mobility data enriched with point-of-interest (POI) data. Specifically, we estimate activity patterns based on Bayesian techniques while infer user segments via a tree-based classification algorithm. We test the performance of our inference system via simulated mobility data and investigate the impact of important factors such as granularity of data. We conclude that imprecise location data, enriched with other source of information, can be used for the development of new generation activity inference models.
【Keywords】: Google; Medical services; Labeling; Global Positioning System; Data models; Meters; Education
【Paper Link】 【Pages】:955-963
【Authors】: Mohammed Alasmar ; George Parisis ; Richard G. Clegg ; Nickolay Zakhleniuk
【Abstract】: Getting good statistical models of traffic on network links is a well-known, often-studied problem. A lot of attention has been given to correlation patterns and flow duration. The distribution of the amount of traffic per unit time is an equally important but less studied problem. We study a large number of traffic traces from many different networks including academic, commercial and residential networks using state-of-the-art statistical techniques. We show that the log-normal distribution is a better fit than the Gaussian distribution commonly claimed in the literature. We also investigate a second heavy-tailed distribution (the Weibull) and show that its performance is better than Gaussian but worse than log-normal. We examine anomalous traces which are a poor fit for all distributions tried and show that this is often due to traffic outages or links that hit maximum capacity.We demonstrate the utility of the log-normal distribution in two contexts: predicting the proportion of time traffic will exceed a given level (for service level agreement or link capacity estimation) and predicting 95th percentile pricing. We also show the log-normal distribution is a better predictor than Gaussian or Weibull distributions.
【Keywords】: Traffic modelling; network planning; bandwidth provisioning; traffic billing
【Paper Link】 【Pages】:964-972
【Authors】: Weili Chen ; Jun Wu ; Zibin Zheng ; Chuan Chen ; Yuren Zhou
【Abstract】: The cryptocurrency market is a very huge market without effective supervision. It is of great importance for investors and regulators to recognize whether there are market manipulation and its manipulation patterns. This paper proposes an approach to mine the transaction networks of exchanges for answering this question. By taking the leaked transaction history of Mt. Gox Bitcoin exchange as a sample, we first divide the accounts into three categories according to its characteristic and then construct the transaction history into three graphs. Many observations and findings are obtained via analyzing the constructed graphs. To evaluate the influence of the accounts' transaction behavior on the Bitcoin exchange price, the graphs are reconstructed into series and reshaped as matrices. By using singular value decomposition (SVD) on the matrices, we identify many base networks which have a great correlation with the price fluctuation. When further analyzing the most important accounts in the base networks, plenty of market manipulation patterns are found. According to these findings, we conclude that there was serious market manipulation in Mt. Gox exchange and the cryptocurrency market must strengthen the supervision.
【Keywords】: Bitcoin; Blockchian; Transaction network; Temporal network; Singular value decomposition
【Paper Link】 【Pages】:973-981
【Authors】: Kyoungjun Park ; Myungchul Kim
【Abstract】: Streaming services gradually support high-quality videos for the better user experience. However, streaming high-quality video on mobile devices consumes a considerable amount of energy. This paper presents the design and prototype of EVSO, which achieves power saving by applying adaptive frame rates to parts of videos with a little degradation of the user experience. EVSO utilizes a novel perceptual similarity measurement method based on human visual perception specialized for a video encoder. We also extend the media presentation description, in which the video content is selected based only on the network bandwidth, to allow for additional consideration of the user's battery status. EVSO's streaming server preprocesses the video into several processed videos according to the similarity intensity of each part of the video and then provides the client with the processed video suitable for the network bandwidth and the battery status of the client's mobile device. The EVSO system was implemented on the commonly used H.264/AVC encoder. We conduct various experiments and a user study with nine videos. Our experimental results show that EVSO effectively reduces the energy consumption when mobile devices uses streaming services by 22% on average and up to 27% while maintaining the quality of the user experience.
【Keywords】: Streaming media; Batteries; Servers; User experience; Mobile handsets; Brightness; Energy consumption
【Paper Link】 【Pages】:982-990
【Authors】: Xiaoda Jiang ; Hancheng Lu ; Chang Wen Chen ; Feng Wu
【Abstract】: Non-orthogonal multiple access (NOMA) has shown potential for scalable multicast of video data. However, one key drawback for NOMA-based video multicast is the limited number of layers allowed by the embedded successive interference cancellation algorithm, failing to meet satisfaction of heterogeneous receivers. We propose a novel receiver-driven superposed video multicast (Supcast) scheme by integrating Softcast, an analog-like transmission scheme, into the NOMA-based system to achieve high bandwidth efficiency as well as gradual decoding quality proportional to channel conditions at receivers. Although Softcast allows gradual performance by directly transmitting power-scaled transformation coefficients of frames, it suffers performance degradation due to discarding coefficients under insufficient bandwidth and its power allocation strategy cannot be directly applied in NOMA due to interference. In Supcast, coefficients are grouped into chunks, which are basic units for power allocation and superposition scheduling. By bisecting chunks into base-layer chunks and enhanced-layer chunks, the joint power allocation and chunk scheduling is formulated as a distortion minimization problem. A two-stage power allocation strategy and a near-optimal low-complexity algorithm for chunk scheduling based on the matching theory are proposed. Simulation results have shown the advantage of Supcast against Softcast as well as the reference scheme in NOMA under various practical scenarios.
【Keywords】: Non-orthogonal multiple access; Video multicast; Chunk scheduling; Heterogeneous receivers
【Paper Link】 【Pages】:991-999
【Authors】: Haitian Pang ; Cong Zhang ; Fangxin Wang ; Jiangchuan Liu ; Lifeng Sun
【Abstract】: Recently, the fusion of 360° video and multi-viewpoint video, called multi-viewpoint (MVP) 360° interactive video, has emerged and created much more immersive and interactive user experience, but calls for a low latency solution to request the high-definition contents. Such viewing-related features as head movement have been recently studied, but several key issues still need to be addressed. On the viewer side, it is not clear how to effectively integrate different types of viewing-related features. At the session level, questions such as how to optimize the video quality under dynamic networking conditions and how to build an end-to-end mapping between these features and the quality selection remain to be answered. The solutions to these questions are further complicated given the many practical challenges, e.g., incomplete feature extraction and inaccurate prediction.This paper presents an architecture, called iView, to address the aforementioned issues in an MVP 360° interactive video scenario. To fully understand the viewing-related features and provide a one-step solution, we advocate multimodal learning and deep reinforcement learning in the design. iView intelligently determines video quality and reduces the latency without pre-programmed models or assumptions. We have evaluated iView with multiple real-world video and network datasets. The results showed that our solution effectively utilizes the features of video frames, networking throughput, head movements, and viewpoint selections, achieving at least 27.2%, 15.4%, and 2.8% improvements on the three video datasets, respectively, compared with several state-of-the-art methods.
【Keywords】: Streaming media; Optimization; Quality of experience; Throughput; Reinforcement learning; Video recording; Quality assessment
【Paper Link】 【Pages】:1000-1008
【Authors】: Bastian Alt ; Trevor Ballard ; Ralf Steinmetz ; Heinz Koeppl ; Amr Rizk
【Abstract】: Recent advances in quality adaptation algorithms leave adaptive bitrate (ABR) streaming architectures at a cross-roads: When determining the sustainable video quality one may either rely on the information gathered at the client vantage point or on server and network assistance. The fundamental problem here is to determine how valuable either information is for the adaptation decision. This problem becomes particularly hard in future Internet settings such as Named Data Networking (NDN) where the notion of a network connection does not exist. In this paper, we provide a fresh view on ABR quality adaptation for QoE maximization, which we formalize as a decision problem under uncertainty, and for which we contribute a sparse Bayesian contextual bandit algorithm denoted CBA. This allows taking high-dimensional streaming context information, including client-measured variables and network assistance, to find online the most valuable information for the quality adaptation. Since sparse Bayesian estimation is computationally expensive, we develop a fast new inference scheme to support online video adaptation. We perform an extensive evaluation of our adaptation algorithm in the particularly challenging setting of NDN, where we use an emulation testbed to demonstrate the efficacy of CBA compared to state-of-the-art algorithms.
【Keywords】: Streaming media; Bit rate; Quality of experience; Video recording; Quality assessment; Computer architecture; Bayes methods
【Paper Link】 【Pages】:1009-1017
【Authors】: Fabien Geyer ; Steffen Bondorf
【Abstract】: Network calculus computes end-to-end delay bounds for individual data flows in networks of aggregate schedulers. It searches for the best model bounding resource contention between these flows at each scheduler. Analyzing networks, this leads to complex dependency structures and finding the tightest delay bounds becomes a resource intensive task. The exhaustive search for the best combination of contention models is known as Tandem Matching Analysis (TMA). The challenge TMA overcomes is that a contention model in one location of the network can have huge impact on one in another location. These locations can, however, be many analysis steps apart from each other. TMA can derive delay bounds with high degree of tightness but needs several hours of computations to do so. We avoid the effort of exhaustive search altogether by predicting the best contention models for each location in the network. For effective predictions, our main contribution in this paper is a novel framework combining graph-based deep learning and Network Calculus (NC) models. The framework learns from NC, predicts best NC models and feeds them back to NC. Deriving a first heuristic from this framework, called DeepTMA, we achieve provably valid bounds that are very competitive with TMA. We observe a maximum relative error below 6%, while execution times remain nearly constant and outperform TMA in moderately sized networks by several orders of magnitude.
【Keywords】: Servers; Computational modeling; Delays; Calculus; Analytical models; Predictive models; Aggregates
【Paper Link】 【Pages】:1018-1026
【Authors】: Kunyi Chen ; Hong Gao ; Zhipeng Cai ; Quan Chen ; Jianzhong Li
【Abstract】: Thanks to the recent advances in energy-harvesting devices, nodes equipped with such devices are produced and enable Wireless Sensor Networks (WSNs) to be energy self-sustainable. Such networks are named as Battery-Free WSNs (BF-WSNs). Data aggregation is an essential operation in WSNs, and the Minimum Latency Aggregation Scheduling (MLAS) problem which seeks a collision-free aggregation scheduling with the minimum latency has been well studied in Battery-Powered WSNs (BP-WSN). In BP-WSNs, latency is mainly caused by the time overhead in collision-avoiding. However, the time-consumption for node recharging is the main cause of latency in BF-WSNs. Moreover, the collisions are time-independent while the recharge rate is time-varying. Therefore, the previous algorithms are not suitable for BF-WSNs. In addition, if aggregating data from all nodes, the latency would be determined by the node with the lowest recharge rate. Thus, we propose to aggregate a subset of nodes which can meet the given coverage quality requirement. Meanwhile, the aggregation tree and scheduling strategy should be adaptive to the current energy condition. We formulate this problem and propose a distributed algorithm which can select nodes adaptively according to their energy condition and schedule these nodes to achieve the minimum latency, simultaneously. To the best of our knowledge, it is the first distributed algorithm to solve the MLAS problem with coverage guarantee in BF-WSNs. The simulation results verify that our algorithm can reduce aggregation latency effectively, especially in bad energy condition.
【Keywords】: Wireless sensor networks; Schedules; Monitoring; Energy consumption; Interference; Distributed algorithms; Data aggregation
【Paper Link】 【Pages】:1027-1035
【Authors】: Yifei Zou ; Dongxiao Yu ; Libing Wu ; Jiguo Yu ; Yu Wu ; Qiang-Sheng Hua ; Francis C. M. Lau
【Abstract】: This paper studies jamming-resilient distributed backbone construction in multi-hop wireless networks. Specifically, a strong adversarial jamming model is proposed that captures the general jamming phenomena suffered by wireless communications. The jamming model is based on the realistic Signal-to-Interference-plus-Noise-Ratio (SINR) interference model, and is featured by local-uniformity, unrestricted energy budget and reactivity, which covers more jamming scenarios and is much closer to reality than existing jamming models. Under the strong adversarial jamming model, we propose a randomized distributed algorithm that can construct a backbone in J(O(log n + logR)) rounds with high probability, where J(O(log n + log R)) is the number of rounds in the interval from the beginning of the algorithm execution that contains O(log n + log R) unjammed rounds for every node. This result is asymptotically optimal considering the trivial lower bound of Ω(log n) for a successful transmission even without interference and jamming.
【Keywords】: Jamming; Interference; Signal to noise ratio; Computer science; Protocols; Spread spectrum communication; Wireless communication
【Paper Link】 【Pages】:1036-1044
【Authors】: Boaz Patt-Shamir ; Will Rosenbaum
【Abstract】: We consider packet forwarding on a tree with all packets destined for the root, assuming each link may forward at most c ≥ 1 packets each time step. We use the Adversarial Queuing Theory injection model, where a (ρ, σ)-adversary may inject at most σ + ρ · t packets into the network at arbitrary locations during any time interval of length t. The goal is to find a forwarding protocol that minimizes the maximal buffer space required to avoid overflows against a (ρ, σ)-adversary with ρ ≤ c. We consider protocols from the locality viewpoint. A protocol is called d-local if the actions of a node depend only on the current state of nodes at distance at most d. A D-local protocol, where D is the network diameter, is called centralized. It is known that buffers of size Θ(σ + ρ) are necessary and sufficient for centralized protocols. The buffer requirement of O(1)-local protocols was recently proved to be Θ(ρ log D+σ). In this paper, for any d ≥ 2, we describe a d-local algorithm whose buffer space requirement is O (⌈log D/d⌉ ρ + σ). This result is tight, up d to constant factors. In particular, it implies that O(log D) locality is sufficient to achieve the best worst-case performance possible even for centralized algorithms. We also give evidence suggesting that the buffer requirement of a local algorithm designed for trees is good also when the routes do not constitute a single-destination tree.
【Keywords】: Clustering algorithms; Topology; Partitioning algorithms; Routing protocols; Routing; Queueing analysis
【Paper Link】 【Pages】:1045-1053
【Authors】: Wenqiang Jin ; Mingyan Xiao ; Ming Li ; Linke Guo
【Abstract】: Mobile crowd sensing (MCS) is a technique where sensing tasks are outsourced to a crowd of mobile users. Since most of sensing tasks are location-dependent, workers are required to embed their locations into sensing reports, which incurs location privacy vulnerabilities. Realizing that workers perceive their location privacy differently, in this work we construct an auction-based trading market, facilitating location privacy trading between workers and the platform. Each worker can decide how much location privacy to disclose to the platform based on its own location privacy leakage budget . The higher is, the less secrecy its reported location preserves. As a result, it receives higher payment from the platform as a compensation to its privacy loss. Besides, our mechanism enables the platform to select a suitable set of winning workers to achieve desirable service accuracy. For this purpose, a heuristic algorithm is devised, with polynomial-time complexity and bounded optimality gap. As formally proved in this manuscript, our proposed mechanism guarantees a series of nice properties, including -privacy, (α, 3)accuracy, and budget feasibility.
【Keywords】: Location privacy; mobile crowd sensing; privacy trading
【Paper Link】 【Pages】:1054-1062
【Authors】: Merkouris Karaliopoulos ; Iordanis Koutsopoulos ; Leonidas Spiliopoulos
【Abstract】: In mobile crowdsensing (MCS), users are repeatedly asked to make choices between a set of alternatives, i.e., whether to contribute to a task or not and which task to contribute to. The platform coordinating the MCS campaigns engineers these choices by selecting the tasks to present to each user and offering incentives to ensure user contributions and maximize the benefit from them. In this paper, we revisit the well-investigated question of how to optimize the contributions of crowds of mobile end users to MCS tasks. However, we depart from the bulk of related literature by explicitly accounting for the bounded rationality of human decision making. Bounded rationality is a consequence of cognitive and other kinds of constraints, (e.g., time pressure) and has been studied extensively in behavioral science.We model bounded rationality after two instances of lexicographic decision-making models that originate in the field of cognitive psychology: Fast-and-Frugal-Trees (FFTs) and Discrete Elimination by Aspects (DEBA). With each MCS task modeled as a vector of feature values, the decision process under both models proceeds through sequentially parsing lexicographically ordered features, resulting in choices that are satisfying, but not necessarily optimal. We study, in particular, scenarios where a single task or a pair of tasks are presented to MCS users together with reward offers that adhere to per-task budget constraints. We formulate the optimization problems that emerge for the MCS campaign organizers as instances of the Generalized Assignment Problem (GAP), an NP-hard problem for which approximate algorithms are available. Our evaluation suggests that our optimization approach exhibits significant gains when compared to heuristic rules that do not account for the lexicographic structure in human decision making.
【Keywords】: Mobile crowdsensing; incentive allocation; bounded rationality; task recommendation; decision trees; user choice engineering
【Paper Link】 【Pages】:1063-1071
【Authors】: Haiming Jin ; Hongpeng Guo ; Lu Su ; Klara Nahrstedt ; Xinbing Wang
【Abstract】: The recent proliferation of human-carried mobile devices has given rise to mobile crowd sensing (MCS) systems, where a myriad of data requesters outsource their sensing tasks to a crowd of workers via a cloud-based platform. In order to incentivize participation, requesters typically compensate workers with specific amount of payments. Clearly, setting an appropriate task price is critical for a requester to attract enough worker participation without unnecessary expenses. Therefore, we investigate the problem of task pricing in MCS systems with multi-requester price competition, and also dynamically arriving workers. Task pricing in such scenario is challenging, because of each requester's incomplete information about the others, uncertainty of future information, etc. So as to address these challenges, we use Markov game to model requesters' competitive task pricing, and Markov correlated equilibrium (MCE) as the solution concept. We propose that the platform uses the social cost-minimizing MCE to coordinate requesters' prices, which is self-enforcing, and optimizes the system-wide objective of social cost. Technically, we propose a computationally efficient algorithm to compute an approximately optimal MCE. Furthermore, through extensive performance evaluation, we show numerically that our algorithm yields close-to-minimum social cost in very short running time.
【Keywords】: Task analysis; Pricing; Sensors; Games; Markov processes; Vehicle dynamics; Nickel
【Paper Link】 【Pages】:1072-1080
【Authors】: Zai Shi ; Atilla Eryilmaz
【Abstract】: Distributed optimization has important applications in the practical implementation of machine learning and signal processing setup by providing means to allow interconnected network of processors to work towards the optimization of a global objective with intermittent communication. Existing works on distributed optimization predominantly assume all the processors storing related data to perform updates for the optimization task in each iteration. However, such optimization processes are typically executed at shared computing/data centers along with other concurrent tasks. Therefore, it is necessary to develop efficient distributed optimization methods that possess the flexibility to share the computing resources with other ongoing tasks. In this work, we propose a new first-order framework that allows for this flexibility through a probabilistic computing resource allocation strategy while guaranteeing the satisfactory performance of distributed optimization. Our results, both analytical and numerical, show that by controlling a flexibility parameter, our suite of algorithms (designed for various scenarios) can achieve the lower computation and communication costs of distributed optimization than their inflexible counterparts. This framework also enables the fair sharing of the common resources with other concurrent tasks being processed by the processing network.
【Keywords】: Program processors; Optimization; Task analysis; Convergence; Servers; Probabilistic logic; Signal processing algorithms
【Paper Link】 【Pages】:1081-1089
【Authors】: Geng Li ; Yang Richard Yang ; Franck Le ; Yeon-Sup Lim ; Junqi Wang
【Abstract】: The ability to support continuous network configuration updates is an important ability for enabling Software Defined Networks (SDN) to handle frequent or bursty changes. Current solutions for updating SDN configurations focus on one single update at a time, leading to slow, sequential (i.e., blocking) update execution. In this paper, we develop update algebra, a novel, systematic, theoretical framework based on abstract algebra, to enable continuous, non-blocking, fast composition of multiple updates. Specifically, by modeling each data-plane operation in the set of data-plane operations to be executed by an update as a set-theoretical projection, update algebra defines novel operation composition so that the number of projections for the same match remains constant regardless of the number of updates to be composed, leading to substantial performance benefits. Specifying the dependencies of the data-plane operations in updates as a subset of a free monoid in the general case and as partial ordering for basic consistency, update algebra defines update composition that preserves consistency, even under partially-executed updates, to guarantee correctness. We conduct asymptotic analysis, extensive benchmarking using a real controller, and integration with a real application to demonstrate the benefits of update algebra. In particular, our asymptotic analysis demonstrates that in independent-update dominant settings, update completion time of update algebra remains asymptotically constant despite growth of the number of updates to be executed. Our benchmarking shows that update algebra can achieve 16x reduction in update latency even in settings with an update arrival rate of only 1. 6/s. Our integration with Hedera, a real SDN traffic engineering application, shows that update algebra can reduce average link bandwidth utilization by 30% compared with sequential updates.
【Keywords】: Benchmark testing; Mathematical model; Abstract algebra; Pipeline processing; Software; Systematics
【Paper Link】 【Pages】:1090-1098
【Authors】: Franck Le ; Erich M. Nahum
【Abstract】: Live VM Migration allows a running virtual machine or service to be moved from one host to another without the need to be shut down. This critical process offers many benefits for Internet services, including load balancing and service availability especially during host maintenance. Nevertheless, VM migration has been limited to layer 2 environments where the VM's IP address can be migrated with the VM. This is because the IP address must remain reachable after the migration. This necessarily restricts the ability to migrate VMs, limiting their potential and utility.In this paper, we show how a new Internet standard, Multi-Path TCP, can be used to seamlessly migrate live VMs across WAN boundaries. This allows services to migrate closer to their clients while preserving active TCP connections, improving performance, responsiveness, and user engagement. We show this by designing and implementing LSM-MPTCP, a system for VM Migration over the WAN. We demonstrate how our approach can improve throughput and latency in a real cloud environment, achieving throughput improvements up to 6 times and reducing round-trip times by 99%. We also expose subtle networking issues related to migration that can heavily affect loss rates.
【Keywords】: Wide area networks; IP networks; Servers; Data centers; Routing; Throughput; Bandwidth
【Paper Link】 【Pages】:1099-1107
【Authors】: Konstantinos Poularakis ; Qiaofeng Qin ; Liang Ma ; Sastry Kompella ; Kin K. Leung ; Leandros Tassiulas
【Abstract】: Since the early development of Software-Defined Network (SDN) technology, researchers have been concerned with the idea of physical distribution of the control plane to address scalability and reliability challenges of centralized designs. However, having multiple controllers managing the network while maintaining a “logically-centralized” network view brings additional challenges. One such challenge is how to coordinate the management decisions made by the controllers which is usually achieved by disseminating synchronization messages in a peer-to-peer manner. While there exist many architectures and protocols to ensure synchronized network views and drive coordination among controllers, there is no systematic methodology for deciding the optimal frequency (or rate) of message dissemination. In this paper, we fill this gap by introducing the SDN synchronization problem: how often to synchronize the network views for each controller pair. We consider two different objectives; first, the maximization of the number of controller pairs that are synchronized, and second, the maximization of the performance of applications of interest which may be affected by the synchronization rate. Using techniques from knapsack optimization and learning theory, we derive algorithms with provable performance guarantees for each objective. Evaluation results demonstrate significant benefits over baseline schemes that synchronize all controller pairs at equal rate.
【Keywords】: Synchronization; Protocols; Routing; Control systems; Channel capacity; Topology; Load management
【Paper Link】 【Pages】:1108-1116
【Authors】: Hongli Xu ; Shigang Chen ; Qianpiao Ma ; Liusheng Huang
【Abstract】: Many important functions in software defined networks can benefit from fine-grained traffic measurement at flow level. Because TCAM-based flow entries only provide aggregate traffic statistics, prior research has suggested to perform flow-level measurement in SRAM and balance the measurement load across the network through collaborative traffic measurement. The key problem of collaborative measurement is to provide a mechanism to distribute flows to switches such that each switch can identify its subset of flows to measure. We observe that the prior work has focused on optimizing flow distribution among switches, but overlooked their high space and per-packet processing overhead introduced to the data plane, which becomes a serious issue in large SDN systems. In this paper, we propose a new lightweight solution to the flow distribution problem. It follows the design principle of alleviating complexity of the data plane by minimizing the data-plane space and processing overhead. At the control plane, we formulate flow distribution as optimization problems under two scenarios that implement collaborative measurement by edge switches only and by edge/core switches together, respectively. Our extensive simulations demonstrate that, comparing with the best existing work, the proposed lightweight solution achieves a comparable performance in terms of load balancing, while drastically reducing both space overhead and per-packet processing overhead, making it more practical in real-world systems that are sensitive to the additional overhead introduced by flow distribution.
【Keywords】: Flow Distribution; Collaborative Traffic Measurement; Software Defined Networks; Overhead
【Paper Link】 【Pages】:1117-1125
【Authors】: Irmak Aykin ; Berk Akgun ; Marwan Krunz
【Abstract】: Millimeter wave (mmW) communications have recently attracted considerable attention as a key element of next-generation (5G) wireless systems. Despite significant efforts in this domain, establishing and maintaining directional mmW links in a dynamic environment are still quite challenging, largely due to the search-time overhead of beam scanning, and the vulnerability of directional links to beam misalignment, blockage, and outages. In this paper, we propose SmartLink, a protocol that exploits the multi-cluster scattering phenomenon at mmW frequencies to establish a multi-directional link between a base station and a user. By exploiting multiple clusters, SmartLink enables fast initial access and link maintenance, along with sustained throughput. A search algorithm called multi-lobe beam search (MLBS) is used to discover multiple channel clusters by probing several directions simultaneously using carefully designed multilobe beam patterns. MLBS reduces the search time from linear to logarithmic with respect to the number of directions. We provide detailed analysis of the false alarm and misdetection probabilities for the designed beam patterns. Following cluster discovery, SmartLink divides antennas into sub-arrays to generate the optimal multi-lobe pattern with respect to cluster powers and blockage probabilities. Finally, extensive trace-driven simulations at 29 GHz frequency using phased-array antennas verify the efficiency of SmartLink.
【Keywords】: Millimeter wave; initial access; analog beam-forming; blockage; trace-driven simulations
【Paper Link】 【Pages】:1126-1134
【Authors】: Anfu Zhou ; Shaoyuan Yang ; Yi Yang ; Yuhang Fan ; Huadong Ma
【Abstract】: Ambient environment information, including reflectors' location, dimension and reflectivity, is a key input to many millimeter-wave (mmWave) networking and sensing applications. It has found versatile applications in optimizing network coverage and robustness, enhancing mobile link performance, and enabling high-accuracy indoor localization and navigation. Recent approaches of deriving mmWave environment information require heavy infrastructure support or non-trivial human labor, and rely on costly software defined radios, which prevent their usage in practice. In this work, we design and implement mmRanger, a system can automatically sense environment without any infrastructure support. mmRanger equips a pair of low-cost off-the-shelf mmWave radios in a commodity robot, which constantly samples the ambient environment by exchanging a series of mmWave signals while it moves and rotates. mmRanger then re-engineers the time-domain signal series to derive the spatial-domain environment structure, through novel reflection path extraction and reflector mapping algorithms. Our experiments verify that mmRanger can accurately sense a given environment with minimal overhead, and the learned information can bring 1.6× and 2.1× performance gain, in terms of network coverage and mobile link throughput, respectively, over empirical approaches in mmWave networks.
【Keywords】: Robot sensing systems; Geometry; Correlation; Laser beams; Phased arrays
【Paper Link】 【Pages】:1135-1143
【Authors】: William J. Tomlinson ; Stella Banou ; Christopher Yu ; Michele Nogueira ; Kaushik R. Chowdhury
【Abstract】: Increasing threats of malicious eavesdropping raise concerns in confidential data reporting by body-worn sensors. We propose a secure, body-guided transmission channel through the use of galvanic coupling (GC). This method involves injecting weak electrical current into the body, which propagates primarily through the skin. The proposed approach makes the transmission of biometric data impervious to sniffing attacks, enabling the body to serve as a waveguide. This paper makes the following contributions: (i) An analytical channel model using a tissue equivalent circuit of the human arm-wrist-palm GC-propagation path is formulated and empirically verified. (ii) A simulation study is conducted for a comparative analysis of various modulation schemes, leveraging the validated GC-channel behavior. (iii) A GC-transceiver with optimized communication parameters (modulation, frequency, power) is designed and implemented using a dielectrically equivalent tissue phantom, and (iv) through experimental trials, resilience to over-the-air susceptibility (i.e., likelihood of adversarial eavesdropping) of the GC-signal and similar body communication techniques are demonstrated. Performance results of the GC-transceiver prototype yield a bit error rate of 10 -6 with a transmit power of -2dBm, in addition to over 7x reduction of signal radiation outside the body compared to capacitive coupling.
【Keywords】: Couplings; Electrodes; Receivers; Skin; Integrated circuit modeling; Equivalent circuits; Wrist
【Paper Link】 【Pages】:1144-1152
【Authors】: Alireza Shahanaghi ; Yaling Yang ; R. Michael Buehrer
【Abstract】: Despite the advantages that ocean surface Wireless Sensor Networks (WSN) have over traditional ocean monitoring methods, ocean WSN research suffers from lack of an accurate model that describes the stability of wireless links among sensor nodes. In this paper, we are going to investigate ocean surface waves' effects on the Line-of-Sight (LoS) link between sensors in a homogeneous WSN. Specifically, we will derive the blockage probability of LoS links between a transmitter and receiver pair due to wave movements, and analyze how environmental effects like wind speed affect it. Simulation results along with oceanographic measurements validate our analyses, making our model applicable in design and planning of WSN in the ocean environment.
【Keywords】: Wireless Sensor Network; marine communications; Line-Of-Sight link stability; maximum wave-height; link stability
【Paper Link】 【Pages】:1153-1161
【Authors】: Fatemah Alharbi ; Jie Chang ; Yuchen Zhou ; Feng Qian ; Zhiyun Qian ; Nael B. Abu-Ghazaleh
【Abstract】: DNS poisoning attacks inject malicious entries into the DNS resolution system, allowing an attacker to redirect clients to malicious servers. These attacks typically target a DNS resolver allowing attackers to poison a DNS entry for all machines that use the compromised resolver. However, recent defenses can effectively protect resolvers rendering classical DNS poisoning attacks ineffective. In this paper, we present a new class of DNS poisoning attacks targeting the client-side DNS cache. The attack initiates DNS poisoning on the client cache, which is used in all main stream operating systems to improve DNS performance, circumventing defenses targeting resolvers. Our attack allows an off-path attacker to collaborate with a piece of an unprivileged malware to poison the OS-wide DNS cache on a client machine. We developed the attack on Windows, Mac OS, and Ubuntu Linux. Interestingly, the behaviors of the three operating systems are distinct and the vulnerabilities require different strategies to exploit. We also generalize the attack to work even when the client is behind a Network Address Translation (NAT) router. Our results show that we can reliably inject malicious DNS mappings, with on average, an order of tens of seconds. Finally, we propose a defense against this type of poisoning attacks.
【Keywords】: Computer crime; Microsoft Windows; Servers; Toxicology; Malware; IP networks
【Paper Link】 【Pages】:1162-1170
【Authors】: Xiaoli Zhang ; Huayi Duan ; Cong Wang ; Qi Li ; Jianping Wu
【Abstract】: In-the-cloud middleboxes have drawn widespread attentions recently, along with the rapid advancement of network function virtualization (NFV). Despite the well known benefits like reduced hardware and maintenance cost, deploying middleboxes in the remote environment poses new performance and security concerns, due to invisibility of the untrusted cloud and susceptible software implementations. One essential requirement for enterprise customers is to monitor performance compliance, while ensuring that packets are faithfully processed by remote middleboxes. In this paper, we propose a practical scheme towards verifiable performance measurement over in-the-cloud middleboxes. It employs “sample and replay” to achieve performance measurement and packet processing attestation. It estimates performance by collecting receipts in a tunable way, while coping with dynamic traffic changes made by middleboxes. In particular, our sampling is stateful which can capture a sequence of packets sharing same states of middleboxes for correct local replay. More importantly, it ensures high-confidence packet processing attestation by enforcing middleboxes to bind execution assurances with packets using commitment messages, and by using delayed verification procedure to defeat any potential biased results against selected sampling. To demonstrate the feasibility and efficiency of our scheme, we implement a prototype consisting of various types of middleboxes on Click, and conduct extensive experiments on Amazon EC2 with real traces. The experimental results show that our scheme imposes marginal processing delay for packets with various middleboxes and presents negligible throughput degradation.
【Keywords】: Middleboxes; Cloud computing; Delays; Network function virtualization; Security; Software
【Paper Link】 【Pages】:1171-1179
【Authors】: Chang Liu ; Longtao He ; Gang Xiong ; Zigang Cao ; Zhen Li
【Abstract】: With more attention paid to user privacy and communication security, the volume of encrypted traffic rises sharply, which brings a huge challenge to traditional rule-based traffic classification methods. Combining machine learning algorithms and manual-design features has become the mainstream methods to solve this problem. However, these features depend on professional experience heavily, which needs lots of human effort. And these methods divide the encrypted traffic classification problem into piece-wise sub-problems, which could not guarantee the optimal solution. In this paper, we apply the recurrent neural network to the encrypted traffic classification problem and propose the Flow Sequence Network (FS-Net). The FS-Net is an end-to-end classification model that learns representative features from the raw flows, and then classifies them in a unified framework. Moreover, we adopt a multi-layer encoder-decoder structure which can mine the potential sequential characteristics of flows deeply, and import the reconstruction mechanism which can enhance the effectiveness of features. Our comprehensive experiments on the real-world dataset covering 18 applications indicate that FS-Net achieves an excellent performance (99.14% TPR, 0.05% FPR and 0.9906 FTF) and outperforms the state-of-the-art methods.
【Keywords】: Cryptography; Logic gates; Hidden Markov models; Decoding; Payloads; Computer architecture; Recurrent neural networks
【Paper Link】 【Pages】:1180-1188
【Authors】: Zhen Ling ; Junzhou Luo ; Danni Xu ; Ming Yang ; Xinwen Fu
【Abstract】: Diverse anonymous communication systems are widely deployed as they can provide the online privacy protection and Internet anti-censorship service. However, these systems are severely abused and a large amount of anonymous traffic is malicious. To mitigate this issue, we propose a novel and practical traceback technique to confirm the communication relationship between the suspicious server and the user. We leverage the software-defined network (SDN) switch at a destination server side to intercept target traffic towards the server and alter the advertised TCP window sizes so as to stealthily vary the traffic rate at the server. By carefully varying the traffic rate, we can successfully modulate a secret signal into the traffic. The traffic carrying the signal passes through the anonymous communication system and reaches the SDN switch at the user side. Then we can detect the modulated signal from the traffic so as to confirm the communication relationship between the server and the user. To validate the feasibility and effectiveness of our technique, extensive real-world experiments are performed using three popular anonymous communication systems, i.e., SSH tunnel, OpenVPN tunnel, and Tor. The results demonstrate that the detection rates approach 100% for SSH and Open VPN and 95% for Tor while the false positive rates are significantly low, approaching 0% for these three systems.
【Keywords】: Anonymous communication systems; traceback technique; software-defined network
【Paper Link】 【Pages】:1189-1197
【Authors】: Erqun Dong ; Jingao Xu ; Chenshu Wu ; Yunhao Liu ; Zheng Yang
【Abstract】: Existing indoor navigation solutions usually require pre-deployed comprehensive location services with precise indoor maps and, more importantly, all rely on dedicatedly installed or existed infrastructure. In this paper, we present Pair-Navi, an infrastructure-free indoor navigation system that circumvents all these requirements by reusing a previous traveler's (i.e. leader) trace experience to navigate future users (i.e. followers) in a Peer-to-Peer (P2P) mode. Our system leverages the advances of visual SLAM on commercial smartphones. Visual SLAM systems, however, are vulnerable to environmental dynamics in the precision and robustness and involve intensive computation that prohibits real-time applications. To combat environmental changes, we propose to cull non-rigid contexts and keep only the static and rigid contents in use. To enable real-time navigation on mobiles, we decouple and reorganize the highly coupled SLAM modules for leaders and followers. We implement Pair-Navi on commodity smartphones and validate its performance in three diverse buildings. Our results show that Pair-Navi achieves an immediate navigation success rate of 98.6%, which maintains as 83.4% even after two weeks since the leaders' traces were collected, outperforming the state-of-the-art solutions by >50%. Being truly infrastructure-free, Pair-Navi sheds lights on practical indoor navigations for mobile users.
【Keywords】: Navigation; Simultaneous localization and mapping; Visualization; Trajectory; Real-time systems; Cameras; Smart phones
【Paper Link】 【Pages】:1198-1206
【Authors】: Weijun Wang ; Haipeng Dai ; Chao Dong ; Xiao Cheng ; Xiaoyu Wang ; Guihai Chen ; Wanchun Dou
【Abstract】: This paper considers the fundamental problem of Placement of unmanned Aerial vehicles achieviNg 3D Directional cover Age (PANDA), that is, given a set of objects with determined positions and orientations in a 3D space, deploy a fixed number of UAVs by adjusting their positions and orientations such that the overall directional coverage utility for all objects is maximized. First, we establish the 3D directional coverage model for both cameras and objects. Then, we propose a Dominating Coverage Set (DCS) extraction method to reduce the infinite solution space of PANDA to a limited one without performance loss. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint, and present a greedy algorithm with 1 -1 /e approximation ratio to address this problem. We conduct simulations and field experiments to evaluate the proposed algorithm, and the results show that our algorithm outperforms comparison ones by at least 75.4%.
【Keywords】: Cameras; Three-dimensional displays; Solid modeling; Monitoring; Mathematical model; Two dimensional displays; Unmanned aerial vehicles
【Paper Link】 【Pages】:1207-1215
【Authors】: Yuzhe Yang ; Zhiwen Hu ; Kaigui Bian ; Lingyang Song
【Abstract】: Given the increasingly serious air pollution problem, air quality index (AQI) monitoring in urban areas has drawn considerable attention. This paper presents ImgSensingNet, a vision guided aerial-ground sensing system, for air quality monitoring and forecasting by the fusion of haze images taken by the unmanned-aerial-vehicle (UAV) and the AQI data collected by an on-ground wireless sensor network. Specifically, ImgSensingNet first leverages the computer vision technique to tell the AQI scale in different regions from the haze images, where haze-relevant features and a deep convolutional neural network (CNN) are designed for direct learning between haze images and corresponding AQI scale. Based on the learnt AQI scale, ImgSensingNet determines whether to wake up on-ground wireless sensors for small-scale AQI monitoring and inference, which can greatly reduce the energy consumption of the system. An entropy-based model is employed for accurate real-time AQI estimation at un-measured locations and future air quality distribution forecasting. We implement and evaluate ImgSensingNet on two university campuses since Feb. 2018, and has collected 17,630 photos and 2.6 millions of AQI data samples. Experimental results confirm that ImgSensingNet can achieve high estimation accuracy while greatly reduce the battery consumption, compared to other state-of-the-art AQI monitoring approaches.
【Keywords】: Sensors; Monitoring; Wireless sensor networks; Image color analysis; Feature extraction; Air pollution
【Paper Link】 【Pages】:1216-1224
【Authors】: Binyao Jiang ; Yisheng Ji ; Xiaohua Tian ; Xinbing Wang
【Abstract】: This paper presents BatchQR, a mobile APP that can batch read the densely arranged QR codes attached to caps of the tubes and vials in clinical and biological labs. The basic idea of BatchQR is to detect each code in the image and then decode in an one-by-one manner. However, the unique characteristics of the QR code and the application scenario bring technical challenges: First, off-the-shelf lightweight object detection mechanisms are unable to distinguish those densely arranged codes that are highly similar to each other; second, the focus area of the camera is limited, which blurs or distorts parts of the image. To this end, we propose a lightweight code detection mechanism, which can adaptively adjust operating parameters to identify densely arranged QR codes in practice. We also propose a simple but effective image refocus mechanism, which takes an auto-focused image and multiple refocused ones, and then replaces the blurred or distorted code parts with the high-quality counterparts in the refocused images. Comprehensive experimental results show that BatchQR can read 160-180 Version 1-L QR codes in batch with 90%-95% accuracy in 10-14s, which is only 4% of the time consumed by the regular QR code reader in the same situation.
【Keywords】: Electron tubes; Containers; Object detection; Image color analysis; Biological information theory; Cameras; Standards
【Paper Link】 【Pages】:1225-1233
【Authors】: Yadong Xie ; Fan Li ; Yue Wu ; Song Yang ; Yu Wang
【Abstract】: Since the number of cars has grown rapidly in recent years, driving safety draws more and more public attention. Drowsy driving is one of the biggest threatens to driving safety. Therefore, a simple but robust system that can detect drowsy driving with commercial off-the-shelf devices (such as smart-phones) is very necessary. With this motivation, we explore the feasibility of purely using acoustic sensors embedded in smart-phones to detect drowsy driving. We first study characteristics of drowsy driving, and find some unique patterns of Doppler shift caused by three typical drowsy behaviors, i.e., nodding, yawning and operating steering wheel. We then validate our important findings through empirical analysis of the driving data collected from real driving environments. We further propose a real-time Drowsy Driving Detection system (D 3 -Guard) based on audio devices embedded in smartphones. In order to improve the performance of our system, we adopt an effective feature extraction method based on undersampling technique and FFT, and carefully design a high-accuracy detector based on LSTM networks for the early detection of drowsy driving. Through extensive experiments with 5 volunteer drivers in real driving environments, our system can distinguish drowsy driving actions with an average total accuracy of 93.31% in real-time. Over 80% drowsy driving actions can be detected within first 70% of action duration.
【Keywords】: Smart phones; Vehicles; Wheels; Doppler shift; Feature extraction; Sensors; Cameras
【Paper Link】 【Pages】:1234-1242
【Authors】: Chengwen Luo ; Xingyu Feng ; Junliang Chen ; Jianqiang Li ; Weitao Xu ; Wei Li ; Li Zhang ; Zahir Tari ; Albert Y. Zomaya
【Abstract】: Oral health has significant impact on people's over-all well-being. While many activity recognition systems exist in the literature, accurately sensing toothbrushing activities remains an unsolved challenging problem due to the diversity of tooth-brushing habits among different users and subtle distinctions between different brushing actions. In this work, we propose Hygiea, an energy-efficient and highly-accurate toothbrushing monitoring system which exploits IMU-based wrist-worn gesture sensing using unmodified toothbrushes. To address toothbrushing variety, Hygiea incorporates a number of novel signal preprocessing techniques to automatically transform the sensory input during arbitrary toothbrushing activities to the consistent user coordinate system. To distinguish different brushing actions, Hygiea leverages an emerging deep learning model (e.g., AT-LSTM) to achieve fine-grained activity recognitions. Moreover, a POMDP model is incorporated for sampling control to balance activity detection and energy efficiency. Extensive real-world experiments show that the Hygiea system achieves a 11.7% accuracy gain compared to the state-of-the-art while maintaining energy-efficiency and zero modification on the toothbrushes.
【Keywords】: Toothbrushing Monitoring; Wrist-worn Gesture Sensing; AT-LSTM; POMDP
【Paper Link】 【Pages】:1243-1251
【Authors】: Shuochao Yao ; Yiran Zhao ; Huajie Shao ; Dongxin Liu ; Shengzhong Liu ; Yifan Hao ; Ailing Piao ; Shaohan Hu ; Su Lu ; Tarek F. Abdelzaher
【Abstract】: Deep neural networks are becoming increasingly popular in Internet of Things (IoT) applications. Their capabilities of fusing multiple sensor inputs and extracting temporal relationships can enhance intelligence in a wide range of applications. However, one key problem is the missing of adaptation to heterogeneous on-device sensors. These low-end sensors on IoT devices possess different accuracies, granularities, and amounts of information, whose sensing qualities are heterogeneous and vary over time. The existing deep learning frameworks for IoT applications usually treat every sensor input equally over time or increase model capacity in an ad-hoc manner, lacking the ability to identify and exploit the sensor heterogeneities. In this work, we propose SADeepSense, a deep learning framework that can automatically balance the contributions of multiple sensor inputs over time by exploiting their sensing qualities. SADeepSense makes two key contributions. First, SADeepSense employs the self-attention mechanism to learn the correlations among different sensors over time with no additional supervision. The correlations are then applied to infer the sensing qualities and to reassign model concentrations in multiple sensors over time. Second, instead of directly learning the sensing qualities and contributions, SADeepSense generates the residual concentrations that are deviated from the equal contributions, which helps to stabilize the training process. We demonstrate the effectiveness of SADeepSense with two representative IoT sensing tasks: heterogeneous human activity recognition with motion sensors and gesture recognition with the wireless signal. SADeepSense consistently outperforms the state-of-the-art methods by a clear margin. In addition, we show that SADeepSense only imposes little additional resource-consumption burden on embedded devices compared to the corresponding state-of-the-art framework.
【Keywords】: Sensors; Internet of Things; Correlation; Neural networks; Deep learning; Task analysis; Heating systems
【Paper Link】 【Pages】:1252-1260
【Authors】: Yuanxing Zhang ; Pengyu Zhao ; Kaigui Bian ; Yunxin Liu ; Lingyang Song ; Xiaoming Li
【Abstract】: 360-degree videos have gained more popularity in recent years, owing to the great advance of panoramic cameras and head-mounted devices. However, as 360-degree videos are usually in high resolution, transmitting the content requires extremely high bandwidth. To protect the Quality of Experience (QoE) of users, researchers have proposed tile-based 360-degree video streaming systems that allocate high/low bit rates to selected tiles of video frames for streaming over the limited bandwidth. It is challenging to determine which tiles should be allocated with a high/low rate, because (1) the video playbacks include too many features that dynamically change over time when making the rate allocation; (2) most of the state-of-the-art systems focus on a fixed set of heuristics to optimize a specific QoE objective, while users may have various QoE objectives that need to be optimized in different ways. This paper presents a Deep Reinforcement Learning (DRL) based framework for 360-degree video streaming, named DRL360. The DRL360 framework helps improve the system performance by jointly optimizing multiple QoE objectives across a broad set of dynamic features. The DRL-based model adaptively allocates rates for the tiles of the future video frames based on the observations collected by client video players. We compare the proposed DRL360 to the existing systems by trace-driven evaluations as well as conducting a realworld experiment over a wide variety of network conditions. Evaluation results reveal that DRL360 can adapt to all considered scenarios, and outperform the state-of-the-art approaches by 20%-30% on average given different QoE objectives.
【Keywords】: Virtual reality; deep reinforcement learning; video streaming; quality of experience
【Paper Link】 【Pages】:1261-1269
【Authors】: Shaoqi Wang ; Wei Chen ; Xiaobo Zhou ; Sang-Yoon Chang ; Mike Ji
【Abstract】: Computational skewness is a significant challenge in multi-tenant data-parallel clusters that introduce dynamic heterogeneity of machine capacity in distributed data processing. Previous efforts to addressing skewness mostly focus on batch jobs based on the assumption that processing time is linearly dependent on the size of partitioned data. However, they are illsuited for iterative machine learning (ML) jobs, which (1) exhibit a non-linear relationship between the size of partitioned parameters and processing time within each iteration, and (2) show an explicit binding relationship between input data and parameters for parameter update. In this paper, we present FlexPara, a parameter partition approach that leverages the non-linear relationship and provisions adaptive tasks to match the distinct machine capacity so as to address the skewness in iterative ML jobs on data-parallel clusters. FlexPara first predicts task processing time based on a capacity model designed for iterative ML jobs without the linear assumption. It then partitions parameters to parallel tasks through proactive parameter reassignment. Such reassignment can significantly reduce network transmission cost incurred by input data movement due to the binding relationship. We implement FlexPara in Spark and evaluate it with various ML jobs. Experimental results show that compared to hash partition, FlexPara speeds up the execution by up to 54% and 43% in private and NSF Chameleon clusters, respectively.
【Keywords】: Task analysis; Sparks; Adaptation models; Predictive models; Computational modeling; Iterative methods; Data processing
【Paper Link】 【Pages】:1270-1278
【Authors】: Wuyang Zhang ; Sugang Li ; Luyang Liu ; Zhenhua Jia ; Yanyong Zhang ; Dipankar Raychaudhuri
【Abstract】: Running computer vision algorithms on images or videos collected by mobile devices represent a new class of latency-sensitive applications that expect to benefit from edge cloud computing. These applications often demand real-time responses (e.g., <;100 ms), which can not be satisfied by traditional cloud computing. However, the edge cloud architecture is inherently distributed and heterogeneous, requiring new approaches to resource allocation and orchestration. This paper presents the design and evaluation of a latency-aware edge computing platform, aiming to minimize the end-to-end latency for edge applications. The proposed platform is built on Apache Storm, and consists of multiple edge servers with heterogeneous computation (including both GPUs and CPUs) and networking resources. Central to our platform is an orchestration framework that breaks down an edge application into Storm tasks as defined by a directed acyclic graph (DAG) and then maps these tasks onto heterogeneous edge servers for efficient execution. An experimental proof-of-concept testbed is used to demonstrate that the proposed platform can indeed achieve low end-to-end latency: considering a real-time 3D scene reconstruction application, it is shown that the testbed can support up to 30 concurrent streams with an average perframe latency of 32ms, and can achieve 40% latency reduction relative to the baseline Storm scheduling approach.
【Keywords】: Cloud computing; Task analysis; Storms; Real-time systems; Topology; Image edge detection; Three-dimensional displays
【Paper Link】 【Pages】:1279-1287
【Authors】: Vajiheh Farhadi ; Fidan Mehmeti ; Ting He ; Tom La Porta ; Hana Khamfroush ; Shiqiang Wang ; Kevin S. Chan
【Abstract】: Mobile edge computing allows wireless users to exploit the power of cloud computing without the large communication delay. To serve data-intensive applications (e.g., augmented reality, video analytics) from the edge, we need, in addition to CPU cycles and memory for computation, storage resource for storing server data and network bandwidth for receiving user-provided data. Moreover, the data placement needs to be adapted over time to serve time-varying demands, while considering system stability and operation cost. We address this problem by proposing a two-time-scale framework that jointly optimizes service (data & code) placement and request scheduling, under storage, communication, computation, and budget constraints. We fully characterize the complexity of our problem by analyzing the hardness of various cases. By casting our problem as a set function optimization, we develop a polynomial-time algorithm that achieves a constant-factor approximation under certain conditions. Extensive synthetic and trace-driven simulations show that the proposed algorithm achieves 90% of the optimal performance.
【Keywords】: Mobile edge computing; service placement; resource allocation; complexity analysis
【Paper Link】 【Pages】:1288-1296
【Authors】: Hao Wang ; Di Niu ; Baochun Li
【Abstract】: The need to scale up machine learning, in the presence of a rapid growth of data both in volume and in variety, has sparked broad interests to develop distributed machine learning systems, typically based on parameter servers. However, since these systems are based on a dedicated cluster of physical or virtual machines, they have posed non-trivial cluster management overhead to machine learning practitioners and data scientists. In addition, there exists an inherent mismatch between the dynamically varying resource demands during a model training job and the inflexible resource provisioning model of current cluster-based systems. In this paper, we propose SIREN, an asynchronous distributed machine learning framework based on the emerging serverless architecture, with which stateless functions can be executed in the cloud without the complexity of building and maintaining virtual machine infrastructures. With SIREN, we are able to achieve a higher level of parallelism and elasticity by using a swarm of stateless functions, each working on a different batch of data, while greatly reducing system configuration overhead. Furthermore, we propose a scheduler based on Deep Reinforcement Learning to dynamically control the number and memory size of the stateless functions that should be used in each training epoch. The scheduler learns from the training process itself, in pursuit for the minimum possible training time given a cost. With our real-world prototype implementation on AWS Lambda, extensive experimental results have shown that SIREN can reduce model training time by up to 44%, as compared to traditional machine learning training benchmarks on AWS EC2 at the same cost.
【Keywords】: Training; Servers; Computer architecture; Machine learning; Computational modeling; Cloud computing; Data models
【Paper Link】 【Pages】:1297-1305
【Authors】: Yanbing Yang ; Jun Luo ; Chen Chen ; Wen-De Zhong ; Liangyin Chen
【Abstract】: Visible Light Communication (VLC) systems relying on commercial-off-the-shelf (COTS) devices have gathered momentum recently, due to the pervasive adoption of LED lighting and mobile devices. However, the achievable throughput by such practical systems is still several orders below those claimed by controlled experiments with specialized devices. In this paper, we engineer SynLight aiming to significantly improve the data rate of a practical VLC system. SynLight adopts COTS LEDs as its transmitter, but it innovates in its simple yet delicate driver circuit wiring an array of LED chips in a combinatorial manner. Consequently, modulated signals can directly drive the on-off procedures of individual chip groups, so that the spatially synthesized light emissions exhibit a varying luminance following exactly the modulation symbols. To obtain a readily usable receiver, SynLight interfaces a COTS Photo-Diode with a smartphone through the audio jack. The evaluations on SynLight are both promising and informative: they demonstrate a throughput up to 60 kbps, more than 50× of that achieved by state-of-the-art systems, while suggesting various potentials to further enhance the performance.
【Keywords】: Light emitting diodes; Receivers; Modulation; Transmitters; Throughput; Lifting equipment; Transistors
【Paper Link】 【Pages】:1306-1314
【Authors】: Zeyu Wang ; Zhice Yang ; Qianyi Huang ; Lin Yang ; Qian Zhang
【Abstract】: Visible light positioning (VLP) is a promising direction for indoor localization. VLP depends on Visible light communication (VLC) to receive location anchors sent by light bulbs. In order to decode high-frequency VLC signals, today's VLP systems require the receiver to equip either rolling shutter cameras or high-frequency light sensors, which bring considerable overhead or are even unavailable on many mobile devices. This paper introduces ALS-P, a lightweight VLP approach which only requires the commercially widely available ambient light sensor (ALS). ALS is conventionally not treated as a feasible VLC receiver as its sampling rate is far less than that of VLC signals. Our basic idea is to leverage the property of frequency aliasing. Through dynamically adjusting the sampling rate of the ALS sensor, the down-converted signals can be uniquely distinguished. To realize this idea, we propose novel designs to address challenges which stem from ALS hardware, high-order light aliasing, and environmental interference cancellation. Besides, ALS can also enable a lightweight VLC via changing LED frequencies. We implement the ALS-P on commercial LED bulbs and the ALS of existing smartphones. The evaluation shows that the ALSP can enable robust and efficient LED frequency decoding with at least 4LEDs bulbs in practical scenarios. As a result, ALS-P can enable VLC at a data rate of 5bit/s per each LED bulb and achieve a sub-meter level indoor localization accuracy.
【Keywords】: Light emitting diodes; Receivers; Transmitters; Mobile handsets; Decoding; Frequency response; Interference
【Paper Link】 【Pages】:1315-1323
【Authors】: Hao Cui ; Huanyu Bian ; Weiming Zhang ; Nenghai Yu
【Abstract】: Screen-camera communication techniques achieve one-way communication with widely-used screen and camera devices. Popular barcode methods use visible spatial patterns to represent data, which has been considered obtrusive to human observers. Recent works borrow ideas from visual light communication (VLC), and use inter-frame pixel change to modulate data. To recover pixel change, the receiver has to record and process video frames. Such video-based extraction has high hardware requirements and lacks reliability. Inspired by VLC-based methods, we propose UnseenCode, an invisible on-screen barcode scheme. It leverages inter-frame embedment from VLC-based methods to embed invisible barcodes into arbitrary on-screen contents. Unlike VLC-based methods, UnseenCode does not require video-based extraction. We propose an image-based extraction method based on cross-component correlation of color images. Any off-the-shelf smartphones with camera capability can be used to read UnseenCode by capturing on-screen contents. We propose the full implementation of UnseenCode for evaluation. Experimental results show that UnseenCode decoding algorithm is reliable and applicable under various screen and camera settings. UnseenCode provides up to 2.5 kbit capacity with less than 5% error rate.
【Keywords】: Cameras; Image color analysis; Smart phones; Reliability; Receivers; Hardware; Observers
【Paper Link】 【Pages】:1324-1332
【Authors】: Rens Bloom ; Marco Zuniga ; Qing Wang ; Domenico Giustiniano
【Abstract】: We analyze and optimize the performance of a new type of channel that exploits sunlight for wireless communication. Recent advances on visible light backscatter have shown that if mobile objects attach distinctive reflective patterns to their surfaces, simple photosensors deployed in our environments can decode the reflected light signals. Although the vision is promising, only initial feasibility studies have been performed so far. There is no analysis on how much information this channel can transmit or how reliable the links are. Achieving this vision is a complex endeavour because we have no control over (i) the sun or clouds, which determine the amount and direction of light intensity, and (ii) the mobile object, which determines the modulated reflection of sunlight. We investigate the impact of the surrounding light intensity and physical properties of the object (reflective materials, size and speed) to design a communication system that optimizes the encoding and decoding of information with sunlight. Our experimental evaluation, performed with a car moving on a regular street, shows that our analysis leads to significant improvements across many dimensions. Compared to the state of the art, we can encode seven times more information, and decode this information reliably from an object moving three times faster (53km/h) at a range that is four times longer (4m) and with three times lower light intensity (cloudy day).
【Keywords】: Receivers; Reliability; Sun; Decoding; Automobiles; Encoding; Wireless communication
【Paper Link】 【Pages】:1333-1341
【Authors】: Mathieu Jadin ; Francois Aubry ; Pierre Schaus ; Olivier Bonaventure
【Abstract】: Segment Routing (SR) is a powerful tool to solve traffic engineering in large networks. It enables steering the traffic along any arbitrary network path while limiting scalability issues as routers do not need to maintain a global state. Mathematical programming approaches proposed so far for SR either do not scale well with the size of topology or impose a strong limit on the number of possible detours (typically at most one). Moreover they do not support Segment Routing fully by ignoring the adjacency segments. This paper leverages column generation, a widely used technique for solving large scale linear programs, combined with a novel dynamic program for solving the pricing problem. Our approach reaches near optimal solutions with gap guarantees by also computing a strong lower-bound tighter than the multi-commodity flow relaxation. It scales even on large topologies and exploits the full expressiveness of SR including adjacency segments. Our experiments compared with existing traffic engineering techniques on various topologies and demand matrices demonstrate the advantages of our approach in terms of scalability, any-time behavior and quality of the solutions.
【Keywords】: Routing; Pricing; Network topology; Topology; Multiprotocol label switching; Scalability; Internet
【Paper Link】 【Pages】:1342-1350
【Authors】: Khaled M. Diab ; Mohamed Hefeeda
【Abstract】: Telco-CDNs refer to content distribution networks deployed and managed by Internet Service Providers (ISPs). They are getting popular among major ISPs because they offer new revenue streams and have the potential of providing better performance compared to traditional CDNs. Managing telco-CDNs is, however, a complex problem, because it requires jointly managing the network resources (links and switches) and the caching resources (processing and storage capacities), while supporting the adaptive nature and skewed popularity of multimedia content. To address this problem, we present a new algorithm called CAD (Cooperative Active Distribution), which strives to serve as much as possible of the requested multimedia objects within the ISP while carefully engineering the traffic paths through the network. This is achieved by enabling the cooperation among caches within the ISP not only to serve various representations of multimedia objects, but also to create them on demand using the available processing capacity of caches. We have implemented CAD and evaluated it on top of a network emulator that runs deployment code and processes real traffic. Using an actual ISP topology, our experimental results show that CAD achieves substantial performance improvements compared to the closest work in the literature, e.g., up to 64% reduction in the total inter-domain traffic.
【Keywords】: Streaming media; Servers; Videos; Solid modeling; Multimedia systems; Transcoding; Adaptive systems
【Paper Link】 【Pages】:1351-1359
【Authors】: Chen Avin ; Kaushik Mondal ; Stefan Schmid
【Abstract】: Emerging communication technologies allow to reconfigure the physical network topology at runtime, enabling demand-aware networks (DANs): networks whose topology is optimized toward the workload they serve. However, today, only little is known about the fundamental algorithmic problems underlying the design of such demand-aware networks. This paper presents the first bounded-degree, demand-aware network, ct-DAN, which minimizes both congestion and route lengths. The designed network is provably (asymptotically) optimal in each dimension individually: we show that there do not exist any bounded-degree networks providing shorter routes (independently of the load), nor do there exist networks providing lower loads (independently of the route lengths). The main building block of the designed ct-DAN networks are ego-trees: communication sources arrange their communication partners in an optimal tree, individually. While the union of these ego-trees forms the basic structure of cl-DANs, further techniques are presented to ensure bounded degrees (for scalability).
【Keywords】: Routing; Binary trees; Data centers; Approximation algorithms; Network topology; Entropy
【Paper Link】 【Pages】:1360-1368
【Authors】: Fan Zhou ; Zijing Wen ; Goce Trajcevski ; Kunpeng Zhang ; Ting Zhong ; Fang Liu
【Abstract】: Network alignment (NA) is a fundamental problem in many application domains - from social networks, through biology and communications, to neuroscience. The main objective is to identify common nodes and most similar connections across multiple networks (resp. graphs). Many of the existing efforts focus on efficient anchor node linkage by leveraging various features and optimizing network mapping functions with the pairwise similarity between anchor nodes. Despite the recent advances, there still exist two kinds of challenges: (1) entangled node embeddings, arising from the contradictory goals of NA: embedding proximal nodes in a closed form for representation in a single network vs. discriminating among them when mapping the nodes across networks; and (2) lack of interpretability about the node matching and alignment, essential for understanding prediction tasks. We propose d NAME (disentangled Network Alignment with Matching Explainability) - a novel solution for NA in heterogeneous networks settings, based on a matching technique that embeds nodes in a disentangled and faithful manner. The NA task is cast as an adversarial optimization problem which learns a proximity-preserving model locally around the anchor nodes, while still being discriminative. We also introduce a method to explain our semi-supervised model with the theory of robust statistics, by tracing the importance of each anchor node and its explanations on the NA performance. This is extensible to many other NA methods, as it provides model interpretability. Experiments conducted on several public datasets show that d NAME outperforms the state-of-the-art methods in terms of both network alignment precision and node matching ranking.
【Keywords】: network alignment; social networks; graph kernel; adversarial learning
【Paper Link】 【Pages】:1369-1377
【Authors】: Victor Valls ; George Iosifidis ; Theodoros Salonidis
【Abstract】: This paper studies the problem of allocating band-width and computation resources to data analytics tasks in Internet of Things (IoT) networks. IoT nodes are powered by batteries, can process (some of) the data locally, and the quality grade or performance of how data analytics tasks are carried out depends on where these are executed. The goal is to design a resource allocation algorithm that jointly maximizes the network lifetime and the performance of the data analytics tasks subject to energy constraints. This joint maximization problem is challenging with coupled resource constraints that induce non-convexity. We first show that the problem can be mapped to an equivalent convex problem, and then propose an online algorithm that provably solves the problem and does not require any a priori knowledge of the time-varying wireless link capacities and data analytics arrival process statistics. The algorithm's optimality properties are derived using an analysis which, to the best of our knowledge, proves for the first time the convergence of the dual subgradient method with time-varying sets. Our simulations seeded by real IoT device energy measurements, show that the network connectivity plays a crucial role in network lifetime maximization, that the algorithm can obtain both maximum network lifetime and maximum data analytics performance in addition to maximizing the joint objective, and that the algorithm increases the network lifetime by approximately 50% compared to an algorithm that minimizes the total energy consumption.
【Keywords】: Internet of Things; Data analysis; Routing; Task analysis; Approximation algorithms; Logic gates; Wireless sensor networks
【Paper Link】 【Pages】:1378-1386
【Authors】: Fengqian Guo ; Hancheng Lu ; Daren Zhu ; Hao Wu
【Abstract】: To meet the performance and complexity requirements from practical deployment of non-orthogonal multiple access (NOMA) systems, several users are grouped together for NOMA transmission while orthogonal resources are allocated among groups. User grouping strategies have significant impact on the power consumption and system performance. However, existing related studies divide users into groups based on channel conditions, where diverse quality of service (QoS) and interference have not been considered. In this paper, we focus on the interference-aware user grouping strategy in NOMA systems, aiming at minimizing power consumption with QoS constraints. We define a power consumption and externality (PCE) function for each user to represent the power consumption involved by this user to satisfy its QoS requirement as well as interference that this user brings to others in the same group. Then, we extend the definition of PCE to multi-user scenarios and convert the user grouping problem into the problem of searching for specific negative loops in the graph. Bellman-Ford algorithm is extended to find these negative loops. Furthermore, a greedy suboptimal algorithm is proposed to approach the solution within polynomial time. Simulation results show that the proposed algorithms can considerably reduce the total power consumption compared with existing strategies.
【Keywords】: Non-orthogonal multiple access (NOMA); user grouping; quality of service (QoS); interference
【Paper Link】 【Pages】:1387-1395
【Authors】: Nguyen H. Tran ; Wei Bao ; Albert Y. Zomaya ; Nguyen N. H. Minh ; Choong Seon Hong
【Abstract】: There is an increasing interest in a new machine learning technique called Federated Learning, in which the model training is distributed over mobile user equipments (UEs), and each UE contributes to the learning model by independently computing the gradient based on its local training data. Federated Learning has several benefits of data privacy and potentially a large amount of UE participants with modern powerful processors and low-delay mobile-edge networks. While most of the existing work focused on designing learning algorithms with provable convergence time, other issues such as uncertainty of wireless channels and UEs with heterogeneous power constraints and local data size, are under-explored. These issues especially affect to various trade-offs: (i) between computation and communication latencies determined by learning accuracy level, and thus (ii) between the Federated Learning time and UE energy consumption. We fill this gap by formulating a Federated Learning over wireless network as an optimization problem FEDL that captures both trade-offs. Even though FEDL is non-convex, we exploit the problem structure to decompose and transform it to three convex sub-problems. We also obtain the globally optimal solution by charactering the closed-form solutions to all sub-problems, which give qualitative insights to problem design via the obtained optimal FEDL learning time, accuracy level, and UE energy cost. Our theoretical analysis is also illustrated by extensive numerical results.
【Keywords】: Distributed Machine Learning over Wireless Networks; Federated Learning; optimization Decomposition
【Paper Link】 【Pages】:1396-1404
【Authors】: Jie Chuai ; Zhitang Chen ; Guochen Liu ; Xueying Guo ; Xiaoxiao Wang ; Xin Liu ; Chongming Zhu ; Feiyi Shen
【Abstract】: Cellular network performance depends heavily on the configuration of its network parameters. Current practice of parameter configuration relies largely on expert experience, which is often suboptimal, time-consuming, and error-prone. Therefore, it is desirable to automate this process to improve the accuracy and efficiency via learning-based approaches. However, such approaches need to address several challenges in real operational networks: the lack of diverse historical data, a limited amount of experiment budget set by network operators, and highly complex and unknown network performance functions. To address those challenges, we propose a collaborative learning approach to leverage data from different cells to boost the learning efficiency and to improve network performance. Specifically, we formulate the problem as a transferable contextual bandit problem, and prove that by transfer learning, one could significantly reduce the regret bound. Based on the theoretical result, we further develop a practical algorithm that decomposes a cell's policy into a common homogeneous policy learned using all cells' data and a cell-specific policy that captures each individual cell's heterogeneous behavior. We evaluate our proposed algorithm via a simulator constructed using real network data and demonstrates faster convergence compared to baselines. More importantly, a live field test is also conducted on a real metropolitan cellular network consisting 1700+ cells to optimize five parameters for two weeks. Our proposed algorithm shows a significant performance improvement of 20%.
【Keywords】: Optimization; Cellular networks; Handover; Throughput; Collaborative work; Convergence
【Paper Link】 【Pages】:1405-1413
【Authors】: Ioannis Gasparis ; Zhiyun Qian ; Chengyu Song ; Srikanth V. Krishnamurthy ; Rajiv Gupta ; Paul Yu
【Abstract】: Today's Android systems do not allow users to manage the permissions granted to applications (apps) in a flexible and dynamic way. Recent studies show that apps often misuse these permissions to access private information, or have trapdoors via which other malicious apps can do the same. In this paper, we develop a framework Figment, which consists of set of libraries that developers can easily use to build in fine-grained dynamic permission management capabilities. The users of their apps can readily invoke these capabilities during execution. The apps would potentially run with reduced functionalities if the user does not wish to allow certain permissions. Figment also allows either the developer or a user to specify context aware permissions, which cause different permissions to be granted to the app in different functional modes (contexts). We believe that Figment reduces the attack surface exposed to potentially malicious apps and offers a significant step in preserving user privacy. While the rudimentary version of Figment uses aspect-oriented programming and does not need rooting of the phone or changes to the Android sub-system, we also provide an optional root-level fail safe implementation that facilitates the embedding of dynamic permission management functions in old applications not built by using Figment libraries. We show that Figment offers significant benefits over the Android Marshmallow permission management system with lower runtime overheads; the main penalty is a one time higher compilation overhead.
【Keywords】: Smart phones; Libraries; Privacy; Context-aware services; Runtime; Accelerometers; Programming
【Paper Link】 【Pages】:1414-1422
【Authors】: Nima Eshraghi ; Ben Liang
【Abstract】: We study the problem of joint offloading decision and resource allocation for mobile cloud networks with a computing access point (CAP) and a remote cloud center. We consider the case where the task computing requirement is not fully known before their execution. We aim to jointly optimize the offloading decisions as well as the allocation of computation and communication resources, to minimize a weighted sum of the average cost and cost variation. The problem is formulated as a mixed-integer program. We propose an efficient algorithm, termed Task Offloading and Resource Allocation with Uncertain Computing (TORAUC), and show that it always converges to a Karush-Kuhn-Tucker (KKT) point of an alternate form of the original problem, which has its binary constraints removed but guarantees an offloading decision solution that is arbitrarily close to binary. We extend TORAUC to TORAUC-MP for the case of a multi-processor CAP. Through trace-based simulation, we study the performance of TORAUC and TORAUC-MP. We observe that TORAUC is nearly optimal, and both algorithms substantially outperform several alternatives.
【Keywords】: Task analysis; Cloud computing; Resource management; Delays; Uncertainty; Computational modeling; Mobile handsets
【Paper Link】 【Pages】:1423-1431
【Authors】: Chuang Hu ; Wei Bao ; Dan Wang ; Fengming Liu
【Abstract】: Recent advances in deep neural networks (DNNs) have substantially improved the accuracy and speed of a variety of intelligent applications. Nevertheless, one obstacle is that DNN inference imposes heavy computation burden to end devices, but offloading inference tasks to the cloud causes transmission of a large volume of data. Motivated by the fact that the data size of some intermediate DNN layers is significantly smaller than that of raw input data, we design the DNN surgery, which allows partitioned DNN processed at both the edge and cloud while limiting the data transmission. The challenge is twofold: (1) Network dynamics substantially influence the performance of DNN partition, and (2) State-of-the-art DNNs are characterized by a directed acyclic graph (DAG) rather than a chain so that partition is greatly complicated. In order to solve the issues, we design a Dynamic Adaptive DNN Surgery (DADS) scheme, which optimally partitions the DNN under different network condition. Under the lightly loaded condition, DNN Surgery Light (DSL) is developed, which minimizes the overall delay to process one frame. The minimization problem is equivalent to a min-cut problem so that a globally optimal solution is derived. In the heavily loaded condition, DNN Surgery Heavy (DSH) is developed, with the objective to maximize throughput. However, the problem is NP-hard so that DSH resorts an approximation method to achieve an approximation ratio of 3. Real-world prototype based on self-driving car video dataset is implemented, showing that compared with executing entire the DNN on the edge and cloud, DADS can improve latency up to 6.45 and 8.08 times respectively, and improve throughput up to 8.31 and 14.01 times respectively.
【Keywords】: Cloud computing; Delays; Surgery; Neural networks; Throughput; Streaming media; Bandwidth
【Paper Link】 【Pages】:1432-1440
【Authors】: Hengrun Zhang ; Kai Zeng
【Abstract】: In this paper, we propose a task scheduling strategy, which can achieve image feature extraction on edge while ensuring privacy. Our task scheduling strategy applies to a fairly popular privacy-preserving Scale-Invariant Feature Transform SIFT scheme, where images to be processed are firstly randomly split into two portions for encryption and transmitted to two different edge nodes for feature extraction. Then, in the edge, our task scheduling strategy will re-assign these two portions to proper edge nodes for processing. During the whole process, two portions of the same image should not be assigned to the same edge node in order to preserve privacy. We show that this privacy constraint can be enforced through constructing a pairwise Markov chain, and carefully designing system states and transition probabilities. We further formulate the whole task scheduling problem as a stochastic latency minimization problem and solve it by converting it into a linear programming problem. Simulation results show that our proposed task scheduling strategy can achieve lower latency than baseline strategies while satisfying the privacy constraint.
【Keywords】: Image edge detection; Privacy; Task analysis; Feature extraction; Cloud computing; Markov processes; Processor scheduling
【Paper Link】 【Pages】:1441-1449
【Authors】: Yang Liu ; Huanle Xu ; Wing Cheong Lau
【Abstract】: Jobs in modern computing clusters have highly diverse processing durations and heterogeneous resource requirements. In this paper, we consider the problem of online job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the diversity of resource demands for different jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the notion of fractional job flowtime as a surrogate objective for minimization. We apply Online Convex optimization (OCO) techniques to design the corresponding online scheduling algorithm. More importantly, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function of our online convex optimization formulation with the corresponding switching costs.
【Keywords】: Online job scheduling; resource packing; online convex optimization; dynamic regret; switching cost
【Paper Link】 【Pages】:1450-1458
【Authors】: Klaus-Tycho Foerster ; Juho Hirvonen ; Stefan Schmid ; Jukka Suomela
【Abstract】: As communication networks are growing at a fast pace, the need for more scalable approaches to operate such networks is pressing. Decentralization and locality are key concepts to provide scalability. Existing models for which local algorithms are designed fail to model an important aspect of many modern communication networks such as software-defined networks: the possibility to precompute distributed network state. We take this as an opportunity to study the fundamental question of how and to what extent local algorithms can benefit from preprocessing. In particular, we show that preprocessing allows for significant speedups of various networking problems. A main benefit is the precomputation of structural primitives, where purely distributed algorithms have to start from scratch. Maybe surprisingly, we also show that there are strict limitations on how much preprocessing can help in different scenarios. To this end, we provide approximation bounds for the maximum independent set problem-which however show that our obtained speedups are asymptotically optimal. Even though we show that physical link failures in general hinder the power of preprocessing, we can still facilitate the precomputation of symmetry breaking processes to bypass various runtime barriers. We believe that our model and results are of interest beyond the scope of this paper and apply to other dynamic networks as well.
【Keywords】: Decentralization; Local algorithms; Software-defined networks
【Paper Link】 【Pages】:1459-1467
【Authors】: Bin Gao ; Zhi Zhou ; Fangming Liu ; Fei Xu
【Abstract】: Mobile Edge Computing (MEC) is an emerging computing paradigm in which computational capabilities are pushed from the central cloud to the network edges. However, preserving the satisfactory quality-of-service (QoS) for user applications is non-trivial among multiple densely dispersed yet capacity constrained MEC nodes. This is mainly because both the access network and edge nodes are vulnerable to network congestion. Previous works are mostly limited to optimizing the QoS through dynamic service placement, while ignoring the critical effects of access network selection on the network congestion. In this paper, we study the problem of jointly optimizing the access network selection and service placement for MEC, towards the goal of improving the QoS by balancing the access, switching and communication delay. Specifically, we first design an efficient online framework to decompose the long-term optimization problem into a series of one-shot problems. To address the NP-hardness of the one-shot problem, we further propose an iteration-based algorithm to derive a computation efficient solution. Both rigorous theoretical analysis on the optimality gap and extensive trace-driven simulations validate the efficacy of our proposed solution.
【Keywords】: Cloud computing; Delays; Quality of service; Switches; Optimization; Edge computing; Computer science
【Paper Link】 【Pages】:1468-1476
【Authors】: Tao Ouyang ; Rui Li ; Xu Chen ; Zhi Zhou ; Xin Tang
【Abstract】: Mobile Edge Computing (MEC), envisioned as a cloud extension, pushes cloud resource from the network core to the network edge, thereby meeting the stringent service requirements of many emerging computation-intensive mobile applications. Many existing works have focused on studying the system-wide MEC service placement issues, personalized service performance optimization yet receives much less attention. Thus, in this paper we propose a novel adaptive user-managed service placement mechanism, which jointly optimizes a user's perceived-latency and service migration cost, weighted by user preferences. To overcome the unavailability of future information and unknown system dynamics, we formulate the dynamic service placement problem as a contextual Multi-armed Bandit (MAB) problem, and then propose a Thompson-sampling based online learning algorithm to explore the dynamic MEC environment, which further assists the user to make adaptive service placement decisions. Rigorous theoretical analysis and extensive evaluations demonstrate the superior performance of the proposed adaptive user-managed service placement mechanism.
【Keywords】: Servers; Delays; Task analysis; Heuristic algorithms; Base stations; Adaptive systems; Optimization
【Paper Link】 【Pages】:1477-1485
【Authors】: He Li ; Yaling Yang ; Yanzhi Dou ; Jung-Min "Jerry" Park ; Kui Ren
【Abstract】: Database driven dynamic spectrum sharing is one of the most promising dynamic spectrum access (DSA) solution to address the spectrum scarcity issue. In such a database-driven DSA system, the centralized spectrum management infrastructure, called spectrum access system (SAS), collects sensitive operational data of both incumbent users (IUs) and secondary users (SUs), which makes privacy protection critical in this paradigm. However, the few existing solutions rely on online trusted third party, which requires extra infrastructure and brings the risk of single point failure. To address the shortcomings of existing solutions, we propose a privacy enhanced and database-driven dynamic spectrum sharing (PeDSS) framework in this paper, which preserves the privacy for both IUs and SUs in database-driven DSA systems without the need for online trusted third party. Privacy for both IUs and SUs are formally defined and analyzed, and experiment results show that SAS under PeDSS is able to handle a single spectrum request in 0.51 ms on average, which is three orders of magnitude faster than prior arts.
【Keywords】: Privacy-preserving protocols; Dynamic spectrum access; Location privacy
【Paper Link】 【Pages】:1486-1494
【Authors】: Lin He ; Gang Ren ; Ying Liu
【Abstract】: Accountability and privacy are considered valuable but conflicting properties in the Internet, which at present does not provide native support for either. Past efforts to balance accountability and privacy in the Internet have unsatisfactory deployability due to the introduction of new communication identifiers, and because of large-scale modifications to fully deployed infrastructures and protocols. The IPv6 is being deployed around the world and this trend will accelerate. In this paper, we propose a private and accountable proposal based on IPv6 called PAVI that seeks to bootstrap accountability and privacy to the IPv6 Internet without introducing new communication identifiers and large-scale modifications to the deployed base. A dedicated quantitative analysis shows that the proposed PAVI achieves satisfactory levels of accountability and privacy. The results of evaluation of a PAVI prototype show that it incurs little performance overhead, and is widely deployable.
【Keywords】: accountability; privacy; IPv6
【Paper Link】 【Pages】:1495-1503
【Authors】: Mohamed Grissa ; Attila A. Yavuz ; Bechir Hamdaoui
【Abstract】: As part of its ongoing efforts to meet the increased spectrum demand, the Federal Communications Commission (FCC) has recently opened up 150 MHz in the 3.5 GHz band for shared wireless broadband use. Access and operations in this band, aka Citizens Broadband Radio Service (CBRS), will be managed by a dynamic spectrum access system (SAS) to enable seamless spectrum sharing between secondary users (SUs) and incumbent users. Despite its benefits, SAS's design requirements, as set by FCC, present privacy risks to SUs, merely because SUs are required to share sensitive operational information (e.g., location, identity, spectrum usage) with SAS to be able to learn about spectrum availability in their vicinity. In this paper, we propose TrustSAS, a trustworthy framework for SAS that synergizes state-of-the-art cryptographic techniques with blockchain technology in an innovative way to address these privacy issues while complying with FCC's regulatory design requirements. We analyze the security of our framework and evaluate its performance through analysis, simulation and experimentation. We show that TrustSAS can offer high security guarantees with reasonable overhead, making it an ideal solution for addressing SUs' privacy issues in an operational SAS environment.
【Keywords】: Spectrum access system; Citizens Broadband Radio Service; spectrum databases; Blockchain; privacy
【Paper Link】 【Pages】:1504-1512
【Authors】: Xiaonan Zhang ; Pei Huang ; Linke Guo ; Mo Sha
【Abstract】: Internet of Things (IoT) has emerged as a new computing paradigm that promises to offer a fully connected “smart” world. However, due to the open nature of wireless medium, the information sensed, collected, and transmitted by IoT devices can be easily intercepted by adversaries, which becomes a serious concern in most IoT applications requiring sensitive data. In practice, cooperative communication approaches can effectively improve the security level for wireless communication under the presence of eavesdroppers with unbounded computational ability. In this paper, we apply the amplify-and-forward (AF) cooperative communication to increase the secrecy capacity of IoT systems by incentivizing relay IoT devices. Specifically, a Stackelberg game is designed to motivate the participation of the relay IoT devices for security enhancement. Extensive experimental results have demonstrated the feasibility and security of the proposed mechanism under both unknown and known channel state information (CSI) models.
【Keywords】: IoT; Cooperative Communication; Stackelberg Game; Physical-layer Security
【Paper Link】 【Pages】:1513-1521
【Authors】: Cui Zhao ; Zhenjiang Li ; Ting Liu ; Han Ding ; Jinsong Han ; Wei Xi ; Ruowei Gui
【Abstract】: This paper presents RF-Mehndi, a passive commercial RFID tag array formed identifier. The key RF-Mehndi novelty is that when the user's fingertip touching on the tag array surface during the communication, the backscattered signals by the tag array become user-dependent and unique. Hence, if we enhance the communication modality of many personal cards nowadays by RF-Mehndi, in case that a card gets lost or stolen, it cannot be used illegally by the adversaries. To harvest such a benefit, we have two key observations in designing RF-Mehndi. The first observation is when tags are nearby, their interrogated currents can change each other's circuit characteristics, based on which unique phase features can be obtained from backscattered signals. The second observation is that when the user's fingertip touches the tag array surface during communication, the phase feature can be further profiled by this user. Based on these observations, the card and its holder can be potentially authenticated at the same time. To transfer the RF-Mehndi idea to a practical system, we further address technical challenges. We implement a prototype system. Extensive evaluations show the effectiveness of RF-Mehndi, achieving excellent authentication performance.
【Keywords】: Couplings; Phased arrays; Authentication; RFID tags; Backscatter
【Paper Link】 【Pages】:1522-1530
【Authors】: Jia Liu ; Xingyu Chen ; Xiulong Liu ; Xiaocong Zhang ; Xia Wang ; Lijun Chen
【Abstract】: High write throughput plays a vital role in improving the time efficiency of RFID-enabled applications, such as password update and over-the-air programming. In this paper, we make a fresh attempt to study the under-investigated problem of group write and discuss how to improve the write throughput in the commodity RFID system. By conducting extensive experiments, we reveal that the select operation specified by the C1G2 standard takes up the large overhead of a write cycle, which is the key factor in determining the write efficiency. Based on this finding, we propose an efficient write bundling (WB) scheme that bundles multiple writes up and executes them together in a burst mode, which greatly reduces the number of selects and thereby amplifies the write throughput. In WB, a carefully designed bit vector is assigned to each tag for connecting multiple tags into a run, such that a single select command is able to pick these tags concurrently. Besides, WB integrates multiple select commands into one by running a series of logic operations on the inventoried flags, which are used to indicate whether or not a tag is active. We implement WB in a commodity RFID system, with no need of any software modifications or hardware argument. Extensive experiment results show that WB is able to reduce the number of selects by 87.5% and produce a 2× write amplification, compared with the C1G2-compatible exclusive write.
【Keywords】: Radiofrequency identification; Throughput; Standards; Password; Programming; Protocols; Software
【Paper Link】 【Pages】:1531-1539
【Authors】: Zhenlin An ; Qiongzheng Lin ; Lei Yang ; Wei Lou
【Abstract】: Embedding Radio-Frequency IDentification (RFID) into everyday objects to construct ubiquitous networks has been a long-standing goal. However, a major problem that hinders the attainment of this goal is the current inefficient reading of RFID tags. To address issue, the research community introduces the technique of Bloom Filter (BF) to RFID systems. This work presents TagMap, a practical solution that acquires BFs across commercial off-the-shelf (COTS) RFID tags in the physical layer, enabling upper applications to boost their performance by orders of magnitude. The key idea is to treat all tags as if they were a single virtual sender, which hashes each tag into different intercepted inventories. Our approach does not require hardware nor firmware changes in commodity RFID tags -allows for rapid, zero-cost deployment in existing RFID tags. We design and implement TagMap reader with commodity device (e.g., USRP N210) platforms. Our comprehensive evaluation reveals that the overhead of TagMap is 66.22% lower than the state-of-the-art solution, with a bit error rate of 0.4%.
【Keywords】: RFID tags; Protocols; Hash functions; Physical layer; Standards; RF signals
【Paper Link】 【Pages】:1540-1548
【Authors】: Sihua Shao ; Abdallah Khreishah ; Juan Paez
【Abstract】: Identifying the accurate location of small objects is a key element of Internet of Things (IoT). This paper investigates the feasibility of tracking the real-time location of a completely passive retroreflector using visible light for IoT applications. Existing ultra-low power visible light retroreflector systems modulate light with a liquid crystal display (LCD) shutter, which is powered by a solar cell. However, the solar cell costs additional space exclusively for energy harvesting, and it may not be able to supply enough power to the advanced power-hungry LCD shutter and its driver circuit. To eliminate the power supply, we design, implement and evaluate PassiveRETRO, an enhanced retroreflector-based visible light localization system. The PassiveRETRO system completely eliminates the necessity of any electronic component on the IoT devices. Polarization-based modulation and bandpass optical filters are adopted to identify the retroreflected optical signal and create multiple channels. Each IoT device operates on a specific range of the visible light spectrum. Optical rotatory dispersion is further applied to mitigate the mutual interference among different channels. Experimental results from our prototyped system show that PassiveRETRO is robust to environmental reflection and can still achieve centimeter-level location accuracy when multiple IoT devices are deployed.
【Keywords】: Visible light localization; passive localization; Internet of Things; polarization; retroreflection
【Paper Link】 【Pages】:1549-1557
【Authors】: Yining Zhu ; Haoran Yu ; Randall A. Berry ; Chang Liu
【Abstract】: We analyze the prioritized sharing between an added value Mobile Virtual Network Operator (MVNO) and multiple Mobile Network Operators (MNOs). An added value MVNO is one which earns added revenue from wireless users in addition to the revenue it directly collects for providing them wireless service. To offer service, an MVNO needs to contract with one or more MNOs to utilize their networks. Agreeing on such a contract requires the MNOs to consider the impact on their revenue from allowing the MVNO to enter the market as well as the possibility that other MNOs will cooperate. To further protect their customers, the MNOs may prioritize their direct customers over those of the MVNO. We establish a multi-stage game to analyze the equilibrium decisions of the MVNO, MNOs, and users in such a setting. In particular, we characterize the condition under which the MVNO can collaborate with the MNOs. The results show that the MVNO tends to cooperate with the MNOs when the band resources are limited and the added value is significant. When there is significant difference in band resources among the MNOs, the MVNO first considers cooperating with the MNO with a smaller band. We also consider the case when the users also have access to unlicensed spectrum.
【Keywords】: Wireless communication; Contracts; Games; Wireless sensor networks; Google; Bandwidth; Quality of service
【Paper Link】 【Pages】:1558-1566
【Authors】: Ming Tang ; Jianwei Huang
【Abstract】: Donation-based markets are becoming increasingly popular in our daily life. One example is the online streaming platform Twitch, which attracts millions of users on a daily basis. On such platforms, firms provide services to customers without mandatory charge, and customers voluntarily donate money to the firms. The donations are split between the firms and the platform with a fixed pre-agreed fraction. To gain insights into the operation and optimization of such platforms, we formulate a two-stage game to study the platform's and firms' behaviors. In Stage I, the platform decides a donation-split-fraction (DSF), which corresponds to the fraction of donations kept by the firms. In Stage II, firms decide whether to participate in the platform and how to choose their service attributes considering the DSF as well as the preferences of firms and customers. Analyzing such a two-stage game directly is challenging, as the Stage II problem corresponds to the multi-firm extension of the Hotelling model and is still an open problem. To resolve this issue, we approximate the large number of firms as non-atomic decision makers, where a single firm's strategy choice does not affect the payoffs of the firm population. Under such an approximation, we prove that the Stage II problem is a potential game. We further show that at the equilibrium, a larger DSF leads to more firm participations and a better match to the customers' preferences. The stage I problem, nevertheless, is a non-convex optimization problem that does not render a closed-form solution. To gain insights, we derive the upper-bound and lower-bound of the optimal DSF solution. The bounds suggest that the platform should increase its DSF if the customers' donation sensitivity to the number of firms increases or if the firms' opportunity cost for participation increases. Finally, we collect data from Twitch and demonstrate the results of the two-stage model with a case study. Our simulation results suggest that under our data and model settings, there exists a significant potential for Twitch to improve its payoff, by setting the DSF to 0.38, instead of 0.71 as in Twitch's current practice.
【Keywords】: Games; Sociology; Statistics; Optimization; Data models; Analytical models; Sensitivity
【Paper Link】 【Pages】:1567-1575
【Authors】: Huan Zhou ; Xue Ouyang ; Zhijie Ren ; Jinshu Su ; Cees de Laat ; Zhiming Zhao
【Abstract】: Traditional cloud Service Level Agreement (SLA) suffers from lacking a trustworthy platform for automatic enforcement. The emerging blockchain technique brings in an immutable solution for tracking transactions among business partners. However, it is still very challenging to prove the credibility of possible violations in the SLA before recording them onto the blockchain. To tackle this challenge, we propose a witness model using game theory and the smart contract techniques. The proposed model extends the existing service model with a new role called “witness” for detecting and reporting service violations. Witnesses gain revenue as an incentive for performing these duties, and the payoff function is carefully designed in a way that trustworthiness is guaranteed: in order to get the maximum profit, the witness has to always tell the truth. This is analyzed and proved through game theory using the Nash equilibrium principle. In addition, an unbiased sortition algorithm is proposed to ensure the randomness of the independent witnesses selection from the decentralized witness pool, to avoid possible unfairness or collusion. An auditing mechanism is also introduced in the paper to detect potential irrational or malicious witnesses. We have prototyped the system leveraging the smart contracts of Ethereum blockchain. Experimental results demonstrate the feasibility of the proposed model and indicate good performance in accordance with the design expectations.
【Keywords】: Blockchain; Smart contracts; Cloud computing; Monitoring; Nash equilibrium
【Paper Link】 【Pages】:1576-1584
【Authors】: Yuxuan Jiang ; Mohammad Shahrad ; David Wentzlaff ; Danny H. K. Tsang ; Carlee Joe-Wong
【Abstract】: Leading cloud providers recently introduced a new instance type named burstable instances to better match the time-varying workloads of tenants and further reduce their costs. In the research community, however, little has been done to understand burstable instances from a theoretical perspective. This paper presents the first unified framework to model, analyze, and optimize the operation of burstable instances. Specifically, we model the resource provisioning of burstable instances in different service classes, identify key performance metrics, and derive the performance given the resource provisioning decisions. We then characterize the equilibrium behind tenants' responses to the prices offered for different burstable instance service classes, taking into account the impact of tenants' actions on the performance achieved by each service class. In addition, we investigate how a cloud provider can leverage the knowledge of this equilibrium to find the prices that maximize its total revenue. Finally, we validate our framework on real traces and demonstrate its usage to price a public cloud.
【Keywords】: cloud; burstable instances; equilibrium; revenue maximization
【Paper Link】 【Pages】:1585-1593
【Authors】: Salvatore D'Oro ; Francesco Restuccia ; Tommaso Melodia
【Abstract】: Undetectable wireless transmissions are fundamental to avoid eavesdroppers or censorship by authoritarian governments. To address this issue, wireless steganography “hides” covert information inside primary information by slightly modifying the transmitted waveform such that primary information will still be decodable, while covert information will be seen as noise by agnostic receivers. Since the addition of covert information inevitably decreases the SNR of the primary transmission, a key challenge in wireless steganography is to mathematically analyze and optimize the impact of the covert channel on the primary channel as a function of different channel conditions. Another core issue is to make sure that the covert channel is almost undetectable by eavesdroppers. Existing approaches are protocol-specific and thus their performance cannot be assessed and optimized in general scenarios. To address this research gap, we notice that existing wireless technologies rely on phase-keying modulations (e.g., BPSK, QPSK) that in most cases do not use the channel up to its Shannon capacity. Therefore, the residual capacity can be leveraged to implement a wireless system based on a pseudo-noise asymmetric shift keying (PN-ASK) modulation, where covert symbols are mapped by shifting the amplitude of primary symbols. This way, covert information will be undetectable, since a receiver expecting phase-modulated symbols will see their shift in amplitude as an effect of channel/path loss degradation. Through rigorous mathematical analysis, we first investigate the SER of PN-ASK as a function of the channel; then, we find the optimal PN-ASK parameters that optimize primary and covert throughput under different channel condition. We evaluate the throughput performance and undetectability of PN-ASK through extensive simulations and on an experimental testbed based on USRP N210 software-defined radios. Results indicate that PN-ASK improves the throughput by more than 8x with respect to prior art. Finally, we demonstrate through experiments that PN-ASK is able to transmit covert data on top of IEEE 802.11g frames, which are correctly decoded by an off-the-shelf laptop WiFi card without any hardware modifications.
【Keywords】: Steganography; Wireless Communications; Un-detectability
【Paper Link】 【Pages】:1594-1602
【Authors】: Yidan Hu ; Rui Zhang
【Abstract】: Database-driven Dynamic Spectrum Sharing (DSS) is a promising technical paradigm for enhancing spectrum efficiency by allowing secondary user to opportunistically access licenced spectrum channels without interfering with primary users' transmissions. In database-driven DSS, a geo-location database administrator (DBA) maintains the spectrum availability in its service region in the form of a radio environment map (REM) and grant or deny secondary users' spectrum access requests based on primary users' activities. Crowdsourcing-based spectrum sensing has great potential in improving the accuracy of the REM at the DBA but requires strong incentives and privacy protection to simulate mobile users' participation. To tackle this challenge, this paper introduces a novel differentially-private reverse auction mechanism for crowdsourcing-based spectrum sensing. The proposed mechanism allows the DBA to select spectrum sensing participants under a budget constraint while offering differential bid privacy, approximate truthfulness, and approximate accuracy maximization. Extensive simulation studies using a real spectrum measurement dataset confirm the efficacy and efficiency of the proposed mechanism.
【Keywords】: Sensors; Crowdsourcing; Privacy; Atmospheric measurements; Particle measurements; Interpolation; Task analysis
【Paper Link】 【Pages】:1603-1611
【Authors】: Shangqing Zhao ; Zhuo Lu ; Zhengping Luo ; Yao Liu
【Abstract】: Wireless jamming remains as one of the primary threats towards wireless security. Traditionally, jamming is able to disrupt wireless signals within, but not beyond, its covered bandwidth. In this paper, we propose a novel attack strategy, called orthogonality-sabotaging attack, against orthogonal frequency division multiple access (OFDMA) that has been widely adopted in today's wireless network standards (e.g., 4G/5G and 802.11ax). The attack intentionally introduces an unaligned narrowband jamming signal to an OFDMA network so as to destroy the orthogonality among all subcarriers in broadband signals. We theoretically formulate and optimize the attack strategies, and then use real-world experiments to show that orthogonality sabotaging is very efficient and can take down an 802.11ax network with only 1/5-1/4 of the full network bandwidth. Finally, we propose an attack identification and localization method to identify and localize orthogonality-sabotaging attacks in the fullband spectrum with 92% overall accuracy and localization errors within about 0.4 subcarrier spacing in experiments.
【Keywords】: Jamming; OFDM; Interference; Narrowband; Receivers; Wireless networks
【Paper Link】 【Pages】:1612-1620
【Authors】: Wei Xiong ; Petko Bogdanov ; Mariya Zheleva
【Abstract】: Modulation recognition plays a key role in emerging spectrum applications including spectrum enforcement, resource allocation, privacy and security. While critical for the practical progress of spectrum sharing, modulation recognition has so far been investigated under unrealistic assumptions: (i)a transmitter's bandwidth must be scanned alone and in full, (ii) prior knowledge of the technology must be available and (iii) a transmitter must be trustworthy. In reality these assumptions cannot be readily met, as a transmitter's bandwidth may only be scanned intermittently, partially, or alongside other transmitters, and modulation obfuscation may be introduced by short-lived scans or malicious activity.This paper bridges the gap between real-world spectrum sensing and the growing body of methods for modulation recognition designed under simplifying assumptions. We propose to use local features, besides global statistics, extracted from raw IQ data, which collectively enable a robust framework for modulation recognition that outperforms baselines from the state-of-the-art. Specifically, we exploit the discriminative power of local patterns from consecutive IQ samples extracted based on a Fisher Kernel framework that captures non-linearity in the underlying data. With these domain-informed features, we employ lightweight linear support vector machine classification for modulation detection. Our framework is robust to noise, partial transmitter scans and data biases without utilizing prior knowledge of the underlying transmitter technology. The recognition accuracy of our approach consistently outperforms baselines in both simulated and real-world traces. We demonstrate up to a 98% accuracy and a 30% improvement over several counterparts from the literature with partial scans in a USRP testbed.
【Keywords】: Modulation; Transmitters; Sensors; Feature extraction; Support vector machines; Bandwidth; Kernel
【Paper Link】 【Pages】:1621-1629
【Authors】: Ahmed M. Abdelmoniem ; Brahim Bensaou
【Abstract】: Much of the incremental improvement to TCP over the past three decades had the ultimate goal of making it more effective in using the long-fat pipes of the global Internet. This resulted in a rigid set of mechanisms in the protocol that put TCP at a disadvantage in small-delay environments such as data centers. In particular, in the presence of the shallow buffers of commodity switches and the short round trip times in data centers, the continued use of a large TCP initial congestion window and a huge minimum retransmission timeout (both inherited from the Internet-centric design) results in a very short TCP loss cycle that affects particularly the flow completion times of short-lived incast flows. In this paper, we first investigate empirically the TCP loss cycle and discuss its impact on packet losses, recovery and delay; then we propose a switch-based congestion controller with hysteresis (HSCC) that aims to stretch the TCP loss cycle without modifying TCP itself. To protect incast flows from severe congestion, HSCC is designed to transparently induce the TCP source to alternate between its native TCP congestion control algorithm and a slower more conservative constant bit rate flow control mode that is activated when congestion is imminent. We show the stability of HSCC via analytical modelling, and demonstrate its effectiveness via simulation and implementation in a small testbed.
【Keywords】: Congestion Control; Hysteresis; AQM; TCP
【Paper Link】 【Pages】:1630-1638
【Authors】: Luigi Vigneri ; Georgios S. Paschos ; Panayotis Mertikopoulos
【Abstract】: Network utility maximization (NUM) is an iconic problem in network traffic management which is at the core of many current and emerging network design paradigms - and, in particular, software-defined networks (SDNs). Thus, given the exponential growth of modern-day networks (in both size and complexity), it is crucial to develop scalable algorithmic tools that are capable of providing efficient solutions in time which is dimension-free, i.e., independent-or nearly-independent-on the size of the system. To do so, we leverage a suite of modified gradient methods known as “mirror descent” and we derive a scalable and efficient algorithm for the NUM problem based on gradient exponentiation. We show that the convergence speed of the proposed algorithm only carries a logarithmic dependence on the size of the network, so it can be implemented reliably and efficiently in massively large networks where traditional gradient methods are prohibitively slow. These theoretical results are sub-sequently validated by extensive numerical simulations showing an improvement of several order of magnitudes over standard gradient methods in large-scale networks.
【Keywords】: Complexity theory; Mirrors; Gradient methods; Convergence; Standards; Resource management; Acceleration
【Paper Link】 【Pages】:1639-1647
【Authors】: Fujie Fan ; Bing Hu ; Kwan L. Yeung
【Abstract】: Multipath networks are widely used in data centers and load balancing is one of the most important technologies to improve their performances. Due to the ever-increasing in data center network size, existing load balancing algorithms face the challenges of efficiency and scalability. In this paper, we propose a new load balancing algorithm for large-scale, multi-tier fat-tree based data center networks. Different from the conventional architectures, a multi-tier fat-tree is divided into multiple routing domains according to the topology, and the routing processes in different domains are independent. The devices outside a routing domain can only access the specific interfaces provided by this domain. It is thus very convenient for deployment and modular upgrade. We also design a distributed and data-driven feedback mechanism, with which the routing decision is based on the global load information. We prove that the new algorithm can achieve perfect load balancing in multipath networks and show that the new algorithm outperforms all other load balancing algorithms in performance.
【Keywords】: Routing; Load management; Data centers; Switches; Bandwidth; Servers; Heuristic algorithms
【Paper Link】 【Pages】:1648-1656
【Authors】: Han Zhang ; Wenzhong Li ; Shaohua Gao ; Xiaoliang Wang ; Baoliu Ye
【Abstract】: The Multipath TCP (MPTCP) protocol, featured by its ability of capacity aggregation across multiple links and connectivity maintenance against single-path failure, has been attracting increasing attention from the industry and academy. Multipath packet scheduling is a unique and fundamental mechanism for the design and implementation of MPTCP, which is responsible for distributing the traffic over multiple subflows. The existing multipath schedulers are facing the challenges of network heterogeneities, comprehensive QoS goals, and dynamic environments, etc. To address these challenges, we propose ReLeS, a Reinforcement Learning based Scheduler for MPTCP. ReLeS uses modern deep reinforcement learning (DRL) techniques to learn a neural network to generate the control policy for packet scheduling. It adopts a comprehensive reward function that takes diverse QoS characteristics into consideration to optimize packet scheduling. To support real-time scheduling, we propose an asynchronous training algorithm that enables parallel execution of packet scheduling, data collecting, and neural network training. We implement ReLeS in the Linux kernel and evaluate it over both emulated and real network conditions. Extensive experiments show that ReLeS significantly outperforms the state-of-the-art schedulers.
【Keywords】: Scheduling algorithms; Training; Delays; Reinforcement learning; Neural networks; Scheduling; Quality of service
【Paper Link】 【Pages】:1657-1665
【Authors】: Zhenzhi Qian ; Yang Yang ; Kannan Srinivasan ; Ness B. Shroff
【Abstract】: FlexRadio, a recent breakthrough in wireless Multi-RF technology, has introduced a new way to unify MIMO and full-duplex into a single framework with a fully flexible design. FlexRadio allows a wireless node to use an arbitrary number of RF chains to support transmission and reception, which makes MIMO and full-duplex subset configurations of FlexRadio. This new architecture has greatly changed the feasibility constraint in wireless networks, which makes the design of high performance MAC layer algorithms even more challenging. First, the RF chain becomes a new resource that needs to be allocated across the network, and the optimal configuration depends not only on the network topology and flow demand, but also on the number of available RF chains at each node. Second, it is not clear how to jointly allocate links and RF chain resources based on the arrival rates and queueing dynamics. In this paper, we introduce a new virtual link model to characterize the feasibility constraint from the perspective of contending RF chain usage. Based on this novel model, a distributed CSMA-like framework is developed to fully leverage the flexibility of RF chain resource allocation.
【Keywords】: Radio frequency; Interference; Wireless communication; Schedules; MIMO communication; Scheduling algorithms; Receivers
【Paper Link】 【Pages】:1666-1674
【Authors】: Nithin S. Ramesan ; François Baccelli
【Abstract】: This paper uses Poisson geometry to define a power control mechanism for large mobile ad hoc networks. It considers a homogeneous Poisson bipole network on the Euclidean plane. Bipoles, which represent transmitter-receiver pairs, adapt their power in a local and distributed way. The common aim of the bipoles is to maximize network wide proportional fairness. The mechanism is based on a heuristic which consists of simplifying the interference field seen by each receiver to its dominant term. This max-interference approximation decomposes the global (and infinite dimensional) optimization problem into a collection of finite problems involving the so called descending chains of the Poisson nearest neighbor graph. In addition, in the Rayleigh fading and interference limited case, the problem further factorizes into a collection of pairwise optimization problems with closed form solution. The properties of this power control mechanism are studied both analytically and by discrete event simulation. Significant performance gains are seen despite these approximations, for the motivating metric and other metrics.
【Keywords】: power control; nearest neighbour graph; infinite optimization; Poisson point process; ad hoc network
【Paper Link】 【Pages】:1675-1683
【Authors】: Mohamed Lamine Lamali ; Simon Lassourreuille ; Stephan Kunne ; Johanne Cohen
【Abstract】: In a network, a tunnel is a part of a path where a protocol is encapsulated in another one. A tunnel starts with an encapsulation and ends with the corresponding decapsulation. Several tunnels can be nested at some stage, forming a protocol stack. Tunneling is very important nowadays and it is involved in several tasks: IPv4/IPv6 transition, VPNs, security (IPsec, onion routing), etc. However, tunnel establishment is mainly performed manually or by script, which present obvious scalability issues. Some works attempt to automate a part of the process (e.g., TSP, ISATAP, etc.). However, the determination of the tunnel(s) endpoints is not fully automated, especially in the case of an arbitrary number of nested tunnels. The lack of routing protocols performing automatic tunneling is due to the unavailability of path computation algorithms taking into account encapsulations and decapsulations. There is a polynomial centralized algorithm to perform the task. However, to the best of our knowledge, no fully distributed path computation algorithm is known. Here, we propose the first fully distributed algorithm for path computation with automatic tunneling, i.e., taking into account encapsulation, decapsulation and conversion of protocols. Our algorithm is a generalization of the distributed Bellman-Ford algorithm, where the distance vector is replaced by a protocol stack vector. This allows to know how to route a packet with some protocol stack. We prove that the messages size of our algorithm is polynomial, even if the shortest path can be of exponential length. We also prove that the algorithm converges after a polynomial number of steps in a synchronized setting. We adapt our algorithm into aproto-protocol for routing with automatic tunneling and we show its efficiency through simulations.
【Keywords】: Tunneling; encapsulation; path computation; routing protocol; distributed algorithms
【Paper Link】 【Pages】:1684-1692
【Authors】: Xi Jin ; Abusayeed Saifullah ; Chenyang Lu ; Peng Zeng
【Abstract】: Wireless sensor-actuator networks enable an efficient and cost-effective approach for industrial sensing and control applications. To satisfy the real-time requirement of such applications, these networks adopt centralized scheduling algorithms to optimize the real-time performance based on global information. Existing centralized algorithms mostly focus on scheduling time-triggered flows. They cannot effectively schedule event-triggered flows due to the dynamics and unpredictability of events. In this paper, we propose three fundamental centralized algorithms that reserve as few resources as possible for event-triggered flows such that the real-time performance of time-triggered flows is not affected. We then analyze their advantages and disadvantages. Based on the analysis, we combine their advantages, including those in terms of their resource requirements, into a centralized algorithm. Finally, we conduct extensive simulations based on both real topologies and random topologies. The simulations indicate that for most test cases the schedulability of our combined algorithm is close to optimal solutions.
【Keywords】: Real-time systems; Schedules; Job shop scheduling; Heuristic algorithms; Network topology; Scheduling algorithms
【Paper Link】 【Pages】:1693-1701
【Authors】: Harshvardhan Tibrewal ; Sravan Patchala ; Manjesh K. Hanawal ; Sumit Jagdish Darak
【Abstract】: We consider an ad hoc network where multiple users access the same set of channels. The channel characteristics are unknown and could be different for each user (heterogeneous). No controller is available to coordinate channel selections by the users, and if multiple users select the same channel, they collide and none of them receive any rate (or reward). For such a completely decentralized network we develop algorithms that aim to achieve optimal network throughput. Due to lack of any direct communication between the users, we allow each user to exchange information by transmitting in a specific pattern and sense such transmissions from others. However, such transmissions and sensing for information exchange do not add to network throughput. For the wideband sensing and narrowband sensing scenarios, we first develop explore-and-commit algorithms that converge to near-optimal allocation with high probability in a small number of rounds. Building on this, we develop an algorithm that gives logarithmic regret. We validate our claims through extensive experiments and show that our algorithms perform significantly better than the state-of-the-art CSM-MAB, dE 3 and dE 3 -TS algorithms.
【Keywords】: Multi-player Multi-armed Bandits; Optimal regret; Pure exploration; Distributed learning
【Paper Link】 【Pages】:1702-1710
【Authors】: Fengjiao Li ; Jia Liu ; Bo Ji
【Abstract】: The multi-armed bandit (MAB) model has been widely adopted for studying many practical optimization problems (network resource allocation, ad placement, crowdsourcing, etc.) with unknown parameters. The goal of the player (i.e., the decision maker) here is to maximize the cumulative reward in the face of uncertainty. However, the basic MAB model neglects several important factors of the system in many realworld applications, where multiple arms (i.e., actions) can be simultaneously played and an arm could sometimes be “sleeping” (i.e., unavailable). Besides reward maximization, ensuring fairness is also a key design concern in practice. To that end, we propose a new Combinatorial Sleeping MAB model with Fairness constraints, called CSMAB-F, aiming to address the aforementioned crucial modeling issues. The objective is now to maximize the reward while satisfying the fairness requirement of a minimum selection fraction for each individual arm. To tackle this new problem, we extend an online learning algorithm, called Upper Confidence Bound (UCB), to deal with a critical tradeoff between exploitation and exploration and employ the virtual queue technique to properly handle the fairness constraints. By carefully integrating these two techniques, we develop a new algorithm, called Learning with Fairness Guarantee (LFG), for the CSMAB-F problem. Further, we rigorously prove that not only LFG is feasibility-optimal, but it also has a time-average regret upper bounded by N/2η + β 1 √mNT log T +β 2 N/T, where N is the total T number of arms, m is the maximum number of arms that can be simultaneously played, T is the time horizon, β 1 and β 2 are constants, and η is a design parameter that we can tune. Finally, we perform extensive simulations to corroborate the effectiveness of the proposed algorithm. Interestingly, the simulation results reveal an important tradeoff between the regret and the speed of convergence to a point satisfying the fairness constraints.
【Keywords】: Stochastic processes; Resource management; Simulation; Wireless communication; Optimization; Crowdsourcing; Face
【Paper Link】 【Pages】:1711-1719
【Authors】: Guangmo Amo Tong ; Ding-Zhu Du
【Abstract】: Online misinformation has been considered as one of the top global risks as it may cause serious consequences such as economic damages and public panic. The misinformation prevention problem aims at generating a positive cascade with appropriate seed nodes in order to compete against the misinformation. In this paper, we study the misinformation prevention problem under the prominent independent cascade model. Due to the #P-hardness in computing influence, the core problem is to design effective sampling methods to estimate the function value. The main contribution of this paper is a novel sampling method. Different from the classic reverse sampling technique which treats all nodes equally and samples the node uniformly, the proposed method proceeds with a hybrid sampling process which is able to attach high weights to the users who are prone to be affected by the misinformation. Consequently, the new sampling method is more powerful in generating effective samples used for computing seed nodes for the positive cascade. Based on the new hybrid sample technique, we design an algorithm offering a (1-1/e-€)-approximation. We experimentally evaluate the proposed method on extensive datasets and show that it significantly outperforms the state-of-the-art solutions.
【Keywords】: misinformation prevention; sampling; social network
【Paper Link】 【Pages】:1720-1728
【Authors】: Nelson Antunes ; Vladas Pipiras ; Gonçalo Jacinto
【Abstract】: In this paper, we revisit the estimation of the size distribution of packet flows in Internet traffic through an inversion approach for several packet sampling schemes which are based on probabilistic sampling (PS). We first study the statistical properties of the previously introduced inversion estimator in its general form and make connections to the singular value decomposition. This motivates the use of a regularization technique in the estimation of the flow size distribution. More specifically, a penalized weighted least square approach is proposed. We compare theoretically the penalized estimator under simplified assumptions against the (non-penalized) inversion approach in order to explain differences in their statistical behaviors. A data study with two real traces shows that the proposed penalized estimator outperforms the inversion estimator for all sampling schemes, corroborating the theoretical analysis. This work reveals that the simplest sampling schemes based on PS, that do not work with small sampling probabilities under the inversion approach, can be used with the penalized approach. Furthermore, the penalized approach allows considering smaller packet sampling rates for all the other sampling schemes.
【Keywords】: Big data; measuring and monitoring Internet traffic; sampling packets; flow size distribution; estimation; inversion problem; regularization methods; penalization
【Paper Link】 【Pages】:1729-1737
【Authors】: Shuai Wang ; Dan Li ; Jinkun Geng ; Yue Gu ; Yang Cheng
【Abstract】: To deal with the increasingly larger input data and model sizes, it has become necessary to scale the training of machine learning models to multiple nodes, even a server cluster, which we call distributed machine learning, or DML. However, DML utilizes more computation power at the cost of high communication overhead, which may limit the overall performance in turn. In this paper, we study the impact of network topology on the DML performance both in theory and in practice. We compare two representative network topologies, namely, Fat-Tree which is widely-used in modern data centers, and BCube, which is a low-cost and server-centric network topology, both running on top of RDMA. The results show that Fat-Tree not only has theoretically higher global synchronization time (GST) than BCube, but its practical GST (by NS-3 based simulation) is also considerably larger than the theoretical one. By analyzing the large-scale simulation traces, we find that the root cause for the gap in Fat-Tree comes from the load imbalance among the multiple parallel paths as well as the inevitable PFC frames, both of which do not appear in BCube. For a cluster of around 250 servers, BCube achieves 53%\sim 70% lower GST than Fat-Tree from the simulation. As a result, we suggest using server-centric network topology such as BCube, instead of the common Fat-Tree network, to build a special-purpose DML cluster, due to its parallel synchronization, RDMA friendliness, natural load balance, as well as low economical cost.
【Keywords】: Synchronization; Network topology; Servers; Computational modeling; Parallel processing; Transport protocols; Data models
【Paper Link】 【Pages】:1738-1746
【Authors】: Matteo Salani ; Cristina Rottondi ; Massimo Tornatore
【Abstract】: Machine Learning (ML) is under intense investigation in optical networks as it promises to lead to automation of a variety of management tasks, as amplifier gain equalization, fault recognition, Quality of Transmission (QoT) estimation, and many others. Though several studies focus on each of these specific tasks, the integration of ML-based estimations inside Routing and Spectrum Assignment (RSA) is still largely unexplored.This paper moves towards such integration. We develop a framework that leverages the probabilistic outputs of a ML-based QoT estimator to define the reach constraints in an Integer Linear Programming (ILP) formulation for RSA in an elastic optical network. In this integrated procedure, the RSA problem is solved iteratively by updating the reach constraints based on the outcome of a QoT estimator, to exclude lightpaths with unacceptable QoT. In our numerical evaluation, the proposed integrated method achieves savings in spectrum occupation up to 30% (around 20% on average) compared to traditional ILP-based RSA approaches with reach constraints based on margined analytical models.
【Keywords】: Machine Learning; Routing and Spectrum Assignment; QoT estimation
【Paper Link】 【Pages】:1747-1755
【Authors】: Nikolaos Liakopoulos ; Georgios S. Paschos ; Thrasyvoulos Spyropoulos
【Abstract】: This paper addresses a fundamental challenge in cloud computing, that of learning an economical yet robust reservation, i.e. reserve just enough resources to avoid both violations and expensive over provisioning. Prediction tools are often inadequate due to observed high variability in CPU and memory workload. We propose a novel model-free approach that has its root in online learning. Specifically, we allow the workload profile to be engineered by an adversary who aims to harm our decisions, and we investigate a class of policies that aim to minimize regret (minimize losses with respect to a baseline static policy that knows the workload sample path). Then we propose a combination of the Lyapunov optimization theory [1] and a linear prediction of the future based on the recent past, used in learning and online optimization problems, see [2]. This enables us to come up with a no regret policy, i.e., a policy whose cost difference to the benchmark and violation constraint residual both grow sublinearly in time, and hence become amortized over the horizon. Our policy has then “no regret and eventually learns the minimum cost reservation subject to a time-average constraint for violations.
【Keywords】: Benchmark testing; Cloud computing; Machine learning; Prediction algorithms; Computational modeling; Optimization; Google
【Paper Link】 【Pages】:1756-1764
【Authors】: Nashid Shahriar ; Sepehr Taeb ; Shihabur Rahman Chowdhury ; Massimo Tornatore ; Raouf Boutaba ; Jeebak Mitra ; Mahdi Hemmati
【Abstract】: Network operators must continuously scale the capacity of their optical backbone networks to keep apace with the proliferation of bandwidth-intensive applications. Today's optical networks are designed to carry large traffic aggregates with coarse-grained resource allocation, and are not adequate for maximizing utilization of the expensive optical substrate. Elastic Optical Network (EON) is an emerging technology that facilitates flexible allocation of fiber spectrum by leveraging finer-grained channel spacing, tunable modulation formats and Forward Error Correction (FEC) overheads, and baud-rate assignment, to right size spectrum allocation to customer needs. Virtual Network Embedding (VNE) over EON has been a recent topic of interest due to its importance for 5G network slicing. However, the problem has not yet been addressed while simultaneously considering the full flexibility offered by an EON. In this paper, we present an optimization model that solves the VNE problem over EON when lightpath configurations can be chosen among a large (and practical) set of combinations of paths, modulation formats, FEC overheads and baud rates. The VNE over EON problem is solved in its splittable version, which significantly increases problem complexity, but is much more likely to return a feasible solution. Given the intractability of the optimal solution, we propose a heuristic to solve larger problem instances. Key results from extensive simulations are: (i) a fully-flexible VNE can save up to 60% spectrum resources compared to that where no flexibility is exploited, and (ii) solutions of our heuristic fall in more than 90% of the cases, within 5% of the optimal solution, while executing several orders of magnitude faster.
【Keywords】: Modulation; Resource management; Substrates; Optical fiber networks; Forward error correction; Bandwidth; Wavelength division multiplexing
【Paper Link】 【Pages】:1765-1773
【Authors】: Xinzhe Fu ; Eytan Modiano
【Abstract】: Traditional network interdiction refers to the problem of an interdictor trying to reduce the throughput of network users by removing network edges. In this paper, we propose a new paradigm for network interdiction that models scenarios, such as stealth DoS attack, where the interdiction is performed through injecting adversarial traffic flows. Under this paradigm, we first study the deterministic flow interdiction problem, where the interdictor has perfect knowledge of the operation of network users. We show that the problem is highly inapproximable on general networks and is NP-hard even when the network is acyclic. We then propose an algorithm that achieves a logarithmic approximation ratio and quasi-polynomial time complexity for acyclic networks through harnessing the submodularity of the problem. Next, we investigate the robust flow interdiction problem, which adopts the robust optimization framework to capture the case where definitive knowledge of the operation of network users is not available. We design an approximation framework that integrates the aforementioned algorithm, yielding a quasi-polynomial time procedure with poly-logarithmic approximation ratio for the more challenging robust flow interdiction. Finally, we evaluate the performance of the proposed algorithms through simulations, showing that they can be efficiently implemented and yield near-optimal solutions.
【Keywords】: Throughput; Approximation algorithms; Computational complexity; Knowledge engineering; Probability distribution; Game theory; Optimization
【Paper Link】 【Pages】:1774-1782
【Authors】: Yilei Lin ; Ting He ; Shiqiang Wang ; Kevin S. Chan ; Stephen Pasteris
【Abstract】: The rapid development of network function virtualization (NFV) enables a communication network to provide in-network services using virtual network functions (VNFs) deployed on general IT hardware. While existing studies on NFV focused on how to provision VNFs from the provider's perspective, little is known about how to validate the provisioned resources from the user's perspective. In this work, we take a first step towards this problem by developing an inference framework designed to “look into” the NFV network. Our framework infers the structure and state of the overlay formed by VNF instances, ingress/egress points of measurement flows, and critical points on their paths (branching/joining points). Our solution only uses external observations such as the required service chains and the end-to-end performance measurements. Besides the novel application scenario, our work also fundamentally advances the state of the art on topology discovery by considering (i) general topologies with general measurement paths, and (ii) information of service chains. Evaluations based on real network topologies show that the proposed solution significantly improves the accuracy over existing solutions, and service chaining information is critical in revealing the structure of the underlying topology.
【Keywords】: Topology; Network topology; Probes; Delays; Loss measurement; Communication networks
【Paper Link】 【Pages】:1783-1791
【Authors】: Tingwei Liu ; John C. S. Lui
【Abstract】: This paper focuses on helping network providers to carry out network capacity planning and sales projection by answering the question: For a given topology and capacity, whether the network can serve current flow demands with high probabilities? We name such probability as “ flow availability” and present the -flow availability estimation (FAVE) problem, which is a generalisation of network connectivity or maximum flow reliability estimations. Realistic networks are often large and dynamic, so flow availabilities cannot be evaluated analytically and simulation is often used. However, naive Monte Carlo (MC) or importance sampling (IS) techniques take an excessive amount of time. To quickly estimate flow availabilities, we utilize the correlations among link and flow failures to figure out the importance of roles played by different links in flow failures, and design three “sequential importance sampling” (SIS) methods which achieve “bounded or even vanishing relative error” with linear computational complexities. When applying to a realistic network, our method reduces the flow availability estimation cost by 900 and 130 times compared with MC and baseline IS methods, respectively. Our method can also facilitate capacity planning by providing better flow availability guarantees, compared with traditional methods.
【Keywords】: Reliability; Capacity planning; Estimation; Network topology; Topology; Bandwidth; Monte Carlo methods
【Paper Link】 【Pages】:1792-1800
【Authors】: Dmitrii Chemodanov ; Prasad Calyam ; Flavio Esposito
【Abstract】: Traditionally, Network Function Virtualization uses Service Function Chaining (SFC) to place service functions and chain them with corresponding flows allocation. With the advent of Edge computing and IoT, a retiable composition of latency-sensitive SFCs is needed to support applications in geo-distributed cloud infrastructures. However, the optimal SFC composition in this case becomes the NP-hard integer multi-commodity-chain flow (MCCF) problem that has no known approximation guarantees. In this paper, we present a novel practical and near optimal SFC composition approach for geo-distributed cloud infrastructures that also admits end-to-end network QoS constraints such as latency, packet loss, etc. Specifically, we propose a novel metapath composite variable approach that reaches 99% optimality on average and takes seconds for practically sized integer MCCF problems of US Tier-1 (~300 nodes) and regional (~600 nodes) infrastructure providers' topologies. To ensure reliability, we compose SFCs with capacity chance-constraints and backup policies. Using trace-driven simulations comprising of challenging disaster-incident conditions, we show that our solution composes twice as many SFCs than the state-of-the-art network virtualization methods.
【Keywords】: Reliability; Quality of service; Cloud computing; Barium; Uncertainty; Computer network reliability; Topology
【Paper Link】 【Pages】:1801-1809
【Authors】: Hanling Yi ; Qiulin Lin ; Minghua Chen
【Abstract】: We consider an increasingly popular demand-response scenario where a user schedules the flexible electric vehicle (EV) charging load in response to real-time electricity prices. The objective is to minimize the total charging cost with user dissatisfaction taken into account. We focus on the online setting where neither accurate prediction nor distribution of future real-time prices is available to the user when making irrevocable charging decision in each time slot. The emphasis on considering user dissatisfaction and achieving optimal competitive ratio differentiates our work from existing ones and makes our study uniquely challenging. Our key contribution is two simple online algorithms with the best possible competitive ratio among all deterministic algorithms. The optimal competitive ratio is upper-bounded by min {√α/p min , p max /p min } and the bound is asymptotically tight with respect to α, where p max and p min are the upper and lower bounds of real-time prices and α ≥ p min captures the consideration of user dissatisfaction. The bounds under small and large values of α suggest the fundamental difference of the problems with and without considering user dissatisfaction. Simulation results based on real-world traces corroborate our theoretical findings and show that the empirical performance of our algorithms can be substantially better than its theoretical worst-case guarantee. Moreover, our algorithms achieve large performance gains as compared to conceivable alternatives. The results also suggest that increasing EV charging rate limit decreases overall cost almost linearly.
【Keywords】: Real-time systems; Electric vehicle charging; Load management; Pricing; Batteries; Trajectory
【Paper Link】 【Pages】:1810-1818
【Authors】: Tao Wu ; Panlong Yang ; Haipeng Dai ; Wanru Xu ; Mingxue Xu
【Abstract】: Wireless Power Transfer (WPT) has emerged into an inspiringly commercial and applicable era to charge devices. Existing studies mainly focus on general charging patterns and metrics while overlooking the collaborated task execution, which incurs charging inefficiency among nodes. In this paper we first advocate the collaborated tasks-driven mobile charging and scheduling to respect the energy requirement diversity. Specially, the mobile charging scheduling strategy is considered to maximize the overall task utility which concerns sensor selection and task cooperation. Unfortunately, solving this problem is non-trivial, because it involves solving two coupling NP-hard problems. In tackling with this difficulty, we construct a surrogate function with specific theoretical analysis of its submodularity and gap property. Then, we approximate the traveling cost to transform the formulated problem into an essentially monotone submodular function optimization subject to a general routing constraint, where we propose a (1-\ 1/e)/4-approximation algorithm. Extensive simulations are conducted and the results show that our algorithm can achieve a near-optimal solution covering at least S4.9% of the optimal result achieved by the OPT algorithm. Furthermore, field experiments in office room and soccer field environment with 10 and 20 sensors are implemented respectively to validate our proposed algorithm.
【Keywords】: Task analysis; Optimization; Resource management; Sensors; Energy consumption; Measurement; Couplings
【Paper Link】 【Pages】:1819-1827
【Authors】: Chi Lin ; Yanhong Zhou ; Fenglong Ma ; Jing Deng ; Lei Wang ; Guowei Wu
【Abstract】: The discovery of Wireless Power Transfer (WPT) technologies makes charging more convenient and reliable. Among all the existing WPT technologies, directional WPT is more efficient and has been successfully applied to supply energy for wireless rechargeable sensor networks (WRSNs). However, the state-of-the-art methods ignore the anisotropic energy receiving property of rechargeable sensors, resulting in energy wastage. In order to address this issue, in this paper, we point out that the received energy of a sensor is not only relative to the distance, but also relative to the angle between the sensor and the charger's orientation in directional WPT. Towards this end, we derive a pragmatic energy transfer model verified by experiments. In particular, we focus on a Minimal chArging Delay (MAD) problem to reduce charging delays. To obtain the optimal solution, we formulate the problem as a linear programming problem. Moreover, we introduce a method of charging power discretization, which significantly reduces the search space and bounds the performance gap to the optimal one with a 1/1-ϵ 2 approximation ratio. Besides, a merging method is introduced for a more practical application scenario. Finally, we demonstrate that our methods outperform the Set Cover baseline method by an average of 34.2% through simulations and experiments.
【Keywords】: Energy exchange; Delays; Wireless sensor networks; Wireless communication; Mathematical model; Receiving antennas; Computational modeling
【Paper Link】 【Pages】:1828-1836
【Authors】: Pengzhan Zhou ; Cong Wang ; Yuanyuan Yang
【Abstract】: Energy supply remains to be a major bottleneck in Wireless Sensor Networks (WSNs). A self-sustainable network operates without battery replacement. Recent efforts employ multi-source energy harvesting to power sensors with ambient energy. Meanwhile, wireless charging is considered in WSNs as a reliable energy source. It motivates us to integrate both fields of research to build a self-sustainable network and guarantee operation under any weather condition. We propose a three-step solution to optimize this new framework. We first solve the Sensor Composition Problem (SCP) to derive the percentage of different types of sensors. Then we enable self-sustainability by bringing energy harvesting storage to the field for charging the Mobile Charger (MC). Next, we propose a 3-factor approximation algorithm to schedule sensor charging and energy replenishment of MC. Our extensive simulation results demonstrate significant improvement of network lifetime and reduction of network cost. The network lifetime can be extended at least three times compared with traditional approaches and the charging capability of MC increases at least 100%.
【Keywords】: Multi-source energy harvesting; wireless charging; wireless sensor networks; energy self-sustainable
【Paper Link】 【Pages】:1837-1845
【Authors】: Weichao Mao ; Zhenzhe Zheng ; Fan Wu
【Abstract】: Data is becoming an important kind of commercial good, and many online data marketplaces are set up to facilitate the trading of data. However, most existing data market models and the corresponding pricing mechanisms are simple, and fail to capture the unique economic properties of data. In this paper, we first characterize the distinctive features of IoT data as a commodity, and then present a new IoT data market model from an information design perspective. We further propose a family of data pricing mechanisms for revenue maximization under different market settings. Our MSimple mechanism extracts full surplus from the market for the model with one type of buyer. When multiple types of buyers coexist, our MGeneral mechanism optimally solves the problem of revenue maximization by formulating it as a polynomial size convex program. For a more practical setting where buyers have bounded rationality, we design MPractical mechanism with a tight logarithmic approximation ratio. We evaluate our pricing mechanisms on a real-world ambient sound dataset. Evaluation results show our pricing mechanisms achieve good performance and approach the revenue upper bound.
【Keywords】: Pricing; Internet of Things; Cost accounting; Data models; Biological system modeling; Random variables; Estimation
【Paper Link】 【Pages】:1846-1854
【Authors】: Zhiyuan Wang ; Lin Gao ; Jianwei Huang ; Biying Shou
【Abstract】: Mobile Network Operators (MNOs) are providing more flexible wireless data services to attract subscribers and increase revenues. For example, the data trading market enables user-flexibility by allowing users to sell leftover data to or buy extra data from each other. The rollover mechanism enables time-flexibility by allowing a user to utilize his own leftover data from the previous month in the current month. In this paper, we investigate the economic viability of offering the data trading market together with the rollover mechanism, to gain a deeper understanding of the interrelationship between the user-flexibility and the time-flexibility. We formulate the interactions between the MNO and mobile users as a multi-slot dynamic game. Specifically, in each time slot (e.g., every day), the MNO first determines the selling and buying prices with the goal of revenue maximization, then each user decides his trading action (by solving a dynamic programming problem) to maximize his long-term payoff. Due to the availability of monthly data rollover, a user's daily trading decision corresponds to a dynamic programming problem with two time scales (i.e., day-to-day and month-to-month). Our analysis reveals an optimal trading policy with a target interval structure, specified by a buy-up-to threshold and a sell-down-to threshold in each time slot. Moreover, we show that the rollover mechanism makes users sell less and buy more data given the same trading prices, hence it increases the total demand while decreasing the total supply in the data trading market. Finally, numerical results based on real-world data unveil that the time-flexible rollover mechanism plays a positive role in the user-flexible data trading market, increasing the MNO's revenue by 25% and all users' payoff by 17% on average.
【Keywords】: Rollover; Pricing; Wireless communication; Economics; Dynamic programming; Games; Telecommunications
【Paper Link】 【Pages】:1855-1863
【Authors】: Xuehe Wang ; Lingjie Duan
【Abstract】: Due to its agility and mobility, the unmanned aerial vehicle (UAV) is a promising technology to provide high-quality mobile services (e.g., fast Internet access, edge computing, and local caching) to ground users. Major Internet Service Providers (ISPs) want to enable UAV-provided services (UPS) to improve and enrich the current mobile services for additional profit. This profit-maximization problem is not easy as the UAV has limited energy storage and needs to fly closely to serve users, requiring an optimal energy allocation for balancing both hovering time and service capacity. When hovering in a hotspot, how the UAV should dynamically price its capacity-limited UPS according to randomly arriving users with private service valuations is another question. We prove that the UAV should ask for a higher price if the leftover hovering time is longer or its service capacity is smaller, and its expected profit approaches to that under complete user information if the hovering time is sufficiently large. As the hotspot's user occurrence rate increases, a shorter hovering time or a larger service capacity should be allocated. Finally, when the UAV faces multiple hotspot candidates with different user occurrence rates and flying distances, we prove that it is optimal to deploy the UAV to serve a single hotspot. With multiple UAVs, however, this result can be reversed with UAVs' forking deployment to different hotspots.
【Keywords】: Uninterruptible power systems; Pricing; Unmanned aerial vehicles; Cost accounting; Resource management; Economics; Dynamic scheduling
【Paper Link】 【Pages】:1864-1872
【Authors】: Behrouz Jedari ; Mario Di Francesco
【Abstract】: Content providers (CPs) are keen to cache their popular contents in small-cell base stations (SBSs) provided by mobile network operators (MNOs). In fact, they can serve the requests of their subscribers with low latency, thereby increasing user satisfaction. Employing advanced video encoding techniques, such as scalable video coding (SVC), improves the utilization of wireless resources and the network infrastructure. However, the cache trading policies for SVC videos in multi-provider networks have not been studied yet. In this article, we design a commercial trading system in which multiple CPs, each owning SVC videos, compete over renting the cache in multiple SBSs provided by an MNO. We model cache trading between the MNO and CPs as a social welfare maximization problem, whose objective is to maximize the trading profit while achieving the economic properties of rationality, balanced budget, and truthfulness. Since optimal allocation of random-size caches to multiple CPs is NP-hard, we devise an iterative trading mechanism based on double auction called DOCAT, wherein the cache of SBSs is segmented and traded in multiple rounds. In each round of the auction, the MNO and CPs price the cache segments based on their profit, then submit their asking and buying bids, respectively. Next, a many-to-one matching algorithm is run to efficiently find perfect matches between the cache segments and winning CPs. Numerical results based on a real video dataset show that DOCAT increases the social welfare of the system while satisfying the desired economic properties.
【Keywords】: Heterogeneous networks; edge caching; scalable video coding; network economics; game theory; auction
【Paper Link】 【Pages】:1873-1881
【Authors】: Rui Ning ; Cong Wang ; Chunsheng Xin ; Jiang Li ; Liuwan Zhu ; Hongyi Wu
【Abstract】: This work proposes an innovative approach, named CapJack, to detect in-browser malicious cryptocurrency mining activities by using the latest CapsNet technology. To the best of our knowledge, this is the first work to introduce CapsNet to the field of malware detection through system behavioral analysis. It is particularly effective to detect malicious miners under multitasking environments where multiple applications run simultaneously. Experimental data show appealing performance of CapJack, with a detection rate of as high as 87% instantly and 99% within a window of 11 seconds.
【Keywords】: Malware; Browsers; Cryptocurrency; Computer hacking; Feature extraction; Task analysis
【Paper Link】 【Pages】:1882-1890
【Authors】: Nengwen Zhao ; Jing Zhu ; Rong Liu ; Dapeng Liu ; Ming Zhang ; Dan Pei
【Abstract】: KPI (Key Performance Indicator) anomaly detection is critical for Internet-based services to ensure the quality and reliability. However, existing algorithms' performance in reality is far from satisfying due to the lack of sufficient KPI anomaly data to help train and evaluate these algorithms. In this paper, we argue that labeling overhead is the main hurdle to obtain such datasets. Thus, we novelly propose a semi-automatic labelling tool called Label-Less, which minimizes the labeling overhead in order to enable an ImageNet-like large-scale KPI anomaly dataset with high-quality ground truth. One novel technique in Label-Less is robust and rapid anomaly similarity search, which saves operators from scanning and checking the long KPIs back and forth for abnormal patterns or label consistency. In our evaluations using 30 real KPIs from a large Internet company, our anomaly similarity search achieves the best F-score of 0.95 on average, and a real-time per-KPI response time (less than 0.5 second). Overall, the feedback from deployment in practice shows that Label-Less can reduce operators' labeling overhead by more than 90%.
【Keywords】: Anomaly detection; Labeling; Key performance indicator; Time series analysis; Time factors; Companies
【Paper Link】 【Pages】:1891-1899
【Authors】: Wenxiao Chen ; Haowen Xu ; Zeyan Li ; Dan Pei ; Jie Chen ; Honglin Qiao ; Yang Feng ; Zhaogang Wang
【Abstract】: To ensure the reliability of the Internet-based application services, KPIs (Key Performance Monitors) are closely monitored in real time and the anomalies presented in the KPIs must be discovered in time. While anomaly detection for the seasonal smooth service-level KPIs (e.g., number of transactions per minute) have been solved reasonably well in the literature, the intricate KPIs at the machine level (e.g., the number of I/O requests on a server monitored per second) has been little studied. These intricate KPIs are prevalent and important, but exhibit non-Gaussian noises and complex data distribution that are hard to model. In this paper, we propose an adversarial training method in the Bayesian network based on partition analysis with solid theoretical proof. Based on it, we propose the first unsupervised anomaly detection algorithmBuzz for intricate KPIs with high performance. Its best F-scores on the data from a global Internet company range from 0.92 to 0.99, significantly outperforming a state-of-art VAE-based unsupervised approach without adversarial training and a state-of-art supervised approach.
【Keywords】: Training; Anomaly detection; Microsoft Windows; Monitoring; Bayes methods; Neural networks; Solids
【Paper Link】 【Pages】:1900-1908
【Authors】: Xiaocan Li ; Kun Xie ; Xin Wang ; Gaogang Xie ; Jigang Wen ; Guangxing Zhang ; Zheng Qin
【Abstract】: Traffic anomaly detection is critical for advanced Internet management. Existing detection algorithms usually work off-line and cannot timely detect anomalies. They also suffer from high cost for storage and computation. Although online and accurate traffic anomaly detection is very important, it very difficult to achieve. We propose to utilize tensor model to well exploit the multi-dimensional information hidden in the traffic data for more accurate online Internet anomaly detection. We decouple the tensor recovery problem to iteratively solve two sub problems, a tensor factorization sub-problem and an anomaly detection sub-problem. To reduce the high cost for computation and storage involved in tensor factorization, we propose two lightweight techniques to effectively derive factor matrices of tensor in the current window and iteration, taking advantage of tensor decomposition results of the previous window and iteration. We have done extensive experiments using two real traffic traces to compare with three tensor based algorithms and three matrix based algorithms. The experiment results demonstrate that our online anomaly detection algorithm can achieve the same anomaly detection accuracy as that of the best offline tensor based algorithm, but at 6100 times faster speed and with very low storage cost.
【Keywords】: Anomaly detection; Monitoring; Matrix decomposition; Microsoft Windows; Principal component analysis; Data models
【Paper Link】 【Pages】:1909-1917
【Authors】: Deepak Nadig ; Byrav Ramamurthy ; Brian Bockelman ; David Swanson
【Abstract】: In this paper, we propose an application-aware intelligent load balancing system for high-throughput, distributed computing, and data-intensive science workflows. We leverage emerging deep learning techniques for time-series modeling to develop an application-aware predictive analytics system for accurately forecasting GridFTP connection loads. Our solution integrates with a major U.S. CMS Tier-2 site; we use a real dataset representing 670 million GridFTP transfer connections measured over 18 months to drive our predictive analytics solution. First, we perform extensive analysis on this dataset and use the connection loads as an example to study the temporal dependencies between various user-roles and workflow memberships. We use the analysis to motivate the design of a gated recurrent unit (GRU) based deep recurrent neural network (RNN) for modeling long-term temporal dependencies and predicting connection loads. We develop a novel application-aware, predictive and intelligent load balancer, APRIL, that effectively integrates application metadata and load forecast information to maximize server utilization. We conduct extensive experiments to evaluate the performance of our deep RNN predictive analytics system and compare it with other approaches such as ARIMA and multi-layer perceptron (MLP) predictors. The results show that our forecasting model, depending on the user-role, performs between 5.88%-92.6% better than the alternatives. We also demonstrate the effectiveness of APRIL by comparing it with the load balancing capabilities of an existing production Linux Virtual Server (LVS) cluster. Our approach improves server utilization, on an average, between 0.5 to 11 times, when compared with its LVS counterpart.
【Keywords】: Load modeling; Predictive models; Deep learning; Correlation; Servers; Big Data; Load management
【Paper Link】 【Pages】:1918-1926
【Authors】: Jiao Zhang ; Zenan Wang ; Chunyi Peng ; Linquan Zhang ; Tao Huang ; Yunjie Liu
【Abstract】: Network Function Virtualization (NFV) turns a sequence of network functions on hardwares into a service chain of virtual network functions (VNFs) provisioned on virtual machines or containers. However, the chain of VNFs may suffer from interruption as long as one VNF fails due to software faults or hardware malfunctions. A common approach to ensuring high availability is to provide backup nodes for primary VNFs. However, existing work on allocating backup nodes have not considered the heterogeneous resource demands of different VNFs. In this paper, we formalize the resource-aware backup allocation problem, which aims to minimize the backup resource consumption while meeting the overall availability demand. To this end, we prove the NP-hardness of this problem and propose the RABA-CDDE algorithm based on differential evolution to solve it. Besides, to reduce the computation overhead of RABA-CDDE, a greedy algorithm is proposed. Our extensive evaluation shows that the proposed algorithms can reduce the resource consumption by about 15% and 35% respectively compared to the state-of-art solutions in dedicated and shared protection scenarios.
【Keywords】: Network function virtualization; service function chain; backup allocation; fault tolerance
【Paper Link】 【Pages】:1927-1935
【Authors】: Avirup Saha ; Niloy Ganguly ; Sandip Chakraborty ; Abir De
【Abstract】: Accurate modeling of network traffic has a wide variety of applications. In this paper, we propose Network Transmission Point Process (NTPP), a probabilistic deep machinery that models the traffic characteristics of hosts on a network and effectively forecasts the network traffic patterns, such as load spikes. Existing stochastic models relied on the network traffic being self-similar in nature, thus failing to account for traffic anomalies. These anomalies, such as short-term traffic bursts, are very prevalent in certain modern-day traffic conditions, e.g. datacenter traffic, thus refuting the assumption of self-similarity. Our model is robust to such anomalies since it effectively leverages the self-exciting nature of the bursty network traffic using a temporal point process model.On seven diverse datasets collected from the fields of cyberdefense exercises (CDX), website access logs, datacenter traffic, and P2P traffic, NTPP offers a substantial performance boost in predicting network traffic characteristics against several baselines, ranging from forecasting the network traffic volume to detecting traffic spikes. We also demonstrate an application of our model to a caching scenario, showing that it can be used to effectively lower the cache miss rate.
【Keywords】: time series/data streams; network host behavior modeling; temporal point processes
【Paper Link】 【Pages】:1936-1944
【Authors】: Shiyou Qian ; Weichao Mao ; Jian Cao ; Frederic Le Mouel ; Minglu Li
【Abstract】: When facing fluctuating workloads, can the performance of matching algorithms in a content-based publish/subscribe system be adjusted to adapt to the workloads? In this paper, we explore the idea of endowing matching algorithms with adaptability. The prerequisite for adaptability is to enable the matching algorithm to possess the ability to dynamically and quantitatively adjust its performance. We propose PSAM, a Predicate-Skipping Adjustment Mechanism that realizes dynamic performance adjustment by smoothly switching between exact matching and approximate matching, following the strategy of trading off matching precision in favor of matching speed. The PSAM mechanism is integrated into an existing matching algorithm, resulting in a performance-adjustable matching algorithm called Ada-Rein. To collaborate with Ada-Rein, we design PADA, a Performance Adjustment Decision Algorithm that is able to make proper performance adjustment plans in the presence of fluctuating workloads. The effectiveness of Ada-Rein and PADA is evaluated through a series of experiments based on both synthetic data and real-world stock traces. Experiment results show that adjusting the performance of Ada-Rein at the price of a small false positive rate, less than 0.1%, can shorten event latency by almost 2.1 times, which well demonstrates the feasibility of our exploratory idea.
【Keywords】: Pub/sub; workload; adaptability; adjustability
【Paper Link】 【Pages】:1945-1953
【Authors】: Seyed Ali Hassani ; Karthick Parashar ; André Bourdoux ; Barend van Liempd ; Sofie Pollin
【Abstract】: The use of in-band full duplex (IBFD) is a promising improvement over classical TDD or FDD communication schemes. To enable IBFD radios, the electrical balance duplexer (EBD) has been proposed to suppress the direct self-interference (SI) at the RF stage. The remaining SI is typically assumed to be canceled further in the digital domain. In this paper, we show that the non-zero Doppler frequencies can be extracted from the residual SI, giving information about the speed of objects in the environment. As a result, an IBFD radio can be seen as a monostatic Doppler radar which is affected by the communication signal. This paper presents a detailed performance analysis of the different sources of interference affecting the Doppler radar. The performance is also evaluated using a radar-enhanced IBFD prototype consisting of a SDR module and an EBD designed to achieve up to 55 dB Tx-Rx isolation in the 1.74 GHz RF band. A measurable Doppler component is created by moving a 15 dBsm cone at known velocities at 0. 5-1.3 m from the prototype. For an EBD SI rejection of 45 dB, speeds in the range of 200 to 800 mm/s are detected with high accuracy.
【Keywords】: In-band full duplex; self-interference cancellation; Doppler radar; mono-static wireless sensing
【Paper Link】 【Pages】:1954-1962
【Authors】: Yongce Chen ; Shaoran Li ; Chengzhang Li ; Y. Thomas Hou ; Brian Jalaian
【Abstract】: Degree-of-Freedom (DoF) based models have been widely used to study MIMO networks. To cancel interference, the number of DoFs used in the state-of-the-art DoF models is solely based on the number of interfering data streams. However, by decomposing an interference into the eigenspace, we find that signal strengths varies significantly in different directions for the same interference link. In this paper, we exploited the difference in interference signal strength in the eigenspace and differentiate strong and weak interference signals via their singular values. By introducing a concept of effective rank threshold, we propose to use DoFs only to cancel strong interference in the eigenspace based on this threshold while treating weak interference signals as noise in throughput calculation. We explore a fundamental tradeoff between network throughput and effective rank threshold. Using simulation results on MU-MIMO networks, we show that network throughput under optimal rank threshold setting is significantly higher than that under existing DoF IC models. To ensure feasibility at the PHY layer, we present an algorithm that can find Tx and Rx weights at each node that can offer our desired DoF allocation.
【Keywords】: Interference; Throughput; Integrated circuit modeling; Correlation; MIMO communication; Resource management
【Paper Link】 【Pages】:1963-1971
【Authors】: Sulei Wang ; Zhe Chen ; Yuedong Xu ; Qiben Yan ; Chongbin Xu ; Xin Wang
【Abstract】: Multiuser MIMO (MU-MIMO) empowers access points (APs) with multiple antennas to transmit multiple data streams concurrently to users by exploiting spatial multiplexing. In MU-MIMO, users need to estimate channel state information (CSI) and report it to APs, thus opening a backdoor to attackers who may forge CSI to eavesdrop the content of victims. In this paper, we explore the eavesdropping attack in a novel and practical context in which CSI forgery entangles MU-MIMO user selection in a many-users regime. The attacker hopes to optimize both the eavesdropping opportunity of being selected with the victim and the corresponding decoding quality. We propose new attack and defense mechanisms: (1) USE Attack that enables attackers to achieve near optimal eavesdropping opportunity and high decoding quality through constructing orthogonal CSI against victims followed by stepwise refinements; (2) AngleSec that exploits channel reciprocity for attacker detection without any modification to legacy CSI feedback in which CSI forgery induces a mismatching of downlink and uplink angular spectra at the AP. We implement and evaluate USE Attack and AngleSec in a software defined radio platform WARPv3. Extensive experiments manifest that USE Attack significantly improves the overall eaves-dropping quality compared with state-of-the-art counterparts and AngleSec is able to detect CSI forgery attackers almost for sure.
【Keywords】: Eavesdropping; Forgery; Array signal processing; MIMO communication; Transmitting antennas; Interference; Multiplexing
【Paper Link】 【Pages】:1972-1980
【Authors】: Nan Cen ; Neil Dave ; Emrecan Demirors ; Zhangyu Guan ; Tommaso Melodia
【Abstract】: Indoor Visible Light Communications (VLC) are a promising technology to alleviate the looming spectrum crunch crisis in traditional RF spectrum bands. This article studies how to provide throughput-optimal WiFi-like downlink access to users in indoor visible light networks through a set of centrally-controlled and partially interfering light emitting diodes (LEDs). To reduce the effect of interference among users created by the partial overlap of each LED's field of view, we propose LiBeam, a cooperative beamforming scheme, based on forming multiple LED clusters. Each cluster then serves a subset of users by jointly determining the user-LED association strategies and the beamforming vectors of the LEDs. The paper first proposes a mathematical model of the cooperative beamforming problem, presented as maximizing the sum throughput of all VLC users. Then, we solve the resulting mixed integer nonlinear nonconvex programming (MINCoP) problem by designing a globally optimal solution algorithm based on a combination of branch and bound framework as well as convex relaxation techniques. We then design for the first time a large programmable visible light networking testbed based on USRP X310 software-defined radios, and experimentally demonstrate the effectiveness of the proposed joint beamforming and association algorithm through extensive experiments. Performance evaluation results indicate that over 95% utility gain can be achieved compared to suboptimal network control strategies.
【Keywords】: Visible Light Networking; Cooperative Beamforming; Throughput Optimization; Programmable Testbed.
【Paper Link】 【Pages】:1981-1989
【Authors】: Yi Zhao ; Meina Qiao ; Haiyang Wang ; Rui Zhang ; Dan Wang ; Ke Xu ; Qi Tan
【Abstract】: Due to the explosive growth of social network services, friendship inference has been widely adopted by Online Social Service Providers (OSSPs) for friend recommendation. The conventional techniques, however, have limitations in accuracy or scalability to handle such a large yet sparse multi-source data. For example, the OSSPs will be required to manually give the order in which the various information is applied. This unavoidably reduces the applicability of existing friend recommendation systems. To address this issue, we propose a Two-stage Deep learning framework for Friendship Inference (TDFI). This approach can utilize multi-source information simultaneously with low complexity. In particular, we apply an Extended Adjacency Matrix (EAM) to represent the multi-source information. We then adopt an improved Deep AutoEncoder Network (iDAEN) to extract the fused feature vector for each user. The TDFI framework also provides an improved Deep Siamese Network (iDSN) to measure user similarity from iDAEN. Finally, we evaluate the effectiveness and robustness of TDFI on three large-scale real-world datasets. It shows that TDFI can effectively handle the sparse multi-source data while providing better accuracy for friend recommendation.
【Keywords】: Feature extraction; Complexity theory; Deep learning; Scalability; Computer science; Facebook
【Paper Link】 【Pages】:1990-1998
【Authors】: Abhisek Dash ; Animesh Mukherjee ; Saptarshi Ghosh
【Abstract】: To improve the experience of consumers, all social media, commerce and entertainment sites deploy Recommendation Systems (RSs) that aim to help users locate interesting content. These RSs are black-boxes - the way a chunk of information is filtered out and served to a user from a large information base is mostly opaque. No one except the parent company generally has access to the entire information required for auditing these systems - neither the details of the algorithm nor the user-item interactions are ever made publicly available for third-party auditors. Hence auditing RSs remains an important challenge, especially with the recent concerns about how RSs are affecting the views of the society at large with new technical jargons like “echo chambers”, “confirmation biases”, “filter bubbles” etc. in place. Many prior works have evaluated different properties of RSs such as diversity, novelty, etc. However, most of these have focused on evaluating static snapshots of RSs. Today, auditors are not only interested in these static evaluations on a snapshot of the system, but also interested in how these systems are affecting the society in course of time. In this work, we propose a novel network-centric framework which is not only able to quantify various static properties of RSs, but also is able to quantify dynamic properties such as how likely RSs are to lead to polarization or segregation of information among their users. We apply the framework to several popular movie RSs to demonstrate its utility.
【Keywords】: Recommendation Systems; Recommendation Networks; auditing; diversity; polarization; segregation of information
【Paper Link】 【Pages】:1999-2007
【Authors】: Guangchi Liu ; Chenyu Li ; Qing Yang
【Abstract】: Assessing the trust between users in a trust social network (TSN) isa critical issue in many applications, e.g., film recommendation,spam detection, and online lending. Despite of various trust assessment methods, a challenge remaining to existing solutions is how to accurately determine the factors that affect trust propagation and trust fusion within a TSN. To address this challenge, we propose the NeuralWalk algorithm to cope with trust factor estimation and trust relation prediction problems simultaneously. NeuralWalk employs a neural network, named WalkNet, to model single-hop trust propagation and fusion in a TSN. By treating original trust relations in a TSN as labeled samples, WalkNet is able to learn the parameters that will be used for trust computation/assessment. Unlike traditional solutions, WalkNet is able to accurately predict unknown trust relations in an inductive manner. Based on WalkNet, NeuralWalk iteratively assesses the unknown multi-hop trust relations among users via the obtained single-hop trust computation rules. Experiments on two real-world TSN datasets indicate that NeuralWalk significantly outperforms the state-of-the-art solutions.
【Keywords】: Trust Assessment; Sociat Network; Neurat Network; Machine Learning
【Paper Link】 【Pages】:2008-2016
【Authors】: Jinyuan Jia ; Neil Zhenqiang Gong
【Abstract】: Estimating frequencies of certain items among a population is a basic step in data analytics, which enables more advanced data analytics (e.g., heavy hitter identification, frequent pattern mining), client software optimization, and detecting unwanted or malicious hijacking of user settings in browsers. Frequency estimation and heavy hitter identification with local differential privacy (LDP) protect user privacy as well as the data collector. Existing LDP algorithms cannot leverage 1) prior knowledge about the noise in the estimated item frequencies and 2) prior knowledge about the true item frequencies. As a result, they achieve suboptimal performance in practice. In this work, we aim to design LDP algorithms that can leverage such prior knowledge. Specifically, we design Calibrate to incorporate the prior knowledge via statistical inference. Calibrate can be appended to an existing LDP algorithm to reduce its estimation errors. We model the prior knowledge about the noise and the true item frequencies as two probability distributions, respectively. Given the two probability distributions and an estimated frequency of an item produced by an existing LDP algorithm, our Calibrate computes the conditional probability distribution of the item's frequency and uses the mean of the conditional probability distribution as the calibrated frequency for the item. It is challenging to estimate the two probability distributions due to data sparsity. We address the challenge via integrating techniques from statistics and machine learning. Our empirical results on two real-world datasets show that Calibrate significantly outperforms state-of-the-art LDP algorithms for frequency estimation and heavy hitter identification.
【Keywords】: Frequency estimation; Probability distribution; Differential privacy; Inference algorithms; Aggregates; Data analysis; Browsers
【Paper Link】 【Pages】:2017-2025
【Authors】: Tong Yang ; Jiaqi Xu ; Xilai Liu ; Peng Liu ; Lun Wang ; Jun Bi ; Xiaoming Li
【Abstract】: Sketch is a compact data structure for network measurements. To achieve fast speed, it needs to be held in the on-chip memory (SRAM), which is very small. To enable the sketch fit into the on-chip memory, the product of counter size and number of counters must be below a certain limit. If we use small counters, e.g., 8 bits, some counters will overflow. If we use large counters, e.g., 16 bits per counter, the total number of counters will be small, each counter will be shared by more flows, leading to poor accuracy. To address this issue, we propose a generic technique: self-adaptive counters (SA Counter). When the value of the counter is small, it works as a normal counter. When the value of the counter is large, we increment it using a predefined probability, so as to represent a large value. Moreover, in SA Counter, the probability decreases when the value increases. This technique can significantly improve the accuracy of sketches. To verify the effectiveness of SA Counter, we apply SA Counter to three typical sketches, and conduct extensive experiments on one real dataset and one synthetic dataset. Experimental results show that, compared with the state-of-the-art, sketches using SA Counter improve the accuracy by up to 13.6 times.
【Keywords】: Arrays; Mice; Hash functions; Random access memory; System-on-chip; Size measurement
【Paper Link】 【Pages】:2026-2034
【Authors】: Lu Tang ; Qun Huang ; Patrick P. C. Lee
【Abstract】: Fast detection of heavy flows (e.g., heavy hitters and heavy changers) in massive network traffic is challenging due to the stringent requirements of fast packet processing and limited resource availability. Invertible sketches are summary data structures that can recover heavy flows with small memory footprints and bounded errors, yet existing invertible sketches incur high memory access overhead that leads to performance degradation. We present MV-Sketch, a fast and compact invertible sketch that supports heavy flow detection with small and static memory allocation. MV-Sketch tracks candidate heavy flows inside the sketch data structure via the idea of majority voting, such that it incurs small memory access overhead in both update and query operations, while achieving high detection accuracy. We present theoretical analysis on the memory usage, performance, and accuracy of MV-Sketch. Trace-driven evaluation shows that MVSketch achieves higher accuracy than existing invertible sketches, with up to 3.38× throughput gain. We also show how to boost the performance of MV-Sketch with SIMD instructions.
【Keywords】: Resource management; Memory management; Arrays; Dynamic scheduling; Throughput; Monitoring
【Paper Link】 【Pages】:2035-2043
【Authors】: Yaniv Sadeh ; Ori Rottenstreich ; Arye Barkan ; Yossi Kanizo ; Haim Kaplan
【Abstract】: Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacity of each server or path implies the distribution by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power hungry and are often also required for other tasks such as classification and routing. For splitting a universe of 2 W addresses into k pieces of particular sizes, we give a simple algorithm that computes an optimal representation in Õ(Wk) time. Furthermore, we prove that a recently published load balancer, called Niagara, which also runs in Õ(W k) time is in fact optimal. That is, both our algorithm and Niagara produce the smallest possible TCAM that splits the traffic exactly to the required pieces, where the only previously known algorithm for computing optimal exact representation has running time exponential in k. Finally, we rely on our optimal Õ(Wk) runtime algorithm to investigate through extensive experiments the amount of TCAM memory required to represent traffic splitting in typical scenarios.
【Keywords】: Law; Memory management; Heuristic algorithms; Switches; Partitioning algorithms; Google
【Paper Link】 【Pages】:2044-2052
【Authors】: Vitalii Demianiuk ; Kirill Kogan ; Sergey I. Nikolenko
【Abstract】: Performing exact computations can require significant resources. Approximate computing allows to alleviate resource constraints, sacrificing the accuracy of results. In this work, we consider a generalization of the classical packet classification problem. Our major contribution is to introduce various representations for approximate packet classifiers with controlled accuracy and optimization techniques to reduce classifier sizes exploiting this new level of flexibility. We validate our theoretical results with a comprehensive evaluation study.
【Keywords】: Gold; Silver; Complexity theory; Approximate computing; Optimization methods
【Paper Link】 【Pages】:2053-2061
【Authors】: Zhibo Wang ; Jingxin Li ; Jiahui Hu ; Ju Ren ; Zhetao Li ; Yanjun Li
【Abstract】: Reverse auction-based incentive mechanisms have been commonly proposed to stimulate mobile users to participate in crowdsensing, where users submit bids to the platform to compete for tasks. Recent works pointed out that bid is a private information which can reveal sensitive information of users (e.g., location privacy), and proposed bid-preserving mechanisms with differential privacy against inference attack. However, all these mechanisms rely on a trusted platform, and would fail in bid protection completely when the platform is untrusted (e.g., honest-but-curious). In this paper, we focus on the bid protection problem in mobile crowdsensing with an untrusted platform, and propose a novel privacy-preserving incentive mechanism to protect users' true bids against the honest-but-curious platform while minimizing the social cost of winner selection. To this end, instead of uploading the true bid to the platform, a differentially private bid obfuscation function is designed with the exponential mechanism, which helps each user to obfuscate bids locally and submit obfuscated task-bid pairs to the platform. The winner selection problem with the obfuscated task-bid pairs is formulated as an integer linear programming problem and proved to be NP-hard. We consider the optimization problem at two different scenarios, and propose a solution based on Hungarian method for single measurement and a greedy solution for multiple measurements, respectively. The proposed incentive mechanism is proved to satisfy ε-differential privacy, individual rationality and γ-truthfulness. The extensive experiments on a real-world data set demonstrate the effectiveness of the proposed mechanism against the untrusted platform.
【Keywords】: Task analysis; Privacy; Differential privacy; Sensors; Mobile handsets; Cryptography; Integer linear programming
【Paper Link】 【Pages】:2062-2070
【Authors】: Qian Wang ; Xiu Lin ; Man Zhou ; Yanjiao Chen ; Cong Wang ; Qi Li ; Xiangyang Luo
【Abstract】: Voice biometrics is widely adopted for identity authentication in mobile devices. However, voice authentication is vulnerable to spoofing attacks, where an adversary may deceive the voice authentication system with pre-recorded or synthesized samples from the legitimate user or by impersonating the speaking style of the targeted user. In this paper, we design and implement VoicePop, a robust software-only anti-spoofing system on smartphones. VoicePop leverages the pop noise, which is produced by the user breathing while speaking close to the microphone. The pop noise is delicate and subject to user diversity, making it hard to record by replay attacks beyond a certain distance and to imitate precisely by impersonators. We design a novel pop noise detection scheme to pinpoint pop noises at the phonemic level, based on which we establish individually unique relationship between phonemes and pop noises to identify legitimate users and defend against spoofing attacks. Our experimental results with 18 participants and three types of smartphones show that VoicePop achieves over 93.5% detection accuracy at around 5.4% equal error rate. VoicePop requires no additional hardware but only the built-in microphones in virtually all smartphones, which can be readily integrated in existing voice authentication systems for mobile devices.
【Keywords】: Authentication; Smart phones; Microphones; Feature extraction; Tongue; Mouth; Law
【Paper Link】 【Pages】:2071-2079
【Authors】: Chen Wang ; Jian Liu ; Xiaonan Guo ; Yan Wang ; Yingying Chen
【Abstract】: Mobile payment has drawn considerable attention due to its convenience of paying via personal mobile devices at anytime and anywhere, and passcodes (i.e., PINs or patterns) are the first choice of most consumers to authorize the payment. This paper demonstrates a serious security breach and aims to raise the awareness of the public that the passcodes for authorizing transactions in mobile payments can be leaked by exploiting the embedded sensors in wearable devices (e.g., smartwatches). We present a passcode inference system, WristSpy, which examines to what extent the user's PIN/pattern during the mobile payment could be revealed from a single wrist-worn wearable device under different passcode input scenarios involving either two hands or a single hand. In particular, WristSpy has the capability to accurately reconstruct fine-grained hand movement trajectories and infer PINs/patterns when mobile and wearable devices are on two hands through building a Euclidean distance-based model and developing a training-free parallel PIN/pattern inference algorithm. When both devices are on the same single hand, a highly challenging case, WristSpy extracts multi-dimensional features by capturing the dynamics of minute hand vibrations and performs machine-learning based classification to identify PIN entries. Extensive experiments with 15 volunteers and 1600 passcode inputs demonstrate that an adversary is able to recover a user's PIN/pattern with up to 92% success rate within 5 tries under various input scenarios.
【Keywords】: Online banking; Mobile handsets; Pins; Wearable sensors; Trajectory; Feature extraction
【Paper Link】 【Pages】:2080-2088
【Authors】: Xinyan Zhou ; Xiaoyu Ji ; Chen Yan ; Jiangyi Deng ; Wenyuan Xu
【Abstract】: With the increasing prevalence of mobile devices, face-to-face device-to-device (D2D) communication has been applied to a variety of daily scenarios such as mobile payment and short distance file transfer. In D2D communications, a critical security problem is verifying the legitimacy of devices when they share no secrets in advance. Previous research addressed the problem with device authentication and pairing schemes based on user intervention or exploiting physical properties of the radio or acoustic channels. However, a remaining challenge is to secure face-to-face D2D communication even in the middle of a crowd, within which an attacker may hide. In this paper, we present Nhuth, a nonlinearity-enhanced, location-sensitive authentication mechanism for such communication. Especially, we target at the secure authentication within a limited range such as 20 cm, which is the common case for face-to-face scenarios. Nhuth contains averification scheme based on the nonlinear distortion of speaker-microphone systems and a location-based-validation model. The verification scheme guarantees device authentication consistency by extracting acoustic nonlinearity patterns (ANP) while the validation model ensures device legitimacy by measuring the time difference of arrival (TDOA) at two microphones. We analyze the security of Nhuth theoretically and evaluate its performance experimentally. Results show that Nhuth can verify the device legitimacy in the presence of nearby attackers.
【Keywords】: Microphones; Authentication; Nonlinear distortion; Device-to-device communication; Harmonic analysis; Acoustics
【Paper Link】 【Pages】:2089-2097
【Authors】: Hao Fu ; Zizhan Zheng ; Sencun Zhu ; Prasant Mohapatra
【Abstract】: Recent studies observe that app foreground is the most striking component that influences the access control decisions in mobile platform, as users tend to deny permission requests lacking visible evidence. However, none of the existing permission models provides a systematic approach that can automatically answer the question: Is the resource access indicated by app foreground? In this work, we present the design, implementation, and evaluation of COSMOS, a context-aware mediation system that bridges the semantic gap between foreground interaction and background access, in order to protect system integrity and user privacy. Specifically, COSMOS learns from a large set of apps with similar functionalities and user interfaces to construct generic models that detect the outliers at runtime. It can be further customized to satisfy specific user privacy preference by continuously evolving with user decisions. Experiments show that COSMOS achieves both high precision and high recall in detecting malicious requests. We also demonstrate the effectiveness of COSMOS in capturing specific user preferences using the decisions collected from 24 users and illustrate that COSMOS can be easily deployed on smartphones as a real-time guard with a very low performance overhead.
【Keywords】: Windows; Runtime; User interfaces; Layout; Static analysis; Access control; Privacy
【Paper Link】 【Pages】:2098-2106
【Authors】: Haoran Yu ; Ermin Wei ; Randall A. Berry
【Abstract】: Conventionally, mobile network operators charge users for data plan subscriptions. To create new revenue streams, some operators now also incentivize users to watch ads with data rewards and collect payments from advertisers. In this work, we study two such rewarding schemes: a Subscription-Aware Rewarding (SAR) scheme and a Subscription-Unaware Rewarding (SUR) scheme. Under the SAR scheme, only the subscribers of the operators' existing data plans are eligible for the rewards; under the SUR scheme, all users are eligible for the rewards (e.g., the users who do not subscribe to the data plans can still get SIM cards and receive data rewards by watching ads). We model the interactions among a capacity-constrained operator, users, and advertisers by a two-stage Stackelberg game, and characterize their equilibrium strategies under both the SAR and SUR schemes. We show that the SAR scheme can lead to more subscriptions and a higher operator revenue from the data market, while the SUR scheme can lead to better ad viewership and a higher operator revenue from the ad market. We provide some counter-intuitive insights for the design of data rewards. For example, the operator's optimal choice between the two schemes is sensitive to the users' data consumption utility function. When each user has a logarithmic utility function, the operator should apply the SUR scheme (i.e., reward both subscribers and nonsubscribers) if and only if it has a small network capacity.
【Keywords】: Advertising; Games; Cost accounting; Companies; Ecosystems; Wireless fidelity
【Paper Link】 【Pages】:2107-2115
【Authors】: Lianjie Shi ; Xin Wang ; Richard T. B. Ma
【Abstract】: Increasing popularity of delay-sensitive and data-intensive online services such as video streaming has placed stronger requirements on the quality of content delivery. By negotiating premium peering agreement with an Internet service provider (ISP), a content provider (CP) is able to improve its service quality, which is beneficial for attracting end-users and increasing profits. Meanwhile, by deploying cache on its content delivery route with a proper caching mechanism, transit traffic is effectively reduced and bandwidth is saved, hence the CP can also achieve better service quality. In this paper, we study how a CP determines an optimal strategy that maximizes its utility, if both premium peering and caching are available from an ISP. We present the conditions that the CP's optimal strategy should comply with, and observe that the optimal quantity of purchasing one capacity is positively correlated to that of the other. We also find that the CP's optimal strategy indicates that the CP would purchase a moderate amount of capacity, or the maximum amount available in some case, to maximize its utility.
【Keywords】: Delays; Throughput; Streaming media; Aggregates; Bandwidth; Quality of service; Network neutrality
【Paper Link】 【Pages】:2116-2124
【Authors】: Jingya Zhou ; Jianxi Fan
【Abstract】: Nowadays people tend to create accounts with multiple social networks (SNs) to enjoy a variety of social network services. User identity linkage (UIL) aims to identify those multiple accounts belonging to a same person. UIL is of great importance to user behavior understanding and prediction, information dissemination, viral marketing, wellness diagnosis, etc. Most of existing solutions typically rely on the embedding of either user's attributes or behaviors into a latent vector space, and establish anchor link based on vector distance. However, these efforts still face challenges originated from the heterogeneity of SNs, incompleteness of user information and lack of enough known anchor links. In this paper, we investigate the UIL problem by presenting a translation-modeling approach-TransLink. It jointly embeds both users and interactive behaviors of various SNs into a unified low-dimensional representation space according to a set of known anchor links. More specifically, we primarily study three typical SNs, e.g, Twitter, Foursquare and Instagram. Before embedding, we abstract schemas of three SNs and extract interaction metapaths for each SN. By doing this we can efficiently address the first two challenges. Furthermore, iterative linkage can ensure linkage performance by using a very small set of known anchor links. Experiment results on two real-world datasets demonstrate the superiority of TransLink over the state-of-the-art approaches.
【Keywords】: User identity linkage; Social networks; Network alignment; Translating embeddings
【Paper Link】 【Pages】:2125-2133
【Authors】: Xiuzhen Guo ; Yuan He ; Xiaolong Zheng ; Zihao Yu ; Yunhao Liu
【Abstract】: Cross-Technology Communication (CTC) is an emerging technique that enables direct communication across different wireless technologies. The state-of-the-art works in this area propose physical-level CTC, in which the transmitters emulate signals that follow the receiver's standard. Physical-level CTC means considerable processing complexity at the transmitter, which doesn't apply to the communication from a low-end transmitter to a high-end receiver, e.g. from ZigBee to WiFi. This paper presents transmitter-transparent cross-technology communication, which leaves the processing complexity solely at the receiver side and therefore makes a critical advance toward bidirectional high-throughput CTC. We implement our proposal as LEGO-Fi, the communication from ZigBee to WiFi. The key technique inside is cross-demapping, which stems from two key technical insights: (1) A ZigBee packet leaves distinguishable features when passing the WiFi modules. (2) Compared to ZigBee's simple encoding and modulation schemes, the rich processing capacity of WiFi offers extra flexibility to process a ZigBee packet. The evaluation results show that LEGO-Fi achieves a throughput of 213.6Kbps, which is respectively 13000× and 1200× faster than FreeBee and ZigFi, the two existing ZigBee-to-WiFi CTC approaches.
【Keywords】: Zigbee; Wireless fidelity; Receivers; Synchronization; Throughput; Wireless communication; Standards
【Paper Link】 【Pages】:2134-2142
【Authors】: Panagiotis Vamvakas ; Eirini-Eleni Tsiropoulou ; Symeon Papavassiliou
【Abstract】: In this paper a novel dynamic spectrum management scheme for 5G Non Orthogonal Multiple Access (NOMA) wireless networks is proposed, where users are offered the option to transmit via licensed and unlicensed bands. Users are enabled to determine the optimal allocation of their transmission power in each one of the bands, while the unlicensed band is treated as a Common Pool Resource (CPR) - being non-excludable and rivalrous - which may collapse due to over-exploitation. Towards providing a pragmatic modeling approach for decision making under a realistic setting of probabilistic uncertainty, while properly capturing user risk perceptions, we model the corresponding optimization problem under the principles of Prospect Theory, removing the common assumption that subjects are behaving as neutral utility maximizers, a concept that does not reflect user risk behavior peculiarities. The corresponding problem is formulated as a CPR game, while the existence and uniqueness of its Pure Nash Equilibrium point are proven, and a user centric distributed algorithm is devised that obtains the corresponding solution. Detailed evaluation results are presented, highlighting the operation and superiority of the proposed framework against conventional Expected Utility Theory based approaches, while providing useful insights about user optimal decisions under realistic behaviors.
【Keywords】: Licensed & Unlicensed bands; Prospect Theory; Game Theory; Resource Allocation; Common Pool Resources
【Paper Link】 【Pages】:2143-2151
【Authors】: Jie Wang ; Wenye Wang ; Cliff Wang
【Abstract】: Spectrum monitoring, run-time usage acquisition, and regulation enforcement, in general can be referred to as spectrum activity surveillance (SAS). It is essential to dynamic spectrum access with a two-fold impact: it is a primitive mechanism to continuously scan spectrum usage for system optimization purposes; it is also a prime widget to obtain spectrum footprints of legitimate users, and record misuse by unauthorized or malicious users. Seemingly trivial, large-scale SAS in wireless overlay networks is actually an open yet challenging problem. This is because on one hand, such a system is time and energy-sensitive and hence unlikely (or not necessary) to implement in practice, due to constraints of radio spectrum license and system deployment. On the other hand, it is not clear how to characterize the efficacy and performance of spectrum monitoring strategies in surveillance over a large geographical region, and detection of spectrum culprits, that is, unauthorized spectrum occupants. To address such a challenge, we consider SAS in a 3-dimensional space that is composed of spectrum, time, and geographical region, and then formulate monitoring strategies as graph walks by accounting for the locality of spectrum activities. In particular, our approach transforms the SAS problem from a globally collective activity to a set of localized, distributed actions, and strategy objectives from qualitative attributes to quantitative measures. We find that randomized strategies with m monitors can achieve a sweep-coverage over a space of n assignment points in Θ(n/m ln n) time, and detect an oblivious or adversarial spectrum culprit in Θ(n/m) time for SAS systems.
【Keywords】: Synthetic aperture sonar; Surveillance; Wireless communication; Wireless sensor networks; Measurement; Analytical models
【Paper Link】 【Pages】:2152-2160
【Authors】: Francesco Restuccia ; Tommaso Melodia
【Abstract】: The explosion of 5G networks and the Internet of Things will result in an exceptionally crowded RF environment, where techniques such as spectrum sharing and dynamic spectrum access will become essential components of the wireless communication process. In this vision, wireless devices must be able to (i) learn to autonomously extract knowledge from the spectrum on-the-fly; and (ii) react in real time to the inferred spectrum knowledge by appropriately changing communication parameters, including frequency band, symbol modulation, coding rate, among others. Traditional CPU-based machine learning suffers from high latency, and requires application-specific and computationally-intensive feature extraction/selection algorithms. Conversely, deep learning allows the analysis of massive amount of unprocessed spectrum data without ad-hoc feature extraction. So far, deep learning has been used for offline wireless spectrum analysis only. Therefore, additional research is needed to design systems that bring deep learning algorithms directly on the device's hardware and tightly intertwined with the RF components to enable real-time spectrum-driven decision-making at the physical layer. In this paper, we present RFLearn, the first system enabling spectrum knowledge extraction from unprocessed I/Q samples by deep learning directly in the RF loop. RFLearn provides (i) a complete hardware/software architecture where the CPU, radio transceiver and learning/actuation circuits are tightly connected for maximum performance; and (ii) a learning circuit design framework where the latency vs. hardware resource consumption trade-off can explored. We implement and evaluate the performance of RFLearn on custom software-defined radio built on a system-on-chip (SoC) ZYNQ-7000 device mounting AD9361 radio transceivers and VERT2450 antennas. We showcase the capabilities of RFLearn by applying it to solving the fundamental problems of modulation and OFDM parameter recognition. Experimental results reveal that RFLearn decreases latency and power by about 17x and 15x with respect to a software-based solution, with a comparatively low hardware resource consumption.
【Keywords】: Radio frequency; Deep learning; Computer architecture; Hardware; Central Processing Unit; Wireless communication; Real-time systems
【Paper Link】 【Pages】:2161-2169
【Authors】: Alexandros Milolidakis ; Romain Fontugne ; Xenofontas Dimitropoulos
【Abstract】: Colocation facilities and Internet eXchange Points (IXPs) provide neutral places for concurrent networks to daily exchange terabytes of data traffic. Although very reliable, these facilities are not immune to failure and may experience difficulties that can have significant impacts on exchanged traffic. In this paper we devise a methodology to identify collocation facilities in traceroute data and to monitor delay and routing patterns between facilities. We also present an anomaly detection technique to report abnormal traffic changes usually due to facilities outages. We evaluate this method with eight months of traceroute data from the RIPE Atlas measurement platform and manually inspect the most prominent events, that are: an IXP outage, a DDoS attack, and a power failure in a facility. These case studies validate the benefits of the proposed system to detect real world outages from traceroute data. We also investigate the impact of anomalies at the metropolitan-level and identify outages that span across up to eight facilities.
【Keywords】: IP networks; Delays; Internet; Monitoring; Routing; Switches; Servers
【Paper Link】 【Pages】:2170-2178
【Authors】: Kun Xie ; Jiazheng Tian ; Xin Wang ; Gaogang Xie ; Jigang Wen ; Dafang Zhang
【Abstract】: Finding top- k elephant flows is a critical task in network measurement, with applications such as congestion control, anomaly detection, and traffic engineering. Traditional top- k flow detection problem focuses on using a small amount of memory to measure the total number of packets or bytes of each flow. Instead, we study a challenging problem of inferring the top- k elephant flows in a practical system with incomplete measurement data as a result of sub-sampling for scalability or data missing. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top- k elephant flows. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top- k flow inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of top- k elephant flows with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. Extensive experiments using two real traces demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar data inference accuracy using significantly smaller time and storage space.
【Keywords】: Top- k elephant flow inference; Tensor completion
【Paper Link】 【Pages】:2179-2187
【Authors】: Yang Li ; Jiachen Sun ; Wenguang Huang ; Xiaohua Tian
【Abstract】: In this paper, we propose a tree modeling-based data mining method to detect anomalies from crowdsourced network data. We design an algorithm to extract potential network anomalies from decision trees. Moreover, we propose a criteria to evaluate the severity of anomaly in terms of three factors: standard deviation, weight sum and impurity decrease. To enhance generalization performance, we randomly generate sample subspace of the original dataset as the input for each subtree and compact detected anomalies from all subtrees. We carry out experiments based on the crowdsourced network measurement dataset containing five million samples, which contains round trip time (RTT) from more than 5,000 users. Experiments show that the proposed method can effectively detect high-latency network anomalies. Moreover, the random forest-based approach can achieve an improvement of approximately 25% of generalization performance compared to the single decision tree approach.
【Keywords】: Network Anomaly Detection; Crowdsourcing; Decision Tree; Random Forest
【Paper Link】 【Pages】:2188-2196
【Authors】: Batiste Le Bars ; Argyris Kalogeratos
【Abstract】: In this paper we consider the task of detecting abnormal communication volume occurring at node-level in communication networks. The signal of the communication activity is modeled by means of a clique stream: each occurring communication event is instantaneous, and activates an undirected subgraph spanning over a set of equally participating nodes. We present a probabilistic framework to model and assess the communication volume observed at any single node. Specifically, we employ non-parametric regression to learn the probability that a node takes part in a certain event knowing the set of other nodes that are involved. On the top of that, we present a concentration inequality around the estimated volume of events in which a node could participate, which in turn allows us to build an efficient and interpretable anomaly scoring function. Finally, the superior performance of the proposed approach is empirically demonstrated in real-world sensor network data, as well as using synthetic communication activity that is in accordance with that latter setting.
【Keywords】: Anomaly detection; probabilistic models; communication networks; sensor networks; internet-of-things; link streams; graph signals
【Paper Link】 【Pages】:2197-2205
【Authors】: YiHao Jia ; Aleksandar Kuzmanovic
【Abstract】: Anomalies are a ubiquitous and inevitable phenomenon associated with a complex and large-scale system such as the Internet. While measuring and analyzing network anomalies is as old as the Internet itself, comprehensively detecting anomalies at a global scale is a challenging task that requires a significant measurement infrastructure. In this paper, we demonstrate that the production Content Distribution Networks (CDNs), and their pervasive network infrastructure, could be effectively utilized to detect Internet anomalies. Our approach avoids direct network measurements and instead relies on “abnormal” spatial and temporal CDN replica shifts to indirectly sense anomalies. We measure replica shifts for five CDNs (Google, Amazon, Akamai, Fastly, and Incapsula) for two months. Contrary to our expectations, we find that (i) Google's and Amazon's CDNs, which are characterized by rich connectivity and infrastructure, are not best suited for our method because they effectively mask anomalies; (ii) Akamai is the most “sophisticated” of all evaluated CDNs, yet again not best suited to detect anomalies because it reacts exceptionally to much smaller network performance variations; (iii) Fastly's and Incapsula's replica shifts strongly correlate with network anomalies, making them viable anomaly predictors.
【Keywords】: anomalies prediction; CDN; DNS mapping
【Paper Link】 【Pages】:2206-2214
【Authors】: Zhaoyu Gao ; Arun Venkataramani
【Abstract】: Managed DNS (MDNS) services today excel at providing a simple and cost-effective way to outsource domain management and ensure rapid lookup times for geo-distributed users. The intense focus on optimizing lookup performance coupled with DNS' inherent expectations of weak consistency has had unfortunate side effects: updates are inexplicably slow and MDNS providers pay scant attention to consistency correctness. We conduct an empirical measurement-driven study of 8 top-tier managed DNS providers and find that inter-nameserver update propagation delays commonly take tens of seconds with little improvement over the last several years. Client-perceived inconsistency is rampant with roughly a third of end-users being vulnerable to TTL abuse by local DNS resolvers. Furthermore, we find that 6 of the 8 MDNS providers violate monotonic read consistency under frequent updates and at least one large MDNS provider appears to violate even eventual consistency.
【Keywords】: Extraterrestrial measurements; Servers; Propagation delay; Portals; IP networks; Delays; Google
【Paper Link】 【Pages】:2215-2223
【Authors】: Kun Xie ; Xiaocan Li ; Xin Wang ; Gaogang Xie ; Dongliang Xie ; Zhenyu Li ; Jigang Wen ; Zulong Diao
【Abstract】: With the proliferation of smartphones, a novel sensing paradigm called Mobile Crowd Sensing (MCS) has emerged very recently. However, the attacks and faults in MCS cause a serious false data problem. Observing the intrinsic low dimensionality of general monitoring data and the sparsity of false data, false data detection can be performed based on the separation of normal data and anomalies. Although the existing separation algorithm based on Direct Robust Matrix Factorization (DRMF) is proven to be effective, requiring iteratively performing Singular Value Decomposition (SVD) for low-rank matrix approximation would result in a prohibitively high accumulated computation cost when the data matrix is large. In this work, we observe the quick false data location feature from our empirical study of DRMF, based on which we propose an intelligent Light weight Low Rank and False Matrix Separation algorithm (LightLRFMS) that can reuse the previous result of the matrix decomposition to deduce the one for the current iteration step. Our algorithm can largely speed up the whole iteration process. From a theoretical perspective, we validate that LightLRFMS only requires one round of SVD computation and thus has very low computation cost. We have done extensive experiments using a PM 2.5 air condition trace and a road traffic trace. Our results demonstrate that LightLRFMS can achieve very good false data detection performance with the same highest detection accuracy as DRMF but with up to 10 times faster speed thanks to its lower computation cost.
【Keywords】: Matrix Separation; False Data Detection; Mobile Crowd Sensing
【Paper Link】 【Pages】:2224-2232
【Authors】: Antoine Brochard ; Bartlomiej Blaszczyszyn ; Stéphane Mallat ; Sixin Zhang
【Abstract】: Motivated by the prediction of cell loads in cellular networks, we formulate the following new, fundamental problem of statistical learning of geometric marks of point processes: An unknown marking function, depending on the geometry of point patterns, produces characteristics (marks) of the points. One aims at learning this function from the examples of marked point patterns in order to predict the marks of new point patterns. To approximate (interpolate) the marking function, in our baseline approach, we build a statistical regression model of the marks with respect to some local point distance representation. In a more advanced approach, we use a global data representation via the scattering moments of random measures, which build informative and stable to deformations data representation, already proven useful in image analysis and related application domains. In this case, the regression of the scattering moments of the marked point patterns with respect to the non-marked ones is combined with the numerical solution of the inverse problem, where the marks are recovered from the estimated scattering moments. Considering some simple, generic marks, often appearing in the modeling of wireless networks, such as the shot-noise values, nearest neighbour distance, and some characteristics of the Voronoi cells, we show that the scattering moments can capture similar geometry information as the baseline approach, and can reach even better performance, especially for non-local marking functions. Our results motivate further development of statistical learning tools for stochastic geometry and analysis of wireless networks, in particular to predict cell loads in cellular networks from the locations of base stations and traffic demand.
【Keywords】: Scattering; Base stations; Geometry; Statistical learning; Wireless networks; Cellular networks; Load modeling
【Paper Link】 【Pages】:2233-2241
【Authors】: Leyla Roohi ; Benjamin I. P. Rubinstein ; Vanessa Teague
【Abstract】: We describe a novel protocol for computing the egocentric betweenness centrality of a node when relevant edge information is spread between two mutually distrusting parties such as two telecommunications providers. While each node belongs to one network or the other, its ego network might include edges unknown to its network provider. We develop a protocol of differentially-private mechanisms to hide each network's internal edge structure from the other; and contribute a new two-stage stratified sampler for exponential improvement to time and space efficiency. Empirical results on several open graph data sets demonstrate practical relative error rates while delivering strong privacy guarantees, such as 16% error on a Facebook data set.
【Keywords】: Differential Privacy; Betweenness Centrality
【Paper Link】 【Pages】:2242-2250
【Authors】: Tianchong Gao ; Feng Li
【Abstract】: Online social networks (OSNs) routinely share and analyze user data. This requires protection of sensitive user information. Researchers have proposed several techniques to anonymize the data of OSNs. Some differential-privacy techniques claim to preserve graph utility under certain graph metrics, as well as guarantee strict privacy. However, each graph utility metric reveals the whole graph in specific aspects.We employ persistent homology to give a comprehensive description of the graph utility in OSNs. This paper proposes a novel anonymization scheme, called PHDP, which preserves persistent homology and satisfies differential privacy. To strengthen privacy protection, we add exponential noise to the adjacency matrix of the network and find the number of adding/deleting edges. To maintain persistent homology, we collect edges along persistent structures and avoid perturbation on these edges. Our regeneration algorithms balance persistent homology with differential privacy, publishing an anonymized graph with a guarantee of both. Evaluation result show that the PHDP-anonymized graph achieves high graph utility, both in graph metrics and application metrics.
【Keywords】: Online social network; privacy and utility; differential privacy; persistent homology
【Paper Link】 【Pages】:2251-2259
【Authors】: Anuj Nayak ; Seyyedali Hosseinalipour ; Huaiyu Dai
【Abstract】: The goal of opinion maximization is to maximize the positive view towards a product, an ideology or any entity among the individuals in social networks. So far, opinion maximization is mainly studied as finding a set of influential nodes for fast content dissemination in a social network. In this paper, we propose a novel approach to solve the problem, where opinion maximization is achieved through efficient information spreading. In our model, multiple sources inject information continuously into the network, while the regular nodes with heterogeneous social learning abilities spread the information to their acquaintances through gossip mechanism. One of the sources employs smart information spreading and the rest spread information randomly. We model the social interactions and evolution of opinions as a dynamic Bayesian network (DBN), using which the opinion maximization is formulated as a sequential decision problem. Since the problem is intractable, we develop multiple variants of centralized and decentralized algorithms to obtain approximate solutions. Through simulations in synthetic and real-world networks, we demonstrate two key results: 1) the proposed methods perform better than random spreading by a large margin, and 2) even though the smart source (that spreads the desired content) is unfavorably located in the network, it can outperform the contending random sources located at favorable positions.
【Keywords】: Social network; Opinion maximization; Dynamic Bayesian network; Q-learning; Decentralized algorithm
【Paper Link】 【Pages】:2260-2268
【Authors】: Jiaqi Liu ; Qin Zhang ; Luoyi Fu ; Xinbing Wang ; Songwu Lu
【Abstract】: Many practical applications have observed knowledge evolution, i.e., continuous born of new knowledge, with its formation influenced by the structure of historical knowledge. This observation gives rise to evolving knowledge graphs whose structure temporally grows over time. However, both the modal characterization and the algorithmic implementation of evolving knowledge graphs remain unexplored. To this end, we propose EvolveKG, a framework that reveals cross-time knowledge interaction with desirable performance of storage and computation. The novelty of EvolveKG lies in Derivative Graph - a static weighted snapshot of evolution at a certain time. Particularly, each weight quantifies knowledge effectiveness with a temporarily decaying function of consistency and attenuation, two proposed factors depicting whether or not the effectiveness of a fact fades away with time. Thanks to the cross-time interaction, EvolveKG allows future knowledge prediction by virtue of the influence from the historical ones. Empirically tested under two real datasets, the superiority of EvolveKG is confirmed via its prediction accuracy.
【Keywords】: Attenuation; Knowledge discovery; Information retrieval; Semantics; Lifting equipment; Prediction algorithms; Computational complexity
【Paper Link】 【Pages】:2269-2277
【Authors】: Konstantinos Psychas ; Javad Ghaderi
【Abstract】: We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource requirements (e.g. memory requirements) arrive over time and must be served by a cluster of servers, each with a finite resource capacity. To improve throughput and delay, the scheduler can pack as many jobs as possible in the servers subject to their capacity constraints. Motivated by the ever-increasing complexity of workloads in shared clusters, we consider a setting where the jobs' resource requirements belong to a very large number of diverse types or, in the extreme, even infinitely many types, e.g. when resource requirements are drawn from an unknown distribution over a continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) dimensional setting. We first characterize a fundamental limit on the maximum throughput in such setting, and then develop oblivious scheduling algorithms that have tow complexity and can achieve at least 1/2 and 2/3 of the maximum throughput, without the knowledge of traffic or resource requirement distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms.
【Keywords】: Scheduling Algorithms; Stability; Queues; Knap-sack; Data Centers
【Paper Link】 【Pages】:2278-2286
【Authors】: Frédéric Giroire ; Nicolas Huin ; Andrea Tomassilli ; Stéphane Pérennes
【Abstract】: We consider the placement of jobs inside a data center. Traditionally, this is done by a task orchestrator without taking into account network constraints. According to recent studies, network transfers represent up to 50% of the completion time of classical jobs. Thus, network resources must be considered when placing jobs in a data center. In this paper, we propose a new scheduling framework, introducing network tasks that need to be executed on network machines alongside traditional (CPU) tasks. The model takes into account the competition between communications for the network resources, which is not considered in the formerly proposed scheduling models with communication. Network transfers inside a data center can be easily modeled in our framework. As we show, classical algorithms do not efficiently handle a limited amount of network bandwidth. We thus propose new provably efficient algorithms with the goal of minimizing the makespan in this framework. We show their efficiency and the importance of taking into consideration network capacity through extensive simulations on workflows built from Google data center traces.
【Keywords】: Task analysis; Data centers; Delays; Approximation algorithms; Servers; Data models; Bandwidth
【Paper Link】 【Pages】:2287-2295
【Authors】: Jiaying Meng ; Haisheng Tan ; Chao Xu ; Wanli Cao ; Liuyan Liu ; Bojie Li
【Abstract】: In this paper, we study online deadline-aware task dispatching and scheduling in edge computing. We jointly consider management of the networking bandwidth and computing resources to meet the maximum number of deadlines. We propose an online algorithm Dedas, which greedily schedules newly arriving tasks and considers whether to replace some existing tasks in order to make the new deadlines satisfied. We derive a non-trivial competitive ratio theoretically, and our analysis is asymptotically tight. We then build DeEdge, an edge computing testbed installed with typical latency-sensitive applications such as IoT sensor monitoring and face matching. Besides, we adopt a real-world data trace from the Google cluster for large-scale emulations. Extensive testbed experiments and simulations demonstrate that the deadline miss ratio of Dedas is stable for online tasks, which is reduced by up to 60% compared with state-of-the-art methods. Moreover, Dedas performs well in minimizing the average task completion time.
【Keywords】: Task analysis; Servers; Bandwidth; Processor scheduling; Dispatching; Computational modeling; Optimal scheduling
【Paper Link】 【Pages】:2296-2304
【Authors】: Tung-Wei Kuo
【Abstract】: We consider a transmission scheduling problem in which multiple systems receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall age of information. We call this problem the Min-Age problem. This problem is first studied by He et at. [IEEE Trans. Inform. Theory, 2018], who identified several special cases where the problem can be solved optimally in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant r ≥ 1, every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-Age problem. Second, we give a randomized 2.733-approximation algorithm and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-Age problem is NP-hard.
【Keywords】: Schedules; Receivers; Time division multiple access; Approximation algorithms; Heuristic algorithms; Linear programming; Scheduling algorithms
【Paper Link】 【Pages】:2305-2313
【Authors】: Peshal Nayak ; Santosh Pandey ; Edward W. Knightly
【Abstract】: Internet speed tests assess end-to-end network performance by measuring throughput for 10s of MB of TCP uploads and downloads. While such tests provide valuable insights into network health, they are of little use to network administrators since (1) the results are only available on the client that performs the test and (2) the tests can saturate the network, increasing load and worsening performance for other clients. In this paper, we present virtual speed test, a measurement based framework that enables an AP to estimate speed test results for any of its associated clients without any special-purpose probing, with zero end-user co-operation and purely based on passively observable parameters at the AP. We implemented virtual speed test using commodity hardware, deployed it in office and residential environments, and conducted measurements spanning multiple days having different network loads and channel conditions. Overall, virtual speed test has mean estimation error less than 6% compared to ground truth speed tests, yet with zero overhead, and outcomes available at the AP.
【Keywords】: Servers; Throughput; Wireless LAN; Interference; Downlink; Phase measurement
【Paper Link】 【Pages】:2314-2322
【Authors】: Soumya Basu ; Sanjay Shakkottai
【Abstract】:
We consider the wireless scheduling problem of jointly activating/de-activating base-stations and (opportunistically) scheduling from among the active base stations. Such systems are of increasing relevance in emerging wireless networks with dense overlapping coverage, where it suffices for only a (time-varying) subset of the base-stations to be active at any given time to satisfy traffic demands. In addition to queue stability (to ensure that traffic demands are met), we focus on optimizing for costs arising due to activating base-stations (switching base-station state between active/inactive), and maintaining activation (these costs arising due to energy consumption).We propose two algorithms-LASS-Static and LASS-Dynamic (LASS: Learning Aided Switching and Scheduling), both of which are explore-exploit policies for base-station switching and channel scheduling. In our setting, the switching action consists of two key decisions: when to switch, and what base-station activation state to switch to. Both LASS-Static and LASS-Dynamic determine the resulting switching state (i.e. what to switch to as well as the schedule using current queue-lengths and (estimated) channel states. The crucial difference is inwhen to switch'-LASS-Static determines these statically (motivated by an epsilon-greedy bandit approach), whereas LASS-Dynamic does so using current queue-lengths (thus correlating switching times, switching states and schedules). For either algorithm, existing Lyapunov-based techniques fail to establish stability, as the switching state dynamics correlate the base-station activation decisions with the channel evolution over time. Using novel drift based techniques, in this paper we derive stability, and provide explicit bounds on the expected cost and queue lengths for both algorithms. Furthermore, we show that adaptively selecting switching times in LASS-Dynamic results in an improved upper-tail of queue lengths compared to LASS-Static.
【Keywords】: Switching cost; Constrained Max-weight
【Paper Link】 【Pages】:2323-2331
【Authors】: Xiaoyu Wang ; Haipeng Dai ; He Huang ; Yunhuai Liu ; Guihai Chen ; Wanchun Dou
【Abstract】: In this paper, we deal with the problem of Robust schedUling for wireLess charger nEtworks (RULE), i.e., given a number of rechargeable devices, each of which may drift within a certain range, and a number of directional chargers with fixed positions and adjustable orientations distributed on a 2D plane, determining the orientations of the wireless chargers to maximize the overall expected charging utility while taking the charging power jittering into consideration. To address the problem, we first model the charging power as a random variable, and apply area discretization technique to divide the charging area into several subareas to approximate the charging power as the same random variable in each subarea and bound the approximation error. Then, we discretize the orientations of chargers to deal with the unlimited searching space of orientations with performance bound. Finally, by proving the submodularity of the problem after the above transformations, we propose an algorithm that achieves (1/2-ε)-approximation ratio. We conduct both simulation and field experiments, and the results show that our algorithm can perform better than other comparison algorithms by 103.25% on average.
【Keywords】: Wireless communication; Random variables; Wireless sensor networks; Approximation algorithms; Two dimensional displays; Approximation error; Vehicle dynamics
【Paper Link】 【Pages】:2332-2340
【Authors】: Silvio Mandelli ; Matthew Andrews ; Sem C. Borst ; Siegfried Klein
【Abstract】: Network slicing provides a key functionality in emerging 5G networks, and offers flexibility in creating customized virtual networks and supporting different services on a common physical infrastructure. This capability critically relies on a MAC scheduler to deliver performance targets in terms of aggregate rates or resource shares for the various slices. A crucial challenge is to enforce such guarantees and performance isolation while allowing flexible sharing to avoid resource fragmentation and fully harness channel variations. In the present paper we propose a MAC scheduler which meets these objectives and preserves the basic structure of utility-based schedulers such as the Proportional Fair algorithm in terms of per-user scheduling metrics. Specifically, the proposed scheme involves counters tracking the aggregate rate or resource allocations for the various slices against pre-specified targets, and computes offsets to the scheduling metrics accordingly. This design provides transparency with respect to other scheduling modules, such as link adaptation and beam-forming. We analytically establish that the proposed scheme achieves optimal overall throughput utility subject to the various slicing constraints. In addition, extensive 3GPP-compliant simulation experiments are conducted to assess the impact on best-effort applications and demonstrate substantial gains in overall throughput utility over baseline approaches.
【Keywords】: Aggregates; Scheduling; Resource management; 5G mobile communication; Base stations; Network slicing; Throughput
【Paper Link】 【Pages】:2341-2349
【Authors】: Jinlong E ; Yong Cui ; Mingkang Ruan ; Zhenhua Li ; Ennan Zhai
【Abstract】: Today's cloud storage infrastructures typically provide two distinct types of services for hosting files: object storage like Amazon S3 and filesystem storage like Amazon EFS. The former supports simple, flat object operations with a low unit storage price, while the latter supports complex, hierarchical filesystem operations with a high unit storage price. In practice, however, a cloud storage user often desires the advantages of both-efficient filesystem operations with a low unit storage price. An intuitive approach to achieving this goal is to combine the two types of services, e.g., by hosting large files in S3 and small files together with directory structures in EFS. Unfortunately, our benchmark experiments indicate that the clients' download performance for large files becomes a severe system bottleneck. In this paper, we attempt to address the bottleneck with little overhead by carefully tweaking the usages of S3 and EFS. This attempt is enabled by two key observations. First, since S3 and EFS have the same unit network-traffic price and the data transfer between S3 and EFS is free of charge, we can employ EFS as a relay for the clients' quickly downloading large files. Second, noticing that significant similarity exists between the files hosted at the cloud and its users, in most times we can convert large-size file downloads into small-size file synchronizations (through delta encoding and data compression). Guided by the observations, we design and implement an open-source system called HyCloud. It automatically invokes the data APIs of S3 and EFS on behalf of users, and handles the data transfer among S3, EFS and the clients. Real-world evaluations demonstrate that the unit storage price of HyCloud is close to that of S3, and the filesystem operations are executed as quickly as in EFS in most times (sometimes even more quickly than in EFS).
【Keywords】: Cloud computing; Data transfer; Relays; Encoding; Computer science; Benchmark testing; Metadata
【Paper Link】 【Pages】:2350-2358
【Authors】: Giovanni Neglia ; Gianmarco Calbi ; Don Towsley ; Gayane Vardoyan
【Abstract】: Many learning problems are formulated as minimization of some loss function on a training set of examples. Distributed gradient methods on a cluster are often used for this purpose. In this paper, we study how the variability of task execution times at cluster nodes affects the system throughput. In particular, a simple but accurate model allows us to quantity how the time to solve the minimization problem depends on the network of information exchanges among the nodes. Interestingly, we show that, even when communication overhead may be neglected, the clique is not necessarily the most effective topology, as commonly assumed in previous works.
【Keywords】: Computational modeling; Convergence; Task analysis; Throughput; Synchronization; Network topology; Servers
【Paper Link】 【Pages】:2359-2367
【Authors】: Yérom-David Bromberg ; Quentin Dufour ; Davide Frey
【Abstract】: The last decade has witnessed a rising interest in Gossip protocols in distributed systems. In particular, as soon as there is a need to disseminate events, they become a key functional building block due to their scalability, robustness and fault tolerance under high churn. However, Gossip protocols are known to be bandwidth intensive. A huge amount of algorithms has been studied to limit the number of exchanged messages using different combinations of push/pull approaches. We are revisiting the state of the art by applying Random Linear Network Coding to further increase performance. In particular, the originality of our approach is to combine sparse-vector encoding to send our network-coding coefficients and Lamport timestamps to split messages in generations in order to provide an efficient gossiping. Our results demonstrate that we are able to drastically reduce bandwidth overhead and dissemination delay compared to the state of the art.
【Keywords】: network coding; gossip; dissemination; peer-topeer network; epidemic algorithm; rumor spreading
【Paper Link】 【Pages】:2368-2376
【Authors】: Adiseshu Hari ; Murali S. Kodialam ; T. V. Lakshman
【Abstract】: The Bitcoin blockchain is a secure, distributed ledger that enables trusted transactions across untrusted entities. However, many applications need much faster transaction confirmation than that of the current Bitcoin blockchain. In this paper, we present a high-throughput, low-latency, deterministic confirmation mechanism called ACCEL for accelerating Bitcoin's block confirmation mechanism. Our key idea for achieving faster confirmation is the quick identification of singular blocks that provably belong to the blockchain. While it is impossible to determine with certainty if a block belongs to a blockchain when network delays are unbounded, singular block detection exploits the fact that the end-to-end latency between Bitcoin miners is substantially lower than the inter-block spacing and can be assumed to be upper bounded. ACCEL is especially suitable for low-latency, permissioned blockchains, where the block spacing can be optimized to the blockchain's small latencies to greatly improve throughput. We evaluate ACCEL's performance with extensive simulations and with a real implementation built with minimal changes to and fully compatible with the Bitcoin blockchain. We show that with appropriate bounds on the end-to-end latency, it is possible to reduce transaction confirmation latencies to milliseconds with ACCEL, and so meet the performance needs of a wide range of applications.
【Keywords】: Blockchain; Vegetation; Bitcoin; Delays; Throughput; Consensus algorithm; Distributed ledger
【Paper Link】 【Pages】:2377-2385
【Authors】: Joan Palacios ; Paolo Casari ; Hany Assasa ; Joerg Widmer
【Abstract】: Future millimeter-wave networks will support very high densities of devices and access points. This vastly increases the overhead required for access point selection and beam training. Fortunately, the quasi-optical properties of millimeter-wave channels make location-based network optimization a highly promising technique to reduce control overhead in such millimeter-wave WLANs. In this paper, we extract channel state information from off-the-shelf routers, we use it to design a high accuracy location system, and then show how location information enables the optimization of network operations. The resulting scheme, named LEAP, can predict blockage, optimize access point association, and select the most suitable antenna beam patterns while significantly reducing the beam training overhead. We show that compared to standard state-of-the-art 802.11ad systems, LEAP's location driven management greatly improves network performance and link stability.
【Keywords】: Training; Structural beams; Handover; Antenna arrays; Three-dimensional displays; Optimization
【Paper Link】 【Pages】:2386-2394
【Authors】: Yang Liu ; Wuxiong Zhang ; Yang Yang ; Weidong Fang ; Fei Qin ; Xuewu Dai
【Abstract】: Motion tracking technologies have been widely used in mobile interaction applications, such as Virtual Reality (VR), healthy monitoring, and virtual touch control. Compared with dedicated hardware devices, mobile phones use reliable speakers and microphones, and can serve as ubiquitous devices for cheap acoustic-based motion tracking solutions. However, for complex indoor environments, it is very difficult for acoustic-based methods to achieve accurate motion tracking due to multipath fading and limited sampling rate at mobile devices. In this paper, a new parameter named Multipath Effect Ratio (MER) is defined to indicate the multipath fading effect on received signals at different frequencies. Based on MER, a novel multipath effect mitigating technique is developed to calculate the phase change of acoustic signals and track the corresponding moving distance by using multiple speakers. A Phase-based Acoustic Motion Tracking (PAMT) method is then proposed and implemented on standard Android smartphones. Experiment results show, without any specialized hardware, PAMT can achieve an impressive millimeter-level accuracy for localization and motion tracking applications in multipath fading environments. Specifically, the measurement errors are less than 2mm and 4mm in one-dimensional and two-dimensional scenarios, respectively.
【Keywords】: Motion Tracking; Multipath Fading; Mobile Interaction
【Paper Link】 【Pages】:2395-2403
【Authors】: Yuanchao Shu ; Zhuqi Li ; Börje Karlsson ; Yiyong Lin ; Thomas Moscibroda ; Kang G. Shin
【Abstract】: Despite years of research attention, localization-based indoor navigation has not found wide-spread practical use, largely due to the high burden on deployment and bootstrapping. Lightweight peer-to-peer navigation systems that use a leader-follower model have recently been proposed to alleviate these burdens. However, typical peer-to-peer navigation suffers from poor scalability and flexibility as navigation is only possible over pre-collected leader paths. In this paper, we present FollowUs, an easily-deployable (bootstrap-free) and scalable indoor navigation system. In addition to robust navigation through real-time trace-following, FollowUs integrates cloud services to process and combine traces at large scale. Optionally, it can also leverage floor plans to further enhance navigation efficiency. We design and implement FollowUs, including mobile app and cloud services. Experimental results from a company-internal beta release show that 91% of FollowUs' spatial errors on reaching destinations to be 3m or less, and 95% of navigation instructions are shown to users within a 4-step error margin during navigation.
【Keywords】: Hafnium
【Paper Link】 【Pages】:2404-2412
【Authors】: Sixu Piao ; Zhongjie Ba ; Lu Su ; Dimitrios Koutsonikolas ; Shi Li ; Kui Ren
【Abstract】: Indoor localization has been an active research area given the popularity of Location-Based Services. The CSI fingerprinting based approach is one of the most practical and effective approaches since it can provide adequate accuracy with low overhead for users. The key drawback that limits its wide application is the huge amount of human effort required to build the fingerprint map. This paper is the first to explore addressing this limitation by automating CSI map construction using an Unmanned Aerial Vehicle (UAV). Given the limited battery capacity of commodity UAVs, it is extremely important yet challenging to optimize energy efficiency for the UAV during the CSI measurement task. To address this challenge, we formulate an energy optimization problem based on a novel graph model that includes the cost of possible actions for UAVs. We then transform the formulated problem to the classic Generalized Traveling Salesman Problem (GTSP), which can be solved efficiently. We implement the system on an off-the-shelf programmable drone equipped with a CSI measurement module. We achieve great energy efficiency improvement over the conventional coverage path planning algorithm. Meanwhile, accurate indoor localization can be achieved using the CSI data collected by our UAV system.
【Keywords】: Task analysis; Unmanned aerial vehicles; Energy measurement; Wireless fidelity; Wireless communication; Path planning; Current measurement
【Paper Link】 【Pages】:2413-2421
【Authors】: Anastasios Giovanidis ; Bruno Baynat ; Antoine Vendeville
【Abstract】: We introduce an original mathematical model to analyze the diffusion of posts within a generic online social platform. Each user of such a platform has his own Wall and Newsfeed, as well as his own self-posting and re-posting activity. As a main result, using our developed model, we derive in closed form the probabilities that posts originating from a given user are found on the Wall and Newsfeed of any other. These probabilities are the solution of a linear system of equations. Conditions of existence of the solution are provided, and two ways of solving the system are proposed, one using matrix inversion and another using fixed-point iteration. Comparisons with simulations show the accuracy of our model and its robustness with respect to the modeling assumptions. Hence, this article introduces a novel measure which allows to rank users by their influence on the social platform, by taking into account not only the social graph structure, but also the platform design, user activity (self-and re-posting), as well as competition among posts.
【Keywords】: Mathematical model; Analytical models; Steady-state; Robustness; Facebook
【Paper Link】 【Pages】:2422-2430
【Authors】: Vishrant Tripathi ; Rajat Talak ; Eytan Modiano
【Abstract】: We consider the problem of timely exchange of updates between a central station and a set of ground terminals V , via a mobile agent that traverses across the ground terminals along a mobility graph G = (V, E). We design the trajectory of the mobile agent to minimize peak and average age of information (AoI), two newly proposed metrics for measuring timeliness of information. We consider randomized trajectories, in which the mobile agent travels from terminal i to terminal j with probability P i,j . For the information gathering problem, we show that a randomized trajectory is peak age optimal and factor-8H average age optimal, where H is the mixing time of the randomized trajectory on the mobility graph G. We also show that the average age minimization problem is NP-hard. For the information dissemination problem, we prove that the same randomized trajectory is factor-O(H) peak and average age optimal. Moreover, we propose an age-based trajectory, which utilizes information about current age at terminals, and show that it is factor-2 average age optimal in a symmetric setting.
【Keywords】: Trajectory; Mobile agents; Information age; Sea measurements; Pollution measurement; Minimization
【Paper Link】 【Pages】:2431-2439
【Authors】: Xin Zhang ; Jia Liu ; Zhengyuan Zhu ; Elizabeth S. Bentley
【Abstract】: Network consensus optimization has received increasing attention in recent years and has found important applications in many scientific and engineering fields. To solve network consensus optimization problems, one of the most well-known approaches is the distributed gradient descent method (DGD). However, in networks with slow communication rates, DGD's performance is unsatisfactory for solving high-dimensional network consensus problems due to the communication bottleneck. This motivates us to design a communication-efficient DGD-type algorithm based on compressed information exchanges. Our contributions in this paper are three-fold: i) We develop a communication-efficient algorithm called amplified-differential compression DGD (ADC-DGD) and show that it converges under any unbiased compression operator; ii) We rigorously prove the convergence performances of ADC-DGD and show that they match with those of DGD without compression; iii) We reveal an interesting phase transition phenomenon in the convergence speed of ADC-DGD. Collectively, our findings advance the state-of-the-art of network consensus optimization theory.
【Keywords】: Convergence; Optimization; Linear programming; Information exchange; Eigenvalues and eigenfunctions; Robot sensing systems; Wireless sensor networks
【Paper Link】 【Pages】:2440-2448
【Authors】: Kazuya Sakai ; Min-Te Sun ; Wei-Shinn Ku
【Abstract】: Mobile users and wireless devices are now the sources of a large volume of data. In such data-intensive mobile and wireless computing systems, delay-tolerant network (DTN) routing plays a critical role in data routing, dissemination, and collection. In this paper, we first introduce a new routing problem in DTNs - data-intensive routing - where data transmitted from one node to another is very large with respect to the size of data which can be transmitted in a single contact and available buffer size at relay nodes. In the proposed opportunistic path model, the contact frequency, contact duration, and buffer constraint are all integrated into a single routing metric. Then, we design the data-intensive routing (DIR) protocol where the path with the highest bottleneck link capacity is defined as the path weight. In addition, we propose the advanced DIR (A-DIR) protocol which focuses on the probability that the last message block will be delivered to its destination within the time constraint. Both the DIR and A-DIR protocols forward messages to better relays or to their destinations based on a greedy strategy with the proposed path metric. Simulations using real mobility traces demonstrate that the proposed DIR and A-DIR protocols achieve their design goals.
【Keywords】: Delay tolerant networks; DTNs; routing; data-intensive protocols
【Paper Link】 【Pages】:2449-2457
【Authors】: Qixia Zhang ; Fangming Liu ; Chaobing Zeng
【Abstract】: Based on network function virtualization (NFV) and software defined network (SDN), network slicing is proposed as a new paradigm for building service-customized 5G network. In each network slice, service-required virtual network functions (VNFs) can be flexibly deployed in an on-demand manner, which will support a variety of 5G use cases. However, due to the diverse performance requirements among different 5G scenarios, an adaptive VNF placement approach is needed to automatically accommodate to service-specific requirements. In this paper, we tackle the VNF placement problem by first proposing a general 5G network slice framework, which jointly contains both edge cloud and core cloud servers. Specially, based on the fact that VNF consolidation may cause severe performance degradation, we adopt a demand-supply model to quantity the VNF interference. With an aim to maximize the total throughput of accepted requests, we propose an Adaptive Interference-Aware (AIA) heuristic approach to automatically place VNFs in 5G service-customized network slices. Through simulations on two typical 5G scenarios, we demonstrate that AIA can efficiently handle traffic variation especially caused by VNF interference and improve the total throughput by 20.11% and 24.21% in autonomous driving and 4K/8K HD video network slices as compared with the state-of-the-art methods.
【Keywords】: 5G mobile communication; Servers; Interference; Throughput; Autonomous vehicles; High definition video; Adaptive systems
【Paper Link】 【Pages】:2458-2466
【Authors】: Gil Einziger ; Maayan Goldstein ; Yaniv Sa'ar
【Abstract】: Network Function Virtualization (NFV) allows operators to deploy network functions in virtual machines (VMs) and benefit from on-demand deployment. VMs are placed on one of the hosts in the cloud, and existing resource management algorithms assume full knowledge of the system's state. For large clusters, attaining the system's state creates bottlenecks and therefore it takes a long time to deploy network functionalities. Intuitively, placement can be accelerated if the resource management algorithm operates on a cached system state which is not entirely up to date, but the placement quality may suffer. Our work introduces a new cache refresh method that achieves an up to a 5.3x reduction in placement time with only a slight degradation of quality compared to having the complete and up to date system's state.
【Keywords】: Heuristic algorithms; Cloud computing; Resource management; Computational modeling; Virtual machining; Clustering algorithms; Degradation
【Paper Link】 【Pages】:2467-2475
【Authors】: Sladana Josilo ; György Dán
【Abstract】: We consider the problem of allocating wireless and computing resources to a set of autonomous wireless devices in an edge computing system. Devices in the system can decide whether or not to use edge computing resources for offloading computing tasks so as to minimize their completion time, while the edge cloud operator can allocate wireless and computing resources to the devices. We model the interaction between devices and the operator as a Stackelberg game, prove the existence of Stackelberg equilibria, and propose an efficient decentralized algorithm for computing equilibria. We provide a bound on the price of anarchy of the game, which also serves as an approximation ratio bound for the proposed algorithm. Our simulation results show that the joint allocation of wireless and computing resources by the operator can halve the completion times compared to a system with static resource allocation. At the same time, the convergence time of the proposed algorithm is approximately linear in the number of devices, and thus it could be effectively implemented for edge computing resource management.
【Keywords】: Resource management; Task analysis; Wireless communication; Edge computing; Computational modeling; Games; Approximation algorithms
【Paper Link】 【Pages】:2476-2484
【Authors】: Lorenzo Corneo ; Christian Rohner ; Per Gunningberg
【Abstract】: We consider large scale Internet of Things applications requesting data from physical devices. We study the problem of timely dissemination of sensor data towards applications with freshness requirements by means of a cache. We aim to minimize direct access to the possibly battery powered physical devices, yet improving Age of Information as a data freshness metric. We propose an Age of Information-aware scheduling policy for the physical device to push sensor updates to the caches located in cloud data centers. Such policy groups application requests based on freshness thresholds, thereby reduces the number of requests and threshold misses, and accounts for delay variation. The policy is incrementally introduced as we study its behavior over ideal and more realistic communication links with delay variation. We numerically evaluate the proposed policy against a simple yet widely used periodic schedule. We show that our informed schedule outperforms the periodic schedule even under high delay variations.
【Keywords】: Cloud computing; Schedules; Sensors; Delays; Servers; Internet of Things; Information age
【Paper Link】 【Pages】:2485-2493
【Authors】: Xiangyu Wang ; Jianfeng Ma ; Ximeng Liu ; Yinbin Miao
【Abstract】: The traditional privacy-preserving image retrieval schemes not only bring large computational and communication overhead but also cannot well protect the image and query privacy in multi-user scenarios. To solve the above problems, we first propose a basic privacy-preserving content-based image retrieval (CBIR) framework which significantly reduces storage and communication overhead compared with the previous works. Furthermore, we design a new efficient key conversion protocol to support unshared key multi-owner multi-user image retrieval without losing search precision. Moreover, our framework supports unbounded attributes and can trace malicious users according to leaked secret keys, which significantly improve the usability of multi-source data sharing. Strict security analysis shows that the user privacy and outsourced data security can be guaranteed during the image retrieval process, and the performance analysis using real-world dataset shows that the proposed image retrieval framework is efficient and feasible for practical applications.
【Keywords】: privacy-preserving; content-based image retrieval; unshared key; multi-source data sharing
【Paper Link】 【Pages】:2494-2502
【Authors】: Ke Cheng ; Yulong Shen ; Yongzhi Wang ; Liangmin Wang ; Jianfeng Ma ; Xionghong Jiang ; Cuicui Su
【Abstract】: Cloud database provides an advantageous platform for outsourcing of database service. To protect data confidentiality from an untrusted cloud, the original database is often encrypted and then uploaded to the cloud. However, in order to support functional queries, existing secure databases require users to encrypt their data under the same public/symmetric key, which restricts the usage scenarios since users do not really trust each other in practice. Imagine a scenario where a user uploaded his/her own encrypted data to the cloud database and another user wants to execute private range queries on this data. This scenario occurs in many cases of collaborative statistical analysis where the data provider and analyst are different entities. Then either the data provider must reveal its encryption key or the analyst must reveal the private queries. In this paper, we overcome this restriction for secure range queries by enabling query executions on the multi-key encryption data. We propose a secure cloud database supporting range queries under multiple keys, in which all users could preserve the confidentiality of their own different keys, and do not have to share them with each other. At a higher level, our system is constructed on a two-cloud architecture and a novel distributed two-trapdoor public key cryptosystem. We prove that the proposed scheme achieves the goal of a secure query without leaking data privacy, query privacy, and data access patterns. Finally, we use extensive experiments over a real-world dataset on a commercial cloud platform to verify the efficacy of our proposed scheme.
【Keywords】: Databases; Protocols; Cloud computing; Encryption; Data privacy
【Paper Link】 【Pages】:2503-2511
【Authors】: Lei Xu ; Xingliang Yuan ; Cong Wang ; Qian Wang ; Chungen Xu
【Abstract】: Searchable encryption (SE) is a practical crypto-graphic primitive to build encrypted databases. Recently there has been much attention in leakage-abuse attacks against SE. Among others, attacks based on inference of keyword frequency can easily identify query keywords from the access pattern, i.e., query results. To mitigate these attacks, database padding is considered as a conceptually simple yet effective counter-measure. Unfortunately, none of the existing studies formally understand the relationship between padding security strength and its overhead. Also, how to craft padding is not restricted in current countermeasures, where bogus files are likely to be distinguishable from real ones. In this paper, we propose an information theory based framework to analyse the security strength under certain padding overhead. First, we leverage relative entropy to measure the “closeness” between the distributions of the original dataset and padded dataset. Second, we quantity the attack efforts against padding countermeasures by entropy analysis. Apart from theoretical findings, we further devise an algorithm via outlier detection for padding generation, which considers both the padded dataset distribution and the similarity between real and bogus files. Evaluations on a real-world dataset confirm our theoretical results and demonstrate the efficiency and effectiveness of our proposed padding generation algorithm.
【Keywords】: Databases; Encryption; Information theory; Entropy; Anomaly detection
【Paper Link】 【Pages】:2512-2520
【Authors】: Zhibo Wang ; Mengkai Song ; Zhifei Zhang ; Yang Song ; Qian Wang ; Hairong Qi
【Abstract】: Federated learning, i.e., a mobile edge computing framework for deep learning, is a recent advance in privacy-preserving machine learning, where the model is trained in a decentralized manner by the clients, i.e., data curators, preventing the server from directly accessing those private data from the clients. This learning mechanism significantly challenges the attack from the server side. Although the state-of-the-art attacking techniques that incorporated the advance of Generative adversarial networks (GANs) could construct class representatives of the global data distribution among all clients, it is still challenging to distinguishably attack a specific client (i.e., user-level privacy leakage), which is a stronger privacy threat to precisely recover the private data from a specific client. This paper gives the first attempt to explore user-level privacy leakage against the federated learning by the attack from a malicious server. We propose a framework incorporating GAN with a multi-task discriminator, which simultaneously discriminates category, reality, and client identity of input samples. The novel discrimination on client identity enables the generator to recover user specified private data. Unlike existing works that tend to interfere the training process of the federated learning, the proposed method works “invisibly” on the server side. The experimental results demonstrate the effectiveness of the proposed attacking approach and the superior to the state-of-the-art.
【Keywords】: Servers; Training; Data models; Privacy; Computational modeling; Gallium nitride; Data privacy
【Paper Link】 【Pages】:2521-2529
【Authors】: Pedram Kheirkhah Sangdeh ; Hossein Pirayesh ; Huacheng Zeng ; Hongxiang Li
【Abstract】: As the proliferation of mobile devices has led to an ever-growing demand for wireless Internet services, the spectrum shortage issue becomes increasingly severe and spectrum sharing is regarded as a promising approach to addressing the spectrum shortage issue. In this paper, we propose a practical underlay spectrum sharing scheme for cognitive radio networks (CRNs) where the primary users are oblivious to the secondary users. The key components of our scheme are two MIMO-based interference cancellation (IC) techniques to handle cross-network interference on the secondary network side. The first one is a blind beamforming technique for secondary transmitters. This IC technique allows a secondary transmitter to nullify its generated interference for primary users without requiring channel state information (CSI). The second one is a blind interference cancellation (BIC) technique for secondary receivers. This IC technique enables a secondary receiver to decode its desired signal in the presence of strong unknown interference from primary transmitters. Based on these two MIMO-based IC techniques, we develop a MAC protocol for the secondary network to enable underlay spectrum sharing in CRNs. We have implemented the proposed underlay spectrum sharing scheme on a GNURadio-USRP2 wireless testbed. Experimental results show that the secondary users can achieve an average of 1 bit/s/Hz spectrum efficiency without degrading the performance of the primary users in a real-world office building environment.
【Keywords】: Cognitive radio networks; spectrum sharing; blind interference cancellation; beamforming; MIMO
【Paper Link】 【Pages】:2530-2538
【Authors】: Song Fang ; Tao Wang ; Yao Liu ; Shangqing Zhao ; Zhuo Lu
【Abstract】: Due to the open nature of wireless medium, wireless communications are especially vulnerable to eavesdropping attacks. This paper designs a new wireless communication system to deal with eavesdropping attacks. The proposed system can enable a legitimate receiver to get desired messages and meanwhile an eavesdropper to hear “fake” but meaningful messages, thereby confusing the eavesdropper and achieving additional concealment that further protects exchanged messages. Towards this goal, we propose techniques that can conceal exchanged messages by utilizing wireless channel characteristics between the transmitter and the receiver, as well as techniques that can attract an eavesdropper to gradually approach a trap region, where the eavesdropper can get fake messages. We also implement and evaluate the proposed system on top of Universal Software Defined Radio Peripherals (USRPs). Experimental results show that an eavesdropper at a trap location can receive fake information with a bit error rate (BER) that is close to 0, and the transmitter with multiple antennas can successfully deploy a trap area.
【Keywords】: Receivers; Transmitters; Wireless communication; Communication system security; Signal to noise ratio; MIMO communication; Cryptography
【Paper Link】 【Pages】:2539-2547
【Authors】: Zijiang Hao ; Shanhe Yi ; Qun Li
【Abstract】: The rise of edge computing gives birth to a spectrum of delay-sensitive applications. Many of these applications build their services atop the functionality that the edge nodes quickly negotiate a unique order on the events received from a massive number of client devices, even under very high event rates. To this end, we propose a protocol, called Nomad, for achieving fast event ordering in edge computing environments. Nomad is designed as a consensus protocol that employs a lease-based approach to take advantage of the locality of the unbalanced workload across the system. It also dynamically adjusts the leadership distribution on the edge nodes based on the recent running history, and relies on a cloud-based arbitrator to resolve contentions. Experiments demonstrate that Nomad outperforms the existing solutions, such as Multi-Paxos, Mencius and E-Paxos, in achieving fast event ordering for large-scale, delay-sensitive edge-cloud applications.
【Keywords】: Edge computing; Urban areas; Games; Cloud computing; Protocols; Data centers; Internet of Things
【Paper Link】 【Pages】:2548-2556
【Authors】: Gabriele Castellano ; Flavio Esposito ; Fulvio Risso
【Abstract】: Edge Computing brings flexibility and scalability of virtualization technologies at the edge of the network, enabling service providers to deploy new applications over a richer network infrastructure. However, the coexistence of such variety of applications on the same infrastructure exacerbates the already challenging problem of coordinating resource allocation while preserving the resource assignment optimality. In fact, (i) each application can potentially require different optimization criteria due to their heterogeneous requirements, and (ii) we may not count on a centralized orchestrator due to the highly dynamic nature of edge networks. To solve this problem, we present DRAGON, a Distributed Resource AssiGnment and OrchestratioN algorithm that seeks optimal partitioning of shared resources between different applications running over a common edge infrastructure. We designed DRAGON to guarantee both a bound on convergence time and an optimal (1-1/e)-approximation with respect to the Pareto optimal resource assignment. We evaluate convergence and performance of DRAGON on a prototype implementation, assessing the benefits compared to traditional orchestration approaches.
【Keywords】: Optimization; Convergence; Voting; Resource management; Edge computing; Scalability; Virtualization
【Paper Link】 【Pages】:2557-2565
【Authors】: Jianhai Chen ; Deshi Ye ; Shouling Ji ; Qinming He ; Yang Xiang ; Zhenguang Liu
【Abstract】: Demand response (DR) is a vital means of electricity market in maintaining power grid reliability, sustainability and stability. DR can enable consumers (e.g. data centers) to reduce their electricity consumption when the supply of electricity is a shortage. The consumers will be rewarded if they reduce or shift some of their energy usage during peak hours. Aiming at solving the efficiency of DR, in this paper, we present MEDR, a mechanism on emergency DR in colocation data center. First, we formalize the MEDR problem and propose a dynamic programming to solve the optimization version of the problem. We then design a deterministic mechanism to solve the MEDR. We prove that our mechanism is truthful and it is an FPTAS, i.e., it can be approximated within 1 + ε for any given ε > 0, while the running time of our mechanism is polynomial in the number of tenants n and 1/ε. Furthermore, we also give an auction system covering the efficient FPTAS algorithm as bidding decision program for DR. Finally, we choose a real dataset to build a large number of simulation datasets in performance evaluation. The results show that our mechanism outperforms near-optimal and high utility demonstrate the effectiveness of our work.
【Keywords】: Emergency Demand Response; Knapsack Problem; Mechanism Design; Colocation Data Center; Auction
【Paper Link】 【Pages】:2566-2574
【Authors】: Shutong Chen ; Lei Jiao ; Lin Wang ; Fangming Liu
【Abstract】: The computing frontier is moving from centralized mega datacenters towards distributed cloudlets at the network edge. We argue that cloudlets are well-suited for participation in Emergency Demand Response (EDR) programs due to their enormous energy consumption and flexible workload distribution, while existing EDR mechanisms for clouds and colocation datacenters are not suitable for cloudlets. We propose a novel online market mechanism, EdgeEDR, to incentivize cloudlets to participate in EDR, featuring multiple cloudlet-specific designs. At a high level, we observe that cloudlet operators can dynamically switch on/off entire cloudlets to compensate for the energy reduction required by the power grid. We formulate a long-term social cost minimization problem and decompose it into a series of one-round procurement auctions. In each auction instance, we propose to let the cloudlet tenants bid with cost functions of their service quality degradation tolerance, and let the cloudlet operator choose the service quality, allocate the workload, and shut down the cloudlets. Via rigorous analysis, we exhibit that our bidding policy is individually rational and truthful; our workload distribution algorithm has near-optimal performance in each auction; and our overall online algorithm achieves a provable competitive ratio. We further confirm the performance of our mechanism through extensive trace-driven simulations.
【Keywords】: Cloud computing; Delays; Switches; Generators; Degradation; Procurement; Load management
【Paper Link】 【Pages】:2575-2583
【Authors】: Abhinandan S. Prasad ; Mayutan Arumaithurai ; David Koll ; Yuming Jiang ; Xiaoming Fu
【Abstract】: Currently, cloud computing is a primary enabler of new paradigms such as edge and fog computing. One open issue is the pricing of services or resources. Current pricing schemes are usually oligopolistic and not fair. In this work, we propose OFM, an online learning based marketplace that dynamically determines the price for arbitrary resource types based on supply and demand existing at that period. Unlike state of the art solutions, OFM can handle an arbitrary number of customers and resource types at every instance of time. It further performs integral allocation of resources and thereby avoids the unbounded integrality gap. We evaluate OFM with both real and synthetic datasets to reflect varying buying interests, the number of resources sold and market volatility to demonstrate the feasibility of our solution for several realistic scenarios. We observe that (i) OFM achieves about 9% of optimal prices and maximizes the Nash social welfare (NSW); (ii) OFM converges faster and works with different data distributions; and (iii) OFM scales for a large number of resources and buyers and computational time is in the order of microseconds, making it applicable for real-time use cases especially in edge markets.
【Keywords】: Cloud computing; Pricing; Resource management; Computational modeling; Heuristic algorithms; Stochastic processes; Edge computing
【Paper Link】 【Pages】:2584-2592
【Authors】: Ramya Burra ; Chandramani Singh ; Joy Kuri
【Abstract】: We study service scheduling problems in a slotted system in which jobs arrive according to a Bernoulli process and have to leave within two slots after arrival, service costs are quadratic in service rates, and there is also a linear waiting cost. We illustrate how these systems can be used to model CPU speed scaling, EV charging at a charging center, load scheduling in smart grids etc. We frame the problems as average cost Markov decision processes. While the studied system is a linear system with quadratic costs, it has state dependent control and non-standard cost function structure, rendering the optimization problem complex. We obtain explicit optimal policies in the case when all the jobs are of same size. In particular, we show that the optimal policy is linear or piece-wise linear in the system state, depending on the system parameters. Further, when the job sizes can take two distinct values, we provide an algorithm that yields the optimal policy. We illustrate different forms of these policies via numerical examples.
【Keywords】: Optimal scheduling; Processor scheduling; Stochastic processes; Charging stations; Heuristic algorithms; Games