Rate-Based Dynamic Shortest Path Algorithm for Efficiently Routing Multiple Flows in SDN

Abstract

Efficient routing necessitates the underlying path selection algorithms to find a path that can satisfy certain Quality-of-Service (QoS) requirements of a given flow while maximizing throughput and minimizing maximum link-load. In the case of routing multiple flows at the same time, finding such multiple paths even with just the bandwidth constraint is a well-known NP-hard problem and has been widely studied in the literature as the Unsplittable Flow Problem (UFP). Unfortunately, the existing approximation and heuristic solutions suffer from excessive computation time or low performance in maximizing throughput and minimizing maximum link-load. In this paper, we propose a new effective heuristic solution to find multiple paths that can satisfy bandwidth requirements of a given set of unsplittable flows while providing better throughput and load balancing in Software Defined Networks (SDN). We demonstrate the efficiency of our heuristic using simulations.