Measurement-based Optimal Routing Strategies on Overlay Architectures

Abstract

In this thesis, we seek optimal, yet practical, multipath routing algorithms that can minimize the network congestion by exploiting the locally collected measurement data.

We first develop a distributed measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple unicast sources. Multiple paths are established using overlay nodes. The algorithm is derived from simultaneous perturbation stochastic approximation (SPSA) and does not assume that the gradient of an analytical cost function is known. Instead, it relies on (potentially) noisy estimates from local measurements. We formulate the traffic mapping problem in an optimization

framework and show through an analytical model that the algorithm converges to the optimal solution almost surely under a decreasing step size policy. Motivated by practical concerns, we next consider the constant step size case, for which we establish weak convergence.

In the second part of this thesis, we consider the problem of load balancing of multicast traffic sessions and generalize our unicast routing algorithm to route both types of traffic simultaneously. We consider three network models that reflect different sets of assumptions regarding multicast capabilities of the network. In addition, we investigate the benefits acquired from implementing additional multicast

capabilities by studying the relative performance of the generalized algorithm under the three network models.

Throughout this thesis, we rely on an overlay architecture to establish multiple paths between a source and its destination(s) in an IP network. As the performance of the routing algorithms depends on the quality of paths provided by the overlay nodes, it is of interest to carefully locate a limited number of overlay nodes in the network. The final part of this thesis makes use of the discrete stochastic optimization methods and presents an optimal solution based on Stochastic Comparison (SC) algorithm to locate overlay nodes given a set of sources and their corresponding destination(s). Motivated by the impracticality of stochastic comparison algorithm in an online setting due to its computational complexity, we provide a computationally efficient heuristic solution. We show through a detailed simulation study that the performance obtained by the heuristic solution is comparable to that of optimal algorithm.