Abstract
To improve traffic management ability, Internet Service Providers (ISPs) are gradually upgrading legacy network devices to programmable devices that support Software-Defined Networking (SDN). The coexistence of legacy and SDN devices gives rise to a hybrid SDN. Existing hybrid SDNs do not consider the potential performance issues introduced by a centralized SDN controller: flow requests processed by a highly loaded controller may experience long-tail processing delay; inappropriate multi-controller deployment could increase the propagation delay of flow requests. In this paper, we propose to jointly consider the deployment of SDN switches and their controllers for hybrid SDNs. We formulate the joint problem as an optimization problem that maximizes the number of flows that can be controlled and managed by the SDN and minimizes the propagation delay of flow requests between SDN controllers and switches under a given upgrade budget constraint. We show this problem is NP-hard. To efficiently solve the problem, we propose some techniques (e.g., strengthening the constraints and adding additional valid inequalities) to accelerate the global optimization solver for solving the problem for small networks and an efficient heuristic algorithm for solving it for large networks. The simulation results from real network topologies illustrate the effectiveness of the proposed techniques and show that our proposed heuristic algorithm uses a small number of controllers to manage a high amount of flows with good performance.
| Original language | English (US) |
|---|---|
| Article number | 8672633 |
| Pages (from-to) | 1012-1028 |
| Number of pages | 17 |
| Journal | IEEE Journal on Selected Areas in Communications |
| Volume | 37 |
| Issue number | 5 |
| DOIs | |
| State | Published - May 2019 |
Bibliographical note
Funding Information:Manuscript received October 10, 2018; revised January 30, 2019 and March 10, 2019; accepted March 13, 2019. Date of publication March 21, 2019; date of current version April 16, 2019. The work of Z. Guo and Z.-L. Zhang was supported by NSF under Grants CNS-1411636, CNS-1618339, CNS-1617729, CNS-1814322, and CNS-1836772. The work of W. Chen and Y.-F. Liu was supported in part by the National Natural Science Foundation of China (NSFC) under Grants 11671419, 11571221, 11688101, and 11631013, and in part by the Beijing Natural Science Foundation under Grant L172020. (Corresponding author: Ya-Feng Liu.) Z. Guo is with the School of Automation, Beijing Institute of Technology, Beijing 100081, China, and also with the Department of Computer Science and Engineering, University of Minnesota Twin Cities, Minneapolis, MN 55455 USA (e-mail: guolizihao@hotmail.com).
Funding Information:
The work of Z. Guo and Z.-L. Zhang was supported by NSF under Grants CNS-1411636, CNS-1618339, CNS- 1617729, CNS-1814322, and CNS-1836772. The work of W. Chen and Y.-F. Liu was supported in part by the National Natural Science Foundation of China (NSFC) under Grants 11671419, 11571221, 11688101, and 11631013, and in part by the Beijing Natural Science Foundation under Grant L172020.
Publisher Copyright:
© 1983-2012 IEEE.
Keywords
- Complexity analysis
- controller deployment
- heuristic algorithm
- hybrid software-defined networking (SDN)
- switch upgrade
- upgrade budget