Design of OSPF networks using subpath consistent routing patterns

We address the problem of designing IP networks where the traffic is routed using the OSPF protocol. Routers in OSPF networks use link weights set by an administrator for determining how to route the traffic. The routers use all shortest paths when traffic is routed to a destination, and the traffic is evenly balanced by the routers when several paths are equally short. We present a new model for the OSPF network design problem. The model is based on routing patterns and does not explicitly include OSPF weights. The OSPF protocol is modeled by ensuring that all pairs of routing patterns are subpath consistent, which is a necessary condition for the existence of weights. A Lagrangean heuristic is proposed as solution method, and feasible solutions to the problem are generated using a tabu search method. Computational results are reported for random instances and for real-life instances.The original publication is available at www.springerlink.com:Peter Brostrom and Kaj Holmberg, Design of OSPF networks using subpath consistent routing patterns, 2009, TELECOMMUNICATION SYSTEMS, (41), 4, 293-309.http://dx.doi.org/10.1007/s11235-009-9162-0Copyright: Springer Science Business Mediahttp://www.springerlink.com