Fast and efficient algorithm for delay-sensitive QoS provisioning in SDN networks.

Adoption of Software-Defined Networks(SDN) as a new networking paradigm, promises solutions for Quality of Service(QoS) management issues raised at the service providers level due to the massive increase in connected devices (e.g., Servers, Mobile devices, M2M, Things, etc.), traffic in between, and the diverse user and service demands (e.g., delay, bandwidth, etc.). Although its advantage in network control flexibility compared to traditional networking, SDN still requires a design of robust and fast QoS guaranteeing routing algorithms due to its central control computation overhead. In this article, we present a new QoS-aware routing algorithm designed to work on top of SDN and serves delay-sensitive services that require certain delay requirements with low computation time. Such problems are usually modeled as Delay Constrained Least Cost (DCLC) problem which is a well-known NP-hard problem. We adopted the Lagrangian relaxation-based approach that incorporates the delay constraint into the objective cost function to solve the DCLC problem. Differently than existing Lagrangian relaxation-based algorithms, we designed our algorithm to reduce the solution search space by exploiting the problem lower-bound cost and delay paths. Moreover, we defined three different constraint tightness factors inferred from the problem current state to avoid extra non-useful Dijkstra calls. To improve the solution quality, we propose a novel approach that use state information obtained from previous optimization iterations to obtain a small-size network subgraph. Then it search the obtained subgraph for a better solution that the Lagrangian relaxation-based approach may miss. We performed an extensive python-based simulation to evaluate the performance of MODLARAC and compared it with two Lagrangian relaxation-based heuristic algorithms proposed in the literature to solve the DCLC problem, LARAC, and BiLAD algorithms. The obtained results showed improvement up to a 15% reduction in internal Dijkstra calls count with about a 2% increase in the total path cost compared to those obtained by the optimal solution. [ABSTRACT FROM AUTHOR]