2015/12/24 by Alexander Stolyar, Stolyar, Alexander
Computer Science · Business, Management and Accounting · #Optimization and Search Problems #Advanced Queuing Theory Analysis #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1512.07873
The model is a service system, consisting of several large server pools. A\nserver processing speed and buffer size (which may be finite or infinite)\ndepend on the pool. The input flow of customers is split equally among a fixed\nnumber of routers, which must assign customers to the servers immediately upon\narrival. We consider an asymptotic regime in which the customer total arrival\nrate and pool sizes scale to infinity simultaneously, in proportion to a\nscaling parameter n, while the number of routers remains fixed.\n We define and study a multi-router generalization of the pull-based customer\nassignment (routing) algorithm PULL, introduced in [11] for the single-router\nmodel. Under PULL algorithm, when a server becomes idle it send a\n"pull-message" to a randomly uniformly selected router; each router operates\nindependently -- it assigns an arriving customer to a server according to a\nrandomly uniformly chosen available (at this router) pull-message, if there is\nany, or to a randomly uniformly selected server in the entire system,\notherwise.\n Under Markov assumptions (Poisson arrival process and independent\nexponentially distributed service requirements), and under sub-critical system\nload, we prove asymptotic optimality of PULL: as n\→\∞, the steady-state\nprobability of an arriving customer experiencing blocking or waiting, vanishes.\nFurthermore, PULL has an extremely low router-server message exchange rate of\none message per customer. These results generalize some of the single-router\nresults in [11].\n