Optimal selection of routs in data transmission networks. Energy approach
DOI:
https://doi.org/10.3103/S0735272708100099Abstract
A new algorithm has been proposed for solving the problem of optimal alternative routing based on the energy approach to the network analysis with generalization of Kirchhoff’s laws. This algorithm is the fastest among a wide class of optimization methods based on finding an admissible direction of decreasing the target function. By the example of network analysis it was shown in the case of a quadrature target function this algorithm requires only one iteration for finding an optimal solution that favorably distinguishes it from the gradient projection and other possible methods. Optimization of the same network was conducted by the criterion of average delay minimum that is one of the main criteria used in optimizing networks of queues with representative time of message servicing.
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 for Information Networks with Critical Load (Mashinostroyeniye-1, Moscow, 2004) [in Russian].
D. Bertsekas and R. Gallager, Data Networks (Prentice-Hall, New Jersey, 1987; Mir, Moscow, 1989).
G. Kron, Tensor Analysis of Networks (John Wiley&Sons, Inc., New York, 1939; Sov. Radio, Moscow, 1978).
