Toward efficient parallel routing optimization for large-scale SDN networks using GPGPU
Toward efficient parallel routing optimization for large-scale SDN networks using GPGPU
复制标题
使用 GPGPU 实现大规模 SDN 网络的高效并行路由优化
DOI：
10.1016/j.jnca.2018.03.031
复制
发表时间：
2018
影响因子：
8.7
通讯作者：
Shui Yu
中科院分区：
文献类型：
--
作者：
Xiong Wang;Qian Zhang;Jing Ren;Shizhong Xu;Sheng Wang;Shui Yu
路由优化是提高网络性能、保证用户QoS要求的有效方法。然而，随着网络规模和业务需求的快速增长，集中式控制平面的SDN网络路由优化面临着可扩展性问题。为了克服可扩展性的问题，我们的目标是加快路由优化过程中的大型网络，利用GPU的大规模并行计算能力。本文提出了一种基于拉格朗日松弛的并行布线优化算法（LR-PROA）。LR-PROA首先通过放宽链路容量约束，将路由优化问题分解为一组满足流量需求的路径计算问题，然后将路径计算任务分配给GPU，在GPU上并行执行。为了实现高度并行化，LR-PROA还针对每个交通需求并行化了路径计算过程。此外，为了提高算法的收敛速度，LR-PROA针对部分交通需求对计算路径进行了有效调整，并在每次迭代中设置了求解拉格朗日对偶问题的次梯度算法的步长。通过对合成网络拓扑结构的测试，验证了LR-PROA具有良好的优化性能和上级计算时间效率。在我们的模拟中，LR-PROA比大型网络中的基准算法快数十倍。
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.