Incremental Deployment and Throughput Maximization Routing for a Hybrid SDN

To explore the advantages of software defined network (SDN), while preserving the legacy networking systems, a natural deployment strategy is to deploy a hybrid SDN incrementally to improve the network performance. In this paper, we address two technical challenges: an incremental deployment strategy and a throughput-maximization routing, for deploying a hybrid network incrementally. For incremental deployment, we propose a heuristic algorithm for deploying a hybrid SDN under the budget constraint, and prove the approximate factor of $ 1- \frac {1}{e} $ . For throughput-maximization routing, we apply a depth-first-search method and a randomized rounding mechanism to solve the multi-commodity $h$ -splittable flow routing problem in a hybrid SDN, where $h\ge 1$ . We also prove that our method has approximation ratio $O\left({\frac {1}{\log N}}\right)$ , where $ N $ is the number of links in a hybrid SDN. We then show, by both analysis and simulations, that our algorithms can obtain significant performance gains and perform better than the theoretical worst-case bound. For example, our incremental deployment scheme helps to enhance the throughout about 40% compared with the previous deployment scheme by deploying a small number of SDN devices, and the proposed routing algorithm can improve the throughput about 31% compared with ECMP in hybrid networks.