A laplace transform-based method to stochastic path finding

Suleyman Uludag, Ziyneti E. Uludag, Klara Nahrstedt, King Shan Lui, Fred Baker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2009 IEEE International Conference on Communications, ICC 2009
DOIs
StatePublished - Nov 19 2009
Event2009 IEEE International Conference on Communications, ICC 2009 - Dresden, Germany
Duration: Jun 14 2009Jun 18 2009

Publication series

NameIEEE International Conference on Communications
ISSN (Print)0536-1486

Other

Other2009 IEEE International Conference on Communications, ICC 2009
CountryGermany
CityDresden
Period6/14/096/18/09

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A laplace transform-based method to stochastic path finding'. Together they form a unique fingerprint.

  • Cite this

    Uludag, S., Uludag, Z. E., Nahrstedt, K., Lui, K. S., & Baker, F. (2009). A laplace transform-based method to stochastic path finding. In Proceedings - 2009 IEEE International Conference on Communications, ICC 2009 [5198619] (IEEE International Conference on Communications). https://doi.org/10.1109/ICC.2009.5198619