An Online Load Balancing Algorithm for a Hierarchical Ring Topology

Ring networks are an important topic to study because they have certain advantages over their direct network counterparts: easier to manage, better bandwidth, cheaper and wider communication paths. This paper proposes a new online load balancing algorithm for distributed real-time systems having a hierarchical ring as topology. The novelty of the algorithm lies in the goal it tries to achieve and the method used for load balancing. The main goal of the algorithm is to correctly utilize the computing resources in order to satisfy the average response time of clients. The secondary goal is to ensure fairness between the numbers of requests solved per client with respect to the average response time. A request from a client is moving through the network until a node considers that it can solve the request in the promised average time for that client or until it seems like the best opportunity to avoid any additional delays in solving it. A performance analysis and motivation for the proposed algorithm is given with respect to the goals it tries to achieve. The results show that the proposed algorithm satisfies its goals.