The performance of wireless scheduling algorithms directly depends on the availability and accuracy of channel state information (CSI) at the scheduler. As CSI updates must propagate across the network, they are delayed as they arrive at the controller. In this paper, we analyze the effect that delayed CSI has on the throughput performance of scheduling in wireless networks. By accounting for the delays in CSI as they relate to the network topology, we revisit the comparison between centralized and distributed scheduling. We explore the tradeoff between optimal centralized scheduling using delayed CSI and imperfect distributed scheduling using timely CSI. In particular, we show that under certain conditions distributed scheduling outperforms the optimal centralized scheduling policy and we characterize the point at which distributed scheduling outperforms centralized scheduling for tree and clique networks. Lastly, we propose a partially distributed scheme that achieves high throughput amidst delayed CSI.

We consider a multi-channel communication system in which a transmitter has access to M channels, but does not know the state of any of the channels. We model the channel state using an ON/OFF Markov process, and allow the transmitter to probe a single channel at predetermined probing intervals to decide over which channel to transmit. For models in which the transmitter must transmit over the probed channel, it has been shown that a myopic policy probing the channel most likely to be ON is optimal. In this paper, we allow the transmitter to select a channel over which to transmit that is potentially different from the probed channel. For a system of two channels, we show that the choice of which channel to probe does not affect the throughput. For a system with many channels, we show that a probing policy that probes the channel that is the second-most likely to be ON results in higher throughput. We extend the channel probing problem to dynamically choose when to probe based on probing history, and characterize the optimal probing policy for various scenarios.

We consider the impact of delayed state information on the performance of centralized wireless scheduling algorithms. Since state updates must be collected from throughout the network, they are inevitably delayed, and this delay is proportional to the distance of each respective node to the controller. In this paper, we analyze the optimal controller placement resulting from this delayed state information. We propose a dynamic controller placement framework, in which the controller is relocated using delayed queue length information at each node, and transmissions are scheduled based on channel and queue length information. We characterize the throughput region under such policies, and find a policy that stabilizes the system for all arrival rates within the throughput region.

We consider the problem of scheduling transmissions over a wireless downlink when channel state information (CSI) is not available to the transmitter. We assume channel states are time varying and evolve according to a Markov Chain. We show that using current QLI does not stabilize the system due to correlations between backlog and channel state. We show that the throughput optimal scheduling policy in this context must use delayed queue length information (QLI). We characterize the extent to which QLI must be delayed as a function of the channel state statistics.

The performance of wireless scheduling algorithms directly depends on the availability and accuracy of channel state information (CSI) at the scheduler. As CSI updates must propagate across the network, they are delayed as they arrive at the controller. In this paper, we analyze the effect that delayed CSI has on the throughput performance of scheduling in wireless networks. By accounting for the delays in CSI as they relate to the network topology, we revisit the comparison between centralized and distributed scheduling, which is analyzed as a trade-off between using delayed CSI and making imperfect scheduling decisions. In particular, we prove that there exist conditions under which distributed scheduling outperforms the optimal centralized scheduling policy. We characterize the point at which distributed scheduling outperforms centralized scheduling for tree networks, illustrating the impact of topology on throughput.

The performance of wireless scheduling algorithms directly depends on the availability and accuracy of network state information at the scheduler. As channel state updates must propagate across the network, they are delayed as they arrive at the controller. The location of the controller directly affects the attainable throughput, as its dictates the delays with which information is obtained to make scheduling decisions. In this paper, we analyze the optimal controller placement over a network in which CSI delays are proportional to distance. We propose a dynamic controller placement framework, in which the controller is relocated using delayed queue length information at each node, and scheduling is done using delayed QLI and CSI. We characterize the throughput region under such policies, and find a policy which stabilizes the system for all arrival rates within the throughput region.

This paper presents a scheme in which a dedicated backup network is designed to provide protection from random link failures. Upon a link failure in the primary network, traffic is rerouted through a preplanned path in the backup network. We introduce a novel approach for dealing with random link failures, in which probabilistic survivability guarantees are provided to limit capacity over provisioning. We show that the optimal backup routing strategy in this respect depends on the reliability of the primary network. Specifically, as primary links become less likely to fail, the optimal backup networks employ more resource sharing among backup paths. We apply results from the field of robust optimization to formulate an ILP for the design and capacity provisioning of these backup networks. We then propose a simulated annealing heuristic to solve this problem for large-scale networks and present simulation results that verify our analysis and approach.

We consider an opportunistic communication system in which a transmitter selects one of multiple channels over which to schedule a transmission, based on partial knowledge of the network state. We characterize a fundamental limit on the rate that channel state information must be conveyed to the transmitter in order to meet a constraint on expected throughput. This problem is modeled as a causal rate distortion optimization of a Markov source. We introduce a novel distortion metric capturing the impact of imperfect channel state information on throughput. We compute a closed-form expression for the causal information rate distortion function for the case of two channels, as well as an algorithmic upper bound on the causal rate distortion function. Finally, we characterize the gap between the causal information rate distortion and the causal entropic rate-distortion functions.

We consider a multi-channel communication system in which a transmitter has access to two channels, but does not know the state of either channel. We model the channel state using an ON/OFF Markovian model, and allow the transmitter to probe one of the channels at predetermined probing intervals to decide over which channel to transmit. For models in which the transmitter must transmit over the probed channel, it has been shown that a myopic policy that probes the channel most likely to be ON is optimal. In this work, we allow the transmitter to select a channel over which to transmit that is not necessarily the one it probed. We show that in the case where the two channels are i.i.d, all probing policies yield equal reward. We extend this problem to dynamically choose when to probe based on the results of previous probes, and characterize the optimal policy, as well as provide a LP in terms of state action frequencies to find the optimal policy.

We consider a multi-channel communication system in which a transmitter has access to a large number of channels, but does not know the state of these channels. We model channel state using an ON/OFF Markovian model, and allow the transmitter to probe one of the channels at predetermined probing intervals to decide over which channel to transmit. For models in which the transmitter must send over the probed channel, it has been shown that a myopic policy that probes the channel most likely to be ON is optimal. In this work, we allow the transmitter to select a channel over which to transmit that is not necessarily the one it probed. We show that the myopic policy is not optimal, and propose a simple alternative probing policy, which achieves a higher per-slot expected throughput. Finally, we consider the case where there is a fixed cost associated with probing and derive optimal probing intervals.

This paper addresses the problem of logical topology design for optical backbone networks subject to stochastic traffic demands. The network design problem is broken into three tasks: traffic routing, capacity allocation, and link placement. While the routing and capacity allocation subproblem can be formulated using convex optimization, the link placement component is prohibitive due to its nonlinearity. To address this issue, we develop a linear formulation for the routing and capacity allocation subproblem by extending tools from robust optimization to Gaussian random variables. We show that this linear formulation performs comparably to the optimal nonlinear formulation. Our formulation can then be used to solve the link-placement subproblem for stochastic traffic.

This paper presents a scheme in which a dedicated backup network is designed to provide protection from random link failures. Upon a link failure in the primary network, traffic is rerouted through a preplanned path in the backup network. We introduce a novel approach for dealing with random link failures, in which probabilistic survivability guarantees are provided to limit capacity over-provisioning. We show that the optimal backup routing strategy in this respect depends on the reliability of the primary network. Specifically, as primary links become less likely to fail, the optimal backup networks employ more resource sharing amongst backup paths. We apply results from the field of robust optimization to formulate an ILP for the design and capacity provisioning of these backup networks. We then propose a simulated annealing heuristic to solve this problem for largescale networks, and present simulation results that verify our analysis and approach.