INFOCOM 2019 论文列表

Motivated by the increasingly urgent demands for delivering fresh information, the age-of-information (AoI) has recently been introduced as an important metric for evaluating the timeliness performance of information update systems and has shed light on a number of research studies. Nevertheless, the most common goal of the existing works does not characterize the value of information freshness from the users' perspective. In this paper, we introduce the concept of effective AoI (EAoI) to quantify the freshness of the information users utilize for decision-making. We consider a general request-response model, which captures both proactive information update and timely information delivery, for investigating the scheduling problem with respect to EAoI minimization. By decomposing the scheduling problem into multiple computationally tractable subproblems, we propose request-aware scheduling policies for static and dynamic request models, respectively. The numerical results show that serving users requests proactively can reduce time-average EAoI in both scenarios.

Software-Defined Networking (SDN) provides a tractable and efficient architecture for operators to customize their network functions. Many traditional Data Center Networks (DCNs) are upgraded by SDN to improve link utilization and management flexibility, but they are lack of the instructions for selecting the substitutive SDN switches with the proper flow table space to achieve cost-effective and energy-saving networks. In this paper, we fill the gap of solving the flow table space estimation problem based on queuing theory. First, we divide the life process of a flow table entry into the packet-in process, the handling process and the serving process to establish a queuing system to estimate the least required number of the flow table entries of SDN switches. Second, we analyze the traffic distribution of DCNs to calculate the critical parameters in our model. Third, on the basis of the essence of the structured topologies in DCNs, we construct a probability model of routing strategies to quantize the influence of path selection. Comprehensive experiments show that the relative flow table space estimation error of our model can be less than 10%, which can give operators insights into the requirement of the SDN switches at specific positions.

High write throughput plays a vital role in improving the time efficiency of RFID-enabled applications, such as password update and over-the-air programming. In this paper, we make a fresh attempt to study the under-investigated problem of group write and discuss how to improve the write throughput in the commodity RFID system. By conducting extensive experiments, we reveal that the select operation specified by the C1G2 standard takes up the large overhead of a write cycle, which is the key factor in determining the write efficiency. Based on this finding, we propose an efficient write bundling (WB) scheme that bundles multiple writes up and executes them together in a burst mode, which greatly reduces the number of selects and thereby amplifies the write throughput. In WB, a carefully designed bit vector is assigned to each tag for connecting multiple tags into a run, such that a single select command is able to pick these tags concurrently. Besides, WB integrates multiple select commands into one by running a series of logic operations on the inventoried flags, which are used to indicate whether or not a tag is active. We implement WB in a commodity RFID system, with no need of any software modifications or hardware argument. Extensive experiment results show that WB is able to reduce the number of selects by 87.5% and produce a $2\times$ write amplification, compared with the C1G2-compatible exclusive write.

Mobile Edge Computing (MEC), envisioned as a cloud extension, pushes cloud resource from the network core to the network edge, thereby meeting the stringent service requirements of many emerging computation-intensive mobile applications. Many existing works have focused on studying the system-wide MEC service placement issues, personalized service performance optimization yet receives much less attention. Thus, in this paper we propose a novel adaptive user-managed service placement mechanism, which jointly optimizes a user's perceived-latency and service migration cost, weighted by user preferences. To overcome the unavailability of future information and unknown system dynamics, we formulate the dynamic service placement problem as a contextual Multi-armed Bandit (MAB) problem, and then propose a Thompson-sampling based online learning algorithm to explore the dynamic MEC environment, which further assists the user to make adaptive service placement decisions. Rigorous theoretical analysis and extensive evaluations demonstrate the superior performance of the proposed adaptive user-managed service placement mechanism.

Spectrum monitoring, run-time usage acquisition, and regulation enforcement, in general can be referred to as spectrum activity surveillance (SAS). It is essential to dynamic spectrum access with a two-fold impact: it is a primitive mechanism to continuously scan spectrum usage for system optimization purposes; it is also a prime widget to obtain spectrum footprints of legitimate users, and record misuse by unauthorized or malicious users. Seemingly trivial, large-scale SAS in wireless overlay networks is actually an open yet challenging problem. This is because on one hand, such a system is time and energy-sensitive and hence unlikely (or not necessary) to implement in practice, due to constraints of radio spectrum license and system deployment. On the other hand, it is not clear how to characterize the efficacy and performance of spectrum monitoring strategies in surveillance over a large geographical region, and detection of spectrum culprits, that is, unauthorized spectrum occupants. To address such a challenge, we consider SAS in a 3-dimensional space that is composed of spectrum, time, and geographical region, and then formulate monitoring strategies as graph walks by accounting for the locality of spectrum activities. In particular, our approach transforms the SAS problem from a globally collective activity to a set of localized, distributed actions, and strategy objectives from qualitative attributes to quantitative measures. We find that randomized strategies with m monitors can achieve a sweep-coverage over a space of n assignment points in Θ(n/m ln n) time, and detect an oblivious or adversarial spectrum culprit in Θ(n/m) time for SAS systems.

Network calculus computes end-to-end delay bounds for individual data flows in networks of aggregate schedulers. It searches for the best model bounding resource contention between these flows at each scheduler. Analyzing networks, this leads to complex dependency structures and finding the tightest delay bounds becomes a resource intensive task. The exhaustive search for the best combination of contention models is known as Tandem Matching Analysis (TMA). The challenge TMA overcomes is that a contention model in one location of the network can have huge impact on one in another location. These locations can, however, be many analysis steps apart from each other. TMA can derive delay bounds with high degree of tightness but needs several hours of computations to do so. We avoid the effort of exhaustive search altogether by predicting the best contention models for each location in the network. For effective predictions, our main contribution in this paper is a novel framework combining graph-based deep learning and Network Calculus (NC) models. The framework learns from NC, predicts best NC models and feeds them back to NC. Deriving a first heuristic from this framework, called DeepTMA, we achieve provably valid bounds that are very competitive with TMA. We observe a maximum relative error below 6%, while execution times remain nearly constant and outperform TMA in moderately sized networks by several orders of magnitude.

Non-orthogonal multiple access (NOMA) has received significant attention for future wireless networks. NOMA outperforms orthogonal schemes, such as OFDMA, in terms of spectral efficiency and massive connectivity. The joint subcarrier and power allocation problem in NOMA is NP-hard to solve in general, due to complex impacts of signal superposition on each users achievable data rates, as well as combinatorial constraints on the number of multiplexed users per sub-carrier to mitigate error propagation. In this family of problems, weighted sum-rate (WSR) is an important objective function as it can achieve different tradeoffs between sum-rate performance and user fairness. We propose a novel approach to solve the WSR maximization problem in multi-carrier NOMA with cellular power constraint. The problem is divided into two polynomial time solvable sub-problems. First, the multi-carrier power control (given a fixed subcarrier allocation) is non-convex. By taking advantage of its separability property, we design an optimal and low complexity algorithm (MCPC) based on projected gradient descent. Secondly, the single-carrier user selection is a non-convex mixed-integer problem that we solve using dynamic programming (SCUS). This work also aims to give an understanding on how each sub-problem's particular structure can facilitate the algorithm design. In that respect, the above MCPC and SCUS are basic building blocks that can be applied in a wide range of resource allocation problems. Furthermore, we propose an efficient heuristic to solve the general WSR maximization problem by combining MCPC and SCUS. Numerical results show that it achieves near-optimal sum-rate with user fairness, as well as significant performance improvement over OMA.

We analyze and optimize the performance of a new type of channel that exploits sunlight for wireless communication. Recent advances on visible light backscatter have shown that if mobile objects attach distinctive reflective patterns to their surfaces, simple photosensors deployed in our environments can decode the reflected light signals. Although the vision is promising, only initial feasibility studies have been performed so far. There is no analysis on how much information this channel can transmit or how reliable the links are. Achieving this vision is a complex endeavour because we have no control over (i) the sun or clouds, which determine the amount and direction of light intensity, and (ii) the mobile object, which determines the modulated reflection of sunlight. We investigate the impact of the surrounding light intensity and physical properties of the object (reflective materials, size and speed) to design a communication system that optimizes the encoding and decoding of information with sunlight. Our experimental evaluation, performed with a car moving on a regular street, shows that our analysis leads to significant improvements across many dimensions. Compared to the state of the art, we can encode seven times more information, and decode this information reliably from an object moving three times faster (53km/h) at a range that is four times longer (4m) and with three times lower light intensity (cloudy day).

Network Function Virtualization (NFV) allows operators to deploy network functions in virtual machines (VMs) and benefit from on-demand deployment. VMs are placed on one of the hosts in the cloud, and existing resource management algorithms assume full knowledge of the system's state. For large clusters, attaining the system's state creates bottlenecks and therefore it takes a long time to deploy network functionalities. Intuitively, placement can be accelerated if the resource management algorithm operates on a cached system state which is not entirely up to date, but the placement quality may suffer. Our work introduces a new cache refresh method that achieves an up to a 5.3x reduction in placement time with only a slight degradation of quality compared to having the complete and up to date system's state.

The effectiveness of many optimal network control algorithms (e.g., BackPressure) relies on the premise that all of the nodes are fully controllable. However, these algorithms may yield poor performance in a partially-controllable network where a subset of nodes are uncontrollable and use some unknown policy. Such a partially-controllable model is of increasing importance in real-world networked systems such as overlay-underlay networks. In this paper, we design optimal network control algorithms that can stabilize a partially-controllable network. We first study the scenario where uncontrollable nodes use a queue-agnostic policy, and propose a low-complexity throughput-optimal algorithm, called Tracking-MaxWeight (TMW), which enhances the original MaxWeight algorithm with an explicit learning of the policy used by uncontrollable nodes. Next, we investigate the scenario where uncontrollable nodes use a queue-dependent policy and the problem is formulated as an MDP with unknown queueing dynamics. We propose a new reinforcement learning algorithm, called Truncated Upper Confidence Reinforcement Learning (TUCRL), and prove that TUCRL achieves tunable three-way tradeoffs between throughput, delay and convergence rate.

Demand response (DR) is a vital means of electricity market in maintaining power grid reliability, sustainability and stability. DR can enable consumers (e.g. data centers) to reduce their electricity consumption when the supply of electricity is a shortage. The consumers will be rewarded if they reduce or shift some of their energy usage during peak hours. Aiming at solving the efficiency of DR, in this paper, we present MEDR, a mechanism on emergency DR in colocation data center. First, we formalize the MEDR problem and propose a dynamic programming to solve the optimization version of the problem. We then design a deterministic mechanism to solve the MEDR. We prove that our mechanism is truthful and it is an FPTAS, i.e., it can be approximated within 1 + ε for any given ε > 0, while the running time of our mechanism is polynomial in the number of tenants n and 1/ε. Furthermore, we also give an auction system covering the efficient FPTAS algorithm as bidding decision program for DR. Finally, we choose a real dataset to build a large number of simulation datasets in performance evaluation. The results show that our mechanism outperforms near-optimal and high utility demonstrate the effectiveness of our work.

We study networks of M/M/1 queues in which nodes act as caches that store objects. Exogenous requests for objects are routed towards nodes that store them; as a result, object traffic in the network is determined not only by demand but, crucially, by where objects are cached. We determine how to place objects in caches to attain a certain design objective, such as, e.g., minimizing network congestion or retrieval delays. We show that for a broad class of objectives, including minimizing both the expected network delay and the sum of network queue lengths, this optimization problem can be cast as an NP-hard submodular maximization problem. We show that so-called continuous greedy algorithm attains a ratio arbitrarily close to 1 - 1/e ≈ 0.63 using a deterministic estimation via a power series; this drastically reduces execution time over prior art, which resorts to sampling. Finally, we show that our results generalize, beyond M/M/1 queues, to networks of M/M/k and symmetric M/D/1 queues.

Despite the advantages that ocean surface Wireless Sensor Networks (WSN) have over traditional ocean monitoring methods, ocean WSN research suffers from lack of an accurate model that describes the stability of wireless links among sensor nodes. In this paper, we are going to investigate ocean surface waves' effects on the Line-of-Sight (LoS) link between sensors in a homogeneous WSN. Specifically, we will derive the blockage probability of LoS links between a transmitter and receiver pair due to wave movements, and analyze how environmental effects like wind speed affect it. Simulation results along with oceanographic measurements validate our analyses, making our model applicable in design and planning of WSN in the ocean environment.

The concept of social networking is integrated into Internet of things (IoT) to socialize smart objects by mimicking human behaviors, leading to a new paradigm of Social Internet of Things (SIoT). A crucial problem that needs to be solved is how to establish reliable relationships autonomously among objects, i.e., building trust. This paper focuses on exploring an efficient context-aware trustworthiness inference framework to address this issue. Based on the sociological and psychological principles of trust generation between human beings, the proposed framework divides trust into two types: familiarity trust and similarity trust. The familiarity trust can be calculated by direct trust and recommendation trust, while the similarity trust can be calculated based on external similarity trust and internal similarity trust. We subsequently present concrete methods for the calculation of different trust elements. In particular, we design a kernel-based nonlinear multivariate grey prediction model to predict the direct trust of a specific object, which acts as the core module of the entire framework. Besides, considering the fuzziness and uncertainty in the concept of trust, we introduce the fuzzy logic method to synthesize these trust elements. The experimental results verify the validity of the core module and the resistance to attacks of this framework.

The automotive industry is undergoing disruptive changes, e.g., ride sharing and self-driving cars which, in addition to leveraging wireless connectivity, may lead to dramatic changes in the volume of infotainment and work related data consumption of vehicle bound passengers. This paper studies the potential gains of leveraging clusters of V2V interconnected vehicles to enable: (1) improved opportunistic access to the cellular infrastructure; and (2), balancing traffic loads across cells through cluster multihoming. A stochastic geometric model and associated analysis are used to obtain a preliminary understanding of possible gains of cluster-based opportunistic relaying and its sensitivity to the system parameters, e.g., base station density, vehicular cluster size and density etc. An optimal network utility maximization formulation is then developed to serve as a baseline to evaluate a simple distributed cluster management algorithm which for the scenarios considered proves to be near-optimal. Overall the results suggest that 3-10x throughput gains are possible along with significant improvements in user rate fairness depending on the system parameters.

Embedding Radio-Frequency IDentification (RFID) into everyday objects to construct ubiquitous networks has been a long-standing goal. However, a major problem that hinders the attainment of this goal is the current inefficient reading of RFID tags. To address issue, the research community introduces the technique of Bloom Filter (BF) to RFID systems. This work presents TagMap, a practical solution that acquires BFs across commercial off-the-shelf (COTS) RFID tags in the physical layer, enabling upper applications to boost their performance by orders of magnitude. The key idea is to treat all tags as if they were a single virtual sender, which hashes each tag into different intercepted inventories. Our approach does not require hardware nor firmware changes in commodity RFID tags -allows for rapid, zero-cost deployment in existing RFID tags. We design and implement TagMap reader with commodity device (e.g., USRP N210) platforms. Our comprehensive evaluation reveals that the overhead of TagMap is 66.22% lower than the state-of-the-art solution, with a bit error rate of 0.4%.

Internet speed tests assess end-to-end network performance by measuring throughput for 10s of MB of TCP uploads and downloads. While such tests provide valuable insights into network health, they are of little use to network administrators since (1) the results are only available on the client that performs the test and (2) the tests can saturate the network, increasing load and worsening performance for other clients. In this paper, we present virtual speed test, a measurement based framework that enables an AP to estimate speed test results for any of its associated clients without any special-purpose probing, with zero end-user co-operation and purely based on passively observable parameters at the AP. We implemented virtual speed test using commodity hardware, deployed it in office and residential environments, and conducted measurements spanning multiple days having different network loads and channel conditions. Overall, virtual speed test has mean estimation error less than 6% compared to ground truth speed tests, yet with zero overhead, and outcomes available at the AP.

Mobile social network applications constitute an important platform for traffic information sharing, helping users collect and share sensor information about the driving conditions they experience on the traveled path in real time. In this paper we analyse the simple but fundamental model of a platform choosing between two paths: one with known deterministic travel cost and the other that alternates over time between a low and a high random cost states, where the low and the high cost states are only partially observable and perform respectively better and worse on average than the fixed cost path. The more users are routed over the stochastic path, the better the platform can infer its actual state and use it efficiently.At the Nash equilibrium, if asked to take the riskier path, in many cases selfish users (that are allowed to have access to the information collected by the platform) will myopically disregard the optimal path suggestions of the platform, leading to a suboptimal system without enough exploration on the stochastic path. We prove the interesting result that if the past collected information is hidden from users, the system becomes incentive compatible and even `sophisticated' users (in the sense that they have full capability to reverse-engineer the platform's recommendation and derive the path state distribution conditional on the recommendation) prefer to follow the platform's recommendations. In a more practical setting where the platform implements a model-free Q-learning algorithm to minimise the social travel cost, our analysis suggests that increasing the accuracy of the learning algorithm increases the range of system parameters for which sophisticated users follow the recommendations of the platform, becoming in the limit fully incentive compatible. Finally, we extend the two-path model to include more stochastic paths, and show that incentive compatibility holds under our information restriction mechanism.

We analyze the prioritized sharing between an added value Mobile Virtual Network Operator (MVNO) and multiple Mobile Network Operators (MNOs). An added value MVNO is one which earns added revenue from wireless users in addition to the revenue it directly collects for providing them wireless service. To offer service, an MVNO needs to contract with one or more MNOs to utilize their networks. Agreeing on such a contract requires the MNOs to consider the impact on their revenue from allowing the MVNO to enter the market as well as the possibility that other MNOs will cooperate. To further protect their customers, the MNOs may prioritize their direct customers over those of the MVNO. We establish a multi-stage game to analyze the equilibrium decisions of the MVNO, MNOs, and users in such a setting. In particular, we characterize the condition under which the MVNO can collaborate with the MNOs. The results show that the MVNO tends to cooperate with the MNOs when the band resources are limited and the added value is significant. When there is significant difference in band resources among the MNOs, the MVNO first considers cooperating with the MNO with a smaller band. We also consider the case when the users also have access to unlicensed spectrum.