Toward efficient parallel routing optimization for large-scale SDN networks using GPGPU

Routing optimization is an efficient way to improve network performance and guarantee the QoS requirements of users. However, with the rapid growth of network size and traffic demands, the routing optimization of SDN networks with centralized control plane is facing the scalability issue. To overcome the scalability issue, we aim to speed up the routing optimization process in large networks by utilizing the massive parallel computation capability of GPU. In this paper, we develop an efficient Lagrangian Relaxation based Parallel Routing Optimization Algorithm (LR-PROA). LR-PROA first decomposes the routing optimization problem into a set of path calculation problems for the traffic demands by relaxing the link capacity constraints, then the path calculation tasks are dispatched to GPU and executed concurrently on GPU. In order to achieve high degree of parallelism, LR-PROA also parallelizes the path calculation process for each traffic demand. Furthermore, to improve the convergence speed, LR-PROA uses efficient methods to adjust the calculated paths for a part of traffic demands and set the step size of subgradient algorithm for solving the Lagrangian dual problem in each iteration. Our evaluations on synthetic network topologies verify that LR-PROA has good optimization performance as well as superior calculation time efficiency. In our simulations, LR-PROA is up to tens of times faster than benchmark algorithms in large networks.