Routing Optimization in IP Networks Utilizing Additive and Concave Link Metrics

Routing optimization provides network operators with a powerful method for traffic engineering. Its general objective is to distribute traffic flows evenly across available network resources in order to avoid network congestion and quality of service degradation. In this paper we consider routing optimization based on conventional routing protocols where packets are forwarded hop-by-hop in a destination-based manner. Unlike other work in this area, we consider routing protocols, which are able to take into account concave routing metrics in addition to additive ones. The concave link metric introduces an additional degree of freedom for routing optimization, thus, increasing its optimization potential. We present and evaluate a mixed-integer programming model, which works on these metrics. This model unifies the optimization for single-metric and dual-metric routing concepts and also includes the consideration of multipath routing. Furthermore, we propose a heuristic algorithm usable for larger network instances. Numerical results indicate that employment of both the dual-metric concept and multipath routing can achieve considerably better utilization results than default-configured single-metric routing. A significant finding is that metric-based routing optimization with two link metrics often comes close to the results obtainable by optimization of arbitrarily configurable routing.