Journal Home > Volume 24 , Issue 2

The use of multicast transmission can efficiently reduce the consumption of network resources by jointly serving multiple destinations with a single source node. Currently, many multicast applications impose the constraint wherein multicast flows must be processed by a series of Virtual Network Functions (VNFs) before reaching their destinations. Given a multicast transmission, there are usually multiple server nodes, each of which is able to host all the required VNFs. Thus, the multicast flow should be initially steered to one or a few selected server nodes that act as pseudo sources, and the destinations will then retrieve new flow from any of these pseudo sources. In this paper, we model this kind of multicast as an uncertain multicast with multiple pseudo sources, whose routing structure is usually a forest consisting of multiple isolated trees. We then characterize and construct the Delay-guaranteed Minimum Cost Forest (D-MCF) such that each path from the source to the destination satisfies the end-to-end delay constraint. To tackle this NP-hard problem, we design two efficient methods, the Partition Algorithm (PA) and the Combination Algorithm (CA), to approximate the optimal solution. Theoretical analyses and evaluations indicate that these two methods can generate the desired routing forest for any multicast transfer. Moreover, the PA method achieves a better balance between performance and time consumption than the CA method. The evaluation results show that PA- (Ω+20) can reduce total cost by 49.02% while consuming 12.59% more time, thus significantly outperforming the CA- (Ω+20) method.


menu
Abstract
Full text
Outline
About this article

Minimum-Cost Forest for Uncertain Multicast with Delay Constraints

Show Author's information Bangbang RenGeyao Cheng( )Deke Guo
College of Systems Engineering, National University of Denfense Technology, Changsha 410072, China.

Abstract

The use of multicast transmission can efficiently reduce the consumption of network resources by jointly serving multiple destinations with a single source node. Currently, many multicast applications impose the constraint wherein multicast flows must be processed by a series of Virtual Network Functions (VNFs) before reaching their destinations. Given a multicast transmission, there are usually multiple server nodes, each of which is able to host all the required VNFs. Thus, the multicast flow should be initially steered to one or a few selected server nodes that act as pseudo sources, and the destinations will then retrieve new flow from any of these pseudo sources. In this paper, we model this kind of multicast as an uncertain multicast with multiple pseudo sources, whose routing structure is usually a forest consisting of multiple isolated trees. We then characterize and construct the Delay-guaranteed Minimum Cost Forest (D-MCF) such that each path from the source to the destination satisfies the end-to-end delay constraint. To tackle this NP-hard problem, we design two efficient methods, the Partition Algorithm (PA) and the Combination Algorithm (CA), to approximate the optimal solution. Theoretical analyses and evaluations indicate that these two methods can generate the desired routing forest for any multicast transfer. Moreover, the PA method achieves a better balance between performance and time consumption than the CA method. The evaluation results show that PA- (Ω+20) can reduce total cost by 49.02% while consuming 12.59% more time, thus significantly outperforming the CA- (Ω+20) method.

Keywords: uncertain multicast, network function virtualization, delay guaranteed

References(30)

[1]
Galis A., Clayman S., Mamatas L., Loyola J. R., Manzalini A., Kuklinski S., Serrat J., and Zahariadis T., Softwarization of future networks and services-programmable enabled networks as next generation software defined networks, in Proc. 2013 IEEE SDN for Future Networks and Services, Trento, Italy, 2013, pp. 1-7.
DOI
[2]
Network functions virtualisation–Introductory white Paper, https://portal.etsi.org/nfv/nfv_white_paper.pdf, 2012.
[3]
Han B., Gopalakrishnan V., Ji L. S., and Lee S., Network function virtualization: Challenges and opportunities for innovations, IEEE Commun. Mag., vol. 53, no. 2, pp. 90-97, 2015.
[4]
Mijumbi R., Serrat J., Gorricho J. L., Bouten N., De Turck F., and Boutaba R., Network function virtualization: State-of-the-art and research challenges, IEEE Commun. Surv. Tutor., vol. 18, no. 1, pp. 236-262, 2016.
[5]
Mehraghdam S., Keller M., and Karl H., Specifying and placing chains of virtual network functions, in Proc. 2014 IEEE 3rd International Conference on Cloud Networking, Luxembourg, 2014, pp. 7-13.
DOI
[6]
Xu Z. C., Liang W. F., Huang M. T., Jia M. K., Guo S., and Galis A., Approximation and online algorithms for NFV-enabled multicasting in SDNs, in Proc. 2017 IEEE 37th Int. Conf. Distributed Computing Systems, Atlanta, GA, USA, 2017, pp. 625-634.
[7]
Mahimkar A., Ge Z. H., Shaikh A., Wang J., Yates J., Zhang Y., and Zhao Q., Towards automated performance diagnosis in a large IPTV network, in Proc. of ACM SIGCOMM 2009 Conf. Data Communication, Barcelona, Spain, 2009, pp. 231-242.
DOI
[8]
Guo D. K., Wu J., Liu Y. H., Jin H., Chen H. H., and Chen T., Quasi-kautz digraphs for peerto-peer networks, IEEE Trans. Parall. Distrib. Syst., vol. 22, no. 6, pp. 1042-1055, 2011.
[9]
Ding X. O., Wang H. Z., Gao Y. T., Li J. Z., and Gao H., Efficient currency determination algorithms for dynamic data, Tsinghua Sci. Technol., vol. 22, no. 3, pp. 227-242, 2017.
[10]
Guo D. K., Li C. L., Wu J., and Zhou X. L., DCube: A family of network structures for containerized data centers using dual-port servers, Comput. Commun., vol. 53, pp. 13-25, 2014.
[11]
Diot C., Dabbous W., and Crowcroft J., Multipoint communication: A survey of protocols, functions, and mechanisms, IEEE J. Select. Areas Commun., vol. 15, no. 3, pp. 277-290, 1997.
[12]
Ballardie T., Francis P., and Crowcroft J., Core Based Trees (CBT), in Proc. Conf. on Communications Architectures, Protocols and Applications, San Francisco, CA, USA, 1993, pp. 85-95.
DOI
[13]
Bharath-Kumar K. and Jaffe J., Routing to multiple destinations in computer networks, IEEE Trans. Commun., vol. 31, no. 3, pp. 343-351, 1983.
[14]
Hu Z. Y., Guo D. K., Xie J. J., and Ren B. B., Multicast routing with uncertain sources in software-defined network, in Proc. 2016 IEEE/ACM 24th Int. Symp. Quality of Service (IWQoS), Beijing, China, 2016, pp. 1-6.
[15]
Guo D. K., Teng X. Q., Hu Z. Y., Xie J. J., and Ren B. B., Source selection problem in multi-source multi-destination multicasting, Comput. Netw., vol. 127, pp. 43-55, 2017.
[16]
Ren B. B., Guo D. K., Xie J. J., Li W. X., Yuan B., and Liu Y. F., The packing problem of uncertain multicasts, Concurr. Comput.: Pract. Exp., vol. 29, no. 16, p. e3985, 2017.
[17]
Ergun F., Sinha R., and Zhang L. S., An improved FPTAS for restricted shortest path, Inf. Process. Lett., vol. 83, no. 5, pp. 287-291, 2002.
[18]
Hwang F. K., Richards D. S., and Winter P., The Steiner Tree Problem. Elsevier, 1992.
DOI
[19]
Deering S. E. and Cheriton D. R., Multicast routing in datagram internetworks and extended LANs, ACM Trans. Comput. Syst., vol. 8, no. 2, pp. 85-110, 1990.
[20]
Wang M. M., Liu J. W., Mao J., Cheng H. S., Chen J., and Qi C., RouteGuardian: Constructing secure routing paths in software-defined networking, Tsinghua Sci. Technol., vol. 22, no. 4, pp. 400-412, 2017.
[21]
Shen S. H., Huang L. H., Yang D. N., and Chen W. T., Reliable multicast routing for software-defined networks, in Proc. 2015 IEEE Conf. Computer Communications (INFOCOM), Hong Kong, China, 2015, pp. 181-189.
DOI
[22]
Zhang S. Q., Zhang Q., Bannazadeh H., and Leon-Garcia A., Network function virtualization enabled multicast routing on SDN, in Proc. 2015 IEEE Int. Conf. Communications (ICC), London, UK, 2015, pp. 5595-5601.
DOI
[23]
Kuo J. J., Shen S. H., Yang M. H., Yang D. N., Tsai M. J., and Chen W. T., Service overlay forest embedding for software-defined cloud networks, in Proc. 2017 IEEE 37th Int. Conf. Distributed Computing Systems (ICDCS), Atlanta, GA, USA, 2017, pp. 720-730.
DOI
[24]
Graham R. L. and Hell P., On the history of the minimum spanning tree problem, IEEE Ann. Hist. Comput., vol. 7, no. 1, pp. 43-57, 1985.
[25]
Floyd R. W., Algorithm 97: Shortest path, Commun. ACM, vol. 5, no. 6, p. 345, 1962.
[26]
Salama H. F., Reeves D. S., and Viniotis Y., The delay-constrained minimum spanning tree problem, in Proc. 2nd IEEE Symp. Computers and Communications, Alexandria, Egypt, 1997, pp. 699-703.
[27]
Kompella V. P., Pasquale J. C., and Polyzos G. C., Multicast routing for multimedia communication, IEEE/ACM Trans. Network., vol. 1, no. 3, pp. 286-292, 1993.
[28]
Parsa M., Zhu Q., and Garcia-Luna-Aceves J. J., An iterative algorithm for delay-constrained minimum-cost multicasting, IEEE/ACM Trans. Network., vol. 6, no. 4, pp. 461-474, 1998.
[29]
Chen Y. R., Radhakrishnan S., Dhall S., and Karabuk S., On multi-stream multi-source multicast routing, Comput. Netw., vol. 57, no. 15, pp. 2916-2930, 2013.
[30]
Dijkstra E. W., A note on two problems in connexion with graphs, Numerische Mathematic, vol. 1, no. 1, pp. 269-271, 1959.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 13 May 2017
Accepted: 18 May 2017
Published: 31 December 2018
Issue date: April 2019

Copyright

© The author(s) 2019

Acknowledgements

This work was partially supported by the National Natural Science Foundation for Outstanding Excellent Young Scholars of China (No. 61422214), the National Natural Science Foundation of China (No. 61772544), the National Key Basic Research and Development (973) Program of China (No. 2014CB347800), the Hunan Provincial Natural Science Fund for Distinguished Young Scholars (No. 2016JJ1002), the Guangxi Cooperative Innovation Center of Cloud Computing and Big Data (Nos. YD16507 and YD17X11), and the NUDT Research Plan (No. ZK17-03-50).

Rights and permissions

Return