Optimization Online


Survivable IP network design with OSPF routing

Luciana S. Buriol (buriol***at***dis.uniroma1.it)
Mauricio G. C. Resende (mgcr***at***research.att.com)
Mikkel Thorup (mthorup***at***research.att.com)

Abstract: Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. If a router has multiple outgoing links on shortest paths to a given destination, it splits traffic evenly over these links. It is also the role of the routing protocol to specify how the network should react to changes in the network topology, such as arc or router failures. In such situations, IP traffic is re-routed through the shortest paths not traversing the affected part of the network. This paper addresses the issue of assigning OSPF weights and multiplicities to each arc, aiming to design efficient OSPF-routed networks with minimum total weighted multiplicity (multiplicity multiplied by the arc length) needed to route the required demand and handle any single arc or router failure. The multiplicities are limited to a discrete set of values and we assume that the topology is given. We propose an evolutionary algorithm for this problem, and present results applying it to several real-world problem instances.

Keywords: Internet, IP network design, survivability, OSPF routing, evolutionary algorithm

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

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Network Optimization

Citation: AT&T Labs Research Technical Report TD-64KUAW, September 6, 2004.

Download: [PDF]

Entry Submitted: 09/06/2004
Entry Accepted: 09/07/2004
Entry Last Modified: 09/06/2004

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