Load balancing and density dependent jump Markov processes

摘要: We provide a new approach for analyzing both static and dynamic randomized load balancing strategies. demonstrate the by providing first analysis of following model: customers arrive as Poisson stream rate /spl lambda//sub n/, lambda/<1, at collection n servers. Each customer chooses some constant d servers independently uniformly random from servers, waits service one with fewest customers. Customers are served according to first-in first-out (FIFO) protocol, time is exponentially distributed mean 1. call this problem supermarket model. wish know how system behaves, in particular we interested expected spends equilibrium. The model provides good abstraction simple, efficient scheme setting where jobs large parallel processors. This appears more realistic than similar models studied previously, that it open: is, over time, number not fixed.