The success of nature inspired algorithms,
particularly Ant Colony Optimization (ACO) on various
optimization and scheduling problems has inspired to apply
this approach on load balancing problem. Messor is one
such approach based on AntNet which achieved limited
success with some unaddressed problems. Extending the
Messor's work, in this paper, we propose an ACO based
approach to address load balancing problem. In our
approach, Swarm Intelligent techniques aid in identifying a
suitable node for task transfers from overloaded network
nodes to under loaded nodes and ANNs aid in directional
decision making process that drives the ant search. The
proposed approach is evaluated against Messor with two
types of load arrival strategies static and dynamic on
different sized networks with 20, 40, 60, 80 and 100 nodes
and the experimental results show that the proposed
approach has resulted in achieving better performance.
Neeharika V : Department of Computing, Unitec Institute of Technology
Auckland, New Zealand
Sreenivas Sremath Tirumala : School of Computer and Mathematical Sciences, AUT University
Auckland, New Zealand
Gang Chen : Victoria University of Wellington
Wellington, New Zealand
Jayawardena C : Victoria University of Wellington
Wellington, New Zealand
Distributed Computing
Load Balancing
Ant
Colony Optimization
Messor
This paper proposes a new load balancing approach for
distributed networks, utilizing ACO and ANN. This work
was motivated by the research works conducted in a P2P system called Messor and is further improvised by
exploring the available literature and attempts to address
the shortcomings of Messor. In the proposed approach,
load information is collected by ants (ACO Inspired)
which serve as mobile agents. These ants are aided by
ANNs for optimal decision making to find a suitable node
for job transfer. Based on this decision the process of task
migration is carried out at the node level. The proposed
approach is tested on five different sized networks and
with two different job arrival strategies (fixed and
dynamic) to analyze the possibility of performance
variations. In the fixed job arrival strategy experiment
(experiment 1), network load balance is achieved at
iteration number 18. Whereas in a dynamic job arrival
strategy (experiment 2), load balance is achieved in
iteration number 19. This variation is due to the busyness
of nodes performing their own jobs while attending to the
jobs from overloaded nodes. Experiments are conducted
considering the combination of the job arrival strategies
and variable network sizes. The proposed approach
showed consistent performance irrespective of the network
size and job arrival strategies.
[1] R. Mishra and A. Jaiswal, “Ant colony optimization: A
solution of load balancing in cloud,” International
Journal of Web & Semantic Technology (IJWesT), vol. 3,
no. 2, pp. 33–50, 2012.
[2] S. H. Bokhari, Assignment problems in parallel and
distributed computing. Springer Science &
Business Media, 1987, vol. 32.
[3] M. Dorigo and T. Stutzle, “The ant colony optimization
metaheuristic:¨ Algorithms, applications, and advances,”
in Handbook of metaheuristics. Springer, 2003, pp. 250–
285.
[4] M. Livny and M. Melman, “Load balancing in
homogeneous broadcast distributed systems,” in ACM
SIGMETRICS Performance Evaluation Review, vol. 11,
no. 1. ACM, 1982, pp. 47–55.
[5] A. Y. Zomaya and Y.-H. Teh, “Observations on using
genetic algorithms for dynamic load-balancing,” Parallel
and Distributed Systems, IEEE Transactions on, vol. 12,
no. 9, pp. 899–911, 2001.
[6] N. G. Shivaratri, P. Krueger, and M. Singhal, “Load
distributing for locally distributed systems,” Computer,
vol. 25, no. 12, pp. 33–44, 1992.
[7] G. Cybenko, “Dynamic load balancing for distributed
memory multiprocessors,” Journal of parallel and
distributed computing, vol. 7, no. 2, pp. 279–301, 1989.
[8] O. Kremien and J. Kramer, “Methodical analysis of
adaptive load sharing algorithms,” Parallel and
Distributed Systems, IEEE Transactions on, vol. 3, no. 6,
pp. 747–760, 1992.
[9] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm
intelligence: from natural to artificial systems. Oxford
university press, 1999, no. 1.
[10] J. E. Bell and P. R. McMullen, “Ant colony optimization
techniques for the vehicle routing problem,” Advanced
Engineering Informatics, vol. 18, no. 1, pp. 41–48, 2004.
[11] C. Blum, “Ant colony optimization: Introduction and
recent trends,” Physics of Life reviews, vol. 2, no. 4, pp.
353–373, 2005.
[12] B. Fox, W. Xiang, and H. P. Lee, “Industrial applications
of the ant colony optimization algorithm,” The
International Journal of Advanced Manufacturing
Technology, vol. 31, no. 7-8, pp. 805–814, 2007.
[13] Z. Juanping, F. Xiuhui, and J. Ying, “An improved ant
colony optimization algorithm for mobile robot path
planning,” in Intelligent Systems and Applications (ISA),
2011 3rd International Workshop on. IEEE, 2011, pp. 1–
4.
[14] A. K. Gupta, H. Sadawarti, and A. K. Verma, “Manet
routing protocols based on ant colony optimization,”
2012.
[15] M. A. Salehi, H. Deldari, and B. M. Dorri, “Balancing
load in a computational grid applying adaptive,
intelligent colonies of ants.” Informatica (Slovenia), vol.
32, no. 3, pp. 327–335, 2008.
[16] K. M. Sim and W. H. Sun, “Multiple ant-colony
optimization for network routing,” in Cyber Worlds,
2002. Proceedings. First International Symposium on.
IEEE, 2002, pp. 277–281.
[17] D. Ferrari and S. Zhou, “An empirical investigation of
load indices for load balancing applications,” DTIC
Document, Tech. Rep., 1987.
[18] S. Shaharuddin and A. Y. Zomaya, Scheduling in
parallel computing systems: fuzzy and annealing
techniques. Kluwer Academic Publishers, 1999.
[19] A. Montresor, “Anthill: a framework for the design and
analysis of peer-to-peer systems,” in 4th European
Research Seminar on Advances in Distributed Systems,
Bertinoro, Italy. Citeseer, 2001.