Optimization Online


OSPF Routing with Optimal Oblivious Performance Ratio Under Polyhedral Demand Uncertainty

Aysegul Altin (aaltin***at***etu.edu.tr )
Pietro Belotti (belotti***at***lehigh.edu)
Mustafa Pinar (mustafap***at***bilkent.edu.tr)

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 the performance of each routing is assessed on its worst case congestion ratio for any feasible traffic matrix in the polyhedron. The problem is an accurate reflection of real world IP networks, not only because it considers the likelihood of having inaccurate demand estimates but also because it models one of the main currently viable traffic forwarding technologies, i.e., Open Shortest Path First (OSPF) routing with equal load sharing. This is an NP-hard problem even for a fixed demand matrix, so the problem considered in the paper is also NP-hard. First, we prove that the optimal oblivious routing under polyhedral tra±c uncertainty on a non-OSPF network can be obtained in polynomial time using a duality-based reformulation. 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 tree formulation and a branch-and-price algorithm. Finally, we report and discuss test results for several network instances.

Keywords: OSPF, oblivious routing, traffic engineering, ECMP, branch-and-price, traffic uncertainty, duality-based reformulation.

Category 1: Network Optimization

Category 2: Robust Optimization

Category 3: Applications -- OR and Management Sciences (Telecommunications )


Download: [PDF]

Entry Submitted: 01/12/2009
Entry Accepted: 01/12/2009
Entry Last Modified: 01/12/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society