Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Reliability Estimation for Networks with Minimal Flow Demand and Random Link Capacities

Abstract : We consider a network whose links have random capacities and in which a certain target amount of flow must be carried from some source nodes to some destination nodes. Each destination node has a fixed demand that must be satisfied and each source node has a given supply. We want to estimate the unreliability of the network, defined as the probability that the network cannot carry the required amount of flow to meet the demand at all destination nodes. When this unreliability is very small, which is our main interest in this paper, standard Monte Carlo estimators become useless because failure to meet the demand is a rare event. We propose and compare two different methods to handle this situation, one based on a conditional Monte Carlo approach and the other based on generalized splitting. We find that the first is more effective when the network is highly reliable and not too large, whereas for a larger network and/or moderate reliability, the second is more effective.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01745187
Contributor : Bruno Tuffin <>
Submitted on : Wednesday, March 28, 2018 - 8:48:21 AM
Last modification on : Thursday, January 7, 2021 - 4:34:53 PM
Long-term archiving on: : Thursday, September 13, 2018 - 9:23:35 AM

File

pmc-gs-maxflow.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01745187, version 1

Citation

Zdravko Botev, Pierre l'Ecuyer, Bruno Tuffin. Reliability Estimation for Networks with Minimal Flow Demand and Random Link Capacities. 2018. ⟨hal-01745187⟩

Share

Metrics

Record views

388

Files downloads

233