The quantum internet uses high-quality entanglement distribution to enable long-distance communication. The quality of entanglement is measured by distillable entanglement, which quantifies how many maximally entangled states can be refined from a given ensemble of noisy states. Therefore, identifying highly distillable states is essential for ensuring efficient entanglement distribution. Given$K$ensembles of noisy entangled states, we address the problem of identifying highly distillable states, i.e., states with distillable entanglement exceeding a prespecified threshold. We propose entanglement distillation-based estimation protocols on two copies of bipartite$2 \times 2$and$2 \times 3$pure states. We characterize their distillable entanglement by estimating statedependent parameters from measurement statistics. We identify a structural connection to the Thresholding Bandit problem (TBP) in classical Multi-Armed Bandits (MAB) literature and use these policies to obtain guarantees on the sample complexity for estimating the state-dependent parameters. We also provide numerical results showcasing the performance of the proposed distillation protocol and TBP policies.

We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where information bits become useless after a certain time. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. Motivated by the empirical performance, we show that standard Arıkan’s Polar transform polarizes the M/M/1 EQC.

We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where quantum bits tend to decohere rapidly. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving block code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. We show that standard Arıkan’s Polar transform polarizes the EQC for certain restricted class of erasure probability functions. We also highlight some possible approaches and the corresponding challenges involved in proving the polarization of a general EQC.

A queue-channel is a model that captures waiting time-dependent degradation of information bits—a scenario motivated by quantum communications and delay-sensitive streaming. Recent work has characterised the capacity of the erasure queue-channel [1], and other noise models encountered in quantum communications. In this paper, we study an erasure queue-channel with feedback, and ask after the optimal transmission strategy to minimize waiting-induced erasures. Specifically, we assume that instantaneous feedback of queue-length (or of the queue-channel output) is available at the transmitter, which can modulate the rate of Poisson transmissions into the queue-channel. We pose an optimal control problem using HJB-style equations to maximize the information capacity, when the transmitter can choose from a bounded set of transmission rates. We show (under a numerically verifiable condition) that the optimal transmission policy is a single-threshold policy of the bang-bang type. In other words, transmitting at the maximum (minimum) possible rate when the queue is below (above) a threshold, maximizes the information capacity of the erasure queue-channel with feedback.

We consider maximizing the long-term average reward in a single server queuing system, where the reward obtained for a job is a non-increasing, possibly nonlinear function of its sojourn time. The motivation behind this work comes from delay-sensitive applications, including quantum information processing and multimedia streaming. Although the goal of optimizing the total sojourn time is well-studied, optimizing a nonlinear function of the sojourn times remains unexplored to the best of our knowledge. We consider two arrival models - the first is a ‘burst arrival’ model, wherein all jobs arrive at the server at the same instant. We show that shortest job first (SJF) maximizes the average reward for any monotonic function of the sojourn times. In the second setting, jobs arrive according to some stochastic process with i.i.d. service requirements. This setting is significantly more challenging to analyze, and identifying an optimal discipline remains elusive. We introduce a new service discipline, shortest predicted sojourn time (SPST), and provide analytical guarantees under specific settings. Numerically, we demonstrate that SPST outperforms well-known disciplines across multiple settings.

In several applications such as clinical trials and financial portfolio optimization, the expected value (or the average reward) does not satisfactorily capture the merits of a drug or a portfolio. In such applications, risk plays a crucial role, and a risk-aware performance measure is preferable, so as to capture losses in the case of adverse events. This survey aims to consolidate and summarise the existing research on risk measures, specifically in the context of multi-armed bandits. We review various risk measures of interest, and comment on their properties. Next, we review existing concentration inequalities for various risk measures. Then, we proceed to defining risk-aware bandit problems, We consider algorithms for the regret minimization setting, where the exploration-exploitation tradeoff manifests, as well as the best arm identification setting, which is a pure exploration problem—both in the context of risk-sensitive measures. We conclude by commenting on persisting challenges and fertile areas for future research.

We study the fundamental limits of classical communication using quantum states that decohere as they traverse through a network of queues. We consider a network of Markovian queues, known as a Jackson network, with a single source or multiple sources and a single destination. Qubits are communicated through this network with inevitable buffering at intermediate nodes. We model each node as a ‘queue-channel,’ wherein as the qubits wait in buffer, they continue to interact with the environment and suffer a waiting time-dependent noise. Focusing on erasures, we first obtain explicit classical capacity expressions for simple topologies such as tandem queue-channel and parallel queue-channel. Using these as building blocks, we characterize the classical capacity of a general quantum Jackson network with waiting time-dependent erasures. Throughout, we study two types of quantum networks, namely, (i) Repeater-assisted and (ii) Repeater-less. We also obtain optimal pumping rates and routing probabilities to maximize capacity in simple topologies. More broadly, our work quantifies the impact of delay-induced decoherence on the fundamental limits of classical communication over quantum networks.

Traditional multi-armed bandit (MAB) formulations usually make certain assumptions about the underlying arms’ distributions, such as bounds on the support or their tail behaviour. Moreover, such parametric information is usually ‘baked’ into the algorithms. In this paper, we show that specialized algorithms that exploit such parametric information are prone to inconsistent learning performance when the parameter is misspecified. Our key contributions are twofold: (i) We establish fundamental performance limits ofstatistically robustMAB algorithms under the fixed-budget pure exploration setting, and (ii) We propose two classes of algorithms that are asymptotically near-optimal. Additionally, we consider a risk-aware criterion for best arm identification, where the objective associated with each arm is a linear combination of the mean and the conditional value at risk (CVaR). Throughout, we make a very mild ‘bounded moment’ assumption, which lets us work with both light-tailed and heavy-tailed distributions within a unified framework.

We study regret minimization in a stochastic multi-armed bandit setting, and establish a fundamental trade-off between the regret suffered under an algorithm, and its statistical robustness. Considering broad classes of underlying arms’ distributions, we show that bandit learning algorithms with logarithmic regret are always inconsistent and that consistent learning algorithms always suffer a super-logarithmic regret. This result highlights the inevitable statistical fragility of all ‘logarithmic regret’ bandit algorithms available in the literature - for instance, if a UCB algorithm designed for 1-subGaussian distributions is used in a subGaussian setting with a mismatched variance parameter, the learning performance could be inconsistent. Next, we show a positive result: statistically robust and consistent learning performance is attainable if we allow the regret to be slightly worse than logarithmic. Specifically, we propose three classes of distribution oblivious algorithms that achieve an asymptotic regret that is arbitrarily close to logarithmic.

The Least Recently Used (LRU) policy is widely used in caching, since it is computationally inexpensive and can be implemented ‘on-the-fly.’ However, existing analyses of content- wise hit-rates under LRU have expressions whose complexity grows rapidly with the buffer size. In this paper, we derive a simple yet accurate approximation for the LRU content-wise hitrates under Zipf-distributed requests, in the regime of a large content population. To this end, we map the characteristic time of a content in the LRU policy to the classical Coupon Collector’s Problem (CCP). We justify the accuracy of these approximations by showing analytically that the characteristic time concentrates sharply around its mean. Our bounds highlight and quantify the impact of cache-size scaling as well as the variations in content popularity on the accuracy of the hit-rate estimates. Specifically, we show that these estimates become more accurate with a decrease in Zipf parameter β or an increase in the cache-size scaling. Finally, our analysis of the CCP with Zipf-distributed coupons could be of independent interest.

Accurate taxi demand-supply forecasting is a challenging application of ITS (Intelligent Transportation Systems), due to the complex spatial and temporal patterns involved. We investigate the impact of different spatial partitioning techniques on the prediction performance of an LSTM (Long Short-Term Memory) network, in the context of taxi demand-supply forecasting. We consider two tessellation schemes: (i) the variable-sized Voronoi tessellation, and (ii) the fixed-sized Geohash tessellation. While the widely employed ConvLSTM (Convolutional LSTM) method can model fixed-sized Geohash partitions, the standard convolutional filters cannot be applied on variable-sized Voronoi partitions. To explore the impact of the Voronoi strategy, we propose the use of a GraphLSTM (Graph-based LSTM) model, by representing the Voronoi spatial partitions as nodes on an arbitrarily structured graph. The GraphLSTM model offers competitive performance against the ConvLSTM model, at a lower computational complexity, across three real-world large-scale taxi demand-supply data sets, with different performance metrics. To ensure superior performance across diverse settings, a HEDGE based ensemble learning algorithm is applied over the ConvLSTM and the GraphLSTM networks.

Conditional Value-at-Risk (CVaR) is a widely used risk metric in applications such as finance. We derive concentration bounds for CVaR estimates, considering separately the cases of sub-Gaussian, light-tailed and heavy-tailed distributions. For the sub-Gaussian and light-tailed cases, we use a classical CVaR estimator based on the empirical distribution constructed from the samples. For heavy-tailed random variables, we assume a mild ‘bounded moment’ condition, and derive a concentration bound for a truncation-based estimator. Our concentration bounds exhibit exponential decay in the sample size, and are tighter than those available in the literature for the above distribution classes. To demonstrate the applicability of our concentration results, we consider the CVaR optimization problem in a multi-armed bandit setting. Specifically, we address the best CVaR-arm identification problem under a fixed budget. Using our CVaR concentration results, we derive an upper-bound on the probability of incorrect arm identification.

Classical multi-armed bandit problems use the expected value of an arm as a metric to evaluate its goodness. However, the expected value is a risk-neutral metric. In many applications like finance, one is interested in balancing the expected return of an arm (or portfolio) with the risk associated with that return. In this paper, we consider the problem of selecting the arm that optimizes a linear combination of the expected reward and the associated Conditional Value at Risk (CVaR) in a fixed budget best-arm identification framework. We allow the reward distributions to be unbounded or even heavy-tailed. For this problem, our goal is to devise algorithms that are entirely distribution oblivious, i.e., the algorithm is not aware of any information on the reward distributions, including bounds on the moments/tails, or the suboptimality gaps across arms. In this paper, we provide a class of such algorithms with provable upper bounds on the probability of incorrect identification. In the process, we develop a novel estimator for the CVaR of unbounded (including heavy-tailed) random variables and prove a concentration inequality for the same, which could be of independent interest. We also compare the error bounds for our distribution oblivious algorithms with those corresponding to standard non-oblivious algorithms. Finally, numerical experiments reveal that our algorithms perform competitively when compared with non-oblivious algorithms, suggesting that distribution obliviousness can be realised in practice without incurring a significant loss of performance.

Age-of-Information (AoI) is a recently proposed metric for quantifying the freshness of information from the UE's perspective in a communication network. Recently, Kadota et al. [1] have proposed an index-type approximately optimal scheduling policy for minimizing the average-AoI metric for a downlink transmission problem. For delay-sensitive applications, including real-time control of a cyber-physical system, or scheduling URLLC traffic in 5G, it is essential to have a more stringent uniform control on AoI across all users. In this paper, we derive an exactly optimal scheduling policy for this problem in a downlink system with erasure channels. Our proof of optimality involves an explicit solution to the associated average-cost Bellman Equation, which might be of independent theoretical interest. We also show that the resulting Age-process is positive recurrent under the optimal policy, and has an exponentially light tail. Finally, motivated by typical applications in small-cell residential networks, we consider the problem of minimizing the peak-AoI with throughput constraints to specific UEs, and derive a heuristic policy for this problem. Extensive numerical simulations have been carried out to compare the efficacy of the proposed policies with other well-known scheduling policies, such as Randomized scheduling and Proportional Fair.

We propose distributed scheduling algorithms that guarantee a constant fraction of the maximum throughput for typical wireless topologies, and have O(1) delay and complexity in the network size. Our algorithms resolve collisions among pairs of conflicting nodes by assigning a master-slave hierarchy. When the master-slave hierarchy is chosen randomly, our algorithm matches the throughput performance of the maximal scheduling policies, with a complexity and delay that do not scale with network size. When the master-slave hierarchy is chosen based on the network topology, the throughput performance of our algorithm is characterized by a parameter of the conflict graph called the master-interference degree. For commonly used conflict graph topologies, our results lead to the best known throughput guarantees among the algorithms that have O(1) delay and complexity. Numerical results indicate that our algorithms out-perform the existing O(1) complexity algorithms like Q-CSMA.

A key problem in location-based modeling and forecasting lies in identifying suitable spatial and temporal resolutions. In particular, judicious spatial partitioning can play a significant role in enhancing the performance of location-based forecasting models. In this paper, we investigate two widely used tessellation strategies for partitioning city space, in the context of real-time taxi demand forecasting. Our study compares (1) the Geohash tessellation and (2) the Voronoi tessellation, using two distinct taxi demand data sets, over multiple time scales. For the purpose of comparison, we employ classical time-series tools to model the spatio-temporal demand. Our study finds that the performance of each tessellation strategy is highly dependent on the city geography, spatial distribution of the data, and the time of the day, and that neither strategy is found to perform optimally across the forecast horizon. We propose a combining algorithm that selects the best tessellation strategy at each time step, based on their recent performance. Our algorithm is a non-stationary variant of the well-known HEDGE algorithm for choosing the best advice from multiple experts. We show that the proposed strategy performs consistently better than either of the two tessellation strategies across the data sets considered, at multiple time scales, and with different performance metrics. We achieved an average accuracy of above 80% per km2for both data sets considered at 60 min aggregation levels.

We address the problem of downlink resource allocation in the presence of time-varying interference. We consider a scenario where users served by a base station face interference from a neighboring base station. We model the interference from the neighboring base station as an ON/OFF renewal process, that arises due to its idle and busy cycles. The users feedback their downlink signal to interference plus noise ratio (SINR) values to their base station, but these values are outdated. In this setting, we characterize how the resource allocation layer can optimally exploit the reported SINR values, which could be unreliable due to time-varying interference. In particular, we propose resource allocation policies in two well-known paradigms. First, we address the problem of α-fair scheduling, and propose a policy that ensures asymptotic convergence to the optimal α-fair throughput. Second, we propose a throughput optimal resource allocation policy, i.e., a policy that can stably support the largest possible set of traffic rates under the interference scenario considered. Estimating the outage probability from the outdated SINR values plays an important role in both scheduling paradigms, and we accomplish this using tool from renewal theory.

In the information overload regime, human communication tasks such as responding to email are well-modeled as priority queues, where priority is determined by a mix of intrinsic motivation and extrinsic motivation corresponding to the task's importance to the sender. We view priority queuing from a principal-agent perspective, and characterize the effect of priority-misalignment and information asymmetry between task senders and task receivers in both single-agent and multi-agent settings. In the single-agent setting, we find that discipline can override misalignment. Although variation in human interests leads to performance loss in the single-agent setting, the same variability is useful to the principal with optimal routing of tasks, if the principal has suitable information about agents' priorities. Our approach starts to quantitatively address the effect of human dynamics in routine communication tasks.

We consider a carrier sense multiple access (CSMA)-based scheduling algorithm for a single-hop wireless network under a realistic signal-to-interference-plus-noise ratio model for the interference. We propose two local optimization-based approximation algorithms to efficiently estimate certain attempt rate parameters of CSMA called fugacities. It is known that adaptive CSMA can achieve throughput optimality by sampling feasible schedules from a Gibbs distribution, with appropriate fugacities. Unfortunately, obtaining these optimal fugacities is an NP-hard problem. Furthermore, the existing adaptive CSMA algorithms use a stochastic gradient descent-based method, which usually entails an impractically slow (exponential in the size of the network) convergence to the optimal fugacities. To address this issue, we first propose an algorithm to estimate the fugacities, that can support a given set of desired service rates. The convergence rate and the complexity of this algorithm are independent of the network size, and depend only on the neighborhood size of a link. Furthermore, we show that the proposed algorithm corresponds exactly to performing the well-known Bethe approximation to the underlying Gibbs distribution. Then, we propose another local algorithm to estimate the optimal fugacities under a utility maximization framework, and characterize its accuracy. Numerical results indicate that the proposed methods have a good degree of accuracy, and achieve extremely fast convergence to near-optimal fugacities, and often outperform the convergence rate of the stochastic gradient descent by a few orders of magnitude.

This paper focuses on the design and analysis of scheduling policies for multi-class queues, such as those found in wireless networks and high-speed switches. In this context, we study the response-time tail under generalized max-weight policies in settings where the traffic flows are highly asymmetric. Specifically, we consider a setting where a bursty flow, modeled using heavy-tailed statistics, competes with a more benign, light-tailed flow. In this setting, we prove that classical max-weight scheduling, which is known to be throughput optimal, results in the light-tailed flow having heavy-tailed response times. However, we show that via a careful design of inter-queue scheduling policy (from the class of generalized max-weight policies) and intra-queue scheduling policies, it is possible to maintain throughput optimality, and guarantee light-tailed delays for the light-tailed flow, without affecting the response-time tail for the heavy-tailed flow.

We address the problem of optimal downlink resource allocation in an OFDMA system, in a scenario where very limited channel quality information (CQI) is available at the base station. This paper is particularly applicable in the context of the LTE downlink since the feedback mechanism that we consider closely resembles one of the CQI reporting modes in LTE. Specifically, the users only report the indices of their best M subbands and an effective CQI corresponding to these best M bands. Our policy simultaneously performs optimal subband assignment and rate allocation, by taking into account channel quality and the queue backlogs of each user. The technical novelty of our work lies in exploiting a limit theorem on the best SNRs reported by the users, and combining it within a Lyapunov stability framework. We show that our policy is throughput maximizing among all policies, which are constrained to the CQI mechanism considered. Numerical results indicate that, in terms of throughput and average delay, our policy compares favorably to existing resource allocation policies such as proportional fair.

In this paper, we derive optimal transmission policies for energy harvesting sensors to maximize the utility obtained over a finite horizon. First, we consider a single energy harvesting sensor, with discrete energy arrival process, and a discrete energy consumption policy. Under this model, we show that the optimal finite horizon policy is a threshold policy, and explicitly characterize the thresholds, and the thresholds can be precomputed using a recursion. Next, we address the case of multiple sensors, with only one of them allowed to transmit at any given time to avoid interference, and derive an explicit optimal policy for this scenario as well.

In today's regime of information overload, it is reasonable to model a human executing routine tasks such as responding to emails as a priority queue. Humans typically prioritize task execution based on intrinsic motivators such as interest in the task, as well as extrinsic motivation stemming from the importance of the task to the sender. We view the human priority queue from the perspective of a principal-agent problem and characterize the effect of misalignment between the task sender's and task receiver's priorities. Our model provides insights into how different levels of misalignment affect delays of tasks of varying importance. Further, our approach starts to quantitatively address the effect of human dynamics in routine communication tasks, such as responding to emails.

We study the problem of scheduling over time varying links in a network that serves both heavy-tailed and light tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic (the heavy queue), and the other receives light-tailed traffic (the light queue). The queues are connected to the server through time-varying ON/OFF links, which model fading wireless channels. We first show that the policy that gives complete priority to the light-tailed traffic guarantees the best possible tail behavior of both queue backlog distributions, whenever the queues are stable. However, the priority policy is not throughput maximizing, and can cause undesirable instability effects in the heavy queue. Next, we study the class of throughput optimal max-weight-α scheduling policies. We discover a threshold phenomenon, and show that the steady state light queue backlog distribution is heavy-tailed for arrival rates above a threshold value, and light-tailed otherwise. We also obtain the exact tail coefficient of the light queue backlog distribution under max-weight-α scheduling. Finally, we study a log-max-weight scheduling policy, which is throughput optimal, and ensures that the light queue backlog distribution is light-tailed.

We address the problem of optimal downlink resource allocation in an OFDMA system, in a scenario where very limited channel quality information (CQI) is available at the base-station. Our work is particularly applicable in the context of the LTE downlink, since the feedback mechanism we consider closely resembles one of the CQI reporting modes in LTE. Specifically, the users only report the indices of their best M sub-bands and an effective CQI corresponding to these best M bands. Our policy simultaneously performs optimal sub-band assignment and rate allocation, by taking into account channel quality as well as the queue backlogs of each user. The technical novelty of our work lies in exploiting a limit theorem on the best SNRs reported by the users, and combining it within a Lyapunov stability framework. We show that our policy is throughput maximizing among all policies which are constrained to the CQI mechanism considered. Numerical results indicate that in terms of throughput and average delay, our policy compares favorably to existing resource allocation policies such as proportional fair.

This paper focuses on the design and analysis of scheduling policies for multi-class queues, such as those found in wireless networks and high-speed switches. In this context, we study the response time tail under generalized max-weight policies in settings where the traffic flows are highly asymmetric. Specifically, we study an extreme setting with two traffic flows, one heavy-tailed, and one light-tailed. In this setting, we prove that classical max-weight scheduling, which is known to be throughput optimal, results in the light-tailed flow having heavy-tailed response times. However, we show that via a careful design of inter-queue scheduling policy (from the class of generalized max-weight policies) and intra-queue scheduling policies, it is possible to maintain throughput optimality, and guarantee light-tailed delays for the light-tailed flow, without affecting the response time tail for the heavy-tailed flow.

We consider a system consisting of N parallel queues, served by one server. Time is slotted, and the server serves one of the queues in each time slot, according to some scheduling policy. We first characterize the exponent of the buffer overflow probability and the most likely overflow trajectories under the Longest Queue First (LQF) scheduling policy. Under statistically identical arrivals to each queue, we show that the buffer overflow exponents can be simply expressed in terms of the total system occupancy exponent of m parallel queues, for some m ≤ N. We next turn our attention to the rate of queue length information needed to operate a scheduling policy, and its relationship to the buffer overflow exponents. It is known that queue length blind policies such as processor sharing and random scheduling perform worse than the queue aware LQF policy, when it comes to buffer overflow probability. However, we show that the overflow exponent of the LQF policy can be preserved with arbitrarily infrequent queue length updates.

We consider a dynamic spectrum access system in which Secondary Users (SUs) choose to either acquire dedicated spectrum or to use spectrum-holes (white spaces) which belong to Primary Users (PUs). The trade-off incorporated in this decision is between immediate yet costly transmission and free but delayed transmission (a consequence of both the possible appearance of PUs and sharing the spectrum holes with multiple SUs). We first consider a system with a single PU band, in which the SU decisions are fixed. Employing queueing-theoretic methods, we obtain explicit expressions for the expected delays associated with using the PU band. Based on that, we then consider self-interested SUs and study the interaction between them as a non-cooperative game. We prove the existence and uniqueness of a symmetric Nash equilibrium, and characterize the equilibrium behavior explicitly. Using our equilibrium results, we show how to maximize revenue from renting dedicated bands to SUs and briefly discuss the extension of our model to multiple PUs. Finally, since spectrum sensing can be resource-consuming, we characterize the gains provided by this capability.

We investigate the asymptotic behavior of the steady-state queue-length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput-optimal max-weight-$\alpha $scheduling policies and derive an exact asymptotic characterization of the steady-state queue-length distributions. In particular, we show that the tail of the light queue distribution is at least as heavy as a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also shows that the celebrated max-weight scheduling policy leads to the worst possible tail coefficient of the light queue distribution, among all nonidling policies. Motivated by the above negative result regarding the max-weight-$\alpha $policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail while still being throughput-optimal.

We consider scheduling over a wireless system, where the channel state information is not available a priori to the scheduler, but can be inferred from the past. Specifically, the wireless system is modeled as a network of parallel queues. We assume that the channel state of each queue evolves stochastically as an ON/OFF Markov chain. The scheduler, which is aware of the queue lengths but is oblivious of the channel states, has to choose one queue at a time for transmission. The scheduler has no information regarding the current channel states, but can estimate them by using the acknowledgment history. We first characterize the capacity region of the system using tools from Markov Decision Processes (MDP) theory. Specifically, we prove that the capacity region boundary is the uniform limit of a sequence of Linear Programming (LP) solutions. Next, we combine the LP solution with a queue length based scheduling mechanism that operates over long `frames,' to obtain a throughput optimal policy for the system. By incorporating results from MDP theory within the Lyapunov-stability framework, we show that our frame-based policy stabilizes the system for all arrival rates that lie in the interior of the capacity region.

We investigate the asymptotic behavior of the steady-state queue length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-α scheduling policies, and derive an exact asymptotic characterization of the steady-state queue length distributions. In particular, we show that the tail of the light queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also shows that the celebrated max-weight scheduling policy leads to the worst possible tail of the light queue distribution, among all non-idling policies. Motivated by the above `negative' result regarding the max-weight-α policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail, while still being throughput optimal.

We consider a dynamic spectrum access system in which Secondary Users (SUs) choose to either acquire dedicated spectrum or to use spectrum-holes (white spaces) which belong to Primary Users (PUs). The tradeoff incorporated in this decision is between immediate yet costly transmission and free but delayed transmission (a consequence of both the possible appearance of PUs and sharing the spectrum holes with multiple SUs). We first consider a system with a single PU band, in which the SU decisions are fixed. Employing queueing-theoretic methods, we obtain explicit expressions for the expected delays associated with using the PU band. Based on that, we then consider self-interested SUs and study the interaction between them as a noncooperative game. We prove the existence and uniqueness of a symmetric Nash equilibrium, and characterize the equilibrium behavior explicitly. Using our equilibrium results, we show how to maximize revenue from renting dedicated bands to SUs. Finally, we extend the scope to a scenario with multiple PUs, show that the band-pricing analysis can be applied to some special cases, and provide numerical examples.

We study the role played by queue length information in the operation of flow control and server allocation policies. We first consider a simple model of a single server queue with congestion-based flow control. The input rate at any instant is decided by a flow control policy, based on the queue occupancy. We identify a simple “two-threshold” control policy, which achieves the best possible exponential scaling for the queue congestion probability, for any rate of control. We show that when the control channel is reliable, the control rate needed to ensure the optimal decay exponent for the congestion probability can be made arbitrarily small. However, if control channel erasures occur probabilistically, we show the existence of a critical erasure probability threshold beyond which the congestion probability undergoes a drastic increase due to the frequent loss of control packets. We also determine the optimal amount of error protection to apply to the control signals by using a simple bandwidth sharing model. Finally, we show that the queue length based server allocation problem can also be treated using this framework and that the results obtained for the flow control setting can also be applied to the server allocation case.

The goal of this paper is to characterize the tradeoff between the rate of control and network congestion for flow control policies. We consider a simple model of a single server queue with congestion-based flow control. The input rate at any instant is decided by a flow control policy, based on the queue occupancy. We identify a simple 'two threshold' control policy, which achieves the best possible congestion probability, for any rate of control. We show that in the absence of control channel errors, the control rate needed to ensure the optimal decay exponent for the congestion probability can be made arbitrarily small. However, if control channel errors occur probabilistically, we show the existence of a critical error probability threshold beyond which the congestion probability undergoes a drastic increase due to the frequent loss of control packets. Finally, we determine the optimal amount of error protection to apply to the control signals by using a simple bandwidth sharing model.

We study the problem of efficiently scheduling users in a Gaussian broadcast channel withMtransmit antennas andKindependent receivers, each with a single antenna. We first focus on a scenario with two transmit antennas and statistically identical users, and analyze the gap between the full sum capacity and the rate that can be achieved by transmitting to a suitably selected pair of users. In particular, we consider a scheme that picks the user with the largest channel gain, and selects a second user from the nextL- 1 strongest ones to form the best pair, taking channel orientations into account as well. We prove that the expected rate gap converges to 1/(L- 1) nats/symbol when the total number of usersKtends to infinity. AllowingLto increase withK, it may be deduced that transmitting to a properly chosen pair of users is asymptotically optimal, while considerably reducing the feedback overhead and scheduling complexity. Next, we tackle the problem of maximizing aweightedsum rate in a scenario with heterogeneous user characteristics. We establish a novel upper bound for the weighted sum capacity, which we then use to show that the maximum expected weighted sum rate can be asymptotically achieved by transmitting to a suitably selected subset of at mostMCusers, whereCdenotes the number of distinct user classes. Numerical experiments indicate that the asymptotic results are remarkably accurate and that the proposed schemes operate close to absolute performance bounds, even for a moderate number of users.

The capacity region of the Gaussian multi-antenna broadcast channel was characterized recently in [19]. It was shown that a scheme based on Dirty Paper Coding [2] achieves the full capacity region when the transmitter has perfect channel state information. However, this scheme potentially involves considerable amounts of feedback and complex algorithms for coding and user selection. This has led to a quest for practical transmission schemes and ways to reduce the amount of channel state information required. In particular, it has been shown that when the total number of users is large, the sum capacity can be closely approached by transmitting to a small subset of near-orthogonal users. In order to further quantify the latter observation, we study a Gaussian broadcast channel with two transmit antennas and K statistically identical, independent users each with a single receive antenna. We obtain an exact asymptotic characterization of the gap between the full sum capacity and the rate that can be achieved by transmitting to a suitably selected pair of users. Specifically, we consider various simple schemes for user-pair selection that take into account the channel norms as well as the relative orientation of the channel vectors. We conclude that a scheme that picks the strongest user and selects a second user to form the best pair, is asymptotically optimal, while also being attractive in terms of feedback and operational complexity.