INFOCOM 2015 论文列表

Many truthful spectrum auction schemes have been recently proposed to to ensure that the dominant strategy for bidders is to bid truthfully and thus protect the auctioneer's benefits. However, most of them assume the auctioneer is trustful and do not protect bidders' interests. An auctioneer can manipulate the winner's charging price if it knows bidders' bids. Thus, it is critical to protect bids from the auctioneer. Towards this end, we develop a Privacy-Preserving Economic-Robust spectrum auction scheme, namely PPER. Not only does it well protect users' bid privacy, but also guarantees economic-robustness which is another important auction property. Besides, only transmitters but not receivers are considered in most previous spectrum auctions, resulting in many unexpected collisions during transmissions. In this work, we consider interference constraints from transmissions instead of transmitters in spectrum allocation. Extensive privacy analysis and simulation results show the effectiveness and efficiency of our scheme.

Emerging wake-up radio technologies have the potential to bring the performance of sensing systems and of the Internet of Things to the levels of low latency and very low energy consumption required to enable critical new applications. This paper provides a step towards this goal with a twofold contribution. We first describe the design and prototyping of a wake-up receiver (WRx) and its integration to a wireless sensor node. Our WRx features very low power consumption (<; 1.3μW), high sensitivity (up to -55dBm), fast reactivity (wake-up time of 130μs), and selective addressing, a key enabler of new high performance protocols. We then present ALBA-WUR, a cross-layer solution for data gathering in sensing systems that redesigns a previous leading protocol, ALBA-R, extending it to exploit the features of our WRx. We evaluate the performance of ALBA-WUR via simulations, showing that the use of the WRx produces remarkable energy savings (up to five orders of magnitude), and achieves lifetimes that are decades longer than those obtained by ALBA-R in sensing systems with duty cycling, while keeping latencies at bay.

As service providers have started deploying SDN in their networks, traditional IP routers are gradually upgraded to SDN enabled switches. In other words, the network will have traditional IP routers and SDN switches coexisting, and it is called a hybrid SDN network. With such a network, we take advantage of SDN and propose an approach to guarantee traffic reachability in the presence of any single link failure. By redirecting traffic on the failed link to SDN switches through pre-configured IP tunnels, the proposed approach is able to react to the failures very fast. With the help of coordination among SDN switches, we are also able to explore multiple backup paths for the failure recovery. This allows the proposed approach to avoid potential congestion in the post-recovery network by choosing proper backup paths. Simulation results show that our proposed scheme requires only a very few number of SDN switches in the hybrid SDN network to achieve fast recovery and guarantee 100% reachability from any single link failure. It also shows that the proposed approach is able to better load-balance the post-recovery network comparing to IP Fast Reroute and shortest path re-calculation.

The recent development of 60GHz technology has made hybrid Data Center Networks (hybrid DCNs) possible, i.e., augmenting wired DCNs with highly directional 60GHz wireless links to provide flexible network connectivity. Although a few recent proposals have demonstrated the feasibility of this hybrid design, it still remains an open problem how to route DCN traffics with guaranteed performance under a hybrid DCN environment. In this paper, we make the first attempt to tackle this challenge, and propose the RUSH framework to minimize the network congestion in hybrid DCNs, by jointly routing flows and scheduling wireless (directional) antennas. Though the problem is shown to be NP-hard, the RUSH algorithms offer guaranteed performance bounds. Our algorithms are able to handle both batched arrivals and sequential arrivals of flow demands, and the theoretical analysis shows that they achieve competitive ratios of O(log n), where n is the number of switches in the network. We also conduct extensive simulations using ns-3 to verify the effectiveness of RUSH. The results demonstrate that RUSH produces nearly optimal performance and significantly outperforms the current practice and a simple greedy heuristics.

The number and size of data centers has seen a rapid growth in the last few years. It is no longer uncommon to see large data centers with thousands or even tens of thousands of machines. Hence, it is critical to develop scalable scheduling mechanisms for processing the enormous number of jobs handled by popular paradigms such as the MapReduce framework. This work explores the possibility of simplifying the scheduling procedure by exploiting the “largeness” of the data center system. Specifically, we consider the problem of minimizing the total flow time of a sequence of jobs under the MapReduce framework, where the jobs arrive over time and need to be processed through both Map and Reduce procedures before leaving the system. We show that any work-conserving scheduler is asymptotically optimal under a wide range of traffic loads, including the heavy traffic limit. Our results are shown for scenarios in which the tasks can be preempted and served in parallel over different machines, as well as scenarios when each task has to be served only on one machine and cannot be preempted. This result implies, somewhat surprisingly, that when we have a large number of machines, there is little to be gained by optimizing beyond ensuring that a scheduler should be work-conserving. For long running applications, we also study the relationship between the number of machines and total running time, and show sufficient conditions to guarantee the asymptotic optimality of work-conserving schedulers. Further, we run extensive simulations, that indeed verify that when the total number of machines is large, state-of-the-art work-conserving schedulers have similar and close-to-optimal delay performance.

Statistics show that 79% of the Internet traffic is video and mostly “redundant”. Video-On-Demand in particular follows a 90/10 access pattern, where 90% of the users access the same 10% of all video content. As a result, redundant data are repeatedly transmitted over the Internet. In this paper, we propose a novel traffic deduplication technique to achieve more efficient network communication between video sources (video servers or proxy servers in a CDN) and clients. The proposed SMART (Small packet Merge-Able RouTers) overlay network employs an opportunistic traffic deduplication approach and allows each SMART router to dynamically merge independent streams of the same video content, forming a video streaming tree (VST). The merged streams are tunneled through the overlay together with TCP sessions information before eventually being de-multiplexed and delivered to the clients fully compatible with the TCP protocol. We present theoretical analysis findings on the merging strategy between the video source and clients, the efficiency of the SMART router to save traffic during a merge process, and the overall performance of implementing a SMART overlay topology between a video source and clients. Finally, we prototyped SMART in the PlanetLab environment. We illustrate that performance evaluation results are consistent with our theoretical analysis and significant bandwidth saving is achieved.

Computing clusters have been widely deployed for scientific and engineering applications to support intensive computation and massive data operations. As applications and resources in a cluster are subject to failures, fault-tolerance strategies are commonly adopted, sometimes at the expense of additional delays in job response times, or unnecessarily increasing resource usage. In this paper, we explore concurrent replication with canceling, a fault-tolerance approach where jobs and their replicas are processed concurrently, and the successful completion of either triggers the removals of its replica. We propose a stochastic model to study how this approach affects the cluster service level objectives (SLOs), particularly the offered response time percentiles. In addition to the expected gains in reliability, the proposed model allows us to determine the regions of the utilization where introducing replication with canceling effectively reduces the response times. Moreover, we show how this model can support resource provisioning decisions with reliability and response time guarantees.

We propose a hybrid spectrum and information market for database-assisted TV white space networks, where a geo-location white space database serves as the platform for both the spectrum market and the information market. We study the interactions among the database operator, the spectrum licensee, and unlicensed users systematically, using a three-layer hierarchical model. In Layer I, the licensee negotiates with the database regarding the commission fee of using the spectrum market platform. In Layer II, the database and the licensee compete for selling information or channels to unlicensed users. In Layer III, unlicensed users determine whether to buy the exclusive usage right of licensed channels from the licensee, or to buy the information regarding unlicensed channels from the database. Analyzing such a three-layer model is challenging, due to the coexistence of both positive and negative network externalities in the information market. We characterize the market equilibrium systematically, and analyze how the network externalities affect the equilibrium behaviours of all parties involved. Our numerical results show that the proposed hybrid market can improve the network profit more than 80%, compared with a pure information market. Meanwhile, the achieved network profit is very close to the coordinated benchmark (e.g., the gap is less than 4%).

Using nine months of access logs comprising 1.9 Billion sessions to BBC iPlayer, we survey the UK ISP ecosystem to understand the factors affecting adoption and usage of a high bandwidth TV streaming application across different providers. We find evidence that connection speeds are important and that external events can have a huge impact for live TV usage. Then, through a temporal analysis of the access logs, we demonstrate that data usage caps imposed by mobile ISPs significantly affect usage patterns, and look for solutions. We show that product bundle discounts with a related fixed-line ISP, a strategy already employed by some mobile providers, can better support user needs and capture a bigger share of accesses. We observe that users regularly split their sessions between mobile and fixed-line connections, suggesting a straightforward strategy for offloading by speculatively pre-fetching content from a fixed-line ISP before access on mobile devices.

Vehicle-to-vehicle safety data dissemination plays an increasingly important role in ensuring the safety and efficiency of vehicle transportation. When collecting safety data, vehicles always prefer data generated at a closer location over data generated at a distant location, and prefer recent data over outdated data. However, these data preferences have been overlooked in most of existing safety data dissemination protocols, preventing vehicles getting more precise traffic information. In this paper, we explore the feasibility and benefits of incorporating the data preferences of vehicles in designing efficient safety data dissemination protocols. In particular, we propose the concept of packet-value to quantify these data preferences. We then design PVCast, a packet-value-based safety data dissemination protocol in VANET. PVCast makes the dissemination decision for each packet based on its packet-value and effective dissemination coverage in order to satisfy the data preferences of all the vehicles in the network. In addition, PVCast is lightweight and fully distributed. We evaluate the performance of PVCast on the ns-2 platform by comparing it with three representative data dissemination protocols. Simulation results in a typical highway scenario show that PVCast provides a significant improvement on per-vehicle throughput, per-packet dissemination coverage with small per-packet delay. Our findings demonstrate the importance and necessity of comprehensively considering the data preferences of vehicles when designing an efficient safety data dissemination protocol for VANET.

Virtual overlays generate topologies for greedy routing, like rings or hypercubes, on connectivity restricted networks. They have been proposed to achieve efficient content discovery in the Darknet mode of Freenet, for instance, which provides a private and secure communication platform for dissidents and whistle-blowers. Virtual overlays create tunnels between nodes with neighboring addresses in the topology. The routing performance hence is directly related to the length of the tunnels, which have to be set up and maintained at the cost of communication overhead in the absence of an underlying routing protocol. In this paper, we show the impossibility to efficiently maintain sufficiently short tunnels. Specifically, we prove that in a dynamic network either the maintenance or the routing eventually exceeds polylog cost in the number of participants. Our simulations additionally show that the length of the tunnels increases fast if standard maintenance protocols are applied. Thus, we show that virtual overlays can only offer efficient routing at the price of high maintenance costs.

In this paper we develop a novel technique to analyze both isolated and interconnected caches operating under different caching strategies and realistic traffic conditions. The main strength of our approach is the ability to consider dynamic contents which are constantly added into the system catalogue, and whose popularity evolves over time according to desired profiles. We do so while preserving the simplicity and computational efficiency of models developed under stationary popularity conditions, which are needed to analyze several caching strategies. Our main achievement is to show that the impact of content popularity dynamics on cache performance can be effectively captured into an analytical model based on a fixed content catalogue (i.e., a catalogue whose size and objects' popularity do not change over time).

The hardware improvement of mobile devices and pervasiveness of wireless technology expedite the convergence with the fast growing cloud computing trend, where the abundant resources on the cloud meet well with the deficiency of hand-held devices. Cloudlet, as a newly emerging paradigm “bringing the cloud closer” to the end users, features a more scalable deployment fashion where idle personal servers can be efficiently harnessed. Despite an envisioned monetary saving, such a paradigm confines itself to limited application scenarios, which fails to reach a wide realm of roaming users outside the distance coverage of the access points. In this paper, we propose a cloudlet-based multi-lateral resource exchange framework for mobile users, relying on no central entities. Inspired by the success of BitCoin, we design a novel virtual currency tailored for our framework. To realize an efficient resource exchange market, we also introduce flexible pricing strategies adopted by the individual users whom we assume are rational price-takers, with solid theoretical analysis on the equilibrium state and the stability. After elaborating the key functional modules, we introduce a prototype design enabling seamless trading among mobile users on Internet bandwidth as a proof-of-concept, with least user intervention. Both simulations and experiments are conducted to verify the practicality and efficiency of our system.

In this paper, we utilize a novel communication framework Acoustic-WiFi to develop a smart contention resolution scheme Harmony among the contending devices to address the overhead of the traditional Wi-Fi backoff scheme (i.e. contention window countdown, DIFS) and reduce the overall collisions among the devices. Harmony uses the acoustic channel for contention resolution in Wi-Fi networks. To the best of our knowledge, Harmony is the first to leverage the acoustic interface on commodity smart devices as an addition control channel in parallel with the Wi-Fi interface. We evaluate our scheme using real testbed and simulation. Testbed experiments show more than 40% throughput gain over traditional Wi-Fi networks, while simulation results show more than 27% gain for dense networks.

The growing demand for network programmability has led to the introduction of complex packet processing features that are increasingly hard to provide at full line rates. In this paper, we introduce a novel load-balancing approach that provides more processing power to congested linecards by tapping into the processing power of underutilized linecards. Using different switch-fabric models, we introduce algorithms that aim at minimizing the total average delay and maximizing the capacity region. Our simulations with real-life traces then confirm that our algorithms outperform current algorithms as well as simple alternative load-balancing algorithms. Finally, we discuss the implementation issues involved in this new way of sharing the router processing power.

The quintessential problem in a smart grid is the matching between power supply and demand - a perfect balance across the temporal domain, for the stable operation of the power network. Recent studies have revealed the critical role of electricity storage devices, as exemplified by rechargeable batteries and plug-in electric vehicles (PEVs), in helping achieve the balance through power arbitrage. Such potential from batteries and PEVs can not be fully realized without an appropriate economic mechanism that incentivizes energy discharging at times when supply is tight. This work aims at a systematic study of such demand response problem in storage-assisted smart grids through a well-designed online procurement auction mechanism. The long-term social welfare maximization problem is naturally formulated into a linear integer program. We first apply a primal-dual optimization algorithm to decompose the online auction design problem into a series of one-round auction design problems, achieving a small loss in competitive ratio. For the one round auction, we show that social welfare maximization is still NP-hard, and design a primal-dual approximation algorithm that works in concert with the decomposition algorithm. The end result is a truthful power procurement auction that is online, truthful, and 2-competitive in typical scenarios.

The minimum amount of information that should be supplied to transmitters to resolve traffic conflicts in a multiple access system is investigated in this paper. The arriving packets are modeled as the random points of a homogeneous Poisson point process distributed within a unit interval. The minimum information required is equal to the minimum entropy of a random partition that separates the points of the Poisson point process. Only a lower bound of this minimum is known in previous work. We provide an upper bound of this minimum entropy, and the gap with the existing lower bound is shown to be smaller than log2e bits. The upper bound asymptotically achieves the minimum entropy required to resolve per unit traffic. We then analyze the control information used to resolve the traffic conflicts in the splitting algorithm and in the slotted-ALOHA protocol, and identify their gaps with the theoretic bound.

Multicast data dissemination is the performance bottleneck for high-performance data analytics applications in cluster computing, because terabytes of data need to be distributed routinely from a single data source to hundreds of computing servers. The state-of-the-art solutions for delivering these massive data sets all rely on application-layer overlays, which suffer from inherent performance limitations. This paper presents Blast, a system for accelerating data analytics applications by optical multicast. Blast leverages passive optical power splitting to duplicate data at line rate on a physical-layer broadcast medium separate from the packet-switched network core. We implement Blast on a small-scale hardware testbed. Multicast transmission can start 33ms after an application issues the request, resulting in a very small control overhead. We evaluate Blast's performance at the scale of thousands of servers through simulation. Using only a 10Gbps optical uplink per rack, Blast achieves upto 102× better performance than the state-of-the-art solutions even when they are used over a non-blocking core network with a 400Gbps uplink per rack.

Wireless power transfer is a promising technology to extend the lifetime of, and thus enhance the usability of, the energy-hungry battery-powered devices. It enables energy to be wirelessly transmitted from power chargers to energy receiving devices. Existing studies have mainly focused on maximizing network lifetime, optimizing charging efficiency, minimizing charging delay, etc. Different from these works, our objective is to optimize charging quality in a 2-D target area. Specifically, we consider the following charger Placement and Power allocation Problem (P3): Given a set of candidate locations for placing chargers, find a charger placement and a corresponding power allocation to maximize the charging quality, subject to a power budget. We prove that P3is NP-complete. We first study P3with fixed power levels, for which we propose a (1-1/e)-approximation algorithm; we then design an approximation algorithm of factor 1-1/e / 2L for P3, where e is the base of the natural logarithm, and L is the maximum power level of a charger. We also show how to extend P3in a cycle. Extensive simulations demonstrate that, the gap between our design and the optimal algorithm is within 4.5%, validating our theoretical results.