Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.11851/7249
Title: | Ospf Routing With Optimal Oblivious Performance Ratio Under Polyhedral Demand Uncertainty | Authors: | Altın, Ayşeguel Belotti, Pietro Pınar, Mustafa C. |
Keywords: | OSPF Oblivious routing Traffic engineering ECMP Branch-and-price Traffic uncertainty |
Publisher: | Springer | Abstract: | We study the best OSPF style routing problem in telecommunication networks, where weight management is employed to get a routing configuration with the minimum oblivious ratio. We consider polyhedral demand uncertainty: the set of traffic matrices is a polyhedron defined by a set of linear constraints, and a routing is sought with a fair performance for any feasible traffic matrix in the polyhedron. The problem accurately reflects real world networks, where demands can only be estimated, and models one of the main traffic forwarding technologies, Open Shortest Path First (OSPF) routing with equal load sharing. This is an NP-hard problem as it generalizes the problem with a fixed demand matrix, which is also NP-hard. We prove that the optimal oblivious routing under polyhedral traffic uncertainty on a non-OSPF network can be obtained in polynomial time through Linear Programming. Then we consider the OSPF routing with equal load sharing under polyhedral traffic uncertainty, and present a compact mixed-integer linear programming formulation with flow variables. We propose an alternative formulation and a branch-and-price algorithm. Finally, we report and discuss test results for several network instances. | URI: | https://doi.org/10.1007/s11081-009-9098-y https://hdl.handle.net/20.500.11851/7249 |
ISSN: | 1389-4420 1573-2924 |
Appears in Collections: | Endüstri Mühendisliği Bölümü / Department of Industrial Engineering Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection |
Show full item record
CORE Recommender
SCOPUSTM
Citations
13
checked on Dec 21, 2024
WEB OF SCIENCETM
Citations
14
checked on Dec 21, 2024
Page view(s)
54
checked on Dec 16, 2024
Google ScholarTM
Check
Altmetric
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.