The traditional goal in remote tracking of a dynamic source is to keep the current estimate at the destination as close as possible to the true state. However, in domains such as surveillance applications, the destination is also interested in reconstructing the past trajectory of states for further processing. This requires striking a balance between providing current versus past state information so that the destination can optimize the trade-off between the metrics of freshness and reconstruction queue length. In this work, we propose a randomized update policy that decides between head-of-line versus tail-of-line packets in the update queue. As such, our policy combines the strength of Last-Come-First-Serve (LCFS) service discipline (which aims at reducing the age) with the strength of First-Come-First-Serve (FCFS) service discipline (which aims at reducing the reconstruction delay). We evaluate the performance of our proposed policy in terms of its randomization parameter, which can be optimized given the system parameters to achieve a better trade-off.

Synchronized and fresh communication of common information is vitally important in numerous multi-user network scenarios, whereby end-users must perform coordinated real-time action with the available information. However, developing efficient policies with performance guarantees is greatly complicated by the abruptly changing nature of related age and synchronization metrics. In particular, powerful approaches that are based on so-called drift-plus-penalty (DPP) methods could not be employed due to the non-traditional multiplicative update dynamics of age and synchronization. In this paper, we overcome these limitations by designing and analyzing a Lyapunov-drift-based algorithm under the non-traditional age and synchronization dynamics that is not only low-complexity and analyzable, but also performs better than all the prior designs in numerical investigations. By comparing our design with two alternatives using the DPP approach, we also shed some light on the key aspect of our design that enables the performance analysis, which may be useful in future studies in multiplicative update dynamics. Furthermore, we implement Feature-based Reinforcement Learning (RL) methods with reduced state spaces and RL with full-state observations. Fresh-Async performs very closely to feature-based RL method using a feature space consisting of average age, age asynchrony, and maximum age, and both algorithms exhibit competitive performance compared to full-state RL while maintaining superior computational efficiency. These investigations clarify the contrast between drift-based and RL-based designs, and also reveal how drift-based design can be beneficial for feature selection for RL operation.

The challenge of classification at the network edge is that due to limited computational resources, the edge must transmit the data to a server for processing. However, the communication constraints at the edge necessitate that these devices compress data before transmission. The question this paper aims to answer is how to efficiently compress and transmit this information in order to achieve timely and accurate edge classification. To that end, we develop scheduling algorithms that optimize age of information (AoI) and classification accuracy. Our analysis reveals that in scenarios with multiple available compression levels, an algorithm that selects at most two compression levels can achieve good theoretical performance guarantees. Numerical results indicate that double-level compression algorithms yield near-optimal performance, suggesting that for many classification tasks, numerous compression levels are unnecessary—only two are sufficient, significantly reducing the storage demands on devices and simplifying the overall system design.

In many applications, we regularly face the fundamental problem of allocating a common resource (funding, time, energy, etc.) among a network of processes that evolve in a continuous-space according to a birth-death dynamics. The state of each process tends to gradually improve with the resource and gradually degrade without it. Formulated as a Constrained Markov Decision Process (CMDP), the problem is typically attacked in the continuous space directly using the function approximation method or in discrete space with a fixed granularity. In this work, we investigated an alternative method based on the fact that the granularity of discretization has a crucial impact on the size and the evolution of the state-space. Increasing the granularity has the desirable effect of increasing the control of the processes (due to increased interaction regularity), but it also comes with the burden of an increasing state-space. Without function approximation, it is well-known that finding the optimal solution of CMDP is formidably difficult as the state-space grows. We have taken a fresh look at designing State-Independent policies whose complexity does not scale with the discretization granularity parameternof the underlying continuous space processes. In particular, for a constrained-resource allocation problem over birth-death type processes, we developed state-independent policies that guarantee asymptotic-optimality as the discretization granularityngrows. We also show, through numerical comparisons, that our design has a lower running time compared to alternative designs including index-based methods and function approximation methods.

We study the optimal scheduling problem where n source nodes attempt to transmit updates over L shared wireless on/off fading channels to optimize their age performance under energy and age-violation tolerance constraints. Specifically, we provide a generic formulation of age-optimization in the form of a constrained Markov Decision Process (CMDP), and obtain the optimal scheduler as the solution of an associated Linear Programming problem. We investigate the characteristics of the optimal single-user multi-channel scheduler under different age-related objectives where a usual threshold-based policy does not apply. We then investigate the stability region of the optimal scheduler for the multi-user case under age-violation tolerance constraints. Furthermore, we develop two online schedulers that do not require statistics and are amenable to scalable operation: Drift-plus-penalty-based design, and a novel variation of the well-known Q-learning-based reinforcement learning method that combines Q-learning with drift-minimization-methods successfully for the first time, to the best of our knowledge. Our numerical studies compare the performance of our online schedulers to the optimal scheduler to reveal that both algorithms capture the essential behavior of the optimal design under different scenarios with good scalability, with the Q-learning-based design providing even closer performance to the optimal one by utilizing the history of the drift in a novel way.

We consider a scenario whereby the state of a common source is being updated at multiple distributed devices. We are particularly interested in the tradeoff that exists between thefreshnessof the updates at the distributed devices and thesynchronyof the updates across them. In this paper, we explore this tradeoff in a wireless downlink setting whereby the transmitter can choose between unicast transmissions (with given success probabilities) to particular users and broadcast transmissions (with a smaller success probability) to all users. After discussing the Linear Programming (LP)-based optimal design and extreme choices of “always-unicasting” and “always-broadcasting” policies, we note that the optimal design is not scalable and the extreme policies are inefficient. This motivates us to develop two classes of policies, namely a “mixed randomized policy” and a “feature-based learning policy”, which have desirable performance and computational-complexity characteristics. Additionally we manage to provide complete analysis for the mixed randomized policy under the two-user case, which provides interesting insights and can be partially extended to general cases. We perform extensive numerical studies to compare the performance of these designs over the benchmarks to reveal their gains.

The widespread adoption of low-cost resource-constrained edge devices and high-performance expensive servers necessitates shifting the complexity burden from edge devices to servers. However, in many applications such as image classification, it is often impractical and communication expensive to transmit full information without any form of compression. To address this issue, this paper introduces a neural network (NN)-based compression technique tailored for resource-constrained edge devices for classification at the network edge. The core idea involves simultaneously training a shallow neural network to-be-implemented by the devices and a deep neural network to-be-implemented by the server. To adapt to the time-varying channel conditions, the compression algorithm at the device side must be able to handle multiple output dimensions. To address this issue, we develop two multi-dimensional compression strategies: the multiple codebook approach, using separate NNs for various dimensions, and the single codebook approach, utilizing one NN for all dimensions. The single codebook approach substantially reduces the storage demands on the device, offering a viable solution for low-cost edge devices. Our analysis offers a theoretical performance guarantee, highlighting that the accuracy of the single codebook approach is comparable to that of the multiple codebook strategy. Through empirical evaluations on real-world datasets, we demonstrate that the single codebook approach achieves near-equivalent performance to the accuracy multiple codebook alternative.

We introduce a framework and optimal ‘fresh’ caching for a content distribution network (CDN) comprising a front-end local cache and a back-end database. The data content is dynamically updated at a back-end database and end-users are interested in the most-recent version of that content. We formulate the average cost minimization problem that captures the system’s cost due to the service of aging content as well as the regular cache update cost. We consider the cost minimization problem from two individual perspectives based on the available information to either side of the CDN: the back-end database perspective and the front-end local cache perspective. For the back-end database, the instantaneous version of content is observable but the exact demand is not. Caching decisions made by the back-end database are termed ‘push-based caching.’ For the front-end local cache, the age of content version in the cache is not observable, yet the instantaneous demand is. Caching decisions made by the front-end local cache are termed ‘pull-based caching.’ Our investigations reveal which type of information, updates, or demand dynamic, is of higher value towards achieving the minimum cost based on other network parameters including content popularity, update rate, and demand intensity.

In this work, we perform a comparative study of centralized and decentralized update strategies for the basic remote tracking problem of many distributed users/devices with randomly evolving states. Our goal is to reveal the impact of the fundamentally different tradeoffs that exist between information accuracy and communication cost under these two update paradigms. In one extreme, decentralized updates are triggered by distributed users/transmitters based on exact local state-information, but also at a higher cost due to the need for uncoordinated multi-user communication. In the other extreme, centralized updates are triggered by the common tracker/receiver based on estimated global state-information, but also at a lower cost due to the capability of coordinated multi-user communication. We use a generic superlinear function to model the communication cost with respect to the number of simultaneous updates for multiple sources. We characterize the conditions under which transmitter-driven decentralized update policies outperform their receiver-driven centralized counterparts for symmetric sources, and vice versa. Further, we extend the results to a scenario where system parameters are unknown and develop learning-based update policies that asymptotically achieve the minimum cost levels attained by the optimal policies.

The ever-growing end user data demands, and the reductions in memory costs are fueling edge-caching deployments. Caching at the edge is substantially different from that at the core and needs to consider the nature of individualized data demands. For example, an individual user may not be interested in requesting the same data item again, if it has recently requested it. Such individualized dynamics are not apparent in the aggregated data requests at the core and have not been considered in popularity-driven caching designs for the core. Hence, these traditional caching policies could induce significant inefficiencies when applied at the edges. To address this issue, we develop new edge caching policies optimized for the individualized demands that also leverage overhearing opportunities at the wireless edge. With the objective of maximizing the hit ratio, the proposed policies will actively evict the data items that are not likely to be requested in the near future, and strategically bring them back into the cache via overhearing when they become popular again. Both theoretical analysis and numerical simulations demonstrate that the proposed edge caching policies could outperform the popularity-driven policies that are optimal at the core.

Edge caching has been widely implemented to efficiently serve data requests from end users. Numerous edge caching policies have been proposed to adaptively update the cache contents based on various statistics. One critical statistic is the miss cost, which could measure the latency or the bandwidth/energy consumption to resolve the cache miss. Existing caching policies typically assume that the miss cost for each data item is fixed and known. However, in real systems, they could be random with unknown statistics. A promising approach would be to use online learning to estimate the unknown statistics of these random costs, and make caching decisions adaptively. Unfortunately, conventional learning techniques cannot be directly applied, because the caching problem has additional cache capacity and cache update constraints that are not covered in traditional learning settings. In this work, we resolve these issues by developing a novel edge caching policy that learns uncertain miss costs efficiently, and is shown to be asymptotically optimal. We first derive an asymptotic lower bound on the achievable regret. We then design a Kullback-Leibler lower confidence bound (KL-LCB) based edge caching policy, which adaptively learns the random miss costs by following the “optimism in the face of uncertainty” principle. By employing a novel analysis that accounts for the new constraints and the dynamics of the setting, we prove that the regret of the proposed policy matches the regret lower bound, thus showing asymptotic optimality. Further, via numerical experiments we demonstrate the performance improvements of our policy over natural benchmarks.

We investigate a remote estimation system with communication cost for multiple Internet-of-Things sensors, in which the state of each sensor changes according to a Wiener process. Under sublinear communication cost structure, in which the per-transmission cost decreases with the number of simultaneous transmissions, we address an interesting unexplored trade-off under source dynamics between frequent updates of a smaller number of sensors at a higher cost and sporadic updates of a larger number of sensors at a lower cost. We first suggest two benchmark strategies, an all-at-once policy and a multi-threshold policy, and generalize them to a unified framework, called the MAX-$k$policy. Furthermore, we address the problem of parameter optimization of the MAX-$k$policy by developing online learning algorithms with stochastic feedback and a continuous search space. Through simulations, we demonstrate that the joint solution of the MAX-$k$policy and particle swarm optimization-based online learning achieves a high performance, outperforming the well-known upper confidence bound-based competitor.

In real-world networks, we regularly face the effect of propagating failures over networks, for example, rumors spread over social networks, outages spread over power networks, viruses spread over communication and biological networks. Often, these failures spread over a network of agents with unknown and potentially diverse degrees of vulnerabilities to the propagating phenomenon. In this work, we consider a general network model subject to propagating failures and develop provably fast mechanisms for learning the unknown vulnerabilities of the network with minimal cost incurred in the process. We propose an extension to the classic Independent Cascade (IC) model where we incorporate both node and edge failures with non-uniform costs. From an online learning perspective, the goal is to find an optimal policy to control where to start failures and generate samples. Therefore, we formulate a cost minimization problem with Probably-Approximately-Correct (PAC) type guarantees. As a theoretical benchmark, we design a linear programming problem using a proposed joint Bernstein inequality. Then we characterize the performance of randomized policies that use a fixed budget distribution independent of sampling history. Finally, we propose a fast Lyapunov-based online learning policy, for which we give a formal theoretical analysis. The performance of the policy are validated under extensive numerical studies for both synthetic and real-world networks.

In many applications such as statistical machine learning, reinforcement learning, and optimization for large data centers, the increasing data size and model complexity have made it impractical to run optimizations over a single machine. Therefore, solving the distributed optimization problem has become an important task. In this work, we consider a distributed processing network $G = \left( {\mathcal{V},\mathcal{E}} \right)$ with n nodes, where each node i can only evaluate the values of a local function (i.e., has zeroth-order information) and can only communicate with its neighbors. The objective is to reach consensus on the global optimizer of ${\max _{x \in \mathcal{X}}}\frac{1}{n}\sum\nolimits_{i = 1}^n {{f_i}(x)} $. Previous methods either assume first-order gradient information which is not suitable for many model-free learning scenarios, or consider the zeroth-order information but assume convexity of the objective functions and can only guarantee convergence to a stationary point for nonconvex objectives. To address these limitations, we drop both the known gradient assumption and convexity assumption. Instead, we propose a distributed Bayesian framework for the problem with only zeroth-order information and general nonconvex objective functions in a Matérn Reproducing Kernel Hilbert Space (RKHS). Under this framework, we propose an algorithm and show that with high probability it reaches consensus on all nodes and has a sublinear regret with regard to the global optimal. The results are validated under numerical studies.

In a broad class of reinforcement learning applications, stochastic rewards have heavy-tailed distributions, which lead to infinite second-order moments for stochastic (semi)gradients in policy evaluation and direct policy optimization. In such instances, the existing RL methods may fail miserably due to frequent statistical outliers. In this work, we establish that temporal difference (TD) learning with a dynamic gradient clipping mechanism, and correspondingly operated natural actor-critic (NAC), can be provably robustified against heavy-tailed reward distributions. It is shown in the framework of linear function approximation that a favorable tradeoff between bias and variability of the stochastic gradients can be achieved with this dynamic gradient clipping mechanism. In particular, we prove that robust versions of TD learning achieve sample complexities of order $\mathcal{O}(\varepsilon^{-\frac{1}{p}})$ and $\mathcal{O}(\varepsilon^{-1-\frac{1}{p}})$ with and without the full-rank assumption on the feature matrix, respectively, under heavy-tailed rewards with finite moments of order $(1+p)$ for some $p\in(0,1]$, both in expectation and with high probability. We show that a robust variant of NAC based on Robust TD learning achieves $\tilde{\mathcal{O}}(\varepsilon^{-4-\frac{2}{p}})$ sample complexity. We corroborate our theoretical results with numerical experiments.

We consider a scenario whereby the state of a common source is being updated at multiple distributed devices. We are particularly interested in the tradeoff that exists between the freshness of the updates at the distributed devices and the synchrony of the updates across them. In this paper, we explore this tradeoff in a wireless downlink setting whereby the transmit-ter can choose between unicast transmissions (with given success probabilities) to particular users and broadcast transmissions (with a smaller success probability) to all users. After discussing the Linear Programming (LP)-based optimal design and extreme choices of “always-unicasting” and “always-broadcasting” poli-cies, we note that the optimal design is not scalable and the extreme policies are inefficient. This motivates us to develop two classes of policies, namely a “mixed randomized policy” and a “feature-based learning policy”, which have desirable performance and computational-complexity characteristics. We perform extensive numerical studies to compare the performance of these designs over the benchmarks to reveal their gains.

In this work, we consider the problem of ‘fresh’ caching at distributed (front-end) local caches of content that is subject to ‘dynamic’ updates at the (back-end) database. We first provide new models and analyses of the average operational cost of a network of distributed edge-caches that utilizes wireless multicast to refresh aging content. We attack the problems of what to cache in each edge-cache and how to split the incoming demand amongst them (also called “load-splitting” in the rest of the paper) in order to minimize the operational cost. While the general form of the problem comes with an NP-hard Knapsack structure, we were able to completely solve the problem by judiciously choosing the number of edge-caches to be deployed over the network This reduces the complex problem to a solvable special case. Interestingly, our findings reveal that the optimal caching policy necessitates unequal load-splitting over the edge-caches even when all conditions are symmetric. Moreover, we find that edge-caches with higher load will generally cache fewer but relatively more popular content. We further investigate the tradeoffs between cost reduction and cache savings when employing equal and optimal load-splitting solutions for demand with Zipf($z$) popularity distribution. Our analysis reveals that equal load-splitting to edge-caches achieves close-to-optimal for less predictable demand ($z< 2$) while also saving in the cache size. On the other hand, for more predictable demand ($z>2$), optimal load-splitting results in substantial cost gains while decreasing the cache occupancy.

Future generation wireless technologies are expected to serve an increasingly dense and dynamic population of users that generate short bundles of information to be transferred over the shared spectrum. This calls for new distributed and low-overhead Multiple-Access-Control (MAC) strategies to serve such dynamic demands with spectral efficiency characteristics. In this work, we address this need by identifying and developing two fundamentally different MAC paradigms: (i) congestion-based paradigm that estimates the congestion level in the system and adapts to it; and (ii) age-based paradigm that prioritizes demands based on their ages. Despite their apparent differences, we develop policies under each paradigm in a generic multi-channel access scenario that are provably throughput-optimal when they employ any asymptotically-efficient channel encoding/decoding mechanism. We also characterize the stability regions of the two designs, and investigate the conditions under which one design outperforms the other. We perform extensive simulations to validate the theoretical claims and investigate the non-asymptotic performances of our designs.

In a wide variety of applications including online advertising, contractual hiring, and wireless scheduling, the controller is constrained by a stringent budget constraint on the available resources, which are consumed in a random amount by each action, and a stochastic feasibility constraint that may impose important operational limitations on decision-making. In this work, we consider a general model to address such problems, where each action returns a random reward, cost, and penalty from an unknown joint distribution, and the decision-maker aims to maximize the total reward under a budget constraint B on the total cost and a stochastic constraint on the time-average penalty. We propose a novel low-complexity algorithm based on Lyapunov optimization methodology, named LyOn, and prove that for K arms it achieves square root of KBlog(B) regret and zero constraint-violation when B is sufficiently large. The low computational cost and sharp performance bounds of LyOn suggest that Lyapunov-based algorithm design methodology can be effective in solving constrained bandit optimization problems.

Despite many valuable advances in the domain of online convex optimization over the last decade, many machine learning and networking problems of interest do not fit into that framework due to their nonconvex objectives and the presence of constraints. This motivates us in this paper to go beyond convexity and study the problem of stochastic continuum-armed bandit with long-term constraints. For noiseless observations of constraint functions, we propose a generic method using a Bayesian approach based on a class of penalty functions, and prove that it can achieve a sublinear regret with respect to the global optimum and a sublinear constraint violation (CV), which can match the best results of previous methods. Additionally, we propose another method to deal with the case where constraint functions are observed with noise, which can achieve a sublinear regret and a sublinear CV with more assumptions. Finally, we use two experiments to compare our methods with two benchmark methods in online optimization and Bayesian optimization, which demonstrates the advantages of our algorithms.

Edge caching has been widely implemented to efficiently serve data requests from end users. Numerous edge caching policies have been proposed to adaptively update cache content based on various statistics including data popularities and miss costs. Nevertheless, these policies typically assume that the miss cost for each data item is known, which is not true in real systems. A promising approach would be to use online learning to estimate these unknown miss costs. However, existing techniques cannot be directly applied, because the caching problem has additional cache capacity and cache update constraints that are not covered in traditional learning settings. In this work, we resolve these issues by developing a novel edge caching policy that learns uncertainty miss costs efficiently, and is shown to be asymptotically optimal. We first derive an asymptotic lower bound on the achievable regret. We then design a Kullback-Leibler lower confidence bound (KL-LCB) based edge caching policy, which adaptively learns the random miss costs by following the “optimism in the face of uncertainty” principle. By employing a novel analysis that accounts for the new constraints and the dynamics of the setting, we prove that the regret of the proposed policy matches the regret lower bound, thus showing asymptotic optimality. Further, via numerical experiments we demonstrate the performance improvements of our policy over natural benchmarks.

Existing content caching mechanisms are predominantly geared towards easy-access to content that is static once created. However, numerous applications, such as news and dynamic sources with time-varying states, generate ‘dynamic’ content where new updates replace previous versions. This motivates us in this work to study the freshness-driven caching algorithm for dynamic content, which accounts for the changing nature of data content. In particular, we provide new models and analyses of the average operational cost both for the single and distributed edge caching scenarios. In both scenarios, we characterize the performance of the optimal solution and develop algorithms to select the content and the update rate that the user(s) must employ to have low-cost access to fresh content. Moreover, our work reveals new and easy-to-calculate key metrics for quantifying the caching value of dynamic content in terms of their refresh rates, popularity, number of users in the distribute edge caching group, and the fetching and update costs associated with the optimal decisions. We compare the proposed freshness-driven caching strategies with benchmark caching strategies like cache the most popular content. Results demonstrate that freshness-driven caching strategies considerably enhance the utilization of the edge caches with possibly orders-of-magnitude cost reduction. Furthermore, our investigations reveal that the distributed edge caching scenario, benefiting from the multicasting property of wireless service to update the cached content, can be cost-effective compared to the single edge caching, as the number of edge caches increases.

We introduce a framework and provably-efficient schemes for ‘fresh’ caching at the (front-end) local cache of content that is subject to ‘dynamic’ updates at the (back-end) database. We start by formulating the hard-cache-constrained problem for this setting, which quickly becomes intractable due to the limited cache. To bypass this challenge, we first propose a flexible time-based-eviction model to derive the average system cost function that measures the system’s cost due to the service of aging content in addition to the regular cache miss cost. Next, we solve the cache-unconstrained case, which reveals how the refresh dynamics and popularity of content affect optimal caching. Then, we extend our approach to a soft-cache-constrained version, where we can guarantee that the cache use is limited with arbitrarily high probability. The corresponding solution reveals the interesting insight that ‘whether to cache an item or not in the local cache?’ depends primarily on its popularity level and channel reliability, whereas ‘how long the cached item should be held in the cache before eviction?’ depends primarily on its refresh rate. Moreover, we investigate the cost-cache saving trade-offs and prove that substantial cache gains can be obtained while also asymptotically achieving the minimum cost as the database size grows.

We introduce a framework and provably-efficient schemes for `fresh' caching at the (front-end) local cache of content that is subject to `dynamic' updates at the (back-end) database. We start by formulating the hard-cache-constrained problem for this setting, which quickly becomes intractable due to the limited cache. To bypass this challenge, we first propose a flexible time-based-eviction model to derive the average system cost function that measures the system's cost due to the service of aging content in addition to the regular cache miss cost. Next, we solve the cache-unconstrained case, which reveals how the refresh dynamics and popularity of content affect the optimal caching. Then, we extend our approach to a soft-cache-constrained version, where we can guarantee that the cache use is limited with arbitrarily high probability. The corresponding solution reveals the interesting insight that `whether to cache an item or not in the local cache?' depends primarily on its popularity level, whereas `how long the cached item should be held in the cache before eviction?' depends primarily on its refresh rate. Moreover, we investigate the cost-cache saving tradeoffs and prove that substantial cache gains can be obtained while also asymptotically achieving the minimum cost as the database size grows.

In this work, we perform a comparative study of centralized and decentralized update strategies for the basic remote tracking problem of many distributed users/devices with randomly evolving states. Our goal is to reveal the impact of the fundamentally different tradeoffs that exist between information accuracy and communication cost under these two update paradigms. In one extreme, decentralized updates are triggered by distributed users/transmitters based on exact local state-information, but also at a higher cost due to the need for uncoordinated multi-user communication. In the other extreme, centralized updates are triggered by the common tracker/receiver based on estimated global state-information, but also at a lower cost due to the capability of coordinated multi-user communication. We use a generic superlinear function to model the communication cost with respect to the number of simultaneous updates for multiple sources. We characterize the conditions under which transmitter-driven decentralized update policies outperform their receiver-driven centralized counterparts for symmetric sources, and vice versa. Further, we extend the results to a scenario where system parameters are unknown and develop learning-based update policies that asymptotically achieve the minimum cost levels attained by the optimal policies.

As an emerging technique to employ machine learning processes within an edge computing infrastructure, federated learning (FL) has aroused great interests in both industry and academia. In this paper, we consider a potential challenge of FL in a wireless setup, whereby uplink communication from edge devices to the central server has limited capacity. This is particularly important for machine learning tasks (such as training deep neural networks) in FL with extremely high-dimensional domains that can substantially increase the communication burden. To tackle this challenge, we first propose a basic method called Subspace Stochastic Gradient Descent for Federated Learning (FL-SSGD) to introduce the idea of subspace methods. Through theoretical analysis, we show that by choosing appropriate subspace matrices in FL-SSGD, we can reduce uplink communication costs compared to classical FedAvg method. To improve FL-SSGD, we then propose another method called Subspace Stochastic Variance Reduced Gradient for Federated Learning (FL-SSVRG) that has a faster convergence rate with less assumptions on objective functions. By conducting experiments of a nonconvex machine learning problem in two FL setups, we demonstrate the advantages of our methods compared to other communication-efficient methods.

In this work, we consider the problem of ‘fresh’ caching at distributed (front-end) local caches of content that is subject to ‘dynamic’ updates at the (back-end) database. We first provide new models and analyses of the average operational cost of a network of distributed edge-caches that utilizes wireless multicast to refresh aging content. We attack the problems of what to cache in each edge-cache and how to split the incoming demand amongst them (also called "loadsplitting" in the rest of the paper) in order to minimize the operational cost. While the general form of the problem comes with an NP-hard Knapsack structure, we were able to completely solve the problem by judiciously choosing the number of edge-caches to be deployed over the network. Interestingly, our findings reveal that the optimal caching policy necessitates unequal load-splitting over the edge-caches even when all conditions are symmetric. Moreover, we find that edge- caches with higher load will generally cache fewer but relatively more popular content. We further investigate the tradeoffs between cost reduction and cache savings when employing equal and optimal load-splitting solutions for demand with Zipf(z) popularity distribution. Our analysis reveals that equal load-splitting to edge-caches achieves close-to-optimal for less predictable demand (z2), optimal load-splitting results in substantial cost gains while decreasing the cache occupancy.

In this work, we consider a network, where n distributed information sources whose states evolve according to a random process transmit their time-varying states to a remote estimator over a shared wireless channel. Each source generates packets in a decentralized manner and employs a slotted random access mechanism to transmit the packets. In particular, we are interested in networks with a large number of low-complexity devices that share low-capacity random access channels. Accordingly, we investigate update strategies for remote tracking of source states that require each update to constitute as few bits as possible. To that end, we develop update strategies requiring only one-bit of information per update. We first consider a natural benchmark update policy and reveal that the benchmark policy cannot guarantee stability under all conditions. We then introduce an improvement of the benchmark policy that employs a local cancellation strategy, which makes the system always stable. We further analyze and optimize the performance of the cancellation-enabled update policy to bound the estimation error at the receiver. Through simulations, we compare the proposed cancellation-enabled one-bit update policy with zero-wait sampling and threshold-based sampling policies that require more than one-bit of information per update. The comparisons show that the cancellation-enabled update policy at its optimal threshold level outperforms the multi-bit update policies. This suggests that the cancellation-enabled one-bit update policy could be greatly beneficial for applications where transmission power or shared channel capacity are limited.

With the adoption of 5G wireless technology and the Internet-of-Things (IoT) networking, there is a growing interest in serving a dense population of low-complexity devices over shared wireless uplink channels. Different from the traditional scenario of persistent users, in these new networks each user is expected to generate only small bundles of information intermittently. The highly dynamic nature of such demand and the typically low-complexity nature of the user devices calls for a new MAC paradigm that is geared for low-overhead and distributed operation of dynamic users.In this work, we address this need by developing a generic MAC mechanism for estimating the number and coordinating the activation of dynamic users for efficient utilization of the time-frequency resources with minimal public feedback from the common receiver. We fully characterize the throughput and delay performance of our design under a basic threshold-based multi-channel capacity condition, which allows for the use of different channel utilization schemes. Moreover, we consider the Successive-Interference-Cancellation (SIC) Multi-Channel MAC scheme as a specific choice in order to demonstrate the performance of our design for a spectrally-efficient (albeit idealized) scheme. Under the SIC encoding/decoding scheme, we prove that our low-overhead distributed MAC can support maximum throughput, which establishes the efficiency of our design. Under SIC, we also demonstrate how the basic threshold-based success model can be relaxed to be adapted to the performance of a non-ideal success model.

In this work, we provide a comprehensive analysis of stability properties and delay gains that wireless multicasting capabilities, as opposed to more traditional unicast transmissions, can provide for content distribution in mobile networks. In particular, we propose a model and characterize the average queue-length (and hence average delay) performance of unicasting and various multicasting strategies for serving a dynamic user population at the wireless edge. First, we show that optimized static randomized multicasting (we call it `blind multicasting') leads to stable-everywhere operation irrespective of the network loading factor (given by the ratio of the demand rate to the service rate) and the content popularity distribution. In contrast, traditional unicasting suffers from unstable operation when the loading factor approaches one, although it outperforms blind multicasting at small loading factor levels. This motivates us to study `work-conserving multicast' policies next that always outperform unicasting while still offering stable-everywhere operation. Then, in the worst-case of uniformly-distributed content popularity, we explicitly characterize the scaling of the average queue-length (and hence delay) under a first-come-first-serve multicast strategy as a function of the database size and the loading factor. Consequently, this work provides the fundamental limits, as well as the guidelines, for the design and performance analysis of efficient multicasting strategies for wireless content distribution.

We consider an information network comprised of nodes that are: rational-information-consumers (RICs) and/or biased-information-providers (BIPs). Making the reasonable abstraction that any external event is reported as an answer to a logical statement, we model each node's information-sharing behavior as a binary channel. For various reasons, malicious or otherwise, BIPs might share incorrect reports of the event regardless of their private beliefs. In doing so, a BIP might favor one of the two outcomes, exhibiting intentional or unintentional bias (e.g. human cognitive biases). Inspired by the limitations of humans and low-memory devices in information networks, we previously investigated a graph-blind rational-information-consumer interested in identifying the ground truth. We concluded that to minimize its error probability, graph-blind RIC follows a counter-intuitive but tractable rule. In this work, we build on this foundational knowledge: “graph-blind RICs prefer the combination of information-providers that are all fully-biased against the a-priori likely input, over all other combinations.” Upon studying RICs with partial knowledge of the network graph, we find that they act similar to graph-blind RICs when their BIPs “listen to” sufficiently many information-providers of their own. Furthermore, if a common node is informing/influencing all n BIPs of a partially-aware RIC, that RIC anticipates its discovery of the “influential node” to diminish the average error probability by a factor that increases exponentially with n. However, from the partially-aware RIC's perspective, choosing n fully-, similarly-biased BIPs outweighs the discovery of influential nodes among its BIPs' sources. These insights might inform the design of consumer-centric information networks.

We consider a budget-constrained bandit problem where each arm pull incurs a random cost, and yields a random reward in return. The objective is to maximize the total expected reward under a budget constraint on the total cost. The model is general in the sense that it allows correlated and potentially heavy-tailed cost-reward pairs that can take on negative values as required by many applications. We show that if moments of order $(2+\gamma)$ for some $\gamma > 0$ exist for all cost-reward pairs, $O(\log B)$ regret is achievable for a budget $B>0$. In order to achieve tight regret bounds, we propose algorithms that exploit the correlation between the cost and reward of each arm by extracting the common information via linear minimum mean-square error estimation. We prove a regret lower bound for this problem, and show that the proposed algorithms achieve tight problem-dependent regret bounds, which are optimal up to a universal constant factor in the case of jointly Gaussian cost and reward pairs.

A significant challenge for future virtual reality (VR) applications is to deliver high quality-of-experience, both in terms of video quality and responsiveness, over wireless networks with limited bandwidth. This paper proposes to address this challenge by leveraging the predictability of user movements in the virtual world. We consider a wireless system where an access point (AP) serves multiple VR users. We show that the VR application process consists of two distinctive phases, whereby during the first (proactive scheduling) phase the controller has uncertain predictions of the demand that will arrive at the second (deadline scheduling) phase. We then develop a predictive scheduling policy for the AP that jointly optimizes the scheduling decisions in both phases. In addition to our theoretical study, we demonstrate the usefulness of our policy by building a prototype system. We show that our policy can be implemented under Furion, a Unity-based VR gaming software, with minor modifications. Experimental results clearly show visible difference between our policy and the default one. We also conduct extensive simulation studies, which show that our policy not only outperforms others, but also maintains excellent performance even when the prediction of future user movements is not accurate.

In this paper, we address the problem of stochastic optimization over distributed processing networks, which is motivated by machine learning applications performed in data centers. In this problem, each of a total n nodes in a network receives stochastic realizations of a private function fi(x) and aims to reach a common value that minimizes Σi=1nfi(x) via local updates and communication with its neighbors. We focus on zeroth-order methods where only function values of stochastic realizations can be used. Such kind of methods, which are also called derivative-free, are especially important in solving realworld problems where either the (sub)gradients of loss functions are inaccessible or inefficient to be evaluated. To this end, we propose a method called Distributed Stochastic Alternating Direction Method of Multipliers (DS-ADMM) which can choose to use two kinds of gradient estimators for different assumptions. The convergence rates of DS-ADMM are O(n√k log (2k)/T) for general convex loss functions and O(n k log (2kT)/T) for strongly convex functions in terms of optimality gap, where k is the dimension of domain and T is the time horizon of the algorithm. The rates can be improved to O(n/√T )and O(n log T/T) if objective functions have Lipschitz gradients. All these results are better than previous distributed zerothorder methods. Lastly, we demonstrate the performance of DSADMM via experiments of two examples called distributed online least square and distributed support vector machine arising in estimation and classification tasks.

Motivated by the Internet of Things (IoT) and Cyber-Physical Systems (CPS), we consider dynamic wireless fading networks, where each incoming flow has a random service demand and leaves the system once its service request is completed. In such networks, one of the primary goals of network algorithm design is to achieve short-term fairness that characterizes how often each flow is served, in addition to the more traditional goals such as throughput-optimality and delay-insensitivity to the flow size distribution. In wireline networks, all of these desired properties can be achieved by the round-robin scheduling algorithm. In the context of wireless networks, a natural extension of round-robin scheduling has been developed in the last few years through the use of a counter called the Time-Since-Last-Service (TSLS) that keeps track of the time that passed since the last service time of each flow. However, the performance of this round-robin-like algorithm has been primarily studied in the context of persistent flows that continuously inject packets into the network and do not ever leave the network. The analysis of dynamic flow arrivals and departures is challenging since each individual flow experiences independent wireless fading and thus, flows cannot be served in a strict round-robin manner. In this paper, we overcome this difficulty by exploring the intricate dynamics of TSLS-based algorithm and show that flows are provided round-robin-like service with a very high probability. Consequently, we then show that our algorithm can achieve throughput-optimality. Moreover, through simulations, we demonstrate that the proposed TSLS-based algorithm also exhibits desired properties such as delay-insensitivity and excellent short-term fairness performance in the presence of dynamic flows over wireless fading channels.

The theory of discrete-time online learning has been successfully applied in many problems that involve sequential decision-making under uncertainty. However, in many applications including contractual hiring in online freelancing platforms and server allocation in cloud computing systems, the outcome of each action is observed only after a random and action-dependent time. Furthermore, as a consequence of certain ethical and economic concerns, the controller may impose deadlines on the completion of each task, and require fairness across different groups in the allocation of total time budget $B$. In order to address these applications, we consider continuous-time online learning problem with fairness considerations, and present a novel framework based on continuous-time utility maximization. We show that this formulation recovers reward-maximizing, max-min fair and proportionally fair allocation rules across different groups as special cases. We characterize the optimal offline policy, which allocates the total time between different actions in an optimally fair way (as defined by the utility function), and impose deadlines to maximize time-efficiency. In the absence of any statistical knowledge, we propose a novel online learning algorithm based on dual ascent optimization for time averages, and prove that it achieves $\tilde{O}(B^{-1/2})$ regret bound.

Least-recently-used (LRU) caching and its variants have conventionally been used as a fundamental and critical method to ensure fast and efficient data access in computer and communication systems. Emerging data-intensive applications over unreliable channels, e.g., mobile edge computing and wireless content delivery networks, have imposed new challenges in optimizing LRU caching in environments prone to failures. Most existing studies focus on reliable channels, e.g., on wired Web servers and within data centers, which have already yielded good insights and successful algorithms. Surprisingly, we show that these insights do not necessarily hold true for unreliable channels. We consider a single-hop multi-cache distributed system with data items being dispatched by random hashing. The objective is to design efficient cache organization and data placement that minimize the miss probability. The former allocates the total memory space to each of the involved caches. The latter decides data routing and replication strategies. Analytically, we characterize the asymptotic miss probabilities for unreliable LRU caches, and optimize the system design. Remarkably, these results sometimes are counterintuitive, differing from the ones obtained for reliable caches. We discover an interesting phenomenon: allocating the cache space unequally can achieve a better performance, even when channel reliability levels are equal. In addition, we prove that splitting the total cache space into separate LRU caches can achieve a lower asymptotic miss probability than organizing the total space in a single LRU cache. These results provide new and even counterintuitive insights that motivate novel designs for caching systems over unreliable channels.

In this work, we provide a comprehensive analysis of stability properties and delay gains that wireless multicasting capabilities, as opposed to more traditional unicast transmissions, can provide for content distribution in mobile networks. In particular, we propose a model and characterize the average queue-length (and hence average delay) performance of unicasting and various multicasting strategies for serving a dynamic user population at the wireless edge. First, we show that optimized static randomized multicasting (we call it `blind multicasting') leads to stable-everywhere operation irrespective of the network loading factor (given by the ratio of the demand rate to the service rate) and the content popularity distribution. In contrast, traditional unicasting suffers from unstable operation when the loading factor approaches one, although it outperforms blind multicasting at small loading factor levels. This motivates us to study `work-conserving multicast' policies next that always outperform unicasting while still offering stable-everywhere operation. Then, in the worst-case of uniformly-distributed content popularity, we explicitly characterize the scaling of the average queue-length (and hence delay) under a first-come-first-serve multicast strategy as a function of the database size and the loading factor. Consequently, this work provides the fundamental limits, as well as the guidelines, for the design and performance analysis of efficient multicasting strategies for wireless content distribution.

We consider the optimal link rate selection problem in time-varying wireless channels with unknown channel statistics. The aim of optimal link rate selection is to transmit at the optimal rate at each time slot in order to maximize the expected throughput of the wireless channel/link or equivalently minimize the expected regret. Lack of information about channel state or channel statistics necessitates the use of online/sequential learning algorithms to determine the optimal rate. We present an algorithm called CoTS - Constrained Thompson sampling algorithm which improves upon the current state-of-the-art, is fast and is also general in the sense that it can handle several different constraints in the problem with the same algorithm. We also prove an asymptotic lower bound on the expected regret and a high probability large-horizon upper bound on the regret, which show that the regret grows logarithmically with time in an order sense. We also provide numerical results which establish that CoTS significantly outperforms the current state-of-the-art algorithms.

Least-recently-used (LRU) caching and its variants have conventionally been used as a fundamental and critical method to ensure fast and efficient data access in computer and communication systems. Emerging data-intensive applications over unreliable channels, e.g., mobile edge computing and wireless content delivery networks, have imposed new challenges in optimizing LRU caching systems in environments prone to failures. Most existing studies focus on reliable channels, e.g., on wired Web servers and within data centers, which have already yielded good insights with successful algorithms on how to reduce cache miss ratios. Surprisingly, we show that these widely held insights do not necessarily hold true for unreliable channels. We consider a single-hop multi-cache distributed system with data items being dispatched by random hashing. The objective is to achieve efficient cache organization and data placement. The former allocates the total memory space to each of the involved caches. The latter decides data routing strategies and data replication schemes. Analytically we characterize the unreliable LRU caches by explicitly deriving their asymptotic miss probabilities. Based on these results, we optimize the system design. Remarkably, these results sometimes are counterintuitive, differing from the ones obtained for reliable caches. We discover an interesting phenomenon: asymmetric cache organization is optimal even for symmetric channels. Specifically, even when channel unreliability probabilities are equal, allocating the cache spaces unequally can achieve a better performance. We also propose an explicit unequal allocation policy that outperforms the equal allocation. In addition, we prove that splitting the total cache space into separate LRU caches can achieve a lower asymptotic miss probability than resource pooling that organizes the total space in a single LRU cache. These results provide new and even counterintuitive insights that motivate novel designs for caching systems over unreliable channels. They can potentially be exploited to further improve the system performance in real practice.

Distributed optimization has important applications in the practical implementation of machine learning and signal processing setup by providing means to allow interconnected network of processors to work towards the optimization of a global objective with intermittent communication. Existing works on distributed optimization predominantly assume all the processors storing related data to perform updates for the optimization task in each iteration. However, such optimization processes are typically executed at shared computing/data centers along with other concurrent tasks. Therefore, it is necessary to develop efficient distributed optimization methods that possess the flexibility to share the computing resources with other ongoing tasks. In this work, we propose a new first-order framework that allows for this flexibility through a probabilistic computing resource allocation strategy while guaranteeing the satisfactory performance of distributed optimization. Our results, both analytical and numerical, show that by controlling a flexibility parameter, our suite of algorithms (designed for various scenarios) can achieve the lower computation and communication costs of distributed optimization than their inflexible counterparts. This framework also enables the fair sharing of the common resources with other concurrent tasks being processed by the processing network.

The future Internet of Things (IoT) networks are expected to be composed of a large population of low-cost devices communicating dynamically with access points or neighboring devices to communicate small bundles of delay-sensitive data. To support the high-intensity and short-lived demands of these emerging networks, we propose an efficient MAC paradigm for IoT (EMIT). Our paradigm bypasses the high overhead and coordination costs of existing MAC solutions by employing an interference-averaging strategy that allows users to share their resources simultaneously. In contrast to the predominant interference-suppressing approaches, EMIT exploits the dense and dynamic nature of IoT networks to reduce the spatio-temporal variability of interference to achieve low-delay and high-reliability in service. This paper introduces foundational ideas of EMIT by characterizing the global interference statistics in terms of single-device operation and develops power-rate allocation strategies to guarantee low-delay high-reliability performance. A significant portion of our work is aimed at validating these theoretical principles in experimental test beds and simulations, where we compare the performance of EMIT with a CSMA-based MAC protocol. Our comparisons confirm the beneficial characteristics of EMIT and reveal significant gains over CSMA strategies in the case of IoT traffic.

We study the problem of serving randomly arriving and delay-sensitive traffic over a multi-channel communication system with time-varying channel states and unknown statistics. This problem deviates from the classical exploration-exploitation setting in that the design and analysis must accommodate the dynamics of packet availability and urgency as well as the cost of each channel use at the time of decision. To that end, we have developed and investigated an index-based policy upper confidence bound (UCB)-deadline, which performs dynamic channel allocation decisions that incorporate these traffic requirements and costs. Under symmetric channel conditions, we have proved that the UCB-deadline policy can achieve bounded regret in the likely case where the cost of using a channel is not too high to prevent all transmissions, and logarithmic regret otherwise. In this case, we show that UCB-deadline is order-optimal. We also perform numerical investigations to validate the theoretical fundings, and also compare the performance of the UCB-deadline to another learning algorithm that we propose based on Thompson sampling.

The dominant portion of smartphone traffic is generated by apps that involve human interactivity. Particularly, when human users receive information from a server, they spend a few seconds of information processing before taking an action. The user processing time creates an idle communication period during the app session. Moreover, the generation of the future traffic depends on the service of the current query-response pair. In this paper, we aim at leveraging the properties of such interactions to reap quality-of-experience gains. Existing schedulers, both in practice and theory, are not designed in view of the aforementioned traffic characteristics. Theoretical works predominantly focus on scheduling of traffic that is either generated independently or directly controlled, but not governed by the specific dynamics caused by human interactions. Schedulers in practice, on the other hand, employ round-robin and processor-sharing methods to serve multiple ongoing sessions. We show that neither of these approaches is effective for serving apps that involve human interactivity. Instead, we show that optimal scheduling for interactive traffic is non-randomized over packets, which we call action-based, as it avoids breaking ongoing service of actions in order to align human response times with the service of other actions. Since the design of optimal action-based policy is computationally prohibitive, we develop low-complexity suboptimal action-based policies that are optimal for two ongoing sessions. Our numerical studies based on a real-data trace reveal that our proposed action-based policies can reduce total delay by 22% with respect to packet-based equal processor sharing.

We consider the problem of transmitting at the optimal rate over a rapidly-varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mm Wave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called Modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.

We consider the problem of detecting the active wireless stations among a very large population. This problem is highly relevant in applications involving passive and active RFID tags and dense IoT settings. The state of the art mainly utilizes interference avoiding (e.g., CSMA-based) approaches with the objective of identifying one station at a time. We first derive basic limits of the achievable delay with interference avoiding paradigm. Then, we consider the setting in which each station is assigned a signature sequence, picked at random from a specific alphabet and active stations transmit their signatures simultaneously upon activation. The challenge at the detector is to detect all active stations from the combined signature signal with low probability of misdetection and false positives. We show that, such an interference embracing approach can substantially reduce the detection delay, at an arbitrarily low probability of both types of detection errors, as the number of stations scale. We show that, under a randomized activation model the collision embracing detection scheme achieves Θ(log2(n)/log(log(n))) delay while the expected delay of existing CSMA schemes are Ω(log2(n)) for a population of n stations. Finally, we discuss large-scale implementation issues such as the design of low-complexity detection schemes and present numerical investigations.

There is a rich theory and plethora of algorithms in the literature aiming at the efficient scheduling of stochastic networks. These solutions are predominantly designed under the assumption of traffic demands that are independently generated at network nodes, without any requirement for synchronization among their received services. In this work, we note that many applications, including cloud computing, virtual reality, gaming, autonomous vehicular networks and collaborative design, generate traffic simultaneously at multiple nodes when they arrive, with possibly non-uniform file sizes, whose performance relies on the synchronous completion of the traffic across the network. This calls for the design of new scheduling algorithms that aims to coordinate the service of packets of the same traffic across the network. Towards this end, we propose a novel scheduling algorithm that not only accounts for the heterogeneity of the file size distributions, but also works towards synchronizing the completion time of the same traffic stream across the network. This is achieved by employing two insights that emanate from key motivating examples we develop: (1) the normalization of traffic load with respect to the non-uniform file sizes; and (2) the incorporation of deviation of normalized loads across network nodes that serve synchronized traffic. After establishing the throughput-optimality of our algorithm in general stochastic networks, we perform extensive simulations under various (spanning both wired and wireless) settings to reveal the potential completion time gains that it yields over other throughput-optimal strategies designed under the assumption of independent traffic generation.

We consider the problem of scheduling in wireless networks with the aim of maintaining up-to-date and synchronized (also called, aligned) information at the receiver across multiple flows. This is in contrast to the more conventional approach of scheduling for optimizing long-term performance metrics such as throughput, fairness, or average delay. Maintaining the age of information at a low and roughly equal level is particularly important for distributed cyber-physical systems, in which the effectiveness of the control decisions depends critically on the freshness and synchrony of information from multiple sources/sensors. In this paper, we first expose the weakness of several popular MaxWeight scheduling solutions that utilize queue-length, delay, and age information as their weights. Then, we develop a novel age-based scheduler that combines age with the interarrival times of incoming packets in its decisions, which yields significant gains in the information freshness at the receiver. We characterize the performance of our strategy through a heavy-traffic analysis that establishes upper and lower bounds on the freshness of system information.

Round robin and its variants are well known scheduling policies that are popular in wireline networks due to their throughput optimality, delay insensitivity to file size distributions and short-term fairness. The latter two properties are also extremely important for emerging wireless applications, such as Internet of Things and cyber-physical systems. However, there is no direct wireless analog of round robin with all the desirable properties in wireless networks, where wireless interference and channel fading are predominant. The main reason is due to the fact that it is very difficult to even define what round robin means in wireless networks. This motivates us to develop a round-robin-like algorithm in wireless networks that has nice properties as round robin in wireline networks. To that end, we utilize a counter called the Time-Since-Last-Service (TSLS) that keeps track of the time of each file since its last service, and observe that scheduling a file with maximum TSLS in a single server is equivalent to serving files in a round robin fashion. Based on this key observation, we develop a TSLS-based algorithm that balances the tradeoff between the TSLS value and the channel rate for each link and show that the proposed algorithm achieves maximum system throughput, which demands a nontraditional approach due to the abrupt dynamics of the TSLS metrics. Numerous simulations are provided to validate its desired properties such as delay insensitivity and excellent short-term fairness performance as in the case of round robin algorithms of wireline networks.

We study the problem of serving randomly arriving and delay-sensitive traffic over a multi-channel communication system with time-varying channel states and unknown statistics. This problem deviates from the classical exploration-exploitation setting in that the design and analysis must accommodate the dynamics of packet availability and urgency as well as the cost of each channel use at the time of decision. To that end, we have developed and investigated two policies, one index-based (UCB-Deadline) and the other Bayesian (TS-Deadline), both of which perform dynamic channel allocation decisions that incorporate these traffic requirements and costs. Under symmetric channel conditions, we have proved that the UCB-Deadline policy can achieve bounded regret in the likely case where the cost of using a channel is not too high to prevent all transmissions, and logarithmic regret otherwise. In our numerical studies, we also show that TS-Deadline achieves superior performance over its UCB counterpart, making it a potentially useful alternative when fast convergence to optimal is important.

We introduce a new optimization framework, built over a discounted-rate metric, that captures the sensitivities of wireless users to time-variations in their fairness measure of rate allocations. The resulting, so-called, Discounted-Rate Utility Maximization (DRUM) formulation not only accommodates traditional long-term and less-explored instant fairness concepts in its extremes, but also encompasses all intermediate degrees of sensitivity to fluctuations in the users' rate allocations. After introducing the versatile DRUM formulation, we fully characterize its solution in the instantly-fair and long-term-fair extremes for the general class of ω-weighted α-fair utility functions. These solutions reveal the non-trivial impact of fading channel statistics and the utility function parameters on the rate allocations, even under perfectly symmetric network conditions. In particular, we demonstrate that the rate allocations lie between the maximum and the harmonic mean of the fading-channel rates. To achieve rates in-between these extremes, we also address the general solution of DRUM by proposing a novel low-complexity dynamic rate allocation algorithm that does not require the knowledge of the channel statistics. This algorithm is proven to achieve the optimal performance of the instantly-fair and long-term-fair solutions as the discount parameter approaches its lower and upper limits, respectively. We also study the fairness and rate allocation characteristics of our algorithm for intermediate values of the discount parameter in a Rayleigh-Fading environment.

We consider the problem of scheduling in wireless networks with the aim of maintaining up-to-date and synchronized (also called, aligned) information at the receiver across multiple flows. This is in contrast to the more conventional approach of scheduling for optimizing long-term performance metrics such as throughput, fairness, or average delay. Maintaining the age of information at a low and roughly equal level is particularly important for distributed cyber-physical systems, in which the effectiveness of the control decisions depends critically on the freshness and synchrony of information from multiple sources/sensors. In this work, we first expose the weakness of several popular MaxWeight scheduling solutions that utilize queue-length, delay, and age information as their weights. Then, we develop a novel age-based scheduler that combines age with the interarrival times of incoming packets in its decisions, which yields significant gains in the information freshness at the receiver. We characterize the performance of our strategy through a heavy-traffic analysis that establishes upper and lower bounds on the freshness of system information.

To support the multi-gigabit per second data rates of 5G wireless networks, there have been significant efforts on the research and development of massive MIMO (M-MIMO) technologies at the physical layer. So far, however, the understanding of how M-MIMO could affect the performance of network control, and optimization algorithms remain rather limited. In this paper, we focus on analyzing the performance of the queue-length-based joint congestion control and scheduling framework over M-MIMO cellular networks with limited channel state information (CSI). Our contributions in this paper are twofold. First, we characterize the scaling performance of the queue-lengths and show that there exists a phase transitioning phenomenon in the steady-state queue-length deviation with respect to the CSI quality (reflected in the number of bits B that represent CSI). Next, we characterize the congestion control rate scaling performance and show that there also exists a phase transitioning phenomenon in steady-state congestion control rate deviation with respect to the CSI quality. Collectively, the findings in this paper advance our understanding of the tradeoffs between delay, throughput, and the accuracy/complexity of CSI acquisition in M-MIMO cellular network systems.

Advances in millimeter-wave (mmW) communication open up a vast frequency band, from 30 - 300 GHz, for use in mobile communication systems. However, these new frequencies exhibit highly variable and intermittent channel characteristics. In this work, we investigate the impact of diverse mmW channel statistics on the limit and the rate at which the achievable rates converge to the infinite bandwidth capacity. In particular, we first identify the optimal power allocation algorithm, and investigate the behavior of the capacity both asymptotically and at finite number of channels. Then, we propose a suboptimal algorithm that achieves asymptotic optimality and is tractable for analysis, and analyze the convergence rate of the achievable rate under this algorithm. Analytical findings are supported by numerical investigations in realistic communication scenarios.

The mismatch between user demand and service supply creates a congestion in mobile wireless networks. The literature has a strong evidence that user behavior is highly predictable. Taking advantage of user demand predictability allows the carrier to apply proactive caching in order to smooth out the network load. Moreover, harnessing the information about user mobility enhances carrier's caching decision and minimizes the incurred service cost. The information about users' trajectories allows the carrier to predict their availability in some popular locations which experience high demand. Finding an optimal caching strategy alleviates the network congestion in these locations and improves the overall network performance. We introduce a system model where the carrier takes a decision to proactively cache some of the requested data items in users' devices. Users are equipped with D2D communication which is used to share cached data items between them in these popular locations. Users get reward to compensate their memory usage and battery consumption. Although caching helps users to save some of their payment, this reward promotes them to participate in the proposed model. We establish a lower bound on the proactive service cost which yields some insights on how user demand and mobility statistics affect carrier's caching decision.

The future Internet of Things (IoT) networks are expected to be composed of a large population of low-cost devices communicating dynamically with access points or neighboring devices to communicate small bundles of delay-sensitive data. To support the high-intensity and short-lived demands of these emerging networks, we propose an Efficient MAC paradigm for IoT (EMIT). Our paradigm bypasses the high overhead and coordination costs of existing MAC solutions by employing an interference-averaging strategy that allow users to share their resources simultaneously. In contrast to the predominant interference-suppressing approaches, EMIT exploits the dense and dynamic nature of IoT networks to reduce the spatio-temporal variability of interference to achieve low-delay and high-reliability in service. This paper introduces foundational ideas of EMIT by characterizing the global interference statistics in terms of single-device operation and develops power-rate allocation strategies to guarantee low-delay high-reliability performance. A significant portion of our work is aimed at validating these theoretical principles in experimental testbeds, where we compare the performance of EMIT to a CSMA-based MAC protocol. Our comparisons confirm the beneficial characteristics of EMIT, and reveal significant gains over CSMA strategies in the case of IoT traffic.

The last decade has seen significant advances in optimization-based resource allocation and control approaches for wireless networks. However, the existing work suffer from poor performance in one or more of the metrics of optimality, delay, and convergence speed. To overcome these limitations, in this paper, we introduce a largely overlooked but highly effective heavy-ball optimization method. Based on this heavy-ball technique, we develop a cross-layer optimization framework that offers utility-optimality, fast-convergence, and significant delay reduction. Our contributions are three-fold: i) we propose a heavy-ball joint congestion control and routing/scheduling framework for both single-hop and multi-hop wireless networks; ii) we show that the proposed heavy-ball method offers an elegant three-way trade-off in utility, delay, and convergence, which is achieved under a near index-type simple policy; and more importantly, iii) our work opens the door to an unexplored network control and optimization paradigm that leverages advanced optimization techniques based on “memory/momentum” information.

In recent years, there have been significant efforts on the research and development of Massive MIMO (M-MIMO) technologies at the physical layer. So far, however, the understanding of how M-MIMO could affect the performance of network control and optimization algorithms remains rather limited. In this paper, we focus on analyzing the performance of the queue-length-based joint congestion control and scheduling framework (QCS) over M-MIMO cellular networks with limited channel state information (CSI). Our contributions in this paper are two-fold: i) We characterize the scaling performance of the queue-lengths and show that there exists a phase transitioning phenomenon in the steady-state queue-length deviation respect to the CSI quality (reflected in the number of bits B that represent CSI); and ii) We characterize the congestion control rate scaling performance and show that there also exists a phase transitioning phenomenon in steady-state congestion control rate deviation respect to the CSI quality. Collectively, the findings in this paper advance our understanding of the trade-offs between delay, throughput, and the accuracy/complexity of CSI acquisition in M-MIMO cellular network systems.

We investigate the downlink scheduling problem under Markovian ON/OFF fading channels, where the instantaneous channel state information is not directly accessible, but is revealed via ARQ-type feedback. The scheduler can exploit the temporal correlation/channel memory inherent in the Markovian channels to improve network performance. However, designing low-complexity and throughput-optimal algorithms under temporal correlation is a challenging problem. In this paper, we find that under an average number of transmissions constraint, a low-complexity index policy is throughput-optimal. The policy uses Whittle's index value, which was previously used to capture opportunistic scheduling under temporally correlated channels. Our results build on the interesting finding that, under the intricate queue length and channel memory evolutions, the importance of scheduling a user is captured by a simple multiplication of its queue length and Whittle's index value. The proposed queue-based index policy has provably low complexity. Numerical results show that significant throughput gains can be realized by exploiting the channel memory using the proposed low-complexity policy.

We consider the design of throughput-optimal scheduling policies in multihop wireless networks that also possess good mean delay performance and provide regular service for all links-critical metrics for real-time applications. To that end, we study a parametric class of maximum-weight-type scheduling policies, called Regular Service Guarantee (RSG) Algorithm, where each link weight consists of its own queue length and a counter that tracks the time since the last service, namely Time-Since-Last-Service (TSLS). The RSG Algorithm not only is throughput-optimal, but also achieves a tradeoff between the service regularity performance and the mean delay, i.e., the service regularity performance of the RSG Algorithm improves at the cost of increasing mean delay. This motivates us to investigate whether satisfactory service regularity and low mean-delay can be simultaneously achieved by the RSG Algorithm by carefully selecting its design parameter. To that end, we perform a novel Lyapunov-drift-based analysis of the steady-state behavior of the stochastic network. Our analysis reveals that the RSG Algorithm can minimize the total mean queue length to establish mean delay optimality under heavily loaded conditions as long as the design parameter weighting for the TSLS scales no faster than the order of [1/({5}√{ε})], where ε measures the closeness of the network load to the boundary of the capacity region. To the best of our knowledge, this is the first work that provides regular service to all links while also achieving heavy-traffic optimality in mean queue lengths.

We consider the scheduling problem in downlink wireless networks with heterogeneous, Markov-modulated, on/off channels. It is well known that the performance of scheduling over fading channels relies heavily on the accuracy of the available channel state information (CSI), which is costly to acquire. Thus, we consider the CSI acquisition via a practical ARQ-based feedback mechanism whereby channel states are revealed at the end of only scheduled users' transmissions. In the assumed presence of temporally correlated channel evolutions, the desired scheduler must optimally balance the exploitation-exploration tradeoff, whereby it schedules transmissions both to exploit those channels with up-to-date CSI and to explore the current state of those with outdated CSI. In earlier works, Whittle's Index Policy had been suggested as a low-complexity and high-performance solution to this problem. However, analyzing its performance in the typical scenario of statistically heterogeneous channel state processes has remained elusive and challenging, mainly because of the highly coupled and complex dynamics it possesses. In this work, we overcome these difficulties to rigorously establish the asymptotic optimality properties of Whittle's Index Policy in the limiting regime of many users. More specifically: 1) we prove the local optimality of Whittle's Index Policy, provided that the initial state of the system is within a certain neighborhood of a carefully selected state; (2) we then establish the global optimality of Whittle's Index Policy under a recurrence assumption that is verified numerically for our problem. These results establish that Whittle's Index Policy possesses analytically provable optimality characteristics for scheduling over heterogeneous and temporally correlated channels.

Mobile data users are known to possess predictable characteristics both in their interests and activity patterns. Yet, their service is predominantly performed, especially at the wireless edges, “reactively” at the time of request, typically when the network is under heavy traffic load. This strategy incurs excessive costs to the service providers to sustain on-time (or delay-intolerant) delivery of data content, while their resources are left underutilized during the light-loaded hours. This motivates us in this work to study the problem of optimal “proactive” caching whereby, future delay-intolerant data demands can be served within a given prediction window ahead of their actual time-of-arrival to minimize service costs. To that end, we first establish fundamental bounds on the minimum possible cost achievable by any proactive policy, as a function of the prediction uncertainties. These bounds provide interesting insights on the impact of uncertainty on the maximum achievable proactive gains. We then propose specific proactive caching strategies, both for uniform and fluctuating demand patterns, that are asymptotically-optimal in the limit as the prediction window size grows while the prediction uncertainties remain fixed. We further establish the exponential convergence rate characteristics of our proposed solutions to the optimal, revealing close-to-optimal performance characteristics of our designs even with small prediction windows. Also, proactive design is contrasted with its reactive and delay-tolerant counter-parts to obtain interesting results on the unavoidable costs of uncertainty and the potentially remarkable gains of proactive operation.

In this work, we formulate and study the profit maximization problem for a wireless service provider (SP) that encounters time-varying, yet partially predictable, demand characteristics. The disparate demand levels throughout the course of the day yield excessive service cost in the peak hour that substantially hurts the reaped profit. With the SP's ability to track and statistically predict future requests of its users, we propose to enable proactive caching of the peak hour demand ahead during off-peak times. Thus, network traffic will be smoothed out, while end-users' activity patterns are undisturbed. In addition, the SP is able to assign personalized pricing policies that strike the best balance between enhancing the certainty about the future demand for optimal proactive caching and maximizing the revenue collected from end-users. Comparing the proposed system's performance to the baseline scenario of the existing practice of no-proactive service, we show that the SP attains profit gain that grows with number of users, at least, as the first derivative of the cost function. Moreover, end-users that receive proactive caching services make strictly positive savings. Thus, we essentially demonstrate the win-win situation to be reaped through the exploitation of the consistent users' activity.

It is well-known that maximum weight scheduling, with link weights which are either functions of queue lengths or the ages of the Head-of-Line (HoL) packets in each queue, maximizes the throughput region of wireless networks with persistent flows. In particular, with only persistent flows, it does not matter for throughput optimality whether one uses queue lengths or HoL ages as weights. In this paper, we show the following interesting result: when some flows in the network are dynamic (i.e., they arrive and depart from the network and are not persistent), then HoL-age-based scheduling algorithms are throughput-optimal while it has previously been shown that queue-length-based algorithms are not. This reveals that, age-based algorithms are universal in the sense that their throughput optimality does not depend on whether the arriving traffic is persistent or not. We also present a distributed implementation of the proposed age-based algorithm using CSMA techniques, where each flow only knows its own age and carrier sensing information. Finally, we support our analytical results through simulations. The proof of throughput optimality may be interesting in its own right: it uses a novel Lyapunov function which is the sum of the ages of all the packets in the network.

In this paper, the interactions between a wireless network carrier and a set of end-users trading data contents that were downloaded proactively are studied. In particular, we investigate the profit maximization problem for wireless network carrier and payment minimization for end-users. Motivated by recent findings on proactive resource allocation, we focus on the scenario whereby end-users harness their predictable demands and the possibility of being connected together in downloading proactive data and selling them again to minimize their expected payments. The carrier, on the other hand, takes a commission from each trade and utilizes smart pricing schemes to differentiate between off-peak and peak hour prices to spreadout the peak load and maximize its profit. A marketplace based on risk sharing concept is achieved where the tension between carrier and end-users and the competition between end-users themselves is formulated as a Stackelberg game. The existence and uniqueness of the non-cooperative sub-game Nash equilibrium is shown. We compare the new equilibria with the baseline scenario of smart pricing proactive model without trading between users. Despite the uncertainty about future demand, and the freshness of proactively downloaded contents, we characterize new equilibria point that yield to a win-win situation with respect to the baseline equilibrium. We show that users' activity patterns can be harnessed to create a marketplace that will maximize the carrier's profit while users pay less.

We study opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario that the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state by exploiting the memory inherent in the Markov channels along with Automatic-Repeat-reQues-styled-styled feedback from the scheduled users. Opportunistic scheduling is optimized in two stages: 1) channel estimation and rate adaptation are performed to maximize the short-term throughput, i.e., the successful transmission rate of the scheduled user in the current slot and 2) user scheduling is performed, based on the short-term throughput, to maximize the overall long-term sum-throughput of the downlink. The scheduling problem is a partially observable Markov decision process with the classic exploitation versus exploration tradeoff that is difficult to quantify. We, therefore, study the problem in the framework of restless multiarmed bandit processes, and perform a Whittle's indexability analysis. Whittle's indexability is traditionally known to be hard to establish and the index policy derived based on Whittle's indexability is known to have optimality properties in various settings. We show that the problem of downlink scheduling under imperfect channel state information is Whittle indexable and derive the Whittle's index policy in closed form. Through extensive numerical experiments, we show that the Whittle's index policy has near-optimal performance and is robust against various imperfections in channel state feedback. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant system-level performance gains and that almost all of these gains can be realized using the polynomial-complexity Whittle's index policy.

It is energy-consuming and operationally cumbersome for all users to continuously estimate the channel quality before each transmission decision in opportunistic scheduling over wireless fading channels. This observation motivates us to understand whether and how opportunistic gains can still be achieved with significant reductions in channel probing requirements and without centralized coordination amongst the competing users. To that end, we first study a simple scenario that motivates us to consider the general setup and develop probing and transmission schemes that are amenable to distributed implementation. After characterizing the maximum achievable throughput region under the probing constraints, we provide an optimal probing algorithm. Noting the difficulties in the implementation of the centralized solution, we develop a novel Sequential Greedy Probing (SGP) algorithm, which is naturally well-suited for physical implementation and distributed operation. We show that the SGP algorithm is optimal in the important scenario of symmetric and independent ON-OFF fading channels. Then, we study a variant of the SGP algorithm in general fading channels to obtain its efficiency ratio as an explicit function of the channel statistics and rates, and note its tightness in the symmetric and independent ON-OFF fading scenario. We further discuss the distributed implementation of these greedy solutions by using the Fast-CSMA technique.

In this paper, we study the design of joint flow-rate control and scheduling policies in multihop wireless networks for achieving maximum network utility with provably optimal convergence speed. Fast convergence is especially important in wireless networks that are dominated by the dynamics of incoming and outgoing flows as well as the time-sensitive applications. Yet, the design of fast converging policies in wireless networks is complicated by: 1) the interference-constrained communication capabilities, and 2) the finite set of transmission rates to select from due to operational and physical-layer constraints. We tackle these challenges by explicitly incorporating such discrete constraints to understand their impact on the convergence speed at which the running average of the received service rates and the network utility over a finite time horizon T converges to their limits. In particular, we establish a fundamental fact that the convergence speed of any feasible policy cannot be faster than Ω(1/T) under both the rate and utility metrics. Then, we develop an algorithm that achieves this optimal convergence speed in both metrics. We also show that the well-known dual algorithm can achieve the optimal convergence speed in terms of its utility value. These results reveal the interesting fact that the convergence speed of rates and utilities in wireless networks is dominated by the discrete choices of scheduling and transmission rates, which also implies that the use of higher-order flow-rate controllers with fast convergence guarantees cannot overcome the aforementioned fundamental limitation.

Motivated by the regular service requirements of video applications for improving quality of experience (QoE) of users, we consider the design of scheduling strategies in multihop wireless networks that not only maximize system throughput but also provide regular interservice times for all links. Since the service regularity of links is related to the higher-order statistics of the arrival process and the policy operation, it is challenging to characterize and analyze directly. We overcome this obstacle by introducing a new quantity, namely the time-since-last-service (TSLS), which tracks the time since the last service. By combining it with the queue length in the weight, we propose a novel maximum-weight-type scheduling policy, called Regular Service Guarantee (RSG) Algorithm. The unique evolution of the TSLS counter poses significant challenges for the analysis of the RSG Algorithm. To tackle these challenges, we first propose a novel Lyapunov function to show the throughput optimality of the RSG Algorithm. Then, we prove that the RSG Algorithm can provide service regularity guarantees by using the Lyapunov-drift-based analysis of the steady-state behavior of the stochastic processes. In particular, our algorithm can achieve a degree of service regularity within a factor of a fundamental lower bound we derive. This factor is a function of the system statistics and design parameters and can be as low as two in some special networks. Our results, both analytical and numerical, exhibit significant service regularity improvements over the traditional throughput-optimal policies, which reveals the importance of incorporating the metric of time-since-last-service into the scheduling policy for providing regulated service.

In this paper, we propose and study optimal proactive resource allocation and demand shaping for data networks. Motivated by the recent findings on the predictability of human behavior patterns in data networks, and the emergence of highly capable handheld devices, our design aims to smooth out the network traffic over time and minimize the data delivery costs. Our framework utilizes proactive data services as well as smart content recommendation schemes for shaping the demand. Proactive data services take place during the off-peak hours based on a statistical prediction of a demand profile for each user, whereas smart content recommendation assigns modified valuations to data items so as to render the users' demand less uncertain. Hence, our recommendation scheme aims to boost the performance of proactive services within the allowed flexibility of user requirements. We conduct theoretical performance analysis that quantifies the leveraged cost reduction through the proposed framework. We show that the cost reduction scales at the same rate as the cost function scales with the number of users. Furthermore, we prove that demand shaping through smart recommendation strictly reduces the incurred cost even below that of proactive downloads without recommendation.

In this work, we investigate the profit maximization problem for wireless network carriers and payment minimization for end users. Motivated by our recent findings on proactive resource allocation, we focus on the scenario whereby end users harness predictable demand and WiFi connectivity in proactive data downloads, to minimize their expected payments. Carriers, on the other hand, utilize smart pricing schemes to differentiate between the off-peak and peak hour prices so as to reduce peak costs and maximize their profit.We formulate the tension between the carrier and end user as a two-player Stackelberg game in which the carrier assigns prices first, then the end user responds with optimized proactive downloads. We explore the equilibrium points under maximum and average price constraints, and study the impact of WiFi availability on the system's performance. In particular, we compare the new equilibria with the baseline scenario of flat pricing and no proactive downloads. Despite the potential uncertainty about future demand, and the freshness of proactively downloaded content, we characterize new equilibria points that yield win-win situation with respect to the baseline equilibrium.

We study the stochastic multi-armed bandit (MAB) problem in the presence of side-observations across actions. In our model, choosing an action provides additional side observations for a subset of the remaining actions. One example of this model occurs in the problem of targeting users in online social networks where users respond to their friends's activity, thus providing information about each other's preferences. Our contributions are as follows: 1) We derive an asymptotic (with respect to time) lower bound (as a function of the network structure) on the regret (loss) of any uniformly good policy that achieves the maximum long term average reward. 2) We propose two policies - a randomized policy and a policy based on the well-known upper confidence bound (UCB) policies, both of which explore each action at a rate that is a function of its network position. We show that these policies achieve the asymptotic lower bound on the regret up to a multiplicative factor independent of network structure. The upper bound guarantees on the regret of these policies are better than those of existing policies. Finally, we use numerical examples on a real-world social network to demonstrate the significant benefits obtained by our policies against other existing policies.

In this paper, we consider the design of the day-ahead market for the smart electrical grid. Consumers with flexible demand and generator companies participate in the market to settle on their load and supply schedules, respectively. The market is operated by an Independent System Operator (ISO) whose purpose is to maximize social welfare while keeping load and supply balanced in the electricity network. We develop two distributed pricing algorithms that achieve optimum welfare. The first algorithm yields time-dependent market prices under convexity assumptions on utility and cost functions and the second algorithm yields bundle prices for arbitrary utility and cost functions. In both algorithms, flexible consumers and generator companies simply determine their own schedules based on the prices updated by the ISO at each iteration. We show that the participation of flexible demand in the day-ahead market reduces supply volatility, which would be present when flexible demand does not take part in price setting procedure.

In this paper, we study the design of joint flow rate control and scheduling policies in multi-hop wireless networks for achieving maximum network utility with provably optimal convergence speed. Fast convergence is especially important in wireless networks which are dominated by the dynamics of incoming and outgoing flows as well as the time sensitive applications. Yet, the design of fast converging policies in wireless networks is complicated by: (i) the interference-constrained communication capabilities, and (ii) the finite set of transmission rates to select from due to operational and physical-layer constraints. We tackle these challenges by explicitly incorporating such discrete constraints to understand their impact on the convergence speed at which the running average of the received service rates and the network utility converges to their limits. In particular, we establish a fundamental fact that the convergence speed of any feasible policy cannot be faster than Ω (1/T) under both the T rate and utility metrics. Then, we develop an algorithm that achieves this optimal convergence speed in both metrics. We also show that the well-known dual algorithm can achieve the optimal convergence speed in terms of its utility value. These results reveal the interesting fact that the convergence speed of rates and utilities in wireless networks is dominated by the discrete choices of scheduling and transmission rates, which also implies that the use of higher-order flow rate controllers with fast convergence guarantees cannot overcome the aforementioned fundamental limitation.

Motivated by the low-jitter requirements of streaming multi-media traffic, we focus on the development of scheduling strategies under fading conditions that not only maximize throughput performance but also provide regular inter-service times to users. Since the service regularity of the traffic is related to the higher-order statistics of the arrival process and the policy operation, it is highly challenging to characterize and analyze directly. We overcome this obstacle by introducing a new quantity, namely the time-since-last-service, which has a unique evolution different from a tradition queue. By combining it with the queue-length in the weight, we propose a novel maximum-weight type scheduling policy that is proven to be throughput-optimal and also provides provable service regularity guarantees. In particular, our algorithm can achieve a degree of service regularity within a constant factor of a fundamental lower bound we derive. This constant is independent of the higher-order statistics of the arrival process and can be as low as two. Our results, both analytical and numerical, exhibit significant service regularity improvements over the traditional throughput-optimal policies, which reveals the importance of incorporating the metric of time-since-last-service into the scheduling policy for providing regulated service.

We address the question of optimal proactive service and demand shaping for content distribution in data networks through smart pricing. We develop a proactive download scheme that utilizes the probabilistic predictability of the human demand by proactively serving potential users' future requests during the off-peak times. Thus, it smooths-out the network traffic and minimizes the time average cost of service. Moreover, we incorporate the varying economic responsiveness and demand flexibilities of users into our model to develop a demand shaping mechanism that further improves the gains of proactive downloads. To that end, we propose a model that captures the uncertainty about the users' demand as well as their responsiveness to the pricing employed by the service providers. We propose a joint proactive resource allocation and demand shaping scheme based on nonconvex optimization algorithms, and show that it always leads to strictly better performance over its proactive counterpart without demand shaping.

We study the bounds and means of optimal caching in overlay Content Distribution Networks (CDN) that serve data with dynamic content to end-users who send random requests for the most up-to-date version of such content. Applications with such dynamic content are numerous, including daily news, weather conditions, stock market prices, social networking messages, etc. The service for such a dynamically changing content necessitates a fundamentally different approach than traditional pull-based (also called non-proactive) schemes. In particular, proactive caching is required to optimize the type and amount of content to be updated in the local servers of a CDN hence minimize the transmission and caching costs, subject to storage constraints. We study the metric of cost reduction achieved by proactive caching over non-proactive caching strategies. We introduce the notion of popularity to establish fundamental upper and lower bounds on cost reduction under different degrees of storage space constraints. We prove the lower bounds to achieve the optimal rate of increase achieved by the upper bounds as the database of items increases. In particular, for a general form of convex, superlinear and monotonically increasing cost functions, our results reveal that the optimal cost reduction scales as the cost function itself, or at least as its first derivative, depending on the number of popular data items, as well as the cache storage capacity.

We consider the design of throughput-optimal scheduling policies in multi-hop wireless networks that also possess good mean delay performance and provide regular service for all links -- critical metrics for real-time applications. To that end, we study a parametric class of maximum-weight type scheduling policies with parameter α ≥ 0, called Regular Service Guarantee (RSG) Algorithm, where each link weight consists of its own queue-length and a counter that tracks the time since the last service. This policy has been shown to be throughput-optimal and to provide more regular service as the parameter α increases, however at the cost of increasing mean delay.

In an unreliable single-hop broadcast network setting, we investigate the throughput and decoding-delay performance of random linear network coding as a function of the coding window size and the network size. Our model consists of a source transmitting packets of a single flow to a set of n users over independent time-correlated erasure channels. The source performs random linear network coding (RLNC) over k (coding window size) packets and broadcasts them to the users. We note that the broadcast throughput of RLNC must vanish with increasing n, for any fixed k. Hence, in contrast to other works in the literature, we investigate how the coding window size k must scale for increasing n. Our analysis reveals that the coding window size of Θ(ln(n)) represents a phase transition rate, below which the throughput converges to zero, and above which, it converges to the broadcast capacity. Further, we characterize the asymptotic distribution of decoding delay and provide approximate expressions for the mean and variance of decoding delay for the scaling regime of k=ω(ln(n)). These asymptotic expressions reveal the impact of channel correlations on the throughput and delay performance of RLNC. We also show that how our analysis can be extended to other rateless block coding schemes such as the LT codes. Finally, we comment on the extension of our results to the cases of dependent channels across users and asymmetric channel model.

This paper introduces the novel concept of proactive resource allocation for wireless networks, through which the predictability of user behavior is exploited to balance the wireless traffic over time, and significantly reduces the bandwidth required to achieve a given blocking/outage probability. We start with a simple model in which smart wireless devices are assumed to predict the arrival of new requests and submit them to the network$T$time slots in advance. Using tools from large deviation theory, we quantify the resulting prediction diversity gain to establish that the decay rate of the outage event probabilities increases with the prediction duration$T$. Remarkably, we also show that, in the cognitive networking scenario, the appropriate use of proactive resource allocation by primary users improves the diversity gain of the secondary network at no cost in the primary network diversity. We also shed light on multicasting with predictable demands and show that proactive multicast networks can achieve a significantly higher diversity gain that scales superlinearly with$T$. Finally, we conclude by a discussion of the new research questions posed under the umbrella of the proposed proactive wireless resource framework.

Multirate multicasting is a generalization of single-rate multicasting to prevent destinations with good connections from being limited by the capacity of bottleneck connections. While multirate multicasting has been traditionally performed over fixed trees, advances in network coding theory have enabled higher throughput and have helped us move beyond the restriction of tree structures for routing the multicast data. In this paper, we address the questions of optimal rate allocation and low-complexity network coding solutions to the problem of multirate multicasting in general multihop networks. Our work considers intralayer network coding capabilities, where the session is conceptually divided into layers optimally and coding is performed across packets belonging to the same layer. Our approach differs from earlier works in this domain in its separation of the problem into rate allocation and content distribution items, which allows a number of optimization and graphical techniques in their solution. Noting the complexities involved in the optimal rate allocation and content distribution solutions, we then propose and investigate two novel approaches for reducing the complexity of the original scheme for more practical implementation based on a layered multicasting mechanism and nested optimization approach. We demonstrate the implementation advantages of these low-complexity schemes via extensive numerical studies.

Recently, low-complexity and distributed Carrier Sense Multiple Access (CSMA)-based scheduling algorithms have attracted extensive interest due to their throughput-optimal characteristics in general network topologies. However, these algorithms are not well-suited for time-varying environments (i.e., serving real-time traffic under time-varying channel conditions in wireless networks) for two reasons: (1) the mixing time of the underlying CSMA Markov Chain grows with the size of the network, which, for large networks, generates unacceptable delay for deadline-constrained traffic; (2) since the dynamic CSMA parameters are influenced by the arrival and channel state processes, the underlying CSMA Markov Chain may not converge to a steady-state under strict deadline constraints and fading channel conditions. In this paper, we attack the problem of distributed scheduling for time-varying environments. Specifically, we propose a Fast-CSMA (FCSMA) policy in fully-connected topologies, which converges much faster than the existing CSMA algorithms and thus yields significant advantages for time-varying applications. Then, we design optimal policies based on FCSMA techniques in two challenging and important scenarios in wireless networks for scheduling inelastic traffic with/without channel state information (CSI) over wireless fading channels.

It is energy-consuming and operationally cumbersome for all users to continuously estimate the channel quality before each data transmission decision in opportunistic scheduling over wireless fading channels. This observation motivates us to understand whether and how opportunistic gains can still be achieved with significant reductions in channel probing requirements and without centralized coordination amongst the competing users. In this work, we first provide an optimal centralized probing and transmission algorithm under the probing constraints. Noting the difficulties in the implementation of the centralized solution, we develop a novel Sequential Greedy Probing (SGP) algorithm by using the maximum-minimums identity, which is naturally well-suited for physical implementation and distributed operation. We show that the SGP algorithm is optimal in the important scenario of symmetric and independent ON-OFF fading channels. Then, we study a variant of the SGP algorithm in general fading channels to obtain its efficiency ratio as an explicit function of the channel statistics and rates, and note its tightness in the symmetric and independent ON-OFF fading scenario. We further expand on the distributed implementation of these greedy solutions by using the Fast-CSMA technique.

We consider the scheduling problem in downlink wireless networks with heterogeneous, Markov-modulated, ON/OFF channels. It is well-known that the performance of scheduling over fading channels heavily depends on the accuracy of the available Channel State Information (CSI), which is costly to acquire. Thus, we consider the CSI acquisition via a practical ARQ-based feedback mechanism whereby channel states are revealed at the end of only scheduled users' transmissions. In the assumed presence of temporally-correlated channel evolutions, the desired scheduler must optimally balance the exploitation-exploration trade-off, whereby it schedules transmissions both to exploit those channels with up-to-date CSI and to explore the current state of those with outdated CSI. In earlier works, Whittle's Index Policy had been suggested as a low-complexity and high-performance solution to this problem. However, analyzing its performance in the typical scenario of statistically heterogeneous channel state processes has remained elusive and challenging, mainly because of the highly-coupled and complex dynamics it possesses. In this work, we overcome these difficulties to rigorously establish the asymptotic optimality properties of Whittle's Index Policy in the limiting regime of many users. More specifically: (1) we prove the local optimality of Whittle's Index Policy, provided that the initial state of the system is within a certain neighborhood of a carefully selected state; (2) we then establish the global optimality of Whittle's Index Policy under a recurrence assumption that is verified numerically for the problem at hand. These results establish, for the first time to the best of our knowledge, that Whittle's Index Policy possesses analytically provable optimality characteristics for scheduling over heterogeneous and temporally-correlated channels.

There has been substantial interest over the last decade in developing low complexity decentralized scheduling algorithms in wireless networks. In this context, the queue-length based Carrier Sense Multiple Access (CSMA) scheduling algorithms have attracted significant attention because of their attractive throughput guarantees. However, the CSMA results rely on the mixing of the underlying Markov chain and their performance under fading channel states is unknown. In this work, we formulate a partially decentralized randomized scheduling algorithm for a two transmitter receiver pair set up and investigate its stability properties. Our work is based on the Fast-CSMA (FCSMA) algorithm first developed in [1] and we extend its results to a signal to interference noise ratio (SINR) based interference model in which one or more transmitters can transmit simultaneously while causing interference to the other. In order to improve the performance of the system, we split the traffic arriving at the transmitter into schedule based queues and combine it with the FCSMA based scheduling algorithm. We theoretically examine the performance of our algorithm in both non-fading and fading environment and characterize the set of arrival rates which can be stabilized by our proposed algorithm.

We formulate and solve the problem of optimal channel coding and flow-rate control for serving deadline-constrained traffic with average delivery ratio requirements (typical of multimedia streaming and interactive real-time applications) over time-varying channels. To that end, we first characterize the largest set of arrival processes (rather than rates) whose deadline and delivery ratio requirements can be satisfied. Then, we propose a dynamic (channel) coding algorithm that provably satisfies the requirements of any arrival process in this region. This optimal dynamic algorithm evolves through simple iterations to utilize a combination of pricing and finite-horizon dynamic programming operations. Next, we proposed two low-complexity approximations of the algorithm that has provable performance. We also extend the setup to allow for a flow controller that adjusts the incoming flow rates to satisfy their delivery ratio constraints when the arrival process is unknown but controllable. We propose a joint dynamic coding and a rate control algorithm to solve this problem, and prove its stability under the stochastic system operation. We also apply these general results to an important wireless down-link broadcast scenario with and without random network coding capabilities. Our theoretical work is supported by extensive numerical studies, which also reveal that our dynamic coding strategy outperforms any static coding strategy by opportunistically exploiting the statistical variations in the arrival and channel processes.

Randomization is a powerful and pervasive strategy for developing efficient and practical transmission scheduling algorithms in interference-limited wireless networks. Yet, despite the presence of a variety of earlier works on the design and analysis of particular randomized schedulers, there does not exist an extensive study of the limitations of randomization on the efficient scheduling in wireless networks. In this paper, we aim to fill this gap by proposing a common modeling framework and three functional forms of randomized schedulers that utilize queue-length information to probabilistically schedule nonconflicting transmissions. This framework not only models many existing schedulers operating under a timescale separation assumption as special cases, but it also contains a much wider class of potential schedulers that have not been analyzed. We identify some sufficient and some necessary conditions on the network topology and on the functional forms used in the randomization for throughput optimality. Our analysis reveals an exponential and a subexponential class of functions that exhibit differences in the throughput optimality. Also, we observe the significance of the network's scheduling diversity for throughput optimality as measured by the number of maximal schedules each link belongs to. We further validate our theoretical results through numerical studies.

We attack the challenging problem of designing a scheduling policy for end-to-end deadline-constrained traffic with reliability requirements in a multihop network. It is well known that the end-to-end delay performance for a multihop flow has a complex dependence on the high-order statistics of the arrival process and the algorithm itself. Thus, neither the earlier optimization-based approaches that aim to meet the long-term throughput demands nor the solutions that focus on a similar problem for single-hop flows directly apply. Moreover, a dynamic programming-based approach becomes intractable for such multi-timescale quality-of-service (QoS)-constrained traffic in a multihop environment. This motivates us in this paper to develop a useful architecture that enables us to exploit the degree of freedom in choosing appropriate service discipline. Based on the new architecture, we propose three different approaches, each leading to an original algorithm. We study the performance of these algorithms in different scenarios to show both optimality characteristics and to demonstrate the favorable service discipline characteristics they possess. We provide extensive numerical results to compare the performance of all of these solutions to throughput-optimal back-pressure-type schedulers and to longest waiting-time-based schedulers that have provably optimal asymptotic performance characteristics. Our results reveal that the dynamic choice of service discipline of our proposed solutions yields substantial performance improvements compared to both of these types of traditional solutions under nonasymptotic conditions.

Randomization is a powerful and pervasive strategy for developing efficient and practical transmission scheduling algorithms in interference-limited wireless networks. Yet, despite the presence of a variety of earlier works on the design and analysis of particular randomized schedulers, there does not exist an extensive study of the limitations of randomization on the efficient scheduling in wireless networks. In this work, we aim to fill this gap by proposing a common modeling framework and three functional forms of randomized schedulers that utilize queue-length information to probabilistically schedule non-conflicting transmissions. This framework not only models many existing schedulers operating under a time-scale separation assumption as special cases, but it also contains a much wider class of potential schedulers that have not been analyzed. Our main results are the identification of necessary and sufficient conditions on the network topology and on the functional forms used in the randomization for throughput-optimality. Our analysis reveals an exponential and a sub-exponential class of functions that exhibit differences in the throughput-optimality. Also, we observe the significance of the network's scheduling diversity for throughput-optimality as measured by the number of maximal schedules each link belongs to. We further validate our theoretical results through numerical studies.

We attack the challenging problem of designing a scheduling policy for end-to-end deadline-constrained traffic with reliability requirements in a multi-hop network. It is well-known that the end-to-end delay performance for a multi-hop flow has a complex dependence on the high-order statistics of the arrival process and the algorithm itself. Thus, neither the earlier optimization based approaches that aim to meet the long-term throughput demands, nor the solutions that focus on a similar problem for single-hop flows directly apply. Moreover, a dynamic programming-based approach becomes intractable for such multi-time scale Quality-of-Service(QoS)-constrained traffic in a multi-hop environment. This motivates us in this work to develop an alternative model that enables us to exploit the degree of freedom in choosing appropriate service discipline. Based on the new model, we propose two alternative solutions, first based on a Lyapunov-drift minimization approach, and second based on a novel relaxed optimization-formulation. We provide extensive numerical results to compare the performance of both of these solutions to throughput-optimal back-pressure-type schedulers and to longest waiting time based schedulers that have provably optimal asymptotic performance characteristics. Our results reveal that the dynamic choice of service discipline of our proposed solutions yields substantial performance improvements compared to both of these types of traditional solutions under non-asymptotic conditions.

We address the problem of opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario in which the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state information by exploiting the memory inherent in the Markov channels along with ARQ-styled feedback from the scheduled users. Opportunistic scheduling is optimized in two stages: (1) Channel estimation and rate adaptation to maximize the expected immediate rate of the scheduled user; (2) User scheduling, based on the optimized immediate rate, to maximize the overall long term sum-throughput of the downlink. The scheduling problem is a partially observable Markov decision process with the classic `exploitation vs exploration' trade-off that is difficult to quantify. We therefore study the problem in the framework of Restless Multi-armed Bandit Processes (RMBP) and perform a Whittle's indexability analysis. Whittle's indexability is traditionally known to be hard to establish and the index policy derived based on Whittle's indexability is known to have optimality properties in various settings. We show that the problem of downlink scheduling under imperfect channel state information is Whittle indexable and derive the Whittle's index policy in closed form. Via extensive numerical experiments, we show that the index policy has near-optimal performance. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant performance gains and that almost all of these gains can be realized using an easy-to-implement index policy.

In a recent work, we have introduced the notion of proactive resource allocation in wireless networks whereby the predictability of user demands are leveraged to significantly enhance the spectral efficiency of the network in outage limited regimes. In this paper, we expand the horizon to the important scenario of multicast traffic. Our analysis reveals two additional types of gains that can be leveraged in this proactive multicast scenario. The first can be attributed to the basic nature of multicast traffic in which each request would represent a data source rather than a user, as it would in the unicast case. The second is the demand alignment phenomenon whereby the predictive network would wait to gather as much requests as possible and serve them altogether using the same resources. We analytically derive the impact of these advantages on the system diversity gain, which quantifies the exponential decay rate of the outage probability, and further illustrate the resulting gains via numerical results.

We investigate the problem of designing delay-aware joint flow control, routing, and scheduling algorithms in general multi-hop networks for maximizing network utilization. Since the end-to-end delay performance has a complex dependence on the high-order statistics of cross-layer algorithms, earlier optimization-based design methodologies that optimize the long term network utilization are not immediately well-suited for delay-aware design. This motivates us in this work to develop a novel design framework and alternative methods that take advantage of several unexploited design choices in the routing and the scheduling strategy spaces. In particular, we reveal and exploit a crucial characteristic of back pressure-type controllers that enables us to develop a novel link rate allocation strategy that not only optimizes long-term network utilization, but also yields loop free multi-path routes between each source-destination pair. Moreover, we propose a regulated scheduling strategy, based on a token-based service discipline, for shaping the per-hop delay distribution to obtain highly desirable end-to-end delay performance. We establish that our joint flow control, routing, and scheduling algorithm achieves loop-free routes and optimal network utilization. Our extensive numerical studies support our theoretical results, and further show that our joint design leads to substantial end-to-end delay performance improvements in multi-hop networks compared to earlier solutions.

This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing architecture and a dynamic routing-scheduling-coding strategy are introduced for serving multiple sessions when linear network coding is allowed across sessions. This policy provides a novel extension to the class of back-pressure policies by incorporating inter-session coding decisions via simple rules on the relevant queue-length levels. Despite the fact that the capacity region of inter-session coding is a challenging open problem, in this paper, we prove that our algorithm can support any set of rates in a nontrivial characterized region of achievable rates. In addition to its practical implications, this work also provides a theoretical framework in which the gains of inter-session network coding and pure routing can be compared.

The problem of serving multicast flows in a crossbar switch is considered. Intraflow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is achievable with coding but requires a switch speedup when coding is not allowed. The rate region with coding can be characterized in a simple graph-theoretic manner, in terms of the stable set polytope of the "enhanced conflict graph". No such graph-theoretic characterization is known for the case of fanout-splitting without coding. The minimum speedup needed to achieve 100% throughput with coding is shown to be upper bounded by the imperfection ratio of the enhanced conflict graph, where the imperfection ratio measures a certain graph theoretic property of the given graph. When applied to K × N switches with unicasts and broadcasts only, this gives a bound of min(2K-1/K, 2N/N+1) on the speedup. This shows that speedup, which is usually implemented in hardware, can often be substituted by network coding, which can be done in software. Computing an offline schedule (using prior knowledge of the flow rates) is reduced to fractional weighted graph coloring. A graph-theoretic online scheduling algorithm (using only queue occupancy information) is also proposed, that stabilizes the queues for all rates within the rate region.

We analyze asynchronous carrier sense multiple access (CSMA) policies for scheduling packet transmissions in multihop wireless networks subject to collisions under primary interference constraints. While the (asymptotic) achievable rate region of CSMA policies for single-hop networks has been well-known, their analysis for general multihop networks has been an open problem due to the complexity of complex interactions among coupled interference constraints. Our work resolves this problem for networks with primary interference constraints by introducing a novel fixed-point formulation that approximates the link service rates of CSMA policies. This formulation allows us to derive an explicit characterization of the achievable rate region of CSMA policies for a limiting regime of large networks with a small sensing period. Our analysis also reveals the rate at which CSMA achievable rate region approaches the asymptotic capacity region of such networks. Moreover, our approach enables the computation of approximate CSMA link transmission attempt probabilities to support any given arrival vector within the achievable rate region. As part of our analysis, we show that both of these approximations become (asymptotically) accurate for large networks with a small sensing period. Our numerical case studies further suggest that these approximations are accurate even for moderately sized networks.

We study the optimal control of communication networks in the presence of heterogeneous traffic requirements. Specifically, we distinguish the flows into two crucial classes: inelastic for modeling high-priority, delay-sensitive, and fixed-throughput applications; and elastic for modeling low-priority, delay-tolerant, and throughput-greedy applications. We note that the coexistence of such diverse flows creates complex interactions at multiple levels (e.g., flow and packet levels), which prevent the use of earlier design approaches that dominantly assume homogeneous traffic. In this work, we develop the mathematical framework and novel design methodologies needed to support such heterogeneous requirements and propose provably optimal network algorithms that account for the multilevel interactions between the flows. To that end, we first formulate a network optimization problem that incorporates the above throughput and service prioritization requirements of the two traffic types. We, then develop a distributed joint load-balancing and congestion control algorithm that achieves the dual goal of maximizing the aggregate utility gained by the elastic flows while satisfying the fixed throughput and prioritization requirements of the inelastic flows. Next, we extend our joint algorithm in two ways to further improve its performance: in delay through a virtual queue implementation with minimal throughput degradation and in utilization by allowing for dynamic multipath routing for elastic flows. A unique characteristic of our proposed dynamic routing solution is the novel two-stage queueing architecture it introduces to satisfy the service prioritization requirement.

We study the problem of optimal dynamic coding and rate-control for broadcasting deadline-constrained traffic with average delivery ratio constraints over time-varying wireless channels. In particular, we propose and analyze a novel policy that utilizes a combination of pricing and finite-horizon dynamic programming strategies to jointly optimize the operation of the following two components: (i) a dynamic rate allocation policy, which manages the incoming traffic flow rates so as to maximize their weighted sum; (ii) and a dynamic coding window selection policy, which satisfies the flows' individual delivery ratio requirements. Our heuristic fluid analysis of the resulting stochastic network operation indicates that our joint policy maximizes the weighted sum of the deadline-constrained flow throughput subject to heterogeneous delivery ratio requirements imposed on them. We also apply these general results to an important cellular downlink scenario with and without network coding capabilities to study its behavior under various conditions. Our simulations reveal that the dynamic coding strategy outperforms the optimal static coding strategy by opportunistically exploiting the statistical variations in the arrival and channel processes.

In this paper, we consider the problem of rate and power allocation in a multiple-access channel (MAC). Our objective is to obtain rate and power allocation policies that maximize a general concave utility function of average transmission rates on the information-theoretic capacity region of the MAC without using queue-length information. First, we address the utility maximization problem in a nonfading channel and present a gradient projection algorithm with approximate projections. By exploiting the polymatroid structure of the capacity region, we show that the approximate projection can be implemented in time polynomial in the number of users. Second, we present optimal rate and power allocation policies in a fading channel where channel statistics are known. For the case that channel statistics are unknown and the transmission power is fixed, we propose a greedy rate allocation policy and characterize the performance difference of this policy and the optimal policy in terms of channel variations and structure of the utility function. The numerical results demonstrate superior convergence rate performance for the greedy policy compared to queue-length-based policies. In order to reduce the computational complexity of the greedy policy, we present approximate rate allocation policies which track the greedy policy within a certain neighborhood.

In this work, we study the control of communication networks in the presence of both inelastic and elastic traffic flows. The characteristics of these two types of traffic differ significantly. Hence, earlier approaches that focus on homogeneous scenarios with a single traffic type are not directly applicable. We formulate a new network optimization problem that incorporates the performance requirements of inelastic and elastic traffic flows. The solution of this problem provides us with a new queueing architecture, and distributed load balancing and congestion control algorithm with provably optimal performance. In particular, we show that our algorithm achieves the dual goal of maximizing the aggregate utility gained by the elastic flows while satisfying the demands of inelastic flows. Our base optimal algorithm is extended to provide better delay performance for both types of traffic with minimal degradation in throughput. It is also extended to the practically relevant case of dynamic arrivals and departures. Our solution allows for a controlled interaction between the performance of inelastic and elastic traffic flows. This performance can be tuned to achieve the appropriate design tradeoff. The network performance is studied both theoretically and through extensive simulations.

We consider the problem of rate allocation in a fading Gaussian multiple-access channel with fixed transmission powers. The goal is to maximize a general concave utility function of the expected achieved rates of the users. There are different approaches to this problem in the literature. From an information theoretic point of view, rates are allocated only by using the channel state information. The queueing theory approach utilizes the global queue-length information for rate allocation to guarantee throughput optimality as well as maximizing a utility function of the rates. In this work, we make a connection between these two approaches by showing that the information theoretic capacity region of a multiple-access channel and its stability region are equivalent. Moreover, our numerical results show that a simple greedy policy which does not use the queue-length information can outperform queue-length based policies in terms of convergence rate and fairness.

In an unreliable packet network setting, we study the performance gains of optimal transmission strategies in the presence and absence of coding capability at the transmitter, where performance is measured in delay and throughput. Although our results apply to a large class of coding strategies including maximum-distance separable (MDS) and Digital Fountain codes, we use random network codes in our discussions because these codes have a greater applicability for complex network topologies. To that end, after introducing a key setting in which performance analysis and comparison can be carried out, we provide closed-form as well as asymptotic expressions for the delay performance with and without network coding. We show that the network coding capability can lead to arbitrarily better delay performance as the system parameters scale when compared to traditional transmission strategies without coding. We further develop a joint scheduling and random-access scheme to extend our results to general wireless network topologies.

In this paper, we provide and study a general framework that allows the development of distributed mechanisms to achieve full utilization of multi-hop wireless networks. In particular, we describe a generic randomized routing, scheduling and flow control scheme that is applicable to a large class of interference models, and that allows for the development of distributed algorithms which maximize network throughput and utilization. In particular, we focus on a specific interference model, namely the secondary interference model, and develop distributed algorithms with polynomial communication and computation complexity in the network size. This is an important result given that earlier throughput-optimal algorithms developed for such a model relies on the solution to an NP-hard problem. This results in a polynomial complexity cross-layer algorithm that achieves throughput optimality and fair allocation of network resources amongst the users. We further show that our algorithmic approach enables us to efficiently approximate the capacity region of a multi-hop wireless network.

We consider the problem of serving multicast flows in a crossbar switch. We show that linear network coding across packets of a flow can sustain traffic patterns that cannot be served if network coding were not allowed. Thus, network coding leads to a larger rate region in a multicast crossbar switch. We demonstrate a traffic pattern which requires a switch speedup if coding is not allowed, whereas, with coding the speedup requirement is eliminated completely. In addition to throughput benefits, coding simplifies the characterization of the rate region. We give a graph-theoretic characterization of the rate region with fanout splitting and intra-flow coding, in terms of the stable set polytope of the "enhanced conflict graph" of the traffic pattern. Such a formulation is not known in the case of fanout splitting without coding. We show that computing the offline schedule (i.e. using prior knowledge of the flow arrival rates) can be reduced to certain graph coloring problems. Finally, we propose online algorithms (i.e. using only the current queue occupancy information) for multicast scheduling based on our graph-theoretic formulation. In particular, we show that a maximum weighted stable set algorithm stabilizes the queues for all rates within the rate region.

Abstract — We consider a multi-hop wireless network shared by many users. For an interference model that only constrains a node to either transmit or receive at a time, but not both, we propose an architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm. We show that the proposed joint congestion control and scheduling algorithm supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms. I.

In this paper, we describe and analyze a joint scheduling, routing and congestion control mechanism for wireless networks, that asymptotically guarantees stability of the buffers and fair allocation of the network resources. The queue-lengths serve as common information to different layers of the network protocol stack. Our main contribution is to prove the asymptotic optimality of a primal-dual congestion controller, which is known to model different versions of transmission control protocol well

In this correspondence, we consider a cellular network consisting of a base station and N receivers. The channel states of the receivers are assumed to be identical and independent of each other. The goal is to compare the throughput of two different scheduling policies (a queue-length-based (QLB) policy and a greedy policy) given an upper bound on the queue overflow probability or the delay violation probability. We consider a multistate channel model, where each channel is assumed to be in one of L states. Given an upper bound on the queue overflow probability or an upper bound on the delay violation probability, we show that the total network throughput of the (QLB) policy is no less than the throughput of the greedy policy for all N. We also obtain a lower bound on the throughput of the (QLB) policy. For sufficiently large N, the lower bound is shown to be tight, strictly increasing with N, and strictly larger than the throughput of the greedy policy. Further, for a simple multistate channel model-ON-OFF channel, we prove that the lower bound is tight for all N

We consider the problem of allocating resources (time slots, frequency, power, etc.) at a base station to many competing flows, where each flow is intended for a different receiver. The channel conditions may be time-varying and different for different receivers. It is well-known that appropriately chosen queue-length based policies are throughput-optimal while other policies based on the estimation of channel statistics can be used to allocate resources fairly (such as proportional fairness) among competing users. In this paper, we show that a combination of queue-length-based scheduling at the base station and congestion control implemented either at the base station or at the end users can lead to fair resource allocation and queue-length stability.

We consider the problem of allocating resources at a base station to many competing flows, when each flow is intended for a different receiver. The channel conditions may be time-varying and different for different receivers. It has been shown in A. Eryilmaz and R. Srikant (2005) that in a delay-free network, a combination of queue-length-based scheduling at the base station and congestion control at the end users can guarantee queue-length stability and fair resource allocation. In this paper, we extend this result to wireless networks where the congestion information from the base station is received with a feedback delay at the transmitters. The delays can be heterogeneous (i.e., different users may have different round-trip delays) and time-varying, but are assumed to be upper-bounded, with possibly very large upper bounds. We show that the joint congestion control-scheduling algorithm continues to be stable and continues to provide a fair allocation of the network resources.

We study the problem of stable scheduling for a class of wireless networks. The goal is to stabilize the queues holding information to be transmitted over a fading channel. Few assumptions are made on the arrival process statistics other than the assumption that their mean values lie within the capacity region and that they satisfy a version of the law of large numbers. We prove that, for any mean arrival rate that lies in the capacity region, the queues will be stable under our policy. Moreover, we show that it is easy to incorporate imperfect queue length information and other approximations that can simplify the implementation of our policy.