INFOCOM 2019 Papers

With the amount of user data crowdsourced for data mining dramatically increasing, there is an urgent need to protect the privacy of individuals. Differential privacy mechanisms are conventionally adopted to add noise to the user data, so that an adversary is not able to gain any additional knowledge about individuals participating in the crowdsourcing, by inferring from the learned model. However, such protection is usually achieved with significantly degraded learning results. We have observed that the fundamental cause of this problem is that the relationship between model utility and data privacy is not accurately characterized, leading to privacy constraints that are overly strict. In this paper, we address this problem from an optimization perspective, and formulate the problem as one that minimizes the accuracy loss given a set of privacy constraints. We use sensitivity to describe the impact of perturbation noise to the model utility, and propose a new optimized additive noise mechanism that improves overall learning accuracy while conforming to individual privacy constraints. As a highlight of our privacy mechanism, it is highly robust in the high privacy regime (when ∈ → 0), and against any changes in the model structure and experimental settings.

Multipath networks are widely used in data centers and load balancing is one of the most important technologies to improve their performances. Due to the ever-increasing in data center network size, existing load balancing algorithms face the challenges of efficiency and scalability. In this paper, we propose a new load balancing algorithm for large-scale, multi-tier fat-tree based data center networks. Different from the conventional architectures, a multi-tier fat-tree is divided into multiple routing domains according to the topology, and the routing processes in different domains are independent. The devices outside a routing domain can only access the specific interfaces provided by this domain. It is thus very convenient for deployment and modular upgrade. We also design a distributed and data-driven feedback mechanism, with which the routing decision is based on the global load information. We prove that the new algorithm can achieve perfect load balancing in multipath networks and show that the new algorithm outperforms all other load balancing algorithms in performance.

Cross-Technology Communication (CTC) is an emerging technique that enables direct communication across different wireless technologies. The state-of-the-art works in this area propose physical-level CTC, in which the transmitters emulate signals that follow the receiver's standard. Physical-level CTC means considerable processing complexity at the transmitter, which doesn't apply to the communication from a low-end transmitter to a high-end receiver, e.g. from ZigBee to WiFi. This paper presents transmitter-transparent cross-technology communication, which leaves the processing complexity solely at the receiver side and therefore makes a critical advance toward bidirectional high-throughput CTC. We implement our proposal as LEGO-Fi, the communication from ZigBee to WiFi. The key technique inside is cross-demapping, which stems from two key technical insights: (1) A ZigBee packet leaves distinguishable features when passing the WiFi modules. (2) Compared to ZigBee's simple encoding and modulation schemes, the rich processing capacity of WiFi offers extra flexibility to process a ZigBee packet. The evaluation results show that LEGO-Fi achieves a throughput of 213.6Kbps, which is respectively 13000× and 1200× faster than FreeBee and ZigFi, the two existing ZigBee-to-WiFi CTC approaches.

We consider a transmission scheduling problem in which multiple systems receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall age of information. We call this problem the Min-Age problem. This problem is first studied by He et at. [IEEE Trans. Inform. Theory, 2018], who identified several special cases where the problem can be solved optimally in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant r ≥ 1, every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-Age problem. Second, we give a randomized 2.733-approximation algorithm and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-Age problem is NP-hard.

Database-driven Dynamic Spectrum Sharing (DSS) is a promising technical paradigm for enhancing spectrum efficiency by allowing secondary user to opportunistically access licenced spectrum channels without interfering with primary users' transmissions. In database-driven DSS, a geo-location database administrator (DBA) maintains the spectrum availability in its service region in the form of a radio environment map (REM) and grant or deny secondary users' spectrum access requests based on primary users' activities. Crowdsourcing-based spectrum sensing has great potential in improving the accuracy of the REM at the DBA but requires strong incentives and privacy protection to simulate mobile users' participation. To tackle this challenge, this paper introduces a novel differentially-private reverse auction mechanism for crowdsourcing-based spectrum sensing. The proposed mechanism allows the DBA to select spectrum sensing participants under a budget constraint while offering differential bid privacy, approximate truthfulness, and approximate accuracy maximization. Extensive simulation studies using a real spectrum measurement dataset confirm the efficacy and efficiency of the proposed mechanism.

Future millimeter-wave networks will support very high densities of devices and access points. This vastly increases the overhead required for access point selection and beam training. Fortunately, the quasi-optical properties of millimeter-wave channels make location-based network optimization a highly promising technique to reduce control overhead in such millimeter-wave WLANs. In this paper, we extract channel state information from off-the-shelf routers, we use it to design a high accuracy location system, and then show how location information enables the optimization of network operations. The resulting scheme, named LEAP, can predict blockage, optimize access point association, and select the most suitable antenna beam patterns while significantly reducing the beam training overhead. We show that compared to standard state-of-the-art 802.11ad systems, LEAP's location driven management greatly improves network performance and link stability.

We consider the placement of jobs inside a data center. Traditionally, this is done by a task orchestrator without taking into account network constraints. According to recent studies, network transfers represent up to 50% of the completion time of classical jobs. Thus, network resources must be considered when placing jobs in a data center. In this paper, we propose a new scheduling framework, introducing network tasks that need to be executed on network machines alongside traditional (CPU) tasks. The model takes into account the competition between communications for the network resources, which is not considered in the formerly proposed scheduling models with communication. Network transfers inside a data center can be easily modeled in our framework. As we show, classical algorithms do not efficiently handle a limited amount of network bandwidth. We thus propose new provably efficient algorithms with the goal of minimizing the makespan in this framework. We show their efficiency and the importance of taking into consideration network capacity through extensive simulations on workflows built from Google data center traces.

Online social networks (OSNs) routinely share and analyze user data. This requires protection of sensitive user information. Researchers have proposed several techniques to anonymize the data of OSNs. Some differential-privacy techniques claim to preserve graph utility under certain graph metrics, as well as guarantee strict privacy. However, each graph utility metric reveals the whole graph in specific aspects.We employ persistent homology to give a comprehensive description of the graph utility in OSNs. This paper proposes a novel anonymization scheme, called PHDP, which preserves persistent homology and satisfies differential privacy. To strengthen privacy protection, we add exponential noise to the adjacency matrix of the network and find the number of adding/deleting edges. To maintain persistent homology, we collect edges along persistent structures and avoid perturbation on these edges. Our regeneration algorithms balance persistent homology with differential privacy, publishing an anonymized graph with a guarantee of both. Evaluation result show that the PHDP-anonymized graph achieves high graph utility, both in graph metrics and application metrics.

In this paper, we revisit the estimation of the size distribution of packet flows in Internet traffic through an inversion approach for several packet sampling schemes which are based on probabilistic sampling (PS). We first study the statistical properties of the previously introduced inversion estimator in its general form and make connections to the singular value decomposition. This motivates the use of a regularization technique in the estimation of the flow size distribution. More specifically, a penalized weighted least square approach is proposed. We compare theoretically the penalized estimator under simplified assumptions against the (non-penalized) inversion approach in order to explain differences in their statistical behaviors. A data study with two real traces shows that the proposed penalized estimator outperforms the inversion estimator for all sampling schemes, corroborating the theoretical analysis. This work reveals that the simplest sampling schemes based on PS, that do not work with small sampling probabilities under the inversion approach, can be used with the penalized approach. Furthermore, the penalized approach allows considering smaller packet sampling rates for all the other sampling schemes.

Non-orthogonal multiple access (NOMA) has shown potential for scalable multicast of video data. However, one key drawback for NOMA-based video multicast is the limited number of layers allowed by the embedded successive interference cancellation algorithm, failing to meet satisfaction of heterogeneous receivers. We propose a novel receiver-driven superposed video multicast (Supcast) scheme by integrating Softcast, an analog-like transmission scheme, into the NOMA-based system to achieve high bandwidth efficiency as well as gradual decoding quality proportional to channel conditions at receivers. Although Softcast allows gradual performance by directly transmitting power-scaled transformation coefficients of frames, it suffers performance degradation due to discarding coefficients under insufficient bandwidth and its power allocation strategy cannot be directly applied in NOMA due to interference. In Supcast, coefficients are grouped into chunks, which are basic units for power allocation and superposition scheduling. By bisecting chunks into base-layer chunks and enhanced-layer chunks, the joint power allocation and chunk scheduling is formulated as a distortion minimization problem. A two-stage power allocation strategy and a near-optimal low-complexity algorithm for chunk scheduling based on the matching theory are proposed. Simulation results have shown the advantage of Supcast against Softcast as well as the reference scheme in NOMA under various practical scenarios.

Edge Computing brings flexibility and scalability of virtualization technologies at the edge of the network, enabling service providers to deploy new applications over a richer network infrastructure. However, the coexistence of such variety of applications on the same infrastructure exacerbates the already challenging problem of coordinating resource allocation while preserving the resource assignment optimality. In fact, (i) each application can potentially require different optimization criteria due to their heterogeneous requirements, and (ii) we may not count on a centralized orchestrator due to the highly dynamic nature of edge networks. To solve this problem, we present DRAGON, a Distributed Resource AssiGnment and OrchestratioN algorithm that seeks optimal partitioning of shared resources between different applications running over a common edge infrastructure. We designed DRAGON to guarantee both a bound on convergence time and an optimal (1-1/e)-approximation with respect to the Pareto optimal resource assignment. We evaluate convergence and performance of DRAGON on a prototype implementation, assessing the benefits compared to traditional orchestration approaches.

The traditional privacy-preserving image retrieval schemes not only bring large computational and communication overhead but also cannot well protect the image and query privacy in multi-user scenarios. To solve the above problems, we first propose a basic privacy-preserving content-based image retrieval (CBIR) framework which significantly reduces storage and communication overhead compared with the previous works. Furthermore, we design a new efficient key conversion protocol to support unshared key multi-owner multi-user image retrieval without losing search precision. Moreover, our framework supports unbounded attributes and can trace malicious users according to leaked secret keys, which significantly improve the usability of multi-source data sharing. Strict security analysis shows that the user privacy and outsourced data security can be guaranteed during the image retrieval process, and the performance analysis using real-world dataset shows that the proposed image retrieval framework is efficient and feasible for practical applications.

Much of the incremental improvement to TCP over the past three decades had the ultimate goal of making it more effective in using the long-fat pipes of the global Internet. This resulted in a rigid set of mechanisms in the protocol that put TCP at a disadvantage in small-delay environments such as data centers. In particular, in the presence of the shallow buffers of commodity switches and the short round trip times in data centers, the continued use of a large TCP initial congestion window and a huge minimum retransmission timeout (both inherited from the Internet-centric design) results in a very short TCP loss cycle that affects particularly the flow completion times of short-lived incast flows. In this paper, we first investigate empirically the TCP loss cycle and discuss its impact on packet losses, recovery and delay; then we propose a switch-based congestion controller with hysteresis (HSCC) that aims to stretch the TCP loss cycle without modifying TCP itself. To protect incast flows from severe congestion, HSCC is designed to transparently induce the TCP source to alternate between its native TCP congestion control algorithm and a slower more conservative constant bit rate flow control mode that is activated when congestion is imminent. We show the stability of HSCC via analytical modelling, and demonstrate its effectiveness via simulation and implementation in a small testbed.

Management of networked Internet of Things (IoT) infrastructure with in-network processing capabilities is becoming increasingly difficult due to the volatility of the system with low-cost resource-constraint devices. Traditional software-defined networking (SDN) based management systems are not suitable to handle the plug and play nature of such systems. Therefore, in this paper, we propose Aloe, an elastically auto-scalable SDN orchestration framework. Instead of using service grade SDN controller applications, Aloe uses multiple lightweight controller instances to exploit the capabilities of in-network processing infrastructure. The proposed framework ensures the availability and significant reduction in flow-setup delay by deploying instances near the resource constraint IoT devices dynamically. Aloe supports fault-tolerance and can recover from network partitioning by employing self-stabilizing placement of migration capable controller instances. The performance of the proposed system is measured by using an in-house testbed along with a large scale deployment in Amazon web services (AWS) cloud platform. The experimental results from these two testbed show significant improvement in response time for standard IoT based services. This improvement of performance is due to the reduction in flow-setup time. We found that Aloe can improve flow-setup time by around 10%-30% in comparison to one of the state of the art orchestration framework.

With the exponentially increasing number of Internet of Things (IoT) devices and the huge volume of data generated by these devices, there is a pressing need to investigate a more efficient communication method in both frequency and time domains at the edge of the IoT networks. In this paper, we present Amphista, a novel cross-layer design for IoT communication and data forwarding that can more efficiently utilize the ever increasingly crowded 2.4 GHz spectrum near the gateway. Specifically, by using a single ZigBee data stream, Amphista enables a ZigBee device to send out two different pieces of information to both the WiFi gateway and another ZigBee device. We further leverage this unique feature and design a novel forwarding protocol that can simultaneously forward uplink (e.g., collecting sensing data) and downlink (e.g., disseminating software updates) data by using a single ZigBee data stream. Our extensive experimental results show that Amphista significantly improves throughput (by up to 400×) and reduces the latency.

Urban environments are a particularly important application scenario for the Internet of Things (IoT). These environments are usually dense and dynamic; in contrast, IoT devices are resource-constrained, thus making reliable data collection and scalable coordination a challenge. This work leverages the fog networking paradigm to devise a multi-tier data offloading protocol suitable for diverse data-centric applications in urban IoT scenarios. Specifically, it takes advantage of heterogeneity in the network so that sensors can collaboratively offload data to each other or to mobile gateways. Second, it evaluates the performance of this offloading process through the amount of data successfully reported to the cloud. In detail, it provides an analytical characterization of data drop-off rates as a random process and derives a light-weight yet efficient method for collaborative data offloading. Finally, it shows that the proposed fog-based solution significantly decreases the data drop-off rate through both analysis and extensive trace-driven simulations based on human mobility data from real urban settings.

Understanding customer mobility patterns to commercial districts is crucial for urban planning, facility management, and business strategies. Trade areas are a widely applied measure to quantity where the visitors are from. Traditional trade area analysis is limited to small-scale or store-level studies because information such as visits to competitor commercial entities and place of residence is collected by labour-intensive questionnaires or heavily biased location-based social media data. In this paper, we propose CellTradeMap, a novel district-level trade area analysis framework using mobile flow records (MFRs), a type of fine-grained cellular network data. CellTradeMap extracts robust location information from the irregularly sampled, noisy MFRs, adapts the generic trade area analysis framework to incorporate cellular data, and enhances the original trade area model with cellular-based features. We evaluate CellTradeMap on a large-scale cellular network dataset covering 3.5 million mobile phone users in a metropolis in China. Experimental results show that the trade areas extracted by CellTradeMap are aligned with domain knowledge and CellTradeMap can model trade areas with a high predictive accuracy.

In this work, we provide a comprehensive analysis of stability properties and delay gains that wireless multicasting capabilities, as opposed to more traditional unicast transmissions, can provide for content distribution in mobile networks. In particular, we propose a model and characterize the average queue-length (and hence average delay) performance of unicasting and various multicasting strategies for serving a dynamic user population at the wireless edge. First, we show that optimized static randomized multicasting (we call it `blind multicasting') leads to stable-everywhere operation irrespective of the network loading factor (given by the ratio of the demand rate to the service rate) and the content popularity distribution. In contrast, traditional unicasting suffers from unstable operation when the loading factor approaches one, although it outperforms blind multicasting at small loading factor levels. This motivates us to study `work-conserving multicast' policies next that always outperform unicasting while still offering stable-everywhere operation. Then, in the worst-case of uniformly-distributed content popularity, we explicitly characterize the scaling of the average queue-length (and hence delay) under a first-come-first-serve multicast strategy as a function of the database size and the loading factor. Consequently, this work provides the fundamental limits, as well as the guidelines, for the design and performance analysis of efficient multicasting strategies for wireless content distribution.

Java reflection and dynamic class loading (DCL) are effective features for enhancing the functionalities of Android apps. However, these features can be abused by sophisticated malware to bypass detection schemes. Advanced malware can utilize reflection and DCL in conjunction with Android Inter-App Communication (IAC) to launch collusion attacks using two or more apps. Such dynamically revealed malicious behaviors enable a new type of stealthy, collusive attacks, bypassing all existing detection mechanisms. In this paper, we present DINA, a novel hybrid analysis approach for identifying malicious IAC behaviors concealed within dynamically loaded code through reflective/DCL calls. DINA continuously appends reflection and DCL invocations to control-flow graphs; it then performs incremental dynamic analysis on such augmented graphs to detect the misuse of reflection and DCL that may lead to malicious, yet concealed, IAC activities. Our extensive evaluation on 3,000 real-world Android apps and 14,000 malicious apps corroborates the prevalent usage of reflection and DCL, and reveals previously unknown and potentially harmful, hidden IAC behaviors in real-world apps.