An Online Load Balancing Algorithm for a Hierarchical Ring Topology
Keywords:
ring, hierarchical, distributed, balancing, algorithm, fairnessAbstract
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.
References
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. http://dx.doi.org/10.1007/978-3-642-12242-2_7
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. http://dx.doi.org/10.1145/181014.181333
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. http://dx.doi.org/10.1007/BFb0030677
Young-Soo Myung, Hu-Gon Kim, Dong-Wan Tcha, Optimal Load Balancing on Sonet Bidirectional Rings, Operations Research, 45(1):148-152, 1997. http://dx.doi.org/10.1287/opre.45.1.148
Dekel Tsur, Improved scheduling in rings, Journal of Parallel and Distributed Computing, 67(5):531-535, 2007. http://dx.doi.org/10.1016/j.jpdc.2007.02.002
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. http://dx.doi.org/10.1007/BF01148943
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. http://dx.doi.org/10.1016/j.jda.2010.07.001
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
