An approximation algorithm for client assignment in client/server systems

Yuqing Zhu; Weili Wu; James Willson; Ling Ding; Lidong Wu; Deying Li; Wonjun Lee

doi:10.1109/INFOCOM.2014.6848227

An approximation algorithm for client assignment in client/server systems

Yuqing Zhu, Weili Wu, James Willson, Ling Ding, Lidong Wu, Deying Li, Wonjun Lee

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

Abstract

One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

Original language	English
Title of host publication	Proceedings - IEEE INFOCOM
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2777-2785
Number of pages	9
ISBN (Print)	9781479933600
DOIs	https://doi.org/10.1109/INFOCOM.2014.6848227
Publication status	Published - 2014 Jan 1
Event	33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 - Toronto, ON, Canada Duration: 2014 Apr 27 → 2014 May 2

Other

Other	33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
Country/Territory	Canada
City	Toronto, ON
Period	14/4/27 → 14/5/2

ASJC Scopus subject areas

Computer Science(all)
Electrical and Electronic Engineering

Access to Document

10.1109/INFOCOM.2014.6848227

Cite this

Zhu, Y, Wu, W, Willson, J, Ding, L, Wu, L, Li, D & Lee, W 2014, An approximation algorithm for client assignment in client/server systems. in Proceedings - IEEE INFOCOM., 6848227, Institute of Electrical and Electronics Engineers Inc., pp. 2777-2785, 33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014, Toronto, ON, Canada, 14/4/27. https://doi.org/10.1109/INFOCOM.2014.6848227

@inproceedings{074f31935993474a8e8370691bf7faa4,

title = "An approximation algorithm for client assignment in client/server systems",

abstract = "One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.",

author = "Yuqing Zhu and Weili Wu and James Willson and Ling Ding and Lidong Wu and Deying Li and Wonjun Lee",

year = "2014",

month = jan,

day = "1",

doi = "10.1109/INFOCOM.2014.6848227",

language = "English",

isbn = "9781479933600",

pages = "2777--2785",

booktitle = "Proceedings - IEEE INFOCOM",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 ; Conference date: 27-04-2014 Through 02-05-2014",

}

TY - GEN

T1 - An approximation algorithm for client assignment in client/server systems

AU - Zhu, Yuqing

AU - Wu, Weili

AU - Willson, James

AU - Ding, Ling

AU - Wu, Lidong

AU - Li, Deying

AU - Lee, Wonjun

PY - 2014/1/1

Y1 - 2014/1/1

N2 - One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

AB - One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

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

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

U2 - 10.1109/INFOCOM.2014.6848227

DO - 10.1109/INFOCOM.2014.6848227

M3 - Conference contribution

AN - SCOPUS:84904438137

SN - 9781479933600

SP - 2777

EP - 2785

BT - Proceedings - IEEE INFOCOM

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014

Y2 - 27 April 2014 through 2 May 2014

ER -

An approximation algorithm for client assignment in client/server systems

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this