On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Forests

We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a forest topology. Each packet is destined to one of the roots (sinks) of the forest. We consider a time-slotted system and a primary (or one-hop) interference model. We characterize the existence of causal sample-path optimal scheduling policies for this network topology under this interference model. A causal sample-path optimal scheduling policy is one for which at each time-slot, and for any sample-path traffic arrival pattern, the sum of the queue lengths of all the nodes in the network is minimum among all policies. We show that such policies exist in restricted forest structures, and that for any other forest structure, there exists a traffic arrival pattern for which no causal sample-path optimal policy can exist. Surprisingly, we show that many forest structures for which such policies exist can be scheduled by converting the structure into an equivalent linear network and scheduling the equivalent linear network according to the one-hop interference model. The nonexistence of such policies in many forest structures underscores the inherent limitation of using sample-path optimality as a performance metric and necessitates the need to study other (relatively) weaker metrics of delay performance.