INFOCOM 2018 Papers

We consider the multichannel opportunistic access problem, in which a user decides, at each time slot, which channel to access among multiple Gilbert-Elliot channels in order to maximize his aggregated utility (e.g., the expected transmission throughput) given that the observation of channel state is error-prone. The problem can be cast into a restless multiarmed bandit problem which is proved to be PSPACE-Hard. An alternative approach, given the problem hardness, is to look for simple channel access policies. Whittle index policy is a very popular heuristic for restless bandits, which is provably optimal asymptotically and has good empirical performance. In the case of imperfect observation, the traditional approach of computing the Whittle index policy cannot be applied because the channel state belief evolution is no more linear, thus rendering the indexability of our problem open. In this paper, we mathematically establish the indexability and establish the closed-form Whittle-index, based on which index policy can be constructed. The major technique in our analysis is a fixed point based approach which enable us to divide the belief information space into a series of regions and then establish a set of periodic structures of the underlying nonlinear dynamic evolving system, based on which we devise the linearization scheme for each region to establish indexability and compute the Whittle index for each region.

Mobile devices such as smartphones are enabling users to generate and share videos with increasing rates. In some cases, these videos may contain valuable information, which can be exploited for a variety of purposes. However, instead of centrally collecting and processing videos for information retrieval, we consider crowdprocessing videos, where each mobile device locally processes stored videos. While the computational capability of mobile devices continues to improve, processing videos using deep learning, i.e., convolutional neural networks, is still a demanding task for mobile devices. To this end, we design and build CrowdVision, a computing platform that enables mobile devices to crowdprocess videos using deep learning in a distributed and energy-efficient manner leveraging cloud offload. CrowdVision can quickly and efficiently process videos with offload under various settings and different network connections and greatly outperform the existing computation offload framework (e.g., with a 2× speed-up). In doing so CrowdVision tackles several challenges: (i) how to exploit the characteristics of the computing of deep learning for video processing; (ii) how to parallelize processing and offloading for acceleration; and (iii) how to optimize both time and energy at runtime by just determining the right moments to offload.

Coflow has recently been introduced to capture communication patterns that are widely observed in the cloud and massively parallel computing. Coflow consists of a number of flows that each represents data communication from one machine to another. A coflow is completed when all of its flows are completed. Due to its elegant abstraction of the complicated communication processes found in various parallel computing platforms, it has received significant attention. In this paper, we consider coflow for the objective of maximizing partial throughput. This objective seeks to measure the progress made for partially completed coflows before their deadline. Partially processed coflows still could be useful when their flows send out useful data that can be used for the next round computation. In our measure, a coflow is processed by a certain fraction when all of its flows are processed by the same fraction or more. We consider a natural class of greedy algorithms, which we call myopic concurrent. The algorithms seek to maximize the marginal increase of the partial throughput objective at each time. We analyze the performance of our algorithm against the optimal scheduler. In fact, our result is more general as a flow could be extended to demand various heterogeneous resources. Our experiment demonstrates our algorithm's superior performance.

Parallel computing combined with distributed data storage and management has been widely adopted by most big data analytics systems. Scheduling computing tasks to improve data locality is crucial to the performance of such systems. While existing schedulers target near-data scheduling on top of physical data blocks, these systems face a new scheduling problem where computing tasks process table-based datasets directly and access large physical blocks indirectly through their indices stored in associated small logical blocks. This new problem invalidates the basic assumption made by many existing algorithms on near-data scheduling. In this paper, we propose a Logical-block Affinity Scheduling (LAS) algorithm to coordinate the near-data scheduling of computing tasks and the placement of logical blocks for a desired balance between data-locality and load-balancing to maximize system throughput. The proposed algorithm is implemented and evaluated using a well-known big data benchmark and a practical production system deployed in public clouds. Extensive experimental results illustrate the performance superiority of LAS over three existing scheduling algorithms.

This paper considers the problem of designing the user trajectory in a device-to-device communications setting. We consider a pair of pedestrians connected through a D2D link. The pedestrians seek to reach their respective destinations, while using the D2D link for data exchange applications such as file transfer, video calling, and online gaming. In order to enable better D2D connectivity, the pedestrians are willing to deviate from their respective shortest paths, at the cost of reaching their destinations slightly late. A generic trajectory optimization problem is formulated and solved for the case when full information about the problem in known in advance. Motivated by the D2D user's need to keep their destinations private, we also formulate a regularized variant of the problem that can be used to develop a fully online algorithm. The proposed online algorithm is quite efficient, and is shown to achieve a sublinear offline regret while satisfying the required mobility constraints exactly. The theoretical results are backed by detailed numerical tests that establish the efficacy of the proposed algorithms under various settings.

Indoor positioning systems (IPSes) can enable many location-based services in large indoor environments where GPS is not available or reliable. Mobile crowdsourcing is widely advocated as an effective way to construct IPS maps. This paper presents the first systematic study of security issues in crowd-sourced WiFi-based IPSes to promote security considerations in designing and deploying crowdsourced IPSes. We identify three attacks on crowdsourced WiFi-based IPSes and propose the corresponding countermeasures. The efficacy of the attacks and also our countermeasures are experimentally validated on a prototype system. The attacks and countermeasures can be easily extended to other crowdsourced IPSes.

We investigate competitive online algorithms for online convex optimization (OCO) problems with linear in-stage costs, switching costs and ramp constraints. While OCO problems have been extensively studied in the literature, there are limited results on the corresponding online solutions that can attain small competitive ratios. We first develop a powerful computational framework that can compute an optimized competitive ratio based on the class of affine policies. Our computational framework can handle a fairly general class of costs and constraints. Compared to other competitive results in the literature, a key feature of our proposed approach is that it can handle scenarios where infeasibility may arise due to hard feasibility constraints. Second, we design a robustification procedure to produce an online algorithm that can attain good performance for both average-case and worst-case inputs. We conduct a case study on Network Functions Virtualization (NFV) orchestration and scaling to demonstrate the effectiveness of our proposed methods.

This paper takes the first step in studying the problem of range query for sensor-augmented RFID systems, which is to classify the target tags according to the range of tag information. The related schemes that seem to address this problem suffer from either low time-efficiency or the information corruption issue. To overcome their limitations, we first propose a basic classification protocol called Range Query (RQ), in which each tag pseudo-randomly chooses a slot from the time frame and uses the ON-OFF Keying modulation to reply its range identifier. Then, RQ employs a collaborative decoding method to extract the tag information range from even collision slots. The numerical results reveal that the number of queried ranges significantly affects the performance of RQ. To optimize the number of queried ranges, we further propose the Partition&Mergence (PM) approach that consists of two steps, i.e., top-down partitioning and bottom-up merging. Sufficient theoretical analyses are proposed to optimize the involved parameters, thereby minimizing the time cost of RQ+PM. The prominent advantages of RQ+PM over previous schemes are two-fold: (i) it is able to make use of the collision slots, which are treated as useless in the previous schemes; (ii) it is immune to the interference from unexpected tags. We use the USRP and WISP tags to conduct a set of experiments, which demonstrate the feasibility of RQ+PM. Moreover, extensive simulation results reveal that RQ+PM can ensure 100% query accuracy, meanwhile reducing the time cost as much as 40% comparing with the existing schemes.

Social recommendation has been widely applied to offer users suggestions on who to connect to, where most existing strategies overlook the existence of multi-type connections among users. To overcome such limitation, we characterize each type of connections by a corresponding network layer and then propose a novel algorithm for joint recommendations in cross-layer social networks. Particularly, two types of results are presented in the paper. (i) Our proposed algorithm, named as Cross-layer 2-hop Path (C2P) algorithm, implements the joint recommendation by suggesting a user establish connections to his cross-layer two-hop neighbors, i.e., those who link to the user by two-hop paths with the two hops belonging to two different layers, respectively. In doing so, each produced recommendation item is a combination of user relationships in both two layers and thus can better meet user demands. (ii) By analytical derivations, along with further empirical validation on real datasets, we give the performance evaluation on our proposed algorithm. Firstly, we prove that the algorithm is efficiently implementable with a constant complexity in each recommendation. Then, we evaluate its recommendation performance by two metrics, i.e., acceptance and diversity, where the former metric measures recommendation accuracy and the latter one measures an algorithm's capability to provide diverse recommendation items. Our results show that C2P algorithm is optimal in terms of acceptance and for diversity, its performance is in the same order of the theoretical upperbound. And finally, the effectiveness of the proposed algorithm is validated by our simulations on three real datasets, where it outperforms baseline algorithms with an up to 38% acceptance gain and obtains an around 0.5 diversity ratio to the theoretical upperbound.

Cognitive Radio (CR) has garnered much attention in the last decade, while the security issues are not fully studied yet. Existing research on attacks and defenses in CR - based networks focuses mostly on individual network layers, whereas cross-layer attacks remain fortified against single-layer defenses. In this paper, we shed light on a new vulnerability in cross-layer routing protocols and demonstrate how a perpetrator can exploit this vulnerability to manipulate traffic flow around it. We propose this cross-layer attack in CR-based wireless mesh networks (CR-WMNs), which we call off-sensing and route manipulation (OS-RM) attack. In this cross-layer assault, off-sensing attack is launched at the lower layers as the point of attack but the final intention is to manipulate traffic flow around the perpetrator. We also introduce a learning strategy for a perpetrator, so that it can gather information from the collaboration with other network entities and capitalize this information into knowledge to accelerate its malice intentions. Simulation results show that this attack is far more detrimental than what we have experienced in the past and need to be addressed before commercialization of CR-based networks.

List-based caches can offer lower miss rates than single-list caches, but their analysis is challenging due to state-space explosion. We analyze in this setting randomized replacement policies for caches with non-uniform access costs. In our model, costs can depend on the stream a request originated from, the target item, and the list that contains it. We first show that, similarly to the uniform-cost case, the random replacement (RR) and first-in first-out (FIFO) policies can be exactly analyzed using a product-form expression for the equilibrium state probabilities of the cache. We then tackle the state space explosion by means of the singular perturbation method, deriving limiting expressions for the equilibrium performance measures as the number of items and the cache capacity grow in a fixed ratio. Simulations indicate that our asymptotic formulas rapidly converge to the cache equilibrium distribution.

Age of Information (AoI) is a performance metric that captures the freshness of the information from the perspective of the destination. The AoI measures the time that elapsed since the generation of the packet that was most recently delivered to the destination. In this paper, we consider a single-hop wireless network with a number of nodes transmitting time-sensitive information to a Base Station and address the problem of minimizing the Expected Weighted Sum AoI of the network while simultaneously satisfying timely-throughput constraints from the nodes. We develop three low-complexity transmission scheduling policies that attempt to minimize AoI subject to minimum throughput requirements and evaluate their performance against the optimal policy. In particular, we develop a randomized policy, a Max-Weight policy and a Whittle's Index policy, and show that they are guaranteed to be within a factor of two, four and eight, respectively, away from the minimum AoI possible. In contrast, simulation results show that Max-Weight outperforms the other policies, both in terms of AoI and throughput, in every network configuration simulated, and achieves near optimal performance.

Eccentricity detection is a crucial issue for highspeed rotating machinery, which concerns the stability and safety of the machinery. Conventional techniques in industry for eccentricity detection are mainly based on measuring certain physical indicators, which are costly and hard to deploy. In this paper, we propose RED, a non-intrusive, low-cost, and realtime RFID-based eccentricity detection approach. Differing from the existing RFID-based sensing approaches, RED utilizes the temporal and phase distributions of tag readings as effective features for eccentricity detection. RED includes a Markov chain based model called RUM, which only needs a few sample readings from the tag to make a highly accurate and precise judgement. We implement RED with commercial-of-the-shelf RFID reader and tags, and evaluate its performance across various scenarios. The overall accuracy is 93.59% and the detection latency is 0.68 seconds in average.

VM redundancy is the foundation of resilient cloud applications. While active-active approaches combined with load balancing and autoscaling are usually resource efficient, the stateful nature of many cloud applications often necessitates 1+1 (or 1+n) active-standby approaches. Keeping the standbys, however, could result in inefficient utilization of cloud resources. We explore an intriguing cloud-based solution, where standby VMs from active-standby applications are selectively overbooked to reduce resources reserved for failures. The approach requires careful VM placement to avoid a situation where multiple standby VMs activate simultaneously on the same host and thus cannot get the full resource entitlement. Indeed today's clouds do not have this visibility to the applications. We rectify this situation through ShadowBox, a novel redundancy-aware VM scheduler that optimizes the placement and activation of standby VMs, while assuring applications' resource entitlements. Evaluation on a large-scale cloud shows that ShadowBox can significantly improve resource utilization (i.e., more than 2.5 times than traditional approaches) while minimizing the impact on applications' entitlements.

Nowadays, video surveillance systems are widely deployed in various places, e.g., schools, parks, airports, roads, etc. However, existing video surveillance systems are far from full utilization due to high computation overhead in video processing. In this work, we present ViTrack, a framework for efficient multi-video tracking using computation resource on the edge for commodity video surveillance systems. In the heart of ViTrack lies a two layer spatial/temporal compressive target detection method to significantly reduce the computation overhead by combining videos from multiple cameras. Further, ViTrack derives the video relationship and camera information even in absence of camera location, direction, etc. To address variant video quality and missing targets, ViTrack leverages a Markov Model based approach to efficiently recover missing information and finally derive the complete trajectory. We implement ViTrack on a real deployed video surveillance system with 110 cameras. The experiment results demonstrate that ViTrack can provide efficient trajectory tracking with processing time 45x less than the existing approach. For 110 video cameras, ViTrack can run on a Dell OptiPlex 390 computer to track given targets in almost real time. We believe ViTrack can enable practical video analysis for widely deployed commodity video surveillance systems.

Per-flow traffic measurement is a fundamental problem in the era of big network data, and has been widely used in many applications, including capacity planning, anomaly detection, load balancing, traffic engineering, etc. In order to keep up with the line speed of modern network devices (e.g., routers), per-flow measurement online module is often implemented by using on-chip cache memory (such as SRAM) to minimize per-packet processing time, but on-chip SRAM is expensive and limited in size, which poses a major challenge for traffic measurement. In response, much recent research is geared towards designing highly compact data structures for approximate estimation that can provide probabilistic guarantees for per-flow measurement. The state of art, called Counter Tree (CT), requires at least 2 bits per flow in memory consumption and more than 2 memory accesses per packet in processing time. In this paper, we propose a novel design of a highly compact and efficient counter architecture, called Virtual Active Counter estimation (VAC), which achieves faster processing speed (slightly more than 1 memory access per packet on average) and provides more accurate measurement results than CT under the same allocated memory. Moreover, VAC can perform well even with a very tight memory space (less than 1 bit per flow or even one fifth of a bit per flow). Theoretical analysis and experiments based on real network traces demonstrate the superior performance of VAC.

Utilizing advanced communication technologies to facilitate power system monitoring and control, the smart grid is envisioned to be more robust and resilient against cascading failures. Although the integration of communication network does benefit the smart grid in many aspects, such benefits should not overshadow the fact that the interdependence between the communication network and the power infrastructure makes the smart grid more fragile to cascading failures. Thus, it is essential to understand the impact of such cyber-physical integration with interdependence from both positive and negative perspectives. In this paper, we develop a systematic framework to analyze the benefits and drawbacks of the cyber-physical interdependence. We use theoretical analysis and system-level simulations to characterize the impact of such interdependence. We identify two phases during the progress of failure propagation where the integrated communication and interdependence helps and hinders the mitigation of the failure, respectively, which provides practical guidance to smart grid system design and optimization.

Decentralizing content delivery to edge devices has become a popular solution for saving the bandwidth consumption of CDN when the CDN bandwidth is expensive. One successful realization is the hybrid CDN-P2P VoD system, where a client is allowed to request video content from a number of seeds (seed clients) in the P2P network. However, the seed scarcity problem may arise for a video resource when there are an insufficient number of seeds to satisfy requests to the video. To alleviate this problem, many commercial VoD systems have employed a video push mechanism that directly sends the recent scarce video resources to randomly-chosen seeds to serve more requests. However, the current video push mechanism fails to consider which videos will become scarce in the future, or differentiate the uploading capability of different seeds. In this paper, we propose Proactive-Push, a video push mechanism that lowers the bandwidth consumption of CDN by predicting future scarce videos and proactively sending them to competent seeds with strong uploading capabilities. Proactive-Push trains neural network models to correctly predict 80% of future scarce video resources, and identify over 90% of competent seeds. We evaluate Proactive-Push using a trace-driven emulation and a real-world pilot deployment over a commercial VoD system. Results show that Proactive-Push can further reduce the proportion of direct download from CDN by 21%, and save the CDN bandwidth cost at peak time by 18%.

Typosquatting is a blackhat practice that relies on human error and low-cost domain registrations to hijack legitimate traffic from well-established websites. The technique is typically used for phishing, driving traffic towards competitors or disseminating indecent or malicious content and as such remains a concern for businesses. We take a fresh new look at this well-studied phenomenon to explore why some URLs are more vulnerable to typing mistakes than others. We explore the relationship between human hand anatomy, keyboard layouts and typing mistakes using various URL datasets. We create an extensive user-centric typographical model and compute a Hardness Quotient (likelihood of mistyping) for each URL using a quantitative measure for finger and hand effort. Furthermore, our model predicts the most likely typos for each URL which can then be defensively registered. Cross-validation against actual URL and DNS datasets suggests that this is a meaningful and effective defense mechanism.