TY - GEN
T1 - A laplace transform-based method to stochastic path finding
AU - Uludag, Suleyman
AU - Uludag, Ziyneti E.
AU - Nahrstedt, Klara
AU - Lui, King Shan
AU - Baker, Fred
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70449489420&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449489420&partnerID=8YFLogxK
U2 - 10.1109/ICC.2009.5198619
DO - 10.1109/ICC.2009.5198619
M3 - Conference contribution
AN - SCOPUS:70449489420
SN - 9781424434350
T3 - IEEE International Conference on Communications
BT - Proceedings - 2009 IEEE International Conference on Communications, ICC 2009
T2 - 2009 IEEE International Conference on Communications, ICC 2009
Y2 - 14 June 2009 through 18 June 2009
ER -