On the behaviour of learning algorithms in a changing environment with application to data network routing problem. (English) Zbl 0706.68018

Vasilakos, Athanasios V.

Kybernetika 26, No. 4, 296-307 (1990).

Summary: In data networks the message has peak and slack periods and the topology may change. A learning automaton is situated at each node of the network where a routing decision must be made and directs traffic entering the node onto one of the outgoing links. Using network feedback, an automaton modifies its routing strategy to improve its link selections. This approach has the advantage over existing routing schemes of offering a simple and extremely practical feedback and updating policy. A new model of a nonstationary automaton environment is proposed and the limiting behaviour of this model is analysed. Simulation studies of automata operating in simple networks verify the analytical results.

MSC:

68M10	Network design and communication in computer systems
68T05	Learning and adaptive systems in artificial intelligence
68W10	Parallel algorithms in computer science

Keywords:

packet-switched network; network routing; virtual and datagram network; circuit-switched network; learning

References:

[1]	R. G. Gallager: A minimum delay routing algorithm using distributed computation. IEEE Trans. Comm. 25 (1977), 73-84. · Zbl 0361.68086
[2]	L. Kleinrock: Queueing Systems: II-Applications. J. Wiley, New York 1976. · Zbl 0361.60082
[3]	K. S. Narendra L. G. Mason, S. S. Tripathi: Application of learning automata to telephone traffic routing problems. Preprints of 1974 Joint Automatic Control Conference, Austin, TX, 18-21 June 1974, pp. 753-759.
[4]	K. S. Narendra, M. A. L. Thathachar: Learning automata: a survey. IEEE Trans. Systems Man Cybernet. 4(1974), 323 - 334. · Zbl 0279.68067
[5]	K. S. Narendra E. A. Wright, L. G. Mason: Application of learning automata to telephone traffic routing and control. IEEE Trans. Systems Man Cybernet. 7 (1977), 11, 785-792.
[6]	M. F. Norman: Markov Processes and Learning Models. Academic Press, New York-London 1972. · Zbl 0262.92003
[7]	A. S. Tanenbaum: Computer Networks. Prentice-Hall, Englewood Cliffs, N. J. 1980. · Zbl 0825.68147
[8]	R. Larsen: Functional Analysis. Marcel-Dekker, New York 1973. · Zbl 0261.46001
[9]	V. A. Vasilakos: Learning algorithm in non-stationary environments, with application to data networks. Working Paper, Univ. of Patras.
[10]	V. A. Vasilakos, S. A. Koubias: Learning automata control of data communication networks. Proc. 12th IMACS World Congress on Scientific Computation, Paris, July 1988.
[11]	V. A. Vasilakos, S. A. Koubias: On routing and performance comparison of techniques for packet-switched networks using learning automata. Proc. IEEE Internat. Symposium on Circuits and Systems, Espoo, Finland, June 1988.