Bi-Criteria Approximation for a Multi-Origin Multi-Channel Auto-Scaling Live Streaming Cloud
Abstract
Live video traffic has been widely observed to vary significantly within short timescale. In order to manage such traffic dynamic of overlay live streaming, the Content Provider (CP) may deploy a set of geo-dispersed auto-scaling servers where the pay-as-you-go deployment cost is charged by the amount of resources used due to server uploading and data transmission between servers. To support geo-distributed user demands, we study a novel multi-origin multi-channel auto-scaling live streaming cloud that pushes each channel stream in the core network overlay as a tree covering the end servers who have local demand for the channel. The Origin-to-End (O2E) delay from an origin to an end server is due to the Server-to-Server (S2S) delays of the overlay links along the path. By optimizing the overlay of the core network, we seek to minimize the deployment cost and O2E delays of the channels (i.e., a bi-criteria problem), which can be equivalently phrased as minimizing the deployment cost while meeting certain given maximum O2E delay constraints. We formulate a realistic problem capturing the major cost and delay components, and show its NP-hardness. We propose <bold>C</bold>ost-optimized Multi-<bold>O</bold>rigin Multi-<bold>C</bold>hannel <bold>O</bold>verlay <bold>S</bold>treaming (COCOS), a novel, efficient and near-optimal bi-criteria approximation algorithm with proven approximation ratio. Trace-driven extensive experimental results based on real-world live streaming service data validate that COCOS outperforms other state-of-the-art schemes by a wide margin (cutting the cost in general by more than 50%).
References
[1]
T. Barnett, S. Jain, U. Andra, and T. Khurana, “Cisco visual networking index (VNI): Complete forecast update, 2017–2022,” Accessed: Feb. 21, 2022. [Online]. Available: https://bit.ly/385BAhJ
[2]
E. Veloso, V. Almeida, W. Meira. Jr., A. Bestavros, and S. Jin, “A hierarchical characterization of a live streaming media workload,” IEEE/ACM Trans. Netw., vol. 14, no. 1, pp. 133–146, Feb. 2006.
[3]
C. Zhang and J. Liu, “On crowdsourced interactive live streaming: A Twitch.tv-based measurement study,” in Proc. 25th ACM Workshop Netw. Operating Syst. Support Digit. Audio Video, 2015, pp. 55–60.
[4]
A. Wittig and M. Wittig, “Amazon web services in action,” New York, NY, U.S.: Simon and Schuster, 2018. [Online]. Available: http://aws.amazon.com
[5]
M. V. Marathe et al., “Bicriteria network design problems,” J. Algorithms, vol. 28, no. 1, pp. 142–171, 1998.
[6]
Y. Zhao, H. Jiang, K. Zhou, Z. Huang, and P. Huang, “Meeting service level agreement cost-effectively for video-on-demand applications in the cloud,” in Proc. IEEE Conf. Comput. Commun., 2014, pp. 298–306.
[7]
X. Jin and S.-H. G. Chan, Unstructured Peer-to-Peer Network Architectures in Handbook of Peer-to-Peer Networking. Berlin, Germany: Springer, 2010, pp. 117–142.
[8]
B. Tan and L. Massoulié, “Optimal content placement for peer-to-peer video-on-demand systems,” IEEE/ACM Trans. Netw., vol. 21, no. 2, pp. 566–579, Apr. 2013.
[9]
S. Yun, H. Lim, and K. Chung, “The biometric signature delegation scheme to balance the load of digital signing in hybrid P2P networks,” Peer-to-Peer Netw. Appl., vol. 8, no. 4, pp. 631–640, 2014.
[10]
D. Wu, C. Liang, Y. Liu, and K. Ross, “View-upload decoupling: A redesign of multi-channel P2P video systems,” in Proc. IEEE Conf. Comput. Commun., 2009, pp. 2726–2730.
[11]
H. Zhao, J. Wang, Q. Wang, and F. Liu, “Queue-based and learning-based dynamic resources allocation for virtual streaming media server cluster of multi-version VoD system,” Multimedia Tools Appl., vol. 78, pp. 21827–21852, Apr. 2019.
[12]
J. Niño-Mora, “Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization,” Comput. Operations Res., vol. 103, pp. 221–236, 2019.
[13]
C. Valliyammai and R. Mythreyi, “A dynamic resource allocation strategy to minimize the operational cost in cloud,” in Emerging Technologies in Data Mining and Information Security, A. Abraham, P. Dutta, J. K. Mandal, A. Bhattacharya, and S. Dutta, Eds. Singapore: Springer, 2019, pp. 309–317.
[14]
Z. Chang and S.-H. G. Chan, “An approximation algorithm to maximize user capacity for an auto-scaling VoD system,” IEEE Trans. Multimedia, vol. 23, pp. 3714–3725, 2021.
[15]
R.-X. Zhang et al., “Livesmart: A QoS-guaranteed cost-minimum framework of viewer scheduling for crowdsourced live streaming,” in Proc. 27th ACM Int. Conf. Multimed., New York, NY, USA: Assoc. Comput. Mach., 2019, pp. 420–428.
[16]
R.-X. Zhang et al., “Leveraging QoE heterogenity for large-scale livecaset scheduling,” in Proc. 28th ACM Int. Conf. Multimed., New York, NY, USA: Assoc. Comput. Mach., 2020, pp. 3678–3686.
[17]
R.-X. Zhang et al., “Enhancing the crowdsourced live streaming: A deep reinforcement learning approach,” in Proc. 29th ACM Workshop Netw. Operat. Syst. Support Digit. Audio Video, New York, NY, USA: Assoc. Comput. Mach., 2019, pp. 55–60.
[18]
F. Haouari, E. Baccour, A. Erbad, A. Mohamed, and M. Guizani, “QoE-aware resource allocation for crowdsourced live streaming: A machine learning approach,” in Proc. IEEE Int. Conf. Commun., 2019, pp. 1–6.
[19]
T. Fernando and C. Keppetiyagama, “ISP friendly peer selection in bittorrent,” in Proc. Int. Conf. Adv. ICT Emerg. Regions, 2013, pp. 160–167.
[20]
N. Magharei, R. Rejaie, I. Rimac, V. Hilt, and M. Hofmann, “ISP-friendly live P2P streaming,” IEEE/ACM Trans. Netw., vol. 22, no. 1, pp. 244–256, Feb. 2014.
[21]
S. Hu, M. Xu, H. Zhang, C. Xiao, and C. Gui, “Affective content-aware adaptation scheme on QoE optimization of adaptive streaming over HTTP,” ACM Trans. Multimedia Comput. Commun. Appl., vol. 15, no. 3s, pp. 1–18, Dec. 2019.
[22]
J. Liu and G. Simon, “Fast near-optimal algorithm for delivering multiple live video channels in CDNs,” in Proc. 22nd Int. Conf. Comput. Commun. Netw., 2013, pp. 1–7.
[23]
X. Tan and S. Datta, “Building multicast trees for multimedia streaming in heterogeneous P2P networks,” in Proc. Syst. Commun., 2005, pp. 141–146.
[24]
C. Ding, Y. Chen, T. Xu, and X. Fu, “CloudGPS: A scalable and ISP-friendly server selection scheme in cloud computing environments,” in Proc. IEEE 20th Int. Workshop Qual. Serv., 2012, pp. 1–9.
[25]
I. Irondi, Q. Wang, C. Grecos, J. M. A. Calero, and P. Casaseca-De-La-Higuera, “Efficient QoE-Aware scheme for video quality switching operations in dynamic adaptive streaming,” ACM Trans. Multimedia Comput. Commun. Appl., vol. 15, no. 1, pp. 1–23, Feb. 2019.
[26]
N. Magharei and R. Rejaie, “PRIME: Peer-to-peer receiver-driven mesh-based streaming,” IEEE/ACM Trans. Netw., vol. 17, no. 4, pp. 1052–1065, Aug. 2009.
[27]
D. Ren, Y.-T. H. Li, and S.-H. G. Chan, “Fast-mesh: A low-delay high-bandwidth mesh for peer-to-peer live streaming,” IEEE Trans. Multimedia, vol. 11, no. 8, pp. 1446–1456, Dec. 2009.
[28]
Z. Lu, X. Gao, S. Huang, and Y. Huang, “Scalable and reliable live streaming service through coordinating CDN and P2P,” in Proc. IEEE 17th Int. Conf. Parallel Distrib. Syst., 2011, pp. 581–588.
[29]
H. K. Yarnagula, P. Juluri, S. K. Mehr, V. Tamarapalli, and D. Medhi, “QoE for mobile clients with segment-aware rate adaptation algorithm (SARA) for DASH video streaming,” ACM Trans. Multimedia Comput. Commun. Appl., vol. 15, no. 2, pp. 1–23, Jun. 2019.
[30]
J. Dai, Z. Chang, and S.-H. G. Chan, “Delay optimization for multi-source multi-channel overlay live streaming,” in Proc. IEEE Commun. Softw., Serv. Multimedia Appl. Symp., London, U.K., 2015, pp. 6959–6964.
[31]
X. Liao, H. Jin, Y. Liu, and L. M. Ni, “Scalable live streaming service based on interoverlay optimization,” IEEE Trans. Parallel Distrib. Syst., vol. 18, no. 12, pp. 1663–1674, Dec. 2007.
[32]
X. Liao, H. Jin, Y. Liu, L. M. Ni, and D. Deng, “AnySee: Peer-to-Peer live streaming,” in Proc. IEEE Int. Conf. Comput. Commun., 2006, pp. 1–10.
[33]
K. Pires and G. Simon, “DASH in twitch: Adaptive bitrate streaming in live game streaming platforms,” in Proc. Workshop Des., Qual. Deployment Adaptive Video Streaming, 2014, pp. 13–18.
[34]
A. Bentaleb, P. K. Yadav, W. T. Ooi, and R. Zimmermann, “DQ-DASH: A queuing theory approach to distributed adaptive video streaming,” ACM Trans. Multimedia Comput. Commun. Appl., vol. 16, no. 1, pp. 1–14, Mar. 2020.
[35]
D. Kondo, Y. Hirota, A. Fujimoto, H. Tode, and K. Murakami, “P2P live streaming system for multi-view video with fast switching,” in Proc. 16th Int. Telecommun. Netw. Strategy Plan. Symp., 2014, pp. 1–7.
[36]
R. Jannapureddy, Q.-T. Vien, P. Shah, and R. Trestian, “An auto-scaling framework for analyzing Big Data in the cloud environment,” Appl. Sci., vol. 9, no. 7, 2019, Art. no.
[37]
F. Zhou, L. Jiayi, G. Simon, and R. Boutaba, “Joint optimization for the delivery of multiple video channels in telco-CDN,” in Proc. Int. Conf. Netw. Serv. Manage., 2013, pp. 161–165.
[38]
Z. Zhuang and C. Guo, “Optimizing CDN infrastructure for live streaming with constrained server chaining,” in Proc. IEEE 9th Int. Sympo. Parallel Distrib. Process. Appl., 2011, pp. 183–188.
[39]
C. Wu, B. Li, and S. Zhao, “Multi-channel live P2P streaming: Refocusing on servers,” in Proc. IEEE Int. Conf. Comput. Commun., Phoenix, Arizona, 2008, pp. 1355–1363.
[40]
F. Zhou, S. Ahmad, E. Buyukkaya, R. Hamzaoui, and G. Simon, “Minimizing server throughput for low-delay live streaming in content delivery networks,” in Proc. 22nd Int. Workshop Netw. Operating Syst. Support Digit. Audio Video, 2012, pp. 65–70.
[41]
C. Hu, M. Chen, C. Xing, and B. Xu, “EUE principle of resource scheduling for live streaming systems underlying CDN-P2P hybrid architecture,” Peer-to-Peer Netw. Appl., vol. 5, no. 4, pp. 312–322, 2012.
[42]
F. Lombardi et al., “PASCAL: An architecture for proactive auto-scaling of distributed services,” Future Gener. Comput. Syst., vol. 98, pp. 342–361, 2019.
[43]
S. Budhkar and V. Tamarapalli, “An overlay management strategy to improve QoS in CDN-P2P live streaming systems,” Peer-to-Peer Netw. Appl., vol. 13, no. 1, pp. 190–206, 2020.
[44]
H. Azarpira and S. Yousefi, “On optimal topology in hierarchical P2P live video streaming networks,” in Proc. 6th Int. Symp. Telecommun., 2012, pp. 644–649.
[45]
M. Kucharzak, K. Walkowiak, and M. Klinkowski, “On modeling of minimum cost multicast topology with multiple static streams in overlay communication networks,” in Proc. 15th Int. Conf. Transparent Opt. Netw., 2013, pp. 1–4.
[46]
F. Zhang, X. Tang, X. Li, S. U. Khan, and Z. Li, “Quantifying cloud elasticity with container-based autoscaling,” Future Gener. Comput. Syst., vol. 98, pp. 672–681, 2019.
[47]
X. Jin, K.-L. Cheng, and S.-H. G. Chan, “Island multicast: Combining IP multicast with overlay data distribution,” IEEE Trans. Multimedia, vol. 11, no. 5, pp. 1024–1036, Aug. 2009.
[48]
R. Singh, S. Agarwal, M. Calder, and P. Bahl, “Cost-effective cloud edge traffic engineering with cascara,” in Proc. 18th USENIX Symp. Netw. Syst. Des. Implementation, 2021, pp. 201–216.
[49]
J. Naor and B. Schieber, “Improved approximations for shallow-light spanning trees,” in Proc. 38th Annu. Symp. Foundations Comput. Sci., 1997, pp. 536–541.
[50]
H. N. Gabow and K. Manu, “Packing algorithms for arborescences (and spanning trees) in capacitated graphs,” Math. Program., vol. 82, no. 1, pp. 83–109, 1998.
[51]
D. Kraft et al., A Software Package for Sequential Quadratic Programming. Germany: DFVLR Obersfaffeuhofen, Cologne, 1988.
Recommendations
Dynamic Resource Provision in Multi-Channel P2P Live Streaming Systems
CIT '10: Proceedings of the 2010 10th IEEE International Conference on Computer and Information TechnologyPeer-to-Peer is one of the most popular live streaming delivery technologies owing to its scalability and low-cost. Most practical P2P streaming systems adopt hundreds of channels to deliver streaming to thousands of users simultaneously, and thus there ...
Migration towards cloud-assisted live media streaming
Live media streaming has become one of the most popular applications over the Internet. We have witnessed the successful deployment of commercial systems with content delivery network (CDN)- or peer-to-peer-based engines. While each being effective in ...
Multi-camera Live Video Streaming over Wireless Network
Advances in Mobile Computing and Multimedia IntelligenceAbstractDue to the development of wireless communication technology, more and more streamers are using cameras mounted on mobile devices for live streaming in a wireless LAN environment. Conventional live streaming systems, which employ multiple images ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1520-9210 © 2022 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 January 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Dec 2024