軟體定義網路(Software Defined Network, SDN) 有別於以往傳統網路中，封包從來源傳輸到目的的過程中，封包的轉接行為是逐條獨立控制的分散式控制，軟體定義網路則是透過把實體設備及虛擬機中的控制層(Control Plane) 剝離出來，放置至一個統一的外部控制器(Controller)，由此控制器透過指令集中管理轉接路徑上的所有設備，控制器掌管網路中的所有必須資訊。網路中的中間件(Middlebox) 如：防火牆、解密器、負載平衡器…等，是功能性的硬體設備，在雲端及企業網路中是不可或缺的部份，但其價錢昂貴且難以維護。網路功能虛擬化(Network Function Virtualization, NFV) 推動網路功能虛擬化，將功能性硬體設備遷移到虛擬機上，旨在提高部屬靈活性，降低資本支出(Capital Expenditure, CAPEX)。
　　當服務要求抵達網路，可能需要遍歷一組有順序的功能服務，稱作服務功能鏈(Service Function Chain, SFC)，例如：需先通過防火牆，再通過加密器，最後通過解密器，若這些功能服務的順序交換，將影響整個服務要求的正確性。如何在網路中有效率的規劃服務功能鏈服務要求的路徑，是我們想解決的問題。最主要的挑戰是，維持服務功能鏈所要求功能順序以及考慮當下網路狀態。在維持服務功能鏈要求功能順序下，該分配給哪些虛擬機來完成服務，並且依照網路狀選擇較佳的轉發路徑，在期限內完成服務。
　　本論文中，我們提出一個可以解決上述兩項主要挑戰，並同時顧及演算法執行時間的方法，主要的精神是將網路拓樸以分層圖來表示，此分層圖會依照每一個新進服務功能鏈的條件，以及當下網路狀態做動態的變動，以原本的拓樸為基底，透過良好的分層設計，再利用Dijkstra最短路徑演算法來選擇最佳路徑，其最終目標為在執行時間最快的狀態下達到最高成功率。

　　Software-defined network(SDN) is shifting data communication in network toward more centralized control. The controller manages all necessary information and decides the transit path through commands. Middleboxes such as firewalls, decryptors, load balancers, etc., are functional hardware devices that are　indispensable in the cloud　and in corporate networks, but are expensive and difficult to maintain.

The availability of virtual machines enables dynamic placement of virtual network functions(VNFs) on demand, it can reduce a large number of manual configuration processes, introduce flexibility, and increase deployment efficiency. Service requirements may need more than one VNF. Instead, it may need to traverse a set of sequential functional services called Service Function Chain (SFC). For example: first through the firewall, then through the encryption device, and finally through the decryption device, if these functional services are unordered, it will affect　the correctness of the entire service requirements.

A key challenge is to efficiently route service function chains and place processing functions in a network under operational constraints. We must overcome two challenges: (1) determining a flow path that traverses suitable processing nodes in the correct order to meet the requirements of a given service chain, and (2) considering network load and other dynamic characteristics when routing through 　existing VNFs.

We present a method to solve the node-constrained service chain routing problem in a software-defined network. The main idea is to transform the network representation to a layered graph that considers processing steps and allows the use of conventional shortest path algorithms, such as Dijkstra’s algorithm, to solve the problem. We are not only pursuing the high efficiency of acceptance ratio, but also 　taking into account the execution time of the algorithm.

參 考 文 獻

[1] V. Eramo, A. Tosti, and E. Miucci, “Server resource dimensioning and routing of service function chain in NFV network architectures,” Journal of Electrical and Computer Engineering, vol. 2016, pp. 1–12, Feb. 2016.
[2] R. Bruschi, F. Davoli, P. Lago, A. Lombardo, C. Lombardo, C. Rametta, and G. Schembra, “An SDN/NFV platform for personal cloud services,” IEEE Transactions on Network and Service Management archive, vol. 14, no. 4, pp. 1143–1156, December 2017.
[3] A. Gushchin, A. Walid, and A. Tang, “Scalable routing in SDN enabled networks with consolidated middleboxes,” in Proceedings of the 2015 ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization, pp. 55–60, 2015.
[4] M. F. Bari, S. R. Chowdhury, R. Ahmed, and R. Boutaba, “On orchestrating virtual network functions in nfv,” CoRR abs/1503.06377, 2015.
[5] R. Mijumbi, J. Serrat, J. L. Gorricho, N. Bouten, F. D. 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, First quarter 2016.
[6] R. Yu, G. Xue, V. T. Kilari, and X. Zhang, “Network function virtualization in the multitenant cloud,” IEEE Network, vol. 29, no. 3, pp. 42–47, May-June 2015.
[7] R. Mijumbi, J. Serrat, J. L. Gorricho, S. Latr´e, M. Charalambides, and D. Lopez, “Management and orchestration challenges in network functions virtualization,” IEEE Communications Magazine, vol. 54, no. 1, pp. 98–105, Jan. 2016.
[8] H. A. Alameddine, S. Sebbah, and C. Assi, “On the interplay between network function mapping and scheduling in VNF-based networks: A column generation approach,” IEEE Transactions on Network and Service Management, pp. 860–874, 27 Sep 2017.
[9] K. I. Choi, B. C. Lee, “Tenant based dynamic processor mapping in the cloud network function virtualization system,” 2016 18th International Conference on Advanced Communication Technology (ICACT), pp.592–595, 2016.
[10] Y. Xu, V. P. Kafle, “Reliable service function chain provisioning in software-defined networking,” 2017 13th International Conference on Network and Service Management (CNSM), pp. 1–4, 2017.
[11] P. Quinn, and T. Nadeau, “Problem statement for service function chaining,” IETF RFC 7498, pp. 1–13, April 2015.
[12] Sophia-Antipolis Cedex, “ETSI GS NFV 003 v1.2.1: Network functions vir-tualization (nfv), terminology for main concepts in nfv,” Network Functions Virtualization (NFV) ETSI Industry Specification Group (ISG), pp. 1–13 2014.
[13] N. Huin, A. Tomassilli, F. Giroire, B. Jaumard, “Energy-efficient service function chain provisioning,” IEEE/OSA Journal of Optical Communications and Networking, vol. 10, no. 4, pp. 114–124, 22 March 2018.
[14] Gartner, “Information technology (it) spending on software worldwide,” 2017.
[15] C. Ouyang, Y. Wei, S. Leng, and Y. Chen, “Service chain performance optimization based on middlebox deployment,” 2017 IEEE 17th International Con-ference on Communication Technology (ICCT), pp. 1947–1952, Oct. 2017.
[16] A. Basta, A. Blenk, K. Hoffmann, H. J. Morper, M. Hoffmann, and W. Kellerer, “Towards a cost optimal design for a 5G mobile core network based on SDN and NFV,” IEEE Transactions on Network and Service Management, vol. 14, no. 4, pp. 1061–1075, Dec 2017.
[17] S. Abdelwahab, B. Hamdaoui, M. Guizani, and T. Znati, “Network function virtualization in 5G,” IEEE Communications Magazine, vol. 54, no. 4, pp. 84–91, April 2016.
[18] Q. Duan, N. Ansari, and M. Toy, “Software-defined network virtualization: an architectural framework for integrating SDN and NFV for service provisioning in future networks,” IEEE Network, vol. 30, no. 5, pp. 10–16, September-October 2016.
[19] A. A. Mohammed, M. Gharbaoui, B. Martini, F. Paganelli, and P. Castoldi, “SDN controller for network-aware adaptive orchestration in dynamic service chaining,” 2016 IEEE NetSoft Conference and Workshops (NetSoft), pp. 126–130, 2016.
[20] R. Laufer, M. Gallo, D. Perino, and A. Nandugudi, “CliMB: Enabling network function composition with click middleboxes,” in Proceedings of the 2016 workshop on Hot topics in Middleboxes and Network Function Virtualization (HotMIddlebox '16), New York, NY, USA: ACM, pp. 50–55, August 2016.
[21] G. Baldoni, A. Lombardo, M. Melita, S. Micalizzi, C. Rametta, and A. Vassallo, “An emulation framework for SDN-NFV based services,” in Proceedings of the Second International Conference on Internet of things, Data and Cloud Computing (ICC '17), New York, NY, USA: ACM, 2017.
[22] R. Mijumbi, J. Serrat, J. L. Gorricho, N. Bouten, F. D. Turck, and S. Davy, “Design and evaluation of algorithms for mapping and scheduling of virtual network functions,” Proceedings of the 2015 1st IEEE Conference on Network Softwarization (NetSoft), pp. 1–9, 2015.
[23] B. Han, V. Gopalakrishnan, L. Ji, and S. Lee, “Network function virtualizetion: Challenges and opportunities for innovations,” IEEE Communications Magazine, vol. 53, no. 2, pp. 90–97, Feb. 2015.
[24] B. Pfaff, J. Scherer, D. Hock, N. Gray, T. Zinner, P. Tran-Gia, R. Durner, W. Kellerer, and C. Lorenz, “SDN/NFV-enabled security architecture for finegrained policy enforcement and threat mitigation for enterprise networks,” in Proceedings of the SIGCOMM Posters and Demos (SIGCOMM Posters and Demos '17), New York, NY, USA: ACM, pp.15–16, 2017.
[25] A. M. Medhat, T. Taleb, A. Elmangoush, G. A. Carella, S. Covaci, and T. Magedanz, “Service function chaining in next generation networks: State of the art and research challenges,” IEEE Commun. Mag., vol. 55, no. 2, pp. 216–223, Feb. 2017.
[26] Y. Li, F. Zheng, M. Chen, and D. Jin, “A unified control and optimization framework for dynamical service chaining in software-defined NFV system,” IEEE Wireless Commun., vol. 22, no. 6, pp. 15–23, Dec. 2015.
[27] J. Halpern and C. Pignataro, “Service function chaining (SFC) architecture,” document RFC 7665, Oct. 2015.
[28] W. Haeffner, J. Napper, M. Stiemerling, D. Lopez, and J. Uttaro, “Service function chaining use cases in mobile networks,” Oct. 2016.
[29] J. G. Herrera and J. F. Botero, “Resource Allocation in NFV: A Comprehensive Survey,” IEEE Transactions On Network And Service Management, Vol. 13, No. 3, September 2016.
[30] N. E. Khoury, S. Ayoubi, and C. Assi, “Energy-Aware Placement and Scheduling of Network Traffic Flows with Deadlines on Virtual Network Functions,” 2016 5th IEEE International Conference on Cloud Networking, pp. 89–94, 2016.
[31] B. A. A. Nunes, M. Mendonca, X.-N. Nguyen, K. Obraczka, and T. Turletti, “A survey of software-defined networking: Past, present, and future of programmable networks,” IEEE Commun. Surveys Tuts., vol. 16, no. 3, pp. 1617–1634, 3rd Quart., 2014.
[32] Y. Xie, Z. Liu, S. Wang, Y. Wang, “Service Function Chaining Resource Allocation: A Survey,” arXiv:1608.00095 [cs.NI], 30 Jul 2016.
[33] F. Yue, “Network Functions Virtualization - Everything Old Is New Again. Techinical White Paper,” F5 Networks, Inc., Tech. Rep., February 2014.
[34] W. Xia, Y. Wen, C. H. Foh, D. Niyato, and H. Xie, “A Survey on Software-Defined Networking,” Communications Surveys & Tutorials, IEEE Journals & Magazines, 2015.
[35] A. Dwaraki and T. Wolf, “Adaptive Service-Chain Routing for Virtual Net-work Functions in Software-Defined Networks,” ACM SIGCOMM 2016, pp. 32–37, August 22–26, 2016.
[36] F. Bannour, S. Souihi, and A. Mellouk, “Distributed SDN Control: Survey, Taxonomy, and Challenges,” IEEE Communications Surveys & Tutorials, Vol. 20, No. 1, First Quarter 2018.
[37] H. Kim and N. Feamster, “Improving network management with software defined networking,” IEEE Commun. Mag., vol. 51, no. 2, pp. 114–119, Feb. 2013.
[38] M. F. Bari et al., “Data center network virtualization: A survey,” IEEE Com-mun. Surveys Tuts., vol. 15, no. 2, pp. 909–928, 2nd Quart., 2013.
[39] Q. Zhang, L. Cheng, and R. Boutaba, “Cloud computing: State-of-theart and research challenges,” J. Internet Services Appl., vol. 1, no. 1, pp. 7–18, 2010.
[40] M. A. Sharkh, M. Jammal, A. Shami, and A. Ouda, “Resource allocation in a network-based cloud computing environment: Design challenges,” IEEE Commun. Mag., vol. 51, no. 11, pp. 46–52, Nov. 2013.
[41] W. Xu, Y. Jiang, and C. Zhou, “Problem Statement of Network Functions Virtualization Model. Internet-Draft, draft-xjz-nfv-modelproblem-statement-00,” Active Internet-Draft, IETF Secretariat, Tech. Rep., September 2013.
[42] SDNlib library. [Online]. Available : http://sndlib.zib.de/home.action .
[43] Topology Zoo. [Online]. Available : http://www.topology-zoo.org .