INFOCOM 2018 论文列表

A fundamental problem in many network systems is how to allocate limited resources among competing agents, who may have their own incentives. The well-known Vickrey-Clarke-Groves (VCG) mechanism provides an elegant solution to this incentive issue. In particular, VCG implements the socially optimal outcome in dominant strategies. However, it is also well-known that this mechanism can require an excessive amount of communication. Approaches have been studied that relax the communication requirements while also relaxing the incentive guarantees to use Nash equilibria instead of dominant strategies. Here, we take a different approach and study mechanisms with limited information that still have dominant strategy outcomes, but suffer an efficiency loss. We characterize this loss for the case of a single divisible resource. We first consider a mechanism in which information is limited by quantizing the resource into a finite number of units and allocating each of these to one agent via a VCG mechanism. This limits each agent to submitting a finite number of real values. We subsequently consider the case where each value is also quantized before being reported by each agent. Finally, we present numerical examples of the performance of these mechanisms.

Researchers have demonstrated the feasibility of detecting human motion behind the wall with radio frequency (RF) sensing techniques. With these techniques, an eavesdropper can monitor people's behavior from outside of the room without the need to access the room. This introduces a severe privacy-leakage issue. To address this issue, we propose Aegis, an interference-negligible RF sensing shield that i) incapacitates the RF sensing of eavesdroppers that work at any unknown locations outside of the protected area; ii) has minimum interference to the ongoing WiFi communication; and iii) preserves authorized RF sensing inside the private region. Our extensive evaluation shows that when Aegis is activated, it i) has a negligible impact on the legitimate sensing system; ii) effectively prevents the illegitimate sensing system from sensing human motions. Moreover, the ongoing data communication throughput is even increased.

Mobile crowdsensing with increasing pervasiveness of smartphones has enabled a myriad of applications, including urban-scale signal map monitoring and revision. Despite the importance of its quality, due to the large size of a site to cover, dense crowdsourcing is neither cost-effective nor convenient for crowdsourcing participants, making it critical and challenging to balance between signal quality and crowdsourcing cost. To address this problem, we propose a novel incentive mechanism, BCCS, based on Bayesian Compressive Crowdsensing (BCS). BCCS iteratively determines the spatial grids for crowd-sourcing quality and predicts the remaining unexplored grids for deployment efficiency. BCS returns not only the predicted signal values, but also the confidence intervals for convergence and incentive control. A probabilistic user participation and measurement model is applied for incentive design, which is flexible for crowdsensing deployment. Our extensive evaluation based on two different data sets shows that BCCS achieves much higher prediction accuracy (often by more than 20%) with lower payments to the participants and fewer iterations (often by 30%) than existing solutions.

Mobile Edge Computing (MEC) pushes computing functionalities away from the centralized cloud to the network edge, thereby meeting the latency requirements of many emerging mobile applications and saving backhaul network bandwidth. Although many existing works have studied computation of-floading policies, service caching is an equally, if not more important, design topic of MEC, yet receives much less attention. Service caching refers to caching application services and their related databases/libraries in the edge server (e.g. MEC-enabled BS), thereby enabling corresponding computation tasks to be executed. Because only a small number of application services can be cached in resource-limited edge server at the same time, which services to cache has to be judiciously decided to maximize the edge computing performance. In this paper, we investigate the extremely compelling but much less studied problem of dynamic service caching in MEC-enabled dense cellular networks. We propose an efficient online algorithm, called OREO, which jointly optimizes dynamic service caching and task offloading to address a number of key challenges in MEC systems, including service heterogeneity, unknown system dynamics, spatial demand coupling and decentralized coordination. Our algorithm is developed based on Lyapunov optimization and Gibbs sampling, works online without requiring future information, and achieves provable close-to-optimal performance. Simulation results show that our algorithm can effectively reduce computation latency for end users while keeping energy consumption low.

The development of virtualization techniques enables an architectural shift in mobile networks, where resource allocation, or even signal processing, become software functions hosted in a data center. The centralization of computing resources and the dynamic mapping between baseband processing units (BBUs) and remote antennas (RRHs) provide an increased flexibility to mobile operators, with important reductions of operational costs. Most research efforts on Cloud Radio Access Networks (CRAN) consider indeed an operator perspective and network-side performance indicators. The impact of such new paradigms on user experience has been instead overlooked. In this paper, we shift the viewpoint, and show that the dynamic assignment of computing resources enabled by CRAN generates a new class of mobile terminal handover that can impair user quality of service. We then propose an algorithm that mitigates the problem, by optimizing the mapping between BBUs and RRHs on a time-varying graph representation of the system. Furthermore, we show that a practical online BBU-RRH mapping algorithm achieves results similar to an oracle-based scheme with perfect knowledge of future traffic demand. We test our algorithms with two large-scale real-world datasets, where the total number of handovers, compared with the current architectures, is reduced by more than 20%. Moreover, if a small tolerance to dropped calls is allowed, 30% less handovers can be obtained.

The emergence of Network Function Virtualization (NFV) enables flexible and agile service function chaining in a Software Defined Network (SDN). While this virtualization technology efficiently offers customization capability, it however comes with a cost of consuming precious TCAM resources. Due to this, the number of service chains that an SDN can support is limited by the flowtable size of a switch. To break this limitation, this paper presents CRT-Chain, a service chain forwarding protocol that requires only constant flowtable entries, regardless of the number of service chain requests. The core of CRT-Chain is an encoding mechanism that leverages Chinese Remainder Theorem (CRT) to compress the forwarding information into small labels. A switch does not need to insert forwarding rules for every service chain request, but only needs to conduct very simple modular arithmetic to extract the forwarding rules directly from CRT-Chain's labels attached in the header. We further incorporate prime reuse and path segmentation in CRT-Chain to reduce the header size and, hence, save bandwidth consumption. Our evaluation results show that, when a chain consists of no more than 5 functions, CRT-Chain actually generates a header smaller than the legacy 32-bit header defined in IETF. By enabling prime reuse and segmentation, CRT-Chain further reduces the total signaling overhead to a level lower than the conventional scheme, showing that CRT-Chain not only enables scalable flowtable-free chaining but also improves network efficiency.

Future networks are expected to support low-latency, context-aware and user-specific services in a highly flexible and efficient manner. One approach to support emerging use cases such as, e.g., virtual reality and in-network image processing is to introduce virtualized network functions (vNF)s at the edge of the network, placed in close proximity to the end users to reduce end-to-end latency, time-to-response, and unnecessary utilisation in the core network. While placement of vNFs has been studied before, it has so far mostly focused on reducing the utilisation of server resources (i.e., minimising the number of servers required in the network to run a specific set of vNFs), and not taking network conditions into consideration such as, e.g., end-to-end latency, the constantly changing network dynamics, or user mobility patterns. In this paper, we formulate the Edge vNF placement problem to allocate vNFs to a distributed edge infrastructure, minimising end-to-end latency from all users to their associated vNFs. We present a way to dynamically re-schedule the optimal placement of vNFs based on temporal network-wide latency fluctuations using optimal stopping theory. We then evaluate our dynamic scheduler over a simulated nation-wide backbone network using real-world ISP latency characteristics. We show that our proposed dynamic placement scheduler minimises vNF migrations compared to other schedulers (e.g., periodic and always-on scheduling of a new placement), and offers Quality of Service guarantees by not exceeding a maximum number of latency violations that can be tolerated by certain applications.

Artificial lighting is a pervasive element in our daily lives. Researchers from different communities are investigating challenges and opportunities related to artificial lighting but from different angles: energy disaggregation, to monitor the status of light bulbs in buildings; and communication, to transmit information wirelessly. We argue that there is an unexplored synergy between these two communities. When a light bulb modulates its intensity for communication, it also affects the current it draws. This current signature is unique and could be used by energy disaggregation methods to identify the lights' status. These signatures however will be exposed to interference (collisions of signatures) and distortions due to power line effects. To overcome these problems, we build upon coding schemes to assign interference-resilient signatures, and we develop custom hardware to ameliorate distortions introduced by power lines. We validate our framework in a proof-of-concept testbed, perform simulations to test scalability, and use energy traces from real homes to evaluate the impact of other electric loads.

The surge of video traffic is a challenge for service providers that need to maximize Quality of Experience (QoE) while optimizing the cost of their infrastructure. In this paper, we address the problem of routing multiple HTTP-based Adaptive Streaming (HAS) sessions to maximize QoE. We first design a QoS-QoE model incorporating different QoE metrics which is able to learn online network variations and predict their impact on representative classes of adaptation logic, video motion and client resolution. Different QoE metrics are then combined into a QoE score based on ITU-T Rec. P.1202.2. This rich score is used to formulate the routing problem. We show that, even with a piece-wise linear QoE function in the objective, the routing problem without controlled rate allocation is non-linear. We therefore express a routing-plus-rate allocation problem and make it scalable with a dual subgradient approach based on Lagrangian relaxation where subproblems select a single path for each request with a trivial search, thereby connecting explicitly QoE, QoE and HAS bitrate. We show with ns-3 simulations that our algorithm provides values for HAS QoE metrics (quality, rebufferings, variation) equivalent to MILP and better than QoS-based approaches.

The very large bandwidth available in the 60 GHz band allows, in principle, to design highly accurate positioning systems. Integrating such systems with standard protocols (e.g., IEEE 802.11ad) is crucial for the deployment of location-based services, but it is also challenging and limits the design choices. Another key problem is that consumer-grade 60 GHz hardware only provides coarse channel state information, and has highly irregular beam shapes due to its cost-efficient design. In this paper, we explore the location accuracy that can be achieved using such hardware, without modifying the 802.11ad standard. We consider a typical 802.11ad indoor network with multiple access points (APs). Each AP collects the coarse signal-to-noise ratio of the directional beacons that clients transmit periodically. Given the irregular beam shapes, the challenge is to relate each beacon to a set of transmission angles that allows to triangulate a user. We design a location system based on particle filters along with linear programming and Fourier analysis. We implement and evaluate our algorithm on commercial off-the-shelf 802.11ad hardware in an office scenario with mobile human blockage. Despite the strong limitations of the hardware, our system operates in real-time and achieves sub-meter accuracy in 70% of the cases.

This paper presents FreeIoT, a control plane paradigm that allows fine grained signaling for city-scale IoT deployments without installing any additional infrastructure. FreeIoT overlays control/wake-up information for sensors over existing standards compliant LTE through the following contributions: First, we develop a novel encoding scheme that changes the spatial positioning of Almost Blank Subframes (ABS) within a standard LTE frame to convey control information. ABS was originally defined in the standard to allow coexistence between the macro-cell eNB and nearby small cells, which FreeIoT leverages as a side channel for IoT signaling. Our approach works with any number of ABS settings chosen by the LTE eNB, and accordingly adjusts the encoding of control messages at maximum possible transmission rates. Second, a session management protocol is introduced to maintain contextual information of the control signaling. This allows FreeIoT to handle situations where the control message may span multiple frames, or when the LTE operator temporarily reduces the number of ABS. FreeIoT also incorporates an error detection and correction mechanism to counter channel and fading errors. Finally, we implement a proof of concept testbed to validate the operation of FreeIoT using a software defined LTE eNB and custom-designed RF energy harvesting circuit interfaced with off-the-shelf sensors.

Modern communication technologies are expected to be available in the future Smart Grids to enable the control of equipments over the whole power grid. In this paper, we consider such networked control approach to address failures that may occur at any location of the grid, due to attacks or unit malfunction, and provide a wide-scale solution that prevent the failure impacts from spreading over a large area. Different from literature work that focuses on modifying power equations under the standard constraints of the power system, we estimate the impact of controlling different nodes on topological areas of the grid based on social metrics, which are derived from the graph capturing both the topological and electrical properties of the power grid. We propose a failure control algorithm for topological containment of failures in smart grid. Our algorithm also takes careful consideration of the impact the planned control has on the grid to avoid the possibly involuntary failure extension. We show that social metrics can efficiently trade off between the topological and electrical characteristics revealed by the power grid graph representation. We evaluate the performance against networked control strategies that only use power models to determine the actions to be performed at power nodes. Our results show that the proposed control scheme can effectively contain failures within their original location range.

Smart mobile devices have become an integral part of people's life and users often input sensitive information on these devices. However, various side channel attacks against mobile devices pose a plethora of serious threats against user security and privacy. To mitigate these attacks, we present a novel secure Back-of-Device (BoD) input system, SecTap, for mobile devices. To use SecTap, a user tilts her mobile device to move a cursor on the keyboard and tap the back of the device to secretly input data. We design a tap detection method by processing the stream of accelerometer readings to identify the user's taps in real time. The orientation sensor of the mobile device is used to control the direction and the speed of cursor movement. We also propose an obfuscation technique to randomly and effectively accelerate the cursor movement. This technique not only preserves the input performance but also keeps the adversary from inferring the tapped keys. Extensive empirical experiments were conducted on different smart phones to demonstrate the usability and security on both Android and iOS platforms.

As demand for Internet usage increases, Internet service providers (ISPs) have begun to explore pricing-based solutions to dampen data demand. However few explicitly consider the dual problem of monetizing idle network capacity at uncongested times. PopData is a recent initiative from Verizon that does so by offering supplemental discount offers (SDOs) at these times, in which users can pay a fixed fee in exchange for unlimited data in the next hour. This work is the first of its kind to assess the benefits and viability of SDOs by modeling user and ISP decisions as a game, considering both overall monthly decisions and hour-to-hour decisions throughout the month. We first use our monthly model to show that users are generally willing to accept some SDO offers, allowing the ISP to increase its revenue. We then show that users face a complex hourly decision problem as to which SDOs they should accept over their billing cycles, since they are unaware of their exact future needs or when future SDOs will be made. The ISP faces a similarly challenging problem in deciding when to offer SDOs so as to maximize its revenue, subject to users' decisions. We develop optimal decision criteria for users and ISPs to decide whether to make or accept SDO offers. Our analysis shows that both users and ISPs can benefit from these offers, and we verify this through numerical experiments on a one-week trace of 20 cellular data users. We find that ISPs can exploit user uncertainty in when future SDOs will be made to optimize its revenue.

Software Defined Network (SDN) enables flexible update of network functions with a well-defined abstraction between the control and the data plane. However, multiple active network functions with the same priority will potentially trigger conflicts among policies with overlapped flow space, causing the flow table explosion. In contrast to the local switch conflict resolution schemes proposed by previous works, this paper tackles the same problem from a different angle and resolves the policy conflict problem by coordinating all switches under a global centralized view. Specifically, we propose COnflict RAzor (CORA), which tremendously reduces the storage cost of conflicting policies leveraging the global network information obtained in the controller. The basic idea of CORA is migrating policies causing large explosions across the network if necessary, while keeping the semantics equivalence. We prove CORA's NP hardness and propose a heuristic to efficiently search a near-optimal policy migration strategy. Our experiments demonstrate that, CORA can effectively reduce the flow table storage occupation by at least 49% within less than 40 seconds.

We address the problem of trust establishment between wireless devices that do not share any prior secrets. This includes the mutual authentication and agreement to a common key that can be used to further bootstrap essential cryptographic mechanisms. We propose SFIRE, a secret-free trust establishment protocol that allows the secure pairing of commercial off-the-shelf (COTS) wireless devices with a hub. Compared to the state-of-the-art, SFIRE does not require any out-of-band channels, special hardware, or firmware modification, but can be applied to any COTS device. Moreover, SFIRE is resistant to the most advanced active signal manipulations that include recently demonstrated signal nullification at an intended receiver. These security properties are achieved in-band with the assistance of a helper device such as a smartphone and by using the RSS fluctuation patterns to build a robust “RSS authenticator”. We perform extensive experiments using COTS devices and USRP radios and verify the validity of the proposed protocol.

We study the user association problem in the context of dense networks, where standard adaptive algorithms become ineffective. The paper proposes a novel data-driven technique leveraging the theory of robust optimization. The main idea is to predict future traffic fluctuations, and use the predictions to design association maps before the actual arrival of traffic. Although the actual playout of the map is random due to prediction error, the maps are robustly designed to handle uncertainty, preventing constraint violations, and maximizing the expectation of a convex utility function, which allows to accurately balance base station loads. We propose a generic iterative algorithm, referred to as GRMA, which is shown to converge to the optimal robust map. The optimal maps have the intriguing property that they jointly optimize the predicted load and the variance of the prediction error. We validate our robust maps in Milano-area traces, with dense coverage and find that we can reduce violations from 25% (achieved by an adaptive algorithm) down to almost zero.

Efficient algorithmic solutions for multi-field packet classification have been a challenging problem for many years. This problem is becoming even worse in the era of Software Defined Network (SDN), where flow tables with increasing complexities are playing a central role in the forwarding plane of SDN. In this paper, we first conduct an unprecedented in-depth reasoning on issues that led to the unsuccess of the major quests for scalable algorithmic solutions. With the insights obtained, we propose a practical framework called CutSplit, which can exploit the benefits of cutting and splitting techniques adaptively. By addressing the central problem caused by uncontrollable rule replications suffered by the major efforts, CutSplit not only pushes the performance of algorithmic packet classification more closely to hardware-based solutions, but also reduces the memory consumption to a practical level. Moreover, our work achieves low pre-processing time for rule updates, a problem that has long been ignored by previous decision-trees, but is becoming more relevant in the context of SDN due to frequent updates of rules. Experimental results show that using ClassBench, CutSplit achieves a memory reduction over 10 times, as well as 3x improvement on performance in terms of the number of memory access on average.

We study the problem to maximize the profit for a social network host who offers viral marketing to multiple company campaigners. Each campaigner has its special interest for social network users, and she pays the host commission when a target user adopts her product. The campaigners decide the cost they are willing to pay for viral marketing, and the host collects cost from all campaigners and uses it for marketing. We call our optimization problem Competitive PROfit maximization for the host (CPro), and its solution is the seed allocation for campaigners, such that the profit (commission) campaigners given back to the host is maximized. CPro is NP-hard with a non-monotone and non-submodular objective function, which means existing techniques in influence or profit maximization cannot give guaranteed performance. To solve this issue, we design an efficient approximation algorithm that works on billion-scale networks, and more importantly, we give the performance bound of our algorithm. As far as we know, this is the first bounded scalable approximation algorithm for competitive profit maximization. A comprehensive set of experiments are set on various real networks with up to several billion edges from diverse disciplines, and our solution identifies the top choices for the host in only a few minutes on network that contains 1.5 billion edges.