Please use this identifier to cite or link to this item:
|Title:||OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty||Authors:||Altın, Ayşeguel
Pınar, Mustafa C.
|Issue Date:||2010||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
|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
checked on Sep 23, 2022
WEB OF SCIENCETM
checked on Sep 24, 2022
checked on Dec 26, 2022
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.