Performance Analysis of Learning Automata-Based Routing Algorithms in Sparse Graphs

Authors: Z.Farhadpour, Mohammad.R.Meybodi

Abstract:

A number of routing algorithms based on learning automata technique have been proposed for communication networks. How ever, there has been little work on the effects of variation of graph scarcity on the performance of these algorithms. In this paper, a comprehensive study is launched to investigate the performance of LASPA, the first learning automata based solution to the dynamic shortest path routing, across different graph structures with varying scarcities. The sensitivity of three main performance parameters of the algorithm, being average number of processed nodes, scanned edges and average time per update, to variation in graph scarcity is reported. Simulation results indicate that the LASPA algorithm can adapt well to the scarcity variation in graph structure and gives much better outputs than the existing dynamic and fixed algorithms in terms of performance criteria.

Keywords: Learning automata, routing, algorithm, sparse graph

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329210

References:

[1] S. Misra, , B. John Oommen," An Efficient Dynamic Algorithm for MaintainingAll-Pairs Shortest Paths in Stochastic Networks," IEEE TRANSACTIONS ON COMPUTERS, VOL. 55, NO. 6, JUNE 2006.
[2] G. I. Papadimitriou, M. Sklira, and A. S. Pomportsis," A New Class of ╬Á - Optimal Learning Automata," IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICSÔÇöPART B: CYBERNETICS, VOL. 34, NO. 1, FEBRUARY 2004.
[3] N. Baba,,Y. Mogami, "A New Learning Algorithm for the Hierarchical Structure Learning Automata Operating in the Nonstationary S-Model Random Environment," IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICSÔÇöPART B: CYBERNETICS, VOL. 32, NO. 6, DECEMBER 2002.
[4] M. A. L. Thathachar, P. S. Sastry,"Varieties of Learning Automata: An Overview," IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICSÔÇöPART B: CYBERNETICS, VOL. 32, NO. 6, DECEMBER 2002.
[5] M. S. Obaidat, G. I. Papadimitriou, and A. S. Pomportsis, "LearningAutomata: Theory, paradigms and applications," IEEE Trans. Syst., Man,and Cybern., vol. 32, no. 6, pp. 706-709, Dec. 2002.
[6] G. I. Papadimitriou and A. S. Pomportsis, "Learning-automata-based TDMA protocols for broadcast communication systems with burstytraffic," IEEE Commun. Lett., vol. 4, no. 3, pp. 107-109, 2000.
[7] P. Narvaez, K.-Y Siu, and H. Y. Tzeng, "New dynamic algorithms for shortest path tree computation," IEEE/ACM Trans. Networking, vol. 8, pp. 734-746, 2000.
[8] B. J. Oommen and E. V. de St. Croix, "Graph partitioning using learning automata," IEEE Trans. Comput., vol. 45, pp. 195-208, 1995.
[9] B. J. Oommen and T. D. Roberts, "Continuous learning automata solutions to the capacity assignment problem," IEEE Trans. Comput., vol.49, pp. 608-620, Jun. 2000.
[10] G. Ramalingam, Bounded Incremental Computation. Berlin:Springer- Verlag, 1996, vol. 1089, Lecture Notes in Computer Science.
[11] K. S. Narendra and M. A. L. Thathachar, Learning Automata. EnglewoodCliffs, NJ: Prentice-Hall, 1989.
[12] S. Lakshmivarahan, Learning Algorithms Theory and Applications.New York: Springer-Verlag, 1981.