We consider the optimal control problem for networks subjected to time-varying channels, reconfiguration delays, and interference constraints. We show that the simultaneous presence of time-varying channels and reconfiguration delays significantly reduces the system stability region and changes the structure of optimal policies. We first consider memoryless channel processes and characterize the stability region in closed form. We prove that a frame-based Max-Weight scheduling algorithm that sets frame durations dynamically, as a function of the current queue lengths and average channel gains, is throughput-optimal. Next, we consider arbitrary Markov-modulated channel processes and show that memory in the channel processes can be exploited to improve the stability region. We develop a novel approach to characterizing the stability region of such systems using state-action frequencies, which are stationary solutions to a Markov Decision Process (MDP) formulation. Moreover, we develop a dynamic control policy using the state-action frequencies and variable frames whose lengths are functions of queue sizes and show that it is throughput-optimal. The frame-based dynamic control (FBDC) policy is applicable to a broad class of network control systems, with or without reconfiguration delays, and provides a new framework for developing throughput-optimal network control policies using state-action frequencies. Finally, we propose Myopic policies that are easy to implement and have better delay properties as compared to the FBDC policy.

We consider the optimal control problem for networks subjected to time-varying channels, reconfiguration delays, and interference constraints. We model the network by a graph consisting of nodes, links, and a set of link interference constraints, where based on the current network state, the controller decides either to stay with the current link-service configuration or switch to another service configuration at the cost of idling during schedule reconfiguration. Reconfiguration delay occurs in many telecommunications applications and is a new modeling component of this problem that has not been previously addressed. We show that the simultaneous presence of time-varying channels and reconfiguration delays significantly reduces the system stability region and changes the structure of optimal policies. We first consider memoryless channel processes and characterize the stability region in closed form. We prove that a frame-based Max-Weight scheduling algorithm that sets frame durations dynamically, as a function of the current queue sizes and average channel gains is throughput-optimal. Next, we consider arbitrary Markov modulated channel processes and show that memory in the channel processes can be exploited to improve the stability region. We develop a novel approach to characterizing the stability region of such systems using state-action frequencies which are stationary solutions to a Markov Decision Process (MDP) formulation. Finally, we develop a frame-based dynamic control policy, based on the state-action frequencies, and show that it is throughput-optimal asymptotically in the frame length. The FBDC policy is applicable to a broad class of network control systems, with or without reconfiguration delays, and provides a new framework for developing throughput-optimal network control policies using state-action frequencies.

We consider a dynamic server allocation problem over parallel queues with randomly varying connectivity and server switchover delay between the queues. At each time slot, the server decides either to stay with the current queue or switch to another queue based on the current connectivity and the queue length information. Switchover delay occurs in many telecommunications applications and is a new modeling component of this problem that has not been previously addressed. We show that the simultaneous presence of randomly varying connectivity and switchover delay changes the system stability region and the structure of optimal policies. In the first part of this paper, we consider a system of two parallel queues, and develop a novel approach to explicitly characterize the stability region of the system using state-action frequencies which are stationary solutions to a Markov decision process formulation. We then develop a frame-based dynamic control (FBDC) policy, based on the state-action frequencies, and show that it is throughput optimal asymptotically in the frame length. The FBDC policy is applicable to a broad class of network control systems and provides a new framework for developing throughput-optimal network control policies using state-action frequencies. Furthermore, we develop simple myopic policies that provably achieve more than 90% of the stability region. In the second part of this paper, we extend our results to systems with an arbitrary finite number of queues. In particular, we show that the stability region characterization in terms of state-action frequencies and the throughput optimality of the FBDC policy follows for the general case. Furthermore, we characterize an outer bound on the stability region and an upper bound on sum throughput and show that a simple myopic policy can achieve this sum-throughput upper bound in the corresponding saturated system. Finally, simulation results show that the myopic policies may achieve the full stability region and are more delay efficient than the FBDC policy in most cases.

We consider a dynamic server control problem for two parallel queues with randomly varying connectivity and server switchover delay between the queues. At each time slot the server decides either to stay with the current queue or switch to the other queue based on the current connectivity and the queue length information. The introduction of switchover time is a new modeling component of this problem, which makes the problem much more challenging. We develop a novel approach to characterize the stability region of the system by using state-action frequencies, which are stationary solutions to a Markov Decision Process (MDP) formulation of the corresponding saturated system. We characterize the stability region explicitly in terms of the connectivity parameters and develop a frame-based dynamic control (FBDC) policy that is shown to be throughput-optimal. In fact, the FBDC policy provides a new framework for developing throughput-optimal network control policies using state-action frequencies. Furthermore, we develop simple Myopic policies that achieve more than 96% of the stability region. Finally, simulation results show that the Myopic policies may achieve the full stability region and are more delay efficient than the FBDC policy in most cases.

This paper considers the scheduling problem for networks with interference constraints and switchover delays, where it takes a nonzero time to reconfigure each service schedule. Switchover delay occurs in many telecommunication applications such as satellite, optical or delay tolerant networks (DTNs). Under zero switchover delay it is well known that the Max-Weight algorithm is throughput-optimal without requiring knowledge of the arrival rates. However, we show that this property of Max-Weight no longer holds when there is a nonzero switchover delay. We propose a class of variable frame based Max-Weight (VFMW) algorithms which employ the Max-Weight schedule corresponding to the beginning of the frame during an interval of duration dependent on the queue sizes. The VFMW algorithms dynamically adapt the frame sizes to the stochastic arrivals and provide throughput-optimality without requiring knowledge of the arrival rates. Numerical results regarding the application of the VFMW algorithms to DTN and optical networks demonstrate a good delay performance.

The physical layer of future wireless networks will be based on novel radio technologies such as UWB and MIMO. One of the important capabilities of such technologies is the ability to capture a few packets simultaneously. This capability has the potential to improve the performance of the MAC layer. However, we show that in networks with spatially distributed nodes, reusing backoff mechanisms originally designed for narrow-band systems (e.g., CSMA/CA) is inefficient. It is well known that when networks with spatially distributed nodes operate with such MAC protocols, the channel may be captured by nodes that are near the destination, leading to unfairness. We show that when the physical layer enables multipacket reception, the negative implications of reusing the legacy protocols include not only such unfairness, but also a significant throughput reduction. We present alternative backoff mechanisms and evaluate their performance via Markovian analysis, approximations, and simulation. We show that our alternative backoff mechanisms can improve both overall throughput and fairness.

The physical layer of future wireless networks will be based on novel radio technologies such as UWB and MIMO. One of the important capabilities of such technologies is the ability to capture a few packets simultaneously. This capability has the potential to improve the performance of the MAC layer. However, we show that in networks with spatially distributed nodes, reusing backoff mechanisms originally designed for narrow-band systems (e.g. CSMA/CA) is inefficient. It is well known that when networks with spatially distributed nodes operate with such MAC protocols, the channel may be captured by nodes that are near the destination, leading to unfairness. We show that when the physical layer enables multipacket reception, the negative implications of reusing the legacy protocols include not only such unfairness but also a significant throughput reduction. We present alternative backoff mechanisms and evaluate their performance via Markovian analysis and simulation. We show that our alternative backoff mechanisms can improve both overall throughput and fairness.