Interactivity-constrained server provisioning in large-scale distributed virtual environments
Maintaining interactivity is one of the key challenges in distributed virtual environments (DVE), e.g., online games, distributed simulations, etc., due to the large, heterogeneous Internet latencies; and the fact that clients in a DVE are usually geographically separated. In this paper, we consider...
Saved in:
Main Authors: | , , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2011
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/4770 https://ink.library.smu.edu.sg/context/sis_research/article/5773/viewcontent/213390.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-5773 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-57732020-01-16T10:25:41Z Interactivity-constrained server provisioning in large-scale distributed virtual environments TA, Nguyen Binh Duong NGUYEN, Thang ZHOU, Suiping TANG, Xueyan CAI, Wentong AYANI, Rassul Maintaining interactivity is one of the key challenges in distributed virtual environments (DVE), e.g., online games, distributed simulations, etc., due to the large, heterogeneous Internet latencies; and the fact that clients in a DVE are usually geographically separated. In this paper, we consider a new problem, termed the interactivity-constrained server provisioning problem, whose goal is to minimize the number of distributed servers needed to achieve a pre-determined level of interactivity. We identify and formulate two variants of this new problem and show that they are both NP-hard via reductions to the set covering problem. We then propose several computationally efficient approximation algorithms for solving the problem. The main algorithms exploit dependencies among distributed servers to make provisioning decisions. We conduct extensive experiments to evaluate the performance of the proposed algorithms. More specifically, we use both static Internet latency data available from prior measurements and topology generators, as well as the most recent, dynamic latency data collected via our own large-scale deployment of a DVE performance monitoring system over PlanetLab. The results show that the newly proposed algorithms that take into account interserver dependencies significantly outperform the well-established set covering algorithm for both problem variants. 2011-04-05T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4770 info:doi/10.1109/TPDS.2011.107 https://ink.library.smu.edu.sg/context/sis_research/article/5773/viewcontent/213390.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Computer and Systems Architecture Software Engineering |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Computer and Systems Architecture Software Engineering |
spellingShingle |
Computer and Systems Architecture Software Engineering TA, Nguyen Binh Duong NGUYEN, Thang ZHOU, Suiping TANG, Xueyan CAI, Wentong AYANI, Rassul Interactivity-constrained server provisioning in large-scale distributed virtual environments |
description |
Maintaining interactivity is one of the key challenges in distributed virtual environments (DVE), e.g., online games, distributed simulations, etc., due to the large, heterogeneous Internet latencies; and the fact that clients in a DVE are usually geographically separated. In this paper, we consider a new problem, termed the interactivity-constrained server provisioning problem, whose goal is to minimize the number of distributed servers needed to achieve a pre-determined level of interactivity. We identify and formulate two variants of this new problem and show that they are both NP-hard via reductions to the set covering problem. We then propose several computationally efficient approximation algorithms for solving the problem. The main algorithms exploit dependencies among distributed servers to make provisioning decisions. We conduct extensive experiments to evaluate the performance of the proposed algorithms. More specifically, we use both static Internet latency data available from prior measurements and topology generators, as well as the most recent, dynamic latency data collected via our own large-scale deployment of a DVE performance monitoring system over PlanetLab. The results show that the newly proposed algorithms that take into account interserver dependencies significantly outperform the well-established set covering algorithm for both problem variants. |
format |
text |
author |
TA, Nguyen Binh Duong NGUYEN, Thang ZHOU, Suiping TANG, Xueyan CAI, Wentong AYANI, Rassul |
author_facet |
TA, Nguyen Binh Duong NGUYEN, Thang ZHOU, Suiping TANG, Xueyan CAI, Wentong AYANI, Rassul |
author_sort |
TA, Nguyen Binh Duong |
title |
Interactivity-constrained server provisioning in large-scale distributed virtual environments |
title_short |
Interactivity-constrained server provisioning in large-scale distributed virtual environments |
title_full |
Interactivity-constrained server provisioning in large-scale distributed virtual environments |
title_fullStr |
Interactivity-constrained server provisioning in large-scale distributed virtual environments |
title_full_unstemmed |
Interactivity-constrained server provisioning in large-scale distributed virtual environments |
title_sort |
interactivity-constrained server provisioning in large-scale distributed virtual environments |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2011 |
url |
https://ink.library.smu.edu.sg/sis_research/4770 https://ink.library.smu.edu.sg/context/sis_research/article/5773/viewcontent/213390.pdf |
_version_ |
1770575026266832896 |