臺灣博碩士論文加值系統

在傳統的網路中，交換器裏頭的控制層和傳輸層是被綁定住的，流量只能遵
循網路製造商已經寫好的繞送規則進行繞送。交換器裏頭的繞送規則無法進行修
改，所有的封包只能按造最小路徑進行繞送，顯而易見的，在傳統網路環境中有
一些明顯的缺點，那就是無法即時的針對當時的網路環境進行繞送規則的修改。
因此，軟體定義網路即是把控制層與資料層分開，在 SDN switch 上保留資料層進
行封包的傳輸，將控制層統一由名為 SDN Controller 進行管理，SDN Controller 知
道網路拓譜中的所有資訊，藉此可以即時的依照當時的網路狀況，傳送合適的繞
送規則給各個 SDN swtich 以優化整個網路
另一項技術為網路功能虛擬化，NFV 將網路功能（例如: 防火牆、入侵預防
系統、深度封包解析）實作為軟體並在虛擬機上執行提供服務。在過去的網路中，
網路功能通常是一台名為 Middlebox 的硬體設備提供服務，而每一種類型的功能
都有各自不同的硬體設備，要價不斐並且不易維護。藉由網路功能虛擬化技術藉
此建構一個更加彈性的網路環境。藉由軟體定義網路和網路功能虛擬化兩種技
術，在未來新的網路環境中，封包的繞送會變得更加有效率，不需要昂貴的硬體
設備也能提供網路功能，不但降低了營運成本，遷移網路功能到合適的位置變得
容易。
本論文在軟體定義網路與網路功能虛擬化的環境下，考量了虛擬化網路功能
彼此間的執行優先順序，提出一個為服務功能鏈的網路請求尋找一條最佳繞送路
經之演算法，並針對此演算法再做進一步的優化，減少計算最佳路徑所需要的執
行時間，最後因應實際的網路狀況，將虛擬化網路功能的遷移納入考量，將最佳
路徑演算法延伸至可以處理在虛擬化網路功能的開啟數量有限時，如何選擇較佳
的開啟位置來執行網路功能。

In traditional networks, the control plane and the data plane are bundled into one
switch. The flow of packets are forwarded based on the rules that have been decided since
switches were made by the manufacturers. The rules that in switches cannot be modified
and it forward packets following the shortest path algorithm generally. Obviously, there
are some disadvantages in traditional networks. Traditional networks cannot change the
routing policy to encounter differnet situations.
Thus, there is an emerging paradigm named Software-Defined Networking (SDN)
that separate the control plane from the data plane. By breaking vertical integration, SDN
separate the networks control logic from the underlying routers and switches, promoting (logical) centralization of network control, and introducing the ability to program the
network.
There is another promising technology named network function virtualization (NFV).
NFV implements network functions (e.g., firewalls, intrusion detection systems (IDSs),
deep packet inspection (DPI)) as software running in a virtual machine. In the past, network functions are typically made by dedicated hardware devices named middlebox which
are very expensive and hard to manage. NFV reduce the cost of implementing network
functions and provide a more flexible way to construct the Internet.
Underpinned by the NFV technique, Software-Defined Networking (SDN) that separates the control plane from the data plane can be utilized to enable inexpensive and flexible implementation of network functions as software components running in Virtual Machines (VMs), rather than expensive and hard-to-manage hardware middleboxes. Therefore, routing algorithm for NFV enablement within SDN that minimum the operation cost
or maximum the throughput may be useful in this new architecture.

論文摘要 III
Abstract IV
目錄 V
圖目錄 VII
表目錄 IX
1 緒論 1
1.1 研究背景 1
1.2 論文目標 2
1.3 論文架構 3
2 相關研究 4
2.1 軟體定義網路（Software Defined Network, SDN） 5
2.2 網路功能虛擬化（Network Function Virtualization, NFV） 6
2.3 服務功能鏈（Service Function Chain, SFC） 6
3 系統模型與問題描述 8
3.1 系統模型 8
3.2 問題描述 9
4 基本的最佳路徑演算法 11
4.1 演算法概念 11
4.2 Constructing NFAG 11
4.3 NFV-enabled Routing Path Selection Algorithm 13
4.4 Constructing Advanced NFAG 16
4.5 Advanced NFV-enabled Routing Path Selection Algorithm 18
5 延伸的最佳路徑演算法 20
5.1 演算法概念 20
5.2 Routing Path Selection with VNFs Migration Algorithm 20
6 實驗結果與分析 23
6.1 實驗環境設定 23
6.1.1 拓樸設定 23
6.1.2 虛擬網路功能 24
6.2 實驗結果 25
6.2.1 服務功能鏈中 VNFs 個數影響 25
6.2.2 不同排列個數的影響 27
6.2.3 VNF 遷移的模擬結果 28
7 結論與後續工作 30
參考文獻 31

[1] D. Kreutz, F. M. V. Ramos, P. E. Veríssimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-defined networking: A comprehensive survey,” Proceedings of the IEEE, vol. 103, no. 1, pp. 14–76, Jan 2015.
[2] D. R. Lopez, “Network functions virtualization: Beyond carrier-grade clouds,” in OFC 2014, March 2014, pp. 1–18.
[3] J. Gil Herrera and J. F. Botero, “Resource allocation in nfv: A comprehensive survey,” IEEE Transactions on Network and Service Management, vol. 13, no. 3, pp.
518–532, Sep. 2016.
[4] j. Pei, P. Hong, K. Xue, and D. Li, “Resource aware routing for service function chains in sdn and nfv-enabled network,” IEEE Transactions on Services Computing, pp. 1–1, 2018.
[5] W. Ma, O. Sandoval, J. Beltran, D. Pan, and N. Pissinou, “Traffic aware placement of interdependent nfv middleboxes,” in IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, May 2017, pp. 1–9.
[6] B. Han, V. Gopalakrishnan, L. Ji, and S. Lee, “Network function virtualization: Challenges and opportunities for innovations,” IEEE Communications Magazine, vol. 53, no. 2, pp. 90–97, Feb 2015.
[7] Z. Xu, W. Liang, M. Huang, M. Jia, S. Guo, and A. Galis, “Approximation and online algorithms for nfv-enabled multicasting in sdns,” in 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), June 2017, pp. 625–634.
[8] L. Kou, G. Markowsky, and L. Berman, “A fast algorithm for steiner trees,”
Acta Informatica, vol. 15, no. 2, pp. 141–145, Jun 1981. [Online]. Available:
https://doi.org/10.1007/BF00288961
[9] M. Jia, W. Liang, M. Huang, Z. Xu, and Y. Ma, “Throughput maximization of
nfv-enabled unicasting in software-defined networks,” in GLOBECOM 2017 - 2017
IEEE Global Communications Conference, Dec 2017, pp. 1–6.
[10] ——, “Routing cost minimization and throughput maximization of nfv-enabled unicasting in software-defined networks,” IEEE Transactions on Network and Service Management, vol. 15, no. 2, pp. 732–745, June 2018.
[11] F. Carpio, W. Bziuk, and A. Jukan, “Replication of virtual network functions: Optimizing link utilization and resource costs,” in 2017 40th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), May 2017, pp. 521–526.
[12] C. Pham, N. H. Tran, S. Ren, W. Saad, and C. S. Hong, “Traffic-aware and energyefficient vnf placement for service chaining: Joint sampling and matching approach,” IEEE Transactions on Services Computing, pp. 1–1, 2018.
[13] M. Chen, S. C. Liew, Z. Shao, and C. Kai, “Markov approximation for combinatorial network optimization,” in 2010 Proceedings IEEE INFOCOM, March 2010, pp. 1–9.
[14] “Citrix cloudbridge,”
https://www.citrix.com/content/dam/citrix/enus/documents/
products-solutions/cloudbridge-technical-overview.pdf.
[15] M. J. Miller, B. Vucetic, and L. Berry, Satellite communications: mobile and fixed services. Springer Science & Business Media, 1993.
[16] 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, pp. 69–74, Mar. 2008. [Online].
Available: http://doi.acm.org/10.1145/1355734.1355746
[17] R. Mijumbi, J. Serrat, J. Gorricho, N. Bouten, F. De Turck, and R. Boutaba, “Network function virtualization: State-of-the-art and research challenges,” IEEE Communications Surveys Tutorials, vol. 18, no. 1, pp. 236–262, Firstquarter 2016.
[18] B. Yi, X. Wang, K. Li, S. k. Das, and M. Huang, “A comprehensive survey
of network function virtualization,” Computer Networks, vol. 133, pp. 212 –
262, 2018. [Online]. Available: http://www.sciencedirect.com/science/article/pii/
S1389128618300306
[19] “Abilene backbone,” http://abilene.internet2.edu