  Stochastic models have been dominant in network optimization theory for over
two decades, due to their analytical tractability. However, these models fail
to capture non-stationary or even adversarial network dynamics which are of
increasing importance for modeling the behavior of networks under malicious
attacks or characterizing short-term transient behavior. In this paper, we
consider the network utility maximization problem in adversarial network
settings. In particular, we focus on the tradeoffs between total queue length
and utility regret which measures the difference in network utility between a
causal policy and an "oracle" that knows the future within a finite time
horizon. Two adversarial network models are developed to characterize the
adversary's behavior. We provide lower bounds on the tradeoff between utility
regret and queue length under these adversarial models, and analyze the
performance of two control policies (i.e., the Drift-plus-Penalty algorithm and
the Tracking Algorithm).
