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
Y1 - 2014
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
U2 - 10.1109/INFOCOM.2014.6848227
DO - 10.1109/INFOCOM.2014.6848227
M3 - Conference contribution
AN - SCOPUS:84904438137
SN - 9781479933600
T3 - Proceedings - IEEE INFOCOM
SP - 2777
EP - 2785
BT - IEEE INFOCOM 2014 - IEEE Conference on Computer Communications
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 -