INFOCOM 2017 论文列表

The emerging network slicing paradigm for 5G provides new business opportunities by enabling multi-tenancy support. At the same time, new technical challenges are introduced, as novel resource allocation algorithms are required to accommodate different business models. In particular, infrastructure providers need to implement radically new admission control policies to decide on network slices requests depending on their Service Level Agreements (SLA). When implementing such admission control policies, infrastructure providers may apply forecasting techniques in order to adjust the allocated slice resources so as to optimize the network utilization while meeting network slices' SLAs. This paper focuses on the design of three key network slicing building blocks responsible for (i) traffic analysis and prediction per network slice, (ii) admission control decisions for network slice requests, and (iii) adaptive correction of the forecasted load based on measured deviations. Our results show very substantial potential gains in terms of system utilization as well as a trade-off between conservative forecasting configurations versus more aggressive ones (higher gains, SLA risk).

We revisit the problem of assigning n jobs to m machines/servers. We study this problem under more general settings, which capture important aspects of applications that arise in networking and information systems. In particular, we consider jobs that have placement constraints and machines that are heterogeneous. The cost incurred at a machine is given by any general convex function on the number of jobs assigned to it. We aim to minimize the sum cost and the maximum differential cost. Through a network-flow equivalence transformation, we observe how these two objectives are fundamentally related, showing that sum-cost minimization implies maximum-differential-cost minimization. We propose an efficient algorithm termed Maximum Edge-Cost Cycle Cancelling (MEC3) to solve the sum-cost minimization problem with O(n2m2) time complexity. Furthermore, for applications where only the maximum differential cost is of concern, we further improve the efficiency of MEC3by proposing an early stop condition. We implement MEC3and two other algorithms from the literature. Using benchmark input instances, we show that MEC3has substantially lower run time than the other algorithms.

Recent studies have experimentally shown the gains of full-duplex radios. However, due to its relatively higher cost and complexity, we can envision a more practical step in the network evolution is to have a full-duplex access point (AP) but keep the clients half-duplex. Unfortunately, the full-duplex gains can hardly be extracted in practice as the uplink transmission from a half-duplex client introduces inter-client interference to another downlink client. To address this issue, we present the design and implementation of IC2 (Inter-Client Interference Cancellation), the first physical layer solution that exploits the AP's full-duplex capability to actively cancel the interference at the downlink client. Such active cancellation not only improves the achievable capacity, but also better tolerates imperfect user pairing, simplifying the MAC design as a result. We build a prototype of IC2 on USRP-N200 and evaluate its performance via both testbed experiments and large-scale trace-driven simulations. The results show that, without IC2, about 60% of client pairs produce no gain from full-duplex transmissions, while, with IC2 the median throughput gain over conventional half-duplex networks can be 1.65× even when clients are simply paired randomly.

Mobile crowdsensing is a new paradigm in which a requester can recruit a group of mobile users via a platform and coordinate them to perform some sensing tasks by using their smartphones. In mobile crowdsensing, each user might perform multiple tasks with different sensing qualities. An important problem is recruiting the minimum number of users while achieving a satisfactory sensing quality for each task. Meanwhile, in order to ease users' worries about privacy disclosures, the user recruitment process needs to protect each user's sensing quality information from being revealed to other users or to the platform. We prove that this problem is NP-hard. To solve this problem, we first propose a Basic User Recruitment (BUR) protocol based on a greedy strategy, which can recruit nearly the minimum amount of users while ensuring that the total sensing quality of each task is no less than a given threshold. Based on BUR, we further propose a Secure User Recruitment (SUR) protocol by using secret sharing schemes. We analyze the approximation ratio and prove the security of the SUR protocol in the semi-honest model. Moreover, we extend SUR to deal with a more general case where the total sensing quality of each task might be an increasing submodular function. Finally, we demonstrate the significant performance of the proposed protocol through extensive simulations and execution in real smartphones.

Acknowledging the powerful sensors on wearables and smartphones enabling various applications to improve users' life styles and qualities (e.g., sleep monitoring and running rhythm tracking), this paper takes one step forward developing FitCoach, a virtual fitness coach leveraging users' wearable mobile devices (including wrist-worn wearables and arm-mounted smartphones) to assess dynamic postures (movement patterns & positions) in workouts. FitCoach aims to help the user to achieve effective workout and prevent injury by dynamically depicting the short-term and long-term picture of a user's workout based on various sensors in wearable mobile devices. In particular, FitCoach recognizes different types of exercises and interprets fine-grained fitness data (i.e., motion strength and speed) to an easy-to-understand exercise review score, which provides a comprehensive workout performance evaluation and recommendation. FitCoach has the ability to align the sensor readings from wearable devices to the human coordinate system, ensuring the accuracy and robustness of the system. Extensive experiments with over 5000 repetitions of 12 types of exercises involve 12 participants doing both anaerobic and aerobic exercises in indoors as well as outdoors. Our results demonstrate that FitCoach can provide meaningful review and recommendations to users by accurately measure their workout performance and achieve 93% accuracy for workout analysis.

Signal decay is the fundamental problem of wireless communications, especially in an indoor environment where line-of-sight (LOS) paths for signal propagation are often blocked and various indoor objects exacerbate signal fading. There are three reasons for signal decay: long transmission distance, signal penetration, and reflection. In this paper, we propose OptRe which optimally places metallic reflectors - providing a highly reflective surface that can reflect impinging signals almost 100% - in indoor environments to reduce the reflection loss and enhance wireless transmissions. It enhances both WiFi signal and low-power IoT devices without changing their configurations or network protocols. To enable OptRe, we first develop an empirical signal propagation model that can accurately estimate the signal strength and adapt itself to the reflectors' location. Using micro-benchmarks, our empirical signal propagation model is shown to be more accurate than the other existing path loss models. We also optimally place reflectors to maximize the worst-case signal coverage within the target indoor areas. Our extensive experimental evaluation results have shown OptRe to enhance signal strength for different types of wireless signals by almost 2x.

The recent proliferation of increasingly capable mobile devices has given rise to mobile crowd sensing (MCS) systems that outsource the collection of sensory data to a crowd of participating workers that carry various mobile devices. Aware of the paramount importance of effectively incentivizing participation in such systems, the research community has proposed a wide variety of incentive mechanisms. However, different from most of these existing mechanisms which assume the existence of only one data requester, we consider MCS systems with multiple data requesters, which are actually more common in practice. Specifically, our incentive mechanism is based on double auction, and is able to stimulate the participation of both data requesters and workers. In real practice, the incentive mechanism is typically not an isolated module, but interacts with the data aggregation mechanism that aggregates workers' data. For this reason, we propose CENTURION, a novel integrated framework for multi-requester MCS systems, consisting of the aforementioned incentive and data aggregation mechanism. CENTURION's incentive mechanism satisfies truthfulness, individual rationality, computational efficiency, as well as guaranteeing non-negative social welfare, and its data aggregation mechanism generates highly accurate aggregated results. The desirable properties of CENTURION are validated through both theoretical analysis and extensive simulations.

Traditional wireless schedulers have been driven by rate-based criteria, e.g., utility maximizing/proportionally fair, and/or queue-based packet schedulers which do not directly reflect the Quality of Experience (QoE) associated with flow-based transactions and services. This paper proposes, a Measurement-Based Delay Optimal (MBDO) scheduler, which optimizes a cost function of the mean flow delays in a multi-class system, e.g,. web interactive, file downloads, etc. In this context the cost function expresses desired trade-offs amongst traffic classes reflecting heterogeneous QoE sensitivities which are nonlinear in the flow delays and/or system loads. To achieve optimality, MBDO scheduling uses measured system variables and knowledge (or measurement) of class flow-size distributions to adapt a weighted Gittins index scheduler. We show that under mild assumptions, and in a stationary regime, that MBDO scheduling is indeed asymptotically optimal. Perhaps more importantly, MBDO schedulers can self-optimize by adapting to slowly varying traffic loads, mixes and flow size distributions. Our extensive simulations confirm the effectiveness at realizing trade-offs and performance of the proposed approach.

Graph sampling techniques via random walk crawling have been popular for analyzing statistical characteristics of large online social networks due to simple implementation and provable guarantees on unbiased estimates. Despite the growing popularity, the `cost' of sampling and its true impact on the accuracy of estimates still have not been carefully studied. In addition, the random walk-based methods inherently suffer from the sluggish nature of random walks and the `slow-mixing' structure of social graphs, thereby leading to high correlation in the samples obtained. With these in mind, in this paper, we develop a mathematical framework such that the cost of sampling is properly taken into account, which in turn re-defines a widely used asymptotic variance into a cost-based asymptotic variance. Our new metric enables us to compare a class of sampling policies under the same cost constraint, integrating “random skipping” (bypassing nodes without sampling) into the random walk-based sampling. We obtain an optimal policy striking the right balance between sampling quality (less correlation) and sampling quantity (higher cost per sample), which greatly improves over the usual skip-free crawling-based samplers. We further extend our framework, enabling one to design more sophisticated sampling strategies with an array of control knobs, which all produce unbiased estimates under the same cost constraint.

With the rapid growth of smart devices, mobile crowdsensing is becoming an important paradigm to acquire information from physical environments. Considering that the sensing data collected by mobile users are normally noisy and imprecise, one of the pressing problems in mobile crowdsensing is to evaluate the data quality in real time and to steer users to acquire data with high quality. However, it is challenging to estimate the data quality without the availability of ground truth data. In this paper, we observe that sensing context has a significant impact on data quality, which motivates us to propose a context-aware data quality estimation scheme. With historical sensing data, we train a context-quality classifier, which captures the relation between context information and data quality, to estimate data quality in an online manner. We apply such a context-aware data quality estimation scheme to guide user recruitment in mobile crowdsensing. We model the process of user recruitment as a stochastic submodular maximization problem, and design a random adaptive greedy algorithm to guarantee a constant approximation ratio. We evaluate our algorithm on a real-world temperature data set. The evaluation results show that our algorithm outperforms other existing techniques, in terms of prediction accuracy.

Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just a single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internetscale database. To solve the problem, we propose an algorithm named HLL-TailCut+, which implements the estimation standard error 1.0/√m using the memory units of three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.

Load balancing is an important activity in distributed systems. At a high-level of abstraction, this problem assumes processes in the system begin with a potentially uneven assignment of “work” which they must then attempt to spread evenly. There are many different approaches to solving this problem. In this paper, we focus on local load balancing-an approach in which work is balanced in an iterative and distributed manner by having processes exchange work in each round with neighbors in an underlying communication network. The goal with local load balancing is to prove that these local exchanges will lead over time to a global balance. We describe and analyze a new local load balancing strategy called max neighbor, and prove a bound on the number of rounds required for it to obtain a parameterized level of balance, with high probability, in a general dynamic network topology. We then prove this analysis tight (within logarithmic factors) by describing a network and initial work distribution for which max neighbor matches its upper bound, and then build on this to prove that no load balancing algorithm in which every node exchanges work with at most one partner per round can converge asymptotically faster than max neighbor.

In this paper, we study the correlation between passwords across different datasets which quantitatively explains the success of existing training-based password cracking techniques. We also study the correlation between a user's password and his/her social profile. This enabled us to develop the first social profile-aware password strength meter, namely SociaLShield. Our quantification techniques and SocialShield have meaningful implications to system administrators, users, and researchers, e.g., helping them quantitatively understand the threats posed by a password leakage incident, defending against emerging profile-based password attacks, and facilitating the research of countermeasures against existing and newly developed training-based password attacks. We validate our proposed quantification techniques and SocialShield through extensive experiments by leveraging real-world leaked passwords. Experimental results demonstrate that our quantification techniques are accurate in measuring correlation among different leaked datasets and that although SocialShield is light-weight, it is effective in defending against profile-based password attacks.

Activity sensing has become a key technology for many ubiquitous applications, such as exercise monitoring and elder care. Most traditional approaches track the human motions and perform activity recognition based on the waveform matching schemes in the raw data representation level. In regard to the complex activities with relatively large moving range, they usually fail to accurately recognize these activities, due to the inherent variations in human activities. In this paper, we propose a wearable approach for logic cognition-based activity sensing scheme in the logical representation level, by leveraging the meta-activity recognition. Our solution extracts the angle profiles from the raw inertial measurements, to depict the angle variation of limb movement in regard to the consistent body coordinate system. It further extracts the meta-activity profiles to depict the sequence of small-range activity units in the complex activity. By leveraging the least edit distance-based matching scheme, our solution is able to accurately perform the activity sensing. Based on the logic cognition-based activity sensing, our solution achieves lightweight-training recognition, which requires a small quantity of training samples to build the templates, and user-independent recognition, which requires no training from the specific user. The experiment results in real settings shows that our meta-activity recognition achieves an average accuracy of 92% for user-independent activity sensing.

Thanks to the highly-dense lighting infrastructure in public areas, visible light emerges as a promising means to indoor localization and navigation. State-of-the-art techniques generally require customized hardware (sensing boards), and mainly work with one single light source (e.g., customized LEDs). This greatly limits their application scope. In this paper, we propose NaviLight, a generic indoor localization and navigation framework based on existing lighting infrastructure with any unmodified light sources (e.g., LED, fluorescent, and incandescent lights). NaviLight simply adopts commercial off-the-shelf mobile phones as receivers, and light intensity values as location signatures. Unlike existing WiFi systems, a single light intensity value is not discriminative enough over space though the light intensity field does vary, which makes our design more challenging. We thus propose a LightPrint as a location signature using a vector of multiple light intensity values obtained during user's walks. Such LightPrints are created by leveraging any user movement (of varying distance and direction) in order to minimize user efforts. A set of techniques are proposed to achieve quick LightPrint matching, which includes a coarse-grained classification and a fine-grained matching over dynamic time warping. We have implemented NaviLight to provide real-time service on Android phones in three typical indoor environments, covering a total area size over 1000m2. Our experiments show that NaviLight can achieve sub-meter localization accuracy to meet practical engineering requirements.

Auto-scaling mechanisms are an important line of defense against Distributed Denial of Service (DDoS) in the cloud. Using auto-scaling, machines can be added and removed in an on-line manner to respond to fluctuating load. It is commonly believed that the auto-scaling mechanism casts DDoS attacks into Economic Denial of Sustainability (EDoS) attacks. Rather than suffering from performance degradation up to a total denial of service, the victim suffers only from the economic damage incurred by paying for the extra resources required to process the bogus traffic of the attack. Contrary to this belief, we present and analyze the Yo-Yo attack, a new attack against the auto-scaling mechanism, that can cause significant performance degradation in addition to economic damage. In the Yo-Yo attack, the attacker sends periodic bursts of overload, thus causing the auto-scaling mechanism to oscillate between scale-up and scale-down phases. The Yo-Yo attack is harder to detect and requires less resources from the attacker compared to traditional DDoS. We demonstrate the attack on Amazon EC2 [4], and analyze protection measures the victim can take by reconfiguring the auto-scaling mechanism.

Attacker VMs try to co-reside with victim VMs on the same physical infrastructure as a precursor to launching attacks that target information leakage. VM migration is an effective countermeasure against attempts at malicious co-residency. In this paper, we first undertake an experimental study on Amazon EC2 to obtain an in-depth understanding of the side-channels an attacker can use to ascertain co-residency with a victim. Here, we identify a new set of stealthy side-channel attacks which, we show to be more effective than currently available attacks towards verifying co-residency. Based on the study, we develop a set of guidelines to determine under what conditions victim VM migrations should be triggered given performance costs in terms of bandwidth and downtime, that a user is willing to bear. Via extensive experiments on our private in-house cloud, we show that migrations using our guidelines can limit the fraction of the time that an attacker VM co-resides with a victim VM to about 1 % of the time with bandwidth costs of a few MB and downtimes of a few seconds, per day per VM migrated.

With software-defined network (SDN) and network function virtualization (NFV) techniques, we can embed the service chain consisting of a sequence of virtualized network functions (VNFs), i.e., we can determine the flow path and deploy the VNFs contained in the service chain at any place on the path. In the literature, the methods of service chain embedding bound the number of VNFs at a node, whereas the link capacities are disregarded and the amount of flows is not considered, which could cause serious congestion. In addition, according to our experiment, the process overhead on a computation node is linear to the total amount of flows processed. In this paper, we propose a method of service chain embedding to maximize the total amount of flows while bounding the process overhead of the flows on a node by its computation capability and the total amount of flows on an link by its bandwidth capacity. To our knowledge, our method is the first approximation algorithm of service chain embedding with considering flow in the literature. Simulations show our algorithm has good performance in terms of the total amount of flows.

Wirelessly networked systems of implantable medical devices endowed with sensors and actuators will be the basis of many innovative, sometimes revolutionary therapies. The biggest obstacle in realizing this vision of networked implantable devices is posed by the dielectric nature of the human body, which strongly attenuates radio-frequency (RF) electromagnetic waves. In this paper we present the first hardware and software architecture of an Internet of Medical Things (IoMT) platform with ultrasonic connectivity for intra-body communications that can be used as a basis for building future IoT-ready medical implantable and wearable devices. We show that ultrasonic waves can be efficiently generated and received with low-power and mm-sized components, and that despite the conversion loss introduced by ultrasonic transducers the gap in attenuation between 2.4 GHz RF and ultrasonic waves is still substantial, e.g., ultrasounds offer 70 dB less attenuation over 10 cm. We show that the proposed IoMT platform requires much lower transmission power compared to 2.4 GHz RF with equal reliability in tissues, e.g., 35 dBm lower over 12 cm for 10-3Bit Error Rate (BEr) leading to lower energy per bit and longer device lifetime. Finally, we show experimentally that 2.4 GHz RF links are not functional at all above 12 cm, while ultrasonic links achieve a reliability of 10-6up to 20 cm with less than 0 dBm transmission power.