Load balancing in processor sharing systems
Load balancing in processor sharing systems
复制标题
处理器共享系统中的负载平衡
DOI：
10.1007/s11235-010-9300-8
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
B. Prabhu
中科院分区：
文献类型：
--
作者：
E. Altman;U. Ayesta;B. Prabhu
我们研究最优的负载平衡策略的多类多服务器处理器共享系统的泊松输入流，异构的服务率，和服务器依赖的每单位时间的持有成本。具体来说，我们研究（一）集中式设置，其中调度员路由传入的工作基于他们的服务时间要求，以尽量减少加权平均逗留时间在系统中;和（二）分散，分布式的非合作设置，其中每个工作，知道它的服务时间，选择一个服务器的目标是尽量减少其加权平均逗留时间在系统中。对于分散环境，我们证明了一个势函数的存在性，它允许我们将非合作博弈转化为一个标准的凸优化问题;对于上述两种环境，我们刻画了最优路由策略集，并得到了每个服务器上负载的封闭形式表达式.此外，我们证明了存在一个最优的政策，路由的工作独立于其服务时间的要求。我们还表明，去中心化设置中使用的服务器集是集中式设置中使用的服务器集的子集。最后，我们通过研究所谓的无政府状态价格（PoA），即分散和最佳集中解决方案之间的比率，比较了两种设置中的工作所感知的性能。当所有服务器的单位时间持有成本相同时，已知PoA的上界由系统中的服务器数量决定。有趣的是，我们证明了我们系统的PoA可以是无界的。特别是这表明，在我们的系统中，自私路由的性能可能是非常低效的。
We investigate optimal load balancing strategies for a multi-class multi-server processor-sharing system with a Poisson input stream, heterogeneous service rates, and a server-dependent holding cost per unit time. Specifically, we study (i) the centralized setting in which a dispatcher routes incoming jobs based on their service time requirements so as to minimize the weighted mean sojourn time in the system; and (ii) the decentralized, distributed non-cooperative setting in which each job, aware of its service time, selects a server with the objective of minimizing its weighted mean sojourn time in the system. For the decentralized setting we show the existence of a potential function, which allows us to transform the non-cooperative game into a standard convex optimization problem.For the two aforementioned settings, we characterize the set of optimal routing policies and obtain a closed form expression for the load on each server under any such policy. Furthermore, we show the existence of an optimal policy that routes a job independently of its service time requirement. We also show that the set of servers used in the decentralized setting is a subset of set of servers used in the centralized setting. Finally, we compare the performance perceived by jobs in the two settings by studying the so-called Price of Anarchy (PoA), that is, the ratio between the decentralized and the optimal centralized solutions. When the holding cost per unit time is the same for all servers, it is known that the PoA is upper bounded by the number of servers in the system. Interestingly, we show that the PoA for our system can be unbounded. In particular this indicates that in our system, the performance of selfish routing can be extremely inefficient.