Empirical stability limits for a size-based scheduler applied to Network Utility Maximization

Network Utility Maximization (NUM) is an optimization problem that models rate allocation in the Internet. NUM is considered to produce fair bandwidth allocations, an advantage for the implementation of TCP queue management protocols. Prioritization of data packets can benefit from knowing transfer sizes a-priori. A state-of-the-art NUM formulation considers a size-based approach where transmission flows are scaled by some function of a transfer's residual work (inspired by schedulers like Shortest Remaining Processing Time, SRPT). This new NUM-SRPT hybrid scheduler was proven to be stable for a defined region on any arbitrary topology. We found that for all tested topologies, stability limits are well beyond of what was proven theoretically, showing that performance does benefit from a SRPT-based prioritization at much higher loads. A method to detect empirical stability based on the augmented Dickey-Fuller test was used in order to assess the stability limits.