A laplace transform-based method to stochastic path finding

Abstract

Finding the most likely path satisfying a requested additive Quality-of-Service (QoS) value, such as delay, when link metrics are defined as random variables by known probability distributions is NP-Hard [1]. We transform the probability distributions into the Laplace domain, find the Laplace Transform of their convolutions and numerically inverse to find the distribution function in the time domain. Picard's iterative method of successive approximations is used to find the solution. To the best of our knowledge, ours is the first to propose a transform-based approach for the QoS routing problem of finding the most likely path. Simulations show that our stochastic approach (1) Selects correct paths more frequently, (2) Incurs less overhead with respect to the dissemination and processing of state information, and (3) Reduces the churn by selecting more stable paths. ©2009 IEEE.