Learning Minimum Delay Paths in Service Overlay Networks

We propose a novel approach using active probing and learning techniques to track minimum delay paths for real-time applications in service overlay networks. Stochastic automata are used to probe paths in a de-centralized, scalable manner. We propose four varia-tions on active probing and learning strategies. It can be proved that our approach converges to the user equi-librium for minimum delay routing. The performance of these strategies is studied via fluid simulations of a model of AT&Ts backbone network. The simulation re-sults show that the proposed strategies converge to the minimum delay paths rapidly. We also observe, via sim-ulation, that our approach scales well in the size of the service overlay network. 1