INFOCOM 2015 Papers

Smartphones save energy by entering a low power suspend mode (120mW). As a result, power consumption increases dramatically. To improve energy efficiency, some phones employ a hardware broadcast filter in the WiFi driver. All UDP broadcast frames other than Multicast DNS frames are blocked, thus none is received by upper layer applications. So, we have a dilemma of handling WiFi broadcast traffic during smartphone suspend mode: either receive all of them suffering high power consumption, or receive none of them sacrificing functionalities. In this paper, we propose Software Broadcast Filter (SBF) to address the dilemma. SBF is smarter than the hardware broadcast filter as it only filters out useless broadcast frames and does not impair functionalities of applications. SBF is also more energy efficient than the “receive all” method. Our trace driven evaluation shows that SBF can save up to 52% energy consumption than the “receive all” method.

We look into the realization of mobile crowdsensing campaigns that draw on the opportunistic networking paradigm, as practised in delay-tolerant networks but also in the emerging device-to-device communication mode in cellular networks. In particular, we ask how mobile users can be optimally selected in order to generate the required space-time paths across the network for collecting data from a set of fixed locations. The users hold different roles in these paths, from collecting data with their sensing-enabled devices to relaying them across the network and uploading them to data collection points with Internet connectivity. We first consider scenarios with deterministic node mobility and formulate the selection of users as a minimum-cost set cover problem with a submodular objective function. We then generalize to more realistic settings with uncertainty about the user mobility. A methodology is devised for translating the statistics of individual user mobility to statistics of spacetime path formation and feeding them to the set cover problem formulation. We describe practical greedy heuristics for the resulting NP-hard problems and compute their approximation ratios. Our experimentation with real mobility datasets (a) illustrates the multiple tradeoffs between the campaign cost and duration, the bound on the hopcount of space-time paths, and the number of collection points; and (b) provides evidence that in realistic problem instances the heuristics perform much better than what their pessimistic worst-case bounds suggest.

The Federal Communications Commission (FCC) released the final rule to approve of TV white spaces (TVWS), i.e., locally vacant TV channels, for unlicensed use in 2010. This TV spectrum will mitigate the shortage of wireless spectrum resources and provide opportunities for new applications. TVWS differ from the conventional Wi-Fi spectrum in three aspects: spectrum fragmentation, spatial variation, and temporal variation. These differences make the network design over TVWS challenging and fundamentally different from Wi-Fi networks. While most prior works on TVWS network design focused on outdoor large-area scenario, the important indoor scenario is largely open for investigation. In this paper, we present WINET (for White-space Indoor NETwork), the first design framework for indoor multi-AP white space network. We optimize AP placement, spectrum allocation, and AP association. Spectrum fragmentation, spatial variation, and temporal variation are all tackled in our network design. We build a test-bed and conduct extensive measurements inside an office building across four months to obtain real-world traces. Experimental results show that WINET can increase AP coverage area by an average of 62.2% and obtain 67.9% higher system throughput while achieving fairness among users as compared to alternative approaches.

With the growing stickiness of the Internet, numerous automated programs running in terminal facilities (e.g., laptops) tend to keep closely connected to the Internet by repetitively interacting with remote services. It is of fundamental importance to study such repeating behaviors of automated programs in areas like traffic engineering and network monitoring. This paper focuses on repeating behaviors in packet arrivals that are of interest, aiming at a hierarchical characterization of packet arrivals, detection methods and quantitative metrics. To this end, we present a structure-oriented characterization of packet arrivals, which reflects the temporal structure of repeating behaviors at different scales. Based on such characterization, a repeating behavior detection method is proposed by leveraging online-learning prediction, and two novel metrics of repeating behaviors are proposed from different aspects. In addition, a denoising method is developed to enhance the noise-tolerant capability of detection and measurement in face of noises. Experimental results based on real-world traces demonstrate the effectiveness of our proposed approaches in automated program behavior detection and behavioral botnet analysis.

The backpressure algorithm is known to provide throughput optimality in routing and scheduling decisions for multi-hop networks with dynamic traffic. The essential assumption in the backpressure algorithm is that all nodes are benign and obey the algorithm rules governing the information exchange and underlying optimization needs. Nonetheless, such an assumption does not always hold in realistic scenarios, especially in the presence of security attacks with intent to disrupt network operations. In this paper, we propose a novel mechanism, called virtual trust queuing, to protect backpressure algorithm based routing and scheduling protocols from various insider threats. Our objective is not to design yet another trust-based routing to heuristically bargain security and performance, but to develop a generic solution with strong guarantees of attack resilience and throughput performance in the backpressure algorithm. To this end, we quantify a node's algorithm-compliance behavior over time and construct a virtual trust queue that maintains deviations from expected algorithm outcomes. We show that by jointly stabilizing the virtual trust queue and the real packet queue, the backpressure algorithm not only achieves resilience, but also sustains the throughput performance under an extensive set of security attacks.

Network functions are widely deployed in modern networks, providing various network services ranging from intrusion detection to HTTP caching. Various virtual network function instances can be consolidated into one physical middlebox. Depending on the type of services, packet processing for different flows consumes different hardware resources in the middlebox. Previous solutions of multi-resource packet scheduling suffer from high computational complexity and memory cost for packet buffering and scheduling, especially when the number of flows is large. In this paper, we design a novel low-complexity and space-efficient packet scheduling algorithm called Myopia, which supports multi-resource environments such as network function virtualization. Myopia is developed based upon the fact that most Internet traffic is contributed by a small fraction of elephant flows. Myopia schedules elephant flows with precise control and treats mice flows using FIFO, to achieve simplicity of packet buffering and scheduling. We will demonstrate, via theoretical analysis, prototype implementation, and simulations, that Myopia achieves multi-resource fairness at low cost with short packet delay.

Exponential growth of the web continues to present challenges to the design and scalability of web crawlers. Our previous work on a high-performance platform called IRLbot [28] led to the development of new algorithms for realtime URL manipulation, domain ranking, and budgeting, which were tested in a 6.3B-page crawl. Since very little is known about the crawl itself, our goal in this paper is to undertake an extensive measurement study of the collected dataset and document its crawl dynamics. We also propose a framework for modeling the scaling rate of various data structures as crawl size goes to infinity and offer a methodology for comparing crawl coverage to that of commercial search engines.

It is well established that physical layer impairments significantly affect the performance of optical networks. The management of these impairments is critical for successful transmission, and may significantly affect network layer routing decisions. Hence the traditional divide-and-conquer layered approach is sub-optimal, which has led to work on cross-layer techniques for routing in optical networks. Apart from fiber loss, one critical physical layer impairment that limits the capacity of optical networks is fiber nonlinearity. Handling nonlinearity introduces significant complexity to the traditional cross-layer approaches. We formulate and solve a joint routing and power control problem to optimize the system throughput that takes into consideration both fiber loss and nonlinearity. The joint power control and routing problem considered is a nonlinear integer programming problem. By characterizing the feasible solution space of the power control problem we find a set of universal power settings that transforms the complex power control and routing problem into a constrained path routing problem. We then propose an efficient Fully Polynomial Time Approximation Scheme (FPTAS) to solve the constrained path routing problem. Simulation results show that our proposed algorithm significantly improves network throughput and greatly outperforms greedy heuristics by providing a guaranteed performance bound.

Energy efficiency is an important issue in the study of wireless sensor networks. Given a homogeneous set of sensors with unit lifetime and a set of target points, find an active/sleeping schedule for sensors to maximize the lifetime of k-coverage, i.e., the time period during which every target point is covered by at least k active sensors. This is a well known problem in wireless sensor networks concerning with energy efficiency. When k = 1, it is called the maximum lifetime coverage problem which has been proved to have a polynomial-time (4 + ε)-approximation. When k ≥ 2, it is the maximum lifetime fault-tolerant coverage problem. Previous to this work, only in the case k = 2, a polynomial-time (6 + ε)-approximation is found. In this paper, we will make a significant progress by showing that for any positive integer k, there exists a polynomial-time (4 + ε)-approximation, and for k = 1,2, the performance ratio can be improved to (3 + ε).

In deadline-constrained data aggregation in wireless sensor networks (WSNs), the imposed sink deadline in an interference-limited network hinders participation of all sensor nodes in data aggregation. Thus, a subset of nodes can contribute in aggregation and quality of aggregation (QoA) increases with the growth of the number of participating nodes. Scheduling the nodes' transmissions is a central problem, which aims to maximize the QoA, while satisfying the sink deadline, i.e., on-time delivery of the sensed data to the sink node. Although the previous studies have proposed optimal scheduling algorithms to this problem given a particular aggregation tree, there is no work on constructing optimal tree in this context. The underlying aggregation tree can make a big difference on QoA since we demonstrate that the ratio between the maximum achievable QoAs of different trees could be as large as O(2D), where D is the sink deadline. In this paper, we cast an optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. The problem is combinatorial in nature and difficult to solve as we prove its NP-hardness. We employ Markov approximation framework and devise two distributed algorithms with different computation overheads to find bounded close-to-optimal solutions. Simulation experiments in a set of representative randomly-generated scenarios show that the proposed algorithms significantly improve QoA by 101% and 93% on average compared to the best, to our knowledge, existing alternative methods.

Overflow loss systems have wide applications in telecommunications and multimedia systems. In this paper, we consider an overflow loss system consisting of a set of finite-buffer processor-sharing (PS) queues, and develop effective methods for evaluation of its blocking probability. For such a problem, an existing approximation of the blocking probability is based on decomposition of the system into independent PS queues. We provide a new approximation which instead performs decomposition on a surrogate model of the original system, and demonstrate via extensive numerical results that our new approximation is more accurate and robust than the existing approach. We also examine the sensitivity of the blocking probability to the service time distribution, and demonstrate that an exponential distribution is a good approximation for a wide range of service time distributions.

A Multi-User MIMO (MU-MIMO) Access Point (AP) can obtain a capacity gain by simultaneously transmitting to multiple clients. This technique requires Channel State Information (CSI) at the transmitting AP to set antenna gains and phases to enable simultaneous reception through beamforming. The AP must also select both the mode (number of transmit and collective receive antennas) and the user set prior to transmission. While the ideal mode and user selection is a function of CSI, CSI must be estimated with an overhead intensive channel sounding process. We design, implement, and evaluate Pre-sounding User and Mode selection Algorithm (PUMA), a method for mode and user selection prior to channel sounding. We show that even without CSI, PUMA (i) exploits theoretical properties of MU-MIMO system scaling with respect to mode, (ii) characterizes the relative cost of each potential mode, and (iii) estimates per-stream transmission rate and aggregate throughput in each mode for a potential user set, all without CSI. Once PUMA has selected the appropriate mode and user group, the chosen protocol's channel sounding method is used on the intended user subset to carry out the transmission. We show that, on average, PUMA selects the mode and group that achieves an aggregate rate within 3% of the saturation throughput of what would have been achieved by sounding all users (which would require significant additional overhead). Moreover, we show that PUMA obtains 30% higher aggregate throughput compared to the best fixed-mode policy that uses the maximum number of available transmit and receive antennas.

We consider the problem of streaming live content to a cluster of co-located wireless devices that have both an expensive unicast base-station-to-device (B2D) interface, as well as an inexpensive broadcast device-to-device (D2D) interface, which can be used simultaneously. Our setting is a streaming system that uses a block-by-block random linear coding approach to achieve a target percentage of on-time deliveries with minimal B2D usage. Our goal is to design an incentive framework that would promote such cooperation across devices, while ensuring good quality of service. Based on ideas drawn from truth-telling auctions, we design a mechanism that achieves this goal via appropriate transfers (monetary payments or rebates) in a setting with a large number of devices, and with peer arrivals and departures. Here, we show that a Mean Field Game can be used to accurately approximate our system. Furthermore, the complexity of calculating the best responses under this regime is low. We implement the proposed system on an Android testbed, and illustrate its efficient performance using real world experiments.

The amount of sensory data manifests an explosive growth due to the increasing popularity of Wireless Sensor Networks. The scale of the sensory data in many applications has already exceeds several petabytes annually, which is beyond the computation and transmission capabilities of the conventional WSNs. On the other hand, the information carried by big sensory data has high redundancy because of strong correlation among sensory data. In this paper, we define the concept of e-dominant dataset, which is only a small data set and can represent the vast information carried by big sensory data with the information loss rate being less than e, where e can be arbitrarily small. We prove that drawing the minimum e-dominant dataset is polynomial time solvable and provide a centralized algorithm with 0(n3) time complexity. Furthermore, a distributed algorithm with constant complexity (O(l)) is also designed. It is shown that the result returned by the distributed algorithm can satisfy the e requirement with a near optimal size. Finally, the extensive real experiment results and simulation results are carried out. The results indicate that all the proposed algorithms have high performance in terms of accuracy and energy efficiency.

The continuously growing number of multimedia applications in current communication networks highlights the necessity for an efficient resource allocation mechanism to capture the unique characteristics of multi-tiered multimedia applications and allocate network capacity in an efficient way. This paper examines the problem of sharing the network throughput under the existence of inelastic traffic flows that follow a multi-tiered utility function. First, the concept of multi-sigmoidal utilities is introduced in order to describe user satisfaction, then, the implications of the use of such utilities are discussed for two different allocation policies; the bandwidth-proportional and the utility-proportional fairness allocation policies. In the former case, the intrinsic reasons of possible network oscillations are analyzed in detail and a heuristic to overcome such situations is proposed. In the latter one, where such oscillations are not possible, efficient ways to calculate a closed form solution for the optimal rate allocation are described. Moreover, a novel mathematical representation of such a multi-sigmoidal utility is presented and closed form solutions for a number of application types are calculated. Finally, the efficiency and robustness of the proposed algorithms is evaluated by simulations for different network topologies and compared against other work in literature.

This paper presents LDSP (i.e., low-duty-cycle synchronization protocol), a design that enables scalable clock synchronization in wireless networks with low-duty-cycle radio operations. LDSP prevents exponential error proliferation of many available solutions, if applied in the low-duty-cycle scenario, by introducing a new mechanism of parallel synchronization that is naturally immune to excessive message delays widely existing in such networks. The key novelty behind LDSP is its separation of clock drift rate estimation from the error polluted global reference time in a unique manner, which helps eliminate compound errors that would otherwise amplify aggressively over the message delay at each hop during time dissemination. With LDSP, the time error is bounded to low-order polynomial growth as O(h√h), where h is the hop distance to the reference node, according to theoretical analysis verified by numerical simulation. To evaluate, LDSP was implemented on two hardware platforms equipped with different driven clock sources and compared with representative synchronization protocols via experiments in both indoor and outdoor environments. Results show that the proposed design is practical, effective, and features significantly improved scalability under real-world conditions.

We study the problem of maximizing the multicast throughput in a dense multi-channel multi-radio (MC-MR) wireless network with multiple multicast sessions. Specifically, we consider a fully connected network topology where all nodes are within transmission range of each other. In spite of its simplicity, this topology is practically important since it is encountered in several real-world settings. Further, a solution to this network can serve as a building block for more general scenarios that are otherwise intractable. For this network, we show that the problem of maximizing the uniform multicast throughput across multiple sessions is NP-hard. However, its special structure allows us to derive useful upper bounds on the achievable uniform multicast throughput. We show that an intuitive class of algorithms that maximally exploit the wireless broadcast feature can result in very poor worst case performance. Using a novel group splitting idea, we then design two polynomial time approximation algorithms that are guaranteed to achieve a constant factor of the throughput bound under arbitrary multicast group memberships. These algorithms are simple to implement and provide interesting tradeoffs between the achievable throughput and the total number of transmissions used.

The recent mobile data explosion has increased the interest for mobile user-provided networks (MUPNs), where users share their Internet access by exploiting the diversity in their needs and resource availability. Although promising, MUPNs raise unique challenges. Namely, the success of such services relies on user participation which in turn can be achieved on the basis of a fair and efficient resource (i.e., Internet access and battery energy) exchange policy. The latter should be devised and imposed in a very fast time scale, based on near real-time feedback from mobile users regarding their needs, resources, and network conditions that are rapidly changing. To address these challenges we design and implement a novel cloud-controlled MUPN system, that employs software defined networking support on mobile terminals, to dynamically apply data forwarding policies with adaptive flow-control. We devise these policies by solving a coalitional game that is played among the users. We prove that the game has a non-empty core and hence the solution, which determines the servicing policy, incentivizes the users to participate. Finally, we evaluate the performance of the service in a prototype, where we investigate its performance limits, quantify the implementation overheads, and justify our architecture design choices.

The size of a packet has a strong influence on the quality of wireless data communications. In traditional wireless networks, there is an inherent trade-off in determining the packet size. First of all, compared with long packets, short packets are less likely to be affected by the error-prone wireless channels. However, short packets suffer overhead due to headers. In mobile cognitive radio (CR) networks, determining the secondary user (SU) packet size becomes much more complicated and critical. In addition to all the impacts in traditional wireless networks, the primary user (PU) activity and the mobility of SUs and PUs have significant impacts on the SU packet size. Moreover, the channel fading caused by the SU mobility also has an impact on the SU packet size. More importantly, all these impacts on SU packet size constantly vary with time and space, which makes this issue extremely challenging. Without a careful design of the SU packet size, both SU and PU transmissions may suffer severe performance degradation. In this paper, the optimal SU packet size issue in mobile CR networks under fading channels is studied. We mathematically model these impacts and derive the optimal SU packet size. To the best of our knowledge, this is the first work that systematically investigates the optimal SU packet size issue in mobile CR networks.