Valid cycles: A source of infeasibility in open shortest path first routing
Authors:
Abstract
Many telecommunication networks use the open shortest path first (OSPF) protocol for the routing of traffic. In such networks, each router sends the traffic on the shortest paths to the destination, with respect to the link weights assigned. An interesting question is whether or not a set of desired routing patterns can be obtained in an OSPF network by assigning appropriate weights. If not, we wish to find the source of the infeasibility. We study these issues by formulating a mathematical model and investigating its feasibility. A certain structure, called valid cycle, is found to be present in most infeasible instances. This yields new necessary conditions, stronger than those previously known, for the existence of weights yielding a set of given desired shortest path graphs. A valid cycle indicates which parts of the routing patterns are in conflict and can be used for changing the routing patterns to make the problem feasible. A polynomial algorithm for finding valid cycles is presented, the method is illustrated by a numerical example, and computational tests are reported. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008Keywords
This publication has 10 references indexed in Scilit:
- Inverse Combinatorial Optimization: A Survey on Problems, Methods, and ResultsJournal of Combinatorial Optimization, 2004
- Optimization of Internet Protocol network design and routingNetworks, 2003
- Inverse optimization in high-speed networksDiscrete Applied Mathematics, 2003
- Internet Routing and Related Topology IssuesSIAM Journal on Discrete Mathematics, 2003
- Internet traffic engineering by optimizing OSPF weights2002
- On open shortest path first related network optimisation problemsPerformance Evaluation, 2002
- Inverse Polymatroidal Flow ProblemJournal of Combinatorial Optimization, 1999
- Finding a Useful Subset of Constraints for Analysis in an Infeasible Linear ProgramINFORMS Journal on Computing, 1997
- Connectivity and Network Flows1995
- On an instance of the inverse shortest paths problemMathematical Programming, 1992