The copyright © of this thesis belongs to its rightful author and/or other copyright owner. Copies can be accessed and downloaded for non-commercial or learning purposes without any charge and permission. The thesis cannot be reproduced or quoted as a whole without the permission from its rightful owner. No alteration or changes in format is allowed without permission from its rightful owner.
CONTROLLER PLACEMENT MECHANISM IN SOFTWARE DEFINED NETWORK USING K-MEDIAN ALGORITHM
NOOR SAAD FAHAD
MASTER OF SCIENCE INFORMATION TECHNOLOGY
UNIVERSITI UTARA MALAYSIA
2016
ii
Permission to Use
In presenting this thesis in fulfilment of the requirements for a postgraduate degree from Universiti Utara Malaysia, I agree that the Universiti Library may make it freely available for inspection. I further agree that permission for the copying of this thesis in any manner, in whole or in part, for scholarly purpose may be granted by my supervisor(s) or, in their absence, by the Dean of Awang Had Salleh Graduate School of Arts and Sciences. It is understood that any copying or publication or use of this thesis or parts thereof for financial gain shall not be allowed without my written permission. It is also understood that due recognition shall be given to me and to Universiti Utara Malaysia for any scholarly use which may be made of any material from my thesis.
Requests for permission to copy or to make other use of materials in this thesis, in whole or in part, should be addressed to:
Dean of Awang Had Salleh Graduate School of Arts and Sciences UUM College of Arts and Sciences
Universiti Utara Malaysia 06010 UUM Sintok
iii
Abstrak
SDN memisahkan satah kawalan dengan sata data melalui pemindahan satah kawalan ke entity lain. Pemisahan ini menimbulkan beberapa masalah, antaranya penempatan pengawal dalam rangkaian. Kajian ini bertujuan untuk mengkaji penempatan node kawalan dalam SDN. Kadeah k-median digunakan untuk menentukan kududukan nod pengawal, dan nod pengawal dengan purata kependaman terendah akan dipilih. Penentu kedudukan ini akan membandingkan algoritma greedy yang mengira kombinasi berdasarkan kedudukan nod dan mengira nilai terbaik untuk setiap turutan. Kajian ini turut menbandingkan kombinasi keputusan melalui kedudukan nod tertentu, dan keputusan menunjukkan kaedah k-median memberikan nilai yang lebih tinggi. Tiga nod pengawal dipilih sebagai bilangan nod minima and dinilai dari segi kelewatan dan beban, dan keputusan menunjukkan tiga nod memadai sekiranya tiada kelewatan atau bebenan dalam rangkaian.
Kata kunci: SDN; Pengawal; Penempatan; Purata Kependaman; K-median
iv
Abstract
Software Defined Network (SDN) decouples the control plane and the data plane, and moves the control plane to an external entity. The decoupling raises many challenges, and one of these is the placement of the controller in the network. This study aims to address controller placement problem in SDN. k-median is used to determine the placement of the controllers, and the placement with the lowest value of average propagation latency will be chosen. The placement compares two resulted placements.
First, comparing to greedy algorithm that computes the combinations according to the order of the nodes and calculates the best values at each step, and the results were identical. The second comparison was with the combinations results from considering the placement from specific nodes, and the results showed that it gives higher results than depending on the lowest values resulted from the k-median. Finally, three controllers are chosen as the minimum number of controllers, they were evaluated in terms of delay and load, and as results it was found that three controllers are suitable number of controllers as long as there is no delay or load in the network. Combining the two algorithms for finding the placement and the number results in Controller Placement Mechanism (CPM)
Keywords: SDN; Controllers; Placement; Average propagation latency; K-median
v
Acknowledgement
In the name of ALLAH, Most Gracious, Most merciful
All thanks and praises to Allah (SWT) for the blessings of life and for guiding me through studies and life.
My sincere appreciation goes to my supervisors, Dr. Adib Habbal and Mr. Suwannit Chareen Chit, for your patient guidance and encouragement through this research, without your valuable support, this research will not be possible, Thank you.
To my parents, without your love and support I would not be able to continue my studying, I’m so grateful for always believing in me, encouraging me, and never let me doubt myself, I love you, may ALLAH continue to bestow his blessings on you.
To the examiners committee, I’m grateful for your guidance and remarks to make this research better.
To UNIVERSITI UTARA MALAYSIA for giving the opportunity to further my study, and to make my master journey enjoyable and memorable, you have my sincere gratitude.
To my family and friends, thank you for all your support and praying.
vi
Dedication
To my family.
vii
Table of Content
PERMISSION TO USE ... II
ABSTRAK ... III
ABSTRACT ... IV
ACKNOWLEDGEMENT ...V
TABLE OF CONTENT ... VII
LIST OF FIGURES ... IX
LIST OF TABLES ...X
LIST OF ABBREVIATIONS ... XI
CHAPTER ONE INTRODUCTION ... 1
1.1 OVERVIEW ... 1
1.2 PROBLEM STATEMENT ... 3
1.3 RESEARCH QUESTIONS ... 4
1.4 RESEARCH OBJECTIVES ... 4
1.5 SIGNIFICANT OF RESEARCH ... 4
1.6 SCOPE OF THE RESEARCH ... 5
1.7 RESEARCH OUTCOMES ... 5
1.8 ORGANIZATION OF THE STUDY... 5
CHAPTER TWO LITERATURE REVIEW ... 7
2.1 SOFTWARE DEFINED NETWORK ... 8
2.1.1 Software Defined Network Layers ... 8
2.1.2 Software Defined Network Advantages ... 10
2.1.3 Software Defined Network Challenges ... 11
2.2 RELATED WORK ... 12
2.2.1 Related Work Based on k-center problem ... 12
2.2.2 Related Work Based on Different Algorithms ... 17
2.2.3 Related Work of Distributed Controllers ... 22
2.3 SUMMARY ... 25
CHAPTER THREE METHODOLOGY ... 27
3.1 INTRODUCTION ... 27
viii
3.2 AWARENESS OF PROBLEM ... 28
3.3 THE PROPOSED CONTROLLER PLACEMENT MECHANISM DESIGN ... 28
3.4 DEVELOPMENT OF PROPOSED MECHANISM ... 30
3.4.1 k-median ... 30
3.4.2 Simulation and Development Tools ... 31
3.5 PERFORMANCE EVALUATION ... 32
3.6 SUMMARY ... 34
CHAPTER FOUR CONTROLLER PLACEMENT MECHANISM ... 35
4.1 THE PROPOSED CONTROLLER PLACEMENT MECHANISM ... 35
4.2 IMPLEMENTATION TOOLS ... 37
4.3 IMPLEMENTATION STEPS ... 38
4.4 THE PLACEMENT VALIDATION ... 45
4.5 EVALUATION OF PERFORMANCE ... 48
4.6 RESULTS AND DISCUSSION ... 53
4.7 SUMMARY ... 60
CHAPTER FIVE CONCLUSION ... 61
5.1 CONTRIBUTION... 61
5.2 LIMITATION ... 62
5.3 FUTURE WORK ... 62
5.4 CONCLUSION ... 62
REFERENCES ... 64
APPENDIX ... 67
ix
List of Figures
FIGURE 1:TRADITIONAL SCHEME (A)SDNARCHITECTURE (B) ... 2
FIGURE 2SDNARCHITECTURE (KREUTZ ET AL.,2015) ... 10
FIGURE 3THE RESEARCH METHODOLOGY FRAMEWORK ... 27
FIGURE 4:THE DESIGN OF CONTROLLER PLACEMENT MECHANISM ... 29
FIGURE 5THE NETWORK TOPOLOGY OF CORE NETWORK ... 32
FIGURE 6NETWORK BORDER ROUTER ... 33
FIGURE 7CONTROLLER PLACEMENT MECHANISM ... 36
FIGURE 8MYRENTOPOLOGY ... 40
FIGURE 9THE CODE FOR CREATING WEIGHTED GRAPH ... 41
FIGURE 10CONTROLLER PLACEMENT ... 44
FIGURE 11PLACEMENT FUNCTIONS ... 45
FIGURE 12HIGHEST,LOWEST AVERAGE PROPAGATION LATENCY ... 46
FIGURE 13K-MEDIAN AND GREEDY ALGORITHM ... 50
FIGURE 14SHOWS AVERAGE PROPAGATION LATENCY FOR BOTH METHODS... 52
FIGURE 15COMPARING ALL METHODS ... 53
FIGURE 16THE PLACEMENT OF THREE CONTROLLERS ... 54
FIGURE 17CHECKING THE RESPONSE TIME ... 57
FIGURE 18BEFORE CHANGING THE THRESHOLD ... 58
FIGURE 19THE RESULTS BEFORE THE CHANGE ... 59
FIGURE 20AFTER THE CHANGE ... 59
FIGURE 21THE FIRST ADD AFTER THE CHANGE ... 59
FIGURE 22THE SECOND ADD AFTER THE CHANGE ... 59
FIGURE 23THE FIRST REMOVE AFTER CHANGING BACK ... 60
FIGURE 24THE SECOND REMOVE AFTER CHANGING BACK ... 60
FIGURE 25THE FINAL RUN ... 60
x
List of Tables
TABLE 1RELATED WORK OF K-CENTER ... 15
TABLE 2RELATED WORK OF DIFFERENT ALGORITHMS ... 20
TABLE 3RELATED WORK OF DISTRIBUTED CONTROLLERS ... 24
TABLE 5THE PLACEMENT OF THE CONTROLLERS ... 46
TABLE 6THE PLACEMENT CALCULATED AND GREEDY CALCULATIONS ... 49
TABLE 7COMPARING THE RESULTS OF EACH PLACEMENT ... 51
TABLE 8THE RESULTS OF THE RESPONSE TIME ... 55
xi
List of Abbreviations
SDN - Software Defined Network CPM - Controller Placement Mechanism NOS - Network Operating System FD - Forwarding Devices DP - Data Plane
SI - Southbound Interface CP - Control Plane
NI - Northbound Interface MP - Management Plane
API - Application Program Interface CPP - Controller Placement Problem
CCPP - Capacitated Controller Placement Problem RCP - Reliability aware Controller Placement SA - Simulated Annealing
POCO - Pareto-based Optimal COntroller placement PSA - Pareto Simulated Annealing
GreCo - GREEN CENTRALIZED CONTROLLER BIP - Binary Integer Program
MC - Main Controllers SC - Slave Controllers
AVL - Average Propagation latency
MyREN - Malaysian Research & Education Network MoE - Ministry of Education
MDeC - Multimedia Development Coperation UITM - Universiti Teknologi MARA
xii UTP - Universiti Teknologi Petronas UUM - Universiti Utara Malaysia UM - University of Malaya
UNIMAS - Universiti Malaysia Sarawak UMS - Universiti Malaysia Sabah
IUM - International Islamic University Malaysia UPSI - Sultan Idris Education University
UPM - Universiti Putra Malaysia
UTHM - Universiti Tun Hussein Onn Malaysia UTM - University of Technology, Malaysia UMT - Universiti Malaysia Terengganu UMK -Universiti Malaysia Kelantan UDM - Universiti Darul Iman Malaysia UMP - Universiti Malaysia Pahang
UPNIM - National Defence University of Malaysia UTEM - Universiti Teknikal Malaysia Melaka NOC - Network Operation Center
UKM - National University of Malaysia MMU - Multimedia University
USIM - Universiti Sains Islam Malaysia UNITEN - Universiti Tenaga Nasional
MIMOS - Malaysia's national R&D centre in ICT TMRND - Telekom Research & Development MOHE - Ministry of Higher Education USM - Universiti Sains Malaysia UNIMAP - Universiti Malaysia Perlis
1
CHAPTER ONE INTRODUCTION
1.1 Overview
The current network schemes are complex and very difficult to manage. Predefined policies make the network difficult to be configured and also very hard to reconfigured so that it can respond to the load, faults and changes in the network (Open Networking Foundation, 2012). Current networks are integrated vertically where the control plane (that decides how to handle the traffic), and the data plane (that forwards the traffic based on the decision of the control plane) are coupled together which lead to the reduction of the flexibility as well as holding back the innovation and the network infrastructure evolution.
Software Defined Network (SDN) has gotten a lot of attention recently as a solution to overcome the limitations of the current network schemes. According to the Open Networking Foundation, “ the SDN architecture, the control and data planes are decoupled, network intelligence and state are logically centralized, and the underlying network infrastructure is abstracted from the applications” (Open Networking Foundation, 2012). Based on this definition (Sezer et al., (2013)) extracted four features which are: the control plane and the data plane are separated, interfaces are open between the data plane and the control plane, the controller is centralized, and the network programmability by external applications.
Kreutz et al., (2015) defined SDN as an architecture for the network that has four pillars: First, the separation of the control plane and the data plane. The controller
The contents of the thesis is for
internal user
only
64
REFERENCES
1. Dixit, A. A., Hao, F., Mukherjee, S., Lakshman, T. V., & Kompella, R. (2014, October). ElastiCon: an elastic distributed sdn controller. In Proceedings of the tenth ACM/IEEE symposium on Architectures for networking and communications systems (pp. 17-28). ACM.
2. Heller, B., Sherwood, R., & McKeown, N. (2012). The controller placement problem. ACM SIGCOMM Computer Communication Review, 42(4), 473.
doi:10.1145/2377677.2377767
3. Hu, F., Hao, Q., & Bao, K. (2014). A Survey on SDNing (SDN) and OpenFlow:
From Concept to Implementation. IEEE Communications Surveys & Tutorials, 16(c), 1–1. doi:10.1109/COMST.2014.2326417
4. Hu, Y., Wendong, W., & Gong, X. (2013). Reliability-aware controller placement for Software-Defined Networks. Integrated Network Management (IM 2013), 2013 IFIP/IEEE International Symposium on , vol., no., pp.672-675, 27-31 5. Introduction-to-Mininet @ github.com. (n.d.). Retrieved from
https://github.com/mininet/mininet/wiki/Introduction-to-Mininet
6. Jiménez, Y., Cervelló-Pastor, C., & García, A. J. (2014). On the controller placement for designing a distributed SDN control layer. 2014 IFIP Networking Conference, IFIP Networking 2014. doi:10.1109/IFIPNetworking.2014.6857117 7. Kreutz, D., Rothenberg, C. E., Ieee, M., Azodolmolky, S., Ieee, S. M., Uhlig, S.,
& Ieee, M. (2015). Software-Defined Networking : A Comprehensive Survey, 103(1). doi:10.1109/JPROC.2014.2371999
8. Lange, S., Gebert, S., Zinner, T., Tran-gia, P., Hock, D., Jarschel, M., &
Hoffmann, M. (2015). Heuristic Approaches to the Controller Placement Problem in Large Scale SDN Networks, 12(1), 4–17.
65
9. Open Networking Foundation. (2012). Software-Defined Networking: The New Norm for Networks [white paper]. ONF White Paper, 1–12.
10. Pinheiro, R. S., Pinheirot, B. A., Jorge, A., & Abelem, G. (2014). Model of Organization and Distribution of Applications for SDNs : SDNrepo, 188–193.
11. Ruiz-rivera, A., Chin, K., & Soh, S. (2015). GreCo : An Energy Aware Controller Association Algorithm for SDNs. IEEE Communication Letters, 19(4), 541–544.
12. Sallahi, A., & St-hilaire, M. (2015). Optimal Model for the Controller Placement Problem in SDNs, 19(1), 30–33.
13. Santos, M. a S., Nunes, B. a a, Obraczka, K., & Turletti, T. (2014). Decentralizing SDN ’ s Control Plane, 1–4.
14. Sezer, S., Scott-Hayward, S., Chouhan, P., Fraser, B., Lake, D., Finnegan, J., … Rao, N. (2013). Are we ready for SDN? Implementation challenges for software- defined networks. IEEE Communications Magazine, 51(7), 36–43.
doi:10.1109/MCOM.2013.6553676
15. Vazirani, V. V. (2001). Approximation Algorithms. Approximation Algorithms, 94(2), xx+378. doi:10.1002/rsa.10038
16. Vaishnavi, V. K., & Kuechler, W. (2015). Design science research methods and patterns: innovating information and communication technology. Crc Press.
17. Wang, H. (2014). Authentic and Confidential Policy Distribution in Software Defined Wireless Network, 1167–1171.
18. Xia, W., Wen, Y., Member, S., Heng Foh, C., Niyato, D., & Xie, H. (2015). A Survey on Software-Defined Networking. IEEE Communication Surveys &
Tutorials, 17(1), 27–51. doi:10.1109/COMST.2014.2330903
66
19. Yannan, H. U., Wendong, W., Xiangyang, G., Xirong, Q. U. E., & Shiduan, C.
(2014). On Reliability-optimized Controller Placement for Software-Defined Networks, (February), 38–54.
20. Yao, G., Bi, J., & Guo, L. (2013). On the cascading failures of multi-controllers in SDNs. Proceedings - International Conference on Network Protocols, ICNP, (1), 3–4. doi:10.1109/ICNP.2013.6733624
21. Yao, G., Bi, J., Li, Y., & Guo, L. (2014a). On the Capacitated Controller Placement Problem in SDNs. IEEE Communications Letters, 18(August), 1339–
1342. doi:10.1109/LCOMM.2014.2332341 22. Anaconda. https://www.continuum.io.
23. Spyder. https://pythonhosted.org.
24. Python. https://www.Python.org.
25. MyREN. https://www.myren.net.my.
26. Networkx. https://networkx.githup.io.
27. Multiprocessing. https://docs.python.org 28. Time. https://docs.python.org.
29. Google Maps. https://maps.google.com 30. Google Earth. https://earth.google.com
