Robust regression for minimum-delay load-balancing

By providing origin-destination pairs with several possible paths, Dynamic Load-Balancing has been shown to obtain excellent results in terms of robustness and effective resource usage. In these dynamic schemes, paths are defined a priori, and the portion of traffic routed through each path is (typically) adjusted so that the sum over all links of a certain link-cost function is minimized. Queueing delay is usually used as this cost function due to its versatility and simplicity. However, all loadbalancing schemes require an analytical expression of the delay, for which oversimplistic models are used (such as the classic M/M/1 model). In this paper we propose a framework that instead learns this queueing delay function from measurements, while restricting the assumptions to the minimum. For this, we use a novel robust regression method that, given a set of link load and delay measurements, returns a very simple regression delay function. Some adjustments to this regression function allow us to use it as the link cost of a greedy load-balancing algorithm that converges to the actual minimum-delay configuration. We also compare our framework with previous load-balancing proposals, showing for instance that using the M/M/1 model results in a total delay that may easily exceed the minimum by 10%, and can go as high as more than 100%.