INFOCOM 2018 论文列表

While the Internet of Things (IoT) is embraced as important tools for efficiency and productivity, it is becoming an increasingly attractive target for cybercriminals. This work represents the first endeavor to develop practical Puncturable Attribute Based Encryption schemes that are light-weight and applicable in IoTs. In the proposed scheme, the attribute-based encryption is adopted for fine grained access control. The secret keys are puncturable to revoke the decryption capability for selected messages, recipients, or time periods, thus protecting selected important messages even if the current key is compromised. In contrast to conventional forward encryption, a distinguishing merit of the proposed approach is that the recipients can update their keys by themselves without key re-issuing from the key distributor. It does not require frequent communications between IoT devices and the key distribution center, neither does it need deleting components to expunge existing keys to produce a new key. Moreover, we devise a novel approach which efficiently integrates attribute-based key and punctured keys such that the key size is roughly the same as that of the original attribute-based encryption. We prove the correctness of the proposed scheme and its security under the Decisional Bilinear Diffie-Hellman (DBDH) assumption. We also implement the proposed scheme on Raspberry Pi and observe that the computation efficiency of the proposed approach is comparable to the original attribute-based encryption. Both encryption and decryption can be completed within tens of milliseconds.

The combination of Network Function Virtualization (NFV) and Software Defined Networking (SDN) possesses a great potential in accommodating dynamic network control via cloning/migration of virtualized NFs and steering of traffic flows. A great challenge is the lack of the proprietary internal NF state information to the control system (including SDN controller and NFV orchestrator), which may lead to incorrect packet/flow processing at the newly created NF instances. In this work, we design a light-weight approach which can function either independently or as a plug-in to the network control system to reveal the internal NF states. Unlike the previous work, we propose to learn the internal NF states through normal network functions instead of designing extra APIs for certain NFs. Moreover, we propose a feasible way to detect state violations and even correct them automatically. Our approach is tested by experiments, and the results confirm its efficiency and practicability.

With the evolution of Network Function Virtual-izaiton (NFV), enterprises are increasingly outsourcing their network functions to the cloud. However, using virtualized network functions (VNFs) to provide flexible services in today's cloud is challenging due to the inherent difficulty in intelligently scaling VNFs to cope with traffic fluctuations. To best utilize cloud resources, NFV providers need to dynamically scale the VNF deployments and reroute traffic demands for their customers. Since most existing work is reactive in nature, we seek a proactive approach to provision new instances for overloaded VNFs ahead of time based on the estimated flow rates. We formulate the VNF provisioning problem in order that the cost incurred by inaccurate prediction and VNF deployment is minimized. In the proposed online algorithm, we first employ an efficient online learning method which aims at minimizing the error in predicting the service chain demands. We then derive the requested instances with adaptive processing capacities and call two other algorithms for new instance assignment and service chain rerouting, respectively, while achieving good competitive ratios. The joint online algorithm is proven to provide good performance guarantees by both theoretical analysis and trace-driven simulation.

We consider the problem of predicting link formation in Social Learning Networks (SLN), a type of social network that forms when people learn from one another through structured interactions. While link prediction has been studied for general types of social networks, the evolution of SLNs over their lifetimes coupled with their dependence on which topics are being discussed presents new challenges for this type of network. To address these challenges, we develop a time-series prediction methodology that uses a recurrent neural network architecture to pass network state between time periods, and that models over three types of SLN features updated in each period: neighborhood-based (e.g., resource allocation), path-based (e.g., shortest path), and post-based (e.g., topic similarity). Through evaluation on four real-world datasets from Massive Open Online Course (MOOC) discussion forums, we find that our method obtains substantial improvements over a Bayesian model and an unsupervised baseline, with AUCs typically above 0.75 and reaching 0.97 depending on the dataset. Our feature importance analysis shows that while neighborhood-based features contribute the most to the results, post-based and path-based features add additional information that significantly improve the predictions. We also find that several input features have opposite directions of correlation between link formation and post quality, suggesting that response time and quality are two competing objectives to be accounted for in SLN link recommendation systems.

We present the design and implementation of PAFD, a design methodology that enables full-duplex (FD) in hybrid beamforming systems with constant amplitude phased array antennas. The key novelty in PAFD's design is construction of analog beamformers that maximize the beamforming gains in the desired directions while simultaneously reducing the self-interference (SI). PAFD is implemented on the WARP platform, and its performance is extensively evaluated in both indoor and outdoor environments. Our experimental results reveal that (i) PAFD sacrifices a few dB in beamfomring gain to provide large amounts of reduction in SI power; (ii) the reduction in SI is dependent on the number of phased array antennas and increases as the number of antennas increases; and (iii) finally, PAFD significantly outperforms half-duplex (HD) for small cells even in presence of high interference caused by uplink clients to the downlink clients. The gains increase with a larger array size or less multipath in the propagation environment.

As more applications and businesses move to the cloud, pricing for inter-datacenter links has become an important problem. In this paper, we study revenue maximizing pricing from the perspective of a network provider in inter-datacenter networks. Designing a practical bandwidth pricing scheme requires us to jointly consider the requirements of envy-freeness and arbitrage-freeness, where envy-freeness guarantees the fairness of resource allocation and arbitrage-freeness induces users to truthfully reveal their data transfer requests. Considering the non-convexity of the revenue maximization problem and the lack of information about the users' utilities, we propose a framework for computationally efficient pricing to approximately maximize revenue in a range of environments. We first study the case of a single link accessed by many users, and design a (1 + E)-approximation pricing scheme with polynomial time complexity and information complexity. Based on dynamic programming, we then extend the pricing scheme for the tollbooth network, preserving the (1 + E) approximation ratio and the computational complexity. For the general network setting, we analyze the revenue generated by uniform pricing, which determines a single per unit price for all potential users. We show that when users have similar utilities, uniform pricing can achieve a good approximation ratio, which is independent of network topology and data transfer requests. The pricing framework can be extended to multiple time slots, enabling time-dependent pricing.

The uncertainty and variability of renewable generation pose significant challenges to reliable power-grid operations. This paper designs robust online strategies for jointly operating energy storage units and fossil-fuel generators to achieve provably reliable grid operations at all times under high renewable uncertainty, without the need of renewable curtailment. In particular, we jointly consider two power system operations, namely day-ahead reliability assessment commitment (RAC) and real-time dispatch. We first extend the concept of “safe-dispatch sets” to our setting. While finding such safe-dispatch sets and checking their non-emptiness provide crucial answers to both RAC and real-time dispatch, their computation incurs high complexity in general. To develop computationally-efficient solutions, we first study a single-bus case with one generator-storage pair, where we derive necessary conditions and sufficient conditions for the safe-dispatch sets. Our results reveal fundamental trade-offs between storage capacity and generator ramp-up/-down limits to ensure grid reliability. Then, for the more general multi-bus scenario, we split the net-demand among virtual generator-storage pairs (VGSPs) and apply our single-bus decision strategy to each VGSP. Simulation results on an IEEE 30-bus system show that, compared with state-of-art solutions, our scheme requires significantly less storage to ensure reliable grid operation without any renewable curtailment.

The Transmission Control Protocol (TCP) utilizes congestion avoidance and control mechanisms as a preventive measure against congestive collapse and as an adaptive measure in the presence of changing network conditions. The set of available congestion control algorithms is diverse, and while many have been studied from empirical and simulation perspectives, there is a notable lack of analytical work for some variants. To gain more insight into the dynamics of these algorithms, we: (1) propose a general modeling scheme consisting of a set of functional differential equations of retarded type (RFDEs) and of the congestion window as a function of time; (2) apply this scheme to TCP Reno and demonstrate its equivalence to a previous, well known model for TCP Reno; (3) show an application of the new framework to the widely-deployed congestion control algorithm TCP CUBIC, for which analytical models are few and limited; and (4) validate the model using simulations. Our modeling framework yields a fluid model for TCP CUBIC. From a theoretical analysis of this model, we discover that TCP CUBIC is locally uniformly asymptotically stable-a property of the algorithm previously unknown.

Deep learning shows great promise in providing more intelligence to augmented reality (AR) devices, but few AR apps use deep learning due to lack of infrastructure support. Deep learning algorithms are computationally intensive, and front-end devices cannot deliver sufficient compute power for real-time processing. In this work, we design a framework that ties together front-end devices with more powerful backend “helpers” (e.g., home servers) to allow deep learning to be executed locally or remotely in the cloud/edge. We consider the complex interaction between model accuracy, video quality, battery constraints, network data usage, and network conditions to determine an optimal offloading strategy. Our contributions are: (1) extensive measurements to understand the tradeoffs between video quality, network conditions, battery consumption, processing delay, and model accuracy; (2) a measurement-driven mathematical framework that efficiently solves the resulting combinatorial optimization problem; (3) an Android application that performs real-time object detection for AR applications, with experimental results that demonstrate the superiority of our approach.

Previous research on SDN traffic engineering mostly focuses on static traffic, whereas dynamic traffic, though more practical, has drawn much less attention. Especially, online SDN multicast that supports IETF dynamic group membership (i.e., any user can join or leave at any time) has not been explored. Different from traditional shortest-path trees (SPT) and graph theoretical Steiner trees (ST), which concentrate on routing one tree at any instant, online SDN multicast traffic engineering is more challenging because it needs to support dynamic group membership and optimize a sequence of correlated trees without the knowledge of future join and leave, whereas the scalability of SDN due to limited TCAM is also crucial. In this paper, therefore, we formulate a new optimization problem, named Online Branch-aware Steiner Tree (OBST), to jointly consider the bandwidth consumption, SDN multicast scalability, and rerouting overhead. We prove that OBST is NP-hard and does not have a |Dmax|1-ε-competitive algorithm for any , where |Dmax| is the largest group size at any time. We design a |Dmax|-competitive algorithm equipped with the notion of the budget, the deposit, and Reference Tree to achieve the tightest bound. The simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 25% compared with SPT and ST, and the computation time is small for massive SDN.

Acoustic motion tracking has been viewed as a promising user interaction technique in many scenarios such as Virtual Reality (VR), Smart Appliance, video gaming, etc. Existing acoustic motion tracking approaches, however, suffer from long window of accumulated signal and time-consuming signal processing. Consequently, they are inherently difficult to achieve both high accuracy and low delay. We propose Vernier, an efficient and accurate acoustic tracking method on commodity mobile devices. In the heart of Vernier lies a novel method to efficiently and accurately derive phase change and thus moving distance. Vernier significantly reduces the tracking delay/overhead by removing the complicated frequency analysis and long window of signal accumulation, while keeping a high tracking accuracy. We implement Vernier on Android, and evaluate its performance on COTS mobile devices including Samsung Galaxy S7 and Sony L50t. Evaluation results show that Vernier outperforms previous approaches with a tracking error less than 4 mm. The tracking speed achieves 3×improvement to existing phase based approaches and 10×to Doppler Effect based approaches. Vernier is also validated in applications like controlling and drawing, and we believe it is generally applicable in many real applications.

Stochastic models have been dominant in network optimization theory for over two decades, due to their analytical tractability. However, these models fail to capture non-stationary or even adversarial network dynamics which are of increasing importance for modeling the behavior of networks under malicious attacks or characterizing short-term transient behavior. In this paper, we consider the network utility maximization problem in adversarial network settings. In particular, we focus on the tradeoffs between total queue length and utility regret which measures the difference in network utility between a causal policy and an “oracle” that knows the future within a finite time horizon. Two adversarial network models are developed to characterize the adversary's behavior. We provide lower bounds on the tradeoff between utility regret and queue length under these adversarial models, and analyze the performance of two control policies (i.e., the Drift-plus-Penalty algorithm and the Tracking Algorithm).

Cellular network positioning is a mandatory requirement for localizing emergency callers, such as E911 in North America. Although smartphones are normally with GPS modules, there are still a large number of users with cell phones only as basic devices, and GPS could be ineffective in urban canyon environments. To this end, the fingerprinting positioning mechanism is incorporated into LTE architecture by 3GPP, where the major challenge is to collect geo-tagged wireless fingerprints in vast areas. This paper proposes to utilize the subspace identification approach for large-scale wireless fingerprints prediction. We formulate the problem into the problem of finding the optimal subspace over Stiefel manifold, and redesign the Stiefel-manifold optimization method with fast convergence rate. Moreover, we propose a sliding window mechanism for the practical large-scale fingerprints prediction scenario, where fingerprints are unevenly distributed in the vast area. Combining the two proposed mechanisms enables an efficient method of large-scale fingerprints prediction in the city level. Further, we validate our theoretical analysis and proposed mechanisms by conducting experiments with real mobile data, which shows that the resulted localization accuracy and reliability with our predicted fingerprints exceed the requirement of E911.

Future Internet Architectures must support the rapid growth of traffic generated by mobile endpoints in a manner that is scalable and ensures low latency. We present a quantitative evaluation of three distinct approaches towards handling endpoint mobility: name-based forwarding, indirection and a global name service (GNS). Using a range of parameterized mobility distributions and real ISP topologies, we describe representative instantiations of each approach and evaluate their performance using four key metrics: update cost and update propagation cost in the control plane; and forwarding traffic cost and time-to-connect (TTC) in the data plane. (1) We show that by leveraging the fact that realistic endpoint mobility distributions show a high probability of being at a small subset of visited locations, name-based forwarding strategies can provide up to 60% improvement in control costs over simple best-port forwarding. (2) We show that the TTC in these name-based forwarding strategies is comparable to the TTC in the GNS. (3) Finally we show that a GNS-based approach offers the most suitable balance of total (combined data and control) cost to TTC across all approaches, all endpoint mobility distributions, and all ISP topologies considered.

With the rapid development of web applications in datacenters, network latency becomes more important to user experience. The network latency will be greatly increased by incast congestion, in which a huge number of requests arrive at the front-end server simultaneously. Previous incast problem solutions usually handle the data transmission between the data servers and the front-end server directly, and they are not sufficiently effective in proactively avoiding incast congestion. To further improve the effectiveness, in this paper, we propose a Proactive Incast Congestion Control system (PICC). Since each connection has bandwidth limit, PICC novelly limits the number of data servers concurrently connected to the front-end server to avoid the incast congestion through data placement. Specifically, the front-end server gathers popular data objects (i.e., frequently requested data objects) into as few data servers as possible, but without overloading them. It also re-allocates the data objects that are likely to be concurrently or sequentially requested into the same server. As a result, PICC reduces the number of data servers concurrently connected to the front-end server (which avoids the incast congestion), and also the number of connection establishments (which reduces the network latency). Since the selected data servers tend to have long queues to send out data, to reduce the queuing latency, PICC incorporates a queuing delay reduction algorithm that assigns higher transmission priorities to data objects with smaller sizes and longer queuing times. The experimental results on simulation and a real cluster based on a benchmark show the superior performance of PICC over previous incast congestion problem solutions.

Communication over an interference channel, which is fundamental and pervasive in the wireless and wireline environment, is often intended to carry information among different transmitter-receiver pairs. For applications that require time critical updates, it is desirable to maintain the freshness of the received information, which is quantified by the age metric (unlike the familiar delay metric). In this paper, we consider the case of two transmitter-receiver pairs, and address the impact of interference on information freshness by formulating a two-player “interference” game, in which each player is a transmitter desiring to maintain the freshness of the information updates it sends to its receiver. The strategy of a player is the choice of power level at which it will transmit. We then derive both Nash and Stackelberg strategies for the game. Our analysis shows that the Stackelberg strategy uses less power than the Nash strategy, and that it dominates the Nash strategy (i.e., the Stackelberg total cost function is lower than the Nash total cost function). Our obtained Nash and Stackelberg strategies are desirable user operating points in competitive situations.

This study was carried in the context of the development of technologies for a cloud that uses an optical network for internal communication. The problem addressed in this paper deals with dispatching jobs - units of work, to be performed by machines on the cloud. Sending (or migrating) a job to a machine involves establishing a lightpath (a la circuit switching); this incurs a significant setup cost, but while it exists, the lightpath's capacity is very high. Hence, moving one job is about as expensive as moving a set of jobs over the same lightpath. Our goal is to develop online network dispatching algorithms for a work conserving job scheduling. That is, consider a set of jobs the dispatcher is responsible for their executions on some set SM of machines. Any machine in the network may join or (when not executing a job) leave SM according to decisions made outside the scope of this paper. Whenever a machine joins the set or is in the set and has just finished executing a job, it issues a request for a new job to perform and the dispatcher must send this machine a job that has not been executed yet (if such exists). Every machine can perform any of the jobs, and each job is performed on a single machine. The main algorithmic challenge in this context boils down to the following questions: How many jobs should we send to a requesting machine (or to some intermediate storage to be distributed from there)? From the storage on which machine should these jobs be taken? The algorithms developed here are shown to be efficient in reducing the costs of establishing lightpaths. As opposed to related algorithms for delivering consumable resources (in other contexts), we prove that our online algorithms are fully competitive. We present randomized online algorithms for two different settings: in the first it is assumed that each message requires establishing a lightpath and thus, incurs a setup cost; in the second, we distinguish between messages that carry job sets and small control messages sent by the algorithm, where the latter type of messages is assumed to be sent over a designated (non-optical) control plane at a negligible cost. Our algorithms are quite simple, though the analysis turns out to be rather involved. They are designed (and rigorously analyzed) for a general architecture, but would be especially efficient in fat tree architectures - the common choice in many data centers.

We consider models of content delivery networks in which the servers are constrained by two main resources: memory and bandwidth. In such systems, the throughput crucially depends on how contents are replicated across servers and how the requests of specific contents are matched to servers storing those contents. In this paper, we first formulate the problem of computing the optimal replication policy which if combined with the optimal matching policy maximizes the throughput of the caching system in the stationary regime. It is shown that computing the optimal replication policy for a given system is an NP-hard problem. A greedy replication scheme is proposed and it is shown that the scheme provides a constant factor approximation guarantee. We then propose a simple randomized matching scheme which avoids the problem of interruption in service of the ongoing requests due to re-assignment or repacking of the existing requests in the optimal matching policy. The dynamics of the caching system is analyzed under the combination of proposed replication and matching schemes. We study a limiting regime, where the number of servers and the arrival rates of the contents are scaled proportionally, and show that the proposed policies achieve asymptotic optimality. Extensive simulation results are presented to evaluate the performance of different policies and study the behavior of the caching system under different service time distributions of the requests.

Containers, a form of lightweight virtualization, provide an alternative means to partition hardware resources among users and expedite application deployment. Compared to virtual machines (VMs), containers incur less overhead and allow a much higher consolidation ratio. Container networking, a vital component in container-based virtualization, is still not well understood. Many techniques have been developed to provide connectivity between containers on a single host or across multiple machines. However, there lacks an in-depth analysis of their respective advantages, limitations, and performance in a cloud environment. In this paper, we perform a comprehensive study of representative container networks. We first conduct a qualitative comparison of their applicable scenarios, levels of security isolation, and overhead. Then we quantitatively evaluate the throughput, latency, scalability, and startup cost of various container networks in a realistic cloud environment. We find that virtualized network in containers incurs non-negligible overhead compared to physical networks. Performance degradation varies depending on the type of network protocol and packet size. Our experiments show that there is no clear winner in performance and users need to select an appropriate container network based on the requirements and characteristics of their workloads.