Routing Optimization for SDN Networks Based on Pivoting Rules for the Simplex Algorithm

摘要

Efficient optimization strategies for traffic engineering and routing are important tools for dimensioning networks and provisioning bandwidth for different applications. While current approaches such as MPLS-TE are usually focused on metric such as minimum required bandwidth, we propose to describe here bandwidth requirements as linear utility functions. Based on this description we address in this paper the optimization problem of finding unicast routes such that the average utility of the flows in a network is maximized. This optimization problem, which is a specialization of the multi-commodity flow problem where no splitting allowed, is known to be NP-hard. Our contributions in this paper are two heuristic algorithms for efficiently finding a good solution to this optimization problem. Our method is based on a modification of the simplex algorithm used for solving linear programing problems, where we propose two pivoting rules tailored to the routing optimization problem. Via a numerical evaluation on randomly generated topologies, we provide indications on the optimality of the solutions as well as number of iterations required. We show that compared to standard optimization technique using branch-andcut, our approaches reaches a relative difference of only 0:5% and even outperforms it on some topologies where time limits are set.