Approximation algorithm for estimating failure probability of multipath transmission

Sheng Zhong and Yuan Zhang

Mathematics and Computers in Simulation (MATCOM), 2011, vol. 81, issue 9, 1729-1732

Abstract: In a computer network where nodes can fail, multipath transmission can be used to increase the probability of successful transmission. However, even multipath transmission has a probability of failure, which depends on the selected paths. Hence, estimating this probability of failure is of great importance for designing good multipath routing algorithms. In this paper, we show that it is NP-hard to compute the failure probability of multipath transmission. Therefore, we design a polynomial-time approximation algorithm for estimating this failure probability and give analysis of its error bounds. We also compare the results of our approximation algorithm with the results of Matlab simulations.

Keywords: Computer network; Multipath transmission; Approximation; Polynomial complexity; Error bound (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475411000346
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:81:y:2011:i:9:p:1729-1732

DOI: 10.1016/j.matcom.2011.01.006

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().