INFOCOM 2016 论文列表

In a system of interdependent users, the security of an entity is affected not only by that user's effort towards securing her system, but also by the security decisions of other users. The provision of security in such environment is modeled as a public good provision problem, and is referred to as a security game. In this paper, we propose the notion of exit equilibrium to study users' voluntary participation in mechanisms for provision of non-excludable public goods. We show the fundamental result that, due to the non-excludable nature of security, there exists no reliable mechanism which can incentivize the socially optimal investment profile, while ensuring voluntary participation and maintaining a weakly balanced budget, for all instances of security games. To better understand the features of the games that lead to this result, we consider the class of weighted effort games, and apply the two well-known Pivotal (VCG) and Externality mechanisms. Through analysis and simulation, we identify the effects of several features of the problem environment, including diversity in user types, multiplicity of exit equilibria, and users' self-dependence levels, on the performance of these mechanisms.

At the present time, billions of videos are hosted and shared in the cloud of which a sizable portion consists of near-duplicate video copies. An efficient and accurate content-based online near-duplicate video detection method is a fundamental research goal; as it would benefit applications such as duplication-aware storage, pirate video detection, polluted video tag detection, searching result diversification. Despite the recent progress made in near-duplicate video detection, it remains challenging to develop a practical detection system for large-scale applications that has good efficiency and accuracy performance. In this paper, we shift the focus from feature representation design to system design, and develop a novel system, called CompoundEyes, accordingly. The improvement in accuracy is achieved via well-organized classifiers instead of advanced feature design. Meanwhile, by applying simple features with reduced dimensionality and exploiting the parallelism of the detection architecture, we accelerate the detection speed. Through extensive experiments we demonstrate that the proposed detection system is accurate and fast. It takes approximately 1.45 seconds to process a video clip from a large video dataset, CC_WEB_VIDEO, with a 89% detection accuracy.

Segment routing is a new proposed routing mechanism for simplified and flexible path control in IP/MPLS networks. It builds on existing network routing and connection management protocols and one of its important features is the automatic rerouting of connections upon failure. Re-routing can be done with available restoration mechanisms including IGP-based rerouting and fast reroute with loop-free alternates. This is particularly attractive for use in Software Defined Networks (SDN) because the central controller need only be involved at connection set-up time and failures are handled automatically in a distributed manner. A significant challenge in restoration optimization in segment routed networks is the centralized determination of connections primary paths so as to enable the best sharing of restoration bandwidth over non-simultaneous network failures. We formulate this problem as a linear programming problem and develop an efficient primal-dual algorithm for the solution. We also develop a simple randomized rounding scheme for cases when there are additional constraints on segment routing. We demonstrate the significant capacity benefits achievable from this optimized restoration with segment routing.

Energy Harvesting Wireless Sensor Networks (EH-WSNs) have been attracting increasing interest in recent years. Most current EH-WSN approaches focus on sensing and networking algorithm design, and therefore only consider the energy consumed by sensors and wireless transceivers for sensing and data transmissions respectively. In this paper, we incorporate CPU-intensive edge operations that constitute in-network data processing (e.g. data aggregation/fusion/compression) with sensing and networking; to jointly optimize their performance, while ensuring sustainable network operation (i.e. no sensor node runs out of energy). Based on realistic energy and network models, we formulate a stochastic optimization problem, and propose a lightweight on-line algorithm, namely Recycling Wasted Energy (RWE), to solve it. Through rigorous theoretical analysis, we prove that RWE achieves asymptotical optimality, bounded data queue size, and sustainable network operation. We implement RWE on a popular IoT operating system, Contiki OS, and evaluate its performance using both real-world experiments based on the FIT IoT-LAB testbed, and extensive trace-driven simulations using Cooja. The evaluation results verify our theoretical analysis, and demonstrate that RWE can recycle more than 90% wasted energy caused by battery overflow, and achieve around 300% network utility gain in practical EH-WSNs.

In data parallel frameworks such as MapReduce and Spark, a coflow represents a set of network flows used to transfer intermediate data between successive computation stages for a job. The completion time of a job is then determined by the collective behavior of such a coflow, rather than any individual flow within, and influenced by the amount of network bandwidth allocated to it. Different jobs in a shared cluster have different degrees of sensitivity to their completion times, modeled by their respective utility functions. In this paper, we focus on the design and implementation of a new utility optimal scheduler across competing coflows, in order to provide differential treatment to coflows with different degrees of sensitivity, yet still satisfying max-min fairness across these coflows. Though this objective can be formulated as a lexicographical maximization problem, it is challenging to solve in practice due to its inherent multi-objective and discrete nature. To address this challenge, we first divide the problem into iterative steps of single-objective subproblems; and in each of these steps, we then perform a series of transformations to obtain an equivalent linear programming (LP) problem, which can be efficiently solved in practice. To demonstrate that our solutions are practically feasible, we have implemented it as a real-world coflow scheduler based on the Varys open-source framework to evaluate its effectiveness.

Wireless power transfer (WPT) technique enables wireless charging/recharging, thus is a promising way to power wireless devices' transmissions. Because current WPT technique requires a wireless device to stop transmitting data when receiving power, and also because the received power in this way is limited, careful scheduling is needed to decide when the device should receive power and when it should transmit such that data can be efficiently transmitted. This paper assumes the most fundamental point-to-point White Gaussian Noise channel is used for data transmission and attempts to obtain an optimal scheduling such that a sequence of data packets can be transmitted with the minimum delay. It is discovered that, for all (energy receiving, data transmitting) cycles, except the last one, the optimal transmission rate should be a constant which is called the wOPT rate. Based on this discovery, this paper optimally solves the offline delay minimization problem. Then, an online heuristic scheduling algorithm is proposed, which either receives energy or transmits at the wOPT rate. Simulations have demonstrated its efficiency. The discovery of the wOPT rate reveals an essential property of WPT, thus is expected to make significant impact in the field of WPT.

When vehicle road-level localization cannot satisfy people's need for convenience and safety driving, lane-level localization becomes a corner stone in Intelligent Transportation System. Existing work on tracking vehicles on lane-level mostly depends on pre-deployed infrastructures and additional hardwares. In this paper, we utilize smartphone sensing of driving conditions for vehicle lane-level localization on highways. We analyze the driving traces collected from real driving environments, finding that each type of lane change has its unique pattern on the vehicle's lateral acceleration. Based on this observation, we propose a Lane-Level Localization (L3) system, which can perform real-time vehicle localization on lane-level only using smartphones when vehicles are driving on highways. Our system first uses embedded sensors in smartphones to capture the patterns of lane change behaviors. Then a Gaussian Distribution is employed to track vehicles on lane-level with tolerance of false detections. Extensive experiments demonstrate that L3 is accurate and robust in real driving environments. The experimental results show that, on average, L3 achieves accuracy of 91.49% on lane change detection and 86.94% on lane-level localization.

Since the emergence of Content Centric Networking (CCN) as a new paradigm for content delivery in the Internet, copious of research targeted the evaluation or the enhancement of CCN caching schemes. Motivated by providing the Internet Service Providers with incentives to perform caching, the increasing deployment of in-network cloudlets, and the low cost of storage devices, we study caching in CCN from an economical point of view, where the content providers pay the Internet Service Providers in exchange for caching their content items. We propose an online caching algorithm for CCN that does not require the exact knowledge of content items' popularities to minimize the total cost paid by the content providers. The total cost here is the sum of the caching costs and the retrieval costs. Our analysis shows that the proposed algorithm achieves an O(1) competitive ratio when compared to the optimal offline caching scheme that possesses the exact knowledge of content items' popularities. We also show through simulations that the proposed algorithm can cut the cost incurred by widely used caching schemes such as Leave Copy Down (LCD) and Leave Copy Everywhere (LCE) by up to 65%.

Software defined networking is becoming increasingly prevalent in data center networks for its programmability that enables centralized network configuration and management. However, since switches are statically assigned to controllers, traffic dynamics cause load imbalance among the controllers. As a result, some controllers are not fully utilized, while switches connected to overloaded controllers may experience long response times. In this paper, we consider dynamic controller assignment so as to minimize the average response time of the control plane. We formulate this problem as a stable matching problem with transfers, and propose a hierarchically two-phase algorithm that integrates key concepts from both matching theory and coalitional games to solve it efficiently. Theoretical analysis proves that our algorithm converges to a near-optimal Nash stable solution within tens of iterations. Extensive simulations show that our approach reduces response time by about 86%, and achieves better load balancing among controllers compared to static assignment.

A Social Learning Network (SLN) emerges when users exchange information on educational topics with structured interactions. The recent proliferation of massively scaled online (human) learning, such as Massive Open Online Courses (MOOCs), has presented a plethora of research challenges surrounding SLN. In this paper, we ask: How efficient are these networks? We propose a framework in which SLN efficiency is determined by comparing user benefit in the observed network to a benchmark of maximum utility achievable through optimization. Our framework defines the optimal SLN through utility maximization subject to a set of constraints that can be inferred from the network. Through evaluation on four MOOC discussion forum datasets and optimizing over millions of variables, we find that SLN efficiency can be rather low (from 68% to 82% depending on the specific parameters and dataset), which indicates that much can be gained through optimization. We find that the gains in global utility (i.e., average across users) can be obtained without making the distribution of local utilities (i.e., utility of individual users) less fair. We also discuss ways of realizing the optimal network in practice, through curated news feeds in online SLN.

With the rapid advance of the Internet of Everything, both the number of devices and the range of applications that rely on wireless connectivity show huge growth. Driven by these pervasive trends, wireless networks grow in size and complexity, supporting immense numbers of nodes and data volumes, with highly diverse traffic profiles and performance requirements. While well-established methods are available for evaluating the throughput of persistent sessions with saturated buffers, these provide no insight in the delay performance of flows with intermittent packet arrivals. The occurrence of empty buffers in the latter scenario results in a complex interaction between activity states and packet queues, which severely complicates the performance analysis. Motivated by these challenges, we develop a mean-field approach to analyze buffer contents and packet delays in wireless networks in a many-sources regime. The mean-field behavior simplifies the analysis of a large-scale network with packet arrivals and buffer dynamics to a low-dimensional fixed-point calculation for a network with saturated buffers. In particular, the analysis yields explicit expressions for the buffer content and packet delay distribution in terms of the fixed-point solution. Extensive simulation experiments demonstrate that these expressions provide highly accurate approximations, even for a fairly moderate number of sources.

During the one minute it takes to read this abstract, two billion smartphones worldwide will perform billions of Wifi channel scans recording the signal strength of nearby Wifi Access Points (APs). Yet despite this ongoing planetary-scale wireless network measurement, few systematic efforts are made today to recover this potentially valuable data. In this paper we ask the question: “Are the smartphone channel scans useful in monitoring enterprise Wifi networks?” More specifically, can these client-side measurements provide new insights compared to the AP-side measurements that enterprise Wifi networks already perform? Beginning with two Wifi scan datasets collected on two large scale smartphone testbeds, we conduct case studies that show how smartphone channel scans can be used to (1) improve AP spectrum management, and (2) predict the impact of AP failure or overload. In each case, a walk on the client side yields valuable insights for network operators that are otherwise impossible to gain from AP-side measurements, and together our results demonstrate the value of smartphone channel scans.

Event matching is vital in multi-dimensional content-based publish/subscribe services, which are widely employed for data dissemination in various scenarios. Existing mechanisms suffer from performance degradation in high-dynamic large-scale systems. To this end, we present GEM (Geometrical Event Matching), an analytic geometrical approach to fast event matching. GEM offers a very high event matching speed, and it also has low costs for subscription insertion/deletion operations and memory usage. In GEM, subscriptions are organized efficiently by a triangle-like index structure. A graph partitioning matching method and a selection matching method are jointly used for single-dimensional matching (SDM). Optimized by a decision algorithm for each incoming event, the event matching process is carried out in a pipeline consisting the SDM for each dimension. The search space shrinks continuously as the process goes, so that the event matching performance is promoted adaptively. A cache method is also designed to boost the first SDM in the pipeline. We implement extensive experiments to evaluate the performance of GEM in comparison with 3 state-of-the-art reference algorithms (TAMA, H-TREE and REIN). The results show that, the event matching time, subscription insertion/deletion time and memory consumption of GEM is on average 53.9%, 42.3%/49.5% and 31.8% lower than the best in other 3 algorithms, respectively. The event matching time of GEM is reduced efficiently via the cache method. The superiority of GEM appears more significantly as system scale and dynamic grow, and its performance also maintains in a high stability.

Free-viewpoint television (FTV) is a visionary application that provides immersive experience to the audience with the freedom of changing viewpoint during the video playout. However, live broadcasting and user interaction do not coexist in existing FTV systems. In this paper, we propose F.Live, a framework of FTV content dissemination that supports user-initiated viewpoint changing for live broadcasting. Simulation result of a large-scale experiment, based on camera array settings of existing Nagoya systems and EyeVision System, shows that F.Live is capable of supporting 100,000 concurrent audiences with free-viewpoint low user interaction latency and feasible bandwidth requirements.

As cellular networks like 4G LTE networks get more and more sophisticated, mobiles also measure and send enormous amount of mobile measurement data (in TBs/week/metropolitan) during every call and session. The mobile measurement records are saved in data center for further analysis and mining, however, these measurement records are not geo-tagged because the measurement procedures are implemented in mobile LTE stack. Geo-tagging (or localizing) the stored measurement record is a fundamental building block towards network analytics and troubleshooting since the measurement records contain rich information on call quality, latency, throughput, signal quality, error codes etc. In this work, our goal is to localize these mobile measurement records. Precisely, we answer the following question: what was the location of the mobile when it sent a given measurement record? We design and implement novel machine learning based algorithms to infer whether a mobile was outdoor and if so, it infers the latitude-longitude associated with the measurement record. The key technical challenge comes from the fact that measurement records do not contain sufficient information required for triangulation or RF fingerprinting based techniques to work by themselves. Experiments performed with real data sets from an operational 4G network in a major metropolitan show that, the median accuracy of our proposed solution is around 20 m for outdoor mobiles and outdoor classification accuracy is more than 98%.

Device-to-Device communications represent a paradigm shift in cellular networks. Analytical results on D2D performance are very promising, but there is no experimental evidence that validates these results to date. This paper is the first to provide an experimental analysis of outband D2D schemes. Moreover, we design DORE, a complete framework for handling channel opportunities offered by outband D2D relay nodes. DORE consists of resource allocation optimization tools and protocols suitable to integrate QoS-aware opportunistic D2D communications within the architecture of 3GPP Proximity-based Services. We implement DORE using an SDR framework to profile cellular network dynamics in presence of opportunistic outband D2D communication schemes. Our experiments reveal that outband D2D communications are suitable for a large variety of delay-sensitive cellular applications, and that DORE enables notable gains even with a few active D2D relay nodes.

This paper proposes distributed load shedding policies for regulating excessive network load. Data packets are inserted into the network to be delivered to intended destinations. The intermediate network nodes may decide to forward or shed some packets depending on temporally available resources. It is possible for some packets to traverse several nodes in the network until they are finally dropped before reaching the destination, which exacerbates energy consumption. We define a multi-objective optimization problem where we aim to minimize the used energy subject to providing maximum sum throughput. For the case of single-path unicast sessions, we show that Energy-efficient Distributed Load Shedding (E-DLS), a simple shedding mechanism combined with pushback routing, solves this load di shedding optimization. We implement E-DLS in a testbed and use the experiments to select policy parameter values that strike a good balance between energy and delay performance. We then propose a heuristic extension of E-DLS for multirate multicast routing, and showcase via testbed experiments its optimal performance.

To cope with the increasing scarcity of spectrum resources, researchers have been working to extend LTE/LTE-A cellular systems to unlicensed bands, leading to so-called unlicensed LTE (U-LTE). However, this extension is by no means straightforward, primarily because the radio resource management schemes used by LTE and by systems already deployed in unlicensed bands are incompatible. Specifically, it is well known that coexistence with scheduled systems like LTE degrades considerably the throughput of Wi-Fi networks that are based on carrier-sense medium access schemes. To address this challenge, we propose for the first time a cognitive coexistence scheme to enable spectrum sharing between U-LTE and Wi-Fi networks, referred to as CU-LTE. The proposed scheme is designed to jointly determine dynamic channel selection, carrier aggregation and fractional spectrum access for U-LTE networks, while guaranteeing fair spectrum access for Wi-Fi based on a newly designed cross-technology fairness criterion. We first derive a mathematical model of the spectrum sharing problem for the coexisting networks; we then design a solution algorithm to solve the resulting fairness constrained mixed integer nonlinear optimization problem. The algorithm, based on a combination of branch and bound and convex relaxation techniques, maximizes the network utility with guaranteed optimality precision that can be set arbitrarily to 1 at the expense of computational complexity. Performance evaluation indicates that near-optimal spectrum access can be achieved with guaranteed fairness between U-LTE and Wi-Fi. Issues regarding implementation of CU-LTE are also discussed.

Consider a set S of nodes in the plane such that the unit-disk graph G(S) spanning all nodes is connected. Each node in S is equipped with a directional antenna with beam-width θ = π/2. The objective of the Directional Antenna Orientation (AO) problem concerning symmetric connectivity is to determine an orientation of the antennas with a minimum transmission power range r = O(1) such that the induced symmetric communication graph is connected. Another related problem is the Antenna Orientation and Power Assignment (AOPA) problem whose objective is to assign each node u ϵ S an orientation of its antenna as well as a range r(u) such that the induced symmetric communication graph is connected and the total power assigned ΣuϵSr(u)β is minimized, where β ≥ 1 is the distance-power gradient (typically 2 ≤ β ≤ 5). In this paper, we study both problems by first proving that they are NP-hard. To the best of our knowledge, these NP-hardness results have not been obtained before in the literature. We then propose an algorithm for the AO problem that orients the antennas to yield a symmetric connected graph where the transmission power range is bounded by 9 which is currently the best result for this problem. (Previous bound for this problem is 14√2 by Aschner et al). We also propose a constant-approximation algorithm for the AOPA problem where our constant is smaller than the one in Aschner et al's algorithm.