The Server Provisioning Problem for Continuous Distributed Interactive Applications

被引:10
作者
Zheng, Hanying [1 ]
Tang, Xueyan [1 ]
机构
[1] Nanyang Technol Univ, Sch Comp Engn, Singapore 639798, Singapore
关键词
Distributed interactive application; server placement; interactivity; approximation algorithm; CLIENT ASSIGNMENT; PLACEMENT; LATENCY;
D O I
10.1109/TPDS.2015.2388473
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper, we study the server provisioning problem for continuous Distributed Interactive Applications (DIAs) whose application states not only change because of the operations performed by participants, but also evolve along with the passing of time. We focus on finding the locations of servers for hosting continuous DIAs, with the goals of optimizing the interactivity performance while fulfilling the consistency and fairness requirements. We show that the server provisioning problem is challenging by presenting its NP-hardness and non-approximability results under several conditions. We propose two efficient server placement algorithms and analyze their approximation ratios. The approximation ratio of the proposed M-BETTER algorithm is quite close to a lower bound for any polynomial-time algorithm. We also conduct experimental evaluations to compare the proposed algorithms with several baseline server placements.
引用
收藏
页码:271 / 285
页数:15
相关论文
共 50 条
[31]   Broadband networks for interactive telemedical applications [J].
Graschew, G ;
Roelofs, TA ;
Rakowsky, S ;
Schlag, PM .
AOC 2002: ASIA-PACIFIC OPTICAL AND WIRELESS COMMUNICATIONS; APPLICATIONS OF BROADBAND OPTICAL AND WIRELESS NETWORKS, 2002, 4912 :1-6
[32]   A framework for interactive parameter sweep applications [J].
Wibisono, Adianto ;
Zhao, Zhiming ;
Belloum, Adam ;
Bubak, Marian .
COMPUTATIONAL SCIENCE - ICCS 2008, PT 3, 2008, 5103 :481-490
[33]   A grid infrastructure for parallel and interactive applications [J].
Gomes, J. ;
Borges, G. ;
Montecelo, M. ;
David, M. ;
Silva, B. ;
Dias, N. ;
Martins, J. P. ;
Fernandez, C. ;
Garcia-Tarres, L. ;
Veiga, C. ;
Cordero, D. ;
Lopez, J. ;
Marco, J. ;
Campos, I. ;
Rodriguez, D. ;
Marco, R. ;
Lopez, A. ;
Orviz, P. ;
Hammad, A. ;
Hardt, M. ;
Fernandez, E. ;
Heymann, E. ;
Senar, M. A. ;
Padee, A. ;
Nawrocki, K. ;
Wislicki, W. ;
Heinzlreiter, P. ;
Baumgartner, M. ;
Rosmanith, H. ;
Kenny, S. ;
Coghlan, B. ;
Lason, P. ;
Skital, L. ;
Astalos, J. ;
Ciglan, M. ;
Pospieszny, M. ;
Valles, R. ;
Dichev, K. .
COMPUTING AND INFORMATICS, 2008, 27 (02) :173-185
[34]   Efficient Parameter Server Placement for Distributed Deep Learning in Edge Computing [J].
Wu, Yalan ;
Yan, Jiaquan ;
Chen, Long ;
Wu, Jigang ;
Li, Yidong .
COMPUTER JOURNAL, 2023, 66 (03) :678-691
[35]   Dynamic Network Function Provisioning to Enable Network in Box for Industrial Applications [J].
Sun, Gang ;
Xu, Zhu ;
Yu, Hongfang ;
Chang, Victor .
IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, 2021, 17 (10) :7155-7164
[36]   A demo of a PaaS for IoT Applications Provisioning in Hybrid Cloud/Fog Environment [J].
Bibani, Ons ;
Yangui, Sami ;
Glitho, Roch H. ;
Gaaloul, Walid ;
Ben Hadj-Alouane, Nejib ;
Morrow, Monique J. ;
Polakos, Paul A. .
2016 22ND IEEE INTERNATIONAL SYMPOSIUM ON LOCAL AND METROPOLITAN AREA NETWORKS (IEEE LANMAN), 2016,
[37]   The Location Problem for the Provisioning of Protected Slices in NFV-Based MEC Infrastructure [J].
Chantre, Hernani D. ;
Saldanha da Fonseca, Nelson Luis .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2020, 38 (07) :1505-1514
[38]   A Distributed Algorithm for the Replica Placement Problem [J].
Zaman, Sharrukh ;
Grosu, Daniel .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2011, 22 (09) :1455-1468
[39]   Agile Services Provisioning for Learning-Based Applications in Fog Computing Networks [J].
Chen, Nanxi ;
Sun, Qi ;
Li, Yanbei ;
Shu, Hongfeng ;
Li, Jiamao ;
Zhang, Xiaolin .
IEEE TRANSACTIONS ON SERVICES COMPUTING, 2023, 16 (04) :2423-2436
[40]   Truthful auction mechanisms for VNF chain provisioning and allocation across geo-distributed datacenters [J].
Wang, Xueyi ;
Wang, Xingwei ;
Wu, Dongkuo ;
Ma, Lianbo ;
Huang, Min .
COMPUTER NETWORKS, 2022, 217