INFOCOM 2018 论文列表

The millimeter-wave (mmWave) frequency band has been utilized in the IEEE 802.11ad standard to achieve multi-Gbps throughput. Despite the advantages, mmWave links are highly vulnerable to both user and environmental mobility. Since mmWave radios use highly directional antennas, the line-of-sight (LOS) signal can be easily blocked by various obstacles, such as walls, furniture, and humans. In the complicated indoor environment, it is highly possible that the blocked mmWave link cannot be restored no matter how the access point and the mobile user change their antenna directions. To address the problem and enable indoor mobile mmWave networks, in this paper, we introduce the reconfigurable 60 GHz reflect-arrays to establish robust mmWave connections for indoor networks even when the links are blocked by obstructions. First, the reconfigurable 60 GHz reflect-array is designed, implemented, and modeled. Then a three-party beam-searching protocol is designed for reflect-array-assisted 802.11ad networks. Finally, an optimal array deployment strategy is developed to minimize the link outage probability in indoor mobile mmWave networks. The proposed solution is validated and evaluated by both in-lab experiments and computer simulations.

Today's cloud networks are shared among many tenants. Bandwidth guarantees and work conservation are two key properties to ensure predictable performance for tenant applications and high network utilization for providers. Despite significant efforts, very little prior work can really achieve both properties simultaneously even some of them claimed so. In this paper, we present QShare, a comprehensive in-network solution to achieve bandwidth guarantees and work conservation simultaneously. QShare leverages weighted fair queuing on commodity switches to slice network bandwidth for tenants, and solves the challenge of queue scarcity through balanced tenant placement and dynamic tenant-queue binding. We have implemented a QShare prototype and evaluated it extensively via both testbed experiments and simulations. Our results show that QShare ensures bandwidth guarantees while driving network utilization to over 91% even under unpredictable traffic demands.

Nowadays large-scale distributed machine learning systems have been deployed to support various analytics and intelligence services in IT firms. To train a large dataset and derive the prediction/inference model, e.g., a deep neural network, multiple workers are run in parallel to train partitions of the input dataset, and update shared model parameters. In a shared cluster handling multiple training jobs, a fundamental issue is how to efficiently schedule jobs and set the number of concurrent workers to run for each job, such that server resources are maximally utilized and model training can be completed in time. Targeting a distributed machine learning system using the parameter server framework, w e design an online algorithm for scheduling the arriving jobs and deciding the adjusted numbers of concurrent workers and parameter servers for each job over its course, to maximize overall utility of all jobs, contingent on their completion times. Our online algorithm design utilizes a primal-dual framework coupled with efficient dual subroutines, achieving good long-term performance guarantees with polynomial time complexity. Practical effectiveness of the online algorithm is evaluated using trace-driven simulation and testbed experiments, which demonstrate its outperformance as compared to commonly adopted scheduling algorithms in today's cloud systems.

Communication networks are an essential infrastructure and must be designed carefully to ensure high reliability. Identifying a fully reliable design is, however, computationally very tough since it requires that a reliability evaluation, which is known to be #P-complete, be repeated an exponential number of times. Existing studies, therefore, attempt to avoid exact optimization to reduce the computational burden by applying heuristics. Due to the importance of communication networks and to better assess the accuracy of heuristic approaches, exact optimization remains a key goal. This paper proposes an exact method for two network design problems: reliability maximization under budget constraints and cost minimization with assurance of reliability. Our method employs a common idea to solve these problems, i.e., a best-first search algorithm that runs on decision diagrams. Our method employs just a single binary decision diagram (BDD) to compute the reliability for any solution and is also used as the basis of a novel heuristic function, called the cost-aware BDD heuristic function, as a search guide. Numerical experiments show that our method scales well; it successfully optimizes a network with 189 links. In addition, our method reveals the poor performance of existing heuristic approaches; a well-known existing heuristic method is shown to yield a solution that offers less than half the optimal reliability.

This paper considers energy management on LTE-enabled Internet of Things (IoT) devices. A characteristic feature of IoT applications is the periodic generation of small messages, whose transmission over LTE is highly energy inefficient. In this paper, we consider application message bundling to alleviate the effect of short message transmissions on energy consumption. Specifically, we model the interplay between energy consumption and the extended DRX mechanism introduced in LTE to deal with IoT traffic. We formulate bundling as a cost minimization problem and develop an online algorithm to solve the problem. Detailed analysis shows that, depending on DRX and application parameters, our algorithm is 1, 2, or 4-competitive with respect to the optimal offline algorithm that knows the entire sequence of application messages a priori. We evaluate the performance of the proposed algorithm and the accuracy of our analysis in a range of realistic scenarios using both model-driven simulations and real experiments on an IoT testbed. Our results show that, i) depending on application requirements, energy savings ranging from zero to about 100% can be achieved using our algorithm, and ii) ignoring DRX could significantly overestimate or underestimate energy consumption.

The use of a combinatorial auction is believed to be an effective way to distribute spectrum to buyers who have diversified valuations for different spectrum combinations. However, the allocation of spectrum with combinatorial auctions mainly aims at optimizing over certain utility functions, e.g., social welfare, but ignores individual preferences of buyers and sellers, who have incentives to deviate from globally optimal allocation results to improve their own utility. In this paper, we explore the possibility of designing a new stable matching algorithm for combinatorial spectrum allocations. Starkly different from existing efforts on spectrum matching mechanism design, our proposed combinatorial spectrum matching framework not only allows buyers to express preferences towards spectrum combinations (rather than individual channels), but also computes the payment that should be transferred from buyers to sellers. Payment determination, while essential in spectrum exchange, has never been addressed in existing spectrum matching frameworks. We design a novel algorithm to achieve a stable combinatorial spectrum matching and to compute the corresponding payment profiles. We conducted an extensive array of experiments to compare the performance of stable combinatorial spectrum matching with spectrum auctions. It is shown that the combinatorial spectrum matching sacrifices little allocation efficiency in terms of social welfare and spectrum utilization, but achieves a much higher individual buyer utility, which will incentivize buyers to participate and comply with the allocation results.

An increasing number of depth sensors and surrounding-aware cameras are being installed in the new generation of cars. For example, Tesla Motors uses a forward radar, a front-facing camera, and multiple ultrasonic sensors to enable its Autopilot feature. Meanwhile, older or legacy cars are expected to be around in volumes, for at least the next 10 to 15 years. Legacy car drivers rely on traditional GPS for navigation services, whose accuracy varies 5 to 10 meters in a clear line-of-sight and degrades up to 30 meters in a downtown environment. At the same time, a sensor-rich car achieves better accuracy due to high-end sensing capabilities. To bridge this gap, we propose CoDrive, a system to provide a sensor-rich car's accuracy to a legacy car. We achieve this by correcting GPS errors of a legacy car on an opportunistic encounter with a sensor-rich car. CoDrive uses smartphone GPS of all participating cars, RGB-D sensors of sensor-rich cars, and road boundaries of a traffic scene to generate optimization constraints. Our algorithm collectively reduces GPS errors, resulting in accurate reconstruction of a traffic scene's aerial view. CoDrive does not require stationary landmarks or 3D maps. We empirically evaluate CoDrive which is shown to achieve a 90% and a 30% reduction in cumulative GPS error for legacy and sensor-rich cars respectively, while preserving the shape of the traffic.

As the Ultra High Frequency (UHF) passive Radio Frequency IDentification (RFID) technology becomes increasingly deployed, it faces an array of new security attacks. In this paper, we consider a type of attack in which a malicious RFID reader could arbitrarily modify the tags via standard commands, e.g., IDs or other data in the memory. To deal with this type of attack, we propose a physical-layer RF signal based reader authentication solution, namely Arbitrator, that involves passively listening on RF channels, analyzing the communication signals, identifying unauthorized readers and jamming the commands from such readers. Our solution does not need to modify RFID devices or the underlying communication standards, hence fully compatible with the existing RFID infrastructure. In this study, we have implemented a prototype Arbitrator over the Universal Software Radio Peripheral (USRP) platform, and conducted extensive experiments to evaluate its performance. Our results show that Arbitrator can detect unauthorized RFID readers with high accuracy, and thus effectively diminish the unauthorized access attacks.

SDN programming has been challenging because programmers have to not only implement the control logic, but also handle low-level details such as the generation of flow tables and the communication between the controller and switches. New generation of SDN with protocol oblivious forwarding and multi-table pipelining introduces even more low-level details to consider. We propose POMP, the first SDN programming environment supporting both protocol oblivious forwarding and automatic multi-table pipelining. POMP applies the static taint analysis technique to automatically infer compact and efficient multi-table pipelines from a data-plane agnostic network policy written by the programmer. The runtime system tracks the execution of the network policy, and automatically generates table entries. POMP also introduces a novel notion of dependent labels in the taint analysis, which, combined with the runtime information of the network policy, can further reduce the number of table entries. Like P4, POMP supports protocol-oblivious programming by providing a network protocol specification language. Parsers of packets can be automatically generated based on the protocol specification. POMP supports two main emerging SDN platforms, POF and P4, therefore network policies written in POMP are portable over any switches supporting POF or P4.

Many networking devices, such as firewalls and routing tables, rely upon packet classifiers to define their behavior for various kinds of network traffic. Since these devices have real-time constraints, it is important for packet classification to be as fast as possible. We present a new method, ByteCuts, which includes two major improvements over existing tree-based packet classifiers. First, it introduces a new cutting method that is more efficient than existing methods. Second, ByteCuts intelligently partitions the rule list into multiple trees in a way that supports the cutting method and reduces rule replication. We compare ByteCuts to several existing methods such as HyperCuts, HyperSplit, and SmartSplit. We find that ByteCuts outperforms SmartSplit, the previous fastest classifier, in every metric; specifically, ByteCuts is able to classify packets 58% faster, can be constructed in seconds rather than minutes, and uses orders of magnitude less memory.

In this work, we investigate the problem of joint optimization over placement and routing of network function chains in data centers. In the offline case, we demonstrate that a classical randomization algorithm works well and we derive a new bound on the performance sub-optimality gap. In the online case, we prove a fundamental lower bound in resource violation and propose a new algorithm that combines techniques from multiplicative weight update and primal-dual update paradigms. This online algorithm asymptotically achieves the best possible performance in terms of resource allocation among all online algorithms. We demonstrate the applicability of our solutions to address practical problems by conducting simulation-based evaluations over different data center architectures using data generated from real trace distribution.

In recent years, the rapid growth of mobile data demands has introduced many stringent requirements on latency and convergence performance in wireless network optimization. To address these challenges, several momentum-based algorithms have been proposed to improve the classical queue-length-based algorithmic framework (QLA). By combining queue-length updates and one-slot weight changes (known as the first-order momentum), it has been shown that these algorithms dramatically improve delay and convergence compared to QLA, while maintaining the same throughput-optimality and low-complexity. These exciting attempts have sparked a lot of conjectures about whether it is useful to further exploit high-order momentum information to improve delay and convergence speed. In this paper, we show that the answer is yes. Specifically, we first propose a new weight updating scheme that enables the incorporation of high-order momentum. We then prove the throughput-optimality and queue-stability of the proposed high-order momentum-based approach and characterize its delay and convergence performances. Through these analytical results, we finally show that delay and convergence would continue to improve as more high-order momentum information is utilized.

Existing random access protocols designed for satellite networks have poor performance in short burst communications because of the difficulty on global time synchronization and frequent collisions. In this paper, we propose a Lightweight Retransmission (LwR) mechanism for random access in satellite networks to reduce collisions and get rid of synchronization requirement. In our LwR, only partial bits in a packet are retransmitted. Firstly, we formulate the lightweight retransmission problem and prove that it is NP-hard. Next, we focus on the construction of partial replicas, which is the core of our LwR, and propose regular and random construction methods. Especially, we prove the sufficient conditions for successfully decoding two conflicted packets by ZigZag. Finally, we propose an algebraic model and derive the upper and lower bounds of successfully decoding probability under different construction methods. Both theoretical analysis and experimental results reveal that the random construction method achieves higher decoding probability than the regular construction method. Simulation results also demonstrate that our LwR significantly outperforms related schemes designed for satellite networks.

This paper concerns the problem of finding persistent items in distributed datasets, which has many applications such as port scanning and intrusion detection. To the best of our knowledge, there is no existing solution for finding persistent items in distributed datasets. In this paper, we propose DISPERSE, a probabilistic algorithm that can find persistent items in distributed datasets without collecting all the datasets. Our basic idea is that each monitor compresses each item ID in its dataset in a lossy fashion, sends the set of lossily compressed item IDs to the server, then the server recovers the IDs of the persistent items. We design the lossy compression so that given one lossily compressed item ID, the server cannot recover the item ID, but when the number of lossily compressed versions of the same item ID exceeds a threshold, which means that such items are persistent ones, the server can recover the item ID with a high probability. This threshold is exactly the threshold in the definition of persistent items. We implemented DISPERSE and evaluated its performance. In comparison with the straightforward solution, DISPERSE achieves a compression ratio of 26.5% with FNR=3.5% and FPR=O. In comparison with a developed Bloom filter based scheme and the adapted kBF and IBF schemes, our scheme can achieve 7.9, 5.7, and 6.6 times performance gains, respectively, in terms of compression ratio.

Recently, intelligent sports analytics is becoming a hot area in both industry and academia for coaching, practicing tactic and technical analysis. With the growing trend of bringing sports analytics to live broadcasting, sports robots and common playfield, a low cost system that is easy to deploy and performs real-time and accurate sports analytics is very desirable. However, existing systems, such as Hawk-Eye, cannot satisfy these requirements due to various factors. In this paper, we present MV-Sports, a cost-effective system for real-time sports analysis based on motion and vision sensor integration. Taking tennis as a case study, we aim to recognize player shot types and measure ball states. For fine-grained player action recognition, we leverage motion signal for fast action highlighting and propose a long short term memory (LSTM)-based framework to integrate MV data for training and classification. For ball state measurement, we compute the initial ball state via motion sensing and devise an extended kalman filter (EKF)-based approach to combine ball motion physics-based tracking and vision positioning-based tracking to get more accurate ball state. We implement MV-Sports on commercial off-the-shelf (COTS) devices and conduct real-world experiments to evaluate the performance of our system. The results show our approach can achieve accurate player action recognition and ball state measurement with sub-second latency.

Driven by mission-critical applications in modern industrial systems, the 5th generation (5G) communication system is expected to provide ultra-reliable low-latency communications (URLLC) services to meet the quality of service (QoS) demands of industrial applications. However, these stringent requirements cannot be guaranteed by its conventional dynamic access scheme due to the complex signaling procedure. A promising solution to reduce the access delay is the pre-allocation scheme based on the semi-persistent scheduling (SPS) technique, which however may lead to low spectrum utilization if the allocated resource blocks (RBs) are not used. In this paper, we aim to address this issue by developing DPre, a predictive pre-allocation framework for uplink access scheduling of delay-sensitive applications in industrial process automation. The basic idea of DPre is to explore and exploit the correlation of data acquisition and access behavior between nodes through static and dynamic learning mechanisms in order to make judicious resource per-allocation decisions. We evaluate the effectiveness of DPre based on several monitoring applications in a steel rolling production process. Simulation results demonstrate that DPre achieves better performance in terms of the prediction accuracy, which can effectively increase the rewards of those reserved resources.

Crowdsensing paradigm facilitates a wide range of data collection, where great efforts have been made to address its fundamental issue of matching workers to their assigned tasks. In this paper, we reexamine this issue by considering the spatiotemporal worker mobility and task arrivals, which more fits the actual situation. Specifically, we study the location-aware and location diversity based dynamic crowdsensing system, where workers move over time and tasks arrive stochastically. We first exploit offline crowdsensing by proposing a combinatorial algorithm, for efficiently distributing tasks to workers. After that, we mainly study the online crowdsensing, and further consider an indispensable aspect of worker's fair allocation. Apart from the stochastic characteristics and discontinuous coverage, the nonlinear expectation is incurred as a new challenge concerning fairness issue. Based on Lyapunov optimization with perturbation parameters, we propose online control policy to overcome those challenges. Hereby we can maintain system stability and achieve a time average sensing utility arbitrarily close to the optimum. Performance evaluation on real data set validates the proposed algorithm, where 116% gain of fairness is achieved at the expense of 12% loss of sensing value on average.

We study the scheduling decision for an application consisting of dependent tasks, in a generic cloud computing system comprising a network of heterogeneous local processors and a remote cloud server. We formulate an optimization problem to find the offloading decision that minimizes the overall application execution cost, subject to an application completion deadline. Since this problem is NP-hard, we propose a heuristic algorithm termed Individual Time Allocation with Greedy Scheduling (ITAGS) to obtain an efficient solution. ITAGS first uses a binary-relaxed version of the original problem to allocate a completion deadline to each individual task, and then greedily optimizes the scheduling of each task subject to its time allowance. Through trace-based simulation using real applications, as well as various randomly generated task trees, we study the performance of ITAGS, highlighting the effect of the application deadline, communication delay, number of processors, and number of tasks. We further demonstrate the substantial performance advantage of ITAGS over existing alternatives.

Fog architectures at the network edge are becoming a popular research trend to provide elastic resources and services to end-users, where the processing capacity resides at the network periphery as opposed to traditional data-centers. Despite their momentum, the control plane of these architectures remains complex and challenging to implement. To enhance control capability, in this work, we propose to use Software Defined Networking. SDN moves the control logic off data plane devices and onto external network entities, the controllers. We provide a proof-of-concept implementation of a multi-controller edge system and measure traffic delay and overheads. The results reveal the sensitivity of delay to the location of controllers and the magnitude of inter-controller and controller-node overheads. Guided by the above, we model the problem of determining the placement of controllers in the edge network. Using linearization and supermodular function techniques, we present approximation solutions which perform close to optimal and better than state-of-the-art methods.