We propose a novel approach using active probingand learning techniques to track minimum delay pathsfor real-time applications in service overlay networks.Stochastic automata are used to probe paths in a decentralized,scalable manner. We propose four variationson active probing and learning strategies. It canbe proved that our approach converges to the user equilibriumfor minimum delay routing. The performanceof these strategies is studied via fluid simulations of amodel of AT&Ts backbone network. The simulation resultsshow that the proposed strategies converge to theminimum delay paths rapidly. We also observe, via simulation,that our approach scales well in the size of theservice overlay network.