Algorithm of conditional minimization of the goal function for optimal routing in information networks
DOI:
https://doi.org/10.3103/S0735272708050026Abstract
A new algorithm has been proposed for solving the optimal routing problem. This algorithm is based on applying the Kirchhoff laws to information networks and does not require the mandatory use of derivatives of the goal function making it quite convenient for distributed realizations. The algorithm convergence is substantiated by drawing an analogy between information and electric networks. On the basis of a case study of the network it was shown that its speed is tens of times as high as that of the flow deviation algorithm. It was shown that theoretical labor intensity of implementing this method is substantially less than that of the algorithms based on finding the shortest routes, since the cyclic part of this algorithm does not contain laborious logical operations.
References
L. Fratta, M. Gerla, and L. Kleinrock, “The Flow Deviation Method: An Approach to Store and Forward Communication Network Design,” Networks 3, No. 2, 97 (1973).
M. Schwartz and C. K. Cheung, “The Gradient Projection Algorithm for Multiple Routing in Message–Switched Networks,” IEEE Trans. Commun. 25, 100 (1976).
M. Frank and P. Wolfe, “An Algorithm for Quadratic Programming,” Naval Research Logistic Quarterly, No. 3, 95 (1956).
I. I. Pasechnikov, Methodology of Analysis and Synthesis of Information Networks with Maximum Load (Mashinostroenie-1, Moscow, 2004) [in Russian].
D. Bertsekas and R. Gallager, Data Networks (Mir, Moscow, 1989) [Russian translation].
G. Kron, Tensor Analysis of Networks (Sov. Radio, Moscow, 1978) [Russian translation, ed. by L. T. Kuzina and P. G. Kuznetsova].
