Non-isotonic routing metrics solvable to optimality via shortest path

It is a well-established fact that routing metrics cannot be optimized via shortest path algorithms unless they are both monotone and isotonic. In particular, monotonicity guarantees the convergence of the shortest path procedure, while isotonicity guarantees convergence to the optimal path. This paper presents a class of routing metrics that are not isotonic, yet can be solved to exact optimality via shortest path (or iterative shortest path) procedures. In particular, we consider routing metrics of the form “distance+1/width” and “distance/width”, respectively, where the former is the default form of the composite metric of the interior gateway routing protocol (IGRP). To the best of our knowledge, for the first time we provide shortest-path-based algorithms that are guaranteed to minimize these metrics in spite of their non-isotonicity. This result implies that, contrary to common belief, the composite metric of the IGRP is in fact optimizable.