MODRA: Multi-Objective Distributed Routing Algorithm

<p>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 and All-to-All Multiobjective Shortest Path (MOSP) Problems. The formal proof of a loop-free routing in a 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 the single dimension path conversion principle and constructs a ”Shortest” Path Tree w.r.t. the given single dimension path conversion metric. 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 upperbound 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 good 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 efficient 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.</p>