On replica placement for QoS-aware content distribution

Xueyan Tang; Jianliang Xu

doi:10.1109/INFCOM.2004.1356969

On replica placement for QoS-aware content distribution

Xueyan Tang, Jianliang Xu

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

57 Citations (Scopus)

Abstract

The rapid growth of time-critical information services and business-oriented applications is making quality of service (QoS) support increasingly important in content distribution. This paper investigates the problem of placing object replicas (e.g., web pages and images) to meet the QoS requirements of clients with the objective of minimizing the replication cost. We consider two classes of service models: replica-aware service and replica-blind service. In the replica-aware model, the servers are aware of the locations of replicas and can therefore direct requests to the nearest replica. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for efficient computation of suboptimal solutions are proposed and experimentally evaluated. In the replica-blind model, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.

Original language	English
Title of host publication	Proceedings of 23rd IEEE Conference on Computer Communications, IEEE INFOCOM 2004
Publisher	IEEE
Pages	806-815
Number of pages	10
Volume	4
DOIs	https://doi.org/10.1109/INFCOM.2004.1356969
Publication status	Published - Mar 2004
Event	The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies , IEEE INFOCOM 2004 - Hong Kong Convention and Exhibition Centre, Hong Kong, Hong Kong Duration: 7 Mar 2004 → 11 Mar 2004 https://infocom2004.ieee-infocom.org/ (Link to conference website) https://ieeexplore.ieee.org/xpl/conhome/9369/proceeding (Link to conference proceedings)

Publication series

Name	Proceedings of IEEE INFOCOM
Publisher	IEEE
ISSN (Print)	0743-166X

Conference

Conference	The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies , IEEE INFOCOM 2004
Country/Territory	Hong Kong
City	Hong Kong
Period	7/03/04 → 11/03/04
Internet address	https://infocom2004.ieee-infocom.org/ (Link to conference website) https://ieeexplore.ieee.org/xpl/conhome/9369/proceeding (Link to conference proceedings)

Scopus Subject Areas

General Computer Science
Electrical and Electronic Engineering

Access to Document

10.1109/INFCOM.2004.1356969

Cite this

@inproceedings{d9a74981638e404e8cd535b44488c446,

title = "On replica placement for QoS-aware content distribution",

abstract = "The rapid growth of time-critical information services and business-oriented applications is making quality of service (QoS) support increasingly important in content distribution. This paper investigates the problem of placing object replicas (e.g., web pages and images) to meet the QoS requirements of clients with the objective of minimizing the replication cost. We consider two classes of service models: replica-aware service and replica-blind service. In the replica-aware model, the servers are aware of the locations of replicas and can therefore direct requests to the nearest replica. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for efficient computation of suboptimal solutions are proposed and experimentally evaluated. In the replica-blind model, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.",

author = "Xueyan Tang and Jianliang Xu",

note = "Funding information: Jianliang Xu's work was supponed by a grant from the Hong Kong Baptist University (Grant No. FRG/02-03/II-34). Publisher copyright: Copyright {\textcopyright} 2004 by the Institute of Electrical and Electronics Engineers, Inc.; The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies , IEEE INFOCOM 2004 ; Conference date: 07-03-2004 Through 11-03-2004",

year = "2004",

month = mar,

doi = "10.1109/INFCOM.2004.1356969",

language = "English",

volume = "4",

series = "Proceedings of IEEE INFOCOM",

publisher = "IEEE",

pages = "806--815",

booktitle = "Proceedings of 23rd IEEE Conference on Computer Communications, IEEE INFOCOM 2004",

address = "United States",

url = "https://infocom2004.ieee-infocom.org/, https://ieeexplore.ieee.org/xpl/conhome/9369/proceeding",

}

Tang, X & Xu, J 2004, On replica placement for QoS-aware content distribution. in Proceedings of 23rd IEEE Conference on Computer Communications, IEEE INFOCOM 2004. vol. 4, Proceedings of IEEE INFOCOM, IEEE, pp. 806-815, The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies , IEEE INFOCOM 2004, Hong Kong, Hong Kong, 7/03/04. https://doi.org/10.1109/INFCOM.2004.1356969

TY - GEN

T1 - On replica placement for QoS-aware content distribution

AU - Tang, Xueyan

AU - Xu, Jianliang

N1 - Funding information: Jianliang Xu's work was supponed by a grant from the Hong Kong Baptist University (Grant No. FRG/02-03/II-34). Publisher copyright: Copyright © 2004 by the Institute of Electrical and Electronics Engineers, Inc.

PY - 2004/3

Y1 - 2004/3

N2 - The rapid growth of time-critical information services and business-oriented applications is making quality of service (QoS) support increasingly important in content distribution. This paper investigates the problem of placing object replicas (e.g., web pages and images) to meet the QoS requirements of clients with the objective of minimizing the replication cost. We consider two classes of service models: replica-aware service and replica-blind service. In the replica-aware model, the servers are aware of the locations of replicas and can therefore direct requests to the nearest replica. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for efficient computation of suboptimal solutions are proposed and experimentally evaluated. In the replica-blind model, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.

AB - The rapid growth of time-critical information services and business-oriented applications is making quality of service (QoS) support increasingly important in content distribution. This paper investigates the problem of placing object replicas (e.g., web pages and images) to meet the QoS requirements of clients with the objective of minimizing the replication cost. We consider two classes of service models: replica-aware service and replica-blind service. In the replica-aware model, the servers are aware of the locations of replicas and can therefore direct requests to the nearest replica. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for efficient computation of suboptimal solutions are proposed and experimentally evaluated. In the replica-blind model, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.

UR - http://www.scopus.com/inward/record.url?scp=8344272786&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2004.1356969

DO - 10.1109/INFCOM.2004.1356969

M3 - Conference proceeding

AN - SCOPUS:8344272786

VL - 4

T3 - Proceedings of IEEE INFOCOM

SP - 806

EP - 815

BT - Proceedings of 23rd IEEE Conference on Computer Communications, IEEE INFOCOM 2004

PB - IEEE

T2 - The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies , IEEE INFOCOM 2004

Y2 - 7 March 2004 through 11 March 2004

ER -

On replica placement for QoS-aware content distribution

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this