Bootstrapped LARAC algorithm for fast delay-sensitive QoS provisioning in SDN networks

In today's networks, QoS provisioning becomes a major concern for service providers due to the massive increase in connected devices (e.g., mobile devices, servers, and Things), traffic in between, and the diverse service requirements (e.g., delay and bandwidth). Software-Defined Networking (SDN) promises solution for such issues with its central network control flexibility compared to traditional networking; nonetheless, a design of a fast and QoS guaranteeing routing algorithm is still needed. Delay Constrained Least Cost (DCLC) is a well-known NP-hard problem. LAgrange Relaxation-based Aggregated Cost (LARAC) algorithm is a Dijkstra-based QoS-aware algorithm and one of many heuristic algorithms proposed in the literature to solve the DCLC problem. Despite its outstanding performance over other algorithms in SDN, it still needs improvement. In this article, we present a modified version of LARAC, called MODLARAC, to improve the solution feasibility search state by exploiting LARAC's lower-bound paths before the approximation process start. Also, we modify its stop condition to avoid extra non-useful Dijkstra calls. We implement and evaluate MODLARAC using a realistic ISP network topology using Mininet and controlled by Floodlight SDN controller. We then compare MODLARAC against the original LARAC and BiLAD algorithms. The obtained results showed improvement up to 20% reduction in Dijkstra calls count compared to original LARAC and BiLAD algorithms without a significant increase in path's cost or delay metrics. It reached only 3% increase in path cost and 7% in path delay in its worst case with a safe distance of 11% lower than the delay demand.