Abstract | ||
---|---|---|
This paper discusses the sensitivity of network flows to uncertain link state information for various routing protocols. We show that the choice of probability distribution for the link metrics for a given network can have markedly different effects on the probabilities of path selection. Exact results are obtained for these probabilities but their computation is NP-hard. We provide simulation results for three networks to illustrate the sensitivity of shortest paths to different link metric distributions. We provide results for mean path costs and the k-shortest path algorithm as a comparison. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1109/ICON.2004.1409216 | ICON 2004). Proceedings. 12th IEEE International Conference |
Keywords | Field | DocType |
computational complexity,optimisation,probability,routing protocols,stochastic processes,telecommunication links,NP-hard,k-shortest path algorithm,link state information,routing protocol,stochastic network | Flow network,Average path length,Link-state routing protocol,Mathematical optimization,Computer science,Constrained Shortest Path First,Probability distribution,Yen's algorithm,Distributed computing,K shortest path routing,Routing protocol | Conference |
Volume | ISSN | ISBN |
2 | 1531-2216 | 0-7803-8783-X |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bill Lloyd-Smith | 1 | 0 | 0.34 |
Alexander A. Kist | 2 | 60 | 18.38 |
Richard J. Harris | 3 | 71 | 11.37 |
Nirisha Shrestha | 4 | 0 | 0.34 |