End-to-End Routing Algorithm Based on Max-Flow Min-Cut in SDN Controllers

In this paper, we present seven novel Max-Flow Min-Cut (MFMC) based algorithms that solve the flow routing problem in the Software Defined Network Controller. Our algorithms identify potential traffic bottlenecks using the MFMC cut, and they avoid the bottlenecks during flow route construction through their choice of the cut edge added to the route. Our algorithms utilize either a random edge selection, a shortest path edge selection, or an edge capacity-based selection from the set of cut edges. Our simulation results show improvement in the network performance when using MFMC and shortest path edge selection compared to simple shortest path first algorithms, such that the mean wait time is reduced by 15.1%, the mean slowdown is reduced by 5.1%, reducing the maximum completion time by 9.6%, and increasing the mean throughput by 18.3%. Therefore, by explicitly considering congestion in routing decisions, better network performance is achieved.