臺灣博碩士論文加值系統

Software-Defined Network (SDN) is the next generation of networks and has been rapidly evolving in the recent decade. With the complicated network characteristic, a packet needs to go through a set of network middleware, forming a network chain to archive the demand. As a result, the latency has been increasing throughout these chains of Quality of Service (QoS). Moreover, it is always a burden for network engineers tried to minimize. Diverse methodologies have been proposing to routing through the set of chains, including offload function and specialized routing algorithm.

However, there is room for improvement with the engagement of the programmable switch, which is one way to offload the function faster and less painful by install the rule centralize with a large scale adjustment support. The representative of the programmable switch in this contribution is base on P4 language, a prominent language that big network companies jointly develop. In this paper, we propose 3 Algorithms as a strawman proposal for how to routing through a Service Function Chain (SFC) and reduce latency by using a P4 switch in the SDN environment. We demonstrate the feasibility of this approach through our test bench that virtualizes the dynamic change of network function in the P4 switch. Then we test it on a real topology simulation, which has a different characteristic to show its practicality of our proposed method.

Software-Defined Network (SDN) is the next generation of networks and has been rapidly evolving in the recent decade. With the complicated network characteristic, a packet needs to go through a set of network middleware, forming a network chain to archive the demand. As a result, the latency has been increasing throughout these chains of Quality of Service (QoS). Moreover, it is always a burden for network engineers tried to minimize. Diverse methodologies have been proposing to routing through the set of chains, including offload function and specialized routing algorithm.

However, there is room for improvement with the engagement of the programmable switch, which is one way to offload the function faster and less painful by install the rule centralize with a large scale adjustment support. The representative of the programmable switch in this contribution is base on P4 language, a prominent language that big network companies jointly develop. In this paper, we propose 3 Algorithms as a strawman proposal for how to routing through a Service Function Chain (SFC) and reduce latency by using a P4 switch in the SDN environment. We demonstrate the feasibility of this approach through our test bench that virtualizes the dynamic change of network function in the P4 switch. Then we test it on a real topology simulation, which has a different characteristic to show its practicality of our proposed method.

Table of contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Table of contents . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 P4 language . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Offload Function . . . . . . . . . . . . . . . . . . . . . . 6
3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1 Deploy a P4 Mininet . . . . . . . . . . . . . . . . . . . . 9
4.2 System Formation . . . . . . . . . . . . . . . . . . . . . . 10
5 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 11
6 The Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.1 Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . . 12
6.2 Adaptive Algorithm . . . . . . . . . . . . . . . . . . . . . 17
6.2.1 Topology Tranformation . . . . . . . . . . . . . . 18
6.2.2 Algorithm Design . . . . . . . . . . . . . . . . . 19
6.3 Tree Algorithm . . . . . . . . . . . . . . . . . . . . . . . 22
6.3.1 Algorithm Design . . . . . . . . . . . . . . . . . 23
7 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
7.1 Topology Generator . . . . . . . . . . . . . . . . . . . . . 29
7.2 Number of nodes test result. . . . . . . . . . . . . . . . . 30
7.3 SFC length test result. . . . . . . . . . . . . . . . . . . . . 33
7.4 P4 density test result. . . . . . . . . . . . . . . . . . . . . 35
8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

References
[1] R. Shah, M. Vutukuru, and P. Kulkarni, “Cuttlefish: Hierarchical sdn controllers with adaptive offload,”
in 2018 IEEE 26th International Conference on Network Protocols (ICNP), pp. 198–208,
IEEE, 2018.
[2] J. Yang, X. Yang, Z. Zhou, X. Wu, T. Benson, and C. Hu, “Focus: Function offloading from a controller
to utilize switch power,” in 2016 IEEE Conference on Network Function Virtualization and
Software Defined Networks (NFV-SDN), pp. 199–205, Nov 2016.
[3] G. Sallam, G. R. Gupta, B. Li, and B. Ji, “Shortest path and maximum flow problems under service
function chaining constraints,” in IEEE INFOCOM 2018-IEEE Conference on Computer Communications,
pp. 2132–2140, IEEE, 2018.
[4] A. Dwaraki and T. Wolf, “Adaptive service-chain routing for virtual network functions in softwaredefined
networks,” pp. 32–37, 08 2016.
[5] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco,
A. Vahdat, G. Varghese, et al., “P4: Programming protocol-independent packet processors,” ACM
SIGCOMM Computer Communication Review, vol. 44, no. 3, pp. 87–95, 2014.
[6] “https://p4.org/p4-spec/docs/P4-16-v1.0.0-spec.html, [Online; accessed 26-August-2019],” 2018.
[7] L. Yang, T. Anderson, R. Dantu, and R. Gopal, “Forwarding and control element separation (forces)
framework,” 05 2004.
[8] M. Casado, M. Freedman, J. Pettit, J. Luo, N. McKeown, and S. Shenker, “Ethane: Taking control of
the enterprise,” vol. 37, pp. 1–12, 10 2007.
[9] “Network functions virtualization_ introductory white paper,” 10 2012.
[10] D. Zhao, J. Ren, R. Lin, S. Xu, and V. Chang, “On orchestrating service function chains in 5g mobile
network,” IEEE Access, vol. 7, pp. 39402–39416, 2019.
[11] A. Farrel, “Recent developments in service function chaining (sfc) and network slicing in backhaul
and metro networks in support of 5g,” in 2018 20th International Conference on Transparent Optical
Networks (ICTON), pp. 1–4, July 2018.
[12] A. Mohammadkhan, S. Ghapani, G. Liu, W. Zhang, K. K. Ramakrishnan, and T. Wood, “Virtual
function placement and traffic steering in flexible and dynamic software defined networks,” in The
21st IEEE International Workshop on Local and Metropolitan Area Networks, pp. 1–6, April 2015.
[13] J. Costa-Requena, J. L. Santos, V. F. Guasch, K. Ahokas, G. Premsankar, S. Luukkainen, O. L. Prez,
M. U. Itzazelaia, I. Ahmad, M. Liyanage, M. Ylianttila, and E. M. de Oca, “Sdn and nfv integration in
generalized mobile network architecture,” in 2015 European Conference on Networks and Communications
(EuCNC), pp. 154–158, June 2015.
[14] A. Basta, W. Kellerer, M. Hoffmann, H. J. Morper, and K. Hoffmann, “Applying nfv and sdn to lte
mobile core gateways, the functions placement problem,” in Proceedings of the 4th Workshop on
All Things Cellular: Operations, Applications; Challenges, AllThingsCellular ’14, (New York, NY,
USA), pp. 33–38, ACM, 2014.
[15] J. Zhou, P. Hong, J. Pei, and D. Li, “Multi-task deep learning based dynamic service function chains
routing in sdn;nfv-enabled networks,” in ICC 2019 - 2019 IEEE International Conference on Communications
(ICC), pp. 1–6, May 2019.
[16] . Ogrodowczyk, B. Belter, and M. LeClerc, “Iot ecosystem over programmable sdn infrastructure for
smart city applications,” in 2016 Fifth European Workshop on Software-Defined Networks (EWSDN),
pp. 49–51, Oct 2016.
[17] C. Kim, A. Sivaraman, N. P. Katta, A. Bas, A. Dixit, and L. J. Wobker, “In-band network telemetry
via programmable dataplanes,” 2015.
[18] Q. Duan, Y. Yan, and A. V. Vasilakos, “A survey on service-oriented network virtualization toward
convergence of networking and cloud computing,” IEEE Transactions on Network and Service Management,
vol. 9, pp. 373–392, December 2012.
[19] A. Younis and D. Pompili, “Phd forum: Resource allocation and task offloading in cloud-assisted
wireless networks,” in 2019 IEEE 20th International Symposium on ”A World of Wireless, Mobile
and Multimedia Networks” (WoWMoM), pp. 1–3, June 2019.
[20] A. Al-Quzweeni, T. E. H. El-Gorashi, L. Nonde, and J. M. H. Elmirghani, “Energy efficient network
function virtualization in 5g networks,” in 2015 17th International Conference on Transparent Optical
Networks (ICTON), pp. 1–4, July 2015.
[21] W. John, K. Pentikousis, G. Agapiou, E. Jacob, M. Kind, A. Manzalini, F. Risso, D. Staessens,
R. Steinert, and C. Meirosu, “Research directions in network service chaining,” 12 2013.
[22] C. P. J. Halpern, “Service function chaining (sfc) architecture,” rfc - informational, Internet Engineering
Task Force (IETF), October 2015.
[23] C. P. P. Quinn, U. Elzur, “Network service header (nsh),” rfc - proposed standard, Internet Engineering
Task Force (IETF), January 2018.
[24] A. Abdelsalam, S. Salsano, F. Clad, P. Camarillo, and C. Filsfils, “Sr-snort: Ipv6 segment routing
aware ids/ips,” in 2018 IEEE Conference on Network Function Virtualization and Software Defined
Networks (NFV-SDN), pp. 1–2, Nov 2018.
[25] A. Abdelsalam, S. Salsano, F. Clad, P. Camarillo, and C. Filsfils, “Sera: Segment routing aware firewall
for service function chaining scenarios,” in 2018 IFIP Networking Conference (IFIP Networking)
and Workshops, pp. 46–54, May 2018.
[26] A. Van Bemten, J. W. Guck, P. Vizarreta, C. M. Machuca, and W. Kellerer, “Larac-sn and mole in the
hole: Enabling routing through service function chains,” in 2018 4th IEEE Conference on Network
Softwarization and Workshops (NetSoft), pp. 298–302, June 2018.
[27] G. Li, H. Zhou, B. Feng, G. Li, and Q. Xu, “Horizontal-based orchestration for multi-domain sfc in
sdn/nfv-enabled satellite/terrestrial networks,” China Communications, vol. 15, pp. 77–91, May 2018.
[28] 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.
[29] “https://github.com/p4lang/behavioral-model, [Online; accessed 1-December-2019].,” 2019.
[30] B. Lantz, B. Heller, and N. McKeown, “A network in a laptop: Rapid prototyping for software-defined
networks,” in Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks, Hotnets-
IX, (New York, NY, USA), pp. 19:1–19:6, ACM, 2010.
[31] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische mathematik, vol. 1,
no. 1, pp. 269–271, 1959.
[32] W. Zeng and R. Church, “Finding shortest paths on real road networks: The case for a,” International
Journal of Geographical Information Science, vol. 23, pp. 531–543, 04 2009.