Analysis of Rate-Based Pull and Push Strategies with Limited Migration Rates in Large Distributed Networks

Abstract

In this paper we analyze the performance of pull and push strategies in large homogeneous distributed systems where the number of job transfers per time unit is limited. Job transfer strategies which rely on lightly-loaded servers to attract jobs from heavily-loaded servers are known as pull strategies, whereas for push strategies the heavily loaded servers initiate the job transfers to lightly loaded servers. To this end, servers transmit probe messages to discover other servers that are able to take part in a job transfer. Previous work on rate-based pull and push strategies focused on the impact of the probe rate on the mean job response time. In this paper we also limit the overall migration rate and show that any predefined migration rate can be matched by both the rate-based pull and push strategies. We present closed form formulas for the mean response time (as a function of the allowed probe and migration rate) and validate their accuracy by simulation. We also introduce and analyze a new pull strategy and show that under high loads it is superior to the push strategies considered, while the push strategies offer only a very limited gain for medium to low load scenarios.