Open Access Open Access  Restricted Access Subscription Access

Algorithm of conditional minimization of the goal function for optimal routing in information networks

Vladimir I. Parfenov, S. V. Zolotarev


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.

Full Text:



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].

© Radioelectronics and Communications Systems, 2004–2020
When you copy an active link to the material is required
ISSN 1934-8061 (Online), ISSN 0735-2727 (Print)
tel./fax +38044 204-82-31, 204-90-41