MODRA: Multi-Objective Distributed Routing Algorithm

This paper develops a systematic strategy to construct a model of an IP Network with multiple weight links and proposes a multi-objective distributed routing algorithm (MODRA) for the One-to-All Multi-objective Shortest Path (MOSP) Problem. The formal proof of a loop-free routing in distributed mode is given, as well as extensive experiments are performed in simulated networks to show the algorithm performance. The proposed algorithm is based on computation of complete and exact Pareto-optimal set of paths for each destination and specific routing path selection with the minimal multi-dimension path length. In this work, the proposed MODRA is tested on four network topologies with two-weight links and different configurations, and the performance is evaluated w.r.t. multiple upper-bound path constraints. The algorithm is used to compute a Routing Information Base (RIB) table in each node. Then the distributed hop-by-hop packet routing is simulated and the actual path traversed by a packet is compared to the initially computed one. Our approach supports arbitrary topology, number of additive link weights and shows optimal performance in terms of computing feasible paths satisfying the given multiple upper-bound constraints. The proposed algorithm is implemented and tested in a simulated environment, and the framework of this work could be adopted to design other routing algorithms for multi-objective distributed routing in IP Networks. The algorithm performance evaluation shows its’ ability to compute optimal paths w.r.t. multiple upper-bound constraints, guarantee loop-free distributed routing and satisfy strict execution time requirements. The algorithm is fully compatible with the current router architecture and can be easily implemented in a router.