Stochastic network models with all components being observable and controllable have been the focus of classic network optimization theory for decades. However, in modern network systems, it is common that the network controller can only observe and operate on some nodes (i.e., overlay nodes), and the other nodes (i.e., underlay nodes) are neither observable nor controllable. Moreover, the dynamics can be non-stochastic or even adversarial. In this paper, we focus on the network utility maximization (NUM) problem for networks with overlay-underlay structures. The network dynamics, such as packet admissions, external arrivals and control actions of underlay nodes, can be stochastic, non-stochastic or even adversarial. We propose the Tracking Drift-plus-Penalty (TDP*) algorithm that only operates on the overlay nodes and does not require direct observations of the underlay nodes, and analyze the tradeoffs between the average utility and queue backlog. We show that as long as the peak queue backlog of the network is sublinear in time horizon, TDP* can solve the NUM problem, i.e., reaching the maximum utility while preserving stability.

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.