This paper presents a practical online active learning solution for adaptive channel estimation in fluid antenna systems. We model channel state information (CSI) as a spatiotemporal Gaussian process (GP) and approximate it using a deep dropout neural network (DDNN), transforming the challenge into a deep learning task. By leveraging the expressive power of neural networks, our GP model effectively captures the spatiotemporal characteristics of CSI, thereby reducing the number of ports required for accurate estimation. The DDNN, characterized by its low complexity and ease of training, employs a least-squares loss function based solely on port information and pilot measurements, eliminating the need for true CSI. This facilitates dynamic updates and allows for effective adaptation to environmental changes. Additionally, our solution incorporates a port selection method that maximizes mutual information, focusing on prediction uncertainty to optimize port usage. Simulation results demonstrate that our proposed online active learning method significantly outperforms state-of-the-art solutions in CSI estimation accuracy and exhibits robust adaptability in dynamic environments.

Network traffic forecasting is crucial for dynamic resource allocation and network management. However, real-time network traffic forecasting in real-world scenarios is challenging due to the limitation of incomplete data. In this paper, we propose a masked generative model (MGM) for real-time network traffic forecasting from incomplete data. Firstly, we formulate the forecasting task as a low-tubal-rank tensor completion problem and verify that generative models can produce low-tubal-rank tensors through low-dimensional latent variables. Secondly, we propose MGM, which adapts masked autoencoders to robustly learn latent variables from incomplete traffic data. The variables are then mapped to complete low-tubal-rank traffic tensors through pretrained generative models for real-time forecasting. We also establish a performance guarantee that quantifies the error bound of the proposed approach. Finally, experiments on real-world datasets demonstrate that our approach achieves accurate network traffic forecasting within 100 ms, with a normalized root mean squared error (NRMSE) below 0.1.

The rapid proliferation of mobile devices within Internet of Things (IoT) has substantially heightened the demand for mobile edge computing (MEC). Fog computing (FC) is a more advanced form of edge computing that allows computing nodes to cooperate with each other. Reconfigurable intelligent surfaces (RIS) have emerged as a critical technology for optimizing wireless communication environments, attracting considerable attention. In this paper, we develop an online optimization problem for RIS-aided mobile FC deployed across wireless networks with computing nodes at the base stations (BS). We propose a Lyapunov-drift-plus-penalty-based, space aggregation-assisted proximal policy optimization (LSAPPO) algorithm to tackle the challenges in online optimization problem in RIS-aided mobile FC system. Our technique integrates a reinforcement learning (RL) algorithm employing the proximal policy optimization (PPO) agent, further enhanced by Lyapunov drift-plus-penalty optimization. The space aggregation technique effectively consolidates excessive decision variables and channel state information (CSI) into a manageable set of parameters to streamline the computing framework. Numerical simulation result shows that our proposed algorithm surpasses the benchmarks, underscoring the effectiveness in complicated wireless networks. Furthermore, we introduce the multi-agent LSAPPO algorithm to address the distributed demands of practical scenarios. The multi-agent LSAPPO algorithm enhances convergence speed and performs better in large-scale problems.

To realize orthogonal frequency division multiplexing (OFDM)-based grant-free access for wideband systems under frequency-selective fading, existing device activity detection and channel estimation methods need substantial accuracy improvement or computation time reduction. In this paper, we aim to resolve this issue. First, we present an exact time-domain signal model for OFDM-based grant-free access under frequency-selective fading. Then, we present a maximum a posteriori (MAP)-based device activity detection problem and two minimum mean square error (MMSE)-based channel estimation problems. The MAP-based device activity detection problem and one of the MMSE-based channel estimation problems are formulated for the first time. Next, we build a new factor graph that captures the exact statistics of time-domain channels and device activities. Based on it, we propose two approximate message passing (AMP)-based algorithms,AMP-A-ECandAMP-A-AC, to approximately solve the MAP-based device activity detection problem and two MMSE-based channel estimation problems. Both proposed algorithms alleviate the AMP’s inherent convergence problem when the pilot length is smaller or comparable to the number of active devices. Then, we analyzeAMP-A-EC’s error probability of activity detection and mean square error (MSE) of channel estimation via state evolution and show thatAMP-A-AChas the lower computational complexity (in dominant term). Finally, numerical results show the two proposed AMP-based algorithms’ superior performance and respective preferable regions, revealing their significant values for OFDM-based grant-free access.

This paper investigates resource allocation for providing heterogeneous users with customized virtual reality (VR) streaming services in a mobile edge computing (MEC) system. We introduce a quality of experience (QoE) metric that considers system latency, user attention levels, and preferred resolutions to measure user experience based on the Weber-Fechner Law. A QoE maximization problem is then formulated for resource allocation to optimize user experience. It is cast as a reinforcement learning problem, aiming to learn a generalized policy applicable across diverse user environments of different MEC servers. To solve the problem, we propose a FedPromptDT framework, which employs federated learning (FL) and prompt-based generative sequence modeling to pre-train a common decision model across MEC servers. FL addresses the issue of insufficient local MEC data while protecting user privacy during offline training. Meanwhile, by integrating user-environment cues and user-preferred allocation, the design of prompts enhances the model’s adaptability to various user environments during online execution. Extensive experimental evaluations demonstrate that FedPromptDT outperforms baseline methods, exhibiting remarkable adaptability and maintaining superior performance across various user environments.

Existing primal decomposition algorithms for nonconvex problems cannot handle nonlinear equality constraints and do not fully exploit the original primal decomposition structures, limiting their effectiveness and efficiency. To address these limitations, we propose a new primal decomposition method and a new primal decomposition algorithm for a nonconvex problem with coupling variables in nonconvex inequality and nonlinear equality constraints. Specifically, they remove the dependence on the subproblems’ globally optimal points and the master problem’s convexity, successfully generalizing the classic ones for convex problems to nonconvex problems. Besides, the proposed primal decomposition algorithm allows parallel and distributed implementations and is shown to converge to the stationary points of the original nonconvex problem. We also customize the proposed primal decomposition algorithm for a new optimal Zero-Forcing (ZF) transmit and receive beamforming problem, which is more general and challenging than the existing ZF transmit beamforming problem. Numerical results demonstrate the superior advantages of the proposed primal decomposition algorithm.

In this paper, we propose a Bayesian Reinforcement Learning (BRL)-based CSI feedback, beamforming, and IRS control scheme for IRS-assisted massive MIMO-OFDM systems. Firstly, the proposed approach utilizes the equivalent CSI for optimization, aligning with current channel estimation protocols without necessitating extensive modifications. Secondly, it employs a practical IRS control model that optimizes the effective capacitance of IRS control circuits rather than IRS reflection coefficients, accurately reflecting the IRS's frequencyresponsive behavior to enhance system performance. Additionally, we advocate bypassing the reconstruction of the CSI at the BS to eliminate information irrelevant to beamforming and IRS control, thereby boosting feedback efficiency. Simulation results demonstrate that the proposed IRS-CSI-BRL scheme significantly outperforms start-of-the-art solutions in feedback overhead reduction and system data rate enhancement.

Network latency estimation plays a critical role in network performance monitoring and management. However, with the escalating demand for real-time performance monitoring and rapid network adjustments in contemporary networks, existing latency estimation methodologies fall short in meeting the needs for instantaneous estimation. In this paper, we propose a generative matrix completion (GMC) scheme for real-time network latency estimation. First, we employ a novel matrix completion framework that leverages a pre-trained generative model as a structural proxy to capture the latency matrix lowrankness. The pre-trained generative model well learns the lowrank characteristics of latency matrices in the pre-training stage, and can map a condensed latent representation to the matrix space for instantaneous matrix completion. Secondly, we propose two tailored training strategies for the generative models to adapt to the diverse low-rank patterns observed in network latency data. Thirdly, to further expedite the estimation, a learned update rule is implemented to hasten the discovery of a suitable latent representation, culminating in the development of the GMC scheme. We also provide a theoretical recovery guarantee to reveal the error bound of GMC. Experimental results on real-world datasets show that the proposed scheme can achieve accurate latency estimation within 50 ms, while maintaining the relative square error of estimation at no more than 0.11 (as evidenced using the PlanetLab dataset).

The rapid expansion of multi-user virtual reality (VR) applications, such as VR gaming and the Metaverse, has heightened the demand for bandwidth-efficient, immersive experiences. This paper introduces a customized Quality of Experience (QoE) framework tailored to VR interactions in a sub-6 GHz communication environment, integrating attention-based interaction, keyframe extraction, and principles from the Weber-Fechner Law. The QoE maximization problem is formulated as a Mixed Integer Programming (MIP) problem that jointly optimizes keyframe extraction ratio and resource allocation (i.e., bandwidth and CPU frequency), incorporating fairness. We employ the Deep Deterministic Policy Gradient (DDPG) algorithm as a reinforcement learning strategy. Evaluation with the Motion Capture Database demonstrates that our framework significantly reduces interactive latency, enhances QoE, and maintains fairness, achieving superior performance compared to baseline methods.

Cued Speech (CS) is a visual communication system that combines lip-reading with hand coding to facilitate communication for individuals with hearing impairments. Automatic CS Recognition (ACSR) aims to convert CS hand gestures and lip movements into text via AI-driven methods. Traditionally, the temporal asynchrony between hand and lip movements requires the design of complex modules to facilitate effective multimodal fusion. However, constrained by limited data availability, current methods demonstrate insufficient capacity for adequately training these fusion mechanisms, resulting in suboptimal performance. Recently, multi-agent systems have shown promising capabilities in handling complex tasks with limited data availability. To this end, we propose the first collaborative multi-agent system for ACSR, named Cued-Agent. It integrates four specialized sub-agents: a Multimodal Large Language Model-based Hand Recognition agent that employs keyframe screening and CS expert prompt strategies to decode hand movements, a pretrained Transformer-based Lip Recognition agent that extracts lip features from the input video, a Hand Prompt Decoding agent that dynamically integrates hand prompts with lip features during inference in a training-free manner, and a Self-Correction Phoneme-to-Word agent that enables post-processing and end-to-end conversion from phoneme sequences to natural language sentences for the first time through semantic refinement. To support this study, we expand the existing Mandarin CS dataset by collecting data from eight hearing-impaired cuers, establishing a mixed dataset of fourteen subjects. Extensive experiments demonstrate that our Cued-Agent performs superbly in both normal and hearing-impaired scenarios compared with state-of-the-art methods. The implementation is available at https://github.com/DennisHgj/Cued-Agent.

Network latency estimation is critical for network performance monitoring and management. However, with the escalating demand for real-time performance monitoring and rapid network adjustments in contemporary networks, existing latency estimation methodologies fall short of meeting the need for instantaneous estimation. In this article, we propose a pretrained generative model-based scheme (PGM) for real-time network latency estimation. PGM operates in two stages. First, we employ a pretrained generative model to relax the low-rank constraint typically associated with latency matrix completion (MC). The pretrained generative model well learns the low-rank characteristics of latency matrices in the pretraining stage and can map a condensed latent representation to the matrix space. Second, instead of directly optimizing the matrix, we turn to optimizing the latent representation. Leveraging the low-rank structure achieved by the pretrained generative model simplifies our optimization process, enabling real-time estimation. We also provide a theoretical recovery guarantee to reveal the error bound of PGM. Experimental results on real-world datasets show that the proposed scheme can achieve accurate latency estimation within 50 ms while maintaining the relative squared error (RSE) of estimation at no more than 0.11 (as evidenced using the PlanetLab dataset).

In Intelligent Reflecting Surface (IRS)-assisted massive Multiple-Input Multiple-Output (MIMO) systems, the downlink channel state information (CSI) needs to be fed back to the base station (BS) and utilized to perform the beamforming and IRS control for high spectral efficiency performance. However, the intricate nature of these systems, characterized by a vast number of antennas, subcarriers, and IRS elements, exacerbates the CSI feedback overhead and complicates the optimization of beamforming and IRS parameters, potentially compromising spectral efficiency. Addressing these challenges, this paper introduces a Bayesian Reinforcement Learning (BRL)-based approach, named IRS-CSI-BRL, for efficient CSI feedback, beamforming, and IRS control. Firstly, the IRS-CSI-BRL approach utilizes the equivalent CSI for optimization, aligning with current channel estimation protocols without necessitating extensive modifications. Secondly, it employs a practical IRS control model that optimizes the effective capacitance of IRS control circuits rather than IRS reflection coefficients, accurately reflecting the IRS’s frequency-responsive behavior to enhance system performance. Additionally, we advocate bypassing the reconstruction of the CSI at the BS to eliminate information irrelevant to beamforming and IRS control, thereby boosting feedback efficiency. Another distinctive feature of the proposed scheme is that its output format is probability distributions, which enables the incorporation of model-assisted knowledge about the latent space and boosts the algorithm’s robustness. Simulation results demonstrate that the proposed IRS-CSI-BRL scheme significantly outperforms start-of-the-art solutions in feedback overhead reduction and system data rate enhancement while maintaining exceptional robustness. Furthermore, this approach maintains flexibility, allowing for the incorporation of an additional training loss function for full CSI reconstruction if needed.

In this paper, we investigate multi-resolution model compression for deep neural networks (DNNs) from a Bayesian perspective. By considering the DNN models with channel masks and proposing a resolution likelihood as well as a two-layer sparse prior for the channel masks, we formulate the multi-resolution model compression as a Bayesian inference problem. To solve this problem, we propose a partial update block variational Bayesian inference (PUB- VBI) algorithm which can infer an approximate posterior for the intractable true posterior. The variational posterior and the updating rules are carefully designed such that the proposed algorithm has a low complexity. Simulation results demonstrate that our proposed method can outperform the baselines on various neural network models and datasets.

With huge amounts of data generated from Internet of Things (IoT) devices, data-driven technologies are increasingly applied by firms to improve their IoT-based services in real time. To facilitate efficient utilization of the collected data, the design of data trading markets becomes crucial. Two important practical concerns are: 1) the data buyers arrive in a sequential and arbitrary manner and 2) a firm faces externalities when data is purchased by competing firms. In this article, we design a data trading marketplace for data buyers arriving dynamically in real time where the early arrived data buyers will exert negative externalities on the late arrivals within the same competition. Specifically, in market operations, when a data buyer arrives, it needs to submit a bid based on the price and the current externalities posted by the market operator. After receiving the bid, the market operator will announce the data allocation and payment as well as update the price. To construct the detailed market mechanism, we propose the allocation rule, payment rule, and price update method, which can be proven theoretically to guarantee the desirable properties, including incentive compatibility, individual rationality, revenue maximization, and computation efficiency. These theoretical conclusions are also validated via our numerical experiments.

Although deep neural networks (DNNs) have been remarkably successful in numerous areas, the performance of DNN is compromised in federated learning (FL) scenarios because of the large model size. A large model can induce huge communication overhead during the federated training, and also induce infeasible storage and computation burden at the clients during the inference. To address these issues, we investigate structured model compression in FL to construct sparse models with regular structure such that they require significantly less communication, storage and computation resources. We do this by proposing a three-layer hierarchical prior, which can promote a common regular sparse structure in the local models. We design a decentralized Turbo variational Bayesian inference (D-Turbo-VBI) algorithm to solve the resulting federated training problem. With the common regular sparse structure, both upstream and downstream communication overhead can be reduced, and the final model also has a regular sparse structure, which requires significantly less local storage and computation resources. Simulation results demonstrate that our proposed algorithm can efficiently reduce the communication overhead during federated training and the resulting model can achieve a significantly lower sparsity rate and inference time compared to the baselines while maintaining a competitive accuracy.

Due to the massive computing demands of the Internet of Things, mobile edge computing (MEC) has been extensively investigated as a means of providing computation-intensive and latency-sensitive services at the network edge. With increasing density of base stations (BSs), users are simultaneously served by multiple BSs, leading to the multicell MEC environment. Intelligent reflecting surface (IRS) provides a promising solution for constructing the virtual Line-of-Sight (LoS) links between cell-edge users (CEUs) and BSs. In this article, we investigate the joint channel estimation and resource allocation in the IRS-aided multicell MEC system. Instead of assuming the perfect channel state information (CSI), we propose a three-phase channel estimation method to obtain the CSI. Our purpose is to minimize the total joint energy and latency cost (JELC) in terms of both task-execution latency and energy consumption in the IRS-aided multicell MEC problem by jointly optimizing the task offloading volume, precoding matrix, and IRS phase shifts. We propose a quadratically constrained program (QCP)-assisted proximal policy optimization (PPO) reinforcement learning algorithm with two modules (i.e., QCP optimizer and PPO agent) execute iteratively. The QCP optimizer is utilized to compute the offloading decision variables, and the PPO agent is adapted to determine the optimal channel precoding matrix and the phase shifts of IRS. Numerical results validate that our QCP-assisted PPO algorithm executes more rapidly than benchmarks. Moreover, the proposed QCP-assisted PPO algorithm delivers the best performance compared to benchmarks. Furthermore, the multicell IRS-aided MEC framework yields additional performance gains compared to those without IRS.

Due to the influence of stochastic gradients, the existing algorithms suffer from slow convergence, noise explosion, and even failure to converge in practice, which motivates us to propose an accelerated algorithm to tackle these issues. Recognizing the potential of gradient, momentum, and conjugate gradient as promising search directions, we propose a 3-D acceleration algorithm, which uses a weighted combination of these three basis. Specifically, in order to analyze the dynamics of the discrete-time algorithm during the update process, we provide a general framework for approximating the discrete-time algorithm in the weak sense by a continuous-time stochastic differential equation. We exploit the continuous-time formulation together with Lyapunov drift optimization to derive novel adaptive step sizes, which effectively improve the performance of the algorithm in stabilizing noise and accelerating convergence. Extensive numerical experiments demonstrate the proposed algorithm’s superiority in convergence rate, computation complexity, and noise robustness compared to state-of-the-art baselines.

Model averaging is a widely adopted technique in federated learning (FL) that aggregates multiple client models to obtain a global model. Remarkably, model averaging in FL yields a superior global model, even when client models are trained with non-convex objective functions and on heterogeneous local datasets. However, the rationale behind its success remains poorly understood. To shed light on this issue, we first visualize the loss landscape of FL over client and global models to illustrate their geometric properties. The visualization shows that the client models encompass the global model within a common basin, and interestingly, the global model may deviate from the basin's center while still outperforming the client models. To gain further insights into model averaging in FL, we decompose the expected loss of the global model into five factors related to the client models. Specifically, our analysis reveals that the global model loss after early training mainly arises fromi)the client model's loss on non-overlapping data between client datasets and the global dataset andii)the maximum distance between the global and client models. Based on the findings from our loss landscape visualization and loss decomposition, we propose utilizing iterative moving averaging (IMA) on the global model at the late training phase to reduce its deviation from the expected minimum, while constraining client exploration to limit the maximum distance between the global and client models. Our experiments demonstrate that incorporating IMA into existing FL methods significantly improves their accuracy and training speed on various heterogeneous data setups of benchmark datasets. Code is available athttps://github.com/TailinZhou/FedIMA.

Federated learning allows multiple clients to collaboratively train a model without exchanging their data, thus preserving data privacy. Unfortunately, it suffers significant performance degradation due to heterogeneous data at clients. Common solutions involve designing an auxiliary loss to regularize weight divergence or feature inconsistency during local training. However, we discover that these approaches fall short of the expected performance because they ignore the existence of avicious cyclebetween feature inconsistency and classifier divergence across clients. Thisvicious cyclecauses client models to be updated in inconsistent feature spaces with more diverged classifiers. To break thevicious cycle, we propose a novel framework namedFederated learning withFeatureAnchors(FedFA). FedFA utilizes feature anchors to align features and calibrate classifiers across clients simultaneously. This enables client models to be updated in a shared feature space with consistent classifiers during local training. Theoretically, we analyze the non-convex convergence rate of FedFA. We also demonstrate that the integration of feature alignment and classifier calibration in FedFA brings avirtuous cyclebetween feature and classifier updates, which breaks thevicious cycleexisting in current approaches. Extensive experiments show that FedFA significantly outperforms existing approaches on various classification datasets under label distribution skew and feature distribution skew.

A challenge of ambient backscatter communication (AmBC) systems is signal recovery because the transmitted information bits are embedded in the ambient RF signals and these are unknown and uncontrollable. To meet this challenge, averaging-based energy detectors are typically used but consequently the data rate is low and there is an error floor. Here we propose a new detection strategy based on the ratio between signals received from a multiple-antenna Reader. The advantage of using the ratio is that ambient RF signals are removed directly from the embedded signals without averaging and hence it can increase data rates and avoid the error floor. Different from the original ratio detector that uses the magnitude ratio of the signals between two Reader antennas, in our proposed approach, we utilize the complex ratio so that phase information is preserved and propose an accurate linear channel model approximation. This allows the application of existing linear detection techniques from which we can obtain a minimum distance detector and closed-form expressions for bit error rate (BER). Methods for the estimation of channel state information (CSI) are also provided. In addition, coding and interleaving are also included to further enhance the BER. The results are also general, allowing any number of Reader antennas to be utilized in the approach. Numerical results demonstrate the proposed approach performs better than approaches based on energy detection and the original ratio detectors.

Metaverse applications such as virtual reality (VR) content streaming, require optimal resource allocation strategies for mobile edge computing (MEC) to ensure a high-quality user experience. In contrast to online reinforcement learning (RL) algorithms, which can incur substantial communication overheads and longer delays, the majority of existing works employ offline-trained RL algorithms for resource allocation decisions in MEC systems. However, they neglect the impact of desynchronization between the physical and digital worlds on the effectiveness of the allocation strategy. In this paper, we tackle this desynchronization using a continual RL (CRL) framework that facilitates the resource allocation dynamically for MEC-enabled VR content streaming. We first design a digital twin-empowered edge computing (DTEC) system and formulate a quality of experience (QoE) maximization problem based on attention-based resolution perception. This problem optimizes the allocation of computing and bandwidth resources while adapting the attention-based resolution of the VR content. The CRL framework in DTEC enables adaptive online execution in a time-varying environment. We propose three variants of CRL, namely Continual Deep Deterministic Policy Gradient (CDDPG), Prioritized Experience Replay - CDDPG (PER-CDDPG), and Freshness Prioritized Experience Replay - CDDPG (FPER-CDDPG). We evaluate these algorithms, including two other benchmarks, using extensive experiments. FPER-CDDPG shows superior performance in terms of average latency, QoE, and successful delivery rate as well as meeting the hfQoE requirements over long-term execution while ensuring system scalability with the increasing number of users.

Mobile edge computing (MEC) resource allocation for remote rendering in virtual reality (VR) content streaming is critical for user experience. However, resource allocation becomes challenging due to the desynchronization between the physical and digital worlds in digital twin-empowered MEC. This paper presents our continual RL framework that facilitates dynamic resource allocation for MEC-enabled VR content streaming. We first design a digital twin-empowered edge computing (DTEC) system and formulate a maximization problem that considers attention-based resolution perception to maximize the quality of experience (QoE). This problem optimizes the allocation of computing and bandwidth resources while adapting the attention-based resolution of the VR content. We then apply continual reinforcement learning (CRL) to enable adaptive attention-based resolution VR streaming in a time-varying environment. We base the CRL's reward function on the QoE and horizon-fairness QoE (hfQoE) constraints. We support CRL with prioritized experience replay - continual deep deterministic policy gradient (PER-CDDPG) to enhance the performance of continual learning in the presence of time-varying DT updates. We test PER-CDDPG using extensive experiments and evaluation. PER-CDDPG outperforms the benchmarks in terms of average latency, QoE, and successful delivery rate as well as meeting the hfQoE requirements and performance over long-term execution while ensuring system scalability with the increasing number of users.

Non-orthogonal multiple access (NOMA)-aided mobile edge computing (MEC) system can enhance the spectral-efficiency with massive tasks offloading. However, with more dynamic devices and the uncontrollable stochastic channel environment, it is even desirable to deploy appealing technique, i.e., intelligent reflecting surfaces (IRS), in the MEC system to flexibly adjust the communication environment and improve the system energy-efficiency. In this paper, we investigate the joint offloading, communication and computation resource allocation for IRS-assisted NOMA-aided MEC system. We firstly formulate a mixed integer energy-efficiency maximization problem with the system queue stability constraint. We then propose a Het-erogeneous Multi-agent Lyapunov-function-based Mixed Integer Deep Deterministic Policy Gradient (HMA-LMIDDPG) algorithm which is based on the multi-agent reinforcement learning (MARL) framework with homogeneous edge devices (EDs) and heterogeneous base station (BS) as heterogeneous multi-agent. Numerical results show that our proposed algorithms can achieve superior energy-efficiency performance to the benchmark algorithms while maintaining the queue stability.

In this paper, we propose a new solution to improve the achievable rate of radio frequency (RF) powered cognitive radio networks (CRNs) with ambient backscatter communication (AmBC). Assisted with AmBC, the secondary transmitter (ST) can harvest energy and backscatter ambient signals when the primary channel is busy, which enhances the achievable rate compared with conventional RF-powered CRNs adopting the harvest-then-transmit (HTT) protocol. Our work proposes an RF-powered CRN that uses a multi-antenna ST since implementing multiple antennas on ST can enhance energy harvesting and increase the data rate. We discuss the corresponding time sharing and antenna selection tradeoffs and propose a low-complexity and time-efficient block coordinate descent (BCD)-assisted exhaustive search algorithm to find the optimal tradeoff that maximizes the data rate of the system. Simulation results show that our proposed scheme outperforms both the HTT mode and the ambient backscatter technique, leading to improved overall system performance.

An electric vehicle based mobility-on-demand (EMoD) system provides shared transportation (e.g., car-sharing or ride-sharing) to satisfy customers’ individual mobility demands. It has been recognized as a vital alternative form of transportation between public and private transportations in future sustainable cities. Constrained by the long charging time and limited driving range of EVs, an operator of an EMoD system demands for decision-making models and algorithms to manage the mobility and energy of EVs to best serve customers with least costs. In this paper, we propose a stochastic dynamic program (DP) to model three operational decisions of the EMoD system: i) dispatching EVs to serve mobility demand from customers, ii) repositioning EVs to accommodate the unbalanced mobility demands between service regions, and iii) recharging EVs to maintain their sufficient state-of-charge levels. To handle this large-scale DP problem, we first observe and prove that it has a coordinate-wise concave value function. Based on this structural property, we propose to use a separable piecewise linear function to approximate the value function and design an approximation-based algorithm to efficiently derive the decision policy. Numerical tests show that our proposed algorithm significantly outperforms the existing model-free approaches (e.g., greedy heuristic and Q-learning) that fail to take into account the structural properties of the DP problem.

By employing powerful edge servers for data processing, mobile edge computing (MEC) has been recognized as a promising technology to support emerging computation-intensive applications. Besides, non-orthogonal multiple access (NOMA)-aided MEC system can further enhance the spectral efficiency with massive tasks offloading. However, with more dynamic devices brought online and the uncontrollable stochastic channel environment, it is even desirable to deploy appealing technique, i.e., intelligent reflecting surfaces (IRS), in the MEC system to flexibly tune the communication environment and improve the system energy efficiency. In this paper, we investigate the joint offloading, communication and computation resource allocation for the IRS-assisted NOMA MEC system. We first formulate a mixed integer energy efficiency maximization problem with system queue stability constraint. We then propose the Lyapunov-function-based Mixed Integer Deep Deterministic Policy Gradient (LMIDDPG) algorithm which is based on the centralized reinforcement learning (RL) framework. To be specific, we design the mixed integer action space mapping which contains both continuous mapping and integer mapping. Moreover, the award function is defined as the upper-bound of the Lyapunov drift-plus-penalty function. To enable end devices (EDs) to choose actions independently at the execution stage, we further propose the Heterogeneous Multi-agent LMIDDPG (HMA-LMIDDPG) algorithm based on distributed RL framework with homogeneous EDs and heterogeneous base station (BS) as heterogeneous multi-agent. Numerical results show that our proposed algorithms can achieve superior energy efficiency performance to the benchmark algorithms while maintaining the queue stability. Specially, the distributed structure HMA-LMIDDPG can acquire more energy efficiency gain than the centralized structure LMIDDPG.

In this article, we consider a parking lot that manages the charging processes of its parked electric vehicles (EVs). Upon arrival, each EV requests a certain amount of energy. This request should be fulfilled before the EV’s departure. It is of critical importance to coordinate the EVs’ charging rates to smooth out the load profile of the parking lot because inappropriate charging rates can lead to sharp spikes and fluctuations on the load profile, imposing negative effects on the power grid. Meanwhile, empirical studies show that many parking lots exhibit statistical patterns on EV dynamics. For example, the bulk of EVs arrives during rush hours. Therefore, in this article, we incorporate such patterns into charging rate coordination. Although the statistical patterns can be summarized from historical data, they are difficult to be analytically modeled. As a result, we adopt a model-free deep reinforcement learning approach. We also take the latest continuous charging rate control technology into consideration. The decision variables are thus continuous and a policy gradient algorithm is needed to perform reinforcement learning. Technically, we first formulate the problem as a Markov decision process (MDP) with unknown state transition probabilities. To further derive a deep policy gradient algorithm, the challenge lies in the inconsistent and state-dependent action space of the MDP model, due to the constraint to satisfy EVs’ energy demands before their scheduled departure. To tackle the challenge, we design a customized model for neural network training by extending the action space to be consistent and state independent, and revise the reward function to penalize the neural network output if it is beyond the action space of the original MDP model. With this customized model, we then develop a deep policy gradient algorithm based on the proximal policy gradient framework. Numerical results show that our algorithm outperforms the benchmarks.

With the popularization of ride-sharing transportation and increasing penetration of electric vehicles (EVs) in recent years, the electric mobility-on-demand (EMoD) system is emerging as a promising means to provide ride-sharing services in the context of sustainable cities. In this paper, we focus on sequential decision-making for the operator of an EMoD system by considering both the passengers’ utility and system revenue. Specifically, we design a pricing mechanism to incentivize passengers with spatially and temporally different demand to make different mobility choices. After the passengers’ demand is realized, the operator makes operational decisions, including dispatching and repositioning EVs between service regions, and recharging EVs to maintain their energy levels. Therefore, a bi-level and dynamic programming problem is formulated to model these decisions. To solve this problem, we first transform the bi-level problem into a single-level one based on the structural properties of the formulation. Furthermore, we rigorously prove the coordinate-wise concavity of the single-level formulation and efficiently obtain near-optimal solutions based on approximation. Numerical tests show that the proposed dynamic pricing mechanism achieves a significantly better performance than static pricing and other existing model-free approaches (e.g., Q-learning).

This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.

The Internet-of-Things (IoT) platform is faced with critical challenges posed by the conflict between resource-hungry IoT applications and resource-constrained IoT devices. Mobile-edge computing provides a promising solution by allowing IoT devices to offload their computation to nearby edge servers to enable fast and energy-efficient data processing. In this article, we study a scenario, where two IoT users (IoT devices) offload their computation workloads to an edge server with hybrid nonorthogonal multiple access (NOMA)-orthogonal multiple access (OMA) transmission. The hybrid multiple access transmission incorporates three offloading methods, namely, hybrid NOMA, pure NOMA, and pure OMA. The offloading-method selection, together with user selection, which determines the roles played by different IoT users in data transmission, comprises our offloading strategy and is optimized to minimize the maximal offloading latency of the two IoT users. By exploiting the method of successive convex approximation, we design an efficient algorithm to solve the complicated nonconvex problem and rigorously prove the convergence of our algorithm. Extensive numerical tests show that our scheme can always help IoT users to flexibly choose the best offloading strategy. Inspired by experimental observations, we analytically establish the criteria for the three offloading methods. We show that pure OMA transmission is never the best offloading method, except in some extreme cases that rarely occur in practice, while pure NOMA transmission is the most desirable offloading method in terms of latency minimization. We then propose detection approaches for the best offloading strategy with both offloading-method selection and user selection under certain system settings. The user selection is applied to avoid the pure OMA transmission and encourage the pure NOMA transmission.

Ambient backscatter communication (AmBC) leverages the existing ambient radio frequency (RF) environment to implement communication with battery-free devices. The key challenge in the development of AmBC is the very weak RF signals backscattered by the AmBC Tag. To overcome this challenge, we propose the use of orthogonal space-time block codes (OSTBC) by incorporating multiple antennas at the Tag as well as at the Reader. Our approach considers both coherent and non-coherent OSTBC so that systems with and without channel state information can be considered. To allow the application of OSTBC, we develop an approximate linearized and normalized multiple-input multiple-output (MIMO) channel model for the AmBC system. This MIMO channel model is shown to be accurate for a wide range of useful operating conditions. Two coherent detectors and a non-coherent detector are also provided based on the proposed AmBC channel model. Simulation results show that enhanced bit error rate performance can be achieved, demonstrating the benefit of using multiple antennas at the Tag as well as the Reader.

This paper proposes a tandem fluid queue model for a mobile computing system with computation offloading and analytically derives its key quality-of-service (QoS) metric. Based on the performance model, we further evaluate the economic benefits of burstable instances, a new type of cloud instances that are recently introduced to the market, and make suggestions on whether burstable instances should be used for mobile computing to save users' costs under different wireless channel conditions and QoS requirements.

With the growing popularity of cloud gaming and cloud virtual reality (VR), interactive 3D applications have become a major class of workloads for the cloud. However, despite their growing importance, there is limited public research on how to design cloud systems to efficiently support these applications due to the lack of an open and reliable research infrastructure, including benchmarks and performance analysis tools. The challenges of generating human-like inputs under various system/application nondeterminism and dissecting the performance of complex graphics systems make it very difficult to design such an infrastructure. In this paper, we present the design of a novel research infrastructure, Pictor, for cloud 3D applications and systems. Pictor employs AI to mimic human interactions with complex 3D applications. It can also track the processing of user inputs to provide in-depth performance measurements for the complex software and hardware stack used for cloud 3D-graphics rendering. With Pictor, we designed a benchmark suite with six interactive 3D applications. Performance analyses were conducted with these benchmarks, which show that cloud system designs, including both system software and hardware designs, are crucial to the performance of cloud 3D applications. The analyses also show that energy consumption can be reduced by at least 37% when two 3D applications share a could server. To demonstrate the effectiveness of Pictor, we also implemented two optimizations to address two performance bottlenecks discovered in a state-of-the-art cloud 3D-graphics rendering system. These two optimizations improved the frame rate by 57.7% on average.

The past decades have witnessed an explosive growth of the Internet of Things (IoT) services requiring intensive computation resources. The conventional IoT devices, however, are usually equipped with very limited computation resources, which results in degraded quality of experience when executing the resource-hungry applications. Mobile edge computing (MEC), which enables smart terminals (STs) to offload parts of their computation workloads to the edge servers located at cellular base stations (BSs), has provided a promising approach to address this issue. In this article, we investigate the nonorthogonal multiple access (NOMA)-enabled multiaccess MEC. Specifically, by exploiting the advanced NOMA, an ST can simultaneously offload its computation workloads to different edge servers (ESs), which thus reduces the overall delay in completing the ST's computation workloads. To study this problem, we formulate a joint optimization of the computation resource allocations at the ESs, the ST's offloaded workloads and its radio resource allocations for NOMA transmission, with the objective of minimizing a system wise cost that accounts for the overall delay in finishing the ST's total computation workload and the total computation resource usage cost at the ESs. Despite the nonconvexity of the joint optimization problem, we exploit its layered structure and propose an efficient layered algorithm to find the optimal solution. By exploiting the optimal offloading solution of a single ST, we further investigate the scenario of multiple STs and propose two algorithms to determine the optimal grouping among different ESs for serving the STs, with one algorithm aiming at minimizing the total cost of all STs and the other algorithm aiming at determining the Nash stable grouping for the ESs. Numerical results are presented to validate the effectiveness of our proposed algorithms and show the performance gain of our proposed NOMA-enabled multiaccess computation offloading.

In this paper, we study a general transactive energy (TE) retailing problem in smart grids: a TE retailer (e.g., a utility company) publishes the energy price, which may vary over time. TE customers arrive in an arbitrary manner and may choose to either purchase a certain amount of energy based on the posted price, or leave without buying. Typical examples of such a setup include a transactive electric vehicle charging platform, or a general market-based demand-side management program, etc. We consider the setting where the customer arrival information is unknown (i.e., without prediction), and focus on maximizing the social welfare of the TE system through a posted-price mechanism (PPM) that runs in an online fashion with causal information only. We quantify the performance of the proposed PPM in the competitive analysis framework, and show that our proposed PPM is optimal in the sense that no other online mechanisms can achieve a better competitive ratio. We evaluate our theoretic results for the case of transactive electric vehicle charging. Our extensive experimental results show that the proposed PPM is competitive and robust against system uncertainties, and outperforms several existing benchmarks.

We study a general online combinatorial auction problem in algorithmic mechanism design. A provider allocates multiple types of capacity-limited resources to customers that arrive in a sequential and arbitrary manner. Each customer has a private valuation function on bundles of resources that she can purchase (e.g., a combination of different resources such as CPU and RAM in cloud computing). The provider charges payment from customers who purchase a bundle of resources and incurs an increasing supply cost with respect to the totality of resources allocated. The goal is to maximize the social welfare, namely, the total valuation of customers for their purchased bundles, minus the total supply cost of the provider for all the resources that have been allocated. We adopt the competitive analysis framework and provide posted-price mechanisms with optimal competitive ratios. Our pricing mechanism is optimal in the sense that no other online algorithms can achieve a better competitive ratio. We validate the theoretic results via empirical studies of online resource allocation in cloud computing. Our numerical results demonstrate that the proposed pricing mechanism is competitive and robust against system uncertainties and outperforms existing benchmarks.

Recent studies have reported that big data analytics clusters, such as Hadoop, can create substantial power peaks, bringing instability and inflexibility issues to the power grid. Substantial power peaks also lead to high penalty charges from electric utility companies, accounting for more than 30 percent of the electricity bill for a cluster operator according to empirical studies. To this end, in this paper, we present a framework that schedules computing jobs in large-scale data analytics clusters to mitigate power peaks. The scheduling model captures important properties of modern distributed data analytics clusters, including bundled resource provisioning and job-to-task decomposition with distributed processing. The scheduling problem is formulated as a nonlinear integer program. Its solution is derived by decomposing it into two classes of sub-problems and solving each class with an exact and efficient solution method. As a direct application, we detail the implementation of our proposed scheduling framework on a Hadoop cluster, and demonstrate its efficacy by extensive trace-driven simulations based on the CloudSim simulator.

Leading cloud providers recently introduced a new instance type named burstable instances to better match the time-varying workloads of tenants and further reduce their costs. In the research community, however, little has been done to understand burstable instances from a theoretical perspective. This paper presents the first unified framework to model, analyze, and optimize the operation of burstable instances. Specifically, we model the resource provisioning of burstable instances, identify key performance metrics, and derive the analytical performance given the resource provisioning decisions. We then characterize the equilibrium behind tenants' responses to the prices offered for different burstable instance service classes, taking into account the impact of tenants' actions on the performance achieved by each service class. In addition, we investigate how a cloud provider can leverage knowledge of this equilibrium to find the prices that maximize its total revenue. Finally, we validate our framework on real traces and demonstrate its usage to price burstable offerings in a public cloud.

Leading cloud providers recently introduced a new instance type named burstable instances to better match the time-varying workloads of tenants and further reduce their costs. In the research community, however, little has been done to understand burstable instances from a theoretical perspective. This paper presents the first unified framework to model, analyze, and optimize the operation of burstable instances. Specifically, we model the resource provisioning of burstable instances in different service classes, identify key performance metrics, and derive the performance given the resource provisioning decisions. We then characterize the equilibrium behind tenants' responses to the prices offered for different burstable instance service classes, taking into account the impact of tenants' actions on the performance achieved by each service class. In addition, we investigate how a cloud provider can leverage the knowledge of this equilibrium to find the prices that maximize its total revenue. Finally, we validate our framework on real traces and demonstrate its usage to price a public cloud.

In this paper, we study resource allocation (including power and computation resources) and channel assignment in an uplink Non-orthogonal Multiple Access (NOMA)-based Mobile Edge Computing (MEC) system. Our objective is to minimize the total energy consumption of all users. The problem, however, is a non-convex combinatorial optimization problem. We first investigate the hidden convexity by reformulating the resource allocation problem when the channel assignment is given, and propose an efficient algorithm to allocate the resources by dual decomposition methods. Furthermore, we design a heuristic algorithm to decide the channel assignment leveraging the structural property in the reformulation. Extensive simulations verify that NOMA has great advantages over Orthogonal Multiple Access (OMA) in multi-user latency-intensive MEC systems.

This paper addresses the beamforming and power allocation problem in the downlink multi-input multi-output (MIMO) non-orthogonal multiple access (NOMA) based cognitive radio (CR) network. In particular, we consider a secondary base station (BS) located at cell-edge of a primary BS assists far away secondary users that do not have direct link with the primary BS. Random user pairing is performed among primary users (PUs) and secondary user (SUs) respectively, to reduce successive interference cancellation (SIC) complexity and inter-user interference. In order to eliminate inter-cluster interference and interference from the secondary BS, interference alignment (IA)-based coordinated beamforming (CBF) is proposed. We then provide an optimal power allocation method to maximize the sum rate of each network while guaranteeing a minimum quality of service for users with weaker channel gain inside each cluster. We show that compared to two baseline beamforming schemes for NOMA, the proposed scheme improves the system throughput significantly.

Historically, transportation electrification has been largely hindered by the limited battery capacity and the long charging time. Battery swapping has emerged as one promising technology to mitigate these problems. A centralised battery charging station (BCS) is responsible for charging depleted batteries (DBs) and providing fully‐charged batteries (FBs) for multiple geographically‐distributed battery swapping stations (BSSs) so that they can carry out battery swapping services. Facilitated by the recent advancement in sensor and communication technologies, one salient advantage of this centralised approach lies in its convenience to better utilise dual energy sources (i.e. the traditional power grid and local renewable energy generators). This is achieved via optimising the charging processes of a large number of DBs. In this study, the authors propose an optimisation framework for a centralised BCS to minimise the energy cost from the dual energy sources to satisfy the FB demands from multiple BSSs. Particularly, the power dispatch problem in the day‐ahead and real‐time electricity markets is formulated as a two‐stage stochastic optimisation through consideration of the intermittent renewable energy. Numerical simulations show that the proposed optimised power dispatch is capable of achieving cost saving of 76% compared with the benchmark, subject to the limited information available in day‐ahead.

Offloading computation tasks from resource-poor end devices to powerful backend clouds has become a prevalent solution thanks to the rapid development of cloud computing. However, modern Internet of Things applications, such as augmented reality and real-time monitoring, bring stringent delay requirements to the computation tasks in the device-to-computing-facility communications. To better accommodate the delay requirements of the computation tasks, the recently proposed fog computing architecture suggests that these computation tasks can be extensively offloaded to the distributed computation facilities along the cloud-to-things continuum. These computation facilities, including central clouds and the computation facilities standing at the network edge, jointly form an overlay network, named a fog network, to provide fog computing services for end devices. This paper targets a practical and efficient scheme to schedule tasks with heterogeneous delay sensitivities in a shared fog network. A mathematical model is first constructed to capture the major characteristics of a fog network. The model enforces lexicographic max–min fairness, an enhanced metric compared to conventional max–min fairness. The task offloading problem is modeled as an integer nonlinear program. An efficient and exact solution method is proposed based on problem-specific analysis. Finally, synthesized-trace-driven simulations demonstrate the efficacy of our proposed offloading scheme.

Distributed stream big data analytics platforms have emerged to tackle the continuously generated data streams. In stream big data analytics, the data processing workflow is abstracted as a directed graph referred to as a topology. Data are read from the storage and processed tuple by tuple, and these processing results are updated dynamically. The performance of a topology is evaluated by its throughput. This paper proposes an efficient resource allocation scheme for a heterogeneous stream big data analytics cluster shared by multiple topologies, in order to achieve max-min fairness in the utilities of the throughput for all the topologies. We first formulate a novel resource allocation problem, which is a mixed 0-1 integer program. The NP-hardness of the problem is rigorously proven. To tackle this problem, we transform the non-convex constraint to several linear constraints using linearization and reformulation techniques. Based on the analysis of the problem-specific structure and characteristics, we propose an approach that iteratively solves the continuous problem with a fixed set of discrete variables optimally, and updates the discrete variables heuristically. Simulations show that our proposed resource allocation scheme remarkably improves the max-min fairness in utilities of the topology throughput, and is low in computational complexity.

With the integration of renewable energy sources to the power grid, the volatility of supply in the system will increase. Consequently, the mismatch between the power supply and demand may happen frequently and, thus, lead to frequency deviation from its nominal value. To avoid this scenario, demand-side flexibility has been widely considered to provide frequency regulation services. In this paper, we focus on the flexibility of thermal systems in buildings and propose a hierarchical demand-response market with a three-step algorithm to model the interactions among three entities: the independent system operators (ISOs), aggregators, and end users. The flexibility from the end users is aggregated in step 1, which is based on the incentive and electricity prices broadcasted by the aggregator. A robust optimization approach is adopted to improve the user's decision under the electricity price uncertainty. To model the interaction between the ISO and aggregators in step 2, a bilevel optimization problem is solved, in which the ISO seeks to minimize its cost, while the aggregators maximize their benefits in the day-ahead market. In step 3, each aggregator allocates its successful trading reserve among end users based on their performance scores.

The nineteen articles in this special section focus on energy informatics, a new and emerging nterdisciplinary research field. The main goal is to tackle the future global warming, energy crisis, and climate change challenges by exploiting advanced information and communication (ICT) theories and tools to address energy-related problems. The scope of energy informatics includes the next-generation communications, networking, computing, sensing, and control technologies (e.g., big data, machine learning, 5G, cloud computing, and fog computing); and their applications in the energy sectors (e.g., smart cities, smart grid, electric vehicles, and PV systems).

Due to their environment friendliness, electric vehicles (EVs) are anticipated to form a considerable fraction of vehicles for transportation in smart cities. It is essential to design an electricity charging scheme that takes the utilities of both the charging stations and the EVs into consideration. However, the self-interested nature of the EVs together with the information asymmetry between the energy demand and supply sides makes the design a significant challenge. In this paper, we propose a queuing network-based model to characterize the charging process of the multiple EVs in a renewable energy-aided charging station. Based on the model, we adopt a contract theoretic approach to design an optimal charging policy in an information asymmetry scenario. Furthermore, we propose the new contract-based charging rate assignment and admission control schemes that maximize the utility of the charging station under certain charging constraints. To derive the optimal contract, we present a two-step iterative algorithm and prove its convergence. We evaluate the proposed schemes based on the IEEE 69-bus distribution test system. Results indicate that the contract-based charging schemes can effectively benefit both the charging stations and the EVs and concurrently improve the load level of the smart grid.

Providing backhaul connectivity for macro and pico base stations (BSs) constitutes a significant share of infrastructure costs in future heterogeneous networks (HetNets). To address this issue, the emerging idea of flexible backhaul is proposed. Under this architecture, not all the pico BSs are connected to the backhaul, resulting in a significant reduction in the infrastructure costs. In this regard, pico BSs without backhaul connectivity need to communicate with their nearby BSs in order to have indirect accessibility to the backhaul. This makes the radio resource management (RRM) in such networks more complex and challenging. In this paper, we address the problem of cross-layer RRM in HetNets with flexible backhaul. We formulate this problem as a two-timescale non-convex stochastic optimization, which jointly optimizes flow control, routing, interference mitigation, and link scheduling in order to maximize a generic network utility. By exploiting a hidden convexity of this non-convex problem, we propose an iterative algorithm which converges to the global optimal solution. The proposed algorithm benefits from low complexity and low signaling, which makes it scalable. Moreover, due to the proposed two-timescale design, it is robust to the backhaul signaling latency as well. Simulation results demonstrate the significant performance gain of the proposed solution over various baselines.

Due to the ever-increasing use of electric vehicles (EVs) and renewable energy sources, the charging station with renewable energy supply is made as one promising energy solution. Moreover, grouping vehicles into platoons could greatly improve road capacity and reduce energy consumption. These tendencies urgently demand a theoretical performance analysis framework of the EV platoons charging at renewable energy supplied stations. In this paper, we present such a framework based on a queuing network model. In this model, the fluctuation of the renewable energy, the uncertainty of the EV platoons arrival, the variation of the charging price, and the serving capacity limitation of the charging station are taken into account. The steady-state distribution of the queuing system have been presented based on the equilibrium equations. Then, various performance metrics of the charging system together with the charging gain of EVs have been proposed. The queuing network model, validated by the simulation results, can be used in the planning of practical charging stations and the charging scheduling of EV platoons.

We address the problem of scheduling jobs with utilities that depend solely upon their completion-times in a shared cloud that imposes considerable uncertainty on the jobs' runtime. However, it is very hard to estimate the jobs' runtime in a shared cloud where jobs are often delayed due to reasons such as slow I/O performance and variations in memory availability. Unlike prior works, we acknowledge that runtime estimates are often erroneous and instead shift the burden of robustness to the job scheduler. Specifically, we present a scheduling problem that jointly accounts for: (i) job utilities specified as functions of their completion-time, and (ii) uncertainty in the jobs' runtime. Our proposed solution to this problem achieves lexicographic max-min fairness among the job utilities. We implement this as a robust scheduler, named RUSH, for YARN in Hadoop. Our experiments, using real-world data sets, illustrate RUSH's efficacy when compared with other commonly used schedulers.

In this paper, we consider the problem of cross-layer radio resource management in heterogeneous networks (HetNets) with flexible backhaul, which aims at minimizing the total transmit power of base stations (BSs) while guaranteeing the average end-to-end data rate requirement of each data flow. We formulate the problem as a two-time scale stochastic optimisation, where the long-timescale control variables are flow control, routing control and interference coordination, while the short-timescale control variable is instantaneous beamforming within each cell. Using a stochastic cutting plane (SCP) method, we propose a cross-layer queue-state information (QSI) aware radio resource management (RRM) solution in which the long-term controls are updated centrally at radio resource management server (RRMS) without needing to know the global statistical information of the network, and the short-term control variables are updated locally at each BS with only the local instantaneous QSI and channel-state information (CSI) available at each cell. Simulation results show the significant performance gain of our proposed algorithm compared to various baselines.

Consolidating virtual machine workload is a unique feature of cloud computing platforms that greatly reduces the operating cost of the cloud data center. Correctly consolidating VMs' workloads for a large scale cloud computing platform is nontrivial because a shortsighted scheme may save some cost in one aspect but becomes expensive in other aspects being neglected. In this paper, we present a framework that automates the VM consolidation process to improve the VMs and servers assignment whenever such improvement is possible. The proposed VM consolidation framework can achieve a balance among multiple administrative objectives (e.g., power cost, network cost) during the VM consolidation process. The solution method of solving the VM consolidation problem is designed based on the powerful and efficient semi quasi M-convex optimization framework. The proposed algorithm can also produce VM consolidation solutions that require minimal system reconfigurations (e.g., VM migrations, turning on/off servers). More importantly, the proposed algorithm can be implemented distributedly so that the scalability of the proposed framework is greatly improved. As a result, the proposed framework is efficient, scalable and highly practical.

The optimal operation of a distributed battery energy storage system (BESS) for energy arbitrage under dynamic pricing is studied in this paper, and the Pareto optimal arbitrage policy that balances the economic value and lifetime tradeoff of the BESS is obtained. Specifically, the lifetime performance of the BESS is represented by its average lifetime, i.e., the average operational duration within which its capacity stays above a certain threshold, and the value performance of the BESS is defined as the total average arbitrage value within its entire lifetime. We propose a constrained stochastic shortest path (CSSP) model to characterize the optimal value-lifetime performance pair. By exploiting the hidden structure of this CSSP problem, an efficient parallel algorithm is proposed to compute the optimal policy. We further prove the condition under which the optimal policy is Pareto optimal. This implies that the achievable optimal value-lifetime performance pair is globally optimal as long as the system-wide utility is monotonically increasing in both the value performance and the lifetime performance. We validate our proposed model and algorithm via real battery specifications and electricity market data, and the results show promising insights for both infrastructure planning and operational management of BESSs in practice.

In this paper, we focus on the problem of hierarchical cross-layer dynamic resource allocation for heterogeneous networks with flexible backhaul. We formulate the radio resource management problem as a two timescale non-convex stochastic optimisation problem which jointly optimizes flow control, routing control, interference mitigation and link scheduling in order to maximize a generic network utility. We propose an iterative hierarchical control structure where the long-term controls are adaptive to large scale fading and the short-term control is adaptive to the local CSI within a pico or macro BS, to find the optimal solution. The proposed solution benefits from low complexity and requires low signalling and message passing among different nodes, which makes it scalable. Moreover, due to the proposed two-timescale hierarchical design, it is robust to the backhaul signalling latency as well. Simulation results demonstrate the significant performance gain of the proposed solution over various baselines.

There is an increasing need for cloud service performance that can be tailored to customer requirements. In the context of jobs submitted to cloud computing clusters, a crucial requirement is the specification of job completion-times. A natural way to model this specification, is through client/job utility functions that are dependent on job completion-times. We present a method to allocate and schedule heterogeneous resources to jointly optimize the utilities of jobs in a cloud. Specifically: (i) we formulate a completion-time optimal resource allocation (CORA) problem to apportion cluster resources across the jobs that enforces max-min fairness among job utilities, and (ii) starting with an integer programming problem, we perform a series of steps to transform it into an equivalent linear programming problem, and (iii) we implement the proposed framework as a utility-aware resource scheduler in the widely used Hadoop data processing framework, and finally (iv) through extensive experiments with real-world datasets, we show that our prototype achieves significant performance improvement over existing resource-allocation policies.

One of the main advantages of utilizing flexible backhaul in future HetNets is that it can provide better user experience through flexible resource allocation. For this purpose, it is important to provide the required quality of service (QoS) in such networks. In this paper, we consider the problem of cross-layer radio resource management in HetNets with flexible backhaul which guarantees minimum total transmit power of BSs as well as the average end-to-end data rate requirement of each data flow. The problem is formulated as a two-timescale stochastic optimisation, where the long-timescale control variables are flow control, routing control and interference mitigation, while the short-timescale control variable is instantaneous beamforming within each cell. Using stochastic cutting plane, we propose an online cross-layer hierarchical algorithm in which the long-term controls are updated centrally at radio resource management server (RRMS) without needing to know the global statistical information of the network, and the short-term control variables are updated locally at each BS with only the local instantaneous CSI available at each cell. The proposed algorithm has low complexity and signalling overhead. Moreover, simulation results show the significant gains of our proposed algorithm over various baselines.

Energy-aware routing is a promising technique for reducing energy consumption in future networks. Under this scheme, traffic loads are aggregated over a subset of the network links, allowing other links to be turned off to save energy. Since the capacity of links is the main limiting constraint in this problem, to further improve energy saving, the idea of using redundancy elimination (RE) in energy-aware routing has been proposed. As performing RE in routers consumes some energy, it should be specified, which routers should perform RE and which links should be deactivated so that the total energy consumption of the network is minimized. As a result, the problem of energy-aware routing with redundancy elimination, which is known to be NP-hard, arises. In this paper, we first model the problem as a mixed integer linear program (MILP). Since this problem is NP-hard, we propose an efficient heuristic solution. For this purpose, we apply Lagrangian relaxation to the problem and then prove that the obtained formulation is totally unimodular. Under this property, we can relax the integer variables to efficiently determine the solution in polynomial time. Simulation results show the advantages of our proposed heuristic solution over previous ones in terms of approximately twice the energy saving, as well as a lower number of active RE-routers. Furthermore, we show that our method can be applied to the generic energy-aware routing problem (i.e., without RE) as well.

Future smart grid (SG) has been considered a complex and advanced power system, where energy consumers are connected not only to the traditional energy retailers (e.g., the utility companies), but also to some local energy networks for bidirectional energy trading opportunities. This paper aims to investigate a hybrid energy trading market that is comprised of an external utility company and a local trading market managed by a local trading center (LTC). The existence of local energy market provides new opportunities for the energy consumers and the distributed energy sellers to perform the local energy trading in a cooperative manner such that they all can benefit. This paper first quantifies the respective benefits of the energy consumers and the sellers from the local trading and then investigates how they can optimize their benefits by controlling their energy scheduling in response to the LTC's pricing. Two different types of the LTC are considered: 1) the nonprofit-oriented LTC, which solely aims at benefiting the energy consumers and the sellers; and 2) the profit-oriented LTC, which aims at maximizing its own profit while guaranteeing the required benefit for each consumer and seller. For each type of the LTC, the optimal trading problem is formulated and the associated algorithm is further proposed to efficiently find the LTC's optimal price, as well as the optimal energy scheduling for each consumer and seller. Numerical results are provided to validate the benefits of the hybrid energy trading market and the performance of the proposed algorithms.

The current mobile broadband market experiences major growth in data demand and average revenue loss. To remain profitable from the perspective of a service provider (SP), one needs to maximize revenue as much as possible by making subscribers satisfied within the limited budget. On the other hand, traffic demands are moving toward supporting the wide range of heterogeneous services with different quality of service (QoS) requirements. In this paper, we consider packet scheduling problem in the 4th generation partnership project (3GPP) long term evolution-advanced (LTE-A) system to optimize the long-term average revenue of SPs subject to differential QoS constraints for heterogeneous traffic demands. The QoS-constrained control problem is first formulated as a constrained Markov decision process (CMDP) problem, of which the optimal control policy is achieved by utilizing the channel and queue information simultaneously. Subsequently, based on the proposed CMDP problem, we further formulated an optimization problem which stochastically grantees the QoS through a chance constraint. To make the proposed chance-constraint programming problem computationally tractable, we use Bernstein approximation technique to analytically approximate the chance constraint as a convex conservative constraint. Finally, the proposed scheduling framework and solution methods are validated via numerical simulation.

We propose a revenue sharing based resource allocation scheme for dynamic spectrum access (DSA) networks. In our scheme, based on a mutually agreed revenue sharing scheme, a primary network operator (PNO) actively shares its radio resource with a secondary network operator (SNO), which provides access service to secondary users (SUs) for its revenue maximization. To investigate the coupling effect between the revenue sharing and resource allocation, we formulate the interaction between PNO and SNO as a two-layered game, which includes a top layer game to model their revenue sharing and a bottom layer game to model their joint resource allocations. Specifically, in the top layer, based on their joint resource allocation decisions, the PNO and SNO form a Nash bargaining game to determine the revenue sharing scheme such that both of them can benefit from cooperation satisfactorily. Then, in the bottom layer, under the given revenue sharing scheme, the PNO and SNO form a Stackelberg game to determine their joint resource allocation decisions, which also influence their respective revenues. The two games work iteratively such that the PNO and SNO reach a final equilibrium state at which neither PNO nor SNO will change its decisions unilaterally in both layers. We propose efficient algorithms to solve both the top layer and bottom layer games and compute the final equilibrium of the two-layered game. Specifically, despite the non-convexity of joint resource allocation optimization problem in the bottom layer, we identify its hidden monotonic structure and propose an efficient algorithm, which is based on the polyblock approximation, to achieve the optimal solutions. Moreover, in the top layer, to tackle with the difficulty due to the lack of an analytical objective function for the revenue sharing problem, we explore its hidden unimodal property and propose a Brent's method based algorithm to achieve the optimal solution. Numerical results are presented to verify the performance of our algorithms and show that our revenue sharing based resource allocation scheme yields a win-win situation for the PNO and SNO.

Frequency domain packet scheduling (FDPS) problem is one of the crucial elements in the 3rd generation partnership project (3GPP) long term evolution (LTE) system, which has a tremendous impact on the LTE system performance. However, optimal resource allocation through FDPS is a complicated and challenging task when multiple input and multiple output (MIMO)-orthogonal frequency division multiple access (OFDMA) technology is adopted. In this paper, we propose a new FDPS scheme for the 3GPP LTE downlink channels that optimally assigns time-frequency resources to users based on the proportional fairness metric. The proposed scheme jointly considers multiple system constraints imposed by the 3GPP LTE standard that arise in the MIMO mode selection and modulation and coding scheme (MCS) selection. Such scheduling problem is considered to be among the most difficult optimization problems. Our major contribution in this paper is that we model the FDPS problem as a unique binary linear programming problem and prove that the problem is totally unimodular. With the total unimodularity property, we are able to solve the complicated FDPS problem using efficient linear programming problem solvers. Simulation results show that our proposed scheme outperforms the existing state-of-the-art MIMO proportional fair scheduling algorithms used in the FDPS problem.

This paper presents MCP, a novel distributed and reactive transport protocol for data center networks (DCNs) to achieve minimal per-packet delay while providing guaranteed transmission rates to meet flow deadlines. To design MCP, we first formulate a stochastic packet delay minimization problem with constraints on deadline completion and network stability. By solving this problem, we derive an optimal congestion window update function which establishes the theoretical foundation for MCP. To be incrementally deployable with existing switch hardware, MCP leverages functionality available on commodity switch, i.e., ECN, to approximate the optimal window update function. Our preliminary results show that MCP holds great promise in terms of deadline miss rate and goodput.

Localization is the enabling technology of geolocation database assisted Cognitive Radio Networks (CRN) in TV White Space (TVWS), as the location is required in the implementation of geolocation database approach by regulators such as FCC and Ofcom. This paper proposes a novel Sensing enAbled Localization and Tracking (SALT) system, which locates Secondary Users (SUs) and tracks their movements. In particular, the system localize SUs based on their measurement of Primary User (PU) signals in the TV spectrum. SALT also uses the SU movement information to dynamically manage the available spectrum with an optimal spectrum allocation algorithm based on the location estimation, so as to maximize the uplink throughput of the entire network. The performance of the proposed localization and tracking algorithm is verified with field measurement data from complex environment through extensive experimentation.

IEEE 802.11e EDCA induces service differentiation by appropriate joint tuning of four adjustable contention parameters. Existing and emerging work has devoted considerable attention to the nonsaturated performance of EDCA networks due to the difficulty of predicting the joint influence of the four parameters. However, most existing nonsaturated EDCA models adopt complex extensions of a Markov-chain approach. In sharp contrast, this paper invokes an extension of a renewal-reward approach. Our extension has the following unparalleled advantages: good scalability, ease of understanding, fast computation speed, high accuracy, models joint differentiation of all four parameters, captures the impact of an arbitrary buffer size, and predicts a wide range of performance indicators including the buffer overflow probability and the MAC access delay distribution. Our nonsaturated EDCA model is a nontrivial augmentation of our previously proposed nonsaturated DCF model. Our results indicate that if we accurately model the nonsaturated collision probability, the same formulas used for the saturated performance descriptors can produce accurate results for nonsaturated operation, and therefore it is unnecessary to construct specific formulas for nonsaturated performance descriptors, as done in previous work. To illustrate the utility of our model, we also develop an admission control policy based on the proposed EDCA model for a CWmin-differentiation system. Simulations validate that this policy enables the system to run slightly below a critical point, beyond which the system performance deteriorates drastically.

In this paper, by taking both sensing performance and energy efficiency into consideration, the Cooperative Sensing Scheduling (CSS) problem for multi-band Cognitive Radio Networks (CRNs) is investigated under a practical scenario where both Primary User (PU) channels and Secondary Users (SUs) have heterogeneous characteristics. Unlike many existing works that merely claim that the CSS problem is NP-hard and then turn to heuristic methods, we analyze this problem under a solid discrete-convex framework. After formulating the CSS problem as a nonlinear binary programming problem, we adopt a three-step approach to solve it. In the first step, the number of SUs assigned to sense each PU channel is determined with the M/M^natural-convex theory. Based on the results obtained in the first step, we then find the SU assignment using the L/L^natural-convex theory in the second step. In the last step, the optimal number of SUs participating in sensing is obtained based on the SU assignment obtained in step two. By combining these three steps, a complete and efficient SU assignment scheme is obtained. Numerical results are provided to evaluate the performance of our proposed SU assignment scheme and validate the theoretical analysis.

One of the most attractive features that computing clouds can offer is that the data center maintenance cost can be reduced by consolidating the workload generated by the virtual machines (VMs) into a few powerful physical servers. In this paper, the problem of maximally consolidating heterogeneous virtual machines into servers while protecting the service level agreement of each virtual machine is investigated. A generic and robust VM workload consolidation framework is proposed. The proposed framework achieves several attractive properties like low maintenance cost, low algorithm complexity, adjustable resource provisioning aggressiveness, and good scalability.

Cooperative spectrum sensing, which provides an effective approach to improve the sensing performance and better exploit the spectrum opportunities, is an important technology to enable the implementation of Cognitive Radio Networks (CRNs). The most fundamental and practical problem of cooperative spectrum sensing is: how to appropriately schedule Secondary Users (SUs) to sense multiple primary channels? In this paper, we study this Cooperative Sensing Scheduling (CSS) problem in the context of energy-aware CRNs. The CSS problem is modeled as a combinatorial optimization problem with the objective of improving energy efficiency in CRNs. Different from general approaches which employ heuristic methods to solve such combinatorial optimization problem, we propose a theoretical framework and analytically study the problem. Some interesting and important properties are obtained, while a simple but robust algorithm that guarantees to find the optimal solution efficiently is developed based on our findings. By observing that our problem shares a general form as studied in many other topics, we also discuss about the potential applications of our framework.

In this paper, we study the revenue sharing and rate allocation for Internet Service Providers (ISPs) that jointly provide network connectivity between content providers and end-users. Without colluding, each ISP may selfishly set a high transit-price to cover its cost and maximize its own profit, which inevitably results in a loss in social profit. We model this noncooperative interaction between an “eyeball” ISP and a “content” ISP as a Stackelberg game and quantify the resulting loss in social profit. To recover the profit loss, we propose a revenue sharing contract between ISPs by modeling them as a supply chain to deliver traffic in a two-sided market. Parameterized by the profit division factor, the sharing contract coordinates ISPs' objectives such that they aim to maximize the social profit self-incentively. We further propose a Nash bargaining process to determine the profit division factor such that all ISPs are simultaneously better off compared to the noncooperative equilibrium.

Due to the problem of spectrum scarcity and large energy consumption in wireless communications, designing energy-efficient Cognitive Radio Networks (CRNs) becomes important and necessary. In this paper, we consider the problem of optimal Cooperative Sensing Scheduling (CSS) and parameter design to achieve energy efficiency in CRNs using the framework of Partially Observable Markov Decision Process (POMDP). In particular, we consider the CSS problem for a CRN with M Secondary Users (SUs) and N primary channels to determine how many SUs should be assigned to sense each channel in order to maximize the objective function that is related to energy efficiency. By assigning more SUs to sense one channel, higher sensing accuracy can be gained; however, by spreading out the SUs to sense more channels, spectrum opportunities can be better exploited. The CSS problem is formulated as a combinatorial optimization problem. While such problem is generally hard and can only be solved by numerical methods with high computation complexity, in this paper we provide a detailed analysis and the analytical results provide useful and interesting insights. The optimality of the myopic CSS is proved for the case of two channels, and it is also conjectured for the general case. We also study the tradeoff between the sensing and transmission durations. In addition, the structure of the optimal sensing time that maximizes the energy efficiency objective is also analyzed, the condition for the optimality of the myopic sensing time is obtained, and the performance upper bound of the myopic policy is derived. Based on the numerical results, we show that by carefully tuning a punishment parameter, better energy efficiency can be achieved.

Cooperative spectrum sensing, which can profoundly improve the ability of discovering the spectrum opportunities, is regarded as an enabling mechanism for Cognitive Radio Networks (CRNs). One of the most fundamental problems in cooperative spectrum sensing is how to assign Secondary Users (SUs) to sense different primary channels such that SUs can achieve a good balance between sensing accuracy and the exploration of potential “spectrum holes”. This problem becomes more challenging when the primary channels require heterogeneous detection probabilities for incumbent protection. In this paper, the Cooperative Sensing Scheduling with QoS guarantee (CSS-Q) problem is studied for designing energy-efficient CRNs.We first explore the inherent structure of the CSS-Q problem and find several useful properties for it. Then, based on these properties a novel and efficient algorithm is proposed to solve the problem optimally. Sufficient numerical results are also presented to validate our analysis.

We propose an approximate model for a nonsaturated IEEE 802.11 DCF network. This model captures the significant influence of an arbitrary node transmit buffer size on the network performance. We find that increasing the buffer size can improve the throughput slightly but can lead to a dramatic increase in the packet delay without necessarily a corresponding reduction in the packet loss rate. This result suggests that there may be little benefit in provisioning very large buffers, even for loss-sensitive applications. Our model outperforms prior models in terms of simplicity, computation speed, and accuracy. The simplicity stems from using a renewal theory approach for the collision probability instead of the usual multidimensional Markov chain, and it makes our model easier to understand, manipulate and extend; for instance, we are able to use our model to investigate the important problem of convergence of the collision probability calculation. The remarkable improvement in the computation speed is due to the use of an efficient numerical transform inversion algorithm to invert generating functions of key parameters of the model. The accuracy is due to a carefully constructed model for the service time distribution. We verify our model using ns-2 simulation and show that our analytical results based on an M/G/1/K queuing model are able to accurately predict a wide range of performance metrics, including the packet loss rate and the waiting time distribution. In contradiction to claims by other authors, we show that 1) a nonsaturated DCF model like ours that makes use of decoupling assumptions for the collision probability and queuing dynamics can produce accurate predictions of metrics other than just the throughput, and 2) the actual service time and waiting time distributions for DCF networks have truncated heavy-tailed shapes (i.e., appear initially straight on a log-log plot) rather than exponential shapes. Our work will help developers select appropriate buffer sizes for 802.11 devices, and will help system administrators predict the performance of applications.

This paper proposes a simple and practical call admission control (CAC) scheme for one-hop IEEE 802.11 distributed coordination function (DCF) networks in heterogeneous environments. The proposed scheme is the first CAC scheme derived from an asymptotic analysis of the critical traffic load, where the critical traffic load represents the threshold for queue stability. The salient feature of our CAC scheme is that it can be performed quickly and easily without the need for network performance measurements and complex calculations. Using the proposed scheme, we specifically investigate the voice capacity of 802.11 DCF networks with unbalanced traffic. Extensive simulations covering both ad hoc and infrastructure-based networks, and a variety of nonsaturated traffic types, show that the proposed CAC scheme is very effective.

In this work we study joint pricing and power allocation for Dynamic Spectrum Access (DSA) networks with Stackelberg game. In our model, Primary User (PU) is the game leader and jointly determines its power allocation (to guarantee its QoS requirement) and the interference price charged to Secondary User (SU) (to reap revenue). Meanwhile, SU is the game follower and determines its power demand in response to PU's decisions. We quantify PU's and SU's benefit from the channel sharing model by deriving the Stackelberg equilibrium. Our results show that PU's equilibrium profit is asymptotically upper bounded with its marginal power cost and rate requirement. A distributed algorithm is proposed to find the equilibrium. We also propose an incentive-compatible mechanism for PU and SU to keep the social welfare optimum cooperatively. We extend our Stackelberg game to the multiple SUs scenario, where the interference among SUs results in a noncooperative power demand subgame. We propose a low-complexity heuristic algorithm for PU to maximize its profit. Our results show that PU can benefit by selecting multiple SUs to share its channel if SUs' mutual interference is limited.

The P2P pull-push hybrid architecture has achieved great success in delivering live video traffic over the Internet. However, a formal study on the sub-stream scheduling problem, a key design issue in hybrid systems, is still lacking. In this paper, we propose a max-flow model for mathematical analysis of this problem. We find that the sub-stream scheduling schemes used in existing hybrid systems, including CoolStreaming+, GridMedia and LStreaming, individually solve one special case of the proposed max-flow model. Moreover, this model can also serve as a benchmark to assess the performance of these existing sub-stream scheduling schemes. Further, we propose a weighted max-flow scheme to address the issue of peer heterogeneity in scheduling sub-streams. Finally, we point out the benefits of combining the hybrid streaming architecture and layered coding, and we also investigate how to schedule sub-streams in hybrid layered streaming systems.

In this paper we study the joint rate allocation, routing and spectrum sharing policy for multi-hop Cognitive Radio Networks (CRNs). We formulate this cross layer optimization problem as a sequential decision process which aims to minimize the average total power consumption of CRNs in each scheduling cycle under the constraint that each Cognitive Radio (CR) user's traffic demand is guaranteed. We consider imperfect spectrum sensing in our problem formulation and address Primary Users (PUs) protection with the interference regulation. We use Dynamic Programming (DP) to solve the formulated problem and derive the optimal rate allocation, routing and spectrum sharing policy for CRNs.

For peer-to-peer (P2P) networks continually to flourish, QoS provision is critical. However, the P2P networks are notoriously dynamic and heterogeneous. As a result, QoS provision in P2P networks is a challenging task with nodes of the varying and intermittent throughput. This raises a fundamental problem: is stable and delicate QoS provision achievable in the highly dynamic and heterogeneous P2P networks? In this work, we investigate BitTorrent (BT) with the particular interest in its QoS performance in the highly dynamic and heterogeneous network. Our contributions are two-fold. First, we develop an analytical model to examine a randomly selected BT node under a microscope. Based on the model, we study the mean and variance of nodal download rate in the dynamic network and the performance of BT in QoS provision under different levels of peer churns. Our analysis unveils that although BT strives to provide nodes with guaranteed throughput, due to the network dynamics, the download rates of the peers oscillate extraordinarily and can hardly converge to the target QoS as proposed in previous literature. Second, to improve the QoS provision, we propose an enhanced protocol incorporating with BT. The proposed protocol enables nodes to quickly and elaborately search their uploaders, and as a result, achieve guaranteed and stable QoS in the dynamic networks. Using both analysis and simulations, we validate the effectiveness of the proposed protocol in comparisons with the original BT.

Usage-based pricing has been recognized as a network congestion management tool. Internet Service Providers (ISPs), however, have limited ability to set time-adaptive usage-price to manage congestion arising from time-varying consumer utility for data. To achieve the maximum revenue, ISP can set its time-invariant usage-price low enough to aggressively encourage consumer's traffic demand. The downside is that ISP has to drop consumer's excessive traffic demand through congestion management (i.e., packet dropping), which may degrade Quality of Service (QoS) of consumer's traffic. Alternatively, to protect consumer's QoS, ISP can set its time-invariant usage-price high enough to reduce consumer's traffic demand, thus minimizing the need for congestion management through packet dropping. The downside is that ISP suffers a revenue loss due to the inefficient usage of its network. The tradeoff between ISP's revenue maximization and consumer's QoS protection motivates us to study ISP's revenue maximization subject to QoS constraint in terms of the number of packets dropped. We investigate two different QoS measures: short-term per-slot packet dropping constraint and long-term packet dropping constraint. The short-term constraint can be interpreted as a more transparent congestion management practice compared to the long-term constraint. We analyze ISP's optimal time-invariant pricing for both constraints, and develop an upper bound for the optimal revenue by considering the specified packet dropping threshold. We quantify the impact of consumer's price elasticity on ISP's optimal revenue and show that ISP should carry out a differentiated QoS protection strategy based on consumer's price elasticity in order to mitigate the revenue loss1.

This paper proposes a new call admission control (CAC) scheme for one-hop homogeneous 802.11 DCF networks. Using the proposed scheme, we can perform admission control quickly and easily without the need for network performance measurements and complex calculations. The CAC rule is derived under asymptotic conditions, but our extensive numerical examples show that it works well for practical-sized networks with a finite retransmission limit and realistic nonsaturated traffic.

Abstract To prolong the battery lifetime, it is important to continue designing a better energy efficient mechanism for different mobile technologies. Most of the existing works on the IEEE 802.16e sleep mode operation focus on the decision making before a mobile station switching to sleep mode state. The correlation of the decision is mainly on when and how to sleep based on the traffic demands. After the mobile station is switched to sleep mode, the deactivation of it mainly depends on new incoming traffic regardless of the actual amount. Truly, frequent switching can increase the energy cost on the mobile station, which can significantly reduce the battery lifetime. To minimize the switching frequency, we propose a novel approach to resolve this issue by making a heuristic decision during the listening interval. With this aim, we propose a real‐time heuristic algorithm, WAKSLP_DECISION, to accommodate our target. Three main decision criteria are analyzed and designed, namely the probability of buffer overflow, expected delay violation, and battery lifetime expiry, to achieve our goal. We verify the energy consumption performance with simulation experiments to validate our proposed scheme. The result shows that our scheme performs 25–30% better compared with the original standard in terms of energy consumption. We believe this algorithm is practical and implementable without changing the original standard, which can contribute both in the research community and industrial development. Copyright © 2009 John Wiley & Sons, Ltd.

The IEEE 802.16e mobile WiMAX technology aims to provide with an energy efficient communication platform for various mobile applications. In the standard, the sleep mode feature with three Power Saving Classes (PSCs) is designed to compensate for the power saving as the target. Prior work has shown that the proposed Markov Decision Process (MDP) approach can achieve the optimal performance in terms of energy consumption and packet delay through the optimal PSC selection. In this paper, we further consider the design of when to sleep and how to sleep in the system to achieve better tradeoffs between the switching frequency during idle mode and mean power consumption in overall. First, we present our optimal timeout scheme designed based on the previous proposed MDP approach, which can help the system determine when to sleep as well as how to sleep optimally with less switching frequency intuitively. To guarantee the optimality, we show the equivalency of the MDP approach and our optimal timeout scheme that both can achieve the optimal performance in terms of energy consumption level. Also, we demonstrate the performance of our proposed scheme through numerical analysis and validate it with simulation experiments using ns-2 compared with the MDP approach. Finally, we evaluate the impact of Poisson and non-Poisson traffic on our proposed optimal scheme.

In this paper we study the distributed multi-channel power allocation for spectrum sharing cognitive radio networks with QoS guarantee. We formulate this problem as a non- cooperative game GMCPA-Cwith coupled strategy space to address both the co-channel interference among secondary users and the interference temperature regulation imposed by primary systems. We investigate the properties of Nash equilibrium (N.E.) for our GMCPA-C, including the existence and QoS provisioning. Furthermore, we derive a layered structure by applying the Lagrangian dual decomposition to GMCPA-Cand design a distributed algorithm to find the N.E. via this structure. Simulation results are presented to show both the validity of our game theoretic model and the performance of our proposed algorithm. Finally, we incorporate the Pigouvian taxation into our algorithm to improve the efficiency of N.E. when social optimality is considered.

To prolong the battery lifetime, it is important to continue designing a better energy efficient mechanism for different mobile technologies. Most of the existing works on the IEEE 802.16e sleep mode operation focus on the decision making before a mobile station switching to sleep mode state. The correlation of the decision is mainly on when and how to sleep based on the traffic demands. After the mobile station is switched to sleep mode, the deactivation of it mainly depends on new incoming traffic regardless of the actual amount. Truly, frequent switching can increase the energy cost on the mobile station, which can significantly reduce the battery lifetime. To minimize the switching frequency, we propose a novel approach to resolve this issue by making a heuristic decision during the listening interval. With this aim, we propose a real-time heuristic algorithm, WAKSLP_DECISION, to accommodate our target. Three main decision criteria are analyzed and designed, namely the probability of buffer overflow, expected delay violation, and battery lifetime expiry, to achieve our goal. We verify the energy consumption performance with simulation experiments to validate our proposed scheme. The result shows that our scheme performs 25% to 30% better compared with the original standard in terms of energy consumption. We believe this algorithm is practical and implementable without changing the original standard, which can contribute both in the research community and industrial development.

We propose an approximate model for a nonsaturated IEEE 802.11 DCF network that is simpler than others that have appeared in the literature. Our key simplification is that the attempt rate in the nonsaturated setting can be approximated by scaling the attempt rate of the saturated setting with an appropriate factor. Use of different scaling factors leads to variants of the model for a small buffer and an infinite buffer. We develop a general fixed-point analysis that we demonstrate can have nonunique solutions for the infinite buffer model variant under moderate traffic. Nevertheless, in an asymptotic regime that applies to light traffic, we are able to prove uniqueness of the fixed point and predict the offered load at which the maximum throughput is achieved. We verify our model using ns-2 simulation and show that our MAC access delay results are the most accurate among related work, while our collision probability and throughput results achieve comparable accuracy to (D. Malone et al., 2007), (K. Duffy et al., 2007).

Energy efficiency in mobile devices remains a critical issue in the design of wireless communication system. In order to provide a high quality of service (QoS), the IEEE 802.16e-2005 standard supports three unique power saving classes (PSCs) which aim to reduce the power consumption of mobile devices based on the different types of traffic. Our goal is to design an optimal sleep mode selection scheme so as to maximize the energy efficiency in a mobile WiMAX system while providing a certain QoS guarantee. In this paper, we propose a theoretical framework based on the semi-Markov decision process along with a performance evaluation on the sleep mode operation. Based on this model, we formulate a stochastic optimization problem and solve it through our novel policy optimization algorithm, which is capable of finding the optimal policy for the selection of different PSCs. The numerical and simulation results demonstrate the validity of our proposed scheme under different QoS requirements such as the packet delay and energy consumption level. We believe that our scheme has achieved a high energy efficiency and is best fit to the IEEE 802.16e mobile system.

While the overall bandwidth of peer-to-peer live video streaming system scales automatically as peers collectively contribute the bandwidth, each peer also demands to download at the specified video playback rate so as to play the video smoothly. Therefore, a fundamental problem arisen is how to balance the bandwidth supply and demand in the peer-to-peer system to enjoy peers with the best video quality. To address this problem, we propose a fully distributed peer-to-peer video streaming framework which automatically adapts the network towards full bandwidth utilization. Our design possesses two unique features. First, a speciallink-level homogenousoverlay network is formed in which all the overlay links approach to have an identical bandwidth value. With such a feature, video flowing through the overlay links will not encounter any bottlenecks, and peers can thus achieve the guaranteed downloading rates. Second, based on the peer downloading rate observed locally at the streaming server, the server can adaptively adjust the video playback rate so that peers can achieve the best video quality with full bandwidth utilization. The effectiveness of our framework is verified through extensive simulations.

In this paper, we propose a cross-layer optimization framework to jointly design the spectrum sharing and flow routing with the interference considerations in cognitive radio networks. Given multiple traffic demands from different source nodes to destination nodes, we formulate an optimization problem in the form of mixed integer linear programming (MILP) to provide a fair routing. Different from the existing work, we consider bi-directional links because we believe the link level acknowledgements in an ad-hoc network are a must. For traffic routing we allow multi-path for each traffic demand. Numerical results show that the spectrum sharing among the secondary users is interference-free and a fair routing is guaranteed for different traffic demands.

Cognitive radio technology solves the spectrum under-utilization problem by enabling the secondary users access the spectrum holes opportunistically. Therefore, how to efficiently share the spectrum holes among the secondary users is of interest. Previous studies on spectrum sharing focused on the formulations with homogeneous channels. The channel heterogeneity, which is a unique feature in cognitive radio networks, has been ignored. In this paper, we consider heterogeneous channels and explore the impact of channel heterogeneity on the spectrum sharing. We model the channel heterogeneity, interference constraints and spectrum sharing, and formulate an optimization problem in the form of binary integer linear programming (BILP). To the best of our knowledge this is the first attempt to model the channel heterogeneity into the formulation of spectrum sharing in cognitive radio networks. Numerical results show that the optimal solution on spectrum sharing is highly dependent on the channel heterogeneity.

P2P live streaming systems are developed in two major approaches: tree-push versus mesh-pull. The hybrid push-pull streaming, as an emerging and promising approach, offers a good tradeoff between traffic overhead and system throughput. In this paper, we demonstrate that video redundancy is a large c

In this paper, we study the joint rate and multi-channel power allocations in spectrum sharing networks (SSNs) with balanced QoS provisioning and power saving. We formulate this cross layer problem as a non-cooperative game GJRPA in which each user aims to achieve its target data rate as exactly as

In this paper, we study the distributed multichannel power allocation (MCPA) problem for the spectrum sharing cognitive radio networks (CRNs), where secondary transceiver pairs share the same spectrum with the primary system. The problem is formulated as a non-cooperative game with coupled constraints to address the interference temperature restrictions imposed by the primary system. Existence and uniqueness of the Nash Equilibrium (N.E.) for this coupled constraints MCPA game are investigated. Distributed MCPA algorithm is proposed to approach the unique N.E. Simulation results are obtained to verify the validity of the proposed algorithm.

IEEE 802.11e standard develops a reference design for a sample scheduler and admission control unit to support the contention-free access. However, the reference design can not efficiently utilize the bandwidth. This paper proposes an equalspacing- based (equal-SP) design to address the problem. In the equal-SP design, which generalizes the reference design, each stream is scheduled with equal-spacing and different streams are scheduled with different spacings. The equal-SP design not only keeps all advantages of the reference design (i.e., it is simple, easy to implement, and can guarantee the delay requirement), but it is compatible with the standard and can also utilize the bandwidth efficiently.

IEEE 802.11e standard develops a reference design to support the contention-free access. In the reference design, the packet transmission opportunity (TXOP) duration is calculated based on the mean data rate and the mean packet size, whereas the scheduled service interval (SI) is calculated based on the most stringent delay requirement. Such design can not effectively utilize the bandwidth and support the guaranteed packet loss requirement. This paper proposes a packet-loss-based and bandwidth-utilization-based (PB-based) design to address the two problems. In the PB-based design, the TXOP is calculated based on the data rate and packet size fluctuation, whereas the SI is calculated based on different delay requirements. In addition, when packet loss requirement is not taken into account, we propose an equal-spacing-based (ES-based) design to improve the bandwidth utilization. The proposed designs are helpful to provide more comprehensive QoS support.

When constructing an unstructured P2P topology, one should consider the application running on top of it in order to achieve a good performance for the whole P2P system. It is not enough only to consider the "topology" objective when forming an overlay such as minimizing a P2P network diameter because it does not achieve a good performance for the whole P2P system. For example, minimizing a P2P network diameter may overload some peers under a flooding search application because of their excess connections. Therefore, one should consider the behavior of the application on top of the topology such that the topology can adapt itself in order to benefit the application. To fulfil this objective, we propose an application-aware topology formation algorithm which can be "tuned" so as to achieve load-balancing for a spectrum of P2P applications. Furthermore, we provide a very detailed analytical model to understand the behavior of our algorithm under any heterogeneous environment. The analytical results are validated by the simulations.

Wireless mesh networks (WMNs) have emerged as a key technology for the next-generation wireless networking. Due to infrequent topology change and unreliable wireless links, a fundamental problem arisen is how to form an optimal topology to meet the traffic requirement. In this paper, we propose a joint optimization design on topology formation and traffic routing, which is formulated as a linear binary programming (LBP) problem. Since LBP is difficult to solve except for very small-size problems, we provide an efficient approximation method based on the decomposition method. Numerical results show that our approximation method not only obtains a very good performance, but also it reduces the number of network interfaces required by mesh nodes. Moreover, our approximation method significantly reduces the computation complexity and is capable of providing solution to practical problems when mathematical packages cannot offer a feasible solution.

IEEE 802.11e standard develops a reference design for a sample scheduler and admission control unit to support the contention-free access. However, the reference design can not effectively utilize the bandwidth. This paper proposes an equal-spacing-based (equal-SP) design to address the problem. In the equal-SP design, which generalizes the reference design, each stream is scheduled with equal-spacing and different streams are scheduled with different equal-spacings. The equal-SP design not only keeps all advantages of the reference design, but it can also utilize the bandwidth effectively.

The new IEEE 802.16e standard introduces two types of sleep modes for energy-efficient operations: power saving classes (PSCs) of type I based on binary-increasing sleep window size and PSCs of type II using constant sleep window size. This paper determines the optimal sleep mode selection for IEEE 802.16e by using the semi-Markov decision processes (semi-MDP). By means of evaluating corresponding cost metrics on system energy consumption and delay performance, we highlight the energy-performance trade-offs among different operational modes and formulate it as probabilistic constrained policy optimization (PO) problems. Our main goal is to search the space of all policies and to find the optimal one that achieves the minimum energy cost or traffic delay under different traffic requirements. Numerical results demonstrate the effectiveness of our semi-MDP method. We also investigate how the energy cost, delay penalty, as well as user objective jointly affect the space of the optimal policies.

The eleven papers in this special issue are devoted to advancements in peer-to-peer streaming systems.

Many communication and networking systems can be modeled as resource-sharing systems with multiple classes of calls. Call admission control (CAC) is an essential component of such systems. Markov decision process (MDP) tools can be applied to analyze and compute the optimal CAC policy that optimizes certain performance metrics of the system. But for most practical systems, it is prohibitively difficult to compute the optimal CAC policy using any MDP algorithm because of the "curse of dimensionality". We are, therefore, motivated to consider two families of structured CAC policies: reservation and threshold policies. These policies are easy to implement and have good performance in practice. However, since the number of structured policies grows exponentially with the number of call classes and the capacity of the system, finding the optimal structured policy is a complex unsolved problem. In this paper, we develop fast and efficient search algorithms to determine the parameters of the structured policies. We prove the convergence of the algorithms. Through extensive numerical experiments, we show that the search algorithms converge quickly and work for systems with large capacity and many call classes. In addition, the returned structured policies have optimal or near-optimal performance, and outperform those structured policies with parameters chosen based on simple heuristics

The IEEE 802.16e standard introduces two types of sleep modes which perform very differently under different traffic types: power saving classes of type I based on binary-increasing sleep window size and power saving of type II using constant sleep window size. This paper provides simple but accurate analytical models capable of calculating the power efficiency and packet access delay for the two power saving types. In addition, a comparison of the energy efficiency and delay performance between the two power saving types is reported. By means of the proposed model and evaluation, we point out the trade-off between these two types and suggest a power switching scheme to obtain optimal power efficiency under different traffic conditions. Numerical and simulation results are provided for validation of our models

The design of the medium-access control (MAC) protocol is the most crucial aspect for high-speed and high-performance local and metropolitan area networks, since the decisions made at this level determine the major functional characteristics of these networks. Most of the MAC protocols proposed in the literature are not suitable for multimedia applications, since they have been designed with one generic traffic type in mind. As a result, they perform quite well for the traffic types they have been designed for, but poorly for other traffic streams with different characteristics. In this paper, we propose an integrated MAC protocol called the Multimedia-MAC (M-MAC), which integrates different MAC protocols into a hybrid protocol in a shared-medium network to efficiently accommodate various types of multimedia traffic streams with different characteristics and quality-of-service demands, namely, a constant-bit-rate traffic, bursty traffic (say, variable-bit-rate traffic), and emergency messages (say, control messages). We have developed a mathematical framework for the analysis and performance evaluation of our M-MAC protocol, which involves a queueing system with vacation. We have applied our M-MAC design approach to a wavelength-division multiplexing network, and evaluated its performance under various traffic conditions.

End-to-end available bandwidth estimation is important in understanding network congestion and enhancing service quality. In this paper, we investigate a light-weight probing method for available bandwidth measurement in a queueing analysis approach. Unlike the self-congestion based measurement approach, a light-weight probing technique infers the available bandwidth along a path without congesting the routers along the path. Of particular interest in our investigations, is the squared coefficient of variation (SCV) of the inter-departure process of a periodic probing stream. We analyze approximately the departure process of this probing stream. Simulation results indicate that the proposed hybrid approximation can provide good estimates of the SCV of the probing stream regardless of the stochastic behavior of the arrival process of the cross traffic. Given a measured SCV, inverting this approximation infers the load of the cross traffic on the congested link.

Many communications and networking systems can be modelled as resource-sharing systems with multiple classes of calls. Call admission control (CAC) is an essential component of such systems. For most practical systems it is prohibitively difficult to compute the optimal CAC policy that optimizes certain performance metrics because of the 'curse of dimensionality'. In this paper we study two families of structured CAC policies: threshold and reservation policies. These policies are easy to implement and have good performance in practice. However, since the number of structured policies grows exponentially with the number of call classes and the capacity of the system, finding the optimal structured policies is a complex unsolved problem. In this paper efficient search algorithms are proposed to find the coordinate optimal structured policies among all structured policies. Through extensive numerical experiments we show that the search algorithms converge quickly and work for systems with large capacity and many call classes. In addition, the returned structured policies have optimal or near-optimal performance, and outperform those structured policies with parameters chosen based on simple heuristics.

In IEEE 802.11 WLANs, there are two types of access modes which perform very differently under different channel or traffic conditions: the basic access mode CSMA/CA and and an RTS/CTS based mechanisms. In seeking to balance between the use of the different modes, the contribution of this paper is threefold. Firstly, we present our development of a new method capable of calculating the access delay via an analytical model. Secondly, we report a comparison of the throughput and delay performance of basic and RTS/CTS mechanisms and the analysis of which mode should be chosen to obtain better throughput and delay performance under different conditions. Finally, we propose an adaptive RTS/CST mechanism that adjusts the RTS threshold adaptively in order to achieve optimal performance in a centralized or distributed way. Numerical results, and simulation results obtained using NS2 are provided.

The IEEE 802.11 working group is currently working on the standard IEEE 802.11e and introduces the hybrid coordination function (HCF) to provide better QoS support to real-time traffic. A reference design of simple scheduling and admission control algorithm is proposed in a TGe consensus proposal. However, this scheduling and admission control unit only consider the mean data rate and mean packet size. The rate and packet size variation are not taken into account. Thus, it is only efficient to CBR traffic and the packet loss rate of VBR traffic may be very high. In W. F. Fan et al. (Aug. 2004), we analyzed the packet loss rate of the reference scheme and proposed a new method to determine the effective TXOP duration for admission control so that the packet loss rate of VBR flows can be guaranteed. In both reference and our proposed scheme, all stations use fixed schedule service interval (SI) which is the minimum of all maximum service interval of all admitted flows. Thus, maximum packet delay of all stations is limited by the most stringent SI and some traffic with larger delay bound may be over-guaranteed. Also, the efficiency of the admission control scheme in W. F. Fan et al. (Aug. 2004), becomes lower than that of the reference one. We extend our admission control scheme by using variable service interval to improve the efficiency about 20% - 30% and avoid over guarantee on packet delay. Also, the packet loss rate of VBR traffic can be guaranteed.

In this paper, we investigated a non-intrusive probing methodology for available bandwidth measurement based on the analysis of the departure process of an active Poisson probing stream. Unlike the self-congestion based available bandwidth measurement, non intrusive techniques are meant to infer the available bandwidth along a path without congesting the path. We propose to probe the end-to-end path using small size packets with exponentially distributed time between consecutive probing packets. Of particular interest to our investigations, is the squared coefficient of variation (SCV) of the inter-departure process of the probing stream. The Internet is modelled as single server queue with two concurrent streams, the probing traffic stream and the cross traffic, we rely on the results on M/sub 1/ + M/sub 2//GI/sub i//1 queueing system and a heavy traffic approximation model to analyze the departure process of the probing stream. Thus, in a real measurement system, given the measured SCV of the probing stream, inverting the approximation helps inferring the load of the cross traffic on an end-to-end-path.

IEEE 802.11 wireless LAN is considered one of the most popular wireless technology all over the world because of its low cost and easy deployment. The support of quality of service (QoS) in medium access control (MAC) protocol is important in meeting the QoS requirements of real-time traffic such as guaranteed packet delay and packet loss probability. In this paper, the performance of the proposed admission control algorithm and different VBR video traffic are analyzed. In the analysis, three mean data rates of video flows ( 300 kbps, 600 kbps and 1 Mbps) were also considered.

We first present our recent work on the non-saturation modelling and performance analysis for IEEE 802.11 distributed coordination function. We extended the previous work and developed a model capable of reflecting the non-saturation condition. Employing the model, by introducing a concept of equivalent competing entity, we designed a measurement-aided model-based call admission control scheme for IEEE 802.11e WLANs contention-based channel access - enhanced distributed coordination function (EDCF) to provide guaranteed throughput quality of service (QoS) in a statistical sense. Extensive numerical and simulation results are provided.

The new standard IEEE 802.11e is specified to support quality-of-service in wireless local area networks. A comprehensive study of the performance of enhanced distributed channel access (EDCA), the fundamental medium access control mechanism in IEEE 802.11e, is reported in this paper. We present our development of an analytical model, in which most new features of the EDCA such as virtual collision, different arbitration interframe space (AIFS), and different contention window are taken into account. Based on the model, we analyze the throughput performance of differentiated service traffic and propose a recursive method capable of calculating the mean access delay. Service differentiation functionality and effectiveness of the EDCA are investigated through extensive numerical and simulation results. The model and the analysis provide an in-depth understanding and insights into the protocol and the effects of different parameters on the performance.

We address the problem of the performance analysis of the stochastic fair sharing (SFS) algorithm for fair link sharing. The SFS scheme has been proposed to carry out a fair link sharing and fair sharing among virtual private networks. Depending upon the current utilization and provisioned capacities of the classes, the SFS admission control algorithm decides which sessions to accept and which to reject. In this letter, we undertake the performance evaluation of the SFS scheme analytically. We explore the tradeoff between fairness and the blocking probability by varying the trunk reservation parameter. The results show that the analytical performance measure agrees well with the simulation results.

Content delivery network (CDN) is an intermediate layer of infrastructure that helps to efficiently deliver the ever increasing multimedia content from content providers to a large community of geographically distributed clients. Content routing is an essential component of CDN architecture. In this paper we propose a hierarchical content routing architecture for large-scale CDN, in which CDN servers perform inter-cluster content routing based on two-level hierarchical overlay network. We analyze the routing overhead and the corresponding CDN performance of different intra-cluster content routing schemes. In particular, we propose a semi-hashing based scheme for intra-cluster content routing and a content-query based scheme for inter-cluster content routing. Through qualitative analysis and simulations we show that the semi-hashing based scheme is scalable (small routing overhead), efficient (high content sharing efficiency), and flexible (adjustable parameters).

The proportional service model is receiving a lot of attention a an attractive model for providing differentiated services on the Internet. In particular, this model is controllable, able to provide the "tuning knobs" for network operators to quantitatively differentiate the quality-of-service (QoS) of different classes, and lends itself naturally to simple pricing schemes. We focus on the issue of how to practically implement such a QoS differentiation scheme at high-speed routers using efficient buffer management and packet scheduling mechanisms. We first propose a uniform scheduler. Unlike previously proposed schedulers which can be used only for a single QoS metric, our scheduler is suitable for various QoS metrics. We then introduce a new packet dropping mechanism with an active counter resetting scheme that compare favorably with previous schemes. Finally, we develop an original and simple approach for the integration of absolute QoS constraints with the proportional differentiation paradigm.

We address the problem of the performance analysis of the stochastic fair sharing (SFS) algorithm for fair link sharing. The SFS scheme has been proposed (see Garg, R. and Saran, H., Infocom, 2000) to carry out a fair link sharing and fair sharing among virtual private networks (VPNs). Depending on the current utilization and provisioned capacities of the classes, the SFS admission control algorithm decides which sessions to accept and which to reject. We undertake the performance evaluation of the SFS scheme analytically. The main performance measure in our analysis is the session blocking probability. In particular, we obtain the Roberts-Kaufman like recursion (see Kaufman, J.S., IEEE Trans. Commun., vol.COM-29, no.19, p.1474-81, 1981) for the SFS scheme to compute the blocking probability. We then use linear programming techniques to compute the blocking probability from the above recursion.

Optical burst switching (OBS) is considered as an efficient switching technique for building the next generation optical Internet. An offset-time based scheme has recently been proposed in order to provide quality-of-service (QoS) in OBS networks. Unfortunately, the proposed service differentiation has several problems. The aim of this paper is to address these problems and introduce the concept of proportional QoS into this OBS paradigm. An intentional dropping scheme is proposed so as to give a controllable burst loss probability for different service classes. In order to achieve flexible packet delay differentiation, we extend the well-known waited-time-priority (WTP) scheduler to form a burst assembling scheme. Simulations are conducted to evaluate the performance of our proportional QoS provisioning within OBS networks in terms of burst loss probability and packet delay.

The multicast routing and wavelength assignment (MC-RWA) problem is generally studied with the objective of maximizing the number of multicast groups admitted, or equivalently, to minimize the call (or session) blocking probability given a certain number of wavelengths. While this approach is sound, a better objective is to maximize the total number of users served (i.e., minimizing the user blocking probability) by allowing part of a multicast group to be admitted. We present for the first time a formulation of the MC-RWA problem with such an objective. The formulation is a nonlinear integer program, which in general is complex to solve. We therefore propose a heuristic algorithm based on linear programming (LP). We further develop a simpler MAX-FIRST algorithm, which achieves almost the same performance as the LP algorithm. These algorithms are for static MC-RWA, where the multicast trees are predetermined and cannot be changed during the wavelength assignment. We extend the algorithms to dynamic MC-RWA, where new multicast trees can be built for unserved groups. We finally present upper and lower bounds on the user blocking probability for the static MC-RWA.

Conventional medium access control (MAC) protocols perform quite well for the traffic types they have been designed for, but poorly for other traffic streams with different characteristics. But, the emerging multimedia applications require that the MAC protocol should perform equally well for all types of traffic characteristics. We propose an integrated MAC protocol (termed the multimedia medium access control protocol (multimedia-MAC)) which integrates different MAC protocols into a hybrid protocol to efficiently accommodate various types of multimedia traffic streams with different characteristics and QoS demands. We have applied our multimedia-MAC design approach to wavelength division multiplexing (WDM) based optical network. We have developed a mathematical framework for the analysis and performance evaluation of our multimedia-MAC protocol which involves a queueing model with vacation.

The provision of scalable quality-of-service (QoS) guarantees on wavelength-division-multiplexing (WDM) networks is an important and challenging issue for the next generation Internet. One of the important performance metrics in a QoS-capable WDM network is the call blocking probability. Previously, a proportional differentiation model has been proposed as an effective method for scalable differentiated services provision. This model provides the network operators the ability of quantitatively adjusting the quality differentiation between service classes. We introduce this model into WDM networks with the aim of providing proportionally differentiated blocking probability to various traffic classes. An intentional blocking algorithm is proposed to implement this model at the wavelength level. In order to solve the link utilization degradation in this algorithm, we propose another intentional termination algorithm. Since the performance requirement from the network operator might be various, a hybrid algorithm is also given as a balance between the above two. These three algorithms are also suitable to TDM over WDM, where one connection only take part of the transmission capacity of one wavelength. Extensive simulation results demonstrate that our algorithms provide accurate and controllable differentiation on blocking probability between various traffic classes even in a bursty traffic situation. The infeasibility problem in proportional blocking probability provision is also discussed.

This paper proposes a simple rate-based scheduling algorithm for packet-switched networks. Using a set of counters to keep track of the credits accumulated by each traffic flow, the bandwidth share allocated to each flow, and the size of the head-of-line (HOL) packets of the different flows, the algorithm decides which flow to serve next. Our proposed algorithm requires on average a smaller complexity than the most interesting alternative ones while guaranteeing comparable fairness, delay, and delay jitter bounds. To further reduce the complexity, a simplified version (CBFQ-F) of the general algorithm is also proposed for networks with fixed packet lengths, such as ATM, by relaxing the fairness bound by a negligibly small amount.

In this paper, we investigate the dynamic multicast routing problem for single rate loss network and briefly discuss the dynamic multicast routing algorithm called least load multicast routing (LLMR). We propose a new multicast routing algorithm called maximum mean number of new calls accepted before blocking multicast routing (MCBMR), which can more accurately capture the current and future loading of a network. Simulation results show that this algorithm, compared with LLMR, not only has a smaller network revenue loss, but also results in smaller call blocking probabilities for all classes of traffic. We also discuss the implementation issues of our proposed algorithm and develop two approximation methods, state approximation and curve fitting, which can reduce the measurement complexity significantly with only a slight performance degradation.

We investigate a state dependent multicast routing algorithm called least load multicast routing (LLMR), for single rate loss networks. The algorithm is based on least load routing (LLR) concept and the approach is to select the least load links for establishing connections. The networks considered are assumed fully connected. In addition, connection requests are Poisson arrival and the holding times of accepted calls are exponentially distributed. The analytical model that we developed for calculating the blocking probabilities is based on the link independence assumption and the reduced load approximation (RLA). Analytical results are compared with simulation results and the agreement is surprisingly good. We find that the effect of link independence assumption is insignificant for the analytical model.

A service scheduling scheme that controls the order of servicing cells within an ATM node is very important in providing guaranteed services. Much attention has previously been paid to emulating the general processor sharing (GPS) system as closely as possible with low computational complexity. The primary motivation of emulating the GPS system is to provide traffic isolation and thus to achieve a maximum delay bound. This delay bound is guaranteed by guaranteeing the minimum bandwidth. However, after guaranteeing the minimum bandwidth, some excess bandwidth might be left over and we argue that it should be used more intelligently to improve other system performance. In this paper, we propose a novel scheduling scheme that guarantees each traffic stream a minimum bandwidth while achieving a low cell loss probability in a finite buffer ATM node.

Call admission control (CAC) is one of the key elements to provide quality of service (QoS) guarantee in wireless mobile networks. A good CAC scheme should efficiently support handoffs and maintain a high utilization of the scarce radio resource while it should also be simple for implementation. Since the traditional guard channel policy is not optimal for a hard constrained handoff dropping probability, new CAC algorithms have been studied in the literature. Among them, the distributed call admission control seems to be simpler and more efficient with regards to the above requirements. However, there are some problems in the original scheme which make the implementation complex and lead to performance degradation. In this paper, we will first discuss simplifications to the original scheme, and then further enhance the modified scheme by considering the difference of mobility support requirement between high and low mobility users. The simulation results show that the enhanced scheme gives better performance.

We propose a fuzzy logic-based control scheme for real-time motion picture expert group (MPEG) video to avoid long delay or excessive loss at the user-network interface (UNI) in an asynchronous transfer mode (ATM) network. The system consists of a shaper whose role is to smooth the MPEG output traffic to reduce the burstiness of the video stream. The input and output rates of the shaper buffer are controlled by two fuzzy logic-based controllers. To avoid a long delay at the shaper, the first controller aims to tune the output rate of the shaper in the video frame time scale based on the number of available transmission credits at the UNI and the occupancy of the shaper's buffer. Based on the average occupancy of the shaper's buffer and its variance, the second controller tunes the input rate to the shaper over a much larger time scale by applying a closed-loop MPEG encoding scheme. With this approach, the traffic enters the network at an almost constant bit rate (with a very small variation) allowing simple network management functions such as admission control and bandwidth allocation, while guaranteeing a relatively constant video quality since the encoding rate is changed only in critical periods when the shaper buffer "threatens" to overflow. The performance of the proposed scheme is evaluated through numerical tests on real video sequences.

The IEEE 802.14 standard committee is currently working on a project to find a cost-effective means of providing access to integrated networks for people to enjoy multimedia programs and to work at home. An advanced system based on the CATV system called hybrid fiber coax (HFC) is being studied. Since some properties of the HFC system preclude the possibility of directly using existing medium access control protocols for its data link layer, a MAC scheme based on time division is discussed in this paper.

With the increased popularity of ATM technology and the high demand for multimedia applications in wireless systems, the interconnection between wireless systems and wired ATM networks becomes important to support multimedia applications. This paper presents an AAL3/4-based architecture for the interconnection between wireless and ATM networks. The main advantage of this architecture is that modification or additional functions are not necessary to the ATM layer to support mobility, and the ATM part of the connection is totally transparent to the mobiles so that the existing wireless protocols can be used without any change.

We study the problem of dynamic bandwidth allocation for an ATM multiplexer loaded with real-rime VBR video traffic. The proposed mechanism adjusts the allocated bandwidth at regular intervals based on measured QoS. Instead of actual measurement of small cell loss ratios, we combine a virtual output buffer method with a regression method to shorten the time interval required for estimating the required bandwidth to support the specified QoS by prediction. Using numerical examples, we show that our proposed dynamic bandwidth allocation scheme is more efficient than the optimum static bandwidth allocation scheme. Our measurement-based scheme offers several advantages: (1) it removes the dependence on accurate traffic parameters to be declared by users; (2) it can be applied to a wide variety of traffic sources; (3) it adapts quickly to the variations of traffic with small measurement intervals, and (4) the complexity of the algorithm is small.

Hajek and Sasaki (1988) showed that, for continuous traffic and packet radio network, the selection of paths that minimize the maximum nodal degree generates schedules of minimum-length. This result suggests that minimization of the maximum nodal degree provides good (although not necessarily optimal) performance in slotted networks with fixed-length packets. We give a multispace search algorithm that interplays structural operations in conjunction with a local search algorithm for the minimization of the maximum nodal degree. Structural operations disturb the environment of forming local minima, which makes multispace search a very natural approach to the problem. Experimental results indicate that this method has improved local search in terms of the solution quality and its sensitivity to the initial random assignment.

Estimating the cell loss probability in an ATM multiplexer is a key issue in network management and traffic control such as call admission control and bandwidth allocation. In this paper, we derive a new approximation to estimate the total and individual cell loss probabilities in an ATM multiplexer fed by a superposition of heterogeneous on-off sources with exponentially distributed on and off periods. Based on this approximation, a simple and accurate method is proposed to estimate the aggregate required bandwidth by a given mix of traffic to guarantee a given cell loss probability.

A generalized fairness criterion referred to as the generalized weighted fairness criterion (GWFC) for flow control on an ABR service is presented. Within the GWFC framework, a weight is assigned to each ABR connection and bandwidth is allocated to it in proportion to the corresponding weight. The GWFC can generalize fairness sub-criteria for prioritized services, and in particular, subsume the max-min criterion as a uni-weight fairness criterion. Two weighted fairness sub-criteria are introduced and their performance on bandwidth allocation are presented and compared with that of the max-min criterion.

An important parameter in asynchronous transfer model (ATM)-based network design and management is the cell loss ratio (CLR) in ATM multiplexers. It is a key parameter to many vital functions in the network such as call admission control (CAC), bandwidth allocation, etc. However, the CLR depends usually on many unknown and unpredictable traffic parameters such as input traffic correlations. In this paper, we propose a simple and robust fuzzy-based algorithm to predict the CLR in large-sized systems based on both a small amount of information from small-sized systems, and the asymptotic behavior for very large systems. Unlike the model-based approaches, our approximation avoids the problem of assuming any traffic parameters or arrival process. This algorithm is used with real-time traffic measurement to propose an effective measurement-based call admission control framework for ATM networks.

A new rate-based switch mechanism for ABR traffic in ATM networks, which aims to rapidly achieve max-min fairness allocation, is proposed. Simulation results show that the proposed scheme can out-perform both CAPC and ERICA in terms of response times and peak queue lengths. An analytical approximation of the performance is also introduced and its accuracy is found to be close to the simulation results. A variant of the proposed scheme is presented for handling the problem of different source-to-bottleneck separations. By using this scheme, the peak queue lengths at the switches can further be reduced without any degradation in throughput.

In this paper, we study the bandwidth allocation problem for an ATM multiplexer loaded with compressed VBR video sources. To estimate the bandwidth required by a VBR video source, we characterize its traffic by five parameters: peak rate, bottom rate, mean rate, standard deviation, and the coefficient of the autocorrelation function. The aggregate traffic of a number of VBR video sources is modelled by a discrete-time Markov modulated deterministic process (D-MMDP) which is approximately equal to the superposition of a number of identical and independent two-active-state mini-sources. Based on the effective bandwidth approach and the Gaussian approximation, we derive simple formulas for estimating the required bandwidth.

Estimating the cell loss probability in an ATM multiplexer is one of the most important problems concerning congestion control and bandwidth management in an ATM-based BISDN. We propose a new approach to estimating the cell loss probability in an ATM multiplexer. We use the Markov modulated deterministic process (MMDP) to approximate the actual arrival process and then model the ATM multiplexer as an MMDP/D/1/K queueing system. Using queueing analysis, we derive a formula for the cell loss probability expressed in terms of the limiting probabilities of a Markov chain. We propose two approximation methods based on the results of the analysis. The actual arrival process is approximated by an (M+1)-state MMDP in the first method and by a two-state MMDP in the second. The major advantages of both methods are simplicity, computational efficiency, and numerical stability. The most attractive feature of the second method is that the cell loss probability can be expressed in closed form. Numerical and simulation results show that the first method is sufficiently accurate for all cases in which burst-level congestion is the main contributing factor to cell loss, while the closed-form formula is sufficiently accurate for applications where the average burst length is large (such as large file transfers, image retrievals, etc.).>

For future broadband-ISDN, asynchronous transfer mode (ATM) is designed not only to support a wide range of traffic classes with diverse flow characteristics (e.g., burstiness, bit rate and burst length), but to guarantee the different quality of service (QOS) requirements as well. The QOS may be measured in terms of cell loss probability and maximum cell delay. The authors consider the ATM network in which the virtual path (VP) concept is implemented. By applying the Markov modulated deterministic process method, they develop an efficient algorithm to compute the minimum capacity required to satisfy all the QOS requirements when multiple classes of on-off sources are multiplexed onto a single VP. Using the result, they then propose a simple algorithm to determine the VP combination to achieve the near optimum of the total capacity required for satisfying the individual QOS requirements. Numerical results are also presented to demonstrate the performance of the algorithm when compared to the optimal total capacity required.>

Although many closed multiclass queuing networks have a product-form solution, evaluating their performance measures remains nontrivial due to the presence of a normalization constant. We propose the application of Monte Carlo summation in order to determine the normalization constant, throughputs, and gradients of throughputs. A class of importance-sampling functions leads to a decomposition approach, where separate single-class problems are first solved in a setup module, and then the original problem is solved by aggregating the single-class solutions in an execution model. We also consider Monte Carlo methods for evaluating performance measures based on integral representations of the normalization constant; a theory for optimal importance sampling is developed. Computational examples are given that illustrate that the Monte Carlo methods are robust over a wide range of networks and can rapidly solve networks that cannot be handled by the techniques in the existing literature.

A circuit-switched network consisting of multiple-access links connected to a common link is considered. Each call requires circuits on one access link and on the common link. The network supports multiple classes of calls where each class specifies a bandwidth requirement, an arrival rate, and a holding-time distribution. Based on a product-form solution for these networks, four algorithms are developed to determine the exact blocking probability for each of the classes. The first two algorithms are based on convolution, the third on the fast Fourier transform, and the fourth on a recursion due to J.S. Kaufman (1981) and to J.W. Roberts (1981). Complexity bounds and numerical results demonstrate that these algorithms can determine blocking probabilities in reasonable CPU time for networks with thousands of circuits.>

The problem of packing a knapsack of integer volume F with objects from K different classes to maximize profit is studied. Optimization is carried out over the class of coordinate convex policies. For the case of K=2, it is shown for a wide range of parameters that the optimal control is of the threshold type. In the case of Poisson arrivals and of knapsack and object volumes being integer multiples of each other, it is shown that the optimal policy is always of the double-threshold type. An O(F) algorithm to determine the revenue of threshold policies is also given. For the general case of K classes, the problem of the optimal static control where for each class a portion of the knapsack is dedicated is considered. An efficient finite-stage dynamic programming algorithm for locating the optimal static control is presented. Furthermore, variants of the optimal static control which allow some sharing among classes are also discussed.>

The problem of determining optimal access policies for circuit-switched networks that support traffic types with varying bandwidth requirements is addressed. The authors suppose that the network supports K classes of calls where each class is determined by a fixed route and a bandwidth requirement. A Markov decision process (MDP) approach is used to obtain optimal access policies for three models: the flexible scheme access-port model where a single link is shared; the contiguous scheme access-port model where wideband calls are required to occupy specific contiguous regions of the TDM frame; and the network-access model where a call holds several channels in different links simultaneously. Both linear programming and value-iteration MDP algorithms are coupled with a novel state descriptor in order to locate the optimal policy for reasonable-size problems (several T1 carriers in parallel for the access-port case, and small networks of T1 carriers for the network-access case).>