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

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.

Authors:

• Z.Farhadpour
• Mohammad.R.Meybodi

Keywords:

• Learning automata
• routing
• algorithm
• sparse graph

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.