INFOCOM 2018 Papers

Graph analytics has emerged as one of the fundamental techniques to support modern Internet applications. As real-world graph data is generated and stored globally, the scale of the graph that needs to be processed keeps growing. It is critical to efficiently process graphs across multiple geographically distributed datacenters, running wide-area graph analytics. Existing graph analytics frameworks are not designed to run across multiple datacenters well, as they implement a Bulk Synchronous Parallel model that requires excessive wide-area data transfers. In this paper, we present a new Hierarchical Synchronous Parallel model designed and implemented for synchronization across datacenters with a much improved efficiency in inter-datacenter communication. Our new model requires no modifications to graph analytics applications, yet guarantees their convergence and correctness. Our prototype implementation on Apache Spark can achieve up to 32% lower WAN bandwidth usage, 49% faster convergence, and 30% less total cost for benchmark graph algorithms, with input data stored across five geographically distributed datacenters.

We consider the problem of transmitting at the optimal rate over a rapidly-varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mm Wave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called Modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.

Approximate graph matching refers to the problem of finding the best correspondence between the node labels of two correlated graphs. The problem has been applied to a number of domains, including social network de-anonymization. Recently, a number of algorithms have been proposed for seeded graph matching, which uses a few seed matches between two graphs to determine the remaining correspondence. We adapt the ideas from seeded algorithms to develop a graph matching correction algorithm, which takes a partially correct correspondence as input and returns an improved correspondence. We show that this algorithm can correct all errors in graph matching for stochastic block model graphs with high probability. Finally, we apply our algorithm as a post-processing step for other approximate graph matching algorithms to significantly improve the performance of state-of-the-art algorithms for seedless graph matching.

State-of-the-art cloud platforms adopt pay-as-you-go pricing, where users pay for the resources on demand according to occupation time. Simple and intuitive as it is, such a pricing scheme is a mismatch for new workloads today such as large-scale machine learning, whose completion time is hard to estimate beforehand. To supplement existing cloud pricing schemes, we propose an occupation-oblivious online pricing mechanism for cloud jobs without pre-specified time duration and for users who prefer a pre-determined cost for job execution. Our strategy posts unit resource prices upon user arrival and decides a fixed charge for completing the user's job, without the need to know how long the job is to occupy the requested resources. At the core of our design is a novel multi-armed bandit based online learning algorithm for estimating unknown input by exploration and exploitation of past resource sales, and deciding resource prices to maximize profit of the cloud provider in an online setting. Our online learning algorithm achieves a low regret sublinear with the time horizon, in terms of overall provider profit, compared with an omniscient benchmark. We also conduct trace-driven simulations to verify efficacy of the algorithm in real-world settings.

Traditional mobile crowdsensing photo selection process focuses on selecting photos from participants to a server. The server may contain tons of photos for a certain area. A new problem is how to select a set of photos from the server to a smartphone user when the user requests to view an area (e.g., a hot spot). The challenge of the new problem is that the photo set should attain both photo coverage and view quality (e.g., with clear Points of Interest). However, contributions of these geo-tagged photos could be uncertain for a target area due to unavailable information of photo shooting direction and no reference photos. In this paper, we propose a novel and generic server-to-requester photo selection approach. Our approach leverages a utility measure to quantify the contribution of a photo set, where photos' spatial distribution and visual correlation are jointly exploited to evaluate their performance on photo coverage and view quality. Finding the photo set with the maximum utility is proven to be NP-hard. We then propose an approximation algorithm based on a greedy strategy with rigorous theoretical analysis. The effectiveness of our approach is demonstrated with real-world datasets. The results show that the proposal outperforms other approaches with much higher photo coverage and better view quality.

Collaborative uploading describes a type of crowd-sourcing scenario in networked environments where a device utilizes multiple paths over neighboring devices to upload content to a centralized processing entity such as a cloud service. Intermediate devices may aggregate and preprocess this data stream. Such scenarios arise in the composition and aggregation of information, e.g., from smart phones or sensors. We use a queuing theoretic description of the collaborative uploading scenario, capturing the ability to split data into chunks that are then transmitted over multiple paths, and finally merged at the destination. We analyze replication and allocation strategies that control the mapping of data to paths and provide closed-form expressions that pinpoint the optimal strategy given a description of the paths' service distributions. Finally, we provide an online path-aware adaptation of the allocation strategy that uses statistical inference to sequentially minimize the expected waiting time for the uploaded data. Numerical results show the effectiveness of the adaptive approach compared to the proportional allocation and a variant of the join-the-shortest-queue allocation, especially for bursty path conditions.

In this paper, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. We conduct both simulations and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 %.

Wireless network simulation is a fundamental service aiming at providing controlled and repeatable environment for protocol design, performance testing, etc. The existing simulators focus on reproducing the packet behaviors on individual links. However, as observed in some recent works, individual link behaviors alone are not enough to characterize the protocol performance. As a result, while the existing works can mimic the link behaviors very closely, they often fail to simulate protocol level performance. In this paper, we propose a novel performance-aware simulation approach which can preserve not only the link-level behaviors but also the performance-level behaviors. We first devise an accurate performance model by combining link quality and the spatial-temporal link correlation. Based on the performance modeling, we then propose a Performance Aware Hidden Markov Model (PA-HMM), where the protocol performance is directly fed into the Markov state transitions. PA-HMM is able to simulate both link-level behaviors and high-level protocol performance. We conduct extensive testbed and simulation experiments with broadcast and anycast protocols. The results show that compared to the state-of-the-art work, 1) the performance model is able to accurately characterize wireless communication performance and 2) the protocol performance is closely simulated as compared to the empirical results.

Unlicensed spectrum has been viewed as a way to increase competition in wireless access and promote innovation in new technologies and business models. However, several recent papers have shown that the openness of such spectrum can also lead to it becoming over congested when used by competing wireless service providers (SPs). This in turn can result in the SPs making no profit and may deter them from entering the market. However, this prior work assumes that unlicensed access is a separate service from any service offered using licensed spectrum. Here, we instead consider the more common case were service providers bundle both licensed and unlicensed spectrum as a single service and offer this with a single price. We analyze a model for such a market and show that in this case SPs are able to gain higher profit than the case without bundling. It is also possible to get higher social welfare with bundling. Moreover, we explore the case where SPs are allowed to manage the customers' average percentage of time they receive service on unlicensed spectrum and characterize the social welfare gap between the profit maximizing and social welfare maximizing setting.

In order to evaluate the expected availability of a service, a network administrator should consider all possible failure scenarios under the specific service availability model stipulated in the corresponding service-level agreement. Given the increase in natural disasters and malicious attacks with geographically extensive impact, considering only independent single link failures is often insufficient. In this paper, we build a stochastic model of geographically correlated link failures caused by disasters, in order to estimate the hazards a network may be prone to, and to understand the complex correlation between possible link failures. With such a model, one can quickly extract information, such as the probability of an arbitrary set of links to fail simultaneously, the probability of two nodes to be disconnected, the probability of a path to survive a failure, etc. Furthermore, we introduce a pre-computation process, which enables us to succinctly represent the joint probability distribution of link failures. In particular, we generate, in polynomial time, a quasilinear-sized data structure, with which the joint failure probability of any set of links can be computed efficiently.

This paper addresses the problem of inferring link loss rates based on network performance tomography in noisy network systems. Since the network tomography emerged, all existing tomography-based methods are limited to the basic condition that both network topologies and end-to-end routes must be absolutely accurate, which in most cases is impractical, especially for large-scale heterogeneous networks. To overcome the impracticability of tomography-based methods, we propose a robust tomography-based loss inference method capable of accurately inferring all link loss rates even when the network system may change dynamically. The new method first measures the end-to-end loss rates of selected paths to reduce the probing cost, and then calculates an upper bound for the loss rate of each link using the measurement results. Finally, it finds all the link loss rates that most closely conform to the measurement results within their upper bounds. Compared with two traditional loss inference methods (with and without path selection, respectively), the results strongly confirm the promising performance of our proposed approach.

With the emergence of Internet of Things, mobile devices are generating more network traffic than ever. TrustZone is a hardware-enabled trusted execution environment for ARM processors. While TrustZone is effective in providing the much-needed memory isolation, we observe that it is possible to derive secret information from secure world using the cache contention, due to its high-performance cache sharing design. In this work, we propose TruSense to study the timing-based cache side-channel information leakage of TrustZone. TruSense can be launched from not only the normal world operating system but also a non-privileged user application. Without access to virtual-to-physical address mapping in user applications, we devise a novel method that uses the expected channel statistics to allocate memory for cache probing. We also show how an attacker might use the less accurate performance event interface as a timer. Using the T-table based AES implementation in OpenSSL 1.0.1f as an example, we demonstrate how a normal world attacker can steal fine-grained secret in the secure world. We also discuss possible mitigations for the information leakage.

Heterogeneous cellular networks (HetNets) can significantly improve the spectrum efficiency, where low-power low-complexity base stations (Pico-BSs) are deployed inside the coverage of macro base stations (Macro-BSs). Due to cross-tier interference, joint detection of the uplink signals is widely adopted so that a Pico-BS can either detect the uplink signals locally or forward them to the Macro-BS for processing. The latter can achieve increased throughput at the cost of additional backhaul transmission. However, in existing literature the delay of the backhaul links was often neglected. In this paper, we study the delay-optimal uplink scheduling problem in HetNets with limited backhaul capacity. Local signal detection or joint signal detection is scheduled in a unified delay-optimal framework. Specifically, we first prove that the problem is NP-hard and then formulate it as a Markov Decision Process problem. We propose an efficient and effective algorithm, called OLIUS, that can deal with the exponentially growing state and action spaces. Furthermore, OLIUS is online learning based which does not require any prior statistical knowledge on user behavior or channel characteristics. We prove the convergence of OLIUS and derive an upper bound on its approximation error. Extensive experiments in various scenarios show that our algorithm outperforms existing methods in reducing delay and power consumption.

360-degree video has the potential to transform the video streaming experience by providing a more-immersive environment for users to interact with than standard streaming video. This experience is hampered, however, by high bandwidth requirements resulting from the extra information associated with the 360-degree frames. Because users cannot see this full 360-degree view, but the full view is transmitted in the majority of 360-degree streaming systems, there is much potential to reduce wasted bandwidth in this domain. We propose ClusTile, a tiling approach formulated to select a set of tiles that allows minimal bandwidth needed to be used when streaming 360-degree video over an expected set of views. These tiles are selected by solving a set of integer linear programs (ILPs) independently on clusters of collected user views. The clustering approach reduces computation requirements of the ILPs to practical levels. Tilings computed from ClusTile can save up to 76% bandwidth compared to standard 360-degree streaming and up to 52% bandwidth compared to best-performing fixed tiling schemes.

Mobile augmented reality (MAR) involves high complexity computation which cannot be performed efficiently on resource limited mobile devices. The performance of MAR would be significantly improved by offloading the computation tasks to servers deployed with the close proximity to the users. In this paper, we design an edge network orchestrator to enable fast and accurate object analytics at the network edge for MAR. The measurement-based analytical models are built to characterize the tradeoff between the service latency and analytics accuracy in edge-based MAR systems. As a key component of the edge network orchestrator, a server assignment and frame resolution selection algorithm named FACT is proposed to mitigate the latency-accuracy tradeoff. Through network simulations, we evaluate the performance of the FACT algorithm and show the insights on optimizing the performance of edge-based MAR systems. We have implemented the edge network orchestrator and developed the corresponding communication protocol. Our experiments validate the performance of the proposed edge network orchestrator.

As the Internet-of-Things (IoT) emerges, connecting immense numbers of sensors and devices, the continual growth in wireless communications increasingly manifests itself in terms of a larger and denser population of nodes with intermittent traffic patterns. A crucial issue that arises in these conditions is how to set the activation rates as a function of the network density and traffic intensity. Depending on the scaling of the activation rates, dense node populations may either result in excessive activations and potential collisions, or long delays that may increase with the number of nodes, even at low load. Motivated by the above issues, we examine optimal activation rate scalings in ultra-dense networks with intermittent traffic sources. We establish stability conditions, and provide closed-form expressions which indicate that the mean delay is roughly inversely proportional to the nominal activation rate. We also discuss a multi-scale mean-field limit, and use the associated fixed point to determine the buffer content and delay distributions. The results provide insight in the scalings that minimize the delay while preventing excessive activation attempts. Extensive simulation experiments demonstrate that the mean-field asymptotics yield highly accurate approximations, even when the number of nodes is moderate.

Coflow scheduling is crucial to improve the communication performance of data-parallel jobs, especially when these jobs running in the inter-datacenter networks with limited and heterogeneous link bandwidth. However, prior solutions on coflow scheduling assume the endpoints of flows in a coflow to be fixed, making them insufficient to optimize the coflow completion time (CCT). In this paper, we focus on the problem of jointly considering endpoint placement and coflow scheduling to minimize the average CCT of coflows across geo-distributed datacenters. We first develop the mathematical model and formulate a mixed integer linear programming (MILP) problem to characterize the intertwined relationship between endpoint placement and coflow scheduling, and reveal their impact on the average CCT. Then, we present SmartCoflow, a coflow-aware optimization framework, to solve the MILP problem without any prior knowledge of coflow arrivals. In SmartCoflow, we first apply an approximate algorithm to obtain the endpoint placement and scheduling decisions for a single coflow. Based on the single-coflow solution, we then develop an efficient online algorithm to handle the dynamically arrived coflows. To validate the efficiency and practical feasibility of SmartCoflow, we implement it as a real-world coflow scheduler based on the Varys open-source framework. Through experimental results from both a small-scale testbed implementation and large-scale simulations, we demonstrate that SmartCoflow can achieve significant improvement on the average CCT, when compared to the state-of-the-art scheduling-only method.

As the network operating system (NOS) is the strategic control center of a software-defined network (SDN), its design is critical to the welfare of the network. Contemporary research has largely focused on specialized NOSs that seek to optimize controller design across one or a few dimensions (e.g., scalability, performance, or security) due to fundamental differences in architectural trade-offs needed to support competing demands. We thus designed Barista, as a new framework that enables flexible and customizable instantiations of network operating systems (NOSs) supporting diverse design choices. The Barista framework incorporates two mechanisms to harmonize architectural differences across design choices: component synthesis and dynamic event control. First, the modular design of the Barista framework enables flexible composition of functionalities prevalent in contemporary SDN controllers. Second, its event-handling mechanism enables dynamic adjustment of control flows in a NOS. These capabilities allow operators to easily enable functionalities and dynamically handle associated events, thereby satisfying network operating requirements. Our results demonstrate that Barista can synthesize NOSs with many functionalities found in commodity NOSs with competitive performance profiles.

In the “network-as-a-service” paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.