臺灣博碩士論文加值系統

近年來,網絡功能虛擬化(NFV)的技術被提出,並用來將網絡功能與底層 的硬體分開,以軟體方式提供網路加值服務功能。另外一方面,服務功能鏈(SFC) 的概念也被提出,用來讓端到端之間的網路訊務流依照特定順序經過一些加值網 路服務後才到達目的地。服務功能於資料中心中的部署策略,會十分顯著的影響 服務功能鏈的效能。本論文致力於研究混合式 NFV 環境中的服務功能部署問題, 這種部署環境是資料中心從傳統網路轉變為 NFV 網絡過渡期間的一種替代方案。
本論文所提出的 GASFP 是一種高效能的部署策略,用於最佳化混合式 NFV 環境中的服務功部署以及鏈結。GASFP 結合 GA(基因演算法算法)和貪婪最廣 度優先搜尋演算法,減少為了提供 SFC 服務而導致資料中心計算資源的浪費, 並找到一個用以減緩不適當的服務功能部署而造成延遲增加的解決方案。模擬結 果顯示,與其他 3 種演法:BINPacking,GKMSFP 以及 VCD 相比,GASFP 無 論是在混合式NFV環境或是純NFV環境中,在服務功能路徑的平均延遲和VNF 部署成本的表現上,均表現出最佳的效能。
本論文還在 XenServer 中設計並實作了一服務功能雲端平台,以及一個名為 NSHSFC 的 SFC 導向機制,以驗證本論文所提出的演算法以及實驗環境比先前 的相關研究更為全面以及真實。

In recent years, the network functions virtualization (NFV) was proposed to separate network functions from the underlying hardware to provide value-added service functions with software. The concept of service function chain (SFC) architecture has also been proposed, which allow traffic pass through some value-added network functions between end-to-end services. The placement of the service functions in data centers significantly affects the performance of SFC. We study the service function placement problem in hybrid NFV environment, which is an alternative plan during the transition from traditional networks to NFV networks in data centers.
We present GASFP, a high-performance approach for optimizing service function placement and service chaining in hybrid NFV environment. GASFP combine GA (Genetic Algorithm) and Greedy best-first search algorithm to reduce the waste of data center computation resource for providing SFC services and find a good solution to slow down the growth of delay from unsuitable service function placement. Simulation results show that when compared with other 3 algorithms: BINPacking, GKMSFP and VCD, GASFP has the best performance of average delay and VNF placement cost no matter in hybrid NFV environment or pure NFV environment.
We also implement a service function cloud platform and a SFC steering mechanism named NSHSFC in XenServer to verify our works are more comprehensive and realistic than the former works.
Keyword: Software-defined Networking; Service Function Chain; Network Function Virtualization; service function placement; genetic algorithm

第一章 緒論 1
1.1 概要 1
1.2 研究動機 2
1.3 研究目的 3
1.4 論文架構 4
第二章 背景知識與相關研究 5
2.1 軟體定義網路相關技術 5
2.1.1 軟體定義網路與OpenFlow 5
2.1.2 Open Flow交換機與Open vSwitch 7
2.2 服務功能、服務功能鏈及網路功能虛擬化技術 8
2.2.1 服務功能與服務功能鏈 8
2.2.2 SFC Encapsulation 13
2.2.3 Network Service Header 17
2.2.4 網路功能虛擬化的市場趨勢 20
2.3 服務功能鏈部署策略 22
2.3.1 服務功能鏈部署問題 22
2.3.2 混合式NFV環境部署 26
2.4 基因演算法 27
2.5 相關文獻比較 33
第三章 研究方法 36
3.1 系統架構與設計 36
3.1.1 SFF OVS Agent模組 39
3.1.2 NSHKSF模組 40
3.1.3 Netlink Client & iproute模組 42
3.1.4 SF instance Agent 模組 42
3.1.5 Cloud Orchestrator模組 43
3.1.6 SF Placement simulator模組 43
3.1.7 OpenFlow Control模組 44
3.1.8 SFC Composition模組 46
3.1.9 Web Front-end模組 46
3.1.10 Web Back-end模組 47
3.1.11 Json API Provider模組 48
3.2 系統運作流程與機制 48
3.2.1 系統假設與定義 49
3.2.2 資料符號表 52
3.2.3 NSHSFC運作流程 57
3.2.4 GASFP運作流程 62
3.3 系統實作 71
第四章 實驗與討論 75
4.1 情境一：服務功能雲端平台測試與NSHSFC分析 75
4.1.1 實驗一：服務功能雲端平台測試 76
4.1.2 實驗二：NSHSFC訊務流導向驗證 81
4.1.3 實驗三：NSHSFC訊務流導向效能分析 84
4.1.4 實驗四：NSHSFC OVS flow entry消耗分析 86
4.2 情境二：GASFP於純NFV環境部署成本及延遲 88
4.2.1 實驗五：當服務功能要求僅包含單一虛擬服務功能 89
4.2.2 實驗六：當服務功能要求包含多虛擬服務功能 93
4.3 情境三：GASFP於混和式NFV環境部署成本及延遲 96
4.3.1 實驗七：當服務功能要求僅包含單一虛擬或硬體服務功能 97
4.3.2 實驗八：當服務功能要求混和多虛擬與硬體服務功能 100
4.4 情境四：GASFP於商用服務功能雲端平台效能分析 104
4.4.1 實驗九：服務功能要求接受率及部署成本分析 104
4.4.2 實驗十：商用服務功能雲端平台之營收分析 106
4.4.3 實驗十一：GASFP演算法運算效能 109
第五章 結論與未來研究方向 110
5.1 結論 110
5.2 研究限制 111
5.3 未來方向 111
參考文獻 114

[1].Internet Engineering Task Force (IETF). "Service Function Chaining (SFC) Architecture." RFC7665.
Available: https://tools.ietf.org/html/rfc7665
[2].AT&T Corporation. "Network infrastructure made simple."
Available: https://www.business.att.com/content/productbrochures/network-function-virtualization-product-brief.pdf
[3].AT&T Corporation. "AT&T FlexWare Applications."
Available: https://www.business.att.com/content/productbrochures/flexware-applications-brief.pdf
[4].Internet Engineering Task Force (IETF). "Problem Statement for Service Function Chaining." RFC7498.
Available: https://www.rfc-editor.org/rfc/rfc7498.txt
[5].Khebbache, Selma, Makhlouf Hadji, and Djamal Zeghlache. "Scalable and cost-efficient algorithms for VNF chaining and placement problem." Innovations in Clouds, Internet and Networks (ICIN), 2017 20th Conference on. IEEE, 2017.
[6].Pham, Chuan, et al. "Traffic-aware and Energy-efficient vNF Placement for Service Chaining: Joint Sampling and Matching Approach." IEEE Transactions on Services Computing (2017).
[7].Jemaa, Fatma Ben, Guy Pujolle, and Michel Pariente. "QoS-aware VNF placement optimization in edge-central carrier cloud architecture." Global Communications Conference (GLOBECOM), 2016 IEEE. IEEE, 2016.
[8].Hirwe, Anish, and Kotaro Kataoka. "LightChain: A lightweight optimisation of VNF placement for service chaining in NFV." NetSoft Conference and Workshops (NetSoft), 2016 IEEE. IEEE, 2016.
[9].Oechsner, Simon, and Andreas Ripke. "Flexible support of VNF placement functions in OpenStack." Network Softwarization (NetSoft), 2015 1st IEEE Conference on. IEEE, 2015.
[10].Breitgand, David, et al. "Network aware virtual machine and image placement in a cloud." Network and Service Management (CNSM), 2013 9th International Conference on. IEEE, 2013.
[11].Moens, Hendrik, and Filip De Turck. "VNF-P: A model for efficient placement of virtualized network functions." Network and Service Management (CNSM), 2014 10th International Conference on. IEEE, 2014.
[12].Internet Engineering Task Force (IETF). "Network Service Header." Draft-ietf-sfc-nsh-12.
Available: https://www.ietf.org/id/draft-ietf-sfc-nsh-12.txt
[13].Cisco Systems, Inc. "Cisco Visual Networking Index:Forecast and Methodology, 2015–2020". White-Paper-
Available: http://www.cisco.com/c/dam/en/us/solutions/collate ral/service-provider/visual-networking-index-vni/complete-white-paper-c11-481360.pdf
[14].N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker and J. Turner, "OpenFlow: Enabling Innovation in Campus Networks", SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, p. 69, 2008.
[15].Open Networking Foundation (ONF). "OpenFlow Switch Specification- Version 1.5.0 (Protocol version 0x06)." ONF TS-020.
Available: https://tools.ietf.org/html/rfc1701
[16].O.E.-E. Ferkouss, R.-B. Ali, Y. Lemieux, C. Omar, "Performance model for mapping processing tasks to OpenFlow switch resources." Proceedings of the IEEE International Conference on Communications, pp.1476-1481, Jun. 2012.
[17].S. Yeganeh, A. Tootoonchian and Y. Ganjali. "On scalability of software-defined networking." IEEE Communications Magazine, vol. 51, no. 2, pp. 136-141, 2013.
[18].European Telecommunications Standards Institute (ETSI). "Network Functions Virtualisation (NFV) Architectural Framework.".
Available:http://www.etsi.org/deliver/etsi_gs/nfv/001_099/002/01.01.01_60/gs_nfv002v010101p.pdf
[19].Bifulco, Roberto, Anton Matsiuk, and Alessio Silvestro. "Ready-to-deploy service function chaining for mobile networks." NetSoft Conference and Workshops (NetSoft), 2016 IEEE. IEEE, 2016.
[20].周新堯, “基於SDN的網路功能資源管理與服務功能鏈.”, Jul. 2015
[21].P. Quinn and J. Guichard, "Service Function Chaining: Creating a Service Plane via Network Service Headers", Computer, vol. 47, no 11, pp. 38-44, 2014.
[22].Internet Engineering Task Force (IETF). "Virtual eXtensible Local Area Network (VXLAN): A Framework for Overlaying Virtualized Layer 2 Networks over Layer 3 Networks." RFC7348.
Available: https://tools.ietf.org/html/rfc7348
[23].Internet Engineering Task Force (IETF). "Generic Routing Encapsulation (GRE)." RFC1701.
Available: https://tools.ietf.org/html/rfc1701
[24].Li, Xin, and Chen Qian. "The virtual network function placement problem." Computer Communications Workshops (INFOCOM WKSHPS), 2015 IEEE Conference on. IEEE, 2015.
[25].Richard M. Karp (1972). "Reducibility Among Combinatorial Problems." In R. E. Miller and J. W. Thatcher. "Complexity of Computer Computations." New York: Plenum. pp. 85–103.
[26].Wikipedia, "Set cover problem", 2017. [Online]. Available: https://en.wikipedia.org/wiki/Set_cover_problem. [Accessed: 21- Jul- 2017].
[27].Chi, Po-Wen, Yu-Cheng Huang, and Chin-Laung Lei. "Efficient NFV deployment in data center networks." Communications (ICC), 2015 IEEE International Conference on. IEEE, 2015.
[28].Leivadeas, Aris, et al. "Resource Management and Orchestration for a Dynamic Service Chain Steering Model." Global Communications Conference (GLOBECOM), 2016 IEEE. IEEE, 2016.
[29].Wikipedia, "Genetic algorithm", 2017. [Online]. Available: https://en.wikipedia.org/wiki/Genetic_algorithm [Accessed: 21- Jul- 2017].
[30].Online Document, "An Introduction to Genetic Algorithms." 2014. [Online]. Available:
https://www.whitman.edu/Documents/Academics/Mathematics/2014/carrjk.pdf
[Accessed: 24- Jul- 2017].
[31].Herrera, Francisco, Manuel Lozano, and Jose L. Verdegay. "Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis." Artificial intelligence review 12.4 (1998): 265-319.
[32].Online Document, "The Genetic Algorithm – Explained." 2017. [Online]. Available:
http://techeffigytutorials.blogspot.tw/2015/02/the-genetic-algorithm-explained.html [Accessed: 21- Jul- 2017].
[33].Detorakis, Zacharias, and George Tambouratzis. "Introduction of a sectioned genetic algorithm for large scale problems." Bio-Inspired Models of Network, Information and Computing Systems, 2007. Bionetics 2007. 2nd. IEEE, 2007.
[34].Cao, Jiuyue, et al. "VNF Placement in Hybrid NFV Environment: Modeling and Genetic Algorithms." Parallel and Distributed Systems (ICPADS), 2016 IEEE 22nd International Conference on. IEEE, 2016.
[35].Github. "About - GitHub."
Available: https://github.com/about
[36].Yyang13. "ovs_nsh_patches."
Available: https://github.com/yyang13/ovs_nsh_patches
[37].Ryo Nakamura. "nshkmod."
Available: https://github.com/upa/nshkmod
[38].Vanessa Wang, Frank Salim, and Peter Moskovits "The Definitive Guide to HTML5 WebSocket."
Available: http://dl.finebook.ir/book/6a/10947.pdf
[39].visjs.org "About - vis.js."
Available: http://visjs.org/#contribute
[40].Internet Engineering Task Force (IETF). "Multi-domain Service Forwarding For NSH." draft-li-sfc-nsh-multi-domain-02.
Available: https://www.ietf.org/id/draft-li-sfc-nsh-multi-domain-02.txt