Robust routing under statistical uncertainty: models and polynomial-time algorithms
2009 (English)In: NGI '09 Next Generation Internet Networks, 2009Conference paper (Refereed)
We study the problem of routing under statistical traffic uncertainty. Models for characterizing the statistical uncertainty which arises when the traffic matrix is estimated from link loads using a maximum likelihood scheme are given, and associated optimization models are formulated for finding routing settings that are insensitive to likely estimation errors. Both statistical and worst-case ellipsoidal traffic models are treated. We demonstrate how the routing optimization can be performed in polynomial time, and compare such algorithms with alternatives based on combined constraint and column generation. The proposed techniques are evaluated in several numerical examples.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:kth:diva-79734DOI: 10.1109/NGI.2009.5175781ScopusID: 2-s2.0-70449370968OAI: oai:DiVA.org:kth-79734DiVA: diva2:499924
5th Euro-NGI Conference on Next Generation Internet Networks, NGI 2009. Aveiro, Portugal. 1-3 July 2009
QC 201204272012-02-132012-02-092012-04-27Bibliographically approved