35th Annual IEEE International Conference on Computer Communications, INFOCOM 2016, San Francisco, CA, USA, April 10-14, 2016. IEEE 【DBLP Link】
【Paper Link】 【Pages】:1-9
【Authors】: Stefano Paris ; Apostolos Destounis ; Lorenzo Maggi ; Georgios S. Paschos ; Jérémie Leguay
【Abstract】: Software-Defined Network (SDN) controllers include mechanisms to globally reconfigure the network in order to respond to a changing environment. While iterative methods are employed to solve flow optimization problems, demands arrive or leave the system changing the optimization instance and requiring further iterations. In this paper, we focus on the general class of iterative solvers considering an exponential decrease over time in the optimality gap. Assuming dynamic arrivals and departures of demands, the computed optimality gap at each iteration Q(t) is described by an auto-regressive stochastic process. At each time slot the controller may choose to apply the current iteration to the network or not. Applying the current iteration improves the optimality gap but requires flow reconfiguration which hurts QoS and system stability. To limit the reconfigurations, we propose two control policies that minimize the flow allocation cost while respecting a network reconfiguration budget. We validate our model by experimenting with a realistic network setting and using standard Linear Programming tools used in the SDN industry. We show that our policies provide a practical means of keeping the optimally gap small within a given reconfiguration constraint.
【Keywords】: Routing; Optimization; Quality of service; Stochastic processes; Linear programming; Computational modeling; Iterative methods
【Paper Link】 【Pages】:1-9
【Authors】: Zdravko Bozakov ; Amr Rizk ; Divyashri Bhat ; Michael Zink
【Abstract】: In this work we outline a framework for measurement-based performance evaluation in SDN environments. The SDN paradigm, which is based on a strict separation of the network logic from the underlying physical substrate, necessitates a comprehensive global view of the network state. To augment the network representation, we propose mechanisms for extracting traffic characteristics from network observations which are used to derive performance metrics. Such metrics can be exploited by SDN applications to optimize the performance of SDN services. Given the bursty nature of network traffic and the well known adverse impact of this property on network performance, we propose an approach for extracting flow autocorrelations from switch counters. Our main contribution is a random sampling approach that reduces the monitoring overhead while enabling a fine grained characterization of the flow autocorrelation structure. We analytically evaluate the impact of random sampling and demonstrate how services may use the estimated traffic properties to compute useful performance metrics.
【Keywords】: Radiation detectors; Monitoring; Switches; Measurement; Covariance matrices; Quality of service
【Paper Link】 【Pages】:1-9
【Authors】: Sebastian Brandt ; Klaus-Tycho Förster ; Roger Wattenhofer
【Abstract】: We study consistent migration of flows, with special focus on software defined networks. Given a current and a desired network flow configuration, we give the first polynomial-time algorithm to decide if a congestion-free migration is possible. However, if all flows must be integer or are unsplittable, this is NP-hard to decide. A similar problem is providing increased bandwidth to an application, while keeping all other flows in the network, but possibly migrating them consistently to other paths. We show that the maximum increase can be approximated arbitrarily well in polynomial time. Current methods as RSVP-TE consider unsplittable flows and remove flows of lesser importance in order to increase bandwidth for an application: We prove that deciding what flows need to be removed is an NP-hard optimization problem with no PTAS possible unless P = NP.
【Keywords】: Bandwidth; Control systems; Software; Optimization; Packet loss; Linear programming
【Paper Link】 【Pages】:1-9
【Authors】: Kai Bu ; Xitao Wen ; Bo Yang ; Yan Chen ; Li Erran Li ; Xiaolin Chen
【Abstract】: Software-Defined Networking (SDN) promises un-precedentedly flexible network management but it is susceptible to forwarding faults. Such faults originate from data-plane rules with missing faults and priority faults. Yet existing fault detection ignores priority faults because they are not discovered on commercial switches until recently. In this paper, we present RuleScope, a more comprehensive solution for inspecting SDN forwarding. RuleScope offers a series of accurate and efficient algorithms for detecting and troubleshooting rule faults. They inspect forwarding behavior using customized probe packets to exercise data-plane rules. The detection algorithm exposes not only missing faults but also priority faults. Beyond simply detecting rule faults, the troubleshooting algorithms uncover actual data-plane flow tables. They help track real-time forwarding status and benefit reliable network monitoring. We explore various techniques for enhancing algorithm efficiency without sacrificing inspection accuracy. Experiments with our prototype on the Ryu SDN controller and Pica8 P-3297 switch show that RuleScope achieves accurate and efficient forwarding inspection with limited bandwidth and packet-switching overhead.
【Keywords】: Probes; Inspection; Fault detection; Detection algorithms; Monitoring; Control systems; Algorithm design and analysis
【Paper Link】 【Pages】:1-9
【Authors】: Zhiyin Chen ; Xiaofeng Gao ; Fan Wu ; Guihai Chen
【Abstract】: Energy consumption is a fundamental and critical issue in wireless sensor networks. Mobile sensors consume much more energy during the movement than that during the communication or sensing process. Thus how to schedule mobile sensors and minimize their moving distance has great significance to researchers. In this paper, we study the target coverage problem in mobile sensor networks. Our goal is to minimize the moving distance of sensors to cover all targets in the surveillance region. Here initially all the sensors are located at k base stations. Thus we define this problem as k-Sink Minimum Movement Target Coverage. To solve this problem, we propose a PTAS, named Energy Effective Movement Algorithm (EEMA). We can divide EEMA into two phases. In the first phase, we partition the surveillance region into some subareas. In the second phase, we select subareas and schedule sensors to the selected subareas. We also prove that the approximation ratio of EEMA is 1 + ε and the time complexity is ηO(1/ε2 Finally, we conduct experiments to validate the efficiency and effectiveness of EEMA.
【Keywords】: Mobile communication; Algorithm design and analysis; Approximation algorithms; Surveillance; Heuristic algorithms; Wireless sensor networks; Mobile computing
【Paper Link】 【Pages】:1-9
【Authors】: Meng Jin ; Tianzhang Xing ; Xiaojiang Chen ; Xin Meng ; Dingyi Fang ; Yuan He
【Abstract】: The low-cost crystal oscillators embedded in wireless sensor nodes are prone to be affected by their working condition, leading to undesired variation of clock skew. To preserve synchronized clocks, nodes have to undergo frequent re-synchronization to cope with the time-varying clock skew, which in turn means excessive energy consumption. In this paper, we propose DualSync, a synchronization approach for low-power wireless networks under dynamic working condition. By utilizing time-stamp exchanges and local measurement of temperature and voltage, DualSync maintains an accurate clock model to closely trace the relationship between clock skew and the influencing factors. We further incorporate an error-driven mechanism to facilitate interplay between Inter-Sync and Self-Sync, so as to preserve high synchronization accuracy while minimizing communication cost. We evaluate the performance of DualSync across various scenarios and compare it with state-of-art approaches. The experimental results illustrate the superior performance of DualSync in terms of both accuracy and energy efficiency.
【Keywords】: Clocks; Synchronization; Temperature measurement; Employee welfare; Temperature; Voltage measurement; Wireless sensor networks
【Paper Link】 【Pages】:1-9
【Authors】: Ying Qiu ; ShiNing Li ; Xiangsen Xu ; Zhigang Li
【Abstract】: Neighbor discovery is a fundamental service for initialization and managing network dynamics in wireless sensor networks and mobile sensing applications. In this paper, we present a novel design principle named Talk More Listen Less (TMLL) to reduce idle-listening in neighbor discovery protocols by learning the fact that more beacons lead to fewer wakeups. We propose an extended neighbor discovery model for analyzing wakeup schedules in which beacons are not necessarily placed in the wakeup slots. Furthermore, we are the first to consider channel occupancy rate in discovery protocols by introducing a new metric to trade off among duty-cycle, latency and channel occupancy rate. Guided by the TMLL principle, we have designed Nihao, a family of energy-efficient asynchronous neighbor discovery protocols for symmetric and asymmetric cases. We compared Nihao with existing state of the art protocols via analysis and real-world testbed experiments. The result shows that Nihao significantly outperforms the others both in theory and practice.
【Keywords】: Protocols; Schedules; Probes; Wireless sensor networks; Measurement; Analytical models; Mobile computing
【Paper Link】 【Pages】:1-9
【Authors】: Cong Wang ; Ji Li ; Yuanyuan Yang ; Fan Ye
【Abstract】: Recently, there have been a growing number of applications that power wireless sensor networks (WSNs) by wireless charging technology. Although previous studies indicate that wireless charging can deliver energy reliably, it still faces regulatory challenges to provide high power density without incurring health risks. In particular, in clustered WSNs there exists a mismatch between the high energy demands from cluster heads and the relatively low energy supplies that wireless charging can provide. Fortunately, solar energy harvesting can provide high power density which is also risk-free. However, it is subject to weather dynamics. Therefore, in this paper, we propose a hybrid framework that combines the two technologies - cluster heads are equipped with solar panels to scavenge solar energy and the rest of nodes are powered by wireless charging. First, we study a placement problem on how to deploy solar-powered cluster heads that can minimize overall cost and propose a distributed 1.61(1 + ϵ)2-approximation algorithm for the placement. Second, we establish an energy balance in the network and explore how to maintain such balance when sunlight is unavailable. Third, we consider combining wireless charging and mobile data gathering in a joint tour in such networks, and propose a polynomial-time scheduling algorithm. Our extensive simulation demonstrates that the hybrid framework can reduce battery depletion by 20% and save system cost by 25% compared to previous results.
【Keywords】: Wireless sensor networks; Inductive charging; Mobile communication; Approximation algorithms; Solar energy; Routing; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Wenhao Fan ; Yuan'an Liu ; Bihua Tang
【Abstract】: Event matching is vital in multi-dimensional content-based publish/subscribe services, which are widely employed for data dissemination in various scenarios. Existing mechanisms suffer from performance degradation in high-dynamic large-scale systems. To this end, we present GEM (Geometrical Event Matching), an analytic geometrical approach to fast event matching. GEM offers a very high event matching speed, and it also has low costs for subscription insertion/deletion operations and memory usage. In GEM, subscriptions are organized efficiently by a triangle-like index structure. A graph partitioning matching method and a selection matching method are jointly used for single-dimensional matching (SDM). Optimized by a decision algorithm for each incoming event, the event matching process is carried out in a pipeline consisting the SDM for each dimension. The search space shrinks continuously as the process goes, so that the event matching performance is promoted adaptively. A cache method is also designed to boost the first SDM in the pipeline. We implement extensive experiments to evaluate the performance of GEM in comparison with 3 state-of-the-art reference algorithms (TAMA, H-TREE and REIN). The results show that, the event matching time, subscription insertion/deletion time and memory consumption of GEM is on average 53.9%, 42.3%/49.5% and 31.8% lower than the best in other 3 algorithms, respectively. The event matching time of GEM is reduced efficiently via the cache method. The superiority of GEM appears more significantly as system scale and dynamic grow, and its performance also maintains in a high stability.
【Keywords】: Indexes; Algorithm design and analysis; Pipelines; Partitioning algorithms; Memory management; Monitoring
【Paper Link】 【Pages】:1-9
【Authors】: Yu Hua
【Abstract】: Cloud computing generally needs to handle large amounts of data in a real-time manner. Typical metrics include fast write and query performance. However, existing cloud systems fail to efficiently offer fast query and write services due to two main reasons. One is the design separation between query and write operations. Most schemes mainly optimize one aspect. The other is the lack of cost-efficient data analytics, which leads to the identical resource consumption for each data item. In order to address the two problems and efficiently support fast query and write services, this paper proposes a novel flat-addressing scheme, called Cheetah. The idea behind Cheetah is to leverage efficient online data compression to reduce the amounts of data to be written, and meantime make use of a flat-addressing cuckoo hashing scheme to support fast query service. In practice, conventional cuckoo hashing schemes suffer from the endless loops, thus not only leading to insertion failure but also causing long operation latency. In order to alleviate the endless loops in item insertion, we use extra space to temporarily store the items that cause hash collisions, which are often shared by multiple loops. In order to further improve system performance, we prefetch the collision data in a batch to further reduce the probability of the occurrence of endless loops, thus offering fast query services to identify the searched items. Extensive experimental results demonstrate that the flat-addressing Cheetah can efficiently support query services in the cloud.
【Keywords】: Cloud computing; Prefetching; Redundancy; Servers; Metadata; Indexes; Random access memory
【Paper Link】 【Pages】:1-9
【Authors】: Liang Tong ; Yong Li ; Wei Gao
【Abstract】: The performance of mobile computing would be significantly improved by leveraging cloud computing and migrating mobile workloads for remote execution at the cloud. In this paper, to efficiently handle the peak load and satisfy the requirements of remote program execution, we propose to deploy cloud servers at the network edge and design the edge cloud as a tree hierarchy of geo-distributed servers, so as to efficiently utilize the cloud resources to serve the peak loads from mobile users. The hierarchical architecture of edge cloud enables aggregation of the peak loads across different tiers of cloud servers to maximize the amount of mobile workloads being served. To ensure efficient utilization of cloud resources, we further propose a workload placement algorithm that decides which edge cloud servers mobile programs are placed on and how much computational capacity is provisioned to execute each program. The performance of our proposed hierarchical edge cloud architecture on serving mobile workloads is evaluated by formal analysis, small-scale system experimentation, and large-scale trace-based simulations.
【Keywords】: Cloud computing; Servers; Mobile communication; Computer architecture; Mobile computing; Delays; Mobile applications
【Paper Link】 【Pages】:1-9
【Authors】: Shuihai Hu ; Wei Bai ; Kai Chen ; Chen Tian ; Ying Zhang ; Haitao Wu
【Abstract】: Today's cloud is shared among multiple tenants running different applications, and a desirable multi-tenant datacenter network infrastructure should provide bandwidth guarantees for throughput-intensive applications, low latency for latency-sensitive short messages, as well as work conservation to fully utilize the network bandwidth. Despite significant efforts in recent years, none of them can achieve these three properties simultaneously. In this paper, we identify the key deficiency of prior solutions and use this insight to motivate our design of Trinity - a simple, practical yet effective solution that achieves bandwidth guarantees, work conservation and low latency simultaneously in the cloud. We implement Trinity using existing commodity hardwares and demonstrate its superior performance over prior solutions using testbed experiments.
【Keywords】: Bandwidth; Probes; Hardware; Delays; Interference; Control systems; Servers
【Paper Link】 【Pages】:1-9
【Authors】: Weiping Sun ; Changmok Yang ; Sunggeun Jin ; Sunghyun Choi
【Abstract】: Wi-Fi Direct, now part of Android smartphones, makes it possible for Wi-Fi devices to communicate directly without passing through an access point. Before starting actual data exchange, two devices should apparently find each other through a device discovery process, called find phase. After identifying the limitation of the legacy find phase, incurring long discovery delay, we propose a simple and efficient scheme, called Listen Channel Randomization (LCR), in order to expedite device discovery. Both the legacy find phase and LCR are evaluated with our elaborate Markov model and ns-3 simulations for comprehensive comparisons. Moreover, we have implemented a prototype of LCR in Android smartphone. Our experimental results reveal that LCR can significantly reduce the device discovery delay, yielding up to 72% delay reduction compared to the legacy find phase.
【Keywords】: IEEE 802.11 Standard; Probes; Markov processes; Delays; Performance evaluation; Wireless communication; Transient analysis
【Paper Link】 【Pages】:1-9
【Authors】: Varun Gupta ; Craig Gutterman ; Yigal Bejerano ; Gil Zussman
【Abstract】: WiFi multicast to very large groups has gained attention as a solution for multimedia delivery in crowded areas. Yet, most recently proposed schemes do not provide performance guarantees and none have been tested at scale. To address the issue of providing high multicast throughput with performance guarantees, we present the design and experimental evaluation of the Multicast Dynamic Rate Adaptation (MuDRA) algorithm. MuDRA balances fast adaptation to channel conditions and stability, which is essential for multimedia applications. MuDRA relies on feedback from some nodes collected via a light-weight protocol and dynamically adjusts the rate adaptation response time. Our experimental evaluation of MuDRA on the ORBIT testbed with over 150 nodes shows that MuDRA outperforms other schemes and supports high throughput multicast flows to hundreds of receivers while meeting quality requirements. MuDRA can support multiple high quality video streams, where 90% of the nodes report excellent or very good video quality.
【Keywords】: Interference; IEEE 802.11 Standard; Receivers; Throughput; Algorithm design and analysis; Orbits; Unicast
【Paper Link】 【Pages】:1-9
【Authors】: Changlai Du ; Ruide Zhang ; Wenjing Lou ; Y. Thomas Hou
【Abstract】: In this paper, we present MobTrack, a single device system which aims to locate interfering radios on unlicensed ISM band in indoor environments. Compared with existing techniques which require a deployment of dense access points (APs), MobTrack only demands a single device equipped with multiple antennas. The location of an interfering signal source are estimated by computing the angle of arrival (AoA) of Line of Sight (LoS) component using an antenna array. Taking advantage of cyclostationary property, MobTrack differentiates interfering signals from working signals. By moving the device around for a short distance within one meter, it depresses multipath effects and determines the LoS component. Simultaneously, the AoAs on the moving trace are recorded to estimate the location of the interfering radio by triangulation. We evaluate the performance of MobTrack by setting up a prototype experimental system. Compared with recent interference localization schemes, MobTrack has much lower hardware complexity and gets better localization accuracy with a median of 0.55 meters.
【Keywords】: Interference; Antenna arrays; IEEE 802.11 Standard; Algorithm design and analysis; Signal processing algorithms; Wireless communication; OFDM
【Paper Link】 【Pages】:1-9
【Authors】: Luca Barletta ; Flaminio Borgonovo ; Ilario Filippini
【Abstract】: The stability and throughput of the Slotted Aloha protocol have been studied at length, yielding results that depend on the environment and channel assumptions, in many cases indicating e-1 as the S-Aloha capacity. When users can detect only their own collisions, and the number of users N goes to infinity, no definite capacity result exists. Approximated models have been introduced to study the exponential back-off mechanism, which seem to indicate an asymptotic capacity of ln(2)/2 when binary back-off is used, and again e-1 when the exponential base is optimized. Here we introduce a more accurate and flexible model that shows that past results miss their mark. In fact, we prove that with binary back-off the capacity is practically 0.370, slightly greater than e-1; furthermore, and more important, we prove that using 1.35 as exponential back-off base, the capacity reaches 0.4303 with an infinite number of users, and up to 0.496 with N = 2 users.
【Keywords】: Throughput; Stability criteria; Indexes; Asymptotic stability; Protocols; Mathematical model
【Paper Link】 【Pages】:1-9
【Authors】: Helei Cui ; Xingliang Yuan ; Yifeng Zheng ; Cong Wang
【Abstract】: Near-duplicate detection (NDD) plays an essential role for effective resource utilization and possible traffic alleviation in many emerging network architectures, leveraging in-network storage for various content-centric services. As innetwork storage grows, data security has become one major concern. Though encryption is viable for in-network data protection, current techniques are still lacking for effectively locating encrypted near-duplicate data, making the benefits of NDD practically invalidated. Besides, adopting encrypted innetwork storage further complicates the user authorization when locating near-duplicate data from multiple content providers under different keys. In this paper, we propose a secure and effective NDD system over encrypted in-network storage supporting multiple content providers. Our design bridges locality-sensitive hashing (LSH) with a newly developed cryptographic primitive, multi-key searchable encryption, which allows the user to send only one encrypted query to access near-duplicate data encrypted under different keys. It relieves the users from multiple rounds of interactions or sending multiple different queries respectively. As simply applying LSH does not ensure the detection quality, we then leverage Yao's garbled circuits to build a secure protocol to obtain highly accurate results, without user-side post-processing. We formally analyze the security strength. Experiments demonstrate our system achieves practical performance with comparable accuracy to plaintext.
【Keywords】: Servers; Encryption; Protocols; Authorization; Generators; Distributed databases
【Paper Link】 【Pages】:1-9
【Authors】: Xiaoqiang Pei ; Yijie Wang ; Xingkong Ma ; Fangliang Xu
【Abstract】: Erasure coding has received considerable attention due to the better tradeoff between the space efficiency and reliability. However, it consumes large network traffic and long time to complete the update, involving updates of both data nodes and parity nodes. Existing solutions to this problem mainly focus on proposing new class of codes with lower update complexity to reduce the network traffic, ignoring the optimization of data transmission structure. In fact, the data transmission structure has great impact on the update. In this paper, we propose T-Update, a tree-structured update scheme with top-down transmission that minimizes the update time for erasure-coded data with no additional network traffic. Specially, we propose a rack-aware tree construction technique to construct an update tree to organize the data connections, with the data node as the root and the parity nodes as the children. To maximize the update efficiency, we propose a top-down data transmission technique to guide the data transmission and distribute the data computation for updating the parity nodes. To evaluate the performance of T-Update, we conduct experiments on HDFS-RAID under various parameter settings on both 30 physical and 200 virtual servers. Extensive experiments confirm that T-Update reduces the update time by 27% and 32% on average compared with two typical update schemes respectively.
【Keywords】: Data communication; Maintenance engineering; Encoding; Reliability; Distributed databases; Bandwidth; Complexity theory
【Paper Link】 【Pages】:1-9
【Authors】: Zichen Xu ; Christopher Stewart ; Nan Deng ; Xiaorui Wang
【Abstract】: In cloud computing, workloads that lease instances on demand get to execute exclusively for a set time. In contrast, workloads that lease spot instances execute until a competing workload outbids the current lease. Spot instances cost less than on-demand instances, but few workloads can use spot instances because of the variable leasing period. We present BOSS, a framework that uses spot instances to reduce costs for in-memory storage workloads. BOSS uses on-demand instances to create and update objects. It uses spot instances to handle read-only queries. BOSS leases instances from multiple sites and exploits varying prices between the sites. When spot instances stop abruptly at one site, BOSS places newly created objects at other sites, reducing the impact on response time. BOSS proposes a novel, online replication approach (1) avoids placing data at too many sites and (2) provides O(1.5)-competitive ratio under skewed cost distributions. Within a site, BOSS manages the tradeoff between savings and risks from replicating to spot instances. We implemented BOSS on top of Cassandra and deployed it on up to 78 instances across 8 sites in Amazon and Google clouds. With BOSS hosting TPC-W data, we spent $8 per hour on Amazon. For the same service, we spent $55 per hour to use ElastiCache and $49 per hour to use on-demand instances only. BOSS saved 85% and 84% respectively. Further, BOSS achieved 95th percentile response time within 13% of ElastiCache.
【Keywords】: Cloud computing; Time factors; Google; Bandwidth; Mathematical model; Computers; Resumes
【Paper Link】 【Pages】:1-9
【Authors】: Thierry Titcheu Chekam ; Ennan Zhai ; Zhenhua Li ; Yong Cui ; Kui Ren
【Abstract】: As one type of the most popular cloud storage services, OpenStack Swift and its follow-up systems replicate each data object across multiple storage nodes and leverage object sync protocols to achieve high availability and eventual consistency. The performance of object sync protocols heavily relies on two key parameters: r (number of replicas for each object) and η (number of objects hosted by each storage node). In existing tutorials and demos, the configurations are usually r = 3 and n <; 1000 by default, and the object sync process seems to perform well. To deep understand object sync protocols, we first make a lab-scale OpenStack Swift deployment and run experiments with various configurations. We discover that in data-intensive scenarios, e.g., when r > 3 and n ≫ 1000, the object sync process is significantly delayed and produces massive network overhead. This phenomenon is referred to as the sync bottleneck problem. Then, to explore the root cause, we review the source code of OpenStack Swift and find that its object sync protocol utilizes a fairly simple and network-intensive approach to check the consistency among replicas of objects. In particular, each storage node is required to periodically multicast the hash values of all its hosted objects to all the other replica nodes. Thus in a sync round, the number of exchanged hash values per node is Θ(n×r). Further, to tackle the problem, we propose a lightweight object sync protocol called LightSync. It remarkably reduces the sync overhead by using two novel building blocks: 1) Hashing of Hashes, which aggregates all the h hash values of each data partition into a single but representative hash value with the Merkle tree; 2) Circular Hash Checking, which checks the consistency of different partition replicas by only sending the aggregated hash value to the clockwise neighbor. Its design provably reduces the per-node network overhead from Θ(n×r) to Θ(n/h). In addition, we have implemented LightSync as an open-source patch and adopted it to OpenStack Swift, thus reducing sync delay by up to 28.8× and network overhead by up to 14.2×.
【Keywords】: Synchronization; Cloud computing; Protocols; Delays; Servers; Open source software; Data models
【Paper Link】 【Pages】:1-9
【Authors】: Xiaofan He ; Huaiyu Dai ; Peng Ning ; Rudra Dutta
【Abstract】: Opportunistic resources are often present in various resource sharing networks for the users to exploit, but their qualities often change over time. Fortunately, many user tasks are delay-tolerant, which offers the network users a favorable degree of freedom in waiting for and accessing the opportunistic resource at the time of its best quality. For such delay-tolerant and opportunistic resource sharing networks (DT-ORS-Net), the corresponding optimal accessing strategies developed in existing literature mainly focus on the single-user scenarios, while the potential competition from other peer users in practical multi-user DT-ORS-Net is often ignored. Considering this, a multi-player Markov stopping game (M-MSG) is developed in this work, and the derived Nash equilibrium (NE) strategy of this M-MSG can guide network users to properly handle the potential competition from other peers and thus exploit the time diversity of the opportunistic resource more effectively, which in turn further improves the resource utilization efficiency. Applications in the cloud-computing and the mobile crowdsourcing networks are demonstrated to verify the effectiveness of the proposed method, and simulation results show that using the NE strategy of the proposed M-MSG can provide substantial performance gain as compared to using the conventional single-user optimal one.
【Keywords】: Cloud computing; Games; Markov processes; Mobile communication; Mobile computing; Resource management; Crowdsourcing
【Paper Link】 【Pages】:1-9
【Authors】: Abhijin Adiga ; Srini Venkat ; Anil Vullikanti
【Abstract】: Interventions such as vaccinations or installing anti-virus software are common strategies for controlling the spread of epidemics and malware on complex networks. Typically, nodes decide whether to implement such an intervention independently, depending on the costs they incur. A node can be protected by herd immunity, if enough other nodes implement such an intervention, making the problem of determining strategic decisions for vaccination a natural game-theoretical problem. There has been a lot of work on vaccination and network security game models, but all these models assume the vaccination decisions are made at the start of the game. However, in practice, a lot of individuals defer their vaccination decision, and the reasons for this behavior are not well understood, especially in network models. In this paper, we study a novel repeated game formulation, which considers vaccination decisions over time. We characterize Nash equilibria and the social optimum in such games, and find that a significant fraction of vaccinations might be deferred, in general. This depends crucially on the network structure, and the information and the vaccination delay. We show that finding Nash equilibria and the social optimum are NP-hard in general, and we develop an approximation algorithm for the social optimum whose approximation guarantee depends on the delay.
【Keywords】: Games; Malware; Delays; Biological system modeling; Vaccines; Complex networks
【Paper Link】 【Pages】:1-9
【Authors】: Benjamin Grimmer ; Sanjiv Kapoor
【Abstract】: We consider distributed network routing for networks that support differentiated services, where services are prioritized by a proportional weighting system. We use the classical Generalized Processor Sharing (GPS) scheme for scheduling traffic on network links. In such a scheme, each type of traffic is guaranteed a minimum capacity rate based on its priority. To model the performance of this scheme and to account for autonomous routing we consider scheduling games on networks. We consider both networks with a set of parallel links (which also applies to processor scheduling) and more general scenarios where the network is a multi-graph. In each of these settings we consider two different routing schemes: Atomic and Non-Atomic. Atomic routing requires all traffic of one type to follow a single path. Non-Atomic routing splits traffic into a flow over multiple paths. For each type of game, we prove either the existence of Nash Equilibrium or give a counterexample. We consider the inefficiency of equilibrium (termed as the price of anarchy) and provide price of anarchy upper bounds under reasonable assumptions. In general, this inefficiency in queuing systems is unbounded. We also provide complexity results on computing optimal solutions and the existence of equilibrium in these games.
【Keywords】: Games; Routing; Delays; Global Positioning System; Nash equilibrium; Processor scheduling; Servers
【Paper Link】 【Pages】:1-9
【Authors】: Parinaz Naghizadeh ; Mingyan Liu
【Abstract】: In a system of interdependent users, the security of an entity is affected not only by that user's effort towards securing her system, but also by the security decisions of other users. The provision of security in such environment is modeled as a public good provision problem, and is referred to as a security game. In this paper, we propose the notion of exit equilibrium to study users' voluntary participation in mechanisms for provision of non-excludable public goods. We show the fundamental result that, due to the non-excludable nature of security, there exists no reliable mechanism which can incentivize the socially optimal investment profile, while ensuring voluntary participation and maintaining a weakly balanced budget, for all instances of security games. To better understand the features of the games that lead to this result, we consider the class of weighted effort games, and apply the two well-known Pivotal (VCG) and Externality mechanisms. Through analysis and simulation, we identify the effects of several features of the problem environment, including diversity in user types, multiplicity of exit equilibria, and users' self-dependence levels, on the performance of these mechanisms.
【Keywords】: Security; Games; Investment; Finance; Optimized production technology; Cost function; Nash equilibrium
【Paper Link】 【Pages】:1-9
【Authors】: Lin Cui ; Richard Cziva ; Fung Po Tso ; Dimitrios P. Pezaros
【Abstract】: In modern Cloud Data Centers (DC)s, correct implementation of network policies is crucial to provide secure, efficient and high performance services for tenants. It is reported that the inefficient management of network policies accounts for 78% of DC downtime, challenged by the dynamically changing network characteristics and by the effects of dynamic Virtual Machine (VM) consolidation. While there has been significant research in policy and VM management, they have so far been treated as disjoint research problems. In this paper, we explore the simultaneous, dynamic VM and policy consolidation, and formulate the Policy-VM Consolidation (PVC) problem, which is shown to be NP-Hard. We then propose Sync, an efficient and synergistic scheme to jointly consolidate network policies and virtual machines. Extensive evaluation results and a testbed implementation of our controller show that policy and VM migration under Sync significantly reduces flow end-to-end delay by nearly 40%, and network-wide communication cost by 50% within few seconds, while adhering strictly to the requirements of network policies.
【Keywords】: Cloud computing; Virtual machining; Servers; Synchronization; Resource management; Security; Topology
【Paper Link】 【Pages】:1-9
【Authors】: Lei Yu ; Zhipeng Cai
【Abstract】: Network virtualization with bandwidth guarantee is essential for the performance predictability of cloud applications because of the shared multi-tenant nature of the cloud. Several virtual network abstractions have been proposed for the tenants to specify and reserve their virtual clusters with bandwidth guarantee. However, they require pre-determined fixed cluster size and bandwidth, and do not support the scaling of the cluster in size and bandwidth requirements. On the other hand, the existing works on virtual cluster scaling focus on dynamically adjusting the cluster size without considering any bandwidth guarantee targeted by current network abstractions. To fill the gap, this paper considers the problem of scaling up a virtual network abstraction with bandwidth guarantee. Efficient algorithms are proposed to find the valid allocation for the scaled cluster abstraction with optimization on the VM locality of the cluster. We also point out the case that a virtual cluster cannot be scaled without changing its original VM placement, and propose an optimal allocation algorithm that exploits the VM migration to address this issue while minimizing the total migration cost for the virtual cluster scaling. Extensive simulations demonstrate the effectiveness and efficiency of our algorithms.
【Keywords】: Bandwidth; Resource management; Cloud computing; Clustering algorithms; Heuristic algorithms; Hoses; Topology
【Paper Link】 【Pages】:1-9
【Authors】: Brent Stephens ; Alan L. Cox
【Abstract】: Today, given data center networks' sizes and bursty workloads, it is likely that at any moment there is packet loss due to some type of failure in the network. This paper focuses on solving the two most common types of data center network failures: congestion and routing failures. Recently, there has been demand for lossless Ethernet (DCB) in data center networks as a solution to congestion failures. However, DCB complicates fault tolerance by introducing a new type of failure, deadlock. If DCB is enabled, then all routing must be deadlock free. To the best of our knowledge, this paper describes the first ever deadlock-free approaches to local fast failover that can be combined with DCB, DF-FI and DF-EDST resilience. Moreover, in the evaluation, this paper shows that DF-EDST resilience, which is the paper's main contribution, can improve fault tolerance without adversely impacting performance when compared to a state-of-the-art approach to deadlock-free routing. If, however, a small reduction in aggregate throughput is acceptable, then it is possible to build routes such that only 0.00001% of the total flows in the network are likely to fail given 16 edge failures on networks with 1K-4K hosts.
【Keywords】: System recovery; Routing; Resilience; Topology; Fault tolerance; Fault tolerant systems; Ports (Computers)
【Paper Link】 【Pages】:1-9
【Authors】: Tao Wang ; Fangming Liu ; Jian Guo ; Hong Xu
【Abstract】: Software defined networking is becoming increasingly prevalent in data center networks for its programmability that enables centralized network configuration and management. However, since switches are statically assigned to controllers, traffic dynamics cause load imbalance among the controllers. As a result, some controllers are not fully utilized, while switches connected to overloaded controllers may experience long response times. In this paper, we consider dynamic controller assignment so as to minimize the average response time of the control plane. We formulate this problem as a stable matching problem with transfers, and propose a hierarchically two-phase algorithm that integrates key concepts from both matching theory and coalitional games to solve it efficiently. Theoretical analysis proves that our algorithm converges to a near-optimal Nash stable solution within tens of iterations. Extensive simulations show that our approach reduces response time by about 86%, and achieves better load balancing among controllers compared to static assignment.
【Keywords】: Control systems; Time factors; Games; Process control; Load modeling; Heuristic algorithms; Topology
【Paper Link】 【Pages】:1-9
【Authors】: Xiang-Fa Guo ; Mobashir Mohammad ; Sudipta Saha ; Mun Choon Chan ; Seth Gilbert ; Derek Leong
【Abstract】: Time synchronization is an enabling service that allows devices to share a consistent notion of time and thus makes it easier to build efficient and robust collaborative services. However, existing synchronization protocols based on wireless packet transmissions are not energy efficient because powering the radio often consumes a significant fraction of the energy budget. In this paper, we propose PSync, a visible light-based time synchronization protocol that relies on an LED light source and is highly energy efficient for the receivers. The key novelty in our protocol is the use of a De Bruijn sequence to provide a rough estimate of time using a minimum amount of information. Experiments show that our scheme achieves an average synchronization error of 1.3 timer ticks (32 μs per clock tick). In addition, the additional energy consumed for one round of synchronization based on PSync can be as low as 19% of the energy needed to receive a small packet (1 byte) using IEEE 802.15.4 radio.
【Keywords】: Synchronization; Receivers; Sensors; Light emitting diodes; Light sources; Media Access Protocol
【Paper Link】 【Pages】:1-9
【Authors】: Palanivel A. Kodeswaran ; Ravindranath Kokku ; Madhumita Mallick ; Sayandeep Sen
【Abstract】: Powered by the emergence of the Internet of Things, smart homes containing a variety of sensors and actuators are expected to monitor and react to the activities of the residents with the goal of improving convenience, comfort and safety. However, in typical home settings, each human Activity of Daily Living (ADL) generates events from multiple sensors, and each sensor is triggered by multiple ADLs. Consequently, achieving high detection accuracy in these complex environments requires large amounts of training data for every possible multiplexing scenario, making it a complex problem. In this paper, we propose a data driven three-step de-multiplexing approach that simplifies the ADL recognition problem by first segmenting the event stream into periods of interest, before feeding to a classifier. We mine datasets to identify salient features which allow us to achieve a good segmentation. Extensive evaluation on ten public datasets shows that our approach achieves upto 77% segmentation accuracy, and a activity detection accuracy within 91% of the best possible.
【Keywords】: Intelligent sensors; Sensor phenomena and characterization; Smart homes; Frequency division multiplexing; Internet of things; Monitoring
【Paper Link】 【Pages】:1-9
【Authors】: Arjun Bakshi ; Lu Chen ; Kannan Srinivasan ; Can Emre Koksal ; Atilla Eryilmaz
【Abstract】: The future Internet of Things (IoT) networks are expected to be composed of a large population of low-cost devices communicating dynamically with access points or neighboring devices to communicate small bundles of delay-sensitive data. To support the high-intensity and short-lived demands of these emerging networks, we propose an Efficient MAC paradigm for IoT (EMIT). Our paradigm bypasses the high overhead and coordination costs of existing MAC solutions by employing an interference-averaging strategy that allow users to share their resources simultaneously. In contrast to the predominant interference-suppressing approaches, EMIT exploits the dense and dynamic nature of IoT networks to reduce the spatio-temporal variability of interference to achieve low-delay and high-reliability in service. This paper introduces foundational ideas of EMIT by characterizing the global interference statistics in terms of single-device operation and develops power-rate allocation strategies to guarantee low-delay high-reliability performance. A significant portion of our work is aimed at validating these theoretical principles in experimental testbeds, where we compare the performance of EMIT to a CSMA-based MAC protocol. Our comparisons confirm the beneficial characteristics of EMIT, and reveal significant gains over CSMA strategies in the case of IoT traffic.
【Keywords】: Interference; Internet of things; Multiaccess communication; Delays; Physical layer; Media Access Protocol; Intelligent sensors
【Paper Link】 【Pages】:1-9
【Authors】: Md Abdullah Al Hafiz Khan ; Ruthvik Kukkapalli ; Piyush Waradpande ; Sekar Kulandaivel ; Nilanjan Banerjee ; Nirmalya Roy ; Ryan Robucci
【Abstract】: Activity recognition has applications in a variety of human-in-the-loop settings such as smart home health monitoring, green building energy and occupancy management, intelligent transportation, and participatory sensing. While fine-grained activity recognition systems and approaches help enable a multitude of novel applications, discovering them with non-intrusive ambient sensor systems pose challenging design, as well as data processing, mining, and activity recognition issues. In this paper, we develop a low-cost heterogeneous Radar based Activity Monitoring (RAM) system for recognizing fine-grained activities. We exploit the feasibility of using an array of heterogeneous micro-doppler radars to recognize low-level activities. We prototype a short-range and a long-range radar system and evaluate the feasibility of using the system for fine-grained activity recognition. In our evaluation, using real data traces, we show that our system can detect fine-grained user activities with 92.84% accuracy.
【Keywords】: Doppler radar; Random access memory; Legged locomotion; Feature extraction; IEEE 802.11 Standard
【Paper Link】 【Pages】:1-9
【Authors】: Markus Fidler ; Yuming Jiang
【Abstract】: Parallel systems have received increasing attention with numerous recent applications such as fork-join systems, load-balancing, and l-out-of-k redundancy. Common to these systems is a join or resequencing stage, where tasks that have finished service may have to wait for the completion of other tasks so that they leave the system in a predefined order. These synchronization constraints make the analysis of parallel systems challenging and few explicit results are known. In this work, we model parallel systems using a max-plus approach that enables us to derive statistical bounds of waiting and sojourn times. Taking advantage of max-plus system theory, we also show end-to-end delay bounds for multi-stage fork-join networks. We contribute solutions for basic G|G|1 fork-join systems, parallel systems with load-balancing, as well as general (k, l) fork-join systems with redundancy. Our results provide insights into the respective advantages of l-out-of-k redundancy vs. load-balancing.
【Keywords】: Servers; Delays; Synchronization; Load modeling; Redundancy; Routing; Load management
【Paper Link】 【Pages】:1-9
【Abstract】: This paper studies information source detection in networks under the independent cascade (IC) model. Assume the spread of information starts from a single source in a network and a complete snapshot of the network is obtained at some time. The goal is to identify the source based on the observation. We derive the maximum a posterior (MAP) estimator of the source for tree networks and propose a Short-Fat Tree (SFT) algorithm for general networks based on the MAP estimator. The algorithm selects the Jordan infection center [1] and breaks ties according the degree of boundary infected nodes. Loosely speaking, the algorithm selects the node such that the breadth-first search (BFS) tree from it has the minimum depth but the maximum number of leaf nodes. On the Erdos-Renyi (ER) random graph, we establish the following possibility and impossibility results: (i) when the infection duration <; log n/(1 + α)log μ for some α > 0.5, SFT identifies the source with probability 1 (w.p.1) asymptotically (as network size increases to infinity), where n is the network size and μ is the average node degree; (ii) when the infection duration > ⌈log n/ log μ ⌉ + 2, the probability of identifying the source approaches zero asymptotically under any algorithm; and (iii) when infection duration <; <; log n/(1 + α)log μ for some α > 0, asymptotically, at least 1-δ fraction of the nodes on the BFS tree starting from the source are leaf-nodes, where δ = 3√log n/μ, i.e., the BFS tree starting from the actual source is a fat tree. 1Numerical experiments on tree networks, the ER random graphs and real world networks with different evaluation metrics show that the SFT algorithm outperforms existing algorithms.
【Keywords】: Integrated circuit modeling; Heuristic algorithms; Erbium; Algorithm design and analysis; Analytical models; Maximum likelihood estimation
【Paper Link】 【Pages】:1-9
【Authors】: Ran Ben-Basat ; Gil Einziger ; Roy Friedman ; Yaron Kassner
【Abstract】: Identifying heavy hitter flows is a fundamental problem in various network domains. The well established method of using sketches to approximate flow statistics suffers from space inefficiencies. In addition, flow arrival rates are dynamic, thus keeping track of the most recent heavy hitters poses a challenge. Sliding window approximations address this problem, reducing space at the cost of increasing point query time. This paper presents two novel algorithms for identifying heavy hitters in streams and sliding windows. Both algorithms use statically allocated memory and support constant time point queries. For sliding windows, this is an asymptotic improvement over previous work. We also demonstrate reduced memory requirements of up to 85% in streams and 66% in sliding windows over synthetic and real Internet packet traces.
【Keywords】: Radiation detectors; Cascading style sheets; Memory management; Data structures; Frequency estimation; Heuristic algorithms; Estimation
【Paper Link】 【Pages】:1-9
【Authors】: Zhan Qiu ; Juan F. Pérez ; Peter G. Harrison
【Abstract】: Processing time variability is commonplace in distributed systems, where resources display disparate performance due to, e.g., different workload levels, background processes, and contention in virtualized environments. However, it is paramount for service providers to keep variability in response time under control in order to offer responsive services. We investigate how request replication can be used to exploit processing time variability to reduce response times, considering not only mean values but also the tail of the response time distribution. We focus on the distributed setup, where replication is achieved by running copies of requests on multiple servers that otherwise evolve independently, and waiting for the first replica to complete service. We construct models that capture the evolution of a system with replicated requests using approximate methods and observe that highly variable service times offer the best opportunities for replication - reducing the response time tail in particular. Further, the effect of replication is non-uniform over the response time distribution: gains in one metric, e.g., the mean, can be at the cost of another, e.g., the tail percentiles. This is demonstrated in wide range of numerical virtual experiments. It can be seen that capturing service time variability is key to the evaluation of latency tolerance strategies and in their design.
【Keywords】: Time factors; Servers; Delays; Transient analysis; Electronic mail; Google
【Paper Link】 【Pages】:1-9
【Authors】: Timothy J. Pierson ; Xiaohui Liang ; Ronald A. Peterson ; David Kotz
【Abstract】: Nearly every setting is increasingly populated with wireless and mobile devices - whether appliances in a home, medical devices in a health clinic, sensors in an industrial setting, or devices in an office or school. There are three fundamental operations when bringing a new device into any of these settings: to configure the device to join the wireless local-area network, to partner the device with other nearby devices so they can work together, and (3) to configure the device so it connects to the relevant individual or organizational account in the cloud. The challenge is to accomplish all three goals simply, securely, and consistent with user intent. We present a novel approach we call Wanda - a `magic wand' that accomplishes all three of the above goals - and evaluate a prototype implementation.
【Keywords】: Transmitting antennas; Biomedical monitoring; Antenna measurements; Wireless communication; Blood pressure; Communication system security
【Paper Link】 【Pages】:1-9
【Authors】: Chen Song ; Aosen Wang ; Kui Ren ; Wenyao Xu
【Abstract】: As mobile technology grows rapidly, the smartphone has become indispensable for transmitting private user data, storing the sensitive corporate files, and conducting secure payment transactions. However, with mobile security research lagging, smartphones are extremely vulnerable to unauthenticated access. In this paper, we present, EyeVeri, a novel eye-movement-based authentication system for smartphone security protection. Specifically, EyeVeri tracks human eye movement through the built-in front camera and applies the signal processing and pattern matching techniques to explore volitional and non-volitional gaze patterns for access authentication. Through a comprehensive user study, EyeVeri performs well and is a promising approach for smartphone user authentication. We also discuss the evaluation results in-depth and analyze opportunities for future work.
【Keywords】: Authentication; Biometrics (access control); Visualization; Iris; Feature extraction; Muscles
【Paper Link】 【Pages】:1-9
【Authors】: Zhen Ling ; Junzhou Luo ; Qi Chen ; Qinggang Yue ; Ming Yang ; Wei Yu ; Xinwen Fu
【Abstract】: Various attacks may disclose sensitive information such as passwords of mobile devices. Residue-based attacks exploit oily or heat residues on the touch screen, computer vision based attacks analyze the hand movement on a keyboard, and sensor based attacks measure a device's motion difference via motion sensors as different keys are tapped. A randomized soft keyboard may defeat these attacks. However, a randomized key layout is counter-intuitive and users may be reluctant to adopt it. In this paper, we introduce a novel and intuitive input system, secure finger mouse, which uses a mobile device's camera sensing the fingertip movement, moves an on-screen cursor and performs clicks by sensing click gestures. We design a randomized mouse acceleration algorithm so that the adversary cannot infer keys clicked on the soft keyboard by observing the finger movement. The secure finger mouse can defeat attacks including residue, computer vision and motion based attacks too. We perform both theoretical analysis and real-world experiments to demonstrate the security and usability of the secure fingertip mouse.
【Keywords】: Mice; Mobile handsets; Keyboards; Skin; Acceleration; Cameras; Aerospace electronics
【Paper Link】 【Pages】:1-9
【Authors】: Dahee Jeong ; Minkyoung Cho ; Omprakash Gnawali ; HyungJune Lee
【Abstract】: In this paper, we consider the problem of distributing patrol officers inside a building to maximize the probability of catching multiple intruders while minimizing the distance the patrol officers travel to reach the locations of the intruders. In our problem setting, the patrol officers are assisted by the information collected by a network of binary proximity sensors installed in the building. We claim that learning even common movement sub-patterns that originate due to the constrained physical environment helps to find likely locations of intruders where each major location is instrumented using a sensor node. We use a series of binary detection events to infer likely future trajectories in a real-world building. For a given set of detectable nodes on the inferred future trajectories, we aim to find the optimal patrol dispatch node location with high exposure to intruders' future appearance using patrol officers in limited numbers, ideally fewer than the intruders. In order to prevent possible crime and perform responsive defense against potential intruders, our algorithm also tries to reduce the travel distance from patrols current positions to their dispatched positions at the same time. We validate our proposed scheme in terms of detection accuracy by varying the number of intruders, robustness against missing events, and responsiveness compared to a practical baseline counterpart through real-world system experiments.
【Keywords】: Buildings; Surveillance; Trajectory; Mobile communication; Sensor systems; Security
【Paper Link】 【Pages】:1-9
【Authors】: Avik Ray ; Supratim Deb ; Pantelis Monogioudis
【Abstract】: As cellular networks like 4G LTE networks get more and more sophisticated, mobiles also measure and send enormous amount of mobile measurement data (in TBs/week/metropolitan) during every call and session. The mobile measurement records are saved in data center for further analysis and mining, however, these measurement records are not geo-tagged because the measurement procedures are implemented in mobile LTE stack. Geo-tagging (or localizing) the stored measurement record is a fundamental building block towards network analytics and troubleshooting since the measurement records contain rich information on call quality, latency, throughput, signal quality, error codes etc. In this work, our goal is to localize these mobile measurement records. Precisely, we answer the following question: what was the location of the mobile when it sent a given measurement record? We design and implement novel machine learning based algorithms to infer whether a mobile was outdoor and if so, it infers the latitude-longitude associated with the measurement record. The key technical challenge comes from the fact that measurement records do not contain sufficient information required for triangulation or RF fingerprinting based techniques to work by themselves. Experiments performed with real data sets from an operational 4G network in a major metropolitan show that, the median accuracy of our proposed solution is around 20 m for outdoor mobiles and outdoor classification accuracy is more than 98%.
【Keywords】: Mobile communication; Radio frequency; Mobile computing; Radio transmitters; Machine learning algorithms; Robots; Velocity measurement
【Paper Link】 【Pages】:1-9
【Authors】: Zhao Li ; Sha Cui ; Kang G. Shin ; Jun Gu
【Abstract】: Both interference alignment (IA) and interference neutralization (IN) are exploited for Coordinated Multi-Point (CoMP) transmissions. With the base station's cooperation, transmit precoder and receive filter are designed jointly, and then concurrent transmissions of multiple data streams are achieved. In the design of preprocessing, IN is applied to the interferences carrying same data so as to align the interfering signals with opposite directions in a subspace. On the other hand, for interferences carrying different information, IA is employed to align them with the same direction in a subspace, thus reducing the interference signal dimension observed at the user side. Based on different precoding schemes at the transmitter's side, receivers adopt zero-forcing (ZF) so as to recover the desired data. The proposed interference alignment and neutralization based CoMP (IAN-CoMP) mechanism can achieve effective interference cancellation and suppression by exploiting limited and flexible collaboration only at the base station (BS) side. We also extend the mechanism to general cases where the antenna configurations at both transmitter and receiver side, the number of transmitters participating in CoMP and simultaneously served users are variable. In addition, the proposed scheme can also achieve a flexible tradeoff between cooperation overhead and the system's achievable degrees of freedom (DoFs). Our in-depth simulation results show that IAN-CoMP can significantly improve the spectral efficiency (SE) for cell-edge users.
【Keywords】: Interference; Relays; Transmitters; Downlink; Precoding; Receiving antennas
【Paper Link】 【Pages】:1-9
【Authors】: Arash Asadi ; Vincenzo Mancuso ; Rohit Gupta
【Abstract】: Device-to-Device communications represent a paradigm shift in cellular networks. Analytical results on D2D performance are very promising, but there is no experimental evidence that validates these results to date. This paper is the first to provide an experimental analysis of outband D2D schemes. Moreover, we design DORE, a complete framework for handling channel opportunities offered by outband D2D relay nodes. DORE consists of resource allocation optimization tools and protocols suitable to integrate QoS-aware opportunistic D2D communications within the architecture of 3GPP Proximity-based Services. We implement DORE using an SDR framework to profile cellular network dynamics in presence of opportunistic outband D2D communication schemes. Our experiments reveal that outband D2D communications are suitable for a large variety of delay-sensitive cellular applications, and that DORE enables notable gains even with a few active D2D relay nodes.
【Keywords】: Relays; Receivers; Throughput; Quality of service; 3GPP; Delays; Complexity theory
【Paper Link】 【Pages】:1-9
【Authors】: Antonis Dimakis ; Spyros Papafragkos
【Abstract】: For CDMA cell-based systems we propose an uplink power control scheme for low data packet queueing delay. The scheme can be seen as a simple extension to the Foschini-Miljanic algorithm which takes the transmit queue sizes at the mobile stations into account. The proposed scheme minimizes the draining time compared to all other policies with the same power consumption. This is because of resource pooling effects which arise when all queues empty at the same time. Although in CDMA systems there is no idle capacity as in wired systems, greater cummulative service is obtained by simultaneous transmissions than through time-sharing. Simulations exhibit significant reductions in queueing delay compared to other power control schemes proposed in the literature.
【Keywords】: Delays; Power control; Multiaccess communication; Interference; Signal to noise ratio; Uplink; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Ting He ; Liang Ma ; Athanasios Gkelias ; Kin K. Leung ; Ananthram Swami ; Don Towsley
【Abstract】: We consider the problem of placing the minimum number of monitors in a communication network with possible topology changes to identify additive link metrics from path metrics. The core of our solution is a suite of robust monitor placement algorithms with different performance-complexity tradeoffs that guarantee network identifiability for the multiple possible topologies. In particular, we show that the optimal (i.e., minimum) monitor placement is the solution to a generalized hitting set problem, where we provide a polynomial-time algorithm to construct the input. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. We further demonstrate how the proposed algorithms can be augmented to handle unpredictable topology changes and tradeoffs between monitor cost and adaptation cost. Our evaluations on mobility-induced dynamic topologies verify the effectiveness and robustness of the proposed algorithms.
【Keywords】: Monitoring; Network topology; Topology; Measurement; Robustness; Heuristic algorithms; Tomography
【Paper Link】 【Pages】:1-9
【Abstract】: Network tomography is an attractive approach for inferring internal network states at edge nodes. Recently, there is a growing interest in the basic understanding of the topological conditions that ensure identifiability in a general network. Un, existing works assume an ideal network model where all network elements are reliable. In this paper, we are aiming to propose topological conditions to ensure identifiability in the presence of any k link failures (k ≥ 0), using measurement paths and cycles. We propose a novel concept called k-identifiability. We propose sufficient and necessary topological conditions to ensure k-identifiability. Based on the established theoretical foundations, we propose two efficient polynomial-time algorithms for addressing two closely related questions. (1) Given a network with specified monitors, which links are k-identifiable? (2) Given a network and κ monitors, where should these monitors be placed such that the number of k-identifiable links is maximized? Simulation results on real ISP network topologies show the effectiveness of our algorithms.
【Keywords】: Monitoring; Measurement; Tomography; Network topology; Additives; Reliability; Merging
【Paper Link】 【Pages】:1-9
【Authors】: Konstantin Avrachenkov ; Philippe Jacquet ; Jithin K. Sreedharan
【Abstract】: In this paper we address the problem of finding top k eigenvalues and corresponding eigenvectors of symmetric graph matrices in networks in a distributed way. We propose a novel idea called complex power iterations in order to decompose the eigenvalues and eigenvectors at node level, analogous to time-frequency analysis in signal processing. At each node, eigenvalues correspond to the frequencies of spectral peaks and respective eigenvector components are the amplitudes at those points. Based on complex power iterations and motivated from fluid diffusion processes in networks, we devise distributed algorithms with different orders of approximation. We also introduce a Monte Carlo technique with gossiping which substantially reduces the computational overhead. An equivalent parallel random walk algorithm is also presented. We validate the algorithms with simulations on real-world networks. Our formulation of the spectral decomposition can be easily adapted to a simple algorithm based on quantum random walks. With the advent of quantum computing, the proposed quantum algorithm will be extremely useful.
【Keywords】: Eigenvalues and eigenfunctions; Signal processing algorithms; Symmetric matrices; Matrix decomposition; Quantum computing; Algorithm design and analysis; Approximation algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Hung T. Nguyen ; Thang N. Dinh ; My T. Thai
【Abstract】: Online social networks have been one of the most effective platforms for marketing and advertising. Through the “world-of-mouth” exchanges, so-called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the Influence Maximization (IM) problem that seeks a set of k seed users that maximize the expected influence. Unfortunately, IM encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called Cost-aware Targeted Viral Marketing (CTVM), to find the most cost-effective seed users who can influence the most relevant users to the advertisement. Since CTVM is NP-hard, we design an efficient (1 - 1/√e-ϵ - e)-approximation algorithm, named BCT, to solve the problem in billion-scale networks. Comparing with IM algorithms, we show that BCT is both theoretically and experimentally faster than the state-of-the-arts while providing better solution quality. Moreover, we prove that under the Linear Threshold model, BCT is the first sub-linear time algorithm for CTVM (and IM) in dense networks. In our experiments with a Twitter dataset, containing 1.46 billions of social relations and 106 millions tweets, BCT can identify key influencers in each trending topic in only few minutes.
【Keywords】: Approximation algorithms; Integrated circuit modeling; Twitter; Electronic mail; Companies
【Paper Link】 【Pages】:1-9
【Authors】: Kianoosh Mokhtarian ; Hans-Arno Jacobsen
【Abstract】: Video Content Distribution Networks (CDNs) serve a significant fraction of the Internet traffic through a global network of cache servers. In a planet-scale CDN with millions of videos, cache servers only consider their own request patterns for managing their content. We analyze how, in the absence of cooperative caching, the knowledge of requests in remote serving locations can lead to better caching decisions overall and can reduce serving costs. We call this practice cache coordination. Our analyses in this paper are based on actual video workload data from a global CDN. We analyze the spatial correlation of video popularities worldwide, the effectiveness and feasibility of cache coordination, and its scalability: from a city to across countries.
【Keywords】: Servers; Videos; Correlation; Internet; Urban areas; Scalability; Content distribution networks
【Paper Link】 【Pages】:1-9
【Authors】: M. Zubair Shafiq ; Amir R. Khakpour ; Alex X. Liu
【Abstract】: Content Delivery Networks (CDNs) have emerged as a dominant mechanism to deliver content over the Internet. Despite their importance, to our best knowledge, large-scale analysis of CDN cache performance is lacking in prior literature. A CDN serves many content publishers simultaneously and thus has unique workload characteristics; it typically deals with extremely large content volume and high content diversity from multiple content publishers. CDNs also have unique performance metrics; other than hit ratio, CDNs also need to minimize network and disk load on cache servers. In this paper, we present measurement and analysis of caching workload at a large commercial CDN. Using detailed logs from four geographically distributed CDN cache servers, we analyze over 600 million content requests accounting for more than 1.3 petabytes worth of traffic. We analyze CDN workload from a wide range of perspectives, including request composition, size, popularity, and temporal dynamics. Using real-world logs, we also evaluate cache replacement algorithms, including two enhancements designed based on our CDN workload analysis: N-hit and content-aware caching. The results show that these enhancements achieve substantial performance gains in terms of cache hit ratio, disk load, and origin traffic volume.
【Keywords】: Streaming media; Servers; Measurement; Image coding; Internet; Aggregates; Social network services
【Paper Link】 【Pages】:1-9
【Authors】: Mathieu Leconte ; Georgios S. Paschos ; Lazaros Gkatzikis ; Moez Draief ; Spyridon Vassilaras ; Symeon Chouvardas
【Abstract】: This paper addresses a fundamental limitation for the adoption of caching for wireless access networks due to small population sizes. This shortcoming is due to two main challenges: making timely estimates of varying content popularity and inferring popular content from small samples. We propose a framework which alleviates such limitations. To timely estimate varying popularity in a context of a single cache we propose an Age-Based Threshold (ABT) policy which caches all contents requested more times than a threshold N (τ), where τ is the content age. We show that ABT is asymptotically hit rate optimal in the many contents regime, which allows us to obtain the first characterization of the optimal performance of a caching system in a dynamic context. We then address small sample sizes focusing on L local caches and one global cache. On the one hand we show that the global cache learns L times faster by aggregating all requests from local caches, which improves hit rates. On the other hand, aggregation washes out local characteristics of correlated traffic which penalizes hit rate. This motivates coordination mechanisms which combine global learning of popularity scores in clusters and Least-Recently-Used (LRU) policy with prefetching.
【Keywords】: Sociology; Statistics; Prefetching; Base stations; Context; Wireless networks
【Paper Link】 【Pages】:1-9
【Authors】: Suoheng Li ; Jie Xu ; Mihaela van der Schaar ; Weiping Li
【Abstract】: This paper presents a novel cache replacement method - Popularity-Driven Content Caching (PopCaching). PopCaching learns the popularity of content and uses it to determine which content it should store and which it should evict from the cache. Popularity is learned in an online fashion, requires no training phase and hence, it is more responsive to continuously changing trends of content popularity. We prove that the learning regret of PopCaching (i.e., the gap between the hit rate achieved by PopCaching and that by the optimal caching policy with hindsight) is sublinear in the number of content requests. Therefore, PopCaching converges fast and asymptotically achieves the optimal cache hit rate. We further demonstrate the effectiveness of PopCaching by applying it to a movie.douban.com dataset that contains over 38 million requests. Our results show significant cache hit rate lift compared to existing algorithms, and the improvements can exceed 40% when the cache capacity is limited. In addition, PopCaching has low complexity.
【Keywords】: Databases; Context; Forecasting; Training; Streaming media; Servers; Algorithm design and analysis
【Paper Link】 【Pages】:1-9
【Authors】: Jonnahtan Saltarin ; Eirina Bourtsoulatze ; Nikolaos Thomos ; Torsten Braun
【Abstract】: Content-Centric Networking (CCN) naturally supports multi-path communication, as it allows the simultaneous use of multiple interfaces (e.g. LTE and WiFi). When multiple sources and multiple clients are considered, the optimal set of distribution trees should be determined in order to optimally use all the available interfaces. This is not a trivial task, as it is a computationally intense procedure that should be done centrally. The need for central coordination can be removed by employing network coding, which also offers improved resiliency to errors and large throughput gains. In this paper, we propose NetCodCCN, a protocol for integrating network coding in CCN. In comparison to previous works proposing to enable network coding in CCN, NetCodCCN permits Interest aggregation and Interest pipelining, which reduce the data retrieval times. The experimental evaluation shows that the proposed protocol leads to significant improvements in terms of content retrieval delay compared to the original CCN. Our results demonstrate that the use of network coding adds robustness to losses and permits to exploit more efficiently the available network resources. The performance gains are verified for content retrieval in various network scenarios.
【Keywords】: Network coding; Face; IEEE 802.11 Standard; Protocols; Network topology; Robustness; Internet
【Paper Link】 【Pages】:1-9
【Authors】: Liang-Hao Huang ; Hsiang-Chun Hsu ; Shan-Hsiang Shen ; De-Nian Yang ; Wen-Tsuen Chen
【Abstract】: Although Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, current literature mostly focuses on unicast communications. Compared to traffic engineering for multiple unicast flows, multicast traffic engineering for multiple trees is very challenging not only because minimizing the bandwidth consumption of a single multicast tree by solving the Steiner tree problem is already NP-Hard, but the Steiner tree problem does not consider the link capacity constraint for multicast flows and node capacity constraint to store the forwarding entries in Group Table of OpenFlow. In this paper, therefore, we first study the hardness results of scalable multicast traffic engineering in SDN. We prove that scalable multicast traffic engineering with only the node capacity constraint is NP-Hard and not approximable within δ, which is the number of destinations in the largest multicast group. We then prove that scalable multicast traffic engineering with both the node and link capacity constraints is NP-Hard and not approximable within any ratio. To solve the problem, we design a δ-approximation algorithm, named Multi-Tree Routing and State Assignment Algorithm (MTRSA), for the first case and extend it to the general multicast traffic engineering problem. The simulation and implementation results demonstrate that the solutions obtained by the proposed algorithm outperform the shortest-path trees and Steiner trees. Most importantly, MTRSA is computation-efficient and can be deployed in SDN since it can generate the solution with numerous trees in a short time.
【Keywords】: Unicast; Bandwidth; Routing; Steiner trees; Tunneling; Control systems; Scalability
【Paper Link】 【Pages】:1-9
【Authors】: Zhenhua Han ; Haisheng Tan ; Guihai Chen ; Rui Wang ; Yifan Chen ; Francis C. M. Lau
【Abstract】: Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs' resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs' resource demands. Most approaches in the latter category are heuristical and lack theoretical performance guarantees. In this work, we formulate dynamic VM management as a large-scale Markov Decision Process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, MadVM can be implemented in a distributed system, which should suit the needs of real data centers. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.
【Keywords】: Power demand; Servers; Markov processes; Dynamic scheduling; Resource management; Energy consumption; Heuristic algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Haipeng Dai ; Yunhuai Liu ; Alex X. Liu ; Lingtao Kong ; Guihai Chen ; Tian He
【Abstract】: Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we optimize our scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than (1 - ϵ) of the optimal solution to PESA with a smaller EMR threshold (1 - ϵ/2)Rt and a larger EMR coverage radius (1 + ϵ/2)D. We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the prior art by up to 45.7%.
【Keywords】: Safety; Wireless communication; Wireless sensor networks; Approximation algorithms; Partitioning algorithms; Inductive charging; Aggregates
【Paper Link】 【Pages】:1-9
【Authors】: Gyan Ranjan ; Alok Tongaonkar ; Ruben Torres
【Abstract】: We present AMPLES, Approximate Matching of Persistent LExicon using Search-Engines, to address the Mobile-Application-Identification (MApId) problem in network traffic at a per-flow granularity. We transform MApId into an information-retrieval problem where lexical similarity of short-text-documents is used as a metric for classification tasks. Specifically, a network-flow, observed at an intercept-point, is treated as a semi-structured-text-document and modified into a flow-query. This query is then run against a corpus of documents pre-indexed in a search-engine. Each index-document represents an application, and consists of distinguishable identifiers from the metadata-file and URL-strings found in the application's executable-archive. The search-engine acts as a kernel function, generating a score distribution vis-'a-vis the index-documents, to determine a match. This extends the scope of MApId to fuzzy-classification mapping a flow to a family of apps when the score distribution is spread-out. Through experiments over an emulator-generated test-dataset (400 K applications and 13.5 million flows), we obtain over 80% flow coverage and about 85% application coverage with low false-positives (4%) and nearly no false-negatives. We also validate our methodology over a real network trace. Most importantly, our methodology is platform agnostic, and subsumes previous studies, most of which focus solely on the application coverage.
【Keywords】: Mobile communication; Androids; Humanoid robots; Mobile applications; Linux; Uniform resource locators; Smart phones
【Paper Link】 【Pages】:1-9
【Authors】: Xi Liu ; Han Hee Song ; Mario Baldi ; Pang-Ning Tan
【Abstract】: Thanks to the widespread use of smart devices, recent years have witnessed the proliferation of mobile apps available on online stores such as Apple iTunes and Google Play. As the number of new mobile apps continues to grow at a rapid pace, automatic classification of the apps has become an increasingly important problem to facilitate browsing, searching, and recommending them. This paper presents a framework that automatically labels apps with a richer and more detailed categorization and uses the labeled apps to study the app market. Leveraging a fine-grained, hierarchical ontology as a guide, we developed a framework not only to label the apps with fine-grained categorical information but also to induce a customized class hierarchy optimized for mobile app classification. With the classification accuracy of 93%, large-scale categorization conducted with our framework on 168,000 Google Play apps discovers novel inter-class relationships among categories of Google Play market.
【Keywords】: Mobile communication; Google; Games; Business; Labeling; Ontologies; Education
【Paper Link】 【Pages】:1-9
【Authors】: Apostolos Destounis ; Georgios S. Paschos ; Iordanis Koutsopoulos
【Abstract】: We study network response to a stream of queries that require computations on remotely located data, and we seek to characterize the network performance limits in terms of maximum sustainable query rate that can be satisfied. The available network setup consists of (i) a communication network graph with finite-bandwidth links over which data is routed, (ii) computation nodes with certain computation capacity, over which computation load is balanced, and (iii) network nodes that need to schedule raw and processed data transmissions. Our aim is to design a universal methodology and distributed algorithm to adaptively allocate resources in order to support maximum query rate. The proposed algorithms extend in a nontrivial way the backpressure (BP) algorithm to take into account computations carried out in the presence of query streams. They contribute to the fundamental understanding of network computation performance limits when the query rate is limited by both the communication bandwidth and the computation capacity, a classical setting that arises in streaming big data applications in network clouds and fogs.
【Keywords】: Bandwidth; Routing; Algorithm design and analysis; Cloud computing; Resource management; Real-time systems; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Boyang Wang ; Yantian Hou ; Ming Li
【Abstract】: Nearest neighbor search (or k-nearest neighbor search in general) is one of the most fundamental queries on massive datasets, and it has extensive applications such as pattern recognition, statistical classification, graph algorithms, Location-Based Services and online recommendations. With the raising trend of outsourcing massive sensitive datasets to public clouds, it is urgent for companies and organizations to demand fast and secure nearest neighbor search solutions over their outsourced data, but without revealing privacy to untrusted clouds. However, existing solutions for secure nearest neighbor search still face significant limitations, which make them far from practice. In this paper, we propose a new searchable encryption scheme, which can efficiently and securely enable nearest neighbor search over encrypted data on untrusted clouds. Specifically, we modify the search algorithm of nearest neighbors with tree structures (e.g., R-trees), where the modified algorithm adapts to lightweight cryptographic primitives (e.g., Order-Preserving Encryption) without affecting the original faster-than-linear search complexity. As a result, we address all the limitations in the previous works while still maintaining correctness and security. Moreover, our design is general, which can be used for secure k-nearest neighbor search, and it is compatible with other similar tree structures. Our experimental results on Amazon EC2 show that our scheme is extremely practical over massive datasets.
【Keywords】: Nearest neighbor searches; Servers; Encryption; Cloud computing; Data privacy; Indexes
【Paper Link】 【Pages】:1-9
【Authors】: Liqiong Chang ; Xiaojiang Chen ; Yu Wang ; Dingyi Fang ; Ju Wang ; Tianzhang Xing ; Zhanyong Tang
【Abstract】: Device-free localization (DfL) techniques, which can localize targets without carrying any wireless devices, have attracting an increasing attentions. Most current DfL approaches, however, have two main drawbacks hindering their practical applications. First, one needs to collect large number of measurements to achieve a high localization accuracy, inevitably causing a high deployment cost, and the areas variety will further exacerbate this problem. Second, as the pre-obtained Received Signal Strength (RSS) from each location (i.e., radio-map) in a specific area cannot be directly applied to new areas for localization, the calibration process of different areas will lead to the high human effort cost. In this paper, we propose, FitLoc, a fine-grained and low cost DfL approach that can localize multiple targets in various areas. By taking advantage of the compressive sensing (CS) theory, FitLoc decreases the deployment cost by collecting only a few of RSS measurements and performs a fine-grained localization. Further, FitLoc employs a rigorously designed transfer scheme to unify the radio-map over various areas, thus greatly reduces the human effort cost. Theoretical analysis about the effectivity of the problem formulation is provided. Extensive experimental results illustrate the effectiveness of FitLoc.
【Keywords】: Sensors; Wireless sensor networks; Wireless communication; Distortion measurement; Real-time systems; Transceivers; Calibration
【Paper Link】 【Pages】:1-9
【Authors】: Fan Yang ; Qiang Zhai ; Guoxing Chen ; Adam C. Champion ; Junda Zhu ; Dong Xuan
【Abstract】: Accurate indoor localization is a key enabling technology for numerous applications such as indoor navigation, mobile social networking, and augmented reality. Despite major effort from the research community, state-of-the-art indoor localization performance remains unsatisfactory. Current approaches using radio frequency entail tedious site surveys and have limited accuracy. While vision-based localization techniques are promising, they struggle with human recognition and changing environments. This paper proposes Flash-Loc, an accurate indoor localization system leveraging flashes of light to localize people carrying mobile phones in areas with deployed surveillance cameras. A person's mobile phone emits a sequence of flashes that uniquely “represents” the person from the cameras' view. Flash-Loc develops three key mechanisms that distinguish people while avoiding long irritating flashes: adaptive-length flash coding, pulse width modulation based flash generation, and image subtraction based flash localization. Further, we design a system in which Flash-Loc cooperates with fingerprinting and dead reckoning for accurate human localization. We implement Flash-Loc on commercial off-the-shelf equipment. Our real-world experiments show Flash-Loc achieves accurate indoor localization by itself and in cooperation with other localization technology. In particular, Flash-Loc can localize a user 45 m away from the camera with sub-meter accuracy.
【Keywords】: Mobile handsets; Cameras; Visualization; Decoding; Surveillance; Radio frequency; Servers
【Paper Link】 【Pages】:1-9
【Authors】: Hao Han ; Shanhe Yi ; Qun Li ; Guobin Shen ; Yunxin Liu ; Edmund Novak
【Abstract】: Smartphone users are often grouped to exchange files or perform collaborative tasks when meeting together. We argue that the location information of group members is critical to many mobile applications. Existing localization solutions mostly rely on anchor nodes or infrastructures to perform ranging and positioning. These approaches are inefficient for ad hoc scenarios. In this paper, we propose AMIL, an Acoustic Mobility-Induced TDoA (Time-Difference-of-Arrival)-based Localization scheme for smartphones. In AMIL, a smartphone user can use simple gestures (e.g., hold the phone and draw a triangle in the air) to quickly obtain the relative coordinates of neighboring mobile devices. We have implemented and evaluated AMIL on off-the-shelf smartphones. The field tests have shown that our scheme can achieve less than three degree orientation errors and can successfully build a simple map of 12 people in an office room with average error of 50cm.
【Keywords】: Smart phones; Microphones; Tracking; Sensors; Acoustics; Accelerometers
【Paper Link】 【Pages】:1-9
【Authors】: Rohit Verma ; Aviral Shrivastava ; Bivas Mitra ; Sujoy Saha ; Niloy Ganguly ; Subrata Nandi ; Sandip Chakraborty
【Abstract】: Public transport in suburban cities (covers 80% of the urban landscape) of developing regions suffer from the lack of information in Google Transit, unpredictable travel times, chaotic schedules, absence of information board inside the vehicle. Consequently, passengers suffer from lack of information about the exact location where the bus is at present as well as the estimated time to be taken to reach the desired destination. We find that off-the-shelf deployment of existing (non-GPS) localization schemes exhibit high error due to sparsity of stable and structured outdoor landmarks (anchor points). Through rigorous experiments conducted over a month however, we realize that there are a certain class of volatile landmarks which may be useful in developing efficient localization scheme. Consequently, in this paper, we design a novel generalized energy-efficient outdoor localization scheme - UrbanEye, which efficiently combines the volatile and non-volatile landmarks using a specialized data structure, the probabilistic timed automata. UrbanEye uses speed-breakers, turns and stops as landmarks, estimates the travel time with a mean accuracy of ±2.5 mins and produces a mean localization accuracy of 50 m. Results from several runs taken in two cities, Durgapur and Kharagpur, reveal that UrbanEye provides more than 50% better localization accuracy compared to the existing system Dejavu [1], and consumes significantly less energy.
【Keywords】: Navigation; IEEE 802.11 Standard; GSM; Urban areas; Databases; Sensors; Probabilistic logic
【Paper Link】 【Pages】:1-9
【Authors】: Muhammad Owais Khan ; Lili Qiu
【Abstract】: The signal-to-noise ratio (SNR) is the gold standard metric for capturing wireless link quality, but offers limited predictability. Recent work shows that frequency diversity causes limited predictability in SNR, and proposes effective SNR. Owing to its significant improvement over SNR, effective SNR has become a widely adopted metric for measuring wireless channel quality and served as the basis for many recent rate adaptation schemes. In this paper, we first conduct trace driven evaluation, and find that the accuracy of effective SNR is still inadequate due to frequency diversity and bursty errors. While common wisdom says that interleaving should remove the bursty errors, bursty errors still persist under the WiFi interleaver. Therefore, we develop two complementary methods for computing frame delivery rate to capture the bursty errors under the WiFi interleaver. We then design a new interleaver to reduce the burstiness of errors, and improve the frame delivery rate. We further design a rate adaptation scheme based on our delivery rate estimation. It can support both WiFi and our interleaver. Using extensive evaluation, we show our delivery rate estimation is accurate and significantly out-performs effective SNR; our interleaver improves the delivery rate over the WiFi interleaver; and our rate adaptation improves both throughput and energy.
【Keywords】: Signal to noise ratio; IEEE 802.11 Standard; Decoding; Bit error rate; Wireless communication; Estimation
【Paper Link】 【Pages】:1-9
【Authors】: Abhijit Bhattacharya ; Anurag Kumar
【Abstract】: We consider single-hop topologies with saturated transmitting nodes, using IEEE 802.11 DCF for medium access, where the propagation delays among the nodes are not negligible compared to the backoff slot duration. In this situation, we find that there is misaligned sensing of channel idleness, and also short-term unfairness in access to the medium. We demonstrate that existing analysis techniques (or, extensions thereof) are unable to account for these features, resulting in inaccurate prediction of the performance. Focusing on the case in which transmitters are equidistant from one another, and also each receiver is equidistant from all the transmitters, we provide a detailed stochastic model that accurately captures the system evolution. Since an exact analysis of this model is computationally intractable, we develop a novel approximate, but accurate, analysis that uses a parsimonious state representation for computational tractability. Numerical experiments show, the approximate analysis predicts the system throughput to a relative accuracy of 2-3%, and collision probabilities to a relative accuracy of 3-8% compared to simulations. Interestingly, we observe that as propagation delay increases, the collision probability of a node initially increases, but then flattens out, contrary to what one might intuitively expect. Finally, we also demonstrate how to optimize slot duration using the approximate analysis for maximizing system throughput.
【Keywords】: Propagation delay; IEEE 802.11 Standard; Analytical models; Transmitters; Receivers; Computational modeling; Radiation detectors
【Paper Link】 【Pages】:1-9
【Authors】: Changhua Pei ; Youjian Zhao ; Guo Chen ; Ruming Tang ; Yuan Meng ; Minghua Ma ; Ken Ling ; Dan Pei
【Abstract】: As mobile Internet is now indispensable in our daily lives, WiFi's latency performance has become critical to mobile applications' quality of experience. Unfortunately, WiFi hop latency in the wild remains largely unknown. In this paper, we first propose an effective approach to break down the round trip network latency. Then we provide the first systematic study on WiFi hop latency in the wild based on the latency and WiFi factors collected from 47 APs on T university campus for two months. We observe that WiFi hop can be the weakest link in the round trip network latency: more than 50% (10%) of TCP packets suffer from WiFi hop latency larger than 20ms (100ms), and WiFi hop latency occupies more than 60% in more than half of the round trip network latency. To help understand, troubleshoot, and optimize WiFi hop latency for WiFi APs in general, we train a decision tree model. Based on the model's output, we are able to reduce the median latency by 80% from 50ms to 10ms in one real case, and reduce the maximum latency from 250ms to 50ms in another real case.
【Keywords】: IEEE 802.11 Standard; Wireless communication; Servers; Internet; Wireless sensor networks; Mobile applications; Decision trees
【Paper Link】 【Pages】:1-9
【Authors】: Wangkit Wong ; Avishek Thakur ; S.-H. Gary Chan
【Abstract】: In wireless local area networks (WLANs), association of the access points (APs) is often not uniform due to joining and leaving of wireless users. Such imbalance leads to unsatisfactory user throughput due to congestion at some APs and channel under-utilization at others. As users may be covered by multiple APs in WLAN deployment, their throughput can be improved by AP re-association, i.e., migrating some users from the congested APs to the less loaded neighboring APs. Such reassociation is expected to come with some cost (due to overhead in handshaking, authentication and data flow management). In this paper, we study the novel problem of optimizing AP re-association by maximizing the minimum user throughput (i.e., max-min fairness), subject to a certain total user migration cost constraint. We show that the problem is NP-hard. We then propose an efficient approximation algorithm called CACA (Cost-constrained Association Control Algorithm). CACA has provable performance, achieving an approximation factor of (4+ϵ), for any ϵ > 0. It is simple and implementable. Our extensive simulation results based on NS3 show that it substantially outperforms other comparison schemes with close-to-optimal performance (the case without cost constraint). Our testbed experiments further confirm the effectiveness of CACA.
【Keywords】: Throughput; Approximation algorithms; Wireless LAN; Authentication; Optimization; Internet; IEEE 802.11 Standard
【Paper Link】 【Pages】:1-9
【Authors】: Zhiping Jiang ; Jinsong Han ; Chen Qian ; Wei Xi ; Kun Zhao ; Han Ding ; Shaojie Tang ; Jizhong Zhao ; Panlong Yang
【Abstract】: Identifying the object that attracts human visual attention is an essential function for automatic services in smart environments. However, existing solutions can compute the gaze direction without providing the distance to the target. In addition, most of them rely on special devices or infrastructure support. This paper explores the possibility of using a smartphone to detect the visual attention of a user. By applying the proposed VADS system, acquiring the location of the intended object only requires one simple action: gazing at the intended object and holding up the smartphone so that the object as well as user's face can be simultaneously captured by the front and rear cameras. We extend the current advances of computer vision to develop efficient algorithms to obtain the distance between the camera and user, the user's gaze direction, and the object's direction from camera. The object's location can then be computed by solving a trigonometric problem. VADS has been prototyped on commercial off-the-shelf (COTS) devices. Extensive evaluation results show that VADS achieves low error (about 1.5° in angle and 0.15m in distance for objects within 12m) as well as short latency. We believe that VADS enables a large variety of applications in smart environments.
【Keywords】: Face; Visualization; Cameras; Computational modeling; Solid modeling; Three-dimensional displays; Estimation
【Paper Link】 【Pages】:1-9
【Authors】: Xiaolong Zheng ; Jiliang Wang ; Longfei Shangguan ; Zimu Zhou ; Yunhao Liu
【Abstract】: Even though indoor smoking ban is being put into practice in civilized countries, existing vision or sensor-based smoking detection methods cannot provide ubiquitous smoking detection. In this paper, we take the first attempt to build a ubiquitous passive smoking detection system, which leverages the patterns smoking leaves on WiFi signals to identify the smoking activity even in the non-line-of-sight and through-wall environments. We study the behaviors of smokers and leverage the common features to recognize the series of motions during smoking, avoiding the target-dependent training set to achieve the high accuracy. We design a foreground detection based motion acquisition method to extract the meaningful information from multiple noisy subcarriers even influenced by posture changes. Without requirements of target's compliance, we leverage the rhythmical patterns of smoking to reduce the detection false positives. We prototype Smokey with the commodity WiFi infrastructure and evaluate its performance in real environments. Experimental results show Smokey is accurate and robust in various scenarios.
【Keywords】: IEEE 802.11 Standard; Wireless communication; Mouth; Gesture recognition; Monitoring; Sensors; Training
【Paper Link】 【Pages】:1-9
【Authors】: Yafeng Yin ; Qun Li ; Lei Xie ; Shanhe Yi ; Edmund Novak ; Sanglu Lu
【Abstract】: Due to the smaller size of mobile devices, on-screen keyboards become inefficient for text entry. In this paper, we present CamK, a camera-based text-entry method, which uses an arbitrary panel (e.g., a piece of paper) with a keyboard layout to input text into small devices. CamK captures the images during the typing process and uses the image processing technique to recognize the typing behavior. The principle of CamK is to extract the keys, track the user's fingertips, detect and localize the keystroke. To achieve high accuracy of keystroke localization and low false positive rate of keystroke detection, CamK introduces the initial training and online calibration. Additionally, CamK optimizes computation-intensive modules to reduce the time latency. We implement CamK on a mobile device running Android. Our experiment results show that CamK can achieve above 95% accuracy of keystroke localization, with only 4.8% false positive keystrokes. When compared to on-screen keyboards, CamK can achieve 1.25X typing speedup for regular text input and 2.5X for random character input.
【Keywords】: Keyboards; Cameras; Image edge detection; Image segmentation; Smart phones
【Paper Link】 【Pages】:1-9
【Authors】: Heba Aly ; Moustafa Youssef
【Abstract】: Human respiratory rate is widely recognized as a vital measure of a patient's health and a primary indicator of several medical problems. Yet, it is usually ignored by medical practitioners due to limitations with available measurements techniques that are either performed through visual counting by trained personnel or using invasive and/or devices limited to medical facilities. We present Zephyr, a ubiquitous low-cost smartphone-based robust respiratory rate estimator. Our analysis shows that accelerometer and gyroscope measurements from a standard smartphone held on a person's chest is affected by her respiration cycle. Zephyr employs a series of signal processing modules to extract the breathing signal from the noisy inertial sensor measurements and handle noisy user movements. Furthermore, as part of Zephyr design, we propose a novel respiratory rate signal quality estimate that we leverage through a probabilistic framework to fuse the estimates from the different sensors, leading to a robust respiratory rate estimate. Implementation of the system on different off-the-shelf Android devices using more than 150 experiments with seven participants of different ages and genders under different typical settings with a side-by-side comparison to a commercial device shows that Zephyr can estimate the user's respiratory rate accurately with a median absolute error of 0.04 breaths per minute in realtime. In addition, Zephyr's quality-based probabilistic framework improves the respiratory rate estimation by more than 51% as compared to using any of the individual sensor measurements. This remarkable accuracy is achieved within 30 seconds of measurements, highlighting the viability of Zephyr as a ubiquitous low-cost respiratory rate estimator.
【Keywords】: Estimation; Robustness; Smart phones; Noise measurement; Monitoring; Accelerometers; Biomedical monitoring
【Paper Link】 【Pages】:1-9
【Authors】: Phuc Nguyen ; Xinyu Zhang ; Ann C. Halbower ; Tam Vu
【Abstract】: In this work, we propose for the first time an autonomous system, called WiSpiro, that continuously monitors a person's breathing volume with high resolution during sleep from afar. WiSpiro relies on a phase-motion demodulation algorithm that reconstructs minute chest and abdominal movements by analyzing the subtle phase changes that the movements cause to the continuous wave signal sent by a 2.4 GHz directional radio. These movements are mapped to breathing volume, where the mapping relationship is obtained via a short training process. To cope with body movement, the system tracks the large-scale movements and posture changes of the person, and moves its transmitting antenna accordingly to a proper location in order to maintain its beam to specific areas on the frontal part of the person's body. It also incorporates interpolation mechanisms to account for possible inaccuracy of our posture detection technique and the minor movement of the person's body. We have built WiSpiro prototype, and demonstrated through a user study that it can accurately and continuously monitor user's breathing volume with a median accuracy from 90% to 95.4% (or 0.0581 to 0.111 of error) to even in the presence of body movement. The monitoring granularity and accuracy are sufficiently high to be useful for diagnosis by clinical doctor.
【Keywords】: Monitoring; Radar; Diseases; Biomedical monitoring; Training; Radar antennas
【Paper Link】 【Pages】:1-9
【Authors】: Zhao Li ; Xiaoqin Dai ; Kang G. Shin
【Abstract】: Due to the hierarchical structure and heterogeneity of most deployed wireless networks, multiple data transmissions using the same communication resource, such as frequency band and time slot, are likely to occur in the same area. Hence, interference becomes critical to the decoding of interfered signals. There have already been numerous techniques dealing with interferences that can be implemented either at the transmitter, the receiver or both, to support simultaneous multi-user transmissions. This paper focuses on the reception design in multiple access channels (MACs) where multiple transmitters send data to a common receiver simultaneously. By exploiting the constructive/destructive interactions among interfering signals, we propose a receiver structure based on interference combination (ICom) incorporating zero-forcing (ZF) and successive interference cancellation (SIC). The proposed receiver structure does not require coordination at the transmitter side and can significantly reduce the number of receiving antennas at a moderate processing cost. The ICom-based reception is shown to be able to not only achieve a significant improvement of system spectral efficiency (SE) under stringent latency constraints, but also make a flexible tradeoff between the requirement of receiving antennas and signal processing complexity, thus facilitating its implementation and deployment.
【Keywords】: Interference; Receiving antennas; Signal processing; Decoding; Transmitting antennas
【Paper Link】 【Pages】:1-9
【Authors】: Wei Gong ; Haoxiang Liu ; Kebin Liu ; Qiang Ma ; Yunhao Liu
【Abstract】: Backscatter communication networks receive much attention recently due to the small size and low power of backscatter nodes. As backscatter communication is often influenced by the dynamic wireless channel quality, rate adaptation becomes necessary. Most existing approaches share a common drawback: they do not distinguish channel qualities from different nodes or sub-channels. Consequently, the transmission rate may be improperly selected, resulting in low network throughput. Through extensive experimental studies, we observe that channel diversity plays a significant role in rate selection. Therefore, there are opportunities of exploiting channel diversity for better rate adaptation, improving network throughput. In this paper, we propose a Channel-Aware Rate Adaptation framework (CARA) for backscatter communication networks. By employing a lightweight channel probing scheme, we are able to obtain fine-grained channel information that enables accurate channel estimation. We further design a novel channel selection algorithm, benefiting as many backscatter nodes as possible. On each selected channel, CARA chooses data rate with respect to the node that has the best channel condition. We implement CARA on commercial readers and the experiment results show that CARA achieves up to 4× goodput gain compared with state-of-the-art rate adaptation scheme.
【Keywords】: Backscatter; Communication networks; Frequency diversity; Channel estimation; Packet loss; Probes
【Paper Link】 【Pages】:1-9
【Authors】: Raul Gomez Cid-Fuentes ; M. Yousof Naderi ; Stefano Basagni ; Kaushik R. Chowdhury ; Albert Cabellos-Aparicio ; Eduard Alarcón
【Abstract】: Wireless RF power transmission from dedicated Energy Transmitters (ETs) is emerging as a promising approach to enable battery-less wireless networked sensor systems. However, when data communication and RF energy recharging occur in-band, sharing the RF medium and devoting separate access times for both operations raises architectural and protocol level challenges. This paper proposes a novel method of concurrent transmission of data and energy to solve this problem, allowing ETs to transmit energy and sensors to transmit data in the same band synchronously. Our key idea concerns devising a physical layer modulation scheme that allows the data transmitting node to introduce variations in the envelope of the energy signal at the intended recipient. We implemented a proof-of-concept receiver, modeled and validated through extensive experimentation. We then propose a new physical layer mechanism for guaranteed successful delivery of information in a point-to-point link. Quantitative results demonstrate the feasibility of joint energy-data transfer, along with its associated benefits and tradeoffs.
【Keywords】: Radio frequency; Wireless sensor networks; Wireless communication; Transmitters; Data communication; Receiving antennas
【Paper Link】 【Pages】:1-9
【Authors】: Alexander J. T. Gurney ; Sanjeev Khanna ; Yang Li
【Abstract】:
In interdomain routing, competing network operators encode policies about possible routes in routing protocol configuration. The operation of the protocol should lead to satisfactory routes for all operators, but this process may not terminate or take a long time, exploring exponentially many alternative paths before stabilizing. In this paper, we study convergence for the partial policy specification model where preferences are set for only some paths and the ranking for the remaining paths is indifferent to the network operator. We consider policy restrictions that ensure a network to stabilize quickly. Specifically, we show that even when each operator only specifies preferences for two paths and each path has at most three hops, a network may still encounter exponentially many steps before convergence. However, restricting the policy any further ensures poly-time convergence. From another direction, it is well known that preferences based only on the next-hop' node always converge within linear-time. We show that even relaxing the preference to be based on thenext-two-hop' leads to exponential-time convergence. Finally, we further study policy completion that leads to a stable state that minimizes the hop-length of the longest path, and establish a hardness result along with an approximation algorithm.
【Keywords】: Convergence; Routing protocols; Routing; Approximation algorithms; Standards; Switches
【Paper Link】 【Pages】:1-9
【Authors】: Leonardo Maccari ; Renato Lo Cigno
【Abstract】: Fast and efficient recovery from node failure, with minimal disruption of routes and the consequent traffic loss is of the utmost importance for any routing protocol. Link-state protocols, albeit preferred to distance vector ones because of faster convergence, still suffer from a trade-off between control message overhead and performance. This work formalizes the routes' disruption following a node failure as an optimization problem depending on the nodes' centrality in the topology, constrained to a constant signaling overhead. Next, it shows that the solution can be found using Lagrange Multipliers. The solution complexity is low enough to be computed on-line on the network routers, thus obtaining the optimal setting of control message timers that minimize the traffic loss following a node failure. The gain obtained is quantified in power-law synthetic topologies, and it is also tested on real network topologies extending the OLSR protocol to use the modified timers, showing that the inevitable approximations introduced in the analysis do not hamper the very good results achievable through this novel approach. The technique can be applied to any link state protocol, including OSPF, and improves route convergence not only upon failures but on every topology modification.
【Keywords】: Network topology; Topology; Routing protocols; Routing; Convergence; Optimization
【Paper Link】 【Pages】:1-9
【Authors】: Yingjie Bi ; Chee Wei Tan ; Ao Tang
【Abstract】: In this paper, we study network utility maximization over both routing choice and path rate assignment for any given path cardinality constraint. We provide a novel convex relaxation, which leads to a randomized algorithm with performance guarantees. The new relaxation also enables distributed algorithm design and allows us to obtain performance estimation for nonconvex routing optimization problems that is significantly better than previous work based on the multipath routing relaxation. Convergence and performance of the proposed randomized algorithm are characterized theoretically and further illustrated numerically through examples to demonstrate its superiority over existing work.
【Keywords】: Routing; Throughput; Resource management; Optimized production technology; Distributed algorithms; Heuristic algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Marc-Olivier Buob ; Anthony Lambert ; Steve Uhlig
【Abstract】: The Internet is made of almost 50, 000 ASes exchanging routing information thanks to BGP. Inside each AS, information is redistributed via iBGP sessions. This allows each router to map a destination exterior to the AS with a given egress point. The main redistribution mechanisms used today, (iBGP full mesh, Route Reflectors and BGP confederations), either guarantee selection of the best egress point or enhance scalability, but not both. In this paper, we propose a new way to perform iBGP redistribution in an AS based on its IGP topology, conciliating optimality in route selection and scalability. Our contribution is threefold. First, we demonstrate the tractability of our approach and its benefits. Second, we provide an open-source implementation of our mechanism based on Quagga. Third, we illustrate the feasibility of our approach through simulations performed under ns-3 and compare its performance with full mesh and Route Reflection.
【Keywords】: Routing; Network topology; Routing protocols; Scalability; Topology; Internet
【Paper Link】 【Pages】:1-9
【Authors】: Francois Aubry ; David Lebrun ; Stefano Vissicchio ; Minh Thanh Khong ; Yves Deville ; Olivier Bonaventure
【Abstract】: To guarantee correct operation of their networks, operators have to promptly detect and diagnose data-plane issues, like broken interface cards or link failures. Networks are becoming more complex, with a growing number of Equal Cost MultiPath (ECMP) and link bundles. Hence, some data-plane problems (e.g. silent packet dropping at one router) can hardly be detected with control-plane protocols or simple monitoring tools like ping or traceroute. In this paper, we propose a new technique, called SCMon, that enables continuous monitoring of the data-plane, in order to track the health of all routers and links. SCMon leverages the recently proposed Segment Routing (SR) architecture to monitor the entire network with a single box (and no additional monitoring protocol). In particular, SCMon uses SR to (i) force monitoring probes to travel over cycles; and (ii) test parallel links and bundles at a per-link granularity. We present original algorithms to compute cycles that cover all network links with a limited number of SR segments. Further, we prototype and evaluate SCMon both with simulations and Linux-based emulations. Our experiments show that SCMon quickly detects and precisely pinpoints data-plane problems, with a limited overhead.
【Keywords】: Monitoring; Routing; Probes; Routing protocols; Topology; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Mike Jia ; Weifa Liang ; Zichuan Xu ; Meitian Huang
【Abstract】: With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for businesses, entertainments and social interactions. Although such portable mobile devices can offer various promising applications, their computing resources remain limited due to their portable size. This however can be overcome by remotely executing computation-intensive tasks on clusters of near by computers known as cloudlets. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-a-box must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload between multiple cloudlets in a network to optimize mobile application performance. We first introduce a system model to capture the response times of offloaded tasks, and formulate a novel optimization problem, that is to find an optimal redirection of tasks between cloudlets such that the maximum of the average response times of tasks at cloudlets is minimized. We then propose a fast, scalable algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. The experimental results demonstrate the significant potential of the proposed algorithm in reducing the response times of tasks.
【Keywords】: Cloud computing; Time factors; Mobile handsets; Delays; Mobile communication; Computers; Load management
【Paper Link】 【Pages】:1-9
【Authors】: Toru Mano ; Takeru Inoue ; Kimihiro Mizutani ; Osamu Akashi
【Abstract】: Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E| = O(|V|2)) based on a traffic matrix, the time complexity is actually O(|E|3 = |V|6). If we were allowed to reduce this dense network into a sparse one before embedding, the time complexity could be decreased to O(|V|3); the time gap can be a million times for |V| = 100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction algorithms and analyze them with several interesting theorems. The analysis indicates that the embedding cost increases only linearly with exponential decay of embedding time. Thorough numerical evaluation justifies the desirability of the trade-off.
【Keywords】: Time complexity; Indium phosphide; III-V semiconductor materials; Measurement; Manganese; Virtualization; Engines
【Paper Link】 【Pages】:1-9
【Authors】: Dapeng Liu ; Youjian Zhao ; Kaixin Sui ; Lei Zou ; Dan Pei ; Qingqian Tao ; Xiyang Chen ; Dai Tan
【Abstract】: Response time plays a key role in Web services, as it significantly impacts user engagement, and consequently the Web providers' revenue. Using a large search engine as a case study, we propose a machine learning based analysis framework, called FOCUS, as the first step to automatically debug high search response time (HSRT) in search logs. The output of FOCUS offers a promising starting point for operators' further investigation. FOCUS has been deployed in one of the largest search engines for 2.5 months and analyzed about one billion search logs. Compared with a previous approach, FOCUS generates 90% less items for investigation and achieves both higher recall and higher precision. The results of FOCUS enable us to make several interesting observations. For example, we find that popular queries are more image-intensive (e.g., TV series and shopping), but they have relatively low SRT because they are cached well by servers. Additionally, as suggested by the first-month analysis results of FOCUS, we conduct an optimization on image transmission time. A one-month real-world deployment shows that we successfully reduce the 80th percentile of search response time by 253ms, and reduce the fraction of HSRT by one third.
【Keywords】: Browsers; Time factors; Search engines; Servers; Loading; Web services; Engines
【Paper Link】 【Pages】:1-9
【Authors】: Yuhuan Du ; Gustavo de Veciana
【Abstract】: Cloud-based computing infrastructure provides an efficient means to support real-time processing workloads, e.g., virtualized base station processing, and collaborative video conferencing. This paper addresses resource allocation for a computing system with multiple resources supporting heterogeneous soft real-time applications subject to Quality of Service (QoS) constraints on failures to meet processing deadlines. We develop a general outer bound on the feasible QoS region for non-clairvoyant resource allocation policies, and an inner bound for a natural class of policies based on dynamically prioritizing applications' tasks by favoring those with the largest (QoS) deficits. This provides an avenue to study the efficiency of two natural resource allocation policies: (1) priority-based greedy task scheduling for applications with variable workloads, and (2) priority-based task selection and optimal scheduling for applications with deterministic workloads. The near-optimality of these simple policies emerges when task processing deadlines are relatively large and/or when the number of compute resources is large. Analysis and simulations show substantial resource savings for such policies over reservation-based designs.
【Keywords】: Quality of service; Resource management; Real-time systems; Computational modeling; Optimal scheduling; Cloud computing; Processor scheduling
【Paper Link】 【Pages】:1-9
【Authors】: Jingjie Jiang ; Shiyao Ma ; Bo Li ; Baochun Li
【Abstract】: Even with the recent proliferation of in-memory computation in data-parallel frameworks (such as Spark), transfers over the network are still time-consuming. Similar to computation, network transfers serve as main roadblocks as we try to minimize job completion times. Existing schedulers were designed as isolated solutions that focused on computation or network performance only. Without any coordination, the utilization of computation and network resources may become unbalanced, leading to a reduced level of overall resource utilization. In this paper, we design, implement, and evaluate Symbiosis, a network-aware task scheduler designed to coordinate computation-bound and network-bound tasks in a large cluster, so that resources are utilized in a more balanced fashion. Symbiosis is an online scheduler that predicts resource imbalance before launching tasks, and correct such imbalance by co-locating computation-bound and network-bound tasks in the same executor process. As a guiding principle, it is engineered to be practically implemented within and to complement existing data-parallel frameworks. We have implemented Symbiosis within Spark, and carried out our experiments on a 100-node cluster. We show convincing evidence that Symbiosis reduces job completion times by 11.9% in comparison to Spark's current scheduler with little overhead.
【Keywords】: Symbiosis; Sparks; Processor scheduling; Runtime; Resource management; Data transfer; Production
【Paper Link】 【Pages】:1-9
【Authors】: Qiaomin Xie ; Ali Yekkehkhany ; Yi Lu
【Abstract】: A fundamental problem to all data-parallel applications is data locality. An example is map task scheduling in the MapReduce framework. Existing theoretical work analyzes systems with only two levels of locality, despite the existence of multiple locality levels within and across data centers. We found that going from two to three levels of locality changes the problem drastically, as a tradeoff between performance and throughput emerges. The recently proposed priority algorithm, which is throughput and heavy-traffic optimal for two locality levels, is not even throughput-optimal with three locality levels. The JSQ-MaxWeight algorithm proposed by Wang et al. is heavy-traffic optimal only for a special traffic scenario with two locality levels. We show that an extension of the JSQ-MaxWeight algorithm to three locality levels preserves its throughput-optimality, but suffers from the same lack of heavy-traffic optimality for most traffic scenarios. We propose a novel algorithm that uses Weighted-Workload (WW) routing and priority service. We establish its throughput and heavy-traffic optimality for all traffic scenarios. The main challenge is the construction of an appropriate ideal load decomposition that allows the separate treatment of different subsystems.
【Keywords】: Servers; Throughput; Delays; Job shop scheduling; Optimal scheduling; Algorithm design and analysis; Routing
【Paper Link】 【Pages】:1-9
【Authors】: Sungjin Im ; Mina Naghshnejad ; Mukesh Singhal
【Abstract】: We consider the problem of scheduling jobs with varying demands on multiple servers. Each server has a certain computing capacity and can schedule multiple jobs simultaneously as long as the jobs' total demand does not exceed the server's capacity. This scenario arises commonly in virtualization, cloud computing, and MapReduce (or Hadoop). We study this problem with the requirement that jobs must be scheduled non-preemptively, meaning that every job must be completed without interruption once it gets started. Often, preemption is out of choice since preempting a job can be prohibitively costly or is not allowed due to system constraints. We focus on the popular objective of minimizing total completion time of jobs. This problem is NP hard hence we study heuristics with provable approximation guarantees. Succinctly, the interaction between two orthogonal quantities, jobs demands and sizes makes the scheduling decision significantly more challenging. In this paper we propose novel algorithms for scheduling jobs with non-uniform demands on multiple homogeneous servers without preemption. We first observe that the Smallest Volume First (SVF) algorithm that favors jobs with smaller volumes could perform very poorly in general. However, we show that SVF yields a nearly optimal schedule when the system is overloaded and jobs have demands considerably smaller than servers' capacities. This result supports the intuition that SVF should work well unless some jobs with high demands occupy the servers for long, blocking other jobs. Building on this intuition and using reduction to geometric packing problems, we develop algorithms that are constant approximation for all instances for the first time. Prior to our work, there was no theoretical study on this problem even for the single server case.
【Keywords】: Schedules; Optimal scheduling; Servers; Approximation algorithms; Interrupters; Algorithm design and analysis; Virtualization
【Paper Link】 【Pages】:1-9
【Authors】: Tal Mizrahi ; Yoram Moses
【Abstract】: With the rise of Software Defined Networks (SDN), there is growing interest in dynamic and centralized traffic engineering, where decisions about forwarding paths are taken dynamically from a network-wide perspective. Frequent path reconfiguration can significantly improve the network performance, but should be handled with care, so as to minimize disruptions that may occur during network updates. In this paper we introduce Time4, an approach that uses accurate time to coordinate network updates. We characterize a set of update scenarios called flow swaps, for which Time4 is the optimal update approach, yielding less packet loss than existing update approaches. We define the lossless flow allocation problem, and formally show that in environments with frequent path allocation, scenarios that require simultaneous changes at multiple network devices are inevitable. We present the design, implementation, and evaluation of a time4-enabled OpenFlow prototype. The prototype is publicly available as open source. Our work includes an extension to the OpenFlow protocol that has been adopted by the Open Networking Foundation (ONF), and is now included in OpenFlow 1.5. Our experimental results demonstrate the significant advantages of Time4 compared to other network update approaches.
【Keywords】: Packet loss; Synchronization; Clocks; Bandwidth; Topology; Resource management
【Paper Link】 【Pages】:1-9
【Authors】: Stefano Vissicchio ; Luca Cittadini
【Abstract】: We propose FLIP, a new algorithm for SDN network updates that preserve forwarding policies. FLIP builds upon the dualism between replacements and additions of switch flow-table rules. It identifies constraints on rule replacements and additions that independently prevent policy violations from occurring during the update. Moreover, it keeps track of alternative constraints, avoiding the same policy violation. Then, it progressively explores the solution space by swapping constraints with their alternatives, until it reaches a satisfiable set of constraints. Extensive simulations show that FLIP outperforms previous proposals. It achieves a much higher success rate than algorithms based on rule replacements only, and massively reduces the memory overhead with respect to techniques solely relying on rule additions.
【Keywords】: Switches; Tagging; Space exploration; Security; Proposals; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Wen Wang ; Wenbo He ; Jinshu Su ; Yixin Chen
【Abstract】: With the popular applications of SDN in load balancing and failure recovery, the controller schedules affected flows to redundant paths to avoid network congestions and failures by updating flow tables in data plane. However, inconsistent flow table updating may lead to transient incorrect network behaviors or undesired performance degradation. Therefore, the consistency imposes dependencies among updates, so that the order of updates must be carefully considered to keep the consistency. To update flow tables consistently and efficiently, in this paper, we propose an update ordering approach - Cupid. To avoid high overhead in update ordering, we divide the global dependencies among updates into local restrictions by: 1) partitioning a new routing path into several independent segments, 2) identifying critical nodes controlling traffic shifting between the old path and new path, and 3) constructing a dependency graph among critical nodes for potential congested links. We then design a heuristic algorithm to resolve the dependency graph. To save the flow table space, a switch keeps only one flow entry with multiple ports for a flow during updating. Our simulation shows that Cupid schedules updates at least 2 times faster and has less throughput losses than the state-of-the-art approaches in both fat-tree and mesh networks.
【Keywords】: Routing; Switches; Bandwidth; Schedules; Degradation; Throughput; Algorithm design and analysis
【Paper Link】 【Pages】:1-9
【Authors】: Salaheddine Hamadi ; Khalil Blaiech ; Petko Valtchev ; Omar Cherkaoui ; Radu State
【Abstract】: Openflow is a key step in abstracting network functions by separating the control and the forwarding plane. However, even with continuous innovation and evolution of the protocol, its adoption on forwarding device targets remains laborious and time consuming. In this paper, we present a semantic-based approach to packet forwarding design that tailors flow classification to the underlying switch device. Its key idea consist in streamlining flow classification through rule compiling and thus to optimize forwarding operations and improve switch resources usage. The compiling itself exploits a rule grouping gleaned through Frequent Pattern Mining and Network Calculus in optimizing flow classification w.r.t. the switch pipelined architecture.
【Keywords】: Switches; Computer architecture; Semantics; Protocols; Heuristic algorithms; Algorithm design and analysis
【Paper Link】 【Pages】:1-9
【Authors】: Jonghoe Koo ; KiTaek Lee ; Wonbo Lee ; Yongseok Park ; Sunghyun Choi
【Abstract】: Energy awareness of mobile devices with limited battery capacity can be achieved by embedding battery drain rate monitoring capability into the devices. With Li-ion battery, battery drain rate varies with temperature and battery aging, since they affect battery characteristics such as capacity and internal resistance. We develop BattTracker, an algorithm to estimate battery drain rate without knowing the exact capacity and internal resistance by incorporating the concept of effective resistance. BattTracker tracks the instantaneous battery drain rate with up to 0.5 second time granularity. Extensive evaluation with smartphones demonstrates that BattTracker accurately estimates the battery drain rate with less than 5% estimation error, thus enabling energy-aware operation of smartphones with finegrained time granularity. To the best of our knowledge, this is the first effort to estimate the instantaneous battery drain rate by considering both temperature and aging effects on the battery characteristics.
【Keywords】: Batteries; Aging; Resistance; Temperature; Temperature measurement; Training; Battery charge measurement
【Paper Link】 【Pages】:1-9
【Authors】: Lu Liu ; Xianghui Cao ; Wenlong Shen ; Yu Cheng ; Lin X. Cai
【Abstract】: As wireless networks are gaining increasing popularity, the network energy efficiency has become a critical issue. In this paper, we focus on energy-efficient networking in a generic multi-radio multi-channel (MR-MC) wireless network where transmission scheduling, transmit power control, radio and channel assignment are coupled together in a multi-dimensional resource space, thus requiring joint optimization and low complexity algorithms. We propose a novel Decomposed Approach For energy-efficient (DAFEE) networking in MR-MC networks, with the objective to minimize network energy consumption while guaranteeing a certain level of performance. In particular, we leverage a multi-dimensional tuple-link based model and a concept of resource allocation pattern to transform the complex optimization problem into a linear programming (LP) problem. The LP problem however has a very large solution space due to the exponentially many possible resource allocation patterns. We then exploit delay column generation and distributed learning techniques to decompose the problem and solve it with an iterative process. Furthermore, we propose a sub-optimal algorithm to speed up the iteration with constant-bounded performance. Simulation results are presented to demonstrate the effectiveness of the proposed algorithm.
【Keywords】: Resource management; Interference; Optimization; Power control; Energy consumption; Scheduling; Aerospace electronics
【Paper Link】 【Pages】:1-9
【Authors】: Wei Wang ; Yingjie Chen ; Lu Wang ; Qian Zhang
【Abstract】: The high sampling rate in Wi-Fi is set to support bandwidth-hungry applications. It becomes energy inefficient in the post-PC era in which the emerging low-end smart devices increase the disparity in workloads. Recent advances scale down the receiver's sampling rates by leveraging the redundancy in the physical layer (PHY), which, however, requires packet modifications or very high signal-to-noise ratio (SNR). To overcome these limitations, we propose Sampleless Wi-Fi, a standard compatible solution that allows energy-constrained devices to scale down their sampling rates regardless of channel conditions. Inspired by rateless codes, Sampleless Wi-Fi recovers under-sampled packets by accumulating redundancy in packet retransmissions. To harvest the diversity gain as rateless codes without modifying legacy packets, Sampleless Wi-Fi creates new constellation diversity by exploiting the time shift effect at receivers. Our evaluation using GNURadio/USRP platform and real Wi-Fi traces have demonstrated that Sampleless Wi-Fi significantly outperforms the state-of-the-art downclocking technique in both decoding performance and energy efficiency.
【Keywords】: IEEE 802.11 Standard; Receivers; Decoding; Redundancy; OFDM; Signal to noise ratio
【Paper Link】 【Pages】:1-9
【Authors】: Dung Pham Van ; Bhaskar Prasad Rimal ; Martin Maier
【Abstract】: This paper aims at designing an ecoconscious future-proof sensor enhanced fiber-wireless (SFiWi) network based on EPON, WLAN, wireless sensor (WS), and fiber optic sensor (FOS) technologies as a shared communications infrastructure for broadband access and smart grids. A total cost of ownership (TCO) model is developed to help utilities decide whether to deploy WSs or FOSs in different scenarios and estimate sensor-related costs. To prolong battery life of wireless devices and maximize the overall energy efficiency, a novel energy conservation scheme for SFiWi networks (ECO-SFiWi) is proposed. ECO-SFiWi designs the whole network in three TDMA layers to enhance network performance, while scheduling network components to sleep outside their transmission slots. A comprehensive energy saving model accounting for both optical backhaul and wireless front-end components and a delay analysis based on M/G/1 queuing are presented. Results reveal that with their extremely long lifetime and ability to sustain in harsh environments, FOSs are superior to WSs when advanced interrogation techniques are deployed to reduce their total cost. ECO-SFiWi achieves more than 89% of energy savings, while maintaining low delay for both broadband and smart grid traffic in typical scenarios. FPGA hardware emulation and analytical results match well verifying the effectiveness of ECO-SFiWi.
【Keywords】: Wireless sensor networks; Intelligent sensors; Smart grids; Optical sensors; Wireless communication; Passive optical networks
【Paper Link】 【Pages】:1-9
【Authors】: Hyunwoo Nam ; Kyung-Hwa Kim ; Henning Schulzrinne
【Abstract】: With the proliferation of online video, measuring quality of experience (QoE) has become a pivotal aspect for the analysis of today's over-the-top (OTT) video streaming. To monitor video QoE, we introduce YouSlow that can detect various playback events (e.g., start-up latency, rebufferings and bitrate changes) from video players while a video is being played. Using YouSlow, we have collected more than 400,000 YouTube views from more than 100 countries. We measured the impact of these playback events on video abandonment and found that rebufferings incur abandonment rates six times higher than start-up latency, mostly caused by pre-roll ads. A single rebuffering event has three times the impact of a bitrate change. Even increasing the bitrate can raise abandonment rates by a factor of four compared to keeping the bitrate constant.
【Keywords】: Videos; Bit rate; YouTube; Monitoring; Quality of service; Streaming media
【Paper Link】 【Pages】:1-9
【Authors】: Konstantinos Poularakis ; George Iosifidis ; Antonios Argyriou ; Iordanis Koutsopoulos ; Leandros Tassiulas
【Abstract】: Distributed caching architectures have been proposed for bringing content close to requesters and the key problem is to design caching algorithms for reducing content delivery delay. The problem obtains an interesting new twist with the advent of advanced layered-video encoding techniques such as Scalable Video Coding (SVC). We show that the problem of finding the caching configuration of video encoding layers that minimizes average delay for a network operator is NP-Hard, and we establish a pseudopolynomial-time optimal solution using a connection with the multiple-choice knapsack problem. We also design caching algorithms for multiple operators that cooperate by pooling together their co-located caches, in an effort to aid each other, so as to avoid large delays due to downloading content from distant servers. We derive an approximate solution to this cooperative caching problem using a technique that partitions the cache capacity into amounts dedicated to own and others' caching needs. Numerical results based on real traces of SVC-encoded videos demonstrate up to 25% reduction in delay over existing (layer-agnostic) caching schemes, with increasing gains as the video popularity distribution gets steeper, and cache capacity increases.
【Keywords】: Streaming media; Delays; Servers; Static VAr compensators; Approximation algorithms; Encoding; Video recording
【Paper Link】 【Pages】:1-9
【Authors】: Kevin Spiteri ; Rahul Urgaonkar ; Ramesh K. Sitaraman
【Abstract】: Modern video players employ complex algorithms to adapt the bitrate of the video that is shown to the user. Bitrate adaptation requires a tradeoff between reducing the probability that the video freezes and enhancing the quality of the video shown to the user. A bitrate that is too high leads to frequent video freezes (i.e., rebuffering), while a bitrate that is too low leads to poor video quality. Video providers segment the video into short chunks and encode each chunk at multiple bitrates. The video player adaptively chooses the bitrate of each chunk that is downloaded, possibly choosing different bitrates for successive chunks. While bitrate adaptation holds the key to a good quality of experience for the user, current video players use ad-hoc algorithms that are poorly understood. We formulate bitrate adaptation as a utility maximization problem and devise an online control algorithm called BOLA that uses Lyapunov optimization techniques to minimize rebuffering and maximize video quality. We prove that BOLA achieves a time-average utility that is within an additive term O(1/V) of the optimal value, for a control parameter V related to the video buffer size. Further, unlike prior work, our algorithm does not require any prediction of available network bandwidth. We empirically validate our algorithm in a simulated network environment using an extensive collection of network traces. We show that our algorithm achieves near-optimal utility and in many cases significantly higher utility than current state-of-the-art algorithms. Our work has immediate impact on real-world video players and BOLA is part of the reference player implementation for the evolving DASH standard for video transmission.
【Keywords】: Videos; Bit rate; Bandwidth; Internet; Servers; Quality assessment
【Paper Link】 【Pages】:1-9
【Authors】: Yixin Chen ; Wenbo He ; Yu Hua ; Wen Wang
【Abstract】: At the present time, billions of videos are hosted and shared in the cloud of which a sizable portion consists of near-duplicate video copies. An efficient and accurate content-based online near-duplicate video detection method is a fundamental research goal; as it would benefit applications such as duplication-aware storage, pirate video detection, polluted video tag detection, searching result diversification. Despite the recent progress made in near-duplicate video detection, it remains challenging to develop a practical detection system for large-scale applications that has good efficiency and accuracy performance. In this paper, we shift the focus from feature representation design to system design, and develop a novel system, called CompoundEyes, accordingly. The improvement in accuracy is achieved via well-organized classifiers instead of advanced feature design. Meanwhile, by applying simple features with reduced dimensionality and exploiting the parallelism of the detection architecture, we accelerate the detection speed. Through extensive experiments we demonstrate that the proposed detection system is accurate and fast. It takes approximately 1.45 seconds to process a video clip from a large video dataset, CC_WEB_VIDEO, with a 89% detection accuracy.
【Keywords】: Feature extraction; Visualization; Color; Metadata; Internet; System analysis and design; Parallel processing
【Paper Link】 【Pages】:1-9
【Authors】: Zizhan Zheng ; Ness B. Shroff
【Abstract】: In many applications including interactive services and big data analytics, a timely result with a good match is often more valuable than a perfect yet delayed result. This fact can be utilized to improve the total utility gain of a cloud computing platform by allowing partial execution of jobs. A fundamental challenge, however, is that in many real environments, scheduling decisions have to be made online without knowledge about future jobs, which makes it difficult to choose between more valuable jobs with large deadlines and less valuable jobs that are more emergent. Moreover, jobs are often heterogeneous in their utilities, deadlines, and demands for different types of resources. In this paper, we study the problem of online scheduling for deadline-sensitive jobs with concave utility functions that can deliver partial results. We develop efficient online multi-resource allocation algorithms that achieve low competitive ratios for both continuous and discrete job models.
【Keywords】: Resource management; Algorithm design and analysis; Cloud computing; Parallel processing; Computational modeling; Numerical models; Delays
【Paper Link】 【Pages】:1-9
【Authors】: Yuhuan Du ; Gustavo de Veciana
【Abstract】: An increasing number of real-time applications with compute and/or communication deadlines are being supported on shared infrastructure. Such applications can often tolerate occasional deadline violations without substantially impacting their Quality of Service (QoS). A fundamental problem in such systems is deciding how to allocate shared resources so as to meet applications' QoS requirements. A simple framework to address this problem is to, (1) dynamically prioritize users as a possibly complex function of their deficits (difference of achieved vs required QoS), and (2) allocate resources so to expedite users with higher priority. This paper focuses on a general class of systems using such priority-based resource allocation. We first characterize the set of feasible QoS requirements and show the optimality of max weight-like prioritization. We then consider simple weighted Largest Deficit First (w-LDF) prioritization policies, where users with higher weighted QoS deficits are given higher priority. The paper gives an inner bound for the feasible set under w-LDF policies, and, under an additional monotonicity assumption, characterizes its geometry leading to a sufficient condition for optimality. Additional insights on the efficiency ratio of w-LDF policies, the optimality of hierarchical-LDF and characterization of clustering of failures are also discussed.
【Keywords】: Quality of service; Resource management; Real-time systems; Wireless communication; Computers; Geometry; History
【Paper Link】 【Pages】:1-9
【Authors】: I-Hong Hou
【Abstract】: This paper studies wireless networks consisting of multiple real-time flows that impose hard delay bounds for all packets. In contrast to most current studies that focus on the long-term average rate of timely deliveries, we aim to model and optimize the short-term performance of each real-time flow, which is vital for most safety-critical applications. We propose to define the instantaneous performance of a flow by a moving average within a short window in the past. Each flow incurs some penalty if its moving average is below some specified requirement, and we aim to minimize the overall penalty of the system. We approximate the system by Brownian motions, and formulate an optimization problem for minimizing the overall penalty. While the optimization problem is not convex, we establish a low-complexity algorithm for optimally solving it by leveraging inherent structures of real-time wireless networks. We also propose a simple online packet scheduling policy and prove that it achieves the minimum overall penalty. Simulation results show that Brownian approximations are accurate in capturing short-term performance, and our policies achieve much better performance than other policies. Moreover, they also demonstrate that policies with optimal long-term average delivery rates can actually have poor short-term performance.
【Keywords】: Real-time systems; Wireless networks; Optimization; Delays; Approximation algorithms; Random variables
【Paper Link】 【Pages】:1-9
【Authors】: Raphael Eidenbenz ; Thomas Locher
【Abstract】: There is a growing demand for live, on-the-fly processing of increasingly large amounts of data. In order to ensure the timely and reliable processing of streaming data, a variety of distributed stream processing architectures and platforms have been developed, which handle the fundamental tasks of (dynamically) assigning processing tasks to the currently available physical resources and routing streaming data between these resources. However, while there are plenty of platforms offering such functionality, the theory behind it is not well understood. In particular, it is unclear how to best allocate the processing tasks to the given resources. In this paper, we establish a theoretical foundation by formally defining a task allocation problem for distributed stream processing, which we prove to be NP-hard. Furthermore, we propose an approximation algorithm for the class of series-parallel decomposable graphs, which captures a broad range of common stream processing applications. The algorithm achieves a constant-factor approximation under the assumptions that the number of resources scales at least logarithmically with the number of computational tasks and the computational cost of the tasks dominates the cost of communication.
【Keywords】: Resource management; Approximation algorithms; Complexity theory; Topology; Distributed databases; Routing; Computational efficiency
【Paper Link】 【Pages】:1-9
【Authors】: Xi Chen ; Linghe Kong ; Xue Liu ; Lei Rao ; Fan Bai ; Qiao Xiang
【Abstract】: The connected vehicles have been considered as a remedy for modern traffic issues, potentially saving hundreds of thousands of lives every year worldwide. The Dedicated Short-Range Communications (DSRC) technology is an essential building block of this promising vision. DSRC faces volatile vehicular environments, where not only wireless propagation channels but also network topologies vary rapidly. Moreover, traffic congestions during rush hours may lead to an unprecedentedly high density of broadcasting radios, resulting in compromised reliability, efficiency and fairness of DSRC. In order to optimize the performance of DSRC, we develop a novel Online Control Approach of power and Rates (OnCAR). Supported by systematic control theories, OnCAR performs stably even in the dynamic and unpredictable vehicular environments. To the best of our knowledge, OnCAR is the first solution to address the strong coupling between communication variables. It adopts a multi-variable control model to synchronously adjust transmission power and data rates, which are two major variables determining the performance of DSRC. In addition, OnCAR leverages receiver-side measurements of performance metrics to strike a balance between overall performance and fairness. Compared with the state of the art, OnCAR enhances the overall reliability and efficiency of DSRC by 23.7% and 30.1%, respectively. Meanwhile, these numbers are achieved with a 40.1% improvement in fairness.
【Keywords】: Reliability; Couplings; Vehicles; Accidents; Safety; Vehicle dynamics; Measurement
【Paper Link】 【Pages】:1-9
【Authors】: Andrew Fox ; B. V. K. Vijaya Kumar ; Fan Bai
【Abstract】: Crowdsourcing data from multiple sensing agents has become a fundamental mechanism for extracting information in large-scale cyber-physical systems (CPS). However, there has been little attention paid to the difficulties crowdsourcing presents when the desired information is represented by continuous signals. Crowdsourcing can result in unique types of noise in the aggregated data sample set. Errors from clock synchronization, GPS location determination, or sensor heterogeneity result in biased and correlated errors in the sampled data from each individual sensor. Furthermore, in CPS sensors are often mobile and operate asynchronously. This affects the spatial sampling rates among sensors and results in nonuniform sample spacing. We refer to these sampling issues as the noisy multi-source, variable-rate (MSVR) sampling problem. This work introduces and investigates signal reconstruction algorithms given MSVR sampling conditions. These signal reconstructions are investigated for vehicular applications, using a joint road inclination and bank angle signal estimation algorithm that has access to MSVR sampled vehicle GPS and accelerometer data. The signal reconstruction and angle determination algorithms are validated on simulated and real-world vehicle data, where we reconstruct a road elevation signal with 0.89 m root-mean-square error.
【Keywords】: Roads; Vehicles; Signal reconstruction; Global Positioning System; Measurement uncertainty; Weight measurement; Sensors
【Paper Link】 【Pages】:1-9
【Authors】: Zhichen Wu ; Jianda Li ; Jiadi Yu ; Yanmin Zhu ; Guangtao Xue ; Minglu Li
【Abstract】: When vehicle road-level localization cannot satisfy people's need for convenience and safety driving, lane-level localization becomes a corner stone in Intelligent Transportation System. Existing work on tracking vehicles on lane-level mostly depends on pre-deployed infrastructures and additional hardwares. In this paper, we utilize smartphone sensing of driving conditions for vehicle lane-level localization on highways. We analyze the driving traces collected from real driving environments, finding that each type of lane change has its unique pattern on the vehicle's lateral acceleration. Based on this observation, we propose a Lane-Level Localization (L3) system, which can perform real-time vehicle localization on lane-level only using smartphones when vehicles are driving on highways. Our system first uses embedded sensors in smartphones to capture the patterns of lane change behaviors. Then a Gaussian Distribution is employed to track vehicles on lane-level with tolerance of false detections. Extensive experiments demonstrate that L3 is accurate and robust in real driving environments. The experimental results show that, on average, L3 achieves accuracy of 91.49% on lane change detection and 86.94% on lane-level localization.
【Keywords】: Vehicles; Acceleration; Sensors; Roads; Global Positioning System; Real-time systems
【Paper Link】 【Pages】:1-9
【Authors】: Tianyi Song ; Xiuzhen Cheng ; Hongjuan Li ; Jiguo Yu ; Shengling Wang ; Rongfang Bie
【Abstract】: The use of mobile phones while driving has become a major source of distraction to drivers, leading to a large number of car accidents. In this paper, we study the problem of automatically detecting driver phone calls by monitoring smartphone activities and utilizing the vehicle on-board unit. The challenges to overcome include: i) passenger phone calls should be allowed while the calls of the driver should be blocked; ii) the detection mechanism should be phone position-independent and phone owner-independent as the driver may put the smartphone at any position in the front row and make calls via an earphone, or the driver may borrow a passenger's phone to make a call; iii) the in-vehicle environment is noisy resulted from the operating engine, the music the driver and passenger may listen to, and the conversation between passengers and/or the driver; and iv) the computational cost at the smartphone should be light as realtime phone call detection is expected to effectively block an ongoing call to and from the driver. To overcome these challenges and achieve our objective of detecting driver phone calls, we take advantage of the uniqueness of individual's voice features. Through a short period of learning stage, our proposed system can recognize the driver's voice from the collected audio data. Combined with the smartphone's call state, our scheme can determine whether the driver is participating in the current phone call or not. Our strategy takes into account the complicated in-vehicle environment, and the proposed algorithm does not rely on the location of the phone within the vehicle nor the ownership of the smartphone, as the most existing driver phone call detection mechanisms do. We develop a client-server based system with the smartphones being the clients and the vehicle on-board unit being the server. To validate our mechanism, we perform extensive real-world experiments under different scenarios. The results demonstrate a high probability of detecting driver phone calls with a small false alarm rate.
【Keywords】: Cellular phones; Automobiles; Feature extraction; Microphones; Accidents; Monitoring
【Paper Link】 【Pages】:1-9
【Authors】: Sijia Gu ; Zongpeng Li ; Chuan Wu ; Chuanhe Huang
【Abstract】: Network Function Virtualization (NFV) is emerging as a new paradigm for providing elastic network functions through flexible virtual network function (VNF) instances executed on virtualized computing platforms exemplified by cloud datacenters. In the new NFV market, well defined VNF instances each realize an atomic function that can be chained to meet user demands in practice. This work studies the dynamic market mechanism design for the transaction of VNF service chains in the NFV market, to help relinquish the full power of NFV. Combining the techniques of primal-dual approximation algorithm design with Myerson's characterization of truthful mechanisms, we design a VNF chain auction that runs efficiently in polynomial time, guarantees truthfulness, and achieves near-optimal social welfare in the NFV eco-system. Extensive simulation studies verify the efficacy of our auction mechanism.
【Keywords】: Approximation algorithms; Algorithm design and analysis; Resource management; Heuristic algorithms; Software; Standards; Hardware
【Paper Link】 【Pages】:1-9
【Authors】: Juntao Wang ; Xun Xiao ; Jianping Wang ; Kejie Lu ; Xiaotie Deng ; Ashwin Gumaste
【Abstract】: As a major driving force for adopting cloud computing, continuous cost reduction has been constantly pursued by cloud users. For a group of users with heterogeneous cloud resource demands, it may be possible for them to buy resources in a collaborative way in order to save the purchase cost, which is known as group-buying in business. While group-buying can benefit cloud users in principle, the question is how to design an implementation scheme to support group-buying on the cloud market. In this paper, we address the question by studying a coalition formation game, aiming to design a way under which the users can form stable coalitions for group-buying. It turns out that group-buying on the cloud market is challenging in that most popular solution concepts may fail to constitute stable coalitions. In order to sustain group-buying for cloud services, we propose a new solution concept, contractually group stable, which is an extension of an existing concept in the literature. We show that this new solution concept can guarantee the existence of stable coalitions, making group-buying always possible on the cloud market. We also develop computing algorithms for solving the coalition formation game under our concept. Computational experiments show that our concept can bring in substantial cost reduction for cloud users.
【Keywords】: Cloud computing; Stability analysis; Games; Power system stability; Algorithm design and analysis; Computer science; Business
【Paper Link】 【Pages】:1-9
【Authors】: Weijie Shi ; Chuan Wu ; Zongpeng Li
【Abstract】: It is common for cloud users to require clusters of inter-connected virtual machines (VMs) in a geo-distributed IaaS cloud, to run their services. Compared to isolated VMs, key challenges on dynamic virtual cluster (VC) provisioning (computation + communication resources) lie in two folds: (1) optimal placement of VCs and inter-VM traffic routing involve NP-hard problems, which are non-trivial to solve offline, not to mention if an online efficient algorithm is sought; (2) an efficient pricing mechanism is missing, which charges a market-driven price for each VC as a whole upon request, while maximizing system efficiency or provider revenue over the entire span. This paper proposes efficient online auction mechanisms to address the above challenges. We first design SWMOA, a novel online algorithm for dynamic VC provisioning and pricing, achieving truthfulness, individual rationality, computation efficiency, and (1 + 2 log μ)-competitiveness in social welfare, where μ is related to the problem size. Next, applying a randomized reduction technique, we convert the social welfare maximizing auction into a revenue maximizing online auction, PRMOA, achieving O(log μ)-competitiveness in provider revenue, as well as truthfulness, individual rationality and computation efficiency. We validate the efficacy of the mechanisms through solid theoretical analysis and trace-driven simulations.
【Keywords】: Cloud computing; Heuristic algorithms; Bandwidth; Resource management; Algorithm design and analysis; Pricing; Cost accounting
【Paper Link】 【Pages】:1-9
【Authors】: Cheng Chen ; Randall A. Berry ; Michael L. Honig ; Vijay G. Subramanian
【Abstract】: Small cells deployed in licensed spectrum and unlicensed access via WiFi provide different ways of expanding wireless services to low mobility users. That reduces the demand for conventional macro-cellular networks, which are better suited for wide-area mobile coverage. The mix of these technologies seen in practice depends in part on the decisions made by wireless service providers that seek to maximize revenue, and allocations of licensed and unlicensed spectrum by regulators. To understand these interactions we present a model in which a service provider allocates available licensed spectrum across two separate bands, one for macro- and one for small-cells, in order to serve two types of users: mobile and fixed. We assume a service model in which the providers can charge a (different) price per unit rate for each type of service (macro- or small-cell); unlicensed access is free. With this setup we study how the addition of unlicensed spectrum affects prices and the optimal allocation of bandwidth across macro-/small-cells. We also characterize the optimal fraction of unlicensed spectrum when new bandwidth becomes available.
【Keywords】: Bandwidth; IEEE 802.11 Standard; Resource management; Mobile communication; Pricing; Channel allocation; Monopoly
【Paper Link】 【Pages】:1-9
【Authors】: Lorenzo Saino ; Ioannis Psaras ; George Pavlou
【Abstract】: Sharding is a method for allocating data items to nodes of a distributed caching or storage system based on the result of a hash function computed on the item identifier. It is ubiquitously used in key-value stores, CDNs and many other applications. Despite considerable work has focused on the design and the implementation of such systems, there is limited understanding of their performance in realistic operational conditions from a theoretical standpoint. In this paper we fill this gap by providing a thorough modeling of sharded caching systems, focusing particularly on load balancing and caching performance aspects. Our analysis provides important insights that can be applied to optimize the design and configuration of sharded caching systems.
【Keywords】: Load modeling; Load management; Random variables; Games; Databases; Analytical models; Harmonic analysis
【Paper Link】 【Pages】:1-9
【Authors】: Li Qiu ; Guohong Cao
【Abstract】: Caching in wireless ad hoc networks can reduce network traffic and content access delay, as nodes can retrieve contents from near neighbors rather than the faraway server. However, the fundamental performance limits of caching in wireless ad hoc networks have rarely been studied in an analytical manner. In this paper, we study the fundamental property of wireless networks with caching, i.e., the scaling laws of the network capacity based on cache size of individual node, the total size of unique content and the number of nodes in the network. We present an upper bound on network capacity, and present an achievable capacity lower bound, where we propose a caching scheme to show what capacity can actually be achievable. Our results suggest that the capacity of wireless ad hoc networks with caching can remain constant even as the number of nodes in the network increases. We also present numerical results and demonstrate that our results are consistent with existing analytical results under extreme conditions where the node communication scenario matches theirs.
【Keywords】: Mobile ad hoc networks; Upper bound; Wireless networks; Throughput; Delays
【Paper Link】 【Pages】:1-9
【Authors】: Ammar Gharaibeh ; Abdallah Khreishah ; Issa Khalil
【Abstract】: Since the emergence of Content Centric Networking (CCN) as a new paradigm for content delivery in the Internet, copious of research targeted the evaluation or the enhancement of CCN caching schemes. Motivated by providing the Internet Service Providers with incentives to perform caching, the increasing deployment of in-network cloudlets, and the low cost of storage devices, we study caching in CCN from an economical point of view, where the content providers pay the Internet Service Providers in exchange for caching their content items. We propose an online caching algorithm for CCN that does not require the exact knowledge of content items' popularities to minimize the total cost paid by the content providers. The total cost here is the sum of the caching costs and the retrieval costs. Our analysis shows that the proposed algorithm achieves an O(1) competitive ratio when compared to the optimal offline caching scheme that possesses the exact knowledge of content items' popularities. We also show through simulations that the proposed algorithm can cut the cost incurred by widely used caching schemes such as Leave Copy Down (LCD) and Leave Copy Everywhere (LCE) by up to 65%.
【Keywords】: Algorithm design and analysis; Routing; Optimization; Knowledge engineering; Web and internet services; Cloud computing
【Paper Link】 【Pages】:1-9
【Authors】: Mostafa Dehghan ; Laurent Massoulié ; Don Towsley ; Daniel S. Menasché ; Y. C. Tay
【Abstract】: In any caching system, the admission and eviction policies determine which contents are added and removed from a cache when a miss occurs. Usually, these policies are devised so as to mitigate staleness and increase the hit probability. Nonetheless, the utility of having a high hit probability can vary across contents. This occurs, for instance, when service level agreements must be met, or if certain contents are more difficult to obtain than others. In this paper, we propose utility-driven caching, where we associate with each content a utility, which is a function of the corresponding content hit probability. We formulate optimization problems where the objectives are to maximize the sum of utilities over all contents. These problems differ according to the stringency of the cache capacity constraint. Our framework enables us to reverse engineer classical replacement policies such as LRU and FIFO, by computing the utility functions that they maximize. We also develop online algorithms that can be used by service providers to implement various caching policies based on arbitrary utility functions.
【Keywords】: Optimization; Algorithm design and analysis; Cache storage; Internet; Analytical models; Resource management; Aggregates
【Paper Link】 【Pages】:1-9
【Authors】: Zhenghao Zhang ; Avishek Mukherjee
【Abstract】: Privacy has become a major concern in wireless networks, especially in networks with weak or no password protection. While it has been proposed to send jamming signals to thwart the reception of the eavesdropper, the jamming signal typically cannot introduce enough errors to cover the entire packet when the jamming signal is not very strong, mainly due to the use of error correction codes in the system. Fortunately, error amplifiers can be easily constructed using block ciphers to amplify and spread the errors without requiring any secret keys. With error amplification, the jamming strategy needs to be revisited, because introducing a few errors is sufficient protect the privacy of the entire packet, instead of having to jam the entire packet. We propose a novel jamming strategy, called jMax, with proven performance bounds to the optimal jamming signal power. The idea of jMax is to rotate jamming vectors such that the jamming power can be maximized when the jamming vector close to the optimal jamming vector is used. We collect real-world CSI data with the Intel 5300 wireless card and use the Microsoft Sora Software-Defined Radio to process jammed data packets. Our results show that jMax achieves significant gains over other approaches.
【Keywords】: Jamming; OFDM; Antennas; Error correction codes; Ciphers; IEEE 802.11 Standard; Privacy
【Paper Link】 【Pages】:1-9
【Authors】: Peyman Siyari ; Marwan Krunz ; Diep N. Nguyen
【Abstract】: In this paper, we expand the scope of PHY-layer security by investigating TX-based friendly jamming (FJ) for the wiretap channel in multi-link settings. For the single-link scenario, creating a TX-based FJ is an effective and practical method in improving the secrecy rate. In a multi-link setting, several information signals must be transmitted simultaneously. Thus, the design must guarantee that the FJ signal of a given transmitter does not interfere with unintended but legitimate receivers. Under the assumption of exact knowledge of the eavesdropping channel, we first propose a distributed price-based approach to improve the secrecy sum-rate of a two-link network with one eavesdropper while satisfying an information-rate constraint for both link. Simulations show that price-based FJ control outperforms greedy FJ, and is close to the performance of a centralized approach. Next, we propose a method based on mixed strategic games that can offer robust solutions to the distributed secrecy sum-rate maximization problem under the assumption of an unknown eavesdropping channel. Lastly, we use simulations to show that in addition to outperforming the greedy approach, our robust optimization also satisfies practical network considerations. In particular, the transmission time for the robust optimization can be determined flexibly to match the channel's coherence time.
【Keywords】: Interference; Receivers; Transmitters; Jamming; Security; Robustness; Information rates
【Paper Link】 【Pages】:1-9
【Authors】: Zhihong Liu ; Jiajia Liu ; Nei Kato ; Jianfeng Ma ; Qiping Huang
【Abstract】: This paper investigates divide-and-conquer based cooperative jamming for physical-layer security enhancement in the presence of multiple eavesdroppers. Different from previous works, we consider a scenario where the eavesdroppers can be located anywhere inside the communication region of the source, no location information of the eavesdroppers is available and no constraint on the number of eavesdroppers is presupposed. The basic idea is to transmit the message in multiple rounds and exploit the helpful interference from the source and the destination to jam the eavesdroppers in close proximity. Stochastic geometry based analytic results as well as Monte Carlo simulations are presented to illustrate the achievable secrecy performances.
【Keywords】: Jamming; Interference; Communication system security; Wireless networks; Manganese; Security
【Paper Link】 【Pages】:1-9
【Authors】: Manjesh Kumar Hanawal ; Diep N. Nguyen ; Marwan Krunz
【Abstract】: Recent advances in the design of in-band full-duplex (IBFD) radios promise to double the throughput of a wireless link. However, IBFD-capable nodes are more vulnerable to jamming attacks than their out-of-band full-duplex (OBFD) counterparts, and any advantages offered by them over the OBFD nodes can be jeopardized by such attacks. A jammer needs to attack both the uplink and the downlink channels to completely break the communication link between two OBFD nodes. In contrast, he only needs to jam one channel (used for both uplink and downlink) in the case of two IBFD nodes. Even worse, a jammer with the IBFD capability can learn the transmitters' activity while injecting interference, allowing it to react instantly with the transmitter's strategies. In this paper, we investigate frequency hopping (FH) technique for countering jamming attacks in the context of IBFD wireless radios. Specifically, we develop an optimal strategy for IBFD radios to combat an “IBFD reactive sweep jammer”. First, we introduce two operational modes for IBFD radios: transmission reception and transmission-detection. These modes are intended to boost the anti-jamming capability of IBFD radios. We then jointly optimize the decision of when to switch between the modes and when to hop to a new channel using Markov decision processes. Numerical investigations show that our policy significantly improves the throughput of IBFD nodes under jamming attacks.
【Keywords】: Jamming; Throughput; Fading channels; Interference; Switches; Silicon; Uplink
【Paper Link】 【Pages】:1-9
【Authors】: Yaxiong Xie ; Zhenjiang Li ; Mo Li ; Kyle Jamieson
【Abstract】: Due to frequency selective fading, modern wideband 802.11 transmissions have unevenly distributed bit BERs in a packet. In this paper, we propose to unequally protect packet bits according to their BERs. By doing so, we can best match the effective transmission rate of each bit to channel condition, and improve throughput. The major design challenge lies in deriving an accurate relationship between the frequency selective channel condition and the decoded packet bit BERs, all the way through the complex 802.11 PHY layer. Based on our study, we find that the decoding error of a packet bit corresponds to dense errors in the underlying codeword bits, and the BER can be truthfully approximated by the codeword bit error density. With above observation, we propose UnPKT, scheme that protects packet bits using different MAC-layer FEC redundancies based on bit-wise BER estimation to augment wide-band 802.11 transmissions. UnPKT is software-implementable and compatible with the existing 802.11 architecture. Extensive evaluations based on Atheros 9580 NICs and GNU-Radio platforms show the effectiveness of our design. UnPKT can achieve a significant goodput improvement over state-of-the-art approaches.
【Keywords】: Bit error rate; IEEE 802.11 Standard; OFDM; Throughput; Redundancy; Fading channels; Decoding
【Paper Link】 【Pages】:1-9
【Authors】: Kimin Lee ; Yeonkeun Kim ; Seokhyun Kim ; Jinwoo Shin ; Seungwon Shin ; Song Chong
【Abstract】: In the past years, the centralized management of dense wireless local area networks has been emerged as a powerful paradigm for improving energy efficiency as well as avoiding severe interference. In this paper, we study the joint optimization on power-operation modes in access points (APs), channel selections and user-AP associations for improving energy efficiency and avoiding interference without sacrificing users' demands. To this end, we first formulate it as a mixed-integer programming using the popular Lyapunov approach, but it turns out to be computationally intractable, i.e., NP-hard. To address the issue, we propose a polynomial-time approximation algorithm and prove that it achieves a constant-factor approximation guarantee under mild assumptions. The main novelty underlying our algorithm design is based on a linear programming relaxation combining with two different greedy rounding schemes, where each achieves a constant-factor approximation in different regimes of parameters. We verify the performance of the proposed algorithm via extensive simulations and also demonstrate its practicability by implementing it at commercial APs using a Software-defined Networking framework, which shows that it reduces the wasted energy significantly while maintaining even higher throughput.
【Keywords】: Interference; Power demand; Approximation algorithms; Optimization; Algorithm design and analysis; Wireless LAN; Energy consumption
【Paper Link】 【Pages】:1-9
【Authors】: Kun Qian ; Chenshu Wu ; Zheng Yang ; Zimu Zhou ; Xu Wang ; Yunhao Liu
【Abstract】: Modern mobile devices are equipped with multiple antennas, which brings various wireless sensing applications such as accurate localization, contactless human detection and wireless human-device interaction. A key enabler for these applications is phased array signal processing, especially Angle of Arrival (AoA) estimation. However, accurate AoA estimation on commodity devices is non-trivial due to limited number of antennas and uncertain phase offsets. Previous works either rely on elaborate calibration or involve contrived human interactions. In this paper, we aim to enable practical AoA measurements on commodity off-the-shelf (COTS) mobile devices. The key insight is to involve users' natural rotation to formulate a virtual spatial-temporal antenna array and conduce a relative incident signal of measurements at two orientations. Then by taking the differential phase, it is feasible to remove the phase offsets and derive the accurate AoA of the equivalent incoming signal, while the rotation angle can also be captured by built-in inertial sensors. On this basis, we propose Differential MUSIC (D-MUSIC), a relative form of the standard MUSIC algorithm that eliminates the unknown phase offsets and achieves accurate AoA estimation on COTS mobile devices with only one rotation. We further extend D-MUSIC to 3-D space and fortify it in multipath-rich scenarios. We prototype D-MUSIC on commodity WiFi infrastructure and evaluate it in typical indoor environments. Experimental results demonstrate a superior performance with an average AoA estimation error of 13°. Requiring no modifications or calibration, D-MUSIC is envisioned as a promising scheme for practical AoA estimation on COTS mobile devices.
【Keywords】: Antenna measurements; Antenna arrays; Multiple signal classification; Estimation; Phase measurement; Mobile handsets
【Paper Link】 【Pages】:1-9
【Authors】: Jinghao Shi ; Lei Meng ; Aaron Striegel ; Chunming Qiao ; Dimitrios Koutsonikolas ; Geoffrey Challen
【Abstract】: During the one minute it takes to read this abstract, two billion smartphones worldwide will perform billions of Wifi channel scans recording the signal strength of nearby Wifi Access Points (APs). Yet despite this ongoing planetary-scale wireless network measurement, few systematic efforts are made today to recover this potentially valuable data. In this paper we ask the question: “Are the smartphone channel scans useful in monitoring enterprise Wifi networks?” More specifically, can these client-side measurements provide new insights compared to the AP-side measurements that enterprise Wifi networks already perform? Beginning with two Wifi scan datasets collected on two large scale smartphone testbeds, we conduct case studies that show how smartphone channel scans can be used to (1) improve AP spectrum management, and (2) predict the impact of AP failure or overload. In each case, a walk on the client side yields valuable insights for network operators that are otherwise impossible to gain from AP-side measurements, and together our results demonstrate the value of smartphone channel scans.
【Keywords】: Wireless networks; Monitoring; Data collection; Extraterrestrial measurements; Performance evaluation; Mobile handsets
【Paper Link】 【Pages】:1-9
【Authors】: Alessandro Enrico Redondi ; Luca Baroffio ; Matteo Cesana ; Marco Tagliasacchi
【Abstract】: Visual Sensor Networks (VSNs) have been recently used for implementing automatic visual analysis tasks where local image features, instead of images, are compressed and transmitted to a central controller. Such features may also be compressed in a multi-view fashion, exploiting the redundancy between overlapping views. In this paper we analyze the problem of multi-view coding and routing of features in VSNs. We empirically analyze the relationship between the bitrate reduction obtained with a practical multi-view local features encoder and several geometry-based, image-based and feature-based predictors. The purpose of this analysis is to identify the most accurate, yet compact predictor of the achievable compression efficiency when jointly encoding correlated streams of local features. Then, we propose a robust optimization framework that exploits the aforementioned predictors. The proposed mathematical problem maximizes the amount of data extracted from the VSN by properly routing the streams of features, subject to capacity, interference and energy constraints, explicitly considering the uncertainty in the compression efficiency estimation. Extensive experiments on simulated VSNs show that multi-view coding maximizes the amount of data extracted from camera nodes, while the robust optimization approach provides significant improvement in uncertain scenarios compared to the optimal solution of a deterministic approach.
【Keywords】: Feature extraction; Cameras; Visualization; Image coding; Encoding; Correlation; Routing
【Paper Link】 【Pages】:1-9
【Authors】: Chunyan Liu ; Hejiao Huang ; Hongwei Du ; Xiaohua Jia
【Abstract】: In wireless sensor networks, Virtual Backbone (VB) construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Transmission ranges of sensors are not always equivalent. A sensor networks is modeled as a directed graph while sensors have different transmission ranges. In this paper, we will try to find a special Strongly Connected Bidirectional Dominating Set (SCBDS) within minimum routing cost for each pair of nodes in directed graphs. The SCBDS forms a VB of the networks whose sensors have different transmission radius. For any pair of sensors, the length of the shortest path they communicate with each other through VB should be no more than a constant times the length of the shortest path without using VB. We propose a constant approximate scheme to construct the SCBDS with the bounded size 3*(8ρ+1)2(2ρ+1)2/2 opt. A centralized and a distributed algorithm with the same performance ratio are presented to show the details to construct the SCDS in directed graphs. Simulation results show that the average shortest path length through our algorithms is reduced greatly compared with other algorithms.
【Keywords】: Routing; Approximation algorithms; Wireless sensor networks; Sensors; Wireless networks; Broadcasting; Distributed algorithms
【Paper Link】 【Pages】:1-8
【Authors】: Zhao Zhang ; Jiao Zhou ; Yuchang Mo ; Ding-Zhu Du
【Abstract】: Using a connected dominating set (CDS) to serve as a virtual backbone of a wireless sensor network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). A subset of nodes C ⊆ V(G) is a (k, m)-CDS of G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. In this paper, we present an approximation algorithm for the minimum (3, m)-CDS problem with m > 3, which has size at most γ times that of an optimal solution, where γ = α + 8 + 21n(2α - 6) for α > 4 and γ = 3α + 2 In 2 for α <; 4, and α is the approximation ratio for the minimum (2, m)-CDS problem. This is the first performance-guaranteed algorithm for the minimum (3, m)-CDS problem in a general wireless network, and improves previous performance ratio in a homogeneous wireless sensor network by a large amount.
【Keywords】: Hafnium; Approximation algorithms; Wireless sensor networks; Sensors; Fault tolerance; Fault tolerant systems; Wireless networks
【Paper Link】 【Pages】:1-9
【Authors】: Abdul Salam ; Mehmet Can Vuran ; Suat Irmak
【Abstract】: Wireless underground sensor networks (WUSNs) are becoming ubiquitous in many areas and designing robust systems requires extensive understanding of the underground (UG) channel characteristics. In this paper, UG channel impulse response is modeled and validated via extensive experiments in indoor and field testbed settings. Three distinct types of soils are selected with sand and clay contents ranging from 13% to 86% and 3% to 32%, respectively. Impacts of changes in soil texture and soil moisture are investigated with more than 1,200 measurements in a novel UG testbed that allows flexibility in soil moisture control. Time domain characteristics of channel such as RMS delay spread, coherence bandwidth, and multipath power gain are analyzed. The analysis of the power delay profile validates the three main components of the UG channel: direct, reflected, and lateral waves. It is shown that RMS delay spread follows a log-normal distribution. The coherence bandwidth ranges between 650 kHz and 1.15MHz for soil paths of up to 1m and decreases to 418 kHz for distances above 10m. Soil moisture is shown to affect RMS delay spread non-linearly, which provides opportunities for soil moisture-based dynamic adaptation techniques. The model and analysis paves the way for tailored solutions for data harvesting, UG sub-carrier communication, and UG beamforming.
【Keywords】: Delays; Soil moisture; Soil measurements; Receivers; Wireless communication; Attenuation
【Paper Link】 【Pages】:1-9
【Authors】: Qian Wang ; Yan Zhang ; Xiao Lu ; Zhibo Wang ; Zhan Qin ; Kui Ren
【Abstract】: Nowadays gigantic crowd-sourced data collected from mobile phone users have become widely available, which enables the possibility of many important data mining applications to improve the quality of our daily lives. While providing tremendous benefits, the release of these data to the public will pose a considerable threat to mobile users' privacy. To solve this problem, the notion of differential privacy has been proposed to provide privacy with theoretical guarantee, and recently it has been applied in streaming data publishing. However, most of the existing literature focus on either event-level privacy on infinite streams or user-level privacy on finite streams. In this paper, we investigate the problem of real-time spatiotemporal crowd-sourced data publishing with privacy preservation. Specifically, we consider continuous publication of population statistics for monitoring purposes and design RescueDP-an online aggregate monitoring scheme over infinite streams with privacy guarantee. RescueDP's key components include adaptive sampling, adaptive budget allocation, dynamic grouping, perturbation and filtering, which are seamlessly integrated as a whole to provide privacy-preserving statistics publishing on infinite time stamps. We show that RescueDP can achieve w-event privacy over data generated and published periodically by crowd users. We evaluate our scheme with real-world as well as synthetic datasets and compare it with two w-event privacy-assured representative benchmarks. Experimental results show that our solution outperforms the existing methods and improves the utility with strong privacy guarantee.
【Keywords】: Privacy; Data privacy; Publishing; Real-time systems; Monitoring; Resource management; Servers
【Paper Link】 【Pages】:1-9
【Authors】: Adriano Di Luzio ; Alessandro Mei ; Julinda Stefa
【Abstract】: Whenever our smartphones have their WiFi radio interface on, they periodically try to connect to known wireless APs (networks the user has connected to in the past). This is done through WiFi Probe requests - special wireless frames that contain the MAC address of the sending device and, in most of the cases, the human-readable name-string (SSID) of the known AP. This semantic information, inherent to the network protocol, is sent in the clear and, if sniffed, can help discover important information and phenomena of people and human nature that have nothing to do with technology. In this paper we present the idea of exploiting WiFi probe requests to de-anonymize the origin of participants in large events. We make use of several, publicly available datasets containing more than 11M of probe requests collected in scenarios that are of citywide, national (two political meetings), and international religion-related relevance. We show how, by exploiting the semantic information brought by the relative WiFi probes, we are able to discover with high accuracy the provenance of the crowds in each event. In particular, the de-anonymization outcome of the two political meetings held few days before the election days in Italy match surprisingly well the official voting results reported for the two respective parties.
【Keywords】: Probes; IEEE 802.11 Standard; Wireless communication; Nominations and elections; Urban areas; Mobile communication; Semantics
【Paper Link】 【Pages】:1-9
【Authors】: Qian Wang ; Shengshan Hu ; Kui Ren ; Jingjun Wang ; Zhibo Wang ; Minxin Du
【Abstract】: Advances in cloud computing have greatly motivated data owners to outsource their huge amount of personal multimedia data and/or computationally expensive tasks onto the semi-trusted cloud by leveraging its abundant resources for cost saving and flexibility. From the privacy perspective, however, the outsourced multimedia data and its originated applications may reveal the data owner's private information, such as the personal identity, locations or even financial profiles. This observation has recently aroused new research interest on privacy-preserving computations over outsourced multimedia data. In this paper, we propose an effective privacy-preserving computation outsourcing protocol for the prevailing scale-invariant feature transform (SIFT) over massive encrypted image data. We first show that previous solutions to this problem have either efficiency/security or practicality issues, and none can well preserve the important characteristics of the original SIFT in terms of distinctiveness and robustness. We for the first time present a new privacy-preserving outsourcing protocol for SIFT with the preservation of its key characteristics, by randomly splitting the original image data, carefully distributing the feature extraction computations to two independent cloud servers and further leveraging the garbled circuit for secure keypoints comparisons. We both carefully analyze and extensively evaluate the security and effectiveness of our design. The results show that our solution is practically secure, outperforms the state-of-the-art and performs comparably to the original SIFT in terms of various characteristics, including rotation invariance, image scale invariance, robust matching across affine distortion and change in 3D viewpoint.
【Keywords】: Feature extraction; Cryptography; Outsourcing; Protocols; Servers; Wires; Multimedia communication
【Paper Link】 【Pages】:1-9
【Authors】: Jingchao Sun ; Rui Zhang ; Jinxue Zhang ; Yanchao Zhang
【Abstract】: Distributed stream monitoring has numerous potential applications in future smart cities. Communication efficiency, and data privacy are two main challenges for distributed stream monitoring services. In this paper, we propose PriStream, the first communication-efficient and privacy-preserving distributed stream monitoring system for thresholded PERCENTILE aggregates. PriStream allows the monitoring service provider to evaluate an arbitrary function over a desired percentile of distributed data reports and monitor when the output exceeds a predetermined system threshold. Detailed theoretical analysis and evaluations show that PriStream has high accuracy and communication efficiency, and differential privacy guarantees under a strong adversary model.
【Keywords】: Monitoring; Privacy; Sensors; Aggregates; Silicon; Distributed databases; Peer-to-peer computing
【Paper Link】 【Pages】:1-9
【Authors】: Kanthaiah Vijayalayan ; Darryl Veitch
【Abstract】: Timekeeping is central to network measurement. In typical systems, its accuracy is ultimately dependent on the forest of timeservers accessible over the network, whose roots are the stratum-1 timeservers, which benefit from reference hardware. It is essential that these servers are accurate and reliable, and it is commonly assumed that this is the case. We put this belief to the test through an examination of around 100 publicly accessible stratum-1 servers, using datasets spanning over 3 years, collected in a testbed with reference timestamping. We develop a methodology capable of disambiguating the effects of routing changes, congestion related variability, and server anomalies on timestamps. We use it to make a first assessment of the health of (public) network timing, by reporting on the type, severity, and frequency of anomalies we encounter.
【Keywords】: Servers; Synchronization; Australia; Delays; Clocks; IP networks
【Paper Link】 【Pages】:1-9
【Authors】: Kun Xie ; Lele Wang ; Xin Wang ; Gaogang Xie ; Jigang Wen ; Guangxing Zhang
【Abstract】: The inference of traffic volume of the whole network from partial traffic measurements becomes increasingly critical for various network engineering tasks, such as traffic prediction, network optimization, and anomaly detection. Previous studies indicate that the matrix completion is a possible solution for this problem. However, as a two-dimension matrix cannot sufficiently capture the spatial-temporal features of traffic data, these approaches fail to work when the data missing ratio is high. To fully exploit hidden spatial-temporal structures of the traffic data, this paper models the traffic data as a 3-way traffic tensor and formulates the traffic data recovery problem as a low-rank tensor completion problem. However, the high computation complexity incurred by the conventional tensor completion algorithms prevents its practical application for the traffic data recovery. To reduce the computation cost, we propose a novel Sequential Tensor Completion algorithm (STC) which can efficiently exploit the tensor decomposition result for the previous traffic data to deduce the tensor decomposition for the current data. To the best of our knowledge, we are the first to apply the tensor to model Internet traffic data to well exploit their hidden structures and propose a sequential tensor completion algorithm to significantly speed up the traffic data recovery process. We have done extensive simulations with the real traffic trace as the input. The simulation results demonstrate that our algorithm can achieve significantly better performance compared with the literature tensor and matrix completion algorithms even when the data missing ratio is high.
【Keywords】: Tensile stress; Data models; Computational modeling; Correlation; Internet; Algorithm design and analysis; Feature extraction
【Paper Link】 【Pages】:1-9
【Authors】: Lin Yang ; Mingxuan Yuan ; Wei Wang ; Qian Zhang ; Jia Zeng
【Abstract】: Owing to the proliferation of mobile devices and their corresponding app ecosystems, more and more people are accessing the internet via various mobile apps, which generates tremendous volume of mobile data. Despite the growing importance of these mobile apps, we have a rather sparse understanding of how they are accessed and what issues affect their usage patterns. To address this problem, we perform a comprehensive measurement on large-scale anonymized network data collected from a tier-1 cellular carrier in China. In this measurement, we characterize the usage pattern of mobile apps and exhibit how the mobility, geospatial properties and behaviours of subscribers affect their mobile app usage at a fine-grained level.
【Keywords】: Conferences; Computers
【Paper Link】 【Pages】:1-9
【Authors】: Ioana Livadariu ; Ahmed Elmokashfi ; Amogh Dhamdhere
【Abstract】: End-to-end IPv6 performance is a factor that can influence IPv6 adoption. The stability of IPv6 - both in the control and data plane - is an important determinant of end-to-end performance, as it influences packet loss, network latency, and hence application performance. In this paper we compare stability and performance measurements from the control and data plane in IPv6 and IPv4. To study control plane stability, we use BGP feeds from five dual-stacked vantage points to measure routing dynamics towards IPv4 and IPv6 destinations. To study data plane stability, we probe dual-stacked webservers in 629 target ASes to determine the availability, RTT performance and RTT stability of paths toward these targets. In both control and data plane experiments IPv6 exhibited less stability than IPv4. In the control plane, most routing dynamics were generated by a small fraction of pathological unstable prefixes. In the data-plane, episodes of unavailability were longer on IPv6 than on IPv4. We found evidence of correlated performance degradation over IPv4 and IPv6 caused by shared infrastructure.
【Keywords】: Routing; Monitoring; Pathology; Internet; Electronic mail; Measurement; Feeds
【Paper Link】 【Pages】:1-9
【Authors】: Carlo Fuerst ; Stefan Schmid ; P. Lalith Suresh ; Paolo Costa
【Abstract】: In multi-tenant cloud environments, the absence of strict network performance guarantees leads to unpredictable job execution times. To address this issue, recently there have been several proposals on how to provide guaranteed network performance. These proposals, however, rely on computing resource reservation schedules a priori. Unfortunately, this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to differences in the input datasets or phenomena such as failures and stragglers. To overcome these limitations, we designed KRAKEN, a system that allows tenants to dynamically request and update minimum guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the tenants' applications but allows tenants to modify their reservation at runtime. Kraken achieves this through an online resource reservation scheme which comes with provable optimality guarantees. In this paper, we motivate the need for dynamic resource reservation schemes, present how this is provided by Kraken, and evaluate Kraken via extensive simulations.
【Keywords】: Bandwidth; Copper; Runtime; Clustering algorithms; Switches; Substrates; Virtual machining
【Paper Link】 【Pages】:1-9
【Authors】: Rashid Tahir ; Mohammad Taha Khan ; Xun Gong ; Adnan Ahmed ; AmirEmad Ghassami ; Hasanat Kazmi ; Matthew Caesar ; Fareed Zaffar ; Negar Kiyavash
【Abstract】: With the advent of big data, modern businesses face an increasing need to store and process large volumes of sensitive customer information on the cloud. In these environments, resources are shared across a multitude of mutually untrusting tenants increasing propensity for data leakage. This problem stands to grow further in severity with increasing use of clouds in all aspects of our daily lives and the recent spate of high-profile data exfiltration attacks are evidence. To highlight this serious issue, we present a novel and highspeed network-based covert channel that is robust and circumvents a broad set of security mechanisms currently deployed by cloud vendors. We successfully test our channel on numerous network environments, including commercial clouds such as EC2 and Azure. Using an information theoretic model of the channel, we derive an upper bound on the maximum information rate and propose an optimal coding scheme. Our adaptive decoding algorithm caters to the cross traffic in the channel and maintains high bit rates and extremely low error rates. Finally, we discuss several effective avenues for mitigation of the aforementioned channel and provide insights into how data exfiltration can be prevented in such shared environments.
【Keywords】: Cloud computing; Delays; Bit rate; Analytical models; Upper bound; Switches
【Paper Link】 【Pages】:1-9
【Authors】: Mehrnoosh Shafiee ; Javad Ghaderi
【Abstract】: We study the problem of load balancing in datacenter networks, namely, assigning the end-to-end data flows among the available paths in order to efficiently balance the load in the network. The solutions used today rely typically on ECMP (Equal Cost Multi Path) mechanism which essentially attempts to balance the load in the network by hashing the flows to the available shortest paths. However, it is well known that ECMP performs poorly when there is asymmetry either in the network topology or the flow sizes, and thus there has been much interest recently in alternative mechanisms to address these shortcomings. In this paper, we consider a general network topology where each link has a cost which is a convex function of the link utilization. Flows among the various source-destination pairs are generated dynamically over time, each with a size (bandwidth requirement) and a duration. Once a flow is assigned to a path in the network, it consumes bandwidth equal to its size from all the links along its path for its duration. We propose a low-complexity congestion-aware algorithm that assigns the flows to the available paths in an online fashion and without splitting, and prove that it asymptotically minimizes the total network cost. Extensive simulation results are presented to verify the performance of our algorithm under a wide range of traffic conditions and under different datacenter architectures.
【Keywords】: Switches; Servers; Network topology; Routing; Scheduling algorithms; Load management; Convex functions
【Paper Link】 【Pages】:1-9
【Authors】: Zhiming Hu ; Baochun Li ; Jun Luo
【Abstract】: Typically called big data processing, processing large volumes of data from geographically distributed regions with machine learning algorithms has emerged as an important analytical tool for governments and multinational corporations. The traditional wisdom calls for the collection of all the data across the world to a central datacenter location, to be processed using data-parallel applications. This is neither efficient nor practical as the volume of data grows exponentially. Rather than transferring data, we believe that computation tasks should be scheduled where the data is, while data should be processed with a minimum amount of transfers across datacenters. In this paper, we design and implement Flutter, a new task scheduling algorithm that improves the completion times of big data processing jobs across geographically distributed datacenters. To cater to the specific characteristics of data-parallel applications, we first formulate our problem as a lexicographical min-max integer linear programming (ILP) problem, and then transform it into a nonlinear program with a separable convex objective function and a totally unimodular constraint matrix, which can be solved using a standard linear programming solver efficiently in an online fashion. Our implementation of Flutter is based on Apache Spark, a modern framework popular for big data processing. Our experimental results have shown that we can reduce the job completion time by up to 25%, and the amount of traffic transferred among datacenters by up to 75%.
【Keywords】: Big data; Bandwidth; Linear programming; Sparks; Transforms; Processor scheduling; Distributed databases
【Paper Link】 【Pages】:1-9
【Authors】: Huiyuan Zhang ; Huiling Zhang ; Alan Kuhnle ; My T. Thai
【Abstract】: Information propagation in online social networks (OSNs), which helps shaping consumers' purchasing decisions, has received a lot of attention. The ultimate goal of marketing and advertising in OSNs is to massively influence audiences and enlarge the number of product adoptions. Most of existing works focus on maximizing the influence of a single product or promoting the adoption of one product in competing campaigns. However, in reality, the majority of companies produce various products for supplying customers with different needs. Therefore, it is truly significant and also challenging to wisely distribute limited budget across multiple products in viral marketing. In this paper, we investigate a Profit Maximization with Multiple Adoptions (PM2A) problem, which aims at maximizing the overall profit across all products. The natural greedy fails to provide a bounded result. In order to select high quality seeds for information propagation, we first proposed the PMCE algorithm, which has a ratio 1/2 (1 - 1/e2). Moreover, we further improve this ratio to (1-1/e) by proposing the PMIS algorithm. Comprehensive experiments on three real social networks are conducted. And results show that our algorithms outperform other heuristics, and better distribute the budget in terms of profit maximization.
【Keywords】: Integrated circuit modeling; Social network services; Companies; Approximation algorithms; Algorithm design and analysis; Biological system modeling; Diffusion processes
【Paper Link】 【Pages】:1-9
【Authors】: Ji Li ; Zhipeng Cai ; Mingyuan Yan ; Yingshu Li
【Abstract】: Online social networks have gained significant popularity recently. The problem of influence maximization in online social networks has been extensively studied. However, in prior works, influence propagation in the physical world, which is also an indispensable factor, is not considered. The Location-Based Social Networks (LBSNs) are a special kind of online social networks in which people can share location-embedded information. In this paper, we make use of mobile crowdsourced data obtained from location-based social network services to study influence maximization in LBSNs. A novel network model and an influence propagation model taking influence propagation in both online social networks and the physical world into consideration are proposed. An event activation position selection problem is formalized and a corresponding solution is provided. The experimental results indicate that the proposed influence propagation model is meaningful and the activation position selection algorithm has high performance.
【Keywords】: Trajectory; Computer science; Electronic mail; Mobile computing; Mobile communication; Facebook
【Paper Link】 【Pages】:1-9
【Authors】: Yuqing Zhu ; Deying Li ; Zhao Zhang
【Abstract】: We wonder that in a competitive environment, how an influence uses the minimum cost to choose seeds such that its influence spread can reach a desired threshold under thwarting from its competitors. At first we take a simple fact into account: the information arriving first has heavy impact, and present Competitive - Independent Cascade (C-IC) model to characterize how different influences competing with others in a social network. We have found that a specific influence's spread is monotone and submodular, and these nice properties make algorithm performance tractable. We then propose Minimum Cost Seed Set problem (MinSeed) to answer our original concern and give a greedy algorithm. We analyze the ratio of greedy algorithm, and give result significantly better than similar ones analyzed by others. Noticing that the computation of real information spread is hard to compute and simple greedy is too time consuming, we design an effective method for estimating information spread in C-IC model, and devise scalable algorithm applying for large social networks. Through simulation on real world datasets, we confirm that, our scalable algorithm outputs seed set with small total cost comparable to that given by simple greedy, with very fast computation.
【Keywords】: Integrated circuit modeling; Social network services; Computational modeling; Algorithm design and analysis; Greedy algorithms; Minimization
【Paper Link】 【Pages】:1-9
【Authors】: Guangmo Tong ; Lei Cui ; Weili Wu ; Cong Liu ; Ding-Zhu Du
【Abstract】: Community detection aims to reveal the community structure in a social network, which is one of the fundamental problems. In this paper we investigate the community detection problem based on the concept of terminal set. A terminal set is a group of users within which any two users belong to different communities. Although the community detection is hard in general, the terminal set can be very helpful in designing effective community detection algorithms. We first present a 2-approximation algorithm running in polynomial time for the original community detection problem. In the other issue, in order to better support real applications we further consider the case when extra restrictions are imposed on feasible partitions. For such customized community detection problems, we provide two randomized algorithms which are able to find the optimal partition with a high probability. Demonstrated by the experiments performed on benchmark networks the proposed algorithms are able to produce high-quality communities.
【Keywords】: Partitioning algorithms; Linear programming; Approximation algorithms; Algorithm design and analysis; Social network services; Silicon; Image edge detection
【Paper Link】 【Pages】:1-9
【Authors】: Jia Liu ; Atilla Eryilmaz ; Ness B. Shroff ; Elizabeth S. Bentley
【Abstract】: The last decade has seen significant advances in optimization-based resource allocation and control approaches for wireless networks. However, the existing work suffer from poor performance in one or more of the metrics of optimality, delay, and convergence speed. To overcome these limitations, in this paper, we introduce a largely overlooked but highly effective heavy-ball optimization method. Based on this heavy-ball technique, we develop a cross-layer optimization framework that offers utility-optimality, fast-convergence, and significant delay reduction. Our contributions are three-fold: i) we propose a heavy-ball joint congestion control and routing/scheduling framework for both single-hop and multi-hop wireless networks; ii) we show that the proposed heavy-ball method offers an elegant three-way trade-off in utility, delay, and convergence, which is achieved under a near index-type simple policy; and more importantly, iii) our work opens the door to an unexplored network control and optimization paradigm that leverages advanced optimization techniques based on “memory/momentum” information.
【Keywords】: Delays; Optimization; Convergence; Wireless networks; Algorithm design and analysis; Queueing analysis; Signal processing algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Shusen Yang ; Yad Tahir ; Po-Yu Chen ; Alan Marshall ; Julie A. McCann
【Abstract】: Energy Harvesting Wireless Sensor Networks (EH-WSNs) have been attracting increasing interest in recent years. Most current EH-WSN approaches focus on sensing and networking algorithm design, and therefore only consider the energy consumed by sensors and wireless transceivers for sensing and data transmissions respectively. In this paper, we incorporate CPU-intensive edge operations that constitute in-network data processing (e.g. data aggregation/fusion/compression) with sensing and networking; to jointly optimize their performance, while ensuring sustainable network operation (i.e. no sensor node runs out of energy). Based on realistic energy and network models, we formulate a stochastic optimization problem, and propose a lightweight on-line algorithm, namely Recycling Wasted Energy (RWE), to solve it. Through rigorous theoretical analysis, we prove that RWE achieves asymptotical optimality, bounded data queue size, and sustainable network operation. We implement RWE on a popular IoT operating system, Contiki OS, and evaluate its performance using both real-world experiments based on the FIT IoT-LAB testbed, and extensive trace-driven simulations using Cooja. The evaluation results verify our theoretical analysis, and demonstrate that RWE can recycle more than 90% wasted energy caused by battery overflow, and achieve around 300% network utility gain in practical EH-WSNs.
【Keywords】: Wireless sensor networks; Data processing; Wireless communication; Sensors; Optimization; Energy harvesting; Internet of things
【Paper Link】 【Pages】:1-9
【Authors】: Chien-Chun Ni ; Zhengyu Su ; Jie Gao ; Xianfeng David Gu
【Abstract】: We consider the problem of capacitated kinetic clustering in which n mobile terminals and k base stations with respective operating capacities are given. The task is to assign the mobile terminals to the base stations such that the total squared distance from each terminal to its assigned base station is minimized and the capacity constraints are satisfied. This paper focuses on the development of distributed and computationally efficient algorithms that adapt to the motion of both terminals and base stations. Suggested by the optimal transportation theory, we exploit the structural property of the optimal solution, which can be represented by a power diagram on the base stations such that the total usage of nodes within each power cell equals the capacity of the corresponding base station. We show by using the kinetic data structure framework the first analytical upper bound on the number of changes in the optimal solution, i.e., its stability. On the algorithm side, using the power diagram formulation we show that the solution can be represented in size proportional to the number of base stations and can be solved by an iterative, local algorithm. In particular, this algorithm can naturally exploit the continuity of motion and has orders of magnitude faster than existing solutions using min-cost matching and linear programming, and thus is able to handle large scale data under mobility.
【Keywords】: Base stations; Transportation; Kinetic theory; Mobile communication; Clustering algorithms; Wireless communication; Resource management
【Paper Link】 【Pages】:1-9
【Authors】: Jin Wang ; Kejie Lu ; Jianping Wang ; Chunming Qiao
【Abstract】: For many emerging mobile broadband services and applications, the source and destination are located in the same local region. Consequently, it is very important to design access networks to facilitate efficient local data exchange. In the past few years, most existing studies focus on either the wired or wireless domains. In this paper, we aim to exploit both the wired and wireless domains. Specifically, we consider a Fiber-Wireless access network in which a passive optical network (PON) connects densely deployed base stations. In such a scenario, we propose a novel access scheme, namely, NCDA, where the main idea is to utilize both network coding and device association. To understand the potentials of NCDA, we first formulate a mixed integer nonlinear programming (MINLP) to minimize the weighted number of packet transmissions (WNT), which is related to both the system capacity and energy consumption. We then theoretically analyze the tight upper bounds of the minimal WNT in the PON, which helps us to approximate the original problem by a mixed integer linear programming (MILP). Next, we develop efficient algorithms based on linear programming relaxation to solve the optimal NCDA problem. To validate our design, we conduct extensive simulation experiments, which demonstrate the impact of important network parameters and the promising potentials of the proposed scheme.
【Keywords】: Optical network units; Wireless communication; Passive optical networks; Network coding; Computer science; Approximation algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Yi Gao ; Wei Dong ; Kai Guo ; Xue Liu ; Yuan Chen ; Xiaojin Liu ; Jiajun Bu ; Chun Chen
【Abstract】: Air quality monitoring has attracted a lot of attention from governments, academia and industry, especially for PM2.5 due to its significant impact on our respiratory systems. In this paper, we present the design, implementation, and evaluation of Mosaic, a low cost urban PM2.5 monitoring system based on mobile sensing. In Mosaic, a small number of air quality monitoring nodes are deployed on city buses to measure air quality. Current low-cost particle sensors based on light-scattering, however, are vulnerable to airflow disturbance on moving vehicles. In order to address this problem, we build our air quality monitoring nodes, Mosaic-Nodes, with a novel constructive airflow-disturbance design based on a carefully tuned airflow structure and a GPS-assisted filtering method. Further, the buses used for system deployment are selected by a novel algorithm which achieves both high coverage and low computation overhead. The collected sensor data is also used to calculate the PM2.5 of locations without direct measurements by an existing inference model. We apply the Mosaic system in a testing urban area which includes more than 70 point-of-interests. Results show that the Mosaic system can accurately obtain the urban air quality with high coverage and low cost.
【Keywords】: Air quality; Monitoring; Atmospheric measurements; Pollution measurement; Particle measurements; Temperature sensors
【Paper Link】 【Pages】:1-9
【Authors】: Yidan Hu ; Guojun Dai ; Jin Fan ; Yifan Wu ; Hua Zhang
【Abstract】: This paper presents BlueAer, the first three-dimensional (3D) spatial-temporal fine particulate matter (PM2.5) monitoring system, which is designed to understand urban PM2.5 concentration distribution in a fine-grained level. For cost-efficient data collection, vast amount of 3D samples are collected by limited mobile carriers with built-in low-cost sensors. A 3D probabilistic concentration estimated method (3D-PCEM) is proposed to infer PM2.5 concentration for undetected area, so that the accuracy of BlueAer is ensured. A prototype system of BlueAer has been implemented and worked throughout a year in a 64km2 testing area with a population of 400,000 in Hangzhou, China. Experimental data has verified that BlueAer can achieve good performance in terms of stability as well as a fine grained 3D distribution of PM2.5 concentration. The inference accuracy of 3D-PCEM is enhanced by 15.4% and 41.0%, comparing to Gaussian Process (GP) and Artificial Network (ANN) respectively. BlueAer can easily be extended for a larger scale and applied city-wise. Besides, our findings can help ordinary citizens better understand their immediate air quality and serve as a framework towards detailed national-wise real-time pollution management.
【Keywords】: Three-dimensional displays; Monitoring; Integrated circuits; Sensor systems; Public transportation; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Rong Du ; Carlo Fischione ; Ming Xiao
【Abstract】: Contamination in drinkable water distribution networks can be potentially monitored by new and agile mobile sensor networks. These sensor networks are composed of static sensor nodes, which are pre-installed, of mobile sensor nodes, which are released into the water network for a more punctual monitoring, and of sink nodes, which are used to collect data from mobile sensor nodes. Thus, the activation of the sink nodes as well as the release locations of the mobile nodes must be carefully decided to ensure timely and accurate event detections. Unfortunately, no approach can be found in the literature to optimally determine the release locations of the mobile sensor nodes and the activation of the sink nodes. In this paper, a novel optimization approach to solve such a problem is posed. The problem is particularly challenging due to the potential large size of the networks, the undetermined movement of the mobile sensor nodes, the integer decision variables associated to the release locations of these mobile sensor nodes, and the binary decision variables associated to the activation of the sink nodes. To account for the mobile node mobility across the water distribution network, a stochastic mobility model is considered. It is shown that the objective function of the optimization problem exhibits submodular properties, which allow establishing a mobile nodes release algorithm. The benefits and efficiency of the proposed algorithm are illustrated by analysis and numerical evaluations. It is concluded that the proposed optimization based approach allows efficient monitoring of water distribution networks by mobile sensor nodes.
【Keywords】: Sensors; Mobile communication; Monitoring; Water pollution; Mobile computing; Contamination; Pipelines
【Paper Link】 【Pages】:1-9
【Authors】: Huihui Chen ; Bin Guo ; Zhiwen Yu ; Qi Han
【Abstract】: Mobile social media enables people to record ongoing physical events they witness and share them instantaneously online. However, since these event pictures are often individually provided, they are typically fragmented and possess high redundancy. Though there have been studies about visual event summarization, they pay little attention to collaborative sensing, subevent detection, and event summary. In this paper, we present several building blocks for a cooperative visual sensing and sharing system. We create a virtual opportunistic community associated with an event, where members collaborate to cover different aspects of the event. More specifically, a crowd-powered approach is first used to localize the event. We then propose three subevent segmentation methods based on crowd-event interaction patterns. Based on the segmentation results, we summarize the event at two levels: multi-facet subevent summary and crowd-behavior-based highlights. Experiments over 21 online datasets and two real world datasets demonstrate the effectiveness of our approaches.
【Keywords】: Sensors; Visualization; Videos; Real-time systems; Twitter; Mobile communication; Context
【Paper Link】 【Pages】:1-9
【Authors】: Wei-Liang Shen ; Kate Ching-Ju Lin ; Ming-Syan Chen ; Kun Tan
【Abstract】: Recent advances have demonstrated the potential of network MIMO (netMIMO), which combines a practical number of distributed antennas as a virtual netMIMO AP (nAP) to improve spatial multiplexing of an WLAN. Existing solutions, however, either simply cluster nearby antennas as static nAPs, or dynamically cluster antennas on a per-packet basis so as to maximize the sum rate of the scheduled clients. To strike the balance between the above two extremes, in this paper, we present the design, implementation and evaluation of FlexNEMO, a practical two-phase netMIMO clustering system. Unlike previous per-packet clustering approaches, FlexNEMO only clusters antennas when client distribution and traffic pattern change, as a result being more practical to be implemented. A medium access control protocol is then designed to allow the clients at the center of nAPs to have a higher probability to gain access opportunities, but still ensure long-term fairness among clients. By combining on-demand clustering and priority-based access control, FlexNEMO not only improves antenna utilization, but also optimizes the channel condition for every individual client. We evaluated our design via both testbed experiments on USRPs and trace-driven emulations. The results demonstrate that FlexNEMO can deliver 94.7% and 93.7% throughput gains over static antenna clustering in a 4-antenna testbed and 16-antenna emulation, respectively.
【Keywords】: MIMO; Servers; Interference; Uplink; Antenna arrays; Throughput
【Paper Link】 【Pages】:1-9
【Authors】: Teng Wei ; Xinyu Zhang
【Abstract】: Increasing popularity of mobile devices and upload-intensive applications is rapidly driving the uplink traffic demand in wireless LANs. Network MIMO (netMIMO) can potentially meet the demand by enabling concurrent uplink transmissions to an AP cluster (APC) comprised of multiple access points. NetMIMO's PHY-layer communication algorithms have been well explored, but the MAC-level signaling procedure remains an open issue: prior to uplink transmission, a group of clients must gain channel access, and ensure synchronization and channel orthogonality with each other. But such signaling is fundamentally challenging, because netMIMO clients tend to be widely distributed and may not even sense each other. In this paper, we introduce the first signaling protocol, called NURA, to meet the challenge. NURA clients employ a novel medium-access-signaling mechanism to realize group-based random access and synchronization, without disturbing ongoing uplink transmissions. The APC leverages a lightweight user-admission mechanism to group users with orthogonal channels (and hence high uplink capacity), without requiring costly channel-state feedback from all users. We have implemented NURA on a software-radio based netMIMO platform. Our experiments show that NURA is feasible, efficient, and can readily serve as the a priori signaling mechanism for distributed asynchronous netMIMO clients.
【Keywords】: Uplink; OFDM; MIMO; Synchronization; Protocols; Signal to noise ratio; Wireless LAN
【Paper Link】 【Pages】:1-9
【Authors】: Hao Yu ; Michael J. Neely
【Abstract】: This paper considers dynamic power allocation in MIMO fading systems with unknown channel state distributions. First, the ideal case of perfect instantaneous channel state information at the transmitter (CSIT) is treated. Using the drift-plus-penalty method, a dynamic power allocation policy is developed and shown to approach optimality, regardless of the channel state distribution and without requiring knowledge of this distribution. Next, the case of delayed and quantized channel state information is considered. Optimal utility is fundamentally different in this case, and a different online algorithm is developed that is based on convex projections. The proposed algorithm for this delayed-CSIT case is shown to have an O (δ) optimality gap, where δ is the quantization error of CSIT.
【Keywords】: Resource management; Heuristic algorithms; MIMO; Fading channels; Transmitters; Algorithm design and analysis; Symmetric matrices
【Paper Link】 【Pages】:1-9
【Authors】: Mingjie Feng ; Shiwen Mao ; Tao Jiang
【Abstract】: In this paper, we investigate the problem of optimal base station (BS) ON-OFF switching and user association in a heterogeneous network (HetNet) with massive MIMO, with the objective to maximize the system energy efficiency (EE). The joint BS ON-OFF switching and user association problem is formulated as an integer programming problem. We first develop a centralized scheme, in which we relax the integer constraints and employ a series of Lagrangian dual methods that transform the original problem into a standard linear programming (LP) problem. Due to the special structure of the LP, we prove that the optimal solution to the relaxed LP is also feasible and optimal to the original problem. We then propose a distributed scheme by formulating a repeated bidding game for users and BS's, and prove that the game converges to a Nash Equilibrium (NE). Simulation studies demonstrate that the proposed schemes can achieve considerable gains in EE over several benchmark schemes in all the scenarios considered.
【Keywords】: MIMO; Macrocell networks; Switches; Power demand; Linear programming; Wireless communication; Games
【Paper Link】 【Pages】:1-9
【Authors】: Kanthi Nagaraj ; Ajay Mahimkar ; Zihui Ge ; Aman Shaikh ; Jia Wang ; Kevin Mohr ; Mark Stockert
【Abstract】: Load on cellular towers is one of the key metrics that cellular service providers monitor as part of their operational and management tasks. Increased load on the towers can lead to congestion, which in turn can severely degrade quality of service perceived by users. Hence, it is of great interest to cellular service providers to minimize the maximum load at cell towers, and thereby minimize chances of congestion in the event of a sudden increase in load due to user demand changes. This goal can be achieved by proactive load balancing among neighboring cell towers, i.e., proactively identify opportunities to balance the load through re-binding of users from heavily loaded cell towers to lightly loaded neighboring towers. In this paper, we propose a new tool Libra to effectively assess the impact of load balancing related parameter changes. Libra provides an objective measure of the degree of load imbalance across multiple network locations and identifies if the measure improves or degrades after parameter changes. Our evaluation of Libra using real-world data collected from a large cellular provider demonstrates its effectiveness in accurately capturing the degree of imbalance at multiple cell towers.
【Keywords】: Poles and towers; Load management; Degradation; Azimuth; Antennas; Interference; Measurement
【Paper Link】 【Pages】:1-9
【Authors】: Michael Lin ; Novella Bartolini ; Thomas F. La Porta
【Abstract】: Densely-deployed femtocell networks are used to enhance wireless coverage in public spaces like office buildings, subways, and academic buildings. These networks can increase throughput for users, but edge users can suffer from co-channel interference, leading to service outages. This paper introduces a distributed algorithm for network configuration, called Radius Reduction and Scheduling (RRS), to improve the performance and fairness of the network. RRS determines cell sizes using a Voronoi-Laguerre framework, then schedules users using a scheduling algorithm that includes vacancy requests to increase fairness in dense femtocell networks. We prove that our algorithm always terminate in a finite time, producing a configuration that guarantees user or area coverage. Simulation results show a decrease in outage probability of up to 50%, as well as an increase in Jain's fairness index of almost 200%.
【Keywords】: Throughput; Interference; Femtocell networks; Scheduling; Geometry; Signal to noise ratio; Wireless networks
【Paper Link】 【Pages】:1-9
【Authors】: Zhenzhi Qian ; Bo Ji ; Kannan Srinivasan ; Ness B. Shroff
【Abstract】: There have been recent attempts to develop scheduling schemes for downlink transmission in a single cell of a multi-channel (e.g., OFDM-based) cellular network. These works have been quite promising in that they have developed low-complexity index scheduling policies that are delay-optimal (in a large deviation rate-function sense). However, these policies require that the channel is ON or OFF in each time-slot with a fixed probability (i.e., there is no memory in the system), while the reality is that due to channel fading and doppler shift, channels are often time-correlated in these cellular systems. Thus, an important open question is whether one can find simple index scheduling policies that are delay-optimal even when the channels are time-correlated. In this paper, we attempt to answer this question for time-correlated ON/OFF channels. In particular, we show that the class of oldest packets first (OPF) policies that give a higher priority to packets with a large delay is delay rate-function optimal under two conditions: 1) The channel is non-negatively correlated, and 2) The distribution of the OFF period is geometric. We use simulations to further elucidate the theoretical results.
【Keywords】: Delays; Servers; OFDM; Throughput; Downlink; Upper bound
【Paper Link】 【Pages】:1-9
【Authors】: Faraz Ahmed ; Jeffrey Erman ; Zihui Ge ; Alex X. Liu ; Jia Wang ; He Yan
【Abstract】: Providing high end-to-end (E2E) performance is critical for cellular service providers to best serve their customers. Detecting and localizing E2E performance degradation is crucial for cellular service providers, content providers, device manufactures, and application developers to jointly troubleshoot root causes. To the best of our knowledge, detection and localization of E2E performance degradation at cellular service providers has not been previously studied. In this paper, we propose a holistic approach to detecting and localizing E2E performance degradation at cellular service providers across the four dimensions of user locations, content providers, device types, and application types. First, we use training data to build models that can capture the normal performance of every E2E-instance, which means flows corresponding to a specific location, content provider, device type, and application type. Second, we use our models to detect performance degradation for each E2E-instance on an hourly basis. Third, after each E2E-instance has been labeled as non-degrading or degrading, we use association rule mining techniques to localize the source of performance degradation. Our system detected performance degradation instances over a period of one week. In 80% of the detected degraded instances, content providers, device types, and application types were the only factors of performance degradation.
【Keywords】: Performance evaluation; Degradation; Servers; Electronic mail; Data models; Internet; Streaming media
【Paper Link】 【Pages】:1-9
【Authors】: Qingkai Liang ; Eytan Modiano
【Abstract】: Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks against unpredictable interruptions. We first show that the traditional definition of survivability is not effective in time-varying networks, and propose a new survivability framework. To evaluate the survivability of time-varying networks under the new framework, we propose two metrics that are analogous to MaxFlow and MinCut in static networks. We show that some fundamental survivability-related results such as Menger's Theorem only conditionally hold in time-varying networks. Then we analyze the complexity of computing the proposed metrics and develop approximation algorithms. Finally, we conduct trace-driven simulations to demonstrate the application of our survivability framework in the robust design of a real-world bus communication network.
【Keywords】: Network topology; Topology; Computational modeling; Delays; Robustness; Hardware
【Paper Link】 【Pages】:1-9
【Authors】: Jaeseong Jeong ; Mathieu Leconte ; Alexandre Proutière
【Abstract】: Predicting the future location of users in wireless networks has numerous applications, and can help service providers to improve the quality of service perceived by their clients. The location predictors proposed so far estimate the next location of a specific user by inspecting the past individual trajectories of this user. As a consequence, when the training data collected for a given user is limited, the resulting prediction is inaccurate. In this paper, we develop cluster-aided predictors that exploit past trajectories collected from all users to predict the next location of a given user. These predictors rely on clustering techniques and extract from the training data similarities among the mobility patterns of the various users to improve the prediction accuracy. Specifically, we present CAMP (Cluster-Aided Mobility Predictor), a cluster-aided predictor whose design is based on recent non-parametric Bayesian statistical tools. CAMP is robust and adaptive in the sense that it exploits similarities in users' mobility only if such similarities are really present in the training data. We analytically prove the consistency of the predictions provided by CAMP, and investigate its performance using two large-scale datasets. CAMP significantly outperforms existing predictors, and in particular those that only exploit individual past trajectories.
【Keywords】: Trajectory; Predictive models; Markov processes; Bayes methods; Hidden Markov models; Training data; Kernel
【Paper Link】 【Pages】:1-9
【Authors】: Mei Wang ; Zhehui Zhang ; Xiaohua Tian ; Xinbing Wang
【Abstract】: Indoor localization based on RSS fingerprinting approach has been attracting many research efforts in the past decades. Recent study presents a fundamental limit of the approach: given requirement of estimation accuracy, reliability of the user's localization result can be derived. As highly accurate indoor localization is essential to enable many location based services, a natural question to ask is: can we further improve the accuracy of the localization scheme fundamentally? In this paper, we theoretically show that the temporal correlation of the RSS can improve accuracy of the RSS fingerprinting based indoor localization. In particular, we construct a theoretical framework to evaluate how the temporal correlation of the RSS can influence the reliability of location estimation, which is based on a newly proposed radio propagation model considering the time-varying property of signals from a given Wi-Fi AP. Such a theoretical framework is then applied to analyze localization in the one dimensional physical space, which reveals the fundamental reason why performance improvement of localization can be brought by temporal correlation of the RSS. We further extend our analysis to high-dimensional scenarios. Experimental results corroborate our theoretical analysis.
【Keywords】: Correlation; Estimation; Radio propagation; Training; Reliability; Analytical models; Mathematical model
【Paper Link】 【Pages】:1-9
【Authors】: Brenton D. Walker
【Abstract】: We consider an opportunistic wireless network where data repositories provide mobile users access to locally-cached data objects. In this setting using network/erasure coding to disseminate large data objects can greatly improve the performance and robustness of the network, but it becomes more difficult to plan, coordinate, and analyze the distribution of information. We introduce a simplicial data structure, the coverage complex, that captures enough of both the structure of the code and the geometry of the network that it can be used to draw conclusions about network coded data coverage. We give a distributed algorithm for computing the coverage complex based on local information, prove results on using it for coverage testing, and study more complicated cases where coverage testing can fail.
【Keywords】: Testing; Encoding; Mobile communication; Face; Wireless networks; Mobile computing
【Paper Link】 【Pages】:1-9
【Authors】: Zongqing Lu ; Xiao Sun ; Thomas F. La Porta
【Abstract】: Opportunistic mobile networks consisting of intermittently connected mobile devices have been exploited for various applications, such as computational offloading and mitigating cellular traffic load. Different from existing work, in this paper, we focus on cooperatively offloading data among mobile devices to maximally improve the probability of data delivery from a mobile device to an intermittently connected remote server or data center within a given time constraint, which is referred to as the cooperative offloading problem. Unfortunately, cooperative offloading is NP-hard. To this end, a heuristic algorithm is designed based on the proposed probabilistic framework, which provides the estimation of the probability of successful data delivery over the opportunistic path, considering both data size and contact duration. Due to the lack of global information, a distributed algorithm is further proposed. The performance of the proposed approaches is evaluated based on both synthetic networks and real traces, and simulation results show that cooperative offloading can significantly improve the data delivery probability and the performance of both heuristic algorithm and distributed algorithm outperforms other approaches.
【Keywords】: Mobile communication; Mobile computing; Mobile handsets; Heuristic algorithms; Probabilistic logic; Time factors; Algorithm design and analysis
【Paper Link】 【Pages】:1-9
【Abstract】: The increasing traffic demand has become a serious concern for cellular networks. To solve the traffic explosion problem in a vehicular network environment, there have been many efforts to offload the traffic from cellular links to Roadside Units (RSUs). Compared with the cost of downloading from cellular link, downloading through RSUs is considered practically free. In most cases, we have to wait for one or several RSUs to download the entire data, which causing huge delays. However, people can always download data from the cellular network. In reality, people are sensitive to the downloading delay but would like to pay little money for downloading the data. As the result, there exists a delay-cost trade-off. In this paper, we unify the downloading cost and downloading delay as the user's satisfaction. The objective of this paper is to maximize the user's satisfaction. A user will be unsatisfied if they are paying too much for data, or if they wait for a long time. We analyze the optimal solution under the condition that the encountering time between vehicles and RSUs follows the exponential and Gaussian distributions. Generally, we propose an adaptive algorithm. A downloading strategy is made based on the historical encountering situation between the vehicle and multiple RSUs. After a period of time, if the real situation is different with the initial prediction, the data downloading strategy will be correspondingly adjusted. Extensive real-trace driven experiment results show that our algorithm achieves a good performance.
【Keywords】: Vehicles; Estimation; Delays; IEEE 802.11 Standard; Internet; Poles and towers; Adaptive algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Yuan Zhang ; Siyuan Tang ; Tingting Chen ; Sheng Zhong
【Abstract】: Offloading part of cellular traffic through existing alternative wireless networks, such as femtocells and WiFi networks, is one promising solution to the severe traffic overload faced by cellular network providers (CSPs) nowadays. Most existing cellular offloading auction mechanisms assume the CSP has the knowledge of incoming overloaded traffic demand, and satisfy the demand by offloading. However, in practice, with the explosive growth of mobile device communications, the overloaded traffic demand at CSPs is very likely to pass over the total capability that third-party resource owners can provide. Then it is critical to enable CSPs to optimize the traffic handling capacity gain through offloading with budget constraints. In this paper, we propose two efficient Competitive Auction MEchanisms for mObile offloading, CAMEO-min and CAMEO-ws. Both mechanisms are proven to be non-budget-deficit, individually rational and incentive-compatible, and have guaranteed lower bounds on the ratio of the CSP's gain achieved in them to the maximum gain that the CSP could achieve in any omniscient auction (the auction with an omniscient auctioneer). Our extensive evaluations show that CAMEOs achieve very good performance in terms of the maximization of the CSP's gain especially when the global bidder dominance or the region dominance is big.
【Keywords】: Femtocells; Macrocell networks; Optimization; IEEE 802.11 Standard; Mobile handsets; Wireless networks
【Paper Link】 【Pages】:1-9
【Authors】: Songtao Guo ; Bin Xiao ; Yuanyuan Yang ; Yang Yang
【Abstract】: Mobile cloud computing (MCC) as an emerging and prospective computing paradigm, can significantly enhance computation capability and save energy of smart mobile devices (SMDs) by offloading computation-intensive tasks from resource-constrained SMDs onto the resource-rich cloud. However, how to achieve energy-efficient computation offloading under the hard constraint for application completion time remains a challenge issue. To address such a challenge, in this paper, we provide an energy-efficient dynamic offloading and resource scheduling (eDors) policy to reduce energy consumption and shorten application completion time. We first formulate the eDors problem into the energy-efficiency cost (EEC) minimization problem while satisfying the task-dependency requirements and the completion time deadline constraint. To solve the optimization problem, we then propose a distributed eDors algorithm consisting of three subalgorithms of computation offloading selection, clock frequency control and transmission power allocation. More importantly, we find that the computation offloading selection depends on not only the computing workload of a task, but also the maximum completion time of its immediate predecessors and the clock frequency and transmission power of the mobile device. Finally, our experimental results in a real testbed demonstrate that the eDors algorithm can effectively reduce the EEC by optimally adjusting the CPU clock frequency of SMDs based on the dynamic voltage and frequency scaling (DVFS) technique in local computing, and adapting the transmission power for the wireless channel conditions in cloud computing.
【Keywords】: Cloud computing; Mobile handsets; Energy consumption; Clocks; Wireless communication; Mobile communication; Computational modeling
【Paper Link】 【Pages】:1-9
【Authors】: Curtis R. Taylor ; Douglas C. MacFarland ; Doran R. Smestad ; Craig A. Shue
【Abstract】: Network operators can better understand their networks when armed with a detailed understanding of the network traffic and host activities. Software-defined networking (SDN) techniques have the potential to improve enterprise security, but the current techniques have well-known data plane scalability concerns and limited visibility into the host's operating context. In this work, we provide both detailed host-based context and fine-grained control of network flows by shifting the SDN agent functionality from the network infrastructure into the end-hosts. We allow network operators to write detailed network policy that can discriminate based on user and program information associated with network flows. In doing so, we find our approach scales far beyond the capabilities of OpenFlow switching hardware, allowing each host to create over 25 new flows per second with no practical bound on the number of established flows in the network.
【Keywords】: Context; Scalability; Security; Hardware; Organizations; Kernel
【Paper Link】 【Pages】:1-9
【Authors】: Jingyu Hua ; Xin Ge ; Sheng Zhong
【Abstract】: Due to the asynchronous and distributed nature of the data plane, consistent configuration updating across multiple switches is a challenging issue in Software-Defined Networking (SDN). The existing version-stamping-based mechanism (VSM) could guarantee per-packet consistency, but this mechanism is designed for non-adversarial settings and can be compromised easily by a malicious attacker. In this paper, we propose an efficient flow-ordered update mechanism that aims to provide per-packet consistency in adversarial settings. Our proposal does not need to stamp data packets with the configuration version, and is robust against both the packet-tampering and packet-dropping attacks. It outperforms a naive mechanism that simply patches VSM using digital signatures in three aspects: First, the switches in this mechanism only need to sign and verify a single control packet, which significantly improves the packet processing time. Second, it avoids keeping both old and new policies on switches during the update, and thus achieves better space efficiency. Third, it reduces the time delay for new policies to come into force. We evaluate our mechanism on a self-constructed SDN testbed and the results demonstrate high efficiency.
【Keywords】: Control systems; Digital signatures; Process control; Software; Proposals; Throughput; Payloads
【Paper Link】 【Pages】:1-9
【Abstract】: Software Defined Networking (SDN) has recently emerged as a new network management platform. The centralized control architecture presents many new opportunities. Among the network management tasks, measurement is one of the most important and challenging one. Researchers have proposed many solutions to better utilize SDN for network measurement. Among them, how to detect Distributed Denial-of-Services (DDoS) quickly and precisely is a very challenging problem. In this paper, we propose methods to detect DDoS attacks leveraging on SDN's flow monitoring capability. Our methods utilize measurement resources available in the whole SDN network to adaptively balance the coverage and granularity of attack detection. Through simulations we demonstrate that our methods can quickly locate potential DDoS victims and attackers by using a constrained number of flow monitoring rules.
【Keywords】: IP networks; Computer crime; Monitoring; Switches; Current measurement; Servers; Feature extraction
【Paper Link】 【Pages】:1-9
【Authors】: Alon Atary ; Anat Bremler-Barr
【Abstract】: Monitoring Round-Trip Time provides important insights for network troubleshooting and traffic engineering. The common monitoring technique is to actively send probe packets from selected vantage points (hosts or middleboxes). In traditional networks, the control over the network routing is limited, making it impossible to monitor every selected path. The emerging concept of Software Defined Networking simplifies network control. However, OpenFlow, the common SDN protocol, does not support RTT monitoring as part of its specification. In this paper, we leverage the ability of OpenFlow to control the routing, and present GRAMI, the Granular RTT Monitoring Infrastructure. GRAMI uses active probing from selected vantage points for efficient RTT monitoring of all the links and any round-trip path between any two switches in the network. GRAMI was designed to be resource efficient. It requires only four flow entries installed on every switch in order to enable RTT monitoring of all the links. For every round-trip path selected by the user, it requires a maximum of two additional flow entries installed on every switch along the measured path. Moreover, GRAMI uses a minimal number of probe packets, and does not require the involvement of the controller during online RTT monitoring.
【Keywords】: Monitoring; Probes; Overlay networks; Routing; Delays; Protocols
【Paper Link】 【Pages】:1-9
【Authors】: Julien Mineraud ; Liang Wang ; Sasitharan Balasubramaniam ; Jussi Kangasharju
【Abstract】: The ICT industry has come under criticism as being one of the major energy consumers to exacerbate high global carbon emissions. Meanwhile, using renewable energy to power ICT infrastructure is becoming an attractive solution and is gaining its momentum due to the recent breakthroughs of converting solar and wind energies as power sources at competitive costs. Although significant amounts of fossil fuel based-energy can be saved by allowing network devices (e.g., routers and line-cards) to be set to sleep, this optimization approach comes at a price of degrading routing performance, i.e., the quality of service. This paper addresses the problem of minimizing fossil fuel consumption in large Internet Service Provider (ISP) networks, by utilizing a novel gradient-based routing protocol, which favors forwarding packets along routers powered by the highest quantity of renewable energies. Besides favoring renewable energy, the proposed routing protocol can support putting routers to sleep in order to optimize energy consumption while ensuring a minimum degradation in routing performance. Through our evaluation utilizing real meteorological data, our proposed solution has demonstrated a massive reduction of fossil fuel usage by the network (> 70%) while maintaining the routing performance to a similar level when no energy optimization is applied.
【Keywords】: Routing protocols; Renewable energy sources; Energy consumption; Green products; Routing; Fossil fuels; Optimization
【Paper Link】 【Pages】:1-9
【Authors】: Yuan Yang ; Dan Wang ; Dawei Pan ; Mingwei Xu
【Abstract】: We present a study on minimizing non-renewable energy for the Internet. The classification of renewable and non-renewable energy brings in several challenges. First, it is necessary to understand how the routing system can distinguish the two types of energy in the power supply. Second, the routing problem changes due to renewable energy; and so do the algorithm designs and analysis. We first clarify the model of how routers can distinguish renewable and non-renewable energy supporting their power supply. This cannot be determined by the routing system alone, and involves modeling the energy generation and supply of the grid. We then present the router power consumption model, which has a fixed startup power and a dynamic traffic-dependent power. We formulate a minimum non-renewable energy routing problem, and two special cases representing either the startup power dominates or the traffic-dependent power dominates. We analyze the complexity of these problems, develop optimal and sub-optimal algorithms, and jointly consider QoS requirements such as path stretch. We evaluate our algorithms using real data from both National and European centers. As compared to the algorithms minimizing the total energy, our algorithms can reduce the non-renewable energy consumption for more than 20% under realistic assumptions.
【Keywords】: Routing; Renewable energy sources; Internet; Power demand; Power grids; Energy consumption
【Paper Link】 【Pages】:1-9
【Authors】: Tuo Shi ; Siyao Cheng ; Zhipeng Cai ; Jianzhong Li
【Abstract】: A Wireless Sensor Network consists of a number of sensors. The energy of each sensor is limited which limits network lifetime. There are many existing energy efficiency algorithms to prolong network lifetime. Basically, there are two kinds of methods. One is energy-efficiency management, such as duty-cycling using virtual-backbones. The other one is energy provision, such as energy harvest from the environment. In this paper, we introduce a new problem, CDSEH, to combine these two methods together. We also propose a new standard to define the network lifetime of a WSN. We prove that the CDSEH problem is NP-Complete and propose two approximate algorithms accordingly. Extensive simulation results are shown to validate the performance of our algorithms.
【Keywords】: Wireless sensor networks; Approximation algorithms; Energy harvesting; Standards; Energy consumption; Distributed algorithms; Schedules
【Paper Link】 【Pages】:1-9
【Authors】: Robert Margolies ; Guy Grebla ; Tingjun Chen ; Dan Rubenstein ; Gil Zussman
【Abstract】: Object tracking applications are gaining popularity and will soon utilize Energy Harvesting (EH) low-power nodes that will consume power mostly for Neighbor Discovery (ND) (i.e., identifying nodes within communication range). Although ND protocols were developed for sensor networks, the challenges posed by emerging EH low-power transceivers were not addressed. Therefore, we design an ND protocol tailored for the characteristics of a representative EH prototype: the TI eZ430-RF2500-SEH. We present a generalized model of ND accounting for unique prototype characteristics (i.e., energy costs for transmission/reception, and transceiver state switching times/costs). Then, we present the Power Aware Neighbor Discovery Asynchronously (Panda) protocol in which nodes transition between the sleep, receive, and transmit states. We analyze Panda and select its parameters to maximize the ND rate subject to a homogeneous power budget. We also present Panda-D, designed for non-homogeneous EH nodes. We perform extensive testbed evaluations using the prototypes and study various design tradeoffs. We demonstrate a small difference (less then 2%) between experimental and analytical results, thereby confirming the modeling assumptions. Moreover, we show that Panda improves the ND rate by up to 3x compared to related protocols. Finally, we show that Panda-D operates well under non-homogeneous power harvesting.
【Keywords】: Protocols; Peer-to-peer computing; Prototypes; Energy harvesting; Transceivers; Wireless communication; Capacitors
【Paper Link】 【Pages】:1-9
【Authors】: Quyen Dinh Vu ; Rui Tan ; David K. Y. Yau
【Abstract】: Much recent work has applied existing fault detectors against attacks in cyber-physical control systems. The results demonstrate effectiveness in detecting simplistic attacks that cause fault-like disruptions. However, they do not address motivated and knowledgeable attackers who craft attacks using knowledge of the system including its method of detecting attacks. In this paper, we analyze the conditions for an attacker to bypass a dissipativity-theoretic fault detector adopted in the prior work. We show that the attacker can use a quadratic programming solver to efficiently compute false data injection attacks to bypass the detector. We show further that, by applying an OR gate to fuse binary detection results from a number of the detectors, with carefully chosen parameters, we can achieve an integrated detector bank that cannot be bypassed by an attacker, if the attacker can tamper with either the sensor or control data of the system. For an n-dimensional linear time-invariant system, the number of needed fault detectors is O(n!). This number can be dramatically reduced to O(n) under a realistic assumption that the system has converged before the attack starts. Simulations for voltage control based on an IEEE 39-bus power system model validate our analysis.
【Keywords】: Fault detection; Detectors; Voltage control; Control systems; Analytical models; Power grids; Linear systems
【Paper Link】 【Pages】:1-9
【Authors】: Christos Liaskos ; Vasileios Kotronis ; Xenofontas A. Dimitropoulos
【Abstract】: Distributed link-flooding attacks constitute a new class of attacks with the potential to segment large areas of the Internet. Their distributed nature makes detection and mitigation very hard. This work proposes a novel framework for the analytical modeling and optimal mitigation of such attacks. The detection is modeled as a problem of relational algebra, representing the association of potential attackers (bots) to potential targets. The analysis seeks to optimally dissolve all but the malevolent associations. The framework is implemented at the level of online Traffic Engineering (TE), which is naturally triggered on link-flooding events. The key idea is to continuously re-route traffic in a manner that makes persistent participation to link-flooding events highly improbable for any benign source. Thus, bots are forced to adopt a suspicious behavior to remain effective, revealing their presence. The load-balancing objective of TE is not affected at all. Extensive simulations on various topologies validate our analytical findings.
【Keywords】: Routing; Internet; Servers; Nickel; Analytical models; Algebra; IP networks
【Paper Link】 【Pages】:1-9
【Authors】: Cheng Jin ; Abhinav Srivastava ; Zhi-Li Zhang
【Abstract】: To ensure security, cloud service providers employ security groups as a key tool for cloud tenants to protect their virtual machines (VMs) from attacks. However, security groups can be complex and often hard to configure, which may result in security vulnerabilities that impact the entire cloud platform. The goal of this paper is to investigate and understand how cloud tenants configure security groups and to assist them in designing better security groups. We first conduct a measurement-based analysis of security group configuration and usage by tenants in an IaaS cloud. We then propose and develop a tool called Socrates, which enables tenants to visualize and hence understand the static and dynamic access relations among VMs. Socrates also helps diagnose potential misconfigurations and provides suggestions to refine security group configurations based on observed traffic traversing tenants' VMs. Applying Socrates to all tenants hosted on the IaaS cloud, we analyze the common usage (“good” as well as “bad” practices) of cloud security groups and report the key lessons learned in our study. To the best of our knowledge, our work is the first to analyze cloud security group usage based on real-world datasets, and to develop a system to help cloud tenants understand, diagnose and better refine their security group configurations.
【Keywords】: Security; Cloud computing; IP networks; Protocols; Switches; Virtual machining; Visualization
【Paper Link】 【Pages】:1-9
【Authors】: Wenxin Chen ; Mengjun Liu ; Rui Zhang ; Yanchao Zhang ; Shubo Liu
【Abstract】: Recent years have witnessed a growing number of location-based service providers (LBSPs) outsourcing their points of interest (POI) datasets to third-party cloud service providers (CSPs), which in turn answer various data queries from mobile users on their behalf. A main challenge in such systems is that the CSPs cannot be fully trusted, which may return fake query results for various bad motives, e.g., in favor of POIs willing to pay. As an important type of queries, location-based skyline queries (LBSQs) ask for the POIs that are not spatially dominated by any other POI with respect to some query position. In this paper, we propose three novel schemes that enable efficient verification of any LBSQ result returned by an untrusted CSP by embedding and exploring a novel neighboring relationship among POIs. The efficacy and efficiency of our schemes are thoroughly analyzed and evaluated.
【Keywords】: Roads; Query processing; Cloud computing; Outsourcing; Cryptography; Mobile radio mobility management
【Paper Link】 【Pages】:1-9
【Authors】: Wan Du ; Jansen Christian Liando ; Mo Li
【Abstract】: Screen-camera links for Visible Light Communication (VLC) are diverse, as the link quality varies according to many factors, such as ambient light and camera's performance. This paper presents SoftLight, a channel coding approach that considers the unique channel characteristics of VLC links and automatically adapts the transmission data rate to the link qualities of various scenarios. SoftLight incorporates two new ideas: (1) an expanded color modulation interface that provides soft hint about its confidence in each demodulated bit and establishes a bit-level VLC erasure channel, and (2) a rateless coding scheme that achieves bit-level rateless transmissions with low computation complexity and tolerates the false positive of bits provided by the soft hint enabled erasure channel. SoftLight is orthogonal to the visual coding schemes and can be applied atop any barcode layouts. We implement SoftLight on Android smartphones and evaluate its performance under a variety of environments. The experiment results show that SoftLight can correctly transmit a 22-KByte photo between two smartphones within 0.6 second and improves the average goodput of the state-of-the-art screen-camera VLC solution by 2.2.
【Keywords】: Image color analysis; Encoding; Smart phones; Standards; Cameras; Bit error rate; Modulation
【Paper Link】 【Pages】:1-9
【Authors】: Jie Hao ; Yanbing Yang ; Jun Luo
【Abstract】: Although Visible Light Communication (VLC) is gaining increasing attentions in research, developing a practical VLC system to harness its immediate benefits using Commercial Off-The-Shelf (COTS) devices is still an open issue. To this end, we develop and deploy CeilingCast as a location-bound wireless broadcast system using COTS LEDs as transmitters and smartphone cameras as receivers. CeilingCast innovates in its effective coding and efficient decoding schemes, so that it can be fully hosted in a smartphone and is feasible for all possible indoor environments. Moreover, we analyze the impact of various parameters on the performance of CeilingCast, in order to derive a model for such VLC systems enabled by COTS devices and hence provide general guidance for future VLC deployments in larger scales. Finally, we conduct extensive field experiments to validate the effectiveness of our LED-camera VLC model, as well as to demonstrate the promising performance of CeilingCast under various parameters.
【Keywords】: Light emitting diodes; Receivers; Cameras; Encoding; Decoding; Transmitters; Reliability
【Paper Link】 【Pages】:1-9
【Authors】: Viet Nguyen ; Yaqin Tang ; Ashwin Ashok ; Marco Gruteser ; Kristin J. Dana ; Wenjun Hu ; Eric Wengrowski ; Narayan B. Mandayam
【Abstract】: Embedded screen-camera communication techniques encode information in screen imagery that can be decoded with a camera receiver yet remains unobtrusive to the human observer. These techniques have applications in tagging content on screens similar to QR-code tagging for other objects. This paper characterizes the design space for flicker-free embedded screen-camera communication. In particular, we identify an orthogonal dimension to prior work: spatial content-adaptive encoding, and observe that it is essential to combine multiple dimensions to achieve both high capacity and minimal flicker. From these insights, we develop content-adaptive encoding techniques that exploit visual features such as edges and texture to unobtrusively communicate information. These can then be layered over existing techniques to further boost the capacity. Our experimental results show that there is potential to achieve an average goodput of about 22 kbps, significantly outperforming existing work while remaining flicker-free.
【Keywords】: Encoding; Cameras; Receivers; Visualization; Modulation; MIMO; Distortion
【Paper Link】 【Pages】:1-9
【Authors】: Mostafa Izz ; Zhong Yuan Li ; Hongbo Liu ; Yingying Chen ; Feng Li
【Abstract】: Recently, Visible Light Communication (VLC) over a screen-camera channel has drawn considerable attention to unobtrusive design. It overcomes the distractive nature of traditional coded image approaches (e.g., barcodes). Previous unobtrusive methods fall into two categories: (1) utilizing alpha channel, a well known concept in computer graphics, to encode bits into the pixel translucency change with off-the-shelf smart devices; and (2) leveraging the spatial-temporal flicker-fusion property of human vision system with the fast frame rate of modern displays. However, these approaches heavily rely on high-end devices to achieve both unobtrusive and high accuracy screen-camera-based data communication without affecting video-viewing experience. Unlike previous approaches, we propose Uber-in-light, a novel unobtrusive and accurate VLC system, that enables real-time screen-camera communication, applicable to any screen and camera. The proposed system encodes the data as complementary intensity changes over Red, Green, and Blue (RGB) color channels that could be successfully decoded by camera while leaving the human visual perception unaffected. We design a MFSK modulation scheme with dedicated frame synchronization signal embedded in an orthogonal color channel to achieve high throughput. Furthermore, together with the complementary color intensity, an enhanced MUSIC-based demodulation scheme is developed to ensure highly accurate data transmission. Our user experience experiments confirmed the effectiveness of delivering unobtrusive data across different types of video content and resolutions. Extensive real-time performance evaluations are conducted using our prototype implementation to demonstrate the efficiency and reliability of the proposed system under diverse wireless environments.
【Keywords】: Image color analysis; Cameras; Machine vision; Throughput; Synchronization; Visible light communication
【Paper Link】 【Pages】:1-9
【Authors】: Huacheng Zeng ; Xu Yuan ; Xiaoqi Qin ; Yi Shi ; Y. Thomas Hou ; Wenjing Lou
【Abstract】: Interference neutralization (IN) is an interference management technique that allows simultaneous transmission of multiple links by nullifying their mutual interference in the air via cooperation among the transmitters. Although IN has been studied from information theoretic perspective, its potential for a general multi-hop wireless network has not been explored. The goal of this paper is to understand IN in a multi-hop wireless network from networking perspective. We first establish an IN reference model. Based on this reference model, we develop a set of feasibility constraints for a subset of links to be active simultaneously. By identifying each eligible neutralization node (called neut), we study IN in a general multi-hop network and develop a set of necessary constraints to characterize neut selection, IN, and scheduling. These constraints allow us to study the performance of multi-hop networks without the need of getting involved into onerous signal design issues at the physical layer. Finally, we apply our IN model and constraints to study a throughput maximization problem and show that the use of IN can generally increase network throughput. In particular, throughput gain is most significant when the node density increases.
【Keywords】: Interference; Receivers; Transmitters; Spread spectrum communication; Throughput; Precoding; Mathematical model
【Paper Link】 【Pages】:1-9
【Authors】: Changhee Joo ; Myeongseon Shin
【Abstract】: Most distributed wireless scheduling schemes that are provably efficient have been developed under the protocol model, which describes interference constraints in a binary form. However, the oversimplified interference model imposes fundamental limitations on the performance in practice. The signal-to-interference-plus-noise-ratio (SINR) based interference model is more accurate and realistic accounting for the cumulative nature of the interference signals, but its complex structure makes the design of scheduling schemes much more challenging. In this paper, we focus on the scheduling performance under the SINR model and develop random access scheduling schemes that are amenable to implement in a distributed fashion with only local information. We analytically show that they are provably efficient under the SINR model, and through simulations demonstrate that they empirically perform better than the theoretical performance bound.
【Keywords】: Signal to noise ratio; Schedules; Protocols; Scheduling; Interference constraints; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Douglas M. Blough ; Giovanni Resta ; Paolo Santi
【Abstract】: We consider the problem of maximizing performance in multihop wireless networks while achieving fairness among flows. While time-based fairness has been widely recognized as the appropriate fairness mechanism in single-hop wireless networks, no analogous notion has been developed for multihop wireless networks. We define the first general notion of time-based fairness for multihop networks by abstracting a network into a virtual single-hop network and applying the single-hop time-based fairness notion. This produces rate shares for each flow in the network, and we develop a constructive method for achieving these rate shares through physical-interference-aware scheduling. When combined with an appropriate link transmission policy, this scheduling approach preserves the time-based-fair rate shares for flows even with spatial reuse and the resulting rate reductions that occur among concurrent links. To our best knowledge, this is the first constructive approach for achieving fair rate shares in multihop wireless networks with or without interference consideration. We also prove that, with an appropriate scheduling algorithm, this approach produces an aggregate rate that is within a constant factor of the maximum aggregate rate subject to time-based fairness. Finally, we perform extensive simulations, which show that our approach as much as doubles the aggregate rate of a solution that approximates max-min fairness, while achieving a more natural fairness property.
【Keywords】: Interference; Spread spectrum communication; Wireless networks; Signal to noise ratio; Aggregates; Throughput
【Paper Link】 【Pages】:1-9
【Authors】: Zhifeng He ; Shiwen Mao
【Abstract】: We investigate the scheduling problem in a centralized dual-hop 60 GHz network with multiple Source-Destination (SD) pairs, relays, and a PicoNet Coordinator (PNC). The objective is to minimize the Maximum Expected Delivery Time (MEDT) among all SD pairs by jointly optimizing relay and link selection, while exploiting reflected mmWave transmissions and considering link blockage dynamics. We develop a Decomposition Principle to transform this problem into two sub-problems, one for link selection and the other for relay assignment when there is enough replays. We prove that the proposed scheme can achieve an optimality gap of just 1 time slot at greatly reduced complexity. We also develop a heuristic scheme to handle the case when there is no enough relays. The proposed schemes are validated with simulations, where their superior performance is observed.
【Keywords】: Relays; Nonlinear optics; Complexity theory; Wireless communication; Receivers; Markov processes; Array signal processing
【Paper Link】 【Pages】:1-9
【Authors】: Rahul Singh ; Alexander L. Stolyar
【Abstract】: The model is a “generalized switch”, serving multiple traffic flows in discrete time. The switch uses MaxWeight algorithm to make a service decision (scheduling choice) at each time step, depending on the current queue lengths. In some applications, it is not important to keep the queue lengths/delays small (e.g., when queues are virtual, rather than physical), but is important that the service processes provided to each flow remains “smooth” (i.e., without large gaps in service) even when the switch is heavily loaded. Addressing this question reduces to the analysis of the asymptotic behavior of the unscaled queue-differential process in heavy traffic. We prove that the stationary regime of this process converges to that of a positive recurrent Markov chain, whose structure we explicitly describe. This in turn implies “smoothness” of the service processes.
【Keywords】: Switches; Markov processes; Queueing analysis; Throughput; Stability analysis; Convergence; Computers
【Paper Link】 【Pages】:1-9
【Authors】: Lei Deng ; Chih-Chun Wang ; Minghua Chen ; Shizhen Zhao
【Abstract】: Most existing wireless networking solutions are best-effort and do not provide any delay guarantee required by important applications such as the control traffic of cyber-physical systems. Recently, Hou and Kumar provided the first framework for analyzing and designing delay-guaranteed network solutions. While inspiring, their idle-time-based analysis appears to apply only to flows with a special traffic (arrival and expiration) pattern, and the problem remains largely open for general traffic patterns. This paper addresses this challenge by proposing a new framework that characterizes and achieves the complete delay-constrained capacity region with general traffic patterns in single-hop downlink access-point wireless networks. We first formulate the timely capacity problem as an infinite-horizon Markov Decision Process (MDP) and then judiciously combine different simplification methods to convert it to an equivalent finite-size linear program (LP). This allows us to characterize the timely capacity region of flows with general traffic patterns for the first time in the literature. We then design three timely-flow scheduling algorithms for general traffic patterns. The first algorithm achieves the optimal utility but suffers from the curse of dimensionality. The second and third algorithms are inspired by our MDP framework and are of polynomial-time complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.
【Keywords】: Wireless networks; Delays; Real-time systems; Scheduling algorithms; Schedules; Wireless sensor networks
【Paper Link】 【Pages】:1-9
【Authors】: Liang Tong ; Wei Gao
【Abstract】: Mobile Cloud Computing (MCC) bridges the gap between limited capabilities of mobile devices and the increasing complexity of mobile applications, by offloading the computational workloads from local devices to the cloud. Current research supports workload offloading through appropriate application partitioning and remote method execution, but generally ignores the impact of wireless network characteristics on such offloading. Wireless data transmissions incurred by remote method execution consume a large amount of additional energy during transmission intervals when the network interface stays in the high-power state, and deferring these transmissions increases the response delay of mobile applications. In this paper, we adaptively balance the tradeoff between energy efficiency and responsiveness of mobile applications by developing application-aware wireless transmission scheduling algorithms. We take both causality and run-time dynamics of application method executions into account when deferring wireless transmissions, so as to minimize the wireless energy cost and satisfy the application delay constraint with respect to the practical system contexts. Systematic evaluations show that our scheme significantly improves the energy efficiency of workload offloading over realistic smartphone applications.
【Keywords】: Wireless communication; Delays; Mobile applications; Data communication; Cloud computing; Scheduling algorithms; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Feng Shan ; Junzhou Luo ; Weiwei Wu ; Xiaojun Shen
【Abstract】: Wireless power transfer (WPT) technique enables wireless charging/recharging, thus is a promising way to power wireless devices' transmissions. Because current WPT technique requires a wireless device to stop transmitting data when receiving power, and also because the received power in this way is limited, careful scheduling is needed to decide when the device should receive power and when it should transmit such that data can be efficiently transmitted. This paper assumes the most fundamental point-to-point White Gaussian Noise channel is used for data transmission and attempts to obtain an optimal scheduling such that a sequence of data packets can be transmitted with the minimum delay. It is discovered that, for all (energy receiving, data transmitting) cycles, except the last one, the optimal transmission rate should be a constant which is called the wOPT rate. Based on this discovery, this paper optimally solves the offline delay minimization problem. Then, an online heuristic scheduling algorithm is proposed, which either receives energy or transmits at the wOPT rate. Simulations have demonstrated its efficiency. The discovery of the wOPT rate reveals an essential property of WPT, thus is expected to make significant impact in the field of WPT.
【Keywords】: Delays; Wireless communication; Batteries; Transmitters; Optimal scheduling; Minimization
【Paper Link】 【Pages】:1-9
【Authors】: Yue Tan ; Cathy H. Xia
【Abstract】: We develop a data-driven adaptive control framework to password management in cyber security systems. A password policy is the frontline of protection against cyber attacks, which contains a set of rules on password length, duration, etc. We assume password has censored lifetime, and policy maker determines the duration of the password without complete knowledge of its true lifetime distribution. We develop a gradient based algorithm integrated with a Bayesian learning framework. We show that our algorithm converges to optimal solution and adapts to non-stationary lifetime data.
【Keywords】: Bayes methods; Optimization; Random variables; Maintenance engineering; Linear programming; Security; Organizations
【Paper Link】 【Pages】:1-9
【Authors】: Shizhen Zhao ; Xiaojun Lin ; Dionysios Aliprantis ; Hugo N. Villegas ; Minghua Chen
【Abstract】: In this paper, we are interested in online multistage decisions to ensure robust power grid operations under high renewable uncertainty. We jointly consider both the reliability assessment commitment (RAC) and the real-time dispatch problems. We first focus on the real-time dispatch problem and define “maximally robust algorithms,” which can provably ensure grid safety whenever there exists any other algorithm that can ensure grid safety under the same level of future uncertainty. We characterize a class of maximally robust algorithms using the concept of “safe dispatch set,” which also provides conditions for verifying grid safety for RAC. However, in general such safe dispatch sets may be difficult to compute. We then develop efficient computational algorithms for characterizing the safe dispatch sets. Specifically, for a simpler single-bus two-generator case, we show that the safe dispatch sets can be exactly characterized by a polynomial number of convex constraints. Then, based on this two-generator characterization, we develop a new solution for the multi-bus multi-generator case using the idea of virtual demand splitting (VDS), which can effectively compute a suitable subset of the safe-dispatch set. Our numerical results demonstrate that a VDS-based economic dispatch algorithm outperforms the standard economic dispatch algorithm in terms of robustness, without sacrificing economy.
【Keywords】: Uncertainty; Real-time systems; Generators; Robustness; Safety; Optimization
【Paper Link】 【Pages】:1-9
【Authors】: Yin Sun ; Elif Uysal-Biyikoglu ; Roy D. Yates ; Can Emre Koksal ; Ness B. Shroff
【Abstract】: In this work we study how to manage the freshness of status updates sent from a source to a remote monitor via a network server. A proper metric of data freshness at the monitor is the age-of-information, which is defined as how old the freshest update is since the moment this update was generated at the source. A logical policy is the zero-wait policy, i.e., the source submits a fresh update once the server is free, which achieves the maximum throughput and the minimum average delay. Surprisingly, this zero-wait policy does not always minimize the average age. This motivates us to study how to optimally control the status updates to keep data fresh and to understand when the zero-wait policy is optimal. We introduce a penalty function to characterize the level of “dissatisfaction” on data staleness, and formulate the average age penalty minimization problem as a constrained semi-Markov decision process (SMDP) with an uncountable state space. Despite of the difficulty of this problem, we develop efficient algorithms to find the optimal status update policy. We show that, in many scenarios, the optimal policy is to wait for a certain amount of time before submitting a new update. In particular, the zero-wait policy can be far from the optimum if (i) the penalty function grows quickly with respect to the age, and (ii) the update service times are highly random and positive correlated. To the best of our knowledge, this is the first optimal control policy which is proven to minimize the age-of-information in status update systems.
【Keywords】: Monitoring; Servers; Delays; Throughput; Minimization; Temperature sensors; Markov processes
【Paper Link】 【Pages】:1-9
【Authors】: Li Chen ; Wei Cui ; Baochun Li ; Bo Li
【Abstract】: In data parallel frameworks such as MapReduce and Spark, a coflow represents a set of network flows used to transfer intermediate data between successive computation stages for a job. The completion time of a job is then determined by the collective behavior of such a coflow, rather than any individual flow within, and influenced by the amount of network bandwidth allocated to it. Different jobs in a shared cluster have different degrees of sensitivity to their completion times, modeled by their respective utility functions. In this paper, we focus on the design and implementation of a new utility optimal scheduler across competing coflows, in order to provide differential treatment to coflows with different degrees of sensitivity, yet still satisfying max-min fairness across these coflows. Though this objective can be formulated as a lexicographical maximization problem, it is challenging to solve in practice due to its inherent multi-objective and discrete nature. To address this challenge, we first divide the problem into iterative steps of single-objective subproblems; and in each of these steps, we then perform a series of transformations to obtain an equivalent linear programming (LP) problem, which can be efficiently solved in practice. To demonstrate that our solutions are practically feasible, we have implemented it as a real-world coflow scheduler based on the Varys open-source framework to evaluate its effectiveness.
【Keywords】: Optimal scheduling; Schedules; Sensitivity; Ports (Computers); Switches; Servers; Sparks
【Paper Link】 【Pages】:1-9
【Authors】: Xingliang Yuan ; Xinyu Wang ; Jianxiong Lin ; Cong Wang
【Abstract】: Middleboxes are essential for a wide range of advanced traffic processing in modern enterprise networks. Recent trend of deploying middleboxes in cloud as virtualized services further expands potential benefits of middleboxes while avoiding local maintenance burdens. Despite promising, designing outsourced middleboxes still faces several security challenges. First, many middlebox processing services, like intrusion detection, require packet payload inspection, while the ever-increasing adoption of HTTPS limits the function due to the end-to-end encryption. Second, many packet inspection rules used by middleboxes can be proprietary in nature. They may contain sensitive information of enterprises, and thus need strong protection when configuring middleboxes in untrusted outsourced environments. In this paper, we propose a practical system architecture for outsourced middleboxes to perform deep packet inspection over encrypted traffic, without revealing either packet payloads or inspection rules. Our first design is an encrypted high-performance rule filter that takes randomized tokens from packet payloads for encrypted inspection. We then elaborate through carefully tailored techniques how to comprehensively support open-source real rulesets. We formally analyze the security strength. Implementations at Amazon Cloud show that our system introduces roughly 100 millisecond latency in each connection initialization, with individual processing throughput over 3500 packets/second for 500 concurrent connections.
【Keywords】: Cryptography; Middleboxes; Inspection; Payloads; Cloud computing; Systems architecture
【Paper Link】 【Pages】:1-9
【Authors】: Ping-Chun Hsieh ; I-Hong Hou
【Abstract】: This paper proposes online scheduling policies to optimize quality of experience (QoE) for video-on-demand applications in wireless networks. We consider wireless systems where an access point (AP) transmits video content to clients over fading channels. The QoE of each flow is measured by its duration of video playback interruption. We are specifically interested in systems operating in the heavy-traffic regime. We first consider a special case of ON-OFF channels and establish a scheduling policy that achieves every point in the capacity region under heavy-traffic conditions. This policy is then extended for more general fading channels, and we prove that it remains optimal under some mild conditions. We then formulate a network utility maximization problem based on the QoE of each flow. We demonstrate that our policies achieve the optimal overall utility when their parameters are chosen properly. Finally, we compare our policies against three popular policies. Simulation results validate that the proposed policy indeed outperforms existing policies.
【Keywords】: Streaming media; Wireless networks; Interrupters; Throughput; Fading channels; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Huaxin Li ; Zheyu Xu ; Haojin Zhu ; Di Ma ; Shuai Li ; Kai Xing
【Abstract】: Although privacy leaking through content analysis of Wi-Fi traffic has received an increased attention, privacy inference through meta-data (e.g. IP, Host) analysis of Wi-Fi traffic represents a potentially more serious threat to user privacy. Firstly, it represents a more efficient and scalable approach to infer users' sensitive information without checking the content of Wi-Fi traffic. Secondly, meta-data based demographics inference can work on both unencrypted and encrypted traffic (e.g., HTTPS traffic). In this study, we present a novel approach to infer user demographic information by exploiting the meta-data of Wi-Fi traffic. We develop a proof-of-concept prototype, Demographic Information Predictor (DIP) system, and evaluate its performance on a real-world dataset, which includes the Wi-Fi access of 28,158 users in 5 months. DIP extracts four kinds of features from real-world Wi-Fi traffic and proposes a novel machine learning based inference technique to predict user demographics. Our analytical results show that, for unencrypted traffic, DIP can predict gender and education level of users with an accuracy of 78% and 74% respectively. It is surprising to show that, even for HTTPS traffic, user demographics can still be predicted at a precision of 67% and 72% respectively, which well demonstrates the practicality of the proposed privacy inference scheme.
【Keywords】: IEEE 802.11 Standard; Privacy; Electronics packaging; Cryptography; Protocols; Feature extraction
【Paper Link】 【Pages】:1-9
【Authors】: Xinfeng Li ; Gang Li ; Fan Yang ; Jin Teng ; Dong Xuan ; Biao Chen
【Abstract】: Massive visual traffic data have become available recently, which provides an opportunity for intelligent traffic analysis. Timely processing is particularly necessary for traffic analysis. In this paper, we study time-bounded aggregation analytics on large visual traffic data. We first find that current MapReduce framework can not work well due to two challenges: first, significant dual diversities exist on data distributions and processing time; second, no apriori knowledge on these distributions and time costs is available. However, we also observe spatial and temporal locality on data values and processing time. Based on the examination, we design TaG, an augmented MapReduce framework for time-bounded traffic analytics jobs. Particularly, we propose a novel sampling algorithm that exploits traffic data localities and stratifies samples based on data distributions and processing time. It runs in an iterative, adaptive manner without apriori knowledge. Moreover, we propose a heuristic scheduling algorithm with considerations of batch processing overhead. Further, we refine load balancing mechanism based on data processing time locality to respect job time bounds. We implement TaG on Hadoop and conduct extensive experiments on a large traffic image dataset. The evaluations on different data sizes show TaG is able to achieve high accuracy within different time bounds.
【Keywords】: Visualization; Load management; Vehicles; Big data; Scheduling algorithms; Computer vision
【Paper Link】 【Pages】:1-9
【Authors】: Morteza Kheirkhah ; Ian Wakeman ; George Parisis
【Abstract】: Modern data centres provide large aggregate network capacity and multiple paths among servers. Traffic is very diverse; most of the data is produced by long, bandwidth hungry flows but the large majority of flows, which commonly come with strict deadlines regarding their completion time, are short. It has been shown that TCP is not efficient for any of these types of traffic in modern data centres. More recent protocols such MultiPath TCP (MPTCP) are very efficient for long flows, but are ill-suited for short flows. In this paper, we present Maximum MultiPath TCP (MMPTCP), a novel transport protocol which, compared to TCP and MPTCP, reduces short flows' completion times, while providing excellent goodput to long flows. To do so, MMPTCP runs in two phases; initially, it randomly scatters packets in the network under a single congestion window exploiting all available paths. This is beneficial to latency-sensitive flows. After a specific amount of data is sent, MMPTCP switches to a regular MultiPath TCP mode. MMPTCP is incrementally deployable in existing data centres as it does not require any modifications outside the transport layer and behaves well when competing with legacy TCP and MPTCP flows. Our extensive experimental evaluation in simulated FatTree topologies shows that all design objectives for MMPTCP are met.
【Keywords】: Transport protocols; Topology; Standards; Servers; Network topology; Switches
【Paper Link】 【Pages】:1-9
【Authors】: Jiao Zhang
【Abstract】: Most of today's data center applications are sensitive to latency. In this paper, a Deadline-aware bandwidth Sharing mechanism by Allocating switch Buffer (DSAB) is proposed to satisfy the deadline requirements of flows. As the existing work SAB does, DSAB also leverages the feature that the buffer size of a switch port is usually much larger than the product of bandwidth and round trip delay in data center networks. The basic idea of DSAB is to allocate switch buffer to deadline-sensitive flows in priority and the remaining buffer is fairly allocated to background flows. However, this method will possibly lead to bandwidth wastage in topologies with multiple bottlenecks. Therefore, enlightened by the pre-authorization method in credit card systems, we propose a Pre-Authorization (PA) algorithm to address this problem. The PA algorithm allows switches take back the extra allocated bandwidth by adding a bandwidth confirmation phase after the bandwidth request phase. End hosts and switch functions of DSAB is implemented in Linux kernel and NetFPGA platform, respectively. The results of experiments conducted in a real small testbed indicate that DSAB can indeed satisfy the deadline requirements of deadline-sensitive flows by allocating switch buffer to them in priority.
【Keywords】: Bandwidth; Switches; Delays; Transport protocols; Ports (Computers); Topology; Convergence
【Paper Link】 【Pages】:1-9
【Authors】: Ziyang Li ; Yiming Zhang ; Dongsheng Li ; Kai Chen ; Yuxing Peng
【Abstract】: Task-aware flow schedulers collect task information across the data center to optimize task-level performance. However, the majority of the tasks, which generate short flows and are called tiny tasks, have been largely overlooked by current schedulers. The large number of tiny tasks brings significant overhead to the centralized schedulers, while the existing decentralized schedulers are too complex to fit in commodity switches. In this paper we present OPTAS, a lightweight, commodity-switch-compatible scheduling solution that efficiently monitors and schedules flows for tiny tasks with low overhead. OPTAS monitors system calls and buffer footprints to recognize the tiny tasks, and assigns them with higher priorities than larger ones. The tiny tasks are then transferred in a FIFO manner by adjusting two attributes, namely, the window size and round trip time, of TCP. We have implemented OPTAS as a Linux kernel module, and experiments on our 37-server testbed show that OPTAS is at least 2.2× faster than fair sharing, and 1.2× faster than only assigning tiny tasks with the highest priority.
【Keywords】: Processor scheduling; Scheduling; Monitoring; Optimization; Delays; Bandwidth; Receivers
【Paper Link】 【Pages】:1-9
【Authors】: Jiawei Huang ; Tian He ; Yi Huang ; Jianxin Wang
【Abstract】: In data center networks, many network-intensive applications typically suffer TCP incast throughput collapse when bursty concurrent TCP flows share a single bottleneck link. To address the TCP incast problem, we first reveal theoretically and empirically that controlling the number of concurrent flows is much more effective in reducing the incast probability than controlling the congestion window. We further propose a novel cross-layer design called Adaptive Request Schedule (ARS), which dynamically adjusts the number of concurrent TCP flows by batching application requests according to the congestion state acquired from transport layer. ARS is deployed only at the aggregator-side, while making no modification on hundreds or thousands of workers. Broad applicability is another advantage of ARS. We integrated ARS transparently (i.e., without modification) with DCTCP and TCP NewReno on NS2 simulation and a physical testbed, respectively. The experimental results show that ARS significantly reduces the incast probability across different TCP protocols and that the network goodput can be increased consistently by on average 6x under severe congestion.
【Keywords】: Packet loss; Protocols; Servers; Probability; Ports (Computers); Throughput
【Paper Link】 【Pages】:1-9
【Authors】: Rachid Guerraoui ; Erwan Le Merrer ; Rhicheek Patra ; Bao Duy Tran
【Abstract】: Aggregation of streamed data is key to the expansion of the Internet of Things. This paper addresses the problem of designing a topology for reliably aggregating data flows from many devices arriving at a datacenter. Reliability here means ensuring operation without data loss. We seek a frugal solution that prevents wasteful resource consumption (over-provisioning). This problem is salient when building an aggregation service out of components (here aggregation nodes) that exhibit hard constraints on the amount of information they can handle per unit of time. We first formalize the problem and provide an analysis of the relation between monitored devices (plus information they send), and the operations performed at aggregation nodes, in terms of data rates. Building on this rate analysis, we devise a novel algorithm, which we call CSA, that basically outputs an aggregation topology capable of handling those incoming data rates, preventing thereby empirical trial-and-error design. We analyze the algorithm, before validating it on the Amazon Kinesis platform, using a device dataset from a European telco operator.
【Keywords】: Topology; Aggregates; Reliability; Algorithm design and analysis; Monitoring; Real-time systems; Program processors
【Paper Link】 【Pages】:1-9
【Authors】: Zeqi Lai ; Yong Cui ; Minming Li ; Zhenhua Li ; Ningwei Dai ; Yuchi Chen
【Abstract】: Cloud computing platforms enable applications to offer low latency access to user data by offering storage services in several geographically distributed data centers. In this paper, we identify the high tail latency problem in cloud CDN via analyzing a large-scale dataset collected from 783,944 users in a major cloud CDN. We find that the data downloading latency in cloud CDN is highly variable, which may significantly degrade the user experience of applications. To address the problem, we present TailCutter, a workload scheduling mechanism that aims at optimizing the tail latency while meeting the cost constraint given by application providers. We further design the Maximum Tail Minimization Algorithm (MTMA) working in TailCutter mechanism to optimally solve the Tail Latency Minimization (TLM) problem in polynomial time. We implement TailCutter across data centers of Amazon S3 and Microsoft Azure. Our extensive evaluation using large-scale real world data traces shows that TailCutter can reduce up to 68% 99th percentile user-perceived latency in comparison with alternative solutions under cost constraints.
【Keywords】: Cloud computing; Minimization; Bandwidth; Time-varying systems; Time-domain analysis; Distributed databases
【Paper Link】 【Pages】:1-9
【Authors】: Javad Ghaderi
【Abstract】: We consider the problem of scheduling VMs (Virtual Machines) in a multi-server system motivated by cloud computing applications. VMs arrive dynamically over time and require various amounts of resources (e.g., CPU, Memory, Storage, etc.) for the duration of their service. When a VM arrives, it is queued and later served by one of the servers that has sufficient remaining capacity to serve it. The scheduling of VMs is subject to: (i) packing constraints, i.e., multiple VMs can be be served simultaneously by a single server if their cumulative resource requirement does not violate the capacity of the server, and (ii) non-preemption, i.e., once a VM is scheduled in a server, it cannot be interrupted or migrated to another server. To achieve maximum throughput, prior results hinge on solving a hard combinatorial problem (Knapsack) at the instances that all the servers become empty (the so-called global refresh times which require synchronization among the servers). The main contribution of this paper is that it resolves these issues. Specifically, we present a class of randomized algorithms for placing VMs in the servers that can achieve maximum throughput without preemptions. The algorithms are naturally distributed, have low complexity, and each queue needs to perform limited operations. Further, our algorithms display good delay performance in simulations, comparable to delay of heuristics that may not be throughput-optimal, and much better than the delay of the prior known throughput-optimal algorithms.
【Keywords】: Servers; Cloud computing; Heuristic algorithms; Delays; Virtual machining; Throughput; Complexity theory
【Paper Link】 【Pages】:1-9
【Authors】: Tao Lu ; Ping Huang ; Morgan Stuart ; Yuhua Guo ; Xubin He ; Ming Zhang
【Abstract】: In virtualization platforms, host-side storage caches can serve virtual machines (VM) disk I/O requests, which originally target network storage servers. When these requests hit host-side caches, network and disk access latencies are obviated, and thus VMs perceive improved storage performance. VM migration is common in cloud environments, however, VM migration does not transfer host-side cache states. As a result, a newly migrated VM suffers performance degradation until the cache is fully rebuilt. The performance degradation period can be hours long if the cache is naturally warmed up. Employing existing cache warm-up solutions such as migrating host-side cache and Bonfire, VMs may either have a prolonged total migration time or undergo a performance degradation period of tens of minutes due to the warm-up caused storage contention. We propose Successor, which proactively warms up caches of destination hosts before migration completes. Specifically, accessibility of destination hosts during migration enables Successor to parallelize cache warm-up and VM migration. Compared with migrating host-side cache and Bonfire, Successor achieves zero VM-perceived cache warm-up time with low resource costs and performance penalties. We have implemented a prototype of Successor on QEMU/KVM based virtualization platform and verified its efficiency.
【Keywords】: Servers; Cloud computing; Context; Virtualization; Degradation; Cache storage; Optimization
【Paper Link】 【Pages】:1-9
【Authors】: Long Cheng ; Yu Gu ; Jianwei Niu ; Ting Zhu ; Cong Liu ; Qingquan Zhang ; Tian He
【Abstract】: Many-to-one data collection is a fundamental operation in wireless sensor networks (WSNs). To support long-term deployment of WSNs, sensor nodes normally operate at low-duty-cycles. However, the low-duty-cycle operation significantly reduces the communication chance between nodes. Consequently, the risk of data collisions significantly increases when multiple senders transmit packets to a receiver during its very short active period. Data collision not only results in wasted packet transmissions, but also incurs a large delivery latency. Under such conditions, collision-free medium access is more appealing than recovering after collision for low-duty-cycle WSNs. In this work, we propose an incast-collision-free data collection protocol, named iCore, to address the many-to-one collision problem in low-duty-cycle WSNs. iCore employs the dynamic forwarding technique and establishes a non-conflicting schedule for delay reduction. Specifically, we design efficient forwarder assignment and forwarding optimization algorithms that ensure low end-to-end latency under diverse data traffic types. Through comprehensive performance evaluations, we demonstrate that, compared with the state-of-the-art protocol, iCore effectively minimizes the end-to-end delay by 25% ~ 57% and maintains high delivery ratio and energy efficiency for different many-to-one convergecast scenarios.
【Keywords】: Wireless sensor networks; Delays; Data collection; Schedules; Wireless communication; Receivers; Protocols
【Paper Link】 【Pages】:1-9
【Authors】: Vijay S. Rao ; M. Koppal ; R. Venkatesha Prasad ; Tamma V. Prabhakar ; Chayan Sarkar ; Ignas G. Niemegeers
【Abstract】: Constructive Interference (CI) phenomenon has been exploited by Glossy, a mechanism for low-latency and reliable network flooding and time synchronization for wireless sensor networks. Recently, CI has also been used for other applications such as data collection and multicasting in static and mobile WSNs. These applications base their working on the high reliability promised by Glossy regardless of the physical conditions of deployment, number of nodes in the network, and unreliable wireless channels that may be detrimental for CI. There are several works that study the working of CI, but they present inconsistent views. We study CI from a receiver's viewpoint, list factors that affect CI and also specify how and why they affect. We validate our arguments with results from extensive and rigorous experimentation in real-world settings. This paper presents comprehensive insights into CI phenomenon. With this understanding, we improve the performance of CI through an energy-efficient and distributed algorithm. We cause destructive interference on a designated byte to provide negative feedback. We leverage this to adapt transmission powers. Compared to Glossy, we achieve 25% lesser packet losses while using only half of its transmission power.
【Keywords】: Radio transmitters; Receivers; Interference; Wireless sensor networks; Synchronization; Reliability; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Georg von Zengen ; Yannic Schröder ; Stephan Rottmann ; Felix Büsching ; Lars C. Wolf
【Abstract】: Being able to determine the location of a node is of great advantage in many IoT and WSN applications. For example, in health care scenarios or for autonomous configuration of IoT setups this information can be useful. One of the key challenges in localization is to estimate the distance between nodes. Most present indoor localization systems require additional hardware for this estimation which is costly in terms of money and energy consumption. To overcome this disadvantage, we developed a system which is able to perform distance measurements without adding any extra hardware and costs. It is based on phase measurements performed by the IEEE 802.15.4 transceiver chip that is normally solely used to realize communication. In the evaluation we investigate the performance of our system in different real world environments that are typical for IoT and WSN setups.
【Keywords】: Phase measurement; Frequency measurement; Estimation; Semiconductor device measurement; Receivers; Synchronization; Clocks
【Paper Link】 【Pages】:1-9
【Authors】: Xueshu Zheng ; Shuailing Yang ; Naigao Jin ; Lei Wang ; Mathew L. Wymore ; Daji Qiao
【Abstract】: This paper presents DiVA, a novel hybrid range-free and range-based acoustic source localization scheme that uses an ad-hoc network of microphone sensor nodes to produce an accurate estimate of the source's location in the presence of various real-world challenges. DiVA uses range-free pairwise comparisons of sound detection timestamps between local Voronoi neighbors to identify the node closest to the acoustic source, which then estimates the source's location using a constrained range-based method. Through simulation and experimental evaluations, DiVA is shown to be accurate and highly robust, making it practical for real-world applications.
【Keywords】: Acoustics; Robustness; Probes; Wireless sensor networks; Position measurement; Ad hoc networks; Microphones
【Paper Link】 【Pages】:1-9
【Authors】: Shanhe Yi ; Zhengrui Qin ; Edmund Novak ; Yafeng Yin ; Qun Li
【Abstract】: We have seen an emerging trend towards wearables nowadays. In this paper, we focus on smart glasses, whose current interfaces are difficult to use, error-prone, and provide no or insecure user authentication. We thus present GlassGesture, a system that improves Google Glass through a gesture-based user interface, which provides efficient gesture recognition and robust authentication. First, our gesture recognition enables the use of simple head gestures as input. It is accurate in various wearer activities regardless of noise. Particularly, we improve the recognition efficiency significantly by employing a novel similarity search scheme. Second, our gesture-based authentication can identify owner through features extracted from head movements. We improve the authentication performance by proposing new features based on peak analyses, and employing an ensemble method. Last, we implement GlassGesture and present extensive evaluations. GlassGesture achieves a gesture recognition accuracy near 96%. For authentication, GlassGesture can accept authorized users in near 92% of trials, and reject attackers in near 99% of trials. We also show that in 100 trials imitators cannot successfully masquerade as the authorized user even once.
【Keywords】: Glass; Authentication; Gesture recognition; User interfaces; Google; Feature extraction; Sensors
【Paper Link】 【Pages】:1-9
【Authors】: Qianyi Huang ; Yan Mei ; Wei Wang ; Qian Zhang
【Abstract】: Recent years have witnessed the prevalence of wearable devices. Wearable devices are intelligent and multifunctional, but they rely heavily on batteries. This greatly limits their application scope, where replacement of battery or recharging is challenging or inconvenient. We note that wearable devices have the opportunity to harvest energy from human motion, as they are worn by the people as long as being functioning. In this study, we propose a battery-free sensing platform for wearable devices in the form-factor of shoes. It harvests the kinetic energy from walking or running to supply devices with power for sensing, processing and wireless communication, covering all the functionalities of commercial wearable devices. We achieve this goal by enabling the whole system running on the harvested energy from two feet. Each foot performs separate tasks and two feet are coordinated by ambient backscatter communication. We instantiate this idea by building a prototype, containing energy harvesting insoles, power management circuits and ambient backscatter module. Evaluation results demonstrate that the system can wake up shortly after several seconds' walk and have sufficient Bluetooth throughput for supporting many applications. We believe that our framework can stir a lot of useful applications that were infeasible previously.
【Keywords】: Foot; Biomedical monitoring; Footwear; Backscatter; Sensors; Legged locomotion; Energy harvesting
【Paper Link】 【Pages】:1-9
【Authors】: Çagdas Karatas ; Luyang Liu ; Hongyu Li ; Jian Liu ; Yan Wang ; Sheng Tan ; Jie Yang ; Yingying Chen ; Marco Gruteser ; Richard P. Martin
【Abstract】: Given the increasing popularity of wearable devices, this paper explores the potential to use wearables for steering and driver tracking. Such capability would enable novel classes of mobile safety applications without relying on information or sensors in the vehicle. In particular, we study how wrist-mounted inertial sensors, such as those in smart watches and fitness trackers, can track steering wheel usage and angle. In particular, tracking steering wheel usage and turning angle provide fundamental techniques to improve driving detection, enhance vehicle motion tracking by mobile devices and help identify unsafe driving. The approach relies on motion features that allow distinguishing steering from other confounding hand movements. Once steering wheel usage is detected, it further uses wrist rotation measurements to infer steering wheel turning angles. Our on-road experiments show that the technique is 99% accurate in detecting steering wheel usage and can estimate turning angles with an average error within 3.4 degrees.
【Keywords】: Wheels; Sensors; Safety; Tracking; Turning; Automobiles
【Paper Link】 【Pages】:1-9
【Authors】: Meenupriya Swaminathan ; Ufuk Muncuk ; Kaushik R. Chowdhury
【Abstract】: Implanted sensors and actuators in the human body promise in-situ health monitoring and rapid advancements in personalized medicine. We propose a new paradigm where such implants may communicate wirelessly through a technique called as galvanic coupling, which uses weak electrical signals and the conduction properties of body tissues. While galvanic coupling overcomes the problem of massive absorption of RF waves in the body, the unique intra-body channel raises several questions on the topology of the implants and the external (i.e., on skin) data collection nodes. This paper makes the first contributions towards (i) building an energy-efficient topology through optimal placement of data collection points/relays using measurement-driven tissue channel models, and (ii) balancing the energy consumption over the entire implant network so that the application needs are met. We achieve this via a two-phase iterative clustering algorithm for the implants and formulate an optimization problem that decides the position of external data-gathering points. Our theoretical results are validated via simulations and experimental studies on real tissues, with demonstrated increase in the network lifetime.
【Keywords】: Relays; Implants; Sensors; Wireless sensor networks; Skin; Muscles; Receivers
【Paper Link】 【Pages】:1-9
【Authors】: Yanjiao Chen ; Baochun Li ; Qian Zhang
【Abstract】: In a crowdsourcing system, it is important for the crowdsourcer to engineer extrinsic rewards to incentivize the participants. With mobile social networking, a user enjoys an intrinsic benefit when she aligns her behavior with the behavior of others. Referred to as network effects, such an intrinsic benefit becomes more significant as the number of users grows in the crowdsourcing system. But should a crowdsourcer design her extrinsic rewards differently when such network effects are taken into account? In this paper, we, for the first time, consider network effects as a contributing factor to intrinsic rewards, and study its influence on the design of extrinsic rewards. Rather than assuming a fixed participant population, we show that the number of participating users evolves to a steady equilibrium, thanks to subtle interactions between intrinsic rewards due to network effects and extrinsic rewards offered by the crowdsourcer. Taken network effects into consideration, we design progressively more sophisticated extrinsic reward mechanisms, and propose new and optimal strategies for a crowdsourcer to obtain a higher utility. Via extensive simulations, we demonstrate that with our new strategies, a crowdsourcer is able to attract more participants with higher contributed efforts; and participants gain higher utilities from both intrinsic and extrinsic rewards.
【Keywords】: Crowdsourcing; Sociology; Statistics; Computers; Mobile communication; Games; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Gaoqiang Zhuo ; Qi Jia ; Linke Guo ; Ming Li ; Pan Li
【Abstract】: Crowdsourcing is a crowd-based outsourcing, where a requester (task owner) can outsource tasks to workers (public crowd). Recently, mobile crowdsourcing, which can leverage workers' data from smartphones for data aggregation and analysis, has attracted much attention. However, when the data volume is getting large, it becomes a difficult problem for a requester to aggregate and analyze the incoming data, especially when the requester is an ordinary smartphone user or a start-up company with limited storage and computation resources. Besides, workers are concerned about their identity and data privacy. To tackle these issues, we introduce a three-party architecture for mobile crowdsourcing, where the cloud is implemented between workers and requesters to ease the storage and computation burden of the resource-limited requester. Identity privacy and data privacy are also achieved. With our scheme, a requester is able to verify the correctness of computation results from the cloud. We also provide several aggregated statistics in our work, together with efficient data update methods. Extensive simulation shows both the feasibility and efficiency of our proposed solution.
【Keywords】: Cloud computing; Data privacy; Crowdsourcing; Smart phones; Mobile communication; Sensors
【Paper Link】 【Pages】:1-9
【Authors】: Lingjun Pu ; Xu Chen ; Jingdong Xu ; Xiaoming Fu
【Abstract】: In this paper, we advocate Crowdlet, a novel self-organized mobile crowdsourcing paradigm, in which a mobile task requester can proactively exploit a massive crowd of encountered mobile workers at real-time for quick and high-quality results. We present a comprehensive system model of Crowdlet that defines task, worker arrival and worker ability models. Further, we introduce a service quality concept to indicate the expected service gain that a requester can enjoy when he recruits an encountered worker, by jointly taking into account worker ability, real-timeness and task reward. Based on the models, we formulate an online worker recruitment problem to maximize the expected sum of service quality. We derive an optimal worker recruitment policy through the dynamic programming principle, and show that it exhibits a nice threshold based structure. We conduct extensive performance evaluation based on real traces, and numerical results demonstrate that our policy can achieve superior performance and improve more than 30% performance gain over classic policies. Besides, our Android prototype shows that Crowdlet is cost-efficient, requiring less than 7 seconds and 6 Joule in terms of time and energy cost for policy computation in most cases.
【Keywords】: Mobile communication; Crowdsourcing; Recruitment; Real-time systems; Computational modeling; Exponential distribution
【Paper Link】 【Pages】:1-9
【Authors】: Honggang Zhang ; Benyuan Liu ; Hengky Susanto ; Guoliang Xue ; Tong Sun
【Abstract】: We investigate emerging proximity-based Mobile Crowd Service or pMCS systems, in which services are provided and consumed by users carrying smart mobile devices (e.g., smartphones) and in proximity of each other (e.g., within Bluetooth range). Due to limited resources on smartphones, it is crucial to provide a mechanism to incentivize users' participation and ensure fair trading in a pMCS system. In this paper, we design a multi-market dynamic double auction mechanism for a pMCS system, referred to as MobiAuc, and we show that it is truthful, feasible, individual-rational, no-deficit, and computationally efficient. The novelty and significance of MobiAuc is that it addresses and solves the fair trading problem in a multi-market dynamic double auction setting which naturally occurs in a mobile wireless environment. We demonstrate its efficiency via simulations based on generated user patterns (stochastic arrivals and random market clustering of users) and real-world traces. Our preliminary implementation of MobiAuc and experiments on Android platform have demonstrated the feasibility of MobiAuc mechanism in practice.
【Keywords】: Smart phones; Mobile communication; Heuristic algorithms; Algorithm design and analysis; Wireless communication; Bluetooth; Electronic mail
【Paper Link】 【Pages】:1-9
【Authors】: Mohamed Lamine Lamali ; Nasreddine Fergani ; Johanne Cohen ; Hélia Pouyllau
【Abstract】: Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to a suboptimal use of the network resources and additional operational costs. However, some routers are able to encapsulate, decapsulate and convert protocols and act as a liaison between these layers. A unified control plane would be useful to optimize the use of the network resources and automate the routing configurations. Software-Defined Networking (SDN) based architectures, such as OpenFlow, offer a chance to design such a control plane. One of the most important problems to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem as they do not take into account encapsulations and conversions of protocols. In this paper, we propose algorithms to solve this problem and study several cases: Path computation without bandwidth constraint, under bandwidth constraint and under other Quality of Service constraints. We study the complexity and the scalability of our algorithms and evaluate their performances on real topologies. The results show that they outperform the previous ones proposed in the literature.
【Keywords】: Protocols; Encapsulation; Adaptation models; Computational modeling; Bandwidth; Context; Complexity theory
【Paper Link】 【Pages】:1-9
【Authors】: Fang Hao ; Murali S. Kodialam ; T. V. Lakshman
【Abstract】: Segment routing is a new proposed routing mechanism for simplified and flexible path control in IP/MPLS networks. It builds on existing network routing and connection management protocols and one of its important features is the automatic rerouting of connections upon failure. Re-routing can be done with available restoration mechanisms including IGP-based rerouting and fast reroute with loop-free alternates. This is particularly attractive for use in Software Defined Networks (SDN) because the central controller need only be involved at connection set-up time and failures are handled automatically in a distributed manner. A significant challenge in restoration optimization in segment routed networks is the centralized determination of connections primary paths so as to enable the best sharing of restoration bandwidth over non-simultaneous network failures. We formulate this problem as a linear programming problem and develop an efficient primal-dual algorithm for the solution. We also develop a simple randomized rounding scheme for cases when there are additional constraints on segment routing. We demonstrate the significant capacity benefits achievable from this optimized restoration with segment routing.
【Keywords】: Routing; Routing protocols; Planning; Bandwidth; Multiprotocol label switching; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Marco Chiesa ; Ilya Nikolaevskiy ; Slobodan Mitrovic ; Aurojit Panda ; Andrei V. Gurtov ; Aleksander Madry ; Michael Schapira ; Scott Shenker
【Abstract】: Fast Reroute (FRR) and other forms of immediate failover have long been used to recover from certain classes of failures without invoking the network control plane. While the set of such techniques is growing, the level of resiliency to failures that this approach can provide is not adequately understood. We embark upon a systematic algorithmic study of the resiliency of immediate failover in a variety of models (with/without packet marking/duplication, etc.). We leverage our findings to devise new schemes for immediate failover and show, both theoretically and experimentally, that these outperform existing approaches.
【Keywords】: Routing; Routing protocols; Robustness; Delays; Topology; Ports (Computers); Computer science
【Paper Link】 【Pages】:1-9
【Authors】: Stefanie Roos ; Martin Beck ; Thorsten Strufe
【Abstract】: Friend-to-friend (F2F) overlays, which restrict direct communication to mutually trusted parties, are a promising substrate for privacy-preserving communication due to their inherent membership-concealment and Sybil-resistance. Yet, existing F2F overlays suffer from a low performance, are vulnerable to denial-of-service attacks, or fail to provide anonymity. In particular, greedy embeddings allow highly efficient communication in arbitrary connectivity-restricted overlays but require communicating parties to reveal their identity. In this paper, we present a privacy-preserving routing scheme for greedy embeddings based on anonymous return addresses rather than identifying node coordinates. We show that the return addresses allow plausible deniability. Furthermore, we enhance the routing's resilience by using multiple embeddings and propose a method for efficient content addressing. Our extensive simulation study on real-world data indicates that our approach is highly efficient and effectively mitigates failures as well as powerful denial-of-service attacks.
【Keywords】: Routing; Resilience; Receivers; Computer crime; Performance analysis; Robustness
【Paper Link】 【Pages】:1-9
【Authors】: Yu Luo ; Lina Pu ; Zheng Peng ; Jun-Hong Cui
【Abstract】: In recent years, the underwater cognitive acoustic network (UCAN) has been advocated as an efficient technique to enhance the utilization of acoustic channel, while not interrupting the activity of marine mammals, sonars and other acoustic users. In cognitive radios, the common control channel (CCC) based media access control (MAC) protocols are very popular for their high reliability, easy implementation and low overhead. However, due to the severe frequency-dependent attenuation of acoustic waves, a UCAN may not have enough bandwidth for CCC. How to prevent the control channel from congesting in a UCAN with heavy traffic should be investigated carefully. With this in mind, we propose a dynamic control channel MAC (DCC-MAC) for distributed UCANs. Nodes in DCC-MAC could adjust the bandwidth of their control channel adaptively based on the situation of network traffic. Whenever acoustic nodes detected the congestion of CCC, they could flexibly select proper data channels to extend the bandwidth of their control channel, and return excessive frequency bands back when the control channel becomes idle. Simulation results show that DCC-MAC could reduce the collision probability among control messages significantly, thereby providing a better network performance in terms of throughput and energy efficiency than conventional cognitive MAC protocols.
【Keywords】: Media Access Protocol; Bandwidth; Acoustics; Synchronization; Frequency control; Receivers
【Paper Link】 【Pages】:1-9
【Authors】: Ming Li ; Dejun Yang ; Jian Lin ; Ming Li ; Jian Tang
【Abstract】: In cognitive radio networks (CRNs), dynamic spectrum access has been proposed to improve the spectrum utilization, but it also generates spectrum misuse problems. One common solution to these problems is to deploy monitors to detect misbehaviors on certain channel. However, in multi-channel CRNs, it is very costly to deploy monitors on every channel. With a limited number of monitors, we have to decide which channels to monitor. In addition, we need to determine how long to monitor each channel and in which order to monitor, because switching channels incurs costs. Moreover, the information about the misuse behavior is not available a priori. To answer those questions, we model the spectrum usage monitoring problem as an adversarial multi-armed bandit problem with switching costs and design two effective online algorithms, SpecWatch and SpecWatch+. In SpecWatch, we select strategies based on the monitoring history and repeat the same strategy for certain timeslots to reduce switching costs. We prove its expected weak regret, i.e., the performance difference between the solution of SpecWatch and optimal (fixed) solution, is O(T2/3), where T is the time horizon. Whereas, in SpecWatch+, we select strategies more strategically to improve the performance. We show its actual weak regret is O(T2/3) with probability 1-δ, for any δ e (0,1). Both algorithms are evaluated through extensive simulations.
【Keywords】: Monitoring; Switches; Algorithm design and analysis; Stochastic processes; Cognitive radio; Computers; Electrical engineering
【Paper Link】 【Pages】:1-9
【Authors】: Bo Yang ; Meng Zheng ; Wei Liang
【Abstract】: Channel rendezvous is a prerequisite for secondary users (SUs) to set up communications in cognitive radio networks (CRNs). It is expected that the rendezvous can be achieved within a short finite time for delay-sensitive applications and over all available channels to increase the robustness to unstable channels. Some existing works suffer from a small number of rendezvous channels and can only guarantee rendezvous under the undesired requirements such as synchronous clock, homogeneous available channels, predetermined roles and explicit SUs' identifiers (IDs). In this paper, to address these limitations, we employ the notion of Disjoint Set Cover (DSC) and propose a DSC-based Rendezvous (DSCR) algorithm. We first present an approximation algorithm to construct one DSC. The variant permutations of elements in the ingeniously constructed DSC are then utilized to regulate the order of accessing channels, enabling SUs to rendezvous on all available channels within a short duration. We derive the theoretical maximum and expected rendezvous latency and prove the full rendezvous degree of the DSCR algorithm. Extensive simulations show that the DSCR algorithm can significantly reduce the rendezvous latency compared to existing algorithms.
【Keywords】: Approximation algorithms; Clocks; Algorithm design and analysis; Heuristic algorithms; Cognitive radio; Sensors; Amplitude modulation
【Paper Link】 【Pages】:1-9
【Authors】: Orly Avner ; Shie Mannor
【Abstract】: Inspired by cognitive radio networks, we consider a setting where multiple users share several channels modeled as a multi-user multi-armed bandit (MAB) problem. The characteristics of each channel are unknown and are different for each user. Each user can choose between the channels, but her success depends on the particular channel chosen as well as on the selections of other users: if two users select the same channel their messages collide and none of them manages to send any data. Our setting is fully distributed, so there is no central control. As in many communication systems, the users cannot set up a direct communication protocol, so information exchange must be limited to a minimum. We develop an algorithm for learning a stable configuration for the multi-user MAB problem. We further offer both convergence guarantees and experiments inspired by real communication networks, including comparison to state-of-the-art algorithms.
【Keywords】: Protocols; Information exchange; Communication networks; Cognitive radio; Stochastic processes; Stability analysis
【Paper Link】 【Pages】:1-9
【Authors】: Haoran Yu ; Man Hon Cheung ; Lin Gao ; Jianwei Huang
【Abstract】: There has been a proliferation of public Wi-Fi hotspots that serve a significant amount of global mobile traffic today. In this paper, we propose a general Wi-Fi monetization model for public Wi-Fi hotspots deployed by venue owners (VOs), where VOs generate revenue from providing both the premium Wi-Fi access and the advertising sponsored Wi-Fi access to mobile users (MUs). With the premium access, MUs directly pay VOs for their Wi-Fi usage; while with the advertising sponsored access, MUs watch advertisements for the free usage of Wi-Fi. VOs sell their ad spaces to advertisers (ADs) via an ad platform, and share a proportion of the revenue with the ad platform. We formulate the economic interactions among the ad platform, VOs, MUs, and ADs as a three-stage Stackelberg game. By analyzing the equilibrium, we show that the ad platform's advertising revenue sharing policy affects a VO's Wi-Fi price but not the VO's advertising price. Moreover, we prove that a single term called equilibrium indicator determines whether a VO will fully rely on the premium access, or fully rely on the advertising sponsored access, or obtain revenue from both types of access. Numerical results show that the VO obtains a large revenue under a large advertising concentration level and a medium MU visiting frequency.
【Keywords】: IEEE 802.11 Standard; Advertising; Mobile communication; Games; Ecosystems; Cost accounting; Pricing
【Paper Link】 【Pages】:1-9
【Authors】: Matthew Andrews ; Yue Jin ; Martin I. Reiman
【Abstract】: We study the problem faced by a wireless service provider (SP) when offering a “sponsored content” service to multiple content providers (CPs). Each CP specifies the value that it would obtain from additional content views together with estimates on the underlying demand for its content. The SP then determines which CPs should sponsor their content along with the price for doing so. This basic framework has been studied in a variety of different contexts in recent years. However, previous work typically assumes that the CP parameters are reported truthfully to the SP. Another common assumption is that each CP has an independent traffic stream, i.e. there is no notion of competition between CPs in similar markets. In this work we address both of these issues. We present a pricing scheme that optimizes SP profit subject to CPs being incentivized to reveal their valuation and number of potential views in a truthful manner. We also examine how the model is affected if CPs in the same market are vying to sponsor a common pool of content.
【Keywords】: Pricing; Nickel; Wireless communication; Wireless sensor networks; Network neutrality; Data models; Adaptation models
【Paper Link】 【Pages】:1-9
【Authors】: Liang Zhang ; Weijie Wu ; Dan Wang
【Abstract】: Mobile data demand is increasing tremendously, and thus new pricing models are in urgent need. One promising new pricing scheme is the “sponsored data plan”, i.e., end users may enjoy free access to contents from certain content providers, while these content providers will pay ISPs for corresponding traffic consumed by end users. Proven a number of advantages, the sponsored data plan is still in its infancy. In this paper, we explore some potential of further development of this plan. We extend the design space and propose the idea of time-dependent, sponsoring, i.e, content providers can decide when to sponsor how much fractions of traffic. The key intuition is by migrating some traffic consumption from peak to valley times, bandwidth resources can be better utilized. We formulate a game model to study the interactions between the ISP, CPs and users, and derive the optimal sponsoring fractions over various times under this new plan. We show that all parties involved can benefit from this plan, and social welfare increases. We believe our proposal, i.e., time-dependent sponsoring, provides important insights to potential development of the sponsored data plan.
【Keywords】: Bandwidth; Internet; Wireless communication; Pricing; Data models; Biological system modeling; Games
【Paper Link】 【Pages】:1-9
【Authors】: Honghai Wu ; Liang Liu ; Xi Zhang ; Huadong Ma
【Abstract】: With the increasing popularity of video delivery among mobile users, the explosive traffic growth problem becomes more and more serious for the mobile wireless networks. We propose to exploit opportunistic transmission and the idea of crowdsourcing to offload mobile video traffic. Specifically, we propose a QoV (Quality of Video) oriented pricing incentive scheme, namely Vbargain, to stimulate mobile users to deliver video data collaboratively. In our scheme, the video packets are treated as commodities, which are dynamically priced according to their expected marginal gains on the quality of reconstructed video; the process of video delivery is regarded as a sequence of packet transactions which are modeled as two-person cooperative games. Our simulation results, based on both the synthetic and real-life traces of mobile users, verify the efficiency of our scheme.
【Keywords】: Mobile communication; Streaming media; Incentive schemes; Pricing; Mobile computing; Crowdsourcing; Mobile handsets
【Paper Link】 【Pages】:1-9
【Authors】: Quanquan Zhi ; Wei Xu
【Abstract】: Software-Defined Networks (SDN) greatly improves programmability but brings in extra challenges for debugging. We propose an SDN debugging framework, Monitor-Emulator-Debugger (MED). It closely monitors the physical network, and automatically creates an emulator that can be set to the network state at any given point of time. In the emulator, MED synchronously constructs a virtual SDN that is identical to the physical SDN and replays real packet samples. The emulator also handles the non-determinism due to packet reordering. On top of the emulator, we provide fast and efficient debugging tools including loop and reachability detector, race condition detector and forwarding table checker. All the tools run on the emulator without adding any additional overhead to the physical SDN. We implement MED for an OpenFlow-based SDN in a data center network employing 20 switches. Using a combination of micro-benchmarks and real debugging case studies, we show that MED is both fast and useful in SDN debugging. During the evaluation, we reveal two physical switch bugs that have been confirmed by the vendor.
【Keywords】: Monitoring; Debugging; Computer bugs; Control systems; Software; Production; Runtime
【Paper Link】 【Pages】:1-9
【Authors】: Yang Li ; Linh Thi Xuan Phan ; Boon Thau Loo
【Abstract】: Network functions are increasingly being commoditized as software appliances on off-the-shelf machines, popularly known as Network Functions Virtualization (NFV). While this trend provides economics of scale, a key challenge is to ensure that the performance of virtual appliances match that of hardware boxes. We present the design and implementation of NFV-RT, a system that dynamically provisions resources in an NFV environment to provide timing guarantees. Specifically, given a set of service chains that each consist of some network functions, NFV-RT aims at maximizing the total number of requests that can be assigned to the cloud for each service chain, while ensuring that the assigned requests meet their deadlines. Our approach uses a linear programming model with randomized rounding to efficiently and proactively obtain a near-optimal solution. Our simulation shows that, given a cloud with thousands of machines and service chains, NFV-RT requires only a few seconds to compute the solution, while accepting three times the requests compared to baseline heuristics. In addition, under some special settings, NFV-RT can provide significant performance improvement. Our evaluation on a local testbed shows that 94% of the packets of the submitted requests meet their deadlines, which is three times that of previous reactive-based solutions.
【Keywords】: Cloud computing; Switches; Timing; Virtual machine monitors; Real-time systems; Home appliances
【Paper Link】 【Pages】:1-9
【Authors】: Shaowei Wang ; Xinxin Huang
【Abstract】: Smart grid is characterized by a large number of smart meters (SMs) that exchange huge amounts of data with control center, where an effective communication network is required to guarantee reliable data transmission. In this paper, we introduce software defined network (SDN) technology to the smart grid, which decouples the control plane from the data plane so as to satisfy the communication requirements in the mart grid effectively. Aggregation points (APs) are employed in the data plane to process and forward data between SMs and control center. A general mathematical model is formulated to plan the APs, where we try to minimize the total deployment cost, including the opening expenditure of the APs, the connection cost between SMs and APs, and the connection cost between APs and control center. We present a 5-approximation algorithm to address the generated NP-hard problem, which yields performance-guaranteed solutions. Three representative scenarios are investigated to verity the efficiency of our proposal. Numerical results show that our proposed algorithm has great advantages over other heuristic ones.
【Keywords】: Smart grids; Planning; Relays; Communication systems; Optimization; Approximation algorithms; Attenuation
【Paper Link】 【Pages】:1-9
【Authors】: Tung-Wei Kuo ; Bang-Heng Liou ; Kate Ching-Ju Lin ; Ming-Jer Tsai
【Abstract】: Recently, Network Function Virtualization (NFV) has been proposed to transform from network hardware appliances to software middleboxes. Normally, a demand needs to invoke several Virtual Network Functions (VNFs) in a particular order following the service chain along a routing path. In this paper, we study the joint problem of VNF placement and path selection to better utilize the network. We discover that the relation between the link and server usage plays a crucial role in the problem. We first propose a systematic way to elastically tune the proper link and server usage of each demand based on network conditions and demand properties. In particular, we compute a proper routing path length, and decide, for each VNF in the service chain, whether to use additional server resources or to reuse resources provided by existing servers. We then propose a chain deployment algorithm to follow the guidance of this link and server usage. Via simulations, we show that our design effectively adapts resource usage to network dynamics, and, hence, serves more demands than other heuristics.
【Keywords】: Servers; Bandwidth; Silicon; Hardware; Routing; Algorithm design and analysis
【Paper Link】 【Pages】:1-9
【Authors】: Yan Liu ; Jack Y. B. Lee
【Abstract】: Mobile video streaming is one of the fastest growing applications in the mobile Internet. Nevertheless, delivering high-quality streaming video over mobile networks remains a challenge. Researchers have since developed various novel streaming algorithms such as rate-adaptive streaming to improve the performance of mobile streaming services. However, selection or optimization of streaming algorithms is far from trivial and there is no systematic way to incorporate the tradeoffs between various performance metrics. This work aims at attacking the heart of the problem by developing a novel framework called Post Streaming Quality Analysis (PSQA) to automatically tune any streaming algorithms to maximize a given quality-of-experience (QoE) objective. We show that PSQA not only can be applied to optimize the performance of existing streaming algorithms, but also opens a new way for the exploration of new adaptive video streaming protocols and QoE metrics. Simulation results based on real network throughput traces show that PSQA can optimize existing and new streaming algorithms to achieve QoE that is remarkably close to the optimal achieved using brute-force method ex post facto.
【Keywords】: Streaming media; Mobile communication; Algorithm design and analysis; Bit rate; Mobile computing; Throughput; Protocols
【Paper Link】 【Pages】:1-9
【Authors】: Eilwoo Baik ; Amit Pande ; Zizhan Zheng ; Prasant Mohapatra
【Abstract】: Synchronizing videos over file-hosting services on personal cloud such as Dropbox, Box or Onedrive leads to wastage in bandwidth and storage, which can be critical, while using mobile devices. Users can alternatively download the video on-the-go, but that leads to high latency, depending on network bandwidth and video file size. In contrast, adaptive video streaming allows near-real-time viewing by streaming the best possible quality in a given network condition. This feature is achieved by keeping multiple versions of video in cloud, leading to additional costs in cloud storage. Moreover, current solutions can only support a small set of bitrates, leading to abrupt switches in video resolution especially when the network condition is unstable, as often experienced by mobile users. This paper introduces Vsync, a framework for cloud based video synchronization for mobile devices. A video content is streamed using a cloud-based real-time transcoding and transmission framework to provide smooth video quality. Built over prediction models for video transcoding sessions and a QoE based adaptive video streaming protocol, Vsync is able to obtain the improvements of 37 ~ 80% than other compared schemes. The dataset and evaluation was done on a pool of 220K video clips.
【Keywords】: Streaming media; Transcoding; Cloud computing; Mobile handsets; Bandwidth; Real-time systems; Mobile communication
【Paper Link】 【Pages】:1-9
【Authors】: Chao Wu ; Xu Chen ; Yuezhi Zhou ; Ningyuan Li ; Xiaoming Fu ; Yaoxue Zhang
【Abstract】: Mobile online social networks (OSNs) are emerging as the popular mainstream platform for information and content sharing among people. In order to provide Quality of Experience (QoE) support for mobile OSN services, in this paper we propose a socially-driven learning-based framework, namely Spice, for media content prefetching to reduce the access delay and enhance mobile user's satisfaction. Through a large-scale data-driven analysis over real-life mobile Twitter traces from over 17,000 users during a period of five months, we reveal that the social friendship has a great impact on user's media content click behavior. To capture this effect, we conduct social friendship clustering over the set of user's friends, and then develop a cluster-based Latent Bias Model for socially-driven learning-based prefetching prediction. We then propose a usage-adaptive prefetching scheduling scheme by taking into account that different users may possess heterogeneous patterns in the mobile OSN app usage. We comprehensively evaluate the performance of Spice framework using trace-driven emulations on smartphones. Evaluation results corroborate that the Spice can achieve superior performance, with an average 67.2% access delay reduction at the low cost of cellular data and energy consumption. Furthermore, by enabling users to offload their machine learning procedures to a cloud server, our design can achieve speed-up of a factor of 1000 over the local data training execution on smartphones.
【Keywords】: Media; Prefetching; Mobile communication; Twitter; Mobile handsets; Servers; Delays
【Paper Link】 【Pages】:1-9
【Authors】: Hui Wang ; Wei Tsang Ooi ; Mun Choon Chan
【Abstract】: Wireless multicast has been exploited to bridge the gap between the limited wireless bandwidth and the rapidly increasing mobile video traffic demand. Multicast of videos to a set of heterogeneous users over multiple wireless access points, however, is challenging because of the trade-offs between high transmission rate, load balancing, and multicast opportunities. In this paper, we present JurCast, a joint user and rate allocation scheme for video multicast over multiple APs. Our approach balances the trade-off between these factors by determining user to Access Points (APs) association, the video resolution version (quality) to be delivered for each session, and the transmission link rate for each video version. The aim of our solution is to maximize the overall received video quality over all users. We have implemented and evaluated our solution on a WiFi testbed as well as the simulation of a large scale deployment. The results indicate that our method considerably outperforms the baseline schemes and achieves up to 3dB and 55% improvements in terms of peak signal-to-noise ratio (PSNR) and goodput, respectively.
【Keywords】: Streaming media; Wireless communication; IEEE 802.11 Standard; Mobile communication; Resource management; Bandwidth; Video recording
【Paper Link】 【Pages】:1-9
【Authors】: Lin Chen ; Yong Li ; Athanasios V. Vasilakos
【Abstract】: Neighbor discovery, the process of discovering all neighbors in a device's communication range, is one of the bootstrapping networking primitives of paramount importance and is particularly challenging when devices have directional antennas instead of omni-directional ones. In this paper, we study the following fundamental problem which we term as oblivious neighbor discovery: How can neighbor nodes with heterogeneous antenna configurations and without clock synchronization discover each other within a bounded delay in a fully decentralised manner without any prior coordination? We first establish a theoretical framework on oblivious neighbor discovery and establish the performance bound of any neighbor discovery protocol achieving oblivious discovery. Guided by the theoretical results, we then design an oblivious neighbor discovery protocol and prove that it achieves guaranteed oblivious discovery with order-minimal worst-case discovery delay in the asynchronous and heterogeneous environment. We further demonstrate how our protocol can be configured to achieve a desired trade-off between average and worst-case performance.
【Keywords】: Protocols; Delays; Directional antennas; Niobium; Directive antennas; Probabilistic logic
【Paper Link】 【Pages】:1-9
【Authors】: Tien Tran ; Min Kyung An ; Dung T. Huynh
【Abstract】: Consider a set S of nodes in the plane such that the unit-disk graph G(S) spanning all nodes is connected. Each node in S is equipped with a directional antenna with beam-width θ = π/2. The objective of the Directional Antenna Orientation (AO) problem concerning symmetric connectivity is to determine an orientation of the antennas with a minimum transmission power range r = O(1) such that the induced symmetric communication graph is connected. Another related problem is the Antenna Orientation and Power Assignment (AOPA) problem whose objective is to assign each node u ϵ S an orientation of its antenna as well as a range r(u) such that the induced symmetric communication graph is connected and the total power assigned ΣuϵSr(u)β is minimized, where β ≥ 1 is the distance-power gradient (typically 2 ≤ β ≤ 5). In this paper, we study both problems by first proving that they are NP-hard. To the best of our knowledge, these NP-hardness results have not been obtained before in the literature. We then propose an algorithm for the AO problem that orients the antennas to yield a symmetric connected graph where the transmission power range is bounded by 9 which is currently the best result for this problem. (Previous bound for this problem is 14√2 by Aschner et al). We also propose a constant-approximation algorithm for the AOPA problem where our constant is smaller than the one in Aschner et al's algorithm.
【Keywords】: Wireless sensor networks; Directional antennas; Broadcasting; Directive antennas; Computer science; Electronic mail
【Paper Link】 【Pages】:1-9
【Authors】: Seungmin Yoo ; Seongwon Kim ; Youngwook Son ; Jaehong Yi ; Sunghyun Choi
【Abstract】: Antenna selection, a cost-effective way to enhance network performance, has been employed in a limited manner in wireless local area networks (WLANs) due to the lack of channel information at the transmitter. In this paper, a practical antenna selection system without using channel information is proposed. We first describe the practical issues of antenna selection system for infrastructure-based WLANs, and then, analyze its characteristics through an extensive measurement study. Based on that, we propose antenna selection algorithms of access point (AP) for both (1) unicast transmission and (2) multicast transmission and reception. The proposed algorithms are comparatively evaluated using prototype implementation in a commercial AP. It is demonstrated that the proposed algorithms achieve up to 34% throughput gain and 54% frame error rate reduction for unicast and multicast transmissions, respectively.
【Keywords】: Transmitting antennas; Radio frequency; Wireless LAN; Antenna measurements; Signal to noise ratio; Unicast
【Paper Link】 【Pages】:1-9
【Authors】: Oscar Bejarano ; Roger Pierre Fabris Hoefel ; Edward W. Knightly
【Abstract】: In this paper we present the design of CHRoME, a downlink multi-user beamforming (MUBF) protocol that addresses the inherent sensitivity of multi-stream systems to mobility, inter-stream interference, and imperfect channel state information. Our contributions are: (i) a technique for accurately selecting the downlink bit rate in the presence of inter-stream interference via a custom multi-user probe and feedback signal, immediately preceding data transmission, and (ii) a fast retransmission scheme that exploits liberated antenna resources to increase the expected per-user signal-to-interference-plus-noise ratio (SINR) and retransmit without having to re-sound the channel. We implement each mechanism and evaluate via a combination of indoor over-the-air experiments and trace-driven emulation. We demonstrate that CHRoME increases the resilience of MUBF systems to inter-stream interference and achieves multi-fold throughput gains compared to IEEE 802.11ac.
【Keywords】: Interference; Signal to noise ratio; Cascading style sheets; Probes; Data communication; Array signal processing; Downlink
【Paper Link】 【Pages】:1-9
【Authors】: Jethro Tan ; Przemyslaw Pawelczak ; Aaron N. Parks ; Joshua R. Smith
【Abstract】: Computational RFID (CRFID) devices are emerging platforms that can enable perennial computation and sensing by eliminating the need for batteries. Although much research has been devoted to improving upstream (CRFID to RFID reader) communication rates, the opposite direction has so far been neglected, presumably due to the difficulty of guaranteeing fast and error-free transfer amidst frequent power interruptions of CRFID. With growing interest in the market where CRFIDs are forever-embedded in many structures, it is necessary for this void to be filled. Therefore, we propose Wisent - a robust downstream communication protocol for CRFIDs that operates on top of the legacy UHF RFID communication protocol: EPC C1G2. The novelty of Wisent is its ability to adaptively change the frame length sent by the reader, based on the length throttling mechanism, to minimize the transfer times at varying channel conditions. We present an implementation of Wisent for the WISP 5 and an off-the-shelf RFID reader. Our experiments show that Wisent allows transfer up to 16 times faster than a baseline, non-adaptive shortest frame case, i.e. single word length, at sub-meter distance. As a case study, we show how Wisent enables wireless CRFID reprogramming, demonstrating the world's first wirelessly reprogrammable (software defined) CRFID.
【Keywords】: Protocols; Radiofrequency identification; Wireless sensor networks; Data transfer; Wireless communication; Nonvolatile memory; Standards
【Paper Link】 【Pages】:1-9
【Authors】: Chuyu Wang ; Lei Xie ; Wei Wang ; Tao Xue ; Sanglu Lu
【Abstract】: In a number of RFID-based applications such as logistics monitoring, the RFID systems are deployed to monitor a large number of RFID tags. They are usually required to track the movement of all tags in a real-time approach, since the tagged-goods are moved in and out in a rather frequent approach. However, a typical cycle of tag inventory in COTS RFID system usually takes tens of seconds to interrogate hundreds of RFID tags. This hinders the system to track the movement of all tags in time. One critical issue in such type of tag monitoring is to efficiently distinguish the motion status of all tags, i.e., stationary or moving. According to the motion status of different tags, the state-of-art localization schemes can further track those moving tags, instead of tracking all tags. In this paper, we propose a real-time approach to detect the moving tags in the monitoring area, which is a fundamental premise to support tracking the movement of all tags. We achieve the time efficiency by decoding collisions from the physical layer. Instead of using the EPC ID, which cannot be decoded in collision slots, we are able to extract two kinds of physical-layer features of RFID tags, i.e., the phase profile and the backscatter link frequency, to distinguish among different tags in different positions. By resolving the two physical-layer features from the tag collisions, we are able to derive the motion status of multiple tags simultaneously, and greatly improve the time-efficiency. Experiment result shows that our solution can accurately detect the moving tags while reducing 80% of inventory time compared with the state-of-art solutions.
【Keywords】: Feature extraction; Monitoring; Tracking; Real-time systems; RFID tags; Backscatter
【Paper Link】 【Pages】:1-9
【Authors】: Xiulong Liu ; Keqiu Li ; Jie Wu ; Alex X. Liu ; Xin Xie ; Chunsheng Zhu ; Weilian Xue
【Abstract】: This paper studies the practically important problem of top-k queries, which is to find the top k largest categories and their corresponding sizes. In this paper, we propose a Top-k Query (TKQ) protocol and a technique that we call Segmented Perfect Hashing (SPH) for optimizing TKQ. Specifically, TKQ is based on the framed slotted Aloha protocol. Each tag responds to the reader with a Single-One Geometric (SOG) string using the ON-OFF Keying modulation. TKQ leverages the length of continuous leading 1s in the combined signal to estimate the corresponding category size. TKQ can quickly eliminate the sufficiently small categories, and only needs to focus on a limited number of large-size categories that require more accurate estimation. We conduct rigorous analysis to guarantee the predefined accuracy constraints. To further improve time-efficiency, we propose the SPH scheme, which improves the average frame utilization of TKQ from 36.8% to nearly 100% by establishing a bijective mapping between tag categories and slots. To minimize the overall time cost, we optimize the key parameter that trades off between communication cost and computation cost. Experimental results show that our TKQ+SPH protocol not only achieves the required accuracy constraints, but also achieves a 2.6~7x faster speed than the existing protocols.
【Keywords】: Protocols; Radiofrequency identification; Estimation; Computers; Servers; Sociology; Statistics
【Paper Link】 【Pages】:1-9
【Authors】: Yunfei Ma ; Edwin C. Kan
【Abstract】: Extremely low-cost passive RFID tags have become key components for the Internet of Things (IoT), where ubiquitous object locating is one of the most important functions. Although the number of tags in indoor environment continues growing fast, objects cannot be always assumed tagged, whether intentionally or unintentionally. Compared to tagged objects, a tagless target which neither emits nor modulates signal is much more difficult to locate, especially when the size is small. In this paper, we achieve accurate tagless object locating through a dense and wide non-uniform sampling in the Fourier domain of target reflectivity with the help of ambient passive RFID tags as landmarks. Unlike conventional RFID systems, we leverage nonlinearity in passive tags to backscatter second harmonic signals. The frequency separation of uplink and downlink in harmonic RFID allows ready interference cancellation. We embrace spatial diversity enabled by ambient tags and frequency diversity by broadband harmonic backscattering to improve accuracy and robustness. We present the fundamental theory and a prototype system to verify the proposed approach.
【Keywords】: Harmonic analysis; Reflectivity; Backscatter; Broadband antennas; Broadband communication; Passive RFID tags; Receiving antennas
【Paper Link】 【Pages】:1-9
【Authors】: Jianwei Qian ; Xiang-Yang Li ; Chunhong Zhang ; Linlin Chen
【Abstract】: Social network data is widely shared, transferred and published for research purposes and business interests, but it has raised much concern on users' privacy. Even though users' identity information is always removed, attackers can still de-anonymize users with the help of auxiliary information. To protect against de-anonymization attack, various privacy protection techniques for social networks have been proposed. However, most existing approaches assume specific and restrict network structure as background knowledge and ignore semantic level prior belief of attackers, which are not always realistic in practice and do not apply to arbitrary privacy scenarios. Moreover, the privacy inference attack in the presence of semantic background knowledge is barely investigated. To address these shortcomings, in this work, we introduce knowledge graphs to explicitly express arbitrary prior belief of the attacker for any individual user. The processes of de-anonymization and privacy inference are accordingly formulated based on knowledge graphs. Our experiment on data of real social networks shows that knowledge graphs can strengthen de-anonymization and inference attacks, and thus increase the risk of privacy disclosure. This suggests the validity of knowledge graphs as a general effective model of attackers' background knowledge for social network privacy preservation.
【Keywords】: Privacy; Social network services; Knowledge engineering; Data privacy; Data models; Publishing; Remuneration
【Paper Link】 【Pages】:1-9
【Authors】: Christopher G. Brinton ; Swapna Buccapatnam ; Felix Ming Fai Wong ; Mung Chiang ; H. Vincent Poor
【Abstract】: A Social Learning Network (SLN) emerges when users exchange information on educational topics with structured interactions. The recent proliferation of massively scaled online (human) learning, such as Massive Open Online Courses (MOOCs), has presented a plethora of research challenges surrounding SLN. In this paper, we ask: How efficient are these networks? We propose a framework in which SLN efficiency is determined by comparing user benefit in the observed network to a benchmark of maximum utility achievable through optimization. Our framework defines the optimal SLN through utility maximization subject to a set of constraints that can be inferred from the network. Through evaluation on four MOOC discussion forum datasets and optimizing over millions of variables, we find that SLN efficiency can be rather low (from 68% to 82% depending on the specific parameters and dataset), which indicates that much can be gained through optimization. We find that the gains in global utility (i.e., average across users) can be obtained without making the distribution of local utilities (i.e., utility of individual users) less fair. We also discuss ways of realizing the optimal network in practice, through curated news feeds in online SLN.
【Keywords】: Optimization; Education; Discussion forums; Inference algorithms; Feeds; Distance measurement; Social network services
【Paper Link】 【Pages】:1-9
【Authors】: Jie Cheng ; Yangyang Zhang ; Qiang Ye ; Hongwei Du
【Abstract】: Over the past decades, many large-scale social network systems, such as Facebook and Twitter, have been deployed in different countries. How to efficiently analyze the topological characteristics of large-scale social networks has been a challenging problem in the research community. One of the critical topological characteristics is the shortest distance between two nodes in a network. The existing shortest distance algorithms, such as Breadth First Search (BFS), work well with small networks. For a network with billions of nodes, calculating the pairwise shortest distances with these algorithms requires an overlong period of time. In this paper, we present a high-precision ShOrtest Distance Approximation (SODA) scheme, which utilizes a small set of pre-calculated distances to estimate the shortest distance between each pair of nodes in large-scale social networks. Compared with the existing shortest distance estimation schemes for social networks, SODA leads to high estimation accuracy since it utilizes a novel optimization method, Robust Discrete Matrix Decomposition (RDMD), to eliminate the impact of significant errors/outliers and generate the coordinates of the nodes in a network simultaneously. In addition, SODA differentiates the asymmetric distances in directed graphs. Consequently, SODA works well with both directed and undirected social networks. Finally, SODA only involves convex optimization. Therefore, SODA is highly competitive in terms of computation complexity. Our experimental results indicate that SODA outperforms the state-of-the-art shortest distance estimation schemes in terms of estimation accuracy and running time.
【Keywords】: Estimation; Robustness; Matrix decomposition; Facebook; Twitter; Principal component analysis
【Paper Link】 【Pages】:1-9
【Authors】: Dong Wang ; Zhenyu Li ; Gaogang Xie ; Mohamed Ali Kâafar ; Kavé Salamatian
【Abstract】: In Search Engine Marketing (SEM), “third-party” partners play an important intermediate role by bridging the gap between search engines and advertisers in order to optimise advertisers' campaigns in exchange of a service fee. In this paper, we present an economic analysis of the market involving a third-party broker in Google AdWords and the broker's customers. We show that in order to optimise his profit, a third-party broker should minimise the weighted average Cost Per Click (CPC) of the portfolio of keywords attached to customer's ads while still satisfying the negotiated customer's demand. To help the broker build and manage such portfolio of keywords, we develop an optimisation framework inspired from the classical Markowitz portfolio management which integrates the customer's demand constraint and enables the broker to manage the tradeoff between return on investment and risk through a single risk aversion parameter. We then propose a method to augment the keywords portfolio with relevant keywords extracted from trending and popular topics on Twitter. Our evaluation shows that such a keywords-augmented strategy is very promising and enables the broker to achieve, on average, four folds larger return on investment than with a non-augmented strategy, while still maintaining the same level of risk.
【Keywords】: Portfolios; Google; Search engines; Twitter; Contracts; Elasticity; Optimization
【Paper Link】 【Pages】:1-9
【Authors】: Jialong Zhang ; Xin Hu ; Jiyong Jang ; Ting Wang ; Guofei Gu ; Marc Ph. Stoecklin
【Abstract】: Nowadays, cyber criminals often build web infrastructures rather than a single server to conduct their malicious activities. In order to continue their malevolent activities without being detected, cyber criminals make efforts to conceal the core servers (e.g., C&C servers, exploit servers, and drop-zone servers) in the malicious web infrastructure. Such deliberate invisibility of those concealed malicious servers, however, makes them particularly distinguishable from benign web servers that are usually promoted to be public. In this paper, we conduct the first large-scale measurement study to investigate the visibility of both malicious and benign servers. From our intensive analysis of over 100,000 benign servers, 45,000 malicious servers and 40,000 redirections, we identify a set of distinct features of malicious web infrastructures from their locations, structures, roles, and relationships perspectives, and propose a lightweight yet effective detection system called VisHunter. VisHunter identifies malicious redirections from visible servers to invisible servers at the entryway of malicious web infrastructures. We evaluate VisHunter on both online public data and large-scale enterprise network traffic, and demonstrate that VisHunter can achieve an average 96.2% detection rate with only 0.9% false positive rate on the real enterprise network traffic.
【Keywords】: Search engines; Superluminescent diodes; Feature extraction; Web servers; Malware; Indexes
【Paper Link】 【Pages】:1-9
【Authors】: Yue Li ; Haining Wang ; Kun Sun
【Abstract】: Though not recommended, Internet users often include parts of personal information in their passwords for easy memorization. However, the use of personal information in passwords and its security implications have not yet been studied systematically in the past. In this paper, we first dissect user passwords from a leaked dataset to investigate how and to what extent user personal information resides in a password. In particular, we extract the most popular password structures expressed by personal information and show the usage of personal information. Then we introduce a new metric called Coverage to quantify the correlation between passwords and personal information. Afterwards, based on our analysis, we extend the Probabilistic Context-Free Grammars (PCFG) method to be semantics-rich and propose Personal-PCFG to crack passwords by generating personalized guesses. Through offline and online attack scenarios, we demonstrate that Personal-PCFG cracks passwords much faster than PCFG and makes online attacks much easier to succeed.
【Keywords】: Measurement; Correlation; Authentication; Dictionaries; Semantics; Electronic mail
【Paper Link】 【Pages】:1-9
【Authors】: Xiang-Yang Li ; Chunhong Zhang ; Taeho Jung ; Jianwei Qian ; Linlin Chen
【Abstract】: We propose a graph-based framework for privacy preserving data publication, which is a systematic abstraction of existing anonymity approaches and privacy criteria. Graph is explored for dataset representation, background knowledge specification, anonymity operation design, as well as attack inferring analysis. The framework is designed to accommodate various datasets including social networks, relational tables, temporal and spatial sequences, and even possible unknown data models. The privacy and utility measurements of the anonymity datasets are also quantified in terms of graph features. Our experiments show that the framework is capable of facilitating privacy protection by different anonymity approaches for various datasets with desirable performance.
【Keywords】: Data privacy; Privacy; Data models; Semantics; Social network services; Measurement; Correlation
【Paper Link】 【Pages】:1-9
【Authors】: Shouling Ji ; Weiqing Li ; Shukun Yang ; Prateek Mittal ; Raheem A. Beyah
【Abstract】: In this paper, we propose a structural importance-aware approach to quantify the vulnerability/de-anonymizability of graph data to structure-based De-Anonymization (DA) attacks [1][2][3][4]. Specifically, we quantify both the seed-based and the seed-free Relative De-anonymizability (RD) of graph data for both perfect DA (successfully de-anonymizing all the target users) and partial DA (where some DA error is tolerated) under a general data model. In our relative quantification, instead of treating all the users in graph data as structurally equivalent, we adaptively quantify their RD in terms of their structural importance. Leveraging 15 real world graph datasets, we validate the accuracy of our relative quantifications and compare them with state-of-the-art seed-based and seed-free quantification techniques. The results demonstrate that our structural importance-aware relative quantifications are more sound and precise when measuring graph data's real vulnerability/de-anonymizability.
【Keywords】: Data models; Erbium; Government; Facebook; Computers; Medical services
【Paper Link】 【Pages】:1-9
【Authors】: Bo Gao ; Sudeep Bhattarai ; Jung-Min "Jerry" Park ; Yaling Yang ; Min Liu ; Kexiong Curtis Zeng ; Yanzhi Dou
【Abstract】: The legacy concept of exclusion zones (EZs) is inept at enabling efficient utilization of fallow spectrum by secondary users (SUs), since legacy EZs are static and overly-conservative. The notion of a static EZ implies that it has to protect incumbent users (IUs) from the union of likely interference scenarios, leading to a worst-case, conservative solution. In this paper, we propose the concept of dynamic, multi-tier EZs, which takes advantage of participatory spectrum sensing carried out by SUs to support efficient database-driven spectrum sharing while protecting IUs against SU-induced aggregate interference. Specifically, the database directly incentivizes SUs to participate in spectrum sensing, which augments geolocation database by defining smaller EZs with dynamic boundaries and creating additional spectrum access opportunities for SUs. We propose an incentive mechanism based on a two-level game-theoretic model, in which the database conducts dynamic pricing in a first-level Stackelberg game in the presence of SUs who strategically contribute to spectrum sensing in a second-level stochastic game. The existence of an equilibrium solution is proven. According to our findings, the proposed incentive mechanism for the concept of dynamic, multi-tier EZs is effective to improve spectrum utilization efficiency while guaranteeing incumbent protection.
【Keywords】: Sensors; Databases; Interference; White spaces; Aggregates; Geology; Pricing
【Paper Link】 【Pages】:1-9
【Authors】: Matthew A. Clark ; Konstantinos Psounis
【Abstract】: In an effort to meet growing demands on the radio frequency spectrum, regulators are exploring methods to enable band sharing among a diverse set of user devices. Proposed spectrum access systems would dynamically assign spectrum resources to users, maintaining databases of spectrum use information. While these systems are anticipated to increase the efficiency of spectrum sharing, incumbent users have raised concerns about exposing details of their operations and have questioned whether their privacy can be protected. In this paper, we explore whether primary users can retain a critical level of privacy when a system uses their information to enable dynamic access to the spectrum by other users. Under a variety of operational scenarios and user models, we examine adversary techniques to exploit the spectrum access system and obfuscation strategies to protect user privacy. We also develop analytical methods to quantify the performance of both the adversary and obfuscation strategies. To our knowledge, this is the first work that considers the privacy of a primary user in the setting of a highly dynamic spectrum access system. Privacy analysis of this kind will help to enable adoption of shared spectrum access systems by allowing incumbent users to quantify and mitigate risks to their privacy.
【Keywords】: Privacy; Interference; Databases; Data privacy; Analytical models; White spaces; TV
【Paper Link】 【Pages】:1-9
【Authors】: Xiaocong Jin ; Yanchao Zhang
【Abstract】: Crowdsourced spectrum sensing has great potential in improving current spectrum database services. Without strong incentives and location privacy protection in place, however, mobile users will be reluctant to act as mobile crowdsourcing workers for spectrum sensing tasks. In this paper, we present PriCSS, the first framework for a crowdsourced spectrum sensing service provider to select spectrum-sensing participants in a differentially privacy-preserving manner. Thorough theoretical analysis and simulation studies show that PriCSS can simultaneously achieve differential location privacy, approximate social cost minimization, and truthfulness.
【Keywords】: Sensors; Databases; Privacy; Mobile communication; Cascading style sheets; Crowdsourcing; Mobile handsets
【Paper Link】 【Pages】:1-9
【Authors】: Zhangyu Guan ; Tommaso Melodia
【Abstract】: To cope with the increasing scarcity of spectrum resources, researchers have been working to extend LTE/LTE-A cellular systems to unlicensed bands, leading to so-called unlicensed LTE (U-LTE). However, this extension is by no means straightforward, primarily because the radio resource management schemes used by LTE and by systems already deployed in unlicensed bands are incompatible. Specifically, it is well known that coexistence with scheduled systems like LTE degrades considerably the throughput of Wi-Fi networks that are based on carrier-sense medium access schemes. To address this challenge, we propose for the first time a cognitive coexistence scheme to enable spectrum sharing between U-LTE and Wi-Fi networks, referred to as CU-LTE. The proposed scheme is designed to jointly determine dynamic channel selection, carrier aggregation and fractional spectrum access for U-LTE networks, while guaranteeing fair spectrum access for Wi-Fi based on a newly designed cross-technology fairness criterion. We first derive a mathematical model of the spectrum sharing problem for the coexisting networks; we then design a solution algorithm to solve the resulting fairness constrained mixed integer nonlinear optimization problem. The algorithm, based on a combination of branch and bound and convex relaxation techniques, maximizes the network utility with guaranteed optimality precision that can be set arbitrarily to 1 at the expense of computational complexity. Performance evaluation indicates that near-optimal spectrum access can be achieved with guaranteed fairness between U-LTE and Wi-Fi. Issues regarding implementation of CU-LTE are also discussed.
【Keywords】: IEEE 802.11 Standard; Computer architecture; Throughput; Algorithm design and analysis; Interference; Mathematical model; Optimization
【Paper Link】 【Pages】:1-9
【Authors】: Chunyi Peng ; Yuanjie Li ; Zhuoran Li ; Jie Zhao ; Jiaqi Xu
【Abstract】: Femtocells (small cells) augment the current mobile network by providing users short-range radio access at home and small-business settings. They have rapidly emerged as a promising scheme to alleviate capacity and coverage shortage by offloading traffic from the conventional Macrocells (large cells). Despite its increasing popularity, the real-world Femtocell performance has remained largely unexplored. In this paper, we conduct an in-depth study to assess Femtocell performance and diagnose identified issues in operational carrier networks. We focus on user-deployed Femtocells in a top-tier US mobile network. While the Femtocell generally works well, unanticipated performance degradations and even failures still occur. Contrary to conventional wisdom in the research community, we find that, radio link quality and interference is not the main bottleneck of Femtocells in many real-life usage scenarios. For instance, while Femtocell deployment at blind-zones with no radio coverage is desirable, not all deployments have succeeded; Compared with their Macrocell counterparts, Femtocells exhibit lower speed and larger speed variations, and induce larger delay for data services. Moreover, mobility support for femtocells is incomplete and no seamless migration is available under certain usage scenarios. We pinpoint their root causes, quantify the potential impacts, and share the learned lessons.
【Keywords】: Macrocell networks; Mobile computing; Buildings; Internet; Access control; Context
【Paper Link】 【Pages】:1-9
【Authors】: Paul Schmitt ; Daniel Iland ; Mariya Zheleva ; Elizabeth M. Belding
【Abstract】: While cellular networks connect over 3.7 billion people worldwide, their availability and quality is not uniform across regions. Under-provisioned and overloaded networks lead to poor network performance and an aggravated user experience. To address this problem we propose HybridCell: a system that leverages locally-owned small-scale cellular networks to augment the operation of overloaded commercial networks. HybridCell is the first system to allow a user with their existing SIM card and mobile phone to seamlessly switch between commercial and local networks in order to maintain continuous connectivity. Hybrid-Cell accomplishes this by identifying poorly-performing networks and taking action to provide seamless cellular connectivity to end users. Using traces collected from observing the cellular infrastructure during our visit to the Za'atari refugee camp in Jordan, we demonstrate HybridCell's capability to detect and act upon commercial network overload, offering an alternate communication channel during times of congestion. We show that even in scenarios where provider networks deny calls due to overload, HybridCell is able to accommodate users and facilitate local calling.
【Keywords】: Base stations; GSM; Access control; Sociology; Statistics; Reliability; Gaussian noise
【Paper Link】 【Pages】:1-9
【Authors】: Wei Bao ; Ben Liang
【Abstract】: User-centric base station (BS) cooperation has been regarded as an effective solution to improve network coverage and throughput in next-generation wireless systems. However, it also introduces more complicated handoff patterns, which may potentially degrade user performance. In this paper, we aim to quantify the number of handoffs in user-centric cooperative wireless networks. The challenges are two-fold: (1) BSs are spatially randomly deployed, and (2) user-centric BS cooperation further creates complicated network topologies so that it is difficult to track handoffs in the system. We propose a stochastic geometric analysis framework on user mobility, to derive a theoretical expression for the handoff rate experienced by an active user with arbitrary movement trajectory. Furthermore, we characterize the average downlink user data rate under a common non-coherent joint-transmission scheme, which is used to illustrate the tradeoff between handoff rate and data rate in optimizing the cooperative cluster size for each user. Finally, computer simulation is conducted to validate the correctness and usefulness of our analysis.
【Keywords】: Wireless networks; Trajectory; Interference; Analytical models; Stochastic processes; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Junse Lee ; Xinchen Zhang ; François Baccelli
【Abstract】: The Poisson building features a Poisson collection of random planes orthogonal to the axes of the 3-D Euclidean space. It divides the space into rectangular rooms of random sizes. The addition of wireless small cell base stations, deployed as Poisson point processes along the ceiling and corner lines of these rooms, provides a first stochastic geometric model representing in-building 3-D wireless networks. The main challenge for analyzing interference in such an environment is the fact that electromagnetic signals originating from different locations are blocked by common obstacles like walls and floors, which makes the path loss highly correlated in space. We propose a natural propagation model taking this phenomenon into account. We give analytical expressions for the interference field and its correlation within this framework. We illustrate the tractability of this model by providing analytical expressions for the spectral efficiency of the downlink in such indoor cellular networks and for D2D communications in such an environment. We combine the model and spatial simulations to show that classical 2-D and distance based attenuation models cannot be used in this context and to argue for the need of such 3-D models to assess the performance of this type of indoor communications.
【Keywords】: Buildings; Solid modeling; Interference; Mathematical model; Analytical models; Shadow mapping; Context modeling
【Paper Link】 【Pages】:1-9
【Authors】: Behnam Dezfouli ; Marjan Radi ; Octav Chipara
【Abstract】: In this paper we consider the problem of supporting real-time communication in mobile networks. To address this challenge, we propose novel transmission scheduling techniques that handle the routing uncertainty introduced by mobility. The core of the scheduling techniques involves controlling the order in which transmissions are scheduled and intelligently scheduling multiple transmissions in a single entry of the scheduling matrix without conflict. Flow-Ordered Mobility-Aware Real-time Scheduling (FO-MARS) integrates these techniques to provide a 14x increase in real-time capacity compared to the baseline algorithms designed for static real-time networks. Additionally, we propose Additive Mobility-Aware Real-time Scheduling (A-MARS), which can handle network dynamics such as the addition or removal of flows without having to reschedule previously admitted flows. As a result, A-MARS achieves significantly lower admission latency than that of the baselines.
【Keywords】: Mobile nodes; Real-time systems; Schedules; Processor scheduling; Dynamic scheduling
【Paper Link】 【Pages】:1-9
【Authors】: Jaewook Kwak ; Do Young Eun
【Abstract】: In recent years, a suite of Glauber dynamics-based CSMA algorithms have attracted great attention due to their simple, distributed implementations with guaranteed throughput-optimality. However, these algorithms often suffer from poor delay performance and the starvation problem. Among several attempts to improve the delay performance, a remarkable improvement has recently been made in a class of CSMA algorithms that utilize multiple instances of the algorithm (or Markov chains). In this paper, we develop a new approach via an antithetic coupling (AC) method, which can further improve the delay performance of those that virtually emulate multiple chains. The key enabler of utilizing AC method lies in our skilful choice of manipulating the driving sequences of random variables that govern the evolution of schedule instances, in such a way that those multiple instances of chains become negatively correlated as oppose to having them run independently. This contributes faster change of the link state, rendering it more like a periodic process and thus leading to better queueing performance. We rigorously establish an ordering relationship for the effective bandwidth of each net-input process to the queue, between our proposed algorithm (AC-CSMA) and other state-of-the-art existing algorithms in the literature, under a mild set of assumptions. The proposed algorithm involves very simple modification onto existing CSMA-based algorithms, and can be implemented in a fully distributed manner without any additional message overhead. Our extensive simulation results also confirm that AC-CSMA always delivers better queueing performance over a variety of network scenarios.
【Keywords】: Multiaccess communication; Schedules; Heuristic algorithms; Delays; Scheduling algorithms; Couplings; Markov processes
【Paper Link】 【Pages】:1-9
【Authors】: Zaixin Lu ; Weili Wu ; Wei Wayne Li ; Miao Pan
【Abstract】: On-demand wireless data broadcast is an efficient way to disseminate data to a large number of mobile users. In many applications, such as stock quotes and flight schedules, users may have to download multiple data items per request. However the multi-item request scheduling has not yet been thoroughly investigated for on-demand wireless data broadcasts. In this paper, we step-up on investigating this problem from viewpoint of theory and simulation. We develop a two-stage scheduling scheme to arrange the requested data items with the objective of minimizing the average access latency. The first stage is to select the data items to be broadcast in the next time period and the second stage is to schedule the broadcasting order for the data items selected in the first stage. We develop algorithms for the two stages respectively and analyze them both theoretically and practically. We also compare the proposed algorithms with other well known scheduling methods through simulation. The theoretical findings and simulation results reveal that significantly better access latency can be obtained by using our scheduling scheme rather than its competitors.
【Keywords】: Wireless communication; Scheduling; Broadcasting; Schedules; Throughput; Heuristic algorithms; Data models
【Paper Link】 【Pages】:1-7
【Authors】: XiaoHua Xu ; Min Song
【Abstract】: Given a set of communication links in cognitive radio networks, assume that the underlying channel state information along each link is unknown; however, we can estimate it by exploiting the feedbacks and evolutions of channel states. Assume time is divided into time-slots. Under the protocol interference model, the opportunistic spectrum scheduling problem aims to select interference-free links to transmit at each time-slot to maximize the average throughput over the long time horizon. Existing works on the opportunistic spectrum scheduling problem cannot satisfyingly address the wireless interference constraints. We apply the framework of restless multi-armed bandit and develop approximation algorithms for the problem with stochastic identical links and nonidentical links respectively. Based on the updated estimations of channel states, the proposed algorithms keep refining future link scheduling decisions. We also obtain approximation bounds of these two proposed algorithms.
【Keywords】: Interference; Approximation algorithms; Scheduling; Protocols; Stochastic processes; Throughput; Wireless communication
【Paper Link】 【Pages】:1-9
【Authors】: Ralf Lübben ; Markus Fidler
【Abstract】: Closed-loop flow control protocols, such as the prominent implementation TCP, are prevalent in the Internet, today. TCP has continuously been improved for greedy traffic sources to achieve high throughput over networks with large bandwidth delay products. Recently, the increasing use for streaming and interactive applications, such as voice and video, has shifted the focus towards its delay performance. Given the need for real-time communication of non-greedy sources via TCP, we present an estimation method for performance evaluation of closed-loop flow control protocols. We characterize an end-to-end connection by a transfer function that provides statistical service guarantees for arbitrary traffic. The estimation is based on end-to-end measurements at the application level, that include all effects induced by the network and by the protocol stacks of the end systems. From our measurements, we identify different causes for delays. We show that significant delays are due to queueing in protocol stacks. Notably, this occurs even if the utilization is moderate. Using our estimation method, we compare the impact of fundamental mechanisms of TCP. In detail, we analyze buffer provisioning and its impact on delays at the application level. We find that a good selection can largely improve the delay performance of TCP.
【Keywords】: Delays; Protocols; Throughput; Estimation; Receivers; Bandwidth; Internet
【Paper Link】 【Pages】:1-9
【Authors】: Simone Ferlin ; Özgü Alay ; Thomas Dreibholz ; David A. Hayes ; Michael Welzl
【Abstract】: Multipath TCP (MPTCP) enables the simultaneous use of multiple links for bandwidth aggregation, better resource utilization and improved reliability. Its coupled congestion control intends to reap the increased bandwidth of multiple links, while avoiding being more aggressive than regular TCP flows on every used link. We argue that this leads to a very conservative behavior when paths do not share a bottleneck. Therefore, in this paper, we first quantify the penalty of the coupled congestion control for links that do not share a bottleneck. Then, in order to overcome this penalty, we design and implement a practical shared bottleneck detection (SBD) algorithm for MPTCP, namely MPTCP-SBD. Through extensive emulations, we show that MPTCP-SBD outperforms all currently deployed MPTCP coupled congestion controls by accurately detecting bottlenecks. For the non-shared bottleneck scenario, we observe throughput gains of up to 40% with two subflows and the gains increase significantly as the number of subflows increase, reaching more than 100% for five subflows. Furthermore, for the shared bottleneck scenario, we show that MPTCP-SBD remains fair to TCP. We complement the emulation results with real-network experiments justifying its safeness for deployment.
【Keywords】: Throughput; Delays; Internet; Linux; Servers; Algorithm design and analysis; Reactive power
【Paper Link】 【Pages】:1-9
【Authors】: Yang Zhang ; Hesham Mekky ; Zhi-Li Zhang ; Fang Hao ; Sarit Mukherjee ; T. V. Lakshman
【Abstract】: Multipath TCP (MPTCP) is a promising technique for boosting application throughput while using well-known and versatile network socket interfaces. Recently, many interesting applications of MPTCP in various environments such as wireless networks and data centers have been proposed, but little work has been done to investigate the impact of this protocol on conventional network devices. For example, MPTCP throughput advantage can be better achieved if all MPTCP subflows are routed on disjoint paths, but this is currently not feasible since routers are not designed to recognize the membership of MPTCP subflows. In this paper, we take a first step to address this issue by proposing SAMPO, an online algorithm to detect and associate MPTCP subflows in network. The main challenge is that sampling techniques and network dynamics may cause a network device to only obtain partial flow records. SAMPO takes advantage of both protocol information and statistical characteristics of MPTCP data sequence number to overcome the challenge in network. Through analysis and experimentation, we show that SAMPO is able to detect and associate MPTCP subflows with high accuracy even when a small portion of the entire flow records are available.
【Keywords】: Receivers; Algorithm design and analysis; Monitoring; Throughput; Sockets; Routing protocols
【Paper Link】 【Pages】:1-9
【Authors】: Mohan Kumar ; Ada Gavrilovska
【Abstract】: To achieve scalable, high-throughput, low-latency packet processing, TCP implementations are parallelized across cores in multicore platforms. This, however, significantly affects the order in which packets from different flows are delivered to application processing. Our measurements record up to 75% of the packets are delivered to applications in a way that does not match the order in which they are received on the network interface. For many important classes of applications, such as financial services, bidding and trading engines, game engines, this cross-flow packet reordering affects their ability to provide fairness guarantees. To address this gap, we propose TCP-Ordo - a TCP stack which provides strict ordering of packets across multiple flows, as well as flexibility to control the degree to which ordering is enforced. TCP-Ordo outperforms existing TCP implementations in both latency and throughput. The current prototype is implemented as a user-level TCP stack for Mellanox Connectx3 NICs with 40Gbps Ethernet interfaces. Without ordering guarantees TCP-Ordo delivers one way latency of 4.75usec (a 5x improvement over the Linux kernel) for 150B packets and throughput of 22Gbps (a 2x improvement over mTCP) for 1500B packets. Furthermore, with TCP-Ordo applications are provided with strict packet order delivery, with performance that continues to be superior to the state-of-the-art, even when enforcing packet order across 800,000 connections on a 12-core platform. Finally, TCP-Ordo supports the notion of `ordered domains' that offer flexibility in the degree of ordering that an application will experience, and pay for.
【Keywords】: Throughput; Servers; Kernel; Sockets; Engines; Multicore processing; Linux
【Paper Link】 【Pages】:1-9
【Authors】: Jianhua Sun ; Kun Sun
【Abstract】: Sophisticated adversaries usually initiate their attacks with a reconnaissance phase to discover exploitable vulnerabilities on the targeted networks and systems. To mitigate the effectiveness of persistent reconnaissance attacks, we develop a defensive mechanism that dynamically mutates network topology with a large number of decoys to invalidate the attacker's knowledge from network scanning. We combine the IP randomization technique with decoy techniques and solve two challenges, namely, service availability to legitimate users and service security against unauthorized users. First, our solution can minimize the probability of the real servers being identified and compromised by unauthorized users through deploying a large number of decoy nodes, which change their IP addresses along with the real servers to prolong the scanning time of the attackers. Second, our solution can ensure seamless connection migration so that all existing communication connections between the legitimate users and the servers are always kept alive even after the servers migrate to different IP addresses multiple times. We implement a virtual machine based system prototype and evaluate it using state-of-the-art scanning techniques. Both theoretical analysis and experimental results show that our solution can effectively mitigate network reconnaissance attacks without sacrificing service availability.
【Keywords】: Servers; IP networks; Authentication; Reconnaissance; Probes; Generators; Network topology
【Paper Link】 【Pages】:1-9
【Authors】: Jie Wang ; Wenye Wang
【Abstract】: In an era of networks in which any individual is connected with one another, such as Internet of Things (IoT) and Online Social Networks (OSNs), the networks are evolving into complex systems, carrying a huge volume of information that may provoke even more. An interesting, yet challenging question is how such information dissemination evolves, that is, to continue or to stop. Specifically, we aim to find out the aftermath of epidemic spreading via individuals and conflicting information dissemination. From a holistic, networking view, it is impossible to take every aspect into accounts for complex networks toward these questions. Therefore, we establish a Susceptible-Infectious-Cured (SIC) propagation model to examine two simple network topologies, clique and star, in terms of extinction time and half-life time of information under controllable, epidemic dynamics. For a network of size n, both theoretical and numerical results suggest that extinction time and half-life time are O(log n/n) for clique networks, and O(log n) for star networks. More interestingly, given an initial network state I0, the extinction time is constant (O(1)) for cliques, and O(log I0) for stars; while the half-life time is O(log 1/I0) for both clique and star networks, respectively. In addition, we developed a method to estimate the conditional infection count distribution, which indicates the scope of information dissemination.
【Keywords】: Silicon carbide; Numerical models; Sociology; Statistics; Silicon; Mathematical model; Immune system
【Paper Link】 【Pages】:1-9
【Authors】: Fabio Cecchi ; Sem C. Borst ; J. S. H. van Leeuwaarden ; Philip A. Whiting
【Abstract】: With the rapid advance of the Internet of Everything, both the number of devices and the range of applications that rely on wireless connectivity show huge growth. Driven by these pervasive trends, wireless networks grow in size and complexity, supporting immense numbers of nodes and data volumes, with highly diverse traffic profiles and performance requirements. While well-established methods are available for evaluating the throughput of persistent sessions with saturated buffers, these provide no insight in the delay performance of flows with intermittent packet arrivals. The occurrence of empty buffers in the latter scenario results in a complex interaction between activity states and packet queues, which severely complicates the performance analysis. Motivated by these challenges, we develop a mean-field approach to analyze buffer contents and packet delays in wireless networks in a many-sources regime. The mean-field behavior simplifies the analysis of a large-scale network with packet arrivals and buffer dynamics to a low-dimensional fixed-point calculation for a network with saturated buffers. In particular, the analysis yields explicit expressions for the buffer content and packet delay distribution in terms of the fixed-point solution. Extensive simulation experiments demonstrate that these expressions provide highly accurate approximations, even for a fairly moderate number of sources.
【Keywords】: Interference; Multiaccess communication; Delays; Wireless networks; Algorithm design and analysis; Asymptotic stability; Stability analysis
【Paper Link】 【Pages】:1-9
【Authors】: Yuexuan Wang ; Dongxiao Yu ; Qipeng Liu ; Francis C. M. Lau
【Abstract】: We study distributed algorithms for achieving efficient communications in the Rayleigh-fading Model. This model extends the popular deterministic SINR model using stochastic propagation to address fading effects observed in reality. Stochastic propagation greatly increases the difficulty of dealing with interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving algorithms for implementing two basic communication primitives. The first primitive is Local Broadcast (LB), which can work in a MAC layer and has been widely studied in different interference models. The proposed algorithm for LB matches the fastest one under the simpler SINR model. The second primitive is Single-Reception (SR), which is to make each node receive at least one message from its neighbors. The proposed algorithm can implement SR in O(log2 n) rounds. To illustrate the versatility of the SR primitive, we use the primitive to derive efficient algorithms for information broadcast and function computations. We conduct simulations to verify all the proposed algorithms, and the results show that the algorithms also perform well in realistic environments.
【Keywords】: Interference; Algorithm design and analysis; Computational modeling; Signal to noise ratio; Rayleigh channels; Distributed algorithms; Approximation algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Zhangjie Fu ; Xingming Sun ; Sai Ji ; Guowu Xie
【Abstract】: With the increasing adoption of cloud computing, a growing number of users outsource their datasets into cloud. The datasets usually are encrypted before outsourcing to preserve the privacy. However, the common practice of encryption makes the effective utilization difficult, for example, search the given keywords in the encrypted datasets. Many schemes are proposed to make encrypted data searchable based on keywords. However, keyword-based search schemes ignore the semantic representation information of users retrieval, and cannot completely meet with users search intention. Therefore, how to design a content-based search scheme and make semantic search more effective and context-aware is a difficult challenge. In this paper, we proposed an innovative semantic search scheme based on the concept hierarchy and the semantic relationship between concepts in the encrypted datasets. More specifically, our scheme first indexes the documents and builds trapdoor based on the concept hierarchy. To further improve the search efficiency, we utilize a tree-based index structure to organize all the document index vectors. Our experiment results based on the real world datasets show the scheme is more efficient than previous scheme. We also study the threat model of our approach and prove it does not introduce any security risk.
【Keywords】: Semantics; Indexes; Cryptography; Feature extraction; Cloud computing; Servers; Computers
【Paper Link】 【Pages】:1-9
【Authors】: Xueyuan Zhao ; Dario Pompili
【Abstract】: Multi-cell interference coordination via Block Diagonalization (BD), which is widely used in LTE-Advanced interference management, has three main drawbacks: (1) limitation on the number of supported co-channel users; (2) performance degradation in Doppler channels with feedback delay and quantization; and (3) high signaling overhead to exchange Channel State Information (CSI) and to generate precoding matrix. In this paper, a new approach is proposed to overcome these drawbacks and to improve the multi-cell interference coordination. The core idea is to create a null space only to the users within one cell; to achieve this goal, Zadoff-Chu Sequence (ZCS) spreading is used to eliminate the multi-cell interference by leveraging the zero-correlation property of cyclic shifts of the ZCS. This way, the capacity of the cellular network is improved in Doppler channels with delayed and quantized feedback; moreover, signaling overhead and computational complexity are both reduced. The auxiliary sampling capability of the hardware is utilized to realize the higher sampling rate required by the proposed approach. The new interference-management solution is compared against the existing one via computer simulations and is shown to lead to significant capacity gains even in high-mobility scenarios.
【Keywords】: Interference; Precoding; Channel estimation; Doppler effect; Delays; Null space; Downlink
【Paper Link】 【Pages】:1-9
【Authors】: Yang Li ; Hao Wu ; Tian Pan ; Huichen Dai ; Jianyuan Lu ; Bin Liu
【Abstract】: Per-flow measurement can provide fine-grained statistics for advanced network management and thus has been studied extensively. As network line rate continues its rapid growth, wire-speed per-flow measurement meets great challenges, for large numbers of statistics counters are required to record flow information at extremely high speed. Most of the previous efforts are committed to elaborate excellent sampling algorithms to make counters' memory occupation as small as possible, so as to fit into off-chip SRAM(s), but the throughput is rigidly bounded by the speed of SRAM. To break the wall, we explore a new path by proposing CASE: a cache-assisted stretchable estimator, which uses the on-chip memory as the fast cache of the off-chip SRAM. In this way, most of the accesses to the counters will happen on cache, thanks to the heavy-tailed distribution of Internet traffic. In this paper, we present CASE's design and derive strict mathematical proof to its relative error bound. Extensive experiments on real-world traces are conducted and the evaluation results indicate CASE can achieve up to 300Gbps throughput when using on-chip memory with 128K entries (equivalent to 1.125MB). Meanwhile CASE is more accurate and stretchable than uncached approaches.
【Keywords】: Radiation detectors; Random access memory; Estimation; Computer aided software engineering; System-on-chip; Throughput; Internet
【Paper Link】 【Pages】:1-9
【Authors】: Xiang Tian ; Jiguo Yu ; Liran Ma ; Guangshun Li ; Xiuzhen Cheng
【Abstract】: Global broadcasting is a fundamental problem in wireless multi-hop networks. In this paper, we propose two distributed deterministic algorithms for global broadcasting based on the Signal-to-Interference-plus-Noise-Ratio (SINR) model. In both algorithms, an arbitrary node can become the source node, and the rest of the nodes are divided into different layers according to their distance to the source node. A broadcast message is propagated from the source node to all the other nodes in a layer by layer fashion. Our first proposed algorithm (named TEGB) selects a Maximal Independent Set (MIS) for each layer. Subsequently, multiple subsets of the MIS are carefully selected so as to allow the most concurrent transmissions. Our theoretical analysis shows that TEGB has the time complexity of O(D log n), where n is the total number of nodes in the network and D is the diameter of the network. Compared with the popular algorithm DetGenBroadcast proposed in the work of Jurdzinski et al.(2013), TEGB has a logarithmic improvement in running time. Furthermore, we develop the second algorithm (named TBGB) to reduce the number of duplicated broadcast messages at each layer. To be specific, TBGB attempts to form a unidirectional spanning tree of the network. On the spanning tree, only the non-leaf nodes transmit the broadcast message. Therefore, the redundant broadcasts in the same layer are eliminated. Our theoretical analysis shows that TBGB has the time complexity of O(DΔ log n), where Δ is the maximum node degree.
【Keywords】: Interference; Broadcasting; Signal to noise ratio; Algorithm design and analysis; Time complexity; Protocols; Approximation algorithms
【Paper Link】 【Pages】:1-9
【Authors】: Han Deng ; I-Hong Hou
【Abstract】: The problem of allocating jobs to appropriate servers in cloud computing is studied in this paper. We consider that jobs of various types arrive in some unpredictable pattern and the system is required to allocate a certain ratio of jobs. In order to meet the hard allocation ratio requirement in the presence of unknown arrival patterns, one can increase the capacity of servers by expanding the size of data centers. We then aim to find the minimum capacity needed to meet a given allocation ratio requirement. We propose two online job allocation policies with low complexity. We prove that, given a hard allocation ratio requirement, these two policies can achieve the requirement with the least capacity. We also derive a closed-from expression for the amount of capacity needed to achieve any given requirement. Two other popular policies are studied, and we demonstrate that they need at least an order higher capacity to meet the same hard allocation ratio requirement. Simulation results demonstrate that our policies remain far superior than the other two when jobs arrive according to some random process.
【Keywords】: Resource management; Servers; Linear programming; YouTube; Streaming media; Random processes; Electronic mail
【Paper Link】 【Pages】:1-9
【Authors】: Chenxi Qiu ; Haiying Shen ; Liuhua Chen
【Abstract】: Functioning as an intermediary between cloud tenants and providers, cloud service brokerages (CSBs) bring about great benefits to the cloud market. To maximize its own profit, a CSB is faced with a challenge: how to reserve servers and distribute tenant demands to the reserved servers such that the total reservation cost is minimized while the reserved servers can satisfy the tenant service level agreement (SLA)? Demand prediction and demand allocation are two steps to solve this problem. However, previous demand prediction methods cannot accurately predict tenant demands since they cannot accurately estimate prediction errors and also assume the existence of seasonal periods of demands. Previous demand allocation methods only aim to minimize the number of reserved servers rather than the server reservation cost, which is more challenging. To solve this challenge, we propose a Probabilistic Demand Allocation system (PDA). It predicts demands and more accurate prediction errors without the assumption of the existence of seasonal periods. It then formulates a nonlinear programming problem and has a decentralized method to find the problem solution. In addition to overcoming the shortcomings in previous methods, PDA is novel in that rather than separately conducting the prediction and demand allocation, it considers prediction errors in demand allocation in order to allocate demands with offsetting prediction errors (e.g., -1 and +1) to the same server, which helps find the problem solution. Both simulation and real-world experimental results demonstrate the superior performance of our system in reducing servers' reservation cost.
【Keywords】: Servers; Cloud computing; Resource management; Handheld computers; Monitoring; Prediction methods; Google
【Paper Link】 【Pages】:1-9
【Authors】: Fei Chen ; Chunming Wu ; Xiaoyan Hong ; Zhouhao Lu ; Zhouhao Wang ; Chang-Ting Lin
【Abstract】: This paper is driven by a simple question of whether traffic engineering in Software Defined Networking (SDN) can react quickly to bursty and unpredictable changes in traffic demand. The key challenge is to strike a careful balance between the overhead (frequently involving the SDN controller) and performance (the degree of congestion measured as the maximum load and the balance between the minimum and the maximum loads). Exploiting OpenFlow (OF) features, quick shift of routing paths for unpredictable traffic bursty is the focal point of this work. It is achieved by using a dual routing scheme and letting the data plane to select the appropriate path in reacting to uncertainty in traffic load. The proposed work is called DUCE (Demand Uncertainty Configuration sElection). Further, we describe a traffic distribution model, an optimization solution that calculates congestion-free traffic distribution plan which guarantees that each switch can select one of the paths in a distributed way, and moreover, OF details about detaching the functionality of responding to the demand uncertainty from the control plane and delegating it to the data plane. Simulations are performed validating the efficiency of DUCE under various network scenarios.
【Keywords】: Uncertainty; Routing; Switches; Bandwidth; Optimization; Real-time systems
【Paper Link】 【Pages】:1-9
【Authors】: Meitian Huang ; Weifa Liang ; Zichuan Xu ; Wenzheng Xu ; Song Guo ; Yinlong Xu
【Abstract】: Software-Defined Networking (SDN) has emerged as the paradigm of the next-generation networking through separating the data control plane from the data plane. The forwarding routing table at each of its switch nodes is usually implemented by expensive and power-hungry Ternary Content Addressable Memory (TCAM) that only has limited number of entries, and the bandwidth at each of its links is bounded too. Under this new network architecture, providing a quality service to users by admitting user requests to meet their resource demands is challenging, and very little attention has ever been paid in this regard. In this paper, we will study online unicast and multicast request admissions in SDNs with the aim to maximize the network throughput under both critical network resources and user bandwidth demand constraints, for which we first propose a novel model to characterize the usage costs of node and link resources. We then devise efficient online algorithms for unicast and multicast requests. We also analyze the competitive ratios of the proposed online algorithms, which are O(log n) and O(Kϵ log n) for unicasting and multicasting, respectively, where n is the network size, K is the maximum number of members in a multicast request, and ϵ is a constant with 0 <; e ≤ 1. We finally evaluate the proposed algorithms empirically through simulations. The simulation results demonstrate that the proposed algorithms are very promising.
【Keywords】: Switches; Unicast; Routing; Bandwidth; Measurement; Throughput
【Paper Link】 【Pages】:1-9
【Authors】: Kostas Choumas ; Georgios S. Paschos ; Thanasis Korakis ; Leandros Tassiulas
【Abstract】: This paper proposes distributed load shedding policies for regulating excessive network load. Data packets are inserted into the network to be delivered to intended destinations. The intermediate network nodes may decide to forward or shed some packets depending on temporally available resources. It is possible for some packets to traverse several nodes in the network until they are finally dropped before reaching the destination, which exacerbates energy consumption. We define a multi-objective optimization problem where we aim to minimize the used energy subject to providing maximum sum throughput. For the case of single-path unicast sessions, we show that Energy-efficient Distributed Load Shedding (E-DLS), a simple shedding mechanism combined with pushback routing, solves this load di shedding optimization. We implement E-DLS in a testbed and use the experiments to select policy parameter values that strike a good balance between energy and delay performance. We then propose a heuristic extension of E-DLS for multirate multicast routing, and showcase via testbed experiments its optimal performance.
【Keywords】: Throughput; Optimization; Routing; Energy consumption; Delays; Receivers; Unicast
【Paper Link】 【Pages】:1-9
【Authors】: Avhishek Chatterjee ; Michael Borokhovich ; Lav R. Varshney ; Sriram Vishwanath
【Abstract】: Many companies now use crowdsourcing to leverage external (as well as internal) crowds to perform specialized work, and so methods of improving efficiency are critical. Tasks in crowdsourcing systems with specialized work have multiple steps and each step requires multiple skills. Steps may have different flexibilities in terms of obtaining service from one or multiple agents, due to varying levels of dependency among parts of steps. Steps of a task may have precedence constraints among them. Moreover, there are variations in loads of different types of tasks requiring different skill-sets and availabilities of different types of agents with different skill-sets. Considering these constraints together necessitates the design of novel schemes to allocate steps to agents. In addition, large crowdsourcing systems require allocation schemes that are simple, fast, decentralized and offer customers (task requesters) the freedom to choose agents. In this work we study the performance limits of such crowdsourcing systems and propose efficient allocation schemes that provably meet the performance limits under these additional requirements. We demonstrate our algorithms on data from a crowdsourcing platform run by a non-profit company and show significant improvements over current practice.
【Keywords】: Crowdsourcing; Resource management; Companies; Computer science; Numerical models; Stochastic processes; Conferences
【Paper Link】 【Pages】:1-9
【Authors】: Pavel Chuprikov ; Sergey I. Nikolenko ; Kirill Kogan
【Abstract】: Cloud computing allows on demand elastic service scaling. The capability of a service to predict resource requirements for the next operational period defines how well it will exploit the elasticity of cloud computing in order to reduce operational costs. In this work, we consider a capacity planning process for service scale-out as an online pricing model. In particular, we study the impact of buffering service requests on revenues in various settings with allocation and maintenance costs. In addition, we analyze the incurred latency implied by buffering service requests. We believe that our insights will allow to significantly simplify predictions and mitigate the unknowns of future demands on resources.
【Keywords】: Resource management; Optimized production technology; Cloud computing; Capacity planning; Economics; Maintenance engineering; Elasticity
【Paper Link】 【Pages】:1-9
【Authors】: Bo Ji ; Gagan Raj Gupta ; Yu Sang
【Abstract】: This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop flows and the one-hop interference model. The objective is twofold: 1) maximize the throughput when the flow sources continuously inject packets into the network, and 2) minimize the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we adopt a novel node-based approach and propose a service-balanced online scheduling algorithm, called NSB, which gives balanced scheduling opportunities to the nodes with heavy workload. We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results.
【Keywords】: Throughput; Scheduling algorithms; Measurement; Complexity theory; Approximation algorithms; Scheduling; Interference
【Paper Link】 【Pages】:1-9
【Authors】: Shannon Chen ; Zhenhuan Gao ; Klara Nahrstedt
【Abstract】: Free-viewpoint television (FTV) is a visionary application that provides immersive experience to the audience with the freedom of changing viewpoint during the video playout. However, live broadcasting and user interaction do not coexist in existing FTV systems. In this paper, we propose F.Live, a framework of FTV content dissemination that supports user-initiated viewpoint changing for live broadcasting. Simulation result of a large-scale experiment, based on camera array settings of existing Nagoya systems and EyeVision System, shows that F.Live is capable of supporting 100,000 concurrent audiences with free-viewpoint low user interaction latency and feasible bandwidth requirements.
【Keywords】: Bandwidth; Broadcasting; Cameras; Streaming media; Multimedia communication; Rendering (computer graphics); Multicast communication
【Paper Link】 【Pages】:1-9
【Authors】: Stefan Dernbach ; Nina Taft ; Jim Kurose ; Udi Weinsberg ; Christophe Diot ; Azin Ashkan
【Abstract】: The majority of Internet traffic is now dominated by streamed video content. As video quality continues to increase, the strain that streaming traffic places on the network infrastructure also increases. Caching content closer to users, e.g., using Content Distribution Networks, is a common solution to reduce the load on the network. A simple approach to selecting what to put in regional caches is to put the videos that are most popular globally across the entire customer base. However, this approach ignores distinct regional taste. In this paper we explore the question of how a video content provider could go about determining whether or not they should use a cache filling policy based solely upon global popularity or take into account regional tastes as well. We propose a model that captures the overlap between inter-regional and intra-regional preferences. We focus on movie content and derive a synthetic model that captures “taste” using matrix factorization, similarly to the method used in recommender systems. Our model enables us to widely explore the parameter space, and derive a set of metrics providers can use to determine whether populating caches according to regional of global tastes provides better cache performance.
【Keywords】: Motion pictures; Streaming media; Measurement; Internet; Sociology; Statistics; Data models
【Paper Link】 【Pages】:1-9
【Authors】: Andrea Detti ; Bruno Ricci ; Nicola Blefari-Melazzi
【Abstract】: MPEG DASH is a widely used standard for adaptive video streaming over HTTP. The conceptual architecture for DASH includes a web server and clients, which download media segments from the server. Clients select the resolution of video segments by using an Adaptive Bit-Rate (ABR) strategy; in particular, a throughput-based ABR is used in the case of live video applications. However, recent papers show that these strategies may suffer from the presence of proxies/caches in the network, which are instrumental in streaming video on a large scale. To face this issue, we propose to extend the MPEG DASH architecture with a Tracker functionality, enabling client-to-client sharing of control information. This extension paves the way to a novel family of Tracker-assisted strategies that allow a greater design flexibility, while solving the specific issue caused by proxies/caches; in addition, its utility goes beyond the problem at hand, as it can be used by other applications as well, e.g. for peer-to-peer streaming.
【Keywords】: Streaming media; Servers; Transform coding; Bandwidth; Encoding; Video coding; Oscillators
【Paper Link】 【Pages】:1-9
【Authors】: Hong Li ; Yunhua He ; Limin Sun ; Xiuzhen Cheng ; Jiguo Yu
【Abstract】: Video surveillance has been widely adopted to ensure home security in recent years. Most video encoding standards such as H.264 and MPEG-4 compress the temporal redundancy in a video stream using difference coding, which only encodes the residual image between a frame and its reference frame. Difference coding can efficiently compress a video stream, but it causes side-channel information leakage even though the video stream is encrypted, as reported in this paper. Particularly, we observe that the traffic patterns of an encrypted video stream are different when a user conducts different basic activities of daily living, which must be kept private from third parties as obliged by HIPAA regulations. We also observe that by exploiting this side-channel information leakage, attackers can readily infer a user's basic activities of daily living based on only the traffic size data of an encrypted video stream. We validate such an attack using two off-the-shelf cameras, and the results indicate that the user's basic activities of daily living can be recognized with a high accuracy.
【Keywords】: Streaming media; Cryptography; Encoding; Cameras; Video surveillance; Redundancy; Image coding
【Paper Link】 【Pages】:1-9
【Authors】: Rajarajan Sivaraj ; Ioannis Broustis ; N. K. Shankaranarayanan ; Vaneet Aggarwal ; Rittwik Jana ; Prasant Mohapatra
【Abstract】: LTE-Advanced (LTE-A) macro-cell deployments are being enhanced with small cells, i.e., low-power base stations, to increase the network coverage and capacity. However, simultaneous co-channel transmissions from macro and small cells cause increased inter-cell interference and under-utilize the spectrum resources at the small cells. The following LTE-A design techniques are used to improve system performance in such deployments: (i) Carrier Aggregation (CA) to increase capacity by using additional carrier bandwidth; (ii) enhanced Inter-Cell Interference Coordination (elCIC), that includes (a) Cell Selection Biasing (CSB) to increase small cell spectrum utilization via cell range expansion; and (b) blanking data transmission on the macro cells for a certain duration of time to increase cell-edge user throughput Our objective is to maximize the CSB of the small cell, subject to user QoS constraints and blanking support from the macro cell. Towards this end, we develop an analytical model that captures the inter-dependency between elCIC techniques. We observe that, not accounting for the complex inter-dependencies between these techniques leads to a degraded network performance. We propose a framework that jointly optimizes elCIC and the assignment of multiple component carriers in an LTE-A deployment for increasing spectrum utilization at the small cells with appropriate blanking support from the macro cells. Our simulation results show that our approach increases the small cell spectrum utilization and aggregate cell-edge throughput by as much as 200%.
【Keywords】: Conferences; Computers
【Paper Link】 【Pages】:1-9
【Authors】: Yi-Han Chiang ; Wanjiun Liao
【Abstract】: Energy saving in cellular systems is increasingly important due to ever-deteriorating global warming. Heterogeneous networks (HetNets) composed of various tiers of cells can attain energy savings thanks to the lower operational and transmit power consumptions of small cells. To address the inter-cell interference problem yet achieving network energy conservation, multicell cooperation facilitating cooperative transmission (also known as coordinated multipoint or CoMP) and sleep mode operation paves a way toward future green HetNets. To further alleviate the induced backhaul energy consumption caused by cooperative transmission, content caching which proactively caches popular files at local storages is regarded as a viable solution. In this paper, we investigate how energy-aware multicell cooperation in HetNets with content caching (ENCORE) can be achieved. On proving that the ENCORE problem is decomposable into two sub-problems, we claim that the place-then-transmit strategy is optimal to the ENCORE problem. Then, we design algorithms for the sub-problems and prove that the total energy consumption achieved by the proposed solution is upper-bounded. Our simulation results demonstrate that the proposed solution outperforms various dynamic clustering approaches in terms of energy savings, and show the impacts of content popularity and cache size on the backhaul energy consumption.
【Keywords】: Energy consumption; Interference; Power demand; Heterogeneous networks; Energy conservation; Algorithm design and analysis; Simulation
【Paper Link】 【Pages】:1-9
【Authors】: Nikolaos Sapountzis ; Thrasyvoulos Spyropoulos ; Navid Nikaein ; Umer Salim
【Abstract】: Operators, struggling to continuously add capacity and upgrade their architecture to keep up with data traffic increase, are turning their attention to denser deployments that improve spectral efficiency. Denser deployments make the problem of user association challenging, and much work has been devoted to finding algorithms that strike a tradeoff between user quality of service (QoS), and network-wide performance (load-balancing). Nevertheless, the majority of these algorithms typically consider only the radio access part, and ignore the backhaul topology and potential capacity limitations. Backhaul constraints are emerging as a key performance bottleneck in future heterogeneous networks, partly due to the continuous improvement of the radio interface, and partly due to the need for inexpensive backhaul links to reduce CAPEX/OPEX. To this end, we propose an analytical framework for user association that jointly considers radio access and backhaul performance. We derive an algorithm that takes into account spectral efficiency, base station load, backhaul link capacities and topology, and uplink and downlink traffic demand, and prove it converges to an optimal solution. We then use extensive simulations to study the impact of (i) backhaul capacity limitations and (ii) backhaul topology on key performance metrics.
【Keywords】: Topology; Network topology; Downlink; Uplink; Routing; Load modeling; Interference
【Paper Link】 【Pages】:1-9
【Authors】: Chan-Ching Hsu ; J. Morris Chang ; Yu-Wen Chen
【Abstract】: To steadily gaining benefit from the exponential growth in mobile traffic, operators are eager to find solutions to maximize profits. Two very attractive strategies have been proposed to complement the existing macro cellular architecture: deploying low power bases stations and offloading data traffic to other networks. Each strategy has different costs and yields different benefits for operators. The offloading option could be cheaper in the short run; nevertheless, it might be more expensive in the long run than cell densification due to the varying cost. On the other hand, small cells, since having to be deployed in advance, may be underutilized or not fully meet future demands. In the latter case, offloading techniques can be used to increase capacity with additional costs. Further, uncertainty of future data demands and electricity prices also impact operators profitability, making the best network strategy difficult to achieve. To address such problem, an optimal cell configuration algorithm is proposed by formulating a stochastic programming model that considers both network design and data offloading. This algorithm can maximize the profit, under future demand and price uncertainty. Numerical studies are extensively performed in which the results show that operators' profits can be improved with our proposed algorithm.
【Keywords】: Mobile communication; Uncertainty; Mobile computing; Computer architecture; Microprocessors; Stochastic processes; Planning
【Paper Link】 【Pages】:1-9
【Authors】: Bin Li ; Aditya Ramamoorthy ; R. Srikant
【Abstract】: We study cloud-storage systems with a very large number of files stored in a very large number of servers. In such systems, files are either replicated or coded to ensure reliability, i.e., file recovery from server failures. This redundancy in storage can further be exploited to improve system performance (mean file access delay) through appropriate load-balancing (routing) schemes. However, it is unclear whether coding or replication is better from a system performance perspective since the corresponding queueing analysis of such systems is, in general, quite difficult except for the trivial case when the system load asymptotically tends to zero. Here, we study the more difficult case where the system load is not asymptotically zero. Using the fact that the system size is large, we obtain a mean-field limit for the steady-state distribution of the number of file access requests waiting at each server. We then use the mean-field limit to show that, for a given storage capacity per file, coding strictly outperforms replication at all traffic loads while improving reliability. Further, the factor by which the performance improves in the heavy-traffic is at least as large as in the light-traffic case. Finally, we validate these results through extensive simulations.
【Keywords】: Servers; Delays; Encoding; Cloud computing; Queueing analysis; Reliability; Load modeling
【Paper Link】 【Pages】:1-9
【Authors】: Boyang Yu ; Jianping Pan
【Abstract】: With the increasing demand of big data applications, a variety of problems on how to operate the supporting infrastructures more intelligently and efficiently have attracted much attention in the literature. To optimize the data placement among distributed network locations is one of the fundamental problems, which aims at facilitating the data storage and access. However, traditional schemes meet challenges on the running time and the overhead introduced due to the increasing scale of datasets. Therefore, we propose a novel data placement scheme based on sketches to overcome these challenges. We first justify the effectiveness of applying the hypergraph sparsification on the data placement problem, and then present the method of constructing sparsifiers through the sketches of request traffic. Besides, the scheme features on the support of aggregating distributed sketches to make the decision and capturing the pattern of recent traffic through sliding windows. Finally, we obtain numerical results through simulations which confirm that the proposed scheme can place data effectively while reducing the introduced overhead in terms of algorithm running time, space and network traffic.
【Keywords】: Distributed databases; Partitioning algorithms; Itemsets; Data models; Approximation algorithms; Big data; Data mining
【Paper Link】 【Pages】:1-9
【Authors】: Yaochen Hu ; Di Niu
【Abstract】: Erasure coding has been applied in many cloud storage systems to enhance reliability at a lower storage cost than replication. While a large amount of prior work aims to enhance recovery performance and reliability, the overall access delay in coded storage still needs to be optimized. As most production systems adopt a systematic code and place the original copy of each block on only one server to be read normally, it is harder to balance server loads and more likely to incur latency tails in coded storage than in three-way replication, where a block can be read from any of the 3 servers storing the block. In this paper, we propose to reduce the access latency in coded storage systems by moving blocks with anti-correlated demands onto same servers for statistical load balancing. We formulate the optimal block placement as a problem similar to Min-k-Partition, propose a local block migration scheme, and derive an approximation ratio as a function of demand variation across blocks. Based on request traces from Windows Azure Storage, we demonstrate that our scheme can significantly reduce the access latency with only a few block moves, especially when the request demand is skewed.
【Keywords】: Servers; Reliability; Approximation algorithms; Cloud computing; Production systems; Systematics; Encoding
【Paper Link】 【Pages】:1-9
【Authors】: Guoxin Liu ; Haiying Shen
【Abstract】: It is important for cloud service brokers to provide a multi-cloud storage service to minimize their payment cost to cloud service providers (CSPs) while providing service level objective (SLO) guarantee to their customers. Many multi-cloud storage services have been proposed or payment cost minimization or SLO guarantee. However, no previous works fully leverage the current cloud pricing policies (such as resource reservation pricing) to reduce the payment cost. Also, few works achieve both cost minimization and SLO guarantee. In this paper, we propose a multi-cloud Economical and SLO-guaranteed Storage Service (ES3), which determines data allocation and resource reservation schedules with payment cost minimization and SLO guarantee. ES3 incorporates (1) a coordinated data allocation and resource reservation method, which allocates each data item to a datacenter and determines the resource reservation amount on datacenters by leveraging all the pricing policies; (2) a genetic algorithm based data allocation adjustment method, which reduce data Get/Put rate variance in each datacenter to maximize the reservation benefit; and (3) a dynamic request redirection method, which dynamically redirects a data request from a reservation-overutilized datacenter to a reservation-underutilized datacenter to further reduce the payment. Our trace-driven experiments on a supercomputing cluster and on real clouds (i.e., Amazon S3, Windows Azure Storage and Google Cloud Storage) show the superior performance of ES3 in payment cost minimization and SLO guarantee in comparison with previous methods.
【Keywords】: Cloud computing; Resource management; Pricing; Schedules; Minimization; Google; Genetic algorithms