進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-3008201814090600
論文名稱(中文) 在軟體定義網路中用於流量排程的元啟發式多限制路由機制
論文名稱(英文) A Metaheuristic Multi-Constraint Routing Mechanism for Traffic Scheduling in Software-Defined Networking
校院名稱 成功大學
系所名稱(中) 電腦與通信工程研究所
系所名稱(英) Institute of Computer & Communication
學年度 106
學期 2
出版年 107
研究生(中文) 鄭裕穎
研究生(英文) Yu-Ying Zheng
學號 q36051067
學位類別 碩士
語文別 英文
論文頁數 86頁
口試委員 指導教授-林輝堂
口試委員-楊竹星
口試委員-鄭伯炤
口試委員-李忠憲
口試委員-許靜芳
中文關鍵字 網路虛擬化  元啟發式路由規劃  軟體定義網路  服務品質 
英文關鍵字 Software Defined Networking  Network Virtualization  Metaheuristic Algorithm 
學科別分類
中文摘要 由於網路蓬勃的發展,各形各色的網路服務開始出現,如多媒體傳輸、網路串流、視訊會議等,這些類型的網路服務需要有相對應不同程度的服務品質(Quality of Service)需求,然而傳統網際協議(IP)的盡力遞送(Best Effort)原則沒有辦法滿足這些需求,基於此項原因要如何對於這些網路應用提供良好的路由規劃成為了一項需要良好處理的議題。為了達成以上這些需求,傳統網路中主要有兩種方法來解決,Integrated service (IntServ) 透過利用資源預留協定(Resource Reservation Protocol, i.e., RSVP) 來提供頻寬給對應的路由; Differentiated services (DiffServ) 則使用封包分類的方法,達成不同的服務品質需求。但受限於傳統網路分散式架構的影響,此二種方法都無法達成有效的部屬並達到快速並且一致的路由規劃。
而在近年來學者提出了一種新興的軟體定義網路(Software Defined Networking, i.e., SDN)架構,在此架構底下,網路將可大致分為控制層(Control Plane)與傳輸層(Data Plane),控制層的控制器(Controller)有權限來負責網路的管理,能使資料網路更靈活、更易於操作和管理、及能夠更好地應對應用程式發展。並且利用其中央集中式的控制模式將可以達成即時監控流量,並且能夠非常快速地重新調整網路以達成特定目標。因此,基於軟體定義網路下開發的管理機制能達成更好的路由規劃。然而,過去的研究只著重在服務品質的最佳化考量,並沒有考慮到軟體定義網路架構下,網路設備的記憶體大小的限制。基於此,本研究提出一套元啟發式路由機制,同時考量到路由的服務品質及選擇網路設備的記憶體使用率比較低的路由避免產生記憶體溢位而對整體網路造成延遲及控制器負擔等問題。並且經由透過模擬結果證明本研究機制不僅可以達成對於不同服務品質需求的網路應用流量,同時也可以避免網路設備的記憶體產生溢位。
英文摘要 Due to the rapid development of the Internet, more and more network services are beginning to emerge, such as multimedia transmission, network streaming, video conferencing, etc. These types of network services require different levels of Quality of Service (QoS) requirements. However, the Best Effort delivery principle of the traditional Internet Protocol (IP) cannot satisfy these needs. Therefore, providing appropriate routing mechanism for these network applications has become an important issue. In order to achieve these requirements, two main methods have been proposed in the traditional network. The Integrated Service (IntServ) provides the bandwidth to the corresponding route by using the Resource Reservation Protocol (RSVP); Differentiated services (DiffServ) use the method of packet classification to achieve different service quality requirements. However, due to the influence of decentralized architecture in the traditional network, neither of these methods has an effective subordinate and achieves fast and consistent routing planning.
In recent decades, scholars have proposed an emerging architecture which could refer to Software Defined Networking (SDN). Under this architecture, the network is divided into Control Plane and Data Plane. Authority of management is delegated to the control layer's controller, which makes the data network more flexible, easier to operate and manage, and better able to cope with application development. And with its central centralized control mode, we can instantly monitor traffic and re-adjust the network very quickly to achieve specific goals. Therefore, a management mechanism developed under software-defined network can achieve better routing planning. However, past research focused only on the optimization of service of quality and did not take into account the memory size limitations of network devices under the SDN architecture. Based on the above issues, this study proposes a metaheuristic routing mechanism to achieve QoS requirements of different flows while avoiding memory overflow problem in OpenFlow switch. Finally, the simulation results show that the research mechanism can not only achieve network application traffic for different service quality requirements, but also avoid overflow of network device memory.
論文目次 摘要 i
Abstract iii
Acknowledgements v
Contents vi
List of Figures viii
List of Tables x
Chapter 1 1
1.1 Overview 1
1.2 Software Defined Networking 3
1.3 OpenFlow Protocol 5
1.4 Network measurement in SDN 9
1.5 Constrained Shortest Path Problem in SDN 11
1.6 Complex Network Analysis 12
1.7 Motivation 13
1.8 Objective 14
1.9 Thesis Outline 15
Chapter 2 16
2.1 Metaheuristics 16
2.1.1 Simulated Annealing Algorithm 17
2.1.2 Genetic Algorithm 17
2.1.3 Ant Colony Optimization Algorithm 18
2.2 Network Measurement Mechanisms 18
2.3 QoS Technologies in Conventional Network 21
2.3.1 Integrated Services 21
2.3.2 Differentiated Services 22
2.4 Recent Research in OpenFlow-based QoS Routing Mechanisms 23
Chapter 3 25
3.1 Network Scenario 26
3.2 System Model 27
3.2.1 Topology Discovery Module 28
3.2.2 Multi-Constraint Routing Module 30
3.2.3 Network Measurement Module 38
Chapter 4 42
4.1 Simulation System 42
4.2 Comparison Methods 43
4.3 Simulation Results 44
4.3.1 Routing Performance in Different Topologies 44
Chapter 5 79
Bibliography 81

參考文獻 [1] Karakus, Murat, and Arjan Durresi. "Quality of service (qos) in software defined networking (sdn): A survey." Journal of Network and Computer Applications 80 (2017): 200-218.
[2] Mirchev, Atanas. "Survey of Concepts for QoS improvements via SDN." Future Internet (FI) and Innovative Internet Technologies and Mobile Communications (IITM) 33 (2015): 1.
[3] Masoudi, Rahim, and Ali Ghaffari. "Software defined networks: A survey." Journal of Network and computer Applications 67 (2016): 1-25.
[4] Fundation, Open Networking. "Software-defined networking: The new norm for networks." ONF White Paper 2 (2012): 2-6.
[5] Aurrecoechea, Cristina, Andrew T. Campbell, and Linda Hauw. "A survey of QoS architectures." Multimedia systems 6.3 (1998): 138-151.
[6] The basics you need to know about SDN. [Online]. Available: http://hamilton-barnes.co.uk/sdn/
[7] Jain, Sushant, et al. "B4: Experience with a globally-deployed software defined WAN." ACM SIGCOMM Computer Communication Review. Vol. 43. No. 4. ACM, 2013.
[8] Braden, Robert, David Clark, and Scott Shenker. Integrated services in the internet architecture: an overview. No. RFC 1633. 1994.
[9] Braden, Robert, et al. Resource reservation protocol (RSVP)--Version 1 functional specification. No. RFC 2205. 1997.
[10] Blake, Steven, et al. An architecture for differentiated services. No. RFC 2475. 1998.
[11] Egilmez, Hilmi E., et al. "OpenQoS: An OpenFlow controller design for multimedia delivery with end-to-end Quality of Service over Software-Defined Networks." Signal & Information processing association annual summit and conference (APSIPA ASC), 2012 Asia-Pacific. IEEE, 2012.
[12] Jinyao, Yan, et al. "HiQoS: An SDN-based multipath QoS solution." China Communications 12.5 (2015): 123-133.
[13] Tomovic, Slavica, Neeli Prasad, and Igor Radusinovic. "SDN control framework for QoS provisioning." Telecommunications Forum Telfor (TELFOR), 2014 22nd. IEEE, 2014..
[14] Moshref, Masoud, Minlan Yu, and Ramesh Govindan. "Resource/accuracy tradeoffs in software-defined measurement." Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking. ACM, 2013.
[15] Chowdhury, Shihabur Rahman, et al. "Payless: A low cost network monitoring framework for software defined networks." Network Operations and Management Symposium (NOMS), 2014 IEEE. IEEE, 2014.
[16] Cisco Visual Networking Index: Forecast and Methodology, 2016–2021, [Online] Available:https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/complete-white-paper-c11-481360.html
[17] Sinha, Debanshu, K. Haribabu, and Sundar Balasubramaniam. "Real-time monitoring of network latency in Software Defined Networks." Advanced Networks and Telecommuncations Systems (ANTS), 2015 IEEE International Conference on. IEEE, 2015.
[18] LAN/MAN Standards Committee. "IEEE Standard for Local and metropolitan area networks–Station and Media Access Control Connectivity Discovery." (2009).
[19] Pakzad, Farzaneh, et al. "Efficient topology discovery in software defined networks." Signal Processing and Communication Systems (ICSPCS), 2014 8th International Conference on. IEEE, 2014.
[20] OpenFlow Switch Specification - Open Networking Foundation [Online]. Available:https://www.opennetworking.org/wp-content/uploads/2014/10/openflow-switch-v1.5.1.pdf
[21] Juttner, Alpar, et al. "Lagrange relaxation based method for the QoS routing problem." INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. Vol. 2. IEEE, 2001.
[22] Qin, Zhijing, et al. "A software defined networking architecture for the internet-of-things." Network Operations and Management Symposium (NOMS), 2014 IEEE. IEEE, 2014.
[23] Lin, Chienhung, Kuochen Wang, and Guocin Deng. "A QoS-aware routing in SDN hybrid networks." Procedia Computer Science 110 (2017): 242-249.
[24] UMTS QoS, Quality of Service - UMTS World [Online] Available: http://www.umtsworld.com/technology/qos.htm
[25] Mininet. [Online]. Available: http://mininet.org/.
[26] Ryu OpenFlow controller [Online]. Available : https://osrg.github.io/ryu/.
[27] Kolahi, Samad S., et al. "Performance monitoring of various network traffic generators." Computer Modelling and Simulation (UKSim), 2011 UkSim 13th International Conference on. IEEE, 2011.
[28] Srivastava, Shalvi, et al. "Comparative study of various traffic generator tools." Engineering and Computational Sciences (RAECS), 2014 Recent Advances in. IEEE, 2014.
[29] Botta, Alessio, Alberto Dainotti, and Antonio Pescapé. "A tool for the generation of realistic network workload for emerging networking scenarios." Computer Networks 56.15 (2012): 3531-3547.
[30] Atary, Alon, and Anat Bremler-Barr. "Efficient round-trip time monitoring in OpenFlow networks." INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, IEEE. IEEE, 2016.
[31] Akyildiz, Ian F., et al. "A roadmap for traffic engineering in SDN-OpenFlow networks." Computer Networks 71 (2014): 1-30.
[32] Dorigo, Marco, and Gianni Di Caro. "Ant colony optimization: a new meta-heuristic." Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 congress on. Vol. 2. IEEE, 1999.
[33] Marinakis, Yannis, Athanasios Migdalas, and Panos M. Pardalos. "A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm." Journal of Global Optimization 38.4 (2007): 555-580.
[34] Shi, Xiaohu H., et al. "Particle swarm optimization-based algorithms for TSP and generalized TSP." Information processing letters 103.5 (2007): 169-176.
[35] Yu, Curtis, et al. "Flowsense: Monitoring network utilization with zero measurement cost." International Conference on Passive and Active Network Measurement. Springer, Berlin, Heidelberg, 2013.
[36] Egilmez, Hilmi E., Seyhan Civanlar, and A. Murat Tekalp. "An optimization framework for QoS-enabled adaptive video streaming over OpenFlow networks." IEEE Transactions on Multimedia 15.3 (2013): 710-715.
[37] Mohan, Purnima Murali, Tram Truong-Huu, and Mohan Gurusamy. "TCAM-aware local rerouting for fast and efficient failure recovery in software defined networks." Global Communications Conference (GLOBECOM), 2015 IEEE. IEEE, 2015.
[38] Beheshti, Neda, and Ying Zhang. "Fast failover for control traffic in software-defined networks." Global Communications Conference (GLOBECOM), 2012 IEEE. IEEE, 2012.
[39] Nakagawa, Yukihiro, et al. "Domainflow: Practical flow management method using multiple flow tables in commodity switches." Proceedings of the ninth ACM conference on Emerging networking experiments and technologies. ACM, 2013.
[40] Iyer, Aakash S., Vijay Mann, and Naga Rohit Samineni. "Switchreduce: Reducing switch state and controller involvement in openflow networks." IFIP Networking Conference, 2013. IEEE, 2013.
[41] Seddiki, M. Said, et al. "FlowQoS: QoS for the rest of us." Proceedings of the third workshop on Hot topics in software defined networking. ACM, 2014.
[42] Understanding the SDN Architecture [Online]. Available: https://www.sdxcentral.com/sdn/definitions/inside-sdn-architecture/
[43] Al-Fares, Mohammad, et al. "Hedera: dynamic flow scheduling for data center networks." Nsdi. Vol. 10. No. 8. 2010.
[44] ONF, “OpenFlow table type patterns,” Open Networking Foundation, Tech. Rep., August 2014. [Online]. Available: https://3vf60mmveq1g8vzn48q2o71a-wpengine.netdna-ssl.com/wp-content/uploads/2014/10/sb-TTP.pdf.
[45] McKeown, Nick, et al. "OpenFlow: enabling innovation in campus networks." ACM SIGCOMM Computer Communication Review 38.2 (2008): 69-74.
[46] Vijayasarathi, Deepak S., et al. "Ripple-precharge TCAM: A low-power solution for network search engines." Computer Design: VLSI in Computers and Processors, 2005. ICCD 2005. Proceedings. 2005 IEEE International Conference on. IEEE, 2005.
[47] Tsai, Hsiang-Jen, et al. "Energy-efficient TCAM search engine design using priority-decision in memory technology." IEEE Transactions on Very Large Scale Integration (VLSI) Systems 25.3 (2017): 962-973.
[48] Qiao, Siyi, et al. "Taming the flow table overflow in OpenFlow switch." Proceedings of the 2016 ACM SIGCOMM Conference. ACM, 2016.
[49] Katsaros, Dimitrios, Nikos Dimokas, and Leandros Tassiulas. "Social network analysis concepts in the design of wireless ad hoc network protocols." IEEE network 24.6 (2010).
[50] Wang, Zheng, and Jon Crowcroft. "Quality-of-service routing for supporting multimedia applications." IEEE Journal on selected areas in communications 14.7 (1996): 1228-1234.
[51] Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512.
[52] Newman, Mark EJ. "The mathematics of networks." The new palgrave encyclopedia of economics 2.2008 (2008): 1-12.
[53] Van Adrichem, Niels LM, Christian Doerr, and Fernando A. Kuipers. "Opennetmon: Network monitoring in openflow software-defined networks." Network Operations and Management Symposium (NOMS), 2014 IEEE. IEEE, 2014.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2023-08-30起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2023-08-30起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw