An Online Load Balancing Algorithm for a Hierarchical Ring Topology


  • Ciprian I. Paduraru Computer Science Department University of Bucharest


ring, hierarchical, distributed, balancing, algorithm, fairness


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.


Oguz AKAY, Kayhan ERCIYES, A Dynamic Load Balancing model for a distributed system, Mathematical & Computational Applications, 8(3):353-350, 2003.

Ciprian Paduraru, A New Online Load Balancing Algorithm in Distributed Systems, Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 14th edition, Pages:327-334, 2012.

Andrew S. Tanenbaum, Modern Operating Systems (3rd Edition), Prentice Hall, December 2007.

Kwang Soo Cho, Un Gi Joo, Heyung Sub Lee, Bong Tae Kim, and Won Don Lee, Efficient Load Balancing Algorithms for a Resilient Packet Ring Using Artificial Bee Colony, Applications of Evolutionary Computation, LNCS, 6025:61-70, 2010.

G. Ravindran and M. Stumm, Hierarchical Ring Topologies and the Effect of their Bisection Bandwidth Constraints, Proc. Intl. Conf.Parallel Processing, I:51-55, 1995.

Perry Fizzano and Clifford Stein, Scheduling on a Ring with Unit Capacity Links, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, Pages:210-219, 1994.

Johannes E. Gehrke, C. Greg Plaxton and Rajmohan Rajaraman, Rapid Convergence of a Local Load Balancing Algorithm for Asyncronous Rings, Distributed Algorithms, LNCS, 1320:81-95, 1997.

Young-Soo Myung, Hu-Gon Kim, Dong-Wan Tcha, Optimal Load Balancing on Sonet Bidirectional Rings, Operations Research, 45(1):148-152, 1997.

Dekel Tsur, Improved scheduling in rings, Journal of Parallel and Distributed Computing, 67(5):531-535, 2007.

Amir Gourgy, Ted H. Szymanski, Cooperative Token-Ring Scheduling For Input-Queued Switches, Journal of Parallel and Distributed Computing, 58(3):351-364, 2009.

Leonidas Georgiadis, Wojciech Szpankowski, Leandros Tassiulas, A scheduling policy with maximal stability region for ring networks with spatial reuse, Queueing Systems (Springer), 19(1-2):131-148, 1995.

Joseph (Seffi) Naor, Adi Rosen, Gabriel Scalosub, Online time-constrained scheduling in linear and ring networks, Journal of Discrete Algorithms, 8(4):346-355, 2010.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.