Cloud services are burgeoning, the next distributed computing era and the next generation of hyperscale data centers are subverting the past. With the rise of Cloud Computing, Artificial Intelligence, and the Internet of Things, data centers have ushered in the third wave of upsurge. Since Network Functions Virtualization (NFV) was put forward by ETSI, NFV development has been highly concerned. Recent methods are becoming obsolete for dealing with the lateral flow in DCN, and attentions to lateral flow to date are also scant. In this research, we devise an algorithm, VIV3A, for hyperscale distributed cloud data centers. The novelty of our work lies not only in considering the new paradigm of lateral flow sensing on real topologies but also in demonstrating the hardness of NFVSED optimization by proof.

[1] ETSI. “Network functions virtualisation (nfv).” (2012), [Online]. Available: https: //portal.etsi.org/nfv/nfv_white_paper.pdf.
[2] ETSI. “Network functions virtualisation (nfv): Network operator perspectives on industry progress.” (2014), [Online]. Available: https://portal.etsi.org/Portals/ 0/TBpages/NFV/Docs/NFV_White_Paper3.pdf.
[3] U. S. Government. “U.s. federal acquisition regulations.” (2017), [Online]. Available: https://web.archive.org/web/20170130041945/https://www.acquisition. gov/far/html/Subpart%202_1.html#wp1158534.
[4] ETSI. “Network functions virtualiztion (nfv): Network operator perspectives on industry progress.” (2013), [Online]. Available: https://portal.etsi.org/NFV/ NFV_White_Paper2.pdf.
[5] CNCF. “Cncf cloud native interactive landscape.” (2021), [Online]. Available: https: //landscape.cncf.io/.
[6] E. A. Brewer, “Kubernetes and the path to cloud native,” in Proceedings of the sixth ACM symposium on cloud computing, 2015, pp. 167–167.
[7] B. Dab, I. Fajjari, M. Rohon, C. Auboin, and A. Diquélou, “Cloud-native service function chaining for 5g based on network service mesh,” in ICC 2020-2020 IEEE International Conference on Communications (ICC), IEEE, 2020, pp. 1–7.
[8] S. Garg, K. Kaur, G. Kaddoum, and S. Guo, “Sdn-nfv-aided edge-cloud interplay for 5g-envisioned energy internet ecosystem,” IEEE Network, vol. 35, no. 1, pp. 356– 364, 2021.
[9] J. Liu, H. Xu, G. Zhao, C. Qian, X. Fan, and L. Huang, “Incremental server deployment for scalable nfv-enabled networks,” in IEEE INFOCOM 2020-IEEE Conference on Computer Communications, IEEE, 2020, pp. 2361–2370.
[10] G. Sallam and B. Ji, “Joint placement and allocation of virtual network functions with budget and capacity constraints,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications, IEEE, 2019, pp. 523–531.
[11] X. Fei, F. Liu, H. Xu, and H. Jin, “Adaptive vnf scaling and flow routing with proactive demand prediction,” in IEEE INFOCOM 2018-IEEE Conference on Computer Communications, IEEE, 2018, pp. 486–494.
[12] L. Gu, X. Chen, H. Jin, and F. Lu, “Vnf deployment and flow scheduling in geo- distributed data centers,” in 2018 IEEE International Conference on Communications (ICC), IEEE, 2018, pp. 1–6.
[13] S. Agarwal, F. Malandrino, C.-F. Chiasserini, and S. De, “Joint vnf placement and cpu allocation in 5g,” in IEEE INFOCOM 2018-IEEE Conference on Computer Communications, IEEE, 2018, pp. 1943–1951.
[14] Y. Sang, B. Ji, G. R. Gupta, X. Du, and L. Ye, “Provably efficient algorithms for joint placement and allocation of virtual network functions,” in IEEE INFOCOM 2017-IEEE Conference on Computer Communications, IEEE, 2017, pp. 1–9.
[15] X. Zhang, C. Wu, Z. Li, and F. C. Lau, “Proactive vnf provisioning with multi- timescale cloud resources: Fusing online learning and online optimization,” in IEEE INFOCOM 2017-IEEE Conference on Computer Communications, IEEE, 2017, pp. 1–9.
[16] H. Feng, J. Llorca, A. M. Tulino, D. Raz, and A. F. Molisch, “Approximation algorithms for the nfv service distribution problem,” in IEEE INFOCOM 2017- IEEE Conference on Computer Communications, IEEE, 2017, pp. 1–9.
[17] S. Herker, X. An, W. Kiess, S. Beker, and A. Kirstaedter, “Data-center architecture impacts on virtualized network functions service chain embedding with high availability requirements,” in 2015 IEEE Globecom Workshops (GC Wkshps), IEEE, 2015, pp. 1–7.
[18] I. Bermudez, S. Traverso, M. Mellia, and M. Munafo, “Exploring the cloud from passive measurements: The amazon aws case,” in 2013 Proceedings IEEE INFOCOM, IEEE, 2013, pp. 230–234.
[19] P.-W. Chi, Y.-C. Huang, and C.-L. Lei, “Efficient nfv deployment in data center net- works,” in 2015 IEEE International Conference on Communications (ICC), IEEE, 2015, pp. 5290–5295.
[20] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” ACM SIGCOMM computer communication review, vol. 38, no. 4, pp. 63–74, 2008.
[21] B. Heller, S. Seetharaman, P. Mahadevan, Y. Yiakoumis, P. Sharma, S. Banerjee, and N. McKeown, “Elastictree: Saving energy in data center networks.,” in Nsdi, vol. 10, 2010, pp. 249–264.
[22] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta, “Vl2: A scalable and flexible data center network,” in Proceedings of the ACM SIGCOMM 2009 conference on Data communication, 2009, pp. 51–62.
[23] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “Bcube: A high performance, server-centric network architecture for modular data centers,” in Proceedings of the ACM SIGCOMM 2009 conference on Data communication, 2009, pp. 63–74.
[24] D. Alger, The Art of the Data Center: A Look Inside the World’s Most Innovative and Compelling Computing Environments. Prentice Hall, 2012.
[25] M. F. Bari, R. Boutaba, R. Esteves, L. Z. Granville, M. Podlesny, M. G. Rabbani, Q. Zhang, and M. F. Zhani, “Data center network virtualization: A survey,” IEEE communications surveys & tutorials, vol. 15, no. 2, pp. 909–928, 2012.
[26] C. E. Leiserson, “Fat-trees: Universal networks for hardware-efficient supercomputing,” IEEE transactions on Computers, vol. 100, no. 10, pp. 892–901, 1985.
[27] C. Clos, “A study of non-blocking switching networks,” Bell System Technical Journal, vol. 32, no. 2, pp. 406–424, 1953.
[28] J. Hamilton, “An architecture for modular data centers,”
[29] C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu, “Dcell: A scalable and fault-tolerant network structure for data centers,” in Proceedings of the ACM SIGCOMM 2008 conference on Data communication, 2008, pp. 75–86.
[30] A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: Networking data centers randomly,” in 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12), 2012, pp. 225–238.
[31] N. Farrington, G. Porter, S. Radhakrishnan, H. H. Bazzaz, V. Subramanya, Y. Fainman, G. Papen, and A. Vahdat, “Helios: A hybrid electrical/optical switch architecture for modular data centers,” in Proceedings of the ACM SIGCOMM 2010 Conference, 2010, pp. 339–350.
[32] C. Chekuri and S. Khanna, “On multi-dimensional packing problems,” in Proceedings of the tenth annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Citeseer, 1999, pp. 185–194.
[33] V. V. Vazirani, Approximation algorithms. Springer Science & Business Media, 2013.
[34] V. Kann, “Maximum bounded 3-dimensional matching is max snp-complete,” Information Processing Letters, vol. 37, no. 1, pp. 27–35, 1991.
[35] M. R. Garey, R. L. Graham, D. S. Johnson, and A. C.-C. Yao, “Resource constrained scheduling as generalized bin packing,” Journal of Combinatorial Theory, Series A, vol. 21, no. 3, pp. 257–298, 1976.
[36] W. F. De La Vega and G. S. Lueker, “Bin packing can be solved within 1+ ε in linear time,” Combinatorica, vol. 1, no. 4, pp. 349–355, 1981.
[37] M. R. Garey and D. S. Johnson, Computers and intractability. freeman San Fran- cisco, 1979, vol. 174.
[38] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, “Proof verification and the hardness of approximation problems,” Journal of the ACM (JACM), vol. 45, no. 3, pp. 501–555, 1998.
[39] S. Mertens, “Number partitioning,” Computational Complexity and Statistical Physics, p. 125, 2006.