  We consider the problem of throughput-optimal packet dissemination, in the
presence of an arbitrary mix of unicast, broadcast, multicast and anycast
traffic, in a general wireless network. We propose an online dynamic policy,
called Universal Max-Weight (UMW), which solves the above problem efficiently.
To the best of our knowledge, UMW is the first throughput-optimal algorithm of
such versatility in the context of generalized network flow problems.
Conceptually, the UMW policy is derived by relaxing the precedence constraints
associated with multi-hop routing, and then solving a min-cost routing and
max-weight scheduling problem on a virtual network of queues. When specialized
to the unicast setting, the UMW policy yields a throughput-optimal cycle-free
routing and link scheduling policy. This is in contrast to the well-known
throughput-optimal Back- Pressure (BP) policy which allows for packet cycling,
resulting in excessive latency. Extensive simulation results show that the
proposed UMW policy incurs a substantially smaller delay as compared to the BP
policy. The proof of throughput-optimality of the UMW policy combines ideas
from stochastic Lyapunov theory with a sample path argument from adversarial
queueing theory and may be of independent theoretical interest.
