Measurement-based optimal routing strategies on overlay architectures

As a natural outcome of dramatic growth of the Internet and proliferation of demanding services with higher data rates, traffic engineering has proved to be vital in avoiding congestion and maximizing the network resource utilization. A key component of traffic engineering is traffic mapping, i.e., splitting the traffic flows along multiple paths. 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 (as with the standard SPSA model). 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. As in the unicast case, we prove the almost sure convergence of the algorithm to a corresponding optimal solution under each network model considered with decreasing step sizes and establish the weak convergence with a fixed step size. 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 the optimal algorithm.