INFOCOM 2017 Papers

Nowadays, high-bandwidth networks are easily accessible in data centers. However, existing distributed graph-processing frameworks fail to efficiently utilize the additional bandwidth capacity in these networks for higher performance, due to their inefficient computation and communication models, leading to very long waiting times experienced by users for the graph-computing results. The root cause lies in the fact that the computation and communication models of these frameworks generate, send and receive messages so slowly that only a small fraction of the available network bandwidth is utilized. In this paper, we propose a high-performance distributed graph-processing framework, called BlitzG, to address this problem. This framework fully exploits the available network bandwidth capacity for fast graph processing. Our approach aims at significant reduction in (i) the computation workload of each vertex for fast message generation by using a new slimmed-down vertex-centric computation model and (ii) the average message overhead for fast message delivery by designing a lightweight message-centric communication model. Evaluation on a 40Gbps Ethernet, driven by real-world graph datasets, shows that BlitzG outperforms the state-of-the-art distributed graph-processing frameworks by up to 27x with an average of 20.7x.

Since the dummy-based method can provide precise query results without any requirement for a third party or key sharing, it has been widely used to protect the user's location privacy in location-based services. However, the neighboring location sets submitted in consecutive requests always include a close spatiotemporal correlation, which enables the adversary to identify some dummies. Therefore, the existing dummy-based schemes cannot protect the user's location privacy completely. To solve this problem, based on the dummies generated by the existing schemes, this paper filters out the dummies that can be identified by taking into account of the spatiotemporal correlation from three aspects, namely time reachability, direction similarity and in-degree/out-degree. In this way, the rest dummies can satisfy the user's personalized privacy protection requirement. Security analysis shows that the proposed scheme successfully perturbs the spatiotemporal correlation between neighboring location sets, therefore, it is infeasible for the adversary to distinguish the user's real location from the dummies. Furthermore, extensive experiments indicate that the proposal is able to protect the user's location privacy effectively and efficiently.

In this work, we propose an SDN-based WLAN monitoring and management framework called RFlow+to address WiFi service dissatisfaction caused by the limited view (lack of scalability) of network traffic monitoring and absence of intelligent and timely network treatments. Existing solutions (e.g., OpenFlow and sFlow) have limited view, no generic flow description, and poor trade-off between measurement accuracy and network overhead depending on the selection of the sampling rate. To resolve these issues, we devise a two-level counting mechanism, namely a distributed local counter (on-site and real-time) and central collector (a summation of local counters). With this, we proposed a highly scalable monitoring and management framework to handle immediate actions based on short-term (e.g., 50 ms) monitoring and eventual actions based on long-term (e.g., 1 month) monitoring. The former uses the local view of each access point (AP), and the latter uses the global view of the collector. Experimental results verify that RFlow+can achieve high accuracy (less than 5% standard error for short-term and less than 1% for long-term) and fast detection of flows of interest (within 23 ms) with manageable network overhead. We prove the practicality of RFlow+by showing the effectiveness of a MAC flooding attacker quarantine in a real-world testbed.

Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.

IEEE 802.11n/ac wireless local area network (WLAN) supports frame aggregation, called aggregate medium access control (MAC) protocol data unit (A-MPDU), to enhance MAC efficiency by reducing protocol overhead. However, the current channel estimation process conducted only once during the preamble reception is known to be insufficient to ensure robust delivery of long A-MPDU frames in mobile environments. To cope with this problem, we first build a model which represents the impact of mobility with a noise vector in the I-Q plane, and then analyze how the mobility affects the A-MPDU reception performance. Based on our analysis, we develop STRALE, a standard-compliant and mobility-aware PHY rate and A-MPDU length adaptation scheme with ease of implementation. Through extensive simulations with 802.11ac using ns-3 and prototype implementation with commercial 802.11n devices, we demonstrate that STRALE achieves up to 2.9x higher throughput, compared to a fixed duration setting according to IEEE 802.11 standard.

This paper deals with the efficient design of network switch/routers for an optical data center network. Each switch has multiple components such as ingress/egress interfaces, optical and/or electronic buffers, interconnection switching fabric and so on. There are several possible choices available for each of these components. This paper presents a systematic approach to designing the switch architecture using a combination of these component choices, while meeting specified design criteria. It requires formally defining the structure of a switch and enforcing semantics across components. This is formulated as a constraint optimization problem with formal language grammar guiding its search process. This problem formulation is used to identify the best-possible architecture for a hierarchical DCN. Two of the three solutions identified were new and were not reported in literature. These solutions were also validated experimentally.

Large-scale MU-MIMO is a promising technology to scale network capacity and the capacity gain grows linearly with the numbers of antennas and users in theory. However, its practical deployment faces three critical challenges in the state-of-the-art WLANs: i) the demand of a large number of expensive RF chains; ii) the linear growth of feedback overheads with the number of antennas; iii) the lack of scalable user selection scheme for a large user population. In this paper, we design BUSH, a large-scale MU-MIMO prototype that performs scalable beam user selection with hybrid beamforming for phased-array antennas in legacy WLANs. The architecture of BUSH consists of three components. Firstly, a low complexity algorithm assigns each pair of RF chain and analog beam to the users to effectively reduce channel correlation and cross-talk interference without instantaneous CSI feedbacks. Secondly, as a prerequisite of user selection, BUSH presents a low-overhead probing scheme in multi-carrier WLANs, and designs a highly accurate blind Power Azimuth Spectrum (PAS) estimation algorithm using a single RF chain. Thirdly, the phased-array antennas use analog beamforming to steer spatial beams toward each selected downlink user, and the finite number of RF chains use beamforming to further mitigate the interference among users. We implement BUSH on the WARPv3 boards and evaluate its performance in more than 30 indoor scenarios. The experimental results show that in terms of total throughput BUSH outperforms the legacy 802.11ac by 2.08×, and an alternative benchmark system by 1.22× on average.

Data aggregation is an essential operation for the sink to obtain summary information in a Wireless Sensor Network (WSN). The problem of Minimum Latency Aggregation Schedule (MLAS) which seeks a fastest and collision-free aggregation schedule has been well studied when nodes are always awake. However, in duty-cycle WSNs, nodes can only receive data in active state. In such networks, it is of great importance to exploit the limited active time slots to reduce aggregation latency. Unfortunately, few studies have addressed this issue and most previous aggregation methods rely on fixed structures which greatly limit the exploitation of the active time slots from other neighbors. In this paper, we investigate the MLAS problem in duty-cycle WSNs without considering structures. We propose the first distributed aggregation algorithm for duty-cycle WSNs, in which the aggregation tree and a conflict-free schedule are generated simultaneously. Compared with the previous centralized and distributed methods, the aggregation latency and the utilization ratio of available time slots are greatly improved. The theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency and communication cost.

This paper proposes an algorithm for optimal decentralized traffic engineering in communication networks. We aim at distributing the traffic among the available routes such that the network utility is maximized. In some practical applications, modeling network utility using non-concave functions is of particular interest, e.g., video streaming. Therefore, we tackle the problem of optimizing a generalized class of non-concave utility functions. The approach used to solve the resulting non-convex network utility maximization (NUM) problem relies on designing a sequence of convex relaxations whose solutions converge to that of the original problem. A distributed algorithm is proposed for the solution of the convex relaxation. Each user independently controls its traffic in a way that drives the overall network traffic allocation to an optimal operating point subject to network capacity constraints. All computations required by the algorithm are performed independently and locally at each user using local information and minimal communication overhead. The only non-local information needed is binary feedback from congested links. The robustness of the algorithm is demonstrated, where the traffic is shown to be automatically rerouted in case of a link failure or having new users joining the network. Numerical simulation results are presented to validate our findings.

Interference management (IM) is essential to wireless communication networks, but interference suppression, a key component of IM, is known to degrade users' achievable spectral efficiency (SE). It is thus important to select an appropriate IM method with optimal operating parameters according to diverse network deployments, transmit power differences of various communication equipments, and dynamically changing channel conditions so as to balance the benefits brought by and the cost of IM. Interference neutralization (IN) has recently been receiving considerable attention, with which a duplicate of interference of the same strength and opposite phase w.r.t. the original interfering signal is generated to neutralize the disturbance at the intended receiver. However, to the best of our knowledge, all existing IN schemes assume that interference is completely neutralized without accounting for their power consumption. To remedy this deficiency, we propose a novel scheme, called dynamic interference neutralization (DIN). By intelligently determining the appropriate portion of interference to be neutralized, we balance the transmitter's power used for IN and the desired signal's transmission. We then present a new way to adaptively select one of DIN and other IM methods by taking into account the cost of multiple IM methods and their benefits. Our analysis has shown that DIN can include complete IN and non-interference management (non-IM) as special cases. The proposed strategy is shown via simulation to be able to make better use of the transmit power than existing IM methods, hence enhancing users' SE.

In Wyner wiretap II model of communication, Alice and Bob are connected by a channel that can be eavesdropped by an adversary with unlimited computation who can select a fraction of communication to view, and the goal is to provide perfect information theoretic security. Information theoretic security is increasingly important because of the threat of quantum computers that can effectively break algorithms and protocols that are used in today's public key infrastructure. We consider interactive protocols for wiretap II channel with active adversary who can eavesdrop and add adversarial noise to the eavesdropped part of the codeword. These channels capture wireless setting where malicious eavesdroppers at reception distance of the transmitter can eavesdrop the communication and introduce jamming signal to the channel. We derive a new upperbound R ≤ 1 - ρ for the rate of interactive protocols over two-way wiretap II channel with active adversaries, and construct a perfectly secure protocol family with achievable rate 1 - 2ρ + ρ2. This is strictly higher than the rate of the best one round protocol which is 1 - 2ρ, hence showing that interaction improves rate. We also prove that even with interaction, reliable communication is possible only if ρ <; 1/2. An interesting aspect of this work is that our bounds will also hold in network setting when two nodes are connected by n paths, a ρ of which is corrupted by the adversary. We discuss our results, give their relations to the other works, and propose directions for future work.

Wireless Power Transfer (WPT) technology has witnessed huge development because of its convenience and reliability. This paper concerns the fundamental issue of wireless charger PLacement with Optimized charging uTility (PLOT), that is, given a fixed number of chargers and a set of points on the plane, determining the positions and orientations of chargers such that the overall expected charging utility for all points is maximized. To address PLOT, we propose a 1 - 1/e - ε approximation algorithm. First, we present techniques to approximate the nonlinear charging power and the expected charging utility to make the problem almost linear. Second, we develop a Dominating Coverage Set extraction method to reduce the continuous search space of PLOT to a limited and discrete one without performance loss. Third, we prove that the reformulated problem is essentially maximizing a monotone submodular function subject to a matroid constraint, and propose a greedy algorithm to address this problem. We conduct both simulation and field experiments to validate our theoretical results, and the results show that our algorithm can outperform comparison algorithms by at least 46.3%.

Collapsed forwarding has long been used in cache systems to reduce the load on servers by aggregating requests for the same content. Named Data Networking (NDN) as a future Internet architecture incorporates this technique through a data structure called Pending Interest Table (PIT). The request aggregation feature suggests that PIT can be viewed as a nonreset time-to-live (TTL) based cache. The Content Store (CS) is a content cache placed in front of the PIT on the NDN forwarding path, so they make up a tandem cache network. To investigate the metrics of interest in this network, like the hit probability for the PIT and the CS, the expected PIT size, non-zero download delay (non-ZDD) should be taken into consideration. Caching policies usually assume zero download delay (ZDD), i.e., request and object arrive simultaneously, and numerous analytical methods have been proposed to study the ZDD caching policies. In this paper, after dissecting the LRU policy, we for the first time propose two LRU variants considering non-ZDD by defining separate operations for the request and object arrivals. When CS adopts the proposed LRU variants, the analysis of the CS-PIT network can still take advantage of the existing models, so the metrics of interest can be computed. Especially, the distribution for the “inter-miss” time of this network can be derived, which has not been achieved by prior works. Finally, the analytical results are verified through simulations.

RAM-based storage aggregates the RAM of servers in data center networks (DCN) to provide extremely high storage performance. For quick recovery of storage server failures, Mem-Cube [1] exploits the proximity of the BCube network to limit the recovery traffic to the recovery servers' 1-hop neighborhood. However, previous design is applicable only to BCube, and has suboptimal recovery performance due to congestion and contention. To address these problems, in this paper we propose CubeX, which generalizes the “1-hop” principle of MemCube for all cube-based networks, and improves the throughput and recovery performance of RAM-based key-value (KV) store via cross-layer optimizations. At the core of CubeX is to leverage the glocality (= globality + locality) of cube-based networks: it scatters backup data across a large number of disks globally distributed throughout the cube, and restricts all recovery traffic within the small local range of each server node. Our evaluation shows that CubeX efficiently supports RAM-based KV store for cube-based networks, and CubeX remarkably outperforms MemCube in both throughput and recovery time.

The paper relates to multi-resource sharing between flows with heterogeneous requirements as arises in networks with wireless links or software routers implementing network function virtualization. Bottleneck max fairness (BMF) is a sharing objective in this context with good performance. The paper shows that BMF results when local fairness is imposed at each resource while flow rates are controlled by an end-to-end window. We analytically prove convergence to BMF under a fluid model when flows share a network limited to 2 resources while numerical results confirm BMF convergence for larger networks. Simulation results illustrate the impact of packetized transmission.

The knowledge of link packet loss rates (PLRs) at different PHY layer configurations is vital for a number of wireless network optimization schemes. However, the very large number of PHY layer configurations offered by modern 802.11 n/ac networks has made probing-based PLR estimation at each available configuration extremely challenging. In this paper, we seek to answer the question “How to estimate the PLRs at each available PHY layer configuration with minimal overhead?” Our analysis of the PLR datasets collected from three 802.11 n/ac testbeds reveals that, for any given link, there are several configurations with similar PLR. However, capturing this similarity using well-known link quality indicators like RSSI, or PHY layer features such as MCS or number of MIMO streams is hard. Consequently, we explore the approach of clustering the available PHY layer configurations into a small number of clusters with similar PLR, independent of any other parameter, and only probe one representative configuration in each cluster. Using two real-world case studies - rate adaptation and multihop routing, we show that the proposed clustering-based PLR estimation helps network optimization schemes to reach optimal configurations faster leading to significant performance improvements.

In data centers, micro-burst is a common traffic pattern. The packet dropping caused by it usually leads to serious performance degradations. Therefore, much attention has been paid to avoiding buffer overflow caused by micro-burst traffic. In particular, ECN is widely used in data centers to keep persistent queue occupancy low, so that enough buffer space can be available as headroom to absorb micro-burst traffic. However, we find that instantaneous-queue-length-based ECN may cause problems in another direction - buffer underflow. Specifically, current ECN marking scheme in data centers is easy to trigger spurious congestion signals, which may result in overreaction of senders and queue length oscillations in switches. Since ECN threshold is low, the buffer may underflow and link capacity is not fully used. In this paper, we reveal this problem by experiments and simulations. Besides, we theoretically deduce the amplitude of queue length oscillations. The analysis result shows that overreaction of senders is caused by ECN mis-marking. Therefore, we propose Combined Enqueue and Dequeue Marking (CEDM), which can mark packets more accurately. Through simulations, we show that CEDM can greatly reduce throughput loss and improve flow completion time.

Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) - a novel algorithm for the frequency and top-k estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top-k identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the workloads' skewness. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. Additionally, we present d-Way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits.

As more knowledge is vastly added to the devices fuelling the Internet of Things (IoT) energy efficiency and real-time data processing are great challenges that must be tackled. In this paper, we introduce ADMin, a low-cost IoT framework that reduces on device energy consumption and the volume of data disseminated across the network. This is achieved by efficiently adapting the rate at which IoT devices disseminate monitoring streams based on run-time knowledge of the stream evolution, variability and seasonal behavior. Rather than transmitting the entire stream, ADMin favors sending updates for its estimation model from which values can be inferred, triggering dissemination only when shifts in the stream evolution are detected. Results on real-life testbeds, show that ADMin is able to reduce energy consumption by at least 83%, data volume by 71%, shift detection delays by 61% while maintaining accuracy above 91% in comparison to other IoT frameworks.