臺灣博碩士論文加值系統

隨著 NFV 與 SFC 的出現，網路管理與流量工程更靈活與敏捷。由於序列 SFC 的特 性，延遲時間會隨折網路功能個數呈現在成長，為了解決這個議題，最近提出了網路 功能平行化的概念，使得獨立的功能可以同時運作。然而現有的方法中都假設網路功 能必須安裝在同一台實體機器上，如此一來可以降低平行成本。如今大多數的網路， 都以分散網路功能來實現負載平衡。我們提出了部分平行服務鏈，在考量功能部署與 平行所增加的而外成本後，只平行確實可以減少延遲時間的服務功能，而我們開發兩 種為了達到最小話延遲時間的設計，窮舉部分平行服務串以及功能實例的配置。我們 的模擬中也證明了，部分平行服務鏈在任何情況下都優於序列與完全平行的服務串。 整理來說，針對序列服務鏈與完全平行的情況，分別減少的延遲時間可以分別提升 47.2% 以及 35.2%。

The emergence of Network Function Virtualization (NFV) and Service Function Chaining (SFC) together enable flexible and agile network management and traffic engineering. Due to the sequential execution nature of SFC, the latency would grow linearly with the number of functions. To resolve this issue, function parallelization has recently been proposed to en- able independent functions to work simultaneously. Existing solutions, however, assume all the function instances are installed in the same physical machine and, thus, can be parallelized with only a little overhead. Nowadays, most of the networks deploy function instances in distributed servers for load balancing, parallelization across different servers would, in fact, introduce a non- negligible cost of duplicating or merging packets. Hence, in this work, we propose PPC (Partial Parallel Chaining), which only parallelizes functions if parallelization can indeed reduce the latency after considering function placement and the required additional parallelization cost. To this end, we design two schemes, partial parallelism enumeration and instance assignment to identify the optimal partial parallelism that minimizes the latency. Our simulation results show that PPC effectively adapts the degree of parallelism and, hence, outperforms both sequential chaining and full parallelism in any general scenario. Overall, the latency reduction can be up to 47.2% and 35.2%, respectively, as compared to sequential chaining and full parallelism.

摘要................................. ............ i
Abstract............................... ............ ii Acknowledgement..................................... iii
Table of Contents ..................................... iv
List of Figures ....................................... vi
1 Introduction....................................... 1
2 RelatedWork...................................... 4
2.1 Routing and Admission Control ......................... 4
2.2 NFPlacement................................... 4
2.3 LatencyReduction ................................ 5
3 Background and Motivation.............................. 6
3.1 NFVandSFC................................... 6
3.2 NetworkFunctionParallelism .......................... 6
3.3 MotivatingExamples............................... 8
4 PartialParallelChaining................................ 11
4.1 ProblemStatement ................................ 11
4.2 PartialParallelismEnumeration ......................... 13
4.2.1 ClusterSizeEnumeration ........................ 14
4.2.2 NF-ClusterAssignment ......................... 15
4.3 Joint Instance and RouteAssignment....................... 18
4.3.1 LayerGraphConstruction ........................ 18
4.3.2 Link latency derivation.......................... 20
4.4 ComplexityAnalysis ............................... 23
5 PerformanceEvaluation................................ 24
5.1 Impact of Number of Instances per Server .................... 24
5.2 Impact of Heterogeneous Delays......................... 25
5.3 Impact o fVariousDelays............................. 27
6 Conclusion ....................................... 30
References ......................................... 31

[1] A. Gember-Jacobson, R. Viswanathan, C. Prakash, R. Grandl, J. Khalid, S. Das, and A. Akella, “OpenNF: Enabling innovation in network function control,” in ACM SIG- COMM, 2014.
[2] J. M. Halpern and C. Pignataro, “Service Function Chaining (SFC) Architecture,” RFC 7665, Oct. 2015. [Online]. Available: https://rfc-editor.org/rfc/rfc7665.txt
[3] D.Bhamare,R.Jain,M.Samaka,andA.Erbad,“ASurveyonServiceFunctionChaining,” Journal of Network and Computer Applications, vol. 75, no. C, pp. 138–155, Nov. 2016.
[4] A. Dwaraki and T. Wolf, “Adaptive service-chain routing for virtual network functions in software-defined networks,” in ACM HotMiddlebox, 2016.
[5] B. L. B. J. Gamal Sallam, GAgan R. Gupta, “Shortest path and maximum flow problems under service function chaining constraints,” in IEEE INFOCOM, 2018.
[6] H. Huang, S. Guo, J. Wu, and J. Li, “Service chaining for hybrid network function,” IEEE Transactions on Cloud Computing, 2018 (accepted).
[7] Z.Cao,M.Kodialam,andT.V.Lakshman,“Trafficsteeringinsoftwaredefinednetworks: Planning and online routing,” SIGCOMM Computer Communication Review, vol. 44, no. 4, Aug. 2014.
[8] J.-J. Kuo, S.-H. Shen, H. Kang, D.-N. Yang, M.-J. Tsai, and W.-T. Chen, “Service chain embedding with maximum flow in software defined network and application to the next- generation cellular network architecture,” in IEEE INFOCOM, 2017.
[9] X. Fei, F. Liu, H. Xu, and H. Jin, “Adaptive VNF scaling and flow routing with proactive demand prediction,” in IEEE INFOCOM, 2018.
[10] Y. Sang, B. Ji, G. R. Gupta, X. Du, and L. Ye, “Provably efficient algorithms for joint placement and allocation of virtual network functions,” CoRR, vol. abs/1702.01154, 2017.
[11] S.Mehraghdam,M.Keller,andH.Karl,“Specifyingandplacingchainsofvirtualnetwork functions,” CoRR, vol. abs/1406.1058, 2014.
[12] Y. Zhang, N. Beheshti, L. Beliveau, G. Lefebvre, R. Manghirmalani, R. Mishra, R. Pat- neyt, M. Shirazipour, R. Subrahmaniam, C. Truchan, and M. Tatipamula, “StEERING: A software-defined networking for inline service chaining,” in IEEE ICNP, 2013.
[13] T.-W. Kuo, B.-H. Liou, K. C.-J. Lin, and M.-J. Tsai, “Deploying chains of virtual network functions: On the relation between link and server usage,” IEEE/ACM Transactions on Networking, vol. 26, no. 4, pp. 1562–1576, 2018.
[14] D. Li, P. Hong, K. Xue, and j. Pei, “Virtual network function placement considering re- source optimization and SFC requests in cloud datacenter,” IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 7, pp. 1664–1677, July 2018.
[15] R. Guerzoni et al., in SDN and OpenFlow World Congress, 2012.
[16] C. Sun, J. Bi, Z. Zheng, H. Yu, and H. Hu, “NFP: Enabling network function parallelism
in NFV,” in ACM SIGCOMM, 2017.
[17] M. Huang, W. Liang, Z. Xu, M. Jia, and S. Guo, “Throughput maximization in software- defined networks with consolidated middleboxes,” in Local Computer Networks (LCN), Nov 2016, pp. 298–306.
[18] M. A. Tahmasbi Nejad, S. Parsaeefard, M. A. Maddah-Ali, T. Mahmoodi, and B. H. Kha- laj, “vSPACE: VNF simultaneous placement, admission control and embedding,” IEEE Journal on Selected Areas in Communications, vol. 36, no. 3, pp. 542–557, March 2018.
[19] Y.Ma,W.Liang,andZ.Xu,“Onlinerevenuemaximizationinnfv-enabledsdns,”inIEEE ICC, 2018.
[20] B. Addis, D. Belabed, M. Bouet, and S. Secci, “Virtual network functions placement and routing optimization,” in IEEE CloudNet, 2015.
[21] B. Li, K. Tan, L. L. Luo, Y. Peng, R. Luo, N. Xu, Y. Xiong, P. Cheng, and E. Chen, “ClickNP: Highly flexible and high performance network processing with reconfigurable hardware,” in ACM SIGCOMM, 2016.
[22] A. Panda, S. Han, K. Jang, M. Walls, S. Ratnasamy, and S. Shenker, “Netbricks: Taking the V out of NFV,” in ACM OSDI, 2016.
[23] J.Martins,M.Ahmed,C.Raiciu,V.Olteanu,M.Honda,R.Bifulco,andF.Huici,“ClickOS and the art of network function virtualization,” in USENIX NSDI, 2014.
[24] J. Hwang, K. K. Ramakrishnan, and T. Wood, “NetVM: High performance and flexible networking using virtualization on commodity platforms,” in USENIX NSDI, 2014.
[25] W. Zhang, G. Liu, W. Zhang, N. Shah, P. Lopreiato, G. Todeschi, K. Ramakrishnan, and T. Wood, “OpenNetVM: A platform for high performance network service chains,” in ACM HotMiddlebox, 2016.
[26] Intel, “Data plane development kit DPDK,” 2012. [Online]. Available: https: //www.dpdk.org
[27] X. Lin, D. Guo, Y. Shen, G. Tang, and B. Ren, “DAG-SFC: Minimize the embedding cost of SFC with parallel VNFs,” in ACM ISBN, 2018.
[28] R. Gandhi, H. H. Liu, Y. C. Hu, G. Lu, J. Padhye, L. Yuan, and M. Zhang, “Duet: Cloud scale load balancing with hardware and software,” in ACM SIGCOMM, 2014.
[29] S. M. C. C. S Kumar, M Tufail and S. Homma, “Chaining use cases in data centers,” in IETF SFC WG, 2015.
[30] Y. Zhang, B. Anwer, V. Gopalakrishnan, B. Han, J. Reich, A. Shaikh, and Z.-L. Zhang, “ParaBox: Exploiting parallelism for virtual network functions in service chaining,” in ACM SOSR, 2017.
[31] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” in ACM SIGCOMM, 2008.