Measurement-based optimal routing on overlay architectures for unicast sessions

We propose a measurement-based routing algorithm to load-balance intradomain traffic along multiple paths for multi-ple unicast sources. Multiple paths are established using overlay nodes. The distributed algorithm is derived from simul-
taneous perturbation stochastic approximation (SPSA) and does not assume that the gradient of an analytical cost
function is known. Instead, we rely on (potentially) noisy estimates from local measurements. Using the analytical model
presented in the paper, we first show the almost sure convergence of the algorithm to the optimal solution under a decreas-
ing step size policy (as with a standard SPSA model). Motivated by practical concerns, we next consider the constant step
size case, for which we establish weak convergence. We provide simulation results to demonstrate the advantages of our
proposed algorithm under various network scenarios, and also present a comparative study with MATE (an existing opti-
mal routing algorithm)