We study online decision-making problems in network applications using the framework of contextual combinatorial multi-armed bandits (C2MAB). Although bandit methods provide a natural solution, two key challenges arise in practice: corruption in feedback and heterogeneity across clients. Corruption may stem from adversarial behaviors or system anomalies, leading to biased reward estimations, while heterogeneity reflects differences in clients’ environments such as computation capabilities or network conditions. To address these challenges, we formulate the C2MAB under corruption (C2MAB-C) problem and extend it to the setting with heterogeneous environmental parameters. We then propose two novel algorithms, namely CW-C2UCB, which leverages confidence-weighted estimations to mitigate corruption effects, and CW-C2CLUB, which further integrates an online clustering mechanism to adaptively group tasks based on shared structure. We derive tight theoretical regret bounds for both algorithms under various corruption models showing that our upper bounds match the established lower bounds up to logarithmic factors. Empirical results on three real-world applications, content delivery networks, client selection in federated learning, and VR video streaming, demonstrate that our proposed algorithms significantly outperform existing baselines, achieving lower regret and stronger resilience in adversarial environments.

Technology companies have built large-scale heterogeneous GPU clusters to support various workloads. However, their cluster machines are found underutilized with severe resource fragmentation. The main causes are myopic online scheduling of incoming tasks and complex placement constraints specified by users or systems. In this paper, we propose to use task migration as a measure to alleviate resource fragmentation. Our trace-driven analysis on a production cluster with 12kmachines reveals that almost at any random snapshot, most of the concurrent tasks have long run-times and small migration times, thus justifying the feasibility of task migration. By making the complex constraints mathematically tractable, we formulate an integer linear programming problem. An efficient heuristic algorithm called Iterative Partitioned Defragmentation (IPD) is presented to perform task migration in multiple iterations of computation. We design and implementDefrag, an operational resource defragmentation system on Kubernetes, and deploy it on the production clusters. Trace-driven experiments show thatDefragcan reduce up to 80% idle CPUs and 29% idle GPUs on average. Furthermore,Defragcan refine the performance of online scheduling strategies by reducing up to 57% idle CPUs and 35% idle GPUs at the time of execution. Our real-world experiment also demonstrates the effectiveness ofDefrag.

Artificial Intelligence-Generated Content (AIGC) has been gaining significant traction for automatic generation of diverse content. Due to the GPU-intensive generation process and the high costs associated with purchasing and operating GPUs, users often prefer to submit requests to a nearby edge cloud, maintained by an AIGC cloud service provider. Efficiently scheduling AIGC requests in the edge cloud faces non-trivial challenges. First, AIGC requests emphasize the quality of generated content, yet conventional scheduling algorithms often overlook this aspect. Second, when the volume of incoming requests exceeds the capacity of the cloud, the AIGC service provider needs to select appropriate requests to execute, which is further complicated by the online arrival pattern of requests and the constraints imposed by request deadlines. Third, users dynamically submit multiple requests at different times. To manage costs, each user operates within a pre-allocated budget for a given time period. For the AIGC cloud service provider, it is highly non-trivial to identify valuable requests and judiciously balance different user budgets. To tackle the above challenges, we target the online AIGC request scheduling problem with the new objective of maximizing the overall content generation quality. We first conduct real experiments to establish the quality model between inference steps and the quality of generated content. Then, based on this quality model, we formulate the problem into an integer linear program, which is proven NP-hard. Under a primal-dual framework, we carefully design the update of multiple dual variables, to flexibly control the consumption of edge resources and user budgets. We rigorously analyze the performance of the proposed algorithm and prove a theoretical performance guarantee on its competitive ratio. Extensive real-world trace-driven experiments manifest that our proposed method improves the state-of-the-art by up to 25.3% in overall content generation quality.

The Autonomous System (AS) level topology observed from current measurement infrastructures is far from complete. Although Looking Glass (LG) vantage points (VPs) that support BGP route queries can provide valuable topology information, the query rate limitations of LG VPs imply that blindly using the VPs to conduct more measurements to improve the topology completeness is inefficient, if not infeasible. In this paper, we try to improve the efficiency by designing a link prediction based measurement strategy, whose basic idea is to first predict where unseen AS links are likely to be located and then use the prediction results to guide the measurements toward a more complete AS-level topology. We formulate the prediction of unseen AS links as a matrix completion problem and develop a side-information assisted learning-based matrix completion method. The method exploits a neural network and utilizes carefully chosen AS attributes based on our understanding on Internet peering practices, thereby learning more expressive latent vectors and achieving outstanding prediction performance in our scenario. We then develop a measurement strategy which takes the link prediction results as guidance to achieve efficient topology completeness improvements. The strategy leverages several heuristics to estimate the utilities of different measurements and takes a greedy algorithm to select the most valuable measurements. Experiments show that our link prediction method can achieve a high AUC (Area Under the Receiver Operating Characteristic Curve) of 0.834 and the link-guided measurement strategy can discover 1.82 times more unseen links than those discovered from non-guided measurement strategies with an equal number of measurements.

To make edge AI inference carbon-neutral, we perform a comprehensive mathematical and algorithmic study on the complex online management of AI model selection and placement with carbon allowance trading. This work is non-trivial due to the critical challenges such as the unknown stochastic distributions and arrivals of inference data, the exploration-exploitation tradeoff with model switching cost, and the uncertain, time-varying allowance prices and system environments. We first model a long-term stochastic cost optimization problem to capture these challenges. Then, we design a novel learning-centric decomposition-based online algorithmic framework which, on the one hand, samples and places the models repeatedly to minimize the expected inference loss with bounded model switches, and on the other hand, buys and sells carbon allowances cost-efficiently in real time toward carbon neutrality without relying on future allowance prices and system emissions. We further formally prove multiple performance guarantees of our algorithms in terms of sub-linear regret and fit. Finally, we conduct trace-driven evaluations to confirm the substantial advantages of our approach compared to baselines and state-of-the-arts in practice.

Cellular-connected UAV systems have enabled a wide range of low-altitude aerial services. However, these systems still face many challenges, such as frequent handovers and the inefficiency of traditional transport protocols. To better study these issues, we develop a modular and scalable simulation platform specifically designed for UAVs communication leveraging the research ecology in wireless communication of MATLAB. The platform supports flexible 5G NR node deployment, customizable UAVs mobility models, and multi-network-interface extensions. It also supports multiple transport protocols including TCP, UDP, QUIC, etc., allowing to investigate how different transport protocols affect UAVs communication performance. In addition, the platform includes a handover management module, enabling the evaluation of both traditional and learning-based handover strategies. Our platform can serve as a testbed for the development and evaluation of advanced transmission strategies in cellular-connected UAV systems.

Large language models (LLMs) typically require fine-tuning for domain-specific tasks, and LoRA offers a computationally efficient approach by training low-rank adaptors. LoRA is also communication-efficient for federated LLMs when multiple users collaboratively fine-tune a global LLM model without sharing their proprietary raw data. However, even the transmission of local adaptors between a server and clients risks serious privacy leakage. Applying differential privacy (DP) to federated LoRA encounters a dilemma: adding noise to both adaptors amplifies synthetic noise on the model, while fixing one adaptor impairs the learnability of fine-tuning. In this paper, we propose FedASK (Differentially Private Federated Low Rank Adaptation with Double SKetching) , a novel federated LoRA framework to enable effective updating of both low-rank adaptor matrices with robust differential privacy. Inspired by randomized SVD, our key idea is a two-stage sketching pipeline. This pipeline first aggregates carefully sketched, privacy-preserving local updates, and then reconstructs the global matrices on the server to facilitate effective updating of both adaptors. We theoretically prove FedASK's differential privacy guarantee and its exact aggregation property. Comprehensive experiments demonstrate that FedASK consistently outperforms baseline methods across a variety of privacy settings and data distributions.

Data silos create barriers to accessing and utilizing data dispersed over networks. Directly sharing data easily suffers from the long downloading time, the single point failure and the untraceable data usage. In this paper, we present Minerva, a peer-to-peer cross-cluster data query system based on the InterPlanetary File System (IPFS). Minerva makes use of the distributed Hash table (DHT) lookup to pinpoint the locations that store content chunks. We theoretically model the DHT query delay and introduce a fat Merkle tree structure as well as the DHT caching to reduce it. We design the query plan for read and write operations on top of Apache Drill that enables the collaborative query with decentralized workers. We conduct comprehensive experiments on Minerva, and the results show that Minerva achieves up to$2.08 \times$query performance acceleration compared to the original IPFS data query, and can complete data analysis queries on the Internet-like environments within an average latency of 0.615 second. With a collaborative query, Minerva could perform up to$1.39 \times$performance acceleration than the centralized query with raw data shipment.

Distributed optimization in resource constrained devices demands both communication efficiency and fast convergence rates. Newton-type methods are getting preferable due to their superior convergence rates compared to the first-order methods. In this paper, we study a new problem in regard to the second-order distributed optimization over unreliable networks. The working devices are power-limited or operate in unfavorable wireless channels, experiencing packet losses during their uplink transmission to the server. Our scenario is very common in real-world and leads to instability of classical distributed optimization methods especially the second-order methods because of their sensitivity to the imprecision of local Hessian matrices. To achieve robustness to high packet loss, communication efficiency and fast convergence rates, we propose a novel distributed second-order method, called RED-New (Packet loss Resilient Distributed Approximate Newton). Each iteration of RED-New comprises two rounds of light-weight and lossy transmissions, in which the server aggregates the local information with a new developed scaling strategy. We prove the linear-quadratic convergence rate of RED-New. Experimental results demonstrate its advantage over first-order and second-order baselines, and its tolerance to packet loss rate ranging from 5% to 40%.

Federated Learning, as an emerging edge artificial intelligence paradigm, enables a group of clients to collaboratively train a global model without revealing their local data. The conventional FL algorithms usually depend on the access to exact gradient or Hessian matrix, which may be inaccessible due to resource limitation or application restriction. Meanwhile, Federated Learning intrinsically suffers from data heterogeneity, which restricts the global model from performing well on each clients’ task. To simultaneously tackle these two challenges, we propose a gradient free personalized federated learning framework, namely pFedZO. We utilize infimal convolution to bridging the gap between personal and global knowledge, and exploit zeroth-order gradient estimator to solve the problem. We theoretically show the local approximation can converge sublinearly and the global problem converge to the neighbourhood of the optimal with a same speed. We further propose pFedZO-Heur to accelerate training procedure. Experimentally, we verify that pFedZO excels at test accuracy with the vanilla Zeroth-Order Optimization (ZOO) based FL by <?TeX $5\%$?> Math 1 . We also show pFedZO-Heur can achieve the same performance level with lower time consumption.

Fine-tuning pre-trained models with task-specific data can produce customized models effective for downstream tasks. However, operating large-scale such fine-tuning tasks in real time in the data center faces non-trivial challenges, including unpredictable task arrival and system environment dynamics, complex deadline-driven fine-tuning scheduling, and intertwined task pricing and cost management. In this paper, targeting the popular Low-Rank Adaptation (LoRA) fine-tuning technique, we present the design and study of a novel auction-based mechanism to jointly schedule and price LoRA tasks in an online manner. We first model the social welfare maximization problem as an integer program for the fine-tuning service provider, capturing all the aforementioned challenges. Then, to solve this NP-hard problem online, we equivalently reformulate this original problem into a schedule selection problem, where each schedule corresponds to a concrete pre-specified operation plan over time for a task. We can thus design a polynomial-time online approximation algorithm via the online primal-dual method to determine the schedule, and with the dual variables, also determine the pricing for each admitted task. We rigorously prove the competitiveness of our online approach against the offline optimum, and prove the economic properties of truthfulness and individual rationality regarding pricing. Finally, we conduct extensive experiments and have validated the substantial advantages of our approach compared to existing methods.

Probabilistic maximum coverage (PMC) is an important framework that can model many network applications, including mobile crowdsensing, content delivery, and task repli¬cation. In PMC, an operator chooses nodes in a graph that can probabilistically cover other nodes, aiming to maximize the total rewards from the covered nodes. To tackle the challenge of unknown parameters in network environments, PMC are studied under the online learning context, i.e., the PMC bandit. However, existing PMC bandits lack context-awareness and fail to exploit valuable contextual information, limiting their efficiency and adaptability in dynamic environments. To address this limitation, we propose a novel context-aware PMC bandit model (C-PMC). C-PMC employs a linear structure to model the mean outcome of each arm, effectively incorporating contextual information and enhancing its applicability to large-scale network systems. Then we design a variance-adaptive contextual combinatorial upper confidence bound algorithm (VAC2UCB), which utilizes second-order statistics, specifically variance, to re-weight feedback data and estimate unknown parameters. Our theoretical analysis shows that C-PMC achieves a regret of $\tilde O(d\sqrt {|\mathcal{V}|T} )$, independent of the number of edges $|\mathcal{E}|$ and action size K. Finally, we conduct experiments on synthetic and real-world datasets, showing the superior performance of VAC2UCB in context-aware mobile crowdsensing and user-targeted content delivery applications.

Scheduling generative-AI jobs in the edge computing environment faces multiple non-trivial challenges, including the Directed Acyclic Graph (DAG) dependency among tasks, the intrinsic intertwinement between task scheduling and model selection, and the dynamic unpredictable arrival of job DAGs. In this work, we capture all such challenges and formulate a non-linear integer program to optimize the long-term profit of the generative-AI service provider, i.e., service revenue of the admitted jobs minus system costs of executing the tasks contained in such job DAGs. This problem is NP-hard even in the offline setting. To solve it, we first reformulate it into an equivalent schedule selection problem using generated schedules to tackle complex constraints. Then, we design a new online scheduling method through the online primal-dual technique. Experimental results confirm that our approach can increase the total service profit by up to 41.2% compared to existing algorithms.

The rapid evolution of multimedia and computer vision technologies requires adaptive visual model deployment strategies to effectively handle diverse tasks and varying environments. This work introduces AxiomVision, a novel framework that can guarantee accuracy by leveraging edge computing to dynamically select the most efficient visual models for video analytics under diverse scenarios. Utilizing a tiered edge-cloud architecture, AxiomVision enables the deployment of a broad spectrum of visual models, from lightweight to complex DNNs, that can be tailored to specific scenarios while considering camera source impacts. In addition, AxiomVision provides three core innovations: (1) a dynamic visual model selection mechanism utilizing continual online learning, (2) an efficient online method that efficiently takes into account the influence of the camera's perspective, and (3) a topology-driven grouping approach that accelerates the model selection process. With rigorous theoretical guarantees, these advancements provide a scalable and effective solution for visual tasks inherent to multimedia systems, such as object detection, classification, and counting. Empirically, AxiomVision achieves a 25.7% improvement in accuracy.

The rapid development of new communication applications such as virtual reality and video conferencing has brought new challenges to congestion control algorithms. In particular, these applications have specific requirements in terms of delay. Meeting specific delay requirements without high throughput loss is difficult, especially in dynamic networks. In addition, it is important that the proposed congestion control algorithms can be easily deployed. In this paper, we propose a congestion control algorithm, namely TD-BBR, to meet the delay requirements of different applications. TD-BBR is built on BBR and can adapt to various network environments without high throughput loss. we employ an online algorithm based on the recursive least squares method to predict future bandwidth. We design a simple and effective algorithm to adjust the congestion window (CWND) to meet the specific delay requirements according to the value of bandwidth prediction and the distance between the current delay and the target delay. We implement a real congestion control system through extended Berkeley Packet Filter (eBPF) technology and have deployed it in the Linux kernel without recompiling the kernel. Extensive experiments show that TD-BBR can effectively meet different delay requirements in most cases, decrease the 95th percentile delay, and avoid high throughput loss compared to other congestion control algorithms,

Nowadays, the training data and neural network models are getting increasingly large. The training time of deep learning will become unbearably long on a single machine. To reduce the computation and storage burdens, distributed deep learning has been put forward to collaboratively train a large neural network model with multiple computing nodes in parallel. The unbalanced development of computation and communication capabilities has led to training time being dominated by communication time, making the communication overhead a major challenge toward efficient distributed deep learning. Communication compression is an effective method to alleviate communication overhead, and it has evolved from simple random sparsification or quantization to versatile strategies or data structures. In this survey, existing communication compression techniques are reviewed and classified to provide a bird’s eye view. The main properties of each class of compression methods are analyzed, and their applications or theoretical convergence are described if necessary. This survey is potentially helpful for researchers and engineers to understand the up-to-date achievements on the communication compression techniques that accelerate the training of large deep learning models.

This paper studies a fundamental problem regarding the security of blockchain PoW consensus on how the existence of multiple misbehaving miners influences the profitability of selfish mining. Each selfish miner maintains a private chain and makes it public opportunistically for acquiring more rewards incommensurate to his Hash power. We first establish a general Markov chain model to characterize the state transition of public and private chains for Basic Selfish Mining (BSM), and derive the stationaryprofitable thresholdof Hash power in closed form. It reduces from 25% for a single attacker to below 21.48% for two symmetric attackers theoretically, and further reduces to around 10% with eight symmetric attackers experimentally. We next explore the profitable threshold when one of the attackers performs strategic mining based on Partially Observable Markov Decision Process (POMDP) that only half of the attributes pertinent to a mining state are observable to him. An online algorithm is presented to compute the nearly optimal policy efficiently despite the large state space and high dimensional belief space. The profitable threshold is much lower for the strategic attacker. Last, we formulate a simple model of absolute mining revenue that yields an interesting observation: selfish mining is never profitable at the first difficulty adjustment period, but relies on the reimbursement of stationary selfish mining gains in future periods. The delay till being profitable of an attacker increases with the decrease of his Hash power, making blockchain miners more cautious about performing selfish mining.

Given the rapid growth of user-generated videos, internet traffic has been heavily dominated by online video streaming. Caching videos on edge servers in close proximity to users has been an effective approach to reduce the backbone traffic and the request response time, as well as to improve the video quality on the user side. Video popularity, however, can be highly dynamic over time. The cost of cache replacement at edge servers, particularly that related to service interruption during replacement, is not yet well understood. This paper presents a novel lightweight video caching algorithm for edge servers, seeking to optimize the hit rate with real-time decisions and minimized cost. Inspired by recent advances in deep Q-learning, our DQN-based online video caching (DQN-OVC) makes effective use of the rich and readily available information from users and networks. We decompose the Q-value function as a product of the video value function and the action function, which significantly reduces the state space. We instantiate the action function for cost-aware caching decisions with low complexity so that the cached videos can be updated continuously and instantly with dynamic video popularity. We used video traces from Tencent, one of the largest online video providers in China, to evaluate the performance of our DQN-OVC and to compare it with state-of-the-art solutions. The results demonstrate that DQN-OVC significantly outperforms the baseline algorithms in the edge caching context.

Due to the high cost of cellular networks, vehicle users would like to offload elastic traffic through vehicular networks as much as possible. This demand prompts researchers to consider how to make the vehicular network system achieve better performance for requests coming online, such as maximizing throughput. The traffic in vehicular networks is transferred through opportunistic contacts between vehicles and infrastructures. When making scheduling decisions, the scheduler must be aware of vehicles’ future trajectories. Vehicles’ future trajectories are usually predicted by trajectory prediction algorithms when users are unwilling to report their future trips. Unfortunately, no trajectory prediction algorithm can be completely accurate, and these inaccurate prediction results will degrade the throughput achieved by scheduling algorithms. In this paper, we focus on reducing the negative impact of inaccurate predictions. Specifically, we measure two data-driven trajectory prediction algorithms that have been widely used for trajectory predictions and understand the characteristics of the accuracy of predicted contacts. Based on the enlightenment from the measurement, we design a system, i.e., i-Offload, to offload elastic traffic under imperfect trajectory predictions. The experimental results show that our system has good throughput and high scheduling efficiency even under imperfect trajectory predictions. Compared with existing scheduling algorithms, our method improves the throughput by about one time.

Communication scheduling is crucial to accelerate the training of large deep learning models, in which the transmission order of layer-wise deep neural network (DNN) tensors is determined for a better computation-communication overlap. Prior approaches adopt user-level tensor partitioning to enhance the priority scheduling with finer granularity. However, a startup time slot inserted before every tensor partition will neutralize this scheduling gain. Tuning hyper-parameters for tensor partitioning is difficult, especially when the network bandwidth is shared or time-varying in multi-tenant clusters. In this article, we propose Mercury, a simple transport layer scheduler that moves the priority scheduling to the transport layer at the packet granularity. The packets with the highest priority in the Mercury buffer will be transmitted first. Mercury achieves the near-optimal overlapping between communication and computation. It also leverages the immediate aggregation at the transport layer to enable the full overlapping of gradient push and pull. We implement Mercury in MXNet and conduct comprehensive experiments on five popular DNN models in various environments. Mercury can well adapt to dynamic communication and computation resources. Experiments show that Mercury accelerates the training by up to 130% compared to the classical PS architecture, and 104% compared to state-of-the-art tensor partitioning methods.

This paper designs the vehicle tracking and resource allocation in the terahertz (THz) vehicle-to-infrastructure communications (V2I) networks, where roadside units (RSUs) equipped with leaky-wave antennas help to estimate the driving states of multiple vehicles and optimize the transmit power and bandwidth per vehicle after receiving the vehicles’ feedback. Different from the conventional phased arrays, the leaky-wave antenna has the potential of improving the sensing accuracy with lower system overhead thanks to its unique spatial-spectral coupling feature. The generalized mobile scenario is studied in which vehicles drive at time-varying speeds. A novel unscented Kalman filter (UKF) based solution is proposed to track the vehicles without requirement of addressing the Doppler effect. Based on the estimated states of multiple vehicles, a low-complexity resource allocation method is developed to maximize the sum rate under user fairness concern. Simulation results confirm that the proposed tracking solution can evaluate the propagation angle, vehicle’s states and inter-vehicle distance accurately, and the tailored resource allocation method strikes a delicate balance between the sum rate and user fairness in the multi-vehicle V2I scenario.

In this paper, we design the vehicle tracking in the terahertz (THz) vehicle-to-infrastructure (V2I) networks, where roadside units (RSUs) equipped with leaky-wave antennas help to estimate the driving states of multiple vehicles after receiving the vehicles’ feedback. Different from the conventional phased arrays, the leaky-wave antenna has the potential of improving the sensing accuracy with lower system overhead thanks to its unique spatial-spectral coupling feature. The generalized mobile scenario is studied in which vehicles drive at time-varying speeds. A novel unscented Kalman filter (UKF) based solution is proposed to track the vehicles without requirement of addressing the Doppler effect. Simulation results confirm that the proposed tracking solution can evaluate the propagation angle, vehicle’s states and inter-vehicle distance accurately.

Communication scheduling is crucial to improve the efficiency of training large deep learning models with data parallelism, in which the transmission order of layer-wise deep neural network (DNN) tensors is determined for a better computation-communication overlap. Prior approaches adopt tensor partitioning to enhance the priority scheduling with finer granularity. However, a startup time slot inserted before each tensor partition will neutralize this scheduling gain. Tuning the optimal partition size is difficult and the application-layer solutions cannot eliminate the partitioning overhead. In this paper, we propose Mercury, a simple transport layer scheduler that does not partition the tensors, but moves the priority scheduling to the transport layer at the packet granularity. The packets with the highest priority in the Mercury buffer will be transmitted first. Mercury achieves the near-optimal overlapping between communication and computation. It leverages immediate aggregation at the transport layer to enable the coincident gradient push and parameter pull. We implement Mercury in MXNet and conduct comprehensive experiments on five DNN models in an 8-node cluster with 10Gbps Ethernet. Experimental results show that Mercury can achieve about 1.18 ~ 2.18 × speedup over vanilla MXNet, and 1.08 ~ 2.04× speedup over the state-of-the-art tensor partitioning solution.

Researchers have noticed the AS-level Internet topology that can be observed from the current measurement infrastructure is far from complete, which means researchers have to deploy more measurement vantage points (VPs) and conduct measurements for more source/destination pairs to fully understand the whole Internet. Unfortunately, it is known that blindly deploying more points and conducting more measurements to achieve the goal is inefficient, if not infeasible. In this paper, we try to improve the efficiency by predicting where unseen AS links might be located from the observed AS paths to guide the measurements towards a more complete AS-level topology. We formulate the prediction of unseen links as a matrix completion problem. However, the traditional matrix completion methods have limited learning capacities and cannot deal with the complex constraints on the underlying topology. We develop a learning-based matrix completion method specifically for the unseen AS link prediction problem. The method exploits a neural network and utilizes side-information which is carefully chosen from AS attributes based on our understanding on Internet peering practices, therefore our method is able to learn more expressive latent vectors and achieves outstanding prediction performance in our scenario. Experiments performed on a real-world dataset show the prediction results can achieve a high AUC (Area Under the Receiver Operating Characteristic Curve) of 0.834.

The past few years have witnessed a surge of interest towards deep reinforcement learning (DRL) in computer networks. With extraordinary ability of feature extraction, DRL has the potential to re-engineer the fundamental resource allocation problems in networking without relying on pre-programmed models or assumptions about dynamic environments. However, such black-box systems suffer from poor robustness, showing high performance variance and poor tail performance. In this work, we propose a unified Teacher-Student learning framework that harnesses rich domain knowledge to improve robustness. The domain-specific algorithms, less performant but more trustable than DRL, play the role of teachers providing advice at critical states; the student neural network is steered to maximize the expected reward as usual and mimic the teacher’s advice meanwhile. The Teacher-Student method comprises of three modules where the confidence check module locates wrong decisions and risky decisions, the reward shaping module designs a new updating function to stimulate the learning of student network, and the prioritized experience replay module to effectively utilize the advised actions. We further implement our Teacher-Student framework in existing video streaming (Pensieve), load balancing (DeepLB), and TCP congestion control (Aurora). Experimental results manifest that the proposed approach reduces the performance standard deviation of DeepLB by 37%; it improves the 90th, 95th, and 99th tail performance of Pensieve by 7.6%, 8.8%, and 10.7% respectively; and it accelerates the growth rate of Aurora by 2x at the initial stage, and achieves a more stable performance in dynamic environments.

Ethereum is one of the most popular blockchain systems that support more than half a million transactions every day and foster miscellaneous decentralized applications with its Turing-complete smart contract machine. Whereas it remains mysterious what the transaction pattern of Ethereum is and how it evolves over time. In this article, we study the evolutionary behavior of Ethereum transactions from a temporal graph point of view. We first develop a data analytic platform to collect external transactions associated with users as well as internal transactions initiated by smart contracts. Three types of temporal graphs, user-to-user, contract-to-contract, and user-contract graphs, are constructed according to trading relationships and are segmented with an appropriate time window. We observe a strong correlation between the size of the user-to-user transaction graph and the average Ether price in a time window, while no evidence of such linkage is shown at the average degree, average edge weights, and average triplet closure duration. The macroscopic and microscopic burstiness of Ethereum transactions are validated. We analyze the Gini indexes of the transaction graphs and the user wealth in which Ethereum is found to be very unfair since the very beginning, in a sense, “the rich is already very rich.”

Packet routing is one of the fundamental problems in computer networks in which a router determines the next-hop of each packet in the queue to get it as quickly as possible to its destination. Reinforcement learning (RL) has been introduced to design autonomous packet routing policies with local information of stochastic packet arrival and service. However, the curse of dimensionality of RL prohibits the more comprehensive representation of dynamic network states, thus limiting its potential benefit. In this article, we propose a novel packet routing framework based onmultiagentdeep RL (DRL) in which each router possess anindependentlong short term memory (LSTM) recurrent neural network (RNN) for training and decision making in afully distributedenvironment. The LSTM RNN extracts routing features from rich information regarding backlogged packets and past actions, and effectively approximates the value function of Q-learning. We further allow each route to communicate periodically with direct neighbors so that a broader view of network state can be incorporated. The experimental results manifest that our multiagent DRL policy can strike the delicate balance between congestion-aware and shortest routes, and significantly reduce the packet delivery time in general network topologies compared with its counterparts.

The past few years has witnessed a surge of interest towards deep reinforcement learning (Deep RL) in computer networks. With extraordinary ability of feature extraction, Deep RL has the potential to re-engineer the fundamental resource allocation problems in networking without relying on pre-programmed models or assumptions about dynamic environments. However, such black-box systems suffer from poor robustness, showing high performance variance and poor tail performance. In this work, we propose a unified Teacher-Student learning framework that harnesses rich domain knowledge to improve robustness. The domain-specific algorithms, less performant but more trustable than Deep RL, play the role of teachers providing advice at critical states; the student neural network is steered to maximize the expected reward as usual and mimic the teacher's advice meanwhile. The Teacher-Student method comprises of three modules where the confidence check module locates wrong decisions and risky decisions, the reward shaping module designs a new updating function to incentive the learning of student network, and the prioritized experience replay module to effectively utilize the advised actions. We further implement our Teacher-Student framework in existing video streaming (Pensieve), load balancing (DeepLB) and TCP congestion control (Aurora). Experimental results manifest that the proposed approach reduces the performance standard deviation of DeepLB by 37%; it improves the 90th, 95th and 99th tail performance of Pensieve by 7.6%, 8.8%, 10.7% respectively; and it accelerates the rate of growth of Aurora by 2x at the initial stage, and achieves a more stable performance in dynamic environments.

This work presents the design and implementation of TyrLoc, an accurate multi-technology switching MIMO localization system that can be deployed on low-cost SDRs. TyrLoc only uses a single RF Chain to switch on each antenna in an antenna array within the coherence time asynchronously, thus mimicking a MIMO platform to pinpoint the positions of WIFI, Bluetooth Low Energy (BLE) and LoRa devices. TyrLoc makes three key technical contributions. First, TyrLoc modifies the firmware of inexpensive PlutoSDR that controls the antenna switching pattern and tags the signal associated with each antenna. Second, it develops a two-stage fine-grained carrier frequency offset (CFO) calibration algorithm that harnesses the agile antenna switching pattern and is 10× more accurate than the baseline method. Third, TyrLoc employs an interpolated transform approach to facilitate angle-of-arrival (AoA) estimation in the presence of missing antennas. The AoA-based localization experiments in a multipath-rich indoor environment show that TyrLoc with eight antennas achieves the median errors of 63cm for WIFI, 39cm for BLE and 32cm for LoRa, respectively.

Channel-state information (CSI)-based fingerprinting for WIFI indoor localization has attracted lots of attention very recently. The frequency diverse and temporally stable CSI better represents the location-dependent channel characteristics than the coarse received signal strength (RSS). However, the acquisition of CSI requires the cooperation of access points (APs) and involves only data frames, which imposes restrictions on real-world deployment. In this article, we present CRISLoc, the first CSI fingerprinting-based localization prototype system using ubiquitous smartphones. CRISLoc operates in a completely passive mode, overhearing the packets on-the-fly for his own CSI acquisition. The smartphone CSI is sanitized via calibrating the distortion enforced by WiFi amplifier circuits. CRISLoc tackles the challenge of altered APs with a joint clustering and outlier detection method to find them. A novel transfer learning approach is proposed to reconstruct the high-dimensional CSI fingerprint database on the basis of the outdated fingerprints and a few fresh measurements, and an enhanced KNN approach is proposed to pinpoint the location of a smartphone. Our study reveals important properties about the stability and sensitivity of smartphone CSI that has not been reported previously. Experimental results show that CRISLoc can achieve a mean error of around 0.29 m in a 6 m × 8 m research laboratory. The mean error increases by 5.4 and 8.6 cm upon the movement of one and two APs, which validates the robustness of CRISLoc against environmental changes.

Owing to the ubiquitous penetration of Wi-Fi in our daily lives, Wi-Fi indoor localization has attracted intensive attentions in the last decade or so. Despite some significant progresses, the high accuracy of existing systems is still achieved at the cost of dense access point (AP) deployment. The more practical single AP localization is largely left as an open problem because the hardware-induced time delay “contaminates” the measurement of signal propagation time in the air. In this article, we design and implement M3to tackle this challenge with commodity Wi-Fi cards. M3exploits a multipath-assisted approach that turns the harmful multipath from foe to friend to enable single AP localization: a device can be pinpointed through the combination of azimuths and the relative time of flight (ToF) of Line-of-Sight (LoS) signal and reflection signals, eliminating the need for multiple APs along with their absolute ToF measurements. M3further utilizes frequency hopping to combine multiple channels to form a virtually wider-spectrum channel for higher ToF resolution. As a prominent feature of M3, the channels do not need to be adjacent. Comprehensive experiments demonstrate that M3outperforms the state-of-the-art systems and achieves a median localization accuracy of 71 cm in three environments with a single AP.

Since Network Function Virtualization (NFV) decouples network functions (NFs) from the underlying dedicated hardware and realizes them in the form of software called Virtual Network Functions (VNFs), they are enabled to run in any resource-sufficient virtual machines. A service function chain (SFC) is composed of a sequential set of VNFs. As VNFs are vulnerable to various faults such as software failures, we consider how to deploy both active and standby SFC instances. Given the complexity and unpredictability of the network state, we propose a double deep Q-networks based online SFC placement scheme DDQP. Specifically, DDQP uses deep neural networks to deal with large continuous network state space. In the case of stateful VNFs, we offer constant generated state updates from active instances to standby instances to guarantee seamless redirection after failures. With the goal of balancing the waste of resources and ensuring service reliability, we introduce five progressive schemes of resource reservations to meet different customer needs. Our experimental results demonstrate that DDQP responds rapidly to arriving requests and reaches near-optimal performance. Specifically, DDQP outweighs the state-of-the-art method by 16.30% and 38.51% higher acceptance ratio under different schemes with 82x speedup on average. In order to enhance the integrity of the SFC state transition, we further proposed DDQP+, which extends DDQP by adding the delayed placement mechanism. Compared with DDQP, the design of the DDQP+ algorithm is more reasonable and comprehensive. The experiment results also show that DDQP+ achieved further improvement in multiple performance indicators.

In theory, the capacity of a wireless network grows linearly with the number of users and antennas equipped at the communication devices, and hence large-scale MU-MIMO can scale up the network throughput. However, three main challenges are impeding the implementation of this promising technology in the state-of-the-art WLANs. Firstly, the current large-scale MU-MIMO technology demands a large number of high-priced RF chains. Secondly, the wireless access points (APs) are overwhelmed by channel state information (CSI) feedback for nulling multi-user and -antenna interference. Thirdly, the lack of scalable user selection scheme limits the capability of APs to serve a large user population. To address these problems, we design BUSH, a large-scale MU-MIMO prototype that performs scalable beam user selection with hybrid beamforming for phased-array antennas in legacy WLANs. We design a low complexity algorithm that assigns each pair of RF chain and analog beam to the users to effectively reduce channel correlation and cross-talk interference without instantaneous CSI feedbacks. As a prerequisite of user selection, BUSH presents a low-overhead probing scheme in multi-carrier WLANs and designs a highly accurate blind Power Azimuth Spectrum (PAS) estimation algorithm using a single RF chain. For reducing the number of RF-chains used, the phased-array antennas use analog beamforming to steer beams toward each selected downlink user, and multiple RF chains use beamforming to further mitigate the interference among users. We implement BUSH on a software-defined radio platform and evaluate its performance in more than 30 indoor scenarios. The experimental results reveal that for throughput, BUSH outperforms the legacy 802.11ac by 2.08×, and an alternative benchmark system by 1.22× on average.

Graphlets are induced subgraph patterns that are crucial to the understanding of the structure and function of a large network. A lot of effort has been devoted to calculating graphlet statistics where random walk-based approaches are commonly used to access restricted graphs through the available application programming interfaces (APIs). However, most of them merely consider individual networks while overlooking the strong coupling between different networks. In this article, we estimate the graphlet concentration in multiplex networks with real-world applications. An inter-layer edge connects two nodes in different layers if they actually belong to the same node. The access to a multiplex network is restrictive in the sense that the upper layer allows random walk sampling, whereas the nodes of lower layers can be accessed only through the inter-layer edges and only support random node or edge sampling. To cope with this new challenge, we define a suit of two-layer graphlets and propose novel random walk sampling algorithms to estimate the proportion of all the three-node graphlets. An analytical bound on the sampling steps is proved to guarantee the convergence of our unbiased estimator. We further generalize our algorithm to explore the tradeoff between the estimated accuracy of different graphlets when the sample budget is split into different layers. Experimental evaluation on real-world and synthetic multiplex networks demonstrates the accuracy and high efficiency of our unbiased estimators.

The Information-Centric Networking (ICN) paradigm has emerged to shift the current host-based network model to a content-oriented one in order to cope with the dominant content-based services in the Internet. Congestion control is a fundamental design concern to support massive content delivery in ICN. While the existing flow-based and hop-by-hop congestion control mechanisms suffer from complexity and compatibility issues, we propose RevMax, a gateway-aware congestion control mechanism based on the architecture of NDN, a well-known ICN platform, to overcome the drawbacks. In the proposed mechanism, the gateway offers a price to each end-user, which urges the user to adjust the request rate according to the price. The optimal pricing policy for the gateway is shown to be formulated as a revenue maximization problem, and an efficient algorithm is proposed to derive the optimal solution. The proposed RevMax mechanism is implemented in NDN and compared to PCON, a state-of-the-art congestion control mechanism for ICNs. Extensive experiments show that RevMax achieves higher throughput, lower network latency, and better fairness in a variety of network scenarios.

This paper studies a fundamental problem regarding the security of blockchain on how the existence of multiple misbehaving pools influences the profitability of selfish mining. Each selfish miner maintains a private chain and makes it public opportunistically for the purpose of acquiring more rewards incommensurate to his Hashrate. We establish a novel Markov chain model to characterize all the state transitions of public and private chains. The minimum requirement of Hashrate together with the minimum delay of being profitable is derived in close-form. The former reduces to 21.48% with the symmetric selfish miners, while their competition with asymmetric Hashrate puts forward a higher requirement of the profitable threshold. The profitable delay increases with the decrease of the Hashrate of selfish miners, making the mining pools more cautious on performing selfish mining.

Multiuser MIMO (MU-MIMO) empowers access points (APs) with multiple antennas to transmit multiple data streams concurrently to users by exploiting spatial multiplexing. In MU-MIMO, users need to estimate channel state information (CSI) and report it to APs, thus opening a backdoor to attackers who may forge CSI to eavesdrop the content of victims. In this paper, we explore the eavesdropping attack in a novel and practical context in which CSI forgery entangles MU-MIMO user selection in a many-users regime. The attacker hopes to optimize both the eavesdropping opportunity of being selected with the victim and the corresponding decoding quality. We propose new attack and defense mechanisms: (1) USE Attack that enables attackers to achieve near optimal eavesdropping opportunity and high decoding quality through constructing orthogonal CSI against victims followed by stepwise refinements; (2) AngleSec that exploits channel reciprocity for attacker detection without any modification to legacy CSI feedback in which CSI forgery induces a mismatching of downlink and uplink angular spectra at the AP. We implement and evaluate USE Attack and AngleSec in a software defined radio platform WARPv3. Extensive experiments manifest that USE Attack significantly improves the overall eaves-dropping quality compared with state-of-the-art counterparts and AngleSec is able to detect CSI forgery attackers almost for sure.

The demand for Internet services that require frequent updates through small messages, also known as microblogging, has tremendously grown in the past few years. Although the use of such applications by domestic users is usually free, their access from mobile devices is subject to fees and consumes energy from limited batteries. If a user activates his mobile device and is in the range of a publisher, an update is received at the expense of monetary and energy costs. Thus, users face a tradeoff between such costs and their messages aging. The goal of this paper is to show how to cope with such a tradeoff, by devising aging control policies. An aging control policy consists of deciding, based on the utility of the owned content, whether to activate the mobile device, and if so, which technology to use (WiFi or cellular). We present a model that yields the optimal aging control policy. Our model is based on a Markov Decision Process (MDP) in which states correspond to content ages. Using our model, we show the existence of an optimal strategy in the class of threshold strategies, wherein users activate their mobile devices if the age of their poadcasts surpasses a given threshold and remain inactive otherwise. The accuracy of our model is validated against traces from the UMass DieselNet bus network.

Confronting with the sheer amount of Over-the-Top (OTT) videos, personalized recommendation is especially important for users to locate videos of interest. However, previous approaches seldom considered the influence of watching time when designing video recommendation algorithms. In this paper, we first conduct a detailed measurement study on a leading OTT video service provider in China and our results show that user view preferences are substantially influenced by watching time. Based on the above results, we further propose a personalized time-aware video recommendation algorithm called TAMF for OTT videos. The basic idea of our proposed TAMF algorithm is to utilize matrix factorization to unveil how watching time affects user view interests and cluster time slots with similar influence. In this way, we can collaboratively learn users' personal interests if their views belong to the same cluster, and precisely capture user view preferences with watching time. Finally, we also conduct extensive experiments using real traces to evaluate the performance of our algorithm, and the experimental results show that our proposed algorithm can improve video recommendation performance by 4.83% and 4.42% in terms of WMRR and WMAP respectively and significantly boost user engagement.

Packet routing is one of the fundamental problems in computer networks in which a router determines the next-hop of each packet in the queue to get it as quickly as possible to its destination. Reinforcement learning has been introduced to design the autonomous packet routing policy namely Q-routing only using local information available to each router. However, the curse of dimensionality of Q-routing prohibits the more comprehensive representation of dynamic network states, thus limiting the potential benefit of reinforcement learning. Inspired by recent success of deep reinforcement learning (DRL), we embed deep neural networks in multi-agent Q-routing. Each router possesses an independent neural network that is trained without communicating with its neighbors and makes decision locally. Two multi-agent DRL-enabled routing algorithms are proposed: one simply replaces Q-table of vanilla Q-routing by a deep neural network, and the other further employs extra information including the past actions and the destinations of non-head of line packets. Our simulation manifests that the direct substitution of Q-table by a deep neural network may not yield minimal delivery delays because the neural network does not learn more from the same input. When more information is utilized, adaptive routing policy can converge and significantly reduce the packet delivery time.

The price-anticipating Kelly mechanism (PAKM) is one of the most extensively used strategies to allocate divisible resources for strategic users in communication networks and computing systems. The users are deemed as selfish and also benign, each of which maximizes his individual utility of the allocated resources minus his payment to the network operator. However, in many applications a user can use his payment to reduce the utilities of his opponents, thus playing a misbehaving role. It remains mysterious to what extent the misbehaving user can damage or influence the performance of benign users and the network operator. In this work, we formulate a non-cooperative game consisting of a finite amount of benign users and one misbehaving user. The maliciousness of this misbehaving user is captured by his willingness to pay to trade for unit degradation in the utilities of benign users. The network operator allocates resources to all the users via the price-anticipating Kelly mechanism. We present six important performance metrics with regard to the total utility and the total net utility of benign users, and the revenue of network operator under three different scenarios: with and without the misbehaving user, and the maximum. We quantify the robustness of PAKM against the misbehaving actions by deriving the upper and lower bounds of these metrics. With new approaches, all the theoretical bounds are applicable to an arbitrary population of benign users. Our study reveals two important insights: 1) the performance bounds are very sensitive to the misbehaving user's willingness to pay at certain ranges and 2) the network operator acquires more revenues in the presence of the misbehaving user which might disincentivize his countermeasures against the misbehaving actions.

We are witnessing a surge of efforts in networking community to develop deep neural networks (DNNs) based approaches to networking problems. Most results so far have been remarkably promising, which is arguably surprising given how intensively these problems have been studied before. Despite these promises, there has not been much systematic work to understand the inner workings of these DNNs trained in networking settings, their generalizability in different workloads, and their potential synergy with domain-specific knowledge. The problem of model opacity would eventually impede the adoption of DNN-based solutions in practice. This position paper marks the first attempt to shed light on the interpretability of DNNs used in networking problems. Inspired by recent research in ML towards interpretable ML models, we call upon this community to similarly develop techniques and leverage domain-specific insights to demystify the DNNs trained in networking settings, and ultimately unleash the potential of DNNs in an explainable and reliable way.

We consider a device-to-device (D2D) underlaid cellular network, where each cellular channel can be shared by several D2D pairs and only one channel can be allocated to each D2D pair. We try to maximize the sum rate of D2D pairs while limiting the interference to cellular links. Due to the lack of global information in large scale networks, resource allocation is hard to be implemented in a centralized way. Therefore, we design a novel distributed resource allocation scheme which is based on local information and requires little coordination and communication between D2D pairs. Specifically, we decompose the original problem into two cascaded subproblems, namely channel allocation and power control. The cascaded structure of our scheme enables us to cope with them respectively. Then a two-stage algorithm is proposed. In the first stage, we model the channel allocation problem as a many-to-one matching with externalities and try to find a strongly swap-stable matching. In the second stage, we adopt a pricing mechanism and develop an iterative two-step algorithm to solve the power control problem.

Delivering high-definition (HD) videos to a large number of Internet users is a challenging research problem due to its heavy bandwidth consumption and inelastic quality-of-service (QoS) requirement. Different from the traditional content delivery networks and overlay peer-to-peer networks, crowdsourcing-based platforms, e.g., Thunder Crystal, deliver HD videos by renting agents' bandwidth and storage resources. Cash will be rewarded to agents based on agents' upload traffic. Online video providers, i.e., Tencent Video and YouKu, pay Thunder Crystal for its video distribution service. Therefore, a critical problem for Thunder Crystal is to evaluate the performance it can achieve, which determines Thunder Crystal's competitiveness and its bargaining power with online video providers. Although previously studied proportional video replication and random request scheduling strategy are implemented by Thunder Crystal, the system performance cannot be evaluated by simply using existing models, because of its novel business model. To address this problem, this paper proposes a theoretical framework that can analyze the performance for synchronized streaming, video-on-demand (VoD) streaming, and video downloading, which are all supported by Thunder Crystal. A differentiated bandwidth allocation is designed to boost Thunder Crystal's streaming performance by assigning downloading users more fluctuating bandwidth, which only slightly degrades downloading performance. Finally, simulation is conducted to validate the accuracy of our theoretical results.

Location spoofing and non-line-of-sight (NLOS) propagation are two leading reasons of serious localization errors in wireless networks. Previous studies have managed to identify these two factors separately. However, when present in the same system, these two factors can cause localization errors in a similar manner, making the identification difficult. In this paper, we address the problem of identifying location spoofing in NLOS conditions. We first carry out a geometric analysis on NLOS and derive a bound that can be used to differentiate NLOS from location spoofing. Based on the bound, we propose an identification method. We show that the proposed method is secure against different types of spoofing attacks including those from individuals and from multiple collaborative attackers. In particular, it can be used to identify the well-known “perfect location spoofing.” Simulation in wireless sensor networks indicates that our method can achieve a high accuracy with 0 false positive on identifying individual attacks and perfect location spoofing in NLOS conditions.

Understanding streaming user behavior is crucial to the design of large-scale Video-on-Demand (VoD) systems. In this article, we begin with the measurement of individual viewing behavior from two aspects: the temporal characteristics and user interest. We observe that active users spend more hours on each active day, and their daily request time distribution is more scattered than that of the less active users, while the inter-view time distribution differs negligibly between two groups. The common interest in popular videos and the latest uploaded videos is observed in both groups. We then investigate the predictability of video popularity as a collective user behavior through early views. In the light of the limitations of classical approaches, the Autoregressive-Moving-Average (ARMA) model is employed to forecast the popularity dynamics of individual videos at fine-grained time scales, thus achieving much higher prediction accuracy. When applied to video caching, the ARMA-assisted Least Frequently Used (LFU) algorithm can outperform the Least Recently Used (LRU) by 11--16%, the well-tuned LFU by 6--13%, and the LFU is only 2--4% inferior to the offline LFU in terms of hit ratio.

Owing to great potential in smart home and human-computer interactive applications, WiFi indoor localization has attracted extensive attentions in the past several years. The state-of-the-art systems have successfully achieved decimeter-level accuracies. However, the high accuracy is acquired at the cost of dense access point (AP) deployment, employing large size of frequency bandwidths or special-purpose radar signals which are not compatible with existing WiFi protocol, limiting their practical deployments. This paper presents the design and implementation of AWL, an accurate indoor localization system that enables a single WiFi AP to achieve decimeter-level accuracy with only one channel hopping. The key enabler of the system is we novelly employ channel hopping to create virtual antennas, without the need of adding more antennas or physically move the antennas' positions for a larger antenna array. We successfully utilize the widely known "bad" spatial aliasing to improve the AoA estimation accuracy. A novel multipath suppression scheme is also proposed to combat the severe multipath issue indoors. We build a prototype of AWL on WARP software-defined radio platform. Comprehensive experiments manifest that AWL achieves a median localization accuracy of 38 cm in a rich multipath indoor environment with only a single AP equipped with 6 antennas. In a small scale area, AWL is able to accurately track a moving device's trajectory, enabling applications such as writing/drawing in the air.

Large-scale MU-MIMO is a promising technology to scale network capacity and the capacity gain grows linearly with the numbers of antennas and users in theory. However, its practical deployment faces three critical challenges in the state-of-the-art WLANs: i) the demand of a large number of expensive RF chains; ii) the linear growth of feedback overheads with the number of antennas; iii) the lack of scalable user selection scheme for a large user population. In this paper, we design BUSH, a large-scale MU-MIMO prototype that performs scalable beam user selection with hybrid beamforming for phased-array antennas in legacy WLANs. The architecture of BUSH consists of three components. Firstly, a low complexity algorithm assigns each pair of RF chain and analog beam to the users to effectively reduce channel correlation and cross-talk interference without instantaneous CSI feedbacks. Secondly, as a prerequisite of user selection, BUSH presents a low-overhead probing scheme in multi-carrier WLANs, and designs a highly accurate blind Power Azimuth Spectrum (PAS) estimation algorithm using a single RF chain. Thirdly, the phased-array antennas use analog beamforming to steer spatial beams toward each selected downlink user, and the finite number of RF chains use beamforming to further mitigate the interference among users. We implement BUSH on the WARPv3 boards and evaluate its performance in more than 30 indoor scenarios. The experimental results show that in terms of total throughput BUSH outperforms the legacy 802.11ac by 2.08×, and an alternative benchmark system by 1.22× on average.

Understanding streaming user behavior is crucial to the design of large-scale video-on-demand (VoD) systems. However, existing studies usually treat all the users as an entire entity to analyze the collective user behavior. In this paper, we measure the individual viewing behavior of 10 million sampled users from two perspectives: the temporal characteristics and the user interest, and present our results by dividing users into the active and inactive groups. We observe that the active users spend more hours on each active day, and their daily request time distribution is more scattered than that of the inactive users, while the inter-viewing time distribution differs negligible between two groups. We exhibit the similar viewing behaviors of the active and inactive users, e.g. the common interests in popular videos and the latest uploaded videos. We further propose a modified Weibull distribution to fit users' view completion rate, which can deal with different video categories well. To identify users with similar viewing behaviors, we cluster them into 24 classes using their daily request timestamp or 11 classes using the watched video category. The analysis of cluster centroid manifests the efficacy of the clustering, which enables us to step closer to the understanding of user behavior in large-scale VoD systems.

Unraveling quality of experience (QoE) of video streaming is very challenging in bandwidth shared wireless networks. It is unclear how QoE metrics such as starvation probability and buffering time interact with dynamics of streaming traffic load. In this paper, we collect view records from one of the largest streaming providers in China over two weeks and perform an in-depth measurement study on flow arrival and viewing time that shed light on the real traffic pattern. Our most important observation is that the viewing time of streaming users fits a hyper-exponential distribution quite well. This implies that all the views can be categorized into two classes, short and long views with separated time scales. We then map the measured traffic pattern to bandwidth shared cellular networks and propose an analytical framework to compute the closed-form starvation probability on the basis of ordinary differential equations (ODEs). Our framework can be naturally extended to investigate practical issues including the progressive downloading and the finite video duration. Extensive trace-driven simulations validate the accuracy of our models. Our study reveals that the starvation metrics of the short and long views possess different sensitivities to the scheduling priority at base station (BS). Hence, a better QoE tradeoff between the short and long views has a potential to be leveraged by offering them different scheduling weights. The flow differentiation involves tremendous technical and non-technical challenges because video content is owned by content providers but not the network operators and the viewing time of each session is unknown beforehand. To overcome these difficulties, we propose an online Bayesian approach to infer the viewing time of each incoming flow with the “least” information from content providers.

Multiview video is essential for various mobile three-dimensional (3D) and immersive applications that can capture scenes from multiple angles for better user experience. However, robust transmission of multiview video is very challenging in wireless networks due to high bandwidth requirement and time-varying channel quality. Though the up-to-date 802.11 system enables spatial multiplexing MIMO to enhance transmission capacity, it is still agnostic to 3D source coding structure in the transmission. In this paper, we study the optimal resource allocation problem in MIMO systems that deliver 3D content with multiview video coding. The basic idea is to exploit the channel diversity of multiple antennas and the source coding characteristics so as to achieve unequal error protection against channel errors. To achieve this goal, we develop a nonlinear mixed integer programming framework to perform antenna selection and power allocation, and propose low-complexity algorithms to assign these resources. We implement a proof-of-concept system, namely MuVi, on the software-defined-radio platform, WARP, to evaluate the proposed algorithms. MuVi is the practical system to tackle 3D multiview streaming in the latest Wi-Fi networks such as IEEE 802.11ac under realistic channel conditions. Extensive experimental results demonstrate that the peak signal-to-noise-ratio of MuVi significantly outperforms that of the conventional power allocation scheme in a variety of indoor environments.

Multi-view video streaming is essential for various mobile 3D and immersive applications that can capture the same scene from multiple angles. However, the large traffic volume of multi-view streaming will drain the battery power quickly. This paper studies the power efficient delivery of 3D content with multi-view video coding (MVC) in the emerging 802.11-like MIMO wireless systems, and the purpose is to minimize the power consumption with the video quality guarantee. We propose an efficient algorithm to perform antenna assignment and transmission power allocation, by exploiting both the source coding characteristics of MVC and channel diversity of multiple antennas. A proof-of-concept system, namely PoM, is designed on the software radio platform and is evaluated in realistic indoor environments. To the best of our knowledge, this is the first practical system for energy efficient multi-view video streaming. Experimental results show that PoM can significantly save energy in the transmission by 12% ~ 65% on average when the required PSNR decreases from 45dB to 35dB.

The explosion of mobile video traffic imposes tremendous challenges on present cellular networks. To alleviate the pressure on backhaul links and to enhance the quality of experience (QoE) of video streaming service, small cell base stations (SBS) with caching ability are introduced to assist the content delivery. In this paper, we present the first study on the optimal caching strategy of scalable video coding (SVC) streaming in small cell networks with the consideration of channel diversity and video scalability. We formulate an integer programming problem to maximize the average subjective quality of SVC streaming under the constraint of cache size at each SBS. By establishing connections between subjective quality and caching state of each video, we simplify the proactive caching of SVC as a multiple-choice knapsack problem (MCKP), and propose a low-complexity algorithm using dynamic programming. Our proactive caching strategy reveals the structural properties of cache allocation to each video based on their popularity profiles. Simulation results manifest that the SBSs with caching ability can greatly improve the average quality of SVC streaming, and that our proposed caching strategy acquires significant performance gain compared with other conventional caching policies.

The device-to-device (D2D) communication theoretically provides both the cellular traffic offloading and convenient content delivery directly among proximity users. However, in practice, no matter in underlay or overlay mode, the employment of D2D may impair the performance of the cellular links. Therefore, it is important to design a spectrum sharing scheme, under which the performance of both links can be improved simultaneously. In this paper, we consider the cell-edge user (CEU) scenario, where both sides have the demand to improve the quality of experience or service. Therefore, CEUs and D2D users both have intentions to form pairs, namely, CEU-D2D pairs, to cooperate mutually. Different from the conventional equilibrium point evaluation, the stable matching between D2D users and CEUs are formulated under matching theory framework instead. For each CEU-D2D pair, a two-stage pricing-based Stackelberg game is modeled to describe the willingness to cooperate, where the win-win goal is reached finally.

In this paper, we consider the scenario of the mobile network operator (MNO) incentivizing femtocell access points (FAPs) to form a shared network. We propose an incentive mechanism under which the licensed femtocell user (FU) of each FAP can use a portion of another FAP's spectrum resources when moving into that FAP's coverage. The FAPs are rewarded based on both the amount of provided resources and the quality of service (QoS). We formulate the problem as a Stackelberg game. The MNO acts as the leader to decide incentive price. When observing the price, each FAP decides the amount of provided resources according to its type information (resource constraint, QoS and especially its licensed FU's mobility pattern). The best response functions of FAPs are first obtained and the existence of the Nash Equilibrium (NE) is investigated. And then we investigate the optimal strategy of the MNO given the FAPs' strategies. Simulation results show that the proposed mechanism can effectively motivate FAPs to share their resources with each other. We will also mainly analyze the influence of FUs' mobility patterns on their adopted strategies.

The Quality of Experience (QoE) of streaming service is often degraded by frequent playback interruptions. To mitigate the interruptions, the media player prefetches streaming contents before starting playback, at a cost of initial delay. We study the QoE of streaming from the perspective of flow dynamics. First, a framework is developed for QoE when streaming users join the network randomly and leave after downloading completion. We model the distribution of prefetching delay using partial differential equations (PDEs), and the probability generating function of playout buffer starvations using ordinary differential equations (ODEs) for constant bit-rate (CBR) streaming. The explicit form starvation probabilities and mean start-up delay are obtained by use of a matrix function approach. Second, we extend our framework to characterize the throughput variation caused by opportunistic scheduling at the base station, and the playback variation of variable bit-rate (VBR) streaming. Our study reveals that the flow dynamics is the fundamental reason of playback starvation. The QoE of streaming service is dominated by the first moments such as the average throughput of opportunistic scheduling and the mean playback rate. While the variances of throughput and playback rate have very limited impact on starvation behavior in practice.

In today WSNs, sensor nodes are able to obtain energy from ambient with energy-harvesting components. However, the energy consumption are diverse across these nodes due to functional or geographical variation, which may lead to potential energy imbalance in network. In virtue of recent wireless power transfer (WPT) technology, the imbalance can be alleviated if all sensor nodes share energy with each other. In order to achieve the maximum energetically sustainable workload, we design an energy cooperation strategy in network by WPT, named energy routing, which should be jointly optimized with data routing simultaneously. An iterative distributed algorithm is developed to achieve the optimal data routing and energy routing solutions, where all sensors only need to exchange local information with neighbors. Simulation results show that the proposed algorithm can achieve higher workload than algorithms without energy cooperation.

Unraveling quality of experience (QoE) of video streaming is very challenging in bandwidth shared wireless networks. It is unclear how QoE metrics such as buffering time and starvation behavior interact with dynamics of streaming traffic load. In this paper, we collect view records from one of the largest streaming providers in China over two weeks and perform an in-depth measurement study on flow arrival and viewing time that shed light on realistic streaming traffic pattern. Our most important observation is that the viewing time of streaming users fits a hyper-exponential distribution quite well. This implies that all the videos can be categorized into two classes, short and long viewing time with separated time scales. We then map the traffic pattern of large-scale measurement to bandwidth sharing cellular networks. We propose two models to compute the close-form starvation probability and mean sojourn time on the basis of ordinary differential equations (ODEs). Extensive trace-driven simulations validate their accuracy. The proposed models precisely capture how the QoE metrics of video streaming in each class are influenced by the scheduling algorithms at a base station.

Cloud gaming has become a new trend for gamers to access high-end video games. By rendering games in the remote cloud and streaming video scenes to the users, games can be played anywhere, anytime, on any device (e.g., smartphones, tablets, or personal computers). In this paper, we address the problem of achieving cost-effective adaptive cloud gaming in geo-distributed data centers from the perspective of cloud gaming service providers (CGSPs). Unlike previous work, we consider a cloud gaming system supported with the adaptive streaming technology. Our purpose is to minimize the overall service cost for CGSPs, by adaptively adjusting the selection of data centers, virtual machine allocation and video bitrate configuration for each user. Meanwhile, we also need to ensure good-enough quality of experience (QoE) for gamers. To this objective, we formulate the problem into a constrained stochastic optimization problem, and apply the Lyapunov optimization theory to drive the corresponding online strategy with provable upper bounds. Due to the diverse QoE requirements of video games, we also take the difference among game genres into account during the algorithm design. Finally, we conduct extensive trace-driven simulations to evaluate the effectiveness of our algorithm and our results show that our proposed algorithm can achieve significant gain over other alternative approaches.

Currently, video-on-demand (VoD) streaming over Internet is a popular application. Because of the rapidly growing video population and user population, how to maintain high user quality of experience (QoE) with low cost is a challenging problem for Internet video streaming providers. A promising technique to potentially benefit VoD streaming system is network coding. A number of recent works studied how to use network coding to simplify chunk scheduling strategy to enhance VoD streaming performance. Most of these works only covered extreme cases of pure coding or pure chunk scheduling, emphasizing implementation, and experimentation in peer-to-peer (P2P) scenario without analytically evaluating the realizable performance gains explicitly. In this paper we discuss the strength and weakness of a family of coding strategies for CDN-based VoD streaming systems. The coding schemes are characterized by block sizes while the chunk scheduling strategy is characterized by the order to download chunks. Both pure coding strategy and pure chunk scheduling strategy are special cases of this family of strategies. We then propose a model to evaluate the benefits brought by each strategy. Basically, the coding scheme with larger block size gives more streaming and scheduling benefits with the cost of heavier overheads (e.g., encoding and decoding). System designers can take advantage of our model to balance the tradeoff between coding gain and coding overheads.

Video streaming service in wireless networks is increasingly using dynamic selection of video bit-rates to provide a high quality of user experience (QoE). The bit-rate switching mechanism, performed at client side, plays a key role in determining QoE metrics. In this paper, we present the first analytical framework to compute starvation probability of playout buffer, continuous playback time and mean video quality, given the bit-rate switching logics. Wireless channel is modeled as a continuous time Markov process, and playout buffer is modeled as a fluid queue with Markov modulated fluid arrival. We construct a set of ordinary differential equations (ODEs) to characterize the dynamics of starvation probability and expected continuous playback time with regard to buffer length, and simple models to analyze mean bit-rate for different bit-rate switching algorithms. Our framework is very general in that by adding appropriate parameters, it can be utilized to predict the QoE metrics of dynamic adaptive streaming with a variety of features: i) buffer-aware bit-rate switching ii) (im)patience of the user, and iii) receiver-side flow control.

Our purpose in this paper is to characterize buffer starvations for streaming services. The buffer is modeled as a FIFO queue with exponential service time and Poisson arrivals. When the buffer is empty, the service restarts after a certain amount of packets are prefetched. With this goal, we propose two approaches to obtain exact distribution of the number of buffer starvations, one of which is based on Ballot theorem, and the other uses recursive equations. The Ballot theorem approach gives an explicit result. We extend this approach to the scenario with a constant playback rate using Tàkacs Ballot theorem. The recursive approach, though not offering an explicit result, allows us to obtain the distribution of starvations with non-independent and identically distributed (i.i.d.) arrival process in which an ON/OFF bursty arrival process is considered. We further compute the starvation probability as a function of the amount of prefetched packets for a large number of files via a fluid analysis. Among many potential applications of starvation analysis, we show how to apply it to optimize objective quality of experience (QoE) of media streaming, by exploiting the tradeoff between startup/rebuffering delay and starvations.

The Quality of Experience (QoE) of streaming service is often degraded by frequent playback interruptions. To mitigate the interruptions, the media player prefetches streaming contents before starting playback, at a cost of delay. We study the QoE of streaming from the perspective of flow dynamics. First, a framework is developed for QoE when streaming users join the network randomly and leave after downloading completion. We compute the distribution of prefetching delay using partial differential equations (PDEs), and the probability generating function of playout buffer starvations using ordinary differential equations (ODEs). Second, we extend our framework to characterize the throughput variation caused by opportunistic scheduling at the base station in the presence of fast fading. Our study reveals that the flow dynamics is the fundamental reason of playback starvation. The QoE of streaming service is dominated by the average throughput of opportunistic scheduling, while the variance of throughput has very limited impact on starvation behavior.

The paper has two objectives. The first is to study rigorously the transient behavior of some peer-to-peer (P2P) networks whenever information is replicated and disseminated according to epidemic-like dynamics. The second is to use the insight gained from the previous analysis in order to predict how efficient are measures taken against P2P networks. We first introduce a stochastic model that extends a classical epidemic model and characterize the P2P swarm behavior in presence of free-riding peers. We then study a second model in which a peer initiates a contact with another peer chosen randomly. In both cases, the network is shown to exhibit phase transitions: A small change in the parameters causes a large change in the behavior of the network. We show, in particular, how phase transitions affect measures of content providers against P2P networks that distribute nonauthorized music, books, or articles and what is the efficiency of countermeasures. In addition, our analytical framework can be generalized to characterize the heterogeneity of cooperative peers.

Our purpose in this paper is to obtain the exact distribution of the number of buffer starvations within a sequence of N consecutive packet arrivals. The buffer is modeled as an M/M/1 queue. When the buffer is empty, the service restarts after a certain amount of packets are prefetched. With this goal, we propose two approaches, one of which is based on Ballot theorem, and the other uses recursive equations. The Ballot theorem approach gives an explicit solution, but at the cost of the high complexity order in certain circumstances. The recursive approach, though not offering an explicit result, needs fewer computations. We further propose a fluid analysis of starvation probability on the file level, given the distribution of file size and the traffic intensity. The starvation probabilities of this paper have many potential applications. We apply them to optimize the quality of experience (QoE) of media streaming service, by exploiting the tradeoff between the start-up delay and the starvation.

The paper has two objectives. The first is to study rigorously the transient behavior of some peer-to-peer (P2P) networks whenever information is replicated and disseminated according to epidemic-like dynamics. The second is to use the insight gained from the previous analysis in order to predict how efficient are measures taken against P2P networks. We first introduce a stochastic model which extends a classical epidemic model, and characterize the P2P swarm behavior in presence of free riding peers. We then study a second model in which a peer initiates a contact with another peer chosen randomly. In both cases the network is shown to exhibit phase transitions: a small change in the parameters causes a large change in the behavior of the network. We show, in particular, how phase transitions affect measures of content providers against P2P networks that distribute non-authorized music or books, and what is the efficiency of counter-measures.

Threshold channel quality index (CQI) feedback helps to achieve a high throughput at a low cost of overhead in multi-carrier systems that have saturated downlink traffic. However, when system is not saturated, the performance will degrade tremendously. In this work we build mathematical model to analyze the phenomenon. We then design traffic-aware threshold CQI feedback schemes to improve feedback efficiency. To further enhance system performance such as fairness, the product of data rate and queue length is applied to determine CQI feedback threshold and BS scheduling. Extensive simulation proves that the proposed scheme leads to a improved throughput and decent fairness in non-saturated systems.