A framework for simulation-based network control via hindsight optimization

We describe a novel approach for designing network control algorithms that incorporate traffic models. Traffic models can be viewed as stochastic predictions about the future network state, and can be used to generate traces of potential future network behavior. Our approach is to use such traces to heuristically evaluate candidate control actions using a technique called hindsight optimization. In hindsight optimization, the finite-horizon "utility" achievable from a given system state is estimated by averaging estimates obtained from a number of traces starting at the state. For each trace, the utility value of the state is estimated by determining the optimal "hindsight control"-this is the control that would be applied by an optimal controller that somehow "knew" the whole trace beforehand-and then measuring the utility obtained under that control. Averaging over many samples then gives a simulation-based "hindsight-optimal" utility for the starting state that upper bounds the true utility value of the state. This technique for estimating state utility can then be used to select the control-simply select the control that gives the highest utility. Our hindsight-optimization approach to designing simulation-based control algorithms can be applied to a wide variety of network decision problems. We present empirical results showing effectiveness for two example control problems-multiclass scheduling and congestion control.