Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
复制标题
异构并行服务器之间基于拉动的负载分配：多个路由器的情况
作者：
A. Stolyar
该模型是一个服务系统，由多个大型服务器池组成。服务器的处理速度和缓冲区大小（可能是有限的或无限的）取决于池。客户的输入流被平均分配到固定数量的路由器中，这些路由器必须在客户到达后立即将其分配给服务器。我们考虑一种渐进机制，其中总客户到达率和池大小同时缩放到无穷大，与缩放参数 n 成比例，而路由器的数量保持固定。我们定义并研究了基于拉动的客户分配（路由）算法 PULL 的多路由器泛化，该算法在 Stolyar (Queueing Syst 80(4): 341–361, 2015) 中针对单路由器模型引入。在PULL算法下，当服务器空闲时，它向随机均匀选择的路由器发送“拉消息”；每个路由器独立运行 - 它根据随机统一选择的可用（在该路由器上）拉消息（如果有）将到达的客户分配给服务器，否则分配给整个系统中随机统一选择的服务器。在马尔可夫假设（泊松到达过程和独立指数分布服务要求）下，在亚临界系统负载下，我们证明了 PULL 的渐近最优性： n→∞documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{文档}$$n
ightarrow infty $$end{document}，到达的客户遇到阻塞或等待的稳态概率消失。此外，PULL 的路由器-服务器消息交换率极低，每个客户一条消息。这些结果概括了 Stolyar (2015) 中的一些单路由器结果。
The model is a service system, consisting of several large server pools. A server’s processing speed and buffer size (which may be finite or infinite) depend on the pool. The input flow of customers is split equally among a fixed number of routers, which must assign customers to the servers immediately upon arrival. We consider an asymptotic regime in which the total customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to a scaling parameter n, while the number of routers remains fixed. We define and study a multi-router generalization of the pull-based customer assignment (routing) algorithm PULL, introduced in Stolyar (Queueing Syst 80(4): 341–361, 2015) for the single-router model. Under the PULL algorithm, when a server becomes idle it sends a “pull-message” to a randomly uniformly selected router; each router operates independently—it assigns an arriving customer to a server according to a randomly uniformly chosen available (at this router) pull-message, if there is any, or to a randomly uniformly selected server in the entire system otherwise. Under Markov assumptions (Poisson arrival process and independent exponentially distributed service requirements), and under subcritical system load, we prove asymptotic optimality of PULL: as n→∞documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$n
ightarrow infty $$end{document}, the steady-state probability of an arriving customer experiencing blocking or waiting vanishes. Furthermore, PULL has an extremely low router–server message exchange rate of one message per customer. These results generalize some of the single-router results in Stolyar (2015).