Scalable load-distance balancing

被引:0
作者
Bortnikov, Edward [1 ]
Cidon, Israel [1 ]
Keidar, Idit [1 ]
机构
[1] Technion Israel Inst Technol, Dept Elect Engn, IL-32000 Haifa, Israel
来源
DISTRIBUTED COMPUTING, PROCEEDINGS | 2007年 / 4731卷
关键词
local computation; distributed algorithms; load-distance balancing; wireless networks;
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We introduce the problem of load-distance balancing in assigning users of a delay-sensitive networked application to servers. We model the service delay experienced by a user as a sum of a network-incurred delay, which depends on its network distance from the server, and a server-incuffed delay, stemming from the load on the server. The problem is to minimize the maximum service delay among all users. We address the challenge of finding a near-optimal assignment in a scalable distributed manner. The key to achieving scalability is using local solutions, whereby each server only communicates with a few close servers. Note, however, that the attainable locality of a solution depends on the workload - when some area in the network is congested, obtaining a near-optimal cost may require offloading users to remote servers, whereas when the network load is uniform, a purely local assignment may suffice. We present algorithms that exploit the opportunity to provide a local solution when possible, and thus have communication costs and stabilization times that vary according to the network congestion. We evaluate our algorithms with a detailed simulation case study of their application in assigning hosts to Internet gateways in an urban wireless mesh network (WMN).
引用
收藏
页码:77 / +
页数:3
相关论文
共 16 条
  • [1] AKYLIDIZ IF, 2005, COMPUTER NETWORKS J
  • [2] COMPLEXITY OF NETWORK SYNCHRONIZATION
    AWERBUCH, B
    [J]. JOURNAL OF THE ACM, 1985, 32 (04) : 804 - 823
  • [3] BARAK A, 1993, LNCS, V672
  • [4] Bejerano Y., 2006, IEEE INFOCOM
  • [5] BIRK Y, 2006, ACM PODC
  • [6] BORTNIKOV E, 2006, EE DEPARTMENT PUB, V1539
  • [7] CHEN J, 2005, LOCALITY AWARE DYNAM
  • [8] Du L, 2004, IEEE INFOCOM SER, P330
  • [9] GANGULY S, 2006, JSAC, V24
  • [10] GHOSH B, 1995, ACM STOC