GSM-R: A Hybrid Scheduling Approach to Dynamic Load Balancing in Hierarchical Cluster of Servers

Assume a hierarchical cluster of servers is composed of logical groups, and each logical group is further made up of physical servers. Based on certain assumptions and the generalized supermarket model (GSM) scheduling, we present a hybrid scheduling based approach to dynamic load balancing in a hierarchical cluster of servers, GSM-R. From the viewpoint of probability, this model is analyzed in detail and a dramatic result is achieved: for the large scale of hierarchical cluster of servers, at the steady state of the system, the average time consumed for tasks converges to the theoretical limit by use of the GSM-R strategy of dynamic load balancing; this means that the total time consumed for a task is almost completely spent on its necessary service fraction without extra waiting time.