Evaluating Different IP Routing Schemes with Metric Optimization

Christoph Reichert

Intra-domain routing in IP networks is based on link metrics which determine shortest paths in a network. Traffic Engineering can be done by computing link metrics so that the traffic engineering goals are met. The most frequent goal is to minimize the maximum link utilization. The presentation is about a link metric optimizer based on Genetic Algorithms and fast local heuristics, which is used to evaluate various routing schemes under different conditions.

The first case investigated is Equal-cost Multi-path routing with and without link failures.

The second case shows how metric optimization can be exploited to alleviate problems with hash-based ECMP forwarding when IP routers employ the same hash function.

The third case evaluates a new routing scheme enabling multiple routing classes. Basically, each routing class is represented by its own routing table, but a much more memory efficient implementation technique is also presented. We show that splitting traffic into multiple ECMP classes can further reduce the maximum link load. Finally, a scenario is investigated where best effort traffic is routed in a ECMP class and traffic with high availability requirements is routed in a routing class with proactive protection against link and node failures. The evaluation shows that up to 30-40% of the total traffic can be put into the protected class without significanly increasing the maximum link load.