INFOCOM 2015 论文列表

When agents compete for common resource and when the utilities derived by them, upon allocation, are independent across the agents and time slots, an opportunistic scheduler is used. The instantaneous utility of one agent can be low, however few among many would have `good' utility with high probability. Opportunistic schedulers utilize these opportunities, allocate resource at any time to a `good' agent. Efficient schedulers maximize the sum of accumulated utilities. Thus, every time `best' agent is allocated. This can result in negligible (unfair) accumulations for some agents, whose instantaneous utilities are `low' with high probability. Fair opportunistic schedulers are thus introduced (e.g., alpha-fair schedulers). We study their price of fairness (PoF). We group the agents into finite classes, each class having identical utilities and QoS requirements. We study the asymptotic PoF as agents increase, while maintaining class-wise proportions constant. Asymptotic PoF is less than one, depends only upon the differences in the largest utilities of individual classes and is less than the maximum such normalized differences. The PoF is zero initially and increases with increase in fairness requirements to an upper bound strictly less than one. We observe that the fair schedulers are essentially priority schedulers, which facilitated easy analysis of PoF.

In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. Such a consideration leads to the problem of finding a minimum weight k-connected m-fold dominating set ((k, m)-MWCDS for short). In this paper, we give an (α + 2.5ρ)-approximation for (2, m)-MWCDS with m ≥ 2 in unit disk graph, where α is the performance ratio for the minimum weight m-fold dominating set problem, and ρ is the performance ratio for the {0,1,2}-Steiner Network Design problem. In view of currently best known ratios for α and ρ, (2, m)-MWCDS has a (9 + ε)-approximation for m ≥ 3 and a (8 + ε)-approximation for m =2, where ε is an arbitrary positive real number.

This paper investigates the problem of finding optimal paths in single-source single-destination accumulative multi-hop networks. We consider a single source that communicates to a single destination assisted by several relays through multiple-hops. At each hop, only one node transmits, while the rest of nodes receive the transmitted signal, and store it after processing/decoding and mixing with the signals received in previous hops. This is, we consider that terminals make use of advanced energy accumulation transmission/reception techniques such us maximal ratio combining reception of repetition codes, or information accumulation with rateless codes. Accumulative techniques increase communication reliability, reduce energy consumption, and decrease latency. We investigate the properties that a routing metric must satisfy in these accumulative networks to guarantee that optimal paths can be computed with Dijkstra's algorithm. We model the problem of routing in an accumulative multi-hop networks, as the problem of routing in a hypergraph. We show that optimality properties in traditional multi-hop network (monotonicity and isotonicity) are no longer valid and derive a new set of sufficient conditions for optimality.

Measurement capabilities are essential for a variety of network applications, such as load balancing, routing, fairness and intrusion detection. These capabilities require large counter arrays in order to monitor the traffic of all network flows. While commodity SRAM memories are capable of operating at line speed, they are too small to accommodate large counter arrays. Previous works suggested estimators, which trade precision for reduced space. However, in order to accurately estimate the largest counter, these methods compromise the accuracy of the rest of the counters. In this work we present a closed form representation of the optimal estimation function. We then introduce Independent Counter Estimation Buckets (ICE-Buckets), a novel algorithm that improves estimation accuracy for all counters. This is achieved by separating the flows to buckets and configuring the optimal estimation function according to each bucket's counter scale. We prove an improved upper bound on the relative error and demonstrate an accuracy improvement of up to 57 times on real Internet packet traces.

We investigate the open problem of characterizing the multiplexing gain offered by FD in a network of M cells (compared to the gain of two available on a single link). While self-interference cancellation is fundamental in realizing full duplex (FD) capability, the more challenging problem in a network-wide deployment of FD communication is a new form of uplink-downlink interference, namely UDI, caused by transmission of uplink clients on the downlink reception of other clients operating in the same frequency band during FD. We leverage spatial interference alignment (IA) as an effective approach to address UDI and characterize the scalability of the FD's multiplexing gain (in terms of M) by providing a closed-form expression. To the best of our knowledge, this is the first characterization of FD's multiplexing gain in a multi-cell network. We also provide an IA construction that can achieve the best scaling possible. Further, we extend our results to practical settings with limited number of clients and limited information sharing between access points.

Data-intensive applications need to address the problem of how to properly place the set of data items to distributed storage nodes. Traditional techniques use the hashing method to achieve the load balance among nodes such as those in Hadoop and Cassandra, but they do not work efficiently for the requests reading multiple data items in one transaction, especially when the source locations of requests are also distributed. Recent works proposed the managed data placement schemes for online social networks, but have a limited scope of applications due to their focuses. We propose an associated data placement (ADP) scheme, which improves the co-location of associated data and the localized data serving while ensuring the balance between nodes. In ADP, we employ the hypergraph partitioning technique to efficiently partition the set of data items and place them to the distributed nodes, and we also take replicas and incremental adjustment into considerations. Through extensive experiments with both synthesized and trace-based datasets, we evaluate the performance of ADP and demonstrate its effectiveness.

Cloud computing platforms provide computational resources (CPU, storage, etc.) for running users' applications. Often, the same application can be implemented in various ways, each with different resource requirements. Taking advantage of this flexibility when allocating resources to users can both greatly benefit users and lead to much better global resource utilization. We develop a framework for fair resource allocation that captures such implementation tradeoffs by allowing users to submit multiple “resource demands”. We present and analyze two mechanisms for fairly allocating resources in such environments: the Lexicographically-Max-Min-Fair (LMMF) mechanism and the Nash-Bargaining (NB) mechanism. We prove that NB has many desirable properties, including Pareto optimality and envy freeness, in a broad variety of environments whereas the seemingly less appealing LMMF fares better, and is even immune to manipulations, in restricted settings of interest.

One practical open problem is the development of a distributed algorithm that achieves near-optimal utility using only a finite (and small) buffer size for queues in a stochastic network. This paper studies utility maximization (or cost minimization) in a finite-buffer regime and considers the corresponding delay and reliability (or rate of packet drops) tradeoff. A floating-queue algorithm allows the stochastic network optimization framework to be implemented with finite buffers at the cost of packet drops. Further, the buffer size requirement is significantly smaller than previous works in this area. With a finite buffer size of B packets, the proposed algorithm achieves within O(e-B) of the optimal utility while maintaining average per-hop delay of O(B) and an average per-hop drop rate of O(e-B) in steady state. From an implementation perspective, the floating-queue algorithm requires little modification of the well-known Drift-Plus-Penalty policy (including MaxWeight and Backpressure policies). As a result, the floating-queue algorithm inherits the distributed and low complexity nature of these policies.

RFID systems have been deployed to detect missing products by affixing them with cheap passive RFID tags and monitoring them with RFID readers. Existing missing tag detection protocols require the tag population to contain only those tags whose IDs are already known to the reader. However, in reality, tag populations often contain tags with unknown IDs, called unexpected tags, and cause unexpected false positives i.e., due to them, missing tags are detected as present. We take the first step towards addressing the problem of detecting the missing tags from a population that contains unexpected tags. Our protocol, RUN, mitigates the adverse effects of unexpected false positives by executing multiple frames with different seeds. It minimizes the missing tag detection time by first estimating the number of unexpected tags and then using it along with the false positive probability to obtain optimal frame sizes and number of times Aloha frames should be executed. RUN works with multiple readers with overlapping regions. It is easy to deploy because it is implemented on readers as a software module and does not require modifications to tags or to the communication protocol between tags and readers. We implemented RUN along with four major missing tag detection protocols and the fastest tag ID collection protocol and compared them side-by-side. Our experimental results show that RUN always achieves the required reliability whereas the best existing protocol achieves a maximum reliability of only 67%.

The prevalence of data-parallel applications has made near-data scheduling an important problem. An example is the map task scheduling in the map-reduce framework. Wang et. al. [13] was the first to identify its capacity region and proposed a throughput-optimal algorithm based on MaxWeight. However, the study of the algorithm's delay performance revealed that it is only heavy-traffic optimal for a very special traffic scenario, where all traffic concentrates on a subset of servers. We propose a simple “local-tasks first” priority algorithm and show that it is throughput-optimal and heavy-traffic optimal for all traffic scenarios, i.e., it asymptotically minimizes the average delay as the arrival rate vector approaches the boundary of the capacity region. So far, it is the only known heavy-traffic optimal algorithm for this setting. As the algorithm is based on pre-determined priority, a direct application of the Lyapunov drift technique does not work. The main proof ideas are the construction of an ideal load decomposition and the separate treatment of two subsystems based on their ideal load. To the best of our knowledge, this is the only setup of affinity scheduling where a simple priority algorithm is shown to be heavy-traffic optimal. Simulation shows that our algorithm also significantly outperforms existing algorithms at loads away from the boundary of the capacity region.

Automated and coordinated vehicles' driving (platooning) is gaining more and more attention today and it represents a challenging scenario heavily relying on wireless Inter-Vehicular Communication (IVC). In this paper, we propose a novel controller for vehicle platooning based on consensus. Opposed to current approaches where the logical control topology is fixed a priori and the control law designed consequently, we design a system whose control topology can be reconfigured depending on the actual network status. Moreover, the controller does not require the vehicles to be radar equipped and automatically compensates outdated information caused by network delays. We define the control law and analyze it in both analytical and simulative way, showing its robustness in different network scenarios. We consider three different wireless network settings: uncorrelated Bernoullian losses, correlated losses using a Gilbert-Elliott channel, and a realistic traffic scenario with interferences caused by other vehicles. Finally, we compare our strategy with another state of the art controller. The results show the ability of the proposed approach to maintain a stable string of vehicles even in the presence of strong interference, delays, and fading conditions, providing higher comfort and safety for platoon drivers.

We study competitive online algorithms for EV (electrical vehicle) charging under the scenario of an aggregator serving a large number of EVs together with its background load, using both its own renewable energy (for free) and the energy procured from the external grid. The goal of the aggregator is to minimize its peak procurement from the grid, subject to the constraint that each EV has to be fully charged before its deadline. Further, the aggregator can predict the future demand and the renewable energy supply with some levels of uncertainty. The key challenge here is how to develop a model that captures the prior knowledge from such prediction, and how to best utilize this prior knowledge to reduce the peak under future uncertainty. In this paper, we first propose a 2-level increasing precision model (2-IPM), to capture the system uncertainty. We develop a powerful computation approach that can compute the optimal competitive ratio under 2-IPM over any online algorithm, and also online algorithms that can achieve the optimal competitive ratio. A dilemma for online algorithm design is that an online algorithm with good competitive ratio may exhibit poor average-case performance. We then propose a new Algorithm-Robustification procedure that can convert an online algorithm with reasonable average-case performance to one with both the optimal competitive ratio and good average-case performance. The robustified version of a well-known heuristic algorithm, Receding Horizon Control (RHC), is found to demonstrate superior performance via trace-based simulations.

Analysis of Internet topologies has shown that the Internet topology has negative curvature, measured by Gromov's “thin triangle condition”, which is tightly related to core congestion and route reliability. In this work we analyze the discrete Ricci curvature of the Internet, defined by Ollivier [1], Lin et al. [2], etc. Ricci curvature measures whether local distances diverge or converge. It is a more local measure which allows us to understand the distribution of curvatures in the network. We show by various Internet data sets that the distribution of Ricci cuvature is spread out, suggesting the network topology to be non-homogenous. We also show that the Ricci curvature has interesting connections to both local measures such as node degree and clustering coefficient, global measures such as betweenness centrality and network connectivity, as well as auxilary attributes such as geographical distances. These observations add to the richness of geometric structures in complex network theory.

Provider policy (e.g., bandwidth rate limits, virtualization, CPU scheduling) can significantly impact application performance in cloud environments. This paper takes a first step towards understanding the impact of provider policy and tackling the complexity of selecting configurations that can best meet the cost and performance requirements of applications. We make three contributions. First, we conduct a measurement study spanning a 19 months period of a wide variety of applications on Amazon EC2 to understand issues involved in configuration selection. Our results show that provider policy can impact communication and computation performance in unpredictable ways. Moreover, seemingly sensible rules of thumb are inappropriate - e.g., VMs with latest hardware or larger VM sizes do not always provide the best performance. Second, we systematically characterize the overheads and resulting benefits of a range of testing strategies for configuration selection. A key focus of our characterization is understanding the overheads of a testing approach in the face of variability in performance across deployments and measurements. Finally, we present configuration pruning and short-listing techniques for minimizing testing overheads. Evaluations on a variety of compute, bandwidth and data intensive applications validate the effectiveness of these techniques in selecting good configurations with low overheads.

Many applications in wireless sensor networks (WSNs) require that sensor observations in a given monitoring area be aggregated in a serial fashion. This demands a routing path to be constructed traversing all sensors in that area, which is also called to linearize the network. In this paper, we present SURF, a Space filling cURve construction scheme for high genus 3D surFace WSNs, yielding a traversal path provably aperiodic (that is, any node is covered at most a constant number of times). SURF first utilizes the hop-count distance function to construct the iso-contour in discrete settings, then it uses the concept of the Reeb graph and the maximum cut set to divide the network into different regions. Finally it conducts a novel serial traversal scheme, enabling the traversal within and between regions. To the best of our knowledge, SURF is the first high genus 3D surface WSNs targeted and pure connectivity-based solution for linearizing the networks. It is fully distributed and highly scalable, requiring a nearly constant storage and communication cost per node in the network. Extensive simulations on several representative networks demonstrate that SURF works well on high genus 3D surface WSNs.

Smart devices such as smartphones and tablet/wearable PCs are equipped with voice user interface, i.e., speaker and microphone. Accordingly, various aerial acoustic communication techniques have been introduced to utilize the voice user interface as a communication interface. In this paper, we propose an aerial acoustic communication system using inaudible audio signal for low-rate communication in indoor environments. By adopting chirp signal, which is widely used for radar applications due to its capability of resolving multi-path propagation, the proposed acoustic modem supports long-range communication independent of device characteristics over severely frequency-selective acoustic channel. We also design a backend server architecture to compensate for the low data rate of chirp signal-based acoustic modem. Via extensive experiments, we evaluate various characteristics of the proposed modem including multi-path resolution and multiple chirp signal detection. We also verify that the proposed chirp signal can deliver data at 16 bps in typical indoor environments, where its maximum transmission range is drastically extended up to 25 m compared to the few meters of the previous research.

We consider a system in which two nodes take correlated measurements of a random source with time-varying and unknown statistics. The observations of the source at the first node are to be losslessly replicated with a given probability of outage at the second node, which receives data from the first node over a constant-rate channel. We develop a system and associated strategies for joint distributed source coding (encoding and decoding) and transmission control in order to achieve low end-to-end delay. Slepian-Wolf coding in its traditional form cannot be applied in our scenario, since the encoder requires the joint statistics of the observations and the associated decoding delay is very high. We analytically evaluate the performance of our strategies and show that the delay achieved by them are order optimal, as the conditional entropy of the source approaches to the channel rate. We also evaluate the performance of our algorithms based on real-world experiments using two cameras recording videos of a scene at different angles. Having realized our schemes, we demonstrated that, even with a very low-complexity quantizer, a compression ratio of approximately 50% is achievable for lossless replication at the decoder, at an average delay of a few seconds.

Privacy protection is critical for Location-Based Services (LBSs). In most previous solutions, users query service data from the untrusted LBS server when needed, and discard the data immediately after use. However, the data can be cached and reused to answer future queries. This prevents some queries from being sent to the LBS server and thus improves privacy. Although a few previous works recognize the usefulness of caching for better privacy, they use caching in a pretty straightforward way, and do not show the quantitative relation between caching and privacy. In this paper, we propose a caching-based solution to protect location privacy in LBSs, and rigorously explore how much caching can be used to improve privacy. Specifically, we propose an entropy-based privacy metric which for the first time incorporates the effect of caching on privacy. Then we design two novel caching-aware dummy selection algorithms which enhance location privacy through maximizing both the privacy of the current query and the dummies' contribution to cache. Evaluations show that our algorithms provide much better privacy than previous caching-oblivious and caching-aware solutions.

Linear interference alignment (LIA) is one of the key interference mitigation techniques to enhance the wireless MIMO network capacity. The generic LIA feasibility amounts to whether or not a well-structured random matrix with entries drawn from a continuous distribution has full row-rank almost surely. Recently, a randomized algebraic test of feasibility was proposed in the literature. It is a pseudo-polynomial bounded-error probabilistic algorithm in nature, and has intrinsic limitations of requiring an inordinate amount of running time and memory even for a moderate sized input and being prone to round-off errors in floating-point computations. This paper presents necessary conditions and sufficient conditions of the generic LIA feasibility and develops fast and robust tests of them based on network flow. In certain settings, these conditions are both necessary and sufficient, and their flow-based tests yield efficient algorithm for feasibility test.