Incremental Deployment and Throughput Maximization Routing for a Hybrid SDN

Authors:

Abstract
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- 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 ≥ 1. We also prove that our method has approximation ratio O(1/log N), 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.
Funding Information
  • NSFC (U1301256, 61472383, 61472385)
  • NSF of Jiangsu in China (BK20161257)
  • China National Funds for Distinguished Young Scientists (61625205)
  • Key Research Program of Frontier Sciences, CAS (QYZDY-SSW-JSC002)
  • NSFC (61520106007, NSF ECCS-1247944, NSF CMMI 1436786, NSF CNS 1526638)

This publication has 28 references indexed in Scilit: