LIDS Thesis: Network Optimization in Adversarial Environments

Thesis Committee: Prof. Eytan Modiano (Chair), Prof. Devavrat Shah, Prof. Suvrit Sra

Stochastic models have been dominant in network optimization theory for over two decades, due to their analytical tractability. However, an increasing number of real-world networked systems exhibit complex behaviors that cannot be captured by the simple stochastic models, such as networks under malicious attacks and networks with uncontrollable nodes. In this thesis, we study efficient network control policies that can optimize network performance in different types of complex environments.

First, we investigate network optimization under adversarial dynamics, where the evolution of network conditions follows some non-stationary and possibly adversarial process. Such an adversarial network dynamics model can be used to capture many real-world scenarios, such as networks under Distributed Denial-of-Service (DDoS) attacks or ad-hoc networks with unpredictable mobility. We focus on two network control problems: (1) achieving network stability, and (2) maximizing network utility subject to stability constraints. New adversarial network models are developed to characterize the adversary's behavior, and the notion of regret is used to measure network performance in adversarial environments. We provide lower bounds on the regret performance that could be achieved by any causal control policies and analyze the performance of several network control policies (e.g., MaxWeight and Drift-plus-Penalty). It is proved that these policies are throughput-optimal and achieve good utility-delay tradeoffs even under adversarial dynamics.

Second, we study network optimization in a partially-controllable environment where a subset of nodes are uncontrollable and adopt a stationary but unknown control policy. Such a partially-controllable model is of increasing importance in real-world networked systems such as overlay-underlay networks and uncooperative wireless networks. We consider the problem of stabilizing a partially-controllable network. It is shown that many well-known network control algorithms (e.g., MaxWeight) may fail to stabilize the network when some nodes adopt non-stabilizing policies. We first study the scenario where uncontrollable nodes use a queue-agnostic policy and propose a low-complexity throughput-optimal algorithm, called Tracking-MaxWeight (TMW), which enhances the original MaxWeight algorithm with an explicit learning of the policy used by uncontrollable nodes. Next, we investigate the scenario where uncontrollable nodes use a queue-dependent policy and the problem is formulated as an MDP with unknown queueing dynamics. We propose a new reinforcement learning algorithm, called Truncated Upper Confidence Reinforcement Learning (TUCRL), and prove that TUCRL achieves tunable three-way tradeoffs between throughput, delay and convergence rate under mild conditions.

Finally, we focus on network optimization with adversarial uncontrollable nodes where the sequence of actions taken by uncontrollable nodes may be non-stationary and adversarial. We first investigate the network stability problem and develop a lower bound on the total queue length that can be achieved by any causal policy. We prove that the Tracking-MaxWeight (TMW) algorithm can achieve network stability under any given sequence of actions of adversarial nodes whenever possible. Next, we study the network utility maximization problem and provide a lower bound on the utility-delay tradeoff. We develop the Tracking Drift-plus-Penalty (TDP) algorithm that achieves tunable utility-delay tradeoffs.