An Approximation Algorithm for Incrementally Deploying SDN Forwarding Devices
Article No.: 38, Pages 1 - 8
Abstract
There are two main optimization problems in software defined networks' traffic engineering, selecting conventional nodes to upgrade to SDN nodes, and finding a routing technique that minimize link utilization. While the second problem is almost solved, there are still not many theoretical results for the first problem. The approximation ratio of the only approximation algorithm for these problems is still as large as O(n), when n is the number of nodes. In this paper, we show that the problem is NP-hard, even for the single-source single-sink case. We then develop an algorithm for the case, and prove that our algorithm is kd-approximation algorithm, when k is the number of nodes to upgrade and d is the maximum degree of networks. We strongly believe that our algorithm can be extended to general cases in future.
References
[1]
S. Agarwal, M. Kodialam, and T. V. Lakshman. 2013. Traffic engineering in software defined networks. In 2013 Proceedings IEEE INFOCOM. 2211--2219.
[2]
M. Caria, A. Jukan, and M. Hoffmann. 2013. A performance study of network migration to SDN-enabled Traffic Engineering. In 2013 IEEE Global Communications Conference (GLOBECOM). 1391--1396.
[3]
Nick Feamster, Jennifer Rexford, and Ellen Zegura. 2014. The Road to SDN: An Intellectual History of Programmable Networks. SIGCOMM Comput. Commun. Rev. 44, 2 (April 2014), 87--98.
[4]
Moran Feldman and Rani Izsak. 2014. Constrained Monotone Function Maximization and the Supermodular Degree. In APPROX-RANDOM'14. 160--175.
[5]
Michael L. Fredman and Robert Endre Tarjan. 1987. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. J. ACM 34, 3 (July 1987), 596--615.
[6]
Y. Guo, Z. Wang, X. Yin, X. Shi, J. Wu, and H. Zhang. 2015. Incremental deployment for traffic engineering in hybrid SDN network. In 2015 IEEE 34th International Performance Computing and Communications Conference (IPCCC). 1--8.
[7]
Jun He and Wei Song. 2015. Achieving near-optimal traffic engineering in hybrid software defined networks. In IFIP Networking Conference'15. 1--9.
[8]
David Ke Hong, Yadi Ma, Sujata Banerjee, and Z. Morley Mao. 2016. Incremental Deployment of SDN in Hybrid Enterprise and ISP Networks. In Proceedings of the Symposium on SDN Research (SOSR '16). ACM, New York, NY, USA, Article 1, 7 pages.
[9]
Sushant Jain, Alok Kumar, Subhasree Mandal, Joon Ong, Leon Poutievski, Arjun Singh, Subbaiah Venkata, Jim Wanderer, Junlan Zhou, Min Zhu, Jon Zolla, Urs Hölzle, Stephen Stuart, and Amin Vahdat. 2013. B4: Experience with a Globally-deployed Software Defined Wan. In Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM (SIGCOMM '13). ACM, New York, NY, USA, 3--14.
[10]
Andreas Krause and Daniel Golovin. 2012. Submodular Function Maximization. (2012), 28. https://las.inf.ethz.ch/files/krause12survey.pdf
[11]
Diego Kreutz, Fernando M. V. Ramos, Paulo Veríssimo, Christian Esteve Rothenberg, Siamak Azodolmolky, and Steve Uhlig. 2015. Software-defined networking: A comprehensive survey. Proc. IEEE 103, 1 (2015), 63. http://arxiv.org/abs/1406.0440
[12]
Bhaskar Krishnamachari, Deborah Estrin, and Stephen Wicker. 2002. Modelling data-centric routing in wireless sensor networks. In INFOCOM'02, Vol. 2. 39--44.
[13]
R Garey Michael and S Johnson David. 1979. Computers and intractability: a guide to the theory of NP-completeness. WH Free. Co.
[14]
Konstantinos Poularakis, George Iosifidis, Georgios Smaragdakis, and Leandros Tassiulas. 2017. One step at a time: Optimizing SDN upgrades in ISP networks. In INFOCOM'17.
[15]
A. Soham. 2017. Finding the maximum bandwidth along a single path in a network. (2017). https://cs.stackexchange.com/questions/1591/finding-the-maximum-bandwidth-along-a-single-path-in-a-netwo
[16]
Ashwin Sridharan, Roch Gúerin, and Christophe Diot. 2005. Achieving Near-optimal Traffic Engineering Solutions for Current OSPF/IS-IS Networks. IEEE/ACM Trans. Netw. 13, 2 (April 2005), 234--247.
[17]
Stefano Vissicchio, Laurent Vanbever, and Olivier Bonaventure. 2014. Opportunities and Research Challenges of Hybrid Software Defined Networks. SIGCOMM Comput. Commun. Rev. 44, 2 (April 2014), 70--75.
[18]
W. Xia, Y. Wen, C. H. Foh, D. Niyato, and H. Xie. 2015. A Survey on Software-Defined Networking. IEEE Communications Surveys Tutorials 17, 1 (Firstquarter 2015), 27--51.
Index Terms
- An Approximation Algorithm for Incrementally Deploying SDN Forwarding Devices
Recommendations
Performance of SDN Routing in Comparison with Legacy Routing Protocols
CYBERC '15: Proceedings of the 2015 International Conference on Cyber-Enabled Distributed Computing and Knowledge DiscoveryLegacy routing protocols such as OSPF and BGP have been developed very comprehensive, but its rigid complex system has been difficult to adapt to the fast growing Internet. The emergence of Software Defined Network (SDN) has brought hope for the ...
Performance Analysis of SDN/OpenFlow Controllers: POX Versus Floodlight
Software-Defined Networking (SDN) is an emerging network architecture that is adaptable, dynamic, cost-effective, and manageable. The SDN architecture is a form of network virtualization where the network controlling functions and forwarding functions ...
Traffic Engineering in SDN/OSPF Hybrid Network
ICNP '14: Proceedings of the 2014 IEEE 22nd International Conference on Network ProtocolsTraffic engineering under OSPF routes along the shortest paths, which may cause network congestion. Software Defined Networking (SDN) is an emerging network architecture which exerts a separation between the control plane and the data plane. The SDN ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2018
628 pages
ISBN:9781450363853
DOI:10.1145/3164541
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
- SKKU: SUNGKYUNKWAN UNIVERSITY
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 January 2018
Check for updates
Author Tags
Qualifiers
- Short-paper
- Research
- Refereed limited
Funding Sources
- JST ERATO
Conference
IMCOM '18
IMCOM '18: The 12th International Conference on Ubiquitous Information Management and Communication
January 5 - 7, 2018
Langkawi, Malaysia
Acceptance Rates
IMCOM '18 Paper Acceptance Rate 100 of 255 submissions, 39%;
Overall Acceptance Rate 213 of 621 submissions, 34%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 83Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in