On the complexity of equal shortest path routing

In telecommunication networks, packets are carried from a source to a destination on a path determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from to follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore, the routing protocol must determine how the traffic from to is distributed among the shortest paths. In the protocol called Open Shortest Path First‐Equal Cost Multiple Path (ospf‐ecmp) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities. In this work, we show that the problem of maximizing even a single commodity flow for the ospf‐ecmp protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial‐time approximations and an exponential‐time exact algorithm. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 344–352 2015