UC San Diego

A scheduling policy plays a critical role in achieving good performance for most networked systems. While the optimal scheduling problems have been studied to a great extent in the literature, the effect of reconfiguration overhead receives far less attention. With the advancement of high speed and highly flexible networking technologies, the reconfiguration overhead becomes more significant in the design of an efficient scheduling policy.

We first consider the scheduling problem in a generalized switch model subject to reconfiguration delay. We propose the Adaptive MaxWeight policy, and prove that the Adaptive MaxWeight policy is throughput optimal. We also extend the idea of the Adaptive MaxWeight and propose a general method to transform scheduling policies that loses the throughput optimality under nonzero reconfiguration delay into adaptive policies that recover the throughput optimality guarantee.

We then further analyze the average queue length of the Adaptive MaxWeight policy in the heavy traffic regime. In particular, we consider a sequence of switch systems with arrival rates approaching to the boundary of the capacity region, where the limiting arrival rate has saturated traffic for all input ports and all output ports. In the heavy traffic regime, we derive an upper bound for the expected sum of queue length, which achieves the optimal scaling with respect to the traffic load as well as to the reconfiguration delay.

Finally, we consider the scheduling problem in a distributed computing network subject to reconfiguration delay and reconfiguration cost. We show that while the capacity region remains unchanged regardless of the reconfiguration delay/cost values, a reconfiguration-agnostic policy may fail to guarantee throughput-optimality and minimum cost under nonzero reconfiguration delay/cost. We then present the Adaptive Dynamic Cloud Network Control policy that allows network nodes to make local flow scheduling and resource allocation decisions while implicitly controlling the frequency of reconfiguration in order to support any input rate in the capacity region and achieve arbitrarily close to minimum cost for any finite reconfiguration delay/cost values.