Comparative Study of Johnson and Bellman-Ford for Shortest Path in OpenFlow SDN

Abstract

Software-Defined Networking (SDN) provides a highly programmable architecture specifically by decoupling the control plane from the data plane. The efficiency of the controller in mapping topologies and responding to link failures depends heavily on the shortest-path algorithm used. While previous studies have evaluated algorithms like Bellman-Ford in small scale SDN, empirical comparisons with hybrid algorithms like Johnson in medium-scale dense topologies remain significantly limited. This study aims to provide an empirical comparative evaluation of Johnson and Bellman-Ford algorithms on OpenFlow 1.3 using the RYU controller, analyzing scalability across ring (sparse) and full-mesh (dense) topologies from 10 to 50 nodes. The research methodology relies on experimental emulation using Mininet to test convergence time, throughput, and recovery time during dynamic link failures. The results indicate that in sparse ring topologies, both algorithms achieve similar convergence under 0,06 seconds. However, in dense 50 node full-mesh networks containing 2.450 links, Bellman-Ford demonstrates a faster average convergence of 37,93 seconds compared to Johnson's 47,44 seconds, primarily due to the absence of graph reweighting overhead, despite exhibiting higher variance. Both algorithms maintained stable throughput, and while recovery times generally met the near carrier-grade standard, some scenarios in dense networks reached 60 milliseconds, slightly exceeding the 50 ms threshold. This study evaluates recovery during single link failure scenarios. In conclusion, Bellman-Ford is highly recommended for dense data center infrastructures, while Johnson is optimal for sparse networks requiring instant route recovery.

GS Cited Analysis