Abstract Network congestion is an obstacle to a Quality of Service (QoS) guarantee for online video applications, because it leads to a high packet loss rate and long transmission delay. In the Software-Defined Network (SDN), the controller can conveniently obtain the network topology and link bandwidth use situation. Based on the above advantages, an SDN-based video multicast routing solution, called Congestion Avoidance Video Multicast (CAVM), is proposed in this paper. CAVM obtains overall network topology, monitors available bandwidth resource and measures the link delays based on the OpenFlow, a popular SDN southbound interface. We introduce a novel multicast routing problem, named the Delay-Constrained and Minimum Congestion-Cost Multicast Routing (DCMCCMR) problem, which finds the multicast tree with the lowest congestion cost and a source-destination delay constraint in the SDN environment. The DCMCCMR problem is NP-hard. CAVM uses an algorithm to solve it in polynomial time. Our experimental results confirm that the proposed algorithm can build multicast trees with good congestion avoidance capability.

References

[1] Chowdhury S., Bari M., Ahmed R., and Boutaba R., “Payless: A Low Cost Network Monitoring Framework for Software Defined Networks,” in Proceedings of IEEE Network Operations and Management Symposium, Krakow, pp. 1-9, 2014.

[2] Derdouri L., Pham C., and Mohamed M., “Analysis of Hybrid Router-Assisted Reliable Multicast Protocols in Lossy Networks,” The International Arab Journal of Information Technology, vol. 14, no. 1, pp. 26-34, 2017.

[3] Dumitrescu I. and Boland N., “Algorithms for the Weight Constrained Shortest Path Problem,” International Transactions in Operational Research, vol. 8, no. 1, pp. 15-29, 2002.

[4] Hasrouty C., Autefage V., Olariu C., Magoni D., and Murphy J., “Sdn-Driven Multicast Streams with Adaptive Bitrates for Voip Conferences,” in Proceedings of IEEE International Conference on Communications, Kuala Lumpur, pp. 1-7, 2016.

[5] Huang L., Hung H., Lin C., and Yang D., “Scalable steiner Tree for Multicast Communications in Software-Defined Networking”, Available at: http://arxiv.org/abs/1404.3454, Last Visited, 2018.

[6] Internet Topology Zoo, Available at: http://www.topology-zoo.org/dataset.html, Last Visited, 2018.

[7] Jiang J., Huang H., Liao J., and Chen S., “Extending Dijkstra’s Shortest Path Algorithm for Software Defined Networking,” in Proceedings of 16th Asia-Pacific Network Operations and Management Symposium, Hsinchu, pp. 1-4, 2014.

[8] Kreutz D., Ramos F., Verissimo P., Rothenberg C., Azodolmolky S., and Uhlig S., “Software-Defined Networking: A Comprehensive Survey,” Proceedings of the IEEE, vol. 103, no. 1, pp. 14-76, 2015.

[9] Kwon G. and Byers J., “Smooth Multirate Multicast Congestion Control,” in Proceedings 22nd Annual Joint Conference of the IEEE Computer and Communications, pp. 1022-1032, 2003.

[10] Mahajan K., Sharma D., and Mann V., “Athena: Reliable Multicast for Group Communication in SDN-Based Data Centers,” in Proceedings of 9th International Conference on Communication Systems and Networks, Bangalore, pp. 174-181, 2017.

[11] McKeown N., Anderson T., Balakrishnan H., Parulkar G., Peterson L., Rexford J., Shenker S., and Turner J., “Openflow: Enabling Innovation in Campus Networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 69-74, 2008.

[12] Moy J., “Multicast Extensions to Ospf,” IETF RFC 1584, Network Working Group, 1994.

[13] Niels L., Adrichem M., Doerr C., and Kuipers F., “Opennetmon: Network Monitoring in Openflow Software-Defined Networks,” in Proceedings of IEEE Network Operations and Management Symposium, Krakow, pp. 1-8, 2014.

[14] Noghani K. and Sunay M., “Streaming Multicast Video Over Software-Defined Networks,” in Proceedings of IEEE 11th International Conference on Mobile Ad Hoc and Sensor Systems, Philadelphia, pp. 551-556, 2014.

[15] Phemius K. and Bouet M., “Monitoring Latency with Openflow,” in Proceedings of 9th International Conference on Network and Service Management, Zurich, pp. 122-125, 2013.

[16] Pusateri T., “Protocol Independent Multicast-Sparse Mode,” IETF RFC 4602, Network Working Group, 2006.

[17] Rao A., Legout A., Lim Y., Towsley D., Barakat C., and Dabbous W., “Network Characteristics of Video Streaming Traffic,” in Proceedings of the 17th Conference on Emerging Networking Experiments and Technologies, Tokyo, pp. 1-12, 2011.

[18] Rizzo L., “Pgmcc: A TCP-Friendly Single-Rate Multicast Congestion Control Scheme,” ACM SIGCOMM Computer Communication Review, vol. 30, no. 4, pp. 17-28, 2000. Toward Building Video Multicast Tree with Congestion Avoidance Capability ... 169

[19] Sheu J., Chang C., and Chang Y., “Efficient Multicast Algorithms for Scalable Video Coding in Software-Defined Networking,” in Proceedings of Personal, Indoor, and Mobile Radio Communications, Hong Kong, pp. 2089-2093, 2015.

[20] Smith O., Boland N., and Waterer H., “Solving Shortest Path Problems with A Weight Constraint and Replenishment Arcs,” Computers and Operations Research, vol. 39, no. 5, pp. 964-984, 2012.

[21] Sun M. and Wang H., “The Memetic Algorithm for the Minimum Spanning Tree Problem with Degree and Delay Constraints,” in Proceedings of 15th International Conference on Advanced Communication Technology, Pyeong Chang, pp. 78-82, 2013.

[22] Voellmy A., Wang J., Yang Y., Ford B., and Hudak P., “Maple: Simplifying SDN Programming Using Algorithmic Policies,” ACM SIGCOMM Computer Communication Review, vol. 43, no. 4, pp. 87-98, 2013.

[23] Waitzman D., Partridge C., and Deering S., “Distance Vector Multicast Routing Protocol,” IETF RFC 1075, 1998.

[24] Waxman B., “Routing of Multipoint Connections,” IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1617-1622, 1988.

[25] Widmer J. and Handley M., “TCP-Friendly Multicast Congestion Control (TFMCC): Protocol Specification,” IETF RFC 4654, Network Working Group, 2006.

[26] Yu M., Rexford J., Freedman M., and Wang J., “Scalable Flow-Based Networking with Difane,” ACM SIGCOMM Computer Communication Review, vol. 40, no. 4, pp. 351-362, 2011.

[27] Zhang Q., Guo Q., Ni Q., Zhu W., and Zhang Y., “Sender-Adaptive and Receiver-Driven Layered Multicast for Scalable Video over the Internet,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, no. 4, pp. 482-495, 2005.

[28] Zhang X., Yang M., Wang L., and Sun M., “An OpenFlow-Enabled Elastic Loss Recovery Solution for Reliable Multicast,” IEEE Systems Journal, vol. 12, no. 2, pp. 1945-1956, 2018.

[29] Zhang X., Yang M., Zhao Y., Zhang J., and Ge J., “An SDN-Based Video Multicast Orchestration Scheme for 5G Ultra-Dense Networks,” IEEE Communications Magazine, vol. 55, no. 12, pp. 77-83, 2017.

[30] Zhou L. and Sun Y., “Delay-Constrained Steiner Tree Algorithm Using mph,” Journal of Computer Re-search and Development, vol. 45, no. 5, pp. 810-816, 2008. Huifen Huang received her M.S degree from Shandong University in 2006, and her Ph.D degree from Wuhan University of Technology in 2012. Presently, she is a professor at Shandong Yingcai University, and the director of Computer Application Technology Research Institution of Information Technology College. Her research interests include networking and information security. Zhihong Wu received her M.S degree from Shandong University in 2005, and her Ph.D degree from Shandong University in 2013. Presently, she is an associate professor at Shandong University. Her current research interests include medical information. She is the corresponding author of this paper. Jing Ge received her B.E. and Ph.D. degrees from Shandong University in 2010 and 2015, respectively. Now, she is a researcher with the Shandong Computer Science Center (National Supercomputer Center in Jinan). Her research interests mainly include software defined networking and multimedia. Lu Wang received the B.S. and M.S. degrees from Shandong University, China, in 2004 and 2007, respectively. He is currently a researcher with the Shandong Computer Science Center (National Supercomputer Center in Jinan). His research interests include network protocol, protocol test, and cloud computing.