%0 Conference Paper %1 7277435 %A Mukhopadhyay, A. %A Mazumdar, R.R. %A Guillemin, F. %B Teletraffic Congress (ITC 27), 2015 27th International %D 2015 %K Chaos Cloud_computing Limiting Mathematical_model Poisson_process Random_variables Routing Servers average_blocking_probability_reduction cloud_computing cloud_computing_application heterogeneous_loss_system itc itc27 mean_field_analysis multiserver_system network_servers randomized_routing stationary_tail_probability stochastic_processes telecommunication_network_routing %P 125-133 %R 10.1109/ITC.2015.22 %T The Power of Randomized Routing in Heterogeneous Loss Systems %U https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc27/7277435.pdf?inline=true %X Motivated by cloud computing applications, we consider a multi-server system, consisting of a large number of parallel servers, where jobs arrive according to a Poisson process and are assigned to the servers for processing. Each server has the capacity to process only a finite number of jobs simultaneously and different servers have different capacities. A job is accepted for processing only if there is a vacancy available at the server to which it is assigned. Otherwise, the job is discarded or blocked. We consider randomized schemes to assign jobs to servers with the aim of reducing the average blocking probability of jobs in the system. In particular, we consider a scheme that assigns an incoming job to the server having maximum available vacancy among d randomly sampled servers. We consider the system in the limit where both the number of servers and the arrival rate of jobs are scaled by a large factor. This gives rise to a mean field analysis. We show that in the limiting system servers behave independently. Stationary tail probabilities of server occupancies are obtained from the stationary solution of the mean field which is shown to be unique and globally attractive. We further characterize the rate of decay of the stationary tail probabilities. Numerical results suggest that the proposed scheme significantly reduces the average blocking probability of jobs compared to static schemes that probabilistically route jobs to servers independently of their states.

@inproceedings{7277435, abstract = {Motivated by cloud computing applications, we consider a multi-server system, consisting of a large number of parallel servers, where jobs arrive according to a Poisson process and are assigned to the servers for processing. Each server has the capacity to process only a finite number of jobs simultaneously and different servers have different capacities. A job is accepted for processing only if there is a vacancy available at the server to which it is assigned. Otherwise, the job is discarded or blocked. We consider randomized schemes to assign jobs to servers with the aim of reducing the average blocking probability of jobs in the system. In particular, we consider a scheme that assigns an incoming job to the server having maximum available vacancy among d randomly sampled servers. We consider the system in the limit where both the number of servers and the arrival rate of jobs are scaled by a large factor. This gives rise to a mean field analysis. We show that in the limiting system servers behave independently. Stationary tail probabilities of server occupancies are obtained from the stationary solution of the mean field which is shown to be unique and globally attractive. We further characterize the rate of decay of the stationary tail probabilities. Numerical results suggest that the proposed scheme significantly reduces the average blocking probability of jobs compared to static schemes that probabilistically route jobs to servers independently of their states.}, added-at = {2016-02-17T10:46:22.000+0100}, author = {Mukhopadhyay, A. and Mazumdar, R.R. and Guillemin, F.}, biburl = {https://www.bibsonomy.org/bibtex/2f14a910b73f11972315727f295a80132/itc}, booktitle = {Teletraffic Congress (ITC 27), 2015 27th International}, doi = {10.1109/ITC.2015.22}, interhash = {0e2d646ec17750a6f82b013a42fa2e5c}, intrahash = {f14a910b73f11972315727f295a80132}, keywords = {Chaos Cloud_computing Limiting Mathematical_model Poisson_process Random_variables Routing Servers average_blocking_probability_reduction cloud_computing cloud_computing_application heterogeneous_loss_system itc itc27 mean_field_analysis multiserver_system network_servers randomized_routing stationary_tail_probability stochastic_processes telecommunication_network_routing}, month = {Sept}, pages = {125-133}, timestamp = {2020-04-30T18:18:14.000+0200}, title = {The Power of Randomized Routing in Heterogeneous Loss Systems}, url = {https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc27/7277435.pdf?inline=true}, year = 2015 }