Distributed load balancing in heterogenous systems
Distributed load balancing in heterogenous systems
复制标题
DOI：
10.1109/ciss.2014.6814133
复制
发表时间：
2014-03
期刊：
影响因子：
--
通讯作者：
Seyoung Yun;A. Proutière
中科院分区：
文献类型：
--
作者：
Seyoung Yun;A. Proutière
我们考虑异构并行服务器系统中的分布式负载平衡问题，其中用户在服务器上获得的服务速率取决于用户和服务器。这种异构性通常出现在无线网络中（例如，服务器可能代表频带，并且用户的服务速率因频带而异）。用户以分布式的方式选择服务器。它们最初连接到任意服务器。然而，在随机的时刻，他们可能会探测新服务器上的负载并迁移到那里以提高其服务率。我们分析了[5]中介绍的自然随机局部搜索（RLS）迁移方案下的系统动力学。在这种方案下，当用户有机会切换服务器时，只有当这提高了她的服务率时，她才会这样做。 RLS 下的动态可以解释为由战略参与者在负载平衡博弈中更新其策略而产生的动态。我们证明了这个博弈具有纯纳什均衡（NE），并分析了它们的效率。我们进一步证明，当用户数量增长时，纯NE会更接近用户到服务器的比例公平（PF）分配，并且我们根据用户数量来描述均衡与理想分配之间的差距。在RLS算法下，系统收敛到纯NE：我们研究系统在一定裕度内达到PF分配所需的时间。
We consider the problem of distributed load balancing in heterogeneous parallel server systems, where the service rate achieved by a user at a server depends on both the user and the server. Such heterogeneity typically arises in wireless networks (e.g., servers may represent frequency bands, and the service rate of a user varies across bands). Users select servers in a distributed manner. They initially attach to an arbitrary server. However, at random instants of time, they may probe the load at a new server and migrate there to improve their service rate. We analyze the system dynamics under the natural Random Local Search (RLS) migration scheme, introduced in [5]. Under this scheme, when a user has the opportunity to switch servers, she does it only if this improves her service rate. The dynamics under RLS may be interpreted as those generated by strategic players updating their strategy in a load balancing game. We show that this game has pure Nash Equilibriums (NEs), and we analyze their efficiency. We further prove that when the user population grows large, pure NEs get closer to a Proportionally Fair (PF) allocation of users to servers, and we characterize the gap between equilibriums and this ideal allocation depending on user population. Under the RLS algorithm, the system converges to pure NEs: we study the time it takes for the system to reach the PF allocation within a certain margin.