INFOCOM 2019 Papers

Network operators must continuously scale the capacity of their optical backbone networks to keep apace with the proliferation of bandwidth-intensive applications. Today’s optical networks are designed to carry large traffic aggregates with coarse-grained resource allocation, and are not adequate for maximizing utilization of the expensive optical substrate. Elastic Optical Network (EON) is an emerging technology that facilitates flexible allocation of fiber spectrum by leveraging finer-grained channel spacing, tunable modulation formats and Forward Error Correction (FEC) overheads, and baud-rate assignment, to right size spectrum allocation to customer needs. Virtual Network Embedding (VNE) over EON has been a recent topic of interest due to its importance for 5G network slicing. However, the problem has not yet been addressed while simultaneously considering the full flexibility offered by an EON. In this paper, we present an optimization model that solves the VNE problem over EON when lightpath configurations can be chosen among a large (and practical) set of combinations of paths, modulation formats, FEC overheads and baud rates. The VNE over EON problem is solved in its splittable version, which significantly increases problem complexity, but is much more likely to return a feasible solution. Given the intractability of the optimal solution, we propose a heuristic to solve larger problem instances. Key results from extensive simulations are: (i) a fully-flexible VNE can save up to 60% spectrum resources compared to that where no flexibility is exploited, and (ii) solutions of our heuristic fall in more than 90% of the cases, within 5% of the optimal solution, while executing several orders of magnitude faster.

Caller-ID spoofing deceives the callee into believing a call is originating from another user. Spoofing has been strategically used in the now-pervasive telephone fraud, causing substantial monetary loss and sensitive data leakage. Unfortunately, caller-ID spoofing is feasible even when user authentication is in place. State-of-the-art solutions either exhibit high overhead or require extensive upgrades, and thus are unlikely to be deployed in the near future. In this paper, we seek an effective and efficient solution for 4G (and conceptually 5G) carrier networks to detect (and block) caller-ID spoofing. Specifically, we propose Nascent, Network-assisted caller ID authentication, to validate the caller-ID used during call setup which may not match the previously-authenticated ID. Nascent functionality is split between data-plane gateways and call control session functions. By leveraging existing communication interfaces between the two and authentication data already available at the gateways, Nascent only requires small, standard-compatible patches to the existing 4G infrastructure. We prototype and experimentally evaluate three variants of Nascent in traditional and Network Functions Virtualization (NFV) deployments. We demonstrate that Nascent significantly reduces overhead compared to the state-of-the-art, without sacrificing effectiveness.

Network slicing provides a key functionality in emerging 5G networks, and offers flexibility in creating customized virtual networks and supporting different services on a common physical infrastructure. This capability critically relies on a MAC scheduler to deliver performance targets in terms of aggregate rates or resource shares for the various slices. A crucial challenge is to enforce such guarantees and performance isolation while allowing flexible sharing to avoid resource fragmentation and fully harness channel variations. In the present paper we propose a MAC scheduler which meets these objectives and preserves the basic structure of utility-based schedulers such as the Proportional Fair algorithm in terms of per-user scheduling metrics. Specifically, the proposed scheme involves counters tracking the aggregate rate or resource allocations for the various slices against pre-specified targets, and computes offsets to the scheduling metrics accordingly. This design provides transparency with respect to other scheduling modules, such as link adaptation and beam-forming. We analytically establish that the proposed scheme achieves optimal overall throughput utility subject to the various slicing constraints. In addition, extensive 3GPP-compliant simulation experiments are conducted to assess the impact on best-effort applications and demonstrate substantial gains in overall throughput utility over baseline approaches.

Traffic engineering (TE) and efficient network updating have been considered as separate problems in previous SDN research. Traffic engineering mostly focuses on static traffic and does not consider the rerouting overheads to support dynamic traffic. Efficient network updating assumes the new routing is provided by TE and focuses on minimizing only the rerouting overheads, and therefore, the improved new routing with bandwidth consumption similar to the new routing from TE but much lower rerouting overheads has not been explored. In this paper, we explore Multi-tree Low-overhead Multicast Rerouting (MLMR) to jointly solve both problems for SDN multicast. We prove that MLMR is NP-hard and design a new approximation algorithm, named Multicast Rerouting and Update Scheduling Algorithm (MRUSA). Equipped with the notions of deterioration indicator, motivator, and inhibitor, MRUSA provides incremental tree updating and multi-tree update scheduling to address the trade-off between the bandwidth consumption and rerouting overheads. Frequent rerouting due to tiny changes of multicast users can be effectively avoided, because rerouting time for each group can be correctly identified. Simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 35% compared with SPT and ST, and the computation time is small for massive SDN.

Undetectable wireless transmissions are fundamental to avoid eavesdroppers or censorship by authoritarian governments. To address this issue, wireless steganography “hides” covert information inside primary information by slightly modifying the transmitted waveform such that primary information will still be decodable, while covert information will be seen as noise by agnostic receivers. Since the addition of covert information inevitably decreases the SNR of the primary transmission, a key challenge in wireless steganography is to mathematically analyze and optimize the impact of the covert channel on the primary channel as a function of different channel conditions. Another core issue is to make sure that the covert channel is almost undetectable by eavesdroppers. Existing approaches are protocol-specific and thus their performance cannot be assessed and optimized in general scenarios. To address this research gap, we notice that existing wireless technologies rely on phase-keying modulations (e.g., BPSK, QPSK) that in most cases do not use the channel up to its Shannon capacity. Therefore, the residual capacity can be leveraged to implement a wireless system based on a pseudo-noise asymmetric shift keying (PN-ASK) modulation, where covert symbols are mapped by shifting the amplitude of primary symbols. This way, covert information will be undetectable, since a receiver expecting phase-modulated symbols will see their shift in amplitude as an effect of channel/path loss degradation. Through rigorous mathematical analysis, we first investigate the SER of PN-ASK as a function of the channel; then, we find the optimal PN-ASK parameters that optimize primary and covert throughput under different channel condition. We evaluate the throughput performance and undetectability of PN-ASK through extensive simulations and on an experimental testbed based on USRP N210 software-defined radios. Results indicate that PN-ASK improves the throughput by more than 8x with respect to prior art. Finally, we demonstrate through experiments that PN-ASK is able to transmit covert data on top of IEEE 802.11g frames, which are correctly decoded by an off-the-shelf laptop WiFi card without any hardware modifications.

We characterize the performance of a backscatter tag-to-tag (T2T) multi-hop network. For this, we developed a discrete component-based backscatter T2T transceiver and a communication protocol suite. The protocol composed of a novel (i) flooding-based link control tailored towards backscatter transmission, and (ii) low-power listening MAC. The MAC design is based on the new insight that backscatter reception is more energy costly than transmission. Our experiments show that multi-hopping extends the coverage of backscatter networks by enabling longer backward T2T links (tag far from the exciter sending to the tag close to the exciter). Four hops, for example, extend the communication range by a factor of two. Furthermore, we show that dead spots in multi-hop T2T networks are far less significant than those in the single-hop T2T networks.

The cryptocurrency market is a very huge market without effective supervision. It is of great importance for investors and regulators to recognize whether there are market manipulation and its manipulation patterns. This paper proposes an approach to mine the transaction networks of exchanges for answering this question. By taking the leaked transaction history of Mt. Gox Bitcoin exchange as a sample, we first divide the accounts into three categories according to its characteristic and then construct the transaction history into three graphs. Many observations and findings are obtained via analyzing the constructed graphs. To evaluate the influence of the accounts' transaction behavior on the Bitcoin exchange price, the graphs are reconstructed into series and reshaped as matrices. By using singular value decomposition (SVD) on the matrices, we identify many base networks which have a great correlation with the price fluctuation. When further analyzing the most important accounts in the base networks, plenty of market manipulation patterns are found. According to these findings, we conclude that there was serious market manipulation in Mt. Gox exchange and the cryptocurrency market must strengthen the supervision.

Today's cloud storage infrastructures typically provide two distinct types of services for hosting files: object storage like Amazon S3 and filesystem storage like Amazon EFS. The former supports simple, flat object operations with a low unit storage price, while the latter supports complex, hierarchical filesystem operations with a high unit storage price. In practice, however, a cloud storage user often desires the advantages of both-efficient filesystem operations with a low unit storage price. An intuitive approach to achieving this goal is to combine the two types of services, e.g., by hosting large files in S3 and small files together with directory structures in EFS. Unfortunately, our benchmark experiments indicate that the clients' download performance for large files becomes a severe system bottleneck. In this paper, we attempt to address the bottleneck with little overhead by carefully tweaking the usages of S3 and EFS. This attempt is enabled by two key observations. First, since S3 and EFS have the same unit network-traffic price and the data transfer between S3 and EFS is free of charge, we can employ EFS as a relay for the clients' quickly downloading large files. Second, noticing that significant similarity exists between the files hosted at the cloud and its users, in most times we can convert large-size file downloads into small-size file synchronizations (through delta encoding and data compression). Guided by the observations, we design and implement an open-source system called HyCloud. It automatically invokes the data APIs of S3 and EFS on behalf of users, and handles the data transfer among S3, EFS and the clients. Real-world evaluations demonstrate that the unit storage price of HyCloud is close to that of S3, and the filesystem operations are executed as quickly as in EFS in most times (sometimes even more quickly than in EFS).

With the advent of Network Function Virtualization (NFV), network services that traditionally run on proprietary dedicated hardware can now be realized using Virtual Network Functions (VNFs) that are hosted on general-purpose commodity hardware. This new network paradigm offers a great flexibility to Internet service providers (ISPs) for efficiently operating their networks (collecting network statistics, enforcing management policies, etc.). However, introducing NFV requires an investment to deploy VNFs at certain network nodes (called VNF-nodes), which has to account for practical constraints such as the deployment budget and the VNF-node capacity. To that end, it is important to design a joint VNF-nodes placement and capacity allocation algorithm that can maximize the total amount of network flows that are fully processed by the VNF-nodes while respecting such practical constraints. In contrast to most prior work that often neglects either the budget constraint or the capacity constraint, we explicitly consider both of them. We prove that accounting for these constraints introduces several new challenges. Specifically, we prove that the studied problem is not only NP-hard but also non-submodular. To address these challenges, we introduce a novel relaxation method such that the objective function of the relaxed placement subproblem becomes submodular. Leveraging this useful submodular property, we propose two algorithms that achieve an approximation ratio of 1/2(1 - 1/e) and 1/3(1 - 1/e) for the original non-relaxed problem, respectively. Finally, we corroborate the effectiveness of the proposed algorithms through extensive evaluations using both trace-driven simulations and simulations based on synthesized network settings.

Advances in virtualization technologies and edge computing have inspired a new paradigm for Internet-of-Things (IoT) application development. By breaking a monolithic application into loosely coupled microservices, great gain can be achieved in performance, flexibility and robustness. In this paper, we study the important problem of load balancing across IoT microservice instances. A key difficulty in this problem is the interdependencies among microservices: the load on a successor microservice instance directly depends on the load distributed from its predecessor microservice instances. We propose a graph-based model for describing the load dependencies among microservices. Based on the model, we first propose a basic formulation for load balancing, which can be solved optimally in polynomial time. The basic model neglects the quality-of-service (QoS) of the IoT application. We then propose a QoS-aware load balancing model, based on a novel abstraction that captures a realization of the application's internal logic. The QoS-aware load balancing problem is NP-hard. We propose a fully polynomial-time approximation scheme for the QoS-aware problem. We show through simulation experiments that our proposed algorithm achieves enhanced QoS compared to heuristic solutions.

Computational skewness is a significant challenge in multi-tenant data-parallel clusters that introduce dynamic heterogeneity of machine capacity in distributed data processing. Previous efforts to addressing skewness mostly focus on batch jobs based on the assumption that processing time is linearly dependent on the size of partitioned data. However, they are illsuited for iterative machine learning (ML) jobs, which (1) exhibit a non-linear relationship between the size of partitioned parameters and processing time within each iteration, and (2) show an explicit binding relationship between input data and parameters for parameter update. In this paper, we present FlexPara, a parameter partition approach that leverages the non-linear relationship and provisions adaptive tasks to match the distinct machine capacity so as to address the skewness in iterative ML jobs on data-parallel clusters. FlexPara first predicts task processing time based on a capacity model designed for iterative ML jobs without the linear assumption. It then partitions parameters to parallel tasks through proactive parameter reassignment. Such reassignment can significantly reduce network transmission cost incurred by input data movement due to the binding relationship. We implement FlexPara in Spark and evaluate it with various ML jobs. Experimental results show that compared to hash partition, FlexPara speeds up the execution by up to 54% and 43% in private and NSF Chameleon clusters, respectively.

Trusted identification is critical to secure IoT devices. However, the limited memory and computation power of low-end IoT devices prevent the direct usage of conventional identification systems. RF fingerprinting is a promising technique to identify low-end IoT devices since it only requires the RF signals that most IoT devices can produce for communication. However, most existing RF fingerprinting systems are data-dependent and/or not robust to impacts from wireless channels. To address the above problems, we propose to exploit the mathematical expression of the physical-layer process, regarded as a function T(·), for device identification. T(·) is not directly derivable, so we further propose a model to learn it and employ this function model as the device fingerprint in our system, namely TID. Our proposed function model characterizes the unique physical-layer process of a device that is independent of the transmitted data, and hence, our system TID is data-independent and thus resilient against signal replay attacks. Modeling and further separating channel effects from the function model makes TID channelrobust. We evaluate TID on thousands of random signal packets from 33 different devices in different environments and scenarios, and the overall identification accuracy is over 99%.

We consider the problem of designing dynamic network topologies that self-adjust to the (possibly changing) traffic pattern they serve. Such demand-aware networks currently receive much attention, especially in the context of datacenters, due to emerging technologies supporting the fast reconfiguration of the physical topology. We present the first fully distributed, provably efficient self-adjusting network. Our network called DiSptayNet relies on algorithms that perform decentralized and concurrent topological adjustments to account for changes in the demand. We present a rigorous formal analysis of the correctness and performance of DiSptayNet, which can be seen as an interesting generalization of analyses known from sequential self-adjusting datastructures. We also report on results from extensive trace-driven simulations.

Due to the open nature of wireless medium, wireless communications are especially vulnerable to eavesdropping attacks. This paper designs a new wireless communication system to deal with eavesdropping attacks. The proposed system can enable a legitimate receiver to get desired messages and meanwhile an eavesdropper to hear “fake” but meaningful messages, thereby confusing the eavesdropper and achieving additional concealment that further protects exchanged messages. Towards this goal, we propose techniques that can conceal exchanged messages by utilizing wireless channel characteristics between the transmitter and the receiver, as well as techniques that can attract an eavesdropper to gradually approach a trap region, where the eavesdropper can get fake messages. We also implement and evaluate the proposed system on top of Universal Software Defined Radio Peripherals (USRPs). Experimental results show that an eavesdropper at a trap location can receive fake information with a bit error rate (BER) that is close to 0, and the transmitter with multiple antennas can successfully deploy a trap area.

The non-uniform memory access (NUMA) architecture has become the dominant server architecture due to its scalable bandwidth performance. However, the NUMA architecture also introduces the complicated performance influences to the applications, because of the differentiated remote devices access latency and shared resource access contention. Secondly, quick developments of high speed networking devices make I/O resource be another important performance affecting element for I/O-intensive cloud applications on NUMA server. Thirdly, it is more critical in virtualized environment since all resources are managed uniformly and transparently to the VM, and the application behaviors in the VM are shielded from the Virtual Machine Manager (VMM). In this paper, we first give an analytic evaluation for performance influence from the various resource affinity. Motivated by the observations, we then build an accurate performance prediction model, named Resource Affinity performance Influence Estimation (RAIE). RAIE provides a novel performance prediction model with the holistic resource affinity parameters that are measured with the platform independent quantification approaches that need be executed in one-off manner. Moreover, RAIE model takes into account the actual influence of resource affinity according to the VM behaviours that can be monitored online without VM modification. Comprehensive evaluations prove that the RAIE model for a VM's performance prediction can increase the average prediction accuracy by 3.27x on a 4node NUMA server with high speed Network Interface Cards (NIC). The RAIE guided scheduling case validates that it can achieve 2.1x performance improvement for actual VMM resource management servicing a VM running the dynamic applications.

Degree-of-Freedom (DoF) based models have been widely used to study MIMO networks. To cancel interference, the number of DoFs used in the state-of-the-art DoF models is solely based on the number of interfering data streams. However, by decomposing an interference into the eigenspace, we find that signal strengths varies significantly in different directions for the same interference link. In this paper, we exploited the difference in interference signal strength in the eigenspace and differentiate strong and weak interference signals via their singular values. By introducing a concept of effective rank threshold, we propose to use DoFs only to cancel strong interference in the eigenspace based on this threshold while treating weak interference signals as noise in throughput calculation. We explore a fundamental tradeoff between network throughput and effective rank threshold. Using simulation results on MU-MIMO networks, we show that network throughput under optimal rank threshold setting is significantly higher than that under existing DoF IC models. To ensure feasibility at the PHY layer, we present an algorithm that can find Tx and Rx weights at each node that can offer our desired DoF allocation.

In mobile crowdsensing (MCS), users are repeatedly asked to make choices between a set of alternatives, i.e., whether to contribute to a task or not and which task to contribute to. The platform coordinating the MCS campaigns engineers these choices by selecting the tasks to present to each user and offering incentives to ensure user contributions and maximize the benefit from them. In this paper, we revisit the well-investigated question of how to optimize the contributions of crowds of mobile end users to MCS tasks. However, we depart from the bulk of related literature by explicitly accounting for the bounded rationality of human decision making. Bounded rationality is a consequence of cognitive and other kinds of constraints, (e.g., time pressure) and has been studied extensively in behavioral science.We model bounded rationality after two instances of lexicographic decision-making models that originate in the field of cognitive psychology: Fast-and-Frugal-Trees (FFTs) and Discrete Elimination by Aspects (DEBA). With each MCS task modeled as a vector of feature values, the decision process under both models proceeds through sequentially parsing lexicographically ordered features, resulting in choices that are satisfying, but not necessarily optimal. We study, in particular, scenarios where a single task or a pair of tasks are presented to MCS users together with reward offers that adhere to per-task budget constraints. We formulate the optimization problems that emerge for the MCS campaign organizers as instances of the Generalized Assignment Problem (GAP), an NP-hard problem for which approximate algorithms are available. Our evaluation suggests that our optimization approach exhibits significant gains when compared to heuristic rules that do not account for the lexicographic structure in human decision making.

With the advance of mobile computing, Internet of Things, and 5G networks, social sensing based edge computing (SSEC) systems have emerged as a new computation paradigm where people and their personally owned devices collect and process sensing measurements about the physical world at the edge of networks. In this paper, we focus on the task allocation problem in SSEC where rational edge devices are motivated by incentives to collectively accomplish the computation tasks in the system. Several unique challenges exist to solve this problem: (i) the edge devices often do not share the complete context information (e.g., CPU, memory usage) in the task allocation process due to privacy concerns; (ii) the edge devices are rational actors who may have competing objectives with the application; (iii) the application server and edge devices are usually owned by different entities, making the coordination in task allocation more challenging. This paper develops a novel integrated Top-Down and Bottom-Up (TDBU) task allocation framework to address these challenges. In particular, TDBU incorporates abottom-up game-theoretic model that allows the edge devices to specify their task preferences in a way that maximizes their payoffs. It also incorporates atop-down control model that ensures the performance of the applications using control theory. The TDBU was implemented on a real-world edge computing testbed that consists of heterogeneous devices (Jetson TX1, TK1 boards, Raspberry Pi3). We compared the performance of TDBU with state-of-the-art baselines through a real-world social sensing application. The results showed that our solution significantly outperformed the baselines in various application settings.

As the proliferation of mobile devices has led to an ever-growing demand for wireless Internet services, the spectrum shortage issue becomes increasingly severe and spectrum sharing is regarded as a promising approach to addressing the spectrum shortage issue. In this paper, we propose a practical underlay spectrum sharing scheme for cognitive radio networks (CRNs) where the primary users are oblivious to the secondary users. The key components of our scheme are two MIMO-based interference cancellation (IC) techniques to handle cross-network interference on the secondary network side. The first one is a blind beamforming technique for secondary transmitters. This IC technique allows a secondary transmitter to nullify its generated interference for primary users without requiring channel state information (CSI). The second one is a blind interference cancellation (BIC) technique for secondary receivers. This IC technique enables a secondary receiver to decode its desired signal in the presence of strong unknown interference from primary transmitters. Based on these two MIMO-based IC techniques, we develop a MAC protocol for the secondary network to enable underlay spectrum sharing in CRNs. We have implemented the proposed underlay spectrum sharing scheme on a GNURadio-USRP2 wireless testbed. Experimental results show that the secondary users can achieve an average of 1 bit/s/Hz spectrum efficiency without degrading the performance of the primary users in a real-world office building environment.