Tracking MaxWeight: Optimal Control for Partially Observable and Controllable Networks

Modern networks are complex and may include components that cannot be fully controlled or observed. Such network models can be characterized by overlay-underlay structures, where the network controller can only observe and operate on overlay nodes, and the underlay nodes are neither observable nor controllable. Classic network control algorithms may fail to work properly if they are only applied to the overlay nodes. To tackle this issue, we propose the Tracking MaxWeight (TMW*) algorithm that does not require direct observations of underlay nodes and only operates on overlay nodes. TMW* maintains virtual queues that track the dynamics of the underlay nodes and makes control decisions based on those virtual queues. We show that TMW* is throughput optimal as long as the network is stabilizable. We further extend our analysis to the setting that the estimates of the underlay state is erroneous and show that as long as the errors scale sub-linearly in time, TMW* preserves throughput optimality.