INFOCOM 2017 Papers

We consider the problem of proactive (i.e. predictive) content caching that is aware of the costs of retention of the content in the cache. Prior work on caching (whether proactive or reactive) does not explicitly take into account the storage cost due to the duration of time for which a content is cached. This new problem, which we call retention aware caching, is motivated by two recent technological developments that are described in the paper: cloud storage rental costs and flash memory damage. We consider a hierarchical network consisting of a server connected to a number of cache-enabled nodes, located either at the edge of a network (e.g. base stations) or in the core of a data center. There are two types of network costs: storage cost at the caches and download cost from the server. We formulate the problem of proactive retention aware data caching (PRAC), which minimizes the total cost subject to the node capacity constraints. We first prove that PRAC is NP-Hard in general and then analyze PRAC for two cases: (1) linear storage cost, (2) convex storage cost. We show that PRAC admits efficient polynomial time algorithms when the storage cost is linear in retention times and caches have a large capacity. Furthermore, we derive bounds on the performance of PRAC for the case when the storage cost is a practically motivated convex function. Numerical evaluations demonstrate that PRAC outperforms other state-of-the-art caching policies for a wide range of parameters of interest.

Fair and efficient coflow scheduling improves application-level networking performance in today's datacenters. Ideally, a coflow scheduler should provide isolation guarantees on the minimum coflow progress to achieve predictable networking performance. Network operators, on the other hand, strive to decrease the average coflow completion time (CCT). Unfortunately, optimal isolation guarantees and minimum average CCT are conflicting objectives and cannot be achieved at the same time. Existing coflow schedulers either optimize isolation guarantees at the expense of long CCTs (e.g., HUG [1]), or decrease the average CCT without performance isolation (e.g., Varys and Aalo [2], [3]). The lack of a smooth tradeoff in between poses a dilemma between low efficiency and no performance isolation. To bridge this gap, we develop a new coflow scheduler, Coflex, to navigate this tradeoff. Coflex allows network operators to specify the desired level of isolation guarantee using a tunable fairness knob, while at the same time decreasing the average CCT. Both our real-world deployments and trace-driven simulations have shown that Coflex offers a smooth tradeoff between fairness and efficiency. At an appropriate tradeoff level, Coflex outperforms fair schedulers by 2 × in minimizing the average CCT.

In wireless ad hoc networks, due to the interference between concurrent transmissions, the per node capacity generally decreases with the increasing number of nodes in the network. Caching can help improve the network capacity, as it shortens the content transmission distance and reduces the communication interference. However, current researches on the capacity of wireless ad hoc networks with caching generally assume that content popularity follows uniform distribution. They ignore the fact that contents in reality have skewed popularity, which may lead to totally different capacity results. In this paper, we evaluate how the distribution of the content popularity affects the network capacity, and derive different capacity scaling laws based on the skewness of the content popularity. Our results suggest that for wireless networks with caching, when contents have skewed popularity, increasing the number of nodes monotonically increases the per node capacity.

Fractional Link scheduling is one of the most fundamental problems in wireless networks. The prevailing approach for shortest fractional link scheduling is based on a reduction to the maximum-weighted independent set problem, which itself may not admit efficient approximation algorithms. In addition, except for the wireless networks under the protocol interference model, none of the existing scheduling algorithms can produce a link schedule with explicit upper bounds on its length in terms of the link demands. As the result, the polynomial approximate capacity regions in these networks remain blank. This paper develops a purely combinatorial paradigm for fractional link scheduling in wireless networks. In addition to the superior efficiency, it is able to provide explicit upper bounds on the lengths of the produced link schedule. By exploiting these upper bounds, polynomial approximate capacity regions are derived. The effectiveness of this new paradigm is demonstrated by its applications in wireless networks under the physical interference model and wireless MIMO networks under the protocol interference model.

Cross-technology communication (CTC) techniques are introduced in recent literatures to explore the opportunities of collaboration between heterogeneous wireless technologies, such as WiFi and ZigBee. Their applications include context-aware services and global channel coordination. However, state-of-the-art CTC schemes either suffer from channel inefficiency, low throughput, or disruption to existing networks. This paper presents the CTC via data packets (DCTC), which takes advantage of abundant existing data packets to construct recognizable energy patterns. DCTC features (i) a significant enhancement in CTC throughput while (ii) keeping transparent to upper layer protocols and applications. Our design also features advanced functions including multiplexing to support concurrent transmissions of multiple DCTC senders and adaptive rate control according to the traffic volume. Testbed implementations across WiFi and ZigBee platforms demonstrate reliable bidirectional communication of over 95% in accuracy while achieving throughput 2.3x of the state of the art. Meanwhile, experiment results show that DCTC has little and bounded impact on the delay and throughput of original data traffic.

A massive explosion of various types of data has been triggered in the “Big Data” era. In big data systems, machine learning plays an important role due to its effectiveness in discovering hidden information and valuable knowledge. Data privacy, however, becomes an unavoidable concern since big data usually involve multiple organizations, e.g., different healthcare systems and hospitals, who are not in the same trust domain and may be reluctant to share their data publicly. Applying traditional cryptographic tools is a straightforward approach to protect sensitive information, but it often renders learning algorithms useless inevitably. In this work, we, for the first time, propose a novel privacy-preserving scheme for canonical correlation analysis (CCA), which is a well-known learning technique and has been widely used in cross-media retrieval system. We first develop a library of building blocks to support various arithmetics over encrypted real numbers by leveraging additively homomorphic encryption and garbled circuits. Then we encrypt private data by randomly splitting the numerical data, formalize CCA problem and reduce it to a symmetric eigenvalue problem by designing new protocols for privacy-preserving QR decomposition. Finally, we solve all the eigenvalues and the corresponding eigenvectors by running Newton-Raphson method and inverse power method over the ciphertext domain. We carefully analyze the security and extensively evaluate the effectiveness of our design. The results show that our scheme is practically secure, incurs negligible errors compared with performing CCA in the clear and performs comparably in cross-media retrieval systems.

Nowadays many clustered file systems adopt asynchronous encoding which transforms replicated data into erasure coding to maintain data availability with bounded storage overhead. Existing implementations of asynchronous encoding construct coding stripes with logically sequential data blocks, which suffers from heavy cross-rack traffic and necessitates data block redistribution. Recent work [12] solves this problem by carefully distributing replicated data blocks among racks at the time when they are being written, but it is not applicable to the cases when existing systems have different data layouts or the data layout changes. In this paper, we propose Dynamic Stripe Construction (DSC) to transform N-way replication to erasure coding. DSC does not induce to any cross-rack traffic for encoding, and it does not require data block redistribution after encoding. Besides, DSC is general enough to be applied to any existing CFSes with various erasure codes, and it can also be deployed on a distributed file system in a hot-plugging-in manner. To validate the effectiveness of DSC, we implement it on HDFS. Through extensive testbed experiments in a real storage cluster, we show that DSC can significantly increase the encoding throughput and reduce the foreground user response time over the traditional approach.

Swarming systems, such as BitTorrent, are one of the most common solutions for scalable, robust and inexpensive content distribution. Although the service capacity of swarming systems has been studied for decades through modeling and analysis, there is a lack of experimental evidence about how the throughput of such systems behaves in under-provisioned regimes. The aim of this paper is to fill this gap. In this paper, we consider a closed-loop model to assess the throughput of peer-to-peer systems. Then, we show through controlled experiments using BitTorrent clients that some analytical findings recently reported in the literature, such as the missing piece syndrome, occur in practice. In particular, we indicate that when seeds have a small effective service capacity, or when seeds are intermittent, the throughput saturates as the population size grows. Finally, we discuss the implications of such findings on the modeling and design of swarming systems.

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P=NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov Decision Process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, it has comparable performance than some other seemingly more sophisticated algorithms. Second, by harnessing the sub-modularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms are justified through extensive simulations on three real network datasets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.

Cluster scheduler serves as a critical component to data-parallel systems in datacenters. Ideally, a scheduler should provide predictable performance with guarantees on the maximal job completion delay, while at the same time ensuring the minimal mean response time. Practically however, performance predictability and optimality are often conflicting with each other. The results often are a plethora of scheduling policies that either achieve predictable performance at the expense of long response times (e.g., max-min fairness), or run the risk of starving some jobs to obtain the minimal mean response time (e.g., Shortest Remaining Processing Time First). To address these problems, we develop a new scheduler, Cluster Fair Queueing (CFQ), which preferentially offers resources to jobs that complete the earliest under a fair sharing policy. We show that CFQ is able to minimize the mean response time while at the same time ensuring jobs to finish within a constant time after their completion under fair sharing. Our Spark deployment on a 100-node EC2 cluster demonstrates that compared to the built-in fair scheduler, CFQ can decrease the mean response time by 40%, which speeds up more than 40% of jobs by over 75% on average.

Many apps have been developed to measure the performance of mobile networks. Unfortunately, their measurement results may not be what users expect, because the results could be biased by various factors and the apps' descriptions may confuse users. Although a few recent studies pointed out several factors, they missed other important factors and lacked of finegrained analysis on the factors and measurement apps. Moreover, none has studied whether or not the descriptions of such apps will mislead users. In this paper, we conduct the first systematic study of the factors that could bias the result from measurement apps and their descriptions. We identify new factors, revisit known factors, and propose a novel approach with new tools to discover these factors in proprietary apps. We also develop a new measurement app named MobiScope for demonstrating how to mitigate the negative effects of these factors. Furthermore, we construct enhanced descriptions for measurement apps to provide users more information about what is measured. The extensive experimental results illustrate the negative effects of various factors, the improvement in performance measurement brought by MobiScope, and the clarity of the enhanced descriptions.

Recently, HTTP-based adaptive video streaming has been widely adopted in the Internet. Up to now, HTTP-based adaptive video streaming is standardized as Dynamic Adaptive Streaming over HTTP (DASH), where a client-side video player can dynamically pick the bitrate level according to the perceived network conditions. Actually, not only the available bandwidth is varying, but also the chunk sizes in the same bitrate level significantly fluctuate, which also influences the bitrate adaptation. However, existing bitrate adaptation algorithms do not accurately involve the chunk size variation, leading to performance losses. In this paper, we theoretically analyze the influence of chunk size variation on bitrate adaptation performance. Based on DASH system features, we build a general model describing the playback buffer evolution. Applying stochastic theories, we respectively analyze the influence of the chunk size variation on rebuffering probability and average bitrate level. Furthermore, based on theoretical insights, we provide several recommendations for algorithm designing and rate encoding, and also propose a simple bitrate adaptation algorithm. Extensive simulations verify our insights as well as the efficiency of the proposed recommendations and algorithm.

With increasing demand for wireless connectivity, IEEE 802.11 WLANs have become ubiquitous and continue to grow in number. This leads to high density of basic service sets with the significant co-channel interference (CCI) among them. This paper sheds light on the CCI caused by 802.11 MAC ACK frames, which has been less studied than the CCI caused by data frames. Based on stochastic geometry analysis, we propose Quiet ACK (QACK), a dynamic transmit power control algorithm for ACK frames. Fine-grained transmit power adjustment is enabled by CCI detection and CCI power estimation in the middle of a data frame reception. Our prototype using software-defined radio shows the feasibility and performance gain of QACK, i.e., 1.5x higher throughput than the legacy 802.11 WLANs. The performance of QACK is further evaluated in more general WLAN environments via extensive simulations using ns-3.

Mobile network operators can track subscribers via passive or active monitoring of device locations. The recorded trajectories offer an unprecedented outlook on the activities of large user populations, which enables developing new networking solutions and services, and scaling up studies across research disciplines. Yet, the disclosure of individual trajectories raises significant privacy concerns: thus, these data are often protected by restrictive non-disclosure agreements that limit their availability and impede potential usages. In this paper, we contribute to the development of technical solutions to the problem of privacy-preserving publishing of spatiotemporal trajectories of mobile subscribers. We propose an algorithm that generalizes the data so that they satisfy-anonymity, an original privacy criterion that thwarts attacks on trajectories. Evaluations with real-world datasets demonstrate that our algorithm attains its objective while retaining a substantial level of accuracy in the data. Our work is a step forward in the direction of open, privacy-preserving datasets of spatiotemporal trajectories.

Cache policies to minimize the content retrieval cost have been studied through competitive analysis when the miss costs are additive and the sequence of content requests is arbitrary. More recently, a cache utility maximization problem has been introduced, where contents have stationary popularities and utilities are strictly concave in the hit rates. This paper bridges the two formulations, considering linear costs and content popularities. We show that minimizing the retrieval cost corresponds to solving an online knapsack problem, and we propose new dynamic policies inspired by simulated annealing, including DynqLRU, a variant of qLRU. For such policies we prove asymptotic convergence to the optimum under the characteristic time approximation. In a real scenario, popularities vary over time and their estimation is very difficult. DynqLRU does not require popularity estimation, and our realistic, trace-driven evaluation shows that it significantly outperforms state-of-the-art policies, with up to 45% cost reduction.

Matrix inverse computation is one of the most fundamental mathematical problems in large-scale data analytics and computing. It is often too expensive to be solved in resource-constrained devices such as sensors. Outsourcing the computation task to a cloud server or a fog server is a potential approach as the server is able to perform large-scale scientific computations on behalf of resource-constrained users with special software. However, outsourcing brings in new security concerns and challenges such as data privacy violations and result invalidation. In this paper, we propose a secure and verifiable outsourcing scheme to compute the matrix inverse in a server. In our scheme, the client generates two secret key sets based on two chaotic systems, which are utilized to create two sparse matrices whose permuted versions are used for matrix encryption and decryption to protect input and output privacy. The server computes the inverse over the ciphertext matrix and returns the result to the client who can verify the validity of the inverse. We analyze the proposed scheme in terms of correctness, security, verifiability, and attack resistance, and compare its performance (computation, storage, and communication overheads) with those of the state-of-the-art. Our theoretical results and comparison study demonstrate that the proposed scheme provides a secure and efficient outsourcing mechanism for matrix inverse computation.

Auctions have been adopted by many major cloud providers, such as Amazon EC2. Unfortunately, only simple auctions have been implemented. Such simple auction has serious limitations, such as being unable to accept elastic user demands and having to allocate different types of VMs independently. These limitations create a big gap between the real needs of cloud users and the available services of cloud providers. In response to the limitations of the existing auction mechanisms, this paper proposes a novel online auction mechanism for IaaS clouds, with the unique features of an elastic model for inputting time-varying user demands and a unified model for requesting heterogeneous VMs together. However, several major challenges should be addressed, such as NP hardness of optimal VM allocation, time-varying user demands and potential misreports of private information of cloud users. We propose a truthful online auction mechanism for maximizing the profit of the cloud provider in IaaS clouds, which is composed of a price-based allocation rule and a payment rule. In the allocation rule, the online auction mechanism determines the number of VMs of each type to each user. In the payment rule, by introducing a marginal price function for each type of VMs, the mechanism determines how much the cloud provider should charge each cloud user. With solid theoretical analysis and trace-driven simulations, we demonstrate that our mechanism is truthful and individually rational, and has a polynomial-time complexity.

With the dense deployment of wireless infrastructure such as radio towers and WiFi access points, wireless network optimization becomes very important for improving the network capacity and enhancing the communication quality of wireless links. Most optimization algorithms rely on the conflict graph to describe the interference situation. However, building a conflict graph requires exhaustive measurements of the whole network and the existing estimation approaches are static and inaccurate. In this paper, we propose a conflict graph embedding approach to assess network interference situations by representing the wireless nodes with low-dimensional vectors while preserving their conflict relationships. Specifically, our approach introduces a sliding-window based partial measurement method to sample the interference graph in the network, then adopts a learning algorithm to obtain the vector representation of the nodes, and then infers the interference situations by exploring the feature vectors. The proposed approach has been proved to be low measurement overhead, low computational cost, and self-adaptive, which is suitable for large-scale dynamic wireless networks. We illustrate that conflict graph embedding can be used for interference-aware wireless network optimizations. We conduct extensive experiments based on real wireless network datasets, which show the efficiency of the proposed approach.

An increasing number of high-performance networks are built over the existing IP network infrastructure to provision dedicated channels for big data transfer. The links in these overlay networks correspond to underlying paths and may share lower-level link segments. We consider a model of overlay networks that incorporates correlated link capacities and linear capacity constraints (LCCs) to formulate such shared bottleneck components. The overlay links are typically shared by multiple users through advance reservations, resulting in varying bandwidth availability in future time. Therefore, efficient bandwidth scheduling algorithms are needed to improve the network resource utilization and also meet the user's transport requirements. We investigate two advance scheduling problems in overlay networks with LCCs: Fixed-Bandwidth Path and Varying-Bandwidth Path, with the objective to minimize the data transfer end time for a given data size. We prove that both problems are NP-complete and non-approximable, and propose heuristic algorithms using a gradual relaxation procedure on the maximum number of links from each LCC allowed for path computation. The performance superiority of these heuristics is verified by extensive simulation results in comparison with optimal and greedy strategies.